Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Годинниковий алгоритм

Наявність біта використання сторінки є основою алгоритму другого шансу, або годинникового алгоритму (clock algorithm), — одного з найефективніших ре­ально застосовуваних алгоритмів.

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

Спочатку беруть сторінку, що найдовше перебуває у пам'яті (як для FIFO). Якщо її біт використання (R) дорівнює 0, то сторінку негайно замінюють, помі­щаючи на її місце нову. Якщо ж біт R дорівнює 1 (до сторінки зверталися), то його покладають рівним 0 (начебто ця сторінка тільки що завантажена у пам'ять), і прохід за списком триває далі, поки не буде знайдена сторінка з R = 0 (а доти біт R для всіх сторінок покладають рівним 0). Знайдену сторінку замінюють, після чого для нової сторінки задають R - 1 і наставляють на неї стрілку (рис. 9.6). У найгіршому випадку (якщо для всіх сторінок біт R дорівнює одиниці) почнеть­ся друге коло обходу списку (другий шанс) і буде замінена найстарша сторінка із тих, що були пройдені на першому колі. У цьому разі алгоритм зводиться до ал­горитму FIFO.

50. Організація заміщення сторінок

Списки сторінок

Організація заміщення сторінок у Ьіпих ґрунтується на їх буферизації. Організо­вують два списки сторінок: список активних (ае1іуе_1і8І) — містить сторінки, які використовують процеси і визначає робочий набір процесів; список неактивних (іпае1іуе_1і8і) — містить сторінки, які не так важливі для процесів (не використо­вуються в цей момент часу). Модифікована сторінка перебуває в списку неактив­них якийсь час, перш ніж її збережуть

на диску.

Нові сторінки додають у початок списку неактивних сторінок. За нестачі па­м'яті частину сторінок переміщують з кінця списку активних сторінок у початок списку неактивних, а потім починають вивільнення сторінок із кінця списку не­активних сторінок

Обробка відображених, змінених і заблокованих сторінок

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

• Сторінка може бути відображена в адресний простір процесу або кількох про­цесів. Щоб вивільнити сторінку, відображення спочатку потрібно вилучити для кожного такого процесу.

• Сторінка може бути заблокована у пам'яті (наприклад, у ній виділено буфер, який використовують для введення даних із пристрою). Під час обходу таку сторінку пропускають і роблять спробу знайти іншу сторінку для вивільнення. Ця сторінка може бути знову перевіренії у такому проході.

• Сторінка була модифікована, тому її спочатку треба записати на диск. Як тільки не відображену в адресний простір процесу модифіковану сторінку пе­реміщують із початку в кінець списку неактивних сторінок, система скидає її вміст на диск.

51. Поняття файла і файлової системи

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

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

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

Файлова система - це підсистема ОС, що підтримує організований набір файлів, здебільшого у конкретній ділянці дискового простору (логічну структуру); низькорівневі структури даних, використовувані для

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

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

До головних задач файлової системи можна віднести: організацію її логічної структури та її відображення на фізичну організацію розміщення даних на диску; підтримку програмного інтерфейсу файлової системи; забезпечення стійкості про­ти збоїв; забезпечення розподілу файлових ресурсів за умов багатозадачності та за­хисту даних від несанкціонованого доступу.

52. Організація інформації у файловій системі

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

Розділ — це логічний пристрій, що з погляду ОС функціонує як окремий диск. Такий пристрій може відповідати всьому фізичному диску (у цьому разі ка­жуть, що диск містить один розділ); найчастіше він відповідає частині диска (та­ку частину називають ще фізичним розділом); буває й так, що подібні логічні пристрої поєднують кілька фізичних розділів, що перебувають, можливо, на різ­них дисках (такі пристрої ще називають логічними томами — logical volumes).

Кожний розділ може мати свою файлову систему (і, можливо, використовува­тися різними ОС). Для поділу дискового простору на розділи використовують спеціальну утиліту, яку часто називають fdisk. Для генерації файлової системи на розділі потрібно використати операцію високорівневого форматування диска. У деяких ОС під томом (volume) розуміють розділ із встановленою на ньому файловою системою. Реалізація розділів дає змогу відокремити логічне відображення дискового простору від фізичного і підвищує гнучкість використання файлових систем.

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

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

Базовою ідеєю організації даних за допомогою каталогів є те, що вони можуть містити інші каталоги. Вкладені каталоги називають підкаталогами (subdirecto­ries). Таким чином формують дерево каталогів. Перший каталог, створений у фай­ловій системі, встановленій у розділі (корінь дерева каталогів), називають коре­невим каталогом (root directory).

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

53. Операції над файлами і каталогами

Підходи до використання файлів із процесу бувають такі: зі збереженням (stateful) і без збереження стану (stateless).

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

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

основні файлові операції, які звичайно надає операційна система для ви­користання у прикладних програмах.

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

Наступні виклики використовуватимуть цю структуру для доступу до файла.

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

• Створення файла. Ця операція спричиняє створення на диску нового файла нульової довжини. Після створення файл автоматично відкривають.

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

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

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

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

• Отримання і задания атрибутів файла.Ці дві операції дають змогу зчитувати поточні значення всіх або деяких атрибутів файла або задавати для них нові значення.

54. Файлові операції POSIX

Відкриття і створення файлів

Для відкриття файла використовують системний виклик ореп(), першим пара­метром якого є шлях до файла.

#і ndude <fcntl,h>

int open(const char ‘pathname. int flags[. mode_t mode]);

Виклик open() повертає цілочислове значення - файловий дескриптор.

Закриття файла

Файл закривають за допомогою системного виклику close(), що приймає файло­вий дескриптор:

closetfdl);

Читання і записування даних

Для читання даних із відкритого файла використовують системний виклик readO: ssizet re ad (i n t fdl, void *buf, size_t count);

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

char buf [ 1 00];

jj читають 100 байт з файлу в buf

int bytes_read = read(fdl. buf. sizeof (buf));

Для записування даних у відкритий файл через файловий дескриптор вико­ристовують системний виклик writeC):

ssize_t writetint fdl, const void *buf. size_t count);

Внаслідок цього виклику буде записано count байтів у файл через дескриптор fdl із пам'яті, на яку вказує buf. Виклик wri te() повертає обсяг записаних даних.

int fdl. bytes_written;

fdl - openC./myfile.txt", 0_RDWR10_CREAT. 00644); bytes_written = writeCfdl, "hello", sizeofC'hello");

Реалізація копіювання файлів

char buf[ 1024]; int bytes_read. intfile, outfile; jj відкриття вихідного файла для читання infile = openCinfile.txt". 0_RD0NLY); if Cinfile == -1) {

printf ("помилка під час відкриття файла\п"); exit(-l);

}

jj створення результуючого файла, перевірку помилок пропущено outfile - openC'ou tfile.txt", O_WR0NLY|O_CREAT|O_TRUNC. 0644); do {

jj читання даних із вихідного файла у буфер bytes_read - readtinfile. buf. s ize of (b uf));

// записування даних із буфера в результуючий файл if (bytes_read > 0) writeioutfile. buf, bytes_read):

} while (bytes_read > 0);

Переміщення покажчика поточної позиції у файлі

Кожному відкритому файлу відповідає покажчик позиції (зсув) усередині файла. Його можна пересувати за допомогою системного виклику 1 seek О:

off_t lseekiint fdl. off_t offset, int whence);

Параметр offset задає величину переміщення покажчика. Режим переміщен­ня задають параметром whence, який може набувати значень SEEKSET (абсолютне

переміщення від початку файла), SEEK_CUR (відносне переміщення від поточного місця покажчика позиції) і SEEK_END (переміщення від кінця файла).

// переміщення покажчика позиції на 100 байт від поточного місця Iseek (outfile. 100. SEEK_CUR);

// записування у файл

write (outfile. "hello". sizeofC'hello")):

Збирання інформації про атрибути файла

Для отримання інформації про атрибути файла (тобто про вміст його індексного дескриптора) використовують системний виклик stat().

#include <sys/stat.h>

int stattconst char ‘path. struct stat *attrs);

Першим параметром є шлях до файла, другим — структура, у яку записувати­муться атрибути внаслідок виклику.