CS 162, Spring 2007

Section notes for 6 February 2007

Sections 102/103

GSI: Thomas Kho <cs162-ta@inst.eecs.berkeley.edu> / <tkho@eecs>

Examples are from fa06 course slides

AGENDA

Finish up lock material from last week
Compare&Swap for queue operations (Lock-free queue)
Deadlocks

ADMINISTRIVIA

Upcoming events

2/13 11:59p, Nachos phase 1 initial design doc
2/15-2/16, Design reviews

2/20 11:59p, Nachos phase 1 code

2/22 11:59p, Nachos phase 1 final design doc

HW1 Evaluations!

Last week

Take a look at implementation of locks

Group consolidation?

WORKING IN GROUPS

Task Partitioning

Functional partitioning (Person A does part 1, Person B does part 2, ...)
Task (Person A designs, Person B writes code, Person C tests)

Question: What did you do for hw1, what worked, and what would you change for Nachos?

Importance of hardware support for atomic operations

Milk example doesn't scale when you have many processes trying to gain access.

Compare&Swap for queues
compare&swap (&address, reg1, reg2) { /* 68000 */
if (reg1 == M[address]) {

    M[address] = reg2;

    return success;

  } else {

    return failure;

  }

}

Here is an atomic add to linked-list function:
addToQueue(&object) {

do { // repeat until no conflict

ld r1, M[root] // Get ptr to current head
st r1, M[object] // Save link in new object

} until (compare&swap(&root,r1,object));

}

root -----> next --> next
     |    ^ +obj     +obj
     |    |
     \next/
      +obj

SYNCHRONIZATION TOOLS

Locks, condition variables, semaphores, interrupts, atomic ops

Locks: implement mutual exclusion

Semaphores: a generalized lock, having a non-negative integer value (classical definition)

P(Semaphore s)
{
  await s > 0, then s := s-1; /* must be atomic once s > 0 is detected */
}

V(Semaphore s)
{
  s := s+1;   /* must be atomic */
}

Init(Semaphore s, Integer v)
{
  s := v;
}

from Wikipedia

    //Implementing a semaphore in Nachos

    public void P() {
    boolean intStatus = Machine.interrupt().disable();

    if (value == 0) {
        waitQueue.waitForAccess(KThread.currentThread());
        KThread.sleep();
    }
    else {
        value--;
    }

    Machine.interrupt().restore(intStatus);
        }

    //
        public void V() {
    boolean intStatus = Machine.interrupt().disable();

    KThread thread = waitQueue.nextThread();
    if (thread != null) {
        thread.ready();
    }
    else {
        value++;
    }

    Machine.interrupt().restore(intStatus);

Starvation vs. Deadlock

Starvation: thread waits indefinitely

Example, low-priority thread waiting for resources constantly in use by high-priority threads

Deadlock: circular waiting for resources

Thread A owns Res 1 and is waiting for Res 2

Thread B owns Res 2 and is waiting for Res 1

Deadlock ⇒ Starvation but not vice versa

Starvation can end (but doesn’t have to)

Deadlock can’t end without external intervention

- Types of resources
    - preemptable resources can be taken away with little or no problem
        (eg cpu, memory), and can be scheduled
    - non-preemtable resources cause a problem if they are taken away
        (eg disk, semaphores, terminal, printer),
        and must be allocated

- Deadlock is concerned with allocating resources.
- Deadlock is a situation in which each thread in a set is waiting for something from some other thread waiting in the set. Since each is waiting, non can proceed.

Four requirements for Deadlock

Limited access (Mutual exclusion or a bounded buffer)

Mutual exclusion - only one thread at a time can use a resource.

Hold and wait

Thread holding at least one resource is waiting to acquire additional resources held by other threads

No preemption

Resources are released only voluntarily by the thread holding the resource, after thread is finished with it

Circular wait

There exists a set {T1, …, Tn} of waiting threads

T1 is waiting for a resource that is held by T2

T2 is waiting for a resource that is held by T3

Tn is waiting for a resource that is held by T1

- Approaches to deadlock problem
    - avoidance, OS solution
       1. must eliminate one of the four deadlock conditions (hard!)
       2. only make allocations that are "safe" (Banker's Algorithm)

Methods for Handling Deadlocks

Allow system to enter deadlock and then recover

Requires deadlock detection algorithm

Some technique for forcibly preempting resources and/or terminating tasks
the database solution

Ensure that system will never enter a deadlock

Need to monitor all lock acquisitions

Selectively deny those that might lead to deadlock

Ignore the problem and pretend that deadlocks never occur in the system

Used by most operating systems, including UNIX

- A safe state is one in which there exists a sequence of task completions which lead to all tasks completed.
A safe allocation is one that leads to a safe state.
- An unsafe state may lead to deadlock.

- The Banker's Algorithm is used to compute a safe sequence of tasks.

--------------------------------------------------------------------------
    Banker's Algorithm (deadlock prevention)
--------------------------------------------------------------------------
k is a resource
for each thread x
max(x,k) is max #k to be used by x
alloc(x,k) is #k currently allocated to x
need(x,k) is #k still needed by x
avail(k) is #k currently available

    If all threads can finish with no additional resources,
        need(x) <= avail(k) for all k and x
        state = safe

    Else for all threads do
        Find a thread x, such that
        need(x,k) <= avail(k)

    If not found
        state = unsafe

    If found release resources
        mark x = finished
        avail(k) = avail(k) + alloc(x)

- Source of name: Can be used by banks so they don't allocate their
    available cash without being able to satisfy the needs of all
    customers.
- Process enters system: Declares maximum resources it may need

    Available[0..r] : Number of available resources of each type
    Max[0..p][0..r] : Max demand of process P for resource R
    Alloc[0..p][0..r] : Amount of R allocated to P
    Need[0..p][0..r] : Amount of R *might be* needed by P;
      Need[p,r] = Max[p,r] - Alloc[p,r]

- Define notation:
       Vector X <= Y if X[i] <= Y[i] forall i

- Making a resource request:
     1) Process P states that it needs resources:
          Request[p][0..r]
     2) If Request[p][0..r] > Need[p][0..r], ERROR
         Process is requesting more than its stated maximum
     3) If Request[p][0..r] > Available[p][0..r], WAIT
         All resources not available, so must wait
     4) Set:
         Available[0..r] = Available[0..r] - Request[p][0..r]
    Alloc[p][0..r] = Alloc[p][0..r] + Request[p][0..r]
    Need[p][0..r]   = Need[p][0..r] - Request[p][0..r]

        Now test if this resource-allocation state is "safe".
    If safe, proceed, otherwise revert to previous values of
    vectors and have P wait.

- Safety test: Available resources >= Max needed by ANY process
    Implementation:
      Work[0..r] = Available[0..r]
      Finish[0..p] = false

      1) Find a process P such that
           Finish[P] = false && Need[p][0..r] <0 Work[0..r]
         If no such P exists, goto 3

      2) Work[0..r] = Work[0..r] + Alloc[p][0..r]
         Finish[p] = true
    Goto 1

      3) If Finish[p] = true for all procs P, system is safe

   - Complexity: O(r * p^2)

   - Dining lawyers with the Banker's Algorithm
      4 lawyers (P1, P2, P3, P4)
      4 chopsticks - single resource with Available[r] = 4
      Each lawyer needs 2 chopsticks: Need[0..p][r] = 2

   - Lawyer P1 has 2 chopsticks already

        Alloc Max Avail
    P1    2     2     2
    P2    0     2
    P3    0     2
    P4    0     2

   - P2 asks for a chopstick
     Go ahead and "allocate" it:

        Alloc Max Avail
    P1    2     2     1
    P2    1     2
    P3    0     2
    P4    0     2

     Test for safe state:

     1) Initialize:

        Work = 1

        Alloc Max Need Finish
    P1    2     2     0     F
    P2    1     2     1     F
    P3    0     2     2     F
    P4    0     2     2     F

     2) Need <= Work for P1, so...

        Work = 3

        Alloc Max Need Finish
    P1    2     2     0     T
    P2    1     2     1     F
    P3    0     2     2     F
    P4    0     2     2     F

     3) Need <= Work for P2, so...

        Work = 4

        Alloc Max Need Finish
    P1    2     2     0     T
    P2    1     2     1     T
    P3    0     2     2     F
    P4    0     2     2     F

     3) Need <= Work for P3, so...

        Work = 4 (no change!)

        Alloc Max Need Finish
    P1    2     2     0     T
    P2    1     2     1     T
    P3    0     2     2     T
    P4    0     2     2     F

     4) Need <= Work for P4, so...

        Work = 4 (no change!)

        Alloc Max Need Finish
    P1    2     2     0     T
    P2    1     2     1     T
    P3    0     2     2     T
    P4    0     2     2     T

     We are in a safe state!

   - What about a different setup? P1, P2, and P3 have grabbed
     one chopstick and P4 is about to grab one. What happens?

        Alloc Max Avail
    P1    1     2     1
    P2    1     2
    P3    1     2
    P4    0     2

   - P4 asks for a chopstick
     Go ahead and "allocate" it:

        Alloc Max Avail
    P1    1     2     0
    P2    1     2
    P3    1     2
    P4    1     2

     Test for safe state:

     1) Initialize:

        Work = 0

        Alloc Max Need Finish
    P1    1     2     1     F
    P2    1     2     1     F
    P3    1     2     1     F
    P4    1     2     1     F

     2) No proc exists which has Need <= Work! So we are not in a
        safe state.

- What if P1 had asked for a second chopstick instead?

     1) Initialize:

        Work = 0

        Alloc Max Need Finish
    P1    2     2     0     F
    P2    1     2     1     F
    P3    1     2     1     F
    P4    0     2     2     F

     2) P1's need is <= Work, so

        Work = 2 (+ 2)

        Alloc Max Need Finish
    P1    2     2     0     T
    P2    1     2     1     F
    P3    1     2     1     F
    P4    0     2     2     F

        Now you can see that any order of P2, P3, or P4 will satisfy
    the safe state.