6.1 Background
shared data, uncontrolled scheduling, inconsistency, execution order ...
Race condition: outcome depends on access order
6.2 Critical-Section Problem
critical section: one in, no other in
entry/critical/exit/remainder section
mutual exclusion, progress, bounded waiting
non-preemptive: free of race conditions in kernel mode, not responsive
6.3 Mutex Locks
declare a lock variable (e.g. mutex, holds the state of lock, either free or held)
hardware sync primitives needed
lock() to acquire the lock: if it is free, acquire it; otherwise, will not return
unlock() to free the lock: if no other waiting, change to free; otherwise, one waiting thread will acquire
6.3.1 Build a Lock
a naive flag
For lock() we just code while(flag); flag=1;
For unlock() we just let flag=0;
violate Mutual exclusion and Bounded waiting
Peterson's
Assume load and store are atomic
int turn; bool flag[2];
For process i, we have
flag[i]=1, turn=j;
while(flag[j] && turn==j);
...
flag[i]=0;
Here are some naive wrong solutions:
while(flag[j]);
flag[i]=1;
...
flag[i]=0;
violate Mutual exclusion. (I1,J1,I2,J2,-_-b)
flag[i]=1;
while(flag[j]);
...
flag[i]=0;
violate Progress. (I1,J1,I2,J2,-_-bb)
turn=j;
while(turn==j);
...
violate Progress. (I1,J1,End1,I2,J2,-_-bbb)
Bakery
choosing[]={0}, number[]={<0,0>}
For process i, we have
choosing[i]=1;
number[i]=<max(number[])+1, i>;
choosing[i]=0;
for j in range(0,n):
while(choosing[j]);
while(number[j] && number[j]<number[i]);
...
number[i]=<0,0>;
Without choosing[], it violates Mutual exclusion
For example, Thread i calculates max(...) but haven't store to number[], we switch to Thread j and it calculates max(...) (result is same as i's, if we have
choosing, then only one can enter c.s.), passes the while loop and enters the c.s., then we switch back to Thread i, it stores the result of max, and passes the loop (assuming i<j) and enters the c.s. Ahhh...
F**k it! may be a little hardware support will make it easier...
Controlling Interrupts
Just disable interrupts (ligation?)
Negatives: privileged operation, multiprocessors, lost interrupts, inefficient
Test-and-set
return old and update to new
lock() is while(TAS(flag,1)==1);
unlock() is flag=0;
violates Bounded waiting
How to satisfy Bounded waiting? a help trick in unlock()
waiting[i]=0;
lock=0;
// lock()
waiting[i]=1;
while(waiting[i] && TAS(lock, 1)==1));
waiting[i]=0;
// unlock()
j=(i+1)%n;
while(j!=i && !waiting[j]) j=(j+1)%n;
if(j==i) lock=false;
else waiting[j]=false;
Compare-and-swap
return old, and update to new if old=expected
lock() is while(CAS(flag,0,1)==1);
violates Bounded waiting
can achieve lock-free sync: Atomic Increment like this and no deadlock can arise (?)
// Argu: *counter, amount
do old=*counter; while CAS(counter, old, old+amount)==0;
Load-Linked & Store-Conditional
(to be continue)
Fetch-and-Add
(to be continue)
6.3.2 Spin-Waiting/Yield
(to be continue)
6.4 Locked Data Structures
（to be continue)
6.5 Condition Varibles
as an explicit queue, Conditional Varibles is always used with a lock and a flag
wait() put itself to sleep (lock holding, free the lock, and need to catch it when wake up)
signal() wake a sleeping thread waiting on this condition (lock holding)
thus we can implement join() like
lock(m);
while(done==0) wait(c,m); // while->if is ok here
unlock(m);
also, exit() like
lock(m);
done=1;
signal(c);
unlock(m);
focus: we use it with a mutex lock m. If not, wait after signal may occur. The same without the flag done
6.5.1 Solve Producer-Consumer Problem
give the code of producer (for one time) as
lock(m);
while(count==MAX) wait(cv_empty, m);
signal(cv_fill);
unlock(m);
6.6 Semaphores
an object with an integer value
target: functionality, correctness and convenience (robust, clean, efficient)
wait() or P()
x--;
if(x<0) push(me), block();
signal() or V()
x++;
if(x<=0) wakeup(pop());
tip: the value of x can be regarded as the count of some resource available. If x>0 then some resource are free to use, while x<0 means some are waiting for the resource.
6.6.1 Basic Patterns
Signaling/Rendezvous
we have statement a and b in different thread, how to guarantee a before b?
For thread A
a;
signal(s);
For thread B
wait(s);
b;
it's evident that we need s=0; initially
rendezvous is just like signaling, skip
Mutex/Multiplex
wait(mutex);
...
signal(mutex);
initially mutex=1;
for Multiplex, just modify the initial value
Barrier/Reusable Barrier
how to ensure that no thread executes critical point until after all threads have executed renderzvous?
rendezvous;
wait(mutex);
count++;
signal(mutex);
if(count==n) signal(barrier);
wait(barrier);
signal(barrier);
critical point;
note that we can also use the following code
rendezvous;
wait(mutex);
count++;
if(count==n) signal(barrier) for n times;
signal(mutex);
wait(barrier);
critical point;
reusable barrier: just a small modification
rendezvous;
wait(mutex);
count++;
if(count==n) signal(b1) for n times;
signal(mutex);
wait(b1);
critical point;
wait(mutex);
count--;
if(count==0) signal(b2) for n times;
signal(mutex);
wait(b2);
...
Pairing
// Leader
signal(leader);
wait(follower);
dance();
// Follower
signal(follower);
wait(leader);
dance();
the code above cannot ensure dance() are executed in pairs
// Leader
wait(mutex);
if(num_follower>0) num_follower--, signal(leader);
else num_leader++, signal(mutex), wait(follower);
dance();
wait(pairing);
signal(mutex);
Follower
wait(mutex);
if(num_leader>0) num_leader--, signal(follower);
else num_follower++, signal(mutex), wait(leader);
dance();
signal(pairing);
// !!! no signal mutex !!!
6.6.2 Classical Problems
Producer-Consumer Problem
empty=MAX, full=0, mutex=1
For producer, we have
wait(empty);
wait(mutex);
...
signal(mutex);
signal(full);
Readers-Writers Problem
First type (reader first): no reader be kept waiting unless a writer has obtain permission to write
rw=1, mutex=1, cnt=0
For writer, we have
wait(rw);
...
signal(rw);
For reader, we have
wait(mutex);
cnt++;
if(cnt==1) wait(rw);
signal(mutex);
...
wait(mutex);
cnt--;
if(cnt==0) signal(rw);
signal(mutex);
Here the writer may starve...
Mid Type (fair): we can feed them like this
mutex=1, write=1, wf=1, cnt=0
For writer, we have
wait(wf);
wait(write);
...
signal(write);
signal(wf);
For reader, we have
wait(wf);
signal(wf);
wait(mutex);
cnt++;
if(cnt==1) wait(write);
signal(mutex);
...
wait(mutex);
cnt--;
if(cnt==0) signal(write);
signal(mutex);
Second Type (writer first): once a writer is ready, the writer perform write as soon as possible
we can solve like this
readcount=0, readcount_mutex=1, readmutex=1, writecount=0, writecount_mutex=1, write_mutex=1
For writer, we have
wait(writecount_mutex);
write_count++;
if(write_count==1) wait(readmutex);
signal(writecount_mutex);
wait(writemutex);
...
signal(writemutex);
wait(writecount_mutex);
writecount--;
if(write_count==0) signal(readmutex);
signal(writecount_mutex);
For reader, we have
wait(readmutex);
wait(readcount_mutex);
readcount++;
if(readcount==1) wait(writemutex);
signal(readcount_mutex);
signal(readmutex);
...
wait(readcount_mutex);
readcount--;
if(readcount==0) signal(writemutex);
signal(readcount_mutex);
why different?
Dining Philosophers
at most 4 can eat at same time?
some are left-handed?
6.6.3 Pros/Cons
Pros: robust/clean/efficient (no spin waiting), better performance (hardware support)
Cons: broadcast (CV can signal all), priority inheritance (high prio proc wait the low ones)
6.7 Monitors
monitor class guarantess that only one thread can be active within the monitor at a time
in Java, just add a keyword synchronized
Producers and Consumers problem: if/while, Hoare/Mesa (multi ones, when you come back, it's gone)