Ć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 >>>