SYSTEMY OPERACYJNE

Wykład 8

Zarządzanie pamięcią

• Podstawy
• Logiczna a fizyczna przestrzeń adresowa
• Wymiana
• Przydział ciągły
• Stronicowanie
• Segmentacja
• Segmentacja ze stronicowaniem

• Podstawy

• program - binarny wykonywalny plik musi być wprowadzony do pamięci operacyjnej i rozpatrywany jako proces
• zbiór procesów czekających na dysku na wprowadzenie do pamięci w celu wykonania tworzy kolejkę wejściową
• zanim program zostanie wykonany, przechodzi on przez kilka faz

rys.8.1 Wieloetapowe przetwarzanie programu użytkownika

 

• Wiązanie adresów

• podczas faz przetwarzania programu, reprezentacja adresów pamięci komputera może ulegać zmianom
  • w programie źródłowym adresy są wyrażone w sposób symboliczny, (np. LICZNIK)
  • kompilator na ogół wiąże te adresy z adresami względnymi (np. "14 bajtów licząc od początku danego modułu")
  • konsolidator lub program ładujący powiąże dalej te adresy względne z adresami bezwzględnymi (np. 74014)
  • powiązanie rozkazów i danych z adresami pamięci może w zasadzie zostać wykonane w dowolnym z poniższych kroków.
    • czas kompilacji: jeśli podczas kompilacji jest znane miejsce, w którym proces będzie wykonywany, to można wygenerować kod bezwzględny; kod trzeba skompilować od nowa, gdy w późniejszym czasie ulegnie zmianie adres początkowy programu
    • czas ładowania: jeśli podczas kompilacji nie wiadomo, gdzie będzie umieszczony proces, to kompilator wytworzy kod przemieszczalny; ostateczne wiązanie jest opóźniane do czasu ładowania
    • czas wykonania: jeśli proces może ulegać przemieszczeniom w pamięci podczas swojego wykonania, to trzeba zaczekać z wiązaniem adresów aż do czasu wykonywania; wymaga to specjalnego sprzętu

• Ładowanie dynamiczne

• podprogram nie jest wprowadzany do pamięci dopóty, dopóki nie zostanie wywołany
• umożliwia to lepsze wykorzystanie pamięci; podprogram nieużywany nigdy nie będzie załadowany
• schemat jest szczególnie przydatny wtedy, kiedy okazjonalnie trzeba wykonywać wielkie fragmenty kodu
• nie jest wymagane specjalne wsparcie ze strony SO; to użytkownicy są odpowiedzialni za takie zaprojektowanie programów, aby mogły korzystać z metody

• Konsolidacja dynamiczna

• konsolidacja jest opóźniana do czasu wykonania programu
• w obrazie binarnym, w miejscu odwołania bibliotecznego znajduje się tylko namiastka procedury, wskazująca jak odnaleźć odpowiedni podprogram biblioteki
• namiastka procedury wprowadza na swoje miejsca adres potrzebny podprogramowi i powoduje jego wykonanie
• SO musi sprawdzić, czy potrzebny podprogram znajduje się w obszarze pamięci innych procesów

• Nakładki

• trzymaj w pamięci tylko te rozkazy i dane, które są stale potrzebne
• ta technika może być stosowana gdy proces jest większy aniżeli ilość przydzielonej mu pamięci
• np. mamy dwuprzebiegowy asembler:
  • w pierwszym przebiegu konstruuje on tablicę symboli
  • w drugim, generuje kod maszynowy
• taki asembler można podzielić na kod przebiegu 1, kod przebiegu 2, tablicę symboli i wspólne podprogramy
• do załadowania wszystkiego, potrzeba by było 200kB pamięci, a mamy tylko 150kB

Rys. 8.2 Nakładki dwuprzebiegowego asemblera

• definiujemy 2 nakładki:
  • A - złożoną z tablicy symboli, wspólnych podprogramów i kodu przebiegu 1
  • B - złożoną z tablicy symboli, wspólnych podprogramów i kodu przebiegu 2
• dodajmy moduł obsługi nakładek i rozpoczynamy od wykonania nakładki A
• nakładki nie wymagają specjalnego wsparcia SO, są wykonane przez użytkownika

• Logiczna i fizyczna przestrzeń adresowa

  • adres wytworzony przez procesor, to adres logiczny (często określany jako adres wirtualny)

  • odwzorowanie adresów wirtualnych na fizyczne, odbywające się podczas działania programu jest dokonywane przez jednostkę zarządzania pamięcią

  • proste urządzenie odwzorowujące jest uogólnieniem schematu rejestru bazowego

  

  Rys. 8.3 Przemieszczanie dynamiczne z użyciem rejestru przemieszczenia

  • koncepcja logicznej przestrzeni adresowej powiązanej z odrębną, fizyczną przestrzenią adresów jest podstawą właściwego zarządzania pamięcią

• Wymiana

Rys. 8.4 Wymiana dwu procesów z użyciem dysku jako pamięci pomocniczej

• proces może być tymczasowo wymieniany, tj. odsyłany z pamięci operacyjnej do pamięci pomocniczej

• pamięć pomocnicza - pojemny, szybki dysk

• wyłączanie, włączanie - wariant wymiany stosowany w algorytmach planowania priorytetowego; gdy proces o wyższym priorytecie kończy działanie, to proces o niższym priorytecie może być sprowadzony do pamięci

• główną częścią czasu wymiany jest czas przesyłania; jest on proporcjonalny do ilości wymienianej pamięci

• Przydział ciągły

Rys. 8.5 Podział pamięci

• Pamięć główna zwykle jest podzielona na:

  • rezydujący SO; trzymany zwykle w dolnej pamięci wraz z wektorem przerwań

  • procesy użytkownika trzymane w pamięci górnej

• Przydział pojedynczego obszaru

Rys. 8.6 Zastosowanie rejestrów sprzętowych: przemieszczenia i granicznego

• potrzeba ochrony kodu i danych systemu operacyjnego i procesów użytkownika

• ochronę pamięci można osiągnąć przez użycie rejestru przemieszczenia w połączeniu z rejestrem granicznym

• rejestr przemieszczenia zawiera wartość najmniejszego adresu fizycznego; rejestr graniczny zawiera zakres adresów logicznych

• rejestr przemieszczenia pozwala skutecznie zmieniać na bieżąco rozmiar SO w pamięci

• Przydzielanie wielu obszarów

Rys.8.7 Przykład planowania

• jednym z najprostszych schematów, jest podział obszaru pamięci na pewną liczbę obszarów o stałym rozmiarze

• załóżmy np., że mamy dostępną pamięć oraz kolejkę procesów jak na rysunku

• mając kolejkę wejściową oraz planowanie zadań metodą FCFS, możemy przydzielić procesom P₁, P₂, i P₃ pamięć, tworząc mapę pamięci (rysunek 8.8 (a) )

Rys. 8.8 Przydzielanie pamięci i planowanie długoterminowe

• załóżmy, że mamy rotacyjny algorytm planowania z kwantem wynoszącym 1

  • P₂ zakończy się w chwili 14 zwalniając pamięć (b)

  • następny proces P₄ jest wybrany (c)

  • P₁ kończy się w chwili 28 (d)

  • P₅ otrzymuje pamięć (e)

• dziura - blok dostępnej pamięci; dziury o różnych rozmiarach w pamięci

• SO przechowuje informacje o:

  • alokowanych obszarach

  • wolnych partycjach (dziurach)

• Dynamiczny przydział pamięci

• jeśli dziura jest zbyt wielka, to dzieli się ją na dwie

• przyległe dziury można łączyć

• jak na podstawie listy wolnych dziur spełnić zamówienie na obszar o rozmiarze n ? Najbardziej znane strategie wyboru to:

  • pierwsze dopasowanie: przydziela się pierwszą dziurę o wystarczającej wielkości

  • najlepsze dopasowanie: przydziela się najmniejszą z dostatecznie dużych dziur; ta strategia zapewnia najmniejsze pozostałości po przydziale

  • najgorsze dopasowanie: przydziela się największą dziurę; taka strategia pozostawia po sobie największą dziurę

• pierwsze dwie strategie są lepsze jeśli chodzi o czas i zużycie pamięci

• Fragmentacja

• zewnętrzna fragmentacja - suma wolnych obszarów pamięci wystarcza na spełnienie zamówienia, ale nie tworzą one spójnego obszaru

• wewnętrzna fragmentacja - przydzielona pamięć może być trochę większa niż wymagana wielkość pamięci; ta różnica stanowi wewnętrzną fragmentację, czyli bezużyteczny kawałek pamięci wewnątrz przydzielonego obszaru

• rozwiązanie problemu przez upakowanie:

  • poprzemieszczanie zawartości pamięci, aby cała wolna pamięć znalazła się w jednym wielkim bloku

  • upakowanie jest możliwe tylko przy dynamicznym wiązaniu adresów wykonywanych podczas działania procesu

• Stronicowanie

• logiczna przestrzeń adresowa może być nieciągła: procesowi można przydzielić dowolne dostępne miejsce w pamięci
• stronicowanie - jedno ze sposobów implementacji takiego rozwiązania
• fizyczną pamięć dzieli się na bloki o stałej długości zwane ramkami (o rozmiarach będących potęgą 2, między 512 a 8192 bajtów)
• pamięć logiczna jest również podzielona na bloki takiego samego rozmiaru zwane stronicami

 

Rys. 8.9 Sprzęt stronicujący

• aby wykonać program posiadający n stronic, trzeba znaleźć n wolnych ramek i załadować program
• każdy adres generowany przez procesor dzieli się na 2 części: numer strony "s" i odległość na stronie "o"
• numer strony jest używany jako indeks w tablicy stron; tablica zawiera adresy bazowe wszystkich stron w pamięci

 

Rys. 8.10. Model stronicowania pamięci logicznej i fizycznej

• stronicowanie eliminuje zewnętrzną fragmentację; może jednak wystąpić fragmentacja wewnętrzna (ostatnia przydzielona ramka nie będzie całkowicie wypełniona)
• odpowiedniejsze byłyby małe rozmiary strony - wiążą się z tym jednak dodatkowe koszty spowodowane koniecznością przechowywania wpisu w tablicy stron; typowa dzisiejsza strona to 2 lub 4 kB

Rys. 8.11. Wolne ramki: (a) przed przydziałem; (b) po przydziale

• gdy proces zostaje przedłożony w systemie do wykonania, wówczas sprawdza się jego rozmiar wyrażony w stronach
• dla każdej strony procesu jest potrzebna jedna ramka; zatem, jeśli proces wymaga n stron, to w pamięci powinno być dostępnych przynajmniej n ramek
• pierwsza strona procesu będzie załadowana do którejś z przydzielonych ramek, a numer tej ramki - wpisany do tablicy stron danego procesu
• tablica ramek: które ramki przydzielone / wolne 

• Budowa tablicy stron

• większość SO przydziela tablicę stron do każdego procesu
• w bloku kontrolnym procesu, prócz wartości innych rejestrów (np. licznika rozkazów), przechowuje się wskaźnik do tablicy stron
• w najprostszym przypadku, tablicę stron implementuje się jako zbiór rejestrów specjalnego przeznaczenia
• większość obecnych komputerów przechowuje tablicę stron w pamięci operacyjnej
• rejestr bazowy tablicy stron wskazuje położenie tablicy stron w pamięci
• rejestr długości tablicy stron zawiera informację o rozmiarze tablicy stron
• przy takim podejściu, każdy dostęp do danych lub instrukcji wymaga dwóch kontaktów z pamięcią - powoduje to znaczne opóźnienie
• problem może być rozwiązany dzięki zastosowaniu specjalnej, małej i szybko przeszukiwanej, sprzętowej pamięci podręcznej, zwanej rejestrami asocjacyjnymi lub buforami translacji adresów stron (TLBs)
• rejestry asocjacyjne zawierają tylko podzbiór (8 - 2048 pozycji) wpisów z tablicy stron; ich przeszukiwanie odbywa się w sposób równoległy; jeśli numeru strony nie ma w rejestrach asocjacyjnych, to trzeba odwołać się do tablicy stron
• procent numerów stron odnajdywanych w rejestrach asocjacyjnych nosi nazwę współczynnika trafień, np. 80% oznacza, że w 80 przypadkach na 100 potrzebny numer jest w rejestrze asocjacyjnym
• niech np. przeglądnięcie rejestrów zabiera 20ns, a dostęp do pamięci 100ns, to gdy numer jest w rejestrach, dostęp do pamięci zajmie 120ns, a w przeciwnym wypadku zajmie 220ns
• efektywny czas dostępu do pamięci dla tego przypadku:  0.80 x 120 + 0.20 x 220 = 140ns, co oznacza spowolnienie dostępu do pamięci wynoszące 40% (140ns --> 100ns)
• dla 98% współczynnika trafień efektywny czas dostępu byłby 122ns
• przy użyciu 16 - 512 rejestrów --> współczynnik trafień od 80 do 98%
• procesor Morda 68030 ma 22 pozycje w buforze TLB; procesor Intel 80486 ma 32 rejestry, a deklarowany współczynnik 98%

• Ochrona pamięci

• do ochrony pamięci w środowisku stronicowanym służą bity ochrony, przypisane każdej ramce (pisanie, czytanie, wykonywanie)
• każdy wpis do tablicy stron zostaje z reguły uzupełniony o dodatkowy bit poprawności
  • p ("poprawne") oznacza, że strona znajduje się w logicznej przestrzeni adresowej procesu, a więc jest dozwolona
  • n - strona nie jest dozwolona

Rys. 8.13. Bit poprawności (p) lub niepoprawności (n) w tablicy stron

• Stronicowanie wielopoziomowe

• współczesne komputery posiadają bardzo wielkie przestrzenie adresowe (od 2³²  do 2⁶⁴)
• tablica stron staje się zbyt duża
• rozwiązanie: np. stronicowanie dwupoziomowe, gdzie tablica stron sama podzielona jest na strony

Rys. 8.14. Schemat dwupoziomowej tablicy stron

• np. 32-bitowa maszyna, o stronach 4 kB, jej logiczny adres dzieli się na
  • 20-bitowy numer strony
  • 12-bitową odległość na stronie
• ponieważ dzielimy tablicę stron na strony, numer strony podlega więc dalszemu podziałowi; logiczny adres przyjmie więc postać:

• S₁ jest indeksem do zewnętrznej tablicy stron, a S₂ oznacza przesunięcie na stronie tej zewnętrznej tablicy

• tłumaczenie adresu w takiej architekturze przedstawione jest na rysunku poniżej:

Rys. 8.15. Tłumaczenie adresu w dwupoziomowej architekturze 32-bitowej

 

• Odwrócona tablica stron

Rys. 8.16. Odwrócona tablica stron

• każdy adres wirtualny w systemie składa się z trójki:

< identyfikator-procesu, numer-strony, odległość >

• każdy wpis w odwróconej tablicy stron jest parą: < identyfikator-procesu, numer-strony >
• gdy pojawi się odwołanie do pamięci, wówczas część adresu wirtualnego jest przekazywana podsystemowi pamięci
• jeśli dopasowanie się powiedzie, to tworzony jest adres fizyczny; niedopasowanie oznacza, że usiłowano użyć niedozwolonego adresu

• Strony dzielone

Rys.8.17. Dzielenie kodu w środowisku stronicowanym

• dzielenie wspólnego kodu, np. w środowisku z podziałem czasu
  • jedna kopia kodu wznawialnego (który nie modyfikuje sam siebie) jest dzielona między procesami (edytory tekstu, kompilatory, ...)

• Segmentacja

   

  • segmentacja - schemat zarządzania pamięcią operacyjną oparty na wyobrażeniu użytkownika o tym czym jest program / pamięć
  • program, z punktu widzenia użytkownika to zbiór segmentów, będących logicznymi jednostkami, takimi jak program główny, podprogram, funkcja, itd.

  

  Rys. 8.18. Program z punktu widzenia użytkownika

  • każdy segment ma nazwę (numer) oraz długość; adres logiczny odwołania do segmentu tworzy więc parę: < numer-segmentu (s), odległość (o) >

  

  Rys. 8.19. Sprzęt do segmentacji

  • należy zdefiniować implementację odwzorowującą 2-wymiarowe adresy określone przez użytkownika na 1-wymiarowe adresy fizyczne
  • takie odwzorowanie daje tablica segmentów; pozycja tablicy segmentów składa się z bazy segmentu i granicy

  

  Rys. 8.20. Przykład segmentacji

  • przykład segmentacji
    • np. segment 2 ma długość 400B (granica) i zaczyna się od adresu 4300 (baza)
    • odwołanie do bajtu 53 segmentu 2 jest odwzorowywane na adres 4300+53=4353
    • odwołanie do bajtu 1222 segmentu 0 spowoduje awaryjne przejście do SO

  

  Rys. 8.21 Dzielenie segmentów w systemie pamięci segmentowanej

  • Ochrona i wspólne użytkowanie

• zaletą segmentacji jest powiązanie ochrony pamięci z segmentami (segmenty rozkazów, segmenty danych)
• sprzęt odwzorowujący będzie sprawdzał bity ochrony związane z każdą pozycją tablicy segmentów, kontrolujące read / write / execute status segmentu
• problemy fragmentacji zewnętrznej

• Segmentacja ze stronicowaniem

   

  

  Rys. 8.22. Segmentacja stronicowana w komputerze GE 645 (system MULTICS)

  • w systemie MULTICS rozwiązano problem zewnętrznej fragmentacji i kosztownego przeszukiwania w celu przydzielenia pamięci dla segmentów przez wprowadzenie stronicowania segmentów
  • tablica segmentów, posiada w charakterze wpisu nie adres segmentu, lecz adres bazowy tablicy stron tego segmentu
  • każdy segment musi mieć oddzielną tablicę stron

  • adres logiczny w systemie MULTICS składa się z 18-bitowego numeru segmentu i 16-bitowej odległości; w systemie stronicuje się również tablicę segmentów; tak więc, logiczny adres w systemie wygląda następująco:

  ... ramka

  S₁ - indeks do tablicy stron tablicy segmentów

  S₂ - przemieszczenie na stronie tablicy segmentów

  O₁ - przemieszczenie w tablicy stron potrzebnego segmentu

  O₂ - przemieszczenie na stronie zawierającej słowo, do którego chce się uzyskać dostęp

  • w celu zwiększenia wydajności, zastosowano 16 rejestrów asocjacyjnych zawierających adresy 16 ostatnio używanych stron

  

  Rys. 8.24. Tłumaczenie adresu w procesorze Intel 80386

  • System OS/2 (IBM) w wersji 32-bitowej

• działa na procesorze Intel 386 (i późniejszych)
• adres logiczny jest parą (selektor, odległość), przy czym selektor jest liczbą o postaci (s,g,p) gdzie s - numer segmentu; g - wskazuje czy segment jest w tablicy deskryptorów globalnych, czy lokalnych
• każdy segment jest stronicowany, a stronicowanie jest dwupoziomowe
• tablice stron można wysyłać na dysk, co polepsza wydajność

<<< THE END >>>