DOC PREVIEW
CORNELL CS 414 - Study Guide

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

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

Unformatted text preview:

Critical Sections with lots of ThreadsAnnouncementsReview: Race conditionsThe Fundamental Issue: AtomicityRevisiting Race ConditionsCritical Section ProblemSolution StructureSolution RequirementsRefresher: Dekker’s AlgorithmPeterson’s Algorithm (1981)Napkin analysis of Peterson’s algorithm:Can we generalize to many threads?Bakery “concept”Bakery Algorithm: “Take 1”Bakery Algorithm: “Take 2”Bakery Algorithm: “Take 3”Bakery Algorithm: “Take 4”Bakery Algorithm: Almost finalBakery Algorithm: Issues?Bakery Algorithm: FinalHow do real systems do it?Critical Sections with Atomic Hardware Primitivestest_and_set InstructionSolution using TestAndSetSwap InstructionSolution using SwapPresenting critical sections to usersSemaphoresSemaphore TypesSemaphore ImplementationSemaphore Implementation with no Busy waitingImplementing SemaphoresSlide 33In Summary…Critical Sections with lots of ThreadsAnnouncements•CS 414 Homework due todayReview: Race conditions•Definition: timing dependent error involving shared state –Whether it happens depends on how threads scheduled•Hard to detect:–All possible schedules have to be safe •Number of possible schedule permutations is huge•Some bad schedules? Some that will work sometimes?–they are intermittent•Timing dependent = small changes can hide bugThe Fundamental Issue: Atomicity•Our atomic operation is not done atomically by machine–Atomic Unit: instruction sequence guaranteed to execute indivisibly–Also called “critical section” (CS)When 2 processes want to execute their Critical Section,–One process finishes its CS before other is allowed to enterRevisiting Race ConditionsProcess b: while(i > -10)i = i - 1; print “B won!”;Process a: while(i < 10)i = i +1; print “A won!”;– Who wins?– Will someone definitely win?Critical Section Problem•Problem: Design a protocol for processes to cooperate, such that only one process is in its critical section–How to make multiple instructions seem like one?Processes progress with non-zero speed, no assumption on clock speedUsed extensively in operating systems:Queues, shared variables, interrupt handlers, etc.Process 1Process 2CS1Time CS2Solution StructureShared vars: Initialization:Process:. . . . . . Entry SectionCritical SectionExit SectionAdded to solve the CS problemSolution Requirements•Mutual Exclusion–Only one process can be in the critical section at any time•Progress–Decision on who enters CS cannot be indefinitely postponed•No deadlock•Bounded Waiting–Bound on #times others can enter CS, while I am waiting•No livelock•Also efficient (no extra resources), fair, simple, …Refresher: Dekker’s Algorithm•Assumes two threads, numbered 0 and 1 CSEnter(int i){inside[i] = true;while(inside[J]){ if (turn == J) { inside[i] = false; while(turn == J) continue; inside[i] = true; }}}CSExit(int i){turn = J;inside[i] = false;}Peterson’s Algorithm (1981) CSEnter(int i){inside[i] = true;turn = J;while(inside[J] && turn == J)continue; }CSExit(int i){inside[i] = false;}•Simple is good!!Napkin analysis of Peterson’s algorithm:•Safety (by contradiction): –Assume that both processes (Alan and Shay) are in their critical section (and thus have their inside flags set). Since only one, say Alan, can have the turn, the other (Shay) must have reached the while() test before Alan set his inside flag. –However, after setting his inside flag, Alan gave away the turn to Shay. Shay has already changed the turn and cannot change it again, contradicting our assumption.Liveness & Bounded waiting => the turn variable.Can we generalize to many threads?•Obvious approach won’t work:•Issue: Who’s turn next?CSEnter(int i){inside[i] = true;for(J = 0; J < N; J++)while(inside[J] && turn == J)continue; }CSExit(int i){inside[i] = false;}Bakery “concept”•Think of a popular store with a crowded counter, perhaps the pastry shop in Montreal’s fancy market–People take a ticket from a machine–If nobody is waiting, tickets don’t matter–When several people are waiting, ticket order determines order in which they can make purchasesBakery Algorithm: “Take 1”•int ticket[n];•int next_ticket;CSEnter(int i){ticket[i] = ++next_ticket;for(J = 0; J < N; J++)while(ticket[J] && ticket[J] < ticket[i])continue;}CSExit(int i){ticket[i] = 0;}•Oops… access to next_ticket is a problem!Bakery Algorithm: “Take 2”•int ticket[n];CSEnter(int i){ticket[i] = max(ticket[0], … ticket[N-1])+1;for(J = 0; J < N; J++)while(ticket[J] && ticket[j] < ticket[i])continue;}CSExit(int i){ticket[i] = 0;}•Clever idea: just add one to the max.Just add 1 to the max!•Oops… two could pick the same value!Bakery Algorithm: “Take 3”If i, j pick same ticket value, id’s break tie:(ticket[J] < ticket[i]) || (ticket[J]==ticket[i] && J<i)Notation: (B,J) < (A,i) to simplify the code: (B<A || (B==A && J<i)), e.g.:(ticket[J],J) < (ticket[i],i)Bakery Algorithm: “Take 4”•int ticket[N];•boolean picking[N] = false;CSEnter(int i){ticket[i] = max(ticket[0], … ticket[N-1])+1;for(J = 0; J < N; J++) while(ticket[J] && (ticket[J],J) < (ticket[i],i))continue;}CSExit(int i){ticket[i] = 0;}•Oops… i could look at J when J is still storing its ticket, and yet J could have a lower id than me (i)!Bakery Algorithm: Almost final•int ticket[N];•boolean choosing[N] = false;CSEnter(int i){choosing[i] = true;ticket[i] = max(ticket[0], … ticket[N-1])+1;choosing[i] = false;for(J = 0; J < N; J++) {while(choosing[J]) continue;while(ticket[J] && (ticket[J],J) < (ticket[i],i))continue;}}CSExit(int i){ticket[i] = 0;}Bakery Algorithm: Issues?•What if we don’t know how many threads might be running?–The algorithm depends on having an agreed upon value for N–Somehow would need a way to adjust N when a thread is created or one goes away•Also, technically speaking, ticket can overflow!–Solution: Change code so that if ticket is “too big”, set it back to zero and try again.Bakery Algorithm: Final•int ticket[N]; /* Important: Disable thread scheduling when changing N */•boolean choosing[N] = false;CSEnter(int i){do { ticket[i] = 0; choosing[i] = true; ticket[i] = max(ticket[0], … ticket[N-1])+1; choosing[i] = false;} while(ticket[i] >= MAXIMUM);for(J = 0; J < N; J++) {while(choosing[J]) continue;while(ticket[J] && (ticket[J],J) < (ticket[i],i))continue;}}CSExit(int i){ticket[i] = 0;}How do real


View Full Document

CORNELL CS 414 - Study Guide

Documents in this Course
Security

Security

49 pages

Processes

Processes

24 pages

Deadlocks

Deadlocks

57 pages

Threads

Threads

5 pages

Threads

Threads

29 pages

Deadlocks

Deadlocks

36 pages

Load more
Download Study Guide
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 Study Guide 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 Study Guide 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?