当前位置:首页 >> 工学 >>

西安交大操作系统第一次习题课


习题课(一)

张航 2013.11.4

Contact me
张航 Email: endsub@stu.xjtu.edu.cn Addr : 西一楼721 Ftp : ftp://202.117.10.128 User : stu Pwd : 2013 Upload your file to /up/, download the shared file from /down/.

Brief
? 第六章及之前作业存在的问题 ? 补充习题(重点在于进程同步)

Assignment: 6.4

Points: 1.等待自旋锁期间进程仍然占用处理器 2.自旋锁需要的进入条件必须由其他进程满足

Assignment: 6.9

Advice: 将高级语言代码细化为汇编代码进行分析 start: mov eax,[s] cmp eax,0 jng start dec eax mov [s],eax

Assignment: 6.11

Steps: 1.从题目中找出各方进程争夺的共享资源 2.所有的共享资源都应当有相应的信号量进行保护 3.分析各角色的行为逻辑,必要时定义辅助变量或信号量,如果辅助变量也是多 进程共享访问的,则应当定义对应的互斥锁mutex加以保护。 4.形成最终代码 Tips:对信号量的使用一定要成对

var mutex,customers, barbers : semaphore; waiting, chairs : integer; procedure barber: begin while(true) begin p(customers); p(mutex); waiting:= waiting – 1 ; v(mutex); cuthair(); v(barbers); end end

procedure customer; begin p(mutex); if (waiting < chairs) then begin waiting:= waiting + 1 ; v(customers); v(mutex); p(barbers); get-haircut() end else begin v(mutex); end end

begin

seminitial (mutex,1 ; barbers, 0; customers,0); waiting=0; chairs=10; cobegin barber; customer; ….. customer; coend end

Assignment: Extra problem 1
实现读者-写者问题的写者无饥饿版本 Rc=0;w=0; //共享变量 Mutex=1; wr=1 //互斥信号量 READER : While w = 1 do skip; P(mutex); Rc:=Rc + 1; If Rc = 1 then P(wr); V(mutex); READING P(mutex); Rc := rc -1; If rc = 0 then V(wr); V(mutex)

WRITER : w := 1; P(wr); w := 0; V(wr)

解法二:另外设置一个信号量w=1;用于写 进程到达后封锁后续读进程 READER : P(w); P(mutex); Rc:=rc + 1; If rc = 1 then P(wr); -----若是第一个 读进程,则要看有无写进程 V(mutex); V(w); READING P(mutex); Rc := rc -1; If rc = 0 then V(wr); -------若所有读进 程都执行完,可以让其它进程读写 V(mutex) WRITER : P(w); P(wr); WRITING; V(wr) V(w);

额外的PV操作降低了并发度和效 率,此方法不如第一种解法简单高 效。

Assignment: Extra problem 2
缓冲区容量无限的生产者-消费者问题。 producer: p(mutex); v(product); v(mutex); producer: v(product); p(mutex) p(mutex); v(product); v(mutex); 虽然缓冲区容量无限,但是对缓 冲区的操作仍需用互斥量mutex进 行保护。 consumer:

consumer:

p(product);
p(mutex); //remove product

p(mutex);
p(product); //remove product

v(mutex);

v(mutex);

Assignment: 5.1

Points: 1.描述两类程序各自特点 2.指出具体应采用的调度策略(I/O bound优先)

Assignment: 5.4

B.What is the turnaround time of each process for each of the scheduling algorithms in part a?

C.What is the waiting time of each process for each of the scheduling algorithms in part a? 区分waiting time 和 response time

?

1.有一阅览室,共有100个座位。读者进 入时必须先在一张登记表上登记,该表为 每一座位列一表目,包括座号和读者姓名。 读者离开时要消掉登记内容。试用P/v操 作描述读者进程的同步结构。 解析:定义信号量以及相应变量 mutex: semaphore; 互斥信号量 full: semaphore; 同步信号量 table: array 0.. n-1 of item ;

?

Procedure reader; begin P(full) ; P(mutex); Register-name ( table) ; V(mutex); Reading ; P(mutex); Delet-name (table) ; V(mutex); V(full); end

begin Seminitsal ( mutex,1; full,100) Cobegin Reader; Reader; …… coend end

? 2.一座小桥(最多能承重两个人),横 跨东西两岸 东侧桥段和西侧桥段任意时刻只允许一 人通过 桥中间一处宽敞,允许两人通过或者休 息。 请用P、V操作描述东西两岸过桥的算 法。

桥中央 西 东

? ? ?

一人:西->东 一人:东->西 两个人:西->东 两个人:东->西

? 设置信号量如下

信号量 EW WE east west

初值 2 2 1 1 允许从东到西的人数 允许从西到东的人数 是否允许在东段桥上

含义

是否允许在西段桥上

? eastTowest:begin

P(EW);
P(WE); P(east); 从东岸经东段桥,走到桥中央; V(east); 通过桥中央或者休息; P(west); 经西段桥,从桥中央到西岸; V(west); V(WE); V(EW); end;
没有必要同时定义EW和WE。

? westToeast:begin P(EW); P(WE); P(west); 从西岸经西段桥,走到桥中央; V(west); 通过桥中央或者休息; P(east);

经东段桥,从桥中央到东岸;
V(east); V(WE);

V(EW);
end;

? 3.把学生和监考老师都看作进程, 学生有N人, 教师1人.

考场门口每次只能进出一个人, 进考场原则是先来先进.
当N个学生都进入考场后, 教师才能发卷子. 学生交卷后 可以离开考场. 教师要等收上来全部卷子并封装卷子后才

能离开考场.
? 问题: ? 问共需设置几个进程? ? 试用P、V操作解决上述问题中的同步和互斥关系.
该题解析是错误的!

? 【解析】:
– 定义一个共享变量StudentCounter=N – 定义四个信号量:
? Mutex=1,实现考场门口的互斥进入 ? M1=1,实现对StudentCounter的互斥访问; ? M2=1,表示学生是否到齐了,教师是否可以发 试卷; ? M3=1,表示试卷是否收齐了,教师是否可以离 开

– 共需设置二个进程:学生进程,教师进程

学生: P(mutex); 进入考场; V(mutex); P(M1); StudentCounter:=StudentCounter -1; 教师: If StudentCounter=0 P(mutex); V(M2); 进入考场; V(M1); V(mutex); 答题; P(M1); P(M2); StudentCounter:=StudentCounter+1; 发试卷; 交试卷; 巡视考场; If StudentCounter=N 收试卷; V(M3); P(M3); 离开考场; 离开 V(M1); P(mutex); 考虑一个学生“一马当先”的情况。 离开考场; 不应共用一个StudentCounter V(mutex);

? 4.流水线问题 某流水线有4个并发工序P1、P2、P3、P4,他们 执行情况如下: P1先执行;P1结束后,P2,P3同时开始执行, P2,P3都结束后,P1才能继续下一次执行,同时 P4开始执行。试用PV操作实现他们之间的同步。 【解析】:

SA12,SB12,SA13,SB13,SB24,SB34; Semophore SA12:=SA13:=1; SB12:=SB13:=SB24:=SB34:=0;

Process PA Begin P(SA12) P(SA13) 执行P1 V(SB13) V(SB12) End;(PA)

Process PB Begin P(SB12) 执行P2 V(SB24) V(SA12) End;(PB)

Process PC Begin P(SB13) 执行P3 V(SB34) V(SA13) End;(PC)

Process PD Begin P(SB24) P(SB34) 执行P4 End;(PD)

? 5.设在公共汽车上,司机和售票员的活动分 别如下: 司机的活动:启动车辆;正常行车;到站 停车。 售票员的活动:关车门;售票;开车门。 ? 问题:在汽车不停地到站、停车以及行驶的 过程中,司机和售票员之间的活动有什么同 步关系?

? 解答: ? 首先分析两个进程之间的同步关系。汽车行驶过 程中,司机活动与售票员活动之间的同步关系为: – 售票员关车门后,向司机发开车信号 – 司机接到开车信号后起动车辆 – 在汽车正常行驶过程中售票员售票 – 到站时司机停车 – 售票员在车停后开车门让乘客下车 ? 定义两个信号量s1:表示是否允许司机起动车辆, s2:表示是否允许售票员开门。初值为0。

?请将以下描述这两个活动的PV操作补充完整:

Semaphore s1=0; Semaphore s2=0; main() {cobegin driver(); conductor(); Coend; }

driver() {while(1) {p(s1); 启动车辆; 正常行车; 到站停车; ; } }

conductor() {while(1) {关车门; ; 售票; p(s2); 开车门; 上下乘客; } }

s1:表示是否允许司机起动车辆; s2:表示是否允许售票员开门;

Semaphore s1=0; Semaphore s2=0; main() {cobegin driver(); conductor(); Coend; }

driver() {while(1) {p(s1); 启动车辆; 正常行车; 到站停车; v(s2); } }

conductor() {while(1) {关车门; v(s1) ; 售票; p(s2); 开车门; 上下乘客; } }

CPU调度习题(1)
? 一个具有两道作业的批处理系统,作业调度采用短作业优先的调 度算法,进程调度采用以优先数为基础的抢占式调度算法,如下 表的作业序列(表中所有作业优先数即为进程优先数,数值越小 优先级越高)。要求: (1)列出所有作业进入内存时间及结束时间 (2)计算平均周转时间 作业名 到达时间 估计运算时间 优先数 A 10:00 40分 5 B 10:20 30分 3 C 10:30 50分 4 D 10:50 20分 6

A

B

C

D

图例:

到达时间 进入内存 结束时间

10:00 10:20 A B

30

50 11:10 D B C A

12:00

12:20

t

C

D

?10:00 A作业到达, 作业A调入内存,进程调度程序调度A运行 ?10:20 B作业到达,作业B调入内存,抢占进程A的处理机,A回到就绪队列 ,A还需运行20分钟 ?10:30 C作业到达,在后备队列中等待 ?10:50 B运行30分钟后结束运行,D作业到达,后备队列中有C,D两个作业 等待调度,根据短作业优先原则,D调入内存.内存中,A在就绪队列上已等待 了30分钟,A的优先级高于D,A运行,D就绪.此时C在后备队列中已等待了20 分钟并继续等待.

A

B

C

D

图例:

到达时间 进入内存 结束时间

10:00 A

10:20 B

30

50 11:10 D B C A

12:00

12:20

t

C

D

? 11:10 A运行结束,C装入内存,C的优先权高于D,C运行,D继续等 待,此时D已等待了20分钟. ? 12:00 C运行结束,D运行 ? 12:20 D运行结束

? 作业名 进入内存时间 结束时间 A 10:00 11:10 B 10:20 10:50 C 11:10 12:00 D 10:50 12:20 ? 各作业的周转时间为: A:70 B:30 C:90 D:90 ? 平均周转时间为(70+30+90+90)/4=70
A B C D
图例: 到达时间 进入内存 结束时间

10:00 A

10:20 B

30

50 11:10 D B C A

12:00

12:20

t

C

D

CPU调度习题(2)
一个四道作业的操作系统中,设在一段时间内先后到达6个作业,它 们的提交时间和运行时间见下表 作业号 JOB1 JOB2 JOB3 JOB4 JOB5 JOB6 提交时间 运行时间 60 35 20 25 5 10

8:00 8:20 8:25 8:30 8:35 8:40

系统采用SJF算法,作业被调度进入运行后不再退出,但当一作业进 入运行时,可以调整运行的优先次序。 1 分别给出上述6个作业的执行时间次序 2 计算作业的平均周转时间

【解析】 ? ? 四道的系统,作业调度最多可选择四道作业进入内存,以进程的形式运行; 进程调度采用可抢占的短作业优先调度原则

? 8:00 J1到达,无竞争者,进入内存。 ? 8:20 J1运行20分钟,剩余40分钟;J2到达,运行时间为35分钟, 小于J1, 取代J1运行。 ? 8:25 J1剩余40分钟,J2剩余30分钟;J3到达,运行时间为20分钟, 取代J2运行。 ? 8:30 J1剩余40分钟,J2剩余30分钟,J3剩余15分钟,J4到达,运 行时间为25分钟,J3继续运行。 ? 8:35 J3剩余10分钟,J5到达,运行时间为5分钟,尽管最短,但内 存已经有四道作业,因此,J5不可进入内存,J3继续运行。

? 08:40 J3剩余5分钟;J6到达,同理不可以进入内存,J3继 续运行。 ? 08:45 J3运行结束,离开主存。J5最短,进入内存。 ? 08:50 J5结束,离开。J6进入,运行时间为10分钟,为最短, 开始运行。 ? 09:00 J6结束,离开。J1剩余40分钟,J2剩余30分钟,J4 剩余25分钟,J4最短,开始运行。 ? 09:25 J4结束,离开。J2最短,开始运行。 ? 09:55 J2结束,J1运行。 ? 10:35 J1结束。

? 每道作业的周转时间=结束时间-提交时间

J1:8:00~10:35 J2:8:20~09:55 J3:8:25~08:45 J4:8:30~09:25 J5:8:35~08:50 J6:8:40~09:00

周转时间155分钟 周转时间95分钟 周转时间20分钟 周转时间55分钟 周转时间15分钟 周转时间20分钟

? 平均周转时间:360/6=60分钟。

The End


相关文章:
操作系统复习题
西安交大附中理科学霸高... 东北师大附中理科学霸高...4 答:一是操作系统对各层的管理和控制 二是各层...35、 (1)什么是首次适应算法?(157 页) 起始地址...
操作系统复习题
西安交大附中理科学霸高... 东北师大附中理科学霸高...1/2 相关文档推荐 ...暂无评价|0人阅读|0次下载|举报文档 复习题一、选择 1.若把操作系统看作计算机...
操作系统练习题3 -4
西安交大附中理科学霸高... 东北师大附中理科学霸高...1/2 相关文档推荐 ...暂无评价|0人阅读|0次下载|举报文档 操作系统练习题 3-4 章一、判断题 1....
操作系统总复习题
西安交大附中理科学霸高... 东北师大附中理科学霸高...操作系统试题全集2 9页 免费 操作系统复习问答题 2...A、首次适应算法 B、最佳适应算法 C、循环首次适应...
操作系统第四章练习题
西安交大附中理科学霸高... 东北师大附中理科学霸高...1/2 相关文档推荐 ...暂无评价|0人阅读|0次下载|举报文档第四章练习题一,选择题 1, 在存储管理中...
操作系统复习题
西安交大附中理科学霸高... 东北师大附中理科学霸高...() 第二章练习题操作系统中进程的状态有许多种, ...分 别用首次适应算法、最佳适应算法、最坏适应算法,...
操作系统期末复习题
西安交大附中理科学霸高... 东北师大附中理科学霸高...一.选择题 1.在设计分时操作系统,首先要考虑的是(...银行家算法问题:例如课后练习 P115 页 22 题 3....
操作系统模拟练习题-2
西安交大附中理科学霸高... 东北师大附中理科学霸高... 操作系统模拟练习题-1...操作系统(本科)模拟练习题 操作系统(本科)模拟练习题-2 一、选择题(选择一个...
操作系统复习题含答案
西安交大附中理科学霸高... 东北师大附中理科学霸高...计算机操作系统试题 45页 免费 习题课答案版(徐向英...用首次适应算法和最佳适应算法画出时刻 t 的空闲区...
操作系统期末复习题
西安交大附中理科学霸高... 东北师大附中理科学霸高...1/2 相关文档推荐 ...暂无评价|0人阅读|0次下载|举报文档 三、课程练习及参考解答一、选择题(选择一...
更多相关标签: