《操作系统》习题课分析

计算题类型：

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次内存访问中有1次需要调页处理！ 因此，请求分页式存储管理过程中，平均有效内存访问时间： 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个柱面（即每个盘面有2K个磁道）

H=16个磁头（即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，即128KB/4KB=32个簇

例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