操作系统典型题汇总

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2024/11/28,进程,(,作业,),调度算法（,p91,）,先来先服务调度算法（,FCFS,）：,每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。,2024/11/28,进程,(,作业,),调度算法（,p91,）,短进程（作业）优先调度算法,(SPF),：,它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。,2024/11/28,进程,(,作业,),调度算法（,p91,）,时间片轮转调度算法：,系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把,CPU,分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。,2024/11/28,进程,(,作业,),调度算法（,p91,）,优先权调度算法：,它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。,高响应比优先调度算法：,它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。,2024/11/28,进程,(,作业,),调度算法（,p91,）,作业周转时间（,Ti,）完成时间提交时间,作业平均周转时间,(T),周转时间,/,作业个数,作业带权周转时间（,Wi,）周转时间,/,运行时间,响应比,1+,等待时间,/,运行时间,2024/11/28,进程,(,作业,),调度算法（,p91,）,1,假设有,4,道作业，它们的提交时间及执行时间由下图给出。,计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法，抢占式短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。,2024/11/28,进程,(,作业,),调度算法（,p91,）,1,答案,2024/11/28,进程,(,作业,),调度算法（,p91,）,1,答案,2024/11/28,进程,(,作业,),调度算法（,p91,）,1,答案,2024/11/28,进程,(,作业,),调度算法（,p91,）,2,在一个单处理器的计算机系统中，有四个进程,P1,，,P2,，,P3,，,P4,的到达时间和所需要的运行时间如下表所示（时间单位：小时，以十进制计算），请问,（,1,）分别写出采用“先来先服务”调度算法、“短进程优先”和“响应比高者优先”调度算法选中进程运行的次序。,（,2,）分别计算上述三种算法使各进程在就绪队列中的平均等待时间以及三种算法下的平均周转时间。,（,3,）是否存在缩短平均周转时间的调度策略，如果存在，请提出来，写出选中进程运行的次序，并计算在就绪队列中的平均等待时间以及平均周转时间？,2024/11/28,进程,(,作业,),调度算法（,p91,）,2,答案,2024/11/28,进程,(,作业,),调度算法（,p91,）,2,答案,（,2,）从上面表格中可看出：,先来先服务算法的平均等待时间为：,(0+7.6+11+9)/4=6.9,平均周转时间为：（,8+11.6+12+12,）,/4=10.9,短进程优先算法的平均等待时间为：（,0+11.6+7+5,）,/4=5.9,平均周转时间为：,(8+15.6+8+8)/4=9.9,高响应比者优先算法的平均等待时间为：（,0+8.6+7+9,）,/4=6.15,平均周转时间为：,(8+12.6+8+12)/4=10.15,2024/11/28,进程,(,作业,),调度算法（,p91,）,2,答案,2024/11/28,存储器连续分配方式中分区分配算法,(p123),首次适应分配算法（,FF,）：,对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第,1,条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。保留了高址部分的大空闲区。,2024/11/28,存储器连续分配方式中分区分配算法,(p123),循环首次适应算法,：每次分配均从上次分配的位置之后开始查找。使内存中的空闲区分布得更均匀,最佳适应分配算法,(BF),：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。,2024/11/28,存储器连续分配方式中分区分配算法,(p123),最坏适应分配算法（,WF,）：,将作业申请大小与内存中所有未分配区的大小进行比较，直到找到最大的或等于作业空间的区分配给作业。要求按空闲区大小从大到小的次序组成空闲区链。优先使用大的自由空间，在进行分割后剩余空间还可以被使用。大的自由空间无法保留给需要大空间的作业。,2024/11/28,存储器连续分配方式中分区分配算法,(p123),假定磁盘空闲空间表表明有下列存储块空闲：,13,、,11,、,18,、,9,、,20,块。有一个要求为某文件分配,10,个连续磁盘块。,（,1,）如果采用首次适应分配策略，那么将分配哪个块？,（,2,）如果采用最佳适应分配策略，那么将分配哪个块？,（,3,）如果采用最差适应分配策略，那么将分配哪个块？,2024/11/28,存储器连续分配方式中分区分配算法,(p123),答案：,（,1,）分配第一个遇到满足要求的大小为,13,块的空闲区。,（,2,）将空闲块按大小递增顺序排列，,9,、,11,、,13,、,18,、,20,，分配第一个遇到满足要求的，大小为,11,块的空闲区。,（,3,）将空闲块按大小递减顺序排列，,20,、,18,、,13,、,11,、,9,，分配第一个遇到满足要求的，大小为,20,块的空闲区。,2024/11/28,页面置换算法,(p149),最佳置换算法（,OPT),：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。,先进先出置换算法（,FIFO,）：选择最先进入内存的页面予以淘汰。,最近最久未使用算法（,LRU,）：选择在最近一段时间内最久没有使用过的页，把它淘汰。,时钟算法（,CLOCK,）：选择访问位为,0,的页面淘汰。,2024/11/28,页面置换算法,(p149),在一个采用分页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是,115,228,120,88,446,102,321,432,260,167,。若分配给作业可使用的主存空间共,300,个字，作业页面大小为,100,个字，且第,0,页已经装入主存，请回答下列问题：,（,1,）按,FIFO,页面调度算法将产生多少次缺页中断？写出依次淘汰的页号。,（,2,）按,LRU,页面调度算法将产生多少次缺页中断？写出依次淘汰的页号。,2024/11/28,页面置换算法,(p149),答案：,作业页面大小为,100,个字，所以地址,88,对应的页号为,0,，地址,115,，,102,，,120,，,167,对应的页号为,1,，地址,228,，,260,对应的页号为,2,，地址,321,对应页号为,3,，地址,446,，,432,对应的页号为,4,。整个访问地址序列按页写则为，,1,，,2,，,1,，,0,，,4,，,1,，,3,，,4,，,2,，,1,。主存空间可使用空间共,300,个字即,3,个页框，第,0,页已经装入主存。,2024/11/28,页面置换算法,(p149),答案：,2024/11/28,磁盘调度,(p194),先来先服务（,FCFS,）：,是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置,最短寻道时间优先（,SSTF,）：,让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题，但容易造成进程饥饿现象,2024/11/28,磁盘调度,(p194),扫描算法（,SCAN,）或电梯调度算法：,总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。,循环扫描算法（,CSCAN,）：,循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。,2024/11/28,磁盘调度,(p194),设某磁盘,磁头刚从,138,道向,0,道方向移动。若某时刻磁盘请求分别对如下各道进行读写：,201 288 140 225 117 227 168 170,试分别求,FCFS,、,SSTF,及,SCAN,磁盘调度算法响应请求的次序及磁头移动的总距离。,2024/11/28,磁盘调度,(p194),答案,(1)FCFS,算法,磁道访问序列：,138,201,188,140,225,117,227,168,170,共移动,488,个磁道,(2)SSTF,算法,磁道访问序列：,138,140,117,168,170,188,201,225,227,共移动,115,个磁道,(3)SCAN,算法,磁道访问序列：,138,117,140,168,170,188,201,225,227,共移动,131,个磁道。,2024/11/28,磁盘调度,(p194),假定磁盘的旋转速度为每圈,20ms,，格式化时每个磁道被分成,10,个扇区。现有,10,个逻辑记录存放在同一磁道上，其排列顺序如下表所示。,处理程序要顺序处理这些记录，每读出一个记录要花费,4ms,的时间进行处理，然后再顺序读下一个记录并进行处理，直到处理完这些记录，请回答：,（,1,）顺序处理完这,10,个记录总花费了多少时间？,（,2,）请给出一种记录优化分布方案，使处理程序能在最短的时间内处理完成这,10,个记录，并计算优化时间。,2024/11/28,磁盘调度,(p194),答案,（,1,）顺序处理完这,10,个记录所费时间：,读一个记录的时间是,20/10=2ms,每条记录处理时间为,4ms.,计算如下：,A,记录：,2,4,6ms,B,记录：因为,6ms,后已转到第,4,扇区，因此还要转过,8,个扇区方能到达,第,2,扇区取,B,记录，所需时间为：,28+2+4=22ms,，同样的，,C,、,.J,记录,和,B,记录访问一样，会有,8,个扇区的空转时间。,总的时间为：,6,229=204ms,（,2,）要使处理程序在最短时间内处理完毕，则根据我们上面的计算，,把,B,记录安排在第扇区,4,上，把,C,记录存放在扇区,7,上，,.,按照这个办法，,可以得到记录的优化分布如下分配：,ABCDEFGHIJ,1 4 7 10 3 6 9 2 5 8,这时每处理一个记录后刚好转入下一记录扇区，,所以处理时间总和为：,10,（,2+4,）,=60ms,2024/11/28,银行家算法（,p108,）,两个判断,假设性分配,安全性检查,2024/11/28,银行家算法（,p108,）,假定一个系统有,4,种资源，,R=,（,6,，,4,，,4,，,2,），当前系统状态如下表，该状态安全吗？请阐述理由。,2024/11/28,银行家算法（