进程同步练习.ppt

1、习题课,进程同步练习,进程同步练习,信号量 typedef struct int value; struct process *L; semaphore; P操作 P(S) S.value-; if(S.value 0)把此进程回到到与此资源相关的等待队列中并将此进程挂起 V操作 V(S) s.value+; if(S.value = 0)从此资源相关的等待队列中唤醒一个进程; ,即Wait(S),即Singal(S),进程同步问题的求解依据 信号量的两种应用 实现进程互斥 分析题目中的资源、互斥资源，设置信号量及初值 分析题目中的进程，及其行为，进程访问的资源 利用所设置的信号量控制进程对资

2、源的访问 必要时增加共享变量（如计数器），进程对共享变量的访问是互斥的 实现进程合作（实现前趋关系） 识别是进程合作类型的题目（一般会有合作、协作、配合之类的字样） 分析进程/语句之间的前趋关系，为每条边设置信号量（初值为0） 利用所设置的信号量控制进程/语句执行的次序,题目1： 一个仓库中只库存两种产品：A和B，需要满足条件如下： A的产品数量-B的产品数量 M B的产品数量-A的产品数量 N 每次只能存一种产品 其中M，N均为整数。 分析： A数量与B数量相互制约，假设当前时刻A最多可以再存Sa个，B最多可以再存Sb个，则Sa初值为M-1，Sb初值为N-1，A每库存一个，Sa应该减1（减少

3、一个），Sb应该加1（A加1，B同样加1，题中两个不等式仍然成立）；同理B每库存一个Sb减1，Sa加1。每次只能存一种产品表明仓库中临界资源,设置信号量mutex, 初值为1。,semaphore mutex=1; semaphore Sa=M-1, Sb=N-1; ProcessA() P(Sa); P(mutex); 存一个A产品; V(Sb); V(mutex); ProcessB() P(Sb); P(mutex); 存一个B产品; V(Sa); V(mutex); ,题目2： 三个合作进程A，B，C，需要依次通过同一台输入设备输入各自的数据a，b，c，且输入设备互斥，A接受a，B接受

4、b，C接受c。 A，B，C分别进行如下运算： A: x=a+b B: y=a*b C: z=y+c-a 最终由A进程将x，y，z结果打印出来。 分析： 由于依次通过同一设备，故顺序为A-B-C，即图中的1，4. A中需要B输入的数据b，所以必须在B接收完b后A的计算才能运行。即图的2 C需要B的运算结果，故C要等B计算完后才能计算，即图的5 A需要B，C的运算结果y，z，所以必须B，C计算完成后A才能打印，即图的3，6 输入设备是互斥的，需要互斥信号量。,semaphore mutex=1; semaphore s1=s2=s3=s4=s5=s6=0; ProcessA() P(mutex);

5、 / 获得输入设备 输入a; V(mutex); V(s1); P(s2); x=a+b; P(s3); P(s6); 打印x,y,z; ,ProcessB() P(s1); P(mutex); 输入b; V(mutex); V(s4); V(s2); y=a*b; V(s5); V(s3); ,ProcessC() P(s4); P(mutex); 输入c; V(mutex); P(s5); z=y+c-a; V(s6); ,只要理解一个同步的情况，上面6个同步的情况就非常简单：,A必须先于B完成，可以使用一个信号量来实现：,semaphore S=0; A() .; V(S); B() P

6、(S); .; ,若B先于A执行，则P(S)由于S.value后0故挂起；当A执行V(S)后执行S.value+后S.value=0满足value=0唤醒B，即A先于B执行。 为方便记忆：,题目3; 一条小河上有一座独木桥，规定每次只允许一人过桥。如果把每个过桥看作一个进程，为保证安全，请用信号量操作实现正确管理。 begin s:semaphore; s：=1; cobegin begin wait(s); 过桥； signal(s)； end Coend end,题目4： 一个快餐店，有两个厨师，一个做中餐，一个做西餐，厨师做完一份食物就放在窗口，由顾客自取。窗口只能放下一份食物。到店顾客

7、分两类：要么只吃中餐，要么只吃西餐。试实现进程同步。 分析： 窗口只能放一份食物，是临界资源，设一互斥信号量mutex,初值为1 两个资源信号量：中餐S1,西餐S2,初值都为0 四个进程：中餐厨师，西餐厨师，中餐顾客，西餐顾客,var mutex,s1,s1:semaphore:=1,0,0 Begin Parbegin,中餐厨师： Begin repeat 做中餐; Wait(mutex); 放在窗口; Signal(s1); Until false End,西餐厨师： Begin repeat 做西餐; Wait(mutex); 放在窗口; Signal(s2); Until false

8、End,ParendEnd,中餐顾客： Begin repeat Wait(s1); 从窗口取走中餐; Signal(mutex); 吃中餐; Until false End,西餐顾客： Begin repeat Wait(s2); 从窗口取走西餐; Signal(mutex); 吃西餐; Until false End,题目5： 汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客，试设必要的信号灯及赋初值，写出他们的同步过程。,

9、解答：可以用两个信号量s1、s2，分别表示可以开门和可以开车，其初始值都为0，用PV操作实现为： 司机： 售票员： L0:正常行车 L1:售票 到站停车 P(S1) V(S1) 开车门 P(S2) 关车门 启动开车 V(S2) goto L0 goto L1,题目1：假设有4道作业，它们的提交时刻及执行时间由下表给出： 计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的周转时间和平均带权周转时间，并指出它们的调度顺序。,处理机调度练习,（1）先来先服务调度： 顺序：提交时间 开始执行时间 结束时间 执行时间 周转时间 1、 Ts1=10:00 10:00 Te1=12:00

10、 Tr1=2.00 T1=2 2、 Ts2=10:20 12:00 Te2=13:00 Tr2=1.00 T2=2.7 3、 Ts3=10:40 13:00 Te3=13:30 Tr3=0.50 T3=2.8 4、 Ts4=10:50 13:30 Te4=13:50 Tr4=0.30 T4=3 T=0.25*(2+2.7+2.8+3)=2.625h W=0.25*(2/2+2.7/1+2.8/0.5+3/0.3)=4.825 （2）最短作业优先调度： 顺序：提交时间 开始执行时间 结束时间 执行时间 周转时间,假定要在一台处理机上执行下列作业(如下表所示)，且假定这些作业在时刻0时以1、2、3

11、、4、5的顺序几乎同时到达。 1)说明分别使用FCFS、RR(时间片为1)、SJF、以及优先级法(优先数越小优先级越高)时，这些作业的执行情况(执行顺序)。 2）给出上述算法的平均周转时间和平均带权周转时间。,FCFS,13.4,7.26,18.有5个进程(ABCDE)几乎同时到达一个计算中心，估计的运行时间为2，4，6，8，10分钟，它们的优先级分别为1，2，3，4，5（1为最低优先级），对下面各种调度算法，分别计算进程的平均周转时间和平均带权周转时间。 1）FCFS（设到达顺序为CDBEA） 2）优先级法 3）最短进程优先 4）时间片轮转（时间片为2分钟）,解： 1）执行顺序为CDBEA

12、C周转时间Tc=6-0=6， 带权周转时间Wc=6/6=1 D周转时间Td=14-0=14,带权周转时间Wd=14/8=1.75 B周转时间Tb=18-0=18,带权周转时间Wb=18/4=4.5 E周转时间Te=28-0=28,带权周转时间We=28/10=2.8 A周转时间Ta=30-0=30,带权周转时间Wa=30/2=15,平均周转时间 =19.2分钟,平均带权周转时间 =5.01,2）执行顺序为EDCBA E周转时间Te=10-0=10,带权周转时间We=10/10=1 D周转时间Td=18-0=18,带权周转时间Wd=18/8=2.25 C周转时间Tc=24-0=24,带权周转时间

13、Wc=24/6=4 B周转时间Tb=28-0=28,带权周转时间Wb=28/4=7 A周转时间Ta=30-0=30,带权周转时间Wa=30/2=15,平均周转时间 =22分钟,平均带权周转时间 =5.85,3）执行顺序为ABCDE A周转时间为Ta=2-0=2, 带权周转时间Wa=2/2=1 B周转时间为Tb=6-0=6, 带权周转时间Wb=6/4=1.5 C周转时间为Tc=12-0=12,带权周转时间Wc=12/6=2 D周转时间为Td=20-0=20,带权周转时间Wd=20/8=2.5 E周转时间为Te=30-0=30,带权周转时间We=30/10=3,平均周转时间 =14分钟,平均带权周转时间 =2