Ugrás a tartalomhoz

Operációs rendszerek mérnöki megközelítésben

Benyó Balázs, Fék Márk, Kiss István, Kóczy Annamária, Kondorosi Károly, Mészáros Tamás, Román Gyula, Szeberényi Imre, Sziray József

Panem Kiadó

7.3. Multiprogramozott operációs rendszerek

7.3. Multiprogramozott operációs rendszerek

1. Mi a futásra kész állapotú folyamatok közös jellemzője?

2. Miért lehet szükség egy operációs rendszer felügyelete alatt futó folyamatoknál felfüggesztett állapotra? Mondjon konkrét példát a felfüggesztés okára!

3. Sorolja fel, hogy egy operációs rendszerben a rendszerhívások végrehajtása milyen főbb lépésekben zajlik! Mi a jelentősége annak, hogy a felhasználói programok és az operációs rendszer magja a CPU különböző működési módjában fut?

4. Rajzolja fel egy „tipikus”, felfüggesztett állapotokat is használó operációs rendszerben a folyamatok állapotátmeneti diagramját az állapotok és az átmenetek elnevezésével! Mikor, milyen okok hatására következhet be a futó állapotból futásra kész állapotba átmenet?

5. Az operációs rendszerek a megszakítások kiszolgálására milyen alapvető módszereket alkalmazhatnak?

6. Ismertesse a hosszú, közép- és rövid távú ütemezés feladatát! Egy folyamat állapotátmeneti diagramján jelölje be azokat az átmeneteket, amelyek a fenti ütemezéseket jelentik!

7. Milyen szempontok alapján történhet a folyamatok hosszú távú ütemezése?

8. Ismertesse, hogy az operációs rendszer megszakítás kiszolgálása során milyen tevékenységeket hajt végre! Hogyan jelentkezik a megszakítások kiszolgálásánál a preemtív és a nem preemptív ütemezés különbözősége?

9. Mit jelent a CPU-ütemezési algoritmusok paraméterei között a CPU-kihasználtság?

10. Mi a kapcsolat a CPU-ütemezési algoritmusok jellemzésére használt körülfordulási idő (turnaround time) és várakozási idő (waiting time) között?

11. Mikor nevezünk egy ütemezőt preemptívnek?

12. Milyen paraméterek alapján lehet a különböző CPU-ütemezési algoritmusokat értékelni? Definiálja a különböző paraméterek jelentését! Hasonlítsa össze valamely fenti paraméter alapján a legrégebben várakozó (FCFS) és a legrövidebb löketidejű (SJF) algoritmusokat!

13. Ismertesse a legrövidebb löketidejű (SJF, Shortest Job First) és a legrövidebb hátralévő löketidejű (SRTF, Shortest Remaining Time First) CPU-ütemezési algoritmusokat, kiemelve a közöttük lévő lényeges különbségeket!

14. Definiálja a preemptív és a nem preemptív ütemező közötti különbséget! Rajzoljon fel egy felfüggesztett állapotokat nem tartalmazó folyamat állapotátmeneti diagramot és illusztrálja ezen is a preemptív és nem preemptív ütemezés közötti különbséget!

15. Milyen szempontok alapján lehet osztályozni a folyamatok ütemezésénél megismert visszacsatolt többszintű sorokat (Multilevel Feedback Queues)?

16. Hogyan lehet a CPU-löketidőn (burst time) alapuló ütemezési algoritmusoknál a futásra kész folyamatok következő löketidejét meghatározni?

  1. Egy operációs rendszerben a következő folyamatok találhatók futásra kész állapotban (az érkezési idő azt az időpillanatot jelenti, amikor a folyamat futásra késszé vált):

Folyamat

Érkezési idő

Löketidő

P1

0

4

P2

1

5

P3

5

3

P4

7

1

P5

9

3

Adja meg, hogy az egyes folyamatok milyen sorrendben futnak le, számolja ki a folyamatok átlagos várakozási idejét

  • sorrendi (First Come First Serve, FCFS),

  • legrövidebb löketidejű (Shortest Job First, SJF),

  • legrövidebb hátralévő löketidejű (Shortest Remaining Time First, SRTF),

  • 2 időegységnyi időszeletű körforgó (Round Robin, RR),

  • nem preemptív prioritásos ütemezés esetén.

18. Melyik ütemezési algoritmus esetén a legkisebb a válaszidő (response time) szórása?

  • Legrégebben várakozó (First Come, First Served, FCFS),

  • Körbeforgó (Round Robin, RR).

  • Legrövidebb löketidejű (Shortest Job First, SJF).

19. Mely állítások igazak a CPU-ütemezésnél használt körbeforgó (Round Robin) algoritmusra?

  • Biztosítja a legkisebb átlagos várakozási időt.

  • Használata esetén nem lép fel a folyamatok kiéheztetése.

  • Használatával lehet valósidejű operációs rendszert készíteni.

20. Mely állítások igazak a preemtív ütemező algoritmusra?

  • Mindig prioritásos ütemezési algoritmusokat használ annak eldöntésére, hogy mikor és melyik folyamatot kezdje el futtatni.

  • Alkalmazása esetén egy éppen futó folyamatot bármelyik időpillanatban megszakíthat és futásra kész állapotúvá tehet az operációs rendszer.

  • Használatával az operációs rendszer átlagos válaszideje (response time) csökkenthető.

21. Mely állítások igazak a prioritásos ütemező algoritmusokra?

  • Jobban kihasználják a CPU-t.

  • Használata holtpont kialakulásához vezethet.

  • Használata kiéheztetéshez vezethet.

22. Milyen ütemezési módszereket alkalmaznak szimmetrikus, illetve aszimmetrikus multiprocesszoros rendszerekben?

23. Definiálja a külső (external) és belső tördelődés (internal fragmentation) fogalmát! Mondjon konkrét példát mindkét jelenségre!

24. Mit jelent a pozíció-független (position independent, PIC) programrészlet?

25. Mi a kapcsolatszerkesztő (linker) program feladata?

26. Mit jelent a változó méretű partíciós rendszerekben használt algoritmusoknál a tárkihasználtság 1/3-os szabálya?

27. Mit jelent az átfedő programrészekkel (overlay) történő tárkezelés?

28. Mi a tömörítés (garbage collection) szerepe a többpartíciós társzervezésben?

29. A programfejlesztés, illetve futtatás mely fázisaiban történhet a program memóriacímeinek kötése?

30. Magyarázza el a változó méretű partíciók lefoglalásánál használt

  • legjobban megfelelő (best fit),

  • első megfelelő (first fit),

  • legrosszabban illeszkedő (worst fit)

algoritmusokat. Egy rendszerben az adott pillanatban 100 K, 600 K, 200 K, 300 K és 500 K méretű szabad területek vannak. Hogyan foglal helyet a fenti 3 algoritmus sorrendben 417 K, 212 K, 112 K és 426 K mé­re­tű par­tícióknak?

31. Ismertesse kombinált szegmens- és lapszervezést tartalmazó tárkezelő hardver esetén a logikai-fizikai címtranszformáció módját! Melyek a kombinált társzervezés előnyei?

32. Ismertesse az igény szerinti lapozáson (demand paging) alapuló virtuális tárkezelésnél a legrégebben nem használt (LRU, Least Recently Used) és az újabb esély (Second Chance) lapcsere algoritmusokat! Hogyan le­het(ne) az LRU-algoritmust implementálni? Milyen hardver támogatás szükséges az újabb esély algoritmushoz?

33. Definiálja a következő fogalmakat: vergődés (trashing), munkahalmaz (working set), térbeli és időbeli lokalitás! Hogyan lehet a folyamatok munkahalmazának méretét figyelembe venni a vergődés elkerüléséhez?

34. Milyen összefüggés van a virtuális tárkezelésnél munkahalmaz nagysága és a folyamat által okozott laphibák gyakorisága között? Hogyan lehet a laphiba gyakoriságot felhasználni a folyamatok számára allokált lapok számának meghatározásánál?

35. Ismertesse és hasonlítsa össze a virtuális tárkezelésnél használt FIFO és újabb esély (second chance) algoritmusokat! Milyen hardvertámogatást igényelnek ezek?

36. Mit nevezünk Belady-féle anomáliának?

37. Milyen részidőkből áll össze a háttértáron lévő lapokhoz való hozzáférési idő? Kis vagy nagy lapok használata esetén kapunk jobb transzferidőt?

38. Egy igény szerinti lapozást alkalmazó rendszerben 4 fizikai memórialap található és sorban a következő virtuális lapokra történik hivatkozás:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3

Számítsa ki a rendszerben bekövetkező laphibák számát a következő algoritmusok alkalmazása esetén:

  • legrégebbi lap (FIFO),

  • újabb esély (Second Chance),

  • legrégebben nem használt (Least Recently Used, LRU),

  • optimális.

A négy fizikai lap kezdetben „üres”, nem tartalmazza egyik virtuális lapot sem.

39. Mi a translation lookaside buffer és mi a szerepe a fizikai cím kiszámításánál?

40. Melyek igaz állítások?

A lapokat alkalmazó virtuális tárkezelésnél előforduló belső tördelődést csökkenteni lehet

  • az egyes lapok méretének növelésével.

  • az egyes lapok méretének csökkentésével.

  • megfelelően kiválasztott lap elhelyezési (placement) stratégia alkalmazásával.

41. Melyek igaz állítások?

A virtuális tárkezelésnél egyes lapokat ideiglenesen a tárba kell „fagyasztani” (page locking), azaz megakadályozni, hogy a lapcsere algoritmus cserére kijelölje, ha

  • azokat több folyamat is használja.

  • az adott lapokon valamelyik folyamat verme található.

  • az adott lapokra folyamatban van perifériás művelet.

42. Melyek igaz állítások?

Igény szerinti lapozást (demand paging) használó rendszerekben egy folyamat vergődik, ha

  • a folyamatnak túl kicsi a prioritása.

  • a folyamat munkahalmaza (working set) több lapból áll, mint ahány lapot a rendszer a folyamathoz rendel.

  • a folyamat munkahalmaza nagyobb, mint a rendszer generálásakor megadott konstans.

  • a folyamat futását gyakran szakítják meg nála nagyobb prioritású folyamatok.

43. Hogyan lehet egy szegmensszervezésű tárkezelő rendszerben a túlcímzés ellen védekezni?

44. Melyik állomány tárolási módszer esetén jelent gondot az állomány blokkjaihoz direkt hozzáférés megvalósítása?

  • láncolt listás,

  • indexelt,

  • FAT-ot használó.

45. Ismertesse az állományokhoz tartozó blokkok tárolásához használt láncolt listás, az ún. FAT-os (File Allocation Table) és az indextáblás módszereket! Milyen előnyös tulajdonságokkal rendelkezik a FAT-os módszer?

46. Sorolja fel, milyen módszereket ismer a lemezegységen a szabad helyek, illetve az egyes állományokhoz tartozó blokkok nyilvántartására!

47. Mit jelent az adattárolás biztonságának növelésére használt inkrementális mentés (incremental backup)?

48. Rajzolja fel egy mágneslemezes háttértár tipikus felépítését, valamint adja meg az egydimenziós blokkcímek meghatározási módját!

49. Mi a RAID (Redundant Array of Inexpensive Disks) technika lényege?

50. Egy 200 sávos (0 .. 199) mágneslemez-egységen a fej jelenleg a 143-as sáv felett áll, ezt megelőzően a 125-ös sávon szolgált ki egy átviteli kérelmet. Jelenleg a következő sávokra várakozik – a megadott érkezési sorrendben – egy-egy átviteli kérelem: 86, 147, 91, 177, 94, 150, 102, 175, 130. Adja meg, hogy a kéréseket az

  • időrendi kiszolgálás (First Come, First Served, FCFS),

  • legkisebb fejmozgás (Shortest Seek Time First, SSTF),

  • pásztázó (SCAN),

  • körkörös (Circular LOOK)

algoritmus milyen sorrendben szolgálja ki, illetve közben a fej mekkora utat (hány sávnyit) tett meg!

51. Melyik, a lemezműveletek ütemezésénél használt algoritmusnál nem lép fel kiéheztetés veszélye:

  • pásztázó (SCAN),

  • N lépéses pásztázó (N-SCAN),

  • legrövidebb fejmozgási idejű (Shortest Seek Time First).

52. Melyek igaz állítások?

A lemezműveletek ütemezésénél használt algoritmusok közül a következőnek a legkisebb az átlagos kiszolgálási idő szórása:

  • legrövidebb fejmozgási idő (Shortest Seek Time First),

  • pásztázó (SCAN),

  • egyirányú pásztázó (Circular SCAN).

53. Melyek az ún. belső, illetve külső parancsok?

54. A felhasználóknak milyen igényei lehetnek egy felhasználói felülettel szemben?