Critical Sections with lots of Threads
Announcements
CS 414 Homework due today
Review: Race conditions
Definition: timing dependent error involving shared state
Whether it happens depends on how threads scheduled
Hard to detect:
All possible schedules have to be safe
Number of possible schedule permutations is huge
Some bad schedules? Some that will work sometimes?
they are intermittent Timing dependent = small changes can hide bug
The Fundamental Issue: Atomicity
Our atomic operation is not done atomically by machine
Atomic Unit: instruction sequence guaranteed to execute indivisibly Also called critical section (CS)
When 2 processes want to execute their Critical Section,
One process finishes its CS before other is allowed to enter
Revisiting Race Conditions
Process a: while(i < 10) i = i +1; print A won!;
Process b: while(i > -10) i = i - 1; print B won!;
Who wins? Will someone definitely win?
Critical Section Problem
Problem: Design a protocol for processes to cooperate, such that only one process is in its critical section
How to make multiple instructions seem like one?
Process 1 Process 2 CS1 CS2
Time
Processes progress with non-zero speed, no assumption on clock speed Used extensively in operating systems: Queues, shared variables, interrupt handlers, etc.
Solution Structure
Shared vars:
Initialization:
Process: ... ... Entry Section
Critical Section
Exit Section
Added to solve the CS problem
Solution Requirements
Mutual Exclusion
Only one process can be in the critical section at any time
Progress
Decision on who enters CS cannot be indefinitely postponed
No deadlock
Bounded Waiting
Bound on #times others can enter CS, while I am waiting
No livelock
Also efficient (no extra resources), fair, simple,
Refresher: Dekkers Algorithm
Assumes two threads, numbered 0 and 1
CSEnter(int i)
{
inside[i] = true; while(inside[J]) { if (turn == J) { inside[i] = false; while(turn == J) continue; inside[i] = true; } }}
CSExit(int i) {
turn = J; inside[i] = false; }
Petersons Algorithm (1981)
CSEnter(int i) {
inside[i] = true; turn = J; while(inside[J] && turn == J) continue;
CSExit(int i) {
inside[i] = false; }
Simple is good!!
Napkin analysis of Petersons algorithm:
Safety (by contradiction):
Assume that both processes (Alan and Shay) are in their critical section (and thus have their inside flags set). Since only one, say Alan, can have the turn, the other (Shay) must have reached the while() test before Alan set his inside flag. However, after setting his inside flag, Alan gave away the turn to Shay. Shay has already changed the turn and cannot change it again, contradicting our assumption.
Liveness & Bounded waiting => the turn variable.
Can we generalize to many threads?
Obvious approach wont work:
CSEnter(int i) {
inside[i] = true; for(J = 0; J < N; J++) while(inside[J] && turn == J) continue;
CSExit(int i) {
inside[i] = false;
Issue: Whos turn next?
Bakery concept
Think of a popular store with a crowded counter, perhaps the pastry shop in Montreals fancy market
People take a ticket from a machine If nobody is waiting, tickets dont matter When several people are waiting, ticket order determines order in which they can make purchases
Bakery Algorithm: Take 1
int ticket[n]; int next_ticket;
CSEnter(int i) {
ticket[i] = ++next_ticket; for(J = 0; J < N; J++) while(ticket[J] && ticket[J] < ticket[i]) continue;
CSExit(int i) {
ticket[i] = 0;
Oops access to next_ticket is a problem!
Bakery Algorithm: Take 2
int ticket[n];
Just add 1 to the max!
CSEnter(int i) {
CSExit(int i) {
ticket[i] = 0;
ticket[i] = max(ticket[0], ticket[N-1])+1; for(J = 0; J < N; J++) } while(ticket[J] && ticket[j] < ticket[i]) continue;
Clever idea: just add one to the max. Oops two could pick the same value!
Bakery Algorithm: Take 3
If i, j pick same ticket value, ids break tie:
(ticket[J] < ticket[i]) || (ticket[J]==ticket[i] && J<i)
Notation: (B,J) < (A,i) to simplify the code:
(B<A || (B==A && J<i)), e.g.: (ticket[J],J) < (ticket[i],i)
Bakery Algorithm: Take 4
int ticket[N]; boolean picking[N] = false;
CSEnter(int i) {
ticket[i] = max(ticket[0], ticket[N-1])+1; for(J = 0; J < N; J++) } while(ticket[J] && (ticket[J],J) < (ticket[i],i)) continue;
CSExit(int i) {
ticket[i] = 0;
Oops i could look at J when J is still storing its ticket, and yet J could have a lower id than me (i)!
Bakery Algorithm: Almost final
int ticket[N]; boolean choosing[N] = false;
CSEnter(int i) {
CSExit(int i) {
ticket[i] = 0;
choosing[i] = true; ticket[i] = max(ticket[0], ticket[N-1])+1; } choosing[i] = false; for(J = 0; J < N; J++) { while(choosing[J]) continue; while(ticket[J] && (ticket[J],J) < (ticket[i],i)) continue;
} }
Bakery Algorithm: Issues?
What if we dont know how many threads might be running?
The algorithm depends on having an agreed upon value for N Somehow would need a way to adjust N when a thread is created or one goes away
Also, technically speaking, ticket can overflow!
Solution: Change code so that if ticket is too big, set it back to zero and try again.
Bakery Algorithm: Final
int ticket[N]; /* Important: Disable thread scheduling when changing N */ boolean choosing[N] = false;
CSEnter(int i) {
do { ticket[i] = 0; choosing[i] = true; ticket[i] = max(ticket[0], ticket[N-1])+1; choosing[i] = false; } while(ticket[i] >= MAXIMUM); for(J = 0; J < N; J++) { while(choosing[J]) continue; while(ticket[J] && (ticket[J],J) < (ticket[i],i)) continue;
CSExit(int i) {
ticket[i] = 0;
} }
How do real systems do it?
Some real systems actually use algorithms such as the bakery algorithm
A good choice where busy-waiting isnt going to be super-inefficient For example, if you have enough CPUs so each thread has a CPU of its own
Some systems disable interrupts briefly when calling CSEnter() and CSExit() Some use hardware help: atomic instructions
Critical Sections with Atomic Hardware Primitives
Share: int lock; Initialize: lock = false;
Process i While(test_and_set(&lock));
Assumes that test_and_set is compiled to a special hardware instruction that sets the lock and returns the OLD value (true: locked; false: unlocked)
Critical Section lock = false;
Problem: Does not satisfy liveness (bounded waiting) (see book for correct solution)
test_and_set Instruction
Definition:
boolean test_and_set (boolean *target) { boolean rv = *target; *target = TRUE; return rv: }
Solution using TestAndSet
Shared boolean variable lock., initialized to false. Solution: while (true) { while ( TestAndSet (&lock )) ; /* do nothing // critical section
lock = FALSE; // } remainder section
Swap Instruction
Definition:
void Swap (boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp: }
Solution using Swap
Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key. Solution: while (true) { key = TRUE; while ( key == TRUE) Swap (&lock, &key ); // critical section
lock = FALSE; // remainder section
Presenting critical sections to users
CSEnter and CSExit are possibilities But more commonly, operating systems have offered a kind of locking primitive We call these semaphores
Semaphores
Non-negative integer with atomic increment and decrement Integer S that (besides init) can only be modified by:
P(S) or S.wait(): decrement or block if already 0 V(S) or S.signal(): increment and wake up process if any
These operations are atomic (indivisible)
These systems operation Some systems useuse the the operation signal() instead of V() wait() instead of P() semaphore S;
P(S) { while(S 0) ; S--; }
V(S) { S++; }
Semaphore Types
Counting Semaphores:
Any integer Used for synchronization
Binary Semaphores
Value is limited to 0 or 1 Used for mutual exclusion (mutex) Process i Shared: semaphore S Init: S = 1; P(S); Critical Section V(S);
Semaphore Implementation
Must guarantee that no two processes can execute P () and V () on the same semaphore at the same time
No process may be interrupted in the middle of these operations
Thus, implementation becomes the critical section problem where the P and V 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.
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.
Implementing Semaphores
Busy waiting (spinlocks)
Consumes CPU resources No context switch overhead
typedef struct semaphore { int value: ProcessList L; } Semaphore; void P(Semaphore *S) { S->value = S->value - 1; if (S.value < 0) { add this process to S.L; block(); } }
Alternative: Blocking Should spin or block?
Less time spin More time block A theory result:
Spin for as long as block cost If lock not available, then block void V(Semaphore *S) { S->value = S->value + 1; Shown factor of 2-optimal! if (S->value <= 0) { remove process P from S.L; wakeup P } }
Implementing Semaphores
Per-semaphore list of processes
Implemented using PCB link field Queuing Strategy: FIFO works fine
Will LIFO work?
In Summary
Fundamental Issue
Programmers atomic operation is not done atomically Atomic Unit: instruction sequence guaranteed to execute indivisibly Also called critical section (CS)
Critical Section Implementation
Software: Dekkers, Petersons, Bakers algorithm Hardware: test_and_set, swap
Hard for programmers to use
Operating System: semaphores
Implementing Semaphores
Multithread synchronization algorithms shown earlier Could have a thread disable interrupts, put itself on a wait queue, then context switch to some other thread (an idle thread if needed) The O/S designer makes these decisions and the end user shouldnt need to know
