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 ...
Yuval Filmus's user avatar
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 ...
jbapple's user avatar
  • 3,340
6 votes
Accepted

Lamport’s fast mutual exclusion algorithm intuition

In what sense are this locks fast/slow? Lamport optimizes for a very specific scenario, as pointed out in the paper: The current belief among operating system designers is that contention for a ...
ComicSansMS's user avatar
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 ...
EL Dendo's user avatar
  • 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 ...
chi's user avatar
  • 14.5k
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 ...
hengxin's user avatar
  • 9,501
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 ...
Amaury Pouly's user avatar
  • 1,181
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 ...
Akash Mahapatra's user avatar
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 ...
Ugnes's user avatar
  • 311
4 votes
Accepted

Software mutexes and consensus number 1

Herlihy's result, indeed the whole paper, is about wait-free synchronization. Corollary 1 states that there is no wait-free two-process consensus protocols using atomic registers. Wait-free is defined ...
Gilles 'SO- stop being evil''s user avatar
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 (...
meolic's user avatar
  • 143
3 votes
Accepted

Confusion in the solution to first readers-writers synchronization

But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer. It's a bit more subtle. The ...
Gilles 'SO- stop being evil''s user avatar
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 ...
gnasher729's user avatar
  • 29.4k
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 ...
fade2black's user avatar
  • 9,817
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 ...
Alwyn Mathew's user avatar
2 votes

Lamport's Bakery algorithm

Let me try to help you with. 1) The problem here is that you are missing the big picture. Lamport's Bakery Algorithm (LBA) is just a deadlock-free algorithm that is used for mutual exclusion, so ...
Shadow Template's user avatar
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 ...
Yuval Filmus's user avatar
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$, ...
yeputons's user avatar
  • 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 ...
user308485's user avatar
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, ...
Chaos's user avatar
  • 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.'s user avatar
  • 158k
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 ...
theasianpianist's user avatar
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 ...
Wandering Logic's user avatar
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,...
nano's user avatar
  • 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 ...
hexpheus's user avatar
  • 133

Only top scored, non community-wiki answers of a minimum length are eligible