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