А.В. Столяров - Введение в операционные системы (1152218), страница 34
Текст из файла (страница 34)
25: Âçàèìîèñêëþ÷åíèå íà îñíîâå ÷åðåäîâàíèÿ153Íà ðèñ.25 ïîêàçàíû äâà ïðîöåññà, îñóùåñòâëÿþùèå äîñòóï ê ðàçäåëÿåìûì äàííûì (ôóíêöèÿ section()) â ñîîòâåòñòâèè ñ ìàðêåðîì ÷åðåäîâàíèÿ,õðàíÿùèìñÿ â ïåðåìåííîé turn. Çíà÷åíèå 0 îçíà÷àåò, ÷òî ïðàâî íà äîñòóï êðàçäåëÿåìûì äàííûì èìååò ïåðâûé ïðîöåññ, çíà÷åíèå 1 ñîîòâåòñòâóåò ïðàâóâòîðîãî ïðîöåññà. Çàâåðøèâ ðàáîòó â êðèòè÷åñêîé ñåêöèè, ïðîöåññ ïåðåäàåòõîä äðóãîìó ïðîöåññó è ïðèñòóïàåò ê âûïîëíåíèþ äåéñòâèé, íå òðåáóþùèõäîñòóïà ê ðàçäåëÿåìûì äàííûì (ôóíêöèÿ noncritical_job()).Òàêîé ñïîñîá äåéñòâèòåëüíî íå äàåò ïðîöåññàì îêàçàòüñÿ â êðèòè÷åñêîéñåêöèè îäíîâðåìåííî, íî èìååò, ê ñîæàëåíèþ, äðóãîé íåäîñòàòîê.
Åñëè îäèíèç ïðîöåññîâ, ïåðåäàâ õîä äðóãîìó, áûñòðî âûïîëíèò âñå íåêðèòè÷åñêèå äåéñòâèÿ è ñíîâà ïîïûòàåòñÿ âîéòè â êðèòè÷åñêóþ ñåêöèþ, ìîæåò ïîëó÷èòüñÿòàê, ÷òî âòîðîé ïðîöåññ â ýòî âðåìÿ äî ñâîåé êðèòè÷åñêîé ñåêöèè òàê è íåäîøåë (è, ñîîòâåòñòâåííî, íå ïåðåäàë õîä ïåðâîìó ïðîöåññó).  ðåçóëüòàòåâòîðîé ïðîöåññ, íå íóæäàÿñü â äîñòóïå ê ðàçäåëÿåìûì äàííûì, òåì íå ìåíååáóäåò ìåøàòü îñóùåñòâëÿòü òàêîé äîñòóï ïåðâîìó ïðîöåññó, òî åñòü íàðóøèòñÿ âòîðîå èç ñôîðìóëèðîâàííûõ âûøå óñëîâèé.27.3.4Àëãîðèòì ÏåòåðñîíàÎò íåäîñòàòêîâ ïðåäûäóùèõ ïîäõîäîâ èçáàâëåí àëãîðèòì Ïåòåðñîíà.Ìû ðàññìîòðèì åãî äëÿ ñëó÷àÿ äâóõ ïðîöåññîâ4 .Äëÿ îñóùåñòâëåíèÿ âçàèìîèñêëþ÷åíèÿ íàì â ýòîò ðàç ïîòðåáóþòñÿñîçäàòü â ðàçäåëÿåìîé ïàìÿòè ìàññèâ èç äâóõ ëîãè÷åñêèõ ïåðåìåííûõinterested[2], ïîêàçûâàþùèõ, íóæäàåòñÿ ëè ñîîòâåòñòâóþùèé (íóëåâîéèëè ïåðâûé) ïðîöåññ â âûïîëíåíèè êðèòè÷åñêîé ñåêöèè; âî âðåìÿ âûïîëíåíèÿ ñåêöèè ñîîòâåòñòâóþùåå ëîãè÷åñêîå çíà÷åíèå òàêæå áóäåò èñòèííûì.Êðîìå òîãî, ââåäåì (òàêæå â ðàçäåëÿåìîé ïàìÿòè) ïåðåìåííóþ who_waits,êîòîðàÿ áóäåò ïîêàçûâàòü, êîòîðûé èç ïðîöåññîâ â ñëó÷àå ñòîëêíîâåíèÿ äîëæåí ïîäîæäàòü çàâåðøåíèÿ êðèòè÷åñêîé ñåêöèè âòîðîãî.Ïðèíöèï àëãîðèòìà â òîì, ÷òî, ïîêàçàâ ñâîþ çàèíòåðåñîâàííîñòü âî âõîäåâ êðèòè÷åñêóþ ñåêöèþ (òî åñòü ïðèñâîèâ ëîãè÷åñêóþ èñòèíó ñîîòâåòñòâóþùåé ÿ÷åéêå ìàññèâà interested), ïðîöåññ çàòåì çàÿâëÿåò î ñâîåé ãîòîâíîñòèïîäîæäàòü, åñëè ýòî íåîáõîäèìî, çàíåñÿ â ïåðåìåííóþ who_waits ñâîé íîìåð.Çàòåì îí áóäåò æäàòü äî òåõ ïîð, ïîêà ëèáî íå èçìåíèòñÿ íîìåð who_waits(ýòî îçíà÷àåò, ÷òî âòîðîé ïðîöåññ ïðîÿâèë ãîòîâíîñòü ïîäîæäàòü), ëèáî âòîðîé ïðîöåññ íå îêàæåòñÿ íåçàèíòåðåñîâàí âî âõîæäåíèè â ñåêöèþ.Íà ðèñ.
26 àëãîðèòì Ïåòåðñîíà ïîêàçàí â âèäå äâóõ ïðîöåäóð:enter_section()(âõîäâêðèòè÷åñêóþñåêöèþ)è4 Ñóùåñòâóþòîòíîñèòñÿàíàëîãè÷íûå àëãîðèòìû è äëÿ ïðîèçâîëüíîãî ÷èñëà ïðîöåññîâ; íàïðèìåð, ê òàêîâûì(bakery algorithm)àëãîðèòì áóëî÷íîé154void enter_section() {interested[0] = TRUE;who_waits = 0;while(who_waits==0 &&interested[1]) {}}void leave_section() {interested[0] = FALSE;}void enter_section() {interested[1] = TRUE;who_waits = 1;while(who_waits==1 &&interested[0]) {}}void leave_section() {interested[1] = FALSE;}Ðèñ. 26: Àëãîðèòì Ïåòåðñîíàleave_section() (âûõîä èç êðèòè÷åñêîé ñåêöèè)Åäèíñòâåííûì íåäîñòàòêîì àëãîðèòìà Ïåòåðñîíà è áîëåå ñëîæíûõ àëãîðèòìîâ, ïîñòðîåííûõ íà ýòîé èäåå, òàêèõ êàê àëãîðèòì áóëî÷íîé (àíãë.bakery algorithm), ÿâëÿåòñÿ àêòèâíîå îæèäàíèå. Ê ñîæàëåíèþ, ýòîãî âïîëíåäîñòàòî÷íî, ÷òîáû ñ÷èòàòü ýòè ðåøåíèÿ íåïðèåìëåìûìè.27.427.4.1Ìüþòåêñû è ñåìàôîðûÏîääåðæêà âçàèìîèñêëþ÷åíèÿ íà óðîâíå ÎÑÏîäõîäû ê ïîñòðîåíèþ âçàèìíîãî èñêëþ÷åíèÿ, ïåðå÷èñëåííûå â ïðåäûäóùåì ïàðàãðàôå, õàðàêòåðíû íàëè÷èåì àêòèâíîãî îæèäàíèÿ − òàêîãî ñîñòîÿíèÿ ïðîöåññà, ïðè êîòîðîì îí â îæèäàíèè ìîìåíòà, êîãäà ìîæíî áóäåò âîéòèâ êðèòè÷åñêóþ ñåêöèþ, âûíóæäåí ïîñòîÿííî îïðàøèâàòü îïðåäåëåííûå ïåðåìåííûå â ðàçäåëÿåìîé ïàìÿòè, ïðè ýòîì íå âûïîëíÿÿ íèêàêèõ ïîëåçíûõäåéñòâèé, íî çàíèìàÿ âðåìÿ öåíòðàëüíîãî ïðîöåññîðà.×òîáû ïðîöåññ, îæèäàþùèé âõîäà â êðèòè÷åñêóþ ñåêöèþ, íå ðàñõîäîâàëïîïóñòó ïðîöåññîðíîå âðåìÿ, ñëåäóåò, î÷åâèäíî, çàáëîêèðîâàòü åãî äî òåõ ïîð,ïîêà íóæíûå åìó ðàçäåëÿåìûå ðåñóðñû íå îêàæóòñÿ ñâîáîäíû, òî åñòü íåâûäåëÿòü åìó êâàíòîâ âðåìåíè äî îñâîáîæäåíèÿ ðåñóðñîâ.
Ñ äðóãîé ñòîðîíû,â ìîìåíò îñâîáîæäåíèÿ ðåñóðñîâ ïðîöåññ íåîáõîäèìî ðàçáóäèòü, òî åñòüïåðåâåñòè èç ñîñòîÿíèÿ áëîêèðîâêè â ñîñòîÿíèå ãîòîâíîñòè; æåëàòåëüíî ïðèýòîì ñíîâà ïîìåòèòü ðàçäåëÿåìûå ðåñóðñû êàê çàíÿòûå, ÷òîáû ïðîöåññó íåïðèøëîñü ñíîâà âûäåðæèâàòü êîíêóðåíòíûé ïîåäèíîê ñ äðóãèìè ïðîöåññàìèçà ñîîòâåòñòâóþùèé ðåñóðñ.Áëîêèðîâàòü ïðîöåññ ìîæåò òîëüêî îïåðàöèîííàÿ ñèñòåìà. Åñëè áû ïðîöåññó áûëî òî÷íî èçâåñòíî, ÷åðåç êàêîé ïðîìåæóòîê âðåìåíè íóæíûé åìóðåñóðñ îêàæåòñÿ îñâîáîæäåí, îí ìîã áû âûïîëíèòü ñèñòåìíûé âûçîâ, ïîäîá155íûé ôóíêöèè sleep(), ÷òîáû îòêàçàòüñÿ îò âûïîëíåíèÿ íà çàäàííûé ïåðèîä.Îäíàêî ìîìåíò îñâîáîæäåíèÿ íóæíîãî ðåñóðñà ïðîöåññó íå èçâåñòåí, ò.ê.
çàâèñèò îò ôóíêöèîíèðîâàíèÿ äðóãèõ ïðîöåññîâ.Ïîëó÷àåòñÿ, ÷òî óïðàâëåíèå ïîìåòêàìè çàíÿòîñòè/îñâîáîæäåíèÿ ðåñóðñîâ ñëåäóåò âîçëîæèòü íà îïåðàöèîííóþ ñèñòåìó, ñîçäàâ åùå îäèí ñïîñîáâçàèìîäåéñòâèÿ ïðîöåññîâ.Ñëåäóåò îòìåòèòü, ÷òî òàêîé ïîäõîä, êðîìå èçáàâëåíèÿ îò àêòèâíîãî îæèäàíèÿ, èìååò è äðóãîå âàæíîå ïðåèìóùåñòâî. Îïåðàöèîííàÿ ñèñòåìà, â îòëè÷èå îò ïðîöåññà, èìååò âîçìîæíîñòü ïðè íåîáõîäèìîñòè çàïðåùàòü ïðåðûâàíèÿ íà âðåìÿ èñïîëíåíèÿ îïðåäåëåííûõ äåéñòâèé âíóòðè ÿäðà, îáåñïå÷èâàÿ,òàêèì îáðàçîì, àòîìàðíîñòü ñêîëü óãîäíî ñëîæíûõ îïåðàöèé5 .
Ïðè ýòîì èñ÷åçàåò íåîáõîäèìîñòü â ñëîæíûõ óõèùðåíèÿõ, ïîäîáíûõ àëãîðèòìó Ïåòåðñîíà.27.4.2ÌüþòåêñûÏîä ìüþòåêñîì 6 â îáùåì ñëó÷àå ïîíèìàåòñÿ îáúåêò, èìåþùèé äâà ñîñòîÿíèÿ (îòêðûò/çàïåðò) è, ñîîòâåòñòâåííî, äâå îïåðàöèè: lock() (çàïåðåòü) èunlock() (îòêðûòü).Îïåðàöèÿ unlock() ïðîõîäèò óñïåøíî (è íåìåäëåííî âîçâðàùàåò óïðàâëåíèå) â ëþáîì ñëó÷àå, ïåðåâîäÿ îáúåêò â ñîñòîÿíèå îòêðûò.Äëÿ îïåðàöèè lock() ìîæåò áûòü äâà âàðèàíòà:1.
Îïåðàöèÿ ìîæåò áûòü ðåàëèçîâàíà êàê áóëåâñêàÿ ôóíêöèÿ. Ïðè ïðèìåíåíèè åå ê îòêðûòîìó ìüþòåêñó îíà çàêðûâàåò åãî è âîçâðàùàåò çíà÷åíèå èñòèíà (óñïåõ). Ïðè ïðèìåíåíèè ê çàêðûòîìó ìüþòåêñó ôóíêöèÿâîçâðàùàåò çíà÷åíèå ëîæü (íåóäà÷à). Òàêîé âàðèàíò ðåàëèçàöèè íàçûâàåòñÿ íåáëîêèðóþùèì.2. Îïåðàöèþ ìîæíî ðåàëèçîâàòü è êàê ïðîöåäóðó, íå âîçâðàùàþùóþ íèêàêîãî çíà÷åíèÿ.  ýòîì ñëó÷àå ïðè ïðèìåíåíèè åå ê îòêðûòîìó ìüþòåêñó îíà çàêðûâàåò åãî è âîçâðàùàåò óïðàâëåíèå; ïðè ïðèìåíåíèè åå êçàêðûòîìó ìüþòåêñó îíà áëîêèðóåò âûçâàâøèé ïðîöåññ äî òåõ ïîð, ïîêà ìüþòåêñ íå îêàæåòñÿ îòêðûò, ïîñëå ÷åãî çàêðûâàåò åãî è âîçâðàùàåòóïðàâëåíèå.Âàæíåéøèì ñâîéñòâîì îïåðàöèé lock() è unlock() ÿâëÿåòñÿ èõàòîìàðíîñòü .Ýòî îçíà÷àåò, ÷òî îáå îïåðàöèè âûïîëíÿþòñÿ êàê åäèíîå5 Êîíå÷íî,ñëîæíîñòü àòîìàðíûõ îïåðàöèé äîëæíà îñòàâàòüñÿ â ðàçóìíûõ ïðåäåëàõ, ò.ê.
äëèòåëüíûéçàïðåò ïðåðûâàíèé ìîæåò îòðèöàòåëüíî ñêàçàòüñÿ íà ôóíêöèîíèðîâàíèè âñåé âû÷èñëèòåëüíîé ñèñòåìû:íàïðèìåð, ìîãóò ñáèòüñÿ îïåðàöèè ÷òåíèÿ/çàïèñè äèñêîâ, è ò.ï.6 Àíãë. mutex − ñîêðàùåíèå îò ñëîâ mutual exception156öåëîå è íå ìîãóò áûòü ïðåðâàíû7 .  ÷àñòíîñòè, îïåðàöèÿ lock() íå ìîæåòáûòü ïðåðâàíà ìåæäó ïðîâåðêîé òåêóùåãî çíà÷åíèÿ ìüþòåêñà è èçìåíåíèåìýòîãî çíà÷åíèÿ íà çàêðûòî.Âñïîìíèì òåïåðü íàøó ïîïûòêó âûïîëíèòü âçàèìîèñêëþ÷åíèå ñ ïîìîùüþ áëîêèðîâî÷íîé ïåðåìåííîé (27.3.1).
Èñïîëüçóåì âìåñòî îáû÷íîé ïåðåìåííîé ìüþòåêñ (îáîçíà÷èì åãî, êàê è áëîêèðîâî÷íóþ ïåðåìåííóþ, áóêâîés), à âìåñòî ïðèñâàèâàíèé s = 0 è s = 1 − ñîîòâåòñòâåííî îïåðàöèè lock()è unlock(). Ðàññìîòðèì äëÿ íà÷àëà íåáëîêèðóþùóþ ðåàëèçàöèþ lock():while(!lock(s)) {} /* æäåì, ïîêà íå óäàñòñÿ çàêðûòü ìüþòåêñ */section();/* ... ðàáîòà ñ ðàçäåëÿåìûìè äàííûìè ... */unlock(s);/* ðàçðåøàåì äðóãèì ïðîöåññàì äîñòóï */ îòëè÷èå îò âàðèàíòà ñ èñïîëüçîâàíèåì áëîêèðóþùåé ïåðåìåííîé, äàííûéâàðèàíò ÿâëÿåòñÿ êîððåêòíûì. Ïîñêîëüêó îïåðàöèÿ lock() àòîìàðíà, âûõîäèç öèêëà (ïî èñòèííîìó çíà÷åíèþ ôóíêöèè lock()) îçíà÷àåò, ÷òî â íåêèéìîìåíò ìüþòåêñ îêàçàëñÿ îòêðûò (òî åñòü íèêòî â ýòî âðåìÿ íå ðàáîòàë ñðàçäåëÿåìûìè äàííûìè), è íàøåìó ïðîöåññó óäàëîñü åãî çàêðûòü, ïðè÷åìíèêòî äðóãîé âêëèíèòüñÿ ìåæäó ïðîâåðêîé è çàêðûòèåì íå ìîã.Åñëè ïðèìåíèòü âòîðîé òèï ðåàëèçàöèè îïåðàöèè lock() (ïðè êîòîðîìîíà áëîêèðóåòñÿ äî òåõ ïîð, ïîêà íå óäàñòñÿ çàêðûòü îòêðûòûé ìüþòåêñ),íàø êîä ñòàíåò åùå ïðîùå, è èç íåãî èñ÷åçíåò öèêë àêòèâíîãî îæèäàíèÿ:lock(s);section();unlock(s);/* æäåì, ïîêà íå óäàñòñÿ çàêðûòü ìüþòåêñ *//* ...
ðàáîòà ñ ðàçäåëÿåìûìè äàííûìè ... *//* ðàçðåøàåì äðóãèì ïðîöåññàì äîñòóï */ßñíî, ÷òî òàêîé ìüþòåêñ ìîæåò áûòü ðåàëèçîâàí òîëüêî ïðè ñîäåéñòâèè ÿäðà îïåðàöèîííîé ñèñòåìû: ëèáî öåëèêîì êàê îáúåêò ÿäðà, ëèáî êàê íàáîðîïåðàöèé, îñóùåñòâëÿåìûõ ÿäðîì íàä ïåðåìåííîé, ðàñïîëîæåííîé â ïîëüçîâàòåëüñêîì ïðîöåññå8 . Îòìåòèì ñ äðóãîé ñòîðîíû, ÷òî ââåäåíèå òàêîãî ñðàâíèòåëüíî ïðîñòîãî ñåðâèñà â ÿäðå ÎÑ ïîçâîëÿåò èçáàâèòüñÿ ðàçîì îò âñåõíåäîñòàòêîâ ðàññìîòðåííûõ âûøå ïîäõîäîâ ê âçàèìíîìó èñêëþ÷åíèþ.27.4.3Ñåìàôîðû ÄåéêñòðûÏðåäëîæåííûå Ýäñãåðîì Äåéêñòðîé ñåìàôîðû ïðåäñòàâëÿþò ñîáîé îáîáùåíèå ïîíÿòèÿ ìüþòåêñà.7 Êðîìåñëó÷àÿ, êîãäà îïåðàöèÿ lock() áëîêèðóåò âûçâàâøèé ïðîöåññ − òîãäà íà âðåìÿ áëîêèðîâêèïðåðûâàíèÿ ðàçðåøàþòñÿ8 Êàê ìû óâèäèì èç äàëüíåéøåãî, ìüþòåêñ, â êîòîðîì lock() ñäåëàí íåáëîêèðóþùèì, ìîæíî ðåàëèçîâàòü íà íåêîòîðûõ àðõèòåêòóðàõ è áåç ó÷àñòèÿ ÿäðà157â êëàññè÷åñêîì âàðèàíòå ïðåäñòàâëÿåò ñîáîé öåëî÷èñëåííóþ ïåðåìåííóþ, ïðî êîòîðóþ èçâåñòíî, ÷òî îíà ïðèíèìàåò òîëüêîíåîòðèöàòåëüíûå çíà÷åíèÿ, è íàä êîòîðîé îïðåäåëåíû äâå îïåðàöèè: up() èdown().
Îïåðàöèÿ up() âñåãäà ïðîõîäèò óñïåøíî, óâåëè÷èâàÿ çíà÷åíèå ïåðåìåííîé íà 1, è íåìåäëåííî âîçâðàùàåò óïðàâëåíèå. Îïåðàöèÿ down() äîëæíà,íàîáîðîò, óìåíüøàòü çíà÷åíèå íà 1, íî ñäåëàòü ýòî îíà ìîæåò òîëüêî â ñëó÷àå,åñëè òåêóùåå çíà÷åíèå ñòðîãî áîëüøå íóëÿ, âåäü çíà÷åíèå ñåìàôîðà íå ìîæåòáûòü îòðèöàòåëüíûì. Ñîîòâåòñòâåííî, ïðè ïîëîæèòåëüíîì çíà÷åíèè ñåìàôîðà îïåðàöèÿ down() óìåíüøàåò åãî çíà÷åíèå íà 1 è íåìåäëåííî âîçâðàùàåòóïðàâëåíèå.  ñëó÷àå æå íóëåâîãî çíà÷åíèÿ ñåìàôîðà îïåðàöèÿ áëîêèðóåòâûçâàâøèé ïðîöåññ äî òåõ ïîð, ïîêà çíà÷åíèå íå ñòàíåò ïîëîæèòåëüíûì, ïîñëå ÷åãî óìåíüøàåò çíà÷åíèå è âîçâðàùàåò óïðàâëåíèå.Ñåìàôîð ÄåéêñòðûÊàê è â ñëó÷àå ñ ìüþòåêñîì, îïåðàöèè íàä ñåìàôîðîì îáÿçàòåëüíî äîëæíû áûòü ðåàëèçîâàíû àòîìàðíî: íåîáõîäèìî ïîëíîñòüþ èñêëþ÷èòü ñèòóàöèè, êîãäà ðåçóëüòàò íåñêîëüêèõ íåçàâèñèìûõ îïåðàöèé íàä ñåìàôîðîì ìîæåò çàâèñåòü îò âðåìåíè âûçîâà îïåðàöèé ïðîöåññàìè (êàê ýòî ïðîèñõîäèëîâ ïðèìåðå, ïðèâåäåííîì â íà÷àëå ëåêöèè).
Ñåìàôîð, êàê è ìüþòåêñ, ìîæåòáûòü ðåàëèçîâàí öåëèêîì êàê îáúåêò ÿäðà, ëèáî êàê íàáîð îïåðàöèé ÿäðàíàä ïåðåìåííîé èç ïàìÿòè ïîëüçîâàòåëüñêîãî ïðîöåññà.ßñíî, ÷òî ñ ïîìîùüþ ñåìàôîðà ìîæíî èìèòèðîâàòü ôóíêöèîíèðîâàíèåìüþòåêñà, åñëè ñ÷èòàòü çíà÷åíèå 0 ñîñòîÿíèåì çàêðûò, çíà÷åíèå 1 − ñîñòîÿíèåì îòêðûò, à îïåðàöèè lock() è unlock() çàìåíèòü íà down() è up().Íåîáõîäèìî òîëüêî ñëåäèòü, ÷òîáû îïåðàöèÿ up() íèêîãäà íå ïðèìåíÿëàñü êïîëîæèòåëüíîìó ñåìàôîðó, à ýòîãî ìîæíî äîñòè÷ü, åñëè ïðèìåíÿòü îïåðàöèþup() òîëüêî â íà÷àëå ïðîãðàììû (îäèí ðàç), à òàêæå ïîñëå òîãî, êàê ïðîøëàîïåðàöèÿ down(), è íèêîãäà èíà÷å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
