Medziprocesorova komunikacia Flashcards
Z akych dovodov posobia procesy na seba?
- neumyselne - vykonavaju sa bez ohladu na ine procesy, sutazia o prostriedky
- nepriamo - vedia o existencii inych procesov, ale nevedia nic viac, napriklad pouzivaju rovnaky subor
- umyselne - spolupracuju, komunikuju
Co je komunikacia medzi procesmi?
Vymena dat
Co je synchronizacia vykonavania procesov?
treba dodrzat poradie vykonania procesov
Co je subeh?
Procesy pristupujúce do spoločnej pamäti sa môžu vykonávať súbežne, respektíve v ľubovoľnom poradí.
Kedy moze nastat prerusenie procesu?
Medzi dvoma instrukciami, pouzitie instrukcie je atomicke
Aky je rozdiel medzi CISC a RISC pri incremente a++?
V CISC je to atomicka operacia inc a, v RISC treba po jednom loadnut, inc a ulozit, teda sa moze preplanovat hocikedy medzi
Ako nazyvame situaciu, ked viacero procesov pristupuje k rovnakej premennej a vysledok zavisi od poradia?
subeh - race condition
Preco race condition?
Procesy sutazia o pristup a vysledok zavisi od toho kto bude prvy
Co je vzajomne vylucovanie?
Aby k spolocnemu prostriedku pristupoval v kazdom case najviac jeden z procesov
Ako sa nazyva usek programu kde sa vykonava pristup k spolocnemu prostriedku?
kriticka oblast
Program v kritickej oblasti smie byt teda vykonavany kolko procesmi?
jednym
Riesenia mut. ex. vieme rozdelit na ..?
cisto programove a hardverove
Ake su hw implementacie mut ex?
zakazanie preruseni, specialne instrukcie a pod
Aka je nevyhoda zakazania prerusenia?
neobsluhuju sa chyby od I/O
v pripade chyby sa zasekne cely system
kedy sa pouziva zakazanie prerusenia?
v jadre na kratke casy
Co je problem ked ma system viac CPU?
zakazanie preruseni na jednom z nich nestaci
Aky je problem pri CISC a viac CPU pri atomickej operacii inc?
subezne moze pristupit k pamati proces na inom procesore
Ake je hw riesenie pri viac CPU?
uzamknutie zbernice signalom lock ako prefix instrukcie
Ake je riesenie “spolocny zamok”?
spolocna premenna lock
enterCS: while(lock); lock = TRUE
leaveCS: lock = FALSE
Aky je problem pre spolocny zamok?
ak bude proces preplanovany tesne po tom co ukonci while a pred tym co nastavi LOCK na true, teda tam vedia vojst oba procesy
Ake je riesenie “striedanie”?
spolocna premenna urcuje kto smie vojst, pred vstupom proces pocka kym bude na rade
enum {P, Q} turn = P;
EnterCS_P() { while(turn != P); }
LeaveCS_P() { turn = Q; }
pre Q rovnako
Preco je zle riesenie “striedanie”?
Vynucujeme striedanie, teda ak jeden treba castejsie, tak to zbytocne spomaluje
Aka je druha podmienka riesenia mut ex?
Proces ktorý sa \vykonáva mimo kritickej oblasti nesmie brániť iným vstúpiť do nej.
Ake je riesenie “zamok pre kazdy proces”?
kazdy proces ma svoju premennu ktora indikuje potrebu vstupit do kritickej oblasti, pred vstupom ju nastavi na true a pocka ak aj druhy bude chciet vojst
inP, inQ = FALSE
EnterCS_P() { inP = TRUE; while(inQ); }
LeaveCS_P() { inP = FALSE; }
Aky je problem riesenia zamok pre kazdy proces?
preplanovanie po nastaveni na true, nastane deadlock a system sa zasekne, nikto to nezmeni na false
Ake je riesenie “prerusenie cakania”?
Kazdy proces ma premennu ktora indikuje vstup do crit. section. Nastavi na 1, ak ale aj druhy ma 1, tak nastavi na 0 a pokus zopakuje, inak break, cele to bezi vo while(1)
Aky je problem riesenia prerusenie cakania?
livelock - navzajom sa uprednostnuju a nikto tam nevstupi, ak sa preplanuju vzdy po nastaveni premennej na true
Ake su 4 podmienky riesenia synch. problemu mut ex?
1) V kritickej oblasti sa smie vykonávať v každom čase najviac jeden proces.
2) Proces ktorý sa vykonáva mimo kritickej oblasti nesmie brániť iným vstúpiť do nej.
3) Rozhodnutie o vstupe musí prísť v konečnom čase.
4) Procesy nemôžu pri vstupe do kritickej oblasti predpokladať nič
o vzájomnom časovaní (plánovaní).
Aké je petersonovo riešenie?
da sa rozsirit aj na N > 2 procesov mame premenne int inP = FALSE, inQ = FALSE; enum {P, Q} last = P; enter je ze inP = TRUE; last = P; while(inQ && last == P);
Ako znacime instrukciu ktora chceme aby sa vykonala atomicky?
«_space;…»_space;
Co je instrukcia TSL?
Test and set lock
nastavi lock na 1 a vrati predosliu hodnotu locku
Co je instrukcia XCHG?
Exchange
vymeni hodnoty parametra a a lock
Co je instrukcia FA?
Fetch and add
prida k hodnote premennej a vrati staru hodnotu
Ako vieme spravit V/V protokol s pouzitim TSL?
int lock = FALSE;
EnterCS() { while (TS(&lock)); }
LeaveCS() { lock = FALSE; }
Co je spinlock?
Zamok implementovany pomocou cakania v tesnej slucke
Co je ticket algoritmus?
Algoritmus pre mut ex N procesov inspirovany systemom cakania na poradie
Kazdy proces dostane ticket, planovac inkrementuje aktualny tiket a ked ma proces svoj tiket tak je na rade
Co je problem ticket alg?
ak zlyha proces tak ostatne cakaju navzdy
Aka je kriticka oblast ticket alg?
Pridelenie tiketu procesu - je tam inkrement takze 2 procesy mozu dostat rovnake cislo
Co je bakery algoritmus?
ako ticket algoritmus, ale nepotrebuje specialnu instrukciu, ak maju 2 rovnake cislo tak sa rozhodne o ich poradi napr podla PID
Aka je zlozitost ticket alg?
O(1)
Aka je zlozitost bakery alg?
O(n)
Co je obsadzujuce cakanie?
Procesor caka v tvare while(lock) - nevykonava ziadnu uzitocnu pracu
Aka je nevyhoda obsadzujuceho cakania navyse v multiprocesorovych systemoch?
zahlcovanie zbernice citanim jednej premennej dokola
Ake je riesenie obsadzujuceho cakania?
Napr signaly a wait
Co je semafor?
Vseobecny synchronizacny mechanizmus, v podstate cele nezaporne cislo
Aka je hlavna vyhoda semaforu?
Odstranuje obsadzujuce cakanie, proces bude v blokovanom stave
Aka je “nevyhoda” semaforu?
Treba podporu priamo od OS
Ake metody su pre semafor?
init - nastavi hodnotu na cislo
wait - ak je hodnota viac ako nula dekrementuje ju inak sa uspi a caka
signal - ak je rad cakajucich neprazdny tak sa vyberie jeden a zobudi sa, inak inkrementuje cislo
Obsahuje aj semafor kriticku oblast?
Ano, napr to inkrementovanie
Co teda potrebujeme pre implementaciu semaforu aby sme sa zbavili kritickej oblasti?
synchronizacny mechanizmus nizsej urovne
Ako vieme implementovat uspanie a zobudenie procesu?
Signalmi
Ake pozname varianty semaforu?
Vseobecny semafor
Binarny semafor - mutex
Ako znie invariant semaforu?
pW - pS <= I kde pW je pocet vykonanych write a pS signal, I je hodnota
Na co vieme vyuzit napr inu hodnotu semaforu ako 1?
Ak R procesov vie vyuzivat prostriedok sucasne tak nastavime na R
Na co nam je semafor s hodnotou 0?
Na synchronizaciu poradia. Cakajuci zavola wait, signal zavola predosly az po vykonani a dany co volal wait teda moze bezat
Co je precedencny graf?
Poradie vykonania procesov
Ake 2 druhy vykonavania pozname?
Sekvencne, paralelne
Na co nam je buffer?
Vyrovnava rozne rychlosti zapisu a citania
Kedy v bufferi potrebujeme synchronizaciu?
ak chce niekto zapisat a je plno, alebo chce citat a je prazdno
Co je kruhovy buffer?
Efektivne znovupouzitie uvolneneho miesta v bufferi