# Tag Info

Accepted

### Are there hardware lock implementations without test-and-set or swap?

Yes, you can implement mutual exclusion with only memory load and store instructions. There is a long tradition of devising successively simpler solutions to this problem. The earliest version that ...
• 17.3k
Accepted

You should first state the deadlock freedom property and the starvation freedom property more precisely. I use the definition in the Book: The Art of Multiprocessor Programming; Section 2.2. Freedom ...
• 9,209

### Why would you use a monitor instead of a semaphore?

They are nearly interchangeable and one can be built out of the other. It is somewhat language dependent which is implemented/ preferred (eg Java has built-in monitors using "synchronize" ...
• 10.8k
Accepted

### Minimum number of processes for the deadlock?

I agree that no deadlock is possible here. If there are three or fewer processes, there clearly cannot be a deadlock because there are enough resources for every process to just hold two resources the ...
• 80.3k
Accepted

### Bakery algorithm: what is the choosing[] boolean array for?

choosing[i] is true while number[i] is being updated to be larger than all the other values in the ...

### Difference between Lamport timestamps and Vector clocks

Summary: Lamport timestamps and vector clocks are both logical clocks, and both provide a total ordering of events consistent with causality. Vector clocks allow you to determine if any two ...
• 211
Accepted

### Why are most mutex implementations unfair?

Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority ...
• 18.9k

### Implementing wait-free consensus with queues

This paper Some results on the impossibility, universality, and decidability of consensus (by Prasad Jayanti and Sam Toueg, 1992) directly answers your question. We study how initialization of shared ...
• 9,209
Accepted

### Why would you use a monitor instead of a semaphore?

We finally discussed why you would use a monitor instead of a semaphore in the lecture today. It basically comes down to this: The monitor and the semaphore are equally expressive, meaning you can ...
• 296
Accepted

### What does "monotonicity" mean in the context of mutability

The author appears to be using the same (general) concept of "monotonicity" as in pure mathematics. Using the example of a vector, if the size of some particular ...
• 306
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,200
Accepted

### Priority inversion in Hoare and Mesa monitors

Unless you are careful priority inversion is possible in either Hoare type or Mesa type monitors. This is because monitors implement a form of mutual exclusion (only one process can be "in" the ...
• 17.3k

### Are Test and set primitives as powerful as semaphores?

Your hunch is correct, they aren't equivalent. Test-and-set has a consensus number of 2, which means, roughly speaking, that it is only able to efficiently synchronize between 2 processes. See Why is ...

### Difference between Lamport timestamps and Vector clocks

Although similar they have different purposes: version vectors can distinguish whether two operations are concurrent or one is causally dependent on the other; Lamport timestamps enforces total ...
• 51

### generation-compare-and-swap, or GCAS, in CTries

Nice observation. To prevent the scenario that you are describing, the actual implementation in the Scala standard library uses a variant of the software RDCSS instruction when reading or modifying ...
• 140
Accepted

### Provide some help regarding the "Dining Philosophers Problem"?

Righties: will never try to acquire the left fork before they have the right one. Lefties: will never try to acquire the right fork before they have the left one. Deadlock: Assume that you reached ...
• 13.2k
Accepted

### Using a counting semaphore as a binary semaphore

A binary semaphore is just a semaphore whose values are limited to 0 and 1 (locked and unlocked; when locked there can be an unlimited queue of tasks waiting). When using such a semaphore you have to ...
• 13.6k
Accepted

### How are lamport clocks implemented in real world distributed systems?

Amazon's Dynamo [1] is a distributed storage system that uses vector clocks "to capture causality between different versions of the same object". Section 4.4 of the paper describes how exactly Lamport ...
Accepted

### How do locks work?

Almost every modern processor has special memory instructions built in specifically to deal with this problem. For example, many processors have a swap instruction....
• 17.3k

### Two threads are waiting on a mutex. Which one is unblocked?

The short answer is "it depends". If there is truly nothing to distinguish thread B from thread C, then the answer on most scheduler implementations will likely be either "could be B or C, and you ...
• 18.9k

### Vector clocks: Why is it necessary to increment my clock on receiving a message?

Look at the definition of $<_H$. We say that $e_1<_H e_2$ (event 1 happened before event 2) if: $e_1,e_2$ took place in the same process, and $e_1$ happened first (events within the same ...
• 13.2k
Accepted

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 ...
• 309

"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 ...

### Increment and Decrement on binary semaphores when their values are $1$ and $0$ respectively?

A binary semaphore has the wait() and the signal() method. The one which causes a process to stop is the wait() method, while the one that increments the counter x in the semaphore is signal(). If ...
• 581

### Why are most mutex implementations unfair?

'Priority inversion' is one reason that fairness can be undesirable. A low priority process hits the locked mutex and sleeps. Then a higher priority process hits it, and also sleeps. When the mutex ...
Accepted

### Bounded waiting and starvation free in critical section problem

No, starvation-free doesn't imply bounded waiting. For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily ...
• 141k
Accepted

### Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system?

You're right that this is an impossible problem to solve in an asynchronous distributed system, and you're also right that it would solve a lot of problems if we could get a totally ordered clock. But ...
• 201
Accepted

### Lamport logical clock: what does partial mean in the concept of Partial ordering?

The "partial ordering" in the papar means partial order as in standard mathemtics theory. To be more rigorous, the "partial ordering" in that paper, also called "irreflexive parital ordering" in that ...
• 34.1k