操作系統(tǒng)內(nèi)存管理的實(shí)現(xiàn)

孫溫穩(wěn)

（鄭州師范學(xué)院　信息科學(xué)與技術(shù)學(xué)院，河南　鄭州　450044）

?

操作系統(tǒng)內(nèi)存管理的實(shí)現(xiàn)

孫溫穩(wěn)

（鄭州師范學(xué)院信息科學(xué)與技術(shù)學(xué)院，河南鄭州450044）

摘要：在操作系統(tǒng)課程中的實(shí)驗(yàn)教學(xué)中，針對如何設(shè)計(jì)管理內(nèi)存的實(shí)驗(yàn)，通過介紹具體的函數(shù)編寫（使用C語言）來引導(dǎo)學(xué)生如何實(shí)現(xiàn)手工編寫管理內(nèi)存，其中包括如何初始化內(nèi)存，如何使用最先適應(yīng)法分配內(nèi)存，如何釋放內(nèi)存，以及如何顯示內(nèi)存。

關(guān)鍵詞：內(nèi)存管理；C語言編程；分區(qū)分配算法

操作系統(tǒng)屬于計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課程之一，是一門理論與實(shí)踐并重的課程，也是一門教師難教、學(xué)生難學(xué)的課程。其教學(xué)難點(diǎn)集中表現(xiàn)在：內(nèi)容十分龐雜，涉及面廣，與計(jì)算機(jī)軟、硬件及用戶都有著密切的交互；實(shí)踐性強(qiáng)，與實(shí)際運(yùn)行著的各類操作系統(tǒng)有著密切的聯(lián)系。所以，在教學(xué)過程中要理論結(jié)合實(shí)踐，設(shè)計(jì)出一些相應(yīng)的實(shí)驗(yàn)，來激發(fā)學(xué)生學(xué)習(xí)的積極性。內(nèi)存管理是操作系統(tǒng)課程學(xué)習(xí)中的難點(diǎn)、重點(diǎn)之一，也是計(jì)算機(jī)編程最為基本的領(lǐng)域之一。對實(shí)際編程來說，理解內(nèi)存管理器的能力與局限性至關(guān)重要。該文將介紹如何用C語言設(shè)計(jì)一些函數(shù)來引導(dǎo)學(xué)生用手工實(shí)現(xiàn)內(nèi)存的管理，從而加深對內(nèi)存管理的理解［1］。

1　操作系統(tǒng)內(nèi)存管理概述

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

2　內(nèi)存管理的算法

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

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

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

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

該函數(shù)帶有一個入口參數(shù)為被分配內(nèi)存塊的大小，且返回一個指向被分配內(nèi)存塊的指針，若沒有可分配的內(nèi)存塊，則返回NLUU。目前實(shí)現(xiàn)分區(qū)分配有3種算法：最先適應(yīng)法、最佳適應(yīng)法和最壞適應(yīng)法。運(yùn)行時可任選一種算法。系統(tǒng)均能顯示內(nèi)存分配的狀態(tài)和參數(shù)變化情況。最先適應(yīng)法是分配時從表頭指針開始查找可利用空間表，將找到的第一個大小不小于“請求”的空閑塊的一部分分配給用戶。最先適應(yīng)算法要求可用表或自由鏈接按起始地址遞增的次序排列。該算法的最大特點(diǎn)是一旦找到大于或等于所要求內(nèi)存長度的分區(qū)，則搜索結(jié)束。最佳適應(yīng)算法將可利用空間表中一個大小不小于“請求”且最接近“請求”的空閑塊的一部分分配給用戶。最差適應(yīng)算法將可利用空間表中一個大小不小于“請求”且是鏈表中最大的空閑塊的一部分分配給用戶。該函數(shù)主要實(shí)現(xiàn)第一種算法，當(dāng)某用戶請求N字節(jié)內(nèi)存，分配器遍歷空閑塊鏈表以尋找一塊足夠大的內(nèi)存塊。如果內(nèi)存塊的內(nèi)存部分與請求的內(nèi)存大小相同，則將此內(nèi)存塊從鏈表中移除同時返回一個指向此內(nèi)存塊內(nèi)存部分的指針。如果內(nèi)存部分的大小大于所需要的內(nèi)存，分割此塊內(nèi)存為兩部分，一個是申請的大小，另一個是剩余的大小。然后將分配給用戶的那塊內(nèi)存?zhèn)鹘o用戶，并將剩下的那塊（如果有的話）返回到鏈表上。可將最先適應(yīng)法定義為0，最壞適應(yīng)法定義為1，最佳適應(yīng)法定義為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:......}}在實(shí)際的算法實(shí)現(xiàn)當(dāng)中，還應(yīng)考慮在回收用戶釋放的內(nèi)存塊后對內(nèi)存空間的重新組織，合并連續(xù)的內(nèi)存塊，即“節(jié)點(diǎn)合并”的問題。因?yàn)橄到y(tǒng)在不斷的分配和回收過程中，使得大的空閑塊逐漸被分割成小的占用塊，然后又重新成為空閑塊被系統(tǒng)回收，如此反復(fù)，地址相鄰的兩塊空閑塊卻分別作為鏈表中的節(jié)點(diǎn)存在，導(dǎo)致出現(xiàn)較大的用戶“請求”時，雖然有足夠的空閑空間，但是他們分布在多個空閑塊內(nèi)，分配無法進(jìn)行。為了使內(nèi)存空間得到更有效的利用，就要求在回收內(nèi)存塊后對內(nèi)存空間進(jìn)行重新組織，合并連續(xù)的內(nèi)存空間，最大限度地滿足將來的分配需求。下面就來看一下如何來實(shí)現(xiàn)這一功能。

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

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

void mem_free(void*zone,size_t size)

{//可設(shè)計(jì)一些需要的指針變量;//尋找在占用塊鏈表中要釋放的內(nèi)存塊;//將要釋放的內(nèi)存塊從占用塊的鏈表中刪除;//插入新的空閑塊到空閑塊鏈表中，同時要進(jìn)行適當(dāng)?shù)暮喜?//1.前面是否有空閑可合并://2.合并后面的空閑塊:}

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

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

3　驗(yàn)證（如何運(yùn)行所編寫的函數(shù)）

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

動態(tài)存儲管理的算法是操作系統(tǒng)設(shè)計(jì)的一個重要問題，學(xué)習(xí)和研究它們能夠?yàn)樵诓僮飨到y(tǒng)等方面的深入研究提供一定的理論依據(jù)和實(shí)踐感知。通過了解諸多算法的基本思想和應(yīng)用環(huán)境，也使得學(xué)生更加深入地了解軟件在運(yùn)行時計(jì)算機(jī)內(nèi)存資源如何高效、快速地分配，并且在適當(dāng)?shù)臅r候釋放和回收內(nèi)存資源。

參考文獻(xiàn)：

［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

文獻(xiàn)標(biāo)識碼：A

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

收稿日期：2016-01-16

作者簡介：孫溫穩(wěn)（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