CS241 System Programming Process Synchronization (1)ContentAdministrativeReviewInter-Process Communication (IPC)A simple gameFirst RoundSecond RoundData RacesSpooling Example: CorrectSpooling Example: RacesCritical Region (Critical Section)Critical Region RequirementCritical Regions (2)Mutual Exclusion With Busy WaitingDisabling InterruptsLock VariablesSolution HistoryTurn Mutual Exclusion(Strict Alteration)Turn Mutual Exclusion (Strict Alteration)Other Flag Mutual ExclusionOther Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag and Turn Mutual Exclusion(Peterson Solution)2 Flag and Turn Mutual Exclusion(Peterson Solution)SummaryCS241 System Programming Process Synchronization (1)Klara NahrstedtLecture 62/1/20062/3/2006CS 241 - System Programming, Klara Nahrstedt2Content zData Races–A simple gamezCritical region and mutual exclusionz Mutual exclusion using busy waiting–Disabling Interrupts–Lock Variables–Strict Alternation–Peterson’s solutionzSummary2/3/2006CS 241 - System Programming, Klara Nahrstedt3AdministrativezRead : T:2.2 on Process Synchronizationz Read: R&R 13 and 14z MP1 posted – deadline February 132/3/2006CS 241 - System Programming, Klara Nahrstedt4ReviewzProcess: a program in executionz Threads: a light weight process2/3/2006CS 241 - System Programming, Klara Nahrstedt5Inter-Process Communication (IPC)zCommunication–Pass information to each otherzMutual exclusion & Synchronization–Proper sequencing zThe last one also applies to threads2/3/2006CS 241 - System Programming, Klara Nahrstedt6A simple gamezTwo volunteers–Producer: produce 1 card per iterationzStep1: increment the counterzStep2: put the card on the table–Consumer:zStep1: check the counter to see if it is zerozStep2a: if the counter is zero, go back to step1zStep2b: if the counter is nonzero, take a card from the tablezStep3: decrement counterz I am the OS–I decide who should go, who should stop2/3/2006CS 241 - System Programming, Klara Nahrstedt7First RoundzStop Producer before step2 and let Consumer go.zWhat happens?zTwo volunteers–Producer: produce 1 card per iterationzStep1: increment the counterzStep2: put the card on the table–Consumer:zStep1: check the counter to see if it is zerozStep2a: if the counter is zero, go back to step1zStep2b: if the counter is nonzero, take a card from the tablezStep3: decrement the counter switch2/3/2006CS 241 - System Programming, Klara Nahrstedt8Second RoundzStop Producer before step2 and let Consumer go.zWhat happens?zTwo volunteers–Producer: produce 1 card per iterationzStep1: put the card on the tablezStep2: increment the counter–Consumer:zStep1: check the counter to see if it is zerozStep2a: if the counter is zero, go back to step1zStep2b: if the counter is nonzero, take a card from the tablezStep3: decrement the counter2/3/2006CS 241 - System Programming, Klara Nahrstedt9Data RaceszReason: data sharingz Previous game: producer and consumer–Share the counter–Share the cards2/3/2006CS 241 - System Programming, Klara Nahrstedt10Spooling Example: CorrectShared memoryabcProg.cProg.n4567F2…outinProcess 1next_free = in;int next_free;Stores F1 into next_free;Process 2int next_free;12F1in=next_free+13next_free = in4Stores F2 into next_free;5…in=next_free+162/3/2006CS 241 - System Programming, Klara Nahrstedt11Spooling Example: RacesShared memoryabcProg.cProg.n4567…outinProcess 1next_free = in;int next_free;Stores F1 into next_free;Process 2int next_free;13next_free = in/* value: 7 */2F1in=next_free+14F2Stores F2 into next_free;5…in=next_free+162/3/2006CS 241 - System Programming, Klara Nahrstedt12Critical Region (Critical Section)Process { while (true) { ENTER CRITICAL SECTIONAccess shared variables; // Critical Section; LEAVE CRITICAL SECTIONDo other work } }2/3/2006CS 241 - System Programming, Klara Nahrstedt13Critical Region Requirement–Mutual Exclusion: No other process must execute within the critical section while a process is in it. –Progress: If no process is waiting in its critical section and several processes are trying to get into their critical section, then entry to the critical section cannot be postponed indefinitely. –Bounded Wait: A process requesting entry to a critical section should only have to wait for a bounded number of other processes to enter and leave the critical section. –Speed and Number of CPUs: No assumption may be made about speeds or number of CPUs. z2/3/2006CS 241 - System Programming, Klara Nahrstedt14Critical Regions (2)Mutual exclusion using critical regions2/3/2006CS 241 - System Programming, Klara Nahrstedt15Mutual Exclusion With Busy WaitingzPossible Solutions–Disabling Interrupts–Lock Variables–Strict Alternation–Peterson’s solution–TSL2/3/2006CS 241 - System Programming, Klara Nahrstedt16Disabling InterruptszHow does it work?–Disable all interrupts just after entering a critical section and re-enable them just before leaving it. zWhy does it work?–With interrupts disabled, no clock interrupts can occur. (The CPU is only switched from one process to another as a result of clock or other interrupts, and with interrupts disabled, no switching can occur.) zProblems:–What if the process forgets to enable the interrupts?–Multiprocessor? (disabling interrupts only affects one CPU)zOnly used inside OS2/3/2006CS 241 - System Programming, Klara Nahrstedt17Lock VariablesWhile (lock);lock = 1;EnterCriticalSection;access shared variable;LeaveCriticalSection;lock = 0;Does the above code work?2/3/2006CS 241 - System Programming, Klara Nahrstedt18Solution HistoryApproaches:1. Turn Mutual Exclusion2. Other Flag Mutual Exclusion3. Two Flag Mutual Exclusion4. Two Flag and Turn Mutual Exclusion2/3/2006CS 241 - System Programming, Klara Nahrstedt19Turn Mutual Exclusion(Strict Alteration)Process; /* For two processes */{while (true){ while ( turn != my_process_id) { };Access shared variables; // Critical Section;turn = other_process_id;Do other work} }mutual exclusion a) yes, b) noWhat Properties does this satisfy?2/3/2006CS 241 - System Programming, Klara Nahrstedt20Turn Mutual Exclusion (Strict Alteration)Process; /* For two processes */{while (true){ while ( turn != my_process_id) { };Access shared variables; // Critical Section;turn = other_process_id;Do other work} }Progress: a) yes, b) noWhat Properties does this satisfy?2/3/2006CS 241 - System Programming, Klara Nahrstedt21Other Flag Mutual Exclusionint owner[2] = {false,
View Full Document