Operációs Rendszerek

1. 1998. február 6. péntek
2. 1998. február 13. péntek
3. 1998. február 20. péntek
4. 1998. február 27. péntek
5. 1998. március 6. péntek
6. 1998. március 13. péntek
7. 1998. március 20. péntek
8. 1998. március 27. péntek
9. 1998. április 3. péntek
10. 1998. április 10. péntek (2 elôadás)
11. 1998. április 24. péntek (2 elôadás)

• Az operációs rendszerekrôl általában
• Folyamatok
• CPU ütemezés
• Folyamatokból álló rendszerek
• Folyamatok szinkronizációja
• Folyamatok közötti információcsere
• Holtpont
• Központi tár kezelése
• Háttértár kezelés
• Állományrendszerek
• Elosztott operaciós rendszerek
• Elosztott állományrendszerek
• SUN Network File System
• Operációs rendszerek kezelôi felülete
• X Window System

Bevezetés

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.

---

3. elõadás ( 1998. február 20. péntek)

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),
• Megszakítások kezelése: megszakítás kiszolgálásainak lépései.
• 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.

Operációs rendszerek szolgáltatásai és komponensei

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:

• folyamat kezelô,
• központi tár kezelô,
• periféria kezelô,
• állomány kezelô,
• védelmi rendszer,
• hálózat kezelô,
• kezelõi felület.

---

4. elõadás ( 1998. február 27. péntek)

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.

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

---

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ázi pá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.

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.

---

6. elõadás ( 1998. március 13. péntek )

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.

• 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

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.

---

9. elõadás ( 1998. április 3. péntek )

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.

---

10. elõadás ( 1998. április 10. péntek )

• 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

---

11. elõadás ( 1998. április 24. péntek )

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

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

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.

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.

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

Elosztott operációs rendszerek

Elosztott operációs rendszerek típusai

Hálózati operációs rendszer

Távoli gépek, erôforrások elérésének biztosítása.

Elosztott operációs rendszer

Az operációs rendszer elelrejti az elosztott hardvert.

Tipikus funkciók:

• adatvándorlás
• feldolgozás vándorlás
• folyamatvándorlás

Elosztott rendszerek elônyei

• erôforrás megosztás
• megbizhatóság növelése
• terhelés megosztása
• kommunikáció lehetôsége

---

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, megbízhatóság
• 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.

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.