Алгоритми за преместување на мемориски страници

Алгоритми за преместување на мемориски страници (анг. Page replacement algorithms)

Апстрактно

Меморијата е многу битен ресурс кој мора да биде внимателно управуван. Системите на управување со меморијата може да се поделат на две класи: Класа која при извршување на процесите, истите ги движат од меморијата до тврдиот диск и назад(замена анг. Swapping и страничење анг.paging), и класа која не го прават тоа. Втората класа е полесна за проучување од првата. Како и да е, денеска овој начин на управување со меморијата не се применува поради тоа што денешните компјутери се графички ориентирани. Па така, не секогаш има доволно меморија за да ги задржи сите активни процеси одеднаш, туку некои процеси мора да бидат задржани на некој диск и динамично да се повикуваат. Постојат два пристапи кои се користат за управување на меморијата зависно од хардверот. Наједноставен пристап е пристапот со замена (анг. Swapping). Тој се состои од земање на целиот процес, пуштање на процесот да работи некое време, и потоа враќање на процесот назад на дискот. Вториот пристап се нарекува вертуелна меморија. Кај овој пристап, процесите работаат дури и кога само дел од нив се наоѓа во главната меморија (RAM). Многу од системите на виртуелна меморија користат техника која се нарекува страничење. Следи краток опис на оваа техника. На секој компјутер постои множество на мемориски адреси кои се произведуваат од страна на процесите. Кога некоја програма користи инструкција како

MOV REG, 1000

Тој ја копира содржината на мемориската адреса 1000 во REG (или обратно, зависи од компјутерот). Адресите можат да бидат генерирани(создадени) користејќи индексирање(анг. Indexing), сегментни регистри (анг. segment registers) и други начини. Овие адреси генерирани од страна на програми се нарекуваат виртуелни адреси и формираат виртуелен адресен простор. Овој простор е поделен на посебни единици кои се нарекуваат страници(анг. pages). Соодветните страни во физичката меморија се нарекуваат рамки на страниците(анг. page frames). На пример, ако имаме 64kb виртуелен адресен простор и 32kb физичка меморија, добиваме 16 виртуелни страни и 8 рамки на страните.

Во случај кога програмата пробува да искористи не мапирана страница, како на пример, при користење на следнава инструкција

MOV REG, 32780

која е бајт 12 во виртуелна страница 8, MMU(Memory Management Unit) гледа дека страницата не е мапирана и предизвикува CPU(Central Processing Unit) да се фати во стапица. Оваа појава се нарекува дефект на страницата(анг. page fault).

Причина за постоење на алгоритмите за преместување на сраници

При појава на дефект на страница, оперативниот систем мора да одбере страница и да ја извади од меморијата за да направи место за новата не-мапирана страница. Ако страницата која е избрана за вадење е изменета додека била во меморијата, мора да биде повторно запишана на дискот па дури потоа заменета со новата. Ако, во случај, страницата не била менувана, новата страница се запишува над неа.

Иако е возможно да се одбере произволна страница за замена, перформансите на системот ќе бидат подобри ако се одбере страница која не е премногу користена. Доколку од меморијата се избрише страница која е често користена, веројатноста е многу голема истата да има потреба повторно да се врати назад. Ова резултира во зголемување на времето за размена на страници. Во целиот тек на развојот на компјутерската индустрија многу е работено на подобрување на алгоритмите за преместување на страници, експериментално колку и теоретски. Подолу ќе опишеме неколку побитни алгоритми.

Оптимален алгоритам - алгоритам за преместување на страници

Ова е теоретски оптимален алгоритам за преместување на страници. Познат е и како OPT, clairvoyant(1) алгоритам за преместување или правецот за преместување на страници на Bélády(2). OPT работи на следниов начин: кога некоја страница треба да се вметне во меморијата, оперативниот систем ја вади страницата која би требало повторно да се користи најдалеку во иднина. На пример, имаме страница која нема да ја користиме во следните 7 секунди и страница која ќе ја користиме повторно за 0,4 секунди. Со овој алгоритам, страницата која нема да се користи во следните 7 секунди ќе биде преместена наместо онаа која ќе ја користиме за 0,4 секунди.

Овој алгоритам не може да биде имплементиран кај оперативните системи за општа употреба бидејќи не е возможно да се пресмета точно колку време ќе помине пред да биде повторно искористена некоја страница. Не земајќи го предвид ова ограничување, постојат алгоритми кои нудат скоро-оптимални перформанси- оперативниот систем го следи сите страници кои ги користи некој програм, и тие податоци ги користи за да одлучи кои страници да ги премести. Овој алгоритам ни нуди скоро-оптимални перформанси, но не и при првото вклучување на некој програм, и само доколку мемориското повикување на некој програм е релативно во согласност секојпат кога програмата е повикана.

Иако овој метод е корисен за оценување на другите алгоритми за страничење, нема никаква примена во порактичните системи.

Не-скоро-употребен - алгоритам за преместување на страници

(Not Recently Used, NRU)

За некој систем да може да собере корисни податоци за тоа колку некоја страна е користена и колку не е, повеќете компјутери со виртуелна меморија користат два бита кои го покажуваат статусот на секоја страна. Битот R се користи секогаш кога некоја страна е повикана, а битот M секогаш кога некоја страна е променета(изменета). Битно е да се сфати дека овие битови мора да бидат ажурирани(анг. Updated) на секое повикување од страна на меморијата, па е многу битно тие да бидат поставени од страна на хардверот. Кога битот еднаш бил поставен на 1, останува 1 сè додека оперативниот систем не го постави повторно на 0 во софтверот.

Ако ахрдверот ги нема овие битови, истите може да бидат симулирани на следниов начин: Кога некој процес е започнат, целата негова тебела на страници е обележана како да не е во меморија. Кога било која страница од табелата е повикана од страна на меморијата, се појавува дефект на страницата(page fault). Оперативниот систем тогаш го поставува R битот, ја променува табелата на страници да покажува на точната страница, со мод READ ONLY, и ги рестартира инструкциите. Ако во истиот момент оваа страница е изменета, нова дефект на страница ќе се појави и ќе му дозволи на оперативниот систем да го постави битот M и да го промени модот на страницата во READ/WRITE.

R и M битовите може да се искористат за изградба на едноставен алгоритам каков што е следниов. Кога некој процес е започнат, двата бита се поставуваат на 0 од страна на оперативниот систем. Потоа, периодично, R битот се ресетира за да се разликуваат страници кои не биле повикани во скоро време од оние кои биле.

При појава на дефект на страница, оперативниот систем ги проверува сите страници и ги дели на четири категории, во зависност од состојбата на R и M битовите.

Класа 0: неповикана, непроменета. Класа 1: неповикана, променета. Класа 2: повикана, непроменета. Класа 3: повикана, променета.

Иако се чини дека страниците од класа 1 се невозможни, тие се случуваат кога битот R на страница од класа 3 е ресетиран од страна на прекин во такт генераторот(анг. Clock interrupt). Овие прекини не го ресетираат M битот затоа што тој содржи информација потребна за да се знае дали страницата треба да биде пре-напишана на дискот или не. Со ова ресетирање на R но не и на М води до појава на страница од класа 1.

NRU алгоритмот произволно брише страница од најниска класа. Безусловно кај овој алгоритам е тоа дека подобро е да се премести изменета страница која не била повикана во скоро време отколку чиста страница која е многу употребувана. Најпривлечно кај NRU алгоритмот е тоа што е лесно разбирлив, средно ефикасен за имплементирање, и овозможува, ако не оптимални, адекватни перформанси.

Прв внатре, прв надвор - алгоритам за преместување на страници

(First-In, First-Out; FIFO)

FIFO е наједноставниот алгоритам за преместување на страници. Идејата е очигледна од самото име на алгоритмот- оперативниот систем ги следи сите страници во меморијата во редица во која најновата страница влегува на крајот, а најстарата е на почетокот. Кога доаѓа до потреба некоја страница да се промени, се бира страницата на почетокот на редицата. Додека FIFO е евтин и интуитивен, неговите перформанси се прилично слаби во практика.

FIFO е користен од страна на VAX/VMS (3) оперативниот систем, со мали промени. Парцијална втора шанса е можна со прескокнување на ограничен број на влезни податоци со валидно преведени табели на повикување, и додатно, страниците се разместени од множество на процеси кои работаат, во системски базен од кој истите може да бидат повратени ако не се веќе повторно искористени.

FIFO е конзервативен алгоритам, па така ова е неговата формула.

Втора шанса – алгоритам за преместување на страници

(Second Chance)

Овој алгоритам претставува едноставно изменета верзија на FIFO алгоритмот која го прескокнува проблемот на отфрлање на многу употребувана страница така што врши проверка на R битот на најстарата страница. Ако битот покажува 0, страницата е и стара и некористена, така да веднаш се преместува. Доколку R битот покажува 1, битот е ресетиран, страницата е се става на крајот на списокот на страници, и нејзиното време на вчитување е ажурирано исто како да е штотуку стасана во меморијата. Пребарувањето продолжува понатаму.

Следната слика ја покажува целата оваа постапка. На неа се гледаат страниците од A do H сместени на поврзана листа и сортирани според времето на пристигнување во меморијата.

Она што “Втора шанса” го прави, е тражење на стара страница која не била повикана во претходниот тактен интервал. Ако сите страници биле повикани, алгоритмот дегенерира во чист FIFO-заснован алгоритам. Поспецифично, да замислиме дека R битовите на сите страници на претходната слика се поставени. Една по една, оперативниот систем ги преместува страниците на крајот од листата, ресетирајќи го R битот секој пат кога се вчитува нова страница на крајот од листата. Случајно, доаѓа до страницата А, чиј R бит е ресетиран. Во оваа точка, страницата А е протерана. Во овој случај алгоритмот секогаш завршува.

Часовникот – алгоритам за преместување на страници

(The Clock)

Иако алгоритмот со втора шанса е прифатлив, тој е непотребно неефикасен бидејќи константно префрла страници во својата листа. Подобар пристап е да се зачувуваат сите рамки на страниците во циклична листа во форма на часовник, прикажан на следната слика. Стрелката покажува на најстарата страница во листата.

При појава на дефект на страница, се испитува страницата на која покажува стрелката. Доколку R битот е 0, страницата е протерана, новата страница се внесува во часовникот на нејзиното место, а стрелката се придвижува едно место нанапред на следната страница. Ако R е 1, битот се ресетира и стрелката се поместува едно место нанапред. Овој процес се повторува сè додека не се најде страница со R бит еднаков на 0. Овој алгоритам се разликува од алгоритмот со втора шанса само при имплементирање.

Резиме

Разгледавме неколку од многуте алгоритми за преместување на страници. Во прилог ќе дадеме еден краток опис на секој од нив.

7.1 OPT ги преместува страниците кои се повикани во најбрзо време од множеството на присутни страници. Како и да е, не постои начин да се детерминира која страница всушност е последно повикана, па затоа овој алгоритам не може да се искористи во практика. Корисен е само како модел по кој се оценуваат останатите алгоритми.

7.2 NRU алгоритмот ги дели страниците на четири класи во зависност од состојбата на R и M битовите. За преместување се избира произволна страница од страниците од најниска класа. Овој алгоритам лесно се имплементира, но е многу груб. Постојат подобри алгоритми.

7.3 FIFO следи кога страниците се вчитани во меморијата и ги вметнува во поврзани листи. Тој ја исфрла најстарата страница од листата, но тука проблем претставува можноста дека таа страница сè уште е во употреба. Па, поради тоа, FIFO е лош избор на алгоритам.

7.4 Втора шанса е изменета верзија на FIFO која проверува дали некоја страница е во употреба пред да ја исфрли. Во случај да е, ја поштедува. Оваа модификација ги зголемува перформансите на овој алгоритам.

7.5 Часовникот има исти перформанси како и втора шанса, но се разликува во една работа. Потребно е малку пократко време за извршување на алгоритмот.

Забелешка: Сите слики искористени во овој документ се преземени од: A.S. Tanenbaum, Modern Operating Systems: 2ed, Prentice-Hall, 2001

Библиографија

• A.S. Tanenbaum, Modern Operating Systems: 2ed, Prentice-Hall, 2001