Последната актуализация на този раздел е от 2021 година.

 

6.4.2  Алгоритми за заместване на страници

 

 

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

1.       Търсената страница съществува и нейното зареждане от външната памет в оперативната памет не създава проблеми ;

2.       Търсената страница съществува, но нейното зареждане от външната памет в оперативната памет не е възможно да се осъществи веднага.

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

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

      Обърнете внимание, че при заместване се налага двукратно прехвърляне на страници между основната и външната памет. Този процес може да бъде оптимизиран като се използва атрибутът за модификация на страничния кадър (съдържа се в таблицата на страниците). Флагът за модификация се вдига, ако поне един байт в дадената страница е бил записан (актуализиран) от изпълнявани преди това машинни команди. Когато операционната система трябва да избере кандидат за изхвърляне, тя най-напред преглежда страниците с този атрибут и ако се намери страница, чийто бит за модификация не е установен, нейното място може да се счита за свободно. Това е така, защото нейното копие върху диска е абсолютно идентично със страничния кадър. Страниците, за които изначално се знае че са от тип само за четене (read only), не се модифицират и тяхното предпочитане като кандидати за изхвърляне значително намаляват времето на процедурата за заместване.

      Като цяло, разглежданата тук тема и до ден днешен остава открита. Търсенето и експериментирането с все “по-умни” алгоритми продължава, при това в условията на безкомпромисна конкуренция. Ясно трябва да се заяви, че формални методи за синтез на алгоритми за заместване на страници не съществуват – частните съображения, които следва да бъдат отчетени, са изключително много, а и самата задача по определение се явява многокритериална. В този смисъл постигането на единствен “най-добър” алгоритъм в смисъла на всички критерии е невъзможно. Интересно е да се отбележи, че проблемът с оптималното управление на паметта е закопан дълбоко и по тази причина различните водещи критерии раждат различни операционни системи, за които по същество задачата за управление на паметта е изначална и една от основните. По същество следва да се решат 3 главни задачи, на всяка от които съответства определена стратегия:

·         Избор на страница и стратегия за доставка (fetch policy) ;

·         Поместване на страницата в оперативната памет и стратегия за поместване (placement policy) ;

·         Заместване на страница и стратегия за заместване (replacement policy ).

      Първата задача се решава чрез прилагане на някоя от следните две стратегии:

·         При поискване (on demand). Действия по доставката на физическа страница стартират като следствие на page fault. Доставя се от диска липсващата страница ;

·         С изпреварване (in cashe). Доставката на страници се осъществява изпреварващо – освен самата тя, търсената, така и нейното близко обкръжение. Страничният кадър се доставя, защото е поискан от програмата, но останалите кадри се доставят без да са необходими и в резултат на политиката за предвидливост, т.е. изпреварващо във времето.

      Втората задача се решава лесно – доставената от диска страница се помества в първия срещнат свободен страничен кадър на оперативната памет.

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

      В началото трябва да кажем, че алгоритмите за заместване на страници се делят на:

·         Физически нереализуеми. Това са алгоритми, които разчитат в своята реализация на реална информация за налагащите се обръщения към паметта в бъдеще време. Ясно е, че какъвто и да е алгоритъмът, в условия на известно бъдещо поведение, този алгоритъм може да се признае за оптимален. За съжаление на лице са множество фактори, които не позволяват на операционните системи да знаят бъдещото поведение на програмите и такива алгоритми на практика няма реализирани. Все пак трябва да кажем, че тези алгоритми играят важна роля в методите за оценка и сравнение на прилаганите евристични алгоритми. Михновский С. Д. и Шор Н. З. (1965 год.) са доказали твърдението, че когато за изхвърляне се избира онази страница, чието използване в бъдеще време ще се наложи с най-голямо закъснение по сравнение с всички останали страници, то броят на налагащите се замествания на страници в по-високото ниво на паметта е минимален (при един предварително известен поток от обръщения към паметта и при известно разпределение на паметта). С други думи, всеки друг алгоритъм за заместване би породил по-голям брой замествания. По тази причина алгоритъмът на Михновский-Шор се нарича МИН-алгоритъм. Подобни резултати, година по-късно, е публикувал Belady (унгарски математик). В този вариант се предполага, че е известна вероятността за обръщение към всяка страница от програмата и ако за заместване се избира онази страница, към която има минимална вероятност за обръщение в сравнение с всички останали, то в смисъла на минимум на математическото очакване на страничната грешка, този избор е оптимален в сравнение с всеки друг. По тази причина в литературата алгоритъмът се нарича оптимален алгоритъм на Биледи или още ОПТ-алгоритъм.

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

      Алгоритмите за заместване на страници се делят още на глобални и локални. За глобални алгоритми говорим, когато операционната система търси страничен кадър в цялата оперативната памет, без при това да отчита разпределението на отделните кадри по процеси.

      Локални алгоритми са онези, при които операционната система избира страничен кадър само от множеството, вече разпределено за даден процес. Множеството кадри разпределени за даден процес може да бъде с фиксиран обем или с динамично настройващ се обем.

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

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

      Ефективността на един алгоритъм за заместване се оценява върху конкретна последователност от обръщения към паметта, за която последователност се преброяват възникналите пропуски (page fault). Тази последователност се нарича reference string (последователност на обръщенията). Повечето процесори имат някакви сравнително прости апаратни средства, които позволяват натрупването на своеобразна статистика за обръщенията към паметта. Това са обикновено 2 бита във всеки елемент от таблицата на страниците. Флагът за обръщение (reference бит) се установява автоматично, когато се направи обръщение към страницата, а флагът за изменения (modify бит) се установява, когато се актуализира съдържанието поне на един байт в страницата. Операционната система има за задача периодично (на всеки квант време) да проверява тези признаци, за да изяви активно използваните странични кадри, след което ресетира (нулира) тези битове.

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

1.       Ще приемем, че в мултипрограмен режим се изпълняват 2 процеса – процес П1, във виртуалното пространство В1 и процес П2 във виртуалното пространство В2, при това сумарният размер на реално заетите им части изпълнява следното условие: В1+В2 > ОП.

2.       Нека предположим, че в момент от времето Т1 в процеса П1 възниква искане за виртуалната страница ВС1. Операционната система обработва прекъсването като избира за заместване страничния кадър СК2, който е разпределен за виртуалната страница ВС2, от виртуалното пространство В2. За пълно обслужване на заявения достъп до данни от ВС1 са необходими два трансфера – за изхвърляне на СК2 върху диска и за доставка на копие от ВС1 в оперативната памет.

3.       Тъй като операционната система поддържа мултипрограмен режим на работа, то по време на трансфера достъп до процесора ще получи процесът П2, и той, напълно вероятно, може да поиска достъп до своята виртуална страница ВС2, която току що му е била отнета. Така отново ще възникне прекъсване и операционната система може да замени някоя страница от оперативната памет СК3, в която е разпределена виртуална страница ВС3 на процеса П1.

4.       Когато завърши обменът, свързаните с обработката изисквания за достъпа до ВС1, ще се възобнови процесът П1, и той, напълно вероятно, може да поиска достъп до своята виртуална страница ВС3 (която току що му е била отнета). И така нататък.

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

      Единствените алгоритми, които теоретически гарантират отсъствие на явлението thrashing , вече бяха споменати по-горе (МИН-алгоритъм и ОПТ-алгоритъм). Разбира се, в условията на динамични операционни системи, точното познаване на бъдещето е невъзможно. Ето защо тези алгоритми бяха определени като физически нереализуеми.

      Практическите реализации, даващи известни гаранции за отсъствие на описаното прибуксуване, се основават на създаването на работен набор от страници на процеса. Авторът на този алгоритъм Питер Деннинг, предлага използването на работния набор въз основа на принципа на локалното действие. Според съвременни изследователи, алгоритъмът на работния набор представлява практически реализуема апроксимация на оптималния алгоритъм на Биледи.

      Принципът на локалните обръщения в случая се изразява в това, че ако в период от времето [T-t, T] програмата се е обръщала към страниците (С1, С2, … , Сn), то при подходящ избор на t, с голяма вероятност тази програма ще се обръща към същите страници и в периода [T, T+t]. С други думи, принципът на локалното действие твърди, че ако не се гледа твърде далеко в бъдещето, то е възможно достатъчно добре да го прогнозираме, като изхождаме от неговото минало. Зафиксираният набор от страниците (С1, С2, … , Сn) се нарича работно множество на програмата в момента Т. Може още да се каже, че това е множеството, реално съответстващо на процеса към момента Т. Въз основа на това разбиране алгоритъмът на Деннинг, като елемент в операционната система, трябва във всеки момент от времето да осигурява наличието в оперативната памет работния набор странични кадри на всички процеси. За алгоритъма на Деннинг е известно, че:

·         Пълната му реализация практически гарантира отсъствието на буксуване (thrashing) ;

·         Доказана е апаратната му реализация ;

·         Пълната му апаратна реализация е много скъпа.

      Поради горните причини на практика се използват различни облекчени варианти на алгоритъма, основаващи се на идеята за работния набор. Тези реализации се основават на оценки за работния набор на процесите, получавани апаратно или програмно, в лицето на определено множество признаци за обръщенията към страничните кадри в оперативната памет. Периодически за всеки процес се извършват следните действия. Преглеждат се всички таблици на съответствието на виртуалната памет на дадения процес. Ако елементът на таблицата съдържа описател на физическа страница, то се анализира признакът на обръщението. Ако признакът е установен, то страницата се приема за влизаща в работния набор, а броячът ѝ на “стареене” се нулира. Ако признакът на обръщенията не е установен, то към съдържанието на брояча ѝ на стареене се добавя единица и страницата приема статус (състояние) на кандидат за изхвърляне от работния набор на процеса. Ако при поредното увеличение броячът на стареене достига определена критическа стойност, страницата се счита за излязла от състава на работния набор и нейният описател се прехвърля в списък на страниците, които могат да бъдат изхвърлени, ако е необходимо, във външната памет. По време на преглеждането на елементите в таблиците на съответствието, във всеки един от тях се нулира (ресетира) признакът на обръщенията.

      Изхвърлянето (изпомпването) на страниците от оперативната памет, които не влизат вече в работните набори на процесите, се осъществява от специален системен процес (stealer). Този процес започва работа, когато броят на страниците в списъка на свободните страници достигне определена ниска стойност. Функцията на този процес се състои в анализ на необходимостта от изпомпване на базата на признак за обновяване и запис на страницата.

      При обръщение към виртуална страница, чието физическо копие отсъства от оперативната памет, както вече бе казано, възниква прекъсване към операционната система. Ако списъкът с описатели на свободните страници не е празен, то от него се избира един описател и заявената страница се подключва към виртуалния набор на процеса.

      Ако се поиска страница в условия, когато списъкът от описатели на свободните страници е празен, тогава се стартира механизмът, наречен свопинг (swapping). Главният повод за извършване на свопинг на процеси се състои в това, че простото изхвърляне на страница от някой процес (включително и от този, който е поискал страница) представлява потенциална ситуация за настъпване на буксуване (thrashing), тъй като се разрушава цялостта на работния набор на съответния процес. Всеки процес, който заявява страница не от своя работен набор, става кандидат за изхвърляне. Повече не му се предоставят ресурси и описателят на процеса се прехвърля в опашката на системния процес, наречен swapper. Разбира се в тази опашка могат да се намират няколко процеса. Процесът swapper изпълнява последователното изхвърляне на процесите в опашката, като помества описателите на физическите им страници в списъка на свободните страници дотогава, докато броят на страниците в този списък не достигне определена горна граница. След завършване на поредната свопинг-сесия, на първия процес в опашката отново се дава възможност да продължи своето изпълнение.

      В някои операционни системи се използва опростена версия на горния алгоритъм, в която вероятността от thrashing се неутрализира за сметка на свопинга. Тази версия на алгоритъма се нарича NRU-алгоритъм (Not Recently Used). Същността на алгоритъма се състои в това, че процесът stealer периодично изчиства (нулира) признаците за обръщение към всички страници на основната памет, съответстващи на виртуалната памет на процесите. Страницата се характеризира с два бита – reference bit, който се установява в единица при всяко успешно обръщение към страницата и modified bit, който се установява в единица след всяко изменение на данните в страницата. Reference битовете се нулират през определено време. Ако възникне необходимост от изхвърляне, т.е. достигната е долната граница за дължината на списъка с описатели на свободните страници, то stealer избира в качеството на кандидати за изхвърляне преди всичко онези страници, към които не имало обръщение с цел запис след последното изчистване на признаците и които не са били модифицирани. Това са страниците от които най-безболезнено могат да се освободят процесите. На второ място се избират страници, които действително следва да бъдат изхвърлени. Паралелно с това работи описаният по-горе алгоритъм на свопинг, т.е. ако възникне заявка за страница, а свободни страници няма, то съответният процес става кандидат за свопинг. Някои операционни системи разделят страниците на 4 класа, според значението на тези класове. Класовете са следните

 

 

Referenced bit

Modified

bit

Клас  0

0

0

Клас  1

0

1

Клас  2

1

0

Клас  3

1

1

 

      При необходимост за от избор на кандидат за изхвърляне, се избира страница с най-нисък клас.

      Освен описаните алгоритми, традиционно още се прилагат (както в глобален, така и в локален вариант) такива алгоритми като:

·         FIFO-алгоритъм (First In First Out) и още

·         LRU-алгоритъм (Least Recently Used) ;

·         LFU-алгоритъм (Least Frequently Used) ;

·         MFU-алгоритъм (Most Frequently Used) .

      “Логиката” на алгоритъм FIFO е най-елементарната – на изхвърляне подлежи онази страница, която най-дълго време е останала в оперативната памет. В същност, времето не се измерва фактически. При зареждане, страниците се регистрират в един последователен списък, който поддържа системата. Списъкът е от тип FIFO-опашка (от тук идва и наименованието на алгоритъма). В десния край на списъка се намира номерът на първата страница, а в левия – на последната. Когато възникне необходимост от изхвърляне на страници, кандидатите за това са онези страници, чиито номера са десния край на списъка или с други думи в дъното на FIFO-списъка. За съжаление тази логика, или още стратегия, не оценява фактическата активност на страниците и вероятността да бъдат изхвърляни активни страници е напълно реална. Като типичен пример в литературата често се посочва работата на процес, при който работи програма текстов редактор с файл с текстови данни.

      За пълнота на картината ще споменем една модификация на алгоритъм FIFO, която се нарича алгоритъм Second-Chance. В този алгоритъм загубата на често използваните страници се избягва с помощта на анализ на признака за обръщение. Ако признакът на разглежданата страница е установен, то тя, за разлика от алгоритъм FIFO, не се изхвърля – признакът й за обръщение се нулира, а нейният номер се премества в левия край на списъка от страници, т.е. в края на FIFO-опашката. Ако при анализа и преподреждането на опашката се намери страница, чийто признак не е установен (към нея не имало обръщение), то тя подлежи на изхвърляне. Това периодично прочистване на FIFO-опашката дава възможност съдържанието на оперативната памет да бъде поддържано актуално. Ако признаците на всички страници в списъка са установени, то алгоритъмът Second-Chance се превръща в алгоритъм FIFO – изхвърля се първата в опашката страница, тъй като изхвърляне трябва да има задължително. Алгоритъмът на втория шанс е също недостатъчно ефективен, тъй като причинява непрекъснато разместване на страниците отметнати в списъка. Известно подобрение той получава ако опашката се зацикли. В така зациклената опашка указателят към кандидата за изхвърляне се интерпретира като часовникова стрелка, откъдето и произтича наименованието на тази модификация на FIFO алгоритъма – часовников алгоритъм. Логическата реализация на това зацикляне вече многократно сме разглеждали, например вижте поясненията в §4.3. В този вариант не се премества елемент в списъка, а само указателят, като той се модифицира (инкрементира) за да сочи следващата страница. Съществува вариант на този алгоритъм с две “часовникови” стрелки. Като основно достойнство на алгоритмите от тип FIFO ще отбележим тяхната лесна и икономична реализация.

      “Логиката” на алгоритъм LRU предполага, че следва да се изхвърля онази страница, към която най-отдавна не е имало обръщение. Тази логика може да се изкаже и с други думи – близкото минало е добър ориентир за прогнозиране на близкото бъдеще. Тук интуицията подсказва, че “логиката” на този алгоритъм като че ли е по-правилна в сравнение с тази на FIFO-алгоритъма. Интуицията обаче не е доказателство и за съжаление тя се опровергава от ситуации, в които алгоритъм FIFO се справя по-добре.

      LRU е добър, но доста скъп за реализация алгоритъм. Необходимо е да се поддържа свързан списък на всички страници в паметта, в началото на който се съдържат номерата на последно използваните страници. Списъкът се реализира като стек в паметта. Този списък трябва да се обновява след всяко обръщение към паметта, за което се губи много време. Съществува вариант на LRU алгоритъма, в който се използва специален 64-битов указател, който автоматично се увеличава с единица след изпълнение на всяка машинна команда, а в таблицата на страниците съществува отделно поле, в което този указател се записва, при всяко обръщение към дадената страница. Кандидатът за изхвърляне се сочи от указателят с най-малката стойност. Апаратната поддръжка на логиката на LRU алгоритъма оскъпява техническото му реализиране.

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

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

      Съществуват и други алгоритми, които тук няма да разгледаме подробно, тъй като приемаме, че принципната същност на проблематиката в този пункт е достатъчно добре изяснена. Ще споменем само две наименования, колкото да събудим интереса на читателя – NFU-алгоритъм (Not Frequently Used) и стекови алгоритми. Конкретиката на всеки алгоритъм следва да се търси в архитектурата на съответните процесори. Нека да припомним, че с алгоритмите за заместване се запознахме още при представяне на логическите структури и функциониране на кеш паметите а няколко предходни раздела. В бъдеще предстои да се запознаем и с други алгоритми за заместване.

      За задълбочено изучаване на темата препоръчваме на Читателя книгата

Andrew S. Tanenbaum  and  Herbert Bos,

MODERN  OPERATING  SYSTEMS,

Pearson Prentice-Hall, 2015, ISBN-13: 978-0-13-359162-0, pages 1140.

 

 

 

Следващият раздел е:

 

6.4.3.  Сегментна организация на паметта