操作系统期末复习老师的.ppt

需掌握的典型算法及应用 进程同步的例题： 例7、某寺庙，有小和尚、老和尚若干。有一水缸，由小和尚用水桶从井中提水入缸，老和尚用水桶从缸里取水饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个水桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可以同时进行。试用P、V操作给出小和尚、老和尚动作的算法描述。 分析： 小和尚从井中取水并向缸中倒水为一个进程，而老和尚从缸中取水为另一个进程。 有关互斥的资源有： 水井（一次仅允许一个水桶进出）； 水缸（一次倒水、取水仅一个水桶）。 分别为它们设置信号量mutex1、mutex2来实现互斥，初值均为1。 分析（续）： 有关同步的问题是： 3个水桶----无论是从井中取水还是倒水入缸或取水出缸都是一次一个，即为其设置信号量count，初值为3，抢不到水桶的进程只好等待。 此外，设置信号量empty来控制入缸的水量，初值为10，当水缸满时不可入水；设置信号full控制出缸的水量，初值为0，当水缸空时不可出水。 Begin mutex1:=1;mutex2:=1; empty:=10;full:=0; count:=3; Cobegin 小和尚i（i=1,2,…）打水； 老和尚j（j=1,2,…）取水； Coend; End. 小和尚i（i＝1,2,…）打水: Begin Repeat P(empty); /*看水缸满否,满则阻塞打水进程*/ P(count); /*申请打水的桶*/ P(mutex1);/*互斥使用水井,即不允许两和尚同时打水*/ 从井中取水； V(mutex1); P(mutex2); /*互斥使用水缸*/ 送水入缸; V(mutex2); V(count); /*归还水桶*/ V(full) /*水缸又多一桶水*/ Until false End; 老和尚j(j=1,2,…)取水: Begin Repeat P(full); /*看水缸是否有水，无水则阻塞取水进程*/ P(count); /*申请取水的桶*/ P(mutex2); /*互斥使用水缸*/ 从缸中取水； V(mutex2); V(count) /*归还水桶*/ V(empty); /*缸中少了一桶水*/ Until false End * 1.调度算法（范围：先来先服务、短优先、非剥夺式优先级） 2.银行家算法 3.页面置换算法（范围：先进先出、理想型、最近最久未使用） 4.页式管理之地址变换 5.磁盘调度算法（范围：先来先服务、最短寻道时间优先、SCAN） 6.进程同步控制—生产者-消费者问题及变形 例1：4个进程ABCD的到达时间和要求系统的服务时间如下表，请分析按照FCFS算法进行调度时的执行过程，并填写下表。 执行过程如下 1.99 199 202 102 100 3 D 100 100 102 101 1 2 C 1 100 101 1 100 1 B 1 1 1 0 1 0 A 带权周转时间 周转时间 完成时间 开始执行时间 服务时间 到达时间 进程名 A B C D 0 进程 时间 1 101 102 202 Wi=Ti / TS Ti=T完成i-T提交i 答： 例1：4个进程ABCD的到达时间和要求系统的服务时间如下表，请分析按照SPF算法进行调度时的执行过程，并填写下表。 执行过程如下 1.99 199 202 102 100 3 D 100 100 102 101 1 2 C 1 100 101 1 100 1 B 1 1 1 0 1 0 A 带权周转时间 周转时间 完成时间 开始执行时间 服务时间 到达时间 进程名 A B C D 0 进程 时间 1 101 102 202 Wi=Ti / TS Ti=T完成i-T提交i 答： 例2：考虑5个进程P1P2P3P4P5如下表，规定进程的优先数越小优先级越高，请分析按照 非剥夺式优先级调度算法时各进程执行过程，并计算采用每算法时的平均周转时间（假设忽略进程的调度时间）。 非剥夺式HPF过程如下: 3 9 13 18 优先数 运行时间／ms 创建时刻 进程 3 3 0 P1 4 2 8 P5 2 5 6 P