CS61B Lecture #25Administrative:Today:• Threads• Communication between threads• Synchronization• Mailboxes• CoroutinesComing Up:Data Structures,Chapter 12, Graph Struc-turesLast modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 1Threads• So far, all our programs consist of single sequenceof instructions.• Each such sequence is called athread(for “threadof control”) in Java.• Java supports programs containingmultiplethreads,which (conceptually) run concurrently.• Actually, on a uniprocessor, only one thread at a timeactually runs, while others wait, but this is largelyinvisible.• To allow program access to threads, Java providesthe type Thread in java.lang. Each Thread containsinformation about, and controls, one thread.• Simultaneous access to data from two threads cancause chaos, so are also constructs for controlledcommunication, allowing threads tolockobjects, towaitto be notified of events, and tointerruptotherthreads.Last modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 2But Why?• Typical Java programs always have > 1 thread: be-sides the main program, others clean up garbage ob-jects, receive signals, and other stuff.• When programs deal with asynchronous events, issometimes convenient to organize into subprograms,one for each independent, related sequence of events,one for other things.• Threads allow us to insulate one such subprogramfrom another.• GUIs often organized like this: application is doingsome computation or I/O, another thread waits formouse clicks (like ‘Stop’), another pays attention toupdating the screen as needed.• And, of course, sometimesdohave a real multipro-cessor.Last modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 3Java Mechanics• To specify the actions “walking” and “chewing gum”:class Chewer1 implements Runnable {public void run () { while (true) ChewGum(); }}class Walker1 implements Runnable {public void run () { while (true) Walk(); }}• To walk and chew gum:Thread chomp = new Thread (new Chewer1 ());Thread clomp = new Thread (new Walker1 ());chomp.start (); clomp.start ();• Alternative:class Chewer2 extends Thread {// NOTE: Thread implements Runnable.public void run () { while (true) ChewGum(); }}class Walker2 extends Thread {public void run () { while (true) Walk(); }}----------------------------------------------------Thread chomp = new Chewer2 (), clomp = new Walker2 ();chomp.start (); clomp.start ();Last modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 4Avoiding Interference• When one thread has data for another, one mustwait for the other to be ready.• Likewise, if two threads use the same data struc-ture, generally only one should modify it at a time;other must wait.• E.g., what would happen if two threads simultane-ously inserted an item into a linked list at the samepoint in the list?• A: Both could conceivably executep.next = new ListCell(x, p.next);with thesamevalues of p and p.next; one insertionis lost.• Can arrange for only one thread at a time to executea method on a particular object with either ofvoid f (...) { | synchronized void f (...) {synchronized (this) { |body of fbody of f| }} |} |Last modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 5Communicating the Hard Way• Communicating data is tricky: the faster party mustwait for the slower.• Obvious approaches don’t work: suppose thread1 wantsto give data to thread2 by callingDataExchanger.putData (...):class DataExchanger {static volatile Object value;Object getData () {Object r; r = null;while (r == null) { r = value; }value = null;return r;}void putData (Object data) {while (value != null) { }value = data;}}• . . . and thread2 receives the data withDataExchanger.getData).•Lotsof ways this doesn’t work! One thread can mo-nopolize machine while waiting; two threads execut-ing getData or putData simultaneously cause chaos.Last modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 6Primitive Java Facilities• wait method on Object makes thread wait (not us-ing processor) until notified by notifyAll, unlockingthe Object while it waits.• E.g., ucb.util.mailbox has something like this (sim-plified):interface Mailbox {void deposit (Object msg) throws InterruptedException;Object receive () throws InterruptedException;}class QueuedMailbox implements Mailbox {private List queue = new LinkedList ();public synchronized void deposit (Object msg) {queue.add (msg);this.notifyAll (); // Wake any waiting receivers}public synchronized Object receive ()throws InterruptedException {while (queue.isEmpty ())wait ();return queue.remove (0);}}Last modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 7Message-Passing Style• Use of Java primitives very error-prone. Wait untilCS162.• We will just use mailboxes and be happy.• They allow the following sort of program structure:Mailbox#1Mailbox#2Player#1Player#2depositreceive depositreceiveinformation flow through Mailbox #1information flow through Mailbox #2• Where each Player is a thread that looks like thisif (IGoFirst ())myMove = computeMyMove ();while (!gameOver ()) {outBox.deposit (myMove);hisMove = inBox.receive ();myMove = computeMyMove (hisMove);}Last modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 8More Concurrency• Previous example can be done other ways, but mech-anism is very flexible.• E.g., suppose you want to think during opponent’smove:if (IGoFirst ())myMove = computeMyMove ();while (!gameOver ()) {outBox.deposit (myMove);hisMove = null;while (hisMove == null) {thinkAheadForAWhile ();hisMove = inBox.receiveIfPossible ();}myMove = computeMyMove (hisMove);}• receiveIfPossible doesn’t wait; returns null if nomessage yet.public synchronized Object receiveIfPossible ()throws InterruptedException {if (queue.isEmpty ())return null;return queue.remove (0);}Last modified: Tue Nov 13 18:11:02 2001 CS61B: Lecture #25 9Use In GUIs• Java library handles things like buttons in GraphicalUser Interfaces withcallbacks:JMenuItem item = new JMenuItem ("Quit");item.addActionListener (new ActionListener () {public void actionPerformed (ActionEvent e) {System.exit (0);}})• ActionListener, like Comparator, functions as a kindof lambda expression here. The above tells the sys-tem to exit the program whenever the user pushesa certain menu item labeled ‘Quit’.• Is a special thread that does nothing but wait foreventslike mouse clicks, pressed keys, mouse move-ment, etc., look to see if there is an ActionListenerwaiting for that
View Full Document
Unlocking...