Черги з пріоритетами

У реальних задачах іноді виникає необхідність у формуванні черг, відмінних від FІFO чи LІFO. Порядок вибірки елементів з таких черг визначається пріоритетами елементів. Пріоритет у загальному випадку може бути представлений значенням, що обчислюється, або на основі значень поля будь-якого елемента, або на основі зовнішніх факторів. Так, FІFO, і LІFO - черги трактуються як пріоритетні черги, у яких пріоритетом є час включення елемента в чергу.

Над пріоритетною чергою визначені наступні операції:

– включення елемента в кінець черги;

– включення елемента в чергу по пріоритету;

– виключення елемента з черги по пріоритету;

– виключення елемента з початку черги;

– визначення розміру черги;

– очищення черги.

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

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

Алгоритм пріоритетного включення передбачає так дії:

– якщо черга неповна, знайти згідно з пріоритетом таке місце в черзі, де треба поставити запит;

– звільнити місце для запита, для чого зсунути всі елементи від цього місця до кінця черги на один елемент;

– внести запит до черги.

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

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

Алгоритм пріоритетного виключення запиту такий:

– якщо черга непорожня, знайти за пріоритетом потрібний запит (цей пошук може бути тільки лінійним);

– прочитати запит;

–видалити запит з черги, для чого зрушити всі елементи черги від наступного до кінцевого на одну позицію ліворуч.

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

Черги в обчислювальних системах. Ідеальним прикладом кільцевої черги в обчислювальній системі є буфер клавіатури, що розташовується за адресами від 40:1E до 40:2D включно. За адресою 40:1A і 40:1C розташовуються покажчики на початок і кінець черги відповідно. Код натиснутої клавіші міститься (переривання 9H) у буфері клавіатури – у кінці черги. При введенні даних із клавіатури (переривання 16H) вибирається код клавіші з буфера – з початку черги.

Черга є одним із ключових понять у багатогозадачних операційних системах (Wіndows NT, Unіx, OS/2, ЄС та ін.). Ресурси обчислювальної системи (процесор, оперативна пам'ять, зовнішні пристрої і т.п.) використовуються всіма задачами, що одночасно виконуються в середовищі такої операційної системи. Оскільки багато видів ресурсів реально не допускають одночасного їхнього використання різними задачами, такі ресурси надаються задачам по черзі. Таким чином, задачі, що претендують на використання того чи іншого ресурсу, розміщуються в чергу до цього ресурсу. Ці черги звичайно пріоритетні, однак, досить часто застосовуються і FIFO-черги, тому що це єдина логічна організація черги, яка гарантовано не допускає постійного витиснення задачі більш пріоритетними. LIFO-черги звичайно використовуються операційними системами для обліку вільних ресурсів.

Також у сучасних операційних системах одним із засобів взаємодії між паралельно виконуваними задачами є черги повідомлень, названі також поштовими скриньками. Кожна задача має свою чергу – поштову скриньку, і всі повідомлення, що відправляються їй від інших задач, потрапляють у цю чергу. Задача-власник черги вибирає з неї повідомлення, причому може керувати порядком вибірки – FІFO, LІFO чи за пріоритетом.