Abraham Silberschatz Podstawy Systemów Operacyjnych (Edycja 5) Streszczenie

wówczas, gdy są one nieodzowne do wykonywania ich zadań. Ponieważ często może dochodzić do
konfliktowych zamówień na zasoby, system operacyjny musi decydować o przydziale zasobów
poszczególnym zamawiającym, mając na względzie harmonijne i wydajne działanie całego systemu
komputerowego.

System operacyjny

jest

programem sterującym

- nadzoruje działanie programów użytkownika,

przeciwdziała błędom i zapobiega niewłaściwemu użyciu komputera. Zajmuje się zwłaszcza
obsługiwaniem i kontrolowaniem pracy urządzeń wejścia-wyjścia.

System operacyjny

jest to ten program , który działa w komputerze nieustannie (nazywany zazwyczaj

jądrem

) , podczas gdy wszystkie inne są programami użytkowymi.

Najważniejszym celem systemu operacyjnego jest

wygoda użytkownika i efektywność działania

systemu komputerowego.Te dwa cele są nieraz sprzeczne ze sobą - dlatego teoria systemów operacyjnych
skupia się przede wszystkim na optymalnym użytkowaniu zasobów komputerowych.

Systemy operacyjne i architektura komputerów wywarły na siebie wzajemnie znaczny wpływ. Aby
ułatwić posługiwanie się sprzętem, zaczęto rozwijać systemy operacyjne. Wraz z postępami w
projektowaniu i użytkowaniu systemów operacyjnych okazało się, że wprowadzenie zmian w sprzęcie
ułatwiłoby ich działanie.

1.2.Wczesne systemy operacyjne.

Na początku był tylko sprzęt komputerowy...

Pierwsze komputery były wielkimi (fizycznie maszynami) obsługiwanymi za pośrednictwem

konsoli

Programista pisał i uruchamiał program

bezpośrednio

przy konsoli operatorskiej. Najpierw należało

program (

rozkaz po rozkazie

) wprowadzić ręcznie do pamięci, ustawiając przełączniki na płycie

czołowej, względnie posługując się

czytnikiem taśmy papierowej

lub

kart dziurkowanych

. Następnie

trzeba było nacisnąć odpowiednie przyciski, aby ustawić

adres startowy

i rozpocząć wykonywanie

programu. Podczas wykonywania programu programista-operator mógł nadzorować jego działanie,
obserwując lampki (sic!) na konsoli. W razie wykrycia błędu, programista mógł wstrzymać program,
sprawdzić

zawartość pamięci

oraz

rejestrów

i wprowadzić poprawki z konsoli. Wyniki były

drukowane

albo

dziurkowane

na taśmie papierowej lub kartach w celu późniejszego ich wydrukowania.

Ważny aspekt takiego środowiska to jego

bezpośredni

, interakcyjny charakter.Programista był

jednocześnie

operatorem

systemu komputerowego.

W celu przydzielania czasu pracy maszyny stosowano

harmonogramy pracy maszyny

Każdy użytkownik musiał zapisać się , by móc w określonym czasie skorzystać z komputera.

W miarę upływu czasu powstawało coraz więcej oprogramowania i sprzętu.
Upowszechniły się

czytniki kart, drukarki wierszowe i taśmy magnetyczne

Dla ułatwienia programwania opracowano

asemblery, programy ładujące i programy łączące

Powstały biblioteki typowych funkcji. Szczególnie ważne okazały się biblioteki podprogramów
wykonujących operacje wejścia-wyjścia, (

programy obsługi urządzeń

) różne i specyficzne dla każdego

typu urządzenia znacznie ułatwiły pisanie programów.
Później pojawiły się

kompilatory języków

- Fortranu i Cobolu i in.

Zostało znacznie ułatwione programowanie ale obsługa i działnie komputera znacznie się skomplikowało.
Przykład czynności potrzebnych do wykonania programu w Fortranie :
1.)Wprowadzenie do komputera kompilator Fortrana.- czyli zamontowanie odpowiedniej taśmy na
urządzeniu.
2.)Przeczytanie programu z czytnika kart i zapisanie go na innej taśmie.
3.)Kompilator Fortranu wytwarzał na wyjściu przekład programu na język asemblerowy.
4.)Przetworzenie przez asembler.- czyli zamontowanie odpowiedniej taśmy z asemblerem.
5.)Połączenie z funkcjami bibliotecznymi.
6.)Gotowy program w systemie dwójkowym gotowy do wykonania - wprowadzenie do pamięci i
uruchomienie z konsoli operatorskiej.
Znaczną część czasu wykonania takiego zadania zabierał

czas instalowania

1.3. Prosty monitor.

Czas instalowania

zadania stanowił poważną trudność - jednostka centralna była wtedy bezczynna, a ze

względów ekonomicznych dążono do maksymalizacji wykorzystania komputera.
Rozwiązano to za pomocą :
1) Zawodowych operatorów.
Programista przestał obsługiwać maszynę , a zajął się tym operator.(Kiedy kończyło się
jedno zadanie , mógł instalować już następne).
Znikły więc przestoje spowodowane sztywną rezerwacją czasu komputera.
Skrócono czas instalowania - operator miał więcej wprawy w instalowaniu taśm.
Użytkownik oprócz kart i taśm dostarczał krótki opis wykonania zadania.
W przypadku błędów wyprowadzano zawartość pamięci i programista szukał przyczyn
błędów. A operator mógł uruchamiać następne zadanie.
2) Skrócenie czasu instalowania zadania za pomocą

wsadów

- grup zadań o podobnych wymaganiach.

Pozostały jednak inne problemy - czas przestoju pracy procesora przy przechodzeniu z jednego zadania
do drugiego.W celu likwidacji tej bezczynności zastosowano metodę

automatycznego porządkowania

zadań

(ang.

automatic job sequencing

), która posłużyła jako podstawa do zbudowania pierwszych,

najprostszych systemów operacyjnych.Dla realizacji procedury automatycznego przekazywania
sterowania od jednego zadania do następnego ułożono program zwany

monitorem rezydującym

, który

stale przebywa w pamięci komputera.

Rozmieszczenie monitora rezydującego w pamięci :

|program ładujący
monitor => |porządkowanie zadań
|interpretator kart sterujących
-----------------------------------
obszar programu użytkownika
-------------------------------------------------------

Po włączeniu komputera wywoływano monitor rezydujący , który przekazywał sterowanie do programu.
Kiedy program kończył działanie, wtedy zwracał sterowanie do monitora, a ten wyznaczał kolejny
program.Aby monitor wiedział , który program uruchomić wprowadzono

karty sterujące

.Są one

dyrektywami dla monitora wskazującymi , które programy mają być uruchomione.
Karty sterujące umieszcza się razem z programami.
Np.$FTN - uruchamia kompilator Fortranu
$ASM - uruchamia asembler.
$RUN - uruchamia program użytkownika
Dodatkowo karty separujące zadania ( pozwalają dodatkowo zdefiniować parametry zadania
np.nazwa,numer rachunku itd.)
$JOB - pierwsza karta zadania
$END - ostatnia karta zadania
Karty sterujące mogły też służyć do poproszenia operatora o założenie taśmy.
Odróżnienie kart sterujących od kart programu dokonywało się za pomocą :
a)znaku dolara ($) w pierwszej kolumnie.
b)W

JCL -Job Control Language

( język sterowania zadaniami by IBM) stosowano (//) w dwóch

pierwszych kolumnach.

Monitor rezydujący

składa się m. in. z

interpretatora kart sterujących

- odpowiedzialnego za czytanie

i wykonywanie poleceń z kart podczas wykonywania zadania.

Interpretator kart sterujących

wywołuje

też

program ładujący

, który uruchamia programy systemowe i użytkowe.

Monitor również musi być wyposażony w programy do obsługi urządzeń wejścia-wyjścia.

1.4.Praca pośrednia.

Powolność urządzeń wejścia-wyjścia może powodować , że jednostka centralna będzie często na nie
oczekiwać.Sposobem na to było zastąpienie bardzo powolnych czytników kart (wejście) i drukarek
wierszowych (wyjście) jednostkami taśmy magnetycznej.Kopiowano wpierw zawartość kart na taśmę
magnetyczną i dopiero wówczas gdy była zapełniona przenoszono ją do komputera.Wyniki natomiast
również nagrywano na taśmie , a drukowano w późniejszym terminie.Taki sposób obsługi czytnika kart i
drukarki nazywa się

trybem pośrednim.(off-line)

Tryb pośredni

realizowano na dwa sposoby:

1) Skonstruowano specjalne czytniki i drukarki mogące bezpośrednio współpracować z taśmą
magnetyczną.
2)Przeznaczono małego komputera (np.IBM 1401) wyłącznie do celów kopiowania na taśmy i z
taśm.Taki komputer stawał się

satelitą

głównego komputera.

Przetwarzanie satelitarne

było jednym z

pierwszych przypadków organizacji systemów wielokomputerowych, w których współpraca
poszczególnych komputerów miała na celu poprawienie działania całości.

Zaletą trybu pośredniego było to , że komputer główny nie był ograniczony przez wolne urządzenia we-
wy lecz przez o wiele szybsze napędy taśm magnetycznych.

Dodatkowo zmiana urządzeń we-wy nie wymagała żadnych zmian w stosowanych
programach.Zmieniano jedynie programy obsługi urządzeń w monitorze rezydującym pod tą samą
procedurą systemową.W ten sposób programowi było wszystko jedno z jakiego urządzenia korzysta
monitor , gdyż dostawał taki sam obraz danych jak w trybie bezpośrednim.

Możliwość działania programu z różnymi urządzeniami we-wy zwie się

niezależnością od

urządzeń

.Polega to na pozostawieniu decyzji o tym , którego urządzenia będzie używał program ,

systemowi operacyjnemu.W programach używa się

logicznych urządzeń we-wy

, a interpretacja ich na

urządzenia rzeczywiste należy do kart sterujących (lub innych poleceń).
Faktyczny zysk czasu wynika jeszcze z możliwości pomnożenia liczby zestawów czytnik-taśma taśma-
drukarka przypadających na jeden procesor

Bezpośrednia praca urządzeń we-wy

czytnik kart => jednostka centralna => drukarka wierszowa

Pośrednia praca urządzeń we-wy

czytnik kart => przewijaki taśmy => jednostka centralna => przewijaki taśmy => drukarka wierszowa.

1.5. Buforowanie i spooling.

1.5.1 Buforowanie.

Buforowanie

jest metodą jednoczesnego wykonywania obliczeń i operacji we-wy dla danego zadania.Po

przeczytaniu danych, kiedy procesor może zacząć je przetwarzać, wtedy poloeca się urządzeniu we
natychmiastowe rozpoczęcie czytania następnych danych. W ten sposób zarówno jednostka centralna, jak
i urządzenia we są zajęte.(przy odpowiednich parametrach - patrz niżej).
Podobnie można postąpić na wy.Tym razem procesor posyła dane do bufora, skąd może je pobierać
urządzenie wy.
W praktyce

buforowanie

danych rzadko utrzymuje i jednostkę centralną , i urządzenie we-wy w stanie

nieprzerwanej aktywności, ponieważ albo procesor, albo urządzenie we kończy pracę wcześniej.

Czynność

buforowania

należy do

obowiązków systemu operacyjnego

Monitor rezydujący

lub

programy obsługi

urządzeń

zawierają systemowe

bufory

we-wy dla każdego urządzenia zew.Wywołania programów

obsługi urządzeń przez programy użytkowe ( zamówienia na operacje we-wy) powodują zazwyczaj
przesyłanie danych do lub z bufora systemowego.Rzeczywista operacja we-wy albo jest już wykonana,
albo zostanie wykonana później - kiedy urządzenie będzie dostępne.

W zadaniach

uzależnionych od we-wy

procesor często czeka na urządzenia zew.

W zadaniach

uzależnionych od jednostki centralnej

procesor nie może nadążyć za urządzeniami we-

wy.

Buforowanie dla drugiego przypadku jest bardziej pomocne

, ale we wczesnych systemach

komputerowych większość zadań była uzależniona od we-wy.Buforowanie pomagało nieco ale
urządzenia i tak były za wolne by nadążyć za procesorem.

1.5.2. Spooling

Szerokie rozpowszechnienie się

systemów dyskowych

spowodowało , że zaczęto jest stosować do pracy

pośredniej zamiast systemów taśmowych , które miały tą wadę , że przed zaczęciem zapisywania trzeba
było przeczytać całą taśmę , przewinąć a dopiero potem zapisywać.
Głowica dysku może natomiast błyskawicznie przemieszczać się po całym jego obszarze przeskakując z
obszaru czytania do obszaru zapisywania.
Dlatego zastosowano metodę , w której zawartość czytnika przesyłana jest bezpośrednio na dysk
(rozmieszczenie obrazów kart jest zapisywane w tablicy przechowywanej przez system operacyjny), a
płynące z programu zamówienia na dane z czytnika są realizowane poprzez czytanie z dysku.Gdy zaś
zadanie zażąda wyprowadzenia wiersza na drukarkę , wówczas dany wiersz będzie skopiowany do buforu
systemowego i zapisany na dysku. Po zakończeniu zadania jego wyniki są rzeczywiście drukowane. Ta
metoda nazywana jest

spoolingiem

.(ang.

simultaneous peripheral operation on-line

jednoczesna

bezpośrednia praca urządzeń).
Spooling w istocie polega na tym , że używa się dysku jako bardzo wielkiego buforu do czytania danych
z maksymalnym wyprzedzeniem z urządzeń wejściowych oraz do przechowywania plików wyjściowych
do czasu, aż urządzenia wyjściowe będą w stanie je przyjąć.
Można też przesłać całą zawartość taśmy na dysk ( ang.

staging - przeniesienie danych

) wtedy wszystkie

działania odnosić się będą do dysku .

Spooling

umożliwił zwiększenie wykorzystania procesora , jak i urządzeń we-wy , zwłaszcza wtedy gdy

są ze sobą przemieszane zadania uzależnione od jednostki centralnej i od we-wy, gdyż procesor mógł
wykonywać obliczenia jednego zadania równośczenie z operacjami we-wy dla innych zadań .

Spooling

wytwarza bardzo ważną strukturę danych -

pulę zadań

.Pula zadań na dysku pozwala

systemowi operacyjnemu tak wybierać następne zadanie do wykonania, aby zwiększyć wykorzystanie
jednostki centralnej. Staje się więc możliwe

planowanie zadań

1.6. Wieloprogramowość.

Najistotniejszym aspektem

planowania zadań

jest

wieloprogramowość

.Jeden użytkownik nie jest w

stanie spożytkować sam wszystkich zasobów systemu. Ideą więc wieloprogramowości jest przełączanie
się między zadaniami wtedy gdy zadanie musi czekać na zakończenie jakiejś operacji nie okupującej
czasu procesora. Procesor zaczyna wykonywać następne zadanie , a gdy i to przerwie swą akcję w
oczekiwaniu na zakończenie np. operacji we-wy , rozpoczyna kolejne zadanie.Jeśli jakieś z poprzednio
wykonywanych zadań zakończy oczekiwanie , to powraca do jego wykonywania.Dopóki są jakieś
zadania do wykonania , dopóty nie ma przestojów.
Wieloprogramowe systemy operacyjne są skomplikowane - wymagają :
- utrzymywanie kilkunastu programów w pamięci
- specyficznego

zarządzania pamięcią

planowanie przydziału procesora

(gdy jest > 1 zadanie gotowe do wykonania.

- kontrola wzajemnych potencjalnie niekorzystnych oddziaływań między zadaniami (na polu planowania
procesów, magazynowania danych na dyskach i zarządzania pamięcią).

1.7. Podział czasu.

Podział czasu

(inaczej

wielozadaniowość

) stanowi logiczne rozszerzenie wieloprogramowości.Procesor

przełącza się między różnymi zadaniami ale na tyle szybko , że użytkownicy mogą współdziałać z
każdym programem podczas jego wykonywania.

Wielozadaniowość

umożliwia jednocześnie obsługę tak wielu zadań , że może stworzyć

dostęp

interakcyjny

(

bezpośredni - ang. hands-on

) użytkownika do systemu . Ułatwia to reakcję użytkownika

na nieprzewidziane zachowania programu , który testuje , pomaga na bieżąco poprawiać błędy i
uruchamiać ponownie.Wymaga to jednak innych, dodatkowych bardziej user-friendly urządzeń we-
wy.Jako wejście służy wtedy klawiatura (nareszcie:-)), a jako wyjście drukarka lub ekran monitora (
np.CRT - cathode-ray tube).
W celu udogodnienia dostępu do danych i do oprogramowania dostarcza się

system plików dostępnych

bezpośrednio

(ang.

on-line file system

) .

Plik

jest zestawem powiązanych informacji, zdefiniowanym przez jego twórcę .

Pliki

mogą zawierać programy (wersja źródłowa lub wynikowa) lub dane.

Pliki

mogą zawierać liczby, tekst lub mieszane dane alfanumeryczne.

Pliki

mogą mieć układ swobodny (pliki tekstowe) lub precyzyjnie określony format.

Abstrakcyjne pojęcie pliku jest urzeczywistnione przez system operacyjny przez zarządzanie
urządzeniami pamięci masowych.Pliki są zorganizowane w logicznie niepodzielne grupy lub katalogi
oraz ustanowiony jest nadzór nad tym kto i w jaki sposób korzysta z plików.

Systemy interakcyjne

mają zastosowanie tam gdzie oczekuje się szybkich odpowiedzi.

Panuje w nich

tryb konwersacyjny

- wyniki mogą być wyświetlane na ekranie , a polecenia i dane

wyprowadzane z klawiatury.

Dla systemów operacyjnych z podziałem czasu stworzono mechanizmy działan współbieżnych ,
zarządzania pamięcią , ochrony i planowania przydziałów procesora , administrowania pamięcią
dyskową (która stała się niezbędna jako zaplecze dla pamięci operacyjnej) , systemów plików dostępnych
bezpośrednio i ich ochrony.

1.8. Systemy rozproszone.

W systemach

wieloprocesorowych

procesory współdzielą pamięć i zegar .Są to systemy

ściśle

powiązane.

luźno powiązanych

systemach każdy procesor ma własną pamięć lokalną.Procesory komunikują się

za pomocą różnych linii komunikacyjnych , na przykład za pomocą szybkich szyn danych lub za pomocą
łączy telefonicznych.Systemy te nazywają sie

systemami rozproszonymi

Powody , dla których buduje się

systemy rozproszone

Podział zasobów

Możliwość dostępu dzielonego do plików w węzłach zdalnych , przetwarzania informacji w
rozproszonych bazach danych, drukowania plików w węzłach zdalnych, zdalnego użytkowania
specjalizowanych urządzeń sprzętowych itd.

Przyśpieszenie obliczeń

Jeśli dane obliczenie da się rozłożyć na zbiór obliczeń cząstkowych, które można wykonywać
współbieżnie, to system rozproszony umożliwia przydzielenie obliczeń cząstkowych poszczególnym
węzłom i współbieżne wykonanie obliczeń.Ponadto, jeżeli pewne stanowisko jest w danej chwili
przeładowane zadaniami, to część z nich można przenieść do innego, mniej obciążonego stanowiska.
Takie przemieszczanie nazywa się

dzieleniem obciążeń

Niezawodność

W przypadku awarii jednego węzła w systemie rozproszonym pozostałe węzły mogą kontynuować
pracę.Jeżeli istnieje w systemie wystarczający zapas zasobów system może pracować nawet po
uszkodzeniu pewnej liczby jego węzłów.

Łączność

Wymiana danych pomiędzy programami lub między użytkownikami ( poczta elektroniczna ).

1.9. Systemy czasu rzeczywistego.

Innym rodzajem systemu operacyjnego jest

system czasu rzeczywistego

Jest stosowany bardzo często jako sterownik urządzenia o ściśle określonym zadaniu.Czujniki dostarczają
dane do komputera.Komputer musi analizować te dane i w zależności od sytuacji regulować działanie
kontrolowanego obiektu, tak aby zmieniły się wskazania wejściowe czujników.System operacyjny czasu
rzeczywistego ma ściśle zdefiniowane, stałe ograniczenia czasowe.Przetwarzanie danych musi się
skończyć przed upływem ściśle określonego czasu , inaczej system nie spełnia wymagań.

1.10. Systemy operacyjne jednostanowiskowe.

Potanienie sprzętu spowodowało upowszechnienie się komputerów osobistych , a z nimi powstały
systemy operacyjne , które nie stawiały sobie celów wielozadaniowości i wielodostępności , a głównie
dbały o wygodę użytkowania , z czasem jednak i te systemy operacyjne doczekały się właściwości
wielozadaniowości mając jednak głównie na celu wygodę użytkownika.

2. Struktury systemów komputerowych.

2.1.Systemy z obsługą przerwań.

Aby operacje CPU (jednostki centralnej) i urządzeń we-wy mogły być wykonywane równocześnie muszą
istnieć metody desynchronizacji i resynchronizacji.Istnieją dwie:



przesyłanie danych sterowane

przerwaniami



przesyłanie danych na zasadzie

bezpośredniego dostępu do pamięci

(

DMA - direct-memory-

access)

W starszych systemach zamiast tych metod przesyłanie było sterowane przez CPU.To uniemożliwiało
jednoczesne obliczenia i transfer danych z/do urządzeń zewn.
Stosowano metodę

aktywnego czekania

- procesor musiał czekać na zakończenie operacji we/wy cały

czas sprawdzając stan urządzeń.Wprawdzie można kazać procesorowi wykonywać inne zadanie między
kolejnymi operacjami we/wy to istnieje jednak ryzyko utracenia części danych.
Dlatego rozwiązaniem jest system oparty na

przerwaniach we/wy.

Struktura:

- Każdy sterownik urządzenia zewn. ma pod opieką specyficzny typ urządzenia.
- Sterownik ten odpowiada za :
a) rozporządzanie lokalnym buforem i zbiorem rejestrów
b) przesyłanie danych pomiędzy urządzeniem zewnętrznym a jego własną pamięcią
buforową.
-

Inicjowanie przesyłania danych

a) procesor wprowadza pewne liczby do odpowiednich rejestrów sterownika
b) wznowienie normalnej pracy
c) sterownik bada rejestry by podjąć określone przez nie zadanie
-

Kiedy przesyłanie się zakończy

sterownik informuje CPU o tym za pomocą

sygnału przerwania

- Procesor przerywa pracę i pobiera zawartość określonego miejsca pamięci ( najczęściej jest to

adres

startowy procedury obsługującej to przerwanie

)

- procedura obsługi przerwania przesyła dane z lokalnego bufora sterownika do pamięci głównej.
- po zakończeniu przesyłania danych procesor jest gotowy do wznowienia przerwanych obliczeń.

Ważne cechy przerwań :

- Przerwanie musi przekazywać sterowanie do

procedury obsługi przerwań

Tablica w pamięci , w której przechowywane są adresy procedur obsługi przerwań
pochodzących od różnych urządzeń nazywana jest wektorem przerwań i jest indeksowana
jednoznacznym numerem urządzenia.
- Trzeba też uwzględnić przechowanie adresu przerwanego rozkazu (np. na

stosie systemowym

)

- Trzeba także przechować zawartość rejestrów procesora w momencie gdy nastąpiło
przerwanie.Po obsłużeniu przerwania następuje pobranie

adresu powrotnego

i wznowienie

działania procesora na przerwanym etapie tak jakby przerwania nie było.

Zwykle podczas obsługi jednego przerwania inne przerwania są

wyłączone

(ang.

disabled

) - następuje

opóźnianie przyjęcia następnego przerwania do czasu , aż zakończy się bieżące przerwanie i wtedy
przerwania zostaną

włączone

(ang.

enabled

).Bez tej możliwości uruchomienie kolejnego przerwania przy

niezakończonej obsłudze poprzedniego mogłoby spowodować zniszczenie danych i

utratę

pierwszego

przerwania.

Doskonalsze architektury pozwalają jednak na obsługę nowego przerwania przed zakończeniem
poprzedniego na zasadzie

priorytetowej

.Poszczególnym żądaniom nadaje się priorytety , a informacje o

przerwaniach są przechowywane w osobnym miejscu dla każdego priorytetu.
Przerwanie o wyższym priorytecie zostanie obsłużone nawet wtedy gdy jest aktywne jakieś inne
przerwanie , a przerwanie niższego priorytetu są

maskowane

czyli

selektywnie wyłączane

Druga metoda (

DMA

) jest stosowana w przypadku szybkich urządzeń - gdy czas obsługi przerwania jest

dłuższy od czasu odstępu między przerwaniami.
Polega to na tym , że po określeniu

buforów, wskaźników i liczników

sterownik danego urządzenia

przesyła od razu cały blok danych między własnym buforem , a pamięcią - bez udziału procesora.
Przerwanie wypada więc raz na cały blok danych.
Przebieg przesyłu z DMA:
- system operacyjny żąda przesłania danych
- wybór bufora we/wy z kolejki gotowych do przesłania.
- umieszczenie w rejestrach sterownika DMA

adresy źródła i miejsce przeznaczenia.

(dokonuje tego na

ogół program obsługi urządzenia)
- sterownik DMA inicjalizuje operacje we/wy , a po jej zakończeniu wysyła przerwanie do procesora.

2.2. Struktura wejścia-wyjścia.

Jeśli system nie ma żadnych zadań ani nie czekają na niego do obsługi żadne urządzenia we/wy , to
system operacyjny spokojnie oczekuje na jakieś

zdarzenie

Zdarzenia

są głównie sygnalizowane przez przerwania lub tzw.

pułapki.

Pułapka

(lub wyjątek) jest rodzajem przerwania generowanym przez oprogramowanie, a powodowanym

albo przez błąd , albo przez specjalne zamówienie pochodzące z programu użytkownika, które wymagają
obsłużenia przez system operacyjny.System operacyjny jest zatem sterowany zdarzeniami.
Po wykryciu przerwania ( lub pułapki) sprzęt przekazuje sterowanie do systemu operacyjnego , który w
pierwszej kolejności przechowuje bieżący stan jednostki centralnej, zapamiętując wartość rejestrów i
licznika rozkazów.
Ustala rodzaj wykrytego przerwania.Albo za pomocą

odpytywania

tj. badania stanu wszystkich urządzeń

we/wy , by wykryć ten który potrzebuje obsługi, albo może stanowić naturalny efekt zastosowania

wektorowego systemu przerwań.

Każdemu rodzajowi przerwania odpowiadają w systemie operacyjnym odrębne segmenty kodu ,
określające działania, które należy podjąć w związku z przerwaniem.
Po rozpoczęciu operacji we/wy są możliwe dwa scenariusze.
Albo operacja rozpoczyna się , kończy i sterowanie wraca do programu użytkownika.
Albo następuje oddanie sterowania do programu użytkownika bez czekania na zakończenie operacji.
Czekanie na zakończenie operacji może się odbyć na dwa sposoby.
Za pomocą rozkazu

wait

(

czekaj

) - powodującego bezczynność procesora aż do chwili wystąpienia

przerwania.
Lub za pomocą pętli czekania :
czekaj : jmp czekaj
Pętla ta jest wykonywana dopóki nie nastąpi przerwanie i oddanie sterowania do innej części systemu

operacyjnego.Rozkaz

wait

jest lepszy gdyż wykonywanie pętli może spowodować rywalizację o dostęp

między urządzeniem , a procesorem pobierającym rozkazy.

Zaletą ciągłego czekania na zakończenie jednej operacji we/wy jest to , że w jednym czasie występuje
tylko jedno nieobsłużone zamówienie.Z drugiej strony uniemożliwia to jednoczesną pracę urządzeń.

Innym rozwiązaniem jest zapoczątkowanie transmisji i natychmiastowe zwrócenie sterowania do
programu użytkownika. Wówczas, aby umożliwić użytkownikowi zaczekanie na zakończenie transmisji ,
trzeba odwołać się do systemu operacyjnego. Potrzebny stale jest kod powodujący czekanie.Trzeba też
odnotować wiele operacji we/wy w tym samym czasie. Robi się to za pomocą

tablicy stanów urządzeń

Każdy element tej tablicy określa typ urządzenia, jego adres i stan (nieoperatywne , bezczynne,
zajęte).Dla stanu zajętego dla określonego urządzenia odpowiadający mu element tablicy zawiera rodzaj
zamówienia i odpowiednie parametry.
Zamówienia mogę też tworzyć listę , gdy więcej niż jedno jest zgłoszone dla tego samego urządzenia.

Urządzenie we/wy wysyła przerwanie , jeśli wymaga obsługi. Po wystąpieniu przerwania system
operacyjny rozstrzyga najpierw, które urządzenie spowodowało przerwanie . Następnie pobiera z

tablicy

stanu urządzeń

informacje o stanie danego urządzenia i zmienia je.Ponieważ na ogół przerwanie

następuje na zakończenie operacji , to system sprawdza czy jest jakieś następne zamówienie do
obsłużenia przez urządzenie i realizuje je.
Na koniec procedura obsługi przerwania z urządzenia we/wy zwraca sterowanie.Jeśli na zakończenie jej
czekał czekał jakiś program (co zostało odnotowane w

tablicy stanów urządzeń

), to można oddać mu

sterowanie. W przeciwnym razie nastąpi powrót do tego , co było robione przed przerwaniem: do
wykonywania programu użytkownika (program rozpoczął operację we/wy , która się właśnie zakończyła,
ale program nie czekał na zakończenie operacji) albo do pętli czekania ( program zapoczątkował dwie
lub więcej operacji we/wy i czeka na zakończenie jednej z nich, lecz to przerwanie pochodziło od jakiejś
innej).

Istnieje też sytuacja kiedy można dokonywać operacji we bez zamówienia ze strony programu.Na
przykłąd przy wczytywaniu znaków z klawiatury.Tworzy się specjalny bufor , do którego ładuje się znaki
, które czekają później aż zgłosi się po niego jakiś program.

2.3. Dualny tryb pracy.

Ponieważ system operacyjny dzieli zasoby systemowe między pewną liczbę programów jednocześnie
spowodowało to poprawę użytkowania systemu ale powiększyło ilość problemów.
Koegzystencja wielu programów w pamięci powoduje ryzyko , że błąd który wystąpi w jednym
programie będzie miał wpływ na działanie innych zadań.Na przykład program może pozmieniać dane
innego programu lub nawet kod samego systemu operacyjnego.Dobrze zaprojektowany system
operacyjny musi gwarantować , że niepoprawny (lub złośliwy program) nie będzie mógł zakłócić
działania innych programów.

Wiele błędów programowania jest wykrywanych przez sprzęt.Tymi błędami zajmuje się na ogół system
operacyjny.Gdy program użytkownika dopuści się jakiegoś uchybienia, na przykład spróbuje wykonać
niedozwolony rozkaz lub sięgnąć po komórkę pamięci nienależącą do jego przestrzeni adresowej,
wpadnie w

pułapkę

zastawioną przez sprzęt, co oznacza w skutkach przejście do systemu

operacyjnego.Tak jak przerwanie, pułapka powoduje przejście do systemu operacyjnego za pomocą

wektora przerwań

.Za każdym razem gdy wystąpi błąd w programie system wymusza nienormalne

zakończenie programu.Zdarzenie takie jest obsługiwane za pomocą tego samego kodu, co żądanie
nienormalnego zakończenia programu pochodzące od użytkownika.

Takie podejście sprawdza się jeżeli błędy są wykrywane przez sprzęt.Powinny być wykrywane wszystkie
błędy ,by chronić system operacyjny i inne programy oraz ich dane przed każdym niepoprawnie
działającym programem.Toteż ochrona musi obejmować wszystkie

zasoby dzielone

Polega to na zaopatrzeniu sprzętu w środki do rozróżniania

trybu

jego pracy.Minimalnie potrzebne jest

rozdzielenie dwóch

trybów

trybu użytkownika

trybu monitora

( inaczej zwanego

trybem nadzorcy i

trybem systemu

). Sprzęt komputerowy uzupełnia się o

bit

(zwany

bitem trybu

) , którego wartość

wskazuje bieżący tryb pracy: monitor(0) lub użytkownik(1). Za pomocą

bitu trybu

można rozróżnić

działania wykonywane na zazmówienie systemu operacyjnego od działań wykonanych na zamówienie
użytkownika.
Za każdym razem po wystąpieniu pułapki lub przerwania, sprzęt zmienia swój tryb pracy z trybu
użytownika na tryb monitora.Tym samym, ilekroć system operacyjny otzrymuje sterowanie nad
komputerem, tylekroć jest on w trybie monitora.Przed przejściem do programu użytkownika system
zawsze przełącza tryb pracy na tryb użytkownika.

Dualny tryb pracy

komputera dostarcza środków do ochrony systemu operacyjnego przed

nieodpowiedzialnymi użytkownikami, a także do chronienia nieodpowiedzialnych użytkowników samych
przed sobą. Ochrona ta jest uzupełniana za pomocą oznaczenia potencjalnie niebezpiecznych rozkazów
kodu maszynowego jako

rozkazów uprzywilejowanych

.Sprzęt pozwala na wykonanie

rozkazów

uprzywilejowanych

tylko w trybie monitora.Próba wykonania rozkazu uprzywilejowanego w trybie

użytkownika nie zakończy się wykonaniem go przez sprzęt , a potraktowany zostanie jako
niedopuszczalny i poprowadzi prosto do pułapki obsługiwanej przez system operacyjny.

2.4 Ochrona sprzętowa.

Aby ustrzec użytkownika przed wykonywaniem niedozwolonych operacji we/wy przyjęto ,że wszystkie
rozkazy we/wy są

uprzywilejowane.

Użytkownicy nie mogą więc używać tych rozkazów bezpośrednio,

lecz muszą robić to za pośrednictwem systemu operacyjnego. Pełna ochrona we/wy musi zapewniać , że
program użytkownika nigdy nie przejmie kontroli nad komputerem w trybie pracy monitora. Jeżeli
komputer pracuje w trybie użytkownika , to przechodzi w tryb monitora przy każdym wystąpieniu

przerwania lub pułapki

, wykonując skok pod adres określony w

wektorze przerwań.

Jeśli program

użytkownika umieściłby nowy adres w wektorze przerwań , to mógłby on wskazać miejsce w
programie użytkownika i w wypadku odpowiedniego przerwania sprzęt przełączałby komputer w tryb
monitora i przekazał sterowanie według zmienionego wektora przerwan do programu użytkownika.!
Program osiągnąłby kontrolę nad komputerem w trybie pracy monitora.!

Trzeba chronić

wektor przerwań

przed zmianami , które mógłby wprowadzić program użytkownika.

Także trzeba chronić przed modyfikacjami systemowe procedury obsługi przerwań. Inaczej program
mógłby rozkazy w procedurze zastąpić skokami do własnego obszaru, przechwytując sterowanie od
procedury obsługi przerwania, pracującej w trybie monitora.

Aby oddzielić od siebie obszary pamięci każdego programu, musimy mieć możność rozstrzygania o
zakresie dopuszczalnych adresów programu i chronienia pamięci poza tymi adresami. Tego rodzaju
ochronę można uzyskać za pomoca dwu rejestrów , zwanych

bazowym i granicznym.Rejestr bazowy

przechowuje najmniejszy dopuszczalny adres fizyczny pamięci ,

rejestr graniczny

zawiera rozmiar

obszaru pamięci. Ochronę taką sprawuje sprzęt jednostki centralnej poprzez porównywanie każdego
adresu wygenerowanego w trybie pracy użytkownika z zawartością opisanych rejestrów.Jakiekolwiek
usiłowanie programu pracującego w trybie użytkownika uzyskania dostępu do pamięci monitora lub
programu innego użytkownika kończy się pułapką w monitorze, który traktuje taki zamiar jako poważny
błąd.
Zawartości

rejestrów - bazowego i granicznego

- mogą być określane przez system operacyjny przy

użyciu specjalnych, uprzywilejowanych rozkazów. Ponieważ rozkazy uprzywilejowane można wykonać
tylko w trybie pracy monitora, a jednocześnie tylko system operacyjny może pracować w tym trybie -
jedynie system operacyjny może załadowac rejestr bazowy i graniczny.

Żeby zagwarantować utrzymanie kontroli przez system operacyjny musimy strzec program użytkownika
przed wpadnięciem w nieskończoną pętlę, gdyż grozi to odebraniem sterowania systemowi operacyjnemu
na zawsze. Osiąga się to przez zastosowanie

czasomierza

( ang.

timer

Czasomierz

mozna tak ustawić ,

aby generował w komputerze przerwanie po wyznaczonym okresie czasu.Okres ten może byc stały (np.
1/60 s) lub zmienny (np. od 1 ms do 1 s , z przyrostami co 1 ms).Odmierzenie zmiennych okresów
implementuje się za pomocą

zegara stałookresowego i licznika

. System operacyjny ustawia licznik.

Przy każdym tyknięciu zegara następuje zmniejszenie licznika. Z chwilą wyzerowania licznika następuje
przerwanie. Dziesięciobitowy licznik z jednomilisekundowym zegarem umożliwia przerwania w
odstępach od 1 do 1024 ms, z przyrostem co 1 ms.
Przed oddaniem sterowania do programu użytkownika system operacyjny dopilnowuje ustawienia
czasomierza na przerwanie. Kiedy czasomierz powoduje przerwane, wtedy sterowanie wraca
automatycznie do systemu operacyjnego, który może uznać to przerwanie za poważny błąd lub
zdecydować o przyznaniu programowi większej ilości czasu. Rozkazy modyfikujące działanie
czasomierza są oczywiście zastrzeżone na użytek monitora.
W ten sposób czasomierz może być użyty do zapobiegania zbyt długiemu działaniu programu
użytkownika .Proste postępowanie polega na zapamiętaniu w liczniku, ile czasu przydziela się
programowi na wykonanie.

2.5 Ogólna architektura systemu

Dążenie do maksymalnego skrócenia czasu instalowania zadań i polepszanie użytkowania systemu
komputerowego doprowadziło, po grupowaniu zadań, buforowaniu i spoolingu do wieloprogramowości i
podziału czasu. Wpłynęło to bezpośrednio na modyfikacje podstawowej architektury komputera
system operacyjny zarządza systemem komputerowym (w tym urządzeniami we wy). Aby nadzór
przebiegał bez kłopotów, zastosowano dualny tryb pracy komputera tryb monitora i tryb użytkownika.
Opiera się to na koncepcji rozkazów uprzywilejowanych (ich wykonywanie jest możliwe tylko w trybie
monitora).

Rozkazy uprzywilejowane:

1. rozkazy WE/WY
2. rozkazy zmieniające zawartość rejestrów zarządzania pamięcią
3. rozkazy zmieniające zawartość rejestrów czasomierza
4. rozkaz HALT (zatrzymaj)
5. rozkazy włączania i wyłączania systemu przerwań
6. rozkaz przejścia z trybu użytkownika do trybu monitora
7. jakakolwiek zmiana bitu trybu pracy

Rozkazy WE/WY mogą być wykonywane tylko przez system operacyjny. Aby użytkownik mógł
wykonać operację WE/WY musi poprosić monitor, aby ten wykonał taką operację rozkaz odwołania
do systemu. Rozkaz ten jest traktowany przez sprzęt jak przerwanie programowe. Za pomocą wektora
przerwań sterowanie jest przekazywane do odpowiedniej procedury obsługi w systemie operacyjnym, a
bit trybu zostaje przełączony w tryb monitora. Procedura odwołania się do systemu jest funkcją systemu
operacyjnego. Monitor sprawdza rozkaz przerywający i określa wystąpienie odwołania do systemu
rodzaj obsługi na jaką użytkownik zgłasza zapotrzebowanie określa parametr odwołania do systemu, a
dodatkowe informacje potrzebne w związku z zamówieniem mogą być przekazane za pomocą rejestrów,
albo pamięci. System operacyjny sprawdza poprawność polecenia.

2.6 Różne klasy komputerów.

2.6.1 Systemy wieloprocesorowe

System jednoprocesorowy tylko jedna jednostka centralna.

System wieloprocesorowy ścisła współpraca kilku procesorów, dzieląc szynę komputera, a czasami
pamięć i urządzenia zewnętrzne.

Powody stosowania systemów wieloprocesorowych:

1. Zwiększenie przepustowości większa ilość pracy da się wykonać w krótszym czasie. Część

czasu jest jednak tracona na utrzymanie jednego działania w całości. W połączeniu z rywalizacją o
zasoby dzielone, obniża to oczekiwany zysk z zastosowania większej ilości procesorów.

2. Niezawodność umiejętne rozdzielenie zadań między kilka procesorów powoduje, że awaria

jednego z procesorów, nie zatrzymuje systemu, a tylko go spowalnia.

Kontynuowanie działania niezależnie od uszkodzeń wymaga mechanizmów ich wykrywania,
diagnozowania i naprawy. Obecnie stosuje się model wieloprzetwarzania symetrycznego, w którym w
każdym procesorze działa identyczna kopia systemu operacyjnego. Kopie te komunikują się ze sobą w
razie potrzeby (przykładem może być system UNIX, wersja Encore). Czasami stosuje się
wieloprzetwarzanie asymetryczne każdy procesor ma przypisane inne zadanie , a systemem zawiaduje
procesor główny. Inne procesory albo oczekują na instrukcję od procesora głównego, albo wykonują inne
działania, określone uprzednio. Wieloprzetwarzanie asymetryczne częściej występuje w bardzo wielkich
systemach, w których czynnościami zużywającymi najwięcej czasu są operacje WE/WY.

2.6.2 Komputery osobiste

Syf nie ma o czym pisać...

3. Struktury systemów operacyjnych

System operacyjny tworzy środowisko, w którym są wykonywane programy
Aby skonstruować takie środowisko, system operacyjny dzieli się logicznie na
małe moduły i tworzy dobrze określony interfejs z wykonywanymi programami.

Systemy operacyjne znacznie różnią się między sobą pod względem organizacji wewnętrznej.

3.1. Składowe systemu

System tak wielki i złożony jak system operacyjny można utworzyć tylko wówczas, gdy podzieli się go
na mniejsze części. Każda z takich części powinna stanowić dobrze zdefiniowany fragment systemu, ze
starannie określonym wejściem, wyjściem i funkcjami.

3.1.1. Zarządzanie procesami

Jednostka centralna wykonuje wielką liczbę programów oraz spełnia też inne zadania systemu zwane
procesami. Proces to program, który jest wykonywany. W myśl tego - zadanie wsadowe jest procesem.
Program użytkownika wykonywany w systemie z podziałem czasu też jest procesem. Procesem jest
również zadanie systemowe jak na przykład spooling.

Na ogół, aby móc wypełnić swoje zadania, proces musi korzystać z pewnych zasobów, takich jak czas
jednostki centralnej, pamięć, pliki i urządzenia wejścia wyjścia. Zasoby te proces otrzymuje w chwili
jego utworzenia albo są one przydzielane procesowi podczas jego działania. Jako uzupełnienie
rozmaitych zasobów fizycznych i logicznych, które proces dostaje w chwili powstania, może on również
otrzymać pewne dane początkowe (wejściowe).

Program sam w sobie nie jest procesem. Program jest pasywny, tak jak zawartość pliku
przechowywanego na dysku. Natomiast proces jest jednostką aktywną, której licznik rozkazów określa
następną instrukcję do wykonania. Wykonanie procesu musi przebiegać w sposób sekwencyjny. Mimo iż
z jednym i tym samym programem mogą być związane dwa procesy, zawsze będzie się je rozważać jako
dwa oddzielne ciągi wykonywanych instrukcji

Proces stanowi jednostkę pracy w systemie. W takim ujęciu system składa się ze zbioru procesów, z
którym część to procesy systemu operacyjnego (te, które wykonują kod systemu), pozostałe zaś są
procesami użytkownika (wykonującymi kod określony przez użytkownika). Wszystkie procesy
potencjalnie mogą być wykonywane współbieżnie na zasadzie multipleksowania między nimi procesora
centralnego.

W odniesieniu do zarządzania procesami system operacyjny odpowiada za następujące czynności:



tworzenie i usuwanie zarówno procesów użytkowych, jak systemowych;



wstrzymywanie i wznawianie procesów,



dostarczanie mechanizmów synchronizacji procesów,



dostarczanie mechanizmów komunikacji procesów,



dostarczanie mechanizmów obsługi blokad.

3.1.2. Zarządzanie pamięcią operacyjną

Pamięć operacyjna odgrywa centralną rolę w działaniu współczesnego systemu komputerowego. Pamięć
ta jest wielką tablicą słów lub bajtów, której każdy element ma przypisany adres. Stanowi ona magazyn
szybko dostępnych danych eksploatowanych wspólnie przez jednostkę centralną i urządzenia wejścia-
wyjścia. Podczas wykonywania cyklu pobierania rozkazów procesor centralny czyta je z pamięci
operacyjnej; także podczas wykonywania cyklu pobierania danych procesor czyta i zapisuje dane do tej
pamięci. Operacje wejścia-wyjścia dokonywane za pośrednictwem metody DMA również używają
pamięci operacyjnej do odczytywania i zapisywania danych. Pamięć operacyjna jest w zasadzie jedyną
pamięcią, która jednostka centralna może adresować bezpośrednio. W przypadku innych rodzajów
pamięci, na przykład pamięci dyskowej, aby przetwarzać znajdujące się w nich dane, procesor musi
najpierw sprowadzić je do pamięci operacyjnej za pomocą odpowiednich operacji wejścia-wyjścia.
Zupełnie podobnie, aby jednostka centralna mogła wykonywać instrukcje, muszą one znajdować się w tej
pamięci .

Aby program mógł być wykonany, musi być zaadresowany za pomocą adresów bezwzględnych oraz
załadowany do pamięci. Podczas wykonywania programu rozkazy i dane są pobierane z pamięci za
pomocą generowania tych właśnie adresów bezwzględnych. Kiedy program zakończy działanie, wtedy
jego miejsce w pamięci jest oznaczane jako wolne, co umożliwia załadowanie i wykonanie następnego
programu.

Jeśli chcemy uzyskać zarówno lepsze wykorzystanie jednostki centralnej, jak i szybszą reakcję komputera
na polecenia jego użytkowników, to musimy przechowywać kilka programów w pamięci operacyjnej.

Wybór sposobu zarządzania pamięcią zależy od wielu czynników, a zwłaszcza od cech sprzętu, w którym
działa dany system. Każdy algorytm wymaga swoistego wspomagania sprzętowego.

W odniesieniu do zarządzania pamięcią system operacyjny odpowiada za następujące czynności:



utrzymywanie ewidencji aktualnie zajętych części pamięci wraz z informacją, w czyim są
władaniu;



decydowanie o tym, które procesy mają być załadowane do zwolnionych obszarów pamięci;



przydzielanie i zwalnianie obszarów pamięci stosownie do potrzeb.

3.1.3. Zarządzanie pamięcią pomocniczą

Podstawowym zadaniem systemu komputerowego jest wykonywanie programów. Podczas wykonywania
programy oraz używane przez nie dane muszą znajdować się w pamięci operacyjnej. Pamięć ta jest
jednak za mała, aby nieustannie mieścić wszystkie dane i programy. System komputerowy musi zatem
mieć dodatkową pamięć pomocniczą, stanowiącą zaplecze dla pamięci operacyjnej. Większość
współczesnych systemów komputerowych posługuje się pamięcią dyskową jako podstawowym środkiem
magazynowania zarówno danych, jak i programów. Większość programów - w tym kompilatory,
asemblery, procedury sortujące, edytory i pogramy formatujące - do czasu ładowania do pamięci jest
przechowywana na dysku oraz używa dysków jako źródeł i miejsc przeznaczenia przetwarzanych przez
nie danych. Dlatego jest niezwykle ważne, aby zarządzanie pamięcią dyskową w systemie
komputerowym odbywało się w sposób właściwy.

W odniesieniu do zarządzania dyskami system operacyjny odpowiada za następujące czynności:



zarządzanie obszarami wolnymi;



przydzielanie pamięci;



planowanie przydziałów obszarów pamięci dyskowej.

3.1.4. Zarządzanie systemem wejścia-wyjścia

Jednym z celów systemu operacyjnego jest ukrywanie przed użytkownikiem szczegółów dotyczących
specyfiki urządzeń sprzętowych. Na przykład w systemie Unix osobliwości urządzeń wejścia-wyjścia są
ukrywane przed większością samego systemu operacyjnego przez tzw. system wejścia-wyjścia. System
ten składa się z:



systemu buforowo notatnikowego;



ogólnego interfejsu do programów obsługi poszczególnych urządzeń sprzętowych;



programów obsługi poszczególnych urządzeń sprzętowych.

Osobliwości konkretnego urządzenia sprzętowego zna tylko odpowiadający mu program obsługi.

3.1.5. Zarządzanie plikami

Zarządzanie plikami jest jedną z najbardziej widocznych części składowych systemu operacyjnego.
Komputery mogą przechowywać informację w kilku postaciach różnych pod względem fizycznym.
Najbardziej rozpowszechnione są



taśmy,



dyski magnetyczne,



dyski optyczne.

Dla wygody użytkowania systemu komputerowego system operacyjny tworzy logicznie jednolity obraz
magazynowanej informacji. System operacyjny definiuje pliki, czyli jednostki logiczne przechowywanej
informacji, niezależne od fizycznych właściwości używanych urządzeń pamięciowych. System
operacyjny musi zatem odwzorowywać pliki na urządzenia fizyczne.

Plik jest zbiorem powiązanych ze sobą informacji, zdefiniowanych przez jego twórcę. W plikach
zazwyczaj przechowuje się programy (zarówno w postaci źródłowej, jak i wynikowej) oraz dane. Pliki
danych mogą być liczbowe, tekstowe lub alfanumeryczne. Format plików może być swobodny, jak w
przypadku plików tekstowych lub ściśle określony. Zawartość pliku można traktować jako ciąg bitów,
bajtów, wierszy lub rekordów, których znaczenie zależy od twórcy pliku.

System operacyjny realizuje abstrakcyjną koncepcję plików przez zarządzanie urządzeniami pamięci
masowych, takimi jak taśmy lub dyski.

W odniesieniu do zarządzania plikami system operacyjny odpowiada za następujące czynności:



tworzenie i usuwanie plików;



tworzenie i usuwanie katalogów;



dostarczanie elementarnych operacji do manipulowania plikami i katalogami;



odwzorowywanie plików na obszary pamięci pomocniczej;



składowanie plików na małych nośnikach pamięci (na których informacja nie zanika).

3.1.6. System ochrony

Liczne procesy w systemie operacyjnym muszą być chronione przed wzajemnym oddziaływaniem.
Muszą istnieć mechanizmy gwarantujące, że pliki, segmenty pamięci, procesor i inne zasoby będą
użytkowane tylko przez te procesy, które zostały przez system operacyjny odpowiednio uprawnione.

Ochrona jest mechanizmem nadzorowania dostępu programów, procesów lub użytkowników do zasobów
zdefiniowanych przez system komputerowy. Mechanizm ten musi zawierać sposoby określania, co i
jakiej ma podlegać ochronie, jak również środki do wymuszenia zaprowadzonych ustaleń.

Ochrona może zwiększać rzetelność działania systemu, poszukując błędów ukrytych w interfejsach
między składowymi podsystemami. Wczesne wykrywanie błędów w interfejsach może często zapobiec
zanieczyszczeniu zdrowego podsystemu przez uszkodzony podsystem. Zasoby, które nie są chronione,
nie mogą obronić się przez ich użyciem (lub nadużyciem) przez nieupoważnionego lub
niekompetentnego użytkownika.

3.1.7. Praca sieciowa

System rozproszony jest zbiorem procesów, które nie korzystają ze wspólnej pamięci ani zegara. W
zamian każdy procesor ma własną, lokalną pamięć i komunikuje się z innymi procesorami za pomocą
różnorodnych linii komunikacyjnych, takich jak szybkie szyny danych lub linie telefoniczne. Procesory w
systemie rozproszonym są zróżnicowane pod względem wielkości i funkcji. Mogą być wśród nich małe
mikroprocesory, stacje robocze, minikomputery oraz wielkie systemy komputerowe ogólnego
przeznaczenia.

Procesory w systemie rozproszonym są połączone za pomocą sieci komunikacyjnej, która może być
skonfigurowana na kilka różnych sposobów. Sieć może mieć połączenia pełne lub częściowe. System
rozproszony umożliwia użytkownikowi dostęp do różnych zasobów zgromadzonych w systemie. Dostęp
do zasobów dzielonych pozwala przyśpieszać obliczenia, zwiększa osiągalność danych i pewność
działania. Systemy operacyjne są zazwyczaj uogólnieniem dostępu sieciowego jako pewnej postaci
dostępu do plików, przy czym szczegóły komunikacji sieciowej są zawarte w programie obsługi
urządzenia sprzęgającego z siecią.

3.1.8. System interpretacji poleceń

Jednym z najważniejszych programów w systemie operacyjnym jest interpretator poleceń. Niektóre
systemy operacyjne, zwłaszcza mikrokomputerowe, jak MS-DOS lub system Macintosh firmy Apple,
zawierają interpretator poleceń w swoim jądrze. W innych systemach operacyjnych, na ogół pracujących
w większych komputerach, interpretator poleceń jest specjalnym programem wykonywanym przy
inicjowaniu zadania lub wtedy, gdy użytkownik rejestruje się w systemie (z podziałem czasu).

Wiele żądań jest przekazywanych do systemu operacyjnego za pomocą instrukcji sterujących. W chwili
startu nowego zadania w systemie wsadowym lub zarejestrowania się użytkownika w systemie
konwersacyjnym, automatycznie zaczyna pracować program interpretujący instrukcje sterujące. Program
ten bywa nazywany rozmaicie: interpretator kart sterujących, interpretator wierszy poleceń, shell (w
Unixie) itp. Jego zadanie jest proste - ma pobrać następną instrukcję i ją wykonać.

Systemy operacyjne często różnią się pod względem sposobu interpretowania poleceń. Np. interpretator
systemu Macintosh pozwala korzystać z okien i menu prawie wyłącznie za pośrednictwem myszy.
Użytkownik, manewrując myszą, wskazuje na ekranie za pomocą kursora obrazki (ikony) reprezentujące
programy, pliki i funkcje systemowe. Zależnie od położenia kursora, naciskając odpowiedni przycisk
myszy można wywołać program, wybrać plik lub katalog (zwany tu kartoteką) lub rozwinąć pole menu
zawierającego polecenia. Bogatsze w możliwości, bardziej złożone i trudniejsze do opanowania
interpretatory cieszą się uznaniem w gronie bardziej doświadczonych użytkowników. Polecenia pisze się
za pomocą klawiatury z równoczesnym wyświetleniem ich na monitorze ekranowym lub drukowaniem.
Do sygnalizacji, że polecenie .jest kompletne i gotowe do wykonania, służy klawisz Enter ( lub Return).
W tym trybie pracuje program shell systemu Unix.

Polecenia rozpoznawane przez interpretator dotyczą: zarządzania procesami, obsługi wejścia-wyjścia,
administrowania pamięcią pomocniczą i operacyjną, dostępu do plików, ochrony zasobów i pracy
sieciowej.

3.2. Usługi systemu operacyjnego

System operacyjny tworzy środowisko, w którym są wykonywane programy.

Dostarcza on pewnych usług zarówno programom, jak i użytkownikom tych programów. Wśród nich
można wyodrębnić pewne wspólne klasy. Usługi te pomyślano dla wygody programisty, aby ułatwić jego
pracę nad programem.



Wykonanie programu

System powinien móc załadować program do pamięci i rozpocząć jego wykonywanie. Program powinien
móc zakończyć swą pracę w sposób normalny lub z przyczyn wyjątkowych.



Operacje wejścia wyjścia

Wykonywany program może potrzebować wyników operacji wejścia-wyjścia odnoszących się do pliku
lub do jakiegoś urządzenia. Poszczególne urządzenia mogą wymagać specyficznych funkcji (jak zwijanie
taśmy na przewijaku lub wyczyszczenie ekranu monitora). Ponieważ program użytkownika nie może
wykonywać operacji wejścia-wyjścia bezpośrednio, więc środki do realizacji tych czynności musi mieć
system operacyjny.



Manipulowanie systemem plików

System plików ma znaczenie szczególne. Nie ulega wątpliwości, że programy muszą zapisywać i
odczytywać pliki. Jest im również potrzebna możliwość tworzenia i usuwania plików przy użyciu ich
nazw.



Komunikacja

Są dwie podstawowe metody organizowania komunikacji. Pierwszą stosuje się w przypadku procesów
działających w tym samym komputerze; druga znajduje zastosowanie przy komunikowaniu się procesów
wykonywanych w różnych systemach komputerowych, powiązanych ze sobą za pomocą sieci
komputerowej. Komunikacja może przebiegać za pomocą pamięci dzielonej lub przy użyciu mniej
ogólnej techniki przekazywania komunikatów, w której pakiety informacji są przemieszczane między
procesami za pośrednictwem systemu operacyjnego.



Wykrywanie błędów

System operacyjny powinien być nieustannie powiadamiany o występowaniu błędów. Błędy mogą się
pojawiać w działaniu jednostki centralnej i pamięci (sprzętowa wada pamięci Iub awaria zasilania), w
urządzeniach wejścia-wyjścia (np. błąd parzystości na taśmie, zacięcie się czytnika kart albo brak papieru
w drukarce) lub w programie użytkownika (np. nadmiar arytmetyczny, próba sięgnięcia poza obszar
pamięci programu lub przekroczenia przydzielonego procesora}. Na wszystkie rodzaje błędów system
operacyjny powinien odpowiednio reagować, gwarantując poprawność i spójność obliczeń.

Istnieje jeszcze dodatkowy zbiór funkcji systemu operacyjnego, które nie są przeznaczone do pomagania
użytkownikowi, lecz do optymalizacji działania samego systemu. Systemy pracujące dla wielu
użytkowników mogą zyskiwać na efektywności dzięki podziałowi zasobów komputera pomiędzy
użytkowników.



Przydział zasobów

Jeżeli wielu użytkowników i wiele zadań pracuje w tym samym czasie, to każdemu z nich muszą być
przydzielane zasoby. System operacyjny zarządza różnego rodzaju zasobami. Przydzielanie niektórych z
nich (jak cykli procesora pamięci operacyjnej oraz pamięci plików) wymaga odrębnego kodu, podczas,
gdy inne (jak urządzenia wejścia-wyjścia) mogą mieć znacznie ogólniejszy kod zamawiania i zwalniania.
Na przykład do określenia najlepszego wykorzystania jednostki centralnej służą systemowi operacyjnemu
procedury planowania przydziału jednostki centralnej w zależności od: szybkości procesora, zadań
czekających na wykonanie, liczby dostępnych rejestrów i innych czynników. Mogą też istnieć procedury
przydzielania przewijaka taśmy dla zadania. Procedura tego rodzaju odnajduje wolny przewijak i
odnotowuje w wewnętrznej tablicy, że przydzielono go nowemu użytkownikowi. Do wymazania tej
informacji w tablicy przydziałów wywołuje się inną procedurę. Takie procedury mogą być również
wywołane do przydzielania ploterów, modemów i innych urządzeń zewnętrznych.



Rozliczanie

Przechowywanie danych o tym, którzy użytkownicy, w jakim stopniu korzystają z poszczególnych
zasobów komputera, jest kolejnym zadaniem systemu operacyjnego. Przechowywanie takich rekordów
może służyć do rozliczania (aby można było wystawiać użytkownikom rachunki) lub po prostu do
gromadzenia informacji w celach statystycznych.



Ochrona

Właściciele informacji przechowywanej w systemie skupiającym wielu użytkowników mogą chcieć
kontrolować jej wykorzystanie. Gdy kilka oddzielnych badań jest wykonywanych równocześnie,
wówczas jedno zadanie nie może zaburzać pracy innych zadań lub samego systemu operacyjnego.
Ochrona obejmuje sprawdzenie poprawności wszystkich parametrów przekazywanych w wywołaniach
systemowych i gwarantuje nadzór nad dostępem do wszystkich zasobów systemu. Niemniej ważne jest
zabezpieczenie systemu przed niepożądanymi czynnikami zewnętrznymi. Zabezpieczenia tego rodzaju
rozpoczynają się od tego, że użytkownicy muszą podawać swoje hasła, aby uzyskać dostęp do zasobów.
Dalszym rozszerzeniem zabezpieczeń jest obrona zewnętrznie zlokalizowanych urządzeń wejścia-
wyjścia, w tym modemów i adapterów sieciowych, przed usiłowaniami niedozwolonego dostępu i
rejestrowanie wszystkich takich przypadków w celu wykrywania włamań.

3.3. Funkcje systemowe

Funkcje systemowe (ang. system calls) tworzą interfejs między wykonywanym programem a systemem
operacyjnym. Można z nich korzystać za pomocą instrukcji w języku asemblera. Ich wykazy znajdują się
zazwyczaj w podręcznikach używanych przez programujących w języku asemblera.

Niektóre systemy umożliwiają wywoływanie funkcji systemowych bezpośrednio w programie napisanym
w języku wyższego poziomu. W tym przypadku wywołania funkcji systemowych są podobne do
wywołań funkcji standardowych lub podprogramów.

W większości języków programowania systemy wspomagania i wykonania programu tworzą znacznie
prostsze interfejsy. Na przykład instrukcja write w Pascalu lub analogiczna w Fortranie
najprawdopodobniej zostanie przełożona na wywołanie procedury wspomagania wykonania programu,
która spowoduje wykonanie niezbędnych funkcji systemowych, sprawdzi, czy wystąpiły błędy, po czym
powróci do programu użytkownika.

W ten sposób dzięki kompilatorowi większość drobiazgowych czynności systemu operacyjnego pozostaje
ukryta przed programistą piszącym programy użytkowe. Postać wywołania funkcji systemowych zależy
od komputera. Zazwyczaj oprócz symboli identyfikujących daną funkcję systemową są potrzebne
dodatkowe informacje. Dokładny wzorzec i ilość informacji zmienia się w zależności od systemu
operacyjnego i wywoływanej funkcji.

Istnieją zasadniczo trzy metody przekazywania parametrów do systemu operacyjnego. Najprostsza polega
na umieszczeniu parametrów w rejestrach jednostki centralnej. W niektórych przypadkach może być
jednak więcej parametrów niż rejestrów. Wówczas parametry przechowuje się w bloku lub tablicy w
pamięci, adres zaś tego bloku przekazuje się jako parametr za pośrednictwem rejestru. Parametry można
również przekazywać lub składać na stosie za pomocą programu, skąd będą zdejmowane przez system
operacyjny. W pewnych systemach operacyjnych dano pierwszeństwo metodom bloków lub stosu,
ponieważ nie ograniczają one liczby ani długości przekazywanych parametrów.

Funkcje systemowe można z grubsza podzielić na pięć podstawowych kategorii: nadzorowanie procesów,
operacje na plikach, operacje na urządzeniach, utrzymywanie informacji oraz komunikacja.

1. Nadzorowanie procesów



zakończenie, zaniechanie;



załadowanie, wykonanie;



utworzenie procesu, zakończenie procesu;



pobranie atrybutów procesu, określenie atrybutów procesu;



czekanie czasowe;



oczekiwanie na zdarzenie, sygnalizacja zdarzenia;



przydział i zwolnienie pamięci.

1. Operacje na plikach



utworzenie pliku, usunięcie pliku;



otwarcie, zamknięcie;



czytanie, pisanie, zmiana położenia;



pobranie atrybutów pliku, określenie atrybutów pliku;

1. Operacje na urządzeniach



zamówienie urządzenia, zwolnienie urządzenia;



czytanie, pisanie, zmiana położenia;



pobranie atrybutów urządzenia, określenie atrybutów urządzenia;



logiczne przyłączanie lub odłączanie urządzeń;

1. Utrzymywanie informacji



pobranie czasu lub daty, określenie czasu lub daty;



pobranie danych systemowych, określenie danych systemowych;



pobranie atrybutów procesu, pliku lub urządzenia, określenie atrybutów procesu, pliku lub
urządzenia;

1. Komunikacja



utworzenie, usunięcie połączenia komunikacyjnego;



nadawanie, odbieranie komunikatów;



przekazanie informacji o stanie;



przyłączenie lub odłączenie urządzeń wymiennych.

3.3.1. Nadzorowanie procesów i zadań

Wykonywany program powinien móc zakończyć się w sposób normalny lub wyjątkowy Jeżeli jest
wykonywana funkcja systemowa, która powoduje nagłe zakończenie bieżącego programu Iub jeśli
działanie wykonania programu zmierza do pułapki związanej z błędem, to wykonuje się niekiedy zrzut
zawartości pamięci, po czym jest generowany sygnał błędu. Niezależnie od tego, czy powstała sytuacja
jest normalna czy też nie, system operacyjny musi przekazać sterowanie do interpretatora poleceń, który
czyta wówczas następne polecenie. W systemie interakcyjnym interpretator poleceń po prostu wykonuje
następne polecenie; zakłada się, że użytkownik wyda właściwe polecenie w odniesieniu do dowolnego
błędu. W systemie wsadowym interpretator poleceń musi zazwyczaj zaprzestać wykonywania całego
zadania i przystąpić do wykonywania następnego zadania. Niektóre systemy pozwalają na stosowanie
kart sterujących ze wskazówkami określającymi postępowanie w przypadku wystąpienia błędu. Jeśli
program wykryje w swoich danych wejściowych błąd zmuszający go do awaryjnego zatrzymania, to
może również chcieć określić poziom błędu. Poważniejsze błędy można sygnalizować za pomocą
większych wartości parametru poziomu błędu. Można bowiem ujednolicić zatrzymania normalne i
awaryjne w ten sposób, że zatrzymanie normalne definiuje się jako mające poziom błędu równy 0.

Interpretator poleceń Iub następny wykonywany program mogą posłużyć się uzyskanym poziomem błędu
do podjęcia automatycznej decyzji o dalszym postępowaniu.

Proces Iub zadanie wykonujące jakiś program może spowodować załadowanie i wykonanie innego
programu. Interpretator poleceń rozpoczyna wykonywanie takiego nowego programu zupełnie tak samo,
jak gdyby zostało to nakazane przez polecenie użytkownika, wsadową instrukcją sterującą Iub w wyniku
naciśnięcia klawisza myszy. Jeśli po zakończeniu nowego programu sterowanie ma powrócić do
poprzedniego programu, to musimy przechować obraz pamięci pierwszego programu. Uzyskamy dzięki
temu efektywny mechanizm wywoływania jednego programu z wnętrza innego programu. Natomiast gdy
oba programy pracują współbieżnie, wówczas otrzymujemy nowe zadanie Iub proces, który trzeba
uwzględnić w algorytmie wieloprogramowości. Służy do tego zazwyczaj specjalna funkcja systemowa
(utworzenie procesu Iub zadania).

Jeśli utworzymy nowe zadanie Iub proces - albo nawet zbiór zadań Iub procesów - to powinniśmy móc
wpływać na jego wykonanie. Wymaga to możliwości określania i ustalania wartości początkowych
atrybutów zadania Iub procesu, w tym priorytetu zadania, maksymalnego czasu przeznaczonego na jego
wykonanie itd. (pobranie atrybutów procesu, określenie atrybutów procesu). Możemy również chcieć
zakończyć wykonanie utworzonego zadania Iub procesu, jeśli okaże się, że są niepoprawne Iub już
niepotrzebne.

Po utworzeniu nowych zadań Iub procesów możemy chcieć poczekać na ich zakończenie. Może to być
czekanie przez określony czas lub na określone zdarzenie. Zadania Iub procesy powinny w związku z tym
sygnalizować występowanie zdarzeń.

Odrębny zbiór funkcji systemowych jest pomocny przy sprawdzaniu poprawności programów. W wielu
systemach są funkcje systemowe umożliwiające wykonywanie zrzutów zawartości pamięci. Jest to
przydatne przy sprawdzaniu poprawności programów napisanych w języku asemblerowym Iub
maszynowym, zwłaszcza w systemach wsadowych. Ślad działania programu rejestruje ciąg instrukcji w
kolejności ich wykonywania; możliwość taką ma mniej systemów. Nawet w mikroprocesorach istnieje
tryb pracy jednostki centralnej, zwany jednokrokowym, w którym procesor po wykonaniu każdej
instrukcji wchodzi w tryb obsługi specjalnej pułapki. Pułapka taka jest zwykle przechwytywana przez
systemowy program uruchomieniowy pomagający programiście lokalizować i usuwać błędy.

Wiele systemów umożliwia oglądanie profilu czasowego programu. Profil czasowy ukazuje, ile czasu
spędza program w poszczególnych komórkach lub grupach komórek. Sporządzenie profilu czasowego
wymaga możliwości śledzenia programu Iub istnienia regularnych przerwań zegarowych. Po każdym
wystąpieniu przerwania zegarowego jest zapamiętywany stan licznika rozkazów programu. Przy
odpowiednio częstych przerwaniach zegarowych można otrzymać statystyczny obraz czasu zużywanego
przez różne części programu.

Sterowanie procesami i zadaniami ma wiele aspektów i odmian. System operacyjny MS-DOS jest
przykładem systemu jednozadaniowego z interpretatorem poleceń wywoływanym na początku pracy
komputera. Ponieważ MS-DOS jest jednozadaniowy, używa prostej metody wykonywania programu, nie
powodującej tworzenia nowego procesu. System wprowadza program do pamięci operacyjnej, nawet
kosztem większej części własnego kodu, aby zapewnić programowi możliwie jak najwięcej przestrzeni.
Następnie ustawia licznik rozkazów na pierwszą instrukcję programu. Program rozpoczyna działanie, w
którego wyniku albo wystąpi błąd i uaktywni się odpowiednia pułapka systemowa, albo program
zatrzyma się, wykonując odpowiednią funkcję systemową. W obu przypadkach kod błędu zostanie
przechowany w pamięci systemu do późniejszego użytku. Po wykonaniu tych czynności wznawia
działanie mały fragment interpretatora poleceń, który nie został zniszczony przez kod programu.
Najpierw powtórnie ładuje z dysku resztę swojego kodu, a po zakończeniu tej czynności - już jako pełny
interpretator poleceń - udostępnia ostatni kod błędu użytkownikowi Iub następnemu programowi.

3.3.2. Działania na plikach

Istnieje kilka głównych funkcji systemowych dotyczących plików.

Należy móc tworzyć i usuwać pliki. Każde wywołanie funkcji systemowej wymaga podania nazwy pliku
i, być może, jakichś jego atrybutów. Potrzebne będą również operacje czytania i pisania oraz zmiany
punktu odniesienia w pliku - na przykład przewijanie Iub przeskakiwanie na koniec pliku. Do
zaznaczenia, że plik nie będzie więcej używany, będzie wymagana operacja zamknięcia pliku. Jeśli
system plików zawiera strukturę katalogów, to będzie potrzebny taki sam zbiór operacji dla katalogów. W
dodatku, zarówno dla plików, jak i dla katalogów należy określać wartości różnych atrybutów, a nie
wykluczone, że i nadawać im wartości początkowe. Do atrybutów pliku zalicza się nazwę pliku, typ
pliku, kody zabezpieczające, informacje używane do rozliczania użytkownika itd. Potrzebne są do tego
celu dwie funkcje systemowe: pobrania atrybutu pliku i określenia atrybutu pliku.

3.3.3. Zarządzanie urządzeniami

Wykonywany program może potrzebować dodatkowych zasobów: zwiększenia przydzielonej pamięci,
udostępnienia plików Iub przewijaków taśm itd. Jeżeli te zasoby są dostępne, to będą mu przyznane i
sterowanie powróci do programu użytkownika; w przeciwnym razie program musi czekać dopóty, dopóki
nie będzie wystarczającej ilości zasobów. Pliki można rozumieć jako abstrakcyjne Iub wirtualne
urządzenia. Wiele zatem funkcji systemowych dla plików może mieć także zastosowanie w przypadku
urządzeń. Jeżeli system ma wielu użytkowników, to należy najpierw poprosić o urządzenie, aby zapewnić
sobie wyłączność jego użytkowania. Po skończeniu użytkowania urządzenia, należy je zwolnić. Te
czynności są podobne do systemowego otwierania i zamykania plików. Po zażądaniu przydziału
urządzenia (i uzyskaniu go ), do urządzenia można odnosić operacje czytania, pisania i (być może)
zmiany położenia nośnika danych - jak w operacjach na plikach. Podobieństwo między urządzeniami
wejścia-wyjścia i plikami jest tak duże, że wiele systemów operacyjnych łączy je w jedną strukturę
plików-urządzeń; urządzenia wejścia-wyjścia są wówczas rozpoznawane jako pliki o specjalnych
nazwach.

3.3.4. Utrzymywanie informacji

Wiele funkcji systemowych istnieje tylko w celu przesyłania informacji między

programem użytkownika a systemem operacyjnym. Na przykład większość systemów ma funkcję
systemową przekazującą bieżący czas i datę. Inne funkcje systemowe mogą przekazywać informacje o
systemie, takie jak liczbę bieżących użytkowników, numer wersji systemu operacyjnego, ilość wolnej
pamięci Iub miejsca na dysku itd.

System operacyjny przechowuje ponadto informacje o wszystkich swoich zadaniach i procesach oraz
zawiera funkcje systemowe udostępniające te informacje (pobranie atrybutów procesu). Są także funkcje
operujące na ich stanie ( określenie atrybutów procesu).

3.3.5. Komunikacja

Są dwa główne modele komunikacji. W modelu przesyłania komunikatów informacja jest wymieniana
przez międzyprocesowe środki komunikacji, które dostarcza system operacyjny. Przed rozpoczęciem
komunikacji należy nawiązać połączenie. Musi być znana nazwa odbiorcy; może być nim inny proces w

tej samej jednostce centralnej lub proces w innym komputerze. Każdy komputer w sieci ma swoją nazwę
sieciową, która go identyfikuje. Podobnie, każdy proces ma swoją nazwę procesu, tłumaczoną na
równoważny identyfikator, za którego pomocą system operacyjny odwołuje się do procesu.
Odpowiednich tłumaczeń dokonują funkcje systemowe pobrania nazwy sieciowej i pobrania nazwy
procesu. Uzyskane identyfikatory są potem parametrami ogólnych funkcji systemowych otwierania i
zamykania plików Iub specyficznych funkcji systemowych otwierania połączenia i zamykania
połączenia. Proces odbiorcy musi zazwyczaj udzielić zgody na nawiązania komunikacji za pomocą
funkcji akceptującej połączenie. Większość procesów realizujących połączenia stanowią tzw. demony
(czyli inspirujące do działania dobre duszki opiekuńcze - uwzględniając barwę znaczenia wyrazu demon),
będące przeznaczonymi specjalnie do tego celu programami systemowymi. Wywołują one funkcję
czekania na połączenie i są wtedy budzone, gdy połączenie zostanie nawiązane. Źródło komunikacji,
nazywane klientem, i demon odbiorcy, nazywany systemem obsługi wymieniają wówczas komunikaty za
pomocą funkcji systemowych czytania komunikatu i pisania komunikatu. Wywołanie funkcji zamknięcia
połączenia kończy komunikację.

W modelu pamięci dzielonej procesy posługują się systemowymi funkcjami odwzorowania pamięci, aby
uzyskać dostęp do obszarów pamięci należących do innych procesów. System operacyjny na ogół próbuje
zapobiegać dostawaniu się jednego procesu do pamięci innego procesu. Dzielenie pamięci wymaga, aby
dwa lub więcej procesów zgodziło się na usunięcie tego ograniczenia. W następstwie tego procesy mogą
wymieniać informacje przez czytanie i pisanie do współużytkowanych obszarów. Procesy określają
postać danych i ich miejsce w pamięci - nie podlega to kontroli systemu operacyjnego. Procesy muszą
także dopilnować, aby nie pisały jednocześnie do tego samego miejsca.

Obydwa modele komunikacji występują w systemach operacyjnych, czasami nawet równocześnie.
Przesyłanie komunikatów jest przydatne do bezkonfliktowej wymiany mniejszych ilości danych. Jest
także łatwiejsze do zrealizowania w komunikacji rniędzykomputerowej niż metoda pamięci dzielonej.
Pamięć dzielona daje maksymalną prędkość i wygodę komunikacji, która może przebiegać z prędkością
działania pamięci. Metoda ta jest jednak obarczona problemami ochrony obszarów pamięci i
synchronizacji działań.

3.4. Programy systemowe

Programy systemowe tworzą wygodniejsze środowisko do opracowywania i wykonywania innych
programów. Można je podzielić na kilka kategorii:



Manipulowanie plikami

Należą tu programy, które służą do tworzenia, usuwania, kopiowania, przemianowywania, składowania i
wyprowadzania zawartości plików bądź katalogów, mówiąc ogólnie - do wykonywania działań na
plikach i katalogach.



Informowanie o stanie systemu

Pewne programy po prostu pobierają z systemu dane określające datę, czas, ilość dostępnej pamięci Iub
miejsca na dysku, liczbę użytkowników Iub podobne informacje o stanie systemu i komputera. Uzyskana
informacja jest potem formatowana i drukowana na terminalu Iub innych urządzeniach wyjściowych,
względnie posyłana do plików.



Tworzenie i zmienianie zawartości plików

Rozmaite odmiany edytorów służą do tworzenia plików na taśmach Iub

dyskach i zmieniania ich zawartości.



Translatory języków programowania

W skład systemu operacyjnego wchodzą często kompilatory, asemblery oraz

interpretatory popularnych języków programowania (takich jak : Fortran,

Cobol, Pascal, Basic, C, Lisp itd.).



Komunikacja

W tej grupie znajdują się programy realizujące mechanizmy tworzenia wirtualnych połączeń miedzy
procesami, użytkownikami i różnymi systemami komputerowymi. Pozwalają one użytkownikom
przesyłać komunikaty wyświetlane na ekranach ich odbiorców, ekspediować większe komunikaty za
pomocą poczty elektronicznej Iub przesyłać pliki z jednej maszyny do drugiej, a nawet zdalnie
rejestrować się na innych komputerach.



Programy użytkowe

Większość systemów operacyjnych jest dostarczana wraz z programami do rozwiązywania typowych
zadań Iub wykonywania typowych działań. Do programów takich zalicza się: metatranslatory , procesory
tekstów, pakiety programów graficznych, systemy baz danych, arkusze kalkulacyjne, pakiety programów
statystycznych, gry itp.

Najważniejszym programem systemowym jest interpretator poleceń, którego głównym zadaniem jest
pobieranie i wykonywanie kolejnych poleceń określanych przez użytkownika.

Wiele poleceń wykonywanych na tym poziomie dotoczy plików. Są to polecenia tworzenia, usuwania,
wyprowadzania, drukowania, kopiowania, wykonywania itd. Istnieją dwa podstawowe sposoby realizacji
takich poleceń. Jeden polega na tym, że interpretator poleceń sam zawiera kod wykonujący polecenia. Na
przykład polecenie usunięcia pliku może powodować skok interpretatora do części jego własnego kodu,
która obsłuży pobranie parametrów polecenia i wywoła odpowiednią funkcję systemową. Przy takim
rozwiązaniu liczba możliwych poleceń wpływa na rozmiar interpretatora. Ponieważ każde polecenie
wymaga zaprogramowania odrębnego kodu.

Alternatywną metodę zastosowano między innymi w systemie Unix. Wszystkie polecenia są
wykonywane przez specjalne programy systemowe. W tym wypadku interpretator poleceń sam "nie
rozumie" polecenia; służy mu ono jedynie do zidentyfikowania pliku, który ma być załadowany do
pamięci i wykonany. W ten sposób polecenie delete G spowoduje odnalezienie pliku o nazwie delete,
załadowanie go do pamięci i wykonanie z parametrem G. Funkcja związana z poleceniem delete jest w
całości określona przez kod zawarty w pliku delete. W ten sposób programiści uzyskują łatwość
dołączania nowych poleceń do systemu wystarczy utworzyć nowy plik z odpowiednią nazwą. W takim
potraktowaniu interpretator poleceń może być niewielki i nie trzeba zmieniać go przy dodawaniu nowych
poleceń.

Przy takim podejściu do projektowania interpretatora poleceń musimy rozwiązać kilka problemów.
Zauważmy, że skoro kod wykonujący polecenie jest osobnym programem, to system operacyjny musi
zawierać mechanizm przekazywania parametrów od interpretatora poleceń do programu systemowego.
Przedsięwzięcie to może okazać się kłopotliwe, ponieważ interpretator poleceń i program systemowy nie
muszą przebywać w tym samym czasie w pamięci. Ponadto załadowanie i wykonanie programu trwa
dłużej niż zwyczajny skok do innego miejsca kodu bieżąco wykonywanego programu.

Źródłem innego problemu jest pozostawienie interpretacji parametrów do dyspozycji autora programu
systemowego. Może to prowadzić do niespójnych konwencji oznaczania parametrów w programach,
które z punktu widzenia użytkownika są do siebie podobne, lecz zostały napisane w różnym czasie przez
różnych programistów.

3.5. Struktura systemu

System tak rozległy i złożony , jak współczesny system operacyjny, musi być konstruowany starannie,
jeśli ma działać właściwie i dawać się łatwo modyfikować. Powszechnie stosowanym podejściem jest
podzielenie tego przedsięwzięcia na małe części. Każda z takich części powinna stanowić dobrze
zdefiniowaną porcję systemu, ze starannie określonym wejściem, wyjściem i funkcjami..

3.5.1. Prosta struktura

Istnieje wiele komercyjnych systemów nie mających dobrze określonej struktury.

Systemy te powstały najczęściej jako małe, proste i ograniczone systemy operacyjne, które następnie
rozrastały się przekraczając pierwotne założenia. Przykładem takiego systemu jest MS-DOS - najlepiej
sprzedawany system operacyjny dla mikrokomputerów.

Mimo iż w systemie MS-DOS da się wyodrębnić pewną strukturę, to jego interfejsy

i poziomy funkcjonalne nie są wyraźnie wydzielone. Na przykład programy użytkowe mogą korzystać z
podstawowych procedur wejścia-wyjścia w celu bezpośredniego pisania na ekran lub dyski.

Inny przykład ograniczonej strukturalizacji systemu stanowi oryginalny system operacyjny Unix, który
również początkowo był ograniczany przez cechy sprzętu. Unix składa się z dwu odrębnych części: jądra
i programów systemowych. Jądro dzieli się dalej na ciąg interfejsów i programów obsługi urządzeń, które
dodawano i rozszerzano przez lata rozbudowy systemu. System Unix jest złożony z warstw. To wszystko,
co znajduje się poniżej interfejsu do funkcji systemowych a powyżej sprzętu, stanowi jądro. Za
pośrednictwem funkcji systemowych jądro zarządza systemem plików , planuje przydział procesora,
zarządza pamięcią i wykonuje inne czynności systemu operacyjnego.

Programy systemowe korzystają z zawartych w jądrze funkcji systemowych w celu wykonywania
użytecznych działań, takich jak kompilowanie programów lub operowanie plikami.

Funkcje systemowe definiują interfejs programisty z systemem Unix. Zbiór ogólnie dostępnych
programów systemowych określa interfejs użytkownika. Oba interfejsy wyznaczają kontekst, w którym
musi występować jądro systemu.

3.5.2. Podejście warstwowe

Nowe wersje systemu Unix zaprojektowano z myślą o ulepszonym sprzęcie.

Jeśli dysponuje się odpowiednim sprzętem, to można podzielić system operacyjny na mniejsze, lepiej
dobrane fragmenty, niż było to możliwe w oryginalnych systemach MS-DOS lub Unix. To z kolei
sprawia, że system operacyjny ma znacznie większą kontrolę nad komputerem, z czego mogą korzystać
programy użytkowe. Daje to również większą swobodę implementatorom przy dokonywaniu zmian w

wewnętrznym działaniu systemu. W tworzeniu modularnych systemów operacyjnych pomagają z dawna
ugruntowane techniki. Przy użyciu metody zstępującej do projektowania systemu można zdefiniować
jego ogólne funkcje i cechy oraz wyodrębnić jego części składowe. Cenna jest również zasada ukrywania
informacji, gdyż pozostawia programistom swobodę w realizacji procedur niskopoziomowych, pod
warunkiem, że zewnętrzne interfejsy z procedurami zostaną nie zmienione oraz że procedury będą
wykonywały przewidziane zadania.

Modularyzację systemu można uzyskać na wiele sposobów, ale najbardziej obiecujące jest podejście
warstwowe, polegające na dzieleniu systemu operacyjnego na warstwy (poziomy), przy czym każda
następna warstwa jest zbudowana na szczycie niższych warstw. Najniższą warstwę (warstwę 0) stanowi
sprzęt; najwyższą (warstwą N) jest interfejs z użytkownikiem.

Warstwa systemu operacyjnego jest implementacją abstrakcyjnego obiektu, wyizolowanym zbiorem
danych i operacji, które mogą danymi tymi manipulować. Typową warstwę systemu operacyjnego np.
warstwę M - przedstawiono na schemacie. Zawiera ona struktury danych i procedury, które mogą być
wywołane z wyższych warstw. Natomiast warstwa M może wywołać operacje dotyczące niższych
warstw. Główną zaletą podejścia warstwowego jest modularność. Warstwy są wybrane w ten sposób, że
każda z nich używa funkcji (operacji) i korzysta z usług tylko niżej położonych warstw To podejście
może znakomicie ułatwić wyszukiwanie błędów i weryfikację systemu. Pierwszy poziom może być
poprawiany bez żadnej troski o resztę systemu, ponieważ - z definicji - do realizacji swoich funkcji
używa tylko podstawowego sprzętu (o którym zakłada się, że działa prawidłowo). Po sprawdzeniu
pierwszego poziomu, zakładając jego poprawne działanie, przystępuje się do opracowania drugiego
poziomu itd. Jeśli podczas uruchamia któregoś poziomu zostanie wykryty błąd, to wiadomo, że musi on
pochodzić z danego poziomu, ponieważ poziomy niższe już sprawdzono. W ten sposób podział systemu
na warstwy upraszcza jego projektowanie i implementację.

Implementacja każdej warstwy bazuje wyłącznie na operacjach dostarczanych przez warstwy niższe.
Warstwa nie musi nic wiedzieć o implementacji tych operacji; wie tylko, co te operacje robią. Każda
warstwa ukrywa zatem istnienie pewnych struktur danych, operacji i sprzętu przed warstwami wyższych
poziomów.

Struktura warstwowa systemu THE

Poziom 5: programy użytkowników

Poziom 4: buforowanie urządzeń wejścia i wyjścia

Poziom 3: programy obsługi konsoli operatora

Poziom 2: zarządzanie pamięcią

Poziom 1: planowanie przydziału procesom

Poziom 0: sprzęt

Podejście warstwowe można stosować różnorodnie. Na przykład system Venus również zaprojektowano
w sposób warstwowy. Niższe poziomy (0 do 4 ), przeznaczone do planowania przydziału procesora i do
zarządzania pamięcią, zostały następnie napisanie w postaci mikroprogramów. Taka decyzja przyniosła
zysk pod postacią szybszego działania i przejrzyście określonego interfejsu między poziomami
mikroprogramowanymi a poziomami wyższymi.

Struktura warstwowa systemu Venus

Poziom 6: programy użytkowników

Poziom 5: programy obsługi i planowania przydziału urządzeń

Poziom 4: pamięć wirtualna

Poziom 3: kanał wejścia-wyjścia

Poziom 2: planowanie przydziału procesora

Poziom 1: interpretator rozkazów

Poziom 0: sprzęt

Główną trudność w podejściu warstwowym stanowi zdefiniowanie warstw.

Niezbędne jest staranne zaplanowanie podporządkowań wynikających z wymogu, że dana warstwa może
używać tylko warstw niższych poziomów.

Program obsługi pamięci pomocniczej powinien być zazwyczaj powyżej programu planującego przydział
procesora, ponieważ program obsługi pamięci pomocniczej może musieć czekać na operacje wejścia-
wyjścia, a w tym czasie procesor może otrzymać nowy przydział. W wielkim systemie program planujący
przydział procesora może mieć więcej informacji o wszystkich aktywnych procesach niż daje się
pomieścić w pamięci operacyjnej. Powstaje więc potrzeba wymiany tych informacji między pamięciami,
a to z kolei obliguje do umieszczenia programu obsługi pamięci pomocniczej poniżej programu
planującego przydział procesora.

Projektuje się systemy złożone z niewielu, lecz bardziej funkcjonalnych warstw, zyskując większość zalet
modularnego programowania i unikając trudności związanych z definiowaniem wzajemnych zależności
między warstwami.

3.6. Maszyny wirtualne

Z ogólnego punktu widzenia, system komputerowy jest zbudowany z warstw.

Sprzęt znajduje się na najniższym poziomie we wszystkich takich systemach.

W jądrze systemu, pracującym na następnym poziomie, użyto instrukcji sprzętowych do tworzenia zbioru
funkcji systemowych, z których korzysta się w zewnętrznych warstwach. W programach systemowych,
występujących powyżej jądra systemu można używać funkcji systemowych na równi z instrukcjami
sprzętowymi i, pod pewnymi względami, nie odróżniać funkcji od instrukcji. Pomimo że oba rodzaje
operacji są różnie osiągane, tak jedne, jak i drugie dostarczają środków, pozwalających zaprogramować
bardziej złożone funkcje. W efekcie, w programach systemowych traktuje się sprzęt i funkcje systemowe
tak, jak gdyby należały one do tego samego poziomu.

Niektóre systemy przedłużają nawet ten schemat o następny krok, umożliwiając łatwe wywoływanie
programów systemowych przez programy użytkowe. Tak jak poprzednio, mimo że programy systemowe
są o szczebel wyżej niż inne procedury, programy użytkowe mogą to wszystko, co znajduje się w
hierarchii poniżej nich, traktować jako stanowiące część maszyny. Logiczną konkluzją tak pojmowanej
warstwowości jest koncepcja maszyny wirtualnej.

Stosując planowanie przydziału procesora i technikę pamięci wirtualnej, system operacyjny może
tworzyć złudzenie, iż wiele procesów pracuje na własnych procesorach i z własną (wirtualną) pamięcią.
Oczywiście, zazwyczaj proces taki ma dodatkowe możliwości, jak funkcje systemowe czy system plików,
których nie dostarcza sam sprzęt. Z drugiej strony, dzięki koncepcji maszyny wirtualnej nie uzyskuje się
żadnych dodatkowych funkcji, lecz tworzy jedynie interfejs identyczny z podstawowym sprzętem. Każdy
proces otrzymuje (wirtualną) kopię komputera będącego podstawą systemu.

Zasoby fizycznego komputera są dzielone w celu utworzenia maszyn wirtualnych. Do podziału procesora
i wywołania wrażenia, że każdy użytkownik ma własny procesor, można zastosować planowanie
przydziału procesora. Spooling i system plików pozwalają utworzyć wirtualne czytniki kart i wirtualne
drukarki wierszowe.

Największa trudność jest związana z systemami dyskowymi. Załóżmy, że fizyczna maszyna z trzema
napędami dysków ma zasymulować siedem maszyn wirtualnych. Jest jasne, że nie można przydzielić po
jednym napędzie każdej maszynie wirtualnej. Należy pamiętać, że samo oprogramowanie maszyny
wirtualnej zajmuje spory obszar dysku na obsługę pamięci wirtualnej i spoolingu. Rozwiązanie stanowi
zastosowanie dysków wirtualnych, które są pod każdym względem identyczne z fizycznymi z wyjątkiem
rozmiaru. Tego rodzaju konstrukcji nadano w systemie operacyjnym VM dla maszyn IBM miano
minidysków. System implementuje każdy minidysk przydzielając mu taką liczbę ścieżek dysku
fizycznego, na jaką dany minidysk zgłosi zapotrzebowanie. Rzecz oczywista, suma rozmiarów
wszystkich minidysków musi być mniejsza od aktualnie dostępnej wielkości fizycznej przestrzeni
pamięci dyskowej.

Użytkownicy otrzymują zatem własne maszyny wirtualne. Mogą w nich wykonywać dowolny pakiet
oprogramowania dostępny w maszynie bazowej. W systemie IBM VM użytkownik na ogół korzysta z
systemu CMS - interakcyjnego systemu operacyjnego dla indywidualnego użytkownika.
Oprogramowanie maszyny wirtualnej jest przeznaczone do zaprogramowania pracy wielu maszyn
wirtualnych w jednej maszynie fizycznej i nie uwzględniono w nim wspomagania oprogramowania
użytkownika. Taką organizację można uznać za pożyteczny podział zagadnienia projektowania
wielostanowiskowego systemu interakcyjnego na dwa mniejsze fragmenty.

Koncepcja maszyny wirtualnej jest trudna w implementacji. Oprogramowanie maszyny wirtualnej może
pracować w trybie monitora, ponieważ jest ono systemem operacyjnym. Natomiast sama maszyna
wirtualna może działać tylko w trybie użytkownika. Niemniej jednak, skoro maszyna fizyczna ma dwa
tryby pracy, to maszyna wirtualna powinna mieć je również. W konsekwencji są potrzebne dwa wirtualne
tryby - użytkownika i monitora, z których każdy pracuje w fizycznym trybie użytkownika. Czynności,
które zmieniają tryb użytkownika na tryb monitora w rzeczywistej maszynie (jak wywołanie funkcji
systemowej lub usiłowanie wykonania rozkazu uprzywilejowanego), muszą również powodować
przejście w maszynie wirtualnej od wirtualnego trybu użytkownika do wirtualnego trybu monitora.

Na ogół to przejście może być wykonane dość łatwo. Kiedy na przykład program pracujący w maszynie
wirtualnej w wirtualnym trybie użytkownika wywoła funkcje systemową, wtedy nastąpi przejście do
wirtualnego monitora maszyny rzeczywistej. Wirtualny tryb użytkownika jest zarazem fizycznym trybem
użytkownika. Kiedy monitor wirtualnej maszyny przejmie sterowanie, wtedy może zmienić zawartości
rejestrów i licznika rozkazów maszyny wirtualnej, aby zasymulować efekt wywołania funkcji
systemowej. Może on następnie wznowić działanie maszyny wirtualnej, zaznaczając, że jest ona teraz w
trybie wirtualnego monitora. Jeśli maszyna wirtualna spróbuje wtedy, na przykład, czytać z jej
wirtualnego czytnika kart, to wykona uprzywilejowany rozkaz wejścia-wyjścia. Ponieważ maszyna

wirtualna pracuje w fizycznym trybie użytkownika, rozkaz ten napotka pułapkę w monitorze maszyny
wirtualnej. Monitor maszyny wirtualnej musi wówczas zasymulować efekt wykonania rozkazu wejścia-
wyjścia. Najpierw odnajduje plik buforowy implementujący dany wirtualny czytnik kart. Następnie
tłumaczy czytanie z wirtualnego czytnika kart na czytanie utożsamionego z nim buforowego pliku
dyskowego, po czym przesyła kolejny wirtualny obraz karty" do wirtualnej pamięci maszyny
wirtualnej. Na koniec wznawia działanie maszyny wirtualnej. Stan maszyny wirtualnej uległ dokładnie
takiej samej zmianie, jak gdyby wykonano rozkaz wejścia-wyjścia za pomocą prawdziwego czytnika kart
w rzeczywistej maszynie pracującej w rzeczywistym trybie monitora. Podstawową różnicę stanowi,
oczywiście, czas. Podczas gdy rzeczywista operacja wejścia-wyjścia mogłaby zabrać 100 m s, wirtualne
operacje wejścia-wyjścia mogą trwać krócej (ponieważ są symulowane przy użyciu buforowego pliku
dyskowego) albo dłużej (ponieważ są interpretowane). Ponadto, procesor musi pracować
wieloprogramowo dla wielu maszyn wirtualnych, co powoduje nie dające się przewidzieć spowolnienie
maszyny wirtualnej. W skrajnym przypadku, aby uzyskać prawdziwą maszynę wirtualną, trzeba
symulować wszystkie rozkazy.

Koncepcja maszyny wirtualnej ma kilka zalet. W tym środowisku istnieje pełna ochrona różnorodnych
zasobów systemowych. Każda maszyna wirtualna jest całkowicie odizolowana od innych maszyn
wirtualnych, nie ma więc kłopotów związanych z zapewnieniem bezpieczeństwa. Z drugiej strony nie
istnieje bezpośredni podział zasobów. Aby go uzyskać, zastosowano dwa podejścia. Po pierwsze - jest
możliwe współdzielenie minidysku. Modeluje się je tak jak dla dysku fizycznego, a realizuje
programowo. Ta technika umożliwia współdzielenie plików. Po drugie - można zdefiniować sieć maszyn
wirtualnych, z których każda może wysyłać informacje przez wirtualną sieć komunikacyjną. Również i tu
sieć jest wzorowana na fizycznych sieciach komunikacyjnych, ale jest zaimplementowana przez
oprogramowanie.

Ponieważ systemy operacyjne są wielkimi i złożonymi programami, nie można wykluczyć, iż zmiana w
jednym miejscu nie spowoduje ukrytego błędu gdzie indziej. Sytuacja taka może być szczególnie
niebezpieczna, zważywszy na możliwości systemu operacyjnego. Ponieważ system operacyjny pracuje w
trybie monitora, złe ustawienie jakiegoś wskaźnika może okazać się błędem prowadzącym do zniszczenia
całego systemu plików. Jest zatem niezbędne staranne testowanie każdej zmiany wprowadzonej do
systemu.

3. 7. Projektowanie i implementacja systemu

3.7.1. Założenia projektowe

Pierwszym zagadnieniem przy projektowaniu systemu jest określenie celów i specyfikacji systemu. Na
najwyższym poziomie projektu systemu powinno się w dużym stopniu uwzględniać wybór sprzętu i typu
systemu Wymagania można zasadniczo podzielić na dwie grupy: cele użytkownika i cele systemu.
Użytkownicy oczekują od systemu operacyjnego pewnych oczywistych właściwości: powinien on być
wygodny w użyciu, łatwy do nauki, niezawodny, bezpieczny i szybki. Jest zrozumiałe, że ze względu na
brak powszechnej zgody co do sposobu osiągania tak określonych celów, tego rodzaju specyfikacje nie są
zbyt przydatne przy projektowaniu systemu.

Podobny zestaw wymagań mogą sformułować osoby, których zadaniem jest taki system zaprojektować,
utworzyć, utrzymywać, a także nim się posługiwać. System operacyjny powinien być łatwy do
zaprojektowania, zaimplementowania i pielęgnowania; powinien być elastyczny, niezawodny, wolny od
błędów i wydajny. I znowu, tak postawione wymagania są niejasne i nie mają ogólnego rozwiązania.

3.7.2. Mechanizm a polityka

Mechanizmy określają, jak czegoś dokonać. Natomiast polityka decyduje o tym, co ma być zrobione.

Na przykład mechanizmem gwarantującym ochronę procesora jest czasomierz. Decyzja o tym, na jak
długo czasomierz jest nastawiany dla poszczególnych użytkowników , leży w sferze polityki.

Odseparowanie polityki od mechanizmu jest bardzo ważne ze względu na elastyczność. W najgorszym
przypadku każda zmiana polityki może pociągać konieczność zmiany leżącego u jej podłoża
mechanizmu. O wiele bardziej pożądany jest mechanizm ogólny. Zmiana polityki wymaga wtedy co
najwyżej przedefiniowania pewnych parametrów w systemie.

Decyzje polityczne są ważne we wszystkich zagadnieniach planowania i przydziału zasobów. Ilekroć
staje się niezbędne rozstrzygnięcie o przydzieleniu bądź nieprzydzieleniu zasobu, tylekroć musi zostać
podjęta decyzja podyktowana jakąś polityką.

3.7.3. Implementacja systemu

Po zaprojektowaniu system operacyjny trzeba zrealizować. Tradycyjnie pisano systemy operacyjne w
językach asemblerowych. Obecnie można je pisać w językach wyższego poziomu.

Programuje się szybciej, uzyskując kod bardziej zwarty, łatwiejszy do zrozumienia i sprawdzenia. Za
główne wady uznaje się spowolnienie tłumaczenia i potrzebę większego rozmiaru pamięci. Chociaż
żaden kompilator nie wyprodukuje kodu bardziej zwartego, niż może to zrobić doświadczony programista
piszący w języku asemblerowym, to jednak produkty kompilacji dorównują często wynikom przeciętnych
programistów używających asemblerów. Ponadto, jeśli zastąpi się kompilator jego lepszą wersją, to
ulegnie jednolitej poprawie jakość całego przekładu systemu operacyjnego, dzięki zwykłemu
powtórnemu przetłumaczeniu całości. System operacyjny jest znacznie łatwiejszy do przenoszenia, czyli
instalowania na innym sprzęcie, jeśli jest napisany w języku wysokiego poziomu.

Tak jak w innych systemach, główne ulepszenia działania są zwykle rezultatem lepszych struktur danych
i algorytmów, aniżeli czystszego kodowania. W dodatku, choć rozmiary systemów operacyjnych są
bardzo wielkie, na efektywność ich działania ma istotny wpływ tylko niewielka część kodu;
najważniejszymi procedurami są prawdopodobnie programy - zarządzający pamięcią i planujący
przydział procesora. Kiedy system zostanie napisany i pracuje poprawnie, wtedy można zidentyfikować
procedury stanowiące jego wąskie gardła i zastąpić je asemblerowymi odpowiednikami.

Aby wykryć wąskie gardła, trzeba mieć możność kontrolowania działania systemu. Konieczne okaże się
dodanie kodu, który obliczy i wyświetli pomiary zachowania systemu. Wszystkie interesujące zdarzenia,
wraz z ich czasem i ważnymi parametrami, są rejestrowane i zapisywane do pliku. Potem program
analizujący może przetworzyć plik z zapisem zdarzeń w celu zbadania zachowania systemu oraz
zidentyfikowania jego wąskich gardeł i nieefektywnych zachowań. Ten sam ślad programu może również
posłużyć jako dane wejściowe do symulacji proponowanego ulepszenia systemu. ślady programów
znajdują także zastosowanie przy wykrywaniu błędów w zachowaniu systemu operacyjnego.

Alternatywna możliwość polega na obliczeniu i wyświetleniu pomiarów zachowania systemu w czasie
rzeczywistym.

3.8. Generowanie systemu

Można zaprojektować i zrealizować system operacyjny wyłącznie dla jednej maszyny w jednej instalacji.
Częściej jednak projektuje się systemy operacyjne przeznaczone do działania na pewnej klasie maszyn w
rozmaitych instalacjach ze zmienną konfiguracją urządzeń zewnętrznych. System musi wówczas
podlegać konfigurowaniu lub generowaniu dla każdej specyficznej instalacji komputerowej. Proces ten
nazywa się generowaniem systemu.

System operacyjny jest zazwyczaj rozpowszechniany na taśmie lub dysku.

Do generowania systemu używa się specjalnego programu. Program generowania systemu czyta z pliku
lub pyta operatora o informacje dotyczące specyfiki konfiguracji danego wyposażenia sprzętowego:



Jaki zastosowano procesor centralny? Jakie dodatkowe możliwości (rozszerzony zbiór instrukcji,
arytmetyka zmiennopozycyjna itd.) zostały zainstalowane? W systemach wieloprocesorowych
należy opisać każdy procesor.



Ile jest dostępnej pamięci? Niektóre systemy same określają ten parametr - dopóty odwołując się
do kolejnych komórek pamięci, dopóki nie wystąpi błąd "niedozwolony adres". Procedura ta
określa maksymalny poprawny adres, a zatem i ilość dostępnej pamięci..



Jakie są dostępne urządzenia? System będzie wymagał podania sposobu adresowania każdego
urządzenia (numeru urządzenia), numeru przerwania od danego urządzenia, opisu typu i modelu
urządzenia i wszelkich specjalnych parametrów technicznych urządzeń.



Jakich oczekuje się możliwości systemu operacyjnego? Mówiąc inaczej - jakie mają być wartości
parametrów instalacyjnych systemu. Mogą to być między innymi informacje o liczbie i wielkości
buforów, pożądanym typie algorytmu planowania przydziału procesora, maksymalnej
przewidywanej liczbie procesów itp.

Określone w ten sposobów dane mogą być wykorzystane na kilka sposobów. W skrajnym przypadku
mogą posłużyć do wprowadzenia zmian do kopii kodu źródłowego systemu. Program systemu
operacyjnego musi zostać potem w całości skompilowany. Zmiany w deklaracjach danych, inicjacjach i
stałych oraz warunkowa kompilacja spowodują wyprodukowanie wynikowej wersji systemu,
przykrojonej na miarę sformułowanych wymagań.

W bardziej elastycznej metodzie opis systemu może spowodować utworzenie tablic i wybranie zawczasu
skompilowanych modułów z biblioteki. Wygenerowanie systemu nastąpi w wyniku skonsolidowania tych
modułów. Selektywne wybieranie modułów z biblioteki pozwala umieścić w niej program obsługi dla
wszystkich przewidywanych urządzeń wejścia wyjścia, a jednocześnie dołączyć do systemu
operacyjnego tylko te, które naprawdę będą używane. Ponieważ system nie musi być ponownie
kompilowany, jego wygenerowanie będzie szybsze. Może jednak powstać system bardziej ogólny, niż
faktycznie był potrzebny.

Na przeciwnym biegunie skrajności leży możliwość skonstruowania systemu całkowicie sterowanego
tablicami. System zawiera zawsze cały kod, wyborów zaś dokonuje się nie podczas kompilacji lub
konsolidacji, lecz podczas wykonania. Generowanie systemu sprowadza się do wytworzenia
odpowiednich tablic opisujących system.

Główne różnice w tych podejściach stanowią rozmiar i ogólność wygenerowanego systemu oraz łatwość
dokonywania modyfikacji w wypadku zmian w sprzęcie.

3.9. Podsumowanie

Systemy operacyjne dostarczają wielu usług. Na najniższym poziomie funkcje systemowe pozwalają, aby
wykonywany program zgłaszał zapotrzebowania na usługi bezpośrednio do systemu operacyjnego. Na
wyższym poziomie interpretator poleceń tworzy mechanizm, za którego pomocą użytkownik może
kierować polecenia pod adresem systemu, bez konieczności pisania programu. Polecenia mogą pochodzić
z kart (w systemie wsadowym) lub wprost z terminala (w interakcyjnym systemie z podziałem czasu).
Jeszcze inny mechanizm przeznaczony do spełniania życzeń użytkownika stanowią programy systemowe.

Rodzaje żądań zależą od poziomu zgłoszenia. Poziom funkcji systemowych musi zapewnić podstawowe
operacje, takie jak nadzór nad procesami oraz działania na plikach i urządzeniach. Żądania wyższego
poziomu, spełniane przez interpretator poleceń Iub programy systemowe, są tłumaczone na ciągi
wywołań funkcji systemowych. Usługi systemu można podzielić na kilka kategorii: nadzór nad
wykonywaniem programów, podawanie informacji o stanie systemu oraz obsługa zamówień na operacje
wejścia-wyjścia. Błędy programowe można uważać za niejawne żądania obsługi.

Gdy określi się usługi systemu operacyjnego, wtedy można przystąpić do opracowania jego struktury.
Znajdują tu zastosowanie liczne tablice, w których odnotowuje się stan systemu komputerowego i stan
zadań systemowych. Zaprojektowanie nowego systemu operacyjnego jest poważnym przedsięwzięciem.
Jest bardzo ważne, aby przed przystąpieniem do pracy nad projektem zostały dobrze zdefiniowane cele
systemu. Punktem wyjścia do wybierania niezbędnych rozwiązań spośród różnych algorytmów i strategii
jest określenie pożądanego typu systemu. Wielkie rozmiary systemu operacyjnego obligują do
zatroszczenia się o jego modularność. Ważną techniką projektowania jest rozważanie systemu jako
układu warstw. Koncepcja maszyny wirtualnej, stanowiącej esencję podejścia warstwowego, zaciera
różnice między jądrem systemu operacyjnego a sprzętem, traktując jedno i drugie jak sprzęt. Na szczycie
tak rozumianej maszyny wirtualnej można umieszczać inne systemy operacyjne.

Przez cały czas cyklu projektowania systemu operacyjnego należy starannie oddzielać decyzje dotyczące
polityki od szczegółów realizacyjnych. Przestrzeganie tego zapewnia maksimum elastyczności w
przypadku późniejszych zmian w decyzjach politycznych.

Obecnie systemy operacyjne są prawie zawsze pisane w językach implementacji systemów lub w
językach wyższego poziomu. Polepsza to warunki implementacji, pielęgnowania i przenośności. Aby
utworzyć system operacyjny dla konkretnej konfiguracji sprzętu, musimy ten system wygenerować.

4. Procesy

4.1 Koncepcja procesu

Proces każde działanie procesora; jednostka pracy systemu; aktywny odpowiednik programu (który
jest obiektem pasywnym). Nieformalnie proces sekwencyjny jest wykonywanym programem.
Sekwencyjność wynika stąd, że na jego zamówienie w danej chwili może być wykonywany jeden rozkaz
kodu. Poza zakodowanym programem proces zawiera:



licznik rozkazów (wskazujący następny rozkaz do wykonania),



stos (przechowywanie danych tymczasowych),



sekcję danych (zmienne globalne).

4.1.1 Stan procesu



nowy,



aktywny (są wykonywane instrukcje)



czekający (czeka na zdarzenie np. zakończenie operacji we-wy);



gotowy (czeka na przydział czasu procesora)



wstrzymany

4.1.2 Blok kontrolny procesu

Jest to blok danych lub rekord będący reprezentacją procesu w systemie. Zawiera:



stan procesu



licznik rozkazów



rejestry procesora (liczba i typy zależą od architektury komputera. Stanowią one jakby pamięć
podręczną procesora. Informacje z rejestrów musi być przechowywana wraz z licznikiem
rozkazów w czasie wykonywania przerwań, aby proces mógł wznowić działanie)



informacje o planowaniu przydziału procesora (priorytet procesu, wskaźniki do kolejek
porządkujących zmówienia itp.)



informacje o zarządzaniu pamięcią (zawartości rejestrów granicznych, lub tablic stron)



informacje do rozliczeń (ilość zużytego czasu procesora i czasu rzeczywistego, ograniczenia
czasowe, numery rachunków, zadań lub procesów itp.)



informacje o stanie we-wy (inf. o niezrealizowanych zamówieniach na oper we-wy, wykaz
urządzeń przydzielonych do procesu, lista otwartych plików)

4.2 Procesy współbieżne

Jeżeli procesy działają współbieżnie, to znaczy, że procesor dzieli moc obliczeniową między wiele
procesów jednocześnie. Powody:



podział zasobów fizycznych



podział zasobów logicznych (np. współużytkowanie pliku)



przyspieszanie obliczeń (pod warunkiem, że występuje wiele elementów przetwarzających)



modularność (system można projektować modularnie dzieląc na osobne procesy)



wygoda (nawet 1 użytkownik może mieć kilka zadań na raz)

4.2.1 Tworzenie i kończenie procesu

Tworzenie procesu

Proces może tworzyć nowe procesy za pomocą odpowiedniej funkcji systemowej. Stary proces nazywa
się macierzystym, a nowy potomnym. Zwykle stosuje się rozwiązanie w którym proces potomny
otrzymuje zasoby od procesu macierzystego proces macierzysty dzieli swe zasoby pomiędzy procesy
potomne. Zapobiega to przeciążeniu systemu, które może mieć miejsce w systemach, gdzie proces
potomny otrzymuje zasoby bezpośrednio od systemu operacyjnego. Proces macierzysty może zawsze
przekazać potomnemu dane wejściowe.

Po utworzeniu procesu potomnego w odniesieniu do macierzystego stosuje się dwa podejścia:



proces macierzysty kontynuuje swoje działanie współbieżnie z procesem potomnym



proces macierzysty czeka na zakończenie działania wszystkich procesów potomnych

Zakończenie procesu

Proces kończy się wówczas, gdy wykona swoją ostatnią instrukcję i poprosi system o swoje usunięcie.
Możliwe jest wówczas przekazanie danych wyjściowych do procesu macierzystego.

Proces macierzysty może spowodować zakończenie swoich procesów potomnych. Dzieje się tak zwykle,
gdy potomek nadużył któregoś z przydzielonych mu zasobów, lub wykonywane przez potomka zadanie
stało się zbędne.

Większość systemów nie pozwala na istnienie potomków po zakończeniu procesu macierzystego i
wymusza ich zakończenie. Jest to zjawisko zakończenia kaskadowego.

4.2.2 Związki między procesami

Proces jest niezależny, jeżeli nie może wpływać na zachowanie innych procesów ani inne procesy nie
mogą na niego oddziaływać. Ma on następujące właściwości:



na jego stan nie wpływa żaden inny proces;



jego działanie jest deterministyczne wynik jego pracy zależy tylko i wyłącznie od stanu
wejściowego;



jego działanie daje się powielać wynik pracy jest zawsze taki sam dla tych samych danych
wejściowych;



jego działanie może być wstrzymywane i wznawiane bez żadnych szkodliwych skutków

Każdy proces, który nie dzieli żadnych danych z innymi jest w istocie niezależny.

Proces jest współpracujący, jeśli oddziałuje na inne procesy w systemie lub może ulegać ich wpływom.
Jego właściwości to:



jego stan jest dzielony z innymi procesami;



wynik działania zależy od względnej kolejności jego wykonywania;



wynik może nie być ten sam przy tych samych danych wejściowych;

Proces, który dzieli dane z innymi jest współpracujący.

4.2.3 Wątki

Wątki (inaczej procesy lekkie) są to procesy współpracujące, które mogą dzielić przestrzeń adresów
logicznych (tj. zarówno kod jak i dane). Grupa równoprawnych wątków dzieli kod, przestrzeń adresową i
zasoby systemu. Środowisko w którym działa wątek nazywamy zadaniem. Jeden wątek przebiega w
jednym zadaniu, ale w zadaniu może być wiele wątków. Pojedynczy wątek posiada własny stan rejestrów
procesora i zwykle własny stos.

Szybkość przełączania i efektywność wątków jest większa niż tradycyjnych, ciężkich procesów.

4.3 Zagadnienia planowania

Celem wieloprogramowania jest najlepsze wykorzystanie czasu procesora. Idea tego jest prosta: proces
wykonywany jest do chwili gdy będzie musiał czekać (np. na zakończenie operacji we-wy, w tym
momencie wieloprogramowy system odbiera procesowi sterowanie i przekazuje następnemu. Daje to
wyższą przepustowość (ilość pracy wykonywanej w jednostce czasu).

4.3.1 Kolejki planowania

Wieloprogramowość wymaga uporządkowania procesów, aby system wiedział do którego oddać w danej
chwili sterowanie. Zwykle występują następujące kolejki:



kolejka zadań przechowuje procesy przechowywane w pamięci masowej i oczekujące na
przydział pamięci operacyjnej



kolejka procesów gotowych procesy rezydujące w pamięci i nie oczekujące. Składa się z
bloków kontrolnych procesów powiązanych polami wskaźnikowymi



kolejka do urządzeń każde urządzenie ma przyporządkowaną kolejkę procesów oczekujących
na nie. W kolejce do urządzeń wielodostępnych może występować wiele procesów, na urządzenie
do wyłącznego dostępu może czekać tylko jeden proces.

Przez cały czas swego istnienia proces wędruje od jednej kolejki do innej.

4.3.2 Planiści

Jest to proces którego zadaniem jest wybieranie z kolejki procesu któremu ma zostać oddane sterowanie.
Jest wywoływany, gdy jakiś proces opuszcza system. Powinien zachowywać właściwą proporcję
procesów ograniczonych przez we-wy, do procesów ograniczonych przez dostęp do procesora. Nie
występuje w systemach z podziałem czasu.

Planista długoterminowy wybiera procesy z kolejki zadań, a planista krótkoterminowy z kolejki procesów
gotowych. Jest wywoływany zawsze gdy aktywny proces przechodzi w stan oczekiwania.

Niekiedy występuje również planista średnioterminowy. Zajmuje się on wymianą, czyli tymczasowym
usuwaniem z pamięci wybranych procesów, oraz ich późniejszym ponownym uruchamianiem.

4.4 Planowanie przydziału procesora

4.4.1 Cykl zatrudnień procesor-urządzenie

Proces składa się z następujących po sobie cykli. Na każdy z nich składa się faza procesora i oczekiwanie
na urządzenia we-wy. Pierwsza zawsze jest faza procesora. Natomiast po ostatniej fazie procesora proces
zamiast przejść do fazy we-wy składa zamówienie na zakończenie swego działania.

4.4.2 Planista przydziału procesora

Jest to inna nazwa planisty krótkoterminowego.

4.4.3 Struktura planowania

Decyzje o przydziale czasu procesora mogą zapadać w następujących sytuacjach:

1. Proces przeszedł od stanu wykonywania do stanu oczekiwania
2. Proces przeszedł od stanu wykonywania od stanu gotowości (np. w skutek wystąpienia

przerwania)

3. Proces przeszedł od stanu oczekiwania do stanu gotowości
4. Proces zakończył działanie

W 1 i 4 następnym procesem musi być nowy proces (jeśli znajduje się w kolejce procesów gotowych)

Jeśli występują wyłącznie warunki 1 i 4 to mówimy o niewywłaszczeniowym schemacie planowania, w
przeciwnym wypadku o wywłaszczeniowym algorytmie planowania.

4.4.4 Przełączanie kontekstu

Jest to operacja zachowanie stanu procesu przy odbieraniu mu sterowania i odczytywania stanu kolejnego
procesu. Im bardzie złożony system tym więcej operacji trzeba tu wykonać.

4.4.5 Program koordynujący

Jest to moduł systemu, który faktycznie przekazuje sterowanie do procesu wybranego przez planistę
krótkoterminowego. Jego obowiązki to:



przełączanie kontekstu



przełączanie do trybu użytkownika



wykonanie skoku do odp. adresu w programie użytkownika w celu wznowienia działania

4.5 Algorytmy planowania

Do ich porównania wykorzystuje się ich właściwości:

1. wykorzystanie procesora
2. przepustowość
3. czas cyklu przetwarzania całkowity czas od wejścia procesu do systemu do zakończenia

działania

4. czas oczekiwania czas spędzony w kolejce procesów gotowych. Algorytm ma wpływ tylko na

ten czas.

5. czas odpowiedzi pomiędzy przedłożeniem zamówienia a nadejściem odpowiedzi (bez czasu jej

wyprowadzania)

Celem jest max(1,2) i min(3,4,5). Optymalizuje się zwykle wartość średnią, ale np. w systemach
interakcyjnych dąży się do zmniejszenia maksymalnego 5 i minimalizacji jego wariancji.

4.5.1 Planowanie metodą FCFS pierwszy nadszedł pierwszy obsłużony

Implementacją jest kolejka procesów gotowych w postaci FIFO. Jest to algorytm niewywłaszczający,
grożący powstaniem efektu konwoju wszystkie procesy czekają, aż jeden duży zakończy obliczenia.
Jest nieelastyczny i niezbyt efektywny.

4.5.2 Planowanie metodą najpierw najkrótsze zadanie (SJF)

Procesor zostaje przydzielony procesowi o najkrótszej najbliższej fazie procesora. Jest to algorytm
optymalny pod względem średniego czasu oczekiwania. Problemem jest oszacowanie długości fazy
procesora (nie ma możliwości dokładnego zmierzenia). Szacuje się zwykle na podstawie długości
poprzednich faz. Nie da się zaimplementować tego algorytmu na poziomie planowania
krótkoterminowego. Może być niewywłaszczający, bądź wywłaszczający, nazywany wówczas metodą
najpierw najkrótszy pozostały czas (z czasu bieżącej fazy procesora).

4.5.3 Planowanie priorytetowe

Każdy proces otrzymuje priorytet i procesor przydziela się temu, który ma najwyższy priorytet. Priorytet
może być definiowany wewnętrznie (od obliczenia p. używa się wówczas mierzalnej wielkości procesu:
limity czasu, wielkość pamięci, liczba otwartych plików, stosunek fazy we-wy do fazy procesora), lub
zewnętrznie (kryteria spoza systemu: ważność, opłaty, właściciel...). Algorytm może wywłaszczający
bądź nie.

Wadą jest nieskończone blokowanie b. długie oczekiwanie procesów o niskim priorytecie.
Rozwiązaniem jest starzenie procesów stopniowe podwyższanie priorytetu.

4.5.4 Planowanie rotacyjne

Dla systemów z podziałem czasu. Ustalona jest mała jednostka czasu nazywana kwantem czasu. Planista
przydziela każdemu procesowi w kolejce (zwykle metodą FIFO) procesor ustawiając jednocześnie
czasomierz na przerwanie po upływie 1 kwantu. Jeżeli do tego czasu proces zakończy fazę procesora,

wówczas planista robi to samo z następnym procesem. Jeżeli faza nie została zakończona to po
wystąpieniu przerwania zegarowego (po upływie kwantu) nastąpi przełączenie kontekstu. Średni czas
oczekiwania wychodzi dość długi.

Jest to zawsze algorytm wywłaszczający.

Przy nieskończonym kwancie algorytm przechodzi w FCFS. Przy bardzo krótkim w dzielenie
procesora powstaje wrażenie, że w systemie jest tyle wolnych procesorów ile procesów jest
jednocześnie wykonywanych.

Wskazane jest by kwant był długi w porównaniu z czasem przełączania, inaczej mamy do czynienia z
dużymi stratami czasu.

4.5.5 Wielopoziomowe planowanie kolejek

Stosowane gdy procesy można przyporządkować do kilku różnych grup. Każda grupa ma własny
algorytm planujący (mogą być to różne algorytmy). Pomiędzy kolejkami planuje się zwykle
stałopriorytetowym planowaniem wywłaszczającym (każda kolejka ma własny, stały priorytet) lub
przydziela się im określone liczby cykli procesora.

4.5.6 Planowanie wielopoziomowych kolejek ze sprzężeniem zwrotnym

W przeciwieństwie do poprzedniego algorytmu, procesy nie są na stałe przypisane do kolejek, lecz mogą
być pomiędzy nimi przemieszczane.

Bazuje to na rozdzieleniu procesów o różnych rodzajach faz procesora. Im więcej czasu procesora
zużywa proces, tym niższy priorytet ma kolejka do której zostaje przypisany. Jednocześnie proces
oczekujący zbyt długo może zostać przeniesiony do kolejki o wyższym priorytecie.

Planista tego typu kolejek jest określony za pomocą następujących parametrów:



liczba kolejek



algorytm planowanie dla każdej kolejki



metoda decydowania o awansie procesu do kolejki o wyższym priorytecie



metoda decydowania o dymisji procesu do kolejki o niższym priorytecie



metoda określania kolejki, do której trafia proces potrzebujący obsługi

4.6 Planowanie wieloprocesorowe

W systemie wieloprocesorowym procesory mogą być jednakowe (system homogeniczny) lub różne
(system heterogeniczny).

W drugim przypadku proces może być wykonywany tylko na określonym procesorze z których każdy
musi posiadać własną kolejkę i zajmować się planowaniem w jej obrębie.

W systemie homogenicznym również możliwe jest rozwiązanie z oddzielnymi kolejkami (tzw. ładowanie
dzielone), ale może to prowadzić do bezczynności jednego z procesorów, podczas gdy inny miałby długą
kolejkę oczekujących procesów. Z tego powodu stosuje się rozwiązanie z jedną wspólną kolejką. Tu
następuje kolejny podział na dwie metody. W pierwszej każdy procesor wybiera z kolejki proces do
wykonania. Wymaga to jednak starannego zabezpieczenia się przed wybraniem przez różne procesory
tego samego procesu, przed ginięciem procesów z kolejki itp. Dlatego w drugiej metodzie jeden procesor
zajmuje się wyłącznie planowaniem przydziału procesów dla pozostałych procesorów. Jest to tzw.
metoda wieloprzetwarzania asymetrycznego.

4.7 Ocena algorytmów

Podstawą jest wybór istotnego dla nas kryterium (4.5) i metody oceniania

4.7.1 Ocena analityczna

Do oceny używa się algorytmu i roboczego załadowania systemu w celu wytworzenia wzoru lub wartości
oszacowujących zachowanie algorytmu dla danego systemu.

Modelowanie deterministyczne

Przyjmuje się konkretne, określone z góry załadowanie systemu i definiuje się zachowanie każdego
algorytmu w warunkach danego załadowania.

Jest to metoda szybka i prosta, dająca konkretne wyniki dające się łatwo porównywać. Jednak dotyczy
ono tylko sytuacji zbliżonych do przebadanych i jest przez to mało wiarygodne w odniesieniu do sytuacji
ogólnych.

Modele obsługi kolejek

Możliwe jest określenie rozkładów prawdopodobieństwa wystąpienia faz procesora i we-wy oraz
rozkładu czasów przybywania procesów do systemu dla większości algorytmów. To daje możliwość ich
porównywania.

System komputerowy można określić jako sieć systemów obsługi (server). Są to zarówno procesor z
kolejką procesów gotowych jak i urządzenia we-wy z kolejkami do urządzeń. Obliczanie wykorzystania,
średnich długości kolejek, średnich czasów oczekiwania należą do analizy obsługi kolejek w sieciach).

Ustabilizowany system ma stałą długość kolejek daną wzorem Littlea: n=l*W, gdzie n - długość
kolejki, l- tempo przybywania nowych procesów, W średni czas oczekiwania w kolejce.

Wadą analizowania kolejek jest trudność matematycznego opracowania skomplikowanych algorytmów
planowania, zaś wyniki otrzymywana przy pomocy przybliżeń stają się przez to mało wiarygodne.

4.7.2 Symulacja

Tworzy się model systemu komputerowego. Symulator ma zmienną reprezentującą zegar i w miarę jej
przyrostu zmienia stan systemu symulując pracę urządzeń, procesów i planisty rejestrując jednocześnie
różnorodne dane i prezentując je po zakończeniu symulacji.

Dane do symulacji dostarcza się bądź przy pomocy generatora liczb losowych (pracującego w oparciu o
matematyczny rozkład prawdopodobieństwa, bądź rozkład zdefiniowany doświadczalnie w badanym
systemie), lub też w oparciu o tzw. taśmy śladów, rejestrujące faktyczną kolejność zdarzeń w systemach
rzeczywistych.

Wadą jest koszt i ogromne zużycie czasu pracy na symulację, jak również wysoki stopień
skomplikowania symulatora.

4.7.1 Implementacja

Najdokładniejszą metodą jest włączenie algorytmu do rzeczywistego systemu i badanie go w czasie
rzeczywistej pracy.

Wadami tej metody są: koszt, zmienne środowisko pracy, utrudnianie pracy rzeczywistych
użytkowników.

5. Koordynowanie procesów

Rozdział dotyczy problemów związanych z synchronizacją i komunikowaniem procesów współbieżnych.

5.1 Podstawy

Zajmijmy się typowym przykładem dwóch procesów sekwencyjnych, wykonywanych asynchronicznie,
dzielących dane: układem producent-konsument. W układzie takim konieczna jest synchronizacja, aby
konsument nie próbował pobierać danych, które nie zostały jeszcze wyprodukowane. Dane pomiędzy
procesami przesyłane są zwykle przy użyciu buforów. Możemy mieć do czynienia z nieograniczonym
buforem wówczas co najwyżej konsument będzie czekał na nowe dane, gdy bufor będzie pusty, ale
producent może pracować nieustannie. Układ z ograniczonym buforem jest bardziej skomplikowany,
gdyż producent musi czkać gdy bufor jest pełen.

Oto przykładowe algorytmy:

var n;

type jednostka...;

var bufor: array [0..n-1] of jednostka;

we, wy: 0..n-1;

n wielkość bufora; bufor tablica cykliczna; we ws

kaźnik do następnego pustego elementu bufora;

wy wskaźnik do pierwszego zajętego elementu bufora; Bufor jest pusty gdy we=wy, a pełny gdy we +
1 mod n = wy {mod zapewnia cykliczność tzn gdy we+1>n-1 przesuwa we na początek tablicy).

Producent

repeat

produkuj jednostkę w nowy;

while we+1 mod n = wy do nic; {bufor pełny}

bufor[we]:=nowy;

we:=we+1 mod n;

until false;

Konsument

repeat

while we=wy do nic; {bufor pusty}

nowy:=bufor[wy];

wy:=wy+1 mod n;

konsumuj jednostkę z nowy;

until false;

Wadą tego schematu jest to, że zawsze jeden element w buforze pozostaje pusty. Aby tego uniknąć
stosuje się inny algorytm, wykorzystujący dzieloną zmienną licznik określającą ilość pustych elementów:

Producent

repeat

produkuj jednostkę w nowy;

while licznik=n do nic; {bufor pełny}

bufor[we]:=nowy;

we:=we+1 mod n;

licznik:=liczznik+1;

until false;

Konsument

repeat

while livznik=0 do nic; {bufor pusty}

nowy:=bufor[wy];

wy:=wy+1 mod n;

licznik:=licznik-1;

konsumuj jednostkę z nowy;

until false;

Tu występuje inny problem: poleceniu licznik:=licznik+(-)1 w języku maszynowym odpowiadają trzy
rozkazy:

rejestr:=licznik;

rejestr:=rejtestr+(-)1;

licznik:=rejestr;

Jeżeli oba programy będą wykonywane jednocześnie, to może być tak, że ten ciąg rozkazów zostanie
rozdzielony, a wówczas licznik będzie wskazywał nieprawdziwe informacje. Trzeba więc
zagwarantować, aby tylko jeden proces mógł operować na zmiennej licznik.

5.2 Problem sekcji krytycznej

Sekcja krytyczna to ta część kody programu w której proces zmienia współdzielone dane. Istotne jest aby
tylko jeden proces mógł w danej chwili wykonywać tą sekcję. Rozwiązanie problemu musi spełniać
następujące warunki:

1. Wzajemne wyłączanie tylko jeden proces może wykonywać sekcję krytyczną;
2. Postęp jeżeli żaden proces nie wykonuje s.k. to do wejścia w nią mogą kandydować tylko

procesy nie wykonujące swoich reszt;

3. Ograniczone czekanie

5.2.1 Rozwiązania dla dwu procesów

Na zwijmy rozpatrywane procesy P

, P

Algorytm 1

Procesy dzielą zmienną numer zezwalającą procesowi na który ona wskazuje na wejście do sekcji
krytycznej.

wygląda wówczas następująco:

repeat

while numer?i do nic;

sekcja krytyczna;

numer:=j;

reszta;

until false;

Rozwiązanie to spełnia warunek wzajemnego wyłączania, ale nie zapewnia postępu. Procesy muszą
wykonywać swe sekcje krytyczne naprzemiennie.

Algorytm 2

Używa on flag:

var flaga: array [0..1] of boolean;

Początkowo flagi są równe False. Wartość True oznacza, że proces jest gotowy do wejścia do sekcji
krytycznej.

wygląda wówczas następująco:

repeat

flaga[i]:=true;

while flaga[j] do nic;

sekcja krytyczna;

flaga[i]:=false;

reszta;

until false;

Jeżeli nastąpi (np. w wyniku przerwania) ustawienie obu flag na True to procesy zapętlą się.

Algorytm3

W pełni poprawne jest dopiero połączenie obu algorytmów:

repeat

flaga[i]:=true;

numer:=j;

while (flaga[j] and numer=j) do nic;

sekcja krytyczna;

flaga[i]:=false;

reszta;

until false;

5.4 Semafory

W bardziej złożonych zagadnieniach stosuje się semafory. Semafor S to zmienna całkowita, która
dostępna jest tylko przy pomocy dwu standardowych, niepodzielnych (tzn. takich które nie mogą zostać
przerwane w żaden sposób) operacji czeka i sygnalizuj. Definiowane są one następująco:

Czekaj(S): while S<=0 do nic;

S:=S-1;

Sygnalizuj(S): S:=S+1;

5.4.1 Sposób użycia

Procesy dzielą wspólną zmienną np. wzajwy(od wzajemnego wyłączania). Na początku jej wartość jest
równa 1. Każdy z procesów jest zorganizowany wg. schematu:

repeat

czekaj(wzajwy);

sekcja krytyczna;

sygnalizuj(wzajwy);

reszta;

until false;

Semafory mogą służyć też do synchronizacji. Mamy dwa współbieżne procesy P

z instrukcją S

i P

instrukcją S

, współdzielące zmienną synch o wartości początkowej 0. Jeżeli chcemy by instrukcja S

została wykonana dopiero po S

do procesu P

należy wstawić:

;

sygnalizuj(synch);

a do P

czekaj(synch);

;

5.4.2 Implementacja

Wadą dotychczasowych metod jest aktywne czekanie, czyli wykonywanie w oczekiwaniu na wykonanie
sekcji krytycznej operacji we, sprawdzających np. semafor. Marnuje to czas procesora. Aby tego uniknąć
wprowadza się kolejki do semaforów. Proces umieszczony w kolejce zostaje zablokowany opuszcza
kolejkę procesów gotowych. Po wykonaniu operacji sygnalizuj przez inny proces rozpatrywany proces
jest budzony i wraca do kolejki procesów gotowych.

Wymaga to zmian obu operacji i samego semafora:

type semafor = record

wart: integer;

L: list of proces; {kolejka}

end;

czekaj(S): S.wart:=S.wart –1;

if S.wart < 0 then begin

dołącz dany proces do S.L;

blokuj;

end;

sygnalizuj(S): S.wart:=S.wart+1;

if S.wart<=0 then begin

usuń jakiś proces P z S.L;

budzenie P;

end;

5.4.3 Blokady i blokowanie nieskończone (głodzenie)

Blokadą nazywamy sytuację gdy wiele procesów czeka na zdarzenie, które może wywołać tylko jeden z
nich. Jest to typowa sytuacja przy semaforach z kolejką. Procesy w kolejce oczekują na operację
sygnalizuj wykonaną przez proces aktywny.

Blokowanie nieskończone zachodzi wówczas gdy procesy czekają pod semaforem w nieskończoność.
Może tak być gdy kolejka do semafora jest w porządki LIFO (last in first out)

5.7 Komunikacja międzyprocesowa

Problemy synchronizacji to jeden z aspektów zagadnienia komunikacji między procesami. Istnieją dwa
rozwiązania komunikacji: pamięć dzielona i system komunikatów.

W systemach z pamięcią dzieloną procesy współużytkowują pewne zmienne. System operacyjny musi
dostarczyć tylko środków do dzielenia pamięci.

W metodzie komunikatów procesy przesyłają sobie na wzajem komunikaty, a system operacyjny musi
dostarczyć odpowiednich do tego narzędzi, w szczególności operacji nadaj(komunikat) i
odbierz(komunikat). Komunikaty mogą mieć zmienną (trudna implementacja, łatwe użytkowanie) lub
stałą długość (odwrotnie).

Aby komunikować umożliwić komunikację pomiędzy procesami muszą być łącza. Logiczna ich
implementacja odpowiada na następujące pytania:



Jak ustanawia się łącza?



Czy łącze może być powiązane z więcej niż dwoma procesami?



Ile łączy może być pomiędzy dwoma procesami?



Jaka jest pojemność łącza? Czy posiada bufor? Jak duży?



Jaki jest rozmiar komunikatów? Czy musi być stały?



Czy łącze jest jednokierunkowe (w jednej chwili przesył w jedną stronę), czy dwukierunkowe
(jednocześnie w obie)?

5.7.1 Określanie nadawców i odbiorców

Komunikacja bezpośrednia

Dokładnie jedno dwukierunkowe łącze pomiędzy dokładnie dwoma procesami.

Wariant symetryczny

Operacje nadaj i odbierz są dokładnie ukierunkowane nadawca i odbiorca dokładnie znają swoje
nazwy.

Wariant asymetryczny

Nadawca wie do kogo nadaje, ale odbiorca dowiaduje się od kogo jest komunikat dopiero po jego
otrzymaniu.

Komunikacja pośrednia

Zachodzi ona poprzez skrzynki pocztowe (inaczej porty). Procesy mogą w nich umieszczać i z nich
pobierać komunikaty. Jest to jedno lub dwukierunkowe łącze pomiędzy dowolną ilością procesów, gdzie
pomiędzy dwoma procesami może istnieć dowolna ilość łączy.

Jeżeli więcej niż dwa procesy mają się komunikować, aby nie dochodziło do konfliktów stosuje się
następujące rozwiązania:



Zezwala tylko na łącza pomiędzy dwoma procesami



Tylko jednemu procesowi pozawala się odbierać w danej chwili



Dopuszczać aby system dowolnie wybierał odbiorcę

Skrzynka może być własnością systemu (jest wówczas niezależna od procesów) lub procesu (rozróżnia
się wówczas proces właściciela może nadawać i odbierać, i użytkownika może tylko nadawać).

5.7.2 Buforowanie

Łącze ma pewną pojemność liczbę komunikatów, które mogą w nim przebywać. Można to
interpretować jako kolejkę komunikatów. Są trzy podstawowe implementacje tej kolejki:



Pojemność zerowa żaden komunikat nie może czekać. Stąd nadawca i odbiorca muszą być
zsynchronizowane (metodę tej synchronizacji nazywa się rendez-vous).



Pojemność ograniczona jeżeli kolejka jest pełna nadawca musi czekać, aż powstanie wolne
miejsce dla jego komunikatu



Pojemność nieograniczona nadawca nigdy nie jest opóźniany

Są też rozwiązania nie należące do tych kategorii:



Nadawca nie jest opóźniany, jednak jeśli odbiorca nie zdąży przeczytać komunikatu, ten ginie.
Aby do tego nie dopuszczać stosuje się jawną synchronizację procesów.



Nadawca jest opóźniany do czasu otrzymania odpowiedzi (potwierdzenia) od odbiorcy.
Spostrzeżono, że przypomina to wywołanie funkcji w procesie w systemie jednoprocesorowym i
oparto na tej metodzie system wywołań procedur zdalnych, gdzie procesy współbieżne wywołują
się nawzajem.

5.7.3 Sytuacje wyjątkowe

Zakończenie procesu

1. Proces P może czekać na komunikat Q, który zakończył działanie, będzie więc czekał w

nieskończoność. Powinien więc także zostać zakończony, bądź powiadomiony o zakończeniu
pracy przez Q.

2. P wysyła komunikat do zakończonego Q. Jeżeli mamy do czynienia z buforowaniem nic się nie

dzieje. Jeżeli jednak nie mamy bufora, lub P będzie czekał na potwierdzenie odbioru patrz 1.

Utrata komunikatów

Komunikat ginie z powodu awarii łącza. Metody postępowania to:

1. System operacyjny jest odpowiedzialny za wykrywanie takich sytuacji i ponowne wysłanie

komunikatu.

2. Nadawca jest odpowiedzialny za wykrywanie takich sytuacji i ponowne wysłanie komunikatu,

jeżeli mu na tym zależy.

3. System operacyjny wykrywa to zdarzenie i zawiadamia nadawcę, który robi co chce.

Utratę komunikatu wykrywa się zwykle metodą time out zawsze wymagane jest potwierdzenie
odbioru, na którego przyjście zakłada się pewien przedział czasu.

Zniekształcenie komunikatu

Np. w skutek zakłóceń w kanale komunikacyjnym. Postępuje się podobnie jak w przypadku zgubienia
komunikatu, a do wykrywania błędy stosuje się zwykle sumy kontrolne.

7. Blokady

W środowisku wieloprogramowym kilka procesów może rywalizować o skończoną liczbę zasobów. Proces zamawiający
zasoby, która są w danej chwili niedostępne, wchodzi w stan oczekiwania. Może się zdarzyć, że oczekujące procesy nigdy nie
zmienią swojego stanu, ponieważ zamawiane przez nie zasoby są przetrzymywane przez inne procesy. Sytuację taką
nazywamy blokadą (deadlock).

6.1

System składa się ze skończonej liczby zasobów, które są rozdzielane pomiędzy pewną liczbę rywalizujących ze sobą
procesów. Całość zasobów dzieli się na kilka grup, z których każda zawiera pewną liczbę identycznych egzemplarzy zasobów
tego samego typu. Przykładami zasobów są:

cykle procesora

obszar pamięci operacyjnej

pliki i urządzenia WE/WY

Jeżeli system ma dwa procesory, to zasób typu procesor składa się z dwóch egzemplarzy.

Jeżeli proces zamawia jeden egzemplarz zasobu jakiegoś typu, to jego zapotrzebowanie spełni przydział dowolnego
egzemplarza danego typu.

Proces powinien zamówić zasób przed jego użyciem i zwolnić go po wykorzystaniu. Proces może żądać tyle zasobów, ile ich
potrzebuje do wykonania zadania. Liczba zamawianych zasobów nie może przekroczyć ogólnej liczby zasobów dostępnych w
systemie.

W normalnych warunkach działania proces może użyć zasobu tylko w następującym porządku:

Zamówienie jeżeli nie może być spełnione natychmiast, to proces zamawiający musi czekać do chwili otrzymania
zasobu.

Użycie proces może korzystać z zasobu.

Zwolnienie proces oddaje zasób.

Zamawiać i zwalniać zasoby można za pomocą funkcji systemowych (np.: zwalnianie i przydzielanie urządzenia, otwarcie i
zamknięcie pliku, przydział i zwolnienie pamięci). Zamawianie i zwalnianie innych zasobów może być dokonywane za
pomocą semaforowych operacji czekaj i sygnalizuj. Użycie zasobów może być także uzyskane za pomocą funkcji
systemowych (np.: czytanie lub zapis do pliku). Dzięki temu, przed każdym użyciem zasobu system operacyjny może
sprawdzić czy proces zamówił dany zasób i czy zasób jest wolny czy też przydzielony, a jeśli jest przydzielony to do którego
procesu. Jeżeli proces zamawia zasób, który jest aktualnie przydzielony innemu procesowi, to zamawiający proces dołącza do
kolejki.

Zbiór procesów pozostaje w stanie blokady, jeśli każdy proces z tego zbioru czeka na zdarzenie, które może być spowodowane
tylko przez inny proces z tego samego zbioru.

3. Charakterystyka blokady

Warunki konieczne

Sytuacja blokady może zajść wtedy i tylko wtedy, gdy w systemie są jednocześnie spełnione cztery warunki:

Wzajemne wyłączanie przynajmniej jeden z zasobów musi być niepodzielny; to znaczy, że zasobu tego może
używać w danym czasie tylko jeden proces. Jeśli inny proces zamawia dany zasób, to proces ten musi być opóźniany
do czasu, aż zasób zostanie zwolniony.

Przetrzymywanie i oczekiwanie musi istnieć proces mający przydzielony co najmniej jeden zasób i oczekujący na
przydział dodatkowego zasobu, który jest przetrzymywany przez inny proces.

Brak wywłaszczeń zasoby nie podlegają wywłaszczaniu; to znaczy, że zasób może zostać zwolniony tylko z
inicjatywy przetrzymującego go procesu, po zakończeniu pracy tego procesu.

Czekanie cykliczne Może istnieć zbiór czekających procesów {P0, P1, ...,Pn}, takich że P0 czeka na zasób
przetrzymywany przez proces P1, Pn-1 na Pn, a Pn na P0.

Graf przydziału zasobów

Patrz XERO.

Metody postępowania z blokadami

Stosowanie protokołu, który zapewni, że system nigdy nie wejdzie w stan blokady (zapobieganie blokadom i unikanie
blokad).

System wchodzi w stan blokady i podejmuje się działania zmierzające do jej usunięcia.

2. Zapobieganie blokadom

Skoro, żeby zaszła blokada, spełnione muszą być wszystkie cztery warunki, doprowadzając by przynajmniej
jeden z nich się nie spełnił, możemy zapobiec blokadzie.

Wzajemne wyłączanie

Warunek wzajemnego wyłączania musi być spełniony w odniesieniu do zasobów niepodzielnych.
Zasoby dzielone nie wymagają dostępu na zasadzie wzajemnego wyłączania, więc nie mogą
występować w blokadach (np.: pliki tylko do odczytu).

Przetrzymywanie i oczekiwanie

Aby zapewnić, że ten warunek nigdy nie wystąpi w systemie, musimy zagwarantować, że jeżeli
kiedykolwiek proces zamawia zasób, to nie powinien mieć żadnych innych zasobów. Protokół,
który można tu zastosować, wymaga, aby każdy proces zamawiał i dostawał wszystkie swoje
zasoby, zanim rozpocznie działanie. Inny protokół umożliwia procesowi zamawianie zasobów tylko
wówczas, gdy proces nie ma żadnych zasobów. Proces może zamówić jakieś zasoby i korzystać z
nich, ale zanim zamówi jakieś dodatkowe, musi oddać wszystkie zasoby, które ma w danej chwili
przydzielone.

Obie metody mają pewne wady wykorzystanie zasobów może być bardzo małe, ponieważ z
wielu przydzielonych zasobów nie będzie korzystać nikt przez długie okresy czasu. Może też
dochodzić do blokowania nieskończonego (głodzenia procesu). Proces potrzebujący kilku
popularnych zasobów może być odwlekany w nieskończoność z powodu ciągłego przydzielania
choćby jednego z nich innym procesom.

Brak wywłaszczeń

Można tu posłużyć się protokołem, który powoduje, iż proces mający jakieś zasoby zgłasza zapotrzebowanie na inny zasób,
który nie może być mu natychmiast przydzielony, wówczas proces ten traci wszystkie dotychczasowe zasoby. Zasoby te są
dopisywane do listy zasobów, na które dany proces oczekuje. Drugi sposób gdy proces zamawia jakiś zasób, to najpierw jest
sprawdzane, czy jest on dostępny. Jeśli tak to następuje jego przydział, jeśli nie to sprawdza się, czy zasoby te nie są
przydzielone do innego procesu., który czeka na dodatkowe zasoby. Jeżeli tak to odbiera mu się te zasoby i przydziela
procesowi aktualnie zamawiającemu. Jeżeli zasoby nie są ani dostępne, ani przetrzymywane przez czekający proces, to proces
zamawiający też musi czekać. Podczas oczekiwania może stracić pewne zasoby, ale tylko wtedy, gdy inny proces ich zażąda.

6.3.4 Czekanie cykliczne

Konieczne jest wymuszenie uporządkowania całkowitego wszystkich typów zasobów i wymagane, aby każdy proces zamawiał
zasoby wzrastającym porządku ich numeracji.

6.4 Unikanie blokad

Alternatywna metoda unikania blokad wymaga dodatkowych informacji o tym, jak będzie następowało zamawianie zasobów.
Mając informacje na temat kolejności występowania zamówień i zwolnień dla każdego procesu, system operacyjny może
decydować przy każdym zamówieniu, czy proces powinien czekać, czy nie. Przy każdym zamówieniu musimy wziąć pod
uwagę zasoby bieżąco dostępne, zasoby przydzielone każdemu z procesów oraz przyszłe zamówienia i zwolnienia ze strony
każdego procesu, aby zadecydować czy bieżące zamówienie może być zrealizowane, czy też musi zostać odłożone w celu
uniknięcia wystąpienia blokady w przyszłości.

W najprostszym algorytmie zakłada się, że każdy proces deklaruje maksymalną liczbę zasobów każdego typu, których mógłby
potrzebować. Dysponując z góry dla każdego procesu informacją o wymaganej przez niego nieprzekraczalnej liczbie zasobów
każdego typu, można zbudować algorytm zapewniający, że system nigdy nie wejdzie w stan blokady. Jest to algorytm
unikania blokady. Algorytm unikania blokady dynamicznie sprawdza stan przydziału zasobów, aby zagwarantować, że nigdy
nie dojdzie do spełnienia warunku czekania cyklicznego. Stan przydziału zasobów jest określany przez liczbę dostępnych i
przydzielonych zasobów oraz przez maksymalne zapotrzebowania procesów. Stan jest bezpieczny, jeśli istnieje porządek, w
którym system może przydzielić zasoby każdemu procesowi (nawet w stopniu maksymalnym), unikając blokady.

Korzystając z koncepcji stanu bezpiecznego można zdefiniować algorytmy unikania blokad, gwarantujące, że system będzie
stale pozostawał w stanie bezpiecznym. Na początku system jest w stanie bezpiecznym. Za każdym razem, gdy proces
zamawia zasób, który jest na bieżąco dostępny, wówczas system musi zdecydować, czy zasób wolno przydzielić natychmiast
czy też proces powinien poczekać. Zgoda na zamówienie zostaje udzielona tylko wtedy, gdy przydział pozostawia system w
stanie bezpiecznym.

6.4.1 Zasoby o typach reprezentowanych wielokrotnie

Algorytm bankiera:

Gdy proces wchodzi do systemu, wówczas musi zadeklarować maksymalną liczbę każdego typu zasobu , które będą mu
potrzebne. Liczba nie może przekroczyć ilości dostępnych zasobów w systemie. Kiedy użytkownik zamawia zbiór zasobów,
system określa czy ich przydzielenie pozostawi system w stanie bezpiecznym. Jeśli tak, to zasoby zostaną przydzielone, a jak
nie to proces musi czekać.

W implementacji algorytmu bankiera występuje kilka struktur danych. Struktury te przechowują stan systemu przydziału
zasobów. Niech n będzie liczbą procesów w systemie, m zaś liczbą typów zasobów.

Są potrzebne następujące struktury danych:



Dostępne

Wektor o długości m, określający liczbę dostępnych zasobów każdego typu. Dostepne[j]=k oznacza, że jest
dostępnych k egzemplarzy zasobu typu Zj.



Maksymalne

Tablica o wymiarach nxm, definiująca maksymalne żądanie każdego procesu. Jeśli maksymalne[i,j]=k, to proces Pi
może zamówić co najwyżej k zasobów typu Zj.



Przydzielone

Tablica o wymiarach nxm, definiująca liczbę zasobów poszczególnych typów przydzielonych do każdego z
procesów. Gdy Przydzielone[i,j]=k, wówczas proces Pi ma przydzielonych k egzemplarzy zasobu typu Zj.



Potrzebne

Tablica o wymiarach nxm, przechowująca pozostałe do spełnienia zamówienia każdego z procesów. Element
Potrzene[i,j]=k, oznacz, że proces Pi może jeszcze potrzebować k dodatkowych egzemplarzy zasobu typu Zj.
Zauważymy, że Potrzebne[i,j]=Maksymalne[i,j] Przydzielone[i,j].

6.4.2 Zasoby o typach reprezentowanych pojedynczo

6.5. Wykrywanie blokady

W systemie, w którym nie stosuje się algorytmów zapobiegania blokadom ani unikania blokad, może
dojść do blokady. W takiej sytuacji w systemie muszą istnieć:



algorytm sprawdzający stan systemu w celu wykrycia, czy wystąpiła blokada;



algorytm wychodzenia z blokady.

Nakłady w schematach wykrywania blokady i jej usuwania dotyczą nie tylko czasu uaktualniania
niezbędnej informacji i wykonywania algorytmu wykrywania, lecz zawierają także potencjalną
możliwość strat związanych z wychodzeniem z blokady.

6.5.1. Typy zasobów reprezentowane wielokrotnie

W algorytmie wykrywania blokady korzysta się z kilku zmieniających się w czasie struktur danych,
podobnych do używanych w algorytmie bankiera :



Dostępne

wektor o długości m, określający liczbę dostępnych zasobów każdego typu.



Przydzielone

Tablica o wymiarach n x m, definiująca liczbę zasobów poszczególnych typów aktualnie przydzielonych
do każdego z procesów.



Zamówienia

Tablica o wymiarach n x m, określająca bieżące zamówienie każdego procesu. Jeśli Zamówienia[i,j] = k,
to proces Pi zamawia dodatkowo k egzemplarzy zasobu typu Z j.

Opisany poniżej algorytm wykrywania blokady bada każdy możliwy ciąg przydziałów dla procesów,
które nie są zakończone.

1. Niech Praca i Koniec będą wektorami o długości odpowiednio m oraz n. Na początku

podstawiamy Praca := Dostępne oraz, dla i = 1, 2, ..., n, jeśli Przydzielone i # 0, to Koniec[i] : =
faIse, w przeciwnym razie Koniec[i] : = true.

2. Znajdujemy indeks i taki, że zarówno:

(a) Koniec[i} = faIse

(b) Zamówienia i <=Praca.

Jeśli nie takiego i, to wykonujemy krok 4.

3. Praca : = Praca + Przydzielone i;

Koniec[i] : = true;

Idziemy do kroku 2.

4. Jeśli dla pewnych i z przedziału 1<= i <= n, Koniec[i] = faIse, to system jest w stanie blokady. Co

więcej, jeśli Koniec[i] = faIse, to blokada dotyczy procesu Pi.

Zdziwienie może budzić fakt odbierania zasobów procesowi Pi (w kroku 3), gdy tylko okaże się, że
Zamówienia i <= Praca (w kroku 2(b)). Wiemy, że proces Pi nie jest aktualnie objęty blokadą (ponieważ
Zamówienia i <= Praca). Toteż zakładamy optymistycznie, że proces Pi nie będzie dłużej potrzebować
zasobów do wypełnienia swojego zadania i niedługo zwróci systemowi wszystkie obecnie przydzielone
zasoby. Jeśli tak się nie stanie, to w późniejszym czasie może wystąpić blokada. Zostanie ona wykryta
przy następnym wykonaniu algorytmu wykrywania blokady

Aby zilustrować ten algorytm, rozważmy system z pięcioma procesami, od P0 do P4, i trzema typami
zasobów. Załóżmy, że w chwili T0 stan przydziału zasobów kształtuje się jak poniżej:

Przydzielone

Zamówienia

Dostępne

ABC

010

000

200

202

303

000

211

100

002

Przyjmujemy, że system nie jest w stanie blokady. Rzeczywiście, jeśli wykonamy nasz algorytm, to
stwierdzimy, że ciąg (Po, P2, P3, P1,P4) da w wyniku

Koniec[i] = true dla wszystkich i.

Załóżmy teraz, że proces P2 -zamawia dodatkowo egzemplarz zasobu typu C. Macierz Zamówienia
przyjmuje postać:

Zamówienia

ABC

Po 000

P1 202

P2 001

P3 100

P4 002

Teraz system popada w blokadę. Nawet jeśli odbierzemy zasoby przetrzymywane przez proces Po, to
dostępnych zasobów nie wystarczy, aby spełnić zamówienia innych procesów. Istnieje zatem blokada, w
którą są uwikłane procesy P1, P2, P3, i P4.

6.5.2. Typy zasobów reprezentowane pojedynczo.

Algorytm wykrywania blokady w p. 6.5.1 ma rząd liczby operacji m x n

. Jeśli wszystkie zasoby mają

tylko po jednym egzemplarzu, to jest możliwe zdefiniowanie szybszego algorytmu. Znów posłużymy się
wariantem grafu przydziału zasobów, zwanym grafem oczekiwań. Graf ten powstaje z grafu przydziału
zasobów przez usunięcie węzłów reprezentujących typy zasobów i złączenie uwolnionych w ten sposób
końców krawędzi.

Mówiąc dokładniej, w grafie oczekiwań krawędź od Pi do Pj implikuje, że proces Pi czeka na proces Pj
aby ten zwolnił potrzebne mu zasoby. Krawędź Pi + Pj istnieje w grafie oczekiwań wtedy i tylko wtedy ,
gdy odpowiadający mu graf przydziału zasobów zawiera dwie krawędzie: Pi -> Zq oraz Zq -> Pj dla tego
samego zasobu Zq.

6.5.3. Użytkowanie algorytmu wykrywania blokady

Kiedy należy wywoływać algorytm wykrywania blokady? Odpowiedź zależy od dwóch czynników:

1. Jak często może wystąpić blokada?

2. Jak wiele procesów zostanie dotkniętych blokadą w przypadku jej wystąpienia ?

Jeśli blokady zdarzają się często, to algorytm ich wykrywania powinien być wywoływany jeszcze
częściej. Zasoby przydzielone procesom tkwiącym w blokadzie będą pozostawały bezczynne do czasu
przełamania blokady. Co więcej, liczba procesów pogrążonych w blokadzie może rosnąć. Powstawanie
blokad grozi tylko wtedy, gdy jakiś proces zgłasza zamówienie, które nie może być natychmiast
zrealizowane. Jest możliwe, że zamówienie takie jest finalną potrzebą, której zaspokojenie
spowodowałoby zakończenie całego łańcucha czekających procesów. W skrajnym przypadku algorytm
wykrywania blokady może być wywoływany za każdym razem, gdy zamówienie na przydział nie może
być spełnione natychmiast. Można wówczas zidentyfikować nie tylko zbiór procesów pozostających w
blokadzie, lecz również proces będący jej "sprawcą". (W rzeczywistości każdy z zablokowanych
procesów stanowi ogniwo pętli w grafie zasobów, zatem wszystkie one łącznie powodują blokadę). Gdy

jest wiele typów zasobów, może spowodować powstanie wielu pętli w grafie zasobów, domykając każdą
z nich; powodujący je proces daje się zidentyfikować.

Blokada, prędzej czy] później, dławi przepustowość systemu i powoduje zmniejszenie wykorzystania
procesora.

6.6. Wychodzenie z blokady.

Kiedy algorytm wykryje istnienie blokady, wtedy można postąpić na kilka sposobów. Można
poinformować operatora o wystąpieniu blokady i pozwolić mu na ręczne jej usunięcie. Druga możliwość,
to pozwolić systemowi, aby automatycznie wydostał się z blokady. Są dwa sposoby złamania blokady.
Jednym jest po prostu usunięcie jednego lub kilku procesów w celu przerwania czekania cyklicznego.
Drugi sposób polega na odebraniu pewnych zasobów jednemu lub kilku procesom, których dotyczy
blokada.

6.6.1. Zakończenie procesu.

Aby usunąć blokadę poprzez usunięcie procesu używa się jednej z dwu metod.

W obu metodach system odzyskuje wszystkie zasoby przydzielone zakończonym procesom.



Zaniechanie wszystkich procesów uwikłanych w blokadę.

Metoda ta rozrywa pętlę blokady, lecz ponoszony przy tym koszt jest znaczny, ponieważ likwidowane
procesy mogły wykonywać swoje obliczenia od dłuższego czasu, a ich wyniki częściowe zostaną
zniszczone; prawdopodobnie spowoduje to konieczność późniejszego liczenia ich od nowa.



Usuwanie procesów pojedynczo, aż do wyeliminowania pętli blokady.

Ta metoda wymaga sporego nakładu na powtarzanie wykonywania algorytmu wykrywania blokady po
każdym usunięciu procesu w celu sprawdzenia, czy pozostałe procesy nadal znajdują się w blokadzie.

Usunięcie procesu może nie być łatwe. Jeśli proces uaktualniał dane w pliku, to zakończenie go wówczas
pozostawiłoby plik w nieokreślonym stanie. Jeśli wybiera się metodę etapowego kończenia procesów, to
należy rozstrzygać, który proces (lub procesy) należy zakończyć w celu przerwania blokady. Jest to
decyzja polityczna.

Na wybór procesu może się złożyć wiele czynników, w tym:

1. Priorytet procesu.

2. Jak długo proces wykonywał już obliczenia oraz ile czasu potrzeba mu jeszcze do zakończenia
przydzielonej mu pracy?

3. Jak wiele zasobów i jakiego typu znajduje się w użytkowaniu procesu (np.

czy zasoby te są, łatwe do wywłaszczenia)?

4. Ile zasobów proces potrzebuje do zakończenia działania?

5. Ile procesów trzeba będzie przerwać?

6. Czy proces jest interakcyjny czy wsadowy?

6.6.2. Wywłaszczanie zasobów.

W celu usunięcia blokady w wyniku wywłaszczania zasobów, stopniowo odbiera się pewne zasoby
jednym procesom i przydziela innym, aż pętla blokady zostanie przerwana. Jeśli do zwalczania blokad
stosuje się wywłaszczenia, to należy uwzględnić następujące trzy kwestie:

1. Wybór ofiary.

Które zasoby i które procesy mają ulec wywłaszczeniu? Tak jak przy kończeniu procesów ,
porządek wywłaszczeń powinien minimalizować ponoszone koszty. Na koszty mogą się składać
takie parametry, jak liczba zasobów, które przetrzymuje zablokowany proces, i czas, który
zablokowany proces zdążył już zużytkować na swoje wykonanie.

2. Wycofanie i wznowienie procesu.

Co wypadnie zrobić z procesem wywłaszczonym z zasobu? Proces pozbawiony jednego z
niezbędnych zasobów nie będzie mógł kontynuować swojego normalnego działania. Trzeba
będzie wycofać proces do jakiegoś bezpiecznego stanu, z którego można go będzie wznowić.

Ponieważ w ogólnym przypadku trudno określić, czym miałby być ów stan bezpieczny,
najprostszym rozwiązaniem staje się całkowite wycofanie: usunięcie procesu i późniejsze jego
wznowienie. Wszelako korzystniej byłoby cofnąć historię procesu tylko tyle, ile jest to niezbędne
do złamania blokady. Ta z kolei metoda wymaga od systemu przechowywania większej ilości
informacji o stanach wszystkich wykonywanych procesów.

3. Głodzenie procesu

W jaki sposób zagwarantować, że nie będzie dochodzić do głodzenia (nieskończonego oczekiwania
procesu na zasoby)? To znaczy, jak zapewnić, że wywłaszczanie nie będzie dotyczyć stale tego samego
procesu? W systemie, w którym wybór ofiary opiera się przede wszystkim na ocenie kosztów, może się
zdarzyć, że w roli ofiary będzie wybierany wciąż ten sam proces. Wskutek tego proces nigdy nie
zakończy swojej pracy - powstanie sytuacja głodzenia procesu, która będzie wymagała jakiegoś
praktycznego rozwiązania. Należy zapewnić, by proces mógł być wydelegowany do roli ofiary tylko
skończoną (małą) liczbę razy. Najpowszechniejszym rozwiązaniem jest uwzględnienie liczby wycofań
przy ocenie kosztów.

6. 7. Łączenie metod postępowania z blokadami.

Podstawowe strategie obsługi blokad (zapobieganie, unikanie i wykrywanie) zastosowane indywidualnie
nie nadają się do rozwiązywania wszystkich problemów związanych z przydzielaniem zasobów w
systemach operacyjnych. Jedną z możliwości jest połączenie tych trzech podstawowych metod,
pozwalające na uzyskanie optymalnego podejścia dla poszczególnych klas zasobów w systemie.
Proponowana metoda jest oparta na spostrzeżeniu, iż zasoby można podzielić na hierarchicznie
uporządkowane klasy. W obrębie klas można dobierać najodpowiedniejsze sposoby postępowania z
blokadami.

Łatwo wykazać, że system, w którym zastosuje się tą strategię, nie będzie zależny od blokad. Dzięki
uporządkowaniu zasobów, blokady nie będą mogły dotyczyć więcej niż jednej klasy. Wewnątrz danej
klasy będzie stosowana jedna z podstawowych metod. W efekcie system będzie wolny od skutków
blokad. Aby zobrazować tę technikę, rozważymy system składający się z następujących czterech klas
zasobów:



Zasoby wewnętrzne.

Zasoby używane przez system, takie jak bloki kontrolne procesów.



Pamięć główna.

Pamięć używana przez zadanie użytkownika.



Zasoby zadania.

Przydzielane urządzenia (w rodzaju przewijaków taśmy) i pliki.



Wymienny obszar pamięci.

Obszar w pamięci pomocniczej, przeznaczony na poszczególne zadania użytkowników.

Możliwe mieszane rozwiązanie problemu blokad w tym systemie klasy w sposób pokazany powyżej i
stosuje następujące metody do każdej z klas:



Zasoby wewnętrzne.

Można zapobiegać powstawaniu blokad dzięki uporządkowaniu zasobów, ponieważ zawsze można obraz
zadania przesłać do pamięci pomocniczej, co pozwala na wywłaszczenie procesów z pamięci głównej.



Pamięć główna.

Można zapobiegać powstawaniu blokad stosując wywłaszczanie, ponieważ zawsze można obraz zadania
przesłać do pamięci pomocniczej, co pozwala na wywłaszczanie procesów z pamięci głównej.



Zasoby zadania.

Można zastosować technikę unikania blokad, ponieważ niezbędna informacja o zapotrzebowaniu na
zasoby może być uzyskana z kart sterujących zadania.



Wymienny obszar pamięci.

Można zastosować wstępny przydział, ponieważ maksymalne wymagania na pamięć są na ogół znane.

Przykład powyższy ukazuje, w jaki sposób, w ramach uporządkowania zasobów, można łączyć ze sobą
różne podstawowe podejścia w celu efektywnego rozwiązania problemu blokady.

6.8. Podsumowanie

Stan blokady występuje wtedy, gdy dwa lub więcej procesów czeka w nieskończoność na zdarzenie,
które może być spowodowane przez jeden z tych czekających procesów. Mówiąc ogólnie, są dwie
metody postępowania z blokadami:



zastosować pewien protokół zapewniający, że system nigdy nie wejdzie w stan blokady.



pozwolić systemowi na popadanie w blokadę, i wycofywanie się z niej.

Blokada może wystąpić wtedy i tylko wtedy. gdy w systemie są spełnione jednocześnie cztery konieczne
warunki: wzajemne wyłączanie, przetrzymywanie i oczekiwanie, brak wywłaszczeń i czekanie cykliczne.
Aby zapobiegać blokadzie, należy zapewnić, że przynajmniej jeden z tych czterech warunków
koniecznych nigdy nie będzie spełniony. Istnieją trzy podstawowe metody zapobiegania blokadzie:



Przetrzymywanie i oczekiwanie.

Przed rozpoczęciem wykonywania każdy proces musi otrzymać wszystkie potrzebne mu zasoby.



Brak wywłaszczeń.

Jeśli proces utrzymuje jakieś zasoby i zamawia inny zasób, który nie może być mu natychmiast
przydzielony (tzn. proces musi czekać), to proces musi zwolnić wszystkie swoje bieżące zasoby.



Czekanie cykliczne.

Wymusza się liniowe uporządkowanie wszystkich typów zasobów. Każdy proces może zamawiać zasoby
tylko we wzrastającym porządku.

Odmienna metoda unikania blokad, mniej rygorystyczna od poprzedniego algorytmu zapobiegania,
sprowadza się do pozyskania z góry informacji o przyszłym użytkowaniu zasobów przez każdy z
procesów. Algorytm bankiera wymaga znajomości maksymalnej liczby zasobów każdej klasy, które
mogą być zamawiane przez proces. Używając tej informacji można zdefiniować algorytm unikania
blokady. Jeśli w systemie nie zastosowano żadnego protokołu zapewniającego, że blokada nie może
wystąpić, to trzeba posłużyć się schematem wykrywania i usuwania blokady z systemu. Aby określić, czy
wystąpiła blokada, należy wykonać algorytmy wykrywania blokady. W wypadku wykrycia blokady,
system musi z niej wychodzić za pomocą przedwczesnego kończenia niektórych z zablokowanych
procesów albo przez wywłaszczanie niektórych z nich z pewnych zasobów.

W systemie, w którym wybór ofiar do wycofania zależy w głównej mierze od oceny kosztów, może
wystąpić przypadek nieskończonego oczekiwania na zasoby. W jego wyniku wybrany proces nigdy nie
zakończy wyznaczonej pracy.

Wykazano na koniec, że żadna z podstawowych metod z osobna nie wystarcza do rozwiązywania
wszystkich problemów przydziału zasobów w systemach operacyjnych. Podstawowe metody można
stosować łącznie na zasadzie dokonywania oddzielnych wyborów optymalnego postępowania z
poszczególnymi klasami zasobów w systemie.

7. Zarządzanie pamięcią.

Aby umieszczać kilka procesów naraz w pamięci operacyjnej , trzeba dzielić między nie pamięć.

Do tego stosuje się różne metody zarządzania pamięcią , zależnie od wielu czynników ale przede wszystkim od sprzętu.
Obowiązuje jedno podstawowe założenie ograniczające dla algorytmów przedstawionych w tym rozdziale przed
wykonaniem programu lub procesu cały musi być załadowany do pamięci fizycznej co ogranicza wielkość procesu
wielkością pamięci fizycznej.

7.1. Podstawy.

Pamięć jest wielką tablicą poadresowanych słów lub bajtów. Współpraca z pamięcią polega na tworzeniu ciągu operacji
czytania lub pisania odnoszących się do konkretnych adresów pamięci.

Typowy cykl wykonania rozkazu :



pobranie go z pamięci



dekodowanie rozkazu



pobranie z pamięci argumentów



wyniki operacji na argumentach zwrócone do pamięci.

7.1.1 Wiązanie adresów.

Zbiór procesów czekających na dysku do załadowania tworzy kolejkę wejściową , wybrany proces zostaje załadowany do
pamięci. Powodować to może czasem przesunięcie adresów lub odpowiednie powiązanie zewnętrznych odniesień z punktami
wejściowymi. ( to zdanie jest dla mnie niejasne nie biorę za nie odpowiedzialności przyp. Tłum.).Podczas wykonywania
programu proces pobiera rozkazy i dane z pamięci.

Po pewnym czasie proces kończy działanie i zajmowana przez niego pamięć staje się ponownie dostępna.

Proces użytkownika może rezydować w dowolnej części pamięci fizycznej. W większości przypadków program użytkownika
zanim zostanie wykonany , przechodzi przez kilka faz . Podczas tych faz reprezentacja adresów może ulec zmianie. W
programie źródłowym adresy są wyrażone w sposób symboliczny. Kompilator na ogół wiąże te adresy z adresami
względnymi. Program łączący lub ładujący wiąże te adresy względne z adresami bezwzględnymi. Każde wiązanie jest
odwzorowaniem z jednej przestrzeni adresowej na inną.

Powiązanie rozkazów i danych z adresami pamięci może w zasadzie zostać wykonane w dowolnym kroku poniższego ciągu
działań :

Czas kompilacji

Jeśli podczas kompilacji jest znane miejsce , w którym proces będzie przebywał w pamięci, to można wygenerować kod
bezwzględny. Wtedy adres startowy procesu będzie adresem bezwzględnym.

Przy zmianie tego adresu trzeba przeadresować kod i rekompilować program.

Czas ładowania

Nieznany jest podczas kompilacji adres startowy , dlatego kompilator tworzy kod przemieszczalny (relokowalny) . Wtedy
ostateczne wiązanie jest opóźniane do czasu ładowania. Przy zmianie adresu startowego wystarczy tylko przeładować
program.

Czas wykonania

Jeśli proces może ulegać przemieszczeniom z jednego miejsca w pamięci do innego podczas swojego wykonania, to trzeba
zaczekać z wiązaniem adresów aż do czasu wykonania. Wymaga to zastosowania specjalnego sprzętu

Wieloetapowe przetwarzanie programu użytkownika :

Program źródłowy ?kompilator lub asembler (czast translacji) ?moduł wynikowy ? program łączący ?

(Inne moduły wynikowe ^) |-------------------------czas ładowania ------------------------------|

moduł ładowalny ? program ładujący ?program wynikowy zakodowany dwójkowo ( czas wykonywania )

(biblioteka systemowa ^) (biblioteka systemowa ładowalna dynamicznie ^).

7.1.2. Ładowanie dynamiczne.

Metoda ładowania dynamicznego

polega na tym , że podprogram , który nie został wywołany nie jest

wprowadzany do pamięci. Do pamięci wprowadzany jest program główny i tam jest wykonywany. Gdy
jakiś podprogram chce wywołać jakiś inny podprogram musi sprawdzić czy znajduje się on w pamięci ,
jeśli nie ma to trzeba wywołać program ładujący i łączący moduły przemieszczalne, który wprowadzi do
pamięci potrzebny podprogram oraz uaktualni tablice odzwierciedlające te zmianę, po czym można
przekazać sterowanie do tego załadowanego podprogramu.

Dzięki ładowaniu dynamicznemu nigdy nie zostanie załadowany podprogram , którego się nie używa.

7.1.3. Łączenie dynamiczne.

Opóźnia się łączenie do czasu wykonania. Dotyczy to zazwyczaj bibliotek systemowych. Jeśli nie ma tej właściwości w
systemie, to wszystkie programy muszą mieć własne kopie bibliotek dołączone do swoich kodów dwójkowych. Powoduje to
marnotrawstwo przestrzeni dyskowej i obszaru pamięci głównej.

W przypadku łączenia dynamicznego w miejscu odwołanie programu do funkcji biblioteki znajdują się tylko zakładki.
Zakładka jest małym fragmentem kodu, wskazującym jak odnaleźć odpowiedni, rezydujący w pamięci podprogram
biblioteczny. Wykonanie tej zakładki powoduje zastąpienie jej przez adres podprogramu bibliotecznego i wykonanie tego
podprogramu. W ten sposób przy następnym napotkaniu danego fragmentu kodu, podprogram biblioteczny będzie
wykonywany bezpośrednio, bez ponoszenia kosztów na dynamiczne łączenie. W tym schemacie wszystkie procesy
korzystające z biblioteki języka programowania wykonują tylko jedną kopię kodu bibliotecznego.

Cechę tę można rozszerzyć na aktualizację bibliotek . Biblioteka może zostać zastąpiona nową wersją i wszystkie odwołujące
się do niej programy będą automatycznie używały nowej wersji.

Bez dynamicznego łączenia wszystkie takie programy musiałyby zostać od nowa połączone, aby uzyskać dostęp do nowej
biblioteki. Aby programy nie mogły przypadkowo korzystać z nowych nie w pełni zgodnych z dotychczasowymi wersji
bibliotek , informację o wersji dołącza się zarówno do programu, jak i do biblioteki. Do pamięci może być wówczas
załadowana więcej niż jedna wersja biblioteki, ponieważ każdy program posłuży się własną informacją o wersji , by wybrać
właściwą bibliotekę. Przy niewielkich zmianach zachowuje się numer wersji, natomiast większe zmiany powodują jego
zwiększenie. Zatem tylko programy skompilowane z nową wersją biblioteki są narażone na zawarte w niej niezgodności,
powstałe na skutek dokonanych zmian. Inne programy, dołączone przed zainstalowaniem nowej biblioteki, będą nadal
wykonywane przy użyciu starej biblioteki. System tego rodzaju bywa nazywany bibliotekami dzielonymi.

7.1.4. Nakładki.

Wymaganie , aby cała logiczna przestrzeń adresowa procesu znajdowała się w pamięci fizycznej zanim proces zacznie się
wykonywać, ogranicza wielkość procesu do rozmiaru pamięci fizycznej. Czasami aby zwiększyć wymiary procesu ponad ilość
zajmowanej przez niego pamięci, stosuje się technikę nakładania.

Idea polega na przechowywaniu w pamięci tylko tych rozkazów i danych , które są stale potrzebne. Inne rozkazy są ładowane
w miarę zapotrzebowań do miejsca zajmowanego uprzednio przez rozkazy już zbyteczne.

Kody np. dwóch nakładek są przechowywane na dysku w postaci obrazów bezwzględnych pamięci i czytane przez program
obsługi nakładek w zależności od potrzeb. Do konstruowania nakładek są potrzebne specjalne algorytmy przemieszczania i
łączenia.

Przy projektowaniu i programowaniu nakładek trzeba bardzo dobrze znać strukturę programu , co przy dużych z założenia
programach jest bardzo trudne , dlatego użycie nakładek ogranicza się jedynie do mikrokomputerów i innych systemów o
ograniczonej ilości pamięci fizycznej i nie mających środków sprzętowych, umożliwiających użycie bardziej zaawansowanych
technik.

7.2. Wymiana.

Wykonanie procesu jest możliwe wówczas gdy jest on w pamięci. Jednakże proces może być tymczasowo wymieniany, tj.
odsyłany z pamięci głównej do pamięci pomocniczej i z powrotem w celu kontynuowania działania.

Dla na przykład wieloprogramowego środowiska sterowanego rotacyjnym algorytmem przydziału procesora :

Po wyczerpaniu kwantu czasu zarządca pamięci rozpoczyna wymianę zakończonego procesu na proces, który zajmie
zwolnione miejsce w pamięci. Równocześnie planista przydziału procesora przydzieli kwant czasu innemu procesowi w
pamięci. Każdy proces po zużyciu kwantu czasu zostanie wymieniony z innym procesem.

W idealnych warunkach zarządca pamięci może wymieniać procesy wystarczająco szybko na to , aby w pamięci były zawsze
procesy gotowe do wykonania wtedy, kiedy planista przydziału procesora zachce dokonać kolejnego jego przydziału. Kwant
czasu musi być także dostatecznie duży, aby między kolejnymi wymianami można było wykonać sensowną porcję obliczeń.

Wariant wymiany stosuje się w algorytmach planowania priorytetowego :

Jeżeli nadejdzie proces o wyższym priorytecie i zażąda obsługi, to zarządca pamięci może z niej usunąć proces o niższym
priorytecie, umożliwiając załadowanie i wykonanie procesu o wyższym priorytecie.

Gdy proces o wyższym priorytecie zakończy działanie, wówczas proces o niższym priorytecie może być z powrotem
wprowadzony do pamięci i kontynuowany. Ten wariant wymiany nazywany jest również zwijaniem i rozwijaniem.

Zazwyczaj proces , który ulegnie wymianie, powraca do pamięci w to samo miejsce, w którym przebywał uprzednio.
Ograniczenie to jest podyktowane metodą wiązania adresów.

Jeśli wiązanie jest wykonywane podczas tłumaczenia lub ładowania, to proces nie może być przesunięty w inne miejsce
pamięci. Jeśli używa się wiązania podczas wykonania, to istnieje możliwość sprowadzenia procesu do innego obszaru pamięci.

Do wymiany potrzebna jest pamięć pomocnicza. Jest nią na ogół szybki dysk. Musi on być wystarczająco pojemny, aby
pomieścić wszystkie kopie obrazów pamięci programów wszystkich użytkowników. Powinien także umożliwiać bezpośredni
dostęp do tych obrazów pamięci. System utrzymuje kolejkę procesów gotowych, składającą się ze wszystkich procesów,
których obrazy pamięci są w pamięci pomocniczej lub operacyjnej i które są gotowe do wykonania. Ilekroć planista przydziału
procesora decyduje się wykonać proces, tylekroć wywołuje program koordynujący, który sprawdza, czy następny proces z
kolejki jest w pamięci operacyjnej. Jeśli proces jest tam nieobecny i nie ma wolnego obszaru pamięci, to program
koordynujący odsyła na dysk któryś z procesów przebywających w pamięci i na jego miejsce wprowadza potrzebny proces.
Następnie jak zwykle uaktualnia stany rejestrów i przekazuje sterowanie do wybranego procesu.

Czas przełączania kontekstu w systemie, w którym stosuje się wymianę, jest dość długi. Aby wykorzystanie procesora było
wydajne, należy zadbać o względnie długi czas wykonania każdego procesu w stosunku do czasu wymiany.

Główną część czasu wymiany stanowi czas przesyłania. Łączny czas przesyłania jest wprost proporcjonalny do ilości
wymienianej pamięci. Warto więc wiedzieć ile pamięci zajmuje proces użytkownika, a nie tylko ile może on zajmować.
Należy wówczas wymieniać tylko to, co jest aktualnie używane skracając czas wymiany. Aby schemat ten był efektywny,
użytkownik musi informować system operacyjny o każdej zmianie zapotrzebowania na pamięć. Zatem w procesie z
dynamiczną gospodarką pamięcią trzeba korzystać z funkcji systemowych służących do zamówienia pamięci i zwolnienia
pamięci w celu informowania systemu operacyjnego o zmieniających się potrzebach.

Z wymianą są związane również inne ograniczenia. Jeśli chcemy dokonać wymiany procesu, to musimy mieć pewność, że
proces jest zupełnie bezczynny. Szczególną uwagę należy zwrócić na trwające operacje we/wy . Jeśli proces czeka z powodu
operacji we/wy, to możemy mieć ochotę usunąć go z pamięci , aby uzyskać wolne miejsce. Wszakże jeśli operacja we/wy ma
asynchroniczny dostęp do buforów w pamięci użytkownika, to proces nie może ulec wymianie. Załóżmy , że operacja we/wy
została ustawiona w kolejce, ponieważ było zajęte urządzenie. Wówczas, gdyby wysłano z pamięci proces P1 i zastąpiono go
obrazem procesu P2, operacja we/wy mogłaby usiłować użyć pamięci należącej obecnie do procesu P2. Istnieją dwa
rozwiązania tego problemu:

nigdy nie wymieniać procesu , w którym trwają operacje we/wy.

Wykonywać operacje we/wy tylko za pośrednictwem buforów systemu operacyjnego.Przesyłanie danych między
systemem operacyjnym , a pamięcią procesu nastąpi wówczas po powtórnym wprowadzeniu procesu do pamięci.

Obecnie standardową wymianę stosuje się w niewielu systemach.

7.3. Przydział pojedynczego obszaru.

Prostym schematem zarządzania pamięcią jest podział na dwie części jednej dla użytkownika i jednej dla rezydującego
systemu operacyjnego. System operacyjny można umieścić w pamięci dolnej albo górnej. Zależy to głównie od lokalizacji
wektora przerwań. Ponieważ wektor przerwań znajduje się często w pamięci dolnej, częstszym rozwiązaniem jest
umieszczenie systemu operacyjnego w pamięci dolnej. Z tego powodu rozważać będziemy sytuację, w której system
operacyjny rezyduje w pamięci dolnej. Postępowanie w drugim przypadku jest podobne.

Jeśli system operacyjny pozostaje w pamięci dolnej , a w górnej wykonuje się proces użytkownika, to powstaje potrzeba
ochrona kodu i danych systemu operacyjnego przed zmianami (przypadkowymi lub złośliwymi), które może spowodować
proces użytkownika. Ochrony tej musi dostarczać sprzęt, w którym służą do tego celu rejestry: bazowy i graniczny. Gdy tylko
jeden użytkownik korzysta z pamięci, to rejestr graniczny nie jest niezbędnie potrzebny.

Następnym problemem do rozważenia jest ładowanie procesów użytkownika do pamięci. Pierwszy adres programu
użytkownika jest pierwszym adresem powyżej wartości rejestru bazowego. Jeśli adres bazowy jest znany podczas kompilacji,
to można wygenerować kod bezwzględny. Kod taki zacznie się od adresu bazowego i będą w nim występować adresy większe
niż adres bazowy. Ewentualna późniejsza zmiana adresu bazowego pociągnęłaby za sobą konieczność powtórnego
kompilowania takiego kodu. W związku z tym kompilator może generować kod przemieszczalny. W tym przypadku wiązanie
opóźnia się do czasu ładowania. Gdyby zmienił się adres bazowy, wówczas kod użytkowy będzie wymagać tylko ponownego
załadowania z uwzględnieniem tej zmiany.

Niewygodą tego schematu jest statyczna wartość adresu bazowego podczas wykonywania programu. W istocie jeżeli adresy
użytkownika są powiązane z adresami fizycznymi przez użycie bazy, zmiana bazy spowoduje ich delegalizację. Tak więc
adres bazowy może być zmieniany tylko wtedy, gdy nie jest wykonywany żaden program użytkownika. Istnieją jednak
sytuacje , w których byłoby pożądane zmienić rozmiar systemu operacyjnego ( a zatem i położenie bazy ) podczas
wykonywania programu. Na przykład system operacyjny zawiera kod i bufory programów obsługi urządzeń. Jeśli program
obsługi jakiegoś urządzenia jest rzadko używany , to nie jest pożądane przechowywanie jego kodu i danych w pamięci , która
mogłaby być użyta do innych celów. Kod taki nazywany bywa czasem przejściowym ( ang. transient) kodem systemu
operacyjnego; pojawia się i znika stosownie do potrzeb. Używanie takiego kodu w oczywisty sposób zmienia rozmiary
systemu operacyjnego podczas wykonywania programu.

Są dwa sposoby zmodyfikowania poprzedniego podstawowego schematu w celu umożliwienia dynamicznych zmian rozmiaru
systemu operacyjnego.

Jedną metodą jest załadowanie procesu użytkownika w górnej pamięci możliwie jak najdalej od adresu bazowego, zamiast
ładowania go wprost od adresu bazowego. Ma to tę zaletę, że cały obszar nie zużytej pamięci znajduje się pośrodku i zarówno
użytkownik jak i system operacyjny mogą się rozszerzać w tej nie używanej przestrzeni wedle potrzeb. Bardziej ogólnym
podejściem jest opóźnienie wiązania adresów do czasu wykonania. Wymaga ono nieco innego wsparcia sprzętowego. Wartość
rejestru bazowego jest dodawana do każdego adresu wytwarzanego przez proces użytkownika w chwili odwoływania się do
pamięci.

Zwróćmy uwagę , że program użytkownika nigdy nie ma do czynienia z rzeczywistymi adresami fizycznymi. Przemieszczeniu
względem rejestru bazowego adres ulegnie tylko wtedy, gdy zostanie użyty w roli adresu pamięci (np. w operacji pośredniego
pobrania zawartości pamięci lub pośredniego przesłania do pamięci). Program użytkownika działa na adresach logicznych.
Sprzęt odwzorowujący pamięć zamienia adresy logiczne na adresy fizyczne. Ostateczna komórka, do której odnosi się adres
pamięci, jest nieokreślona do chwili wykonania danej operacji.

W przypadku takiego sprzętu, do zmiany komórki początkowej wystarczy zmiana zawartości rejestru bazowego i przesłanie
całe pamięci użytkownika do właściwych komórek względem nowej wartości bazy. Postępowanie takie wymaga kopiowania
sporej ilości pamięci, ale pozwala na zmianę bazy w dowolnej chwili.

Mamy więc do czynienia z dwoma rodzajami adresów : adresami logicznymi ( <0;max> ) i adresami fizycznymi ( <R;R+max>
gdzie R wartość bazy ). Użytkownik operuje tylko adresami logicznymi i ma wrażenie, że proces działa w komórkach od 0 do
max. System operacyjny ma lepsze informacje i może sięgać do pamięci fizycznej bezpośrednio, w trybie pracy monitora. Cała
informacja przekazywana od procesu użytkownika do sytemu operacyjnego musi być przed użyciem jawnie
przeadresowywana przez oprogramowanie systemu operacyjnego. Jest to szczególnie ważne przy adresach dotyczących
urządzeń we/wy. Program użytkownika zawiera adresy logiczne; zanim adresy te zostaną użyte, muszą zostać odwzorowane
na adresy fizyczne.

Koncepcja logicznej przestrzeni adresów powiązanej z oddzieloną od niej fizyczną przestrzenią adresów jest podstawą
właściwego zarządzania pamięcią.

7.4. Przydzielanie wielu obszarów.

Problem zarządzania pamięcią polega na przydzielaniu pamięci rozmaitym procesom pozostającym w kolejce wejściowej w
oczekiwaniu na wprowadzenie do pamięci.

Jednym z najprostszych schematów przydziału jest podzielenie pamięci na pewną liczbę obszarów o ustalonym rozmiarze.
Każdy obszar może zawierać dokładnie jeden proces. Stopień wieloprogramowości jest ograniczony przez liczbę obszarów.
Kiedy powstaje wolny obszar, następuje wybranie jakiegoś procesu z kolejki wejściowej i wprowadzenie go do tego obszaru.
Gdy proces kończy działanie, zajmowany przez niego obszar zwalnia się dla innego procesu. Taki schemat nie jest jednak
obecnie używany.

7.4.1. Schemat podstawowy.

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

. G

dy przybywa

proces z zapotrzebowaniem na pamięć, poszukuje się dla niego wystarczająco obszernej dziury. Jeśli zostanie znaleziona,
przydziela się z niej pamięć tylko w niezbędnej ilości, pozostawiając resztę na przyszłe potrzeby.

Na ogół w każdej chwili istnieje zbiór dziur o różnych wymiarach, rozproszonych po całej pamięci. Gdy proces nadchodzi i
zamawia pamięć, wtedy przegląda się ten zbiór w poszukiwaniu dziury wystarczająco dużej dla danego procesu. Jeśli dziura
jest zbyt wielka, dzieli się ją na dwie: jedna część zostaje przydzielona przybyłemu procesowi, druga wraca do zbioru dziur.
Gdy proces kończy pracę, wówczas zwalnia swój blok pamięci , który znów zostaje umieszczony w zbiorze dziur. Jeśli nowa
dziura przylega do innej dziury , to łączy się je tworząc jedną większą dziurę. Należy wówczas sprawdzić, czy jakieś procesy
oczekują na pamięć, oraz czy nowo utworzona dziura może spełnić wymagania któregoś z tych oczekujących procesów.

Powstaje problem przydziału konkretnej dziury konkretnemu procesowi . Rozwiązuje się go za pomocą jednej ze strategii :

Pierwsza pasująca

Przydziela się pierwszą dziurę o wystarczającej wielkości. Można rozpocząć szukanie od początku wykazu dziur lub od
miejsca, w którym zakończono ostatnie szukanie. Kończy się szukać z chwilą napotkania dostatecznie dużej wolnej dziury.

Najlepiej pasująca

Przydziela się najmniejszą z dostatecznie dużych dziur. Należy przejrzeć całą listę, chyba że jest ona uporządkowana według
rozmiarów. Ta strategia zapewnia najmniejsze pozostałości po przydziale.

Najgorzej pasująca

Przydziela się największą dziurę. Również w tym przypadku trzeba przeszukać całą listę, chyba że
jest ona uporządkowana według wymiarów. Strategia taka pozostawia po przydziale największą
dziurę, która może okazać się bardziej użyteczna niż dziura pozostała w wypadku strategii
najlepiej pasującej dziury.

Lepsze są dwie pierwsze strategie , lecz wśród nich żadna nie jest dominująca pod względem zużycia pamięci lecz 1-sza jest
szybsza.

Opisane algorytmy są obarczone zewnętrzną fragmentacją W trakcie ładowania i usuwania procesów z pamięci, przestrzeń
wolnej pamięci dzieli się na małe kawałki. Istnienie zewnętrznej fragmentacji objawia się tym, że suma wolnych obszarów w
pamięci wystarcza na spełnienie zamówienia, ale nie stanowi spójnego obszaru. Pamięć jest podzielona na dużą liczbę małych
dziur. W zależności od ogólnej ilości miejsca w pamięci i średniej długości procesu, zewnętrzna fragmentacja może stanowić
błahy lub poważny problem. Przy metodzie pierwsza pasująca może ginąć nawet do jednej trzeciej pamięci z powodu
fragmentacji.

Ponieważ w pamięci rezyduje w tym samym czasie kilka procesów. Powinna istnieć jakaś jej ochrona. Ochronę pamięci
można osiągnąć przez użycie dwóch rejestrów bazowego i granicznego. Rejestry te pozwalają na dynamiczne
przemieszczanie procesów podczas ich wykonywania. Rejestr bazowy zawiera wartość najmniejszego adresu fizycznego;
rejestr graniczny zawiera zakres adresów logicznych. Gdy korzysta się z tych rejestrów, wówczas każdy adres logiczny musi
być mniejszy od wartości rejestru granicznego; z kolei każdy adres logiczny ulega dynamicznemu przemieszczeniu przez
dodanie do niego wartości z rejestru bazowego. Dopiero tak przekształcony adres dociera do pamięci.

Gdy planista przydziału procesora wybierze proces, wówczas program koordynujący ładuje odpowiednie wartości do rejestru
bazowego i do rejestru granicznego. Ponieważ każdy adres wygenerowany przez procesor porównywany jest z zawartością
tych rejestrów, jest możliwa ochrona programów i danych innych użytkowników przed modyfikacją przez bieżący proces.

Przy zastosowaniu tego schematu powstaje jeszcze inny problem. Weźmy pod uwagę dziurę wielkości 18464 bajtów.
Załóżmy, że następny proces wymaga 18462 bajtów. Jeśli przydzielimy dokładnie zamówiony blok, to pozostaną dwa nie
zajęte bajty. Nakład na trzymanie informacji o takiej dziurze znacznie przekroczy jej wielkość. Na ogół stosuje się metodę
przyłączania bardzo małych dziur do większych zamówień. W ten sposób przydzielona pamięć może być nieco większa niż
żądana. Różnica między tymi dwiema wielkościami stanowi wewnętrzną fragmentację pamięci, czyli efekt pozostawienia
niewykorzystanego fragmentu pamięci wewnątrz przydzielonego obszaru.

7.4.2. Planowanie długoterminowe.

W każdej chwili jest znana lista rozmiarów dostępnych bloków oraz kolejka wejściowa. Planista długoterminowy 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ęć kolejnego procesu nie może być spełnione; żaden dostępny blok pamięci ( dziura )
nie jest wystarczająco duży, żeby pomieścić proces. Planista długoterminowy może wówczas czekać na pojawienie się
dostatecznie dużego bloku lub może przeskoczyć dany proces w kolejce, aby sprawdzić, czy któryś z procesów o niższym
priorytecie nie ma odpowiednio mniejszych wymagań pamięciowych. Decyzja taka prowadzi do wyboru między planowaniem
z przeskokami i bez.

W takim schemacie nie ma fragmentacji wewnętrznej ( lub nieznaczna ) natomiast może istnieć fragmentacja zewnętrzna.

Fragmentacja pamięci może stanowić poważny problem. W najgorszym przypadku może dochodzić do powstawania bloków
wolnej ( marnowanej pamięci ) między każdymi dwoma procesami. Gdyby cała ta pamięć mogła stanowić jeden wolny blok,
można by było wykonać więcej procesów. Wybory według strategii pierwszy pasujący blok lub blok najlepiej pasujący
mogą mieć wpływ na rozmiar fragmentacji. Osobny czynnik stanowi decyzja na którym końcu obszaru wystąpi wolny blok
(gdzie ulokuje się pozostałość po przydziale w górnej czy dolnej części obszaru przydzielonej pamięci ? ) . Niezależnie od
użytego algorytmu, zewnętrzna fragmentacja pamięci pozostanie problemem do rozwiązania.

7.4.3. Upakowanie pamięci.

Jednym z rozwiązań problemu zewnętrznej fragmentacji pamięci jest upakowanie. Chodzi o takie poprzemieszczanie
zawartości pamięci, aby cała wolna pamięć znalazła się w jednym wielkim bloku. Upakowanie pamięci nie zawsze jest
możliwe. Aby procesy mogły pracować w nowych miejscach pamięci, należy przemieścić ich wszystkie wewnętrzne adresy.
Jeśli przemieszczanie jest statyczne i wykonane podczas tłumaczenia lub ładowania, to upakowanie nie jest możliwe.
Możliwość upakowania daje tylko dynamiczne przemieszczanie adresów, wykonywane podczas działania procesu.

Jeśli adresy są przemieszczane dynamicznie, to przemieszczanie procesu sprowadza się do przesunięcia programu i danych
oraz do zmiany zawartości rejestru bazowego dla odzwierciedlenia nowego adresu bazowego.

Schemat upakowywania pamięci może polegać na przesunięciu wszystkich procesów w kierunku jednego końca pamięci
zwalniając drugi koniec, gdzie tworzy się jeden wielki blok wolnej pamięci. Schemat ten jest bardzo kosztowny.

Wybranie optymalnej strategii upakowywania jest dość trudne , bo wymaga takiego przesuwania danych , by otrzymać jak
największą dziurę przesuwając jak najmniej bajtów pamięci.

Z upakowaniem może być połączona wymiana. Proces może zostać wysłany z pamięci głównej do pomocniczej i
wprowadzony na powrót w późniejszym terminie. Po wysłaniu procesu z pamięci, zostaje ona zwolniona i może być
zagospodarowana przez inny proces. Z powrotem procesu do pamięci wiąże się jednak kilka kłopotów. W przypadku
statycznego przemieszczania proces powinien być wprowadzony w dokładnie to samo miejsce, które zajmował przed
wymianą. To ograniczenie może powodować konieczność usunięcia z pamięci innego procesu w celu zwolnienia miejsca.

Jeśli stosuje się przemieszczanie dynamiczne (np. przy użyciu rejestrów bazowego i granicznego ), to proces może zostać
wysłany do innego miejsca w pamięci. W tym przypadku odnajduje się wolny blok pamięci, dokonując w razie potrzeby
upakowania, i umieszcza w nim proces.

Jedna z metod upakowywania polega na usuwaniu z pamięci procesów, które mają być przesłane do innego miejsca, i
wprowadzeniu ich na nowe miejsca. Jeśli wymiana procesów, czyli ekspediowanie ich z pamięci głównej do pomocniczej i z
powrotem, stanowi już część systemu, to dodatkowy kod realizujący upakowywanie może być minimalny.

7.5. Zwielokrotnione rejestry bazowe.

By zmniejszyć zewnętrzną fragmentację można podzielić pamięć wymaganą przez proces na kilka części. Każda część jest
mniejsza od całości więc łatwiej jest ją upakować w pamięci. Podejście takie wymaga zwielokrotnienia rejestrów bazowych
oraz mechanizmu tłumaczenia adresów logicznych na fizyczne.

Jedną z realizacji jest podzielenie pamięci na dwie rozłączne części. System ma dwie pary rejestrów bazowego i
granicznego. Pamięć jest podzielona na dwie połowy w zależności od wartości najbardziej znaczącego bitu w adresie. Bazę
pamięci dolnej i jej ograniczenie określa jedna para rejestrów, bazę i ograniczenie górnej druga.

Na zasadzie umowy, kompilatory i asemblery umieszczają dane przeznaczone wyłącznie do czytania ( stałe i rozkazy ) w
pamięci górnej, zmienne zaś w pamięci dolnej. Każdej parze rejestrów jest przyporządkowany bit ochrony, dzięki któremu
można wymusić traktowanie pamięci górnej jako przeznaczonej tylko do czytania. Takie rozwiązanie pozwala na dzielenie
programów (przechowywanych w pamięci górnej jako tylko do czytania ) między wiele procesów użytkowych, z których
każdy ma własny, odrębny segment w pamięci dolnej.

Inny sposób polega na wydzieleniu w programie dwóch części : kodu i danych. Procesor wie, czy jest potrzebny rozkaz czy
dane. W związku z tym używa się dwu par rejestrów bazowego i granicznego po jednej dla rozkazów i danych. Para
rejestrów bazowego i granicznego dla rozkazów automatycznie służy jedynie do czytania, więc programy mogą być dzielone
między różnych użytkowników.

7.6. Stronicowanie.

Stronicowanie pozwala na to , aby pamięć procesu była nieciągła, a zatem można przydzielać procesowi pamięć fizyczną w
tych miejscach, w których nie jest ona zajęta. Stosując stronicowanie omija się też problem dopasowywania kawałków pamięci
o zmiennych rozmiarach do miejsca w pamięci pomocniczej, co jest bolączką większości uprzednio omówionych schematów.

7.6.1. Sprzęt

Pamięć fizyczną dzieli się na bloki o 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 jego strony, przebywające w
pamięci pomocniczej, są wprowadzane w dowolne ramki. 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. W
połączeniu z odległością na stronie, adres bazowy definiuje adres fizyczny pamięci posyłany do jednostki pamięci.

7.6.2. Planowanie długoterminowe.

Gdy proces zostaje przedłożony do wykonania, wówczas planista długoterminowy sprawdza jego rozmiar. Rozmiar procesu
wyraża się w stronach. Następnie planista długoterminowy szuka wolnej pamięci, przeglądając listę nie przydzielonych ramek.
Dla każdej strony procesu użytkownika potrzeba jednej ramki. Zatem, jeśli proces wymaga n stron, to trzeba znaleźć w
pamięci n ramek. Jeśli istnieje n swobodnych ramek , to planista długoterminowy przydzieli je procesowi. Pierwsza strona
procesu będzie załadowana do którejś z przydzielonych ramek, a numer tej ramki wpisany do tablicy stron danego procesu.
Następną stronę wprowadzi się do innej ramki, numer ramki do tablicy stron itd.

Każda wolna ramka może być przydzielona potrzebującemu jej procesowi. Może tu wszakże wystąpić fragmentacja
wewnętrzna. Zauważmy, że ramki są przydzielane jako jednostki o ustalonej wielkości. Jeśli wymagania pamięciowe procesu
nie odpowiadają dokładnie wielokrotności rozmiaru ramek, to ostatnia przydzielona ramka nie będzie całkowicie wypełniona.
W najgorszym przypadku proces może potrzebować n stron plus jedno słowo. Przydzieli mu się n+1 ramek, z czego straty z
powodu wewnętrznej fragmentacji będą wynosić prawie całą ramkę. Jeśli rozmiar procesu jest niezależny od rozmiaru strony,
to można oczekiwać, że wewnętrzna fragmentacja wyniesie pół strony na proces. Z rozważań tych wynika , że
odpowiedniejsze byłyby małe rozmiary strony. Wszelako z każdą stroną wiążą się dodatkowe koszty spowodowane
koniecznością dokonywania wpisu do tablicy stron. Ten nakład z kolei zmniejsza się wraz ze wzrostem rozmiaru strony.

Tablice stron na ogół przydziela się do każdego procesu. W bloku kontrolnym procesu, oprócz wartości innych rejestrów
przechowuje się wskaźnik do tablicy stron. Kiedy program koordynujący zostanie powiadomiony, że ma rozpocząć proces,
wtedy musi ponownie załadować rejestry użytkownika i określić właściwe wartości sprzętowej tablicy stron według
przechowywanej w pamięci tablicy stron użytkownika.

7.6.3. Implementacja tablicy stron.

Tablicę stron implementuje się jako zbiór rejestrów specjalnego przeznaczenia. Rejestry te powinny być zbudowane z układów
logicznych o wielkiej szybkości działania, aby umożliwiały wydajne tłumaczenie adresów stron. Ponieważ każde odwołanie
się do pamięci musi przejść fazę odwzorowywania strony, bardzo ważna jest wydajność mechanizmu tłumaczenia adresów.
Program koordynujący ładuje te rejestry ponownie tak samo, jak w przypadku innych rejestrów. Oczywiście rozkazy
służące do ładowania i modyfikowania rejestrów tablicy stron są wykonywane w trybie uprzywilejowanym, tak więc tylko
system operacyjny może zmieniać odwzorowania pamięci.

Rejestry stosuje się do małych tablic stron. Dla dużych stron przechowuje się ją w pamięci głównej, a rejestr bazowy tablicy
stron służy do wskazywania jej położenia. Zmiana tablic stron wymaga tylko zmiany zawartości tego rejestru, co znacznie
przyspiesza przełączaniekontekstu.

Jednak powoduje to dwukrotne odwoływania się do pamięci ( do tab. stron i właściwej ramki ), co powoduje z kolei podwójne
spowolnienie.

Rozwiązuje się to za pomocą specjalnej małej tablicy sprzętowej, zwanej rejestrami asocjacyjnymi lub buforami translacji
bliskiego otoczenia. Zbiór rejestrów asocjacyjnych jest zbudowany z wyjątkowo szybkich układów pamięciowych. Każdy
rejestr składa się z dwu części: klucza i wartości. Porównywanie danej pozycji z kluczami w rejestrach asocjacyjnych odbywa
się równocześnie dla wszystkich kluczy. Jeśli dana pozycja zostanie znaleziona, to wynikiem jest odpowiadające danemu
kluczowi pole wartości. Określenie właściwego adresu w pamięci jest bardzo szybkie, jednak stosowny sprzęt bardzo drogi.

Rejestry asocjacyjne zawierają tylko kilka pozycji z tablicy stron. Jeśli adres logiczny znajduje się w rejestrze to uzyskuje się
adres odpowiedniej ramki i dostęp jest bardzo szybki , jeśli adresu logicznego nie ma to sięga się do tablicy stron w pamięci
głównej , a znaleziony adres stosuje się oraz uzupełnia o niego rejestry asocjacyjne , by następnym razem uzyskać szybki do
niego dostęp.

Procent numerów stron odnajdywanych w rejestrach asocjacyjnych nosi nazwę współczynnika trafień.

7.6.4. Strony dzielone.

Zaletą stronicowania jest możliwość dzielenia wspólnego kodu. Jeśli kod jest wznawialny to można go podzielić pomiędzy
parę procesów. Kodem wznawialnym jest taki kod, który nie modyfikuje sam siebie. Dzięki temu kilka procesów może
wykonać ten sam kod w tym samym czasie. Każdy proces ma swoją kopię rejestrów i obszar danych do przechowywania
swoich danych podczas działania. W pamięci fizycznej wystarczy przechowywać tylko jedną kopię kodu. Tablica stron
każdego z użytkowników odwzorowuje adresy rozkazów na tę samą fizyczną kopię edytora, natomiast stronice danych są
odwzorowane na różne ramki.

7.6.5. Ochrona.

Każdej ramce jest przypisany bit ochrony, na ogół są one w tablicy stron. Bit taki określa stronę jako dostępną do czytania lub
i do czytania , i do pisania. Usiłowanie pisania na stronie przeznaczonej wyłącznie do czytania spowoduje uruchomienie
sprzętowej pułapki w systemie operacyjnym.

Procesy rzadko działają w całym zakresie swoich adresów. W rzeczywistości, procesy używają tylko małego ułamka swojej
przestrzeni adresowej. Marnotrawstwem byłoby w takim razie tworzenie tablicy stron z pozycjami dla wszystkich stron
należących do przedziału adresowego. Większość takiej tablicy pozostawałaby bezużyteczna, zajmując cenną przestrzeń
pamięci. Niektóre systemy korzystają ze sprzętu w postaci rejestru długości tablicy stron do wskazywania rozmiaru tablicy
stron. Zawartość tego rejestru jest badana przy każdym adresie logicznym w celu sprawdzenia, czy dany adres należy do
dozwolonego dla procesu przedziału. Niespełnienie tego testu powoduje błąd przekazywany na zasadzie pułapki do systemu
operacyjnego.

7.7. Segmentacja.

7.7.1. Pamięć oglądana przez użytkownika.

Użytkownik widzi pamięć jako zbiór segmentów o jakieś funkcjonalnej właściwości , moduł podprogramu , stos, tablica
symboli itp.. Każdy z tych segmentów ma zmienną długość; jest ona wewnętrznie określona przez cel, któremu segment służy
w programie. Elementy wewnątrz segmentu są identyfikowane za pomocą ich odległości od początku segmentu: pierwsza
instrukcja programu, siedemnasta pozycja w tablicy symboli itd.

Segmentacją

nazywa się schemat zarządzania pamięcią, który urzeczywistnia sposób 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ę segmentu, jak i odległość wewnątrz segmentu. Toteż
użytkownik określa każdy proces za pomocą dwóch wielkości: nazwy segmentu i odległości. Dla
ułatw

ienia implementacji segmenty są numerowane; w odniesieniach do nich; zamiast nazw używa się numerów segmentów.

Segmenty są konstruowane na przykład przy kompilacji. Dzieląc program na segmenty dla : zmiennych globalnych, stosu
wywołań procedur itd.

7.7.2. Sprzęt.

Trzeba teraz zaimplementować odwzorowanie dwuwymiarowego adresu użytkownika na adres jednowymiarowy. Robi się to
za pomocą tablicy segmentów. Adres logiczny składa się z dwu części s numer segmentu i d odległości w tym segmencie.
Numer segmentu służy jako indeks do tablicy segmentów. Każda pozycja w tablicy segmentów składa się z bazy segmentu i
granicy segmentu. Odległość d adresu logicznego musi zawierać się w przedziale od 0 do granicy segmentu. Odległość d
adresu logicznego musi zawierać się w przedziale od 0 do granicy segmentu. Jeśli tak nie jest, to uaktywnia się pułapka w
systemie operacyjnym (adres logiczny poza końcem segmentu ) . Gdy odległość jest poprawna, wówczas dodaje się ją do bazy
segmentu w celu wytworzenia fizycznego adresu potrzebnego słowa. Tablica segmentów jest zatem wykazem par rejestrów
bazy i granicy.

7.7.3. Implementacja tablicy segmentów.

Jest podobna do implementacji tablicy stron z małymi wyjątkami :

Przy stosowaniu rejestru długości tablicy segmentów mając adres logiczny (s,d) sprawdza się najpierw poprawność numeru s
segmentu ( tzn. czy s jest mniejszy od zawartości rejestru długości tablicy segmentów?). Następnie dodaje się numer segmentu
do rejestru bazowego tablicy segmentów i otrzymuje adres przechowywania w pamięci odpowiedniej pozycji w tablicy
segmentów. Następnie czyta się z pamięci zawartość tej pozycji i postępuje, jak uprzednio: sprawdza, czy odległość nie
przekracza długości segmentu, po czym oblicza adres fizyczny danego słowa jako sumę bazy segmentu i odległości.

7.7.4. Ochrona i dzielenie kodu i danych.

Szczególną zaletą segmentacji jest powiązanie ochrony pamięci z jej segmentami. Ponieważ segmenty są określonymi
semantycznie porcjami programu, można więc oczekiwać, że wszystkie elementy segmentu będą używane w ten sam sposób.
Mamy segmenty , które składają się z rozkazów oraz takie , które zawierają. W nowoczesnych architekturach komputerowych
nie ma samo-modyfikujących się rozkazów, toteż segmenty rozkazów mogą być zdefiniowane jako przeznaczone tylko do
czytania lub do wykonywania.

Stosuje się bity ochrony , sprawdzenie poprawności indeksowania tablic.

Zaletą segmentacji jest dzielenie kodu lub danych. Dzielenie segmentów występuje wtedy, gdy pozycje w tablicach dwu
różnych procesów wskazują na to samo miejsce w pamięci.

7.7.5. Fragmentacja pamięci.

Planista długoterminowy musi znaleźć i przydzielić pamięć wszystkim segmentom programu użytkownika. Sytuacja ta
przypomina stronicowanie , oprócz tego , że segmenty mają zmienne długości., podczas gdy wszystkie strony mają ten sam
rozmiar. Segmentacja może powodować zewnętrzną fragmentację wtedy, gdy każdy z bloków wolnej pamięci jest za mały, by
pomieścić cały segment. W tym przypadku proces może po prostu czekać, aż pojawi się większy obszar pamięci (lub
przynajmniej większa dziura) lub też można zastosować upakowanie w celu utworzenia większej dziury.

Jeżeli zdefiniujemy proces jako jeden segment to podejście sprowadza się do schematu obszarów o zmiennej długości. W
przypadku drugiej skrajności, każde słowo może zostać umieszczone w osobnym segmencie i ulegać oddzielnemu
przemieszczaniu. Takie podejście usuwa zewnętrzną fragmentację całkowicie; wszelako każde słowo potrzebowałoby rejestru

bazowego do wykonania przemieszczeń co podwoiłoby zużycie pamięci. Następnym logicznym krokiem przy zastosowaniu
ma łych, stałowymiarowych segmentów jest stronicowanie. Uogólniając, jeśli średni rozmiar segmentu jest mały, to
zewnętrzna fragmentacja także będzie mała. Ponieważ poszczególne segmenty są mniejsze niż cały proces, jest większa szansa
na to , że uda się pomieścić je w dostępnych blokach pamięci.

7.8. Segmentacja stronicowania.

Łączenie tych dwóch schematów można wyjaśnić na podstawie systemu Multics. Tam adresy logiczne składają się z 18-
bitowego numeru segmentu i 16-bitowej odległości. Mimo że schemat taki tworzy 34-bitową przestrzeń adresową, można się
pogodzić z wielkością nakładu na tablicę, ponieważ zmienna liczba segmentów w sposób naturalny implikuje konieczność
zastosowania rejestru długości tablicy segmentów; nie występują w niej żadne puste pozycje.

Niemniej jednak, przy segmentach dochodzących do 64K słów, średni rozmiar segmentu może być wielki i fragmentacja
zewnętrzna może stanowić problem. Jeśli nawet fragmentacja zewnętrzna nie stanowi problemu, to czas przeszukiwania
zużyty na przydzielenie dla segmentu, przy użyciu metody pierwszy pasujący lub najlepiej pasujący może być długi.
Możemy zatem marnować pamięć z powodu zewnętrznej fragmentacji lub / również marnować czas z powodu długich
przeszukiwań.

Zastosowane w tej sytuacji rozwiązanie polega na stronicowaniu segmentów. Stronicowanie usuwa zewnętrzna fragmentację i
upraszcza problem przydziału: każda pusta ramka może być użyta na potrzebną stronę. Zauważmy , że różnica między takim
rozwiązaniem a czystą segmentacją polega na tym, że pozycja w tablicy segmentów zawiera nie adres segmentów, lecz adres
bazowy tablicy stron tego segmentu. Odległość w segmencie jest podzielona na 6-bitowy numer strony i 10-bitową odległość
na stronie. Numer strony jest indeksem w tablicy stron, z której uzyskuje się numer ramki. Wreszcie numer ramki, w
połączeniu z odległością na stronie, tworzy adres fizyczny.

Każdy segment musi obecnie mieć oddzielną tablicę stron. Jednak, ponieważ długość każdego segmentu, określona za pomocą
odpowiedniej pozycji w tablicy segmentów, jest ograniczona, tablica stron nie musi mieć pełnego rozmiaru. Powinno w niej
być tylko tyle pozycji, ile ich naprawdę potrzeba. Ponadto, ostatnia strona każdego segmentu na ogół nie jest całkiem
zapełniona. W efekcie otrzymujemy, średnio pół strony fragmentacji wewnętrznej na segment. W konsekwencji , choć
wyeliminowaliśmy fragmentację zewnętrzną, wprowadziliśmy fragmentację wewnętrzną i zwiększyliśmy nakład pamięci na
przechowywanie tablic.

Prawdę powiedziawszy, nawet zaprezentowany przed chwilą obraz stronicowanej segmentacji w systemie Multics jest
uproszczeniem. Skoro numer segmentu jest liczbą 18-bitową, należy więc brać pod uwagę możliwość wystąpienia 262 144
segmentów , co wymaga olbrzymiej tablicy segmentów. Aby pokonać ten problem Multics stronicuje tablicę segmentów!!!
Zatem ujmując rzecz ogólnie, aby określić adres w systemie Multics, trzeba się posłużyć numerem segmentu do zdefiniowania
indeksu strony w tablicy stron tablicy segmentów. Na podstawie tej pozycji tablicy lokalizuje się tę część tablicy segmentów,
która zawiera pozycję określającą dany segment. Ta pozycja w tablicy segmentów wskazuje na tablicę stron danego segmentu,
która określa ramkę zawierającą wymagane słowo. I już ;-)

8.Pamięć wirtualna.

Pamięć wirtualna

jest techniką , która umożliwia wykonywanie procesów, pomimo że nie są one w całości

przechowywane w pamięci operacyjnej. Dzięki temu programy mogą być większe niż dostępna pamięć
fizyczna. Za pomocą pamięci wirtualnej tworzy się abstrakcyjną , jednorodną wielką tablicę do
magazynowania informacji reprezentującą pamięć główną. W ten sposób oddziela się pamięć logiczną (
taką jaką widzi ją użytkownik ) od pamięci fizycznej , co uwalnia od ograniczenia ilościowego pamięc

8.1. Motywacje.

Wydaje się , że przed wykonaniem programu potrzeba załadować go całego do pamięci fizycznej , jednak w rzeczywistych
przypadkach cały program nie jest potrzebny , bo na przykład :



Programy zawierają często fragmenty przeznaczone do obsługi wyjątkowych sytuacji występowania błędów.
Ponieważ jednak błędy takie w praktyce występują rzadko , kod ich obsługi jest bardzo rzadko wykonywany.



Tablice, listy i wykazy mają przydzielone więcej miejsca niż potrzebują.



Pewne możliwości do wyboru i właściwości programu mogą być rzadko używane.

Korzyści z wykonywania programu , który tylko w części znajduje się w pamięci :



Program przestaje być ograniczany wielkością dostępnej pamięci fizycznej.



Każdy program zajmuje mniejszy obszar pamięci fizycznej co daje możliwość wykonywania większej ilości
programów w tym samym czasie , a stąd lepsze wykorzystanie czasu procesora i przepustowość bez zwiększania
czasu odpowiedzi lub czasu cyklu przetwarzania.



Maleje liczba operacji we/wy koniecznych do załadowania lub wymiany programów użytkowych w pamięci, zatem
każdy program użytkowy powinien wykonywać się szybciej.

Pamięć wirtualna jest najczęściej implementowana w postaci stronicowania na żądanie.

Lub w systemie segmentacji. Używa się również stronicowanego segmentowania. A także segmentacja na żądanie.

8.2. Stronicowanie na żądanie.

Procesy rezydują w pamięci pomocniczej ( na ogół dyskowej ) i nie są traktowane jako całości lecz podzielone na strony.
Poszczególnymi stronami procesu zajmuje się program zmieniania stron.

Gdy proces ma zostać wprowadzony do pamięci , wtedy program zmieniania stron zgaduje, które strony będą w użyciu ( przed
ponownym wysłaniem procesu na dysk ). I ładuje tylko te które będą niezbędne.

Postępowanie takie wymaga korzystania z odpowiednich środków sprzętowych.

Każda pozycja w tablicy stron jest uzupełniona o dodatkowy bit poprawności odniesienia. Gdy bit ten ma wartość
poprawny , wówczas dana strona znajduje się w pamięci operacyjnej , gdy ma wartość niepoprawny tzn. że dana strona
znajduje się na dysku.

Oznaczenie strony jako niepoprawnej nie wywołuje żadnych skutków, jeśli proces nigdy się do niej nie odwoła. Jeśli proces
spróbuje użyć strony nieobecnej w pamięci powstanie pułapka zwana błędem strony. Sprzęt stronicujący, tłumacząc adres na
podstawie tablicy stron, wykryje, że wartością bitu poprawności jest niepoprawny i spowoduje awaryjne przerwanie w
systemie operacyjnym (błąd adresu). Po takim błędzie proces powinien ulec zakończeniu, ponieważ jednak taka pułapka jest
wynikiem zawinionego przez system operacyjny nie przygotowania w pamięci właściwego zestawu stron procesu, koryguje się
to w następujący sposób :

Sprawdza się wewnętrzną tablicę ( na ogół przechowywaną w bloku kontrolnym procesu ), aby określić czy
odwołanie do pamięci było dozwolone czy nie.

Jeżeli odwołanie było niedozwolone , kończy się proces. Jeśli było dozwolone, lecz zabrakło właściwej strony w
pamięci, to sprowadza się tę stronę.

Znajduje się wolną ramkę (np. biorąc jakąś ramkę z listy wolnych ramek).

Wystosowuje się zamówienie na przeczytanie z dysku potrzebnej strony do nowo przydzielonej ramki.

Po zakończeniu czytania z dysku, modyfikuje się przyporządkowaną procesowi tablicę wewnętrzną oraz tablicę stron,
odnotowując w nich, że strona jest już w pamięci.

Wznawia się wykonanie instrukcji, które zostało przerwane wskutek odwołania się do niedozwolonego adresu. Proces
może teraz sięgać do strony tak, jakby była ona zawsze w pamięci.

W skrajnym przypadku można rozpocząć wykonywanie procesu bez żadnej strony w pamięci. Proces natychmiast zostanie
przerwany z powodu braku strony zawierającej pierwszą instrukcję. Po sprowadzeniu tej strony do pamięci proces będzie
wykonywany z ewentualnymi przerwami dopóty, dopóki wszystkie brakujące strony nie znajdą się w pamięci. Odtąd dalsze
działanie procesu może przebiegać bez zakłóceń. Tak przedstawia się czyste stronicowanie na żądanie nigdy nie sprowadza
się strony do pamięci, zanim nie zostanie ona zapotrzebowana.

Tablica stron.

Tablica ta jest wyposażona w wektor bitów poprawności odniesień lub też informacja o poprawności odniesień jest
reprezentowana za pomocą specjalnych wartości układu bitów ochrony.

Pamięć pomocnicza.

Pamięć ta przechowuje strony nie będące w pamięci głównej. Zazwyczaj służy do tego celu szybki dysk. Pamięć pomocnicza
bywa nazywana urządzeniem do dokonywania wymiany, a część dysku przeznaczona do tego celu zwie się przestrzenią
wymiany lub pamięcią uzupełniającą.

Nakłada się pewne dodatkowe ograniczenia na sprzęt. Podstawowym zagadnieniem jest możliwość wznawiania wykonania
rozkazu po błędzie strony. W większości przypadków wymóg ten jest łatwy do spełnienia. Błąd strony może wystąpić w
dowolnym odniesieniu do pamięci. Jeśli błąd strony wystąpi przy pobieraniu rozkazu do wykonania, to wznowienie polega na
ponownym pobraniu tego rozkazu. Jeśli błąd strony wystąpi przy pobieraniu argumentu rozkazu, to należy pobrać ten rozkaz
ponownie go zdekodować i znowu pobrać argument.

Zasadnicza trudność powstaje wtedy, gdy jakiś rozkaz zmienia kilka różnych komórek. Jeżeli którykolwiek blok bajtów
(źródłowy lub docelowy) przekracza granicę strony, błąd strony może powstać po częściowym wykonaniu przesyłania. Na
dodatek jeżeli blok źródłowy zachodzi na blok docelowy, dane w bloku źródłowym mogą ulec zniekształceniu, wykluczając
proste wznowienie tego rozkazu.

Problem ten rozwiązuje się na dwa różne sposoby, zależnie od modelu komputera. W jednym rozwiązaniu korzysta się z
mikroprogramu, który oblicza i usiłuje dotrzeć do obu końców obu bloków. Jeśli mógłby wystąpić błąd strony, to pojawia się
on już w tym kroku, zanim jeszcze cokolwiek zostanie zmienione. Przesyłanie można wykonać wtedy, gdy już wiadomo, że
błąd strony nie wystąpi, bo wszystkie niezbędne strony znajdują się w pamięci.

W drugim rozwiązaniu używa się rejestrów pomocniczych do przetrzymywania wartości przesyłanych pól. Jeśli zdarzy się
błąd strony, to wszystkie poprzednie wartości będą z powrotem przepisane do pamięci, zanim wystąpi pułapka. Działanie
odtwarza stan pamięci sprzed wykonania rozkazu wobec czego może on być powtórzony.

8.3. Sprawność stronicowania na żądanie.

Obliczmy efektywny czas dostępu do pamięci stronicowanej na żądanie.

Czas dostępu do pamięci oznaczmy przez ma (ang. memory access time), dopóki nie występują błędy odniesień do stron
dopóty efektywny czas dostępu = ma.

Jeśli jednak wystąpi błąd strony, to trzeba będzie najpierw przeczytać potrzebną stronę z dysku, a potem sięgnąć po wymagane
słowo.

Niech p oznacza prawdopodobieństwo błędu strony.

Efektywny czas dostępu = (1-p) * ma + p * czas_błędu_strony.

Trzeba znać więc czas obsługi błędu strony . Błąd strony spowoduje, że powstanie następujący ciąg zadań :



obsługa przerwania wywołanego błędem strony



czytanie strony



wznowienie procesu

Pierwsze i trzecie zadanie może być zredukowane przy starannym kodowaniu do kilku setek rozkazów. Każde z tych zadań
może zająć od 1 d 100 ms . Natomiast czas przełączania strony będzie prawdopodobnie trwał około 24 ms. Typowy dysk z
ruchomą głowicą ma czas oczekiwania równy 8 ms, szukania rzędu 15ms i czas przesyłania rzędu 1 ms. Zatem łączny czas
pobrania strony (czas działania sprzętu i oprogramowania) może wynosić około 25 ms. Pamiętajmy także, że zwracamy uwagę
tylko na czas obsługi urządzenia. Jeśli na urządzenie oczekuje kolejka procesów (inne procesy, którym przytrafiły się błędy
strony), to trzeba będzie do naszego obliczenia dodać czas oczekiwania w kolejce na zwolnienie urządzenia stronicującego i
przekazanie go do naszej dyspozycji, co dodatkowo powiększy czas wymiany.

Jeśli przyjmiemy średni czas obsługi błędu strony jako 25 ms , a czas dostępu do pamięci 100 ns, to efektywny czas dostępu
wyniesie w nanosekundach:

Ecd = (1-p) * 100 + p * 25 000 000 = 100 + 24 999 900 * p

Efektywny czas dostępu jest więc wprost proporcjonalny do częstości błędów strony. Jeśli jeden dostęp na 1000 będzie
powodować błąd strony, to efektywny czas dostępu wyniesie 25 ms. Wskutek stronicowania na żądanie komputer zostanie
spowolniony 250-krotnie. Jeśli chcielibyśmy, aby pogorszenie było mniejsze niż 10%, to musiałoby być:

110 > 100 + 25 000 000 * p

10 > 25 000 000 * p

p < 0,0000004

Oznacza to , że do utrzymania spowolnienia wynikającego ze stronicowania na możliwym do przyjęcia poziomie, należałoby
dopuścić błąd strony na każde 2 500 000 odniesień do pamięci.

Utrzymywanie częstości występowania błędów strony na niskim poziomie jest bardzo ważne w systemie stronicowania na
żądanie. W przeciwnym razie rośnie czas dostępu, drastycznie spowalniając wykonanie procesu.

8.4. Zastępowanie stron.

Zastępowanie stron występuje w przypadku tak zwanego nadprzydziału pamięci , tzn. wtedy gdy proces odwoła się do strony
nie będącej w pamięci , a równocześnie przy próbie załadowania jej z dysku okaże się, że nie ma dla niej wolnej ramki cała
pamięć jest w użyciu.

Procedura obsługi błędów strony z uwzględnieniem zastępowania stron wygląda teraz tak :

Odnalezienie lokalizacji potrzebnej strony na dysku.

Odnalezienie wolnej ramki :

jeśli istnieje wolna ramka to zostanie użyta;

w przeciwnym razie trzeba wykonać algorytm zastępowania stron w celu wytypowania ramki-ofiary;

stronę-ofiarę zapisuje się na dysku; towarzyszy temu stosowna zmiana tablic stron i ramek.

Do (świeżo) zwolnionej ramki wczytuje się potrzebną stronę i zmienia tablice stron i ramek.

Wznawia się działanie procesu.

Zauważmy , że gdy nie ma wolnych ramek, wówczas jest potrzebne dwukrotne przesyłanie stron ( jedno na dysk i jedno z
dysku). Powoduje to dwukrotne wydłużenie czasu obsługi błędu strony i w konsekwencji wydłuża efektywny czas
dostępu.

Nakład ten można zmniejszyć przez zastosowanie bitu modyfikacji. Każda strona lub ramka może być wyposażona w
sprzętowy bit modyfikacji. Bit ten jest ustawiany sprzętowo jako równy 1 przy zapisie dowolnego bajtu lub słowa na stronie,
aby wskazywał, że dana strona uległa zmianie. Przy wyborze strony do zastąpienia sprawdza się jej bit modyfikacji ( każda
strona ma własny). Jeśli bit jest ustawiony, wiadomo, że stan danej strony zmienił się od czasu jej przeczytania z dysku. W tym
wypadku stronę należy zapisać na dysku. Natomiast nie ustawiony bit modyfikacji zaświadcza, że zawartość strony nie była
zmieniana od czasu jej przeczytania do pamięci. Toteż, jeśli kopia strony na dysku nie została zniszczona, można uniknąć
przesyłania takiej strony na dysk ponieważ ona już się tam znajduje.

Aby zrealizować stronicowanie na żądanie, należy rozwiązać dwa główne problemy: opracować algorytm przydziału ramek
oraz algorytm zastępowania stron. Jeśli w pamięci znajduje się wiele procesów, to trzeba zdecydować , ile ramek zostanie
przydzielonych do każdego procesu. Następnie, gdy powstanie konieczność zastąpienia strony, wówczas trzeba umieć wskazać
ramkę do wymiany.

8.5. Algorytmy zastępowania stron.

Najważniejsze aby algorytm zastępowania strony zapewniał jak najmniejszą częstość błędów strony.

Algorytm ocenia się na podstawie wykonania go na pewnym ciągu odniesień do pamięci i zsumowania liczby błędów strony.
Ów ciąg odniesień można wytworzyć sztucznie lub na podstawie śledzenia danego systemu i zapisywania adresu każdego
odniesienia do pamięci. Ta druga metoda powoduje powstanie wielkiej liczby danych. Dla zmniejszenia tej liczby wystarczy
zauważyć , że dla danego rozmiaru strony musimy brać pod uwagę tylko numer strony, a nie cały adres. Po drugie, odniesienie
do strony s, następujące bezpośrednio po odniesieniu do strony s, nigdy nie spowoduje błędu strony. Strona s będzie w pamięci
po pierwszym odniesieniu; następujące po nim odniesienie nie spowoduje błędu.

Aby określić liczbę błędów strony dla konkretnego ciągu odniesień i algorytmu zastępowania stron, należy także znać liczbę
dostępnych ramek. Przy wzroście liczby wolnych ramek liczba błędów strony będzie maleć. Wraz ze wzrostem liczby ramek
spada liczba błędów strony do pewnego minimalnego poziomu.

8.5.1. Algorytm FIFO.

Najprostszym z algorytmów zastępowania stron jest algorytm o nazwie pierwszy przyszedł pierwszy odszedł (ang. first-in,
first-out , czyli FIFO).

Gdy trzeba zastąpić stronę wybiera się tę najstarszą. Robi się to za pomocą kolejki FIFO przechowującą wszystkie strony
przebywające w pamięci zdejmuje się stronę z czoła kolejki , a dołącza do pamięci stronę na koniec kolejki.

Algorytm FIFO jest łatwy do zrozumienia i zaprogramowania. Jednak jego zachowanie nie zawsze jest zadowalające. Strona
zastępowana może zawierać wstępny moduł procesu , dawno używany i już niepotrzebny.

Może jednak zawierać też zmienną, która została wcześnie zainicjowana lecz jest ciągle używana.

Zważmy także, iż nawet po wybraniu do zastąpienia strony, która jest bieżąco używana, wszystko działa poprawnie. Po
usunięciu z pamięci tej aktywnej strony w celu wprowadzeniu nowej, prawie natychmiast nastąpi błąd z powodu braku
usuniętej strony . Trzeba będzie usunąć jakąś inną stronę, ponieważ okaże się konieczne ponowne sprowadzenie aktywnej
strony do pamięci. Tym samym zły wybór przy zastępowaniu zwiększa liczbę błędów strony i spowalnia wykonanie procesu,
choć nie powoduje nie właściwego działania.

Jeżeli weźmiemy ciąg odniesień :

1 , 2 , 3 , 4 , 1 , 2 , 5 , 1 , 2 , 3 , 4 , 5

to łatwo zauważyć , że dla ilości ramek ilość błędów wynosi odpowiednio :

1 ? 12

2 ? 12

3 ? 9

4 ? 10

5 ? 6

6 ? 6

Fakt , że dla większej ilości ramek 4 błędów stron jest więcej (10) niż dla mniejszej ilości ( 3 i 9 ) nosi nazwę anomalii
Beladyego i pokazuje , że w niektórych algorytmach zastępowania stron współczynnik błędów strony może wzrastać ze
wzrostem wolnych ramek. Oczekiwalibyśmy raczej , że zwiększenie pamięci procesu powinno polepszyć jego zachowanie ?
jak się okazuje nie zawsze to jest prawdą.

8.5.2. Algorytm optymalny.

Algorytm optymalny zastępowania stron ma najniższy współczynnik błędów strony ze wszystkich algorytmów. Nigdy nie
powoduje anomalii Beladyego. ( nazywany jest OPT i MIN ) . Brzmi po prostu :

Zastąp tę stronę, która najdłużej nie będzie używana.

Niestety , optymalny algorytm zastępowania jest trudny do realizacji, ponieważ wymaga wiedzy o przyszłej postaci ciągu
odniesień. W rezultacie algorytm optymalny jest używany głównie w studiach porównawczych. Znajomość tego, że jakiś nie
jest wprawdzie optymalny, lecz w najgorszym razie odbiega od niego o 12,3% , średnio jest od niego gorszy o 4,7%, może być
bardzo cenna.

8.5.3. Algorytm LRU.

Do oszacowania najbliższej przyszłości używamy niedawnej przeszłości i zastępujemy stronę, która nie była używana od
najdłuższego czasu. Algorytm taki zwie się zastępowaniem najdawniej używanych stron (ang. least recently used) LRU.

Zastępowanie metodą LRU kojarzy z każdą stroną czas jej ostatniego użycia. Gdy strona musi być zastąpioną inną, wówczas
algorytm LRU wybiera tę, która nie była używana od najdłuższego czasu. Metodę LRU uważa się za dość dobrą . Główną
trudność stanowi sposób implementacji algorytmu LRU. Może on wymagać zastosowania specjalnego wyposażenia
sprzętowego. Dodatkowe kłopoty sprawia określenie porządku ramek wyznaczonego przez czas ich ostatniego użycia. W
praktyce stosuje się dwie implementacje :

Liczniki:

W najprostszym przypadku do każdej pozycji w tablicy stron dołączamy rejestr czasu użycia, do procesora zaś dodajemy zegar
logiczny lub licznik. Wskazania zegara są zwiększane za każdym odniesieniem do pamięci. Ilekroć występuje odniesienie do
pamięci, tylekroć zawartość rejestru zegara jest kopiowana do rejestru czasu użycia należącego do danej strony w tablicy stron.
W ten sposób dla każdej strony dysponujemy zawsze czasem ostatniego do niej odniesienia. Zastępujemy stronę z
najmniejszą wartością czasu. Schemat ten wymaga przeglądania tablicy stron w celu znalezienia strony zasługującej na miano
najdawniej używanej ( czyli LRU). Rejestry czasu użycia wymagają uaktualnienia również przy wymianach tablic stron (
powodowanych planowaniem przydziału procesora ). Należy się także liczyć z możliwością powstania nadmiaru w rejestrze
zegara.

Stos:

Wprowadza się stos numerów stron. Przy każdym odniesieniu do strony jej numer wyjmuje się ze stosu i umieszcza na jego
szczycie. W ten sposób na szczycie stosu przebywa zawsze strona użyta ostatnio, na spodzie zaś są strony najdawniej
używane. Najlepsza implementacja polega na zastosowaniu listy dwukierunkowej ze wskaźnikami do czoła i do końca listy.
Wyjęcie strony i ulokowanie jej na szczycie stosu wymaga w najgorszym razie zmiany sześciu wskaźników. Każde
uaktualnienie listy jest zatem nieco bardziej czasochłonne, ale do zastąpienia strony nie jest potrzebne przeszukiwanie listy,
ponieważ wskaźnik do końca listy, wskazujący na dno stosu, identyfikuje najdawniej używaną stronę. Opisana metoda jest
szczególnie przydatna do implementacji zastępowania metodą LRU za pomocą oprogramowania systemowego lub
mikroprogramowania.

Klasa algorytmów stosowych, która nigdy nie wykazuje anomalii Beladyego charakteryzuje się tym , że dla każdego
algorytmu z tej klasy można wykazać, że zbiór stron w pamięci w przypadku istnienia n ramek jest zawsze podzbiorem zbioru
stron znajdującego się w pamięci przy n + 1 ramkach. Przy zastępowaniu metodą LRU zbiór stron w pamięci będzie się składał
z n ostatnio używanych stron. Jeśli liczba ramek ulegnie zwiększeniu , to te strony będą nadal ostatnio używane, więc
pozostaną one w pamięci.

Żadnej implementacji metody LRU nie można wykonać bez odpowiedniego wyposażenia sprzętowego. Uaktualnienie rejestru
zegara lub stosu musi być wykonane przy każdym odniesieniu do pamięci.

Stosowanie przerwania dla każdego odniesienia do pamięci, aby za pomocą oprogramowania uaktualniać te struktury danych,
spowodowałoby co najmniej dziesięciokrotne spowolnienie wykonania odniesień do pamięci, a zatem dziesięciokrotne
spowolnienie każdego procesu użytkownika.

8.5.4. Algorytmy przybliżające metodę LRU.

Przy braku pewnych sprzętowych środków do realizacji metody LRU stosuje się metody przybliżające ją.

Stosuje się ograniczone środki sprzętowe na przykład bity odniesienia, które są przyporządkowane danej pozycji w tablicy
stron i są ustawiane gdy do danej strony było jakieś odniesienie , w ten sposób nie wiadomo, która strona była ostatnio
używana , więc nie wiadomo nic o porządku odniesień, ale wiadomo , do której strony w ogóle nie było odniesień.

Algorytm dodatkowych bitów odniesienia.

Dla każdej strony można przeznaczyć 8-bitowy bajt w tablicy w pamięci operacyjnej. W regularnych okresach przerwanie
zegarowe powoduje przekazanie sterowania do systemu operacyjnego. Dla każdej strony system operacyjny wprowadza bit
odniesienia na najbardziej znaczącą pozycję 8-bitowego bajtu, przesuwając pozostałe bity o jedną pozycję w prawo, z utratą
bitu na pozycji najmniej znaczącej. Takie 8-bitowe rejestry przesuwne zawierają historię użycia strony podczas ostatnich
ośmiu okresów czasu. Interpretując te 8-bitowe bajty jako liczby bez znaku, za stronę najdawniej używaną i kandydującą do
zastąpienia przyjmuje tę stronę, której odpowiada najmniejsza liczba. Nie ma jednak gwarancji, że takie liczby będą parami
różne.

Można zatem zastąpić (wymienić) albo wszystkie strony, którym odpowiadają najmniejsze liczby, albo do wyboru spośród
nich zastosować kryterium FIFO.

Algorytm drugiej szansy.

Podstawą algorytmu na zasadzie drugiej szansy jest algorytm FIFO. Po wybraniu strony sprawdza się dodatkowo jej bit
odniesienia. Jeśli wartość tego bitu wynosi 0, to strona zostaje zastąpiona. Natomiast gdy bit odniesienia jest równy 1,
wówczas dana strona dostaje drugą szansę (na pobyt w pamięci) , a pod uwagę bierze się następną stronę wynikającą z
porządku FIFO. Bit odniesienia strony, której daje się drugą szansę, jest zerowany, a czas jej pobrania ustawia się na czas
bieżący. W ten sposób strona, której dano drugą szansę, dopóty nie będzie uwzględniona przy zastępowaniu, dopóki nie
zostaną zastąpione inne strony ( lub otrzymają drugą szansę). Co więcej, jeśli strona jest eksploatowana wystarczająco często,
by utrzymać swój bit odniesienia ustawiony na 1, to nigdy nie zostanie zastąpiona.

Jednym ze sposobów na zaimplementowanie algorytmu drugiej szansy (nazywanego też zegarowym) jest kolejka cykliczna.
Stronę typowaną do zastąpienia w następnej kolejności pokazuje wskaźnik. Przy zapotrzebowaniu na ramkę wskaźnik
przemieszcza się naprzód, aż znajdzie stronę z wyzerowanym bitem odniesienia. Podczas przemieszczania bity odniesienia są
zerowane ( zob. rys. 8. 13.). W najgorszym przypadku, jeśli wszystkie bity odniesienia były ustawione, to wskaźnik obiegnie
całą kolejkę, dając każdej stronie drugą szansę. Przed wybraniem następnej strony do zastąpienia zostaną wyzerowane
wszystkie bity odniesienia. Gdy wszystkie bity odniesienia są ustawione, wówczas zastępowanie metodą drugiej szansy
sprowadza się do zastępowania zgodnie z algorytmem FIFO.

Algorytm LFU

Algorytm zastępowania strony najmniej używanej ( ang. least frequently used ) LFU prowadzi licznik odniesień do każdej
strony. Zastąpieniu ulega strona z najmniejszą liczbą odniesień. Powodem takiego wyboru jest spostrzeżenie, że strony
aktywnie użytkowane powinny mieć duży licznik odniesień. Algorytm ten może być obarczony błędami wynikającymi z
sytuacji, w której strona jest intensywnie użytkowana w początkowej fazie procesu, a potem przestaje być używana w ogóle. Z
czasów intensywnego użytkowania ma ona wysoką wartość licznika i pozostaje w pamięci, mimo że nie jest dłużej potrzebna.

Jednym z rozwiązań może być tu przesuwanie liczników w prawo o 1 bit w regularnych odstępach czasu, powodujące
wykładnicze zmniejszenie wartości licznika średniego użycia.

Algorytm MFU

Innym algorytmem zastępowania stron jest zastępowanie strony najczęściej używanej (ang. most frequently used MFU ),
uzasadnianie tym , że strona z najmniejszą wartością licznika została prawdopodobnie dopiero co sprowadzona i jest bieżąco
używana. Jak można oczekiwać, oba algorytmy zastępowania, MFU oraz LFU, nie są popularne. Implementacja tych
algorytmów jest dość kosztowna, a nie przybliżają one dość dobrze algorytmu OPT.

Dodatkowe algorytmy.

Istnieje wiele innych algorytmów, które można użyć przy zastępowaniu stron. Na przykład, jeśli będziemy traktować bit
odniesienia i bit modyfikacji jako parę uporządkowaną, to otrzymamy podział stron na następujące cztery klasy :

(0,0) nie używana i nie zmieniona

(0,1) nie używana (ostatnio) ale zmieniona

(1,0) używana ale nie zmieniona

(1,1) używana i zmieniona

Każda ze stron należy do jednej z tych czterech klas. Gdy zastąpienie strony staje się konieczne, wówczas zastępuje się
dowolną stronę z najniższej, niepustej klasy. Jeśli najniższa klasa zawiera wiele stron, stosuje się algorytm FIFO lub wybór
losowy.

8.5.5. Algorytmy ad hoc.

Jako uzupełnienie konkretnych algorytmów zastępowania stron stosuje się często różne procedury. Na przykład często systemy
przechowują pulę wolnych ramek. Po wystąpieniu błędu strony ramkę-ofiarę wybiera się jak uprzednio. Niemniej jednak,
zanim do tej ramki przeczyta się potrzebną stronę, czyta się ją do którejś z wolnych ramek puli. Postępowanie takie pozwala na
maksymalnie szybkie wznowienie procesu, bez oczekiwania na przepisanie strony-ofiary z pamięci operacyjnej. Gdy w
późniejszym czasie strona-ofiara zostanie przepisana do pamięci zewnętrznej, wtedy zajmowaną przez nią ramkę dołączy się
do puli wolnych ramek.

Rozwinięciem tego pomysłu jest utrzymywanie listy zmienionych stron. Kiedy urządzenie stronicujące jest bezczynne, wtedy
wybiera się zmienioną stronę i zapisuje ją na dysku. Jej bit modyfikacji powraca wówczas do stanu początkowego. Taki
schemat zwiększa prawdopodobieństwo, że strona wybrana do zastąpienia będzie czysta i jej zawartości nie trzeba będzie
zapisywać na dysku.

Inna odmiana tej metody polega na utrzymywaniu puli wolnych ramek i pamiętaniu, które strony rezydowały w każdej ramce.
Ponieważ zawartość ramki nie ulega zmianie przy zapisywaniu jej zawartości na dysku, więc dopóki dana ramka nie zostanie

użyta na nowo, dopóty pozostająca w niej strona może być powtórnie wprost z puli wolnych ramek. W tym przypadku nie jest
potrzeba żadna operacja we/wy. Po wystąpieniu błędu strony sprawdza się najpierw, czy potrzebna strona jest w puli wolnych
ramek. Jeśli jej tam nie ma, to należy wybrać wolną ramkę i przeczytać w niej brakującą stronę.

8.6. Przydział ramek.

Połączenie stronicowania na żądanie z wieloprogramowaniem jest przyczyną powstawania dodatkowych problemów.
Wieloprogramowanie umieszcza kilka procesów w pamięci w tym samym czasie. Jak rozdzielić ramki między nie.

8.6.1. Minimalna liczba ramek.

Niezależnie od niekorzystnych objawów działania systemu, w którym przydziela się za mało ramek, istnieje minimalna liczba
ramek, które muszą być przydzielone. Ta minimalna liczba jest określona przez zbiór rozkazów w architekturze komputera.
Zważmy, że jeśli błąd strony wystąpi przed dokończeniem wykonania rozkazu, to rozkaz trzeba powtórzyć. Wynika z tego, że
należy mieć wystarczającą liczbę ramek do przechowywania wszystkich stron, do których może się odnosić pojedynczy
rozkaz.

Minimalna liczba ramek przypadających na proces jest zdefiniowana przez architekturę logiczną komputera, natomiast
maksymalna ich liczba wynika z ilości dostępnej pamięci fizycznej. W tych granicach pozostaje nam ciągle jeszcze wiele
możliwości wyboru.

8.6.2. Algorytmy przydziału.

Przydział równy, dla m ramek i n procesów , każdy dostaje m/n ramek resztę można potraktować jako bufor wolnych ramek.

Przydział proporcjonalny. Każdemu procesowi przydziela się dostępną pamięć odpowiednio do jego rozmiaru.

Niech si oznacza wielkość pamięci wirtualnej procesu pi. Określamy sumę pamięci wirtualnej przydzielonej

wszystkim procesom jako:

Wówczas, gdy ogólna liczba ramek wynosi m, procesowi pi przydzielamy ai ramek, przy czym ai wynosi w przybliżeniu :

ai = si/S * m

i ai > minimalnej liczby ramek.

Przy obu powyższych podziałach nie uwzględnia się priorytetu procesów. A na mocy definicji mamy prawo wymagać , aby
proces o wyższym priorytecie otrzymał więcej pamięci w celu przyśpieszenia swojego działania, nawet za cenę pogorszenia
działania procesów nisko-priorytetowych.

Jedną z metod jest zastosowanie przydziału proporcjonalnego, w którym liczba ramek zależy od priorytetów procesów lub od
kombinacji rozmiaru i priorytetu.

Inne podejście polega na pozwalaniu procesowi wysoko-priorytetowemu , aby ramki potrzebne do zastępowania wybierały z
obszaru procesów nisko-priorytetowych. Proces może wyselekcjonować ramkę do zastąpienia spośród własnych ramek lub
ramek dowolnego procesu o niższym priorytecie. Takie podejście pozwala procesowi o wyższym priorytecie zwiększać liczbę
swoich ramek kosztem procesu o niższym priorytecie.

8.7. Szamotanie.

Jeśli proces niema dość ramek. Chociaż technicznie jest możliwe zmniejszenie liczby przydzielonych ramek do minimum,
zawsze będzie istniała pewna (większa ) liczba stron aktywnie używanych. Jeśli proces nie będzie miał takiej liczby ramek, to
szybko wystąpi brak strony. Wtedy któraś ze stron będzie musiała być zastąpiona. Ponieważ jednak wszystkie strony są
aktywnie używane, więc trzeba będzie zastąpić jakąś stronę, która za chwilę okaże się potrzebna. W konsekwencji, w procesie
bardzo szybko będą następować po sobie kolejne błędy braku strony. Proces będzie ciągle wykazywał brak strony,
wymieniając jakąś stronę, po czym z powodu jej braku sprowadzając ją z powrotem.

Taką bardzo dużą aktywność stronicowania określa się terminem szamotania. Proces szamoce się, jeśli spędza więcej czasu na
stronicowaniu niż na wykonaniu.

8.7.1. Przyczyna szamotania.

System operacyjny nadzoruje wykorzystanie jednostki centralnej. Jeśli jest ono za małe, to zwiększa się poziom
wieloprogramowości, wprowadzając nowy proces do systemu. Strony są zastępowane według globalnego algorytmu
zastępowania stron , bez brania pod uwagę do jakich procesów należą.

Załóżmy teraz , że proces wchodzi w nową fazę działania i potrzebuje więcej ramek. Zaczyna wykazywać błędy braku strony i
powoduje utratę stron przez inne procesy. Te z kolei procesy potrzebują owych stron, więc wykazują ich braki i znowu
przyczyniają się do odbierania stron innym procesom. Tak zachowujące się procesy muszą używać urządzenia stronicującego
w celu dokonania wymian stron. Ustawiają się w kolejce do urządzenia stronicującego, a jednocześnie opróżnia się kolejka
procesów gotowych do wykonywania. Wskutek oczekiwania procesów na urządzenie stronicujące zmniejsza się
wykorzystanie procesora.

Program planujący przydział procesora dostrzega spadek wykorzystania jednostki centralnej, więc zwiększa stopień
wieloprogramowości. Nowy proces próbuje wystartować, przeto zabiera ramki wykonywanym procesom, powodując jeszcze
więcej błędów strony i jeszcze większą kolejkę do urządzenia stronicującego.

W rezultacie, wykorzystanie procesora spada jeszcze bardziej i planista przydziału procesora próbuje zwiększyć stopień
wieloprogramowości po raz kolejny. Powstaje szamotanina, przepustowość systemu gwałtownie spada i równie gwałtownie
wzrasta częstość występowania błędów strony. Wskutek tego wzrasta czas efektywnego dostępu do pamięci. Nie można
zakończyć żadnej pracy, ponieważ procesy spędzają cały czas na stronicowaniu.

Efekt szamotania można ograniczyć za pomocą lokalnego (lub priorytetowego) algorytmu zastępowania. Przy zastępowaniu
lokalnym gdy jakiś proces zaczyna się szamotać nie pozwala mu się kraść ramek innych procesów i tym samym powodować
szamotania innych procesów. Jednak ten szamocący się proces cały czas przedłuża czas dostępu do urządzenia stronicującego
innych procesów. Trzeba więc dostarczyć procesowi tyle ramek, ile ich potrzebuje. Ale ile ?

Przyjmuje się strategię tworzenia zbioru roboczego i rozpoczyna od sprawdzenia z ilu ramek proces bieżąco korzysta. Przy
takim podejściu stosuje się model strefowy wykonania procesu.

W modelu strefowym zakłada się, że podczas wykonania proces przechodzi z jednej strefy programu do innej. Przez strefę
programu rozumie się zbiór stron pozostających we wspólnym użyciu. Program składa się na ogół z wielu stref , które mogą na
siebie nachodzić.

8.7.2. Model zbioru roboczego.

W modelu zbioru roboczego zakłada się istnienie stref programu. W modelu tym używa się parametru delta do
definiowania okna zbioru roboczego. Pomysł polega na sprawdzaniu ostatnich delta odniesień do stron. Za zbiór roboczy
przyjmuje się zbiór stron, do których nastąpiło ostatnich delta odniesień. Jeśli strona jest aktywnie używana, to będzie
znajdować się w zbiorze roboczym. Gdy strona przestanie być używana, wówczas wypadnie ze zbioru roboczego po delta
jednostkach czasu odliczonych od ostatniego do niej odniesienia. W ten sposób zbiór roboczy przybliża strefę programu.
Dokładność zbioru roboczego zależy od wyboru parametru delta. Jeśli będzie on zbyt mały, to nie obejmie całego zbioru
roboczego; jeśli ten parametr będzie za duży, to może zachodzić na kilka stref programu. W skrajnym przypadku, gdy
parametr delta jest nieskończony, wtedy zbiorem roboczym staje się cały program.

Najważniejszą cechą zbioru roboczego jest jego rozmiar. Jeśli dla każdego procesu w systemie obliczymy rozmiar zbioru
roboczego WSSi, to możemy określić ogólne zapotrzebowanie na ramki jako sumę WSSi.

Gdy D > m (il. ramek) , to powstanie szamotanie. Dlatego jeśli są wolne ramki to można zainicjować nowy proces , gdy jednak
suma rozmiarów roboczych wzrasta i zaczyna przekraczać łączną liczbę dostępnych ramek, wtedy system operacyjny wybiera
proces, którego wykonanie trzeba wstrzymać. Strony procesu są usuwane z pamięci , a jego ramki przydziela się innym
procesom. Wstrzymany proces może być później wznowiony.

8.7.3. Częstość braku strony

Zagadnienie polega na znalezieniu sposobu zapobiegania szamotaniu. Szamotanie odznacza się dużą ilością błędów braku
strony. Dąży się zatem do sterowania częstością tych błędów. Za duża jej wartość świadczy o tym, że proces ma zbyt wiele
ramek. Można ustalić górną i dolną granicę pożądanego poziomu błędów braku strony. Procesowi , którego liczba błędów
braku strony przekracza górną granicę, przydziela się dodatkową ramkę; jeśli zaś liczba błędów spada poniżej dolnej granicy,
to usuwa się ramkę z procesu, którego ten objaw dotyczy. Jeśli wzrasta liczba błędów strony i brakuje wolnych ramek, to
trzeba wybrać pewien proces i wstrzymać jego wykonanie. Wolne ramki rozdziela się wtedy między procesy z najwyższymi
częstościami błędów braku strony.

Zarządzanie pamięcią pomocniczą.

W większości systemów komputerowych istnieje pamięć pomocniczą jako rozszerzenie pamięci podstawowej (operacyjnej,
głównej).

Najlepszym rozwiązaniem byłoby przechowywanie programów i wszystkich potrzebnych im danych w pamięci głównej,
jednak jest to niemożliwe z dwóch powodów:



Pamięć główna jest zazwyczaj zbyt mała



Pamięć główna traci swoją zawartość po wyłączeniu lub zaniku zasilania

Jednym z pierwszych nośników pamięci pomocniczej była taśma magnetyczna. Taki sposób przechowywania danych ma
jednak istotne wady:



Bardzo długi czas dostępu do danych w porównaniu z pamięcią główną



Wyłącznie sekwencyjny dostęp do danych (można czytać dane tylko w kolejności w jakiej zostały zapisane, nie
można skoczyć do wybranego miejsca taśmy i przeczytać potrzebne dane)

We współczesnych systemach komputerowych rolę masowej pamięci pomocniczej spełniają dyski.

Struktura dysku.

Dysk składa się z kilku (w zależności od pojemności) talerzy z których każdy pokryty jest materiałem magnetycznym. Kiedy
dysk pracuje, napędzający go silnik wprowadza go w ruch wirowy o dużej prędkości. Tuż ponad dyskiem znajduje się głowica
czytająco pisząca. Powierzchnia dysku jest podzielona na ścieżki. Zapamiętanie informacji polega na magnetycznym zapisaniu
jej na ścieżce przez głowicę czytająco-piszącą, podobnie jak w przypadku taśmy magnetycznej.

Zazwyczaj aby odczytać z dysku potrzebne dane głowica przesuwa się nad odpowiednią ścieżkę i sczytuje dane. Jest to
najtańsza metoda budowy dysk, ale jednocześnie stosunkowo wolna. Tam gdzie wymagany jest bardzo szybki dostęp do
danych na dysku stosuje się dyski o nieruchomych głowicach z których każda ma przyporządkowaną sobie ścieżkę z której
sczytuje dane. Zatem głowic jest tyle ile ścieżek na dysku. Taka konstrukcja zapewnia bardzo szybką pracę, ale jest znacznie
droższa od systemów z ruchomą głowicą.

Ponieważ głowice znajdują się bardzo blisko wirującego dysku (mikronowe odległości) płaszczyzny płyt musza być bardzo
dokładnie wykonane. Często w skutek mechanicznego uszkodzenia może dojść do zetknięcia się głowicy z powierzchnią
dysku i zarysowania tejże powierzchni. Uszkodzenie tego typu na ogół kwalifikuje cały dysk do wymiany.

W dyskach elastycznych (dyskietkach) głowice czytająco piszące dotykają bezpośrednio powierzchni dysku. Jest to możliwe
ponieważ dyski te są powleczone specjalną, twardą warstwą ochronną. Dyski te jednak po pewnym czasie zużywają się.

Dyski charakteryzują się dwiema ważnymi cechami które czynią z nich wygodny środek przechowywania licznych plików:



Informacje mogą być uaktualniane bez zmiany miejsca; można przeczytać blok z dysku, wprowadzić do niego
zmiany i zapisać ponownie w tym samym miejscu.



Dowolny blok informacji na dysku można zaadresować bezpośrednio.

ZARZĄDZANIE WOLNYMI OBSZARAMI DYSKOWYMI.

Aby mieć bieżącą informacje o wolnych obszarach na dysku, system utrzymuje listę wolnych obszarów, w której odnotowane
są wszystkie wolne w danej chwili bloki.

wektor bitowy

Lista wolnych obszarów często bywa implementowana w postaci mapy bitowej lub wektora bitowego. Każdy blok
jest reprezentowany przez jeden bit, jeśli blok jest pusty, odpowiadający mu bit = 0, jeśli natomiast jest zajęty, bit ten
ma wartość 1.

Przykład:

Rozważmy na przykład dysk, którego bloki: 2,3,4,5,8,9,10,12,13,17,25,26 i 27 są wolne, a pozostałe zajęte. Mapa
wolnych przestrzeni przyjmuje postać: 110000110000001110011111100011111 (mam nadzieję, że się nie
pomyliłem).

Lista powiązana

Jest to inny sposób określenia położenia wolnych bloków na dysku. W tym przypadku system przechowuje wskaźnik
do pierwszego wolnego bloku. W nim zaś zapisany jest w wskaźnik do kolejnego wolnego bloku, w którym zapisany
jest wskaźnik do kolejnego wolnego bloku itd. Metoda ta nie jest wydajna aby przejrzeć listę wolnych bloków,
należy odczytać każdy blok, co wymaga czasu.

Grupowanie

Modyfikacją podejścia omówionego powyżej jest przechowywanie adresów n wolnych bloków w pierwszym wolnym
bloku. Pierwsze n-1 adresów wskazuje na wolne bloki. Ostatni adres jest adresem bloku zawierającego adresy
następnych n wolnych bloków.

Zliczanie

Na ogół kilka przylegających do siebie bloków przydziela się i zwalnia jednocześnie. Tą właśnie właściwość wykorzystuje
metoda zliczania. W tej metodzie zamiast listy n wolnych obszarów w systemie przechowywany jest adres pierwszego
wolnego bloku i liczba k wolnych bloków następujących nieprzerwanie po nim.

METODY PRZYDZIAŁU MIEJSCA NA DYSKU

Powszechnie używa się trzech głównych metod przydziału miejsca na dysku:



Ciągłej



Listowej



Indeksowej

przydział ciągły

W metodzie przydziału ciągłego każdy plik musi zajmować ciąg kolejnych adresów na dysku. Kłopotem w przydziale
ciągłym może być znalezienie wolnego miejsca na nowy plik. Jeżeli trzeba zapisać plik o długości n bloków, to
należy odnaleźć na dysku n wolnych bloków przylegających do siebie.

przydział listowy

W przydziale dyskowym każdy plik stanowi listę powiązanych ze sobą bloków dyskowych; bloki te mogą znajdować się
gdziekolwiek na dysku. Każdy blok zawiera wskaźnik do następnego bloku zawierającego dany plik.

Zalety:



Łatwo znaleźć miejsce dla nowego pliku.

Wady:



Ograniczenie zastosowania jedynie do plików o dostępie sekwencyjnym



Przestrzeń zajmowana przez wskaźniki



Uszkodzenie, zmiana klub zagubienie wskaźnika może doprowadzić do dowiązanie do pliku części innego pliku lub
wolnego miejsca.

Ważna odmiana przydziału listowego polega na użyciu tablicy przydziału plików (file-allocation table). Na dysku wydziela się
sekcję która będzie zawierała tablicę. Tablica ma po jednej pozycji dla każdego bloku dyskowego i jest indeksowana za
pomocą numerów bloków. Tablicy tej używa się podobnie jak listy powiązań. Katalog zawiera numer pierwszego bloku pliku.
Pozycja w tablicy indeksowana przez numer tego bloku zawiera numer następnego bloku w pliku. Łańcuch taki ciągnie się do
ostatniego bloku, który ma no odpowiadającej mu pozycji w tablicy specjalny symbol końca pliku.

Ta prosta J , lecz wydajna metoda stosowana jest w systemach MS-DOS i OS/2.

Przydzial indeksowy.

W przydziale indeksowym wszystkie wskaźniki są skupione w jednym miejscu bloku indeksowym. W ten sposób wskaźniki
nie są rozrzucone po całym dysku jak to miało miejsce w przydziale listowym. Każdy plik ma własny blok indeksowy, będący
tablicą adresów bloków dyskowych, zawierających ten plik. Blok indeksowy ma określoną wielkość niezależną od wielkości
pliku. Zatem małemu plikowi, zajmującemu jeden, dwa bloki przy przydziale indeksowym trzeba przydzielić cały blok nawet
jeśli tylko jeden lub dwa wskaźniki będą w nim różne od nil. Jeśli z kolei blok indeksowy będzie za mały nie pomieści
adresów bloków większego pliku.

Oto przykłady mechanizmów pozwalających poradzić sobie z tym problemem:



schemat listowy

Polega na łączeniu bloków indeksowych. Blok indeksowy składa się z n wskaźników z których ostatni jest równy nil dla
małego zbiory, natomiast dla dużego będzie wskaźnikiem do następnego bloku indeksowego.



Indeks wielopoziomowy

Polega na użyciu oddzielnego bloku indeksowego do wskazywania bloków indeksowych, których wskaźniki wskazują już
bezpośrednio na bloki pliku.

PLANOWANIE DOSTĘPU DO DYSKU

Ważną rzeczą jest, aby usługi dyskowe były jak najszybsze. W tym celu należy odpowiednio organizować dostęp do dysku.
poniżej znajdziecie kilka metod planowania dostępu do dysku.

Planowanie metodą FCFS

Jest to najprostsza metoda planowania dostępu do dysku. Działa ona na zasadzie pierwszy nadszedł-pierwszy
obsłużony (First Came First Serviced).

Algorytm ten jest łatwy do zaprogramowania, jednak ma istotną wadę. Jak widać na powyższym rysunku, głowica
gwałtownie wychyla się przemieszczając od ścieżki 122 do 14 i z powrotem do 124.

Planowanie SSTF

Wydaje się uzasadnione, aby dążyć do łącznej obsługi zamówień sąsiadujących z bieżącym położeniem głowicy, aby
w ten sposób ograniczać jej niepotrzebne ruchy.

Planowanie SSTF działa na podstawie algorytmu noszącego nazwę najpierw najkrótszy czas przeszukiwania (shortest
seek-time first). Algorytm SSTF wybiera zamówienie z minimalnym czasem przeszukiwania względem aktualnego
położenia głowicy.

Metoda ta jest znacznie lepsza od FCFS, ale ma też swoje wady. Można wyobrazić sobie sytuację w której jedno
zamówienie będzie dotyczyło odległej ścieżki, (np. 183 na rysunku), natomiast wszystkie pozostałe zamówienia będą
dotyczyły ścieżek wcześniejszych (10, 5 15 ,17, 14 itd.), w takiej sytuacji zamówienie do ścieżki 183 nie zostanie
zrealizowanie.

planowanie metodą SCAN

W tym algorytmie głowica czytająco-pisząca startuje z jednego końca dysku i przemiesza się w kierunku
przeciwległego końca, obsługując zamówienia które napotyka po drodze, aż dotrze do końca dysku. W tym miejscu
zmienia kierunek na przeciwny itd. Algorytm ten bywa nazywany algorytmem windy.

PS.

Jeśli komuś nie podoba się analogia do windy to w książce opisana jest jeszcze jedna : Inną analogią jest tu
odgarnianie śniegu z chodnika podczas zadymki.. Niezłe co? J

Planowanie metodą C-SCAN

Metoda ta działa na podobnej zasadzie co algorytm zadymki, omówiony powyżej, z ta różnicą, że tutaj głowica po
dojściu do końca dysku wraca szybko na początek nie obsługując po drodze żadnych zamówień. Zamówienia są
realizowane gdy głowica przemieszcza się tylko w jednym kierunku.

Planowanie metodą LOOK (popatrz, czy istnieje zamówienie, zanim wykonasz ruch w tym kierunku)

Zarówno w planowaniu metoda SCAN jak i C-SCAN głowica przemieszcza się zawsze od jednego skrajnego położenia na
dysku do drugiego. W praktyce algorytmy te nie są jednak implementowane w ten sposób. Najczęściej głowica przesuwa się
do skrajnego zamówienia w każdym kierunku. Kiedy już nie ma zamówień w danym kierunku, wtedy głowica zaczyna
przesuwać się w przeciwnym kierunku.

TWORZENIE KOLEJEK DO SEKTORÓW

W urządzeniach ze stałymi głowicami, takich jak bębny, stosuje się inne algorytmy. Jednym z nich jest tworzenie kolejek do
sektorów. W bębnach każda ścieżka jest podzielona na sektory. Algorytm tworzenia kolejek do sektorów definiuje oddzielną
kolejkę do każdego sektora na bębnie. Zamówienie które dochodzi do sektora i zostaje umieszczone w kolejce do tego sektora.
W chwili gdy sektor i obraca się pod głowicami czytająco-piszącymi, pierwsze zamówienie z jego kolejki zostaje obsłużone.

SYSTEMY PLIKÓW

Struktura katalogowa

Pliki w systemie komputerowym są reprezentowane za pomocą pozycji w katalogu urządzenia lub tablicy dysku logicznego.

Katalog taki przechowuje dane dotyczące każdego pliku w systemie, takie jak:



Nazwa pliku



Typ pliku



Lokalizacja (jest to wskaźnik do urządzenia i lokalizacja pliku na tym urządzeniu)



Rozmiar



Bieżące położenie (jest to wskaźnik do bieżącej pozycji czytania lub pisania w pliku)



Ochrona (Informacje kontroli dostępu służą do sprawdzania, kto może plik czytać, zapisywać, wykonywać itd.)



Licznik użycia (jest to informacja o liczbie procesów, które jednocześnie używają danego pliku.



Czas, data i identyfikator procesu

OPERACJE PLIKOWE



Tworzenie pliku



Pisanie do pliku



Czytanie pliku



Usuwanie pliku

METODY DOSTĘPU

Dostęp sekwencyjny

Zawartość pliku jest przetwarzana po kolei, jeden rekord za drugim.

Dostęp bezpośredni

Dostęp bezpośredni jest oparty na dyskowym modelu pliku. Plik traktuje się jaki ciąg ponumerowanych
bloków lub rekordów. Plik o dostępie bezpośrednim pozwala na czytanie lub zapisywanie dowolnych bloków.
Dostęp bezpośredni jest szeroko stosowany, szczególnie dobrze sprawdza się przy obsłudze dużych plików.

Inne metody dostępu

Bazując na metodzie dostępu bezpośredniego można tworzyć inne metody dostępu. Metody te zawierają zazwyczaj
konstrukcję indeksu pliku. Indeks ten, podobnie jak skorowidz na końcu książki zawiera wskaźniki do rożnych bloków. Aby
znaleźć jakąś pozycję w pliku przeszukuje się najpierw indeks, a następnie używa wskaźnika w celu uzyskanie bezpośredniego
dostępu do pliku i odnalezienia potrzebnej sekcji.

SEMANTYKA SPOISTOŚCI

Semantyka spoistości jest to właściwość systemu określająca semantykę jednoczesnego dostępu do pliku dzielonego przez
wielu użytkowników.

Semantyka spoistości systemu Unix



Wynik operacji pisania wykonanej przez użytkownika otwartego pliku jest natychmiast widoczny dla innych
użytkowników, którzy maja otwarty ten sam plik.



Istnieje tryb dzielenia, w którym użytkownicy pliku dzielą wskaźnik bieżącej pozycji pliku. Zatem przesunięcie
wskaźnika przez jednego z użytkowników oddziałuje na wszystkie operacje wykonane przez użytkowników
współdzielących ten wskaźnik do pliku. Plik ma pojedynczy obraz, który uczestniczy we wszystkich dostępach,
niezależnie od ich p[pochodzenia

Ponieważ każdy plik ma tylko jeden obraz, współzawodnictwo o ten obraz powoduje opóźnianie wykonania operacji.

Semantyka sesji plikowej

W systemie plików Andrew zastosowano następującą semantykę spoistości



Wynik operacji pisania nie jest natychmiast widoczny dla innych użytkowników , którzy mają równocześnie otwarty
ten sam plik.



Po zamknięciu pliku zmiany, które zostały do niego wprowadzone, będą widoczne dopiero w następnych sesjach.
Otwarte, bieżące egzemplarze tego pliku nie będą odzwierciedlać tych zmian.

W tym przypadku wielu użytkowników może korzystać z jednego pliku bez dodatkowych opóźnień.

ORGANIZACJA STRUKTURY KATALOGOWEJ

Katalog jednopoziomowy

Jest to najprostsza struktura katalogowa. Wszystkie pliki są umieszczone w tym samym katalogu. Istotną wadą takiego
systemu jest to że nazwy plików w katalogu nie mogą się powtarzać. Dlatego tworzy się struktury wielopoziomowych
katalogów. Poza tym łatwiej jest wtedy znaleźć potrzebny plik.

Ochrona Rozdział 11.

Dlaczego stosujemy ochronę :

Zapobieganie zamierzonym, złośliwym naruszeniom ograniczeń dostępu dokonywanych przez użytkowników - Zapewnienie ,
aby każda wykonywana część programu (procesu) używała zasobów systemowych przewidywanych dla danego użytkownika

Domeny ochrony.

Syst. Komputerowy to zbiór procesów i obiektów. Obiekty=elementy sprzętu (procesor, RAM, itp.), elemanty
oprogramowania (pliki, programy.). Każdy obiekt ma jednoznaczną nazwę, oraz operacje charakterystyczne dla obiektu
(procesor - wykonuje rozkazy, czytnik zapisuje itp.)

Każdy proces powinien mieć dostęp tylko do tych zasobów do których został uprawniony. Jeszcze lepiej jak by miał dostęp
tylko do tych zasobów, które są potrzebne do wykonania zadania (Nazywamy to zasada wiedzy koniecznej = need to know )
stosowanie do powyższej reguły ogranicza liczbę uszkodzeń systemu przez wadliwie działający proces ( im do mniej zasobów
ma dostęp tym mniej może uszkodzić).

Dla wygody opisu powyższego schematu wprowadzamy pojęcie domeny ochrony . Proces działa wewnątrz domeny ochrony,
która określa dostępne dla niego zasoby. Każda domena definiuje zbiór obiektów i rodzaje operacji dostępne dla danego
obiektu. Możliwość wykonania operacji na danym obiekcie to prawo
dostępu渀Ā

蠀¥
舀 Ā 렀¥ zytaj, pisz}> to proces działający w domenie D może plik dane.dat
zapisywać i odczytywać ale innych operacji nie może wykonywać.

Domeny mogą dzielić między sobą prawa dostępu. Np. prawo <drukarka,drukuj> może być dzielone przez domeny D1 i D2 ,
proces działający w którejś z domen może drukować na drukarce.

Załóżmy model systemu operacyjnego działający w dwóch trybach : monitora i użytkownika. Gdy proces działa w trybie
monitora, może wykonywać rozkazy uprzywilejowane , sprawując pełną kontrolę nad systemem. Natomiast jeżeli proces
działa w trybie użytkownika, to może wykorzystywać tylko obiekty dostępne dla danego użytkownika, i tylko działać w
określonym obszarze pamięci. Tak więc mamy dwie domeny. Ale systemie wieloprogramowym mamy kilku użytkowników
którzy wymagają ochrony między sobą, a co za tym idzie schemat ochrony się komplikuje....

Macierz dostępów

Model ochrony możemy przedstawić jako macierz dostępów.

Czytnik dysk.

Drukarka

czytaj

Czytaj

czytaj

drukuj

czytaj

Wykonaj

czytaj/pisz

Wiersze - domeny ,kolumny obiekty

Element macierzy dostęp(i,j) określa zbiór operacji które proces działający w domenie Di moze wykonać na elemencie Oj
{F1,F2...}

Tablica globalna.

Najprostsza realizacja macierzy dostępów jest Tablica globalna. Jest to zbiór trójek uporządkowanych < domena, obiekt, zbiór
praw >. Za każdym razem gdy operacja ma być wykonana na obiekcie Oj w domenie Di, wówczas w tablicy globalnej szuka
się trójki <Di,OJ,Rk>, przy czym M. Należy do Rk. Jeżeli taka trójka istnieje to operację można wykonać . W przeciwnym
razie błąd.

Wady : Tablica jest wielka =>nie mieści się w pamięci oper. => jest na dysku => dodatkowe spowolnienie operacjami we/wy,
Bak możliwości stosowania grupowania obiektów, Jeżeli jakiś obiekt ma być dostępny dla każdego do odczytania to musi
wystąpić w każdej domenie.

Wykazy dostępów.

Jeżeli weźmiemy kolumnę z macierzy dostępów to otrzymamy coś w rodzaju wykazu dostępów do danego obiektu.
Otrzymamy wykaz dostępów do każdego obiektu złożony z par <domena, zbiór praw>, które definiują wszystkie domeny z
niepustymi zbiorami praw dostępu do danego obiektu.

Możemy również dodać do zdefiniowanego wykazu dostępów standartowe zbiory praw dostępu. Kiedy pojawi się próba
wykonania operacji M. na obiekcie Oj w domenie Di to w wykazie dostępów szukamy obiektu Oj i związanej z nim pary
<Di,Rk> ( M. należy do Rk ) jeżeli znajdziemy to operacja zostanie wykonana, jeżeli nie to błąd. Jeżeli nie ma pozycji w
wykazie to możemy przeszukać standartowy zbór praw dostępu. Przeszukanie będzie szybsze jeżeli zbór standartowy
przeszukamy na początku.

Wykazy możliwości.

Sytuacja jak wyżej tyle że teraz każdy wiersz macierzy możemy przedstawić jako macierz możliwości domeny. Jest to wykaz
obiektów i operacji które na tych obiektach można wykonać. W celu wykonania operacji M. na obiekcie Oj proces wykonuje
operację Oj, jako parametr określając możliwość dostępu do Oj, jeżeli mamy taką możliwość to mamy dostęp. (

W książce też to jest

zagmatwane, ale działa to tak jak w wykazie dostępów tylko że rozpatrujemy to poziomie).

Wykaz możliwości jest związany z domeną, nie jest dostępny dla procesu (dział. w domenie), wykaz jest obiektem
chronionym i dostępny dla użytkownika tylko pośrednio =>wykaz możliwości jest bezpieczny =>chronione obiekty
zabezpieczone przed nieautoryzowanym dostępem. (Jest to ochrona na podstawie możliwości ).

Mechanizm zamka z kluczem.

Sposób pośredni między wykazami dostępów a wykazami możliwości. Każdy obiekt ma wykaz jednoznacznych wzorców
bitowych zwanych zamkami. Każda domena ma wykaz wzorców bitowych zwanych kluczami. Proces działający w domenie
ma dostęp do obiektu ma do niego dostęp tylko wtedy jeżeli klucz domeny pasuje do jednego z zamków obiektu.

Porównanie (powyższych)

Wykazy możliwości odpowiadają zapotrzebowaniom użytkowników, użytkownik tworzy obiekt i określa które domeny mają
mieć dostęp i jakie operacje można wykonywać. Ale informacja o prawach dostępu w poszczególnych domenach nie są
zlokalizowane więc trudno określać zbór praw dla każdej domeny, ponadto wykazy dostępu mogą być bardzo długie
=>przeszukanie czasochłonne.

Wykazy możliwości nie odpowiadają bezpośrednio użytkownikom, są jednak pożyteczne przy lokalizowaniu informacji o
poszczególnych procesach. Uniemożliwianie dostępu jest czasami niewydajne (

Cytuje z książki).

Mechanizm zamka z kluczem jest efektywny i elastyczny. Klucze można przekazywać domeny do domeny, ponadto klucze
można łatwo uaktualniać => w większości systemów stosujemy tę metodę.

Dynamiczne struktury ochrony

Związek między procesem a domeną może być statyczny ( zbiór zasobów jest ustalony) lub dynamiczny.

Przykład rozpatrywany: Proces składający się z dwóch faz czytania i zapisywania.

Statyczna domena musi mieć zdefiniowane prawo zarówno do odczytu i zapisu. Sprzeczne jest to z zasadą wiedzy koniecznej
(patrz wyżej).

Jeżeli weźmiemy pod uwagę dynamiczne powiązanie to należy pozwolić na dokonanie zmian z zapisie zawartości macierzy
dostępów, tak aby mogła ona zawsze odzwierciedlać minimum praw dostępu dla procesu.

Jeżeli nie możemy zmieniać zawartości domen to możemy utworzyć nową domenę ze zmienioną wartością i przełączać się do
tej domeny wówczas gdy konieczna jest zmiana wartości domeny.

Gdy przełączamy proces z jednej domeny na drugą to traktujmy to jako operację przełącz na obiekcie (domenie).

Czytnik

drukarka

czytaj

przełącz

czytaj

drukuj

przełącz

czytaj

wykonaj

czytaj/pisz

przełącz

Proces działający w domenie D1 może się przełączyć do D2, proces działający w D2 może się przełączyć do D3 lub D4

A teraz zmiana zawartości domeny. Umożliwienie kontrolowanych zmian dostępów wymaga trzech dodatkowych praw:
kopiowania, właściciela, kontroli.

Możliwość kopiowania prawa dostępu oznaczono *. Prawo kopiowania pozwala na skopiowanie tylko w obrębie jednej
kolumny. W powyższym przykładzie proces działający w obrębie D2 może skopiować operację czytania do dowolnego
elementy macierzy w obrębie obiektu F2. Więc macierz dostępu może przyjąć postać (patrz ta z prawej).

Unieważnianie praw dostępu

Czasami chcemy unieważnić prawo dostępu do niektórych obiektów dzielonych przez różnych użytkowników.

Unieważnienie może być: - natychmiast lub z opóźnieniem

- wybiórczo lub ogólnie (wszystkim użytk. lub niektórym)

- Częściowo lub całkowicie (kilka praw lub wszystkie)

- Czasowo lub na stałe

Jeżeli stosujemy wykaz dostępów to unieważnianie proste ponieważ wyszukujemy w wykazie prawo dostępu i usuwamy je.
Jeżeli mamy wykaz możliwości to ciężej bo możliwości są rozproszone po całym systemie.

Ochrona w istniejących systemach.

Domena - Co to właściwie jest ?

Domena może byż zdefiniowana dla każdego użytkownika => Czyli jest to zbiór obiektów do których można mieć
dostęp zależy od identyfikacji użytkownika. Przełączanie domen wtedy kiedy zmiana zalogowanego użytkownika.

Każdy proces może być domeną. Każdy wiersz macierzy dostępów definiuje obiekty do których proces może mieć
dostęp. Przełączanie między domenami odpowiada wysyłaniu przez jakiś proces komunikatu do innego procesu i
oczekiwaniu na odpowiedź.

UNIX

Schemat ochrony dotyczy głównie systemu plików. Z każdym plikiem związane są trzy pola ochronne, określające
odpowiednio - właściciela, grupę i resztę użytkowników. Każde pole składa się z trzech bitów: r, w, x. r (read) nadzoruje
dostęp do czytania, w (write) do pisania, x (eXecute) do wyko

nania pliku.

Domena w UNIXie jest związany z użytkownikiem. Zmiana domeny (związana ze zmianą użytkownika) wykonywana jest w
następujący sposób. Z każdym plikiem związany jest identyfikator użytkownika i bit domeny ( zwany bitem user-id) Gdy
użytkownik A (user-id=A) rozpoczyna wykonanie pliku będoącego własnością użytkownika B i mającego ustawiony bit
domeny. Wówczas user-id=B a po zakończeniu wykonywania pliku, identyfikatorowi użytkownika user-id przywraca się
wartość A (

Też sądzę że książka jest nieco enigmatyczna)

Podobny mechanizm jest kiedy uprzywilejowany program ma być udostępniony zwykłemu użytkownikowi. W takim
przypadku system ustawia bit ustanowienia identyfikatora jest = 1 i to powoduje że identyfikator użytkownika (set-uid)
zmienia się podczas pracy programu.

MULTICS

W tym systemie (

dość znanym i rozpowszechnionym :-) )

schemat ochrony plików jest struktury pierścieniowej. Z każdym plikiem

związany jest wykaz dostępów oraz pola dostępów dla właściciela i reszty świata. Każdy pierścień to jedna domena.
Pierścienie są ponumerowane 0 - 7. Proces działający w domenie D3 jest bardziej uprzywilejowany niż D4 . Przełączanie
domen występuje wtedy gdy proces przechodzi z jednego pierścienia do drugiego. Z każdym procesem związany jest licznik
bieżącego numer pierścienie określający pierścień w którym proces się znajduje.

Oczywiście proces przełączania musi być kontrolowany, bo proces mógłby przejść na pierścień 0 zrywając wszelką ochronę.
Modyfikuje się pole pierścienia tak aby zawierało :ograniczniki dostępu, wartość graniczną oraz wykaz bram którymi można
wywoływać segmenty.

HYDRA

Hydra jest systemem ochrony charakteryzujący się dużą elastycznością, w którym zastosowano schemat możliwości. Do
zbioru stałego możliwych praw dostępu należą np. prawo do czytania, prawo do pisania lub wykonywania. Ponadto system
zawiera środki umożliwiające deklarowanie własnych praw.

System Cambrige CAP

W tym systemie są dwie możliwości ochrony danych:

Zwykły rodzaj to możliwość obsługi danych - jedyne realizowane prawa to czytanie, zapisywanie, wykonywanie
poszczególnych segmentów pamięci.

Możliwość programowa, tą opcję realizuje procedura która jest napisana przez programistę i dostosowana do
własnych oczekiwań. - co daje nam możliwość prowadzenia własnej polityki ochrony.

OCHRONA NA POZIOMIE JĘZYKA OPROGRAMOWANIA

Ochrona w istniejących systemach operacyjnych jest zazwyczaj organizowana na poziomie jądra systemu operacyjnego.
Polityka ochrony zasobów w systemie może ulegać zmianom z zależności od zastosowania i upływu czasu. Więc ochrona nie
może być sprawą którą zajmuje się projektant systemu operacyjnego. Modyfikowanie ochrony powinno być dostępne również

dla użytkownika (projektanta zastosowań). Tu wkraczają języki programowania. Określenie kontroli dostępu w systemie
sprowadza się do napisania odpowiedniej deklaracji w odniesienie do danego zasobu. Deklarując ochronę projektant może
określić własne wymagania w stosunku do ochrony jak i innych zasobów systemu.

Jednak ochrona na poziomie jądra systemu jest bezpieczniejsza ponieważ. Mechanizm ochron programowy musi przyjmować
więcej założeń odnośnie do operacyjnego stanu systemu.

Jakie argumenty przemawiają na rzecz wymuszania ochrony przez jądro systemu, w porównaniu z wymuszeniem przez
kompilator:

Bezpieczeństwo. W systemie ochrony tworzonym przez kompilator zależy od poprawności translatora, od pewnych
bazowych mechanizmów zarządzania pamięcią, chroniących elementy w których znajduje się kod wykonywanego
programu, oraz od bezpieczeństwa plików z których program ładowany jest do pamięci

Elastyczność. Jądro ogranicza realizację polityki zdefiniowane przez użytkownika. Z pomocą języka programowania
polityka ochrony może podlegać deklarowaniu. Jeżeli język nie gwarantuje wystarczającej elastyczności to może
zostać rozszerzony lub wymieniony na inny. Powoduje to mniej zaburzeń niż modyfikowanie jądra systemowego.

Wydajność. Najlepszą wydajność uzyskujemy na poziomie sprzętu lub jądra systemu

Zagadnienia ochrony

Zmienianie obiektów.

Gdy użytkownik przekazuje obiekt do procedury jako argument, wówczas może być konieczne zapewnienie, że procedura nie
zmieni tego obiektu. Ograniczenie - prawo dostępu nie może zawierać prawa do zmiany obiektu. Ale w niektórych syst (np.
HYDRA) możemy mieć możliwość zmiany praw dostępu => możemy obejść prawo dostępu definiowane przez użytkownika
(właściciela) obiektu. Więc użytkownik może uwierzyć że procedura wykona zadanie poprawnie, ale nie musi być
poprawnie bo: błędy sprzętowe lub oprogramowania.

Ograniczenie przenoszenia praw dostępu.

Użytkownik A chce udostępnić obiekt o użytku pewnej grupie użytkowników, ale nie chce aby oni udostępniali obiekt komu
innemu. Można uzyskać taką ochroną przez powiązanie praw kopiowania i właściciela tylko z właścicielem obiektu. (Ale
użytkownik mający dostęp może pozwolić się zarejestrować się komuś innemu pod swoją nazwę i w ten sposób udostępnić
obiekt)

Unieważnienie praw dostępu

Patrz wyżej.

Koń trojański

Segment kodu programy nadużywający swojego środowiska (w szczególności praw dostępu), w celu osiągnięcia korzyści dla
tego co napisał program.

(Analogicznie zdobyto Troję więc, chyba nie ma co więcej się rozpisywać)

Wzajemne podejrzenia

Zagadnienie podejrzewających się systemów. Np. program jest wywoływany przez kilku użytkowników, podejmują oni
ryzyko na wypadek błędnego działania programu i uszkodzenia przez niego danych lub przywłaszczenia przez niego praw
dostępu. Podobnie program może mieć własne pliki które nie powinny być udostępnione użytkownikom.

Poufność

Kwestia zagwarantowania że żadna informacja początkowo przechowywana w obiekcie nie przedostanie się poza środowisko
jego wykonania nazywa się kwestią poufności.

Tylne drzwi

Projektant systemu może zostawić oprogramowaniu lukę, którą on tylko może wykorzystać. Np. specyficzna nazwa
użytkownika i hasło => obchodzi normalne procedury bezpieczeństwa. Sprytnym sposobem jest zainstalowanie tylnych drzwi

w kompilatorze przez co kompilator generuje tylne drzwi niezależnie od kodu źródłowego =>przeglądanie kodu nie ujawni
niedociągnięć. Aby wykryć tylne drzwi trzeba przeanalizować kody źródłowe wszystkich elementów systemu, a te mają kilka
milionów linii więc trudno jest coś znaleźć.

Robaki i Wirusy

W większości systemów istnieją środki rozmnażania procesów. Robakiem nazywamy proces używający tego mechanizmu w
celu osłabienia systemu. Robak rodzi własne kopie, zużywając zasoby systemowe i uniemożliwiając w efekcie innym
procesom dostęp do systemu.

Wirus - Też się rozmnaża ale jest fragmentem kodu innego programu. (

wirus może robić mnóstwo rzeczy, w różnych warunkach o czym każdy

wie)

Bezpieczeństwo

Ochrona jest zagadnieniem wewnętrznym. Zapewnienie bezpieczeństwa wymaga oprócz zapewnienia ochrony,
przeanalizowania środowiska zewnętrznego, w którym działa system.

Podstawowym problemem bezpieczeństwa jest problem tożsamości. System ochrony zależy od możliwości identyfikowania
działających programów i procesów. A ta możliwość jest uzależniona od możliwości identyfikowania każdego z
użytkowników systemu => jak rozstrzygnąć czy identyfikacja jest autentyczna? . Identyfikacja może używać kombinacji
trzech zbiorów : stanu posiadania (karta magn. Klucz), wiedzy użytkownika (nazwa i hasło), atrybutu użytkownika (odcisk
palca, podpis)

Najczęściej używamy hasła. Jeżeli podane hasło pasuje do użytkownika to uważa się że użytkownik został wylegitymowany.
Hasło możemy skojarzyć z każdym zasobem (oczywiście jeżeli hasło podam poprawnie to mamy dostęp do obiektu). Możemy
mieć różne hasła do różnych praw dostępu (inne do czytania, inne do zapisywania).

Największy kłopot z hasłami bo trudno utrzymać hasło w sekrecie, krótkie hasła dają małe możliwości wyboru => łatwo
zgadnąć po określonej ilości prób. Hasła mogą być generowane przez system lub wprowadzane przez użytkownika.

Zabezpieczenia :

-administrator sprawdza hasła i łatwe do odgadnięcia każe zmienić,

-wymuszona okresowa zmiana haseł,

-zastosowanie par haseł przy logowaniu system podaje jedną część hasła a użytkownik musi podać drugą (np. system podaje
losową liczbę całkowitą, a użytkownik po zastosowaniu algorytmu hasła (np. dodaj 4) podaje drugą część, jeżeli para jest
zgodna to autoryzacja). Wadą tej metody jest konieczność przechowywania haseł (par lub algorytmu) w sekrecie.

W UNIXie stosuje się wariant algorytmiczny w celu uniknięcia konieczności trzymania haseł w tajemnicy. Każdy użytkownik
ma hasło. System zwiera funkcję, której wartość wartość łatwo obliczyć, lecz bardzo trudno jest zaleźć dla tej funkcji funkcję
odwrotną (tak sądzą projektanci). Funkcja służy do kodowania haseł. X to argument funkcji czyli nasze hasło, a f(x) to wartość
funkcji czyli nasze hasło w postaci zakodowanej. W pliku z hasłami przechowuje się tylko hasła zakodowane, przy podawaniu
hasła system je koduje przy pomocy wspomnianej funkcji i sprawdza z zapisanym w zakodowanym pliku. (Znając funkcję
odwrotną to moglibyśmy rozkodować zakodowane hasła)

Wadą tej metody jest brak kontroli systemu nad hasłami. Każdy kto ma kopię pliku z hasłami zastosować szybkie procedury
szyfrowania i porównać każde hasło z podręcznym słownikiem haseł. W obecnych systemach UNIX używa się haseł
kombinowanych, w rodzaju dwóch słów oddzielonych znakiem interpunkcyjnym, które trudno jest złamać.

W celu zwiększenia bezpieczeństwa możemy wprowadzić kontrolę zagrożeń.

Licznik niewłaściwych haseł podawanych (przekroczenie określonej liczby powoduje ostrzeżenie dla administratora o
próbie zgadywania hasła.

Dziennik kontroli - rejestrujemy czas użytkownika i rodzaje wszystkich dostępów do obiektów.

Bezpieczeństwo komputerów pracujących w sieciach otwartych jest bardziej zagrożone niż w systemach autonomicznych
ponieważ atak nie następuje ze znanego zbioru punktów dostępu, tylko z nie wiadomo skąd.

Szyfrowanie.

Aby zachować w tajemnicy dane przekazywane w sieci możemy zastosować szyfrowanie.

Mechanizm:

szyfrowanie informacji

przesłanie niepewnymi kanałami

Odszyfrowanie informacji

Głównym zagadnienie jest zastosowanie algorytmu szyfrowania takiego który byłby bardzo trudny do złamania.

Najczęściej stosowana metoda:



ogólny algorytm szyfrowania E



ogólny algorytm deszyfrowania D



tajny klucz.

Wówczas algorytm szyfrowania wiadomości m ma mieć właściwości

D(E(m)) = m.

Algorytmy D , E efektywne

Bezpieczeństwo zależy tylko od tajności klucza a nie od tajności algorytmy E lub D

W tym schemacie najbardziej kłopotliwa jest bezpieczna dystrybucja klucza.

Przykładowy
algorytm.

Rozdział 12 Struktury systemów rozproszonych

Systemy rozproszone cechy-



każdy procesor ma własną pamięć lokalną



procesory komunikują się za pomocą różnych linii komunikacyjnych

więc system rozproszony jest zbiorem luźno powiązanych ze sobą procesorów powiązanych siecią komunikacyjną.

Dla konkretnego procesora systemu rozp. pozostałe procesory i ich zasoby są zdalne, a własne zasoby lokalne.

Procesory w systemie mogą się różnić (mikroprocesory, stacje robocze itp. ). Procesory można określać jako : stanowisko, węzeł, końcówka, komputer itp.

Zasada : jedno stanowisko (system obsługi - server) zarządza zasobami, z których korzysta inne stanowisko (klient). Zadaniem systemu rozproszonego jest tworzenie
wydajnego i wygodnego środowiska dzielenia zasobów.

Cztery główne powody uzasadniające budowę systemów rozproszonych:



Dzielenie zasobów - Użytkownik pracujący na jednym stanowisku może korzystać z zasobów innego stanowiska ( i na odwrót). Możliwe jest dzielenie
plików, praca na rozproszonych bazach danych, drukowanie na zdalnych stanowiskach itd. itp.



Przyspieszanie obliczeń

- Obliczenia można podzielić na kilka mniejszych części i dokonywać ich współbieżnie na kilku

stanowiskach.



Niezawodność - Jeżeli jedno stanowisko pracujące w systemie ulegnie awarii to cały system nie musi przerywać pracy
(chyba że padnie server lub inne odpowiedzialne stanowisko). System powinien wstrzymać korzystanie i udzielanie
zasobów z uszkodzonego stanowiska, i jeśli to możliwe przenieść zadanie na inne stanowisko.



Komunikacja - Użytkownicy mają możliwość wymiany informacji => na dowolne odległości => możliwa współpraca kilku odległych osób nad jednym
projektem.

Topologia

Czyli fizyczny sposób rozmieszczenia i połączenia stanowisk. Kryteria oceny topologii

Koszt podstawowy - koszt podłączenia stanowisk w system

Koszt komunikacji - czas przesyłania komunikatu

Niezawodność

Topologie:



Połączenie pełne, czyli każde stanowisko jest bezpośrednio połączone z każdym innym stanowiskiem.

Koszt podstawowy tego rozwiązania wysoki (wysoki koszt przyłączania kolejnego stanowiska). Szybkie przesyłanie komunikatów, system wysoce niezawodny.



Połączenie częściowe



Hierarchia



Gwiazda



Pierścień



Szyna wielodostępna

.........

Komunikacja

Projektant sieci komunikacyjnej musi wziąć pod uwagę cztery kwestie

Strategie wyboru trasy - Jeżeli A chce się komunikować z B to: jeżeli istnieje jedna fizyczna ścieżka to komunikat musi zostać wysłany tą ścieżką, jeżeli
istnieją kilka możliwych ścieżek to stanowisko zawiera tablicę tras wykazującą alternatywne drogi. Istnieją 3 schematy określania tras:

trasa stała

-z góry określona

trasa wirtualna - droga jest określona tylko dla jednej sesji

trasa dynamiczna - droga jest określana dynamicznie za każdą próbą przesłania komunikatu.

Strategie połączeń - jak A i B wysyła ciąg komunikatów:

komutowanie łączy - jeżeli A i B chcą wysyłać komunikaty do siebie, to ustala się między nimi

stałe połączenie fizyczne dostępne tylko dla nich.

komutowanie komunikatów - łącze miedzy A i B przydzielamy tylko na czas trwania przesyłania

komunikatu.

komutowanie pakietów - Komunikaty dzieli się na pakiety równej długości i każdy pakiet przesyła

się oddzielnie najlepszym aktualnie łączem. Po komunikacji oczywiście łączymy pakiety ze sobą
w jedną całość.

Rywalizacja - jeżeli kilka stanowisk do komunikacji ma jedno łącze to może dojść do kolizji w przesyłaniu komunikatów. Zapobiegamy kolizjom na trzy
sposoby:

Wielodostęp do łącza sieci z badaniem stany kanału. Przed wysłaniem komunikatu stanowisko

prowadzi nasłuch kanału, czy przez dane łącze nie jest przesyłany jakiś komunikat ( jeżeli jest
przesyłany to stanowisko czeka aż się zwolni łącze)(CSMA - carrier-sense with multiple acces -
wielodostęp do łącza z badaniem kanału). Wadą jest to że musimy czeka. CSMA zastosowano w
Ethernet.

Przekazywanie żetonu - w systemie (zazwyczaj typu pierścienia) krąży komunikat (żeton), jeżeli A

chce wysłać do B to A czeka na nadejście żetonu, bierze go, przesyła komunikat, oddaje żeton do
systemu. Gdy żeton zginie to system musi to wykryć i wygenerować nowy.

Przegródki na komunikaty

- pewna liczba prz

egródek stale krąży po systemie (zazwyczaj

typu pierścienia), każda przegródka może przenosić stałej długości komunikat oraz informację
kontrolną. A chce przesłać komunikat do B to czeka aż przyjdzie pusta przegródka, gdy tak się
stanie wkłada do niej komunikat z informacją kontrolną, przegródka idzie do adresata.

Strategie projektowe to zagadnie można podzielić na kilka warstw:

fizyczna - mechaniczne i elektryczne struktury transmisji

łącza danych - obsługa ramek czyli stałej długości pakietów

sieci - organizacja połączeń, określenie tras pakietów w sieci,

transportu - organizacja dostępu na niskim poziomie, przesyłanie komunikatów, dzielenie na

pakiety, kontrolowanie przepływu, generowanie adresów fizycznych.

sesji - implementacja sesji, czyli protokołów komunikacyjnych między procesami

prezentacji - pokonywanie różnic w formatach między różnymi stanowiskami w sieci

zastosowań - bezpośrednia interakcja z użytkownikami. Warstwa ta przesyła pliki, obsługuje

protokoły zdalnych rejestracji, pocztę elektroniczną.

sieci

Są dwa: lokalne ( na małych obszarach, budynkach) i globalne (na dużych obszarach)

Sieci lokalne

LAN - Local Area Network. Pojawiły się we wczesnych latach 70 jako substutu wielkich systemów komputerowych.

Szybko okazało się że jest w wielu przypadkach ekonomiczniejsze niż zakup wielkiego Systemu. Najczęściej używane połączenia to: para skręconych przewodów (jeden
z pasmem podstawowym drugi szeroko pasmowy), oraz kable światłowodowe. Prędkość komunikacji od 1Mb/s do 1Gb/s, norma to 10 Mb/s. Typowa sieć może składać
się z różnych mikrokomputerów, dzielonych urządzeń peryferyjnych, stacji roboczych, jednej lub kilku bram. Brama łączy nam jedną sieć lokalną z drugą (lokalną lub
globalną). Do budowy sieci stosuje się schemat ETHERNET, Środkiem łączności jest kabel ze schematem wykrywania kolizji (j.w.), komunikaty są przesyłane w
postaci pakietów.

Sieci Globalne

WAN - Wide Area Network.. Pojawiły się w późnych latach 60, jako akademickie konstrukcje badawcze, mające na celu umożliwienie wydajnej komunikacji między
ośrodkami akademickimi. Pierwsza taka sieć to był ARPANET któr rozrosła się na cały świat jako Internet. W obrębie USA działa TELENET, a Canady DATAPAC.

Stanowiska sieci są rozmieszczone na dużym obszarze geograficznym więc komunikacja jest powolna i zawodna.

Typowymi łączami są linie telefoniczne, łącza mikrofalowe i kanały satelitarne. Łącza komunikacyjne są nadzorowane przez specjalne procesory komunikacyjne.

Sieć globalna internet , system umożliwia połączenie ze sobą geograficzne odseparowanych komputerów nazywanych stacjami macierzystymi (host). Host-y różnią się
od siebie pod wzgl. Typu, syst. Operacyjnego. Stacje macierzyste są w sieciach lokalnych, te są połączone sieciami regionalnymi, a te są połączone ze sobą za
pośrednictwem komputerów nadzorujących trasy (routers

) w sieć o zasięgu światowym. Wiele stacji jest wyróżnionych wieloczłonowymi

nazwami (wip.pw.edu.pl.) i odpowiadającymi im numerami (148.81.82.34) ( a właściwie na odwrót) przez domenowy system
nazewniczy.

Typy systemów operacyjnych

Dostęp do zasobów w systemie jest nadzorowany przez system operacyjny. Mamy dwa podstawowe uzupełniające się schematy korzystania z usług rozproszonego
systemu operacyjnego:



Sieciowe systemy operacyjne - użytkownicy są świadomi wielości maszyn w celu uzyskania dostępu do różnych zasobów, rejestrują się zdalnie na
odpowiednich maszynach lub przesyłają dane z maszyn własnych do własnych maszyn. Głównym zadaniem Sieciowego Systemu operacyjnego jest
tworzenie mechanizmu służącego do przesyłania plików. W internecie mamy FTP . Program pyta użytkownika o informację skąd plik ma być przesłany
oraz dane uwierzytelniające dostęp do pliku. W tym schemacie lokalizacja jest niezatajona przed użytkownikiem. Nie ma też praktycznie współdzielenia
pliku bo się go po prostu kopiuje.



Rozproszony System Operacyjny - W rozproszonym systemie operacyjnym użytkownicy uzyskują dostęp do zdalnych zasobów tak jak do zasobów
lokalnych. Przemieszczenie danych i procesów odbywa się pod nadzorem systemu operacyjnego. Przemieszczanie danych: A chce dostęp do pliku który
jest w B. 1 metoda cały plik jest przesyłany na stanowisko A, po wykonaniu tego zabiegu wszystkie dostępy są lokalne. Gdy użytkownik rezygnuje z
dostępu do pliku to jest on z powrotem przesyłany na stanowisko B (przesyłamy cały plik. 2 metoda polega na przesłaniu tylko tej porcji pliku która jest

niezbędna do działania. Przemieszczenie obliczeń : jeżeli chcemy dokonać obliczeń da dużych plikach to zamiast je przesyłać można przesłać obliczenia
do komputera gdzie te duże pliki są, i przesłać wyniki z powrotem. Przemieszczenie procesów wyznaczony proces nie zawsze jest wykonywany na
stanowisku na którym go zainicjowano , czasami lepiej jest go wykonać na innym stanowisku ponieważ

równoważne załadowania - wyrównujemy obciążenia poszczególnych stanowisk sieci

przyspieszamy obliczenia - dzieląc proces na pod procesy i puszczając te kawałki współbieżnie na kilku stanowiskach

preferencje sprzętowe - proces może wymagać konkretnego typu procesora

preferencje oprogramowania - proces może wymagać konkretnego oprogramowania.

Zagadnienia projektowe

Użytkownik powinien mieć taki dostęp do zdalnych systemów rozproszonych tak jakby one były lokalne, natomiast odpowiedzialność a odnalezienie
zasobów spada na system.

Mobilność użytkowników - użytkownik powinien móc zarejestrować na dowolnej maszynie należącej do systemu. System przenosi domowy katalog
użytkownika do maszyny przy której aktualnie się znajduje.

Odporność na błędy - komunikacji, awarii dysków, pamięci. System powinien działać (może mniej wydajnie) pomimo wystąpienia sytuacji awaryjnej.

Zdolność do adaptowania się do wzrastających zapotrzebowań na usługi (skalowalnowość) system jest skalowalny jeżeli reaguje na wzrost obciążeń
systemowych. Zasoby systemu skalowalnego powinny później osiągać stan przepełnienia. Dodawanie nowych zasobów może zmniejszać obciążenie ale nie
może pośrednio generować dodatkowego obciążenia.

Skrybowie:
Justyna Skrzyńska: część 3 i 6b
Daniel Antonik: część 2b i 6a
Jan Bąk: część 4 i 5
Piotr Hawemann: część 9 i 10
Tomasz Ładyko: część 11 i 12
Tomasz Gieorgijewski: część 1 , 2a , 7 i 8
UWAGA! TEKST JEST NIEAUTORYZOWANY!
Generatorzy nie biorą odpowiedzialności za przekazywane w nim treści.
Informujemy również, że tekst powstał jako skrypt elektroniczny do wykładów z Systemów
Operacyjnych na Wydziale Inżynierii Produkcji PW i jest w całości oparty na książce pt: "Podstawy
Systemów Operacyjnych" A. SILBERSCHATZA J.L. PETERSONA i P.B. GALVINA.

Wyszukiwarka

Podobne podstrony:
Podstawy systemow operacyjnych Nieznany
Zestaw E Podstawy Systemów Operacyjnych i systemów grafiki komputerowej (2)
podstawy systemow operacyjnych VK2TVKRYMJ4ICHUTQ4HPW4LTK43QGI4Q4K2ZSDI
Egzamin, E. Podstawy systemów operacyjnych i systemów grafiki komputerowej, E
E Podstawy systemów operacyjnych i systemów grafiki komputerowej
LINUX, SZKOLNE PLIKI-mega zbiory (od podstawówki do magisterki), Systemy operacyjne
Podstawy informatyki, Systemy operacyjne, PODSTAWY INFORMATYKI (KONTYNUACJA SYSTEMÓW OPERACYJNYCH)
Podstawy architektury komputera, Szkoła, Systemy Operacyjnie i sieci komputerowe, utk, semestr II
Systemy operacyjne unix polecenia podstawowe
PODSTAWY DZIAŁANIA UKŁADÓW CYFROWYCH, Szkoła, Systemy Operacyjnie i sieci komputerowe, utk, semestr
Podstawowe Polecenia Systemu Operacyjnego DOS
Podstawy Informatyki Wykład IV System operacyjny
Rys historyczny i podstawowe pojęcia systemu operacyjnego, technik informatyk, soisk utk
1 Systemy Operacyjne 05 10 2010 Pojęcia Podstawowe
systemy operacyjne cw 09 podstawy administracji cz2
systemy operacyjne cw 08 podstawy administracji cz1

więcej podobnych podstron