А.В. Столяров - Введение в операционные системы (1152218), страница 36
Текст из файла (страница 36)
 ýòîì ñëó÷àå âñå ôèëîñîôû óñïåþò âçÿòü âèëêè â ëåâûåðóêè, äà òàê è çàìðóò ñ ýòèìè âèëêàìè â îæèäàíèè, êîãäà æå ïîÿâèòñÿ âèëêàñïðàâà. Îäíàêî ñïðàâà âèëêà ìîæåò ïîÿâèòüñÿ òîëüêî òîãäà, êîãäà ïðàâûéñîñåä óòîëèò ãîëîä, à ýòîãî íå ïðîèñõîäèò, âåäü ó íåãî òîæå òîëüêî îäíà âèëêà.  ðåçóëüòàòå íàøè äîñòîéíåéøèå ìóäðûå ìóæè áåçâðåìåííî ïîêèíóò ñåéìèð, òàê è íå äîæäàâøèñü âòîðûõ âèëîê. Ýêàÿ íåïðèÿòíàÿ ñèòóàöèÿ!Èìåííî òàêèå ñèòóàöèè è íàçûâàþòñÿ òóïèêàìè 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 âîçìîæíà ñèòóàöèÿ, êîãäà âñå îíè óñïåþò âûïîëíèòü áëîêèðîâêó, ïîìå÷åííóþâ ëèñòèíãå âîñêëèöàòåëüíûì çíàêîì.
Ïðè ýòîì âñå ïÿòü âèëîê (ìüþòåêñîâ) îêàæóòñÿ áëîêèðîâàíû, òàê ÷òî âñå ïðîöåññû òàêæå çàáëîêèðóþòñÿ íàñëåäóþùåé ñòðîêå ïðîöåäóðû ïðè ïîïûòêå ïîëó÷èòü âòîðóþ âèëêó.Îäíèì èç ïðîñòåéøèõ ìåõàíèçìîâ èçáåæàíèÿ âçàèìîáëîêèðîâêè â çàäà÷åî ïÿòè ôèëîñîôàõ ÿâëÿåòñÿ ïðèìåíåíèå ñåìàôîðà, íå ïîçâîëÿþùåãî ôèëîñîôàì ïðèñòóïàòü ê òðàïåçå âñåì îäíîâðåìåííî. Çàâåäåì ñåìàôîð è íàçîâåìåãî 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Ïðîáëåìà ÷èòàòåëåé è ïèñàòåëåéÅùå îäèí èíòåðåñíûé ïðèìåð ñâÿçàí ñ áàçîé äàííûõ, ê êîòîðîé îäíè ïðîöåññû (÷èòàòåëè) îñóùåñòâëÿþò äîñòóï òîëüêî íà ÷òåíèå, à äðóãèå (ïèñàòåëè) ìîãóò ïðîèçâîäèòü è çàïèñü.Êàê ìû íåîäíîêðàòíî óáåæäàëèñü, äîñòóï íåñêîëüêèõ ïðîöåññîâ íà çàïèñü îäíèõ è òåõ æå äàííûõ ïðèâîäèò ê ïðîáëåìàì (ñèòóàöèÿì ãîíîê).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
