Tag Info

Whats exact definition of 'atomicity' in programming?

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. ...
• 31.4k
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 ...
• 164k

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

Understanding N process Peterson's algorithm

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 ...
• 2,146

Whats exact definition of 'atomicity' in programming?

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. ...
• 12.1k
Accepted

Race condition, my doubt on Peterson's algorithm vs. C

When it is compiled, the while clause will generate multiple instructions which it seems to me can lead to a race condition in a pre-emptive scheduling model. This is the technical beauty of Peterson'...
• 39.1k

Race condition, my doubt on Peterson's algorithm vs. C

For starters, one could model this in one's favourite model-checking language such as Promela and explore the model with spin. With the basic atomic awaits, the code could look like this ...
• 917

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 ...
• 9,877
1 vote
Accepted

I've recently been reasoning about this algorithm as well. I think its both. You pointed out the starvation case. Here is the author's definition of deadlock as given on page 24: Freedom from ...
1 vote
Accepted

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 \$...
• 659
1 vote

Does Dekkers solutions to critical section problem ensure progress?

The overall structure of the processes is modelled to be like: ...
• 14.1k
1 vote
Accepted

Is OS mode required for accessing general purpose registers

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

Deadlock vs "Progress" requirement of the solution to the critical section problem

and this selection cannot be postponed indefinitely In case of deadlock, deciding which process will enter next will be postponed indefinitely. So progress won't happen.
• 117
1 vote

Understanding N process Peterson's algorithm

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

Bounded waiting and progress requirements of critical section problem solution based on exchange instruction

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

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