Управління кількістю сторінок, виділених процесу. Модель робочого безлічі
Отже, що робити, якщо в розпорядженні процесу є недостатнє число кадрів? Чи потрібно його призупинити зі звільненням всіх кадрів? Що слід розуміти під достатньою кількістю кадрів?
Трешінг (Thrashing)
Хоча теоретично можливо зменшити число кадрів процесу до мінімуму, існує якесь число активно використовуваних сторінок, без якого процес часто генерує page faults. Висока частота сторінкових порушень називається трешінг (thrashing. Іноді вживається українська термін "пробуксовка", див. Рис. 10.3). Процес знаходиться в стані трешінга. якщо при його роботі більше часу йде на підкачування сторінок, ніж на виконання команд. Такого роду критична ситуація виникає незалежно від конкретних алгоритмів заміщення.
Мал. 10.3. Частота page faults в залежності від кількості кадрів, виділених процесу
Часто результатом трешінга є зниження продуктивності обчислювальної системи. Один з небажаних сценаріїв розвитку подій може виглядати наступним чином. При глобальному алгоритмі заміщення процес, якому не вистачає кадрів, починає відбирати кадри у інших процесів, які в свою чергу починають займатися тим же. В результаті всі процеси потрапляють в чергу запитів до улаштування вторинного пам'яті (знаходяться в стані очікування), а чергу процесів в стані готовності порожніє. Завантаження процесора знижується. Операційна система реагує на це збільшенням ступеня мультипрограммирования. що призводить до ще більшого трешінгу і подальшого зниження завантаження процесора. Таким чином, пропускна здатність системи падає через трешінга.
Ефект трешінга. що виникає при використанні глобальних алгоритмів, може бути обмежений за рахунок застосування локальних алгоритмів заміщення. При локальних алгоритмах заміщення якщо навіть один з процесів потрапив в трешінг. це не позначається на інших процесах. Однак він багато часу проводить в черзі до пристрою вивантаження, ускладнюючи підкачування сторінок інших процесів.
Критична ситуація типу трешінга виникає незалежно від конкретних алгоритмів заміщення. Єдиним алгоритмом, теоретично гарантує відсутність трешінга. є розглянутий вище не можна реалізувати на практиці оптимальний алгоритм.
Отже, трешінг - це висока частота сторінкових порушень. Hеобходимо її контролювати. Коли вона висока, процес має потребу в кадрах. Можна, встановлюючи бажану частоту page faults. регулювати розмір процесу, додаючи або віднімаючи у нього кадри. Може виявитися доцільним вивантажити процес цілком. Вивільнені кадри виділяються іншим процесам з високою частотою page faults.
Для запобігання трешінга потрібно виділяти процесу стільки кадрів, скільки йому потрібно. Але як дізнатися, скільки йому потрібно? Необхідно спробувати з'ясувати, як багато кадрів процес реально використовує. Для вирішення цього завдання Деннинг використовував модель робочого безлічі. яка заснована на застосуванні принципу локальності.
Модель робочого безлічі
Розглянемо поведінку реальних процесів.
Процеси починають працювати, не маючи в пам'яті необхідних сторінок. В результаті при виконанні першої ж машинної інструкції виникає page fault. вимагає підкачки порції коду. Наступний page fault відбувається при локалізації глобальних змінних і ще один - при виділенні пам'яті для стека. Після того як процес зібрав велику частину необхідних йому сторінок, page faults виникають рідко.
Таким чином, існує набір сторінок (P1. P2. Pn). активно використовуються разом, який дозволяє процесу в момент часу t протягом деякого періоду T продуктивно працювати, уникаючи великої кількості page faults. Цей набір сторінок називається робочим безліччю W (t, T) (working set) процесу. Число сторінок в робочому безлічі визначається параметром Т. є неубивающей функцією T і відносно невелика. Іноді T називають розміром вікна робочого безлічі, через яке ведеться спостереження за процесом (див. Рис. 10.4).
Мал. 10.4. Приклад робочого безлічі процесу
Коли процес виконується, він рухається від одного робочого безлічі до іншого. Програма зазвичай складається з декількох робочих множин, які можуть перекриватися. Hапример, коли викликана процедура, вона визначає нове робоче безліч, що складається з сторінок, що містять інструкції процедури, її локальні і глобальні змінні. Після її завершення процес залишає це робоче безліч, але може повернутися до нього при новому виклику процедури. Таким чином, робоче безліч визначається кодом і даними програми. Якщо процесу виділяти менше кадрів, ніж йому потрібно для підтримки робочого безлічі, він буде перебувати в стані трешінга.
Принцип локальності посилань перешкоджає частим змінам робочих наборів процесів. Формально це можна виразити таким чином. Якщо в період часу (t-T, t) програма зверталася до сторінок W (t, T). то при належному виборі T з великою ймовірністю ця програма буде звертатися до тих же сторінок в період часу (t, t + T). Іншими словами, принцип локальності стверджує, що якщо не занадто далеко заглядати в майбутнє, то можна досить точно його прогнозувати виходячи з минулого. Зрозуміло, що з плином часу робочий набір процесу може змінюватися (як за складом сторінок, так і по їх числу).
Найбільш важлива властивість робочого безлічі - його розмір. ОС повинна виділити кожному процесу достатню кількість кадрів, щоб помістилося його робоче безліч. Якщо кадри ще залишилися, то може бути ініційований інший процес. Якщо робочі безлічі процесів не поміщаються в пам'ять і починається трешінг. то один з процесів можна вивантажити на диск.
Інший спосіб реалізації даного підходу може бути заснований на відстеженні кількості сторінкових порушень. викликаються процесом. Якщо процес часто генерує page faults і пам'ять не надто заповнена, то система може збільшити число виділених йому кадрів. Якщо ж процес не викликає виняткових ситуацій протягом деякого часу і рівень генерації нижче якогось порога, то число кадрів процесу може бути урізано. Цей спосіб регулює лише розмір безлічі сторінок, що належать процесу, і повинен бути доповнений будь-якої стратегії заміщення сторінок. Незважаючи на те що система при цьому може пробуксовувати в моменти переходу від одного робочого безлічі до іншого, пропоноване рішення в змозі забезпечити найкращу продуктивність для кожного процесу, не вимагаючи ніякої додаткової настройки системи.