7
votes
Accepted
Does mutual exclusion hold in this case?
Your friend is correct. In your context, mutual exclusion holds if at most one process is at a critical section at any given time.
You state that you feel that this interpretation is wrong, but you ...
- 279k
7
votes
Accepted
Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)
The paper says
By an easy induction, there exist neighbors $C_0, C_1 \in \mathscr{C}$ such that $D_i = e(C_i)$ is $i$-valent, $i = 0, 1$
Here is a proof:
The set of configurations forms the nodes ...
- 3,390
5
votes
Accepted
What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion?
A semaphore is a counter, that counts the number of processes that have access to a resource. If a resource can service n processes, n is decremented each time a process accesses the resource, and ...
- 249
4
votes
Accepted
What should be the minimum value when the two threads are executed concurrently
Here's a tricky interleaving. R1,R2 denote the independent logical registers used by the threads, while count is the shared ...
- 14.7k
4
votes
Accepted
How can a spinlock progress when it's busy-waiting?
There might be other CPUs in the system, if one is busy waiting, another can be doing something. Furthermore, if the OS uses preemptive scheduling, the thread doing the busy wait might be preempted ...
- 1,181
4
votes
Contrasting Peterson’s and Dekker’s algorithms
In the following paper we give formal models for Peterson’s and Dekker’s algorithms (and some others) and we used model checker to prove their properties. Please, find our results in the table below (...
- 143
4
votes
Reader and Writer mutex
"No_of_Readers" is a shared variable hence, mutex is used to provide mutual exclusion to maintain data consistency.
Consider the statement : No_of_Readers ++;
In high level language it is only one ...
- 858
4
votes
Accepted
Reader and Writer mutex
Lets begin with defining some terms.
Semaphore is one form of software implementation for process synchronization. It's an int value that is used by processes for the purpose of signalling. Only ...
- 311
4
votes
Does mutual exclusion hold in this case?
A mutual exclusion solution should satisfy not only the mutual exclusion property but also the deadlock property. Deadlock occurs when one or more processes are "trying to enter" their critical ...
- 9,641
2
votes
Accepted
Does the process exiting from critical section will always call signal instruction?
Assuming s is a binary semaphore.
If s=0, a V(s) will be successful operation making s=1
If s=1, a V(s) will be successful operation making s=1
If s=0, a P(s) will be unsuccessful operation by ...
- 551
2
votes
How can a spinlock progress when it's busy-waiting?
A spinlock is indeed wasting CPU time while the lock is held by another thread. So why / when would you use a spin lock? You use it when the lock is held for very, very short times.
A "real" lock ...
- 31.6k
2
votes
What is the problem with this Busy Wait solution for two threads?
Your approach works fine providing assignment operations are atomic. But I cannot see any concurrency in your approach. $P_2$ always waits until $P_1$ produces and reaches the upper limit, for example ...
- 9,885
2
votes
Accepted
How are semaphores and test-and-set instructions connected?
Semaphores are an abstract mechanism to control access to a shared resource. Other such mechanisms exist, for example locks and monitors. These are the counterparts of abstract data structures – they ...
- 279k
2
votes
Accepted
What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?
Looks like this modification is correct. Proof is similar to proof of Lamport algorithm and follows.
Consider two processes $P_i$ and $P_k$ who entered critical sections at moments $e$ and $f$, ...
- 256
1
vote
Why is this code for dining philosophers deadlock free?
So apparently my confusion has to do with not realizing what a monitor really is. "The monitor construct ensures that only one process at a time is active
within the monitor" This means that ...
- 225
1
vote
Accepted
PetersonNP, mechanical mutual exclusion proof
I eventually found the solution for the first problem I proposed.
Lemma 10.5.3.2 CAN be proved by induction, but it requires additional lemmata for doing so. I was misled by the note on page 292, ...
- 543
1
vote
Accepted
When does a semaphore issue a wait and when does it issue a signal?
The semaphore doesn't issue those. A semaphore is an object that can be used by processes to coordinate between themselves. Thus, a process will call semSignal or semWait on a shared semaphore. We ...
D.W.♦
- 166k
1
vote
What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?
I believe the purpose is to fulfill the first condition of entering the critical section (site $S_i$ must receive a message from all other sites with timestamp greater than its own request) in case ...
- 131
1
vote
Peterson algorithm for mutual exclusion
The Peterson Algorithm uses only memory read and memory write operations, which are atomic in almost every computer ever built. (All the bits in a word are read or written on the same cycle, and the ...
- 17.8k
1
vote
What is the difference between consensus and mutual exclusion in Distributed Systems?
The mutual exclusion problem makes sense only when processors are scheduled fairly; otherwise, a processor halting in the critical section blocks the whole system. But, in a model with fair scheduling,...
- 166
1
vote
Contrasting Peterson’s and Dekker’s algorithms
Peterson algorithm has a more strict pressure on entering the critical section, where as dekker's algorithm is relatively softer and less aggressive.
To make it more clear, let's check out an example ...
- 133
Only top scored, non community-wiki answers of a minimum length are eligible