• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Система двійників

Як фіксоване, так і динамічний розподіл пам'яті мають переваги і недоліки. Компромісним в цьому плані є система двійників, в якій пам'ять розподіляється блоками розміром 2К, L <= K <= U, де: - 2L - мінімальний розмір виділяється блоку пам'яті;

- 2U - найбільший розподіляється блок (спочатку вся доступна пам'ять).

При запиті розміром S, таким, що 2U-1 <S <= 2U, виділяється весь блок. В іншому випадку блок поділяється на два рівних двійника з розмірами 2U-1. Якщо 2U-2 <S <= 2U-1, то за запитом виділяється один із двох двійників; в іншому випадку один із двійників знову ділиться навпіл. Цей процес продовжується до тих пір, поки не буде згенеровано найменший блок, розмір якого не менше S.

Система двійників постійно веде список "дірок" (доступних блоків) для кожного розміру 2i. Діра може бути вилучена зі списку (i +1) поділом її навпіл і внесенням двох нових дір розміру 2i в список i. Коли пара двійників у списку i виявляється звільненої, вони видаляються зі списку і об'єднуються в єдиний блок у списку i +1.

Нижче наведено приклад (рис. 10.6) використання блоку з початковим розмі ¬ ром 1 Мбайт. Перший запит А - на 100 Кбайт (для нього потрібно блок розміром 128 Кбайт). Для цього початковий блок ділиться на два двійника по 512 Кбайт. Перший з них ділиться на двійники розміром 256 Кбайт, і, в свою чергу, перший з вийшов при цьому поділі двійників також ділиться навпіл. Один з вийшов двійників розміром 128 Кбайт виділяється запитом А. Наступний запит В вимагає 256 Кбайт. Такий блок є в наявності і виділяється. Процес продовжується з разде ¬ ленням і злиттям двійників при необхідності. Зверніть увагу, що після звільнення блоку Е відбувається злиття двійників по 128 Кбайт в один блок розміром 256 Кбайт, який, у свою чергу, тут же зливається зі своїм двійником.

Система двійників є розумний компроміс для подолання недоліків схем фіксованого і динамічного розподілу, але в сучасних ¬ них операційних системах її перевершує віртуальна пам'ять, заснована на сторінкової організації і сегментації. Однак система двійників знайшла застосування в паралельних системах як ефективний засіб розподілу і звільнен ¬ ня паралельних програм. Модифікована версія системи двійників використовується для розподілу пам'яті ядром UNIX.

Рис. 10.6. Приклад системи двійників

Читайте також:

1. Active-HDL як сучасна система автоматизованого проектування ВІС.
2. II. Бреттон-Вудська система (створена в 1944 р.)
3. IV. Система зв’язків всередині центральної нервової системи
4. IV. УЗАГАЛЬНЕННЯ І СИСТЕМАТИЗАЦІЯ ВИВЧЕНОГО
5. V. Систематизація і узагальнення нових знань, умінь і навичок
6. VI. Система навчаючих завдань для перевірки кінцевого рівня завдань.
7. VI. Система навчаючих завдань для перевірки кінцевого рівня завдань.
8. VI. Узагальнення та систематизація знань
9. VII. Закріплення нового матеріалу і систематизація знань.
10. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
11. Автоматизована система ведення державного земельного кадастру
12. Автоматична система сигналізації

Переглядів: 887