Viii. Виртуална памет


с. 1 с. 2




Глава VIII. ВИРТУАЛНА ПАМЕТ
Дискутираните в гл. VII стратегии за управление на паметта имат за цел да държат, с оглед на мултипрограмирането, много процеси в паметта едновременно. Но както беше посочено, те изискват цялото адресно пространство на процеса да бъде поместено в основната (оперативната) памет, преди да започне изпълнението му. Така големината на програмите е ограничена от размера на основната памет.

Ако се разгледат реалните програми, очевидно е, че в много случаи не е необходима цялата програма. Например: декларирани са разни таблици, масиви, списъци (и съответно им е разпределена памет), но много често те не се използват изцяло; в програмите има клонове, които се използват само при определени условия, и т.н.

Възможността да се изпълнява програма, която само отчасти е поместена в паметта, дава много предимства: повече потребители ще бъдат обслужвани едновременно (повишава се използването на процесора и пропускателната способност, обаче не и времето за отговор или за чакане), потребителските програми не са ограничени от обема на паметта, по-малко входно-изходни операции са необходими при размяна и т.н. Или полза има и потребителят, и ОС.

Виртуалната памет е техника, която позволява изпълнение на програми, които не са изцяло поместени в основната памет. Главното предимство на виртуалната памет е, че потребителските програми могат да бъдат по-големи от основната памет. Виртуалната памет се реализира чрез средствата на страничната или на сегментната, или на странично-сегментната организация, и чрез механизма за размяна. Обикновено се използва страничната организация и затова разглеждането в главата се базира на нея, но резултатите са приложими и за сегментната или за странично-сегментната организация. Най-общо казано, виртуалната памет не е лесно да бъде реализирана и дори би могла да доведе до намаляване на производителността, ако предварително не се вземат мерки.

8.1. СЪЩНОСТ НА ВИРТУАЛНАТА ПАМЕТ

Виртуалната памет е отделяне на потребителската логическа памет от реалната (основната) памет. Виртуалната памет съществува наред с основната памет, при което между тях се осъществява динамично съответствие чрез механизмите на страничната организация (респ. сегментната или странично-сегментната). Виртуалната памет представлява адресно пространство, разделено на страници (сегменти, сегменти и страници), разположени върху външно запомнящо устройство (което обикновено е магнитен диск).

В системите с виртуална памет програмистите съставят своите програми така, като че ли имат на разположение практически неограничен обем основна (оперативна) памет. Те не се грижат за организиране на припокриване на отделните части на заданията си или за организиране на работни файлове. Работата на Виртуалната памет много наподобява системите със странична организация и размяна. На всяко избрано за изпълнение задание се разпределя област от виртуалната памет, в която то се разполага, а известен брой негови страници се прехвърлят в основната памет. По-нататьк, по време на изпълнение, страници постоянно се извеждат и въвеждат. Системен механизъм, наречен управление на вторичната памет, поддържа таблица с информация за съответствието между виртуалните адреси и физическото разположение на данните върху диска (възможно е адресите на страниците във вторичната памет да се пазят в таблицата на страниците, но нараства обемът на необходимата основна памет). Съответствието между виртуалната и основната памет се управлява от страничен супервайзор, който динамично организира записа на необходимите страници в основната памет.

Средствата за динамично преобразуване на адресите, разгледани в т. 7.2.3, осигуряват съответствието между виртуалните и абсолютните адреси. Таблицата на страниците, обаче, е допълнена с бит за присъствие, показващ дали съответната страница се намира в основната памет. Ако страницата е в основната памет, преобразуването на адресите става по описания вече начин (вж. фиг. 7.3). В противен случай настъпва прекъсване поради липса на страница (странично прекъсване), чрез което се извиква страничният супервайзор (трябва да се отбележи, че това прекъсване се отнася към класа на програмните прекъсвания, а не показва нарушение на защитата). Супервайзорът намира свободен кадър, например с помощта на таблица на кадрите, и организира четенето на необходимата страница от вторичната в основната памет. След това се коригират таблиците на страниците и на кадрите.

Докато се въведе нужната страница, процесът се привежда в състояние на очакване на завършването на дисковата операция, а за изпълнение се пуска друг, готов процес. В повечето системи това не означава изваждане на процеса от опашката на диспечера. Накрая се повтаря изпълнението на прекъснатата машинна команда.

При повторното изпълнение на прекъсната команда могат да възникнат някои проблеми. Ако прекъсването се случи по време на извличане на команда, рестартира се нейното извличане. Ако прекъсването се случи по време на четенето на операнди, също трябва да се рестартира четенето на командата. Проблем настъпва при команди, които могат да модифицират области на паметта. Типичен пример е командата МVС (прехвърли знаците), която прехвърля група байтове от една облает в друга, при което те могат да се припокриват. Ако при прехвърлянето се излезе от текущата страница, може да настъпи прекъсване поради липса на страница, при което изходната облает вече е модифицирана – в този случай командата не може да се рестартира. Възможни са две решения на проблема. Процесорът най-напред се опитва да достигне границите на двете области, без да прехвърля данни. Ако настъпи прекъсване, то ще бъде пред тази стъпка. Прехвърлянето ще се извърши, когато се знае, че страниците са налице. Другият подход е да се използват регистри за запомняне на съдържанието на припокриващите се области с оглед на възстановяване при прекъсване.

Подобен проблем настъпва при процесорите, които използват начин на регистрова адресация, наречен автонамаляване и автоувеличаване. При тази адресация съдържанието на регистър (адрес на операнд в паметта) автоматично се увеличава (след използване на регистъра) или намалява (преди използването на регистъра) съгласно зададения начин. За да може да се повтори изпълнението на командата при прекъсване, съдържанието на регистрите трябва да се възстанови. Някои машини (като PDP-11/45) имат регистър, в който се копира програмният брояч, както и втори регистър, в които се помни кои регистри и с колко са били модифицирани по време на изпълнение на командата.

Други процесори, като М68010, микропрограмно записват информацията за състоянието си в стек, за да осигурят рестартиране. Трети, като VAX, микропрограмно връщат състоянието на процесора в точката преди стартирането на пропадналата команда.

Тези архитектурни проблеми илюстрират част от трудностите, възникващи при въвеждане на странична организация. Страницирането е прозрачно за потребителската програма - то се добавя между процесора и паметта на компютъра. Затова и често се смята, че то може да се включи в произволна система. Това заключение е вярно, когато страничната организация се използва само за разпределение на паметта, където липса на страница означава грешка (гл. VII). Но то не е вярно, когато липсата на страница означава въвеждане на допълнителна страница в паметта и рестартиране на програмата.

Реализацията на функциите на управлението на паметта при виртуалната памет е значително no-сложна, защото:

1. Информацията за състоянието на паметта се съхранява в три таблици -таблица на страниците на процеса, таблица на кадрите на системата и карта на файловете (съдържаща адресите на външната памет, където са записани страниците на процеса).

2. Определянето кой и кога ще получи памет само частично се решава от планиращата програма - нужни страници се въвеждат и по време на изпълнение.

3. Разпределението решава колко страници и къде да бъдат въведени.

4. Освобождаването на памет при завършване на процес освобождава всички негови кадри. Освен това, ако няма свободен кадър в основната памет, такъв трябва да се освободи и съответната страница се извежда във вторичната памет.



8.2.СТРАТЕГИИ ЗА ВЪВЕЖДАНЕ НА СТРАНИЦИ

Стратегиите за въвеждане на страница определят в кой момент трябва да севъведе страница от вторичната в основната памет. Използват се две стратегии.

При първата стратегия, въвеждане на страница при поискване (demand paging), страница се въвежда при действително обръщане към нея. От вторичиата памет не се въвежда страница дотогава, докато към нея изпълняваният процесне се обърне явно. При стартирането на процес в паметта няма нито една иегова страница (чисто въвеждане при поискване).

Втората стратегия - предварително въвеждане на страници (prepaging), предполага, че се използват методи за прогнозиране на потребностите на процесите от нови страници и след това, при поява на свободно място, те се въвеждат в основната памет. Така необходимите страници вече ще бъдат в паметта, когато процесът се обърне към тях. Тази стратегия позволява да се намалят прекъсванията поради липса на страница, характерни за първата стратегия, но за съжаление в много случаи е трудно да се предскаже към кои страници ще се обръща процесът. Цената е предварително въведена страница, към която няма обръщане. Затова, въпреки предимствата на този подход, традиционно се смята, че е по-изгодно да се приложи въвеждане на страници при поискване.

По-нататък в изложението се разглежда апаратьт на въвеждане на страници при поискване, както и някои възможности за предварително въвеждане.

8.3. СТРАТЕГИИ ЗА ИЗВЕЖДАНЕ НА СТРАНИЦИ

Както беше вече посочено, понякога се оказва, че при въвеждането на страница няма свободен кадър и е необходимо някаква страница да бъде изведена обратно във вторичната памет. Изборът на стратегия за извеждане на страница (за смяна на страници) има голямо значение, като се има предвид, че виртуалната памет работи бързо, ако търсената страница се намира в основната памет, т.е.прекъсванията и смяната на страници стават по-рядко. Съществуват многоалгоритми [7,9, 13,23,43, 85, 88], които могат да се оценят чрез траекториятана обръщанията към паметта и изчислението на броя на страничнитепрекъсвания. За да се намали обемът на данните, no-удобно е да се използва траекторията на страниците, отразяваща реда на извикване на страниците на изпълнявания процес. Също така е необходимо да се знае за всеки процес броят на страниците му в основната памет. С увеличаването на страниците в паметта очевидно ще намаляват прекъсванията (фиг. 8.3, т. 8.5). Алгоритмите могат да се прилагат спрямо всички кадри на основната памет (глобална стратегия)или спрямо кадрите на всеки процес поотделно (локална стратегия).



Оптимално извеждане. Биледи предлага алгоритъм, съгласно който трябва да се извежда страницата, към която най-късно ще има обръщане. Този алгоритъм е практически нереализуем, тьй като почти е невъзможно да се предсказват бъдещите обръщания към паметта, но е полезен като еталон за сравнение на други, реализуеми алгоритми.

Извеждане на случайна страница. Лесна за реализация стратегия, която не дискриминира потребители - страница се избира равновероятно. Очевидно е, че често се изхвърлят необходими страници. Тъй като тук се подхожда съгласно принципа „господар или пропаднал", в реалните системи рядко се прилага.

Извеждане на първата въведена страница (FIFO). С всяка страница се свързва моментьт на постьпването и в основната памет и при необходимост се извежда най-старата страница. Алгоритъмът е прост, но дава лоши резултати, особено при натоварване на системата, тъй като често се изхвърлят нужни страници. Най-стара страница не означава най-малко необходима.

За този алгоритъм е характерна аномалията на Биледи, която се свежда до увеличаване на броя на прекъсванията с увеличаване на броя на кадрите, отделени на процеса. Тя е илюстрирана на фиг. 8.1 за програма с 5 виртуални

страници, използвани в реда: 123412512345. Броят на прекъсванията (10) за 4 кадъра е по-голям от броя на прекъсванията (10) за 4 кадъра е по-голям от броя на прекъсванията (8) за 3 кадъра.


с. 1 с. 2

скачать файл