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

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


习题课(一)

张航 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


赞助商链接
相关文章:
西安交大《锅炉》课后习题答案
西安交大《锅炉》课后习题答案 - 第1 章 锅炉基本知识 1. 阐述世界及我国的能源结构特点。 略。 2. 什么是能源?什么是一次能源与二次能源? 能源是指自然界...
西安交大《机械设计基础》课后习题答案综合版
西安交大《机械设计基础》课后习题答案综合版_工学_...机械运动系统方案设计的基本要求和一般程序、机械零件...机械设计基础(第五版)课... 685人阅读 175页 1...
第一章课程概论习题(西安交大精品课程)
第一章课程概论习题(西安交大精品课程) - 习题 1.1 选择题 1.最早的计算机是用来进行 A) 科学计算 2.在计算机中采用二进制是因为 A) 电子元件只有两个状态 ...
西安交大材料科学基础课后答案
西安交大材料科学基础课后答案_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 西安交大材料科学基础课后答案_工学_高等教育_教育专区。第一章 8....
大学物理实验课后习题答案-西安交大张永利主编
大学物理实验课后习题答案-西安交大张永利主编_物理_自然科学_专业资料。大学物理实验课后习题答案-西安交大张永利主编第一章误差估算与数据处理方法 课后习题答案 1.指...
电机学课后答案(西安交通大学)
电力电子课后习题答案(西... 13页 免费 西安交通大学电机学课件... 182...电机学第二版__胡虔生_课... 29页 1下载券 西安交通大学电机学课件 178页...
西南交大土力学习题课
西南交大土力学习题课_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 西南交大土力学习题课_理学_高等教育_教育专区。习题课一、物理性质 1. 用...
西安交通大学——应用数理统计课后答案_
习题1 1.1 解:由题意 p ? x ? u ? 1? ?...信号与线性系统 第二版 ... 21页 免费 【西安...西安交大材料科学基础课... 9页 免费 喜欢...
西交大复变函数考查课习题及答案
标签: 复变函数| 西交大| 西交大复变函数考查课习题及答案_理学_高等教育_教育专区。2015年西交大复变函数考查课习题及答案 ...
西交大数字电子技术考查课习题及答案
暂无评价|0人阅读|0次下载|举报文档西交大数字电子技术考查课习题及答案_工学_高等教育_教育专区。西安交通大学现代远程教育考试卷课姓 成绩 程:数字电子技术考试...
更多相关标签: