可变分区分配与回收,哈尔滨理工大学 操作系统课程设计报告

1、. 理工大学课程设计操作系统题目： 可变分区分配与回收 首次适应算法班级： 计算机科学与技术学院 计算机系10-8班姓名：旭冬 1004010810指导教师：高雪瑶系主任： 林克正 2013年03月05日.PAGE II- -. 目 录 TOC o 1-3 h z u HYPERLINK l _Toc3497390001可变分区分配与回收 PAGEREF _Toc349739000 h 1HYPERLINK l _Toc3497390011.1 题目分析 PAGEREF _Toc349739001 h 1HYPERLINK l _Toc3497390021.2 数据构造 PAGEREF _To

2、c349739002 h 1HYPERLINK l _Toc3497390031.3 流程图 PAGEREF _Toc349739003 h 1HYPERLINK l _Toc3497390051.4 设计结论和心得 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 局部数据构造 PAGEREF _Toc349739009 h 4HYPERLINK l _Toc3497390102.4 流程图 PAGEREF _Toc349739010 h 4HYPERLINK l _Toc3497390112.5 以实例说明运行过程 PAGEREF _Toc349739011 h 5.- PAGE 10 -. 1可变分区分配与回收题目分析首次适应算法first fit简称FF。FF算法要求空间分区链以地址递增的次序。再分配存时，从链首开场顺序查找，直至找到一个大小能满足要求的空闲分区为

4、止，然后再按照作业的大小，从该分区中划出一款存空间分配给请求者，余下的空闲分区仍留在空闲链中。假设找不到一个能满足要求的分区，则此次存分配失败。数据构造structfloat address; /*空闲区起始地址*/float length; /*空闲区长度，单位为字节*/int flag; /*空闲区表登记栏标志，用0表示空栏目，用1表示未分配*/free_tablem; /*空闲区表*/structfloat address; /*已分分区起始地址*/ float length; /*已分分区长度，单位为字节*/ int flag; /*已分配区表登记栏标志，用0表示空栏目*/used_t

5、ablen; /*已分配区表*/流程图图1设计结论和心得通过课程设计得到如下结论： 设计本课程前，感觉本课程并不是则难，很容易下手，因为主要也就是写出回收主程序、存分配主程序就行了。但是真正实施起来确非常困难。 首先，必须解决动态输入构造空闲区表的问题。刚开场的时候，我们把其他的程序都写出来了，却忘了课题还要求动态输入构造空闲区表。于是我们又花了很大的力气才实现动态输入构造空闲区表，即：可以根据自己的需要，从键盘输入空闲区表的块数，并输入每块空闲区表的大小及首地址。 其次，需要解决的是首次适应算法和最正确适应算法之间的转制问题。我们做完首次适应算法的程序后不知道该从什么地方着手写最正确适应算法

6、。最后过了几天，才想到，原来只需在首次适应算法中，每次申请空闲区前先对空闲区从小到大排序即可。 第三个难题就是解决回收算法的问题。回收算法可以说是本实验最难实现的算法，因为它有四种不同的情况。刚开场我们只考虑了三种情况，即：要回收的区域没有与之相邻接的空闲区。要回收区域有上邻与要回收区域相邻的上面有空闲区。要回收的区域有下邻与要回收的区域相邻的下面有空闲区。当我们满怀欣喜感觉本课程设计已经完成的时候却发现，程序运行的时候，对于一个刚分配好的空闲区，如果有三个相邻的作业可以同时在此空闲区申请到存，并全并回收此三个作业后，此空闲区会被分割成两个空闲区显示。这时我们才意识到少考虑了一种情况：要回收的

7、区域有上邻而且有下邻。我们又不得不再次修改程序。 就这样，在写出大体程序后，我们前后大大小小修改了十屡次，最后修改好的程序完全符合课程设计要求，我们的课程设计终于成功了！. 2 Linu*代码分析功能说明tun/tap 驱动程序实现了虚拟网卡的功能，tun表示虚拟的是点对点设备，tap表示虚拟的是以太网设备，这两种设备针对网络包实施不同的封装。利用tun/tap 驱动，可以将tcp/ip协议栈处理好的网络分包传给任何一个使用tun/tap驱动的进程，由进程重新处理后再发到物理链路中。在linu* 2.4核版本及以后版本中，tun/tap驱动是作为系统默认预先编译进核中的。接口说明做为虚拟网卡驱

8、动，Tun/tap驱动程序的数据接收和发送并不直接和真实网卡打交道，而是通过用户态来转交。在linu*下，要实现核心态和用户态数据的交互，有多种方式：可以通用socket创立特殊套接字，利用套接字实现数据交互；通过proc文件系统创立文件来进展数据交互；还可以使用设备文件的方式，访问设备文件会调用设备驱动相应的例程，设备驱动本身就是核心态和用户态的一个接口，Tun/tap驱动就是利用设备文件实现用户态和核心态的数据交互。从构造上来说，Tun/tap驱动并不单纯是实现网卡驱动，同时它还实现了字符设备驱动局部。以字符设备的方式连接用户态和核心态。下面是示意图：Tun/tap 驱动程序中包含两个局部

9、，一局部是字符设备驱动，还有一局部是网卡驱动局部。利用网卡驱动局部接收来自TCP/IP协议栈的网络分包并发送或者反过来将接收到的网络分包传给协议栈处理，而字符驱动局部则将网络分包在核与用户态之间传送，模拟物理链路的数据接收和发送。Tun/tap驱动很好的实现了两种驱动的结合。局部数据构造struct tun_struct char name8; /设备名unsigned long flags; /区分tun和tap设备struct fasync_struct *fasync; /文件异步通知构造wait_queue_head_t read_wait; /等待队列struct net_devic

10、edev; /linu* 抽象网络设备构造struct sk_buff_head t*q; /网络缓冲区队列 struct net_device_statsstats; /网卡状态信息构造;struct net_device构造是linu*核提供的统一网络设备构造，定义了系统统一的访问接口。Tun/tap驱动中实现的网卡驱动的处理例程：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)；/数据包发送例程 static void tun_net_mclist(struct net_device *dev)；/设置多点传输的地址链表 static struct net_device_stats *tun_net_stats(struct net_device *dev)；/当一个应用程序需要知道网络接口的一些统计数据时，可调用该函数，如ifconfig、netstat等。 int tun_net_init(struct net_device *dev)；/网络设备初始例程 字符设备局部：在Linu*中，字符

12、设备和块设备统一以文件的方式访问，访问它们的接口是统一的，都是使用open()函数翻开设备文件或普通文件，用read()和write()函数实现读写文件等等。Tun/tap驱动定义的字符设备的访问接口如下：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() 函数将该驱动注册为非标准字符设备驱动，提供字符设备具有的各种程序接口。代码摘自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;当翻开一个tun/tap设备时，open 函数将调用tun_chr_open()函数，其中将完成一些重要的初始化过程，包括设置网卡驱动局部的初始化函数以及网络缓冲区链表的初始化和等待队列的初始化。Tun/tap驱动中网卡的注册被嵌入了字符驱动的ioctl例程中，它是通过对字符设备文件描述符利用自定义的ioctl设置标志 TUNSETIFF完成网卡的注册的。流程图五：以实例说明运行过程Tun/tap驱动程序中包含两个局部，一局部是字符设备驱动，还有一局部是网卡驱动局部。利用网卡驱动局部接收来自TCP/IP

15、协议栈的网络分包并发送或者反过来将接收到的网络分包传给协议栈处理，而字符驱动局部则将网络分包在核与用户态之间传送，模拟物理链路的数据接收和发送。Tun/tap驱动很好的实现了两种驱动的结合。下面是定义的tun/tap设备构造：struct tun_struct char name8; /设备名 unsigned long flags; /区分tun和tap设备 struct fasync_struct *fasync; /文件异步通知构造 wait_queue_head_t read_wait; /等待队列 struct net_device dev; /linu* 抽象网络设备构造 stru

16、ct sk_buff_head t*q; /网络缓冲区队列 struct net_device_stats stats; /网卡状态信息构造;struct net_device构造是linu*核提供的统一网络设备构造，定义了系统统一的访问接口。Tun/tap驱动中实现的网卡驱动的处理例程：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