操作系统试验指导书南京中医药大学试验教学网

操作系统试验指导书李玲娟李刚 李玲娟 审核南京中医药大学信息技术学院202310月编者说明软件技术是《操作系统》最重要的计算机系统软件，同时也是计算机科学与技术专业的一门核心专业根底课，其进展极为快速。学习计算机软件技术，特别是计算机操作系统技术，除了需要刻苦努力外，还需要把握软件和操作系统的原理与设计技巧。这些原理与技巧可以说是计算机界的前辈们一代接一代不停留的努力所留下的学问与才智的结晶，学习和把握它们对于激发自己的制造力和想象力是很有帮助的。如何学习和把握操作系统技术的原理与实际技巧呢？除了听课和读书之外，最好的方法就是在实践中练习，通过自己模拟设计操作系统的原理试验，可以培育程序设计的方法和技巧，提高编制和理解清楚、合理、可读性好的系统程序的力量，加深对操作系统课程的理解。使自身更好的把握操作系统的根本概念、根本原理及根本功能，从而具有分析实际操作系统的根本力量，深入直观的理解操作系统使用的各类算法。《操作系统试验指导书》是针对这门课的试验编写的，书中设计了四个重要的操作系统原(进程调度)和试验二(分区式存储治理)(虚拟存储治理)和试验四(文件治理)教材中的理论原理。全部试验共18学时，均承受C语言作为编程语言模拟设计完成相关程序。本书编写中，参考了西安电子科技大学、清华大学的操作系统相关图书资料。本书由信息技术学院副院长李玲娟和应用教研室李刚两位教师编写南京中医药大学教务处赐予了指导和大力帮助，在此表示诚意的感谢！限于编者的水平，难免有疏漏与错误，敬请读者批判指正。李玲娟 李刚20231012日目 录TOC\o“1-1“\h\z\u\l“_TOC_250003“试验一进程调度 1\l“_TOC_250002“试验二分区式存储治理 4\l“_TOC_250001“试验三虚拟存储治理 8\l“_TOC_250000“试验四文件治理 11南京中医药大学信息技术学院操作系统试验南京中医药大学信息技术学院操作系统试验10试验一进程调度试验性质：设计建议学时：6学时试验目的：通过这次试验，加深对进程概念的理解，进一步把握进程状态的转变、进程调度的策略及对系统性能的评价方法。预习内容：阅读教材《计算机操作系统》其次章和第三章，把握进程治理及调度相关概念和原理。根本试验内容：设计程序模拟进程的轮转法调度过程。假设初始状态为：有n个进程处于就绪状态，有m(程不会堵塞)，且每过t个时间片系统释放资源，唤醒处于堵塞队列队首的进程。程序要求如下：1〕.输出系统中进程的调度次序；2〕.计算CPU利用率。实现提示：C语言实现提示：程序中进程可用PCB表示，其类型描述如下：struct PCB_type{char name //进程名int state //进程状态2——表示“执行”状态1——表示“就绪”状态0——表示“堵塞”状态int cpu_time //运行需要的CPU时间〔需运行的时间片个数〕}设置两个队列，将处于“就绪”状态的进程PCB挂在队列ready中；将处于“堵塞”状态的进程PCB挂在队列blocked中。队列类型描述如下：struct QueueNode{struct PCB_type PCB;Struct QueueNode *next;}并设全程量：structQueueNode*ready_head=NULL,//ready队列队首指针*ready_tail=NULL,*blocked_head=NULL,//ready队列队尾指针//blocked队列队首指针*blocked_tail=NULL; //blocked队列队尾指针设计子程序：start_state; //读入假设的数据，设置系统初始状态dispath; //模拟调度calculate; //计算CPU利用率试验要求：上机前认真使用C语言编写好程序，承受TurboC作为编译环境；上机时独立调试程序依据具体试验要求，填写好试验报告〔包括思想、源程序、实例运行结果。测试用数据：n=2m=3t=5ready_headblocked_headdispath算法流程图： beginuse_cpu=0x=0

/*use_cpu中记录CPU运行时间unuse_cpu=0 /*unuse_cpu中记录CPU空闲时间ready 队列不空或blocked队列不空是

否end是ready队列不空 否p ready队首元素p->PCB.state置“运行”p->PCB.namep->PCB.cpu_time--use_cpu++

unuse_cpu++是否 p->PCB.cpu_time>0释放p 是pready队列队尾是x++x==t 否是blocked ready队列队尾；x=0试验二分区式存储治理试验性质：设计建议学时：6试验目的：通过这次试验，加深对内存治理的生疏，进一步把握内存的安排、回收算法的思想。预习内容：阅读教材《计算机操作系统》第四章，把握存储器治理相关概念和原理。试验内容：设计程序模拟内存的动态分区法存储治理。内存空闲区使用自由链治理，承受最坏适应算法从自由链中查找空闲区进展安排，内存回收时假定不做与相邻空闲区的合并。假定系统的内存共640K，初始状态为操作系统本身占用64K。在t1时间之后，有作业A、B、C、D8K、16K、64K、124Kt2C完成；在t3时间之后，作业E50Kt4时间之后，作业D完成。要求编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。实现提示C语言：程序中自由链队列的结点类型可描述如下：struct freelink{int len,address; /* len/* addressstruct freelink *next;}内存占用区用链表描述，其结点类型描述如下：struct busylink{charname; /*作业或进程名name=’S表示OS占用int len,address;struct busylink*next;}并设全程量：structfreelink*free_head=NULL;//自由链队列〔带头结点〕队首指针structbusylink*busy_head=NULL,*busy_tail=NULL；//占用区队列队〔带头结点〕首指针//占用区队列队尾指针设计子函数：void start(void); /*设置系统初始状态*/{ structfreelink*p;structbusylink*q;free_head=(struct freelink*)malloc(sizeof(struct freelink));free_head->next=NULL; //创立自由链头结点busy_head=busy_tail=(struct busylink*)malloc(sizeof(structbusylink));busy_head->next=NULL; //创立占用链头结点p=(structfreelink*)malloc(sizeof(structfreelink));p->address=64;p->len=640-64; 64K〕p->next=NULL;free_head->next=p;q=(struct busylink*)malloc(sizeof(structbusylink));q->name=‟S‟; /* S表示操作系统占用*/q->len=64; q->address=0; busy_head->next=q; busy_tail=q;}void requireMemo(char name,int require);/*模拟内存安排*/void freeMemo(charname); /*模拟内存回收*/void past(int time); /*模拟系统过了time时间*/void printlink; /*输出内存空闲状况〔自由链的结点〕*/设计主函数：main{start;past(t1);requireMemo(„A‟,8); requireMemo(„B‟,16);requireMemo(„C‟,64);requireMemo(„D‟,124);printlink;past(t2);freeMemo(„C‟);printlink;past(t3);requireMemo(„E‟,50);printlink;freeMemo(„D‟);printlink;}试验要求：上机前认真使用C语言编写好程序，承受TurboC作为编译环境；上机时独立调试程序依据具体试验要求，填写好试验报告〔包括思想、源程序、实例运行结果。requireMemo(char name,int require)流程图如下：begin否end printf(“Can’tallocate”)

free_head->next->len>=requirep=(struct busylink*)malloc(…);p->name=name;p->address=free_head->next->address;p->len=require;p->next=NULLbusy_tail->next=p;busy_tail=p;w=free_head->next;free_head->next=w->next;w->len==require

w->address=w->address+require;w->len=w->len-require;u=free_head;v=free_head->next;free(w)

(v!=NULL)&&v->len>w->lenu->next=ww->next=v

u=vv=v->nextendfreeMemo(charname)流程图如下：beginq=busy_headp=busy_head->next否(p!=NULL)&&(p->name!=name)q=pp=p->nextp==NULL是if (p==busy_tail) busy_tail=q; printf(“%cisnotexist”,name)q->next=p->next;len=p->len;address=p->address;free(p)endw=(structfreelink*)malloc(…);w->len=len;w->address=address; 否是u=free_headv=free_head->next(v!=NULL)&&(v->len>len)u=vv=v->next

u->next=ww->next=vend试验三虚拟存储治理试验性质：验证建议学时：3试验目的：存储治理的主要功能之一是合理的安排空间。恳求页式治理是一种常用的虚拟存储治理技术。本试验的目的是恳求页式存储治理中页面置换算法模拟设计，了解虚拟存储技术的特点，把握恳求页式存储治理的页面置换方法。预习内容：阅读教材《计算机操作系统》第四章，把握存储器治理相关概念和原理。试验内容：通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：①、50%的指令是挨次执行的；②、25%的指令是均匀分布在前地址局部；③、25%的指令是均匀分布在后地址局部。具体的实施方法是：① 在[0,319]的指令地址之间随机选取一起点m;② 挨次执行一条指令，即执行地址为m+1的指令；③ 在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’；④ m’+1;⑤ 在后地址[m’+2,319]中随机选取一条指令并执行；⑥ 320次指令。 将指令序列变换成页地址流1K；432页；32K；在用户虚存中，按每K10320条指令在虚存中的存放方式为：第0第9条指令为第0页〔[，9；第10条第19条指令为第1页〔[119；.第310~第319条指令为第31页〔32页。计算并输出下述各种算法在不同的内存容量下的缺页率。①先进先出的算法FIF；②最近最少使用算法LR；③最正确淘汰法OP：先淘汰最不常用的页地址；④最少访问页面算法LF；⑤最近不常常使用算法NU其中③和④为选择内容。缺页率=〔页面失效次数〕/〔页地址流长度〕在本试验中，页地址流的长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。(4)随机数产生方法试验指导

rand，分别进展初始化和产生随机数。例如：rand;语句可初始化的一个随机数；a[0]=10*rand/32767*319+1;a[1]=10*rand/32767*a[0];语句可用来产生a[0]与a[1]中的随机数。1、数据类型定义页面类型typedefstruct{intpn,pfn,counter,time;}pl_type;/*pn为页号，pfn为页面号，counter为一个周期内访问该页面次数，time为访问时间。页面掌握构造pfc_struct{intpn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head;pfc_type *busypf_tail;/*pfc[total_vp]定义用户进程虚页掌握构造*freepf_head为空页面头指针*busypf_head为忙页面头指针*busypf_tail为忙页面尾指针2、函数定义voidinitialize();/*初始化函数，给每个相关的页面赋值voidFIFO(); /*FIFO算法时的缺页率voidLRU(); /*LRU算法时的缺页率voidOPT( /*OPT算法时的缺页率voidLRU(); /*LFU算法时的缺页率voidNUR(); /*计算使用NUR算法时的缺页率3、 变量定义int a[total_struction]: 指令流数据组int [total_instruction]:每个指令所属页号intoffset[total_instruction]:10条指令后取模运算页号偏移量inttotal_pf:用户进程的内存页面数intdiseffect:缺页率2、 程序流程图3、 程序框架：#define total_struction 320#define total_vp 32typedefstruct{intpn,pfn,counter,time;}pl_type;pl_typep[total_vp];pfc_struct{intpn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_struction];int[total_struction],offset[total_struction];voidinitialize();{……}voidFIFO();/LRU();{……}main( ){ints,i,j;sand(getpid*10);s=(float)319*rand/32767+1;for(i=0;i<total_struction;i++){a[i]=s;a[i+1]=a[i]+1;a[I+2]=(float)a[i]*rand/32767;a[i+3]=a[i+2]+1;s=(float)rand*(318-a[i+2])/32767+a[i+2]+2;}for(i=0;i<total_instruction;i++){[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i<=32;i++) FIFO(i);/LRU();}例如：a[0]=194a[1]=195a[2]=55a[3]=56a[4]=73a[5]=74a[6]=30a[7]=31a[8]=257a[9]=258a[10]=210a[11]=211a[12]=319a[13]=320a[14]=46a[15]=47a[16]=273a[17]=274a[18]=205a[19]=206试验四文件治理试验性质：设计建议学时：3试验目的：本试验的目的是通过一个阅读和设计局部简洁多用户文件系统的过程，加深理解文件系统的内部功能和内部实现。预习内容：阅读教材《计算机操作系统》第六章，把握文件治理相关概念和原理。试验内容：DOS①可以实现以下几条命令LOGIN 用户登录DIR 列文件名目CREATE 创立文件DELETE 删除文件OPEN 翻开文件CLOSE 关闭文件READ 读文件WRITE 写文件COPY 拷贝文件②列名目时要列出文件名，物理地址，保护码和文件长度。③源文件可以进展读写保护。试验提示：①首先应确定文件系统的数据构造：主名目、子名目及活动文件等。主名目和子名目都以文件的形式存放于磁盘，这样便于查找和修改。②用户创立的文件，可以编号存储于磁盘上。如：file0