26
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, both algorithms are starvation free, and Peterson's ...
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 ...
10
choosing[i] is true while number[i] is being updated to be larger than all the other values in the number array — the new ticket value that the thread is taking. In the body of the for loop, the code first waits for choosing[j] to be false, which indicates that thread number j has chosen its ticket for this round. If thread j goes on executing while thread i ...
answered Nov 8 '14 at 14:20
Gilles 'SO- stop being evil'
38.9k7 gold badges103 silver badges167 bronze badges
10
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 whole time.
So any deadlock must have at least four participating processes. To participate in a deadlock, a process must hold at least one resource. Further,...
8
Sounds like you are reading The Art of Multiprocessor Programming.
"All function calls have a linearization point at some instant between their invocation and their response"
Okay that's fine, they occur somewhere within a function call, but what are they?
Side effects of the functions. http://en.wikipedia.org/wiki/Side_effect_(...
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 ...
8
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 from Deadlock If some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will ...
7
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 thread is generally the one that should run.
However, there's a little-discussed secret of operating system implementation which you should be aware of, which is ...
6
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 objects affects their ability to solve consensus. In particular, although a queue or a stack can solve name-consensus
between two processes, we prove that an ...
6
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
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
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 monitor at a time), and mutual exclusion and priorities don't mix well. Boosting the priority of the thread in the monitor, mitigates (but does not completely solve)...
5
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 instance of vector is monotonic, then it would seem reasonable to assume that the memory location of any previously pushed element will not be subsequently modified, and thus that it is safe to ...
5
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 ...
5
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 the consensus number for test-and-set, 2?. Semaphores allow synchronization between an arbitrary number of processes (assuming no bound on the number of ...
answered Oct 29 '17 at 11:02
Gilles 'SO- stop being evil'
38.9k7 gold badges103 silver badges167 bronze badges
4
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 clocks are used to manage data versioning.
Some of the open source implementations of Dynamo are Riak [2] and Voldemort [3].
[1] G. DeCandia et al.: Dynamo: ...
4
Almost every modern processor has special memory instructions built in specifically to deal with this problem.
For example, many processors have a swap instruction. This atomically swaps a value between a local variable in a thread and a global variable that is shared between threads. (Under the covers the "local variable" will be stored in a machine ...
4
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 be careful never to increment it past 1. The point is that if the values are thus limited, some tricks are possible that speed up the implementation quite a bit,...
4
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 deadlock, this means that none of the philosophers can eat (so each philosopher holds at most one fork, and cannot pick up the other one). Sine you have both ...
4
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 the root. Any modification of the root is only successful if the value below the main I-node did not change.
All reads of the root location are in the actual ...
4
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 can't predict which one in advance", or "the one which tried to acquire the mutex first" (i.e. first-come, first-served).
However, there may be something which ...
4
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 process are ordered).
$e_1,e_2$ are the sending and receiving of some message $m$, correspondingly.
Finally, we take the transitive closure of the above, and this ...
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 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 signal is called when x=1, then the call is just ignored because the queue of blocked processes is empty, and x has already its maximum value. The process that ...
4
'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 unlocks, which process should get the lock next?
4
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 long. Then there is no bound on the amount of time it might take to complete its operation.
Here is another example of how it can fail. Starvation-free means ...
4
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 it only solves "all" our problems if the clock has the additional constraint of a meaningful relationship with real time.
The two best solutions we have are ...
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
You have mentioned the temporal ordering of events, then you may have known about temporal logic [1] such as LTL [2] and CTL [3]. Temporal logic allows you to reason about time and thus temporal ordering of events. For instance (from [1]), one may wish to say that whenever a request is made, access to a resource is eventually granted, but it is never granted ...
Only top voted, non community-wiki answers of a minimum length are eligible
