《操作系统》习题

计算题类型：

1. 重定位地址计算：

1) 给定逻辑地址，计算物理地址（分段或分页，一级页表或二级页表） 2) 给定逻辑地址LA，页长度，计算逻辑地址的页号和偏移

3) 给定物理地址RA，页帧长度，计算物理地址的页帧号和偏移

2. 有效内存访问时间计算：

给定内存访问时间、快表访问时间及快表命中率、调页时间及缺页率，计算有效内存访问时间

3. 磁盘地址及容量计算：

1) 给定一维的逻辑扇区编址A，柱面数C、磁头数H、扇区数S，计算物

理c、h、s

2) 给定柱面数C、磁头数H、扇区数S，计算磁盘容量

4. 文件系统相关计算：

1) 给定inode数据结构，盘块大小，地址长度，计算文件最大容量

2) 给定卷的容量，簇大小，FAT12/16/32分别需要多少个簇来存放FAT表 3) 给定RAID5阵列的磁盘数量n，计算磁盘空间有效利用率

5. 给定作业达到时刻、计算时间长度，调度策略，计算响应时间、周转时间

例1：在某个采用分页存储管理的系统中，假定逻辑页面和物理存储块的大小

均为1KB，主存容量为10KB。某个用户编写的程序P共有4个页面，被分别装入到主存的第3、4、6、8存储块中。 （1）写出P对应进程的页面映射表；

（2）当P在CPU运行时，执行了一条指令：MOV [2100]，[3100] 请计算指令中的两个操作数的物理地址。

解答：（1）由于页大小为1KB，故页内地址为10bit长。页表应为：

逻辑页号 物理块号 0 1 2 3 3 4 6 8 （2）先计算逻辑页号级页内偏移量，在差页表找到对应物理块号，最后计算物理地址： 逻辑地址 2100 3100

逻辑页号 ?2100/1024?=2 ?3100/1024?=3 页内偏移地址 2100-1024*2=52 3100-1024*3=28 物理存储块号 6 8 物理地址 1024*6+52=6196 1024*8+28=8220 例2：在请求分页式存储管理中，假设一次内存访问时间为100ns，一次快表

(TLB)访问时间为20ns，地址转换计算时的快表命中率为80%，请计算平均有效内存访问时间为多少ns？若缺页率为1‰，且每次缺页中断处理时间为20ms，请计算平均有效内存访问时间为多少ns？

解答：

如果快表命中（即页号在快表中），则内存访问时间A1=20+100=120ns 如果快表未命中，则内存访问时间

A2=20+100+100=220ns【含一次访问内存中页表】

则平均有效内存访问时间

A=A1×80%+A2×20%=120×0.8+220×0.2=140ns

缺页率p=1‰的含义是，每1000次有效内存访问中有2次需要调页处理！ 因此，请求页式存储管理过程中，平均有效内存访问时间： T = (1-p)×A+p×20(ms)

=(1-0.001)×140 + 0.001×20000000(ns) =139.86+20000 =20139ns

【注】1s=1000ms=1000 000us=1000 000 000ns

例3：假设一个磁盘共有2048个柱面，16个磁头，每个磁道分为64个扇区，

每个扇区容量为512字节，请计算该磁盘的总容量有多少GB？假设磁盘的一个逻辑盘块大小为2KB，则逻辑盘块号513所对应的首个扇区的三维物理地址（c，h，s）为多少？

解答：

（1）C=2048=2K个柱面 H=16个磁头 S=64个扇区/每个磁道 每个扇区的容量=512字节=0.5KB

则磁盘总容量=0.5KB×C×H×S = 0.5KB×2K×16×64 = 1GB （2）1个盘块由2KB/0.5K=4个扇区构成

因此，513号盘块的首块扇区号A=4×513=2052 s = A % S = 2052 % 64 = 4

h = ?A / S? % H = ?2052 / 64? % 16 = 0 c = ?A / (S×H)? = ?2052 / (64×16)? = 2 结果 =（2，0，4）

例4-1：RAID5磁盘阵列共有8块磁盘构成，请计算磁盘空间有效利用率？

解答： 磁盘空间有效利用率 = (n-1) / n = 7 / 8 = 87.5%

例4-2：已知磁盘容量为256MB，簇大小为4KB，对FAT16格式的文件系统

来说，文件分配表应该占用多大磁盘空间？（不考虑文件系统的空间开销）

解答： 整个磁盘逻辑盘块（簇）个数 = 256MB/4KB = 256×1024 / 4 = 64K个 FAT16文件格式的文件分配表每项占用16bit即2B空间 因此，文件分配表占用空间 = 2B×64K = 128KB

例4-3：MINIX文件系统1.0中，每个文件均有唯一的一个inode数据结构，

其中共有9个文件数据块指针zone[0..8]，每个指针为short类型。前7个即zone[0..6]为直接数据块指针，zone[7]为一级数据块指针，zone[8]为二级数据块指针。而每个数据块大小为1KB。试计算该文件系统能够支持的最大文件是多大？

解答：数据块大小为1KB，而每个指针为short整型，级占2B空间，因此1个

数据块可以有512个指针。

inode的直接数据块有7个，即可以指出7KB的空间；

inode的一级间接指针块，共有512个指针，可以指出512×1KB = 0.5MB

空间；

inode的二级间接指针块，共有512个指针，可以指出512个一级指针块，

共可以指出512×512个数据块，即可以指出512×512×1KB = 0.25GB空间。

因此，MINIX文件系统1.0的单个文件最大容量为0.25GB+0.5MB+7KB

例5：给定作业达到时刻、计算时间长度，调度策略，计算响应时间、周转时

间

任务 P1 P2 P3 P4 P5 到达时刻 (ms) 0 0 5 5 30 CPU区间 (ms) 10 29 3 7 12 采用SRFS(最少剩余时间作业优先)调度策略 调度执行结果甘特图：

P1 0

5

P3 8

P1 13

P4 20

P2 30

P5 42

P2 61

则响应时间（提交到第1次执行）： 周转时间（提交到执行完成）： 任务 P1 P2 P3 P4 P5 平均

响应时间 (ms) 0 20 0 8 0 5.6 周转时间间 (ms) 13 61 3 15 12 20.8 例6：在银行家算法中，系统有5个进程和3类资源。若出现一下资源分配情

况：

进程 P0 P1 P2 P3 P4 资源最大需求 7，5，3 3，2，2 9，0，2 2，2，2 4，3，3 已分配资源 0，1，0 2，1，0 3，0，2 2，1，1 0，0，2 目前系统中剩余资源数量为（3，2，2）。 目前状态是否为安全状态？如果是安全状态，给出一个安全序列，否则给出死锁进程集合。

解答：各个进程还需要的资源数量情况为： 进程 P0 P1 P2 P3 P4

剩余资源（3，2，2） 分配给P1，则剩余资源（5，3，2） P3 P2 P0 P4 P4 P0 P0 P2 P4 P2 P0 P0 P2 P4 P3 P2 P0 P0 P4 P2 P4 P0 P0 P2 P1 P4 P2 P0 P0 P2 P3 P4 P1 P2 P0 已分配资源 0，1，0 2，1，0 3，0，2 2，1，1 0，0，2 剩余资源请求 7，4，3 1，1，2 6，0，0 0，1，1 4，3，1 安全序列有12个： (1) P1、P3、P2、P0、P4 (2) P1、P3、P2、P4、P0 (3) P1、P3、P4、P0、P2 (4) P1、P3、P4、P2、P0 (5) P1、P4、P3、P0、P2 (6) P1、P4、P3、P2、P0 (7) P3、P1、P2、P0、P4 (8) P3、P1、P2、P4、P0 (9) P3、P1、P4、P0、P2 (10) P3、P1、P4、P2、P0 (11) P3、P4、P1、P0、P2 (12) P3、P4、P1、P2、P0

调度策略：

1. CPU调度（进程调度） FCFS（先来先服务）、 SJF（最短作业优先）、

SRJF（最短剩余时间作业优先）、 RR（时间片轮转）

四种方式的作业(任务)调度执行结果的甘特图，并通过甘特图计算响应时间、周转时间等

2. 虚拟内存的缺页置换 FIFO（先进先出）；OPT(MIN)（最优置换）；LRU（最近最少使用）； 三种置换策略，计算缺页数及缺页率 3. 磁盘调度

FCFS（先来先服务）、

SSTF（最短寻道时间优先）、 SCAN（扫描/电梯法）、 CSCAN（周期扫描法） CLOOK（周期查看扫描）

五种调度策略的寻道移动磁道数量计算

进程状态变迁及条件

三状态、五状态、七状态

算法：

银行家算法检测死锁 哲学家进餐问题

信号量控制互斥、同步程序编写

简答题例子：

（1）解释什么是并行和并发？

答案：并行是指两个或多个活动在同一时刻同时执行的情况；

并行是指系统中存在着若干个逻辑上相互独立的程序或程序段，它们都已

经被启动执行，在相对短的时间内，它们交叉地在CPU上执行的情况。给使用者一个并行的感觉。

（2）进程与程序之间的联系与区别？

答案：进程是程序的一次执行过程，没有程序就没有进程；

程序是完成某个特定功能的一系列程序语句的集合，只有不被破坏，它就

永远存在；

程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完

成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是。

选择题例子：

（1）如果分时系统的时间片一定，那么（ A ），则响应时间越长。

A 用户数越多 B 用户数越少 C 主存容量越大 D 主存容量越小

（2）在分时系统中，当用户数为100时，为保证响应时间不超过2s，系统设置的时间片应为（ D ）。

A 50ms B 100ms C 10ms D 20ms

（3）若信号量S的初值为2，当前值为-1，则表示有（ B ）个等待进程。 A 0 B 1 C 2 D 3

判断题例子：

死锁是指系统中的全部进程都处于阻塞状态。【×】 一个程序在执行过程中可能产生多进程。【√】

P、V操作既可以用来实现进程间的同步，也可以实现进程间互斥。【√】 当进程调度未能选中一个进程运行时，就绪队列和阻塞队列一定为空。【×】

本文来源：https://www.bwwdw.com/article/qn1x.html