System komputerowy
• Architektura systemu operacyjnego w znacznym stopniu zależy od właściwości sprzętu komputerowego, na którym będzie on uruchamiany
• Wiele współczesnych urządzeń komputerowych konstruowanych jest z myślą o udostępnieniu efektywnych sposobów realizacji typowych zadań systemu operacyjnego
Założenia
- Program (ciąg poleceń) dla komputera jest przechowywany w pamięci tak samo jak zwykłe dane, które ten program ma przetworzyć
- Kolejne polecenia programu mogą być automatycznie pobierane z pamięci i wykonywane przez jednostkę centralną.
Koordynacja CPU i urządzeń we/wy
- Przesyłanie danych sterowane przerwaniami
- Przesyłanie danych na zasadzie bezpośredniego dostępu do pamięci (DMA)
Procedura przesyłania danych
1. Procesor ustawia odpowiednie rejestry sterownika urządzenia, po czym wznawia normalną pracę.
2. Sterownik urządzenia bada zawartość tych rejestrów, aby określić, jakie ma podjąć działanie. Jeśli, na przykład zostanie rozpoznane polecenie czytania, to sterownik zainicjuje przesyłanie danych z urządzenia do swojego lokalnego bufora.
3. Kiedy przesyłanie danych zostanie zakończone, sterownik za pomocą przerwania informuje jednostkę centralna, że zakończył swoje działanie.
4. Procesor po otrzymaniu sygnału przerwania wstrzymuje bieżącą prace i pobiera zawartość ustalonego miejsca pamięci, które na ogół zawiera adres procedury obsługującej dane przerwanie.
5. Procedura obsługi przerwania przesyła dane z lokalnego bufora sterownika do pamięci głównej.
6. Po zakończeniu przesyłania danych procesor jest gotowy do wznowienia przerwanych obliczeń. Następuje pobranie wcześniej zapamiętanego adresu powrotnego i wznowienie przerwanych obliczeń, tak, jakby przerwania nie było.
Adresy procedur obsługi przerwań pochodzących od różnych urządzeń przechowuje się na ogół w tzw. wektorze przerwań.
Bezpośredni dostęp do pamięci
• Szybkie urządzenia wejścia-wyjścia korzystają z bezpośredniego dostępu do pamięci operacyjnej (DMA - Direct Memory Access). W tym przypadku sterownik danego urządzenia przesyła bezpośrednio cały blok danych miedzy własnym buforem a pamięcią - bez interwencji procesora.
• Przerwanie wypada jeden raz na cały blok danych, a nie po przesłaniu każdego znaku (lub słowa), jak w przypadku urządzeń powolnych.
• Przebieg procedury przesłania danych:
1. W chwili pojawienia się żądania przesłania danych system operacyjny wybiera z kolejki buforów bufor do przesłania. Może to być pusty bufor wejściowy lub pełny bufor wyjściowy.
2. Adresy źródła i miejsca przeznaczenia umieszcza się w rejestrach sterownika DMA, po czym za pośrednictwem bitów sterujących w rejestrze kontrolnym sterownik DMA dostaje informacje, że należy zainicjować operacje wejścia-wyjścia.
3. Po zakończeniu operacji sterownik wysyła przerwanie do procesora.
• W zależności od architektury sprzętowej przerwania mogą być blokowane, maskowane lub szeregowane wg priorytetów
Struktura pamięci
• Najważniejszym rodzajem pamięci jest pamięć główna (pamięć operacyjna, main memory).
• Pamięć główna jest dostępna dla jednostki centralnej bezpośrednio. Dostęp do każdego elementu pamięci głównej realizowany jest za pomocą unikatowych indeksów. Może on odbywać się za pomocą operacji odczytu i zapisu do pamięci lub automatycznie, gdy pobierane są rozkazy i operandy wykonywanego programu.
• Cykl rozkazowy: pobranie rozkazu - dekodowanie rozkazu - pobranie operandów - realizacja rozkazu - zapis wyniku do pamięci
• W przypadku wielu urządzeń stosuje się odwzorowywanie wejścia/wyjścia w pamięci głównej (porty we/wy).
• Za względu na ograniczenia pamięci głównej, do trwałego przechowywania danych i programów wykorzystuje się pamięć pomocnicza (secondary storage).
• Pamięć podręczna (cache memory) przechowuje wykorzystywane obszary wolniejszych rodzajów pamięci.
Organizacja i architektura komputerów
• Organizacja komputera - bloki funkcjonalne i wzajemne połączenia miedzy nimi
• Architektura komputera - logiczna struktura wewnętrzna, tj. sposób, w jaki programista piszący programy w języku maszynowym widzi platformę sprzętową
Pojecie systemu operacyjnego
• System operacyjny to program, który działa jako pośrednik miedzy użytkownikiem komputera, a sprzętem komputerowym
• Podstawowe zadania systemu operacyjnego:
- Podział zasobów
- Tworzenie wygodnej w użyciu maszyny wirtualnej
• Maszyna wirtualna pozwala na łatwiejsze skorzystanie z następujących zasobów i mechanizmów: wejście-wyjście, pamięć operacyjna, system plików, ochrona zasobów i obsługa błędów, współdziałanie programów, sterowanie programami
Rodzaje systemów operacyjnych
• Podział ze względu na zastosowanie:
- Systemy dla indywidualnego użytkownika
- Serwery informacji i baz danych
- Systemy ogólnego przeznaczenia - systemy wsadowe i interaktywne
- Systemy czasu rzeczywistego (sterowania procesami)
- Systemy równoległe
- Systemy rozproszone
Współcześnie opracowano wiele systemów operacyjnych dla różnych komputerów i do różnych zastosowań. Niektóre zasady ich budowy i działania maja charakter uniwersalny i mogą być omawiane niezależnie od konkretnych rozwiązań
Struktury systemów operacyjnych
• Struktura jednolita
• Struktura warstwowa
• Struktura typu klient-serwer
Składowe systemów operacyjnych
Usługi systemu operacyjnego
• Typowe usługi systemu operacyjnego:
- Wykonanie programu
- Operacje wejścia/wyjścia
- Manipulowanie systemem plików
- Komunikacja miedzy procesami
- Kontrola błędów
- Przydzielanie zasobów
- Ochrona
• Oprogramowanie korzysta z mechanizmów s.o. za pomocą funkcji systemowych
Praca systemu operacyjnego
• Przy uruchomieniu komputera uruchamiany jest program rozruchowy (bootstrap), powodujący:
- ustawienie początkowych wartości systemu komputerowego takich jak: rejestry CPU, urządzeń i wektorów przerwań
- wprowadzenie do pamięci jądra systemu operacyjnego
- uruchomienie procesu oczekującego na wystąpienie jakiegoś zdarzenia
• Jeśli nie ma żadnych zadań ani nie czekają na obsługę żadne urządzenia wejscia-wyjscia bądź wymagające odpowiedzi polecenia użytkowników, system operacyjny oczekuje na zdarzenie. Mówimy, że jest on sterowany zdarzeniami.
• Zdarzenia są sygnalizowane za pomocą przerwań sprzętowych lub programowych.
• Spowodowanie przerwania programowego jest często konsekwencja wywołania specjalnej operacji nazywanej wywołaniem systemowym lub funkcja systemowa (system call).
Rodzaje funkcji systemowych
• Nadzorowanie procesów:
- zakończenie, zaniechanie; załadowanie, wykonanie; utworzenie i zakończenie procesu; pobranie i ustawienie atrybutów procesu; zmiana stanu procesu
• Operacje na plikach
- utworzenie, usuniecie pliku; otwarcie, zamkniecie pliku; czytanie i pisanie, zmiana położenia; pobranie i ustawienie atrybutów pliku
• Operacje na urządzeniach
- Żądanie dostępu i zwolnienie urządzenia; czytanie i pisanie, zmiana położenia; pobranie i ustawienie atrybutów urządzenia; przyłączanie i odłączenie logiczne urządzeń
• Utrzymywanie informacji
- pobranie i ustawienie czasu i daty, danych systemowych, atrybutów procesów, systemu plików, urządzeń
• Komunikacja
- utworzenie i zakończenie połączenia; wysyłanie i odbieranie komunikatów; uzyskanie informacji o stanie
Zarządzanie procesami
Proces jest to ciąg czynności wykonywanych za pośrednictwem ciągu rozkazów (programu), których wynikiem jest wykonanie pewnych zadań systemowych lub określonych przez użytkownika.
Proces = zadanie (ang. task)
Graf stanów procesu
Kontekst procesu
Stan procesu i inne informacje pozwalające systemowi operacyjnemu zarządzać procesem jest przechowywany w strukturze zwanej blokiem kontrolnym procesu (inaczej kontekstem procesu).
Procesy współbieżne
Współbieżność jest terminem nadawanym systemom, w których może istnieć wiele procesów w stanie wykonywania, tj. takich, których obliczenia rozpoczęły się, ale ich nie zakończono lub nie zaprzestano (zakończenie błędne).
Systemy operacyjne dopuszczające współbieżność procesów użytkownika nazywa się systemami wielozadaniowymi.
Proces aktywujący nowy proces nazywa się procesem macierzystym, zaś nowy - procesem potomnym.
Proces jest niezależny, jeżeli nie wpływa na zachowanie innych procesów, zaś inne procesy nie mogą na niego oddziaływać. Proces, który nie spełnia tej własności nazywa się procesem współpracującym.
2. Przydział dostępu do procesora
Gdy do dyspozycji jest mniej procesorów ni_ procesów, należy poszczególnym zadaniom przydzielać czas pracy procesora w miarę potrzeb.
Przydzielaniem tym zajmuje się specjalna część systemu operacyjnego zwana planista lub dyspozytorem (ang. scheduler).
Przełączanie kontekstu polega na przechowaniu stanu starego procesu i załadowania przechowywanego stanu nowego procesu (odtworzenie środowiska procesu).
W większych systemach występują dwa rodzaje dyspozytorów:
_ niskiego poziomu - zajmuje się przydzielaniem czasu procesora przeszukując kolejkę procesów gotowych
_ wysokiego poziomu - zajmuje się strategia uruchamiania procesów, usuwając z pamięci te, których dalsze wykonanie jest przez pewien czas niemożliwe (np. z powodu zajętości urządzenia zewnętrznego, wykonywania procesu o wyższym priorytecie itp.)
3.Algorytmy szeregowania
Miara algorytmu planowania mogą być:
_ sprawność (szybkość) wykonywania zadań
_ czas odpowiedzi na żądania użytkownika
_ czas reakcji na zdarzenia zewnętrzne (w systemach czasu rzeczywistego)
_ wykorzystanie procesora
_ przepustowość, czyli liczba procesów kończonych w jednostce czasu
_ czas cyklu przetwarzania, upływający miedzy chwila nadejścia procesu do systemu do jego zakończenia
_ czas oczekiwania w kolejce procesów gotowych
Popularne algorytmy szeregowania:
Najpierw najkrótsze zadanie (SJF)
_ Kolejka jest uporządkowana według czasu potrzebnego do wykonania każdego procesu
_ Wykorzystywany w systemach, gdzie można oszacować czas wykonywania procesów
_ Celem jest zminimalizowanie długości przetwarzania krótkich prac
_ Jeżeli dwa procesy maja taki sam czas przetwarzania, pierwszy wykonywany jest ten, który wcześniej pojawił się w systemie
_ Algorytm optymalny
_ Wersja algorytmu Najpierw najkrótsze zadanie z wywłaszczaniem pozwala na zawłaszczenie procesora przez proces, który ma krótszy czas wykonywania ni_ aktualnie wykonywany
Pierwszy nadszedł - pierwszy obsłużony (FCFS)
_ Najprostszy w realizacji (kolejka FIFO)
_ Pierwszy proces z kolejki otrzymuje procesor
_ Procesy są wstawiane na koniec kolejki
_ Nadaje się do procesów o porównywalnej długości wykonania
_ Czas oczekiwania, w przypadku dużej różnicy w czasach wykonywania może być bardzo długi
Szeregowanie karuzelowe (round-robin)
_ Każdemu procesowi przydzielany jest taki sam przedział czasu
(kwant czasu, ang. time-slice)
_ Po upływie zadanego czasu, proces jest przerywany i wstawiany na koniec kolejki (kolejka cykliczna)
_ Procesy krótkie mogą się zakończyć w ramach przydzielonego czasu, zaś procesy długie mogą kilkakrotnie obiegać cały cykl kolejki
_ Niezbyt wydajny dla dużej ilości procesów
_ Im mniejszy kwant czasu, tym bardziej istotne jest szybkie przełączenie kontekstu
Szeregowanie według priorytetów
_ Każdemu procesowi przyporządkowuje się priorytet (np. 0-15)
_ Jako pierwszy wykonuje się proces z najwyższym priorytetem
_ Algorytm z wywłaszczaniem pozwala na przejecie procesora przez proces o wyższym priorytecie niż aktualnie wykonywany.
_ Może dojść do nieskończonego blokowania („zagłodzenia” ang. starvation) procesu o niskim priorytecie w sytuacji, gdy działa duża ilość procesów o wyższym priorytecie.
Łączenie algorytmów
Algorytmy można łączyć ze sobą w celu dostosowania do konkretnych zadań.
Przykład: kombinacja algorytmów priorytetowego i karuzelowego.
_ Dla procesów o różnych priorytetach stosowane jest szeregowanie priorytetowe z wywłaszczaniem
_ Dla procesów o równych priorytetach stosowane jest przełączanie karuzelowe
Zarządzanie pamięcią
Cele zarządzania pamięcią:
_ Umieszczenie w pamięci kilku procesów jednocześnie
_ Dynamiczne przemieszczanie procesów
_ Ochrona zawartości pamięci
_ Dostęp do obszarów dzielonych
Zakres adresów programu nazywa się przestrzenią adresów (nazw), zaś zakres komórek w pamięci fizycznej - przestrzenią pamięci.
Odwzorowaniem adresów (ang. Address mapping) nazywamy funkcje:
f:N →P
gdzie:
N - przestrzeń nazw
P- przestrzeń pamięci
Odwzorowanie adresów polega na zamianie adresów użytych przez programistę na odpowiednie adresy pamięci fizycznej. Jest realizowane przez procedury systemu operacyjnego.
Programista tworząc program dysponuje wygodna „pamięcią wirtualna”, której właściwości są inne niż rzeczywistej pamięci, i tak pisze programy, jakby miały być wykonywane w pamięci wirtualnej.
2. Implementacja mechanizmu odwzorowania adresów
Adresem bazowym nazywamy najmniejszy adres zajmowany przez proces po załadowaniu do pamięci. Adres bazowy (B) jest umieszczany w rejestrze bazowym.
Wszystkie adresy w programie są traktowane jako adresy wzgledne w odniesieniu do adresu bazowego:
f(a)= B+ a
gdzie a - adres programu, B - adres bazowy
Adresem granicznym nazywamy największy adres wykorzystywany przez proces.
Adres graniczny (G)jest umieszczany w rejestrze granicznym.
3. Stronicowanie pamięci
Aby umożliwić tworzenie i uruchamianie programów w przestrzenie adresowej większej niż dostępny rozmiar pamięci fizycznej wprowadzono pojecie pamięci jednopoziomowej, czyli takiej, w której pamięć pomocnicza stanowi rozszerzenie pamięci głównej. Pamięcią pomocnicza może być np. dysk twardy.
Stronicowanie (ang. paging) polega na podziale przestrzeni adresów na jednakowej długości strony. System na bieżąco przydziela obszary na strony w pamięci fizycznej (tzw. ramki stron).
Strony aktywne procesu są umieszczone w pamięci głównej, zaś strony nieaktywne - w pamięci pomocniczej.
Zadania mechanizmu stronicowania:
1. Odwzorowywanie adresów, czyli obliczenie, do której strony należy adres w programie oraz znajdowanie ramki strony, dla danej strony programu.
2. Przesyłanie stron z pamięci pomocniczej do pamięci głównej i odwrotnie.
Odwzorowanie adresu przy stronicowaniu
f(a) = f(p, b) = p'+ b
gdzie a - adres programu, R - rozmiar strony
p= a DIV R - numer strony programu,
b = a MOD R- numer bajtu strony programu,
p' - adres ramki strony p.
Jeżeli w tablicy stron dla danego p nie ma informacji o fizycznym adresie (adres pusty) nastąpi przerwanie z powodu błędu braku strony. Wówczas mechanizm stronicowania prześle stronę z pamięci podręcznej do pamięci głównej i uaktualni tablice stron.
Algorytm wymiany stron stosowany jest do wyboru strony, która ma być przesłana do pamięci podręcznej w celu zrobienia miejsca dla innej strony.
4. Segmentacja pamięci
Segmentacja polega na podziale przestrzeni adresów na segmenty, odpowiadające logicznym składowym programu, np. procedurom, danym, modułom itp.
Segmentacja ułatwia prace programisty przez możliwość korzystania z nadanych przez siebie nazw segmentów.
Adres programu jest para (s, a), gdzie a jest adresem, zaś s - numerem segmentu.
Segmentacja ze stronicowaniem
Każdy segment składa się z kilku stron i posiada tablice stron
6. Strategie przydziału pamięci
Strategie rozmieszczania dla systemów bez stronicowania
Obszar pamięci w stanie równowagi (wolny obszar jest porównywalny z zajętym)
Lista dziur to wykaz adresów i rozmiarów wszystkich nie zajętych obszarów pamięci.
x1, x2, ... , xn - rozmiary dziur
Najlepsze dopasowanie
Dziury są porządkowane rosnąco względem ich rozmiaru:
x1 x2 ... xn
Chcąc umieścić w pamięci obszar o rozmiarze s przeglądamy listę dziur i znajdujemy najmniejsze i takie, że: s xi
Najgorsze dopasowanie
Dziury są porządkowane malejąco względem ich rozmiaru:
x1 ≥x2 ≥... ≥xn
Chcąc umieścić w pamięci obszar o rozmiarze s wstawiamy go w dziurę x1, zaś pozostały obszar staje się nowa dziura.
Pierwsze dopasowanie
Dziury są porządkowane rosnąco względem ich adresów.
Chcąc umieścić w pamięci obszar o rozmiarze s przeglądamy listę dziur i znajdujemy najmniejsze i takie, że: s xi
Fragmentacja pamięci nazywamy sytuacje, kiedy wolna pamięć jest podzielona na tak małe dziury, że nie można w nich pomieścić nowych segmentów.
Upakowywaniem pamięci nazywamy mechanizm, który chroni pamięć przed fragmentacja, przenosząc zajęte obszary tak, aby zamiast wielu małych dziur powstała jedna duża.
Strategie rozmieszczania dla systemów ze stronicowaniem
W systemach ze stronicowaniem strategia rozmieszczania polega na wyborze wymaganej ilości wolnych ramek.
Problem fragmentacji pamięci nie istnieje, ze względu na stały rozmiar ramek.
Fragmentacja wewnętrzna polega na utracie części ostatniej przydzielanej strony w przypadku, gdy proces nie wymaga pamięci o rozmiarze będącym dokładnie wielokrotnością strony.
Strategie rozmieszczania dla systemów ze stronicowaniem
W systemach ze stronicowaniem strategia rozmieszczania polega na wyborze wymaganej ilości wolnych ramek.
Problem fragmentacji pamięci nie istnieje, ze względu na stały rozmiar ramek.
Fragmentacja wewnętrzna polega na utracie części ostatniej przydzielanej strony w przypadku, gdy proces nie wymaga pamięci o rozmiarze będącym dokładnie wielokrotnością strony.
Strategie wymiany dla systemów ze stronicowaniem
Strategie wymiany dla systemów bez stronicowania
W tym przypadku strategie są takie same jak dla systemów ze stronicowaniem. W związku z różnymi rozmiarami obszarów wymienianych, algorytm musi dodatkowo wybierać, na podstawie rozmiaru obszaru, który ma być załadowany, obszar przenoszony do pamięci pomocniczej.
Przykład algorytmu:
U = rozmiar wstawianego segmentu
1. Wymień segment o rozmiarze R, takim, że R+D ≥ U, gdzie D jest rozmiarem dziury sąsiadującej z segmentem. Jeżeli istnieje takich kilka segmentów, wybierz jeden z nich np. wg strategii najdawniej używanego segmentu.
2. Jeżeli nie ma takiego segmentu, wymień kilka sąsiadujących segmentów, takich,
że: R1+D1+R2+D2+...+RN+DN≥ U
Strategie pobierania z pamięci pomocniczej
Pobieranie na żądanie (demand): aktywowane gdy brakuje bloku segmentu).
Pobieranie przewidujące (anticipatory): aktywowane z wyprzedzeniem, podstawie:
znajomości konstrukcji programu
Wnioskowania z dotychczasowego przebiegu programu
7. Model zbioru roboczego
Zasada lokalności
Występujące w programie odniesienia do pamięci wykazują tendencje do grupowania się w małych obszarach przestrzeni adresów, a do zmiany tych obszarów dochodzi tylko okresowo.
Model zbioru roboczego określa zachowanie się procesów ze stronicowaniem w środowisku wieloprogramowym, z uwzględnieniem wzajemnego wpływu procesów.
Stopień wieloprogramowości = liczba procesów obecnych w pamięci
Szamotanie jest sytuacja, kiedy następuje przepełnienie kanału pamięci pomocniczej, spowodowane ciągłym napływem zadań pobrania strony.
Szamotanie powoduje:
_ blokowanie większości procesów
_ spadek wykorzystania procesora.
Zbiór roboczy to minimalna liczba stron procesu umieszczonych w pamięci głównej, która zapewnia efektywne wykorzystanie procesora przez proces.
Reguły uwzględniające istnienie zbioru roboczego
1. Wykonuj proces tylko wtedy, gdy cały jego zbiór roboczy znajduje się w pamięci głównej.
2. Nie usuwaj z pamięci głównej stron należących do zbioru roboczego jakiegoś procesu.
Identyfikacja zbioru roboczego
Zbiór roboczy procesu w chwili t
r(t,h) = {zbiór stron procesu, do których wystąpiło ostatnie h odwołań}
Parametr h powinien być dobrany optymalnie, tzn. jest to najmniejsza wartość, której zwiększanie nie wpływa znacząco na wielkość zbioru roboczego.
Zarządzanie plikami
Plik - zbiór danych, które użytkownik lub system operacyjny traktuje jako pewna całość.
Jest logiczna jednostka magazynowania informacji w pamięci pomocniczej.
• Pliki są najczęściej przechowywane w pamięci nieulotnej
• System plików - zbiór mechanizmów systemu operacyjnego pozwalających na organizowanie danych w plikach i korzystanie z nich w sposób wygodny dla użytkownika
• Podstawowe zadania systemu plików:
- tworzenie i usuwanie plików
- umożliwienie dostępu do plików w celu czytania i pisania
- zarządzanie przestrzenia pamięci pomocniczej
- umożliwianie odwoływania się do plików za pomocą symbolicznych nazw
- ochrona plików przed skutkami uszkodzenia systemu
- umożliwienie współdzielenia plików
- ochrona plików przed nieupoważnionym dostępem
Pliki i działania na plikach
• Korzystanie z symbolicznej nazwy przy odwołaniu do pliku jest możliwe dzięki zastosowaniu struktury zwanej katalogiem plików.
• Typowe cechy pojedynczego pliku przechowywane w strukturze katalogowej:
- nazwa pliku
- położenie
- rozmiar
- typ pliku
- atrybuty ochrony
- czas utworzenia, modyfikacji, użycia z ew. identyfikatorem użytkownika lub procesu
• Podstawowe operacje plikowe:
- tworzenie pliku:
• wydzielenie fizycznego miejsca dla pliku
• utworzenie wpisu w katalogu
- czytanie i pisanie do pliku:
• znalezienie wpisu o pliku w katalogu
• wprowadzenie danych z pliku do bufora w pamięci
(odczyt) lub z pamięci do pliku (zapis)
• aktualizacja bieżącego położenia w pliku (kursora)
- usuwanie pliku:
• znalezienie wpisu o pliku w katalogu
• zwolnienie miejsca w pamięci pomocniczej zajmowanej przez plik
• usuniecie wpisu z katalogu
- inne operacje: dołączanie (appending) i skracanie (truncating), przeszukiwanie (seek), zmiana nazwy (renaming)
• W celu uniknięcia ciągłego przeszukiwania katalogu wykorzystuje się uchwyt pliku uzyskiwany w wyniku operacji otwarcia pliku
Struktury katalogowe
• Struktura jednopoziomowa
• Struktura dwupoziomowa
• Struktura wielopoziomowa (drzewiasta)
• Implementacja katalogu bieżącego użytkownika pozwala na unikniecie każdorazowego podawania pełnej nazwy pliku.
Dostęp do plików z tego katalogu uzyskuje się po podaniu samej nazwy pliku - bez ścieżki prowadzącej do tego katalogu
Struktury katalogowe
• Grafy acykliczne pozwalają na umieszczenie odwołania do jednego pliku lub katalogu w dwóch lub więcej katalogach (współdzielenie pliku/katalogu)
• Dowiązanie polega na umieszczeniu w katalogu wskaźnika do pozycji w katalogu macierzystym dzielonego pliku lub podkatalogu
• Dowiązanie trwałe prowadzi bezpośrednio do pliku
• Dowiązanie symboliczne zawiera nazwę dzielonego pliku lub katalogu
• Problemy z dowiązaniami przy usuwaniu
Ochrona plików
• Ochrona plików jest mechanizmem implementowanym w systemach przeznaczonych dla wielu użytkowników
• Prawa dostępu (przywileje) określają, kto i co może z danym plikiem zrobić.
• Typowe prawa dostępu: czytanie, pisanie, usuwanie, wykonywanie
• Sposoby przydziału praw:
- maska ochrony pliku:
• Użytkownicy są podzieleni na trzy klasy:
• właściciel (owner)
• grupa (group)
• pozostali (world)
• Każdej z klas oddzielnie są przydzielane prawa dostępu
• Właściciel pliku ma narzędzia pozwalające na zmianę maski należących do niego plików
• przykład (w UNIXie: -rwxr-xr--)
• Listy kontroli dostępu
- dołączane do pliku lub katalogu
- zawierają informacje o użytkownikach i ich prawach dostępu do obiektu
Zarządzenie wolnymi obszarami pamięci • System plików musi na bieżąco aktualizować informacje o wolnych obszarach (blokach) pamięci pomocniczej
• Sposoby implementacji listy wolnych obszarów:
- mapa bitowa: każdy bit reprezentuje zajętość odpowiadającego mu bloku pamięci pomocniczej:
001001111111100010101110100000...
- łańcuch wolnych bloków: w każdym wolnym bloku przechowywany jest wskaźnik do następnego wolnego bloku
- zgrupowany łańcuch wolnych bloków: pierwszy blok grupy wolnych bloków zawiera wskaźniki do tych bloków oraz wskaźnik na kolejny blok ze wskaźnikami
- zliczanie polega na przechowywaniu wskaźników do pierwszego wolnego bloku i ilości wolnych bloków następujących bezpośrednio po nim pomocniczej
Obsługa wejścia/wyjścia
• Cele podsystemu wejścia/wyjścia:
- udostępnienie jednakowych metod dostępu do urządzeń
- niezależność programów od urządzenia we/wy
- zwiększenie wydajności
• Podstawowe właściwości urządzeń:
- jednostki przesyłania danych (bajty, bloki)
- sposób dostępu (sekwencyjny, swobodny)
- organizacja przesyłu (synchroniczna lub asynchroniczna)
- współdzielenie (dostęp wyłączny lub wspólny)
- prędkość przesyłu danych
- operacje uprzywilejowane (odczyt, zapis, inne)
- błędy przy wykorzystaniu urządzeń
- kody znaków
• Niskopoziomowa obsługa urządzeń:
- przerwania
- DMA
- odpytywanie
• Programowy sterownik urządzenia udostępnia innym modułom s.o. standardowy interfejs do komunikacji z urządzeniem
• Opis urządzenia zawiera jego parametry wykorzystywane przez funkcje s.o. (identyfikator, możliwe operacje, tablice konwersji znaków, stan urządzenia itp.)
Struktura obsługi WE/WY
Niezależność obsługi
• Programy użytkowe wykorzystują procedury dostępu nie do rzeczywistych urządzeń, lecz tzw. strumieni (urządzeń wirtualnych), bez uwzględniania fizycznych charakterystyk konkretnych urządzeń.
• Korzystanie ze strumienia:
1. Otwarcie strumienia (wpis w tablicy strumieni wykorzystywanych przez proces)
2. Wykonanie operacji we/wy
3. Zamkniecie strumienia
Procedura wejścia/wyjścia
• Proces użytkownika żąda dostępu do urządzenia wywołując systemowa procedurę we/wy o następujących parametrach:
- identyfikator strumienia
- rodzaj operacji (odczyt, zapis, formatowanie)
- ilość przesyłanych danych
- adres obszaru danych
- znacznik zakończenia
Procesy obsługi urządzeń
• Proces obsługi urządzenia odpowiada za realizacje zamówień z kolejki
Implementacja podsystemu we/wy
• Niektóre systemy dopuszczają dwa rodzaje wywołania systemowej obsługi we/wy:
- z blokowaniem (proces czeka na zakończenie operacji)
- bez blokowania (proces kontynuuje działanie, zakończenie operacji jest sygnalizowane za pomocą np. semafora)
• Systemy UNIX-owe traktują urządzenia jak pliki. Nazwy urządzeń są pamiętane w przestrzeni nazw systemu plików.
• Buforowanie jest mechanizmem zwiększających wydajność przesyłania danych z i do urządzeń. Polega na wykonywaniu pewnych operacji we/wy z wyprzedzeniem, tzn. przed nadejściem zamówienia
- Dane wejściowe są pobierane przez system i umieszczane w buforze wejściowym, skąd mogą być pobrane przez proces użytkownika.
Faktyczny dostęp do urządzenia jest realizowany w momencie opróżnienia bufora.
- Dane wyjściowe umieszczane są w buforze wyjściowym, zaś system operacyjny wysyła je do urządzenia dopiero po zapełnieniu bufora.
• Podwójne buforowanie polega na istnieniu dwóch buforów, z których jeden jest zapełniany (odczytywany) przez proces użytkownika, podczas gdy system operacyjny zapisuje (odczytuje) zawartość drugiego bufora.
Obsługa urządzeń niepodzielnych
• Urządzenia podzielne to takie, do których dostęp może mieć jednocześnie wiele procesów, zaś kolejka zamówień jest realizowana na bieżąco, zgodnie z napływem zgłoszeń.
• Urządzenia niepodzielne nie dopuszczają przeplatania przesyłanych danych. Jeden proces ma do takiego urządzenia wyłączny dostęp od chwili otwarcia do zamknięcia strumienia. Gdy urządzenie niepodzielne jest zajęte przez proces, zamówienia od innych procesów nie są realizowane, zaś procesy te musza oczekiwać na zwolnienie urządzenia.
• Mechanizm spoolingu ogranicza skutki blokowania procesów korzystających z urządzenia niepodzielnego
- Dane nie są przesyłane bezpośrednio do urządzenia niepodzielnego, lecz do urządzenia pośredniego (np. dysku).
Specjalny proces zwany spoolerem obsługuje dane przechowywane na urządzeniu pośrednim i wysyła je do urządzenia docelowego wtedy, kiedy jest ono wolne.
Ochrona sprzętowa w procesorach x86
• Możliwość powiązania kodu programu z różnymi przywilejami
• Poziomy (rings) są ponumerowane 0-3 (0 - poziom bez zabezpieczeń)
• Ograniczeniu mogą podlegać:
• dostęp do danych
• zestaw instrukcji procesora
• przekazanie kontroli modułowi na innym poziomie
• Przekroczenie przywilejów powoduje błąd ochrony
• Architektura Windows NT wykorzystuje wszystkie 4 poziomy, zaś Windows 9x jedynie Ring 0 i Ring 3
Mechanizmy ochrony
Cele ochrony:
_ ochrona systemu operacyjnego i procesów przed błędami innych procesów;
_ ochrona przed nieupoważnionym dostępem do informacji lub programów.
Podstawowym sposobem ochrony przed nieupoważnionym dostępem jest konieczność identyfikacji użytkownika z podaniem hasła.
Domena ochrony
Każdy proces wykonuje się w domenie ochrony (dziedzinie), określającej przywileje, z których proces może skorzystać. Zmiana przywilejów wiąże się ze zmiana domeny.
Model macierzy dostępów
Macierz dostępu przechowuje informacje o możliwościach procesów wykonywanych w różnych domenach.
Przy dostępie do obiektu następuje odwołanie do sterownika, który odpowiada za przyznanie odpowiednich przywilejów. Sterownikiem może być:
_ dla plików - system plików
_ dla urządzenia - procedura obsługi urządzenia
_ dla segmentu pamięci - mechanizm segmentacji
Implementacja macierzy dostępów
_ Tablica globalna - przechowuje informacje typu (obiekt, domena, zbiór praw)
_ Wykazy dostępów do danego obiektu - przechowują informacje typu (domena, zbiór praw)
_ Wykazy możliwości domeny - lista obiektów i operacji, które można na nich wykonywać
_ Mechanizm zamka z kluczem - każdy obiekt ma wykaz wzorców zwanych zamkami, zaś domena - wykaz wzorców zwanych kluczami.
Dynamiczna zmiana przywilejów
Przełączanie procesu od jednej do drugiej domeny
Proces może się przełączyć z domeny Di do Dj, gdy istnieje prawo dostępu Przełącz z domeny Di do domeny Dj.
Dynamiczna zmiany macierzy dostępów
I. Prawo kopiowania praw dostępu
Specjalny status niektórych praw pozwala na ich:
_ kopiowanie,
_ przenoszenie,
_ ograniczone kopiowanie w obrębie danego obiektu (kolumny macierzy dostępów).
II. Prawo właściciela
Prawo Właściciel w komórce (i,j) macierzy dostępów umożliwia dodawanie i usuwanie praw dostępu w każdej komórce kolumny j przez proces wykonujący się w domenie Di.
III. Prawo kontroli
Prawo Kontroluj w komórce (i,j) macierzy dostępów umożliwia dodawanie i usuwanie praw dostępu w każdej komórce wiersza j przez proces wykonujący się w domenie Di. Prawo to można stosować wyłącznie do obiektów będących domenami.
Transakcje niepodzielne
• Transakcja - zbiór instrukcji, które wykonują logicznie spójna funkcje
• Przy realizacji transakcji konieczne jest zachowanie jej niepodzielności mimo awarii lub błędów - transakcja wykonuje
się w całości albo wcale
• Stany transakcji:
• Sposoby realizacji niepodzielności transakcji:
• Zapisywanie wszelkich zmian w rejestrze (log)
• Tworzenie punktów kontrolnych (checkpoints)
• Przykład zapewnienia odpowiedniego porządku w przypadku współbieżnego wykonywania transakcji za pomocą znaczników czasu operacji i transakcji:
Czytanie:
Odrzuć, gdy wartość została zmieniona w czasie tej transakcji przez późniejszą transakcje (potrzebna wartość już nie istnieje)
Pisanie:
Odrzuć, gdy:
1. w czasie transakcji czytano wartość w późniejszej transakcji (wartość już nie jest potrzebna)
2. w czasie transakcji zapisano nowa wartość w późniejszej transakcji (nie można zapisać wartości nieaktualnej)
Niezawodność systemu
• Niezawodność s.o. nazywamy poziom, do którego działanie systemu - nawet w nieoczekiwanych i nieprzyjaznych warunkach
- jest zgodne ze specyfikacja jego usług dla użytkowników
• System operacyjny jest poprawny, jeżeli w określonym środowisku zachowuje się w oczekiwany sposób.
• Błąd s.o. - odstępstwo od określonego działania
• Wada - przyczyna błędu
• Uszkodzenie - zniszczenie informacji wewnątrz systemu komputerowego, konsekwencja błędu
• Przy konstrukcji s.o. należy zwrócić uwagę na następujące kwestie:
- unikanie wad
- wykrywanie błędów
- usuwanie wad
- naprawianie uszkodzę
Wady i ich unikanie
• Wady spowodowane przez operatora i użytkownika
- trudno stworzyć system całkowicie odporny na niepoprawne użytkowanie
- zmniejszenie ilości tych wad można spowodować za pomocą przeszkolenia użytkowników lub utworzenie odpowiednich interfejsów użytkownika
• Wady sprzętu
- wady sprzętu są maskowane przez odpowiednie oprogramowanie
- wykrywanie błędów za pomocą nadmiarowych informacji, np. bity parzystości, sumy kontrolne; w razie wystąpienia błędu zazwyczaj operacja jest powtarzana
- mechanizm kodów wykrywających i usuwających błędy pozwala usunąć niektóre skutki niepoprawnego przesyłania danych
- technika wybierania większościowego polega na przesyłaniu kilku kopii tych samych danych; w razie różnic, wybierane są te dane, których jest większość
• Wady oprogramowania
- podstawowym sposobem utworzenia oprogramowania lepszej jakości jest przyjęcie odpowiedniego sposobu postępowania w procesie projektowym
Unikanie wad oprogramowania
• Tradycyjny kaskadowy model cyklu życia oprogramowania
• Koszt poprawiania błędów rośnie wraz z postępem prac
• Etapy cyklu życia realizuje się w oparciu o wybrana metodologie (np. podejście strukturalne)
• Poprawność fazy implementacji zależy od wyboru odpowiednich narzędzi programistycznych
• przy konstrukcji s.o. dąży się obecnie do tego, aby największa jego część była utworzona za pomocą języka wysokiego poziomu
• Problem dowodzenia poprawności s.o.
• Usuwanie wad za pomocą testowania
Programowanie współbieżne
Podstawowe pojęcia dotyczące procesów (przypomnienie):
_ Proces jest programem w trakcie wykonywania
_ Proces może być skończony lub nieskończony
_ Dwa procesy są współbieżne, jeżeli jeden z nich rozpoczyna się przed zakończeniem drugiego
_ Podział czasu procesora umożliwia współbieżność w przypadku, gdy procesorów jest mniej ni_ procesów
Rodzaje uzależnienia procesów współbieżnych
I. Współbieżne wykonywanie niezależnych programów użytkowych (współzawodnictwo, brak współpracy).
II. Wykonywanie procesów utworzonych w obrębie jednego programu (tzw. programu współbieżnego)
Program współbieżny opisuje zachowanie się zbioru procesów współbieżnych.
Typy programów współbieżnych
I. Przetwarzanie potokowe
Każdy proces pobiera dane z jednego źródła, przetwarza je i wysyła do jednego odbiorcy.
II. Przetwarzanie potokowe wielowymiarowe
Proces pobiera dane z kilku źródeł i wysyła je do kilku odbiorców.
III. Zbiór takich samych procesów
Identyczne procesy działają współbieżnie.
IV. Klient-serwer
Proces klienta wysyła żądania do procesu obsługującego (serwera) i oczekuje na jego reakcje.
1. Wzajemne wykluczanie
Zasób dzielony jest wspólnym obiektem, z którego może korzystać w sposób wyłączny wiele procesów
Sekcja krytyczna to fragment procesu, w którym korzysta on z obiektu dzielonego.
Ponieważ w danej chwili z zasobu dzielonego może korzystać tylko jeden proces, wykonując swoja sekcje krytyczna uniemożliwia on wykonanie sekcji krytycznych innym procesom.
Problem wzajemnego wykluczania
Zsynchronizować N procesów, z których każdy w nieskończonej pętli na przemian zajmuje się własnymi sprawami i wykonuje sekcje krytyczna, w taki sposób, aby wykonanie sekcji krytycznych jakichkolwiek dwóch lub więcej procesów nie pokrywało się w czasie.
W celu rozwiązania problemu wzajemnego wykluczania należy do treści każdego procesu wprowadzić dodatkowe instrukcje poprzedzające sekcje krytyczna (protokół wstępny) i następujące bezpośrednio po sekcji krytycznej (protokół końcowy).
Wymagania umożliwiające realizacje wzajemnego wykluczania _ Żaden proces nie może wykonywać swej sekcji krytycznej nieskończenie długo _ Protokół wstępny i końcowy musza być wykonane w skończonym czasie _ Poza sekcja krytyczna zachowanie procesu nie może być ograniczone _ Procesy mogą się wykonywać z różnymi dowolnie wybranymi prędkościami.
2. Zakleszczenie i zagłodzenie
Zbiór procesów znajduje się w stanie zakleszczenia, jeżeli każdy z tych procesów jest wstrzymany w oczekiwaniu na zdarzenie, które może być spowodowane tylko przez jakiś inny proces z tego zbioru.
Proces jest w stanie zagłodzenia, jeśli nie zostaje wznowiony mimo, że zdarzenie na które czeka występuje dowolną ilość razy, gdy za każdym razem jest wybierany inny czekający proces.
3. Klasyczne problemy współbieżności
Problem producenta i konsumenta porcje informacji, a następnie przekazuje ja do skonsumowania, i konsumenta, który cyklicznie pobiera porcje i konsumuje ja. Jeśli w danej chwili producent nie może pozbyć się wyprodukowanej porcji, musi czekać. Podobnie, jeśli konsument nie może pobrać porcji, także musi czekać. Porcje powinny być konsumowane w kolejności wyprodukowania. Miedzy producentem a konsumentem znajduje się N-elementowy bufor. Producent wstawia porcje do niepełnego bufora, a konsument pobiera ja z niepustego bufora.
Problem czytelników i pisarzy
Należy zsynchronizować dwie grupy cyklicznych procesów konkurujących o dostęp do wspólnej czytelni. Proces czytelnik co jakiś czas odczytuje informacje zgromadzona w czytelni i może to robić razem z innymi czytelnikami. Proces pisarz co jakiś czas zapisuje nowa informacje i musi wówczas przebywać sam w czytelni.
Zakłada się, że operacje czytania i pisania nie trwają nieskończenie długo.
Mechanizmy niskopoziomowe (sprzętowe)
• Realizacja wzajemnego wykluczania za pomocą blokowania przerwań:
1. Przed wejściem do sekcji krytycznej proces wywołuje odpowiednie przerwanie.
2. Procedura obsługi tego przerwania jest częścią systemu operacyjnego:
- zablokowanie (zamaskowanie) przerwania
- wykonanie sekcji krytycznej
- odblokowanie przerwania
• Specjalne instrukcje procesora:
- TEST&SET(X,R): X<-R; R<-0
- SWAP(X,R): tmp<-X; X<-R; R<-tmp
- Realizacja wzajemnego wykluczania
4. Semafory
Semafory były pierwszym mechanizmem synchronizacyjnym stosowanym w językach wysokiego poziomu (Dijkstra 1968 r.).
Istnieje kilka rodzajów semaforów, z których najważniejsze to semafor ogólny i binarny.
Definicja klasyczna
Semafor ogólny S jest zmienna całkowita z dwoma wyróżnionymi operacjami:
_ Podniesienie semafora V(S):
S:=S+1
_ Opuszczenie semafora P(S):
Czekaj, a_ S>0; S:=S-1.
Zakłada się, że podniesienie i opuszczenie semafora są operacjami niepodzielnymi.
Aby proces czekający na opuszczenie semafora mógł być wznowiony, jakiś inny proces musi mieć możliwość wykonania operacji podniesienia. Operacja opuszczania (o której w definicji klasycznej zakłada się, że jest niepodzielna !) musi być przerwana w trakcie sprawdzania warunku S>0. Podczas tej przerwy jakiś inny proces może rozpocząć opuszczanie semafora i ta operacja tak(e musi być przerwana. W rezultacie może istnieć wiele rozpoczętych, a nie zakończonych operacji opuszczania. W chwili, gdy jakiś proces zwiększy S, tylko jedna z nich biedzie mogła wykonać się do końca. W definicji klasycznej przyjmuje się wiec, (e operacja opuszczenia semafora jest niepodzielna tylko wtedy, gdy sprawdzany w niej warunek jest spełniony.
Wprowadzimy inna definicje operacji opuszczenia i podniesienia semafora, która zapewnia wznowienie jednego z procesów czekających na podniesienie, w chwili, gdy ono nastąpi.
Praktyczna definicja operacji na semaforze ogólnym
_ Opuszczenie semafora:
Jeśli S>0, to S:=S-1, w przeciwnym razie wstrzymaj działanie procesu wykonującego te operacje;
_ Podniesienie semafora:
Jeśli są procesy wstrzymane w wyniku wykonania operacji opuszczania semafora S, to wznów jeden z nich, w przeciwnym razie S:=S+1
Należy założyć, że sposób wyboru wznawianego procesu nie spowoduje zagłodzenia żadnego z czekających procesów.
Definicja klasyczna
Semafor binarny jest zmienna przyjmująca wartości 0 lub 1 z dwoma wyróżnionymi operacjami:
_ Podniesienie semafora VB(S): S:=1
_ Opuszczenie semafora PB(S): Czekaj, a_ S=1; S:=S-1.
Zakłada się, że podniesienie i opuszczenie semafora są operacjami niepodzielnymi.
Praktyczna definicja operacji na semaforze binarnym
_ Opuszczenie semafora binarnego:
Jeśli S=1, to S:=0, w przeciwnym razie wstrzymaj działanie procesu wykonującego te operacje
_ Podniesienie semafora binarnego:
Jeśli są procesy wstrzymane w wyniku wykonania operacji opuszczania semafora S, to wznów jeden z nich, w przeciwnym razie S:=1.
Implementacja semaforów
Z każdym semaforem należy skojarzyć kolejkę semafora, do której wstawiane będą procesy oczekujące na jego podniesienie:
procedure P(S);
begin
if s<>0 then s:= s-1
else
dodaj proces do kolejki semafora i zawieś jego wykonywanie
end;
procedure V(S);
begin
if kolejka pusta then s:=s+1
else
usuń jakiś proces z kolejki semafora i wznów jego wykonywanie
end;
Kolejka może być zorganizowana wg schematu FIFO, czyli zgodnie z napływem zgłoszeń lub wg priorytetów procesów. W niektórych systemach możliwy jest wybór organizacji kolejki na etapie definiowania semafora.
Ponieważ operacje semaforowe mogą zmienić stan procesu (zawiesić lub wznowić) konieczne jest po ich wykonaniu natychmiastowe wywołanie procedury dyspozytora, która umożliwi faktyczna realizacje zmiany stanu i - przy zawieszeniu - wznowi inny proces.
Niepodzielność operacji podnoszenia i opuszczania semafora można zrealizować za pomocą:
_ blokowania przerwań
_ operacji specjalnej procesora na specjalnie wydzielonej komórce pamięci
(TEST&SET, SWAP).
Regiony krytyczne
• Podczas wykonywania instrukcji wchodzących w skład regionu krytycznego, żaden inny proces nie ma dostępu do zmiennej związanej z tym regionem
5. Monitory
Przy posługiwaniu się semaforami łatwo popełnić błędy, np. odwołując się do zasobu dzielonego bez umieszczenia sekcji krytycznej miedzy operacjami V(S) i P(S) lub nieodpowiednie umieszczenie tych operacji. W celu uniknięcia tych problemów po koniec lat 70-tych wprowadzono monitory (Hoare i Brinch Hansen).
Definicja
Monitor to zebrane w jednej konstrukcji programowej zmienne i funkcje działające na tych zmiennych. Część funkcji jest udostępniana na zewnątrz monitora i tylko z ich pomocą procesy mogą uzyskać dostęp do zmiennych ukrytych wewnątrz monitora. Wykonanie procedury monitora jest sekcja krytyczna wykonującego go procesu - w danej chwili tylko jeden spośród współbieżnie wykonujących się procesów może wykonywać procedurę monitora. Z poziomu monitora można wstrzymywać i wznawiać procesy za pomocą zmiennych typu condition. Na zmiennych tych można wykonywać dwie operacje:
_ wait(c) - wstrzymanie procesu wykonującego te operacje i wstawienie go na koniec kolejki związanej ze zmienna c, z jednoczesnym zwolnieniem monitora,
_ signal(c) - wznowienie pierwszego procesu wstrzymanego w kolejce związanej ze zmienna c (jeśli kolejka nie jest pusta). Jeśli operacja ta nie jest ostatnia instrukcja procedury monitorowej, to proces wykonujący te operacje jest wstrzymywany a/ do chwili, gdy wznowiony przezeń proces zwolni monitor.
Za pomocą funkcji logicznej empty(c) można sprawdzić, czy kolejka związana ze zmienna c jest pusta, czy nie.
6. Przekazywanie komunikatów
Przekazywanie komunikatów miedzy procesami realizowane jest za pomocą funkcji:
wyslij_komunikat(proces_odbiorczy, komunikat);
odbierz_komunikat(proces_wysyłajacy, bufor);
Istnieje możliwość wywołania w/w funkcji z tzw. blokowaniem lub bez:
_ Wysyłanie z blokowaniem - operacja wysyłająca czeka, aż proces odbierający przyjmie komunikat;
_ Odbieranie z blokowaniem - operacja odbierająca czeka na komunikat, który ma nadejść;
_ Wysyłanie bez blokowania - operacja wysyłająca umieszcza komunikat w kolejce komunikatów i pozwala kontynuować działanie;
_ Odbieranie bez blokowania - operacja odbierająca przyjmuje komunikat lub zwraca informacje o jego braku.
W niektórych implementacjach (szczególnie w systemach operacyjnych czasu rzeczywistego) można stosować ograniczone blokowanie przez określony okres czasu.
Systemy rozproszone
W systemie rozproszonym procesory nie dzielą pamięci ani zegara; każdy procesor ma własna pamięć lokalna. Procesory (stanowiska) komunikują się poprzez różne linie komunikacyjne.
Cele zastosowania systemów rozproszonych:
_ dzielenie zasobów (plików, danych, urządzeń);
_ przyspieszanie obliczeń;
_ niezawodność;
_ komunikacja, wymiana informacji.
1. Topologia systemów rozproszonych
Połączenie pełne („każdy z każdym”)
_ duży koszt połączenia _ szybka komunikacja _ wysoka niezawodność
Połączenie częściowe
Hierarchia
Gwiazda
Pierścień
Szyna wielodostępna
W zależności od geograficznego rozmieszczenia sieci dzielimy na:
_ sieci lokalne (LAN)
_ sieci globalne (WAN)
2. Komunikacja w systemach rozproszonych
Strategie wyboru trasy
Określają drogę, jaka będzie przesłany komunikat od jednego węzła do drugiego, jeżeli istnieje więcej niż jedna fizyczna scieżka, która może być wykorzystana do tego celu.
Rozróżnia się 3 rodzaje strategii:
_ trasa stała
_ trasa wirtualna (ustalana na czas jednej sesji)
_ trasa dynamiczna
Strategie połączeń
Określają sposób komunikacji miedzy dwoma procesami.
Najważniejsze z nich to:
_ komutowanie łączy - przydzielenie fizycznego połączenia na czas komunikacji; inne procesy nie mogą wówczas z niego skorzystać;
_ komutowanie komunikatów - każdy komunikat posiada dodatkowo informacje o odbiorcy i nadawcy;
_ komutowanie pakietów - polega na podziale komunikatów na stałej długości pakiety, które odbiorca składa w jedna całość.
Rywalizacja
W celu uniknięcia kolizji, gdy łącze jest zajęte (np. w sieci pierścieniowej lub szynie wielodostępnej) stosuje się kilka mechanizmów, a wśród nich:
_ wielodostęp do łącza sieci z badaniem stanu kanału - sprawdzanie zajętości łącza przed wysłaniem komunikatu; po wykryciu kolizji wysyłanie komunikatów zostaje przerwane i wznowione po upływie losowego czasu (Ethernet)
_ przekazywanie żetonu - specjalny komunikat zwany żetonem jest nieustannie przesyłany w systemie; stanowisko, do którego dotrze żeton może wysłać komunikat, po czym przekazuje żeton innym stanowiskom
_ przegródki na komunikaty - w systemie krążą specjalne przegródki na komunikaty; stanowisko, które otrzyma pusta przegródkę może wysłać komunikat; odbiorca sprawdza, czy otrzymana przegródka jest przeznaczona dla niego, jeżeli nie, przesyła ja dalej.
3. Systemy operacyjne
Ze względu na dostęp do zdalnych zasobów systemy dzielimy na:
_ sieciowe systemy operacyjne - użytkownicy są świadomi wielości maszyn i w celu uzyskania dostępu do zasobów rejestrują się zdalnie na odpowiednich maszynach lub przesyłają dane miedzy maszynami zdalnymi a własnymi
_ rozproszone systemy operacyjne - użytkownicy nie musza być świadomi wielości maszyn, zaś dostęp do zasobów zdalnych jest realizowany tak, jak dostęp lokalny.
W rozproszonych systemach operacyjnych przemieszczanie danych i procesów miedzy stanowiskami odbywa się pod nadzorem systemu operacyjnego.
Przemieszczanie danych
_ przesyłanie całego pliku
_ przesyłanie części pliku niezbędnej do prawidłowego działania
Przemieszczanie obliczeń
Zamiast przesyłania danych miedzy stanowiskami można prowadzić obliczenia na stanowiskach, gdzie te dane rezydują za pomocą następujących mechanizmów:
_ zdalne wywołanie procedur
_ przesyłanie komunikatów
Przemieszczanie procesów
Polega na tym, _e proces zainicjowany na jednym stanowisku jest faktycznie wykonywany na innym, w celu:
_ odciążenia stanowiska
_ przyspieszenia obliczeń za pomocą współbieżnego wykonywania procesów
_ wykorzystania zasobów innego stanowiska (sprzętu, oprogramowania).
Przemieszczanie procesów może być kontrolowane lub niejawne dla użytkownika.
Relacja uprzedniości zdarzeń
• W systemie rozproszonym nie zawsze jest możliwe określenie porządku, w jakim wystąpiły dwa zdarzenia (różne zegary i pamięć)
• Informacja o kolejności zdarzeń jest wykorzystywana do realizacji wzajemnego wykluczania, transakcji itp.
• Relacja uprzedniości zdarzeń:
Dany jest zbiór zdarzeń oraz relacja uprzedniości zdarzeń (ozn. →) zdefiniowana następująco:
• Jeśli A i B są zdarzeniami w tym samym procesie i A zostało wykonane przed B, to A→B.
• Jeśli A jest zdarzeniem wysłania komunikatu przez pewien proces i B jest zdarzeniem odebrania tego komunikatu przez inny proces to A→B.
• Jeśli A→B i B→C, to A→C.
Jeśli A i B nie są związane relacja →, to mówimy, że zdarzenia te wystąpiły równocześnie.
Usługi zdalne
• Usługa jest jednostka oprogramowania działająca na jednej lub wielu maszynach, pozwalająca korzystać z określonych funkcji nieznanemu uprzednio klientowi
• System obsługi (serwer) jest to oprogramowanie usługowe wykonywane na jednej maszynie
• Klientem nazywa się proces wywołujący usługę za pomocą zbioru operacji zwanym interfejsem klienta
• Usługa zdalna jest wywoływana przez klienta za pośrednictwem sieci na zdalnym serwerze. Wyniki jej działania są przekazywane przez siec z powrotem do klienta.
• Zdalne wywoływanie procedur (Remote Procedure Call - RPC) jest najczęściej spotykana metoda realizacji usługi zdalnej
• Klasyczne podejście: każda procedura ma na stałe przypisany, znany klientowi numer portu
• Dynamiczne wiązanie portu i klienta
Rozproszone systemy plików
• Zadaniem r.s.p. jest umożliwienie korzystania z plików, które są fizycznie rozmieszczone na równych stanowiskach
• R.s.p. może być częścią rozproszonego systemu operacyjnego lub oprogramowania służącego do komunikacji miedzy „zwykłymi” s.o. i systemami plików
• Idealny r.s.p. = system, który z poziomu użytkownika wygląda jak system scentralizowany
- brak konieczności świadomości wielości stanowisk
- niemożnosc odróżnienia plików zdalnych i lokalnych
- niezależność środowiska użytkownika od stanowiska, na którym pracuje
• Nazwy plików w r.s.p.
- przezroczystość położenia - ukrywanie miejsca przechowywania pliku w sieci
- niezależność położenia - brak konieczności zmiany nazwy, gdy plik zmienia miejsce przechowywania
- schematy nazewnicze:
_ z określeniem stanowiska przechowywania:
nazwa_stanowiska + nazwa_pliku
_ przyłączanie zdalnych katalogów do lokalnych systemów plików
_ globalna struktura nazw
• Korzystanie z plików zdalnych jest realizowane za pomocą zdalnego wywołania procedur (RPC) wraz z mechanizmami redukującymi ilość przesyłanych danych w sieci (np. przechowywanie podręczne części pliku)
Standard POSIX
• POSIX - Portable Operating System Interface for Computer Environment
• Zdefiniowany przez IEEE (Institute of Electrical and Electronic Engineers)
• Określa sprzęg miedzy systemem operacyjnym a światem zewnętrznym (aplikacje i użytkownicy)
• Dynamiczny rozwój w latach 90-tych
• Zalety:
- zgodność aplikacji na poziomie kodu źródłowego
- jednakowe środowisko użytkownika (shell, polecenia, biblioteki C)
- otwartość na różne zastosowania
1. Struktura warstwowa systemu UNIX
2. Jądro systemu
Jądro systemu operacyjnego obejmuje m.in.:
_ zarządzanie procesami
_ zarządzanie pamięcią
_ system plików
4.1. Zarządzanie procesami
4.1.1. Bloki kontrolne procesu
Struktura procesu jest wykorzystywana przy wysyłaniu lub pobieraniu (wymianie) procesu z pamięci pomocniczej i przechowuje m.in.
_ identyfikator procesu
_ priorytet
_ wskaźniki do innych bloków kontrolnych procesu
_ wskaźniki do procesu macierzystego, najmłodszego potomka
Struktura użytkownika jest stosowana gdy proces nie podlega wymianie.
Przechowuje kontekst procesu, gdy nie jest on wykonywany oraz inne informacje, np. identyfikatory użytkowników, bieżący katalog itp.
W chwili wywołania funkcji systemowej uruchamiany jest proces systemowy.
Korzysta on z odrębnego stosu, umieszczonego za struktura użytkownika (tzw. stos jądra).
4.1.2. Planowanie przydziału procesora
W systemie zastosowano kombinacje algorytmu priorytetowego z rotacyjnym.
Każdemu procesowi przypisywany jest priorytet (im większa liczba tym niższy priorytet).
Ważne procesy systemowe maja priorytety ujemne, zwykłe procesy użytkownika - dodatnie.
Im więcej proces zajmuje czasu procesora, tym niższy staje się jego priorytet.
Kwant czasu w algorytmie rotacyjnym jest zależny od implementacji (na ogół 0.1 sek).
Mechanizm upływu czasu umożliwia wywołanie przez algorytm rotacyjny co pewien czas procedur systemowych dokonujących przeliczenia priorytetów i zaplanowania przydziału procesora.
Brak jest wywłaszczania procesów. Jeden proces może zrzec się procesora na rzecz innego procesu.
Czekanie na wystąpienie zdarzenia jest realizowane za pomocą adresów struktur danych w jądrze związanych ze zdarzeniem. Proces zostaje uśpiony pod adresem danego zdarzenia. Gdy zdarzenie wystąpi, procedura systemowa wznawia wszystkie procesy czekające pod adresem zdarzenia.
Warunki wyścigu polegają na podnoszeniu priorytetu procesu w trakcie wykonywania sekcji krytycznej. Uniemożliwia to uśpienie procesu na zawsze, gdy w międzyczasie zdarzenie wystąpiło.
Planista UNIX-a jest przystosowany do procesów ograniczonych operacjami wejscia-wyjscia.
4.2. Zarządzanie pamięcią
4.2.1. Wymiana
Cechy wymiany:
_ usuwanie z pamięci niektórych procesów, gdy nie ma miejsca dla wszystkich
_ metoda wymiany - pierwsze dopasowanie
_ nie ma wysyłania do pamięci pomocniczej dzielonych segmentów rozkazów oraz odczytywania drugiej kopii takiego segmentu jeżeli w pamięci głównej jest już inny egzemplarz wczytywanego procesu
_ do pamięci pomocniczej zostaje wysłany proces bezczynny, przebywający długo w pamięci głównej lub dużych rozmiarów
_ zapobieganie szamotaniu polega na nie dopuszczaniu do wymiany procesu, jeżeli nie przebywał on w pamięci głównej przez pewien czas
4.2.2. Stronicowanie
Cechy stronicowania:
_ stronicowanie na żądanie
_ niewielki rozmiar stron (mała fragmentacja wewnętrzną)
_ mechanizm odzyskiwania stron minimalizuje konieczność wczytywania strony, gdy jest ona jeszcze w pamięci (ale np. jej ramka została oznaczona jako wolna)
_ zastępuje się strony najdawniej używane
_ demon stron cyklicznie sprawdza wszystkie ramki stron i ew. oznacza je jako wolne; jeżeli ilość wolnych ramek jest duża, demon nie jest aktywowany
_ jeżeli system stronicowania jest przeciążony, zastępuje się go wymiana całych procesów
4.3. System plików
Plik w systemie UNIX jest reprezentowany za pomocą struktury zwanej i-wezłem.
Oprócz podstawowych informacji (nazwa) przechowuje ona:
_ Identyfikatory użytkowników
_ Czas ostatniej modyfikacji i dostępu
_ Licznik dowiązań
_ Typ pliku (plik, katalog, dowiązanie, urządzenie)
_ Wskaźniki do 12 bloków z danymi pliku (bezpośrednie wskazanie)
_ Wskaźniki do bloku indeksów (jednokrotnie pośrednie wskazanie)
_ Wskaźniki do bloku ze wskaźnikami do bloków indeksów (dwukrotnie pośrednie)
_ Wskaźniki do bloku ze wskaźnikami do bloków ze wskaźnikami bloków indeksów (trzykrotnie pośrednie wskazanie)
Do małych plików (ok. 50 kB) można odwoływać się bezpośrednio.
Dwukrotnie pośrednie wskazanie wystarcza nawet dla plików o wielkości 2^32 kB.
Katalog jest reprezentowany jako i-wezeł z odpowiednio ustawionym polem określającym typ.
Odwzorowanie scieżki pliku podanej przez użytkownika na odpowiedni i-wezeł odbywa się następująco:
1. Określenie katalogu początkowego - jeżeli scieżka rozpoczyna się od „/” jest nim root, jeżeli nie - katalog bieżący procesu.
2. Sprawdzenie istnienia i możliwosci dostępu do katalogu początkowego.
3. Określenie nazwy pliku (do następnego znaku „/” lub końca ścieżki).
4. Szukanie nazwy pliku w katalogu początkowym.
5. Jeżeli scieżka zawiera jeszcze jakieś nazwy, to znaleziony plik musi być katalogiem. Wówczas ustalany jest on jako katalog początkowy i następuje powtórzenie czynności od p. 3.
6. Znaleziono odpowiedni i-wezeł.
W systemie UNIX użytkownik korzysta z ujednoliconego, logicznego systemu plików. Za pomocą mechanizmu montowania integruje się systemy plików (fizyczne) różne od podstawowego (tzw. korzeniowego, np. zaimplementowanego na dysku twardym). Tworzony jest odpowiedni i-wezeł, który służy do odwoływania się do zamontowanego systemu plików.
Mechanizmy komunikacji miedzy procesami w standardzie POSIX
• Komunikacja międzyprocesowa (IPC - interprocess communication)
Sygnały
• Przekazywane w formie przerwań programowych do procesów
• Informują o wystąpieniu zdarzenia, nie nadają się do przekazywania danych
• Używane przez jądro do obsługi sytuacji wyjątkowych (np. próba wykonania nielegalnych instrukcji)
• Obsługa sygnałów
- Podjecie działań określonych przez programistę (np. usuwanie plików roboczych)
- Ignorowanie sygnału
- Podjecie działań domyślnych - zwykle zakończenie procesu (dla SIGUSR ignorowanie, a SIGSTOP - zawieszenie procesu)
• Blokowanie sygnałów - wstrzymywanie przyjmowania (pozostawienie na później)
• Wysyłanie sygnałów do innych procesów
Definiowanie obsługi sygnału
• Metodę obsługi sygnału definiuje się za pomocą funkcji sigaction()
• Przykład 1: Przechwytywanie sygnału
Zestawy sygnałów
• Programista korzysta z funkcji sygnałowych zadeklarowanych w pliku <signal.h>
• Funkcje te przyjmują argumenty będące zestawami sygnałów (signal sets)
Potoki
• Potoki (pipes) umożliwiają jednokierunkowa, asynchroniczna komunikacje miedzy pokrewnymi procesami (macierzysty/potomny lub mającymi wspólnych przodków).
• Informacja jest przesyłana w postaci sekwencyjnego strumienia bajtów, którego interpretacja należy do procesów korzystających z potoku.
• Odczytanie informacji powoduje usuniecie jej z potoku.
• Jeżeli w potoku nie ma tyle informacji, ile chce odczytać proces-odbiorca, to jest on wstrzymywany.
• Przykład 1: Potoki i polecenia konsoli - połączenie standardowego wyjścia i wejścia
$ pr doc | lp
• Alternatywa (bez potoków):
$ pr doc > tmpfile
$ lp < tmpfile
$ rm tmpfile
Potoki nazwane
• Problemy ze zwykłymi potokami:
- współpraca tylko procesów pokrewnych
- nietrwałość - wymagają działania obu procesów
• Niedostatki te niwelują potoki nazwane (named pipes) inaczej zwane potokami FIFO
Przekazywanie komunikatów (message passing)
• Komunikat - sekwencja znaków lub bajtów
• Komunikaty są przekazywane miedzy procesami za pomocą kolejek komunikatów z możliwością wydzielenia podkanałów
Semafory
• Rozszerzenia w porównaniu z wcześniejszą definicją:
- Występuje dodatkowa operacja, umożliwiająca przechodzenie pod opuszczonym semaforem:
Z(S) = wstrzymaj działanie procesu, a_ S będzie równe zeru
(Wykonanie operacji Z nie zmienia wartości semafora)
- Operacje opuszczania i podnoszenia mają dodatkowy parametr umożliwiający zmianę wartości semafora nie o 1, ale o dowolna ilość jednostek. Dodatkowo występują one w postaci nieblokującej - jeżeli proces nie może natychmiast wykonać żądanej operacji, to rezygnuje z jej wykonania.
- Działania na wielu semaforach można grupować w operacje jednoczesna - jej zakończenie następuje wtedy, gdy wszystkie operacje składowe są wykonalne.
Pozostałe mechanizmy IPC
• Dzielone obszary pamięci - pozwalają dwóm albo więcej procesom korzystać wspólnie z segmentu pamięci.
• Gniazda - rozszerzenie mechanizmu przesyłania komunikatów na środowisko rozproszone (siec)
• Zdalne wywoływanie procedur
- wzajemne wykluczanie podczas realizacji procedur
- rozgłaszanie - jednoczesne wywołanie procedury zdalnej wykonywane przez wiele procesów obsługujących
Wyszukiwarka