Hardware Support for
Synchronization
2024-10-9
2024-10-11
2024-10-15
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!
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?
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!
• Alternatively, the processor may also reorder the statements issued by
Thread 1 and load the variable x before loading the value of flag. Output of
x is 0 for Thread 1, even if Thread 2 is not reordered!
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.
P0 P1
do { do {
turn = 1; turn = 0;
flag[i] = true; flag[j] = true;
while (flag[1] && turn = = 1); while (flag[0] && turn = = 0);
critical section critical section
flag[i] = false; flag[j] = false;
remainder section remainder section
} while (true); } while (true);
t1 t2 t3 t4 time
Synchronization Hardware
• Many systems provide hardware support for implementing the critical
section code.
• Uniprocessors – could disable interrupts
• Currently running code would execute without preemption
• Generally too inefficient on multiprocessor systems
• Operating systems using this not broadly scalable
• Three forms of hardware support:
1. Memory barriers
2. Hardware instructions
3. Atomic variables
Memory Barrier
• How a computer architecture determines what memory guarantees it
will provide to an application program is known as its memory model
• 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.
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.
Memory Barrier Example
• Returning to our earlier 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.
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
test_and_set Instruction
Definition:
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv:
}
[Link] atomically
[Link], if two test and set() instructions are executed simultaneously (each
on a different core), they will be executed sequentially in some arbitrary
order
[Link] the original value of passed parameter
[Link] the new value of passed parameter to “TRUE”.
Solution using test_and_set()
• Shared Boolean variable lock, initialized to false
• Solution (Pi):
do {
while (test_and_set(&lock))
;
/* critical section */
lock = false;
/* remainder section */
} while (true);
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv:
}
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;
}
[Link] atomically
[Link], if two CAS instructions are executed simultaneously (each on a different
core), they will be executed sequentially in some arbitrary order.
[Link] the original value of passed parameter “value”
[Link] if “value” ==“expected”, set the variable “value” to the value of the passed
parameter “new_value”. That is, the swap takes place only under this condition.
Solution using compare_and_swap
• Shared integer “lock” initialized to 0
• Solution (Pi):
do {
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
} while (true);
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value = = expected)
*value = new_value;
return temp;
}
• A process will enter critical section iff lock == 0
• While in CS, lock ==1 (for all processes!)
• Sets lock = 0 when leaving CS, so that other process can enter its CS
• This algorithm satisfies the mutual-exclusion requirement, but it does
not satisfy the bounded-waiting requirement
• Yesterday's solution does not ensure bounded-waiting
• Reason: When P0 has completed its CS and P1 is about to complete its
RS, P1 may or may not enter CS if P0 also quickly comes back to its
while loop
• Above is true for both test_and_set() and compare_and_swap()
Bounded-waiting and Mutual Exclusion with test_and_set
do {
waiting[i] = true;
key = true;
while (waiting[i] && key)
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 = false;
else
waiting[j] = false;
/* remainder section */
} while (true);
Proof: mutual exclusion requirement is met
• These data structures are initialized to false.
• We note that process Pi can enter its critical section only if either
waiting[i] == false or key == false. The value of key
can become false only if the test_and_set() is executed.
• The first process to execute the test_and_set() will find key ==
false; all others must wait. The variable waiting[i] can become
false only if another process leaves its critical section; only one
waiting[i] is set to false, maintaining the mutual-exclusion
requirement.
Proof: progress requirement is met
• We note that the arguments presented for mutual exclusion also
apply here, since a process exiting the critical section either sets
lock to false or sets waiting[j] to false. Both allow a
process that is waiting to enter its critical section to proceed.
Proof: bounded-waiting requirement is met
• We note that, when a process leaves its critical section, it scans the
array waiting in the cyclic ordering (i + 1, i + 2, ..., n
- 1, 0, ..., i - 1). It designates the first process in this
ordering that is in the entry section (waiting[j] == true) as
the next one to enter the critical section. Any process waiting to enter
its critical section will thus do so within n - 1 turns.
Mutex Locks
• Hardware-based solutions are complicated
• Generally inaccessible to application programmers
• Software tools to solve the critical-section problem
• Mutex locks: simplest such tools
• Protect a critical section by first acquire() a lock then
release() the lock
• Boolean variable available indicates if lock is available or not
Mutex Lock
acquire() { release() {
while (!available) available = true;
; /* busy wait */ }
available = false;
}
do {
acquire lock
Process: critical section
release lock
remainder section
} while (true);
• But this solution requires busy waiting
• This lock therefore called a spinlock
• Same issue with all earlier solutions including test_and_set()
compare_and_swap() instructions
• Often employed on multiprocessor systems where one thread can
“spin” on one processor while another thread performs its critical
section on another processor
Semaphores
• Behave similarly to a mutex lock but can also provide more
sophisticated ways 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 wait() and signal()
Operations
wait(S) { signal(S) {
while (S <= 0) S++;
; // busy wait }
S--;
}
Semaphore Usage
• 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
Semaphore Usage
• Counting semaphores can be used to control access to a given resource
consisting of a finite number of instances. The semaphore is initialized to
the number of resources available.
• Each process that wishes to use a resource performs a wait() operation on
the semaphore (thereby decrementing the count).
• When a process releases a resource, it performs a signal() operation
(incrementing the count).
• When the count for the semaphore goes to 0, all resources are being used.
• After that, processes that wish to use a resource will block until the count
becomes greater than 0.
• Can solve various synchronization problems
• Consider P1 and P2 that require S1 to happen before S2
Create a semaphore “synch” initialized to 0
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
• Can implement a counting semaphore S as a binary semaphore