Systemy Operacyjne (wykłady - semestr 1) - notatki.

Opracowane przez Ripiego(D-101, obecnie D-201), na podstawie książki „Podstawy systemów operacyjnych” A. Silberschatz, oraz informacji znalezionych w Internecie.

1) Wstęp do teorii Systemów Operacyjnych.

System Operacyjny - jest programem, który działa jako pośrednik między użytkownikiem komputera a sprzętem komputerowym. Głównym zadaniem systemu operacyjnego jest tworzenie środowiska, w którym użytkownik może wykonywać programy w wygodny i wydajny sposób.

Rodzaje systemów operacyjnych:

• Proste systemy wsadowe - zadania przekazywane do systemu za pomocą `kart perforowanych', prosty system planowania, pamięć, wykorzystywane w pierwszych komputerach.

• Wieloprogramowe systemy wsadowe - wieloprogramowanie zwiększa wykorzystanie procesora wskutek takiej organizacji zadań, aby procesor miał zawsze któreś z nich do wykonania. Idea: W tym samym czasie system operacyjny przechowuje w pamięci kilka zadań. Systemy te tworzyły środowisko w którym rozmaite zasoby systemowe były skutecznie użytkowane, lecz nie umożliwiały użytkownikowi interakcji z systemem komputerowym.

• Systemy z podziałem czasu - są rozszerzeniem systemów wieloprogramowych. Podział czasu (wielozadaniowość) polega na tym że procesor wykonuje wiele różnych zadań, przy czym przełączenia następują tak często, że użytkownicy mogą współdziałać z każdym programem podczas jego wykonywania. System ten umożliwia dialog użytkownika z systemem. Aby zagwarantować akceptowalny czas odpowiedzi (~1s) zaczęto stosować pamięć wirtualną - czyli technikę umożliwiającą wykonywanie zadania które nie musi znajdować się w całości w pamięci operacyjnej. Zaletą tej pamięci jest to iż umożliwia ona wykonywanie programów większych niż pamięć fizyczna. Pamięć logiczna jest to pamięć oglądana przez użytkownika, może być większa niż pamięć fizyczna - wprowadzono ją by uwolnić programistów od zajmowania się ograniczeniami pamięciowymi.

• Systemy operacyjne dla komputerów osobistych - w systemach tych nacisk kładziono nie na maksymalizacje wykorzystania procesora lecz na wygodę użytkowania i szybkość kontaktu z użytkownikiem. Przykładowymi systemami dla komputerów PC są: Microsoft Windows, OS/2 firmy IBM, Apple Mocintosh.

• Systemy równoległe - zwane również wieloprocesowymi, charakteryzują się tym iż istnieje pewna liczba procesorów które pozostają ze sobą w ścisłej komunikacji, dzieląc szynę komputera, zegar a czasami pamięć i urządzenia zewnętrzne. Trzy główne zalety systemów równoległych to: zwiększona przepustowość, ekonomia skali, zwiększona niezawodność (łagodna degradacja - zdolność do kontynuowania usług na poziomie proporcjonalnym do ilości sprawnego sprzętu, systemy tolerujące awarie.). Stosuje się dwóch modeli:

1. wieloprzetwarzania symetrycznego (SMP) - na każdym procesorze działa identyczna kopia systemu operacyjnego. Kopie te komunikują się ze sobą w zależności od potrzeb.

2. wieloprzetwarzania asymetrycznego - każdy procesor ma przypisane inne zadanie. Systemem takim zawiaduje główny procesor.

• Systemy rozproszone - połączone siecią. Ich funkcjonalność zależy od sieci z jakiej korzystają. Sieci lokalne (LAN) istnieją w obrębie pokoju, piętra lub budynku. Sieci rozległe (WAN) rozciągają się między budynkami, miastami, krajami. Systemy takie nie dzielą pamięci ani zegara - wyposażone są we własną pamięć lokalną.

• Systemy czasu rzeczywistego - wykorzystywane są tam, gdzie stawia się surowe wymagania na czas wykonania operacji lub przepływu danych. Rygorystyczny system czasu rzeczywistego gwarantuje terminowe wypełnianie krytycznych zadań. Wszelkiego rodzaju pamięć pomocnicza jest na ogół bardzo ograniczona lub nie występuje wcale. Łagodny system czasu rzeczywistego, krytyczne zadanie obsługi w czasie rzeczywistym otrzymuje pierwszeństwo nad innymi zadaniami i zachowuje je aż do momentu swojego zakończenia - nie gwarantuje on terminowego wypełniania zadań krytycznych.

2) Struktury systemów operacyjnych.

Usługi i funkcje systemu operacyjnego (terminologia):

Interpreter poleceń - jest interfejsem między użytkownikiem a systemem operacyjnym.

Wywołania systemowe - tworzą interfejs między wykonywanym programem a systemem operacyjnym.

Program rozruchowy - pierwszy program, który jest wykonywany po starcie systemu. Program ten musi wiedzieć jak załadować system operacyjny i rozpocząć jego działanie.

Przerwanie - jest to sposób sygnalizowania, wystąpienia jakiegoś zdarzenia. Przerwanie pochodzi od sprzętu lub oprogramowania.

Sektor - wielkość najmniejszej adresowalnej porcji dysku (512 B, i wielokrotności).

Wejście-wyjście synchroniczne - operacja przesyłania danych rozpoczyna się, kończy, po czym wraca do procesu użytkownika.

Wejście-wyjście asynchroniczne - polega na oddaniu sterowania do programu użytkownika bez czekania na zakończenie operacji. Operacja I/O może być wtedy kontynuowana wraz z innymi działaniami systemu.

Bezpośredni dostęp do pamięci operacyjnej (DMA) - po ustawieniu buforów wskaźników i liczników sterownik danego urządzenia przesyła bezpośrednio cały blok danych między własnym buforem a pamięcią - bez interwencji procesora.

Pamięć operacyjna - zwana również pamięcią o dostępie swobodnym (RAM), jest jednym wielkim obszarem pamięci dostępnym dla procesora bezpośrednio. Tak więc programy komputerowe muszą znajdować się w pamięci operacyjnej aby mogły być wykonywane.

Pamięć pomocnicza - rozszerza pamięć operacyjną. Trwale przechowuje duże ilości danych.

Pamięć podręczna (cashe) - jest to bufor pamięci stosowany do niwelowania różnic w szybkości CPU a pamięcią operacyjną.

Pamięć ulotna - traci zawartość po odłączeniu od niej zasilania.

Pamięć nieulotna - analogicznie, zachowuje zawartość po odłączeniu od niej zasilania.

3) Zarządzanie procesami

• Proces - wykonujący się program. W większości systemów operacyjnych jest jednostką pracy. Wykonywanie procesu musi odbywać się sekwencyjnie. W pojęciu procesu mieści się:

• Licznik rozkazów - zawiera on adres komórki pamięci zawierającej następny rozkaz do wykonania.

• Rejestr procesora - umieszczone wewnątrz procesora komórki pamięci, przechowujące tymczasowe wyniki obliczeń oraz adresy lokacji w pamięci operacyjnej.

• Stos procesu - przechowuje dane tymczasowe.

• Sekcja danych - zawiera zmienne globalne.

Stany procesu:

• Nowy - proces został utworzony;

• Aktywny - są wykonywane instrukcje;

• Czekający - proces czeka na wystąpienie jakiegoś zdarzenia;

• Gotowy - proces czeka na przydział procesora;

• Zakończony - proces zakończył działanie.

Tylko 1 proces może być aktywny w danym momencie.

• Blok kontrolny procesu (PCB) - zawiera następujące informacje o danym procesie:

• Stan procesu

• Licznik rozkazów

• Rejestr procesora

• Informacje o planowaniu przydziału procesora

• Informacje o zarządzaniu przydziałem procesora

• Informacje o zarządzaniu pamięcią

• Informacje do rozliczeń

• Informacje o stanie wejścia-wyjścia.

• Planowanie procesów

Wchodzące do systemu procesy trafiają do kolejki zadań. Gotowe do działania procesy, które

oczekują w pamięci operacyjnej, są trzymane na liście zwanej kolejką procesów gotowych. Kolejka ta ma zazwyczaj postać listy powiązanej.

Planista długoterminowy - (planista zadań) wybiera procesy z puli i ładuje je do pamięci w celu wykonania. Nadzoruje stopień wieloprogramowości - liczbę procesów w pamięci. Jeśli stopień wieloprogramowości jest stabilny to średnia liczba utworzonych procesów musi równać się średniej liczbie procesów usuwanych z systemu. Planista długoterminowy może być w niektórych systemach nieobecny lub mocno zredukowany. Planista ten powinien dobierać dobrą mieszankę procesów zawierającą zarówno procesy ograniczone przez I/O jak i przez dostęp do procesora.

• Proces ograniczony przez wejście-wyjście spędza większość czasu na wykonywaniu operacji wejścia-wyjścia, mniej zajmując się obliczeniami.

• Proces ograniczony przez procesor, jest analogią do I/O.

Planista krótkoterminowy - (przydziału procesora) wybiera jeden proces spośród procesów gotowych do wykonania i przydziela mu procesor.

Podstawową różnicą między obydwoma tymi (krótko/długoterminowymi) planistami jest częstość ich uaktywnień.

Planista średnioterminowy - usuwa procesy z pamięci, zmniejszając w ten sposób stopień wieloprogramowości. Usunięty proces można znów wprowadzić do pamięci, a jego wykonywanie kontynuować od miejsca w którym go przerwano. Nosi to nazwę wymiany (swapping). Proces jest wymieniany, czyli wysyłany z pamięci na zewnątrz a później sprowadzany do niej ponownie przez planistę średnioterminowego. Wymiana może być niezbędna do uzyskania lepszej mieszanki procesów.

• Tworzenie procesu - proces może tworzyć nowe procesy. Nowy proces tworzy się za pomocą funkcji systemowej fork.

Proces macierzysty (rodzicielski, przodek) - proces tworzący inny proces. Proces macierzysty może rozdzielać własne zasoby między procesy potomne albo powodować, że niektóre zasoby będą przez potomków użytkowane wspólnie. Proces macierzysty może kontynuować działanie współbieżnie ze swoimi potomkami lub oczekiwać na zakończenie działań niektórych lub wszystkich swoich procesów potomnych.

Proces potomny (potomek) - proces utworzony przez inny proces, zwany macierzystym. Przestrzeń adresowa procesu potomnego może być zagospodarowana na dwa sposoby:

• proces potomny staje się kopią procesu macierzystego;

• proces potomny otrzymuje nowy program.

• Kończenie procesu - proces kończy się wówczas, gdy wykona swoją ostatnią instrukcję i za pomocą wywołania funkcji exit poprosi system operacyjny, aby go usunął. Proces macierzysty może spowodować zakończenie procesu potomnego za pomocą odpowiedniej funkcji systemowej (np. abort).

Kończenie kaskadowe - jest to zjawisko gdy proces macierzysty kończy się, a w tej sytuacji system operacyjny nie pozwala potomkowi na dalsze działanie. W takich systemach zakończenie procesu (zwykłe lub wyjątkowe) wymusza zakończenie wszystkich jego potomków.

• Proces współpracujący - jest to taki proces który może wpływać na inne procesy w systemie lub inne procesy mogą oddziaływać na niego.

Proces niezależny - jest to proces na który nie mogą oddziaływać inne procesy, ale on sam też nie może na nie oddziaływać.

• Problem producenta-konsumenta - proces producent wytwarza informacje, które zużywa proces konsument. Aby umożliwić producentowi i konsumentowi działanie współbieżne, musimy dysponować buforem jednostek który będzie mógł być zapełniany przez producenta i opróżniany przez konsumenta. Podczas gdy producent tworzy pewną jednostkę, konsument może zużywać inną. Problem producenta-konsumenta z:

• Nieograniczonym buforem, nie ma żadnych praktycznych ograniczeń na rozmiar bufora. Może się zdarzać ze konsument musi czekać na nowe jednostki, ale producent może je produkować nieustannie.

• Ograniczonym buforem, zakłada się ze bufor ma ustaloną długość. W tym przypadku konsument musi czekać, jeśli bufor jest pusty, a producent musi czekać, jeśli bufor jest pełny.

• Wątki - wątek (proces lekki) jest podstawową jednostką wykorzystania procesora. W jego skład wchodzi:

• Identyfikator wątku

• Licznik rozkazów

• Zbiór rejestrów

• Stos

Wątki tego samego procesu korzystają ze wspólnego kodu i danych, mają jednak oddzielne stosy. Obecne systemy operacyjne umożliwiają występowanie wielu wątków sterujących w procesie.

Proces tradycyjny (ciężki) ma jeden wątek sterujący.

Korzyści programowania wielowątkowego:

• Zdolność do reagowania: Podział interakcyjnej aplikacji na wątki może umożliwiać działanie programu mimo zablokowania jego części lub wykonania przez niego długiej operacji co zwiększa gotowość do odpowiadania użytkownikowi.

• Dzielenie zasobów: umożliwia to aplikacji posiadanie kilku różnych wątków działania w tej samej przestrzeni adresowej.

• Ekonomika: Bardziej opłacalne jest tworzenie wątków i przełączanie się miedzy nimi, niż tworzenie kilku nowych procesów.

• Wykorzystanie architektury wieloprocesorowej: Każdy wątek może działać na oddzielnym procesorze.

Wątki użytkownika - są udostępniane powyżej jądra i realizowane przez bibliotekę wątków na poziomie użytkowym.

Wątki jądrowe - są udostępniane bezpośrednio przez system operacyjny.

• Komunikacja międzyprocesowa (IPC)

• Komunikacja bezpośrednia - każdy proces który chce się komunikować musi jawnie nazwać odbiorcę lub nadawcę uczestniczącego w wymianie informacji. Łącze dotyczy dokładnie dwu procesów, między każdą parą istnieje dokładnie jedno łącze.

Symetryczna - proces nadawczy jak i odbiorczy w celu utrzymania ze sobą łączności musza wzajemnie używać nazw.

Asymetryczna - tylko nadawca nazywa odbiorcę a od odbiorcy nie wymaga się znajomości nazwy nadawcy.

• Komunikacja pośrednia - komunikaty są nadawane i odbierane za pośrednictwem skrzynek pocztowych, nazywanych także portami. Łącze może dotyczyć wiecej niż dwóch procesów, a między każda parą może istnieć wiele łączy (skrzynek).

• Buforowanie - niezależnie od rodzaju komunikacji, komunikaty wymieniane przez kontaktujące się procesy przebywają czasowo w kolejce. Są trzy podstawowe metody implementacji takiej kolejki:

• Pojemność zerowa - łącze nie dopuszcza by czekał w nim jakikolwiek komunikat.

• Pojemność ograniczona - kolejka ma skończoną długość „n”, może w niej zatem pozostawać co najwyżej „n” komunikatów.

• Pojemność nieograniczona - kolejka ma potencjalnie nieskończoną długość, może w niej oczekiwać dowolna liczba komunikatów.

• Planowanie przydziału procesora

Elementami kolejek są na ogół bloki kontrolne procesów (PCB).

Planowanie wywłaszczające - polega na tym iż wykonywany obecnie proces, może być przerwany na skutek np. pojawienia się ważniejszego procesu.

Planowanie bez wywłaszczeń - proces który otrzyma procesor, zachowuje go dopóty, dopóki go nie odda go z powodu swojego zakończenia lub przejścia do stanu czekania.

Ekspedytor - (dyspozytor) jest modułem który faktycznie przekazuje procesor do dyspozycji procesu wybranego przez planistę krótkoterminowego.

Opóźnienie ekspedycji - jest to czas który ekspedytor zużywa na wstrzymanie jednego procesu i uaktywnienie innego.

Kryteria planowania przydziału procesora:

• Wykorzystanie procesora - powinno się ono mieścić w granicach od 40% do 90%.

• Przepustowość - jest to liczba procesów kończonych w jednostce czasu.

• Czas cyklu przetwarzania - jest to czas upływający między chwilą nadejścia procesu do systemu a chwilą zakończenia procesu.

• Czas oczekiwania - jest sumą okresów, w których proces czeka w kolejce procesów gotowych do działania.

• Czas odpowiedzi - czas upływający między wysłaniem żądania, a pojawieniem się pierwszej odpowiedzi, ale nie obejmuje czasu potrzebnego na wyprowadzenie tej odpowiedzi.

Algorytmy planowania przydziału procesora:

• Metoda FCFS (First-come first-served) - pierwszy zgłoszony, pierwszy obsłużony. Jest to algorytm niewywłaszczający, może wystąpić efekt konwoju gdy proces o długiej fazie procesora „blokuje inne procesy”. Proces przetrzymuje użycie procesora aż do momentu zakończenia pracy lub zamówienia operacji wejścia-wyjścia.

• Metoda SJF (Shortest-job-first) - najpierw najkrótsze zadanie. Może być wywłaszczająca lub nie wywłaszczająca. Metoda ta często wykorzystywana jest w planowaniu długoterminowym.

• Metoda priorytetowa - może być wywłaszczająca lub niewywłaszczająca. Każdemu procesowi przypisuje się priorytet, po czym przydziela się procesor temu procesowi, którego priorytet jest najwyższy. Procesy o równych priorytetach planuje się w porządku FCFS. Może wystąpić blokowanie nieskończone (głodzenia) - w mocno obciążonym systemie stały dopływ procesów o wyższych priorytetach może nigdy nie dopuścić niskopriorytetowego procesu do procesora. Rozwiązaniem tego problemu jest postarzanie procesów niskopriorytetowych, polegające na stopniowym podwyższaniu priorytetów procesów długo oczekujących w systemie.

• Metoda RR (round-robin) - rotacyjna, wywłaszczająca. Zaprojektowana specjalnie dla systemów z podziałem czasu. Jest on podobny do FCFS, z tym że w celu przełączania procesów dodano do niego wywłaszczenie. Ustala się małą jednostkę czasu zwaną kwantem czasu. Planista przydziału procesora przegląda kolejkę i każdemu procesowi przydziela odcinek czasu nie dłuższy niż jeden kwant. Jeśli faza procesu jest dłuższa niż kwant, to proces zostaje wywłaszczony.

• Metoda wielopoziomowego planowania kolejek - rozdziela kolejkę procesów gotowych na osobne kolejki, np. procesów pierwszoplanowych i drugiplanowych. Każda kolejka może mieć swój własny algorytm planowania. Występuje także planowanie między kolejkami, np. priorytetowe.

• Metoda wielopoziomowego planowania kolejek ze sprzężeniem zwrotnym - umożliwia przemieszczanie się procesów między kolejkami, ze względu na aktualne zapotrzebowanie lub długość faz..

• Metoda planowania wieloprocesorowego - można zastosować dzielenie obciążeń dzięki temu, że jest dostępnych kilka procesorów.

• Metoda planowania w czasie rzeczywistym - podzielić ja można na dwa rodzaje:

a) Rygorystyczne systemy czasu rzeczywistego - wypełniają zadania krytyczne w gwarantowanym czasie.

2. Łagodne systemy czasu rzeczywistego - procesy o decydującym działaniu mają priorytet nad słabiej sytuowanymi, jednakże nie gwarantują wypełniania zadań krytycznych w określonym czasie.

• Synchronizowanie procesów

Współbieżny dostęp do danych dzielonych może powodować ich niespójność.

Synchronizacja - mechanizmy zachowywania spójności danych przez uporządkowane

wykonywanie współpracujących ze sobą procesów użytkujących wspólnie logiczną

przestrzeń adresową. Przykład: producent - konsument.

Szkodliwa rywalizacja - sytuacja w której kilka procesów współbieżnie sięga po te same dane i wykonuje na nich działania, w skutek czego wynik tych działań zależy od porządku w jakim następował dostęp do danych.

• Sekcja krytyczna - rozważając system n-procesowy, każdy proces ma segment kodu zwany sekcją krytyczną, w którym zmienia wspólne zmienne (globalne), aktualizuje tablice, pisze do pliku, itp.

Gdy jeden proces wykonuje sekcję krytyczną to żaden inny proces nie jest dopuszczony do wykonywania swojej sekcji krytycznej.

Warunki konieczne do rozwiązania problemu sekcji krytycznej:

• Wzajemne wykluczanie - jeśli jeden proces działa w swojej sekcji krytycznej, to żaden inny proces nie działa w swojej sekcji krytycznej.

• Postęp - jeżeli żaden proces nie działa w sekcji krytycznej oraz istnieją procesy, które chcą wejść do sekcji krytycznych to tylko procesy nie wykonujące swoich reszt mogą kandydować jako następne do wejścia do sekcji krytycznych i wybór ten nie może być odwlekany w nieskończoność.

• Ograniczone czekanie - musi istnieć wartość graniczna liczby wejść innych procesów do ich sekcji krytycznych po tym, gdy dany proces zgłosił chęć wejścia do swojej sekcji krytycznej i zanim uzyskał na to pozowlenie.

Problemy sekcji krytycznej mogą zostać rozwiązane na kilka różnych sposobów. Jednym z nich jest odpowiednie napisanie programów tak, aby zachowane zostały warunki sekcji krytycznej. Można wykorzystać także sprzętowe środki synchronizacji przez użycie instrukcji niepodzielnych „Testuj_i_ustal”. W środowisku jednoprocesorowym można także wyłączyć przerwania przed wejściem do sekcji krytycznej gwarantując w ten

sposób, że proces nie zostanie wywłaszczony w momencie zmiany danych i zachowana zostanie ich spójność. Zaraz po wyjściu z sekcji krytycznej włącza się ponownie przerwania. Innym sposobem jest wykorzystanie semaforów.

• Semafor - jest to sprzętowe narzędzie synchronizacji.

Semafor S - jest to zmienna całkowita, która oprócz nadania wartości początkowej, jest dostępna tylko za pomocą dwu standardowych, niepodzielnych operacji: czekaj (wait) i sygnalizuj (signal).

• Zakleszczenia - zbiór procesów jest w stanie zakleszczenia, gdy każdy proces oczekuje na zdarzenie, które może być spowodowane tylko przez inny proces z tego zbioru.

P0 P1

czekaj(S) czekaj(Q)

czekaj(Q) czekaj(S)

... ...

sygnalizuj(S) sygnalizuj(Q)

sygnalizuj(Q) sygnalizuj(S)

Blokowanie nieskończone (głodzenie) - gdy proces czeka w nieskończoność pod semaforem (np. gdy użyje się porządku LIFO)

Warunki konieczne do wystąpienia zakleszczenia (muszą zachodzić jednocześnie):

1. Wzajemne wykluczanie - przynajmniej jeden zasób musi być niepodzielny, tzn. że

zasobu tego może używać w danym czasie tylko jeden proces, jeśli inny proces

zamawia dany zasób to musi być opóźniany do czasu aż zasób zostanie zwolniony

2. Przetrzymywanie i oczekiwanie - musi istnieć proces, któremu przydzielono co

najmniej jeden zasób i który oczekuje na przydział dodatkowego zasobu,

przytrzymywanego właśnie przez inny proces

3. Brak wywłaszczeń - zasoby nie podlegają wywłaszczaniu, co oznacza, że zasób

może zostać zwolniony tylko z inicjatywy przetrzymującego go procesu, po zakończeniu

pracy tego procesu

4. Czekanie cykliczne - musi istnieć zbiór {P0, P1,..., Pn} czekających procesów,

takich że P0 czeka na zasób przetrzymywany przez proces P1, P1 czeka na zasób

przetrzymywany przez proces P2,..., Pn-1 czeka na zasób przetrzymywany przez

proces Pn, a Pn,..., czeka na zasób przetrzymywany przez proces P0

Stan bezpieczny - system jest w stanie bezpiecznym, gdy istnieje ciąg bezpieczny, czyli gdy dla każdego procesu jego potencjalne zapotrzebowanie na zasoby może być zaspokojone przez bieżąco dostępne zasoby oraz użytkowane. Gdy ciąg taki nie istnieje to system jest w stanie zagrożenia.

Metody postępowania z zakleszczeniami:

• Zastosowanie protokołu gwarantującego, że system nigdy nie wejdzie w stan zakleszczenia.

• Metody zapobiegawcze - zbiór metod zapewniających, że co najmniej jeden z warunków koniecznych do wystąpienia zakleszczenia nie będzie spełniony.

• Schemat unikania zakleszczeń.

• Pozwolenie systemowi na zakleszczenia i podejmowanie działań zmierzających do ich usunięcia.

• Zlekceważenie problemu.

• Klasyczne problemy synchronizacji:

• Problem czytelników i pisarzy - procesy zainteresowane tylko czytaniem to czytelnicy, inne zaś to pisarze. Jednoczesne uzyskanie dostępu przez dwu czytelników do dzielonego obiektu danych w sposób oczywisty nie powoduje żadnych szkodliwych skutków. Gdyby jednak pisarz i jakiś inny proces miały jednoczesny dostęp do dzielonego obiektu mogłoby to spowodować chaos. Należy więc zagwarantować wyłączność dostępu pisarzy do obiektu dzielonego.

• Pierwszy problem czytelników i pisarzy - żaden czytelnik nie powinien czekać, chyba że właśnie pisarz otrzymał pozwolenie na używanie obiektu dzielonego. Innymi słowy, żaden czytelnik nie powinien czekać na zakończenie pracy innych czytelników tylko z tego powodu że czeka pisarz.

• Drugi problem czytelników i pisarzy - jeśli pisarz jest gotowy, to rozpoczyna wykonywanie swojej pracy tak wcześnie, jak tylko jest to możliwe. Mówiąc inaczej, jeśli pisarz czeka na dostęp do obiektu, to żaden nowy czytelnik nie rozpocznie czytania.

Rozwiązanie każdego z tych problemów może powodować głodzenie. W pierwszym przypadku może dotyczyć ono pisarzy, w drugim czytelników.

• Problem obiadujących filozofów - przy stole siedzi pięciu filozofów, którzy spędzają życie na myśleniu i jedzeniu. Naokoło stołu leży pięć misek z ryżem i pałeczek. Kiedy filozof myśli nie kontaktuje się ze swoimi kolegami. Od czasu do czasu filozof zaczyna odczuwać głód. Wówczas próbuje ująć w dłonie dwie pałeczki leżące najbliżej jego miejsca przy stole. Za każdy, razem filozof może podnieść tylko jedną pałeczkę. Jest oczywiste, że nie będzie wyrywać pałeczki z ręki sąsiada. Kiedy głodny filozof zdobędzie obie pałeczki, wtedy rozpoczyna jedzenie, nie rozstając się z pałeczkami ani na chwile. Po spożyciu posiłku filozof odkłada obie pałeczki na stół i ponownie zatapia się w rozmyślaniach.

- Przydzielanie wielu zasobów do wielu procesów w sposób grożący zakleszczeniom i głodzeniu.

Inne środki synchronizacji:

• Regiony krytyczne - podstawowa konstrukcja synchronizująca wysokiego poziomu.

• Monitory - konstrukcja stosowana w językach wysokiego poziomu do synchronizacji. Monitor jest charakteryzowany przez zbiór operacji zdefiniowanych przez programistę.

• Transakcje - zbiór instrukcji (operacji), które wykonują logicznie spójną funkcję. Transakcja jest fragmentem programu, w którym dokonuje się dostępu do rozmaitych obiektów danych przechowywanych w różnych plikach na dysku. Jest ona ciągiem operacji czytania i pisania zakończonych operacją zatwierdzenia (transakcja zakończona pomyślnie) lub zaniechania (wykonanie transakcji nie dobiegło do końca z powodu jakiegoś błędu lub awarii systemu).

Punkty kontrolne - system podczas działania rejestruje z wyprzedzeniem operacje pisania, a ponadto co pewien czas organizuje punkty kontrolne, w których należy wykonać następujący ciąg czynności:

• wszystkie rekordy aktualnie powstające w pamięci ulotnej mają być zapisywane w pamięci trwałej

• wszystkie zmienione dane pozostające w pamięci ulotnej mają być umieszczone w pamięci trwałej.

• W przechowywanym w pamięci trwałej dzienniku transakcji należy zapisać rekord <punkt kontrolny>.

4) System plików

• Interfejs systemu plików

Plik - jest zbiorem powiązanych ze sobą informacji zdefiniowanych przez jego twórcę. Jest on zwany również logiczna jednostka magazynowania informacji.

Struktura pliku - jest zależna od typu pliku (plik tekstowy, źródłowy, wykonywalny, wynikowy...)

Partycje - służą do wyodrębniania fizycznie lub logicznie wielkich zbiorów katalogów.

Atrybuty pliku:

• Nazwa - jedyna informacja przechowywana w postaci czytelnej dla użytkownika.

• Identyfikator - pole o niepowtarzalnej wartości, zwykle liczbowej, wyodrębnia plik w całym systemie; jest to nazwa pliku w postaci nieczytelnej dla człowieka.

• Typ - Ta informacja jest potrzebna w systemach, w których rozróżnia się typy plików.

• Lokacja - Jest to wskaźnik do urządzenia i położenia pliku na tym urządzeniu.

• Rozmiar - Atrybut ten określa bieżący rozmiar pliku (w bajtach, słowach lub blokach), może też określać maksymalny dopuszczalny rozmiar pliku.

• Ochrona - Informacje kontroli dostępu rozstrzygają o tym, kto może plik czytać, zapisywać, wykonywać itp.

• Czas, data i identyfikator użytkownika - Informacje te mogą obejmować czas utworzenia pliku, jego ostatniej zmiany i ostatniego użycia. Takie dane mogą być użyteczne ze względów ochronnych, bezpieczeństwa i w celu doglądania użycia plików.

Informacje o wszystkich plikach są przechowywane w strukturze katalogowej, która również rezyduje w pamięci pomocniczej.

Metody dostępu:

• Dostęp sekwencyjny - jest to najprostsza metoda dostępu. Informacje w pliku przetwarzane są po kolei - jeden rekord za drugim. W ten sposób zazwyczaj używają plików edytory i kompilatory.

• Dostęp bezpośredni (względny)- umożliwia błyskawiczne czytanie i zapisywanie rekordów bez żadnego, określonego porządku.

• Dostęp indeksowy (skorowidzowy)- Aby znaleźć jakąś pozycję w pliku, przeszukujemy najpierw indeks, a następnie używamy wskaźnika w celu uzyskania bezpośredniego dostępu do pliku i odnalezienia potrzebnego wpisu.

Struktura katalogowa zawiera informacje o zawartych w niej plikach.

• Katalog jednopoziomowy - jest to najprostsza struktura katalogowa. Wszystkie pliki są ujęte w tym samym katalogu, który jest łatwo utworzyć i obsługiwać. MS-DOS dopuszcza tylko 11-znakowe nazwy plików, UNIX zaś zezwala na 255 znaków.

• Problem nazewnictwa.

• Problem grupowania.

• Katalog dwupoziomowy - każdy użytkownik ma własny katalog plików użytkownika (user fie directory - UFD). Gdy rozpoczyna się nowe zadanie użytkownika albo użytkownik rejestruje się w systemie, wówczas przegląda się główny katalog plików (master file directory - MFD). Ścieżka przeszukiwania jest to ciąg katalogów przeszukiwanych w celu odnalezienia nazwy pliku.

• Można używać te same nazwy plików dla różnych użytkowników.

• Skuteczniejsze szukanie.

• Brak możliwości grupowania.

• Nazwa ścieżki.

• Katalogi o strukturach drzewiastych - jest to najpowszechniejsza struktura katalogowa. Każdy plik w systemie ma jednoznaczną nazwę ścieżki. Nazwą ścieżki jest ścieżka wiodąca od korzenia, przez wszystkie pośredniczące podkatalogi aż do określonego pliku.

• Efektywne szukanie.

• Możliwość grupowania.

• Każdy użytkownik ma katalog bieżący.

• Jednoznaczna (bezwzględna) i względna ścieżka dostępu.

• Tworzenie pliku wykonywane jest w bieżącym katalogu.

• Tworzenie katalogu wykonywane jest w bieżącym katalogu.

• Acykliczne grafy katalogów - umożliwia przechowywanie w katalogach podkatalogów i plików dzielonych. Ten sam plik może występować w dwóch różnych katalogach.

• Możliwość dzielenia podkatalogów i plików (dowiązania symboliczne i nie symboliczne)

• Wiele różnych nazw (aliasy)

• Jeżeli usuniemy katalog (plik) to powstanie tzw. Oswobodzenie dowiązań. Dowiązanie (link) jest wskaźnikiem do innego pliku lub podkatalogu.

Ochrona - dostęp kontrolowany.

Niezawodność - z zasady osiąga się dzięki wykonywaniu kopii zapasowych plików.

Semantyka spójności jest ważnym kryterium oceny dowolnego systemu plików

realizujących dzielenie plików. Jest to właściwość systemu określająca semantykę

jednoczesnego dostępu do pliku dzielonego przez wielu użytkowników.

Semantyka ta powinna zwłaszcza określać warunki, przy których zmiany danych

wykonywane przez jednego użytkownika są obserwowalne przez innych

użytkowników.

• Implementacja systemu plików

System plików rezyduje na stałe w pamięci pomocniczej (dysk), przesyłanie informacji miedzy pamięcią operacyjną a dyskiem odbywa się w jednostkach nazwanych blokami.

Blok - blok zawiera co najmniej jeden sektor

Sektor - ma długość od 32 do 4096 B (zwykle 512 B)

Metadane - cała struktura systemu plików, z wyjątkiem rzeczywistych danych (czyli treści plików).

Blok kontrolny pliku (file control block FCB) - zawiera informacjie o pliku, w tym nazwę właściciela, pozwolenia (dostępu) i umiejscowienie treści pliku.

Warstwowy system plików:

• Programy użytkowe - n/c

• Logiczny system plików - używa metadanych. Posługuje się strukturą katalogową, aby na podstawie symbolicznej nazwy pliku dostarczyć informacji potrzebnych modułowi organizacji pliku. Odpowiada on także za ochronę i bezpieczeństwo.

• Moduł organizacji pliku - interpretuje zarówno pliki jak i ich bloki logiczne, jak i bloki fizyczne. Tłumaczy on adresy logiczne bloków na adresy bloków fizycznych do przesłania przez podstawowy system plików.

• Podstawowy system plików - wydaje tylko ogólne instrukcje odpowiedniemu modułowi obsługi urządzenia w celu czytania i pisania poszczególnych bloków na dysku.

• Sterowanie wejściem-wyjściem - składa się z modułów obsługi urządzeń (device driver) i procedur związanych z przesyłaniem informacji między pamięcią operacyjną a systemem dyskowym.

• Urządzenia - n/c

Metody przydziału miejsca na dysku:

• Przydział ciągły - każdy plik musi zajmować zbiór kolejnych bloków na dysku. Wpis katalogowy każdego pliku zawiera adres bloku początkowego i długość obszaru przydzielonego danemu plikowi. Występuje zjawisko fragmentacji zewnętrznej. Fragmentacja zewnętrzna - gdy występuje dużo małych, trudnych do zagospodarowania bloków na dysku. W przydziale ciągłym można implementować dostęp sekwencyjny i swobodny ale pliki nie mogą rosnąć.

• Przydział listowy - każdy plik jest listą powiązanych ze sobą bloków dyskowych. Katalog zawiera wskaźnik do pierwszego i ostatniego bloku (wskaźniki nie są dostępne dla usera). Nie występuje zjawisko fragmentacji zewnętrznej. Efektywne zastosowanie możliwe jest tylko dla plików o dostępie sekwencyjnym. Tablica przydziału plików FAT jest odmianą przydziału listowego.

• Przydział indeksowy - każdy plik ma własny blok indeksowy, będący tablicą adresów bloków dyskowych. Katalog zawiera adres bloku indeksowego. Nie występuje zjawisko fragmentacji zewnętrznej.

Zarządzanie wolną przestrzenią:

System utrzymuje listę wolnych obszarów i implementowaną w postaci:

• wektora bitowego (mapy bitowej) - każdy blok reprezentowany jest przez 1 bit, jeżeli blok jest wolny bit ma wartość 1, zajęty - 0

• listy powiązanej - powiązanie ze sobą wszystkich wolnych bloków dyskowych i przechowywanie wskaźnika do pierwszego wolnego bloku.

• grupowania - przechowywanie adresów `n' wolnych bloków w pierwszym bloku, ostatni blok zawiera adresy następnych `n' wolnych bloków.

• zliczania - utrzymuje się listę, na której zapisane są: adres wolnego bloku i ilość kolejnych wolnych bloków po nim.

Rekonstrukcja:

Metody tworzenia kopii zapasowych (backup):

• składowanie pełne (full backup) - kopiowanie na nośnik zapasowy wszystkich plików z dysku.

• składowanie przyrostowe (incremental backup) - kopiowanie na inny nośnik wszystkich plików zmienionych od czasu zrobienia pełnego backup'u.

• składowanie różnicowe (differential backup)

• Przykłady

• FAT (File Allocation Table) -

• FAT 16 - implementacja w 1977 roku. Podstawową jednostką alokacji jest klaster.

• zastosowanie: dyski twarde o małej i średniej pojemności

• maksymalna liczba klastrów: 65 tys.

• wielkość używanych klastrów: 2-32 KB

• FAT 32

• zastosowanie: dyski twarde o średniej i dużej pojemności

• maksymalna liczba klastrów: 286 mln.

• wielkość używanych klastrów: 4-32 KB

• NTFS (New Technology File System) - Podstawowe cechy:

• Szyfrowanie i odzyskiwanie zaszyfrowanych danych kluczem symetrycznym (EFS)

• Dziennik zmian i przydziały dysku

• Kompresja.

---