А.В. Столяров - Введение в операционные системы (1114673), страница 36
Текст из файла (страница 36)
Ïðè ýòîì âñå ïÿòü âèëîê (ìüþòåêñîâ) îêàæóòñÿ áëîêèðîâàíû, òàê ÷òî âñå ïðîöåññû òàêæå çàáëîêèðóþòñÿ íàñëåäóþùåé ñòðîêå ïðîöåäóðû ïðè ïîïûòêå ïîëó÷èòü âòîðóþ âèëêó.Îäíèì èç ïðîñòåéøèõ ìåõàíèçìîâ èçáåæàíèÿ âçàèìîáëîêèðîâêè â çàäà÷åî ïÿòè ôèëîñîôàõ ÿâëÿåòñÿ ïðèìåíåíèå ñåìàôîðà, íå ïîçâîëÿþùåãî ôèëîñîôàì ïðèñòóïàòü ê òðàïåçå âñåì îäíîâðåìåííî. Çàâåäåì ñåìàôîð è íàçîâåìåãî sem. Òîãäà æèçíåííûé öèêë ôèëîñîôà ïðèìåò ñëåäóþùèé âèä:void philosopher(int n) {for(;;) {think();down(sem);lock(forks[n]); lock(forks[right(n)]);eat();unlock(forks[n]); unlock(forks[right(n)]);up(sem);}}Îòäåëüíîãî ðàññìîòðåíèÿ çàñëóæèâàåò âîïðîñ î òîì, êàêîå çíà÷åíèå ïðèñâîèòü ñåìàôîðó ïåðåä íà÷àëîì ðàáîòû.
Òàê, åñëè ïðèñâîèòü åìó çíà÷åíèå 1,îäíîâðåìåííî óïîòðåáëÿòü ñïàãåòòè ñìîæåò ëèøü îäèí ôèëîñîô. Ñ òåîðåòè÷åñêîé òî÷êè çðåíèÿ âñå õîðîøî, îäíàêî ïðè ýòîì ìû èìååì íåðàöèîíàëüíûé166ïðîñòîé ðåñóðñîâ, âåäü óñëîâèÿ ïîçâîëÿþò åñòü äâóì ôèëîñîôàì îäíîâðåìåííî, íå ìåøàÿ äðóã äðóãó. Îäíàêî è íà÷àëüíîå çíà÷åíèå, ðàâíîå äâóì, íåñïàñåò ñèòóàöèþ, âåäü ïî çàêîíó ïîäëîñòè çà ñåìàôîð îáÿçàòåëüíî ïðîéäóòôèëîñîôû, ñèäÿùèå ðÿäîì.Î÷åâèäíî, ìàêñèìàëüíîå âîçìîæíîå çíà÷åíèå ñåìàôîðà − ÷åòûðå, â ïðîòèâíîì ñëó÷àå òåðÿåòñÿ åãî ñìûñë. Ïðè òàêîì çíà÷åíèè âîçìîæíà ñèòóàöèÿ,êîãäà òðè ôèëîñîôà óñïåëè âçÿòü ïî îäíîé âèëêå è ëèøü îäèí âçÿë äâå, òàê÷òî, ïîêà îí íå ïîåñò, îñòàëüíûå áóäóò æäàòü. êíèãå [7] Ý. Òàííåíáàóì ïðèâîäèò ðåøåíèå5 , ïîçâîëÿþùåå èçáåæàòüòàêèõ íåäîñòàòêîâ.
 ýòîì ðåøåíèè êàæäîìó ôèëîñîôó ñîîòâåòñòâóåò ïåðåìåííàÿ, õðàíÿùàÿ åãî ñîñòîÿíèå : hungry, thinking èëè eating; ìàññèâýòèõ ïåðåìåííûõ íàçîâåì state. Êðîìå òîãî, êàæäîìó ôèëîñîôó ñîîòâåòñòâóåò ìüþòåêñ, íà êîòîðîì îí áëîêèðóåòñÿ äî òîãî ìîìåíòà, êîãäà åìó áóäåòìîæíî ïðèñòóïèòü ê òðàïåçå, ÷òîáû ïðè ýòîì íèêîìó íå ìåøàòü. Òàêîâûìñ÷èòàåòñÿ ìîìåíò, êîãäà íè îäèí èç åãî ñîñåäåé (íè ñëåâà, íè ñïðàâà) íå ïðèñòóïèë ê åäå è íå ïðèíÿë ðåøåíèå ïðèñòóïàòü ê åäå.
Åñëè â òîò ìîìåíò, êîãäàôèëîñîô ïðîãîëîäàëñÿ, îáà ñîñåäà ðàçìûøëÿëè, ôèëîñîô ñàì ñåáå âçâîäèòñâîé ìüþòåêñ, ïîçâîëÿÿ ñàìîìó ñåáå íà÷àòü òðàïåçó, òî åñòü âûïîëíÿåò îïåðàöèþ unlock(); åñëè æå îäèí èç ñîñåäåé â ýòîò ìîìåíò åë, ôèëîñîô ìüþòåêñíå âçâîäèò. Íåñêîëüêèìè øàãàìè ïîçæå ôèëîñîô ïûòàåòñÿ çàõâàòèòü ñîáñòâåííûé ìüþòåêñ, ÷òî óäàåòñÿ åìó òîëüêî â ñëó÷àå, åñëè ïåðåä ýòèì îí åãîâçâåë.  ïðîòèâíîì ñëó÷àå ôèëîñîô áóäåò æäàòü (â ðåæèìå áëîêèðîâêè íàìüþòåêñå) äî òåõ ïîð, ïîêà ñîñåä, óòîëèâ ãîëîä, íå ïðåäëîæèò åìó ïîäêðåïèòüñÿ. Ïðè ýòîì ôèëîñîô ïðèñòóïèò ê òðàïåçå òîëüêî â òîì ñëó÷àå, åñëè âòîðîé åãî ñîñåä òàêæå â íàñòîÿùèé ìîìåíò íå åñò, èíà÷å îí ïðîäîëæèòæäàòü, óïîâàÿ íà òî, ÷òî óæå âòîðîé ñîñåä, íàñûòèâøèñü, íàïîìíèò íàøåìóìóäðåöó, ÷òî ïðèøëî âðåìÿ óòîëèòü ãîëîä.Îòìåòèì, ÷òî â ýòîì ðåøåíèè ìüþòåêñû, ñâÿçàííûå ñ âèëêàìè, îêàçûâàþòñÿ íå íóæíû: àëãîðèòì è òàê ãàðàíòèðóåò, ÷òî äâà ôèëîñîôà íèêîãäà íåïîïûòàþòñÿ ñõâàòèòü îäíó âèëêó îäíîâðåìåííî.Òàêæå ïîòðåáóåòñÿ îäèí îáùèé ìüþòåêñ äëÿ çàùèòû ìàññèâà state.Ñîîòâåòñòâóþùèé êîä ïðèâåäåí íèæå.
Öåíòðàëüíîå ìåñòî â íåì çàíèìàåòôóíêöèÿ test(). Ñ åå ïîìîùüþ êàæäûé ôèëîñîô, ïðîãîëîäàâøèñü, îïðåäåëÿåò, ñëåäóåò ëè åìó ïðÿìî ñåé÷àñ ïðèñòóïàòü ê òðàïåçå. Óòîëèâ æå ãîëîä,ôèëîñîô âûçûâàåò ôóíêöèþ test() äëÿ ñîñåäåé (ýòî è åñòü íàøå ëþáåçíîåïðåäëîæåíèå ïîäêðåïèòüñÿ), â ðåçóëüòàòå ÷åãî, åñëè ñîîòâåòñòâóþùèé ñîñåäãîëîäåí, à ñîñåäè ñîñåäà â íàñòîÿùåå âðåìÿ íå åäÿò, ïðîèñõîäèò âçâåäåíèåìüþòåêñà (è ôèëîñîô, íàõîäèâøèéñÿ â ñîñòîÿíèè áëîêèðîâêè, ïðèñòóïàåò êòðàïåçå).5 Íàøòåêñò, ïðèâåäåííûé íèæå, îò ðåøåíèÿ Ý. Òàííåíáàóìà íåñêîëüêî îòëè÷àåòñÿ167enum possible_states { hungry, eating, thinking };int state[5] = { thinking, thinking, thinking, thinking, thinking };mutex mut[5]; // â íà÷àëå îíè çàïåðòûmutex state_mut; // â íà÷àëå îòêðûòvoid philosopher(int n) {for(;;) {think();take_forks(n);eat();put_forks(n);}}void take_forks(int i) {lock(state_mut);state[i] = hungry;test(i);unlock(state_mut);lock(mut[i]);/* åñëè ôèëîñîô íå ðàçðåøèë ñàì ñåáå íà÷àòü òðàïåçó, çäåñü îíáóäåò æäàòü, ïîêà åìó î òðàïåçå íå íàïîìíÿò ñîñåäè */}void put_forks(int i) {lock(state_mut);state[i] = thinking;/* òåïåðü ëþáåçíî ïîèíòåðåñóåìñÿ, íå õîòÿò ëè íàøè ñîñåäè êóøàòü */test(left(i));test(right(i));unlock(state_mut);}void test(int i) {if(state[i] == hungry &&state[left(i)] != eating && state[right(i)] != eating){ /* íàñòàë ÷åðåä i-ãî ôèëîñîôà ïîåñòü */state[i] = eating;unlock(mut[i]);}}28.2.5Ïîíÿòèå ãðàôà îæèäàíèÿÑóùåñòâóþò ðàçëè÷íûå ïîäõîäû ê àâòîìàòè÷åñêîìó îòñëåæèâàíèþ íàñòóïëåíèÿ òóïèêîâûõ ñèòóàöèé; îäíèì èç íèõ ÿâëÿåòñÿ àíàëèç ãðàôà îæèäàíèÿ.Ãðàô îæèäàíèÿ ïðåäñòàâëÿåò ñîáîé äâóäîëüíûé îðèåíòèðîâàííûé ãðàô,âåðøèíàìè êîòîðîãî ÿâëÿþòñÿ ïðîöåññû (ïåðâàÿ äîëÿ) è ðåñóðñû (âòîðàÿäîëÿ).
Ñèòóàöèÿ ïðîöåññ ìîíîïîëüíî âëàäååò ðåñóðñîì èçîáðàæàåòñÿ îðèåíòèðîâàííîé äóãîé îò ñîîòâåòñòâóþùåãî ðåñóðñà ê ñîîòâåòñòâóþùåìó ïðî168процессыресурсыÐèñ. 29: Ïðèìåðû ãðàôà îæèäàíèÿöåññó. Íàïðîòèâ, ñèòóàöèÿ ïðîöåññ çàáëîêèðîâàí â îæèäàíèè îñâîáîæäåíèÿðåñóðñà èçîáðàæàåòñÿ äóãîé îò ïðîöåññà ê ðåñóðñó.Ïîÿâëåíèå â ãðàôå îæèäàíèÿ îðèåíòèðîâàííûõ öèêëîâ îçíà÷àåòíàëè÷èå â ñèñòåìå ñèòóàöèè òóïèêà.Íà ðèñ. 29 äàíû ïðèìåðû ãðàôà îæèäàíèÿ. Ñëåâà ïîêàçàí ãðàô îæèäàíèÿ ñ ÷åòûðüìÿ ïðîöåññàìè è øåñòüþ ðåñóðñàìè; â ýòîé ñèñòåìå òóïèêîâîéñèòóàöèè ïîêà íåò.  ñåðåäèíå ïðèâåäåí ïðèìåð ïðîñòåéøåé òóïèêîâîé ñèòóàöèè (ýòîò ïðèìåð íàìè óæå ðàññìàòðèâàëñÿ íà ñòð. 163).
Ñïðàâà ïîêàçàíãðàô îæèäàíèÿ äëÿ çàäà÷è î ïÿòè ôèëîñîôàõ â òîò ìîìåíò, êîãäà âñå ïÿòåðîîäíîâðåìåííî âçÿëè ïî îäíîé (ëåâîé) âèëêå.28.3Ïðîáëåìà ÷èòàòåëåé è ïèñàòåëåéÅùå îäèí èíòåðåñíûé ïðèìåð ñâÿçàí ñ áàçîé äàííûõ, ê êîòîðîé îäíè ïðîöåññû (÷èòàòåëè) îñóùåñòâëÿþò äîñòóï òîëüêî íà ÷òåíèå, à äðóãèå (ïèñàòåëè) ìîãóò ïðîèçâîäèòü è çàïèñü.Êàê ìû íåîäíîêðàòíî óáåæäàëèñü, äîñòóï íåñêîëüêèõ ïðîöåññîâ íà çàïèñü îäíèõ è òåõ æå äàííûõ ïðèâîäèò ê ïðîáëåìàì (ñèòóàöèÿì ãîíîê). Çàìåòèì òåïåðü, ÷òî, äàæå åñëè èç äâóõ îäíîâðåìåííî îñóùåñòâëÿþùèõ äîñòóïïðîöåññîâ îäèí òîëüêî ÷èòàåò äàííûå, à ìîäèôèêàöèåé çàíèìàåòñÿ òîëüêîâòîðîé, ýòî âñå ðàâíî ìîæåò ïðèâåñòè ê ñèòóàöèè ãîíîê, êàê ìû óæå âèäåëèâ ïðèìåðå ñ ïîäñ÷åòîì îñòàòêîâ äåíåã íà áàíêîâñêèõ ñ÷åòàõ (ñì. ñòð. 149). òî æå âðåìÿ ïðîöåññû, îñóùåñòâëÿþùèå îäíîâðåìåííûé äîñòóï òîëüêîíà ÷òåíèå (áåç âìåøàòåëüñòâà ïèøóùèõ ïðîöåññîâ), ïîìåøàòü äðóã äðóãó íåìîãóò.Òàêèì îáðàçîì, çàäà÷à ÷èòàòåëåé è ïèñàòåëåé ñîñòîèò â òîì, ÷òîáû ïîçâîëèòü îäíîâðåìåííûé äîñòóï ê äàííûì ïðîèçâîëüíîìó ÷èñëó ÷èòàòåëåé, íîïðè ýòîì òàê, ÷òîáû íàëè÷èå õîòÿ áû îäíîãî ÷èòàòåëÿ èñêëþ÷àëî äîñòóï ïèñàòåëåé, à íàëè÷èå õîòÿ áû îäíîãî ïèñàòåëÿ èñêëþ÷àëî äîñòóï âîîáùå êîãî169áû òî íè áûëî, âêëþ÷àÿ è ÷èòàòåëåé.Äëÿ ðåøåíèÿ çàäà÷è ââåäåì îáùóþ ïåðåìåííóþ, êîòîðàÿ áóäåò ïîêàçûâàòü òåêóùåå êîëè÷åñòâî ÷èòàòåëåé (íàçîâåì åå rc îò ñëîâ readers count).Ýòî ïîçâîëèò ïåðâîìó ïðèøåäøåìó ÷èòàòåëþ óçíàòü, ÷òî îí ïåðâûé, è áëîêèðîâàòü äîñòóï ê áàçå äëÿ ïèñàòåëåé, à ïîñëåäíåìó óõîäÿùåìó ÷èòàòåëþ −óçíàòü, ÷òî îí ïîñëåäíèé, è ðàçáëîêèðîâàòü äîñòóï.
Äëÿ áëîêèðîâêè äîñòóïà ê äàííûì âîñïîëüçóåìñÿ ìüþòåêñîì db_mutex, à äëÿ çàùèòû öåëîñòíîñòèïåðåìåííîé rc íàì ïîòðåáóåòñÿ åùå îäèí ìüþòåêñ − rc_mutex.Ïðîöåäóðà çàïèñè â îáëàñòü îáùèõ äàííûõ (ïèñàòåëü) áóäåò äîñòàòî÷íîïðîñòîé:void writer(...) {lock(db_mutex);/* ... ïèøåì äàííûå â îáùóþ ïàìÿòü ... */unlock(db_mutex);}Ïðîöåäóðà ÷èòàòåëÿ îêàæåòñÿ ñóùåñòâåííî ñëîæíåå, ò.ê. òðåáóåò ìàíèïóëÿöèé ñ ïåðåìåííîé rc. ×èòàòåëü ïðåæäå âñåãî ïðîâåðÿåò, íå ïåðâûé ëè îíñðåäè ÷èòàòåëåé.
Åñëè â íàñòîÿùèé ìîìåíò åñòü äðóãèå ÷èòàòåëè, îñóùåñòâëÿþùèå äîñòóï ê îáùåé ïàìÿòè, ÷èòàòåëü ïðîñòî ïðèñîåäèíÿåòñÿ ê íèì, îòðàçèâ ôàêò ñâîåãî ïðèñóòñòâèÿ â ïåðåìåííîé rc; åñëè æå äðóãèõ ÷èòàòåëåé íåò,ïåðâûé ïðèøåäøèé ÷èòàòåëü ñíà÷àëà äîæèäàåòñÿ, ïîêà êðèòè÷åñêóþ ñåêöèþíå ïîêèíåò ïèñàòåëü (åñëè, êîíå÷íî, òàêîâîé åñòü) − ýòî äåëàåòñÿ ñ ïîìîùüþáëîêèðîâêè ìüþòåêñà db_mutex. Åñëè â ýòî âðåìÿ ê âõîäó â êðèòè÷åñêóþñåêöèþ ïîäîéäóò äðóãèå ÷èòàòåëè, îíè áëîêèðóþòñÿ íà ìüþòåêñå, çàùèùàþùåì ïåðåìåííóþ rc (rc_mutex â ýòîò ìîìåíò âñå åùå óäåðæèâàåò ÷èòàòåëü,ïðèøåäøèé ïåðâûì).void reader(...) {lock(rc_mutex);rc++;if(rc == 1) lock(db_mutex); /* ïåðâûé! */unlock(rc_mutex);/* ...
÷èòàåì äàííûå èç îáùåé ïàìÿòè ... */lock(rc_mutex);rc--;if(rc == 0) unlock(db_mutex); /* óõîäÿ, ãàñèòå ñâåò */unlock(rc_mutex);}170Ëåêöèÿ 142929.1Ñåìàôîðû è ìüþòåêñû â ÎÑ UnixÄâà òèïà ñåìàôîðîâ â ÎÑ Unix ñîâðåìåííûõ âåðñèÿõ ÎÑ Unix ñåìàôîðû ïðåäñòàâëåíû â äâóõ âàðèàíòàõ: ñåìàôîðû System V IPC è ñåìàôîðû POSIX.29.1.1Ñåìàôîðû System V IPCÏîäñèñòåìà System V IPC ïðåäîñòàâëÿåò òðè âèäà îáúåêòîâ ÿäðà, ïðåäíàçíà÷åííûõ äëÿ âçàèìîäåéñòâèÿ ïðîöåññîâ:• î÷åðåäè ñîîáùåíèé;• îáëàñòè ðàçäåëÿåìîé ïàìÿòè1 ;• ìàññèâû ñåìàôîðîâ.Âñå òðè âèäà îáúåêòîâ ñóùåñòâóþò íåçàâèñèìî îò ïîðîäèâøèõ èõ ïðîöåññîâ, òî åñòü ñîçäàííûé îáúåêò íåîáõîäèìî â ÿâíîì âèäå óíè÷òîæèòü, â ïðîòèâíîì ñëó÷àå îí îñòàíåòñÿ â ÿäðå ÎÑ äî ïåðåçàãðóçêè. Äîñòóï ê îáúåêòàìIPC ìîæåò ïîëó÷èòü ëþáîé ïðîöåññ, èìåþùèé ñîîòâåòñòâóþùèå ïîëíîìî÷èÿ(èñïîëüçóþòñÿ ïðàâà äîñòóïà, àíàëîãè÷íûå ôàéëîâûì). Òàêèì îáðàçîì, ïðèíåîáõîäèìîñòè ìîæíî èñïîëüçîâàòü îáúåêòû System V IPC äëÿ âçàèìîäåéñòâèÿ ïðîöåññîâ, ïðèíàäëåæàùèõ ðàçíûì ïîëüçîâàòåëÿì.Ñåìàôîðû System V ÿâëÿþòñÿ îáúåêòàìè ÿäðà, ïðè÷åì êàæäûé îáúåêòìîæåò ñîäåðæàòü íåñêîëüêî ñåìàôîðîâ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
