处理机管理.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,兰州理工大学计算机与通信学院,*,单击此处编辑母版标题样式,操作系统原理,Principle,of,Operating System,第二章 处理器管理,2.1,中央处理器,2.2,进程及其实现,2.3,处理器调度,2.4,批处理作业的管理与调度,2.5,低级调度,兰州理工大学计算机与通信学院,2.1,中央处理器,单处理器系统和多处理器系统,寄存器,特权指令与非特权指令,处理器状态,程序状态字寄存器,兰州理工大学计算机与通信学院,单处理器和多处理器系统,单处理器系统：一个计算机系统,只包括一个运算处理器。,多处理器系统：一个计算机系统有多个运算处理器。,兰州理工大学计算机与通信学院,寄存器,计算机系统的处理器包括一组寄存,器，其个数根据机型的不同而不同，,它们构成了一级存储，比主存容量,小，但访问速度快。,这组寄存器所存储的信息与程序的,执行有很大关系，构成了处理器现场。,兰州理工大学计算机与通信学院,寄存器类型,通用寄存器,数据寄存器,基地址寄存器,I/O,地址寄存器,I/O,缓冲寄存器,控制寄存器,兰州理工大学计算机与通信学院,特权指令与非特权指令,机器指令的集合称指令系统,(1),数据处理类指令；,(2),转移类指令；,(3),数据传送类指令；,(4),移位与字符串指令；,(5)I/O,类指令。,兰州理工大学计算机与通信学院,从资源管理和控制程序执行的角度出,发，把指令系统中的指令分作两部分：,特权指令,和,非特权指令,。,特权指令是指只能提供给操作系统的核,心程序使用的指令，如启动,I/O,设备、设,置时钟、控制中断屏蔽位、清内存、建立,存储键，加载,PSW,等。,兰州理工大学计算机与通信学院,处理器状态,中央处理器怎么知道当前是操作系统还是一般用户程序在运行呢,?,处理器状态标志和设置处理器成不同状态,:,管理状态（特权状态、系统模式、特态或管态）和用户状态（目标状态、用户模式、常态或目态,),兰州理工大学计算机与通信学院,程序状态字寄存器,通常操作系统都引入程序状态字,PSW,（,Program Status Word,）,来区别不同的处理器工作状态,PSW,用来控制指令执行顺序并保留和指示与程序有关的系统状态，主要作用是实现程序状态的保护和恢复。每个程序都有一个与其执行相关的,PSW,，,每个处理器都设置一个,PSW,寄存器。,兰州理工大学计算机与通信学院,PSW,寄存器包括以下内容：,程序基本状态：,程序计数器、条件码、处理器状态位。,中断码。保存程序执行时当前发生的中断事件。,中断屏蔽位。指明程序执行中发生中断事件时，是否响应出现的中断事件。,兰州理工大学计算机与通信学院,2.2,进程及其实现,进程的定义和属性,进程的状态和转换,进程的描述,进程的控制,兰州理工大学计算机与通信学院,进程的定义和属性,进程是一个可并发执行的具有独立功能的程,序关于某个数据集合的一次执行过程，也是操,作系统进行资源分配和保护的基本单位。,进程是一个既能用来共享资源，又能描述程,序并发执行过程的一个基本单位。,兰州理工大学计算机与通信学院,进程的属性：,（,1,）结构性,（,2,）共享性,（,3,）动态性,（,4,）独立性,（,5,）制约性,（,6,）并发性,兰州理工大学计算机与通信学院,进程的状态和转换,运行态,就绪态,等待态,选中,落选,出现等待事件,等待事件结束,三态模型,兰州理工大学计算机与通信学院,运行态,就绪态,等待态,选中,落选,出现等待,事件,等待事件,结束,新建态,终止态五态模型,兰州理工大学计算机与通信学院,具有挂起功能的进程状态及其转换,挂起,等待事件结束,出现等待事件,解除挂起,挂起,落选,选中,运行态,就绪态,等待事件结束,终止态,新建态,挂起就,绪态,解除挂起,挂起,挂起等,待态,等待态,提交,提交,七态模型,兰州理工大学计算机与通信学院,进程的描述,操作系统核心控制结构是进程结构,资源管理的数据结构将围绕进程结构展开。,操作系统的控制表分为四类：,进程控制表、存储控制表、,I/O,控制表和文件控制表。,兰州理工大学计算机与通信学院,进程上下文组成,（,1,）用户级上下文：由用户程序块、用户数据,块和用户堆栈组成的进程地址空间。,（,2,）系统级上下文：包括进程的标识信息、现,场信息和控制信息，进程环境块及系统堆栈等,组成的进程地址空间。,（,3,）寄存器上下文：由,PSW,寄存器和各类控制,寄存器、地址寄存器、通用寄存器组成。,兰州理工大学计算机与通信学院,进程控制块,进程控制,块,P C B,，,是操作系统用于记录,和刻划进程状态及有关信息的数据结构。也是,操作系统掌握进程的唯一资料结构，它包括了,进程执行时的情况，以及进程让出处理器后所,处的状态、断点等信息。,进程控制块包含三类信息：标识信息、,现场信息、控制信息,兰州理工大学计算机与通信学院,进程管理,处于同一状态的所有,PCB,链接在一起的数,据结构称为进程队列,(Process Queues),。,同一状态进程,的,PCB,既可按先来先到的原,则排成队列,;,也可按优先数或其它原则排成队列。,进程控制块可采用表格法和链接法（包括单,向链接和双向链接）组织。,兰州理工大学计算机与通信学院,队列管理和状态转换示意图,处理器,指派,提交,完成,超时,事件,1,等待队列,事件,2,等待队列,事件,n,等待队列,就绪队列,等待事件,1,等待事件,2,等待事件,n,事件,1,出现,事件,2,出现,事件,n,出现,兰州理工大学计算机与通信学院,进程的控制,进程的控制包括：创建进程、阻塞进程、唤,醒进程、挂起进程、激活进程、终止进程和撤销,进程等。这些控制和管理功能由操作系统中的原,语实现。,原语和机器指令类似，其特点是执行过程中,不允许被中断，是一个不可分割的基本单位，原,语的执行是顺序的而不能是并发的。,兰州理工大学计算机与通信学院,2.3,处理机调度,处理机调度的层次,选择调度算法的原则,兰州理工大学计算机与通信学院,中级调度,新建态,挂起就,绪态,挂起等,待态,高级调度,低级调度,运行态,就绪态,等待态,终止态,处理器调度的层次,兰州理工大学计算机与通信学院,处理器调度与进程状态转换,高级调度,中级调度,低级调度,运行态,就绪态,终止态,新建态,挂起就绪态,中级调度,挂起等待态,等待态,高级调度,高级调度,中级调度,兰州理工大学计算机与通信学院,选择调度算法的原则,l,资源利用率,CPU,利用率,=CPU,有效工作时间,/CPU,总的运行时间,CPU,总的运行时间,=CPU,有效工作时间,+CPU,空闲等待时间。,兰州理工大学计算机与通信学院,2,响应时间,交互式进程从提交一个请求,(,命令,),到接收到响应之间的时间间隔称响应时间。,使交互式用户的响应时间尽可能短，或尽快处理实时任务。,这是分时系统和实时系统衡量调度性能的一个重要指标。,兰州理工大学计算机与通信学院,3,周转时间,批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。,这是批处理系统衡量调度性能的一个重要指标。,兰州理工大学计算机与通信学院,4,吞吐率,单位时间内处理的作业数。,5,公平性,确保每个用户每个进程获得合理的,CPU,份额或其他资源份额，不会出现饿死情况。,兰州理工大学计算机与通信学院,作业周转与平均周转时间,如果作业,i,提交给系统的时刻是,t,s,，,完成时刻是,t,f,，,该作业的周转时间,t,i,为：,t,i,=,t,f,-,t,s,实际上，它是作业在系统里的等待时间与运行时间之和。,为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。,平均作业周转时间,T=(,t,i,)/n,兰州理工大学计算机与通信学院,作业带权周转时间和平均作业带权周转时间,如果作业,i,的周转时间为,t,i,，,所需运行时间为,t,k,，,则称,w,i,=,t,i,/,t,k,为该作业的带权周转时间。,t,i,是等待时间与运行时间之和，故带权周转时间总大于,1,。,平均作业带权周转时间,W=(,w,i,)/n,兰州理工大学计算机与通信学院,2,.4,批处理作业的管理与调度,作业和进程的关系,批处理作业的管理,批处理作业的调度,作业调度算法,兰州理工大学计算机与通信学院,作业和进程的关系,作业,(JOB),和作业步,(Job Step),作业是任务实体，进程是完成任务的执行实体,;,没有作业任务，进程无事可干，没有进程，作业任务,没法完成。,作业概念更多地用在批处理操作系统，而进程则,可以用在各种多道程序设计系统。,兰州理工大学计算机与通信学院,批处理作业的管理,作业控制块,多道批处理操作系统具有独立的作业管理模块，必须,像进程管理一样为每一个作业建立作业控制,块（,JCB,）。,JCB,通常是在批作业进入系统,时，由,Spooling,系统建,立的，它是作业存在于系统的标志，作业撤离,时,，,JCB,也被撤销。,JCB,的主要内容包括：作业情况,资源需求,资源使,用情况。,兰州理工大学计算机与通信学院,作业生命周期状态,输入状态,：此时作业的信息正在从输入设备上预输入。,后备状态,：此时作业预输入结束但尚未被选中执行。,执行状态,：作业已经被选中并构成进程去竞争处理器资源以获得运行。,完成状态,：作业已经运行结束，正在等待缓输出。,兰州理工大学计算机与通信学院,批处理作业的调度,处于后备状态的作业在系统资源满足的前提下可以被作业调度选中进入内存计算。而只有处于执行状态的作业才真正构成进程获得计算的机会。,作业调度选中一个作业且把它装入主存储器时就为该作业创建一个用户进程。这些进程将在进程调度的控制下占有处理器运行。,为了充分利用处理器，可以把多个作业同时装入主存储器，这样就会同时有多个用户进程，这些进程都要竞争处理器。,兰州理工大学计算机与通信学院,作业调度算法,1,先来先服务算法（,FCFS,）,按照作业进入系统的先后次序来挑选作业，,先进入系统的作业优先被挑选。,算法容易实现，效率不高，只顾及作业等候,时间，没考虑作业要求服务时间的长短。不利于,短作业而优待了长作业。,兰州理工大学计算机与通信学院,2,最短作业优先算法（,SJF,）,SJF,算法以进入系统的作业所要求,的,CPU,时间为标准，总选取估计计算时间最短的作业投入运行。,算法易于实现，效率不高，主要弱点是忽视了作业等待时间，会出现饥饿现象。,SJF,的平均作业周转时间比,FCFS,要小，故它的调度性能比,FCFS,好。,实现,SJF,调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。,兰州理工大学计算机与通信学院,3,响应比最高者优先算法,(HRRF),作业进入系统后的等待时间与估计,运行时间之比称作响应比，现定义；,响应比,1+,已等待时间,/,估计运行时间,短作业容易得到较高响应比，长作,业等待时间足够长后，也将获得足够高,的响应比，饥饿现象不会发生。,兰州理工大学计算机与通信学院,HRRF,算法举例,四个作业到达系统时间,/,所需,CPU,时间,:,作业,1-0/20,，,作业,2-5/15,，作业,3-10/5,，作业,4-15/10,。,(1)SJF,调度顺序为作业,1,、,3,、,4,、,2,，平均作业周转时间,T=25,，,平均带权作业周转时间,W=2.25,。,(2)FCFS,调度顺序为作业,1,、,3,4,、,2,，平均作业周转时间,T=28.75,，,平均带权作业周转时间,W=3.125,。,(3)HRRF,调度顺序为作业,1,、,3,、,4,、,2,，平均作业周转时间,T=26.25,，,平均带权作业周转时间,W=2.46,。,兰州理工大学计算机与通信学院,4,优先数法,这种算法是根据确定的优先数来选取作,业，每次总是选择优先数高的作业。,规定用户作业优先数的方法：,(1),一种是由用户自己提出作业的优先数。,(2),另一种是由系统综合考虑有关因素来,确定用户作业的优先数,。,兰州理工大学计算机与通信学院,5,分类调度算法,预先按一定原则把作业划分成若干类，以达,到均衡使用系统资源和兼顾大小作业的目的。,分类原则包括作业计算时间、对内存的需,求、对外围设备的需求等。作业调度时还可为每,类作业设置优先级，从而照顾到同类作业中的轻,重缓急。,兰州理工大学计算机与通信学院,6,用与不用磁带的作业搭配,作业调度时，把使用磁带机和不使用磁,带机的作业搭配挑选。,可使要用磁带机的作业在执行时省去等,待装磁带的时间。显然对缩短系统的平均周,转时间是有益的。,兰州理工大学计算机与通信学院,2.5,低级调度,低级调度的功能,低级调度算法,兰州理工大学计算机与通信学院,低级调度的功能,低级调度负责动态地把处理器分配,给进程或内核级线程。操作系统中实现,低级调度的程序称为进程,(,线程,),调度程,序，或分派程序,(Dispatcher),。,进程调,度算法多数适用于线程调度。,兰州理工大学计算机与通信学院,低级调度基本功能,:,(1),记住进程的状态。,(2),决定某个进程什么时候获得处理器，,以及占用多长时间。,(3),把处理器分配给进程。,(4),收回处理器。,低级调度基本方式：,非抢占式、抢占式、,折衷方式,兰州理工大学计算机与通信学院,低级调度算法,1,先来先服务算法,2,时间片轮转调度算法,可防止那些很少使用外围设备的进程过长的占用处理器,而使得要使用外围设备的那些进程没有机会去启动外围设备。,3,优先权调度,（静态优先数法动态优先数法）,4,多级反馈队列调度,兰州理工大学计算机与通信学院,低级就绪队列,高级就绪队列,中级就绪队列,等待磁,盘磁带,等待其,他外设,运行,选中,时间片,500ms,超过时间片,启动磁盘,磁带,启动其他,外设,选中,时间片,200ms,选中,时间片,100ms,一个三级反馈队列调度策略,兰州理工大学计算机与通信学院,5,保证调度算法,向用户做出明确的性能保证，然后去实现它。,容易实现的一种保证是：当工作时己有,n,个用,户登录在系统，则将获得,CPU,处理能力的,1/n,。,类似的，如果在一个有,n,个进程运行的用户系统,中，每个进程将获得,CPU,处理能力的,1/n,。,兰州理工大学计算机与通信学院,6,彩票调度算法,基本思想：,为进程发放针对各种资源（如,CPU,时间）的彩票。调度程序随机选择一张彩票，,持有该彩票的进程获得系统资源。,进程都是平等的，有相同的运行机会。如果,某些进程需要更多的机会，可被给予更多彩,票，增加其中奖机会。,兰州理工大学计算机与通信学院,谢谢,!,兰州理工大学计算机与通信学院,