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

1、习题课（一）张航2013.11.4Contact me张航Email: Addr : 西一楼721Ftp : 28User : stuPwd : 2013Upload your file to /up/, download the shared file from /down/.Brief 第六章及之前作业存在的问题 补充习题（重点在于进程同步）Assignment: 6.4Points：1.等待自旋锁期间进程仍然等待自旋锁期间进程仍然占用处理器占用处理器2.自旋锁需要的进入条件必须由自旋锁需要的进入条件必须由其他进程其他进程满足满足Assignment: 6

2、.9Advice:将高级语言代码细化为汇编代码进行分析将高级语言代码细化为汇编代码进行分析start:mov eax,scmp eax,0jng startdec eaxmov s,eaxAssignment: 6.11Steps:1.从题目中找出各方进程争夺的从题目中找出各方进程争夺的共享资源共享资源2.所有的共享资源都应当有所有的共享资源都应当有相应的信号量相应的信号量进行保护进行保护3.分析各角色的行为逻辑，必要时定义分析各角色的行为逻辑，必要时定义辅助变量或信号量辅助变量或信号量，如果辅助变量也是多，如果辅助变量也是多进程共享访问的，则应当定义进程共享访问的，则应当定义对应的互斥锁对应

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 endprocedure customer; begin p(mutex); if (w

4、aiting 东东 一人：东一人：东西西 两个人：西两个人：西东东 两个人：东两个人：东西西西东桥中央设置信号量如下设置信号量如下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); 经东段桥，从桥中央到东岸

5、； V(east); V(WE); V(EW); end; 3.把学生和监考老师都看作进程把学生和监考老师都看作进程, 学生有学生有N人人, 教师教师1人人. 考场门口每次只能进出一个人考场门口每次只能进出一个人, 进考场原则是先来先进进考场原则是先来先进. 当当N个学生都进入考场后个学生都进入考场后, 教师才能发卷子教师才能发卷子. 学生交卷后学生交卷后可以离开考场可以离开考场. 教师要等收上来全部卷子并封装卷子后才教师要等收上来全部卷子并封装卷子后才能离开考场能离开考场. 问题问题: 问共需设置几个进程问共需设置几个进程? 试用试用P、V操作解决上述问题中的同步和互斥关系操作解决上述问题中

6、的同步和互斥关系. 该题解析是错误的！该题解析是错误的！ 【解析】【解析】： 定义一个共享变量定义一个共享变量StudentCounter=N 定义四个信号量：定义四个信号量： Mutex=1，实现考场门口的互斥进入，实现考场门口的互斥进入 M1=1，实现对，实现对StudentCounter的互斥访问；的互斥访问； M2=1，表示学生是否到齐了，教师是否可以发，表示学生是否到齐了，教师是否可以发试卷；试卷； M3=1，表示试卷是否收齐了，教师是否可以离，表示试卷是否收齐了，教师是否可以离开开 共需设置二个进程：学生进程，教师进程共需设置二个进程：学生进程，教师进程学生：学生： P(mutex

7、); 进入考场；进入考场； V(mutex);P（M1）；）； StudentCounter：=StudentCounter -1； If StudentCounter=0 V(M2);V(M1);答题；答题；P（M1）；）； StudentCounter：=StudentCounter+1； 交试卷；交试卷； If StudentCounter=N V(M3); 离开考场；离开考场；V(M1); P(mutex); 离开考场；离开考场； V(mutex);教师：教师： P(mutex); 进入考场；进入考场； V(mutex); P（M2）；）； 发试卷；发试卷； 巡视考场；巡视考场； 收试

8、卷；收试卷； P（M3）；）； 离开离开考虑一个学生“一马当先”的情况。不应共用一个StudentCounter 4.流水线问题流水线问题 某流水线有某流水线有4个并发工序个并发工序P1、P2、P3、P4，他们，他们执行情况如下：执行情况如下： P1先执行；先执行；P1结束后，结束后，P2，P3同时开始执行，同时开始执行，P2，P3都结束后，都结束后，P1才能继续下一次执行，同时才能继续下一次执行，同时P4开始执行。试用开始执行。试用PV操作实现他们之间的同步。操作实现他们之间的同步。【解析解析】：SA12,SB12,SA13,SB13,SB24,SB34;SemophoreSA12:=SA1

9、3:=1;SB12:=SB13:=SB24:=SB34:=0;Process PCBeginP(SB13)执行执行P3V(SB34)V(SA13)End;(PC)Process PBBeginP(SB12)执行执行P2V(SB24)V(SA12)End;(PB)Process PDBeginP(SB24)P(SB34)执行执行P4End;(PD)Process PABeginP(SA12)P(SA13)执行执行P1V(SB13)V(SB12)End;(PA) 5.设在公共汽车上，司机和售票员的活动分设在公共汽车上，司机和售票员的活动分别如下：别如下： 司机的活动：启动车辆；正常行车；到站司机的

10、活动：启动车辆；正常行车；到站停车。停车。 售票员的活动：关车门；售票；开车门。售票员的活动：关车门；售票；开车门。 问题问题:在汽车不停地到站、停车以及行驶的在汽车不停地到站、停车以及行驶的过程中，司机和售票员之间的活动有什么同过程中，司机和售票员之间的活动有什么同步关系？步关系？ 解答：解答： 首先分析两个进程之间的同步关系。汽车行驶过首先分析两个进程之间的同步关系。汽车行驶过程中，司机活动与售票员活动之间的同步关系为：程中，司机活动与售票员活动之间的同步关系为： 售票员关车门后，向司机发开车信号售票员关车门后，向司机发开车信号 司机接到开车信号后起动车辆司机接到开车信号后起动车辆 在汽车

11、正常行驶过程中售票员售票在汽车正常行驶过程中售票员售票 到站时司机停车到站时司机停车 售票员在车停后开车门让乘客下车售票员在车停后开车门让乘客下车 定义两个信号量定义两个信号量s1：表示是否允许司机起动车辆，：表示是否允许司机起动车辆，s2：表示是否允许售票员开门。初值为：表示是否允许售票员开门。初值为0。请将以下描述这两个活动的PV操作补充完整：Semaphore s1=0;Semaphore s2=0;main()cobegindriver();conductor();Coend; driver()while(1)p(s1); 启动车辆；启动车辆； 正常行车；正常行车； 到站停车；到站停车

12、； ； conductor()while(1)关车门；关车门； ； 售票；售票； p(s2); 开车门；开车门； 上下乘客；上下乘客；Semaphore s1=0;Semaphore s2=0;main()cobegindriver();conductor();Coend; driver()while(1)p(s1); 启动车辆；启动车辆； 正常行车；正常行车； 到站停车；到站停车； v(s2)； conductor()while(1)关车门；关车门；v（s1） ； 售票；售票； p(s2); 开车门；开车门； 上下乘客；上下乘客；CPU调度习题（1）一个具有一个具有两道两道作业的批处理系统，

13、作业调度采用作业的批处理系统，作业调度采用短作业短作业优先的调优先的调度算法，进程调度采用以优先数为基础的度算法，进程调度采用以优先数为基础的抢占式调度抢占式调度算法，如下算法，如下表的作业序列（表中所有作业优先数即为进程优先数，数值越小表的作业序列（表中所有作业优先数即为进程优先数，数值越小优先级越高）。要求：优先级越高）。要求：（1）列出所有作业进入内存时间及结束时间）列出所有作业进入内存时间及结束时间（2）计算平均周转时间）计算平均周转时间 作业名作业名 到达时间到达时间 估计运算时间估计运算时间 优先数优先数 A 10：00 40分分 5 B 10：20 30分分 3 C 10：30

14、50分分 4 D 10：50 20分分 610:00 A作业到达作业到达, 作业作业A调入内存，进程调度程序调度调入内存，进程调度程序调度A运行运行10:20 B作业到达作业到达,作业作业B调入内存调入内存,抢占进程抢占进程A的处理机的处理机,A回到就绪队回到就绪队列列,A还需运行还需运行20分钟分钟10:30 C作业到达作业到达,在后备队列中等待在后备队列中等待10:50 B运行运行30分钟后结束运行分钟后结束运行,D作业到达作业到达,后备队列中有后备队列中有C,D两个作业两个作业等待调度等待调度,根据短作业优先原则根据短作业优先原则,D调入内存调入内存.内存中内存中,A在就绪队列上已等待在

15、就绪队列上已等待了了30分钟分钟,A的优先级高于的优先级高于D,A运行运行,D就绪就绪.此时此时C在后备队列中已等待了在后备队列中已等待了20分钟并继续等待分钟并继续等待.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各作业的周转时间为各作业的周转时间

16、为: A:70 B:30 C:90 D:90平均周转时间为平均周转时间为(70+30+90+90)/4=70一个一个四道四道作业的操作系统中，设在一段时间内先后到达作业的操作系统中，设在一段时间内先后到达6个作业，它个作业，它们的提交时间和运行时间见下表们的提交时间和运行时间见下表作业号作业号 提交时间提交时间 运行时间运行时间 JOB1JOB2JOB3JOB4JOB5JOB68:008:208:258:308:358:4060352025 510系统采用系统采用SJF算法，算法，作业被调度进入运行后不再退出作业被调度进入运行后不再退出，但当一作业进，但当一作业进入运行时，可以调整运行的优先次

17、序。入运行时，可以调整运行的优先次序。1 分别给出上述分别给出上述6个作业的执行时间次序个作业的执行时间次序2 计算作业的平均周转时间计算作业的平均周转时间CPU调度习题（调度习题（2 2）【解析】【解析】四道的系统四道的系统,作业调度最多可选择四道作业进入内存作业调度最多可选择四道作业进入内存,以进程的形式运行以进程的形式运行;进程调度采用可抢占的短作业优先调度原则进程调度采用可抢占的短作业优先调度原则8：00 J1到达，无竞争者，进入内存。到达，无竞争者，进入内存。8：20 J1运行运行20分钟，剩余分钟，剩余40分钟；分钟；J2到达，运行时间为到达，运行时间为35分钟，分钟，小于小于J1

18、， 取代取代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结束，离开。结束，离开