10.3.4 Натискане на рядко използвана страница. Nfu (не се използва често) алгоритъм.
Друго име за този алгоритъм е LFU (The Least Frequently Used).
Софтуерна реализация на алгоритъм, близък до LRU.
Разгледаните варианти на LRU са принципно реализируеми, но, както вече беше отбелязано, те изискват специална хардуерна поддръжка, която повечето съвременни процесори не осигуряват. Затова бихме искали да имаме алгоритъм, който е достатъчно близък до LRU, но не изисква сложна специална поддръжка.
Един такъв възможен алгоритъм е NFU алгоритъмът.
Изисква програмни броячи, по един за всяка страница, които първоначално са нула. При всяко времево прекъсване (а не след всяка инструкция) операционната система сканира всички страници в паметта и за всяка страница с зададен флаг за достъп, увеличава стойността на брояча с единица и нулира флага за достъп.
По този начин страницата с най-ниска стойност на брояча е кандидатът за освобождаване, като страницата, която е била най-малко посещавана. Основният недостатък на NFU алгоритъма е, че той никога не забравя нищо. Например, страница, която е била посещавана много за известно време и след това е спряла достъпа, пак няма да бъде премахната от паметта, тъй като нейният брояч съдържа голяма стойност. Например, в многопроходни компилатори, страниците, които са били силно използвани по време на първото преминаване, могат да съхраняват големи стойности на брояча за дълго време, предотвратявайки зареждането на полезни страници в бъдеще.
За щастие е възможна лека модификация на алгоритъма, който реализира "забравяне". Достатъчно е при всяко изчакване съдържанието на всеки брояч да се измества надясно с 1 бит и едва след това да се увеличава за страници с зададен флаг за достъп (фиг. 3-27 Tanenbaum).
Други вече нетолкова лесно елиминиран недостатък на алгоритъма е продължителността на процеса на сканиране на таблици на страници.
10.3.5 Други алгоритми
За да бъде картината пълна, могат да се споменат още няколко алгоритма.
Например алгоритъмът Second-Chance - модификация на FIFO, която избягва загубата на често използвани страници - анализира r (референтен) бит за най-старата страница. Ако битът е 1, тогава страницата, за разлика от FIFO, не се изхвърля, но битът се изчиства и страницата се поставя в края на опашката. Ако всички страници са били свързани, тя става FIFO. Този алгоритъм е използван в BSD Unix.
Компютърът Macintosh използва алгоритъма NRU (неизползван наскоро), при който жертвената страница се избира въз основа на анализ на модификацията и битовете за връзка.
Има и много други алгоритми за заместване. Обхватът на този курс не позволява да ги разгледаме подробно. Подробно описание на различни алгоритми за заместване е достъпно в монографиитеDeitel, Tsikritis, Tanenbaumи други.
10.4. Тръшкане. свойство на местността. Модел работен комплект.
Ами ако процесът няма достатъчно рамки на свое разположение? Трябва ли да се спре с освобождаването на всичките му рамки. Какво означава достатъчен брой персонал?
Въпреки че теоретично е възможно да се намали броят на фреймовете, които даден процес има до минимум, има определен брой активно използвани страници, без които процесът често генерира грешки. Тази висока честота на прекъсвания на страници се наричатрешинг (трашинг, понякога се използва българският термин slippage). Един процес е в състояние на боклук, ако прекарва повече време в страниране, отколкото в изпълнение. Критична ситуация от този вид възниква независимо от конкретните алгоритми за заместване.
Ориз. 10.2 Честота на грешките на страницата
Разбиването често води до влошаване на производителността. Един от нежеланите сценарии за развитие на събитията може да изглежда така. С алгоритъма за глобална замяна, процес, който няма кадри, започва да ги взема от други процеси, а те от своя страна започват да правят същото. В резултат на това всички процеси влизат в опашката от заявки към вторичното устройство с памет, а опашката от процеси в състояние на готовност е празна. Използването на процесора намалява. Процесорът вижда това и увеличава степента на мултипрограмиране. По този начин пропускателната способност на системата пада поради трашинг.
Ефектът на боклук, който възниква при използване на глобални алгоритми, може да бъде ограничен чрез използване на алгоритми за локално заместване. Дори ако един от процесите бъде изместен в кошчето, това не засяга други процеси. Въпреки това, той прекарва много време в опашка за пейджъра, което затруднява други процеси при пейджинг.
Критична ситуация като изхвърляне възниква независимо от конкретните алгоритми за подмяна. Единственият алгоритъм, който теоретично гарантира липсата на трешинг, е оптималният алгоритъм, разгледан по-горе, който не се прилага на практика.
Така че изхвърлянето в боклука е висока честота на нарушения на страницата. Трябва да се контролира. Когато е високо, процесът има нужда от персонал. Възможно е, като зададете желаната честота на грешките, да регулирате размера на процеса чрез добавяне или изваждане на кадри от него. Както при работния набор (вижте по-долу), може да е подходящо да задържите процес чрез освобождаване на неговите рамки. Освободените рамки се разпределят към други процеси с висока честота на грешки.
За да предотвратите разбиване, трябва да разпределите колкото се може повече кадри за процесатой се нуждае. Но откъде знаеш колко му трябва. Има няколко подхода. Трябва да опитате да разберете колко кадъра всъщност използва процесът. Този подход дефинирамодел на местоположениетона изпълнение на процеса.
Същността на понятието местност е описана във въведението. Изучавайки свойствата на локалността в системите за пейджинг, Денинг (1968) формулира теорията на работните множества на програмите (виж по-долу).
Моделът на местността е, че когато даден процес работи, той се премества от едно местоположение в друго. Локалност - набор от страници, които се използват активно заедно. Една програма обикновено се състои от няколко различни локализации, които може да се припокриват. Например, когато се извика процедура, тя дефинира ново местоположение, състоящо се от операторите на процедурата, нейните локални променливи и набор от глобални променливи. След завършването си процесът напуска това място, но може да се върне отново в него. По този начин местоположението се определя от кода и данните на програмата. Имайте предвид, че локалният модел е принципът, залегнал в основата на работата на кеша. Ако достъпът до който и да е тип данни беше произволен, кешът би бил безполезен.
Ако на даден процес са разпределени по-малко рамки, отколкото са му необходими, за да поддържа своята локалност, той ще бъде в състояние на кошче.
Модел на работен комплект
В известен смисъл подходът, предложен от Денинг, е практическо приближение на оптималния алгоритъм (виж също [28]. Принципът на локалност на препратките (недоказуем, но потвърден на практика) е, че ако дадена програма има достъп до страници (P1, P2, . Pn) в периода от време (T-t, T), тогава с подходящ избор на t, с голяма вероятност тази програма ще има достъп до същите страници в периода от време (T, T+t).С други думи, принципът на локалността гласи, че ако човек не гледа твърде далеч в бъдещето, тогава може да го предвиди добре въз основа на миналото. Наборът от страници (P1, P2, . Pn) еработният наборна програмата (или, по-правилно, на съответния процес) в момент T. Ясно е, че работният набор на един процес може да се променя във времето (както в състава на страниците, така и в техния брой).
Идеята на алгоритъма за пейджинг на Denning (понякога наричан алгоритъм за работен набор) е, че операционната система трябва да гарантира, че текущите работни набори от всички процеси, на които е разрешено да се конкурират за достъп до процесора, са в основната памет във всеки един момент. Пълното внедряване на алгоритъма на Denning на практика гарантира липса на разбиване. Алгоритъмът е реализуем (известна е поне една негова пълна реализация, която обаче изисква специална хардуерна поддръжка). На практика се използват олекотени версии на алгоритми за размяна, базирани на идеята за работещ набор.