14. tétel Flashcards
(14 cards)
Folyamat (process)
a multiprogramozott OS rendszerek alapfogalma, végrehajtás alatt álló program.
Multitaskos rendszerben több folyamat végrehajtása zajlik egyidejűleg, de a CPU-n egyszerre csak egy futhat (a CPU kitüntetett erőforrás).
Folyamatok modellezése:
a) Multiprogramozott rendszer (1 PC)
b) Valódi párhuzamos rendszer (4 PC)
c) Folyamatok időbeli eloszlása multiprogramozott rendszerben
Mivel több folyamatra csak egy CPU jut és egy adott pillanatban csak egy program hajtódik végre, ezért a párhuzamosság csak látszólagos, és a CPU kitüntetett erőforrás lesz.
Állapotátmeneti gráf
Egy folyamat életciklusát az ún. állapot-átmeneti gráffal írhatunk le és a következő állapotokat különböztetjük meg:
* Fut: a CPU a folyamathoz tartozó utasításokat hajtja végre, CPU-nként egyetlen ilyen folyamat lehet.
* Várakozik, blokkolt: a folyamat várakozni kényszerül, működését csak valamilyen esemény bekövetkezésekor tudja folytatni. Több ilyen is lehet a rendszerben.
* Futásra kész: minden feltétel adott, de a CPU éppen foglalt. Több ilyen is lehet a rendszerben.
Folyamatok állapotátmenetei:
* Folyamat létrehozása: a folyamatot egy másik folyamat hozza létre. A folyamatok szülő-gyerek hierarchiáját tárolni kell, a létrehozó folyamat a szülő, míg a létrejöttek a gyerekek. A folyamatnak erőforrásra van szüksége, melyen a szülő folyamattal is osztozhat. A szülővel kommunikálhat, paramétereket kaphat tőle. A szülő folyamat párhuzamosan fut a gyerek folyamattal, ill. bevárhatja azt. Folyamat létrejöhet a rendszer indulásakor (pl.: felhasználói interfészek, démonok), folyamatot létrehozó rendszerhívás hatására, egy program indulásakor, ill. egy új batch-job indulásakor.
* Folyamat befejeződése: a folyamat befejeződik, ha az utolsó utasítását is végrehajtotta, de leállítható egyéb okok miatt is (pl.: túl sok erőforrást használ). Ilyenkor a folyamat által használt erőforrások felszabadulnak és a megszűnő folyamat információt adhat vissza a szülő folyamatnak.
* Eseményre vár: a folyamatnak a tevékenysége folytatásához várnia kell valamilyen eseményre (pl.: erőforrásra, perifériára, információra egy másik folyamattól). Az operációs rendszer feljegyzi, hogy a folyamat mire vár. Több folyamat is várakozhat ugyanarra az eseményre (pl.: népszerű erőforrás).
* Esemény bekövetkezik: bekövetkezik a várt esemény, az operációs rendszer megváltoztatja a folyamat állapotát és a folyamat bekerül a várakozási sorba (még nem fut).
* Folyamat elindulása: a CPU felszabadulásakor az operációs rendszer valamilyen kritériumok alapján kiválaszt egy folyamatot a várakozási sorból és elindítja azt.
* Futás megszakad: az operációs rendszer elveheti a processzort a folyamattól (pl.: megszakítások), de a folyamat önként is lemondhat a CPU-ról (pl.: tipikusan statisztikát gyűjtő folyamatok).
Kibővített állapotátmeneti gráf
A bővítés oka, hogy az operációs rendszer felfüggeszthet (suspend) folyamatokat azzal, hogy elveszi az elvehető erőforrásokat. Ennek okai például, hogy a rendszer túl van terhelve; vészhelyzet esetén (pl.: kimarad a tápfeszültség); ill. a felhasználó kérésére. A felfüggesztett folyamatok nem versengenek az erőforrásokért, ill. ezek bármikor folytathatók.
Új állapotok:
* Felfüggesztve várakozik
* Felfüggesztve kész
Új állapotátmenetek:
* Felfüggeszt: az operációs rendszer várakozik állapotból felfüggesztheti a folyamatot, attól a fontosabb erőforrásokat elveszi.
* Aktivál: a felfüggesztett folyamat visszakapja az erőforrásait. Felfüggesztve várakozó folyamatot a rendszer nem aktivál, mivel az továbbra sem futhat, de az erőforrásokat foglalja (a rendszer feleslegesen dolgozna, ha az éppen aktivált folyamatot újra fel kellene függeszteni).
* Felfüggesztve várakozik -> felfüggesztve futásra kész: akkor is bekövetkezhet a várt esemény, ha a folyamat éppen felfüggesztett állapotban van.
Környezetváltás (kontext switch)
A futó folyamat elhagyja a futó állapotot, majd egy futásra kész pedig elindul. Az átkapcsolásnak zökkenőmentesnek kell lennie, akkor hatékony a rendszer. Több folyamatnak van hely a memóriában, mely tartalma nem változik, így a saját állapotjelzőket nem kell elmenteni, csak a végrehajtó gép állapota kerül elmentésre.
Folyamat- és I/O leírók
Az operációs rendszer a folyamatok kezeléséhez szükséges információkat egy úgynevezett folyamatleíróban tárolja (folyamatleírók – Process Control Block, PCB; I/O leírók – Input Output Control Block, IOCB).
Folyamatleíró blokk tartalmazza:
* A folyamat állapotát (pl.: futásra kész, fut)
* A folyamat azonosítóját (általában egy szám)
* A folyamat szülőjének és gyerekeinek azonosítóját
* A kapcsolódó tárterületek leírását (pl.: mutatók, virtuális tárkezeléshez szükséges információk)
* A használt erőforrások leírását
* A regiszterek tartalmát
* A várakozó folyamatnál a várt esemény leírását
* Ütemezéshez szükséges információkat (pl.: prioritás, várakozási idő)
* Statisztikai információkat
I/O műveletek leírásához tartozó adatok:
* Műveletek kijelölése (pl.: írás, olvasás)
* Tárterület címe (ahonnan / ahova a művelet végrehajtandó)
* I/O készülék egyéb adatai (pl.: mágneslemez szektorcíme)
* Átvitendő adatmennyiség
* Állapotjelző
Függő és független folyamatok
Egy rendszer sok folyamatból állhat, melyek között csatolás lehet:
* Független folyamatok: egymás működését semmilyen módon nem befolyásolják. Végrehajtásuk aszinkron, egymással párhuzamosan is végrehajtódhatnak, nincs időbeli függőség.
* Függő folyamatok:
o Logikailag független folyamatok megosztottan használnak
erőforrásokat (pl.: több felhasználó azonos gépen dolgozik).
o Logikailag is függő folyamatok közösen oldanak meg valamely
feladatot. Együttműködnek, kommunikálnak egymással (pl.:
közös változók).
Együttműködő folyamatok használatának indokai például az erőforrások megosztása a jobb kihasználtság végett; számítások felgyorsulása (párhuzamosítás miatt); felhasználók kényelme (egyszerre több program futtatása); modularitás, vagyis a kisebb készekre bontás (javul az áttekinthetőség).
Szinkronizáció
A folyamat végrehajtásának olyan időbeli korlátozása, ahol ez egy másik folyamat futásától, ill. egy külső esemény bekövetkezésétől függ.
A szinkronizáció három alapesete:
* Precedencia (előidejűség): meghatározott sorrend biztosítása. az egyik folyamat adott utasításai meg kell, hogy előzzék egy másik folyamat adott utasításait. pl: szakács-kávét főz kukta-cukrot vesz (különben kihűl a kávé)
* Egyidejűség: két vagy több folyamat bizonyos utasításainak egyidejűsége. A folyamatok bevárják egymást, mielőtt további működésüket elkezdenék (randevú). pl. szakács-kávét főz || kukta-habot ver (különben kihűl a kávé vagy összeesik a hab)
* Kölcsönös kizárás: a futási sorrendre nincs korlát. A kijelölt utasítások közül egyszerre csak egy futhat. pl. szakács-habot ver X kukta-habverőt mosogat
Versenyhelyzet
Több párhuzamosan futó folyamat közös erőforrást használ. A futás eredménye függ attól, hogy az egyes folyamatok mikor és hogyan futnak, ezáltal hogyan (milyen sorrendben) férnek az erőforráshoz.
Kritikus szakasz
Kritikus szakasznak nevezzük a programok azon részeit, amelyek egyidejű végrehajtása nem megengedett. Versenyhelyzet miatt a kritikus szakaszok kölcsönös kizárását biztosítani kell (ha egy folyamat kritikus szakaszban van, akkor más nem léphet be a kritikus szakaszba).
A megvalósítás feltételei:
* Biztosítja a kölcsönös kizárást: egyszerre csak egy folyamat lehet a kritikus szakaszban.
* Halad: ha nincs folyamat kritikus szakaszban, akkor az algoritmus egyet beenged a várakozók közül.
* A folyamatok várakozása korlátozott: ha egy folyamat be akar lépni a kritikus szakaszba, akkor véges időn belül be is tud lépni.
Megvalósítási módszerek:
* Megszakítás (interrupt) tiltása: nem lehet a folyamatot megszakítani, különben az egész rendszert lefagyaszthatja.
* Busy waiting megoldások:
o Tisztán programozott megoldások: közösen használt
változókon alapulnak, több processzoron párhuzamosan futó
folyamatokat tételeznek fel.
o Hardveres támogatás: speciális, megszakíthatatlan gépi
utasítások, amelyek egyszerre több műveletet is elvégeznek.
* Szemafor.
* Magas szintű módszerek: léteznek olyan programszerkezetek, amelyek a kritikus szakasz automatikus, megbízható megvalósulását támogatják.
Szemafor
Egy speciális adattípus, amely nullát, ill. pozitív egész számokat tartalmazhat és két művelet van értelmezve rajta. Mindkét művelet elemi, megszakíthatatlan:
* P: vizsgál / belép művelet
V: kilép művelet
Mutex: speciális szemafor, melynek vagy nyitott (unlocked) vagy zárt (locked) az értéke.
Megvalósítási problémák:
* A P elemi művelet az üres utasítás helyén a folyamattól elveszi a CPU-t és várakozó állapotba teszi, majd ezt feljegyzi a szemaforhoz tartozó valamilyen adatszerkezetbe.
* A V elemi műveletnél nem csak a számláló nő, hanem egy folyamatot (ha van) futásra kész állapotba tesz. Itt többféle stratégia is lehetséges.
* Az aktív várakozás állandóan használja a processzort, azaz a folyamat állandóan futó állapotban van.
* A multiprogramozott operációs rendszereknél ilyenkor a várakozni kényszerülő folyamattól el kell venni a processzort.
Holtpont
Holtpontról akkor beszélünk, ha több folyamat olyan eseményre, erőforrás felszabadulásra vár, amelyet csak egy másik, ugyancsak várakozó folyamat tud előidézni.
Kialakulásának feltéttelei:
* Kölcsönös kizárás: a folyamatok az erőforrásokat kizárólagosan használják.
* Foglalva várakozás: létezik olyan folyamat, amely lefoglalva tart erőforrásokat addig, amíg másik erőforrásokra várakozik.
* Nem elvehető erőforrások találhatók a rendszerben: az erőforrást a folyamat csak önszántából szabadíthatja fel.
* Körkörös várakozás: a rendszerben lévő folyamatok közül létezik egy olyan Pn sorozat, amelyben a Pi folyamat a Pi+1 által lefoglalva tartott erőforrásra vár, Pn pedig P0 -ra.
Holtpont kezelése:
* Strucc algoritmus: nem veszünk tudomást a problémáról és nem teszünk semmit. Ez viszont bizonyos rendszereknél nem engedhető meg. Kisebb kockázatú rendszereknél megengedhető.
* Szabályokkal biztosítjuk, hogy holtpont ne alakuljon ki (holtpont megelőzés és elkerülés).
* Detektálás / feloldás: hagyjuk, hogy esetleg kialakuljon a holtpont és csak ekkor avatkozunk be (holtpont felismerés és megszűntetés).
Ütemezés
Az ütemezés (scheduling) az a tevékenység, amely eredményeként eldől, hogy az adott erőforrást a következő pillanatban mely folyamat használja.
Egy folyamat futása során két különböző jellegű tevékenységet végez:
* CPU löket: a folyamatnak csak a processzorra és az operatív tárra van szüksége.
* Periféria löket: A folyamat perifériás átvitelt hajt végre, annak lezajlására vár. Nincs szüksége CPU-ra.
Az ütemezés két fő típusa:
* Preemptív: el lehet venni a CPU-t a folyamattól. Az időosztásos rendszerekben ilyen van.
* Nem preemptív: a folyamattól nem lehet elvenni a CPU-t, csak magától mondhat le róla.
Mikor következhet be ütemezés:
* A futó állapotból kikerül a folyamat: ilyenkor a folyamat várakozni kényszerül, befejeződik, lemond a processzorról vagy elveszik tőle.
* Egy folyamat futásra késszé válik
A várakozó folyamatokat az operációs rendszer általában egy várakozási sorban tartja nyilván. A sor elemei a folyamatleírókra hivatkoznak, az ütemező pedig a várakozási sorból választ folyamatot.
Ütemezési algoritmusok teljesítményének mérése
- CPU kihasználtság (CPU utilization): a CPU az idejének hány százalékát használja a folyamatok utasításainak végrehajtására.
- Átbocsátó képesség (Throughput): az operációs rendszer időegységenként hány munkát futtat le.
- Körülfordulási idő (Turnaround Time): egy munka a rendszerbe helyezésétől számítva mennyi idő alatt fejeződik be.
- Várakozási idő (Waiting Time): egy munka (vagy folyamat) mennyi időt tölt várakozással.
- Válaszidő (Response Time): időosztásos (interaktív) rendszereknél fontos. Az operációs rendszer reakció ideje, a kezelői parancs után a rendszer első látható reakciójáig eltelt idő.
Ütemezési algoritmusok
- Egyszerű algoritmusok:
o Legrégebben várakozó (FCFS): a futásra kész folyamatok a várakozási sor végére kerülnek, az ütemező a sor elején álló folyamatot kezdi el futtatni. Nem preemptív, egyszerűen megvalósítható. Konvoj hatás (egy hosszú CPU löketű folyamat feltartja a mögötte várakozókat)
o Körforgó (RR): preemptív, a folyamatok időszeletet kapnak. Ha a CPU löket nagyobb, mint az időszelet, akkor az időszelet végén az ütemező elveszi a CPU-t, a folyamat futásra kész lesz és beáll a várakozó sor végére. Ha a CPU löket rövidebb, akkor a löket végén a folyamatot újra ütemezzük. - Prioritásos algoritmusok: a futásra kész folyamatokhoz egy prioritást rendelünk. A legnagyobb prioritású folyamat lesz a következő futtatandó folyamat.
o Legrövidebb löketidejű (SJF): nem preemptív, a futásra kész folyamatok közül a legrövidebb löketidejűt indítja.
o Legrövidebb hátralévő idejű (SRTF): az SJF preemptív változata. Ha egy folyamat válik futásra késszé, akkor az ütemező újra megvizsgálja a futásra kész folyamatokat, ill. az éppen futó folyamat hátralévő löketidejét és a legrövidebbet indítja tovább.
o Legrosszabb válaszarány (HRR): az SJF algoritmus változata, ahol a várakozó fo-
𝑙ö𝑘𝑒𝑡𝑖𝑑ő + 𝑘 ∗ 𝑣á𝑟𝑎𝑘𝑜𝑧á𝑠𝑖 𝑖𝑑ő lyamatok öregednek. A kiválasztás a löketidő helyett a
𝑙ö𝑘𝑒𝑡𝑖𝑑ő képlettel megy végbe, ahol k egy jól megválasztott konstans. - Többszintű algoritmusok: a futásra kész folyamatokat több, külön sorban várakoztatják. Minden sorhoz prioritás van rendelve. Egy kisebb prioritású sorból csak akkor indulhat el egy folyamat, ha a nagyobb prioritású sorok üresek. Az egyes sorokon belül különböző kiválasztási algoritmusok működhetnek:
o Statikus többszintű sorok (SMQ): a folyamat elindulásakor valamilyen kritérium alapján besoroljuk egy várakozó sorba. A folyamat élete során végig ugyanabban a sorban marad.
o Visszacsatolt többszintű sorok (MFQ): a sorokhoz egy időszelet tartozik. Minél nagyobb a prioritás, annál kisebb az időszelet. A folyamatok futásuk során átkerülhetnek másik sorokba. - Többprocesszoros ütemezés:
o Heterogén rendszerek esetében egy folyamat csak bizonyos processzorokon futhat.
o Homogén rendszerekben a futásra kész folyamatokat közös sorokban tárolja.
