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

第1章概述

一、单项选择题

D、A、B、A、C、D、C、A、C、B

二、填空题

Windows、linux

用户态、内核态

PSW

中断

同步中断

系统调用

I/O设备管理、文件系统

实时性、可靠性

第2章进程管理

一、单项选择题

D、D、C、D、BA、B、D^C、C

B、B、B、D、B、A、B、A

二、填空题

PCB

运行、就像、阻塞

4、5

时间片用完

进程管理、存储管理

PCB

进程

CPU寄存器的值、栈

竞争状态

运行、就绪

I/O繁忙

SJF

FCFS

短进程、I/O繁忙进程

三、简答题

1、运行状态、阻塞状态、就绪状态

运行。阻塞如进行I/O操作、进程间同步关系；

运行->就绪时间片用完、被高优先级进程所打断;

阻塞->就绪等待的I/O操作、信号量等事件发生;

就绪->运行调度程序选中该进程运行；

(1)进程是资源分配单位，拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈;

(2)线程能减少并发执行的时间和空间开销，包括创建时间、终止时间、切换时间；

(3)线程之间可以共享同一个地址空间，可以进行不通过内核的通信，而进程不行；

(4)线程=轻量级进程；

(5)线程是CPU调度单位；

(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、

(l)CPU空闲：100ms-150ms

(2)A无等待，B有等待，180ms〜200ms

2、

⑴Jobl从投入到运行完成需要110ms,Job2从投入到运行完成需要90ms,Job3从投入到运行完成需要110ms：

(2)CPU的利用率：(110—30)/110=72.7%；

(3)设备II的利用率：(110-30)/110=72.7%,设备12的利用率：(110-20)/110=81.8%。

3、

(1)这种机制不能实现资源的互斥访问

考虑如下的情形：

(a)初始化的时候，flag数组的两个元素值均为FALSE

(b)线程0先执行，在执行while循环语句的时候，由于flag[l]=FALSE,所以顺利结束，不会被卡住。假设这个时

候来了一个时钟中断，打断它的运行；

(c)线程1去执行，在执行while循环语句的时候，EtlTflag[0J=FALSE,所以顺利结束，不会被卡住，然后就进入

了临界区；

(d)后来当线程0再执行的时候，也进入了临界区，这样就同时有两个线程在临界区

(2)可能会出现死锁

考虑如下的情形：

(a)初始化的时候，flag数组的两个元素值均为FALSE

(b)线程0先执行，flag[0]=TRUE,假设这个时候来了一个时钟中断，打断它的运行；

(c)线程1去执行，flag[l]=TRUE,在执行while循环语句的时候，由于flag[0]=TRUE,所以在这个地方被卡住了，

直到时间片用完；

(d)线程0再执行的时候，由于flag[l]=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_wailing=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_waiting>0)

(

girls_waiting—;

V(S_girls);

)

elseif(boys_waiting>0)

(

boys_waiting—;

V(S_boys);

else

using=0;

}

V(S_mutex);

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_waiting>0)

(

girls_waiting—;

V(S_girls);

)

elseif(boys_waiting>0)

(

boys_waiting—;

V(S_boys);

else

using=0;

V(S_mutex);

(l)FCFS算法：

周转时间:Pl：52,P2：68,P3：136,P4：164

平均周转时间：105

(2)SJF算法：

周转时间:Pl：96,P2：16,P3：164,P4：44

平均周转时间：80

(3)RR算法：

周转时间：P1：136,P2：36,P3：164,P4：124

平均周转时间：115

7、

(1)不可抢占的SJF算法：

执行顺序：Pl(0-l4)P4(14-18)P3(18-25)P5(25-32)P2(32-44)

Pl：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

⑵可抢占的SJF算法：

执行顺序：Pl、P3、P4、P3、PkP5、P2

Pl: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算法：

执行顺序：Pl,P2、Pl、P3、P4、P2、PI、P3、P5、P2、Pl、P5

PI:41P2:39-3=36P3:31-5=26;P4：20-7=13;P5=44-19=25

平均周转时间：(41+36+26+13+25)/5=28.2

8、

(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、

令Rl+R2+...+Rn=n+k0<=k<m

由于C1+C2+…+Cn+R1+R2+..+Rn<n+m

所以C1+C2+...+Cn<m-k

所以剩余的资源个数A=m-(Cl+C2+...+Cn)>k,即A>=k+1

而对于每一个进程Pi,Ri<=k+1,所以任何一个进程的资源请求都能够满足。

2、

当N=l、2、3时都不会发生死锁的危险。

当N=3时，在最坏情形下，每个进程都需要4台磁带机，且假定每个进程都己经得到了3个资源，那么此时系统

中还剩下1个可用资源，可以把该资源分配给任何一个进程，当该进程得到资源后，可以运行完毕，并释放所占用的

所有4个资源，这样，剩余的2个进程都可以顺利地运行完毕。

3、

(1)系统处于安全状态1分

当前剩余资源向量A=(2,1,1),调度顺序为：

P4、*、*、*或者

P3,*,*,*

⑵不能，如果分配的话，系统将处于不安全的状态。

如果给它的话，那么当前剩余资源向量A=(0,1,1),无法把它分配给任何一个线程。

请求矩阵变为

021

410

100

200

4、

(1)该状态是一个安全状态

安全序列：Pl、P4、P5、P2、P3(或者PlP4P2P5P3或PlP4P2P3P5);

(2)不能把资源分配给它，否则的话会进入不安全的状态。

5、

请求矩阵：

P1347

P2134

P3006

P4221

P5110

剩余向量(233)

(1)是，P4(437){P2,P3,P5}P1；或者P5(547)然后任意顺序

⑵不能，资源不够

(3)能，顺序P4(437){P2,P3,P5}P1

请求矩阵：

P1347

P2134

P3006

P4020

P5110

剩余向量(032)

⑷不能，找不到安全序列。

6、

证明：假设出现了死锁，则必然存在一条环路，如下图所示：

Pml->Rnl->Pm2->Rn2->Pm3->Rn3->...->Pmk->Rnk->

如题所述，存在如下的关系：

Rnl<Rn2<Rn3<...<Rnl

矛盾，因此不可能出现这种环路，即不可能出现死锁。

第4章存储管理

一、选择题

C、C、B、B、C、C、B、B、A

A^D、A、C

二、填空题

寄存器、高速缓存

内存、硬盘

外碎片

内存紧缩

MMU

逻辑地址、物理地址

可变分区

内存分区起始地址、段长

可变分区

固定分区

逻辑页面、物理页面

操作系统

TLB

2次

对

数组(结构体数组)

局部性理论

内存大小/页面大小

不是

FIFO

工作集

内存大小/页面大小

三、简答题

1、

(1)会有外碎片的问题。

用户给出的请求大小是不同的，在经过不断的申请和释放以后，有一些小的空闲

块被夹在其他已分配的数据块之间，无法被利用，成为外碎片。

(2)会有内碎片的问题。

由于用户申请的空间必须是100的整数倍，即使用户只需要4个字节的内存空间,

也必须去申请100个字节的内存空间，因此剩下的96个字节就变成了内碎片。

2、

(1)在编译时确定。

(2)代码段

(3)全局变量gvCh由于没有设置初始值，所以放在bss段当中。

全局变量gvlnt有初始值，所以放在data段当中。

数组array是main函数的局部变量，所以存放在栈当中。

(4)指针p存放在栈当中。*(p+l)所描述的内存单元位于堆空间

(1)局部性原理：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定

区域。

(2)虚拟存储技术、LRU页面置换算法、CPU的cache、TLB,文件系统中的缓冲区。

(1)这两个寄存器的内容在进程切换的时候需要更新；

(2)由操作系统来负责更新；

(3)它们的内容平时存放在进程的PCB当中，在进程切换的时候装入到寄存器当中

(1)页表给出了逻辑页面号和物理页面号之间的映射关系。

(2)页表存放在内存中，在OS内核的数据结构中。

(3)页表的起始地址存放在进程控制块PCB中。

(4)N张页表。

⑸对。

页表的功能：逻辑页面号转换为物理页面号

页表项的格式：由CPU厂商设定

页表项的内容：由OS填写

驻留位的功能：该页面是否在内存

一个进程有多少个页表项：逻辑地址空间/页面大小

四、应用题

1、

(1)最先匹配法：无法满足要求(1分)，在申请96K存储区时，选中的是4号分区：在申请201＜时・，选中1号分区；在

申请200K时，现有的五个分区都无法满足要求

(2)下次匹配法：能够满足要求(1分)，在申请96K存储区时，选中的是5号分区；在申请20K时・，选中1号分区；在

申请200K时，选中4号分区

(3)最佳匹配法：能够满足要求，在申请96K存储区时，选中的是5号分区；在申请20K时，选中1号分区；在申请

200K时，选中4号分区

(4)最坏匹配法：无法满足要求(1分)，在申请96K存储区时，选中的是4号分区；在申请20K时，选中的还是4号分

区；在申请200K时，无法满足要求

(1)CPU必须访问两次内存才能获得所需数据，因此实现一次页面访问的存取时间是：1.5X2=3微秒;

(2)在增加快表后，实现一次页面访问的平均存取时间为：

0.85X1.5+(1-0.85)X2X1.5=1.725微秒

3、

(1)0x0

(2)0x20E

(3)地址越界

4、

逻辑地址物理地址逻辑地址物理地址

0x204ABC0x46ABC0x23200D0x7400D

0x1020410x100410xll03DBVirt.pagetoobig

0x304F51Invalidsegment!0x0103500x16350

5^

(1)1位、2位、3位

(2.a)34333

(2,b)写入物理地址67345时出错，写保护

(2.C)段错误，段号18不合法

(2.d)29806

(2.e)缺页中断，物理地址03097

6、

逻辑页面号：0、0、1、1、0、3、1、2、2、4、4、3

(l)OPT:5次

(2)FIFO:6次

⑶LRU:7次

⑷Clock:6次

7、

⑴FIFO优于LRU：

3个页面：1231423(4:6)

2个页面：12132(3:4)

(2)HFO等于LRU:

3个页面:123456(6:6)

2个页面：123412(6:6)

(3)LRU优于FIFO：

3个页面：123141(4:5)

2个页面:12131(3:4)

8、

每个进程有3个页面，其中1个存放程序，2个存放数据。

数组A有10000个整数，每页存放200个，数组占用50页，顺序为:

A[0][0],A[0][l],-A[0][99],A[l][0],-,A[l][99]1

A[2][0],A[2][l],-A[2][99](A[3][0],-,A[3][99]2

A[98][0],A[98][99],A[99][0],-,A[99][99]50

对于程序A：按行访问矩阵，访问的页面号为：1,2,…,50,因此缺页50次；

对于程序B：按列访问矩阵，访问的页面号为：1,1,2,2,…，50,50,1,1,2,2,…，因此缺页次数为：100X50=5000

次。

9、

⑴略

(2)379(0x17B)、缺页中断

10、

(1)页面大小为4K,每个页表项大小为4个字节，因此在每个页表当中，总共有1024个页表项，对于每个层次的页

表来说，都满足这一点，这样每级页表的索引均为10位，由于页面大小为4K,所以页内偏移地址为12位。

逻辑地址被划分为五个部分：

22位|10位|10位|10位|12位|

空闲一级索引二级索引三级索引页内偏移

可访问的虚拟地址空间大小为2八42=4T(2分)

(2)

假定一个页面的大小为2AY,即页内偏移地址为Y位，每个页表可以包含2^Y/8=2A(Y-3)个页表项，因此每级页表

的索引位为Y-3位，总共有4级页表，所以4(Y-3)+Y<=64

Y<=15.2因此Y=15

所以最大的页面大小为32KB。

|1位|12位|12位|12位|12位|15位|

空闲一级索引二级索引三级索引三级索引页内偏移

访问请求P1-AP1-BP2-CP2-FP2-EPl-AP2-DP2-EP2-DPl-APl-B缺页次数

AAAFFFDDDDD

全局LRU*BBBEEEEEEB8次

**CCCAAAAAA

AAAAAAAAAAA

局部FIFO*BBBBBBBBBB8次

**CFEEDEDDD

12、

(1)17CAH：页面大小1KB,故逻辑页面号为5。

(2)采用FIFO算法，淘汰第。页，其页框号为7,因此物理地址为1FCAH

(3)先循环一圈，将所有访问位都置为0,然后回到2号页框，将其置换，因此物理地址为0BCAH。

第5章I/O管理

一、选择题

A、D、D、A、C、D、D、B、B、B

A、A、C、A

二、填空题

磁盘、键盘

设备控制器

设备独立性

I/O独立编址、内存映像编址、混合编址

程序循环检测方式、中断驱动方式、DMA方式

不是

设备驱动程序

Spooling

不正确

柱面定位、旋转延迟

15.9ms、991.7ms

三、简答题

1、

(1)控制寄存器、状态寄存器、数据寄存器

(2)1/0独立编址；

(3)内存映像编址；

(4)混合编址；

2、

(1)是

(2)控制寄存器、状态寄存器、数据寄存器

(3)设备驱动程序

(4)I/O独立编址、内存映像编址或混合编址

3、

(l)CPU对DMA控制器进行编程，告诉它应把什么数据传送到内存的什么地方。并向磁盘控制器发出命令，让它去

磁盘驱动器中读入所需的数据块，保存到内部缓冲区中，并验证数据的正确性；

(2)DMA控制器通过总线向磁盘控制器发出一个读操作的信号，并把将写入的内存地址打在总线上；

(3)磁盘控制器取出一个字节，按该地址写入内存；

(4)磁盘控制器向DMA发一个确认信号，DMA把内存地址加1,把字节计数器减1。若计数器的值大于0转第2步;

(5)DMA控制器向CPU发出一个中断，告诉它数据传输已完成。

4、

(1)一般可以分为4层：中断处理程序、设备驱动程序、设备独立的

系统软件、用户空间的I/O软件；

(2)其中，中断处理程序和设备驱动程序是与硬件设备有关的；

(3)设备独立的系统软件和用户空间的I/O软件是与硬件设备无关的:

5、

硬件厂商。

处于系统态(管态)

信号量和PV操作来同步

OS设计人员

OS设计人员

6、

⑴扇区

(2)实现过程：

(a)读入包含该字节的扇区；

(b)修改该字节；

(c)把整个扇区写回到磁盘；

四、应用题

1、

根据题意：

10个盘面，每个盘面有100个磁道，每个磁道有16个扇区，因此总的扇区数为：10X100X16=16000

每个扇区用一个位来描述，共需要：16000/8=2000字节。

2、

磁盘访问时间=柱面定位+旋转延迟+数据传输;

读一个数据块的时间为：13X6+100+25=203ms

读取一个100块的文件需要时间：203X100=20300ms

3、

(1)先来先服务(First-ComeFirst-Served,FCFS)

执行顺序：(40)20、44、40、4、80、12、76

移动距离:292

柱面定位时间：876毫秒

⑵最短定位时间优先(ShortestSeekTimeFirst,SSTF)

执行顺序：(40)40、44、20、12、4、76、80

移动距离：120

柱面定位时间：360毫秒

(3)电梯算法(elevatoralgorithm),也叫扫描算法(SCAN)

执行顺序：(40)40、20、12、4、44、76、80

移动距离：112

柱面定位时间：336毫秒

4、

(l)FCFS

执行顺序：(10,0,10)->(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=48

(l)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、B

A、A,C

二、填空题

文件控制块

FCB

文件

文件名+FCB

块

不对

目录项

顺序结构

可变分区

打开方式、读写指针

位图法、链表法、索引法

三、简答题

1、

(1)普通的子目录以文件的形式存放。

根目录单独存放在磁盘的固定区域。

(2)目录的属性信息存放在目录文件的FCB中

(3)直接法：目录项=文件名+FCB。

间接法：目录项=文件名+FCB的起始地址。

2、

(1)链表结构：把文件的各个逻辑块依次存放在若干个(可以)不连续的物理块当中，各块之间通过指针连接，前

一个物理块指向下一个物理块。

(2)只能进行顺序访问，不能进行随机访问。为了访问一个文件的第n个逻辑块，必须从文件的第一个物理块开始,

按照指针所指向的地址，顺序地访问前n个块，即为了得到第n个逻辑块的物理块地址，必须先访问n-1次的磁盘，

速度非常慢；

(3)每个物理块上的数据存储空间不再是2