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

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


3

If an operation X is atomic, that means that anyone observing the operation will see it either as not yet started, or as completed, and not in any state that is partially completed. That's it. Obviously if you write code to perform an operation X, and other code can see it half performed, or interfere with it, then your implementation of the operation X is ...


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


2

I'm not sure I know of a simple, formal, abstract definition of "atomic" for a programming language. I know of many different ones at various levels of abstraction and with regards to various topics. I also know some that seem fairly abstract but have fairly sophisticated prerequisites (e.g. presheaf models of concurrency). Part of the problem is that there ...


1

These are two distinct phenomena. Contention refers to the fact that when thread $A$ has accessed a resource $B$ needs to wait until $A$ frees it. Race refers to the fact when both threads $A$ and $B$ want to secure access to a resource. The fastest will secure it and thus lead to contention.


1

The overall structure of the processes is modelled to be like: while(TRUE) { /** get exclusive access */ /* critical section is here */ /** release exclusive access */ /* remainder, i.e., non-critical section */ } You are right, the remainder is outside of the critical section. A real process alternates between critical section/remainder. None ...


1

Computations on general-purpose registers ((a), (b), (d)) doesn't require any privileges. Input/output requires privileges, to access a peripheral or to communicate with the part of the system that manages files. So (c) does generally require going to kernel mode. It's possible for some printf calls to remain entirely within the calling process, for example ...


1

I'm late to the party but I suppose I can offer my intuition on this. I think of it as a race between threads. The race consists the number of laps = #threads-1. The idea is after each lap, 1 thread is left behind, so at the end of the race, only 1 thread is guaranteed to come out on top. From the perspective of each thread, it looks like below (the comments)...


1

The way the N-process Peterson's algorithm works is slightly different than how the 2-process version is presented above. We can reason about the N-process version a little more like this: When a process wants to start running (i.e.: executes lock()), it imagines that it's joining an imaginary queue of processes. It doesn't know exactly how many processes ...


1

Little late anyway...First of all 8 do exchange (&key, &lock) 9 while (key != 0); //if lock wasn’t free The exchange instruction has to be within the while loop otherwise the value of the key will never change. Coming to the question of: 1. Progress 2. Bounded waiting This solution guarantees progress, as some thread will ...


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