操作系統內存管理的實現

孫溫穩

（鄭州師范學院　信息科學與技術學院，河南　鄭州　450044）

?

操作系統內存管理的實現

孫溫穩

（鄭州師范學院信息科學與技術學院，河南鄭州450044）

摘要：在操作系統課程中的實驗教學中，針對如何設計管理內存的實驗，通過介紹具體的函數編寫（使用C語言）來引導學生如何實現手工編寫管理內存，其中包括如何初始化內存，如何使用最先適應法分配內存，如何釋放內存，以及如何顯示內存。

關鍵詞：內存管理；C語言編程；分區分配算法

操作系統屬于計算機專業的專業基礎課程之一，是一門理論與實踐并重的課程，也是一門教師難教、學生難學的課程。其教學難點集中表現在：內容十分龐雜，涉及面廣，與計算機軟、硬件及用戶都有著密切的交互；實踐性強，與實際運行著的各類操作系統有著密切的聯系。所以，在教學過程中要理論結合實踐，設計出一些相應的實驗，來激發學生學習的積極性。內存管理是操作系統課程學習中的難點、重點之一，也是計算機編程最為基本的領域之一。對實際編程來說，理解內存管理器的能力與局限性至關重要。該文將介紹如何用C語言設計一些函數來引導學生用手工實現內存的管理，從而加深對內存管理的理解［1］。

1　操作系統內存管理概述

通常將已分配給用戶使用的一段連續的內存空間稱為“占用塊”，將未分配給任何用戶的一段連續的內存空間稱為“可利用空間塊”或者“空閑塊”。可以為學生設計一些編程過程當中用到的一些常量和變量：①設置常量HEAP_SIZE為 內 存 區 域 總 的 尺寸，如：#define HEAP_SIZE 1048576；②設置指定內存區域指針struct fb{size_t size;struct fb*next;}。需要說明的是，size_t 在C語言中是一種“整型”類型，里面保存的是一個整數，如int、long。這種整數用來記錄一個大小（size）。size_t的全稱應該是size type，就是說“一種用來記錄大小的數據類型”。其中，‘size’字段包括所指定內存塊的總的大小，‘next’字段包括下一個內存塊的地址，如果沒有下一個內存塊，則為空。并且內存塊的排列是以地址的大小順序遞增排列的。

2　內存管理的算法

實現內存管理的算法建立于內存空閑塊所在的鏈表的分配原理。對每一個空閑塊都有其相關的描述包括塊的大小和相連的下一個空閑塊。換句話說，內存的管理也就是實現內存分配和釋放的管理。目前已經有了3種算法關于實現內存的管理，分別是最先適應法、最佳適應法和最差適應算法。而每一種算法實現都包含4個函數，需要學生完成下面4個函數的編寫工作。2.1void mem_init():（內存初始化）

mem_init是初始化內存分配程序的函數，其要完成以下兩件事：找到系統中有效內存區域，并將它們初始化，這些初始化內存塊的尺寸為內存區域的總尺寸減去該結構體變量所占用空間的字節數，即taille_libre= HEAP_SIZE-sizeof(struct fb)。然后建立起指向我們管理的內存的指針。

void mem_init(){size_t taille_libre;//初始化空閑內存塊;//初始化占用塊內存指針}

2.1void*mem_alloc(size_t size)（分配內存）

該函數帶有一個入口參數為被分配內存塊的大小，且返回一個指向被分配內存塊的指針，若沒有可分配的內存塊，則返回NLUU。目前實現分區分配有3種算法：最先適應法、最佳適應法和最壞適應法。運行時可任選一種算法。系統均能顯示內存分配的狀態和參數變化情況。最先適應法是分配時從表頭指針開始查找可利用空間表，將找到的第一個大小不小于“請求”的空閑塊的一部分分配給用戶。最先適應算法要求可用表或自由鏈接按起始地址遞增的次序排列。該算法的最大特點是一旦找到大于或等于所要求內存長度的分區，則搜索結束。最佳適應算法將可利用空間表中一個大小不小于“請求”且最接近“請求”的空閑塊的一部分分配給用戶。最差適應算法將可利用空間表中一個大小不小于“請求”且是鏈表中最大的空閑塊的一部分分配給用戶。該函數主要實現第一種算法，當某用戶請求N字節內存，分配器遍歷空閑塊鏈表以尋找一塊足夠大的內存塊。如果內存塊的內存部分與請求的內存大小相同，則將此內存塊從鏈表中移除同時返回一個指向此內存塊內存部分的指針。如果內存部分的大小大于所需要的內存，分割此塊內存為兩部分，一個是申請的大小，另一個是剩余的大小。然后將分配給用戶的那塊內存傳給用戶，并將剩下的那塊（如果有的話）返回到鏈表上。可將最先適應法定義為0，最壞適應法定義為1，最佳適應法定義為2。

#define FIRST_FIT 0

#define WORST_FIT 1

#define BEST_FIT 2

void*mem_alloc(size_t size)

{switch(choix_algo){用 switch選擇合適的算法

case FIRST_FIT:

case WORST_FIT:

case BEST_FIT:......}}在實際的算法實現當中，還應考慮在回收用戶釋放的內存塊后對內存空間的重新組織，合并連續的內存塊，即“節點合并”的問題。因為系統在不斷的分配和回收過程中，使得大的空閑塊逐漸被分割成小的占用塊，然后又重新成為空閑塊被系統回收，如此反復，地址相鄰的兩塊空閑塊卻分別作為鏈表中的節點存在，導致出現較大的用戶“請求”時，雖然有足夠的空閑空間，但是他們分布在多個空閑塊內，分配無法進行。為了使內存空間得到更有效的利用，就要求在回收內存塊后對內存空間進行重新組織，合并連續的內存空間，最大限度地滿足將來的分配需求。下面就來看一下如何來實現這一功能。

2.2Void mem_free(void*zone,size_t size)（釋放內存）

這個函數帶有2個入口參數，zone為將要釋放內存塊的地址，size為將要釋放內存塊的大小。當用戶釋放一個內存塊，將遍歷占用塊的鏈表（記住，鏈表是有序的），然后根據內存塊的地址搜索其位置，找到后并從鏈表中刪除。同時將被釋放塊加入到空閑塊的鏈表中，將此內存塊與其相鄰塊合并。若其正好處于其他兩個空閑塊的中間位置，將把它們合并成一個尺寸更大的空閑塊。

void mem_free(void*zone,size_t size)

{//可設計一些需要的指針變量;//尋找在占用塊鏈表中要釋放的內存塊;//將要釋放的內存塊從占用塊的鏈表中刪除;//插入新的空閑塊到空閑塊鏈表中，同時要進行適當的合并://1.前面是否有空閑可合并://2.合并后面的空閑塊:}

2.3Void mem_show(void(*print)(void*zone, size_t size))（顯示內存）

這個函數有一個入口參數是一個指針指向一個過程print，這個過程本身帶有2個參數，一個參數是內存地址，一個參數是內存塊的大小。Print這個過程被用于在屏幕上顯示特定的空閑塊。顯示的方式可分為3種情況：第一種傳統的顯示方式，主要用于顯示空閑塊鏈表；第二種增長的顯示方式，主要用于顯示占有塊鏈表；第三種個人的顯示方式，主要用于顯示所有內存塊的狀態、分配情況，并且內存塊按升序排列。

3　驗證（如何運行所編寫的函數）

在一步驟中，需要編寫主函數main()函數以及其他一些所需要的函數，如幫助函數aide()。為了減輕學生的負擔，這些函數可由老師給出。

動態存儲管理的算法是操作系統設計的一個重要問題，學習和研究它們能夠為在操作系統等方面的深入研究提供一定的理論依據和實踐感知。通過了解諸多算法的基本思想和應用環境，也使得學生更加深入地了解軟件在運行時計算機內存資源如何高效、快速地分配，并且在適當的時候釋放和回收內存資源。

參考文獻：

［1］Jonathan Bartlett.Inside memory management［EB/OL］. （2004-10-16）[2016-01-15].http://www-128.ibm.com/developer?works/linux/library/l-memory.

中圖分類號：TP31

文獻標識碼：A

文章編號：1003-5168（2016）02-0062-02

收稿日期：2016-01-16

作者簡介：孫溫穩（1974-），女，碩士，研究方向：人工智能。

Implementation of Memory Management in Operating System

Sun Wenwen
（Information Science&Technology College，Zhengzhou Normal University，Zhengzhou Henan 450044）

Abstract:This paper provided an experiment on how to design and manage memory in experimental teach?ing of operating system course,by specific examples(using C language)to guide students how to manage memory manual,including how to initialize the memory,how to allocate memory by using the first fit algo?rithm,how to release the memory,as well as how to display memory.

Keywords:memory management；C language programming；partition allocation algorithms