操作系统(谌卫军-王浩娟)课后习题参考答案

1第1章概述一、单项选择题D、A、B、A、C、D、C、A、C、B二、填空题Windows、linux用户态、内核态PSW中断同步中断系统调用I/O设备管理、文件系统实时性、可靠性2第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)在分时系统中，当一个进程的时间片用完时；34、RR算法的基本思路：(1)将所有的就绪进程按照FCFS原则，排成一个队列；(2)每次调度时将处理器分派给队首进程，让其执行一小段CPU时间；(3)在一个时间片结束时，如果进程还没有执行完的话，将发生时钟中断，在时钟中断中，进程调度程序将暂停当前进程的执行，并将其送到就绪队列的末尾，然后执行当前的队首进程；(4)如果进程在它的时间片用完之前就已结束或被阻塞，那么立即让出CPU。RR算法的主要缺点：时间片q的大小难以确定。5、(1)时间片用完，高优先级进程就绪(2)不会发生切换(3)PCB(4)不需要(5)不能四、应用题1、(1)CPU空闲：100ms～150ms(2)A无等待，B有等待，180ms～200ms2、(1)Job1从投入到运行完成需要110ms，Job2从投入到运行完成需要90ms，Job3从投入到运行完成需要110ms：(2)CPU的利用率：(110－30)/110=72.7%；(3)设备I1的利用率：(110-30)/110=72.7%，设备I2的利用率：(110-20)/110=81.8%。3、(1)这种机制不能实现资源的互斥访问考虑如下的情形：(a)初始化的时候，flag数组的两个元素值均为FALSE(b)线程0先执行，在执行while循环语句的时候，由于flag[1]=FALSE，所以顺利结束，不会被卡住。假设这个时候来了一个时钟中断，打断它的运行；(c)线程1去执行，在执行while循环语句的时候，由于flag[0]=FALSE，所以顺利结束，不会被卡住，然后就进入了临界区；(d)后来当线程0再执行的时候，也进入了临界区，这样就同时有两个线程在临界区(2)可能会出现死锁考虑如下的情形：(a)初始化的时候，flag数组的两个元素值均为FALSE(b)线程0先执行，flag[0]=TRUE，假设这个时候来了一个时钟中断，打断它的运行；(c)线程1去执行，flag[1]=TRUE，在执行while循环语句的时候，由于flag[0]=TRUE,所以在这个地方被卡住了，直到时间片用完；4(d)线程0再执行的时候，由于flag[1]=TRUE，它也在while循环语句的地方被卡住了，这样，这两个线程都无法执行下去，从而死锁。4、(1)最后打印了3个字符'D'(2)最少可能打印了0个字符'A'，例如，P1连续执行了3次，然后P3连续执行了3次。P2一次也没有执行。(3)不可能，因为当打印出前面的“CABAB”的时候，信号量R的值等于1，此时，不可能连续打印两个D。(4)可能。相当于进程P2在打印完第二个A的时候被中断了。5、(1)信号量的定义：intboys_waiting=0,girls_waiting=0,using=0;SemaphoreS_mutex=1,S_boys=0,S_girls=0;(2)voidboy_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)voidboy_leaves_bathroom(){P(S_mutex);if(girls_waiting0){girls_waiting--;V(S_girls);}elseif(boys_waiting0){boys_waiting--;V(S_boys);5}else{using=0;}V(S_mutex);}(4)voidgirl_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)voidgirl_leaves_bathroom(){P(S_mutex);if(girls_waiting0){girls_waiting--;V(S_girls);}elseif(boys_waiting0){boys_waiting--;V(S_boys);}else{using=0;}6V(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：44－3=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、P2P1: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、P5P1:41P2:39-3=36P3: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)正确缺点是降低了并发性，应该在离开临界区后立即释放互斥信号量，这样才能提高进程之间的并发性。7第3章死锁一、选择题D、B、C、D、C二、填空题竞争资源CPU、内存不对互斥条件、请求和保持条件环路2个死锁避免剥夺资源、进程回退、撤消进程三、应用题1、令R1+R2+...+Rn＝n+k0=km由于C1+C2+...+Cn+R1+R2+..+Rnn+m所以C1+C2+...+Cnm-k所以剩余的资源个数A=m-(C1+C2+...+Cn)k，即A=k+1而对于每一个进程Pi，Ri=k+1，所以任何一个进程的资源请求都能够满足。2、当N＝1、2、3时都不会发生死锁的危险。当N＝3时，在最坏情形下，每个进程都需要4台磁带机，且假定每个进程都已经得到了3个资源，那么此时系统中还剩下1个可用资源，可以把该资源分配给任何一个进程，当该进程得到资源后，可以运行完毕，并释放所占用的所有4个资源，这样，剩余的2个进程都可以顺利地运行完毕。3、(1)系统处于安全状态1分当前剩余资源向量A=(2,1,1)，调度顺序为：P4、*、*、*或者P3，*,*,*(2)不能，如果分配的话，系统将处于不安全的状态。如果给它的话，那么当前剩余资源向量A=(0,1,1)，无法把它分配给任何一个线程。请求矩阵变为02141010020084、(1)该状态是一个安全状态安全序列：P1、P4、P5、P2、P3(或者P1P4P2P5P3或P1P4P2P3P5);(2)不能把资源分配给它，否则的话会进入不安全的状态。5、请求矩阵:P1347P2134P3006P4221P5110剩余向量(233)(1)是，P4(437){P2,P3,P5}P1；或者P5(547)然后任意顺序(2)不能，资源不够(3)能，顺序P4(437){P2,P3,P5}P1请求矩阵：P1347P2134P3006P4020P5110剩余向量(032)(4)不能，找不到安全序列。6、证明：假设出现了死锁，则必然存在一条环路，如下图所示：Pm1-Rn1-Pm2-Rn2-Pm3-Rn3-...-Pmk-Rnk-如题所述，存在如下的关系：Rn1Rn2Rn3...Rn1矛盾，因此不可能出现这种环路，即不可能出现死锁。9第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段当中。10全局变量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填写驻留位的功能：该页面是否在内存一个进