第八讲进程调度与线程概念课件.ppt

进程调度进程调度（CPUCPU调度）调度）要解决的问题要解决的问题WHATWHAT：按什么原则分配按什么原则分配CPUCPU 进程调度算法进程调度算法WHENWHEN：何时分配何时分配CPUCPU 进程调度的时机进程调度的时机HOWHOW：如何分配如何分配CPUCPU CPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）处理机调度分成三个层次处理机调度分成三个层次l处理机是计算机系统中的重要资源处理机是计算机系统中的重要资源l处理机调度算法对整个计算机系统的综处理机调度算法对整个计算机系统的综合性能指标有重要影响合性能指标有重要影响l可把处理机调度分成三个层次：可把处理机调度分成三个层次：高级调度 中级调度 低级调度高级调度高级调度也称为作业调度或宏观调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天高级调度的时间尺度通常是分钟、小时或天中中级级调调度度涉涉及及进进程程在在内内外外存存间间的的交交换换，从从存存储储器器资资源源管管理理的的角角度度来来看看，把把进进程程的的部部分分或或全全部部换换出出到到外外存存上上，可可为为当当前前运运行行进进程程的的执执行行提提供供所所需需内内存存空空间间，将将当当前前进进程程所所需需部部分分换换入入到到内内存存。指指令令和和数数据据必必须须在在内内存存里里才才能能被被处处理理机机直接访问直接访问低低级级调调度度也也称称微微观观调调度度，从从处处理理机机资资源源分分配配的的角角度度来来看看，处处理理机机需需要要经经常常选选择择就就绪绪进进程程或或线线程程进进入入运运行行状状态态，低低级级调调度度的的时时间间尺尺度度通通常常是是毫毫秒秒级级的的。由由于于低低级级调调度度算算法法的的频频繁繁使使用用，要求在实现时做到高效要求在实现时做到高效一一.进程调度算法进程调度算法 1 1进程调度进程调度 进进程程调调度度的的任任务务是是控控制制协协调调进进程程对对CPUCPU的的竞竞争争。即即按按一一定定的的调调度度算算法法从从就就绪绪队队列列中中选选中中一一个个进进程程，把把CPUCPU的的使使用用权权交交给给被被选选中的进程中的进程2 2确定算法的原则确定算法的原则具有公平性具有公平性资源利用率高（特别是资源利用率高（特别是CPUCPU利用率）利用率）在在交交互互式式系系统统情情况况下下要要追追求求响响应应时时间间（越越短越好）短越好）在批处理系统情况下要追求系统吞吐量在批处理系统情况下要追求系统吞吐量3 3各种进程调度算法各种进程调度算法先进先出进程调度算法先进先出进程调度算法（FIFOFIFO）按照进程就绪的先后次序来调度进程按照进程就绪的先后次序来调度进程 优点优点:实现简单实现简单 缺点缺点:没考虑进程的优先级没考虑进程的优先级 基于优先数的调度基于优先数的调度（HPFHighest Priority First）优优先先选选择择就就绪绪队队列列中中优优先先级级最最高高的的进进程程投投入运行入运行优先级根据优先数来决定优先级根据优先数来决定确定优先数的方法确定优先数的方法静态优先数法：静态优先数法：在在进进程程创创建建时时指指定定优优先先数数，在在进进程程运运行行时优先数不变时优先数不变动态优先数法：动态优先数法：在在进进程程创创建建时时创创立立一一个个优优先先数数，但但在在其其生生命命周周期期内内优优先先数数可可以以动动态态变变化化。如如等等待待时间长优先数可改变时间长优先数可改变两种占用两种占用CPUCPU的方式的方式可剥夺式（可抢占可剥夺式（可抢占式式PreemptivePreemptive）：）：当当有有比比正正在在运运行行的的进进程程优优先先级级更更高高的的进进程程就就绪绪时时，系系统统可可强强行行剥剥夺夺正正在在运运行行进进程程的的CPUCPU，提供给具有更高优先级的进程使用提供给具有更高优先级的进程使用不可剥夺式（不可抢占式不可剥夺式（不可抢占式 Non-preemptive Non-preemptive）：）：某某一一进进程程被被调调度度运运行行后后，除除非非由由于于它它自自身身的的原因不能运行，否则一直运行下去原因不能运行，否则一直运行下去时间片轮转程序调度算法时间片轮转程序调度算法(RRRound Robin)把把CPUCPU划划分分成成若若干干时时间间片片,并并且且按按顺顺序序赋赋给给就就绪绪队队列列中中的的每每一一个个进进程程，进进程程轮轮流流占占有有CPUCPU，当当时时间间片片用用完完时时，即即使使进进程程未未执执行行完完毕毕，系系统统也也剥剥夺夺该该进进程程的的CPUCPU，将将该该进进程程排排在在就就绪绪队队列列末末尾尾。同同时时系系统统选选择择另另一一个进程运行个进程运行分时系统中常用时间片轮转法分时系统中常用时间片轮转法时间片选择问题时间片选择问题：固定时间片固定时间片 可变时间片可变时间片与时间片大小有关的因素：与时间片大小有关的因素：系统响应时间系统响应时间 就绪进程个数就绪进程个数 CPUCPU能力能力 多队列反馈调度算法：多队列反馈调度算法：将将就就绪绪队队列列分分为为N N级级，每每个个就就绪绪队队列列分分配配给给不不同同的的时时间间片片，队队列列级级别别越越高高，时时间间越越长长，级级别别越越小小，时时间间片片越越小小，最最后后一一级级采采用用时时间间片片轮轮转转，其其他他队队列列采采用用先先进进先先出出；系系统统从从第第一一级级调调度度，当当第第一一级级为为空空时时，系系统统转转向向第第二二个个队队列列，.当当运运行行进进程程用用完完一一个个时时间间片片，放放弃弃CPUCPU时时，进进入入下下一一级级队队列列；等等待待进进程程被被唤唤醒醒时时，进进入入原原来来的的就就绪绪队队列列；当当进进程程第第一一次次就就绪绪时，进入第一级队列时，进入第一级队列 *首先系统中设置多个就绪队列首先系统中设置多个就绪队列*每每个个就就绪绪队队列列分分配配给给不不同同时时间间片片，优优先先级级高高的的为为第第一一级级队列，时间片最小，随着队列级别的降低，时间片加大队列，时间片最小，随着队列级别的降低，时间片加大*各个队列按照先进先出调度算法各个队列按照先进先出调度算法*一个新进程就绪后进入第一级队列一个新进程就绪后进入第一级队列*进进程程由由于于等等待待而而放放弃弃CPUCPU后后，进进入入等等待待队队列列，一一旦旦等等待待的的事件发生，则回到原来的就绪队列事件发生，则回到原来的就绪队列*当当有有一一个个优优先先级级更更高高的的进进程程就就绪绪时时，可可以以抢抢占占CPUCPU，被被抢抢占进程回到原来一级就绪队列末尾占进程回到原来一级就绪队列末尾*当第一级队列空时，就去调度第二级队列，如此类推当第一级队列空时，就去调度第二级队列，如此类推*当时间片到后，进程放弃当时间片到后，进程放弃CPUCPU，回到下一级队列回到下一级队列二二.进程调度的时机进程调度的时机当一个进程运行完毕，或由于某种错误而终止当一个进程运行完毕，或由于某种错误而终止运行运行当一个进程在运行中处于等待状态（等待当一个进程在运行中处于等待状态（等待I/OI/O）分时系统中时间片到分时系统中时间片到当有一个优先级更高的进程就绪（可抢占式）当有一个优先级更高的进程就绪（可抢占式）例例如如：新新创创建建一一个个进进程程，一一个个等等待待进进程程变变成成就就绪绪在在进进程程通通信信中中，执执行行中中的的进进程程执执行行了了某某种种原原语语操作（操作（P P操作，阻塞原语，唤醒原语）操作，阻塞原语，唤醒原语）三三.进程切换进程切换进程切换进程切换 一个进程让出处理器，由另一个进程占用处理器的过程一个进程让出处理器，由另一个进程占用处理器的过程进进程的切程的切换换使系使系统统中的各中的各进进程均有机会占用程均有机会占用CPUCPU进进程程的的切切换换是是由由进进程程状状态态的的变变化化引引起起的的，而而进进程程状状态态的的变变化又与出化又与出现现中断事件有关中断事件有关当当有有中中断断事事件件发发生生时时，当当前前运运行行的的进进程程被被中中断断，中中断断响响应应后后由由操操作作系系统统处处理理出出现现的的中中断断事事件件。中中断断处处理理后后，某某些些进进程程的的状状态态会会发发生生变变化化，也也可可能能又又创创建建了了一一些些新新的的进进程程。因因此此，要要进进行行队队列列的的调调整整。然然后后，进进程程调调度度根根据据预预定定的的调调度度算算法法从从就就绪绪队队列列选选一一个个进进程程占占用用CPUCPU。这这个个占占用用CPUCPU运运行行的的进进程程可可能能仍仍是是被被中中断断的的进进程程，也也可可能能是是另另一一个个进进程程 何时切换进程何时切换进程?只只要要OSOS取取得得对对CPUCPU的的控控制制，进进程程切切换换就就可可能发生，如能发生，如:超级用户调用超级用户调用来来自自程程序序的的显显式式请请求求 (如如：打打开开文文件件)，该该进进程程通常会被阻塞通常会被阻塞陷阱陷阱最最末末一一条条指指令令导导致致出出错错，会会引引起起进进程程移移至至退退出出状状态态中断中断 外外部部因因素素影影响响当当前前指指令令的的执执行行，控控制制被被转转移移至至IHIH（中断处理程序）中断处理程序）中断的例子中断的例子时钟时钟进程用完其时间片，被转换至就绪状态进程用完其时间片，被转换至就绪状态I/O I/O 先先前前等等待待该该事事件件的的进进程程被被转转换换为为就就绪绪(或或就就绪绪挂挂起起)状态状态然后重新运行该进程或选择一更高优先级的进程然后重新运行该进程或选择一更高优先级的进程存储器因素存储器因素内内存存地地址址是是在在虚虚拟拟存存储储器器中中，它它必必须须把把对对应应的的存存储块调入主存储块调入主存于是相应的进程成为阻塞状态于是相应的进程成为阻塞状态(等待等待I/OI/O完成完成)四四.CPU.CPU调度过程调度过程*保存现场保存现场：顺序保存，最后一步保存：顺序保存，最后一步保存PSWPSW*选择要运行的程序选择要运行的程序 （如如果果没没有有就就绪绪进进程程,系系统统会会安安排排一一个个闲闲逛逛进进程程(idle)(idle),没没有有其其他他进进程程时时该该进进程程一一直运行直运行,在执行过程中可接收中断）在执行过程中可接收中断）*恢复现场：恢复现场：最后一步恢复选中进程的最后一步恢复选中进程的PSWPSW在进程（上下文）中切换的步骤在进程（上下文）中切换的步骤保保存存处处理理器器的的上上下下文文，包包括括程程序序计计数数器器和和其其它它寄存器寄存器用用新新状状态态和和其其它它相相关关信信息息更更新新正正在在运运行行进进程程的的PCBPCB把原来的进程移至合适的队列把原来的进程移至合适的队列-就绪、阻塞就绪、阻塞选择另一个要执行的进程选择另一个要执行的进程更新被选中进程的更新被选中进程的PCBPCB从被选中进程中重装入从被选中进程中重装入 CPU CPU 上下文上下文二二.系统核心系统核心系统核心：系统核心：向上提供多个无中断的虚拟机器向上提供多个无中断的虚拟机器在核心内不允许中断在核心内不允许中断特点：特点：*为进程运行提供一个舞台为进程运行提供一个舞台 *核心常驻内存核心常驻内存 *设计短小精焊设计短小精焊1.1.核心的组成核心的组成 中断处理中断处理 进程管理进程管理:调度调度 控制控制 通讯通讯 互斥互斥 同步等同步等 原语管理原语管理:在在核核心心中中提提供供一一系系列列原原语语，同同步步,通通信，创建，撤消等信，创建，撤消等队列管理队列管理:队列数据结构队列数据结构:指向队首的表指针指向队首的表指针 三个队列三个队列:运行，就绪，等待队列运行，就绪，等待队列 排队方式排队方式:排队首排队首 排队尾排队尾 插插 队队 出队方式出队方式:队首出队队首出队/队中出队队中出队 队列管理队列管理:中断之后，进程调度之前中断之后，进程调度之前现场管理现场管理:保存现场保存现场;注意顺序注意顺序,中断之后第一步中断之后第一步 恢复现场恢复现场:恢复时机，进程调度最后一步恢复时机，进程调度最后一步 时钟管理时钟管理:以固定频率以固定频率 +1-1+1-1 用途用途:进入绝对时钟进入绝对时钟 间隔时钟间隔时钟 进行分析比较进行分析比较虚时钟虚时钟:每每个个进进程程分分配配给给一一个个虚虚时时钟钟来来记记录录CPUCPU时时间间,这个时钟称为虚时钟这个时钟称为虚时钟 虚虚时时钟钟存存放放在在PCBPCB中中，属属于于现现场场的的一一部部分分，进进程程运运行行时时，将将虚虚时时钟钟放放入入内内存存开开辟辟的的专专门单元，离开门单元，离开CPUCPU则放在则放在 PCBPCB中中2.2.核心处理流程核心处理流程进入核心的唯一入口进入核心的唯一入口:中断中断中断后进入核心，由硬件完成中断后进入核心，由硬件完成 3.3.内核的执行特点内核的执行特点由中断驱动的由中断驱动的:中断中断内核内核退出退出内核执行是连续的内核执行是连续的内核执行过程中在中断屏蔽状态下内核执行过程中在中断屏蔽状态下内核使用特权指令内核使用特权指令三三.线程的基本概念线程的基本概念线程的引入线程的引入线程与进程的对比线程与进程的对比线程的实现线程的实现实例：实例：SolarisSolaris1.1.线程的引入线程的引入进程的两个基本属性：进程的两个基本属性：资源的拥有者：资源的拥有者：给给每每个个进进程程分分配配一一虚虚拟拟地地址址空空间间，保保存存进进程程映映像像，控控制制一一些些资资源源（文文件件，I/OI/O设设备备），有状态、优先级、调度，有状态、优先级、调度调度单位：调度单位：进程是一个执行轨迹进程是一个执行轨迹 以上两个属性构成进程并发执行的基础以上两个属性构成进程并发执行的基础线程的引入（续线程的引入（续1 1）系统必须完成的操作：系统必须完成的操作：创建进程创建进程撤消进程撤消进程进程切换进程切换缺点：缺点：时间空间开销大，限制并发度的提高时间空间开销大，限制并发度的提高线程的引入（续线程的引入（续2 2）在在操操作作系系统统中中，进进程程的的引引入入提提高高了了计计算算机机资资源源的的利利用用效效率率。但但在在进进一一步步提提高高进进程程的的并并发发性性时时，人人们们发发现现进进程程切切换换开开销销占占的的比比重重越越来来越越大大，同同时时进进程程间间通通信信的的效效率率也也受受到限制到限制线线程程的的引引入入正正是是为为了了简简化化线线程程间间的的通通信信，以小的开销来提高进程内的并发程度以小的开销来提高进程内的并发程度线程的引入（续线程的引入（续3 3）线程：线程：有时称轻量级进程有时称轻量级进程 进程中的一个运行实体进程中的一个运行实体 是一个是一个CPUCPU调度单位调度单位 资源的拥有者还是进程或称任务资源的拥有者还是进程或称任务将原来进程的两个属性分开处理将原来进程的两个属性分开处理线程的引入（续线程的引入（续4 4）线程：线程：有执行状态（状态转换）有执行状态（状态转换）不运行时保存上下文不运行时保存上下文有一个执行栈有一个执行栈有一些局部变量的静态存储有一些局部变量的静态存储可存取所在进程的内存和其他资源可存取所在进程的内存和其他资源可以创建、撤消另一个线可以创建、撤消另一个线程程线程和进程：线程和进程：单进程、单线程单进程、单线程单进程、多线程单进程、多线程多进程、一个进程一个线程多进程、一个进程一个线程多进程、一个进程多个线程多进程、一个进程多个线程P C B用用户户栈栈单线程进程模型单线程进程模型用户地址空间用户地址空间核核心心栈栈线程控制块：线程控制块：包含了寄存器映像，线程优先数和线程状态信息包含了寄存器映像，线程优先数和线程状态信息P C B多线程进程模型多线程进程模型用户用户地址地址空间空间用用户户栈栈核核心心栈栈线程线程控制块控制块用用户户栈栈核核心心栈栈线程线程控制块控制块用用户户栈栈核核心心栈栈线程线程控制块控制块引入线程的好处：引入线程的好处：创建一个新线程花费时间少（结束亦如此）创建一个新线程花费时间少（结束亦如此）两个线程的切换花费时间少两个线程的切换花费时间少 （如如果果机机器器设设有有“存存储储 恢恢复复 所所有有寄寄存存器器”指指令令，则则整整个个切切换换过过程程用用几几条条指指令令即即可可完成）完成）因因为为同同一一进进程程内内的的线线程程共共享享内内存存和和文文件件，因此它们之间相互通信无须调用内核因此它们之间相互通信无须调用内核适合多处理机系统适合多处理机系统例子例子1 1：LANLAN中中的的一一个个文文件件服服务务器器，在在一一段段时时间间内内需需要处理几个文件请求要处理几个文件请求因因此此有有效效的的方方法法是是：为为每每一一个个请请求求创创建建一一个个线程线程在在一一个个SMPSMP机机器器上上：多多个个线线程程可可以以同同时时在在不不同的处理器上运行同的处理器上运行例子例子2 2：一个线程显示菜单，并读入用户输入；一个线程显示菜单，并读入用户输入；另一个线程执行用户命令另一个线程执行用户命令考考虑虑一一个个应应用用：由由几几个个独独立立部部分分组组成成，这这几几个个部部分分不不需需要要顺顺序序执执行行，则则每每个个部部分分可以以线程方式实现可以以线程方式实现当当一一个个线线程程因因I/OI/O阻阻塞塞时时，可可以以切切换换到到同同一一应用的另一个线程应用的另一个线程2.2.线程与进程的比较线程与进程的比较调度调度并发性并发性拥有资源拥有资源系统开销系统开销3.3.线程的实现机制线程的实现机制用户级线程用户级线程核心级线程核心级线程两者结合方法两者结合方法（1 1）用户级线程（）用户级线程（User Level ThreadUser Level Thread）由应用程序完成所有线程的管理由应用程序完成所有线程的管理 通过线程库通过线程库(用户空间用户空间)一组管理线程的过程一组管理线程的过程核心不知道线程的存在核心不知道线程的存在线程切换不需要核心态特权线程切换不需要核心态特权调度是应用特定的调度是应用特定的线程库线程库创建、撤消线程创建、撤消线程在线程之间传递消息和数据在线程之间传递消息和数据调度线程执行调度线程执行保护和恢复线程上下文保护和恢复线程上下文对用户级线程的核心活动对用户级线程的核心活动核核心心不不知知道道线线程程的的活活动动，但但仍仍然然管管理理线线程程的进程的活动的进程的活动当线程调用系统调用时，整个进程阻塞当线程调用系统调用时，整个进程阻塞但对线程库来说，线程仍然是运行状态但对线程库来说，线程仍然是运行状态 即线程状态是与进程状态独立的即线程状态是与进程状态独立的用户级线程的优点和缺点用户级线程的优点和缺点优点：优点：线程切换不调用核心线程切换不调用核心调度是应用程序特定的：可以选择最好的算法调度是应用程序特定的：可以选择最好的算法ULTULT可运行在任何操作系统上（只需要线程库）可运行在任何操作系统上（只需要线程库）缺点：缺点：大大多多数数系系统统调调用用是是阻阻塞塞的的，因因此此核核心心阻阻塞塞进进程程，故进程中所有线程将被阻塞故进程中所有线程将被阻塞核核心心只只将将处处理理器器分分配配给给进进程程，同同一一进进程程中中的的两两个个线程不能同时运行于两个处理器上线程不能同时运行于两个处理器上（2 2）核心级线程（）核心级线程（KLTKLT）所有线程管理由核心完成所有线程管理由核心完成没有线程库，但对核心线程工具提供没有线程库，但对核心线程工具提供APIAPI核心维护进程和线程的上下文核心维护进程和线程的上下文线程之间的切换需要核心支持线程之间的切换需要核心支持以线程为基础进行调度以线程为基础进行调度例子：例子：Windows NTWindows NT，OS/2OS/2核心级线程的优点和缺点核心级线程的优点和缺点优点：优点：对对多多处处理理器器，核核心心可可以以同同时时调调度度同同一一进进程程的多个线程的多个线程阻塞是在线程一级完成阻塞是在线程一级完成核心例程是多线程的核心例程是多线程的缺点：缺点：在在同同一一进进程程内内的的线线程程切切换换调调用用内内核核，导导致致速度下降速度下降（3 3）两者分析）两者分析针对不同的操作系统针对不同的操作系统开销和性能（开销和性能（线程的调度和切换速度线程的调度和切换速度线程的调度和切换速度线程的调度和切换速度）系统调用系统调用（阻塞阻塞阻塞阻塞）线程执行时间线程执行时间灵活性灵活性可扩充性可扩充性抢占抢占CPUCPU共享进程的资源共享进程的资源（4 4）ULTULT和和KLTKLT结合方法结合方法线程创建在用户空间完成线程创建在用户空间完成大量线程调度和同步在用户空间完成大量线程调度和同步在用户空间完成程序员可以调整程序员可以调整KLTKLT的数量的数量可以取两者中最好的可以取两者中最好的例子：例子：SolarisSolaris4.4.实例：实例：SolarisSolaris进程：进程：用户地址空间用户地址空间用户栈用户栈进程控制块进程控制块实例：实例：SolarisSolaris（续续1 1）用户级线程（线程库）用户级线程（线程库）：可在应用进程中建立多个可在应用进程中建立多个ULTULT 每个每个ULTULT需要：栈、程序计数器需要：栈、程序计数器 不受调度程序的调度，线程切换快不受调度程序的调度，线程切换快 对操作系统不可见对操作系统不可见 提供应用程序并行性接口提供应用程序并行性接口实例：实例：SolarisSolaris（续续2 2）核心级线程核心级线程：设置了大量设置了大量KLTKLT 有一个小的数据结构和栈有一个小的数据结构和栈 完成内核的所有工作完成内核的所有工作 调度处理器的单位，其结构由核心维护调度处理器的单位，其结构由核心维护实例：实例：SolarisSolaris（续续3 3）轻型进程（轻型进程（LWPLWP）：）：每个每个ULTULT利用利用LWPLWP与内核通信与内核通信 每每个个LWPLWP支支持持一一个个或或多多个个用用户户级级线线程程，并并映射到一个核心级线程映射到一个核心级线程 每每个个LWPLWP对对应应用用程程序序可可见见，内内核核看看到到的的是是多个多个LWPLWP而看不到而看不到ULTULTSolarisSolaris：如如果果逻逻辑辑并并行行性性不不需需要要硬硬件件并并行行性性的的支支持，则可使用持，则可使用ULTULT 例例子子：多多个个窗窗口口，任任一一时时刻刻只只有有一一个个窗窗口是活跃的口是活跃的 如如果果内内核核级级线线程程可可能能被被阻阻塞塞，则则可可以以指指定定两两个个或或多多个个LWPLWP，避避免免整整个个应应用用程程序序的的阻塞阻塞 分派分派唤醒唤醒继续继续抢占抢占停止停止可运行可运行睡眠睡眠睡眠睡眠停止停止停止停止停止停止用户级线程用户级线程活跃活跃连接在连接在LWP上上分派分派唤醒唤醒继续继续时间片时间片或抢占或抢占停止停止运行运行阻塞阻塞系统系统调用调用停止停止停止停止轻型进程状态轻型进程状态LWP状态独立于状态状态独立于状态ULT（受限制受限制ULT除外）除外）可运行可运行阻塞阻塞唤醒唤醒进程进程 1进程进程 2进程进程 3进程进程 4进程进程 5进程库进程库用户用户内核内核硬件硬件用户级线程用户级线程内核级线程内核级线程轻型线程轻型线程处理器处理器线程与进程的关系线程与进程的关系线程：进程线程：进程特点特点例子例子1:1每一执行的线程是每一执行的线程是有自己的地址空间有自己的地址空间和资源的唯一进程和资源的唯一进程.各种各种UNIX版本版本M:1进程定义了所拥有进程定义了所拥有的地址空间和动态的地址空间和动态资源。在该进程中资源。在该进程中多个线程可被创建多个线程可被创建和执行和执行.Windows NT,Solaris,OS/2,OS/390,MACH