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.
59 questions
1 vote
0 answers
28 views
Technique to prove/disprove if an Algorithm satisfies Deadlock Freedom or Mutual Exclusion
Regarding the following question: Let A be an arbitrary correct deadlock-free mutual exclusion algorithm such that its exit code is not wait-free, the number of steps in the exit code of A depends on ...
1 vote
0 answers
73 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
354 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
335 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 ...
- 107
2 votes
1 answer
195 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 ...
- 21
0 votes
1 answer
164 views
2 votes
0 answers
44 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
163 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 ...
- 672
1 vote
1 answer
2k 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
155 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
170 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
325 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
52 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,757
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