Scribe Notes for 04/27/10

Tara McBride

Critical section = mutual exclusion + bounded wait

• mutual exclusion: don't step on another thread's toes
• bounded wait: no timed waits indefinitely

readc + writec

1. implemented as system calls
2. on a uniprocessor
3. clock interrupt - might resume some other process

readc:

[ get a lock

add data to buffer

unlock ] (system calls provide lock for free)

[ disableinterrupts( )

add data to buffer

enableinterrupts( ) ]

disabling interrupts is done cheaply--just requires setting a register

Is this a good way to go? Yeah, if it's cheap (which it is on a uniprocessor).

Suppose you disable interrupts and forget to enable interrupts. This is a very common programming error!

Ex.:

disableinterrupts()
for(...)
 if(...)
  return failure; // forget to enable interrupts again!
enableinterrupts();
return();

Readers + Writers

Often have a shared data structure and sometimes there are people that only want to read to it (not write to it).

• Readers: read only access to shared data (unlike readcm which modifies pipe)
• Writers: modify data

Both need to lock. Readers can lock out other readers, which doesn't make a lot of sense.

Want a "read lock" that will handle any amount of readeres.

For write lock, only want one writer (no readers).

How would we do this?

lock-for-reading(struct rlock *p);
lock-for-writing(struct rlock *p);

struct rlock {
 unsigned int readers; // want to keep track of how many readers
 bool writer; // don't need this
 lockt l; // spin lock
}

// lock-for-reading

lock(&p->l); // need lock and unlock in case readers want to access at the same time
p->readers++;
unlock(&p->l);

// lock-for-writing

// This code is wrong:

{
 do lock(&p->l);
 while(p->readers); // is non-zero
}

// Fix it:

{
 for(;;) {
  lock(&p->l);
  if(!p->readers) return; // have write lock
   unlock(&p->l); // have to unlock before locking again
}

void unlock_for_reading(struct rlock *p) {
 lock(&p->l);
 p->readers--;
 unlock(&p->l);
}

void unlock_for_writing(struct rlock *p) {
 unlock(&p->l);
}

What is deeply unsatisfying about this approach?

• Write lock will spin, waiting for readers to stop, doing nothing useful, & wasting the CPU.
• Also, this approach assumes fairness.

Spin locks (mutexes) are not enough...

Blocking mutex: when you can't lock, you give up the CPU so that it can work on some other thread. It's the OS's responsibility to wake you up later.

typedef struct {
 lock_t l;
 bool locked; // does someone else have it locked?
 proc_t *blocked_list; // linked via 'next'
} bmutex_t;

// implement lock & unlock for blocking mutexes

void acquire (bmutex_t *b) {
 lock(&b->l); // generates no machine instructions!
 while (b->locked) {
  add self to b->blocked_list;
  unlock(&b->l);
  schedule(); // let someone else run
  lock(&b->l);
 }
 b->locked = true;
 unlock(&b->l);
}

We need to rethink the organization of this code...

// 'p' = pointer to current process descriptor

for(;;) {
 lock(&b->l);
 add p to b->blocked_list;
 p->blocked = true;
 if (!b->locked)
  break;
 unlock(&b->l);
 schedule();
}
p->blocked = false; // mark ourselves as runnable
remove p from b->blocked_list;

Semaphore: blocking mutex that controls an integer (which tells you how many resources you have available).

• locked when integer == 0 (no resources are available)
• unlocked when integer > 0

Operations on Semaphores: (different names)

• P/V
• down/up
• grab/increase
• acquire/release

void release (bmutex_t *b) {
 lock(&b->l);
 for(each process a in b->blocked list)
  remove a from blocked_list;
 a->blocked = false;
 b->blocked = false;
 unlock(&b->l);
}

struct pipe {
 bmutex_t b;
 char buf[N];
 sid_t r,w; // can't read this line on the board
}

for(;;) {
 acquire(&p->b);
 if(p->w != p->r)
  break;
 release(&p->b);
 return c;
}

Rather than acquire/release:

wait_for(p->w != p->r); // wake me up when there is actually work to do

But, we don't have primitives to do that. Need something else...

Condition Variable

• Boolean condition defining variable
• Blocking mutex protecting this condition
• Condition variable to represent condition
  

API:

wait(condvar_t *c, bmutex_t *b);

PRECONDITION: We've acquired b

Releases b, then blocks until some other thread notifies us that the condition may have changed. Then, reacquires b and returns.

Other parts of API:

notify(condvar_t *c)

Calls this whenever the condition may have changed. It will wake up one of the waiters (one of the threads waiting on this condition).

broadcast(condvar_t *c) // a.k.a. notify_all(condvar_t *c)

Just like notify, but wakes up all the waiters.

struct pipe {
 bmutex_t b;
 char buf[N];
 sid_t r,w; // can't see the board here
 condvar_t nonempty;
 condvar_t nonfull;
}

char readc(strcu pipe *p) {
 acquire(&p->b);
 while(p->w == p->r) // no data in pipe
  wait(&p->nonempty, &p->b);
 char c = p->buf[p->r++];
 notify(&p->nonfull);
 release(&p->b);
}

Deadlock

... | cat | ...

Want to add a new system call

copy(0, 1, 8192); // for performance

// 0, 1 are file descriptors
// 8194 = nbytes

How to implement copy?

void copy(struc pipe *in, struct pipe *out, int nbytes) {
 acquire(&in->b);
 acquire(&in->b);
 .
 .
 .
 release(&in);
 release(&out);
}

Suppose:

process1: copy(p, q, 1000);

and at the exact same time:

process2: copy(p, q, 1000);

After you, Alphonse!

(waiting on each other forever)

This is "deadlock," or "deadly embrace" (race condition).

There are 4 things that need to happen for these conditions to hold:

1. Circular wait
2. Mutual exclusion
3. No pre-emption of locks
4. Hold & wait

Therefore, to fix deadlock, you need only fix one of these things.

Examples:

Fix Property 1:

Whenever a process acquires a lock, check all dependencies for a cycle. If a cycle exists, do not lock. (This is actually not "too bad" to implement).

Fix Property 4:

Order the locks (pick some order). Example order: by machine address. Then, have a rule that says if you need to acquire several locks, you always do it in increasing order. Also, if you have a lock and are waiting, give up all locks and try again.