1. Az operációs rendszerekről általában

Operációs rendszer fogalmának meghatározása.

Az operációs rendszerek funkciója:

Az operációs rendszerek feladatai:

Alternatívák az operációs rendszer részének tekintett programok meghatározására:
    1. Az operációs rendszerek típusai a történetük tükrében

Az operációs rendszerek fejlődése párhuzamos a HW fejlődésével.

A HW hatékony kihasználásának alapvető eszközei:

Batch típusú rendszerek:

Megoldások I/O műveletek gyorsítására:

 

Multiprogramozott rendszerek:
hatékony megoldás különböző programok CPU és a perifériás műveleteinek átlapolására, vagyis a HW hatékony kihasználására.

Felvetődő problémák:

Időosztásos rendszerek (time sharing):
gyors job váltás

Interaktív rendszerek:
rövid válaszidők, on-line file rendszer

Napjaink rendszerei:

      1. Személyi számítógépes rendszerek

        2. Eredetileg kiskapacitású, egyfelhasználós rendszerek, mára kapacitásuk közelít a nagygépes rendszerek teljesítményéhez.

      2. Párhuzamos rendszerek

Csoportosításuk alapja:

      1. Elosztott rendszerek

Lazán csatolt rendszerek.

Elosztott operációs rendszerek előnyei:

      1. Valósidejű (real time) rendszerek

külső események bekövetkezésére garantált válaszidő.

    1. Számítógépek felépítése

Busz struktúra: CPU, memória, vezérlők.

Interrupt-ok, rendszerhívások és végrehajtásuk.

ROM program rendszer betöltéséhez.

Be- és kivitel (I/O):

Védelmi mechanizmusok:

Számítógépek adattároló eszközeinek hierarchiája.

    1. Operációs rendszerek részei és szolgáltatásai
      1. Rendszerkomponensek
      1. Operációs rendszerek legfontosabb szolgáltatásai
    1. Az operációs rendszerek felépítése

Komplex, nagyméretű szoftver rendszer. Alapvető felépítés:

  1. Folyamatok

    2. A folyamat (process) a multiprogramozott rendszerek alapfogalma.

    1. Folyamatok definíciója

      2. Általános meghatározás: műveletek meghatározott sorrendben történő végrehajtása. Sorrend az ún. vezérlési szál által definiált.

      1. Logikai modell

Oszthatatlan utasítások:

Folyamat állapotának jellemzői:
      1. Gyakorlati modell

Végrehajtás alatt álló "életre kelt" program, kód és adatterületeivel együtt.

Folyamat memóriaterületének részei:

Multiprogramozott rendszer:

Szükséges egy folyamat végrehajtásának leállítása, ill. újraindítása.

    1. Folyamatok állapota

Folyamat környezet (context) fogalma: program és végrehajtó gép állapota. Azon információ összessége, amit szükséges elmenteni egy folyamat későbbi újraindításához.

Környezetváltás definíciója: a CPU-t birtokló futó folyamat váltása.

Egy folyamat környezetének részei:

Folyamat memóriaterületének részei:

    1. Szálak (thread, lightweight process)

      2. A szálak olyan együttműködő folyamatok, melyek környezete részben (a program számláló, a CPU regiszterek tartalma és a veremtár kivételével minden) közös. Azonos erőforrásokat használnak így a szálak között történő környezetváltás összehasonlíthatatlanul gyorsabb, mint a folyamatok között.

    2. Folyamatok ill. szálak használatának előnyei
    1. Párhuzamos folyamatok viszonya
  1. Folyamatok együttműködése

Alapfogalmak:
    1. Folyamatok közötti információcsere (kommunikáció)

Információcsere formái:
      1. Közös tárterületen történő kommunikáció

PRAM (Pipelined/Parallel Random Access Memory) modell:
      2. Kommunikációs csatornán keresztül történő üzenetváltás

Séma:

A rendszerezés szempontjai: (részben önkényes választás)
      1. Kommunikáló partner megnevezése

A kommunikáló partner megnevezése alapján az üzenetváltás lehet

Közvetlen kommunikáció:

Közvetett kommunikáció:

 

Aszimmetrikus kommunikáció

Csatorna használata (közvetlen FIFO összeköttetés két folyamat között)

Csatorna jellemzői:

Csatorna használatának szintaxisa:

Ki vagy bemeneti (port) kapu használata:

Csoport kommunikáció

Üzenetküldő műveletek szemantikája

Csatorna megbízhatatlan lehet távoli kommunikáció esetén. Kezelendő hiba események:

Üzenetek sérülésének megakadályozása az üzenet kódolásával

Hibakezelés technikája:

Üzenetváltás módja:

Műveletek általános paraméterei:

  1. Szinkronizáció
    1. A szinkronizáció formái
    1. Gyakorlati példa

      2. Egy nyomtatót használó folyamat példáján keresztül megvizsgáljuk egy tipikus termelő-fogyasztó (felhasználó) szituációban előforduló feladatokat és azok egy lehetséges megoldását.

      Termelő

      repeat
      [Készít egy új kinyomtatandó adatot a következőKész változóban.]
      while teliElemekSzáma >= n do üresUtasítás;
      buffer[következőÜres]:= következőKész;
      következőÜres:= (következőÜres + 1) mod n;
      teliElemekSzáma := teliElemekSzáma + 1;
      until false;

      Fogyasztó

      repeat
      while teliElemekSzáma <= 0 do üresUtasítás;
      következőFeldolgozandó := buffer[következőTeli];
      következőTeli := (következőTeli + 1) mod n;
      teliElemekSzáma := teliElemekSzáma - 1;
      [Kinyomtatja a következőFeldolgozandó változóban tárolt adatot.]
      until false;

      Probléma

      A teliElemekSzáma inkrementálásának ill. dekrementálásának gépi utasításai párhuzamosan (átlapolódva) hajtódnak végre, az eredmény a végrehajtás sorrendjétől függ.

      Inkrementálás

      MOV AX, teliElemekSzáma
      INC AX
      MOV teliElemekSzáma, AX

      Dekrementálás

      MOV AX, teliElemekSzáma
      DEC AX
      MOV teliElemekSzáma, AX
    2. Kritikus szakasz

A kritikus szakasz olyan utasítássorozat a programban, amelyen belül egyidejűleg csak egyetlen folyamat tartózkodhat, a kritikus szakaszt a belépő (entry) és kilépő (exit) utasítások határolják.

A kritikus szakasz helyes implementálásának kritériumai:

      1. A kritikus szakasz implementálása

Tisztán programozott megoldások

Két folyamat esetén:

entry:
flag [i] := IGAZ;
következő := j;
while ( flag[j]==IGAZ and következő == j )
do { üres utasítás };
exit:
flag [i] := HAMIS;

Mind a három kritikus szakaszra vonatkozó feltételt teljesíti a fenti megoldás.

Tetszőleges n folyamat esetén használható megoldások jóval bonyolultabbak.

Kritikus szakasz megvalósítása HW támogatással

Speciális, megszakíthatatlan, egyidejűleg több tárműveletet végző hardver utasítások:

TestAndSet
entry:
while TestAndSet(lakat) do { üres utasítás };
exit:
lakat:= false;

Swap
entry:
kulcs := IGAZ;
repeat
swap(lakat, kulcs);
until (kulcs == HAMIS);
exit:
lakat:= HAMIS;

A fenti megoldások csak az első kettő kritikus szakaszra vonatkozó feltételt teljesítik. A harmadik feltétel is kielégíthető, azonban annak megoldása bonyolultabb.

Szemafor

Speciális adatszerkezet és rajta értelmezett oszthatatlan utasítások; 

init(s, v):
   s := v;

P(s):
   while s <= 0 do { üres utasítás };
   s := s - 1;

V(s):
   s := s + 1
 
 		init(s,1)
entry: 	P(s)
exit:  	V(s)
init(s,O);
1. folyamat:
Utasítás1;
V(s);
2. folyamat:
P(s);
Utasítás2;
 
P(s):
 if s <= 0
 	then tedd a várakozó listára és altasd el;
 else s := s - 1;

V(s):
 if várnak rá és a várakozó lista nem üres
   then leveszi és felébreszti az elsőt a várakozók közül;
 else s := s + 1;

Kritikus szakasz megvalósítása magas szintű programnyelvekben

Erőforrások ill. változók és a rajta műveleteket végző, kritikus szakaszba tartozó utasítások magas szintű nyelvi szerkezetben.

Kritikus szakasz

region változó do utasítások end

Feltételes kritikus szakasz 

region változó when feltétel
      do utasítások end

A megvalósítás problémái:

Monitor

A közösen használandó erőforrás és az összes rajta végezhető művelet egyetlen szintaktikus egységbe (monitor) zárva;

Felépítése:

A monitor olyan program modul (önálló fordítási egység), amely automatikusan kölcsönös kizárást biztosít a belépési pontja (entry point) eljárásaira.

Csak kölcsönös kizárást valósít meg, egyéb szinkronizáláshoz más eszköz kell.

Ez az eszköz az ún. feltételes változó (conditional variable), ami bináris szemaforhoz hasonló adattípus, két speciális belépési ponttal:

  1. Folyamatok modellezése az operációs rendszerekben
    1. Folyamatok állapotátmenet diagrammja

Folyamatok állapotai:

Állapotátmeneti diagramm:

    1. Folyamatok sorbanállási modellje

Hatékony rendszermodell, ha feltételezzük, hogy egyidőben egy folyamat csak egy erőforrást foglal, ill. használ.

  1. CPU ütemezés

Az ütemezés (scheduling) fogalma: az azonos erőforrásra igényt tartó folyamatok közül választás, az erőforrások allokálása.

A CPU ütemezés kategóriái:

A rövidtávú CPU ütemezési algoritmusok alapjai:

ütemezés helye az állapotátmenet diagrammban:

Az ütemezési algoritmusok összehasonlítására lehetőséget adó paraméterek:

Követelmények (néha ellentmondó példák):

    1. Egyszerű ütemezési algoritmusok
    1. Prioritásos ütemezési algoritmusok

A prioritás típusai:

Az ütemezés lehet preemptív és nem preemptív is. Általában fennáll a kiéheztetés (starvation, indefinit postponement) veszélye. Elkerülése az ún. öregítés (aging) használatával.

      1. Prioritás meghatározása a CPU löketidő alapján

Algoritmusok:
    1. Többszintű ütemezési algoritmusok

Alternatívák:

Algoritmusok:
    2. Többprocesszoros ütemezés

Többprocesszoros ütemezés megvalósításának feltételei:

lehet szimmetrikus vagy aszimmetrikus ütemezés, kölcsönös kizárás biztosítása szükséges

    1. Ütemezési algoritmusok hatékonyságának meghatározása
  1. Holtpont

A holtpont (deadlock) fogalma: több folyamat olyan eseményre, erőforrás felszabadulására vár, amelyet másik, ugyancsak várakozó folyamat tud előidézni.

Fontos, hogy a kiéheztetés és a holtpont különböző fogalmak!

Az erőforrások modellje:

    1. A holtpont kialakulásának feltételei

A holtpont kialakulásának szükséges feltételei:

  1. kölcsönös kizárás,
  2. foglalva várakozás,
  3. nem elvehető erőforrások,
  4. körkörös várakozás.

A holtpont kialakulásának elégséges feltétele:
A fenti 4 szükséges feltétel, valamint minden erőforrás osztályban csak egyetlen erőforrás van.

    1. Holtpont kezelési stratégiák

Holtpont kezelési stratégiák:
      1. A holtpont megelőzése

A holtpont kialakulásának valamelyik szükséges feltételének kizárása.

  1. kölcsönös kizárást nem lehet kiküszöbölni,
  2. foglalva várakozás kizárása: egy folyamat csak akkor kérhet új erőforrást, ha nem tart lefoglalva másikat,
  1. nem elvehető erőforrások: erőforrások elvétele egyes folyamatoktól,
  2. körkörös várakozás kizárása: erőforrások megszámozása, az erőforrások csak sorrendben igényelhetők.
      1. A holtpont elkerülése

Az erőforrások óvatos allokálásával elkerülhető a holtpont kialakulása; de a folyamatok erőforrás-igényéről kiegészítő információval kell rendelkezni:

Feltététezzük, hogy a folyamat erőforrás igényének kielégítése után véges időn belül visszaadja az összes erőforrást.

Módszer:
      1. A holtpont felismerése
      2. A holtpont felszámolása
      1. Kombinált holtpont-kezelő stratégiák

Különböző erőforrás-típusokhoz más-más stratégiát használhatunk, pl.:

 

 

------------------------------------------------------------------------------------

Megszakítások kezelése: megszakítás kiszolgálásainak lépései.

Alapvető módszerek:

-------------------------------------------------------------------------------------

  1. Tárkezelés
    1. Adattároló eszközök hierarchiája

Számítógépek adattároló eszközeit hierarchiába rendezhetjük.

A hierarchiában lefelé nő az adatok elérési ideje, de csökken az egységnyi tárolókapacitás ára, így a tárolók kapacitása.

A számítógépek működése során szükséges a tárolók közötti adatmozgatás.

Az adatmozgatás meggyorsítására gyorsító tárakat (cache) alkalmaznak a hierarchia minden szintjén.

A gyorsító tárak alkalmazásának lehetőségét, ill. a hatékonyságuk magyarázatát a programok működésének lokális volta biztosítja.

    1. Központi tár kezelése

A tárkezelés szerepe az operációs rendszerekben:

Klasszikus tárkezelés fő kérdései:

      1. Programok címeinek kötése

A logikai-fizikai cím hozzárendelés történhet:

      1. Gazdaságos memóriakihasználás megvalósítása

Három megközelítés:

      1. Társzervezési elvek

50%-os szabály: átlagosan a használt tár 50%-ának megfelelő memória (vagyis a teljes tár egyharmada) kihasználatlanul marad a tördelődés miatt.

 

 

      1. Programok címeinek kötése futási időben

Hardver támogatás szükséges:
      1. Tárcsere (swap)

Logikai címek fizikai címmé való transzformálásának módszerei:

Különböző módszerek által használt adatszerkezetek, a módszerek összehasonlítása.

      1. Virtuális memóriakezelés

A hardver támogatta címtranszformáció lehetővé teszi az időlegesen nem használt memórialapok háttértárra történő mentését.

Feladatok:
    2. Állományrendszer

Alapfogalmak:

Állománykezelő feladatai:

Az állományrendszer réteges implementációja:

Adatszerkezetek a lemezen:

      1. Szabad helyek nyilvántartása
      1. Állományokhoz tartozó blokkok nyilvántartása
      1. Állományok elérése

Állományok belső szerkezete:

Állomány hozzáférési módok:

Műveletek az állományokon:

Állománykezelés során használt adatszerkezetek:

      2. Könyvtárak

Könyvtárak hierarchiája:

Hozzáférés szabályozása:

    2. Háttértár (mágneslemez) kezelés

Háttértár tulajdonságai:

Háttértár típusok:

      1. A lemezek fizikai szerkezete

 

      1. Lemezműveletek ütemezése

A lemezműveletek ütemezésénél a fejmozgásra koncentráló algoritmusokkal foglalkozunk.

Egyéb gyorsítási lehetőségek:

Megbízhatóság növelésének lehetősége: rendszeres mentés, redundáns tárolás, elosztott tárolás