Questions tagged [mutual-exclusion]
Questions about the concurrency-control requirement of ensuring that no two processes are simultaneously in a critical section (a period when the process is accessing a shared resource). Failing to achieve mutual exclusion leads to the problem of data races.
58 questions
1
vote
0
answers
44
views
Order of releasing the semaphores
I was studying the dining philosopher problem (See problem description) and its solution using semaphores, and I came across this :
...
- 11
0
votes
1
answer
276
views
How are waits in semaphores made atomic in nature?
I was going through the book Operating Systems by Galvin. First they explain Semaphores acting like a mutex.
While talking about semaphores as mutex, they mention that the wait operation of semaphores ...
- 115
0
votes
2
answers
232
views
What's the standard technique to test if the algorithm satisfies mutual exclusion, progress and bounded waiting or not?
Sorry if this is a stupid question. But it really intrigued me. Same resources at different algorithms are telling different ways to test these stuffs.
Here's an algorithm and how I'd test for its 3 ...
- 105
1
vote
0
answers
104
views
For what example would Maekawa's algorithm allow out of timestamp order access to the critical section
For what example would Maekawa's algorithm allow out of timestamp order access to the critical section. It is mentioned that ordering is not satisfied in Maekawa's algorithm. But in what scenario ...
- 11
0
votes
1
answer
126
views
2
votes
0
answers
25
views
Minimum number of registers for mutual exclusion
I was reading distributed algorithms (by Nancy lynch) and there is a part that I would kindly like to get a simpler explanation for.
I know the book mentioned no algorithm can solve mutual exclusion ...
- 320
3
votes
1
answer
120
views
PetersonNP, mechanical mutual exclusion proof
Good day everyone,
I'm currently trying to carry out the PetersonNP (a.k.a. FilterLock) correctness proof (mutual exclusion).
I've found several proof sketches on concurrency books but I'm interested ...
- 543
1
vote
1
answer
1k
views
How are semaphores and test-and-set instructions connected?
Cheers, so my textbook explains these parts very poorly, so I would gladly take any advice! I am confused between the test-and-set instructions, which per my book is a very common CPU instruction set, ...
1
vote
0
answers
137
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 ...
- 11
1
vote
0
answers
135
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 ...
- 113
0
votes
1
answer
291
views
When does a semaphore issue a wait and when does it issue a signal?
In my textbook, Operating Systems: Internals and Design Principles (9th Edition) by William Stallings in chapter 5, it explains how semaphores work:
The fundamental principle is this: Two or more ...
- 155
1
vote
0
answers
27
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,727
5
votes
1
answer
1k
views
What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?
Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle).
It ...
- 256
3
votes
1
answer
1k
views
What should be the minimum value when the two threads are executed concurrently
int count=0;
void *thfunc()
{
int ctr=0;
for(ctr=0;ctr<100;ctr++)
count++;
}
If *thfunc() is executed by two threads concurrently in a uniprocessor ...
- 323
1
vote
0
answers
151
views
Do we really need a mutex in this case?
Wikipedia's solution for multi Producer-Consumer problem uses both mutexes and semaphores.
...
3
votes
1
answer
925
views
What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?
After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages ...
- 171
2
votes
0
answers
125
views
Starvation algorithm in operating system
Is there an algorithm for mutual exclusion with shared flag variables, as the Peterson's one, that doesn't prevent the starvation ?
- 341
2
votes
1
answer
532
views
Peterson algorithm for mutual exclusion
In the Peterson Algorithm for mutual exclusion an implicit assumption is that the operations with the shared global variables happen atomically.
To me, this is not a superficial assumption , cause it'...
- 341
0
votes
0
answers
150
views
a problem with Suzuki-Kasami mutex algorithm
I have some sort of a misunderstanding regarding the Suzuki-Kasami distributed mutex algorithm. I am writing my question here because I failed on gaining access to the original paper.
I will call ...
- 752
1
vote
0
answers
72
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 ...
- 111
1
vote
0
answers
57
views
1
vote
0
answers
126
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:
...
- 11
1
vote
3
answers
2k
views
How can a spinlock progress when it's busy-waiting?
I read that in spinlock, process keeps on waiting for the lock continuously in a loop until it receives signal(lock) or ...
- 993
3
votes
2
answers
1k
views
What is the problem with this Busy Wait solution for two threads?
We have two processes. One process produces F and the other process consumes F
Initialization:
Consuming = false
Produced = false
F = EMPTY
The first thread (...
- 133
1
vote
0
answers
455
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 ...
- 229
0
votes
1
answer
491
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 ...
- 863
4
votes
0
answers
372
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", "...
- 41
6
votes
1
answer
540
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 ...
- 265
4
votes
2
answers
537
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 $...
- 43
1
vote
1
answer
200
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 ...
- 348
2
votes
2
answers
2k
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 ...
- 125
6
votes
1
answer
423
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. ...
- 379
5
votes
1
answer
1k
views
Lamport’s fast mutual exclusion algorithm intuition
Here's Lamport’s fast mutual exclusion algorithm:
...
- 215
4
votes
0
answers
78
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,800
4
votes
2
answers
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 ...
- 41
2
votes
0
answers
389
views
Lamport's Bakery algorithm with other > relation
i'm reading an old exam and one question was:
Which property of the Bakery algorithm is violated with the following change?
...
- 149
1
vote
2
answers
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 ...
- 641
3
votes
0
answers
1k
views
Proof of Manna-Pnueli algorithm for mutual exclusion being incorrect
Suppose we have the Manna-Pnueli algorithm for mutual exclusion:
I was trying to find a sequence that violates mutual exclusion and I came up with this:
...
- 131
2
votes
2
answers
203
views
Help understanding this algorithm that's supposed to solve the critical section problem through mutual exclusion
Our professor gave us the following algorithm that's supposed to solve the critical section problem. I'm guessing the code is just pseudocode so I'm not trying to focus on the strange syntax and just ...
- 393
1
vote
1
answer
216
views
Why do we need $k \geq n$ in Dijkstra's token ring self-stabilizing system?
Let's say I have a ring with four nodes $n=\{0;1;2;3\}$ and three possible states $k=\{0;1;2\}$. A transient failure happens and the system ends up in an illegal state.
I know from the restriction ($...
- 111
2
votes
1
answer
201
views
Mutex-/semaphore-/locking-algorithm using atomic reads/writes with data-propagation delays
Is there a mutual exclusion or semaphore or locking algorithm that only relies on atomic reads and atomic writes of shared memory and can tolerate a delay in propagation of the written data between ...
- 223
5
votes
1
answer
615
views
Mutual exclusion algorithm using only atomic reads and writes for unknown number of processes and robust to process abortion
I am trying to come up with a mutual exclusion algorithm that is based only on atomic reads and atomic writes of shared memory (i.e. no compare-and-swap or similar).
Apart from mutual exclusion and ...
- 223
11
votes
3
answers
8k
views
Why would you use a monitor instead of a semaphore?
I am currently attending the concurrent programming course in my university and we recently started talking about the concept of a monitor. While I understand the necessity of mutual exclusion, I do ...
- 316
1
vote
1
answer
451
views
Deadlock Solutions: Lock Ordering
This is from a textbook on operating systems. This is not homework, just part of the chapter on deadlocks.
...
- 211
2
votes
1
answer
708
views
Disabeling interrupts to solve critical section issue on multiprocessor system
Assume I have a multicore system and a critical section.
I understand how disableling interrupts on a single core systems solves the critical section problem.
So assume I could disable interrupts on ...
- 239
4
votes
0
answers
319
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 ...
5
votes
1
answer
1k
views
Mutex implementation on top of a minimalistic preemptive scheduler
In this question, 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 ...
8
votes
1
answer
195
views
What is the practical relevance of textbook mutual exclusion algorithms?
There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is ...
- 2,269
0
votes
1
answer
232
views
What happens if the holder of a lock tries to acquire a lock? [closed]
In a system, suppose there is a process and a resource with only one instance.
Let us assume that the process holds the instance and requests the same instance of that resource. Will there be a ...
- 515
4
votes
0
answers
111
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:
...
- 143