Основним недоліком такого способу розподілу пам'яті є наявність часом досить великого обсягу невикористаної пам'яті (див. мал.2). Невикористана пам'ять може бути в кожному з розділів. Оскільки розділів декілька, то і невикористаних областей виходить мало, тому такі втрати стали називати фрагментацією пам'яті. В окремих розділах утрати пам'яті можуть бути дуже значними, однак використовувати фрагменти вільної пам'яті при такому способі розподілу не представляється можливим.

Бажання розроблювачів скоротити ці значні втрати привело їх до двох рішень:

а) виділяти розділ рівно такого обсягу, що потрібний під поточну задачу;

б) розміщати задачу не в одній безперервній області пам'яті, а в декількох областях.

Розділи з рухливими границями

Щоб позбутися фрагментації, можна спробувати розміщати в оперативній пам'яті задачі щільно, одну за іншою, виділяючи рівно стільки пам'яті, скільки задача вимагає. Спеціальний планувальник (диспетчер пам'яті) веде список адрес вільної оперативної пам'яті. З появою нової задачі диспетчер пам'яті переглядає цей список і виділяє для задачі розділ одним із трьох способів:

перша придатна ділянка;

найбільш придатна ділянка;

найбілш невідповідна ділянка.

У першому випадку список вільних областей упорядковується по адресах (наприклад, по зростанню адрес). Диспетчер пам'яті переглядає цей список і виділяє задачі розділ у тій області, що перша підійде по обсягу.

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

Найефективнішим правилом є останнє, по якому для нового розділу виділяється «найбілш невідповідний» фрагмент вільної пам'яті. Для цієї дисципліни список вільних областей впорядковується по зменшенню обсягу вільного фрагмента, і оскільки цей фрагмент є найбільшим, то, швидше за все, після виділення з нього розділу пам'яті для задачі, область, що залишилася, ще зможе бути використана в подальшому.

5. Дисципліни заміщення сегментів. Організація, переваги і недоліки

Сегментний спосіб організації віртуальної пам'яті

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

Логічно звертання до елементів програми в цьому випадку буде представлятися як вказівка імені сегмента і зсуву відносно початку цього сегменту. Фізично ім'я (або порядковий номер) сегменту буде відповідати деякій адресі, з якого цей сегмент починається при його розміщенні в пам'яті, і зсув повинний додаватися до цієї базової адреси.

Кожен сегмент, розташований у пам'яті, має відповідну інформаційну структуру, часто називану дескриптором сегмента. Саме операційна система будує для кожного процесу, що виконується, відповідну таблицю дескрипторів сегментів і при розміщенні кожного з сегментів в оперативній чи зовнішній пам'яті в дескрипторі відзначає його поточне місцезнаходження.

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

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

Для рішення проблеми заміщення (визначення того сегмента, який повинний бути або переміщений у зовнішню пам'ять, або просто заміщений новим) використовуються наступні дисципліни (їх наз. дисциплінами заміщення):

правило FIFO (first in -- first out: «перший прийшов першим і вибуває»);

правило LRU (1еаst recently used: «довше всього невикористовуваний»);

правило LFU (1еаst frequently used: «використовуваний рідше всіх інших»);

випадковий (random) вибір сегмента.

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

Алгоритм FIFO асоціює з кожним сегментом час, коли він був поміщений у пам'ять. Для заміщення вибирається найбільш старший сегмент.

Для реалізації дисциплін LRU і LFU необхідно, щоб процесор мав додаткові апаратні засоби. Мінімальні вимоги -- складання списку, упорядкованого або по тривалості не використання (для дисципліни LRU), або по частоті використання (для дисципліни LFU).

Сторінковий спосіб організації віртуальної пам'яті

При такому способі усі фрагменти програми, на які вона розбивається (за винятком останньої її частини), виходять однаковими. Ці однакові частини називають сторінками і говорять, що пам'ять розбивається на фізичні сторінки, а програма -- на віртуальні сторінки. Частина віртуальних сторінок задачі розміщається в оперативній пам'яті, а частина -- у зовнішній. Місце в зовнішній пам'яті називають файлом підкачки або сторінковим файлом (swap-файлом), тим самим підкреслюючи, що записи цього файлу -- сторінки -- заміщають один одного в оперативній пам'яті.

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

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

При звертанні до віртуальної сторінки, якої не має в даний момент у оперативної пам'яті, виникає переривання і керування передається диспетчеру пам'яті, що повинний знайти вільне місце. Звичайно надається перша вільна сторінка. Якщо вільної фізичної сторінки немає, то диспетчер пам'яті по одній з вищезгаданих дисциплін заміщення (LRU, LFU, FIFO, random) визначить сторінку, що підлягає розформуванню або збереженню в зовнішній пам'яті.

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

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

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

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

Для того щоб уникнути другого недоліку, зберігши достоїнства сторінкового способу організації пам'яті, було запропоновано ще один спосіб - сегментно-сторінковий.

Сегментно-сторінковий спосіб організації віртуальної пам'яті

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

Цей спосіб організації віртуальної пам'яті вносить ще більшу затримку доступу до пам'яті. Необхідно спочатку обчислити адресу дескриптору сегмента і прочитати його, потім обчислити адресу елементу таблиці сторінок цього сегменту і витягти з пам'яті необхідний елемент, і вже тільки після цього можна до номера фізичної сторінки приписати номер комірки в сторінці (індекс). Затримка доступу до шуканої комірки виходить принаймні в три рази більше, ніж при простій прямій адресації.

Щоб уникнути цієї неприємності, вводиться кешування, причому кеш, як правило, будується по асоціативному принципі.

6. Транслятори, компілятори й інтерпретатори -- загальна схема роботи

Визначення транслятора, компілятора, інтерпретатора

Транслятор - це програма, що переводить вхідну програму на вихідній (вхідній) мові в еквівалентну їй вихідну програму на результуючій (вихідній) мові.

Компілятор -- це транслятор, що здійснює переклад вихідної програми в еквівалентну їй об'єктну програму мовою машинних команд або мовою ассемблера.

Таким чином, компілятор відрізняється від транслятора лише тим, що його результуюча програма завжди повинна бути написана мовою машинних кодів чи мовою ассемблера. Результуюча програма транслятора, у загальному випадку, може бути написана на будь-якій мові. Відповідно, усякий компілятор є транслятором, але не навпаки -- не всякий транслятор буде компілятором.

Необхідність компіляторів з'явилася одночасно з появою мов програмування високого рівня.

Інтерпретатор -- це програма, що сприймає вхідну програму вихідною мовою і виконує її.

Інтерпретатор, так само як і транслятор, аналізує текст вихідної програми. Однак він не породжує результуючої програми, а відразу ж виконує вихідну відповідно до її змісту, заданим семантикою вхідної мови.

Етапи трансляції. Загальна схема роботи транслятора

Рис. 1. Загальна схема роботи компілятора

На мал.1 представлена загальна схема роботи компілятора. З неї видно, що в цілому процес компіляції складається з двох основних етапів -- синтезу й аналізу.

На етапі аналізу виконується розпізнавання тексту вихідної програми, створення і заповнення таблиць ідентифікаторів. Результатом його роботи служить деяке внутрішнє представлення програми, зрозуміле компілятору.

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

7. Призначення й особливості побудови таблиць ідентифікаторів

Призначення й особливості побудови таблиць ідентифікаторів

Компілятор повинний мати можливість зберігати всі знайдені ідентифікатори і зв'язані з ними характеристики на протязі всього процесу компіляції, щоб мати можливість використовувати їх на різних фазах компіляції.

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

Будь-яка таблиця ідентифікаторів складається з набору полів, кількість яких дорівнює числу різних ідентифікаторів, знайдених у вхідній програмі. Кожне поле містить у собі повну інформацію про даний елемент таблиці. Компілятор може працювати з однією або декількома таблицям ідентифікаторів -- їхня кількість залежить від реалізації компілятора.

У таблицях ідентифікаторів може зберігатися наступна інформація:

для змінних:

ім'я змінної;

тип даних змінною;

область пам'яті, зв'язана із змінною;

для констант:

назва константи (якщо воно є);

значення константи;

тип даних константи (якщо потрібно);

для функцій:

ім'я функції;

Страницы: 1, 2, 3, 4, 5