CS 563 Concurrent Programming
Lecture 12: Locks
Critical Section Problem
Copyright By PowCoder代写 加微信 powcoder
implementing (often large) atomic actions in software why?
linked lists in OSes, database records, counters, etc.
Implementing Atomic Actions
Spin locks (busy waiting)
multiprocessor OS or parallel program Blocking primitives (e.g., semaphores)
higher-level parts of an OS or multithreaded programs
Model for CS Problem
process CS[i = 1 to n] { ! !while (true) { !
! !CSenter: entry protocol;
! !critical section;
! !CSexit: exit protocol; ! !noncritical section;
Model for CS Problem
Specifying mutual exclusion
int in[1:n] # initially all zero
in[i] = 1 when process i is in its critical section
at all times require
MUTEX: 0 <= sum of in[i] <= 1
Spin Locks
How can we solve the CS problem using machine instructions directly?
Spin Locks
Observation -- there are only 2 key states:
nobody is in its CS lock == false
somebody is in its CS lock == true
Using just lock, we get the following code:
〈 await (!lock) lock = true; 〉
critical section
lock = false; # angle brackets needed here?
Test and Set
The first instruction for implementing spin locks (IBM, mid 1960s)
bool TS(bool lock) { # an atomic instruction 〈 bool initial = lock;
lock = true;
return initial; 〉 }
We get the following simple solution
CSenter: while (TS(lock)) skip;
CSexit: lock = false # simply reinitialize
Properties
Mutual exclusion
Absence of deadlock (livelock)
bool TS(bool lock) { # an atomic instruction 〈 bool initial = lock;
lock = true;
return initial; 〉 }
CSenter: while (TS(lock)) skip;
CSexit: lock = false;
(with weakly fair scheduling) Absence of unnecessary delay
(with weakly fair scheduling) Eventual entry (fairness)
not fair -- no GUARANTEE of eventual entry
Problems with TS
Efficiency Fairness
TS Efficiency
Shared memory multiprocessors
Performance of Test and Set
TS reads AND writes a lock
Best case (no contention), i.e. lock is free, 1 process wants in:
read lock (50 clocks) ✤ write lock (50 clocks)
bool TS(bool lock) { # an atomic instruction 〈 bool initial = lock;
lock = true;
execute CS
write lock (1 or 50 clocks)
repeated usage by the same process gets cheap reads
return initial; 〉 }
Performance of Test and Set
Worst case -- n processes all trying to get into their CS
1 process does read and write and succeeds (100 clocks) other n-1 processes do read, write, fail, repeat
hence, the bus is jammed AND the first process might get delayed when it wants to release the lock
Test and Test and Set
CSenter: while (lock) skip; # test
One extra clock in best case; no write (or bus use) while spinning
lock = false;
while (TS(lock))
while(lock) skip;
# test and set
# test again
bool TS(bool lock) { # an atomic instruction 〈 bool initial = lock;
lock = true;
return initial; 〉 }
Implementing Await Statements
We can use a spin lock solution to implement any kind of await statement and hence any kind of atomic action
CSenter; S; CSexit;
〈 await(B) S; 〉
while (!B) { CSexit; Delay; CSenter; }
S; CSexit;
Fair Solutions to the CS Problem
Need a fair way to break ties
Tiebreaker Algorithm
process CS2 {
while (true) {
last = 2; in2 = true; /* entry
protocol */ 〈await (!in1 or last == 1);〉
critical section;
in2 = false; /* exit protocol */ noncritical section;
bool in1 = false, in2 = false; int last = 1;
process CS1 {
while (true) {
last = 1; in1 = true; /* entry
protocol */ 〈await (!in2 or last == 2);〉
critical section;
in1 = false; /* exit protocol */ noncritical section;
Ticket Algorithm
shared: int number = 1, next = 1; !
CSenter: int myturn; # private variable; !
! ! ! ! !#onecopyperprocess
! ! 〈 myturn = number; number++; 〉!
! ! 〈 await(myturn == next); 〉!
CSexit: 〈 next++ 〉 # different variable, ! !! ! !#notaspinlock!
Fetch and Add Instruction
Read and increment a variable as a single atomic action:
int FA(var, incr) {
〈 int tmp = var; var += incr; return (tmp); 〉
Ticket drawing is then simply
myturn = FA(number, 1);
Pros and Cons:
But, hardware has to provide an FA or similar instruction
Bakery Algorithm
int turn[1:n] = ([n] 0);
process CS[i = 1 to n] {
while (true) {
critical section;
turn[i] = 0;
noncritical section;
int turn[1:n] = ([n] 0);
process CS[i = 1 to n] {
while (true) {
turn[i] = 1;
turn[i] = max(turn[1:n]) + 1;
for [j = 1 to n st j != i]
while (turn[j] != 0 and
(turn[i],i) > (turn[j],j)) skip;
〈turn[i] = max(turn[1:n]) + 1;〉
for [j = 1 to n st j != i]
〈await (turn[j] == 0 or turn[i] < turn[j]);〉
critical section;
turn[i] = 0;
noncritical section;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com