Kriitiline intervall - Sissejuhatus

Kriitiline intervall
Et mitu paralleelset protsessi saaks korraga olla aktiivsed on vaja mehanismi nende töö sünkroniseerimiseks. Ka teineteisest sõltumatud protsessid pöörduvad aeg-ajalt ühiste ressursside poole (näiteks mälu). Et ainult üks protsess saaks korraga selliste ressursside poole pöörduda, jagatakse kõik protsesid kriitilisteks intervallideks. Kriitilises intervallis saab olla korraga ainult üks protsess, s.t. kui üks protsess mingit ressurssi kasutab, on teistel keelatud seda teha.
Lukud(locks)
Lukud on kõige lihtsam viis kriitiliste intervallide vastastikuseks välistamiseks. Lukk on 1bitine muutuja. Kui tema väärtus on 1 siis see näitab, et protsess on sisenenud kriitilisse intervalli (lukk on kinni). Kui luku väärtus on 1, siis pole ühtegi protsessi parajasti kriitlises intervallis (lukk on lahti). Kui protsess soovib siseneda kriitilisse intervalli peab ta kõigepealt kontrollima, millises seisus on lukk. Kui lukk onl lahti, siseneb protsess kriitilisse intervalli ja suleb luku. Kriitilisest intervallist väljudes teeb ta luku uuesti lahti. Kui protsess tahab siseneda kriitilisse intervalli, aga lukk on kinni, siis ta peab ootama. Kõige lihtsamal juhul ta lihtsalt kontrollib pidevalt, kas lukk on juba lahti (busy waiting), tehes samal ajal mitte midagi muud kasulikku. Kui rohkem kui üks protsess ootab luku avanemist, võib olla vaja mehanismi, mis avanemisel annaks kriitilisse intervalli sisenemise õiguse kõige suurema prioriteediga protsessile. On oluline, et protsessi ei saaks katkestada luku kontrollimise ja intervalli sisenemise vahepeal, s.t, et ei tekiks olukorda, kus protsess on avastanud, et lukk on lahti, kuid kriitilisse intervalli sisenemisel leiab, et teine protsess on temast ette jõudnud. Paljudel protsessoritel on luku avamiseks ja lukustamiseks nähtamatud masinkäsud, millede täitmine on realiseeritud riistvaraliselt.
LOCK
LOCK käsu puhul genereeritakse LOCK signaal selle ja järgmise käsu (luku lukustamise) ajaks. LOCK signaal keelab riistvaraliselt selle signaali ajal täidetava käsu katkestamise.
Test And Set(TAS)
Käsul Test And Set on kuju
TAS mälu aaderss
TAS kontrollib, milline väärtus on selle aadressil ja seejärel muudab väärtuse 1ks, s.t suleb luku vaatamata sellele, kas ta oli juba enne suletud või mitte.
Semafoorid
Semafoor s võib omada kas positiivset täisarvulist väärtust või olla null. Semafooril on defineeritud kaks operatsiooni - P ja V:
P(S): kui s=0, siis protsessi täitmine lükatakse edasi seniks, kui s on positiivne. Kui s on positiivne arv, siis tema väärtust vähendatakse ühe võrra ja protsess võib jätkata.
V(S): suurendab semafoori väärtust 1 võrra.
Kahendsemafoori puhul võib s omada ainult väärtusi 1 ja 0. Kui s=1, siis pole ühtegi protsessi kriitilises intervallis. Kui siis mõni protsess soovib siseneda kriitilisse intervalli, omistab ta semafoorile väärtuse s=0. Siis ei saa enam ükski protsess kriitilisse intervalli siseneda, kuid kõik protsessid, mis seda teha sooviksid, pannakse järjekorda ootama. Kui protsess väljub kriitilisest intervallist rakendab ta V(s) operaatorit, lubades sellega sieseneda järgmisel protsessil:
P(s)
Kriitiline intervall
V(s)
Semafoorid aitavad vältida surnud seisu. Surnud seis tekib siis, kui kõik protsessid tahavad kasutada mõnda ressurssi, kuid see on parajasti hõivatud mõne teise poolt ja ükski protsess ei saa jätkata. Nälgimine tekib siis, kui üks või osa protsesse ei saa jätkata, sest teised protsessid hoiavad vajaminevaid resursse kinni.
Monitorid
Monitoride kasutamise puhul saab ressursi kasutamine toimuda ainult monitori kaudu. Igal ajahetkel võib ainult üks protsess monitori kasutada. Kui protsess tahab kasutada monitori, mis on parasjagu kasutusel teise protsessi poolt, pannakse ta järjekorda ootama kuni monitor vabaneb. Monitori vabanemisel saab seda kasutada esimene protsess järjekorrast.
Ühissiiniga multiprotsessorsüsteemid
Ühise siini külge on ühendatud nii protsessorid kui mälumoodulid. Mälumoodulid kokku moodustavad kogu süsteemi ühise mälu, millele on ligipääs kõikidel protsessoritel. Siini saab kasutada korraga ainult üks protsessor. Protsessorit, millel on parasjagu siini kasutamise õigus, nimetatakse siini haldajaks (bus master). Kui protsessor soovib siini haldamise õigust, saadab ta päringu (bus request) siini haldajale. Kui haldaja on siini kasutamise lõpetanud saadab ta kasutamiset taotlevale protsessorile kinnitussignaali (bus grant) ja kasutamist taotlev protsessor saab uueks siini haldajaks. Tihti kasutatakse ka signaali bus busy, millega siini haldur võib vastata, kui ta pole siini kasutamist veel lõpetanud.
Kui siini soovib kasutada korraga mitu protsessorit, on vaja mehanismi konfliktide lahendamiseks (siini arbitreerimiseks). Arbitreerimine jaotatakse paralleelseks ja järjestikuliseks ning ka tsentraliseerituks ja detsentraliseerituks.
Protsessorite prioriteedid võivad olla kas staatilised või dünaamilised. Staatiliste prioriteetide puhul on igal protsessoril alati üks ja sama prioriteet. Dünaamiliste prioriteetide puhul nende järjestust muudetakse, et anda kõigile protsessoritele siini kasutamise võimalus. Sünkroonsete süsteemid puhul võib siini kasutamine olla jaotatud võrdselt kõigi protsessorite vahel nii, et igal protsessoril on oma kindel ajaintervall siini kasutamiseks.
|