C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:305

連續內存分配及其方式詳解

內存應容納操作系統和各種用戶進程,因此應該盡可能有效地分配內存。本節介紹一種早期方法:連續內存分配

內存通常分為兩個區域:一個用于駐留操作系統,另一個用于用戶進程。操作系統可以放在低內存,也可放在高內存,這取決與中斷向量的位置。由于中斷向量通常位于低內存,因此程序員通常將操作系統也放在低內存。因此,本節只討論操作系統位于低內存的情況,其他情況的討論也類似。

通常,我們需要將多個進程同時放在內存中。因此我們需要考慮,如何為輸入隊列中需要調入內存的進程分配內存空間。在采用連續內存分配時,每個進程位于一個連續的內存區域,與包含下一個進程的內存相連。

內存保護

在深入討論內存分配前,我們應先討論內存保護問題。結合《內存交換》一節中討論的兩個想法,我們可以防止進程訪問不屬于它的內存。如果一個系統有重定位寄存器和界限寄存器,則能實現我們的目標。

重定位寄存器含有最小的物理地址值,界限寄存器含有邏輯地址的范圍值(例如,重定位=100040,界限=74600)。每個邏輯地址應在界限寄存器規定的范圍內。MMU(內存管理單元)通過動態地將邏輯地址加上重定位寄存器的值,來進行映射。映射后的地址再發送到內存(圖1 )。

重定位和界限寄存器的硬件支持
圖 1 重定位和界限寄存器的硬件支持

當 CPU 調度器選擇一個進程來執行時,作為上下文切換工作的一部分,分派器會用正確的值來加載重定位寄存器和界限寄存器。由于 CPU 所產生的每個地址都需要與這些寄存器進行核對,所以可以保證操作系統和其他用戶的程序和數據不受該運行進程的影響。

重定位寄存器方案提供了一種有效方式,以便允許操作系統動態改變大小。許多情況都需要這一靈活性。例如,操作系統的驅動程序需要代碼和緩沖空間。如果一個驅動程序(或其他操作系統的服務)不常使用,可以不必在內存中保留它的代碼和數據,這部分空間可以用于其他目的。這類代碼有時稱為暫時的操作系統代碼,它們根據需要再調入或調出。因此,使用這種代碼可以在程序執行時動態改變操作系統的大小。

內存分配

現在我們討論內存分配。最為簡單的內存分配方法之一,就是將內存分為多個固定大小的分區。每個分區可以只包含一個進程。因此,多道程序的程度受限于分區數。如果使用這種多分區方法,那么當一個分區空閑時,可以從輸入隊列中選擇一個進程,以調入空閑分區。當該進程終止時,它的分區可以用于其他進程。

這種方法最初為 IBMOS/360 操作系統所使用,現在已不再使用。下面所描述的方法是固定分區方案的推廣(稱為 MVT),它主要用于批處理環境。這里所描述的許多思想也可用于采用純分段內存管理的分時操作系統。

對于可變分區方案,操作系統有一個表,用于記錄哪些內存可用和哪些內存已用。開始,所有內存都可用于用戶進程,因此可以作為一大塊的可用內存,稱為塊。最后,正如將會看到的,內存有一個集合,以包含各種大小的塊。

隨著進程進入系統,它們將被加入輸入隊列。操作系統根據所有進程的內存需求和現有可用內存的情況,決定哪些進程可分配內存。當進程分配到空間時,它就加載到內存,并開始競爭 CPU。當進程終止時,它將釋放內存,該內存可以被操作系統分配給輸入隊列內的其他進程。

任何時候,都有一個可用塊大小的列表和一個輸入隊列。操作系統根據調度算法來對輸入隊列進行排序。內存不斷地分配給進程,直到下一個進程的內存需求不能滿足為止,這時沒有足夠大的可用塊來加載進程。操作系統可以等到有足夠大的空間,或者可以往下掃描輸入隊列,以確定是否有其他內存需求較小的進程可以被滿足。

通常,如上所述,可用的內存塊為分散在內存里的不同大小的塊的集合。當新進程需 要內存時,系統為該進程查找足夠大的塊。如果塊太大,那么就分為兩塊:一塊分配給新進程,另一塊還回到塊集合。當進程終止時,它將釋放內存,該內存將還給塊的集合。如果新塊與其他塊相鄰,那么將這些塊合并成大塊。這時,系統可以檢查,是否有進程在等待內存空間,以及新合并的內存空間是否滿足等待進程等。

這種方法是通用動態存儲分配問題(根據一組空閑塊來分配大小為 n 的請求)的一個特例。這個問題有許多解決方法。

從一組可用塊中選擇一個空閑塊的最為常用方法包括:首次適應最優適應最差適應

模擬結果顯示,首次適應和最優適應在執行時間和利用空間方面都好于最差適應。首次適應和最優適應在利用空間方面難分伯仲,但是首次適應要更快些。

碎片

用于內存分配的首次適應和最優適應算法都有外部碎片的問題。

隨著進程加載到內存和從內存退出,空閑內存空間被分為小的片段。當總的可用內存之和可以滿足請求但并不連續時,這就出現了外部碎片問題:存儲被分成了大量的小塊,這個問題可能很嚴重。

在最壞情況下,每兩個進程之間就有空閑(或浪費的)塊。如果這些內存是一整塊,那么可能可以再運行多個進程。

選擇首次適應或者最優適應,可能會影響碎片的數量。(對一些系統來說,首次適應更好;對另一些系統,最優適應更好)。另一因素是從空閑塊的哪端開始分配。(哪個是剩余的塊,是上面的還是下面的?)不管使用哪種算法,外部碎片始終是個問題。

根據內存空間總的大小和平均進程大小的不同,外部碎片問題或許次要或許重要。例如,采用首次適應方法的統計說明,不管使用什么優化,假定有 N 個可分配塊,那么可能有 0.5N 個塊為外部碎片。即 1/3 的內存可能不能使用。這一特性稱為 50%規則

內存碎片可以是內部的,也可以是外部的。假設有一個 18 464 字節大小的孔,并采用 多分區分配方案。假設有一個進程需要 18 462 字節。如果只能分配所要求的塊,那么還剩下一個 2 字節的塊。維護這一小塊的開銷要比塊本身大很多。

因此,通常按固定大小的塊為單位(而不是字節)來分配內存。采用這種方案,進程所分配的內存可能比所需的要大。這兩個數字之差稱為內部碎片,這部分內存在分區內部,但又不能用。

外部碎片問題的一種解決方法是緊縮。它的目的是移動內存內容,以便將所有空閑空間合并成一整塊。然而,緊縮并非總是可能的。如果重定位是靜態的,并且在匯編時或加載時進行的,那么就不能緊縮。只有重定位是動態的,并且在運行時進行的,才可采用緊縮。

如果地址被動態重定位,可以首先移動程序和數據,然后再根據新基地址的值來改變基地址寄存器。如果能采用緊縮,那么還要評估開銷。最簡單的合并算法是簡單地將所有進程移到內存的一端,而將所有的塊移到內存的另一端,從而生成一個大的空閑塊。這種方案比較昂貴。

外部碎片化問題的另一個可能的解決方案是,允許進程的邏輯地址空間是不連續的,這樣,只要有物理內存可用,就允許為進程分配內存。有兩種互補的技術可以實現這個解決方案:分段和分頁。這兩個技術也可以組合起來。

碎片是一個常見問題,當需要管理數據塊時它就可能出現。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo