DOC PREVIEW
CORNELL CS 514 - CS514: Intermediate Course in Operating Systems

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:

CS514: Intermediate Course in Operating SystemsRecapSo far?This and upcoming lectures?What time is it?But what does time “mean”?Lamport’s approachDrawing time-line pictures:Slide 9Slide 10Slide 11Slide 12Slide 13Happens before “relation”Logical clocksRules for managing logical clocksTime-line with LT annotationsSlide 18Can we do better?Vector clocksTime-line with VT annotationsRules for comparison of VTsSlide 23Vector time and happens beforeIntroducing “wall clock time”Synchronizing clocksSlide 27Slide 28Consequences?Thought questionSlide 31Real systems?Clock synchronizationFor next timeCS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TARecapWe’ve started a process of isolating questions that arise in big systemsTease out an abstract issueTreat it separate from the original messy contextTry and understand what can and cannot be done, and how to solve when something can be doneSo far?Naming and discoveryPerformance through threading, events, ultimately clustersNotions of consistency that can and cannot be solvedCan’t achieve common knowledgeBut if we accept certain very limited risks can often achieve reasonable goalsThis and upcoming lectures?We’ll focus on concepts relating to timeTime as it can be “used” in systemsSystems that present behaviors best understood in terms of temporal models (notably the transactional model)Event ordering used to ensure consistency in distributed systems (multicasts that update replicated data or program state)What time is it?In distributed system we need practical ways to deal with timeE.g. we may need to agree that update A occurred before update BOr offer a “lease” on a resource that expires at time 10:10.0150 Or guarantee that a time critical event will reach all interested parties within 100msBut what does time “mean”?Time on a global clock?E.g. with GPS receiver… or on a machine’s local clockBut was it set accurately?And could it drift, e.g. run fast or slow?What about faults, like stuck bits?… or could try to agree on timeLamport’s approachLeslie Lamport suggested that we should reduce time to its basicsTime lets a system ask “Which came first: event A or event B?”In effect: time is a means of labeling events so that…If A happened before B, TIME(A) < TIME(B)If TIME(A) < TIME(B), A happened before BDrawing time-line pictures:pmsndp(m)qrcvq(m) delivq(m)DDrawing time-line pictures:A, B, C and D are “events”. Could be anything meaningful to the applicationSo are snd(m) and rcv(m) and deliv(m)What ordering claims are meaningful?pmACBsndp(m)qrcvq(m) delivq(m)DDrawing time-line pictures:A happens before B, and C before D“Local ordering” at a single processWrite and pqmACBrcvq(m) delivq(m)sndp(m)BApDCqDDrawing time-line pictures:sndp(m) also happens before rcvq(m)“Distributed ordering” introduced by a messageWritepqmACBrcvq(m) delivq(m)sndp(m))m(rcv)m(sndqMpDDrawing time-line pictures:A happens before DTransitivity: A happens before sndp(m), which happens before rcvq(m), which happens before DpqmDACBrcvq(m) delivq(m)sndp(m)Drawing time-line pictures:B and D are concurrentLooks like B happens first, but D has no way to know. No information flowed…pqmDACBrcvq(m) delivq(m)sndp(m)Happens before “relation”We’ll say that “A happens before B”, written AB, if1. APB according to the local ordering, or2. A is a snd and B is a rcv and AMB, or3. A and B are related under the transitive closure of rules (1) and (2)So far, this is just a mathematical notation, not a “systems tool”Logical clocksA simple tool that can capture parts of the happens before relationFirst version: uses just a single integerDesigned for big (64-bit or more) countersEach process p maintains LTp, a local counterA message m will carry LTmRules for managing logical clocksWhen an event happens at a process p it increments LTp. Any event that matters to pNormally, also snd and rcv events (since we want receive to occur “after” the matching send)When p sends m, setLTm = LTpWhen q receives m, setLTq = max(LTq, LTm)+1Time-line with LT annotationsLT(A) = 1, LT(sndp(m)) = 2, LT(m) = 2LT(rcvq(m))=max(1,2)+1=3, etc…pqmDACBrcvq(m) delivq(m)sndp(m)LTq0 0 0 1 1 1 1 3 3 3 4 5 5LTp0 1 1 2 2 2 2 2 2 3 3 3 3Logical clocksIf A happens before B, AB,then LT(A)<LT(B)But converse might not be true:If LT(A)<LT(B) can’t be sure that AB This is because processes that don’t communicate still assign timestamps and hence events will “seem” to have an orderCan we do better?One option is to use vector clocksHere we treat timestamps as a listOne counter for each processRules for managing vector times differ from what did with logical clocksVector clocksClock is a vector: e.g. VT(A)=[1, 0]We’ll just assign p index 0 and q index 1Vector clocks require either agreement on the numbering, or that the actual process id’s be included with the vectorRules for managing vector clockWhen event happens at p, increment VTp[indexp]Normally, also increment for snd and rcv events When sending a message, set VT(m)=VTpWhen receiving, set VTq=max(VTq, VT(m))Time-line with VT annotationspqmDACBrcvq(m) delivq(m)sndp(m)VTq0 00 00 00 10 10 10 12 22 22 2232 32 4VTp0 01 01 02 02 02 02 02 02 03 0303 03 0VT(m)=[2,0]Could also be [1,0] if we decide not to increment the clock on a snd event. Decision depends on how the timestamps will be used.Rules for comparison of VTsWe’ll say that VTA ≤ VTB ifI, VTA[i] ≤ VTB[i]And we’ll say that VTA < VTB ifVTA ≤ VTB but VTA ≠ VTBThat is, for some i, VTA[i] < VTB[i]Examples?[2,4] ≤ [2,4][1,3] < [7,3][1,3] is “incomparable” to [3,1]Time-line with VT annotationsVT(A)=[1,0]. VT(D)=[2,4]. So VT(A)<VT(D)VT(B)=[3,0]. So VT(B) and VT(D) are incomparablepqmDACBrcvq(m) delivq(m)sndp(m)VTq0 00 00 00 10 10 10 12 22 22 2232 32 4VTp0 01 01 02 02 02 02 02 02 03 0303 03 0VT(m)=[2,0]Vector time and happens beforeIf AB, then VT(A)<VT(B)Write a chain of events from A to BStep by step the vector clocks get largerIf VT(A)<VT(B) then ABTwo cases: if A and B both happen at same process p, trivialIf A happens at p and B at q, can trace the path


View Full Document

CORNELL CS 514 - CS514: Intermediate Course in Operating Systems

Documents in this Course
LECTURE

LECTURE

29 pages

LECTURE

LECTURE

28 pages

Load more
Download CS514: Intermediate Course in Operating Systems
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 CS514: Intermediate Course in Operating Systems 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 CS514: Intermediate Course in Operating Systems 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?