Стратегии за въвеждане на страници

Те определят в кой момент трябва да се въведе страница от вторичната в основната памет.

Има две стратегии:

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

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

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

Алгоритми апроксимиращи LRU:

• 
  Допълнителни битове на използване.
  

• 
  Втори шанс. В неговата основа е алгоритъмът FIFO. За да се избегне изхвърлянето на нужни страници., проверява се стойността на бита на използване на най-старата страница. Ако е нула страницата е стара и неизползвана, и се сменя незабавно. Ако битът е единица на страницата се дава “втори шанс” като битът се нулира.
  

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

• 
  Извеждане на най-рядко използвана страница(LFU). LFU поддържа брояч на
  

• 
  Извеждане на най-често използвана страница(MFU). Мотивацията e, че страницата с
  

• 
  Класове от страници. Освен бита за използване на страници, въвежда се още един бит
  

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

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

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

Друг подход е да се разреши на процесите с висок приоритет да избират кадри при замяна на страници не само от собствените си кадри, но и от кадрите на по-ниско приоритетните п-си.

8.5. Локалност на обръщенията

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

Локалноста е следствие н организация на програмите и данните, където са използвани цикли, от програми, стекове, броячи (времева локалност), масиви от данни, последователно изпълнение на прогр. (пространствена локалност).

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

Със замяната на страници е свързан и проблема с така нареченото ‘боксуване’ (задръстване), което означава ,че изчислителните способности на системата рязко спада в следствие на интензивното изв. и въвежд. на едни и същи страници по причина на недостатъчен обем оперативна памет, притежавана от отделните п-си. Процес боксува, ако изразходва повече време за смяна на страници отколкото за изпълнение на програмата. При локална стратегия всеки п-с получава фиксиран брой кадри, които могат да се окажат недостатъчни при нарастване на работните им множества от страници. При глобална стратегия процес може да отнеме нужни кадри на друг п-с, който от своя страна отнема кадри на следващ п-с и т.н., което води до усилване на движението на страници. Затова правило е, че на процесите трябва да се разпредели неох. обем памет. Единственото ефикасно средство против боксуването е да се ограничи броят на процесите, получаващи памет. За целта обикновенно се ограничава опашката на готовите п-си или се управлява натоварването. Управлението на натоварването може да се извърши по различни начини-ч/з преустановяване и възобновяване на процеси, очаква се оператора да забележи боксуването и да вземе мерки. Принципно решение на проблема дава концепцията на работното множество:

Всеки п-с в даден момент t има работно множество от страници w(t,T), представляващо съвкупността от страници, към които п-сът се е обръщал в течение на интервала от време

(t-T,t). Или в работното м-во влизат тези страници към които е имало обръщение през последните Т единици прозесорно време на п-са. Т се нарича размер на на прозореца на работното м-во и неговият избор на решаваща роля за ефективноста на управлението на паметта.

Нов процес може да се стартира и изпълнява само, ако има достатъчно място за работното му множество. Страница може да се изхвърли само , ако не е член на работното му множество на изпълнявания процес.

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

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

Директен начин да се контролира боксуването е да се използва честотата на страничното прекъсване(PFF) или PFF алгоритъм за разпределение. Когато тази честота е твърде висока това означава че на процеса са необходими повече кадри, и обратното. Може да се установи горен и долен праг на желаната честота. Ако се достигне горната граница, на процеса се разпределят нови кадри. При достигане на долния праг от процеса се отнемат кадри.

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

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

При локалната стратегия броят на кадрите, разпределени на процес, не се променят, докато при глобалната стратегия един процес може да увеличи своя брой кадри за сметка на други процеси.

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

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

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

1. 
   Обмен да се извърши само със системната памет като Данните се копират между двете памети
   

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

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

8.7.6. Размер на страниците

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

-По големият размер на страниците намалява времето за входно-изходни операции (четене/запис на сран.) по време на изпълнение на прогр.

-По-големият размер води до въвеждане на излишна инф., която може и да не потрябва;

-Намаляването на р-ра на сран. позволява по компактно работно м-во от страници, съдържащи най-използваните обекти.

-по-малката стр. води до намаляване на вътрешната фрагментация, която е половината от последната страница;

Виртуалната памет маже да бъде използвана по два начина:

ОС с единна виртуална памет-една за всички потребители, образува се с общо логическо адресно просранство.

ОС с множествена виртуална памет-създават се отделни адресни пространства за заданията на всеки потребител. Всеки потребител има възможност за монополно използване на цялата виртуална памет.

Допуска сегментна, странично/сегментна и странична организация.

Виртуалният адрес има две съставни-селектор и отместване. Селекторът се използва за индексиране на системни дескрипторни таблици. Дескрипторите описват системни обекти. Сегментите на паметта се описват от сегментни дескриптори. Отместването е спрямо на1алото на сегмент със стойност 32 бита. Виртуалната памет в 386/486 използва 2 таблици LDT (локална таблица на дескр), GDT (глобална табл. на дескр.). Има само една обща за всички програми глобална таблица GDT, описваща всички системни сегменти. Всяка програма има собствена локална табл.LDT. Достъпът до даден сегмент се извършва ч/з селектора му, който се зарежда в един от шестте сегментни регистри. Селекторът има дължина 16 бита, битовете-0-1 определят нивото на защита (0-3), бит 2-в коя таблица е описан сегм. и битовете 3-15-индекс на елемент на таблица.

15 2 1 0

Индекс

GDT/LDT

Защита

Селектор

Дескрипторите имат дължина 8 байта. Имат следната структура-базов адрес, граница и следната информация: Бит G-гранулация на сегмента (G=0-байтова, G=1-странична). D-вид процесор (D=0-работи се с 16 битово отместване за 286,D=1-работи се с 32 битово отместване за 386/486), бит AVL-за използване от системни програмисти, бит Р-присъствие на сегм. в основната памет (Р=1 да, Р=0 не), поле DPL-ниво на привилегия, бит S-сегментен (S=1-сегмент на паметта,S=0-друг обект), поле Type-тип на сегмента и защитата, и бит А-достъпен. Дескриптор 0 е забранен-той индицира забрана за използване на регистъра.

Когато селектор се зареди в сегментен регистър, достъпът до съответния дескриптор се реализира, като най-напред се избира, въз основа на бит2, таблица LDT/GDT. Селекторът се копира в работен р-р и трите младши бита се нулират. Адресът на избраната таблица се прибавя към него и се получава указател към дескриптор, който чете от таблицата и се пази в работен р-р.

По-нататък двойката (селектор- отместване) се преобразува във физически адрес.Ако всичко е наред, 32 битовата база се събира с отместването, в резултат на което се получава 32 битов линеен адрес.