Mir l lesz szó? Operációs rendszerek. A sorbaállási modell. A sorbaállási modell. Er forrás csoportosítás 1. Er forrás csoportosítás 2

Mirl lesz szó? • A probléma: vetélkedés erforrásokért • Alapfogalmak, kívánalmak • Megoldások

Operációs rendszerek

– Váltogatás és ki érdekelt, zároló-változó stb. (primitívek, alapalgoritmusok) – szemaforok

Kölcsönös kizárás - szemaforok


• Problémák megoldásai, esettanulmányok

1


A sorbaállási modell

2

A sorbaállási modell

• Erforrásokért verseng processzek rendszerének analizálására • Várakozási sorok (queue) képezhetk (téglalapok) • Vannak erforrások (körök) • Ütemezések (függleges vonal)

Középtávú ütemezés M Belép

Felfüggesztett

– CPU ütemezésnél • Hosszú-távú • Középtávú • Rövid-távú

Kilép

CPU

Futásra kész

Hosszú-távú ütemezés

Memória kérés

Rövid-távú ütemezés I/O

Várakozó

I/O kérés

I/O ütemezés

– Egyéb erforrás ütemezések is lehetnek


Idszelete letelt

3

Erforrás csoportosítás1

4

Erforrás csoportosítás2 • „Létük” szerinti csoportosítás

• A típus száma szerint

– Elállítandó és fogyasztható (consumable) erforrás

– Egy példányos erforrások – Többpéldányos erforrások: használati értékükben azonosak a példányok)

• Itt: elállítás – igénylés|kérés – használat forgatókönyv

– Újrahasználható erforrás • Itt: igénylés|kérés – használat – lemondás|felszabadítás forgatókönyv …

• A forgatókönyvekhez

• Használati mód szerint

– Igénylés, kérés: esetleg várakozással

– Megosztottan használhatók, melyek • Állapota lementhet és visszaállítható, emiatt esetleg „elvehetk” a használótól (preemption lehetséges)

• Általánosan: egy kéréssel több erforrásból, több példányt is igényelünk …

– A felszabadítás|lemondás (szignálozás is) 2 típusa (legalább) • Adott típusból valamennyit felszabadítom • Adott foglaltakból adott példányokat szabadítok fel

– Csak kizárólagosan használhatók, melyek • Nem vehetk el a használótól csak „zökkenkkel” (pl. vissza kell küldeni a használót egy korábbi állapotába, terminálni kell a használót) Operációs rendszerek


• Az „igénylés|kérés” és a „lemondás|felszabadítás” absztrakt instrukciók 5


6

A CPU erforrás különleges …

Erforrás-használat - holtpont

• A (független) processz modellnél a CPU erforrás használathoz preemptív ütemezésnél nincs kérhasznál-lemond „instrukciókészlet”

• Az (egy) egyszer példa: – P1 és P2 processzek; X és Y erforrások … – P1-ben kér(X); kér(Y) absztrakt insrukció-sor – P2-ben kér(Y); kér(X) absztrakt insrukció-sor

– A CPU ütemezésben nem lesz holtpont probléma … – Legfeljebb a „kooperatív” ütemezésnél van lemondás …

• A kérés-kielégítés modelljei

• A „User-level” szálakat a taszk saját maga ütemezi …

– A kér-en egy processz „blokkolódhat” (vár kielégítésre) – A kielégités modellje: kielégítésre váró szignált vár (eseményt vár), végül megkapja a szignált; valami kell adja a szignált

– Itt már lehet holtpont probléma …


7

Együttmköd processzek egy absztrakt problémája

• A termék ugyan lehet elfogyó erforrás, de az elállítására várakozás a raktár üresség kezeléssel eliminálódhat • A raktárra való korlátozás vonatkozhat:

– Vannak termel folyamatok, melyek saját ritmusukban terméket (item, message) állítanak el és behelyezik egy raktárba. – Vannak fogyasztó folyamatok, melyek saját ritmusukban a terméket kiveszik a raktárból és felhasználják, fogyasztják – Van korlátozott termék-raktár.

– a raktár méretére (teli raktárba termel nem rakodhat, üresbl fogyasztó nem fogyaszthat); Ez megelzési (precedencia) probléma. – a raktár használatára (egy idben több termel nem használhatja a raktárt, egy idben több fogyasztó nem használhatja a raktárt, egy idben csak egy folyamat, akár termel, akár fogyasztó, használhatja a raktárt.) Ez kölcsönös kizárási probléma.


Kölcsönös kizárás processz() { while (true) { nem-kritikus-szakasz1(); kérelem(); használat(); felszabadítás(); nem-kritikus-szakasz2(); } }

9


10

Alapfogalmak1

Precedencia

processz() { // kérelmez processz while (true) { nem-kritikus-szakasz1(); kérelem(); használat(); nem-kritikus-szakasz2() } } processz() { // engedélyez ... if (van-kérelmez) engedélyezés(); .... }


8

A termel-fogyasztó probléma

• Termel-fogyasztó (Producer-Consumer) probléma

Az alap séma


11

Kölcsönös kizárás (Mutual Exclusion): • Csak kizárólagosan használható, egypéldányos erforrásokért vetélked processzek közül egy és csakis egy, több példányos erforrásokért vetélked processzek közül kötött számú processz kapja meg a jogot egy erforráspéldány használatára. • A kölcsönös kizárásnak legyenek módszerei, eszközei, technikái.


12

Alapfogalmak2

Alapfogalmak3-5

• Kritikus szakasz (Critical Section): a folyamaton belüli kódrész (valójában annak futási idszakasza), melyen belül a kölcsönös kizárást meg kell valósítani. Egy erforráspéldány kizárólagos használatának (id)szakasza.

• Belépési szakasz (Entry Section) a folyamaton belül az a kódrész, ahol kéri az engedélyt a kritikus szakaszba való belépésre. A kérelem szakasza. • Kilépési szakasz (Leave Section) az a kódrész, ahol elhagyja a processz a kritikus szakaszt. Az erforráspéldány felszabadítása: jelzés más processzeknek az erforrás felszabadulásáról. • A folyamatoknak természetesen lehetnek nem kritikus szakaszaik is.


13


14

Kívánalmak1

Kívánalmak2

• Biztonsági (safety) kívánalom: Valósuljon meg a kölcsönös kizárás: ha processz kritikus szakaszában fut, más processz csak akkor léphessen be kritikus szakaszába, ha van még szabad erforráspéldány. (Ugyanazon idben csakis korlátozott számú kritikus szakasz futhat.). Természetesen, ezalatt további processzek a belépési szakaszukban lehetnek (éppen az a fontos, hogy azon ne jussanak túl).

• Elrehaladási (progress) kívánalom: általában nem kritikus szakaszban és nem belépési szakaszban futó processz ne befolyásolja mások belépését. Ha egyetlen folyamat sincs kritikus szakaszában és vannak processzek a belépési szakaszukban, akkor csakis ezek vegyenek részt abban a döntésben, hogy melyik fog végül belépni. Ráadásul ez a döntés nem halasztható végtelenségig.


15


Kívánalmak3-4

A mutex alap séma

• Korlátozott várakozási (bounded waiting) kívánalom: ha egy processz bejelentette igényét a belépésre, de még nem léphet be, korlátozzuk ésszeren azt, hogy egy másik processz hányszor léphet be. Egy processz se várakozzon a végtelenségig belépésre azért, mert egy másik újból bejelentve az igényét megint megelzi. Ne legyen kiéhezés. • Hardver és platform kívánalom: ne legyenek elfeltételeink a hardverre (sem a CPU-k típusára, számára, sem a sebességükre), a processzek számára, relatív sebességükre, az operációs rendszer ütemezésére stb. Operációs rendszerek

16

17

Kölcsönös kizárás

„Blokkolni” kell „Szignáloz” Blokkolni? – Ne jusson a CPU-hoz – Busy waiting – Állapotváltással

processz() { while (true) { nem-kritikus-szakasz1(); kérelem(); használat(); felszabadítás(); nem-kritikus-szakasz2(); } }


18

Megoldás #1: váltogatás

Alapalgoritmusok, építkövek

Az osztott turn változó nyomonköveti, ki lesz a következ. shared turn=i;

0-ik megoldás: Megszakítás letiltás

processz-i() { while (true) { nem-kritikus-szakasz1(); while(turn!=i) nop(); kritikus-szakasz(); turn = j; nem-kritikus-szakasz2(); } }

• Kritikus szakasz elején IT letiltás, végén engedélyezés • Csak egy CPU-ra jó (4. követelmény!) • Veszélyes: hiba esetén deadlock! Csak nagyon letesztelt kernel kódokban!

processz-j() { while (true) { nem-kritikus-szakasz1(); while(turn!=j) nop(); kritikus-szakasz(); turn = i; nem-kritikus-szakasz2(); } }

Sérül a 2. követelmény: nem követi, hogy egy processz érdekelt-e vagy sem (4. köv: csak 2 processzre). Operációs rendszerek

19


Megoldás #1: turn & erd

Zárolásváltozó használat #2

Egymás váltogatása az érdekeltség figyelembevételével

Az osztott lock változó tesztelhet és beállítható. shared lock = false;

Shared turn, erd[N] = {false, false, …}; processz-i() { processz-j() { while (true) { while (true) { nem-kritikus-szakasz1(); nem-kritikus-szakasz1(); erd[i] = true; turn = j; erd[j] = true; turn = i; while (erd[j] && turn == j) while (erd[i] && turn == i) nop(); nop(); kritikus-szakasz(); kritikus-szakasz(); erd[i] = false; erd[j] = false; nem-kritikus-szakasz2(); nem-kritikus-szakasz2(); } } } }

processz-i() { while (true) { nem-kritikus-szakasz1(); while (tsl(&lock)) nop(); kritikus-szakasz(); lock= false; nem-kritikus-szakasz2(); } }

int tsl(*lock) { register int temp; temp = *lock; *lock = true; return temp; } // ez megszakithatatlan // instrukcio kell legyen

Sérül a 4. követelmény: nem minden hardveren van ilyen instrukció. IT letiltás többprocesszoros rendszeren nem segít. A 3. követelmény is sérülhet: egy processz kisajátíthatja az erforrást.

Csak a 4. köv. sérül: 2 processzre jó. De kiterjeszthet! Operációs rendszerek

20

21


Szemaforok

22

Operációk szemaforon

• Dijkstra (1965) szemafor: pozitív egész számot tartalmazó közös változó és egy várakozási sor. • Szemaforon két atomi operáció. Atomi:

DOWN(semaphore S) { if (S >= 1) S=S - 1; else { a hivo helyezze magat az S varakozo sorara és PC-t állítsd az if elé}

– Egy idben csak egy processz operálhat egy szemaforon. – Blokkolódásból “felébred“ processz végrehajtja azt az operációt, amin elzleg blokkolódott.

} UP(semaphore S) {

• DOWN (P: Passeren) - ezen blokkolódhat. • UP (V: Vrijgeven [vrejhéfen]) - ez szignáloz.

S= S + 1; if (S varakozo sora nem ures) {egy processzt vegy le rola}

}


23


24

Esettanulmány

Használata Kritikus szakasz védelme shared semaphore s = 1;

Egy termel-fogyasztó probléma Szinkronizáció

• • • •

Több termel folyamat van. Több fogyasztó folyamat van. Korlátozott a raktár mérete: N számú hely. Korlátozott a raktárhoz való hozzáférés: csak egy ki-berakó gép van (egy idben csakis egy termel vagy fogyasztó használhatja a raktárt). • Raktár “teliség“ és “üresség“ kezelend. Belátható, legalább 3 szemafor kell:

shared semaphore s = 0;

processz-i() { while (true) { nem-kritikus-szakasz1(); DOWN(s); kritikus-szakasz(); UP(s); nem-kritikus-szakasz2(); } }

processz-i() { // ui elozze uj-t ... ui(); UP(s); ... } processz-j() { ... DOWN(s); uj(); ... }


– Ki-berakó gép védelmére; – Üresség jelzésére; – teliség jelzésére.

25

#define N semaphore semaphore semaphore

void producer ( ) { termek_ttermek; while (1) { termek=gyart( ); // nem kritikus szakasz DOWN(ures); // üres rekeszre vár DOWN(mutex); // raktárba lép termeket_raktarba_tesz(termek); UP(mutex); // raktárból kilép UP(teli); // teli jelzést növeli } }

32 mutex = 1; ures = N; teli = 0;

void cosumer ( ) { termek_ttermek; while (1) { DOWN(teli); // teli rekeszre vár DOWN(mutex); // raktárba lép termek=termeket_raktarbol_vesz( ); UP(mutex); // raktárból kilép UP(ures); // üresek száma n } } 27

Egy kérdés


28

A Unix szemafor mechanizmusa

• Mi történne, ha a DOWN(teli); DOWN(mutex);

26

A fogyasztó

32 mutex = 1; ures = N; teli = 0;


Szinkronizáció


A termel #define N semaphore semaphore semaphore

Kizárás probléma

• Gyors, kis átvihet információmennyiség • Indirekt, OS kötdés, többirányú • A kapcsolódó rendszerhívások:

// teli rekeszre vár, vagy csökkenti // belép a raktárba

sorokat felcserélnénk?

– semget( ) – semctl( ) – semop( )

// készítés, azonosítás // kontroll, jellemzk lekérdezése, törlés // operációkészlet végrehajtás

• A szükséges „beleértett” fájlok: – #include <sys/ipcs.h> – #include <sys/sem.h>


29


30

Dijkstra szemafor – Unix szemafor

A rendszerhívások: semget( )

• D nem definiálta a blokkolás implementációját • A Usem: – Blokkolásos jelleg, – elemi szemaforok készlete van egyetlen szemaforban, – elemi operációk készletének végrehajtása történik egyetlen (atomi) operációban, – az elemi operációk nemcsak egységgel csökkenthetnek, növelhetnek (non-unitary), – van nulla ellenrzés is, – kérésre az elemi operációk „visszavonódnak” (undo) – kérésre nincs blokkolódás, bár kellene. Operációs rendszerek

31

Az elkészült szemafor bels adatstruktúrái • Az alap adatszerkezet: struct semid_ds { struct ipc_perm sem_perm; // hozzáférések struct sem *sem_base; // a 0. elemi szem. Pointere ushort sem_nsems; // az elemi szem.ok száma … } • Ebbl egy elemi szemafor adatai: struct sem { ushort semval; // pillanatnyi érték ushort semzcnt; // nullára váró processzek száma ushort semncnt; // növelésre várók száma pid_t sempid; // utolsó operáló processz } Operációs rendszerek


32

A rendszerhívások: semctl( ) int semctl( int sid, int semnum, int cmd[, union semunion arg]); • Ahol sid a bels leíró, semnum az elemi szemafor indexe, cmd IPC_STAT állapot lekérdez, IPC_SET állapot beállító, IPC_RMID törl parancs. A GETVAL, GETALL, GETPID, GETNCNT, GETZCNT szintén lekérdez, a SETVAL, SETALL beállító parancsok. arg a felhasználói címtartományhoz tartozó union változó vagy konstans, lekérdezésnél eredmény, beállításkor forrás.

33

A semctl( ) híváshoz


34

Rendszerhívások: semop( )

• Az elemi szemaforok 0 és nsems-1 közötti indexek. • Az i-edik elemi szemafor inicializálása: semctl(sid, i, SETVAL, init_value) • Az i-edik elemi szemafor pillanatnyi értékének lekérdezése: value=semctl(sid, i, GETVAL); • Az arg típusa: union semun { int val; // elemi szemafor érték ushort *array; // elemi értékek tömbjének ptr-e struct semid_ds *buf; // adatstruktúrák mutatója } arg; // egyes rendszerekben ez a sem.h fájlban … Operációs rendszerek

int semget(key_t key, int nsems, int flg); • Ahol key (hexa) kulcs a küls azonosításhoz, nsems az elemi szemaforok száma a szemaforban flg készítéskor védelem, hozzáférés beállítás, azonosításkor létezés ellenrzés, hozzáférés ellenrzés • Készít nsems elemi szemaforból álló szemafort az adott kulccsal és hozzáférésekkel, vagy azonosít létez szemafort. • Visszatér a szemafor bels leírójával, vagy hibaértékkel. • Készítés során az elemi szemaforok 0 értéket vesznek fel.

int semop(int sid, struct sembuf *sops, unsigned nsops); • Ahol: sid a szemfor leírója, sops pointer az elemi operációk tömbjéhez, nsops az elemi operációk száma. • Egy elemi operációt a következ struktúra határoz meg: struct sembuf { ushort sem_num; // az elemi szemafor indexe short sem_op; // az elemi operáció short sem_flg; // operációt módosító jelz } 35


36

Az operációkészlet

A sem_op értéke

• Egy operációkészletre példa: struct sembuf opkeszlet[4] = { 0, -2, 0, 1, 1, 0, 2, 2, 0, 0, 0, 0 }; • És az operáció:

• Ha a sem_op < 0, akkor vár, amíg a semval |sem_op|, és semval+=sem_op; (Negatív sem_op dekrementáció, down operáció.) • Ha sem_op == 0 akkor vár, amíg semval == 0 lesz. (Null ellenrzés.) • Ha sem_op > 0, akkor semval+= sem_op; (Pozitív sem_op inkrementráció, up operáció.)

semop(sid, &opkeszlet[0], 4);


37


A sem_flg módosító

Egy példa: nsems=3, nops=4

• Lehet 0, vagy vagy kapcsolatban a következ makrók • IPC_SEMUNDO

Kiindulás

– A processz terminálódására az elemi opráció „visszaáll”.

• IPC_NOWAIT – Ha nem sikerülne a dekrementáció (down), akkor abortál a semop( ) és a processz fut tovább. Mire jó ez? … while( 1) { if ( semop( ) ) { kritikus_szakasz( ); break} else valami_mas_hasznos( ); } …


39

Példaprogramok

sid 2 0 0 0

1 2

Eredmény num

op

flag

0

-2

0

0

1

1

0

1

2

2

0

2

0

0

0

3

sid 0 0 1

1

2

2

semval


40

Az ebédel filozófusok …

• Nézzük a „szokásos” helyet! www.iit.uni-miskolc.hu/iitweb/opencms/users/DVadasz/ GEIAL302B/Peldaprogramok/ipc/sem


38

41

• Nézzék meg Tanenbaum megoldást (D szemaforral egész bonyolult. • Elegáns megoldás U szemaforral


42

Ebédel filozófusok

Ebédel filozófusok • Az i-edik filozófus programja …

• „Megterítünk” (inicializálás) #define N 5 … sid = semget(key, N, 0666); … for(i=0; i < N; i++) semctl(sid, i, SETVAL,1); …

/* inicializáljuk a tömböt 1-ekre */


43

Operációs rendszerek Kölcsönös kizárás - szemaforok


45

#define N #define i i #define BAL (i – 1) % N /* bal szomszéd */ #define JOBB (i + 1) % N /* jobb szomszéd */ static struct sembuf villakat[2] = { BAL, 0, 0, JOBB, 0, 0}; … while(1) { gondolkodom( ); villakat[0].semop = -1; villakat[1].semop = -1; semop(sid, villakat, 2); /* 2 villa fel */ nyam_nyam_spagetti( ); villakat[0].semop = 1; villakat[1].semop = 1; semop(sid, villakat, 2); /* 2 villa le */ } Operációs rendszerek

44

Mir l lesz szó? Operációs rendszerek. A sorbaállási modell. A sorbaállási modell. Er forrás csoportosítás 1. Er forrás csoportosítás 2

Recommend Documents