《操作系统(处理器管理).ppt》由会员分享，可在线阅读，更多相关《操作系统(处理器管理).ppt（100页珍藏版）》请在三一办公上搜索。
1、操作系统（处理器管理）,徐锋南京大学计算机科学与技术系,主要内容,什么是处理器管理？处理器的相关知识中断技术进程与线程处理器调度作业管理与调度低级调度,什么是处理器管理？,处理器管理是操作系统的重要组成部分，负责管理、调度和分派计算机系统的重要资源处理器，并控制程序执行。涉及两方面内容处理器运行的程序（进程）,处理器的相关知识,处理器寄存器机器指令处理器状态程序状态字(PSW,Program Status Word),处理器,内部组成：控制器运算器寄存器中断装置输入/输出电路高速缓存(Cache),寄存器,通用寄存器数据寄存器地址寄存器I/O地址寄存器I/O缓冲寄存器控制寄存器程序计数器指令寄
2、存器中断寄存器内存和I/O控制寄存器,机器指令,指令是指示计算机执行某些操作的命令，一台计算机的所有指令的集合，称为指令系统，反映机器的功能和能力指令系统可分为：复杂指令系统(CISC)、精简指令系统(RISC)指令分类按功能分：运算（算术运算、逻辑运算、移位运算）程序控制（转移、子程序调用、返回）数据传送（一般传送、堆栈操作、数据交换）输入/输出指令按使用者分：特权指令，仅供操作系统内核调用非特权指令,处理器状态,特权指令的执行限制，使处理器必须能区分当前运行的程序是操作系统还是普通应用程序处理器状态：管理状态（特权状态、系统状态、特态、管态），能执行所有机器指令用户状态（目标状态、用户模式
3、、常态、目态），只能执行非特权指令中断导致状态转换程序请求操作系统服务产生中断事件,程序状态字(PSW),用于区别不同的处理器工作状态每个程序都有一个与其执行相关的PSW，而每个处理器均设置一组相关寄存器用于存储PSW信息PSW的主要内容程序基本状态（程序计数器、条件码、状态位）中断码中断屏蔽位,中断技术,什么是中断？中断源分类中断装置中断处理程序中断的优先级和多重中断,什么是中断？,中断是用来向CPU报告某设备已完成某项操作的手段，是并发程序的基础。中断是指程序执行过程中，当发生某个事件时，？终止CPU上现行程序的运行，引出处理该事件的服务程序执行的过程。中断事件处理需要硬件（中断装置）和软
4、件（中断处理程序）配合完成。,中断源分类,中断源：引起中断的事件按中断事件的性质和激活的手段分：强迫性中断事件机器故障、程序性错误（异常）、外部中断、输入输出中断事件、自愿性中断事件调用访管指令,中断源分类,内外的划分标准：处理器和主存为内，其他硬件为外按中断信号的来源分：外中断（中断）电源故障中断、时钟中断（外部）、控制台中断、输入输出中断、内中断（异常）通路校验错、主存奇偶校验错、非法操作码、地址越界、页面失效、调试指令、访管中断、算术操作溢出、,中断与异常的区别,中断特点：与现行指令无关发生时间与CPU所处状态无关两条指令之间才能响应中断可被屏蔽可嵌套异常特点：由现行指令执行而引起在目态
5、发生可在一个指令周期内处理不可屏蔽、不可嵌套可细分为：出错，处理完后回到当前出错指令陷入，处理完后执行下一条指令（常用于系统功能调用）,中断装置,定义：发现中断源并产生中断的硬件，通常包括逻辑电路和中断寄存器具体功能：捕获中断源，响应中断请求保护现场启动处理中断事件的中断处理程序，CPU从目态切换为管态,32位处理器的PC机通常的中断硬件结构,系统数据总线,CPU,INT,INTA,主中断控制器,主中断控制器,IRQ0 时钟,键盘,tty2,tty1,IRQ8实时时钟,中断装置工作过程演示,中断寄存器,中断装置,中断控制部件,内存,PSW寄存器,1#中断向量,现行PSW,中断处理程序,处理中断
6、事件的程序具体功能：保护一些未被硬件保护的现场信息识别中断源，分析中断产生的原因处理发生的中断事件恢复正常操作实现方法：向量地址是中断服务程序的入口中断向量表,0,1,3,0#入口地址,1#入口地址,3#入口地址,处理程序段,中断事件处理,中断和异常的一般处理过程硬件故障中断程序性中断（浮点溢出、非法指令）输入输出中断I/O操作正常结束I/O操作发生故障I/O操作发生异常设备报道或设备结束访管中断时钟中断,中断的优先级,优先级同时有多个中断事件发生时，中断装置按一定顺序对其作出响应，其先后顺序即优先级优先级设定的原则按造成计算机系统出错的严重程度划分例，机器校验中断 自愿性中断 程序性中断 外
7、部中断 输入输出中断 重启动中断,中断的优先级和多重中断,中断优先级的设计导致：中断屏蔽高优先级的中断响应过程中，应屏蔽低优先级的中断有些中断是不能被屏蔽的，如自愿访管中断,多重中断事件的处理,中断处理过程中，又产生了新的中断事件串行处理中断处理过程中关中断嵌套处理开中断，暂停当前执行的中断处理程序，转而执行更高优先级的中断处理程序即时处理主要针对中断处理程序执行过程中发生的程序性中断,Linux中断处理,快中断与慢中断区别,慢中断处理前需要保存所有寄存器的值，而快中断仅需保存会被内核使用的寄存器的值慢中断处理时，不关中断，快中断处理时，关中断慢中断处理完成后，通常不立即返回被中断进程，而是转
8、而执行调度程序。快中断处理完成后，通常返回被中断进程继续执行,Minix中断处理,类似于linux的低半处理方式目的:为了缩短屏蔽中断的时间,提高系统并发工作的能力一种任务延迟处理机制,核心代码在关中断的核心态完成与中断事件有关的基本处理,另外一部分耗时的工作留在中断处理例程之外,在开中断的非核心态完成。这些非核心态运行的代码，在Minix中被组织成与设备基本相对应的任务（驱动程序）进程，如磁盘任务、终端任务、时钟任务等等,其中中断任务需要对应如键盘,RS232串口等硬件.,信号机制,一种模拟硬件中断的简单通信机制（软件中断）内核向进程（进程发生异常，向其通知）进程向进程（进程间通信，发送某个
9、事件）signal,killPOSIX定义的信号类型（终端，Ctrl+C，2）Ctrl+Z，SIGSTOP,信号的检测与处理流程,系统空间,中断或异常服务,当前进程因中断/异常而进入核心态,在返回用户态之前，调用do_signal()，handle_signal()转向用户空间执行信号处理程序,陷入内核后执行善后工作,从内核返回用户空间,进程,进程是现代操作系统中最基本、最重要的概念两个角度看进程概念：从理论角度看，进程是对正在运行的程序活动规律的抽象从实现角度看，进程是一种数据结构为什么引入进程？刻画系统的动态性、发挥系统的并发性，提高资源利用率（并发程序设计的工具）解决共享性，正确描述程序
10、的执行状态（标识程序的多次运行）,程序共享性可再入，可再用,可再入程序，只有代码部分，调用方提供工作区，可同时被多个程序调用可再用程序，调用过程中可修改自身数据，一次只能被一个程序调用，串行对于可再入程序的多次运行，难以用程序本身来标识，需引入新的概念进程,进程的定义与性质,定义进程(process)是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。性质结构性共享性动态性独立性制约性并发性,进程的状态和转换,三态模型,运行态,就绪态,等待态,落选,选中,等待结束,出现等待事件,阻塞态、睡眠态,进程的状态和转换,五态模型,运行态,就绪态
11、,等待态,落选,选中,等待结束,出现等待事件,新建态,终止态,具有挂起功能的系统,什么是进程挂起？将进程对换到外部存储器上，释放其占有的系统资源，排除在进程调度之外为什么要挂起进程？提高系统资源的利用率减轻系统的负载调试程序、排除故障,具有挂起状态的状态转换模型,挂起就绪态,挂起等待态,新建态,就绪态,等待态,运行态,终止态,提交,提交,等待事件结束,等待事件结束,挂起,挂起,挂起,解除挂起,解除挂起,进程的描述,操作系统的控制结构通常以表的方式来管理和维护常见的四类表,进程的描述,进程的内存映像,进程控制块(PCB),用户堆栈,用户私有地址空间（代码段、数据段）,共享地址空间,代码段,数据段
12、,堆栈段,Minix进程结构,进程上下文,进程物理实体和支持进程运行的环境合称为进程上下文用户级上下文程序段、数据段、共享存储区、用户栈寄存器上下文程序状态字寄存器、栈指针寄存器、控制寄存器、通用寄存器系统级上下文进程控制块、主存管理信息（如页表）、核心栈,进程的描述,进程控制块的结构每个进程都有且只有一个进程控制块,进程标识信息（外部标识+内部标识）,进程现场信息（通用寄存器、PSW寄存器、各种指针）,进程控制信息（调度、组成、通信等信息、资源清单等）,Minix进程控制表内容,进程控制块,单个进程块刻画一个进程的运行状态进程控制块的集合，则刻画了一个操作系统的当前状态进程控制块的使用和修改
13、，只能由操作系统内核来完成,进程队列,将处于同一状态的所有进程控制块链接在一起的数据结构，称为进程队列便于操作系统进行统一的管理和调度,先进先出,PCB,进程队列管理和状态转换示意,CPU,提交,完成,指派,就绪队列,超时,事件1等待队列,事件n等待队列,等待事件1,等待事件n,等待事件2,事件出现,进程切换与模式切换,模式切换进程切换模式切换是中断驱动的，在用户态和核心态之间切换进程切换只能在核心态（管理态）完成，是一个进程与另一个进程之间的切换进程切换一定是先产生模式切换，而模式切换不一定导致进程切换。（模式切换频繁、进程切换较少）,进程切换与模式切换,用户态运行(1),核心态运行(2),
14、等待态(4),就绪态(3),中断引起的模式切换,模式切换,中断、中断返回,调度进程,唤醒,等待,用户进程,系统进程,用户进程/系统进程,用户进程和系统进程是一个进程的两个侧面，对应一个进程实体(PCB)系统进程是在核心态执行操作系统代码的进程用户进程是在用户态执行用户程序的进程,进程控制,原语：在管态下执行、完成系统特定功能的过程。其执行不可中断操作系统内核实现操作系统用于进行进程控制的工具,进程控制的内容,进程创建进程阻塞和唤醒进程撤消（终止）进程挂起和激活,进程创建,常见原语：fork,clonefork,派生，父子进程关系clone,克隆，对等关系主要内容：申请PCB分配进程映像空间分配
15、资源将进程内容装入分配空间初始化PCB，分配唯一标识加入就绪队列，或投入运行通知操作系统其他模块,进程阻塞与唤醒,常见原语（阻塞）：wait,waitpid进程阻塞内容：保存现场到PCB修改进程状态（运行等待）将PCB加入相应等待队列转入进程调度程序，调度其他进程进程唤醒内容：从相应等待队列中取出PCB修改进程状态（等待 就绪）PCB加入就绪队列,进程撤消（终止）,常见原语:exit原因：完成出现严重异常主要内容：根据进程标识号，找到相应的PCB将该进程资源归还给父进程或系统若有子进程，则要撤消其所有子（孙）进程PCB出队，将PCB归还PCB池,线程,引入线程的动机（原因）：以进程为单位的并发
16、程序设计效率不高：进程时空开销大频繁调度耗费大量CPU时间空间（内存资源）占用大进程通信代价高进程间并发粒度大解决思路：将进程的两项功能：独立分配资源、独立分派调度分离,单线程进程与多线程进程比较,用户地址空间,PCB,用户堆栈,系统堆栈,单线程进程,用户地址空间,PCB,用户堆栈,系统堆栈,多线程进程,管理者,执行控制,用户堆栈,系统堆栈,执行控制,执行序列,多线程环境下进程与线程的定义,进程：操作系统中进行保护和资源分配的基本单位线程：操作系统中能够独立执行的实体，是处理器调度和分配的基本单位轻量级进程同一进程中的所有线程共享进程获得的主存空间和资源,线程结构,线程控制块(TCB),用户堆
17、栈,系统堆栈（可选）,线程的特征,并发性：可在一个或多个CPU上并发或并行执行共享性：共享进程资源，通信和同步更容易实现动态性：一个执行序列的执行过程结构性TCB,线程的状态与转换,运行态,就绪态,等待态,落选,选中,等待结束,出现等待事件,线程的管理与实现,通过提供线程包（库）来提供一整套关于线程管理的原语实现对多线程的支持基本的线程管理（控制）：spawn 孵化block 阻塞/封锁unblock 活化/恢复finish 撤消线程的实现方式：内核级实现 KLT用户级实现 ULT混合实现,三种线程实现方式示意,线程库,用户级线程,用户空间,内核空间,内核级线程,线程库,混合式线程,ULT,K
18、LT,Process,用户空间,用户空间,内核空间,内核空间,内核级实现的优缺点,优点：能够在多个处理器上同时执行多个线程某个进程中一个线程被阻塞，不会影响其他线程的运行缺点：线程间的切换代价高，需要涉及两次模式切换,用户级实现的优缺点,优点：线程切换不涉及模式切换（代价小）调度算法的选择较灵活缺点：同一进程的多个线程不能同时在多个处理器上运行一个线程的阻塞将导致整个进程的阻塞,混合型实现的优缺点,优点：设计得当，将可结合前两者的优点，并避开其缺点缺点：设计不当，将产生更差的效果,并发多线程程序设计的优点,易于实现多个活动间的通信更低的管理开销I/O密集型应用能获得更好的性能能更好地利用多（核
19、）处理器，加快程序执行,处理器调度,主要内容：挑选作业进入内存在进程之间分配处理器时间处理调度细可分为：高级调度，作业管理（用户接口）中级调度，决定作业（进程）进入内存低级调度，决定作业（进程）占用处理器,处理器调度层次示意,中级调度,新建态,挂起就绪态,挂起等待态,高级调度,低级调度,运行态,就绪态,等待态,终止态,处理器调度模型,CPU,提交,指派,就绪队列,超时,挂起就绪队列,等待队列,等待事件,事件出现,低级调度,高级调度,挂起等待队列,中级调度,中级调度,高级调度,又称作业调度、长程调度多道批处理系统中的主要内容：后备作业进程作业准备启动善后工作分时系统中的主要内容：是否接受一个终端
20、用户的连接？交互作业能否被接纳，并创建进程？,中级调度,又称平衡负载调度、中程调度主要内容：控制主存储器中能容纳的进程数保证在合理数目的进程间竞争处理器及相关资源具有“挂起”功能的操作系统“挂起”状态的进程不参与低级调度,低级调度,又称（进）线程调度、短程调度两类低级调度方式：剥夺方式优先级剥夺限时剥夺非剥夺方式剥夺方式开销通常大于非剥夺方式，但可避免一个进程或线程长时间独占处理器,调度算法,任何层次的处理器调度均由操作系统相应的调度程序实施，调度程序所使用的算法，被称为调度算法。,如何评价调度算法？,考虑的主要因素：资源利用率，CPU有效工作时间/CPU总运行时间响应时间（分时系统、实时系统
21、）从作业提交到收到回应的时间周转时间（批处理系统）作业提交开始到作业完成的时间平均周转时间、平均带权周转时间吞吐率单位时间内处理的作业数公平性确保每个用户，每个进程获得合理的CPU份额或其他资源份额，不会出现“饿死”现象,批处理作业的管理与调度,作业的生命周期：提交收容执行完成,输入状态,后备状态,执行状态,完成状态,高级调度,中级调度低级调度,批处理作业调度考虑,用户角度：每个用户希望自己的作业周转时间等于或接近作业执行时间操作系统角度：处理器的利用率高，作业平均周转时间小,几个典型的作业（高级）调度算法,先来先服务算法最短作业优先算法最短剩余时间优先算法响应比最高优先算法另外，还有：优先数
22、法分类调度算法用磁带与不用磁带的作业搭配,先来先服务算法FCFS,按照作业进入系统的作业后备队列的先后次序挑选作业，先进入系统的作业优先被挑选优点：实现简单缺点：不利于短作业而优待长作业效率低,最短作业优先算法SJF,以进入系统的作业所要求的CPU时间长短为标准，总是选取时间最短的作业投入运行优点：实现简单缺点：实际系统中，往往很难预测作业的运行时间导致长作业等待时间过长，甚至出现“饥饿”现象效率高,最短剩余时间优先SRTF,每次调度时，总选择预测剩余运行时间最短的作业优先运行优点：效率相对较高缺点：调度频繁与最短作业优先类似,响应比最高优先算法HRRF,在FCFS和SJF之间的折中，既考虑作
23、业的等待时间，而考虑作业的运行时间响应比=作业响应时间/作业估计计算时间优点：防止了饥饿发生,几个典型的低级调度算法,先来先服务时间片轮转优先数调度多级反馈队列调度保证调度彩票调度,先来先服务调度算法,非抢占调度方式使用就绪队列实现，先进先出特点：实现容易，但效率低，不利于I/O频繁操作的进程,时间片轮转调度算法,抢占调度方式实现：时钟中断，轮流执行分类：基本时间片轮转法，时间片相同动态时间片轮转法，时间片不同时间片的选取时间片太长=FCFS时间片太短，调度频繁,优先数调度算法,抢占和非抢占调度方式实现：取优先数最大的进程执行分类：静态优先数动态优先数如何计算优先数？何时计算优先数？,动态优先
24、数调度算法的基本原则,一个进程连续占用处理器的时间越长，则其再次获得调度的优先数越小一个进程等待处理器的时间越长，则其再次获得调度的优先数越大,动态优先数调度算法举例,早期UNIX版本的动态优先数计算公式：p pri=min 127,(p cpu/16+PUSER+p nice)值越小，优先权越高（取值范围：-100127）重要参数：p nice 描述进程的紧急程度（基本优先数）p cpu 描述进程的动态情况，反映了进程使用处理器的时间，每20ms对当前运行进程的该参数加一，每1s检查所有进程的参数，小于10则置0，大于则减10。,动态优先数调度算法举例,调度的实施：动态优先数调度算法，计算各
25、进程的优先数需要占用较多的CPU时间，为降低调度开销，应选择合适的时机和合适的计算对象UNIX算法的实现：对于优先数大于100的进程，系统每秒种计算一次优先数每次系统调用命令处理完成后，重新对现进程的优先数进行计算,多级反馈队列调度算法,又称：反馈循环队列或多队列策略主要思想：将就绪队列分为多级队列，较高的队列分配的时间片较短，但具有较高的优先权占有处理器，同一队列按先来先服务原则调度进程分级方式：静态分级动态分级,多级反馈队列调度算法示意,低级就绪队列,运行,等待其他外设,高级就绪队列,中级就绪队列,等待磁盘/磁带,选中，时间片500ms,超过时间片,启动磁盘/磁带,启动其他外设,选中，时间
26、片200ms,选中，时间片100ms,保证调度算法,基本思想：向用户做出明确的性能保证，并在调度中实现该保证例：在有n运行的用户系统中，每个进程将获得处理器能力的1/n。实现：计算实际获得的CPU时间和应获得的CPU时间之比，调度转向比率最低的进程。,彩票调度算法,基本思想：为进程发放针对系统各资源的彩票。当调度程序需要作出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。进程所持有的彩票越多，获得系统资源的机会越大特点：对系统的情况反应迅速允许多个进程进行协作,实时调度与调度算法,什么是实时系统？时间因素非常关键的系统，强调响应时间分类：软实时系统、硬实时系统构成：将程序分为多个进程
27、，每个进程负责处理相应的周期性出现的事件特点：规模小、进程切换快、中断可屏蔽、处理时间短、能够管理多个高精度的定时器,实时调度与调度算法,什么是可调度？在忽略调度本身所花费CPU时间的前提下，系统能够在各事件规定的响应时间处理完这些事件。对于周期事件，判断系统任务是否可调度的数学公式：C1/P1+C2/P2+Cm/Pm=1其中m为事件总数，Ci为某个事件的处理时间，Pi为事件发生的周期,实时调度与调度算法,几个典型的实时调度算法：单比率调度算法（静态）进程的优先级与对应的事件出现频率成正比该算法最优限期调度算法（动态）进程就绪队列按照对应事件处理的截止期限排序最少裕度调度算法（动态）裕度=截止
28、时间-（就绪时间+计算时间）选择裕度最小的进程先执行,实时调度算法举例,A,B两进程于当前时间点12ms处同时被创建，并进入就绪队列。各进程的相关信息：A进程的截止时间是15ms，估计计算时间为1msB进程的截止时间是16ms，估计计算时间为2.5ms采用上述三种调度算法，当前时间应选择哪个进程运行？,12ms,A,B进程就绪,15ms,A进程截止,16ms,B进程截止,多处理器调度与调度算法,多处理器系统：松散耦合多处理器系统紧密耦合多处理器系统同步粒度：是指进程之间同步的频率可分为：细粒度（指令）中粒度（线程）粗粒度（进程）超粗粒度（网络分布系统）独立,多处理器调度与调度算法,多处理器调度
29、设计的要点：为进程分配处理器在主从方式、对等方式和混合方式之间选择？在单个处理器上支持多道程序设计是否需要支持多道程序并发执行？如何指派进程如何进行低级调度？,多处理器调度与调度算法,进程调度算法不是关注的重点多处理器调度主要是线程调度几个典型的调度算法负载共享调度算法群调度算法处理器专派调度算法动态调度算法,负载共享调度算法,基本思想：进程并不分配给一个特定的处理器，系统维护一个全局的就绪线程队列，当某个处理器空闲时，就选择一个就绪线程占有处理器运行。,CPU1,CPU2,CPU1,全局就绪线程队列,负载共享调度算法,优点：把负载均匀分派到所有可用的处理器，保证了处理器的高效率不需要一个集中
30、的调度程序运行进程的选择可以采用各种可行的策略先来先服务、最少线程数优先、有剥夺的最少线程数优先缺点：就绪线程队列必须互斥访问，可能成为性能瓶颈被抢占的线程很难在同一个处理器恢复执行，处理器高速缓存的恢复带来性能的下降线程间没有优先级差别,群调度算法,基本思想：把一组进程在同一时间一次性调度到一组处理器上运行。优点：当紧密相关的进程同时执行时，同步造成的等待将减少，进程切换也相应减少，提高系统运行效率由于是一次调度一组进程，调度的代价减少,处理器专派调度算法,基本思想：给一个应用专门指派一组处理器，一旦一个应用被调度，它的每个线程被分配一个处理器并一直占有该处理器，直到整个应用运行结束。特点：仅考虑单个应用的执行效率，不考虑处理器的利用率,动态调度算法,基本思想：由操作系统和应用进程共同完成调度。操作系统负责在应用进程间划分处理器，应用进程自主决定其内部线程的执行情况,
