Questions tagged [concurrency]

Questiont about issues of concurrency such as synchronization and deadlocks.

73 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
252 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 ...
7
votes
2answers
406 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 ...
5
votes
0answers
109 views

Model Join calculus as hypergraphs

I'm not sure if this is the right site to ask, but I couldn't find a another one. Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For ...
4
votes
1answer
133 views

Task scheduling algorithm that limits concurrency

My prof introduced us an algorithm with semaphores that was used to solve the "dining philosophers" problem. The algo is ok, apart from that it limits concurrency. What does mean that it "limits ...
4
votes
0answers
337 views

Classic Problems on Process Synchronization

I have been studying Process Synchronization and inter-process communication in Operating Systems Engineering and have come across multiple problems like "Sleeping Barbers", "Producer Consumers", "...
4
votes
0answers
69 views

Deadlock free process calculi

So when programming with locks as a synchronization primitives you can ensure no deadlock by ensuring that an ordering exists on the locks and that all acquires of the locks happen in that order (...
4
votes
0answers
68 views

Why use coroutines instead of mutable objects?

What scenarios would cause coroutines to be a better (i.e. more robust, easier to modify) answer than simple mutable objects? For example, in Fluent Python, the following running average example is ...
4
votes
0answers
262 views

Mutex implementation on top of a preemptive scheduler that does not guarantee liveness

I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of a microkernel with ...
4
votes
0answers
100 views

Concurrent Programming Bar Problem

I have been posed a question by my lecturer and I'm trying to figure the right way to go about it. They want me to ensure mutual exclusion for n processes. The code provided is as follows: ...
4
votes
0answers
280 views

Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my "...
4
votes
0answers
62 views

Extending the causal memory model to wide-area distributed storage systems

In the seminal paper "Causal memory: definitions, implementations, and programming", distributed causal memory is defined to ensures that all the processes in a system agree on the relative ordering ...
3
votes
1answer
74 views

How to use Parallel Semaphores for Dining Philosophers Problem

I am in an intro to OS class and we are learning about mutual exclusion and semaphores. One classical problem we learned about was the dining philosophers problem. My professor touched on the ...
3
votes
0answers
77 views

Why is the Black-White Bakery Algorithm considered bounded?

As stated in Lamport's papers for the bakery algorithm he states that the ticket numbers are unbounded specifically The range of values of number is unbounded. and Fortunately, practical ...
3
votes
0answers
89 views

Concurrent Element-wise Reduction Algorithm (multi-threaded) (C++)

I'd like to implement a high-performance implementation of a multi-threaded reduction, element-wise, on x86 CPUs. Without loss of generality, assume the reduction operation is a sum of integers (so, ...
3
votes
0answers
219 views

Is the Bakery Lock fair?

Consider this implementation of the Bakery Lock: ...
3
votes
0answers
84 views

Wikipedia on MVCC

I read about Multiversion Concurrency Control in Wikipedia. They say that every piece of data in DB has a Read Time Stamp (RTS) and If transaction Ti wants to Write to object P, and there is also ...
3
votes
0answers
40 views

Original proof that orders eliminate deadlocks?

A well-known approach to eliminate the possibility of a deadlock when accessing exclusive ressources is enforcing a partial (or total) order in which the ressources may be requested. Which ...
3
votes
0answers
639 views

How to generate globally unique timestamps for transactions in distributed database systems?

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following,...
3
votes
0answers
1k 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 ...
2
votes
0answers
24 views

Algorithm for locking based on a shared resource (dictionary)

I am working with a shared resource with the following specifications acts as a dictionary (values can be obtained with key name: dictionary['key']) does not have ...
2
votes
0answers
31 views

Does this state certify to be called as a deadlock?

I came across following problem: Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others ...
2
votes
0answers
245 views

how to find the depth of a concurrency bug

How to find the depth of a concurrency bug The below program runs on two separate threads and shares the variable x. Variables t1 and t2 are local to their threads. The program has a concurrency bug ...
2
votes
0answers
60 views

Select/Barrier statements in $\pi$-Calculus denotational semantics

A select statement waits on $n$ channels until channel $0$ or $1$ or ... or $n-1$ have data. A barrier lock waits on $n$ ...
2
votes
0answers
40 views

Through how many levels must cache writeback propagate?

Suppose that my multicore computer system has the diagrammed memory caches. ...
2
votes
0answers
135 views

Mesa Semantics without Starvation?

When a process inside a monitor with Mesa semantics finishes, another process can acquire the monitor. Now there can be starvation here when there is a thread with a lower priority. Are there ...
2
votes
0answers
41 views

How can I talk about priority inversion if it's impossible to specify priority?

In the paper: Leslie Lamport: What It Means for a Concurrent Program to Satisfy a Specification: Why No One Has Specified Priority; ACM Symp Principles of Programming Languages, (POPL-12):78-83, ...
2
votes
0answers
94 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 ...
2
votes
0answers
46 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 ...
1
vote
0answers
5 views

Is there a review of lock free priority queues for single consumer multiple producer?

Background The task I have at hand is to write an event scheduler. From what I understood, it is basically a priority queue which needs to support concurrent insertions and single threaded delete ...
1
vote
0answers
37 views

Dekker's Algorithm spin on intent instead of turn

For Dekker's algorithm given below (from Wikipedia), why is it that we wait for the turn to change, instead of waiting for p1 to set it's flag to false? It seems to me that it would be safer (or more ...
1
vote
0answers
27 views

Calculus for Communicating Systems vs. Calculus of Communicating Systems

Robin Milner uses both terms: Calculus for Communicating Systems and Calculus of Communicating Systems and, AFAIK, writes CCS for both. Is there any difference between the two? Is there a difference ...
1
vote
0answers
27 views
1
vote
0answers
57 views

Unconditionally fair, weakly fair, and strongly fair scheduling

I am trying to understand the difference between weakly fair and strongly fair scheduling. For example, what scheduling policy would ensure that a process delayed at its first await statement will ...
1
vote
0answers
47 views

Bakery algorithm: How does it work with single-writer safe registers?

I'm trying to understand the bakery algorithm and read that the Bakery algorithm uses single-writer safe registers. But I am not able to understand the correctness of bakery algorithm with safe ...
1
vote
0answers
44 views

n thread consensus queues

Its generally agreed that wait free queues have a consensus number of 2. But what about this following code for a consensus protocol for a queue. How is it that this does not go against the idea above?...
1
vote
0answers
112 views

How to prove that an algorithm has no deadlock

I need to mathematically prove that this algorithm is deadlock-free: ...
1
vote
0answers
26 views

Comparing wait-signal alternatives for synchronizing two piece of programs

I came across following problem: A certain computation generates two arrays a and b such that ...
1
vote
0answers
58 views
1
vote
0answers
48 views

Prove that set of operations form a commutative Monoid

this is my first post on this exchange. I am looking for some help with defining a proof that a set of operations I have designed forms a commutative monoid. (Disclaimer: I am not sure that I have ...
1
vote
0answers
109 views

How can I implement locking a range of values in a sorted sequence?

I am trying to write a general purpose locking algorithm which allows me to lock a range of contiguous values in a sorted array. To start with, these could be exclusive locks - so two concurrent locks ...
1
vote
0answers
99 views

Do we really need a mutex in this case?

Wikipedia's solution for multi Producer-Consumer problem uses both mutexes and semaphores. ...
1
vote
1answer
550 views

What fraction of all combinations is guaranteed to be deadlock free?

I found this question in the exercise of Tanenbaum (operating systems): Two processes, $A$ and $B$,each need three records $1, 2, \text{ and } 3$ in a database. If $A$ asks for them in the order $...
1
vote
0answers
65 views

How to Optimise Each Multithreading Technique? (Cooperative/Preemptive/Simultaneous)

I am currently in the process of writing an IB Extended Essay on the efficacy of multithreading on increasing the performance of applications. So far, I have been able to deduce that there are three ...
1
vote
0answers
263 views

interval tree clocks

I understand how vector clocks detect concurrent events, but they are designed for a fixed number of nodes, so we can't easily add and remove nodes. And with interval tree clock we can. Could you ...
1
vote
0answers
140 views

bakery algorithm, switching up the condition

I'm currently studying the Bakery Algorithm. I understand it for what it is but now I want to switch it up a bit. If we changed the < in the 2nd ...
1
vote
0answers
65 views

Lamport's distributed mutual exclusion: wait-chain order clock

Regarding Lamport's mutual exclusion... Where messages are exchanged in the following sequence between nodes S, G1, and G2. G1 and G2 are the members of the group. (for this, lets just assume that ...
1
vote
0answers
122 views

Is Dekker's algorithm not k-bounded for any finite k?

Consider this version of the algorithm, for only 2 processes, 0 and 1: ...
1
vote
0answers
27 views

Communicating Sequential Processes: SQUASH

In C.A.R Hoare's Communicating Sequential Processes (1978), he presents the SQUASH problem: Replace every pair of consecutive asterisks "**" by an upward arrow "↑". Assume that the final character ...
1
vote
0answers
111 views

Behaviour of Regular Registers for Multiple Writer Case ( in context of Safe, Regular and Atomic Registers)

From the link below I understand the behaviour of different kinds of registers. However that raises few more queries in my mind. https://stackoverflow.com/questions/8871633/whats-the-difference-...
1
vote
0answers
315 views

Matrix Vector Multiplication Parallel

CLRS book has the following algorithm for parallel for matrix vector multiplication My problem is, can't we use a simple approach like this, ...