Elosztott rendszerek NGM_IN005_1 Konkurrens folyamatok
Folyamat koncepció Adatok (információ reprezetáció) M!veletek (input->output) Számítás (algoritmus) Program (formális nyelv) Folyamat (végrehajtás alatti számítás) konkurrens folyamatok független (privát adatok) együtt m!köd" (közös adatok) 2
Többszálú folyamatok Implementációs absztrakciós szint Egy programon (op. r. folyamaton) belüli tevékenységek párhuzamosítása közös er"források ütemezés 3
Op. rendszer struktúrák Applications
Monolit, struktúrálatlan Rétegszerkezetek
File storage Proc. mngnt.
I/O
Dev. driver
Memory mngnt.
Dev. driver
Network services
Dev. driver HW interface
védelmi domének
Applications
OS services
Mikrokernel OR Communication services Dev. driver
Dev. driver
Proc. mngnt.
Microkernel
Memory mngnt. Dev. driver
HW interface
4
Eszközkezelés Interfész Device driver (OR) Device spec. szoftver interfész Device hardver interfész Device interfész input puffer output puffer kontrol regiszter státusz regiszter 5
Eszközkezelés (folyt.) Pollozás Interrupt kezelés hardver támogatás interrupt kiszolgáló rutin interrupt vektor környezetváltás prioritás
IR vector
Program
IR vector
IR serv. routine
Program
IR serv. routine
Saved PC
Memory
PC
Saved status reg.
Memory
PC
Status reg.
Status reg. Processor
Processor
6
Eszközkezelés (folyt.) DMA cycle stealing Memory-mapped I/O allokált memóriacímek Timerek programozhatók interrupt felhasználás: futásid" (CPU használat), riasztások,periódikus tevékenységek 7
Több processzoros rendszerek Interrupt kezelés perifériák processzorokhoz kötötten perifériák bármely processzor által vezérelhet"k osztott memória, DMA periféria alrendszer inter-processzor interrupt 8
Pufferek és szinkronizáció I/O modulok között adatpufferek különböz" szinteken futó adatcserél" folyamatok szinkronizációja pufferelési stratégia Szinkron I/O Aszinkron I/O 9
Processzek és processzorok Processzek használata aszinkron esemény feldogozáskor Több processz, mint fizikai processzor processzorok megosztása (virtuális processzorok) interrupt mechanizmus processz menedzsment funkciók Ütemezés nem-preemptív preemptív 10
Multi-processz rendszer (pl.) IRQ
Dev A ISR of Dev A
Wait()
Proc A Wait() Proc B ISR of Dev B Dev B
IRQ
11
Processz állapotok RUNNING
Wait primitív végrehajtása RUNNING
egy processzoron fut RUNNABLE
BLOCKED Ütemezve végrehajtásra Esemény bekövetkezett
Futási jog elvéve RUNNABLE
elkezdhet futni egy processzoron BLOCKED várakozás valamilyen eseméyre 12
Versenyhelyzetek Értesítés esemény bekövetkeztér"l Signal primitív (wake-up waiting) Események relatív id"zítése befolyásolja a következményt pl.: megszakítás bekövetkezte wait kiadása közben Wait és Signal metódusoknak oszthatatlannak (atominak) kell lennie 13
Ütemezés Processz kiválasztása végrehajtásra Ütemezési algoritmus hatékonyság optimális er"forrás kihasználás overhead csökkentése speciálisan kialakított adatszerkezetek speciális helyzetek unary scheduling binary scheduling 14
Folyamatok viselkedése Prioritás kezelés statikus, fix prioritás OR funkciók, real-time rendszerek változó aktivitás, multi user rendszerek dinamikusan meghatározott prioritás id"szeletek különböz" prioritású várakozósorok 15
Folyamatok viselkedése (folyt.) Prioritások rendszer folyamatok (statikus) kritikus er"forráson blokkolt folyamatok kevésbbé kritikus er"forrásokon blokkolt foly. I/O tevékenységet nem folytató, id" szeletet elhasznált foly. 16
Valós idej! ütemezés Valós idej! tevékenységek periódikus (ciklikus) spóradikus (nem meghatározott idej! fellépés) Határid"k betartása periódikus ütemezés (proc. frekvencia minimuma) ráta monoton ütemezés (frekvencia függ" prioritás) legkorábbi határidej!, legkisebb holtidej! 17
Valós idej! ütemezés (pl.) WorkA
SlackA
WorkB
W A
WB
SlackB
WorkA
EDF
WorkA
WorkB
LSF
DB
DA
18
OR folyamatok Felhasználói folyamatok privilégizált és nem privilégizált mód Device kezel" folyamatok Memória kezel" folyamatok Folyamat kezel" (ütemez") nem valósíthat meg folyamatként 19
Többszálúság implementálása Végrehajtási egység Szál Könny! súlyú folyamat Er"forrás allokálási egység Taszk Folyamat Címtér User és kernel thread ütemezhet" kernel thread -> többszálú folyamatok Nehéz súlyú folyamatok 20
Többszálúság implementálása (folyt.)
one program one proc.
one program one proc.
one program user threads
one program user threads
one program user threads
one program user threads
Language runtime system
Language runtime system
Language runtime system
Language runtime system
Language runtime system
Language runtime system Kernel threads
OS kernel
OS kernel
OS kernel
Szekvenciális pr. nyelv
Konk. pr. nyelv, OR támogatás nélkül
Konk. pr. nyelv, OR támogatással 21
Konkurrencia megoldások Szekvenciális nyelv nincs támogatás elkülönített tevékenységek kezelésére felhasználói kódnak kell menedzselni az állapotváltásokat nem lehet azonnal reagálni eseményekre 22
Konkurrencia megoldások (folyt.) Nyelv korutinokkal független alprogramok egy programon belül runtime támogatás coroutine-create, kill, call, suspend, resume aktív korutin lista de explicit kontrol, (ütemezés, konzisztencia meg"rzése) 23
Konkurrencia megoldások (folyt.)
Nyelv folyamatokkal, szálakkal kontrol, ütemezés a runtime rendszerben kernel threadek
24
Konkurrencia megoldások (folyt.) Megoldandó problémák blokkoló rendszerhívások eseménykezelés (pollozás, interrupt) kooperatív, barátságosan viselked" folyamatok preemptív ütemezés esetén adat konzisztencia átkapcsolási overhead 25
Java threads Thread osztály, Runnable interfész run és start metódus ütemezés VM és hoszt OR függ" sleep InterruptedException join setPriority szinkronizációs eszközök 26
Processz-interakció Folyamatok közös adatokkal teljesen közös címtér külön címtér szegmentált memóriakezelés közös kód szegmens elosztott folyamatok kommunikáció közös adat szegmens 27
Processz-interakció (folyt.) Szinkronizálási igények egymás közötti feltétel szinkronizálás szinkronizálás kölcsönös kizárást kívánó er"forrásokon Interakció típusok one-to-one any-to-one one-to-many any-to-(one of) many many-to-many (shared data) 28
Granularitás Konkurrens tevékenységek felbontása folyamat, taszk, m!velet dekompozíció tevékenységek száma interakció frekvenciája közös adatok hozzáférése védelmi kívánalmak blokkoló rendszerhívások 29
Granularitás (folyt.) Atomi tevékenység oszthatatlan utasítás szekvencia (átmeneti állapotok nem láthatók) fine-grained: egy gépi utasítás coarse-grained: oszthatatlannak látszó fine-grained tevékenységek sorozata 30
Alacsonyszint! szinkronizáció Közös írható adatterületek védelme Kritikus szakasz megvalósítása One-to-one interakciónál általánosabb megoldás kell Eszközkezelés Wait() és Signal() primitívjei nem alkalmasak 31
Kritikus régiók Kölcsönös kizárás biztosítása közös adatterületen végzett nem atomi blokkok számára Proc. A
Critical region
Proc. B
Data structure
Critical region
32
Hardver megoldások Oszthatatlan hardver m!velet "r flag ellen"rzésére és beállítására Test-and-set compare-and-swap
Proc. A
Proc. B
TAS
TAS
Data structure
Critical region
Critical region
load linked/store conditional 33
Szemaforok A
Dijkstra Szemafor objektum
1
B
C
semWait()
0 semWait() 0
semWait() semSignal() érték várakozósor
B
semWait()
0 B
semSignal() C
0 B 0
semSignal()
semSignal()
1
34
Szemaforok (folyt.) Szamaforok korlátai felhasználásuk nem automatikus, programozási hibák blokkolás nélkül nem lehet tesztelni nincs több szemaforra vonatkozó együttes semWait() nincs timeout 35