可變分區(qū)分配與回收,哈爾濱理工大學(xué) 操作系統(tǒng)課程設(shè)計報告

哈爾濱理工大學(xué)課程設(shè)計（操作系統(tǒng)）題目： 可變分區(qū)分配與回收 （首次適應(yīng)算法）班級： 計算機科學(xué)與技術(shù)學(xué)院 計算機系10-8班姓名：劉旭冬 1004010810指導(dǎo)教師：高雪瑤系主任： 林克正 2013年03月05日 目 錄1可變分區(qū)分配與回收11.1 題目分析11.2 數(shù)據(jù)結(jié)構(gòu)11.3 流程圖11.4 設(shè)計結(jié)論和心得22 Linux代碼分析42.1 功能說明42.2 接口說明42.3 局部數(shù)據(jù)結(jié)構(gòu)42.4 流程圖42.5 以實例說明運行過程5第1章- 11-哈爾濱理工大學(xué)課程設(shè)計報告1可變分區(qū)分配與回收1.1 題目分析首次適應(yīng)算法（first fit）簡稱FF。FF算法要求空間分區(qū)鏈以地址遞增的次序鏈接。再分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止，然后再按照作業(yè)的大小，從該分區(qū)中劃出一款內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若找不到一個能滿足要求的分區(qū)，則此次內(nèi)存分配失敗。1.2 數(shù)據(jù)結(jié)構(gòu)structfloat address; /*空閑區(qū)起始地址*/float length; /*空閑區(qū)長度，單位為字節(jié)*/int flag; /*空閑區(qū)表登記欄標(biāo)志，用"0"表示空欄目，用"1"表示未分配*/free_tablem; /*空閑區(qū)表*/structfloat address; /*已分分區(qū)起始地址*/ float length; /*已分分區(qū)長度，單位為字節(jié)*/ int flag; /*已分配區(qū)表登記欄標(biāo)志，用"0"表示空欄目*/used_tablen; /*已分配區(qū)表*/1.3 流程圖圖11.4 設(shè)計結(jié)論和心得通過課程設(shè)計得到如下結(jié)論： 設(shè)計本課程前，感覺本課程并不是那么難，很容易下手，因為主要也就是寫出回收主程序、內(nèi)存分配主程序就行了。但是真正實施起來確非常困難。 首先，必須解決動態(tài)輸入構(gòu)造空閑區(qū)表的問題。剛開始的時候，我們把其他的程序都寫出來了，卻忘了課題還要求動態(tài)輸入構(gòu)造空閑區(qū)表。于是我們又花了很大的力氣才實現(xiàn)動態(tài)輸入構(gòu)造空閑區(qū)表，即：可以根據(jù)自己的需要，從鍵盤輸入空閑區(qū)表的塊數(shù)，并輸入每塊空閑區(qū)表的大小及首地址。 其次，需要解決的是首次適應(yīng)算法和最佳適應(yīng)算法之間的轉(zhuǎn)制問題。我們做完首次適應(yīng)算法的程序后不知道該從什么地方著手寫最佳適應(yīng)算法。最后過了幾天，才想到，原來只需在首次適應(yīng)算法中，每次申請空閑區(qū)前先對空閑區(qū)從小到大排序即可。 第三個難題就是解決回收算法的問題。回收算法可以說是本實驗最難實現(xiàn)的算法，因為它有四種不同的情況。剛開始我們只考慮了三種情況，即：1、 要回收的區(qū)域沒有與之相鄰接的空閑區(qū)。2、 要回收區(qū)域有上鄰（與要回收區(qū)域相鄰的上面有空閑區(qū)）。3、 要回收的區(qū)域有下鄰（與要回收的區(qū)域相鄰的下面有空閑區(qū)）。當(dāng)我們滿懷欣喜感覺本課程設(shè)計已經(jīng)完成的時候卻發(fā)現(xiàn)，程序運行的時候，對于一個剛分配好的空閑區(qū)，如果有三個相鄰的作業(yè)可以同時在此空閑區(qū)內(nèi)申請到內(nèi)存，并全并回收此三個作業(yè)后，此空閑區(qū)會被分割成兩個空閑區(qū)顯示。這時我們才意識到少考慮了一種情況：要回收的區(qū)域有上鄰而且有下鄰。我們又不得不再次修改程序。 就這樣，在寫出大體程序后，我們前后大大小小修改了十多次，最后修改好的程序完全符合課程設(shè)計要求，我們的課程設(shè)計終于成功了！2 Linux代碼分析一、 功能說明tun/tap 驅(qū)動程序?qū)崿F(xiàn)了虛擬網(wǎng)卡的功能，tun表示虛擬的是點對點設(shè)備，tap表示虛擬的是以太網(wǎng)設(shè)備，這兩種設(shè)備針對網(wǎng)絡(luò)包實施不同的封裝。利用tun/tap 驅(qū)動，可以將tcp/ip協(xié)議棧處理好的網(wǎng)絡(luò)分包傳給任何一個使用tun/tap驅(qū)動的進(jìn)程，由進(jìn)程重新處理后再發(fā)到物理鏈路中。在linux 2.4內(nèi)核版本及以后版本中，tun/tap驅(qū)動是作為系統(tǒng)默認(rèn)預(yù)先編譯進(jìn)內(nèi)核中的。二、 接口說明做為虛擬網(wǎng)卡驅(qū)動，Tun/tap驅(qū)動程序的數(shù)據(jù)接收和發(fā)送并不直接和真實網(wǎng)卡打交道，而是通過用戶態(tài)來轉(zhuǎn)交。在linux下，要實現(xiàn)核心態(tài)和用戶態(tài)數(shù)據(jù)的交互，有多種方式：可以通用socket創(chuàng)建特殊套接字，利用套接字實現(xiàn)數(shù)據(jù)交互；通過proc文件系統(tǒng)創(chuàng)建文件來進(jìn)行數(shù)據(jù)交互；還可以使用設(shè)備文件的方式，訪問設(shè)備文件會調(diào)用設(shè)備驅(qū)動相應(yīng)的例程，設(shè)備驅(qū)動本身就是核心態(tài)和用戶態(tài)的一個接口，Tun/tap驅(qū)動就是利用設(shè)備文件實現(xiàn)用戶態(tài)和核心態(tài)的數(shù)據(jù)交互。從結(jié)構(gòu)上來說，Tun/tap驅(qū)動并不單純是實現(xiàn)網(wǎng)卡驅(qū)動，同時它還實現(xiàn)了字符設(shè)備驅(qū)動部分。以字符設(shè)備的方式連接用戶態(tài)和核心態(tài)。下面是示意圖：Tun/tap 驅(qū)動程序中包含兩個部分，一部分是字符設(shè)備驅(qū)動，還有一部分是網(wǎng)卡驅(qū)動部分。利用網(wǎng)卡驅(qū)動部分接收來自TCP/IP協(xié)議棧的網(wǎng)絡(luò)分包并發(fā)送或者反過來將接收到的網(wǎng)絡(luò)分包傳給協(xié)議棧處理，而字符驅(qū)動部分則將網(wǎng)絡(luò)分包在內(nèi)核與用戶態(tài)之間傳送，模擬物理鏈路的數(shù)據(jù)接收和發(fā)送。Tun/tap驅(qū)動很好的實現(xiàn)了兩種驅(qū)動的結(jié)合。三、 局部數(shù)據(jù)結(jié)構(gòu)struct tun_struct char name8; /設(shè)備名unsigned long flags; /區(qū)分tun和tap設(shè)備struct fasync_struct *fasync; /文件異步通知結(jié)構(gòu)wait_queue_head_t read_wait; /等待隊列struct net_devicedev; /linux 抽象網(wǎng)絡(luò)設(shè)備結(jié)構(gòu)struct sk_buff_head txq; /網(wǎng)絡(luò)緩沖區(qū)隊列 struct net_device_statsstats; /網(wǎng)卡狀態(tài)信息結(jié)構(gòu);struct net_device結(jié)構(gòu)是linux內(nèi)核提供的統(tǒng)一網(wǎng)絡(luò)設(shè)備結(jié)構(gòu)，定義了系統(tǒng)統(tǒng)一的訪問接口。Tun/tap驅(qū)動中實現(xiàn)的網(wǎng)卡驅(qū)動的處理例程： static int tun_net_open(struct net_device *dev)； static int tun_net_close(struct net_device *dev)； static int tun_net_xmit(struct sk_buff *skb, struct net_device *dev)；/數(shù)據(jù)包發(fā)送例程 static void tun_net_mclist(struct net_device *dev)；/設(shè)置多點傳輸?shù)牡刂锋湵?static struct net_device_stats *tun_net_stats(struct net_device *dev)；/當(dāng)一個應(yīng)用程序需要知道網(wǎng)絡(luò)接口的一些統(tǒng)計數(shù)據(jù)時，可調(diào)用該函數(shù)，如ifconfig、netstat等。 int tun_net_init(struct net_device *dev)；/網(wǎng)絡(luò)設(shè)備初始例程 字符設(shè)備部分： 在Linux中，字符設(shè)備和塊設(shè)備統(tǒng)一以文件的方式訪問，訪問它們的接口是統(tǒng)一的，都是使用open()函數(shù)打開設(shè)備文件或普通文件，用read()和write()函數(shù)實現(xiàn)讀寫文件等等。Tun/tap驅(qū)動定義的字符設(shè)備的訪問接口如下：static struct file_operations tun_fops = owner: THIS_MODULE, llseek: tun_chr_lseek, read tun_chr_read, write: tun_chr_write, poll: tun_chr_poll, ioctl: tun_chr_ioctl, open: tun_chr_open, release: tun_chr_close, fasync: tun_chr_fasync ; 在內(nèi)核中利用misc_register() 函數(shù)將該驅(qū)動注冊為非標(biāo)準(zhǔn)字符設(shè)備驅(qū)動，提供字符設(shè)備具有的各種程序接口。代碼摘自linux-2.4.20linux-2.4.20driversnettun.cstatic struct miscdevice tun_miscdev= TUN_MINOR, "net/tun", &tun_fops;int _init tun_init(void)if (misc_register(&tun_miscdev) printk(KERN_ERR "tun: Can't register misc device %dn", TUN_MINOR);return -EIO;return 0;當(dāng)打開一個tun/tap設(shè)備時，open 函數(shù)將調(diào)用tun_chr_open()函數(shù)，其中將完成一些重要的初始化過程，包括設(shè)置網(wǎng)卡驅(qū)動部分的初始化函數(shù)以及網(wǎng)絡(luò)緩沖區(qū)鏈表的初始化和等待隊列的初始化。Tun/tap驅(qū)動中網(wǎng)卡的注冊被嵌入了字符驅(qū)動的ioctl例程中，它是通過對字符設(shè)備文件描述符利用自定義的ioctl設(shè)置標(biāo)志 TUNSETIFF完成網(wǎng)卡的注冊的。四、 流程圖五：以實例說明運行過程Tun/tap驅(qū)動程序中包含兩個部分，一部分是字符設(shè)備驅(qū)動，還有一部分是網(wǎng)卡驅(qū)動部分。利用網(wǎng)卡驅(qū)動部分接收來自TCP/IP協(xié)議棧的網(wǎng)絡(luò)分包并發(fā)送或者反過來將接收到的網(wǎng)絡(luò)分包傳給協(xié)議棧處理，而字符驅(qū)動部分則將網(wǎng)絡(luò)分包在內(nèi)核與用戶態(tài)之間傳送，模擬物理鏈路的數(shù)據(jù)接收和發(fā)送。Tun/tap驅(qū)動很好的實現(xiàn)了兩種驅(qū)動的結(jié)合。下面是定義的tun/tap設(shè)備結(jié)構(gòu)：struct tun_struct char name8; /設(shè)備名 unsigned long flags; /區(qū)分tun和tap設(shè)備 struct fasync_struct *fasync; /文件異步通知結(jié)構(gòu) wait_queue_head_t read_wait; /等待隊列 struct net_device dev; /linux 抽象網(wǎng)絡(luò)設(shè)備結(jié)構(gòu) struct sk_buff_head txq; /網(wǎng)絡(luò)緩沖區(qū)隊列 struct net_device_stats stats; /網(wǎng)卡狀態(tài)信息結(jié)構(gòu);struct net_device結(jié)構(gòu)是linux內(nèi)核提供的統(tǒng)一網(wǎng)絡(luò)設(shè)備結(jié)構(gòu)，定義了系統(tǒng)統(tǒng)一的訪問接口。Tun/tap驅(qū)動中實現(xiàn)的網(wǎng)卡驅(qū)動的處理例程：static int tun_net_open(struct net_device *dev)；static int tun_net_close(struct net_device *dev)；static int tun_net_xmit(struct sk_buff *skb, struct net_device *dev)；/數(shù)據(jù)包發(fā)送例程static void tun_net_mclist(struct net_device *dev)；/設(shè)置多點傳輸?shù)牡刂锋湵韘tatic struct net_device_stats *tun_net_stats(struct net_device *dev)；/當(dāng)一個應(yīng)用程序需要知道網(wǎng)絡(luò)接口的一些統(tǒng)計數(shù)據(jù)時，可調(diào)用該函數(shù)，如ifconfig、netstat等。int tun_net_init(struct net_device *dev)；/網(wǎng)絡(luò)設(shè)備初始例程