1、 习题一 1、举例说明为什么对并发执行的程序不加控制会产生与执行时间有关的错误？ 解：程序在并发执行时由于资源是共享的，而且常常资源数少于程序对这些资源的需求数，致使这些并发执行的程序之间因为竞争资源导致存在间接制约关系，这种间接制约使得并发执行的程序具有随机性（异步性），即“执行暂停 执行”，它们何时启动、何时停止是未知的。例如：飞机售票系统、堆栈的存数与取数过程等（示例说明略）。 2、程序并发执行为什么会失去顺序执行时的封闭性和可再现性？ 解：所谓 “封闭性 ”是指程序执行得到的最终结果由给定的初始条件决定 ，不受外界因素的影响。在程序并发执行时由于资源共享，导致这些资源的状态将由多个程序
2、来改变，又由于存在程序执行的随机性，所以程序的运行失去封闭性。由于失去了封闭性，也将导致其失去可再现性。即虽然它们执行时的环境和初始条件相同，但得到的结果却可能各不相同。 习题二 1、试用加锁的方法解决飞机售票系统的问题。 例：民航售票系统， n 个售票处 2、用机器指令（ testAndset）解决飞机售票系统中任一进程的算法。 习题三 1、进程在做 P、 V 操作时对自己和其他进程有何影响？ 进程在信号量上执行 P 操作后，若 信号量的值为正，当前进程继续执行；若信号量的值为负，当前进程变为等待状态、放弃处理机，其它进程则有机会获得 CPU。 进程在信号量上执行 V 操作后，不会对自己有任
3、何影响，但当信号量的值不大于 0 时，需要唤醒在该信号量上所对应的等待队列中的进程。 2、设课程的前驱、后继关系如下，若每修一门课程看作进程 Px（ x 1.6）试用 P、 V 操作算法描述这种前驱与后继关系。 答： Semaphore： S1： =S2： =S3： =S4： =S5： =S6： =0； Begin Cobegin P1、 P2、 P3、 P4、 P5、 P6 coend; end. P1（） P2（） P3（） Begin begin begin 修计算机导论； P（ S1）； P（ S2）； V（ S1）； 修高级语言程序设计 修计算机组成原理； V（ S2）； V（ S3
4、） V（ S4）； End; End; End; P4（） P5（） P6（） Begin begin begin P（ S3）； P（ S4）； P（ S5）； 修数据结构； 修 86 汇编语言； P（ S6）； V（ S5）； V（ S6）； 修操作系统； End; End; End; 习题四 1、有三个进程 R、 W1、 W2，进程 R 从输入设备上读数据送缓冲区 B，若是奇数由 W1 进程从 B 取数输出；若是偶数则由 W2 进程从 B 取数输出。设缓冲区 B 只有一个单元，试用信号量机制设计实现算法。 1、 se,sf1,sf2:semaphore; se:=1;sf1:=sf2:=
5、0; R（）、 W1（）、 W2（）并发执行 Process R process W1 process W2 repeat repeat repeat 读数 ; P(sf1); P(sf2); P(se); 从 B 中取数 ; 从 B 中取数 ; 送数到 B; V(se); V(se); if B mod 2!=0 then until false until false V(sf1); else V(sf2); until false 2、设有一台计算机， 挂有一台输入机和一台打印机。现在从输入机上把数据输入到缓冲区 B 中，处理程序处理后再把结果送到缓冲区 B 中，（设 B 只能放 1 个
6、数据）然后在打印机上输出。问 : （ 1）系统可设哪些进程来完成这一任务 ? （ 2）这些进程之间有什么样的制约关系 ? （ 3）用 PV 操作写出这些进程的同步算法 . 答：（ 1） 输入进程、处理进程、输出进程 （ 2） 处理进程不能在输入进程之前执行、输出进程不能在处理进程之前执行；输入进程在未得到处理进程、输出进程的消息前不能运行。 （ 3） 输入（）、处理（）、输 出（）进程并发执行 Semaphore:s1、 s2、 s3； S1： =1； S2： =S3： =0； process 输入（） process 处理（） process 输出（） L1: 读数 L2: P(S2) L3
7、: P(S3) P(S1) 从 B 取数处理后再送 B 从 B 取数输出 送数到 B V(S3) V（ S1） V(S2) Goto L2 Goto L3 Goto L1 习题五 1、设系统中有 M 个资源， N 个进程，每个进程都要求 K 个资源；若 M=5、 N=5、 K=2，问： （ 1）如何分配会导致死锁？ （ 2）要不死锁应该如何分配？ 如果对每个进程平均分配 1 个资源，则系统中的可用资源为 0，而每个进程都还需要 1 个资源，才能向前推进；因此、系统发生死锁。 只要保证有 1 个进程能获得 2 个资源 ，则它在有限的时间内就可以运行完成并释放资源，这样系统就不会死锁。例如、先给
8、4 个进程各分配 1 个资源，让它们先运行，通过安全性算法测试可以知道第 5 个进程的资源申请将被拒绝；再把最后 1 个资源分配给这 4 个进程中的 1 个即可。 2、假设甲、乙、丙三个并发进程间的 PV 操作同步算法如下所示 , 信号量 S1,S2,S3 的初值都为 1，问这些算法在什么情况下发生死锁 ?如何防止死锁？ 甲 乙 丙 . . . L1： P(S1) L2： P(S2) L3： P(S3) P(S2) P(S3) P(S1) . . . V(S2) V(S3) V(S1) V(S1) V(S2) V(S3) . . . goto L1 goto L2 goto L3 答： 甲 P
9、(S1)后暂停、乙 P(S2) 后暂停、丙 P(S3) 后暂停 采用按序分配，丙改为 P（ S1）、 P（ S3）。 也可以改甲或乙进程的 P、 V 操作次序，以限制进程的并发执行。 习题六 1.设有 5 个哲学家，共享一张放有五把椅子的桌子，每人分得一把椅 子。但是，桌子上总共只有 5 支筷子，在每人两边分开各放一支。哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐。 条件： (1) 只有拿到两支筷子时，哲学家才能吃饭。 (2) 如果筷子已在他人手上，则该哲学家必须等待到他人吃完之后才能拿到筷子。 (3) 任一哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。 试 : (1) 描
10、述一个保证不会出现两个邻座同时要求吃饭的通信算法。 (2) 描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。 (3) 在什么情况下， 5 个哲学家全部吃不上饭？ 答：使用非对称解决 即奇数号的哲学家先拿起他左边的筷子，接着拿起他右边的筷子，而偶数号的哲学家先拿起他右边的筷子，接着再拿他左边的筷子。 （ 1 ）设信号量 c0c4, 初 始 值 均 为 1, 分别表示 i 号筷子被拿 (i=0,1,2,3,4), send(i): 第 i 个 哲 学 家 要 吃 饭 begin think; P(ci); P(ci+1 mod 5); eat; V(ci+1 mod 5); V
11、(ci); End; 该过程能保证两邻座不同时吃饭 ,但会出现 5 个哲学家一人拿一只筷子 ,谁也吃不上饭的死 锁情况 （ 2）解决的思路 :让奇数号的哲学家先取右手边的筷子 ,让偶数号的哲学家先取左手边的筷子 .这样 ,任何一个哲学家拿到一只筷子之后 ,就已经阻止了他邻座的一个哲学家吃饭的企图 ,除非某个哲学家一直吃下去 ,否则不会有人会饿死 . send(i): 第 i 个 哲 学 家 要 吃 饭 Begin think; If i mod 2=0 then P(ci); P(ci+1mod 5) eat; V(ci; ci+1 mod 5) else P(ci+1 mod 5) P(ci
12、) Eat V(ci+1 mod 5) V(ci) End （ 3） 非对称解决，并发主程序略 Program diningphilosophers; Var chopstick:array0.4 of semaphore(:=1),i:integer; Procedure philosopher(i:integer); Begin Repeat Think; If(i mod 2！ =0) then Begin P(chopsticki)； P(chopstick(i+1) mod 5)；吃面； V(chopstick(i+1) mod 5)； V(chopsticki)； End Else
13、 Begin P(chopstick(i+1) mod 5)； P(chopsticki)；吃面； V(chopstick(i+1) mod 5)； V(chopsticki)； End Forever End 习题七 1、某程序在虚拟（逻辑）地址 100 处有一条取数指令 LOAD 1,500 而 500 单元存放数据 51888。若程序分配到的内存地址为 5000，试画出下列方式下的该指令及数据的物理地址和变换过程。 （ 1）静态重定位 （ 2）动态重定位 2、若一个虚拟地址空间占 8 页，每个页大小为 1024，需要映射到 32 个内存块上，试问： （ 1）虚拟地址要用多少位表示？ （
14、2）物理地址要用多少位表示？ 答 （ 1）逻辑地址需要的位数： 8*1024=23*210=213 所以需要 13 位。 （ 2）物理地址需要的位数： 32*1024=25*210=215 所以需要 15 位。 习题八 1、在页式存储管理系统中某个时刻某个进程的页表如下， 设地址结构为 32 位，页号占据 22 位，试把逻辑地址 0A5CH转换成物理地址（以十六进制表示）。 2、在静态页式下，内存总量为 65536 字节，每个存储块为 4KB，一程序代码段长 32768 字节 ,数据段长 16386 字节，堆栈段长 15870 字节，规定不允许一个块内包含两个段的内容，请问能为该程序分配空间吗
15、？如果块长为 512 字节呢？ 答： 习题九 1.在某页式虚拟存储系统中，页面大小为 100 个单元，某作业占有内存块数 m=2，若它的访问虚存逻辑地址序列为： 55、 135、 96、 227、 42、 156、 330、 169、 11、 252、 253 假设各个内存块初始为空，试问： （ 1）按 OPT 置换算法画图表示页面置换过程并求缺页中断率 f=？ （ 2）按 FIFO 置换算法画图表示页面置换过程并求缺页中断率 f=？ （ 3）按 LRU 置换算法画图表示页面置换过程并求缺页中断率 f=？ 习题十 1.某系统的磁盘文件空间共有 80 个柱面，被划分成 20 道 /柱面， 6 块 /道， 1KB/块的等长物理块。每块用位示图（ 64字 /张，使用 60 个字， 32 位 /字，其它为控制信息）的相应位表示其空闲（ 0）或占用（ 1）；试给出申请和归还一块的计算公式 。
