Egzamin PSO 22.06.2005
1. Zakładamy, że system składa się z dwóch procesów P1 i P2, współdzielących cztery jednostki zasobu typu R. Każdy z procesów może żądać co najwyżej 3 jednostki tego zasobu. Procesy mogą przyjmować stany:
Nie posiada R,
Nie posiadać R, żąda R,
Posiada R,
Posiada R, żąda 2R,
Posiada 2R,
Posiada 2R, żąda 3R,
Posiada 3R.
Możliwe są przejścia między stanami:
- 0 do 1, 2 lub 3 oraz 4 do 5 poprzez żądanie jednej jednostki zasobu,
- 1 do 2, 3 lub 4, 5 do 6 poprzez uzyskanie jednej jednostki zasobu,
- 6 do 4, 4 do 2, 2 do 0 poprzez zwolnienie jednej jednostki zasobu.
Sij oznacza stan systemu, i to stan P1, j P2. Oceń stany systemu w tabeli:
Stan |
bezpieczny |
niebezpieczny |
zakleszczenia |
nieosiągalny |
S32 |
|
|
|
|
S55 |
|
|
|
|
S44 |
|
|
|
|
S36 |
|
|
|
|
S54 |
|
|
|
|
S51 |
|
|
|
|
W schemacie pamięci wirtualnej ze stronicowaniem występują 4 ramki pamięci oraz 8 stron logicznej przestrzeni adresowej. Każda o wielkości 512 (01000 ósemkowo) bajtów. Załóżmy, że dla pewnego procesu związana z nim tabela stron ma postać B:
nr strony |
nr ramki |
bit ważności |
0 |
3 |
1 |
1 |
1 |
1 |
2 |
|
0 |
3 |
|
0 |
4 |
2 |
1 |
5 |
|
0 |
6 |
0 |
1 |
7 |
|
0 |
Na podstawie tabeli podać adresy fizyczne odpowiadające poniższym adresom logicznym:
512 (0100)
24 (00030)
3136 (06100)
2688 (05200)
Załóżmy, że w pewnym systemie ze stronicowaniem na żądanie, strona ma rozmiar 4KB, adres długość 24 bity, pamięć operacyjna składa się z 3 ramek i jest początkowo pusta, algorytmem jest IRU. Wygenerowano ciąg adresów wirtualnych, który w zapisie szesnastkowym wygląda następująco:
R:00AFA00 W:01D001 R:028202 W:014EA0 R:0280AA W:01DF00
R:0320AF W:03C0AF R:01DE30 W:00A44A
R oznacza operacje czytania ze strony, W zapisu.
a) Ile błędów braku strony zostanie wygenerowanych podczas wykonania tego ciągu odwołań?
b) Ile dyskowych operacji odczytu i ile dyskowych operacji zapisu zostanie wykonanych (zakładamy, że wszystko odbywa się synchronicznie)?
Załóżmy, dla uproszczenia, że wszystkie żądania odczytu i zapisu dyskowego wygenerowane podczas realizacji tego ciągu odwołań czekają w kolejce na obsługę i są obsługiwane zgodnie z zasadą kolejki prostej. Ponadto zakładamy, że strony programu są umieszczone w pliku wymiany w kolejnych blokach fizycznych (jedna strona w jednym bloku) na kolejnych ścieżkach, po 20 stron na ścieżce, jak na załączonym rysunku:
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
Zakładamy. Że transmisja jednego bloku trwa 5 ms, przesunięcie głowicy między dwoma kolejnymi ścieżkami 10 ms, głowica inicjalnie znajduje się na (0,0).
c) Ile łącznie czasu zajmie wykonanie operacji dyskowych z punktu b).
Rozważ następujący ciąg odniesień do adresów logicznych pochodzących z 460 bajtowego programu - 10, 11, 104, 170, 73, 309, 185, 245, 246, 434, 458, 364.
Podaj ciąg odniesień do stron, zakładając, że rozmiar strony wynosi 100 bajtów,
Znajdź liczbę błędów strony dla ciągu odniesień z a)przy założeniu, że programowi przydzielono 200 bajtów pamięci operacyjnej i zastosowano algorytm FIFO.
Oblicz, jaka byłaby liczba błędów stron, gdyby zastosowano tu algorytm IRU.
Oblicz, ile wynosiła by liczba błędów stron przy zastosowaniu algorytmu optymalnego.
Do obsłużenia zostaje zgłoszone 5 procesów (P0-P4).
Proces |
Czas nadejścia |
Czas trwania fazy |
Priorytet |
P0 |
0 |
4 |
2 |
P1 |
1 |
12 |
3 |
P2 |
4 |
6 |
3 |
P3 |
7 |
20 |
1 |
P4 |
8 |
3 |
2 |
Narysować diagram Ganta dla metody FCFS, SJF i priorytetowej wywłaszczającej. Dla każdej z tych metod określić średni czas oczekiwania. Mniejszy numer priorytetu oznacza wyższy priorytet.
Co się wyświetli (postać wykonywana w fwr)?
#include<studio.h>
#define MAXSTRS 5
int main(void)
{
FILE *fp;
char *cmdString=”cat pipopen.c”;
char buf[80];
if((fp=popen(cmdString,”r”))==NULL)
{
perror(“popen”);
exit(1);
}
while((fgets(buf,80,fp))!=NULL)
printf(“%s”,buf);
pclose(fp);
exit(0);
return(0);
}
Rozważmy następujący ciąg instrukcji, fwr jest programem z pytania 6:
mkfifo -m 600 fifoN
cat < fifoN | cut -c1-5 &
./fwr > fifoN
Co zobaczymy na ekranie? (Opisowo nie ciąg znaków)
Pytania testowe brzmiały:
Stan zombie NET.
W i-węźle na dysku zapisywana jest.
U-obszar zawiera.
Jakie warunki muszą być spełnione, aby zwykły użytkownik mógł uruchomić swój skrypt shell'owy.
Zapis do potoku ma następujące cechy.