. СКЛАД АЛГОРИТМІВ ВНУТРІШНЬОГО ПЛАНУВАННЯ Найважливішим фактором що впливає на ефективність обчислюваль
Работа добавлена на сайт samzan.net:
1. СКЛАД АЛГОРИТМІВ ВНУТРІШНЬОГО ПЛАНУВАННЯ
Найважливішим фактором, що впливає на ефективність обчислювальних систем, є втрати часу на організа-
цію мультизадачного режиму, тому до складу алгоритмів внутрішнього планування входять:
- Алгоритм управління кількістю процесів в робочій суміші;
- Алгоритм планування черговості вибору завдань для виконання їх на ЦП;
- Алгоритми вибору величини кванта часу, протягом якого процес, який отримав ЦП, може використовувати його.
Особливою функцією, покладеної на внутрішнє планування, є синхронізація паралельних процесів, проте-
кающих в системі.
АЛГОРИТМ УПРАВЛІННЯ КІЛЬКІСТЮ ПРОЦЕСІВ В РОБОЧОЇ СУМІШІ
Управління служить для підвищення продуктивності системи на основі раціонального використання апаратури
ЕОМ. Для режиму витісняючою мультизадачности кількість процесів, одночасно допускаються в систему, являє
собою обсяг робочої суміші N. Вибір значення N здійснюється з урахуванням величини кванта і тривалості циклу. Введемо сле-
дмуть позначення: qi - величина кванта процесорного часу, що відводиться i-м процесом; Ti - тривалість одного циклу
обробки для i-го процесу; Tз i, Tв i - тривалість переміщення i-го процесу з ОЗУ в ВЗП і назад при його витісненні і
відновленні; Tc i - витрати часу ОС на організацію роботи i-го процесу.
Тоді маємо: Тц i = Тз i + Tв i + qi + Tc i ,
Если Tз i = Tв i = Tп ; Tc i = Tc ; qi = q, i = 1, ..., N, то T = (2Tп + q + Tc) N; N = T / (2Tп + q + Tc )
Неважко розрахувати також ефективність завантаження центрального процесора на одному циклі для одного процесу: величина кванта час процесора - qi; непродуктивні витрати часу - Тн i = Тз i + Tп i + Tc i; показник завантаження процесора корисною роботою роботою
Збільшення кількості завдань, одночасно розв'язуваних системою, пов'язане зі збільшенням значення N
можна здійснити чотирма методами: 1)збільшенням загальної тривалості інтервалу циклу Т; 2)зменшенням витрат часу ОС на організацію мультипрограммирования Тс;3) зменшенням витрат часу на переміщення процесів з ОЗУ в ВЗП і назад при їх витіснення і відновленні Тз і Тв; 4)скороченням тривалості квантів часу, що відводяться для виконання процесів q.
Скорочення тривалості квантів часу qi, що відводяться для виконання процесів, автоматично викликає збіль-
чення тривалості перебування процесів у системі, через що цей спосіб має обмежене присування.
Найбільш продуктивними є методи, що призводять до скорочення витрат часу операційної системи Тс і, в
особливості, витрат часу на переміщення процесів з ОЗУ в ВЗП і назад при їх витіснення і відновленні.
Зменшення значення Тс досягається шляхом створення ефективних системних програм, що мають найменшу довжину програмного коду і найвищу швидкість виконання своїх функцій. У сучасних обчислювальних системах застосовуються всі перераховані способи збільшення ефективності обработки завдань.
АЛГОРИТМИ вибору чергової ОБРОБКИ
Планування черговості обробки здійснюється на основі черги процесів, що знаходяться в стані готовності.Всі ці процеси в мультипрограмних системах конкурують між собою, перш за все, через час центрального
процесора. Протягом кванта часу, виділеного процесу, можливе настання одного або декількох подій: ви-
конання процесу завершено; процес перейшов у стан очікування; центральний процесор знадобився для обслуговування процесу з вищим пріоритетом; завершився виділений процесу квант часу; сталася помилка в системі.
Рішення про порядок вибору процесів з черги здійснюється відповідно до реалізованими в ОС алгоритмами
планування черговості обробки. В даний час найбільш відомими є:
• алгоритм циклічної обробки;
• алгоритм черг зі зворотним зв'язком;
• алгоритм вибору за характером використання попереднього кванта;
• алгоритм вибору з пріоритетом за характером блокування.
Практично всі алгоритми планування черговості обробки мають евристичний характер. Сигналом до початку
роботи цих алгоритмів служать зазначені вище події, що настали у системі:
• якщо попередній процес закінчився, то виконуються дії по його виведення з системи:
• якщо попередній процес перейшов у стан очікування, то він переміщається в чергу блокованих процесів;
• якщо попередній процес перерваний операційною системою через те, що ЦП знадобився для обслуговування іншого процесу з вищим пріоритетом, то перерваний процес міститься в чергу перерваних процесів;
• якщо попередній процес вичерпав виділений йому квант часу, то він надходить в чергу готових процесів;
• якщо алгоритм планування активізований через якого іншого події, то виконуються дії згідно реакції на помилкову ситуацію, що виникла в системі.
Логіка роботи всіх алгоритмів планування черговості обробки практично збігається. Розрізняються вони лише
реалізаціями блоків "Вибір довжини кванта" і "Вибір чергового процесу".
Розглянемо алгоритми реалізації блоку "вибір чергового процесу".
Алгоритм циклічної обробки процесів не використовує жодної інформації про пріоритети оброблюваних
процесів. Всі процеси, що знаходяться в черзі, упорядковуються за часом їх надходження. Що стоїть першим у черзі процес отримує квант часу q центрального процесора. Існує багато різновидів алгоритмів циклічної
обробки, які називають також алгоритмами кругообігу процесів, наприклад, кругообіг зі зміщенням і егоїстичний кругообіг.
Алгоритм черг зі зворотним зв'язком організовує деяку кількість М черг, кожна з яких обслуговується в порядку надходження. Новий процес, що надійшов в систему, потрапляє в чергу № 1. Після закінчення використання чергового кванта часу процес переходить з черги з номером m в чергу з номером m + 1.
Алгоритм вибору за характером використання попереднього кванта розрізняє два типи стану готовності процесів : низькопріоритетною і високопріоритетною готовністю.
Якщо процес повністю використав попередній виділений квант часу ЦП, то йому присвоюється стан
"Низькопріоритетна готовність". Якщо процес використав не весь виділений квант часу ЦП через перехід у стання очікування, то йому присвоюється стан "високопріоритетна готовність". На обслуговування спочатку вибираються процеси, що знаходяться в стані високопріоритетної готовності, а потім, якщо їх немає, процеси, які знаходь. в стані "низькопріоритетної готовності"
АЛГОРИТМИ ВИБОРУ ВЕЛИЧИНИ КВАНТА
Вибір величини кванта є принципово необхідним у режимі поділу часу. Процедура квантування
виконується щоразу, коли ОС вибирає процес з робочої суміші і активізує його. В даний час найбільш
поширеними є:
- Алгоритм рівномірного квантування;
- Алгоритм квантування по пріоритету процесу;
- Алгоритм мінімізації кількості перемикань між процесами.
Алгоритм рівномірного квантування - найпростіший із згаданих вище алгоритмів. Відповідно до цього алго-
ритму кожному процесу, що знаходиться в робочій суміші, виділяється квант часу, тривалість якого може вимірюватися на відрізку часу існування процесу в системі. Тривалості квантів часу всіх процесів рівні між
собою. Алгоритм квантування по пріоритету процесу здійснює регулювання тривалості кванта qi для i-го про-
цесу залежно від його поточного пріоритету pi. Функціональна залежність qi = qi (pi) може мати будь допустимий вид і повинна мати такі основні характеристики: монотонність, позитивна визначеність, обмеженість. Алгоритм квантування з мінімізацією кількості перемикань полягає в тому, що активізується процес займає не тільки свій квант, але і залишки квантів процесів, які перейшли до цього моменту часу в стан сподіваня.
2. Засоби управління ресурсами
Під управлінням ресурсами в ОС розуміється розподіл ресурсів системи між різними завданнями і процессами, одночасно функціонуючими в ній.В ОС, як правило, відсутній окремий супервізор ресурсів, оскільки функції розподілу ресурсів реалізуються як на рівні зовнішнього планування, так і на рівні внутрішнього планування.
Основними функціями управління ресурсами є:
- Облік наявності та стану ресурсів;
- Прийом і облік заявок на ресурси від завдань і процесів;
- Розподіл ресурсів між завданнями та процесами;
- Організація використання ресурсів, виділених кожній задачі чи процесу;
- Повернення ресурсу в систему по мірі його звільнення споживачем.
Для реалізації функцій управління ресурсами в ОС формуються інформаційні таблиці, в яких відображаються
такі основні дані:
• для ресурсів:
- Облікова інформація про ресурс (ідентифікатор, клас, кількість каналів тощо);
- Код стану ресурсу;
- Ідентифікатор процесу-власника і т.п.;
• для заявок на ресурси:
- Ідентифікатор процесу-заявника;
- Пріоритет процесу;
- Ідентифікатор і необхідний обсяг ресурсу тощо
У ході організації використання ресурсів формуються таблиці, в яких зазначаються списки розподілених і
вільних ресурсів, зв'язку між ресурсами і процесами.
Поряд з проблемою раціонального розподілу ресурсів між процесами існує також проблема синхронізації протікання паралельних процесів і виключення виникнення тупиків в обчислювальній системі.
Процес у мультипрограмній системі знаходиться в стані тупика, якщо він очікує деякої події, яка ніколи не відбудеться.
Системна тупикова ситуація, або ситуація "зависання" системи - це ситуація, коли один або більше процесів
опиняються в стані безвиході.
В операційних системах тупики виникають в більшості випадків як результат конкуренції процесів за облада-
ня монопольно використовуваними ресурсами (рис. 3.1).
Сформульовані наступні чотири необхідних умови наявності тупика:
1) процеси вимагають надання їм монопольного права керування ресурсом, які їм виділяються (умова
взаимоисключения);
2) процеси утримують за собою ресурси, вже виділені їм, очікуючи в той же час виділення додаткових ре-
сурсов (умова очікування ресурсів);
3) ресурси не можна відібрати у процесів, що утримують їх, ці ресурси не будуть використані для завершення роботи (умова неперераспределяемості);
4) існує кільцева зв'язок процесів, в якій кожен процес утримує за собою один або більше ресурсів,
потрібних наступного процесу ланцюга (умова кругового очікування).
У проблемі тупиків виділяють наступні чотири основних напрямки: запобігання тупиків, обхід тупиків, виявлення тупиків, відновлення після тупиків.
При запобіганні тупиків метою є забезпечення умов, що виключають можливість виникнення тупикових ситуацій. Такий підхід є цілком коректним рішенням про те, що стосується самого глухого кута, проте він часто призводить до нераціонального використання ресурсів.
Обхід тупиків полягає в тому, щоб можна було передбачати менш жорсткі обмеження, ніж у випадку запобігання тупиків, і тим самим забезпечити краще використання ресурсів. За наявності засобів обходу тупиків не потрібно такий реалізації системи, при якій небезпека тупикових ситуацій навіть не виникає. Методи обходу враховують подібну можливість, однак у разі збільшення ймовірності виникнення тупикової ситуації тут приймаються заходи по акуратному обходу глухого кута. Методи виявлення тупиків застосовуються в системах, які допускають можливість виникнення тупикової ситуації як наслідок умисних або ненавмисних дій програмістів. Метою засобів виявлення тупиків є встановити сам факт виникнення тупикової ситуації і точно визначити ті процеси і ресурси, які виявились залученими в цю тупикову ситуацію.
Методи відновлення після тупиків застосовуються для усунення тупикових ситуацій з тим, щоб система могла продовжувати працювати, а процеси, що потрапили в тупикову ситуацію, могли завершитися із звільненням займаних ними ресурсів.
3. Паралельно процесу І КРИТИЧНІ ДІЛЯНКИ
Робоча суміш, створена механізмами вищої та внутрішнього планування, являє собою сукупність паралельних процесів.
Процеси називаються паралельними, якщо вони існують у системі одночасно.
Паралельні процеси називаються незалежними, якщо вони працюють без цілеспрямованої передачі сигналів інформації один одному.Паралельні процеси називаються пов'язаними, якщо здійснюється спрямований обмін сигналами (інформацією) між ними.Пов'язані паралельні процеси бувають синхронними, коли забезпечуються узгодження швидкостей їх розвитку в системі, і асинхронними, якщо швидкості протікання процесів не регулюються в системі.У механізмах синхронізації потребують всі види паралельних процесів, що функціонують в мультипрограмній обчислювальній системі.
Не зв'язані між собою процеси також потребують синхронізації своєї роботи. Це пояснюється тим, що вони
використовують під час функціонування одні й ті ж фізичні і логічні зовнішні пристрої, які в кожен
конкретний момент часу можуть обслуговувати тільки один процес (критичні ресурси).
Ресурс системи називається критичним, якщо він допускає в кожен момент часу обслуговування тільки одного процесу.Загальним принципом, покладеним в основу всіх механізмів синхронізації процесів, є принцип взаємовиключення.
Принцип взаємовиключення: кожен процес, що звертає до поділюваних (критичним) ресурсів, повинен ви-
чить можливість для всіх інших процесів одночасного з ним використання цього ресурсу.
Використання принципу взаимоисключения вимагає вбудовування в програми процесів механізмів синхронізації,
забезпечують виконання наступних умов:
• при зверненні декількох процесів до одного ресурсу, що тільки одному з них дозволено скористатися
цим ресурсом;
• в кожен момент часу тільки один процес повинен володіти критичним ресурсом.
Всі механізми синхронізації, реалізують принцип взаємовиключення, засновані на застосуванні концепції критичного ділянки програми.
Критичним ділянкою, критичною областю програми процесу називається той відрізок програмного коду
процесу, на якому цей процес утворюється до критичного ресурсу.Кількість критичних ділянок у процесі залежить тільки від того, до ресурсів якого виду він звертається при своєму функціонуванні.
Коли певний процес знаходиться на своїй критичному ділянці, інші процеси можуть продовжувати виконання, але без входу в їх критичні ділянки (зайнятим критичним ресурсам), коли процес виходить з критичного ділянки, то повинно бути дозволено використання звільненого критичного ресурсу. Забезпечення взаимоисключения є основною проблемою паралельного програмування.
4.Механізми синхронізації процесів
Критична секція
Важливим поняттям синхронізації процесів є поняття "критична секція" програми. Критична секція - це частина програми, в якій здійснюється доступ до даних, що розділяються. Щоб виключити ефект гонок по відношенню до деякого ресурсу, необхідно забезпечити, щоб у кожен момент в критичній секції, зв'язаної з цим ресурсом, перебував максимум один процес. Цей прийом називають взаємним виключенням.
Найпростіший спосіб забезпечити взаємне виключення - дозволити процесу, що знаходиться в критичній секції, забороняти все переривання. Однак цей спосіб не годиться, тому що небезпечно довіряти управління системою для користувача процесу, він може надовго зайняти процесор, а при краху процесу в критичній області крах потерпить вся система, тому що переривання ніколи не будуть дозволені.
Іншим способом є використання блокуючих змінних. З кожним ресурсом зв'язується двійкова змінна, яка приймає значення 1, якщо ресурс вільний (тобто ні один процес не знаходиться в даний момент в критичній секції, пов'язаною з цим процесом), і значення 0, якщо ресурс зайнятий. На малюнку 2.4 показаний фрагмент алгоритму процесу, що використовує для реалізації взаємного виключення доступу до ресурсу D блокує змінну F (D). Перед входом в критичну секцію процес перевіряє, чи вільний ресурс D. Якщо він зайнятий, то перевірка циклічно повторюється, якщо вільний, то значення змінної F (D) встановлюється в 0, і процес входить в критичну секцію. Після того, як процес виконає всі дії з ресурсом D, значення змінної F (D) знову встановлюється рівним 1.
Рис. 2.4. Реалізація критичних секцій з використанням блокуючих змінних
Якщо всі процеси написані з використанням вищеописаних угод, то взаємне виключення гарантується. Слід зауважити, що операція перевірки та встановлення блокує змінної повинна бути неподільною. Пояснимо це. Нехай у результаті перевірки змінної процес визначив, що ресурс вільний, але відразу після цього, не встигнувши встановити змінну в 0, був перерваний. За час його призупинення інший процес зайняв ресурс, увійшов у свою критичну секцію, але також був перерваний, не завершивши роботи з ресурсом. Коли управління було повернуто перший процесу, він, вважаючи ресурс вільним, встановив ознака зайнятості і почав виконувати свою критичну секцію. Таким чином був порушений принцип взаємного виключення, що потенційно може призвести до небажаних наслідків. Щоб уникнути таких ситуацій у системі команд машини бажано мати єдину команду "перевірка-установка", або ж реалізовувати системними засобами відповідні програмні примітиви, які б забороняли переривання протягом всієї операції перевірки та встановлення.
Реалізація критичних секцій з використанням блокуючих змінних має істотний недолік: протягом часу, коли один процес знаходиться в критичній секції, інший процес, якому потрібен той же ресурс, буде виконувати рутинні дії за опитуванням блокує змінної, марно витрачаючи процесорний час. Для усунення таких ситуацій може бути використаний так званий апарат подій. За допомогою цього засобу можуть вирішуватися не тільки проблеми взаємного виключення, але й більш загальні завдання синхронізації процесів. У різних операційних системах апарат подій реалізується по своєму, але в будь-якому випадку використовуються системні функції аналогічного призначення, які умовно назвемо WAIT (x) і POST (x), де x - ідентифікатор деякої події. На малюнку 2.5 показаний фрагмент алгоритму процесу, що використовує ці функції. Якщо ресурс зайнятий, то процес не виконує циклічний опитування, а викликає системну функцію WAIT (D), тут D позначає подія, що полягає у звільненні ресурсу D. Функція WAIT (D) переводить активний процес в стан ОЧІКУВАННЯ і робить відмітку в його дескрипторі про те, що процес чекає події D. Процес, який в цей час використовує ресурс D, після виходу з критичної секції виконує системну функцію POST (D), в результаті чого операційна система переглядає чергу очікують процесів і переводить процес, що очікує події D, в стан ГОТОВНІСТЬ.
5. семафор
Семафор - це захищена змінна, значення якої можна опитувати і змінювати тільки за допомогою операції
ініціалізація_семафора та двох спеціальних операцій P і V:
• операція P над семафором S записується як P (S) і виконується за правилами:
якщо S> 0 то S: = S-1 інакше (очікувати на S);
• операція V над семафором S записується як V (S) і виконується за правилами:
якщо (один або більше процесів очікують на S) то (дозволити одному з процесів продовжити роботу) інакше S: = S +1.
Розрізняють два види семафорів: двійкові семафори, у яких S може приймати значення 0 і 1, і вважають семафори, де S може приймати невід'ємні цілі значення.
Подібно операції проверіть_і_установіть, операції ініціалізація_семафора, P (S) і V (S) є неподільними.
Ділянки взаимоисключения по семафору S обрамляются операціями P (S) і V (S). Якщо одночасно декілька процесів спробують виконати операцію P (S), то тільки одному з них буде дозволено це зробити, а іншим доведеться чекати.
Семафори і операції над ними можуть бути реалізовані як програмно (рис. 3.5), так і апаратно. при програмноїреалізації вони розміщуються в тій частині ядра операційної системи, де здійснюється управління зміною станів процесів.
Узагальнююче засіб синхронізації процесів запропонував Дейкстра, який ввів два нових примітиву. В абстрактній формі ці примітиви, що позначаються P і V, оперують над цілими невід'ємними змінними, званими семафорами. Нехай S такий семафор. Операції визначаються наступним чином:
V (S): мінлива S збільшується на 1 одним неподільним дією; вибірка, інкремент та запам'ятовування не можуть бути перервані, і до S немає доступу іншим процесам під час виконання цієї операції.
P (S): зменшення S на 1, якщо це можливо. Якщо S = 0, то неможливо зменшити S і залишитися в області цілих невід'ємних значень, в цьому випадку процес, що викликає P-операцію, чекає, поки це зменшення стане можливим. Успішна перевірка і зменшення також є неподільною операцією.
Рис. 2.5. Реалізація критичної секції з використанням системних функцій WAIT (D) і POST (D)
В окремому випадку, коли семафор S може приймати тільки значення 0 і 1, він перетворюється на блокуючу змінну. Операція P містить в собі потенційну можливість переходу процесу, який її виконує, в стан очікування, в той час як V-операція може за деяких обставин активізувати інший процес, призупинений операцією P (порівняйте ці операції з системними функціями WAIT і POST).
Розглянемо використання семафорів на класичному прикладі взаємодії двох процесів, що виконуються в режимі мультипрограмування, один з яких пише дані в буферний пул, а інший зчитує їх з буферного пула. Нехай буферний пул складається з N буферів, кожний з яких може містити один запис. Процес "письменник" повинен припинятися, коли всі буфери опиняються зайнятими, і активізуватися при звільненні хоча б одного буфера. Навпаки, процес "читач" припиняється, коли всі буфери порожні, і активізується при появі хоч би одного запису.
Введемо два семафора: e - число порожніх буферів і f - число заповнених буферів. Припустимо, що запис у буфер і зчитування з буфера є критичними секціями (як у прикладі з принт-сервером на початку цього розділу). Введемо також двійковий семафор b, який використовується для забезпечення взаємного виключення. Тоді процеси можуть бути описані в такий спосіб:
/ / Глобальні змінні
# Define N 256
int e = N, f = 0, b = 1;
void Writer ()
while (1)
PrepareNextRecord (); / * підготовка нового запису * /
P (e) / * Зменшити число вільних буферів, якщо вони є * /
/ * У противному випадку - чекати, поки вони звільняться * /
P (b) / * Вхід в критичну секцію * /
AddToBuffer (); / * Додати новий запис у буфер * /
V (b) / * Вихід з критичної секції * /
V (f) / * Збільшити число зайнятих буферів * /
void Reader ()
while (1)
P (f) / * Зменшити число зайнятих буферів, якщо вони є * /
/ * У противному разі чекати, поки вони з'являться * /
P (b) / * Вхід в критичну секцію * /
GetFromBuffer (); / * Взяти запис з буфера * /
V (b) / * Вихід з критичної секції * /
V (e) / * Збільшити число вільних буферів * /
ProcessRecord (); / * Опрацювати запис * /
Тупики
Наведений вище приклад допоможе нам проілюструвати ще одну проблему синхронізації - взаємні блокування, звані також дедлок (deadlocks), клінчами (clinch) або тупиками. Якщо переставити місцями операції P (e) і P (b) у програмі "письменника", то при деякому збігу обставин ці два процеси можуть взаємно заблокувати один одного. Дійсно, нехай "письменник" першим увійде в критичну секцію та виявить відсутність вільних буферів; він почне чекати, коли "читач" візьме чергову запис з буфера, але "читач" не зможе цього зробити, тому що для цього необхідно увійти в критичну секцію, вхід до якої заблоковано процесом "письменником".
Розглянемо ще один приклад глухого кута. Нехай двох процесів, що виконується в режимі мультипрограмування, для виконання їхньої роботи потрібно два ресурси, наприклад, принтер і диск. На малюнку 2.6, а показані фрагменти відповідних програм. І нехай після того, як процес А зайняв принтер (встановив блокує змінну), він був перерваний. Управління отримав процес В, який спочатку зайняв диск, але при виконанні наступної команди був заблокований, так як принтер виявився вже зайнятим процесом А. Управління знову отримав процес А, який у відповідності зі своєю програмою зробив спробу зайняти диск і був заблокований: диск вже розподілено процесу В. У такому положенні процеси А і В можуть знаходитися як завгодно довго.
У залежності від співвідношення швидкостей процесів, вони можуть або цілком незалежно використовувати колективні ресурси (г), або утворювати черги до ресурсів (в), або взаємно блокувати один одного (б). Тупикові ситуації треба відрізняти від простих черг, хоча і ті й інші виникають при спільному використанні ресурсів і зовні виглядають схоже: процес призупиняється і чекає звільнення ресурсу. Однак чергу - це нормальне явище, невід'ємною ознакою високого коефіцієнта використання ресурсів при випадковому надходженні запитів. Вона виникає тоді, коли ресурс недоступний в даний момент, але через деякий час він звільняється, і процес продовжує своє виконання. Тупик ж, що видно з його назви, є до певної міри нерозв'язною ситуацією.
У розглянутих прикладах глухий кут був утворений двома процесами, але взаємно блокувати один одного можуть і більше число процесів.
Проблема тупиків включає в себе наступні завдання:
- Запобігання тупиків,
- Розпізнавання тупиків,
- Відновлення системи після тупиків.
Рис. 2.6. (A) фрагменти програм А і В, які поділяють принтер і диск; (б) взаємне блокування (клінч); (в) чергу до разделяемому диску; (г) незалежне використання ресурсів
Тупики можуть бути запобігти на стадії написання програм, тобто програми повинні бути написані таким чином, щоб глухий кут не міг виникнути ні при якому співвідношенні взаємних швидкостей процесів. Так, якщо б у попередньому прикладі процес А і процес У запитували ресурси в однаковій послідовності, то глухий кут був би в принципі неможливий. Другий підхід до запобігання тупиків називається динамічним і полягає у використанні певних правил при призначенні ресурсів процесам, наприклад, ресурси можуть виділятися в певній послідовності, загальною для всіх процесів.
У деяких випадках, коли тупикова ситуація утворена багатьма процесами, що використовують багато ресурсів, розпізнавання глухого кута є нетривіальним завданням. Існують формальні, програмно-реалізовані методи розпізнавання тупиків, засновані на веденні таблиць розподілу ресурсів і таблиць запитів до зайнятих ресурсів. Аналіз цих таблиць дозволяє виявити взаємні блокування.
Якщо ж тупикова ситуація виникла, то не обов'язково знімати з виконання всі заблоковані процеси. Можна зняти тільки частину з них, при цьому звільняються ресурси, очікувані іншими процесами, можна повернути деякі процеси в область свопінгу, можна зробити "відкат" деяких процесів до так званої контрольної точки, в якій запам'ятовується вся інформація, необхідна для відновлення виконання програми з даного місця. Контрольні точки розставляються в програмі в місцях, після яких можливе виникнення безвиході.
З усього вищесказаного ясно, що використовувати семафори потрібно дуже обережно, тому що одна незначна помилка може призвести до зупинки системи. Для того, щоб полегшити написання коректних програм, було запропоновано високорівневий засіб синхронізації, зване монітором. Монітор - це набір процедур, змінних і структур даних. Процеси можуть викликати процедури монітора, але не мають доступу до внутрішніх даних монітора. Монітори мають важливе властивість, яка робить їх корисними для досягнення взаємного виключення: тільки один процес може бути активним по відношенню до монітора. Компілятор обробляє виклики процедур монітора особливим чином. Зазвичай, коли процес викликає процедуру монітора, то перші кілька інструкцій цієї процедури перевіряють, не активний може який-небудь інший процес по відношенню до цього монітора. Якщо так, то зухвалий процес припиняється, поки інший процес не звільнить монітор. Таким чином, виключення входу декількох процесів в монітор реалізується не програмістом, а компілятором, що робить помилки менш імовірними.
6. МОНІТОРИ
Монітор - це механізм організації паралелізму, який містить як дані, так і процедури, необхідні для
реалізації динамічного розподілу конкретного загального ресурсу або групи загальних ресурсів.
Щоб забезпечити виділення потрібного йому ресурсу, процес повинен звернутися до конкретної процедури монітора.Необхідність входу в монітор в різні моменти часу може виникати у багатьох процесів. Однак вхід до монітору знаходиться під жорстким контролем: тут здійснюється взаємовиключає процесів, так що в кожен момент часу тільки одному процесу дозволяється увійти в монітор. Процесам, які хочуть увійти в монітор, коли він зайнятий,доводиться чекати, причому режимом очікування автоматично керує сам монітор.Якщо процес звертається до деякої процедурі монітора і виявляється, що відповідний ресурс вже зайнятий, то ця процедура монітора видає процесу команду WAIT (ЧЕКАТИ). Процес, який отримав таку команду, переводиться в режим очікування поза монітора.З часом процес, який займав потрібний ресурс, звільняє його, звертаючись для цього до монітора. Відповідна процедура монітора може просто прийняти повідомлення про повернення ресурсу, а потім чекати, поки не надійде запит від іншого процесу, якому буде потрібно цей ресурс. Однак може виявитися, що вже є процеси, які очікують звільнення даного ресурсу. У цьому випадку монітор виконує примітив оповіщення SIGNAL, щоб один з очікуючих процесів міг зайняти даний ресурс і покинути чергу до монітора. Якщо процес сигналізує про звільнення ресурсу і в цей час немає процесів, що очікують цей ресурс, то подібне сповіщення не викликає ніяких інших дій, крім того, що монітор знову вносить ресурс в список вільних.
7. Алгоритми управління ресурсами
Вступні зауваження
Для реалізації функцій управління ресурсами операційна система здійснює постійний облік їх наявності та стану. У сучасних ОС найбільш вживаним є ідентифікація ресурсу за допомогою файлу його опису.
Способи формування запитів на ресурси розрізняються місцем їх видачі в операційну систему - в пакеті завдань або в програмі під час її виконання. У першому випадку ОС здійснює статичний розподіл ресурсів, а в
другому - динамічний. Операційна система може прийняти, відкласти або проігнорувати запит на ресурс, що залежить від реалізованого в ОС алгоритму управління ресурсами.
Існують також комбіновані способи формування запитів на ресурси з попереднім замовленням в пакеті
завдань або в програмі і виконавчим запитом під час виконання програми.
АЛГОРИТМ НАДАННЯ РЕСУРСУ за першим зверненням
Алгоритм подання ресурсу за першим зверненням до нього є найпростішим з алгоритмів управління
ресурсами. Суть даного алгоритму полягає в наступному.
Незалежно від місця видачі запиту на ресурс (пакет завдань або виконується в системі програма) ОС виконує наступні дії:
1) фіксує перша згадка імені запитуваного ресурсу;
2) розподіляє конкретну фізичну пристрій, відповідне цьому імені, джерела запиту;
3) позначає ресурс у відповідній таблиці як виділений (зайнятий, розподілений).
Розподілений ресурс не може бути виділений іншим процесам, що виконується в системі, поки процес, якому цей ресурс виділено, не звільнить його або не припинить своє існування.
Даний алгоритм простий в реалізації, проте володіє серйозним недоліком - при його застосуванні можливо появлення тупикових ситуацій в обчислювальній системі. Тому цей алгоритм називають також алгоритмом з можливим виникненням тупиків.
АЛГОРИТМИ ЗАПОБІГАННЯ Тупиків
Всі алгоритми запобігання тупикових ситуацій при управлінні ресурсами засновані на порушенні хоча б одного з необхідних умов наявності тупика Д. Хавендером (Havender JW) запропоновані наступні стратегії:
1) кожен процес повинен запрошувати всі необхідні йому ресурси відразу, причому не може почати виконуватися до тих пір, поки всі вони не будуть йому надані;
2) якщо процес, що утримує певні ресурси, отримує відмову в задоволенні запиту на додаткові ресурси, цей процес повинен звільнити свої первинні ресурси і при необхідності запросити їх знову разом з додатковими;
3) введення лінійної впорядкованості за типами ресурсів для всіх процесів; іншими словами, якщо процесу виділені ресурси даного типу, то надалі він може запросити тільки ресурси більш далеких по порядку типів.
Можна бачити, що кожна з цих стратегій порушує одне з необхідних умов існування глухого кута. Свідомо залишено умова монопольного володіння процесом виділеними йому ресурсами, оскільки потрібно передбачити можливість роботи з закріпленими ресурсами.Алгоритм попереднього розподілу ресурсів відповідно з першим стратегічним принципом Хавендера вимагає, щоб процес відразу ж запитував всі ресурси, які йому знадобляться. Система у відповідь на ці запити повинна представляти ресурси за принципом "все або нічого", тобто якщо набір ресурсів, необхідний процесу, є, то система надає процесу всі ці ресурси відразу ж так, що він може продовжити свою роботу. Якщо в даний момент часу ні повного набору ресурсів немає, то цьому процесу доведеться чекати, поки вони не звільняться. В алгоритмі розподілу ресурсів із звільненням при відмові процес, що має у своєму розпорядженні деякі ресурси, якщо він отримує відмову на запит про виділення додаткових ресурсів, повинен звільнити всі належачищие йому ресурси і при необхідності запитувати їх знову разом з додатковими. Така ситуація дієво веде до
порушення умови неперерозподілу, подібним чином можна забирати ресурси і утримують їх процесів до
завершення цих процесів.Алгоритм розподілу з лінійним упорядкуванням за типами ресурсів передбачає попереднє присвоєння всіх ресурсів обчислювальної системи унікальних номерів.Процеси в ході свого виконання повинні запитувати необхідні їм ресурси строго в порядку зростання номерів цих ресурсів, так що ситуація кругового очікування виникнути не може.
АЛГОРИТМИ ОБХОДУ Тупиків
Якщо навіть необхідні умови виникнення тупиків не порушені, то все ж є можливість уникнути тупикові ситуації, раціонально розподіляючи ресурси з дотриманням певних правил. Найбільш відомими алгоритмом, що дозволяють здійснити обхід тупиків, є алгоритм Дейкстри, званий також алгоритмом банкіра, і
алгоритм Хаберман, званий алгоритмом регульованого розподілу.
Алгоритм регульованого розподілу заснований на представленні розподілу ресурсів, запитів і процесів у вигляді орієнтованого графа (орграфа), званого графом розподілу ресурсів (ГРР).
Правило Хаберман: Якщо граф розподілу ресурсів має цикли, то такий розподіл ресурсів по процесах
може призвести до утворення тупикової ситуації.
Це правило дозволяє побудувати наступний алгоритм розподілу ресурсів:
• при вступі чергового запиту перевірити наявність вільного ресурсу;
• якщо вільний ресурс відсутній, то відмова, процес блокувати, інакше зробити попередній розподіл і
скорегувати ГРР;
• перевірити ГРР на наявність циклів;
• якщо в ГРР є цикли, то скасувати попередній розподіл, відновити ГРР, сформувати відмову і блокувати процес, інакше закріпити ресурс за процесом.Алгоритм Хаберман дозволяє обійти тупики, однак він складний в реалізації через необхідність роботи з графом розподілу ресурсів.
ПОНЯТТЯ ПРО ОРГАНІЗАЦІЮ І УПРАВЛІННІ ФІЗИЧНОЇ ПАМ'ЯТТЮ
В операційних системах розрізняють два види пам'яті: основна (первинна) і зовнішня (вторинна).
Основна пам'ять - оперативна пам'ять центрального процесора або її частина, що представляє собою
єдиний простір пам'яті.
Зовнішня пам'ять - пам'ять, дані в якій доступні центральному процесору за допомогою операцій введення-виведення.
Для безпосереднього виконання програм або звернення до даних необхідно, щоб вони розміщувалися в основнії пам'яті. Зовнішня пам'ять має, як правило, набагато більшу ємність, ніж основна, коштує дешевше і дозволяє зберігати дані і програми, які повинні бути напоготові для обробки.Крім основної та зовнішньої пам'яті в сучасних ЕОМ існує додаткова швидкодіюча пам'ять, назване кеш-пам'яттю.
Усі три види пам'яті утворюють ієрархію пам'яті обчислювальної машини .Операційним системам з кількома рівнями ієрархії пам'яті властива висока інтенсивність човникових обмінів програмами і даними між фізичними пристроями пам'яті різних рівнів. Такі обміни віднімають системні ресурси (наприклад, час центрального процесора), які можна було б використовувати більш продуктивно.
Основна пам'ять являє собою один з найдорожчих ресурсів. Головним завданням при розробці ОС вва-
тается оптимальне використання основної пам'яті на основі раціональної організації та управління.
Під організацією пам'яті розуміється те, яким чином представляється ос-новная пам'ять.
Під управлінням пам'яттю розуміється те, як використовується основна пам'ять.
В ОС застосовуються такі види представлення основної пам'яті:
1) фіксованими блоками рівного розміру;
2) фіксованими розділами неоднакового розміру;
3) динамічними розділами, розміри яких змінюються в ході роботи обчислювальної системи.
Використання основної пам'яті може здійснюватися такими способами:
1) розміщення в пам'яті одноразово тільки однієї програми користувачів;
2) розміщення в пам'яті одночасно декількох програм користувачів;
3) розміщення програм користувачів в конкретному заздалегідь заданому розділі основної пам'яті;
4) розміщення кожної програми користувача в одному безперервному (однозв'язний) просторі основної пам'яті;
5) розміщення програми користувача в несуміжних областях оперативної пам'яті.
В операційних системах може застосовуватися будь-яка комбінація перерахованих видів представлення і способів використування основної пам'яті ЕОМ.Незалежно від того, яка схема організації пам'яті прийнята для конкретної ОС, необхідно вирішити, які стратегії слід застосовувати для досягнення оптимальних характеристик.
Стратегії управління пам'яттю визначають, як буде працювати пам'ять з конкретною схемою організації при різних підходах до вирішення наступних питань:
1) коли слід помістити нову програму в пам'ять;
2) в яке місце основної пам'яті буде розміщуватися чергова програма;
3) як розмістити чергову програму в пам'яті (з мінімізацією втрат пам'яті або з максимізацією швидкості розміщения);
4) яку з знаходяться в пам'яті програм слід вивести з пам'яті, якщо необхідно обов'язково розмістити нову програму, а пам'ять вже заповнена.
В існуючих ОС реалізовані стратегії управління, по-різному відповідають на перераховані вище питання,
що неабиякою мірою обумовлено наявними в розпорядженні розробників апаратурними і програмними методами.
. Ієрархія пам'яті ЕОМ
Кеш-пам'ять
Основна
(Первинна) пам'ять
Зовнішня
(Вторинна) пам'ять
Стратегії управління пам'яттю поділяються на такі категорії: стратегії вибірки; стратегії розміщення; стратегії
заміщення.
У свою чергу, стратегії вибірки поділяють на дві підкатегорії: стратегії вибірки за запитом (на вимогу),
стратегії випереджаючої вибірки.
Стратегії вибірки ставлять своєю метою визначити, коли слід "заштовхнути" чергову програму (або блок про-
грами) або дані в основну пам'ять.
Стратегії розміщення ставлять своєю метою визначити, в яке місце основної пам'яті слід розміщувати надходить програму. Найбільш поширеними є стратегії розміщення, реалізують принципи заняття "першого слушного "," найбільш відповідного "і" найменш придатного "за розмірами вільної ділянки пам'яті.
Стратегії заміщення ставлять своєю метою визначити, який блок програми або даних слід вивести ("витолк-
нуть ") з основної пам'яті, щоб звільнити місце для розміщення знову надходять програм або даних.
При реалізації стратегій розміщення операційні системи часто враховують вимоги зв'язкового розподілу
пам'яті для програм і даних. Чіткий розподіл пам'яті - такий розподіл основної пам'яті ЕОМ, при якому кожна програм займаєодин безперервний (зв'язний) блок осередків пам'яті. Недоладне розподіл пам'яті - такий розподіл основної пам'яті ЕОМ, при якому програма користувача розбивається на ряд блоків (сегментів, сторінок), які можуть розміщуватися в основній пам'яті в ділянках, не обов'язково сусідять один з одним (у несуміжних ділянках). У цьому випадку забезпечується більш ефективне використання простору основної пам'яті.
МЕТОДИ зв'язкова РОЗПОДІЛУ ОСНОВНої ПАМ'ЯТІ
Звязний розподіл пам'яті для одного користувача
Чіткий розподіл пам'яті для одного користувача, зване також одиночним безперервним розподілом,
застосовується в ЕОМ, що працюють в пакетному однопрограмні режимі під управлінням найпростішої ОС.
Вся основна частина ЕОМ, не зайнята програмами операційної системи, виділяється програмі єдиного на
даному відрізку часу користувача.
Розмір програми в цьому випадку обмежується розміром доступної основної пам'яті, проте існує можливість виконання програм, розмір яких перевищує розмір основної пам'яті, використовуючи механізм оверлеїв. Коефіцієнт використання пам'яті обчислюється за формулою ηс1 = Vп / Vo , де Vп - розмір програми користувача; Vо - об'єм доступного для розподілу основної пам'яті ЕОМ.
Функціями ОС є: виділення програмі необхідного простору пам'яті; захист пам'яті; звільнення памяті.
Функція виділення пам'яті зводиться до надання програмі всієї доступної пам'яті ЕОМ.
Захист пам'яті в однопрограмних системах полягає в установці захисту областей пам'яті, зайнятих операційної
системою, від впливу програм користувача. Ця функція реалізується за допомогою одного регістра кордону, вбудованого в центральний процесор. Регістр грані містить або старший адрес команди, що відноситься до операційної системи або молодший адресу доступною програмою основної пам'яті (адреса початку програми). Якщо програма користувача намагається увійти в область операційної системи, то виробляється переривання по захисту пам'яті, і програма аварійно завершується.
Зв’язний розподіл пам'яті примультипрограммной обробці
При мультипрограммной обробці в пам'яті комп'ютера розміщується відразу кілька завдань. Розподіл пам'яті між завданнями в цьому випадку може бути виконано наступними способами: розподіл фіксованими розділами; розподіл змінними розділами; розподіл зі свопінгом.
Розподіл фіксованими розділами має дві модифікації:
1) із завантаженням програм в абсолютних адресах;
2) із завантаженням переміщуються модулів.
При завантаженні переміщуються модулів вся оперативна пам'ять машини розбивається на деяку кількість розділів фіксованого розміру . Розміри розділів можуть не збігатися. У кожному розділі може бути розміщено тільки одне завдання. У разі завантаження програм в абсолютних адресах при їх підготовці вказується початковий адресу завантаження програм, збігається з початковим адресою розділу, в якому ця програма буде виконуватися. У разі завантаження переміщуються модулів розділ, в якому буде розміщено завдання, або автоматично визначається операційною системою відповідно до реалізованої в ньому стратегією вибору розділу ("перший підходящий", "самий підходящий "," самий невідповідний "), або вказується операційній системі спеціальними командами мови управління завданнями.В обох випадках завдання монопольно володіє всім обсягом оперативної пам'яті розділу, в який воно було поміщено операційною системою.
Основним недоліком розподілу пам'яті фіксованими розділами є неефективне використання ре-
сурсов обчислювальної системи через можливу появу довгих черг завдань, які очікують звільнення конкретного розділу в той час, як інші розділи порожні.
Захист пам'яті при розподілі фіксованими розділами виконується аналогічно захисту пам'яті для одного користувача, тільки тепер необхідно наявність декількох граничних регістрів - по два регістри на кожен розділ. Уодному із граничних регістрів вказується нижня межа розділу, а в другому - його верхня межа. Якщо програма користувача намагається звернутися до даних, розташованим поза області адрес даного розділу, то виробляється прериваніе по захисту пам'яті.
У мультипрограмних системах з фіксованими розділами спостерігається явище фрагментації пам'яті.
Фрагментація пам'яті - поява в пам'яті обчислювальної машини чергування зайнятих і незайнятих (вільних)ділянок оперативної пам'яті.
При розподілі фіксованими розділами поява фрагментації обумовлено тим, що або завдання пользователей повному обсязі займають виділені їм розділи, або частину розділів залишається незайнятою.
Розподіл пам'яті змінними розділами призначено для підвищення ефективності використання оперативной пам'яті ЕОМ. Суть способу розподілу пам'яті змінними розділами полягає в тому, що завданням, коли вони поступають, виділяється такий об'єм пам'яті, який їм потрібно, тобто розмір розділу оперативної пам'яті, що виділяється кожному завданням, в точності відповідає розміру цього завдання.
Є дві модифікації способу розподілу змінними розділами: розподіл змінними неперемещаемимі розділами; розподіл змінними переміщуваними розділами.
При розподілі пам'яті змінними непереміщуваними розділами (динамічними розділами) операційна система створює дві таблиці: таблицю обліку розподілених областей пам'яті та таблицю обліку вільних областей пам'яті("Дірок").
При надходженні чергового завдання пам'ять для нього відводиться на етапі довгострокового планування, причому виділення пам'яті здійснюється за інформацією з таблиці обліку "дірок" відповідно до прийнятої в ОС стратегією розміщення ("перший підходящий", "самий підходящий", "самий невідповідний"). При успішному розподілі ОС коригує
обидві таблиці - розподілених і вільних областей.
При розподілі пам'яті змінними переміщуваними розділами операційна система здійснює дії, на-
звані ущільненням пам'яті, що складаються у переміщенні всіх зайнятих ділянок до одного чи іншого краю основної пам'яті. Завдяки цьому замість великої кількості невеликих "дірок", що утворюються при використанні распределенія змінними непереміщуваними розділами, формується єдиний (зв'язний) ділянка вільної пам'яті. Цей процес називають також дефрагментацією пам'яті.
Дефрагментація пам'яті, застосовувана при розподілі переміщуваними розділами, має свої недоліки:
1) потрібні додаткові витрати часу;
2) під час ущільнення пам'яті система повинна припиняти (призупиняти) усі інші роботи, що часто може
виявитися неприйнятним;
3) необхідність переміщення завдань у пам'яті вимагає зберігання значного обсягу інформації, пов'язаної з
розміщенням програм в пам'яті, що збільшує вимоги до пам'яті з боку ОС;
4) при інтенсивному потоці коротких програм може виникнути необхідність частої дефрагментації пам'яті, так
що заточується на ці цілі системні ресурси можуть виявитися невиправданими одержуваної вигодою.
Розподіл пам'яті зі свопінгом (від англ. Swapping - підкачка) характеризується тим, що на відміну від рассмотренних раніше способів розподілу програми користувачів не залишаються в основній пам'яті до моменту їх завершення.
Вся пам'ять цілком на короткий період виділяється одному завданню, потім в деякий момент часу це завдання виводиться (виштовхується, тобто здійснюється "відкачка"), а чергове завдання вводиться (заштовхується, тобто здійснюється "під-
качка "). У звичайному випадку кожне завдання, ще до свого завершення, буде багато раз перекачуватися із зовнішньої пам'яті в основну і назад. Для забезпечення свопінгу у зовнішній пам'яті ОС створює один або декілька файлів підкачки, де зберігаються образи оперативної пам'яті знаходяться в роботі завдань користувачів. Спосіб розподілу пам'яті зі свопінгом застосовується в найпростіших ОС, що працюють у режимі поділу часу.
Стратегії розміщення інформації в пам'яті
Стратегії розміщення інформації в пам'яті призначені для того, щоб визначити, в яке місце основної пам'яті слід поміщати надходять програми і дані при розподілі пам'яті непереміщуваними розділами. Найбільш
часто застосовуються такі стратегії:
• розміщення з вибором першого підходящого (стратегія "перший підходящий");
• розміщення з вибором найбільш підходящого (стратегія "самий підходящий");
• алгоритм з вибором найменш придатного (стратегія "самий невідповідний").
Стратегія "перший підходящий": полягає у виконанні наступних кроків:
1) порядок таблицю вільних областей у порядку зростання адрес;
2) помістити інформацію в перший зустрівся ділянку основної пам'яті розміром не менше необхідного.
Стратегія "самий підходящий": реалізує наступну послідовність дій:
1) порядок таблицю вільних областей у порядку зростання розмірів вільних областей;
2) помістити інформацію в перший зустрівся ділянку вільної пам'яті розміром не менше необхідного.
Стратегія "самий невідповідний": виконує наступні дії:
1) порядок таблицю вільних областей спадний розмірів областей;
2) помістити інформацію в перший зустрівся ділянку вільної пам'яті розміром не менше необхідного.
Керування файлами
Поняття файлового способу зберігання даних і файлової системи
З появою у складі ЕОМ зовнішніх запам'ятовуючих пристроїв, здатних зберігати величезні масиви інформації в протягом тривалого часу, призвело до необхідності розробки такого способу зберігання і управління даними, при якому витрати на доступ до інформації з боку розробників прикладних систем і програм були б зведені до мінимума.
У багатокористувацьких обчислювальних системах вторинна (зовнішня) пам'ять має бути так само разделяемості між користувачами, як і первинна. Такий поділ в сучасних операційних системах забезпечується за використанням файлового способу зберігання даних.
Файловий спосіб зберігання даних - це спосіб зберігання даних, за якого кожен набір даних представляються як іменоване, можливо, захищене, зібрання записів, званої файлом.
Файл - ідентифікована сукупність примірників повністю описаного в конкретній програмі типу даних,знаходяться поза програмою в зовнішній пам'яті і доступних програмі допомогою спеціальних операцій.
Файлова система - система управління даними з файловим способом зберігання.
В результаті застосування файлового способу зберігання даних користувач отримує віртуальне представлення зовнішньої пам'яті і працює з нею не в термінах команд управління конкретними фізичними пристроями зовнішньої пам'яті, а в термінах, обумовлених особливостями структури і складу його конкретних наборів даних. Користувач бачить віртуальну зовнішню пам'ять як середу, здатну зберігати його відокремлені і поіменовані інформаційні об'єкти, що мають певну внутрішню структуру. Середа повинна забезпечити можливість зберігання довільного колі-
пра ці файлів без обмеження обсягу, причому користувач повинен мати можливість доступу як до окремих файлів,так і до їх складових частин, з урахуванням логічної структури.
Файлові системи можуть бути простими і складними. Їх природа залежить від різноманітності застосувань і середовища, в яке буде використовуватися операційна система. У загальному випадку до файлової системи висувають такі основні
вимоги:
• кожен користувач повинен мати можливість створювати, видаляти і змінювати файли;
• кожен користувач може мати контрольований доступ до файлів інших користувачів;
• кожен користувач може контролювати, які типи доступу дозволені до його файлів;
• кожен користувач повинен мати можливість переструктурувати свої файли до форми, яка відповідає його
завдання;
• кожен користувач повинен мати можливість пересилати дані між файлами;
• кожен користувач повинен мати можливість копіювати і відновлювати свої файли в разі їх пошкодження;
• кожен користувач повинен мати можливість доступу до своїх файлів по їх символічним іменам.
Для того щоб задовольнити перелічені вище вимоги, програмна частина файлових систем повинна містити наступні компоненти:
1) засоби взаємодії з процесами користувачів, забезпечують приймання та інтерпретацію запитів від пользователя на обробку файлів і що повідомляють йому про результати виконаної обробки;
2) засоби реалізації методів доступу до файлу і до його складовим елементам;
3) кошти розподілу зовнішньої пам'яті для зберігання файлів, а також її звільнення у міру знищення файлов;
4) засоби обліку розташування файлів і їх складових елементів.
Організація файлів
Фізична організація файлів залежить від фізичних характеристик зовнішнього пристрою. Існують зовнішні устройства, які можна розглядати як послідовні файли, де обмін записами доступний тільки в лінійному порядку. До них відносяться накопичувачі на магнітних стрічках, стримери, принтери, модеми і т.п. У порівнянні з ними назбиратели на магнітних дисках допускають величезну гнучкість організації файлів. На поверхні дискової пластини розміщено серія концентричних кіл, які називаються доріжками або циліндрами диска. Кожна доріжка підрозділяється на сектори. Сектор - це мінімальний обсяг інформації, зазвичай передається в дискової системі.
Фізичні записи можуть розташовуватися в будь-якому місці диска. З міркувань ефективності при пошуку і передачі даних робляться всілякі спроби розташувати пов'язані фізичні записи в суміжних секторах або на сусідніх пластинах тієї ж доріжки диска.
Структура диска дозволяє системі управління файлами організувати файли трьома різними способами: послідовним, безперервним, сегментованим. Кожна організація файлів володіє своїми обмеженнями та характеристиками продуктивності.
Послідовна організація файлу передбачає створення на диску послідовного файлу.
Послідовний файл - файл, до компонентів якого забезпечується лише послідовний доступ в відповідності з впорядкованістю цих компонентів.
У послідовних файлах розміщують набори даних з послідовною організацією. Зазвичай в послідовних файлах використовують один покажчик від одного блоку до іншого (рис. 5.8). Іноді для прискорення доступу застосовують подвійні посилання.
Послідовний файл складається із зв'язаної послідовності блоків. В одному блоці послідовного файлу може бути розміщена одна або декілька записів послідовного набору даних. Доступ до послідовного файлу відрізняється простотою і досить швидкий. Для того, щоб знайти потрібний запис, файл повинен бути переглянутий блок за блоком від початку файлу, поки не буде знайдена необхідна запис. При обробці послідовного файлу в файлових системах розглядають наступні випадки розміщення логічного запису у фізичних блоках:
1) один фізичний блок під одну логічну запис;
2) кілька фізичних блоків під одну логічну запис;
3) один фізичний блок під декілька логічних записів.
У першому випадку необхідно зчитувати в первинну пам'ять тільки один фізичний блок. Логічна запис може бути оновлена на тому ж місці шляхом запису нових даних поверх старих. Включити новий запис досить просто, так як система виділяє ще один фізичний блок і налаштовує відповідні покажчики.У другому випадку для того, щоб отримати логічну запис цілком, всі фізичні блоки, зайняті нею, повинні бути лічені в пам'ять. Оновлення логічного запису проводиться так само, як і в першому випадку - шляхом запису нових даних поверх старих у знайденому фізичному блоці. Відносно нескладно додати нову логічну запис, так як для цього система повинна просто виділити необхідну кількість блоків для нового запису і налаштувати відповідні указатели.
У третьому випадку для забезпечення доступу до необхідної запису програма управління файлами повинна спочатку знайти блок, де вона знаходиться. Після того, як цей блок лічений в первинну пам'ять, виконується виділення потрібної записи з содержимому блоку. Додати новий запис значно складніше, ніж у перших двох випадках, так як якщо блок заповнений, необхідно перенести в новий блок одну або кілька записів зі старого блоку з відповідною корекцією покажчиків.Доступ до запису в послідовному файлі вимагає, в середньому, читання та перегляду половини блоків файлу.
Безперервна організація файлу передбачає створення на диску безперервного файлу.
Безперервний файл - файл на носії, що з низки фізичних блоків, які все розташовані в одній
суцільний області дискового простору.
Безперервна організація файлу являє собою жорстку структуру, що забезпечує найшвидший доступ до даними. Розмір безперервного файлу фіксований і задається у момент створення файла. Файл не може бути збільшений у розміру, проте зменшення довжини безперервного файлу допускається. Головний недолік безперервної організації файлу в тому, що в зовнішній пам'яті не завжди може бути виділено потрібну кількість суміжних фізичних блоків.
Доступ до записів безперервного файлу досить простий. Якщо позначити через r - номер запису, l - довжину запису і L
- Довжину блоку, то номер b блоку, де знаходиться запис, обчислюється за формулою
b = l r / L.
Значення b використовується потім для зчитування потрібного блоку в первинну пам'ять. Оскільки не потрібно проходити по вказівниками, як у першому випадку, то досягається суттєве скорочення витрат часу на доступ до даних.Оновлення запису r скоюється дуже просто - вона просто перекривається новими даними. При цьому відбувається звернення до потрібного кількістю фізичних блоків. Для безперервного файлу мають місце ті ж три випадки розміщення логічних записів у фізичних блоках, що і для послідовного файлу. Включення нового запису в безперервний файл дуже складно. Для цього системі, в середньому, необхідно перемістити половину записів довжиною l, перш ніж звільнити місце для нового запису. Включення нового запису в
безперервний файл може закінчитися невдачею, якщо при зсуві записів остання запис буде пересунуто за кордон файлу.
Сегментована організація файлу припускає створення сегментированного файлу.
Сегментований файл - це файл, що складається з послідовного індексу, що містить адреси відповідних блоків даних.Сегментований файл називають також індексним файлом.
Така організація призначена для подолання недоліків доступу в послідовних файлах. Індекс представляє собою міру довільності доступу і засіб обслуговування додавання у файл.
Індекс будується як безліч блоків покажчиків сегментів (БУС) і може бути організований послідовним або безперервним способами. При безперервному підході максимальний розмір файлу вважається відомим (наприклад, один дисковий том) та відповідно з цим виділяється необхідна кількість індексних блоків. У разі послідовного підходу розмір файлу не обмежується. Проте пошук по послідовному індексом ставить ті ж проблеми, що і при пошуку в послідовному файлі. Кожен БУС в індексному файлі містить n елементів або покажчиків на блоки даних
і, можливо, покажчик на наступний індексний блок. Покажчик на дисковий блок повинен мати розмір, достатній для подання всього діапазону адрес на пристрої пам'яті.
Отримання записи з сегментированного файлу вимагає не більше двох звернень до диску. У першу чергу обчислюється адресу індексного блоку, і він зчитується в пам'ять. Потім з нього витягується адресу блоку даних, і той зчитується впам'ять. Включення нового запису в сегментований файл також не викликає великих труднощів.
2. ПОАД 3 Проектирование туристического маршрута Специальность 5В0421
3. Лекція 1 Актуальні тенденції організації іншомовної освіти в контексті євроінтеграції
4. .1 ББК 369 Укладачі Осипенкова І
5. это глобальная компьютерная сеть которая по протоколу TCP-IP объединяет сети различных регионов государств н
6. тема палатки рюкзаки репшнуры прусики карты карандаши секундомер
7. ТЕМА ЗАНЯТТЯ- Ручна і механічна обробка деталей виробів
8. отставание в области технического прогресса и производительности труда низкий по сравнению с мировыми ста
9. Влияние народного хозяйства на географическую оболочку
10. Психология личности 4 месяца 144 уч
11. модульний контроль з дисципліни Політологія Автор- ст
12. Ибо тайна беззакония уже в действии только не совершится до тех пор пока не будет взят от среды удержив
13. Реферат на тему Документальне оформлення й облік додаткового капіталу Виконал
14. Миграционные процессы в мире
15. Тема Правовой резким особо охраняемых природных территорий и объектов Задача 1
16. Жалпы медицина Курс- 1 Уа~ыты- 50 мин
17. Все люди от природы стремятся к знанию
18. на тему- Сприйняття ціни споживачем Виконала- студентка 4 курсу групи УМ02 Демиденко
19. РЕФЕРАТ дисертація на здобуття наукового ступеня кандидата біологічних наук
20. Новоя Зеландия