Concurrency COMS W4115 Prof Stephen A Edwards Spring 2002 Columbia University Department of Computer Science Concurrency Multiple simultaneous execution contexts Want to walk and chew gum at the same time to 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 Increase performance Split the problem into parts and solve each on a separate processor 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 control transfer Example Lexer parser Scan control transfer Parse control transfer Coroutines char c 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 Implementing Coroutines Languages such as C C Java don t have direct support Some libraries provide such a mechanism Challenge Each couroutine needs a separate stack Can be faked often done Faking Coroutines in C returns 0 1 9 10 9 1 0 0 int count int i for i 0 i 10 i return i for i 10 i 0 i return i for return 0 Faking Coroutines in C 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 program counter state use static not automatic vars i i Faking Coroutines in Java Harder because it insists on more structure 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 Cooperative Multitasking Coroutines explicitly say when to context switch and who to run next 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 Typical MacOS 10 or Windows 95 program 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 Cooperative Multitasking Advantages Frees the programmer from worrying about which other processes are running Cheap to implement Disadvantages Malicious process may never call get next event Programmer needs to add calls to long executing event responses Programmer still partially responsible for scheduling Multiprogramming History First processors ran batch jobs resident monitor loads one program runs it then loads the next Problem I O was slow even by the standards of the time You re wasting expensive cycles waiting for the punch card reader Solution Multiprogramming with interrupt driven I O Multiprogramming Avoids I O busy waiting App 1 Disk read App 2 Context switch on I O request App 1 read complete App 1 I O completion triggers interrupt Disk read App 3 Disk write Interrupt causes context switch App 2 App 1 App 1 read complete App 3 write complete Preemptive Multitasking Idea give the OS the power to interrupt any process Advantages Programmer completely freed from thinking about scheduling never needs to say context switch Scheduler can enforce fairness no process may monopolize processor Disadvantages Heavyweight each process typically has own memory map switching costly Inter program interaction now asynchronous program may be interrupted anywhere Timesharing Model used on most modern operating systems e g Unix 1970s Windows Mac 2000s System runs multiple threads Each a separate execution context registers stack memory Single processor system has OS switch among threads Each imagines it is running on its own computer Concurrent but not simultaneous execution Only one thread running at a time Gives the impression of simultaneity Three Threads on a Uniprocessor Thread 1 Context switch Thread 2 Thread 3 time Context switch Thread 1 Context switch Context switch Thread 2 Context switch Thread 3 Context switch Concurrency Schemes Compared Scheduler Fair Cost Program No Low Program OS No Medium Multiprogramming OS No Medium Preemptive Multitasking OS Yes High Coroutines Cooperative Multitasking Java s Support for Concurrency Concurrency Support in Java Based on preemptive multitasking Threads and synchronization part of language 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 Thread Basics Creating a thread class MyThread extends Thread public void run thread body MyThread mt new MyThread Create the thread mt start Invoke run return immediately Thread Basics A thread is a separate program counter with its own stack and local variables 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 Suspension The Sleep Method public void run for try sleep 1000 Pause for 1 second catch InterruptedException e Caused by thread interrupt return System out println Tick Sleep Does this print Tick once a second No sleep delay is a lower bound 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 Races In a concurrent world always assume something else is accessing your objects 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 runs before Thread 2 Thread 1 Thread 2 1 f1 a field1 old value 2 f2 a field2 old value a field1 1 3 a field2 2 4 Thread 1 sees new values Thread 1 runs after Thread 2 Thread 1 Thread 2 a field1 1 1 a field2 2 2 3 f1 a field1 1 4 f2 a field2 2 Thread 1 sees inconsistent values Execution of Thread 1 interrupts execution of Thread 2 Thread 1 Thread 2 a field1 1 1 2 f1 a field1 1 3 f2 a field2 old value a field2 2 4 Non atomic Operations Biggest problem is the third case reader thread sees partially updated values Might violate an invariant Problem is non atomic updates Want no write to interrupt a read no read to
View Full Document
Unlocking...