《操作系统》习题课

计算题类型：

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 例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，剩（7，4，3） P0 P2 P4 P4 P2 P2 P0 P4 P4 P0 P0 P2 P4 P2 P0 P0 P2 P4， 剩（5，3，4） 已分配资源 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 分配给P3，则剩余资源（5，3，3） P1，剩（7，4，3） P0 P2 P4 P4 P2 P0 P4 P2 P4 P0 P4 P0 P2 P2 P0 P4， 剩（5，3，5） P3 P2 P0 P1 P0 P2 P2 P0 安全序列有14个： (1) P1、P3、P0、P2、P4

(2) P1、P3、P0、P4、P2 (3) P1、P3、P2、P0、P4 (4) P1、P3、P2、P4、P0 (5) P1、P3、P4、P0、P2 (6) P1、P3、P4、P2、P0 (7) P1、P4、P3、P0、P2 (8) P1、P4、P3、P2、P0 (9) P3、P1、P0、P2、P4 (10) P3、P1、P0、P4、P2 (11) P3、P1、P2、P0、P4 (12) P3、P1、P2、P4、P0 (13) P3、P1、P4、P0、P2 (14) P3、P1、P4、P2、P0 (15) P3、P4、P1、P0、P2 (16) P3、P4、P1、P2、P0

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《操作系统》习题课在线全文阅读。