Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

Пошук жертви

  ..И ось ми утворилися вашому прибутку, - може, ви погодитеся принести себе в жертву
А. Тутуола

Природно, для того, щоб автоматизувати процес видалення барахла" — рідко використовуваних даних і програм — ми повинні мати якийсь критерій, що легко формалізується, по якому визначається, які дані вважаються рідко використовуваними.
Один критерій вибору очевидний — за інших рівних умов, в першу чергу ми повинні вибирати як "жертву" (victim) для видалення той об'єкт, який не був змінений за час життя в швидкій пам'яті. Дійсно, ви швидше видалите з вінчестера саму іграшку (якщо у вас є її копія на дискетах), чим файли збереження!
Для ручного перенесення даних очевидний і інший критерій: потрібно видаляти (Для блоків даних, які не піддалися зміні за час перебування в швидкій пам'яті, видалення полягатиме в знищенні копії. Для модифікованих же блоків нове значення даних має бути скопійоване назад в повільну пам'ять, і лише після цього можна провести власне видалення.) те, що найдовше не використовуватиметься в майбутньому. Звичайно, будь-які припущення про майбутнє мають умовний характер, все може несподівано змінитися. Ми робимо припущення про те, що використовуватиметься, лише на підставі накопиченої статистики звернень до сторінок. Така екстраполяція не зовсім коректна логічно, тому може виявитися доцільним змиритися з деякою неточністю або неповнотою цієї статистики.
Найпростіша стратегія — викидати випадково вибраний об'єкт. При цьому не треба збирати жодної статистики про частоту використання і т. д., поважно лише забезпечити рівномірність розподілу псевдовипадкових чисел, що генеруються. Очевидно, що при цьому видалений об'єкт абсолютно необов'язково буде непотрібним
Можна також видаляти те, що найдовше знаходиться в пам'яті. Це називається алгоритмом FIFO (First In, First Outперший увійшов, перший вийшов). Видно, що це вже ледве складніше за випадкове видалення — потрібно запам'ятовувати, коли ми що завантажували.

Пошук жертви в Vax/vms і Windows Nt/2000/xp
У Vax/vms і Windows Nt/2000/xp застосовується цікавий варіант цього алгоритму. У цих системах сторінка, оголошена жертвою, виключається з адресного простору завдання (у відповідного дескриптора виставляється біт відсутності), але не віддається негайно під іншу нужду. Замість цього сторінки, помічені як відсутні, поміщаються в пул вільних сторінок, який, за сумісництвом, використовується і для дискового кеша і може займати більше половини оперативної пам'яті. В Vax/vms цей пул складається з трьох черг (мал. 5.19).
1. Черга модифікованих сторінок, що чекають записи на диск (у міру запису, ці сторінки переходять в другу чергу).
2. Черга немодифікованих сторінок.
3. Черга вільних сторінок (визволених прикладною програмою або що визволилися після її завершення).

Жертвою з рівною імовірністю може бути оголошена як модифікована, так і немодифікована сторінка, проте для запитів прикладних програм і буферів дискового кеша використовуються лише сторінки з другої і третьої черг.

Мал. 5.19. Віртуальна пам'ять Vax/vms

Обробляючи сторінкову відмову, система не звертається до диска за вмістом необхідної сторінки, а спочатку намагається знайти її в одній з черг пулу. Якщо сторінка там, її без подальших питань включають в адресний простір завдання (мал. 5.20).
Такий алгоритм породжує багато зайвих сторінкових відмов, але забезпечує велику економію звернень до диска. В Vax/vms ця стратегія поєднується з управлінням об'ємом пулу сторінок: у кожного користувача є квота на об'єм робочої безлічі запущених ним програм. При перевищенні квоти ОС і здійснює пошук жертви серед адресних просторів завдань цього користувача. При розумному управлінні цими квотами система забезпечує вельми хороші показники навіть при невеликих об'ємах оперативної пам'яті.
Windows NT (і пізніші версії цієї системи, 2000/хр) намагається управляти пулом вільних сторінок динамічно, не надаючи адміністраторові жодних засобів для прямого налаштування. Тому на брак ОЗУ або нетиповий режим використання пам'яті ця система реагує різким падінням продуктивності. Мабуть, це падіння обумовлене розвитком автоколивань в динамічному налаштуванні пулу вільних сторінок.
Так, авторові удавалося привести в непрацездатний достаток Windows 2000 Wokrstation з 256 Мбайт ОЗУ, всього лише відкривши помилково для редагування в far файл об'ємом 64 Мбайт. Файл не перевершував 1/4 доступній оперативній пам'яті. Проте, машина "впала в КТО", не реагуючи навіть на <Ctrl>+<alt>+<del>, і знаходилася в цьому достатку достатньо довго для того, щоб зібрати довкола неї консиліум системних адміністраторів і, врешті-решт, вирішити, що простіше натискувати на кнопку системного скидання.

Мал. 5.20. Обробка сторінкової відмови (блок-схема)

Фірма Microsoft цілком усвідомлює збитковість прийнятої стратегії управління пам'яттю і офіційно не рекомендує запуськаить на серверах під управлінням Windows Nt/2000/xp більш за одне застосування або ресурсоємний сервіс.

Пул вільних сторінок, в який входять як дійсно вільні, так і відібрані в завдань як "жертви" сторінки, в тій або іншій формі підтримують всі ОС, що використовують сторінковий обмін, проте зазвичай цей пул відокремлюють від дискового кеша і при повному завантаженні він не перевершує декількох відсотків ОЗУ. При запитах ядра і сторінкових відмовах система виділяє сторінки з цього пулу, і лише при падінні його об'єму нижче за деяку межу, починає пошук жертв в адресних просторах активних процесів.
Шиболєє справедливим видалятиме той об'єкт, до якого найдовше не було звернень у минулому LRU (Leasr Recently Used). Такий підхід вимагає набору відомостей про всі звернення. Наприклад, диспетчер пам'яті повинен підтримувати в дескрипторі кожної сторінки лічильник звернень, і при кожній операції читання або запису над цією сторінкою збільшувати цей лічильник на одиницю. Це вимагає досить великих накладних витрат — у ряді робіт, наприклад, в [Краков'як 1987], затверджується, що вони будуть неприпустимо великими.
Дотепним наближенням до алгоритму LRU є так званий clock-алгоритм вживаний в багато сучасних ОС, у тому числі в системах сімейства Unix. Він полягає в наступному (мал. 5.21).

  • Дескриптор кожної сторінки містить біт, вказуючий, що до даної сторінки було звернення. Цей біт називають clock-битом.
  • При першому зверненні до сторінки, в якій clock-бит був скинутий, диспетчер пам'яті встановлює цей біт.
  • Програма, що займається пошуком жертви, циклічно переглядає всі дескриптори сторінок. Якщо clock-бит скинутий, дана сторінка оголошується жертвою, і перегляд закінчується до появи потреби в новій сторінці. Якщо clock-бит встановлений, то програма скидає його і продовжує пошук.

Мал. 5.21. Clock-алгоритм (блок-схема)

Назва clock, мабуть, походить від зовнішньої схожості процесу циклічного перегляду з рухом стрілки годинника (мал. 5.22). Очевидно що вірогідність виявитися жертвою для сторінки, до якої часто відбуваються звернення, істотно нижче. Накладні витрати цього алгоритму значно менше, чим в LRU: замість лічильника ми зберігаємо лише один біт і змінюємо його не при кожному зверненні до сторінки, а лише при першому зверненні після проходу "стрілки".

Мал. 5.22. Робота clock-алгоритма

Практично всі відомі авторові сучасні диспетчери пам'яті передбачають використання clock-алгоритма. Такі диспетчери зберігають в дескрипторі сторінки або сегменту два біта — clock-бит і ознака модифікації. Ознака модифікації встановлюється при першому записі в страніцу/сегмент, в дескрипторі якої ця ознака була скинута.

Імітація clock-алгоритма
Ранні версії процесора VAX не мали апаратний реалізованого clock-бита. BSD Unix на цих процесорах реалізував clock-алгоритм, використовуючи для цього біт відсутності сторінки.
Читачеві пропонується детально уявити собі алгоритм такого використання і знайти відзнаки між цією стратегією і FIFO-алгоритмом у виконанні Vax/vms.

Експеріментааьниє дослідження показують, що реальна продуктивність системи досить слабо залежить від вживаного алгоритму пошуку жертви. Статистика виконання реальних програм говорить про те, що кожна програма має деякий набір сторінок, званий робітником безліччю який їй в даний момент дійсно потрібний. Розмір такого набору сильно залежить від алгоритму програми, він змінюється на різних етапах виконання і т. д.. але в більшості моментів ми модем досить точно вказати його.
Якщо робочий набір запущених програм перевершує оперативну пам'ять, частота сторінкових відмов різко зростає. При браку пам'яті програмі майже на кожній команді потрібна нова сторінка, і продуктивність системи катастрофічно падає. Цей достаток по-англійськи називається thrashing (загальноприйнятого перекладу для цього слова немає) і є украй небажаним.
У системах колективного користування розмір пам'яті часто вибирають так, щоб система балансувала десь між достатком, коли всі програми тримають свою робочу безліч в ОЗУ, і трешингом.
Точне положення точки балансування визначається залежно від співвідношення між швидкістю процесора і швидкістю обміну з диском, а також від потреб прикладних програм. У багатьох старих підручниках рекомендується підбирати об'єм пам'яті так, щоб канал дискового обміну був завантажений на 50% [Краков'як 1987].
Ще одне емпіричне правило приводиться в документації фірми Amdahl: збалансована система повинна мати по мегабайту пам'яті на кожен MIPS (Million of Instructions Per Second — мільйон операцій в секунду) продуктивності центрального процесора. Якщо система не використовує пам'ять, визначену по цій формулі, є підстави вважати, що процесор також працює з недовантаженням. Іншими словами, це означає, що ви купили дуже потужний для ваших цілей процесор і заплатили зайві гроші.
Це правило було вироблене на основі досвіду експлуатації великих комп'ютерів четвертого покоління, в основному на завданнях управління базами даних. Швидкість дискової підсистеми в цих машинах була приблизно порівнянна з дисковими контроллерами сучасних персональних комп'ютерів, тому в першому наближенні цей критерій застосовний і до ПК, що особливо працює під управлінням систем з віртуальною пам'яттю — Os/2, Windows NT і системами сімейства Unix. У будь-якому випадку, для видачі рекомендацій потрібний аналіз суміші додатків, яка виконуватиметься в системі, і інших вимог до неї.
У сучасних персональних системах користувач, як правило, працює в кожен момент лише з одной-двумя програмами, і затримки у виконанні цих програм істотно знижують спостережувану швидкість системи. Тому в таких системах пам'ять зазвичай ставлять з великим запасом, так, щоб при звичайній діяльності робоча безліч програм навіть близько не личила до розміру ОЗУ. Частково це обумовлено тим, що у наш час динамічна пам'ять стає все дешевшою і дешевшою.

 

:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017