CS 162, Spring 2007

Section notes for 30 January 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

ADMINISTRIVIA

PROCESSES and THREADS


Multiprogramming 







• Supervisor/superuser bit
• How can programs access protected system services?
    • Syscalls / interrupts
• How can a CPU run multiple programs? 




    • Yielding vs time-slice - CPU support for preemptive multitasking
Thread Switch 
  1. Run thread
  2. Choose next thread
  3. Save state of current thread -> TCB
  4. Restore state to new thread <- TCB

Stack View:
ComputePi()
yield()
kernel_yield() <-- kernel space
run_new_thread()
switch()

Similar stack view for blocking on IO
CopyFile()
read()
kernel_read() <-- kernel space
run_new_thread()
switch()

And Interrupt:
ComputePi()
TimerInterruptHandler() <-- kernel space
run_new_thread()
switch()

• Little's formula: N = λ·F
  N = average users in system
  λ = arrival rate
  F = mean flow time
  (e.g. bandwidth-delay product in networks)
 
• Open/closed system
• Cooperating (to share resources and get speedup) vs independent processes
SCHEDULING
 
SCHEDULING SIMULATION!

• FCFS, RR (Q=2), SJF, SRPT (Q=2), SET (Q=2)

• Job, Arrival time, service time:
    A  1  1
    B  4  3
    C  6  5
    D 15 10
    E 19  6
    F 19  4
    G 20  1

• Calculate: flow time, service time - mean, std dev
SYNCHRONIZATION

- Issues with threads and concurrency (things to think about)
   - How to let threads interact safely? (SYNCHRONIZATION.)
     - I.e. two threads each writing to the same shared variable
     - How to avoid having one thread overwrite the other's value
        (i.e. T1 does: local := shared; local := f(local); shared := local;
          T2 does: local := shared; local := g(local); shared := local;
        RACE CONDITION: T1 writes new value of 'shared' while T2 computing
     g, so T2 writes 'shared' based on "old" value.)

- Critical Section, a piece of code that only one thread can execute at once. Only one thread at a time will get into the section of code.

- Synchronization Requirements
  - Mutual Exclusion, ensuring only one thread can execute in a critical section at a time
  - Progress, one thread must always be allowed to enter the  critical section
  - Bounded waiting, a thread should not wait indefinitely to enter its critical section

- Locks are used to implement mutual exclusion. All require some level of hardware support.

- Atomic operations are a set of instructions which execute as one uninterruptible unit. TestAndSet and Swap are atomic operations supported by most hardwares.

  /* returns the current value of lock and sets lock to true */
  TestAndSet(lock)
    TestAndSet = lock
    lock = true

  /* swaps two values
  Swap(local(i), lock)
    temp = lock;
    lock = local(i)
    local(i) = temp

Synchronization
---------------

• Critical section: abstract notion, lines of code
• Mutually exclusive lock

Atomicity
---------
• Single instructions
    • Load, store (32 bits on 32-bit processor)
    • Add, sub, xor, etc.

How to implement mutex lock?
----------------------------
• Need hardware support

• Atomic instructions: test&set, swap

    class Lock { 
        acquire() { ... }

        release() { ... }
    }

• Naive implementation:

    class Lock { 
        boolean flag = false;
        acquire() { while (flag == false) /* twiddle */; flag = true; }

        release() { flag = false; }
    }

    • What's wrong?

    class Lock { 
        boolean flag = false;
        acquire() { 
          start:
            if flag == false: // needs to be atomic
                goto start;
            flag = true;
        }

        release() { flag = false; }
    }

• Test&set:

    class Lock { 
        boolean flag = false;
        acquire() { 
          start:
            if tset(flag) == false: 
                goto start;
        }

        release() { flag = false; }
    }

    class Lock { 
        boolean flag = false;
        acquire() { 
          start:
            while (tset(flag)) { /* twiddle */ }
        }

        release() { flag = false; }
    }

    • Works

    • Busy waiting! => "spin lock"

• Disable interrupts

    class Lock { 
        acquire() { 
            disableInterrupts();
        }

        release() { 
            enableInterrupts();
        }
    }

    • How does this work?

    • Problems?

    • => only disableInterrupts for a SHORT time!
    • Other threads should be allowed to run if using different lock

• Final solution?

    • Use spinlock or interrupts-disabling to implement heavyweight but
      non-busy-waiting lock, that uses queues

    class Lock { 
        owner = null;
        waitQ = {};
        acquire() { 
            disableInterrupts();
            if (owner != null) {
                waitQ.add(currentThread());
                KThread.sleep();
            }
            enableInterrupts();
        }

        release() {
            disableInterrupts();
            if (waitQ.notEmpty()) 
                waitQ.pop().wake(); 
            enableInterrupts();
        }
    }