操作系统期末复习02125

1、操作系统期末考试复习2014-06-26考试题型和题量 一 判断题 共10题，1题1分，共10分 二 填空题 共10题，1题1分，共10分 三 选择题 共10题，1题2分，共20分 四 综合题 共6题，1题10分，共60分判断题 11 1、引起中断的事件与、引起中断的事件与CPUCPU当前执行的程序（进程）无关。在处理高级别中断时，低级别中断能够当前执行的程序（进程）无关。在处理高级别中断时，低级别中断能够被屏蔽。而对异常的处理一般要依赖当前程序（进程）的运行现场，而且异常不能被屏蔽，一被屏蔽。而对异常的处理一般要依赖当前程序（进程）的运行现场，而且异常不能被屏蔽，一旦发生应立即处理。旦发生应

2、立即处理。 2 2、前趋图是一个有向无循环图，前趋图中不可以存在循环。、前趋图是一个有向无循环图，前趋图中不可以存在循环。3 3、挂起是指暂时将一个进程从内存换出到外存。激活指解除挂起状态，将进程重新换回内存。、挂起是指暂时将一个进程从内存换出到外存。激活指解除挂起状态，将进程重新换回内存。4 4、在大多数操作系统中，线程被终止后并不立即释放它所占用的系统资源。、在大多数操作系统中，线程被终止后并不立即释放它所占用的系统资源。 5 5、与低级调度相关联的进程（线程）队列称为就绪队列。而与高级调度相关联的进程（线程）队、与低级调度相关联的进程（线程）队列称为就绪队列。而与高级调度相关联的进程（线

3、程）队列是后备队列。列是后备队列。 6 6、如果不按照安全序列分配资源，则系统、如果不按照安全序列分配资源，则系统可能可能会由安全状态进入不安全状态。会由安全状态进入不安全状态。7 7、字节多路通道以字节为信息传输单位，主要用于连接大量低速外围设备。而数组选择通道以数、字节多路通道以字节为信息传输单位，主要用于连接大量低速外围设备。而数组选择通道以数据块为信息传送单位，因此信息传输速率很高，主要用于连接高速外围设备。据块为信息传送单位，因此信息传输速率很高，主要用于连接高速外围设备。8 8、硬盘访问时间一般主要由寻道时间长短决定。、硬盘访问时间一般主要由寻道时间长短决定。 这是因为寻道操作通常

4、花费的时间最多。这是因为寻道操作通常花费的时间最多。判断题 21 1、进程是进程实体的运行过程，是系统资源分配和调度的一个独立单位。、进程是进程实体的运行过程，是系统资源分配和调度的一个独立单位。2 2、机器指令本身在一个指令周期内执行，不可以被中断。、机器指令本身在一个指令周期内执行，不可以被中断。3 3、进程具有异步性的特征，使得进程可能具有不同的推进顺序。、进程具有异步性的特征，使得进程可能具有不同的推进顺序。4 4、磁盘调度的目标是使所有进程的平均寻道时间最少。、磁盘调度的目标是使所有进程的平均寻道时间最少。 5 5、一般情况下，目标模块（程序）和装入模块（程序）中的地址都是逻辑地址。

5、、一般情况下，目标模块（程序）和装入模块（程序）中的地址都是逻辑地址。6 6、根据交换的单位不同，交换技术可以分为两种具体的实现方式：整体交换、根据交换的单位不同，交换技术可以分为两种具体的实现方式：整体交换（进程交换）和部分交换。（进程交换）和部分交换。7 7、在大多数系统中，物理地址空间只是虚拟地址空间的一个子集。、在大多数系统中，物理地址空间只是虚拟地址空间的一个子集。 8 8、两级页表机制解决了大页表需要连续内存空间存放的问题，但并未减少页表、两级页表机制解决了大页表需要连续内存空间存放的问题，但并未减少页表对内存空间的需求，页表在内存中占用的总空间并没有减少。对内存空间的需求，页表在

6、内存中占用的总空间并没有减少。填空题 11 1、操作系统包含了三种运行模型，分别为独立运行的内核模型、操作系统包含了三种运行模型，分别为独立运行的内核模型、嵌入应用进程中执行的模型嵌入应用进程中执行的模型、作、作为独立进程运行的模型。为独立进程运行的模型。2 2、为了使多个进程能有条不紊地运行，需要进行进程同步，即对进程的执行次序以及访问资源的、为了使多个进程能有条不紊地运行，需要进行进程同步，即对进程的执行次序以及访问资源的顺序进行协调。协调有两种方式：进程互斥方式和顺序进行协调。协调有两种方式：进程互斥方式和进程同步方式进程同步方式。3 3、进程之间的制约关系包含：、进程之间的制约关系包含

7、：间接相互制约关系间接相互制约关系和直接相互制约关系。和直接相互制约关系。4 4、进程同步进程同步就是对并发诸进程的执行顺序进行协调，使进程的执行结果具有可再现性。就是对并发诸进程的执行顺序进行协调，使进程的执行结果具有可再现性。5 5、存在以下两种低级调度方式：非抢占调度方式、存在以下两种低级调度方式：非抢占调度方式、抢占调度方式抢占调度方式。6 6、时间片的长短受、时间片的长短受系统处理能力系统处理能力和系统负载状态等因素的影响。和系统负载状态等因素的影响。7 7、按照设备的信息交换单位，可将设备分成、按照设备的信息交换单位，可将设备分成字符设备字符设备和块设备。和块设备。8 8、根据在输

8、入、根据在输入/ /输出过程中起的作用和与硬件的关系，可以将输入输出过程中起的作用和与硬件的关系，可以将输入/ /输出软件分为四个层次：用户输出软件分为四个层次：用户层输入层输入/ /输出软件、设备无关软件、输出软件、设备无关软件、设备驱动程序设备驱动程序和输入和输入/ /输出中断处理程序。输出中断处理程序。9 9、存储器管理指的是管理、存储器管理指的是管理内部存储器内部存储器。1010、针对链接时间的不同，存在三种链接方式：静态链接、针对链接时间的不同，存在三种链接方式：静态链接、装入时动态链接装入时动态链接、运行时动态链接。、运行时动态链接。填空题 21 1、系统调用和过程调用的主要区别在

9、于、系统调用和过程调用的主要区别在于运行的状态不同运行的状态不同、进入的方式不同、返回的方式不同、代、进入的方式不同、返回的方式不同、代码层次不同。码层次不同。2 2、在多道程序环境中，作业一般要经过调度才能执行。存在三种调度方式，它们是高级调度、低、在多道程序环境中，作业一般要经过调度才能执行。存在三种调度方式，它们是高级调度、低级调度、级调度、中级调度中级调度。3 3、正是借助、正是借助PCBPCB（或（或进程控制块进程控制块），操作系统才能对并发进程进行有效管理和控制。），操作系统才能对并发进程进行有效管理和控制。4 4、进程互斥进程互斥是指并发的各个进程必须以互斥的方式访问临界资源。是

10、指并发的各个进程必须以互斥的方式访问临界资源。5 5、当最高优先权优先调度算法用于低级调度时，根据是否允许发生抢占，可以将算法进一步划分、当最高优先权优先调度算法用于低级调度时，根据是否允许发生抢占，可以将算法进一步划分成以下两种算法：非抢占式优先权算法、成以下两种算法：非抢占式优先权算法、抢占式优先权算法抢占式优先权算法。6 6、优先权的类型分为两种，分别是、优先权的类型分为两种，分别是静态优先权静态优先权和动态优先权。和动态优先权。7 7、按照资源属性，可将设备分成独占设备、共享设备和、按照资源属性，可将设备分成独占设备、共享设备和虚拟设备虚拟设备。8 8、输入、输入/ /输出控制方式包含

11、：程序直接输入输出控制方式包含：程序直接输入/ /输出控制方式、中断输入输出控制方式、中断输入/ /输出控制方式、输出控制方式、DMADMA输入输入/ /输出控制方式输出控制方式和通道输入和通道输入/ /输出控制方式。输出控制方式。9 9、计算机中的存储器分为、计算机中的存储器分为内部存储器内部存储器和外部存储器。和外部存储器。1010、根据进行地址变换时间的不同，可以将程序装入分成、根据进行地址变换时间的不同，可以将程序装入分成静态装入静态装入和运行时动态装入两种。和运行时动态装入两种。填空题 21 1、系统调用和过程调用的主要区别在于、系统调用和过程调用的主要区别在于运行的状态不同运行的状

12、态不同、进入的方式不同、返回的方式不同、代、进入的方式不同、返回的方式不同、代码层次不同。码层次不同。2 2、在多道程序环境中，作业一般要经过调度才能执行。存在三种调度方式，它们是高级调度、低、在多道程序环境中，作业一般要经过调度才能执行。存在三种调度方式，它们是高级调度、低级调度、级调度、中级调度中级调度。3 3、正是借助、正是借助PCBPCB（或（或进程控制块进程控制块），操作系统才能对并发进程进行有效管理和控制。），操作系统才能对并发进程进行有效管理和控制。4 4、进程互斥进程互斥是指并发的各个进程必须以互斥的方式访问临界资源。是指并发的各个进程必须以互斥的方式访问临界资源。5 5、当最

13、高优先权优先调度算法用于低级调度时，根据是否允许发生抢占，可以将算法进一步划分、当最高优先权优先调度算法用于低级调度时，根据是否允许发生抢占，可以将算法进一步划分成以下两种算法：非抢占式优先权算法、成以下两种算法：非抢占式优先权算法、抢占式优先权算法抢占式优先权算法。6 6、优先权的类型分为两种，分别是、优先权的类型分为两种，分别是静态优先权静态优先权和动态优先权。和动态优先权。7 7、按照资源属性，可将设备分成独占设备、共享设备和、按照资源属性，可将设备分成独占设备、共享设备和虚拟设备虚拟设备。8 8、输入、输入/ /输出控制方式包含：程序直接输入输出控制方式包含：程序直接输入/ /输出控制

14、方式、中断输入输出控制方式、中断输入/ /输出控制方式、输出控制方式、DMADMA输入输入/ /输出控制方式输出控制方式和通道输入和通道输入/ /输出控制方式。输出控制方式。9 9、计算机中的存储器分为、计算机中的存储器分为内部存储器内部存储器和外部存储器。和外部存储器。1010、根据进行地址变换时间的不同，可以将程序装入分成、根据进行地址变换时间的不同，可以将程序装入分成静态装入静态装入和运行时动态装入两种。和运行时动态装入两种。单选题 11 1、引起进程挂起的事件包括终端用户的请求、父进程请求、负荷调节的需要和操作系统的需要。2 2、引起进程激活的事件包括系统资源尤其是内存资源已经充裕内存

15、资源已经充裕，或者用户或父进程要求激活指定进程等。3 3、引起进程创建的事件包括提交批处理作业、用户登录、提供服务和应用进程请求。4 4、引起进程撤销的事件包括正常结束、异常结束和外界干预外界干预。5 5、实现进程互斥的机器指令包含：开关中断指令、测试与设置指令、交换指令。6 6、实现进程互斥的软件方法包含：两标志算法两标志算法、三标志法三标志法。7 7、最高响应比优先调度算法最高响应比优先调度算法可以看成是一种优先权调度算法，只是将作业的响应比当成动态优先权。这种调度算法可用于高级调度。8 8、时间片轮转调度时间片轮转调度是一种剥夺式调度算法。使用这种算法进行调度，系统耗费在进程（线程）切换

16、上的开销比较大，而开销的大小与时间片的长短有很大的关系。9 9、实现实时调度的基本条件有提供必要的信息、系统处理能力强系统处理能力强、采用抢占式调度机制、具有快速切换机制。单选题 21 1、按资源属性对计算机设备进行分类，可将其分为：共享设备、虚拟设备、独占设备。2 2、按照设备的使用特性，可将设备分为：存储设备存储设备和输入/ /输出设备。3 3、按信息传输速率对计算机设备进行分类，可将其分为：低速设备、中速设备和高速设备。4 4、按照设备的信息交换单位，可将设备分成字符设备字符设备和块设备。5. 5. 要使源程序能够运行，必须经过编译、链接、装入3 3个步骤。6. 6. 可变分区存储管理通

17、常使用的数据结构包括已使用分区表、空闲区表、空闲分区链。7 7、固定分区存储管理使用的数据结构是分区说明表分区说明表。8 8、不能进行进程调度和切换的情况包括在操作系统内核临界区中、中断处理过程、其它需要完全屏蔽的原子操作过程，而不包括当前进程由于某种原因进入等待状态当前进程由于某种原因进入等待状态（它是导致内核发生调度以及进程切换的事件）。9 9、要求掌握使用信号量实现进程同步，例子：书本第4949页图2-92-9和第7676页中的第2727题。有6个并发执行的进程Pi（i=1,2, ,6），若希望它们按照如下图所示的次序执行，试写出进程并发执行的算法。（书本49页 图2-9）按该图次序并发

18、执行的程序可以描述如下： Semaphore S8; /定义一个大小等于8的结构型信号量数组for(int i=0;i 8;i+) Si.value = 0;process PP( ) cobegin P1; V(S0); V(S1); V(S2); P(S0); P2; V(S5); P(S2); P3; V(S3); V(S4); P(S1); P(S3); P(S5); P4; V(S7); P(S4); P5; V(S6); P(S6); P(S7); P6; coend有7个并发执行的进程Pi（i=1,2, ,7），若希望它们按照如下图所示的次序执行，试写出进程并发执行的算法。（书本

19、76页第27题）按该图次序并发执行的程序可以描述如下： Semaphore S8; /定义一个大小等于8的结构型信号量数组for(int i=0;i8;i+) Si.Value=0;process PP()cobegin /伪代码cobegin和coend表示夹在它们之间的语句可以并发执行P1; V(S1);P2; V(S0);P(S0); P(S1); P3; V(S2); V(S3); V(S4);P(S2); P4; V(S5);P(S4); P5; V(S6);P(S5); P(S3); P6; V(S7);P(S7); P(S6); P7;coend使用资源分配图检测系统是否已进入死

20、锁状态的方法如下：（1 1）在资源分配图上，找出一个能满足其资源请求的进程顶点PiPi，删除PiPi的请求边和分配边，使之成为孤立顶点。因为在正常情况下，PiPi可以获得资源继续运行，直至运行结束，而当进程PiPi运行结束之后， Pi Pi就会释放它占有的资源，相当于去掉PiPi的请求边和分配边。（2 2）重复第（1 1）步，直至不能再进行删除操作为止。 (a) 资源分配图不能完全简化资源分配图不能完全简化R1R2R3P1P2P3 (b) 资源分配图可以完全简化资源分配图可以完全简化R1R2R3P1P2P3通道程序由通道指令构成。通道指令通常包含：（1）命令码也称为操作码，它规定了本条指令要执

21、行的操作，如读、写、控制等。（2）内存地址指明数据送入内存（读操作）或从内存取数据（写操作）的内存起始地址。（3）传输字节数指明本条指令要读/写的字节数。（4）记录结束标志标识某个记录是否结束，若为1，则表示本条指令是处理某个记录的最后一条指令。（5）通道程序结束标志标识通道程序是否结束，若为1，则表示本条指令是通道程序的最后一条指令。操作码通道程序结束标志记录结束标志传输字节数内存地址Write 002001000Write014002370Write003004250Write00200350Write114005130通道执行如下表所示操作要求的通道程序可以将位于内存不同位置的数据分别写

22、成通道执行如下表所示操作要求的通道程序可以将位于内存不同位置的数据分别写成 个字节和个字节和 个字节的两个记录。个字节的两个记录。600900通过采用覆盖技术，按照程序自身的逻辑结构，使不可能同时运行的程序段共享同一内存通过采用覆盖技术，按照程序自身的逻辑结构，使不可能同时运行的程序段共享同一内存空间，从而极大地提高内存资源的利用率。例子：进程的程序正文段包括空间，从而极大地提高内存资源的利用率。例子：进程的程序正文段包括6 6个程序段，分个程序段，分别是别是A A、B B、C C、D D、E E、F F，它们之间的调用关系如图，它们之间的调用关系如图4-94-9（a a）所示；程序段）所示；

23、程序段A A调用程序段调用程序段B B和和C C，程序段，程序段B B调用程序段调用程序段D D和和E E，程序段，程序段C C调用程序段调用程序段F F。通。通过调用关系可以知道，程序段过调用关系可以知道，程序段B B和和C C之间相互没有调用关系，它们不需要同时驻留在内存，可以共享同一覆盖区。同理，程序之间相互没有调用关系，它们不需要同时驻留在内存，可以共享同一覆盖区。同理，程序段段D D、E E、F F也可以共享同一覆盖区，其覆盖结构如图也可以共享同一覆盖区，其覆盖结构如图4-94-9（b b）所示。）所示。其中，覆盖区的大小其中，覆盖区的大小取决于共享程序段中最大程序段的大小。取决于共

24、享程序段中最大程序段的大小。ABCFDE覆盖区140K（）覆盖区230K（）A（10K）A10KB20KC30KD15KE30KF40K（a）进程各程序段的调用关系（b）覆盖结构 图4-9 覆盖示例覆盖技术综合题进程的同步最高响应比优先调度算法 最短剩余时间优先调度算法银行家算法磁盘调度算法页面置换算法1.1.假定有假定有3 3个进程个进程R R、W1W1、W2W2共享一个缓冲区共享一个缓冲区B B，B B中每次只能存放一个整数。进程中每次只能存放一个整数。进程R R从输入设备读入一从输入设备读入一个数进缓冲区个数进缓冲区B B。若读入的是奇数，则由进程。若读入的是奇数，则由进程W1W1取出打

25、印；若读入的是偶数，则由进程取出打印；若读入的是偶数，则由进程W2W2取出打印。取出打印。规定不能重复从规定不能重复从B B中取数打印。试写出同步算法。中取数打印。试写出同步算法。解：需要设置解：需要设置3个信号量：个信号量：（1）信号量）信号量empty用于表示进程用于表示进程R可向缓冲区可向缓冲区B中读入的整数的个数，初值为中读入的整数的个数，初值为1，表示进程，表示进程R能读入一个整数到能读入一个整数到缓冲区缓冲区B中。中。（2）信号量）信号量SW1的初值为的初值为0，表示开始时缓冲区，表示开始时缓冲区B中没有奇数可供进程中没有奇数可供进程W1读取。读取。SW1控制控制R与与W1之间的同

26、步。之间的同步。（3）信号量）信号量SW2的初值为的初值为0，表示开始时缓冲区，表示开始时缓冲区B中没有偶数可供进程中没有偶数可供进程W2读取。读取。SW2控制控制R与与W2之间的同步。之间的同步。使用信号量机制对这三个进程的同步算法描述如下：使用信号量机制对这三个进程的同步算法描述如下：Semaphore empty,SW1,SW2; /首先定义3个信号量empty.value=1;SW1.value=0;SW2.value=0;cobegincoendprocess R() int x; while(1) 从输入设备上读一个整数到x； P(empty); B=x; if(x%2=1) V(

27、SW1); else V(SW2); process W1() int y; while(1) P(SW1); /收到R发过来的信号，已产生一个奇数 y=B; /取出缓冲区B中的奇数到变量y中 打印打印y中的数中的数; /注意要先打印缓冲区B中存放的整数，再向R发送信号 V(empty); /向R发出信号，使进程R又可以向缓冲区B读入一个整数 process W2() int z; while(1) P(SW2); /收到进程R发过来的信号，已产生一个偶数 z=B; /取出缓冲区B中的偶数到变量z中 打印打印z中的数中的数; V(empty); /向R发出信号，使进程R又可以向缓冲区B读入一个

28、整数 2、最高响应比优先调度算法、最高响应比优先调度算法 最高响应比优先调度算法可以看成是一种优先权调度算法，只是将作业的响应比当成动态优先权。这种调度算法可用于高级调度高级调度。作业在后备队列上的等待时间与要求运行时间之和称为系统对该作作业在后备队列上的等待时间与要求运行时间之和称为系统对该作业的响应时间，该时间在数值上与作业的周转时间相等业的响应时间，该时间在数值上与作业的周转时间相等。系统对该系统对该作业的响应时间与作业要求运行时间之比称为作业的响应比作业的响应时间与作业要求运行时间之比称为作业的响应比R ，它，它在数值上等于作业的带权周转时间。在数值上等于作业的带权周转时间。 最高响应

29、比优先调度算法是最高响应比优先调度算法是介于FCFS算法与SJF算法之间的一种非剥夺式调度算法非剥夺式调度算法。这种调度算法既考虑了作业的等待时间，也考虑了作业的处理时间，既照顾了短作业，也不会使长作业等待时间过长，因而有效地改善了调度性能。 作业要求运行时间作业要求运行时间作业等待时间作业要求运行时间系统响应时间R例子：某系统有例子：某系统有3个作业个作业J1、J2、J3，它们到达系统的时间分别为，它们到达系统的时间分别为9.0、9.2、9.7，所需的，所需的CPU的的时间分别为时间分别为1.5、0.4、1.0，系统确定它们全部到达后，采用最高响应比优先算法进行调度，并忽，系统确定它们全部到

30、达后，采用最高响应比优先算法进行调度，并忽略系统的调度时间，试问它们的调度顺序是什么？各自的开始执行时间、完成时间、周转时间是略系统的调度时间，试问它们的调度顺序是什么？各自的开始执行时间、完成时间、周转时间是多少？多少？解：（1）9.7时，3个作业都已经到达系统，分别计算这3个作业的响应比（即分别计算这三个作业在9.7时的带权周转时间的值），得到的结果如下：作业到达系统的时间所需CPU的时间开始执行时间完成时间周转时间带权周转时间J19.01.59.711.22.21.467J29.20.49.710.10.92.25J39.71.09.710.711.0因为在9.7时，作业J2的响应比最高

31、，所以作业J2最先投入运行。10.1时，作业J2运行结束。在此基础上，再分别计算作业J1和J3的响应比，即分别计算作业J1和J3在10.1时的带权周转时间的值，得到的结果如下：作业到达系统的时间所需CPU的时间开始执行时间完成时间周转时间带权周转时间J19.01.510.111.62.61.733J39.71.010.111.11.41.4因为在10.1时，作业J1的响应比最高，所以作业J1在作业J2运行完成之后就立即投入运行。在11.6时，作业J1运行结束。在此基础上，再计算作业J3的响应比，即计算作业J3在11.6时的带权周转时间的值，得到的结果如下：作业到达系统的时间所需CPU的时间开始

32、执行时间完成时间周转时间带权周转时间J39.71.011.612.62.92.9作业J3是在最后投入运行的。所以根据以上分析过程可得出这三个作业的调度顺序和各自的周转时间如下：例子：某系统有例子：某系统有3个作业个作业J1、J2、J3，它们到达系统的时间分别为，它们到达系统的时间分别为9.0、9.2、9.7，所需的，所需的CPU的时间分别为的时间分别为1.5、0.4、1.0，系统确定它们全部到达后，采，系统确定它们全部到达后，采用最高响应比优先算法进行调度，并忽略系统的调度时间，试问它们的调度顺用最高响应比优先算法进行调度，并忽略系统的调度时间，试问它们的调度顺序是什么？各自的开始执行时间、完

33、成时间、周转时间是多少？序是什么？各自的开始执行时间、完成时间、周转时间是多少？调度顺序作业到达时间所需CPU的时间开始执行时间完成时间周转时间2J19.01.510.111.62.61J29.20.49.710.10.93J39.71.011.612.62.93最短剩余时间优先调度算法 该算法是对短进程优先调度算法进行改造而得到的一种剥夺式调度算法，故又称为抢占式短进程优先调度算法。该算法的基本思想是：调度程序将CPU分配给就绪队列中离运行结束最近（即剩余执行时间越短）的就绪进程（线程），使之投入运行；进程（线程）在执行过程中，若新到达进程（线程）的执行时间比当前进程（线程）的剩余执行时间更

34、短，则调度程序剥夺当前进程（线程）的CPU，调度新进程（线程）执行。进程到达系统的时间所需CPU的时间/min开始执行时间结束时间周转时间/min等待时间/min带权周转时间/minP18:00508:009:2181311.62P28:10208:108:4131111.55P38:2058:208:25501P48:2568:258:31601平均周转时间 = 30.75 ， 平均等待时间 = 10.5 ， 平均带权周转时间 = 1.2925 表表3-4 最短剩余时间优先调度算法的例子最短剩余时间优先调度算法的例子表表3-4给出了给出了4个进程到达系统的时间和所需个进程到达系统的时间和所需

35、CPU的时间。由表的时间。由表3-4可知，进程可知，进程P1执行过程中，执行过程中，8:10新进程新进程P2到达，到达，P2的执行时间（的执行时间（20）小于）小于P1的剩余执行时间（的剩余执行时间（40），因此，），因此，P1暂停，暂停，P2执行；执行；P2执行过程中，执行过程中，8:20新进程新进程P3到达，到达，P3的执行时间（的执行时间（5）小于）小于P2的剩余执行时间的剩余执行时间（10），因此，），因此，P2暂停，暂停，P3执行；执行；P3在在8:25执行结束，同时又有新进程执行结束，同时又有新进程P4到达，到达，P4的执的执行时间（行时间（6）小于）小于P2的剩余执行时间（的剩余

36、执行时间（10）和）和P1的剩余执行时间（的剩余执行时间（40），于是），于是P4执行；执行；8:31进程进程P4执行结束，由于执行结束，由于P2的剩余执行时间（的剩余执行时间（10）小于）小于P1的剩余执行时间（的剩余执行时间（40），于是），于是P2执行；执行；8:41进程进程P2执行结束，最后执行执行结束，最后执行P1。书上书上87 88页页停停 时间时间 8:10 8:20在此基础上，完成此训练题：设单处理器系统中有4个进程P1、P2、P3、P4并发执行，它们到达系统的时间分别为10:00、10:10、10:20、10:25，所需的CPU的时间分别为50min、20min、5min、6

37、min，采用最短剩余时间优先调度算法进行调度，要求计算它们的开始执行时间、结束时间、周转时间、等待时间、带权周转时间、平均周转时间、平均等待时间、平均带权周转时间。4利用银行家算法避免死锁利用银行家算法避免死锁 银行家算法中所使用到的数据结构：银行家算法中所使用到的数据结构： 假设系统存在假设系统存在m类资源类资源,有有n个进程在并发执行个进程在并发执行.（1）系统可用资源向量）系统可用资源向量Available ：若Availablei= k，则表示系统中现有k个第i类资源。（2）分配矩阵）分配矩阵Allocation ：若Allocationijk，则表示进程i当前已获得k个第j类资源。（

38、3）需求矩阵）需求矩阵Need ：若Needijk，则表示当前进程i还需要k个第j类资源才能执行完成。 （4）请求向量）请求向量Requesti (i=1,2,n)：若Requestijk，则表示进程i正请求k个第j类资源。 银行家算法银行家算法 假设进程i提出资源请求Requesti，银行家算法按照以下思路决定是否满足进程i的分配请求：（1）如果RequestiNeedi，则继续往下执行，否则认为出错，因为它请求的资源数量超过了它目前还需要的资源数量。（2）如果RequestijAvailablej（j=1,2,m），则继续往下执行，否则表示目前尚无足够的资源，进程i必须等待。（3）系统试探

39、着将资源分配给进程i，并修改以下三个数据结构： AvailablejAvailablejRequestij （ j=1,2,m） AllocationijAllocationijRequestij （ j=1,2,m） NeedijNeedijRequestij （ j=1,2,m）（4）系统执行安全性算法，检查本次资源分配的安全性，若分配后系统仍处于安全状态，则正式将资源分配给进程i，否则本次分配作废，恢复原来的资源状态，让进程i等待。 检查资源分配安全性的方法如下：检查资源分配安全性的方法如下： （1）设置两个一维数组：Work包含m个数组元素，代表在检测过程中的某个时刻仍空闲的资源数量，

40、初始值等于初始值等于Available ； Finish包含n个数组元素；Finishi(i=1,2,n)代表进程i是否可以分得足够的资源而运行结束，若Finishitrue，则表示进程i可以运行结束；刚开始进行试探时，刚开始进行试探时，Finishifalse；在算法执行过程中，如果有足够的资源分配给进程i，再令Finishitrue。（2）从进程集合中找到一个能满足下述条件的进程： Finishifalse 且且 NeedijWorkj(j=1,2,m) 若找到，则执行第（3）步，否则执行第（4）步。（3）由于进程i获得资源后可以执行完成，而执行完毕后会 释放它占有的资源，故应修改以下数据

41、结构： WorkjWorkjAllocation ij （j=1,2,m） Finishitrue 再转第（2）步。（4）若所有进程的Finish数组元素值都等于数组元素值都等于true，则表示系统处于安全安全状态，否则系统处于不安全状态。 4 4银行家算法之例银行家算法之例 （书本（书本106106页）页） 假定系统中有五个进程假定系统中有五个进程P1, P2, P3, P4, P5，存在三类，存在三类资源，各种资源的数量分别为资源，各种资源的数量分别为12、7、9 。在。在T0时刻的资源分时刻的资源分配情况如下图所示。问该状态下系统是否安全？配情况如下图所示。问该状态下系统是否安全？ T0

42、时刻系统的资源分配情况时刻系统的资源分配情况 进程AllocationNeedAvailableP10 , 1 , 010 , 6 , 53 , 3 , 0P24 , 2 , 41 , 2 , 0P33 , 0 , 28 , 2 , 2P42 , 1 , 12 , 3 , 3P50 , 0 , 26 , 5 , 3T0时刻系统的安全性分析时刻系统的安全性分析 T0时刻系统的资源分配情况时刻系统的资源分配情况 进程AllocationNeedAvailableP10 , 1 , 010 , 6 , 53 , 3 , 0P24 , 2 , 41 , 2 , 0P33 , 0 , 28 , 2 ,

43、2P42 , 1 , 12 , 3 , 3P50 , 0 , 26 , 5 , 3进程WorkNeedAllocationWork+AllocationFinishP23 , 3 , 01 , 2 , 04 , 2 , 47 , 5 , 4falseP47 , 5 , 42 , 3 , 32 , 1 , 19 , 6 , 5falseP39 , 6 , 58 , 2 , 23 , 0 , 212 , 6 , 7falseP112 , 6 , 710 , 6 , 50 , 1 , 012 , 7 , 7falseP512 , 7 , 76 , 5 , 30 , 0 , 212 , 7 , 9fa

44、lsetruetruetruetruetrue由于所有进程由于所有进程的的Finish数组数组元素都等于元素都等于true，则表示，则表示系统处于系统处于安全安全状态。找到的状态。找到的安全队列为安全队列为P2、P4、P3、P1、P5 。5磁盘调度 磁盘是在一段时间内可以同时提供给多个进程使用的共享设备。当多个进程都要求访问磁盘时，应采用适当的调度算法，对各个进程访问磁盘的先后顺序进行合理安排，使所有进程对磁盘的平均访问时间最少。由于磁盘的访问时间主要由寻道时间决定，因此，也可以认为磁盘调度的目标是使所有进程的平均寻道时间最少。 磁盘调度算法，常用的有： 先来先服务 最短寻道时间优先 各种扫描

45、算法5.5.1 1 先来先服务调度算法先来先服务调度算法 先来先服务算法（先来先服务算法（FCFSFCFS）根据进程请求访问磁盘的先后次序进行调度。）根据进程请求访问磁盘的先后次序进行调度。先来先服务调度算法先来先服务调度算法假设磁头当前位于假设磁头当前位于100100号磁道上，先后有号磁道上，先后有8 8个进程依次提出访问个进程依次提出访问9090、170170、4040、110110、2020、128128、6060、8080号磁道，磁头移动一个磁道需要号磁道，磁头移动一个磁道需要3ms3ms时间，请按照先来先服务调度时间，请按照先来先服务调度算法计算完成上述各种访问的平均寻道时间。算法计

46、算完成上述各种访问的平均寻道时间。被访问的下一个磁道9017040110201286080平均寻道时间216ms磁头移动距离（磁道数）1080130709010868205.5.2 2 最短寻道时间优先调度算法最短寻道时间优先调度算法 根据请求进程要访问的磁道离当前磁头位置的远近来决定调度顺序。根据请求进程要访问的磁道离当前磁头位置的远近来决定调度顺序。这种调度算法保证了每次寻道距离最短，但并没有保证平均寻道距离最这种调度算法保证了每次寻道距离最短，但并没有保证平均寻道距离最短。短。 最短寻道时间优先调度算法最短寻道时间优先调度算法 答案答案 1假设磁头当前位于假设磁头当前位于100100号磁

47、道上，先后有号磁道上，先后有8 8个进程依次提出访问个进程依次提出访问9090、170170、4040、110110、2020、128128、6060、8080号磁道，磁头移动一个磁道需要号磁道，磁头移动一个磁道需要3ms3ms时间，请按照最短寻道时间优时间，请按照最短寻道时间优先调度算法计算完成上述各种访问的平均寻道时间。先调度算法计算完成上述各种访问的平均寻道时间。被访问的下一个磁道9080604020110128170平均寻道时间86.25ms磁头移动距离（磁道数）10102020209018429017040110201286080 (-100)1070601080284020 901

48、7040110201286080 (-90)1080502070383010 9017040110201286080 (-80)1090403060482010 9017040110201286080 (-60)10110205040682010 9017040110201286080 (-40)10130207020882010 9017040110201286080 (-20)101502090201082010 9017040110201286080 (-110)1060209020182010 9017040110201286080 (-128)1042209020182010 901

49、7040110201286080 (-170)1042209020182010 5.5.2 2 最短寻道时间优先调度算法最短寻道时间优先调度算法 根据请求进程要访问的磁道离当前磁头位置的远近来决定调度顺序。根据请求进程要访问的磁道离当前磁头位置的远近来决定调度顺序。这种调度算法保证了每次寻道距离最短，但并没有保证平均寻道距离最这种调度算法保证了每次寻道距离最短，但并没有保证平均寻道距离最短。短。 假设磁头当前位于假设磁头当前位于100100号磁道上，先后有号磁道上，先后有8 8个进程依次提出访问个进程依次提出访问9090、170170、4040、110110、2020、128128、6060、

50、8080号磁道，磁头移动一个磁道需要号磁道，磁头移动一个磁道需要3ms3ms时间，请按照最短寻道时间优时间，请按照最短寻道时间优先调度算法计算完成上述各种访问的平均寻道时间。先调度算法计算完成上述各种访问的平均寻道时间。被访问的下一个磁道1101289080604020170平均寻道时间107.25ms磁头移动距离（磁道数）10183810202020150 最短寻道时间优先调度算法最短寻道时间优先调度算法 答案答案 29017040110201286080(-100)10706010802840209017040110201286080(-110)2060701090185030901704

51、0110201286080(-128)384288101081868489017040110201286080(-90)38805010701830109017040110201286080(-80)38904010601820109017040110201286080(-60)381102010401820109017040110201286080(-40)381302010201820109017040110201286080(-20)381502010201820109017040110201286080(-170)381502010201820105 5.3 .3 扫描调度算法 又称为

52、电梯调度算法，其基本思想是：没有访问请求时磁头不动，有访问请又称为电梯调度算法，其基本思想是：没有访问请求时磁头不动，有访问请求时磁头来回扫描，每次选择磁头移动方向上离当前磁头位置最近的访问请求进求时磁头来回扫描，每次选择磁头移动方向上离当前磁头位置最近的访问请求进行处理；扫描过程中，若磁头移动方向上仍有访问请求，则继续向同一个方向扫行处理；扫描过程中，若磁头移动方向上仍有访问请求，则继续向同一个方向扫描；当磁头移动方向上不存在访问请求时则向相反方向扫描。描；当磁头移动方向上不存在访问请求时则向相反方向扫描。 被访问的下一个磁道1101281709080604020平均寻道时间：82.5ms磁

53、头移动距离（磁道数）1018428010202020扫描调度算法扫描调度算法假设磁头当前位于假设磁头当前位于100100号磁道上，先后有号磁道上，先后有8 8个进程依次提出访问个进程依次提出访问9090、170170、4040、110110、2020、128128、6060、8080号磁道，磁头移动一个磁道需要号磁道，磁头移动一个磁道需要3ms3ms时间，请按照扫描调度算法计时间，请按照扫描调度算法计算完成上述各种访问的平均寻道时间。（假设最初向磁道号增加方向扫描）算完成上述各种访问的平均寻道时间。（假设最初向磁道号增加方向扫描）5.5.4 4 循环扫描调度算法 循环扫描调度算法与扫描调度算法

54、的不同之处是将来回扫描改为单向扫描，即没有访问循环扫描调度算法与扫描调度算法的不同之处是将来回扫描改为单向扫描，即没有访问请求时磁头不动，有访问请求时磁头向一个方向扫描，若扫描方向是往磁道号增加的方向请求时磁头不动，有访问请求时磁头向一个方向扫描，若扫描方向是往磁道号增加的方向（从外向里扫描），则每次选择位于磁头位置或磁头内侧离磁头位置最近的访问请求进行处（从外向里扫描），则每次选择位于磁头位置或磁头内侧离磁头位置最近的访问请求进行处理；扫描过程中，若磁头内侧仍有访问请求，则继续向外内扫描；当磁头内侧不存在访问请理；扫描过程中，若磁头内侧仍有访问请求，则继续向外内扫描；当磁头内侧不存在访问请求

55、时，则磁头回到最外侧欲访问的磁道处，向磁道号增加的方向（向内）开始新的一趟扫描。求时，则磁头回到最外侧欲访问的磁道处，向磁道号增加的方向（向内）开始新的一趟扫描。 注意：磁道的编号为从外向内依次增加，最外层的磁道编号是注意：磁道的编号为从外向内依次增加，最外层的磁道编号是0 0。书本上的说法是错误的，。书本上的说法是错误的，请大家注意更正。请大家注意更正。被访问的下一个磁道1101281702040608090平均寻道时间：108.75ms磁头移动距离（磁道数）10184215020202010循环扫描调度算法循环扫描调度算法假设磁头当前位于假设磁头当前位于100100号磁道上，先后有号磁道上

56、，先后有8 8个进程依次提出访问个进程依次提出访问9090、170170、4040、110110、2020、128128、6060、8080号磁道，磁头移动一个磁道需要号磁道，磁头移动一个磁道需要3ms3ms时间，请按照循环扫描调度算时间，请按照循环扫描调度算法计算完成上述各种访问的平均寻道时间。（假设最初向磁道号增加方向扫描）法计算完成上述各种访问的平均寻道时间。（假设最初向磁道号增加方向扫描）6 6页面置换算法 进程执行过程中，若要访问的页面不在内存，缺页中断机构便产生缺页中断，以便将所需页面调入内存。如果此时内存已没有空闲空间来存放调入的页面，系统必须从内存中选择一个页面换出到外存，以便

57、腾出内存空间来存放调入的页面。但应将哪个页面调出，必须通过页面置换算法来确定。页面置换算法的好坏，对系统性能有重要影响。一个好的页面置换算法，应具有较低的缺页率。要求掌握三种页面置换算法：（1 1）最佳置换算法（OPTOPT） 该算法在选择页面淘汰时，把内存中以后不会再访问的页面或在最长时间内不会再访问的页面予以淘汰。（2 2）先进先出置换算法(FIFO)(FIFO) 该算法在选择页面淘汰时，首先选择当前内存中驻留时间最长的页面予以淘汰。（3 3）最近最久未使用算法(LRU)(LRU) 该算法在选择页面淘汰时，首先选择到目前为止最近一段时间内，最久没有被访问的页面予以淘汰。1 1、若给某进程在内存中分配了4 4个物理块，其页面访问顺序为1 1、3 3、4 4、5 5、2 2、3 3、4 4、8 8、6 6、7 7、5 5、6 6、5 5、4 4、2 2，进程开始运行时所有页面均未装入内存。分别