Spis treści:

Zadania systemów operacyjnych:

Klasyfikacja systemów operacyjnych:

Proces:

Zasoby:

Wątki:

Szeregowanie procesów:

Ogólna koncepcja planowania:

Argumenty funkcji planowania:

Algorytmy szeregowania (z wywłaszczaniem i bez wywłaszczania).

Kryteria oceny algorytmów planowania:

Zarządzanie pamięcią operacyjna:

Tworzenie obrazu procesu w pamięci

Stronicowanie:

Segmentacja:

Pamięć Wirtualna

Stronicowanie na żądanie.

Problemy realizacji stronicowania na żądanie:

Algorytmy wymiany:

Kryteria oceny algorytmów planowania:

Interakcja jednostki centralnej z urządzeniami we/wy

Buforowanie:

Przechowywanie podręczne:

Pojęcie pliku:

Struktura katalogów:

Organizacja logiczna systemu plików:

Przydział miejsca na dysku:

Zarządzanie wolną przestrzenią:

Klasyfikacja mechanizmów synchronizacji.

Algorytm Petersona:

Algorytm Lamporta:

Semafory:

Zamki:

Klasyczne problemy synchronizacji:

1.Definicja, zadania, klasyfikacja systemów operacyjnych.

1.

Definicja systemów operacyjnych

:

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.

Spis treści:

Zadania systemów operacyjnych:

• Definicja interfejsu użytkownika
• Udostępnianie systemu plików
• Udostępnianie środowiska do wykonywania programów użytkownika
– mechanizm ładowania i uruchamiania programów
– mechanizmy synchronizacji i komunikacji procesów
• Sterowanie urządzeniami wejścia-wyjścia
• Obsługa podstawowej klasy błędów

Spis treści:

Klasyfikacja systemów operacyjnych:

a) Klasyfikacja systemów operacyjnych ze względu na sposób przetwarzania:

• Systemy przetwarzania bezpośredniego:
— 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:
— systemy wsadowe
– występuje znacząca zwłoka czasowa między przedłożeniem a rozpoczęciem wykonywania zadania,
– niemożliwa jest ingerencja

b) Klasyfikacja systemów operacyjnych ze względu na liczbę:

• 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.

c) Klasyfikacja systemów operacyjnych ze względu na liczbę użytkowników:

• 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ą.

Spis treści:

2. Procesy, wątki, zasoby.

1. Proces:

•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
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.

Spis treści:

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.
Klasyfikacja zasobów:
• Ze względu na sposób wykorzystania
– zasoby odzyskiwalne (zwrotne, ang. reusable),
– zasoby nieodzyskiwalne (niezwrotne, zużywalne,).
• Ze względu na sposób odzyskiwania
– zasoby wywłaszczalne,
– zasoby niewywłaszczalne.
• Ze względu na tryb dostępu
– współdzielone
– wyłączne

Spis treści:

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
• Wątek posiada własny blok kontrolny w jądrze systemu operacyjnego, obejmujący:
– stan licznika rozkazów,
– stan rejestrów procesora,
– stan rejestrów związanych z organizacją stosu.
• Własności realizacji wątków na poziomie jądra:
– przełączanie kontekstu pomiędzy wątkami przez jądro,
– większy koszt przełączanie kontekstu,
– bardziej sprawiedliwy przydział czasu procesora.

Spis treści:

3.Szeregowanie procesów. Ogólna koncepcja planowania. Argumenty funkcji planowania.
Algorytmy szeregowania (z wywłaszczaniem i bez wywłaszczania). Kryteria oceny
algorytmów planowania. Przykłady implementacji planowania przydziału procesora.

1. Szeregowanie procesów:

W środowisku systemu pracuje zwykle więcej procesów gotowych do wykonania niż dostępnych jest procesorów.
Stąd istnieje potrzeba decydowania który z procesów ma być wykonywany na którym z procesorów
Decyduje o tym procedura szeregująca (ang. scheduler). Jest to szereg funkcji zaimplementowanych w jądrze
systemu które decydują które procesy ze zbioru procesów gotowych ma być wykonywany i na którym procesorze.
Procedura szeregująca jest aktywowana gdy:
1. Wystąpiło przerwanie zegarowe – proces bieżący wykorzystał przydzielony mu kwant czasu.
2. Wystąpiło przerwanie od urządzenia zewnętrznego – proces zablokowany na operacji wejścia / wyjścia stał się
gotowy.

3. Proces bieżący wykonał wywołanie systemowe na skutek którego inny proces stał się gotowy.
4. Proces bieżący dobrowolnie oddał procesor lub zakończył się
5. Proces bieżący naruszył mechanizm ochrony procesora co spowodowało przerwanie wewnętrzne procesora.
Ze względu na wymogi szeregowania wyróżnia się trzy klasy procesów:
· Procesy interaktywne (ang. Interactive)
· Procesy wsadowe lub tła (ang. batch, background)
· Procesy czasu rzeczywistego (ang. Real Time)

Spis treści:

2. Ogólna koncepcja planowania:

Planowanie opiera się na trzech elementach, z których dwa zasadnicze to tryb decyzji oraz funkcja priorytetu:
• 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.
• Funkcja priorytetu — funkcja wyznaczająca aktualny priorytet procesu na podstawie parametrów procesu i stanu
systemu.
• Reguła arbitrażu — reguła rozstrzygania konfliktów w dostępie do procesora w przypadku procesów o tym samym
priorytecie.

Spis treści:

3. Argumenty funkcji planowania:

• Czas oczekiwania — czas spędzony w kolejce procesów gotowych (czas spędzony w stanie gotowości).
• Czas obsługi — czas, przez który proces był wykonywany (wykorzystywał procesor) od momentu przyjęcia do
systemu.
• Rzeczywisty czas przebywania w systemie — czas spędzony w systemie od momentu przyjęcia (czas obsługi + czas
oczekiwania + czas realizacji żądań zasobowych).
• Czasowa linia krytyczna — czas, po którym wartość wyników spada (nawet do zera, np. przy przewidywaniu
pogody).
• Priorytet zewnętrzny — składowa priorytetu, która pozwala wyróżnić procesy ze względu na klasy użytkowników
lub rodzaj wykonywanych zadań.
• Wymagania odnośnie wielkości przestrzeni adresowej pamięci.
• Obciążenie systemu — liczba procesów przebywających w systemie i ubiegających się (potencjalnie) o przydział
procesora lub innych zasobów, zajętość pamięci

Spis treści:

Algorytmy szeregowania (z wywłaszczaniem i bez wywłaszczania).

Bez wywłaszczenia:
• FCFS (First Come First Served) — pierwszy zgłoszony, pierwszy obsłużony - FCFS jest naturalnym algorytmem w
systemach obsługi masowej, takich jak kasy sklepowe, kasy biletowe, banki, urzędy itp. Procesy otrzymują procesor
w kolejności, w jakiej zgłosiły się do systemu.
• LCFS (Last Come First Served) — ostatni zgłoszony - Algorytm LCFS obsługuje procesy w kolejno�ci odwrotnej do
kolejności zgłoszeń. Algorytm nie wywłaszcza procesów, więc nowo przychodzący proces jest pierwszy w kolejce i
czeka na zwolnienie procesora przez bieżąco wykonywany proces pierwszy obsłużony -Algorytm SJF preferuje
procesy, które mają najmniejsze wymagania odnośnie czasu procesora, potrzebnego na realizację przetwarzania
• SJF (SJN, SPF, SPN, Shortest Job/Process First/Next)
— najpierw najkrótsze zadanie - Algorytm SJF preferuje procesy, które mają najmniejsze wymagania odno�nie
czasu procesora, potrzebnego na realizację przetwarzania.
Algorytmy wywłaszczające:
• Planowanie rotacyjne (ang. Round Robin, RR) — po ustalonym kwancie czasu proces wykonywany jest przerywany i
trafia do kolejki procesów gotowych. - Typowym algorytmem planowania wywłaszczającego jest algorytm rotacyjny.
Każdy proces wykonywany jest co najwyżej przez pewien okres czasu, po czym następuje przełączenie kontekstu na
inny proces. Po jakimś czasie nastąpi wznowienie procesu przerwanego. Proces może przed upływem kwantu czasu

zgłosić żądanie zasobowe, zrezygnować dobrowolnie z procesora lub zakończyć się, co skutkuje przydzieleniem
nowego kwantu dla następnego procesu.
• SRT (Shortest Remaining Time) — najpierw zadanie, które ma najkrótszy czas do zakończenia - SRT jest
wywłaszczającą wersją algorytmu SJF. Zakładając, że znany jest czas następnej fazy procesora dla każdego procesu,
sprawdza się, czy jakiś proces gotowy ma mniejsze wymagania odnośnie czasu procesora, niż proces aktualnie
wykonywany. Je�li tak, to podejmowana jest decyzja o wywłaszczeniu.

Spis treści:

5. 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
– sprawiedliwosć (fairness) — równe traktowanie procesów
– respektowanie zewnętrznych priorytetów procesów
– równoważenie obciążenia wykorzystania zasobów

Spis treści:

6. Przykłady implementacji planowania przydziału procesora.

4.Zarządzanie pamięcią operacyjną. Tworzenie obrazu procesu w pamięci.
Stronicowanie i segmentacja

Zarządzanie pamięcią operacyjna:

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.

Hierarchia pamięci:

Spis treści:

Tworzenie obrazu procesu w pamięci

Tworzenie obrazu procesu zaczyna się od programu źródłowego. Program taki jest kompilowany do
przemieszczalnego modułu wynikowego, a następnie łączony (konsolidowany) z modułami bibliotecznymi, do
których są odwołania w kodzie. Konsolidację można jednak odłożyć do czasu ładowania, a nawet wykonywania kodu.
Konsolidacja przed ładowaniem określana jest jako statyczna, a w jej wyniku powstaje moduł absolutny. Konsolidacja
w czasie ładowania lub wykonania określana jest jako konsolidacja dynamiczna.

Spis treści:

Stronicowanie:

Stronicowanie polega na podziale pamięci na spójne bloki ustalonej wielkości. Powoduje to znaczne ułatwienia przy
obsłudze pamięci, a także brak fragmentacji zewnętrznej , chociaż występuje fragmentacja wewnętrzna. Taki
pojedyńczy blok, na które jest podzielona pamięć nazywa się stroną, a jego wielkość określa stała PAGE_SIZE w pliku
page.h. W wersji systemu, której dotyczy ten opis ma ona wielkość 4096 (bajtów, czyli 4 kB).

Spis treści:

Segmentacja:

Segmentacja pamięci polega na podzieleniu przez procesor pamięci fizycznej na fragmenty o określonym początku,
rozmiarze, atrybutach i identyfikatorze. System tworzy takie segmenty na żądanie aplikacji, przekazując jej jedynie
identyfikatory nie pozwalające na odczytanie parametrów segmentów. Programy odwołują się zatem do kolejnych
komórek pamięci w ramach należących do nich segmentów, nie wiedząc nic o tym, w jakie miejsca pamięci fizycznej
trafiają odwołania do nich. Procesy nie mają też prawa „widzieć” segmentów należących do innych programów – w
czasie przekazywania kontroli procesowi system musi zablokować definicje segmentów należących do pozostałych
procesów, przy każdym przełączeniu blokując segmenty wyłączanego programu i na nowo uaktywniając segmenty
programu aktywowanego.

Spis treści:

1. Pamięć wirtualna. Stronicowanie na żądanie. Problemy realizacji stronicowania na

żądanie. Algorytmy wymiany

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). Stosowanie pamięci wirtualnej ma wiele zalet nie tylko związanych z możliwością
powiększenia zasobów pamięci ponad dostępną pamięć fizyczną. Umożliwia bardziej racjonalne wykorzystanie
pamięci operacyjnej, gdyż programy tworzone są często z nadmiarem w stosunku do typowych potrzeb.

Spis treści:

Stronicowanie na żądanie.

Stronicowanie na żądanie związane jest przede wszystkim z wymianą stron pomiędzy pamięcią pierwszego rzędu
(operacyjną, fizyczną) i drugiego rzędu (masową, dyskową). Dzięki wykorzystaniu pamięci masowej można
rozszerzyć wirtualną przestrzeń adresową i tym samym zwiększyć stopień wieloprogramowości lub uruchamiać
zadania, których rozmiar wykracza poza dostępną pamięć operacyjną. Kosztem wprowadzenia takiego
mechanizmu jest złożoność zarządzania pamięcią i narzut czasowy związany z dostępem, wynikający z
wykorzystania stosunkowo wolnej pamięci dyskowej.

Spis treści:

Problemy realizacji stronicowania na żądanie:

Realizacja pamięci wirtualnej oprócz wsparcia sprzętowego wymaga rozwiązania dwóch zasadniczych
problemów na poziomie systemu operacyjnego:
• problemu wyboru ramki ofiary do wymiany strony, jeśli zajdzie potrzeba wymiany,
• problemu wznawiania rozkazów, którego rozwiązanie sprowadza się do zapewnienia dostępności odpowiednio
dużej liczby ramek dla procesu.

Spis treści:

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.

Spis treści:

2. Urządzenia wejścia wyjścia - klasyfikacja. Interakcja jednostki centralnej z

urządzeniami we/wy. Buforowanie, przechowywanie podręczne.

Urządzenia wejścia wyjścia – 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 antyrakietowejitd.),

– kasy i drukarki fiskalne itp.,
– urządzenia medyczne.

Spis treści:

Interakcja jednostki centralnej z urządzeniami we/wy

•Odpytywanie (polling) — ciągłe lub okresowe sprawdzanie stanu sterownika.
• Sterowanie przerwaniami (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 (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ą.

Spis treści:

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

Spis treści:

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.

Spis treści:

3. Warstwa logiczna - pojęcie pliku, struktura katalogu, organizacja logiczna systemu

plików. Warstwa fizyczna – przydział miejsca na dysku, zarządzanie wolną
przestrzenią

Pojęcie 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.
Atrybuty pliku:
• Nazwa — ciąg znaków służących użytkownikowi do identyfikacji pliku
• Typ — informacja służąca do rozpoznania rodzaju zawartości pliku i tym samym sposobu interpretacji
• Lokalizacja — informacja służąca do odnalezienia pliku w systemie komputerowym (urządzenie i położenie pliku w
tym urządzeniu)
• Rozmiar — bieżący rozmiar pliku w ustalonych jednostkach (bajtach, słowach, blokach itp.)
• Ochrona — informacje umożliwiające kontrolę dostępu
• Czasy dostępów — daty i czasy wykonywania pewnych operacji na pliku, typu odczyt, modyfikacja, utworzenie

• Podstawowe operacje na plikach:
• Tworzenie pliku — konieczne jest określenie podstawowych atrybutów pliku, znalezienie miejsca na ten plik w
systemie komputerowym oraz jego zaewidencjonowanie (utworzenie wpisu katalogowego)
• Zapis do pliku — konieczne jest określenie, co ma być zapisane i gdzie ma być zapisane (w którym pliku i w jakim
miejscu tego plik, zależnie od sposobu dostępu)
• Odczyt z pliku — konieczne jest określenie, co ma być odczytane (z którego pliku i z jakiego miejsca tego plik,
zależnie od sposobu dostępu) i gdzie mają być umieszczone odczytane dane
• Usuwanie informacji z pliku — należy określić jaki fragment pliku (i którego pliku) ma być usunięty.
Najczęściej możliwe jest tylko skracanie pliku, czyli usuwanie jego końcowej zawartości lub całej jego zawartości.
• Usuwanie pliku — należy określić plik do usunięcia. Usuwana jest zawartość oraz wpis ewidencyjny pliku.
• Dodatkowe operacje na plikach, wykonywane w celu uzyskania dostępu do zawartości pliku:

– otwieranie,
– zamykanie,
– przesuwanie wskaźnika bieżącej pozycji.

Spis treści:

Struktura katalogów:

• 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
Operacje:
•Tworzenie katalogu
• Usuwanie katalogu
• Tworzenie wpisu katalogowego — gdy tworzony jest plik, jego nazwa alternatywna, podkatalog itp.
• Usuwanie wpisu katalogowego
• Przemianowanie pliku (zmiana nazwy)
• Odnajdowanie wpisu katalogowego
• Tworzenie wykazu wpisów katalogowych (listing zawartości)

Spis treści:

Organizacja logiczna systemu plików:

•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.

Spis treści:

Przydział miejsca na dysku:

Przestrzeń dyskowa na potrzeby systemu plików zorganizowana jest w jednostki alokacji, zwane krótko blokami. Blok
jest wielokrotnością sektora dysku. W zakresie przydziału miejsca dla pliku na dysku, czyli powiązania bloków z
plikiem, omówione są trzy podejścia: przydział ciągły, listowy i indeksowy.
• 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óre
mogą być zorganizowane w:
– schemat listowy
– schemat wielopoziomowy
– schemat kombinowany

Spis treści:

Zarządzanie wolną przestrzenią:

Zarządzanie wolną przestrzenią sprowadza się do identyfikacji bloków, które nie są przydzielone i mogą zostać
wykorzystane dla nowo tworzonych lub rozszerzanych plików. Wolne bloki można wykorzystać do tymczasowego
przechowywania danych na potrzeby zarządzania. Dlatego część stosowanych rozwiązań przypomina przydział
bloków na potrzeby plików. Można więc powiedzieć, że w tych podejściach wolna przestrzeń jest plikiem
składającym się z wolnych bloków.
• 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.

Spis treści:

1. Implementacje we współczesnych systemach operacyjnych:

4. Klasyfikacja mechanizmów synchronizacji. Algorytmy Petersona i Lamporta.

Klasyfikacja mechanizmów synchronizacji.

Wśród mechanizmów synchronizacji można wyodrębnić dwie zasadnicze klasy:
• mechanizmy sprzętowe — wspierane przez rozwiązania na poziomie maszynowym procesora (lub architektury
komputera), związane z listą rozkazów i obsługą przerwań,
• mechanizmy systemowe — zintegrowane z systemem operacyjnym i związane z odpowiednim zarządzaniem
procesami.

Spis treści:

Algorytm Petersona:

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 (sekcji krytycznej). Algorytm
Petersona zapewnia wzajemne wykluczanie tylko dla dwóch procesów, istnieje jednak uogólniona postać algorytmu
do zastosowania z wieloma procesami: algorytm piekarniany.

Spis treści:

Algorytm Lamporta:

Algorytm Lamporta jest rozproszonym algorytmem synchronizacji wzajemnego wykluczania, wykorzystującym
znaczniki czasu Lamporta. Każdy proces przechowuje kolejkę żądań sekcji krytycznej uszeregowanych według
znaczników czasowych. Algorytm ten wymaga, aby wiadomości dostarczane były pomiędzy każdą parą procesów w
kolejności FIFO.

Spis treści:

5. Semafory, zamki. Klasyczne problemy synchronizacji.

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.

1.

Rodzaje:

• Semafor binarny — zmienna semaforowa przyjmuje tylko 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.

Spis treści:

Zamki:

• Zamki są podobne do semaforów binarnych i używane są do zapewnienie wzajemnego wykluczania
Operacje:
– lock — zajęcie (zaryglowanie) zamka
– unlock — zwolnienie (odryglowanie) zamka
– trylock — nieblokująca próba zajęcia zamka

Spis treści:

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 i zakleszczenia)
• Problem śpiących fryzjerów — problem synchronizacji w interakcji klient-serwer przy ograniczonym kolejkowaniu

Spis treści: