08. 記憶體管理策略 (Memory Management Strategies)

             

08. 記憶體管理策略 (Memory Management Strategies)

基於課程投影片與恐龍書所整理

內容大綱

  • 背景
  • 置換(Swapping)
  • 連續記憶體配置(Contiguous Memory Allocation)
  • Segmentation
  • 分頁(Paging)
  • Structure of Page Table
  • Example:Intel
  • Example:ARM

 

(8.1)背景

(1) 目的: 存儲器是計算機系統的重要組成部分,雖然記憶體容量在不斷擴大,但記憶體仍是寶貴資源,如何提高主存儲器利用率,並擴充主存,對主存信息實現有效保護是存儲器管理主要任務,也是各種不同存儲管理策略的目標。

(2) 存儲管理目的和功能

  • 主存儲器的分配和回收

為每一道程序分配記憶體空間,使它們“各得其所”。

  • 提高主存儲器的利用率。

減少不可用的存儲空間,允許多道程序動態共享主存。

  • 存儲保護 

確保每道程序都在自己的記憶體空間運行,互不干擾。 

  • 記憶體擴充

從邏輯上擴充記憶體容量,使用戶認為系統所擁有的記憶體空間遠比其實際的記憶體空間(硬件RAM)大的多。

  • 程式(program)必須從硬碟移動到記憶體中,並變成一個進程(process)才能執行
  • CPU只能直接存取,CPU內暫存器(register)或記憶體(memory)的內容

  • CPU可以在一個時脈週期內,存取暫存器(register)多次
  • 但是存取相同內容的話,存取記憶體(memory)可能要花數個CPU時脈週期(因為memory速率較register慢),照成CPU需要等待(stall)
  • 補救方法就是,在快與慢之間加入存取速率中等的快取記憶體(cache)
  • 保護記憶體內容並正確存取 

(3) 基底暫存器與限制暫存器(Base and Limit Registers)

     使用兩個暫存器,分別記錄該行程/進程(process)的起始記憶體地址,我們稱為基底暫存器(Base register),與該進程所佔記憶體地址大小,我們稱為限制暫存器(Limist register)

 


 

而程序會在CPU的監督下只能存取範圍內的內容

 

(8.2)地址連結(Address Binding)

      程式必須載入到記憶體後,變成行程/進程(process)後才能執行。在硬碟上等待被載入到記憶體執行得的所有行程,會形成一個輸入佇列(input queue)

      雖然記憶體的起始地址是000000,但使用者的行程地址開頭不一定是000000,此外寫在行程裡的地址位置可能剛好有人用了。

      所以使用者的程式在開始執行前,會經過許多步驟,而原始程式的地址通常只是個符號(例如:count),而在編譯後,符號化的地址可能重新地位為  "程式起始地址後,往後數000014",而之後的鏈結器(Linker)或載入器(Loder)又會重行定位,把地址連結(bind) 至絕對地址 "例如700014"

而與記憶體位置的連結(bind),可以在以下任何步驟完成:

  • 編譯時間 (compile time):如果編譯時,程式所在的記憶體位置已知,那麼可產生絕對碼(absolute code) 如果起始位置變化,必須重新編譯代碼
  • 載入時間 (load time):如果編譯時不能確定程式所在的記憶體位置,則必須生成 重定代(relocatable code) 
  • 執行時間 (execution time):如果行程正要執行時,記憶體區段被移動到另一個區段,則連結時間才會延遲到這個時候(這需要硬體是否支援)

 

 

                                  

 

 

 

 

 

(8.3)地址重定位

(1). 名字空間、地址空間和存儲空間在源程序中,是通過符號名來訪問子程序和數據的,程序中符號名的集合稱為“名字空間”。

     彙編語言源程序經過彙編,或者高級語言源程序經過編譯,得到的目標程序是以“0”作為參考地址的模塊。然後多個目標模塊由連接程序連接成一個具有統一地址的裝配模塊,以便最後裝入記憶體中執行。目標模塊中的地址稱為相對地址(或稱為“邏輯地址”),而把相對地址的集合稱為“相對地址空間”或簡稱為“地址空間”。

    裝配模塊雖然具有統一的地址空間,但是仍是以“0”作為參考地址,即是浮動的。要把它裝入記憶體執行,就要確定裝入記憶體的實際物理地址,並修改程序中與地址有關的代碼,這一過程稱為地址重定位。地址空間的程序和數據經過地址重定位處理後,就變成了可由CPU直接執行的絕對地址程序。我們把這一地址集合稱為“絕對地址空間”或“存儲空間”。

(2). 地址重定位

  • 地址重定位完成把相對地址轉換成記憶體中的絕對地址,這個過程稱為地址映射(map)。按照重定位的時機,可分為靜態重定位和動態重定位。靜態重定位靜態重定位是在程序執行之前進行重定位。它根據裝配模塊將要裝入的記憶體起始地址,直接修改裝配模塊中的有關使用地址的指令。在下圖中以“0”作為參考地址的裝配模塊,要裝入以1000為起始地址的存儲空間。顯然在裝入程序之前,程序必須做一些修改才能正確運行。 
  • 程序的目標模塊在裝入記憶體時,與地址有關的指令都無須進行修改,如在圖中LOAD 1,2500這條指令中仍保持相對地址2500。當該模塊被操作系統調度到處理機上執行時,操作系統首先把該模塊裝入的實際起始地址減去目標模塊的相對基地址(圖中該模塊的基地址為0),然後將其差值裝入重定位寄存器。當CPU取一條訪問記憶體的指令時,地址變換硬件邏輯自動將指令中的相對地址與重定位寄存器中的值相加,再根據和值作為記憶體的絕對地址去訪問該單元的數據。 
  • 動態重定位是在指令執行過程中動態進行,這帶來兩個好處:

       1)目標程序裝入記憶體時無需任何修改,所以裝入之後再移動也不會影響其正確運行,這便於存儲器        用緊縮來解決存儲器的碎片問題。

       2)一個程序由若干個相對獨立的目標模塊組成時,每個目標模塊各裝入一個存儲區域,這些存儲區域        可以不相鄰接,只要各個模塊有自己對應的重定位寄存器就可以了。

(3).連續分配存儲方式

  •  單一連續分配

     一種最簡單的存儲管理方式,只能用於單用戶、單任務的操作系統,如在8位和16位微機上CP/M和MS-      DOS操作系統。它將記憶體分為兩個區:

     系統區:僅供操作系統使用,通常設置在記憶體的低段;

     用戶區:指除系統區以外的全部記憶體空間,提供給用戶使用。 

  • 可變式分區分配

--可變式分區指在作業裝入記憶體時,從可用的記憶體中劃出一塊連續的區域分配給它,且分區大小正好等於該作業的大小。可變式分區中分區的大小和分區的個數都是可變的,而且是根據作業的大小和多少動態地劃分,因此又稱為動態式分區。這種存儲管理技術既可以獲得較大的靈活性,又能提高記憶體的利用率。

--可變式分區的分配和釋放的基本思想是:在分配時,首先找到一個足夠大的空閒分區,即這個空閒區的大小比作業要求的要大,系統則將這個空閒分區分成兩部分:一部分成為已分配的分區,剩餘的部分仍作為空閒區。在回收撤除作業所佔領的分區時,要檢查回收的分區是否與前後空閒的分區相領接,若是,則加以合併,使之成為一個連續的大空間。

--可變式分區數據結構

     1)空閒區表形式

     2)空閒分區表為每個尚未分配的分區設置一個表項,包括分區的序號、大小、始址和狀態。

     3)空閒區鏈形式

在每個分區的起始部分,設置一些用於控制分區分配的信息(如分區的大小和狀態位),以及用於鏈接其它分區的前向指針;在分區尾部,則設置了一個後向指針,為了檢索方便也設置了控制分區分配的信息。然後,通過前、後向指針將所有的分區鏈接成一個雙向鍊錶。

(4). 分區分配算法

  • 最佳配合法(Best-Fit):它從全部空閒區中找出能滿足作業要求的、且大小最小的空閒分區,這種方法能使碎片盡量小。為適應這種算法,空閒分區表(空閒區鏈)中的空閒分區要按大小從小到大進行排序,自表頭開始查找到第一個滿足要求的自由分區分配。
  • 最先配合算法(First-Fit):從空閒分區表的第一個表目起查找該表,把最先能夠滿足要求的空閒區分配給作業,這種方法目的在於減少查找時間。為適應這種算法,空閒分區表(空閒區鏈)中的空閒分區要按地址由低到高進行排序。
  • 循環最先算法:該算法是首次適應算法的變種。在分配內存空間時,不再每次從表頭(鏈首)開始查找,而是從上次找到的空閒區的下一個空閒區開始查找,直到找到第一個能滿足要求的空閒區為止,並從中劃出一塊與請求大小相等的內存空間分配給作業。該算法能使內存中的空閒區分佈得比較均勻。
  • 最差配合法(Worst-fit):從所有未分配的分區中挑選最大的且大於和等於作業大小的分區分給要求的作業;空閒分區按大小由大到小排序。

(8.4)交換 

(1). 交換技術

      在多道程序環境下,一方面,在內存中的某些進程由於某事件尚未發生而被阻塞運行,但它卻佔用了大量的內存空間,甚至有時可能出現在內存中所有進程都被阻塞而迫使CPU停止下來等待的情況;另一方面,卻又有著許多作業在外存上等待,因無內存而不能進入內存運行的情況。顯然這對系統資源是一種嚴重的浪費,且使系統吞吐量下降。為了解決這一問題,在系統中又增設了交換(也稱交換)設施。所謂“交換”,是指把內存中暫時不能運行的進程或者暫時不用的程序和數據調出到外存上,以便騰出足夠的內存空間,再把已具備運行條件的進程或進程所需要的程序和數據調入內存。交換是提高內存利用率的有效措施。自從在60 年代初期出現“交換”技術後,它便引起了人們的重視,現在該技術已被廣泛地應用於操作系統中。

    如果交換是以整個進程為單位的,便稱之為“整體交換”或“進程交換”。這種交換被廣泛地應用於分時系統中,其目的是用來解決內存緊張問題,並可進一步提高內存的利用率。而如果交換是以“頁”或“段”為單位進行的,則分別稱之為“頁面交換”或“分段交換”,又統稱為“部分交換”。這種交換方法是實現後面要講到的請求分頁和請求分段式存儲管理的基礎,其目的是為了支持虛擬存儲系統。在此,我們只介紹進程交換,而分頁或分段交換將放在虛擬存儲器中介紹。為了實現進程交換,系統必須能實現三方面的功能:交換空間的管理、進程的換出,以及進程的換入。

      最早用在麻省理工學院的兼容分時系統CTSS中,該系統是單用戶系統,所有用戶都駐留在外存的後備隊列中,每次只調入一個作業進入記憶體運行,此作業的時間的時間片用完時,又將該作業調至外存,再將後備隊列中的一個作業調入記憶體運行一個時間片。這是早期的簡單分時系統,它採用早期的交換(調進/凋出)來滿足多個程序共享主存的需要。

(2). 交換空間的管理

     外存分為文件區和交換區。文件區用戶存放文件,對文件區管理目標是提高文件存儲空間的利用率,為此系統採用離散分配方式;交換區用於存放從記憶體頻繁換出的進程,它的管理目標是提高進程換入換出速度,為此系統採用連續分配方式。

(3). 進程的換出與換入

    當內核發現記憶體不足時調用交換進程,交換進程檢查駐留在內存的進程,選擇處於阻塞和睡眠狀態的進程換出,如無則選擇優先級低的駐留記憶體時間長的處於就緒狀態的進程換出。而當記憶體又空時交換進程在交換區中選擇換出時間長的處於就緒態的進程調入。

(8.5)分頁存儲管理

(1)純分頁存儲管理原理

  • 分頁

分頁存儲管理是將一個進程的地址空間劃分成若干個大小相等的區域,稱為頁,相應地,將內存空間劃分成與頁相同大小的若干個物理塊,稱為塊或頁框。在為進程分配記憶體時,將進程中的若干頁分別裝入多個不相鄰接的塊中。 

  • 多道程序環境下的交換

在多道程序環境下為了提高記憶體和CPU的利用率,增加系統吞吐量,系統中增設了交換,把記憶體中暫不能運行的進程調出到外存上,以騰出足夠的記憶體空間,把已具備運行條件的進程換入記憶體。

系統設置一個交換進程完成以上功能。為了實現進程交換,系統必須能實現對交換空間的管理,進程換入和進程換出等三項功能。

  • 地址結構

分頁系統的地址結構是由兩部分組成:前一部分為頁號P;後一部分為位移量W,即頁內地址。圖中的地址長度為32位,其中0~11位為頁內地址(每頁的大小為4K),12~31位為頁號,所以允許地址空間的大小最多為1M個頁。

(2)純分頁存儲管理

1.頁表

在將進程的每一頁離散地分配到內存的多個物理塊中後,系統應能保證能在內存中找到每個頁面所對應的物理塊。為此,系統為每個進程建立了一張頁面映射表,簡稱頁表(如下圖所示)。每個頁在頁表中佔一個表項,記錄該頁在記憶體中對應的物理塊號。進程在執行時,通過查找頁表,就可以找到每頁所對應的物理塊號。可見,頁表的作用是實現從頁號到物理塊號的地址映射。

2.地址變換機構

  • 基本的地址變換機構
    地址變換機構任務是利用頁表把用戶程序中的邏輯地址變換成記憶體中的物理地址。
    為了實現地址變換功能,在系統中設置頁表寄存器,用來存放頁表的始址和頁表的長度。在進程未執行時,每個進程對應的頁表的始址和長度存放在進程的PCB中,當該進程被調度時,就將它們裝入頁表寄存器。
    在進行地址變換時,系統將頁號與頁表長度進行比較,如果頁號大於頁表寄存器中的頁表長度,則訪問越界,產生越界中斷。如未出現越界,則根據頁表寄存器中的頁表始址和頁號計算出該頁在頁表項中的位置,得到該頁的物理塊號,將此物理塊號裝入物理地址寄存器中。與此同時,將有效地址(邏輯地址)寄存器中頁內地址直接裝入物理地址寄存器的塊內地址字段中,這樣便完成了從邏輯地址到物理地址的變換。
  • 具有快表的地址變換機構
    如果頁表存放在內存中,則每次訪問記憶體時,都要先訪問記憶體中的頁表,然後根據所形成的物理地址再訪問記憶體。這樣CPU存一個數據必須訪問兩次記憶體,從而使計算機的處理速度降低了1/2。

為了提高地址變換的速度,在地址變換機構中增設了一個具有並行查詢功能的特殊的高速緩衝存儲器,稱為“聯想存儲器”或“快表”,用以存放當前訪問的那些頁表項。

此時地址變換過程為:在CPU給出有效地址後,地址變換機構自動地將頁號送入高速緩存,確定所需要的頁是否在快表中。若是,則直接讀出該頁所對應的物理塊號,送入物理地址寄存器;若在快表中未找到對應的頁表項,則需再訪問記憶體中的頁表,找到後,把從頁表中讀出的頁表項存入快表中的一個寄存器單元中,以取代一個舊的頁表項。

(8.6)分段存儲管理

(1)分段的引入

   每個作業的地址空間,都有一定的邏輯結構關係,一個作業通常是由若干個程序段和數據段所組成的,例如、主程序、若干子程序以及數據區等。在頁式存儲管理中把一維線性的作業地址空間機械地劃分成若干大小相等的頁面,常常會把邏輯相關的部分劃分到不同的頁面。顯然、這樣做破壞了程序內部自然的邏輯結構,造成頁共享和保護的困難。

(2)分段存儲管理的方法

    是按程序的自然邏輯結構將程序分成若干邏輯段,並對這些段分別分配存儲空間。

這些段的長度可以不同,也不必連續進行分配。這種存儲管理方式已成為當今所有存儲管理方式的基礎。

(3)分段存儲管理基本思想

  • 主存空間劃分

物理段:主存空間被動態地劃分為若干個長度不相同的區域,每個區域稱作一個物理段。

段首址:每個物理段在記憶體中的起始地址。

  • 邏輯地址空間劃分

邏輯段:用戶程序按邏輯上有完整意義的段來劃分,稱為邏輯段,簡稱段。

段號:將用戶的所有邏輯段從0開始編號,稱為段號。

段內地址:將邏輯段中的所有單元從0開始依次編址

  • 邏輯地址的表示

劃分後邏輯地址由兩部分組成: 可用一個數對(S,W)來表示;

  • 主存分配

分配主存時,以段為單位,為每一個邏輯段分配一個連續的主存區(物理段); 邏輯上連續的段在主存中不一定連續存放。 

(4)分頁和分段的主要區別

頁是信息的物理單位,分頁是為了便於系統管理;而段是信息的邏輯單位,分段是為了滿足用戶需要。

分頁式存儲管理的作業地址空間是一維的;而分段式存儲管理作業地址空間是二維的。

 頁的長度由系統確定,是等長的;而段的長度由具有相對完整意義的信息長度確定,是不固定的。

 (8.7)具有快表的地址變換機構

由於成本的原因,快表不可能做得很大,通常只能存放16~512個頁表項。例如,在Intel80486中有32個。這對中、小型作業來說,已可能把全部頁表項放入快表中;但對於大型作業來說,則只能將一部分頁表放入快表中。由於對程序和數據的訪問往往帶有局限性,所以快表的命中率可以達到80%~90%。

例:假設檢索聯想存儲器的時間為20ns,訪問記憶體的時間為100ns,訪問聯想存儲器的的命中率為85%,則CPU存取一個數據的平均時間為T=0.85*120+0.15*220= 135ns,所以訪問時間只增加35%。如果不引入聯想存儲器,其訪問將延長一倍(達200ns)。

(8.8)主存管理要解決的問題

(1)記憶體空間管理

當用戶需要記憶體時,系統為之分配相應的存儲空間;不需要時,及時回收,以供其它用戶使用。

  • 記錄記憶體的使用情況:設置相應的記憶體分配表
  • 記憶體空間劃分問題:靜態或動態,等長或不等長。
  • 確定分配算法

(2)存儲擴充

用戶在編制程序時,不應該受記憶體容量限制,所以要採用一定技術來“擴充”記憶體的容量,使用戶得到比實際記憶體容量大的多的記憶體空間。

(3)存儲保護和主存共享

為多個程序共享記憶體提供保障,使在記憶體中的各道程序,只能訪問它自己的區域,避免各道程序間相互干擾,特別是當一道程序發生錯誤時,不致於影響其他程序的運行