操作系统处理器管理整理ppt.ppt

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

1、操作系统处理器管理整理ppt Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望主要内容什么是处理器管理？处理器的相关知识中断技术进程与线程处理器调度作业管理与调度低级调度什么是处理器管理？处理器管理是操作系统的重要组成部分，负责管理、调度和分派计算机系统的重要资源处理器，并控制程序执行。涉及两方面内容处理器处理器运行的程序（进程）运行的程序（进程）处理器的相关知识处理器寄存器机器指令处理器状态程序状态字(PSW,Program Status Word)处理器内部组成

2、：控制器控制器运算器运算器寄存器寄存器中断装置中断装置输入输入/输出电路输出电路高速缓存高速缓存(Cache)(Cache)寄存器通用寄存器通用寄存器数据寄存器数据寄存器地址寄存器地址寄存器I/OI/O地址寄存器地址寄存器I/OI/O缓冲寄存器缓冲寄存器控制寄存器控制寄存器 程序计数器程序计数器 指令寄存器指令寄存器 中断寄存器中断寄存器 内存和内存和I/OI/O控制寄存器控制寄存器机器指令指令是指示计算机执行某些操作的命令，一台计算机的所指令是指示计算机执行某些操作的命令，一台计算机的所有指令的集合，称为指令系统，反映机器的功能和能力有指令的集合，称为指令系统，反映机器的功能和能力指令系统可

3、分为：指令系统可分为：复杂指令系统复杂指令系统(CISC)(CISC)、精简指令系统、精简指令系统(RISC)(RISC)指令分类指令分类 按功能分：按功能分：运算（算术运算、逻辑运算、移位运算）运算（算术运算、逻辑运算、移位运算）程序控制（转移、子程序调用、返回）程序控制（转移、子程序调用、返回）数据传送（一般传送、堆栈操作、数据交换）数据传送（一般传送、堆栈操作、数据交换）输入输入/输出指令输出指令 按使用者分：按使用者分：特权指令，仅供操作系统内核调用特权指令，仅供操作系统内核调用非特权指令非特权指令处理器状态特权指令的执行限制，使处理器必须能区分当前特权指令的执行限制，使处理器必须能区

4、分当前运行的程序是操作系统还是普通应用程序运行的程序是操作系统还是普通应用程序处理器状态：处理器状态：管理状态（特权状态、系统状态、特态、管态），能管理状态（特权状态、系统状态、特态、管态），能执行所有机器指令执行所有机器指令 用户状态（目标状态、用户模式、常态、目态），只用户状态（目标状态、用户模式、常态、目态），只能执行非特权指令能执行非特权指令中断导致状态转换中断导致状态转换 程序请求操作系统服务程序请求操作系统服务 产生中断事件产生中断事件程序状态字(PSW)用于区别不同的处理器工作状态每个程序都有一个与其执行相关的PSW，而每个处理器均设置一组相关寄存器用于存储PSW信息PSW的主要

5、内容程序基本状态（程序计数器、条件码、状态位）程序基本状态（程序计数器、条件码、状态位）中断码中断码中断屏蔽位中断屏蔽位中断技术什么是中断？中断源分类中断装置中断处理程序中断的优先级和多重中断什么是中断？中断是用来向CPU报告某设备已完成某项操作的手段，是并发程序的基础。中断是指程序执行过程中，当发生某个事件时，？终止CPU上现行程序的运行，引出处理该事件的服务程序执行的过程。中断事件处理需要硬件（中断装置）和软件（中断处理程序）配合完成。中断源分类中断源：引起中断的事件引起中断的事件按中断事件的性质和激活的手段分：强迫性中断事件强迫性中断事件机器故障、程序性错误（异常）、外部中断、输入机器故

6、障、程序性错误（异常）、外部中断、输入输出中断事件、输出中断事件、自愿性中断事件自愿性中断事件调用访管指令调用访管指令中断源分类内外的划分标准：处理器和主存为内，其他硬件为外处理器和主存为内，其他硬件为外按中断信号的来源分：外中断（中断）外中断（中断）电源故障中断、电源故障中断、时钟中断（外部）时钟中断（外部）、控制台中断、控制台中断、输入输出中断、输入输出中断、内中断（异常）内中断（异常）通路校验错、主存奇偶校验错、非法操作码、地址通路校验错、主存奇偶校验错、非法操作码、地址越界、页面失效、调试指令、访管中断、算术操作越界、页面失效、调试指令、访管中断、算术操作溢出、溢出、中断与异常的区别中

7、断特点：中断特点：与现行指令无关与现行指令无关 发生时间与发生时间与CPUCPU所处状态无关所处状态无关 两条指令之间才能响应中断两条指令之间才能响应中断 可被屏蔽可被屏蔽 可嵌套可嵌套异常特点：异常特点：由现行指令执行而引起由现行指令执行而引起 在目态发生在目态发生 可在一个指令周期内处理可在一个指令周期内处理 不可屏蔽、不可嵌套不可屏蔽、不可嵌套 可细分为：可细分为：出错，处理完后回到当前出错指令出错，处理完后回到当前出错指令陷入，处理完后执行下一条指令（常用于系统功能调用）陷入，处理完后执行下一条指令（常用于系统功能调用）中断装置定义：发现中断源并产生中断的硬件，通常包括逻辑发现中断源并

8、产生中断的硬件，通常包括逻辑电路和中断寄存器电路和中断寄存器具体功能：捕获中断源，响应中断请求捕获中断源，响应中断请求保护现场保护现场启动处理中断事件的中断处理程序，启动处理中断事件的中断处理程序，CPUCPU从目从目态切换为管态态切换为管态32位处理器的PC机通常的中断硬件结构系统数据总线CPUINTINTA主中断控制器主中断控制器IRQ0 时钟键盘tty2tty1IRQ8实时时钟中断装置工作过程演示0000中断寄存器中断寄存器中断装置中断装置中断源中断源1写写中断控制部件中断控制部件读读内存内存PSW寄存器寄存器控制控制1#中断向量中断向量现行现行PSW中断处理程序处理中断事件的程序具体功

9、能：保护一些未被硬件保护的现场信息保护一些未被硬件保护的现场信息识别中断源，分析中断产生的原因识别中断源，分析中断产生的原因处理发生的中断事件处理发生的中断事件恢复正常操作恢复正常操作实现方法：向量地址是中断服务程序的入口向量地址是中断服务程序的入口中断向量表中断向量表0130#入口地址1#入口地址3#入口地址处理程序段中断事件处理中断和异常的一般处理过程中断和异常的一般处理过程硬件故障中断硬件故障中断程序性中断（程序性中断（浮点溢出、非法指令浮点溢出、非法指令）输入输出中断输入输出中断 I/OI/O操作正常结束操作正常结束 I/OI/O操作发生故障操作发生故障 I/OI/O操作发生异常操作发

10、生异常 设备报道或设备结束设备报道或设备结束访管中断访管中断时钟中断时钟中断中断的优先级优先级同时有多个中断事件发生时，中断装置按一定同时有多个中断事件发生时，中断装置按一定顺序对其作出响应，其先后顺序即优先级顺序对其作出响应，其先后顺序即优先级优先级设定的原则优先级设定的原则按造成计算机系统出错的严重程度划分按造成计算机系统出错的严重程度划分例，机器校验中断例，机器校验中断 自愿性中断自愿性中断 程序性中断程序性中断 外部中断外部中断 输入输出中断输入输出中断 重启动中断重启动中断 中断的优先级和多重中断中断优先级的设计导致：中断屏蔽中断屏蔽高优先级的中断响应过程中，应屏蔽低优先级的中高优先

11、级的中断响应过程中，应屏蔽低优先级的中断断有些中断是不能被屏蔽的，如自愿访管中断有些中断是不能被屏蔽的，如自愿访管中断多重中断事件的处理 中断处理过程中，又产生了新的中断事件串行处理串行处理中断处理过程中关中断中断处理过程中关中断嵌套处理嵌套处理开中断，暂停当前执行的中断处理程序，转而执行开中断，暂停当前执行的中断处理程序，转而执行更高优先级的中断处理程序更高优先级的中断处理程序即时处理即时处理主要针对中断处理程序执行过程中发生的程序性中主要针对中断处理程序执行过程中发生的程序性中断断Linux中断处理中断 自陷慢中断快中断 进程正在运行 用户态 核心态 上半部分处理 返回原进 程运行 排队下

12、半部分 快中断处理 系统调用处理 从系统调用返回 ret_from_sys_call 调用schedule()调度新进程运行运行 用户态 调度下半部分do_bottom_half()/do_softirq()处理积累的信号 do_signal()restore_all中断快中断与慢中断区别慢中断处理前需要保存所有寄存器的值，而快中断仅需保存会被内核使用的寄存器的值慢中断处理时，不关中断，快中断处理时，关中断慢中断处理完成后，通常不立即返回被中断进程，而是转而执行调度程序。快中断处理完成后，通常返回被中断进程继续执行Minix中断处理类似于linux的低半处理方式目的目的:为了缩短屏蔽中断的时间

13、为了缩短屏蔽中断的时间,提高系统并发工提高系统并发工作的能力作的能力一种任务延迟处理机制一种任务延迟处理机制,核心代码在关中断的核核心代码在关中断的核心态完成与中断事件有关的基本处理心态完成与中断事件有关的基本处理,另外一部另外一部分耗时的工作留在中断处理例程之外分耗时的工作留在中断处理例程之外,在开中断在开中断的非核心态完成。的非核心态完成。这些非核心态运行的代码，在这些非核心态运行的代码，在MinixMinix中被组织成中被组织成与设备基本相对应的任务（驱动程序）进程，如与设备基本相对应的任务（驱动程序）进程，如磁盘任务、终端任务、时钟任务等等磁盘任务、终端任务、时钟任务等等,其中中断其中

14、中断任务需要对应如键盘任务需要对应如键盘,RS232,RS232串口等硬件串口等硬件.信号机制一种模拟硬件中断的简单通信机制（软件中断）内核向进程（进程发生异常，向其通知）内核向进程（进程发生异常，向其通知）进程向进程（进程间通信，发送某个事件）进程向进程（进程间通信，发送某个事件）signal,killPOSIX定义的信号类型（终端，Ctrl+C，2）Ctrl+ZCtrl+Z，SIGSTOP SIGSTOP 信号的检测与处理流程系统空间中断或异常服务当前进程因中断/异常而进入核心态在返回用户态之前，调用do_signal()，handle_signal()转向用户空间执行信号处理程序陷入内核

15、后执行善后工作从内核返回用户空间用户空间应用程序信号处理程序应用程序继续执行发送信号执行信号处理程序断点断点返回信号处理程序执行结束，执行sigreturn()进程进程是现代操作系统中最基本、最重要的概念进程是现代操作系统中最基本、最重要的概念两个角度看进程概念：两个角度看进程概念：从理论角度看，进程是对正在运行的程序活动规律的从理论角度看，进程是对正在运行的程序活动规律的抽象抽象 从实现角度看，进程是一种数据结构从实现角度看，进程是一种数据结构为什么引入进程？为什么引入进程？刻画系统的动态性、发挥系统的并发性，提高资源利刻画系统的动态性、发挥系统的并发性，提高资源利用率（并发程序设计的工具）

16、用率（并发程序设计的工具）解决共享性，正确描述程序的执行状态（标识程序的解决共享性，正确描述程序的执行状态（标识程序的多次运行）多次运行）程序共享性可再入，可再用可再入程序，只有代码部分，调用方提供工作区，可同时被多个程序调用可再用程序，调用过程中可修改自身数据，一次只能被一个程序调用，串行对于可再入程序的多次运行，难以用程序本身来标识，需引入新的概念进程进程的定义与性质定义定义 进程进程(process)(process)是一个是一个可并发执行可并发执行的具有独立功能的的具有独立功能的程程序序关于某个关于某个数据集合数据集合的一次的一次执行过程执行过程，也是操作系统，也是操作系统进行进行资源

17、分配和保护的基本单位资源分配和保护的基本单位。性质性质 结构性结构性 共享性共享性 动态性动态性 独立性独立性 制约性制约性 并发性并发性进程的状态和转换三态模型运行态就绪态等待态落选选中等待结束出现等待事件阻塞态、睡眠态进程的状态和转换五态模型运行态就绪态等待态落选选中等待结束出现等待事件新建态终止态具有挂起功能的系统什么是进程挂起？将进程对换到外部存储器上，释放其占有的系将进程对换到外部存储器上，释放其占有的系统资源，排除在进程调度之外统资源，排除在进程调度之外为什么要挂起进程？提高系统资源的利用率提高系统资源的利用率减轻系统的负载减轻系统的负载调试程序、排除故障调试程序、排除故障具有挂起

18、状态的状态转换模型挂起就绪态挂起等待态新建态就绪态等待态运行态终止态提交提交等待事件结束等待事件结束挂起挂起挂起解除挂起解除挂起进程的描述操作系统的控制结构通常以表的方式来管理和维护通常以表的方式来管理和维护常见的四类表常见的四类表存储器设备文件进程存储表I/O表文件表进程表进程1内存映像进程N内存映像进程的描述进程的内存映像进程控制块(PCB)用户堆栈用户私有地址空间（代码段、数据段）共享地址空间代码段数据段堆栈段Minix进程结构进程上下文进程物理实体和支持进程运行的环境合称为进程上下文用户级上下文程序段、数据段、共享存储区、用户栈程序段、数据段、共享存储区、用户栈寄存器上下文程序状态字寄

19、存器、栈指针寄存器、控制寄存器、程序状态字寄存器、栈指针寄存器、控制寄存器、通用寄存器通用寄存器系统级上下文进程控制块、主存管理信息（如页表）、核心栈进程控制块、主存管理信息（如页表）、核心栈进程的描述进程控制块的结构每个进程都有且只有一个进程控制块每个进程都有且只有一个进程控制块进程标识信息（外部标识+内部标识）进程现场信息（通用寄存器、PSW寄存器、各种指针）进程控制信息（调度、组成、通信等信息、资源清单等）Minix进程控制表内容进程管理进程管理内存管理内存管理文件管理文件管理寄存器寄存器正文段正文段(代码段代码段)指针指针UMASKUMASK掩码掩码程序计数器程序计数器数据段指针数据段

20、指针根目录根目录程序状态字程序状态字(PSW)(PSW)bssbss段指针段指针工作目录工作目录栈指针栈指针退出状态退出状态文件描述符文件描述符进程状态进程状态信号状态信号状态有效有效UIDUID进程开始时间进程开始时间进程标识号进程标识号(PID)(PID)有效有效GIDGID使用的使用的CPUCPU时间时间父进程父进程(PPID)(PPID)系统调用参数系统调用参数子进程的子进程的CPUCPU时间时间进程组进程组(GID)(GID)各种标志位各种标志位下次报警时间下次报警时间真实真实UIDUID消息队列指针消息队列指针有效有效UIDUID挂起的信号位挂起的信号位真实真实GIDGID进程标识

21、号进程标识号(PID)(PID)有效有效GIDGID各种标志位各种标志位信号位图信号位图各种标志位各种标志位进程控制块单个进程块刻画一个进程的运行状态进程控制块的集合，则刻画了一个操作系统的当前状态进程控制块的使用和修改，只能由操作系统内核来完成进程队列将处于同一状态的所有进程控制块链接在一起的数据结构，称为进程队列便于操作系统进行统一的管理和调度先进先出PCB进程队列管理和状态转换示意CPU提交完成指派就绪队列超时事件1等待队列事件n等待队列等待事件1等待事件n等待事件2事件出现进程切换与模式切换模式切换进程切换模式切换是中断驱动的，在用户态和核心态之模式切换是中断驱动的，在用户态和核心态之

22、间切换间切换进程切换只能在核心态（管理态）完成，是一进程切换只能在核心态（管理态）完成，是一个进程与另一个进程之间的切换个进程与另一个进程之间的切换进程切换一定是先产生模式切换，而模式切换进程切换一定是先产生模式切换，而模式切换不一定导致进程切换。不一定导致进程切换。（模式切换频繁、进程（模式切换频繁、进程切换较少）切换较少）进程切换与模式切换用户态运行(1)核心态运行(2)等待态(4)就绪态(3)中断引起的模式切换模式切换中断、中断返回调度进程唤醒等待用户进程系统进程用户进程/系统进程用户进程和系统进程是一个进程的两个侧面，对应一个进程实体(PCB)系统进程系统进程是在核心态执行操作系统代码

23、的进程是在核心态执行操作系统代码的进程用户进程用户进程是在用户态执行用户程序的进程是在用户态执行用户程序的进程进程控制原语：在管态下执行、完成系统特定功能的过程。在管态下执行、完成系统特定功能的过程。其执行不可中断其执行不可中断操作系统内核实现操作系统内核实现操作系统用于进行进程控制的工具操作系统用于进行进程控制的工具进程控制的内容进程创建进程阻塞和唤醒进程撤消（终止）进程挂起和激活进程创建常见原语：常见原语：fork,clonefork,clone fork,fork,派生，父子进程关系派生，父子进程关系 clone,clone,克隆，对等关系克隆，对等关系主要内容：主要内容：申请申请PCB

24、PCB 分配进程映像空间分配进程映像空间 分配资源分配资源 将进程内容装入分配空间将进程内容装入分配空间 初始化初始化PCBPCB，分配唯一标识，分配唯一标识 加入就绪队列，或投入运行加入就绪队列，或投入运行 通知操作系统其他模块通知操作系统其他模块进程阻塞与唤醒常见原语（阻塞）：常见原语（阻塞）：wait,waitpidwait,waitpid进程阻塞内容：进程阻塞内容：保存现场到保存现场到PCBPCB 修改进程状态（运行修改进程状态（运行等待）等待）将将PCBPCB加入相加入相应应等待等待队队列列 转转入入进进程程调调度程序，度程序，调调度其他度其他进进程程进进程程唤唤醒内容：醒内容：从相

25、从相应应等待等待队队列中取出列中取出PCBPCB 修改修改进进程状程状态态（等待（等待 就就绪绪）PCBPCB加入就加入就绪队绪队列列进程撤消（终止）常见原语:exit原因：完成完成出现严重异常出现严重异常主要内容：根据进程标识号，找到相应的根据进程标识号，找到相应的PCBPCB将该进程资源归还给父进程或系统将该进程资源归还给父进程或系统若有子进程，则要撤消其所有子（孙）进程若有子进程，则要撤消其所有子（孙）进程PCBPCB出队，将出队，将PCBPCB归还归还PCBPCB池池线程引入线程的动机（原因）：以进程为单位的并发程序设计效率不高：以进程为单位的并发程序设计效率不高：进程时空开销大进程时

26、空开销大 频繁调度耗费大量频繁调度耗费大量CPUCPU时间时间 空间（内存资源）占用大空间（内存资源）占用大进程通信代价高进程通信代价高进程间并发粒度大进程间并发粒度大解决思路：解决思路：将进程的两项功能：将进程的两项功能：独立分配资源独立分配资源、独立分派调度独立分派调度分离分离单线程进程与多线程进程比较用户地址空间PCB用户堆栈系统堆栈单线程进程单线程进程用户地址空间PCB用户堆栈系统堆栈多线程进程多线程进程管理者执行控制用户堆栈系统堆栈执行控制执行序列多线程环境下进程与线程的定义进程：操作系统中进行保护和资源分配的基本单位操作系统中进行保护和资源分配的基本单位线程：操作系统中能够独立执行

27、的实体，是处理器调操作系统中能够独立执行的实体，是处理器调度和分配的基本单位度和分配的基本单位轻量级进程轻量级进程同一进程中的所有线程共享进程获得的主存空同一进程中的所有线程共享进程获得的主存空间和资源间和资源线程结构线程控制块(TCB)用户堆栈系统堆栈（可选）线程的特征并发性：可在一个或多个可在一个或多个CPUCPU上并发或并行执行上并发或并行执行共享性：共享进程资源，通信和同步更容易实现共享进程资源，通信和同步更容易实现动态性：一个执行序列的执行过程一个执行序列的执行过程结构性TCBTCB线程的状态与转换运行态就绪态等待态落选选中等待结束出现等待事件线程的管理与实现通过提供线程包（库）来提

28、供一整套关于线程管通过提供线程包（库）来提供一整套关于线程管理的原语实现对多线程的支持理的原语实现对多线程的支持基本的线程管理（控制）：基本的线程管理（控制）：spawn spawn 孵化孵化 block block 阻塞阻塞/封锁封锁 unblock unblock 活化活化/恢复恢复 finish finish 撤消撤消线程的实现方式：线程的实现方式：内核级实现内核级实现 KLTKLT 用户级实现用户级实现 ULTULT 混合实现混合实现三种线程实现方式示意线程库用户级线程用户空间P内核空间内核级线程线程库混合式线程ULTKLTProcessPPP用户空间用户空间内核空间内核空间P内核级实

29、现的优缺点优点：能够在多个处理器上同时执行多个线程能够在多个处理器上同时执行多个线程某个进程中一个线程被阻塞，不会影响其他线某个进程中一个线程被阻塞，不会影响其他线程的运行程的运行缺点：线程间的切换代价高，需要涉及两次模式切换线程间的切换代价高，需要涉及两次模式切换用户级实现的优缺点优点：线程切换不涉及模式切换（代价小）线程切换不涉及模式切换（代价小）调度算法的选择较灵活调度算法的选择较灵活缺点：同一进程的多个线程不能同时在多个处理器上同一进程的多个线程不能同时在多个处理器上运行运行一个线程的阻塞将导致整个进程的阻塞一个线程的阻塞将导致整个进程的阻塞混合型实现的优缺点优点：设计得当，将可结合前

30、两者的优点，并避开其设计得当，将可结合前两者的优点，并避开其缺点缺点缺点：设计不当，将产生更差的效果设计不当，将产生更差的效果并发多线程程序设计的优点易于实现多个活动间的通信更低的管理开销I/O密集型应用能获得更好的性能能更好地利用多（核）处理器，加快程序执行处理器调度主要内容：挑选作业进入内存挑选作业进入内存在进程之间分配处理器时间在进程之间分配处理器时间处理调度细可分为：高级调度，作业管理（用户接口）高级调度，作业管理（用户接口）中级调度，决定作业（进程）进入内存中级调度，决定作业（进程）进入内存低级调度，决定作业（进程）占用处理器低级调度，决定作业（进程）占用处理器处理器调度层次示意中级

31、调度新建态挂起就绪态挂起等待态高级调度低级调度运行态就绪态等待态终止态处理器调度模型CPU提交指派就绪队列超时挂起就绪队列等待队列等待事件事件出现低级调度低级调度高级调度高级调度挂起等待队列中级调度中级调度中级调度中级调度高级调度又称作业调度、长程调度多道批处理系统中的主要内容：后备作业后备作业进进程程作业准备作业准备启动启动善后工作善后工作分时系统中的主要内容：是否接受一个终端用户的连接？是否接受一个终端用户的连接？交互作业能否被接纳，并创建进程？交互作业能否被接纳，并创建进程？中级调度又称平衡负载调度、中程调度主要内容：控制主存储器中能容纳的进程数控制主存储器中能容纳的进程数保证在合理数目

32、的进程间竞争处理器及相关资保证在合理数目的进程间竞争处理器及相关资源源具有“挂起”功能的操作系统“挂起挂起”状态的进程不参与低级调度状态的进程不参与低级调度低级调度又称（进）线程调度、短程调度两类低级调度方式：剥夺方式剥夺方式优先级剥夺优先级剥夺限时剥夺限时剥夺非剥夺方式非剥夺方式剥夺方式开销通常大于非剥夺方式，但可避免一个进程或线程长时间独占处理器调度算法任何层次的处理器调度均由操作系统相应的调度程序实施，调度程序所使用的算法，被称为调度算法。如何评价调度算法？考虑的主要因素：考虑的主要因素：资源利用率，资源利用率，CPUCPU有效工作时间有效工作时间/CPU/CPU总运行时间总运行时间 响

33、应时间（分时系统、实时系统）响应时间（分时系统、实时系统）从作业提交到收到回应的时间从作业提交到收到回应的时间 周转时间（批处理系统）周转时间（批处理系统）作业提交开始到作业完成的时间作业提交开始到作业完成的时间平均周转时间、平均带权周转时间平均周转时间、平均带权周转时间 吞吐率吞吐率单位时间内处理的作业数单位时间内处理的作业数 公平性公平性确保每个用户，每个进程获得合理的确保每个用户，每个进程获得合理的CPUCPU份额或其他资源份额，份额或其他资源份额，不会出现不会出现“饿死饿死”现象现象批处理作业的管理与调度作业的生命周期：提交提交收容收容执执行行完成完成输入状态后备状态执行状态完成状态高

34、级调度中级调度低级调度批处理作业调度考虑用户角度：每个用户希望自己的作业周转时间等于或接近每个用户希望自己的作业周转时间等于或接近作业执行时间作业执行时间操作系统角度：处理器的利用率高，作业平均周转时间小处理器的利用率高，作业平均周转时间小几个典型的作业（高级）调度算法先来先服务算法最短作业优先算法最短剩余时间优先算法响应比最高优先算法另外，还有：优先数法优先数法分类调度算法分类调度算法用磁带与不用磁带的作业搭配用磁带与不用磁带的作业搭配先来先服务算法FCFS按照作业进入系统的作业后备队列的先后次序挑选作业，先进入系统的作业优先被挑选优点：实现简单实现简单缺点：不利于短作业而优待长作业不利于短

35、作业而优待长作业效率低效率低最短作业优先算法SJF以进入系统的作业所要求的CPU时间长短为标准，总是选取时间最短的作业投入运行优点：实现简单实现简单缺点：实际系统中，往往很难预测作业的运行时间实际系统中，往往很难预测作业的运行时间导致长作业等待时间过长，甚至出现导致长作业等待时间过长，甚至出现“饥饿饥饿”现象现象效率高效率高最短剩余时间优先SRTF每次调度时，总选择预测剩余运行时间最短的作业优先运行优点：效率相对较高效率相对较高缺点：调度频繁调度频繁与最短作业优先类似与最短作业优先类似响应比最高优先算法HRRF在FCFS和SJF之间的折中，既考虑作业的等待时间，而考虑作业的运行时间响应比=作业

36、响应时间/作业估计计算时间优点：防止了饥饿发生防止了饥饿发生几个典型的低级调度算法先来先服务时间片轮转优先数调度多级反馈队列调度保证调度彩票调度先来先服务调度算法非抢占调度方式使用就绪队列实现，先进先出特点：实现容易，但效率低，不利于实现容易，但效率低，不利于I/OI/O频繁操作的进频繁操作的进程程时间片轮转调度算法抢占调度方式抢占调度方式实现：实现：时钟中断，轮流执行时钟中断，轮流执行分类：分类：基本时间片轮转法，时间片相同基本时间片轮转法，时间片相同 动态时间片轮转法，时间片不同动态时间片轮转法，时间片不同时间片的选取时间片的选取 时间片太长时间片太长 =FCFS=FCFS 时间片太短，调

37、度频繁时间片太短，调度频繁优先数调度算法抢占和非抢占调度方式实现：取优先数最大的进程执行取优先数最大的进程执行分类：静态优先数静态优先数动态优先数动态优先数如何计算优先数？如何计算优先数？何时计算优先数？何时计算优先数？动态优先数调度算法的基本原则一个进程连续占用处理器的时间越长，则其再次获得调度的优先数越小一个进程等待处理器的时间越长，则其再次获得调度的优先数越大动态优先数调度算法举例早期UNIX版本的动态优先数计算公式：p pri=min 127,(p cpu/16+PUSER+p p pri=min 127,(p cpu/16+PUSER+p nice)nice)值越小，优先权越高（取值

38、范围：值越小，优先权越高（取值范围：-100127-100127）重要参数：重要参数：p nice p nice 描述进程的紧急程度（基本优先数）描述进程的紧急程度（基本优先数）p cpu p cpu 描述进程的动态情况，反映了进程使用处描述进程的动态情况，反映了进程使用处理器的时间，每理器的时间，每20ms20ms对当前运行进程的该参数加一，对当前运行进程的该参数加一，每每1s1s检查所有进程的参数，小于检查所有进程的参数，小于1010则置则置0 0，大于则，大于则减减1010。动态优先数调度算法举例调度的实施：动态优先数调度算法，计算各进程的优先数需动态优先数调度算法，计算各进程的优先数需

39、要占用较多的要占用较多的CPUCPU时间，为降低调度开销，应时间，为降低调度开销，应选择合适的时机和合适的计算对象选择合适的时机和合适的计算对象UNIXUNIX算法的实现：算法的实现：对于优先数大于对于优先数大于100100的进程，系统每秒种计算一次的进程，系统每秒种计算一次优先数优先数每次系统调用命令处理完成后，重新对现进程的优每次系统调用命令处理完成后，重新对现进程的优先数进行计算先数进行计算多级反馈队列调度算法又称：反馈循环队列或多队列策略主要思想：将就绪队列分为多级队列，较高的队列分配的将就绪队列分为多级队列，较高的队列分配的时间片较短，但具有较高的优先权占有处理器，时间片较短，但具有

40、较高的优先权占有处理器，同一队列按先来先服务原则调度同一队列按先来先服务原则调度进程分级方式：静态分级静态分级动态分级动态分级多级反馈队列调度算法示意低级就绪队列运行等待其他外设高级就绪队列中级就绪队列等待磁盘/磁带选中，时间片500ms超过时间片启动磁盘/磁带启动其他外设选中，时间片200ms选中，时间片100ms保证调度算法基本思想：向用户做出明确的性能保证，并在调度中实现向用户做出明确的性能保证，并在调度中实现该保证该保证例：在有在有n n运行的用户系统中，每个进程将获得处运行的用户系统中，每个进程将获得处理器能力的理器能力的1/n1/n。实现：实现：计算实际获得的计算实际获得的CPUC

41、PU时间和应获得的时间和应获得的CPUCPU时间之比，调度时间之比，调度转向比率最低的进程。转向比率最低的进程。彩票调度算法基本思想：为进程发放针对系统各资源的彩票。当调度程为进程发放针对系统各资源的彩票。当调度程序需要作出决策时，随机选择一张彩票，持有序需要作出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。该彩票的进程将获得系统资源。进程所持有的彩票越多，获得系统资源的机会进程所持有的彩票越多，获得系统资源的机会越大越大特点：对系统的情况反应迅速对系统的情况反应迅速允许多个进程进行协作允许多个进程进行协作实时调度与调度算法什么是实时系统？时间因素非常关键的系统，强调响应时间时间因

42、素非常关键的系统，强调响应时间分类：分类：软实时系统、硬实时系统软实时系统、硬实时系统构成：构成：将程序分为多个进程，每个进程负责处理相应的周将程序分为多个进程，每个进程负责处理相应的周期性出现的事件期性出现的事件特点：特点：规模小、进程切换快、中断可屏蔽、处理时间短、规模小、进程切换快、中断可屏蔽、处理时间短、能够管理多个高精度的定时器能够管理多个高精度的定时器实时调度与调度算法什么是可调度？在忽略调度本身所花费在忽略调度本身所花费CPUCPU时间的前提下，系时间的前提下，系统能够在各事件规定的响应时间处理完这些事统能够在各事件规定的响应时间处理完这些事件。件。对于周期事件，判断系统任务是否

43、可调度的数对于周期事件，判断系统任务是否可调度的数学公式：学公式：C C1 1/P/P1 1+C+C2 2/P/P2 2+C+Cmm/P/Pmm=1=1其中其中mm为事件总数，为事件总数，C Ci i为某个事件的处理时间，为某个事件的处理时间，P Pi i为为事件发生的周期事件发生的周期实时调度与调度算法几个典型的实时调度算法：单比率调度算法（静态）单比率调度算法（静态）进程的优先级与对应的事件出现频率成正比进程的优先级与对应的事件出现频率成正比该算法最优该算法最优限期调度算法（动态）限期调度算法（动态）进程就绪队列按照对应事件处理的截止期限排序进程就绪队列按照对应事件处理的截止期限排序最少裕

44、度调度算法（动态）最少裕度调度算法（动态）裕度裕度 =截止时间截止时间 -（就绪时间（就绪时间 +计算时间）计算时间）选择裕度最小的进程先执行选择裕度最小的进程先执行实时调度算法举例A,BA,B两进程于当前时间点两进程于当前时间点12ms12ms处同时被创建，并处同时被创建，并进入就绪队列。各进程的相关信息：进入就绪队列。各进程的相关信息：A A进程的截止时间是进程的截止时间是15ms15ms，估计计算时间为，估计计算时间为1ms1ms B B进程的截止时间是进程的截止时间是16ms16ms，估计计算时间为，估计计算时间为2.5ms2.5ms采用上述三种调度算法，当前时间应选择哪个进采用上述三

45、种调度算法，当前时间应选择哪个进程运行？程运行？12msA,B进程就绪15msA进程截止16msB进程截止多处理器调度与调度算法多处理器系统：多处理器系统：松散耦合多处理器系统松散耦合多处理器系统 紧密耦合多处理器系统紧密耦合多处理器系统同步粒度：同步粒度：是指进程之间同步的频率是指进程之间同步的频率 可分为：可分为：细粒度（指令）细粒度（指令）中粒度（线程）中粒度（线程）粗粒度（进程）粗粒度（进程）超粗粒度（网络分布系统）超粗粒度（网络分布系统）独立独立多处理器调度与调度算法多处理器调度设计的要点：为进程分配处理器为进程分配处理器在主从方式、对等方式和混合方式之间选择？在主从方式、对等方式和

46、混合方式之间选择？在单个处理器上支持多道程序设计在单个处理器上支持多道程序设计是否需要支持多道程序并发执行？是否需要支持多道程序并发执行？如何指派进程如何指派进程如何进行低级调度？如何进行低级调度？多处理器调度与调度算法进程调度算法不是关注的重点多处理器调度主要是线程调度几个典型的调度算法负载共享调度算法负载共享调度算法群调度算法群调度算法处理器专派调度算法处理器专派调度算法动态调度算法动态调度算法负载共享调度算法基本思想：基本思想：进程并不分配给一个特定的处理器，系统维护一个全进程并不分配给一个特定的处理器，系统维护一个全局的就绪线程队列，当某个处理器空闲时，就选择一局的就绪线程队列，当某个

47、处理器空闲时，就选择一个就绪线程占有处理器运行。个就绪线程占有处理器运行。CPU1CPU2CPU1全局就绪线程队列负载共享调度算法优点：优点：把负载均匀分派到所有可用的处理器，保证了处理器把负载均匀分派到所有可用的处理器，保证了处理器的高效率的高效率 不需要一个集中的调度程序不需要一个集中的调度程序 运行进程的选择可以采用各种可行的策略运行进程的选择可以采用各种可行的策略先来先服务、最少线程数优先、有剥夺的最少线程数优先先来先服务、最少线程数优先、有剥夺的最少线程数优先缺点：缺点：就绪线程队列必须互斥访问，可能成为性能瓶颈就绪线程队列必须互斥访问，可能成为性能瓶颈 被抢占的线程很难在同一个处理

48、器恢复执行，处理器被抢占的线程很难在同一个处理器恢复执行，处理器高速缓存的恢复带来性能的下降高速缓存的恢复带来性能的下降 线程间没有优先级差别线程间没有优先级差别群调度算法基本思想：把一组进程在同一时间一次性调度到一组处理把一组进程在同一时间一次性调度到一组处理器上运行。器上运行。优点：当紧密相关的进程同时执行时，同步造成的等当紧密相关的进程同时执行时，同步造成的等待将减少，进程切换也相应减少，提高系统运待将减少，进程切换也相应减少，提高系统运行效率行效率由于是一次调度一组进程，调度的代价减少由于是一次调度一组进程，调度的代价减少处理器专派调度算法基本思想：给一个应用专门指派一组处理器，一旦一个应给一个应用专门指派一组处理器，一旦一个应用被调度，它的每个线程被分配一个处理器并用被调度，它的每个线程被分配一个处理器并一直占有该处理器，直到整个应用运行结束。一直占有该处理器，直到整个应用运行结束。特点：仅考虑单个应用的执行效率，不考虑处理器的仅考虑单个应用的执行效率，不考虑处理器的利用率利用率动态调度算法基本思想：由操作系统和应用进程共同完成调度。由操作系统和应用进程共同完成调度。操作系统负责在应用进程间划分处理器，应用操作系统负责在应用进程间划分处理器，应用进程自主决定其内部线程的执行情况进程自主决定其内部线程的执行情况