1)

Algorytm Dekkera – pierwszy algorytm poprawnie rozwiązujący problem wzajemnego wykluczania się równolegle działających procesów. Tylko jeden z nich może w danej chwili wykonywać swoją sekcję krytyczną. Jeśli proces chce wejść do sekcji krytycznej, to ma zagwarantowane, że kiedyś do tej sekcji wejdzie.

W algorytmie Dekkera wykorzystywane są trzy zmienne. Mamy dwa procesy, tablicę dwuelementową k (początkowo elementy tej tablicy są równe 1, każdy proces kontroluje jedną komórkę tej tablicy). Jeśli proces chce wejść do sekcji krytycznej, to ustawia komórkę na 0 i jest ona tak ustawiona aż do momentu opuszczenia sekcji przez proces. Jeśli obydwa procesy chcą wejść do sekcji krytycznej, rozstrzyga zmienna kolejność. Zmienna p przechowuje numer procesu. Wady: dotyczy zaledwie dwóch procesów, oczekiwanie jest oczekiwanie aktywnym, czyli czekając na zdarzenie, proces musi sprawdzać warunek określający, czy dane zdarzenie już zaszło, czy też nie.

Algorytm piekarniany(Lamporta) wykorzystuje się do rozwiązania problemu wzajemnego wykluczania się w sekcji krytycznej dla dowolnej N liczby procesów. Proces o najwyższym indeksie wykona swoją sekcję krytyczną najpóźniej.

2)

Stany procesu:

a) nowy (new) – w tym stanie proces znajduje się zaraz po utworzeniu;
b) wykonywanie (running, executing) – proces ma przydzielony procesor, który wykonuje jego instrukcje;
c) oczekiwanie (waiting) – proces oczekuje na zdarzenie (np. na zakończenie operacji wejścia-wyjścia);
d) gotowość (ready) – proces oczekuje na przydział procesora w kolejce procesów gotowych do wykonywania;
e) zakończony (terminated) – proces zakończył działanie, lecz wciąż pozostaje w systemie (np. nie przekazał wyników).
Dodatkowo wyróżnia się jeszcze stan blokady, w którym jednak muszą jednocześnie uczestniczyć co najmniej dwa procesy. Naprzemienne występowanie po sobie stanów wykonywania i oczekiwania jest typowe w przebiegu procesu.

3)

Zasada wiedzy koniecznej(need-to-know principle), zalecenie projektowe, ważne przy budowie systemów operacyjnych, w myśl którego procesy w każdej chwili działania powinny dysponować tylko niezbędnymi prawami dostępu do zasobów. Na przykład proces, którego zadaniem jest czytanie pliku, nie powinien mieć prawa zapisywania tego pliku. Przestrzeganie zasady wiedzy koniecznej zmniejsza skutki awarii systemu.

zasada wiedzy koniecznej (need to know): proces p wywołuje procedurę A – procedura A ma dostęp jedynie do swoich zmiennych i przekazanych do niej parametrów, a nie do wszystkich zmiennych procesu p.

4)

Struktura klient-serwer:

• Podział systemu operacyjnego na moduły,

• Moduły nie są rozmieszczone w warstwach,

• Nie komunikują się między sobą poprzez wywołanie procedur, ale wysyłają komunikaty za pośrednictwem centralnego programu obsługi komunikatów,

• Komunikaty mogą być wysyłane w obie strony,

• Moduł wysyłający komunikat początkowy nazywa się klientem,

• Moduł obierający ten komunikat jest serwerem

5)

Wątek – część programu wykonywana współbieżnie w obrębie jednego procesu; w jednym procesie może istnieć wiele wątków.

Różnica między zwykłym procesem a wątkiem polega na współdzieleniu przez wszystkie wątki działające w danym procesie przestrzeni adresowej oraz wszystkich innych struktur systemowych (np. listy otwartych plików, gniazd, itp.) - z kolei procesy posiadają niezależne zasoby.

6)

Szamotanie to sytuacja, gdy proces ma mniej ramek niż liczba aktywnie używanych stron i musi, co chwile sprowadzać jedną ze stron usuwając inną, która za chwilę będzie niezbędna.

Zapobieganie: zastosować lokalny lub priorytetowy algorytm zastępowania stron lub dostarczyć procesowi właściwą liczbę ramek – strategia tworzenia zbioru roboczego.

Aby ograniczyć szamotanie należy:

zastosować lokalny lub priorytetowy algorytm zastępowania stron,

dostarczyć procesowi właściwą liczbę ramek – strategia tworzenia zbioru roboczego –

model strefowy wykonania procesu.

7)

Windows	Linux
- pamięć fizyczna (RAM), - pamięć wirtualna (przechowywana na dysku), automatycznie ustawia obsługę pamięci fizycznej - umożliwia użytkownikowi ręczną konfigurację pamięci wirtualnej lub może zrobić to automatycznie - dzięki takiemu narzędziu jak Miernik zasobów możliwa jest kontrola zużycia zasobów użytkownika, systemu oraz interfejsu graficznego	- podział pamięci fizycznej na ramki - podział pamięci wirtualnej na strony - rozwiązania sprzętowe - przydział pamięci fizycznej poszczególnym procesom, - odwzorowanie logicznej przestrzeni adresowej procesu na fizyczną przestrzeń adresową pamięci, -ochrona zawartości pamięci,
- również dzięki Monitorowi systemu możliwa jest obserwacja aktualnego stanu zużycia pamięci, podręcznej pamięci dysku, jądra systemu oraz systemu plików - ma ikonę System, która informuje nas o pamięci wirtualnej i pamięci fizycznej komputera	- współdzielenie obszarów pamięci przez różne procesy. - obsługuje pamięć wirtualną - wykorzystuje cześć dysku jako rozszerzenie fizycznej Pamięci - Jądro zapisuje zawartość nieużywanych bloków pamięci fizycznej na dysku, umożliwiając tym samym wykorzystanie ich do innych celów - Linux potrafi wykorzystywać zwykły plik na systemie plików lub oddzielną partycję jako obszar wymiany. - Linux pozwala używać kilku partycji/plików wymiany jednocześnie.

8)

Sposoby realizacji domeny (ochrona)

- użytkownik – domena(zbiór obiektów zależy od id użytkownika)

- proces ( zbiór obiektów zależy od id procesu)

- procedura ( zbiór obiektów zależy od lokalnych zmiennych procedury)

UNIX: domena związana z użytkownikiem

przełączanie domen – czasowa zmiana identyfikacji użytkownika:

dla każdego pliku – ID właściciela + bit domeny (setuid bit)

gdy bit domeny=0, user_id procesu=user_id użytkownika, który uruchomił proces

gdy bit domeny=1, user_id procesu=user_id użytkownika, który jest właścicielem pliku

9)-------------

10)

Planowanie procesów:

Celem planowania procesów jest jak najlepsze wykorzystanie procesora – szczególnie

ważne w systemach wieloprogramowych z podziałem czasu,

Kolejki planowania – zbiory procesów czekających na jakieś zdarzenia:

o Kolejka zadań (job queue): zbiór wszystkich procesów w systemie,

o Kolejka procesów gotowych (ready queue): zbiór procesów rezydujących w

pamięci operacyjnej, gotowych i czekających na wykonanie (ma postać listy

powiązanej),

o Kolejka do urządzenia (device queue): zbiór procesów czekających na

konkretne urządzenie WE/WY – każde urządzenie ma własną kolejkę.

Planowanie procesów:

Planista długoterminowy (long term scheduler) – planista zadań – ładuje procesy do

pamięci (system wsadowy – wiele procesów gotowych do wykonania – na dyskach;

system z podziałem czasu często nie ma planisty długoterminowego; nadzoruje

stopień wieloprogramowości (wywoływany tylko gdy proces upuszcza system) –

ładuje procesy do pamięci.

Planista krótkoterminowy (short term scheduler) – planista przydziału procesora

(CPU scheduler) – wybiera jeden proces i przydziela mu procesor (min. co 100ms)

Planista średnioterminowy (medium term scheduler) – umożliwia usunięcie procesu

z pamięci – zmniejszenie stopnia wieloprogramowości (swapping).

11)

Semafory służą do synchronizacji procesów. Pozwalają na czasowe zabezpieczenie jakiegoś zasobu przed innymi procesami. Semafor jest to nieujemna zmienna całkowita, na której, z wyjątkiem nadawania wartości początkowych, mogą działać jedynie operacje czekaj i sygnalizuj.

Operacja czekaj powoduje zmniejszenie wartości semafora o 1, pod warunkiem, że nie ma on wartości 0. Jest to operacja niepodzielna. Operacja czekaj może spowodować wstrzymanie jakiegoś procesu, ponieważ jeśli dotyczy ona semafora mającego wartość 0, to proces, którym ta operacja wystąpiła, będzie mógł być nadal wykonywany tylko wówczas, gdy inny proces zwiększy wartość semafora o 1 w wyniku operacji sygnalizuj.

Operacja sygnalizuj powoduje zwiększenie wartości semafora o 1 i zawsze jest możliwa do wykonania. Jest to również operacja niepodzielna.

13)

Jak się oblicza efektywny czas dostępu?

EAT (Effective Access Time)=(1-p)·cd + p · x

cd - czas dostępu do pamięci zwykłej

x – narzut związany z przerwaniem braku strony

p - prawdopodobieństwo braku strony

14)

Omów algorytm SJF oraz policz średni czas oczekiwania dla algorytmów szeregowania zadań SJF i

FIFO dla procesów o czasach trwania faz wynoszących 7, 5, 2, 4 jednostki?

SJF jest algorytmem optymalnym ze względu na najkrótszy średni czas oczekiwania. W wersji z wywłaszczaniem,

stosowana jest metoda: najpierw najkrótszy czas pracy pozostałej do wykonania. Problemem tego algorytmu

jest głodzenie długich procesów - może się zdarzyć, że cały czas będą nadchodzić krótsze procesy, a wtedy proces

dłuższy nigdy nie zostanie wykonany. Algorytm SJF jest optymalny, tzn. daje minimalny średni czas oczekiwania

dla danego zbioru procesów.

SJF śr. czas oczek. = (0 + (0+2) + (0+2+4) + (0+2+4+5))/4 = (0+2+6+11)/4 = 19/4 = 4.75

FCFS śr. czas oczek. = (0 + (0+7) + (0+7+5) + (0+7+5+2))/4 = (0+7+12+14)/4 = 33/4 = 8.25

15)

Co się dzieje z procesem po jego utworzeniu?

Gdy nowoutworzony proces ma już wszystkie zasoby do dyspozycji (oprócz procesora)

1.Proces nowy może przejść jedynie do stanu gotowy. Dzieje się tak po przyjęciu go przez system.

2.Proces gotowy może przejść jedynie do stanu aktywny. Dzieje się tak, gdy planista przydzieli temu procesowi

procesor.

3.Proces aktywny może przejść do jednego z trzech stanów:

- gotowy (gdy planista odbierze temu procesowi procesor),

- czekający (gdy ten proces rozpocznie oczekiwanie na jakieś zdarzenie, albo na ukończenie operacji wejściawyjścia),

- zakończony (gdy proces zakończy działanie).

4.Proces czekający może przejść jedynie do stanu gotowy. Dzieje się tak, gdy nastąpi oczekiwane przezeń

zdarzenie lub ukończenie operacji wejścia-wyjścia.

5.Proces zakończony nie może już zmienić swojego stanu.

proces może wydać zamówienie na operację we/wy i następnie zostać umieszczony w kolejce procesów

czekających na we/wy. Proces może utworzyć nowy proces i oczekiwać na jego zakończenie. Proces może zostać przymusowo usunięty z procesora w wyniku przerwania i przeniesiony z powrotem do kolejki procesów gotowych.

16)

Omów i porównaj stronicowanie z segmentacją?

Celem segmentacji jest logiczny podział przestrzeni adresów, podczas gdy celem stronicowania jest fizyczny

podział pamięci, którą chcemy implementować, jako pamięć na tym samym poziomie.

Strony mają ustalony rozmiar wynikający z architektury maszyny, podczas gdy rozmiar segmentów może być

dowolny, określony przez programistę.

Podział adresu programu na numery strony i bajtu jest wykonywany środkami sprzętowymi, a przekroczenie

zakresu dla numeru bajtu automatycznie powoduje zwiększenie numeru strony.

Podział adresu programu na numery segmentu i bajtu jest logiczny, a przekroczenie zakresu dla numeru bajtu nie

ma żadnego wpływu na numer segmentu (przekroczenie zakresu dla numeru bajtu powoduje sygnalizację

przekroczenia zakresu pamięci).

17)

Schematy przydziału ramek

- równy (każdy proces dostaje tyle samo ramek)

- proporcjonalny (liczba ramek proporcjonalna do jego rozmiaru)

- priorytetowy (liczba przydzielanych ramek jest proporcjonalna do priorytetu procesu lub do kombinacji priorytetu

i rozmiaru)

- zstępowanie lokalne

- zstępowanie globalne

18)

Omów metody obsługi zakleszczeń?

Zapobieganie zakleszczeniom Polega na zaprzeczeniu co najmniej jednemu z czterech warunków koniecznych

zakleszczenia. Gdy co najmniej jeden z tych warunków nie jest spełniony, mamy pewność, że do zakleszczenia nie

dojdzie.

Unikanie zakleszczeń Gdy stosujemy tę metodę wszystkie warunki konieczne występowania zakleszczeń są

prawdziwe. Nie dopuszczamy do zakleszczeń poprzez badanie stanu systemu przed każdym żądaniem przydziału

zasobów i niekiedy odrzucamy to żądanie nawet wtedy, gdy są wolne zasoby, ale uznaliśmy, że spełnienie tego

żądania może prowadzić do zakleszczenia. Unikanie zakleszczeń zwykle wymaga dodatkowej wiedzy o procesach

(np. o ich maksymalnym dopuszczalnym zapotrzebowaniu na zasoby).

Wykrywanie zakleszczeń i odtwarzanie Dopuszczamy powstawanie zakleszczeń, ale umiemy je wykrywać,

likwidować i przywracać normalne działanie systemu po tym zabiegu.

19)

Sprzętowe mechanizmy ochrony pamięci operacyjnej?

Ochrona wektora przerwań, ochrona procedur obsługi przerwań, oddzielenie obszaru pamięci programów

21)

Dynamiczny przydział pamięci:

Jak na podstawie listy wolnych dziur spełnić zamówienie na obszar o rozmiarze n?

o Pierwsze dopasowanie (first-fit) – przydziela się pierwszą dziurę o

wystarczającej wielkości. Szuka się od początku wykazu dziur lub od miejsca

zakończenia ostatniego szukania.

o Najlepsze dopasowania (best-fit) – przydziela się najmniejszą z dostatecznie

dużych dziur. Zapewnia najmniejsze pozostałości, ale wymaga przeszukania

całej listy.

o Najgorsze dopasowanie (worst-fit) – przydziela się największą dziurę.

Wymaga przeszukanie całej listy, pozostawia po przydziale największą dziurę

(czasami może być bardziej przydatna niż wiele rozproszonych małych dziur).

Symulacje pokazują, że pierwsze dwie strategie są lepsze od trzeciej pod względem

zużycia czasu, jak i pamięci (najszybsza jest pierwsza).

22)

Omów dwie metody przydziału miejsca na dysku, które najlepiej nadają się do realizacji dostępu

bezpośredniego?

1. System plików zwartych (przydział ciągły): cały plik zajmuje ciąg kolejnych bloków; odwołanie do pliku składa

się z adresu bloku początkowego i rozmiaru pliku (ilość bloków w pliku). Własności:

-Efektywność dostępu (niewielkie ruchy głowic dysk.)

-Łatwa lokalizacja bloków pliku zarówno przy dostępie sekwencyjnym jak i swobodnym

-Problem fragmentacji zewnętrznej: po usuniętych plikach pozostają dziury, które trudno połączyć w jeden

większy blok

-Umożliwia najbardziej elastyczną organizację danych – zniszczenie jednego bloku powoduje tylko lokalną utratę

danych

2. Mapa plików (Windows):

Wpis katalogowy wskazuje na adres pierwszego bloku, natomiast pozostałe adresy wynikają z mapy plików

(tablicy alokacji). Uszkodzenie mapy plików powoduje utratę informacji dyskowych w pliku.

Właściwości:

• Każdy blok na dysku – pozycja w mapie,

• Bloki nieużywane – 0 w tablicy,

• Uszkodzenie mapy plików może spowodować poważne straty danych – dwie kopie

mapy w różnych rejonach dysku, aby w razie awarii sprzętu nie zniszczyć wszystkich

kopii,

• Znaczy ruch głowic dyskowych,

• Polepszenie czasu dostępu swobodnego.

23)

Algorytmy przybliżające LRU

Jedno z takich przybliżeń polega na skojarzeniu z każdą ramką bitu odwołania/odniesienia. Wstępnie wszystkie

bity odwołania są równe 0. Przy każdym odwołaniu do strony odpowiadający jej bit jest ustawiany na 1.

- Algorytm bitów odniesień

- z każdą pozycją w tablicy stron związany jest bit odniesienia ustawiony początkowo na 0

- przy odwołaniu do strony jest on ustawiany na 1

- zastępowana jest ta strona w porządku FIFO, która ma bit odniesienia ustawiony na 0

24)

Różnice w sposobach synchronizacji: semafory i strukturalne metody synchronizacji?

Monitory.

Stosując semafory można popełnić szereg błędów programistycznych: zapomnieć o podniesieniu czy

opuszczeniu semafora, pomylić semafory, czy np. pomylić operacje P i V. W przypadku monitorów

odpowiednie instrukcje synchronizujące są realizowane przez język programowania.

Konstrukcja monitora zapewnia, że tylko jeden proces na raz może znajdować się w monitorze. Pozostałe

procesy oczekują w kolejce (FIFO). Jeśli jakiś proces chce wejść do monitora, który jest właśnie zajęty, to

jest on wstawiany na koniec kolejki procesów oczekujących na wejście do monitora. Jeśli proces opuszcza

monitor, a inne procesy czekają w kolejce na wejście do monitora, to pierwszy proces z kolejki wchodzi do

monitora.

Regiony Krytyczne.

 Każdy proces posiada swoje własne zmienne lokalne oraz procedury

 Do zmiennych lokalnych proces może sięgać tylko w swoich procedurach, żaden z procesów nie ma

dostępu do zmiennych lokalnych innego procesu

 Procesy współdzielą między sobą zmienne globalne

26)

Omówić RAID0 i RAID1?

RAID 0 - Dane są podzielone na bloki(najczęściej o rozmiarze 512 bajtów) pomiędzy wszystkie dyski. Jest to

rozwiązanie tanie w implementacji, lecz nie oferuje bezpieczeństwa danych. Dane odczytywane są równolegle ze

wszystkich dysków co zapewnia szybkość, lecz przy awarii jednego dysku nie jesteśmy w stanie odtworzyć

danych.

RAID 1 – Zapis danych jest realizowany na dyskach połączonych w pary, dane na obu dyskach w każdej parze są

identyczne. Zapewnia wysoki poziom bezpieczeństwa, lecz kosztem utraty połowy pojemności dysku.

27)

Wymień cztery sposoby implementowania macierzy dostępów

- Tablica globalna

- Wykazy dostępów do obiektów

- Wykazy uprawnień do domen

- Mechanizm zamka-klucz

29)

Gdzie można umiejscowić obszar wymiany?

Dysk twardy, pamięć flash (USB) – generalnie szybka pamięć pomocnicza z możliwością zapisu i odczytu

30)

Warstwowy system plików:

Programy użytkowe -> logiczny system plików (odpowiada również za bezpieczeństwo) -> moduł organizacji pliku -> podstawowy system plików (ogólne instrukcje dla modułów obsługi urządzenia) -> sterowanie we/wy -> urządzenia

Omów strukturę warstwową systemu operacyjnego?

Tworzenie systemu polega na podzieleniu go na moduły połączone w warstwy. Każda warstwa spełnia funkcje, które zależą tylko od warstwy znajdującej się pod spodem. Podział na moduły zmniejsza stopień wzajemnych zależności między różnymi składowymi systemu. Pozwala to uniknąć niepożądanych powiązań.