操作系统试验指导书

1、操作系统实验指导书李玲娟李刚编写李玲娟审核南京中医药大学 信息技术学院2005年10月编者说明软件技术是操作系统最重要的计算机系统软件，同时也是计算机科学与技术专业的一 门核心专业基础课，其发展极为迅速。学习计算机软件技术，特别是计算机操作系统技术，除 了需要刻苦努力外，还需要掌握软件和操作系统的原理与设计技巧。这些原理与技巧可以说是 计算机界的前辈们一代接一代不停歇的努力所留下的知识与智慧的结晶，学习和掌握它们对于 激发自己的创造力和想象力是很有帮助的。如何学习和掌握操作系统技术的原理与实际技巧呢？除了听课和读书之外，最好的方法就 是在实践中练习，通过自己模拟设计操作系统的原理实验，可以培养

2、程序设计的方法和技巧， 提高编制和理解清晰、合理、可读性好的系统程序的能力，加深对操作系统课程的理解。使自 身更好的掌握操作系统的基本概念、基本原理及基本功能，从而具有分析实际操作系统的基本 能力，深入直观的理解操作系统使用的各类算法。操作系统实验指导书是针对这门课的实验编写的，书中设计了四个重要的操作系统原 理实验， 包括进程调度、 分区式存储管理、 虚拟存储管理和文件管理。 四个实验难易层次分明， 重点突出， 其中实验一 （进程调度 ）和实验二 （分区式存储管理 ）为设计性实验， 重在培养理论原理 应用于实践的设计能力， 而实验三 （虚拟存储管理 ）和实验四 （文件管理 ）为验证性实验，

3、重在验证 教材中的理论原理。所有实验共 18 学时，均采用 C 语言作为编程语言模拟设计完成相关程序。本书编写中，参考了西安电子科技大学、清华大学的操作系统相关图书资料。本书由信息技术学院副院长李玲娟和应用教研室李刚两位教师编写， 由李玲娟副教授审核。 南京中医药大学教务处给予了指导和大力帮助，在此表示衷心的感谢！限于编者的水平，难免有疏漏与错误，敬请读者批评指正。李玲娟 李刚2005年 10月 12日实验一 进程调度 1实验二 分区式存储管理 4.实验三 虚拟存储管理 8实验四 文件管理 1.1实验一进程调度实验性质：设计建议学时：6学时实验目的：通过这次实验，加深对进程概念的理解，进一步掌

4、握进程状态的转变、进程调度的策略及对系统性能的评价方法。预习内容：阅读教材计算机操作系统第二章和第三章，掌握进程管理及调度相关概念和原理。基本实验内容：设计程序模拟进程的轮转法调度过程。假设初始状态为：有n个进程处于就绪状态，有个进程处于阻塞状态。 采用轮转法进程调度算法进行调度 （调度过程中，假设处于执行状态的进 程不会阻塞），且每过t个时间片系统释放资源，唤醒处于阻塞队列队首的进程。程序要求如下：1）.输出系统中进程的调度次序；2）.计算CPU利用率。实现提示：用C语言实现提示：1 ）程序中进程可用 PCB表示，其类型描述如下：struct PCB_type char name ;进程名i

5、ntstate ;/进程状态2表示“执行”状态1表示“就绪”状态0表示“阻塞”状态int cpu_time ;/运行需要的CPU时间（需运行的时间片个数）2）设置两个队列，将处于“就绪”状态的进程PCB挂在队列ready中；将处于“阻塞”状态的进程PCB挂在队列blocked中。 队列类型描述如下：struct QueueNodestruct PCB_type PCB; Struct QueueNode *next;/ready队列队首指针 /ready队列队尾指针 /blocked队列队首指针并设全程量：struct QueueNode *ready_head=NULL, *ready_ta

6、il=NULL , *blocked_head=NULL,*blocked_tail=NULL;/blocked队列队尾指针3)设计子程序：start_state(); dispath(); calculate。；实验要求：/读入假设的数据，设置系统初始状态/模拟调度计算CPU利用率1）上机前认真使用 C语言编写好程序，采用Turbo C作为编译环境;2）上机时独立调试程序3）根据具体实验要求，填写好实验报告（包括思想、源程序、实例运行结果） 测试用数据：n=2 m=3t=5dispath()算法流程图:beginuse_cpu=0 x=0 unuse_cpu=0/*use_cpu中记录CPU

7、运行时间/*unuse_cpu中记录CPU空闲时间是是ready 队列不空或blocked队列不空ready队列不空p 取ready队首元素 p->PCB.state 置"运行” 输出 p->PCB.name p->PCB.cpu_time- use_cpu+endunuse_cpu+释放p否p->PCB.cpu timep入ready队列队尾曰 是x+x=t是blocked 队首进程入 ready队列队尾；x=0实验二分区式存储管理实验性质：设计建议学时：6实验目的：通过这次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。预习内容：阅读教材

8、计算机操作系统第四章，掌握存储器管理相关概念和原理。实验内容：设计程序模拟内存的动态分区法存储管理。内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分配，内存回收时假定不做与相邻空闲区的合并。假定系统的内存共 640K，初始状态为操作系统本身占用64K。在t1时间之后，有作业 A、B、C、D分别请求8K、16K、64K、124K的内存空间；在 t2时间之后，作业 C完成；在t3时间之后，作业 E请求50K的内存空间；在t4时间之后，作业 D完成。要求编程序分别输出 t1、t2、t3、t4时刻内存的空闲区的状态。实现提示（C语言）：1.程序中自由链队列的结点类型可描述如下:st

9、ruct freelinkint len, address; /* len为分区长度/* address为分区起始地址struct freelink *next;内存占用区用链表描述，其结点类型描述如下： struct busylinkchar name; /*作业或进程名int len , address;name=' S表示OS占用struct busylink *next; 并设全程量：struct freelink struct busylink*free_head=NULL; *busy_head=NULL,2.设计子函数：void start(void);*busy_tai

10、l=NULL ;/*设置系统初始状态*/自由链队列（带头结点）队首指针 占用区队列队（带头结点）首指针/占用区队列队尾指针 struct freelink * p;struct busylink *q;free_head=(struct freelink*)malloc(sizeof(structfreelin k);free_head->next=NULL; /创建自由链头结点 busy_head=busy_tail=(structbusylink*)malloc(sizeof(structbusylink);busy_head->next=NULL; /创建占用链头结点 p=(

11、 struct freelink *)malloc(sizeof(struct freelin k); p->address=64;p->len=640-64;( OS 占用了 64K)p->next=NULL;free_head->next=p;q=( struct busylink *)malloc(sizeof(struct busylink); q->name=' S' ;* S表示操作系统占用*/q->len=64; q->address=0; q->next=NULL; busy_head->next=q; bu

12、sy_tail=q;卄void requireMemo(char name, int require); /* 模拟内存分酉己 */ void freeMemo(char name); /* 模拟内存回收 */void past(int time); /* 模拟系统过了 time 时间 */void printlink(); /*输出内存空闲情况(自由链的结点)*/3.设计主函数：main() start();past(t1);requireMemo( A ,8XequireMemo( B' ,16); requireMemo( C' ,64); requireMemo( D&

13、#39; ,124);printlink();past(t2);freeMemo( C'); printlink();past(t3); requireMemo( E' ,50);printlink(); freeMemo( D'); printlink();实验要求:4）上机前认真使用 C语言编写好程序，采用 Turbo C作为编译环境；5）上机时独立调试程序6）根据具体实验要求，填写好实验报告（包括思想、源程序、实例运行结果）requireMemo(char name, int require)流程图如下:freeMemo(char name)流程图如下:实验三虚拟

14、存储管理实验性质：验证建议学时：3实验目的：存储管理的主要功能之一是合理的分配空间。请求页式管理是一种常用的虚拟存储管 理技术。本实验的目的是请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术 的特点，掌握请求页式存储管理的页面置换方法。预习内容：阅读教材计算机操作系统第四章，掌握存储器管理相关概念和原理。实验内容：（1） 通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 、50%的指令是顺序执行的； 、25%的指令是均匀分布在前地址部分； 、25%的指令是均匀分布在后地址部分。 具体的实施方法是： 在0,319的指令地址之间随机选取一起点m; 顺序执行一条指令，即

15、执行地址为m+1的指令； 在前地址0,m+1中随机选取一条指令并执行，该指令的地址为m ； 顺序执行一条指令，其地址为m +i； 在后地址m' +2,319中随机选取一条指令并执行； 重复上述步骤，直至执行320次指令。（2）将指令序列变换成页地址流 设：页面大小为1K ； 用户内存容量为 4页到32页； 用户虚存容量为32K ；在用户虚存中，按每 K存放10条指令排列虚存地址，即 320条指令在虚存中的存放 方式为：第0条第9条指令为第0页（对应的虚存地址为0，9）；第10条第19条指令为第1页（对应的虚存地址为10，19）；第310条第319条指令为第31页（对应的虚存地址为310

16、, 319）； 按以上方式，用户指令可组成32页。（3）计算并输出下述各种算法在不同的内存容量下的缺页率。 先进先出的算法（FIFO）; 最近最少使用算法（LRR）； 最佳淘汰法（OPT）:先淘汰最不常用的页地址； 最少访问页面算法（LFR）； 最近不经常使用算法（NUR ）。其中和为选择内容。缺页率=（页面失效次数）/ （页地址流长度） 在本实验中，页地址流的长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。（4）随机数产生办法关于随机数产生办法，可以使用系统提供函数rand（）,分别进行初始化和产生随机数。例如：ran d（）;语句可初始化的一个随机数；a0=

17、10*ra nd（）/32767*319+1;a1=10*ra nd（）/32767*a0;语句可用来产生 a0与a1中的随机数。实验指导1、数据类型定义（1 ）页面类型typedef struct int pn ,pfn,counter,time;pi_type；/*pn为页号，pfn为页面号，counter为一个周期内访问该页面次数，time为访问时间。（2）页面控制结构pfc_structint pn , pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp,*freepf_

18、head,*busypf_head;pfc_type *busypf_tail;/*pfctotal_vp定义用户进程虚页控制结构*freepf_head为空页面头指针*busypf_head为忙页面头指针*busypf_tail为忙页面尾指针2、函数定义（1）void initialize（ ）;/*初始化函数，给每个相关的页面赋值（2）voidFIFO（ ）;/*计算使用FIFO算法时的缺页率（3）voidLRU（ ）;/*计算使用LRU算法时的缺页率（4）voidOPT（ ）;/*计算使用OPT算法时的缺页率（5）voidLRU（ ）;/*计算使用LFU算法时的缺页率（6）voidNUR

19、（ ）;/*计算使用NUR算法时的缺页率3、变量定义（4）intatotal_struction:指令流数据组（5）intpagetotal_instruction:每个指令所属页号（6）int offsettotal_instruction:每页装入10条指令后取模运算页号偏移量（7）inttotal_pf:用户进程的内存页面数（8）intdiseffect:缺页率2、程序流程图3、程序框架：#define total_struction 320#define total_vp 32typedef struct int pn ,pfn,counter,time;pl_type;pl_type

20、 ptotal_vp;pfc_structint pn , pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp,*freepf_head,*busypf_head, *busypf_tail;int diseffect, atotal_struction;int pagetotal_struction,offsettotal_struction; void initialize(); void FIFO( ); / LRU();main() int s,i,j;sand(getp

21、id()*10);s=(float)319*rand()/32767+1;for(i=0;i < total_struction;i+) ai=s; ai+1=ai+1; aI+2=(float)a i *rand()/32767;ai+3=ai+2+1;s=(float)rand()*(318-ai+2)/32767+ai+2+2; for( i=O;ivtotal_instruction;i+)pagei=ai/10;offseti=ai%10;例如：a0=194a1=195a2=55a3=56a4=73a5=74a6=30a7=31a8=257a9=258a10=210a11=21

22、1a12=319a13=320a14=46a15=47a16=273a17=274a18=205a19=206FIFO(i);/ LRU();for(i=4;iv=32;i+) 实验四文件管理实验性质：设计建议学时：3实验目的：本实验的目的是通过一个阅读和设计部分简单多用户文件系统的过程，加深理解文件系统 的内部功能和内部实现。预习内容：阅读教材计算机操作系统第六章，掌握文件管理相关概念和原理。实验内容：为DOS系统设计一个简单的二级文件系统。要求做到以下几点： 可以实现下列几条命令LOGIN用户登录DIR列文件目录CREATE创建文件DELETE删除文件OPEN打开文件CLOSE关闭文件READ读文件WRITE写文件COPY拷贝文件 列目录时要列出文件名，物理地址，保护码和文件长度。 源文件可以进行读写保护。实验提示： 首先应确定文件系统的数据结构：主目录、子目录及活动文件等。主目录和子目录都以 文件的形式存放于磁盘，这样便于查找和修改。 用户创建的文件，可以编号存储于磁盘上。如：file0,file1,file2并以编号作为物理地址，在目录中进行登记。实验实现程序提示（C语言）：1、程序中相关数据类型定义（本程序