Модель робочої множини

Розглянемо поведінку реальних процесів.

Процеси починають працювати, не маючи в пам'яті необхідних сторінок. В результаті при виконанні першої ж машинної інструкції виникає page fault, що вимагає підкачки порції коди. Наступний page fault відбувається при локалізації глобальних змінних і ще один - при виділенні пам'яті для стека. Після того, як процес зібрав велику частину необхідних йому сторінок, page faults виникають рідко.

Таким чином, існує набір сторінок (P1, P2 ... Pn), що активно використовуються разом, який дозволяє процесу у момент часу t протягом деякого періоду T продуктивно працювати, уникаючи великої кількості page faults. Цей набір сторінок називається робочим безліччю W(t,T) (working set) процесу. Число сторінок в робочій множині визначається параметром Т, є неубутною функцією T і відносно невелико. Іноді T називають розміром вікна робочої множини, через яку ведеться спостереження за процесом (див. мал. 10.4).

Рис. 12.4. Приклад робочої множини процесу

Легко написати тестову програму, яка систематично працює з великим діапазоном адрес, але, на щастя, більшість реальних процесів не ведуть себе так само, а проявляють властивість локальності. Протягом будь-якої фази обчислень процес працює з невеликою кількістю сторінок.

Коли процес виконується, він рухається від однієї робочої множини до іншого. Програма зазвичай складається з декількох робочих множин, які можуть перекриватися. Hапример, коли викликана процедура, вона визначає нову робочу множину, що складається із сторінок, що містять інструкції процедури, її локальні і глобальні змінні. Після її завершення процес покидає ця робоча множина, але може повернутися до нього при новому виклику процедури. Таким чином, робоча множина визначається кодом і даними програми. Якщо процесу виділяти менше кадрів, чим йому вимагається для підтримки робочої множини, він знаходитиметься в змозі трешинга.

Принцип локальності посилань перешкоджає частим змінам робочих наборів процесів. Формально це можна виразити таким чином. Якщо в період часу програма зверталася до сторінок W(t,T), то при належному виборі T з великою вірогідністю ця програма звертатиметься до тих же сторінок в період часу (t, t+T). Іншими словами, принцип локальності стверджує, що якщо не дуже далеко заглядати в майбутнє, то можна достатньо точно його прогнозувати виходячи з минулого. Зрозуміло, що з часом робочий набір процесу може змінюватися (як по складу сторінок, так і по їх числу).

Найбільш важлива властивість робочої множини - його розмір. ОС повинна виділити кожному процесу достатнє число кадрів, щоб помістилася його робоча множина. Якщо кадри ще залишилися, то може бути ініційований інший процес. Якщо робоча безліч процесів не поміщається в пам'ять і починається трешинг, то один з процесів можна вивантажити на диск.

Вирішення про розміщення процесів в пам'яті винне, отже, базуватися на розмірі його робочої множини. Для процесів, що вперше ініціюються, це рішення може бути ухвалене евристично. Під час роботи процесу система повинна уміти визначати: розширює процес своя робоча множина або переміщається на нову робочу множину. Якщо до складу атрибутів сторінки включити час останнього використання ti (для сторінки з номером i), то приналежність i-й сторінки до робочого набору, визначуваного параметром T у момент часу t виражатиметься нерівністю: t-T < ti < t. Алгоритм виштовхування сторінок WSClock, що використовує інформацію про робочий набір процесу, описаний в [Таненбаум, 2002].

Інший спосіб реалізації даного підходу може бути заснований на відстежуванні кількості сторінкових порушень, що викликаються процесом. Якщо процес часто генерує page faults і пам'ять не дуже заповнена, то система може збільшити число виділених йому кадрів. Якщо ж процес не викликає виняткових ситуацій протягом деякого часу і рівень генерації нижче якогось порогу, то число кадрів процесу може бути урізане. Цей спосіб регулює лише розмір безлічі сторінок, що належать процесу, і має бути доповнений якою-небудь стратегією заміщення сторінок. Не дивлячись на те що система при цьому може пробуксовывать в моменти переходу від однієї робочої множини до іншого, пропоноване рішення в змозі забезпечити якнайкращу продуктивність для кожного процесу, не вимагаючи ніякого додаткового налаштування системи.