24

Your informal descriptions of the algorithms is wonderful. I think in both cases the author was trying to come up with the simplest solution they could think of that guaranteed both mutual exclusion and deadlock freedom. Neither algorithm is starvation free or fair.[ed: as pointed out in the comments, Peterson's algorithm is starvation free and fair]. ...


13

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 I know of, called "Dekker's solution", was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., Programming Languages: NATO ...


8

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" keyword). However the semaphore is considered a "lower level" entity than the monitor for the following reasons & differences: Both Monitors and Semaphores are used ...


6

Answer: none. That's not what those sections of Herlihy and Shavit's The Art of Multiprocessor Programming are about. In the chapters on mutual exclusion Herlihy and Shavit are not giving you alternatives to the pthread library, they are showing you how it is implement the equivalent of the pthread library. Chapter 2 of Herlihy and Shavit is titled "...


6

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 critical section is rare in a well-designed system; most of the time, a process will be able to enter without having to wait. The reasoning goes like this: ...


6

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 have not been able to prove your intuition. You cannot prove a definition! What you are really saying is that the concept of mutual exclusion is vacuous if no ...


5

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 find a solution for a problem with a monitor where originally a semaphore was used and vice versa. Well, we already knew that, so why would you use a monitor ...


5

From my understanding of the 2-processor, if you want to do the same thing you would delete the statement (I truly dont know why you had it. There could be something interesting behind this statement of yours). i = turn and instead, let each of the $n$ processors have an id from $\{1, \dots, n\}$. Then, you would let the processors go in sequence to the ...


5

Atomicity and mutual exclusion are different concepts that are related in that either can be used to implement the other. The important property of mutexes and semaphores is not so much that they are atomic as they guarantee that only one process can get past a particular point at a time. Atomic read-modify-write hardware primitives like test_and_set() and ...


5

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 increments it when the process no longer needs the resource. When n reaches zero, the access of the resource is denied. A real life example will make things ...


4

If the number of threads is less than the number of values that you can hold in a memory location, then you can implement a non-overflowing test-and-test-and-set operation with atomic-fetch-and-decrement. So, for example, if you have 32-bit integers and less than 4 billion threads the following should work: initialize: x = 0 acquireLock: repeat: ...


4

Resources that can only be used by a single process at a time are usually protected by a lock. If the process that currently holds the lock attempts to acquire it a second time, what happens depends on the type of lock. If the lock is reentrant, then it can be acquired multiple times by the same process. The process will need to call the release function as ...


4

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 informally at the beginning of the introduction, and defined formally in the automata model in §2.3. Dekker's algorithm is not wait-free. The busy-wait loop ...


4

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 three atomic operations: initialize, increment and decrement, can be performed. A binary semaphore is restricted type of semaphore which only takes three values,...


4

"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 statement but in machine level it is a combination of more than one statements like shown below: ( Machine languages are architecture dependent so please do not ...


4

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 sections, but no process ever does. See Lamport@JACM'86; Page 6. Although the algorithm you describe trivially satisfies the mutual exclusion property (and the ...


4

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 of a multidigraph in which the edges are labelled by events. $\mathscr{C}$ is the set of nodes reachable in any number of steps from $C$ while not following ...


4

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 and another thread will do something and release the lock for example. The signal might also come from an interrupt handler, for example if the thread is waiting ...


4

Here's a tricky interleaving. R1,R2 denote the independent logical registers used by the threads, while count is the shared variable in memory. Thread 1 starts its first iteration, performing only a read. count=0, R1=0, R2=? Thread 2 performs 99 iterations. count=99, R1=0, R2=99 Thread 1 completes its first iteration (increment and write). count=1, R1=1, R2=...


3

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 second reader is not given priority. Rather, the reader is not blocked by the first reader. This means that if the first reader takes sufficiently long, then the ...


3

You simply need to place a total order on the accounts and always lock the accounts in that order. You define a < operator on Accounts and then change the beginning like this: mutex lock1 = getlock(from) mutex lock2 = getlock(to) if (from < to) mutex lockSwap = lock1 lock1 = lock2 lock2 = lockSwap It doesn't matter what order you choose, ...


3

Mutex For the mutex I'm going to propose a modification of the MCS spinlock that uses your sleep/wake primitives to block instead of spin while waiting to acquire the mutex. The MCS lock was introduced in Mellor-Crummey, John M; Scott, Michael L: Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors, ACM Trans. on Comp. Sys. (TOCS), 9(...


3

If you have a consensus mechanism, then you can achieve consensus on who owns a critical section, and thus solve mutual exclusion. This is exactly what happens in, say, single-master distributed database systems when they are doing leader election to decide which machine will accept writes (this has to be mutually exclusive). However, different algorithms ...


3

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 (columns "Deadlock" and "Divergent" refer to our models, "ME" = TRUE means that the algorithm is correct, "Overtaking" = TRUE means that it is fair). R. Meolic, ...


2

Implementations of software primitives like mutexes and semaphores employ atomic hardware primitives such as test_and_wait() or compare_and_set(), and as a result they behave in an atomic fashion. Usually these software primitives are more powerful and easier to use than the hardware primitives, which is why you would rather use them. This is an example of ...


2

For the first task think about what might happen, if the loop in Overflow is not run for each car. For the second task, look at the following things: How is the opening and closing of bars linked to arriving cars? Does the overflow bar really open at the $100-\max$-th car? The specification requests a specific order of opening and closing the bars. Is this ...


2

Low-level atomicity primitives At the level of the interface between hardware and software, atomicity is typically provided by an operation that combines a read and a write operation. Here are two common examples: test-and-set: read the old value of a memory location, and write a new value. This is an atomic operation: the read is always executed together ...


2

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 acknowledged that side A took the mutex. Since we know nothing about the shared memory, we cannot assume that write to two seperate regions will be seen in order (some ...


2

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 retaining s=0 If s=1, a P(s) will be successful operation by making s=0 s=0 V(s) < Critical Section > P(s) Let process ${p_1,p_2,p_3,.,p_k,.,p_n}$ are ...


2

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 until it completely fills the buffer. Then it triggers $P_2$ to consume and waits until $P_2$ consumes all items, for example empties the buffer. So the ...


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