Operációs rendszerek MINB240 UNIX, Windows NT ütemezése Holtpontkezelés
4. előadás Ütemezés Operációs rendszerek MINB240
1
UNIX ütemezése • Meglehetősen összetett algoritmus • Rendszerjellemzők: • Többfelhasználós • Interaktív és batch programokat egyaránt futatható környezet
Operációs rendszerek MINB240
2
Algoritmus követelményei • Alacsony válaszidő támogatása (interaktív folyamatok)
• Nagy átbocsátóképesség • Éhezés elkerülése (háttérben futó, alacsony prioritású folyamatoknál) • Rendszer terhelését figyelembe vevő ütemezés • Felhasználó befolyása
Operációs rendszerek MINB240
3
1
UNIX ütemezés jellemzése • Prioritásos ütemezés • Folyamatokhoz időben dinamikusan változó prioritást rendel • Ütemezés fajtái: • Kernel mód • Felhasználói mód
Operációs rendszerek MINB240
• • • •
4
Felhasználói módban futó folyamatok ütemezése
Preemtív ütemezés Időosztásos Időben változó prioritás RR és FCFS algoritmusok
Operációs rendszerek MINB240
5
Kernel módban futó folyamatok ütemezése • • • •
Nem preemtív ütemezés Rögzített prioritású folyamatok Pl.: rendszerhívás, megszakítás kezelés Ütemezés következik, ha: • Folyamat önként lemond a futás jogáról (sleep) • Kernel módból viszszatér felhasználói módba Operációs rendszerek MINB240
6
2
Folyamatok prioritása UNIX-ban • 0-127 közötti egész számok jelölik (a 0 érték jelöli a legnagyobb prioritást) • A prioritási értékeknek két tartománya: • Kernel módú folyamatok 50 alatti prioritás • Felhasználó módú folyamatok 50 feletti prioritás
Operációs rendszerek MINB240
7
Prioritás meghatározása kernel módban • Folyamat prioritása statikus • Sleep rendszerhívás – milyen eseményre várakozik • Ütemezés alkalmával vizsgálja
Operációs rendszerek MINB240
8
Prioritás meghatározása felhasználói módban • Prioritás adott pillanatban: • Felhasználó által adott külső prioritás (nice szám) • Folyamat korábbi CPU használata
• Prioritásszámításhoz használt paraméterek • • • •
p_pri p_usrpri p_cpu p_nice
aktuális ütemezési prioritás felhszanálói módban érvényes prioritás CPU használat mértékére vonatkozó szám futás elején adott nice szám
• A paramétereket az op.rsz. minden folyamat esetén számon tartja Operációs rendszerek MINB240
9
3
Paraméter módosulások • p_pri • Ez alapján választja ki mely folyamatot ütemezze következőben • Felhsználói módban a p_pri = p_usrpri
• p_usrpri • felhszanálói módban érvényes prioritás
• p_cpu • CPU használat mértékére vonatkozó szám • folyamat indításakor 0 • Ezen érték módosítása óramegszakításokhoz kapcsolódik – Minden óramegszakításkor – Minden 10. órajelnél – Minden 100. órajel megszakításnál
• p_nice • futás elején adott nice szám Operációs rendszerek MINB240
10
Óramegszakításhoz kötődő ütemezési tevéknységek
Futó folyamat
Minden folyamat
Minden óramegszakítás
p_cpu = p_cpu + 1
Vizsgál: van-e magasabb prioritású folyamat Ha igen: újraütemez
Minden 10. óramegszakítás
RR algoritmus
Minden 100. óramegszakítás
Felhsználói prioritások újraszámolása
Operációs rendszerek MINB240
11
Környezetváltás ütemezéskor • Nem preemtív ütemezés • Ha egy folymatnak várnia kell – sleep • Befejeződik a folyamat - exit
• Preemtív ütemezés • 100. óraciklus után prioritás újraszámolás – váltás • 10. óraciklus esetén – RR algoritmus szerint vált • Ha egy futó folyamat felébred (futásra kész állapot)
Operációs rendszerek MINB240
12
4
Adatszerkezetek a folyamatok prioritásának tárolására • Időben változó prioritások tárolására: dinamikus adatszerkezetek • Azonos prioritású folyamatok – láncolt lista • Ezek keresésére – hash táblázat
Operációs rendszerek MINB240
13
A folyamatok prioritásának tárolása
Operációs rendszerek MINB240
14
Értékelés Átlagos terhelés mellett: • Jó rendszer kihasználtság • Jó áteresztőképesség De: • Nem méretezhető megfelelően • Nem lehet meghatározott CPU időt allokálni • Fix válaszidő nem garantált • Felhasználó a folyamatainak prioritásár nem tudja megfelelő módon befolyásolni
Operációs rendszerek MINB240
15
5
A Windows NT (1989) • Elvárások: • Valós 32 bites, preemtív, újrahívható op. rsz. • Virtuális memóriakezelést megvalósító • Fusson: – különböző hardver platformokon – Szimmetrikus multiprocesszoros környezetben – Elosztott hardver környezetben
• Az eddigi 16 bites alkalmazások futását támogassa • POSIX 1003.1 szabvány teljesítése • UNICODE használata Operációs rendszerek MINB240
16
UNICODE • Karakterek gépi ábrázolásának szabványa • 16 biten ábrázol • Foglakozik a karakterek: • Osztályozásával • Megjelenésével • Használatával
• Ezt alkalmazva lehetőség nyílik az alkalmazások nyelvterülettől független változatának elkészítésére Operációs rendszerek MINB240
17
Windows NT felépítése • Rétegszerkezet • Kliens-szerver architektúra • Objektumorientált szemlélet • Teljesíti: – Adatrejtés – Interfész használat
• Nem teljesíti – Polimorfizmus – Öröklődés
Operációs rendszerek MINB240
18
6
Windows NT felépítése
Operációs rendszerek MINB240
19
Windows NT ütemezése • Program: • Kódot végrehajtó szál • Szálak által lefoglalt erőforrások
• NT folyamatmodellje • • • • •
Program kód és adat Saját virtuális memória-címtér Rendszererőforrások Folyamat egyedi azonosítója Végrehajtható szál – szál egy egység, amit az ütemező kezel és végrehajtásra ütemez a CPU-hoz Operációs rendszerek MINB240
20
Processzor regiszterei - állapot leírás Két veremtár Kizárólagosan használható tárterületet Szál egyedi azonosítója – thread ID
Thread context
• • • •
Környezet
NT szál komponensei
• Erőforrás foglalás – objektum - handle • Elérési token • Folyamat biztonsági azonosítója • Folyamat jogosultságainak leírása
Operációs rendszerek MINB240
21
7
Windows NT folyamatmodellje
Operációs rendszerek MINB240
22
Folyamatkezelés NT alatt • Executive réteg tárolja a folyamatokhoz tartozó adatokat egy folyamatblokkban EPROCESS blokk: – Kísérőadatok – Mutatók a kapcsolódó adatstruktúrákra
Operációs rendszerek MINB240
23
Szálkezelés NT alatt • Minden szálat egy executive szálblokk reprezentál ETHREAD
Operációs rendszerek MINB240
24
8
Szálütemezés NT-ben • Prioritáson alapuló ütemezés • Preemtív ütemezés • Processzor affinitás – a szál futását azok a processzorok korlátozhatják, melyeken a szál futása már meg van kezdve
Operációs rendszerek MINB240
25
A kvantum • Időszelet – kvantum – az az időtartam, amennyit egy szál futhat, mielőtt az NT megszakítja , hogy kiderítse, hogy: • vár-e másik szál is futásra azonos prioritással, • vagy nincs-e szükség a szál prioritásának csökkentésére
• Kvantumok értéke szálanként változhat
Operációs rendszerek MINB240
26
Ütemezés Windows NT-ben • Az ütemezési funkciókat a kernel valósítja meg • Ütemezést megvalósító rutinok: a kernel diszpécsere • Ütemezési döntések szigorúan szálak alapján történik • Nem számít melyik szál melyik processzhez tartozik • Pl.: A és B processzek futtatható szálai 10 és 2 azonos prioritással, akkor minden szál a CPU idő 1/12 részét kapja
• Prioritási szintek: 0-31-ig
Operációs rendszerek MINB240
27
9
Prioritási szintek NT alatt 16–31-ig 1–15-ig 0
valós idejű szint változószint rendszerszint
• Kvantumérték meghatározása: • Minden szálhoz – kvantumegység • Órajel megszakításokkor a kvantumszámból levonódik 3 • Ha értéke 0 vagy negatív, akkor új szál kerül kiválasztásra
Operációs rendszerek MINB240
28
Holtpont (deadlock) Példa: Egy rendszerben két folyamat a következő-képpen használ két erőforrást (nyomtatót és mágnesszalagot): P1 folyamat
P2 folyamat
…
…
Lefoglal (M)
Lefoglal (NY)
Lefoglal (NY)
Lefoglal (M)
…
…
Felszabadít (M)
Felszabadít (NY)
Felszabadít (NY)
Felszabadít (M)
…
… Operációs rendszerek MINB240
29
Erőforrások • Engedélyezett objektumok, mint erőforrások • Erőforrás az a „valami”, amit ugyanabban az időben csak egy processzus használhat Például: hardvereszköz, információ, stb.
Operációs rendszerek MINB240
30
10
Erőforrások fajtái 1 • Egypéldányos erőforrás • Egyes típusokhoz egyetlen erőforráspéldány tartozik • Pl.: speciális perifériák, rajzgép, rendszertáblák, stb.
• Többpéldányos erőforrás • Több erőforráspéldány áll rendelkezésre,melyek használati értékükben azonosak • Folyamat számára közömbös, hogy melyik példányt használja • Pl.: memória, munkaterület a mágneslemezen, egyenértékű nyomtatók, stb. Operációs rendszerek MINB240
31
Erőforrások fajtái 2 Megszakítható erőforrás • Ha hiba bekövetkezte nélkül elvehető az őt birtokló folyamattól (pl.: memória) • Holtpont nem áll elő
Megszakíthatatlan erőforrás • Itt a tulajdonostól való elvétele hibát eredményez (pl.: CD írás során Cd író elvétele) • Holtpont probléma • Általában feloldhatóak az erőforrások eljárások közötti újrakiosztásával
Operációs rendszerek MINB240
32
Példa Adott rendszerben: • 64MB memória • Két 64MB-os processzus • Egy nyomtató
Mindegyik processzus nyomtatni akar • A kéri, kapja a nyomtatót • Nyomtatandó értékek kimásolását kezdi • Mielőtt végez,lejár az időszelete • B fut- sikertelen kísérlet a nyomtató megszerzésére HOLTPONT helyzet: A-hoz nyomtató, B-hez memória van rendelve – egyik sem tud futni a másik erőforrása nélkül
Operációs rendszerek MINB240
33
11
Erőforrásokkal kapcsolatos tevékenységek 1. Erőforrás kérése - igénylés • •
Ha kéréskor az erőforrás nem hozzáférhető, akkor a kérő processzus kénytelen várakozni Sikertelen kérés esetén: blokkolódhat a folyamat vagy hibakód generálódik
2. Erőforrás használata 3. Erőforrás elengedése - felszabadítás
Operációs rendszerek MINB240
34
Holtpont Egy rendszer folyamatainak H részhalmaza holtpontban van, ha a H halmazba tartozó valamennyi folyamat olyan eseményre vár, amelyet csak egy másik H halmazbeli folyamat tudna előidézni. • • • •
A definíció általános A rendszerben lévő folyamatok lehetnek futó, élő folyamatok Nem biztos, hogy minden együttfutáskor kialakul holtpont Befagyasztott folyamatok által ellátott funkciók kiesését okozza
Operációs rendszerek MINB240
35
Holtpont kialakulásának szükséges feltételei
Coffman et.al. 1971 1. Kölcsönös kizárás feltétel – legyenek olyan erőforrások a rendszerben, melyeket a folyamatok csak kizárólagosan használhatják 2. Foglalva várakozás – legyen olyan folyamat, amely lefoglalva tart erőforrásokat, miközben erőforrásra várakozik 3. Megszakíthatatlanság – a folyamat addig birtokolhatja az erőforrást, amíg el nem engedi 4. Körkörös várakozás – két agy több proesszusból álló ciklikus láncnak kell kialakulnia ,melynek mindegyik processzusa olyan erőforrásra vár, melyet a láncban következő processzus fogva tart
Operációs rendszerek MINB240
36
12
Megjegyzés • Coffman – erőforrásholtpont • Egyéb holdpont problémák pl.: kereszteződésbeli járművek szabály szerint közlekednek – jobbkéz szabály ütemezési holdpont
Operációs rendszerek MINB240
37
Holtpont modellje • Holt (1972) a négy feltétel modellezése irányított gráfokkal • Kétféle csúcs: – Kör – processzus – Négyzet – erőforrás
• Él: – Erőforráscsúcsból processzuscsúcsba – az erőforrást a processzus kérte, engedélyezték, jelenleg birtokolja – Processzuscsúcsból erőforráscsúcsba – a processzus pillanatnyilag blokkolt és várakozik erőforrásra
Operációs rendszerek MINB240
38
Holtpont modellje irányított gráffal a.) R1 erőforrás P1 processzushoz van rendelve b.) P1 processzus várakozik R1 erőforrásra c.) P1 processzus R1 erőforrásra várakozik,melyet P2 processzus birtokol P2 azonban nem tudja elengedni R1-et, mivel az R2 erőforrásra várakozik – kör a gráfban (P1-R1-P2-R2-P1 kör)
Operációs rendszerek MINB240
39
13
Példa
Holtpont Operációs rendszerek MINB240
40
Példa 1. A kéri R-t 2. C kéri T-t 3. A kéri S-t 4. C kéri R-t 5. A elengedi R-t 6. A elengedi S-t Nincs holtpont
Operációs rendszerek MINB240
41
Stratégiák 1. Probléma figyelmen kívül hagyása – strucc politika 2. Felismerés és helyreállítás – detektálás feloldás 3. Védekezünk a kialakulás ellen 1. Megelőzés – struktúrálisan holtpontmentes rendszert tervezünk 2. Elkerülés – erőforrások körültekintő lefoglalásával
Operációs rendszerek MINB240
42
14
1. Strucc algoritmus • Tegyünk úgy,mintha semmi probléma nem lenne • Mérlegeljük: mekkora a probléma és milyen áron oldható meg • Általános célú operációs rendszerek álláspontja (UNIX, Windows nem foglalkoznak a problémával)
Operációs rendszerek MINB240
43
2. Észlelés és helyreállítás • • • •
A rendszer figyeli az erőforrásigényeket és elengedéseket Módosítja az erőforrásgráfot Ellenőrzi, van-e benne kör Ha kör keletkezik, akkor a körben lévő processzusok egyikét megszünteti • Ezt addig teszi, mg meg nem szűnik a kör • Alkalmazás: nagygépeknél, kötegelt rendszerekben
Operációs rendszerek MINB240
44
2.1. Holtpont észlelése • Holtpontdetektáló algoritmus Példa: többpéldányos erőforrások pillanatnyi allokációja és igénylése FOGLAL
KÉR
P1
4
4
P2
1
0
P3
3
4
P4
1
2
Operációs rendszerek MINB240
45
15
Coffman-féle holtpontdetektáló algoritmus 1. Kezdőérték beállítása Gyűjtő := Szabad; Tovább[i] := hamis minden i-re; 2. Továbblépés esélyes folyamatok kezelése: Keress i-t, melyre (Tovább[i] = hamis ÉS Kér[ig<= gyűjtő); Ha van ilyen i, akkor Gyűjtő := Gyűjtő + Foglalt [i]; Tovább[i] := igaz; Ismételd 2. lépést Egyébként folytasd 3. lépéssel 3. Kiértékelés Ha Tovább[i] = igaz minden i-re, akkor NINCS HOLTPONT Egyébként A Pi folyamatok,melyekre Tovább[i] = hamis, HOLTPONTBAN VANNAK. Operációs rendszerek MINB240
46
2.2. Holtpont feloldása • Általában nem számolható fel veszteségek nélkül • Erőforrások felszabadítása erőszakos megoldással • Problémák: • Választani kell radikális vagy kíméletes megoldás között – Radikális – valamennyi holtpontban érintett folyamatot felszámoljuk; áldozatok kiválasztásához szempontrendszer felállítása
• Biztosítani kell a folyamatok visszaállíthatóságát
Operációs rendszerek MINB240
47
3. Védekezünk a kialakulás ellen Kétféle módszer: • •
Megelőzés – struktúrálisan holtpontmentes rendszert tervezünk Elkerülés – erőforrások körültekintő lefoglalásával
Operációs rendszerek MINB240
48
16
3.1. Holtpont megelőzése • Holtpont eleve ehetetlen legyen • Elv: Coffman négy tételének egyike ne teljesüljön Æ ekkor nem lesz holtpont
Operációs rendszerek MINB240
49
Holtpont megelőzése 1. elv Kölcsönös kizárás • Egy erőforrás sincs soha kizárólagosan egy processzuhoz rendelve • Megoldás: • Háttértárban történő tárolás
Operációs rendszerek MINB240
50
Holtpont megelőzése 2. elv Foglalva várakozás • Megelőzni olyan helyzeteket, melyekben erőforrásokat birtokló folyamatok várakoznak további erőforrásra • Megoldás: • Ha minden folyamat közölné összes erőforrásigényét futás előtt és ha elérhető mindet lefoglalná (nem tudja és nem optimális kihasználás)
Operációs rendszerek MINB240
51
17
Holtpont megelőzése 3. elv Megszakíthatatlanság • Ha elvehetnénk az erőforrást - káosz
Operációs rendszerek MINB240
52
Holtpont megelőzése 4. elv Körkörös várakozás Többféle megoldás: 1. Egy folyamat egyetlen pillanatban csak egyetlen erőforrást foglalhat 2. Összes erőforrás megszámozása 1. Fotókidolgozó 2. Szkenner 3. Rajzgép 4. Szalagmeghajtó 5. CD-ROM
Holtpont csak akkor lenne, ha P1 kérné R2 erőforrást P2 pedig R1-et Tfh R1 és R2 különböző erőforrások Ha i > j akkor P1-nek nincs megengedve R2 kérése Ha i < j akkor P2-nek nincs megengedve R1 kérése Operációs rendszerek MINB240
53
Megelőzési stratégiák összefoglalva Feltétel
Megközelítés
Kölcsönös kizárás
Háttértárolás
Birtokol és várakozik
Összes erőforrásigény előzetes kérése
Megszakíthatatlanság
Erőforrások elvétele
Ciklikus várakozás
Erőforrások numerikus kezelése
Operációs rendszerek MINB240
54
18
3.2. Holtpont elkerülése Van-e olyan algoritmus, mellyel a holtpont elkerülhető?
Igen, elkerülhető a holtpont, ha bizonyos információ előre elérhető.
Operációs rendszerek MINB240
Dijkstra (1965)
55
Holtpont elkerülése Bankár algoritmus
A 0 6 Kisvárosi bankár munkájának modellje Bizonyos nagyságú hitelt engedélyez B 0 5 Pl.: négy hitelező A,B,C,D adott C 0 4 hitelezési egységgel D 0 7 Kiszolgálásukra a bankát 10 egységet foglal le (22 helyett) A 1 6 A 1 6 Egy állapot biztonságos, ha Feltéve: mindenki amint tudja visszafizeti létezikBezzel 1 5kezdődő 5 B 2olyan állapotsorozat, melynek C 2 4 mindegyik C 2 4 eredményeként ügyfélDfelvehet 4 7 összesen D 4 7 annyi kölcsönt, amennyit a Szabad :2 Szabad :1 hitelbiztonságos lehetősége enged. nem biztonságos Operációs rendszerek MINB240
56
Bankár algoritmus Ügyfelek – processzusok Bankár – operációs rendszer Egységek – erőforrás • Egy állapot biztonságos, ha létezik ezzel kezdődő olyan állapotsorozat, melynek eredményeként mindegyik ügyfél felvehet összesen annyi kölcsönt, amennyit a hitel lehetősége enged. • Azaz mindegyik processzus megkapja az összes erőforrását és befejeződik
Operációs rendszerek MINB240
57
19
Példa Biztonságos –e vagy sem?
Biztonságos!
Operációs rendszerek MINB240
58
Példa Biztonságos –e vagy sem?
Nem biztonságos! Operációs rendszerek MINB240
59
Erőforrás pályagörbék • Két processzus és két erőforrás esetén
Operációs rendszerek MINB240
60
20