Operációs Rendszerek II

Operációs Rendszerek II. Harmadik előadás

Első verzió: 2004/2005. I. szemeszter Ez a verzió: 2009/2010. II. szemeszter Sunday, February 21, 2010

Visszatekintés: folyamatok • Programok és erőforrások dinamikus összerendelése – a program végrehajtás alatt lévő példánya • Erőforrások: – CPU – Memória – I/O

• Folyamat és módváltás

Sunday, February 21, 2010

Szálak


Szálak – miért? • Programok egyre több párhuzamosan is végrehajtható részfeladattal bírnak – Szerver megoldások (web, file) – Kliensek esetén háttérfunkciók (backup, stb.) – Előtér párhuzamosítás (pl. web böngésző)

• A több (sok) processzor kihasználásához párhuzamosan végrehajtható kód! • Ezek a kódok nem függetlenek – közös adatok, együttműködés (szinkronizáció)!


Problémák


Problémák • Természetes megoldás: párhuzamos kód ⇒ több folyamat (hiszen erre való) • Ez így jó (is volt sokáig), de:


Problémák • Természetes megoldás: párhuzamos kód ⇒ több folyamat (hiszen erre való) • Ez így jó (is volt sokáig), de: – Létrehozásuk, megszüntetésük drága – Kommunikáció, együttműködés (drága) kernel műveletekkel lehetséges – Folyamatok közötti váltás költséges – Általában: kernel funkciók futtatása drága!


Problémák • Természetes megoldás: párhuzamos kód ⇒ több folyamat (hiszen erre való) • Ez így jó (is volt sokáig), de: – Létrehozásuk, megszüntetésük drága – Kommunikáció, együttműködés (drága) kernel műveletekkel lehetséges – Folyamatok közötti váltás költséges – Általában: kernel funkciók futtatása drága!

⇒Szálak Sunday, February 21, 2010

Szálak • Alapötlet: válasszuk külön az erőforrások birtoklását a program futtatásától! – Folyamat: erőforrás foglalás alapegysége (mint eddig is) – Szál: folyamaton belüli futási végrehajtás egysége

• Egy folyamaton belül egyszerre több végrehajtási szál is létezhet


Folyamatok, szálak


A folyamathoz képest… • Gyorsabb végrehajtás • Gyorsabb terminálás • Egy folyamaton belül – A szálak közötti váltás gyorsabb, mint a folyamatváltás – A szálak közötti adatcsere, kommunikáció kernel funkciók igénybe vétele nélkül zajlik

• Nem a folyamatok helyett van!


Megvalósítási lehetőségek • Felhasználói szálak • Kernel szálak • Hibrid megoldások


Felhasználói szálak


Felhasználói szálak • • • •

Kernel nem tud róla, továbbra is folyamatokat lát Szálmenedzsment alkalmazás szintű kóddal (lib) Szálütemezés folyamatonként eltérő lehet Előnyök – szálváltás gyors (user módban fut) – OS-től független, hordozható megoldás

• Korlátok – I/O blokkolhatja az összes folyamat-szálat (aszinkron I/O) – 1 folyamat összes szála 1 CPU! – Signal-ok kezelése nem triviális


Signal-ok kezelése • Aszinkron események (nem szinkron válasz egy hívásra) • Felhasználói szálak esetén a kernel csak folyamat szinten tudja ezeket az eseményeket kezelni • Ez is a thread könyvtár problémája…


Kernel szálak


Kernel szálak • • • •

A teljes szálmenedzsment kernel módban Felhasználói szinten csak API van A szálak ütemezést a kernel végzi Erősségek – egy szál blokkolódása nem blokkolja a teljes folyamatot – folyamat szálai több CPU-n is futhatnak – Signal kezelés megoldott

• Korlátok – drága


Mennyire „olcsó”? • Gyorsabb a létrehozás (kb. 20x) UL KL • Gyorsabb a terminálása Fork 34 us 948 us •Null Egyazon folyamat szálai között

Process 11300 us

– Gyorsabb váltás Signal Man 37 us 441 us 1840 us – Szálak közötti kommunikáció user címtérben zajlik, a kernel nélkül! 1992, VAX-on végzett mérések (UNIX-szerű környezet)


Hibrid szálak (pl. Solaris 10 előtt)


Hibrid szálak • A felhasználói szálak alkalmazás szinten értelmezettek, de vannak szálak kernel szinten is. • A kernel LWP-k (LightWeight Process) szintjén látja a folyamatokat (ezek 1:1-ben kapcsolódnak kernel szálakhoz) • Az LWP-k és a felhasználói szálak közötti kapcsolatot felhasználói szintű kód menedzseli • A felhasználói szálak és LWP-k aránya dinamikus, de kódból is módosítható • A Solaris 10-ben már nincs meg ez a megoldás!


Adatok, struktúrák • kell privát stack (user mindig, kernel szálak esetén kernel stack is) • szálaknak is van állapota /ready, run, blocked/ és prioritása, a CPU regisztereket menteni kell: TCB (a PCB-vel analóg módon)


Adatok, struktúrák


További szál-megoldások? thread

process

Name

1

1

Klasszikus (multiprocessing)

n

1

Multithreading

1

n

Experimental (in distrib. sys)

m

n

Experimental


Szálműveletek • POSIX threads (felhasználói szintű szálkönyvtár) szolgáltatások – Szálak létrehozása és megszüntetése – Üzenetek és adatok átadása szálak között – Szálak végrehajtásának ütemezése – Szál környezet mentése és visszaállítása


Ütemezés


Folyamatok ütemezése • A folyamat ütemezés célja a folyamatok és a processzor(ok) összerendelésének dinamikus szabályozása. Típusai: – Hosszú távú ütemezés – Közép távú ütemezés – Rövid távú ütemezés

• Ezen felül létezik még I/O ütemezés is


Hosszú távú ütemezés


Hosszú távú ütemezés • A programok aktiválását szabályozza (folyamat diagramban a „felvesz” állapot átmenetet jelképezi).


Hosszú távú ütemezés • A programok aktiválását szabályozza (folyamat diagramban a „felvesz” állapot átmenetet jelképezi).


Hosszú távú ütemezés • A programok aktiválását szabályozza (folyamat diagramban a „felvesz” állapot átmenetet jelképezi). • Biztosítja, hogy a multiprogramozás foka optimális legyen a rendszerben. Szempontok: – folyamatok száma a rendszerben – a CPU passzív (idle) állapotának aránya a teljes CPU időhöz képest


Megvalósítás


Megvalósítás • Kötegelt rendszerek esetén a job-ok egy várakozó sorba kerülnek, ebből választ a hosszú távú ütemező. A döntés dimenziói: – Mikor válasszon új folyamatot: multiprogramozás fokának optimalizálása – Melyik folyamatot válassza: FIFO vagy terhelési minta optimalizálás.

• Interaktív rendszerekben a felhasználó a fő ütemező, OS lehetőségei: ha a rendszer terhelése meghalad egy kritikus szintet (ez általában a folyamatok számában, esetleg a szabad virtuális memória mennyiségében mérhető), akkor nem engedi új folyamat létrehozását.


Közép távú ütemezés • Feladata komplett folyamatok mozgatása a központi memória és a másodlagos tároló (swap terület) között (swapping). • Vizsgálata a memóriakezelés ismertetése során fog megtörténni


Rövid távú ütemezés • Ez az ütemező közvetlenül és folyamatosan meghatározza a processzor(ok) és a folyamatok közötti kapcsolatot. – A hosszú- és közép távú ütemezők viszonylag ritkán aktivizálódnak csak durva ütemezési döntéseket hoznak.

• A rövid távú ütemező aktivizálódásához különböző események vezethetnek (nem mindegyik esemény érvényes minden algoritmus esetén): – – – –

Időzítő megszakítása I/O megszakítások Operációs rendszer hívások Signal-ok


Rövid távú ütemezési szempontok • Meglehetősen sokféle algoritmus létezik, egyik sem „mindenható”. • Lehetséges vizsgálati szempontok: – felhasználó vagy rendszer orientált – teljesítmény alapú vagy „egyéb”


Felhasználó vagy rendszer orientált • Felhasználó orientált eset –

az egyedi felhasználók (folyamatok) igényeit vesszük figyelembe, így például az egyes folyamatok válaszidejét. – Ezek azok a szempontok, melyeket interaktív rendszer esetén egy felhasználó valóban érzékel.

• Rendszer szempontjából – a rendszernek a kihasználtsági szint maximalizálására kell törekednie – az egyes felhasználók (folyamatok) kevésbé érdekesek, – ez a felhasználók érdekét sértheti

• Egyszerre mindkét szempontot nem lehet teljesen kielégíteni.


Teljesítmény alapú vagy egyéb • A közvetlen teljesítmény jellemzők mellett más tényezők is befolyásolják a rendszerről alkotott véleményt, pl: – megjósolhatóság: folyamatosan hasonló válaszidőket produkáló rendszer sokkal inkább elfogadható egy felhasználó számára, mint egy folyamatosan ingadozó rendszer (ugyanarra a tevékenységre vizsgálva)


Szempontok Teljesítmény alapú

Egyéb

Felhasználó - Fordulási idő (B) - Megjósolhatóság orientált - Válaszidő (I) - Határidők tartása Rendszer - Átbocsátókép. (B) - Korrektség (kiéhezt.) orientált - CPU kihasználtság - Prioritások bizt. - Erőforrások kihaszn. B: batch (kötegelt, I: Interaktív


Algoritmusok jellemzői • Folyamat megszakíthatósága • Prioritások alkalmazása • A döntés alapja (amely alapján meghatározzuk a kiválasztandó folyamatot)


Algoritmusok jellemzői • Folyamat megszakíthatósága (preemptive) • Meghatározza, hogy az ütemező algoritmus megszakíthatja-e egy folyamat futását, vagy az csak akkor szakad meg, ha a folyamat lemond a CPU-ról vagy erőforrás miatt blokkolódik. • A megszakítható ütemező algoritmusok általában bonyolultabbak, jobban terhelik a rendszert – ugyanakkor sokkal korrektebb ütemezési megoldást biztosítanak.


Algoritmusok jellemzői • Folyamat megszakíthatósága • Prioritások alkalmazása • Több olyan algoritmus is van, ahol a folyamatok közötti választást egy, a felhasználó által meghatározott fontossági információ (prioritás) befolyásolja. • A „tiszta” prioritásos megoldás fő problémája az alacsonyabb prioritású folyamatok kiéheztetése.


Algoritmusok jellemzői • Folyamat megszakíthatósága • Prioritások alkalmazása • A döntés alapja több paraméter közül kerülhet kiválasztásra: – A folyamat rendszerben eddig eltöltött összes ideje (várakozás és végrehajtás egyaránt): w – Az eddig futással eltöltött idő: e – A folyamat becsült teljes kiszolgálási ideje (az eddig eltöltött időt is beleértve): s – Fontos látni, hogy a kiszolgálási idő valóban csak becsülhető – amely az esetleges múltbéli tapasztalatok alapján pontosítható. A túlzottan optimista folyamatok futását (amelyek az előre megadottnál sokkal tovább kívánnak futni) a megadott idő letelte után a rendszer megszakíthatja.


Vizsgált algoritmusok • • • • • • •

FCFS (FIFO) Round Robin Shortest Process Next Shortest Remaining Time Highest Response Ratio Next Feedback Lottó ütemezés


FCFS (FIFO) • Működés – A legegyszerűbb algoritmus, amely beérkezésük sorrendjében futtatja a folyamatokat. – Az algoritmus nem megszakítható, ha valamely folyamat blokkolódik, helyette a legrégebben a sorban található folyamat kerül kiválasztásra.

• Értékelés – Az algoritmus előnybe részesíti a CPU igényes folyamatokat, hiszen azok sokkal ritkábban blokkolódnak, mint az I/O igényes folyamatok. – Az algoritmus következtében az I/O eszközök kihasználtsága meglehetősen rossz.


Vizsgált algoritmusok

Folyamat rendszerben eddig eltöltött összes ideje: w Az eddig futással eltöltött idő: e Folyamat becsült teljes kiszolgálási ideje (az eddig eltöltött időt is beleértve): s Sunday, February 21, 2010

Példa – FCFS (FIFO) Folyamat

A

B

C

D

E

Érkezik

0

2

4

6

8

Kisz. idő

3

6

4

5

2


Round Robin • Az interaktív rendszerek alapalgoritmusa. Az időzítő periodikusan megszakításokat generál, a kernel minden megszakításkor másik folyamatot választ ki futásra a futásra kész folyamatok közül – így alapesetben minden folyamat egy időszeletnyi ideig futhat. • Az algoritmus egyik alapvető kérdése az időszelet hosszának meghatározása. – Nagyon rövid időszelet választásával a rövid folyamatok gyorsan végrehajtásra kerülnek, ugyanakkor a sok folyamatváltás komoly többletterhet ró a rendszerre. – Legcélszerűbb olyan időszeletet választani, amely egy tipikus interakció végrehajtását lehetővé teszi – ez a megoldás kifejezetten jó hatással van a válaszidőre.


Round Robin (értékelés) • Használható általános célú ütemező • I/O igényes folyamatokkal szemben igazságtalan – az I/O igényes folyamat viszonylag gyorsan blokkolódik, így az időszelete egy részét elveszti – összességében a CPU igényes folyamatok sokkal több időt kapnak, mint az I/O igényes társaik.

• Módosított algoritmus a fenti probléma megoldására – a várakozósor két sorból áll: az egyik „normál” várakozósoron kívül van egy sor a blokkolásból visszatérő folyamatok számára is. – Amíg a második sor nem üres, a kernel ebből választ folyamatot – azonban ez a folyamat csak a blokkoláskori időszeletéből megmaradt időtartamig futhat (ezután – ha nem blokkolódik ismét – visszakerül a normál várakozósorba).




Példa – Round Robin Folyamat

A

B

C

D

E

Érkezik

0

2

4

6

8

Kisz. idő

3

6

4

5

2


Shortest Process Next • Az ütemező mindig azt a folyamatot választja, amelynek legrövidebb a becsült teljes kiszolgálási ideje • Rövid folyamatokat favorizálja a hosszabbakkal szemben • Nem megszakítható algoritmus




Shortest Remaining Time • Az SPN egy megszakítható változatának tekinthető – Mindig az a folyamat lesz futásra kiválasztva, amelynek legkisebb a várható futási időszükséglete (tehát ami még hátra van) – Amennyiben folyamat kerül a várakozósorba (pl. blokkolódásból visszatér), a megtörténik a folyamatok felülvizsgálata, és a legrövidebb folyamat kiválasztása




Példa – SPN, SRT Folyamat

A

B

C

D

E

Érkezik

0

2

4

6

8

Kisz. idő

3

6

4

5

2


Highest Response Ratio Next • Célja a fordulási idő és az aktív idő (mikor a folyamat valóban futott) arányának minimalizálása. – (nem megszakítható módon) mindig azt a folyamatot választja ki, amely esetében az R= (w+s)/s hányados értéke a legnagyobb. – w a rendszerben eltöltött összes idő, s pedig a becsült teljes kiszolgálási idő.

• Előnye: figyelembe veszi a folyamatok korát Sunday, February 21, 2010



Példa – HRRN Folyamat

A

B

C

D

E

Érkezik

0

2

4

6

8

Kisz. idő

3

6

4

5

2


Feedback • Az előző algoritmusok közös problémája az, hogy alkalmazásukhoz legalább becsléssel kell rendelkeznünk az adott folyamat várható futási idejéről – ez pedig sok esetben nem lehetséges. • A feedback algoritmus az ütemezési döntést a folyamat eddigi „élete” alapján hozza meg. • Az algoritmus megszakítható, időszelet alapú azonban változtatható prioritásokat használ: – minél hosszabb ideje fut a folyamat a rendszerben, annál jobban csökken a prioritása (egy minimum értékig).


Feedback (értékelés) • Probléma: az algoritmus a hosszú folyamatokat komolyan bünteti – Megoldás: különböző prioritási szintek esetén eltérő időszeleteket használ: minél alacsonyabb a prioritás, annál hosszabb az időszelet

• Probléma: sok rövid folyamat könnyen kiéheztet egy hosszabb folyamatot – Megoldás: az algoritmus módosított változatában a várakozó folyamatok prioritása lassan növekszik




Lottó algoritmus • A klasszikus változó prioritásos ütemezők problémáit próbálja kiküszöbölni: – nem lehet a folyamatoknak CPU birtoklási arányt megadni – egy felhasználó monopolizálhatja a rendszert ha sok folyamatot indít

• Minden folyamat adott számú (sors)jegyet kap, az ütemezés „véletlen” sorshúzással zajlik. A folyamatok CPU birtoklási aránya a kapott jegyek számán alapul • Ha a jegyeket a felhasználóhoz rendeljük, akkor az összes folyamata számára adunk birtoklási arányt – nem lehet monopolizálni a rendszert • A megoldás egyik komoly hátránya az, hogy a blokkolás miatt elveszett idő-töredékek valóban elvesznek – erre az algoritmus továbbfejlesztése ad megoldást


Az ütemezők fejlődése • A fejlődés mozgatórugói – Többprocesszoros rendszerek megjelenése – Valós idejű ütemezési igények megjelenése


Ütemezés többprocesszoros rendszerekben - szemcsézettség Szemcsézettség

Leírás

Szinkronizálási időszak (utasítások)

Finom

A párhuzamosság utasítás szintű

Közepes

Párhuzamos feldolgozás egy folyamaton belül

20-200

Durva

Konkurrens, együttműködő folyamatok multiprogramozott rendszerben

200-2000

Nagyon durva

Elosztott feldolgozás hálózaton keresztül összekapcsolt csomópontokon, amelyek közös környezetet alkotnak

2000-1M

Független

Egymástól független folyamatok


Kevesebb, mint 20

N.A.

Folyamatok és processzorok összerendelése • Az összerendelés lehet – Statikus (a folyamat CPU-hoz kötött) – Dinamikus (mindig az éppen szabad CPU-t használjuk)

• SMP megoldások esetén a statikus összerendelés jelentős teljesítmény problémákat okozhat (bár sokkal egyszerűbb megvalósítani) – az egyik CPU várakozósorában több folyamat várakozik, míg egy másik CPU kihasználatlanul várakozik.


Kernel folyamatok és processzorok összerendelése • Kernel folyamatok CPU-hoz rendelése történhet – master/slave – peer

• Master/slave esetben a kernel kulcsfunkcióit valamely CPU-hoz kapcsoljuk. – Ez a megoldás jelentősen leegyszerűsíti a működést, de ez a CPU könnyen szűk keresztmetszetté válhat.

• Teljesen dinamikus működés esetén viszont arról kell gondoskodni, hogy ha a két CPU egyszerre aktivizálja valamely kernel funkciót, akkor nehogy ütközés legyen.


Egyes CPU-k multiprogramozása (statikus összerendelésnél) • Elvben lehetséges, de… • Ha sok CPU van a rendszerben 1-1 CPU kihasználtsága nem igazán fontos • Sok esetben a szálak akkor tudnak igazán hatékonyan futni, ha egyszerre aktívak (egyéb esetben a közöttük fellépő szinkronizációs igény jelentősen visszaveti a működést). • Előfordulhat, hogy több szál együttes futása fontosabb, mint minden CPU folytonos kihajtása.


Folyamatok és szálak ütemezése • A tradicionális multiproc. rendszerek – Folyamat alapú ütemezés –Folyamatokat nem kötjük hozzá processzorokhoz, jellemzően egy közös várakozósorba szervezzük őket

• Mai multiprocesszoros rendszerek – Ütemezés szál alapon történik


Szálak ütemezése • Egyprocesszoros rendszerekben a szálakat a programozás megkönnyítésére használták • Többprocesszoros rendszerekben a szálak már a valós párhuzamosság kihasználására is alkalmasak • Ebben az esetben azonban fontos lehet, hogy a párhuzamos szálak valóban egy időben fussanak (kommunikáció).


Szálak üzemezésének módjai • Terhelés megosztás: az egyprocesszoros rendszerek esetén megismert megoldást terjesztjük ki MP rendszerekre • Csoportos ütemezés, a szálak és a CPU-k között 1:1 megfelelést alakítunk ki, a folyamat futásához pontosan annyi CPU kell, amennyi szála van • Dedikált CPU-k, a CPU-kat a folyamat élete alatt hozzárendeljük az adott folyamathoz • Dinamikus ütemezés, dinamikusan kezeljük a folyamatokhoz tartozó szálak számának változását


Terhelés megosztás • Jellemzők – Terhelést egyenlően osztjuk szét a CPU-k között – Nincs szükség központi ütemezésre, minden szabad CPU magának választ folyamatot • Ehhez kell egy globális folyamat-sor

• Hátrányok – A folyamat-sor szűk keresztmetszet lehet, bár ez a probléma több tíz, sőt több száz CPU esetén jelentkezik – A szálak nem biztos, hogy az előzőleg kiválasztott CPU-hoz térnek vissza, ami lokális gyorsítótárral rendelkező CPU-k esetében problématikus – Több szálból álló folyamat esetén nem valószínű, hogy az összes szál egyszerre aktivizálódik – ez pedig a szál szinkronizáció során teljesítmény probléma.

• Hátrányai ellenére ez a legelterjedtebb ütemezési mód!


Csoportos ütemezés • Több (egy folyamathoz tartozó) szál együttes kiválasztásának előnyei – a szorosan kapcsolódó szálak szinkronizáció miatti blokkolódásának problémája jelentősen csökken – ütemezési terhelés többlet kisebb, hiszen egy döntés több CPU-t is érint

• Ehhez az ütemezéshez szükséges valamilyen CPU foglalási algoritmus


Dedikált CPU hozzárendelés • A csoportos ütemezésnek egy extrém formája. • Látszólag rendkívül CPU pazarlóan működik (hisz nincs CPU szintű multiprogramozás), bizonyos esetekben megoldás lehet – Sok CPU-s rendszerekben (akár 100 feletti CPU számmal), egyetlen CPU a költségeknek töredékét képviseli – A folyamatváltások elmaradása a folyamat teljes futási idejére jótékonyan hathat


Dinamikus ütemezés • Sok esetben a folyamathoz tartozó szálak számossága folyamatosan változhat, így a statikus összerendelések nem túl hatékonyak • Ezek az algoritmusok általában az operációs rendszerek és a folyamatok közötti együttműködést igénylik – Az operációs rendszer feladata a CPU-k szétosztása a folyamatok között, a többi már a folyamat szint feladata


Operációs Rendszerek II

Recommend Documents