А.В. Столяров - Введение в операционные системы, страница 9
Описание файла
PDF-файл из архива "А.В. Столяров - Введение в операционные системы", который расположен в категории "". Всё это находится в предмете "операционные системы" из 3 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 9 страницы из PDF
Åñëèó÷åñòü, ÷òî êàæäàÿ ñòðîêà â òàáëèöå ñòðàíèö çàíèìàåò îáû÷íî 4 áàéòà, ïîëó÷èì, ÷òî íà òàáëèöó ñòðàíèö êàæäîãî ïðîöåññà òðåáóåòñÿ 4Mb ïàìÿòè.Áåçóñëîâíî, ýòî íåïðèåìëåìî: áîëüøèíñòâî çàäà÷ çàíèìàåò â ïàìÿòè ñóùåñòâåííî ìåíüøå îäíîãî Mb, òàê ÷òî íà òàáëèöû ñòðàíèö ïðèäåòñÿ ïîòðàòèòüáîëüøå ïàìÿòè, ÷åì íà ñàìè çàäà÷è. Îäíèì èç âîçìîæíûõ ðåøåíèé ÿâëÿåòñÿ èñêóññòâåííîå îãðàíè÷åíèå êîëè÷åñòâà ñòðàíèö, íî ýòî ðåøåíèå äàëåêîíå ëó÷øåå, ò.ê. ïðèâîäèò ê íåâîçìîæíîñòè âûïîëíåíèÿ çàäà÷, òðåáóþùèõáîëüøåãî êîëè÷åñòâà ïàìÿòè.Áîëåå ýëåãàíòíîå ðåøåíèå ñîñòîèò â ïðèìåíåíèè ìíîãîóðîâíåâûõ ñòðàíè÷íûõ òàáëèö.
 ýòîì ñëó÷àå íîìåð ñòðàíèöû äåëèòñÿ íà ãðóïïû áèòîâ, çàäàþùèõ íîìåð ñòðîêè â òàáëèöàõ ñîîòâåòñòâóþùèõ óðîâíåé; òàáëèöà ïåðâîãîóðîâíÿ ñîäåðæèò àäðåñà òàáëèö âòîðîãî óðîâíÿ, è ò.ä., à òàáëèöà ïîñëåäíåãî38Виртуальный адрестабл. 1 табл. 2смещениеТаблица второго уровняНомер физ. кадраатрибутыТаблица первого уровняАдрес табл. 2го ур. атрибутыномер физ. кадрасмещениеФизический адресÐèñ. 12: Äâóõóðîâíåâàÿ ñõåìà ñòðàíè÷íîãî ïðåîáðàçîâàíèÿóðîâíÿ − íîìåðà ôèçè÷åñêèõ êàäðîâ (ðèñ. 12).  ýòîì ñëó÷àå äëÿ êàæäîéçàäà÷è íåîáõîäèìî çàâåñòè òàáëèöó âåðõíåãî óðîâíÿ è ïî îäíîé òàáëèöå äëÿâñåõ îñòàëüíûõ óðîâíåé; îñòàëüíûå òàáëèöû áóäóò äîáàâëÿòüñÿ ïî íåîáõîäèìîñòè.
Ïîñêîëüêó ñõåìà, êàê ïðàâèëî, ñîäåðæèò íå áîëåå òðåõ óðîâíåé5 , äëÿíåáîëüøîé çàäà÷è òðåáóåòñÿ õðàíèòü âñåãî äâå èëè òðè ñðàâíèòåëüíî íåáîëüøèå ïî ðàçìåðó òàáëèöû.Ðàññìîòðèì äëÿ ïðèìåðà äâóõóðîâíåâóþ ñòðàíè÷íóþ ñõåìó äëÿ ñëó÷àÿ32-áèòíûõ àäðåñîâ è ðàçìåðà ñòðàíèöû 4Kb. Ñìåùåíèå ïðè òàêîì ðàçìåðåñòðàíèöû çàíèìàåò 12 áèò, íà íîìåð ñòðàíèöû îñòàåòñÿ 20 áèò, èç êîòîðûõ10 èñïîëüçóåì äëÿ âûáîðà ñòðîêè â òàáëèöå ïåðâîãî óðîâíÿ, îñòàëüíûå 10 −äëÿ âûáîðà ñòðîêè â òàáëèöå âòîðîãî óðîâíÿ6 . Òîãäà òàáëèöû îáîèõ óðîâíåéìîãóò ñîäåðæàòü 210 = 1024 ñòðîêè, ÷òî ïðè äëèíå ñòðîêè 4 áàéòà òðåáóåò4096 áàéò, òî åñòü êàæäàÿ òàáëèöà çàíèìàåò ðîâíî îäèí êàäð â ïàìÿòè.Êàê ìîæíî çàìåòèòü, ñòðàíè÷íàÿ îðãàíèçàöèÿ ïàìÿòè ñíèìàåò ïðîáëåìûîáúåìà è ôðàãìåíòàöèè. Äåéñòâèòåëüíî, â ðàññìîòðåííîé ìîäåëè ôèçè÷åñêàÿïàìÿòü âûäåëÿåòñÿ êàäðàìè, ïðè÷åì ñîâåðøåííî áåçðàçëè÷íî, áóäóò ëè êàäðû ñîñåäíèìè èëè íåò; ëþáîé ñâîáîäíûé êàäð ìîæåò áûòü èñïîëüçîâàí äëÿëþáîé çàäà÷è.
Òàêèì îáðàçîì, ôðàãìåíòàöèÿ âîçíèêíóòü íå ìîæåò. Äàëåå,5 Îáû÷íîäâà óðîâíÿ äëÿ 32-áèòíûõ àðõèòåêòóð è òðè − äëÿ 64-áèòíûõòàê îáñòîÿò äåëà â ñîâðåìåííûõ i386-ñîâìåñòèìûõ ïðîöåññîðàõ; â äîêóìåíòàöèè îáû÷íî òàáëèöà ïåðâîãî óðîâíÿ íàçûâàåòñÿ êàòàëîãîì òàáëèö, à òàáëèöû âòîðîãî óðîâíÿ − ñîáñòâåííî òàáëèöàìèñòðàíèö6 Èìåííî39êàæäàÿ ñòðàíèöà íåçàâèñèìî îò äðóãèõ ìîæåò áûòü â ëþáîé ìîìåíò îòêà÷àíà íà äèñê. Ïðè îáðàùåíèè ê íåé ïðîèçîéäåò ñòðàíè÷íîå ïðåðûâàíèå, ïîêîòîðîìó îïåðàöèîííàÿ ñèñòåìà ìîæåò ïîäêà÷àòü ñòðàíèöó îáðàòíî â ïàìÿòü,ïîñëå ÷åãî ïðîäîëæèòü âûïîëíåíèå çàäà÷è â òî÷íîñòè ñ èíñòðóêöèè, âûçâàâøåé ïðåðûâàíèå.
Âîçìîæíî, ñòðàíèöà áóäåò ïîäêà÷àíà â ñîâåðøåííî äðóãîéôèçè÷åñêèé êàäð, íî ïîëüçîâàòåëüñêàÿ çàäà÷à ýòîãî íå çàìåòèò, êàê è âîîáùåñàìîãî ôàêòà ïîäêà÷êè. Áëàãîäàðÿ íåçàâèñèìîé îáðàáîòêå îòäåëüíûõ ñòðàíèö, çàäà÷å ìîæíî âûäåëèòü áîëüøå ïàìÿòè, ÷åì ôèçè÷åñêè åñòü íà ìàøèíå;â ýòîì ìû îãðàíè÷åíû òîëüêî îáúåìîì âèðòóàëüíîãî àäðåñíîãî ïðîñòðàíñòâàè, êîíå÷íî, âûäåëåííûì äèñêîâûì ïðîñòðàíñòâîì ïîä ñâîïïèíã.Ê íåäîñòàòêàì ñòðàíè÷íîé ìîäåëè ìîæíî îòíåñòè, âî-ïåðâûõ, ñðàâíèòåëüíî áîëüøîå êîëè÷åñòâî íåèñïîëüçóåìîé ïàìÿòè â êîíöå ïîñëåäíåé ñòðàíèöûêàæäîé çàäà÷è (îñîáåííî ïðè áîëüøèõ ðàçìåðàõ ñòðàíèö) è, âî-âòîðûõ, áîëüøèå îáúåìû ñëóæåáíîé èíôîðìàöèè (ñòðàíè÷íûõ òàáëèö).Îñòàíîâèìñÿ íà ýòîì ïîäðîáíåå.
Åñëè íå ïðåäïðèíÿòü ñïåöèàëüíûõ ìåð,ïðè ðàáîòå ïî äâóõóðîâíåâîé òàáëè÷íîé ñõåìå êàæäîå îáðàùåíèå ê ïàìÿòèçà êîìàíäîé èëè äàííûìè ïîòðåáóåò åùå äâóõ îáðàùåíèé: ê òàáëèöå ïåðâîãîóðîâíÿ è ê òàáëèöå âòîðîãî óðîâíÿ. Ñèòóàöèÿ, â îáùåì, àíàëîãè÷íà âîçíèêøåé â ñåãìåíòíîé ìîäåëè, çà èñêëþ÷åíèåì òîãî, ÷òî ñòðàíèöà − íå ñåãìåíò,åå îáúåì ñóùåñòâåííî ìåíüøå, à êîëè÷åñòâî ñòðàíèö − ãîðàçäî áîëüøå; ïðîãðàììà ìîæåò çà îäíó ñåêóíäó óñïåòü îáðàòèòüñÿ ê íåñêîëüêèì äåñÿòêàìñòðàíèö.
ßñíî, ÷òî õðàíèòü èíôîðìàöèþ î ñòðàíè÷íîì ñîîòâåòñòâèè â ðåãèñòðîâîé ïàìÿòè íå ïîëó÷èòñÿ èç-çà áîëüøîãî îáúåìà.Ðåøèòü ïðîáëåìó ïîçâîëÿåò âñòðîåííîå â ïðîöåññîð ñïåöèàëüíîå óñòðîéñòâî, íàçûâàåìîå àññîöèàòèâíîé ïàìÿòüþ 7 . Óñòðîéñòâî ïðåäñòàâëÿåò ñîáîéòàáëèöó èç äâóõ ïîëåé − íîìåð âèðòóàëüíîé ñòðàíèöû è èíôîðìàöèÿ î ñîîòâåòñòâóþùåì åé êàäðå (íîìåð êàäðà è åãî àòðèáóòû). Ýëåêòðîííàÿ ñõåìààññîöèàòèâíîé ïàìÿòè óñòðîåíà òàê, ÷òî çàïðîñ ê íåé ôîðìèðóåòñÿ íå ïîíîìåðó ñòðîêè òàáëèöû, à ïî çíà÷åíèþ ïåðâîãî ïîëÿ, òî åñòü ïî êëþ÷ó.Ñëè÷åíèå ïðåäúÿâëåííîãî çíà÷åíèÿ ñî çíà÷åíèÿìè êëþ÷åâîãî ïîëÿ ïðîèçâîäèòñÿ îäíîâðåìåííî âî âñåõ ñòðîêàõ òàáëèöû (ïàðàëëåëüíûìè ñõåìàìè).Åñëè â îäíîé èç ñòðîê çíà÷åíèå ñîâïàäàåò, â êà÷åñòâå ðåçóëüòàòà âûäàåòñÿâòîðîå ïîëå òîé æå ñòðîêè (òî åñòü íîìåð êàäðà è åãî àòðèáóòû).Ñëîæíîñòü ðåàëèçàöèè àññîöèàòèâíîé ïàìÿòè ðàñòåò íåëèíåéíî ñ óâåëè÷åíèåì êîëè÷åñòâà ñòðîê, òàê ÷òî îáû÷íî ÷èñëî ñòðîê òàáëèöû íå ïðåâûøàåòíåñêîëüêèõ äåñÿòêîâ (16 ñòðîê ìîæíî ñ÷èòàòü òèïè÷íûì ïðèìåðîì åìêîñòèàññîöèàòèâíîé ïàìÿòè).Ïðè îáðàùåíèè ê ñòðàíèöå, î êîòîðîé â àññîöèàòèâíîé ïàìÿòè íåò èí7Âàíãëîÿçû÷íîé ëèòåðàòóðå ÷àñòî âñòðå÷àåòñÿ òåðìèíñêîÿçû÷íîé − áóôåð áûñòðîãî ïðåîáðàçîâàíèÿ àäðåñà40Translation Lookaside Buer, TLB, à â ðóñ-ôîðìàöèè, ïðîèçâîäèòñÿ ïðåîáðàçîâàíèå ÷åðåç ñòðàíè÷íûå òàáëèöû (òî åñòüê ñòðàíèöàì âñå-òàêè ïðèõîäèòñÿ îáðàòèòüñÿ), íî ïîñëå ýòîãî èíôîðìàöèÿ,ïîëó÷åííàÿ èç òàáëèö, çàïèñûâàåòñÿ â àññîöèàòèâíóþ ïàìÿòü.
Åñëè òåïåðüïðîãðàììà îáðàòèòñÿ ê òîé æå ñàìîé ñòðàíèöå, îáðàùåíèÿ ê òàáëèöàì íåïîòðåáóåòñÿ. Êîãäà âñå ñòðîêè òàáëèöû îêàçûâàþòñÿ çàïîëíåíû, î÷åðåäíîåîáðàùåíèå ê íåèçâåñòíîé ñòðàíèöå ïðèâîäèò ê òîìó, ÷òî èíôîðìàöèÿ îá îäíîé èç èçâåñòíûõ ñòðàíèö èç àññîöèàòèâíîé ïàìÿòè óäàëÿåòñÿ.Ñëåäóåò îòìåòèòü, ÷òî èíôîðìàöèÿ îá îòîáðàæåíèè ñòðàíèö ÿâëÿåòñÿ ëîêàëüíîé äëÿ êàæäîé çàäà÷è, òàê ÷òî ïðè ñìåíå àêòèâíîé çàäà÷è ñîäåðæèìîåàññîöèàòèâíîé ïàìÿòè ïðèõîäèòñÿ ñáðàñûâàòü, è íåêîòîðîå âðåìÿ íîâàÿ çàäà÷à òðàòèò íà çàïîëíåíèå àññîöèàòèâíîé ïàìÿòè ñâîèìè äàííûìè. Òàêèìîáðàçîì, ïðè ñòðàíè÷íîé îðãàíèçàöèè ïàìÿòè ñìåíà çàäà÷è ñòàíîâèòñÿ åùåáîëåå äîðîãîñòîÿùåé îïåðàöèåé, îäíàêî âûáîðà ó íàñ íåò.Îòìåòèì òàêæå, ÷òî óïðàâëåíèå àññîöèàòèâíîé ïàìÿòüþ ìîæíî âîçëîæèòü íà îïåðàöèîííóþ ñèñòåìó.  ýòîì ñëó÷àå ïðîöåññîð âîîáùå íå äåëàåòíèêàêèõ ïðåäïîëîæåíèé î òîì, êàê óñòðîåíû ñòðóêòóðû äàííûõ, îòâå÷àþùèå çà îòîáðàæåíèå ñòðàíèö; ýòî ïîëíîñòüþ îòäàíî íà îòêóï îïåðàöèîííîéñèñòåìå.
 ñëó÷àå, åñëè â àññîöèàòèâíîé ïàìÿòè îòñóòñòâóåò ñòðîêà îòíîñèòåëüíî òðåáóåìîãî íîìåðà ñòðàíèöû, ïðîöåññîð ãåíåðèðóåò ïðåðûâàíèå, ïîñëå÷åãî îïåðàöèîííàÿ ñèñòåìà äîëæíà ïðîãðàììíî ïðîèçâåñòè ïîèñê èëè èíîåâû÷èñëåíèå ñîîòâåòñòâóþùåé èíôîðìàöèè è çàíåñòè ýòó èíôîðìàöèþ â àññîöèàòèâíóþ ïàìÿòü, ïîñëå ÷åãî âîçîáíîâèòü èñïîëíåíèå àêòèâíîé çàäà÷è.8.3.4Ñåãìåíòíî-ñòðàíè÷íàÿ îðãàíèçàöèÿ ïàìÿòèÊàê ãîâîðèëîñü ðàíåå, ñåãìåíòíàÿ ìîäåëü îðãàíèçàöèè ïàìÿòè èìååò ñâîèñïåöèôè÷åñêèå äîñòîèíñòâà, äåëàÿ àäðåñíîå ïðîñòðàíñòâî çàäà÷è ìíîãîìåðíûì. Ñåãìåíòíî-ñòðàíè÷íàÿ ìîäåëü ïðåäñòàâëÿåò ñîáîé ïîïûòêó îáúåäèíèòüäîñòîèíñòâà ñåãìåíòíîé è ñòðàíè÷íîé îðãàíèçàöèè ïàìÿòè.
 ýòîé ìîäåëè çàäà÷à èìååò íåñêîëüêî ñåãìåíòîâ, ïðè÷åì êàæäûé ñåãìåíò ïðåäñòàâëÿåò ñîáîéñàìîñòîÿòåëüíîå âèðòóàëüíîå àäðåñíîå ïðîñòðàíñòâî, ïîäåëåííîå íà ñòðàíèöû. Èíà÷å ãîâîðÿ, êàæäîé çàäà÷å ïðèïèñûâàåòñÿ, â îáùåì ñëó÷àå, íå îäíîîòîáðàæåíèå ñòðàíèö â ôèçè÷åñêèå êàäðû, à íåñêîëüêî (ïî îäíîìó íà êàæäûé ñåãìåíò).Ñåãìåíòíî-ñòðàíè÷íàÿ îðãàíèçàöèÿ ðåàëèçîâàíà, íàïðèìåð, íà i386ñîâìåñòèìûõ ïðîöåññîðàõ. Îñíîâíûì íåäîñòàòêîì ýòîé ìîäåëè ÿâëÿåòñÿ åå÷ðåçìåðíàÿ ñëîæíîñòü; ïðàêòè÷åñêè íå èçâåñòíû îïåðàöèîííûå ñèñòåìû, ñóùåñòâåííî èñïîëüçóþùèå ñåãìåíòíî-ñòðàíè÷íóþ ìîäåëü.41Ëåêöèÿ 49Èñòîðèÿ ÎÑ Unix êîíöå 1960-x ãîäîâ êîíñîðöèóì â ñîñòàâå êîíöåðíà General Electrics,Ìàññà÷óñåòñêîãî Òåõíîëîãè÷åñêîãî Èíñòèòóòà (MIT) è èññëåäîâàòåëüñêîéêîìïàíèè Bell Laboratories (íà òîò ìîìåíò − ïîäðàçäåëåíèÿ AT&T) ðàçðàáàòûâàëè îïåðàöèîííóþ ñèñòåìó MULTICS.Î ïðîåêòå MULTICS èíîãäà ãîâîðÿò êàê î íåóäà÷íîì; òàê èëè èíà÷å, BellLabs â íåêèé ìîìåíò èç ïðîåêòà âûøëà. ÷èñëî ñîòðóäíèêîâ Bell Labs, ó÷àñòâîâàâøèõ â ïðîåêòå MULTICS, âõîäèë Êåí Òîìïñîí.
Ïî îäíîé èç ëåãåíä, â òå âðåìåíà åãî èíòåðåñîâàëà íîâàÿíà òîò ìîìåíò îáëàñòü ïðîãðàììèðîâàíèÿ − êîìïüþòåðíûå èãðû.  ñèëóäîðîãîâèçíû âû÷èñëèòåëüíîé òåõíèêè òîãî âðåìåíè ó Êåíà Òîìïñîíà áûëè îïðåäåëåííûå ñëîæíîñòè ñ ïîëó÷åíèåì êîìïüþòåðíîãî âðåìåíè äëÿ èãðû â íàïèñàííóþ èì Star Travel, ïîýòîìó îí çàèíòåðåñîâàëñÿ èìåâøåéñÿ âBell Labs è ìàëîâîñòðåáîâàííîé íà òîò ìîìåíò ìàøèíîé PDP-7. Íàëè÷åñòâîâàâøåå äëÿ ýòîé ìàøèíû ñèñòåìíîå ïðîãðàììíîå îáåñïå÷åíèå Òîìïñîíà íåóñòðîèëî, è, ïîëüçóÿñü îïûòîì, ïîëó÷åííûì â ïðîåêòå MULTICS, îí íàïèñàëäëÿ PDP-7 ñâîþ îïåðàöèîííóþ ñèñòåìó.
