А.В. Столяров - Введение в операционные системы (1114673), страница 35
Текст из файла (страница 35)
Íàçîâåì ýòè ïðîöåññû ïðîèçâîäèòåëÿìè.Ñ äðóãîé ñòîðîíû, èìåþòñÿ íåñêîëüêî ïðîöåññîâ, îáðàáàòûâàþùèõ (ïîòðåáëÿþùèõ ) äàííûå, ïîäãîòîâëåííûå ïðîöåññàìè-ïðîèçâîäèòåëÿìè. Ýòèïðîöåññû ìû íàçîâåì ïîòðåáèòåëÿìè.Çàäà÷à ïðîèçâîäèòåëåé è ïîòðåáèòåëåé, ïðåäíàçíà÷åííàÿ äëÿ èëëþñòðàöèè ïðèìåíåíèÿ ñåìàôîðîâ, ðàññìàòðèâàåò ñëåäóþùèé âàðèàíò ïåðåäà÷è èíôîðìàöèè îò ïðîèçâîäèòåëåé ïîòðåáèòåëÿì. Ïóñòü êàæäàÿ ïîðöèÿ èíôîðìàöèè, ïîäãîòàâëèâàåìàÿ ïðîèçâîäèòåëåì è îáðàáàòûâàåìàÿ ïîòðåáèòåëåì,èìååò ôèêñèðîâàííûé ðàçìåð.  ðàçäåëÿåìîé ïàìÿòè îðãàíèçóåì áóôåð, ñïîñîáíûé õðàíèòü N òàêèõ ïîðöèé èíôîðìàöèè.ßñíî, ÷òî ðàáîòà ñ òàêèì áóôåðîì òðåáóåò âçàèìîèñêëþ÷åíèÿ. Äëÿ óïðîùåíèÿ ðàáîòû áóäåì ñ÷èòàòü, ÷òî áóôåð ïðåäñòàâëÿåò ñîáîé åäèíîå öåëîå1 , èíà âðåìÿ ðàáîòû ëþáîãî ïðîöåññà ñ áóôåðîì èñêëþ÷àòü îáðàùåíèÿ ê áóôåðóäðóãèõ ïðîöåññîâ.Îäíàêî ïðîáëåìà âçàèìîèñêëþ÷åíèÿ â äàííîì ñëó÷àå îêàçûâàåòñÿ íååäèíñòâåííîé. Äåëî â òîì, ÷òî ïðè âçàèìîäåéñòâèè ïîòðåáèòåëåé è ïðîèçâîäèòåëåé âîçìîæíû äâå (ñèììåòðè÷íûå) ñèòóàöèè, òðåáóþùèå áëîêèðîâêè:• ïîòðåáèòåëü ãîòîâ ê ïîëó÷åíèþ ïîðöèè äàííûõ, íî â áóôåðå íåò íèîäíîé ïîðöèè äàííûõ (áóôåð ïóñò);• ïðîèçâîäèòåëü ïîäãîòîâèë ê çàïèñè â áóôåð ïîðöèþ äàííûõ, íî çàïèñûâàòü åå íåêóäà (âñå ñëîòû áóôåðà çàíÿòû).1 Ýòîòàê è åñòü, åñëè â áóôåðå, íàïðèìåð, èìåþòñÿ ãëîáàëüíûå äàííûå î òîì, êàêèå èç ñëîòîâ ñâîáîäíû,à êàêèå çàíÿòû160 îáîèõ ñëó÷àÿõ ïðîöåññó íåîáõîäèìî äîæäàòüñÿ, êîãäà äðóãîé ïðîöåññ èçìåíèò ñîñòîÿíèå áóôåðà (â ïåðâîì ñëó÷àå, ïîòðåáèòåëþ − êîãäà ïðîèçâîäèòåëüçàïèøåò íîâûå äàííûå, âî âòîðîì ñëó÷àå, íàîáîðîò, ïðîèçâîäèòåëþ − êîãäàïîòðåáèòåëü çàáåðåò êàêèå-òî óæå èìåþùèåñÿ äàííûå).Ïðîñòåéøàÿ âîçìîæíàÿ ñòðàòåãèÿ ñîñòîèò â òîì, ÷òîáû áëîêèðîâàòü îïåðàöèè íàä áóôåðîì (âîéòè â êðèòè÷åñêóþ ñåêöèþ), ïðîâåðèòü, íå èçìåíèëîñüëè ñîîòâåòñòâóþùèì îáðàçîì ñîñòîÿíèå áóôåðà è, åñëè îíî íå èçìåíèëîñü,âûéòè èç êðèòè÷åñêîé ñåêöèè, íè÷åãî â áóôåðå íå ïîìåíÿâ, à çàòåì îïÿòüâîéòè, è ò.ä., òî åñòü, ïîïðîñòó ãîâîðÿ, âûïîëíÿòü öèêëè÷åñêè ïðîâåðêó èçìåíåíèé.
Èíà÷å ãîâîðÿ, òàêàÿ ñòðàòåãèÿ ïðåäñòàâëÿåò ñîáîé àêòèâíîå îæèäàíèå, òîëüêî íå íà âõîäå â êðèòè÷åñêóþ ñåêöèþ, à â ïðîöåññå ðàáîòû.Êàê óæå ãîâîðèëîñü, àêòèâíîå îæèäàíèå − èäåÿ êðàéíå íåóäà÷íàÿ. Ïîýòîìó ñëåäóåò ïðèäóìàòü òàêîé ìåõàíèçì, ïðè êîòîðîì ïðîöåññû, ïîïàâøèå âîïèñàííûå ñèòóàöèè, âîîáùå íå áóäóò çàõîäèòü â êðèòè÷åñêóþ ñåêöèþ, ïîêàâ áóôåðå íå ïîÿâÿòñÿ äàííûå (äëÿ ïîòðåáèòåëÿ) ëèáî ñâîáîäíûå ñëîòû (äëÿïðîèçâîäèòåëÿ).void producer() {/* ... ïîäãîòîâèòüäàííûå ...*/down(empty);lock(m);put_data();unlock(m);up(full);}void consumer() {down(full);lock(m);get_data();unlock(m);up(empty);/* ... îáðàáîòàòüäàííûå ...*/}Ðèñ. 27: Ïðîèçâîäèòåëè è ïîòðåáèòåëèÄëÿ ýòîãî ìû âîñïîëüçóåìñÿ ñåìàôîðàìè Äåéêñòðû â êà÷åñòâå ñ÷åò÷èêîâ äîñòóïíûõ ðåñóðñîâ.
 çàäà÷å áóäóò èñïîëüçîâàòüñÿ äâà ñåìàôîðà: îäèíáóäåò ñ÷èòàòü ñâîáîäíûå ñëîòû (è íà íåì áóäóò áëîêèðîâàòüñÿ ïðîöåññûïðîèçâîäèòåëè, åñëè ñâîáîäíûõ ñëîòîâ íåò), âòîðîé áóäåò ñ÷èòàòü ñëîòû, çàïîëíåííûå äàííûìè (è íà íåì áóäóò áëîêèðîâàòüñÿ ïðîöåññû-ïîòðåáèòåëè,åñëè íåò ãîòîâûõ äàííûõ). Íàçîâåì ýòè ñåìàôîðû, ñîîòâåòñòâåííî, empty èfull; â íà÷àëå ðàáîòû (îäíîâðåìåííî ñ ñîçäàíèåì áóôåðà) âûïîëíèì îïåðàöèþ up(empty) ñòîëüêî ðàç, ñêîëüêî â áóôåðå èìååòñÿ ñâîáîäíûõ ñëîòîâ.Ìüþòåêñ, áëîêèðóþùèé îïåðàöèè ñ áóôåðîì, íàçîâåì m, à ïðîöåäóðû äëÿïîìåùåíèÿ äàííûõ â áóôåð è èçâëå÷åíèÿ äàííûõ èç áóôåðà − ñîîòâåòñòâåííî161Ðèñ.
28: Îáåäàþùèå ôèëîñîôûput_data() è get_data(). Ðåøåíèå ïîêàçàíî íà ðèñ. 27.Âàæíî ïîíèìàòü, ÷òî ñåìàôîðû â äàííîì ñëó÷àå èñïîëüçóþòñÿ íå äëÿâçàèìîèñêëþ÷åíèÿ êðèòè÷åñêèõ ñåêöèé, à äëÿ áëîêèðîâàíèÿ ïðîöåññîâ, êîòîðûå âñå ðàâíî íå ìîãóò ñäåëàòü íè÷åãî ïîëåçíîãî.28.2Çàäà÷à î ïÿòè ôèëîñîôàõ è ïðîáëåìà òóïèêîâÏðè ñîâìåñòíîé ðàáîòå íåñêîëüêèõ ïðîöåññîâ ñ íåñêîëüêèìè ðåñóðñàìèâîçìîæíà ñèòóàöèÿ, ïðè êîòîðîé äâà èëè áîëüøå ó÷àñòíèêîâ âçàèìîäåéñòâèÿîêàçûâàþòñÿ â ñîñòîÿíèè áëîêèðîâêè, èç êîòîðîãî êàæäûé ìîã áû âûéòè,åñëè áû äðóãîé îñâîáîäèë íåêèé ðåñóðñ, íî ýòîò äðóãîé îñâîáîäèòü ðåñóðñ íåìîæåò, ò.ê.
ñàì òîæå íàõîäèòñÿ â áëîêèðîâàííîì ñîñòîÿíèè.28.2.1Îáåäàþùèå ôèëîñîôûÄëÿ èëëþñòðàöèè ïðîáëåìû òóïèêîâ Ýäñãåð Äåéêñòðà ïðåäëîæèë øóòî÷íóþ çàäà÷ó î ïÿòè îáåäàþùèõ ôèëîñîôàõ.Çà êðóãëûì îáåäåííûì ñòîëîì ñèäÿò ïÿòü ôèëîñîôîâ, ðàçìûøëÿþùèõî âûñîêèõ ôèëîñîôñêèõ ìàòåðèÿõ.  ñåðåäèíå ñòîëà ñòîèò áîëüøàÿ òàðåëêàñïàãåòòè. Ìåæäó êàæäûìè äâóìÿ ôèëîñîôàìè íà ñòîëå ðàñïîëàãàåòñÿ âèëêà,ò.å. âèëîê òîæå ïÿòü, ïðè÷åì êàæäûé ôèëîñîô ìîæåò âçÿòü âèëêó ñëåâà (åñëèåþ â äàííûé ìîìåíò íå ïîëüçóåòñÿ ëåâûé ñîñåä) è âèëêó ñïðàâà (åñëè åþ âäàííûé ìîìåíò íå ïîëüçóåòñÿ ïðàâûé ñîñåä).Ïîñêîëüêó ñïàãåòòè îòëè÷àþòñÿ èçðÿäíîé äëèíîé, äëÿ åäû êàæäîìó ôè162ëîñîôó íåîáõîäèìî äâå âèëêè2 .
Ïîýòîìó êàæäûé ôèëîñîô, ïîðàçìûñëèâíåêîòîðîå âðåìÿ î íåïðåõîäÿùèõ êàòåãîðèÿõ è ðåøèâ ïîäêðåïèòüñÿ, ïûòàåòñÿ ñíà÷àëà âçÿòü â ëåâóþ ðóêó âèëêó, íàõîäÿùóþñÿ îò íåãî ñëåâà; åñëè âèëêàçàíÿòà, ôèëîñîô ñ ïîèñòèíå ôèëîñîôñêèì ñïîêîéñòâèåì îæèäàåò, ïîêà âèëêà íå îñâîáîäèòñÿ. Çàâëàäåâ ëåâîé âèëêîé, ôèëîñîô òî÷íî òàê æå ïûòàåòñÿâçÿòü âèëêó ñïðàâà, íå âûïóñêàÿ ïðè ýòîì ïåðâóþ âèëêó èç ëåâîé ðóêè. Ôèëîñîôû, êàê èçâåñòíî, îòëè÷àþòñÿ ôèëîñîôñêèì îòíîøåíèåì ê æèòåéñêèìòðóäíîñòÿì, òàê ÷òî êàæäûé ôèëîñîô ãîòîâ æäàòü ïîÿâëåíèÿ íóæíîé åìóâèëêè õîòü äî ñêîí÷àíèÿ âåêîâ (òî÷íåå, äî íàñòóïëåíèÿ ãîëîäíîé ñìåðòè,èáî áðåííûå òåëà, â îòëè÷èå îò ïðîñâåòëåííûõ óìîâ, òðåáóþò èíîãäà ïèùèîòíþäü íå äóõîâíîé).Çàâëàäåâ îáåèìè âèëêàìè, ôèëîñîô íåêîòîðîå âðåìÿ óòîëÿåò ãîëîä, çàòåìêëàäåò âèëêè îáðàòíî íà ñòîë è ïðîäîëæàåò ðàçìûøëÿòü î âå÷íûõ âîïðîñàõ,ïîêà ñíîâà íå ïðîãîëîäàåòñÿ.Ïðîáëåìà çàêëþ÷àåòñÿ â òîì, ÷òî âñå ïÿòü ôèëîñîôîâ ìîãóò ïðîãîëîäàòüñÿ îäíîâðåìåííî (ñ òî÷íîñòüþ äî âðåìåíè, çàòðà÷èâàåìîãî íà ïðîöåäóðóçàâëàäåíèÿ âèëêîé).
 ýòîì ñëó÷àå âñå ôèëîñîôû óñïåþò âçÿòü âèëêè â ëåâûåðóêè, äà òàê è çàìðóò ñ ýòèìè âèëêàìè â îæèäàíèè, êîãäà æå ïîÿâèòñÿ âèëêàñïðàâà. Îäíàêî ñïðàâà âèëêà ìîæåò ïîÿâèòüñÿ òîëüêî òîãäà, êîãäà ïðàâûéñîñåä óòîëèò ãîëîä, à ýòîãî íå ïðîèñõîäèò, âåäü ó íåãî òîæå òîëüêî îäíà âèëêà.  ðåçóëüòàòå íàøè äîñòîéíåéøèå ìóäðûå ìóæè áåçâðåìåííî ïîêèíóò ñåéìèð, òàê è íå äîæäàâøèñü âòîðûõ âèëîê. Ýêàÿ íåïðèÿòíàÿ ñèòóàöèÿ!Èìåííî òàêèå ñèòóàöèè è íàçûâàþòñÿ òóïèêàìè 3 .28.2.2Äðóãîé ïðèìåð òóïèêîâîé ñèòóàöèèÄëÿ âîçíèêíîâåíèÿ òóïèêà, âîîáùå ãîâîðÿ, äîñòàòî÷íî äâóõ ïðîöåññîâ èäâóõ ðåñóðñîâ. Ïóñòü èìåþòñÿ äâà ìüþòåêñà m1 è m2.
Åñëè ïåðâûé ïðîöåññâûïîëíÿåò êîä, ñîäåðæàùèé âûçîâûlock(m1);lock(m2);à âòîðîé â ýòî æå âðåìÿ âûïîëíÿåò êîä, ñîäåðæàùèé òå æå âûçîâû â îáðàòíîìïîðÿäêå:2 Ïîñêîëüêóîòâåò íà âîïðîñ, êàê æå åäÿò äâóìÿ âèëêàìè, ñòóäåíòû çàäàþò ñ çàâèäíîé ðåãóëÿðíîñòüþ,ïîçæå áûë ïðåäëîæåí äðóãîé âàðèàíò óñëîâèé çàäà÷è: çà ñòîëîì ñèäÿò âîñòî÷íûå ôèëîñîôû, ïåðåäíèìè áëþäî ñ ðèñîì, à íà ñòîëå ëåæàò íå âèëêè, à äåðåâÿííûå ïàëî÷êè äëÿ åäû. Âñåì èçâåñòíî, ÷òî ýòèõïàëî÷åê íóæíî äâå (ïðàâäà, äåðæàò èõ âñå æå îäíîé ðóêîé).3  àíãëîÿçû÷íîé ëèòåðàòóðå èñïîëüçóåòñÿ ñëîâî deadlock.163lock(m2);lock(m1);òî ïðè íåóäà÷íîì ñòå÷åíèè îáñòîÿòåëüñòâ îáà ïðîöåññà óñïåþò ñäåëàòü ïîîäíîìó âûçîâó è âîéäóò âî âçàèìíóþ áëîêèðîâêó íà âòîðûõ, ïîïàâ, òàêèìîáðàçîì, â òóïèê.28.2.3Òóïèêîâûå ñèòóàöèè áåç âçàèìîèñêëþ÷åíèéÑèòóàöèè âçàèìîáëîêèðîâêè âîçìîæíû íå òîëüêî ñ ó÷àñòèåì ñåìàôîðîâè ìüþòåêñîâ.
Ðàññìîòðèì äëÿ ïðèìåðà îäíó òàêóþ ñèòóàöèþ.Ïóñòü íàì íåîáõîäèìî çàïóñòèòü êîìàíäó ls äëÿ ïîëó÷åíèÿ â òåêñòîâîìâèäå ñïèñêà ôàéëîâ â òåêóùåì êàòàëîãå. Íà÷èíàþùèå ïðîãðàììèñòû ÷àñòîäåëàþò õàðàêòåðíóþ îøèáêó, ïðèìåíÿÿ ïðèìåðíî òàêîé êîä:char buf[100];int rc;int fd[2];pipe(fd);if(fork()==0) {dup2(fd[1], 1);close(fd[1]);close(fd[0]);execlp("ls", "ls", NULL);perror("ls");exit(1);}close(fd[1]);wait(NULL);while((rc = read(fd[0], buf, sizeof(buf)))>0) {/* ... */}Ëþáîïûòíî, ÷òî òàêàÿ ïðîãðàììà, âîîáùå ãîâîðÿ, ìîæåò è çàðàáîòàòü, îäíàêîìîæåò è çàâèñíóòü.
Ýêñïåðèìåíòèðóÿ ñ íåé, ìû, ñêîðåå âñåãî, îáíàðóæèì,÷òî ïðîãðàììà êîððåêòíî ðàáîòàåò â êàòàëîãàõ ñî ñðàâíèòåëüíî íåáîëüøèìêîëè÷åñòâîì ôàéëîâ, à íà áîëüøèõ êàòàëîãàõ çàâèñàåò.Ïðåæäå ÷åì ÷èòàòü äàëüøå, ðåêîìåíäóåì ÷èòàòåëþ ïîïûòàòüñÿ ñàìîñòîÿòåëüíî äîãàäàòüñÿ î ïðè÷èíàõ ýòîãî.Èòàê, ðàññìîòðèì ïðîãðàììó ïîäðîáíåå. Çàïóñêàåìàÿ íàìè â äî÷åðíåìïðîöåññå ïðîãðàììà ls â êà÷åñòâå äåñêðèïòîðà ñòàíäàðòíîãî âûâîäà ïîëó÷à164åò âõîäíîé äåñêðèïòîð êàíàëà, òàê ÷òî, ïðåæäå ÷åì çàâåðøèòüñÿ, îíà áóäåòçàïèñûâàòü â êàíàë èìåíà ôàéëîâ èç òåêóùåãî êàòàëîãà.Ìåæäó òåì ðîäèòåëüñêèé ïðîöåññ, äâèæèìûé áëàãîðîäíîé öåëüþ íåäîïóùåíèÿ çàñîðåíèÿ ñèñòåìíîé òàáëèöû çîìáè-ïðîöåññàìè, âûïîëíÿåò âûçîâwait(), â ðåçóëüòàòå ÷åãî áëîêèðóåòñÿ äî òåõ ïîð, ïîêà äî÷åðíèé ïðîöåññ íåçàâåðøèòñÿ. Ëèøü ïîñëå ýòîãî ðîäèòåëüñêèé ïðîöåññ âûïîëíÿåò ÷òåíèå èçêàíàëà. ðåçóëüòàòå ïîëó÷àåòñÿ, ÷òî âî âðåìÿ ðàáîòû äî÷åðíåãî ïðîöåññà (ïðîãðàììû ls) íèêòî èç êàíàëà íå ÷èòàåò.
Êàê íàì èçâåñòíî èç 19.1, ðàçìåðáóôåðà êàíàëà îãðàíè÷åí (îáû÷íî îí ñîñòàâëÿåò 4096 áàéò), òàê ÷òî, êîãäàáóôåð çàïîëíèòñÿ, î÷åðåäíîé âûçîâ write(), âûïîëíåííûé ïðîãðàììîé ls,çàáëîêèðóåòñÿ â îæèäàíèè îñâîáîæäåíèÿ ìåñòà â áóôåðå. Îäíàêî áóôåð îñâîáîæäàòü íåêîìó, ïîñêîëüêó ðîäèòåëüñêèé ïðîöåññ, áëîêèðîâàííûé íà âûçîâåwait(), äî ïåðâîãî âûçîâà read() íå äîøåë è íå äîéäåò, ïîêà äî÷åðíèé ïðîöåññ íå çàâåðøèòñÿ.Òàêèì îáðàçîì, èìååì çàìêíóòûé êðóã: ðîäèòåëüñêèé ïðîöåññ îæèäàåò,÷òî äî÷åðíèé çàâåðøèòñÿ, è íå âûïîëíÿåò ÷òåíèå èç êàíàëà, à äî÷åðíåìó,÷òîáû çàâåðøèòüñÿ, íåîáõîäèìî, â ñâîþ î÷åðåäü, ÷òîáû ðîäèòåëüñêèé íà÷àë÷èòàòü.Òàêèå çàìêíóòûå êðóãè âçàèìîáëîêèðîâîê è íàçûâàþòñÿ òóïèêîâûìè ñèòóàöèÿìè.Êàê óæå, íåñîìíåííî, äîãàäàëñÿ ÷èòàòåëü, â äàííîì ñëó÷àå âçàèìîáëîêèðîâêà âîçíèêíåò òîëüêî òîãäà, êîãäà âûäà÷à ls äëÿ äàííîãî êàòàëîãà ñîñòàâëÿåò 4096 áàéò è áîëüøå.ßñíî, ÷òî ïðèâåäåííîå ðåøåíèå î÷åíü ïðîñòî ïðåâðàòèòü â ïðàâèëüíîå:äîñòàòî÷íî ïåðåíåñòè âûçîâ wait() íà íåñêîëüêî ñòðîê íèæå, ÷òîáû îí âûïîëíÿëñÿ óæå ïîñëå âûïîëíåíèÿ âûçîâîâ read().28.2.4Âîçìîæíûå ðåøåíèÿ çàäà÷è î ïÿòè ôèëîñîôàõÄëÿ íà÷àëà ðàññìîòðèì ðåàëèçàöèþ çàäà÷è î ïÿòè ôèëîñîôàõ, äîïóñêàþùóþ âûøåîïèñàííóþ òóïèêîâóþ ñèòóàöèþ.
Çàâåäåì ìàññèâ èç ïÿòè ìüþòåêñîâ, êàæäûé èç êîòîðûõ ñâÿçàí ñ ñîîòâåòñòâóþùåé âèëêîé (îáîçíà÷èì ýòîòìàññèâ èäåíòèôèêàòîðîì forks4 ). È ôèëîñîôîâ, è âèëêè çàíóìåðóåì ÷èñëàìè îò 0 äî 4. Îïèøåì äâå âñïîìîãàòåëüíûå ôóíêöèè, ïîçâîëÿþùèå âû÷èñëèòüíîìåð ñîñåäà ñïðàâà è ñëåâà:int left(int n) { return (n - 1 + 5) % 5; }int right(int n) { return (n + 1) % 5; }4 Àíãëèéñêîåñëîâîforkáóêâàëüíî ïåðåâîäèòñÿ êàêâèëêà.165Áóäåì ñ÷èòàòü, ÷òî íîìåð âèëêè, ëåæàùåé ñëåâà îò ôèëîñîôà, ñîâïàäàåò ñíîìåðîì ñàìîãî ôèëîñîôà.Æèçíåííûé öèêë ôèëîñîôà òîãäà ìîæíî áóäåò ïðåäñòàâèòü ñëåäóþùåéïðîöåäóðîé:void philosopher(int n) {for(;;) {think();lock(forks[n]);/* ! */lock(forks[right(n)]);eat();unlock(forks[n]);unlock(forks[right(n)]);}}ßñíî, ÷òî ïðè îäíîâðåìåííîì âûïîëíåíèè òàêèõ ïðîöåäóð äëÿ n îò 0 äî 4 âîçìîæíà ñèòóàöèÿ, êîãäà âñå îíè óñïåþò âûïîëíèòü áëîêèðîâêó, ïîìå÷åííóþâ ëèñòèíãå âîñêëèöàòåëüíûì çíàêîì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
