CS 111, Winter 2012 – Lecture 9
Scribe Notes
Synchronization Primitives and Deadlock
02/08/2012
Scribe: Daniel Lee
Lecturer: Paul Eggert
Synchronization
using lock/unlock
Synchronization
is not guaranteed through the use of critical sections. It requires the use of
low level primitives in coordination with lock and unlock.
Basic Implementation of lock and unlock
typedef
bool lock_t;
void lock (lock_t *l){
while (*l)
continue; //This code creates a race condition
*l = true;
}
void unlock(lock_t *l){
*l = false;
}
***There
is a function in the x86 instruction set that seems
like it would be helpful: lock incl x
This
function grabs the bus, allowing no other processes to access it, increments x
by 1, then releases the bus. In actuality though, this function is useless for
what we are trying to do here.
For
a practical example of using lock and unlock, here is the function int xchgl (x, r), which exchanges
the contents of x and r as long as x and r are aligned in memory.
int xchgl (int *p, int new){
int old = *p; //The assembly code of this is
*p = new; //asm (xchgl
%....)
return
old;
}
=>This
particular implementation creates a race condition when running multiple
threads. To avoid this, we should implement a lock on the code while the
exchange is occurring.
typedef
int lock_t;
void lock (lock_t *l){
while
(xchgl (l, 1) != 0)
continue;
}
The
lock makes it so that no other thread can intercept while the function is
running and change the data in r or x as long as it owns the lock.
***What
if we want to increment a value by 2 when the function is called? This can be
done with the introduction of two atomics:
.....
lock_t
vl;
int v;
.....
lock (&vl);
v += 2;
unlock (&vl);
.....
For
another example of how lock works, let’s look at the function cmpxchgl (), which will compare two values then swap them.
bool cmpxchgl (int *p, int old, int new) {
if
(*p == old) {
*p =
new;
return true;
}
else
return false;
}
If
the function were to be called in this manner: while (!cmpxchgl (&v, v, v + 2), it would result in
undefined behavior because while the comparison is occurring, another thread
may come and change the value of v. This is a common problem with shared
resources among multiple threads.
To
fix this, we only need modify the code like this:
do {
int old = v; //lw and sw
are atomic in an x86 machine
} while (!cmpxchgl (&v, old, old + 2); //we can assume this holds true in //general
Read and write locks
The
size of the lock has limits, so how do we lock large objects?
struct
rwlock_t {
lock_t l;
int readers; //Number of readers accessing the object
bool writers; //Is anyone trying to write to the object
}
void lock_for_read (struct
rwlock *l) {
lock
(&l->l);
l->readers++;
unlock
(&l->l);
}
void unlock_for_read (struct
rwlock *l) {
lock
(&l->l);
l->readers--;
unlock
(&l->l);
}
So
far it seems like the code will prevent race conditions. Now
to implement the write lock.
void lock_for_write (struct
rwlock *l) {
lock
(&l->l);
l->writers
= true;
unlock
(&l->l);
}
There
is a problem with this implementation in that we need to check if any readers
are locking out writers.
void unlock_for_read (struct
rwlock *l) {
while
(l->readers)
continue;
for
(;;) { //When in doubt, make an infinite loop
lock (&l->l);
if (!l->readers)
break;
unlock(&l->l);
}
}
void unlock_for_write (struct
rwlock *l) {
unlock
(&l->l);
}
Readcare and writecare
struct
pipe {
lock_t l;
char
buf [N];
size_t r, w;
}
void writec (struct
pipe *p, char c) {
for
(;;) {
lock (&p->l);
if (p->w – p->r < N)
Break;
unlock (&p->l);
}
p->buf[p->w++%N] = c;
unlock
(&p->l);
}
char readc (struct
pipe *p) {
for
(;;) {
lock (&p->b);
if (p->w != p->r)
break;
unlock (&p->b);
}
char
c = p->buf[p->r++];
unlock
(&p->b);
return
c;
}
The
problem with this implementation is that it chews up a lot of CPU just waiting
for a lock. We need a more efficient implementation that doesn’t waste so much
CPU time.
Blocking
Mutexes (mutices?)
The
idea behind a blocking mutex is to “grab a lock if it
is available, otherwise, release the CPU to another process”. This improves
efficiency as we no longer have threads idly waiting to grab a lock.
typedef
struct {
.....
bool blocked;
.....
}
struct
b_mutex {
lock_t l;
bool locked;
proc_t
*blocked_list; //Linked list of processes that are blocked
}
void acquire (struct b_mutex
*p) {
for
(;;) {
lock (&p->l);
add (&p->blocked_list,
self);
self->blocked
= true;
if (!p->locked);
break;
unlock (&p->l);
schedule (); //Gives up the CPU
}
lock
(&p->l);
self->locked
= false;
b->locked
= true;
remove
(&p->blocked_list, self);
unlock
(&p->l);
}
void release (struct b_mutex
*p) {
lock
(&p->l);
//set the first process in
p->blocked_list to RUNNABLE
if
(p->blocked_list)
p->blocked_list->locked =
false;
p->locked
= false;
unlock
(&p->l);
}
Condition
Variables
The
basic idea is to have a pseudo-event driven code where if certain conditions
are met, then the system will alert whatever function is waiting on those
conditions. This saves CPU time and resources on things like waiting and
polling.
The
desired API for this is in the form of:
wait_for(condvar_t *c, bmutex_t *b) {
(b
must be acquired already)
[releases
b, blocks until some other thread notifies
[reacquires
b
notify
(condvar_t *c) notifies on waiting thread
notify
All “ “ “
The three things required for a code
driven by condition variables are:
1.
Condition
variable
--stand-in
for arbitrary boolean
expression
2.
Blocking
mutex
3.
Storage
for the variable itself
struct
pipe {
lock_t l;
char
buf [N];
size_t r, w;
condvar_t nonempty; //The new condition variables added
condvar_t nonfull; //to the struct pipe
}
With the new condition variables,
the complete implementation of readc() and writec() are now:
void writec (struct
pipe *p, char c) {
acquire
(&p->l);
while
(p->w – p->r == N)
wait_for (&p->nonfull,
&p->l);
p->buf [p->w++%N] = c;
notify
(&p->nonempty);
release
(&p->b);
}
char readc (struct
pipe *p) {
acquire
(&p->b);
while
(p->w == p->r)
wait_for (*p->nonempty, &p->b);
char
c = p->buf[p->r++];
notify
(&p->nonfull);
release
(&p->b);
}
Deadlock
While the implementation of
synchronization primitives certainly clears up a lot of problems with
synchronization, there still exists the problem of deadlock. Deadlock can occur
when there is too much synchronization, or over-synchronization. Here is an
example of deadlock.
for (;;) {
n = read (fd, buf,
sizeof buf);
write
(fd, buf, n);
}
//Thread 1
n = copy (ifd, ofd, n); //copy () acquires a lock on ifd, then acquires a lock on ofd. Then
it copies the data and releases both locks.
//Thread 2
copy (ofd, ifd,
n);
In the above example, Thread 1 would
acquire a lock on ifd while Thread 2 acquires a lock
on ofd, which results in both of them waiting for the
other thread to release the lock, which it never will.
This shows that deadlock is a kind
of race condition, where if one thread does not acquire all the required locks
before some other thread, both threads end up waiting for each other forever
and deadlocking.
Conditions for deadlock
For the possibility of deadlock to
occur, four conditions must be met:
1.
Circular
wait for multiple threads
2.
Mutual
exclusion
3.
No
preemption of locks. Threads cannot just take a lock from another thread when
needed.
4.
Hold
and wait. Threads will hold onto resources while waiting for other resources.
Avoiding deadlock
There are several ways to make it so
that deadlock will not occur. Two possible methods are:
1.
Have
the system maintain a dependency graph. If the acquisition of a lock would
create an endless cycle in the graph, then deny the lock.
2.
Lock
ordering. Always acquire locks in an agreed order, and if any of the locks are
already owned by another thread, then release all owned locks and try again.