《操作系统》课程设计指导书
Course Work of Operating System 本指导书中包含5个题目，每个小组选择一个题目。

小组人数最多为4人，也可以1个人为1组。

上机时间安排为：每周二7~8节在软件实验室。

总学时为“两周”，分散到整个学期完成。

在2004年12月31日（周五）之前上交课程设计报告并拷贝电子文档及源程序到615的机器上。

每个题目的实验提示是互相启发的。

另外实验提示只是提示，你可以有自己的实现方法和理解，但必须在报告中清楚地说明。

你在实现复杂原理时可以也必须做简化假设。

数据结构以你自设的数组或链表居多。

题目一页面置换算法的模拟实现和计算命中率
一、课程设计目的
通过请求页式管理方式中页面置换算法的模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理中的页面置换算法。

二、课程设计内容
模拟实现OPT、FIFO和LRU算法，并计算命中率。

命中率= 1- 缺页率。

三、实验要求及提示
1、首先用随机数生成函数产生“指令”序列（实际上是产生指令将访问的地址序列），然后将指令序列变换成相应的页地址流，再计算不同算法下的命中率。

2、通过随机数产生一个指令序列，共产生400条。

其中50%的指令是顺序执行的（另外50%就是非顺序），且25%的指令分布在前半部地址空间，25%的指令分布在后半部地址空间。

具体的产生方法是：
1）在[0，399]之间随机选取一起点m，记录到指令地址流数组中；
2）所谓“顺序执行一条指令”，即执行地址为m+1的指令，把m+1记录下来；
3）在前半部地址空间，即[0，m+1]中随机选一数，作为新指令地址m’；
4）顺序执行一条指令，其地址为m’+1；
5）在后半部地址空间[m’+2，399]中随机选一数，作为新指令地址；
6）重复步骤1~5，直到产生400个指令地址。

3、将指令地址流变换成页地址（页号）流，简化假设为：
1）页面大小为1K；
2）用户虚存容量为40K；
3）用户内存容量为4页到40页；
4）用户虚存中，每K存放10条指令，所以那400条指令访问地址所对应的页地址（页号）流为：
指令访问地址为[0，9]的指令为第0页；指令访问地址为[10，19]的指令为第1
页；……。

按这种方式，把400条指令组织进“40页”。

4、循环运行，使用户内存容量从4到40。

计算每个内存容量下不同页面置换算法的命中率。

输出结果可以为：
[4] OPT：FIFO：LRU：
[5] OPT：FIFO：LRU：
…………
[39] OPT：FIFO：LRU：
[40] OPT：FIFO：LRU：
题目二UNIX成组链接策略的模拟实现
一、课程设计目的
通过模拟UNIX成组链接策略的实现，理解UNIX管理磁盘空闲空间的方法。

二、课程设计内容
实现UNIX管理磁盘空闲空间的方法——成组链接。

具体策略参见教材第六章。

（UNIX的成组链接例：莱昂氏UNIX源代码.pdf文件的第162页alloc(dev)和第163页free(dev,bno)过程。

另外文件系统数据结构定义在第134页struct filsys。

）
三、实验要求及提示
本题目的简化假设是：
1、设磁盘空闲块现有100块，块号就是[0，99]。

每组有10块（而不是课本中的
50块），因此盘块号栈容量也为10。

2、申请和释放块的请求由你自己随机产生（块数及假想的文件名），让你的程序
循环，发出200次请求，在前半期以申请块请求居多，在后半期以释放块请求居
多。

3、如果万一发生100块都用完的情况，就报告，且保存新产生的申请请求，直到
有新的释放请求发出。

4、每次请求完成后，列出本次请求的简要情况。

全部请求完成后，列出现在的磁
盘空间状况（空闲或已分配给哪个“文件”）。

题目三DOS的文件分配表策略的模拟实现
一、课程设计目的
通过模拟DOS的文件分配表策略的实现，理解DOS管理磁盘空闲空间和文件系统空间的方法。

二、课程设计内容
实现DOS的文件分配表策略（参见课件《北os06-文件》）和文件目录项。

三、实验要求及提示
本题目的简化假设是：
1、设可用磁盘空间总共300个簇，因此你设置的FAT数组或队列只有300项。

运行开始时全为空闲。

设一个FAT即可。

2、以文件为单位申请和释放簇（意味着创建、删除和修改文件），文件所占簇数由你自己随机产生。

你的程序应该产生至少100个文件请求，在前半期以申请请求居多，在后半期以释放请求居多。

3、你需要再设置一个文件目录项表（实际上就是一个目录文件的内容），记录文件名、起始簇号和簇数。

为简化，该目录文件为单级目录，不设子目录，且该目录文件占那300
个簇以外的簇。

4、如果万一发生300簇都用完的情况，就报告，且保存新产生的申请请求，直到有新的释放请求发出。

5、在文件请求全部结束后，列出文件目录项表中现有文件的文件名和所占簇号。

如：file1：13，24，58，76，90
题目四死锁避免——银行家算法的模拟实现
一、课程设计目的
通过模拟死锁避免的实现，加深对死锁避免，系统安全状态等的理解。

二、课程设计内容
实现死锁避免算法——银行家算法。

三、实验要求及提示
银行家算法的数据结构参见教材第八章。

本题目的简化假设是：
1、程序运行开始时，资源全部可用。

资源种类约10种，每种资源数目为1~10。

2、不断随机产生或手工输入新的“进程资源需求向量”，并填写到最大需求矩阵。

3、在各进程的最大需求数量范围内（因此需作是否超出范围的检验），为各进程随机生成或手工输入资源请求。

经银行家算法后输出系统是否安全的信息。

当一个进程的资源请求全部发完后，认为它结束。

题目五死锁定理——资源分配图化简法的模拟实现
一、课程设计目的
通过模拟资源分配图化简法的实现，加深对死锁状态判定的理解。

二、课程设计内容
实现死锁定理——资源分配图的化简。

（注：此题目不能被3人或4人小组选做）
三、实验要求及提示
资源分配图化简法参见教材。

本题目的简化假设是：
1、程序开始运行时，随机生成资源分配图的内容。

2、每种资源为一个资源类，包含的实例数为1~10。

进程数为20左右。

3、输出内容为：
1）资源分配图中的有向边内容和环路。

不要求程序输出图形，但要求在撰写课程设计报告时，用word画出图形（同时把程序输出的有向边内容列出）。

2）化简后，输出是否死锁的信息。