Archiwa tagu: lottery scheduling

Szeregowanie loteryjne w systemie MINIX

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.

minix1

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

Czytaj dalej