Operační systémy Tomáš Hudec. 6 Komunikace procesů (IPC) Obsah: 6.1 Klasické problémy souběhu Obědvající filosofové

25.1.2014

IOSYS_2013: Komunikace procesů (IPC)

Operační systémy Tomáš Hudec 6 Komunikace procesů (IPC) Obsah: 6.1

Klasické problémy souběhu, 6.1.1 6.1.2 6.1.3 6.1.4

6.2 6.3

Obědvající filosofové, Producenti a konzumenti, Problém spících holičů, Problém pisatelů a čtenářů,

Podpora meziprocesové komunikace operačním systémem, Semafor, 6.3.1 6.3.2 6.3.3 6.3.4 6.3.5

Použití semaforu pro řízení přístupu do kritické sekce, Použití semaforu pro synchronizaci, Binární semafor, Hodnocení semaforu, Použití semaforu pro řešení problémů souběhu, 6.3.5.1 Obědvající filosofové – řešení pomocí semaforů, 6.3.5.2 Producenti a konzumenti – řešení pomocí semaforů, 6.3.5.3 Problém spících holičů – řešení pomocí semaforů,

6.4

Fronta zpráv, 6.4.1 Použití fronty zpráv pro řízení přístupu do kritické sekce, 6.4.2 Použití fronty zpráv pro synchronizaci, 6.4.3 Použití fronty zpráv pro řešení problémů souběhu, 6.4.3.1 Producenti a konzumenti – řešení pomocí fronty zpráv,

6.5

Opakování.

Pro řešení určitých úloh je výhodné použít více kooperujících procesů (případně vláken). Zjednoduší se tím programování (možnost používat blokujících systémových volání), ale klade to nároky na prostředky komunikace takových procesů. Kooperující procesy si potřebují obvykle vyměňovat informace a řídit přístup ke sdíleným prostředkům. Při výměně informací hraje důležitou roli synchronizace. Pokud jeden proces vygeneruje data pro druhý proces, musí se druhý proces s prvním synchronizovat, tedy počkat na platná data. Přitom se nemůže spoléhat na plánovač operačního systému, nelze předpokládat, že plánovač přidělí procesor nejprve prvnímu procesu a pak teprve druhému. Komunikaci a synchronizaci procesů obvykle podporuje operační systém poskytnutím speciálních systémových volání, případně lze nalézt podporu v některých programovacích jazycích.

6.1 Klasické problémy souběhu Zde budou představeny klasické konkurenční problémy, které budou následně řešeny v dalších kapitolách.

6.1.1 Obědvající filosofové Zadání U kulatého stolu s jídlem sedí pět (obecně n) filosofů. Každý buď přemýšlí nebo jí. Na stole je pouze pět vidliček umístěných mezi filosofy. Pro jedení potřebuje každý filosof dvě vidličky.

http://fei-learn.upceucebny.cz/mod/page/view.php?id=5276

1/13

25.1.2014


Původní znění formuloval roku 1965 Edsger Dijkstra jako cvičení na zkoušku studentům. Dnešní podobu formuloval později (1985) Tony Hoare.

Obědvající filosofové

Problém Představímeli si filosofy jako procesy a vidličky jako sdílené prostředky, je třeba navrhnout algoritmus procesů tak, aby: byl řízen přístup ke sdíleným vidličkám a zároveň nedošlo k uváznutí či vyhladovění. Proces filosof i (pro i ∊ {0, …, n − 1}, kde n je počet filosofů): repeat think(); take_fork(i);

// přemýšlení

kritická sekce

// zvednutí vidličky po levé straně

take_fork((i+1) % n); // zvednutí vidličky po pravé straně eat(); // jedení release_fork((i+1) % n); release_fork(i);

// položení vidličky po pravé straně

// položení vidličky po levé straně

forever

Snadno lze zjistit, že bez řízení přístupu k vidličkám může dojít ke zvednutí stejné vidličky dvěma filosofy, což je nepřípustné (vidlička je prostředek s exkluzivním přístupem). Po vyřešení vzájemné výlučnosti prostředků je třeba dále uvažovat i případ, kdy se rozhodnou filosofové současně jíst: Každý ve stejném okamžiku zvedne vidličku po své levé straně a následně bude čekat na uvolnění vidličky po své pravé straně – deadlock.

6.1.2 Producenti a konzumenti Zadání Máme jeden nebo více procesů generujících data (producenti) a několik procesů zpracovávajících vygenerovaná data (konzumenti). Pro snížení prodlev (zvýšení efektivity) je zaveden mezisklad, kam budou producenti data ukládat a odkud si je konzumenti budou vybírat. Problém Přístup do skladu musí být řízen tak, aby producenti ukládali data pouze na volná místa a konzumenti vybírali každý jiná data z obsazených míst. Konzumenti musejí čekat, pokud je sklad prázdný, producenti musejí čekat, pokud je zaplněný. Pro sklad použijeme kruhový buffer reprezentovaný polem o dané kapacitě n položek.


2/13

25.1.2014


Sklad: Kruhový buffer

Sdílená data: buffer[n]; // sklad: pole o kapacitě n položek in = 0; out = 0;

// index následující volné pozice (pro uložení producentem) // index následující obsazené pozice (pro vyzvednutí konzumentem)

count = 0; // počet položek ve skladě

Proces producenta i (pro i ∊ {0, …, p − 1}, kde p je počet producentů): repeat item = produce(); // vyprodukování položky while (count == n); // čekání na uvolnění místa ve skladě

kritická sekce

buffer[in] = item; // uložení položky do skladu na pozici in in = (in + 1) % n; // posunutí indexu na následující místo count++; // zvýšení počtu položek ve skladě forever

Proces konzumenta i (pro i ∊ {0, …, c − 1}, kde c je počet konzumentů): repeat while (count == 0); // čekání na neprázdný sklad

kritická sekce

item = buffer[out]; // vyzvednutí položky ze skladu na pozici out out = (out + 1) % n; count--; consume(item);

// posunutí indexu na následující místo

// snížení počtu položek ve skladě // zpracování položky

forever

Takto navržené algoritmy mají zásadní nedostatky: Producenti mohou současně vložit data na stejnou pozici, konzumenti mohou číst ze stejné pozice (položka bude zpracována vícekrát) a následně některé položky nemusejí být zpracovány vůbec. V neposlední řadě je synchronizace neefektivně řešena aktivním čekáním.

6.1.3 Problém spících holičů Zadání V hypotetickém holičství jsou tři křesla pro stříhání, tři holiči, jedna pokladna, čekárna s pohovkou pro čtyři čekající zákazníky a místo pro další čekající ve stoje. Dovnitř holičství se vejde nejvýše 20 zákazníků, další musejí čekat venku nebo odejít. Na začátku jsou v holičství pouze holiči, kteří spí ve svých křeslech. Přijdeli zákazník, zkontroluje čekárnu, a jeli neprázdná, zůstane v ní čekat. Pokud najde čekárnu prázdnou, zkontroluje křesla. Jsouli křesla obsazena jinými zákazníky, usadí se nově příchozí v čekárně, jinak vzbudí holiče a usadí se do křesla. Zákazník v křesle čeká na dostříhání a pak se odebere k pokladně zaplatit, počká na stvrzenku a odchází.


3/13

25.1.2014


Holič po probuzení novým zákazníkem tohoto ostříhá, následně přijme platbu a vydá stvrzenku. Pak zkontroluje, zda nečeká v čekárně další zákazník. Jeli čekárna neprázdná, vybere holič nejdéle čekajícího zákazníka, usadí jej do křesla a obslouží jej. Nečekáli žádný zákazník, holič se uloží ke spánku do svého křesla.

Problém spících holičů

Problém Na první pohled problém není zřejmý, ale je třeba: hlídat kapacitu holičství, pohovky, křesel a pokladny, řešit synchronizaci při umisťování nového zákazníka do křesla, při dokončení stříhání a při placení. Snadno se může stát, že dva současně příchozí zákazníci se pokusí vzbudit stejného holiče a použít stejné křeslo, případně se usadit na stejné místo v čekárně. Tedy dva procesy současně zjistí volný prostředek a následně se pokusí jej použít. Další problém nastane v případě prázdné čekárny a obsazených křesel: nově příchozí zákazník se po zjištění stavu jde posadit do čekárny, ale než se usadí, proces holiče dokončí obsloužení předchozího zákazníka a stihne zkontrolovat čekárnu ještě před tím, než se nový zákazník usadí. Výsledkem je, že se holič odebere ke spánku, zatímco nový zákazník zbytečně čeká v čekárně.

6.1.4 Problém pisatelů a čtenářů Zadání Do sdílené paměti přistupují procesy, které z ní čtou nebo do ní zapisují data. Data je třeba udržet v konzistentním stavu. Problém Integrita dat může být porušena současným přístupem zapisujícího procesu a jakéhokoliv jiného (zapisujícího nebo čtecího). Čtecí proces může přečíst část dat původních a část nově zapsaných; druhý zapisující proces může přerušit první proces uprostřed jeho zápisu, takže výsledkem budou kombinovaná data druhého a prvního zapisujícího procesu.

6.2 Podpora meziprocesové komunikace operačním systémem Operační systém poskytuje procesům prostředky pro řešení problému kritické sekce, synchronizace i sdílení paměti. Skupina těchto prostředků se označuje jako IPC (InterProcess Communication). Mezi nástroje IPC patří podpora sdílené paměti mezi procesy, semafor – nástroj pro synchronizaci i řízení přístupu do kritické sekce, fronty zpráv – nástroj pro komunikaci procesů, který lze využít i pro synchronizaci a řízení přístupu do kritické sekce.


4/13

25.1.2014


6.3 Semafor Semafor je nástroj IPC pro řešení problémů synchronizace a kritické sekce. Jedná se o datovou strukturu s celočíselným čítačem, frontou procesů a operacemi inicializace, snižování a zvyšování čítače. typedef struct {

// struktura semaforu

int count;

// celočíselný čítač

fifo_t *q;

// fronta (čekajících) procesů

} sem_t; void sem_init(sem_t *s, int v); // inicializace čítače void sem_wait(sem_t *s);

// atomická operace wait

void sem_post(sem_t *s);

// atomická operace signal

K čítači se přistupuje výhradně pomocí atomických operací: Operace init inicializuje čítač nezápornou hodnotou. Operace wait (down) snižuje hodnotu čítače, a jeli výsledek záporný, volající proces je blokován a zařazen do fronty. Operace signal (up) zvyšuje hodnotu čítače, a jeli ve frontě nějaký proces, je vyjmut z fronty a odblokován. void sem_init(sem_t *s, int v) // operace init { s->count = v;

// inicializace čítače

} void sem_wait(sem_t *s)

// operace wait

{ s->count--;

// snížení čítače

if (s->count < 0) {

// je-li čítač záporný,

fifo_put(s->q, self);

// zařaď volající proces do fronty

block_process(self);

// a blokuj volající proces

} } void sem_post(sem_t *s)

// operace signal

{ s->count++;

// zvýšení čítače

if ((p = fifo_get(s->q))) { // je-li ve frontě čekající proces, ready_process(p); // odblokuj jej } }

Nezáporná hodnota čítače udává, kolikrát lze volat operaci wait bez blokování. Absolutní hodnota záporného čítače udává, kolik procesů čeká ve frontě. Všechny operace musejí být prováděny atomicky – v jednom okamžiku smí operaci se semaforem provádět nejvýše jeden proces (vlákno) – zajišťuje operační systém. Pozn.: Programové bloky operací jsou vlastně také kritické sekce a operační systém musí řídit přístup do nich.

6.3.1 Použití semaforu pro řízení přístupu do kritické sekce Čítač sdíleného semaforu se inicializuje na počet procesů smějících současně provádět kód kritické sekce (typicky na jedničku). Ve vstupní sekci se volá operace wait, ve výstupní sekci operace signal. Inicializace: deklarace / inicializace sem_init(&s, 1);

// inicializace na počet procesů smějících současně do KS


5/13

25.1.2014


Kód procesů: repeat

vstupní sekce

sem_wait(&s);

// operace wait

kritická sekce // kód KS

výstupní sekce sem_post(&s);

// operace signal

// kód ZS forever

6.3.2 Použití semaforu pro synchronizaci Máli jeden proces počkat na dokončení akce jiného procesu (například na vypočtení hodnoty), lze pro synchronizaci použít semafor, jehož čítač se inicializuje na nulu. Proces, který má čekat na provedení akce volá operaci wait a proces provádějící akci po ní volá operaci signal. Inicializace: deklarace / inicializace sem_init(&s, 0);

// inicializace na nulu

Kód procesu provádějícího akci, např. vypočtení hodnoty sdílené proměnné x: x = calculate();

// provedení akce

sem_post(&s);

// operace signal

synchronizace – signalizace

Kód procesu čekajícího na dokončení akce: synchronizace – čekání sem_wait(&s); use(x);

// operace wait // použití hodnoty sdílené proměnné x vypočtené jiným procesem

6.3.3 Binární semafor Binární semafor – obvykle označovaný jako mutex (z mutually exclusive) – nemá čítač, ale Booleovskou proměnnou inicializovanou na false. Operace wait a signal se obvykle označují po řadě jako lock a unlock.


6/13

25.1.2014


typedef struct {

// binární semafor, mutex

bool locked; fifo_t *q;

// Booleovská proměnná // fronta (čekajících) procesů

} mutex_t; void mutex_lock(mutex_t *m) { if (m->locked) {

// operace wait

// je-li mutex již zamčen (jiným procesem)

fifo_put(m->q, self);

// zařaď volající proces do fronty

block_process(self);

// a blokuj volající proces

} else { m->locked = true;

// jinak zamkni mutex

} } void mutex_unlock(mutex_t *m) { // operace signal if ((p = fifo_get(m->q))) { // je-li ve frontě čekající proces, ready_process(p);

// odblokuj jej

} else { m->locked = false; // jinak odemkni mutex } }

6.3.4 Hodnocení semaforu Semafor je výkonný nástroj vhodný pro řešení řízení přístupu do kritické sekce (vzájemného vylučování) i synchronizace. Jeho použití je snadné a efektivní – nepoužívá se aktivního čekání, čekající procesy jsou v blokovaném stavu a nespotřebovávají tak zbytečně procesorový čas. Řešení složitějších problémů s mnoha procesy a více semafory mohou být obtížnější na porozumění, neboť operace semaforu jsou volány z různých procesů (či vláken). Takové skupiny procesů se obtížně ladí a chybné použití operace se semaforem může způsobit problémy celé skupině procesů. Jediné volání operace wait na nesprávném místě může způsobit uváznutí (deadlock), jediné volání signal na nesprávném místě zase vede k porušení konzistence dat.

6.3.5 Použití semaforu pro řešení problémů souběhu 6.3.5.1 Obědvající filosofové – řešení pomocí semaforů Definice problému – vizte výše. Pro řízení přístupu ke sdíleným vidličkám (kritické sekce) lze použít semafory – pro každou vidličku jeden – inicializované na jedničku (v každém okamžiku smí vidličku používat nejvýše jeden filosof): deklarace / inicializace sem_t fork[n]; for (i = 0; i < n; ++i)

// deklarace pole semaforů pro vidličky // čítač každého semaforu

sem_init(&fork[i], 1); // inicializujeme na jedničku

Proces filosof i (pro i ∊ {0, …, n − 1}, kde n je počet filosofů):


7/13

25.1.2014


repeat think();

// přemýšlení

sem_wait(&fork[i]);

vstupní sekce

// exkluzivní alokace vidličky po levé straně

sem_wait(&fork[(i+1) % n]); // exkluzivní alokace vidličky po pravé straně

kritická sekce take_fork(i);


take_fork((i+1) % n); eat();

// zvednutí vidličky po pravé straně

// jedení

release_fork((i+1) % n); release_fork(i);



výstupní sekce sem_post(&fork[(i+1) % n]); // uvolnění vidličky po pravé straně sem_post(&fork[i]);

// uvolnění vidličky po levé straně

forever

Výše uvedené řešení však nebude funkční v případě, že se ve stejný okamžik rozhodnou všichni filosofové současně najíst: Každý ve stejném okamžiku alokuje a zvedne vidličku po své levé straně a následně bude čekat na uvolnění vidličky po své pravé straně, k čemuž nemůže dojít – deadlock. Jedním z řešení je přidat ještě jeden semafor, který nedovolí zvednout vidličku všem, takže alespoň jedna bude vždy volná pro některého z filosofů, který se nají a následně uvolní vidličky dalším. deklarace / inicializace sem_t waiter;

// deklarace semaforu omezujícího počet současných jedlíků

sem_init(&waiter, n − 1);

// nejvýše smí zahájit jedení n − 1 filosofů

Proces filosof i (pro i ∊ {0, …, n − 1}, kde n je počet filosofů): repeat think();

// přemýšlení

sem_wait(&waiter);

// omezení počtu současných jedlíků

sem_wait(&fork[i]);

// exkluzivní alokace vidličky po levé straně

vstupní sekce 1 vstupní sekce 2

sem_wait(&fork[(i+1) % n]); // exkluzivní alokace vidličky po pravé straně

kritická sekce take_fork(i);


take_fork((i+1) % n); // zvednutí vidličky po pravé straně eat(); // jedení release_fork((i+1) % n); release_fork(i);



výstupní sekce 2 sem_post(&fork[(i+1) % n]); // uvolnění vidličky po pravé straně sem_post(&fork[i]); // uvolnění vidličky po levé straně

výstupní sekce 1 sem_post(&waiter);

// konec omezení počtu současných jedlíků

forever

6.3.5.2 Producenti a konzumenti – řešení pomocí semaforů Definice problému – vizte výše. Pro výlučný přístup do skladu lze použít mutex, pro synchronizaci při prázdném a plném skladu semafory, jejichž použití navíc odstraní aktivní čekání. Neúplné řešení: Sdílená data:


8/13

25.1.2014


deklarace / inicializace buffer[n];

// sklad: pole o kapacitě n položek

in = 0;

// index následující volné pozice (pro uložení producentem)

out = 0;

// index následující obsazené pozice (pro vyzvednutí konzumentem)

sem_t mutex;

// řízení vzájemně výlučného přístupu do skladu

sem_t item_count;

// synchronizace při vložení položky do skladu

sem_init(&mutex, 1);

// do skladu smí pouze jeden proces

sem_init(&item_count, 0);

// na začátku je sklad prázdný

Proces producenta i (pro i ∊ {0, …, p − 1}, kde p je počet producentů): repeat item = produce();

// vyprodukování položky

sem_wait(&mutex);

// exkluzivní přístup do skladu

vstupní sekce kritická sekce

buffer[in] = item; // uložení položky do skladu na pozici in in = (in + 1) % n; // posunutí indexu na následující místo

výstupní sekce sem_post(&mutex);

// konec exkluzivního přístupu do skladu

synchronizace – signalizace sem_post(&item_count); // signalizace neprázdného skladu forever

Proces konzumenta i (pro i ∊ {0, …, c − 1}, kde c je počet konzumentů): repeat

synchronizace – čekání

sem_wait(&item_count); // čekání na neprázdný sklad

vstupní sekce sem_wait(&mutex);

// exkluzivní přístup do skladu

kritická sekce item = buffer[out]; // vyzvednutí položky ze skladu na pozici out out = (out + 1) % n;

// posunutí indexu na následující místo

výstupní sekce sem_post(&mutex);

// konec exkluzivního přístupu do skladu

consume(item);

// zpracování položky

forever

Zamyslete se nad uvedeným neúplným řešením a dokončete je.

6.3.5.3 Problém spících holičů – řešení pomocí semaforů Definice problému – vizte výše. Pro synchronizaci se inicializují semafory:


9/13

25.1.2014


deklarace / inicializace sem_init(max_capacity, 20); // celková kapacita holičství sem_init(sofa, 4);

// počet volných míst na pohovce

sem_init(chair, 3);

// počet křesel

sem_init(cash_register, 1); // omezení přístupu k pokladně sem_init(cust_ready, 0);

// připravenost zákazníka ke stříhání

for (i = 0; i < chairs; i++) sem_init(finished[i], 0);

// dokončení stříhání holičem

sem_init(payment, 0);

// synchronizace platby zákazníka s holičem

sem_init(receipt, 0);

// předání účtenky

Proces zákazníka: řešení sem_wait(max_capacity);

// čekání venku, pokud se nevejde dovnitř

enter_barbershop();

// vstup do holičství

sem_wait(sofa);

// kontrola místa na pohovce

sit_on_sofa();

// posadí se na pohovku

sem_wait(chair); get_up();

// kontrola volného křesla ke stříhání // uvolnění pohovky

sem_post(sofa);

// signalizace volného místa na pohovce

ch = sit_in_chair();

// posazení zákazníka do křesla ch

sem_post(cust_ready);

// signalizace připravenosti ke stříhání (vzbuzení holiče)

sem_wait(finished[ch]);

// čekání na dokončení stříhání

leave_chair();

// opuštění křesla

sem_post(chair);

// signalizace volného křesla

sem_wait(cash_register); pay();

// čekání na uvolnění pokladny

// přesun k pokladně a platba

sem_post(payment);

// signalizace platby

sem_wait(receipt);

// čekání na převzetí platby a přijetí účtenky

sem_post(cash_register); // uvolnění místa u pokladny exit_shop(); // opuštění holičství sem_post(max_capacity);

// signalizace volné kapacity v holičství

Proces holiče: repeat

řešení

sem_wait(cust_ready);

// čekání na zákazníka (holič spí)

ch = go_to_chair(); // přesun k zákazníkovi cut_hair();

// stříhání

sem_post(finished[ch]); // signalizace dokončení stříhání go_to_cash_register(); // přesun k pokladně sem_wait(payment); // čekání na platbu accept_pay();

// přijetí platby

sem_post(receipt); // vydání účtenky forever

Výše uvedený návrh není úplný: chybí řešení akceptace platby správným holičem, pokud je současně dokončena obsluha více zákazníků. Přesto je vidět, že celý problém je poměrně složitý a je třeba důkladného rozboru možných situací.

6.4 Fronta zpráv Pro podporu komunikace procesů může operační systém poskytovat fronty zpráv. Jedná se v podstatě o prostředek k předávání


10/13

25.1.2014


dat mezi procesy, přičemž se používají dvě základní operace: send – zasílá zprávu do fronty, receive – přijímá zprávu z fronty. Typická implementace je taková, že volání send je neblokující, jeli ve frontě místo, a blokující v případě plné kapacity fronty. Volání receive je neblokující, jeli ve frontě dostupná zpráva, a blokující, jeli fronta prázdná. Blokování končí, jakmile je do fronty zaslána zpráva. Pro stanovení kapacity fronty se ještě používá inicializační volání. Inicializace a předávání zpráv může vypadat např. takto: mq_t mq;

// deklarace identifikátoru fronty zpráv

mq_init(mq, 5);

// nastavení kapacity fronty zpráv

mq_send(mq, msg);

// zaslání zprávy msg do fronty mq

mq_receive(mq, &msg);

// přijetí zprávy z fronty mq

Operační systém zajišťuje výlučný přístup k frontě zpráv, takže ji lze využít pro řešení synchronizace i řízení přístupu do kritické sekce.

6.4.1 Použití fronty zpráv pro řízení přístupu do kritické sekce Do fronty zpráv zašleme tolik inicializačních zpráv, kolik procesů smí současně provádět kód kritické sekce (typicky jednu). Ve vstupní sekci se volá operace receive, ve výstupní sekci operace send. Inicializace: deklarace / inicializace mq_send(mq, "go");

// zaslání inicializační zprávy do fronty

Kód procesů: repeat

vstupní sekce

mq_receive(mq, &msg);

// operace receive

kritická sekce // kód KS

výstupní sekce mq_send(mq, msg);

// operace send

// kód ZS forever

První proces přijme inicializační zprávu a vstoupí do kritické sekce. Každý další je na volání receive blokován, dokud není kritická sekce zase uvolněná zasláním zprávy do fronty.

6.4.2 Použití fronty zpráv pro synchronizaci Inicializace: na začátku je fronta zpráv prázdná. Kód procesu provádějícího akci, např. vypočtení hodnoty sdílené proměnné x: x = calculate();

// provedení akce


mq_send(sync, "done"); // operace send, signalizace dokončení výpočtu


11/13

25.1.2014


Kód procesu čekajícího na dokončení akce: synchronizace – čekání mq_receive(sync, &msg); // operace receive, čekání na dokončení výpočtu use(x);

// použití hodnoty sdílené proměnné x vypočtené jiným procesem

6.4.3 Použití fronty zpráv pro řešení problémů souběhu Řešení mnohých problémů pomocí fronty zpráv je v mnohém analogické použití semaforů. Pro inicializaci je třeba zaslat do fronty tolik inicializačních zpráv, na kolik je inicializován semafor, a všude nahradit volání wait voláním receive a volání signal voláním send. Některé problémy lze však pomocí fronty zpráv řešit elegantněji a jednodušeji.

6.4.3.1 Producenti a konzumenti – řešení pomocí fronty zpráv Definice problému – vizte výše. Jako sklad lze použít přímo frontu zpráv. Je třeba inicializovat maximální počet položek ve frontě na kapacitu skladu a použít operace send pro vkládání do skladu a receive pro vybírání ze skladu. Výlučný přístup k frontě zpráv (skladu) je automaticky zajištěn operačním systémem. Při prázdném skladě bude konzument automaticky blokován při použití receive a stejně tak bude blokován producent po zaplnění kapacity při volání send. Inicializace: deklarace / inicializace mq_t storage;

// deklarace identifikátoru fronty zpráv

mq_init(storage, n);

// nastavení kapacity fronty zpráv (skladu) na n položek

Proces producenta i (pro i ∊ {0, …, p − 1}, kde p je počet producentů): repeat item = produce(); mq_send(storage, item);

// vyprodukování položky


// zaslání položky do skladu

forever

Proces konzumenta i (pro i ∊ {0, …, c − 1}, kde c je počet konzumentů): repeat

synchronizace – čekání

mq_receive(storage, &item); // vyzvednutí položky ze skladu consume(item);

// zpracování položky

forever

Jak je vidět, řešení problému svázaných producentů a konzumentů pomocí fronty zpráv je triviální.

6.5 Opakování 1. 2. 3. 4.

Definujte semafor a popište operace na něm používané. Definujte frontu zpráv a popište operace na ní používané včetně informace, kdy blokují. Popište řešení řízení přístupu do kritické sekce pomocí semaforu. Popište řešení řízení přístupu do kritické sekce pomocí fronty zpráv.


12/13

25.1.2014

5. 6. 7. 8. 9.


Řešte synchronizaci procesů pomocí semaforu. Řešte synchronizaci procesů pomocí fronty zpráv. Popište řešení problému obědvajících filosofů pomocí semaforů. Popište řešení problému svázaných producentů a konzumentů pomocí semaforů. Popište řešení problému svázaných producentů a konzumentů pomocí fronty zpráv. Naposledy změněno: Pondělí, 7. říjen 2013, 15.17


13/13

Operační systémy Tomáš Hudec. 6 Komunikace procesů (IPC) Obsah: 6.1 Klasické problémy souběhu Obědvající filosofové

Recommend Documents