Concurrency Multiple simultaneous execution contexts Concurrency Want to walk and chew gum at the same time to COMS W4115 Prof Stephen A Edwards Spring 2002 Columbia University Department of Computer Science Capture simultaneity of system structure E g Web Servers must deal with multiple simultaneous independent requests Deal with independent physical devices The disk drive is delivering data while the network is delivering packets while the user is typing while Coroutines Basic idea run two routines concurrently and let them trade control Scan Pick up where you left off Scan control transfer Parse control transfer control transfer Parse Scan control transfer Increase performance Parse Split the problem into parts and solve each on a separate processor control transfer Coroutines Implementing Coroutines Faking Coroutines in C char c Languages such as C C Java don t have direct support returns 0 1 9 10 9 1 0 0 int count void scan c s transfer parse c a transfer parse c e transfer parse parse char buf 10 transfer scan buf 0 c transfer scan buf 1 c transfer scan buf 2 c control transfer Example Lexer parser int i Some libraries provide such a mechanism for i 0 i 10 i return i Challenge Each couroutine needs a separate stack Can be faked often done for i 10 i 0 i return i for return 0 Faking Coroutines in C Faking Coroutines in Java Cooperative Multitasking returns 0 1 9 10 9 1 0 0 int count static int state 0 static int i switch state case 0 for i 0 i 10 state 1 return i case 1 for i 10 i 0 state 2 return i case 2 for state 3 return 0 case 3 Harder because it insists on more structure Coroutines explicitly say when to context switch and who to run next program counter state use static not automatic vars i i class Corout int state 0 int i public int count switch state case 0 i 0 case 1 while i 10 state 1 return i i 10 case 2 while i 0 state 2 return i case 3 state 3 return 0 return 0 Programmer completely responsible for scheduling Alternative cooperative multitasking Programs explicitly release control to operating system Operating system responsible for deciding which program runs next Cooperative Multitasking Cooperative Multitasking Multiprogramming History Typical MacOS 10 or Windows 95 program Advantages First processors ran batch jobs resident monitor loads one program runs it then loads the next void main Magical Event e while e get next event QUIT switch e case CLICK break case DRAG break case DOUBLECLICK break case KEYDOWN break Multiprogramming Avoids I O busy waiting App 1 Disk read App 1 read complete App 1 Disk read I O completion triggers interrupt Disk write App 2 App 1 App 1 read complete App 3 write complete Three Threads on a Uniprocessor Thread 1 Context switch Thread 2 time Thread 1 Context switch Context switch Thread 2 Context switch Thread 3 Malicious process may never call get next event Context switch Solution Multiprogramming with interrupt driven I O Programmer needs to add calls to long executing event responses Programmer still partially responsible for scheduling Preemptive Multitasking Timesharing Idea give the OS the power to interrupt any process Model used on most modern operating systems e g Unix 1970s Windows Mac 2000s Programmer completely freed from thinking about scheduling never needs to say context switch System runs multiple threads Each a separate execution context registers stack memory Scheduler can enforce fairness no process may monopolize processor Single processor system has OS switch among threads Each imagines it is running on its own computer Heavyweight each process typically has own memory map switching costly Concurrent but not simultaneous execution Only one thread running at a time Gives the impression of simultaneity Inter program interaction now asynchronous program may be interrupted anywhere Concurrency Schemes Compared Coroutines Context switch Thread 3 Cheap to implement Disadvantages Disadvantages App 3 Interrupt causes context switch Problem I O was slow even by the standards of the time You re wasting expensive cycles waiting for the punch card reader Advantages App 2 Context switch on I O request Frees the programmer from worrying about which other processes are running Cooperative Multitasking Scheduler Fair Program No Cost Low Program OS No Medium Multiprogramming OS No Medium Preemptive Multitasking OS Yes High Java s Support for Concurrency Concurrency Support in Java Thread Basics Thread Basics Based on preemptive multitasking Creating a thread Threads and synchronization part of language class MyThread extends Thread public void run thread body A thread is a separate program counter with its own stack and local variables Model multiple program counters sharing a memory space Separate stacks All objects can be shared among threads Fundamentally nondeterministic but language provides some facilities for avoiding it Suspension The Sleep Method public void run for try sleep 1000 Pause for 1 second catch InterruptedException e return Caused by thread interrupt System out println Tick MyThread mt new MyThread Create the thread mt start Invoke run return immediately Sleep It is not an object the Thread class is just a way to start a thread A thread has no sense of ownership classes objects methods etc do not belong to any particular thread Any method may be executed by one or more threads even simultaneously Does this print Tick once a second No Races sleep delay is a lower bound In a concurrent world always assume something else is accessing your objects public void run Rest of the loop takes an for indeterminate amount of time try sleep 1000 catch InterruptedException e return System out println Tick Other threads are your adversary Consider what can happen when two threads are simultaneously reading and writing Thread 1 Thread 2 f1 a field1 a field1 1 f2 a field2 a field2 2 Thread 1 sees old values Thread 1 sees new values Thread 1 sees inconsistent values Thread 1 runs before Thread 2 Thread 1 runs after Thread 2 Execution of Thread 1 interrupts execution of Thread 2 Thread 1 Thread 1 Thread 2 1 f1 a field1 old value Thread 2 Thread 1 a field1 1 1 Thread 2 a field1 1 1 2 f1 a field1 1 2 f2 a field2 old value a field2 2 2 3 f2 a field2 old value a field1 1 3 3 f1 a field1 1 a field2 2 4 4 f2 a field2 2 a field2 2 4 Non atomic Operations Subtle Non atomic Operations Locks Making Things Atomic Biggest problem is the third case reader thread sees partially updated values Java assumes a 32 bit architecure Each object
View Full Document
Unlocking...