操作系统典型题汇总

1、2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） 先来先服务调度算法（先来先服务调度算法（FCFS）：）：每次调每次调 度是从就绪队列中，选择一个最先进入就度是从就绪队列中，选择一个最先进入就 绪队列的进程，把处理器分配给该进程，绪队列的进程，把处理器分配给该进程， 使之得到执行。该进程一旦占有了处理器，使之得到执行。该进程一旦占有了处理器， 它就一直运行下去，直到该进程完成或因它就一直运行下去，直到该进程完成或因 发生事件而阻塞，才退出处理器。特点：发生事件而阻塞，才退出处理器。特点： 利于长进程，而不利于短进程。利于长进程，而不利于短进程。 2021-7-12 进程进程

2、(作业作业)调度算法（调度算法（p91） 短进程（作业）优先调度算法短进程（作业）优先调度算法(SPF)：它它 是从就绪队列中选择一个估计运行时间最是从就绪队列中选择一个估计运行时间最 短的进程，将处理器分配给该进程，使之短的进程，将处理器分配给该进程，使之 占有处理器并执行，直到该进程完成或因占有处理器并执行，直到该进程完成或因 发生事件而阻塞，然后退出处理器，再重发生事件而阻塞，然后退出处理器，再重 新调度。新调度。 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） 时间片轮转调度算法时间片轮转调度算法 ：系统将所有的就系统将所有的就 绪进程按进入就绪队列的先后次序排列

3、。绪进程按进入就绪队列的先后次序排列。 每次调度时把每次调度时把CPU分配给队首进程，让分配给队首进程，让 其执行一个时间片，当时间片用完，由计其执行一个时间片，当时间片用完，由计 时器发出时钟中断，调度程序则暂停该进时器发出时钟中断，调度程序则暂停该进 程的执行，使其退出处理器，并将它送到程的执行，使其退出处理器，并将它送到 就绪队列的末尾，等待下一轮调度执行。就绪队列的末尾，等待下一轮调度执行。 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） 优先权调度算法优先权调度算法 ：它是从就绪队列中选择一个它是从就绪队列中选择一个 优先权最高的进程，让其获得处理器并执行。优先

4、权最高的进程，让其获得处理器并执行。 高响应比优先调度算法：高响应比优先调度算法：它是从就绪队列中选它是从就绪队列中选 择一个响应比最高的进程，让其获得处理器执择一个响应比最高的进程，让其获得处理器执 行，直到该进程完成或因等待事件而退出处理行，直到该进程完成或因等待事件而退出处理 器为止。特点：既照顾了短进程，又考虑了进器为止。特点：既照顾了短进程，又考虑了进 程到达的先后次序，也不会使长进程长期得不程到达的先后次序，也不会使长进程长期得不 到服务，因此是一个比较全面考虑的算法，但到服务，因此是一个比较全面考虑的算法，但 每次进行调度时，都需要对各个进程计算响应每次进行调度时，都需要对各个进

5、程计算响应 比。所以系统开销很大，比较复杂。比。所以系统开销很大，比较复杂。 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） F 作业周转时间（作业周转时间（Ti）完成时间提交时间）完成时间提交时间 F 作业平均周转时间作业平均周转时间(T)周转时间周转时间/作业个数作业个数 F 作业带权周转时间（作业带权周转时间（Wi）周转时间）周转时间/运行时间运行时间 F 响应比响应比1+等待时间等待时间/运行时间运行时间 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） F1假设有假设有4道作业，它们的提交时间及执行时间由下道作业，它们的提交时间及执行时间由下

6、 图给出。图给出。 F F计算在单道程序环境下，采用先来先服务调度算法和计算在单道程序环境下，采用先来先服务调度算法和 最短作业优先调度算法，抢占式短作业优先调度算法时最短作业优先调度算法，抢占式短作业优先调度算法时 的平均周转时间和平均带权周转时间，并指出它们的调的平均周转时间和平均带权周转时间，并指出它们的调 度顺序。度顺序。 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） F1答案答案 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） F1答案答案 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） F1答案答案 2021-7-

7、12 进程进程(作业作业)调度算法（调度算法（p91） F2在一个单处理器的计算机系统中，有四个进程在一个单处理器的计算机系统中，有四个进程P1，P2，P3， P4的到达时间和所需要的运行时间如下表所示（时间单位：小时的到达时间和所需要的运行时间如下表所示（时间单位：小时 ，以十进制计算），请问，以十进制计算），请问 F（1）分别写出采用）分别写出采用“先来先服务先来先服务”调度算法、调度算法、“短进程优先短进程优先” 和和“响应比高者优先响应比高者优先”调度算法选中进程运行的次序。调度算法选中进程运行的次序。 F（2）分别计算上述三种算法使各进程在就绪队列中的平均等待）分别计算上述三种算法使

8、各进程在就绪队列中的平均等待 时间以及三种算法下的平均周转时间。时间以及三种算法下的平均周转时间。 F（3）是否存在缩短平均周转时间的调度策略，如果存在，请提）是否存在缩短平均周转时间的调度策略，如果存在，请提 出来，写出选中进程运行的次序，并计算在就绪队列中的平均等出来，写出选中进程运行的次序，并计算在就绪队列中的平均等 待时间以及平均周转时间？待时间以及平均周转时间？ 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） F2答案答案 2021-7-12 进程进程(作业作业)调度算法（调度算法（p91） F2答案答案 F（2）从上面表格中可看出：）从上面表格中可看出： F先

9、来先服务算法的平均等待时间为：先来先服务算法的平均等待时间为：(0+7.6+11+9)/4=6.9 F 平均周转时间为：（平均周转时间为：（8+11.6+12+12）/4=10.9 F 短进程优先算法的平均等待时间为：（短进程优先算法的平均等待时间为：（0+11.6+7+5）/4=5.9 F 平均周转时间为：平均周转时间为：(8+15.6+8+8)/4=9.9 F 高响应比者优先算法的平均等待时间为：（高响应比者优先算法的平均等待时间为：（0+8.6+7+9）/4=6.15 F 平均周转时间为：平均周转时间为：(8+12.6+8+12)/4=10.15 2021-7-12 进程进程(作业作业)

10、调度算法（调度算法（p91） F2答案答案 2021-7-12 存储器连续分配方式中分区分配算法存储器连续分配方式中分区分配算法(p123) F首次适应分配算法（首次适应分配算法（FF）：）：对空闲分区表记录的要求对空闲分区表记录的要求 是按地址递增的顺序排列的，每次分配时，总是从第是按地址递增的顺序排列的，每次分配时，总是从第1 条记录开始顺序查找空闲分区表，找到第一个能满足作条记录开始顺序查找空闲分区表，找到第一个能满足作 业长度要求的空闲区，分割这个空闲区，一部分分配给业长度要求的空闲区，分割这个空闲区，一部分分配给 作业，另一部分仍为空闲区。保留了高址部分的大空闲作业，另一部分仍为空闲

11、区。保留了高址部分的大空闲 区。区。 2021-7-12 存储器连续分配方式中分区分配算法存储器连续分配方式中分区分配算法(p123) F 循环首次适应算法循环首次适应算法：每次分配均从上次分配的位置之：每次分配均从上次分配的位置之 后开始查找。后开始查找。 使内存中的空闲区分布得更均匀使内存中的空闲区分布得更均匀 F最佳适应分配算法最佳适应分配算法(BF)：是按作业要求从所有的空闲：是按作业要求从所有的空闲 分区中挑选一个能满足作业要求的最小空闲区，这样可分区中挑选一个能满足作业要求的最小空闲区，这样可 保证不去分割一个更大的区域，使装入大作业时比较容保证不去分割一个更大的区域，使装入大作业

12、时比较容 易得到满足。为实现这种算法，把空闲区按长度递增次易得到满足。为实现这种算法，把空闲区按长度递增次 序登记在空闲区表中，分配时，顺序查找。序登记在空闲区表中，分配时，顺序查找。 2021-7-12 存储器连续分配方式中分区分配算法存储器连续分配方式中分区分配算法(p123) F 最坏适应分配算法（最坏适应分配算法（WF）：）：将作业申请大小与内存将作业申请大小与内存 中所有未分配区的大小进行比较，直到找到最大的或等中所有未分配区的大小进行比较，直到找到最大的或等 于作业空间的区分配给作业。要求按空闲区大小从大到于作业空间的区分配给作业。要求按空闲区大小从大到 小的次序组成空闲区链。优先

13、使用大的自由空间，在进小的次序组成空闲区链。优先使用大的自由空间，在进 行分割后剩余空间还可以被使用。大的自由空间无法保行分割后剩余空间还可以被使用。大的自由空间无法保 留给需要大空间的作业。留给需要大空间的作业。 2021-7-12 存储器连续分配方式中分区分配算法存储器连续分配方式中分区分配算法(p123) F 假定磁盘空闲空间表表明有下列存储块空闲：假定磁盘空闲空间表表明有下列存储块空闲：13、11、 18、9、20块。有一个要求为某文件分配块。有一个要求为某文件分配10个连续磁盘块。个连续磁盘块。 F（1）如果采用首次适应分配策略，那么将分配哪个块？）如果采用首次适应分配策略，那么将分

14、配哪个块？ F（2）如果采用最佳适应分配策略，那么将分配哪个块？）如果采用最佳适应分配策略，那么将分配哪个块？ F（3）如果采用最差适应分配策略，那么将分配哪个块？）如果采用最差适应分配策略，那么将分配哪个块？ 2021-7-12 存储器连续分配方式中分区分配算法存储器连续分配方式中分区分配算法(p123) F 答案：答案：（1）分配第一个遇到满足要求的大小为）分配第一个遇到满足要求的大小为13块的空块的空 闲区。闲区。 F（2）将空闲块按大小递增顺序排列，）将空闲块按大小递增顺序排列，9、11、13、18、 20，分配第一个遇到满足要求的，大小为，分配第一个遇到满足要求的，大小为11块的空闲

15、区。块的空闲区。 F（3）将空闲块按大小递减顺序排列，）将空闲块按大小递减顺序排列，20、18、13、11、 9，分配第一个遇到满足要求的，大小为，分配第一个遇到满足要求的，大小为20块的空闲区。块的空闲区。 2021-7-12 页面置换算法页面置换算法(p149) F 最佳置换算法（最佳置换算法（OPT) ：选择以后永不使用或在最长时间：选择以后永不使用或在最长时间 内不再被访问的内存页面予以淘汰。内不再被访问的内存页面予以淘汰。 F先进先出置换算法（先进先出置换算法（FIFO）：选择最先进入内存的页面予）：选择最先进入内存的页面予 以淘汰。以淘汰。 F最近最久未使用算法（最近最久未使用算法

16、（LRU）：选择在最近一段时间内最）：选择在最近一段时间内最 久没有使用过的页，把它淘汰。久没有使用过的页，把它淘汰。 F时钟算法（时钟算法（CLOCK）：选择访问位为）：选择访问位为0的页面淘汰。的页面淘汰。 2021-7-12 页面置换算法页面置换算法(p149) F 在一个采用分页式虚拟存储管理的系统中，有一用户作业在一个采用分页式虚拟存储管理的系统中，有一用户作业 ，它依次要访问的字地址序列是，它依次要访问的字地址序列是 115,228,120,88,446,102,321,432,260,167。若分配给作业。若分配给作业 可使用的主存空间共可使用的主存空间共300个字，作业页面大小

17、为个字，作业页面大小为100个字，个字， 且第且第0页已经装入主存，请回答下列问题：页已经装入主存，请回答下列问题： F（1）按）按FIFO页面调度算法将产生多少次缺页中断？写出页面调度算法将产生多少次缺页中断？写出 依次淘汰的页号。依次淘汰的页号。 F（2）按）按LRU页面调度算法将产生多少次缺页中断？写出页面调度算法将产生多少次缺页中断？写出 依次淘汰的页号。依次淘汰的页号。 2021-7-12 页面置换算法页面置换算法(p149) F 答案：答案： F作业页面大小为作业页面大小为100个字，所以地址个字，所以地址88对应的页号为对应的页号为0， 地址地址115，102，120，167对应

18、的页号为对应的页号为1，地址，地址228，260 对应的页号为对应的页号为2，地址，地址321对应页号为对应页号为3，地址，地址446，432对对 应的页号为应的页号为4。整个访问地址序列按页写则为，。整个访问地址序列按页写则为，1，2，1，0 ，4，1，3，4，2，1。主存空间可使用空间共。主存空间可使用空间共300个字即个字即3 个页框，第个页框，第0页已经装入主存。页已经装入主存。 2021-7-12 页面置换算法页面置换算法(p149) F 答案：答案： 2021-7-12 磁盘调度磁盘调度(p194) F先来先服务（先来先服务（FCFS）：）：是按请求访问者的先后次序启动是按请求访问

19、者的先后次序启动 磁盘驱动器，而不考虑它们要访问的物理位置磁盘驱动器，而不考虑它们要访问的物理位置 F最短寻道时间优先（最短寻道时间优先（SSTF）：）：让离当前磁道最近的请求让离当前磁道最近的请求 访问者启动磁盘驱动器，即是让查找时间最短的那个作业访问者启动磁盘驱动器，即是让查找时间最短的那个作业 先执行，而不考虑请求访问者到来的先后次序，这样就克先执行，而不考虑请求访问者到来的先后次序，这样就克 服了先来先服务调度算法中磁臂移动过大的问题，但容易服了先来先服务调度算法中磁臂移动过大的问题，但容易 造成进程饥饿现象造成进程饥饿现象 2021-7-12 磁盘调度磁盘调度(p194) F扫描算法

20、（扫描算法（SCAN）或电梯调度算法：）或电梯调度算法：总是从磁臂当前位总是从磁臂当前位 置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个 柱面的访问者。如果沿磁臂的方向无请求访问时，就改变柱面的访问者。如果沿磁臂的方向无请求访问时，就改变 磁臂的移动方向。在这种调度方法下磁臂的移动类似于电磁臂的移动方向。在这种调度方法下磁臂的移动类似于电 梯的调度，所以它也称为电梯调度算法。梯的调度，所以它也称为电梯调度算法。 F循环扫描算法（循环扫描算法（CSCAN）：）：循环扫描调度算法是在扫描循环扫描调度算法是在扫描 算法的基础上改进的。磁臂改为单项

21、移动，由外向里。当算法的基础上改进的。磁臂改为单项移动，由外向里。当 前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪 个柱面的访问者。如果沿磁臂的方向无请求访问时，再回个柱面的访问者。如果沿磁臂的方向无请求访问时，再回 到最外，访问柱面号最小的作业请求。到最外，访问柱面号最小的作业请求。 2021-7-12 磁盘调度磁盘调度(p194) F设某磁盘设某磁盘,磁头刚从磁头刚从138道向道向0道方向移动。若某时刻磁盘道方向移动。若某时刻磁盘 请求分别对如下各道进行读写：请求分别对如下各道进行读写： F 201 288 140 225 117 2

22、27 168 170 试分别求试分别求FCFS 、SSTF及及SCAN磁盘调度算法响应请求的次序及磁头移动磁盘调度算法响应请求的次序及磁头移动 的总距离。的总距离。 2021-7-12 磁盘调度磁盘调度(p194) F答案答案 F(1)FCFS算法算法 F磁道访问序列：磁道访问序列： 138201188140225117227168170 F共移动共移动488个磁道个磁道 F(2)SSTF算法算法 F磁道访问序列：磁道访问序列： 138140117168170188201225227 F共移动共移动115个磁道个磁道 F(3)SCAN算法算法 F磁道访问序列：磁道访问序列： 138117140

23F共移动共移动131个磁道。个磁道。 2021-7-12 磁盘调度磁盘调度(p194) F假定磁盘的旋转速度为每圈假定磁盘的旋转速度为每圈20ms，格式化时每个磁道被，格式化时每个磁道被 分成分成10个扇区。现有个扇区。现有10个逻辑记录存放在同一磁道上，其个逻辑记录存放在同一磁道上，其 排列顺序如下表所示。排列顺序如下表所示。 F处理程序要顺序处理这些记录，每读出一个记录要花费处理程序要顺序处理这些记录，每读出一个记录要花费 4ms的时间进行处理，然后再顺序读下一个记录并进行处的时间进行处理，然后再顺序读下一个记录并进行处 理，直到处理完这些记录，请回答

24、：理，直到处理完这些记录，请回答： F（1）顺序处理完这）顺序处理完这10个记录总花费了多少时间？个记录总花费了多少时间？ F（2）请给出一种记录优化分布方案，使处理程序能在最）请给出一种记录优化分布方案，使处理程序能在最 短的时间内处理完成这短的时间内处理完成这10个记录，并计算优化时间。个记录，并计算优化时间。 2021-7-12 磁盘调度磁盘调度(p194) F答案答案 （1）顺序处理完这）顺序处理完这10个记录所费时间：个记录所费时间： 读一个记录的时间是读一个记录的时间是20/10=2ms 每条记录处理时间为每条记录处理时间为4ms.计算如下：计算如下： A记录：记录：246ms B

25、记录：因为记录：因为6ms后已转到第后已转到第4扇区，因此还要转过扇区，因此还要转过8个扇区方能到达个扇区方能到达 第第2扇区取扇区取B记录，所需时间为：记录，所需时间为：28+2+4=22ms，同样的，同样的，C、.J记录记录 和和B记录访问一样，会有记录访问一样，会有8个扇区的空转时间。个扇区的空转时间。 总的时间为：总的时间为：6229=204ms （2）要使处理程序在最短时间内处理完毕，则根据我们上面的计算，）要使处理程序在最短时间内处理完毕，则根据我们上面的计算， 把把B记录安排在第扇区记录安排在第扇区4上，把上，把C记录存放在扇区记录存放在扇区7上，上，.按照这个办法，按照这个办法

26、， 可以得到记录的优化分布如下分配：可以得到记录的优化分布如下分配： ABCDEFGHIJ 1 4 7 10 3 6 9 2 5 8 这时每处理一个记录后刚好转入下一记录扇区，这时每处理一个记录后刚好转入下一记录扇区， 所以处理时间总和为：所以处理时间总和为：10（2+4）=60ms 2021-7-12 银行家算法（银行家算法（p108） F两个判断两个判断 F假设性分配假设性分配 F安全性检查安全性检查 2021-7-12 银行家算法（银行家算法（p108） F假定一个系统有假定一个系统有4种资源，种资源，R=（6，4，4，2），当前系统），当前系统 状态如下表，该状态安全吗？请阐述理由。状

27、态如下表，该状态安全吗？请阐述理由。 2021-7-12 银行家算法（银行家算法（p108） F答案答案 F 2021-7-12 银行家算法（银行家算法（p108） F一系统具有一系统具有150个存储单元。在个存储单元。在T0时刻如下表分配给三个时刻如下表分配给三个 进程。对下列请求应用银行家算法分析是否安全？进程。对下列请求应用银行家算法分析是否安全？ F（1）第四个进程）第四个进程P4到达，最大需求到达，最大需求60个存储单元，当前个存储单元，当前 请求分配请求分配25个单元。个单元。 F（2）第四个进程）第四个进程P4到达，最大需求到达，最大需求60个存储单元，当前个存储单元，当前 请求

28、分配请求分配35个单元。个单元。 F如安全，请给出安全序列，如不安全，请说明理由如安全，请给出安全序列，如不安全，请说明理由 2021-7-12 银行家算法（银行家算法（p108） F答案答案 2021-7-12 信号量问题（信号量问题（p53） n分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问 题（具有前后执行顺序要求的）。题（具有前后执行顺序要求的）。 n对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个 或几类，通常只设置一个互斥信号量，且初值为或几类，通常只设置一个互

29、斥信号量，且初值为1，代表一次只允，代表一次只允 许一个进程对临界资源访问。许一个进程对临界资源访问。 n对同步问题要设置同步信号量，通常同步信号量的个数与参与对同步问题要设置同步信号量，通常同步信号量的个数与参与 同步的进程种类有关，即同步关系涉及几类进程，就有几个同步同步的进程种类有关，即同步关系涉及几类进程，就有几个同步 信号量。同步信号量表示该进程是否可以开始或该进程是否已经信号量。同步信号量表示该进程是否可以开始或该进程是否已经 结束。结束。 n在每个进程中用于实现互斥的在每个进程中用于实现互斥的PV操作必须成对出现；用于实现操作必须成对出现；用于实现 同步的同步的PV操作也必须成对

30、出现，但可以分别出现在不同的进程中操作也必须成对出现，但可以分别出现在不同的进程中 ；在某个进程中如果同时存在互斥与同步的；在某个进程中如果同时存在互斥与同步的P操作，则其顺序不能操作，则其顺序不能 颠倒，必须先执行对同步信号量的颠倒，必须先执行对同步信号量的P操作，再执行对互斥信号量的操作，再执行对互斥信号量的 P操作，但操作，但V操作的顺序没有严格要求。操作的顺序没有严格要求。 2021-7-12 信号量问题（信号量问题（p53） n1进程进程p1使用缓冲区使用缓冲区buffer向进程片向进程片P2，P3，P4发发 送消息，要求每当送消息，要求每当P1向向buffer中发消息时只有当中发消

31、息时只有当P2， P3，P4进程都读取这条消息后才能再向进程都读取这条消息后才能再向buffer中发送中发送 新的消息。利用新的消息。利用P，V原语进程的动作序列原语进程的动作序列 。 n2某招待所有某招待所有100个床位，住宿者住人要先登记（在个床位，住宿者住人要先登记（在 登记表上填写姓名和床位）。离去时要注销登记（在登登记表上填写姓名和床位）。离去时要注销登记（在登 记表上删去姓名和床位号）。请给出住宿及注销过程的记表上删去姓名和床位号）。请给出住宿及注销过程的 算法描述。算法描述。 n3请用信号量解决以下的请用信号量解决以下的“晕独木桥晕独木桥”问题：同一方问题：同一方 向的行人可连续

32、过桥，当某一方向有人过桥时，另一方向的行人可连续过桥，当某一方向有人过桥时，另一方 向的行人必须等待，当某一方向无人过桥时，另一方向向的行人必须等待，当某一方向无人过桥时，另一方向 的行人可以过桥。的行人可以过桥。 2021-7-12 地址变换（内存管理一章）地址变换（内存管理一章） n1若在一分页存储管理系统中，某作业若在一分页存储管理系统中，某作业 的页表如下表所示。已知页面大小为的页表如下表所示。已知页面大小为 1024字节，试将逻辑地址字节，试将逻辑地址 1011,2148,3000, 5012转化为相应的物理转化为相应的物理 地址。地址。 2021-7-12 地址变换（内存管理一章）

33、地址变换（内存管理一章） n1答案答案 n（1）逻辑地址）逻辑地址1011，除以页面大小，除以页面大小1024可知商为可知商为0，余数为，余数为1011， 则此地址页号为则此地址页号为0，页内位移为，页内位移为1011，由页表找到对应块号为，由页表找到对应块号为2，则，则 其物理地址为其物理地址为2*1024+1011=3059。 n（2）逻辑地址）逻辑地址2148，除以页面大小，除以页面大小1024可知商为可知商为2，余数为，余数为100， 则此地址页号为则此地址页号为2，页内位移为，页内位移为100，由页表找到对应块号为，由页表找到对应块号为1，则其，则其 物理地址为物理地址为1*1024+100=1124。 n（3