Zarządzanie pamięcią

W wyniku planowania przydziału procesora - wydajność rośnie, kilka procesów współbieżnie, jednocześnie muszą być w pamięci operacyjnej muszą dzielić pamięć. Założenie, że pamięć fizyczna musi pomieścić cały proces przed wykonaniem.

Pamięć jest wielką tablicą poadresowanych słów (bajtów), współpraca z nią ciąg operacji czytania lub pisania pod konkretne adresy (nieważne, jak są one wyliczane).

Ładowanie dynamiczne - podprogram nie jest ładowany, dopóki nie jest wywoływany, wszystkie podprogramy w postaci przemieszczalnej na dysku. Do pamięci operacyjnej program główny, gdy potrzebny jakiś podprogram, to wywołujący najpierw sprawdza, czy jest on w pamięci, jeśli go nie ma, to uruchamiany jest loader i linker (wczytają odp. podprogram, uaktualni tablice opisujące), następnie sterowanie do tego kawałka programu. Zaleta: nigdy nie załaduje się zbędny kawałek (np. duże moduły obsługi błędów)

Łączenie (konsolidacja) dynamiczne - podobnie jak ładowanie dynamiczne, ale opóźnia się dołączanie modułów bibliotecznych, zwłaszcza systemowych (UNIX, Windows). Jeśli tak nie jest, to wszystkie programy muszą mieć własne kopie bibliotek używanych funkcji. W wersji dwójkowej programu w miejscach odwołań do podprogramów są zakładki (mały fragment kodu, jak wybrać odpowiedni kawałek biblioteki), wykonanie zakładki zastąpienie jej przez adres podprogramu bibliotecznego i wykonanie go (przy następnym wywołaniu tegoż już jest w pamięci), wszystkie procesy korzystają z jednej kopii.

Logiczna i fizyczna przestrzeń adresowa - adres wytworzony przez procesor jest logiczny (wirtualny), zaś adres oglądany przez jednostkę pamięci fizyczny, odwzorowanie robi jednostka zarządzania pamięcią.

Przydział wielu obszarów

Gdy wiele procesów, najprostszy schemat przydziału: podział pamięci na założoną liczbę równych obszarów, każdy dla jednego procesu. Gdy proces się kończy, zwalnia ten obszar i można załadować tam inny schemat już nie stosowany.

Schemat podstawowy: na początku cała pamięć na procesy wolna: dziura. Gdy przybywa proces, to szuka mu się miejsca, gdy się uda, to przydziela się to miejsce dla niego, reszta zostaje wolna. System pamięta o przydziałach. Problemy: istnieje zbiór dziur o różnych wymiarach, rozproszonych po całej pamięci. Gdy przychodzi proces, to trzeba mu dać pamięć: przegląd dziur. Gdy proces kończy, zwalnia pamięć, dziury przylegające do siebie się łączy, sprawdzenie, czy jakiś proces nie czeka na przydział pamięci i czy ta nowa dziura ew. mu wystarczy.

Dynamiczny przydział pamięci:

• pierwsza pasująca - przegląd od miejsca, gdzie się skończyło ostatnio, najszybsza metoda

• najlepiej pasująca - najmniejsza z dostatecznie dużych, przeszukanie całej listy

• najgorzej pasująca - największa dziura, też przegląd całej listy (chyba, że posortowana)

Zewnętrzna fragmentacja - przy ładowaniu i usuwaniu procesów przestrzeń wolnej pamięci dzieli się na kawałki: suma wolnych obszarów wystarcza na spełnienie zamówienia, ale nie są w odpowiednio dużym kawałku: pamięć podzielona na dużo małych dziur może „ginąć” 50% z powodu fragmentacji.

Inny problem: trzeba 18462B, jest dziura 18464B, zostaje 2B, ale przechowywanie informacji o tych 2B zajmuje znacznie więcej miejsca! przyłączanie takich małych kawałków do większych zamówień wewnętrzna fragmentacja: efekt pozostawienia niewykorzystanego fragmentu pamięci wewnątrz przydzielonego obszaru.

Stronicowanie

Schemat obszarów o różnych wielkościach niesie ze sobą fragmentację: dostępna pamięć nie jest ciągła, a proces musi dostać pamięć z ciągłym kawałku upakowanie. Stronicowanie pozwala aby pamięć procesu była nieciągła można przydzielać wolne kawałki. Omija się też problem dopasowywania kawałków pamięci o zmiennych rozmiarach. Stosuje się też ten schemat do pamięci pomocniczej (upakowywanie w niej jest bardzo kosztowne!). Powszechnie stosowany schemat.

Sprzęt - pamięć fizyczna jest podzielona na kawałki o stałej długości ramki. Pamięć logiczna podzielona na strony o tej samej długości. Strony procesu są wprowadzane w dowolne ramki (z pamięci pomocniczej, gdzie są bloki o takiej samej długości). Każdy adres dzieli się na: numer strony (indeks w tablicy stron) i odległość na stronie.

Strony dzielone - strony z tzw. czystym kodem, który nie modyfikuje sam siebie, tylko do odczytu. Możliwe łatwe współdzielenie kodu przez wiele procesów.

Segmentacja

Oddzielenie sposobu widzenia pamięci przez użytkownika od rzeczywistości fizycznej. Nie widzi jako jednowymiarowej liniowej tablicy bajtów. Tylko wg struktur danych i funkcji.

Pamięć wirtualna

Umożliwia wykonywanie procesów pomimo, że nie są one w całości w pamięci operacyjnej programu mogą być większe niż pamięć fizyczna, pamięć wirtualna pozwala tworzyć abstrakcyjną pamięć główną jako wielka, jednorodna tablica łatwiej programować, ale implementacja pamięci wirtualnej nie jest prosta, może znacznie obniżyć wydajność systemu!

Po co? W rzeczywistości cały program nie jest potrzebny, bo:

• Często są tam fragmenty rzadko używane: do obsługi błędów

• Struktury danych często są z nieużywanym zapasem

• Pewne możliwości są rzadko wykonywane: np. w edytorze zamiana wszystkich znaków

Korzyści z pamięci wirtualnej:

• Program nie jest ograniczony wielkością dostępnej pamięci fizycznej pisanie w bardzo dużej przestrzeni wirtualnej uproszczenie programowania, nie trzeba martwić się o brak pamięci zanik nakładek

• Każdy program użytkownika może zajmować mniejszy obszar pamięci fizycznej można więcej na raz wykonywać procesów lepsze wykorzystanie procesora i przepustowość

• Maleje liczba operacji we/wy koniecznych do załadowania lub wymiany procesów użytkowych w pamięci każdy może szybciej działać

• Pamięć wirtualna pozwala odseparować pamięć logiczną użytkownika od fizycznej

• Posługiwanie się wielką pamięcią nawet gdy w rzeczywistości jest bardzo mała.

Stronicowanie na żądanie

Podobne do stronicowania z wymianą: procesy rezydują w pamięci pomocniczej (dysk), ten, który trzeba wykonać wprowadza się do RAM, ale zamiast całość, to „leniwa” wymiana („lazy” swapper): nie dokonuje się wymiany strony w pamięci, dopóki nie jest to konieczne (wymiana jest złym określeniem, bo wymienia się całe procesy, a tu jest program zmieniania stron pager); program zmieniania stron zgaduje, które strony będą potrzebne zamiast całości wczytuje tylko te (unika się czytania stron, które nigdy nie będą potrzebne krócej, mniej pamięci. Ale potrzebny wówczas odp. sprzęt: każda pozycja w tablicy stron ma dodatkowy bit poprawności odniesienia (poprawny - dana strona jest w pamięci, nie - na dysku).

Oznaczenie strony jako niepoprawnej gdy proces się do niej nie odwołuje, to nic się nie dzieje (jakby się udawało dobrze zgadywać...); gdy spróbuje użyć strony nieobecnej, to powstaje pułapka błąd strony: awaryjne przerwanie w systemie operacyjnym:

1. Sprawdzamy wewnętrzną tablicę (w bloku kontrolnym procesu): czy odwołanie do pamięci dozwolone, czy nie

2. Jeśli niedozwolone, to kończymy proces, jeśli zaś dozwolone tylko zabrakło właściwej strony w pamięci, to sprowadzamy tę stronę

3. Znajdujemy wolną ramkę (z listy wolnych ramek)

4. Zamówienie na przeczytanie z dysku potrzebnej strony do tej ramki

5. Po przeczytaniu modyfikujemy tablice (wewnętrzną procesu i stron) strona jest w pamięci

6. Wznawiamy wykonanie instrukcji, tak jakby strona była zawsze w pamięci dzięki przechowaniu stanu przerwanego procesu dokładnie w tym samym miejscu

Skrajny przypadek: rozpocząć wykonanie procesu bez żadnej strony w pamięci: natychmiast przerwanie z powodu braku pierwszej instrukcji, potem z dalszymi przerwami, aż wszystkie brakujące strony trafią do pamięci, dalej już bez zakłóceń tzw. czyste stronicowanie na żądanie (nigdy nie sprowadza się strony bez zapotrzebowania na nią).

Teoretycznie: nowa strona na każdą instrukcję błąd strony ciągle obniżenie wydajności systemu ale to mało prawdopodobne, bo lokalność odniesień.

Sprzęt do stronicowania na żądanie (jak do stronicowania i wymiany):

• Tablica stron: jest wektor bitów poprawności odniesień (lub specjalne układy bitów ochrony)

• Pamięć pomocnicza: dysk

• Odpowiednie oprogramowanie

• Dodatkowe ograniczenia na sprzęt: możliwość wznawiania rozkazu po błędzie strony: ponowne pobranie rozkazu do wykonania / ponownie pobrać rozkaz, zdekodować i znowu pobrać argument / gorzej, gdy rozkaz zmienia kilka komórek: na granicy stron mikroprogram do obliczania końców wówczas błąd przed zmienianiem, albo rejestry pomocnicze / specjalne tryby adresowania (zmniejszanie rejestru przed rozkazem) specjalny rejestr stanu.

Stronicowanie jest między procesorem a pamięcią operacyjną, powinno być całkowicie przezroczyste dla procesów użytkownika.

Sprawność stronicowania na żądanie: błąd strony co trzeba wówczas zrobić:

1. Pułapka w systemie operacyjnym

2. Przechowanie rejestrów i stanu procesu

3. Określenie, że przerwanie z powodu błędu strony

4. Sprawdzenie, czy odniesienie do strony było poprawne i określenie położenia strony na dysku

5. Wydanie polecenia czytania z dysku do wolnej ramki:

1. Czekanie w kolejce do dysku

2. Czekanie przez czas szukania informacji na urządzeniu

3. Rozpoczęcie przesyłania strony

6. Podczas czekania przydzielenie procesora innemu procesowi

7. Otrzymanie przerwania z dysku o końcu we/wy

8. Przechowanie rejestrów i stanu tego innego procesu

9. Określenie, czy przerwanie z dysku

10. Skorygowanie zawartości tablicy stron i innych tablic że strona w pamięci

11. Czekanie na powtórny przydział procesora

12. Odtworzenie rejestrów, stanu procesu i nowej tablicy stron, wznowienie procesu

Główne zadania wpływające na czas obsługi błędu strony:

• Obsługa przerwania

• Czytanie strony

• Wznowienie procesu

Efektywny czas dostępu (do pamięci stronicowanej na żądanie) jest wprost proporcjonalny do częstości błędów strony utrzymywanie częstości tego na niskim poziomie jest bardzo ważne, bo rośnie efektywny czas dostępu drastyczne spowolnienie procesu.

Zastępowanie stron

Dotychczas częstość występowania błędów nieistotna, bo każda strona co najwyżej jeden błąd (wtedy trafi do pamięci i potem już tam jest). Ale w rzeczywistości jest trochę inaczej!

Proces 10stronicowy korzysta tylko z 5 stron nieefektywne podwyższyć stopień wieloprogramowości: jeśli mamy 40 ramek, to zamiast 4 procesów po 10 stron można 8 procesów po 5 stron (efektywniej), ale może dojść do nadprzydziału pamięci: 6 procesów po 10 ramek faktycznie używających po 5 każdy zwiększamy wieloprogramowość, zatrudnienie procesora i przepustowość (jeszcze 10 zapasu); ale może być tak, że każdy z tych procesów nagle zechce po całe swoje 10ramek zapotrzebowanie na 60 a jest tylko 40! Szansa na coś takiego rośnie przy wzroście wieloprogramowości, gdy średnie wykorzystanie pamięci zbliży się do fizycznej. Objawy nadprzydziału pamięci: pojawia się błąd strony, sprzęt wysyła przerwanie do systemu, ten sprawdza wewnętrzne tablice (czy dopuszczalna operacja procesu), określa gdzie na dysku potrzebna strona, ale na liście wolnych ramek nie ma nic! Cała pamięć zajęta.

Modyfikacje procedury obsługi błędów strony:

1. odnalezienie potrzebnej strony na dysku

2. odnalezienie wolnej ramki

1. jeśli jest taka, to użycie jej

2. gdy nie ma, to wytypowanie ramki-ofiary

3. zapis ramki-ofiary na dysk, modyfikacje tablic

3. do świeżo zwolnionej ramki wpis odpowiedniej strony, modyfikacje tablic

4. wznowienie procesu

Gdy nie ma wolnej ramki trzeba 2 razy przesyłać stronę (na dysk zeskładować i wczytać nową) wydłużenie efektywnego czasu dostępu. Zmniejszenie go poprzez bit modyfikacji: sprzętowo ustawiany 1 przy zapisie dowolnej zmiany na stronie. Przy wyborze strony-ofiary sprawdza się ten bit, gdy 1 to trzeba ją zapisać na dysk, gdy zaś 0 to zawartość się nie zmieniła od czasu przeczytania do pamięci jeśli jest kopia na dysku, to wystarczy. Ta sama technika przy stronach tylko do czytania nie wolno zmieniać, można się ich taniej pozbyć. Do rozwiązania pozostają ważne algorytmy (mocno decydują o efektywności): przydziału ramek (ile ramek dla każdego procesu na wstępie) oraz zastępowania stron.

Algorytmy zastępowania stron - zależy nam na najmniejszej częstości błędów stron, są różne.

Algorytm FIFO: z każdą następną stroną skojarzony czas jej wprowadzenia gdy trzeba zastąpić wybiera najstarszą (nie trzeba pamiętać czasów, wystarczy zrobić kolejkę FIFO: do zastąpienia z czoła, zastępująca na koniec)

Algorytm drugiej szansy - wg FIFO, po wybraniu strony sprawdza się dod. jej bit odniesienia: 0 to zastąpiona, 1 to ma drugą szansę (na pobyt w pamięci), a wybiera się następną z kolejki: bit odniesienia ustawiany na 0, czas jej pobrania = czas bieżący; nie będzie uwzględniona przy zastępowaniu, dopóki innych nie zastąpi się (albo też dostaną drugą szansę), jeśli strona eksploatowana wystarczająco często, to nigdy nie będzie zastąpiona. Realizacja przez kolejkę cykliczną: ofiarę pokazuje wskaźnik, przesuwa się zerując bity, aż natrafi na 0 (może przejść całą kolejkę i wyzerować wszystko --> FIFO)

Szamotanie

Zawsze jest pewna liczba stron aktywnie używanych przez dany proces, gdy za mało, to bardzo szybko błąd strony, wtedy któraś musi być zastąpiona, ale ponieważ jest często używana, to bardzo szybko potrzebna w procesie bardzo szybko kolejne błędy braku strony: wymiana i znów brakuje odpowiedniej i sprowadzenie jej z powrotem. Proces szamoce się, gdy więcej czasu spędza na stronicowanie niż na wykonywanie.

Przyczyna szamotania: Gdy wykorzystanie procesora za małe, to system uruchamia następny proces, strony zastępowane wg globalnego algorytmu bez brania pod uwagę, czyja to była strona. Proces zaczyna potrzebować więcej ramek błędy braku strony zabiera innym procesom, one używają dysku do zrzutu stron ustawiają się w kolejce do urządzenia opróżnia się kolejka procesów gotowych (bo wiele procesów czeka w kolejce na zrzut pamięci) zmniejsza się wykorzystanie procesora planista uruchamia następne procesy, które potrzebują ramek zabierają innym procesom większa kolejka do zrzutu, błędy ... następny ..

wykorzystanie procesora jako funkcja wieloprogramowości: najpierw rośnie, ale potem gwałtownie maleje na skutek szamotania.

Szamotanie można ograniczyć za pomocą algorytmu zastępowania:

• lokalnego - gdy jakiś proces zaczyna się szamotać, to nie wolno mu kraść ramek innego

• priorytetowego - ważniejszy zabiera mniej ważnym (te najlepiej całe zrzucić)

Ale gdy któryś się szamoce, to większość czasu spędza w kolejce do urządzenia stronicującego efektywny czas dostępu wzrasta dla wszystkich.

Zapobieganie szamotaniu: dać procesowi tyle ramek, ile potrzebuje. Ale ile on potrzebuje?!

Prościej zapobiegać szamotaniu poprzez - sterowanie częstością błędów braku strony. Bo szamotanie = dużo błędów braku strony. Za dużo = brakuje procesowi ramek, za mała = ma za dużo. Można określić górną i dolną granicę pożądanego poziomu błędów braku strony i odpowiednio reagować (dawać ramkę lub zabierać). Można wstrzymywać proces, aby obdzielić inne procesy.

Przydział lokalny / globalny - jeden proces nie może / może dostać ramkę innego procesu. Przy globalnym czas wykonania procesu może drastycznie się zmieniać, ale jest lepsza przepustowość poprzez lepszą gospodarkę pamięcią.

Stronicowanie wstępne - na początku działania procesu naturalnie dużo błędów braku strony, bo trzeba uzyskać początkową strefę procesu, gdy wznawia się usunięty proces, to wszystkie jego strony po kolei trzeba ściągać z dysku po błędzie. Aby zapobiec dużemu stronicowaniu we wstępnej fazie stronicowanie wstępne jednorazowe wprowadzenie stron, o których wiadomo, że będą potrzebne.

1

1

---