CMSC 433 – Programming LanguageTechnologies and ParadigmsFall 2007Threads and SynchronizationOctober 11th, 2007(thanks to Doug Lea for some slides)2Overview• What are threads?– Concept– Basic Java mechanisms• Thread concerns– Safety and Liveness– Use of synchronization and signalling• Threading design patterns3Computation Abstractionsp3p1 p2 p4t1t2t1t2t3t1t4t5A computerProcesses(e.g., JVM’s)ThreadsCPU 1CPU 24Processes vs. Threadsint x;foo() {…x…}int x;foo() {…x…}int x;foo() { …x…}foo() { …x…}Processes do notshare dataThreads share datawithin a process5So, What Is a Thread?• Conceptually: it is a parallel computationoccurring within a process• Implementation view: it’s a programcounter and a stack. The heap and staticarea are shared among all threads• All programs have at least one thread(main)6Why Multiple Threads?• Performance:– Parallelism on multiprocessors– Concurrency of computation and I/O• Can easily express some programmingparadigms– Event processing– Simulations7Why Not Multiple Threads?• Complexity:– Dealing with safety, liveness, composition• Nondeterminism– Even with "correct" code, timing differencesmay result in different output each time it is run– Not necessarily bad, just makes it a pain to test8Programming Threads• Threads are available in many languages– C, C++, Objective Caml, Java, SmallTalk …• In many languages (e.g., C and C++),threads are a platform specific add-on– Not part of the language specification• Part of the Java language specification9Java Threads• Every application has at least one thread– The “main” thread, started by the JVM to runthe application’s main() method• The code executed by main() can createother threads– Explicitly, using the Thread class– Implicitly, by calling libraries that createthreads as a consequence• RMI, AWT/Swing, Applets, etc.10Java Threads: Creation• To explicitly create a thread– Instantiate a Thread object• An object of class Thread or a subclass of Thread– Invoke the object’s start() method• This will start executing the Thread’s run() methodconcurrently with the current thread– Thread terminates when its run() methodreturns11Scheduling Consequences• Concurrency– Different threads from the same application canbe running at the same time on differentprocessors• Interleaving– Threads can be pre-empted at any time inorder to schedule other threads12Thread Scheduling• When multiple threads share a CPU, must decide:– When the current thread should stop running– What thread to run next• A thread can voluntarily yield() the CPU– Call to yield may be ignored; don’t depend on it• Preemptive schedulers can de-schedule the currentthread at any time– Almost all JVMs use preemptive scheduling, but a few(embedded) JVM’s do not, so a thread stuck in a loopmay never yield by itself. Therefore, put yield() intoloops• Threads are de-scheduled whenever they block(e.g., on a lock or on I/O) or go to sleep13Thread Lifecycle• While a thread executes, it goes through anumber of different phases– New: created but not yet started– Runnable: is running, or can run on a free CPU– Blocked: waiting for I/O or on a lock– Sleeping: paused for a user-specified interval– Terminated: completed14Which Thread to Run Next?• The scheduler looks at all of the runnable threads,including threads that were unblocked because– A lock was released– I/O became available– They finished sleeping, etc.• Of these threads, it considers the thread’s priority.This can be set with setPriority(). Higher prioritythreads get preference.– Oftentimes, threads waiting for I/O are also preferred– But don’t depend on priority for correctness15Simple Thread Methods• void start()• boolean isAlive()• void setPriority(int newPriority)– Thread scheduler might respect priority• void join() throws InterruptedException– Waits for a thread to die/finish16Simple Static Thread Methods• void yield()– Give up the CPU• void sleep(long milliseconds)throws InterruptedException– Sleep for the given period• Thread currentThread()– Thread object for currently executing thread• All apply to thread invoking the method17Daemon Threads• void setDaemon(boolean on)– Marks thread as a daemon thread– Must be set before thread started• By default, thread acquires status of threadthat spawned it• Program execution terminates when nothreads running except daemons18Concurrency Issues• Threads allow concurrent activities, whichcan be both good and bad!• Two opposing design forces– Safety: “Nothing bad ever happens”– Liveness: “Something (useful) eventuallyhappens”• A safe system may not be live and a livesystem may not be safe. Balance is key.19Safe Objects• Perform actions only when in consistent states– Don’t want one thread to access an object while anotherthread is modifying its internal state.• This boils down to ensuring object invariants inthe face of concurrent access20Violating Safety• Data can be shared by threads– Scheduler can interleave or overlap threadsarbitrarily– Can lead to interference• Storage corruption (e.g., a data race/race condition)• Violation of representation invariant• Violation of a protocol (e.g., A occurs before B)21Data Race Examplepublic class Example extends Thread { private static int cnt = 0; // shared state public void run() { int y = cnt; cnt = y + 1; } public static void main(String args[]) { Thread t1 = new Example(); Thread t2 = new Example(); t1.start(); t2.start(); }}22Data Race Examplestatic int cnt = 0;t1.run() { int y = cnt; cnt = y + 1;}t2.run() { int y = cnt; cnt = y + 1;}cnt = 0Start: both threads ready torun. Each will increment theglobal count. Shared state23Data Race Examplestatic int cnt = 0;t1.run() { int y = cnt; cnt = y + 1;}t2.run() { int y = cnt; cnt = y + 1;}cnt = 0T1 executes, grabbingthe global counter value into y.Shared statey = 024Data Race Examplestatic int cnt = 0;t1.run() { int y = cnt; cnt = y + 1;}t2.run() { int y = cnt; cnt = y + 1;}cnt = 0T1 is pre-empted. T2executes, grabbing the globalcounter value into y.Shared statey = 0y = 025Data Race Examplestatic int cnt = 0;t1.run() { int y = cnt; cnt = y + 1;}t2.run() { int y = cnt; cnt = y + 1;}cnt = 1T2 executes, storing theincremented cnt value.Shared statey = 0y = 026Data Race Examplestatic int cnt =
View Full Document
Unlocking...