Sprawozdanie z symulacji wybranych algorytmów przydzielania czasu procesora i stronnicowania

1. Opis sposobu testowania

• Symulacja 1

Dane potrzebne do wykonania programu są wczytywane z pliku dane_wejsciowe.txt. Dla algorytmu FCFS z zamkniętą pulą zadań istotny jest tylko czas trwania procesu. Procesy są wykonywane w kolejności „pierwszy wchodzi pierwszy wychodzi”. Dla algorytmu SJF z zamkniętą pulą zadań istotny jest także czas trwania procesu. Procesy są wykonywane w kolejności „najkrótszy wykonuje się pierwszy”. Aby dało się to zrealizować należało posortować tablicę za danymi rosnąco, używając sortowania bąbelkowego po czasie trwania fazy. Algorytm FCFS oraz SJF z otwartą pulą zadań działa podobnie jak FCFS oraz SJF z zamkniętą pulą zadań. Różnica polega na tym, że procesy będą pobierane z nieskończonej puli zadan.

• Symulacja 2

Dane potrzebne do wykonania programu są wczytywane z pliku dane_wejsciowe.txt. Pierwsza część programu działa jak w programie z symulacji 1 dla algorytmu SJF z zamkniętą pulą zadań. W drugiej części, z pliku pobierane są: czas trwania fazy oraz priorytet procesu. Dane są sortowane malejąco według priorytetu (7 – najwyższy priorytet, 0 – najniższy). Następnie zaczyna się wykonywanie procesów. Po wpisanej liczbie cykli priorytet wszystkich procesów zostaje zwiększony o 1. Dalej procesy się wykonują, po kolejnych cyklach znowu priorytety są postarzane itd. Gdy będą 2 procesy osiągną najwyższy priorytet, to najpierw wykonuje się ten o krótszym czasie trwania fazy.

• Symulacja 3

Program ten realizuje 3 główne algorytmy stronicowania:

• FIFO – kojarzy z każdą stroną jej czas wprowadzenia do pamięci. Kiedy trzeba zastąpić stronę, wtedy wybiera się stronę najstarszą.

• LRU – Oszacowuje najbliższą przyszłość, używana niedawnej przyszłości do zastępowania stron, wymienia stronę która nie była używana od najdłuższego czasu.

• Optymalny – cechuje się najniższym współczynnikiem braków stron
  ze wszystkich algorytmów. Zasada brzmi: „Zastąp tę stronę, która najdłużej nie będzie używana”.

1. Dane testowe

• Symulacja 1

Czas trwania fazy	Czas przybycia
9	3
1	7
3	1

• Symulacja 2

Numer procesu	Czas trwania fazy	Priorytet
0	1	5
1	9	6
2	3	7
3	6	3
4	8	1
5	6	3
6	4	4

• Symulacja 3

  • Liczba pustych ramek: 3

  • Długość sekwencji: 20

  • Sekwencja: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

1. Wyniki testów

• Symulacja 1

  • FCFS z zamknięta pulą zadań

• SJF z zamknięta pulą zadań

• Symulacja 2

  • SJF

• SJF z postarzaniem procesów

• Symulacja 3

  • FIFO

• LRU

• Optymalny

1. Opracowanie wyników testów

• Symulacja 1

Algorytm	Średni czas oczekiwania
FCFS z zamknięta pulą zadań	6.33333
SJF z zamknięta pulą zadań	1.66667

• Symulacja 2

Algorytm	Średni czas oczekiwania
SJF	10.7143
SJF z postarzaniem procesów	11.7143

• Symulacja 3

Algorytm	Liczba błędów strony
FIFO	15
LRU	12
Optymalny	9

1. Wnioski

• Można zauważyć, że algorytm FCFS ma gorsze parametry od SJF. Drugi z nich jest bardziej korzystny, gdyż w tej samej jednostce czasu możemy wykonać, więcej ale krótszych procesów.

• Algorytm SJF bez postarzania w trakcie testów, ma mniejszy czas średni oczekiwania, jednakże może w nim wystąpić głodzenie procesów, co może skutkować nie wykonaniem się jakiegoś z nich. Dlatego, na dłuższą metę, lepszy może się okazać algorytm z postarzaniem procesów, który gwarantuje wykonanie się wszystkich procesów w kolejce

• Jak widać w porównaniu, do stronicowania najlepiej wykorzystywać algorytm optymalny. Niestety nie jest on możliwy do zrealizowania w rzeczywistym systemie. Wtedy najlepszym wyborem jest algorytm LRU. Najgorszy w całym zestawieniu okazał się algorytm FIFO.