OPERÁCIÓS RENDSZEREK. A mai program. Fogalmak. Ütemezés és a Context Switch

OPERÁCIÓS RENDSZEREK Ütemezés és a Context Switch

A mai program • • • •

A CPU ütemezéshez fogalmak, alapok, stratégiák Időkiosztási algoritmusok VAX/VMS, NT, Unix időkiosztás A Context Switch implementáció

Ütemezés, © Vadász, 2008.

Ea6 2

Fogalmak • Erőforrásokat – Hozzárendelünk processzekhez (allokáció); – A használatukat időben beosztjuk (időkiosztás, scheduling); – Kapcsoljuk azokat a kiosztott időpillanatban (dipatching és switch).

• Most a processzor „üzemezésről” lesz szó • (Az egyéb erőforrás ütemezés kérdéskör a „kölcsönös kizárás’ probléma kezelésénél előjön majd …) • A CPU meglehetősen fontos (és jellegzetes) erőforrás. Érdemes ütemezését külön tárgyalni. Ütemezés, © Vadász, 2008.

Ea6 3

1

A probléma • Több processz van, mint processzor … • A processzek osztozzanak egy CPU idején. (Tegyük fel: minden processzhez rendeltek (ez az allokáció) egy CPU-t.) • Emlékezz a processz állapotokra: – ha letelt az időszelete a futó processznek, – Vagy ha maga blokkolt állapotba megy (ezzel „lemond” a CPU-ról), – akkor a futásra kész processzekből válasszunk ki egyet (ez a scheduling), és – „kapcsoljuk neki” a CPU-t (ez a dispathing és a Context Switch második fele). Ütemezés, © Vadász, 2008.

Ea6 4

Tágítjuk a problémát: ütemezési szintek • Long-term-scheduling (hosszútávú) – JOB ütemezés: JOB/taszk pool-ból melyiket válasszuk ki futásra. A multiprogramozási szintet befolyásolja.

• Medium-term-scheduling (középtávú) – suspended (futásra nem kész, partially executed, outswapped) processzek közül melyeket helyezzük futásra késszé (memória igény is érdekes)

• Short-term-scheduling (rövidtávú) – futásra kész processzek közül melyik kapja a CPU-t. – A továbbiakban ezzel foglalkozunk. (Ezzel ismét szűkítünk.) Ütemezés, © Vadász, 2008.

Ea6 5

Mit várunk el? • Pártatlanság: minden processz (taszk) korrekt módon, de nem feltétlenül egyenrangúan kapja meg a processzort • Hatékonyság: a CPU lehetőleg legnagyobb százalékban legyen kihasználva • Válaszidő (interaktív felhasználóknak): elfogadható legyen • Fordulási idő (kötegelt munkák): elfogadható legyen • Teljesítmény: időegységre eső JOB, taszk, processz feldolgozás (más, mint a CPU kihasználás!) jó legyen Látható ellentmondások! Ütemezés, © Vadász, 2008.

Ea6 6

2

Technikai alapok • Óraeszköz periodikusan megszakításokat generál • Az időt szeletekre (time slice, quantum) bonthatjuk • A CPU felhasználás idejét, a processzek életidejét stb. számon tarthatjuk • Bizonyos időnként az állapotokat kiértékelhetjük, és CPU kapcsolást valósíthatunk meg


Ea6 7

Az óraeszköz • A programozható óra 3 komponensből áll: – oszcillátor kristály: nagy pontossággal periodikusan jeleket generál (tipikusan 5 - 100MHz). – Számláló (counter): ami dekrementálja az értékét minden a kristály által generált jelre. Mikor a számláló eléri a 0 értéket, IT generálódik. – Tartó regiszter (holding register): az óra indulásakor (oneshot mode) vagy a counter 0-vá válásakor (square-wavemode) tartalma betöltődik a számlálóba, ezzel szabályozhatjuk, milyen gyakran keletkezzen IT (clock tick rate). •

Pl. egy 1MHz-es kristály (1μs-ként ad jelet), 16 bites regiszterekkel programozható 1μs-től 65535 μs-ig tartó óra ütés (clock-tick) tartományba. Ütemezés, © Vadász, 2008.

Ea6 8

Az óraeszköz IT kezelőjének feladatai • A napi idő karbantartása, • a futó processz által felhasznált CPU idő számolására, • a processz időkvantuma lejártának megállapítására, ütemező meghívására, • alarm szignál generálására (amikorra azt egy processz igényelte), • "watchdog timer"-t biztosíthat (pl. floppy kezelésnél: felpörgetés, lehet I/O; ugyanekkor indul a wd-timer, ami leállítja a pörgetést, ha nem jön újabb i/o kérés) • Segíti a profiling-ot, monitoring-ot, statisztikáz. Ütemezés, © Vadász, 2008.

Ea6 9

3

Napi idő karbantartás • Egy számláló (64 bites) a napi időt (time-of-day) nyilvántartja óra-ütésekben (clock-tick), vagy 2 számláló: sec-ben + "ütésszám a kurrens sec-ben" (32 bit a sec-nak, 16 bit tickeknek) – egy fix időhöz képest (Unix: 1970. jan 1. 12:00-tól) – a bootolási időtől (32 bit a tick-számlálónak, 32 bit a secben mért betöltési időnek). – A rendszergazda által adott dátum-idő átszámítódik clocktick-ekbe, és beíródik a számlálóba.

• Az óra kezelő (clock driver, clock IT handler) ütésenként növeli ezt a számlálót (számlálókat) Ütemezés, © Vadász, 2008.

Ea6 10

CPU idő nyilvántartás • A processzhez tartozó számláló ütésenként inkrementálódik, ha a processz futó állapotú. • Megoldható, hogy külön számláljuk a felhasználói módú és a kernel módú CPU használatot (persze, kis hibák itt lehetnek).

Az idő-szelet nyilvántartása • A quantum, time-slice nyilvántartáshoz a context switch esetén egy számlálót (akár processzenkénti számlálót) feltöltünk óra-ütésekben mért időszelet értékkel, majd ezt ütésenként dekrementáljuk. • A számláló 0-vá válása jelzi a quantum lejártát Ütemezés, © Vadász, 2008.

Ea6 11

Időzítő (alarm, watchdog-timer) • Idők lejártát ütésekben (tickek-ben) adott számlálók 0vá válása jelezheti. • Számlálók (órák) időben rendezett láncolt listáját tartjuk fel, a számlálókban a következő szignál ideje (tick-ben). • A lista elején lévő számlálót dekrementáljuk. – Pl. Kurrens idő: 4200, S1:4203, S2:4207, S3:4213 Kurrens idő

Következő szignál

4200

3

Clock header

3|S1


4|S2

6|S3

Ea6 12

4

Vissza az ütemezéshez: technikai alapok • Óraeszköz periodikusan megszakításokat generál • Az időt szeletekre (time slice, quantum) bonthatjuk • A CPU felhasználás idejét, a processzek életidejét stb. számon tarthatjuk • Bizonyos időnként az állapotokat kiértékelhetjük, és CPU kapcsolást valósíthatunk meg


Ea6 13

Döntési stratégiák • Nem beavatkozó (non-preemptive) – run-to-completion jellegű – együttműködő (kooperative)

• Szelektív beavatkozó • Beavatkozó (preemptive): akkor is elveszik a CPU-t egy processztől, ha az nem akar lemondani róla


Ea6 14

Ütemezési döntési helyzetek 1 Egy processz wait állapotátmenete. 2 Egy processz preemption állapotátmenete (pl. megszakítás bekövetkezése miatt). 3 Egy processz signal állapotátmenete. 4 Egy processz terminálódása. (4) exit

running (1) sleep/wait/request

blocked

schedule/run (2) preempt

(3) signal/assign

ready

waiting Ütemezés, © Vadász, 2008.

Ea6 15

5

Ütemezési döntési helyzetek 1 Egy processz wait állapotátmenete. 2 Egy processz preemption állapotátmenete (pl. megszakítás bekövetkezése miatt). 3 Egy processz signal állapotátmenete. 4 Egy processz terminálódása.

A processz szempontjából az 1. és 4. helyzet nem döntési helyzet. Az viszont a 2. és a 3. számú. Ha ütemezési döntések csak az 1., 4. helyzetekben lehetségesek: nem beavatkozó az ütemezés. Ütemezés, © Vadász, 2008.

Ea6 16

A leegyszerűsített forgatókönyv • A futó processz ideje lejárt (egy logikai óra, számláló lejárt, ütésére egy IT kezelő működésbe lép), vagy a futó processz blokkolt állapotba menne; • A kezelő (a sheduler) kiértékel, és kiválasztja a futásra kész processzekből a „nyertest” (ez egy prioritás számítás, optimum számítás); • Majd megtörténik a „kapcsolás” …


Ea6 17

Mi befolyásolhatja a kiválasztást? • Prioritás = fontosság. Mi befolyásolhatja? – A processzek memóriaigénye – A processzek „érkezési ideje” vagy „érkezési sorrendje” – Az eddigi CPU felhasználási idő* • Vö.: CPU lázas processzek szemben I/O lázas processzek

– A várható CPU felhasználási idő* • Vö.: Számolásigényes processzek szemben I/O igényes processzek. • Vajon lehet-e időt becsülni?

– A processz „időszerűsége”** • • • •

Vö.: interaktív processzek szemben kötegelt munkák, CPU lázas szakaszok szemben az I/O lázas szakaszok. Rendszer terhelés befolyása. Valós idejű processzek problémája kezelendő. Ütemezés, © Vadász, 2008.

Ea6 18

6

Egy kis fogalom magyarázat … • A processz életében lehetnek – CPU lázas időszakaszok (CPU burst) – I/O lázas időszakaszok (I/O burst)

• Vannak – Számolásigényes (CPU bound) processzek (hosszú CPU lázas szakaszokkal); – I/O igényes (I/O bound) processzek (rövid CPU lázas szakaszok, sok I/O lázas szakasz).


Ea6 19

Melyik ütemezési prioritása legyen magasabb? Egy processz állapotátmenetei CPU lázas időszakában

Egy processz állapotátmenetei I/O lázas időszakában

Fut

Fut

Blokkolt

Ready

Blokkolt


Ready

Ea6 20

Az ütemezési algoritmusok • Mi (milyen) a prioritásfüggvény? – Az igény-bejelentési sorrend (First Come, First Served) (Long- és Medium-term ütemezéshez) – A legkisebb igény (Shortest Job First) (Long- és Mediumterm ütemezéshez) – Valamilyen ígéret (ígéret-vezérelt időkiosztás) (Policy Driven Scheduling) – Körkörös sorrend (Round-Robin Scheduling) – Több összetevőtől függő (Többszintes prioritás-sorokon alapuló visszacsatolásos) (Multilevel Feedback Queue Scheduling) Ütemezés, © Vadász, 2008.

Ea6 21

7

First Come, First Served • A processzek készletében (Process Pool) lévő processzek a beérkezési sorrendjük szerint kapnak CPU-t. • Egyszerű a megvalósítás. • Kialakulhat a „convoy effect”: korábban érkezett CPU lázas szakaszú processz lefogja a CPU-t. (Országúton lassú jármű mögött sorban a gyorsabbak)


Ea6 22

Shortest Job First • Régi, egyszerű. • A nyomtató kiszolgálási sorokból ütemezésre még ma is használják. • Az átlagos fordulási idő a legkisebb. • CPU ütemezéshez: hogyan lehetne megmondani előre a várható időigényt? • Idősorozatokkal jellemezhető munkákhoz az aging (öregedés) algoritmus.


Ea6 23

“Aging “ algoritmus 0, 1, 2, ...,i,.. CPU lázas szakaszok ismétlődnek (nem egyforma időt igényelve). Becsülhetjük a következő idejét (Ti : tényleges, mért; Bi : becsült): Bi+1 = a * Ti + (1 - a) * Bi ; Legyen a = 1/2, ekkor

ahol 0 <= a <= 1. (a: súlyozó faktor)

Bi+1 = (Ti + Bi ) / 2

i

i +1

i+2

i+3

i+4

Ti

6

4

6

4

13

13

Bi

10

8

6

6

5

9


i+5

11

Ea6 24

8

Policy Driven Scheduling • Reális ígéret: n számú processz esetén 1/n-ed részét kapja egy processz a CPU-nak. • Mérni kell az – – – –

élet-idő-t (a rendszerben eddig eltöltött idejét), és cpu-idő-t (eddig felhasznált CPU időt), számítandó a jogosultsági-idő = élet-idő / n; prioritás = jogosultsági-idő / cpu-idő.

• Más ígéretek is lehetnek • Az ígéret-vezérelt időkiosztás speciális esete a valós idejű (Real Time) időkiosztás. Ütemezés, © Vadász, 2008.

Ea6 25

Round Robin Egyszerű, elég régi algoritmus. Időszeleteket (quantum) rendelünk a processzekhez. • A kész állapotú processzek egy soron nyilvántartottak. • Egy processz futhat, amíg a időszelete tart (ha blokkolódik, akkor addig sem fut). • Lejárt szeletű (preempted) processz a sor végére kerül. • A sor elején álló kapja a CPU-t. A listán a processzek “körben“ járnak. Ütemezés, © Vadász, 2008.

Ea6 26

Multilevel Feedback Queue Scheduling • Több ready sor van, a különböző prioritási szintekhez – Elvileg lehet minden sorhoz más-más scheduling/prioritás algoritmus • Pl. interaktív processzekhez preemptív FCFS, vagy MLFQ • Batch processzekhez SJF • Valós idejű (Real Time) processzekhez fix prioritás

– Minden sorhoz rendelhetünk időszeletet

• Kell egy módszer: mikor, mennyivel csökkentsük a prioritást • Kell egy módszer (algoritmus), mikor mennyivel növeljük a prioritást (visszacsatolás) • Preempted/blocked/signaled processz a neki megfelelő sor végére kerüljön • Kell egy módszer, melyik sorról "kapcsoljunk" • Pl. a legegyszerűbb: a legmagasabb sorról az elsőt.


Ea6 27

9

VAX VMS scheduling • • • • • •

Multilevel feedback jellegű, alkalmas real time-ra is. 32 prioritási szint. Nagyobb szám: nagyobb prioritás. 16-32: a valós idejű processzek számára. Nem dinamikus! 0-15: reguláris processzeknek, dinamikusan számítódik. A processz bázis-prioritása: minimális prioritása. Rendszerhívásokhoz rögzített prioritás növekmény. Mikor a processz futásra késszé válik, a növekmény hozzáadódik a bázis-prioritáshoz, és a megfelelő sorra kerül processz. • Scheduled processz prioritása egy szinttel csökken (határ a bázis-prioritás). Ha elveszik tőle a CPU-t, erre az új sorra kerül. • Sokáig várakozókat eggyel följebb emelik (no starvation). • A scheduler a legmagasabb prioritás sor elejéről választ. Ütemezés, © Vadász, 2008.

Ea6 28

Unix időkiosztás 0

Swapper Nem megszakítható

Kernel mód prioritástartomány

Várakozás bufferre Várakozás i-bögre Karakter I várakozás

Megszakítható

Küszöb prioritás

Diszk I/O várakozás

Karakter O várakozás Gyermek exitre várakozás U k szint U k +1 szint

User mód prioritástartomány

U k + 2 szint U k + 3 szint U k + 4 szint ... U n szint

n


Ea6 29

A Unix időkiosztása • A processzeknek user-mode vagy kernel-mode prioritásértéke lehet. Az előző dinamikus, ezek lehetnek preempted processzek. Utóbbi fix érték. Ezekre nincs preempció. • Küszöb prioritás szint elválaszt. • A user-mode prioritások (p_usrpri) dinamikusan “igazítódnak“. • A p_cpu mező a futó processznél a CPU használattal arányosan nő. • A p_cpu mezőt quantumonkként öregbítik (aging): p_cpu = p_cpu / const1; (rendszerint const1 = 2). Ütemezés, © Vadász, 2008.

Ea6 30

10

A Unix időkiosztása2 • A prioritás kiszámítódik (kisebb érték jelenti a nagyobb prioritást!): p_usrpri=PUSER+p_cpu/const2 + p_nice/const3; (Rendszerint const2=const3=2;). • A PUSER a processz bázis prioritása, külső prioritás. • A p_nice a nice() rendszerhívással (felhasználói kontrollt lehetővé tevő) beállított érték. • A p_usrpri a küszöb érték alá, egy beállított érték fölé nem mehet. Ütemezés, © Vadász, 2008.

Egy példa Egy rendszerben a PUSER=60. Ha egy processz megkapja a CPU-t és quantumában végig használja, a p_cpu növekmény legyen 60. Legyen 3 processz (A, B, C), induláskor a C p_cpu-ja 7, a másik kettőé 0. Induláskor a p_uspri C-nél 63, a másik kettőnél 60. Mindhárom processznél a p_nice érték 0 legyen. Követhetjük, hogyan változnak a prioritások, melyik processz kap CPU-t.

Quan tum

1

A processz

Ea6 31

B processz

C processz

p_uspri

p_cpu

p_uspri

p_cpu

p_uspri

p_cpu

60

0

60

0

63

7

60

0

61

1 2 ... 60 2

75

30

7 3

1 .... 30 3

67

15

60 75

30

3 60

1 2 ...

15 4

63

7

5

76

33

30 67

67

15

61 75

15 63

7

30

30 67

15

8 ...


Ea6 32

BSD 4.3 Scheduling • Quantum=0.1 sec; const2=4; const3=2; • const1 dinamikusan számítódik: – const1=(2*load+1)/(2*load); ahol – load a run queue álagos hossza az utóbbi 1 percben

• Ugyanekkor a p_cpu öregbítés nem quantumonként, hanem 1 sec-enként történik csak! • Az 1 sec-nél hosszabb ideig blokkolt processzeknél – const1 a blokkolási időtől is függ!


Ea6 33

11

NT Scheduling a fonalakra • Van standby állapot is: a legnagyobb prioritású futásra kész. A standby-t ütemezik ki. • 32 prioritási szint, 16-31: valósidejű, 0-15: normál, változó (mint a VAX/VMS-nél) • Lejárt quantumú fonál prioritás 1-gyel csökken (a bázisig). • Kész állapotba jutó fonál prioritása növekszik, a blokkolódása típusától függően • A legmagasabb kész sor első fonala standby állapotúra változik. Ha nincs ilyen, az idle fonál lesz standby. Ütemezés, © Vadász, 2008.

Ea6 34

Linux scheduling • A POSIX 1003.4-nek megfelelően több ütemezési osztály van (processzenként beállítható) – SCHED_FIFO, SCHED_RR, SCHED_OTHER

• A schedule( ) függvény hívódik – ha processz blokkolt állapotba megy, – Minden syscall és "slow" IT után, ha egy flag beállított.

• A schedule( ) függvény 3 dolgot csinál – "szokásos" teendőket (miknek az óra IT kezelőben kellene lenniük, de "hatékonyság" miatt itt vannak) – Legmagasabb prioritású processz meghatározása – Context Switch


Ea6 35

A CPU allokálás: Context Switch • A futó processz hardver kontextusát (dinamikus részét) lementjük valahová, • a kiválasztott processz kontextusát felvesszük. • Legfontosabb a programszámláló (PC, IP) lementése, felvétele. • Lementés történhet – wait (blokkolódás) állapot-átmenetnél, vagy – preemption állapot-átmenetnél is.

• A felvétel schedule átmenetet okoz.


Ea6 36

12

Hova mentsük le a dinamikus kontextust? Lehetne • a Process Table sorába (PCB-be). Hátrány: nagy lesz a tábla, a lementés/felvétel hardveresen nem támogatott. • Veremtárba. Előny: hardveres push/pop is van. • Felhasználói szintű verembe? Nem. • Közös kernel verembe? • Processzenkénti kernel verembe? • Egyes CPU-kban többszörös regiszterkészlet! • Egyes CPU-knak van védett módú processz kapcsolás gépi instrukciójuk! Ütemezés, © Vadász, 2008.

Ea6 37

Unix processz kontextus komponensek A kontextus statikus része

A kontextus dinamikus (volatile)része

Felhasználói szintű kontextus •Program szöveg •Adatok •Veremtár •Osztott adatok Rendszer szintű kontextus statikus része •Process Table bejegyzése •U Area •Processzenkénti Region Table

Keret a 3. rétegnek Keret a 2. rétegnek Keret az 1. rétegnek Felhasználói szint


Ea6 38

Egy lehetséges mechanizmus • Lásd a Unix processz kontextus ábrát (előző dia): keretek a processz kernel veremben a dinamikus kontextus részére. • Hány keret kell? Mikor keletkezik új réteg? – rendszerhívással (trap) belépünk a kernelbe; – megszakítással belépünk a kernelbe; – preemption következett be.

• Megszűnik egy réteg, ha – rendszerhívásból visszatérünk user szintre; – megszakítás kiszolgálásból vissztérünk; – schedule átment következett be. Ütemezés, © Vadász, 2008.

Ea6 39

13

A kapcsolás lépései • Döntés, legyen Context Switch. • A save-context() algoritmussal a kurrens processz dinamikus kontextusának lementése; • A “legjobb“ processz kiválasztása (scheduling algoritmusok!) • A resume-context() algoritmussal a kiválasztott processz kontextusának felvétele. Tételezzük fel: R0 regiszterben van a függvények visszatérési értéke, PC a programszámláló, PSW a státus regiszter. Ezekre van hardveres push/pop.


Ea6 40

Pszeudókódok1 int save_context() { R0 ← 0; SWIT { HW-PUSH(PC,PSW); PUSH (altalanos regiszterek); /* lementődött a keret, R0=0-val */

R0 ← (-1); JUMP Return-re; } Return(R0); } /* A HW-PUSH-nál a PC a Return-re mutat. Látjuk majd, két visszatérés van ebből. Először a JUMP Return miatt (R0=-1-gyel), másodszor a PC felvétele miatt (de akkor előtte az R0-t is felveszik, az meg 0 lesz, tehát R0=0-val). */ Ütemezés, © Vadász, 2008.

Ea6 41

Pszeudókódok2 int resume_context(pid_t pid) { A pid-del azonosított processz verméről vedd vissza az általanos regisztereket; POP PSW; POP PC; /* ide a vezérlés nem juthat el */ } /* Miért nem jut oda a vezérlés? Mert a visszavett PC a save_context Return-jére mutat! */ Ütemezés, © Vadász, 2008.

Ea6 42

14

A Context Switch pszeudókódja ...

if (save_context()){ Ütemezz másik processzt, ennek pid-je = new_pid; resume_context(new_pid); /* ide a vezérlés nem juthat el */ } ... /* Innen futhat a visszavett kontextusú processz */ /* Ne feledjük, a save_context-ből két visszatérés is van: az ifnek először nem-nulla értéket ad (és belefut a schedulingba), másodszor 0-val visszatérve kikerüli azt. */ Ütemezés, © Vadász, 2008.

Ea6 43

A vezérlés menete … Dönt; if(save_context( )) { npid = Ütemez; Resume_context(npid);

B

A IT

} 2nd; D S Ü 2nd

R

IRET Ütemezés, © Vadász, 2008.

Ea6 44

Volt már ilyen, emlékezzünk ... #include <setjmp.h> jmp_buf env; int i = 0; main () { if (setjmp(env) != 0) { (void) printf("2nd from setjmp: i=%d\n", i); exit(0); } (void) printf("1st from setjmp: i=%d\n", i); i = 1; g(); /*NOTREACHED*/ } g() { longjmp(env, 1); /*NOTREACHED*/ } Ütemezés, © Vadász, 2008.

Ea6 45

15

Összefoglalás • Foglakoztunk az – – – –

Alapokkal, stratégiákkal Időkiosztási algoritmusokkal VAX/VMS, NT, Unix időkiosztással A Context Switch implementációval


Ea6 46

OPERÁCIÓS RENDSZEREK Ütemezés és a Context Switch Vége

16

OPERÁCIÓS RENDSZEREK. A mai program. Fogalmak. Ütemezés és a Context Switch

Recommend Documents