ВСТУП
З розвитком обчислювальної техніки та в наслідок науково–технічного прогресу зростає попит на замовлення по створенню необхідного прикладного програмного забезпечення. В сучасних умовах розвитку суспільства програмне забезпечення перетворюється в товар, якщо воно відповідає певним вимогам ринку. Таке програмне забезпечення значно полегшує та спрощує обов’язки персоналу, дозволяють вчасно, швидко і якісно, надійно та без помилок і без додаткових витрат взяти на себе частину роботи та заощадити дорогоцінний час.
На сьогоднішній день існують комп’ютери з різною комплектацією, але проблема нестачі оперативної пам’яті залишається актуальною. В зв’язку з цим була введена, так звана, віртуальна пам’ять.
Віртуальна пам’ять — схема адресації пам’яті комп’ютера, при якій пам’ять для запущеної програми реалізується однорідним масивом, в той час як насправді операційна система виділяє пам’ять блоками в різних видах пам’яті, включаючи короткочасну (оперативну) і довгочасну (жорсткі диски).
Також під віртуальною пам’яттю часто розуміють файл підкачки (Windows–системи), або окремий розділ на диску (Unix–системи). Ця пам’ять використовується для того, щоб дати можливість системі або користувачу одночасно виконувати більшу кількість програм, ніж це дозволяє фізична оперативна пам’ять.
Віртуальну пам’ять підтримують процесори, що працюють у захищеному режимі, починаючи з 80286 (випущено у 1982 році), але широко стали використовувати тільки в операційних системах і оболонках для 32–розрядних процесорів (80386 і новіші, починаючи з 1985 року).
При використанні віртуальної пам’яті спрощується програмування, так як програмісту більше не потрібно враховувати обмеженість пам’яті або погоджувати використання пам’яті з іншими додатками. Для програми виглядає доступним і безперервним весь допустимий адресний простір, незалежно від наявності в ЕОМ відповідного обсягу ОЗУ.
Застосування механізму віртуальної пам’яті дозволяє:
– спростити адресацію пам’яті клієнтським програмним забезпеченням;
– раціонально управляти оперативною пам’яттю комп’ютера (зберігати в ній тільки активно використовуються області пам’яті);
– ізолювати процеси один від одного (процес вважає, що монопольно володіє всією пам’яттю).
В даний час ця технологія має апаратну підтримку на всіх сучасних побутових процесорах. У той же час у вбудованих системах і в системах спеціального призначення, де потрібно або дуже швидка робота, або є обмеження на тривалість відгуку (системи реального часу) віртуальна пам’ять використовується відносно рідко.
Метою даної кваліфікаційної роботи є проектування і створення програмного продукту за допомогою якого можна буде створювати засоби опису програми для побудови її автоматної моделі.
Для вирішення даної задачі будуть виконуватися наступні завдання: дослідження і аналізування предметної області проекту; аналіз переваг та недоліків сучасних аналогів відповідних систем; проектування та реалізація структурної та функціональної схем, алгоритм роботи модулів; розробка програмного засобу який надасть змогу створювати засоби опису програми. З метою та завданнями проекту безпосередньо пов’язані його предмет та об’єкт.
Об’єктом проекту даної кваліфікаційної роботи є процес створення засобів опису програми для побудови її автоматної моделі.
Предметом є програмний продукт, який надає змогу створювати засоби опису програми для побудови її автоматної моделі.
1 АНАЛІТИЧНА ЧАСТИНА
1.1 Віртуальна пам’ять в Windows
У Windows реалізовано систему віртуальної пам’яті, яка утворює плоский (лінійний) адресний простір. Вона створює кожному процесу ілюзію того, що в нього є власний достатньо великий і закритий від інших процесів адресний простір. Віртуальна пам’ять дає логічне представлення (звідси й назва – віртуальна, неіснуюча), яке не обов’язково відповідає (і як правило не відповідає) структурі фізичної пам’яті. У період виконання диспетчер пам’яті, використовуючи апаратну підтримку, транслює, або проектує (maps), віртуальні адреси на фізичні, за якими реально зберігаються дані. Керуючи проектуванням і захистом сторінок пам’яті, операційна система гарантує, що жоден процес не зашкодить іншому й не зможе пошкодити дані самої операційної системи. Оскільки в більшості комп’ютерів обсяг фізичної пам’яті набагато менший від загального обсягу віртуальної пам’яті, задіяної процесами, диспетчер пам’яті переміщає (підкачує) частину вмісту пам’яті на диск. Підкачування даних на диск звільняє фізичну пам’ять для інших процесів або операційної системи. Коли потік звертається до скинутої на диск сторінки віртуальної пам’яті, диспетчер пам’яті завантажує цю інформацію з диска назад у пам’ять. Для використання переваг підкачування в програмах ніякого додаткового коду не потрібно, тому що диспетчер пам’яті спирається на апаратну підтримку цього механізму.
1.2 Керування віртуальною пам’яттю
Механізм керування пам’яттю є однією з найважливіших складових операційної системи. У комп’ютерах IBM–сумісної архітектури застосунки разом з оброблюваними даними розташовуються в оперативній пам’яті. Таким чином, виконання будь–якого процесу обов’язково супроводжується операціями з пам’яттю. Для реалізації схеми керування віртуальною пам’яттю, при якій кожен процес отримує власний закритий адресний простір, використовується диспетчер віртуальної пам’яті (virtual memory manager). Диспетчер пам’яті виконує два головних завдання: узгодження адрес віртуального адресного простору з наявними фізичними ресурсами пам’яті (трансляція віртуальних адрес) та керування використанням сторінкового файлу, який дозволяє компенсувати нестачу фізичної пам’яті.
1.3 Структура віртуального адресного простору
Розмір віртуального адресного простору залежить від конкретної апаратної платформи. На 32–розрядних системах теоретичний максимум для загального віртуального адресного простору становить 4 Гб. За замовчуванням Windows виділяє нижню половину цього простору (у діапазоні адрес від х00000000 до х7FFFFFFF) процесам, а другу половину (у діапазоні адрес від х80000000 до xFFFFFFFF) використовує у власних цілях. Windows 2000 Advanced Server, Windows 2000 Datacenter Server, Windows XP (SP2 і вище) і Windows Server 2003 підтримують завантажуванні параметри /3GB і /USERVA, які вказують у файлі Boot.ini та дозволяють процесам, що виконують програми зі спеціальним прапорцем у заголовку образу, використовувати до 3 Гб закритого адресного простору й залишає операційній системі тільки 1 Гб. Цей варіант дає можливість вимогливій до пам’яті програмі зберігати в адресному просторі свого процесу великі порції даних і тим самим зменшити частоту дискових звертань.
Кожному процесу виділяється власний віртуальний адресний простір. Для 32–розрядних процесів його розмір становить 4 Гб (це максимальний обсяг, який може використовуватися при 32–бітній адресації – 232). Для 64–розрядних процесів розмір адресного простору становить 16 екзабайт (264 байт). Потоки при виконанні отримують доступ тільки до пам’яті, яка належить його процесу. Пам’ять, відведена іншим процесам, прихована від потоку й недоступна для використання. Тому дані різних процесів, записані за тією ж віртуальною адресою, розміщуються в різних сторінках фізичної пам’яті (це забезпечує система трансляції адрес). У ряді випадків ізоляція може бути частково знята (наприклад, для відображених файлів). У подібних випадках забезпечують контроль доступу до області пам’яті, для чого створюють окремий об’єкт, який містить атрибути захисту. 4 Гб адресного простору система ділить на дві приблизно однакові за обсягом частини. Перша частина надається у користування процесу, а друга резервується для системних потреб. Таким чином, за замовчуванням кожен користувацький процес в 32–розрядній версії Windows має у своєму розпорядженні власний адресний простір розміром до 2 Гб; інші 2 Гб використовує операційна система. У системному просторі розміщуються такі компоненти:
– Системний код. Містить образ операційної системи, HAL і драйвери пристроїв, які використовуються для завантаження системи. Сюди ж проектується частина підсистеми Windows режиму ядра, а також графічні драйвери.
– Гіперпростір. Особлива область, яка використовується для проектування на пам’ять списку робочого набору процесу й тимчасового проектування інших фізичних сторінок для ряду системних операцій.
– Структури даних списку робочого набору, які описують системний робочий набір.
– Системний кеш. Віртуальний адресний простір, який використовується для проектування файлів.
– Системна купа відкачуваної пам’яті.
– Елементи системної таблиці сторінок. Це елементи в таблиці сторінок, що містять фізичну адресу, на яку проектується віртуальна.
– Системна купа непідкачуваної пам’яті.
– Дані аварійного дампу. Область, зарезервована для запису інформації про стан системи на момент краху.
– Область, зарезервована під специфічні для HAL структури.
1.4 Віртуальний адресний простір 32–бітних систем
Віртуальний адресний простір кожного процесу розбивається на розділи, розмір і призначення яких залежать від версії Windows. Розділ для виявлення нульових вказівників резервується, щоб полегшити розробникам програмного забезпечення виявляти нульові вказівники. Спроба читання або запису за цими адресами викликає порушення доступу. Якщо в програмі відсутня належна обробка помилок, то при невдалій спробі виділення пам’яті за вказівником він може мати нульове значення. Тоді спроба звертання до даних за таким вказівником (тобто за адресою $00000000) буде явно помилковою. Оскільки цей розділ адресного простору заблокований, виникне виняткова ситуація некоректного доступу до пам’яті. Ця особливість допомагає програмістам виявляти помилки у програмах.
Розділ для коду й даних є закритою частиною адресного простору процесу.
Основний обсяг даних, що належать процесу, зберігається саме тут. Сюди завантажуються всі виконавчі модулі, враховуючи й динамічні бібліотеки. На цей же розділ відображуються проектовані файли, доступні даному процесу.
Структура віртуального адресного простору в 32–бітних системах зображена на рис. 1.1.
Рис. 1.1 – Структура віртуального адресного простору в 32–бітних системах
1.5 Сторінковий файл
У старих операційних системах фізичною пам’яттю вважалася лише оперативна пам’ять (RAM). Сучасні ОС імітують пам’ять за рахунок дискового простору. При цьому на диску створюється сторінковий файл (paging file), який містить доступну для всіх процесів віртуальну пам’ять. З погляду прикладної програми, сторінковий файл просто збільшує обсяг доступної пам’яті. Під час роботи операційна система скидає вміст частини оперативної пам’яті в сторінковий файл і при необхідності довантажує його порціями назад у пам’ять. Якщо такого файлу немає, система працюватиме, але застосункам буде доступний менший обсяг пам’яті. Сторінковий файл збільшує обсяг доступної пам’яті і дозволяє програмам працювати з більшими обсягами даних. Фізична пам’ять ділиться на сторінки, кожна з яких може мати окремі атрибути захисту.
1.6 Апаратна підтримка
Апаратна підтримка здійснюється за допомогою компонента Memory Management Unit(Блок управління пам’яттю, MMU) – це компонент апаратного забезпечення комп’ютера, що відповідає за управління доступом до пам’яті, запитуваною центральним процесором. Його функції полягають у трансляції адрес віртуальної пам’яті в адреси фізичної пам’яті (тобто управління віртуальною пам’яттю), захисту пам’яті, управлінні кеш–пам’яттю, арбітражем шини і, в більш простих комп’ютерних архітектурах (особливо 8–бітних), перемиканням блоків пам’яті. Іноді також згадується як блок управління сторінкової пам’яттю.
Принцип роботи сучасних MMU заснований на поділі віртуального адресного простору (одновимірного масиву адрес, використовуваних центральним процесором) на ділянки однакового, як правило кілька кілобайт, хоча, можливо, й істотно більшого, розміру рівного ступеня 2, звані сторінками. Молодші n біт адреси (зміщення всередині сторінки) залишаються незмінними. Старші біти адреси являють собою номер (віртуальної) сторінки. MMU зазвичай перетворює номера віртуальних сторінок в номери фізичних сторінок використовуючи буфер асоціативної трансляції (англ. Translation Lookaside Buffer, TLB). Якщо перетворення за допомогою TLB неможливо, включається більш повільний механізм перетворення, заснований на специфічному апаратному забезпеченні або на програмних системних структурах. Дані в цих структурах як правило називаються елементами таблиці сторінок (англ. Page table entries, PTE), а самі структури – таблицями сторінок (англ. Page table, PT). Конкатенація номера фізичної сторінки зі зміщенням всередині сторінки дає фізичну адресу.
Елементи PTE або TLB можуть також містити додаткову інформацію: біт ознаки записи в сторінку (англ. Dirty bit), час останнього доступу до сторінки (англ. Accessed bit, для реалізації алгоритму заміщення сторінок найбільш давно використаний (англ. Least recently used, LRU), які процеси (користувальницькі (англ. user mode) або системні (англ. supervisor mode)) можуть читати або записувати дані в сторінку, чи необхідно кешувати сторінку.
1.7 Сегментна організація пам’яті в реальному режимі роботи мікро процесорів x86
Для мікропроцесорів x86 в реальному режимі роботи зсув є одночасно ефективною адресою. Ефективні адреси формуються в Intel–сумісних мікропроцесорах за допомогою регістрів даних, “Системні регістри центрального процесора”. Ефективна адреса формується таким чином.: до восьми або шістнадцяти розрядного зміщення в програмі додається 16–ти розрядний вміст базового регістра і 16–ти розрядний вміст індексного регістра. Розрядність зміщення повинна відповідати розрядності регістру, куди пересилаються дані. Зазвичай в базовому регістрі міститься початкова адреса блоку видобутих даних, а в індексному регістрі – довжина витягуваного запису, помножена на порядковий номер (від 0 до N–1) запису.
Система команд в мікропроцесорах x86 влаштована так, що для утворення ефективної адреси необхідно обов’язкову присутність тільки одного його компонента. Таким чином будь–який компонент: база, індекс, зсув, або навіть обидва з них можуть бути опущені.
1.8 Базові адреси та формування лінійних адрес
Базові адреси містяться в сегментних регістрах мікропроцесорів i8086 / 88 і в регістрах селекторів сегментів в мікропроцесорах x86. Ці регістри шістнадцяти розрядні. Однак утворена в результаті складання базової та ефективної адреси, лінійна адреса є 20–ти розрядною.
Таким чином максимальна лінійна адреса має розмір 1,062 Мбайт (тобто на 64 Кбайт більше, ніж адресний простір в 1 Мбайт). Тому в мікропроцесорах i8086/88 відбувається “загортання” адреси навколо кордону сегмента. Тобто фізична адреса Буде мати значення 0FFEFh. У мікропроцесорі i80286, в резульат помилки розробників, такого загортання немає. У мікропроцесорах i80386 і вище це “загортання” можна включити, а можна і вимкнути, Для включення “загортання” необхідне апаратне блокування лінії A20 (A20 = 0) за допомогою порту контролера клавіатури. Його станом можна управляти програмно.
1.9 Сегментація пам’яті в захищеному режимі
У захищеному режимі роботи мікропроцесорів x86 забезпечується кращий захист операційної системи від несанкціонованого доступу програм користувача. Це відбувається шляхом ускладнення формування лінійної адреси в мікропроцесорах i80386 і вище. Наприклад, сегмент не може бути використаний ніякою програмою, якщо він не “представлений” їй відповідним чином. Програма вже не може звертатися за будь–якою адресою, який вона може сформувати. При “поданні” сегмента програмі вона повинна запросити не тільки базову адресу сегмента, а й рівень привілеїв, локалізацію сегмента, його довжину і роздільну здатність, права доступу до сегмента (читання, запис і виконання) і деякі інші параметри.
При цьому у системного програміста є більше можливостей з управління сегментацією пам’яті. Так, уже в мікропроцесорі i80386 зняті обмеження на розмір сегмента. Він може мати значення від 1 байта до 4 Гбайт. У ньому також зняті обмеження на розташування кордону сегмента. Кордон сегмента більше не прив’язано до кордону параграфа, та й саме поняття “параграф” до захищеного режиму роботи мікропроцесора не застосовується. Програміст в описі сегмента сам визначає рівні привілеїв і тип використовуваного сегмента.
Рівні привілеїв призначаються програмами з метою не допустити руйнування системних областей некоректними діями прикладних програм. Деякі команди виконуються тільки на нульовому (самому верхньому) рівні привілеїв. Виконання інших команд залежить від того, які рівні привілеїв встановлені в регістрів прапорів і при описі сегмента. У будь–якому випадку діють наступні правила виклику сегментів і між сегментних переходів:
1. Можливий перехід від сегмента до сегмента, що мають один і той же рівень привілеїв.
2. Можливе звернення до сегменту даних, що має той же або більш низький рівень привілеїв, ніж сегмент коду.
3. Якщо необхідно перейти до сегменту коду, що має більш високий рівень привілеїв, необхідно використовувати вентиль.
1.10 Функції системи управління пам’яттю
Щоб забезпечити ефективний контроль використання пам’яті, ОС повинна виконувати наступні функції:
– відображення адресного простору процесу на конкретні галузі фізичної пам’яті;
– розподіл пам’яті між конкуруючими процесами;
– контроль доступу до адресних просторів процесів;
– вивантаження процесів (цілком або частково) в зовнішню пам’ять, коли в оперативній пам’яті недостатньо місця;
– облік вільної та використаної пам’яті.
Кожна схема включає в себе певну ідеологію управління, а також алгоритми і структури даних і залежить від архітектурних особливостей використовуваної системи.
1.10.1 Найпростіші схеми управління пам’яттю
Перші ОС застосовували дуже прості методи управління пам’яттю. Спочатку кожен процес користувача повинен був повністю поміститися в основній пам’яті, займати безперервну область пам’яті, а система брала до обслуговування додаткові користувацькі процеси до тих пір, поки всі вони одночасно поміщалися в основній пам’яті. Потім з’явився "простий свопінг" (система як і раніше розміщує кожен процес в основний пам’яті цілком, але іноді на підставі деякого критерію цілком скидає образ деякого процесу з основної пам’яті в зовнішню і замінює його в основної пам’яті чином іншого процесу). Такого роду схеми мають не лише історичну цінність. В даний час вони застосовуються в навчальних і науково–дослідних модельних ОС, а також в ОС для вбудованих (embedded) комп’ютерів.
1.10.2 Схема з фіксованими розділами
Найпростішим способом управління оперативною пам’яттю є її попереднє (зазвичай на етапі генерації або в момент завантаження системи) розбиття на кілька розділів фіксованої величини. Процеси що поступають поміщаються в той чи інший розділ. При цьому відбувається умовне розбиття фізичного адресного простору. Зв’язування логічних і фізичних адрес процесу відбувається на етапі його завантаження в конкретний розділ, іноді – на етапі компіляції.
Кожен розділ може мати свою чергу процесів, а може існувати і глобальна черга для всіх розділів(рис. 1.2.).
Ця схема була реалізована в IBM OS / 360 (MFT), DEC RSX–11 і ряді інших систем.
Підсистема управління пам’яттю оцінює розмір надійшовшого процесу, вибирає підходящий для нього розділ, здійснює завантаження процесу в цей розділ і налаштування адресу.
Рис. 1.2 – Схема з фіксованими розділами
Очевидним недоліком цієї схеми – число одночасно виконуваних процесів обмежено числом розділів.
Іншим істотним недоліком є те, що пропонована схема сильно страждає від внутрішньої фрагментації – втрати частини пам’яті, виділеної процесу, але не використовуваної ним. Фрагментація виникає тому, що процес не повністю займає виділений йому розділ або тому, що деякі розділи занадто малі для виконуваних програм користувача.
1.10.3 Один процес в пам’яті
Окремий випадок схеми з фіксованими розділами – робота менеджера пам’яті однозадачної ОС. У пам’яті розміщується один користувальницький процес. Залишається визначити, де розташовується користувача програма по відношенню до ОС – у верхній частині пам’яті, в нижній або у середній. Причому частина ОС може бути в ROM (наприклад, BIOS, драйвери пристроїв). Головний фактор, що впливає на це рішення, – розташування вектора переривань, який зазвичай локалізована в нижній частині пам’яті, тому ОС також розміщують у нижній. Прикладом такої організації може служити ОС MS–DOS.
Захист адресного простору ОС від користувача програми може бути організовано за допомогою одного граничного регістра, що містить адресу кордону ОС.
1.10.4 Оверлейна структура
Так як розмір логічного адресного простору процесу може бути більше, ніж розмір виділеного йому розділу (або більше, ніж розмір самого великого розділу), іноді використовується техніка, звана оверлей (overlay) або організація структури з перекриттям (рис. 1.3). Основна ідея – тримати в пам’яті тільки ті інструкції програми, які потрібні в даний момент.
Потреба в такому способі завантаження з’являється, якщо логічний адресний простір системи малий, наприклад 1 Мбайт (MS–DOS) або навіть всього 64 Кбайта (PDP–11), а програма відносно велика. На сучасних 32–розрядних системах, де віртуальний адресний простір вимірюється гігабайтами, проблеми з нестачею пам’яті вирішуються іншими способами.
Рис. 1.3 – Організація структури з перекриттям. Можна по черзі завантажувати в пам’ять гілки A–B, A–C–D і A–C–E програми
Коди гілок оверлейной структури програми знаходяться на диску як абсолютні образи пам’яті і зчитуються драйвером оверлеїв при необхідності. Для опису оверлейной структури зазвичай використовується спеціальна нескладний мова (overlay description language). Сукупність файлів виконуваної програми доповнюється файлом (зазвичай з розширенням.odl), що описує дерево викликів всередині програми.
Оверлеї можуть бути повністю реалізовані на рівні користувача в системах з простою файлової структурою. ОС при цьому лише робить дещо більше операцій введення–виведення. Типове рішення – породження лінкером спеціальних команд, які включають завантажувач кожен раз, коли потрібно звернення до однієї з гілок програми що перекриваються.
Ретельне проектування оверлейної структури забирає багато часу і вимагає знання устрою програми, її коду, даних і мови опису оверлейної структури. З цієї причини застосування оверлеїв обмежено комп’ютерами з невеликим логічним адресним простором. Проблема оверлейних сегментів, контрольованих програмістом, відпадає завдяки появі систем віртуальної пам’яті.
Зауважимо, що можливість організації структур з перекриттями багато в чому зумовлена властивістю локальності, що дозволяє зберігати в пам’яті тільки ту інформацію, яка необхідна в конкретний момент обчислень.
1.10.5 Стопінг
Свопінг, або підкачка сторінок — один з механізмів віртуальної пам’яті, при якому окремі фрагменти пам’яті (зазвичай неактивні) переміщуються з ОЗП на жорсткий диск, звільняючи оперативну пам’ять для завантаження інших фрагментів пам’яті. Такими фрагментами в сучасних ЕОМ є сторінки пам’яті.
Тимчасово вивантажені з пам’яті сторінки можуть зберігатися на зовнішніх запам’ятовуючих пристроях як у файлі, так і в спеціальному розділі на жорсткому диску, звані відповідно swap–файл і swap–розділ. У разі відкачування сторінок, що відповідають вмісту будь–якого файлу вони можуть вилучатися. При запиті такої сторінки вона може бути прочитана з оригінального файлу.
Коли програма звернеться до відкачаної сторінки, відбудеться виняткова ситуація PageFault. Оброблювач цієї події повинен перевірити, чи була раніше відновлено запитана сторінка, і, якщо вона є в свопі, завантажити її назад в пам’ять.
Так як при використані свопінгу частина даних зберігається в енергонезалежній пам’яті, і відповідно не стирається, зловмисники можуть скористатися цим, проаналізувавши swap–файл і витягнути з нього цінну інформацію, наприклад паролі. Тому слід або відмовитись від свопінгу взагалі, або повністю шифрувати розділ жорсткого диску де зберігається swap–файл.
1.10.6 Схема зі змінними розділами
В принципі, система свопінгу може базуватися на фіксованих розділах. Більш ефективною, однак, видається схема динамічного розподілу або схема зі змінними розділами, яка може використовуватися і в тих випадках, коли всі процеси цілком містяться в пам’яті, тобто за відсутності свопінгу. У цьому випадку спочатку вся пам’ять вільна і не розділена заздалегідь на розділи. Знову надходить задачі виділяється строго необхідна кількість пам’яті, не більше. Після вивантаження процесу пам’ять тимчасово звільняється. Після закінчення деякого часу пам’ять – змінне число розділів різного розміру (рис. 1.4). Суміжні вільні ділянки можуть бути об’єднані.
Рис. 1.4 – Динаміка розподілу пам’яті між процесами (сірим кольором показана невживана пам’ять)
В який розділ поміщати процес? Найбільш поширені три стратегії.
– Стратегія першого підходящого (First fit). Процес поміщається в перший відповідний за розміром розділ.
– Стратегія найбільш підходящого (Best fit). Процес поміщається в той розділ, де після його завантаження залишиться менше всього вільного місця.
– Стратегія найменш придатного (Worst fit). При приміщенні в найбільший розділ в ньому залишається достатньо місця для можливого розміщення ще одного процесу.
Моделювання показало, що частина корисно використовуваної пам’яті в перших двох випадках більше, при цьому перший спосіб трохи швидше. Зауважимо, що перераховані стратегії широко застосовуються і іншими компонентами ОС, наприклад для розміщення файлів на диску.
Типовий цикл роботи менеджера пам’яті полягає в аналізі запиту на виділення вільної ділянки (розділу), виборі його серед наявних відповідно до однієї із стратегій (першого підходящого, найбільш відповідного і найменш придатного), завантаженні процесу у вибраний розділ і наступних змінах таблиць вільних і зайнятих областей. Аналогічна коригування необхідна і після завершення процесу. Зв’язування адрес може здійснюватися на етапах завантаження і виконання.
Цей метод більш гнучкий в порівнянні з методом фіксованих розділів, проте йому притаманна зовнішня фрагментація – наявність великої кількості ділянок невживаної пам’яті, не виділеної ні одному процесу. Вибір стратегії розміщення процесу між першим підходящим і найбільш підходящим слабо впливає на величину фрагментації. Цікаво, що метод найбільш підходящого може виявитися найгіршим, оскільки він залишає безліч дрібних незайнятих блоків.
Статистичний аналіз показує, що припадають в середньому 1/3 пам’яті! Це відоме правило 50% (дві сусідніх вільних ділянки на відміну від двох сусідніх процесів можуть бути об’єднані).
Одне з рішень проблеми зовнішньої фрагментації – організувати стиск, тобто переміщення всіх зайнятих (вільних) ділянок у бік зростання (спадання) адрес, так, щоб вся вільна пам’ять утворила безперервну область. Цей метод іноді називають схемою з переміщуваними розділами. В ідеалі фрагментація після стиснення має бути відсутня. Стиснення, однак, є дорогою процедурою, алгоритм вибору оптимальної стратегії стиснення дуже важкий і, як правило, стиснення здійснюється в комбінації з вивантаженням і завантаженням за іншими адресами.
1.10.7 Сторінкова пам’ять
Описані вище схеми недостатньо ефективно використовують пам’ять, тому в сучасних схемах управління пам’яттю не прийнято розміщувати процес в оперативній пам’яті одним безперервним блоком.
У найпростішому і найбільш поширеному випадку сторінкової організації пам’яті (або paging) як логічний адресний простір, так і фізичний представляються набором блоків або сторінок однакового розміру. При цьому утворюються логічні сторінки (page), а відповідні одиниці у фізичній пам’яті називають фізичними сторінками або сторінковими кадрами (page frames). Сторінки (і сторінкові кадри) мають фіксовану довжину, зазвичай є ступенем числа 2, і не можуть перекриватися. Кожен кадр містить одну сторінку даних. При такій організації зовнішня фрагментація відсутня, а втрати через внутрішню фрагментації, оскільки процес займає ціле число сторінок, обмежені частиною останньої сторінки процесу.
Логічна адреса в сторінкової системі – упорядкована пара (p, d), де p – номер сторінки у віртуальній пам’яті, а d – зміщення в рамках сторінки p, на якій розміщуються адресовані елементи. Зауважимо, що розбиття адресного простору на сторінки здійснюється обчислювальною системою непомітно для програміста. Тому адреса є двовимірна лише з точки зору операційної системи, а з точки зору програміста адресний простір процесу залишається лінійним.
Описувана схема дозволяє завантажити процес, навіть якщо немає безперервної області кадрів, достатньою для розміщення процесу цілком. Але одного базового регістра для здійснення трансляції адреси в даній схемі недостатньо. Система відображення логічних адрес у фізичні зводиться до системи відображення логічних сторінок у фізичні і являє собою таблицю сторінок, яка зберігається в оперативній пам’яті. Іноді кажуть, що таблиця сторінок – це кусково–лінійна функція відображення, задана в табличному вигляді.
Дата добавления: 2015-09-30; просмотров: 23 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |