Linux powstał jako rozszerzenie systemu Minix. Minix był bardzo prostym systemem operacyjnym przeznaczonym do celów edukacyjnych, natomiast Linux został pomyślany jako system do codziennego użytku -- bezpłatny system uniksowy.5 Linuksa przeniesiono na wiele platform sprzętowych i w chwili obecnej jest wykorzystywany przez instytucje i firmy, których nie stać na drogie systemy komercyjne.
Siłę Linuksa stanowi dostępność jego źródeł. Prawie od samego początku nad Linuksem pracowanli programiści z całego świata. Poświęcili oni swój czas i zdolności na tworzenie darmowego systemu. Duża część kodu została napisana przez informatyków zainteresowanych nie tylko programowaniem niskopoziomowym, ale także tym, by kod systemu był napisany przejrzyście i efektywnie. W Linuksie zastosowano praktycznie wszystkie nowoczesne koncepcje z dziedziny systemów operacyjnych i wiele ciekawych algorytmów: do zarządzania pamięcią, procesami, odwołaniami do dysku itp.
Celem niniejszej pracy była modyfikacja wybranych algorytmów Linuksa
i analiza różnic między wersjami oryginalnymi algorytmów a zmodyfikowanymi.
Część I jest poświęcona algorytmowi planowania przydziału procesora. Algorytm ten jest realizowany przez moduł szeregujący jądra. W pracy używane jest określenie planista, dla odróżnienia od pojęcia ładowalnych modułów Linuksa.
Planista Linuksa realizuje bardzo prosty algorytm. Ma on dużo cech algorytmu rotacyjnego (ang. round-robin). W szczególności w niewielkim stopniu uwzględnia różnice w charakterystyce wykorzystania procesora przez procesy zorientowane na wejście-wyjście i procesy zorientowane na obliczenia. Wpływa to negatywnie na wygodę pracy interakcyjnej w systemie obciążonym.
W dostępnych systemach operacyjnych można spotkać różne rozwiązania zagadnienia planowania przydziału procesora. W pracy podjęto próbę zaprogramowania w jądrze Linuksa planistów wzorowanych na algorytmach spotykanych w innych systemach operacyjnych: Uniksie (odmiany System V i BSD), Windows NT oraz QNX. Algorytmy te porównano następnie z algorytmem Linuksa.
Ważną częścią pracy był projekt implementacji algorytmów szeregowania w zewnętrznych, dynamicznie ładowanych modułach jądra Linuksa. Testowane algorytmy szeregowania zaimplementowano w takich właśnie modułach. Umożliwiło to zmianę strategii przydziału procesora bez potrzeby restartowania systemu.
W rozdziale 1 przedstawiono problem planowania przydziału procesora
dla procesów w systemach z jednym i wieloma procesorami. Przedstawiono
także metody porównywania algorytmów szeregowania procesów. W rozdziale
2 omówiono klasyczne algorytmy szeregowania. Plan eksperymentu opisano
w rozdziale 3. Rozdział 4 zawiera projekt i omówienie implementacji
algorytmu szeregowania dla Linuksa jako dynamicznie ładowanego modułu jądra
systemu. W rozdziale 5 przedstawiono sposób gromadzenia danych do
na potrzeby mierników wydajności algorytmów szeregowania. Rozdział 6
zawiera porównanie zaimplementowanych algorytmów.
Część II pracy dotyczy jednego z algorytmów związanych z zarządzaniem pamięcią.
Zagadnienie zarządzania pamięcią w Linuksie obejmuje wiele dziedzin, np. zarządzanie pamięcią dynamiczną w jądrze, pamięcią pomocniczą (pliki wymiany, stronicowanie), przestrzenią adresową procesu dla trybu użytkownika itp.
W pracy przeprowadzono analizę algorytmu wyszukiwania w drzewie AVL, użytego w Linuksie do zarządzania pamięcią procesów. Pamięć procesu składa się ze zbioru rozłącznych obszarów obejmujących pewne zakresy wirtualnej przestrzeni adresowej procesu. Opisy takich obszarów są zorganizowane w drzewo AVL. Struktury tej używa się do sprawdzania, czy dany adres należy do jakiegoś obszaru w przestrzeni adresowej procesu. Procesy mają w swej przestrzeni adresowej zwykle co najwyżej kilkadziesiąt obszarów, dlatego rozsądne wydaje się porównanie rozwiązania zastosowanego w Linuksie z rozwiązaniem prostszym: przechowywaniem informacji o obszarach adresowych na liście. Podjęto także próbę usprawnienia algorytmu Linuksa poprzez zastosowanie bufora.
Rozdział 7 zawiera wprowadzenie do problemu. Opisana jest przestrzeń
adresowa procesu i zastosowany algorytm. Rozdział zawiera krótką analizę
teoretyczną złożoności porównywanych algorytmów. W rozdziale 8 opisano
sposób porównywania algorytmów i konstrukcję testów. Zawiera także analizę
uzyskanych wyników.
Rozdział 9 zawiera podsumowanie pracy.
W dodatku A opisano narzędzie do wizualnej analizy algorytmów szeregowania.
W dodatku B opisano pliki znajdujące się na załączonej dyskietce.