ConcurrencyCOMS W4115Prof. Stephen A. EdwardsSpring 2002Columbia UniversityDepartment of Computer ScienceConcurrencyMultiple, simultaneous execution contexts.Want to “walk and chew gum at the same time” to•Capture simultaneity of system structureE.g., Web Servers must deal with multiple,simultaneous, independent requests.•Deal with independent physical devicesThe disk drive is delivering data while the network isdelivering packets while the user is typing while. ..•Increase performanceSplit the problem into parts and solve each on aseparate processorCoroutinesBasic idea: run tworoutines concurrentlyand let them tradecontrol.“Pick up where you leftoff”Example: Lexer/parserScancontrol transferParsecontrol transferScancontrol transferParsecontrol transferScancontrol transferParsecontrol transferCoroutineschar 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 CoroutinesLanguages such as C, C++, Java don’t have directsupport.Some libraries provide such a mechanism.Challenge: Each couroutine needs a separate stackCan 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; /* program counter state */static int i; /* use static, not automatic vars */switch (state) {case 0:for ( i = 0 ; i < 10 ; i++ ) {state = 1; return i;case 1: ;}for ( i = 10 ; i > 0 ; i-- ) {state = 2; return i;case 2: ;}for (;;) {state = 3; return 0;case 3: ;}}}Faking Coroutines in JavaHarder 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 MultitaskingCoroutines explicitly say when to context switch and whoto run next.Programmer completely responsible for scheduling.Alternative: cooperative multitaskingPrograms explicitly release control to operating system.Operating system responsible for deciding which programruns next.Cooperative MultitaskingTypical MacOS < 10 or Windows < 95 program:void main() {Event e;while ( (e = get_next_eventMagical()) != QUIT ) {switch (e) {case CLICK: /* ... */ break;case DRAG: /* ... */ break;case DOUBLECLICK: /* ... */ break;case KEYDOWN: /* ... */ break;/* ... */}}}Cooperative MultitaskingAdvantages:Frees the programmer from worrying about whichother processes are runningCheap to implement.Disadvantages:Malicious process may never call getnext event.Programmer needs to add calls to long-executingevent responses.Programmer still partially responsible for scheduling.Multiprogramming HistoryFirst processors ran batch jobs: resident monitor loadsone 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 punchcard reader!Solution: Multiprogramming with interrupt-driven I/OMultiprogrammingAvoids I/O busywaiting.Context switchon I/O request.I/O completiontriggers interrupt.Interrupt causescontext switch.App 1Disk readApp 2App 1 read completeApp 1Disk readApp 3Disk writeApp 2App 1 read completeApp 1App 3 write completePreemptive MultitaskingIdea: give the OS the power to interrupt any process.Advantages:Programmer completely freed from thinking aboutscheduling: never needs to say “context switch.”Scheduler can enforce fairness: no process maymonopolize processorDisadvantages:Heavyweight: each process typically has own memorymap (switching costly)Inter-program interaction now asynchronous: programmay be interrupted anywhereTimesharingModel used on most modern operating systems (e.g.,Unix 1970s, Windows/Mac 2000s)System runs multiple threads. Each a separate executioncontext (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 onethread running at a time. Gives the impression ofsimultaneity.Three Threads on a Uniprocessor↓timeThread 1Context switchThread 2Context switchThread 3Context switchThread 1Context switchThread 2Context switchThread 3Context switchConcurrency Schemes ComparedScheduler Fair CostCoroutines Program No LowCooperative Multitasking Program/OS No MediumMultiprogramming OS No MediumPreemptive Multitasking OS Yes HighJava’s Support for ConcurrencyConcurrency Support in JavaBased on preemptive multitasking.Threads and synchronization part of language.Model: multiple program counters sharing a memoryspace. Separate stacks.All objects can be shared among threads.Fundamentally nondeterministic, but language providessome facilities for avoiding it.Thread BasicsCreating a thread:class MyThread extends Thread {public void run() {/* thread body */}}MyThread mt = new MyThread(); // Create the threadmt.start(); // Invoke run, return immediatelyThread BasicsA thread is a separate program counter with its own stackand local variables.It is not an object: the Thread class is just a way to starta 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 Methodpublic void run() {for(;;) {try {sleep(1000); // Pause for 1 second} catch (InterruptedException e) {return; // Caused by thread.interrupt()}System.out.println("Tick");}}SleepDoes this print Tick once asecond? No.sleep() delay is a lower boundRest of the loop takes anindeterminate amount of time.public void run() {for(;;) {try {sleep(1000);} catch (InterruptedException e) {return;}System.out.println("Tick");}}RacesIn a concurrent world, always assume something else isaccessing your objects.Other threads are your adversaryConsider what can happen when two threads aresimultaneously reading and writing.Thread 1 Thread 2f1 = a.field1 a.field1 = 1f2 = a.field2 a.field2 = 2Thread 1 sees old valuesThread 1 runs before Thread 2Thread 11 f1 = a.field1 = old value2 f2 = a.field2 = old valueThread 2a.field1 = 13a.field2 = 24Thread 1 sees new valuesThread 1 runs after Thread 2Thread 13 f1 = a.field1 = 14 f2 = a.field2 = 2Thread 2a.field1 = 11a.field2 =
View Full Document
Unlocking...