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

1、. 理工大學(xué)課程設(shè)計操作系統(tǒng)題目： 可變分區(qū)分配與回收 首次適應(yīng)算法班級： 計算機科學(xué)與技術(shù)學(xué)院 計算機系10-8班姓名：旭冬 1004010810指導(dǎo)教師：高雪瑤系主任： 林克正 2013年03月05日.PAGE II- -. 目 錄 TOC o 1-3 h z u HYPERLINK l _Toc3497390001可變分區(qū)分配與回收 PAGEREF _Toc349739000 h 1HYPERLINK l _Toc3497390011.1 題目分析 PAGEREF _Toc349739001 h 1HYPERLINK l _Toc3497390021.2 數(shù)據(jù)構(gòu)造 PAGEREF _To

2、c349739002 h 1HYPERLINK l _Toc3497390031.3 流程圖 PAGEREF _Toc349739003 h 1HYPERLINK l _Toc3497390051.4 設(shè)計結(jié)論和心得 PAGEREF _Toc349739005 h 2HYPERLINK l _Toc3497390062 Linu*代碼分析 PAGEREF _Toc349739006 h 4HYPERLINK l _Toc3497390072.1 功能說明 PAGEREF _Toc349739007 h 4HYPERLINK l _Toc3497390082.2 接口說明 PAGEREF _To

3、c349739008 h 4HYPERLINK l _Toc3497390092.3 局部數(shù)據(jù)構(gòu)造 PAGEREF _Toc349739009 h 4HYPERLINK l _Toc3497390102.4 流程圖 PAGEREF _Toc349739010 h 4HYPERLINK l _Toc3497390112.5 以實例說明運行過程 PAGEREF _Toc349739011 h 5.- PAGE 10 -. 1可變分區(qū)分配與回收題目分析首次適應(yīng)算法first fit簡稱FF。FF算法要求空間分區(qū)鏈以地址遞增的次序。再分配存時，從鏈?zhǔn)组_場順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為

4、止，然后再按照作業(yè)的大小，從該分區(qū)中劃出一款存空間分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。假設(shè)找不到一個能滿足要求的分區(qū)，則此次存分配失敗。數(shù)據(jù)構(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_t

5、ablen; /*已分配區(qū)表*/流程圖圖1設(shè)計結(jié)論和心得通過課程設(shè)計得到如下結(jié)論： 設(shè)計本課程前，感覺本課程并不是則難，很容易下手，因為主要也就是寫出回收主程序、存分配主程序就行了。但是真正實施起來確非常困難。 首先，必須解決動態(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)算法

6、。最后過了幾天，才想到，原來只需在首次適應(yīng)算法中，每次申請空閑區(qū)前先對空閑區(qū)從小到大排序即可。 第三個難題就是解決回收算法的問題。回收算法可以說是本實驗最難實現(xiàn)的算法，因為它有四種不同的情況。剛開場我們只考慮了三種情況，即：要回收的區(qū)域沒有與之相鄰接的空閑區(qū)。要回收區(qū)域有上鄰與要回收區(qū)域相鄰的上面有空閑區(qū)。要回收的區(qū)域有下鄰與要回收的區(qū)域相鄰的下面有空閑區(qū)。當(dāng)我們滿懷欣喜感覺本課程設(shè)計已經(jīng)完成的時候卻發(fā)現(xiàn)，程序運行的時候，對于一個剛分配好的空閑區(qū)，如果有三個相鄰的作業(yè)可以同時在此空閑區(qū)申請到存，并全并回收此三個作業(yè)后，此空閑區(qū)會被分割成兩個空閑區(qū)顯示。這時我們才意識到少考慮了一種情況：要回收的

7、區(qū)域有上鄰而且有下鄰。我們又不得不再次修改程序。 就這樣，在寫出大體程序后，我們前后大大小小修改了十屢次，最后修改好的程序完全符合課程設(shè)計要求，我們的課程設(shè)計終于成功了！. 2 Linu*代碼分析功能說明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ā)到物理鏈路中。在linu* 2.4核版本及以后版本中，tun/tap驅(qū)動是作為系統(tǒng)默認(rèn)預(yù)先編譯進(jìn)核中的。接口說明做為虛擬網(wǎng)卡驅(qū)

8、動，Tun/tap驅(qū)動程序的數(shù)據(jù)接收和發(fā)送并不直接和真實網(wǎng)卡打交道，而是通過用戶態(tài)來轉(zhuǎn)交。在linu*下，要實現(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ù)交互。從構(gòu)造上來說，Tun/tap驅(qū)動并不單純是實現(xiàn)網(wǎng)卡驅(qū)動，同時它還實現(xiàn)了字符設(shè)備驅(qū)動局部。以字符設(shè)備的方式連接用戶態(tài)和核心態(tài)。下面是示意圖：Tun/tap 驅(qū)動程序中包含兩個局部

9、，一局部是字符設(shè)備驅(qū)動，還有一局部是網(wǎng)卡驅(qū)動局部。利用網(wǎng)卡驅(qū)動局部接收來自TCP/IP協(xié)議棧的網(wǎng)絡(luò)分包并發(fā)送或者反過來將接收到的網(wǎng)絡(luò)分包傳給協(xié)議棧處理，而字符驅(qū)動局部則將網(wǎng)絡(luò)分包在核與用戶態(tài)之間傳送，模擬物理鏈路的數(shù)據(jù)接收和發(fā)送。Tun/tap驅(qū)動很好的實現(xiàn)了兩種驅(qū)動的結(jié)合。局部數(shù)據(jù)構(gòu)造struct tun_struct char name8; /設(shè)備名unsigned long flags; /區(qū)分tun和tap設(shè)備struct fasync_struct *fasync; /文件異步通知構(gòu)造wait_queue_head_t read_wait; /等待隊列struct net_devic

10、edev; /linu* 抽象網(wǎng)絡(luò)設(shè)備構(gòu)造struct sk_buff_head t*q; /網(wǎng)絡(luò)緩沖區(qū)隊列 struct net_device_statsstats; /網(wǎng)卡狀態(tài)信息構(gòu)造;struct net_device構(gòu)造是linu*核提供的統(tǒng)一網(wǎng)絡(luò)設(shè)備構(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_*mit(struct s

11、k_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è)備局部：在Linu*中，字符

12、設(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: t

13、un_chr_close, fasync: tun_chr_fasync ; 在核中利用misc_register() 函數(shù)將該驅(qū)動注冊為非標(biāo)準(zhǔn)字符設(shè)備驅(qū)動，提供字符設(shè)備具有的各種程序接口。代碼摘自linu*-2.4.20linu*-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: Cant register mis

14、c 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

15、協(xié)議棧的網(wǎng)絡(luò)分包并發(fā)送或者反過來將接收到的網(wǎng)絡(luò)分包傳給協(xié)議棧處理，而字符驅(qū)動局部則將網(wǎng)絡(luò)分包在核與用戶態(tài)之間傳送，模擬物理鏈路的數(shù)據(jù)接收和發(fā)送。Tun/tap驅(qū)動很好的實現(xiàn)了兩種驅(qū)動的結(jié)合。下面是定義的tun/tap設(shè)備構(gòu)造：struct tun_struct char name8; /設(shè)備名 unsigned long flags; /區(qū)分tun和tap設(shè)備 struct fasync_struct *fasync; /文件異步通知構(gòu)造 wait_queue_head_t read_wait; /等待隊列 struct net_device dev; /linu* 抽象網(wǎng)絡(luò)設(shè)備構(gòu)造 stru

16、ct sk_buff_head t*q; /網(wǎng)絡(luò)緩沖區(qū)隊列 struct net_device_stats stats; /網(wǎng)卡狀態(tài)信息構(gòu)造;struct net_device構(gòu)造是linu*核提供的統(tǒng)一網(wǎng)絡(luò)設(shè)備構(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_*mit(struct sk_buff *skb, struct net_dev