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 ExclusionSlide 222 Flag Mutual ExclusionSlide 24Slide 252 Flag and Turn Mutual Exclusion (Peterson Solution)Slide 27SummaryCS241 System Programming Process Synchronization (1)Klara NahrstedtLecture 62/1/200601/14/19 CS 241 - System Programming, Klara Nahrstedt2Content Data Races–A simple gameCritical region and mutual exclusionMutual exclusion using busy waiting–Disabling Interrupts–Lock Variables–Strict Alternation–Peterson’s solutionSummary01/14/19 CS 241 - System Programming, Klara Nahrstedt3AdministrativeRead : T:2.2 on Process SynchronizationRead: R&R 13 and 14MP1 posted – deadline February 1301/14/19 CS 241 - System Programming, Klara Nahrstedt4ReviewProcess: a program in executionThreads: a light weight process01/14/19 CS 241 - System Programming, Klara Nahrstedt5Inter-Process Communication (IPC)Communication–Pass information to each otherMutual exclusion & Synchronization–Proper sequencing The last one also applies to threads01/14/19 CS 241 - System Programming, Klara Nahrstedt6A simple gameTwo volunteers–Producer: produce 1 card per iterationStep1: increment the counterStep2: put the card on the table–Consumer:Step1: check the counter to see if it is zeroStep2a: if the counter is zero, go back to step1Step2b: if the counter is nonzero, take a card from the tableStep3: decrement counterI am the OS–I decide who should go, who should stop01/14/19 CS 241 - System Programming, Klara Nahrstedt7First RoundStop Producer before step2 and let Consumer go.What happens?Two volunteers–Producer: produce 1 card per iterationStep1: increment the counterStep2: put the card on the table–Consumer:Step1: check the counter to see if it is zeroStep2a: if the counter is zero, go back to step1Step2b: if the counter is nonzero, take a card from the tableStep3: decrement the counter switch01/14/19 CS 241 - System Programming, Klara Nahrstedt8Second RoundStop Producer before step2 and let Consumer go.What happens?Two volunteers–Producer: produce 1 card per iterationStep1: put the card on the tableStep2: increment the counter–Consumer:Step1: check the counter to see if it is zeroStep2a: if the counter is zero, go back to step1Step2b: if the counter is nonzero, take a card from the tableStep3: decrement the counter01/14/19 CS 241 - System Programming, Klara Nahrstedt9Data RacesReason: data sharingPrevious game: producer and consumer–Share the counter–Share the cards01/14/19 CS 241 - System Programming, Klara Nahrstedt10Spooling Example: CorrectShared memoryabcProg.cProg.n4567F2……outinProcess 1Process 2next_free = in;next_free = inint next_free;Stores F1 into next_free;Stores F2 into next_free;int next_free;124in=next_free+1F1in=next_free+135601/14/19 CS 241 - System Programming, Klara Nahrstedt11Spooling Example: RacesShared memoryabcProg.cProg.n4567……outinProcess 1Process 2next_free = in;next_free = in/* value: 7 */int next_free;Stores F1 into next_free;Stores F2 into next_free;int next_free;132in=next_free+1F1in=next_free+1456F201/14/19 CS 241 - System Programming, Klara Nahrstedt12Critical Region (Critical Section)Process { while (true) { ENTER CRITICAL SECTION Access shared variables; // Critical Section; LEAVE CRITICAL SECTION Do other work } }01/14/19 CS 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. 01/14/19 CS 241 - System Programming, Klara Nahrstedt14Critical Regions (2)Mutual exclusion using critical regions01/14/19 CS 241 - System Programming, Klara Nahrstedt15Mutual Exclusion With Busy WaitingPossible Solutions–Disabling Interrupts–Lock Variables–Strict Alternation–Peterson’s solution–TSL01/14/19 CS 241 - System Programming, Klara Nahrstedt16Disabling InterruptsHow does it work?–Disable all interrupts just after entering a critical section and re-enable them just before leaving it. Why 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.) Problems:–What if the process forgets to enable the interrupts?–Multiprocessor? (disabling interrupts only affects one CPU)Only used inside OS01/14/19 CS 241 - System Programming, Klara Nahrstedt17Lock VariablesWhile (lock);lock = 1;EnterCriticalSection; access shared variable;LeaveCriticalSection;lock = 0;Does the above code work?01/14/19 CS 241 - System Programming, Klara Nahrstedt18 Solution HistoryApproaches:1. Turn Mutual Exclusion2. Other Flag Mutual Exclusion3. Two Flag Mutual Exclusion4. Two Flag and Turn Mutual Exclusion01/14/19 CS 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?01/14/19 CS 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?01/14/19 CS 241 -
View Full Document