Teknologian jakaminen

OS_Synchronization and Mutual Exclusion

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

2024-07-04: Käyttöjärjestelmän synkronointi ja keskinäinen poissulkeminen -tutkimuksen muistiinpanot


Samanaikaiset prosessit tai ohjelmat menettävät sulkemisensa suoritettaessa. Eli jos kaksi ohjelmaa käyttävät yhteistä resurssia eri alueilla, kunkin ajon tulokset voivat olla erilaisia.
Lisää kuvan kuvaus tähän
Syynä on se, että emme suojanneet jaettua resurssia x, jota sekä ohjelman a että ohjelman b on käytettävä.


9.1 Synkronoinnin ja keskinäisen poissulkemisen peruskäsitteet

9.1.1 Synkronointisuhde

Toisiaan rajoittava suhde on synkronointi Yksinkertainen käsitys synkronoinnista on, että prosessien suorittamisessa on oltava järjestys.
Lisää kuvan kuvaus tähän


9.1.2 Toisensa poissulkeva suhde

Suhdetta, joka epäsuorasti rajoittaa toisiaan, kutsutaan toisensa poissulkevaksi suhteeksi, esim
Lisää kuvan kuvaus tähän


9.1.3 Kriittiset resurssit

  • Resursseja, joita vain yksi prosessi saa käyttää tietyn ajanjakson sisällä, kutsutaan kriittisiksi resursseiksi (tai yksinomaisiksi resursseiksi).
  • Kriittisten resurssien jakamiseen tulisi käyttää molemminpuolista poissulkemista prosessien välillä

"Tuottaja- ja kuluttajamalli"
Lisää kuvan kuvaus tähänlaskuri++

首先把变量放到寄存器里面
register1 = counter;
接下来对寄存器进行一个自增
register1 = register1 + 1;
再把结果返回到counter里
counter = register1;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

laskuri- -

首先把变量放到寄存器里面
register2 = counter;
接下来对寄存器进行一个自减
register2 = register2 - 1;
再把结果返回到counter里
counter = register2;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

Lisää kuvan kuvaus tähän

Ratkaisu: Käsittele laskuria kriittisenä resurssina ja anna prosessin käyttää muuttujalaskuria keskenään (synkronointimekanismin opit myöhemmin)


9.1.4 Kriittinen osa

Olipa kyseessä laitteistokriittinen resurssi tai ohjelmistokriittinen resurssi, useiden prosessien on käytettävä sitä keskenään.
Lisää kuvan kuvaus tähän
Nämä alueet ovat pohjimmiltaan koodeja

  • Sisääntuloalue
  • kriittinen jakso
  • Poistumisalue
  • jäljellä oleva alue

9.1.5 Synkronointimekanismien tulee noudattaa sääntöjä

  • Vapaa päästää sisään

Kun kriittisessä osassa ei ole prosessia, se osoittaa, että kriittisen osan resurssit ovat käyttämättömiä. Prosessin, joka pyytää pääsyä kriittiseen osioon, tulee päästää välittömästi omaan kriittiseen osioon resurssien tehokkaaksi hyödyntämiseksi.

  • Jos olet kiireinen, odota

Kun olemassa oleva prosessi tulee kriittiseen osioon, se osoittaa, että kriittistä resurssia käytetään. Siksi muiden kriittiseen osaan pääsyä yrittävien prosessien on odotettava varmistaakseen toisensa poissulkevan pääsyn kriittiseen resurssiin.

  • rajoitettu odotus

Niiden prosessien osalta, jotka edellyttävät pääsyä kriittisiin resursseihin, heidän tulee varmistaa, että ne pääsevät omaan kriittiseen osioonsa rajoitetun ajan sisällä, jotta ne eivät joutuisi "odottaa kuolemaa" -tilaan.

  • anna periksi ja odota

Kun prosessi ei pääse omaan kriittiseen osaansa, prosessori (CPU) on vapautettava välittömästi, jotta prosessi ei putoa "varattu odottavaan" -tilaan.


9.2 Ohjelmiston synkronointimekanismi

9.2.1 Yhden merkin menetelmä

  • Aseta julkinen kokonaislukumuuttuja, joka ilmaisee, onko kriittisessä osassa prosessi, se odottaa silmukkatarkistuksen läpi syöttöalueella muutetaan poistumisalueella.
  • Yhden lipun menetelmä asettaa julkisen kokonaislukumuuttujan osoittamaan prosessin numeroa, joka saa tulla kriittiseen osaan. Kun turn=0, prosessi P0 saa tulla kriittiseen osaan.
  • Kun käännös=1, prosessi P1 pääsee kriittiseen osuuteen ja kriittisestä osiosta poistuttaessa kriittisen osan käyttöoikeus annetaan toiselle prosessille (kun Pi poistuu kriittisestä osiosta, käännös=j)

Lisää kuvan kuvaus tähän
Lisää kuvan kuvaus tähän
两个进程必须交替进入临界区,若一个进程不再进入临界区,则另一个进程也无法进入临界区,违背了“空闲让进”准则


9.2.2 Kaksoispisteen ensimmäinen tarkistusmenetelmä

Kaksoislipun ensimmäinen tarkistusmenetelmä asettaa Boolen taulukon lipun[2] merkitsemään kunkin prosessin halukkuutta siirtyä kriittiseen osioon lippu[i]=true tarkoittaa, että Pi haluaa siirtyä kriittiseen osaan.

  • Ennen kuin Pi siirtyy kriittiseen osioon, tarkista ensin, onko toinen osapuoli siirtynyt kriittiseen osioon
  • Muussa tapauksessa aseta lippu[i] arvoon tosi ennen kriittiseen osaan siirtymistä
  • Kun Pi poistuu kriittisestä osasta, aseta lippu[i] arvoon false

Lisää kuvan kuvaus tähän

Lisää kuvan kuvaus tähän

  • While-silmukka vastaa liikennevalomekanismia
  • Toisen osapuolen lipun asettaminen vastaa toisen osapuolen liikennevalon vaihtamista.
  • Koska molemmat prosessit kuitenkin tarkistavat lipun ensin [katso liikennevaloa ensin] ja molemmat ovat aluksi vääriä [molemmat vihreät valot], on mahdollista, että molemmat prosessit ohittavat liikennevalon samanaikaisesti ja tulevat kriittiseen osaan yhdessä .

9.2.3 Kaksoispisteen jälkitarkastusmenetelmä

Kaksoislipun jälkitarkistusmenetelmä tarkistaa toisen osapuolen lipun ja asettaa sitten oman. Näitä kahta toimintoa ei voi tehdä yhdellä kertaa, joten nämä kaksi prosessia voivat siirtyä kriittiseen osioon samaan aikaan jälkitarkistusmenetelmä, joka asettaa ensin oman lipun ja sitten tarkistaa toisen osapuolen lipun, jos toisen osapuolen lippu on tosi, siirry kriittiseen osioon

Lisää kuvan kuvaus tähän
Lisää kuvan kuvaus tähän


9.2.4 Peterson-algoritmi

Petersonin algoritmi yhdistääyhden merkin menetelmäjaKaksoispisteen jälkitarkastusmenetelmäAjatuksena on käyttää lippua [] ratkaistakseen toisensa poissulkevan pääsyongelman ja käyttää turnaa nälkäongelman ratkaisemiseen.

Jos molemmat osapuolet kilpailevat pääsystä kriittiseen osioon, voidaan prosessin antaa toiselle osapuolelle mahdollisuus päästä kriittiseen osaan.
Ennen kuin kukin prosessi siirtyy kriittiseen osioon, se asettaa oman lippunsa ja asettaa vuorolipun, jonka jälkeen se tunnistaa toisen osapuolen lipun ja käännöksen samanaikaisesti varmistaakseen, että vain yksi prosessi pääsee sisään. molemmat osapuolet pyytävät pääsyä kriittiseen osioon samanaikaisesti.
Lisää kuvan kuvaus tähän
Odotusoikeudesta luopumatta jättäminen
Lisää kuvan kuvaus tähän


9.3 Laitteiston synkronointimekanismi

Ohjelmiston on vaikea ratkaista ongelmaa, jonka mukaan jokainen prosessi ei pääse kriittiseen osioon, ja sillä on suuria rajoituksia. Siksi tietokone tarjoaa joitain erityisiä laitteistoohjeita ongelman ratkaisemiseksi.

9.3.1 Kytke keskeytykset pois päältä

(1) Keskeytysten poiskytkennän määritelmä

  • Keskeytysten poistamista on käsitelty tietokoneen kokoonpanon periaatteissa. Se viittaa bitin muokkaamiseen CPU:ssa, keskeytyykö nykyinen CPU pysäytettävä
  • Käyttöjärjestelmän prosessien ajoitus perustuu keskeytyksiin, kuten kellokeskeytykseen.
  • Kriittisen osan prosessin suorittamisen aikana tietokonejärjestelmä sulkee keskeytykset, jotka eivät laukaise ajoitusta ja prosessia tai säiettä ei tapahdu.

(2) Keskeytysten poistamisen haitat

  • Päätteiden väärinkäyttö voi johtaa vakaviin seurauksiin
  • Jos sammutusaika on liian pitkä, se vaikuttaa järjestelmän tehokkuuteen.
  • Keskeytysten poistaminen käytöstä ei koske usean prosessorin järjestelmiä.

9.3.2 Testaa ja aseta -komento (TS-komento)

Lisää kuvan kuvaus tähän

TS-käskyä voidaan pitää funktioprosessina (primitiivinä), jonka suoritusprosessi on jakamaton.

  • lukolla on kaksi tilaa:
    • *lock=FALSE osoittaa, että resurssi on ilmainen
    • *lock=TRUE osoittaa, että resurssia käytetään

Käytä TS:ää kriittisten osien hallintaan ja lukituksen asettamiseen jokaiselle kriittiselle resurssille.

  • Alkuarvo on EPÄTOSI, mikä tarkoittaa, että kriittiset resurssit ovat käyttämättömänä.
  • Ennen kuin prosessi siirtyy kriittiseen osioon, se testaa lukon ensin TS:n avulla. Jos se on EPÄTOSI, se voi syöttää arvon TOSI lukolle ja sulkea kriittisen resurssin.

9.3.3 Vaihda komento

Lisää kuvan kuvaus tähän
Sitä kutsutaan vaihtokäskyksi ja sitä käytetään kahden sanan sisällön vaihtamiseen.

  • Aseta globaali Boolen muuttujan lukitus jokaiselle kriittiselle resurssille, jonka alkuarvo on FALSE.
  • Käytä yllä olevia laitteisto-ohjeita prosessin vastavuoroisen poissulkemisen suorittamiseksi loppuun
  • Tämä menetelmä aiheuttaa kuitenkin myös pääsyprosessin jatkuvan testaamisen ja "varatussa odotustilassa", mikä ei ole "oikea odotus" -periaatteen mukainen.

9.4 Semaforimekanismi

9.4.1 Kokonaislukusemafori

Se määritellään kokonaislukuna S, jota käytetään edustamaan resurssien määrää. Tälle kokonaislukusemaforille on vain kolme toimintoa: alustus (alkuarvon määrittäminen), odotus (vähennys), signaali (lisäys).
Lisää kuvan kuvaus tähän

  • Sekä odotus että signaali ovat ydintoimintoja, eikä niitä voi keskeyttää suorituksen aikana.
  • Kun prosessi muokkaa semaforia, mikään muu prosessi ei voi muokata semaforia samanaikaisesti.

9.4.2 Tallenna semafori

Prosessin synkronointimekanismi ilman "varattu odotus" -ilmiötä

  • Kokonaislukumuuttujan arvon lisäksi, jota käytetään edustamaan resurssien määrää
  • On myös tarpeen lisätä prosessiin linkitetty luettelo L linkittääksesi kaikki resurssia odottavat prosessit.

Lisää kuvan kuvaus tähän

  • Odotustoiminto vastaa P-operaatiota
  • Signaalitoiminta vastaa V-toimintoa
  • Vain kaksi eri nimeä, toiminnot ovat täsmälleen samat
  • odota(A) = P(A)
  • signaali(B) = V(A)

(1) Käytä semaforia toteuttaaksesi prosessin keskinäisen poissulkemisen

Aseta toisensa poissulkeva semafori mutex=1 ja aseta sitten kriittinen osa kullekin prosessille kriittisten resurssien käyttämiseksi odotus(mutex) ja signaali(mutex) välillä.
Lisää kuvan kuvaus tähän


(2) Käytä semaforeja saavuttaaksesi prosessin synkronoinnin

Aseta synkronointisemaforiksi S=0, jotta ensin suoritettava käskysignaali(S) ja sitten odotus(S)
Lisää kuvan kuvaus tähän