DOC《《操作系统》课程设计指导书》

《操作系统》课程设计指导书 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%的指令分布在后半部地址空间.具体的产生方法是: 在[0,399]之间随机选取一起点m,记录到指令地址流数组中;

所谓"顺序执行一条指令",即执行地址为m+1的指令,把m+1记录下来;

在前半部地址空间,即[0,m+1]中随机选一数,作为新指令地址m';

顺序执行一条指令,其地址为m'+1;

在后半部地址空间[m'+2,399]中随机选一数,作为新指令地址;

重复步骤1~5,直到产生400个指令地址.

3、将指令地址流变换成页地址(页号)流,简化假设为: 页面大小为1K;

用户虚存容量为40K;

用户内存容量为4页到40页;

用户虚存中,每K存放10条指令,所以那400条指令访问地址所对应的页地址(页号)流为: 指令访问地址为[0,9]的指令为第0页;

指令访问地址为[10,19]的指令为第1页;

…….按这种方式,把400条指令组织进"40页".

4、循环运行,使用户内存容量从4到40.计算每个内存容量下不同页面置换算法的命中率.输出结果可以为: [4] OPT:0.5566 FIFO:0.4455 LRU:0.5500 [5] OPT:0.6644 FIFO:0.5544 LRU:0.5588 …… …… [39] OPT:0.9000 FIFO:0.9000 LRU:0.9000 [40] OPT:1.0000 FIFO:1.0000 LRU:1.0000 题目二 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)化简后,输出是否死锁的信息.