Pamięć a sterowanie procesami W poprzednich wykładach pokazano, w jaki sposób jednostka centralna może być współdzielona przez zbiór procesów. W wyniku planowania przydziału procesora można zarówno zwiększyć jego wykorzystanie, jak i skrócić czas udzielania przez komputer odpowiedzi użytkownikom. W celu urzeczywistnienia tego wzrostu wydajności należy jednak w pamięci operacyjnej umieszczać kilka procesów naraz - musimy dzielić pamięć. Program na ogół rezyduje na dysku jako binarny, wykonywalny plik. Aby nastąpiło wykonanie programu, należy go wprowadzić do pamięci operacyjnej i zaliczyć do odpowiadającego mu procesu. Jeśli sposób zarządzania pamięcią na to pozwala, to wykonywany proces może być przemieszczany między dyskiem a pamięcią operacyjną. Zbiór procesów czekających na dysku na wprowadzenie do pamięci w celu wykonania tworzy kolejką wejściową. Większość systemów pozwala procesowi użytkowemu przebywać w dowolnej części pamięci fizycznej. Toteż, choć przestrzeń adresów komputera zaczyna się od 00000, pierwszy adres procesu użytkownika nie musi wynosić 00000. Wpływa to na zakres adresów dostępnych dla programu użytkownika. Wiązanie adresów W większości przypadków program użytkownika, zanim zostanie wykonany, przechodzi przez kilka faz (niektóre z nich mogą nie występować). 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 (w rodzaju:„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. 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ń: 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. Gdy w późniejszym czasie ten adres początkowy ulegnie zmianie, wówczas kod taki trzeba będzie skompilować od nowa. Czas ładowania: Jeśli podczas kompilacji nie wiadomo, gdzie będzie umieszczony proces w pamięci, to kompilator musi wytwarzać kod przemieszczalny . W tym przypadku ostateczne wiązanie jest opóźniane do czasu ładowania. Jeśli adres początkowy ulegnie zmianie, to wystarczy tylko załadować ponownie kod użytkowy z uwzględnieniem nowej wartości tego adresu. 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. Ładowanie dynamiczne W celu lepszego wykorzystania obszaru pamięci stosuje się ładowanie dynamiczne. Przy ładowaniu dynamicznym podprogram nie jest wprowadzany do pamięci dopóty, dopóki nie zostanie wywołany. Do pamięci wprowadza się program główny i tam jest on wykonywany. Gdy jakiś podprogram chce wywołać inny podprogram, musi wówczas najpierw sprawdzić, czy ów podprogram znajduje się w pamięci. Jeśli go tam nie ma, to trzeba wywoływać program łączący i ładujący moduły przemieszczalne, który prowadzi do pamięci potrzebny podprogram oraz uaktualni tablicę adresów programu, aby odzwierciedlić tę zmianę. Ładowanie dynamiczne nie wymaga specjalnego wsparcia ze strony systemu operacyjnego. To użytkownicy są odpowiedzialni za takie zaprojektowanie programów, aby mogły one korzystać z tej metody. Systemy operacyjne mogą jednak pomagać programiście, dostarczając procedur bibliotecznych do realizowania ładowania dynamicznego. Konsolidacja dynamiczna Pomysł dynamicznej konsolidacji jest podobny do ładowania dynamicznego. Zamiast odwlekania ładowania do czasu wykonania, opóźnia się konsolidację. Cecha ta zwykle dotyczy bibliotek systemowych, na przykład bibliotek języków programowania. Jeśli system nie ma tej właściwości, to wszystkie programy muszą mieć dołączoną do swoich obrazów binarnych kopię biblioteki języka (lub przynajmniej kopie podprogramów, do których się odwołują). W przypadku konsolidacji dynamicznej, w obrazie binarnym, w miejscu odwołania bibliotecznego znajduje się tylko namiastka procedury. Namiastka procedury jest małym fragmentem kodu, wskazującym jak odnaleźć odpowiedni, rezydujący w pamięci podprogram biblioteczny lub jak załadować bibliotekę, jeśli podprogramu nie ma w pamięci. Programy, skonsolidowane przed zainstalowaniem nowej biblioteki, będą nadal wykonywane przy użyciu starej biblioteki. System tego rodzaju bywa nazywany bibliotekami dzielonymi. W odróżnieniu od ładowania dynamicznego konsolidacja dynamiczna wymaga na ogół pomocy ze strony systemu operacyjnego. Jeżeli procesy w pamięci są chronione przed sobą wzajemnie, to tylko system operacyjny może sprawdzać, czy potrzebny podprogram znajduje się w obszarach pamięci innych procesów oraz zezwalać, aby wiele procesów miało dostęp do tych samych adresów pamięci. Nakładki Rozmiar procesu jest ograniczony do wielkości pamięci fizycznej. Niekiedy, aby umożliwić większenie wymiarów procesu ponad ilość przydzielonej mu pamięci, stosuje się technikę zwaną nakładkami. Idea nakładek polega na przechowywaniu w pamięci tylko tych rozkazów i danych, które są stale potrzebne. Inne rozkazy są wprowadzane w miarę zapotrzebowania na miejsca zajmowane uprzednio przez rozkazy już zbyteczne (np. asamblery dwuprzebiegowe). Podobnie jak przy ładowaniu dynamicznym, nakładki nie wymagają specjalnego wsparcia ze strony systemu operacyjnego. Mogą być w całości wykonane przez użytkownika za pomocą prostej struktury plików, czytania za-wartości plików do pamięci oraz wykonywania skoków w określone miejsca pamięci w celu wykonania nowo przeczytanych instrukcji. System operacyjny odnotowuje tylko większą liczbę operacji wejścia-wyjścia niż zwykle. Użycie nakładek ogranicza się obecnie 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 zastosowanie bardziej zaawansowanych technik. Adresy logiczne i fizyczne Adres wytworzony przez procesor jest zazwyczaj nazywany adresem logicznym, a adres oglądany przez jednostkę pamięci (tj. ten, który zostaje umieszczony w jej rejestrze adresowym) na ogół zwie się adresem fizycznym. Schematy ustalania adresów podczas kompilacji oraz ładowania tworzą środowisko, w którym adresy logiczne i fizyczne są takie same. Z kolei schematy wiązania adresów podczas wykonywania rozkazów prowadzą do środowiska, w którym adresy logiczne i fizyczne są różne. W tym przypadku często określamy adres logiczny mianem adresu wirtualnego (ang. virtual address). Zbiór wszystkich adresów logicznych generowanych przez program jest nazywany logiczną przestrzenią adresową. Zbiór wszystkich adresów fizycznych odpowiadających tym adresom logicznym nazywa się fizyczną przestrzenią adresową. Tak więc adresy logiczne i fizyczne powstające wskutek wiązania adresów podczas wykonywania procesu różnią się. Odwzorowywanie adresów wirtualnych na fizyczne, odbywające się podczas działania programu, jest dokonywane przez jednostkę zarządzania pamięcią (MMU), będącą urządzeniem sprzętowym. Wartość z rejestru przemieszczenia jest dodawana do każdego adresu wytwarzanego przez proces użytkownika w chwili odwoływania się do pamięci. Jeśli na przykład baza wynosi 14000, to gdy użytkownik próbuje zaadresować komórkę, wówczas wartość tego adresu jest dynamicznie zmieniana na odwołanie do komórki 14000; odwołanie do komórki 346 przemieszcza się do komórki 14346. Program użytkownika nigdy nie ma do czynienia z rzeczywistymi adresami fizycznymi. Program użytkownika działa na adresach logicznych. Sprzęt odwzorowujący pamięć zamienia adresy logiczne na adresy fizyczne. W takim schemacie istnieją dwoma rodzajami adresów: adresami logicznymi (z przedziału od O do max) i adresami fizycznymi (z prze-działu od R + O do R + max, przy czym R jest wartością bazy). Koncepcja logicznej przestrzeni adresów powiązanej z odrębną, fizyczną przestrzenią adresów jest podstawą właściwego zarządzania pamięcią. Przestrzeń wymiany Wykonanie procesu jest możliwe wtedy, gdy jest on w pamięci. Jednakże proces może być tymczasowo wymieniany tj. odsyłany z pamięci operacyjnej do pamięci pomocniczej i z powrotem w celu kontynuowania działania. Zazwyczaj proces, który ulega
|
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. Jeśli adresy ustala się podczas wykonania, to istnieje możliwość sprowadzenia procesu do innego obszaru pamięci, ponieważ adresy fizyczne są obliczane na bieżąco. Do wymiany jest potrzebna pamięć pomocnicza. Jest nią na ogół szybki dysk. Musi on być wystarczająco pojemny, aby pomieścić wszystkie kopie obrazów pamięci wszystkich użytkowników. Powinien także umożliwiać bezpośredni dostęp do tych obrazów pamięci. Zauważmy, że główną częścią czasu wymiany jest czas przesyłania. W procesie z dynamiczną gospodarką pamięcią trzeba będzie zatem korzystać z funkcji systemowych służących do zamawiania pamięci i zwalniania pamięci w celu informowania systemu operacyjnego o zmieniających się potrzebach. Przydział ciągły Pamięć operacyjna (główna) musi pomieścić zarówno system operacyjny, jak i rozmaite procesy użytkownika. Jest ona zazwyczaj podzielona na dwie części - jedną dla rezydującego systemu operacyjnego i drugą dla procesów użytkownika. System operacyjny można umieścić w pamięci dolnej albo w pamięci górnej. Na decyzję w tej sprawie wpływa głównie lokalizacja wektora przerwań. Ponieważ wektor przerwań znajduje się często w pamięci dolnej, powszechniejszym rozwiązaniem jest umieszczenie systemu operacyjnego w pamięci dolnej. Jeśli system operacyjny pozostaje w pamięci dolnej, a proces użytkownika wykonuje się w pamięci górnej, to powstaje potrzeba ochrony kodu i danych systemu operacyjnego przed zmianami (przypadkowymi lub złośliwymi), które może spowodować proces użytkownika. Procesy użytkowników należy także chronić wzajemnie przed sobą. Przydział pojedynczego obszaru 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. Posługiwanie się rejestrem przemieszczenia pozwala skutecznie zmieniać na bieżąco rozmiar systemu operacyjnego. Plastyczność taka jest pożądana w wielu sytuacjach. System operacyjny zawiera na przykład kod i obszar buforów modułów sterujących urządzeń. Jeśli moduł sterujący urządzenia (lub inna usługa systemu operacyjnego) nie jest w częstym użyciu, to utrzymywanie jego kodu i danych w pamięci operacyjnej nie jest wskazane, gdyż zajmowany przez niego obszar można by wykorzystać do innych celów. Kod taki nazywa się niekiedy kodem przejściowym systemu operacyjnego pojawia się i znika stosownie do potrzeb. Przydział wielu obszarów Ponieważ na ogół jest pożądane, aby w pamięci pozostawało w tym samym czasie kilka procesów użytkowych, musimy rozważyć problem przydzielania pamięci różnym procesom oczekującym w kolejce wejściowej na wprowadzenie do pamięci operacyjnej. Jednym z najprostszych schematów przydziału pamięci jest podzielenie jej na pewną liczbę obszarów o stałym rozmiarze. Każdy obszar może zawierać dokładnie jeden proces. Zatem stopień wieloprogramowości jest ograniczony przez liczbę obszarów. 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 (ang. hole). Gdy przybywa proces z zapotrzebowaniem na pamięć, wówczas poszukuje się dla niego wystarczająco obszernej dziury. Jeśli zostanie znaleziona, to przydziela się z niej pamięć tylko w niezbędnej ilości, pozostawiając resztę na przyszłe potrzeby. Dynamiczny przydział pamięci Dynamiczny przydział pamięci polega na rozstrzyganiu, jak na podstawie listy wolnych dziur spełnić zamówienie na obszar o rozmiarze n. Najbardziej znane strategie wyboru wolnego obszaru ze zbioru dostępnych dziur to: Pierwsze dopasowanie : Przydziela się pierwszą dziurę o wystarczającej wielkości. Szukanie można rozpocząć od początku wykazu dziur lub od miejsca, w którym je ostatnio zakończono. Szukanie kończy się z chwilą napotkania dostatecznie dużej, wolnej dziury. Najlepsze dopasowanie: Przydziela się najmniejszą z dostatecznie dużych dziur. Należy przejrzeć cała listę, chyba że jest ona uporządkowana według wymiarów. Ta strategia zapewnia najmniejsze pozostałości po przydziale Najgorsze dopasowanie: Przydziela się największą dziurę. Również w tym przypadku należy przeszukać cała 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ż pozostałość wynikająca z podejścia polegającego na przydziale najlepiej pasującej dziury. Fragmentacja Opisane algorytmy są obarczone zewnętrzną fragmentacją. Istnienie zewnętrznej fragmentacji objawia się tym, że suma wolnych obszarów w pamięci wystarcza na spełnienie zamówienia, ale nie tworzą one spójnego obszaru. Inny problem wynikający ze stosowania schematu przydzielania wielu obszarów jest pokazany na rys. Weźmy pod uwagę dziurę wielkości 18 464 bajtów. Załóżmy, że następny proces wymaga 18 462 bajtów. Jeśli przydzielimy dokładnie zamówiony blok, to pozostanie dwubajtowy nieużytek. Nakład na trzymanie informacji o takiej dziurze znacznie przekroczy samą jej wielkość. Na ogół stosuje więc się metodę dołączania bardzo małych dziur do większych przydziałów. W ten sposób przydzielona pamięć może być nieco większa niż zamawiana. Różnica między tymi dwiema wielkościami stanowi wewnętrzną fragmentację, czyli bezużyteczny kawałek pamięci wewnątrz przydzielonego obszaru. Upakowanie pamięci Jednym z rozwiązań problemu zewnętrznej fragmentacji 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. Jeśli ustalanie adresów jest statyczne i wykonywane podczas tłumaczenia lub ładowania, to upakowanie nie jest możliwe. Możliwość upakowywania występuje tylko przy dynamicznym wiązaniu adresów wykonywanym podczas działania procesu. Jeśli istnieje możliwość upakowania, to należy oszacować jego koszt. Najprostszy algorytm upakowania polega po prostu na przesunięciu wszystkich procesów w kierunku jednego końca pamięci; wszystkie dziury lokują się na drugim końcu, tworząc jeden wielki obszar dostępnej pamięci. W celu zmniejszenia kosztów upakowaniu może również towarzyszyć wymiana. Stronicowanie Inne możliwe rozwiązanie problemu zewnętrznej fragmentacji polega na dopuszczeniu nieciągłości logicznej przestrzeni adresowej procesu, tj. zezwoleniu na to, aby procesowi można było przydzielać dowolne dostępne miejsca w pamięci fizycznej. Jednym ze sposobów implementacji takiego rozwiązania jest zastosowanie schematu stronicowania. Stosując stronicowanie, omija się 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 zarządzania pamięcią. Metoda podstawowa Pamięć fizyczną dzieli się na bloki 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ęci operacyjnej. Pamięć pomocniczą dzieli się na stałej długości bloki tego samego rozmiaru co ramki w pamięci operacyjnej. Inne możliwe rozwiązanie problemu zewnętrznej fragmentacji polega na dopuszczeniu nieciągłości logicznej przestrzeni adresowej procesu, tj. zezwoleniu na to, aby procesowi można było przydzielać dowolne dostępne miejsca w pamięci fizycznej. Jednym ze sposobów implementacji takiego rozwiązania jest zastosowanie schematu stronicowania. Każdy adres wygenerowany przez procesor dzieli się na dwie części: numer strony s i odległość na stronie o. 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. |
|
|