文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
哈尔滨理工大学
课 程 设 计
（操作系统）
题 目：
可变分区分配与回收
（首次适应算法） 班 级： 计算机科学与技术学院 计算机系 10-8班 姓 名： 刘旭冬 指导教师： 高雪瑶 系主任： 林克正
2013年03月05日
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
目 录
1可变分区分配与回收 .................................................................... 错误!未定义书签。 1.1 题目分析 ............................................................................... 错误!未定义书签。 1.2 数据结构 ............................................................................... 错误!未定义书签。 1.3 流程图 ................................................................................... 错误!未定义书签。 1.4 设计结论和心得 ................................................................... 错误!未定义书签。 2 Linux代码分析 ............................................................................. 错误!未定义书签。 2.1 功能说明 ............................................................................... 错误!未定义书签。 2.2 接口说明 ............................................................................... 错误!未定义书签。 2.3 局部数据结构 ....................................................................... 错误!未定义书签。 2.4 流程图 ................................................................................... 错误!未定义书签。 2.5 以实例说明运行过程 ........................................................... 错误!未定义书签。
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
1可变分区分配与回收
1.1 题目分析
首次适应算法（first fit）简称FF。
FF算法要求空间分区链以地址递增的次序链接。再分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止，然后再按照作业的大小，从该分区中划出一款内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若找不到一个能满足要求的分区，则此次内存分配失败。
1.2 数据结构
struct{ float address; /*空闲区起始地址*/ float length; /*空闲区长度，单位为字节*/
int flag; /*空闲区表登记栏标志，用\表示空栏目，用\表示未分配*/ }free_table[m]; /*空闲区表*/ struct{ float address; /*已分分区起始地址*/ float length; /*已分分区长度，单位为字节*/ int flag; /*已分配区表登记栏标志，用\表示空栏目*/ }used_table[n]; /*已分配区表*/
1.3 流程图
图1
1.4 设计结论和心得
通过课程设计得到如下结论：
设计本课程前，感觉本课程并不是那么难，很容易下手，因为主要也就是写出回收主程序、内存分配主程序就行了。但是真正实施起来确非常困难。
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
首先，必须解决动态输入构造空闲区表的问题。刚开始的时候，我们把其他的程序都写出来了，却忘了课题还要求动态输入构造空闲区表。于是我们又花了很大的力气才实现动态输入构造空闲区表，即：可以根据自己的需要，从键盘输入空闲区表的块数，并输入每块空闲区表的大小及首地址。
其次，需要解决的是首次适应算法和最佳适应算法之间的转制问题。我们做完首次适应算法的程序后不知道该从什么地方着手写最佳适应算法。最后过了几天，才想到，原来只需在首次适应算法中，每次申请空闲区前先对空闲区从小到大排序即可。
第三个难题就是解决回收算法的问题。回收算法可以说是本实验最难实现的算法，因为它有四种不同的情况。刚开始我们只考虑了三种情况，即： 1、要回收的区域没有与之相邻接的空闲区。
2、要回收区域有上邻（与要回收区域相邻的上面有空闲区）。 3、要回收的区域有下邻（与要回收的区域相邻的下面有空闲区）。
当我们满怀欣喜感觉本课程设计已经完成的时候却发现，程序运行的时候，对于一个刚分配好的空闲区，如果有三个相邻的作业可以同时在此空闲区内申请到内存，并全并回收此三个作业后，此空闲区会被分割成两个空闲区显示。这时我们才意识到少考虑了一种情况：要回收的区域有上邻而且有下邻。我们又不得不再次修改程序。
就这样，在写出大体程序后，我们前后大大小小修改了十多次，最后修改好的程序完全符合课程设计要求，我们的课程设计终于成功了！
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
2 Linux代码分析
一、 功能说明
tun/tap 驱动程序实现了虚拟网卡的功能，tun表示虚拟的是点对点设备，tap表示虚拟的是以太网设备，这两种设备针对网络包实施不同的封装。利用tun/tap 驱动，可以将tcp/ip协议栈处理好的网络分包传给任何一个使用tun/tap驱动的进程，由进程重新处理后再发到物理链路中。
在linux 2.4内核版本及以后版本中，tun/tap驱动是作为系统默认预先编译进内核中的。
二、 接口说明
做为虚拟网卡驱动，Tun/tap驱动程序的数据接收和发送并不直接和真实网卡打交道，而是通过用户态来转交。在linux下，要实现核心态和用户态数据的交互，有多种方式：可以通用socket创建特殊套接字，利用套接字实现数据交互；通过proc文件系统创建文件来进行数据交互；还可以使用设备文件的方式，访问设备文件会调用设备驱动相应的例程，设备驱动本身就是核心态和用户态的一个接口，Tun/tap驱动就是利用设备文件实现用户态和核心态的数据交互。
从结构上来说，Tun/tap驱动并不单纯是实现网卡驱动，同时它还实现了字符设备驱动部分。以字符设备的方式连接用户态和核心态。下面是示意图：
Tun/tap 驱动程序中包含两个部分，一部分是字符设备驱动，还有一部分是网卡驱动部分。利用网卡驱动部分接收来自TCP/IP协议栈的网络分包并发送或者反过来将接收到的网络分包传给协议栈处理，而字符驱动部分则将网络分包在内核与用户态之间传送，模拟物理链路的数据接收和发送。Tun/tap驱动很好的实现了两种驱动的结合。
可变分区分配与回收,哈尔滨理工大学操作系统课程设计报告
