Concurrent systems are systems where several threads of computation are potentially executing simultaneously and interacting.

learn more… | top users | synonyms

5
votes
1answer
76 views

Question about threads and locks

I am currently reading Fuss, Futexes and Furwocks: Fast Userland Locking in Linux and came across this quote: In a fair locking scheme the lock is granted in the order it was requested. This can ...
1
vote
1answer
32 views

If a thread containing main terminates, can another thread do anything?

I'm studying threads in C and I have this theoretical question in mind that is driving me crazy. Assume the following code: ...
1
vote
0answers
17 views

Why is this execution happens-before consistent?

In section 17.4.5 "Happens-before Order" of Java Language Specification, a trace is examined for the notion of happens-before consistency. The trace is shown in the figure in which $A$ and $B$ are ...
3
votes
0answers
59 views

“Data-race free” programs

In section 6.3 of the paper Causal memory: definitions, implementations, and programming, the authors define "data-race free" as follows: Program $\Pi$ is data-race free if, for all histories $H$ ...
1
vote
0answers
21 views

Proof strategies for linearizability of implementations

Background: In section 4.2 of the paper Linearizable Implementations Do Not Suffice for Randomized Distributed Computation@STOC'2011, the authors mentioned two typical proof strategies for ...
3
votes
0answers
29 views

What are methods for showing that concurrent objects are not linearizable?

Linearizability is a well-known correctness condition for concurrent objects. It provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point ...
2
votes
0answers
36 views

Proof of contention of the wait-free consensus algorithm

I know that this is a known theorem but I can't find its proof. The theorem is: The write-contention of any $n$-process wait-free consensus algorithm (implemented from any read-modify-write ...
2
votes
0answers
22 views

Polylogarithmic value-bounded concurrent data structures such as max register, counter, and monotone circuit

While reading the research paper Polylogarithmic Concurrent Data Structures from Monotone Circuits [@JACM'2012] by James Aspnes, Hagit Attiya, and Keren Censor-Hillel, I am not sure about some points ...
0
votes
1answer
150 views

Deadlock and cycle in a resource allocation graph

Here is a resource allocation graph asked in my Operating Systems Theory midterm. The question is, "Is there a deadlock here? Explain your answer in detail" Ra and Rb are resource sets and every ...
2
votes
1answer
38 views

Finding issues in concurrent implementation of carpark overflow control

Firstly, I am revising for my Concurrent Programming exam and have come across the following question from a previous exam paper. I have attempted to answer it, and will try and convey this effort; ...
6
votes
3answers
258 views

Difference between Parallel and Concurrent programming?

When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel. And some programming languages specifically claim support for parallel programming, such as Java. ...
3
votes
2answers
89 views

How can an extended linearizable history G be equivalent to sequential history S?

I am undertaking a module in Concurrent Programming where some of the new content this year covers linearizability, the Java Memory Model, and sequential consistency. Our class slides are companion ...
2
votes
1answer
119 views

Differences between the Actor Model and Communicating Sequential Processes (CSP)

When we look at the Actor Model and Communicating Sequential Processes we see that they are both trying to do concurrency based on message passing, yet they are distinct. (We see implementations of ...
2
votes
1answer
44 views

How to express Rob Pike's classic Go Code presentation in Hoare's CSP Algebra?

At 15:30 in this talk (p13 of this presentation here) Rich Hickey mentions the formalisms available for reasoning about Communicating Sequential Processes. He then goes on to mention that these ...
1
vote
0answers
18 views

defining the operational semantics of a concurrent language

As big-step operational semantics is about evaluating an expression to a final value, can we state that for defining a concurrent language one needs small-step semantics, as concurrent programs need ...
-2
votes
1answer
82 views

Number of concurrent schedules in database

In a database system, say there are $N$ transactions each having $m_1,m_2,\dots,m_N$ operations. How many concurrent schedules are possible? $(m_1+m_2+....+m_n)!$ is the number of possible ...
2
votes
2answers
711 views

Difference between multitasking, multithreading and multiprogramming

I was a little confused between these three terms Multitasking, Multithreading and Multiprogramming Although every one means executing different lines of codes, and for every one we need something ...
1
vote
1answer
67 views

Is it possible to do multitasking without context switch with just one cpu?

All the article I can find seems to talk about multitasking and context switch as its a two different thing. It seems that multitasking and context switch are the same thing.
4
votes
3answers
288 views

Solutions to synchronization problem need to be executed in critical section

I was reading about synchronization problems for cooperating processes and i learned that only hardware solutions like test_and_wait() and ...
1
vote
3answers
231 views

Maximum degree of concurrency in task dependency graphs

I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find ...
1
vote
0answers
18 views

What are some visual tools for the design of concurrent systems?

I am looking for visual tools for the design, and optionally verifications, of concurrent systems. PS: There is no tag for visual-programming, I must have 150 reputation to create one, so please ...
5
votes
3answers
110 views

Is it possible to prove thread safety?

Given a program consisting of variables and instructions which modify these variables, and a synchronization primitive (a monitor, mutex, java's synchronized or C#'s lock), is it possible to prove ...
0
votes
2answers
116 views

What is the impact of synchronisation overhead on parallel speedup? [closed]

When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used? Is coarse-grained parallelism better ...
6
votes
2answers
152 views

Automaton equivalent of the π calculus?

If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing ...
4
votes
2answers
89 views

How does a race condition work?

When two threads try to access the same resources at exactly the same time how does the computer decide which one gets the resource, or is it just decided at random?
9
votes
1answer
2k views

Understanding Peterson’s and Dekker’s algorithms

I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries. I tried to formulate the algorithms in informal language like follows: ...
1
vote
1answer
79 views

Using Little's law to find the average N of customers

I'm trying to understand Little's law and can't seem to get past this scenario: Let's say people arrive at the register at 12 per hour. It takes 10 minutes (1/6 of an hour) to service each one of ...
3
votes
1answer
41 views

Is there a mistake in the expression for clean behavior in Pnueli's article from 81'?

I am reading an article called The temporal semantics of concurrent programs . On page $9$, there is a small section (numbered as $2$) called "clean behavior". I think that there is a problem with ...
1
vote
1answer
71 views

Definition of “K-fairness” with respect to concurrency?

There are definitions of Absolute, Strong and Weak Fairness available across the internet, but I cannot find a definition of "K-Fairness" property for critical section algorithms (also algorithms that ...
16
votes
1answer
733 views

What does 'true concurrency' mean?

I often hear phrases like 'true concurrency semantics' and 'true concurrency equivalences' without any references. What does those terms mean and why are they important? What are some examples of ...
5
votes
1answer
83 views

Formalisms in concurrent and/or distributed programming?

My background came from imperative languages, primarily C, C++, and Python. I picked up Scala, Erlang, and a bit of Haskell a few years later and have since become very interested in functional ...
0
votes
1answer
113 views

concurrency and hardware

I've a couple of questions that I need answers for. What I am looking for here is the outline of the answers. Not necessarily the exact complete answer. I can do that. The question is that common ...
1
vote
1answer
72 views

Synchronization using serialization

How can someone synchronize two or more threads using serialization? According to my professor's slides and code assignments you can use serialization to solve the synchronization problem. (He doesn't ...
0
votes
1answer
58 views

applying CTL/LTL model-checking on some system

I apologies if my title is vague, I'm trying to apply CTL/LTL model-checking on some system written in java, however, I still don't understand how to reach a result using either of the approaches ...
3
votes
1answer
57 views

Process graphs and finding infinite processes

I am reading on concurrent processes and algorithms which find infinite processes by searching the process graph recursively. Most of the material I have found is not for beginners. I am looking for ...
3
votes
2answers
93 views

Mutual exclusion for n processes

I want to implement mutual exclusion for $n$ processes. Critical section code: ...
3
votes
1answer
337 views

What is a linearization point?

With respect concurrent programming, what is a linearization point? They seem to occur at a compare-and-swap instruction apparently. The best definition I could find is here. All function calls ...
3
votes
2answers
669 views

Banker's Algorithm and deadlocks

So we have the following table of processes , where A, B and $\Gamma$ are the resources. Here is a pic that i drew with the processes and the resources. So the exact question is this: Using ...
4
votes
1answer
214 views

Batch processing in increase-key function using binary heap

Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one ...
16
votes
1answer
498 views

Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
6
votes
1answer
160 views

Variation of the dining philosophers: is the standard solution still valid?

I have a problem that is almost equal to the standard one of the dining philosophers, but has a quirk: while a philosopher thinks, he still holds the fork on his left. If after the period of thinking ...
5
votes
1answer
133 views

Compare-and-Swap in an RDBMS for custom locks and lock escalation

I'm applying the Compare-and-Swap technique to a SQL database to create custom row-level locking in my dataset, allowing for safe READ UNCOMMITTED isolation at the database level. The Resource table ...
5
votes
1answer
334 views

What is the purpose of M:N (Hybrid) threading?

In other words, what advantages does Hybrid threading have over 1:1 (kernel only) and N:1 (user only) threading? This is a follow-up to What is the difference between user-level threads and ...
12
votes
1answer
13k views

What is the difference between user-level threads and kernel-level threads?

After reading several sources I'm still confused about user- and kernel-level threads. In particular: Threads can exist at both the user level and the kernel level What is the difference ...
11
votes
3answers
330 views

Similarities and differences in major process algebras

To my knowledge, there are three major process algebras that have inspired a vast range of research into formal models of concurrency. These are: CCS and $\pi$-calculus both by Robin Milner CSP by ...
8
votes
2answers
151 views

CCS process for a drink dispenser with two different prices

A drink dispenser requires the user to insert a coin ($\bar c$), then press one of three buttons: $\bar d_{\text{tea}}$ requests a cup of tea $e_{\text{tea}}$, ditto for coffee, and $\bar r$ requests ...
4
votes
1answer
150 views

termination of two concurrent threads with shared variables

We're in a shared memory concurrency model where all reads and writes to integer variables are atomic. do: $S_1$ ...
6
votes
2answers
370 views

Does Peterson's 2-process mutual exclusion algorithm account for dying processes?

I think that in Peterson's algorithm for mutual exclusion, if the process first to enter the critical section were to die or be cancelled, the other process would loop forever, waiting to enter the ...
4
votes
1answer
47 views

Which instruction yields atomicity in this expression that makes the result 2?

I am reading about atomicity and came across the following scenario ...
5
votes
1answer
163 views

Reflection on Concurrency

Reflection is a common mechanism for accessing and changing the structure of a program at run-time, found in many dynamic programming languages such as Smalltalk, Ruby and Python, and in impoverished ...