DOC PREVIEW
U of I CS 241 - Introduction to Synchronization

This preview shows page 1-2-17-18-19-36-37 out of 37 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 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 37 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 37 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 37 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 37 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 37 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 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to SynchronizationCS241 AdministrativeOverviewInter-Process Communication (IPC)Spooling Example: CorrectSpooling Example: Data RacesCritical Region (Critical Section)Critical Region Requirements Critical Region Requirements 1 of 2 Critical Region Requirements Critical Regions (2)Mutual Exclusion With Busy WaitingLock VariablesTurn-based Mutual Exclusion with strict alternationTurn-based Mutual Exclusion with strict alternationTurn-based Mutual Exclusion with strict alternationTurn-based Mutual Exclusion with strict alternation Other Flag Mutual ExclusionOther Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag and Turn Mutual Exclusion2 Flag and Turn Mutual ExclusionDiscussionDiscussionSummaryCS 241 Spring 2007System Programming09/14/06 CS241 © 2006 RHC and YZ, All Rights Reserved1Introduction to SynchronizationKlara NahrstedtLecture 102/7/072CS241 AdministrativeThis week SMP2, Deadline Monday 9am, 2/12/07 Regular Quiz 3 on Friday, 2/9/07Reminder:Read Stallings Chapter 5 and R & R Chapter 13 and 143OverviewIntroduction to synchronizationWhy do we need synchronization?What is a data race?Critical region, mutual exclusion, progress, bounded waiting4Inter-Process Communication (IPC)IPC needed in multiprogramming – management of multiple processes within a uni-processor systemmultiprocessing – management of multiple processes within a multi-processor systemPass information to each other via shared resource Mutual exclusion & SynchronizationProper sequencing5Spooling Example: CorrectShared memoryabcProg.cProg.n4567F2……outinProcess 1next_free = in;int next_free;Stores F1 into next_free;Process 2int next_free;next_free = inStores F2 into next_free;124in=next_free+1F1in=next_free+13566Spooling Example: Data RacesShared memoryabcProg.cProg.n4567……outinProcess 1next_free = in;int next_free;Stores F1 into next_free;Process 2int next_free;next_free = in/* value: 7 */Stores F2 into next_free;132in=next_free+1F1in=next_free+1456F27Critical Region (Critical Section)Process { while (true) { ENTER CRITICAL SECTIONAccess shared variables; // Critical Section; LEAVE CRITICAL SECTIONDo other work } }8Critical Region RequirementsMutual ExclusionProgressBounded WaitNo Speed and Number of CPU assumptions9Critical Region Requirements 1 of 2Mutual 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.10Critical Region RequirementsMutual ExclusionProgressBounded 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.11ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsGood concrete example...12ProgressMutual ExclusionBounded WaitOversimplifying Assumptionsvisual learning aid: ‘bmp’ in alphabetical order13ProgressMutual ExclusionBounded WaitOversimplifying Assumptions14ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsNo cutting in!15ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsAre there door locks?No cutting in!16ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsAre there door locks?We'll be first if we sprintNo cutting in!17ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsAre there door locks?We'll be first if we sprintNo cutting in!Well, Did you see anybody go in?18Progress?Bounded Wait?What's the difference?19Progress?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 bepostponed indefinitely20Progress?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 indefinitelyBounded 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.21Critical Regions (2)Mutual exclusion using critical regions22Mutual Exclusion With Busy Waiting Possible Solutions Software-only candidate solutions (Two-Process Solutions) Lock Variables Turn Mutual Exclusion Other Flag Mutual Exclusion Two Flag Mutual Exclusion Two Flag and Turn Mutual Exclusion Hardware solutions Disabling Interrupts; Test-and-set; Swap (Exchange) Semaphores23Lock Variableswhile (lock) {/* spin spin spin spin */}lock = 1;/* EnterCriticalSection; */access shared variable;/* LeaveCriticalSection; */lock = 0;What's the problem?24Turn-based Mutual Exclusionwith strict alternationProcessMe/* For two processes */{while (true){ while ( turn != my_process_id) { }access shared variablesturn = other_process_iddo other work} }25Turn-based Mutual Exclusionwith strict alternationSatisfies Mutual Exclusion?ProcessMe/* For two processes */{while (true){ while ( turn != my_process_id) { }access shared variablesturn = other_process_iddo other work} }26Turn-based Mutual Exclusion with strict alternationSatisfies Bounded Waiting?ProcessMe/* For two processes */{while (true){ while ( turn != my_process_id) { }access shared variablesturn = other_process_iddo other work} }27Turn-based Mutual Exclusion with strict alternationProcessMe /* For two processes */{while (true){ while ( turn != my_process_id) { }access shared variablesturn = other_process_iddo other work} }Satisfies Progress?z28Other Flag Mutual ExclusionProgress?int owner[2] = {false, false}ProcessMe{ while (true){ while (owner[other_process_id] ) { }owner[my_process_id] = trueaccess shared variablesowner[my_process_id] = falsedo other work} }29Other Flag Mutual ExclusionMutual exclusion?int owner[2] = {false, false}ProcessMe{ while (true){ while (owner[other_process_id] ) { }owner[my_process_id] = trueaccess shared variablesowner[my_process_id] = falsedo other work} }z302 Flag Mutual ExclusionMutual Exclusion? int owner[2]= {false, false}ProcessMe { while (true) {owner[my_process_id] = truewhile (owner[other_process_id] ) { }access shared variablesowner[my_process_id] = falsedo other work} }312 Flag Mutual Exclusionint owner[2]= {false, false}ProcessMe { while (true)


View Full Document

U of I CS 241 - Introduction to 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 Introduction to 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 Introduction to 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 Introduction to 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?