《操作系统》习题课 - 计算题类型： 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 =20229ns 【注】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 第 页 共 页。