Szamotanie – to zmniejszenie wykorzystania procesora przy zwiększeniu stopnia
wieloprogramowości (wykonywanie przesyłania pomiędzy pamięcią operacyjną a dyskiem).
Aby zapobiec szamotaniu, należy przydzielić procesowi tyle ramek, ile potrzebuje – jak się o
tym dowiedzieć?
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.
zasada wiedzy koniecznej: 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.
Struktura klient-serwer:
• Przykładem takiego systemu jest Windows NT,
• 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.
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ę.
Procesy wędrują pomiędzy różnymi kolejkami.
Wątki (threads):
• Wątek (thread), zwany także procesem lekkim (light-weight process – LWP), jest
podstawową jednostką wykorzystania CPU – posiada: licznik rozkazów, zbiór
rejestrów i obszar stosu,
• Wątek dzieli wraz z innymi równorzędnymi wątkami: sekcję kodu, sekcję danych oraz
zasoby systemowe (otwarte pliki, sygnały itd.) – łącznie nazywa się to zadaniem.
• Tradycyjny proces, tzw. ciężki (heavy-weight), jest równoważny zadaniu z jednym
wątkiem,
• Zadanie nic nie robi, jeśli nie ma w nim ani jednego wątku. Wątekmoże przebiegać
dokładnie w jednym zadaniu.
• Zalety wątków:
o Dzielenie zasobów sprawia, że przełączanie między wątkami oraz tworzenie
wątków jest tanie w porównaniu z procesami ciężkimi,
o Oszczędne wykorzystanie zasobów – dzięki ich współużytkowaniu,
o Współpraca wielu wątków pozwala zwiększyć przepustowość i poprawić
wydajność (np. jeśli jeden wątek jest zablokowany, to może działać inny),
o Wykorzystanie architektury wieloprocesorowej (wątek –> procesor)
bash długość stringa ${#zmienna}
Zarządzanie wolną przestrzenią:
• Należy dbać o wtórne zagospodarowanie dla nowych plików przestrzeni po plikach
usuniętych,
• System utrzymuje listę wolnych obszarów,
• Odnotowywane są wszystkie bloki, które są wolne,
• Utworzenie pliku,
• Usunięcie pliku.
Zarządzenie wolną przestrzenią:
• Lista wolnych obszarów (free-space list)
o Wektor binarny
o Lista powiązana
o Grupowanie
o Zliczanie
Wektor bitowy:
Każdy blok dyskowy jest reprezentowany przez jeden bit w wektorze bitowym superbloku.
Wartość 1 oznacza, że dany blok jest wolny, natomiast wartość 0oznacza, że dany blok jest
zajęty. Rozwiązanie jest mało wydajne, dopuszczalne tylko dla małych dysków.
Lista powiązana:
Powiązanie wszystkich wolnych bloków w ten sposób, że w bloku poprzednim znajduje się
indeks bloku następnego. W systemie plików jest wyznaczone miejsce, gdzie znajduje się
indeks pierwszego wolnego bloku. Wszystkie pozostałe wolne bloki są powiązane w postaci
listy, indeks do bloku następnego znajduje się w kilku ostatnich bajtach bloku poprzedniego.
Metoda niewydajna, aby przejrzeć listę, należy odczytać każdyblok.
Grupowanie:
Pierwszy wolny blok zawiera indeksy n innych wolnych bloków, z których n-1 dotyczy
wolnych bloków do alokacji, a n-ty blok zawiera znowu n-1 indeksów kolejnych wolnych
bloków. Umożliwia to szybkie odnajdywanie większej liczby wolnych bloków.
Zliczanie:
W przypadku kilku kolejnych (przylegających do siebie) wolnych bloków pamiętany jest tylko
indeks pierwszego z nich oraz liczba wolnych bloków znajdujących się bezpośrednio za nim.
Wykaz wolnych obszarów jest ciągiem wpisów składających się z indeksu bloku oraz licznika
– ma formę uporządkowanych par
Efektywny czas dostępu:
Oznaczmy przez p prawdopodobieństwo braku strony.
Efektywny czas dostępu (effective access time (EAT)) do pamięci stronicowanej – średni czas
wymagany na obsługę odwołania do pamięci (pewna miara sprawności).
EAT = (1-p)*(czas dostępu do pamięci) + p*(narzut związany z przerwaniem braku strony –
zwolnienie ramki[zapisanie na dysk], wczytanie z dysku żądanej strony, narzut związany ze
wznowieniem procesu)
Algorytm optymalny (OPT):
• zastąp tę stronę, która najdłużej nie będzie używana,
• algorytm OPT ma najniższy współczynnik braków strony ze wszystkich algorytmów,
• jest wolny od anomalii Belady’ego,
• jest trudny w realizacji, gdyż wymaga wiedzy o przyszłej postaci ciągu odniesień,
której nie mamy,
• jest używany głównie w studiach porównawczych jako punkt odniesienia.
Algorytm LRU:
• Algorytm zastępowania najdawniej używanych stron (least recently used – LRU),
używa niedawnej historii do oszacowania najbliższej przyszłości,
• Lepszy od algorytmu FIFO (mniej braków stron) i wolny od anomalii Belady’ego –
często stosowany,
• Trudność z zapamiętywaniem historii użycia stron – może wymagaćsporego zaplecza
sprzętowego,
• Algorytm LRU, podobnie jak OPT, należy do klasy algorytmów stosowych:zbiór stron
w pamięci przy n ramkach jest zawsze podzbiorem zbioru stron w pamięci przy n+1
ramkach.
Algorytmy przybliżające LRU:
• Niewiele systemów posiada odpowiedni sprzęt umożliwiających realizację algorytmu
LRU – często stosowane są algorytmy przybliżające metodę LRU:
o algorytm bitów odniesień,
o algorytm dodatkowych bitów odniesień,
o algorytm drugiej szansy.
Algorytm bitów odniesień:
• Z każdą pozycją w tablicy stron związany jest bit odniesienia ustawiony na początku
na 0,
• Przy odwołaniu do strony jest on sprzętowo ustawiany na 1,
• Zastępowana jest ta strona w porządku FIFO, która ma bit odniesienia ustawiony na
0.
Algorytm dodatkowych bitów odniesień:
• Z każdą stroną skojarzony jest 8-bitowy rejestr ustawiony na początek na 00000000.
• W regularnych odstępach czasu, np. co 100ms, so wprowadza na najbardziej
znaczącą pozycję rejestru bit odniesienia,
• Wymieniana jest strona najdawniej używana – najmniejsza liczba w rejestrze, np.
0111010<1100010,
• Jeśli kilka stron ma taką samą wartość rejestru, następuje wymiana wszystkich lub
według zasady FIFO.
Algorytm drugiej szansy (zegarowy):
• Strony przeglądane są w porządku FIFO,
• Sprawdzenie bitu odniesienia:
o jeśli 0 – strona zastąpiona
o jeśli 1 – „druga szansa”
• Druga szansa – zerowanie bitu odniesienia, ustawienie czasu bieżącego (koniec
kolejki),
• Przewijanie stron dokonuje się cyklicznie,
• Strona często eksploatowana – nigdy nie będzie zastąpiona.
Przydział ramek:
• zastępowanie globalne – proces może wybierać ramki do zastąpienia ze zbioru
wszystkich ramek – jeden proces może odebrać ramkę drugiemu,
• zastępowanie lokalne – proces może wybierać ramki tylko z własnego zbioru
przydzielonych ramek – gorsza przepustowość, rzadziej stosowany.
UNIX – stany procesu:
Stan procesu opisany w strukturze procesu może przyjmować następujące wartości:
SIDL– stan pośredni podczas tworzenia procesu
SRUN– wykonywany
SSLEEP – oczekujący (na zdarzenie)
SSTOP– zawieszony (proces jest zatrzymany przez sygnał lub proces macierzysty)
SZOMB– stan pośredni podczas usuwania procesu