Problém spícího holiče. Problémy se synchronizací OS
Velikost: px
Začít zobrazení ze stránky:
přepis
1 Klasické problémy se synchronizací, část 2 Čtenáři a spisovatelé Výrobci a spotřebitelé Spící kadeřník
2 Čtenáři a zapisovači Vzhledem k určité oblasti sdílené paměti Tato datová struktura může být přístupná libovolnému počtu "čtenářů" a libovolnému počtu "zapisovatelů" Současně lze přistupovat k více čtenářům, zapisovače nejsou v daný okamžik povoleny Pouze jeden spisovatel je přístupný, ostatní autoři a čtenáři musí počkat
3 Řešení 1 Řešení 1: Čtenář může vstoupit do kritické sekce, pokud zde nejsou žádní autoři Toto řešení je nespravedlivé, protože zvýhodňuje čtenáře Velký tok požadavků od čtenářů může mít za následek, že pisatel nikdy nezíská přístup ke kritické části: „hladovění“ situace (hladovění)
4 Řešení 2 Dejme přednost zapisovatelům, to znamená, že čtenář není zahrnut do kritické sekce, pokud existuje alespoň jeden čekající zapisovatel pthread_mutex_t m; pthread_cond_t cw, cr; int rcnt, wcnt; int wwcnt; // počet čekajících zapisovatelů void rdlock() ( pthread_mutex_lock(&m); while (wcnt > 0 wwcnt > 0) pthread_cont_wait(&cr, &m); rcnt++; pthread_mutex_unlock(&m); )
5 Řešení 2 void wrlock() ( pthread_mutex_lock(&m); while (wcnt > 0 rcnt > 0) ( wwcnt++; pthread_cond_wait(&cw, &m); wwcnt--; ) wcnt++; pthread_mutex_unlock(&m)); () v //)
6 Řešení 2 Toto řešení upřednostňuje autory a je také nespravedlivé Možné hladovění čtenářů Třetí řešení: nedávejte nikomu přednost, použijte mutex
7 Problém producent-spotřebitel Vzhledem k vyrovnávací paměti pevné velikosti (N), která drží frontu. Výrobci přidávají prvky na konec fronty, pokud je vyrovnávací paměť plná, výrobci jdou spát Spotřebitelé odebírají prvky z přední části fronty, pokud je vyrovnávací paměť prázdná, spotřebitelé jdou spát
8 Producent-spotřebitelé int buf[n]; int hlava, ocas; pthread_mutex_tm; pthread_cond_tcc; // spotřebitelský condvar pthread_cond_t pc; // producent condvar void put(int x) ( pthread_mutex_lock(&m); while ((ocas + 1) % N == hlava) pthread_cond_wait(&pc, &m); buf = x; ocas = (ocas + 1) % N; if ((hlava + 1) % N == ocas) pthread_cond_signal(&cc); pthread_mutex_unlock(&m); )
9 Spotřebitelští výrobci int get(void) ( int val; pthread_mutex_lock(&m); while (head == ocas) pthread_cond_wait(&cc, &m); val = buf; if ((ocas + 1) % N == hlava) pthread_cond_signal ( &pc); head = (head + 1) % N; pthread_mutex_unlock(&m); návratová hodnota; )
10 Spací holič V holičství je jedno stříhací křeslo a N židlí pro čekající návštěvníky Pokud zde nejsou žádné návštěvy, holič spí čekací židli Pokud jsou všechna místa obsazena, návštěvník odchází
11 Spící holič pthread_mutex_t m; pthread_t chair_thr; // koho jsme vyřízli int wait_cnt; // kolik návštěvníků čeká pthread_cond_t bc; // holič condvar pthread_cond_t cc; // spotřebitelský condvar void barber(void) ( while (1) ( pthread_mutex_lock(&m); while (chair_thr == NULL && wait_cnt == 0) pthread_cond_wait(&bc, &m); pthread_mutex_unlock(&m); make_haircut(x); pthreadlock &m); chair_thr = NULL; pthread_cond_signal(&cc); pthread_mutex_unlock(&m); ))
12 Sleeping Barber int Consumer(void) ( pthread_mutex_lock(&m); if (chair_thr!= NULL && wait_cnt == N) ( // bez mezery, ponechání pthread_mutex_unlock(&m); return -1; ) while (chair_thr!= NULL) ( wait_cnt++; pthread_cond_wait(&cc, &m); wait_cnt--; ) chair_thr = pthread_self(); pthread_cond_signal(&bc); pthread_mutex_unlock(&m); get_haircut(); return 0; )
13 Detekce uváznutí Proces 1: lock(&a); zámek(&b); Proces 2: lock(&b); zámek(&a); Proces 1 A Proces 2 B Oblouk zabraného zdroje od procesu ke zdroji Čekající oblouk zdroje od zdroje k procesu Pokud je v grafu cyklus, systém je ve stavu uváznutí
14 Process group Process group procesy, které jsou sloučeny k provedení úkolu (například k provedení pipeline) Process group se chová jako jedna entita při příjmu signálů, zejména z terminálu (např. Ctrl-C SIGINT) Při práci s terminálem (procesy hlavní a pozadí skupiny) ID skupiny procesů je ID jednoho z procesů ve skupině
15 Vytvořte skupinu #include
16 Vytvoření skupiny, speciální případy setpgid(0, 0); Proces vytvoří novou skupinu procesů a umístí se do ní (spustí se v potomkovi) setpgid(0, pgid); Proces se umístí do existující skupiny procesů (v potomkovi) setpgid(pid, pid); Proces vytvoří novou skupinu procesů a vloží do ní zadaný proces (do otce)
17 Skupiny procesů a terminál Terminál může mít jednu hlavní skupinu procesů a libovolný počet skupin procesů na pozadí Hlavní skupina procesů: Má právo číst z terminálu (pokus o čtení pro skupinu procesů na pozadí způsobí pozastavení procesu skupiny na pozadí) Přijímá signály SIGINT, SIGQUIT z terminálu
18 Primární terminálová skupina procesů pid_t tcgetpgrp(int fd); int tcsetpgrp(int fd, pid_t pgrp); fd libovolný popisovač souboru terminálu (např. 0 standardní vstup) tcsetpgrp nastavuje hlavní skupinu procesů terminálu
19 Příklad: ls -l wc -l int main(void) ( pipe(fds); if (!(pid1 = fork())) ( setpgid(0, 0); tcsetpgrp(0, getpid()); dup2( fds, 1); close(fds); close(fds); execlp("/bin/ls", "/bin/ls", "-l", NULL); ) setpgid(pid1, pid1); tcsetpgrp(0 , pid1); if (!(pid2 = fork())) ( setpgid(0, pid1); dup2(fds, 0); close(fds); close(fds); execlp("/usr/bin/wc" , "/usr/bin/wc", "-l", NULL); ) setpgid(pid2, pid1); close(fds); close(fds); wait(0); wait(0); tcsetpgrp(0, getpgid(0)); return 0; )
20 procesů démonů
21 Plánování procesů Plánovač komponent jádra operačního systému Plánovač určuje, který z procesů připravených ke spuštění je přiřazen ke spuštění na CPU Typy plánovače: Burst Time-sharing Real-time
22 Dávkové plánování Cílem je maximalizace propustnosti WB (tedy maximálního počtu provedených úloh) Jádro přechází z jednoho procesu do druhého za následujících podmínek: Běžící proces byl ukončen Při provádění došlo k fatální chybě resp. proces vyčerpal své zdroje Provádějící proces zahájil operaci, kterou nelze provést okamžitě Proces si vyžádal dobrovolné přepnutí
23 Plánování sdílení času Cíl: Rozdělit čas CPU mezi procesy, které jsou připraveny ke spuštění Jádro se přepne z jednoho procesu na druhý za následujících podmínek Proces byl ukončen Při provádění došlo k chybě Proces zahájil operaci, kterou nelze provést okamžitě Proces time quantum has expired Proces si vyžádal dobrovolné přepnutí
24 Klasifikace procesů Podle chování "I / O-bound" - proces provádí aktivní výměnu s externími zařízeními a tráví mnoho času čekáním na vstup / výstup (příklad: webový server, textový editor) "CPU-bound" - procesy které intenzivně zabírají čas procesoru (příklad: kompilace programů, výpočetní úlohy, vykreslování obrázků atd.)
25 Klasifikace procesů Podle účelu: Interaktivní tráví většinu času čekáním na vstup od uživatele, když je vstup přijat, musí být rychle aktivován, aby nenastal pocit „zpomalení“ Dávkové nečekají na vstup uživatele (překladače, numerické aplikace...)
26 Parametry pro plánování procesů sdílení času Pěkná hodnota: [-20, 19] čím menší hodnota, tím vyšší priorita. 0 výchozí priorita Priorita skupiny procesů: grpnice Priorita uživatele: usrnice Plná priorita: nice + grpnice + usrnice zkráceno o interval [-20; 19] Normalizovaná priorita normprio = 20 - fullnice, je v intervalu čím vyšší hodnota, tím vyšší priorita
27 Plánování Linuxu Plánování procesů je rozděleno do epoch Na začátku každé epochy je každému procesu přiřazeno základní kvantum base_quantum = normprio/4 + 1 počítadlo počtu „neutracených“ kvant v epoše, zpočátku counter = base_quantum 1 Priorita: priorita = čítač + normprio Je vybrán proces s nejvyšší prioritou
28 Plánování Linuxu Epocha končí, když všechny procesy, které jsou připraveny ke spuštění, mají čítač == 0 Na začátku další epochy: base_quantum = čítač/2 + normprio/4 + 1 Priorita je tedy dána procesům vázaným na I/O
29 Plánování v reálném čase Účel: poskytnout minimální dobu odezvy, to znamená dobu od výskytu události do provedení procesu čekajícího na tuto událost Typy plánování v reálném čase Založeno na pevný rozvrh Na základě statických priorit
30 Plánování v reálném čase Jádro se přepne z jednoho procesu na druhý za následujících podmínek Proces byl ukončen Při provádění došlo k chybě Proces zahájil operaci, kterou nelze provést okamžitě Proces s vysokou prioritou je připraven ke spuštění Časový úsek procesu vypršela Proces si vyžádal dobrovolný přechod
31 Statická priorita Každý proces v reálném čase má statickou prioritu Procesy sdílení času mají statickou prioritu 0, tj. jsou přiřazeny ke spuštění pouze v případě, že nejsou připraveny žádné procesy v reálném čase ke spuštění
32 Druhy plánování r.v. SCHED_FIFO žádné časové dělení, proces běží, dokud se neobjeví proces s vyšší prioritou nebo proces nezahájí vstup/výstup, nebo se SCHED_RR (round-robin) vymaže, provádění je kvantizováno, procesy se stejnou prioritou se provádějí postupně
33 Inverze priority Předpokládejme, že proces P1 s nízkou prioritou získal nějaký zdroj R V tuto chvíli je připraven ke spuštění proces s vysokou prioritou P2, který vyžaduje zdroj R. Proces P2 čeká na uvolnění zdroje R procesem P1. V tuto chvíli má střední prioritu proces P3, který dále zpozdí uvolnění zdroje R procesem P1
34 Inverze priority Problém nastává, protože procesy, které čekají na uvolnění zdroje, implicitně získávají prioritu procesu, který zdroj získal. Odložení provedení procesu s vysokou prioritou může být katastrofální Neexistuje jednoznačné řešení problému Možná možnost: přiřadit procesu, který zdroj uchopil, maximální prioritu čekajícího procesu (přednostní dědičnost)
35 Správa priorit Linuxu int nice(int inc); void sched_yield(void); int sched_setscheduler(pid_t pid, zásada int, const struct sched_param *param);
Obsah 1 Řízení úlohy 1 1.1 Základní pojmy................................................ ....... 1 1.2 Doplňkové ovládání úlohy. ................... 2 1.3 Ovládací terminál ............ ........................
Státní univerzita v Nižním Novgorodu Fakulta výpočetní matematiky a kybernetiky Operační systémy: Aspekty paralelismu Plánování CPU Linev A.V. Závit Závity
Algoritmy plánování vláken Preemptivní a nepreemptivní plánovací algoritmy Nepreemptivní plánovací algoritmy spoléhají na to, že umožní aktivnímu vláknu běžet, zatímco z vlastní iniciativy,
KAPITOLA 15 Řízení úloh Řízení úloh, funkce standardizovaná v POSIX.1 a poskytovaná mnoha dalšími standardy, umožňuje jednomu terminálu provádět více úloh. Cvičení
Nejdůležitější částí operačního systému, která přímo ovlivňuje fungování počítače, je subsystém řízení procesů. Proces (nebo jinými slovy úkol) je abstrakce, která popisuje
Název Přednáška 5. Plánování úloh Operační systémy 6. listopadu 2012 Přednáška 5 1 / 39 Plánování Začátek Plánování Cíle Základní algoritmy Definice Zásady plánování: (Strategie plánování)
Modul 3. PROCESNÍ ŘÍZENÍ 1. Rozděluje procesorový čas mezi několik procesů současně existujících v systému, zabývá se také tvorbou a zánikem procesů, poskytuje
Plánování procesů Multitasking Operační systém je multitasking, pokud je schopen prokládat provádění více procesů, což vytváří dojem, že v daném okamžiku běží více než jeden proces.
Přednáška 8. Vlákna POSIX Efektivní použití IPC – sdílená paměť a semafory jsou stále omezeny náklady na vytváření nových procesů pomocí systémového volání fork / 2, a to i při použití technologie
Přednáška 2. Subsystém řízení procesů. Správa procesů v multitaskingovém systému spočívá v přidělování zdrojů jádra pro každý běžící proces, provádění přepínání kontextu procesu
UNIX Přednáška 4 UNIX. L.4 1 UNIXOVÉ PROCESY Proces je úkol během jeho provádění. P - obraz programu, včetně zobrazení v paměti spustitelného souboru získaného při kompilaci, segmentů
Laboratorní práce 4 SEZNÁMENÍ S PROCESY Účel práce Seznámit se s pojmem proces. Naučte se získat seznam procesů dostupných v systému a spravovat jejich stav. 1. Teoretické informace
Procesy a toky Operační systémy Přednáška 2 Uljanovsk, UlSTU, katedra " Informační systémy» 1 / 12 Procesní model Čtyři programy běžící v multitaskingovém režimu a); koncepční model čtyř
Základy Unixu Signály Základy Unixu 28.2.08 Snímek 1 z 34 Dnes Co je to signál? Terminologie Staré problémy se signály POSIX a signály Linux Práce se sadami signálů Základy Unixu 28.2.08 Slide
NÁRODNÍ VÝZKUM JADERNÁ UNIVERZITA "MEPhI" Katedra informatiky a řídicích procesů (17) Předmět "Moderní operační systémy" Přednáška 7 Plánování Moskva 2016 Obsah 1. Hlavní
Signály Prostředek asynchronní komunikace mezi procesy Odesílané: Jedním procesem jinému procesu Jádrem operačního systému k procesu k označení událostí ovlivňujících proces Jádrem operačního systému proces v reakci na nesprávné
4.1 Procesy 4.1.1 Pojem procesu Proces (úloha) - program, který je v režimu provádění. Každý proces je spojen se svým adresním prostorem, ze kterého může číst a do kterého může
Operační systémy. Vývoj a implementace. Tanenbaum E., Woodhull A. 3. vyd. - Petrohrad: Piter, 2007. 704 s. Třetí vydání klasického návrhu a implementace operačních systémů od Andrewa Tanenbauma
Operační systémy Přednáška 2 Procesy a vlákna (vlákna). 2.1 Procesy 2.1.1 Pojem proces Proces (úloha) - program, který je v režimu provádění. Každý proces má svůj vlastní adresní prostor s ním spojený.
Pojmenovaná propojení procesů Propojovací kanál, ke kterému se přistupuje prostřednictvím kotevního bodu souborového systému Jádro vytvoří jeden objekt pojmenovaného kanálu pro každou položku v souborovém systému int mkfifo(const char
1 Práce s procesy v systémech POSIX Pojem „proces“ spolu s pojmem „soubor“ odkazuje na základní pojmy operačního systému. Proces je probíhající program. S procesem
Lekce 6. Pojem procesu. Stavy procesu. Dispečink. Plán lekce. 1. Proces. Klasifikace procesů. 2. Zdroje. Klasifikace zdrojů. 3. Řízení procesů. 4. Plánování procesů.
Název Přednáška 6. Blokovací algoritmy Operační systémy 19. listopadu 2012 Přednáška 6 1 / 46 Cíle plánování Požadavky na vzájemné vyloučení Požadavky Kdykoli v jednom kritickém
Procesy a vlákna Pojmy "proces" a "vlákno" Proces (úloha) - program, který je v režimu provádění. Threads provádění (thread thread) nejmenší část programu, které lze přiřadit provedení
VESTAVĚNÉ INFORMAČNÍ A ŘÍDICÍ SYSTÉMY REÁLNÉHO ČASU Přednáška 4: Staticko-dynamické plánování výpočtů v systémech integrované modulární avioniky Katedra ASVK, Laboratoř výpočetní techniky
SUPERPOČÍTAČOVÉ KONSORCIUM RUSKÝCH UNIVERZIT Projekt Vytvoření systému pro školení vysoce kvalifikovaného personálu v oblasti superpočítačových technologií a specializovaného softwaru
Přednáška 10. Přístupy k synchronizaci. Obsah Úkol čtenářů-zapisovatelů Zámky Přístupy k synchronizaci Úkol čtenářů-pisatelů Úkol čtenářů-pisatelů Existuje paměťová oblast, ke které se přistupuje
Plánování procesů ve funkcích Windows NT 1) Procesy Windows NT jsou implementovány jako objekty a přistupuje se k nim prostřednictvím objektové služby. 2) Proces Windows NT má vícevláknovou strukturu
Název Deadlock Petriho síť Požadavky na algoritmus Přednáška 6. Zamykací algoritmy Operační systémy 11. listopadu 2016 Přednáška 6 1 / 65 Příklad: Porovnání dat POSIX Název Deadlock
Implementace souběžnosti pomocí „efektivních objektů“ Paralelismus aplikací je tradičně řešen pomocí preemptivního multitaskingu. Takové schéma je vhodné
Operační systémy Přednáška 3 Procesy 1 Pojem procesu Operační systém za provozu vykonává jeden nebo více programů, naplánuje úlohy (soubor programů, příkazy pro jeho provedení
UNIX Přednáška 6 UNIX. L.6 1 SIGNÁLY Přerušení a speciální situace Přerušení. Externí I/O zařízení, systémové hodiny atd. asynchronně přerušit CPU. Po obdržení signálu přerušení, jádro operačního systému
Název Přednáška 7. Locking Algorithms Operating Systems 24. března 2016 Přednáška 7 1 / 48 Příklad: Porovnání dat POSIX Zablokování Petriho algoritmu Požadavky Příklad Příklad (konec)
RTOS Operační systémy v reálném čase Page 1 Přehled přednášek Definice operačního systému Vlastnosti vestavěného OS Procesy, úlohy, vlákna Systémový čas Meziprocesová komunikace Zpracování
UNIX Přednáška 5 UNIX. L.5 1 Zombies and sirotci Ke známým čtyřem stavům procesu přidáme ještě jednu pětinu: provedení procesu v režimu jádra; spuštění procesu v režimu úloh; napětí; připravenost
Paralelismus 1 Úvod 2 3 Vlákna v jazyce Java Vlákna v jazyce C# Úvod Paralelismus se může vyskytovat na čtyřech úrovních Úroveň strojových instrukcí Úroveň instrukcí vysokoúrovňového programovacího jazyka
Rybinská státní letecká technologická akademie pojmenovaná po P.A. Solovjov "SCHVALUJI" děkan FREI A.I. PRACOVNÍ PROGRAM Dvorson V disciplíně "Operační systémy" pro směr 230100 "Informatika
Laboratoř 4 – Možnosti Možnost 1: Musíte vyřešit problém „Santa Claus“ pomocí knihovny PTHREAD, s výhradou následujících omezení: Santa spí celou dobu, dokud neodejde nebo všichni
1 Meziprocesová komunikační zařízení Vzhledem k tomu, že adresní prostory každého procesu jsou od sebe navzájem izolované, systém musí poskytovat komunikační zařízení pro procesy. Nejjednodušší interakce
Vztahy mezi procesy.. Operační systémy 2011/12 Taťána Romanová 17. září 2011 1 / 29 Plán na dnešek Terminály. Skupiny procesů. Relace. Pojem signálů. Spolehlivé a nespolehlivé
Objekty jádra systému Windows Typy objektů jádra přístupových tokenů / souborů událostí / projekce souborů / mapování souborů
Státní univerzita v Nižním Novgorodu Fakulta výpočetní matematiky a kybernetiky Operační systémy: Aspekty synchronizace paralelismu-1 Linev A.V. Téma diskuze
Operační systém Rozhraní FX-RTOS HAL verze 2.2 Obsah Úvod... 3 O této příručce... 3 Terminologie... 3 Popis funkce API Formát... 3 Rozhraní HAL... 5 Řízení přerušení...
Státní univerzita v Nižním Novgorodu Fakulta výpočetní matematiky a kybernetiky Operační systémy: Aspekty paralelních procesů a vláken Linev A.V. Téma diskuze
Technologie adaptivních nabídek pro budování vysoce spolehlivých systémů Eduard Belokhvostikov Inženýr oddělení SWD Software Services Budování komplexních systémů Velký tým, umístění vývojářů
* 1. Řešení problému zablokování zdrojů. Zablokování nastane, když se dva nebo více úkolů trvale vzájemně blokují, protože úkol na každé straně uzamkne zdroj, který druhý potřebuje.
Domácí práce 4 (2015) Úloha H41: Synchronní čtení-2 Podmínka této úlohy téměř doslovně opakuje podmínku úlohy H32, místo signálů by měly být použity pouze semafory. Napište program
KVASI-PLÁNOVAČ PRO POUŽITÍ nečinných výpočetních modulů víceprocesorového výpočetního systému řízeného EMS Baranov, E.A. Kiselev, D.S. Lyakhovets mezirezortní superpočítač
32. Principy provozních systémů budov. Výpočetní proces a jeho implementace pomocí OS. Řízení výpočetních procesů, vstup-výstup, reálná paměť. Principy operačních sálů
Paralelismus Multithreading Proč vytvářet paralelní systémy? Přirozená omezení Je nemožné donekonečna zvyšovat rychlost jednojádrových procesorů. Příklad 1 takt 4 GHz procesor 0,25 ns.
Přednáška 6. Použití deskriptorů souborů. Uživatelský deskriptor souboru Systémová volání pro práci se souborem: 1. otevřít/vytvořit 1 otevřít/vytvořit soubor s danými možnostmi a režimem přístupu int
POST katedry VGKS Kurz "Systémový software" Laboratoř 1 (4 hodiny) Téma: "Vytváření vláken v Win32 API pro MS Windows." Vlákno je vytvořeno funkcí CreateThread, která má následující
GOUVPO "Volžská státní univerzita telekomunikací a informatiky" Sekce 6. Software kontrolní komplexy. Operační systémy Přednášející: real-time prof. oddělení JE
Státní univerzita v Nižním Novgorodu Fakulta výpočetní matematiky a kybernetiky N. I. Lobačevského Operační systémy: aspekty paralelismu Úkol producentů a spotřebitelů Spotřebitelé
"Operační systémy" Test. Cvičení. Řízení procesu. Nejtěžší na vysvětlení úkol, ale pokusím se vysvětlit, aby bylo alespoň něco jasné. Takže dostáváme tabulku a proces,
Přednáška 22 Topologické třídění. 22.1. Reprezentace libovolného stromu jako binárního. 22.1.1. Na rozdíl od binárního stromu nemůže být libovolný strom prázdný (podle definice musí
Ministerstvo školství Běloruské republiky Vzdělávací zařízení "Běloruská státní univerzita informatiky a radioelektroniky" Katedra elektronických výpočetních prostředků D. S. Likhachev ROZVOJ
Laboratorní práce 4 Účel: Laboratorní práce je určena k získání praktických zkušeností s tvorbou aplikace s využitím programovacího jazyka C++ pro matematické výpočty. Volala:
Modul 1. OBECNÉ INFORMACE O PROVOZNÍCH SYSTÉMECH, PROSTŘEDÍCH A SHELL
SYSTÉMOVÉ PROGRAMOVÁNÍ VE WINDOWS Pobegailo AP Programování systému ve Windows. Petrohrad: BHV-Petersburg, 2006. - 1056 s.: ill. ISBN 5-94157-792-3 Zabývá se do hloubky systémovým programováním
SESTAVOVATELÉ: Ryaby V.V., odborný asistent katedry matematické podpory elektronických počítačů Běloruského státní univerzita; Pobegailo A.P., docent, katedra technologie
Synchronization Primitives 2011 Jaký je hlavní problém programových mutexových metod? Nelze zaručit kontinuitu provádění jednotlivých akcí: Program lze kdykoli přerušit
Inverze priority nastane, když dvě vlákna, která mají vysokou prioritu ( V) a nízkou prioritou ( H) sdílet nějaký společný zdroj ( R). Předpokládejme také, že v systému existuje třetí vlákno, jehož priorita je mezi prioritami V a H. Říkejme tomu průměr Z). Pokud vlákno B vstoupí do stavu připravenosti, když je vlákno aktivní H a H zablokoval zdroj R, pak tok V přemístit tok H a R zůstane zablokován. Když V potřebovat zdroj R, pak přejde do blokovaného stavu. Pokud je pouze vlákno ve stavu připravenosti H pak se nic zlého nestane, H uvolněte uzamčený prostředek a nechejte se předjímat vláknem V. Ale pokud v době blokování průtoku V, stream je ve stavu připravenosti Z, která má vyšší prioritu než H, pak se stane aktivním a H bude opět vytlačena a kontrolu získá až poté Z dokončí svou práci. Takové zpoždění může dobře vést ke skutečnosti, že kritická doba provozu vlákna V bude přeskočeno. Pokud V je tedy tvrdý proud v reálném čase podobná situace není povoleno.
Jaké ochranné mechanismy proti tomuto problému používají vývojáři RTOS? Nejpoužívanějším a osvědčeným mechanismem je přednostní dědictví.
Mechanismus dědičnosti priority bohužel nemůže vždy vyřešit problémy spojené s blokováním vlákna s vysokou prioritou na blokovaném zdroji. V případě, že několik vláken se střední a nízkou prioritou sdílí některé prostředky s vláknem s vysokou prioritou, je možné, že vlákno s vysokou prioritou bude muset čekat příliš dlouho, dokud každé z nižších vláken neuvolní svůj prostředek a dojde ke ztrátě kritického servisního času. Takové situace (sdílení zdrojů vlákna s vysokou prioritou) by však měli sledovat vývojáři aplikačního systému. V zásadě je dědění priority nejběžnějším obranným mechanismem proti problému inverze priority.
Další, poněkud méně obvyklá metoda se nazývá Priority Ceiling Protocol. Tato metoda spočívá v přidání ke standardním vlastnostem synchronizačních objektů parametr určený maximální prioritou vlákna, které k tomuto objektu přistupuje. Je-li tato možnost nastavena, bude priorita jakéhokoli vlákna přistupujícího k tomuto synchronizačnímu objektu zvýšena na zadanou úroveň, a proto nemůže být potlačena žádným vláknem, které může potřebovat prostředek, který uzamklo. Po odemknutí zdroje se priorita vlákna sníží na počáteční úroveň. Ukazuje se tedy něco jako předběžné dědictví priorit. Tato metoda má však řadu vážných nevýhod. V první řadě je na vývojáři, aby synchronizační objekty „vycvičil“ s úrovní jejich priority. Za druhé, může docházet ke zpožděním při spouštění vláken s vysokou prioritou, zatímco se vlákna s nízkou prioritou zpracovávají. Obecně lze tento mechanismus použít nejúčinněji, když existuje jedno pevné vlákno v reálném čase a několik vláken s nižší prioritou, která s ním sdílejí prostředky.
11.Meziprocesová komunikace (angl. Inter-Process Communication, IPC) - sada metod pro výměnu dat mezi více vlákny v jednom nebo více procesech. Procesy mohou běžet na jednom nebo více počítačích propojených sítí. Metody IPC se dělí na metody zasílání zpráv, synchronizace, sdílené paměti a vzdáleného volání (RPC). Metody IPC závisí na šířce pásma a latenci interakce mezi proudy a typu přenášených dat.
IPC spolu s konceptem adresního prostoru je základem pro vymezení adresního prostoru.
| Metoda | Implementováno (operačním systémem nebo jiným prostředím) |
| Soubor | Všechny operační systémy. |
| Signál | Většina operačních systémů; některé systémy, jako je Windows, implementují signály pouze v runtime knihovně C, ale neposkytují plnou podporu pro použití metod IPC. |
| zásuvka | |
| Kanál | |
| Pojmenovaná dýmka | Všechny systémy vyhovující standardu POSIX. |
| Semafor | Všechny systémy vyhovující standardu POSIX. |
| Sdílená paměť | Všechny systémy vyhovující standardu POSIX. |
| Zprávy (bez oddělení) | Používá se v paradigmatu MPI, Java RMI, CORBA a dalších. |
| Soubor mapovaný v paměti | Všechny systémy vyhovující POSIX; nese riziko sporu, pokud je použit dočasný soubor. Windows také podporuje tuto technologii, ale používá jiné než POSIX API. |
| fronta zpráv | většina operačních systémů. |
| Poštovní schránka | některé operační systémy. |
12. Klasické problémy meziprocesové komunikace
Problém filozofů stravování
V roce 1965 Dijkstra formuloval a vyřešil problém synchronizace, který nazval Dining Philosophers Problem. Problém lze formulovat následovně: sedí pět filozofů kulatý stůl a každý má talíř špaget. Špagety jsou tak kluzké, že každý filozof potřebuje dvě vidličky, aby je zvládl. Mezi každé dva talíře je jedna vidlička.
Život filozofa se skládá ze střídání období jídla a přemýšlení. Když má filozof hlad, snaží se dostat dvě vidličky, levou a pravou, v libovolném pořadí. Pokud se mu podaří získat dvě vidličky, chvíli jí, pak vidličky vrátí a dál přemýšlí. Otázka zní: je možné napsat algoritmus, který simuluje tyto akce pro každého filozofa a nikdy se nezasekne.
Situace, kdy všechny programy běží neomezeně dlouho, ale nemohou dosáhnout žádného pokroku, se nazývá zablokování procesu.
Z praktického hlediska vyvstávají problémy s efektivitou: pouze jeden filozof může jíst špagety najednou. Vidliček je ale pět, takže je nutné dovolit jíst dvěma filozofům v kteroukoli danou chvíli. Filosof může začít jíst pouze tehdy, když nejí žádný z jeho sousedů.
Problém čtenářů a spisovatelů
Dalším známým problémem je problém čtenář-zapisovatel, který modeluje přístup k databázi. Představte si databázi rezervací letadel, do které se mnoho procesů snaží dostat. Můžete povolit současné čtení dat z databáze, ale pokud proces zapisuje informace do databáze, musí být ukončen přístup ostatních procesů, dokonce i přístup pro čtení. Jak naprogramovat čtenáře a spisovatele?
Dokud je v databázi alespoň jeden aktivní čtenářský proces, je povolen přístup k dalším čtenářům a všichni přicházejí a přicházejí. Abyste se této situaci vyhnuli, musíte mírně změnit program: pokud proces zápisu čeká na přístup k databázi, nový proces čtení nezíská přístup, ale zařadí se do fronty za procesem zápisu.
Problém s holičem ve spánku
V holičství je jeden holič, jeho křeslo a n židlí pro návštěvníky. Pokud se nenajdou lidé, kteří chtějí využít jeho služeb, holič se posadí do křesla a spí. Pokud klient přijde do holičství, musí holiča probudit. Pokud klient přijde a vidí, že je holič zaneprázdněn, buď si sedne na židli (pokud je místo), nebo odejde (pokud není místo). Holiče a návštěvníky je nutné naprogramovat tak, aby se vyhnuli podmínkám soutěže.
Navrhované řešení využívá tři semafory: zákazníci, pro počítání čekajících návštěvníků (klient sedící v holičském křesle se nepočítá - již nečeká); barbers, počet holičů (0 nebo 1) nečinně čekajících na klienta a mutex pro realizaci vzájemného vyloučení. Proměnná čekání slouží také k počítání čekajících návštěvníků.
13. Zablokování je situace, kdy se skupina procesů zablokuje, pokud každý proces ve skupině čeká na událost, kterou může vyvolat pouze jiný proces ve stejné skupině.
Stránkované zdroje jsou bezbolestně převzaty z procesu, který je vlastní.
Nestránkovatelný zdroj nelze z procesu bezbolestně odebrat.
Algoritmus pro použití zdrojů v obecný pohled:
2. Využití zdrojů
3. Návratnost zdrojů
Stav uváznutí:
1. Podmínka vzájemného vyloučení. Každý zdroj v daném čase je buď přidělen přesně jednomu procesu, nebo je dostupný.
2. Podmínka držení a čekání. Byly přijaty procesy, které jsou aktuálně uloženy rané zdroje může požadovat nové zdroje.
3. Podmínka absence nuceného vykládání zdrojů. Proces nemůže být nucen odebírat dříve získané zdroje. Proces vlastnictví musí uvolnit zdroje sám.
4. Podmínka cyklického čekání. Musí existovat kruhová sekvence dvou nebo více procesů, z nichž každý čeká na přístup ke zdroji, který drží další člen sekvence.
Detekce a odstranění uváznutí:
1. Obnova nuceným uvolněním zdroje spočívá v záměrném výběru zdrojů z procesu a používá se zejména v systémech pro dávkové zpracování dat. Má nevýhodu v tom, že ne všechny zdroje lze vzít z procesu.
2. Obnova prostřednictvím vrácení zpět. Spočívají ve vytváření bodů přerušení vývojáři v aplikacích. Jakmile dojde k uváznutí, proces se vrátí k nejbližšímu kontrolnímu bodu a odtud se restartuje.
3. Obnova zničením procesů Spočívá ve zničení jednoho z procesů, které se dostaly do slepé uličky. Pokud se zabíjení nezdaří, další proces v procesu je zabit, dokud se nevyřeší zablokování.
Vyhýbání se zablokování:
Stav je bezpečný, pokud není zablokován a v plánovači existuje určité pořadí, ve kterém je každý proces chráněn (i když všechny procesy chtějí získat maximální množství zdrojů).
Prevence uváznutí:
1. Útok s podmínkou vzájemného vyloučení
Pokud systém nemá zdroj prezentovaný v jediném použití jednoho procesu, k uváznutí nikdy nedojde. Je třeba se vyhnout alokaci zdrojů, když to není skutečně nutné, a je důležité pokusit se zajistit, aby si zdroj mohl nárokovat minimální počet procesů.
2. Podmínky zadržení a čekání
Programování procesu takovým způsobem, že vyžaduje všechny zdroje bezprostředně před spuštěním programu.
Nevýhody tohoto řešení:
· Ne všechny procesy před zahájením práce vědí, kolik a jaké zdroje potřebují.
Zdroje nebudou využity optimálně
3. Útok na podmínku absence nuceného vykládání zdrojů
Neexistuje žádný normální způsob, jak se vyhnout uváznutí, protože Násilné odstranění prostředku z procesu, když běží, je téměř nemožné.
4. Útok za podmínky kruhového čekání
· Řízení zdrojů obecně uvádí, že proces má nárok pouze na jeden zdroj najednou. Toto pravidlo nemusí být povoleno pro všechny procesy.
· Obecné číslování všech zdrojů a zavedení pravidla, podle kterého si proces musí vyžádat několik zařízení podle pořadí jejich číslování. Funguje pouze s relativně malým množstvím zdrojů.
5. Bankéřův algoritmus
Bezpečný stav je stav, pro který existuje alespoň jedna sekvence událostí, která nepovede k uváznutí.
Podstata algoritmu:
· Předpokládejme, že systém má "x" zařízení.
Operační systém přijme požadavek od uživatelského procesu, pokud jeho maximální požadavek nepřekročí "x".
· Uživatel má zaručeno, že pokud je operační systém schopen uspokojit jeho požadavek, budou všechna zařízení vrácena do systému v konečném čase.
· Aktuální stav systému se nazývá spolehlivý, pokud OS dokáže zajistit provedení všech procesů v konečném čase.
· Podle bankovního algoritmu je alokace zařízení možná pouze tehdy, pokud stav systému zůstává spolehlivý.
Závěry: Existují různé způsoby, jak se dostat z patové situace.
· Stažení běžícím procesem, dokud nezmizí zablokování.
Restartování systému z kontrolního bodu
Kontrolní bod - plný stav PC uloženo na externím médiu.
14. Stránkované zdroje
Viz 13. (na internetu nic není, infa 146%).
15.Nestránkované zdroje
Viz 13.
16. TLUSTÝ (angl. File Allocation Table - „file alokační tabulka“) je klasická architektura souborového systému, která je pro svou jednoduchost stále hojně využívána pro flash disky a paměťové karty. V nedávné minulosti se používal v disketách, pevných discích a dalších paměťových médiích.
Navrhli Bill Gates a Mark McDonald (anglicky) v letech 1976-1977. Byl používán jako hlavní souborový systém v operačních systémech rodiny DOS a Windows (až do Windows 2000).
Struktura FAT odpovídá standardu ECMA-107 a je podrobně definována oficiální specifikací společnosti Microsoft známou jako FATGEN.
| FAT16 | FAT32 |
| Implementováno a používáno většinou operačních systémů (MS-DOS, Windows 95/98/Me, Windows 2000 a Windows XP, OS/2, UNIX). | V současné době podporováno pouze na Windows 95/98/Me, Windows 2000 a Windows XP (vousatý článek, ani Vista, buďte optimisté - lež, že všichni implementovali všechno) |
| Velmi efektivní pro logické jednotky menší než 256 MB. | Nefunguje s disky menšími než 512 MB. |
| Podporuje kompresi disku, jako je například algoritmus DriveSpace. | Nepodporuje kompresi disku. |
| Zvládá maximálně 65 525 clusterů, jejichž velikost závisí na velikosti logické jednotky. Protože maximální velikost clusteru je 32 KB, FAT16 zvládne pouze logické disky do 2 GB. | Dokáže pracovat s logickými jednotkami až do 2047 GB s maximální velikostí clusteru 32 KB. |
| Jak větší velikost logický disk, tím méně efektivní ukládání souborů v systému FAT "16, protože se také zvětšuje velikost clusterů. Prostor pro soubory je přidělován clustery, a proto při maximální velikosti logického disku bude soubor o velikosti 10 kB vyžadovat 32 KB a 22 KB místa na disku bude zbytečné. | Na logických jednotkách menších než 8 GB je velikost clusteru 4 KB. |
Maximální možná délka souboru ve FAT32 je 4 GB mínus 2 bajty. Aplikace Win32 mohou otevírat soubory této délky bez zvláštního zpracování. Jiné aplikace by měly používat přerušení Int 21h, funkce 716C (FAT32) s příznakem otevření rovným EXTEND-SIZE (1000h).
V systému souborů FAT32 jsou pro každý cluster v alokační tabulce souborů přiděleny 4 bajty, zatímco ve FAT16 - 2 bajty a ve FAT12 - 1,5 bajtu.
Horní 4 bity 32bitového záznamu tabulky FAT32 jsou vyhrazeny a nepodílejí se na vytváření čísla klastru. Programy, které přímo čtou tabulku PAT32, musí tyto bity maskovat a zabránit jejich změně při zápisu nových hodnot.
Souborové systémy (NTFS)
Souborový systém je způsob organizace dat na paměťových médiích. Systém souborů určuje, kde a jak budou soubory zapisovány na médium, a poskytuje operačnímu systému přístup k těmto souborům.
Na moderní systémy souborů jsou kladeny další požadavky: schopnost šifrovat soubory, řízení přístupu k souborům a další atributy. Obvykle je souborový systém zapsán na začátku pevného disku.
NTFS(zkratka Nový technologický souborový systém - Souborový systém Nová technologie ) je standardní souborový systém pro rodinu operačních systémů Microsoft Windows NT.
Uvedeno 27. července 1993 s Windows NT 3.1. NTFS je založen na souborovém systému HPFS (zkratka Vysoce výkonný souborový systém - Vysoce výkonný souborový systém), který byl vytvořen společností Microsoft společně s IBM pro operační systém OS / 2.
Hlavní vlastnosti NTFS: vestavěné funkce pro omezení přístupu k datům pro různé uživatele a skupiny uživatelů, stejně jako přidělování kvót (omezení maximálního množství místa na disku obsazeného určitými uživateli), použití žurnálovacího systému pro zlepšení spolehlivosti systému souborů .
Specifikace systému souborů jsou uzavřeny. Obvykle je velikost clusteru 4 kB. V praxi se nedoporučuje vytvářet objemy větší než 2TB. Pevné disky právě dosáhly této velikosti, snad se v budoucnu dočkáme nového souborového systému.
Během instalace systému Windows XP se zobrazí výzva k naformátování disku v systému TLUSTÝ nebo NTFS. To znamená FAT32.
Všechny souborové systémy jsou postaveny na principu: jeden cluster - jeden soubor. Tito. jeden cluster ukládá data pouze jednoho souboru.
Hlavním rozdílem pro běžného uživatele mezi těmito systémy je velikost clusteru. "Kdysi dávno, když byly disky malé a soubory velmi malé," to bylo velmi nápadné.
Zvažte příklad jednoho svazku na 120GB disku a 10Kb souboru.
Pro FAT32 velikost clusteru bude 32 kB a pro NTFS- 4 kb.
V FAT32 takový soubor zabere 1 cluster a zbyde 32-10=22Kb nepřiděleného prostoru.
V NTFS takový soubor zabere 3 clustery a zbyde 12-10=2Kb nepřiděleného prostoru.
Tedy přechod z FAT32 na NTFS umožňuje optimálnější využití pevného disku, když je v systému velké množství malých souborů.
A meziprocesová komunikace ( meziprocesová komunikace) v multitaskingovém operačním systému. Úkolem je zajistit, aby kadeřník pracoval, když jsou klienti, a odpočíval, když klienti nejsou.
Encyklopedický YouTube
1 / 1
✪ Neefektivní schůzka. film "Afonya"
titulky
Problém
Přirovnání je založeno na hypotetickém holičství s jedním holičem. Kadeřnictví má jedno pracoviště a přijímací místnost s několika židlemi. Když kadeřník ukončí stříhání klienta, propustí klienta a poté se jde na recepci podívat, zda tam čekají nějací klienti. Pokud ano, pozve jednoho z nich a ostříhá ho. Pokud tam nejsou žádní čekající zákazníci, vrátí se do svého křesla a spí v něm.
Každý klient, který přijde, se dívá na to, co kadeřník dělá. Pokud kadeřník spí, klient ho probudí a posadí se do křesla. Pokud kadeřník pracuje, tak klient jde na recepci. Pokud je v čekárně volná židle, klient si sedne a čeká, až na něj přijde řada. Pokud není volná židle, klient odchází. Na základě naivní analýzy má výše uvedený popis zajistit správné fungování holičství, kdy holič ostříhá každého, kdo přijde, dokud jsou zákazníci, a pak spí, dokud nepřijde další zákazník. V praxi existuje několik konfliktních situací, které ilustrují obecné problémy plánování.
Všechny tyhle konfliktní situace související s tím, že úkony kadeřníka i klienta (kontrola čekárny, vstup do kadeřnictví, usazení se v čekárně atd.) trvají neznámou dobu a/nebo mohou probíhat současně. Klient může například přijít a všimnout si, že kadeřník pracuje, pak jde na recepci. Kadeřník při chůzi dokončí stříhání, které dělá, a jde se podívat do čekárny, a to rychleji než klient tam mířící. Protože v recepci ještě nikdo není (klient ještě nedošel), vrací se na své místo a spí. Kadeřník nyní čeká na klienta a klient čeká na kadeřníka. V jiném příkladu mohou dva zákazníci dorazit ve stejnou dobu, když je v prostoru recepce k dispozici pouze jedno místo. Všimnou si, že je kadeřník v práci, jdou do čekárny a oba se snaží zaujmout jedinou židli.
Problém spícího holiče je často připisován Edsger Dijkstrovi (1965), jednomu z průkopníků počítačové vědy.
Řešení
Existuje několik možných řešení tohoto problému. Hlavním prvkem každého z řešení je mutex - mechanismus, který zajišťuje změnu stavu ( Stát) v daný čas může pouze jeden z účastníků. Holič musí získat mutex před kontrolou klientů a uvolnit ho, když začne spát nebo pracovat. Klient si musí před vstupem do kadeřnictví pořídit stejný mutex a uvolnit jej, jakmile se usadí buď v prostoru recepce nebo u kadeřníka. Tím jsou vyřešeny oba problémy uvedené v předchozí části. Pro indikaci aktuálního stavu systému je také možné použít obecnější mechanismus semaforu. Například pomocí semaforu můžete vyjádřit počet osob v čekárně.
Varianta stejného problému s více kadeřníky má další složitost spočívající v koordinaci více kadeřníků mezi čekajícími klienty.
Literatura o operačních systémech obsahuje mnoho zajímavých problémů, které byly široce diskutovány a analyzovány pomocí různé metody synchronizace. V této části se podíváme na tři nejznámější problémy.
Problém filozofů stravování
V roce 1965 Dijkstra formuloval a vyřešil problém synchronizace, který nazval Dining Philosophers Problem. Od té doby se každý, kdo vynalezl další nové synchronizační primitivum, cítil nucen demonstrovat přednosti nového primitiva na příkladu problému Dining Philosophers. Problém lze formulovat takto: pět filozofů sedí u kulatého stolu a každý má talíř špaget. Špagety jsou tak kluzké, že každý filozof potřebuje dvě vidličky, aby je zvládl. Mezi každé dva talíře je jedna vidlička.
Život filozofa se skládá ze střídání období jídla a přemýšlení. (Toto je samozřejmě abstrakce, i když je aplikována na filozofy, ale zbytek životních procesů je pro náš úkol irelevantní.) Když má filozof hlad, snaží se získat dvě vidličky, levou a pravou, v libovolném pořadí. Pokud se mu podaří získat dvě vidličky, chvíli jí, pak vidličky vrátí a dál přemýšlí. Otázka zní: je možné napsat algoritmus, který simuluje tyto akce pro každého filozofa a nikdy se nezasekne? (Někteří lidé si myslí, že potřeba dvou vidliček je trochu umělá. Možná bychom měli nahradit italské jídlo čínským jídlem, špagety rýží a vidličky odpovídajícími hůlkami.)
Program můžete změnit tak, že po obdržení levé vidlice se zkontroluje dostupnost té pravé. Pokud není k dispozici pravá vidlice, filozof vrátí levou, chvíli počká a celý proces zopakuje. Ani tento přístup nebude fungovat, i když z jiného důvodu. Bez štěstí může všech pět filozofů zahájit proces současně, zvednout levou vidličku, objevit nepřítomnost pravé, položit levou zpět na stůl, zvednout levou vidličku ve stejnou dobu a tak dále. do nekonečna. Situace, kdy všechny programy pokračují v práci libovolně dlouhou dobu, ale nemohou udělat alespoň nějaký pokrok, se nazývá proces hang (v angličtině hladovění, doslova „hladovění“.
Termín se použije, i když se problém nevyskytuje v italské nebo čínské restauraci, ale na počítačích).
Možná si říkáte: „Pokud filozofové přemýšlejí nějakou náhodně zvolenou dobu poté, co se jim nepodařilo zvednout správnou vidličku, je malá šance, že všechny procesy budou šlapat vodu alespoň hodinu.“ To je správné a pro většinu aplikací není problém opakovat po chvíli. Například v lokální síti Ethernet v situaci, kdy dva počítače současně posílají pakety, musí každý počkat náhodně nastavený čas a zkusit to znovu – v praxi toto řešení funguje dobře. V některých aplikacích je však vhodnější jiné řešení, které funguje vždy a není závislé na náhodných číslech (například v aplikaci pro bezpečnost v jaderných elektrárnách).
Proveďte vylepšení, které eliminuje zablokování a zablokování procesu: chraňte pět příkazů následujících po požadavku myšlení pomocí binárního semaforu. Filozof by pak musel provést operaci Down s proměnnou mutexu, než by sáhl po vidlicích. A poté, co jsou vidlice zpět na místě, by měla provést operaci Up na proměnné mutex. Z teoretického hlediska je řešení vcelku vhodné. Z praktického hlediska vyvstávají problémy s efektivitou: pouze jeden filozof může jíst špagety najednou. Vidliček je ale pět, takže je nutné dovolit jíst dvěma filozofům v kteroukoli danou chvíli.
Řešení odstraňuje uváznutí a umožňuje implementovat maximální možný paralelismus pro libovolný počet filozofů. Zde se pole stavů používá ke sledování stavu mysli každého filozofa: buď jí, medituje, nebo hladoví (snaží se získat vidličky). Filosof může začít jíst pouze tehdy, když nejí žádný z jeho sousedů. Sousedé čísla filozofa i jsou definováni makry LEFT a RIGHT (tj. pokud i = 2, pak LEFT=
Problém čtenářů a spisovatelů
The Dining Philosophers Problem je užitečný pro modelování procesů, které soutěží o exkluzivní přístup k omezenému počtu zdrojů, jako jsou I/O zařízení. Dalším známým problémem je problém čtenář-zapisovatel, který modeluje přístup k databázi. Představte si databázi rezervací letadel, do které se mnoho procesů snaží dostat. Můžete povolit současné čtení dat z databáze, ale pokud proces zapisuje informace do databáze, musí být ukončen přístup ostatních procesů, dokonce i přístup pro čtení. Jak naprogramovat čtenáře a spisovatele?
Abyste se této situaci vyhnuli, musíte mírně změnit program: pokud proces zápisu čeká na přístup k databázi, nový proces čtení nezíská přístup, ale zařadí se do fronty za procesem zápisu. Nyní musí proces zápisu počkat, až čtecí procesy, které již jsou v něm, opustí databázi, ale není nutné přeskakovat čtecí procesy, které přišly do databáze po něm. Nevýhodou tohoto řešení je zhoršení výkonu způsobené sníženou konkurencí. Je prezentováno řešení, ve kterém mají procesy psaní vyšší prioritu.
Problém s holičem ve spánku
Další klasická problémová situace meziprocesové komunikace se odehrává v holičství. V holičství je jeden holič, jeho křeslo a n židlí pro návštěvníky. Pokud nejsou žádní lidé, kteří chtějí využít jeho služeb, holič sedí v křesle a spí.Přijde-li klient ke kadeřníkovi, musí holič probudit. Pokud klient přijde a vidí, že je holič zaneprázdněn, buď si sedne na židli (pokud je místo), nebo odejde (pokud není místo). Holiče a návštěvníky je nutné naprogramovat tak, aby se vyhnuli podmínkám soutěže. Tento problém má mnoho analogií například v oblasti front informační služba, která zpracovává omezený počet požadavků současně, s počítačovým systémem čekání na žádosti.
Navrhované řešení využívá tři semafory: zákazníci, pro počítání čekajících návštěvníků (klient sedící v holičském křesle se nepočítá - již nečeká); barbers, počet holičů (0 nebo 1) nečinně čekajících na klienta a mutex pro realizaci vzájemného vyloučení. Proměnná čekání slouží také k počítání čekajících návštěvníků.
Je to kopie proměnné Zákazníci. Přítomnost této proměnné v programu je způsobena tím, že nelze přečíst aktuální hodnotu semaforu. V tomto řešení musí návštěvník při pohledu do holičství spočítat počet čekajících návštěvníků. Pokud je návštěvníků méně než židlí, nový návštěvník zůstává, jinak odchází.
Když holič ráno přijde do práce, provede proceduru holič, čímž zablokuje semafor zákazníků, protože hodnota semaforu je 0. Holič pak jde spát a spí, dokud nepřijde první zákazník.
Po příchodu do holičství návštěvník provede zákaznickou proceduru a požádá o přístup k mutexu pro vstup do kritické oblasti. Pokud se po něm objeví další návštěvník, nebude moci nic dělat, dokud první návštěvník neuvolní přístup k mutexu. Poté návštěvník zkontroluje volné židle, v případě poruchy uvolní přístup do mutexu a odejde.
Pokud je volná židle, návštěvník zvýší hodnotu celočíselné proměnné čekání. Poté provede proceduru up na zákaznickém semaforu,
Nejvíce aktivující tok holič. V tuto chvíli je aktivní jak návštěvník, tak holič. Když návštěvník uvolní přístup k mutexu, holič ho uchopí, udělá úklid a začne klientovi stříhat vlasy.
Na konci stříhání návštěvník opouští proceduru a odchází od kadeřníka. Na rozdíl od předchozích programů zde není žádný návštěvnický cyklus, protože každý návštěvník je škrtnut pouze jednou. Holičský cyklus existuje a holič se snaží najít dalšího návštěvníka. Pokud se mu to podaří, ostříhá dalšího návštěvníka, jinak holič usne.
Stojí za zmínku, že navzdory nedostatku přenosu dat v problému čtenář-zapisovatel a problému spícího holiče jsou oba tyto problémy problémy meziprocesové komunikace, protože vyžadují synchronizaci několika procesů.
Problém
Přirovnání je založeno na hypotetickém holičství s jedním holičem. Kadeřnictví má jedno pracoviště a čekárnu s mnoha židlemi. Když kadeřník ukončí stříhání klienta, klienta pustí a poté se jde na recepci podívat, zda tam čekají klienti. Pokud existuje, pozve jednoho z nich a ostříhá ho. Pokud tam nejsou žádní čekající zákazníci, vrátí se do svého křesla a spí v něm.
Každý klient, který přijde, se dívá na to, co kadeřník dělá. Pokud kadeřník spí, klient ho probudí a posadí se do křesla. Pokud kadeřník pracuje, tak klient jde na recepci. Pokud je v čekárně volná židle, klient si sedne a čeká, až na něj přijde řada. Pokud není volná židle, klient odchází. Na základě naivní analýzy by měl výše uvedený popis zajistit, aby holičství fungovalo správně, kdy holič ostříhá každého, kdo přijde, dokud jsou zákazníci, a pak spí, dokud nepřijde další zákazník. V praxi může nastat mnoho problémů, které ilustrují běžné problémy s plánováním.
Všechny problémy pramení z toho, že veškeré činnosti kadeřníka i klienta (kontrola čekárny, vstup do kadeřnictví, usazení v čekárně atd.) zabírají neznámou dobu. Klient může například přijít a všimnout si, že kadeřník pracuje, pak jde na recepci. Při chůzi holič dokončí účes, který právě dělá, a jde se podívat na recepci. Protože tam nikdo není (klient ještě nedošel), vrací se na své místo a spí. Holič nyní čeká na klienta a klient čeká na holiče. V jiném příkladu mohou dva zákazníci dorazit ve stejnou dobu, když je v prostoru recepce k dispozici pouze jedno místo. Všimnou si, že je kadeřník v práci, jdou do čekárny a oba se snaží zaujmout jedinou židli.
Problém spícího holiče je často připisován Edsgeru Dijkstrovi (1965), jednomu z průkopníků informatiky.
Řešení
K dispozici je mnoho možných řešení. Hlavním prvkem každého z nich je mutex , který zajišťuje změnu stavu ( Stát) může být pouze jeden z účastníků. Kadeřník musí před kontrolou klientů zachytit tuto výjimku mutexu a uvolnit ji, když začne spát nebo pracovat. Zákazník musí před vstupem do prodejny uchopit mutex a uvolnit jej, jakmile se usadí buď v prostoru recepce nebo u kadeřníka. Tím jsou vyřešeny oba problémy uvedené v předchozí části. Semafory jsou také nutné k označení stavu systému. Například je možné uložit počet osob v prostoru recepce.
Možnost více kadeřníků má další složitost koordinace více kadeřníků mezi čekajícími klienty.
viz také
- Problém kuřáků
Odkazy
- Moderní operační systémy (2. vydání) od Andrewa S. Tanenbauma (ISBN 0-13-031358-0)
- Malá kniha semaforů od Allena B. Downeyho, http://greenteapress.com/semaphores
- Kooperující sekvenční procesy od E.W. Dijkstra. Technická zpráva EWD-123, 1965, Technologická univerzita, Eindhoven, Nizozemsko.
Nadace Wikimedia. 2010 .