UNIX ütemezése • Meglehetősen összetett algoritmus • Rendszerjellemzők:
Operációs rendszerek
• Többfelhasználós • Interaktív és batch programokat egyaránt futatható környezet
MINB240 UNIX, Windows NT ütemezése Holtpontkezelés
4. előadás Ütemezés Operációs rendszerek MINB240
1
Algoritmus követelményei
2
UNIX ütemezés jellemzése
• 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
Operációs rendszerek MINB240
3
• 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
Kernel 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
• • • •
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
5
Operációs rendszerek MINB240
6
Prioritás meghatározása kernel módban
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:
• Folyamat prioritása statikus • Sleep rendszerhívás – milyen eseményre várakozik • Ütemezés alkalmával vizsgálja
• Kernel módú folyamatok 50 alatti prioritás • Felhasználó módú folyamatok 50 feletti prioritás
Operációs rendszerek MINB240
7
Operációs rendszerek MINB240
8
Prioritás meghatározása felhasználói módban • p_pri
• Prioritás adott pillanatban:
• Ez alapján választja ki mely folyamatot ütemezze következőben • Felhsználói módban a p_pri = p_usrpri
• Felhasználó által adott külső prioritás (nice szám) • Folyamat korábbi CPU használata
• p_usrpri • felhszanálói módban érvényes prioritás
• Prioritásszámításhoz használt paraméterek • • • •
p_pri p_usrpri p_cpu p_nice
Paraméter módosulások
• p_cpu
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
Óramegszakításhoz kötődő ütemezési tevéknységek
• 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
Környezetváltás ütemezéskor • Nem preemtív ütemezés • Ha egy folymatnak várnia kell – sleep • Befejeződik a folyamat - exit
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
• 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)
Felhsználói prioritások újraszámolása
Operációs rendszerek MINB240
11
Operációs rendszerek MINB240
12
Adatszerkezetek a folyamatok prioritásának tárolására
A folyamatok prioritásának tárolása
• 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
Értékelés
14
A Windows NT (1989)
Á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
Operációs rendszerek MINB240
• 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 15
Operációs rendszerek MINB240
16
UNICODE
Windows NT felépítése
• Karakterek gépi ábrázolásának szabványa • 16 biten ábrázol • Foglakozik a karakterek:
• Rétegszerkezet • Kliens-szerver architektúra • Objektumorientált szemlélet
• Osztályozásával • Megjelenésével • Használatával
• Teljesíti:
• 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
– Adatrejtés – Interfész használat
• Nem teljesíti – Polimorfizmus – Öröklődés
17
Operációs rendszerek MINB240
Windows NT felépítése
18
Windows NT ütemezése • Program: • Kódot végrehajtó szál • Szálak által lefoglalt erőforrások
• NT folyamatmodellje • • • • •
Operációs rendszerek MINB240
19
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
NT szál komponensei Thread context
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
Környezet
• • • •
Windows NT folyamatmodellje
• 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
Folyamatkezelés NT alatt
Operációs rendszerek MINB240
22
Szálkezelés NT alatt
• Executive réteg tárolja a folyamatokhoz tartozó adatokat egy folyamatblokkban EPROCESS blokk:
• Minden szálat egy executive szálblokk reprezentál ETHREAD
– Kísérőadatok – Mutatók a kapcsolódó adatstruktúrákra
Operációs rendszerek MINB240
23
Operációs rendszerek MINB240
24
Szálütemezés NT-ben
A kvantum
• Prioritáson alapuló ütemezés • Preemtív ütemezés • Processzor affinitás – a szál futását azok a
• Időszelet – kvantum – az az időtartam, amennyit egy szál futhat, mielőtt az NT megszakítja , hogy kiderítse, hogy:
processzorok korlátozhatják, melyeken a szál futása már meg van kezdve
Operációs rendszerek MINB240
• Kvantumok értéke szálanként változhat
25
Ütemezés Windows NT-ben
Operációs rendszerek MINB240
26
Prioritási szintek NT alatt
• 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
16–31-ig 1–15-ig 0
• 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
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
• Prioritási szintek: 0-31-ig
Operációs rendszerek MINB240
• 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
27
Operációs rendszerek MINB240
28
Holtpont (deadlock)
Erőforrások
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
• 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.
29
Erőforrások fajtái 1
Operációs rendszerek MINB240
30
Erőforrások fajtái 2 Megszakítható erőforrás
• Egypéldányos erőforrás
• Ha hiba bekövetkezte nélkül elvehető az őt birtokló folyamattól (pl.: memória) • Holtpont nem áll elő
• Egyes típusokhoz egyetlen erőforráspéldány tartozik • Pl.: speciális perifériák, rajzgép, rendszertáblák, stb.
Megszakíthatatlan erőforrás
• 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
• 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
Erőforrásokkal kapcsolatos tevékenységek
Példa Adott rendszerben:
1. Erőforrás kérése - igénylés
• 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
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
2. Erőforrás használata 3. Erőforrás elengedése - felszabadítás
Operációs rendszerek MINB240
34
Holtpont kialakulásának szükséges feltételei
Holtpont
• • • •
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
35
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
Megjegyzés
Holtpont modellje
• Coffman – erőforrásholtpont • Egyéb holdpont problémák pl.: kereszteződésbeli járművek szabály szerint
• Holt (1972) a négy feltétel modellezése irányított gráfokkal • Kétféle csúcs:
közlekednek – jobbkéz szabály ütemezési holdpont
– 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
37
Operációs rendszerek MINB240
38
Példa
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)
Holtpont Operációs rendszerek MINB240
39
Operációs rendszerek MINB240
40
Példa
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. 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
1. Megelőzés – struktúrálisan holtpontmentes rendszert tervezünk 2. Elkerülés – erőforrások körültekintő lefoglalásával
Nincs holtpont
Operációs rendszerek MINB240
41
Operációs rendszerek MINB240
1. Strucc algoritmus
2. Észlelés és helyreállítás
• 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
42
43
• • • •
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
Coffman-féle holtpontdetektáló algoritmus
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
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.
45
Operációs rendszerek MINB240
2.2. Holtpont feloldása
46
3. Védekezünk a kialakulás ellen
• Á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
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
– 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
Operációs rendszerek MINB240
48
Holtpont megelőzése 1. elv Kölcsönös kizárás
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
• Egy erőforrás sincs soha kizárólagosan egy processzuhoz rendelve • Megoldás: • Háttértárban történő tárolás
49
Operációs rendszerek MINB240
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:
•
50
Holtpont megelőzése 3. elv Megszakíthatatlanság Ha elvehetnénk az erőforrást - káosz
• 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
Operációs rendszerek MINB240
52
Holtpont megelőzése 4. elv Körkörös várakozás
Megelőzési stratégiák összefoglalva
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
Feltétel
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
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
Ha i < j akkor P2-nek nincs megengedve R1 kérése Operációs rendszerek MINB240
53
Operációs rendszerek MINB240
3.2. Holtpont elkerülése Dijkstra (1965)
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
55
54
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
Példa
Ügyfelek – processzusok Bankár – operációs rendszer Egységek – erőforrás
Biztonságos –e vagy sem?
• 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
Példa
Biztonságos!
Operációs rendszerek MINB240
58
Erőforrás pályagörbék • Két processzus és két erőforrás esetén
Biztonságos –e vagy sem?
Nem biztonságos! Operációs rendszerek MINB240
59
Operációs rendszerek MINB240
60