Synchronization Revisited

By: Kin Chung Chu, Wing Cheong Tam


MECHANISM
• spin locks          : data type - mutex_t
                        function  - lock(), unlock()
                        idea      - rely on test-and-set or similiar


• blocking mutexes    : data type - semaphore, bmutex_t
                        function  - acquire(), release()
	                idea      - wait for resource instead of spinning


• condition variables : data type - condvar_t



DISASTERS
• deadlock

BLOCKING MUTEX :

typedef struct {
     proc_t *next;
     int state;
     ..
     ..
     ..
} proc_t;

typedef struct {
     mutex_t m;
     bool locked;
     proc_t *blocked_list;
} bmutex_t;

void acquire (bmutex_t *b) {
     for (;;) {
          lock (&b->m); // acquire spin lock in bmutex_t in order to modify data in bmutex_t
          self->state = BLOCKED; // set current process to BLOCKED
          if (not in b->blocked_list) // check if current process already in bmutex_t's blocked_list
               add self to b->blocked_list;
          if (!b->locked) // check if bmutex_t is free
               break;
          unlock (&b->m); // unlock spin lock in bmutex_t
          schedule(); // ask scheduler to run someone
     } // end for

     self->state = RUNNABLE; // set current process to RUNNABLE
     b->locked = true; // acquire bmutex_t
     remove self from blocked_list;
     unlock (&b->m); // release spin lock in bmutex_t
} // end acquire

void release (bmutex_t *b) {
     lock (&b->m); // acquire spin lock in bmutex_t in order to modify data in bmutex_t
     b->locked = false; // release bmutex_t
     if (b->blocked_list) // check if there are other processes waiting for this bmutex_t
          set state of *(b->blocked_list) to RUNNABLE; // wake up the first process in blocked_list
     unlock (&b->m); // release spin lock in bmutex_t
} // end release



CONDITION VARIALBE
a|b
• read as "a given b" 
• a - statements to perform
• b - condition variable

Do a only if b is true

writec function using spin lock :

void writec (pipe_t *p, char c) {
for (;;) {
     wait_for ((p->w - p->r) != N); // magical wait_for function
     lock (&p->m); // acquire pipe_t's spin lock
     if ((p->w - p->r) != N) // check if pipe again to make sure pipe has not changed between wait_for() and lock()
          break;
     unlock (&p->m);
     } // end for
     p->buf[p->w++ % N] = c; // write c to buffer
     unlock (&p->m);
} // end writec

structure of pipe :

typedef struct {
     bmutex_t b;
     char bud;
     size_t r;
     size_t w;
     condvar_t nonfull;
     condvar_t nonempty;
} pipe_t

writec function using condition variables :

void writec (pipe_t *p, char c) {
     acquire (&p->b); // acquire pipe's bmutex_t
     while ((p->w - p->r) == N) { // check if pipe is full
          wait (&p->nonfull, &p->b);
     } // end while

     p->buf[p->w++ % N] = c; // write c to buffer
     notify (&p->nonempty);
     release (&p->b); // release pipe's bmutex_t
} // end writec



wait() does :
1. release bmutex_t
2. wait for notification
3. reacquires bmutex_t
4. returns


notify() tell scheduler to wake up one waiting process (os do the scheduling)
notifyall() wake up all waiting processes (application do the scheduling)



DEADLOCK
assume a function - copy (0, 1, N);

0 - file descriptor, copy from
1 - file descriptor, copy to
N - number of byte to copy


for simplicity, copy() copy one byte only and not doing condition variable

copy function:

void copy (pipe_t *from, pipe_t to) {
     acquire (&from->b);
     acquire (&to->b);
     if ((from->w - to->r != 0) && (to->w - to->r != N))
          to->buf[to->w++ % N] = from->buf[from->r++ % N];
     release (&from->b);
     release (&to->b);
} // end copy

Assume:
P1 does : copy (a, b); acquire (&a->b); - OK acquire (&b->b); - wait	P2 does : copy (b, a); acquire (&b->b); - OK acquire (&a->b); - wait

DEADLOCK!! 
- P1 has lock a
- P2 has lock b
- P1 wait for lock b
- P2 wait for lock a

How about:
P1 does : copy (a, b); if (acquire (&a->b)){} - OK while (!acquire (&b->b)) - wait continue;	P2 does : copy (b, a); if (acquire (&b->b)){} - OK while (!acquire (&a->b)) - wait continue;

LIVELOCK!! 
- P1 has lock a
- P2 has lock b
- P1 keep trying to lock b, but acquire always fail
- P2 keep trying to lock a, but acquire always fail




Ways to attack deadlock
0. do not allow user to do copy (a, b); and copy (b, a);
1. acquire() can fail with errno == EDEADLOCK
   - can lead to livelock (processes are running but making no real progress)



Ways to avoid livelock
1. a process can give up all locks if any acquire fails
   - kernel maintains a data structure recording who is waiting for what

2. no mutexes

3. allowed lock preemption
   all syscalls that require a lock can fail, errno == ELOSTLOCK
   - one more errno to handle

4. acquire fails if you have the lock already
   + easier to implement than (1)
   - more restrictive : copy becomes read() + write()


Lock ordering
you want { L3, L1, L4 }
do this:

acquire L1
acquire L3
acquire L4

if any fail, release all locks, start over.

Deadlock is a race condition (testing often doesn't work well)
4 conditions :
  • circular wait
  • mutual exclusion
  • no preemption of locks
  • hold & wait ( a process can hold | lock and wait for another )

Review of storage hierarchy

Disk

To do read :
1) seek & move
2) rotational latency
3) throughput as data go underneath head