Ćwiczenia
5.1 Algorytm planowania przydziału procesora wyznacza porz+-dek wykonywania planowanych przez niego procesów. Maj+-c n procesów do zaplanowania dla jednego procesora, okreP:l, ile istnieje możliwych zaplanowań. Podaj wzór zależny od n.
5.2 Zdefiniuj różnicę między planowaniem wywłaszczaj+-cym a niewywłaszczaj+-cym. Uzasadnij, dlaczego w oP:rodku obliczeniowym czyste planowanie nie wywłaszczaj+-ce byłoby trudne do przyjęcia.
5.3 Rozważmy następuj+-cy zbiór procesów, których długoP:ci faz
procesora w milisekundach wynosz+- odpowiednio:
Proces | Czas trwania fazy | Priorytet |
P1 | 10 | 3 |
P2 | 1 | 1 |
P3 | 2 | 3 |
P4 | 1 | 4 |
P5 | 5 | 2 |
Zakładamy, że procesy nadeszły czasie O w kolejnoP:ci P1, P2, P3, P4, P5.
(a) Narysuj cztery diagramy Gantta ilustruj+-ce wykonanie tych zadań przy użyciu algorytmu FCFS, SJF, niewywłaszczaj+-cego algorytmu priorytetowego (mniejszy numer priorytetu oznacza wyższy priorytet) i algorytmu rotacyjnego (kwant czasu =1).
(b) Jaki będzie czas cyklu przetwarzania każdego procesu w każdym z algorytmów planowania wymienionych w częP:ci (a)?
(c) Jaki będzie czas oczekiwania każdego procesu w każdym z algorytmów planowania wymienionych w częP:ci (a)?
(d) Który z planistów z częP:ci (a) daje minimalny P:redni czas oczekiwania (dla ogółu procesów)?
5.4 Załóżmy, że poniższe procesy nadchodz+- do wykonania w podanych
chwilach. Każdy proces będzie działał przez czas podany w tabeli. Odpowiadaj+-c
na dalsze pytania, zastosuj planowanie niewywłaszczaj+-ce i podejmuj każd+-
decyzję na podstawie informacji, którymi będziesz dysponować wtedy, kiedy będzie
należało j+- podj+-ć.
Proces | Czas nadejP:cia | Czas fazy |
P1 | 0,0 | 8 |
P2 | 0,4 | 4 |
P3 | 1,0 | 1 |
(a) Ile wyniesie P:redni czas cyklu przetwarzania tych procesów przy planowaniu metod+- FCFS?
(b) Ile wyniesie P:redni czas cyklu przetwarzania tych procesów przy planowaniu według algorytmu SJF?
(c) Zakłada się, że algorytm SJF poprawi wydajnoP:ć, warto jednak zauważyć, że proces P\ zostanie wybrany w chwili O, ponieważ nie wiadomo, iż niebawem nadejd+- dwa krótsze procesy. Oblicz, ile wyniósłby czas P:redni cyklu przetwarzania, gdyby przez pierwsz+- jednostkę czasu pozostawiono procesor bezczynny i dopiero potem zastosowano planowanie SJF. Należy pamiętać, że procesy P1 i P2 będ+- czekały w okresie tej bezczynnoP:ci, zatem ich czas oczekiwania się zwiększy. Algorytm tego rodzaju mógłby się nazywać planowaniem na podstawie przyszłej wiedzy.
5.5 Rozważ wariant algorytmu planowania rotacyjnego, w którym pozycje w kolejce procesów gotowych s+- wskaĽnikami do bloków kontrolnych procesów.
(a) Co się stanie w wyniku wstawienia do kolejki procesów gotowych dwu wskaĽników do tego samego procesu?
(b) Jakie będ+- główne zalety i wady takiego postępowania?
(c) Jak można by zmienić podstawowy algorytm rotacyjny, aby uzyskać ten sam efekt bez podwajania wskaĽników?
5.6 Jakie s+- zalety dysponowania różnymi kwantami czasu na różnych poziomach kolejek w systemie z wielopoziomowym układem kolejek?
5.7 Rozważmy następuj+-cy wywłaszczaj+-cy, priorytetowy algorytm planowania, oparty na dynamicznych zmianach priorytetów. Większe numery priorytetów oznaczaj +- wyższe priorytety. Gdy proces czeka na procesor (jest w kolejce procesów gotowych, ale nie jest wykonywany), wówczas jego priorytet zmienia się w tempie a; kiedy zaP: jest wykonywany, wtedy jego priorytet zmienia się w tempie b. Wszystkie procesy w chwilach wchodzenia do kolejki procesów gotowych otrzymuj+- priorytet 0. WartoP:ci parametrów a i b można okreP:lać, otrzymuj+-c wiele różnych algorytmów planowania.
(a) Jaki algorytm powstaje, gdy b > a > O?
(b) Jaki algorytm powstaje, gdy a < b < O?
5.8 Wiele algorytmów planowania przydziału procesora podlega parametryzacji. Na przykład algorytm rotacyjny wymaga parametru okreP:laj+-cego kwant czasu. Wielopoziomowe kolejki ze sprzężeniem zwrotnym wymagaj+- parametrów definiuj+-cych liczbę kolejek, algorytm planowania dla każdej kolejki, kryteria przemieszczania procesów między kolejkami itd.
Algorytmy takie s+- więc w istocie zbiorami algorytmów (np. zbiór algorytmów rotacyjnych dla wszystkich kwantów czasu itp.) Jeden zbiór algorytmów może zawierać inny (np. algorytm FCFS jest algorytmem rotacyjnym o nieskończonym kwancie czasu). Czy i jakie relacje zachodz+- między następuj+-cymi parami zbiorów algorytmów:
(a) priorytetowymi i SJF,
(b) wielopoziomowymi kolejkami ze sprzężeniem zwrotnym i FCFS,
(c) priorytetowymi i FCFS,
(d) rotacyjnymi i SJF.
5.9 Załóżmy, że algorytm planowania (na poziomie krótkoterminowego planowania przydziału procesora) faworyzuje procesy, które zużyły najmniej czasu procesora w przeszłoP:ci. Dlaczego algorytm ten będzie faworyzował programy ograniczone przez wejP:cie — wyjP:cie oraz te spoP:ród programów ograniczonych przez procesor, które na razie nie cierpi+- nieustannie z powodu jego braku?
5.10 WyjaP:nij, czy i w jakim stopniu każdy z następuj+-cych algorytmów planowania przedkłada krótkie procesy ponad inne:
(a) FCFS,
(b) rotacyjny,
(c) wielopoziomowe kolejki ze sprzężeniami zwrotnymi.
<<< THE END >>>