7. Threads


Threads

  • Review of OS/2 Threads & Semaphores
  • Thread introduction and basics.
    • Spawning a Thread.
    • Controlling Thread Execution.
  • Thread Safety.
    • Monitors.
    • Mutual Exclusion.
    • Condition Synchronization.
  • Thread Liveness.
    • Deadlock.
  • Ensuring Safety and Liveness.
A more detailed version of this section is available in Threads.

Thread Introduction

  • What's a Thread?
    • Single flow of control with separate stack.
    • Threads can have own local variables and make method calls.
    • Like multi-CPU computer.
    • Lightweight process.
  • What are threads good for?
    • Concurrent operations; background tasks, multi-client servers.
    • Simpler programs; responding to events, ...
    • High degree of control; "watchdog", ...
    • Exploiting parallelism.

OS/2 Threads and Semaphores

  • OS/2 Thread functions:
  • DosCreateThread
  • DosSuspendThread
  • DosResumeThread
  • DosWaitThread
  • DosKillThread
  • DosExit

DosCreateThread

  • Creates a new thread of execution
  • Accepts a function pointer as a parameter.
    • Will execute that function as the new thread of execution.
  • May be run immediately upon creation or may suspend based on parameter passed in.

DosSuspendThread / DosResumeThread

  • DosSuspendThread
    • Temporarily suspends a thread of execution.
  • DosResumeThread
    • Resumes a thread that has been suspended or starts a thread that was created in the seuspended state.

DosWaitThread / DosKillThread / DosExit

  • DosWaitThread
    • Causes the current thread of execution to wait for another thread to die before continuing to execute.
  • DosKillThread
    • Used by a thread to force other threads to terminate.
  • DosExit
    • Used by a thread that has run to completion.
    • If called by the main thread, causes the application to terminate.

Additional APIs

  • DosGetInfoBlocks - Used to check thread priority.
  • DosSetPriority - Used to change the priority of a thread.
  • DosEnterCritSec - Starts critical section.
  • DosExitCritSec - Ends critical section.

Semaphores

  • Like a traffic cop to restrict thread control
  • Three types:
    • Event Semaphores.
      • Blocks thread while waiting for an event to occur.
    • Mutex Semaphores
      • Insure that resource access is only allowed to one thread at a time.
    • MuxWait Semaphores.
      • Allow threads to be blocked by two or more Event or Mutex Semaphores.

Event Semaphores

  • One or more threads can block waiting for an event to occur.
  • When the event occurs, all waiting threads resume.
  • An Event Semaphore has two states: Reset (waiting) or Posted (occurred).

Event Semaphore APIs

  • DosCreateEventSem - Create an Event Semaphore.
  • DosOpenEventSem - Open an Event Semaphore so a thread can use it.
  • DosResetEventSem - Reset an Event Semaphore to wait for the next occurrence of an event.
  • DosPostEventSem - Notify the Event Semaphore that an event has occurred.
  • DosQueryEventSem - Check Event Semaphore state.
  • DosWaitEventSem - Wait for an Event Semaphore.
  • DosCloseEventSem - Close access to an Event Semaphore for all threads.

Mutex Semaphores

  • Associated with a shared resource
  • Threads request access to shared resource
  • Thread will block until resource is available.
  • When resource is available to requestor
    • Requstor is allowed to access it
    • Requestor is given exclusive access. (Other requestors on Mutex must wait.)

Mutex Semaphore APIs

  • DosCreateMutexSem - Create the data structures associated with a Mutex Semaphore.
  • DosOpenMutexSem - Open access to a Mutex Semaphore from a thread.
  • DosQueryMutexSem - Query the state of a Mutex Semaphore to see if it is available.
  • DosRequestMutexSem - Request access to the Mutex Semaphore and block while waiting.
  • DosReleaseMutexSem - Release a Mutex Semaphore when a thread is done with the resource.
  • DosCloseMutexSem - Close access to a Mutex Semaphore for all threads.

MuxWait Semaphores

  • Provides a way to wait for
    • Any of multiple Events or Mutexes.
    • All of a group of Events or Mutexes.

MuxWait Semaphore APIs

  • DosCreateMuxWaitSem - Create the data structures used by a MuxWait Semaphore.
  • DosOpenMuxWaitSem - Open access to a MuxWait Semaphore to a thread.
  • DosAddMuxWaitSem - Add an Event or Mutex Semaphore to the MuxWait Semaphore.
  • DosDeleteMuxWaitSem - Remove an Event or Mutex Semaphore from the MuxWait Semaphore.
  • DosQueryMuxWaitSem - Check the state of a MuxWait Semaphore.
  • DosCloseMuxWaitSem - Close access to a MuxWait Semaphore for all threads.

Java Threads

  • Much simpler
  • "Least Common Denominator"
  • Still very powerful.

Spawning a Thread

  • Make a runnable class:
    • Create your class, making it implement interface Runnable.
    • Define a method within your class with signature: public void run();
      class Animation implements Runnable {
        ...
        public void run() {
          // when this exits, thread dies
        }
      }
      

Spawning a Thread Continued...

  • Spawn a thread on an instance of that class.
    • Create an instance of your class.
    • Create a new thread attached to your new instance.
    • Start thread attached to your object.
      Animation a = new Animation();
      Thread t = new Thread(a);
      t.start();
      

Thread Example

  • Print strings simultaneously to standard out.
    class Jabber implements Runnable {
      String str;
      public Jabber(String s) { str = s; }
      public void run() {
        while (true) System.out.println(str);
      }
    }
    

Thread Example Continued...

  • Launch two threads on different Jabbers.
    class T {
      public static void main(String[] args) {
        Jabber j = new Jabber("MageLang");
        Jabber k = new Jabber("Institute");
        Thread t = new Thread(j);
        Thread u = new Thread(k);
        t.start();
        u.start();
      }
    }
    

Thread Control

  • suspend: suspend execution until start is called.
  • resume: Resume a suspended thread.
  • stop: Kill the thread.
  • join: Wait for a thread to die before continuing.
  • yield: Allow another thread to execute.
  • sleep(int n): sleep for n ms.

Problems With Threads

  • Interference:
    • Corruption.
    • Sequence issues.
    • Overlapping resource access.
  • Liveness:
    • Starvation.
    • Deadlock.

Thread Safety: Terminology

  • A thread can interrupt another in a critical section.
    • Bank deposit example.
    • Train semaphore example.
  • State is instantaneous value of all variables.
  • History is sequence of states.
  • Mutual exclusion constrains all possible histories to those with good states. We use synchronization to achieve exclusion.
  • Condition synchronization: wait for a state to become valid/correct.

Thread Safety and Java

  • Java thread mechanism based on monitors.
    • Chunk of data accessed only through mutually-exclusive accessors (routines).
    • Today, we call this an object.
  • Mutual exclusion in Java: synchronized methods have exclusive access to object data.
  • Condition synchronization in Java: wait and notifyAll methods.
  • Locks: A synchronized method acquires a lock on that object.
  • Atomic operations in Java: assignment to primitives except long and double.

Synchronization Example

    class IntArray {
      private int[] data = new int[10];
      public void inc() {
        for (int i=0; i<10; i++) data[i]++;
      }
      public void dump() {
        for (int i=0; i<10; i++)
          System.out.print(" "+data[i]);
        System.out.println();
      }
    }
    

Synchronization Example (continued)

  • Imagine a thread that tries to increment data.
    public void run() {
      while ( true ) ia.inc();
    }
    
  • Imagine another thread that tries to print data.
    public void run() {
      while ( true ) ia.dump();
    }
    

Synchronization Example (continued)

  • Caught incompletely-updated:
  • inc() interrupted making data all 8s, dump() prints.
  • dump() prints data[0], inc() interrupts to update data.

Solution 1

  • Synchronize the methods:
    class IntArray {
      private int[] data = new int[10];
      synchronized public void inc() {
        for (int i=0; i<10; i++) data[i]++;
      }
      synchronized public void dump() {
        for (int i=0; i<10; i++)
          System.out.print(" "+data[i]);
        System.out.println();
      }
    }
    

Solution 2

  • Synchronize the method invocations:
    public void run() {
      while ( true )
        synchronized(ia) ia.inc();
    }
    
    And:
    public void run() {
      while ( true )
        synchronized(ia) ia.dump();
    }
    

Synchronized Statements

  • Synchronized statements--lock an object during the execution of statement(s).
    synchronized (object-expr) statement
    
  • Says: "Heh, I'm working on this object. Don't play with it until I'm finished."

  • Locks out all other statements that are synchronized on that same object.

Per-Class Synchronization

  • Class methods can also be synchronized to prevent simultaneous access to class variables.
    class HPLaser {
      private static Device dev = ...;
      static synchronized void print(String s) {
        ...
      }
    }
    ...
    HPLaser.print("I'm trapped in this PC!");
    ...
    HPLaser.print("We're not in Kansas anymore");
    

Per-Class Synchronization Cont'd...

  • Instances all refer to class def object.

  • Class methods lock on class def object allowing us to generalize: all synchronized code is synchronized on a per-object basis.

Condition Synchronization

  • Delays execution until a condition is satisfied.
    • Wait until a thread finishes.
    • Or, state is valid again--safe to proceed.
    • Vs mutual-exclusion, which waits for lock.

  • What we want:
    await (condition) statement;
    

Condition Synchronization Cont'd...

  • What we got:
    while (!condition) wait();
    
    and
    notifyAll();
    
  • Use while-loop because:
    • No way to restrict notifyAll to a specific condition.
    • Another thread may have awakened beforehand and modified state.

Blocking Queue

    class BlockingQueue { // block until data available
        int n = 0;
        ...
        public synchronized Object read() {
            while (n==0) wait();
            // we have the lock!
            n--;
            ...
        }
        public synchronized void write(Object o) {
            ...
            n++;
            notifyAll();
        }
    }
    

Thread Liveness

  • Notion that your program won't lock up.

  • Probable causes:
    • Deadlock.
    • Unsatisfied wait condition(s).
    • Suspended thread not resumed.
    • Starvation.
    • Premature death.

  • Safety often conflicts with liveness!!

Deadlock

  • What causes it?
    • Thread 1 waiting for thread 2 to do something, but thread 2 is waiting for thread 1 to do something.

  • Classic problem: "Dining philosophers".
    • Five philosophers, five forks, lots of spaghetti, each philosopher needs 2 forks.
    • Deadlock: each philosopher picks up a fork, can't acquire the second.
    • One solution: have one philosopher pick up fork in other order.

Deadlock Example

  • Set of Cells running in different threads. Both try to execute line (*) at about same time. 1 will have exclusive control of itself while trying to get control of 2, while 2 will be in opposite situation.
    class Cell {
      private int value_;
      synchronized int  getvalue() { return value_; }
      synchronized void setValue(int v) { value_ = v; }
      synchronized void swapContents(Cell other) {
        int newValue = other.getValue(); // (*)
        other.setValue(getValue());
        setValue(newValue);
      }
    }
    

Thread Starvation

  • What is it?
    • A thread won't run even though nothing blocking it.
  • What causes it?
    • Running higher-priority threads don't yield.
    • Make sure you don't forget to notify().
  • Scheduling policies not defined! (portable?)
    • SUN: cooperative between threads at same priority.
      Preemptive between priority levels.
    • Win95: all threads are preemptively scheduled.

Ensuring Safety and Liveness

  • Testing. Test program in many different situations trying to catch incorrect behavior and deadlock.
  • Case analysis. "What would happen in this situation?"
  • Design patterns. Concurrent programming problems are fit into known patterns whose behaviors are well understood.
  • Formal proofs. Using predicates and axioms to describe program state and state transformations, proofs are constructed to establish correctness.

Converting OS/2 to Java

  • Many basic thread operations have a direct counterpart.
  • Thread communication/synchronization is different.
    • A "general" solution was selected.

Thread Manipulation

  • DosCreateThread
    Thread t = new MyThread();
      // requires subclass of Thread, override run()
      /***** OR *****/
    Thread t = new Thread(object);
      // requires object implement Runnable
    
    t.start();       
    
  • DosSuspendThread
    t.suspend()
    
  • DosResumeThread
    t.resume()
    

Thread Manipulation (continued)

  • DosWaitThread
    t.join()
    
  • DosKillThread
    t.stop()
    
  • DosExit
    System.exit();  // stops application
      /***** OR *****/
    /* just let run to end of run() */
    

Thread Manipulation (continued)

  • DosGetInfoBlocks
    t.getPriority()
    
  • DosSetPriority
    t.setPriority()
    
  • DosEnterCritSec -- use synchronized sections
  • DosExitCritSec -- automatic at end of synchronized section

Semaphores

  • Usually not a "simple" solution.
  • Need to think through intention.
  • Use things like:
    • wait()/notify()
    • synchronized blocks
      • Define a "lock" object that can act like a semaphore
    • AWT Event Handling

Copyright © 1996-1997 MageLang Institute. All Rights Reserved.