Processzusok, szálak • Egy processzus – Saját címtartomány – Egyetlen vezérlési szál
Operációs rendszerek MINB240
• Hasznos lehet több kvázi párhuzamos vezérlési szál használata egy címtartományban – Mintha különálló processzus lenne
2. előadás Szálak, IPC
• Szál (thread) vagy könnyű súlyú processzus
1
Szál modell
2
Szál modell Nem csak processzus, hanem szál táblázat is van Processzus elemei Címtartomány Globális változók Megnyitott fájlok Gyermekprocesszusok Függőben lévő ébresztők Szignálok és szignálkezelők Elszámolási információk
(a) 3 processzus, mindegyik egy szállal (b) 1 processzus, 3 szállal 3
Szál elemei Utasításszámláló Regiszterek Verem Állapot
4
Miért használunk szálakat?
Szövegszerkesztő
• Hasonlóak a processzusokhoz, de ... • Kevesebb idő kell – a létrehozáshoz – a lezáráshoz – a szálak közötti váltáshoz
• A szálak egy memóriaterületen belül vannak így könnyen kommunikálhatnak a kernel hívása nélkül
5
6
Többszálas Web böngésző
Kép kérés processzussal
• Sok weblap tartalmaz több kis képet • A böngészőnek minden képért külön kapcsolatot kell kiépítenie a lapot tároló számítógéppel • A kapcsolatok felépítése és bontása sok idő • A böngésző több szál használatával több képet kérhet le egyszerre
Idő Kép kérés
Kép kérés
Processzus 1 server
server
Futás Várakozás 7
8
Kép kérés szállal
Többszálas Web szerver
Idő Kép kérés
server
Szál A (Processzus 1) Szál B (Processzus 1)
Kép kérés
server
Futás Várakozás Várakozás, amí szál B végez
9
Felhasználói szintű szálak
10
Felhasználói szintű szálak, előnyök
• A kernel semmit nem tud a szálakról
• Szálak közötti kapcsolás gyorsabb
– Csak a processzusokat látja
– Nincs szükség kernel csapdára, rendszerhívásra
• Szál kezelés egy könyvtárban van implementálva
11
• Bármelyik operációs rendszer alatt implementálható • Nagy számú szál hozható létre alkalmazásonként
12
Felhasználói szintű szálak, hátrányok
Kernel szintű szálak
• A szálnak önként kell feladnia a futását – Nincs óra megszakítás a szálhoz – Együttműködő többszálas programozás
• Nem használja ki ha több CPU van a gépben • Ha egy szál blokkolt, akkor az egész processzus blokkolt, hiszen a kernel semmit nem tud a szálakról
13
Kernel szintű szálak
14
Hibrid szálak
• Előnyök – Parallel működés • Blokkolt I/O és számítás átlapolható • Ki tud használni több processzort
• Hátrányok – Szál létrehozás és lezárás esetén szükség van a kernelbe lépésre (rendszerhívásra) – „Drágább” mint a felhasználói szintű
15
16
Processzusok kommunikációja • •
InterProcess Communication (IPC) Milyen feladatokat lát el: 1. Egymás közötti információcsere 2. Erőforrások megosztás (ne keresztezzék egymást) 3. Szinkronizáció (megfelelő sorrend kialakítása)
Processzusok kommunikációja •
Szálaknál – 1. nem probléma (közös címtartomány) – 2. és 3. ugyanúgy érvényes
17
Többszálas program, egy hibajelző Idő
Szál 1
18
Nyomtató démon Háttér katalógus
Szál 2
Honnan vegyük a nyomtatandó file nevét?
errno = -1
Hová tároljuk a nyomtatandó file nevét?
errno = -2
if(errno == -1) { … 19
20
Versenyhelyzet
Versenyhelyzet
• Ha kettő vagy több processzus olvas vagy ír megosztott adatokat és a végeredmény attól függ ki és mikor fut
• Problémás lehet megtalálni a versenyhelyzetet
• Megoldás: – Megelőzés – Kölcsönös kizárás: egy módszer, amely biztosítja hogy ha egy processzus használ valamely megosztott változót, fájlt, akkor a többi processzus „tartózkodjon” ettől a tevékenységtől.
– Legtöbb teszt jó, csak néha kapunk hibát
21
Kritikus terület, szekció
22
Versenyhelyzet elkerülésének 4 feltétele
• Egy processzus ideje jelentős részét számítással tölti • Néha a megosztott változókhoz, fájlokhoz kell hozzáférni • Azt a részt mely megosztott részekhez fér hozzá kritikus területnek nevezzük • Az kellene hogy két processzus azonos időben ne legyen kritikus szekcióban (kölcsönös kizárás) • Koordinálatlan belépés a kritikus szekcióba verseny helyzethez vezet 23
1. Ne legyen két processzus egyszerre a saját kritikus szekciójában (kölcsönös kizárás) 2. Semmilyen előfeltétel ne legyen a sebességekről vagy a CPU-k számáról 3. Egyetlen, a kritikus szekcióján kívül futó processzus sem blokkolhat más processzusokat (haladás) 4. Egyetlen processzusnak se kelljen örökké arra várni, hogy belépjen a kritikus szekciójába (korlátosság) 24
Kölcsönös kizárás kritikus szekcióval Idő A kritikus szekcióba lép A kilép a kritikus szekcióból Processzus A B megpróbál kritikus szekcióba lépni
B kritikus szekcióba lép
B kilép a kritikus szekcióból
Megoldások és problémák
Processzus A
T1
T2
B blokkolódik
T3
T4
25
Kölcsönös kizárás tevékeny várakozással
Zárolásváltozó • Megosztott zárolásváltozó
• Tevékeny várakozás – A processzus folyamatosan ellenőrzi hogy beléphet-e a kritikus szekcióba – Semmi mást (hasznosat) nem tud csinálni a processzus
• • • •
26
Zárolásváltozó Szigorú váltogatás Peterson megoldása Hardware-es segítséggel 27
– Kezdetben értéke 0 – Mielőtt egy processzus belépne a kritikus szekcióba • Ha a zárolásváltozó értéke 0, akkor 1-re állítja és belép a kritikus szekcióba • Ha a zárolásváltozó értéke 1, akkor várakozik amíg 0 nem lesz
28
Zárolásváltozó, megoldás?
Zárolásváltozó, a problémás futás Idő
Processzus A
Processzus B
while(TRUE) { while(TRUE) { while(lock == 1); lock = 1; critical(); lock = 0; non_critical(); }
while(TRUE) { while(lock == 1);
while(TRUE) { while(lock == 1); lock = 1; critical(); lock = 0; non_critical(); }
while(lock == 1); lock = 1; lock = 1; critical();
critical(); lock = 0; non_critical(); }
lock = 0; non_critical(); }
29
Zárolásváltozó, megoldás?
30
Szigorú váltogatás
• Segít-e ha a megint ellenőrizzük a zárolásváltozót az írás előtt? (lock = 1) • NEM – A processzustól bármikor elvehetik a vezérlést!!!
while(TRUE) { while(turn != 0); critical(); turn = 1; non_critical(); }
while(TRUE) { while(turn != 1); critical(); turn = 0; non_critical(); }
Helyesen működik, de ...
31
32
Szigorú váltogatás
Szigorú váltogatás
Idő Processzus 0 while(TRUE) { while(turn != 0); critical(); turn = 1; non_critical();
while(turn != 0); critical(); turn = 1; while(turn != 0); critical(); turn = 1;
• 0. processzust blokkolta egy nem kritikus szekcióban levő processzus • Sérti a 3. feltételt
Processzus 1 while(TRUE) {
while(turn != 1); critical(); turn = 0; non_critical(); ...
• Akkor jó, ha a két processzus szigorúan váltogatja egymást
Blokkolódik, amíg processzus 1 ismét végre nem hajt egy kritikus szekciót 33
34
Peterson megoldása
Peterson megoldása
#define IGEN 1 #define NEM 0 #define N 2
Processzus 0 while(TRUE) { enter_region(0); critical(); leave_region(0); non_critical(); }
int turn; int interested[N]; void enter_region(int process) { int other; other = 1 - process; interested[process] = IGEN; turn = process; while(turn == process && interested[other] == TRUE) ; } void leave_region(int process) { interested[process] = NEM; }
35
Processzus 1 while(TRUE) { enter_region(1); critical(); leave_region(1); non_critical(); }
36
Peterson megoldása interested
Processzus 0
turn
0
1
0 1 1
0 0 1
0 1
1
1
while(TRUE) { enter_region(0); critical(); critical(); leave_region(0); 0 non_critical();
Peterson megoldása interested
Processzus 1
Processzus 0
while(TRUE) {
while(TRUE) { enter_region(0);
enter_region(1);
0
1
0 1 1
0 0 1
turn
Processzus 1 while(TRUE) { 0 1
enter_region(1);
while(turn == process && interested[other] == TRUE) ;
critical(); leave_region(0); non_critical();
critical(); leave_region(1); non_critical();
}
critical(); leave_region(1); non_critical();
}
}
}
37
Hardware-es segítséggel, megszakítások
Ha majdnem egyszerre hajtják végre az enter_region részt akkor 38 is működik!!!
Hardware-es utasítással
• Amikor belép a kritikus szekcióba letítja az összes megszakítást. Amikor kilép engedélyezi. • Ilyenkor az órajel is tiltva van, nincs processzus átütemezés • Probléma – Felhasználói processzus kezébe adjuk a megszakításokat (nem szerencsés) • Mi van ha egy processzus soha nem kapcsolja vissza
– Több CPU esetén a tiltás csak egy CPU-ra vonatkozik, így még mindig fennállhat a versenyhelyzet 39
• Zárolásváltozók helyes implementálása • Test and Set Lock utasítás: TSL RX,LOCK – Beolvassa a LOCK memóriaszó tartalmát az RX regiszterbe – Egy nem nulla értéket ír a LOCK memóriába
• Garantáltan nem szétválasztható, nem megszakítható műveletek – Atomi művelet – Az utasítást végrehajtva a CPU zárolja a memória sínt minden más CPU elől 40
Eddigiek összefoglalása
Alvás-ébredés
• Eddigi módszerek tevékeny várakozást használtak és van két problémájuk: – Aktívan használják a CPU-t, még a várakozás alatt is – Fordított prioritás probléma • Legyen két processzus, H és L – H processzusnak magas a prioritása – L processzusnak alacsony a prioritása – Amikor H futáskész, mindenképp fut
• L belép a kritikus szekcióba • H futáskész lesz és belépne a kritikus szekcióba
• Az ötlet: – Amikor a processzus egy eseményre vár, meghívja a sleep (altatás) függvényt és blokkolódik – Amikor az esemény bekövetkezik, az esemény generáló processzus (egy másik processzus), felébreszti (wake-up), futásra készre állítja a blokkolt processzust.
• Gyártó-fogyasztó probléma
– Örökké várni fog, mert L soha nem futhat
– Korlátos tároló problémának is nevezik 41
Gyártó-fogyasztó probléma
Gyártó-fogyasztó probléma, kérdések
• A gyártó adatokat generál és egy bufferben tárolja • A fogyasztó adatokat vesz ki a bufferből és felhasználja • A két processzus egy közös, korlátos méretű tárolón osztozik gyártó
X
fogyasztó
X
42
• Gyártó – Amikor a buffer megtelik, elalszik – Felébresztik, amikor a fogyasztó kivett adatokat
• Fogyasztó – Amikor a buffer üres, elalszik – Felébresztik, amikor a gyártó betett adatokat
• Versenyhelyzet alakulhat ki
X
43
44
Gyártó-fogyasztó probléma
Gyártó-fogyasztó probléma Processzus 0
int count = 0; #define N 4 gyarto() { while(TRUE) { item = produce() if(count == N) sleep(); insert_item(); count++; if(count == 1) wakeup(con); } }
0
fogyaszto() { while(TRUE) { if(count == 0) sleep(); remove_item(); count--; if(count == N-1) wakeup(prod); } }
Együttes, ellenőrizetlen hozzáférés
Processzus 1
count
gyarto() { while(TRUE) { item = produce() if(count == N) sleep(); insert_item(); count++; if(count == 1) wakeup(con);
fogyaszto() { while(TRUE) { if(count == 0)
Igaznak találja
1
Elalszik, örökre sleep(); remove_item(); count--; if(count == N-1) wakeup(prod);
Elveszik, hiszen fogyasztó nem alszik 45
Megtölti a buffert és elalszik }
} } 46
}
Szemaforok
down-up
• E.W. Dijkstra, 1965-ben javasolta • Egész változókban számoljuk az ébresztések számát • Az új változó típust szemafornak nevezte el (semaphor) • Két művelet:
• down – Megvizsgálja hogy a szemafor értéke nagyobb-e mint nulla? • Ha igen, akkor csökkenti az értéket és folytatja • Ha nulla, akkor a processzust elaltatja mielőtt befejeződne
• up – A szemafor értékét növeli – Ha egy vagy több processzus aludna ezen a szemaforon akkor egyet kiválaszt és megengedi hogy a down befejeződjön
– Down – Up
• Általánosabb mint, sleep-wakeup 47
48
Szemaforok
Szemaforok
• Atomi, elemi műveletek (nem szedhetők szét)
• • • •
– Csak néhány utasítás
• Egy CPU esetén megszakítások használhatók • Több CPU esetén a TSL utasítás használható
Szemaforok mint szinkronizációs eszközök Először A majd B részlet fusson le Szemafor: count = 0 Kód: Processzus i Processzus j ... A up(count)
... down(count) B
49
Mutex • Mutex = Mutual Exclusion (Kölcsönös kizárás) szóból származik a megnevezés!! Nem a kölcsönös kizárást jelenti !!!!!!!!
semaphor mutex; mutex = 1; /* inicializálás */
50
Gyártó-fogyasztó probléma szemaforral • 3 szemafor – full (0): tele rekeszek száma – empty (N): üres rekeszek száma – mutex (1): biztosítja, hogy egyszerre csak az egyik processzus érje el a tárolót
down(mutex); /* belépés a kritikus szekcióba */ kritikus szekció up(mutex); /* kilépés a kritikus szekcióból */
51
52
Gyártó-fogyasztó probléma szemaforral gyarto() { while(TRUE) { item = produce() down(&empty); down(&mutex); insert_item(); up(&mutex); up(&full); } }
Szemaforok összefoglalva • Szemaforokkal többféle probléma megoldható • Ugyanakkor könnyű hibázni
fogyaszto() { while(TRUE) { down(&full); down(&mutex); remove_item(); up(&mutex); up(&empty); } }
– Azonos számú down és up kell – Megfelelő sorrendben kell őket kiadni
53
54
Monitorok
Egyszerű példa
• Programozás könnyítésére Hoare (1974) javasolta – Magas szintű szinkronizációs primitív – A programozási nyelv része
monitor szamlalo { int count; inc() {
• Ötlet
Kölcsönös kizárást biztosít Nincs versenyhelyzet a count változón
count = count + 1;
– Függvények és változók egy speciális modulba vannak csoportosítva – Egyszerre csak egy processzus/szál hajthatja végre a monitoron belüli részt • Fordító (compiler) biztosítja a kölcsönös kizárást
} dec() { count = count - 1; } }
55
56
Eddigiek összefoglalás
Üzenetküldés
• Szemaforok túl alacsony szintűek • A monitorok csak néhány programozási nyelvben használhatók • Mindkét esetben a processzusok elérik a közös memóriát • Mi van ha több CPU - több memóriával rendelkezünk? (Nincs közös memóriaterület.) Üzenetküldés
• Két primitív – send: küldés • send(cél, üzenet);
– receive: fogadás • receive(forrás, &üzenet);
• Egyszerűek, akár könyvtári függvények is lehetnek – MPI: Message Passing Interface – PVM: Parallel Virtual Machine
57
Szinkronizálás
58
Szinkronizálás
• A küldő és fogadó lehet blokkoló vagy nem blokkoló
• Nem blokkoló küldés, blokkoló fogadás
• Blokkoló küldés, blokkoló fogadás
• Nem blokkoló küldés, nem blokkoló fogadás
– A küldő folytatja működését – A fogadó blokkolódik amíg az üzenet meg nem érkezik – Egyik processzus sem várakozik, blokkolt – A fogadó kaphat üzenetet vagy semmit
– Mind a küldő, mind a fogadó blokkolódik amíg az üzenet meg nem érkezik teljesen – Ezt randevúnak hívják
59
60
Üzenetek küldése
Üzenetküldés, tervezési szempontok
• Direkt címzés – Minden processzushoz hozzárendelünk egy egyedi címet • Az üzenetet a processzusokhoz kell címezni
• Olyan problémák amelyekkel eddig nem kellett foglalkozni – Üzenetek elveszhetnek a hálózaton • Lehet nyugtázó üzenetet kérni • Ha a küldő nem kapja meg a nyugtázó üzenetet, újra elküldi az üzenetet
• Indirekt címzés – Levelesláda • • • • •
A címzés a levelesládának szól Több üzenetet is képes tárolni ideiglenesen Ha egy láda tele van a küldő felfüggesztődik A fogadó a levelesládából fogadja az üzeneteket Két processzus csak akkor kommunikálhat ha közös a levelesládájuk
– Üzenet megjön, de a nyugta elvész • Ismét megkapja az üzenetet. Mi legyen vele? • Sorszámmal megoldható – Ugyanolyan sorszám esetén felismerhető, hogy már megérkezett
61
62
Üzenetküldés, tervezési szempontok • Hitelesítés
Példa: szálak • Felhasználói szintű szálak
– Tényleg a fájl szerverrel kommunikálunk-e?
– POSIX Pthreads – Win32 threads – Java threads
• Kernel szintű szálak – – – – 63
Windows XP/2000 Solaris Linux Mac OS X 64
Több szálas modellek
Sok-egy
• Sok-egy • Egy-egy • Sok-sok
• Sok felhasználói szintű szál tartozik egy kernel szintű szálhoz • Példák – Solaris Green Thread – GNU Portable Thread
65
Egy-egy
66
Sok-sok
• Minden felhasználói szintű szálnak egy kernel szintű szál felel meg • Például
• Több felhasználói szál több kernel szálhoz tartozhat • Például
– Windows NT/2000/XP – Linux – Solaris 9 és később
– Solaris 9 előtt – Windows NT/2000 a ThreadFiber csomaggal
67
68
Két szintű modell
Windows 2000 processzus
• Hasonló a sok-sok modellhez, de lehetőség van egy-egy megfeleltetésre is • Például – IRIX – HP-UX – Tru64 Unix
69
Windows 2000 szál
70
Windows 2000 szál állapotok
71
72
Solaris
Solaris
• Felhasználói szintű szálak • Kernel szintű szálak • Könnyű processzusok (Lightweight processes)
73
Unix vs. Solaris
74
Solaris
75
76
Linux
77
