并發(fā)數(shù)據(jù)結(jié)構(gòu)與多核編程chapter_04

1、100111Single-Reader/Single-Writer Register0110010011Art of Multiprocessor Programming2Multi-Reader/Single-Writer Register10011Art of Multiprocessor Programming1001101100100113mumblemumble11011Multi-Reader/Multi-Writer Registermumble100111001101010Art of Multiprocessor Programming4Register SpaceSafeR

2、egularAtomicm-valuedBooleanArt of Multiprocessor ProgrammingMulti-Reader Multi-WriterMulti-Reader Single-WriterSingle-Reader Single-Writer5Safe Registerwrite(1001)read(1001)OK if reads and writes dont overlapArt of Multiprocessor Programming6Safe Registerwrite(1001)Some valid value if reads and writ

3、es do overlapread(?)000010011111$*&vArt of Multiprocessor Programming7Regular Registerwrite(0)read(1)write(1)read(0) Single Writer Readers return: Old value if no overlap (safe) Old or one of new values if overlapArt of Multiprocessor Programming8Regular or Not?write(0)read(1)write(1)read(0)Art

4、of Multiprocessor Programming9Regular or Not?write(0)read(1)write(1)read(0)Overlap: returns new valueArt of Multiprocessor Programming10Regular or Not?write(0)write(1)read(0)Overlap: returns old valueArt of Multiprocessor Programming11Regular or Not?write(0)read(1)write(1)read(0)regularArt of Multip

5、rocessor Programming12Regular Linearizablewrite(0)read(1)write(1)read(0)write(1) already happenedcant explain this!Art of Multiprocessor Programming13Atomic Registerwrite(1001)read(1001)Linearizable to sequential safe registerwrite(1010)read(1010)read(1010)Art of Multiprocessor Programming14Atomic R

6、egisterwrite(1001)read(1001)write(1010)read(1010)read(1010)Art of Multiprocessor Programming15Weakest Register101Single readerSingle writerSafe Boolean registerArt of Multiprocessor Programming16Results From SRSW safe Boolean register All the other registers Mutual exclusion But not everything! Cons

7、ensus hierarchyFoundations of the fieldThe really cool stuff Art of Multiprocessor ProgrammingFrom Safe SRSW Boolean to Atomic SnapshotsArt of Multiprocessor Programming17MRMWMRSWSRSWSafeRegularAtomicM-valuedBooleanSnapshot18Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW regu

8、lar MRSW atomic MRMW atomic Atomic snapshotArt of Multiprocessor Programming19public class SafeBoolMRSWRegister implements Register public boolean read() public void write(boolean x) Register NamesArt of Multiprocessor Programming20Safe Boolean MRSW fromSafe Boolean SRSW00000000000zzzreaderswriterAr

9、t of Multiprocessor Programming21Safe Boolean MRSW fromSafe Boolean SRSWpublic class SafeBoolMRSWRegister implements Register private SafeBoolSRSWRegister r = new SafeBoolSRSWRegisterN; public void write(boolean x) for (int j = 0; j N; j+) rj.write(x); public boolean read() int i = ThreadID.get(); r

10、eturn ri.read(); Art of Multiprocessor Programming22Regular Boolean MRSW fromSafe Boolean MRSWpublic class RegBoolMRSWRegister implements Register private boolean old; private SafeBoolMRSWRegister value; public void write(boolean x) if (old != x) value.write(x); old = x; public boolean read() return

11、 value.read(); Art of Multiprocessor Programming23MRSW Regular m-valued from MRSW Regular Booleanpublic class RegMRSWRegister implements Register RegBoolMRSWRegisterM bit; public void write(int x) this.bitx.write(true); for (int i=x-1; i=0; i-) this.biti.write(false); public int read() for (int i=0;

12、 i M; i+) if (this.biti.read() return i; Art of Multiprocessor Programming24DefinitionAn object implementation is wait-free if every method call completes in a finite number of steps No mutual exclusion Thread could halt in critical section Build mutual exclusion from registersArt of Multiprocessor

13、Programming25Space of RegistersArt of Multiprocessor ProgrammingMRMW,MV,AMRSW,MV,ASRSW,B,ASRSW,MV,ASRSW,B,SSRSW,MV,SSRSW,MV,RMRSW,B,AMRSW,B,SMRSW,B,RMRSW,MV,RMRSW,MV,SMRMW,MV,RSRSW,B,R26Atomic SnapshotupdatescanArt of Multiprocessor Programming27Atomic Snapshot Array of MRSW atomic registers Take in

14、stantaneous snapshot of all Generalizes to MRMW registers Art of Multiprocessor Programming28Snapshot Interfacepublic interface Snapshot public int update(int v); public int scan();Art of Multiprocessor Programming29Atomic Snapshot Collect Read values one at a time Problem Incompatible concurrent co

15、llects Result not linearizableArt of Multiprocessor Programming30Clean Collects Clean Collect Collect during which nothing changed Can we make it happen? Can we detect it?Art of Multiprocessor Programming31Simple Snapshot Put increasing labels on each entry Collect twice If both agree, Were done Oth

16、erwise, Try againxyzwrzx=Collect 2Collect 1xyzwrzxProblem: Scanner might not be collecting a snapshot!Art of Multiprocessor Programming32Claim: We Must Use LabelstimexyxyzzxzxzScannerUpdaterUpdaterBut scanner sees x and z together!x and z are never in memory together wArt of Multiprocessor Programmi

17、ng33Must Use Labelstime1,x2,y3,x4,y1,z3,z1,x1,z3,x3,zScannerUpdaterUpdater2,wScanner reads x and z with different labels and recognizes collect not cleanArt of Multiprocessor Programming34Simple Snapshot Collect twice If both agree, Were done Otherwise, Try again12217131812=Collect 2Collect 11221713

18、1812Art of Multiprocessor Programming35Simple Snapshot: Updatepublic class SimpleSnapshot implements Snapshot private AtomicMRSWRegister register; public void update(int value) int i = Thread.myIndex(); LabeledValue oldValue = registeri.read(); LabeledValue newValue = new LabeledValue(oldValue.label

19、+1, value); registeri.write(newValue); Art of Multiprocessor Programming36Simple Snapshot: Updatepublic class SimpleSnapshot implements Snapshot private AtomicMRSWRegister register; public void update(int value) int i = Thread.myIndex(); LabeledValue oldValue = registeri.read(); LabeledValue newValu

20、e = new LabeledValue(oldValue.label+1, value); registeri.write(newValue); One single-writer register per threadArt of Multiprocessor Programming37Simple Snapshot: Updatepublic class SimpleSnapshot implements Snapshot private AtomicMRSWRegister register; public void update(int value) int i = Thread.m

21、yIndex(); LabeledValue oldValue = registeri.read(); LabeledValue newValue = new LabeledValue(oldValue.label+1, value); registeri.write(newValue); Write each time with higher labelArt of Multiprocessor Programming38Simple Snapshot: Collectprivate LabeledValue collect() LabeledValue copy = new Labeled

22、Valuen; for (int j = 0; j n; j+) copyj = this.registerj.read(); return copy;Art of Multiprocessor Programming39Simple Snapshotprivate LabeledValue collect() LabeledValue copy = new LabeledValuen; for (int j = 0; j n; j+) copyj = this.registerj.read(); return copy;Just read each register into arrayAr

23、t of Multiprocessor Programming40Simple Snapshot: Scanpublic int scan() LabeledValue oldCopy, newCopy; oldCopy = collect(); collect: while (true) newCopy = collect(); if (!equals(oldCopy, newCopy) oldCopy = newCopy; continue collect; return getValues(newCopy);Art of Multiprocessor Programming41Simpl

24、e Snapshot: Scanpublic int scan() LabeledValue oldCopy, newCopy; oldCopy = collect(); collect: while (true) newCopy = collect(); if (!equals(oldCopy, newCopy) oldCopy = newCopy; continue collect; return getValues(newCopy);Collect onceArt of Multiprocessor Programming42Simple Snapshot: Scanpublic int

25、 scan() LabeledValue oldCopy, newCopy; oldCopy = collect(); collect: while (true) newCopy = collect(); if (!equals(oldCopy, newCopy) oldCopy = newCopy; continue collect; return getValues(newCopy);Collect onceCollect twiceArt of Multiprocessor Programming43Simple Snapshot: Scanpublic int scan() Label

26、edValue oldCopy, newCopy; oldCopy = collect(); collect: while (true) newCopy = collect(); if (!equals(oldCopy, newCopy) oldCopy = newCopy; continue collect; return getValues(newCopy);Collect onceCollect twiceOn mismatch, try againArt of Multiprocessor Programming44Simple Snapshot: Scanpublic int sca

27、n() LabeledValue oldCopy, newCopy; oldCopy = collect(); collect: while (true) newCopy = collect(); if (!equals(oldCopy, newCopy) oldCopy = newCopy; continue collect; return getValues(newCopy);Collect onceCollect twiceOn match, return valuesArt of Multiprocessor Programming45Simple Snapshot Lineariza

28、ble Update is wait-free No unbounded loops But Scan can starve If interrupted by concurrent updateArt of Multiprocessor Programming46Wait-Free Snapshot Add a scan before every update Write resulting snapshot together with update value If scan is continuously interrupted by updates, scan can take the

29、 updates snapshot Art of Multiprocessor Programming47Wait-free SnapshotIf As scan observes that B movedtwice, then B completed an updatewhile As scan was in progresstimeUpdateB262412Collect262412Collect262412CollectArt of Multiprocessor Programming48Wait-free Snapshottime262412Collect262412Collect26

30、2412CollectUpdateABArt of Multiprocessor Programming49Wait-free Snapshottime262412Collect262412Collect262412CollectABScanWriteUpdateArt of Multiprocessor Programming50Wait-free Snapshottime262412Collect262412Collect262412CollectABScanWriteUpdateScanWriteBs 1st update must have written during 1st col

31、lectSo scan of Bs second update mustbe within interval of As scanSo A can steal result of Bs scanArt of Multiprocessor Programming51Wait-free Snapshottime262412Collect262412Collect262412CollectABScanWriteScanWriteBut no guarantee that scanof Bs 1st update can be usedWhy?Art of Multiprocessor Program

32、ming52Once is not Enoughtime262412Collect262412CollectUpdateABScanWriteWhy cant A steal Bs scan?Because another update might have interferedbefore the scanUpdateArt of Multiprocessor Programming53Someone Must Move TwicetimeUpdateB262412Collect262412Collect262412CollectIf we collect n timessome threa

33、d must move twice (pigeonhole principle) Art of Multiprocessor Programming54Scan is Wait-free scanupdateSo some thread must have had clean collectscanupdatescanAt most n-1 depthArt of Multiprocessor Programming55Wait-Free Snapshot Labelpublic class SnapValue public int label; public int value; publi

34、c int snap; Art of Multiprocessor Programming56Wait-Free Snapshot Labelpublic class SnapValue public int label; public int value; public int snap; Counter incremented with each snapshotArt of Multiprocessor Programming57Wait-Free Snapshot Labelpublic class SnapValue public int label; public int valu

35、e; public int snap; Actual valueArt of Multiprocessor Programming58Wait-Free Snapshot Labelpublic class SnapValue public int label; public int value; public int snap; most recent snapshotArt of Multiprocessor Programming59Wait-Free Snapshot Label1101111010100010110000labelvalueLast snapshotArt of Mu

36、ltiprocessor Programming60Wait-free Update public void update(int value) int i = Thread.myIndex(); int snap = this.scan(); SnapValue oldValue = ri.read(); SnapValue newValue = new SnapValue(oldValue.label+1, value, snap); ri.write(newValue); Art of Multiprocessor Programming61Wait-free Scan public v

37、oid update(int value) int i = Thread.myIndex(); int snap = this.scan(); SnapValue oldValue = ri.read(); SnapValue newValue = new SnapValue(oldValue.label+1, value, snap); ri.write(newValue); Take scanArt of Multiprocessor Programming62Wait-free Scan public void update(int value) int i = Thread.myInd

38、ex(); int snap = this.scan(); SnapValue oldValue = ri.read(); SnapValue newValue = new SnapValue(oldValue.label+1, value, snap); ri.write(newValue); Take scanLabel value with scanArt of Multiprocessor Programming63Wait-free Scan public int scan() SnapValue oldCopy, newCopy; boolean moved = new boole

39、ann; oldCopy = collect(); collect: while (true) newCopy = collect(); for (int j = 0; j n; j+) if (oldCopyj.label != newCopyj.label) return getValues(newCopy);Art of Multiprocessor Programming64Wait-free Scan public int scan() SnapValue oldCopy, newCopy; boolean moved = new booleann; oldCopy = collec

40、t(); collect: while (true) newCopy = collect(); for (int j = 0; j n; j+) if (oldCopyj.label != newCopyj.label) return getValues(newCopy);Keep track of who movedArt of Multiprocessor Programming65Wait-free Scan public int scan() SnapValue oldCopy, newCopy; boolean moved = new booleann; oldCopy = coll

41、ect(); collect: while (true) newCopy = collect(); for (int j = 0; j n; j+) if (oldCopyj.label != newCopyj.label) return getValues(newCopy);Repeated double collectArt of Multiprocessor Programming66Wait-free Scan public int scan() SnapValue oldCopy, newCopy; boolean moved = new booleann; oldCopy = co

42、llect(); collect: while (true) newCopy = collect(); for (int j = 0; j n; j+) if (oldCopyj.label != newCopyj.label) return getValues(newCopy);If mismatch detectedArt of Multiprocessor Programming67Mismatch Detectedif (oldCopyj.label != newCopyj.label) if (movedj) / second move return newCopyj.snap; e

43、lse movedj = true; oldCopy = newCopy; continue collect; return getValues(newCopy);Art of Multiprocessor Programming68Mismatch Detectedif (oldCopyj.label != newCopyj.label) if (movedj) return newCopyj.snap; else movedj = true; oldCopy = newCopy; continue collect; return getValues(newCopy);If thread m

44、oved twice, just steal its second snapshotArt of Multiprocessor Programming69Mismatch Detectedif (oldCopyj.label != newCopyj.label) if (movedj) / second move return newCopyj.snap; else movedj = true; oldCopy = newCopy; continue collect; return getValues(newCopy);Remember that thread movedArt of Multiprocessor Programming70Summary We saw we could implement MRMW multi valued snapsho