CS 162, Spring 2007

Section notes for 13 February 2007

Sections 102/103

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

Based on notes by Hakim Weatherspoon and Karl Chen

AGENDA

Monitors
Linkers & Loaders

DEADLINES
2/13 - Phase I initial design doc due
2/15-2/16 - Design reviews *SIGNUP*


NACHOS WALKTHROUGH

  - Homework #1 posted: Need to understand this to do project



  - Overall: For this project, really need to understand

     nachos.threads.KThread

     nachos.threads.ThreadedKernel

     nachos.machine.TCB  (not the internals, just the interface)



  - Only modify nachos.threads package - nothing else

    You cannot use Java threads or 'synchronized' keyword



  - Main structure:

     nachos.machine.* -- the internals of the implementation

       Not really important to understand how this works, but

       need to know what the public methods are



       Machine.interrupt().disable()

            Disable interrupts, return flag of previous interrupt state

       Machine.interrupt().enable()

            Enable interrupts

       Machine.interrupt().restore()

            Restore to previously saved flag



       TCB.contextSwitch()

        Context switch to this TCB. Used internally by KThread,

        you don't need to call this yourself but important to

        see where it's used

       TCB.start()

        Used to bootstrap a new TCB - used internally by KThread



    nachos.threads.* -- what you will be modifying

       

       KThread(Runnable target)

            Create a new kernel thread and associate with it the

        code in 'target.run()'.

       KThread.setName(String name)

            Associate a new, can be retrieved with getName

       KThread.fork()

            Fork the given thread - that is, start it running

       KThread.yield()

            Cause the current thread to yield the CPU

       KThread.sleep()

            Cause the current thread to block - will be woken up later

       KThread.ready()

            Move this thread to the ready queue, i.e. wake it up



       Lock.acquire()

            Sleep until this lock can be acquired



        private KThread lockHolder;



        intStatus = Machine.interrupt().disable();

        if (lockHolder == null) {

          waitQueue.acquire(KThread.currentThread());

          lockHolder = KThread.currentThread();

        } else {

          waitQueue.waitForAccess(KThread.currentThread());

          KThread.sleep();

        }

        Machine.interrupt.restore(intStatus);



       Lock.release()

            Release the lock

        (Ask class how this would be implemented)



            int status = Machine.interrupt().disable();

        lockHolder = waitQueue.nextThread();

        lockHolder.ready(); // Wake it up

        Machine.interrupt().restore(intStatus);



PRIORITY INVERSION AND DONATION

(using http://inst.eecs.berkeley.edu/~cs162-tc/pri)


Priority Scheduling

Priority scheduling is used to schedule which process or thread next uses the CPU. Priorities (usually integers) are assigned to each thread and among threads that are ready to run, the one with the highest priority is chosen next. The idea behind priority scheduling is that high priority threads are doing the work we want done first, while threads with lower priority can wait. Usually, threads are kept in a queue, sorted by their priorities so that the highest priority thread is "next" on the queue.

Priority Inversion

Suppose we have a shared resource. In order to prevent race conditions and inconsistencies, it makes sense to use a lock (mutex). Locks make sure that only one thread is accessing the resource at a time. If a thread wants to access a resource it must acquire the lock first. If it is unable to acquire the lock (in other words, another thread is using the resource), it must wait until the thread currently accessing the resource releases the lock.

Example: Thread A, with priority 1, has a lock. Thread C, with priority 3, is waiting on thread A, with priority 1. Thread B, with priority 2, will run before thread C.Threads A, B, and C have priority 1, 2, and 3, respectively.
Thread A is holding a lock on a resource that Thread C is wants to use. Thread C must wait for thread A to release the lock because it called acquire on the lock. Because thread C is waiting for the lock, it is not available to run. Thread A and B are ready to run. So when the priority scheduler chooses a thread to run next, it can only choose between A and B. B has a higher priority, so it will go next. Thread A cannot run, so it won't be able to release the lock and thread C will have to wait until B finishes. In other words, the highest priority thread, thread C, is inadvertently being blocked from running by a lower priority thread, thread B.

Priority Donation

One solution to this problem is to donate priority. In the case we just looked at, if thread A had the same priority as thread C, it would not be blocked. So thread C "donates" its priority to thread A - thread A's priority effectively becomes 3

Continues example of priority donation. Thread C, with priority 3, donates its priority to thread A, with real priority 1. Thread A may now run.

When thread A releases the lock, its priority drops down again to its original priority. Thread C is now able to run and the priorities behave as we intended.

After priority donation. Thread C, with priority 3, is now able to run and thread A's priority dropped back down to 1.




Monitors
--------

• CVs + locks

    • Mesa vs Hoare Condition variables

• H2O example

    • Need 2 hydrogen threads + 1 oxygen thread to produce water molecule

    • Problems:
        • Starvation
        • Deadlock 
        • State variables accessed outside critical section

T/F
Every condition variable is associated with some lock?
    True.

Multiple condition variables may not be associated with the same lock?
    False.

Condition.sleep, wake, wakeAll can be used without holding associated lock?
    False.

Can a thread wait for access to one object while having access to another?
   True.

What does condition.sleep() do?
     - atomically release the lock and relinkquish the CPU until woken; then reacquire the lock.

What does condition.wake() do? condition.wakeAll()?
     - wake() wakes up a single thread sleeping in 'this' condition variable, if possible.
     - wakeAll() wakes up all threads sleeping in 'this' condition variable.

Whats the difference between Mesa-style condition variables and
Hoare style condition variables? What does nachos use?
What is the advantage/disadvantage?

      - Mesa-style condition variables define wake() to wake up another thread and place woken thread on the ready queue. It is the responsibility of the woken thread to reacquire the lock (this reacquire is taken care of in sleep()).

      By contrast, Hoare-style condition variables define wake() to wake up another thread, give it the lock, and place directly on the CPU (i.e. woken thread runs immediately.

      Nachos uses Mesa-style semantics.

      The consequence of using Mesa-style semantics is that some other thread can acquire the lock and change data structures, before the woken thread gets a chance to run. The advance to Mesa-style semantics is that it is a lot easier to implement.

   * Monitors
        - Use locks to provide mutual exclusion and condition variables to synchronize.
        - Monitor encapsulates a lock and one or more condition variables.
        - Condition Varibles are like queue, with sleep resembling enqueue and wake resembling dequeue.
        - Only the lock holder can call sleep() or wake()/wakeAll()
            - Thus sleep() must atomically realease the lock before going to sleep.
        - when sleep returns the thread must have reaccquired the lock.

Mesa vs. Hoare Monitors

Hoare-style (most textbooks):

Signaler gives lock, CPU to waiter; waiter runs immediately
Waiter gives up lock, processor back to signaler when it exits critical section or if it waits again

Mesa-style (Nachos, most real operating systems):

Signaler keeps lock and processor
Waiter placed on ready queue with no special priority
Practically, need to check condition again after wait

Complete Monitor Example (Infinite synchronized queue)

Lock lock;
Condition dataready;
Queue queue;
AddToQueue(item) {

    lock.Acquire(); // Get Lock

    queue.enqueue(item); // Add item

    dataready.signal(); // Signal any waiters

    lock.Release(); // Release Lock

}
RemoveFromQueue() {

    lock.Acquire(); // Get Lock

    while (queue.isEmpty()) {

      dataready.wait(&lock); // If nothing, sleep

    }

    item = queue.dequeue(); // Get next item

    lock.Release(); // Release Lock

    return(item);

}

--------------------------------------------------------------------------
   Producers and Consumers using Condition Variables
--------------------------------------------------------------------------

Lock lock;
Condition wantToAdd = new Condition(lock);
Condition wantToTake = new Condition(lock);

Producer() {
    lock.acquire();
    while (numCokes == MAXCOKES) { // Like a semaphore.P()
      wantToAdd.sleep(); // Lock released!
    }
    numCokes++;   // Lock reacquired!
    wantToTake.wakeAll();          // Like a semaphore.V()
    lock.release();
}

Consumer() {
    lock.acquire();
    while (numCokes == 0) {        // Like a semaphore.P()
      wantToTake.sleep(); // Lock released!
    }
    numCokes--; // Lock reacquired
    wantToAdd.wakeAll();           // Like a semaphore.V()
    lock.release();
}

- This is much nicer
- Question: What if we changed 'wakeAll()' to 'wake()' in the above?
- Answer: Would have to wait for another producer or consumer
    to come around before the next producer or consumer would wake up!
- Note that we're really building "semaphores" when we do it this way!
- So different synchronization primitives are more useful or convenient
in different situations.

    Nachos :: Condition.java

    public void sleep() {
        Lib.assert(conditionLock.isHeldByCurrentThread());

        Semaphore waiter = new Semaphore(0);
        waitQueue.add(waiter);

        conditionLock.release();
        waiter.P();
        conditionLock.acquire();
     }

     public void wake() {
    Lib.assert(conditionLock.isHeldByCurrentThread());

    if (!waitQueue.isEmpty())
        ((Semaphore) waitQueue.removeFirst()).V();
      }

Sections
--------

• Fundamental insight in computer science: code == data

    • Machine cares not whether 32bits in memory represent integer or float or
      code!

    • But matters for efficiency -- running multiple copies of one program

        • Remember Play vs Script?

• Sections in unix:
    • Code
    • Data
    • BSS = initialized data


Compiling & running
-------------------

    foo.c:
        main() { printf("Meaning of life = %d\n", bar()); }

    bar.c:
        bar() { return 6*7; }

    1. gcc -o foo.o -c foo.c
    2. gcc -o bar.o -c bar.c
    3. gcc -o foobar.exe foo.o bar.o


• Steps 1,2: compiling
     
    • How does compiler know at step 1 how to generate code?
     
        • Placeholder for "bar" (undefined external symbol)

    • If the location of bar() in memory is unknown during step 2, how to
      generate addresses even within bar.c?
        • -> Relative addresses

• Step 3: linking

    • Fix placeholders

    • Calculate addresses

    • Re-order sections (e.g. put all data sections first)

        • Draw: [foo.data,bar.data,foo.code,bar.code]