《操作系统》期末最全复习题及解析_操作系统期末题库及答案

选择题

1. 若信号量S的初值为2，且有3个进程共享此信号量，则S的取值范围是（B ）。

   A.[-2，2] B.[-1，2] C.[0，2] D.[-3，2]

s最小：2-3=-1；s最大：2-0=2
1

2. 为了使A、B两个进程互斥地访问单个缓冲区，应为设置一个互斥信号量S，初值为1，相应的P(S)、V(S)作必须分别安排在（B）的两端。

   A.该单缓冲区 B.两进程的临界区 C.两进程的程序 D.两进程的控制块

并发进程中涉及相同变量的程序段叫做临界区，对这些程序段要执行（ 互斥 ）操作。

一次仅允许一个进程使用的资源叫（ 临界资源），一个进程访问这类资源的代码叫（ 临界区）。

临界区：每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，进入后不允许其他进程进入。
1

3. 操作系统处理缺页中断时，选择一种好的调度算法对主存和辅存中信息进行高效调度，尽可能地避免（ D）。

   A.碎片 B.CPU空闲 C.多重中断 D.抖动

​ 系统“抖动”现象的发生是由（ A ）引起的。

​ A.置换算法选择不当 B.交换的信息量过大 C.内存容量不足 D.请求页式管理方案

*页面抖动现象:如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集包含于工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢，把这种状态称为“抖动”。
产生抖动的原因：随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。所以OS要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。
*在请求分页存储管理中，刚被替换出去的页，立即又要被访问因无空,此时因无空闲内存，又要替换另一页，而后者又是下一次要被访问的页，于是系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，这种现象称为抖动现象。一般都是由于置换算法不佳引起
1
2
3

4. 若进程P一旦被唤醒（完成I/O操作）就能够投入运行，系统可能为（D）。

   A.在分时系统中，进程P的优先级最高

   B.抢占调度方式，就绪队列上的所有进程的优先级均比P的低

   C.就绪队列为空队列

   D.抢占调度方式，P的优先级高于当前运行的进程

两种可能：
1.就绪队列为空且CPU空闲；
2.抢占式调度，P的优先级高于当前运行进程和就绪队列上的所有进程
1
2
3

4. 在下面的I/O控制方式中，需要CPU干预最少的方式是（ D）。

A.程序I/O方式 B.中断驱动I/O控制方式 C.DMA控制方式 D.I/O通道控制方式

​ 如果I/O设备与存储设备进行数据交换不经过CPU来完成，这种数据交换方式是（B ）。

A.中断方式 B.DMA方式 C.无条件存取方式 D.程序查询方式

①程序I/O控制方式:适用于结构简单，只需少量硬件的电路；
②中断驱动I/O控制方式：适用于高效场合；
③直接存储访问DMA I/O控制方式：适用于无须CPU介入的控制器来控制内存与外设之间的数据交流的场合；(无需cpuX)
④I/O通道控制方式：适用于以字节为单位的干预，同时实现CPU，通道和I/O设备三者并行操作的场合。(最少cpu√)
1
2
3
4

6. 若P、V操作的信号量S初值为2，当前值为-1，则表示有（ 1）个等待进程。

初值为2：可用数目为2，当前值为-1：表示有1个等待进程；
S--:有一个进程获取资源，S++：有一个进程释放资源
1
2

7. 一个作业8：00到达系统，估计运行时间为1小时。若从10:00开始执行该作业，则其响应比是（ 3）。

响应比：(等待时间+服务时间）/服务时间：(10-8+1)/1=3
1

8. 在单CPU的多进程系统中，进程切换时，什么时候占用CPU以及占用多长时间取决于（进程自身和进程调度策略 ）。

   A.进程相应程序段的长度 B.进程总共需要运行时间的多少

   C.进程自身和进程调度策略 D.进程完成什么功能

进程调度的时机与进程特点有关，如进程是否为CPU繁忙型还是I/O繁忙型、自身的优先级等。但是仅这些特点是不够的，能否得到调度还取决于进程调度策略，若采用优先级调度算法，则进程的优先级才起作用。至于占用处理器运行时间的长短，则要看进程自身，若进程是I/O繁忙型，运行过程中要频繁访问I/O端口，也就是说，可能会频繁放弃CPU。所以，占用CPU的时间就不会长，一旦放弃CPU，则必须等待下次调度。若进程是CPU繁忙型，则一旦占有CPU就可能会运行很长时间，但是运行时间还取决于进程调度策略，大部分情况下，交互式系统为改善用户的响应时间，大多数采用时间片轮转的算法，这种算法在进程占用CPU达到一定时间后，会强制将其换下，以保证其他进程的CPU使用权。所以选择C选项。
1

9. 某系统中有11台打印机，n个进程共享打印机资源，每个进程要求获得3台打印机，当n的取值不超过（ 5）时，系统不会发生死锁。

给每个进程分配2台，所以当n=5.2*5=10,还剩一台打印机可以轮流使用，系统安全
1

10. 与E-mail类似的进程间数据通信机制是（消息传递 ）。

    A.消息传递 B.管道 C.共享存储区 D.信号量

进程通信方式：管道通信、
消息队列（直接通信方式：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。
间接通信方式：发送进程把消息发送到某个中间实体中，接收进程从中间实体中取得消息。这种中间实体一般称为信箱，这种通信方式又称为信箱通信方式。该通信方式广泛引用于计算机网络中，相应的通信系统称为电子邮件系统。）、
共享内存、信号量、信号、套接字
1
2
3
4

11. 在可变分区存储管理中，采用紧凑技术的目的是（合并空闲分区）。

所谓碎片是指内存中出现的一些零散的小空闲区域。由于碎片都很小，无法再利用。如果内存中碎片很多，将会造成严重的存储资源浪费。解决碎片的方法是移动所有的占用区域，使所有的空闲区合并成一片连续区域，这一技术称为移动技术（紧凑技术）。移动技术除了可解决碎片问题还使内存中的作业进行扩充。显然，移动带来系统开销加大，并且当一个作业如果正与外设进行I/O时，该作业是无法移动的。
1

12. 在请求分页存储管理中，若采用FIFO页面淘汰算法，则当分配的页面数增加时，缺页中断的次数（ 可能增加也可能减少 ）。

请求分页管理系统中，采用（ FIFO ）页面淘汰算法时，当分配的物理块增多，缺页中断次数反而会（ 增加），这就是“Belady”现象。

Belady现象是操作系统虚拟存储技术下，请求分页技术采用FIFO置换算法所特有的问题。
采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
1
2

13. 操作系统采用分页存储管理方式，要求（每个进程拥有一张页表，且进程的页表驻留在内存中 ）。

在多个进程并发执行时，所有进程的页表大多数驻留在内存中，在系统中只设置一个页表寄存器(PTR)，在其中存放页表在内存的起始地址和页表的长度。平时，进程未执行时，页表的起始地址和页表长度存放在本进程的PCB中，当调度到某进程时，才将这两个数据装入页表寄存器中。每个进程都有一个单独的逻辑地址，有一张属于自己的页表。
1

14. 文件系统采用两级索引分配方式，若每个物理块的大小是1KB，每个物理块号占4个字节（4B），则该系统中单个文件允许的最大长度是（ A）。

    A. 64kb B. 128MB C. 32MB D. 以上都不对

    因为是二级索引，所以假如第一级索引有N个指向第二级索引的指针，而二级索引有N个指向第X块的指针，则最大的文件=N*N；
    又因为每一块地址占4B，第一级索引是1kb，可以存下1k/4=256个指向二级索引指针，同理，二级最多有256个指向块的指针，所以256*256=64kb
    1
    2

    文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。

    二级索引文件最大长度 [512/3]×[512/3]=170×170=28900(块)
    三级索引文件最大长度[512/3]×[512/3]×[512/3]=170×170×170=491300(块)
    1
    2

15. 下面不适合于直接存取的外存分配方式是（B）。

    A. 连续分配 B. 链接分配 C. 索引分配 D. A~D都适合

直接存取即随机存取采用连续分配和索引分配的文件都适合于直接存取方式，只有采用链接方式分配方式的文件，不具有随机存取的特性。
1

​ 采用直接存取法来读写盘上的物理记录时，效率最高的是（ C）文件。

​ A. 串连结构 B.索引结构 C.连续结构 D.其他结构

采用直接存取方法来读写磁盘上的物理记录时，应采用连续结构的文件存储方式，因为对于连续结构的文件存储方式来说，只要知道文件在存储设备上的起始地址(首块号)和文件长度(总块数)，就能很快地进行存取；索引结构也是直接存取的，但要访问索引表；链接结构不是直接存取的。
1

16. 单处理机系统中，可并行的是（ D ）。

    I.进程与进程 II.处理机与设备 III.处理机与通道 IV.设备与设备

    A. I、II和III B. I、II和IV

    C. I、III和IV D. II、III和IV

    对于一个单CPU系统，允许若干进程同时执行，轮流占用CPU，称它们为（并发）执行的。

进程和进程之前只能并发，不能并行，注意并发和并行的区别。
并发是多个事件在同一时间间隔内发生（宏观上同时运行，微观上交替运行；并行是指多个事件在同一时刻发生。
1
2

17. 某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（ C）。

​ A. 2 B. 3 C. 4 D. 5

2*4=8，如果每个进程分配两台打印机产生死锁
1

18. 分区分配内存管理方式的主要保护措施是（A ）。

    A. 越界地址保护 B. 程序代码保护

    C. 数据保护 D. 栈保护

 分区分配存储管理方式的保护措施是设置界地址寄存器。 每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。 当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。
1

19. .一个分段存储管理系统中，地址长度为32位，其中段号占12位，则段长最大是（C ）。

    A. 2的12次方字节 B. 2的16次方字节

    C. 2的20次方字节 D. 2的32次方字节

分段存储管理中，逻辑地址分为两部分，段号和段内位移，地址总长度为32位．段号占了12位，则剩下20位表示段内位移的，则最大段长为2^20字节
1

20. 下列关于虚拟存储的叙述中，正确的是（ B ）。

    A. 虚拟存储只能基于连续分配技术

    B. 虚拟存储只能基于非连续分配技术

    C. 虚拟存储容量只受外存容量的限制

    D. 虚拟存储容量只受内存容量的限制

虚拟内存本来就是为了把所有的能用的存储空间都统一起来。所以，基于非连续分配技术看起来很适合。而虚拟内存的容量是受到内外存容量和计算机地址位数限制的。
1

21. 下列关于银行家算法的叙述中，正确的是（ A ）。

    A. 当系统处于安全状态时，系统中一定无死锁进程

    B. 银行家算法可以预防死锁

    C. 当系统处于不安全状态时，系统中一定会出现死锁进程

    D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件

    采用资源剥夺法可解除死锁，还可以采用（B ）方法解除死锁。

    A.执行并行操作 B.撤消进程 C.拒绝分配新资源 D.修改信号量

银行家算法可以避免死锁；系统处于不安全状态时，系统可能会出现死锁进程；银行家算法破坏了死锁必要条件中的循环与等待。
1

死锁的必要条件：
互斥条件、不可剥夺条件、请求和保持条件、循环等待条件
死锁的预防：
破坏“不可剥夺”条件、破坏”请求与保持条件、破坏“循环等待”条件（银行家算法是死锁避免算法）
死锁的解除：
1.资源剥夺法。将一些死锁进程暂时挂起来，并且抢占它的资源，并将这些资源分配给其他的死锁进程 ，要注意的是应该防止被挂起的进程长时间得不到资源而处于资源匮乏的状态
2.撤销进程法。强制撤销部分甚至全部死锁并剥夺这些进程的资源。撤销的原则可以按照进程优先级和撤销进程的代价高低进行。
3.进程回退法，让一或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。这个方法要求系统保持进程的历史信息，并设置还原点。
1
2
3
4
5
6
7
8

22. 下列关于进程和线程的叙述中，正确的是（ A ）。

    A. 不管系统是否支持线程，进程都是资源分配的基本单位

    B. 线程是资源分配的基本单位，进程是调度的基本单位

    C. 系统级线程和用户级线程的切换都需要内核的支持

    D. 同一进程中的各个线程拥有各自不同的地址空间

在引入线程的操作系统中，独立调度和分派的基本单位是线程，资源分配的单位是（进程 ）。

 进程是资源分配的基本单位，线程是调度的基本单位；
 在用户级线程中，有关线程管理的所有工作都由应用程序完成，无需内核的干预，内核意识不到线程的存在。；
 同一进程中的各个线程共享进程的地址空间。
1
2
3

23. 设有5个进程共享一个互斥段，如果最多允许两个进程同时进入互斥段,则所采用的互斥信号量初值应该是（ B ）。

​ A.5 B.2 C.1 D.0

若P、V操作的信号量S初值为2，当前值为-1，则表示有（ 1 ）个等待进程。

当有两个进程进入互斥段之后，第3个进程想要进入时,再执行P操作如果此时P操作的信号量+进程数<0时，会造成堵塞，所以信号量最小是-3，最多3个等待。最多允许两个进程同时进入，所以初值为2.
在有 n个进程共享一个互斥段，如果最多允许 m 个进程 (m<n) 同时进入互斥段，则信号量的变化范围是 -(n-m)到m
(其实很好理解 就是有5个需要资源的，现在最多只有2个，那么“许可证（信号量）”最多是+2，如果都借，那么最少就是-3，可以理解为打了欠条，等有空的就给欠条的)
1
2
3

24. 通道又称I/O处理机，它用于实现（A ）之间的信息传输。

    A.主存与外设 B.CPU与外设 C.主存与外存 D.CPU与外存

通道又称I/O处理器，能完成内存和设备之间的信息传送，与CPU并行地执行操作。
内存又称主存，是CPU能直接寻址访问的存储空间。
辅助存储器又称外存储器，是除计算机内存和CPU缓存以外的储存器（硬盘、光盘、U盘等）
1
2
3

25. 如果要使装入内存的目标程序，在内存中移动后能正常运行，必须要有（ B ）。

    A.静态重定位 B.动态重定位 C.动态链接 D.静态链接

    将逻辑地址转换成物理地址的工作称为（ 重定位 ），由装入程序实施的这种地址转换方式称为（ 静态重定位 ）。

    在采用多道程序设计技术的系统中，用户编写程序时使用的地址是（ 逻辑地址 ），装入内存后的地址为（物理地址 ），这种地址转换的过程叫做（重定位 ）。

重定位，通常来说把在装入时对目标程序中指令和数据地址修改的过程称为重定位。
A选项，静态重定位在逻辑地址转换为物理地址的过程中，地址变换在进程装入时一次完成，以后不再改变。程序的存储空间只能是连续的一片区域，而且在重定位之后就不能再移动。这不利于内存空间的有效使用。因此A选项错误。
B选项，是在程序执行期间每次访问内存之前进行重定位。可变分区容易产生外部碎片。由于进程的位置发生了变化，所以要对进程在内存中的地址进行修改。修改的过程就是重定位的过程，所以这种做法也叫动态重定位。因此B选项正确。
C选项，对换是指将内存中的暂时还不能被运行的进程或者暂时用不到的程序和数据，调到外存上，以便腾出足够的内存供在外存中等待的作业使用。不符合题中定义，因此C选项错误。
D选项，分页是一种操作系统里存储器管理的一种技术，可以使电脑的主存使用存储在辅助存储器中的数据。操作系统会将辅助存储器（通常是磁盘）中的数据分区成固定大小的区块，称为“页”。当不需要时，将分页由主存（通常是内存）移到辅助存储器；当需要时，再将数据取回，加载主存中。因此D选项错误。
1
2
3
4
5

26. 决定一个程序是否能占用处理机执行，是由（ C）机制决定的。

    A.内存管理 B.设备管理 C.进程调度 D.作业调度

进程调度与作业调度的不同点：
（1）作业调度是宏观调度，它决定了哪一个作业能进入主存。进程调度是微观调度，它决定各作业中的哪一个进程占有中央处理机。
（2）作业调度是选符合条件的收容态作业装入内存。进程调度是从就绪态进程中选一个占用处理机。
1
2
3

27. （ D ）与进程是一对一的关系，操作系统通过它实现地址变换。

​ A.JCB B.线程 C.目录 D.页表

页表是一种特殊的数据结构，放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。 每一个进程都拥有一个自己的页表，PCB表中有指针指向页表。
1

28. 在页式存储管理方式中，对于一逻辑页面访问请求量，最佳页面置换算法发生10次缺页，推断出其他页面置换算法可能发生的缺页次数如下，最可信的次数是（A ）。

​ A.FCFS 15次 B.LFU 9次 C.FIFO 6次 D.LRU 8次

*最佳置换算法——OPT（Optimal）置换算法
OPT是一种理想的置换算法。当要调入一页面而必须淘汰一个旧页面时，所淘汰的页面应该是以后不再访问的或距现在最长时间后再访问的页面，该置换算法的缺页中断率最低。根据其原理，我们不难发现OPT是需要知道现有作业的页面访问序列的，而实际情况中，我们不可能知道页面的访问序列的，因此OPT在实际中不可能实现，但我们常把它作为衡量其他置换算法效率的标准。
*先进先出置换算法——FIFO（First In First Out）置换算法
FIFO算法总是淘汰最先进入主存的页面，该算法比较简单，但算法效率不高。
*最近最久未用置换算法——LRU（Least Recently Used）置换算法
LRU算法总是淘汰最后一次访问时间距当前时间间隔最长的页面。该算法是一种通用算法，因而广泛被采用。
----OPT是缺页率最小的算法，所以其他置换算法缺页次数肯定大于等于10
1
2
3
4
5
6
7

29. 在存储管理中，采用覆盖与交换技术的目的是（ A ）。

    A.节省主存空间 B.物理上扩充主存容量 C.实现外存共享 D.提高CPU效率

*覆盖技术：覆盖技术的实现是把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时运行的程序段共享同一块内存区域。程序段先保存在磁盘上，当有关程序的前一部分执行结束后，把后续程序段调入内存，覆盖前面的程序段。
*交换技术：在分时系统中，用户的进程比内存能容纳的数量更多，系统将那些不再运行的进程或某一部分调出内存，暂时放在外存上的一个后备存储区，通常称为交换区，当需要运行这些进程时，再将它们装入内存
----采用覆盖交换的目的是节省主存空间 实现虚拟存储器的目的是从逻辑上扩充主存容量
1
2
3

30. 下列选项中，操作系统提供的给应用程序的接口是（ A）。

    A.系统调用 B.中断 C.库函数 D.原语

操作系统接口主要有命令接口和程序接口，其中程序接口又称为系统调用。库函数是高级语言中提供的与系统调用对应的函数(也有些库函数与系统调用无关)，目的是隐藏“访管”指令的细节，使系统调用更为方便、抽象。但要注意，库函数属于用户程序而非系统调用，是系统调用的上层。
1

31. 下列选项中，导致创进新进程的操作是（C ）。

    I用户成功登陆 II设备分配 III启动程序执行

    A.仅I和II B.仅II和III C.仅I和III D.I，II，III

引起创建进程的事件：
1、用户登录
2、作业调度
3、提供服务（用户程序提出请求）
4、应用请求（基于应用进程的需求）
----设备分配只需要分配相应的端口，有事件发生时进行中断即可，不需要额外的进程管理。
1
2
3
4
5
6

32. 某进程所要求的一次打印输出结束，该进程被（C ）。

    A.阻塞 B．执行 C．唤醒 D．挂起

挂起和睡眠是主动的，挂起恢复需要主动完成，睡眠恢复则是自动完成的，因为睡眠有一个睡眠时间，睡眠时间到则恢复到就绪态。而阻塞是被动的，是在等待某种事件或者资源的表现，一旦获得所需资源或者事件信息就自动回到就绪态。
睡眠和挂起是两种行为，阻塞则是一种状态。
----所请求的I/O完成，故被唤醒，即从阻塞态到就绪态。
1
2
3

33. 引入缓冲的主要目的是（D ）。

    A.节省内存 B.提高I/O设备的效率

    C.提高CPU的利用率 D.改善CPU和I/O设备之间速度不匹配的情况

缓冲的引入可以缓和CPU和I/O设备间（ 速度不匹配）的矛盾。

缓冲是两种不同速度设备之间的传输信息时平滑传输过程的常用手段。
引入缓冲技术的原因：
1、  为了进一步缓和CPU和I/O设备之间速度不匹配的矛盾。
2、  提高CPU与I/O设备之间的并行性。
3、  为了减少中断次数和CPU的中断处理时间。如果没有缓冲，慢速I/O设备每传一个字节就要产生一个中断，CPU必须处理该中断。如果用了缓冲技术，则慢速的I/O设备将缓冲区填满时，才向CPU发出中断，从而减少了中断次数和CPU的中断处理时间。
4、  为了解决DMA或通道方式下数据传输的瓶颈问题。DMA或通道方式都适用于成批数据传输，在无缓冲的情况下，慢速I/O设备只能一个字节一个字节的传输信息，这造成DMA方式或通道方式数据传输的瓶颈。缓冲区的设置适应了DMA或通道方式的成批数据传输方式，解决了数据传输的瓶颈问题。
1
2
3
4
5
6

填空题

1. 对待死锁，一般考虑死锁的（ 预防 ）、避免、检测和解除四个问题。
2. 一个刚刚被创建的进程有时是不能立即得到处理器运行（当有进程在运行时），这时它处于（ 就绪 ）态。

3. 设有四个作业同时到达，每个作业的执行时间均为2小时，它们在一台处理机上按单道方式运行，则平均周转时间为（ 5）小时。

周转时间=作业完成时刻-作业到达时刻；
带权周转时间=周转时间/服务时间；
平均周转时间=作业周转总时间/作业个数；
平均带权周转时间=带权周转总时间/作业个数；
1
2
3
4

平均周转：（2+4+6+8）/4=5h

4. 有m个进程共享一个同类临界资源，如使用信号量解决进程间的互斥问题，则信号量的取值范围为（ 1~-(m-1) ）。

总共一个可用资源，所以初值为1；最坏情况，有一个进程访问这个资源，m-1个进程在等待，则0-(m-1)=-(m-1)
1

5. 常用的可变分区分配算法中，（ 首次适应）算法有利于大作业装入，但会使主存低地址和高地址两端的分区利用不均衡。

(1)首次适应算法（first fit，FF）：
要求，空闲分区链以地址递增的顺序链接。每次从链首开始，直到找到第一个能满足要求的空闲分区为止。
简单来说，就是，每次都从第一个开始顺序查找，找到一块区域可以满足要求的。
优点：优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。
缺点：低址部分不断被划分，会留下许多难以利用的，很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销。
(2)循环首次适应算法（next fit，NF）：
与FF算法区别就是，不是每次都从首次开始，而是从上次找到的空闲分区的下一个空闲分区开始。（第一次查找的话也是从首页开始）。
特点：能使内存中的空闲区分布得较均匀。
(3)最佳适应算法（best，BF）：
将所有空闲分区按照空闲分区容量大小从小到大的顺序连接起来，形成一个空闲分区链。
即，每次都是找空间容量不但可以满足要求的空闲区，而且该空闲分区的容量还要最接近要求的容量大小。
优点：每次分配给文件的都是最合适该文件大小的分区。
缺点：内存中留下许多难以利用的小的空闲区（外碎片）。
(4)最坏适应算法（worst，WF）：
与BF算法相反，WF算法是按照空闲分区容量从大到小的顺序连接起来的，而且每次找空闲分区的时候也是按照空闲分区容量最大的。
特点：尽可能的分配大的分区。
缺点：使得内存缺乏大分区，可能使得后续到来的大作业无法装入内存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最佳适应：每次分配最小的内存，这种方法能使碎片尽量小；
最坏适应：每次分配最大的内存；
首次适应：地址由低到高，找出一个能满足要求的空闲分区给所需要的请求；
循环首次适应：首次适应的变种，分配内存时，从上次找到的空闲区的下一个空闲处开始查找，该算法可以使得内存中空闲区域分布的较均匀。
1
2
3
4

6. 设有8页的逻辑空间，每页有1024字节，它们被映射到32块物理存储区中，那么，逻辑地址的有效位是（ 13 ）位，物理地址至少是（ 15）位。

逻辑地址：8*1024=2^13 13位
物理地址：32*1024=2^15 15位
1
2

7. 从用户的角度看，文件系统的功能是要实现（ 按名存取）。

从用户角度来看
1、  用户可以执行创建、修改、删除、读写文件命令。
2、  用户能以合适的方式构造自己的文件。
3、  用户能在系统的控制下，共享其他用户的文件。
4、  允许用户用符号名访问文件。(按名存取)
从系统角度看
1、  系统转存和恢复文件的能力，以防止意外事故的发生。
2、  提供可靠的保护以及保密措施。
3、  负责文件的存储并对存入的文件进行保护、检索
4、  负责对文件存储空间的组织和分配。
1
2
3
4
5
6
7
8
9
10

8. 内存中各存储单元的地址是从统一的基地址顺序编址，这种地址称为（ 物理地址 ）。

逻辑地址：是指用户程序经编译后，每个目标模块以0为基地址进行的顺序编址。逻辑地址又称相对地址 。
物理地址：是指内存中各物理存储单元的地址从统一的基地址进行的顺序编址。物理地址又称绝对地址，它是数据在内存中的实际存储地址。
处理机在执行时必须使用物理地址才能从主存中存取信息，而应用程序使用的地址是逻辑地址，改地址并非处理机能正确识别的地址，故需要转换。
1
2
3

9. 磁盘访问时间分为3部分：（寻道时间 ）、旋转延迟时间和传输时间。

通常磁盘数据访问时间计算分为三个部分（实际上是四个，但是启动时间不加说明时忽略不计）：
寻道时间，也称寻找时间：磁头移动到指定磁道需要的时间
延迟时间：磁头定位到某一磁道的扇区所需要的时间
传输时间：从磁盘读出或者写入经历的时间
1
2
3
4

10. 在多级目录结构的文件系统中，可以通过（ 路径）和文件名进行文件访问。

绝对路径：目标文件在硬盘上的真实路径（最精确路径）
相对路径：相对于当前文件位置的路径
1
2

11. 面对一般用户，通过（ 操作命令 ）形式使用操作系统；面对编程人员，通过（系统调用 ）使用操作系统。

12. 进程的状态和优先级信息存放在（PCB ）中。

为了使参与并发执行的每个程序，包含数据都能独立地运行，在操作系统中必须为之配置一个专门的数据结构，称为进程控制块（PCB,Process Control Block）。进程与PCB是一一对应的，用户进程不能修改。
PCB作为独立运行基本单位的标志。
PCB能实现间断性运行方式。
PCB提供进程管理所需要的信息。
PCB提供进程调度所需要的信息。
PCB实现与其他进程的同步与通信。
1
2
3
4
5
6

13. SPOOLing系统中，作业执行时，从磁盘上的（ 输入井）中读取信息，把作业的执行结果暂时存放在磁盘上的（输出井 ）中。

SPOOLing系统：又称为假脱机系统；在联机的情况下实现的同时外围操作的技术称为SPOOLing技术，或成为假脱机技术。
组成：
1、输入井和输出井：输入井和输出井的存储区域是在磁盘上开辟出来的。输入输出井中的数据一般以文件的形式组织管理，这些文件称之为井文件。一个文件仅存放某一个进程的输入或输出数据，所有进程的数据输入或输出文件链接成一个输入输出队列。
2、输入缓存区和输出缓存区：输入缓冲区和输出缓冲区的存储区域是在内存中开辟出来的。主要用于缓和CPU和磁盘之间速度不匹配的矛盾。输入缓冲区用于暂存有输入设备传送的数据，之后再传送到输入井；输出缓冲区同理。
3、输入进程和输出进程：输入进程也称为预输入进程，用于模拟脱机输入时的外围控制机，将用户要求的数据从输入设备传送到输入缓冲区，再放到输入井。当CPU需要的时候，直接从输入井将数据读入内存。反之，输出的同理。
4、井管理程序：用于控制作业与磁盘井之间信息的交换。
1
2
3
4
5
6

14. 如果系统中有n个进程，则在等待队列中进程的个数最多为（ n ）个。

​ 在一个单CPU的多道程序设计系统中，若在某一时刻有N个进程同时存在，那么处于运行态、阻塞态和就绪态进程个数的最小值和最大值分别可能是多少？

运行态：0~1

阻塞态（等待):0~N

就绪态：0~N-1

15. 若使当前运行的进程总是优先级最高的进程，应选择（ 抢占式优先级调度 ）进程调度算法。

非抢占式（Nonpreemptive）   让进程运行直到结束或阻塞的调度方式容易实现适合专用系统，不适合通用系统   
抢占式（Preemptive）   允许将逻辑上可继续运行的在运行过程暂停的调度方式可防止单一进程长时间独占CPU系统开销大（降低途径：硬件实现进程切换，或扩充主存以贮存大部分程序）
1
2

16. 目前认为逻辑文件有两种类型，即（ 有结构 ）文件与（无结构 ）文件。

文件的逻辑结构是指文件的数据组织形式，可以分为有结构的记录式文件和无结构的字符流式文件。
1

17. 有n个并发进程竞争必须互斥使用的共享资源时，若某进程作为第一个使用资源者调用P操作后，则这时信号量的值为（0）

进程互斥使用资源时，进程调用了P操作，成为了第一个使用资源者，因此，此时没有可用资源，即信号量为0。
1

PV操作由P操作原语和V操作原语组成（原语是不可中断的过程)。对信号量进行操作，具体定义如下：
P（S）： ①将信号量S的值减1，即S = S - 1；
②如果s >= 0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。
V（S）：①将信号量S的值加1，即S = S + 1；
②如果S > 0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。
一般来说，信号量S >= 0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S <= 0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。也就是说，有一个未被占用的资源就可以让一个阻塞的进程执行，而不是S为正是才可以执行。
1
2
3
4
5
6

18. 段页式管理中，每取一数据，要访问（ 3）次内存。

第一次获一级页表，第二次获二级页表，第三次存取数据
在段页式存储管理系统中，若不考虑快表，则为了获得1条指令或数据，至少须访问3次内存
1
2

19. 虚拟设备是通过（ Spooling ）技术把（ 独占设备）变成能为若干用户共享的设备。

如果说，通过多道程序技术可将一台物理CPU虚拟为多台逻辑CPU，从而允许多个用户共享一台主机。那么，通过假脱机（Spooling） 技术，可以将一台物理I/O设备虚拟为多台逻辑I/O设备，这样也就允许多个用户共享一台物理I/O设备。
1

20. 设备管理的（ 设备无关系/设备独立性 ）功能来实现使用用户所编制的程序与实际使用的物理设备无关。
21. 在直接通信方式中，系统通常提供的两条通信原语为（send(receiver,message) ），（receive(sender,message) ）。

直接通信原语
对称寻址方式 —— 要求发送进程和接收进程都必须以显式方式提供对方的标识符。
系统提供以下两条通信命令：
send(receiver,message);
receive(sender,message);
1
2
3
4
5

22. 设一段表

那么，逻辑地址(2, 88)对应的物理地址是（ 178 ）。逻辑地址(4, 100)对应的物理地址是（ 地址越界 ）。

逻辑地址（2，88）,即找到段号为2的第88位地址，读表可得段号为2的基地址为90，段长为100（大于88），所以不越界，且其物理地址为90+88（基地址+查找的地址）；同理可知逻辑地址为（4,100）的物理地址，读表可得段号为4的基地址为1952，段长为96（小于100），所以产生了越界。
1

24. 设有一组作业，它们的提交时间及运行时间如下表所示。则在单道方式下，采用短作业优先调度算法，作业的执行顺序是（ 1，3，4，2 ）。

9：00 作业1到达
10：00 作业1完成，作业2和3到达，短作业优先选择作业3调度。
10：10 作业3完成，作业4到达，短作业优先选择作业4调度
10：15 作业4完成，作业2进入运行
10：45 作业2完成
1
2
3
4
5

25. 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送到用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在双缓冲区结构下，读入并分析完该文件的时间为（1100us ）。

单缓冲区总时间=(磁盘写入缓冲区时间+缓冲区读出时间)*磁盘块数+CPU处理最后一块数据的时间=(100+50)*10+50=1550us
双缓冲总时间=磁盘写入缓冲区时间*磁盘块数+读出最后一块数据时间+CPU分析最后一块数据时间=100*10+50+50=1100us
1
2

简答题

1. n个进程共享m个同类资源，若每个进程都需要用该资源，而且每个进程对该类资源的最大需求量之和小于m＋n。说明该系统不会因竞争该类资源而阻塞。

   假设最多每个进程对该类资源最大需求为x个，最坏情况每个进程分配（x-1）个，总共分配了n(x-1)个，系统还剩下m-n(x-1)。只要m-n(x-1)>=1  nx<=m+n-1，不会发生死锁。由题可知x<m+n且m,n,x都为大于0的整数，所以nx<m+n，所以nx<=m+n-1成立，系统不会发生死锁安全。
   
   1
   2

2. 简述SPOOLing系统的组成，并以共享打印机为例，说明SPOOLing系统的工作过程。

SPOOLing（即外部设备联机并行操作），即Simultaneous Peripheral Operation On-Line的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。SPOOLing系统的三大组成部分：（1）输入井和输出井；（2）输入缓冲和输出缓冲；（3）输入进程SPi和输出进程SPo 
1

​ 在实现后台打印时，SPOOLing系统应为请求I/O的进程提供那些服务？

（1）输出进程在输出井申请一空闲盘块，并将要打印的数据送入其中；
（2）输出进程为用户进程申请空白用户打印表，填入打印要求，将该表挂到请求打印队列；
（3）一旦打印机空闲，输出进程便从打印队列的队首取出一张请求打印表，根据表中要求将要打印的数据从输出井传送到内存缓冲区，再有打印机打印输出。
1
2
3

​ 试说明SPOOLing系统的组成。

输入井、输出井、输入缓冲区、输出缓冲区、输入进程、输出进程。
1

​ 什么是虚拟设备？SPOOLing技术如何使一台打印机虚拟成多台打印机？

通过某种技术，将原不能共享的独占设备变为共享设备，改造后的独占设备称为虚拟设备。
共享打印机技术指当用户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做两件事：
①由输出进程在输出井中为之申请一个空闲磁盘块区， 并将要打印的数据送入其中；
②输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。
1
2
3
4

3. 内存管理中“内零头”和“外零头”各指的是什么？在固定分区分配、可变分区分配、页式虚拟存储系统、段式存储管理系统中，各会存在何种零头？

（1）在存储管理中，内零头是指分配给作业的存储空间中未被利用的部分，外零头是指系统中无法利用的小存储块。
（2）在固定式分区分配中，为将一个用户作业装入内存，内存分配程序从系统分区表中找出一个能满足作业要求的空闲分区分配给作业，由于一个作业的大小并不一定与分区大小相等，因此，分区中有一部分存储空间浪费掉了。由此可知，固定式分区分配中存在内零头。
在可变式分区分配中，为把一个作业装入内存，应按照一定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业，如果这个空闲分区的容量比作业申 请的空间容量要大，则将该分区一分为二，一部分分配给作业，剩下的部分仍然留作系统的空闲分区。由此可知，可变式分区分配中存在外零头。
在页式虚拟存储系统中，用户作业的地址空间被划分成若干大小相等的页面，存储空间也分成也页大小相等的物理块，但一般情况下，作业的大小不可能都是物理块大小的整数倍，因此作业的最后一页中仍有部分空间被浪费掉了。由此可知，页式虚拟存储系统中存在内零头。
在段式虚拟存储系统中，作业的地址空间由若干个逻辑分段组成，每段分配一个连续的内存区，但各段之间不要求连续，其内存的分配方式类似于动态分区分配。由此可知，段式虚拟存储系统中存在外零头。 
1
2
3
4
5

4. 现有同类资源12个，供3个进程共享。假定进程所需资源和已占用资源的情况如下所示：

若此时系统又为进程A分配一个资源，则系统会出现什么现象？解释之。

会使系统进入不安全状态，可能会出现死锁
1

如果分配给A一个资源，则分配情况如下

此时可以资源为1个，提供给任意一个都无法运行，找不到安全序列。

5. 操作系统有哪几大特征？其最基本的特征是什么？

（1）操作系统具有并发、共享、虚拟和异步这四个基本特征。并发指两个或多个事件在同一时间间隔内发生；共享指系统中的资源可供内存中多个并发执行的进程（线程）共同使用；虚拟指通过某种技术把一个物理实体变为若干个逻辑上的对应物；异步性指进程是以不可欲知的速度向前推进。
（2）其最基本的特征是并发性。
1
2

6. 在请求分页系统中，页表应包括哪些数据项？

页号、物理块号、状态位、访问字段、修改位、外存地址。 
1

7. 举例说明操作系统中采用的时间换空间和空间换时间技术。

(1)时间换空间技术：虚拟存储技术/紧凑技术。增加了访问时间，但扩充了主存的逻辑容量。
(2)空间换时间技术：缓冲区技术/SPOOLING技术。减少了CPU的等待时间，缓解了速度不匹配的矛盾，但增加了外存或内存容量，将数据进行了暂存。
1
2

8. 一个计算机有6台磁带机，有n个进程竞争使用，每个进程最多需要两台。请问n为多少时，系统才不存在死锁的危险？

资源的分配情况最坏是每个进程分得最大数-1个，如果这时系统还剩一个，那么这一个分给哪个进程都将不会死锁，因此6-n(2-1)≥1时，不会发生死锁。
计算得n最大值为5个进程。
1
2

9. 设备分配时为什么应考虑安全性以及与设备的无关性？试给出一个检查系统安全性的算法。

为了提高系统的适应性和均衡性，避免死锁的产生，设备分配必须考虑安全性问题。
设备无关性使得用户的应用程序独立于实际的物理设备，不仅方便了用户，而且增加设备分配的灵活性，也便于实现I/O重定向。
利用银行家算法就是一个检查系统安全性的典型算法。
1
2
3

10. 在多道操作系统控制下，一个作业反复执行多次，它的运行时间都相同吗？为什么？

一个作业反复执行多次，它每次的运行时间可能并不相同。
由于在多道操作系统控制下，一个作业需要和其他作业创建的进程并发执行，使其在执行过程中呈现异步性，时走时停，其开始、暂停及再次获得调度的时间都是无法预知的，因此其运行时间无法确定。
1
2

11. 某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换为物理地址，转换过程中是否会发生中断？发生何种中断？

（1）该系统的逻辑地址有15位，其中高5位为页号，低10位为页内地址；物理地址14位，其中高4位为块号，低10位为块内地址。逻辑地址(OA5C)16表示为二进制数地址为000 1010 0101 1100，即其页号为00010，即2，故页号合法；从页表中找到对应的内存块号为4，即0100；与页内地址10 0101 1100拼接形成物理地址010010 0101 1100，即（125C)16           
（2）逻辑地址（103C）16的页号为4，页号合法，但该页未装入内存，故产生缺页中断。
（3）逻辑地址（1A5C）16的页号为6，为非法页号，故产生越界中断。
1
2
3

程序题

1. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题。

（1）用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。

（2）根据所定义的信号量，利用PV操作写出能正确并发执行的进程。

（1）定义一信号量S，初始值为 20 。    
意义： 
        S>0     S 的值表示可继续进入售票厅的人数 
        S=0     表示售票厅中已有20名顾客 ( 购票者 ) 
        S<0     |S| 的值为等待进入售票厅的人数        
（2）COBEGIN 
        PROCESS Pi(i=1 ， 2 ， ……) 
          begin 
           P(S);
            进入售票厅; 
            购票;
            退出; 
           V(S);
          end 
        COEND                               
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

由题每个购票者看作一个进程，所以最多容纳20个进程，少于20个可以进入，多于20个则等待。信号量S>0：可用数目为|S|；S=0：可用数目为0，表示已有20个进程；S<0,|S|表示有|S|个等待进程；
S--:有一个进程获取资源，S++：有一个进程释放资源
1
2

2. 有两个生产者a、b不断向仓库存放产品，由销售者c取走仓库中产品（仓库初态为空，仓库容量为无限大）。请写出通过P、V操作实现3个进程间的同步和互斥的框图或伪程序，并写出信号量的初值和意义。

设置两个信号量为：Product：同步信号量，初值为0；
Mutex：互斥信号量，初值为1（仓库为临界资源，描述a、b互斥使用仓库）
1
2

上图右图：生产a,b进程，存放产品（put in)，P（Mutex)=0资源开始被占用，然后V(Muxtex)释放资源；产品总量+1，所以V（Proudct)
左图：消费c进程，取出产品（take out)，产品总量-1，所以S(Product),
1
2

同步信号量：同步信号量的值为资源可以使用的个数，信号量小于0，则线程进行等待，信号量大于0，表示可用资源个数。初始值0.  
互斥信号量：只有两个值0或1，0表示资源正在被占用，线程等待。1表示，资源没有被使用，线程可以进入。初始值为1
1
2

3. a、b两点之间是一段东西向的单行道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一个方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点（b点）的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确的管理以保证行驶安全。

semaphore  S1=1,S2=1,Sab=1;  int  ab=ba=0; 

void  Pab() {
   while(1)
   {  wait(S1);
     if(ab==0)  wait(Sab);
     ab=ab+1;
signal(S1);
车辆从a点驶向b点；
wait(S1);
   ab=ab-1;
   if (ab==0)  signal(Sab);
signal(S1)
}
            }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void Pba() {
   while(1)
   {  wait(S2);
     if(ba==0) wait(Sab);
     ba=ba+1;
signal(S2);
车辆从b点驶向a点；
wait(S2);
 ba=ba-1;
 if (ba==0) signal(Sab);
signal(S2)
}
            }
1
2
3
4
5
6
7
8
9
10
11
12
13

int main()  {
cobegin
{  Pab();
   Pba();
}
return 0;
}
1
2
3
4
5
6
7

4. 公路上有一座桥，该桥一次只允许一辆汽车在桥上行驶。当桥上有汽车时，其它汽车不能上桥。试问：

   （1）这是一个同步问题还是互斥问题？

   （2）用信号量和P、V操作描述并发过程的活动。

（1）这一问题是互斥问题。桥是汽车进程互斥使用的资源。（3分）
（2）每了辆汽车对应一个进程，进程数量不确定。用Pi（i=0,1,2,…）表示汽车进程；设互斥信号量s，其初值为1。（2分）
汽车进程Pi的过程可描述如下： 
汽车进程Pi  （i=1，2,3…）
			  P(S)          
              汽车上桥           
              在桥上行驶
              汽车下桥
              V(S)         
1
2
3
4
5
6
7
8
9

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。　　
同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。
1
2

5. 有3个并发执行的进程A，B，C，它们在执行时都要读共享文件F。限定：进程A和进程B可同时读文件F，进程B和进程C也可同时读文件F，但不允许进程A和进程C同时读文件F。请回答下列问题：

   （1）用PV操作实现管理时应怎样定义信号量及其初值？

   （2）写出用PV操作管理3个进程的程序。

（1）semaphore mutex=1  //mutex为实现进程A和进程C对共享文件F的互斥访问的信号量；
（2）3个进程描述如下：
1
2

A:{
 While(1){
   P(mutex);
     读文件F;
   V(mutex);
	}
}     
1
2
3
4
5
6
7

B:{
While(1){
	读文件F；
}
1
2
3
4

C:{
While(1){
	P(mutex);
	读文件F;
	V(mutex);
   }
} 
1
2
3
4
5
6
7

综合题

1.银行家算法

在银行家算法的例子中，若出现下述资源分配情况如下表所示。

试问：（1）该状态是否安全？安全给出安全序列，不安全给出理由。

（2）若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？（要说明理由）

---

（1）如图

存在一个安全序列{P0,P3,P1,P2,P4},不会发生死锁，所以该状态安全。

（2）如果分配给P2，则如图

找不到任何一个安全序列，系统不安全所以不能分配给P2

Available:可用资源；Need：进程所需资源；Allocation：已分配的资源
只要Need<=Avaiable则可以分配，此进程运行完，释放已分配资源和可用资源，Available+Available：下一次的可用资源
安全序列可能不止一个，只要存在一个，则系统安全
1
2
3

2.页面置换算法

考虑下述页面走向： 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6，当分配的内存块数量为5时，试画出LRU、FIFO这两种置换算法的页面置换图，求置换的次数，产生了多少次缺页中断，产生缺页中断后依次淘汰的页是哪些，并计算出它们的缺页率。

页面置换图：

(1)LRU

缺页数：8

置换次数：3

淘汰页面：3，4，5

缺页率：8/20=40%

页面置换图：

（2）FIFO

缺页数：10

置换次数：5

淘汰页面：1，2，3，4，5

缺页率：10/20=50%

LRU:最近最少使用算法;FIFO:先进先出算法 缺页率：缺页数/总页数
1

3.进程调度算法

①假定在单CPU条件下有下列要执行的作业。作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。

（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。

（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？

（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？

---

（1)（2)（3)

执行时间图：非抢占式优先级算法

平均周转：（10+11+16）/3=37/3

平均带权周转：（1+4+11/3）/3 =26/9

②在一个两道的批处理操作系统中，有5个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示（注：优先数越大优先级越高）。

​ 作业号 进入时刻 估计运行时间 优先数

​ JOB1 8：00 60分钟 5

​ JOB2 8：05 15分钟 4

​ JOB3 8：20 30分钟 2

​ JOB4 8：40 25分钟 7

​ JOB5 9：10 10分钟 1

系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出。但当有新的作业投入运行时，可以按照优先级进行进程调度。

（1）试给出各个作业的运行时间序列；（例如：JOB1：8：00-8：30，9：10-9：20，…）

（2）试计算出作业的平均周转时间。

（1）如图

运行时间序列：

JOB1 8:00-9:00

JOB2 8:05-9:25 9:25-9:40

JOB3 8:20-9:40 9:40-10:10

JOB4 8:40-9:00 9:00－9:25

JOB5 9:10-9:25 9:25-10:10 10:10-10:20

（2）平均周转时间：（60+95+110+45+70）/5=76min

①8：00 1 进入
②8：05 2 到达， 2 进入就绪 1 继续运行
③9：00 1 运行完，按短作业优先 4 进入就绪，4优先级大于2，4 运行
④9：25 4 运行完，短作业优先 5 进入就绪，2优先级大于5，2 运行
⑤9：40 2 运行完，3 进入就绪，3优先级大于5，3 运行
⑥10：10 3 运行完，5 运行
⑦10：20 5 运行完
1
2
3
4
5
6
7

4.磁盘调度算法

①假设磁盘共有200个柱面，编号从0～199。当前存取臂在120号柱面上服务，并刚刚完成了105号柱面的请求。如果现有进程P1、P2、P3和P4分别请求的柱面号为186、l58、115、90。按下列3种算法调度时，试问：①系统调度的次序是什么？②存取臂移动总量为多少？

（1）先来先服务 （2）最短寻道时间优先 （3）电梯调度算法（4）循环扫描算法

（1)先来先服务

调度次序：186，156，115，90

存取臂移动总量：66+28+43+25=162

（2）最短寻道时间优先

调度次序：115，90，158，186

存取臂移动总量：5+25+68+28=126

（3）电梯调度算法

调度次序：158，186，115，90

存取臂移动总量：38+28+71+25=162

（4）循环扫描算法

调度次序：158，186，90，115

存取臂移动总量：38+28+96+25=187

如题”当前存取臂在120号柱面上服务，并刚刚完成了105号柱面的请求“所以磁臂是向着增大方向移动，否则电梯算法和循环扫描都有两种情况
先来先服务：FCFS调度;最短寻道时间优先：SSTF调度;电梯算法：SCAN调度;循环扫描算法：C-SCAN调度
1
2

②假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，设某单面磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号大的方向移动，磁道号请求队列为50、90、30、120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这4个扇区点共需要多少时间？要求给出计算过程。

---

采用CSCAN调度算法，磁道的访问次序为100→120→30→50→90

因此访问过程中移动的磁道总数为(120-100)+(120-30)+(90-30)=170，故总的寻道时间为170´1ms=170ms； （2分）

由于每转需要1/6000分钟=10ms，则平均旋转延迟时间为10ms/2 =5ms，总的旋转延迟时间为5ms´4=20ms； （2分）

由于每个磁道有100个扇区，则读取一个扇区需要10ms/100 = 0.1ms，总的读取扇区时间（传输时间）为0.1ms´4=0.4ms； （2分）

综上，磁盘访问总时间为170ms+20ms+0.4ms=190.4ms。

5.求物理/逻辑地址

①某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下表，求逻辑地址357所对应的物理地址为？2456所对应的物理地址为？

页号 = 有效地址÷每页字节数（页号=商，页内偏移量=余数）
块号：对应页号找表中的物理块号
块长：每页字节数
地址转换公式：物理地址 = 块号×块长+块内地址(页内偏移量)
1
2
3
4

357：357÷1024=0…357 页号=0 页内偏移量=357

357所对应的物理地址：5*1024+357=5477

2456：2456÷1024=2…408 页号=2 业内偏移量=408

2456所对应的物理地址：4*1024+408=4504

---

②一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如表所示：

请分别计算进程中逻辑地址为0x03B7、0x12A5、0x1432单元的物理地址（用十六进制表示），并说明理由。

块号如图依次页号为0~4
1

因为页面大小=1k=2^10,所以低十位为页内偏移量，剩下为页号

0x03B7=0000 0011 1011 0111(B) 页号：000000(B)=0(D) 页号0对应块号0x1C(H)=0001 1100(B) 物理地址=页内偏移量（低地址）物理块号（高地址），0001 1100 “+” 11 1011 0111 = 0001 1100 11 1011 0111=0111 0011 1011 0111(B)=0X73B7

0x12A5=0001 0010 1010 0101(B) 页号：000100(B)=4(D) 页号4不在内存，产生缺页

0x1432=0001 0100 0011 0010(B) 页号：000101(B)=5(D) 页号为5，产生地址越界，出错

二进制：0B-/-(B)
八进制：0O-/-(O)
十六进制：0x-/-(H)
十进制：-(D)
1
2
3
4

---

③某分页系统的逻辑地址为16位，其中高6位为页号，低10位为页内地址。请问：

（1）这样的地址结构一页有多少字节？逻辑地址可有多少页？一个作业最大的使用空间是多少？

（2）逻辑地址2318，4096，850对应的页号、页内地址分别是多少？

（1）

页的大小由页内位移所占的位数决定;
页号的位数决定了一共有多少页;
逻辑地址的位数决定了作业的最大使用空间.
1
2
3

由于低10位为页内地址，寻址能力为2^ 10=1024，1页有1024个字节（或1KB），共有页面2^ 6=64。所以一个作业最大空间是64*1024=64KB。

（2）

分页系统中每页都一样大（1KB），所以用逻辑地址除以页面大小，商为页号，余数为页内地址。
1

因此，逻辑地址2318，页号为2，页内地址为270；

逻辑地址4096，页号为4，页内地址为0；

逻辑地址850，页号为0，页内地址为850。

---

④某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换为物理地址，转换过程中是否会发生中断？发生何种中断？

（1）该系统的逻辑地址有15位，其中高5位为页号，低10位为页内地址；物理地址14位，其中高4位为块号，低10位为块内地址。逻辑地址(OA5C)16表示为二进制数地址为000 1010 0101 1100，即其页号为00010，即2，故页号合法；从页表中找到对应的内存块号为4，即0100；与页内地址10 0101 1100拼接形成物理地址010010 0101 1100，即（125C)H

（2）逻辑地址（103C)H的页号为4，页号合法，但该页未装入内存，故产生缺页中断。

（3）逻辑地址（1A5C)H的页号为6，为非法页号，故产生越界中断。

6.分页存储管理

①请求分页管理系统中，假设某进程的页表内容如下所示。

页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为10^8ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设：

① TLB初始为空；

② 地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；

③ 有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：

（1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。

（2） 基于上述访问序列，求虚地址2362H、虚地址1565H和虚地址25A5H的物理地址是多少？请说明理由。

（1）

​ 由于页面大小为4KB=2^12KB，故逻辑地址末尾12位表示页内偏移W，前4位表示页号P。 设访问内存时间为t，查找快表时间为a，处理 缺页中断的时间为T。

由此，题目可以解的：
2362H，P（页号）=2，偏移地址=362。
    1）访问快表，快表初始时为空（10ns）
    2）访问页表 100ns，此时题目中给出页号为 2 存在，取得对应得页框号（物理块号）；并且将页号 2 同步更新到快表中。
    3）通过 物理地址=页内偏移地址+页面大小*物理块号，得到物理地址，再次访问内存（主存），取得这个地址，花费 100ns。

总时间=10ns+100ns+100ns=210ns

PS：页表是常驻内存的，所以第二步是花费的 100ns。

1565H，P=1，偏移地址=565
    1）访问快表为空，10ns.（此时快表中只有刚刚更新的页号为 2 的页面）
    2）访问页表，页表中也没有，因为有效位为 0（100ns）
    3）产生缺页中断 10^8ns，此时，页表和快表都将更新新调入的页号为 1 的页面
    4）再次优先访问快表（这里没有先访问页表的原因就是第三步加粗），花费10ns
    5）合成物理地址，访问主存中取得这个地址（100ns）

总时间=10ns+100ns+10^8ns+10ns+100ns=100000220ns

25A5H，P=2，偏移地址=5A5
    1）访问快表，快表中有页号为 2 的记录（10ns）
    2）合成物理地址，并访问主存取得它（100ns）

总时间=10ns+100ns=110ns
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（2）

​ 2362H=0010 0011 0110 0010B 页号 =2 页内地址 =0011 0110 0010B=362H
​ 页表项中有效位指示在该页在内存，根据该页对应的页框号形成物理地址：254362H
​ 1565H=0001 0101 0110 0101B 页号 =1 页内地址 = 0101 0110 0101B=565H
​ 因为页1不在内存中发生缺页，根据LRU置换算法，将页0换出页1换入，所以页1对应页框号为101H，所以物理地址：101565H
​ 25A5H=0010 0101 1010 0101B 页号= 2页内地址 = 0101 1010 0101B=5A5H
​ 页表项中有效位指示在该页在内存，根据该页对应的页框号形成物理地址：2545A5H

---

②在分页存储管理系统中，页内地址12位，一次内存访问时间10ns，查询快表时间1ns，缺页处理时间1000ns。现开始执行一进程，第3号逻辑页面已经在内存，连续访问5E5F、3E4F、435F、3EA4、7E41、6B41、431A、3E40、7D88逻辑地址上的数据。假设：该进程驻留集为4，采用局部置换策略，缺页处理后指令重新开始执行，快表容量足够大，采用的LRU置换算法，试求：

（1） 页面大小是多少？

（2）这个进程依次访问哪些逻辑页面？

（3）访问上述地址序列的时，哪些地址发生了缺页中断？共发生几次？（请写出分析过程）

（4）访问地址5E5F、3E4F、3EA4的数据访问需要的时间是多少？（请列式说明）

---

（1）因为页内地址12位，所以页面大小2^12=4096=4k

（2）所以前四位为页号，如题依次访问5，3，4，3，7，6，4，3，7

（3）驻留集为4，所以有4个物理块

LRU

发生中断缺页的页是5，4，7，6，共4次缺页

（4）5E5F:1+10+1000+1+10=1022ns

查询快表1ns，访问页表10ns，页面中没有5，发生缺页1000ns，再次查询快表1ns，访问页表10ns合成物理地址
1

3E4F:1+10+10=21ns

查询快表1ns，访问页表 10ns，此时题目中给出页号为 3 存在，取得对应得页框号（物理块号）；并且将页号 3 同步更新到快表中。访问页表10ns合成物理地址
1

3EA4：1+10=11ns

查询快表1ns，访问页表10ns，页号为3存在，访问页表10ns合成物理地址
1

---

③在页式存储管理系统中，假设进程逻辑地址空间占64页，每页为1024字节，系统物理内存为2M字节。进程的页表及所有逻辑页面都已在内存中。系统有快表（TLB），其平均命中率为85%。一次内存访问需要100ns，对TLB的查找时间忽略不计，则：

（1）进程的页表项共几项？页表项中物理页帧(frame)号占几位？

（2）进程访问一个逻辑页面的平均时间是多少？

(1)因为逻辑地址占64页所以页表项共64；

​ 系统物理内存为2M所以物理页帧号为2^11=11位

(2)平均时间 0.85*100+0.15 * ( 100 + 100)=85+30=115ns。

当页表项在快表中时,查找时间忽略为0—无法确定是否在快表中可以找到
增加快表之后，需要考虑2种情况
1.访问时，可以直接在快表中访问到的
2.访问时，在快表中找不到，需要在内存中访问，依次访问页表，和物理块----一共访问2次
所以综上所述：两种情况综合考虑
快表中命中率85%
那剩余不能在快表中找到：15%
1
2
3
4
5
6
7

7.可变分区分配算法

3.下面给出某存储器的空白区记录示意图，若现有一个13KB的作业要进入内存，分别指出最先适应算法、最佳适应算法和最坏适应算法将该程序放入内存的起始地址，并完成下列各算法的空白区表。

空白区记录表 最先适应法空白区表

最佳适应法空白区表 最坏适应法空白区表

答案： 最先适应法空白区表 最佳适应法空白区表 最坏适应法空白区表

最先适应法：每次从起始地址开始，A长度16k可以装下，所以作业装入A
最佳适应法：最佳适应：每次分配最小且能装下作业的内存，所以作业装入B 14k
最坏适应：每次分配最大的内存；所以作业装入D 30k
1
2
3