华东理工815操作系统第9讲

1、课程主要内容课程主要内容操作系统引论（第操作系统引论（第1 1章）章）进程管理（第进程管理（第2-32-3章）章）存储管理（第存储管理（第4 4章）章）设备管理（第设备管理（第5 5章）章）文件管理（第文件管理（第6 6章）章）操作系统接口（第操作系统接口（第7 7章）章）UnixUnix操作系统（第操作系统（第1010章）章）Process Management Process Management 进程管理进程管理u进程的基本概念与控制进程的基本概念与控制v进程的基本概念进程的基本概念v进程控制进程控制v线程的基本概念线程的基本概念vUNIXUNIX中进程的描述与控制中进程的描述与控制u进

2、程同步与通信进程同步与通信v进程同步进程同步v经典进程的同步问题经典进程的同步问题v管程机制管程机制v进程通信进程通信vUNIXUNIX中进程的同步与通信中进程的同步与通信u处理机调度与死锁（第处理机调度与死锁（第3 3章）章）第第3 3章章 处理机调度与死锁处理机调度与死锁 在多道程序环境下，一个作业从提交到执行，通常在多道程序环境下，一个作业从提交到执行，通常都要经历多级调度，如都要经历多级调度，如高级调度高级调度、低级调度低级调度、中级调度中级调度等。而系统的运行性能在很大程度上取决于调度，因此等。而系统的运行性能在很大程度上取决于调度，因此调度便成为多道程序的关键。调度便成为多道程序的

3、关键。 在多道程序环境下，由于多个进程的并发执行，改在多道程序环境下，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力，然而，善了系统资源的利用率并提高了系统的处理能力，然而，多个进程的并发执行也带来了新的问题多个进程的并发执行也带来了新的问题-死锁。死锁。第第3 3章章 处理机调度与死锁处理机调度与死锁u处理机调度的层次处理机调度的层次u调度队列模型和调度准则调度队列模型和调度准则u调度算法调度算法u实时调度实时调度uUNIXUNIX系统中进程的调度系统中进程的调度v产生死锁的原因和必要条件产生死锁的原因和必要条件v预防死锁的方法预防死锁的方法v死锁的避免死锁的避免v死锁

4、的检测与解除死锁的检测与解除v本章作业本章作业3.1 3.1 处理机调度的层次处理机调度的层次 在多道程序环境下，一个作业从提交直到完成，在多道程序环境下，一个作业从提交直到完成，往往要经历多级调度。往往要经历多级调度。 在不同操作系统中所采用的调度层次不完全相在不同操作系统中所采用的调度层次不完全相同。同。 有些系统中：仅采用一级调度；有些系统中：仅采用一级调度； 另一些系统：可能采用两级或三级调度。另一些系统：可能采用两级或三级调度。 在执行调度时所采用的调度算法也可能不同。在执行调度时所采用的调度算法也可能不同。一、调度的层次一、调度的层次 如图所示。如图所示。中级调度中级调度新建态新建

5、态挂起就绪挂起就绪态态挂起等待挂起等待态态高级调度高级调度低级调度低级调度运行态运行态就绪态就绪态等待态等待态终止终止态态二、高级调度（二、高级调度（1 1） 一个作业从提交开始，往往要经历三级调一个作业从提交开始，往往要经历三级调度：度：高级调度高级调度、低级调度低级调度、中级调度中级调度。有关作业的几个基本概念有关作业的几个基本概念（1 1）作业）作业（2 2）作业步）作业步（3 3）作业流）作业流（4 4）作业控制块（）作业控制块（JCBJCB） 是作业在系统中存在的标志，其中保存了系是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。统对作业进行管理和调度所需的

6、全部信息。二、高级调度（二、高级调度（2 2）高级调度高级调度（长程（长程/ /作业作业/ /宏观调度）宏观调度）（1 1）用于决定把外存上处于后备队列中的哪些作）用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的业调入内存，并为它们创建进程、分配必要的资源，排在就绪队列上。资源，排在就绪队列上。（2 2）在批处理系统中）在批处理系统中, ,大多配有作业调度大多配有作业调度, ,但在分但在分时系统及实时系统中时系统及实时系统中, ,一般不配置一般不配置. .（3 3）作业调度执行频率很低）作业调度执行频率很低, ,通常为几分钟一次通常为几分钟一次, ,甚至更久。甚至

7、更久。u高级调度需解决的问题高级调度需解决的问题（1 1）主要任务是从外存后备队列中）主要任务是从外存后备队列中选择多少作业选择多少作业进入就绪队进入就绪队列，即允许多少作业同时在内存中运行（多道程序的列，即允许多少作业同时在内存中运行（多道程序的“道道或度或度” ）。若作业太多，则可能会影响系统的服务质量）。若作业太多，则可能会影响系统的服务质量（如周转时间太长），若太少，又将导致系统资源利用率（如周转时间太长），若太少，又将导致系统资源利用率和吞吐量的下降。因此，应根据系统的规模和运行速度来和吞吐量的下降。因此，应根据系统的规模和运行速度来确定，同时确定，同时要求要求I/OI/O型进程型进

8、程与与CPUCPU型进程型进程中和中和调度。调度。（2 2）应）应将哪些作业从外存调入内存将哪些作业从外存调入内存，将取决于调度算法（先，将取决于调度算法（先来先服务、短作业优先等）。来先服务、短作业优先等）。 二、高级调度（二、高级调度（3 3）三、低级调度三、低级调度( (短程短程/CPU/CPU/进程进程/ /微观调度微观调度) )（1 1）主要任务是从就绪队列中选择）主要任务是从就绪队列中选择一个一个进程来执行并分配处理机。进程来执行并分配处理机。（2 2）是）是OSOS中最基本的调度。中最基本的调度。（3 3）调度频率非常高，一般几十毫秒一次。）调度频率非常高，一般几十毫秒一次。（4

9、 4）常采用）常采用非抢占（非剥夺）方式非抢占（非剥夺）方式和和抢占抢占（剥夺剥夺）方式方式两种。两种。（5 5）引起进程调度的因素：）引起进程调度的因素：v进程正常终止或异常终止进程正常终止或异常终止v正在执行的进程因某种原因而阻塞正在执行的进程因某种原因而阻塞v在引入时间片的系统中，时间片用完。在引入时间片的系统中，时间片用完。v在抢占调度方式中，就绪队列中某进程的优先权变得比当在抢占调度方式中，就绪队列中某进程的优先权变得比当前正执行的进程高。前正执行的进程高。调度方式调度方式-非抢占式进程调度、抢占式进程调度非抢占式进程调度、抢占式进程调度u非抢占方式非抢占方式：一旦把处理机分配给某进

10、程后，便让该进：一旦把处理机分配给某进程后，便让该进程程一直执行一直执行，直到该进程完成或因某事件而被阻塞，才，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。配出去的处理机。 实现简单，系统开销小，常用于批处理系统；但不利实现简单，系统开销小，常用于批处理系统；但不利于处理紧急任务，故实时、分时系统不宜采用。于处理紧急任务，故实时、分时系统不宜采用。u抢占方式抢占方式: : 允许调度程序根据某种原则（时间片、优先允许调度程序根据某种原则（时间片、优先权、短进程优先），权、短进程优先），停止停止

11、正在执行正在执行的进程，而将处理机的进程，而将处理机重新分配给另一进程。重新分配给另一进程。 有利于处理紧急任务，故实时与分时系统中常采用。有利于处理紧急任务，故实时与分时系统中常采用。四、中级调度（中程四、中级调度（中程/ /交换调度）交换调度） 在内存和外存对换区之间按照给定的原则和在内存和外存对换区之间按照给定的原则和策略策略选择进程对换选择进程对换，以解决内存紧张问题，从，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。时系统或具有虚拟存储器的系统中。3.23.2 调度队列模型和调度准则调度队列模型和

12、调度准则 在在OSOS中的任何一种调度中，都将涉及中的任何一种调度中，都将涉及到到进程队列进程队列，由此形成了三种类型的调度，由此形成了三种类型的调度队列模型。队列模型。v仅有进程调度的调度队列模型仅有进程调度的调度队列模型v具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型v同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型一、仅有进程调度的调度队列模型一、仅有进程调度的调度队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列进程调度进程调度时间片完时间片完CPU进程完成进程完成等待事件等待事件事事件件出出现现交互用户交互用户二、具有高级和低级调度的调度队列模型二、具

13、有高级和低级调度的调度队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完后后备备队队列列进程调度进程调度CPU进程完成进程完成事事件件出出现现等待事件等待事件1等待事件等待事件2等待事件等待事件n作业作业调度调度 就就 绪绪 队队 列列挂挂 起起 就就 绪绪 队队 列列时间片完时间片完阻阻 塞塞 队队 列列后后备备队队列列进程调度进程调度CPU进程完成进程完成事事件件出出现现等待事件等待事件作业作业调度调度挂挂 起起 阻阻 塞塞 队队 列列中级调度中级调度事件出现事件出现挂起挂起挂起挂起交互型作业交互型作业批量作业批量作业三、同时具有三级调度的调度队列模型三、同时具有三级调度

14、的调度队列模型四、选择调度方式和算法的若干准则（四、选择调度方式和算法的若干准则（1 1） 在一个操作系统的设计中，应如何选择调度方式和在一个操作系统的设计中，应如何选择调度方式和算法，在很大程度上取决于操作系统的类型及其目标，算法，在很大程度上取决于操作系统的类型及其目标，选择调度方式和算法的准则有：选择调度方式和算法的准则有：u 面向用户的准则面向用户的准则v周转时间短周转时间短v响应时间快响应时间快v截止时间的保证截止时间的保证v优先权准则优先权准则u 面向系统的准则面向系统的准则v系统吞吐量系统吞吐量v处理机利用率好处理机利用率好v各类资源平衡利用各类资源平衡利用u 最优准则最优准则v

15、 最大的最大的CPUCPU利用率利用率v 最大的吞吐量最大的吞吐量v 最短的周转时间最短的周转时间v 最短的等待时间最短的等待时间v 最短的响应时间最短的响应时间四、选择调度方式和算法的若干准则（四、选择调度方式和算法的若干准则（2 2）CPUCPU利用率利用率=CPU=CPU有效工作时间有效工作时间/CPU/CPU总的运行时间，总的运行时间， CPU CPU总的运行时间总的运行时间=CPU=CPU有效工作时间有效工作时间+CPU+CPU空闲等待时空闲等待时间。间。响应时间响应时间-交互式进程从提交一个请求交互式进程从提交一个请求( (命令命令) )到接收到接收到响应之间的时间间隔称响应时间。

16、到响应之间的时间间隔称响应时间。周转时间周转时间-批处理用户从作业提交给系统开始，到作批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，实际上它业完成为止的时间间隔称作业周转时间，实际上它是作业在系统里的等待时间与运行时间之和。应使是作业在系统里的等待时间与运行时间之和。应使作业周转时间或平均作业周转时间尽可能短。作业周转时间或平均作业周转时间尽可能短。四、选择调度方式和算法的若干准则（四、选择调度方式和算法的若干准则（3 3）带权周转时间带权周转时间周转时间周转时间/ /进程要求运行时进程要求运行时间间吞吐量吞吐量-单位时间内处理的作业数。单位时间内处理的作业数。公平性

17、公平性-确保每个用户每个进程获得合理的确保每个用户每个进程获得合理的CPUCPU份额或其他资源份额，不会出现饿死份额或其他资源份额，不会出现饿死情况。情况。3.3 3.3 调度算法调度算法u先来先服务调度算法先来先服务调度算法u短作业短作业/ /进程优先调度算法进程优先调度算法u时间片轮转调度算法时间片轮转调度算法u优先权调度算法优先权调度算法u高响应比优先调度算法高响应比优先调度算法u多级反馈队列调度算法多级反馈队列调度算法 进程调度的核心问题就是采用什么样的算法进程调度的核心问题就是采用什么样的算法将处理机分配给进程，常用的进程调度算法有：将处理机分配给进程，常用的进程调度算法有：一、先来

18、先服务调度算法一、先来先服务调度算法FCFSFCFSu 基本思想基本思想: :按照进程进入就绪队列的先后次序来分配处理机。按照进程进入就绪队列的先后次序来分配处理机。 一般采用非剥夺的调度方式。一般采用非剥夺的调度方式。u ExampleExample: :进程名进程名 到达时间到达时间 服务时间服务时间 A 0 1 B 1 100 C 2 1 D 3 100u 该调度的该调度的GanttGantt（甘特）图为（甘特）图为: :u 平均周转时间平均周转时间=(=(1-0)+(101-1)+(102-2)+(202-3)(1-0)+(101-1)+(102-2)+(202-3)）/4=100/4

19、=100u 平均等待时间平均等待时间=(0-0)+(1-1)+(101-2)+(102-3)/4 = 49.5=(0-0)+(1-1)+(101-2)+(102-3)/4 = 49.5u 平均带权周转时间平均带权周转时间= =？DBCA0 1 2 3 101 102 202 0 1 2 3 101 102 202 甘特图甘特图(Gantt)是作业排序中是作业排序中最常用的一种工具，最早由最常用的一种工具，最早由Henry L. Gantt于于1917年提年提出。这种方法基于作业排序的出。这种方法基于作业排序的目的，是将任务与时间联系起目的，是将任务与时间联系起来的表现形式之一来的表现形式之一。

20、 一、一、FCFSFCFS调度算法（续）调度算法（续）u改变到达顺序改变到达顺序: : 进程名进程名 到达时间到达时间 服务时间服务时间 A 0 1 B 1 100 D 2 100 C 3 1u该调度的该调度的GanttGantt图为图为: :u平均周转时间平均周转时间= =(1-0)+(101-1)+(202-3)+(201-2)/4=124.25u平均等待时间平均等待时间= =(0-0)+(1-1)+(201-3)+(101-2)/4 = 74.25u平均带权周转时间平均带权周转时间= =？周转周转T100100124.25124.25等待等待T49.549.574.2574.25CBDA

21、0 1 2 3 101 201 202 0 1 2 3 101 201 202 FCFSFCFS调度算法存在的问题调度算法存在的问题 从表面上，先来先服务对于所有作业是公平的，从表面上，先来先服务对于所有作业是公平的，即按照它们到来的先后次序进行服务。但如果一个长即按照它们到来的先后次序进行服务。但如果一个长作业先到达系统，就会使许多短作业等待很长的时间，作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。从而引起许多短作业用户的不满。 所以，现在操作系统中，已很少用该算法作为主所以，现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它要

22、调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。常被结合在其它调度策略中使用。二、短作业二、短作业/ /进程优先调度算法进程优先调度算法SJF/SPFSJF/SPFu 短作业优先调度算法（短作业优先调度算法（SJFSJF）v用于作业调度用于作业调度v主要任务是从后备队列中选择一个或若干个估计运行时间最主要任务是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。短的作业，将它们调入内存运行。u 短进程优先调度算法（短进程优先调度算法（SPFSPF）v用于进程调度用于进程调度v主要任务是从就绪队列中选出一个估计运行时间最短的进程，主要任务是从就绪队列

23、中选出一个估计运行时间最短的进程，将处理机分配给它。将处理机分配给它。v可采用抢占（剥夺）（有时称为可采用抢占（剥夺）（有时称为最短剩余时间优先最短剩余时间优先（shortest-remaining-time-firstshortest-remaining-time-first）调度）或者非抢占）调度）或者非抢占（非剥夺）调度方式。（非剥夺）调度方式。二、二、SJ(P)F -SJ(P)F -非抢占式非抢占式u到达顺序到达顺序: : 进程名进程名 到达时间到达时间 服务时间服务时间 A 0 1 B 1 100 D 2 100 C 3 1u该调度的该调度的GanttGantt图为图为: :u平均周

24、转时间平均周转时间= =(1-0)+(101-1)+(102-3)+(202-2)/4=100u平均等待时间平均等待时间= =(0-0)+(1-1)+(101-3)+(102-2)/4 = 49.5u平均带权周转时间平均带权周转时间=？FCFSFCFSSPFSPF周转周转T124.25124.25100100等待等待T74.2574.2549.549.50 1 2 3 101 102 202 0 1 2 3 101 102 202 DBCA二、短作业二、短作业/ /进程优先调度算法进程优先调度算法- -抢占式抢占式u 到达顺序到达顺序: : 进程名进程名 到达时间到达时间 服务时间服务时间 A

25、 0 1 B 1 100 D 2 100 C 3 1u 该调度的该调度的GanttGantt图为图为: :u 平均周转时间平均周转时间=(1-0)+(102-1)+(4-3)+(202-2)=(1-0)+(102-1)+(4-3)+(202-2)）/4=75.75/4=75.75u 平均等待时间平均等待时间=(0-0)+(4-3)+(3-3)+(102-2)/4 = 25.25=(0-0)+(4-3)+(3-3)+(102-2)/4 = 25.25u 平均带权周转时间平均带权周转时间= =？BCDBBA0 1 2 3 4 102 202 0 1 2 3 4 102 202 FCFSFCFSSP

26、F-SPF-非非SPF-SPF-抢抢周转周转T124.25124.2510010075.7575.75等待等待T74.2574.2549.549.525.2525.25uEgEg： 进程进程 到达时间到达时间 服务时间服务时间P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (非抢占式非抢占式) )u平均周转时间平均周转时间=(7-0)+(12-2)+(8-4)+(16-5)/4=8=(7-0)+(12-2)+(8-4)+(16-5)/4=8u平均等待时间平均等待时间 =(0-0)+(8-2)+(7

27、-4)+(12-5)/4 = 4=(0-0)+(8-2)+(7-4)+(12-5)/4 = 4u平均带权周转时间平均带权周转时间= =？SPFSPF（非抢占式）调度（非抢占式）调度73160812P1P3P2P4SPFSPF抢占式调度抢占式调度进程进程到达时间到达时间服务时间服务时间P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (抢占式抢占式) )u平均周转时间平均周转时间=(16-0)+(7-2)+(5-4)+(11-5)/4=7=(16-0)+(7-2)+(5-4)+(11-5)/4=7u平

28、均等待时间平均等待时间=(11-2)+(5-4)+(4-4)+(7-5)/4=3=(11-2)+(5-4)+(4-4)+(7-5)/4=3u平均带权周转时间平均带权周转时间= =？P1P3P242110P457P2P116FCFSFCFS先来先服务调度先来先服务调度进程进程到达时间到达时间服务时间服务时间P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uFCFSFCFSu平均周转时间平均周转时间=(7-0)+(11-2)+(12-4)+(16-5)/4=8.75=(7-0)+(11-2)+(12-4)+(16-5)/

29、4=8.75u平均等待时间平均等待时间 =(0+(7-2)+(11-4)+(12-5)/4 =4.75=(0+(7-2)+(11-4)+(12-5)/4 =4.75u平均带权周转时间平均带权周转时间= =？P142110P257P41612P3SPFSPF与与FCFSFCFS的比较的比较FCFSFCFS非抢占非抢占SPFSPF抢占抢占SPFSPF吞吐量吞吐量0-7ms0-7ms1 11 12 2平均周转时间平均周转时间8.758.758 87 7平均等待时间平均等待时间4.754.754 43 3SJ(P)FSJ(P)F短作业短作业/ /进程优先调度的优缺点进程优先调度的优缺点 优点：优点： 1 1）能有效降低作业的平均等待时间；