CMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)1CMSC433, Fall 2002Programming Language Technology and ParadigmsThreads and SynchronizationMichael HicksCMCS 433, Fall 2002 -Michael Hicks2Overview•What are threads?•Thread scheduling, data races, and synchronization•Thread mechanisms in JavaCMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)2CMCS 433, Fall 2002 -Michael Hicks3Computation AbstractionsCPU 1 CPU 2p3p1 p2 p2t1t2t1t2t3t1t4t5A computerProcesses(e.g. JVM’s)ThreadsCMCS 433, Fall 2002 -Michael Hicks4Processes vs. Threadsintx;foo() {…x…}intx;foo() {…x…}int x;foo() {…x…}foo() {…x…}Processes do notshare dataThreads share datawithin a processCMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)3CMCS 433, Fall 2002 -Michael Hicks5So, what is a thread?•Conceptually: it is a parallel computation occurring within a process•Implementation view: it’s a program counter and a stack. The heap and static area are shared among all threads•All programs have at least one threadCMCS 433, Fall 2002 -Michael Hicks6Why multiple threads?•Performance:–Parallelism on multiprocessors–Concurrency of computation and I/O•Can easily express some programming paradigms–Event processing–Simulations•Keep computations separate, as in an OS– Java OSCMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)4CMCS 433, Fall 2002 -Michael Hicks7Programming Threads•Most languages have threads–C, C++, ObjectiveCaml, Java, SmallTalk …•The thread API differs with each, but most have the basic features we will now presentCMCS 433, Fall 2002 -Michael Hicks8Thread Applications•Web browsers–one thread for I/O–one thread for each file being downloaded–one thread to render web page•Graphical User Interfaces (GUIs)–Have one thread waiting for each important event, like key press, button press, etc.CMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)5CMCS 433, Fall 2002 -Michael Hicks9Thread Scheduling•OS schedules a single-threaded process on a single processor•Multithreaded process scheduling:–One thread per processor•Effectively splits a process across CPU’s•Exploits hardware-level concurrency–Many threads per processor•Need to share CPU in slices of timeCMCS 433, Fall 2002 -Michael Hicks10Scheduling Example (1)CPU 1CPU 2p1p2p1p2One process per CPUp2 threads:p1 threads:CMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)6CMCS 433, Fall 2002 -Michael Hicks11Scheduling Example (2)CPU 1CPU 2p1p2p1p2Threads shared between CPU’sp2 threads:p1 threads:CMCS 433, Fall 2002 -Michael Hicks12Scheduling Consequences•Concurrency– Different threads from the same application can be running at the sametimeon different processors•Interleaving–Threads can be “pre-empted” at any timein order to schedule other threadsCMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)7CMCS 433, Fall 2002 -Michael Hicks13Data Races•Data shared between threads can become corrupted due to “inopportune” scheduling of the sharing threads. These are called “data races.”•Therefore need to selectively control the scheduler to avoid such data accesses. This is usually done via synchronization.CMCS 433, Fall 2002 -Michael Hicks14Data Race Exampleint cnt= 0;void thread1() {int y = cnt;cnt= y + 1;}void thread2() {int y = cnt;cnt= y + 1;}cnt= 0Start: both threads ready torun. Each will increment theglobal count. Shared stateCMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)8CMCS 433, Fall 2002 -Michael Hicks15Data Race Exampleint cnt= 0;void thread1() {int y = cnt;cnt= y + 1;}void thread2() {int y = cnt;cnt= y + 1;}cnt= 0Thread1 executes, grabbingthe global counter value into y.Shared statey = 0CMCS 433, Fall 2002 -Michael Hicks16Data Race Exampleint cnt= 0;void thread1() {int y = cnt;cnt= y + 1;}void thread2() {int y = cnt;cnt= y + 1;}cnt= 0Thread1 is pre-empted. Thread2executes, grabbing the globalcounter value into y.Shared statey = 0y = 0CMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)9CMCS 433, Fall 2002 -Michael Hicks17Data Race Exampleint cnt= 0;void thread1() {int y = cnt;cnt= y + 1;}void thread2() {int y = cnt;cnt= y + 1;}cnt = 1Thread2 executes, storing theincremented cnt value.Shared statey = 0y = 0CMCS 433, Fall 2002 -Michael Hicks18Data Race Exampleint cnt= 0;void thread1() {int y = cnt;cnt= y + 1;}void thread2() {int y = cnt;cnt= y + 1;}cnt = 1Thread2 completes. Thread1Executes again, storing theold counter value (1) ratherthan the new one (2)!Shared statey = 0y = 0CMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)10CMCS 433, Fall 2002 -Michael Hicks19What happened?•Thread1 was preempted after it read the counter but before it stored the new value.•A particular way in which the execution of two threads is interleaved is called a schedule. We want to prevent this undesirable schedule.•Undesirable schedules can be hard to reproduce, and so hard to debug.CMCS 433, Fall 2002 -Michael Hicks20Applying synchronizationint cnt = 0;lock l;void thread1() {synchronized(l) {int y = cnt;cnt = y + 1;}}void thread2() {synchronized(l) {int y = cnt;cnt = y + 1;}}cnt= 0Shared stateLock, for protecting theshared stateAcquiresthe lock; onlysucceeds if not held byanother threadReleasesthe lockCMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)11CMCS 433, Fall 2002 -Michael Hicks21Applying synchronizationint cnt = 0;lock l;void thread1() {synchronized(l) {int y = cnt;cnt = y + 1;}}void thread2() {synchronized(l) {int y = cnt;cnt = y + 1;}}cnt= 0Shared stateThread1 acquires lock lCMCS 433, Fall 2002 -Michael Hicks22Applying synchronizationint cnt = 0;lock l;void thread1() {synchronized(l) {int y = cnt;cnt = y + 1;}}void thread2() {synchronized(l) {int y = cnt;cnt = y + 1;}}cnt= 0Shared stateThread1 readscnt into yy = 0CMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)12CMCS 433, Fall 2002 -Michael Hicks23Applying synchronizationint cnt = 0;lock l;void thread1() {synchronized(l) {int y = cnt;cnt = y + 1;}}void thread2() {synchronized(l) {int y = cnt;cnt = y + 1;}}cnt= 0Shared stateThread1 is pre-empted.Thread2 attempts toacquire lock 1 but failsbecause it’s held byThread1, so it blocksy = 0CMCS 433, Fall 2002 -Michael Hicks24Applying synchronizationint cnt = 0;lock l;void thread1() {synchronized(l) {int y = cnt;cnt = y + 1;}}void thread2() {synchronized(l) {int y = cnt;cnt = y + 1;}}cnt = 1Shared stateThread1 runs, assigningto cnty = 0CMSC 433, Alan Sussman, U. Maryland (via Bill Pugh)13CMCS 433, Fall 2002 -Michael Hicks25Applying synchronizationint cnt =
View Full Document
Unlocking...