Shortcut to the NerveCenter InfoTetel2

| RecentChanges | FrontPage |
2. Tétel: Operációs rendszerek processzuskezelése. Klasszikus IP problémák (filozófusok, iró-olvasó, alvó borbély), kritikus terület, szemaforok, ütemezési algoritmusok.


Alapvetõ definíciók

  • Szoftverek osztályozása : rendszerprogram / felhasználói program

  • Operációs rendszer := A legalapvetõbb rendszerprogram amely a számítógép erõforrásait kezeli és azt az alapot biztosítja, amelyen felhasználói programok írhatóak (és futtathatóak).

  • Erõforrás := Minden olyan dolog amelyre egy programnak szüksége lehet a futása során. Pl.:
    • CPU idõ
    • memória
    • B/K eszközök
    • adatállományok
    • fájlrendszer
    • kommunikációs szolgáltatások
    • stb...

  • Processzus := Egy végrehajtás alatt álló program annak környezetével és állapotával együtt. A környezetének része a hozzárendelt memóriaterület, a nyitott fájlok (fájlleírók), CPU állapota, futás állapota is.

  • Processzus állapotok := Az operációs rendszer egyik erõforrása a CPU. A rendszerben egyszerre futtatható processzusok mennyisége véges, CPU mennyiség és típus függõ. Annak eldöntése, hogy mely CPU erõforrás melyik processzust futtatssa egy adott idõben, az ütemezõ feladata. Az ütemezõ része az operációs rendszernek. Az ütemezõ mûködése során a processzusokhoz állapotokat rendel:


Szálak és szinkronizáció

Szálak := Azonos memóriaterületen (címtartományban), de külön ütemezett és külön futási állapottal bíró végrehajtási egységek. Modern operációs rendszerekben az ún. egyszálú programot is szálakkal valósítják meg.

Olyan esetekben amikor egymással konkuráló végrehajtási egységek azonos erõforrásokat érnek el szükség lehet az elérések szinkronizációjára. Ennek hiányában az adott erõforrás nem tervezett állapotot vehet fel amely program hibához vezet. Az ilyen helyzeteket versenyhelyzetnek is hívják. Ennek elkerülésére szinkronizációs mechanizmusokat használhatunk fel:

Mutex (Mutual exclusion) := Kölcsönös kizárás mechanizmusa. Ha egy végrehajtási egység birtokolja, akkor másik végrehajtási egység nem birtokolhatja. Ha a másiknak szüksége van rá, várnia kell. Mûveletei:

  • Lock
  • Unlock

Read-Write lock := író-olvasó lock. Egyszerre max. 1 író, vagy tetszõleges számú olvasó birtokolhatja. Egyes implementációk engedik az olvasó-író átmenetet, amikor egy olvasó van. Mûveletei:
  • Read Lock
  • Write Lock
  • Upgrade Lock
  • Unlock
 

Szemafor := A szemafor megadott számú konkurens elérést enged. Amikor a megadott számú végrehajtási egység már birtokolja, a következõnek várnia kell amíg, az egyik elengedi. Mûveletei:
  • Down
  • Up

Kritikus terület := Egy program részt lehet védeni vele, hogy a kritikus terület eleje és vége között maximum egy végrehajtási egység tartózkodhat, a többi amely szintén azt a kódrészletet készül végrehajtani, várni fog. Mûveletei:
  • Enter
  • Leave

Barrier := Az ellenkezõje a szemafornak. Megadott számú végrehajtási egységet bevár. Amikor mind elérkezik a barrierhez-akkor egyszerre futni engedi õket. Mûveletei:
  • Wait

A programozó feladata, hogy az adott feladathoz kiválassza a megfelelõ szinkronizációs mechanizmust. A megfelelõ kiválasztása sebesség szempontjból kritikus lehet, mivel ezek különbözõ mértékû párhuzamos futást tesznek lehetõvé.


Processzusok közötti kommunikáció (Inter Process Communication=IPC)

Feladatoktól függõen szükség lehet különbözõ processzusok információ cseréjére. Az információ csere speciális módjai a már említett szinkronizációs mechanizmusok. Ezen kívül lehetõség van adatok átadására is a következõ mechanizmusok valamelyikével:

  • Üzenet küldés
  • Osztott memóriába írás és olvasás onnan


Filozófusok

1965-ben Dijkstra felvetett és megoldott egy szinkronizációs problémát, amelyet étkezõ filozófusok problémának nevezett el. A probléma a következõ: öt filozófus ül egy kerek asztal körül. Mindegyik filozófusnak van egy tányér spagettije. A spagetti olyan csúszós, hogy egy filozófusnak két villára van szüksége, hogy megegye. Minden egymás melletti tányér között van egy villa. A filozófusok élete egymást váltogató evésbõl és gondolkodásból áll. Amikor egy filozófus éhes lesz, megpróbálja megszerezni a bal és jobb oldalán lévõ villát, egyszerre csak egyet, tetszõleges sorrendben. Ha sikerül mindkét villát megszereznie, akkor eszik egy ideig, majd lerakja az evõeszközöket és gondolkodik. Kulcskérdés: tudunk-e olyan programot készíteni mindegyik filozófus számára, amelyik azt csinálja, amit elvárunk és soha nem akad el? A nyilvánvaló megoldás (próbálja megszerezni a bal oldalon lévõ villát, majd ha ez megvan, szerezze meg a job oldalon lévõt) sajnos hibás. Ha ugyanakkor szerzi meg mind az öt filozófus a bal oldali villát, akkor nem lesz villa a jobb oldalon és holtpont alakul ki. Az sem segít, ha várakozunk. Véletlen ideig történõ várakozás nem hoz garantált sikert. A korrekt megoldás bináris szemaforokat használ.


Iró-olvasó

Az író-olvasó probléma nem más, mint az adatbázisok hozzáférési problémáit modellezõ feladat (például repülõjegy-foglalás). Elfogadható, hogy több olvasó legyen a bázisban egyidejûleg, de az írónak kizárólagos jogot kell adni a hozzáféréshez. Ha az olvasó mindig új olvasókat enged maga mellé, (mert teheti), akkor hatékony egyidejûséget kapunk. Ugyanakkor a bázis elõtt akár a végtelenségig is várakozhat egy író, hogy az olvasók elfogyjanak, és egyedül maradjon a bázisban. Ezt elkerülendõ, ha író várakozik, és újabb olvasó érkezik, azt az író maga mögé parancsolja. Csak azt kell megvárnia, hogy a bázisban tartózkodó olvasók elfogyjanak. Ez a módszer kevésbé hatékony, mert nem támogatja az egyidejû olvasást oly mértékben, mint a filozófusos.


Alvó borbély

Megint egy másik klasszikus IPC probléma a borbélynál fordul elõ. A fodrászüzletben egy borbély van, egy fodrászszék, és n szék a várakozó vendégeknek. Ha éppen nincs vendég, akkor a orbély leül a fodrászszékbe és elalszik. Ha egy vendég érkezik, fel kell ébresztenie. Ha további vendégek érkeznek, míg a borbély egy vendég haját vágja, akkor vagy leülnek (ha van üres szék) vagy elmennek (ha minden szék foglalt).

Megoldásunk három szemafort használ: customers (a várakozó vendégeket számolja, a fodrászszéken ülõ kivételével), barbers (az unatkozó borbélyok száma, értéke 0 vagy 1 lehet) és mutex (a kölcsönös kizárásra használunk.


Ütemezési algoritmusok

  • Round-Robin := Az ütemezési egységek sorban egymás után kerülnek futó állapotba. Minden végrehajtási egység azonos mennyiségû idõt kap. A kiosztott idõszeletrõl önszántából lemondhat, ha olyan rendszerhívást hív amely blokkolást eredményez.

  • Prioritásos ütemezés := A legmagasabb prioritású végrehajtási egység fog futni. Az egyes egységek prioritása idõben változhat. Például futás után átmenetileg csökkenthetõ azért, hogy a többi processzus is futhasson.

  • Prioritási osztályok := Azonos osztályon belül round-robin ütemezés.

  • Garantált ütemezés := Az ütemezõ figyel arra, hogy n darab processzus 1/n idõt használjon fel.

  • Sorsjáték ütemezés := Minden ütemezési egység egy sorsjegyet kap, amelyek közül az ütemezõ véletlenszerûen választ.

  • Valós idejû ütemezés := Külsõ fizikai eszközök számára garantálja, hogy a hardver megszakítás megadott idõn belül feldolgozásra kerüljön.


Vissza: [InformatikaSzigorlat][LaPm][FrontPage]
 EditPageRegexSearch: