DOC PREVIEW
U of I CS 241 - System Programming Process Synchronization

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 241 - System Programming Process Synchronization

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download System Programming Process Synchronization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view System Programming Process Synchronization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view System Programming Process Synchronization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?