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,290
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
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.4k
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,461
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

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
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
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
Accepted

Mutex-/semaphore-/locking-algorithm using atomic reads/writes with data-propagation delays

If you don't have access to atomic primitives like CAS, you're going to have to depend on voluntary synchronization between the two halves. This means side A cannot proceed until side B has ...
Cort Ammon's user avatar
  • 3,243
2 votes

Mutual exclusion algorithm using only atomic reads and writes for unknown number of processes and robust to process abortion

Since I don't really care about fairness or starvation (it doesn't matter which process enters the critical section), I don't really need to use an algorithm as complex as Szymanski's (also pointed ...
Markus A.'s user avatar
  • 223
2 votes

Why would you use a monitor instead of a semaphore?

Take a peek at e.g. "The little book of sempaphores" by Allen B. Downey. it states and solves lots of synchronization problems. Check particularly the botched solutions, and you will see that ...
vonbrand's user avatar
  • 13.9k
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

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,727
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
  • 27.7k
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
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

How are waits in semaphores made atomic in nature?

A possible implementation is to have the semaphore counter protected by a spinlock, in order to avoid concurrent accesses (a spinlock manages a lightweight critical section). When the value is found ...
Yves Daoust's user avatar
  • 10.3k
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
  • 433
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
  • 154k
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

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
1 vote

Help understanding this algorithm that's supposed to solve the critical section problem through mutual exclusion

Assumptions Consider a Petri Net model of the algorithm, based on the pseudo code (“Help”, 2015) and the following assumptions: Main executes first. process1; in Main is actually a call to schedule ...
John Frederick Chionglo's user avatar
1 vote

Help understanding this algorithm that's supposed to solve the critical section problem through mutual exclusion

Note that the while bodies are empty, i.e., if the condition is false, they just fall through to the next line. Horrible, horrible code; extremely restrictive (...
vonbrand's user avatar
  • 13.9k

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