Кільцевий буфер

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

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

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

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

Виконавець може випереджати споживача, тоді з часом він заповнить увесь буфер. У такому випадку процесу-виконавцю необхідно зачекати доки процес-споживач звільнить хоча б один або декілька елементів масиву. Для очікування можна використати монітор.

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

Спулінг – буферизація вхідних та вихідних потоків.

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

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

Конвеєр (програмний канал)

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

Конвеєри це не файли на диску, а буферна пам’ять, яка працює за принципом FIFO, тобто за принципом звичайної черги. Конвеєр має певний розмір і працює як циклічний кільцевий) буфер. Він складається з ділянки пам’яті та двох покажчиків head – вказує на перший елемент даних, tail – на останній.

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

 

Рис. __

 

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

Черги повідомлень (Queue)

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

Черга та конвеєр мають наступні відмінності:

1) Черги повідомлень дають можливість реалізувати декілька дисциплін обробки:

FIFO – записано першим, прочитано першим;

LIFO – записано останнім, прочитано першим;

пріоритетний – повідомлення вичитуються з врахуванням їх пріоритетів;

довільний – повідомлення можна вичитувати в довільному порядку.

Канал забезпечує тільки дисципліну FIFO.

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

3) У чергах знаходяться не самі повідомлення, тільки їх адреси в пам’яті та розмір. Ця інформація розміщується в загальному сегменті пам’яті доступній всім задачам, що спілкуються за допомогою черги.

Кожний процес, який використовує чергу, повинен попередньо отримати дозвіл на використання спільного сегменту пам’яті. Черга – це також системний ресурс.

Під час читання з черги задача-приймач користується наступною інформацією:

- ідентифікатором процесу (PID) передавача повідомлення;

- адресою та довжиною повідомлення;

- ознакою очікування, коли черга порожня;

- пріоритетом повідомлення;

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