第一章：
单项选择题：
1.（D）2.（D）3.（A）4.（C）5.（A）6.（C）7.（B）
综合应用题
1. 抽象、共享、安全
2. 通信语言——终端用户接口和系统调用——（高级语言）编程接口
3. 区分执行态的主要目的是保护系统程序；用户态到核心态的转换发生在中断产生时，而核心态到用户态的转换则发生在中断返回到用户程序时。
4. 在串行情况下，程序总的执行时间为90min，并行方式下作业运行的方式可以是TA执行18min→TB执行27min（TA同时进行I/O）→TA继续I/O（共需42min）、系统程序运行15min→TB进行I/O（共需63min），总的额执行时间为123min，提供的效率为（1-123/150）×100%。
5. 断点是发生中断时PC寄存器指向的指令的前一条指令地址；恢复点是发生中断时PC寄存器指向的指令地址；恢复点位置一般是中断恢复后执行的第一条指令，但是在一些操作系统中的缺页中断的断点作为恢复执行的第一条指令。
6. 参考本章内容。
7. 单道程序情况下：CPU和设备利用率均为50%；多道程序情况下：CPU和设备利用率均为(1-8/9)×100%
8. （第7题的最后两问应该是第8题）参考本章内容
第二章
单项选择题：
1.（A）2.（A）3.（D）4.（B）5.（A）6.（C）（F）7.（D）8.（A）9.（C）10.（B）11.（A）12.（B）
注：第8题的A、B两个选项的“保持”均改为“保证”
综合应用题：
1．阻塞到运行状态是不可能的，因为必须经过就绪状态；就绪到阻塞状态是不可能的；就绪到退出状态也是不可能的，中间必须经过执行状态。
2.～7. 参考本章内容。
8．第一种情况是因为进程完成I/O后，需要提高优先级，这是一种照顾I/O为主进程的策略；后4种情况均是因为它们长时间没有得到运行的机会，需要提高优先级，这是一种典型的动态优先级策略。
9．线程并行相对与进程并行可以降低上下文的切换开销。
10． 参考本章的例5。
11． 多CPU的调度依赖于操作系统内核的调度，而ULT不能影响操作系统的调度策略，因此不能实现真正的并行。
12． 提高并行执行的程度。
13.～19.参考本章的内容。
20． 死锁检测方法可以获得最大并发性。并发性排序：死锁检测方法、银行家算法、资源预分配法。
21． 参考第一章的第4题。
22． 题目中没有文字的框应该是就绪队列。（1）系统采用的是时间片轮转法（或者剥夺调度）策略。2是时间片到时；3、4是发出I/O请求；5、6是I/O完成；1是调度执行。
23． （1）系统每秒100次时钟中断，时间周期是10ms，因此10%的CPU时间用于时钟中断处理；（2）10次时钟中断一个时间片，则一个时间片是100ms，因此进程调度占用的CPU是4%。
24． 与第一章的第7题重复。
25． （1）10.6 6.6
（2）6.8 2.8
（3）7.48 3.48
26． 0ms 50 100 150 180 200 300ms
程序A： 计算 打印 计算 打印
程序B wait 计算 输入 wait 计算
(1)存在CPU空闲（在程序A运行后100ms-150ms之间，程序A正打印，程序B正输入）。CPU利用率为（300-50）/300=83.3%;
（2）程序A运行后无等待现象
（3）程序B运行后有等待现象（在A开始180ms-200ms之间；或程序B在运行后130ms-150ms之间）
27． 盘子为互斥资源，只能放入一个水果，设信号量empty初值为1；爸爸放苹果前先看看有无空间，若有则抢盘子，放入苹果后向女儿发信号；妈妈放橘子前先看看有无空间，若有则抢盘子，放入橘子后向儿子发信号；女儿先看有无苹果，若有则抢盘子，取走苹果后发出盘子为空的信号；儿子看有无橘子，若有则抢盘子，取走橘子后发出盘子置空的信号；置空信号应是爸爸和妈妈都可以接收的。该题是生产者/消费者问题的变形，有两对生产者和消费者。生产者需要指明是给哪个消费者的产品，但消费者取走产品后无须特别通知某个生产者，因为空出的缓冲区可由两个生产者随意争夺。此处无需设置信号量控制对盘子的互斥访问，因为盘子只能放一个产品；apple表示盘中有苹果，orange表示盘中有橘子，初值均为0。
Parbegin
爸爸: begin
L1: P(empty);
放苹果;
V(apple);
Goto L1;
End;
妈妈：begin
L2: P(empty);
放橘子;
V(orange);
Goto L2;
End;
女儿：begin
L3: P(apple);
取苹果;
V(empty);
Goto L3;
End;
儿子：begin
L4: P(orange);
取橘子;
V(empty);
Goto L4;
End;
Parend
28． 对8个哲学家顺序编号为P1、P2、P3、P4、P5、P6、P7、P8，对8个叉子顺序编号为1、2、3、4、5、6、7、8。讨论每个哲学家的行为过程，再总结出规律，发现下标为奇数的哲学家是先拿左边的叉子，再拿右边的叉子；下标为偶数的哲学家先拿右边的叉子，再拿左边的叉子；由此得到以下程序，信号量S的初值均为1。又因为编号P8的哲学家拿起的是8号和1号叉子，因此用取余运算令其返回1。
If i%2=0{ P(S);
P(S[(i+1)%i]);
吃；
V(S);
V(S[(i+1)%i]);}
Else
{ P(S[i+1]);
P(S);
吃；
V(S[i+1]);
V(S);}
该题不可能死锁。死锁产生的条件是所有的哲学家都从同一边拿起叉子，导致每个进程占用一个资源（叉子）而等待另一个资源，但该题的取叉子方式避免了这一现象。
29． 变量X是两个进程的共享资源，在进程同时申请访问时很容易出错。若采用顺序执行的方法，结果为Y=1，Z=1，T=2，U=2；若采用并发的方式，并按以下顺序12345678执行，则结果为Y=0，Z=0，出错。改正的方法是为临界资源X设置信号量S,初值为1。程序如下：
Parbegin
Var x:integer;
Process P1 Process P2
Var y，z：integer； Var t，u：mteger；
Begin Begin
P(S); P(S);
x：=1； ① x：=0； ②
y：=0； ③ t：=0； ⑥
ifx>=1 then y：＝y+1； ④ ifx<=1 then t：=t+2； ⑦
V(S); V(S);
z：=y； ⑤ u: =t; ⑧
end end
Parend
30． 哥哥存两次钱后，amount=20,第三次存钱时，弟弟正在取钱，因没有对amout互斥操作，故发生错误。最后amount上可能出现的值应与两进程相对执行速度有关；若TAKE先行结束后SAVE才开始，则剩20元；若SAVE先行结束后TAKE才开始，也剩20元；问题就出在两个进程交替使用cpu时，则会出现不同值。关键在于最后被执行的语句是amount:=m1,还是amount:=m2,若先amount:=m1后amount:=m2,则amount=10,反之，先amount:=m2后amount:=m1,则amount=30.设信号量mutex(初值为1)控制两进程对变量amount的互斥使用。正确过程如下：
Begin
Amount:integer;
Amount:=0;
Cobegin
Process SAVE
M1:integer;
Begin
P(mutex);
M1:=amount;
M1:=m1+10;
Amount:=m1;
V(mutex);
End;
Process TAKE
M2:integer;
Begin
P(mutex);
M2:=amount;
M2:=m2-10;
Amount:=m2;
V(mutex);
End;
Coend;
End;
31．
type semaphore=monitor
var acknowledgement1,acknowledgement2,acknowledgement3:boolean;
x,y:condition;
a,b,c:integer
指挥官：begin
while acknowledgement1:false
or acknowledgement2:=false
or acknowledgement3:=false
do x.wait;
下达命令;
a:=1;
b:=1;
c:=1;
y.signal;
end.
士兵1：begin
while a=0 do y.wait;
接收命令;
acknowledgement1:true;
x.signal;
end.
士兵1：begin
while a=0 do y.wait;
接收命令;
acknowledgement2:true;
x.signal;
end.
士兵1：begin
while a=0 do y.wait;
接收命令;
acknowledgement3:true;
x.signal;
end.
begin
a:=0;
b:=0;
c:=0;
acknowledgement1:=false;
acknowledgement2:=false;
acknowledgement3:=false;
end.
32． 读者有任意多个，但进入阅览室阅读最多为100人，为此可设一个信号量s，代表空座位的数目；另登记表为临界资源，需设一个用于互斥的信号量mutex,防止2个及以上的读者进程同时对此表访问。对于每个读者的动作包括进入、阅读、离开。)
struct semaphore s,mutex=100,1;
cobegin
void readeri(void) (i=1,2,…,k)
{
while(TRUE){
P(s);
P(mutex);
查登记表，置某座位为占用；
V(mutex);
……
reading;
……
P(mutex);
查登记表，置某座位为空;
V(mutex);
V(s);}
}
coend
33． （1）Sr用于读者计数rc的互斥信号量；
（2）if rc=1 then P（S）中的P（S）用于读写互斥，写者进程中的P（S）用于写写互斥，读写互斥。
（3）程序中增加一个信号量S5，初值为5，P（S5）语句加在读者进程P（Sr）之前，V（S5）语句加在读者进程第2个V（Sr）之后。
34． 设置信号量：
readcount:=0,nwriter:=0,swriter:=1,mutex:=1,wrt:=1;
读者：P(swriter);
if(nwriter=0)
{P(mutex);
readcount:=readcount+1;
if(readcount=1)
P(wrt);
V(mutex);
V(swriter);}
else
{V(swriter);
block();}
reading;
P(mutex);
readcount:=readcount-1;
if(readcount=0)
V(wrt);
V(mutex);
写者：P(swriter);
nwriter:=nwriter+1;
P(wrt);
writing;
P(swriter);
nwriter:=nwriter-1;
if(nwriter=0)
{wakeup(读者进程);
V(swriter);}
else
{V(wrt);
V(swriter);}
35． 首先在题目的初始条件上找安全序列。要想找安全序列，首先给出进程的剩余需求量，也就是在占有部分资源的基础上，还需要多少资源。列表如下：
占有资源量 剩余需求量
A B C A B C
P0 0 0 3 0 0 1
P1 1 0 0 0 7 5
P2 1 3 5 1 0 0
P3 0 0 2 0 6 2
P4 0 0 1 0 6 4
检查系统剩余资源数（1，4，0），看是否可以一次性满足某个进程的全部剩余需求量。找到P0和P2，则选其一进入安全序列，并假设该进程已完成，然后将进入安全序列的进程所占有的资源回收，再检查是否可以一次性满足某个进程的全部剩余需求。以此类推，最后如果所有进程都可以进入安全序列，则系统处于安全状态，不会死锁。本题第一问的答案是： 当前系统处于安全状态，因为至少可以找到一个安全序列<P0P2P1P3P4>(答案不定)。
如果系统中可用资源为（0，6，2），则只可满足P3的要求，P3归还后，可满足P4的要求，P4归还后，可满足P0的要求，P0归还后，无法满足P1和P2的要求，即找不到安全序列，因此系统处在不安全状态。
36． （1）这里要进行一下特别的说明。题目中没有强调m与n的大小关系及取值范围，而实际上这点很重要，影响到题目证明的正确与否。举例如下：假设m=6,根据题意，每个进程的最大需求量在1~6之间则不会死锁。但请考虑，如果有3个进程，且每个进程最大需要3个资源，则当每个进程占用2个资源的时候，死锁就已经发生，所以该问无法证明。
(2)用反证法。假设发生死锁，此时系统的资源已全部分配，即m个资源被n个进程占用，但所有进程仍处于等待状态，说明每个进程至少还需1个资源，n个进程还需要n个资源，即n个进程所需的资源总数至少是m+n个，这与已知条件相矛盾，假设不成立。
37． 会死锁。因为对两个账户进行加锁操作是可以分割进行的，若此时有两个用户同时进行转账，P1先对帐户A进行加锁，再申请帐户B；P2先对帐户B进行加锁，再申请账户A，此时死锁。解决办法是：可以采用资源顺序分配法，将A、B账户进行编号，用户转账是，只能按照编号由小到大进行加锁；也可以采用资源预分配法，要求用户在使用资源之前将所有资源一次性申请到。
38． 不发生死锁必须保证至少有1个进程可以得到所需的全部资源并执行完毕，当m≥n*(k-1)+1则一定不会发生死锁
序号 m n k 是否会死锁
1 6 3 3 可能会
2 9 3 3 不会
3 13 6 3 不会
39． (1)可能会发生死锁
(2)可有几种答案：
A.采用静态分配：由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。
B.采用按序分配：不会出现循环等待资源现象。
C.采用银行家算法：因为在分配时，保证了系统处于安全状态。
40． 略
第三章
1. (1) 单一重定位分区
系统启动时，操作系统在重定位寄存器中装入用户程序可以访问的最低内存地址。
(2) 多重固定分区
当操作系统启动时，在界限寄存器中装入分区大小。操作系统记录哪些分区已用和哪些分区空闲。当创建进程或进程终止时，操作系统必须更新分区使用数据。在将进程分配给内存时，操作系统必须检查进程是否小于分区大小。当进程获得CPU控制权时，操作系统必须在重定位寄存器中装入进程起始地址。
(3) 简单分段
操作系统必须记录哪些内存已使用和哪些内存空闲。当创建进程时，操作系统必须把段装入内存并为进程创建段表。当进程终止时，操作系统必须释放它所占用的内存空间。当进程获得CPU控制权时，操作系统必须在内存管理寄存器中装入进程的段表。如果出现分段错误，操作系统必须处理错误。
2. (1) 单一重定位分区
每次访问内存时，用该位置的地址加上重定位寄存器中的地址形成物理地址。
(2) 多重固定分区
每次访问内存时，将逻辑地址和界限寄存器中的地址进行比较。大于界限寄存器中地址的地址将产生内存出错陷阱。同时，逻辑地址加上重定位寄存器中的地址形成物理地址。
(3) 简单分段
每次访问内存时，分段硬件把逻辑地址转换成物理地址。逻辑地址中的段号位被用做段表的索引。逻辑地址的段偏移位加上从相应段表项中得到的段起始地址形成物理地址。
3. 535, 560, 564, 620, 624
4. 12位
5. (1) 程序产生的每个逻辑地址和界限寄存器比较。任何大于界限寄存器的地址将造成内存出错陷阱。
(2) 每个逻辑地址加上重定位寄存器产生物理地址。然后将物理地址和最大物理地址比较。任何大于最大物理地址的地址将造成内存出错陷阱。
(3) 在重定位寄存器加上逻辑地址的同时，将逻辑地址和界限寄存器比较。之后将物理地址和最大物理地址比较。通过同时比较，能较快完成虚实地址转换。
6. 64 （勘误：28， 224， 264应改为28, 224, 264）
7. p
8. 21
9. 512
10. 23
11. 4096
12. 24
13. 9
14. 10
15. 19
16. 15
17. 10
18. 25
19. 225
20. (1) 214 (2) 28 (3) 210 (d) 218
21. 6
22. 144
23. 70%
24. int Trans(struct VirtualAddressType virtAddr)
{
int physAddr = -1;
if(virtAddr.off >= segTable(virtAddr.seg).len)
fault( );
else
physAddr = segTable(virtAddr.seg).loc + virtAddr.off;
return physAddr;
}
25. (1) 1400
(2) 出错
(3) 3100
(4) 5100
(5) 出错
26. (1) 缺页
(2) 3 700 410
(3) 602 012
(4) 5 000 234
27. (1) 01011001001
(2) 11010010110
(3) 缺页
(4) 00101111100
28. 156.245
29. 4.99865ms
30. 133.61
31. (1) 轻微降低或没有影响。
(2) 没有影响。
(3) 没有影响或影响很小。
(4) 没有影响或影响很小。
(5) 没有影响或影响很小。
(6) 可能改进。
(7) 在一定程度上降低性能。
(8) 可能改进。
32. (1) FIFO: 13
(2) LRU: 14
(3) OPT: 9
33. 110.2205μs
34. (1) 2 (2) 0
35. (1) 0111 0101 0001 0101 11
(2) 1110 1001 0011 1111 11
(3) 0110 0101 0011 0001 11
(4) 段故障
第四章
1．文件引入的主要目的是便于用户存放信息。文件抽象体现了操作系统的“抽象”概念。
2．基本思想是使用关联规则，及使用某种特定规则将文件和处理程序管理起来。一种规则可以是文件名字的后缀；另一种规则可以特定文件的前缀；还可以使用统配符号，等等。
3．两者之间的区别在与rename可以是一个原子操作；后者的操作序列可能引起错误，比如在（1）完成之后（2）开始之前，其他人可能将原有文件移动到其他位置。
4．内存映射（Memory-Mapped）文件概念。
5．可以。比如使用一些特定的文件名字，使用“.”表示目录的结束，使用/作为文件的名字，/A/B/C文件表示A目录下B子目录的C文件。
6．一种方法是使用open/close/read方法模拟，当文件指针向文件尾移动时，使用read移动文件指针；如果想文件头移动，则可以关闭文件后打开文件，在使用read；另一种方法是将文件内容全部读入一个缓冲中，使用内存指针移动模拟文件指针移动。这两种方法均在存在过度I/O的缺点。
7．顺序结构在文件内容发生移动时容易产生内部碎片；索引结构文件在索引小文件时容易产生索引块内部碎片（这也是UNIX使用特殊索引结构的主要原因）。
8．一次紧致大约10ms左右；紧致8GB数据，大约是1M个文件，因此大约需要1万秒左右。
9．10个直接地址则最大容纳10M数据，而一个间接地址可以容纳1024M数据，因此最大文件大小为1034M。
10． 最多存储的数据规模基本不变。
11． 马丁的方法在多个进程打开同一个文件是产生共享问题。即，一个进程对文件内容的修改结果对其它进程不可见。
12． 空闲链表所需的空间为F×D位，而位映射占用的空间为B位，因此使用空闲链表占用空间小于位映射的条件是F×D<B；如果D=16，则F<B/16，即有6.25%的空闲。
13． （1）1111 1111 1111 0000；（2）1000 0001 1111 0000；（3）1111 1111 1111 1100；（4）1111 1110 0000 1100。
14． 优点是可以在读取FCB时顺便读取文件的开始部分，大多数的文件操作均是从头开始操作文件，因此可以减少文件I/O次数；缺点是对于一些中型大小的文件，增加了后续I/O的次数（寻找索引）。
15． h×1+（1-h）×40。
16． 前一种情况下需要的时间为99×6×13+100×（100+25）ms；后一种情况所需时间为99×6×2+100×（100+25）ms。
17． 磁盘调度算法是在操作系统中实现的，磁盘驱动器服务不应该实现特殊的调度方法，而只会使用FCFS方法。
18． （左侧的磁盘空间利用率的单位应该是0.1%），在块大小为1KB、2KB、4KB时的磁盘空间利用率分别依次为100%、100%和50%；其数据率依次为80、160和320KB/s左右。至于空间利用率应该是因为系统中文件大小是2K左右。而产生数据率逐步提高的原因是因为旋转速度为1500rpm，即平均的旋转延迟为40ms；每个磁道为256KB，在块大小为1KB、2KB和4KB时分别可以存放256块、128块和64块，因为旋转延迟是寻道时间的5倍，因此磁道中存放的块越多，寻找一个块所需的时间也就越多，数据率也就越小。
19． 这种情况下空间利用率为50%。实际情况下，特别是在Windows环境下，大多数文件大小远远高于2KB，因此空间利用率会高于这个数字。
20． 5次。
21． 索引节点放在磁盘开始处可以减少I/O次数（搜索文件的I/O次数），但是开始处的磁盘空间大小是有限的，因此文件系统中文件数目取决于存放索引节点的空间大小。第二种方法正好相反。
22． （1）修改文件目录，指向一个未被授权访问的文件的FCB。（2）在修改文件目录文件时，禁止指向其它目录。
23． （1）顺序结构；（2）顺序结构；（3）链接结构。
24． 参考例14。
25． 旋转延迟为60000/300=200ms，假设处理数据的速度为k B/ms。在（a）中读取一个磁道的时间为8×(200 / (512/K) )* 200ms；在（b）则为8×(400 / (512/K))* 200ms；在（c）中则为8×(600 / (512/K) )* 200ms。
第五章
1．可以。因为扫描仪的带宽最低。
2．大约500MB。可参考计算机原理中的相关知识。
3．如果采用中断驱动I/O，按照打印速度，发出中断的频率为400Hz，发生中断的时间间隔是2.5ms，CPU的消耗率为50/2500=2%，但是由于CPU需要处理许多的设备以及其他任务来看，这样的消耗不太合算。
4．将磁盘作为I/O缓冲。
5．使用中断通知设备ready，使用直接控制I/O进行数据传输。
6．使用缓冲需要消耗存储（空间）资源，但是可以减少对慢速设备的访问次数，节省时间。
7．参考本章的内容。
8．这个例程应该使用中断I/O方式。
9．参考本章内容。
10． 提高CPU利用率。
11． 参考第一章内容。
12． 提高通道设备的利用率。
13． (1-2/(1000/60))*100% |
收藏
点赞!
反对!