
|
|
7. 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.
- Ensuring Safety and Liveness.
A more detailed version of this section is available in Threads.
- 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 Thread functions:
- DosCreateThread
- DosSuspendThread
- DosResumeThread
- DosWaitThread
- DosKillThread
- DosExit
- 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
- 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
- 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.
- DosGetInfoBlocks - Used to check thread priority.
- DosSetPriority - Used to change the priority of a thread.
- DosEnterCritSec - Starts critical section.
- DosExitCritSec - Ends critical section.
- 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.
- 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).
- 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.
- 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.)
- 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.
- Provides a way to wait for
- Any of multiple Events or Mutexes.
- All of a group of Events or Mutexes.
- 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.
- Much simpler
- "Least Common Denominator"
- Still very powerful.
- 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
}
}
- 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();
- 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);
}
}
- 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();
}
}
- 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.
- Interference:
- Corruption.
- Sequence issues.
- Overlapping resource access.
- Liveness:
- 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.
- 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.
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();
}
}
- 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();
}
- Caught incompletely-updated:
- inc() interrupted
making data all 8s,
dump() prints.
- dump() prints data[0],
inc() interrupts to
update data.
- 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();
}
}
- 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--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.
- 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");
- 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.
- 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;
- 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.
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();
}
}
- 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!!
- 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.
- 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);
}
}
- 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.
- 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.
- Many basic thread operations have a direct counterpart.
- Thread communication/synchronization is different.
- A "general" solution was selected.
- 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()
- DosWaitThread
t.join()
- DosKillThread
t.stop()
- DosExit
System.exit(); // stops application
/***** OR *****/
/* just let run to end of run() */
- DosGetInfoBlocks
t.getPriority()
- DosSetPriority
t.setPriority()
- DosEnterCritSec -- use synchronized sections
- DosExitCritSec -- automatic at end of synchronized section
- 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
|