操作系统期末复习

操作系统期末考试复习,2014-06-26,考试题型和题量,一判断题共10题，1题1分，共10分二填空题共10题，1题1分，共10分三选择题共10题，1题2分，共20分四综合题共6题，1题10分，共60分,判断题1,1、引起中断的事件与CPU当前执行的程序（进程）无关。在处理高级别中断时，低级别中断能够被屏蔽。而对异常的处理一般要依赖当前程序（进程）的运行现场，而且异常不能被屏蔽，一旦发生应立即处理。2、前趋图是一个有向无循环图，前趋图中不可以存在循环。3、挂起是指暂时将一个进程从内存换出到外存。激活指解除挂起状态，将进程重新换回内存。4、在大多数操作系统中，线程被终止后并不立即释放它所占用的系统资源。5、与低级调度相关联的进程（线程）队列称为就绪队列。而与高级调度相关联的进程（线程）队列是后备队列。6、如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。7、字节多路通道以字节为信息传输单位，主要用于连接大量低速外围设备。而数组选择通道以数据块为信息传送单位，因此信息传输速率很高，主要用于连接高速外围设备。8、硬盘访问时间一般主要由寻道时间长短决定。这是因为寻道操作通常花费的时间最多。,判断题2,1、进程是进程实体的运行过程，是系统资源分配和调度的一个独立单位。2、机器指令本身在一个指令周期内执行，不可以被中断。3、进程具有异步性的特征，使得进程可能具有不同的推进顺序。4、磁盘调度的目标是使所有进程的平均寻道时间最少。5、一般情况下，目标模块（程序）和装入模块（程序）中的地址都是逻辑地址。6、根据交换的单位不同，交换技术可以分为两种具体的实现方式：整体交换（进程交换）和部分交换。7、在大多数系统中，物理地址空间只是虚拟地址空间的一个子集。8、两级页表机制解决了大页表需要连续内存空间存放的问题，但并未减少页表对内存空间的需求，页表在内存中占用的总空间并没有减少。,填空题1,1、操作系统包含了三种运行模型，分别为独立运行的内核模型、嵌入应用进程中执行的模型、作为独立进程运行的模型。2、为了使多个进程能有条不紊地运行，需要进行进程同步，即对进程的执行次序以及访问资源的顺序进行协调。协调有两种方式：进程互斥方式和进程同步方式。3、进程之间的制约关系包含：间接相互制约关系和直接相互制约关系。4、进程同步就是对并发诸进程的执行顺序进行协调，使进程的执行结果具有可再现性。5、存在以下两种低级调度方式：非抢占调度方式、抢占调度方式。6、时间片的长短受系统处理能力和系统负载状态等因素的影响。7、按照设备的信息交换单位，可将设备分成字符设备和块设备。8、根据在输入/输出过程中起的作用和与硬件的关系，可以将输入/输出软件分为四个层次：用户层输入/输出软件、设备无关软件、设备驱动程序和输入/输出中断处理程序。9、存储器管理指的是管理内部存储器。10、针对链接时间的不同，存在三种链接方式：静态链接、装入时动态链接、运行时动态链接。,填空题2,1、系统调用和过程调用的主要区别在于运行的状态不同、进入的方式不同、返回的方式不同、代码层次不同。2、在多道程序环境中，作业一般要经过调度才能执行。存在三种调度方式，它们是高级调度、低级调度、中级调度。3、正是借助PCB（或进程控制块），操作系统才能对并发进程进行有效管理和控制。4、进程互斥是指并发的各个进程必须以互斥的方式访问临界资源。5、当最高优先权优先调度算法用于低级调度时，根据是否允许发生抢占，可以将算法进一步划分成以下两种算法：非抢占式优先权算法、抢占式优先权算法。6、优先权的类型分为两种，分别是静态优先权和动态优先权。7、按照资源属性，可将设备分成独占设备、共享设备和虚拟设备。8、输入/输出控制方式包含：程序直接输入/输出控制方式、中断输入/输出控制方式、DMA输入/输出控制方式和通道输入/输出控制方式。9、计算机中的存储器分为内部存储器和外部存储器。10、根据进行地址变换时间的不同，可以将程序装入分成静态装入和运行时动态装入两种。,填空题2,1、系统调用和过程调用的主要区别在于运行的状态不同、进入的方式不同、返回的方式不同、代码层次不同。2、在多道程序环境中，作业一般要经过调度才能执行。存在三种调度方式，它们是高级调度、低级调度、中级调度。3、正是借助PCB（或进程控制块），操作系统才能对并发进程进行有效管理和控制。4、进程互斥是指并发的各个进程必须以互斥的方式访问临界资源。5、当最高优先权优先调度算法用于低级调度时，根据是否允许发生抢占，可以将算法进一步划分成以下两种算法：非抢占式优先权算法、抢占式优先权算法。6、优先权的类型分为两种，分别是静态优先权和动态优先权。7、按照资源属性，可将设备分成独占设备、共享设备和虚拟设备。8、输入/输出控制方式包含：程序直接输入/输出控制方式、中断输入/输出控制方式、DMA输入/输出控制方式和通道输入/输出控制方式。9、计算机中的存储器分为内部存储器和外部存储器。10、根据进行地址变换时间的不同，可以将程序装入分成静态装入和运行时动态装入两种。,单选题1,1、引起进程挂起的事件包括终端用户的请求、父进程请求、负荷调节的需要和操作系统的需要。2、引起进程激活的事件包括系统资源尤其是内存资源已经充裕，或者用户或父进程要求激活指定进程等。3、引起进程创建的事件包括提交批处理作业、用户登录、提供服务和应用进程请求。4、引起进程撤销的事件包括正常结束、异常结束和外界干预。5、实现进程互斥的机器指令包含：开关中断指令、测试与设置指令、交换指令。6、实现进程互斥的软件方法包含：两标志算法、三标志法。7、最高响应比优先调度算法可以看成是一种优先权调度算法，只是将作业的响应比当成动态优先权。这种调度算法可用于高级调度。8、时间片轮转调度是一种剥夺式调度算法。使用这种算法进行调度，系统耗费在进程（线程）切换上的开销比较大，而开销的大小与时间片的长短有很大的关系。9、实现实时调度的基本条件有提供必要的信息、系统处理能力强、采用抢占式调度机制、具有快速切换机制。,单选题2,1、按资源属性对计算机设备进行分类，可将其分为：共享设备、虚拟设备、独占设备。2、按照设备的使用特性，可将设备分为：存储设备和输入/输出设备。3、按信息传输速率对计算机设备进行分类，可将其分为：低速设备、中速设备和高速设备。4、按照设备的信息交换单位，可将设备分成字符设备和块设备。5.要使源程序能够运行，必须经过编译、链接、装入3个步骤。6.可变分区存储管理通常使用的数据结构包括已使用分区表、空闲区表、空闲分区链。7、固定分区存储管理使用的数据结构是分区说明表。8、不能进行进程调度和切换的情况包括在操作系统内核临界区中、中断处理过程、其它需要完全屏蔽的原子操作过程，而不包括当前进程由于某种原因进入等待状态（它是导致内核发生调度以及进程切换的事件）。9、要求掌握使用信号量实现进程同步，例子：书本第49页图2-9和第76页中的第27题。,有6个并发执行的进程Pi（i=1,2,6），若希望它们按照如下图所示的次序执行，试写出进程并发执行的算法。（书本49页图2-9）,按该图次序并发执行的程序可以描述如下：SemaphoreS8;/定义一个大小等于8的结构型信号量数组for(inti=0;i8;i+)Si.value=0;processPP()cobeginP1;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），若希望它们按照如下图所示的次序执行，试写出进程并发执行的算法。（书本76页第27题）,按该图次序并发执行的程序可以描述如下：SemaphoreS8;/定义一个大小等于8的结构型信号量数组for(inti=0;i8;i+)Si.Value=0;processPP()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,使用资源分配图检测系统是否已进入死锁状态的方法如下：（1）在资源分配图上，找出一个能满足其资源请求的进程顶点Pi，删除Pi的请求边和分配边，使之成为孤立顶点。因为在正常情况下，Pi可以获得资源继续运行，直至运行结束，而当进程Pi运行结束之后，Pi就会释放它占有的资源，相当于去掉Pi的请求边和分配边。（2）重复第（1）步，直至不能再进行删除操作为止。,(a)资源分配图不能完全简化,R1,R2,R3,P1,P2,P3,(b)资源分配图可以完全简化,R1,R2,R3,P1,P2,P3,通道程序由通道指令构成。通道指令通常包含：（1）命令码也称为操作码，它规定了本条指令要执行的操作，如读、写、控制等。（2）内存地址指明数据送入内存（读操作）或从内存取数据（写操作）的内存起始地址。（3）传输字节数指明本条指令要读/写的字节数。（4）记录结束标志标识某个记录是否结束，若为1，则表示本条指令是处理某个记录的最后一条指令。（5）通道程序结束标志标识通道程序是否结束，若为1，则表示本条指令是通道程序的最后一条指令。,通道执行如下表所示操作要求的通道程序可以将位于内存不同位置的数据分别写成个字节和个字节的两个记录。,600,900,通过采用覆盖技术，按照程序自身的逻辑结构，使不可能同时运行的程序段共享同一内存空间，从而极大地提高内存资源的利用率。例子：进程的程序正文段包括6个程序段，分别是A、B、C、D、E、F，它们之间的调用关系如图4-9（a）所示；程序段A调用程序段B和C，程序段B调用程序段D和E，程序段C调用程序段F。通过调用关系可以知道，程序段B和C之间相互没有调用关系，它们不需要同时驻留在内存，可以共享同一覆盖区。同理，程序段D、E、F也可以共享同一覆盖区，其覆盖结构如图4-9（b）所示。其中，覆盖区的大小取决于共享程序段中最大程序段的大小。,覆盖技术,综合题,进程的同步最高响应比优先调度算法最短剩余时间优先调度算法银行家算法磁盘调度算法页面置换算法,1.假定有3个进程R、W1、W2共享一个缓冲区B，B中每次只能存放一个整数。进程R从输入设备读入一个数进缓冲区B。若读入的是奇数，则由进程W1取出打印；若读入的是偶数，则由进程W2取出打印。规定不能重复从B中取数打印。试写出同步算法。,解：需要设置3个信号量：（1）信号量empty用于表示进程R可向缓冲区B中读入的整数的个数，初值为1，表示进程R能读入一个整数到缓冲区B中。（2）信号量SW1的初值为0，表示开始时缓冲区B中没有奇数可供进程W1读取。SW1控制R与W1之间的同步。（3）信号量SW2的初值为0，表示开始时缓冲区B中没有偶数可供进程W2读取。SW2控制R与W2之间的同步。使用信号量机制对这三个进程的同步算法描述如下：Semaphoreempty,SW1,SW2;/首先定义3个信号量empty.value=1;SW1.value=0;SW2.value=0;cobegincoend,processR()intx;while(1)从输入设备上读一个整数到x；P(empty);B=x;if(x%2=1)V(SW1);elseV(SW2);,processW1()inty;while(1)P(SW1);/收到R发过来的信号，已产生一个奇数y=B;/取出缓冲区B中的奇数到变量y中打印y中的数;/注意要先打印缓冲区B中存放的整数，再向R发送信号V(empty);/向R发出信号，使进程R又可以向缓冲区B读入一个整数,processW2()intz;while(1)P(SW2);/收到进程R发过来的信号，已产生一个偶数z=B;/取出缓冲区B中的偶数到变量z中打印z中的数;V(empty);/向R发出信号，使进程R又可以向缓冲区B读入一个整数,2、最高响应比优先调度算法,最高响应比优先调度算法可以看成是一种优先权调度算法，只是将作业的响应比当成动态优先权。这种调度算法可用于高级调度。作业在后备队列上的等待时间与要求运行时间之和称为系统对该作业的响应时间，该时间在数值上与作业的周转时间相等。系统对该作业的响应时间与作业要求运行时间之比称为作业的响应比R，它在数值上等于作业的带权周转时间。,最高响应比优先调度算法是介于FCFS算法与SJF算法之间的一种非剥夺式调度算法。这种调度算法既考虑了作业的等待时间，也考虑了作业的处理时间，既照顾了短作业，也不会使长作业等待时间过长，因而有效地改善了调度性能。,例子：某系统有3个作业J1、J2、J3，它们到达系统的时间分别为9.0、9.2、9.7，所需的CPU的时间分别为1.5、0.4、1.0，系统确定它们全部到达后，采用最高响应比优先算法进行调度，并忽略系统的调度时间，试问它们的调度顺序是什么？各自的开始执行时间、完成时间、周转时间是多少？,解：（1）9.7时，3个作业都已经到达系统，分别计算这3个作业的响应比（即分别计算这三个作业在9.7时的带权周转时间的值），得到的结果如下：,因为在9.7时，作业J2的响应比最高，所以作业J2最先投入运行。10.1时，作业J2运行结束。在此基础上，再分别计算作业J1和J3的响应比，即分别计算作业J1和J3在10.1时的带权周转时间的值，得到的结果如下：,因为在10.1时，作业J1的响应比最高，所以作业J1在作业J2运行完成之后就立即投入运行。在11.6时，作业J1运行结束。在此基础上，再计算作业J3的响应比，即计算作业J3在11.6时的带权周转时间的值，得到的结果如下：,作业J3是在最后投入运行的。所以根据以上分析过程可得出这三个作业的调度顺序和各自的周转时间如下：,例子：某系统有3个作业J1、J2、J3，它们到达系统的时间分别为9.0、9.2、9.7，所需的CPU的时间分别为1.5、0.4、1.0，系统确定它们全部到达后，采用最高响应比优先算法进行调度，并忽略系统的调度时间，试问它们的调度顺序是什么？各自的开始执行时间、完成时间、周转时间是多少？,3最短剩余时间优先调度算法该算法是对短进程优先调度算法进行改造而得到的一种剥夺式调度算法，故又称为抢占式短进程优先调度算法。该算法的基本思想是：调度程序将CPU分配给就绪队列中离运行结束最近（即剩余执行时间越短）的就绪进程（线程），使之投入运行；进程（线程）在执行过程中，若新到达进程（线程）的执行时间比当前进程（线程）的剩余执行时间更短，则调度程序剥夺当前进程（线程）的CPU，调度新进程（线程）执行。,表3-4最短剩余时间优先调度算法的例子,表3-4给出了4个进程到达系统的时间和所需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的剩余执行时间（10）和P1的剩余执行时间（40），于是P4执行；8:31进程P4执行结束，由于P2的剩余执行时间（10）小于P1的剩余执行时间（40），于是P2执行；8:41进程P2执行结束，最后执行P1。,书上8788页,停时间,8:10,8:20,在此基础上，完成此训练题：设单处理器系统中有4个进程P1、P2、P3、P4并发执行，它们到达系统的时间分别为10:00、10:10、10:20、10:25，所需的CPU的时间分别为50min、20min、5min、6min，采用最短剩余时间优先调度算法进行调度，要求计算它们的开始执行时间、结束时间、周转时间、等待时间、带权周转时间、平均周转时间、平均等待时间、平均带权周转时间。,4利用银行家算法避免死锁,银行家算法中所使用到的数据结构：,假设系统存在m类资源,有n个进程在并发执行.（1）系统可用资源向量Available：若Availablei=k，则表示系统中现有k个第i类资源。（2）分配矩阵Allocation：若Allocationijk，则表示进程i当前已获得k个第j类资源。（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）系统试探着将资源分配给进程i，并修改以下三个数据结构：AvailablejAvailablejRequestij（j=1,2,m）AllocationijAllocationijRequestij（j=1,2,m）NeedijNeedijRequestij（j=1,2,m）（4）系统执行安全性算法，检查本次资源分配的安全性，若分配后系统仍处于安全状态，则正式将资源分配给进程i，否则本次分配作废，恢复原来的资源状态，让进程i等待。,检查资源分配安全性的方法如下：,（1）设置两个一维数组：Work包含m个数组元素，代表在检测过程中的某个时刻仍空闲的资源数量，初始值等于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获得资源后可以执行完成，而执行完毕后会释放它占有的资源，故应修改以下数据结构：WorkjWorkjAllocationij（j=1,2,m）Finishitrue再转第（2）步。（4）若所有进程的Finish数组元素值都等于true，则表示系统处于安全状态，否则系统处于不安全状态。,4银行家算法之例（书本106页）,假定系统中有五个进程P1,P2,P3,P4,P5，存在三类资源，各种资源的数量分别为12、7、9。在T0时刻的资源分配情况如下图所示。问该状态下系统是否安全？,T0时刻系统的资源分配情况,T0时刻系统的安全性分析,T0时刻系统的资源分配情况,true,true,true,true,true,5磁盘调度,磁盘是在一段时间内可以同时提供给多个进程使用的共享设备。当多个进程都要求访问磁盘时，应采用适当的调度算法，对各个进程访问磁盘的先后顺序进行合理安排，使所有进程对磁盘的平均访问时间最少。由于磁盘的访问时间主要由寻道时间决定，因此，也可以认为磁盘调度的目标是使所有进程的平均寻道时间最少。磁盘调度算法，常用的有：先来先服务最短寻道时间优先各种扫描算法,5.1先来先服务调度算法先来先服务算法（FCFS）根据进程请求访问磁盘的先后次序进行调度。,先来先服务调度算法,假设磁头当前位于100号磁道上，先后有8个进程依次提出访问90、170、40、110、20、128、60、80号磁道，磁头移动一个磁道需要3ms时间，请按照先来先服务调度算法计算完成上述各种访问的平均寻道时间。,5.2最短寻道时间优先调度算法根据请求进程要访问的磁道离当前磁头位置的远近来决定调度顺序。这种调度算法保证了每次寻道距离最短，但并没有保证平均寻道距离最短。,最短寻道时间优先调度算法答案1,假设磁头当前位于100号磁道上，先后有8个进程依次提出访问90、170、40、110、20、128、60、80号磁道，磁头移动一个磁道需要3ms时间，请按照最短寻道时间优先调度算法计算完成上述各种访问的平均寻道时间。,9017040110201286080(-100)1070601080284020,9017040110201286080(-90)1080502070383010,9017040110201286080(-80)1090403060482010,9017040110201286080(-60)10110205040682010,9017040110201286080(-40)10130207020882010,9017040110201286080(-20)101502090201082010,9017040110201286080(-110)1060209020182010,9017040110201286080(-128)1042209020182010,9017040110201286080(-170)1042209020182010,5.2最短寻道时间优先调度算法根据请求进程要访问的磁道离当前磁头位置的远近来决定调度顺序。这种调度算法保证了每次寻道距离最短，但并没有保证平均寻道距离最短。,假设磁头当前位于100号磁道上，先后有8个进程依次提出访问90、170、40、110、20、128、60、80号磁道，磁头移动一个磁道需要3ms时间，请按照最短寻道时间优先调度算法计算完成上述各种访问的平均寻道时间。,最短寻道时间优先调度算法答案2,9017040110201286080(-100)1070601080284020,9017040110201286080(-110)2060701090185030,9017040110201286080(-128)38428810108186848,9017040110201286080(-90)3880501070183010,9017040110201286080(-80)3890401060182010,9017040110201286080(-60)38110201040182010,9017040110201286080(-40)38130201020182010,9017040110201286080(-20)38150201020182010,9017040110201286080(-170)38150201020182010,5.3扫描调度算法又称为电梯调度算法，其基本思想是：没有访问请求时磁头不动，有访问请求时磁头来回扫描，每次选择磁头移动方向上离当前磁头位置最近的访问请求进行处理；扫描过程中，若磁头移动方向上仍有访问请求，则继续向同一个方向扫描；当磁头移动方向上不存在访问请求时则向相反方向扫描。,扫描调度算法,假设磁头当前位于100号磁道上，先后有8个进程依次提出访问90、170、40、110、20、128、60、80号磁道，磁头移动一个磁道需要3ms时间，请按照扫描调度算法计算完成上述各种访问的平均寻道时间。（假设最初向磁道号增加方向扫描）,5.4循环扫描调度算法循环扫描调度算法与扫描调度算法的不同之处是将来回扫描改为单向扫描，即没有访问请求时磁头不动，有访问请求时磁头向一个方向扫描，若扫描方向是往磁道号增加的方向（从外向里扫描），则每次选择位于磁头位置或磁头内侧离磁头位置最近的访问请求进行处理；扫描过程中，若磁头内侧仍有访问请求，则继续向外内扫描；当磁头内侧不存在访问请求时，则磁头回到最外侧欲访问的磁道处，向磁道号增加的方向（向内）开始新的一趟扫描。注意：磁道的编号为从外向内依次增加，最外层的磁道编号是0。书本上的说法是错误的，请大家注意更正。,循环扫描调度算法,假设磁头当前位于100号磁道上，先后有8个进程依次提出访问90、170、40、110、20、128、60、80号磁道，磁头移动一个磁道需要3ms时间，请按照循环扫描调度算法计算完成上述各种访问的平均寻道时间。（假设最初向磁道号增加方向扫描）,6页面置换算法进程执行过程中，若要访问的页面不在内存，缺页中断机构便产生缺页中断，以便将所需页面调入内存。如果此时内存已没有空闲空间来存放调入的页面，系统必须从内存中选择一个页面换出到外存，以便腾出内存空间来存放调入的页面。但应将哪个页面调出，必须通过页面置换算法来确定。页面置换算法的好坏，对系统性能有重要影响。一个好的页面置换算法，应具有较低的缺页率。要求掌握三种页面置换算法：（1）最佳置换算法（OPT）该算法在选择页面淘汰时，把内存中以后不会再访问的页面或在最长时间内不会再访问的页面予以淘汰。（2）先进先出置换算法(FIFO)该算法在选