Questions tagged [concurrency]

Questiont about issues of concurrency such as synchronization and deadlocks.

Filter by
Sorted by
Tagged with
2
votes
1answer
248 views

Consensus number of memory-to-memory swap

I think that consensus number of mem-to-mem-swap(a,b) operation which atomically swaps the values between shared locations a and b (shared R/W memory) is infinite , but I'm having trouble proving it. ...
1
vote
0answers
107 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
310 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, ...
2
votes
1answer
126 views

Solving consensus for a known number of processes

I was given an object with exactly 2 operations test-and-reset that sets the value of the object to 0 only if it was previously set to 1 and does not return a value ...
3
votes
2answers
233 views

Paxos made simple -- two details

I'm missing two details from Paxos made easy P1. An acceptor must accept the first proposal that it receives. What exactly is the reason for rule P1? What if the rule P2 was different, i.e. Upon ...
1
vote
0answers
394 views

What are the practical use of weak semaphores?

Weak semaphores are often defined as if a process (or thread), say p1, performs a V operation and some other process is waiting on that semaphore, then the first process (i.e. p1) is not ...
0
votes
1answer
309 views

What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion?

So I've got this so far to try and wrap my head around the abstract idea of a semaphore: A semaphore is a variable or abstract datatype (commonly an integer), used to control access to a common ...
1
vote
0answers
58 views

Is a single starved process considered deadlocked?

In regard to the critical section problem, an algorithm that switches between allowing one of two processes, P1 or P2, to complete their critical section would cause starvation for P1 if P2 stayed in ...
4
votes
1answer
1k views

A real life system that faces and solves the dining philosophers problem

I'm looking for an application of the dining philosophers problem. Is there some real life system that faces the concurrency problem of "the dining philosophers problem" and implements a solution? I'...
1
vote
1answer
168 views

How was multiprogramming brought into computer languages

I am going through the book operating system principles by Hansen . Hansen begins the third chapter on concurrent programming by discussing interleaving of the machine instructions of processes being ...
11
votes
3answers
3k views

Why are most mutex implementations unfair?

My understanding is that most popular implementations of a mutex (e.g. std::mutex in C++) do not guarantee fairness -- that is, they do not guarantee that in instances of contention, the lock will be ...
4
votes
0answers
336 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", "...
1
vote
0answers
223 views

Processor consistency and cache coherence

Consider this example from Wikipedia: ...
3
votes
1answer
52 views

One rational interval function and one irrational, will they ever collide?

This question may be a little mathy or hardware-y, so I may have to ask elsewhere. I've recently learned that if a is a positive rational number and b is a positive irrational number, there exists no ...
1
vote
0answers
26 views

Why can't a server provide guaranteed service with only bounded nondeterminsm?

The wikipedia page Actor Model and Process Calculi History, presents the following claim: The semantics [of CSP] provided bounded nondeterminism unlike the Actor model with unbounded nondeterminism....
2
votes
1answer
702 views

When will deadlock occur in this producer-consumer code

I was reading about Producer Consumer problem from Operating Systems by William Stallings where following code was given: ...
6
votes
1answer
394 views

Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

Please bear with my unhelpful typesetting. My question is regarding well known FLP paper Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson While ...
0
votes
1answer
68 views

Deadlock not possible?

System is in safe state if there exists a safe sequence of all processes. Sequence $[P_1, P_2 …P_n]$ is safe, if for each $P_i$ the resources that can still request can be satisfied by $P_i$ ...
3
votes
1answer
895 views

Why deadlock in cigarette smokers problem

"The Little Book of Semaphores" (2nd Ed. by Allen B. Downey, section 4.5.1) as well as Wiki (link) mentioned that a trivial solution (as shown below) to the 'Cigarette smokers problem' will cause a ...
3
votes
2answers
367 views

Does mutual exclusion hold in this case?

I entered into a discussion with a friend on the following question, which asks if mutual exclusion holds: Consider two processes: $s_1$ and $s_2$ are two variables, set equal initially. P1: while $...
5
votes
1answer
66 views

Blocking because of concurrency correctness condition

I am confused about a statement in The Art of Multiprocessor Programming: Theorem 3.6.2: Let inv(m) be an invocation of a total method. If ...
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 ...
0
votes
1answer
31 views

Preventing multiple threads from racing on a queue while not wastefully polling its size

I have a queue with 50 ints in it, and I have 3 threads that want to race at the queue to print the values in it, with a 2 second delay before trying to get the next int. The queue is not thread safe,...
2
votes
1answer
60 views

Does a multi-agent system have to have a synchronous component in order for the agents to cooperate?

During my programming assignments in multi-agent systems, I noticed that it feels impossible to get distributed agents to cooperate without a synchronous component. Let me explain what I mean by these ...
7
votes
3answers
2k views

Write Serialization for Cache Coherence in the presence of Store Buffers

One of the requirements for a coherent memory system is write serialization - "two writes to address X by any two processors are observed in the same order by all processors". I am not sure how this ...
1
vote
1answer
144 views

Does the process exiting from critical section will always call signal instruction?

I have seen many solutions to critical section problems in process synchronization chapter . Many of them first acquire resources , execute critical section and leave . My Question is a process ...
2
votes
2answers
1k views

Reader and Writer mutex

I am looking over the classic Reader and Writer Problem Just to give a quick overview: Many readers can be in CS (as long as no writers are) Only one writer can be in the CS (with no combination of ...
4
votes
1answer
137 views

How does lack of deadlock relate to computability in process calculi?

I'm interested in knowing things about the computability of concurrent programs. If you had a Turing complete language that also let you branch off new programs but had no means of communication ...
6
votes
1answer
352 views

Software mutexes and consensus number 1

There are numerous possibilities to implement a software mutex using only shared memory (e.g. Dekker's algorithm). Recently I've read the following from a paper "Wait-free Synchronization" by M. ...
0
votes
1answer
670 views

Is bounded waiting satisfied in this 2 process solution?

Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes: ...
1
vote
0answers
61 views

Communication senario: A sends to B or B sends to A

Consider processes A and B and the situation where either A will send a message to B or B will send a message to A. Is there a standard algorithm for this scenario that makes sure that exactly one of ...
5
votes
1answer
1k views

Lamport’s fast mutual exclusion algorithm intuition

Here's Lamport’s fast mutual exclusion algorithm: ...
7
votes
2answers
10k views

Understanding N process Peterson's algorithm

The intuitive informal description of two process Peterson's algorithm for process 0 can be given as follows: ...
1
vote
1answer
4k views

Bounded waiting and progress requirements of critical section problem solution based on exchange instruction

Atomic exchange instruction is given as follows: void exchange (int *a, int *b) { int temp; temp = *b; *b = *a; *a = temp; } Now consider the ...
6
votes
1answer
1k views

Is this solution to the dining philosopher's problem entirely valid?

In a question on Stack Overflow, the answer by Patrick Trentin lists the following solution to the dining philosopher's problem: A possible approach for avoiding deadlock without incurring ...
20
votes
6answers
3k views

Why must uncommitted transactions be undone in backwards order?

I have a database log where some transactions win (they are committed before crash) and some lose (not committed yet). We learned in class that the losers' actions have to be undone backwards. Is ...
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 (...
3
votes
2answers
1k views

Is bounded waiting ensured in given version of Dekker's solution for critical section problem?

William Stallings discuss various step by step process in developing Dekker's algorithm in his Operating Systems book. In process, he reaches to following version of algorithm (which is incomplete as ...
0
votes
1answer
60 views

Concurrency: Is it order-independability or interruptibility of tasks?

After researching concurrency I am unable to discern if it is either of these specifically or it encapsulates both? I was also wondering if someone could provide some programming applications/real ...
4
votes
2answers
4k views

Lamport's Bakery algorithm

I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 ...
1
vote
2answers
159 views

What does it mean that a core supports 2 threads?

I understand that a process may have multiple threads, and that a processor may have multiple cores to run processes in parallel. But I can't understand how a core may allow multiple threads, what ...
4
votes
1answer
175 views

What techniques could be used to support thread-local contexts and resources in a language?

I am interested in the subject of thread-local contexts, which is a feature that I use quite often in solutions, but seems to lack first-class support in any languages I have used. Quite often in ...
4
votes
2answers
720 views

How probable is a deadlock in the dining philosophers problem

I created this simulation of the dining philosophers problem, but did not manage to initialize it with four philosophers without running into a deadlock: *Philosophers are represented by black ...
2
votes
1answer
387 views

Exclusive queue problem

There is the exclusive queue problem in The Little Book of Semaphores, which is stated as follows: Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers,...
9
votes
1answer
2k views

Why is quiescent consistency compositional, but sequential consistency is not

I'm having trouble in comparing these two memory consistency models. Essentially for sequential consistency I think of real code like this: ...
1
vote
1answer
2k views

Confusion in the solution to first readers-writers synchronization

I am studying the solution to “First Readers-Writers Problem” from the book Operating System Concepts (9th edition) and it describes: First readers–writers problem, requires that no reader be kept ...
2
votes
1answer
296 views

Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?

Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O_1,...,O_k}$. The modified algorithm ...
5
votes
1answer
4k views

example for weakly fair v.s. strongly fair scheduling in concurrency

I am having difficult time understanding the difference between weakly fair and strongly fair schedulers. Can someone provide an example and explain how they are different? for reference, here are ...
-3
votes
1answer
81 views

Which process comes first?

Let's say we have 3 processes: Process 1 service time 6 arrival time 0 Process 2 service time 2 arrival time 1 Process 3 service time 5 arrival time 3 We know that: after 1 time, process 2 will ...
2
votes
3answers
105 views

How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?

A semaphore is a variable that, apart from initialization is accessed through only two standard atomic operations wait(s) and signal(s). ...