Operációs Rendszerek

1. 1997. szeptember 17. szerda
2. 1997. szeptember 24. szerda
3. 1997. október 1. szerda
4. 1997. október 8. szerda
5. 1997. október 15. szerda
6. 1997. október 22. szerda
7. 1997. október 29. szerda
8. 1997. noveber 5. szerda
9. 1997. noveber 12. szerda
10. 1997. noveber 19. szerda
11. 1997. noveber 26. szerda
12. 1997. december 3. szerda
13. 1997. december 10. szerda
14. 1997. december 17. szerda

Az operációs rendszerekrôl általában

• a felhasználók (és programozók) kényelmének biztosítása,
• hatékony HW kihasználás.

• végrehajtási környezet biztosítása,
• erõforrás elosztás,
• vezérlõ program.

• a számítógépen állandóan futó vezérlõ program (kernel),
• minden a gép általános felhasználásához szükséges program.

Az operációs rendszerek története

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

Korai rendszerek:

• nincs operációs rendszer (open shop),
• operátor alkalmazása (closed shop)
• kötegelt feldolgozás (batch),
• egyszerû monitor.

A HW hatékony kihasználásának alapvetô eszköze a CPU és a perifériás mûveletek átlapolása.

Korai megoldások:

• off-line feldolgozás,
• pufferelés,
• spooling.

Multiprogramozott rendszerek:

• hatékony megoldás különbözô programok CPU és a perifériás mûveleteinek átlapolására.
• Felvetôdô problémák:
• tárgazdálkodás,
• CPU ütemezés,
• erõforrás allokáció,
• védelmi mechanizmusok.

Napjaink rendszerei:

• Multiprogramozott "kötegelt" rendszerek.
• Idõosztásos (time sharing) rendszerek:
  interaktív felhasználás, rövid válaszidõk,
  felhasználók azonosítása, állományok és könyvtárak.
• Elosztott rendszerek.
  Csoportosításuk alapja:
• szorosan csatolt (közös tárral rendelkezõ) hardware, ill. lazán csatolt rendszerek
• szimmetrikus ill. asszimmetrikus
• homogén ill. inhomogén rendszerek.
• Elosztott operációs rendszerek elônyei:
• erõforrás megosztás (resource sharing),
• terhelés megosztás (load sharing),
• megbízhatóság növekedése,
• kommunikáció.
• Valósidejû (real time) rendszerek:
  külsõ események bekövetkezésére garantált válaszidõ.

Operációs rendszerek HW támogatása

ROM program rendszer betöltéséhez.

Be- és kivitel (I/O):

• megszakítások,
• szinkron és aszinkron perifériakezelés,
• adatátvitel közvetlen tárhozzáféréssel (DMA).

Védelmi mechanizmusok:

• két módú programfuttatás (felhasználói- és rendszermód), privilegizált utasítások,TRAP utasítás a módváltáshoz,
• tár címtartományok védelme,
• óra periféria, rendszeres megszakítások.

Tároló hierarchia:

• regiszterek, központi tár, mágneslemez, optikai lemez, szalag,
• virtuális tárkezelés támogatása,
• gyorsító tárak (cache), konzisztencia és koherencia.

Az operációs rendszerek feladatai

Operációs rendszer szolgáltatások:

• programok végrehajtása, folyamatok vezérlése,
• perifáriás eszközök kezelése,
• állományok kezelése,
• kommunikáció,
• hiba detektálás,
• erôforrás foglalás,
• rendszerinformációk gyûjtése,
• védelmi mechanizmusok biztosítása.

Fontosabb rendszerkomponensek:

• folyamatok kezelése,
• központi tár kezelése,
• perifériakezelés,
• állományok kezelése,
• védelmi rendszer,
• hálózatok kezelése,
• kezelõi felület.

Rendszerhívások és végrehajtásuk.

Az operációs rendszerek felépítése

Komplex, nagyméretû szoftver. Alapvetô felépítés:

• Rétegszerkezet:
  nehéz tiszta rétegszerkezetben a funkciók egymásra építése.
• Moduláris szerkezet:
  példa: "klasszikus" UNIX szerkezet.
• Virtuális gép (virtual machine, VM):
  HW teljeskörû emulációja (védett utasítások is),
  konkrét HW erõforrások osztott kezelése,
  különbözõ operációs rendszerek akár egyidejûleg is, változtatás nélkül futtathatók.

Folyamatok

A folyamat (process)fogalma:

multiprogramozott rendszerek alapfogalma,

"életre kelt" program, kód és adatterület.

Folyamat adatterületei:

• a program kódja,
• adatterületek: inicializált (DATA) és nem inicializált (BSS),
• verem, dinamikusan növekvõ terület.

Környezet (context) fogalma:

program és végrehajtó gép állapota. Részei:

• adatterületek leírása
• vezérlési informáciôk (folyamat állapota, azonosítója, erôforrásai, ütemezési információ)
• futási, állományelérési jogok
• környezeti változók
• HW környezet (regiszterek, stb.)

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

Szálak (thread, lightweight process):

szálak környezete részben közös, közös erõforráshasználat, gyors környezetváltás

folyamatol ill. szálak használatának elõnyei, hátrányai.

Párhuzamos folyamatok viszonya:

• független folyamatok
• együttmûködô folyamatok

Megszakítások kezelése:

megszakítás kiszolgálásainak lépései.

Alapvetõ módszerek:

• kiszolgáló rutin (nincs környezetváltás),
• kiszolgáló folyamat (mindig környezetváltás),
• köztes megoldás, kiszolgáló rutin, a várakozó folyamatok átütemezésének kezdemányezáse.

Folyamatok állapota, állapotátmeneti diagramm:

alap állapotok: fut és várakozik,

futásra kész állapot: kvázipárhuzamos végrehajtás,

felfüggesztett állapotok, jelentõségük,

állapotátmenetek, környezetváltás helye az állapotátmeneti diagrammban,

preemptív és nem preemtív operációs rendszerek.

Folyamatok a UNIX operációs rendszerben

• Folyamat (process) tábla bejegyzés (állandóan elérhetô):
• mutató a u Area ra
• azonosító (PID)
• állapot
• szülô ill. gyerek folyamatok leírása
• ütemezési információ
• várt események leírása, signal (jelzés) kezelô információ
• általános információ a memória felhasználásról
• U Area (user area [felhasználói terület], csak futás során érhetô el)
• mutató a folyamat (process) tábla bejegyzésre
• regiszterek tartalma,
• lefoglalt memóriaterületek helye:
• a program kódja,
• adatterületek: inicializált (DATA) és nem inicializált (BSS),
• verem, dinamikusan növekvõ terület.
• kernel verem,
• rendszerhívások visszatérési kódja, hibakódok
• részletes információ a memória felhasználásról, virtuális tárkezelés információió
• nyitott állományok leírói.
• statisztikai információ futási paraméterekrôl.

---

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:

• hosszútávú:
  kötegelt rendszerben a következõ elindítandó program kiválasztása,
• középtávú:
  felfüggesztendõ és újra aktiválandó folyamatok kiválasztása,
• rövidtávú:
  a futásra kész folyamatok közül a küvetkezõ futó kiválasztása, esetleg a futó folyamat megszakítása.

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

CPU és I/O löket fogalma,

CPU löket eloszlása,

I/O löketidõt más folyamatok kihasználhatják.

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

nem preemtív: befejezõdik, fut -> vár; (csak önkéntesen mondhat le a futási jogról)

preemptív: fut -> futásra kész (nem önként), vár -> futásra kész.

összehasonlításukra lehetõséget adó paraméterek:

• CPU kihasználtság (CPU utilization),
• átbocsájtó képesség (throughput),
• körülfordulási idõ (turnaround time),
• várakozási idõ (waiting time),
• válaszidõ (response time)

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

• valamelyik fenti paraméter szempontjából optimális;
• korrekt: minden folyamatot azonos módon kezeljen,
• biztosítson prioritásokat,
• kerülje a kiéheztetést,
• legyen megjósolható viselkedésû, minimalizálja a paraméterek szórását,
• részesítse elõnyben a kihasználatlan erõforrásokat igénylõ folyamatokat,
• részesítsen elõnyben fontos erõforrásokat használó folyamatokat,
• növeklõ terhelés hatására a rendszer teljesítõképessége fokozatosan csökkenjen (graceful degradation), ne omoljon össze.

Egyszerû ütemezési algoritmusok:

• legrégebben várakozó (First Come, First Served, FCFS)
  nem preemptív,
  nagy átlagos várakozási idõ (konvoj hatás).
• körbeforgó (Round Robin) preemptív algoritmus, idõosztásos rendszerek alapja,
  idõszelet megválasztásának fontossága, kb. 80%-a az átlagos CPU löketidõnek.

Prioritásos ütemezési algoritmusok:

• belsõ vagy külsõ prioritás,
• statikus vagy dinamikus prioritás,

lehet preemptív és nem preemptív

kiéheztetés (starvation, indefinit postponement) veszélye: öregítés (aging).

CPU löketidõt figyelembe vevõ algoritmusok:

(átlagos) löketidõ "bevallása",

löketidõ becslése (exponenciális) átlagolással.

• legrövidebb löketidejû (Shortest Job First, SJF)
  optimális átlagos várakozási idõ (körbefordulási idô), nincs konvojhatás.

---

5. elõadás ( 1997. október 15. szerda)

• legrövidebb hátralévû löketidejû (Shortest Remaining Time First, )
  SJF preemptív változata, döntés, ha új futásra kész folyamat van.
• legjobb válaszarány (Highest Response Ratio, HRR)
  prioritás módosítása a várakozási idõvel (öregítés).

Többszintû ütemezési algoritmusok:

• Statikus többszintû sorok (Static Multilevel Queues),
• Dinamikus többszintû sorok (Dynamic Multilevel Queues),
• Visszacsatolt többszintû sorok (Multilevel Feedback Queues),

Többprocesszoros ütemezés:

feltétel: szorosan csatolt homogén rendszer

közös várakozási sor

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

Ütemezési algoritmusok hatékonyságának meghatározása:

• analitikus kiértékelés:
• determinisztikus modellezés
• sztochasztikus modellezés
• szimuláció: mérés modellezett környezetben
• implementáció: mérés valós környezetben

CPU ütemezés a UNIX-ban

Implementációnként vannak különbségek, itt a

Elve:

idõosztásos ütemezés,

többszintû visszacsatolásos várakozási sorok,

az egyes sorokban körforgó FCFS.

Prioritás osztályok:

Kernel és felhasználói prioritási osztályok, eltérô prioritás meghatározás a két osztályban

a nagyobb prioritáshoz kisebb belsõ kód tartozik (pl. O..127),

a kernel módu prioritási sorok (pl. O..49) mindig megelõzik a felhasználói móduakat (pl. 5O..127).

Prioritás meghatározásához használt paraméterek:

p_nice: "nice" érték, felhasználó eszköze a prioritás csökkentésére

p_cpu: a futó folyamat CPU felhsználása

p_pri: az aktuálisan érvényes prioritás

p_usrpri: felhasználói módban érvényes prioritás

• kernel módú prioritások:
  nem preemptín kernel,
  a prioritás a várt esemény lekezelésének ill. az éppen megszerzett erõforrás "fontossága" alapján kerül meghatározásra
• felhasználói módú prioritások:
  a felhasználói futó illetve a preempted állapotban lévõ folyamatok prioritása,
  a "közelmúlt" CPU felhasználásától függ,
• Futó folyamatnál
  p_usrpri = PUSER + p_cpu + 2 * p_nice
• Nem futó folyamatnál
  p_usrpri = PUSER + ( p_usrpri - PUSER ) / 2

Ütemezési funkciôk az óra IT ben hajtôdnak végre. Csökkenô gyakorisággal a funkciók:

• p_cpu frissítése (pl. minden IT-nél)
• Futó folyamat prioritásmeghatározása (pl. minden 4. IT )
• Körbeforgó ütemezô (pl. minden 1O. IT)
• Nem futó folyamat prioritásmeghatározása (pl. minden 1OO. IT )

Átütemezés:

• éppen felhasználói folyamat fut és új futásra kész folyamat van, amelyik prioritása nagyobb, mint az éppen futóé (prioritás újraszámolása vagy várt esemény bekövetkezése miatt)
• ha lejárt az éppen futó felhasználói folyamat idõszelete, és van más hasonló prioritási osztályba tartozo folyamat (körbeforgó ütemezés)
• ha a futó folyamat várni kényszerül vagy kilép

Ütemezés adminisztrálása: (gyors kiértékelés támogatása)

hash tábla, láncolt sorok, külön jelzôbitek

Óra megszakítás a UNIX-ban

• ütemezéshez prioritások számítása, idõszelet végén átütemezés;
• bekapcsolás óta eltelt idõ, "pontos idõ"mérése;
• kernel algoritmusokhoz szükséges idõzítések kezelése (callout mechanizmus):
  esedékessé váló tevékenység indítása szoftver megszakítással;
• periódikusan futtatandó folyamatok ébresztése;
• felhasználóknak "ébresztõóra" szolgáltatás:
  alarm rendszerhívás és SIGALARM jelzés;
• folyamatonkénti futási statisztikák készítése:
  kernel, felhasználói módban, ill. várakozással töltött idõ
  a folyamatnál összesítik a terminált gyerekek statisztikáit.

Ébresztés (alarm) kérése

• valós idô alapján
• folyamat kezdete óta eltelt idô alapján
• felhasználói módban CPU használattal eltöltött idô alapján

Folyamatokból álló rendszerek

Folyamatok viszonya:

• független folyamatok:
  egymás futását semmilyen módon nem befolyásolják,
  aszinkron futnak, egymáshoz viszonyított sebességükrõl nincs információ.
• csatolt folyamatok:
  
• versengõ folyamatok:
  logikailag függetlenek, de közös erõforrásokat használnak.
• együttmûködõ folyamatok:
  közös cél végrehajtásán munkálkodnak.

Motiváció:

• erõforrás megosztás az erôforrások jobb kihasználása érdekében,
• gyorsabb feladatmegoldás (több CPU esetén),
• feladat particionálásának (kisebb, egymáshoz viszonylag lazán kapcsolódó részekre osztásának) módja.

Alapfogalmak:

• folyamatok;
• szinkronizáció: folyamatok futásának idõbeli összehangolása
  elsôsorban szorosan csatolt rendszerekben használt;
• komunikáció: információcsere a folyamatok között
  elsôsorban lazán csatolt rendszerekben használt.
• holtpont
• éheztetés

A szinkronizáció formái:

• elõidejûség (precedencia):
  az egyik folyamat adott utasításának mindig meg kell elõznie egy másik folyamat megfelelõ utasítását, a második folymamat bevárja az elsõt.
• egyidejûség (randevú):
  "azonos idõben" hajtódnak végre, vagy 1 processzoros rendszer esetén egyik utasítás sem kezdõdhet el, amíg a másik folyamat egyidejûleg végrehajtadó utasítását megelõzõ összes utasítás végre nem hajtódott;

• gyakran elõfordul az ún. meghosszabbított (extended) randevú, amikor az egymást bevárt 2 folyamat közül az egyik (ügyfél, client)) csak akkor mehet tovább, ha a másik (kiszolgáló, server) befejezett egy bizonyos tevékenységet.
• kölcsönös kizárás (mutual exclusion):
  a két utasítás sorrendje közömbös, az egyedüli követelmény, hogy azok ne egyidejûleg hajtódjanak végre.
  A kölcsönös kizárás a leggyakrabban használt szinkronizációs eszköz. Szükségességes olyan erõforrás (hardver vagy szoftver) használata esetén, amelyet egyidejûleg csak egy folyamat használhat, különben hibásan mûködik, ill. egyes esetekben lehet egy magasszintû utasítássorozaton belül is követelmény a kölcsönös kizárás.

Motiváló gyakorlati példa

Termelô

[Keszít egy új kinyomtatandó adatot a következôKész változóban.]

while számláló >= n do NOP;
buffer[beszúrandó]:= következôKész;
beszúrandó:= (beszúrandó + 1) mod n;
számláló := számláló + 1;

Fogyasztó

while számláló <= 0 do NOP;
következôKimenô := buffer[kimenô];
kimenô := (kimenô + 1) mod n;
számláló := számláló - 1;
[Kinyomtatja a következôKimenô változóban tárolt adatot.]

Probléma

A számláló 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.

Folyamatok szinkronizációja

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:

• biztosítsa a kölcsönös kizárást:
  a kritikus szakaszban (az egymáshoz tartozó kritikus szakaszokban) mindig legfeljebb egyetlen folyamat tartózkodhat.
• halad:
  ha a kritikus szakasz szabad és van, aki be akar lépni, ezek közül egyet beenged.
• korlátozott várakozás:
  elkerüli a várakozó folyamatok kiéheztetését.

A kritikus szakasz implementálása

Tisztán programozott megoldások

Két folyamat esetén:

A két folyamat P(1) ill. P(2).

A P(i) folyamathoz tartozó belépô (entry) és kilépô (exit)szakaszok:

entry:

flag [i] := IGAZ;

következô := j;

while ( flag[j] 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. Példa a jegyzetben található.

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 (key == HAMIS);
exit:
lakat:= HAMIS;

• szemaforok:
  speciális adatszerkezet és rajta értelmezett oszthatatlan utasítások;
  
• mûveletek jelentése:

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

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

V(s):
   s := s + 1

• bináris szemaforok: csak 0 vagy 1 (true és false) érték;
• kritikus szakasz megvalósítása:

       init(s, 1)
entry: P(s)
exit:  V(s)

• univerzális eszköz, a többi szinkronizálás is megvalósítható;
  Pl. elôidejûség
  
init(s, O)
Folyamat(1):
Utasítás(1)
V(s)
Folyamat(2):
P(s)
Utasítás(2)
• a folyamatok állapotátmeneti diagrammja és a szemafor implementáció:

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á, 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;

korrekt megoldás, a szemafort nem lehet a felébresztett folyamattól ellopni.

• problémája: túl alacsonyszintû eszköz.

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

• 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:
• az azonos erõforráshoz tartozó kritikus szakaszok a program szövegben szétszórtan fordulnak elõ,
• az erõforrásra várakozó össze folyamatot fel kell ébreszteni, mert a kernel nem tudja kiértékelni a belépési feltételeket.

• 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
• megosztott változók,
• elérési pontok (eljárások),
• inicializáló utasítások,
• várakozó folyamatok listája
• 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: feltételes változó (conditional variable):
  bináris szemaforhoz hasonló adattípus, két speciális belépési ponttal:
• wait mindig blokkol, elhagyja a monitort;
• signal csak akkor van hatása, ha várakozik valaki;
• problémája: a feltételes változók újra alacsonyszintû eszközt jelentenek.

Folyamatok közötti információcsere

Információcsere formái:

• közös tárterületen keresztül
  szinkronizáció, kölcsönös kizárás biztosítása szükséges
• kommunikációs csatornán keresztül üzenetváltás a csatornán
  mechanizmus küldô SEND(üzenet), vevô RECIEVE(üzenet)

Üzenet hossza

• változó
• állandó

Csatorna jellemzôi

• átviteli közeg
• kapcsolat iránya (egyirányú, kétitányú, szimetrikus, aszimetrikus)
• csatornát használô folyamatok száma (kettô v. több)
• csatorna kapacitása (bufferelés, explicit automatikus)
• csatorna megbízhatósága

Folyamatok megnevezése

• Közvetlen kommunikácó
• SEND(címzett, üzenet)
• RECIEVE(küldô, üzenet)
• Közvetett kommunikácó
  Postaláda használat
• SEND(postaláda, üzenet)
• RECIEVE(postaláda, üzenet)

Üzenetek tárolása a csatornán

• Nincs tárolás
  szinkronizáció (randevú) szükséges
• Véges tárolás
  kölcsönös kizárás, ill. várakoztatás szükséges
• Végtelen tárolás
  virtuális lehetôség, nincs várakozás

Hibakezelés

Kezelendô események

• Adó meghal
• Vevô meghal
• Felismerés lehetséges módja
  Idôkorlát (timeout) használata
• Üzenetvesztés, sérülés
• OR jelzi és kezeli
• OR jelzi, felhasználó kezeli
• Felhasználó veszi észre

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

• Hiba detektálása
• Hiba javítása

Holtpont kezelés

A holtpont (deadlock)

• fogalma: több folyamat olyan eseményre, erõforrás felszabadulására vár, emelyet másik, ugyancsak várakozó folyamat tud elõidézni,
• a kiéheztetés és a holtpont különbsége.

Az erõforrások modellje:

• véges számú erõforrás,
• erõforrás osztályok,
• elvehetõ (preemptable) és nem elvehetõ (non-preemptable) erõforrások,
• erõforrás használat lépései:
• igénylés, ha az igény nem teljesíthetõ, a folyamat várakozik,
• az erõforrás kizárólagos használata,
• az erõforrás felszabadítása, valamelyik várakozó továbbengedése.
• a rendszer állapota leírható az erõforrás-használati gráffal (resource allocation graph)

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ételei:

a fenti 4 szükséges feltétel, valamint

minden erõforrás osztályban csak egyetlen erõforrás van.

Holtpont kezelési stratégiák:

• erõforrás használati szabályokkal biztosítani, hogy holtpont ne alakuljon ki:
• holtpont megelõzés (deadlock prevention),
• holtpont elkerülés (deadlock avoidance).
• csak a holtpont kialakulásánál avatkozunk be:
• holtpont felismerés (deadlock recognition),
• holtpont felszámolása (deadlock recovery).

A holtpont megelõzése:

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

1. kölcsönös kizárással nem lehet mit tenni,
2. foglalva várakozás ellen: csak akkor kérhet új erõforrást, ha nem tart lefoglalva másikat,
• futás elején lefoglalja az erôforrásokat
• erôforrásfoglalás elôtt a foglalt erôforrások felszabadítása
3. nem elvehetõ erõforrások: erõforrások elvétele egyes folyamatoktól,
4. körkörös várakozás ellen: beszámozott erõforrások, csak sorrendben igényelhetõk.

---

8. elõadás ( 1997. november 5. szerda)

A holtpont elkerülése:

• erõforrások óvatos allokálásával kerülhetõ el a holtpont kialakulása;
• a folyamatok erõforrás-igényérõl kiegészítõ információval kell rendelkezni:
• ismert a folyamatok erõforrás-osztályonkénti maximális igénye,
• a folyamat igényének kielégítése után véges idõn belül visszaadja az összes erõforrást;
• az erõforrás igényt csak akkor teljesítjük, ha az így kialakult rendszer biztonságos állapotban marad.
• biztonságos állapot, ha található olyan folyamat-sorrend, hogy az egyes folyamatok maximális igénye is kielégíthetõ.
• megvalósítása: bankár algoritmus.

A holtpont felismerése:

• az erõforrás-használati gráf alapján,
• gráf redukciós algoritmus:
• olyan folyamat kiválasztása, amelynek a jelenlegi igényei a szabad erõforrásokkal kielégíthetõ,
• a folyamat által lefoglalt erõforrásokat visszaadjuk (optimista algoritmus),
• újra keresünk kielégíthetõ folyamatot, ha nincs ilyen, de maradtak kielégítetlen folyamatok, akkor holtpont van.
• az algoritmus viszonylag lassú, mikor futtassuk:
• minden erõforrás igény teljesítésekor,
• idõnként.

A holtpont felszámolása:

• folyamatok megszûntetésével:
• minden holtpontban lévõ folyamatot megszûntetünk,
• csak bizonyosakat, kiválasztáshoz paraméterek pl.:
• hány holtpont hurokban szerepel,
• mekkora a prioritása,
• mennyi ideje fut (várhatóan mennyi ideig futna még),
• milyen erõforrásokat tart lefoglalva,
• milyen erõforrásokat igényelne még.
• erõforrások elvételével
  probléma: melyik folyamattól és milyen erõforrásokat vegyük el.
• ellenõrzési pontok (checkpoint) és visszállítás (rollback) fontossága.

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.:

• belsõ rendszer-erõforrások: sorrendi foglalás,
• központi tár: erõforrás elvétele,
• kötegelt rendszerekben, elõre megadott erõforrás szükséglet: holtpont elkerülés,
• tárcsere terület a háttértáron: elõzetes foglalás.

Központi tár kezelése

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

• multiprogramozás igényli, hogy egyidejûleg több folyamat tartozkodjon a központi tárban.

• címek kötése,
• tár allokáció.

• fordításkor,
• szerkesztéskor: kapcsolatszerkesztõ (linker) program,
• betöltéskor: áthelyezõ betöltõ program (relocating loader),
• futás közben:
• hardver támogatással: pl. bázisregiszter, szegmens- és lapszervezésû tárkezelõ hardver,
• pozíciófüggetlen kód (Position Independent Code, PIC)
• késleltetett betöltés:
• dinamikus betöltés (dynamic loading);
• dinamikus könyvtárak (shared library, dynamicaly loaded library, DLL):
  operációs rendszer támogatás, közös könyvtárak, betöltés név és verzió alapján;
• egymást átfedõ programrészletek (overlay).

Társzervezési elvek:

• egy partíciós rendszerek:
• operációs rendszer és egyetlen alkalmazói folyamat,
• operációs rendszer védelme határregiszterrel,
• probléma: operációs rendszer terület növekedése;
• több partíciós rendszerek, fix- és változó méretû partíciók:
• operációs rendszer és a többi folyamat védelme partíciónként alsó és felsõ határregiszterrel,
• fix partíciók: belsõ tördelõdés (internal fragmentation),
• változó partíciók: külsõ tördelõdés (external fragmentation).
• tárallokációs stratégiák változó méretû partícióknál:
• elsõ illeszkedõ (first fit),
• következõ illeszkedõ (next fit),
• legjobban illeszkedõ (best fit),
• legrosszabban illeszkedõ (worst fit),

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.

---

9. elõadás ( 1997. november 12. szerda)

• Tárcsere (swap)
• (középtávú) ütemezés: kevés szabad központi tár esetén folyamatok felfüggesztése,
• folyamat teljes tárterületének háttértárra mentése és visszaállítása,
• felfüggesztendõ és újra aktiválandó folyamatok kiválasztásának kritériuma.

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

• Állandó blokkméret: lapszervezés
• Változó blokkméret: szegmensszervezés
• Kombinált szegmens és lapszervezés

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

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

Háttértár tulajdonságai:
• kedvezô ár/kapacitás arány
• nagy tárolókapacitás
• állandó (passzív) tárolás
Háttértár típusok:
• mágnes szalag
• mágnes dob
• merev ill. floppy lemez
• CD-ROM
• EEPROM kártya....

A lemezek fizikai szerkezete
• alapfogalmak:
• cilinder (i),
• felület (j)
• sáv,
• szektor (k).
• szektor címzés: b = S* (i * T+ j) + k
  (T=szektor/sáv, T=sáv/cilinder)
• kiszolgálási idõ felbontása:
• fejmozgási idõ (seek time),
• elfordulási idõ (rotation latency time),
• átviteli idõ (transfer time).

Lemezmûveletek ütemezése: (fejmozgásra koncentráló algoritmusok)

• algoritmusok értékelésének paraméterei:
• átbocsájtó képesség,
• átlagos válaszidõ,
• válaszidõ szórása.
• ütemezési algoritmusok:
• sorrendi kiszolgálás (First Come First Served, FCFS),
• legrövidebb fejmozgási idõ (Shortest Seek Time First, SSTF),
• pásztázó (SCAN),
• N lépéses pásztázó (N-SCAN),
• Körbeforgó (egyirányú) pásztázó (Circular SCAN, C-SCAN),
• elfordulási idõ optimalizálása:
• szektor sorbarendezés

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

• lemezterület tömörítése (disk compaction),
• ütemezési algoritmusok sajátosságainak figyelembe vétele,
• információ többszörözése a lemez különbözõ területein,
• több blokk egyidejû átvitele,
• átmeneti, gyorsító tár alkalmazása,
• adattömörítés (compression).

Megbízhatóság növelésének lehetôságe:

rendszeres mentés,

redundáns tárolás,

elosztott tárolás

Állományrendszer

Alpfogalmak:

• állomány,
• könyvtár.

Állománykezelõ feladatai:

• információátvitel az állományok és a folyamatok tárterülete között,
• mûveletek állományokon és könyvtárakon.
• osztott állománykezelés vezérlése,
• állományokhoz hozzáférés szabályozása,
• tárolt információ védelme.

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

• periféria meghajtó (device driver),
• elemi átvitelek,
• fizikai állományszervezés,
• logikai állományszervezés.

Adatszerkezetek a lemezen:

• blokkok,
• kötet,
• szabad helyek nyilvántartása,
• állományokhoz tartozó blokkok nyilvántartása,
• katalógusok ábrázolása.

Szabad helyek nyilvántartása

• bittérkép,
• szabad blokkok láncolt listája,
• szabad blokkok csoportjának láncolt listája,
• egybefüggõ szabad területek leírása.

Állományokhoz tartozó blokkok nyilvántartása

• egyetlen egybefüggõ terület,
• láncolt lista,
• lácolt list központi láncelem-táblával (File Allocation Table, FAT),
• indexelt tárolás,
• többszintû indexelés.

Állományok belsõ szerkezete:

• nincs szerkezet: Byte - esetleg bit - sorozat
• logikai szerkezet:
• mezõ
• rekord

Hozzáférési módok:

• soros (sequential),
• közvetlen (direct, random access),
• indexelt, index-szekvenciális (index sequential access method, ISAM),
• particionált.

Mûveletek az állományokon:

• átvitel: írás vagy olvasás,
• hozzáírás, bõvítés,
• pozicionálás,
• állomány megnyitása, lezárása,
• programállomány végrehajtása,
• állomány létrehozása,
• állomány törlése.

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

• Átviteli állapot leíró:
• soros hozzáférés pozíciója.
• aktuális jogosultságok.
• Osztott elérés támogatása:
• használók száma,
• kölcsönös kizárás támogató adatszerkezet
• várakozók listája.

Könytárak:

• nyilvántartás bejegyzés:
• az állomány neve;
• az állomány fizikai elhelyezkedését leíró információk:
• hossza,
• hozzá tartozó háttértár blokkok leírása,
• a hozzáférés módja;
• az állománykezeléssel kapcsolatos logikai információk:
• típusa (ha van ilyen),
• tulajdonosának, létrehozójának azonosítója,
• különbözõ idõpontok,
• hozzáférés jogosultágok,
• hivatkozás számláló.
• mûveletek a könyvtárakon
• állomány attribútumainak módosítása,
• könyvtár létrehozása, törlése,
• keresés a könyvtárban,
• új bejegyzés létrehozása, törlése.

---

11. elõadás ( 1997. november 26. szerda)

Könyvtárak hierarchiája:

• alapfogalmak:
• aktuális könyvtár (current directory),
• gyökér könyvtár (root directory),
• elérési út (path),
• keresési út (search path).
• kétszintû könyvtárak,
• körmentes irányított gráf,
• általános gráf.

Osztott állománykezelés:

• a teljes állományra vonatkozó szabályozás (megnyitásnál):
• kizárólagos használat,
• több egyidejû olvasás,
• több egyidejû írás;
• (változások érvényrejutása (consistency semantics) )
• az állomány részeire vonatkozó kizárás,
• (kötelezõ (mandatory) vagy ajánlott (advisory) zárak.)

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

• állomány létrehozója, tulajdonosa definiálhatja;
• tipikus jogosultságok: olvasás, írás, hozzáírás, végrehajtás, törlés;
• jogosultságok állományokra, könyvtárakra
• jogosultságok engedélyezése: felhasználónként, felhasználói csoportonként, alapértelmezés (bárki).

Unix file rendszer

A file rendszer a UNIX viszonylag állandó része. A 8O-as évekig jórészt változatlan. (System V - s5fs) Utána az elosztott file-kezelés támogatására különbözô megoldások:

• Network File System
• Remote File System
• Andrew File System

Felhasználói felület:

• file
• directory
• file descriptor
• file system

Lényeges tulajdonságok:

• Azonos típusú adat file-ok
• File elérés:
• soros (alapértelmezésben)
• párhuzamos (pozícionálással)
• Transzparens file kezelés
• Könyvtárak körmentes gráf szerkezete (fa gráf link-ekkel)
• Homogén file név, bármilyen karaktersorozat (NULL ill. / kivételével)
• File azonosítás: ÚT/FILE-NÉV
• Aktuális könyvtár a folyamat környezetének része, abszolút és relatív út használata

File típusok:

• közönséges adat file
• directory
• pipe (csatorna)
• speciális file (perifériás eszköz)
• szimbolikus link (könyvtári bejegyzés)

File rendszer belsô leírása (adatszerkezetek):

• directory
• i-node
• super block
• lemezen tárolt adatok helye, belsô struktúrája

Szabad adat blokkok nyilvántartása:

• szabad blokkok láncolt listája.

Szabad i-node-ok nyilvántartása, adatszerkezetek frissítése.

Linkek:

• Szoros (hard) link
• Szimbolikus link

Filekezelô parancsok:

• cd, ls, cp, mv, mkdir, rm, rmdir, ln, utimes, chown, chmod

Rendszerhívások:

• file-descriptor open(út/file-név, nyitási-mód, létrehozási-mód)
• close(file-descriptor)
• seek(file-descriptor, eltolás, referencia-szám)
• referencia-szám:
• O - file elejérôl
• 1- aktuális pozíciótól
• 2- file végérôl

Nyitott file-ok adminisztrálása:

• Adatszerkezetek:
• folyamatonkénti file leíró (Per Process User File Descriptor Table)
• nyitott állományok leírója (System File Descriptor Table)
• kernel-beli i-node táblázat

File lezárása: lock

File rendszerek összekapcsolása: mount

Logikai lemezek fogalma, használata.

Csatorna (pipe):

• elnevezett csatorna (named pipe)
• név alapján mindenki számára elérhetô (open() )
• explicit törléssel szûnik meg
• év nélküli csatorna (unnamed pipe)
• csak a létrehozó folyamat utódai ismerik (pipe() )
• utolsó hivatkozás megszûnése után automatikusan megszûnik
• mûködés:
• korlátos FIFO (< 1O adat blokk)
• író ill. olvasó pointer
• adatokat egyszer lehet csak kiolvasni
• teli ill. üres csatorna esetén automatikus várakoztatás

Elosztott állományrendszerek

A hetvenes évektôl kezdôdôen az elosztott rendszerek használata egyre gyorsuló ütemben fejlôdött. Távoli fileok elérésére kidolgozott protokollok:

• Unix to Unix Copy
• File Transfer Protocol

Transzparens file elérést támogató protokollok (nyolcvanas évektôl):

• Network File System
• Remote File System
• Andrew File System

Elosztott állományrendszerek általános jellemzôi

Kliens szerver modell használata: A szerver szolgáltatást nyújt a kliens gépen futó felhasználói folyamatnak.

Fontos a következô három fogalom megkülönböztetése:

• Elosztott file rendszer
• Elosztott operációs rendszer
• Hálózati operációs rendszer

Jellemzô tulajdonságok:

• Hálózat áttetszôsége
• Elhelyezkedés áttetszôsége
• Elhelyezkedés független file elérés
• Felhasználó mobilitósa
• Hibatûrés
• Skálázhtóság
• File ok mobilitása

Tervezési szempontok:

• File nevek állapt tere
• uniform
• nem uniform
• Állapt mentes és állapot tárolós mûködés
• File ok osztott elérésének megvalósítása
• Távoli szolgáltatás módja

SUN Network File System

1985 ben.publikálták a

• a szabadon elérhetó protokollt és
• referencia implementációkat.

Azóta de facto szabvánt lett.

Jellemzô tulajdonságok, mûködés:

• Kliens szerver modell
• Szétválasztható kliens és szerver
• Szinkron távoli eljáráshívás

Felhasználói felület lehetôségei:

• Egy vagy több fiile rendszer teljes vagy részleges (rész fa) exportálása,
• Konfigurációs file az exportált filerendszert elérô kliensek számára
• Távoli filerendszer mount olásának lehetôsége az elérési jogosultságok definiálásával
• HARD (szoros) ill. SOFT (laza) mountolás
• A lokális file okkal azonos elérés
• A szerver csak a saját lokális file rendszerét exportálhatja.

NFS tervezési célok:

• Minden OR alatt lehetséges legyen megvalósítani
• Protokoll HW függetlensége
• Egyszrûújraélesztési lehetôség a kliens ill. a szerver számára
• Kliens kezelje az OR függô file elérési metodikát
• NFS teljesótménye a helyi file rendszer teljesítményével összemérhetô legyen
• A hálózati összeköttetéstôl független ill. a forgalomnövekedéssel bôvóthetô kapacitású implementációt tegyen lehetôvé

Az NFS specifikáció következménye az állapotmentes megvalósítás.

• Elônyei:
• Kérések függetlenek egymástól.
• Kliens állapota a szerverben nem tárolt, csak statisztikai információt gyûjthet a szerver.
• Egyszerû kliens, ill. szerver recovery
• Hátrányai:
• A szerver csak stabil állapotban válaszolhat (pl. cache mentés után), ami idôkésleltetést okoz
• File LOCK hoz külön SW erôforrés kell.

NFS részei:

• NFS protokoll
• RPC (Remote Procedure Call) protokoll
• XDR (EXtended Data Representation) protokoll
• NFS szerver és kliens mûködést megvalósító SW komponensek
• Mount protokoll
• daemon folyamatok
• Network Lock Manager
  Network Status Manager

XDR (EXtended Data Representation) protokoll:

Szabályrendszer különbözô típusú adatok HW független ábrázolásának, ill. továbbításának módjára.

Rögzíti az adatelemek:

• méretét,
• sorrendjét,
• formátumát.

Definiál alapadatípusokat és szabályrendszert (formális nyelvet) ad kombinált típusok definiálására.

RPC (Remote Procedure Call) protokoll:

A kliens és a szerver kommunikációjának formai defininíciója:

• üzenetek formátumának
• üzenetközvetítés és
• partnerazonosítás módjának rögzítése.

SUN RPC jellemzôi:

• Szinkron mûveletvégzés
• Megbízható üzenettovábbítás
• Üzenetek számontartása, válasz hiánya esetén automatikus ismétlés

SUN RPC üzenet (kérés ill. válasz) formátuma.

NFS megvalósítása UNIX rendszerben

• mutatók file rendszer függô adatokra :
• file leíró
• file rendszer specifikus eljárások leírása
• mutatók > virtuális< eljárásokra (hagyományos file kezelô eljárásoknak megfelelô rutinok)
• mutatók >utility< eljárásokra a kernel számára

• Unix file rendszer esetén: i node
• NFS esetén: file rendszer azonosító + i node + i node generálási szám

Operációs rendszerek kezelôi felülete

• parancs bevitel, értelmezás
• parancs végrehajtás
• eredmények ill. esetleges hibák közlése, megjelenítése

• belsô
• tárolt (külsô):
• rendszer
• felhasználói

• Nem interaktív
• Job Control Card
• Interaktív
• teletype, keyboard
• display
• grafikus terminál
• egér
• fényceruza
• touch screen
• beszedfelismerésen ill. szintézisen alapuló kommunikáció ...

• kevés és egyszerû parancs
• biztonságos parancsok
• részletes, környezetfüggô help

• hatékony, minden lehetôséget kihasználó parancsok
• konfigurálható parancsok
• bôvíthetô parancs készlet

X window rendszer

• Kliens szerver modell használata:
• Kliens
• Grafikus ki és bemeneti lehetôséget biztosít a kliensnek
  Kezeli a grafikus munkahelyet, mely részei:
• képernyô(k)
• billentyûzet
• grafikus beviteli eszköz
• Szerver
• Grafikus kimenetû (interaktív) folyamat

X protokoll

• Magasszintû, kétirányú

• Aszinkron kommunikáció
  Üzenetek típusai:
• Kérés (kliens -> szerver)
• Válasz (szerver -> kliens )
• Esemény (szerver -> kliens )
• Hiba (szerver -> kliens )
  
• Törekszik álózati kommunikáció csökkentésére:
• Kliens üzeneteit összegyûjtve küldi
• Szerver helyben kezel bizonyos eseményeket
• A szerver SW erôforrásokat (grafikus környezetet, betûtípushoz tartozó leírást stb.) hoz létre a kliensben, amiket késôbb hivatkozással ér el.

Az X koncepciója

• X display:
• X screen (megjelenítô)(egy vagy több)
• Ki- és bemeneti eszközök
• 1 billentyûzet
• 1 pozicionáló eszköz

Ablakkezelés

Ablak: Téglalap alakú képernyôrészlet.

Hierarchikus ablak rendszer.

Automatikus vágás átlapolódó, egymást fedô ablakoknál. Kitakaráskor eseményküldés, ablakfrissítés támogatása.

Megjelenítô eszköz

Ki és bemeneti eszközök kezelése

A bemeneti eszközök állapotváltozásakor a szerver esemény üzenettel értesíti a klienst.

Input focus:
Input focus birtokosa az a kitüntetett kliens folyamat, amelyik a bemeneti eszközök állapotváltozásakor értesítendô.

Pozicionáló eszköznél a kliens relatív koordinátákat kap.

Karakteres input esetén a karakter hozzárendelést a szerver végzi.

A kezelôi felület elemei

• Windowing system:
  Az X protokollt megvalósító SW
• Window manager:
  Kitûntetett kliens folyamat, ami az ablakok felhasználó által történô manipulálását intézi.
  Minden windowing system-hez csak egy window manager kapcsolódhat.
  Támogatott mûveletek az ablakokkal:
• mozgatás
• méretezés
• zárás
• ikonizálás
• menü
• Session manager:
  Állandóan futó szerver esetén a felhasználó beléptetését intézi.

Az X programozás alapjai

• Bemeneti eszközok állapotváltozása (felhasználó biztosította bemenet)
• Ablakok mozgatása a képernyôn (kitakarás)
• Hibák

• kliens kezeli (alapértelmezés)
• szerver kezeli

Összefoglalás