第3章 处理器管理

L/O/G/O第三章第三章第三章第三章 处理器管理处理器管理处理器管理处理器管理mxh处理器管理的地位处理器管理的地位处理器管理的地位处理器管理的地位mxh主要内容主要内容主要内容主要内容3.1 3.1 进程的引入程的引入3.23.2进程的概念程的概念3.33.3进程控制程控制3.43.4线程程3.53.5处理器理器调度度3.63.6调度算法度算法3.73.7处理器理器调度和度和实时调度度mxh3.1.13.1.13.1.13.1.1程序的执行方式程序的执行方式程序的执行方式程序的执行方式(顺序顺序顺序顺序)顺序序执行行特征：特征：顺序性、封序性、封闭性、可再性、可再现性性I1C1P1I2C2P2mxh3.1.23.1.23.1.23.1.2程序的执行方式程序的执行方式程序的执行方式程序的执行方式(并发并发并发并发)并并发执行行I1I2I3I4C1C2C3C4P1P2P3P4tmxh3.1.13.1.13.1.13.1.1程序的执行方式程序的执行方式程序的执行方式程序的执行方式(并发并发并发并发)特征特征mxh与并发有关的错误与并发有关的错误与并发有关的错误与并发有关的错误mxh3.2 3.2 3.2 3.2 进程的概念进程的概念进程的概念进程的概念问题引入引入 程序程序这个静个静态概念已不能如概念已不能如实反映程序并反映程序并发执行行过程的特征。程的特征。为了深刻描述程序了深刻描述程序动态执行行过程的性程的性质，人，人们引入引入“进程程（ProcessProcess）”概念。概念。mxh3.2 3.2 3.2 3.2 进程的概念进程的概念进程的概念进程的概念程序在程序在处理机上理机上执行行时所所发生的活生的活动(Dijkstra)(Dijkstra)。是一个容器，是一个容器，该容器用以聚集相关容器用以聚集相关资源。源。（A.S.TanenbaumA.S.Tanenbaum）进程是一个具有独立功能的进程是一个具有独立功能的程序程序关于某关于某个个数据集合数据集合的的一次运行活动一次运行活动。是系统进。是系统进行资源分配和调度的单位。行资源分配和调度的单位。mxh3.2 3.2 3.2 3.2 进程的概念进程的概念进程的概念进程的概念操作操作级:图形窗口界面形窗口界面:一个窗口就是一个一个窗口就是一个进程程打开窗口：建立一个打开窗口：建立一个进程程关关闭窗口：一个窗口：一个进程程结束束字符命令界面字符命令界面:一条命令一般就是一个一条命令一般就是一个进程程命令行尾回命令行尾回车:一个一个进程开始程开始命令命令执行行结束束(下一命令提示符出下一命令提示符出现):):一个一个进程程结束束编程程级：进程建立：程建立：“建立建立进程程”函数或系函数或系统调用用进程程结束：束：“撤消撤消进程程”函数或系函数或系统调用，或者程序用，或者程序的正常或非正常的正常或非正常结束。束。mxh进程和程序的区别进程和程序的区别进程和程序的区别进程和程序的区别 程序静程序静态的，的，进程是程是动态的。的。程序和程序和进程的程的组成不同：成不同：进程程=程序程序+数据数据+PCB 程序的存在是永久的，程序的存在是程序的存在是永久的，程序的存在是暂时的。的。一个程序可以一个程序可以对应多个多个进程，一个程，一个进程可包含程可包含多个程序。多个程序。mxh进程的特征进程的特征进程的特征进程的特征动态性性：进程是个程是个动态的概念，有一定的生命周期，要的概念，有一定的生命周期，要经历创建、建、执行、撤行、撤销过程。程。结构性构性：它由：它由进程控制程控制块、程序段和数据段、程序段和数据段组成成。并并发性性：在一个系：在一个系统内可以同内可以同时存在多个存在多个进程，它程，它们通通过交替使用交替使用处理器，从而理器，从而实现并并发执行。行。异步性：异步性：指指进程之程之间在交替使用在交替使用计算机算机资源源时没有没有强制制的的顺序，按各自独立的、不可序，按各自独立的、不可预知的速度向前推知的速度向前推进。独立性：独立性：进程是系程是系统分配分配资源和源和进行行调度的独立度的独立单位。位。mxh3.2.2 3.2.2 3.2.2 3.2.2 进程的状态进程的状态进程的状态进程的状态 进程从程从创建而建而产生至撤生至撤销而消亡的整个生命周期，而消亡的整个生命周期，可用一可用一组状状态加以刻画，按加以刻画，按进程在程在执行行过程中的状程中的状况至少定况至少定义三种不同的三种不同的进程状程状态：a 运行运行态（RunningRunning）a 就就绪状状态（ReadyReady）a 阻塞状阻塞状态（BlockedBlocked）当前进程已经分配到当前进程已经分配到CPUCPU，它的程，它的程序正在处理机上执行的状态。序正在处理机上执行的状态。已具备运行条件，但因为其他进程已具备运行条件，但因为其他进程正在占用正在占用CPU,CPU,使它暂时不能运行而使它暂时不能运行而处于等待分配处于等待分配CPUCPU的状态。的状态。进程因等待某种事件发生（例如等待进程因等待某种事件发生（例如等待I/OI/O操作完成，等待其他进程发来的信操作完成，等待其他进程发来的信号）而暂时不能运行的状态，也就是说，号）而暂时不能运行的状态，也就是说，处于阻塞状态的进程尚不具备运行条件，处于阻塞状态的进程尚不具备运行条件，即使即使CPUCPU空闲它也无法使用。空闲它也无法使用。mxh3.2.2 3.2.2 3.2.2 3.2.2 进程的状态进程的状态进程的状态进程的状态引起引起进程状程状态转换原因原因就就绪-运行运行时间一到，一到，调度程序度程序选择一个新的一个新的进程运行程运行运行运行-就就绪运行运行进程用完了程用完了时间片；运行片；运行进程被中断，因程被中断，因为一一高高优先先级进程程处于就于就绪状状态mxh3.2.2 3.2.2 3.2.2 3.2.2 进程的状态进程的状态进程的状态进程的状态引起引起进程状程状态转换原因原因运行运行-阻塞阻塞当一当一进程所需的程所需的东西必西必须等待等待时对一一资源的源的访问尚不能尚不能进行行初始化初始化I/O I/O 且必且必须等待等待结果果等待某一等待某一进程提供程提供输入入阻塞阻塞-就就绪当所等待的事件当所等待的事件发生生时mxh3.2.2 3.2.2 3.2.2 3.2.2 进程的状态进程的状态进程的状态进程的状态进程三种状程三种状态的的转换mxh3.2.2 3.2.2 3.2.2 3.2.2 进程的状态进程的状态进程的状态进程的状态 有一个有一个计算机科学家，有一天女儿算机科学家，有一天女儿过生日，想生日，想亲手手给女儿做一个生日蛋糕。所以他就找了一本有关做蛋女儿做一个生日蛋糕。所以他就找了一本有关做蛋糕的食糕的食谱，买了一些原料，面粉、了一些原料，面粉、鸡蛋、糖、香料等，蛋、糖、香料等，然后然后边看看边学学边做。做。食食谱程序；科学家程序；科学家CPUCPU；原料数据；做蛋糕原料数据；做蛋糕进程；程；这时小儿子哭着跑小儿子哭着跑进来，来，说手被蜜蜂手被蜜蜂蛰了。教授只了。教授只好把蛋糕先放在一好把蛋糕先放在一边。他在食。他在食谱上做了个上做了个标记，把状，把状态信息信息记录了起来。然后又去找了一本医了起来。然后又去找了一本医疗手册，手册，查到了相关的内容，按照上面的指令一步步地到了相关的内容，按照上面的指令一步步地执行。当行。当伤口口处理完之后，又回到厨房理完之后，又回到厨房继续做蛋糕。做蛋糕。CPUCPU从一个从一个进程（做蛋糕）切程（做蛋糕）切换到另一个到另一个进程（医程（医疗救救护）。）。mxh3.2.2 3.2.2 3.2.2 3.2.2 进程的状态进程的状态进程的状态进程的状态五状态模型：新建态新建态就绪态：允许进入就绪态：允许进入运行态运行态完成态完成态：执行完：执行完mxh3.2.2 3.2.2 3.2.2 3.2.2 进程的状态进程的状态进程的状态进程的状态问题出出现进程挂起（程挂起（suspendsuspend）进程不断程不断创建，系建，系统资源已不源已不满足足进程程运行的要求，系运行的要求，系统就必就必须把某些把某些进程挂起，程挂起，即将即将进程程对换到磁到磁盘中，中，暂时不参与不参与进程程调度，已达到平衡操作系度，已达到平衡操作系统负荷的目的。荷的目的。引起引起进程挂起原因程挂起原因(P45-46(P45-46：(1)-(4)1)-(4)mxh挂起（挂起（Suspend):把一个把一个进程从内存程从内存转到外到外存。存。激活（激活（Activate）:把一个把一个进程从外存程从外存转到到内存。内存。mxh引入挂起状态后的七状态模型引入挂起状态后的七状态模型mxhLinuxLinuxLinuxLinux进程的状态进程的状态进程的状态进程的状态 D Uninterruptible sleep(usually IO)R Running or runnable(on run queue)S Interruptible sleep(waiting for an event to complete)T Stopped,either by a job control signal or because it is being traced.X dead(should never be seen)Z Defunct(zombie)process,terminated but not reaped by its parent.high-priority(not nice to other users)N low-priority(nice to other users)L has pages locked into memory(for real-time and custom IO)s is a session leaderl is multi-threaded(using CLONE_THREAD,like NPTL pthreads do)+is in the foreground process groupmxh例题例题例题例题 1 1如果系如果系统中有中有N N个个进程，运行的程，运行的进程最多几个，最少几个；就程最多几个，最少几个；就绪进程最程最多几个最少几个；等待多几个最少几个；等待进程最多几个，最少几个？程最多几个，最少几个？解答解答：在：在单处理机系理机系统中，中，处于运行状于运行状态的的进程最多程最多为1 1个，最少个，最少为0 0个；个；处于就于就绪进程最多程最多为N-1N-1个，最少个，最少为0 0个；个；处于阻塞的于阻塞的进程最多程最多为N N个，个，最少最少为0 0个。个。2.2.有没有有没有这样的状的状态转换，为什么？什么？（1 1）等待等待运行；运行；（2 2）就就绪等待等待mxh3.2.3 3.2.3 3.2.3 3.2.3 进程控制块进程控制块进程控制块进程控制块进程描述程描述进程控制程控制块程序和数据程序和数据组成了成了进程的程的实体（静体（静态文本）文本）需要一个数据需要一个数据结构来描述构来描述进程当前状程当前状态、本身、本身特性、特性、对资源的占用以及源的占用以及调度信息等，即度信息等，即进程程控制控制块（Process Control Block,PCBProcess Control Block,PCB）进程进程程序程序+数据数据+PCB+PCBmxh3.2.3 3.2.3 3.2.3 3.2.3 进程控制块进程控制块进程控制块进程控制块mxh3.2.3 3.2.3 3.2.3 3.2.3 进程控制块进程控制块进程控制块进程控制块PCBPCB是进程存在是进程存在的唯一标志；的唯一标志；PCBPCB常驻内存常驻内存pidpid进程状态进程状态现场现场优先级优先级阻塞原因阻塞原因程序地址程序地址同步机制同步机制资源清单资源清单链接指针链接指针mxhCPUCPUCPUCPU在进程之间的切换在进程之间的切换在进程之间的切换在进程之间的切换mxhPCBPCBPCBPCB的组织的组织的组织的组织链表：同一状表：同一状态的的进程其程其PCBPCB组成一成一链表，表，多个状多个状态对应多个不同的多个不同的链表。表。各状各状态的的进程形成不同的程形成不同的链表：就表：就绪链表、阻塞表、阻塞链表表mxh链链表表表表执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针1PCB90PCB89PCB77PCB6PCB58PCB40PCB33PCB24PCB1PCBPCBPCBPCB的组织的组织的组织的组织mxhPCBPCBPCBPCB的组织的组织的组织的组织索引表：同一状索引表：同一状态的的进程程归入一个入一个indexindex表表（由（由indexindex指向指向PCBPCB），多个状），多个状态对应多个不多个不同的同的indexindex表表各状各状态的的进行形成不同的索引表：就行形成不同的索引表：就绪索引表、阻塞索引表索引表、阻塞索引表mxh3.2.3 3.2.3 3.2.3 3.2.3 进程控制块进程控制块进程控制块进程控制块PCBPCB的的组织索引表索引表执行指针执行指针就绪表指针就绪表指针阻塞表指针阻塞表指针PCB7PCB6PCB5PCB4PCB3PCB2PCB1mxh补充补充补充补充PCBPCB和进程的代码数据放在一起吗？和进程的代码数据放在一起吗？系统态和用户态系统态和用户态系统空间和用户空间系统空间和用户空间mxh3.3 3.3 3.3 3.3 进程控制进程控制进程控制进程控制OS如何管理和控制如何管理和控制进程程必必须知道知道进程的位置程的位置（依（依赖于所使用的存于所使用的存储管管理方案）理方案）必必须知道知道进程的属性程的属性（PCB）必必须能能够创建、撤建、撤销进程程必必须能能够改改变进程的状程的状态mxhl 进程控制的职责：l 进程的创建l 进程的撤消l 进程的阻塞与唤醒l 进程控制是通过执行各种原语来实现的。3.3 3.3 3.3 3.3 进程控制进程控制进程控制进程控制mxh原原语是由若干条机器指令构成的、用于完是由若干条机器指令构成的、用于完成特定功能的一段程序。原成特定功能的一段程序。原语在在执行行过程程中是不可分割的。（中是不可分割的。（P47）3.3 3.3 3.3 3.3 进程控制进程控制进程控制进程控制mxh3.3.3 3.3.3 3.3.3 3.3.3 进程的创建进程的创建进程的创建进程的创建进程图进程图引起创建进程的事件引起创建进程的事件进程的创建过程进程的创建过程123mxh3.3.3 3.3.3 3.3.3 3.3.3 进程的创建进程的创建进程的创建进程的创建A AB BC CD DE EI IJ JF FHHL LMMKKGGA AB BC CD DE EI IJ JF FHHL LMMKKGGmxh入口入口查查PCBPCB链表链表有空有空PCBPCB取空表取空表PCB(i)PCB(i)填填PCB(i)PCB(i)相应项相应项PCB(i)PCB(i)入就绪队列入就绪队列PCB(i)PCB(i)入进程家族入进程家族返回返回创建失败创建失败YNmxh进程创建进程创建进程创建进程创建#include#include pid_t fork(void);功能：创建一个新的进程。返回值：在子进程中为0，在父进程中为子进程ID，出错为-1mxh进程创建进程创建进程创建进程创建该函数被调用一次，但返回两次。两次返回的区别是子进程的返回值是0，而父进程的返回值则是子进程的进程ID一般来说，在fork之后是父进程先执行还是子进程先执行是不确定的。这取决于内核所使用的调度算法。新创建的子进程是父进程的完全克隆完全克隆,会复制父进程的数据段、堆、栈空间（共享代码段）。mxh进程相关术语进程相关术语进程相关术语进程相关术语init 进程领养：当父进程在子进程结束前结束，子进程变成了孤儿进程，孤儿进程被init进程收养，子进程的父进程就变成了init进程。僵尸进程当子进程在父进程结束前结束，如果父进程没有释放子进程的资源(默认)，那么子进程就变成了一个僵尸进程。mxh进程创建进程创建进程创建进程创建mxh3.3.4 3.3.4 3.3.4 3.3.4 引起进程终止的事件引起进程终止的事件引起进程终止的事件引起进程终止的事件寿终：进程运行完自行退出寿终：进程运行完自行退出自杀：进程因错误而自行退出自杀：进程因错误而自行退出mxh3.3.2 3.3.2 3.3.2 3.3.2 引起进程终止的事件引起进程终止的事件引起进程终止的事件引起进程终止的事件他杀：进程被其它进程强行杀他杀：进程被其它进程强行杀死或由用户杀死死或由用户杀死处决：进程因异常而强行终结处决：进程因异常而强行终结mxh 检索相应的PCB，读其状态 若处于执行状态，则终止执行 若有子孙进程则终止子孙进程 释放终止进程的全部资源 将PCB从队列中移出3.3.4 进程的终止过程mxh入口查进程链表有此PCB释放该进程所占资源释放该PCB结构本身返回出错处理有子进程无有有无mxh3.3.3 3.3.3 3.3.3 3.3.3 进程的阻塞与唤醒进程的阻塞与唤醒进程的阻塞与唤醒进程的阻塞与唤醒1、引起进程阻塞的事件2、进程阻塞的过程3、进程唤醒的过程4、唤醒原语的执行过程mxh引起进引起进程阻塞程阻塞的事件的事件启动某种操作启动某种操作请求系统服务请求系统服务新数据尚未到达新数据尚未到达无新工作可做无新工作可做mxh 执行状态的进程调用阻塞原语 进程变为阻塞状态 PCB进入阻塞队列 转进程调度程序，进行切换进程阻塞的过程mxh被阻塞进程期待的事件发生。由发现者进程调用唤醒原语 唤醒阻塞进程。阻塞进程进入就绪状态。进程唤醒的过程mxh3.3 3.3 3.3 3.3 进程控制进程控制进程控制进程控制Linux进程控制原程控制原语:进程程创建建 fork进程程监控控 ps进程程终止止 killmxh3.4 3.4 3.4 3.4 线程线程线程线程线程的引入程的引入进程：程：资源分配源分配单位和位和CPU调度度单位位缺点：缺点：时间空空间开开销大，限制并大，限制并发度的提高度的提高将程序将程序块的的执行从行从进程中分离出来程中分离出来程序程序块执行需要行需要单独的：独的：执行状行状态：寄存器内容、：寄存器内容、栈、局部内存、局部内存程序程序块执行不需要行不需要单独的：独的：进程程资源：如文件、源：如文件、页表内容等表内容等多多线程：将一个程序分成多个并程：将一个程序分成多个并发的活的活动（程（程序序块）mxh3.4 3.4 3.4 3.4 线程线程线程线程进程程=线程程+资源集源集进程作程作为拥有有资源的基本源的基本单位，位，线程是系程是系统调度的基本度的基本单位。位。mxh3.4 3.4 3.4 3.4 线程线程线程线程进程和程和线程程资源所有源所有权（Process）调度的度的实体（体（Thread）mxh3.4 3.4 3.4 3.4 线程线程线程线程线程描述程描述线程状程状态（运行、就（运行、就绪、等待）、等待）一个一个执行行栈未运行未运行时保存的保存的线程上下文、静程上下文、静态存存储局部局部变量量对内存和其他内存和其他进程程资源的源的访问与与该进程中其他程中其他线程共享程共享资源源mxh3.4 3.4 3.4 3.4 线程线程线程线程用用户级线程程由由应用程序（用程序（线程程库）实现线程管理（程管理（POSIX Pthreads、Win32 threads）内核感内核感觉不到不到线程的存在程的存在优点点共享一个共享一个进程用程用户空空间中，中，线程管理不需要内核模式的程管理不需要内核模式的切切换可运行任何可运行任何OS上，内核无需修改。上，内核无需修改。缺点缺点全阻塞全阻塞不能运用多不能运用多处理技理技术mxh3.4 3.4 3.4 3.4 线程线程线程线程用户级线程用户级线程mxh内核级线程（在处理机上被调度和执行的对象）由内核实现线程管理克服了用户级线程的缺点线程切换需要到内核的模式切换3.4 3.4 3.4 3.4 线程线程线程线程mxh内核级线程内核级线程3.4 3.4 3.4 3.4 线程线程线程线程mxh3.4 3.4 3.4 3.4 线程线程线程线程mxh程序、程序、进程、程、线程的比程的比较程序：程序：一一组有序指令的集合有序指令的集合进程：程：系系统分配分配资源的基本源的基本单位位线程：程：处理机理机调度的基本度的基本单位位3.4 3.4 3.4 3.4 线程线程线程线程mxh3.4 3.4 3.4 3.4 线程线程线程线程多多线程程编程程优点：点：响响应程度高程度高资源共享源共享经济多多处理器体系理器体系结构利用构利用mxhmxhmxh3.5 3.5 3.5 3.5 处理器调度处理器调度处理器调度处理器调度请思考：我思考：我们是如何确定在任意是如何确定在任意时刻到刻到底哪个底哪个进程程执行，哪个不行，哪个不执行呢？行呢？进程管理的一个主要任程管理的一个主要任务就是就是选择下一下一个要运行的个要运行的进程。程。mxh要解决的要解决的问题WHAT:按什么原按什么原则分配分配CPU-进程程调度算法度算法WHEN:何何时分配分配CPU-进程程调度度时机机HOW：如何分配：如何分配CPU-进程程调度方式度方式 3.5 3.5 3.5 3.5 处理器调度处理器调度处理器调度处理器调度mxhWHAT:WHAT:WHAT:WHAT:选择进程调度算法的标准选择进程调度算法的标准选择进程调度算法的标准选择进程调度算法的标准CPUCPU利用率利用率用用户程序响程序响应时间系系统吞吐量吞吐量公平合理公平合理设备利用率利用率mxhWHEN:WHEN:WHEN:WHEN:进程调度时机进程调度时机进程调度时机进程调度时机时间片片过期期进程退出程退出进程阻塞程阻塞I/O中断中断发生生mxhHOW:HOW:HOW:HOW:进程调度方式进程调度方式进程调度方式进程调度方式 1.1.非抢占方式非抢占方式:简单，实时性差简单，实时性差 2.2.抢占方式抢占方式:（1 1）时间片原则）时间片原则（2 2）优先权原则）优先权原则（3 3）短作业优先原则。）短作业优先原则。mxh处理器调度的层次处理器调度的层次处理器调度的层次处理器调度的层次mxh（1 1）CPUCPU利用率利用率 CPUCPU利用率利用率=CPU=CPU有效工作有效工作时间/CPU/CPU总运行运行时间=CPU=CPU有效工作有效工作时间/(CPU/(CPU有效工作有效工作时间+CPU+CPU空空闲等待等待时间)（2 2）吞吐量（特）吞吐量（特别用于批用于批处理）理）使得使得单位位时间内内处理的作理的作业数尽可能多。数尽可能多。选择调度算法的原则(面向系统)mxh（3）周转时间）周转时间从作业提交给系统开始，到作业完成为止的时间间隔称作作业周转时间。作业周转时间：作业周转时间：ti=tf -ts 实际上，实际上，ti 是作业在系统里等待时间和运行是作业在系统里等待时间和运行时间之和。时间之和。平均作业周转时间平均作业周转时间:选择调度算法的原则(面向用户)mxh（4）响应时间）响应时间交互式进程从提交一个请求到接收到响交互式进程从提交一个请求到接收到响应之间的时间间隔。应之间的时间间隔。（5）公平性）公平性确保每个用户每个进程获得合理的CPU份额和其它资源份额，不会出现饿死的情况。选择调度算法的原则选择调度算法的原则(面向用户面向用户)mxh调度算法一调度算法一调度算法一调度算法一(FCFS)(FCFS)(FCFS)(FCFS)1 1、先来先服、先来先服务(First-come,first-served,FCFS)(First-come,first-served,FCFS)最先最先进入就入就绪进程首先分配到程首先分配到CPUCPU，FCFSFCFS策略可用策略可用FIFOFIFO队列列实现 缺点：只缺点：只顾及到等候及到等候时间，没有考，没有考虑要求服要求服务时间长短。（不利于短作短。（不利于短作业）mxh例例例例:如下一组进程如下一组进程如下一组进程如下一组进程P1P1P1P1、P2P2P2P2、P3P3P3P3，到达系统的先后顺序分别如下，到达系统的先后顺序分别如下，到达系统的先后顺序分别如下，到达系统的先后顺序分别如下面三图所示，计算各种顺序的平均周转时间面三图所示，计算各种顺序的平均周转时间面三图所示，计算各种顺序的平均周转时间面三图所示，计算各种顺序的平均周转时间进程到达时间运行时间P1028P219P323进程到达时间运行时间P209P1128P323进程到达时间运行时间P303P219P1228mxhP1P1P2P2P3P3T=(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算法的平均作算法的平均作业周周转时间与作与作业提交及提交及调度的度的顺序有关。序有关。mxh调度算法二调度算法二调度算法二调度算法二(SJF)(SJF)(SJF)(SJF)2 2、短作、短作业优先（先（shortest-job-first,SJFshortest-job-first,SJF）以以进入系入系统的作的作业所要求的所要求的CPUCPU时间长短短为标准，准，总是是选取估取估计计算算时间最短的作最短的作业投投入运行。入运行。mxh进程名到达时间运行时间P106P208P307P403采用采用SJFSJF调度：调度：P4P4P1P1P3P3P2P2T=13msT=13ms采用采用FCFSFCFS调度：调度：P1P1P2P2P3P3P4P4T=16.25msT=16.25msmxhSJFSJFSJFSJF缺点：缺点：难以精确估以精确估计作作业所需所需CPUCPU时间，如程序，如程序员估估计过低，系低，系统可能提前可能提前终止止该作作业。忽忽视作作业等待等待时间，由于系，由于系统不断接受新作不断接受新作业，而，而调度算法又度算法又总选计算算时间短的作短的作业投投入运行，因此，使入运行，因此，使进入系入系统时间早但早但计算算时间长的作的作业等待等待时间长，会出，会出现饥饿现象。象。mxh可抢占式可抢占式可抢占式可抢占式SJFSJFSJFSJF算法算法算法算法(SRTF)(SRTF)(SRTF)(SRTF)当一个新作当一个新作业到达就到达就绪队列，如果新作列，如果新作业需需要的要的CPUCPU时间短，短，则强行赶走当前作行赶走当前作业，这种算法也叫种算法也叫最短剩余最短剩余时间优先算法先算法（shortest remaining time first,SRTFshortest remaining time first,SRTF）。）。mxh进程名到达时间运行时间P108P214P329P435SRTF:SRTF:P1P1P2P2P4P4P1P1P3P3T=13msT=13msSJF:SJF:P1P1P2P2P4P4P3P3T=14.25msT=14.25msmxh调度算法三调度算法三调度算法三调度算法三(HRRF)(HRRF)(HRRF)(HRRF)3 3、高响、高响应比比优先先调度（度（Highest Response Ratio Highest Response Ratio First,HRRF)First,HRRF)FCFSFCFS和和SJFSJF都是比都是比较片面和片面和调度算法，度算法，FCFSFCFS只考只考虑作作业等候等候时间而忽而忽视了作了作业计算算时间，SJFSJF正好相反，本算法是一种折衷算法，正好相反，本算法是一种折衷算法，既考既考虑作作业等待等待时间，又考，又考虑作作业运行运行时间，这样既照既照顾了短作了短作业又不使又不使长作作业等待等待时间过长，改，改进了了调度性能。度性能。mxhHRRFHRRFHRRFHRRF响响应比比=响响应时间/要求服要求服务时间 =（等待（等待时间+运行运行时间）/运行运行时间 =1+=1+等待等待时间/运行运行时间缺点：每次缺点：每次计算各道作算各道作业的响的响应比会有一比会有一定定时间开开销，性能比，性能比SJFSJF略差。略差。mxh作业名到达时间运行时间P1020P2515P3105P41510SJF:SJF:P1P1P3P3P4P4P2P2T=25msT=25msFCFS:FCFS:P1P1P2P2P3P3P4P4T=28.75msT=28.75msHRRF:HRRF:P1P1P3P3P2P2P4P4T=26.25msT=26.25msmxh调度算法四调度算法四调度算法四调度算法四 优先级调度算法优先级调度算法优先级调度算法优先级调度算法优优先先级级可可以以通通过过内内部部或或外外部部方方式式来来定定义义。内内部部优优先先级级使使用用一一些些可可测测量量数数据据以以计计算算进进程程优优先先级级。外外部部优优先先级级是是通通过操作系统之外的准则来设置的。过操作系统之外的准则来设置的。优优先先级级调调度度可可以以是是可可抢抢占占的的或或者者非非抢抢占的占的。mxh静态优先级：创建进程时就确定，直到进程终止前都不静态优先级：创建进程时就确定，直到进程终止前都不改变。通常是一个整数。依据：改变。通常是一个整数。依据：进程类型（系统进程优先级较高）进程类型（系统进程优先级较高）对资源的需求（对对资源的需求（对CPUCPU和内存需求少的优先级较高）和内存需求少的优先级较高）用户要求（紧迫程度和付费多少）用户要求（紧迫程度和付费多少）动态优先级：在创建进程时赋予优先级，在进程运行过动态优先级：在创建进程时赋予优先级，在进程运行过程中可以自动改变，以后便获得更好的调度性能。如：程中可以自动改变，以后便获得更好的调度性能。如：在就绪队列中等待时间延长则优先级提高，使优先级较低的进程在就绪队列中等待时间延长则优先级提高，使优先级较低的进程在等待足够了的时间后，其优先级提高到可被调度执行。在等待足够了的时间后，其优先级提高到可被调度执行。进程每执行一个时间片，就降低其优先级。进程每执行一个时间片，就降低其优先级。mxh进程名进程名 到达到达时间时间运行运行时间时间优先级优先级P1P10 010103 3P2P20 01 11 1P3P30 02 24 4P4P40 01 15 5P5P50 05 52 2优先级调度算法优先级调度算法P2P2P5 P5 P1P1 P3P3 P4 P4T=12T=12mxh优先级调度算法优先级调度算法优先级调度算法优先级调度算法缺点：无缺点：无穷阻塞（阻塞（indefinite blockingindefinite blocking）或或饥饿（starvationstarvation）解决方案之一解决方案之一:老化老化在在19731973年关闭年关闭MITMIT的的IBM7094IBM7094时，发时，发现有一个低优先级进程是于现有一个低优先级进程是于19671967年年提交但是一直未运行提交但是一直未运行mxh调度算法五调度算法五调度算法五调度算法五(RR)(RR)(RR)(RR)4 4、轮转法法调度（度（Round-robin,RRRound-robin,RR）系系统将所有的将所有的进程按先程按先进先出的原先出的原则排成一排成一个个队列，将新来的列，将新来的进程加到就程加到就绪队列的末尾，列的末尾，每当每当执行行调度度时，调度程序从就度程序从就绪队列中列中选第一个第一个进程，分配一个程，分配一个时间片，将片，将CPUCPU分配分配给进程，程，时间片一般片一般为10ms10ms100ms100ms。mxhRRRRRRRR进程需要程需要CPUCPU的的时间小于小于一个一个时间片的片的时间：进程本身会程本身会释放放CPUCPU，进程程调度程序接着度程序接着处理就理就绪队列的下一个列的下一个进程。程。进程所需程所需CPUCPU的的时间大于大于一个一个时间片的片的时间：定定时器会切断当前器会切断当前进程，程，进行上下文切行上下文切换，该进程被加到程被加到队列尾部，接着列尾部，接着进程程调度程序度程序选择就就绪队列中的下一下列中的下一下进程。程。mxh进程名到达时间运行时间P1024P203P303RRRR(注：时间片为注：时间片为4ms)4ms)P1P1P2P2P3P3P1P1P1P1P1P1P1P1P1P1T=15.67msT=15.67msmxhRRRRRRRR如果如果时间片太小片太小，以至于大多数，以至于大多数进程都不可程都不可能在一个能在一个时间片内运行完片内运行完毕，切，切换就会就会频繁，繁，系系统开开销显著增大，所以，从系著增大，所以，从系统效率来看，效率来看，时间片取大一点好。片取大一点好。如果如果时间片片较大大，那么，随着就，那么，随着就绪队列里列里进程数目的增加，程数目的增加，轮转一次的一次的总时间增大，亦增大，亦即即对每个每个进程的响程的响应速度放慢了。速度放慢了。所以，所以，时间片大小的确定要从片大小的确定要从进程个数，切程个数，切换开开销，系，系统效率和响效率和响应时间等多方面考等多方面考虑。mxh 例题：假如例题：假如5 5个就绪进程其到达系统和所需个就绪进程其到达系统和所需CPUCPU时间如下表所示时间如下表所示（单位：毫秒），如果忽略（单位：毫秒），如果忽略I/OI/O以及其他开销分别计算采用以及其他开销分别计算采用FCFSFCFS、非抢占式、非抢占式SJFSJF、抢占式、抢占式SJFSJF、HRRFHRRF调度算法进行调度算法进行CPUCPU调度调度的平均周转时间。的平均周转时间。进程到达和运行时间进程到达和运行时间进程进程到达时间到达时间运行时间运行时间A A0 03 3B B2 26 6C C4 44 4D D6 65 5E E8 82 2mxh 解答如下：解答如下：（1 1）采用）采用FCFSFCFS的调度顺序为：的调度顺序为：A AB BC CD DE E0 03 39 9131318182020平均周转时间为：平均周转时间为：T=(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6T=(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6带权平均周转时间为：带权平均周转时间为：W=2.56W=2.56mxh （2 2）采用非抢占）采用非抢占SJFSJF的调度顺序为：的调度顺序为：A AB BE EC CD D0 03 39 9111115152020平均周转时间为：平均周转时间为：T=7.6T=7.6带权平均周转时间为：带权平均周转时间为：W=1.84W=1.84mxh （3 3）采用抢占）采用抢占SJFSJF的调度顺序为：的调度顺序为：平均周转时间为：平均周转时间为：T=7.2T=7.2带权平均周转时间为：带权平均周转时间为：W=1.59W=1.59A AB1B1E EC CB2B20 03 38 8101015152020D D4 4mxh解答：解答：（4）HRRF算法：算法：在时刻在时刻0时进程时进程A就绪，此时，就绪，此时，CPU空闲，故空闲，故A运行，运行，到了时刻到了时刻2时进程时进程B就绪，进程就绪，进程A结束后，进程结束后，进程B进入运行，进入运行，接着进程接着进程C、D、E先后到达，进入就绪状态。进程先后到达，进入就绪状态。进程B运行结运行结束后，调度程序要从束后，调度程序要从C、D和和E中选择一个投入运行，为此，中选择一个投入运行，为此，计算它们的响应比：计算它们的响应比：RRc=9/4=2.25 RRd=8/5=1.60 RRe=3/2=1.50 因此，因此，C进程被选择投入运行。进程运行进程被选择投入运行。进程运行4个单位后结束个单位后结束mxh 进程进程C运行运行4个单位后结束，调度程序需要从个单位后结束，调度程序需要从D和和E进程挑进程挑选一个运行，为此，计算它们的响应比：选一个运行，为此，计算它们的响应比：RRd=12/5=2.40 RRe=7/2=3.5 因此，选择因此，选择E投入运行。综上所述，进程的调度顺序为：投入运行。综上所述，进程的调度顺序为：平均周转时间为：平均周转时间为：T=8.0 平均带权周转时间：平均带权周转时间：W=2.14A AB BC CE ED D0 03 39 9131315152020mxh调度算法六调度算法六调度算法六调度算法六(多级队列调度多级队列调度多级队列调度多级队列调度)mxh调度算法七调度算法七调度算法七调度算法七(多级反馈队列调度多级反馈队列调度多级反馈队列调度多级反馈队列调度)mxh调度算法七调度算法七调度算法七调度算法七(多级反馈队列调度多级反馈队列调度多级反馈队列调度多级反馈队列调度)特点：长、短作业兼顾，有较好的响特点：长、短作业兼顾，有较好的响 应时间应时间（1 1）短作业一次完成；）短作业一次完成；（2 2）中型作业周转时间不长；）中型作业周转时间不长；（3 3）大型作业不会长期不处理。）大型作业不会长期不处理。mxh重点概念和内容提示重点概念和内容提示重点概念和内容提示重点概念和内容提示常用进程调度算法常用进程调度算法进程的概念、进程与程序的区别进程的概念、进程与程序的区别进程的结构、状态及转换进程的结构、状态及转换