Peterson’s Solution and Modern Architecture
Although useful for demonstrating an algorithm, Peterson’s
Solution is not guaranteed to work on modern architectures.
• To improve performance, processors and/or compilers may
reorder operations that have no dependencies
Understanding why it will not work is useful for better
understanding race conditions.
For single-threaded this is ok as the result will always be the
same.
For multithreaded the reordering may produce inconsistent or
unexpected results!
Operating System Concepts – 10th Edition 6.19 Silberschatz, Galvin and Gagne ©2018
Modern Architecture Example
Two threads share the data:
boolean flag = false;
int x = 0;
Thread 1 performs
while (!flag)
;
print x
Thread 2 performs
x = 100;
flag = true
What is the expected output?
100
Operating System Concepts – 10th Edition 6.20 Silberschatz, Galvin and Gagne ©2018
Modern Architecture Example (Cont.)
However, since the variables flag and x are independent
of each other, the instructions:
flag = true;
x = 100;
for Thread 2 may be reordered
If this occurs, the output may be 0!
Operating System Concepts – 10th Edition 6.21 Silberschatz, Galvin and Gagne ©2018
Peterson’s Solution Revisited
The effects of instruction reordering in Peterson’s Solution
This allows both processes to be in their critical section at the same
time!
To ensure that Peterson’s solution will work correctly on modern
computer architecture we must use Memory Barrier.
Operating System Concepts – 10th Edition 6.22 Silberschatz, Galvin and Gagne ©2018
Hardware Support-Memory Barrier
Memory models are the memory guarantees a computer
architecture makes to application programs.
Memory models may be either:
• Strongly ordered – where a memory modification of one
processor is immediately visible to all other processors.
• Weakly ordered – where a memory modification of one
processor may not be immediately visible to all other
processors.
A memory barrier is an instruction that forces any change in
memory to be propagated (made visible) to all other processors.
Operating System Concepts – 10th Edition 6.23 Silberschatz, Galvin and Gagne ©2018
Memory Barrier Instructions
When a memory barrier instruction is performed, the
system ensures that all loads and stores are completed
before any subsequent load or store operations are
performed.
Therefore, even if instructions were reordered, the memory
barrier ensures that the store operations are completed in
memory and visible to other processors before future load
or store operations are performed.
Operating System Concepts – 10th Edition 6.24 Silberschatz, Galvin and Gagne ©2018
Memory Barrier Example
Returning to the example:-
We could add a memory barrier to the following instructions to ensure
Thread 1 outputs 100:
Thread 1 now performs
while (!flag)
memory_barrier();
print x
Thread 2 now performs
x = 100;
memory_barrier();
flag = true
For Thread 1 we are guaranteed that that the value of flag is
loaded before the value of x.
For Thread 2 we ensure that the assignment to x occurs before the
assignment flag.
Operating System Concepts – 10th Edition 6.25 Silberschatz, Galvin and Gagne ©2018
Synchronization Hardware
Many systems provide hardware support for implementing the
critical section code.
Uniprocessors – could disable interrupts
• Currently running code would execute without preemption while
in the critical section
• Generally too inefficient on multiprocessor systems because you
need to send messages to all the processors
Operating systems using this not broadly scalable
Operating System Concepts – 10th Edition 6.26 Silberschatz, Galvin and Gagne ©2018
Hardware Instructions
Special hardware instructions that allow us to either
test-and-modify the content of a word, or to swap the
contents of two words atomically (uninterruptedly.)
• Test-and-Set instruction
• Compare-and-Swap instruction
Operating System Concepts – 10th Edition 6.27 Silberschatz, Galvin and Gagne ©2018
The test_and_set Instruction
Definition
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = true;
return rv:
}
Properties
• Executed atomically
• Returns the original value of passed parameter
• Set the new value of passed parameter to true
Operating System Concepts – 10th Edition 6.28 Silberschatz, Galvin and Gagne ©2018
Solution Using test_and_set()
Shared boolean variable lock, initialized to false
Solution:
do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
Does it solve the critical-section problem?
Operating System Concepts – 10th Edition 6.29 Silberschatz, Galvin and Gagne ©2018
The compare_and_swap Instruction
Definition
int compare_and_swap(int *value, int expected, int new_value)
{
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
Properties
• Executed atomically
• Returns the original value of passed parameter value
• Set the variable value the value of the passed parameter
new_value but only if *value == expected is true. That is, the
swap takes place only under this condition.
Operating System Concepts – 10th Edition 6.30 Silberschatz, Galvin and Gagne ©2018
Solution using compare_and_swap
Shared integer lock initialized to 0;
Solution:
while (true){
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
Does it solve the critical-section problem?
Operating System Concepts – 10th Edition 6.31 Silberschatz, Galvin and Gagne ©2018
Bounded-waiting with test and set
while (true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key == 1)
key = test and set(&lock);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = 0;
else
waiting[j] = false;
/* remainder section */
}
Operating System Concepts – 10th Edition 6.32 Silberschatz, Galvin and Gagne ©2018
Mutex Locks
Previous solutions are complicated and generally inaccessible to
application programmers
OS designers build software tools to solve the critical section problem
Simplest is mutex lock
• Boolean variable indicating if lock is available or not
Protect a critical section by
• First acquire() a lock
• Then release() the lock
Calls to acquire() and release() must be atomic
• Usually implemented via hardware atomic instructions such as
test and set / compare and swap
But this solution requires busy waiting
• This lock therefore called a spinlock
Operating System Concepts – 10th Edition 6.33 Silberschatz, Galvin and Gagne ©2018
Solution to CS Problem Using Mutex Locks
while (true) {
acquire lock
critical section
release lock
remainder section
}
Operating System Concepts – 10th Edition 6.34 Silberschatz, Galvin and Gagne ©2018
Semaphore
Synchronization tool that provides more sophisticated ways
(than Mutex locks) for processes to synchronize their activities.
Semaphore S – integer variable
Can only be accessed via two indivisible (atomic) operations
• wait() and signal()
Originally called P() and V()
Definition of the wait() operation
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
Definition of the signal() operation
signal(S) {
S++;
}
Operating System Concepts – 10th Edition 6.35 Silberschatz, Galvin and Gagne ©2018
Semaphore (Cont.)
Counting semaphore – integer value can range over an unrestricted
domain
Binary semaphore – integer value can range only between 0 and 1
• Same as a mutex lock
Can implement a counting semaphore S as a binary semaphore
With semaphores we can solve various synchronization problems
Operating System Concepts – 10th Edition 6.36 Silberschatz, Galvin and Gagne ©2018
Semaphore Usage Example
Solution to the CS Problem
• Create a semaphore “mutex” initialized to 1
wait(mutex);
CS
signal(mutex);
Consider P1 and P2 that with two statements S1 and S2 and
the requirement that S1 to happen before S2
• Create a semaphore “synch” initialized to 0
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
Operating System Concepts – 10th Edition 6.37 Silberschatz, Galvin and Gagne ©2018
Semaphore Implementation
Must guarantee that no two processes can execute the wait()
and signal() on the same semaphore at the same time
Thus, the implementation becomes the critical section problem
where the wait and signal code are placed in the critical
section
Could now have busy waiting in critical section implementation
• But implementation code is short
• Little busy waiting if critical section rarely occupied
Note that applications may spend lots of time in critical sections
and therefore this is not a good solution
Operating System Concepts – 10th Edition 6.38 Silberschatz, Galvin and Gagne ©2018
Semaphore Implementation with no Busy waiting
With each semaphore there is an associated waiting queue
Each entry in a waiting queue has two data items:
• Value (of type integer)
• Pointer to next record in the list
Two operations:
• block – place the process invoking the operation on the
appropriate waiting queue
• wakeup – remove one of processes in the waiting queue
and place it in the ready queue
Operating System Concepts – 10th Edition 6.39 Silberschatz, Galvin and Gagne ©2018
Implementation with no Busy waiting (Cont.)
wait(semaphore *S) {
S->value--; // Decrease the resource count
if (S->value < 0) { // No available resources
add this process to S->list; // Add this process to the
queue
block(); // sleep until signaled
}
}
signal(semaphore *S) {
S->value++; // Increase the resource count
if (S->value <= 0) { // There are processes waiting
remove a process P from S->list; // Pick a waiting process
wakeup(P); // Resume the waiting process
}
}
Operating System Concepts – 10th Edition 6.40 Silberschatz, Galvin and Gagne ©2018
Liveness
Processes may have to wait indefinitely while trying to acquire a
synchronization tool such as a mutex lock or semaphore.
Waiting indefinitely violates the progress and bounded-waiting criteria
discussed at the beginning of this chapter.
Liveness refers to a set of properties that a system must satisfy to
ensure processes make progress.
Indefinite waiting is an example of a liveness failure.
Operating System Concepts – 10th Edition 6.41 Silberschatz, Galvin and Gagne ©2018
Liveness
Deadlock – two or more processes are waiting indefinitely for an
event that can be caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
... ...
signal(S); signal(Q);
signal(Q); signal(S);
Consider if P0 executes wait(S) and P1 wait(Q). When P0 executes
wait(Q), it must wait until P1 executes signal(Q)
However, P1 is waiting until P0 execute signal(S).
Since these signal() operations will never be executed, P0 and P1 are
deadlocked.
Operating System Concepts – 10th Edition 6.42 Silberschatz, Galvin and Gagne ©2018
Liveness
Other forms:
Starvation – indefinite blocking
• A process may never be removed from the semaphore queue in
which it is suspended
Operating System Concepts – 10th Edition 6.43 Silberschatz, Galvin and Gagne ©2018