Egzamin Sysopy2002 2

Szczecin, dn. 20 czerwca 2002 r.

Kierunek INFORMATYKA - studia magisterskie dzienne PODSTAWY SYSTEMÓW OPERACYJNYCH - Grupa A

Imię i nazwisko:........................................................................ Ocena:

Pytanie I

Załóżmy, że w przedstawionej poniżej propozycji Petcrsona dotyczącej rozwiązania sekcji krytycznej dia dwóch procesów zmodyfikowaliśmy pętlę while Mod\Tikacja ta polega na podzieleniu pętli na dwa fragmenty (przejmij, ż.c każda operacje pobierania, zapisywania i testowania języka C jest niepodzielna) Uwaga CS - sekcja krytyczna. NCS - sekcja niekrytyczna

shared int turn, state[2);

Init { turn= (011) , state = (0,0) }

Rozwiązanie Petersona

Proces PI wykonuje:    I Proces P2 wykonuje:

while(l) {

state[0] * 1; turn « 0;

wbile( !turn && state(l] ); CS () ;

state[0] = 0;

NON_CS();

}

while(l) {

state[l] * 1; turn = 1;

while ( turn && statefO] ); CS () ;

state[1] ⁵⁵ 0;

NON_CS () ;

}

Proces P2 wykonuje:

while(1)    {

state(l) = 1; turn * 1; while ( turn ); while ( state(0) ) ;

CS () ;

state[l) = 0;

NON_CS() ;

)

Propozycja modyfikacji Proces PI wykonuje:

while(l) {

state(0] = 1; turn = 0; while (    !turn );

while( state[1] );

CS () ;

state[0] * 0; NON_CS () ;

}

Jeśli proponow ane rozwiązanie jest poprawne, to uzasadnij dlaczego Jeśli jest niepoprawne, to dokładnie wyjaśnij, co jest źle i podaj sekwencje wykonań procesów PO i Pl_: która ilustruje błąd.

Pytanie 2 (grafy alokacji zasobów)

□    Narysuj grafy, które ilustrują każdy z następujących przypadków: (a) cykl. stan bezpieczny, (b) cykl. stan zagrożenia, (c) cykl. blokada (d) trzy cykle, stan bezpieczny.

□    • podaj cztery warunki konieczne powstania blokady i wyjaśnij jak nic dopuścić do spełnienia każdego z ty ch warunków. Uwaga¹

Proszę nie definiować warunków, a jedynie je wymienić.

□    Który z przedstawionych niżej elementów najbardziej wpływa na powstanie blokady i dlaczego (a) liczba procesów, (b) liczba typów' zasobów, (c) liczba egzemplarzy każdego typu zasobu, (d) porządek, w jakim zasoby są przy dzielane?

Pytanie 3

Załóżmy, że dany jest początkowy stan zasobów w systemie oraz przyjmijmy, że w celu umknięcia blokady stosowany jest algorytm Bankiera.. Uzupełnij przedstawiona poniżej tabelę i odpowiedz na postawione pytania

Początkowy stan zasobów (2,3,2)

Proces

0

1

2

3

| Max |

I-------1

10 12 1 ! 1 2 0 | |2 0 2| |231|

Przydz ielone

| Potrzebne

Dostępne A=(x, y, z): określ wartości

0 0 0 0 10 0 0 1 10 0

? ? ? I ??? I ??? I ???

(a)    System znajduje się w stanie bezpiecznym -    podaj bezpieczną sekwencję procesów

(b)    Załóżmy, żc proces PO zamawia (1.0.0).    Co    robi    system operacyjny? Przedstaw    swoje analizy

(c)    Zalóż.TTW. że proces PO zamawia (0.0.2)    Co robi    system operacyjny'' Przedstaw    swoje analizy

(d)    Załóżmy, żc proces P3 zamawia (0.1.0).    Co    robi    system operacyjny^-' Przedstaw    swoje analizy

(e) Zalóżmv. że proces PO zamawia (0.1.0) Co robi system operacyjny? Przedstaw swoje analizy

Uwaga! Każde z powy ższy ch py lan jest niezależne i rozpoczy na się zawsze od stanu, który został określony na początku zadania

Pytanie 4    ,

Rozważ, następujący ciąg odniesień do adresów logicznych pochodzący z 460-bajtowego programu 10. 11. 104, 170. 73. 309. 185. 245. 246. 434. 458. 364*

(a)    Podaj ciąg odniesień do stron zakładając, że rozmiar strony wynosi 100 bajtów.

(b)    Znajdź, liczbę błędów strony dla ciągu odniesień z (a) przy założeniu, że programowi przy dzielono 200 bajtów pamięci operacyjnej, a do zastępowania stron stosuje się algorytm F1FO.

(c)    Oblicz, jaka byłaby liczba błędów stron, gdyby zastosowano tu algory tm LRU.

(d)    Określ, ile wynosiłaby liczba błędów stron przy zastosow aniu algory tmu opty malnego

Pytanie 5

Sy stem posiada 28-bitowe adresy wirtualne oraz. 64 megabajty pamięci Fizycznej. Wielkość strony i ramki wynoszą 8 kB (kilobajty ) Aktualnie wykonywany proces ma wielkość I MB Następna dostępna ramka ma numer 100. tzn. w przypadku powstania następnego błędu braku strony system operacyjny załaduje niezbędna stronę do ramki numer 100 Poniż.ej przedstawiono część tabeli stron (sy stem jest z adresowaniem bajtów. 1KB=2¹⁰. I MB=2²⁰)

indeks	ramka	bit poprawności
0	10	1
1	1000	0
2	300	1
3	6	1
4	3	0
5	5	0
6	2	0
7	0	0
8	3	1

Odpowiedz, na następujące py tania:

□    Ile wierszy występuje w całej tabeli stron rozważanego procesu'’ Ilu bitowe jest pole wystarczające do opisania numeru ramki?

U    Załóżmy, że każdy wiersz można zapisać na 4 bajtach i tabela stron w całości przechowyw ana jest w pamięci operacy jnej. Jaka

jest wielkość (w bajtach) tej pamięci?

Aktualnie wykonywane proces odwołuje się do pamięci. Opisz, co się stanie po każdy m odwołaniu oraz podaj wartość żądanego adresu fizycznego lub wirtualnego. Przedstaw swoje obliczenia (zakładamy, że bajty pamięci adresowane są od zera).

□    Proces pisze pod    wirtualny adres    8198. Podaj odpowiadający mu adres fizyczny.

□    Proces pisze pod    wirtualny adres    21000. Podaj odpowiadający    mu adres fizy czny.

□    Proces pisze pod    wirtualny adres    25000. Podaj odpowiadający    mu adres wirtualny .

□    Jeśli wystąpi wewnętrzna fragmentacja. to podaj ile bajtów'    zostanie utraconych Jeśli fragmentacja nie wystąpi, to wyjaśnij

dlaczego’

Py tanie 6

•r

Załóżmy, że mamy plik. który początkowo składa się ze 100 bloków. Załóżmy', że blok kontrolny pliku (i blok indeksowy w przypadku przy działu indeksowego) znajduje się już w pamięci operacyjnej Oblicz, ile dyskowych operacji wejścia-wyjścia wy maga każda ze strategii przydziału: ciągłą, listowa i indeksowa (jednopoziomowa), jeśli dla jednego bloku trzeba wykonać każdą z jioniższy ch operacji. W przy padku przydziału ciągłego zakładamy, że nie ma więcej miejsca do rozrastania się pliku na początku, ale jest wolne miejsce na jego końcu. Zakładamy też. że blok informacji, która ma zostać dodana do pliku, jest przechowywana w pamięci operacy jnej: (a) blok ma być dodany na początku pliku, (b) blok ma być dodany w środku pliku, (c) blok ma być dodany na końcu, (d) blok ma być usunięty z początku pliku, (e) blok ma być usunięty ze środka pliku. (0 blok ma być usunięty z. końca pliku

Py tanie 7 (Unix)

Wyjaśnij, jaki będzie wynik działania niniejszego programu? Dokładniej, co zobaczy my na ekranie po skompilowaniu i uruchomieniu programu

łinclude <stdio.h>

#define MAXSTRS 5

int rnain(void)

<

int entr;

FILE *pipe_fp;

char *strings(MAXSTRS] = { "echo",

"bravo", "alpha", "charlie", "delta"};

if (( pipe_fp « popen("sort", "w")) *= NULL)

(

perror("popen”); exit(1);

)

for(cntr=0; cntr<MAXSTRS; entr+t)

(

fputs(strings[entr], pipe_fp); fputc('\n' , pipę fp) ;