А.В. Столяров - Введение в операционные системы (1152218), страница 35
Текст из файла (страница 35)
Îäíàêî ñåìàôîð ìîæíî èñïîëüçîâàòü âáîëåå ñëîæíîé ðîëè, à èìåííî, êàê ñ÷åò÷èê äîñòóïíûõ ðåñóðñîâ.Íåêîòîðûå ðåàëèçàöèè îáîáùàþò îïåðàöèè íàä ñåìàôîðàìè, ââîäÿ äîïîëíèòåëüíûé öå-ëî÷èñëåííûé ïàðàìåòð. Îïåðàöèÿ up(sem, n) óâåëè÷èâàåò çíà÷åíèå ñåìàôîðà íà n, îïåðàöèÿdown(sem, n) æäåò, ïîêà çíà÷åíèå íå îêàæåòñÿ áîëüøèì ëèáî ðàâíûì n, è ïîñëå ýòîãî óìåíüøàåò çíà÷åíèå íà n.
Êðîìå òîãî, ðåàëèçàöèè îáû÷íî èìåþò íåáëîêèðóþùèé âàðèàíò îïåðàöèèdown(), àíàëîãè÷íûé íàøåé îïåðàöèè lock() äëÿ ìüþòåêñîâ, ðåàëèçîâàííîé â âèäå ëîãè÷åñêîé ôóíêöèè.  îòëè÷èå îò êëàññè÷åñêîãî âàðèàíòà, ýòîò âàðèàíò âìåñòî îæèäàíèÿ ñðàçóâîçâðàùàåò óïðàâëåíèå, óêàçûâàÿ, ÷òî îïåðàöèÿ ïðîøëà íåóäà÷íî. Áîëüøèíñòâî ñóùåñòâóþùèõ ðåàëèçàöèé ïîçâîëÿåò óçíàòü òåêóùåå çíà÷åíèå ñåìàôîðà èëè äàæå óñòàíîâèòü åãî áåçâñÿêèõ áëîêèðîâîê è ïðîâåðîê, ÷òî áûâàåò óäîáíî ïðè èíèöèàëèçàöèè ïðîãðàììû.Èçâåñòíàÿ ðåàëèçàöèÿ ñåìàôîðîâ èç System V IPC (ñì. [5]) ïðåäîñòàâëÿåò ìàññèâû ñåìàôîðîâ, íàä êîòîðûìè ìîæíî ïðîèçâîäèòü ñëîæíûå àòîìàðíûå îïåðàöèè, íàïðèìåð, óâåëè÷èòüòðåòèé ñåìàôîð íà äâà, à ÷åòâåðòûé óìåíüøèòü íà òðè çà îäíî (àòîìàðíîå!) äåéñòâèå. Êðîìå òîãî, â ýòîé ðåàëèçàöèè åñòü äîïîëíèòåëüíàÿ îïåðàöèÿ áëîêèðîâàòüñÿ, ïîêà ñåìàôîð íåñòàíåò ðàâåí íóëþ.15827.4.4Êîìàíäà TSLÍà íåêîòîðûõ àðõèòåêòóðàõ ìîæíî ðåàëèçîâàòü ìüþòåêñ áåç îáðàùåíèÿê ÿäðó.
Äëÿ ýòîãî íåîáõîäèìà ïðîöåññîðíàÿ êîìàíäà TSL (test and set lock,ïðîâåðèòü è çàêðûòü). Êîìàíäà èìååò äâà îïåðàíäà: ðåãèñòð è àäðåñ â ïàìÿòè. Ñóòü êîìàíäû â òîì, ÷òîáû çà îäíî íåäåëèìîå (àòîìàðíîå) äåéñòâèåïîìåñòèòü â ðåãèñòð ñîäåðæèìîå ÿ÷åéêè ïàìÿòè, ðàñïîëîæåííîé ïî óêàçàííîìó àäðåñó, à â ñàìó ÿ÷åéêó çàíåñòè íåêîòîðîå ôèêñèðîâàííîå çíà÷åíèå,íàïðèìåð 1. Òàêèì îáðàçîì, ìîæíî â îäíî äåéñòâèå óñòàíîâèòü ïåðåìåííîéìüþòåêñó çíà÷åíèå (êîòîðîå áóäåò ñîîòâåòñòâîâàòü ñîñòîÿíèþ çàïåðò) èñîõðàíèòü äëÿ ïðîâåðêè òî çíà÷åíèå, êîòîðîå áûëî â ïåðåìåííîé-ìüþòåêñåðàíüøå. Åñëè ðàíüøå ìüþòåêñ ñîäåðæàë çíà÷åíèå îòêðûò − çíà÷èò, íàøàîïåðàöèÿ ïðîøëà óñïåøíî. Åñëè æå çíà÷åíèå óæå áûëî çàêðûò, íåîáõîäèìî ïîäîæäàòü.Ðåàëèçàöèÿ ôóíêöèé lock() è unlock() íà àññåìáëåðå áóäåò âûãëÿäåòüïðèìåðíî òàê:mutex: DB 0lock:TSL RX, mutexCMP RX, 0JE okJMP lockok:RETunlock: MOV mutex, 0RETÊàê ìîæíî çàìåòèòü, çäåñü ìû ñíîâà âîçâðàùàåìñÿ ê àêòèâíîìó îæèäàíèþ.ßñíî, ÷òî îñóùåñòâèòü áëîêèðîâêó áåç ó÷àñòèÿ îïåðàöèîííîé ñèñòåìû íåâîçìîæíî.
Îäíàêî ïðè íåêîòîðûõ óñëîâèÿõ â ïðîãðàììàõ, èñïîëüçóþùèõ ëåãêîâåñíûå ïðîöåññû (òðåäû), òàêàÿ ðåàëèçàöèÿ ìüþòåêñà9 îêàçûâàåòñÿ áîëååýôôåêòèâíîé çà ñ÷åò ýêîíîìèè íà ïåðåêëþ÷åíèè êîíòåêñòîâ (ñ ïðîöåññà íàÿäðî è îáðàòíî).Ïðè ðàáîòå ñ ëåãêîâåñíûìè ïðîöåññàìè ìîæíî ïåðåä ïåðåõîäîì íà íà÷àëî ïðîöåäóðûlock()(ò.å. ñðàçó ïîñëå êîìàíäû óñëîâíîãî ïåðåõîäà) âñòàâèòü îáðàùåíèå ê ïðîöåäóðå ïåðå-êëþ÷åíèÿ ëåãêîâåñíûõ ïðîöåññîâ, ÷òîáû óìåíüøèòü ïîòåðè îò àêòèâíîãî îæèäàíèÿ.9Âàíãëîÿçû÷íîé ëèòåðàòóðå åå èíîãäà íàçûâàþòspinlock.159Ëåêöèÿ 13Íà ýòîé ëåêöèè ìû ðàññìîòðèì íåñêîëüêî êëàññè÷åñêèõ ïðèìåðîâ ïðîãðàììèðîâàíèÿ ñ èñïîëüçîâàíèåì ìüþòåêñîâ è ñåìàôîðîâ.2828.1Ïðèìåðû âçàèìîèñêëþ÷åíèéÇàäà÷à ïðîèçâîäèòåëåé è ïîòðåáèòåëåéÏóñòü èìåþòñÿ íåñêîëüêî ïðîöåññîâ, ïðîèçâîäÿùèõ äàííûå, ïîäëåæàùèåäàëüíåéøåé îáðàáîòêå.
Ýòî ìîãóò áûòü, íàïðèìåð, ïðîöåññû, îïðàøèâàþùèåêàêèå-ëèáî äàò÷èêè; òàêæå ýòî ìîãóò áûòü ïðîöåññû, ïîëó÷àþùèå îïðåäåëåííûå äàííûå ïî ñåòè ñ äðóãèõ ìàøèí è ïðåîáðàçóþùèå èõ â íåêîòîðîåâíóòðåííåå ïðåäñòàâëåíèå; âîçìîæíî, ÷òî äàííûå ïîëó÷àþòñÿ â ðåçóëüòàòåèíòåðàêòèâíîãî âçàèìîäåéñòâèÿ ñ ïîëüçîâàòåëåì èëè, íàîáîðîò, âû÷èñëÿþòñÿ â õîäå ìàòåìàòè÷åñêèõ ðàñ÷åòîâ. Íàçîâåì ýòè ïðîöåññû ïðîèçâîäèòåëÿìè.Ñ äðóãîé ñòîðîíû, èìåþòñÿ íåñêîëüêî ïðîöåññîâ, îáðàáàòûâàþùèõ (ïîòðåáëÿþùèõ ) äàííûå, ïîäãîòîâëåííûå ïðîöåññàìè-ïðîèçâîäèòåëÿìè. Ýòèïðîöåññû ìû íàçîâåì ïîòðåáèòåëÿìè.Çàäà÷à ïðîèçâîäèòåëåé è ïîòðåáèòåëåé, ïðåäíàçíà÷åííàÿ äëÿ èëëþñòðàöèè ïðèìåíåíèÿ ñåìàôîðîâ, ðàññìàòðèâàåò ñëåäóþùèé âàðèàíò ïåðåäà÷è èíôîðìàöèè îò ïðîèçâîäèòåëåé ïîòðåáèòåëÿì.
Ïóñòü êàæäàÿ ïîðöèÿ èíôîðìàöèè, ïîäãîòàâëèâàåìàÿ ïðîèçâîäèòåëåì è îáðàáàòûâàåìàÿ ïîòðåáèòåëåì,èìååò ôèêñèðîâàííûé ðàçìåð.  ðàçäåëÿåìîé ïàìÿòè îðãàíèçóåì áóôåð, ñïîñîáíûé õðàíèòü 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 . Ïîýòîìó êàæäûé ôèëîñîô, ïîðàçìûñëèâíåêîòîðîå âðåìÿ î íåïðåõîäÿùèõ êàòåãîðèÿõ è ðåøèâ ïîäêðåïèòüñÿ, ïûòàåòñÿ ñíà÷àëà âçÿòü â ëåâóþ ðóêó âèëêó, íàõîäÿùóþñÿ îò íåãî ñëåâà; åñëè âèëêàçàíÿòà, ôèëîñîô ñ ïîèñòèíå ôèëîñîôñêèì ñïîêîéñòâèåì îæèäàåò, ïîêà âèëêà íå îñâîáîäèòñÿ. Çàâëàäåâ ëåâîé âèëêîé, ôèëîñîô òî÷íî òàê æå ïûòàåòñÿâçÿòü âèëêó ñïðàâà, íå âûïóñêàÿ ïðè ýòîì ïåðâóþ âèëêó èç ëåâîé ðóêè. Ôèëîñîôû, êàê èçâåñòíî, îòëè÷àþòñÿ ôèëîñîôñêèì îòíîøåíèåì ê æèòåéñêèìòðóäíîñòÿì, òàê ÷òî êàæäûé ôèëîñîô ãîòîâ æäàòü ïîÿâëåíèÿ íóæíîé åìóâèëêè õîòü äî ñêîí÷àíèÿ âåêîâ (òî÷íåå, äî íàñòóïëåíèÿ ãîëîäíîé ñìåðòè,èáî áðåííûå òåëà, â îòëè÷èå îò ïðîñâåòëåííûõ óìîâ, òðåáóþò èíîãäà ïèùèîòíþäü íå äóõîâíîé).Çàâëàäåâ îáåèìè âèëêàìè, ôèëîñîô íåêîòîðîå âðåìÿ óòîëÿåò ãîëîä, çàòåìêëàäåò âèëêè îáðàòíî íà ñòîë è ïðîäîëæàåò ðàçìûøëÿòü î âå÷íûõ âîïðîñàõ,ïîêà ñíîâà íå ïðîãîëîäàåòñÿ.Ïðîáëåìà çàêëþ÷àåòñÿ â òîì, ÷òî âñå ïÿòü ôèëîñîôîâ ìîãóò ïðîãîëîäàòüñÿ îäíîâðåìåííî (ñ òî÷íîñòüþ äî âðåìåíè, çàòðà÷èâàåìîãî íà ïðîöåäóðóçàâëàäåíèÿ âèëêîé).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
