3.4 Cydamseredd: Mae Amser yn Hanfodol

Rydym wedi gweld grym gwrthrychau cyfrifiadurol â chyflwr lleol fel offer modelu. Eto, fel y rhybuddiodd 3.1.3, mae pris i'w dalu am y grym hwn: colli tryloywder cyfeiriadol, sy'n arwain at lu o gwestiynau dyrys am fod yr un fath a newid, a'r angen i roi heibio'r model amnewid o werthuso o blaid y model amgylchedd mwy cymhleth.

Y mater canolog sy'n llechu o dan gymhlethdod cyflwr, bod yr un fath, a newid yw ein bod, drwy gyflwyno aseiniad, yn cael ein gorfodi i gynnwys amser yn ein modelau cyfrifiadurol. Cyn inni gyflwyno aseiniad, roedd ein holl raglenni'n ddiamser, yn yr ystyr bod gan unrhyw fynegiad sydd â gwerth yr un gwerth bob amser. Mewn cyferbyniad, cofiwch yr enghraifft o fodelu codi arian o gyfrif banc a dychwelyd y balans a geir, a gyflwynwyd ar ddechrau 3.1.1:

(withdraw 25)
75

(withdraw 25)
50

Yma mae gwerthusiadau olynol o'r un mynegiad yn rhoi gwerthoedd gwahanol. Mae'r ymddygiad hwn yn deillio o'r ffaith bod gweithredu gosodiadau aseinio (yn yr achos hwn, aseiniadau i'r newidyn balance) yn diffinio eiliadau mewn amser pan fydd gwerthoedd yn newid. Mae canlyniad gwerthuso mynegiad yn dibynnu nid yn unig ar y mynegiad ei hun, ond hefyd ar a yw'r gwerthuso'n digwydd cyn neu ar ôl yr eiliadau hyn. Mae adeiladu modelau yn nhermau gwrthrychau cyfrifiadurol â chyflwr lleol yn ein gorfodi i wynebu amser fel cysyniad hanfodol mewn rhaglennu.

Gallwn fynd ymhellach wrth strwythuro modelau cyfrifiadurol i gyd-fynd â'n canfyddiad o'r byd ffisegol. Nid yw gwrthrychau yn y byd yn newid fesul un yn eu trefn. Yn hytrach, gwelwn hwy'n gweithredu'n gydamserol—i gyd ar unwaith. Felly mae'n aml yn naturiol modelu systemau yn gasgliadau o brosesau cyfrifiadurol sy'n gweithredu'n gydamserol. Yn union fel y gallwn wneud ein rhaglenni'n fodiwlaidd drwy drefnu modelau yn nhermau gwrthrychau â chyflwr lleol ar wahân, mae'n aml yn briodol rhannu modelau cyfrifiadurol yn rhannau sy'n esblygu ar wahân ac yn gydamserol. Hyd yn oed os yw'r rhaglenni i'w gweithredu ar gyfrifiadur dilyniannol, mae'r arfer o ysgrifennu rhaglenni fel pe baent i'w gweithredu'n gydamserol yn gorfodi'r rhaglennydd i osgoi cyfyngiadau amseru diangen ac felly'n gwneud rhaglenni'n fwy modiwlaidd.

Yn ogystal â gwneud rhaglenni'n fwy modiwlaidd, gall cyfrifiannu cydamserol ddarparu mantais cyflymder dros gyfrifiannu dilyniannol. Dim ond un gweithrediad ar y tro y mae cyfrifiaduron dilyniannol yn ei weithredu, felly mae'r amser sydd ei angen i gyflawni tasg yn gyfrannol â chyfanswm nifer y gweithrediadau a gyflawnir.¹⁶² Fodd bynnag, os yw'n bosibl dadelfennu problem yn rhannau sy'n gymharol annibynnol ac sydd ond angen cyfathrebu'n anaml, gall fod yn bosibl dyrannu rhannau i brosesyddion cyfrifiadurol ar wahân, gan gynhyrchu mantais cyflymder sy'n gyfrannol â nifer y prosesyddion sydd ar gael.

Yn anffodus, mae'r cymhlethdodau a gyflwynir gan aseiniad yn mynd yn fwy problemus fyth ym mhresenoldeb cydamseredd. Mae'r ffaith bod gweithredu'n gydamserol, naill ai am fod y byd yn gweithredu'n baralel neu am fod ein cyfrifiaduron yn gwneud hynny, yn golygu cymhlethdod ychwanegol yn ein dealltwriaeth o amser.

3.4.1Natur Amser mewn Systemau Cydamserol

Ar yr wyneb, mae amser yn ymddangos yn syml. Trefn a osodir ar ddigwyddiadau ydyw.¹⁶³ Ar gyfer unrhyw ddigwyddiadau $A$ ac $B$, naill ai mae $A$ yn digwydd cyn $B$, mae $A$ ac $B$ yn digwydd ar yr un pryd, neu mae $A$ yn digwydd ar ôl $B$. Er enghraifft, gan ddychwelyd at enghraifft y cyfrif banc, tybiwch fod Peter yn codi $10 a Paul yn codi $25 o gyfrif ar y cyd sy'n cynnwys $100 i ddechrau, gan adael $65 yn y cyfrif. Yn dibynnu ar drefn y ddau godi arian, mae dilyniant balansau'r cyfrif naill ai'n $100 $\to <!--\; \to \; -->$ $90 $\to <!--\; \to \; -->$ $65 neu'n $100 $\to <!--\; \to \; -->$ $75 $\to <!--\; \to \; -->$ $65. Mewn gweithrediad cyfrifiadurol o'r system fancio, gellid modelu'r dilyniant newidiol hwn o falansau drwy aseiniadau olynol i newidyn balance.

Mewn sefyllfaoedd cymhleth, fodd bynnag, gall safbwynt o'r fath fod yn broblemus. Tybiwch fod Peter a Paul, a phobl eraill hefyd, yn cyrchu'r un cyfrif banc drwy rwydwaith o beiriannau bancio wedi'u dosbarthu ar hyd a lled y byd. Bydd gwir ddilyniant balansau'r cyfrif yn dibynnu'n hollbwysig ar union amseru'r cyrchiadau ac ar fanylion y cyfathrebu rhwng y peiriannau.

Gall yr ansicrwydd hwn yn nhrefn digwyddiadau beri problemau difrifol wrth ddylunio systemau cydamserol. Er enghraifft, tybiwch fod codiadau arian Peter a Paul wedi'u gweithredu'n ddwy broses ar wahân sy'n rhannu newidyn cyffredin balance, a phob proses wedi'i phennu gan y weithdrefn a roddir yn 3.1.1:

(define (withdraw amount)
  (if (>= balance amount)
      (begin 
        (set! balance 
              (- balance amount))
        balance)
      "Insufficient funds"))

Os yw'r ddwy broses yn gweithredu'n annibynnol, gallai Peter brofi'r balans a cheisio codi swm dilys. Fodd bynnag, gallai Paul godi rhywfaint o arian rhwng yr adeg y mae Peter yn gwirio'r balans a'r adeg y mae Peter yn cwblhau'r codi arian, gan wneud prawf Peter yn annilys.

Gall pethau fod yn waeth fyth. Ystyriwch y mynegiad

(set! balance (- balance amount))

a weithredir yn rhan o bob proses codi arian. Mae hwn yn cynnwys tri cham: (1) cyrchu gwerth y newidyn balance; (2) cyfrifo'r balans newydd; (3) gosod balance i'r gwerth newydd hwn. Os yw codiadau arian Peter a Paul yn gweithredu'r gosodiad hwn yn gydamserol, yna gallai'r ddau godi arian gydblethu'r drefn y maent yn cyrchu balance ac yn ei osod i'r gwerth newydd ynddi.

Mae'r diagram amseru yn Ffigur 3.29 yn dangos trefn digwyddiadau lle mae balance yn dechrau ar 100, mae Peter yn codi 10, mae Paul yn codi 25, ac eto 75 yw gwerth terfynol balance. Fel y dangosir yn y diagram, y rheswm dros yr anghysondeb hwn yw bod aseiniad Paul o 75 i balance yn cael ei wneud ar sail y dybiaeth mai 100 yw gwerth balance sydd i'w leihau. Daeth y dybiaeth honno, fodd bynnag, yn annilys pan newidiodd Peter balance i 90. Mae hwn yn fethiant trychinebus i'r system fancio, am nad yw cyfanswm yr arian yn y system yn cael ei gadw. Cyn y trafodion, cyfanswm yr arian oedd $100. Ar eu hôl, mae gan Peter $10, mae gan Paul $25, ac mae gan y banc $75.¹⁶⁴

Y ffenomen gyffredinol a ddangosir yma yw y gall sawl proses rannu newidyn cyflwr cyffredin. Yr hyn sy'n gwneud hyn yn gymhleth yw y gall mwy nag un broses fod yn ceisio trin y cyflwr a rennir ar yr un pryd. Yn enghraifft y cyfrif banc, yn ystod pob trafodyn, dylai pob cwsmer allu gweithredu fel pe na bai'r cwsmeriaid eraill yn bodoli. Pan fydd cwsmer yn newid y balans mewn ffordd sy'n dibynnu ar y balans, rhaid iddo allu tybio bod y balans, yn union cyn eiliad y newid, yn dal i fod yr hyn y credai ei fod.

Ymddygiad cywir rhaglenni cydamserol

Mae'r enghraifft uchod yn nodweddiadol o'r bygiau cynnil a all sleifio i raglenni cydamserol. Mae gwraidd y cymhlethdod hwn yn yr aseiniadau i newidynnau a rennir rhwng y gwahanol brosesau. Gwyddom eisoes fod rhaid inni fod yn ofalus wrth ysgrifennu rhaglenni sy'n defnyddio set!, am fod canlyniadau cyfrifiad yn dibynnu ar y drefn y digwydd yr aseiniadau ynddi.¹⁶⁵ Gyda phrosesau cydamserol rhaid inni fod yn arbennig o ofalus ynghylch aseiniadau, am na allwn efallai reoli trefn yr aseiniadau a wneir gan y gwahanol brosesau. Os gallai sawl newid o'r fath gael eu gwneud yn gydamserol (fel gyda dau adneuwr yn cyrchu cyfrif ar y cyd), mae arnom angen rhyw ffordd o sicrhau bod ein system yn ymddwyn yn gywir. Er enghraifft, yn achos codi arian o gyfrif banc ar y cyd, rhaid inni sicrhau bod arian yn cael ei gadw. I wneud i raglenni cydamserol ymddwyn yn gywir, efallai y bydd angen inni osod rhai cyfyngiadau ar weithredu cydamserol.

Un cyfyngiad posibl ar gydamseredd fyddai mynnu na all dau weithrediad sy'n newid unrhyw newidynnau cyflwr a rennir ddigwydd ar yr un pryd. Mae hwn yn ofyniad llym iawn. Ar gyfer bancio dosbarthedig, byddai'n mynnu bod dylunydd y system yn sicrhau mai dim ond un trafodyn a allai fynd rhagddo ar y tro. Byddai hyn yn aneffeithlon ac yn rhy geidwadol. Mae Ffigur 3.30 yn dangos Peter a Paul yn rhannu cyfrif banc, lle mae gan Paul gyfrif preifat hefyd. Mae'r diagram yn dangos dau godi arian o'r cyfrif a rennir (un gan Peter ac un gan Paul) ac adneuo yng nghyfrif preifat Paul.¹⁶⁶ Rhaid i'r ddau godi arian o'r cyfrif a rennir beidio â bod yn gydamserol (gan fod y ddau'n cyrchu ac yn diweddaru'r un cyfrif), a rhaid i adneuo a chodi arian Paul beidio â bod yn gydamserol (gan fod y ddau'n cyrchu ac yn diweddaru swm yr arian ym mhwrs Paul). Ond ni ddylai fod problem wrth ganiatáu i adneuo Paul yn ei gyfrif preifat fynd rhagddo'n gydamserol â chodi arian Peter o'r cyfrif a rennir.

Byddai cyfyngiad llai llym ar gydamseredd yn sicrhau bod system gydamserol yn cynhyrchu'r un canlyniad â phe bai'r prosesau wedi rhedeg yn ddilyniannol mewn rhyw drefn. Mae dwy agwedd bwysig ar y gofyniad hwn. Yn gyntaf, nid yw'n mynnu bod y prosesau'n rhedeg yn ddilyniannol mewn gwirionedd, ond dim ond eu bod yn cynhyrchu canlyniadau sydd yr un fath â phe baent wedi rhedeg yn ddilyniannol. Ar gyfer yr enghraifft yn Ffigur 3.30, gall dylunydd y system cyfrifon banc ganiatáu'n ddiogel i adneuo Paul a chodi arian Peter ddigwydd yn gydamserol, am y bydd y canlyniad terfynol yr un fath â phe bai'r ddau weithrediad wedi digwydd yn ddilyniannol. Yn ail, gall fod mwy nag un canlyniad “cywir” posibl i raglen gydamserol, am mai dim ond mynnu bod y canlyniad yr un fath ag ar gyfer rhyw drefn ddilyniannol a wnawn. Er enghraifft, tybiwch fod cyfrif ar y cyd Peter a Paul yn dechrau â $100, a bod Peter yn adneuo $40 tra bod Paul yn codi hanner yr arian yn y cyfrif yn gydamserol. Yna gallai gweithredu dilyniannol arwain at falans cyfrif naill ai o $70 neu o $90 (gweler Ymarfer 3.38).¹⁶⁷

Ceir gofynion gwannach fyth ar gyfer gweithredu rhaglenni cydamserol yn gywir. Gallai rhaglen i efelychu trylediad (dyweder, llif gwres mewn gwrthrych) gynnwys nifer fawr o brosesau, pob un yn cynrychioli cyfaint bach o ofod, sy'n diweddaru eu gwerthoedd yn gydamserol. Mae pob proses yn newid ei gwerth dro ar ôl tro i gyfartaledd ei gwerth ei hun a gwerthoedd ei chymdogion. Mae'r algorithm hwn yn cydgyfeirio at yr ateb cywir yn annibynnol ar drefn cyflawni'r gweithrediadau; nid oes angen unrhyw gyfyngiadau ar ddefnyddio'r gwerthoedd a rennir yn gydamserol.

Ymarfer 3.38: Tybiwch fod Peter, Paul, a Mary yn rhannu cyfrif banc ar y cyd sy'n cynnwys $100 i ddechrau. Yn gydamserol, mae Peter yn adneuo $10, mae Paul yn codi $20, ac mae Mary yn codi hanner yr arian yn y cyfrif, drwy weithredu'r gorchmynion canlynol:

Peter: (set! balance (+ balance 10))
Paul:  (set! balance (- balance 20))
Mary:  (set! balance (- balance 
                        (/ balance 2)))

1. Rhestrwch yr holl werthoedd posibl gwahanol ar gyfer balance ar ôl cwblhau'r tri thrafodyn hyn, gan dybio bod y system fancio'n gorfodi'r tair proses i redeg yn ddilyniannol mewn rhyw drefn.
2. Beth yw rhai gwerthoedd eraill y gellid eu cynhyrchu os yw'r system yn caniatáu cydblethu'r prosesau? Tynnwch ddiagramau amseru fel yr un yn Ffigur 3.29 i esbonio sut y gall y gwerthoedd hyn godi.

3.4.2Mecanweithiau Rheoli Cydamseredd

Gwelwn fod yr anhawster wrth ymdrin â phrosesau cydamserol yn deillio o'r angen i ystyried cydblethu trefn digwyddiadau yn y gwahanol brosesau. Er enghraifft, tybiwch fod gennym ddwy broses, un â thri digwyddiad mewn trefn $(a,b,c)$ ac un â thri digwyddiad mewn trefn $(x,y,z)$. Os yw'r ddwy broses yn rhedeg yn gydamserol, heb gyfyngiadau ar sut y cydblethir eu gweithredu, yna ceir 20 trefn bosibl wahanol ar gyfer y digwyddiadau sy'n gyson â threfn unigol y ddwy broses:

(a,b,c,x,y,z)  (a,x,b,y,c,z)  (x,a,b,c,y,z)  
(x,a,y,z,b,c)  (a,b,x,c,y,z)  (a,x,b,y,z,c)  
(x,a,b,y,c,z)  (x,y,a,b,c,z)  (a,b,x,y,c,z)  
(a,x,y,b,c,z)  (x,a,b,y,z,c)  (x,y,a,b,z,c)
(a,b,x,y,z,c)  (a,x,y,b,z,c)  (x,a,y,b,c,z)  
(x,y,a,z,b,c)  (a,x,b,c,y,z)  (a,x,y,z,b,c)  
(x,a,y,b,z,c)  (x,y,z,a,b,c)

Fel rhaglenwyr sy'n dylunio'r system hon, byddai'n rhaid inni ystyried effeithiau pob un o'r 20 trefn hyn a gwirio bod pob ymddygiad yn dderbyniol. Buan iawn y daw dull o'r fath yn anhylaw wrth i nifer y prosesau a'r digwyddiadau gynyddu.

Dull mwy ymarferol o ddylunio systemau cydamserol yw dyfeisio mecanweithiau cyffredinol sy'n ein galluogi i gyfyngu ar gydblethu prosesau cydamserol fel y gallwn fod yn sicr bod ymddygiad y rhaglen yn gywir. Datblygwyd llawer o fecanweithiau at y diben hwn. Yn yr adran hon, disgrifiwn un ohonynt, y cyfresolydd.

Cyfresoli mynediad at gyflwr a rennir

Mae cyfresoli yn gweithredu'r syniad canlynol: Bydd prosesau'n gweithredu'n gydamserol, ond bydd rhai casgliadau o weithdrefnau na ellir eu gweithredu'n gydamserol. Yn fwy manwl gywir, mae cyfresoli yn creu setiau penodedig o weithdrefnau fel mai dim ond un gweithrediad o weithdrefn ym mhob set wedi'i chyfresoli a ganiateir ar y tro. Os oes rhyw weithdrefn yn y set yn cael ei gweithredu, yna gorfodir proses sy'n ceisio gweithredu unrhyw weithdrefn yn y set i aros hyd nes y bydd y gweithredu cyntaf wedi gorffen.

Gallwn ddefnyddio cyfresoli i reoli mynediad at newidynnau a rennir. Er enghraifft, os ydym am ddiweddaru newidyn a rennir ar sail gwerth blaenorol y newidyn hwnnw, rhown y cyrchu at werth blaenorol y newidyn ac aseinio'r gwerth newydd iddo yn yr un weithdrefn. Yna sicrhawn na all unrhyw weithdrefn arall sy'n aseinio i'r newidyn redeg yn gydamserol â'r weithdrefn hon drwy gyfresoli'r holl weithdrefnau hyn â'r un cyfresolydd. Mae hyn yn gwarantu na ellir newid gwerth y newidyn rhwng cyrchiad a'r aseiniad cyfatebol.

Cyfresolyddion yn Scheme

I wneud y mecanwaith uchod yn fwy pendant, tybiwch ein bod wedi ymestyn Scheme i gynnwys gweithdrefn o'r enw parallel-execute:

(parallel-execute ⟨p₁⟩ 
                  ⟨p₂⟩ 
                  … 
                  ⟨pₖ⟩)

Rhaid i bob ⟨p⟩ fod yn weithdrefn heb argiau. Mae Parallel-execute yn creu proses ar wahân ar gyfer pob ⟨p⟩, sy'n cymhwyso ⟨p⟩ (i ddim argiau). Mae'r prosesau hyn i gyd yn rhedeg yn gydamserol.¹⁶⁸

Yn enghraifft o sut y defnyddir hyn, ystyriwch

(define x 10)
(parallel-execute (lambda () (set! x (* x x)))
                  (lambda () (set! x (+ x 1))))

Mae hyn yn creu dwy broses gydamserol—$P_1$, sy'n gosod x i x wedi'i luosi ag x, ac $P_2$, sy'n cynyddu x. Ar ôl cwblhau'r gweithredu, bydd gan x un o bum gwerth posibl, yn dibynnu ar gydblethu digwyddiadau $P_1$ ac $P_2$:

101: Mae $P_1$ yn gosod x yn 100 ac yna mae $P_2$ yn cynyddu
     x i 101.
121: Mae $P_2$ yn cynyddu x i 11 ac yna mae $P_1$ yn gosod
     x yn x lluosi x.
110: Mae $P_2$ yn newid x o 10 i 11 rhwng y 
     ddau dro y mae $P_1$ yn cyrchu gwerth 
     x wrth werthuso (* x x).
 11: Mae $P_2$ yn cyrchu x, yna mae $P_1$ yn gosod x yn 100, 
     yna mae $P_2$ yn gosod x.
100: Mae $P_1$ yn cyrchu x (ddwywaith), yna mae $P_2$ yn gosod
     x yn 11, yna mae $P_1$ yn gosod x.

Gallwn gyfyngu ar y cydamseredd drwy ddefnyddio gweithdrefnau wedi'u cyfresoli, a grëir gan gyfresolyddion. Adeiledir cyfresolyddion gan make-serializer, y rhoddir ei weithrediad isod. Mae cyfresolydd yn cymryd gweithdrefn yn arg ac yn dychwelyd gweithdrefn wedi'i chyfresoli sy'n ymddwyn fel y weithdrefn wreiddiol. Mae pob galwad i gyfresolydd penodol yn dychwelyd gweithdrefnau wedi'u cyfresoli yn yr un set.

Felly, yn wahanol i'r enghraifft uchod, mae gweithredu

(define x 10)
(define s (make-serializer))
(parallel-execute 
 (s (lambda () (set! x (* x x))))
 (s (lambda () (set! x (+ x 1)))))

yn gallu cynhyrchu dim ond dau werth posibl i x, sef 101 neu 121. Dilëir y posibiliadau eraill, am na ellir cydblethu gweithredu $P_1$ ac $P_2$.

Dyma fersiwn o'r weithdrefn make-account o 3.1.1, lle mae'r adneuo a'r codi arian wedi'u cyfresoli:

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) 
             (protected withdraw))
            ((eq? m 'deposit) 
             (protected deposit))
            ((eq? m 'balance) 
             balance)
            (else (error "Unknown request: 
                          MAKE-ACCOUNT"
                         m))))
    dispatch))

Gyda'r gweithrediad hwn, ni all dwy broses fod yn codi arian o un cyfrif neu'n adneuo ynddo yn gydamserol. Mae hyn yn dileu ffynhonnell y gwall a ddangosir yn Ffigur 3.29, lle mae Peter yn newid balans y cyfrif rhwng yr adeg y mae Paul yn cyrchu'r balans i gyfrifo'r gwerth newydd a'r adeg y mae Paul yn cyflawni'r aseiniad mewn gwirionedd. Ar y llaw arall, mae gan bob cyfrif ei gyfresolydd ei hun, fel y gall adneuo a chodi arian mewn gwahanol gyfrifon fynd rhagddynt yn gydamserol.

Ymarfer 3.39: Pa rai o'r pum posibilrwydd yn y gweithredu paralel a ddangosir uchod sy'n aros os cyfresolwn y gweithredu fel a ganlyn yn lle hynny:

(define x 10)
(define s (make-serializer))
(parallel-execute 
  (lambda () 
    (set! x ((s (lambda () (* x x))))))
  (s (lambda () (set! x (+ x 1)))))

Ymarfer 3.40: Rhowch holl werthoedd posibl x a all ddeillio o weithredu

(define x 10)
(parallel-execute 
 (lambda () (set! x (* x x)))
 (lambda () (set! x (* x x x))))

Pa rai o'r posibiliadau hyn sy'n aros os defnyddiwn weithdrefnau wedi'u cyfresoli yn lle hynny:

(define x 10)
(define s (make-serializer))
(parallel-execute 
 (s (lambda () (set! x (* x x))))
 (s (lambda () (set! x (* x x x)))))

Ymarfer 3.41: Mae Ben Bitdiddle yn poeni y byddai'n well gweithredu'r cyfrif banc fel a ganlyn (lle mae'r llinell â sylw wedi'i newid):

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin 
          (set! balance 
                (- balance amount))
          balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) 
             (protected withdraw))
            ((eq? m 'deposit) 
             (protected deposit))
            ((eq? m 'balance)
             ((protected 
                (lambda () 
                  balance)))) ; serialized
            (else 
             (error 
              "Unknown request: 
               MAKE-ACCOUNT"
              m))))
    dispatch))

am y gall caniatáu mynediad heb ei gyfresoli at falans y banc arwain at ymddygiad anghyson. A ydych yn cytuno? A oes unrhyw sefyllfa sy'n dangos pryder Ben?

Ymarfer 3.42: Mae Ben Bitdiddle yn awgrymu ei bod yn wastraff amser creu gweithdrefn newydd wedi'i chyfresoli mewn ymateb i bob neges withdraw ac deposit. Dywed y gellid newid make-account fel bod y galwadau i protected yn cael eu gwneud y tu allan i'r weithdrefn dispatch. Hynny yw, byddai cyfrif yn dychwelyd yr un weithdrefn wedi'i chyfresoli (a grëwyd ar yr un pryd â'r cyfrif) bob tro y gofynnir iddo am weithdrefn codi arian.

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (let ((protected-withdraw 
           (protected withdraw))
          (protected-deposit 
           (protected deposit)))
      (define (dispatch m)
        (cond ((eq? m 'withdraw) 
               protected-withdraw)
              ((eq? m 'deposit) 
               protected-deposit)
              ((eq? m 'balance) 
               balance)
              (else 
               (error "Unknown request: 
                       MAKE-ACCOUNT"
                      m))))
      dispatch)))

A yw hwn yn newid diogel i'w wneud? Yn benodol, a oes unrhyw wahaniaeth yn y cydamseredd a ganiateir gan y ddwy fersiwn hyn o make-account?

Cymhlethdod defnyddio sawl adnodd a rennir

Mae cyfresolyddion yn darparu haniaeth bwerus sy'n helpu i ynysu cymhlethdodau rhaglenni cydamserol fel y gellir ymdrin â hwy'n ofalus ac (yn obeithiol) yn gywir. Fodd bynnag, er bod defnyddio cyfresolyddion yn gymharol syml pan nad oes ond un adnodd a rennir (megis un cyfrif banc), gall rhaglennu cydamserol fod yn beryglus o anodd pan fo sawl adnodd a rennir.

I ddangos un o'r anawsterau a all godi, tybiwch ein bod am gyfnewid balansau dau gyfrif banc. Cyrchwn bob cyfrif i ganfod y balans, cyfrifwn y gwahaniaeth rhwng y balansau, codwn y gwahaniaeth hwn o un cyfrif, ac adneuwn ef yn y cyfrif arall. Gallem weithredu hyn fel a ganlyn:¹⁶⁹

(define (exchange account1 account2)
  (let ((difference (- (account1 'balance)
                       (account2 'balance))))
    ((account1 'withdraw) difference)
    ((account2 'deposit) difference)))

Mae'r weithdrefn hon yn gweithio'n dda pan mai dim ond un broses sy'n ceisio gwneud y cyfnewid. Tybiwch, fodd bynnag, fod gan Peter a Paul ill dau fynediad at gyfrifon $a1$, $a2$, ac $a3$, a bod Peter yn cyfnewid $a1$ ac $a2$ tra bod Paul yn cyfnewid $a1$ ac $a3$ yn gydamserol. Hyd yn oed gydag adneuo a chodi arian wedi'u cyfresoli ar gyfer cyfrifon unigol (fel yn y weithdrefn make-account a ddangosir uchod yn yr adran hon), gall exchange ddal i gynhyrchu canlyniadau anghywir. Er enghraifft, gallai Peter gyfrifo'r gwahaniaeth rhwng balansau $a1$ ac $a2$, ond yna gallai Paul newid y balans yn $a1$ cyn i Peter allu cwblhau'r cyfnewid.¹⁷⁰ Er mwyn cael ymddygiad cywir, rhaid inni drefnu i'r weithdrefn exchange atal unrhyw gyrchiadau cydamserol eraill at y cyfrifon drwy gydol amser y cyfnewid.

Un ffordd o gyflawni hyn yw defnyddio cyfresolyddion y ddau gyfrif i gyfresoli'r weithdrefn exchange gyfan. I wneud hyn, byddwn yn trefnu mynediad at gyfresolydd cyfrif. Sylwch ein bod yn torri modiwlaredd gwrthrych y cyfrif banc yn fwriadol drwy amlygu'r cyfresolydd. Mae'r fersiwn ganlynol o make-account yn union yr un fath â'r fersiwn wreiddiol a roddir yn 3.1.1, ac eithrio bod cyfresolydd yn cael ei ddarparu i ddiogelu'r newidyn balans, a bod y cyfresolydd yn cael ei allforio drwy drosglwyddo negeseuon:

(define (make-account-and-serializer balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin 
          (set! balance (- balance amount))
          balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer 
         (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) 
             balance-serializer)
            (else (error "Unknown request: 
                          MAKE-ACCOUNT"
                         m))))
    dispatch))

Gallwn ddefnyddio hyn i adneuo a chodi arian drwy gyfresoli. Fodd bynnag, yn wahanol i'n cyfrif wedi'i gyfresoli cynharach, cyfrifoldeb pob defnyddiwr o wrthrychau cyfrif banc bellach yw rheoli'r cyfresoli'n benodol, er enghraifft fel a ganlyn:¹⁷¹

(define (deposit account amount)
  (let ((s (account 'serializer))
        (d (account 'deposit)))
    ((s d) amount)))

Mae allforio'r cyfresolydd fel hyn yn rhoi digon o hyblygrwydd inni weithredu rhaglen gyfnewid wedi'i chyfresoli. Dim ond cyfresoli'r weithdrefn exchange wreiddiol â chyfresolyddion y ddau gyfrif a wnawn:

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer)))
    ((serializer1 (serializer2 exchange))
     account1
     account2)))

Ymarfer 3.43: Tybiwch fod balansau tri chyfrif yn dechrau'n $10, $20, a $30, a bod sawl proses yn rhedeg, yn cyfnewid balansau'r cyfrifon. Dadleuwch, os rhedir y prosesau'n ddilyniannol, y dylai balansau'r cyfrifon fod yn $10, $20, a $30 mewn rhyw drefn ar ôl unrhyw nifer o gyfnewidiadau cydamserol. Tynnwch ddiagram amseru fel yr un yn Ffigur 3.29 i ddangos sut y gellir torri'r amod hwn os gweithredir y cyfnewidiadau gan ddefnyddio fersiwn gyntaf y rhaglen cyfnewid cyfrifon yn yr adran hon. Ar y llaw arall, dadleuwch y bydd swm balansau'r cyfrifon yn cael ei gadw hyd yn oed gyda'r rhaglen exchange hon. Tynnwch ddiagram amseru i ddangos sut y byddai hyd yn oed yr amod hwn yn cael ei dorri pe na baem yn cyfresoli'r trafodion ar gyfrifon unigol.

Ymarfer 3.44: Ystyriwch y broblem o drosglwyddo swm o un cyfrif i un arall. Mae Ben Bitdiddle yn honni y gellir cyflawni hyn â'r weithdrefn ganlynol, hyd yn oed os oes sawl person yn trosglwyddo arian yn gydamserol rhwng sawl cyfrif, gan ddefnyddio unrhyw fecanwaith cyfrif sy'n cyfresoli trafodion adneuo a chodi arian, er enghraifft, y fersiwn o make-account yn y testun uchod.

(define 
  (transfer from-account to-account amount)
  ((from-account 'withdraw) amount)
  ((to-account 'deposit) amount))

Mae Louis Reasoner yn honni bod problem yma, a bod angen inni ddefnyddio dull mwy soffistigedig, fel yr un sydd ei angen i ymdrin â'r broblem gyfnewid. A yw Louis yn iawn? Os nad yw, beth yw'r gwahaniaeth hanfodol rhwng y broblem drosglwyddo a'r broblem gyfnewid? (Dylech dybio bod y balans yn from-account o leiaf yn amount.)

Ymarfer 3.45: Mae Louis Reasoner yn meddwl bod ein system cyfrifon banc yn ddiangen o gymhleth ac yn dueddol o wallau bellach, gan nad yw adneuo a chodi arian yn cael eu cyfresoli'n awtomatig. Mae'n awgrymu y dylai make-account-and-serializer fod wedi allforio'r cyfresolydd (i'w ddefnyddio gan weithdrefnau fel serialized-exchange) yn ogystal â (yn hytrach nag yn lle) ei ddefnyddio i gyfresoli cyfrifon ac adneuon fel y gwnaeth make-account. Mae'n cynnig ailddiffinio cyfrifon fel a ganlyn:

(define 
  (make-account-and-serializer balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer 
         (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) 
             (balance-serializer withdraw))
            ((eq? m 'deposit) 
             (balance-serializer deposit))
            ((eq? m 'balance) 
             balance)
            ((eq? m 'serializer) 
             balance-serializer)
            (else (error "Unknown request: 
                          MAKE-ACCOUNT"
                         m))))
    dispatch))

Yna trinnir adneuon fel gyda'r make-account gwreiddiol:

(define (deposit account amount)
  ((account 'deposit) amount))

Esboniwch beth sydd o'i le ar resymu Louis. Yn benodol, ystyriwch beth sy'n digwydd pan elwir serialized-exchange.

Gweithredu cyfresolyddion

Gweithredwn gyfresolyddion yn nhermau mecanwaith cydamseru mwy cyntefig o'r enw clo cyd-eithrio (mutex). Gwrthrych sy'n cefnogi dau weithrediad yw clo cyd-eithrio—gellir caffael y clo, a gellir rhyddhau y clo. Unwaith y caffaelir clo cyd-eithrio, ni chaiff unrhyw weithrediadau caffael eraill ar y clo hwnnw fynd rhagddynt nes rhyddhau'r clo.¹⁷² Yn ein gweithrediad, mae gan bob cyfresolydd glo cyd-eithrio cysylltiedig. O gael gweithdrefn p, mae'r cyfresolydd yn dychwelyd gweithdrefn sy'n caffael y clo cyd-eithrio, yn rhedeg p, ac yna'n rhyddhau'r clo. Mae hyn yn sicrhau mai dim ond un o'r gweithdrefnau a gynhyrchir gan y cyfresolydd a all fod yn rhedeg ar unwaith, sef yn union y briodwedd gyfresoli y mae angen inni ei gwarantu.

(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
        (mutex 'acquire)
        (let ((val (apply p args)))
          (mutex 'release)
          val))
      serialized-p)))

Gwrthrych newidiadwy yw'r clo cyd-eithrio (yma defnyddiwn restr un elfen, y cyfeiriwn ati fel cell) a all ddal y gwerth gwir neu anwir. Pan fo'r gwerth yn anwir, mae'r clo cyd-eithrio ar gael i'w gaffael. Pan fo'r gwerth yn wir, nid yw'r clo ar gael, a rhaid i unrhyw broses sy'n ceisio ei gaffael aros.

Mae ein hadeiladydd clo cyd-eithrio make-mutex yn dechrau drwy gychwyn cynnwys y gell i anwir. I gaffael y clo, profwn y gell. Os yw'r clo ar gael, gosodwn gynnwys y gell i wir ac awn ymlaen. Fel arall, arhoswn mewn dolen, gan geisio ei gaffael dro ar ôl tro, nes canfod bod y clo ar gael.¹⁷³ I ryddhau'r clo cyd-eithrio, gosodwn gynnwys y gell i anwir.

(define (make-mutex)
  (let ((cell (list false)))
    (define (the-mutex m)
      (cond ((eq? m 'acquire)
             (if (test-and-set! cell)
                 (the-mutex 'acquire))) ; retry
            ((eq? m 'release) (clear! cell))))
    the-mutex))
(define (clear! cell) (set-car! cell false))

Mae Test-and-set! yn profi'r gell ac yn dychwelyd canlyniad y prawf. Yn ogystal, os oedd y prawf yn anwir, mae test-and-set! yn gosod cynnwys y gell i wir cyn dychwelyd anwir. Gallwn fynegi'r ymddygiad hwn fel y weithdrefn ganlynol:

(define (test-and-set! cell)
  (if (car cell)
      true
      (begin (set-car! cell true)
             false)))

Fodd bynnag, nid yw'r gweithrediad hwn o test-and-set! yn ddigonol fel y mae. Mae cynnildeb hollbwysig yma, sef y man hanfodol lle mae rheoli cydamseredd yn dod i mewn i'r system: Rhaid cyflawni'r gweithrediad test-and-set! yn atomig. Hynny yw, rhaid inni warantu, unwaith y mae proses wedi profi'r gell a chanfod ei bod yn anwir, y bydd cynnwys y gell yn cael ei osod i wir mewn gwirionedd cyn y gall unrhyw broses arall brofi'r gell. Os na rown y warant hon, yna gall y clo cyd-eithrio fethu mewn ffordd debyg i fethiant y cyfrif banc yn Ffigur 3.29. (Gweler Ymarfer 3.46.)

Mae union weithrediad test-and-set! yn dibynnu ar fanylion sut y mae ein system yn rhedeg prosesau cydamserol. Er enghraifft, gallem fod yn gweithredu prosesau cydamserol ar brosesydd dilyniannol gan ddefnyddio mecanwaith rhannu amser yn dafelli sy'n cylchdroi drwy'r prosesau, gan ganiatáu i bob proses redeg am gyfnod byr cyn torri ar ei thraws a symud ymlaen i'r broses nesaf. Yn yr achos hwnnw, gall test-and-set! weithio drwy analluogi rhannu amser yn dafelli yn ystod y profi a'r gosod.¹⁷⁴ Fel arall, mae cyfrifiaduron amlbrosesu yn darparu cyfarwyddiadau sy'n cefnogi gweithrediadau atomig yn uniongyrchol yn y caledwedd.¹⁷⁵

Ymarfer 3.46: Tybiwch ein bod yn gweithredu test-and-set! gan ddefnyddio gweithdrefn gyffredin fel y dangosir yn y testun, heb geisio gwneud y gweithrediad yn atomig. Tynnwch ddiagram amseru fel yr un yn Ffigur 3.29 i ddangos sut y gall y gweithrediad o glo cyd-eithrio fethu drwy ganiatáu i ddwy broses gaffael y clo ar yr un pryd.

Ymarfer 3.47: Cyffredinoliad o glo cyd-eithrio yw semaffor (o faint $n$). Fel clo cyd-eithrio, mae semaffor yn cefnogi gweithrediadau caffael a rhyddhau, ond mae'n fwy cyffredinol yn yr ystyr y gall hyd at $n$ o brosesau ei gaffael yn gydamserol. Rhaid i brosesau ychwanegol sy'n ceisio caffael y semaffor aros am weithrediadau rhyddhau. Rhowch weithrediadau o semafforau

1. yn nhermau cloeon cyd-eithrio
2. yn nhermau gweithrediadau test-and-set! atomig.

Cydglo

Nawr ein bod wedi gweld sut i weithredu cyfresolyddion, gallwn weld bod problem o hyd gyda chyfnewid cyfrifon, hyd yn oed â'r weithdrefn serialized-exchange uchod. Dychmygwch fod Peter yn ceisio cyfnewid $a1$ ag $a2$ tra bod Paul yn ceisio cyfnewid $a2$ ag $a1$ yn gydamserol. Tybiwch fod proses Peter yn cyrraedd y pwynt lle mae wedi mynd i mewn i weithdrefn wedi'i chyfresoli sy'n diogelu $a1$ ac, yn union ar ôl hynny, fod proses Paul yn mynd i mewn i weithdrefn wedi'i chyfresoli sy'n diogelu $a2$. Nawr ni all Peter fynd ymlaen (i mewn i weithdrefn wedi'i chyfresoli sy'n diogelu $a2$) nes i Paul adael y weithdrefn wedi'i chyfresoli sy'n diogelu $a2$. Yn yr un modd, ni all Paul fynd ymlaen nes i Peter adael y weithdrefn wedi'i chyfresoli sy'n diogelu $a1$. Mae pob proses wedi'i hatal am byth, yn aros am y llall. Gelwir y sefyllfa hon yn gydglo (deadlock). Mae cydglo bob amser yn berygl mewn systemau sy'n darparu mynediad cydamserol at sawl adnodd a rennir.

Un ffordd o osgoi'r cydglo yn y sefyllfa hon yw rhoi rhif adnabod unigryw i bob cyfrif ac ailysgrifennu serialized-exchange fel y bydd proses bob amser yn ceisio mynd i mewn i weithdrefn sy'n diogelu'r cyfrif â'r rhif isaf yn gyntaf. Er bod y dull hwn yn gweithio'n dda ar gyfer y broblem gyfnewid, mae sefyllfaoedd eraill yn gofyn am dechnegau mwy soffistigedig i osgoi cydglo, neu sefyllfaoedd lle na ellir osgoi cydglo o gwbl. (Gweler Ymarfer 3.48 ac Ymarfer 3.49.)¹⁷⁶

Ymarfer 3.48: Esboniwch yn fanwl pam mae'r dull osgoi cydglo a ddisgrifir uchod (h.y., rhifir y cyfrifon, ac mae pob proses yn ceisio caffael y cyfrif â'r rhif lleiaf yn gyntaf) yn osgoi cydglo yn y broblem gyfnewid. Ailysgrifennwch serialized-exchange i gynnwys y syniad hwn. (Bydd angen ichi hefyd addasu make-account fel y crëir pob cyfrif â rhif, y gellir ei gyrchu drwy anfon neges briodol.)

Ymarfer 3.49: Rhowch sefyllfa lle nad yw'r mecanwaith osgoi cydglo a ddisgrifir uchod yn gweithio. (Awgrym: Yn y broblem gyfnewid, mae pob proses yn gwybod ymlaen llaw pa gyfrifon y bydd angen iddi eu cyrchu. Ystyriwch sefyllfa lle mae'n rhaid i broses gael mynediad at rai adnoddau a rennir cyn y gall wybod pa adnoddau ychwanegol a rennir y bydd eu hangen arni.)

Cydamseredd, amser, a chyfathrebu

Rydym wedi gweld sut mae rhaglennu systemau cydamserol yn gofyn am reoli trefn digwyddiadau pan fydd gwahanol brosesau'n cyrchu cyflwr a rennir, ac rydym wedi gweld sut i gyflawni'r rheolaeth hon drwy ddefnyddio cyfresolyddion yn ddoeth. Ond mae problemau cydamseredd yn ddyfnach na hyn, am nad yw bob amser yn eglur, o safbwynt sylfaenol, beth a olygir wrth “gyflwr a rennir.”

Mae mecanweithiau fel test-and-set! yn gofyn i brosesau archwilio baner fyd-eang a rennir ar adegau mympwyol. Mae hyn yn broblemus ac yn aneffeithlon i'w weithredu mewn prosesyddion cyflym modern, lle gall cynnwys y cof beidio â bod mewn cyflwr cyson ar bob amrantiad oherwydd technegau optimeiddio megis piblinellu a chof celc. Mewn systemau amlbrosesu cyfoes, felly, mae dulliau newydd o reoli cydamseredd yn disodli paradeim y cyfresolydd.¹⁷⁷

Mae agweddau problemus cyflwr a rennir hefyd yn codi mewn systemau mawr, dosbarthedig. Er enghraifft, dychmygwch system fancio ddosbarthedig lle mae canghennau banc unigol yn cadw gwerthoedd lleol ar gyfer balansau banc ac yn cymharu'r rhain o bryd i'w gilydd â gwerthoedd a gedwir gan ganghennau eraill. Mewn system o'r fath, byddai gwerth “balans y cyfrif” heb ei bennu, ac eithrio yn union ar ôl cydamseru. Os yw Peter yn adneuo arian mewn cyfrif sydd ganddo ar y cyd â Paul, pryd y dylem ddweud bod balans y cyfrif wedi newid—pan fydd y balans yn y gangen leol yn newid, neu ddim tan ar ôl cydamseru? Ac os yw Paul yn cyrchu'r cyfrif o gangen wahanol, pa gyfyngiadau rhesymol y dylid eu gosod ar y system fancio fel bod yr ymddygiad yn “gywir”? Efallai mai'r unig beth sy'n bwysig i gywirdeb yw'r ymddygiad a welir gan Peter a Paul yn unigol a “chyflwr” y cyfrif yn union ar ôl cydamseru. Gall cwestiynau am falans “gwirioneddol” y cyfrif neu drefn digwyddiadau rhwng cyfnodau cydamseru fod yn amherthnasol neu'n ddiystyr.¹⁷⁸

Y ffenomen sylfaenol yma yw bod cydamseru gwahanol brosesau, sefydlu cyflwr a rennir, neu osod trefn ar ddigwyddiadau yn gofyn am gyfathrebu rhwng y prosesau. Yn ei hanfod, rhaid i unrhyw syniad o amser wrth reoli cydamseredd fod â chysylltiad agos iawn â chyfathrebu.¹⁷⁹ Mae'n ddiddorol fod cysylltiad tebyg rhwng amser a chyfathrebu hefyd yn codi yn Namcaniaeth Perthnasedd, lle mae buanedd golau (y signal cyflymaf y gellir ei ddefnyddio i gydamseru digwyddiadau) yn gysonyn sylfaenol sy'n cysylltu amser a gofod. Gall y cymhlethdodau a wynebwn wrth ymdrin ag amser a chyflwr yn ein modelau cyfrifiadurol adlewyrchu, mewn gwirionedd, gymhlethdod sylfaenol y bydysawd ffisegol.

(define (test-and-set! cell)
  (without-interrupts
   (lambda ()
     (if (car cell)
         true
         (begin (set-car! cell true)
                false)))))