“操作系统课程设计”实验讲义20150303

操作系统课程设计实验讲义黑龙江大学计算机科学技术学院软件学院2004年-2015年目录第一部分课程目的与任务.....................................................................................................1一、课程基础.......................................................................................................................1二、适应对象.......................................................................................................................1三、教学目的.......................................................................................................................1四、内容提要.......................................................................................................................1第二部分主要内容及基本要求.............................................................................................2一、进程控制.......................................................................................................................2二、分页式存储管理...........................................................................................................4三、设备管理.......................................................................................................................6四、文件管理.....................................................................................................................11五、进程调度.....................................................................................................................15六、总结报告模板.............................................................................................................16第三部分“操作系统课程设计”读书工程环节方案.......................................................20一、目的与要求.................................................................................................................20二、考核方式.....................................................................................................................20三、参考书目.....................................................................................................................20四、读书报告模板.............................................................................................................251第一部分课程目的与任务一、课程基础在学这门课之前，学生必须预修过高级语言、数据结构、离散数学方面的基本知识，并学习操作系统课程相关内容。二、适应对象计算机科学与技术-计算机应用;软件工程-软件工程;电子信息科学类-电子信息科学与技术;管理类-信息管理专业三、教学目的为配合“操作系统”课程的教学，通过模拟操作系统的实现，使学生能更深刻地领会操作系统工作原理和操作系统实现方法，并提高程序设计能力。四、内容提要本课程要求实现一套模拟单用户多任务操作系统的软件程序。该软件通过5个互相关联的模块模拟进程管理、存储管理、设备管理和文件管理四部分的主要内容，最终形成一套完整的模拟程序。2第二部分主要内容及基本要求一、进程控制●基本要求：利用简单的结构和控制方法模拟进程结构、进程状态和进程控制。●参考学时：6学时●实验提示：1、用PCB表示整个进程实体，利用随机数方法或键盘控制方法模拟进程执行中产生的事件，或者利用基于图形界面的鼠标或者键盘操作控制进程管理内容。2、定义PCB：包括理论PCB中的基本内容，如内部ID、外部ID、队列指针。由于很难实现真正的进程创建功能，在实验中只需建立PCB节点，并用它代表一个完整的进程。每创建一个进程时，可动态分配PCB节点，对相应内容赋值，并链接到适当的队列上。可参考如下数据结构（动态形式）：structPCB{charname[10];structPCB*next;};structPCB*ready,*blocked,*running;创建进程时：structPCB*p=(structPCB*)malloc(sizeof(structPCB));并将此进程添加到就绪队列末尾：add(ready,p);其中，ready为就绪队列头节点，并在开始处分配了空间；add函数是链表中添加节点函数，代码可以为：voidadd(structPCB*head,structPCB*process){structPCB*tmp=head;while(tmp-next!=NULL)3tmp=tmp-next;tmp-next=process;process-next=NULL;}3、定义进程状态转换方式：真实的进程状态转换是由进程内部操作或操作系统的控制引起的。由于模拟程序中无法实现这些功能，我们可以采用随机数方法或键盘控制方法模拟，并实现对应的控制程序。随机方法指产生1－5的随机数，分别代表创建进程(1)、时间片到(2)、进程阻塞(3)、唤醒进程(4)、结束进程(5)等事件；键盘模拟方法指定义5个选项菜单代表以上五种事件。4、根据随机数或键盘操作处理就绪队列、阻塞队列和当前执行进程的状态。每次事件处理后应显示出当前系统中的执行进程是哪一个，就绪队列和阻塞队列分别包含哪些进程。5、*（带*部分为试验班和特长班需要完成的内容，普通班选作）完成可变分区的分配与回收，创建进程的同时申请一块连续的内存空间，结束进程同时回收分配的内存空间。分配采用最佳适应算法，碎片大小为2Kb,最后回收所有进程的空间。可以查看进程所占的空间和系统空闲空间。●评分标准：满分15分要求必须完成以下几个方面的内容：能够模拟进程的创建与撤销过程；5分可对进程的状态进行全面的控制；5分按先进先出方式管理就绪和阻塞队列，能够按队列形式输出进程状态。5分4二、分页式存储管理●基本要求：在第1部分实验基础上实现进程的分页式内存分配和地址转换过程，并进一步实现请求分页式存储分配和地址转换过程。页面置换算法至少应实现先进先出（FIFO）、最近最久未使用（LRU）等算法。●参考学时：6学时●实验提示：1、建立1个位示图，用来模拟内存的分配情况，位示图的位数与设定的物理块个数相同。程序启动时可利用一组随机0和1填充位示图，表示内存已被占用情况。假设内存容量为64K，块大小为1K，则共有64个块，随机填充后的位示图可能的值如下：该位示图表示内存的2（0字节第2位）、3（0字节第3位）、6（0字节第6位）、8（1字节第0位）、9（1字节第1位）、12（1字节第4位）、15（1字节第7位）…等块没有被占用。2、创建进程时输入进程大小，并根据程序中设定的物理块大小为进程分配物理块，同时建立页表。例如，在上图基础上，若要建立一个大小为5000字节的进程，则：计算出该进程共有“向上取整（5000/1024）=5”个页，需要占用5个内存块；建立空的页表，即长度为5的一维整数数组；从位示图中找出前5个“0”位在整个位示图中的位置号（即i字节j位为0，则该位的位置为8*i+j），并将这些号依次填入页表中，同时把前5个“0”改为“1”，以示对应内存块已经分配。第0字节10110011第2字节11100111第4字节00011111第6字节11111000第1字节01101100第3字节10000111第5字节01110011第7字节0000000153、输入当前执行进程所要访问的逻辑地址，并将其转换成相应的物理地址。4、进程退出时，根据其页表内容向位示图反向回填“0”。5、扩充页表，将其变成支持请求和置换功能的二维页表（增加存在位等）。创建进程时可装入固定的前三页（或键盘输入初始装入页数，不同进程的装入个数可以不同），其余页装入到置换空间内（置换空间大小应为内存空间大小的1.5-2倍，对其还需建立独立的置换空间位示图）。6、分别采用FIFO或LRU置换算法对地址转换过程中遇到的缺页现象进行页面置换，可将多次地址转换过程中所涉及到的页号视为进程的页面访问序列，从而计算置换次数和缺页率。7、*可以在完成第六步的基础上实现OPT的页面置换算法，并加以比较。●评分标准（满分15分）：要求必须完成以下几个方面的内容（实验提示前4部分，10-12分）：在第1部分基础上扩展；能够模拟内存的分页式分配和回收过程，可查看内存分配位示图和进程页表；可根据内存分配状态进行地址转换。如果实现以下要求（实验提示后3部分），有额外3-5分加分：能够模拟基于虚拟存储器的内存分配和回收过程，可查看交换空间位示图和扩展的页表；在虚拟存储器基础上完成地址转换，缺页时能够实现页面置换；页面置换过程中能够模拟FIFO、LRU置换算法，可将多次地址转换过程中所涉及到的页面视为进程的页面访问序列，从而计算置换次数和缺页率。6三、设备管理●基本要求：在前面的实验基础上实现设备管理功能的模拟，主要包括通道和控制器的添加和删除，设备的添加、删除，设备的分配和回收。●参考学时：6学时●实验提示：1、假定模拟系统中已有键盘、鼠标、打印机和显示器四个设备，另有三个控制器和两个通道。2、设备管理子系统涉及到系统设备表（SDT）、通道控制表（CHCT）、控制器控制表（COCT）和设备控制表（DCT）来体现输入输出系统的四级结构和三级控制。应实现上述数据结构来完成对外围设备的管理。数据结构参考代码:C/C++版:structNode{charname[10];//名称structPCB*process;//占用该节点的进程structP