Развитие на ос. Основни типове


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



страница8/8
Дата17.10.2018
Размер2.7 Mb.
1   2   3   4   5   6   7   8

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

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

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


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

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

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

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



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

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

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

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

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

2.С всеки елемент на таблицата на страницата се свързва регистър, а в процесора се включва логически таймер или брояч. При всяко обръщение към паметта съдържанието на брояча се увеличава. При обръщение към страница, стойността на брояча се копира в съответния регистър на таблицата. Реализацията на всеки от алгоритмите иска апаратна поддръжка, тъй като стекът или регистърът трябва да се обновяват при всяко обръщение към паметта. Много системи използват различни апроксимации на LRU, които изискват минимална апаратна поддръжка и дават задоволителна производителност. Малко системи предоставят апаратна поддръжка за реализация на алгоритъма. В много системи е на разположение допълнителен бит за използване на страници , който се установява апаратно при обръщане при съответна страница.

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



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

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

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

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

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

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

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

най-малък брой обръщения е вероятно току що използвана за това не е използвана.

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

показващ дали страницата е модифицирана. (използвана, модифицирана) Клас 0 (0,0), Клас 1 (0,1), Клас 2 (1,0), Клас 3 (1,1) изхвърля се от най-ниския не празен клас. Ако са повече стр се използва или FIFO или по азбучен ред.

8.4.Разпределение на кадри

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

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

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

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

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

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

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




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



8.6. Боксуване

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



8.6.1. Работно м-во

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

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

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

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

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



8.6.2. Честота на странични прекъсвания

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



8.7. 1. Възможности за предварително въвеждане на страници.

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



8.7.2. Локална или глобална стратегия.

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

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

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



8.7.3. Таблици на страниците на повече нива.

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


2
Виртуалният адрес включва три полета. Първото поле p1 индексира таблица на стратегиите на първо ниво. Определеният елемент съдържа адреса или номера на кадъра , съдържащ таблица от второ ниво. Чрез полето p2 се индексира избраната таблица, за да се определи номера на кадъра, в който е записана страницата. Третото поле d е отместването в страницата. Ако адресът е 32 битов, полетата p1 и p2 са 10 битови , а d е 12 битово.

8.7.5.Заключване на кадри и забрана.

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



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

2.Да се свърже бит за заключване с всеки кадър.Този бит за заключване може да се използва и за

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

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

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

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

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

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

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

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



8.7.7.Единни м-ва на виртуална памет

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

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

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



8.9.Пример:INTEL80486

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

Виртуалният адрес има две съставни-селектор и отместване. Селекторът се използва за индексиране на системни дескрипторни таблици. Дескрипторите описват системни обекти. Сегментите на паметта се описват от сегментни дескриптори. Отместването е спрямо на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 битов линеен адрес.




3
Полето БАЗА е разделено на три части и осигурява съвместимост с модел 286, който има база 24 бита. Полето осигурява произволен начален адрес в 32 битовото адресно пространство. Ако не се използва странициране, което се отбелязва с бит в глобален управляващ регистър, линейният адрес се разглежда като физически и може да се чете и пише в паметта. По този начин се реализира чиста сегментация. Ако страницирането е разрешено, линейният адрес се преобразува във физически с използване на таблиците на страниците. Всяка задача има справочник на страниците, който има 24 елементи и е резидентен. Той са адресира с помощта на глобален регистър CR3. Линейният адрес включва три полета: справочник(d), страница(p) и отместване (о).


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8




База данных защищена авторским правом ©obuch.info 2020
отнасят до администрацията

    Начална страница