操作系统谌卫军王浩娟课后习题参考答案.doc

第1章 概述一、单项选择题D、A、B、A、C、D、C、A、C、B二、填空题Windows、linux用户态、内核态PSW中断同步中断系统调用I/O设备管理、文件系统实时性、可靠性第2章 进程管理一、单项选择题D、D、C、D、B、A、B、D、C、CB、B、B、D、B、A、B、A二、填空题PCB运行、就像、阻塞4、5时间片用完进程管理、存储管理PCB进程CPU寄存器的值、栈竞争状态运行、就绪I/O繁忙SJFFCFS短进程、I/O繁忙进程三、简答题1、运行状态、阻塞状态、就绪状态 运行-阻塞：如进行I/O操作、进程间同步关系； 运行-就绪：时间片用完、被高优先级进程所打断； 阻塞-就绪：等待的I/O操作、信号量等事件发生； 就绪-运行：调度程序选中该进程运行； 2、 (1)进程是资源分配单位，拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈； (2)线程能减少并发执行的时间和空间开销，包括创建时间、终止时间、切换时间； (3)线程之间可以共享同一个地址空间，可以进行不通过内核的通信，而进程不行； (4)线程 轻量级进程； (5)线程是CPU调度单位；3、 (1)当一个新的进程被创建时； (2)当一个进程运行完毕时； (3)当一个进程由于I/O、信号量或其他的某个原因被阻塞时； (4)当一个I/O中断发生时，表明某个I/O操作已经完成，而等待该I/O操作的进程转入就绪状态； (5)在分时系统中，当一个进程的时间片用完时；4、 RR算法的基本思路： (1)将所有的就绪进程按照FCFS原则，排成一个队列； (2)每次调度时将处理器分派给队首进程，让其执行一小段CPU时间； (3)在一个时间片结束时，如果进程还没有执行完的话，将发生时钟中断，在时钟中断中，进程调度程序将暂停当前进程的执行，并将其送到就绪队列的末尾，然后执行当前的队首进程； (4)如果进程在它的时间片用完之前就已结束或被阻塞，那么立即让出CPU。 RR算法的主要缺点：时间片q的大小难以确定。5、(1)时间片用完，高优先级进程就绪(2)不会发生切换(3)PCB(4)不需要(5)不能四、应用题1、(1)CPU空闲：100ms150ms(2)A无等待，B有等待，180ms200ms2、(1)Job1从投入到运行完成需要110ms，Job2从投入到运行完成需要90ms，Job3从投入到运行完成需要110ms：(2)CPU的利用率：(11030)/110 = 72.7%；(3)设备I1的利用率：(110-30)/110 = 72.7%，设备I2的利用率：(110-20)/110 = 81.8%。3、(1)这种机制不能实现资源的互斥访问考虑如下的情形： (a)初始化的时候，flag数组的两个元素值均为FALSE (b)线程0先执行，在执行while循环语句的时候，由于flag1=FALSE，所以顺利结束，不会被卡住。假设这个时候来了一个时钟中断，打断它的运行； (c)线程1去执行，在执行while循环语句的时候，由于flag0=FALSE，所以顺利结束，不会被卡住，然后就进入了临界区； (d)后来当线程0再执行的时候，也进入了临界区，这样就同时有两个线程在临界区 (2)可能会出现死锁考虑如下的情形： (a)初始化的时候，flag数组的两个元素值均为FALSE (b)线程0先执行，flag0=TRUE，假设这个时候来了一个时钟中断，打断它的运行； (c)线程1去执行，flag1=TRUE，在执行while循环语句的时候，由于flag0=TRUE,所以在这个地方被卡住了，直到时间片用完； (d)线程0再执行的时候，由于flag1=TRUE，它也在while循环语句的地方被卡住了，这样，这两个线程都无法执行下去，从而死锁。4、 (1)最后打印了3个字符D (2)最少可能打印了0个字符A，例如，P1连续执行了3次，然后P3连续执行了3次。P2一次也没有执行。 (3)不可能，因为当打印出前面的“CABAB”的时候，信号量R的值等于1，此时，不可能连续打印两个D。 (4)可能。相当于进程P2在打印完第二个A的时候被中断了。5、(1)信号量的定义：int boys_waiting = 0, girls_waiting = 0, using = 0;Semaphore S_mutex = 1, S_boys = 0, S_girls = 0;(2) void boy_wants_to_use_bathroom() P(S_mutex); if(using = 0) & (girls_waiting = 0) using = 1; V(S_mutex); else boys_waiting +; V(S_mutex); P(S_boys); (3) void boy_leaves_bathroom() P(S_mutex); if(girls_waiting 0) girls_waiting -; V(S_girls); else if(boys_waiting 0) boys_waiting -; V(S_boys); else using = 0; V(S_mutex);(4) void girl_wants_to_use_bathroom() P(S_mutex); if(using = 0) using = 1; V(S_mutex); else girls_waiting +; V(S_mutex); P(S_girls); (5) void girl_leaves_bathroom() P(S_mutex); if(girls_waiting 0) girls_waiting -; V(S_girls); else if(boys_waiting 0) boys_waiting -; V(S_boys); else using = 0; V(S_mutex);6、(1)FCFS算法： 周转时间：P1：52，P2：68，P3：136，P4：164 平均周转时间：105(2)SJF算法： 周转时间：P1：96，P2：16，P3：164，P4：44 平均周转时间：80(3)RR算法： 周转时间：P1：136，P2：36，P3：164，P4：124 平均周转时间：1157、(1)不可抢占的SJF算法： 执行顺序：P1(0-14)P4(14-18)P3(18-25)P5(25-32)P2(32-44) P1：14；P2：443=41；P3: 25-5=20; P4: 18-7=11; P5: 32-19=13 平均周转时间：(14+41+20+11+13)/5=19.8(2)可抢占的SJF算法： 执行顺序：P1、P3、P4、P3、P1、P5、P2 P1: 25-0 = 25; P2: 44-3=41; P3= 16-5=11; P4= 11-7=4; P5=32-19=13 平均周转时间：(25+41+11+4+13)/5=18.8(3)时间片轮转RR算法： 执行顺序：P1、P2、P1、P3、P4、P2、P1、P3、P5、P2、P1、P5 P1: 41 P2: 39-3=36 P3: 31-5=26; P4：20-7=13; P5=44-19=25 平均周转时间：(41+36+26+13+25)/5=28.28、(1)不正确，可能导致死锁 例如，开始时缓冲区为空，消费者先运行，通过了P(S_Mutex)，由于此时S_ProductNum为0，所以在P(S_ProductNum)处被阻塞，而生产者会在P(S_Mutex)处被阻塞，从而死锁。 再比如：开始时缓冲区满了，生产者先运行，通过了P(S_Mutex)，由于此时S_BufferNum为0，所以在P(S_BufferNum)处被阻塞，而消费者会在P(S_Mutex)处被阻塞，从而死锁。(2)不正确，可能导致死锁 例如，假设现在缓冲区已经满了，然后生产者先运行，通过了P(S_Mutex)，在P(S_BufferNUM)处被阻塞，然后消费者执行，在P(S_Mutex)处被阻塞，从而死锁。(3)正确 缺点是降低了并发性，应该在离开临界区后立即释放互斥信号量，这样才能提高进程之间的并发性。第3章 死锁一、选择题D、B、C、D、C二、填空题竞争资源CPU、内存不对互斥条件、请求和保持条件环路2个死锁避免剥夺资源、进程回退、撤消进程三、应用题1、令R1+R2+.+Rn n+k 0=km由于C1+C2+.+Cn + R1+R2+.+Rn n+m所以C1+C2+.+Cn k，即 A = k+1而对于每一个进程Pi，Ri Rn1 - Pm2 - Rn2 - Pm3 - Rn3 - . - Pmk - Rnk -如题所述，存在如下的关系：Rn1 Rn2 Rn3 . Rn1矛盾，因此不可能出现这种环路，即不可能出现死锁。第4章 存储管理一、选择题C、C、B、B、C、C、B、B、AA、D、A、C二、填空题寄存器、高速缓存内存、硬盘外碎片内存紧缩MMU逻辑地址、物理地址可变分区内存分区起始地址、段长可变分区固定分区逻辑页面、物理页面操作系统TLB2次对数组（结构体数组）局部性理论内存大小/页面大小不是FIFO工作集内存大小/页面大小三、简答题1、 (1)会有外碎片的问题。 用户给出的请求大小是不同的，在经过不断的申请和释放以后，有一些小的空闲 块被夹在其他已分配的数据块之间，无法被利用，成为外碎片。 (2)会有内碎片的问题。 由于用户申请的空间必须是100的整数倍，即使用户只需要4个字节的内存空间， 也必须去申请100个字节的内存空间，因此剩下的96个字节就变成了内碎片。2、(1) 在编译时确定。(2) 代码段(3) 全局变量gvCh由于没有设置初始值，所以放在bss段当中。 全局变量gvInt有初始值，所以放在data段当中。 数组array是main函数的局部变量，所以存放在栈当中。(4) 指针p存放在栈当中。*(p+1)所描述的内存单元位于堆空间3、 (1)局部性原理：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。 (2)虚拟存储技术、LRU页面置换算法、CPU的cache、TLB、文件系统中的缓冲区。4、 (1)这两个寄存器的内容在进程切换的时候需要更新； (2)由操作系统来负责更新； (3)它们的内容平时存放在进程的PCB当中，在进程切换的时候装入到寄存器当中5、 (1)页表给出了逻辑页面号和物理页面号之间的映射关系。 (2)页表存放在内存中，在OS内核的数据结构中。 (3)页表的起始地址存放在进程控制块PCB中。 (4)N张页表。 (5)对。6、页表的功能：逻辑页面号转换为物理页面号 页表项的格式：由CPU厂商设定 页表项的内容：由OS填写 驻留位的功能：该页面是否在内存 一个进程有多少个页表项：逻辑地址空间/页面大小四、应用题1、(1)最先匹配法：无法满足要求(1分)，在申请96K存储区时，选中的是4号分区；在申请20K时，选中1号分区；在申请200K时，现有的五个分区都无法满足要求(2)下次匹配法：能够满足要求(1分)，在申请96K存储区时，选中的是5号分区；在申请20K时，选中1号分区；在申请200K时，选中4号分区(3)最佳匹配法：能够满足要求，在申请96K存储区时，选中的是5号分区；在申请20K时，选中1号分区；在申请200K时，选中4号分区(4)最坏匹配法：无法满足要求(1分)，在申请96K存储区时，选中的是4号分区；在申请20K时，选中的还是4号分区；在申请200K时，无法满足要求2、（1）CPU必须访问两次内存才能获得所需数据，因此实现一次页面访问的存取时间是：1.523微秒；（2）在增加快表后，实现一次页面访问的平均存取时间为：0.851.5(10.85)21.51.725微秒3、(1)0x0(2)0x20E (3)地址越界 4、逻辑地址物理地址逻辑地址物理地址0x204ABC0x46ABC0x23200D0x7400D0x1020410x100410x1103DBVirt. page too big!0x304F51Invalid segment!0x0103500x163505、(1) 1位、2位、3位(2.a) 34333(2.b) 写入物理地址67345时出错，写保护(2.c) 段错误，段号18不合法(2.d) 29806(2.e) 缺页中断，物理地址030976、逻辑页面号：0、0、1、1、0、3、1、2、2、4、4、3(1) OPT: 5次 (2) FIFO: 6次 (3) LRU: 7次(4) Clock: 6次7、 (1)FIFO优于LRU： 3个页面：1 2 3 1 4 2 3 (4 : 6) 2个页面：1 2 1 3 2 (3 : 4) (2)FIFO等于LRU: 3个页面：1 2 3 4 5 6 (6 : 6) 2个页面：1 2 3 4 1 2 (6 : 6) (3)LRU优于FIFO： 3个页面：1 2 3 1 4 1 (4 : 5) 2个页面：1 2 1 3 1 (3 : 4)8、每个进程有3个页面，其中1个存放程序，2个存放数据。数组A有10000个整数，每页存放200个，数组占用50页，顺序为：A00, A01, A099,A10,A199 1A20, A21, A299,A30,A399 2 A980, , A9899, A990, A9999 50对于程序A：按行访问矩阵，访问的页面号为：1, 2, , 50，因此缺页50次；对于程序B：按列访问矩阵，访问的页面号为：1, 1, 2, 2, , 50, 50, 1, 1, 2, 2, , 因此缺页次数为：100505000次。9、(1)略(2)379(0x17B)、缺页中断10、(1)页面大小为4K，每个页表项大小为4个字节，因此在每个页表当中，总共有1024个页表项，对于每个层次的页表来说，都满足这一点，这样每级页表的索引均为10位，由于页面大小为4K，所以页内偏移地址为12位。逻辑地址被划分为五个部分：-| 22位 | 10位 | 10位 | 10位 | 12位 |- 空闲 一级索引 二级索引 三级索引 页内偏移可访问的虚拟地址空间大小为 242 = 4T (2分)(2) 假定一个页面的大小为2Y，即页内偏移地址为Y位，每个页表可以包含2Y / 8 = 2 (Y-3)个页表项，因此每级页表的索引位为Y-3位，总共有4级页表，所以4(Y-3) + Y = 64 Y (22,1,20)-(20,5,100)-(8,5,50)-(40,10,50)- (6,11,120)-(36,8,100)移动距离： 20-10-22-20-8-40-6-36 = 10+12+2+12+32+34+30 = 132(2)SSTF: 执行顺序：(20,5,100)-(22,1,20)-(10,0,10)-(8,5,50)-(6,11,120)- (36,8,100)-(40,10,50)移动距离： 20-20-22-10-8-6-36-40 = 0+2+12+2+2+30+4 = 52(3)SCAN: 执行顺序：(20,5,100)-(10,0,10)-(8,5,50)-(6,11,120)-(22,1,20)- (36,8,100)-(40,10,50)移动距离：20-20-10-8-6-22-36-40 = 0+10+2+2+16+14+4 = 485、(1)15.9ms (2)2975.1ms(3)86.4GB(4)柱面定位、设备驱动程序6、采用位图法来管理磁盘空闲空间，每个磁盘块的状态用0和1表示：2KB = 2*1024*8bit = 16384bit根据CSCAN算法，被访问的磁道号顺序为100 - 120 - 30 - 50 - 90寻道时间：（20+90+20+40）*1ms = 170ms每分钟6000转，转一圈时间10ms，通过一个扇区时间0.1ms，随机访问4个扇区，总时间170 + (0.5*10+0.1)*4 = 190.4ms第6章 文件系统一、选择题A、D、B、A、D、A、A、C、C、BA、A、C二、填空题文件控制块FCB文件文件名+FCB块不对目录项顺序结构可变分区打开方式、读写指针位图法、链表法、索引法三、简答题1、 (1)普通的子目录以文件的形式存放。 根目录单独存放在磁盘的固定区域。 (2)目录的属性信息存放在目录文件的FCB中 (3)直接法：目录项文件名+FCB。 间接法：目录项文件名FCB的起始地址。2、 (1)链表结构：把文件的各个逻辑块依次存放在若干个（可以）不连续的物理块当中，各块之间通过指针连接，前一个物理块指向下一个物理块。 (2)只能进行顺序访问，不能进行随机访问。为了访问一个文件的第n个逻辑块，必须从文件的第一个物理块开始，按照指针所指向的地址，顺序地访问前n个块，即为了得到第n个逻辑块的物理块地址，必须先访问n-1次的磁盘，速度非常慢； (3)每个物理块上的数据存储空间不再是2的整数次幂（指针占用了若干个字节），从而使文件的访问不太方便。3、 (1)移动操作的速度更快； (2)拷贝操作需要把文件的每个数据块都复制一份，而且还要创建一个新的目录项， 用来指向这些数据块，所以时间比较长； 而移动操作不需要拷贝数据块，只需要创建一个新的目录项，并且删除旧的目录 项即可，所以速度很快；4、 (1)文件系统首先就把根目录读进来； (2)在根目录中查找temp这个子目录的目录项； (3)根据这个目录项，找到temp目录文件的FCB，并将其内容读进来； (4)在temp目录文件中去查找old.txt这个目录项； (5)在这个目录项中，把old.txt修改为new.txt。5、(1)直接重命名方法更快(2)前者只是去修改相应的目录项当中的文件名，其他不变(3)后者需要复制一份文件，增加一个目