Kolejki procesów

W implementowany systemie występują dwie kolejki procesów: gotowych do uruchomienia (ang. runable) i uśpionych (ang. sleeping). Kolejki te są sformatowane jako statyczne tablice struktur PROCESS_QUEUE zawierających PID procesów, oraz dwa wskaźniki - na następny i poprzedni element. Dzięki temu rozwiązaniu nie ma potrzeby dynamicznego przydziału pamięci dla poszczególnych pozycji kolejki, przez co skraca się znacznie czas tworzenia i kasowania elementów kolejki oraz upraszcza budowę kodu przy zachowaniu części właściwości struktury jaką jest lista dwukierunkowa (przede wszystkim bardzo proste dodawanie i usuwanie elementów oraz brak potrzeby przeszukiwania tablicy w celu znalezienia niezajętego rekordu).

Kolejka procesów gotowych do uruchomienia zawiera wszystkie procesy, które mogą być w każdej chwili uruchomione przez program szeregujący. Kolejka ta ma charakter pętli - brak w niej określonego pierwszego i ostatniego elementu. Taka konstrukcja kolejki znacznie ułatwia budowę procedury szeregującej.

Proces dodaje się do kolejki procesów gotowych wywołując procedurę put_to_runable, której argumentem jest PID procesu umieszczonego w tablicy procesów, a usuwa z kolejki wywołując procedurę remove_from_runable.

Rys. Budowa kolejki procesów gotowych do uruchomienia

put_to_runable.c

remove_from_runable.c

Kolejka procesów uśpionych zawiera procesy, których wykonywanie zostało przerwane na określony interwał czasu przez wywołanie systemowe _sys_sleep. Kolejka ta różni się tym od kolejki procesów gotowych, że nie ma charakteru pętli - zarówno pierwszy jak i ostatni element kolejki wskazuje na dodatkowy element, nie biorący udziału w mechanizmach szeregowania.

Rys. Budowa kolejki procesów uśpionych

Proces jest dodawany do kolejki procesów uśpionych poprzez wywołanie procedury put_to_sleeping, której argumentem jest PID procesu umieszczonego w tablicy procesów, oraz wartość interwału czasowego na jaki ma zostać uśpiony proces. Procesy z kolejki usuwa się analogicznie - wywołując procedurę remove_from_sleeping.

put_to_sleeping.c

remove_from_sleeping.c

Kolejka procesów uśpionych jest tworzona według tzw. algorytmu delta - w kontekście usypianego procesu zapamiętywany jest nie cała wartość interwału czasowego, ale liczba będąca wynikiem różnicy zadanego interwału czasowego, a sumą interwałów czasowych wszystkich procesów już umieszczonych w kolejce. Nowy proces jest dodawany do kolejki w miejscu w którym jego względny interwał czasowy jest jak najmniejszy (ale większy od zera). Dzięki takiemu rozwiązaniu, podczas każdorazowej kontroli procesów uśpionych przez procedurę szeregującą, modyfikowany jest czas uśpienia tylko pierwszego procesu, co znacznie przyśpiesza działanie procedury.

Rys. Zasada działania algorytmu delta