Wykład nt. podstawy systemów operacyjnych -- pamięć




Praca semestralna
Podstawy systemów operacyjnych


Poprzedni | Spis treści
| Następny  | Zadania



Rozdział 3: Zarządzanie pamięcią


Do czego procesowi pamięć
Każdy prces działający w komputerze wymaga pamięci operacyjnej do przechowywania
kodu swego prograamu i danych które przetwarza.
Dane, które przetwarza proces reprezentowane są przez zmienne programu.
Przez zmienną programu rozumie się obszar pamięci o ustalonym adresie początkowym
i długości, do którego można odwoływać się z programu poprzez symbol zwany
nazwą zmiennej.  Każda zmienna posiada swój typ, definiowany jako
zbiór, którego elementy mogą być kodowane przez wartości zmiennej, np.
typ char języka C koduje znaki zbioru ASCII lub liczby z przedziału
-128 do 127.  Typ decyduje o długości obszaru przeznaczonego na zmienną.
Ważnymi typami zmiennych są zmienne wskaźnikowe. Przechowują one adresy
(adresy początku obszaru) innych zmiennych.
Z punktu widzenia zarządzania pamięcią wyróżnia się trzy klasy zmiennych:


Zmienne statyczne - są tworzone przy starcie procesu i istnieją przez cały
czas jego życia.

Określenie zmienna statyczna może być mylące. Zmienna ta, oczywiście,
może być modyfikowana przez program. Określenie statyczna odnosi się do
sposobu gospodarowania pamięcią tej zmiennej - rezerwuje się ją przy starcie
a zwalnia przy końcu procesu. Przez cały czas życia procesu dany obszar
pamięci wykorzystywany jest w ten sam sposób - na przechowywanie aktualnej
wartości danej zmiennej.

Zmienne lokalne podprogramów zwane też automatycznymi - są tworzone dla
każdego wywołania podprogramu i usuwane po jego zakończeniu.


Zmienne dynamiczne - są tworzone i usuwane w miarę potrzeby.

Wyróżnia się trzy zasadnicze grupy obszarów pamięci, z których korzysta
proces:


Obszary zajmowane przez kod programu i bibliotek. Na pamięci wchodzącej
w skład tych obszarów po załadowaniu programu (lub biblioteki) procesor
wykonuje jedynie operacje odczytu. Obszary te mogą być wspólny dla różnych
procesów wykonujących ten sam program, lub korzystających z tej samej bibloteki
ładowanej dynamicznie.


Obszary zajmowany przez prywatne dane programu, w tym zmienne statyczne
i dynamiczne. Obszar ten jest inicjowany przy starcie procesu początkowymi
wartościami zmiennych globalnych (często zerami). W trakcie życia procesu
dokonywane są zarówno operacje odczytu jak i zapisu. Obszar przechowujący
zmienne dynamiczne nazywany jest stertą. Tworzenie i niszczenie zmiennych
dynamicznych może powodować zwiększanie się i zmniejszanie tego obszaru
w trakcie życia procesu. Każdy proces wymaga własnego obszaru prywatnych
danych. Jeżeli proces składa się z wątków, wątki współdzielą obszar danych
procesu.


Obszar stosu. W obszarze tym zapamiętuje się adresy powrotów z podprogramów
oraz przechowuj zmienne lokalne (dla każdego wywołania podprogramu tworzony
jest jego własny komplet zmiennych lokalnych). Obszar ten jest rezerwowany
w pamięci przy starcie procesu. Z początku jest pusty. Wypełnia się i opróżnia
w miarę jak wywoływane i kończone są poszczególne podprogramy. Każdy wątek
wymaga własnego obszaru stosu.

Powyższe obszary pamięci bywają często nazywane segmentami odpowiednio
kodu, danych i stosu.
Można wyróżnić dodatkowe obszary pamięci dostępnej procesowi:


Obszary systemowe. W nowoczesnych systemach operacyjnych dostęp do tych
obszarów proces ma tylko wtedy, gdy wykonuje w trybie jądra podprogram
jądra systemu operacyjnego.



Dane systemu operacyjnego w tym np. bufory dyskowe,


kod jądra systemu operacyjnego,


kod sterowników urządzeń w pamięci ROM,


adresowalna pamięć urządzeń wejścia wyjścia, np. pamięć obrazu karty graficznej.



Pamięć dzielona - obszary pamięci przechowujące dane, do których dostęp
ma więcej niż jeden proces.


Pliki dyskowe mapowane na pamięć.

Rozważmy prosty program w C
#include <stdio.h>
#include <string.h>

char napis[] = "Hello world!";

void main()
{
  char *tymczasowa;
  tymczasowa=strdup(napis);
  printf("%s\n",tymczasowa);
  free (tymczasowa);
}

Rys. 3.1 Przykładowy program w C używający różnych klas zmiennych
W trakcie działania powyższego programu tworzone są (a potem usuwane) następujące
zmienne:


zmienna statyczna ``napis '' zawierająca łańcuch "Hello World!";


bezimienna zmienna statyczna zawierająca łańcuch "%s\n";


zmienna lokalna funkcji ``main'' typu wskaźnikowego (wskaźnik
do typu char) o nazwie ``tymczasowa'';


zmienna dynamiczna, będąca duplikatem zmiennej ``napis'', wskaźnik
do niej podstawiany jest do zmiennej ``tymczasowa''.


inne zmienne zadeklarowane w standardowej bibliotece C, których deklaracje
znajdują się w plikach nagłówkowych stdio.h i string.h

Przy starcie procesu wykonującego powyższy program w obszarze kodu programu
znajdzie się skompilowana funkcja ``main'' oraz skompilowane niezbędne
funkcje biblioteczne w tym funkcje ``printf'', ``strdup''
i ``free''. W obszarze danych statycznych utworzone będą zmienne
``napis'', bezimienna zmienna zawierająca łańcuch "%s\n"
oraz niesprecyzowane tutaj bliżej zmienne tworzone dla potrzeb bibliotek.
Po zainicjowaniu pamięci proces zaczyna wykonywać swój kod poczynając
od funkcji ``main''. W trakcie prologu tej funkcji rezerwowane
jest na stosie miejsce na zmienną ``tymczasowa''. W trakcie wykonania
(druga linijka) tworzona jest zmienna dynamiczna będąca duplikatem zmiennej
``napis'' a jej adres wstawiany jest do zmiennej ``tymczasowa''.
Przy końcu programu zmienna dynamiczna (której adres wciąż przechowuje
zmienna ``tymczasowa'') jest niszczona. Epilog funkcji ``main''
niszczy zmienną lokalną ``tymczasowa''. Zakończenie się tej funkcji
kończy jednocześnie proces. W trakcie usuwania zakończonego procesu niszczone
są pozostałe zmienne.

Gospodarka pamięcią w systemach bez mechanizmu pamięci
wirualnej


CP/M
Najprostszą gospodarkę pamięcią prezentuje system operacyjny CP/M. Ponieważ
w systemi tym może istnieć tylko jeden proces, dostaje on całą pamięć w
swoje władanie. System operacyjny iinformuje go jedynie, gdzie znajdują
się jego obszary pamięci. Poza tym ostrzeżeniem, system operacyjny nie
chroni swej pamięci przed procesem.

Systemy wieloprocesowe
W wieloprocesowych systemach operacyjnych należy stworzyć mechanizmy przydzielania
pamięci wielu procesom oraz ochrony pamięci przydzielonej poszczególnym
procesom i pamięci zajmowanej przez kod i dane jądra przed innymi procesami.
W pierwszych sysemach wieloprocesowych z ochroną pamięci uruchamiany
proces otrzymywał sztywną pulę pamięci wyznaczną przez adresy graniczne.
Proces musiał zmieścić swój kod i dane w zadanym obszarze. Użycie zmiennych
dynamicznych było w związku z tym ograniczone. W przypadku odwołania się
do adresów spoza wyznaczonych granic proces wpadał w pułapkę i był kończony.

MS-DOS
W systemie operacyjnym MS-DOS proces przy starcie może zarezerwować pewną
ilość tzw. segmentów pamięci operacyjnej położonej poniżej adresu 655360.
W trakcie życia może zarezerwować dodatkowe segmenty lub zwolnić je. Może
też rezerwować i zwalniać pamięć powyżej 1MB. Nowy proces będzie uruchomiony
pod warunkiem, że jest dość segmentów dla niego w obszarze pierwsych 640kB
pamięci. MS-DOS nie zapewnia ochrony pamięci.

MS-Windows 3.x
Windows 3.x są nakładką na MS-DOS częściowo modyfikującą jego zachowanie,
m in. zarządzanie pamięcią. Przede wszystkim znika ograniczenie wielkości
pamięci procesu do 640kB. MS-Windows również nie zapewniają pamięci.
Obszary pamięci można rezerwować jako:


Fixed - Obszar ten cały czas dostępny jest pod adresami przydzielonymi
mu przy rezerwacji. W obszarach tej klasy lokuje się kod, dane statyczne
i stos procesu.


Movable - Aby odwoływać się do adresów w tym obszarze, należy go zablokować.
System operacyjny gwarantuje, że po odblokowaniu zawartość obszaru nie
będzie zniszczona, jednak nie gwarantuje, że po powtórnym zablokowaniu
znajdować się będzie w tym samym miejscu pamięci. W związku z tym, adresy
zmiennych zawartych w tym obszarze, po jego odblokowaniu tracą ważność.
Obszary tej klasy wykorzystuje się na współdzielone dane i pewne mniej
potrzebne zmienne dynamiczne.


Discardable - Aby odwoływać się do adresów w tym obszarze, należy go zablokować.
Po odblokowaniu obszaru może on zostać zniszczony. W związku z tym, adresy
zmiennych zawartych w tym obszarze, po jego odblokowaniu tracą ważność.
Obszary tej klasy wykorzystuje się na pewne mniej potrzebne zmienne dynamiczne.

MS-Windows zapewnia dwa mechanizmy gospodarowania pamięcią:


Konsolidacja. W przypadku gdy dla nowotworzonego procesu, lub procesu,
który zarządał pamięci brak miejsca, odblokowane obszary klasy discardable
są niszczone, a odblokowane obszary klasy movable przesuwane tak by utworzyć
spójny obszar mogący zaspokoić żądanie.



Wymiana. Jeżeli powyższe operacje nie pozwalają uzyskać spójnego obszaru
pamięci odpowiedniej wielkości, jeden lub więcej z obszarów klasy fixed,
lub zablokowanych obszarów klas movable i discardable należących do innych
procesów trafia na dysk do pliku wymiany. Zmiana kontekstu (uzyskanie procesora
przez inny proces) powoduje że obszary pamięci danego procesu umieszczone
w pliku wymiany są sprowadzane do pamięci operacyjnej, a obszary należące
do innych procesów, pokrywające się w pamięci operacyjnej z nimi są konsolidowane
lub trafają do pliku wymiany.

Jak widać na rysunku 3.2 pomimo zastosowania konsolidacji pamięci, jest
ona wciąż pofragmentowana, choć największy spójny obszar znacząco wzrósł.
Fragmentacja pamięci powoduje, że żądania przydziału pamięci, domagające
się mniej pamięci niż jest w sumie wolne, ale więcej niż zawiera największy
spójny obszar mogą nie zostać spełnione.
Z pomocą przychodzi wymiana (mechanizm zapewniany przez system operacyjny)
i nakładkowanie (mechanizm zapewniany przez programistę lub jego kompilator).
Polegają one na czasowym usuwaniu pewnych obszarów pamięci na dysk do specjalnie
utworzonego pliku wymiany. Mechanizmem nakładkowania nie będziemy się tu
zajmować, jest on zbliżony do mechanizmu wymiany, a dotyczy głównie wymiany
zestawów podprogramów.
Wadą mechanizmu wymiany jest to, że pamięć jest usuwana na dysk wielkimi
blokami, a w razie przełączenia kontekstu cała pamięć procesu musi być
przeniesiona od razu z pliku wymiany do pamięci operacyjnej. Nie można
również zarezerwować obszaru większego niż dostępna pamięć operacyjna.

Mechanizm pamięci wirtualnej


Zalety i wady
Mechanizm pamięci wirtualnej nie posiada wad przedstawionych w poprzednim
paragrafie. Jego cechy to:


Powstanie prywatnych przestrzeni adresowych dla każdego procesu. Procesy
nie widzą nawzajem swoich przestrzeni adresowych.


Niewidoczny dla procesu podział pamięci na niewielkie (rzędu 1kB) obszary
pamięci podlegające wymianie zwane stronami.


Praktyczne nieistnienie problemu fragmentacji pamięci.


Możliwośc przechowywania w pamięci operacyjnej w trakcie wykonywania procesu
jedynie najczęściej ostatnio używanych stron. Długo niewykorzystywane strony
trafiają na dysk do pliku wymiany. Przy przełączaniu kontekstu nie ma potrzeby
ładować całej przestrzeni adresowej do pamięci operacyjnej, wystarczy strona
z komórką zawierającą następną instrukcję programu, oraz strona z wierzchem
stosu.


Proces ma iluzję posiadania przez maszynę znacznie większej ilości pamięci
operacyjnej niż ma ona w rzeczywistości, w szczególności można tworzyć
zmienne o rozmiarze przekraczającym rozmiar pamięci operacyjnej.


Możliwość poddania ochronie obszarów przestrzeni adresowej procesu, w szczególności
obszarów systemowych, obszaru kodu i pamięci współdzielonej.


Możliwość spójnego implementowania pamięci wirtualnej, pamięci współdzielonej,
mapowania pliku na pamięć operacyjną i buforowania operacji dyskowych.

Wadami mechanizmu pamięci wirtualnej są


Narzut na pamięć związany z przechowywaniem dodatkowych struktur danych
t.j. tablic stron.


Narzut na wydajność i złożoność procesora związany z wyliczaniem adresów
fizycznych z adresów wirtualnych.


Narzut na wydajność systemu związany z koniecznością wczytania do procesora
częsci tablicy stron nowego procesu przy przełączaniu kontekstu.


Narzut na wydajność systemu związany z operacjami dyskowymi wymiany stron.
Trzeba tu jednak zaznaczyć, że dobre algorytmy wymiany stron minimalizują
ten narzut.



Zasada działania
Najistotniejszym elementem mechanzmu jest rozróżnienie między adresem logicznym
a fizycznym komórki pamięci i sposób odwzorowania adresu logicznego na
fizyczny.
Adresem fizycznym komórki nazywamy adres, jaki wysyła na magistralę
adresową procesor, aby odwołać się do tej komórki. Każda komórka pamięci
operacyjnej ma swój niezmienny adres fizyczny. Każdy adres fizyczny odnosi
się zawsze do tej samej komórki pamięci lub jest zawsze błędny.
Adresem logicznym (lub wirtualnym) nazywamy adres jakim posługuje się
program, aby odwołać się do zmiennej lub instrukcji. Adres logiczny może
odnosić się zarówno do komórki pamięci operacyjnej jak i słowa maszynowego
zapisanego na dysku. Przypisanie adresu logicznego do konkretnej komórki
pamięci, czy konkretnego miejsca na dysku jest inne dla każdego procesu
i może się zmieniać w trakcie jego życia.
Pamięć operacyjna dzielona jest na ramki, to jest spójne obszary o
stałym romiarze zwanym wielkością ramki. Przestrzeń adresów wirtualnych
dzielona jest na strony, to jest spójne obszary o stałym rozmiarze zwnym
wielkością strony. Wielkość strony równa się wielkości ramki i jest wielokrotnością
rozmiaru sektora dyskowego. Wielkość strony jest rzędu 1kB, i tak, w systemie
VMS wynosi ona 512B, w Linuksie - 1kB a w Windows NT - 4kB.
Analogicznie do pamięci operacyjnej, można przyjąć, że plik wymiany
dzieli się również na ramki. Strona pamięci wirtualnej może znajdować się
w jednej z ramek pamięci operacyjnej, jednej z ramek pliku wymiany lub
być stroną niezarezerwowaną (błędną). Odwzorowania stron pamięci wirtualnej
w ramki pamięci operacyjnej lub ramki pliku wymiany dokonuje procesor za
każdym razem, gdy oblicza adres fizyczny z adresu wirtualnego (celem pobrania
instrukcji, lub odwołania się do zmiennej). Do odwzorowywania stron w ramki
służą mu tablice stron wirtualnych.  Szczegóły tłumaczenia adresu
logicznego na fizyczny w prypadku, gdy strona znajduje się w pewnej ramce
pamięci operacyjnej ilustruje rys. 3.3.

Adres logiczny składa się z dwóch cęści: numery strony i przesunięcia
na stronie. Numer strony służy jako indeks do tablicy stron wirtualnych.
W tablicy tej odnajdywana jaest pozycja odpowiadająca dnej stronie. Na
podstawie atrybutów procesor ustala, czy strona znajduje się w pamięci
operacyjnej i jeśli tak, pobiera numer ramki po czym łączy go z przesunięciem
na stronie otrzymując adres fizyczny, który może być wysłany na magistralę
adresową.
Jeżeli atrybut dostępności strony wskazuje, że znajduje się ona w pamięci
wymiany, następuje tzw. ``page fault'' - wyjątek pamięci wirtualnej. Procesor
przerywa proces (wątek), który odwołał się do nieobecnej strony i przenosi
go w stan uśpiony. Jednocześnie podejmowane są działania mające na celu
sprowadzenie strony do pamięci t.j. wyszukiwana jest wolna ramka. Jeśli
wolnej ramki brak, jedna z ramek zajętych zapisywana jest na dysk i zwalniana.
Uzyskana ramka pamięci operacyjnej zapełniana jest zawartością przywracanej
strony przechowywaną w pliku wymiany.
Tablice stron mogą rezydować tak jak to pokazano na rysunku w specjalnych
obszarach pamięci, które są znane procesorowi przez ich adres fizyczny
(a nie logiczny) lub też mogą być częściowo przechowywane w podręcznej
pamięci asocjacyjnej procesora. Wiele systemów operacyjnych dopuszcza by
część tabeli stron mogła być przenoszona do pliku wymiany.
Duża część mechanizmu pamięci wirtualnej musi być realizowana sprzętowo
przez procesor. System operacyjny dochodzi do głosu gdy następuje page
fault i trzeba sprowadzić stronę do pamięci, usuwając być może inną stronę
oraz dokonać przełączenia kontekstu. Mechanizm ten może zatem działać jedynie
w systemach operacyjnych działających na procesorach wspierających go,
takich jak np. Intel i386 i nowsze procesory Intela, procesory Alpha, nowsze
procesory Motorolli itd.

Izolacja procesów i ochrona pamięci.
Aby zapewnić każdemu procesowi prywatną przestrzeń adresową, dostaje on
własną tablicę stron wirtualnych. W związku z tym tablica ta jest elementem
kontekstu procesu. Przełączenie kontekstu wymaga wczytania do procesora
tablicy stron nowego procesu (a przynajmniej jej części).
Atrybutem strony może być uprawnienie procesu do posługiwania się tą
stroną:


Uprawnienie do odczytu i zapisu (read/wite). To uprawnienie otrzymują strony
obszarów danych i stosu programu.


Uprawnienie do odczytu (read only). To uprawnienie nadaje się m.in. stronom
zawierającym kod programu. Można dzięki temu współdzielić te strony między
procesami wykonującymi ten sam program bez obawy, że jeden proces zmodyfikuje
kod programu i tym samym wpłynie katastrofalnie na przebieg działania drugiego
procesu.


Uprawnienie zabraniające wszelkich operacji (no access). Tym atrybutem
oznacza się strony przechowujące kod i dane jądra systemu operacyjnego
oraz strony nie zarezerwowane dotąd przez proces.

Niektóre systemy operacyjne wyróżniają bardziej złożony system uprawnień
np. copy on write i execute only, pod warunkiem, że procesor wspiera takie
upranienia.
Proces, diałając w trybie użytkownika, nie ma możliwości bezpośredniej
zmiany zawartości tablicy stron. Może on zlecić systemowi operacyjnemu
rezerwację nowych stron (np. na zmienne dynamiczne) lub zwolnienie tych
które przestał używać. Odbywa się to przez wywołanie odpowiednich podprogramów
jądra (działających w trybie jądra).


Poprzedni | Spis treści
| Następny  | Zadania