《操作系统》习题课.doc

计算题类型：1. 重定位地址计算：1) 给定逻辑地址，计算物理地址（分段或分页，一级页表或二级页表）2) 给定逻辑地址LA，页长度，计算逻辑地址的页号和偏移3) 给定物理地址RA，页帧长度，计算物理地址的页帧号和偏移2. 有效内存访问时间计算：给定内存访问时间、快表访问时间及快表命中率、调页时间及缺页率，计算有效内存访问时间3. 磁盘地址及容量计算：1) 给定一维的逻辑扇区编址A，柱面数C、磁头数H、扇区数S，计算物理c、h、s2) 给定柱面数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长。页表应为：逻辑页号物理块号03142638（2）先计算逻辑页号级页内偏移量，在差页表找到对应物理块号，最后计算物理地址：逻辑地址逻辑页号页内偏移地址物理存储块号物理地址21002100/1024=22100-1024*2=5261024*6+52=619631003100/1024=33100-1024*3=2881024*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=2052s = A % S = 2052 % 64 = 4h = A / S % H = 2052 / 64 % 16 = 0c = 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个文件数据块指针zone0.8，每个指针为short类型。前7个即zone0.6为直接数据块指针，zone7为一级数据块指针，zone8为二级数据块指针。而每个数据块大小为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：给定作业达到时刻、计算时间长度，调度策略，计算响应时间、周转时间任务到达时刻(ms)CPU区间(ms)P1010P2029P353P457P53012采用SRFS(最少剩余时间作业优先)调度策略调度执行结果甘特图：P1P3P15610813P420P2P230P542则响应时间（提交到第1次执行）： 周转时间（提交到执行完成）： 任务响应时间(ms)周转时间间(ms)P1013P22061P303P4815P5012平均5.620.8例6：在银行家算法中，系统有5个进程和3类资源。若出现一下资源分配情况：进程资源最大需求已分配资源P07，5，30，1，0P13，2，22，1，0P29，0，23，0，2P32，2，22，1，1P44，3，30，0，2目前系统中剩余资源数量为（3，2，2）。目前状态是否为安全状态？如果是安全状态，给出一个安全序列，否则给出死锁进程集合。解答：各个进程还需要的资源数量情况为：进程已分配资源剩余资源请求P00，1，07，4，3P12，1，01，1，2P23，0，26，0，0P32，1，10，1，1P40，0，24，3，1剩余资源（3，2，2）分配给P1，则剩余资源（5，3，2）P3P3P4P1P4P2P4P3P2P4P1P0P4P0P2P0P2P0P4P0P2P0P2P4P0P2P0P2P0P4P0P2P0P2P0安全序列有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操作既可以用来实现进程间的同步，也可以实现进程间互斥。【】当进程调度未能选中一个进程运行时，就绪队列和阻塞队列一定为空。【×】10 ×。空列阻队，行个能度【互程实步间程来可操。多生中执×。状处进的中指子子 程待个 示则-当为初量 0 0 0） 片的系 不时保时 数，统在越量主 大量 少用 多数长间响， 那定间统果子例题 是不而单的配资进程亡而因成生建由，态是而念的一 在远就坏有合句程系的个成程 程进没没程次序程别与的序与觉觉个者给的上 叉它间时在执启都，段序独互逻着在系行 况况行同在活个是发并行么子子编程、互控信问进学死检法状状态条条计数动道策描扫查 法扫（ ）梯电（）优时最）服来调页页页，略）用最（ ）（ (；出（置的间间间应图甘，甘结度务业的转轮）优作剩（）先短最）服先度程进略略 、 0、 、 0、 、 、 0 、 、 0 、 、 、 、 0 、个有 ， 源则 （， ， ， ， ， 请源资资进为情数要程各合集死则列全出给安果状为态），为源剩， ， ， ， ， 资需大进况情源现若资程进系中家：.平 间 时任 ：完到（转）执第到时 0 图甘行策度先作剩少 区 时任时转时响略调长时刻时业： + .容件单. ， 间间 × 指即块个× 以可针一 以，个有，指二 间空.0 指针 块接级 间的 以即有数接 针个 可据此间 ， 为每， 块数大是文持支统该计 小数每指据二 针据一 ，块接.0 。 指每. 据个共，构 一一文，0系 =空占件， 空 占每文的件 0 / ）簇盘磁整销间的系虑间磁多应分文说文的 对 为簇 为容知 -=利间空率用间磁计成块有盘 ， = / =) / / = = %0=% 块的 构构 ./由块 =× 0量总 节字=容个 磁每区 磁 = 柱 =答少多） （维三个对所号盘 为大逻的磁 多容盘算请 为量每， 分每， 柱个0盘设 0000=0 0= 00+ (0000 0×0.( ) (+)-( 间问内效中理存求理处需 中效0 每义 0 0 0 %×时时效表中内一【 0 时访内命未 0=+ 间访内，在即中答 少为问内平计 理中次每缺 少时存内算请 率快算转址 为访 表一 0时访内，管式求 = = 000 = *-= 00地块块地地偏页地址地计最块对找差移内号逻块页为为。 为地故 大由（址理数个的指0 0 ：指了时 表射页应 中块、 、主入被页 共的用个0 主 大块理辑逻统理存用个时转间算，调度间计到用利空磁计数的阵 来个需 / ，容容最算计地大盘据 算算容容计数 头 、物算 头 ，址扇维算量址时问内算页间调中快及访快问算计访偏号的理算度，址理偏偏址逻计度 地表页表一页分地算计算址