Postawy teoretyczne, najbardziej obrazowo jak to możliwe

Szeregowanie loteryjne polega na tym, aby następny proces do uruchomienia niejako ‚wylosować’, jednak z zachowaniem możliwości ustalania priorytetu. W tym opisie priorytet będzie zależał od „ilości losów”.

Każdy proces powinien posiadać pewną liczbę losów, na potrzeby zadania przyjmiemy od 1 do 20. Liczbę losów nadaje się mu przy jego utworzeniu i będzie ona zmieniana wyłącznie na żądanie użytkownika. Liczba losów jest na poniższym obrazku tożsama z szerokością prostokąta.

Kiedy ma nastąpić wybranie nowego procesu do wykonania – losujemy liczbę od 1 do sumy losów wszystkich gotowych procesów. W tym wypadku od 1 do 11.

Następnie patrzymy na którym procesie wypadła nasza liczba i ten proces zostanie uruchomiony. Kiedy zajdzie potrzeba wybrania nowego procesu – należy powtórzyć tą procedurę.

Liczby 1,2,3,4,5 wypadają na procesie #1
Liczby 6,7,8 wypadają na procesie #2
Liczby 9,10 na procesie #3
A 11 na procesie #4

Zakładając, że wylosowanie każdej liczby jest równo prawdopodobne – proces 1 ma aż 5/11 szans na bycie wylosowanym, więc po wielu losowaniach okaże się, że dostał znacznie więcej czasu procesora niż proces 4 którego szanse były 1/11. Wychodzi na to, że będzie to 5-krotna różnica.

Dla przykładu załóżmy, że wylosowaną liczbą jest 8. Spowoduje to, że teraz uruchomionym procesem będzie proces #2. Na tym kończy się operacja wyboru procesu. Wylosowaliśmy, ustawiliśmy, gotowe.

Implementacja

Założenia implementacji

Do systemu należy dołożyć wywołanie umożliwiające zmianę ilości losów procesu oraz ich odczyt. Na potrzeby implementacji funkcje nazwiemy setlot i getlot.

Szeregowaniu loteryjnemu podlegać będą jedynie procesy z grupy USER.

Dodatkowe zmienne

Niewątpliwe należy gdzieś zapisać liczbę losów każdego procesu. Myślę, że wybór miejsca będzie oczywisty – struktura proc. Przyjęliśmy, że liczba losów procesu może wahać się od 1 do 20. Zdecydowanie dobrym pomysłem będzie wykorzystanie zmiennej typu unsigned char. Na potrzeby zadania dodatkową wartość w strukturze nazwiemy num_tickets i umieścimy ją w pliku /usr/src/kernel/proc.h

Wyprzedzając jeszcze zagadnienie optymalizacji rozwiązania – powiem, że powinniśmy gdzieś przechowywać sumę losów procesów gotowych do wykonania. Ta liczba nie jest związana z procesem, a z całym narzędziem szeregującym, stąd warto umieścić ją w pliku w którym będziemy z niej najwięcej korzystać – /usr/src/kernel/proc.c. Wybierając typ, trzeba rozważyć minimalną i maksymalną wartość tej zmiennej. Minimum osiągniemy przy braku procesów (wtedy suma będzie równa 0), maksimum, gdy wszystkie procesy będą gotowe z maksymalną liczbą losów. Stała NR_PROCS podpowiada, że nie można uruchomić więcej procesów użytkownika niż 32. Stąd 20 * 32 = 640 – co spokojnie powinniśmy zamknąć w zmiennej unsigned short. Zmienną opisującą sumę losów procesów gotowych do wykonania nazwijmy total_tickets.

Optymalizacja

No właśnie. W całym tym rozwiązaniu jest kilka pułapek, które może nie spowodują, że nasz minix zacznie chodzić jak Windows Vista, ale na pewno ujmą mu trochę piękna i szyku.

Przechowywana globalnie suma losów procesów gotowych

Gdyby nie ona, przy każdym wyborze procesu konieczne byłoby przejrzenie całej listy procesów gotowych. Jest to prawdopodobnie strata czasu, szczególnie, że proces staje się gotowy lub niegotowy tylko przez funkcje ready i unready. W nich należy więc zawrzeć dodawanie i odejmowanie ilości losów procesu od globalnej zmiennej total_tickets. Jest jeszcze jedno miejsce, gdzie coś się dzieje. Jest to setlot. W tej funkcji należy sprawdzić, czy proces jest gotowy (bo jeśli nie jest, to jego liczba losów nie jest w żaden sposób na liście) i jeśli tak – dodać / odjąć różnicę losów. Jeśli proces miał ich 10, a teraz ma mieć 8 i do tego jest gotowy – należy odjąć 2 losy od listy. Łatwym rozwiązaniem może też okazać się wywołanie unready, zmiana ilości losów, ready.

Kolejność procesów na liście gotowych

Kiedy zajdzie potrzeba wybrania procesu – musimy „przelecieć” (jakkolwiek okrutnie to brzmi) listę procesów, aby znaleźć ten wybrany. To, czy procesy są posortowane, czy nie – w żaden sposób nie wpłynie na prawdopodobieństwo wylosowania któregokolwiek z nich. Wpływa to jedna na czas wykonania wyszukiwania. Minix to nie życie, tutaj chcemy przelecieć w jak najkrótszym czasie.

Procesy na liście powinny być ułożone według nierosnącej liczy losów. Dlaczego? Załóżmy, że mamy procesy z takimi liczbami losów: 10, 9, 8, 7, 1, 1, 1, 1. Wylosowaliśmy liczbę 15. Przykładowy algorytm wyszukujący proces – sprawdzi czy liczba wylosowana jest mniejsza bądź równa ilości losów procesu – jeśli tak, wybierze go, jeśli nie – odejmie jego ilość od wylosowanej liczby i skoczy na następny oraz zacznie od początku.

Wyobraźmy sobie teraz układ najgorszy – procesy są w kolejności 1, 1, 1, 1, 7, 8, 9, 10. Liczba wylosowana to 15. Sprawdzenie -> Odjęcie -> Skok, Sprawdzenie -> Odjęcie -> Skok, itp… Musimy przeskoczyć 1, 1, 1, 1, 7, aby ostatecznie wybrać 8. Razem należało wykonać 5 skoków.

A teraz weźmy układ posortowany. Wyszukiwanie zatrzyma się już na drugiej liczbie: 10, stop na 9. Nie jest to żaden przypadek szczególny. W przypadku małej ilości procesów, czy małej liczbie wylosowanej – różnica wydajności będzie niewielka. Wraz ze wzrostem tych liczb – będzie rosła.

Kiedy zadbać o porządek na liście? Wyłącznie przy dodawaniu / usuwaniu / modyfikowaniu rekordu na liście – w funkcjach ready, unready, setlot.

Implementacja w jądrze:

Zajmiemy się teraz implementacją w/w algorytmu w jądrze systemu minix, plik po pliku.

Będziemy potrzebowali funkcji dostępnych z poziomu programu użytkownika służących do pobrania i ustawienia ilości losów dla procesu. Te funkcje obsługuje kernel, do którego jednak, jako program, nie mamy dostępu. W związku z tym te wywołania muszą być obsłużone pośrednio poprzez moduł MM lub FS. Postawiłem na MM.

/usr/src/kernel/proto.h

Aby ułatwić sobie życie stworzymy sobie funkcję która sprawdzi nam, czy zadany proces znajduje się na liście gotowych. W pliku proto.h dodamy jej prototyp (deklarację).

Ponieważ będziemy implementować ją w pliku proc.c – prototyp dodajemy w wyznaczonej komentarzem sekcji (jest ona tylko dla zachowania porządku).

_PROTOTYPE( void printer_task, (void) );
/* proc.c */
_PROTOTYPE( unsigned short is_proc_ready, (struct proc * rp) );
_PROTOTYPE( void interrupt, (int task) );

/usr/src/kernel/proc.h

W tym pliku dodajemy do struktury procesu proc aktualną liczbę losów. Korzystamy z ustalonego wcześniej typu.

int p_sendto;

unsigned char num_tickets; /* liczba ticketów w naszej loterii */
struct proc *p_nextready; /* pointer to next ready process */

/usr/src/kernel/main.c

Ten plik niejako tworzy i przygotowuje proces INIT. Jest to jedyny proces, który nie powstał przez FORK – z tego powodu musimy osobno ustalić mu numer losów. Ważne, aby nie dodawać tego na dole, tam gdzie ustalany jest PID, bo w tym miejscu ten proces przeszedł już przez ready. Listę jego losów musimy ustalić przed pętlą w której wywoływane jest ready.

*/
proc[NR_TASKS+INIT_PROC_NR].num_tickets = 1; /* Init się nie forkuje - manualnie ustawiamy mu liczbę losów na 1 */
/* Task stacks. */
ktsb = (reg_t) t_stack;

/usr/include/minix/com.h

W tym pliku dodajemy numery wowołań, które będzie obsługiwało samo jądro.

Wpisy dodajemy w okolicy końca wpisów SYS_

# define SYS_GETLOT 22 /* fcn code for sys_getlot(proc) */
# define SYS_SETLOT 23 /* fcn code for sys_setlot(proc, newlot) */

/usr/src/kernel/system.c

W tym pliku dodamy prototypy właściwych już wywołań realizowanych przez jądro. Będą to getlot i setlot. Pomocnikiem będzie funkcja wyszukująca proces w tablicy na podstawie pidu i zwracająca wskazanie na niego.

 FORWARD _PROTOTYPE( int do_findproc, (message *m_ptr) );
 _PROTOTYPE( struct proc * find_user_proc_by_pid, (pid_t) );
 FORWARD _PROTOTYPE( int do_getlot, (message *m_ptr) );
 FORWARD _PROTOTYPE( int do_setlot, (message *m_ptr) );
 
 /*===========================================================================*

Tutaj zamiast tabeli, tak jak w modułach MM i FS stosowana jest lista case’ów. Dodajemy tam swoje:

case SYS_FINDPROC: r = do_findproc(&m); break;
case SYS_GETLOT: r = do_getlot(&m); break;
case SYS_SETLOT: r = do_setlot(&m); break;
default: r = E_BAD_FCN;

Następnie dodajemy (na przykład na końcu pliku) obsługę wywołań. Nie będę wklejał tu całego kodu. Jest on dobrze skomentowany w pliku: https://github.com/peku33/minix203-lottery-scheduling/blob/master/usr/src/kernel/system.c#L1031

W tym pliku także zadbamy o ustalanie liczby losów dla nowych procesów. W systemie minix nowy proces może powstać wyłącznie poprzez wywołanie FORK. Znajdujemy więc kod obsługi wywołania i dodajemy w nim nadanie procesowi ustalonej ilości losów.

rpc->child_stime = 0;

rpc->num_tickets = 1; /* initial number of tickets for lottery scheduling */

return(OK);

/usr/src/kernel/proc.c

Czyli właściwa implementacja.

W tym pliku przechowujemy sumę losów procesów gotowych – ustaloną wcześniej jako total_tickets. Jest ona zadeklarowana poprzez:

PRIVATE unsigned char switching; /* nonzero to inhibit interrupt() */
unsigned short total_tickets = 0; /* Na początku nie ma żadnego procesu, więc suma ticketów jest równa 0 */

FORWARD _PROTOTYPE( int mini_send, (struct proc *caller_ptr, int dest,
message *m_ptr) );

Tu dodana jest definicja funkcji sprawdzającej gotowość procesu: https://github.com/peku33/minix203-lottery-scheduling/blob/master/usr/src/kernel/proc.c#L49

oraz zmodyfikowane wywołania:

Teraz zajmiemy się wywołaniami dostępnymi z poziomu użytkownika poprzez moduły.

/usr/include/minix/callnr.h

W pliku /usr/include/minix/callnr.h który jest listą stałych których potem używamy w programie – zmieniamy liczbę dostępnych wywołań o 2 na plus.

#define NCALLS 80 /* number of system calls allowed */

#define EXIT 1
#define FORK 2
#define READ 3

i dodajemy je na dole. u mnie nazywają się GETLOT oraz SETLOT.

#define REBOOT 76
#define SVRCTL 77

#define GETLOT 78
#define SETLOT 79

/usr/src/fs/table.c

Musimy uzupełnić tabelę modułu FS o dwa wywołania. Nie są one jednak implementowane w tym module, więc zamiast nazw funkcji podajemy puste odwołania – no_sys.

Na końcu tabeli dodajemy:

no_sys, /* 76 = REBOOT */
do_svrctl, /* 77 = SVRCTL */

no_sys, /* 78 = unused */
no_sys, /* 79 = unued */

/usr/src/mm/table.c

Te funkcje są jednak obsługiwane przez MM – tu dodajemy rozwiązania ich nazw (że wywołanie numer 78 <czyli 78 pozycja w tabeli> to getlot, a 79 setlot)

do_reboot, /* 76 = reboot */
do_svrctl, /* 77 = svrctl */

do_getlot, /* 78 = getlot */
do_setlot, /* 79 = setlot */

/usr/src/mm/proto.h

W tym pliku dodajemy prototypy funkcji do_getlot oraz do_setlot. Są / będą one w pliku main.c, więc dodajemy je do odpowiedniej sekcji.

/* main.c */
_PROTOTYPE( void main, (void) );
_PROTOTYPE( int do_getlot, (void) );
_PROTOTYPE( int do_setlot, (void) );

/usr/src/mm/main.c

W reszcie finalna implementacja tych funkcji. Wszystko co mają one zrobić, to odwołać się prosto do jądra i zawołać przygotowane wcześniej przez nie funkcje systemowe. Doklejamy do na przykład na końcu.

/*
Funkcja do_getlot musi być wywołana bezpośrednio przez jądro
@kernel/system.c
*/
PUBLIC int do_getlot()
{
        message m = mm_in;
        return _taskcall(SYSTASK, SYS_GETLOT, &m);
}
/*
Funkcja do_setlot musi być wywołana bezpośrednio przez jądro
@kernel/system.c
*/
PUBLIC int do_setlot()
{
        message m = mm_in;
        return _taskcall(SYSTASK, SYS_SETLOT, &m);
}

Implementacja publicznego interfejsu

Aby użytkownik końcowy, zamiast wykorzystywać jakieś skomplikowane syscalle czy inne takie – mógł łatwo napisać sobie program – dodajemy nowy plik .h do /usr/include/ który użytkownik będzie mógł sobie dołączyć poprzez #include.

/usr/include/lottery.h

Ten plik definiuje publicznie dostępne funkcje getlot oraz setlot.

Komentarze, zwracane wartości itp są opisane w środku.

Aby dołączyć plik w dowolnym programie – wystarczy wykonać

#include <lottery.h>

Dodaje nam on w programie dodatkowe funkcje:

int getlot(pid_t pid);
int setlot(pid_t pid, unsigned short new_lot);

Implementacja testowania:

Testowanie składa się z dwóch części.

/usr/sched_test/test.sh

Skrypt w shellu który równocześnie uruchomi dwie instancje programu test, odpowiednio z priorytetami 1 oraz 10 oraz zmierzy im czas.

/usr/sched_test/test.c

Program test którego celem jest:

Uruchomić się
Nadać sobie priorytet zadany przez parametr uruchomieniowy
Wykonać dużo ciężkich i długich operacji, co jaki czas informując o postępach.
Zakończyć żywot

Program uruchamiamy poprzez ./test PRIORYTET

Cały projekt na GitHubie:

https://github.com/peku33/minix203-lottery-scheduling

blog.peku33.net

Blog peku33. O programowaniu, o życiu.

Szeregowanie loteryjne w systemie MINIX