处理器管理PPT讲稿.ppt

《处理器管理PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《处理器管理PPT讲稿.ppt（102页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、处理器管理处理器管理处理器管理处理器管理第1页，共102页，编辑于2022年，星期六处理器管理的地位处理器管理的地位第2页，共102页，编辑于2022年，星期六主要内容主要内容3.1 3.1 进程的引入进程的引入3.23.2进程的概念进程的概念3.33.3进程控制进程控制3.43.4线程线程3.53.5处理器调度处理器调度3.63.6调度算法调度算法3.73.7处理器调度和实时调度处理器调度和实时调度第3页，共102页，编辑于2022年，星期六3.1.13.1.1程序的执行方式程序的执行方式(顺序顺序)顺序执行顺序执行特征：顺序性、封闭性、可再现性特征：顺序性、封闭性、可再现性I1C1P1I2

2、C2P2第4页，共102页，编辑于2022年，星期六3.1.23.1.2程序的执行方式程序的执行方式(并发并发)并发执行并发执行I1I2I3I4C1C2C3C4P1P2P3P4t第5页，共102页，编辑于2022年，星期六3.1.13.1.1程序的执行方式程序的执行方式(并发并发)特征特征第6页，共102页，编辑于2022年，星期六与并发有关的错误与并发有关的错误第7页，共102页，编辑于2022年，星期六3.2 3.2 进程的概念进程的概念问题引入问题引入 程序这个静态概念已不能如实反映程序并发执程序这个静态概念已不能如实反映程序并发执行过程的特征。为了深刻描述程序行过程的特征。为了深刻描述

3、程序动态执行动态执行过过程的性质，人们引入程的性质，人们引入“进程（进程（ProcessProcess）”概念。概念。第8页，共102页，编辑于2022年，星期六3.2 3.2 进程的概念进程的概念程序在处理机上执行时所发生的活动程序在处理机上执行时所发生的活动(Dijkstra)(Dijkstra)。是一个容器，该容器用以聚集相关资源。（是一个容器，该容器用以聚集相关资源。（A.S.TanenbaumA.S.Tanenbaum）进程是一个具有独立功能的进程是一个具有独立功能的程序程序关于某个关于某个数数据集合据集合的的一次运行活动一次运行活动。是系统进行资源分。是系统进行资源分配和调度的单位

4、。配和调度的单位。第9页，共102页，编辑于2022年，星期六3.2 3.2 进程的概念进程的概念操作级操作级:图形窗口界面图形窗口界面:一个窗口就是一个进程一个窗口就是一个进程打开窗口：建立一个进程打开窗口：建立一个进程关闭窗口：一个进程结束关闭窗口：一个进程结束字符命令界面字符命令界面:一条命令一般就是一个进程一条命令一般就是一个进程命令行尾回车命令行尾回车:一个进程开始一个进程开始命令执行结束命令执行结束(下一命令提示符出现下一命令提示符出现):):一个进程结束一个进程结束编程级：编程级：进程建立：进程建立：“建立进程建立进程”函数或系统调用函数或系统调用进程结束：进程结束：“撤消进程撤

5、消进程”函数或系统调用，或者程序的函数或系统调用，或者程序的正常或非正常结束。正常或非正常结束。第10页，共102页，编辑于2022年，星期六进程和程序的区别进程和程序的区别 程序静态的，程序静态的，进程是动态的。进程是动态的。程序和进程的组成不同：进程程序和进程的组成不同：进程=程序程序+数据数据+PCB+PCB 程序的存在是永久的，程序的存在是暂时的。程序的存在是永久的，程序的存在是暂时的。一个程序可以对应多个进程，一个进程可包含多个一个程序可以对应多个进程，一个进程可包含多个程序。程序。第11页，共102页，编辑于2022年，星期六进程的特征进程的特征动态性动态性：进程是个动态的概念，有

6、一定的生命周期，要经历创建、：进程是个动态的概念，有一定的生命周期，要经历创建、执行、撤销过程。执行、撤销过程。结构性结构性 ：它由进程控制块、程序段和数据段组成：它由进程控制块、程序段和数据段组成 。并发性并发性 ：在一个系统内可以同时存在多个进程，它们通过交：在一个系统内可以同时存在多个进程，它们通过交替使用处理器，从而实现并发执行。替使用处理器，从而实现并发执行。异步性：异步性：指进程之间在交替使用计算机资源时没有强制的顺指进程之间在交替使用计算机资源时没有强制的顺序，按各自独立的、不可预知的速度向前推进序，按各自独立的、不可预知的速度向前推进 。独立性：独立性：进程是系统分配资源和进行

7、调度的独立单位。进程是系统分配资源和进行调度的独立单位。第12页，共102页，编辑于2022年，星期六3.2.2 3.2.2 进程的状态进程的状态 进程从创建而产生至撤销而消亡的整个生命周期，可进程从创建而产生至撤销而消亡的整个生命周期，可用一组状态加以刻画，按进程在执行过程中的状况至少用一组状态加以刻画，按进程在执行过程中的状况至少定义三种不同的进程状态：定义三种不同的进程状态：运行态运行态（RunningRunning）就绪状态就绪状态（ReadyReady）阻塞状态阻塞状态（BlockedBlocked）当前进程已经分配到当前进程已经分配到CPUCPU，它的程，它的程序正在处理机上执行的

8、状态。序正在处理机上执行的状态。已具备运行条件，但因为其他进程已具备运行条件，但因为其他进程正在占用正在占用CPU,CPU,使它暂时不能运行而使它暂时不能运行而处于等待分配处于等待分配CPUCPU的状态。的状态。进程因等待某种事件发生（例如等待进程因等待某种事件发生（例如等待I/OI/O操作完成，等待其他进程发来的信操作完成，等待其他进程发来的信号）而暂时不能运行的状态，也就是说，号）而暂时不能运行的状态，也就是说，处于阻塞状态的进程尚不具备运行条件，处于阻塞状态的进程尚不具备运行条件，即使即使CPUCPU空闲它也无法使用。空闲它也无法使用。第13页，共102页，编辑于2022年，星期六3.2

9、.2 3.2.2 进程的状态进程的状态引起进程状态转换原因引起进程状态转换原因就绪就绪-运行运行时间一到，调度程序选择一个新的进程运行时间一到，调度程序选择一个新的进程运行运行运行-就绪就绪运行进程用完了时间片；运行进程被中断，因为一高优先运行进程用完了时间片；运行进程被中断，因为一高优先级进程处于就绪状态级进程处于就绪状态第14页，共102页，编辑于2022年，星期六3.2.2 3.2.2 进程的状态进程的状态引起进程状态转换原因引起进程状态转换原因运行运行-阻塞阻塞当一进程所需的东西必须等待时当一进程所需的东西必须等待时对一资源的访问尚不能进行对一资源的访问尚不能进行初始化初始化I/O I

10、/O 且必须等待结果且必须等待结果等待某一进程提供输入等待某一进程提供输入阻塞阻塞-就绪就绪当所等待的事件发生时当所等待的事件发生时第15页，共102页，编辑于2022年，星期六3.2.2 3.2.2 进程的状态进程的状态进程三种状态的转换进程三种状态的转换第16页，共102页，编辑于2022年，星期六3.2.2 3.2.2 进程的状态进程的状态 有一个计算机科学家，有一天女儿过生日，想亲手给女有一个计算机科学家，有一天女儿过生日，想亲手给女儿做一个生日蛋糕。所以他就找了一本有关做蛋糕的食谱，儿做一个生日蛋糕。所以他就找了一本有关做蛋糕的食谱，买了一些原料，面粉、鸡蛋、糖、香料等，然后边看边学

11、买了一些原料，面粉、鸡蛋、糖、香料等，然后边看边学边做。边做。食谱程序；科学家食谱程序；科学家CPUCPU；原料数据；做蛋糕进程；原料数据；做蛋糕进程；这时小儿子哭着跑进来，说手被蜜蜂蛰了。教授只好这时小儿子哭着跑进来，说手被蜜蜂蛰了。教授只好把蛋糕先放在一边。他在食谱上做了个标记，把状态信把蛋糕先放在一边。他在食谱上做了个标记，把状态信息记录了起来。然后又去找了一本医疗手册，查到了相息记录了起来。然后又去找了一本医疗手册，查到了相关的内容，按照上面的指令一步步地执行。当伤口处理关的内容，按照上面的指令一步步地执行。当伤口处理完之后，又回到厨房继续做蛋糕。完之后，又回到厨房继续做蛋糕。CPUC

12、PU从一个进程（做蛋糕）切换到另一个进程（医疗从一个进程（做蛋糕）切换到另一个进程（医疗救护）。救护）。第17页，共102页，编辑于2022年，星期六3.2.2 3.2.2 进程的状态进程的状态五状态模型：新建态新建态就绪态：允许进入就绪态：允许进入运行态运行态完成态完成态：执行完：执行完第18页，共102页，编辑于2022年，星期六3.2.2 3.2.2 进程的状态进程的状态问题出现问题出现进程挂起（进程挂起（suspendsuspend）进程不断创建，系统资源已不满足进程运行进程不断创建，系统资源已不满足进程运行的要求，系统就必须把某些进程挂起，即将进的要求，系统就必须把某些进程挂起，即将

13、进程对换到磁盘中，暂时不参与进程调度，已达程对换到磁盘中，暂时不参与进程调度，已达到平衡操作系统负荷的目的。到平衡操作系统负荷的目的。引起进程挂起原因引起进程挂起原因(P45-46(P45-46：(1)-(4)1)-(4)第19页，共102页，编辑于2022年，星期六挂起（挂起（Suspend):Suspend):把一个进程从内存转到外存。把一个进程从内存转到外存。激活（激活（ActivateActivate）:把一个进程从外存转到内存。把一个进程从外存转到内存。第20页，共102页，编辑于2022年，星期六引入挂起状态后的七状态模型引入挂起状态后的七状态模型第21页，共102页，编辑于202

14、2年，星期六LinuxLinux进程的状态进程的状态 D D Uninterruptible sleep(usually IO)Uninterruptible sleep(usually IO)R R Running or runnable(on run queue)Running or runnable(on run queue)S S Interruptible sleep(waiting for an event to complete)Interruptible sleep(waiting for an event to complete)T T Stopped,either by a

15、 job control signal or because it is Stopped,either by a job control signal or because it is being traced.being traced.X X dead(should never be seen)dead(should never be seen)Z Z Defunct(zombie)process,terminated but not reaped by its Defunct(zombie)process,terminated but not reaped by its parent.pa

16、rent.high-priority(not nice to other users)high-priority(not nice to other users)N N low-priority(nice to other users)low-priority(nice to other users)L L has pages locked into memory(for real-time and custom IO)has pages locked into memory(for real-time and custom IO)s s is a session leader is a se

17、ssion leaderl l is multi-threaded(using CLONE_THREAD,like NPTL pthreads do)is multi-threaded(using CLONE_THREAD,like NPTL pthreads do)+is in the foreground process groupis in the foreground process group第22页，共102页，编辑于2022年，星期六例题例题 1 1如果系统中有如果系统中有N N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；个进程，运行的进程最多几个，最少几个；

18、就绪进程最多几个最少几个；等待进程最多几个，最少几个？等待进程最多几个，最少几个？解答解答：在单处理机系统中，处于运行状态的进程最多为：在单处理机系统中，处于运行状态的进程最多为1 1个，最少为个，最少为0 0个；处于就绪进程最个；处于就绪进程最多为多为N-1N-1个，最少为个，最少为0 0个；处于阻塞的进程最多为个；处于阻塞的进程最多为N N个，最少为个，最少为0 0个。个。2.2.有没有这样的状态转换，为什么？有没有这样的状态转换，为什么？（1 1）等待等待运行；运行；（2 2）就绪就绪等待等待第23页，共102页，编辑于2022年，星期六3.2.3 3.2.3 进程控制块进程控制块进程描

19、述进程描述进程控制块进程控制块程序和数据组成了进程的实体（静态文本）程序和数据组成了进程的实体（静态文本）需要一个数据结构来描述进程当前状态、本身特性、需要一个数据结构来描述进程当前状态、本身特性、对资源的占用以及调度信息等，即进程控制块对资源的占用以及调度信息等，即进程控制块（Process Control Block,PCBProcess Control Block,PCB）进程进程程序程序+数据数据+PCB+PCB第24页，共102页，编辑于2022年，星期六3.2.3 3.2.3 进程控制块进程控制块第25页，共102页，编辑于2022年，星期六3.2.3 3.2.3 进程控制块进程控

20、制块PCBPCB是进程存在的是进程存在的唯一标志；唯一标志；PCBPCB常驻内存常驻内存pid进程状态进程状态现场现场优先级优先级阻塞原因阻塞原因程序地址程序地址同步机制同步机制资源清单资源清单链接指针链接指针第26页，共102页，编辑于2022年，星期六CPUCPU在进程之间的切换在进程之间的切换第27页，共102页，编辑于2022年，星期六PCBPCB的组织的组织链表：同一状态的进程其链表：同一状态的进程其PCBPCB组成一链表，组成一链表，多个状态对应多个不同的链表。多个状态对应多个不同的链表。各状态的进程形成不同的链表：就绪链各状态的进程形成不同的链表：就绪链表、阻塞链表表、阻塞链表第

21、28页，共102页，编辑于2022年，星期六链表链表链表链表执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针1PCB90PCB89PCB77PCB6PCB58PCB40PCB33PCB24PCB1PCBPCBPCBPCB的组织的组织的组织的组织第29页，共102页，编辑于2022年，星期六PCBPCB的组织的组织索引表：同一状态的进程归入一个索引表：同一状态的进程归入一个indexindex表（由表（由indexindex指向指向PCBPCB），多个状态对应多个不同的），多个状态对应多个不同的indexindex表表各状态的进行形成不同的索引表：就绪索引各状态的进行形成不同的索

22、引表：就绪索引表、阻塞索引表表、阻塞索引表第30页，共102页，编辑于2022年，星期六3.2.3 3.2.3 进程控制块进程控制块PCBPCB的组织的组织索引表索引表执行指针执行指针就绪表指针就绪表指针阻塞表指针阻塞表指针PCB7PCB6PCB5PCB4PCB3PCB2PCB1第31页，共102页，编辑于2022年，星期六补充补充PCBPCB和进程的代码数据放在一起吗？和进程的代码数据放在一起吗？系统态和用户态系统态和用户态系统空间和用户空间系统空间和用户空间第32页，共102页，编辑于2022年，星期六3.3 3.3 进程控制进程控制OSOS如何管理和控制进程如何管理和控制进程必须知道必须

23、知道进程的位置进程的位置（依赖于所使用的存储管理方（依赖于所使用的存储管理方案）案）必须知道必须知道进程的属性进程的属性（PCBPCB）必须能够必须能够创建、撤销进程创建、撤销进程必须能够必须能够改变进程的状态改变进程的状态第33页，共102页，编辑于2022年，星期六l 进程控制的职责：l 进程的创建l 进程的撤消l 进程的阻塞与唤醒l 进程控制是通过执行各种原语来实现的。3.3 3.3 进程控制进程控制第34页，共102页，编辑于2022年，星期六原语原语是由若干条机器指令构成的、用于完成特是由若干条机器指令构成的、用于完成特定功能的一段程序。原语在执行过程中是不可定功能的一段程序。原语在

24、执行过程中是不可分割的。（分割的。（P47P47）3.3 3.3 进程控制进程控制第35页，共102页，编辑于2022年，星期六3.3.3 3.3.3 进程的创建进程的创建进程图进程图引起创建进程的事件引起创建进程的事件进程的创建过程进程的创建过程123第36页，共102页，编辑于2022年，星期六3.3.3 3.3.3 进程的创建进程的创建A AB BC CD DE EI IJ JF FHHL LMMKKGGA AB BC CD DE EI IJ JF FHHL LMMKKGG第37页，共102页，编辑于2022年，星期六入口入口查查PCBPCB链表链表有空有空PCBPCB取空表取空表PCB

25、(i)PCB(i)填填PCB(i)PCB(i)相应项相应项PCB(i)PCB(i)入就绪队列入就绪队列PCB(i)PCB(i)入进程家族入进程家族返回返回创建失败创建失败YN第38页，共102页，编辑于2022年，星期六进程创建进程创建#include#include pid_t fork(void);功能：创建一个新的进程。返回值：在子进程中为0，在父进程中为子进程ID，出错为-1第39页，共102页，编辑于2022年，星期六进程创建进程创建该函数被调用一次，但返回两次。两次返回的区别是子进程的返回值是0，而父进程的返回值则是子进程的进程ID一般来说，在fork之后是父进程先执行还是子进程先

26、执行是不确定的。这取决于内核所使用的调度算法。新创建的子进程是父进程的完全克隆完全克隆,会复制父进程的数据段、堆、栈空间（共享代码段）。第40页，共102页，编辑于2022年，星期六进程相关术语进程相关术语init 进程领养：当父进程在子进程结束前结束，子进程变成了孤儿进程，孤儿进程被init进程收养，子进程的父进程就变成了init进程。僵尸进程当子进程在父进程结束前结束，如果父进程没有释放子进程的资源(默认)，那么子进程就变成了一个僵尸进程。第41页，共102页，编辑于2022年，星期六进程创建进程创建第42页，共102页，编辑于2022年，星期六3.3.4 3.3.4 引起进程终止的事件引

27、起进程终止的事件寿终：进程运行完自行退出寿终：进程运行完自行退出自杀：进程因错误而自行退出自杀：进程因错误而自行退出第43页，共102页，编辑于2022年，星期六3.3.2 3.3.2 引起进程终止的事件引起进程终止的事件他杀：进程被其它进程强行杀死或他杀：进程被其它进程强行杀死或由用户杀死由用户杀死处决：进程因异常而强行终结处决：进程因异常而强行终结第44页，共102页，编辑于2022年，星期六 检索相应的PCB，读其状态 若处于执行状态，则终止执行 若有子孙进程则终止子孙进程 释放终止进程的全部资源 将PCB从队列中移出3.3.4 进程的终止过程第45页，共102页，编辑于2022年，星期

28、六入口查进程链表有此PCB释放该进程所占资源释放该PCB结构本身返回出错处理有子进程无有有无第46页，共102页，编辑于2022年，星期六3.3.3 3.3.3 进程的阻塞与唤醒进程的阻塞与唤醒1、引起进程阻塞的事件2、进程阻塞的过程3、进程唤醒的过程4、唤醒原语的执行过程第47页，共102页，编辑于2022年，星期六引起进引起进程阻塞程阻塞的事件的事件启动某种操作启动某种操作请求系统服务请求系统服务新数据尚未到达新数据尚未到达无新工作可做无新工作可做第48页，共102页，编辑于2022年，星期六 执行状态的进程调用阻塞原语 进程变为阻塞状态 PCB进入阻塞队列 转进程调度程序，进行切换进程阻

29、塞的过程第49页，共102页，编辑于2022年，星期六被阻塞进程期待的事件发生。由发现者进程调用唤醒原语 唤醒阻塞进程。阻塞进程进入就绪状态。进程唤醒的过程第50页，共102页，编辑于2022年，星期六3.3 3.3 进程控制进程控制LinuxLinux进程控制原语进程控制原语:进程创建进程创建 forkfork进程监控进程监控 psps进程终止进程终止 killkill第51页，共102页，编辑于2022年，星期六3.4 3.4 线程线程线程的引入线程的引入进程：资源分配单位和进程：资源分配单位和CPUCPU调度单位调度单位缺点：时间空间开销大，限制并发度的提高缺点：时间空间开销大，限制并发

30、度的提高将程序块的执行从进程中分离出来将程序块的执行从进程中分离出来程序块执行需要单独的：程序块执行需要单独的：执行状态：寄存器内容、栈、局部内存执行状态：寄存器内容、栈、局部内存程序块执行不需要单独的：程序块执行不需要单独的：进程资源：如文件、页表内容等进程资源：如文件、页表内容等多线程：将一个程序分成多个并发的活动（程序块）多线程：将一个程序分成多个并发的活动（程序块）第52页，共102页，编辑于2022年，星期六3.4 3.4 线程线程进程进程=线程线程+资源集资源集进程作为拥有资源的基本单位，线程是系统调进程作为拥有资源的基本单位，线程是系统调度的基本单位。度的基本单位。第53页，共1

31、02页，编辑于2022年，星期六3.4 3.4 线程线程进程和线程进程和线程资源所有权（资源所有权（ProcessProcess）调度的实体（调度的实体（ThreadThread）第54页，共102页，编辑于2022年，星期六3.4 3.4 线程线程线程描述线程描述线程状态（运行、就绪、等待）线程状态（运行、就绪、等待）一个执行栈一个执行栈未运行时保存的线程上下文、静态存储局部变量未运行时保存的线程上下文、静态存储局部变量对内存和其他进程资源的访问对内存和其他进程资源的访问与该进程中其他线程共享资源与该进程中其他线程共享资源第55页，共102页，编辑于2022年，星期六3.4 3.4 线程线程

32、用户级线程用户级线程由应用程序（线程库）实现线程管理（由应用程序（线程库）实现线程管理（POSIX PthreadsPOSIX Pthreads、Win32 threadsWin32 threads）内核感觉不到线程的存在内核感觉不到线程的存在优点优点共享一个进程用户空间中，线程管理不需要内核模式的切换共享一个进程用户空间中，线程管理不需要内核模式的切换可运行任何可运行任何OSOS上，内核无需修改。上，内核无需修改。缺点缺点全阻塞全阻塞不能运用多处理技术不能运用多处理技术第56页，共102页，编辑于2022年，星期六3.4 3.4 线程线程用户级线程用户级线程第57页，共102页，编辑于202

33、2年，星期六内核级线程（在处理机上被调度和执行的对象）由内核实现线程管理克服了用户级线程的缺点线程切换需要到内核的模式切换3.4 3.4 线程线程第58页，共102页，编辑于2022年，星期六内核级线程内核级线程3.4 3.4 线程线程第59页，共102页，编辑于2022年，星期六3.4 3.4 线程线程第60页，共102页，编辑于2022年，星期六程序、进程、线程的比较程序、进程、线程的比较程序：程序：一组有序指令的集合一组有序指令的集合进程：进程：系统分配资源的基本单位系统分配资源的基本单位线程：线程：处理机调度的基本单位处理机调度的基本单位3.4 3.4 线程线程第61页，共102页，编

34、辑于2022年，星期六3.4 3.4 线程线程多线程编程优点：多线程编程优点：响应程度高响应程度高资源共享资源共享经济经济多处理器体系结构利用多处理器体系结构利用第62页，共102页，编辑于2022年，星期六第63页，共102页，编辑于2022年，星期六第64页，共102页，编辑于2022年，星期六3.5 3.5 处理器调度处理器调度请思考：我们是如何确定在任意时刻到请思考：我们是如何确定在任意时刻到底哪个进程执行，哪个不执行呢？底哪个进程执行，哪个不执行呢？进程管理的一个主要任务就是选择下一个要进程管理的一个主要任务就是选择下一个要运行的进程。运行的进程。第65页，共102页，编辑于2022

35、年，星期六要解决的问题要解决的问题WHAT:WHAT:按什么原则分配按什么原则分配CPUCPU-进程调度算法进程调度算法WHEN:WHEN:何时分配何时分配CPUCPU-进程调度时机进程调度时机HOWHOW：如何分配：如何分配CPUCPU-进程调度方式进程调度方式 3.5 3.5 处理器调度处理器调度第66页，共102页，编辑于2022年，星期六WHAT:WHAT:选择进程调度算法的标准选择进程调度算法的标准CPUCPU利用率利用率用户程序响应时间用户程序响应时间系统吞吐量系统吞吐量公平合理公平合理设备利用率设备利用率第67页，共102页，编辑于2022年，星期六WHEN:WHEN:进程调度时

36、机进程调度时机时间片过期时间片过期进程退出进程退出进程阻塞进程阻塞I/OI/O中断发生中断发生第68页，共102页，编辑于2022年，星期六HOW:HOW:进程调度方式进程调度方式 1.1.非抢占方式非抢占方式:简单，实时性差简单，实时性差 2.2.抢占方式抢占方式:（1 1）时间片原则）时间片原则（2 2）优先权原则）优先权原则（3 3）短作业优先原则。）短作业优先原则。第69页，共102页，编辑于2022年，星期六处理器调度的层次处理器调度的层次第70页，共102页，编辑于2022年，星期六（1 1）CPUCPU利用率利用率 CPUCPU利用率利用率=CPU=CPU有效工作时间有效工作时间

37、/CPU/CPU总运行总运行时间时间=CPU=CPU有效工作时间有效工作时间/(CPU/(CPU有效工作时间有效工作时间+CPU+CPU空闲等待时间空闲等待时间)（2 2）吞吐量（特别用于批处理）吞吐量（特别用于批处理）使得单位时间内处理的作业数尽可能多。使得单位时间内处理的作业数尽可能多。选择调度算法的原则(面向系统)第71页，共102页，编辑于2022年，星期六（3 3）周转时间）周转时间 从作业提交给系统开始，到作业完成为止的时间间隔称作作业周转时间。作业周转时间：作业周转时间：t ti i=t=tf f -t -ts s 实际上，实际上，t ti i 是作业在系统里等待时间和运行是作业

38、在系统里等待时间和运行时间之和。时间之和。平均作业周转时间平均作业周转时间:选择调度算法的原则(面向用户)第72页，共102页，编辑于2022年，星期六（4 4）响应时间）响应时间 交互式进程从提交一个请求到接收到响应之交互式进程从提交一个请求到接收到响应之间的时间间隔。间的时间间隔。（5 5）公平性）公平性 确保每个用户每个进程获得合理的CPU份额和其它资源份额，不会出现饿死的情况。选择调度算法的原则选择调度算法的原则(面向用户面向用户)第73页，共102页，编辑于2022年，星期六调度算法一调度算法一(FCFS)(FCFS)1 1、先来先服务、先来先服务(First-come,first-

39、served,FCFS)(First-come,first-served,FCFS)最先进入就绪进程首先分配到最先进入就绪进程首先分配到CPUCPU，FCFSFCFS策策略可用略可用FIFOFIFO队列实现队列实现 缺点：只顾及到等候时间，没有考虑要求服务时缺点：只顾及到等候时间，没有考虑要求服务时间长短。（不利于短作业）间长短。（不利于短作业）第74页，共102页，编辑于2022年，星期六例例:如下一组进程如下一组进程P1P1、P2P2、P3P3，到达系统的先后顺序分别如下面，到达系统的先后顺序分别如下面三图所示，计算各种顺序的平均周转时间三图所示，计算各种顺序的平均周转时间进程到达时间运行

40、时间P1028P219P323进程到达时间运行时间P209P1128P323进程到达时间运行时间P303P219P1228第75页，共102页，编辑于2022年，星期六P1P1P2P2P3P3T=(28+36+38)/3=T=(28+36+38)/3=3434P2P2P1P1P3P3T=(9+36+38)/3=T=(9+36+38)/3=27.627.6P3P3P2P2P1P1T=(3+11+38)/3=T=(3+11+38)/3=17.317.3可见，可见，FCFSFCFS算法的平均作业周转时间与作业算法的平均作业周转时间与作业提交及调度的顺序有关。提交及调度的顺序有关。第76页，共102页

41、，编辑于2022年，星期六调度算法二调度算法二(SJF)(SJF)2 2、短作业优先（、短作业优先（shortest-job-first,SJFshortest-job-first,SJF）以进入系统的作业所要求的以进入系统的作业所要求的CPUCPU时间长短为标准，时间长短为标准，总是选取估计计算时间最短的作业投入运行。总是选取估计计算时间最短的作业投入运行。第77页，共102页，编辑于2022年，星期六进程名到达时间运行时间P106P208P307P403采用采用SJFSJF调度：调度：P4P4P1P1P3P3P2P2T=13msT=13ms采用采用FCFSFCFS调度：调度：P1P1P2P

42、2P3P3P4P4T=16.25msT=16.25ms第78页，共102页，编辑于2022年，星期六SJFSJF缺点：缺点：难以精确估计作业所需难以精确估计作业所需CPUCPU时间，如程序员估时间，如程序员估计过低，系统可能提前终止该作业。计过低，系统可能提前终止该作业。忽视作业等待时间，由于系统不断接受新作业，而忽视作业等待时间，由于系统不断接受新作业，而调度算法又总选计算时间短的作业投入运行，因此，调度算法又总选计算时间短的作业投入运行，因此，使进入系统时间早但计算时间长的作业等待时间长，使进入系统时间早但计算时间长的作业等待时间长，会出现饥饿现象。会出现饥饿现象。第79页，共102页，编

43、辑于2022年，星期六可抢占式可抢占式SJFSJF算法算法(SRTF)(SRTF)当一个新作业到达就绪队列，如果新作业需当一个新作业到达就绪队列，如果新作业需要的要的CPUCPU时间短，则强行赶走当前作业，这种时间短，则强行赶走当前作业，这种算法也叫算法也叫最短剩余时间优先算法最短剩余时间优先算法（shortest shortest remaining time first,SRTFremaining time first,SRTF）。）。第80页，共102页，编辑于2022年，星期六进程名到达时间运行时间P108P214P329P435SRTF:SRTF:P1P1P2P2P4P4P1P1P3

44、P3T=13msT=13msSJF:SJF:P1P1P2P2P4P4P3P3T=14.25msT=14.25ms第81页，共102页，编辑于2022年，星期六调度算法三调度算法三(HRRF)(HRRF)3 3、高响应比优先调度（、高响应比优先调度（Highest Response Ratio Highest Response Ratio First,HRRF)First,HRRF)FCFSFCFS和和SJFSJF都是比较片面和调度算法，都是比较片面和调度算法，FCFSFCFS只只考虑作业等候时间而忽视了作业计算时间，考虑作业等候时间而忽视了作业计算时间，SJFSJF正好相反，本算法是一种折衷算

45、法，既考虑作正好相反，本算法是一种折衷算法，既考虑作业等待时间，又考虑作业运行时间，这样既照业等待时间，又考虑作业运行时间，这样既照顾了短作业又不使长作业等待时间过长，改进顾了短作业又不使长作业等待时间过长，改进了调度性能。了调度性能。第82页，共102页，编辑于2022年，星期六HRRFHRRF响应比响应比=响应时间响应时间/要求服务时间要求服务时间 =（等待时间（等待时间+运行时间）运行时间）/运行时间运行时间 =1+=1+等待时间等待时间/运行时间运行时间缺点：每次计算各道作业的响应比会有一定时缺点：每次计算各道作业的响应比会有一定时间开销，性能比间开销，性能比SJFSJF略差。略差。第

46、83页，共102页，编辑于2022年，星期六作业名到达时间运行时间P1020P2515P3105P41510SJF:SJF:P1P1P3P3P4P4P2P2T=25msT=25msFCFS:FCFS:P1P1P2P2P3P3P4P4T=28.75msT=28.75msHRRF:HRRF:P1P1P3P3P2P2P4P4T=26.25msT=26.25ms第84页，共102页，编辑于2022年，星期六调度算法四调度算法四 优先级调度算法优先级调度算法优优先先级级可可以以通通过过内内部部或或外外部部方方式式来来定定义义。内内部部优优先先级级使使用用一一些些可可测测量量数数据据以以计计算算进进程程优

47、优先先级级。外外部部优优先先级级是是通通过过操操作作系系统统之之外外的的准准则来设置的。则来设置的。优先级调度可以是优先级调度可以是可抢占的或者非抢占的可抢占的或者非抢占的。第85页，共102页，编辑于2022年，星期六静态优先级：创建进程时就确定，直到进程终止前都不改变。静态优先级：创建进程时就确定，直到进程终止前都不改变。通常是一个整数。依据：通常是一个整数。依据：进程类型（系统进程优先级较高）进程类型（系统进程优先级较高）对资源的需求（对对资源的需求（对CPUCPU和内存需求少的优先级较高）和内存需求少的优先级较高）用户要求（紧迫程度和付费多少）用户要求（紧迫程度和付费多少）动态优先级：

48、在创建进程时赋予优先级，在进程运行过程动态优先级：在创建进程时赋予优先级，在进程运行过程中可以自动改变，以后便获得更好的调度性能。如：中可以自动改变，以后便获得更好的调度性能。如：在就绪队列中等待时间延长则优先级提高，使优先级较低的进程在在就绪队列中等待时间延长则优先级提高，使优先级较低的进程在等待足够了的时间后，其优先级提高到可被调度执行。等待足够了的时间后，其优先级提高到可被调度执行。进程每执行一个时间片，就降低其优先级。进程每执行一个时间片，就降低其优先级。第86页，共102页，编辑于2022年，星期六进程名进程名 到达到达时间时间运行运行时间时间优先级优先级P10103P2011P30

49、24P4015P5052优先级调度算法优先级调度算法P2P2P5 P5 P1P1 P3P3 P4 P4T=12T=12第87页，共102页，编辑于2022年，星期六优先级调度算法优先级调度算法缺点：无穷阻塞（缺点：无穷阻塞（indefinite blockingindefinite blocking）或饥）或饥饿（饿（starvationstarvation）解决方案之一解决方案之一:老化老化在在19731973年关闭年关闭MITMIT的的IBM7094IBM7094时，发时，发现有一个低优先级进程是于现有一个低优先级进程是于19671967年年提交但是一直未运行提交但是一直未运行第88页，共

50、102页，编辑于2022年，星期六调度算法五调度算法五(RR)(RR)4 4、轮转法调度（、轮转法调度（Round-robin,RRRound-robin,RR）系统将所有的进程按先进先出的原则排成一个队系统将所有的进程按先进先出的原则排成一个队列，将新来的进程加到就绪队列的末尾，每当执行列，将新来的进程加到就绪队列的末尾，每当执行调度时，调度程序从就绪队列中选第一个进程，分调度时，调度程序从就绪队列中选第一个进程，分配一个时间片，将配一个时间片，将CPUCPU分配给进程，时间片一般为分配给进程，时间片一般为10ms100ms10ms100ms。第89页，共102页，编辑于2022年，星期六R