Teoria System Operacyjne

1.Definicja Systemów Operacyjnych

System operacyjny jest zbiorem ręcznych i automatycznych procedur, które pozwalają grupie osób na efektywne współdzielenie urządzeń maszyny cyfrowej - per brinch habsen	System operacyjny jest programem, który działa jako pośrednik między użytkownikiem komputera a sprzętem komputerowym. Zadaniem systemu operacyjnego jest tworzenie środowiska, w którym użytkownik może wykonywać programy w sposób wygodny i wydajny. -Abraham Silberschatzan Shaw
System operacyjny (nadzorczy, nadrzędny, sterujący) jest to zorganizowany zespół programów, które pośredniczą między sprzętem a użytkownikami, dostarczając użytkownikom zestawu środków ułatwiających projektowanie, kodowanie, uruchamianie i eksploatację programów oraz w tym samym czasie sterują przydziałem zasobów dla zapewnienia efektywnego działania. -Alan shaw	System operacyjny jest warstwą oprogramowania operującą bezpośrednio na sprzęcie, której celem jest zarządzanie zasobami systemu komputerowego i stworzenie użytkownikowi środowiska łatwiejszego do zrozumienia i wykorzystania. -Andrew Tanenbaum

2.Zadania Systemu Operacyjnego

-Definiowanie interfejsu użytkownika: system operacyjny dostarcza użytkownikom zbiór poleceń lub system okienkowy wraz z odpowiednim menu, który umożliwia interakcję z systemem komputerowym.

-Udostępnianie systemu plików: system operacyjny organizuje i ułatwia dostęp do informacji np. w postaci hierarchicznego systemu plików.

-Udostępnianie środowisko do wykonywania programów: system operacyjny dostarcza struktur danych do organizacji wykonywania programu oraz zachowywania i odtwarzania stanu przetwarzania (procesy i przełączanie kontekstu). System operacyjny udostępnia też programistom mechanizmy komunikacji pomiędzy procesami (kolejki komunikatów, strumienie, pamięć współdzielona) oraz mechanizmy synchronizacji procesów (np. semafory).

-Sterowanie urządzeniami wejścia-wyjścia: odpowiednie moduły sterujące, integrowane z systemem operacyjnym, inicjalizują pracę urządzeń zewnętrznych oraz pośredniczą w efektywnym przekazywaniu danych pomiędzy jednostką centralną a tymi urządzeniami.

-Obsługa podstawowej klasy błędów: system operacyjny reaguje na błędy użytkowników (np. niedostępność zasobów, brak prawa dostępu), programistów (np. błąd dzielenia przez 0, naruszenie ochrony pamięci, nieprawidłowy kod rozkazu) oraz systemu (np. błąd braku strony, błąd magistrali).

-Efektywność zarządzania zasobami oraz wygodny interfejs dla użytkownika są dwoma ogólnymi, niezależnymi celami projektowymi systemów operacyjnych. Pierwszy z tych celów był kluczowy w rozwoju rodziny systemów uniksowych. Dopiero w późniejszych etapach ich rozwoju pojawił się intuicyjny okienkowy interfejs użytkownika. Systemy rodziny MS Windows zorientowane były natomiast przede wszystkim na interfejs użytkownika, na bazie którego w późniejszych etapach rozwoju powstawał pełnowartościowy system operacyjny, uwzględniający szerzej rozumiane zarządzanie zasobami.

3.Klasyfikacja Systemow Operacyjnych

1.sposob przetwarzania Systemy przetwarzania bezpośredniego (ang. on-line processing systems) — systemy interakcyjne – występuje bezpośrednia interakcja pomiędzy użytkownikiem a systemem, – wykonywanie zadania użytkownika rozpoczyna się zaraz po przedłożeniu. • Systemy przetwarzania pośredniego (ang. off-line processing systems) — systemy wsadowe – występuje znacząca zwłoka czasowa między przedłożeniem a rozpoczęciem wykonywania zadania, – niemożliwa jest ingerencja użytkownika w wykonywanie zadania.

3.liczbe uzytkownikow Systemy dla jednego użytkownika — zasoby przeznaczone są dla jednego użytkownika (np. w przypadku komputerów osobistych), nie ma mechanizmów autoryzacji, a mechanizmy ochrony informacji są ograniczone. • Systemy wielodostępne — wielu użytkowników może korzystać ze zasobów systemu komputerowego, a system operacyjny gwarantuje ich ochronę przed nieupoważnioną ingerencją.

2.liczbe wykownywanych proramow Systemy jednozadaniowe — niedopuszczalne jest rozpoczęcie wykonywania następnego zadania użytkownika przed zakończeniem poprzedniego. • Systemy wielozadaniowe — dopuszczalne jest istnienie jednocześnie wielu zadań (procesów), którym zgodnie z pewną strategią przydzielany jest procesor.

4.Inne Systemy czasu rzeczywistego (ang. real-time systems) — zorientowane na przetwarzanie z uwzględnieniem czasu zakończenie zadania, tzw. linii krytycznej (ang. deadline). • Systemy sieciowe i rozproszone (ang. network and distributed systems) — umożliwiają zarządzanie zbiorem rozproszonych jednostek przetwarzających, czyli zbiorem jednostek (komputerów), które są zintegrowane siecią komputerową i nie współdzielą fizycznie zasobów. • Systemy operacyjne komputerów naręcznych — tworzone dla rozwiązań typu PDA, czy telefonów komórkowych, podlegają istotnym ograniczeniom zasobowym.

1.Procesy

Proces jest elementarną jednostką pracy (aktywności) zarządzaną przez system operacyjny, która ubiega się o zasoby systemu komputerowego w celu wykonania programu.

• Proces = wykonujący się program.

• Elementy składowe procesu:

– program — definiuje zachowanie procesu,

– dane — zbiór wartości przetwarzanych oraz wyniki,

– zbiór zasobów tworzących środowisko wykonawcze,

– blok kontrolny procesu (PCB, deskryptor) — opis bieżącego stanu procesu.

Podział operacji jądra systemu w zarządzaniu procesami

i zasobami

• Operacje tworzenia i usuwania procesów oraz

elementarna komunikacja międzyprocesowa

• Operacje przydziału i zwalniania jednostek zasobów

• Elementarne operacje wejścia-wyjścia

• Procedury obsługi przerwań

Zarządcy

• Zarządca procesów (process manager) — kontroluje stany procesów w celu efektywnego i bezpiecznego wykorzystania współdzielonych zasobów systemu.

• Zarządca zasobów (resource manager) — realizuje przydział zasobów stosownie do żądań procesów, aktualnego stanu systemu oraz ogólnosystemowej polityki przydziału.

Struktury danych

• Deskryptor procesu (blok kontrolny procesu, PCB) — używany przez zarządcę procesów w celu rejestrowania stanu procesu w czasie jego monitorowania i kontroli.

• Deskryptor zasobu — przechowuje informacje o dostępności i zajętości danego typu zasobu.

Deskryptor procesu

• Identyfikator procesu

• Stan procesu (nowy, gotowy, oczekujący, itd.)

• Identyfikator właściciela

• Identyfikator przodka

• Lista przydzielonych zasobów

• Zawartość rejestrów procesora

• Prawa dostępu (domena ochrony)

• Informacje na potrzeby zarządzania pamięcią

• Informacje na potrzeby planowania (np. priorytet)

• Informacje do rozliczeń

• Wskaźniki do kolejek porządkujących

Stany procesu

• Nowy (ang. new) — proces jest tworzony.

• Wykonywany (ang. running) — wykonywane są instrukcje programu.

• Oczekujący (ang. waiting) — proces oczekuje na jakieś zdarzenie, np. na zakończenie operacji wejścia-wyjścia, na przydział dodatkowego zasobu, synchronizuje się z innymi procesami.

• Gotowy (ang. ready) — proces czeka na przydział procesora.

• Zakończony (ang. terminated) — proces zakończył działanie i zwalnia zasoby.

Obsługa procesów

• Tworzenie procesu

– POSIX: fork

– Windows: CreateProcess

• Usuwanie procesu

– POSIX: exit, abort, kill

– Windows: ExitProcess, TerminateProcess

Obsługa procesów (2)

• Zawieszanie i aktywacja procesu

• Wstrzymywanie i wznawianie procesu

• Zmiana priorytetu procesu

– POSIX: nice (setpriority)

– Windows: SetPriorityClass

• Oczekiwanie na zakończenie procesu

– POSIX: wait, waitpid

– Windows: brak bezpośredniego wsparcia, należy użyć odpowiednich mechanizmów synchronizacji

Kolejki procesów

• Kolejka zadań (ang. job queue) — wszystkie procesy systemu.

• Kolejka procesów gotowych (ang. ready queue) — procesy gotowe do działania, przebywające w pamięci głównej.

• Kolejka do urządzenia (ang. device queue) — procesy czekające na zakończenie operacji wejścia-wyjścia.

• Kolejka procesów oczekujących na sygnał synchronizacji od innych procesami (np. kolejka procesów na semaforze).

2.Zasoby

Zasobem jest element sprzętowy lub programowy systemu komputerowego, którego brak może potencjalnie zablokować wykonywanie programu (przetwarzanie)

• Przykłady zasobów: procesor, pamięć, plik (dane) itp.

W ramach zarządzania ogólnie rozumianymi zasobami można wyróżnić następujące operacje:

• Przydział zasobów: realizacja żądań dostępu do zasobów w taki sposób, że zasoby używane są zgodnie z intencją użytkowników (np. zagwarantowanie wyłącznego dostępu drukarki).

• Planowanie dostępu do zasobów: strategia przydziału zasobów gwarantująca bezpieczeństwo, żywotność, brak zakleszczenia, sprawiedliwość oraz optymalność ich wykorzystania. Warto zwrócić uwagę na odróżnienie planowania od samego przydziału — przydział oznacza powiązanie zasobu z realizowanym zadaniem, podczas gdy planowanie wiąże się z podejmowaniem decyzji odnośnie wyboru zdania, któremu zasób będzie przydzielony.

• Ochrona i autoryzacja dostępu do zasobów: dopuszczanie możliwości użytkowania zasobu tylko przez osoby uprawnione i w zakresie przydzielonych im uprawnień.

• Odzyskiwanie zasobów: dołączanie zwolnionych zasobów do zbioru zasobów wolnych po zakończeniu ich użytkowania.

• Rozliczanie: rejestrowanie i udostępnianie informacji o wykorzystaniu zasobów w celach kontrolnych i rozrachunkowych.

Deskryptor zasobu

• Identyfikator zasobu

• Rodzaj zasobu

• Identyfikator twórcy zasobu

• Lista i liczba dostępnych jednostek zasobu

• Lista (kolejka) procesów oczekujących na jednostki danego zasobu

• Procedura przydziału

Klasyfikacja zasobów

• Ze względu na sposób wykorzystania

– zasoby odzyskiwalne (zwrotne, ang. reusable),

– zasoby nieodzyskiwalne (niezwrotne, zużywalne, ang. consumable).

• Ze względu na sposób odzyskiwania

– zasoby wywłaszczalne,

– zasoby niewywłaszczalne.

• Ze względu na tryb dostępu

– współdzielone

– wyłączne

Elementarne operacje na zasobach

• Tworzenie deskryptora zasobu

• Usuwanie deskryptora zasobu

• Realizacja żądania przydziału jednostek zasobu

• Zwolnienie i odzyskiwanie jednostek zasobu odzyskiwalnego

• Uwolnienie (wyprodukowanie) jednostki zasobu nieodzyskiwalnego

3. Wątki

Wątek (lekki proces, ang. lightweight process — LWP) jest obiektem w obrębie procesu ciężkiego (heavyweight), posiadającym własne sterowanie i współdzielącym z innymi wątkami tego procesu przydzielone (procesowi) zasoby:

– segment kodu i segment danych w pamięci

– tablicę otwartych plików

– tablicę sygnałów

Realizacja wątków

• Realizacja wątków na poziomie jądra systemu operacyjnego — jądro tworzy odpowiednie struktury (blok kontrolny) do utrzymywania stanu wątku.

– stan licznika rozkazów,

– stan rejestrów procesora,

– stan rejestrów związanych z organizacją stosu.

– przełączanie kontekstu pomiędzy wątkami przez jądro,

– większy koszt przełączanie kontekstu,

– bardziej sprawiedliwy przydział czasu procesora.

• Realizacja wątków na poziomie użytkownika — struktury związane ze stanami wątków tworzone są w przestrzeni adresowej procesu.

– przydział czasu procesora dla procesu (nie dla wątku)

– przełączanie kontekstu pomiędzy wątkami przez jawne odwołania do mechanizmu obsługi wątków

– mniejszy koszt przełączanie kontekstu (bez angażowania jądra systemu operacyjnego)

– możliwość „głodzenia” wątków tego samego procesu, gdy jeden z nich spowoduje przejście procesu w stan oczekiwania

Obsługa wątków

• Tworzenie wątku

– POSIX: pthread_create

– Windows: CreateThread, CreateRomoteThread

• Usuwanie wątku

– POSIX: pthread_exit, pthread_cancel

– Windows: ExitThread, TerminateThreadWstrzymywanie i wznawianie wątku

– POSIX: brak

– Windows: SuspendThread, ResumeThread

• Zmiana priorytetu wątku

– POSIX: pthread_setschedprio, pthread_setschedparam

– Windows: SetThreadPriority

• Oczekiwanie na zakończenie wątku

– POSIX: pthread_join

– Windows: brak bezpośredniego wsparcia, należy użyć odpowiednich mechanizmów synchronizacji

1.Ogólna koncepcja planowania

Tryb decyzji — określa okoliczności, w których oceniane i porównywane są priorytety procesów oraz dokonywany jest wybór procesu do wykonania.

-Schemat niewywłaszczeniowy (ang. nonpreemptive) — proces po uzyskaniu dostępu do procesora wykonywany

jest do momentu zakończenie lub zgłoszenia żądania obsługi do systemu.

-Schemat wywłaszczeniowy (ang. preemptive) — proces może zostać zatrzymany i umieszczony w kolejce procesów gotowych, a procesor zostaje przydzielony procesowi o wyższym (lub równym) priorytecie.

2.Argumenty funkcji planowania

-Utworzenie i przyjęcie nowego procesu

-Obudzenie procesu w wyniku otrzymania komunikatu, sygnału gotowości urządzenia (przerwanie) lub sygnału wynikającego z synchronizacji

- Upłynięcie kwantu czasu odmierzanego przez czasomierz

-Wzrost priorytetu innego procesu w stanie gotowy powyżej priorytetu procesu wykonywanego — możliwe w systemie ze zmiennymi priorytetami

3.Alogrytm szeregowania(z wywłaszczaniem i bez wywłaszczania)

Algorytmy planowania niewywłaszczającego

• FCFS (First Come First Served) — pierwszy zgłoszony,

pierwszy obsłużony

• LCFS (Last Come First Served) — ostatni zgłoszony,

pierwszy obsłużony

• SJF (SJN, SPF, SPN, Shortest Job/Process First/Next)

— najpierw najkrótsze zadanie

Algorytmy planowania wywłaszczającego

• Planowanie rotacyjne (ang. Round Robin, RR) — po

ustalonym kwancie czasu proces wykonywany jest

przerywany i trafia do kolejki procesów gotowych.

• SRT (Shortest Remaining Time) — najpierw zadanie,

które ma najkrótszy czas do zakończenia.

4.Kryteria oceny algorytmów planowania

• Efektywność z punktu widzenia systemu

– wykorzystanie procesora (processor utilization) — procent czasu, przez który procesor jest zajęty pracą

– przepustowość (throughput) — liczba procesów kończonych w jednostce czasu

• Inne aspekty z punktu widzenia systemu

– sprawiedliwość (fairness) — równe traktowanie procesów

– respektowanie zewnętrznych priorytetów procesów

– równoważenie obciążenia wykorzystania zasobów

• Efektywność z punktu widzenia użytkownika

– czas cyklu przetwarzania (turnaround time) — czas pomiędzy przedłożeniem zadania, a zakończeniem jego wykonywania (rzeczywisty czas przebywania w systemie w momencie zakończenie procesu),

– czas odpowiedzi (reakcji, response time) — czas pomiędzy przedłożeniem żądania, a rozpoczęciem przekazywania odpowiedzi.

– czas opóźnienia — czas od linii krytycznej do momentu zakończenia wykonywania

• Inne aspekty z punktu widzenia użytkownika

– przewidywalność — realizacja przetwarzania w zbliżonym czasie niezależnie od obciążenia systemu.

5. Przykład implementacji planowania przydziału procesora

Szeregowanie w systemie UNIX

Stosowany jest algorytm rotacyjny z wywłaszczaniem, oparty na priorytetach dynamicznych.

• Wartość priorytetu jest z zakresu od 0 do 127, mniejsza wartość liczbowa oznacza wyższy priorytet.

• Priorytet (dynamiczny) składa się z części statycznej i części modyfikowanej przez planistę.

• Część statyczna składa się z bazy (definiowanej przez system) oraz wartość nice (ustalanej przez użytkownika lub nadzorcę).

• Priorytet procesu ustalany jest zawsze, gdy proces ten przechodzi z trybu jądra do trybu użytkownika.

• Okresowo (mniej więcej co 1 sekundę) przeliczane są priorytety wszystkich procesów gotowych.

Szeregowanie w systemie Linux (jądro 2.6)

Stosowany jest algorytm rotacyjny z wywłaszczaniem, oparty na priorytetach dynamicznych.

• Wyróżnia 140 poziomów priorytetu związanych z 3 klasami (politykami) szeregowania:

– SCHED_OTHER — polityka szereg. zwykłych zadań,

– SCHED_FIFO — polityka szereg. zadań czasu rzeczywistego zgodnie z zasadą FIFO,

– SCHED_RR — polityka szeregowania zadań czasu rzeczywistego w sposób rotacyjny.

• Większa wartość oznacza niższy priorytet.

Szeregowanie w systemie Windows 2000/XP

Szeregowaniu podlegają wątki, stanowiące obiekty w obrębie procesu.

• Stosowany jest algorytm rotacyjny z wywłaszczaniem, oparty na priorytetach dynamicznych.

• Wyróżnia się 32 poziomy priorytetu:

– 0 — bezczynność (poziom systemowy, niedostępny),

– 1 do 15 — priorytety dynamiczne (zmienne)

– 16 do 31 — priorytety czasu rzeczywistego

• Większa wartość (poziom) oznacza wyższy priorytet.

1. Zarządzanie pamięcią operacyjną

Pamięć jako zasób systemu komputerowego

• Pamięć jest zasobem służący do przechowywania danych i programów.

• Z punktu widzenia systemu pamięć jest zasobem o strukturze hierarchicznej (począwszy od rejestrów procesora, przez pamięć podręczną, pamięć główną, skończywszy na pamięci masowej), w której na wyższym poziomie przechowywane są dane, stanowiące fragment zawartości poziomu niższego.

• Z punktu widzenia procesu (również procesora) pamięć jest zbiorem bajtów identyfikowanych przez adresy, czyli tablicą bajtów, w której adresy są indeksami.

Przestrzeń adresowa

• Przestrzeń adresowa jest zbiór wszystkich dopuszczalnych adresów w pamięci.

• W zależności od charakteru adresu odróżnia się:

– przestrzeń fizyczną — zbiór adresów przekazywanych do układów pamięci głównej (fizycznej).

– przestrzeń logiczną — zbiór adresów generowanych przez procesor w kontekście aktualnie wykonywanego procesu.

Podział pamięci

• Podział stałyPodział pamięci na stałe obszary (strefy, partycje), których rozmiar i położenie ustalane są na etapie konfiguracji systemu.

• Przydział całego obszaru o rozmiarze większym lub równym zapotrzebowaniu, określonym w żądaniu.

• Zalety: łatwość implementacji i zarządzania

• Wady: słaba efektywność wykorzystania pamięci (fragmentacja wewnętrzna, ograniczona odgórnie liczba jednocześnie przydzielonych partycji).

– partycje o równym rozmiarze

– partycje o różnych rozmiarach

• Podział dynamiczny Podział pamięci tworzony jest w czasie pracy systemu stosownie do żądań procesów.Proces ładowany jest w obszar o rozmiarze dosyć dokładnie odpowiadającym jego wymaganiom.

• Zalety: lepsze wykorzystanie pamięci (brak fragmentacji wewnętrznej)

• Wady: skomplikowane zarządzanie, wynikające z konieczności utrzymywania odpowiednich struktur danych w celu identyfikacji obszarów zajętych oraz wolnych.

• Podział na bloki bliźniacze (zwany też metodą sąsiedzkich stert)Pamięć dostępna dla procesów użytkownika ma rozmiar 2U.

• Przydzielany blok ma rozmiar 2K, gdzie L≤K≤U.

• Początkowo dostępny jest jeden blok o rozmiarze 2U.

• Realizacja przydziału obszaru o rozmiarze s polega na znalezieniu lub utworzeniu (przez połowienie) bloku o rozmiarze 2i takim, że 2i−1 < s ≤ 2i.

2. Tworzenie obrazu procesu w pamieci

Obraz procesu w pamięci

• Tworzenie obrazu

– Kompilacja

– KonsolidacjaKonsolidacja statyczna — odniesienia do innych modułów zamieniane są na adresy w czasie tworzenia programu wykonywalnego.

• Konsolidacja dynamiczna

– w czasie ładowania — w czasie ładowania programu następuje załadowanie modułów bibliotecznych i związanie odpowiednich adresów,

– w czasie wykonania — załadowanie modułów bibliotecznych i związanie adresów następuje dopiero przy odwołaniu się do nich w czasie wykonywania programu.

– Ładowanie koduŁadowanie absolutne — program ładowany jest w ustalone miejsce w pamięci, znane w momencie tworzenia programu ładowalnego.

• Ładowanie relokowalne — fizyczna lokalizacja procesu ustalana przy ładowaniu do pamięci.

• Ładowanie dynamiczne w czasie wykonania — fizyczna lokalizacja procesu w pamięci może ulec zmianie w

czasie wykonywania.

• Relokacja

• Ochrona

Weryfikacja poprawności adresu pod kątem zakresu

dopuszczalności

• Weryfikacja praw dostępu:

– prawa zapisu

– prawa odczytu

– prawa wykonania

• Współdzielenie

Efektywność wykorzystania pamięci

– współdzielenie kodu programu

– współdzielenie kodu funkcji bibliotecznych

• Kooperacja procesów

– synchronizacja działań procesów

– komunikacja pomiędzy procesami (współdzielenie

danych)

3.Stronicowanie i segmentacja

Stronicowanie

• Arbitralny podział pamięci fizycznej na ramki, w które ładowane są odpowiednie strony obrazu procesu.

• Podział logicznej przestrzeni adresowej na strony o takim samym rozmiarze, jak ramki w pamięci fizycznej.

• Zalety:

– brak problemu fragmentacji zewnętrznej,

– wspomaganie dla współdzielenia i ochrony pamięci.

• Wady:

– narzut czasowy przy transformacji adresu,

– narzut pamięciowy (na potrzeby tablicy stron),

– fragmentacja wewnętrzna (niewielka).

Segmentacja

• Przestrzeń adresów logicznych jest postrzegana jako zbiór segmentów.

• Podstawowe atrybuty segmentu:

– identyfikator,

– adres bazowy,

– rozmiar,

– informacja o rodzaju zawartości i formach dostępu.

• Adres logiczny składa się z numeru segmentu i przesunięcia wewnątrz segmentu.

• Odwzorowanie adresów logicznych w fizyczne zapewnia tablica segmentów.

1.Pamięć wirtualna

Pamięć wirtualna jest organizacją zasobów pamięci, zrealizowaną w oparciu o tzw. przestrzeń wymiany w pamięci drugiego rzędu (na dysku). Pamięć operacyjna (fizyczna) jest dla tych zasobów tylko pewnym oknem, przechowującym część zawartości na potrzeby bieżącego przetwarzania.

2. Stronicowanie na żądanie

• Działanie mechanizmu: strony są sprowadzane dopamięci tylko wówczas, gdy jest to konieczne, czyli wówczas gdy następuje odniesienie do komórki o adresie, znajdującym się na tej stronie

• Wymaganie sprzętowe

– tablica stron z bitem poprawności (ang. valid-invalid bit) dla każdej pozycji (dodatkowo z bitem modyfikacji i odniesienia),

– mechanizm reakcji na odniesienie do strony niepoprawnej,

– urządzenie wymiany (ang. swap device) — pamięć pomocnicza.

3.Problem realizacji stronicowania na zadanie

Problem zastępowania (wymiany, ang. page replacement) stron pojawia się, gdy w pamięci fizycznej brakuje wolnych ramek i konieczne jest zwolnienie jakieś ramki poprzez usunięcie z niej strony. Jeśli strona była modyfikowana w pamięci, konieczne jest zapisanie jej w obszarze wymiany ⇒ konieczność wprowadzenia bitu modyfikacji (ang. Modify bit), zwanego też bitem zabrudzenia (ang. dirty bit).

Problem wyboru ofiary — niewłaściwy wybór ramki-ofiary powoduje wzrost kosztu wymiany.

– W skrajnym przypadku może dojść do zjawiska migotania, w przypadku którego często dochodzi do wystąpienia odniesienia do właśnie usuniętej strony.

Problem wznawiania rozkazów — w przypadkuwielokrotnego odniesienia do pamięci w jednym cyklu rozkazowym należy zapewnić, że wszystkie adresowane strony są jednocześnie dostępne w ramkach w pamięci fizycznej.

4. Algorytmy wymiany

Klasyfikacja algorytmów wymiany z względu na okoliczności sprowadzania i usuwania stron

• Algorytmy wymiany na żądanie

– sprowadzenia odbywa się na żądanie — strona sprowadzana jest dopiero wówczas, gdy następuje odniesienie do niej i nie ma jej w pamięci,

– usuwanie odbywa się na żądanie — strona usuwana jest wówczas, gdy konieczne jest sprowadzenie innej strony w wyniku odniesienia i nie ma wolnej ramki

• Algorytmy wymiany ze sprowadzaniem na żądanie

– tylko sprowadzanie dobywa się na żądanie

• Algorytmy wstępnego sprowadzania

– sprowadzana jest strona żądana, a wraz z nią inne strony

Klasyfikacja algorytmów wymiany ze względu na sposób zastępowania stron

• Zastępowanie lokalne (ang. local replacement) — algorytm wymiany zastępuje tylko strony w ramkach przydzielonych procesowi, który spowodował błąd strony.

• Zastępowanie globalne (ang. global replacement) — algorytm wymiany zastępuje strony znajdujące się w dostępnej puli ramek w całym systemie (w szczególności zatem usuwa strony innych procesów).

Klasyfikacja algorytmów wymiany ze względu na przydział ramek dla procesów

• Przydział statyczny — liczba ramek przydzielonych procesowi jest ustalona i nie ulega zmianie w trakcie przetwarzania.

• Przydział dynamiczny — liczba ramek przydzielonych procesowi może się zmienić w trakcie przetwarzania.

Algorytmy wymiany na żądanie

• MIN — zastępowana jest strona, która najdłużej nie będzie używana (optymalny w tej klasie)

• FIFO (ang. First In First Out) — zastępowana jest strona najstarsza (najwcześniej sprowadzona)

• LIFO (ang. Last In First Out) — zastępowana jest strona najmłodsza (najpóźniej sprowadzona)

• LRU (ang. Least Recently Used) — zastępowana jest najdawniej użyta strona (najdłużej nie używana)

• LFU (ang. Least Frequently Used) — zastępowana jest najrzadziej używana strona

• MFU (ang. Most Frequently Used) — zastępowana jest najczęściej używana strona

Algorytmy ze sprowadzaniem na żądanie

• VMIN — usuwane są strony, których koszt utrzymania w pamięci jest większy od kosztu ponownego sprowadzenia

• WS — usuwane są strony, do których nie było odniesień przez określony czas

• WSClock — przybliżona wersja algorytmu WS, oparta na bicie odniesienia

• PFF, VSWS — przydział i zwalnianie ramek procesów realizowane jest na podstawie częstości zgłaszania błędów strony

Algorytmy wstępnego stronicowania

• DPMIN — sprowadzane są wszystkie strony potrzebne w najbliższej przyszłości, które mieszczą się dostępnych ramkach

• OBL — sprowadzana jest strona żądana oraz strona następna (wg. numeracji w tablicy stron)

• SL — na podstawie wcześniejszych odniesień i błędów strony budowana jest tablica skojarzeń stronsprowadzanych po sobie i informacja taka wykorzystywana jest prze następny sprowadzaniu

• FDPA — podejście uwzględniające sugestie programisty co do stron potrzebnych w przyszłości

1.Urządzenia wejścia wyjscia – klasyfikacja

• Urządzenia składowania danych (dyski, dyskietki, taśmy,CD ROM, DVD itp.)

• Urządzenia transmisji danych na odległość (karty sieciowe, modemy)

• Urządzenia do komunikacji z człowiekiem (monitory, projektory, klawiatury, myszy, drukarki, skanery itp.)

• Urządzenia specjalizowane

– układy sterowania (np. elektrownią, samolotem,systemem obrony antyrakietowej itd.)

– kasy i drukarki fiskalne itp.

– urządzenia medyczne

•Tryb pracy urządzenia:

– synchroniczny — dane zostaną przekazane w znanym z góry (przewidywalnym) czasie, przykład: dysk, karta graficzna

– asynchroniczny — dane mogą zostać przesłane w dowolnym, trudnym do przewidzenia, momencie, przykład: klawiatura, karta sieciowa

• Tryb użytkowania:

– współdzielony — dopuszczalne jest współbieżne używanie urządzenia przez wiele procesów, np.: dysk

– wyłączny — niemożliwe jest współbieżne używanie urządzenia przez wiele procesów, przykład: drukarka

• Szybkość działania (transmisji)

– od bardzo wolnych, przykład: drukarka

– do stosunkowo szybkich, przykład: dysk

• Kierunek przekazywania danych

– urządzenia wejścia i wyjścia — możliwość zarówno zapisu jak i odczytu, przykład dysk, karta sieciowa

– urządzenia wejścia — tylko możliwość odczytu z urządzenia, przykład: klawiatura

– urządzenia wyjścia — tylko możliwość zapisu, przykład: drukarka

2.Interakcja jednostki centralnej z urzadzeniami we/wy

• Odpytywanie (ang. polling) — ciągłe lub okresowe sprawdzanie stanu sterownika

• Sterowanie przerwaniami (ang. interrupt-driven I/O) — inicjalizacja pracy sterownika przez procesor i obsługa urządzenia po zakończeniu działania w ramach reakcji na przerwanie

• Bezpośredni dostęp do pamięci (ang. direct memory access) — inicjalizacja pracy sterownika przez procesor i uruchomienie układu bezpośredniego dostępu do pamięci w celu realizacji transferu danych pomiędzy sterownikiem a pamięcią

3.Buforowanie

• Dopasowanie urządzeń różniących się szybkością przekazywania danych — dopasowanie chwilowo szybszego producenta danych do możliwości konsumenta.

• Dopasowanie urządzeń różniących się podstawową jednostką transmisji danych — dopasowanie w celu efektywnego przekazywania danych urządzeń przesyłających mniejsze jednostki danych do urządzeń wymagających większych jednostek lub odwrotnie (fragmentowanie).

• Semantyka kopii — zagwarantowanie niezmienności danych w czasie wykonywania operacji wejścia-wyjścia.

4.Przechowywanie podręczne

• Przechowywanie podręczne polega na gromadzeniu kopii danych w pamięci w celu poprawy efektywności ich przetwarzania.

• Przechowywanie podręczne w przypadku operacji wejścia zmniejsza czas dostępu.

• Przechowywanie podręczne w przypadku operacji wyjścia umożliwia skumulowanie wyników przetwarzania w dłuższym czasie i przekazanie ich na urządzenie zewnętrzne w wyniku jednej operacji wyjścia.

1.Pojecie pliku

• Plik jest abstrakcyjnym obrazem informacji gromadzonej i udostępnianej przez system komputerowy.

• Plik jest podstawową jednostką logiczną magazynowania informacji w systemie komputerowym, widoczną dla użytkownika.

• Plik jest nazwanym zbiorem powiązanych ze sobą informacji, zapisanym w pamięci pomocniczej.

2.Struktura katalogu

• Struktura jednopoziomowa — wpisy katalogowe poszczególnych plików znajdują się w tym samym katalogu (na tym samym poziomie).

• Struktura dwupoziomowa — wpisy katalogowe plików znajdują się w różnych katalogach, ale katalogi nie mogą zawierać innych katalogów.

• Struktura drzewiasta — w katalogach można tworzyć podkatalogi oraz pliki.

• Graf acykliczny — podkatalog (lub plik) może być umieszczony w wielu katalogach.

• Graf ogólny — dopuszcza się cykl w powiązaniach pomiędzy katalogami

3.Organizacja logiczna systemow plikow

• Podział na strefy (wolumeny, woluminy, tomy, partycje)

– strefa obejmuje część dysku, jeden lub kilka dysków,

– strefa zawiera pliki i katalogi.

• Organizacja katalogów:

– katalog jest tablicą kojarzącą nazwy plików z wpisami katalogowymi, obejmującymi inne atrybuty plików,

– katalogi mogą być jedno- lub wielopoziomowe,

– katalogi wielopoziomowe zorganizowane mogą być w różne struktury logiczne (drzewo, graf acykliczny, dowolny graf)

• Pliki identyfikowane są przez nazwy, znajdujące się w katalogach.

4.Przydzial miejscu na dysku

• Przydział ciągły (ang. contiguous allocation) — cały plik zajmuje ciąg kolejnych bloków

• Przydział listowy (łańcuchowy, ang. linked allocation, chained allocation) — bloki pliku tworzą listę powiązaną

• Przydział indeksowy (ang. indexed allocation) — bloki z danymi wskazywane są przez bloki indeksowe, któremogą być zorganizowane w:

– schemat listowy

– schemat wielopoziomowy

– schemat kombinowany

Przydział ciągły — właściwości

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

• Łatwa lokalizacja bloków pliku zarówno przy dostępie sekwencyjnym jak i bezpośrednim

• Problem fragmentacji zewnętrznej — po usuniętych plikach pozostają dziury, które trudno połączyć w jeden większy blok

• Problem rozszerzania pliku

– pliku nie da się rozszerzyć,

– będzie go trzeba przenieść w nowe miejsce (znaleźć większą dziurę)

– będzie trzeba z góry zarezerwować więcej miejsca w

przestrzeni dyskowej

Przydział listowy — właściwości

• Nie ma problemu fragmentacji zewnętrznej

• Łatwa realizacja dostępu sekwencyjnego

• Problem realizacji dostępu bezpośredniego

• Konieczność pamiętania wewnątrz bloku wskaźnika do bloku następnego

• Zawodność — utrata jednego bloku pociąga za sobą stratę wszystkich następnych

5. Zarzadzanie wolna przestrzenia

• Wektor bitowy — każdy bit odpowiada jednemu blokowi, wartość 1 oznacza wolny blok.

• Lista powiązana — każdy wolny blok zawiera indeks następnego wolnego bloku.

• Grupowanie — niektóre wolne bloki zapełnione są w całości indeksami innych wolnych bloków, ostatni indeks wskazuje na kolejny blok zapełniony w całości indeksami.

• Zliczanie — wykaz wolnych bloków obejmuje indeks pierwszego wolnego bloku oraz liczbę wolnych bloków znajdujących się za nim, stanowiących ciągły obszar.

6. Implementacje we współczesnych systemach operacyjnych

• CP/M — katalog zawiera blok kontrolny pliku (FCB), identyfikujący 16 jednostek alokacji (zawierający indeksy tych jednostek alokacji).

• DOS — wpis katalogowy zawiera indeks pierwszej jednostki alokacji, a pozostałe jednostki wynikają ztablicy FAT.

• ISO 9660 (CD ROM) — bloki zorganizowane są wg. zasady przydziału ciągłego, wpis katalogowy zawiera indeks pierwszej jednostki alokacji oraz rozmiar pliku, wpisy katalogowe są posortowane alfabetycznie.

• UNIX — plik opisany jest przez i-węzeł, wpis katalogowy zawiera indeks i-węzła, który z kolei zawiera indeks (kombinowany) jednostek alokacji.

• NTFS — plik identyfikowany jest przez referencję, która jest indeksem rekordu w tablicy MFT, rekord zawiera atrybuty pliku (w szczególności dane) lub odnośniki do bloków z atrybutami.

1.Klasyfikacja mechanizmow synchronizacji

• Zapis lub odczyt współdzielonych danych

• Złożone operacje atomowe na współdzielonych danych (np. test&set, exchange)

• Mechanizmy wspierane przez system operacyjny

– semafory

– mechanizmy POSIX (zamki oraz zmienne warunkowe)

• Mechanizmy strukturalne (wspierane przez wysokopoziomowe języki programowania)

– monitory

– regiony krytycznena operandach ze

2. Algorytm Petersona algorytm przetwarzania współbieżnego, zapewniający wzajemne wykluczenie, umożliwiające dwóm procesom lub wątkom bezkonfliktowy dostęp do współdzielonego zasobu 

shared znacznik: array [0..1] of Boolean;

shared numer: Integer;

znacznik[i] := true;

numer := j;

while znacznik[j] and numer ≠ i do

nic;

sekcja krytycznai;

znacznik[i] := false; ← sekcja wyjściowa

resztai;zbioru O ⊆

3.Algorytm Lamporta(piekarni) algorytm Leslie Lamporta rozwiązujący wykluczanie się w sekcji krytycznej dla dowolnej N liczby procesów.

Algorytm dla procesu Pi przy n procesach ( i = 0…n-1 )

shared wybieranie: array [0..n-1] of

Boolean := false;

shared numer: array [0..n-1] of Integer := 0;

local k: Integer;

wybieranie[i] := true;

numer[i] := max(numer[0],numer[1], …) + 1;

wybieranie[i] := false; D

1.Semafory

• Semafor jest zmienną całkowitą nieujemną lub — w przypadku semaforów binarnych — zmienną typu logicznego.

• Na semaforze można wykonywać dwa rodzaje operacji:

– P — opuszczanie semafora (hol. proberen)

– V — podnoszenie semafora (hol. verhogen)

• Synchronizacja polega na blokowaniu procesu w operacji opuszczania semafora, jeśli semafor jest już opuszczony.

Rodzaje semaforów

• Semafor binarny — zmienna semaforowa przyjmujetylko wartości true (stan podniesienia, otwarcia) lub false (stan opuszczenia, zamknięcia).

• Semafor ogólny (zliczający) — zmienna semaforowa przyjmuje wartości całkowite nieujemne, a jej bieżąca wartość jest zmniejszana lub zwiększana o 1 w wyniku wykonania odpowiednio operacji opuszczenia lub podniesienia semafora.

• Semafor uogólniony — semafor zliczający, w przypadku którego zmienną semaforową można zwiększać lub zmniejszać o dowolną wartość, podaną jako argument operacji.

• Semafor dwustronnie ograniczony — semafor ogólny, w przypadku którego zmienna semaforowa, oprócz dolnego ograniczenia wartością 0, ma górne ograniczenie, podane przy definicji semafora.

2.Zamek

• Zamek — umożliwia implementację wzajemnego wykluczania. Operacje:

– lock — zajęcie (zaryglowanie) zamka

– unlock — zwolnienie (odryglowanie) zamka

– trylock — nieblokująca próba zajęcia zamka

• Zmienna warunkowa — umożliwia usypianie i budzenie wątków. Operacje:

– wait — uśpienie wątku,

– signal — obudzenie jednego z uśpionych wątków

– broadcast — obudzenie wszystkich uśpionych

wątków

3.Klasyczne problemy synchronizacji

• Problem producenta i konsumenta — problem ograniczonego buforowania w komunikacji międzyprocesowej

• Problem czytelników i pisarzy — problem synchronizacji dostępu do zasobu w trybie współdzielonym i wyłącznym

• Problem pięciu filozofów — problem jednoczesnego dostępu do dwóch zasobów (ryzyko głodzenia izakleszczenia)

• Problem śpiących fryzjerów — problem synchronizacji w interakcji klient-serwer przy ograniczonym kolejkowaniu