操作系统复习资料.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第一章 操作系统引论,*,1、当CPU执行操作系统代码时，称处理机处于（）。,A 自由态 B 目态 C D 就绪态,2、从目态到管态的转换是由（）完成的。,A 硬件 B C 用户程序 D 中断处理程序,解释：从目态到管态的转换是执行访管指令，引起一次中断，触发中断后，硬件中断机制将计算机状态置为管态。管态程序是指在管态下执行的程序。,3、操作系统提供给应用程序的接口是（）。,C,A,系统调用,1,4、简述中断处理过程。,答：当中断发生时，一旦CPU响应中断，系统就开始进行中断处理，中断处理过程如下：,（1）保护被中断进程的现场，为了在中断处理程序结束后能使进程正确的返回到中断点，系统必须保存当前处理机的状态字（PSW）和程序计数器（PC）等的值。,（2）分析中断原因，转去执行相应的中断处理程序，在多个中断请求同时发生时，处理优先级最高的中断源发出的中断请求。,（3）恢复被中断进程的现场，CPU继续执行原来被中断的进程。,2,5、简述系统调用的实现过程。,答：系统调用的一般处理过程如下：,（1）系统产生软中断，由硬件完成现场保护，并通过中断向量转向系统调用总控程序，同时处理机状态由用户态切换到核心态。,（2）系统调用总控程序根据系统调用号和系统内部的系统调用入口转入相应的系统调用处理过程。,（3）系统调用处理程序执行完毕后，返回执行成功与否以及成功时的执行结果给调用者，恢复中断进程或新调度进程的CPU现场，返回被中断进程或新进程运行。,3,1、进程与程序的关系和区别是什么？,答：进程就是可并发执行的程序在一数据集合上的一次执行过程。,进程和程序的区别主要体现在：,1）进程是动态的，具有一定的生命周期，而程序是静态的；,2）进程可并发执行，而没有创建进程的程序是不能执行的；,3）进程是操作系统中申请和分配资源的基本单位，而没有创建进程的程序是不能申请资源的；,4）进程包括程序、数据和进程控制块；,5）同一程序的多次执行对应多个进程。,4,3、什么是操作系统？从资源管理的角度来看，OS的主要功能是什么？现代OS的四大主要特征是什么？,答：从资源管理的角度来看，OS的主要功能是控制和管理计算机中的软硬件资源。现代OS的4大主要特征是：并发、共享、虚拟和不确定性。,5,4、什么叫重定位？动态重定位和静态重定位有什么区别？,答：使一个作业程序装入到与其地址空间不一致的存储空间所引起的对有关地址部分的调整过程叫重定位。,静态重定位是由作业装入程序在装入程序时一次性集中完成的，而动态重定位是由专用硬件地址变换机构在程序执行中随着指令的执行动态完成的。,6,7、请详细说明请求分页系统的地址变换过程。,答：请求分页系统的地址变换过程如下：（图略去）,1）取逻辑地址分解为页号P和页内偏移w;,2)根据页号查找页表，获得该页的描述信息；,3）若该页中断位为1，产生缺页中断；,4）更新该页的描述信息；,5）根据页块号和页内偏移w，计算物理地址。,7,5、简述分段和分页的区别。,答：分段和分页有本质的区别：,1）分段是逻辑划分，每个分段逻辑意义完整，而分页是物理划分，每个分页逻辑意义不完整；,2）分段的划分需程序员的参与，而分页的划分是操作系统完成的，对用户是透明的；,3）分段的地址空间是二维的，而分页的地址空间是一维的；,4）分段大小可变，甚至可动态扩充，而分页的大小是固定不变的；,8,14.作业的页面映象表如下图所示：（一页=一块=1024字节）,页号,块号,中断位,访问位,修改位,辅存地址,问：指出页表中中断位、访问位、修改位、辅存地址的含义？,当执行到单元的指令“，”时，系统是怎样进行地址变换（即在主存的哪个单元中）,当执行到单元指令（，）时，会发生什么现象？,9,（1）中断位：是否在内存；访问位：是否被访问过、修改位：是否被修改过；辅存地址：页面在辅存备份的地址。,（2）1000逻辑地址位于0号虚页，1800逻辑地址位于1号虚页，5号页架，对应物理地址510247765896；,（3）访问逻辑地址3600时，3600位于3号虚页，对应中断位为0，说明不在内存，产生缺页中断。,10,15.有个一虚拟存储系统,每个进程在内存占有3页数据区,刚开始时数据区为 空.有以下访页序列:2,3,4,5,3,4,1,2,3,5,1,4,2,4,5,1,3,2,1,3试给出下列情形下的缺页次数:(1)系统采用先进先出(FIFO)淘汰算法.(2)系统采用最近最少使用(LRU)淘汰算法.(3)系统采用优化(OPT)淘汰算法.,11,页面流,缺页情况,答：,（1）采用FIFO算法：,2,3,4,5,3,4,1,2,3,5,1,4,2,4,5,1,3,2,1,3,2,3,4,5,5,5,1,2,3,5,1,4,2,2,5,1,3,2,2,2,2,3,4,4,4,5,1,2,3,5,1,4,4,2,5,1,3,3,3,2,3,3,3,4,5,1,2,3,5,1,1,4,2,5,1,1,1,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,缺页次数为15。,12,（2）采用LRU算法：,2,3,4,5,3,4,1,2,3,5,1,4,2,4,5,1,3,2,1,3,2,3,4,5,3,4,1,2,3,5,1,4,2,4,5,1,3,2,1,3,2,3,4,5,3,4,1,2,3,5,1,4,2,4,5,1,3,2,1,2,3,4,5,3,4,1,2,3,5,1,1,2,4,5,1,3,2,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,缺页次数为15。,13,（2）采用OPT算法：,2,3,4,5,3,4,1,2,3,5,1,4,2,4,5,1,3,2,1,3,2,3,4,4,4,4,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,1,4,4,4,4,4,3,3,3,3,2,5,5,5,5,5,5,5,5,5,5,5,5,1,1,1,1,1,T,T,T,T,T,T,T,T,T,T,缺页次数为10。,14,1、下列选项中，降低进程优先级的合理时机是（）。,A 进程的时间片用完,B 进程刚完成I/O，进入就绪队列,C 进程长期处于就绪队列中,D 进程从就绪状态转为运行态,2、下列选项中，导致创建新进程的操作是（）。（1）用户登录成功；（2）设备分配；（3）启动程序执行,A 仅（1）和（2）B 仅（2）和（3）,C 仅（1）和（3）D（1）、（2）、（3）,A,C,15,3、下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。,A 时间片轮转调度算法 B 短进程优先调度算法,C 先来先服务调度算法 D 高响应比优先调度算法,解释：在高响应比调度算法中，响应比=（等待时间+估计作业运行时间）/估计作业运行时间。,D,16,12.多级反馈队列调度算法的原理是什么？优点是什么？,应设置多个就绪队列，并为各个队列赋予不同的优先级。当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1(i-1)队列均空时，才会调度第i队列中的进程运行。,17,19、一单道批处理系统中,有如下五个作业,并采用FCFS,SJF调度算法,试计算作业的平均周转时间和平均带权周转时间。(单位:小时),作业,提交时间,运行时间,700,25,800,2.5,900,1,4,900,050,5,1000,10,18,答,（1）FCFS算法：,7点时作业1先运行,作业,提交时间,运行时间,开始时间,结束时间,周转时间,带权周转,700,25,700,930,2.5,1,800,2.5,9.30,12.00,4,1.6,900,1,12.00,13.00,4,4,4,900,050,13.00,13.30,4.5,9,5,1000,10,13.30,14.30,6.5,6.5,19,答,（1）SJF算法：,7点时作业1先运行,作业,提交时间,运行时间,开始时间,结束时间,周转时间,带权周转,700,25,700,930,2.5,1,800,2.5,12.00,14.30,6.5,2.6,900,1,10.00,11.00,2,2,4,900,050,9.30,10.00,1,2,5,1000,10,11.00,12.00,2,2,20,20.有4个进程P1，P2，P3，P4，它们进入就绪队列的先后次序为P1，P2，P3，P4，它们的优先级和需要的处理机时间如表所示。假定这四个进程执行过程中不会发生等待事件，忽略进程调度等所花费的时间，从某个时刻开始进程调度，请写出分别采用“先来先服务”、“非抢占式优先级”（固定优先级），“时间片轮转”调度算法中进程的执行次序。计算各个进程在就绪队列中的等待时间以及平均等待时间。,进程,处理机时间,优先级,P1,8,3,P2,6,1,P3,22,5,P4,4,4,21,1）先来先服务算法,进程的执行顺序P1、P2、P3、P4；,进程P1等待时间为0；,进程P2等待时间为8；,进程P3等待时间为8614；,进程P4等待时间为862236；,平均等待时间为（0+8+14+36）/414.5,2）优先级算法,进程的执行顺序P3、P4、P1、P2；,进程P1等待时间为4+2226；,进程P2等待时间为22+4+834；,进程P3等待时间为0；,进程P4等待时间为22；,平均等待时间为（26+34+0+22）/420.5,22,3）时间片轮转算法,进程的执行顺序P1、P2、P3、P4、P1、P2、P3、P3、P3、P3；,进程P1等待时间为0（554）14；,进程P2等待时间为5（543）17；,进程P3等待时间为（55）（431）18；,进程P4等待时间为55515；,平均等待时间为（14+17+18+15）/416,23,1、进程P0和P1的共享变量定义及初值为：,Boolean flag2;int turn=0;flag0=false;flag1=false;,算法中标志数组,flag,表示进程是否希望进入临界区或是否在临界区中执行，,turn,变量用于指示允许进入临界区的进程标识。,P0,和,P1,访问临界资源的类,C,语言代码实现如下，请问能否保证互斥？会不会出现饥饿现象？,答：算法中利用,flag,解决临界资源的互斥访问，利用,turn,解决“饥饿”现象，既能解决临界资源的互斥访问，又不会出现“饥饿”现象。,void P0,while(TRUE),flag0=TRUE;,turn=1;,while(flag1,临界区；,flag0=FALSE;,void P1,while(TRUE),flag1=TRUE;,turn=0;,while(flag0,临界区；,flag1=FALSE;,24,2,、设与某资源相关联的信号量初值为,3,，当前值为,1,，若,M,表示现在资源的可用个数，,N,表示等待资源的进程数，则,M,、,N,分别是（）。,1,，,0,25,21.有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是？,范围：11-m,26,3,、三个进程,P1,、,P2,、,P3,互斥使用一个包含,N,（,N0,）个单元的缓冲区，,P1,每次用,produce,（）生成一个正整数并用,put,（）送入缓冲区的某一空单元中；,P2,每次用,getodd,（）从该缓冲区中取出一个奇数并用,countodd,（）统计奇数个数；,P3,每次用,geteven,（）从该缓冲区中取出一个偶数并用,counteven,（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。,27,解：（,1,）缓冲区是一互斥资源，因此设互斥信号量,mutex,；,（,2,）同步问题：,P1,、,P2,因为奇数的放置与取用而同步，设同步信号量,odd,；,P1,、,P3,因为偶数的放置与取用而同步，设同步信号量,even,；,P1,、,P2,、,P3,因为共享缓冲区，设同步信号量,empty,。,P1,、,P2,、,P3,的活动描述如下：,semaphore mutex=1,，,odd=0,even=0,empty=N;,进程,P1,while(true),number=produce();,wait(empty);,wait(mutex);,put();,signal(mutex);,if(number%2=0),signal(even);,else,signal(odd);,进程P2,while(true),wait(odd);,wait(mutex);,getodd();,signal(mutex);,signal(empty);,countodd();,进程P3,while(true),wait(even);,wait(mutex);,geteven();,signal(mutex);,signal(empty);,counteven();,28,2、什么是死锁？产生死锁的原因是什么？,答：两个或两个以上的进程在保持部分资源的同时等待本组其他进程占有的资源而形成的一种循环等待僵局叫死锁。,死锁产生的必要条件是：互斥条件、不剥夺条件、占有并等待条件和环路等待条件。,29,6、请详细说明可通过哪些途径预防死锁？,答：预防死锁是通过破坏死锁产生的必要条件来预防死锁发生的，具体如下：,剥夺资源法：当进程阻塞时，剥夺该进程已获得的全部资源；,全部分配法：当给进程分配资源时一次性地分配给进程所需要的全部资源，如资源不够分配，则进程一个资源都不分配；,有序资源分配法：要求进程申请同类资源时采用全部分配的方法，而申请不同类资源时，按资源类别的序号从小到大的顺序申请。,30,18、系统中有3种类型的资源（A,B,C,）和5个进程P1,P2,P3,P4,P5,A资源总数为10，B为8，C为8，在T0时刻系统状态如下表。系统采用银行家算法实施死锁避免策略。试问：,a:T0时刻此系统是否安全，若是，给出一个安全序列。,b:此时若进程P2请求资源（1，1，0），是否能实施资源分配，为什么？,c:在此基础上，若进程P1请求资源（2，0，1），能否实施资源分配，为什么？,31,最大资源需求量,已分配资源数量,A B C,A B C,P1,7 7 3,0 2 0,P2,3 3 4,2 1 0,P3,9 1 2,3 0 2,P4,2 3 3,2 1 2,P5,4 3 4,0 1 2,解：依题意可得Available（3，3，2）,a:T0时刻是安全的，安全序列为（P4,p2,p3,p5,p1）。（过程略）,b:若进程P2请求资源Req（1，1，0），按银行家算法判断如下：,32,1）判断Req(1，1，0)=Need2(1,2,4),表示Req为合法请求；,2）判断Req(1，1，0)=Available（3，3，2），表示Req为可满足的请求；,3）试探性分配,Available-=Req;变为（2，2，2）,Alloc2+=Req;变为（3，2，0）,Need2-=Req;变为（0，1，4）,4）判断新状态的安全性,新状态是安全的，可找到安全序列（P4,p2,p3,p5,p1）（具体过程在此略去）,因此可分配资源，Available变为（2,2,2）,33,c:若进程P1请求资源Req（2，0，1），按银行家算法判断如下：,1）判断Req(2,0,1)=Need1(7,5,3),表示Req为合法请求；,2）判断Req(2,0,1)=Available（2，2，2），表示Req为可满足的请求；,3）试探性分配,Available-=Req;变为（0，2，1）,Alloc1+=Req;变为（2，2，1）,Need1-=Req;变为（5，5，2）,4）判断新状态的安全性,新状态是不安全的，因为可利用资源只能满足P4后就不能满足任何进程的全部资源需求了，即找不到安全序列，此时系统进入不安全状态。,因此，不能满足进程P1的资源请求Req（2，0，1）。,34,1、本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是（）。,A 命令解释程序 B 中断处理程序,C 系统调用程序 D 用户登录程序,2、程序员利用系统调用打开I/O设备时，通常使用的设备标识是（）。,A 逻辑设备名 B 物理设备名,C 主设备号 D 从设备号,B,A,35,11.什么是块设备的延迟写？什么是预读？,答：1）当一次写操作未写满缓冲区时，就采用“延迟写”，即不急于写到设备上去，而是把这个缓冲区的标志位置上延迟写的标志，并把这个buf挂到自由buf队尾，同时留在这个设备的buf队列中。,此后，有两个时机要进行具体的写操作。,当延迟写缓存被再次按原状使用并全部写满后，用异步方式写到块设备上去。,另一个时机与缓存的再分配有关。如果一个buf已移到自由buf队首，系统准备将它分配改作他用时检测到它带有延迟写标志，则也用异步写方式将它控制的缓存内容写到块设备上去。,2）当一个进程顺序读取文件时，为加快它的前进速度，提高CPU和块设备工作的并行程度，核心还提供了预读盘块程序breada。其实现思想是：（1）核心检查第一块是否在缓冲区中，如不在，则调用磁盘驱动程序读该块。（2）如第二块不在缓冲区中，核心指示盘驱动程序异步读它。然后进程睡眠，等待第一块I/O完成。,36,13.磁盘访问时间一般要有哪几部分时间？简述磁盘调度算法中SSTF、Scan算法的原理。,1）由三部分组成：寻道时间；等待时间；传送时间。,2）SSTF算法选择从当前磁头位置出发，移动最少的磁盘I/O请求。,2）Scan算法选择在磁头前进方向上从当前位置移动最少的磁盘I/O请求执行，直至到达磁盘的另一端时才改变方向。,37,23、假设一个活动头磁盘有200道,编号从0-199.当前磁头正在143道上服务,并且刚刚完成了125道的请求.现有如下访盘请求序列(磁道号):86,147,91,177,94,150,102,175,130试给出采用下列算法后磁头移动的顺序和移动总量(总磁道数).(1).先来先服务(FCFS)磁盘调度算法.(2).最短寻道时间优先(SSTF)磁盘调度算法.(3).扫描法(SCAN)磁盘调度算法.(假设沿磁头移动方向不再有访问请求时,磁头沿相反方向移动.),38,答案:,(1)86,147,91,177,94,150,102,175,130 共565(2)当前磁头在143道上:147,150,130,102,94,91,86,175,177，共162,(3)当前磁头在143道上,并且刚刚完成125道的请求147,150,175,177,130,102,94,91,86 共125,39,3、假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空间状态,(1)请说明在上述条件下如何进行磁盘块空闲状态管理。,(2)设某单面磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相临磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号大的方向移动(如下图所示)，磁道号请求队列为50，90，30，120。对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这个扇区点共需要多少时间?要求给出计算过程。,(3)如果将磁盘替换为随机访问的Flash半导体存储器（如U盘等），是否有比CSCAN更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，也说明理由。,40,答：（1）使用位示图法表示磁盘的空闲状态，每一位表示一个磁盘块是否为空闲，共需要16384/8=2048=2KB空间。,41,（2）访问磁道的顺序为：120，30，50，90，则移动磁道长度为20+90+20+40=170，总的移动磁道时间为1701ms=170ms。,每分钟6000转，则平均旋转延迟为（60S/6000）/2=5ms，总的旋转延迟时间=5ms4=20ms。,每分钟6000转，则读取一个磁道上一个扇区的平均读取时间为10ms/100=0.1ms，总的读取扇区的时间=0.1ms4=0.4ms。,读取上述磁道上所有扇区所花的总时间=170ms+20ms+0.4ms=190.4ms。,（3）采用FCFS（先来先服务）调度策略更高效。因为Flash半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按I/O请求的先后顺序服务。,42,8、常用的文件物理结构有哪几种？试比较它们的优劣。,答：常用的文件物理结构有,1）连续文件：实现简单，支持直接存取，不便于文件的动态增加、删除。,2）链接文件：便于文件的动态增加、删除，但不支持直接存取。,3）索引文件：采用索引表，便于文件的动态增加、删除，可支持直接存取。,43,1、设置当前工作目录的主要目的是（）。,A 节省外存空间 B 节省内存空间,C 加快文件的检索速度 D加快文件的读/写速度。,2、设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1，此时，F2和F3的引用计数值分别是多少？,答：文件共享主要有两种方式，一是基于索引节点的共享方式，称为硬链接，二是利用符号链接实现文件共享，称为软链接。首先文件F1的引用计数值均为1.当建立F1的符号链接F2时，F2的引用计数值仍为1，当建立F1的硬链接文件F3时，F3的引用计数值变为2，当删除F1后，F2的引用计数值不变，而F3的引用计数值减1变1。所以F2和F3的引用计数值分别是1、1。,C,44,24.在Unix中超级块filsys的当前情况如图所示，,为某文件顺序释放了物理盘块号为276、1526、273的3个盘块，画出释放后有关部分的变化结果。如果某个文件要再分配2个盘块，分配后的结果是什么？,filsys,.,s_nfree:48,s_free0:2000,.,s_free47:1900,.,45,filsys,.,s_nfree:1,s_free0:273,.,273,.,s_nfree:50,s_free0:2000,.,s_free47:1900,s_free48:276,s_free49:1526,.,46,filsys,.,s_nfree:49,s_free0:2000,.,s_free47:1900,s_free48:276,.,273,47,