Systemy operacyjne
Skrypt do wykładu
Opracowanie: Efcia
Systemy operacyjne  skrypt do wykładu Autor: Efcia
WST
P
Niniejszy skrypt powstał w celu uporządkowania wiadomości z zakresu systemów operacyjnych. Mam
nadzieje, że okaże się pomocy w zaliczeniu przedmiotu, a także poszerzy Waszą wiedzę.
Skrypt powstał na podstawie:
Materiałów dr Juszczyszyna (rozdziały 1-4 oraz początek rozdziału 5)
Notatek sporządzonych na podstawie wykładu dr Juszczyszyna
A. Silbershatz, J.L. Peterson, P.B. Galvin, Podstawy systemów operacyjnych
A.S. Tannenbaum, Rozproszone systemy operacyjne
Mam nadzieje, że docenicie ten skrypt, ponieważ opracowanie tego materiału (który jest dosyć
rozległy) kosztowało mnie sporo czasu i wysiłku.
Przyjemnej lektury.
Efcia
2
Systemy operacyjne  skrypt do wykładu Autor: Efcia
SPIS TREŚCI
Rozdział 1: Systemy operacyjne& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & .& & & & & 4
Historia systemów operacyjnych& & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & .& & .5
Ogólna struktura systemów operacyjnych& & & & & & & & & & & & & & & & & & & & & & & & & & ...8
Rozdział 2: Procesy i wątki& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & & ..10
Proces& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ...& & ..& .10
Wątek& & & & & & & & ..& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & .& .& & & 11
Rozdział 3: Procesy  zagadnienia planowania& & & & & & & & & & & & & & & & & & & .& & & & ..& ..& & & & .13
Planowanie& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .13
Algorytmy planowania& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & & 14
Struktura kolejek w systemie operacyjnym (planowanie wielopoziomowe)& & & & ..& & ..15
Rozdział 4: Koordynacja procesów& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & & & ..& & 17
Sekcje krytyczne& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .17
Semafory& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & ..18
Blokady& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ..& ..& 18
Zapobieganie i usuwanie blokad& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & 20
Wykrywanie i wychodzenie z blokady& & & & & & & & & & & & & & & & & & & & & & & & & .& & & & 22
Rozdział 5: Zarządzanie pamięcią& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & & 23
Założenia wstępne& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & & 23
Wymiana& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & & 23
Zarządzanie pamięcią operacyjną& & & & & & & & & & & & & & & & & & & & & & ..& & & & & & & & & 24
Segmentacja pamięci operacyjnej& & & & & & & & & & & & & & & & & & & & & & .& & & & & & & & & 25
Stronicowanie& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & & & & & 26
Algorytmy zastępowania stron& & & & & & & & & & & & & & & & & & & & & & & & & .& & & & & & & & 28
Zasada lokalności odwołań& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & 29
Algorytmy przydziału ramek& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& .29
Sposoby likwidacji szamotania& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .30
Rozdział 6: Struktura pamięci masowej& & & & & & & & & & & & & & & & & & & & & & ..& & & & & & & & & & & & 31
Twardy dysk& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 31
Obsługa ciągu zgłoszeń& & & & & & & & & & & & & & & & & & & & & & & & & ..& & & & & & & & & & & & 31
Zarządzanie wolnym obszarem dysku& & & & & & & & & & & & & & & & & & .& & & & & & & & & & & 33
Zapisywanie plików na dysku& & & & & & & & & & & & & & & & & & & & & & & & .& & & & & & & & & & 34
Rozdział 7: Bezpieczeństwo w systemach operacyjnych& & & & & & & & & & & & & & & & & & & & & & & & & 37
Kontrola dostępu& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 37
Podział systemów operacyjnych ze względu na politykę bezpieczeństwa& & & & & & & & & 38
Rozdział 8: Rozproszone systemy operacyjne& & & & & & & & & & & & & & & & & & & & & & & & ..& & & .& & & 41
Synchronizacja& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & 42
Strategie synchronizacji zegarów& & & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & & 43
Synchronizowanie działania procesorów& & & & & & & & & & & & & & & & & & & & & & & & & .& & 46
Metody implementacji transakcji& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 46
Blokady& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & 49
Zarządzanie procesami w systemach rozproszonych& & & & & & & & & & & & & ..& & & & & & & 50
Przykładowe algorytmy przydziału procesora& & & & & & & & & & & & & & & & & & & & & & & & & 51
Dochodzenie do uzgodnień w systemie& & & & & & & & & & & & & & & & & & & & .& & & & & & & & 52
Rozproszone systemy plików& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & & & 53
Spójność pamięci operacyjnej& & & & & & & & & & & & & & & & & & & & & & & & & & & ..& & & & & & 54
Rozdział 9: Inne systemy& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & .& & & & & 57
Lokalizacja i nazewnictwo zasobów& & & & & & & & & & & & & & & & & & & ..& ..& & & & & & & & & 57
Routing i lokalizacja zasobów& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 58
Internet Mapping Project& & & & & & & & & & & & & & & & & & & & & & & & & & & .& & & & & & & & & 60
3
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ROZDZIAA
1 - SYSTEM OPERACYJNY
System operacyjny (najprościej) - program, który pośredniczy między użytkownikiem komputera a
sprzętem.
ZADANIA SYSTEMU OPERACYJNEGO
" Ukrywa szczegóły sprzętowe systemu komputerowego poprzez tworzenie abstrakcji (maszyn
wirtualnych). przykłady:
o jednolity sposób dostępu do urządzeń zewnętrznych
o zbiory bloków dyskowych widziane jako pliki o symbolicznych nazwach
o duża, szybka, dedykowana pamięć operacyjna
o współbieżne wykonanie programów (jako abstrakcja równoległości)
" Zarządzanie zasobami:
o zasoby to  obiekty niezbędne do wykonania programu, np. pamięć, czas CPU, wejście-wyjście,
porty komunikacyjne (wszystko co przedstawia wartość funkcjonalna dla systemu)
o strategie przydziału i odzyskiwania zasobów (zarządzanie pamięcią, zarządzanie procesorem,
zarządzanie plikami, zarządzanie urządzeniami)
o efektywność zarządzania zasobami decyduje o wydajnej eksploatacji sprzętu komputerowego
" Dostarcza  przyjazny interfejs
o wygoda użycia (ustawianie przełączników, karty perforowane, taśmy perforowane, terminale
graficzne z myszką i klawiaturą)
SKA
ADOWE SYSTEMU KOMPUTEROWEGO
" Sprzęt - podstawowe zasoby obliczeniowe (CPU, pamięć, urządzenia we-wy)
USER
APLIKACJE
USER
SYST. OPER.
SPRZ
T
USER
" System operacyjny - nadzoruje i koordynuje posługiwanie się sprzętem
" Programy użytkowe - określają sposób użycia zasobów systemu do rozwiązania zadań stawianych
przez użytkowników
" Użytkownicy (ludzie, maszyny, inne komputery, programy zewnętrzne)
4
Systemy operacyjne  skrypt do wykładu Autor: Efcia
HISTORIA SYSTEMÓW OPERACYJNYCH
WCZESNE SYSTEMY OPERACYJNE   GOA
Y SPRZ
T
" Struktura:
o wielkie maszyny obsługiwane za pośrednictwem konsoli
o dla jednego użytkownika (konieczność harmonogramów pracy etc.)
o programista/użytkownik pełnił rolę operatora
o nieefektywne wykorzystanie kosztownych zasobów
o niskie wykorzystanie CPU
o pełna sekwencyjność pracy urządzeń
o przestoje sprzętu związane z wykonywaniem czynności operatorskich
" Wczesne oprogramowanie
o asemblery, programy ładujące, programy łączące, biblioteki typowych funkcji, kompilatory,
programy sterujące urządzeń
SYSTEMY WSADOWE
" Zatrudnienie operatora (użytkownik oraz operator)
" Skrócenie czasu instalowania zadania przez przygotowywanie wsadu zadań o podobnych
wymaganiach
" Automatyczne porządkowanie zadań - automatyczne przekazywanie sterowania od jednego
zadania do drugiego
" Rezydentny monitor:
o początkowo sterowanie należy do monitora
o przekazanie sterowania do zadania
o po zakończeniu zadania sterowanie wraca do monitora
" Wprowadzenie kart sterujących (Job Control Language)
o Istotna zmiana trybu pracy z punktu widzenia użytkownika
o Zwiększona przepustowość systemu kosztem średniego czasu obrotu zadania
o Problem: niska wydajność (CPU i urządzenia we-wy nie mogą pracować równocześnie, czytnik
kart bardzo wolny) Rozwiązanie: praca w trybie pośrednim (off-line)
" Zastosowanie czytników taśm magnetycznych:
o Przyspieszenie obliczeń poprzez ładowanie zadań do pamięci z taśm oraz czytanie kart i
drukowanie wyników wykonywane off-line
o Komputer główny nie jest ograniczony prędkością pracy czytników kart i drukarek, a jedynie
prędkością szybszych stacji taśmowych
o Nie są potrzebne zmiany w programach użytkowych przy przejściu do trybu pracy
pośredniej
o Możliwość używania wielu systemów czytnik-taśma i taśma-drukarka dla jednego CPU
5
Systemy operacyjne  skrypt do wykładu Autor: Efcia
BUFOROWANIE
" Metoda jednoczesnego wykonywania obliczeń i operacji we-wy dla jednego zadania:
o Nie eliminuje całkowicie przestojów CPU czy urządzeń we-wy
o Wymaga przeznaczenia pamięci na systemowe bufory
o Niweluje wahania w czasie przetworzenia danych
SPOOLING (simultaneous peripheral operation on-line)
" Metoda jednoczesnego wykonywania we-wy jednego zadania i obliczeń dla innych zadań
o Możliwe dzięki upowszechnieniu się systemów dyskowych Podczas wykonania jednego
zadania system operacyjny czyta następne zadanie z czytnika kart na dysk (kolejka zadań)
oraz np. drukuje umieszczone na dysku wyniki poprzedniego zadania
o Pula zadań - możliwość wyboru kolejnego zadania do wykonania
o Dalsza rozbudowa systemu operacyjnego (moduł wczytujący, moduł sterujący, moduł
wypisujący)
6
Systemy operacyjne  skrypt do wykładu Autor: Efcia
SYSTEMY Z PODZIAA
EM CZASU
" Procesor wykonuje na przemian wiele różnych zadań, przy czym przełączenia następują tak
często, że użytkownicy mogą współdziałać z programem podczas jego wykonania
o Interakcja użytkownika z systemem komputerowym (zadanie interakcyjne składa się z wielu
krótkich działań)
o System plików dostępnych bezpośrednio (dostęp do programów i danych)
o Wymiana zadania między pamięcią i dyskiem (ang. swapping)
SYSTEMY RÓWNOLOGA
E
" Systemy wieloprocesorowe z więcej niż jednym CPU.
o Systemy - procesory dzielą pamięć i zegar; komunikacja zwykle poprzez pamięć dzieloną
o Korzyści: zwiększona przepustowość, ekonomiczne, zwiększona niezawodność
" Symetryczna wieloprocesowość (każdy procesor wykonuje identyczną kopię systemu
operacyjnego, wiele procesów może się wykonywać równocześnie, bez spadku wydajności).
" Asymetryczna wieloprocesowość (każdy procesor wykonuje przydzielone mu zadanie; procesor
główny szereguje i przydziela pracę procesorom podrzędnym  rozwiązanie stosowane w dużych
systemach).
" Możliwe rozproszenie systemów wieloprocesorowych.
SYSTEMY CZASU RZECZYWISTEGO
" Ostre wymagania czasowe
" Sprzężenie zwrotne z działaniami użytkownika/sprzętu.
" Przykłady: sterowanie procesami przemysłowym, monitorowanie stanu zdrowia pacjenta...
Rozwój sprzętu: (cztery generacje): lampy, tranzystory, układy scalone małej skali integracji, układy
scalone dużej skali integracji
WYMAGANIA SPRZ
TOWE DLA WSPÓA
CZESNYCH SYSTEMÓW
" system przerwań (tablice przerwań, podczas wykonywania przerwania inne są wyłączone, ew.
istnieje priorytet przerwań).
" bezpośredni dostęp do pamięci (DMA) dla szybkich urządzeń we-wy
" ochrona pamięci (operacje we-wy tylko za pośrednictwem s.o., ochrona tablicy przerwań i
systemu, wzajemna ochrona zadań np. rejestry bazowy i graniczny)
" wielostanowość procesora
" rozkazy uprzywilejowane
" zegar
GENERACJE SYSTEMÓW OPERACYJNYCH
" Lata 40. Brak systemów operacyjnych w obecnym znaczeniu tego słowa
" Lata 50. Możliwość przetwarzania wsadowego
" Wczesne lata 60. Wieloprogramowość, wieloprocesowość, niezależność urządzeń, podział czasu,
przetwarzanie w czasie rzeczywistym.
7
Systemy operacyjne  skrypt do wykładu Autor: Efcia
" Połowa lat 60., do połowy lat 70. Systemy ogólnego przeznaczenia umożliwiające jednocześnie
różne tryby pracy
" Obecnie: Komputery osobiste, stacje robocze, systemy baz danych, sieci komputerowe, systemy
rozproszone
OGÓLNA STRUKTURA SYSTEMU OPERACYJNEGO
MODUA
Y FUNKCJONALNE SYSTEMU OPERACYJNEGO
" zarządzanie pamięcią
" zarządzanie procesorem (na poziomie zadań i procesów  dostepne operacje na procesach:
create, terminate, abort, signal, allocate/free memory)
" zarządzanie urządzeniami (operacje attach/detach, request/release, read/write)
" zarządzanie informacją (system plików  operacje: create, delete, open, close, change attributes)
" jądro (m.in. zapewnienie komunikacji między komponentami systemu oraz ochrony)
NAJPROSTRZA STRUKTURA (MONOLITYCZNT S. O.)
" program złożony z wielu procedur, każda może wołać każdą, ograniczona strukturalizacja (np.
OS/360, MS-DOS, niektóre wersje Unix)
makrojądro - wszystkie funkcje SO umieszczone w jądrze i wykonywane w trybie uprzywilejowanym
(np. OS/360)
jądro - część funkcji przeniesiona z jądra na poziom użytkownika (np. w systemie Unix: jądro i
programy systemowe)
STRUKTURA WARSTWOWA
Każda warstwa spełnia funkcje zależne tylko od warstwy poniżej (T.H.E., RC-4000, VMS); w Multicsie
odmiana struktury warstwowej - zespół koncentrycznych pierścieni. Wykorzystywane makrojądro -
wszystkie warstwy są uprzywilejowane. Struktura warstwowa (system T.H.E.):
" poziom 5: programy użytkowników
" poziom 4: buforowanie urządzeń we-wy
" poziom 3: program obsługi konsoli operatora
" poziom 2: zarządzanie pamięcią
" poziom 1: planowanie przydziału procesora
" poziom 0: sprzęt
STRUKTUA MIKROJ
DRA
Mikrojądro obejmuje jedynie tworzenie procesów, komunikację międzyprocesową, mechanizmy (ale
nie strategie!), zarządzanie pamięcią, procesorem i urządzeniami (na najniższym poziomie), np.
Mach, QNX (ogólnie  systemy przemysłowe)
STRUKTURA TYPU KLIENT-SERWER
" Moduły pełnią wyodrębnione zadania, komunikują się poprzez wysyłanie komunikatów.
8
Systemy operacyjne  skrypt do wykładu Autor: Efcia
" Serwer: dostarcza usługę, klient: żąda usługi. Prosta adaptacja do systemów rozproszonych.
" konieczny bezpołączeniowy protokół typu pytanie-odpowiedz

" jądro można zredukować do 2 odwołań do systemu (nadaj/odbierz komunikat)
" łatwa realizacja rozpraszania
KONCEPCJA MASZYNY WIRTUALNEJ
" każdy proces otrzymuje (wirtualną) kopię komputera będącego podstawą systemu; każda
wirtualna maszyna jest identyczna z rzeczywistym sprzętem, więc każda może wykonywać
dowolny system operacyjny; np. VM dla dużych komputerów firmy IBM
" Korzyści: każda część systemu jest dużo mniejsza, bardziej elastyczna i łatwiejsza w utrzymaniu.
CMS - system operacyjny dla indywidualnego użytkownika
9
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ROZDZIAA
2  PROCESY I W
TKI
PROCES
Proces - program (kod binarny) w czasie wykonania; wykonanie przebiega sekwencyjnie (wyjątek:
procesy wielowątkowe  patrz niżej).
" Procesy wykonują się współbieżnie (ale niekoniecznie równolegle  podział czasu)
" Stany procesu:
o nowy: proces został utworzony
o wykonywany: są wykonywane instrukcje procesu
o oczekujący: proces czeka na wystąpienie zdarzenia
o gotowy: proces czeka na przydzielenie procesora
o zakończony: proces zakończył wykonanie
REPREZENTACJA PROCESU W SYSTEMIE (ZAWARTOSC BLOKU KONTROLNEGO PROCESU)
" stan procesu
" identyfikator (unikalny numer  w UNIX ie  PID)
" licznik rozkazów
" rejestry procesora
" wskaz
nik do kolejki procesów
" informacje o pamięci zajętej przez proces
" wykaz otwartych (używanych plików)
TWORZENIE PROCESU
" za pomocą funkcji systemowej (np. fork() w UNIX)
" proces utworzony przez inny proces (macierzysty, ew. rodzic) nazywamy potomnym.
" potomek uzyskuje nową pulę zasobów lub korzysta z zasobów rodzica (mniejsze przeciążenie
systemu).
10
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ZAKOC
CZENIE PROCESU
" po ostatniej instrukcji.
" specjalna funkcją (np. exit() w UNIX)
" na żądania rodzica ( abort() )
" niekiedy: zakończenie kaskadowe: po zakończeniu rodzica kończone są procesy potomne.
W
TEK
Wątek sterowania (tzw. lekki proces): sekwencja instrukcji; tradycyjnie proces = jeden wątek
sterowania, jednak czasami (w niektórych systemach) w przestrzeni adresowej procesu dopuszcza
więcej wykonywanych współbieżnie wątków sterowania.
" wątek ma te same podst. cechy co proces (stany, możliwość tworzenia wątków potomnych,
korzystania z urządzeń zewn. itd...)
" między wątkami tego samego procesu nie ma ochrony pamięci.
" analogia: maszyna-procesy == proces-wątki
" elementy wątku i procesu:
Wątek Proces
licznik rozkazów przestrzeń adresowa
stos otwarte pliki, semafory
rejestry procesora zmienne globalne
lista wątków potomnych lista proc. potomnych
" Tradycyjny proces (ciężki) jest równoważny zadaniu z jednym wątkiem
" Jeżeli zadanie składa się z wielu wątków, to w czasie gdy jeden wątek jest zablokowany, może się
wykonywać inny wątek tego zadania; współpraca wielu wątków w jednym zadaniu pozwala
zwiększyć przepustowość i poprawić wydajność
" Wątki umożliwiają połączenie równoległości z sekwencyjnym wykonaniem:
(1) model dyspozytor-pracownik
(2) model zespołu
(3) model potoku
11
Systemy operacyjne  skrypt do wykładu Autor: Efcia
W
TKI STATYCZNE/DYNAMICZNE
Struktura wątków procesu jest ustalona (w kodzie z
r. procesu) lub też proces może dowolnie
tworzyć/usuwać swoje wątki
IMPLEMENTACJA W
TKÓW W SYSTEMIE OPERACYJNYM
" Pakiet wątków : zbiór elementarnych działań na wątkach dostępnych w systemie (np. procedur
bibliotecznych.
" Implementacja wątków w przestrzeni użytkownika:
o jądro nie wie o wątkach, widzi tylko jednowątkowe procesy
o zaleta1: można używać wątków w systemie, który ich nie implementuje (np. pierwotnie
UNIX)
o możliwe szybkie przełączanie wątków  tylko przeładowania wsk. stosu i instrukcji oraz
rejestrów (najszybsze działania w syst. komputerowym).
o zaleta2:każdy proces może używać własnego alg. planowania dla swoich wątków.
o problem1: przy blokowanych odwołaniach wątków do systemu  proces nie może oddać
sterowania systemowi, musi czekać na swoje wątki. Używa się kodu sprawdzającego (and.
jacket) czy odwołania wątków będą blokować. a wątków używa się głownie w zadaniach z
blokującymi odwołaniami, gdzie mają poprawić wydajność...
o problem2: nie ma wywłaszczania, wątki muszą same oddawać sterowanie procedurze
wykonawczej procesu.
" Implementacja wątków w jądrze:
o system wykonawczy jest częścią jądra
o jądro zakłada tablicę wątków dla każdego procesu
o wszystkie funkcje mogące blokować mają postać odwołań do systemu
o gdy wątek czka, jądro wybiera następny  wydajność!
o wada: koszt odwołań do systemu (czas!)
" Ogólne problemy (najtrudniejsze do implementacji) z wątkami:
o obsługa przerwań (sygnałów)
o niewznawialne procedury systemowe
12
Systemy operacyjne  skrypt do wykładu Autor: Efcia
RODZIAA
3  PROCESY  ZADANIENIA PLANOWANIA
PLANOWANIE
Planowanie  przydział procesora gwarantujący jego optymalne wykorzystanie (np. gdy proces czeka
na urządzenie we-wy; sterowanie przechodzi do następnego.
" procesy oczekują na przydział procesora w kolejkach (kolejka: lista bloków kontrolnych
procesów)
o kolejka zadań: procesy nowoutworzone i czekające na pamięć
o kolejka procesów gotowych: czekających na przydział procesora
o kolejki urządzeń: procesy oczekujące na przydział urządzenia
" za szeregowanie (wybór z kolejek) procesów odpowiada planista (scheduler  proces systemowy)
o planista długoterminowy: wybiera procesy z kolejki zadań (zredukowany w niektórych
systemach); działa co sek/min.
o planista krótkoterminowy: wybiera z kolejki pr. gotowych; działa co ms.
o czasem planista odpowiada za wymianę (swapping) czyli czasowe usuwanie zadania w całości
z pamięci głównej do pomocniczej
" Decyzję podejmuje się gdy proces:
1. przechodzi ze stanu wykonywany do stanu oczekujący
2. przechodzi ze stanu wykonywany do stanu gotowy
3. przechodzi ze stanu oczekujący do stanu gotowy
4. kończy się
" Sterowanie do procesu wybranego przez planistę przekazuje dyspozytor (dispatcher):
o przechowuje stan (kontekst) bieżącego procesu.
o przełącza kontekst (rejestry, itd...)
o przełącza system w tryb użytkownika
o wykonuje skok do adresu z bloku kontrolnego
o opóz
nienie wnoszone przez dyspozytora: 1-100ms (zależne od wsparcia sprzetowego)
Życie procesu: dwie fazy (cykliczne) : 1. procesora, 2. we-wy (oczekiwania na urządzenie)
" procesy zorientowane na we-wy (1): spędzają więcej czasu wykonując operacje we-wy niż
obliczenia; wiele krótkich odcinków czasu zapotrzebowania na CPU
" zorientowane na procesor (2): spędzają więcej czasu wykonując obliczenia; kilka bardzo długich
odcinków czasu zapotrzebowania na CPU
Częstość fazy procesora
1
2
Dł. fazy procesora
13
Systemy operacyjne  skrypt do wykładu Autor: Efcia
KRYTERIA PLANOWANIE (RÓŻNE MOŻLIWOŚCI  MAXYMALIZACJA I MINIMALIZACJA)
" max wykorzystania procesora (najlepiej 40-90%)
" max przepustowości  liczba procesów kończonych w jedn. czasu)
" min czasu przetwarzania procesu (od utworzenia do zakończenia)
" min czasu oczekiwania w kolejkach (to kryterium będziemy stosować)
" min czasu odpowiedzi procesu (w syst. interaktywnych)
będziemy minimalizować średni czas oczekiwania w kolejkach
ALGORYTMY PLANOWANIA
FCFS (First Come First Served)
" przydział czasu w kolejności zgłaszania się procesów
" najprostsza implementacja (kolejka FIFO)
" brak wywłaszczania
" kłopotliwy w systemach z podziałem czasu
" przykład:
o Procesy i ich zapotrzebowanie na CPU: P1 (24), P2 (3), P3 (3)
o Jeżeli procesy przybyły w kolejności P1, P2, P3: � czas oczekiwania: P1 = 0, P2 = 24, P3 = 27 �
średni czas oczekiwania: (0 + 24 + 27)/3 = 17.
o Jeżeli procesy przybyły w kolejnooeci P2, P3, P1: � czas oczekiwania: P1 = 6, P2 = 0, P3 = 3 �
średni czas oczekiwania: (6 + 0 + 3)/3 = 3
" efekt: krótkie procesy są wstrzymywane przez długie
" zalety: sprawiedliwy, niski narzut systemowy
" wady: długi oeredni czas oczekiwania i wariancja czasu oczekiwania, nieakceptowalny w
systemach z podziałem czasu
SJF (Shortest Job First)
" Algorytm wiąże z każdym procesem długość jego najbliższej fazy procesora. Procesor jest
przydzielany najkrótszemu.
" Przy równych fazach procesora mamy FCFS
" SJF jest optymalny (dowód: umieszczenie krótkiego przed długim bardziej zmniejsza czas
oczekiwania krótkiego niż zwiększa długiego)
" SJF może być:
o niewywłaszczający
o wywłaszczający (gdy dł. fazy nowego jest krótsza niż to, co zostało aktualnie wykonywanemu
procesowi)
" Problem: jak oszacować długość przyszłej fazy procesora?
o planista długoterminowy może wymagać jego zadeklarowani od procesów (zadania maj ą
predefiniowany czas fazy); krótkoterminowy nie może (wielkie opóz
nienia)
o częste rozwiązania: dł. następnej fazy (tn+1)= średnia wykładnicza długości n faz poprzednich
(założenie: dł fazy jest zależna od długości poprzednich faz):
o tn+1 = Łi=0n a(1-a)i tn-i gdzie a<1.
14
Systemy operacyjne  skrypt do wykładu Autor: Efcia
o powyższe rozwiązania jest adaptacyjne (dostosowuje się gdy zapotrzebowanie procesu ulega
zmianie)
PLANOWANIE PRIORYTETOWE
" szczególnym przypadkiem jest SJF ( w którym priorytet = 1/(dł nast. fazy procesora) ).
" zwykle priorytet określa jednak liczba całkowita np. z przedziału [0,7] czy [0,4096]  niższa wartość
= wyższy priorytet.
" problem: proces o niskim priorytecie może się nigdy nie wykonać (w jednym z przemysłowych
systemów IBM proces czekał na wykonanie od 1967 do 1973...); rozwiązanie: postarzanie
procesów (zmniejszenie priorytetu o 1 np. co 10 min.)
" może być wywłaszczające (ale niekoniecznie)
" określenie priorytetu:
o zewnętrznie (przez funkcję systemową)
o wewn. przez deklarację samego procesu (na podstawie np. wymagań: pamięć, procesor
etc...)
PLANOWANIE ROTACYJNE (Round Robin - RR, pol. karuzelowe)
" ustala się kwant czasu (~10-100 ms)
" kolejka procesów jest traktowana jak cykliczna FIFO
" algorytm przegląda kolejkę i kolejno przydziela każdemu kwant czasu (jeśli proces się w nim nie
zakończy  wraca do kolejki, a długość jego fazy procesora zmniejsza się o kwant czasu).
" algorytm jest wywłaszczający
" gdy jest N procesów a kwant czasu wynosi Q, max. czas oczekiwania może wynieść (N-1)Q
" efekty:
o gdy Q rośnie nieograniczenie; planowanie rotacyjne FCFS
o gdy Q zmierza do 0 zachodzi dzielenie procesora  każdy proces dysponuje procesorem o
prędkości 1/N rzeczywistego.
" a propos: podobny efekt dają tzw. procesory peryferyjne  z np. 10 zestawami rejestrów; na każde
zadanie. Procesor peryf. wykonuje po 1 rozkazie każdego zadania. Zysk: procesor jest szybszy od
pamięci  całość nie jest 10x wolniejsza...)
" Aspekty wydajnościowe:
o wskazany jest długi kwant czasu w porównaniu z przełączaniem kontekstu (wpp zła
wydajność)
o reguła doświadczalna: kwant czasu powinien być dłuższy niż 80% faz procesora dla
optymalnej wydajności.
STRUKTURA KOLEJEK W SYSTEMIE OPERACYJNYM
(PLANOWANIE WIELOPOZIOMOWE)
" Kolejka procesów gotowych jest podzielona na odrębne kolejki; przykładowo (najprościej):
o procesów piewszoplanowych (systemowe, interakcyjne)
o procesów drugoplanowych (wsadowe)
15
Systemy operacyjne  skrypt do wykładu Autor: Efcia
" Każda kolejka ma własny algorytm szeregowania
" Przykład:
o procesy piewszoplanowe - strategia karuzelowa (RR)
o procesy drugoplanowe - FIFO
" Szeregowanie pomiędzy kolejkami:
o Ustalone, np. obsługuj najpierw wszystkie procesy pierwszoplanowe, potem drugoplanowe;
możliwość zagłodzenia
o Kwant czasu: każda kolejka otrzymuje ustaloną część czasu CPU do podziału pomiędzy swoje
procesy, np. 80% dla pierwszoplanowych z RR, 20% dla drugoplanowych z FCFS
o Procesy mogą się przemieszczać pomiędzy kolejkami
" Parametry planisty systemowego:
o liczba kolejek
o algorytm szeregowania dla każdej kolejki
o metoda awansu/degradacji procesów (do kolejki o odpowiednio niższym/wyższym
priorytecie)
o metoda wybierania kolejki dla nowego procesu
" Przykład: proces zużywający dużo czasu procesora (np. cały kwant w RR) przechodzi do kolejki o
niższym priorytecie, ale dłuższym kwancie. Na najniższym poziomie: FCFS. Procesy interakcyjne i
zorientowane na we-wy będą pozostawać w kolejkach o wyższym priorytecie, a procesy
zorientowane obliczeniowo - w kolejkach o niższym priorytecie.
SYSTEMOW E (RR)
INTERAKCYJNE (RR)
PRIORYTETOW E
W YW A
ASZCZAJ
CE CPU
ZGA
OSZENIA
...
(+ ew. postarzanie)
W SADOW E (FCFS)
" Wnioski z symulacji, teorii, praktyki:
o rozkład faz jest na ogół w rzeczywistych systemach wykładniczy
o jeśli średnia długość kolejki = n, średni czas obsługi = T, tempo przybywania nowych
procesów =  T (tw. Little a; stosuje się ogólnie do stabilnych systemów kolejkowych)
, to n = 
 
 
" Systemy wieloprocesorowe:
o dzielenie (osobna kolejka i algorytm dla każdego procesora) lub...
o wspólna kolejka:
- każdy procesor sam wybiera proces do wykonania
- jeden procesor przydziela procesy do procesorów
- (tzw. wieloprzetwarzanie asymetryczne)
16
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ROZDZIAA
4  KOORDYNACJA PROCESÓW
SEKCJE KRYTYCZNE
" interpretacja przetwarzania współbieżnego dla pojedynczego CPU: proces rozpoczyna się przed
zakończeniem poprzedniego
" możliwy konflikt przy operacjach na danych dzielonych (np. nawet instrukcja x:=x=1 to 3
instrukcje (mov AX,x; inc AX; mov x,AX) procesora...
" Wniosek: każdy z procesów ma (może mieć) segment kodu nazywany sekcją krytyczną (SK). SK
procesów podlegają wzajemnemu wykluczaniu się w czasie.
" Cechy rozwiązania problemu SK:
o wzajemne wyłączanie SK
o ograniczone (skończone) czekanie na wejście do SK
o postęp: kandydują tylko procesy zgłaszające chęć wejścia do SK
" np.(ogólna struktura procesu i przykładowe rozwiązanie):
repeat
while x<>0 do nic (sekcja wejściowa)
(SK)
x:=1 (sekcja wyjściowa)

until false (narzucone naprzemienne (czyli nie spełniające warunku postępu) wykonanie SK dla
2(może być więcej) procesów)
" Poprawne rozwiązanie dla 2 procesów:
var flaga: array[o..1] of Boolean
numer: 0..1
repeat
flaga[i]:=TRUE (chcę wejść)
numer:=j (założenie, że drugi chce wejść)
while (flaga[j] AND numer:=j)do nic

flaga[i]:=FALSE

until false (bez zmiennej numer możliwe byłoby ustawienie obu flag przez procesy w
dwóch kolejnych instrukcjach procesora (po pechowym przełączeniu kontekstu) i wieczne ich
zapętlenie...)
17
Systemy operacyjne  skrypt do wykładu Autor: Efcia
SEMAFORY
" Semafor ogólne popularne rozwiązanie problemu SK i synchronizacji
" Semafor s to zmienna całkowita dostępna po inicjacji za pomocą tylko 2 operacji:
o czekaj(s): while s <= 0 do nic; s := s-1;
o sygnalizuj(s): s := s+1;
" Interpretacja s: ilość wolnych zasobów; w tym przypadku zasobem jest SK
" Operacje na semaforach są NIEPODZIELNE! Implementacja:
o na pojedynczym CPU  zablokowanie przerwań na czas operacji
o w systemie wieloprocesorowym instrukcja procesora TEST&SET
" Użycie:
s:=1
repeat
czekaj(s)

sygnalizuj(s)

until false
" Zastosowanie przy synchronizacji (np. gdy operacja1 musi się wykonać po operacji2):
s:=0
1proces: op1; 2proces: czekaj(s);
sygnalizuj(s); op2;
" Wada: s wymaga aktywnego czekania (czas procesora!!!)
o rozwiązanie: po czekaj(s) proces jest blokowany i umieszczany w kolejce związanej z s
o pobranie procesu z kolejki następuje po sygnalizuj(s)
o wtedy semafor to rekord (zmienna całk. + lista procesów)
o algorytm obsługi kolejki nie ma znaczenia dla procesora
" Realizacja niepodzielności:
o 1 procesor: blokada przerwań na czas operacji
o wiele procesorów: np. pojedyncza instrukcja procesora  test&set
BLOKADY
" Stan blokady: każdy proces w zbiorze procesów czeka na zdarzenie, które może być spowodowane
tylko przez inny procesu z tego samego zbioru (zdarzeniem może być np. przydział lub zwolnienie
zasobu).
np.:
Semafory A i B mają wartość 1:
18
Systemy operacyjne  skrypt do wykładu Autor: Efcia
P0: wait(A); wait(B)
P1: wait(B); wait(A)
" Przypadek szczególny: tzw. głodzenie  czekanie w nieskończoność pod semaforem  gdy np.
zastosujemy kolejkę LIFO semafora.
" Warunki powstania blokady:
1. Wzajemne wyłączanie (co najmniej 1 zasób musi być niepodzielny)
2. Przetrzymywanie i oczekiwanie (proces przetrzymujący co najmniej jeden zasób czeka na
przydział dodatkowych zasobów będących w posiadaniu innych procesów).
3. Nie ma wywłaszczania z zasobów.
4. Cykliczne czekanie (istnieje zbiór czekających procesów {P0, P1, Pn }, takich że P 0 czeka na
zasób przetrzymywany przez P1 , P1 czeka na zasób przetrzymywany przez P2 , ..., P n czeka
na zasób przetrzymywany przez P0 .
(4 implikuje 2, więc podane warunki nie są niezależne)
" Opis blokady:
o zbiór procesów P, zasobów Z,  graf przydziału zasobów  dwudzielny (krawędzie łączą
wierzchołki należące do 2 rozdzielnych zbiorów  w tym przypadku zasobów i procesów) graf
skierowany.
o krawędzie Pi Zj : krawędz
zamówienia
o krawędzie Zj Pi : krawędz
przydziału
" Rysunek:
o proces p kółko,
o zasób z prostokąt
o 1 egzemplarz zasobu z kropka w prostokącie.
o krawędz
przydziału zaczyna się od kropki
" Zdarzenia w systemie:
o zamówienie z przez p : dodajemy krawędz
p z
o realizacja zamówienia : dodajemy krawędz
z p, usuwamy p z
o zwolnienie zasobu : usuwamy krawędz

19
Systemy operacyjne  skrypt do wykładu Autor: Efcia
" Blokada:
o jeżeli w grafie nie ma cyklu: nie ma blokady.
o jeżeli jest cykl a zasoby są pojedyncze to jest blokada
o jeżlei jest cykl a zasoby są wielokrotne, to może być blokada
" Postępowanie z blokadami:
o zapewnić że nigdy ich nie będzie (odp. protokół przydziału zasobów)
o pozwalać na wejście w blokadę i potem ją usuwać
o zignorować i założyć, że nie wystąpią (np. UNIX i większość popularnych s.o).
ZAPOBIEGANIE I UNIKANIE BLOKAD
" Zapobiec spełnieniu jednego z 4 warunków koniecznych wystąpienia blokady:
o wzajemne wyłącznie: na ogół niemożliwe; niektóre zasoby są z definicji niepodzielne
(drukarka, plik do pisania...)
o Przetrzymywanie - trzeba zagwarantować, że gdy proces żąda zasobu, to nie posiada innych
zasobów: pozwalać na zamówienie tylko gdy zwolni wszystkie posiadane (problem: głodzenie
i nieefektywne wykorzystanie zasobów).
o Można wymagać, by proces zamawiał i dostawał wszystkie swoje zasoby zanim rozpocznie
działanie lub żądał zasobów wtedy, gdy nie posiada żadnych innych - niskie wykorzystanie
zasobów, możliwość zagłodzenia
o Brak wywłaszczeń: jeśli proces będący w posiadaniu zasobów żąda zasobu, którego nie
można natychmiast przydzielić, to musi zwolnić wszystkie posiadane zasoby - Wywłaszczone
zasoby dodaje się do listy zasobów, na które czeka proces
o Cykliczne czekanie: narzuca się uporządkowanie całkowite wszystkich typów zasobów i
wymaga, by proces zamawiał zasoby we wzrastającym porządku ich numerów (metoda
wyklucza powstawanie cykli)
powyższe metody zawsze ograniczają przepustowość systemu...
" Unikanie blokad:
o Wymaga, by system posiadał pewną informację o przyszłym zapotrzebowaniu na zasoby
o W najprostszym modelu wymaga się, by proces deklarował maksymalną liczbę zasobów
każdego typu, których będzie potrzebował
o Algorytm unikania blokady dynamicznie bada stan przydziału zasobów, by zapewnić, że nigdy
nie dojdzie do cyklicznego oczekiwania
o Stan systemu jest określony przez liczbę dostępnych i przydzielonych zasobów oraz przez
maksymalne zapotrzebowanie procesów.
" Stan bezpieczny - kiedy proces żąda dostępnego zasobu, system musi ustalić, czy natychmiastowy
przydział zasobu zachowa bezpieczny stan systemu
" System jest w stanie bezpiecznym, gdy istnieje bezpieczna sekwencja :
bezpieczna, jeśli dla każdego P i jego potencjalne zapotrzebowanie na zasoby można zaspokoić
przez bieżąco dostępne zasoby oraz zasoby będące w posiadaniu procesów Pk , gdzie k < i.
o Jeśli system jest w stanie bezpiecznym to nie ma blokady
o Jeśli system nie jest w stanie bezpiecznym to istnieje możliwość blokady. Można unikać
blokady zapewniając, że system nigdy wejdzie do stanu niebezpiecznego.
" Algorytm unikania korzystający z grafu przydziału zasobów: (dla zasobów pojedynczych):
o wprowadzamy krawędzie deklaracji (zapotrzebowania)  rysowane linią przerywaną)
o szukamy pętli w grafie (złożoność O(n2) )
o jeśli jest pętla  nie przydzielamy zasobu.
20
Systemy operacyjne  skrypt do wykładu Autor: Efcia
" Algorytm unikania (dla zasobów wielokrotnych  tzw. alg. bankiera. Por. A Silbershatz i.in.
Podstawy syst. operacyjnych rozdz. 6.4.1 str. 208.):
o Każdy proces musi a priori złożyć maskymalne zapotrzebowanie na zasoby
o Proces żądający zasobu być może będzie musiał czekać, mimo że zasób jest dostępny..
o Gdy proces dostanie wszystkie potrzebne zasoby, to zwróci je w skończonym czasie
o Po zamówieniu przez proces zasobów system ustala czy ich przydzielenie prowadzi do stanu
bezpiecznego.
Założenia:
n  liczba procesów
m  liczba typów zasobów
int Dostępne[m]  liczba zasobów określonego typu (np. Dostępne[3]=5 to 5 zasobów typu 3)
int Maks[n][m]  maksymalne żądania procesów
int Przydzielone[n][m]  przydzielone zasoby
int Potrzebne[n][m]  potrzebne zasoby (z tym, że Potrzebne[i][j]=Maks[i][j]-Przydzielone[i][j])
int Zamówienia[n][m]  aktualne zamówienia procesu.
Algorytm:
1. Jeśli Zamówienia[i] <= Potrzebne[i] to wykonaj krok 2. Wpp błąd  proces przekroczył
deklarowane zapotrzebowanie.
2. Jeśli Zamówienia[i] <= Dostępne wykonaj krok 3. Wpp proces i musi czekać.
3. System próbuje przydzielić żądane zasoby procesowi i zmieniając stan systemu w następujący
sposób:
Dostępne = Dostępne  Zamówienia[i]
Przydzielone[i] = Przydzielone[i] + Zamówienia[i]
Potrzebne[i] = Potrzebne[i]  Zamówienia[i]
Jeśli stan po zmianie jest bezpieczny, transakcja dochodzi do skutku. Jeśli nie  proces i
musi czekać...
Algorytm bezpieczeństwa:
1. int Praca[m]; int Koniec[n]
2. Praca = Dostępne; Koniec[i] = FALSE dla wszystkich i
3. Znajdujemy i takie że Koniec[i]=FALSE oraz Potrzebne[i] <= Praca; Jeśli nie ma takiego i do
kroku 5.
4. Praca = Praca + Przydzielone[i]; Koniec[i] = TRUE; przejdz
do kroku 2.
5. Jeśli Koniec[i] = TRUE dla wszystkich i, to system jest w stanie bezpiecznym...
Koszt stwierdzenia czy system jest bezp. = m x n2
21
Systemy operacyjne  skrypt do wykładu Autor: Efcia
WYKRYWANIE I WYCHODZENIE Z BLOKADY
" W systemach bez zapobiegania i unikania musi być:
o alg. wykrywania blokady (najczęściej: poszukiwanie cykli w grafie)
o alg. wychodzenia z blokady
" Kiedy wywoływać algorytm wykrywania blokady:
o gdy nie można natychmiast przydzielić zasobu
o raz na ustalony czas (np. 10 min)
o gdy obciążenie procesora spada poniżej ~40% (blokada dławi przepustowość systemu)
" Wychodzenie z blokady (sposoby):
o Powiadomienie operatora (rozwiązuje problem ręcznie)
o Usunięcie procesu(ów) uczestniczących w blokadzie
całej pętli (znaczny koszt, utrata częściowych wyników)
kolejno (wywołanie szukania cykli po każdym usunięciu)
o różne kryteria wyboru ofiary (priorytet, typ, posiadane zasoby...)
o Wywłaszczanie z zasobów (potrzebna gwarancja że nie będzie głodzenia  np. wywłaszczenie
możliwe max. k razy)
" Ogólnie (bsługa blokad):
o zapobieganie, unikanie, wykrywanie, usuwania
" We współczesnych systemach: - podział zasobów na klasy:
o do klas stosujemy zapobieganie cyklom
o w obrębie klas:
- zasoby wewnętrzne (bloki kontr. itp...) uporządkowanie zasobów
- pamięć głowna
- urządzenie i pliki unikanie blokad
22
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ROZDZIAA
5  ZARZ
DZANIE PAMI
CI

ZAA
OŻENIA WST
PNE
" pamięć mieści cały program (o wyjątkach poniżej)
" pamięć to tablica poadresowanych słów
" współpraca z pamięcią polega na pisaniu/czytaniu z/pod adres
" procesy pobierane są do pamięci z kolejki zadań.
RÓŻNE MECHANIZMY
" Wiązanie:
o proces może rezydować w dowolnej częsci pamięci; musi istnieć mechanizm wiązania
rozkazów i danych z adresami fizycznymi.
o wiązanie może nastąpić w czasie:
- kompilacji (przy założeniu że proces rozpoczyna się od adresu X  np. pliki *.com w dos)
- ładowania (po przemieszczeniu kodu trzeba przeładować)
- wykonania (możliwe przemieszczenia)
" A
adowanie dynamiczne: podprogramy są na dysku w formie przemieszczalnej i są ładowane po
wywołaniu przez pr. główny. zaleta: nie ładujemy nieużywanego kodu.
" A
ączenie dynamiczne (bez niego wszystkie programy musza mieć swoje kopie bibliotek
systemowych (np. DLL). W miejscach odwołań znajdują się zakładki (małe fr. kodu, po wywołaniu
podające adres procedury bibliotecznej)
" Nakładki (np. *.ovl)  w pamięci jest tylko niezbędny kod, nakładki się wyłączają (na ogół), są
przechowywane na dysku w postaci bezwzględnego obrazu pamięci.
ponieważ procesy wykonują się wyłącznie w pamięci, nie zawsze wszystkie się mieszczą. Więc:
WYMIANA
" Proces może zostać czasowo wysłany z pamięci głównej do zewnętrznej, a po jakimś czasie
sprowadzony ponownie do pamięci głównej
" Program wraca w to samo miejsce, chyba że mamy do czynienia z wiązaniem w czasie wykonania.
" Jako pamięć zewnętrzna na potrzeby wymiany służy duży szybki dysk z dostępem bezpośrednim
" Główny narzut: czas transmisji; dla dobrej wydajności czas wykonania musi być długi w
porównaniu z czasem przełączania.
" System musi wiedzieć o zapotrzebowaniu na pamięć by pracować efektywnie, przydziału
dokonują funkcje systemowe.
" W czasie wymiany nie mogą występować operacje we/wy (operujące na buforach pamięci) nie
wymienia się procesów we/wy a buforami opiekuje się system.
23
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ZARZ
DZANIE PAMI
CI
OPERACYJN

SO
Z1
Z2
Z3
&
Z4
System operacyjny przechowuje tablicę z informacjami o tym, które części pamięci są dostępne, a
które zajęte. Na początku cała pamięć jest dostępna dla procesów użytkowych i jest traktowana jako
jeden wielki blok pamięci  dziura. Gdy przybywa proces z zapotrzebowaniem na pamięć, wówczas
poszukuje się dla niego wystarczająco obszernej dziury. Jeśli zostanie znaleziona, to przydziela się z
niej pamięć tylko w niezbędnej ilości, pozostawiając resztę na przyszłe potrzeby.
Nadchodzące do systemu procesy są umieszczane w kolejce wejściowej. Przydzielając pamięć
procesom, system operacyjny uwzględnia zapotrzebowanie na pamięć każdego procesu oraz ilość
wolnej pamięci. Proces, któremu przydzielono przestrzeń, jest wprowadzany do pamięci i zaczyna
rywalizować o przydział procesora. Gdy proces kończy pracę, wówczas zwalnia swoją pamięć, a
system operacyjny może wtedy umieścić w niej obraz innego procesu z kolejki wejściowej.
W każdej chwili dysponujemy listą rozmiarów dostępnych bloków oraz kolejką wejściową. System
operacyjny może porządkować kolejkę wejściową zgodnie z algorytmem planowania. Procesy
otrzymują przydziały pamięci aż do chwili, kiedy okaże się, że zapotrzebowanie na pamięć złożone
przez kolejny proces nie może być spełnione. Żaden dostępny blok pamięci (dziura) nie jest dość
duży, żeby pomieścić ten proces. System operacyjny może wówczas zaczekać na pojawienie się
odpowiednio dużego bloku lub może przeskoczyć pozycję w kolejce wyjściowej, żeby sprawdzić, czy
nie da się zaspokoić mniejszego wymagania na pamięć któregoś z pozostałych procesów.
Na ogół zbiór w każdej chwili zbiór dziur o różnych rozmiarach jest rozproszony po całej pamięci. Gdy
proces nadchodzi i zamawia pamięć, wówczas system przegląda ten zbiór w poszukiwaniu dziury
wystarczająco dużej dla danego procesu. Jeśli dziura jest zbyt wielka, to dzieli się ją na dwie: jedna
część zostaje przydzielona przybyłemu procesowi, druga wraca do zbioru dziur. Gdy proces skończy
pracę, zwalnia swój blok pamięci, który, znów zostaje umieszczony w zbiorze dziur. Jeśli nowa dziura
przylega do innych dziur, to łączy się przyległe dziury, tworząc jedną, większą dziurę. Należy wówczas
sprawdzić, czy jakieś procesy oczekują na pamięć oraz czy nowo odzyskana i zreorganizowana pamięć
może spełnić wymagania któregoś z tych oczekujących procesów.
Takie postępowanie jest szczególnym przypadkiem ogólnego problemu dynamicznego przydziału
pamięci polegającego na rozstrzyganiu, jak na podstawie listy wolnych dziur spełnić zamówienie na
obszar o rozmiarze n. Problem ten ma wiele rozwiązań. Przegląda się zbiór dziur, aby określić, która z
24
Systemy operacyjne  skrypt do wykładu Autor: Efcia
nich najlepiej nadaje się do przydziału. Najbardziej znane strategie wyboru wolnego obszaru ze zbioru
dostępnych dziur to:
1) Pierwsze dopasowanie  przydziela się pierwszą dziurę o wystarczającej wielkości.
2) Najlepsze dopasowanie  przydziela się najmniejszą dziurę z dostatecznie dużych dziur; ta
strategia zapewnia najmniejsze pozostałości po przydziale.
3) Najgorsze dopasowanie  przydziela się największą dziurę; ta strategia pozostawia po
przydziale największą dziurę, która może okazać się bardziej użyteczna niż pozostałość
wynikająca z podejścia polegającego na przydziale najlepiej pasującej dziury.
Strategie wyboru pierwszej lub najlepiej pasującej dziury są lepsze od wyboru największej dziury
zarówno pod względem zmniejszania czasu, jak i zużycia pamięci. Ani przydzielenie pierwszych, ani
najlepiej pasujących dziur nie jest wyraz
nie lepsze pod względem wykorzystania pamięci, ale
przydziały na zasadzie pierwszego dopasowania są z reguły szybsze.
SEGMENTACJA PAMI
CI OPERACYJNEJ
Segmentacja to schemat zarządzania pamięcią, który pomaga w urzeczywistnieniu opisanego
sposobu widzenia pamięci przez użytkownika. Przestrzeń adresów logicznych jest zbiorem
segmentów. Każdy segment ma nazwę i długość. Adresy określają zarówno nazwę segmentacji, jak i
odległość wewnątrz segmentu. Użytkownik określa więc każdy adres za pomocą dwóch wielkości:
nazwy segmentu i odległości.
W celu ułatwienia implementacji segmenty są numerowane, a w odwołaniach do nich zamiast nazw
segmentów, używa się numerów segmentów. Adres logiczny tworzy więc parę odległość>.
Suma bitów
RAM
Nowe bity
Procesor +
S O
Generowanie
Pole danych
zawierające
stare bity
25
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Jakie powinny być segmenty?
Ilość
odwołań
Kod i dane opłaca się podzielić na
niewielkie segmenty.
Granica Wielkość segmentu
STRONICOWANIE
Stronicowanie to schemat zarządzania pamięcią zezwalający na nieciągłość fizycznej przestrzeni
adresowej procesu. Stosując stronicowanie, omija się problem dopasowywania kawałków pamięci o
zmiennych rozmiarach do miejsca w pamięci pomocniczej. Rozmaite formy stronicowania są w
powszechnym użyciu w większości systemów.
Pamięć fizyczną dzieli się na bloki stałej długości zwane ramkami. Pamięć logiczna jest również
podzielona na bloki takiego samego rozmiaru zwane stronami. Gdy ma nastąpić wykonanie procesu,
wówczas z jego strony, przebywające w pamięci pomocniczej, są wprowadzane w dowolne ramki
pamięci operacyjnej. Pamięć pomocniczą dzieli się na stałej długości bloki tego samego rozmiaru co
ramki w pamięci operacyjnej.
Każdy adres wygenerowany przez procesor dzieli się na dwie części: numer strony i odległość na
stronie. Numer strony jest używany jako indeks w tablicy stron. Tablica stron zawiera adresy bazowe
wszystkich stron w pamięci operacyjnej.
Model stronicowania pamięci logicznej i fizycznej:
0
0
1
Strona 0
1
4 1
Strona 0
Strona 1
2 3
2
Strona 2
3 7
Strona 2
Strona 3 3
Tablica
Pamięć Strona 1
4
stron
logiczna
5
6
Strona 3
7
Pamięć
fizyczna
26
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Rozmiar strony (a także ramki) jest określony przez sprzęt. Rozmiar ten jest zwykle potęgą 2 z
przedziału od 512 B do 16 MB na stronę  w zależności od architektury komputera.
Ważnym aspektem stronicowania jest wyraz
ne rozdzielenie pamięci oglądanej przez użytkownika od
pamięci fizycznej. Program użytkownika powstaje przy założeniu, że obszar pamięci jest ciągły i
zawiera tylko jeden program. W rzeczywistości program użytkownika jest rozrzucony fragmentami po
pamięci fizycznej, w której są przechowywane również inne programy. Rozbieżność między pamięcią
widzianą przez użytkownika a pamięcią fizyczną usuwa sprzęt tłumaczący adresy. Adresy logiczne są
przekładane na adresy fizyczne. Odwzorowanie to jest ukrywane przed użytkownikiem i
nadzorowane przez system operacyjny. Proces użytkownika nie jest w stanie sięgnąć do pamięci,
której nie jest właścicielem. Nie ma on żadnej możliwości zaadresowania pamięci leżącej poza jego
tablicą stron, z kolei tablica ta zawiera tylko te strony, które należą do procesu.
Ponieważ system operacyjny zarządza pamięcią fizyczną, musi znać wszystkie szczegóły jej
przydzielania: które ramki są przydzielone, które ramki są wolne, jaka jest ogólna liczba ramek itd.
Informacje te są przechowywane w tablicy ramek. Ma ona po jednej pozycji dla każdej fizycznej
ramki strony. W każdej pozycji tablicy znajdują się informacje o tym, czy ramka jest wolna czy też
zajęta, a jeśli jest zajęta, to do której strony jakiego procesu lub procesów jest przydzielona.
BA

D STRONY  odwoływanie się do pamięci zapisanej na dysku.
RAM
Procesor +
S O
Krytyczny
moment
Ramka
Tablica stron
Twardy dysk
27
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Prawdopodobieństwa akcji I-III znacznie się od siebie różnią :
I - 90%
II  9%
III  1%
I
II
III
ALGORYTMY ZAST
POWANIA STRON
Gdy występuje błąd strony i w pamięci fizycznej nie ma już wolnego miejsca (ramek) stosuje się
wtedy algorytmy:
1) FIFO  usuwana jest strona najdłużej przebywająca w pamięci
2) OPT  algorytm optymalny  usuwamy stronę, która najdłużej nie będzie używana; błąd
strony będzie występował najrzadziej jak to możliwe; wada  algorytm wymaga wiedzy o
przyszłym ciągu odniesień
3) LRU  last recently used  usuwamy stronę, która najdłużej nie była wykorzystywana, trzeba
znać przeszłość  dane o przeszłości muszą być zapisane
4) ALRU  aproksymowany LRU (algorytm drugiej szansy)  zminimalizowana ilość danych, 1 bit
 bit odniesienia; w momencie, gdy wykonywany jest kod strony to bit ustawia się na 1, gdy
występuje błąd strony, szukamy strony do usunięcia  gdy trafimy na stronę z bitem 1,
zmieniamy go na 0, natomiast gdy trafimy na stronę z 0  usuwamy ją.
5) LFU  usuwamy najrzadziej używaną stronę
6) MFU  usuwamy najczęściej używaną stronę
28
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ZASADA LOKALNOŚCI ODWOA
AC

Działanie aplikacji w SO
Adres
Przerwy w odwołaniach
Obszary są wypełnione
odwołaniami do pamięci.
t
Struktura pamięci operacyjnej jest wielopoziomowa.
W przypadku rejestrów procesora to jest kwestia 1 lub 0 cykli dostępu.
CPU 1 -0
3 -10
Cache CPU
Pamięc fizyczna
10 -100
Ext. Cache / pamięć pom.
RAM >100
HDD ~106 - twardy dysk
Efektywność wynika z ograniczeń telekomunikacyjnych i uwarunkowań ekonomicznych.
ALGORYTMY PRZYDZIAA
U RAMEK
Algorytmy odpowiadają na pytanie, ile miejsca powinna dostać aplikacja ładowana do pamięci.
Jednak nie można odpowiedzieć na to pytanie. Są 2 rozwiązania:
" Przydział równy  każdy proces dostaje tę samą ilość ramek
" Przydział proporcjonalny  każdemu procesowi przydziela się dostępną pamięć odpowiednio do
jego rozmiaru
29
Systemy operacyjne  skrypt do wykładu Autor: Efcia
CPU
100%
Procesy
Istnieje limit podziału. W momencie, gdy odwołań jest coraz więcej, SO musi czekać na HDD. Aplikacji
jest coraz więcej, ale procesor nic nie robi, nazywamy to szamotaniem.
SPOSOBY LIKWIDACJI SZAMOTANIA
1. Model strefowy  służy do zapewnienia aplikacji tylu ramek, ile potrzebuje; minimalizuje to
szanse na wystąpienie błędu strony.
Strony 1, 2, 7, 5, 5, 8, 3, 9, 10, &
"  okno zbioru roboczego, ilość ostatnich odwołań do stanu, które będziemy rozpatrywać
ZR  zbiór roboczy aplikacji lub procesu
" = 6
ZR = {1, 2, 5, 7} -> | ZR | = 4
Wielkość | ZR | jest prawie o połowę mniejsza od " -> na tej podstawie SO przydziela 4 ramki.
2. Strategia sterowania częstością błędu strony.
Błędy
strony
+
Maksymalny próg błędu strony
Minimalny próg błędu strony
-
Ramki
SO oddaje ramki do procesu, gdy przekroczy maksymalny próg. Natomiast procesowi, który
przekroczy minimalny próg zabiera ramki.
30
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ROZDZIAA
6  STRUKTURA PAMI
CI MASOWEJ
TWARDY DYSK
Głowice
Talerze
dyskowe
Sektor
Ramię
głowicy
Nie każda część HDD działa z tą samą prędkością. Głowica jest dużo wolniejsza od powierzchni
dyskowej.
Organizacja zapisu:
" Nośnik magnetyczny ma ścieżki magnetyczne, które są podzielone na sektory.
" Informacja na dysku jest przechowywana w ciągu bloków.
" Bloki są numerowane w obrębie jednej ścieżki.
" Następnie przechodzi się do kolejnego cylindra i to samo robi się z kolejną ścieżką.
X X
0 max
X
Jeżeli adresy są blisko siebie to istnieje duża szansa, że znajdują się na tym samym cylindrze. Aby
uzyskać do nich dostęp wystarczy tylko obrócić cylinder. Gdy adresy znajdują się na różnych
cylindrach, musi zostać przesunięta także głowica  zajmuje to więcej czasu.
OBSA
UGA CI
GU ZGA
OSZEC

Jednym z zadań systemu operacyjnego jest zapewnienie szybkiego dostępu do dysku i szybkie
przesyłanie danych dyskowych. Przez czas wyszukiwania rozumie się czas potrzebny na
przemieszczenie ramienia dysku do pozycji, w której głowice ustawiają się w cylindrze zawierającym
potrzebny sektor. Opóz
nienie obrotowe oznacza dodatkowy czas zużywany na obrót dysku do
pozycji, w której potrzebny sektor trafia pod głowicę dysku. Szerokością pasma dysku nazywa się
31
Systemy operacyjne  skrypt do wykładu Autor: Efcia
łączną liczbę przesyłanych bajtów, podzieloną przez łączny czas, jaki upływa od pierwszego
zamówienia na usługę dyskową do chwili zakończenia ostatniego przesłania. Planując wykonywanie
dyskowych operacji wejścia-wyjścia w odpowiednim porządku, możemy polepszać zarówno czas
dostępu, jak i szerokość pasma.
1. FCFS  działanie tak jak w kolejce FIFO, obsługiwane jest zgłoszenie, które pojawi się jako
pierwsze. Algorytm ten jest z natury sprawiedliwy, lecz na ogół nie zapewnia najszybszej obsługi.
X X X X X X X X
max
0
X
Głowica przesuwa się losowo.
Zasada FCFS jest mało efektywna  średnia czas oczekiwania procesów bywa bardzo długi.
2. SSTF  najpierw najkrótszy czas oczekiwania, wybiera się proces z minimalnym czasem
przeszukiwania względem bieżącej pozycji głowicy; może nastąpić  wygłodzenie procesu
znajdującego się po jednej stronie dysku, jeśli głowica  utknie po drugiej stronie i kolejne
procesy będą się tam pojawiać.
X X X X X X X X
max
0
X
3. C-SCAN  głowica HDD skanuje całą powierzchnię w poszukiwaniu procesów i wykonuje je po
kolei, porusza się tylko w jednym kierunku.
X X X X X X X X
max
0
X
32
Systemy operacyjne  skrypt do wykładu Autor: Efcia
4. SCAN  głowica zawraca przy ostatnim aktywnym zgłoszeniu. W przypadku dużego obciążenia
dysku czas na skanowanie dysku od początku do końca będzie bardzo duży.
X X X X X X X X
max
0
X
ALGORYTMY PLANOWANIA
1. EDF  najpierw pierwszy deadline; przypomina FCFS  nie wiadomo, czy procesy o największych
deadlinach są w tym samym cylindrze.
2. FD-SCAN  odczytujemy najbliższy deadline po drodze w dół lub w górę (podobnie do SCAN).
ZARZ
DZANIE WOLNYM OBSZAREM DYSKU
1. Wektor bitowy.
Każdy blok jest reprezentowany przez 1 bit. Jeśli blok jest wolny to bit ma wartość 1, natomiast
jeśli jest przydzielony, to dany bit wynosi 0. Podstawową zaletą takiego rozwiązania jest to, że
umożliwia ono względnie proste i wydajne odnajdywanie pierwszego wolnego bloku lub n
kolejnych takich bloków.
Niestety zastosowanie wektorów bitowych jest mało wydajne, jeśli nie można przechowywać
całego wektora w pamięci operacyjnej. Przechowywanie wektora bitowego w pamięci
operacyjnej jest możliwe dla mniejszych dysków (stosowanych np. w mikrokomputerach), ale nie
dla większych.
2. Tworzenie list wolnych obszarów.
Polega to na powiązaniu ze sobą wszystkich wolnych bloków dyskowych i przechowywanie
wskaz
nika do pierwszego wolnego bloku w specjalnym miejscu na dysku oraz podręcznie  w
pamięci. Ten pierwszy blok zawiera wskaz
nik do następnego wolnego bloku itd.
Jednak ta metoda nie jest wydajna  aby przejść po liście, należy odczytać każdy blok, co
wymaga znacznej ilości czasu zużytego na operacje wejścia-wyjścia. Na szczęście przechodzenie
listy wolnych bloków nie jest częstym działaniem. Zazwyczaj system operacyjny korzysta z
pierwszego bloku z listy bloków wolnych.
33
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ZAPISYWANIE PLIKÓW NA DYSKU
1. PRZYDZIAA
CI
GA
Y  każdy plik musi zajmować zbiór kolejnych bloków na dysku. Przejścia
między blokami nie wymagają ruchu głowicy. Gdy ruch głowicy będzie konieczny (między
ostatnim sektorem na jednym cylindrze i pierwszym sektorem na następnym cylindrze), będzie
to przesunięcie tylko o jedną ścieżkę. Wynika z tego, że liczba wykonanych operacji
przeszukiwania dysku jest minimalna.
Przydział ten ma jednak wady:
" Jeżeli dysk zacznie się przepełniać możliwa będzie konieczność przesunięcia obszarów
plików.
" Jest to szczególny przypadek ogólnego problemu dynamicznego przydziału pamięci
(rozdział 9.3).
" Fragmentacja zewnętrzna  wskutek tworzenia i usuwania plików wolna przestrzeń
dyskowa ulega podziałowi na małe kawałki. Staje się to kłopotliwe wówczas, gdy największy
ciągły kawałek nie wystarcza, aby sprostać zamówieniu.
" Trudno jest określić wielkość obszaru potrzebnego dla pliku. Jeśli przydzielimy plikowi za
mało miejsca, to może się okazać, że nie da się go rozszerzyć.
2. PRZYDZIAA
LISTOWY  usuwa wszystkie problemy związane z przydziałem ciągłym. Każdy plik
jest listą powiązanych ze sobą bloków dyskowych. Bloki te mogą się znajdować gdziekolwiek na
dysku. Katalog zawiera wskaz
nik do pierwszego i ostatniego bloku pliku, a każdy blok zawiera
wskaz
nik do następnego bloku.
W celu utworzenia pliku tworzymy nowy wpis w katalogu. Każdy wpis w katalogu ma wskaz
nik
do pierwszego bloku pliku. Początkową wartością tego wskaz
nika jest nil (oznacza to, że plik jest
pusty), a pole rozmiaru przyjmuje wartość 0. Operacja pisania powoduje odnalezienie przez
system zarządzania wolnymi obszarami nie zajętego bloku i jego zapisanie oraz dowiązanie do
końca pliku. Czytanie pliku odbywa się według wskaz
ników zapamiętanych na kolejnych blokach.
nazwa Dane Dane
pliku
Adres
Zalety w porównaniu z przydziałem ciągłym:
" Nie ma potrzeby zachowania ciągłości dla jednego pliku, więc nie trzeba nic przesuwać.
" Nie ma zewnętrznej fragmentacji.
" Do spełnienia zamówienia może być użyty każdy wolny blok z listy wolnych obszarów.
" Nie trzeba deklarować rozmiaru pliku w chwili jego tworzenia  plik może rosnąć dopóki są
wolne bloki.
Wady przydziału listowego:
" Mała efektywność  trzeba  skakać po dysku. Każdy dostęp do wskaz
nika wymaga czytania
dysku.
" Jeżeli chcemy odczytać ostatni blok pliku musimy przejść przez cały ciąg bloków.
" Wskaz
niki zajmują pewną przestrzeń  każdy plik potrzebuje nieco więcej miejsca niż w
innym przypadku. Można rozwiązać ten problem przez grupowanie bloków po kilka w tzw.
34
Systemy operacyjne  skrypt do wykładu Autor: Efcia
grona (klastry) i przydzielanie gron zamiast bloków. Kosztem tego rozwiązania jest wzrost
wewnętrznej fragmentacji, ponieważ w przypadku częściowego zapełnienia grona marnuje
się więcej miejsca niż w niepełnym bloku. Grona są wykorzystywane w większości
systemów operacyjnych.
" Zawodność  pliki są powiązane wskaz
nikami porozrzucanymi po całym dysku, a w
przypadku zagubienia bądz
uszkodzenia danego wskaz
nika może spowodować pobranie
złego wskaz
nika. Taki błąd mógłby spowodować dowiązanie pliku do listy wolnych
przestrzeni lub do innego pliku. Częściowym rozwiązaniem jest używanie list z podwojonymi
dowiązaniami lub zapamiętywanie w każdym bloku nazwy pliku i względnego numeru
bloku. Jednak takie rozwiązania zwiększają jeszcze bardziej nakłady ponoszone na każdy
plik.
3. PRZYDZIAA
INDEKSOWY  skupia wskaz
niki w jednym miejscu - w bloku indeksowym.
Rozwiązuje w ten sposób problem przydziału listowego, gdzie wskaz
niki do bloków są
rozrzucone po całym dysku i muszą być odzyskiwane po kolei. Przydział indeksowy łączy w sobie
zalety dwóch poprzednich przydziałów.
Bloki dzielimy na: bloki indeksowe i bloki danych. Każdy plik ma własny blok indeksowy, będący
tablicą adresów bloków dyskowych.
Dane
Blok
indeksowy
Dane
Podczas tworzenia pliku wszystkie wskaz
niki w bloku indeksowym otrzymują wartość nil. Gdy
blok i jest po raz pierwszy zapisywany, pobiera się go od zarządcy obszarów wolnych, a jego
adres zostaje umieszczony w i-tej pozycji bloku indeksowego.
Zalety:
" Przydział indeksowy łączy w sobie zalety dwóch poprzednich przydziałów.
" Umożliwia dostęp bezpośredni bez powodowania zewnętrznej fragmentacji, ponieważ
zamówienie na dodatkowy obszar może spełnić wolny blok znajdujący się gdziekolwiek na
dysku.
" Dostęp sekwencyjny jest ułatwiony.
Wady:
" Marnowanie przestrzeni  wskaz
niki bloku indeksowego zajmują na ogół więcej miejsca niż
wskaz
niki przy przydziale listowym.
" Schemat przydziału indeksowego jest obarczony podobnymi problemami wydajności jak
przydział listowy. W szczególności bloki indeksowe mogą być przechowywane w pamięci
podręcznej, lecz bloki danych mogą być rozrzucone po całej partycji dysku.
Marnowanie przestrzeni nasuwa pytanie, jaka powinna być wielkość bloku indeksowego.
Ponieważ każdy plik musi mieć blok indeksowy, to chciałoby się, żeby był on jak najmniejszy.
Jeśli jednak będzie on za mały to nie pomieści wystarczającej liczby wskaz
ników dla wielkiego
pliku. W związku z tym należy opracować mechanizm postępowania w tej sytuacji. Są 3
rozwiązania:
35
Systemy operacyjne  skrypt do wykładu Autor: Efcia
" Schemat listowy: Blok indeksowy zawiera się zwykle w jednym bloku dyskowym, dzięki
czemu on sam może być czytany lub zapisywany bezpośrednio. Aby umożliwić
organizowanie wielkich plików, można połączyć kilka bloków indeksowych.
" Indeks wielopoziomowy: Wariantem reprezentacji listowej jest użycie bloku indeksowego
pierwszego poziomu do wskazywania zbioru bloków indeksowych drugiego poziomu,
których wskaz
niki wskazują już na bloki pliku.
" Schemat kombinacyjny: Innym podejściem (zastosowanym w systemie UNIX) jest
przechowywanie np. pierwszych 15 wskaz
ników bloku indeksowego w i-więz
le pliku.
Pierwszych 12 z tych wskaz
ników wskazuje na bloki bezpośrednie, tzn. zawiera adresy
bloków z danymi pliku. Dzięki temu dane w małych plikach nie muszę mieć oddzielnego
bloku indeksowego. Następne 3 wskaz
niki wskazują na bloki pośrednie. Pierwszy wskaz
nik
bloku pośredniego jest adresem bloku jednopośredniego. Blok jednobezpośredni jest
blokiem indeksowym, który zamiast docelowych danych zawiera adresy bloków z danymi.
Dalej następuje wskaz
nik bloku dwypośredniego, który zawiera adres bloków z adresami
bloków zawierającymi wskaz
niki do faktycznych bloków danych. Ostatni wskaz
nik
zawierałby adres bloku trój pośredniego.
36
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ROZDZIAA
7 - BEZPIECZEC
STWO W SYSTEMACH OPERACYJNYCH
Informacje przechowywane w systemie komputerowym chcemy chronić przed fizycznym
uszkodzeniem (niezawodność) oraz przed niewłaściwym dostępem (ochrona).
Kontrola dostępu
Podmioty Obiekty
Autoryzacja
Podmioty  element aktywny, jego zadaniem jest dostęp do Obiektu
Obiekty  kontener nadany (plik, struktura danych, urządzenie zewnętrzne) przechowuje dane
KONTROLA DOST
PU
" autoryzacja  następuje na podstawie wiedzy podmiotu lub na podstawie autoryzacji opartych
ma tokenach, analizie siatkówki itp.
" audyt  obserwacja i przetwarzanie danych o użytkowniku w systemie
Listy kontroli dostępu (ACL)  każdemu podmiotowi w systemie przypisana jest lista obiektów. Jest
to dostęp zależny od tożsamości i polega na skojarzeniu z każdym plikiem i katalogiem wspomnianej
lisy. Zawiera ona nazwy użytkowników i dozwolone dla poszczególnych użytkowników rodzaje
dostępu. Przykład:
Kiedy użytkownik zażąda dostępu do jakiegoś pliku, wtedy system operacyjny sprawdzi listę
dostępów przyporządkowaną danemu plikowi. Jeżeli użytkownik widnieje na niej przy danym rodzaju
dostępu, to go uzyska. W przeciwnym razie wystąpi naruszenie reguł ochrony i zadanie użytkownika
otrzyma odmowę dostępu do pliku.
Zalety listy:
" umożliwianie złożonych metod dostępu
Wady:
" Długość list.
" Jeżeli chcemy pozwolić czytać plik wszystkim, to musimy wyliczyć wszystkich użytkowników
uprawnionych do jego czytania. Ma to 2 negatywne konsekwencje:
o Sporządzanie takiej listy może być żmudnym i nie przynoszącym korzyści zajęciem,
zwłaszcza jeśli nie znamy z góry spisu użytkowników.
o Wpis katalogowy, który dotąd był stałego rozmiaru, musi obecnie mieć zmienną długość, a
to komplikuje zarządzanie przestrzenią dyskową.
Można uniknąć powyższych kłopotów korzystając z zagęszczonej wersji listy dostępu. W celu jej
skrócenia, w wielu systemach do każdego z plików odnosi się 3 klasy użytkowników:
" Właściciel  właścicielem jest użytkownik, który utworzył dany plik.
37
Systemy operacyjne  skrypt do wykładu Autor: Efcia
" Grupa albo zespół roboczy  zbiór użytkowników, którzy wspólnie korzystają z pliku i potrzebują
podobnego dostępu.
" Wszechświat  wszyscy inni użytkownicy.
O1�" �" �" Oj�" �" �"On
P1 Prawo podmiotu Pk do obiektu Oj
�" R  prawo do odczytu
RWC
�" W  prawo do zapisu
Pk
C  możliwość zmiany praw dostępu
�"
Można manipulować całą kolumną Oj
�"
Pn
Podstawowe prawo dostępu  prawo do zapisu i odczytu pliku. Niektóre systemy mają dodatkowe
prawa, np. możliwość zmiany praw dostępu.
A  administrator
U  użytkownik
Y
A U
P1  plik ściśle tajny
P2  plik jawny
RW
X  administrator odczytuje zawartość pliku P1
RW
X RW
i zapisuje ją do pliku P2 (Y). W ten sposób
użytkownik ma dostęp do danych w
tajnym pliku P1
P1 P2
PODZIAA
SYSTEMÓW OPERACYJNYCH
ZE WZGL
DU NA POLITYK
BEZPIECZEC
STWA
RODZAJE KONTROLI DOST
PU
" DAC  (Discretionary Access Control) dyskretna kontrola dostępu  pozwala użytkownikowi na
całkowite ustalenie uprawnień dostępu do swoich zasobów. Kontrola dostępu do danych
obiektów bazuje na sprawdzeniu tożsamości właścicieli/grup, do których on należy.
" MAC  (Mandatory Access Control) obowiązkowa kontrola dostępu - opiera się na poziomach
zaufania, podmiot żądający dostępu do obiektu musi należeć do odpowiedniej kategorii/grupy.
Spotykany w systemach wysokiej poufności, wojskowych. Wprowadzamy także dodatkowe
założenia:
o Istnienie klas bezpieczeństwa w systemach operacyjnych  zbiór tych klas powinien być
częściowo uporządkowany
ST > T > P > J
ST  ściśle tajne
T  tajne
P  poufne
J  jawne
38
Systemy operacyjne  skrypt do wykładu Autor: Efcia
o Wszystkie dane i aktywne podmioty w systemach operacyjnych są etykietowane  nie może
istnieć w systemie operacyjnym obiekt nie posiadający klas bezpieczeństwa.
o Klasa bezpieczeństwa podmiotu musi być większa od klas bezpieczeństwa obiektu  dla
odczytu. Natomiast w przypadku zapisu klasa bezpieczeństwa podmiotu musi być mniejsza
od klasy bezpieczeństwa obiektu.
ZAPIS: KB podmiotu e" KB obiektu
ODCZYT: KB podmiotu d" KB obiektu
Przykład: W przypadku zapisu klasę P można przypisać do ST, T i P, a w przypadku odczytu
do P i J.
Aktualną klasę bezpieczeństwa podmiotu można zmieniać. System operacyjny może
obniżyć klasę bezpieczeństwa nie przekraczają klasy bezpieczeństwa, która jest mu
przypisana.
KLASY BEZPIECZEC
STWA SYSTEMÓW OPERACYJNYCH
TCB  klasa bezpieczeństwa komputerowego. Jest to zespół wszystkich systemów ochronnych w
systemie komputerowym (sprzęt, oprogramowanie, oprogramowanie układowe), które poprawnie
egzekwują zasady bezpieczeństwa.
" D  minimalna ochrona  systemy operacyjne, które nie spełniają wymagań żadnej innej klasy,
aaa np. DOS, Windows 95
" C  opierają się na dyskretnej kontroli dostępu (DAC); określa dowolne reguły ochrony i
odpowiedzialności użytkowników oraz ich działań przez umożliwienie wglądu w ich poczynania
(audyt).
o C1  podstawowa kontrola dostępu dla wielu użytkowników:
Zawiera środki kontroli, które umożliwiają użytkownikom ochronę informacji i
nie pozwalają innym użytkownikom na przypadkowe czytanie lub niszczenie
danych.
W środowisku tej klasy współpracujący użytkownicy mają dostęp do danych na
tych samych poziomach uwrażliwienia.
TCB sprawuje nadzór nad dostępem między użytkownikami i plikami na
zasadzie umożliwiania użytkownikowi określania i kontrolowania reguł
dzielenia obiektów z nazwanymi osobami lub zdefiniowanymi grupami.
Baza TCB wymaga, aby użytkownik przedstawiał się przed rozpoczęciem
jakichkolwiek działań, w których baza pośredniczy.
Dane uwierzytelniające są chronione w bazie TCB, aby były niedostępne dla
nieuprawnionych użytkowników.
o C2  zawiera te same wymagania do system klasy C1 oraz dodatkowo:
Dodaje się indywidualny poziom kontroli dostępu, np. prawa dostępu do pliku
w odniesieniu do poszczególnych osób.
Administrator systemu może śledzić wybiórczo działania dowolnego
użytkownika lub grupy użytkowników na podstawie indywidualnej tożsamości
Występuje tu audyt  gromadzenie informacji o użytkownikach, np. ilość
logowań, ilość prób dostępu do tajnych plików itp.
Baza TCB również ochrania samą siebie przed zmienianiem jej kodu lub
struktur danych.
39
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Ponadto żadne informacje utworzone przez wcześniejszego użytkownika nie
zostaną udostępnione innemu użytkownikowi, który zwraca się do obiektu
pamięci przekazanego z powrotem do systemu.
Niektóre specjalne, zabezpieczone wersje systemu UNIX mają certyfikaty
poziomu C2
" B  opiera się na obowiązkowej kontroli dostępu (MAC); systemy z klasą B mają wszystkie
właściwości systemów klasy C2, a ponadto dołącza się w nich do każdego obiektu w systemie
etykietę uwrażliwienia:
o B1  spełnia podstawowe założenia (etykietowanie, zasada nierówności klas):
Utrzymuje się etykietę bezpieczeństwa każdego obiektu w systemie, z której
korzysta się przy podejmowaniu decyzji w sprawie obowiązkowej kontroli
dostępu, np. użytkownikowi z poziomu poufnego nie wolno sięgać do pliku na
poziomie jeszcze bardziej uwrażliwionym na bezpieczeństwo (T, ST).
W bazie TCB określa się również ramy poziomów uwrażliwienia dla każdej
strony wyników zdatnych do czytania przez człowieka.
Baza TCB zajmuje się nie tylko kontrolowaniem zwykłych informacji
uwierzytelniających (nazwy użytkownika i hasła), ale także odprawą
(prześwietlaniem) i upoważnianiem poszczególnych użytkowników i dostarcza
co najmniej dwóch poziomów bezpieczeństwa. Są to poziomy hierarchiczne,
więc użytkownik ma prawo dostępu do obiektów, których etykiety
uwrażliwienia są równe lub mniejsze niż jego certyfikat bezpieczeństwa, no.
Użytkownik z poziomu tajnego mógłby mieć dostęp do pliku o poziomie
poufnym, mimo braku innych uregulowań dostępu.
Procesy również podlegają izolacji dzięki stosowaniu rozłącznych przestrzeni
adresowych.
o B2  dodatkowa autoryzacja; formalna weryfikacja konfiguracji (SO)
Etykiety uwrażliwienia są przypisywane wszystkim zasobom systemowym, np.
obiektom pamięci.
Urządzeniom fizycznym przypisuje się minimalne i maksymalne poziomy
bezpieczeństwa, użytkowane przez system w celu egzekwowania ograniczeń
wynikających z fizycznych środowisk, w których dane urządzenia się znajdują.
System B2 udostępnia tajne kanały oraz umożliwia śledzenie zdarzeń, które
mogą prowadzić do eksploatacji tajnego kanału.
o B3  TCB  bezpieczna baza obliczeniowa  wszystko, co dzieje się w systemie
operacyjnym jest zapisywane, co ma to duży wpływ na zmniejszenie efektywności:
Można tworzyć listy kontroli dostępów określających użytkowników i grupy,
którym zabrania się dostępu do obiektu o danej nazwie.
W bazie TCB istnieje także mechanizm nadzorowania zdarzeń mogących
wskazywać na naruszenie przyjętych zasad bezpieczeństwa. Mechanizm ten
powiadamia administratora odpowiedzialnego za bezpieczeństwo i (w razie
konieczności) zamyka łańcuch zdarzeń w sposób powodujący najmniejsze
straty.
Obowiązek weryfikacji każdej operacji.
" A  klasa abstrakcyjna  wymagana jest formalna weryfikacja systemu operacyjnego na
podstawie kodu systemu; weryfikacja matematyczna kodu jest bardzo rzadko potrzebna.
Użycie bazy TCB gwarantuje jedynie zdolność egzekwowania przez system zakładanej polityki
bezpieczeństwa. Baza nie określa, jaką politykę należy przyjąć. Na ogół w danym środowisku
komputerowym wypracowuje się zasady bezpieczeństwa uzyskiwania certyfikatów oraz rozporządza
się planem zatwierdzonym przez daną agencję bezpieczeństwa, np. NCSC lub TEMPEST.
40
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ROZDZIAA
8 - ROZPROSZONE SYSTEMY OPERACYJNE
System rozproszony (ang. distributed system) jest zbiorem luz
no powiązanych ze sobą procesorów
połączonych siecią komunikacyjną. Dla konkretnego procesora systemu rozproszonego pozostałe
procesory i ich zasoby są zdalne, podczas gdy jego własne zasoby są lokalne.
Procesory w systemie rozproszonym mogą różnić się mocą obliczeniową i funkcjami. Wśród nich
mogą się znajdować:
" mikroprocesory,
" stacje robocze,
" minikomputery,
" wielkie systemy komputerowe ogólnego przeznaczenia.
Procesory określa się za pomocą kilku nazw w zależności od kontekstu, w którym się o nich mówi:
" stanowiska  kiedy będziemy chcieli zwrócić uwagę na położenie maszyn,
" węzły,
" komputery sieciowe  kiedy będziemy odnosić się do konkretnego systemu w danym miejscu.
Pewien proces na jakimś stanowisku  nazywany serwerem  dysponuje zasobem, którego
potrzebuje inny proces na innym stanowisku  klient, czyli użytkownik. Zadaniem systemu
rozproszonego jest tworzenie wydajnego i wygodnego środowiska umożliwiającego taki sposób
dzielenia zasobów.
Schemat systemu rozproszonego:
Stanowisko A Stanowisko C
Serwer
Zasoby
Sieć
Komunikacja
Klient
Stanowisko B
Charakterystyka systemów rozproszonych:
" Występuje tu dzielenie zasobów  urządzenia udzielają sobie nawzajem dostępu do swoich
zasobów.
" Taksonomia Flynna  klasyfikacja architektur komputerowych opierająca się na liczbie
przetwarzanych strumieni danych i strumieni rozkazów:
o SISD (Single Instruction, Single Data) - przetwarzany jest jeden strumień danych przez jeden
wykonywany program (tradycyjne komputery jednoprocesorowe).
41
Systemy operacyjne  skrypt do wykładu Autor: Efcia
o SIMD (Single Instruction, Multiple Data) - przetwarzanych jest wiele strumieni danych przez
jeden wykonywany program (procesory macierzowe z jedną jednostką wykonywania
instrukcji, która pobiera instrukcję, a następnie zarządza wieloma jednostkami w sposób
równoległy  każda z nich operuje na własnych danych).
o MISD (Multiple Instruction, Single Data) - wiele równolegle wykonywanych programów
przetwarza jednocześnie jeden wspólny strumień danych. Rozwiązanie to jest nieco
bezsensowne i ma niewiele zastosowań (temu modelowi nie odpowiada żaden ze znanych
komputerów).
o MIMD (Multiple Instruction, Multiple Data) - równolegle wykonywanych jest wiele
programów, z których każdy przetwarza własne strumienie danych (wieloprocesowy i muli
komputery).
SYNCHRONIZACJA
Architektury rozproszone nie mają bezpośredniego przełożenia parametrów na funkcjonalność.
Ważne są inne zagadnienia, np. czas i synchroniczność. W przypadku złożonej architektury wskazania
zegara mogą się od siebie różnić. Powoduje to problem ustalenia jednoczesności wydarzeń i
określenie kolejności.
P1 P2
10
Jednostki
30
czasu
20
Czas Czas
Techniki wykorzystywane w systemach rozproszonych w celu zlikwidowania powyższego problemu:
" Algorytm Lamporta  ustalenie kolejności zdarzeń w systemie. Algorytm wykrywa anomalie
czasowe i koryguje je na bieżąco (np. wykrycie zdarzenia przed jego nadaniem, co pokazuje
powyższy rysunek). Weryfikuje wskazania zegara  na powyższym przykładzie dodałby do 10
+20, aby wydarzenie zostało odebrane w odpowiednim czasie, a nie przed jego nadaniem.
WADA: przy takiej strategii wszystkie zegary wyrównują swój czas do najszybciej chodzącego
czasomierza w systemie.
" Synchronizacja (koordynacja) wskazań zegarów w systemie
C  wskazania zegara absolutnego
`" 1
Ponieważ dąży do 1, więc:
1  � d" d" 1 + � dt  �dt d" dC d" dt + �dt
Jeżeli założymy istnienie dwóch takich samych zegarów.
2 �dt d" "
42
Systemy operacyjne  skrypt do wykładu Autor: Efcia
- maksymalny czas, po którym dokonujemy synchronizacji
dt d"
�  mała wartość, współczynnik odchylenia zachwiania zegara w systemie
STRATEGIE SYNCHRONIZACJI ZEGARÓW
1. Algorytm Cristiana  w systemach rozproszonych znajduje się jedna maszyna, którą traktujemy
jako zegar podstawowy i nazywamy serwerem czasowym.
N SCz N  nadawca
SCz  serwer czasowy
t1
a
t2 a  maszyna nadawcy pyta o aktualne
x wskazanie zegara
y
t3 y  czas wysyłanie odpowiedzi
b
t4  maszyna nadawcy wie, która
t4
godzina była na t3
Czas wysyłania komunikatu jest zaniedbywalnie mały w stosunku do synchronizacji czasu, więc
nadawca ma dokładnie zmierzony czas x. Zakładamy, że czasy a i b są symetryczne i niewielkie.
| |
| |
|t3  t1| = - oszacowanie różnicy między t3 i t1
Niestety, nie do końca dzieje się tak, jak zostało to przedstawione wyżej. Są systemy bliżej i dalej
położone od serwera czasu, więc w większym rozproszonym systemie operacyjnym ta procedura
daje różne czasu dla poszczególnych elementów systemu.
2. Rozproszony (zdecentralizowany) algorytm synchronizacji zegarów  wszystkie elementy są
traktowane sprawiedliwie, nie ma znaczenia odległość od serwera.
Każdy zegar ustawia czas biorąc pod uwagę średni czas wszystkich zegarów uwzględniają czas
podróży komunikatów.
Ta procedura jest rzadko stosowana.
3. Algorytmy elekcji  wybór jednej wyróżnionej maszyny z dostępnej puli.
W wielu algorytmach rozproszonych wymaga się, aby jeden z procesów występował w roli
koordynatora, inicjatora, porządkującego lub pełnił inne specjalne funkcje. Na ogół nie ma
znaczenia, który proces przejmuje te specjalne obowiązku, lecz powinien je wykonywać tylko
jeden proces.
43
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Jeśli wszystkie procesy są dokładnie takie same, bez żadnych cech charakterystycznych, to nie
ma możliwości wybrania spośród nich jakiegoś specjalnego. Wobec tego możemy założyć, że
każdy proces ma niepowtarzalny numer, na przykład swój adres sieciowy. Algorytmy elekcji
najczęściej próbują zlokalizować proces o największym numerze i mianować go koordynatorem.
Dodatkowo zakłada się, że każdy proces zna numery wszystkich pozostałych procesów. Procesy
nie wiedzą natomiast, które z nich aktualnie działają, a które są unieruchomione.
1) Algorytm tyrana
8
3
2 9
4
7
1
5
10
6
Proces, który zauważy, że koordynator przestał odpowiadać na zamówienia, rozpoczyna
elekcję. Proces P przeprowadza elekcję następująco:
1. P wysyła komunikat o elekcji do wszystkich procesów z większymi numerami.
2. Jeśli nikt nie odpowie, to P zwycięża w wyborach i zostaje nowym koordynatorem.
3. Jeśli któryś z procesów o większym numerze nadeśle odpowiedz
, to on przejmuje
kontrolę, a rola procesu P się kończy.
W dowolnej chwili proces może otrzymać komunikat o elekcji, od któregoś z kolegów o
mniejszym numerze. Po nadejściu takiego komunikatu odbiorca wysyła do nadawcy
komunikat OK., aby poinformować go, że jest aktywny i przejmuje sterowanie. Następnie
odbiorca podejmuje dalszy ciąg elekcji, o ile nie przeprowadzał jej już dotąd. Dochodzi w
końcu do tego, że wszystkie procesy  z wyjątkiem jednego  zaniechały elekcji. Ten jeden
pozostały proces staje się koordynatorem. Ogłasza swoje zwycięstwo wysyłając do wszystkich
procesów komunikat.
Jeżeli jakiś proces, uprzednio wyłączony, powraca do działania, to rozpoczyna wybory. Jeśli
zdarzy się, że ma on największy numer pośród aktualnie wykonywanych procesów, to
wygrywa elekcję i przejmuje funkcje koordynatora. Jest to więc sytuacja, że proces o
największym numerze zawsze zwycięża w elekcji.
Na podstawie powyższego rysunku wygląda to tak:
Proces numer 10 ulega zniszczeniu, co zostaje zauważone przez proces 4. Wszyscy o wyższych
numerach od 4 dostają komunikat. Każdy z nich robi to samo  wysyła komunikat do
44
Systemy operacyjne  skrypt do wykładu Autor: Efcia
wyższych numerów (jako przykład podane jest wysyłanie komunikatu z 7 do 8 i do 10). 9 nie
dostanie ani jednego potwierdzenia, bo 10  nie żyje , więc 9 wygrywa i wysyła do reszty
komunikat o zakończeniu elekcji. W tym momencie 9 staje się najważniejsza.
Algorytm tyrana prowadzi do wyłonienia nowej jednostki centralnej. Jest to szybka strategia
 po 2 przejściach wybierana jest nowa jednostka rządząca. Jednak robi się problem, gdy to
proces numer 1 zaczyna wysyłać komunikaty do wszystkich (a nie numer 4 jak na
przykładzie). Wtedy sama 1 wyśle n-1 komunikatów.
2) Algorytm pierścieniowy
3
4
2
5
1
6
8
7
W tym algorytmie przyjmuję się, że procesy są fizycznie i logicznie uporządkowane, tak, że
każdy zna swojego następcę. Gdy jakikolwiek proces zauważy brak działania koordynatora,
buduje komunikat ELEKCJA, który zawiera jego własny numer, i nadaje go do swojego
następcy. Jeśli następca okazałby się wyłączony, to nadawca pomija go i kontaktuje się z
następnym członkiem pierścienia lub kolejnym za nim  aż do odnalezienia działającego
procesu. W każdym kroku nadawca dodaje swój numer procesu do listy w komunikacie.
Ostatecznie komunikat dochodzi do procesu, który zapoczątkował jego obieg. Proces ten
rozpoznaje to zdarzenie po odebraniu komunikatu z własnym numerem. W tym miejscu
następuje zmiana typu komunikatu na KOORDYNATOR i obieg się powtarza, tym razem po to,
by zawiadomić wszystkie inne procesy o nowym koordynatorze (procesie, który ma na
utworzonej liście największy numer) oraz o członkach nowego pierścienia.
Na podstawie powyższego rysunku wygląda to tak:
Proces numer 4 zauważa, że nie ma koordynatora (proces 8 umarł) i wysyła komunikat z
potwierdzeniem do procesu 5, który przekazuje go dalej dołączając swój numer. 6 jest
zepsuty, więc przesyła do 7 i 7 zostaje nowym koordynatorem.
Ilość komunikatów będzie mniejsza niż w przypadku algorytmu tyrana, ale czas będzie gorszy,
ponieważ komunikaty muszą obiec cały pierścień. Ten algorytm jest stosowany w
komputerach mimo, że algorytm tyrana jest skuteczniejszy i szybszy.
45
Systemy operacyjne  skrypt do wykładu Autor: Efcia
SYNCHRONIZOWANIE DZIAA
ANIA PROCESORÓW
Dostępy do sekcji krytycznych będą odbywać się w ramach TRANSAKCJI. (str. 178)
Transakcja  ma swój początek i koniec, składa się z uporządkowanych sekcji działań. Cechy:
" Niepodzielność (ang. atomicity)  ciąg działań może wykonać się w całości albo wcale, nie może
wykonywać się częściowo
" Spójność (ang. consistence)  transakcja nie może naruszać niezmienności systemu; system
operacyjny nie ma tu  dużo do powiedzenia
" Izolacja (ang. isolation)  jeżeli w systemie zachodzi więcej niż jedna transakcja to nakładają się
na siebie w czasie
" Trwałość (ang. durability)  raz wstrzymanej transakcji nie można odwołać; nie można odwołać
skutków transakcji
Powyższe właściwości określa się często skrótem ACID od pierwszych liter angielskich nazw.
Granulacja obsługi zasobów  jeżeli plik jest otwierany przez dużą liczbę transakcji może być
kłopotliwa.
METODY IMPLEMENTACJI TRANSAKCJI
1) Prywatna przestrzeń robocza
Procesowi rozpoczynającemu transakcję przydziela się prywatną przestrzeń roboczą zawierającą
wszystkie pliki (i inne obiekty), do których ma on dostęp. Transakcja nie zostanie zatwierdzona
lub zaniechana, dopóki wszystkie operacje czytania i zapisywania odnoszą się do prywatnej
przestrzeni roboczej, a nie do  rzeczywistej , przez którą rozumie się zwykły system plików.
Istnieją dwie optymalizacje umożliwiające tą implementację:
1. Nie zachodzi konieczność wykonywania prywatnej kopii pliku, który jest przez proces
czytany, ale nie zmieniany. Można w tym przypadku posłużyć się jego rzeczywistym
egzemplarzem (chyba że został zmieniony już po rozpoczęciu transakcji). W wyniku tego
procesowi rozpoczynającemu transakcję wystarczy utworzyć prywatną przestrzeń roboczą,
w której  poza wskaz
nikiem wstecz do przestrzeni roboczej procesu rodzicielskiego  nie
ma nic innego. Dla transakcji na najwyższym poziomie przestrzenią roboczą procesu
rodzicielskiego jest  rzeczywisty system plików. Jeżeli proces otwiera plik do czytania to
stosuje się wskaz
niki wstecz, aż do zlokalizowania pliku w przestrzeni roboczej procesu
rodzicielskiego (lub dalszych przodków).
2. Jeśli plik otwiera się do zapisywania, to można go odnalez
ć tak samo jak przy czytaniu, z tym
że obecnie należy go najpierw przekopiować do prywatnej przestrzeni roboczej. Druga
optymalizacja usuwa tutaj większość operacji kopiowania. Zamiast kopiowania całego pliku
do przestrzeni roboczej kopiuje się tylko indeks pliku. Indeks jest blokiem danych
stowarzyszonym z każdym plikiem, w którym zawarto informację o położeniu dyskowych
bloków pliku. Używając prywatnego indeksu, można czytać plik w zwykły sposób, ponieważ
zawarte w nim adresy dyskowe odnoszą się do oryginalnych bloków pliku na dysku.
Natomiast pierwsza modyfikacja bloku pliku wywołuje utworzenie jego kopii, której adres
zostaje wstawiony do indeksu. Blok można wówczas aktualizować bez naruszania jego
46
Systemy operacyjne  skrypt do wykładu Autor: Efcia
oryginału. Z dodanymi blokami postępuje się podobnie. Nowe bloki nazywa się czasami
cieniami bloków.
Proces wykonujący transakcję ma wgląd w zmieniony plik, lecz wszystkie inne procesy nadal
oglądają plik oryginalny. Przy bardziej złożonej transakcji prywatna przestrzeń robocza może
zawierać wiele plików zamiast jednego. W przypadku zaniechania transakcji usuwa się po prostu
prywatną przestrzeń roboczą, a wszystkie prywatne bloki wracają z powrotem na listę bloków
wolnych. Jeśli dochodzi do zatwierdzenia transakcji, to w sposób niepodzielny przemieszcza się
indeksy prywatne w przestrzeń roboczą procesu rodzicielskiego. Bloki, które po tym zabiegu
stały się niedostępne, umieszcza się na liście bloków wolnych.
2) Rejestr zapisów wyprzedzających jest nazywany czasami listą zamiarów
Metoda ta pozwala na modyfikowanie plików w miejscach ich występowania, lecz przed zmianą
dowolnego bloku następuje zapisanie rekordu do rejestru zapisów wyprzedzających,
przechowywanego w pamięci trwałej. Zapisywane są tam rekordy:
" Która transakcja dokonuje zmiany
" Jakie pliki, sektory podlegają transakcji
" Kiedy zachodzi transakcja
" Stan i nowe zapisy
Zmiana w pliku następuje dopiero po skutecznym zapisaniu tych danych do rejestru.
Jeżeli transakcja się powiedzie i zostanie zatwierdzona, to do rejestru wpisuje się rekord
zatwierdzenia, co jednak nie pociąga zmian w strukturach danych, ponieważ zostały one już
zaktualizowane.
Zatwierdzenie transakcji  po zakończeniu transakcji wszyscy biorący w niej udział muszą wiedzieć,
że transakcja się zakończyła i z jakim skutkiem.
Stosowany jest protokół zatwierdzania transakcji  zakłada on, że istnieją 2 grupy procesów 
koordynator transakcji oraz inni.
2-fazowe zatwierdzenie:
1. Przygotowanie do zatwierdzenia transakcji  w momencie, gdy koordynator widzi, że
wszystko przygotowania zostały zakończone.
K inni
Przygotowanie
Gotowe
I
Koordynator wie, że transakcja
została zakończona, jeszcze inni o tym
Koniec
nie wiedzą
II
47
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Do implementacji systemów transakcyjnych służy:
1. Zajmowanie
" Jeżeli w ramach transakcji system odczytuje coś, to dane ulegają zamknięciu i w czasie
trwania transakcji nikt nie ma do nich dostępu.
" Zajmowanie może być wykonywane za pomocą jednego zcentralizowanego zarządcy zajęć
lub za pomocą zarządców lokalnych na poszczególnych maszynach, zawiadujących plikami
lokalnymi.
" Wykonywanie zajęć i zwolnień dokładnie w chwilach, gdy są potrzebne oraz gdy przestaną
być niezbędne, może prowadzić do niespójności i blokad.
" Aby uniknąć blokad stosuje się technikę ZAJMOWANIE DWUFAZOWE ZASOBÓW
Zajmowanie
Zwalnianie
zasobów
zasobów
I  faza wzrostu II  faza zaniku
(zamykania transakcji)
Proces w fazie wzrostu dokonuje najpierw wszystkich zajęć, po czym zwalnia je w fazie
zaniku. Jeżeli proces powstrzymuje się od aktualizacji jakiegokolwiek pliku do czasu osiągnięcia
fazy malenia, to z niepowodzeniem przy wykonywaniu jakiegoś zajęcia można sobie radzić po
prostu przez zwolnienie wszystkich zajęć, odczekanie jakiś czas i rozpoczęcie wszystkiego od
nowa.
W wielu systemach faza zaniku nie następuje dopóki transakcja nie zostanie zakończona przez
zatwierdzenie lub zaniechanie. Nazywane jest to ścisłym zajmowaniem dwufazowym.
Zajmowanie, nawet w organizacji dwufazowej, może prowadzić do blokad. Jeśli dwa procesy
próbują dokonać dwóch takich samych zajęć w odwrotnej kolejności, to może powstać blokada.
W takich wypadkach stosuje się typowe techniki, jak wykonywanie wszystkich zajęć według
pewnego kanonicznego porządku, które zapobiegają pętlom przetrzymywania i czekania. Można
również stosować wykrywanie blokad przez utrzymywanie grafu jawnie przedstawiającego,
które procesy dokonały zajęć i jakich, oraz które procesy ubiegają się o nie, i analizowanie go
pod kątem występowania pętli.
2. Znaczniki czasu
Każdej transakcji przypisuje się znacznik czasu w chwili jej zgłoszenia. Z każdym plikiem w
systemie kojarzy się znacznik czasu czytania i znacznik czasu pisania, informujący o tym, przez
którą zatwierdzoną transakcję był on ostatnio czytany lub zapisany. Jeśli transakcje są krótkie i
rzadko rozmieszczone w czasie, to gdy proces próbuje dostępu do pliku, znaczniki plikowe czasu
czytania i pisania będą na ogół mniejsze (starsze) od znacznika czasu bieżącej transakcji. Takie
48
Systemy operacyjne  skrypt do wykładu Autor: Efcia
uporządkowanie oznacza, że transakcje są przetwarzane we właściwej kolejności i wszystko jest
w porządku.
3. Optymistyczne nadzorowanie transakcji:
" Nie kontrolujemy niczego.
" Zakładamy, że nie pojawią się blokady, wszystko odbywa się w swoim czasie.
" To podejście można stosować, gdy ilość transakcji jest mała.
" Utrzymuje się informacje o tym, które z plików były czytane i zapisane; w chwili
zatwierdzania transakcji sprawdza się, czy żadna z innych transakcji nie zmieniła plików
nadzorowanej transakcji po jej rozpoczęciu; jeśli tak, to następuje zaniechanie transakcji, w
przeciwnym razie transakcja zostaje zatwierdzona.
" Zaletą tego rozwiązania jest jego odporność na blokady oraz umożliwianie maksymalnej
równoległości działań, gdyż żaden proces nigdy nie musi czekać na zajmowanie.
" Wadą jest to, że możliwe niepowodzenie prowadzi do ponowienia całej transakcji.
BLOKADY
Blokady w systemach rozproszonych są podobne do blokad w systemach jednoprocesorowych, z tym
że są jeszcze gorsze. Trudniej jest ich unikać, zapobiegać im, czy choćby je wykrywać, i trudniej
stosować działania naprawcze po ich wykryciu, ponieważ wszystkie niezbędne informacje są
rozrzucone po wielu maszynach.
WYKRYWANIE ROZPROSZONYCH BLOKAD
1. Scentralizowane wykrywanie blokad
Choć każda maszyna utrzymuje graf własnych procesów i zasobów, to koordynator centralny
działa na grafie zasobów całego systemu (powstałym z połączenia wszystkich poszczególnych
grafów). Jeżeli koordynator wykryje pętlę, to aby przełamać blokadę, kończy któryś z procesów.
W odróżnieniu od przypadku scentralizowanego, w którym wszystkie informacje są
automatycznie dostępne we właściwym miejscu, w systemie rozproszonym należy je dostarczać
jawnie. Każda maszyna obsługuje graf własnych procesów i zasobów. Istnieje kilka sposobów
uzyskania tych informacji. Po pierwsze, przy każdym dodaniu lub usunięciu krawędzi w grafie
zasobów do koordynatora może zostać wysłany komunikat z odpowiednią aktualizacją. Po
drugie, okresowo każdy proces może wysyłać wykaz krawędzi dodanych lub usuniętych od czasu
poprzedniej aktualizacji. Druga metoda wymaga mniejszej liczby komunikatów niż pierwsza. Po
trzecie, koordynator może poprosić o potrzebne informacje, gdy przyjdzie na to pora. Niestety
żadna z tych metod nie działa poprawnie.
Może dojść do sytuacji zwanej fałszywą blokadą. Wiele algorytmów dotyczących blokad w
systemach rozproszonych produkuje fałszywe blokady, wskutek niekompletnych danych lub
opóz
nionych informacji.
49
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Brak pomysłu na graf przydziału zasobu w rozproszonych systemach operacyjnych.
2. Algorytm Chandy-Misra_Haasa  przykład rozproszonego wykrywania bloady
" Procesy wymieniają się informacjami o zapotrzebowaniu na zasoby.
" Proces oczekujący na zasób wysyła do innego procesu komunikat (P1 czeka na coś, co ma P2).
1 1 2
1 2 3
P1 P1 P1
1 2
1
2 numer twórcy
1 4 numer
komunikatu adresata
numer
P1
nadawcy
3 1
1
P1 otrzymuje komunikat, że odbiorca i twórca
komunikatu to 1, więc następuje blokada.
W wykrywaniu blokad biorą tylko udział potencjalni twórcy komunikatu. Rozwiązaniem jest
samobójstwo twórcy komunikatu. Pozostałe rozwiązania w przypadku blokad  tak samo, jak w
przypadku systemu operacyjnego.
ZARZ
DZANIE PROCESAMI W SYSTEMACH ROZPROSZONYCH
Zakłada się, że procesory są identyczne i procesy mogą być przemieszczane.
  gęstość strumienia (strumień zgłoszeń) zgłaszających się procesów na danym procesorze (np. 10
procesów/1 sekundę)
ź  strumień obsługi  zdolność ALU do wykonania pewnej liczby procesów w danym czasie
ź > 
T  czas oczekiwania procesu w kolejce
50
Systemy operacyjne  skrypt do wykładu Autor: Efcia
T = ź - w przypadku jednej kolejki, każdy proces ma własną kolejkę
T
ź

Zakładając, że tworzymy jedną dużą kolejkę:
T = ź = "
W systemach rozproszonych zarządzanie scentralizowane prowadzi do n-krotnego skrócenia czasu.
ALE utworzenie takiej kolejki jest uciążliwe  musi być dobra komunikacja między procesami:
" W przypadku muli komputerów mamy skomplikowaną sytuację  trzeba wziąć pod uwagę czas
przesyłania komunikatów.
" Nie zawsze opłaca się wykonywać procesy na losowych komputerach.
PRZYKA
ADOWE ALGORYTMY PRZYDZIAA
U PROCESORA
1. Deterministyczny algorytm oparty na teoretycznym grafie  służy do minimalizacji przesłań
sieciowych
100 5000
- proces
300 1000
400
200
przykładowy
podział
Graf dzieli się na partycje, aby suma krawędzi łączących była minimalna. WADA  trzeba znać
liczby i zbiór wierzchołków. W przypadku architektury otwartej  zbiór wierzchołków i etykiety
krawędzi nie są znane.
2. Algorytm UP AND DOWN  grupy procesów mają być obsługiwane sprawiedliwe.
Koordynator utrzymuje tabele użyć, która zawiera po jednym wpisie na użytkownika 
początkowo zero. Gdy zachodzą istotne zdarzenia, wtedy do koordynatora wysyła się
komunikaty w celu zaktualizowania tablicy. Decyzje przydziału podejmuje się na podstawie taj
51
Systemy operacyjne  skrypt do wykładu Autor: Efcia
tablicy w chwili, gdy wystąpi zdarzenie uruchamiające procedurę planowania: zapotrzebowanie
na procesor, zwolnienie procesora lub impuls zegara.
procesy
czas
Wpisy w tablicy użyć mogą być dodatnie, zerowe lub ujemne. Dodatnie wpisy oznaczają, że stacja
robocza użytkuje sieciowe zasoby systemu, natomiast wpisy ujemne oznaczają, że stacja potrzebuje
zasobów. Wpisy zerowe są neutralne.
Ta strategia jest adaptacyjna. Jeżeli pojawi się nowy użytkownik, który potrzebuje dużo procesów 
wykres bardzo rośnie, ale też szybko spadnie na wartości ujemne i będzie czekać.
3. Rozproszony algorytm równoważenia obciążeń jednostek centralnych
" Zakładamy, że dla każdych jednostek obliczeniowych jest dopuszczalna wartość progowa,
której nie można przekroczyć.
" Jeśli wykryjemy przekroczenie progu, system ma za zadanie wybranie nowej jednostki i jeśli
ma ona wartość niższą od progu, do niego są kierowane wszystkie zadania  po pewnej ilości
losowanych prób, losowanie ustaje i wszystkie działania na przeciążonej jednostce
" Mutacja algorytmu  procesor, na którym kończone jest losowanie, może wylosować inny i
sprawdzić czy przekroczył próg; wtedy zabiera mu się zadania.
DOCHODZENIE DO UZGODNIEC
W SYSTEMIE
1. Algorytm bizantyjski (bizantyjskich generałów)
Procesory, z których każdy generuje
komunikat i wysyła go do
1 2 3 4
wadliwy
pozostałych. Niektóre procesory
mogę wysyłać fałszywe komunikaty.
Każdy wysyła swój komunikat do
sąsiadów.
1.  wysyłanie komunikatów
2 3
1 4
2.  (1, 2, x, 4) (1, 2, y, 4) (?, ?, ?, ?) (1, 2, z, 4) - wektory komunikatów
52
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Procesor 1 zebrał wektory odpowiedzi i szuka  zdrajcy . Procesory 2 i 4 dostają ten sam
wektor wynikowy.
3.  wysyłanie komunikatów
4.  (1, 2, y, 4)
(a, b, c, d)
(1, 2, z, 4)
g
(1, 2, ?, 4) - wektor wynikowy - wiemy, które procesory działają dobrze, a które nie
W wektorze wynikowym wpisujemy wartości, które występują w przewadze.
Dla 3m + 1 procesorów można wykryć maksymalnie 3 zdrajców.
ROZPROSZONE SYSTEMY PLIKÓW
Dzielimy na 2 grupy:
" Usługi plikowe  operacje na plikach, np. odczyt, zapis, zmiana uprawnień
" Usługi katalogowe  lokalizacja plików: kontrola mechanizmów tworzenia kopii danego pliku
Semantyka dzielenia plików:
1. Semantyka UNIKSOWA  odczyt z pliku zwraca ostatnio zapisaną wartość
2. Semantyka SESJI  zmiany powstałe podczas sesji są widoczne dopiero po jej zakończeniu
3. Semantyka PLIKÓW STAA
YCH  nie ma operacji zapisu do pliku, każda generacja zapisu to
utworzenie nowego pliku, nie ma tu dostępu do pliku, który ma nieaktualne dane; inne pliki
muszą uzyskać nową nazwę pliku
4. Semantyka TRANSAKCYJNA  każdy dostęp do pliku musi być realizowany za pomocą
transakcji; operacje plikowe muszą mieć cechy transakcji
Większość pliku w systemie istnieje tymczasowo; tylko niewielka część plików ma charakter stały.
Usługi katalogowe muszą być realizowane na 2 sposoby:
" Identyfikator plików zawiera identyfikator położenia
Zakłada się, że do operacji odczytu i zapisu potrzebne jest uzyskanie zgody N/2 + 1 serwerów.
53
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Serwer wysyła zgłoszenie o
zgodę na zapis pliku.
Na powyższym obrazku mamy 4 wersje nieaktualne i 5 aktualnych pliku. Wśród N/2 + 1 serwerów
znajduje się co najmniej jeden, który posiada aktualną wersję pliku.
Modyfikacje metody:
" Wartość N dzieli się na kworum czytania i kworum pisania, a ich suma musi być ostro większa od
N:
N > +
W przypadku pamięci operacyjnej sytuacja wygląda gorzej niż w przypadku operacji na plikach:
" Pamięć operacyjna  zapotrzebowanie na dzielenie zasobów jest bardzo wysokie
SPÓJNOŚĆ PAMI
CI OPERACYJNEJ
Modele spójności pamięci operacyjnej:
1. Spójność ŚCISA
A  odczyt komórki pamięci zwraca ostatnio zapisaną wartość; w systemach
rozproszonych jest to prawie niewykonalne, potrzeba czasu na synchronizację; ciężko uzyskać
spójność
x = 0
W(x)1
oś czasu
R(x)1
R(x)0
Zapis do komórki Najpierw uzyska
procesy x wartości 1 wartość 0, a potem 1
Odczyt zmiennej x
54
Systemy operacyjne  skrypt do wykładu Autor: Efcia
2. Spójność SEKWENCYJNA  wszystkie procesy widzą ten sam ciąg odwołań do pamięci
x = 0
W(x)1
W(x)0
R(x)0
R(x)1
R(x)1 R(x)0
Nie trzeba natychmiastowo odczytywać zmienionej wartości.
3. Spójność PRZYCZYNOWA
x = 0
W(x)1
R(x)1
W(x)2
R(x)1
R(x)2
R(x)1
R(x)2
Niezgodność przyczynowości. Aby 2 procesy widzą różną
była zgodność trzeba zlikwidować sekwencję wartości
R(x)1, wtedy i mają prawo
widzieć różne sekwencje, bo i
są niezależne przyczynowo.
Spójność STAA
A  w systemie występują zmienne synchronizujące, zawierają one segmenty lub
strony z pamięci. Brak kontroli sekwencji zdarzeń.
Jeżeli na zmiennych synchronizujących dokonywane są zmiany to wszyscy muszą to widzieć.
Dostęp do zmiennych synchronizujących jest spójny sekwencyjnie. Operacje na pamięci
skojarzone z daną zmienną synchronizującą są zawieszone w systemie.
CPU CPU CPU
PP  pamięć
podręczna,
j j j RAM
PP X PP X PP O np. cache
55
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Może być system, że ta sama komórka pamięci może znajdować się w wielu lokalizacjach.
Każdy z procesorów może coś zmienić w komórce, wtedy wszystkie inne stają się nieaktualne.
Są 2 strategie aktualizacji:
1. Protokół przepisywania  gdy mamy do czynienia z systemem zapisu; gdy zostanie wykryta
zmiana stanu, to procesor ma obowiązek przesłać do innych kopie nowej strony.
2. Protokół jednokrotnego przepisywania  ma ograniczyć przesłania po szynie; każda strona w
pamięci operacyjnej albo w pamięci podręcznej może występować w 3 różnych stanach
(czysta, brudna, nieważna):
" Strona czysta  wszystkie kopie są czyste; gdy pojawia się operacja zapisu, trzeba
dokonać aktualizacji i strona zmienia się na brudną  jest ważna, ale nie ma kopii i
istnieje początkowo tylko w jednym egzemplarzu; należy zwracać się do pamięci
podręcznej, aby ją przeczytać
" Po zapisie wszystkie strony są brudne lub wręcz nieważne (tylko strony biorące udział w
zapisie).
56
Systemy operacyjne  skrypt do wykładu Autor: Efcia
ROZDZIAA
9 - INNE SYSTEMY
Charakterystyka nowych systemów:
" Oparte na szybkich sieciach
" Będą rozproszone (zlokalizowane na obszarze kraju lub kontynentu) systemy
" Będą zorganizowane tak, aby dla użytkownika widoczna była jednolita pamięć itp.
Przepustowość łączy rośnie dużo szybciej niż możliwości obliczeniowe.
Światłowody  przepustowość zależy od tego, co znajduje się na końcach kabla, osiąga prędkość
600 000 GB/s. Jednak daleko nam do tej granicy.
Inna sieć
Inna sieć
Bardzo szybka sieć lokalna
GRID  systemy tej klasy są tak nazywane; w takiej sieci mamy dostęp do wszystkich zasobów bez
względu na to, gdzie się podłączamy
Mechanizmy obowiązujące w systemach operacyjnych, które powinny być przystosowane do takich
systemów.
1. Przy założeniu swobodnego obszaru  mechanizmy routingu muszą działać inaczej.
2. Jeżeli mamy uzależnienie zasobów sprzętowych i obliczeniowych od obecnej sytuacji w
systemie  globalne przetwarzanie danych (proces wykonuje się bez względu na to, że jakiś
procesor jest podłączony do systemu), bezstratne przechowywanie danych (wyłączenie
jednego urządzenia nie może spowodować utraty danych).
LOKALIZACJA I NAZEWNICTWO ZASOBÓW
Założenia w systemie klasy GRID:
1. Wszystkie zasoby systemu (w szczególności pliki) są widziane za pomocą GVID  globalny
identyfikator lokalizacji zasobów.
2. Zakłada się, że nie używamy nazw plików i adresów, ale używamy takich identyfikatorów. Do
utworzenia takiego identyfikatora używana jest tzw. FUNKCJA HASZUJ
CA:
1) Jest obliczeniowo łatwa
2) Wynik jest niewielki w sensie objętości danych
57
Systemy operacyjne  skrypt do wykładu Autor: Efcia
3) Jest nieodwracalna lub trudno odwracalna
4) Dobra funkcja haszująca powinna mieć wartość pseudolosową  niewielka zmiana
argumentu, np. 1 bit w pliku, powoduje drastyczną zmianę  wynik może zmienić się na
wszystkich bitach
a) FUNKCJA HASZUJ
CA
H(data, właściciel, plik)
b) KODOWANIE M z N  nie tylko zapewnia unikalność nazwy, ale też bezstratne
przechowywanie danych
Plik kodowany w postaci N fragmentów, które mogą być rozmieszczone na
dowolnych maszynach w sieci. M z N fragmentów umożliwia odtworzenie pliku
N = 32
(plik) &
M = 8
Z 32 maszyn 25 musi ulec awarii, aby system zawiódł. Jeżeli 8 zawsze działa
poprawnie, to zawsze uzyskamy odtworzenie pliku.
ROUTING LOKALIZACJI ZASOBÓW
1. Strategia zalewowa (wyszukiwanie w trybie zalewowym)  najbardziej kosztowne
rozwiązanie. Istnieje jedna możliwość 100% lokalizacji zasobów. Poszukujący wysyła
zapytanie do wszystkich sąsiadów czy posiadają dany plik, a sąsiedzi robią to samo aż do
znalezienia pliku. Duża liczba komunikatów i wiele maszyn biorą w tym udział mimo, że nie
posiadają danego zasobu.
2. Algorytm probabilistyczny  brak 100% skuteczności, u jej podstaw leży mechanizm
kryptograficzny.
3. SHA-1  secure hash algoritm  160 bitowe, po uzyskaniu globalnego identyfikatora zasobu
mamy ciąg 160 bitów, jest dzielony na 10 porcji po 16 bitów.
4. Filtr Bloom a - 2 bitów = 64 Kb  zapamiętują położenie obiektów w danym węz
le sieci
&
16 16 16
10 razy
& & & & & &
Jeżeli mamy 160 bitowy identyfikator zasobów to pokazuje nam położenie w 64Kb łańcuchu.
58
Systemy operacyjne  skrypt do wykładu Autor: Efcia
Przeważająca część bitów jest wyzerowana. Filtr jest w stanie zapamiętać położenie blisko
kilkuset, a nawet kilkunastu tysięcy obiektów. Jest on niezawodny, ale jeśli zapisujemy bardzo dużo
do filtrów, to pojawi się wiele jedynek i filtr będzie zdezorientowany i będzie odpowiadać, że zawsze
posiada dany obiekt.
Filtr Bloom a
Brak centrum. Chcemy przekazywać gdzieś dane o połączeniach obiektu. Jeżeli z każdym
węzłem będzie skojarzony filtr Bloom a ( ) to będzie to bardzo efektywne.
Jak szukać informacji w skali całej sieci?
Z każdym węzłem jest skojarzonych więcej filtrów Bloom a (często 4). Mówią nam o tym jakie jest (p
 prawdopodobieństwo):
" p = 1  taki jak przy węzłach
" p < jedności  czy znajdziemy obiekt w odległości 2 węzłów
" p = 3  połączenie w odległości 3 węzłów
" p = 4  połączenie w odległości 4 węzłów
1. Wyszukiwanie zalewowe
2. Wyszukiwanie probabilistyczne  posługujemy się informacjami zawartymi w filtrach Bloom a i
w przypadku, gdy system zawiera bardzo dużo obiektów, to filtr Bloom a wypełnia się jedynkami
i często odpowiada fałszywie  odpowiada, że jest obiekt w danym węz
le, a w rzeczywistości go
tam nie ma.
Jeżeli strategia probabilistyczna zawiedzie to wykorzystujemy strategię zalewową.
59
Systemy operacyjne  skrypt do wykładu Autor: Efcia
koszt
7
6
5
zalewowy
4
probabilistyczny
3
2
1
1 2 3 4 5 6
7
odległość między węzłami
Jedynie w około 20% trzeba stosować strategię zalewową. Natomiast, jeśli węzły są blisko siebie to
wartość ta jest blisko 0.
Podsumowanie:
" Jest to architektura, w której nie ma struktur zarządzania.
" Żadna maszyna w takim systemie nie posiada pełnej informacji o zasobach.
" Odległość ma wpływ na efektywność algorytmów.
INTERNET MAPPING PROJECT w latach 90-tych
W latach 50-tych przeprowadzono eksperyment. Steven Milgen napisał list:  Jeżeli znasz Kowalskiego
to wyślij do niego ten list, jeśli nie to prześlij dalej. Następnie wysłał ten list to kilku tysięcy ludzi.
Część doszła, a część zaginęła. Średnia długość listy osób  5-6. Podobną długość dla całej planety
ocenia się na około 7-8.
W przypadku grafu losowego:
Prawdop. że
losowo
wybrany węzeł
jest danego
stopnia
Zjawisko dla sieci społecznych
węzeł
10 oraz dla Internetu (zmieniają się
tylko wykładniki na osiach).
10
P(k) ~
10
10
10
10
& &
10 10 10 10 10 10 & & . Stopień węzła
W takich sieciach istnieją tzw. haby  węzły ogromnej ilości połączeń (sąsiadów).
Zjawiska emergentne (energent fenoma)  nie da się ich wywiez
ć z opisu składowych systemu.
60