操作系统实验指导书

1、操作系统实验指导书东北大学软件学院2008年10月实验要求（1）预习实验指导书有关部分，认真做好实验的准备工作。（2）实验中及时分析记录。（3）按指导书要求书写实验报告，提交打印版（A4）。实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第二部分是提交的实验报告。实验一 进程调度(4学时)一、实验目的在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理机数时，就必须依照某种策略来决定哪些进程优先占用处理机。本实验模拟在单处理机情况下的处理机调度，帮助学生加深了解处理机调度的工作。二、实验类型设计型。三、预习内容预习课本处理机调度有关内容

2、，包括进程占用处理机的策略方法。四、实验内容与提示本实验中共有两个实验题。第一题：编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。 <一>最高优先级优先调度算法 1)优先级简介动态优先数是指在进程创建时先确定一个初始优先数， 以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU的进程，就能因为等待时间的增长而优先数变为最高而得到CPU运行。例如：在进程获得一次CPU后就将其优先数减少1。或者，进程等待的时间超过某一时限时增加其优先数的值，等等。 2)详细设计优先权调度算法：1、设定系统中有五个进程，每一个进程用

3、一个进程控制块（ PCB）表示，进程队列采用链表数据结构。2、 进程控制块包含如下信息：进程名、优先数、需要运行时间、已用CPU时间、进程状态等等。3、 在每次运行设计的处理调度程序之前，由终端输入五个进程的“优先数”和“要求运行时间”。4、 进程的优先数及需要的运行时间人为地指定。进程的运行时间以时间片为单位进行计算。5、 采用优先权调度算法，将五个进程按给定的优先数从大到小连成就绪队列。用头指针指出队列首进程，队列采用链表结构。6、 处理机调度总是选队列首进程运行。采用动态优先数办法，进程每运行一次优先数减“1”，同时将已运行时间加“1”。7、 进程运行一次后，若要求运行时间不等于已运行时

4、间，则再将它加入就绪队列；否则将其状态置为“结束”,且退出就绪队列。8、 “就绪”状态的进程队列不为空，则重复上面6，7步骤，直到所有进程都成为“结束”状态。9、 在设计的程序中有输入语句，输入5个进程的“优先数”和“要求运行时间”，也有显示或打印语句，能显示或打印每次被选中进程的进程名、运行一次后队列的变化，以及结束进程的进程名。10、最后，为五个进程任意确定一组“优先数”和“要求运行时间”，运行并调试所设计的程序，显示或打印出逐次被选中进程的进程名及其进程控制块的动态变化过程。 3)流程图: 图一.最高优先级优先调度算法流程图<二>简单轮转法调度算法1)简单轮转法的基本思想：所

5、有就绪进程按 FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。即将CPU的处理时间划分成一个个相同的时间片，就绪队列的诸进程轮流运行一个时间片。当一个时间片结束时，如果运行进程用完它的时间片后还未完成，就强迫运行机制进程让出CPU，就把它送回到就绪队列的末尾，等待下一次调度。同时，进程调度又去选择就绪队列中的队首进程，分配给它一时间片，以投入运行。直至所有的进程运行完毕。2)详细设计:1、 设系统有5个进程，每个进程用一个进程控制块PCB来代表。2、 为每个进程任意确定一个要求运行时间。3、 按照进程输入的先后顺序排成一个队列。再设一个队首指针指向第一个到达进

6、程的首址。4、 执行处理机调度时，开始选择队首的第一个进程运行。另外，再设一个当前运行进程的指针，指向当前正在运行的进程。5.考虑到代码的可重用性, 轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出。6.进程运行一次后，以后的调度则将当前指针依此下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程。同时还应判断该进程的要求运行时间是否等于已运行时间。若不等，则等待下一轮的运行，否则将该进程的状态置为完成态C，并退出循环队列。7.若就绪队列不空，则重复上述的（5）和（6）步骤直到所有的进程都运行完为止。8.在所设计的调度程序中,包含显示或打印语

7、句。显示或打印每次选中的进程的名称及运行一次后队列的变化情况。3)流程图 图二. 简单轮转法调度算法流程图五、思考题(1) 处理机调度的目的？(2) 你实现优先数调度算法的思想？(3) 你采用时间片轮转法实现处理机调度的思想？(4) 比较效率如何？六、实验报告(1) 实验题目。(2) 程序中使用的数据结构及符号说明。(3) 流程图。(4) 打印一份源程序并附上注释。(5) 打印程序运行时的初值和运行结果。参考资料(1)计算机操作系统（修订版），汤子瀛等编，西安电子科技大学出版社，2001-8。(2)<计算机操作系统>学习指导与题解,汤子瀛等编, 西安电子科技大学出版社,2003-3

8、。实验二 资源分配(4学时)一、实验目的多个进程动态地共享系统的资源可能会产生死锁现象。死锁的产生，必须同时满足四个条件，第一个是互斥条件，即一个资源每次只能由一个进程占用；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其它资源；第三个是非出让条件，任何一个进程不能抢占另一个进程已经获得且未释放的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只须确保上述四个条件之一不出现，则系统就不会发生死锁。在实验中假定系统中任一资源在每一时刻只能则由一个进程使用，任何进程不能抢占它进程正在

9、使用的资源，当进程得不到资源时必须等待。因此只要资源分配策略能保证进程不出现循环等待，则系统就不会发生死锁。本实验要求学生编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁的发生。二、实验类型设计型。三、预习内容预习课本资源分配有关内容，包括死锁发生条件及防止避免死锁的方法。四、实验要求与提示本实验中共有两个实验题。第一题：用银行家算法实现资源分配。要求：(1) 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。 利用银行家算法设计系统，进程

10、可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。(2) 设计用银行家算法和随机分配算法，实现资源分配的两个资源分配程序，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。(3) 确定一组各进程依次申请资源数的序列，在相同的情况下分别运行上述两种资源分配程序，观察运行结果。提示：(1) 银行家算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应付多个客户的借贷周转，为了防止银行因资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似的问题，系统中有限的资源要供多个进程使用，必须保证得到资源的进程能在有限的时间内归还资源

11、，以供其它进程使用资源。如果资源分配不得当，就会发生进程循环等待资源，各进程都无法继续执行下去的死锁现象。银行家算法分配资源的原则是：系统掌握每个进程对资源的最大需求量，当进程要求申请资源时，系统就测试该进程尚需资源的最大量，如果系统中现存的资源数大于或等于该进程尚需的最大量时，则就满足进程的当前申请。这样可以保证至少有一个进程可能得到全部资源而执行到结束，然后归还它所占用的全部资源供其它进程使用。银行家算法破坏了产生死锁的第四个条件，即不可能产生循环等待，从而可以避免死锁的发生。(2) 把各进程需要和已占用资源的情况记录在进程控制块中，假定进程控制块PCB的格式如表1。其中“状态”有就绪态、

12、等待态和完成态。当进程处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。“已占资源量”表示进程目前已经得到但还未归还的资源量。因此，进程在以后还需要的最大资源量等于资源需求总量减去已占有资源量。显然，每个进程的资源需求总量不能超过系统拥有的资源总数。表1 PCB格式进程号状 态当前申请量资源需求总量已占资源量(3) 为了观察死锁现象的发生，了解用银行算法进行资源分配可以避免死锁，故在模拟程序中采用两种资源分配算法：银行算法和随机算法。随机算法的分配原则是：当进程申请资源时，如果系统中现存资源数能满足进程的当前资源申请图1 资源分配模

13、拟程序总流程量，就把资源分配给该进程，否则就置进程为等待态。用随机算法分配资源可能会产生死锁。资源分配模拟程序总流程见图1。随机分配算法流程见图2。图2 随机分配算法模拟流程第二题：用按序分配策略实现资源分配。要求：(1) 设计一个3个进程共享10个资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。(2) 设计用按序分配算法实现资源分配的资源分配程序，应具有显示或打印各进程依次要求申请的资源号以及依次分配资源地情况。(3) 确定两组各进程依次要求申请的资源号，要求其中的一组中各进程按序地申请资源，另一组中各进程申请资源不受序号限制，分别运行上述设计的资源分配程序，观

14、察运行结果。提示：(1) 防止进程发生循环等待的另一种资源分配策略是按序分配算法，其基本思想如下：把系统中所有的资源排一个顺序，例如系统共有m个资源，用ri表示第i个资源，那么这m个资源是： r1, r2, r3 , rm规定任何进程不得在占用资源ri（1<i£m）后再申请rj（j<i£m），或者说，如果里程需要资源rj，那么它必须在申请ri之前申请（j<i）。可以证明，按这种策略分配资源时破坏了循环等待条件，故能防止发生死锁（证明略）。(2) 把各进程申请资源的情况记录在进程控制块PCB中，现假定进程控制块PCB的格式如下：进 程 号状 态当前等待资源号

15、上次申请资源号其中“状态”可以为就绪态、等待态和完成态。当进程处于等待态时，表示系统不能满足该进程的当前资源申请，此时，PCB中的“当前等待资源号”反映了该进程等待的资源。当系统为进程分配了一个资源后，则把分配的资源号填入“上次申请资源号”一栏中。(3) 假定系统中拥有的资源数m=10，而系统中申请资源的进程数N=3。按序分配算法程序流程见图3。图3 按序分配算法模拟流程五、思考题(1) 死锁发生的条件？(2) 避免死锁的方法有哪些？(3) 你的算法采用什么思想预防或避免死锁的发生？(4) 效率如何？六、实验报告(1) 实验题目。(2) 程序中使用的数据结构及符号说明。(3) 打印一份源程序并

16、附上注释。(4) 打印资源申请和分配情况 资源申请：进程号依次申请的资源数/资源号 分配情况：序号进程号得到的资源数/资源号等待资源数/资源号实验三 存储管理一、实验目的一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的

17、数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验类型设计型。三、预习内容预习课本存储管理有关内容，包括首次适应算法、最佳适应算法、最差适应算法。四、实验要求与提示主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区说明表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、循环首次适应算法、最佳适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与

18、回收的过程。1采用可变分区管理，使用首次适应算法实现主存的分配和回收。1）可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。为了说明那些分区是空闲的，可以用来装入新作业，必须有一张空闲说明表空闲区说明表格式如下：  起始地址长度状态第一栏45 K20KB未 分 配第二栏110 K146 KB未 分 配&#

19、160; 空 表 目 其中，起址指出一个空闲区的主存起始地址，长度指出空闲区的大小。 长度指出从起始地址开始的一个连续空闲的长度。 状态有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业完成后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。 2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。

20、有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区，留在空闲区表中。为了尽量减少由于分割造成的空闲区，尽可能分配低地址部分的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序从低到高登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”项留在表格的后部。3）采用首次适应算法分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍

21、为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。4）当一个作业执行完成撤离时，作业所占的分区应该归还给系统，归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在上述中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。2流程图 图1 主存回收算法图2 首次适应分配模拟算法3、例如，假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB作业2申请60KB作业3申请100KB作业

22、2释放60KB作业4申请200KB作业3释放100KB作业1释放130KB作业5申请140KB作业6申请60KB作业7申请50KB作业6申请60KB4实验截图1）进入界面,显示操作2）选择操作1,显示目前的空闲分区3）返回界面,选择操作2,输入如下信息4）显示分配作业后的空闲区表和作业链表:5）作业继续运行,完后回收作业,如下:五、思考题1、内存的主要分配方式有哪些？回收时可能出现的什么情况？应怎样处理这些情况？2、动态分区管理的常用内存分配算法有哪几种？比较它们各自的使用范围。六、实验报告1、设计题目 2、设计要求 3、设计分析 4、实现原理 5、程序流程图6、相关数据结构及说明7、程序执行

23、过程 8、程序代码及注释 9、执行结果和结果分析 10、心得体会 实验四 虚拟存储器(4学时)一、实验目的在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验帮助同学理解在分页式存储管理中怎样实现虚拟存储器。二、实验类型综合型。三、预习内容预习课本虚拟存储器有关内容，包括利用分页式存储管理实现虚拟存储器策略方法。四、实验要求与提示本实验有三个题，其中第一题必做，第二、第三题中可任选一个。第一题：模拟分页式存储管理中硬件的地址转换和产生缺页中断。提示：

24、(1) 分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存，页表的格式为：页号标志主存块号在磁盘上的位置其中，标志用来表示对应页是否已经装入主存，标志位=1，则表示该页已经在主存，标志位=0，则表示该页尚未装入主存。主存块号用来表示已经装入主存的页所占的块号。在磁盘上的位置用来指出作业副本的每一页被存放在磁盘上的位置。(2) 作业执行时，指令中的逻辑地址指出了参加运算的操作数存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时

25、根据关系式：绝对地址=块号´块长+单元号计算出欲访问的主存单元地址。如果块长为2的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而成绝对地址。按计算出的绝对地址可以取到操作数，完成一条指令的执行。若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，由操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。(3) 设计一个“地址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时，则输出“*该页页号”，表示产生了一次缺

26、页中断。该模拟程序的算法如图4-1。(4) 假定主存的每块长度为128个字节；现有一个共七页的作业，其中第0页至第3页已经装入主存，其余三页尚未装入主存；该作业的页表为：页号标志主存块号在磁盘上的位置015011118012219013311021400225002360121图4-1 地址转换模拟算法如果作业依次执行的指令序列为：操作页号单元号操作页号单元号+0070移位4053+1050+5023´2015存1037存3021取2078取0056+4001-6040存6084运行设计的地址转换程序，显示或打印运行结果。因仅模拟地址转换，并不模拟指令的执行，故可不考虑上述指令序列中

27、的操作。第二题：用先进先出（FIFO）页面调度算法处理缺页中断。提示：(1) 在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用FIFO页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上。然后再把当前要访问的页装入该块。调出和装入后都要修改页表中对应页的标志。(2) FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时，把开始的m个页面装入主存，则数组的元素可定为m个。例如：P0，P1，Pm-1其中每一个Pi (i=0, 1, , m-1) 表示一个在主存

28、中的页面号。它们的初值为：P0： =0, P1： =1, , Pm-1： =m-1用一指针K指示当要装入新页时，应淘汰的页在数组中的位置，K的初值为“0”。当产生缺页中断后，操作系统选择Pk所指出的页面调出，然后执行：Pk： =要装入页的页号k： = (k+1) mod m再由装入程序把要访问的一页信息装入到主存中。重新启动刚才那条指令执行。(3) 编制一个FIFO页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必把该页调出（因在磁盘上已有副本）而直接装入一个新页将其覆盖。因此在页表中增加是否修改过的标志，为“1”表示修改过，为“0”表示未修改过，格式为：页号标志主存块

29、号修改标志在磁盘上的位置由于是模拟调度算法，所以，不实际地启动调出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替一次调出和装入的过程。把第一题中程序稍作改动，与本题结合起来，FIFO页面调度模拟算法如图5-2。(4) 如果一个作业的副本已在磁盘上，在磁盘上的存放地址以及已装入主存的页和作业依次执行的指令序列都同第一题中（4）所示。于是增加了“修改标志”后的初始页表为：页号标志主存块号修改标志在磁盘上的位置0150011118001221900133110021400022500023600121按依次执行的指令序列，运行你所设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后的数组P的值。(5) 为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。图5-2 FIFO页面调度模拟算法第三题：用最近最少用（LRU）页面调度算法处理缺页中断。提示：(1) 在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用L