Questions tagged [concurrency]

Questiont about issues of concurrency such as synchronization and deadlocks.

Filter by
Sorted by
Tagged with
3
votes
1answer
52 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
2answers
329 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 ...
31
votes
2answers
4k 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 ...
10
votes
1answer
242 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 ...
1
vote
1answer
957 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 ...
2
votes
1answer
2k 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 ...
1
vote
1answer
284 views

Multithreaded access to a persistent linked list data structure

I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from ...
0
votes
1answer
287 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
83 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 ...
6
votes
2answers
707 views

Mutual exclusion for n processes

I want to implement mutual exclusion for $n$ processes. Critical section code: ...
6
votes
1answer
5k 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
3k 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 banker's ...
4
votes
1answer
457 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 ...
20
votes
1answer
1k 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
755 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
641 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 ...
13
votes
1answer
5k 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 kernel-...
33
votes
2answers
45k 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 between ...
23
votes
3answers
2k 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 ...
11
votes
2answers
235 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 ...
5
votes
1answer
294 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$ ...
9
votes
2answers
1k 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 ...
5
votes
1answer
64 views

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

I am reading about atomicity and came across the following scenario ...
6
votes
1answer
316 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 ...

1 2 3 4 5
6