Programming Language Basics
Programming Language Basics Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit
Computer Science isn’t really About Programming
Art of Multiprocessor Programming 2 Computer Science isn’t really About Programming • Any more than – Astronomy is about telescopes – French Literature is about unfiltered cigarettes
Nevertheless
Art of Multiprocessor Programming 3 Nevertheless • We need a programming language to state algorithms • We use Java – High-level • Sometimes a little too high level – Most of you have seen it before • And may see it again
Other Languages
Art of Multiprocessor Programming 4 Other Languages • PThreads – C and C++ • C# • MPI • Etc…
Threads
Art of Multiprocessor Programming 5 Threads • Execution of a sequential program • You can tell a thread – What to do – When to start • You can – Wait for it to finish • Other stuff: – Interrupt it, give it priority, etc.
Threads in Java
Art of Multiprocessor Programming 6 Threads in Java • Class java.lang.Thread • Each thread has a method – Void run() • Executes when it starts • Thread vanishes when it returns • You must provide this method
Creating a Thread
Art of Multiprocessor Programming 7 Creating a Thread • Create a Runnable object – Runnable is an interface – Provides run() method • Pass Runnable object to thread constructor
A Runnable Class
Art of Multiprocessor Programming 8 A Runnable Class public class Hello implements Runnable { String message; public Hello(m) { message = m; } public void run() { System.out.println(message); } }
A Runnable Class
Art of Multiprocessor Programming 9 A Runnable Class public class Hello implements Runnable { String message; public Hello(m) { message = m; } public void run() { System.out.println(message); } } Runnable interface
Creating a Thread
Art of Multiprocessor Programming 10 Creating a Thread String m = “Hello from ” + i; Runnable h = new Hello(m); Thread t = new Thread(h);
Creating a Thread
Art of Multiprocessor Programming 11 Creating a Thread String m = “Hello from ” + i; Runnable h = new Hello(m); Thread t = new Thread(h); Create a Runnable object
Creating a Thread
Art of Multiprocessor Programming 12 Creating a Thread String m = “Hello from ” + i; Runnable h = new Hello(m); Thread t = new Thread(h); Create the thread
Syntactic Help
Art of Multiprocessor Programming 13 Syntactic Help • Defining a single-use class like Hello can be a nuisance • Java provides special syntax • Anonymous inner classes – May be more trouble than it’s worth – You should recognize it
Anonymous Inner Class
Art of Multiprocessor Programming 14 Anonymous Inner Class t = new Thread( new Runnable() { public void run() { System.out.println(m); } } );
Anonymous Inner Class
Art of Multiprocessor Programming 15 Anonymous Inner Class t = new Thread( new Runnable() { public void run() { System.out.println(m); } } ); Creates object of anonymous Runnable class
Anonymous Inner Class
Art of Multiprocessor Programming 16 Anonymous Inner Class t = new Thread( new Runnable() { public void run() { System.out.println(m); } } ); Calls Thread constructor with anonymous object
Starting a Thread
Art of Multiprocessor Programming 17 Starting a Thread • Starts the new thread • Caller returns immediately • Caller & thread run in parallel t.start();
Joining a Thread
Art of Multiprocessor Programming 18 Joining a Thread • Blocks the caller • Waits for the thread to finish • Returns when the thread is done t.join();
Monitors
Art of Multiprocessor Programming 19 Monitors • Each object has an implicit lock • Managed by synchronized modifer – Methods – Code blocks • OK for easy cases • Not always for hard cases
Call Center Scenario
Art of Multiprocessor Programming 20 Call Center Scenario • Calls arrive faster than they can be answered – Play recorded message • “your call is very important to us …” – Put call in queue • Play insipid music … – Operators dequeue call when ready
Bad Queue Implementation
Art of Multiprocessor Programming 21 Bad Queue Implementation class Queue<T> { int head = 0, tail = 0; T[] items = new T[QSIZE]; public enq(T x) { items[(tail++) % QSIZE] = x; } public T deq() { return items[(head++) % QSIZE] }}
Bad Queue Implementation
Art of Multiprocessor Programming 22 class Queue<T> { int head = 0, tail = 0; T[] items = new T[QSIZE]; public enq(T x) { items[(tail++) % QSIZE] = x; } public T deq() { return items[(head++) % QSIZE] }} Bad Queue Implementation Works for generic type T
Bad Queue Implementation
Art of Multiprocessor Programming 23 class Queue<T> { int head = 0, tail = 0; T[] items = new T[QSIZE]; public enq(T x) { items[(tail++) % QSIZE] = x; } public T deq() { return items[(head++) % QSIZE] }} Bad Queue Implementation Array of T items
Bad Queue Implementation
Art of Multiprocessor Programming 24 class Queue<T> { int head = 0, tail = 0; T[] items = new T[QSIZE]; public enq(T x) { items[(tail++) % QSIZE] = x; } public T deq() { return items[(head++) % QSIZE] }} Bad Queue Implementation next slot to dequeue, 1 st empty slot
Bad Queue Implementation
Art of Multiprocessor Programming 25 class Queue<T> { int head = 0, tail = 0; T[] items = new T[QSIZE]; public enq(T x) { items[(tail++) % QSIZE] = x; } public T deq() { return items[(head++) % QSIZE] }} Bad Queue Implementation Put in empty slot, advance head
Of course, this doesn’t work
Art of Multiprocessor Programming 26 Of course, this doesn’t work head
Mutual Exclusion
Art of Multiprocessor Programming 27 Mutual Exclusion • Only one thread modifying queue fields at a time • Use synchronized methods – Locks object on call – Releases lock on return
Mutual Exclusion
Art of Multiprocessor Programming 28 Mutual Exclusion head
Synchronized Method
Art of Multiprocessor Programming 29 Synchronized Method class Queue<T> { … public synchronized enq(T x) { items[(tail++) % QSIZE]; } ... }
Synchronized Method
Art of Multiprocessor Programming 30 Synchronized Method class Queue<T> { … public synchronized enq(T x) { items[(head++) % QSIZE]; } ... } Lock acquired on entry, released on exit
Syntactic Sugar
Art of Multiprocessor Programming 31 Syntactic Sugar class Queue<T> { … public enq(T x) { synchronized ( this ) { items[(tail++) % QSIZE]; } } ... }
Syntactic Sugar
Art of Multiprocessor Programming 32 Syntactic Sugar class Queue<T> { … public enq(T x) { synchronized ( this ) { items[(tail++) % QSIZE]; } } ... } Same meaning, more verbose
Vocabulary
Art of Multiprocessor Programming 33 Vocabulary • A synchronized method locks the object • No other thread can call another synchronized method for that same object • Code in middle is critical section
Re-entrant Locks
Art of Multiprocessor Programming 34 Re-entrant Locks • What happens if you lock the same object twice? – In Java, no deadlock – Keeps track of number of times locked and unlocked – Unlock occurs when they balance out
Still Doesn’t Work
Art of Multiprocessor Programming 35 Still Doesn’t Work class Queue<T> { … public synchronized enq(T x) { items[(tail++) % QSIZE] = x; } ... }
Still Doesn’t Work
Art of Multiprocessor Programming 36 Still Doesn’t Work class Queue<T> { … public synchronized enq(T x) { items[(tail++) % QSIZE] = x; } ... } What if the array is full?
Waiting
Art of Multiprocessor Programming 37 Waiting • What if – Enqueuer finds a full array? – Dequeuer finds an empty array? • Throw an exception? – What can caller do? – Repeated retries wasteful • Wait for something to happen
Waiting Synchronized Method
Art of Multiprocessor Programming 38 Waiting Synchronized Method class Queue<T> { … public synchronized enq(T x) { while (tail - head == QSIZE) {}; items[(tail++) % QSIZE] = x; } ... }
Waiting Synchronized Method
Art of Multiprocessor Programming 39 class Queue<T> { … public synchronized enq(T x) { while (tail - head == QSIZE) {}; items[(tail++) % QSIZE] = x; } ... } Waiting Synchronized Method Spin while the array is full
Deadlock
Art of Multiprocessor Programming 40 Deadlock • Enqueuer is – Waiting for a dequeuer – While holding the lock • Dequeuer – Waiting for enqueuer to release lock • Nothing will ever happen
Waiting Thread
Art of Multiprocessor Programming 41 Waiting Thread • Release lock while waiting • When “something happens” – Reacquire lock – Either • Rerelease lock & resume waiting • Finish up and return
Styles of Waiting
Art of Multiprocessor Programming 42 Styles of Waiting • Spinning – Repeatedly retest condition • Blocking – Ask OS to run someone else
Styles of Waiting
Art of Multiprocessor Programming 43 Styles of Waiting • Spinning – Good for very short intervals – Expensive to call OS – Works only on multiprocessors! • Blocking – Good for longer intervals – Processor can do work • Clever libraries sometimes mix
The wait() Method
Art of Multiprocessor Programming 44 The wait() Method • Releases lock on q • Sleeps (gives up processor) • Awakens (resumes running) • Reacquires lock & returns q.wait();
The wait() Method
Art of Multiprocessor Programming 45 The wait() Method class Queue<T> { … public synchronized enq(T x) { while (tail – head == QSIZE) { wait(); }; items[(head++) % QSIZE] = x; } ... }
Waiting Synchronized Method
Art of Multiprocessor Programming 46 class Queue<T> { … public synchronized enq(T x) { while (tail – head == QSIZE) { wait(); }; items[(head++) % QSIZE] = x; } ... } Waiting Synchronized Method Keep retesting condition
Waiting Synchronized Method
Art of Multiprocessor Programming 47 class Queue<T> { … public synchronized enq(T x) { while (tail – head == QSIZE) { wait(); }; items[(head++) % QSIZE] = x; } ... } Waiting Synchronized Method Keep retesting condition Release lock & sleep
Wake up and Smell the Coffee
Art of Multiprocessor Programming 48 Wake up and Smell the Coffee • When does a waiting thread awaken? – Must be notified by another thread – when something has happened • Failure to notify in a timely way is called a “ lost wakeup ”
The wait() Method
Art of Multiprocessor Programming 49 The wait() Method • Awakens one waiting thread • Which will reacquire lock & returns q.notify();
The wait() Method
Art of Multiprocessor Programming 50 The wait() Method • Awakens all waiting threads • Which will reacquire lock & return q.notifyAll();
The wait() Method
Art of Multiprocessor Programming 51 The wait() Method public synchronized enq(T x) { while (tail - head == QSIZE) { wait(); }; items[(head++) % QSIZE] = x; if (tail-head == QSIZE-1) { notify(); } }
The wait() Method
Art of Multiprocessor Programming 52 public synchronized enq(T x) { while (tail - head == QSIZE) { wait(); }; items[(head++) % QSIZE] = x; if (tail-head == QSIZE-1) { notify(); } } The wait() Method Wait for empty slot
The wait() Method
Art of Multiprocessor Programming 53 public synchronized enq(T x) { while (tail - head == QSIZE) { wait(); }; items[(head++) % QSIZE] = x; if (tail-head == QSIZE-1) { notify(); } } The wait() Method Stuff item into array
The wait() Method
Art of Multiprocessor Programming 54 public synchronized enq(T x) { while (tail - head == QSIZE) { wait(); }; items[(head++) % QSIZE] = x; if (tail-head == QSIZE-1) { notify(); } } The wait() Method If the queue was empty, wake up a dequeuer
Lost Wakeup
Art of Multiprocessor Programming 55 Lost Wakeup • This code has a lost wakeup bug • Possible to have – Waiting dequeuer – Non-empty queue • Because not enough threads awakened
Empty queue, waiting dequeuers
Art of Multiprocessor Programming 56 Empty queue, waiting dequeuers Zzz … Zzz …
Enqueuer puts item in queue
Art of Multiprocessor Programming 57 Enqueuer puts item in queue Zzz … Zzz …
Since queue was empty, wakes dequeuer
Art of Multiprocessor Programming 58 Since queue was empty, wakes dequeuer Zzz … Ouch! notify() this!
1st Dequeuer slow, overtaken by enqueuers
Art of Multiprocessor Programming 59 1 st Dequeuer slow, overtaken by enqueuers Zzz … Must have coffee …
1st Dequeuer finishes
Art of Multiprocessor Programming 60 1 st Dequeuer finishes Zzz …
Solutions
Art of Multiprocessor Programming 61 Solutions • Don’t write buggy code d’oh! • Always call notifyAll() • Can also use timed waits – Wake up after specified time
Thread-Local Data
Art of Multiprocessor Programming 62 Thread-Local Data • In many of our examples we assume – Threads have unique ids – In range 0,…,n-1 • Where do they come from? – Long-lived data – Unique to a thread
Thread-Local Data in Java
Art of Multiprocessor Programming 63 Thread-Local Data in Java • ThreadLocal<T> class • No built-in language support • Library classes – Syntax is awkward – Very useful anyway
ThreadLocal methods
Art of Multiprocessor Programming 64 ThreadLocal methods • Changes calling thread’s version of object • Other threads’ versions unaffected ThreadLocal<T> local; T x = …; local.set(x);
ThreadLocal methods
Art of Multiprocessor Programming 65 ThreadLocal methods • Returns calling thread’s version of object ThreadLocal<T> local; T x = local.get();
Initializing ThreadLocals
Art of Multiprocessor Programming 66 Initializing ThreadLocals • Called by get() method the first time the thread-local variable is accessed. T x = local.initialValue();
Example
Art of Multiprocessor Programming 67 Example • Return unique thread id • Take a number first time called int me = ThreadID.get()
Thread-Local IDs
Art of Multiprocessor Programming 68 Thread-Local IDs public class ThreadID { static volatile int nextID = 0; private static LocalID threadID = new LocalID(); public static int get() { return threadID.get(); } … // define LocalID here }
Thread-Local IDs
Art of Multiprocessor Programming 69 Thread-Local IDs public class ThreadID { static volatile int nextID = 0; private static LocalID threadID = new LocalID(); public static int get() { return threadID.get(); } … // define LocalID here } Next ID to assign
Thread-Local IDs
Art of Multiprocessor Programming 70 Thread-Local IDs public class ThreadID { static volatile int nextID = 0; private static LocalID threadID = new LocalID(); public static int get() { return threadID.get(); } … // define LocalID here } Declare & initialize thead-local ID
Thread-Local IDs
Art of Multiprocessor Programming 71 Thread-Local IDs public class ThreadID { static volatile int nextID = 0; private static LocalID threadID = new LocalID(); public static int get() { return threadID.get(); } … // define LocalID here } Return value of thread-local ID
The Inner Class
Art of Multiprocessor Programming 72 The Inner Class static class LocalID extends ThreadLocal<Integer> { synchronized Integer initialValue() { return nextID++; } }
The Inner Class
Art of Multiprocessor Programming 73 The Inner Class static class LocalID extends ThreadLocal<Integer> { synchronized Integer initialValue() { return nextID++; } } Subclass of ThreadLocal<Integer>
The Inner Class
Art of Multiprocessor Programming 74 The Inner Class static class LocalID extends ThreadLocal<Integer> { synchronized Integer initialValue() { return nextID++; } } Overrides initialValue()
Summary
Art of Multiprocessor Programming 75 Summary • Threads – And how to control them • Synchronized methods – Wait, notify, and NotifyAll • Thread-Local objects
Art of Multiprocessor Programming 76   creativecommons.org/licenses/by-sa/2.5/ Creative Commons Attribution-ShareAlike 2.5 License . • You are free : – to Share — to copy, distribute and transmit the work – to Remix — to adapt the work • Under the following conditions : – Attribution . You must attribute the work to “The Art of Multiprocessor Programming” (but not in any way that suggests that the authors endorse you or your use of the work). – Share Alike . If you alter, transform, or build upon this work, you may distribute the resulting work only under the same, similar or a compatible license. • For any reuse or distribution, you must make clear to others the license terms of this work. The best way to do this is with a link to – http://creativecommons.org/licenses/by-sa/3.0/. • Any of the above conditions can be waived if you get permission from the copyright holder. • Nothing in this license impairs or restricts the author's moral rights.