Wykłady

1. System operacyjny

Definicja

• coś, co obsługuje przerwania;

• zapewnia wirtualizację urządzeń do poziomu zasobów i udostępnia usługi do operacji na nich.

Cechą systemu musi być współbieżność wraz z zapobieganiem konfliktom - wynika to z różnicy szybkości urządzeń we/wy.

Podział

• systemy wsadowe - zadania są przedkładane systemowi jedno po drugim, wykonywane sekwencyjnie;

• systemy interakcyjne (wielodostępne) - każde zadanie ma pewien kwant czasu, i może zostać przerwane;

• systemy czasu rzeczywistego - mają ściśle zdefiniowane ograniczenia czasowe - przetwarzanie danych musi się zakończyć przed upływem określonego czasu.

Proces

• jest to wykonujący się program; musi trwać w skończonym czasie,

• inaczej: zjawisko wykonywania programu.

Zasoby

istnieją po to, by użytkownikowi mogły być oddawane usługi.

Pośrednictwo (powłoka, shell)

umożliwia kontakt między użytkownikiem a SO.

Zadania SO

• tworzenie procesów przez przodków,

• przydzielanie procesom zasobów,

• kontrola postępu procesów,

• realizacja usług,

• obsługa sytuacji wyjątkowych (np. zakończenie procesu).

Kryteria oceny SO

• niezawodność (zależy od sprzętu),

• bezpieczeństwo,

• efektywność,

• wygoda użytkowania.

2. Procesy & zasoby

<x,f,x₀>:

• x - przestrzeń stanu {M_{1 ...} M_n},

• f - funkcja przekształcająca,

• x₀ - stan początkowy.

Grupy zasobów

• D - domena: zasoby potrzebne do wykonania instrukcji,

• R - stan zasobów zmieniający się w czasie działania.

• D ∪ R = E - środowisko

Ciąg realizacyjny

• sekwencja zdarzeń początków i końców procesów; liczba elementów jest parzysta

• wyniki poszczególnych procesów powinny być niezależne od dowolnego ciągu realizacyjnego - zdeterminizowanie.

Interferencja

• przeszkadzanie sobie wzajemne procesów niezależnych,

• procesy niewspółbieżne nie interferują,

Mamy dwa procesy: 1 ma R₁ i D₁; 2 ma R₂ i D₂.

Interferencja zajdzie gdy: R₁ ∩ D₂ ∪ R₂ ∩ D₁ ∪ R₁ ∩ R₂ ≠ ∅.

W systemie zdeterminowanym interferencja nie wystąpi.

Wywłaszczanie, fantomy

Zasoby mogą być:

• wywłaszczalne - można wstrzymać korzystanie z niego przez jeden proces, zapisać jego aktualny stan, i przekazać go innemu procesowi (np. procesor);

• niewywłaszczalne - jeśli jakiś proces weźmie ten zasób, nie może go oddać, zanim nie skończy z niego korzystać (np. drukarka).

Wywłaszczanie zasobu polega na stworzeniu w przypadku żądania dostępu do niego przez inny proces tzw. fantomu, czyli zapisu jego aktualnego stanu (np. zawartości rejestrów procesora), oraz przekazaniu tego zasobu procesowi, który żądał dostępu.

Wzajemna blokada (deadlock)

Warunki konieczne wystąpienia (3, bo jak ktoś napisze 4 to pała - słowa Nałęckiego):

• istnieją co najmniej 2 zasoby niewywłaszczalne,

• proces, który nie dysponuje pełnym środowiskiem jest zablokowany,

• zasób może być zwolniony tylko przez dysponenta.

Zapobieganie występowaniu deadlocku - trzeba zapobiec spełnieniu któregoś z warunków:

1. Wzajemne wyłączanie:

• nie da się wykluczyć tego warunku, bo istnieją zasoby niewywłaszczalne z natury (np. drukarka).

2. Przetrzymywanie i oczekiwanie:

• procesowi przydziela się wszystkie zasoby, albo żaden. lub

• proces może zamówić zasoby, gdy nie ma aktualnie żadnych zasobów (zwolnił wszystkie, które posiadał)

Wykorzystanie zasobów może być nieefektywne.

3. Brak wywłaszczeń:

• gdy proces mający jakieś zasoby zgłasza zapotrzebowanie na inny zasób, dotychczasowe jego zasoby zostają zwolnione i dopisane do tych, na które on oczekuje. Proces zostaje wznowiony, gdy można mu przydzielić wszystkie, na które oczekuje.

• jeśli proces zamawia jakieś niedostępne zasoby, to sprawdza się, czy nie są one przydzielone do innego procesu, który czeka (na dodatkowe zasoby)

• jeśli jest taki, co czeka (przetrzymuje te, co ma) - tamtemu odbiera się te zasoby i przydziela aktualnie żądającemu,

• jeśli te zasoby nie są przetrzymywane, to zamawiający musi czekać.

4. Czekanie cykliczne:

Technika Havendera (hierarchii grupowej)

Numerujemy zasoby od 1 do n. Dany proces może pobrać zasób k, jeśli ma wszystkie potrzebne mu zasoby o numerach mniejszych od k.

Wyższe numery nadaje się najcenniejszym (najbardziej rozchwytywanym) zasobom.

Synchronizacja

• pozwala na realizację kilku procesów na raz - wprowadza zależności między procesami.

1. semafory:

• V - przydział,

• P - zwolnienie

2. metoda TAS

• rozkaz procesora (testowanie zawartości komórki):

sleep: TAS a

JMP sleep

<dalej>

• jeśli a=0, skok o 1 rozkaz,

• jeśli a≠0, skok o 2 rozkazy.

3. skrzynka pocztowa

• pośredniczy między procesami (umożliwia wymianę informacji)

• możliwe operacje :

• create(id, pojemność),

• destroy(id),

• test(id),

• send(id, treść),

• receive(id, &bufor).

Zmiany stanu procesów

gotowy

• posiada wszystkie zasoby oprócz procesora.

przyczyny przejść między stanami (inne niż normalne) - przerwania

• awarie sprzętu,

• we/wy - przejście do gotowy z czekający / zablokowany,

• zewnętrzne - ze źródła z którym SO nie ma nic wspólnego,

• błędy programowe,

• pochodzące od procesu - usługi systemowe - przejście z liczony do zablokowany.

Gospodarka czasem procesora - gospodarka procesami

• czas procesora jest zasobem podzielnym

• regulamin wybierania, komu przydzielić czas procesora

pierwszy podział:

• naturalny - kolejka bezpriorytetowa,

• priorytetowy

drugi podział:

• z wywłaszczaniem procesora

• bez wywłaszczania procesora

• podział systemów operacyjnych:

priorytetowe	4	3
kolejka	2	1
	z wywłasz-czaniem	bez wywłasz-czania

	wydajność
duża		mała
mała			duża
	szybkość reakcji

Bardzo obrazowe porównania

1	Model wsadowy - jak kolejka u dentysty
2	Wszyscy są równi - wielodostęp z podziałem czasu
3	Dentysta, który poza kolejnością przyjmuje znajomych
4	System o odwołaniu bezpośrednim - czasu rzeczywistego

3. Gospodarka pamięcią operacyjną

procesor

rejestry

cache L1

cache L2

PaO

dysk

serwer

internet

• polega na wyodrębnieniu dla danego procesu pewnego obszaru pamięci,

• 
  
  
  
  
  
  
  
  
  
  
  
  
  
  proces widzi tzn. wirtualną przestrzeń adresową,







Mechanizmy gospodarki pamięcią

Nakładkowanie

• część procesu (kodu, danych) leży na dysku; proces sprowadza sobie to, co potrzebuje.

Stronicowanie

adres logiczny w WPA	nr strony	przesunięcie
	dynamiczna translacja adresu
adres fizyczny	xxx (atrybuty, np. write-enabled)

Działanie

• do PaO ładuje się tylko fragment przestrzeni procesu,

• układ DTA (Dynamicznej Translacji Adresu) tworzy numer ramki lub (jeśli jej brak) generuje przerwanie „brak strony” - trzeba ją sprowadzić z dysku do PaO,

• może być jakaś wolna ramka do załadowania do niej - jak nie ma, to albo czekamy, albo robi się wywłaszczanie,

• są różne algorytmy usuwania stron z PaO, np. ostatnio nieużywanych.

Migotanie

• występuje gdy jest zbyt dużo pamięci wirtualnej w porównaniu z rzeczywistą,

• można przyjąć, że stosunek rozmiaru pamięci rzeczywistej do pamięci wirtualnej powinien być 0.5 .. 0.33.

Sekcjonowanie

• jednospójne - sekcja stanowi jeden spójny obszar

• system początku, końca i długości

Sekcje stałe

• zajęte,

• wolne.

SO realizuje „nakładkowanie” dla procesu - sprowadza mu potrzebne fragmenty sekcji.

• może zaistnieć fragmentacja wewnętrzna - wolne obszary wewnątrz sekcji nie mogą być przydzielone innym procesom.

Sekcje zmienne

• proces dostaje wiele sekcji składających się na jego przestrzeń,

• wystepuje fragmentacja zewnętrzna - proces nie dostaje ciągłego obszaru.

Algorytmy poszukiwania wolnego obszaru dla utworzenia sekcji

• first-fit - mały narzut czasowy; sekcje uporządkowane rosnąco,

• best-fit - wybiera się najmniejszy obszar mogący pomieścić sekcję,

• worst-fit - wybiera się największy wolny obszar.

Technika bliźniaków

• PaO traktujemy jak jeden blok 2ⁿ, i dzielimy go na mniejsze (przez 2),

• Jeśli chcemy przydzielić pamięć o rozmiarze M:

2^k-1 < M ≤ 2^k

• przydzielamy 2^k

• technika nie stosowana we współczesnych SO.

4. Gospodarka zasobami we/wy

Realizacja komunikacji z UZ

1. Programowe we/wy - obsługuje procesor

2. Przerwania

3. DMA

Buforowanie

Bufory mogą być zrealizowane w:

• UZ

• w karcie interfejsu

• pomiędzy aplikacją i sterownikiem

Urządzenia we/wy

• dysk

• terminal

• drukarka

Zadania systemu operacyjnego wobec dysku

• transport: zapis/odczyt + suma kontrolna,

• testowanie,

• organizacja dysku (sektor 0 - informacje o dysku, dalej normalne dane).

SmartDrive

• kolejkuje zgłoszenia do dysku w ten sposób, że gdy głowica przesuwa się nad obszarem, z którego nie czyta, odczytywane są dane, które powinny być odczytane później;

• stosuje się 2 techniki:

• windy: głowica jeździ w góre i w dół czytając po drodze to, co jest lub niedługo będzie potrzebne,

• odkurzacza: jadąc w górę czytamy, wracamy błyskawicznie.

• SmartDrive ma swój bufor w PaO - ta pamięć udaje dysk.

Buforowanie

• wiąże się z ryzykiem utraty danych, musi to kontrolować protokół.

Defragmentacja

• sprzyja programom buforującym, bo zwiększa szansę trafienia w potrzebne dane.

Drukarki

• oprogramowanie buforujące: SPOOL - zapisuje dane do wydrukowania na dysku, a potem posyła na drukarkę, gdy jest gotowa; umożliwia np. drukowanie od końca.

Terminal

• pozwala na interakcję między użytkownikiem a aplikacją,

• ANSI - sposób opisu urządzeń gwarantujący jednoznaczność prezentacji niezależnie od urządzenia.

5. System plików

• organizacja zapisu danych,

• metody dostępu do danych.

Wymagania

• efektywna alokacja pamięci zewnętrznej,

• skuteczność dostępu do danych,

• niewidoczne mechanizmy wewnętrzne,

• niezależność od urządzeń,

• wspólny dostęp do danych,

• ochrona danych,

• operacje na zbiorach.

gotowy

liczony

czekający,

zablokowany

hardware

system

kompilacja

przestrzeń nazw

przestrzeń logiczna

runtime

biblioteki dll

przestrzeń fizyczna

ładowanie do PaO

zadanie systemu operacyjnego

---