Unit 2b – Virtual Processors (Threads)

Irreproducible Interrupt Moments

I/O Devices Introduced Two Problems

1. Multiple active devices needed to cooperate with the CPU to provide services (e.g. read a disk block)

   • multiple active "sequential execution" streams, in the CPU and the controller

     • different from our original hardware model and the model presented by programming languages which was ONE sequential stream of instructions

   • communications with I/O devices is inherently asyncronous

2. I/O controllers had varying response times and the CPU can not simply wait

   • needed to be able to "multitask", and overlap the request and the response
   • programs may need to be arbitrarily interrupted to respond to the controllers

• Solutions was intterupts and more genenerally asyncronous, event-driven programming
• BUT, has difficulties

Difficulties of Asynchronous Programming

• If something has to happen event

  • it must be triggered by the event
  • often this means it must be part of (or called by) event's handler

• To print the checksum

 
xxxxxxxxxx
15
1
void computeChecksumAndPrint (char* buf, int blockNum, int numBytes) {
2
  int xsum = 0;
3
  for (int i = 0); i < numBytes; i++)
4
    xsum ^= buf [i];
5
  printf ("0x%1x\n", xsum);
6
  free (buf);
7
}
8
​
9
void checksum (blockNum, numBytes, whenComplete) {
10
  char* buf = malloc (numBytes);
11
  
12
  diskRead (buf, blockNum, numBytes, whenComplete);
13
}
14
​
15
void checksum (1234, 4096, computeAndPrintChecksum)

• Huge problem

  • often there's a ton of stuff that depend on returned data
  • that is, that must come after a particular event

Thread

• An abstraction for execution

  • looks to programmer like a sequential flow of execution; a private CPU
  • it can be stopped and started, it is sometimes running and sometimes not
  • the physical CPU thus now multiplexes multiple threads at different times

• Creating and starting a htread

  • like an asynchronous procedure call
  • starts a new thread of control to execute a procedure

• Stopping and re-starting a thread

  • stopping a thread is called blocking
  • a blocked thread can be re-started (i.e., unblocked)

• Joining with a thead

  • blocks the calling thread until a target thread completes
  • returns the return value of the target-threads starting procedure
  • turns thread create back into a synchronous procedure call

UThread: A Simple Thread System for C

• The UThread Interface file (uthread.h)

 
xxxxxxxxxx
8
1
void        uthread_init    (int num_processors);
2
uthread_t   uthread_create  (void* (*proc)(void*), void* arg);
3
void        uthread_detach  (uthread_t t);
4
void        uthread_join    (uthread_t t, void **vp);
5
uthread_t   uthread_self    ();
6
void        uthread_yield   ();
7
void        uthread_block   ();
8
void        uthread_unblock (uthread_t thread);

• Explained

  • uthread_t thread id data type

    • uthread_init is called once to initialize the thread system
    • uthread_create create and start a thread to run a specified procedure
    • uthread_yieldtemporarily stop current thread if other threads waiting
    • uthread_join join calling thread with specified other thread and get return value
    • uthread_detach indicate thread no thread will join specified thread
    • uthread_self a pointer to the TCB of the current thread
    • uthread_block block current thread
    • uthread_unblock unblock specified thread and make it runnable

Example Program Using UThreads

Give up CPU if there's another thread that can run (i.e., pong())'

 
xxxxxxxxxx
8
1
void* ping (void* v) {
2
  int i;
3
  for (i = 0; i < 100; i++) {
4
    printf("I");
5
    uthread_yield();
6
  }
7
  return 0;
8
}

Give up CPU if there's another thread that can run (i.e., ping())

 
xxxxxxxxxx
8
1
void* pong (void* v) {
2
  int i;
3
  for (i = 0; i < 100; i++) {
4
    printf("O");
5
    uthread_yield();
6
  }
7
  return 0;
8
}

Give up CPU to wait for ping() to return and thus its thread to finish

 
xxxxxxxxxx
8
1
void ping_pong () {
2
  uthread_t t0, t1;
3
  uthread_init(1);
4
  t0 = uthread_create(ping, 0);
5
  t1 = uthread_create(pong, 0);
6
  uthread_join(t0, 0);
7
  uthread_join(t1, 0);
8
}

Revisiting the Disk Read

• A program that reads a block from disk

  • want the disk read to be synchronous

   
  xxxxxxxxxx
  2
  1
  read            (buf, siz, blkNo);  // read siz bytes at blkNo into buf
  2
  nowHaveBlock    (buf, siz);         // now do something with the block
  

  • but, it is asynchronous so we have this

   
  xxxxxxxxxx
  2
  1
  asyncRead       (buf, siz, blkNo, nowHaveBlock);
  2
  doSomethingElse ();
  

• As a timeline

  • two processors
  • two separate computations

  

Synchronous Disk Read Using Threads

• Create two threads that CPU runs, one at a time

  • one for disk read
  • one for doSomethingElse

• Illusion of synchrony

  • disk read blocks while waiting for disk to complete
  • CPU runs other thread(s) while first thread is blocked
  • disk interrupt restarts the blocked thread

   
  xxxxxxxxxx
  3
  1
  asyncRead           (buf, siz, blkNo);
  2
  blockToWaitForInterrupt ();
  3
  nowHowBlock         (buf, siz);
  

   
  xxxxxxxxxx
  3
  1
  interruptHandler() {
  2
    unblockWaitingThread();
  3
  }
  

Recall Asyncronous Disk Read

We wanted to do this, but couldn't because risk reads are asyncronous...

We implemented it this way in event-driven programming style...

Hiding Asynchrony with Threads

Now we can do this...

We implemented it this way using threads to hide asynchrony...

Implementing Threads: Some Questions

• The key new thing is blocking and unblocking

  • what does it mean to stop a thread?
  • what happens to the thread?
  • what happens to the physical processor?

Data Structures

• Thread State

  • when running: register file and runtime stack
  • when stopped: Thread-Control-Block object and runtime stack

• Thread-Control Block (TCB)

  • thread status: (NASCENT, RUNNING, RUNNABLE, BLOCKED, or DEAD)
  • saved value of thread's stack pointer if its not running
  • scheduling parameters such as priority, quantum, preemptability etc.

• Ready Queue

  • list of TCB's of all RUNNABLE threads

• One or more Block Queues

  • list of TCB's of BLOCKED threads

Thread Scheduling

• Thread Scheduling is:

  • the process of deciding when threads should run
  • when there are more runnable threads than processors
  • involves a policy and a mechanism

• Thread Scheduling Policy

  • is the set of rules that determines which threads should be running

• Things you might consider when setting scheduling policy

  • do some threads have higher priority than others?
  • should threads get fair access to the processor?
  • should threads be guaranteed to make progress?
  • should one thread be able to pre-empty another?

Priority, Round-Robin Scheduling Policy

• Priority

  • is a number assigned to each thread
  • thread with highest priority goes first

• When choosing the next thread to run

  • run the highest priority runnable thread
  • when threads have the same priority, run thread that has waited the longest

• Implementing Thread Mechanism

  • organize Ready Queue as a priority queue

    • highest priority first
    • FIFO (first-in-first-out) among threads of equal priority

  • priority queue: first-in-first-out among equal-priority threads

Preemption

• Preemption occurs when

  • a "yield" is forced upon the current running thread
  • current thread is stopped to allow another thread to run

• Priority-based preemption

  • when a thread is made runnable (e.g., created or unblocked)
  • if it is higher priority than current-running thread, it preempts that thread

• Quantum-based preemption

  • each thread is assigned a runtime "quantum"
  • thread is preempted at the end of its quantum

• How long should quantum be?

  • disadvantage of being too short?
  • disadvantage of being too long?
  • typical value is around 100ms

Implementing Quantum Preemption

• The Problem

  • when application thread(s) are running, nothing is watching over them
  • for the system scheduler to control things it needs a CPU to run on
  • as long as the application threads are running, the system isn't

• Timer Devices

  • an I/O congtroller connected to a clock
  • interrupts processor at regular intervals

• Timer Interrupt Handler

  • compares the running time of current thread to its quantum
  • preempts it if quantum has expired

Summary

• Thread

  • synchronous "thread" of control in a program
  • virtual processor that can be stopped and started
  • threads are executed by real processor one at a time (per processor)

• Threads hide asyncrongy

  • by stopping to wait for interrupt/event, but freeing CPU to do other things

• Thread state

  • when running: stack and machine registers (register file etc.)
  • when stopped: Thread Control Block stores stack pointer, stack stores tate

• Round-robin, preemptive, priority thread scheduling

  • lower priority thread preempted by higher
  • thread preempted when its quantum expires
  • equal-priority threads get fair share of processor, in round-robin fashion