资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,a,1,第二章 进程管理,a,2,2.1,进程的引入,a,3,2.1.1,程序顺序执行与并发执行,程序的执行顺序,1,程序的顺序执行,例子：,S1,：,a,：,x+y,；,S2,：,b,：,a-5,；,S3,：,c,：,b+1,；,a,4,2,程序顺序执行时的特征,（,1,）顺序性,：处理机的操作严格按照程序所规定的顺序执行。,（,2,）封闭性,：程序运行时独占全机资源，程序一旦开始执行，其执行结果不受外界因素影响。,（,3,）可再现性,：只要程序执行时的环境和初始条件相同，都将获得相同的结果。,（不论它是从头到尾不停顿地执行，还是,“,停停走走,”,地执行）,a,5,3.,程序的,并发,执行,a,6,4.,程序并发执行时的特征,1,）间断性,:,由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。相互制约将导致并发程序具有“执行,暂停,执行”这种间断性的活动规律。,2,）失去封闭性,:,是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。,3,）不可再现性,:,程序在并发执行时，由于失去了封闭性，导致不可再现性 。,a,7,例如，有两个循环程序,A,和已它们共享一个变量,N,。程序,A,每执行一次时，都要做,N,：,=N,1,操作；程序,B,每执行一次时，都要执行,Print,（,N,）操作，然后再将,N,置成“,0”,。程序,A,和,B,以不同的速度运行。这样，可能出现其计算结果不可再现性，亦即，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。,a,8,例子：变量,X,为共享变量，程序,1,和程序,2,都要对,X,进行访问，当两个程序执行的速度变化时可得到不同的结果。,执行顺序,1,：程序,1,程序,2,结果为：,X,增加,2,。,执行顺序,2,：,R1=X; R2=X; R1=R1+1; R2=R2+1; X=R1; X=R2,结果为：,X,增加,1,。,还可有许多其它组合,程序,2,R2=X,R2=R2+1,X=R2,程序,1,R1=X,R1=R1+1,X=R1,目 标 程 序,a,9,并发执行的条件：达到封闭性和可再现性,并发执行失去封闭性的原因是共享资源的影,响，去掉这种影响就行了。,1966,年，由,Bernstein,给出并发执行的条件,。,程序,P(i),针对,共享变量,的读集和写集,R(i),和,W(i),条件：任意两个程序,P(i),和,P(j),，有：,R(i),W(j)=,; W(i),R(j)=,; W(i),W(j)=,;,前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。,现在的问题是这个条件不好检查。,a,10,并发和并行区别,并发是指在某一时间间隔内计算机系统中存在着多个程序活动。,并行是指在同一时刻计算机内有多个程序都在执行，这只有在多,CPU,的系统中才能实现。在单,CPU,的计算机系统中，多个程序是不可能同时执行的。并发是从宏观上（这种“宏观”也许不到一秒的时间）看多个程序的运行活动，这些程序在串行的、交错的运行，由操作系统负责这些程序之间的运行切换，人们从外部宏观上观察，有多个程序都在系统中运行。,a,11,2.1.2,进程的概念和特征,1,、进程的定义,进程是一个具有一定,独立,功能的程序关于某个数据集合的一次,运行,活动，是系统进行资源分配和调度的基本单位,。,a,12,进程与程序的区别和相互关系,程序 进程,静态的指令序列,动态的程序执行过程,一程序可对应,一个进程对应至少有,多个进程 一个程序在工作,永久性软件资源,暂存资源,动态产生过程,资源分配和调度的单位,a,13,2,、进程的特征,动态性,：,进程,是程序在并发系统内的一次执行，一个进程有一个从产生到消失的,生命期，,是进程的最基本的特征；,并发性,：,正是为了描述程序在并发系统内执行的动态特性才引入了,进程,，没有并发就没有,进程,，是进程的最重要的特征，正是因为并发性，才提高了系统资源的利用率和系统的吞吐量；,独立性,：,每个,进程,的程序都是相对独立的顺序程序，可以按照自己的方向和速度独立地向前推进；,异步性,：,指,进程,的执行进度，或推进速度不可预测，而与同时驻留在内存的其它进程有关；,制约性,：,进程,之间的相互制约，主要表现在互斥地使用资源和相关,进程,之间必要的同步和通讯；,结构性,：,进程,=,PCB +,程序,+,数据集合,a,14,3,、引入进程后需要解决的问题,*增加了空间开销,*额外的时间开销,*更难控制,*处理机的竞争尤为突出,a,15,2.1.3,进程的结构,为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块（,PCB,）组成。,进程控制块是操作系统感知进程存在的唯一标志,。,程序部分描述进程本身所要完成的功能，而“私有数据块”是接受程序规定操作的一组存储单元的内容，是操作的对象。进程控制块是在进程创建时产生的，当进程存在于系统时（运行），进程控制块就标识了这个进程。,a,16,PCB,包含了进程的描述信息和控制信息，通常有如下项目：,(1),标识符,(2),存贮信息,(3),现场状态,(4),优先数,(5),现场信息,(6),链接字,(,或称队列指针,),(7),族系关系,(8),资源清单,(9),其他,a,17,*,标识符,分为外部标识符和内部标识符。外部标识符由创建进程者提供，通常由字母、数字等组成，在用户或其它进程访问该进程时使用。内部标识符是一个整数。在操作系统的,PCB,表区中，有多个,PCB,表，每个,PCB,表有一个序号，通常将这个序号做为内部标识符，以方便系统使用。,* 程序地址,进程的程序部分在内存及外存的地址，或描述程序地址信息的段表地址、页表地址等。,a,18,*,数据地址,进程的数据部分在内存及外存的地址，或描述数据地址信息的段表地址、页表地址等。,* 状态,进程当前所处的状态，即就绪状态、执行状态及阻塞状态，已经被创建的进程的状态必为此三者之一。,a,19,* CPU,状态保护区,CPU,状态信息主要由通用寄存器、程序计数器,PC,、程序状态字,PSW,以及用户栈指针等组成，也称为中断点现场信息。,CPU,状态保护区用以保护进程被中断而暂停执行时,CPU,的状态信息，以便进程重新获得,CPU,时能够重布现场，从上次被中断处继续执行。,a,20,*,进程优先级,进程优先级是用以描述进程使用处理机的优先级别的整数，是优先级调度算法中调度的依据。通常数值越小，优先级别越高。优先级可以处理成不变的，称为静态优先级，也可以处理成可变的，称为动态优先级。,a,21,*,通信信息,进程通信时需要使用的信息，包括标志位、信号或信号量、消息队列信息等。如消息缓冲通信机制中，在进程的,PCB,表中，需要有消息队列队首指针、消息个数及互斥使用消息队列的信号量等。,a,22,*,资源信息,进程对资源的需求及已经分配资源的清单。,* 队列指针,除了执行状态的进程外，其余的进程,PCB,表都处于某一就绪队列或某一阻塞队列中。队列指针用于指向进程所在队列中下一个,PCB,表的首地址。,a,23,*,家族指针,进程在运行过程中可以创建新进程来协同完成同一任务。创建者称为父进程，被创建者称为子进程。父进程,PCB,表中有指向子进程的,PCB,表的指针，子进程的,PCB,表中有指向父进程的,PCB,表的指针，这就是家族指针，它可以将一个家族的进程联系起来，形成进程家族树。,a,24,进程控制块的组织,为了便于管理，系统把所有的,PCB,用适当方式组织起来。一般说来，大致有以下三种组织方式：,(1),线性表方式,(2),索引方式,(3),链接方式,a,25,a,26,a,27,2.2,进程的状态,a,28,2.2.1,进程执行轨迹,例,假设内存中有,3,个进程,A,、,B,、,C,，他们的程序代码已全部装入内存。若,A,、,C,两进程需要执行,12,条指令，,B,进程需要执行,4,条指令，且,B,进程执行到第,4,条指令处必须等待,I/O,a,29,a,30,a,31,2.2.2,两状态进程模型,在两状态模型中进程可能处于如下两种状态中：,执行,(Running,）,非执行（,Not-running,）,a,32,两状态队列模型,a,33,进程的创建,事 件,说 明,新的批作业,通常位于磁带或磁盘中的批作业控制流被提供给操作系统。当操作系统准备接纳新工作时。它将读取下一个作业控制命令,交互登录,终端用户登录到系统,操作系统因为提供一项服务而创建,操作系统可以创建一个进程，代表用户程序执行一个功能，使用户无需等待（如控制打印的进程）,由现有的进程生成,基于模块化的考虑，或者为了开发并行性，用户程序可以规定许多进程的创建,a,34,进程的终止,事件,说明,正常完成,进程自行执行一个操作系统服务调用，表示它已经结束运行,超过时限,进程运行时间超过规定的时限。可以测量很多种类型的时间，包括总的运行时间（“挂钟时间”）。花费在执行上的时间以及对于交互进程从上一次用户输入到当前时刻的时间总量,无可用存储器,系统无法满足进程需要的存储器空间,越界,进程试图访问不允许访问的存储器单元,保护错误,进程试图使用不允许使用的资源或文件，或者试图以一种不正确的方式使用，如往只读文件中写,算术错误,进程试图进行被禁止的计算，如除以零或者存储器大于硬件可以接纳的数字,a,35,接上表,事件,说明,时间超出,进程等待某一事件发生的时间超过了规定的最大值,I/O,失败,在输入或输出期间发生错误，如找不到文件、在超过规定的最多努力次数后仍然读写失败（例如当遇到了磁带上的一个坏区时）或者无效操作（如从行式打印机中读）,无效指令,进程试图执行一个不存在的指令（通常是由于转移到了数据区并企图执行数据）,特权指令,进程试图使用为操作系统保留的指令,数据误用,错误类型或未初始化的一块数据,操作员或操作系统干涉,由于某些原因，操作员或操作系统终止进程（例如，如果存在死锁）,父进程终止,当父进程终止时，操作系统可能会自动终止该进程的所有后代进程,父进程请求,父进程通常具有终止其任何后代进程的权力,a,36,导致进程状态转换的事件,2.2.3,五状态进程模型,a,37,Running,：,占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机）,Ready,：,准备执行,Blocked,：,等待某事件发生才能执行，如等待,I/O,完成等,New,：,进程已经创建，但未被,OS,接纳为可执行进程，并且程序还在辅存，,PCB,在内存,Exit,：,因停止或取消，被,OS,从执行状态释放,a,38,Null New,：新创建进程首先处于新状态,事 件,说 明,新的批作业,通常位于磁带或磁盘中的批作业控制流被提供给操作系统。当操作系统准备接纳新工作时。它将读取下一个作业控制命令,交互登录,终端用户登录到系统,操作系统因为提供一项服务而创建,操作系统可以创建一个进程，代表用户程序执行一个功能，使用户无需等待（如控制打印的进程）,由现有的进程生成,基于模块化的考虑，或者为了开发并行性，用户程序可以规定许多进程的创建,a,39,NewReady,：,OS,接纳新状态进程为就绪进程,Ready Running,：,OS,只能从就绪进程中选一个进程执行,Running Exit,：执行状态的进程执行完毕，或被取消，则转换为退出状态,RunningReady,：分时系统中，时间片用完，或优先级高的进程到来，将终止优先级低的进程的执行,Running Blocked,：执行进程需要等待某事件发生。通常因进程需要的系统调用不能立即完成，而阻塞,a,40,Blocked Ready,：当阻塞进程等待的事件发生，就转换为就绪状态,Ready Exit,：,某些系统允许父进程在任何情况下终止其子进程。若一个父进程终止，其子孙进程都必须终止。,Blocked Exit,：因为它自身退出了，或者是因为某种原因被取消。,a,41,a,42,Using Two Queues,a,43,a,44,2.2.4,进程的挂起状态,这个问题的出现是由于进程优先级的引入，一些低优先级进程可能,等待较长时间,，从而被,对换至外存,。这样做的目的是：,提高处理机效率,：,就绪进程表为空,时，要提交新进程，以提高处理机效率；,为运行进程,提供足够内存,：资源紧张时，暂停某些进程，如：,CPU,繁忙（或实时任务执行），内存紧张；,被挂起进程的原因,a,45,用于,调试,：在调试时，挂起,被调试进程,（从而对其地址空间进行读写）；,操作系统的需要：操作系统可能挂起,后台进程,或一些,服务进程，或,某些可能,导致系统故障的进程,；,父进程的需求：父进程可能挂起子进程。,a,46,被挂起进程的特征,不能被调度执行。,可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能执行。,为了阻止进程执行，可以通过代理使进程挂起。代理可以是进程自身或父进程、或,OS,。,只有实施挂起操作的进程才能使之由挂起状态转换为其他状态。,a,47,One Suspend State,一个挂起,a,48,Two Suspend States,a,49,具有挂起状态的进程状态转换,BlockedBlocked/Suspend,：,OS,通常将阻塞进程换出，以腾出内存空间,Blocked/SuspendReady/Suspend,:,当,Blocked/Suspend,进程等待的事件发生时，可以将其转换为,Ready/suspend,Ready/SuspendReady,：,OS,需要调入一个进程执行时,ReadyReady/Suspend,：挂起就绪进程，释放足够的内存空间,New Ready/suspend,（,New,Ready,）,：,新进程创建后，可以插入到就绪队列或,Ready/suspend,队列。若无足够的内存分配给新进程，则需要,New Ready/Suspend,a,50,具有挂起状态的进程状态转换（续）,Blocked/SuspendBlocked,：当,Blocked/Suspend,队列中有一个进程的阻塞事件可能会很快发生，则可将一个,Blocked/Suspend,进程换入内存，变为,Blocked,RunningReady/Suspend,：当执行进程的时间片用完时，会转换为,Ready,。或，一个高优先级的,Blocked/Suspend,进程正好变为非阻塞状态，,OS,可以将执行进程转换为,Ready/Suspend,状态,AllExit,：,通常，,Running Exit,。但某些,OS,中，父进程可以终止其子进程，使任何状态的进程都可转换为退出状态,a,51,2.3,进程的控制,a,52,2.3.1,执行模式,处理机有核心态和用户态两种执行状态,核心态,：由设备中断、异常、自陷、信号（即软中断）等进入，这种状态具有较高的特权，允许使用全部机器资源与机器指令，是操作系统程序执行时的状态。,用户态,：处理机在这种状态下只能使用指定的机器指令，不能使用如,I/O,、改变机器状态、修改存储保护等指令，并且只允许访问用户自己的存储区，是用户程序执行时的状态。,a,53,2.3.2,操作系统内核,没有配置任何软件的计算机称为裸机，操作系统是在裸机上添加多层软件形成的。通常将与硬件紧密相关的部分，如中断处理程序、设备驱动程序及进程从创建到撤消包括进程状态变迁中用到的公共操作等集中在一起，常驻内存，作为裸机上添加的第一层软件，叫做,内核,。,a,54,操作系统内核的功能,运行频率高的功能模块大都放在操作系统的内核来实现。,1,、资源管理的功能,*,进程管理,进程的创建和终止、进程调度、进程状态转换、进程之间的同步和通信、以及,PCB,管理等等。,*,存储管理,为进程分配空间、实现内存保护和对换功能、对内存进行分段和分页管理的等等。,*,I/O,设备管理,I/O,缓冲区管理、为进程分配,I/O,通道和设备等等,a,55,2,、支持功能,*,I/O,中断处理,中断 处理功能既是内核的最基本功能，也是整个操作系统赖以活动的基础，即操作系统的一切重要活动都最终依赖于中断。,*,原语操作,操作系统内核的功能大都通过执行各种原语来实现的。,a,56,原语：是机器指令的延伸，是由若干条机器指令构成的、完成特定功能的一个过程。,原子操作：指一个操作中的所有动作，要么全做，要么全不做，即原子操作是一个不可分割的操作。,在单处理机中，操作的原子性可以通过屏蔽中断来实现。,时钟管理,时钟就是操作系统运行的脉搏。,a,57,2.3.3,进程控制,1,、进程的创建和撤消,进程的创建,a,58,进程的撤消,a,59,2,、进程的阻塞和唤醒,阻塞是进程自己通过调用阻塞原语自己阻塞自己，而唤醒操作则由操作系统或其它相关进程调用唤醒原语来唤醒，进程自己无法自己唤醒自己。,进程阻塞的原因：,* 进程请求,I/O,服务，无论获得,I/O,服务与否，通常都要暂时放弃,CPU,；,* 某些原语操作，如,P,操作等可能引起进程阻塞；,* 某些系统进程工作时占用,CPU,，无事可做时，则调用阻塞原语将自己阻塞。,a,60,进程的阻塞,a,61,进程唤醒的原因：,* 进程请求的,I/O,操作完成；,* 某些原语操作，如,V,操作等可以解封阻塞进程；,* 某些系统进程有事可做时，用唤醒原语将其唤醒。,a,62,进程的唤醒,a,63,3,、进程的挂起与激活,根据进程所处状态，挂起原语可以有三种处理：,* 完成进程从活动就绪状态到静止就绪状态的转变,;,*,完成进程从活动阻塞状态到静止阻塞状态的转变,;,*,若进程是执行状态，则转变为静止就绪状态。,a,64,挂起对象,：,* 进程请求挂起自身；,* 父进程挂起子进程。,挂起方式如下,：,* 挂起一个具有指定标识符的进程；,* 挂起某个进程及其所有子孙进程。采用这种挂起方式可以避免进程被挂起而其子孙进程仍在活动而带来的问题。,a,65,进程挂起,a,66,进程的激活,a,67,4,、进程切换,进程切换的大致的两个步骤：,* 保护被切换进程的现场；,* 恢复投入运行的现场。,a,68,2.4,进程调度,a,69,2.4.1,进程调度的目标、原则和方式,1.,交通控制程序,交通控制程序,(Traffic Controller),是,J.H.Saltzer,于,1966,年起的名字。他把操作系统中指挥各个进程的工作比作一个交通警察， 而把各个进程比作车辆。 它们之间有时要竞争，有时要合作， 交通警察就要保证它们协调一致，互不冲突。在操作系统中，交通控制程序的主要职能是管理进程状态之间的转变和协调进程间的通讯。,a,70,2.,进程调度程序,在进程状态的变化中，从就绪到运行的转变是由一个专门的程序来完成的，该程序称为进程调度程序。进程调度称为“低级”调度，是相对作业调度而言的。进程调度程序所要完成的是把一台物理的,CPU,转变为多台虚拟的,CPU,或者多台逻辑的,CPU,。,a,71,3.,引起进程调度的原因,* 现运行进程运行结束或者因任务完成而正常结束，或者因出现错误而异常结束。,* 现运行进程因某种原因，比如,I/O,请求，从运行进入阻塞状态。,* 现运行进程执行某种原语操作，如,P,操作、阻塞原语等，进入阻塞状态。,* 一个具有更高优先级的进程要求使用处理机，即进入就绪队列。,* 分配给该进程运行的时间片已用完。,a,72,4.,进程调度程序的功能,* 记住系统中所有进程的状态、 优先数和资源需求情况。 对于动态优先数，还须按一定算法定期地对它进行计算。,* 确定调度算法，决定把处理机分配给哪个进程和分配多长时间。 某个进程正在运行时，如果有优先级更高的进程进入就绪队列，是继续运行原进程还是分配处理机给优先级更高的进程，由调度方式确定。,* 分配处理机给进程。,a,73,5.,进程调度方式,所谓进程调度方式，是指当一个进程正在处理机上运行时，若有某个更为紧迫或更为重要的进程需要进行处理，或者说，如果有更高优先级的进程进入就绪队列时，如何分配处理机。 通常有两种进程调度方式：,a,74,通常有两种进程调度方式：,*,非剥夺方式,进程一旦获得,CPU,就一直执行，直到完成或发生某事件（如请求,I/O,服务、,P,操作等）而阻塞，其它的进程方可运行。这种调度方式简单，容易实现，但是一个进程的运行往往可能导致多数进程长期得不到服务，所以非抢占方式不适宜有多个竞争用户的通用系统。,*,剥夺方式,允许在逻辑上可执行的进程暂时放弃,CPU,。抢占方式的调度策略（如时间片轮转、优先级等）允许非执行进程在满足某种条件时抢占执行进程所占用的,CPU,。,a,75,6.,进程调度的目标,进程调度要满足两个方面的目标：,*,满足用户的需求,-,交互式用户对响应时间的要求；,-,批处理系统用户对作业周转时间的要求；,-,实时系统对任务截止时间的要求。,*,满足系统的需求,-,系统吞吐量；,-,处理机利用率；,-,各类资源的平衡使用；,-,公平性；,-,优先级。,a,76,7.,进程调度原则,A .,面向用户的原则,*,响应时间,响应时间,：是指从用户通过键盘提交一个请求开始，直到系统首次产生响应为止的时间。常用于评价分时系统的性能。,响应时间包括,3,个部分时间的总和：,（,1,）从键盘输入的请求信息传送到处理机的时间；,（,2,）处理机对请求信息进行处理的时间；,（,3,）将响应结果发送到输出终端的时间。,a,77,*,周转时间,周转时间,：指从作业提交给系统开始，到作业完成为止的这段时间间隔，也叫作业周转时间。常用于批处理系统的性能。,周转时间包括,4,个部分时间的总和：,（,1,）作业在外存排队等待调度的时间；,（,2,）进程在就绪队列中等待调度的时间（可能多次等待）；,（,3,）进程被处理机执行的时间。,（,4,）等待,I/O,操作完成的时间。,a,78,*,截止时间,截止时间,：指实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间。常用于评价实时系统的性能。,a,79,B .,面向系统的原则,*,系统吞吐量,系统吞吐量,：指单位时间内系统所完成的作业数。常用于评价批处理系统的性能。,*,处理机利用率,处理机利用率,：指处理机被使用的频率。对于衡量大中型机的多用户系统是一个重要的指标。对于但用户微机或某些实时系统，则并非很重要。,a,80,*,各种资源的平衡使用,多道程序系统的目标之一就是提高系统资源的利用率，因此，调度算法有责任是系统中的各种资源都尽量处于忙碌状态。该原则同时适合中级调度和高级调度。,* 公平性,调度算法应该对所有进程公平，而不偏袒任何进程。,a,81,*,优先权,优先权是调度算法需要考虑的一个重要因素。优先权高的进程应该优先调度。,确定优先权的高低的方式：,* 静态优先权,* 动态优先权,a,82,2.4.2,进程调度的类型,按照算法所运行的系统类型，可以分为：,* 批处理调度,* 分时调度,* 实时调度,* 多处理机调度,a,83,按照调度的层次，可以分为：,* 高级调度（长程调度）,* 低级调度（短程调度）,* 中级调度（中程调度）,a,84,*,高级调度,即作业调度或宏观调度。其任务是对那些提交给系统后被收容的作业,按照一定策略选择出某些作业,为其分配内存等必要的资源,建立与之对应的进程,并将进程的,PCB,表放入就绪队列中,使其具备参与竞争使用,CPU,的权利。,作业调度,a,85,高级调度要考虑的两个问题：,* 选择多少个作业进入内存，为之创建进程，,这取决于多道程序度。,* 选择哪些作业，这取决于高级调度算法。,可用的高级调度算法有：,-,先来先服务,-,短作业优先,-,基于优先级调度,-,响应比高者优先,注意,：如果系统不支持作业处理功能，也就,不会有高级调度。,a,86,*,低级调度,即进程调度或微观调度。其任务是在进入内存并处于就绪队列的进程中,确定哪个进程真正获得,CPU,及其使用,CPU,的时间。用执行指针指向选中进程的,PCB,表，将它从就绪队列移出并重布现场，使其运行。现代操作系统都支持低级调度。,进程调度,a,87,*,中级调度,将就绪状态细化为内存就绪和外存就绪状态，阻塞状态细化为内存阻塞和外存阻塞状态后，中级调度完成进程在内存与外存之间的对换。其任务是周期性地将那些在内存中暂时不用的进程换出并放到外存，而将那些在外存上需要运行的进程换入到内存。,中级调度,a,88,处理机的三级调度,a,89,2.4.3,进程调度算法,下面是几项主要的评估标准：,（） 平均周转时间 作业,从提交时刻,is,到完成时刻,ic,所经历的时间称为该作业的周转时间,，即,ic,is,；进程,从进入就绪队列的时刻,ir,到执行完本次周期的时刻,ic,称为该进程的周转时间,i,，即,i,ic,ir,。于是，,个作业的平均周转时间或,个进程的平均周转时间,为：,a,90,（） 平均带权周转时间 作业,的周转时间,T,i,与其实际运行时间,i,之比 称为该作业的带权周转时间，即 ，同样，进程,的周转时间,与其本次周期的时值之比 称为该进程的带权周转时间。于是，,个作业或,个进程的平均带权周转时间,为：,a,91,（）平均等待时间 进程,从进入就绪队列那一时刻,ir,到获得的那一时刻,ip,所经历的时间称为它的等待时间,i,，即,i,ip,ir,，那么,个进程的平均等待时间,为：,通常，,用,来衡量不同调度算法对同一作业流或同一进程集的调度性能，用,来衡量不同进程调度算法对同一进程集的调度性能，而用,来衡量同一调度算法对不同作业流或不同进程集的调度性能,。,a,92,现代操作系统采用了以下几种调度算法：,* 先来先服务（,FCFS,）,在先来先服务算法中，进程到达就绪队列时按先后顺序排队。选择进程去执行时，始终选队首进程。进程获得,CPU,后，直至执行完或发生某等待事件，才释放,CPU,。,a,93,先来先服务算法（,）本质上是非剥夺式的，如果可剥夺，则不能保证原则的实施。,先来先服务算法（,）优点：,实现简单,先来先服务算法（,）缺点：,* 对短进程不公平，使排在队列后面的短进程要等待很长时间，增加整个系统的平均周转时间。,* 不利于,I/O,型进程，未能有效利用系统资源,* 采用非剥夺调度方式，未考虑进程的紧迫程度，不适合分时系统和事务处理系统。,a,94,因此，先来先服务算法（,）算法常常和其它调度算法混合使用，算法适合高级调度、中级调度和低级调度。,a,95,平均周转时间和平均带权周转时间,a,96,考虑三个进程,、,和,，它们的本次周期的时值分别为 、 和 ，且以,、,的次序处于就绪队列中，不妨认为它们进入就绪队列的相对时刻均为。于是，在调度下，其执行过程可表示如下：,P,3,P,2,P,1,0,21,27,30,a,97,、,和,的等待时间分别为、和，周转时间分别为、和，故它们的平均等待时间和平均周转时间分别为：,a,98,*,短进程优先,短进程优先算法,本质上是非剥夺式的，如果可剥夺，则不能保证原则的实施。,短进程优先,算法优点：,降低了平均等待时间，提高了系统的吞吐量。,短进程优先,算法缺点：,* 算法需要预测进程的预期执行时间，当进程还没运行时，很难准确预测进程的执行时间。,* 该算法总是优先调度短进程，有可能导致长进程饥饿，对长进程不公平。,* 采用非剥夺调度方式，未考虑进程的紧迫程度，不适合分时系统和事务处理系统。,a,99,a,100,*,时间片轮转调度法,（ ）算法是一种剥夺式的进程调度算法，它依据公平服务的原则，将时间划分成一个个的时间片（记为,S,），并以,为单位，轮转地为各个就绪进程一次分配一个时间片。常用于分时系统和事务处理系统,时间片轮转调度,算法优点：,* 解决了短进程和长进程的不公平问题；,* 对计算型的进程较有利；,* 满足分时系统用户对响应时间的要求。,a,101,时间片轮转调度,算法缺点：,* 不适合批处理系统的进程调度。,* 不利于,I/O,型的进程。,a,102,时间片轮转调度,算法的时间片选择时注意的问题：,* 不能太短，太短会使进程切换非常频繁，从而降低处理机的效率；,* 不能太长，太长将无法满足交互式用户对响应时间的要求。,因此，时间片大小的设置要综合考虑系统的最大用户数、响应时间的要求和系统效率等多种因素。,a,103,以前述的三个进程为例，考察算法的执行情况及其调度性能。设 ，则有：,P,1,P,1,P,1,P,1,P,2,P,1,P,3,P,2,P,1,0,4,8,11,15,17,21,25,29,30,a,104,进程,首先执行一个时间片并被剥夺，其周期所剩余的 放到以后执行；,执行一个时间片后也被剥夺；,的时值为 ，不足一个时间片。第二轮开始，又由,先执行一个时间片后被剥夺； 这次,只执行 。至此，,和,的周期已先后完成，故随后连续个时间片都分给了,，直至,完成，在最后一个时间片里，,只执行了 。容易算出，该例的平均等待时间和平均周转时间分别为：,a,105,其中，,为系统的响应时间上限，,为系统中的进程数目上限。例如，设, ,，,，则,0.1,。,a,106,*,基于优先级的调度算法,优先级通常是用一个整型数来表示，称为优先数。,对于不同的系统，既可以用较大的数也可以用较小的数来表示较高的优先级，这并无统一的规定。,a,107,优先级的设置考虑的因素：,* 进程完成功能的重要性；,* 进程完成功能的紧迫性；,* 为均衡系统资源的使用，指定,进程（作业）优先级；,* 进程对资源的占有程度。,a,108,确定优先权的高低的方式：,* 静态优先权,在进程运行期间其优先级一直不变，,* 动态优先权,随着进程的运行其优先级要改变，,其变化考虑的典型因素有：,根据进程运行时间的剩余时间的,减少而上升，以使要执行结束,的进程尽快结束；,根据进程在队列等待时间的增加而上,升，以不至于饥饿。,动态确定优先级的时刻一般在每个时钟,中断或需要进程切换时。,a,109,设有五个就绪进程，它们各自的本次周期的长度、初始优先数及进入就绪队列的相对时刻如下所示：,a,110,在非剥夺的静态设置方式下，执行情况如下：,P,4,P,3,P,5,P,1,P,2,0,4,36,52,60,62,在进程,执行完时，,已进入就绪队列，因其优先级较高，故先于,和,之前执行。可算得这些进程的平均等待时间,、平均周转时间,以 及平均带权周转时间,分别为：,a,111,*,剩余时间最短者优先算法,根据进程运行时间的剩余时间最短者优先级最高，以使要执行结束的进程尽快结束。本质上是剥夺型的短进程优先调度算法。剥夺是根据时间片。,a,112,*,响应比高者优先算法,根据进程等待时间和进程的预期执行时间纳入优先级的运算。使进程的优先级与等待时间成正比，与进程执行时间成反比。,响应比：,响应时间需运行时间,（已等待时间需运行时间）需运行时间,已等待时间需运行时间,响应比高者优先算法优点：,是长进程和短进程都得到合理的运行机会。,响应比高者优先算法缺点：,很难估计进程的剩余执行时间。,a,113,*,反馈调度算法,多级反馈队列就是综合了、和的 一种进程调度算法，其基本思想如下：,（）系统按优先级别设置,个就绪进程队列，第一级队列的优先级最高，以下逐级降低，第级队列的优先级最低；,（）每个就绪队列对应有一个时间片,S,i,（,i,，,2, ,，,n,），且有,；,a,114,多级反馈队列,a,115,2.4.4,实时系统与实时任务调度,实时系统,实时系统,：,指能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行的计算机系统。,实时系统分为实时控制系统和实时信息处理系统。,实时控制系统,：指要求进行实时控制的系统，主要用于生产过程和实时采集现场数据。,a,116,实时信息处理系统,：指能对信息进行实时处理的系统，该系统由一台或多台主机通过通信线路连接成百上千个远程终端，主机根据终端来的请求进行信息检索和处理，并在很短的时间内为用户做出正确的回答。,a,117,实时任务,实时任务,：,指具有及时性要求的、常常被重复执行的特定进程，在实时系统中常称为任务。,按照任务执行是否呈现周性来划分任务有：,* 周性性实时任务,要求按照指定的周期循环执行。,* 非周期实时任务,任务执行无指定的周期性，但必须要联系着一个截止时间（包括开始截止时间和完成截止时间）。,a,118,按照对截止时间的要求可以划分为：,* 硬实时任务,系统必须满足任务对截止时间的要求。,* 软实时任务,联系着一个截止时间，但并不严格。,a,119,实时调度的目标,实时系统的关键即任务调度，调度策略主要考虑如何使硬实时任务在其规定的截止时间内完成，同时尽可能使软硬实时任务也能在其规定的截止时间内完成。,大多数现代实时操作系统无法直接处理任务的截止时间，只能尽量提高响应速度，以尽快地调度任务。,a,120,实时调度算法,常采用的算法有：,* 最早截止时间优先调度算法,* 速度单调调度算法（,RMS,）,即根据任务的周期大小给进程优先级，,最短周期的任务具有最高优先级。,任务周期,：指一个任务到达至下一任务到达之间的时间范围。,任务速度,：指周期的倒数。,a,121,2.5,线程,a,122,2.5.1,线程的定义,线程可定义为“,进程内的一个执行单位,”， 或者定义为“,进程内的一个可调度的实体,”。,在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。 负责处理机调度的程序称为线程调度程序，它是操作系统内核的重要组成部分， 线程调度也是内核的主要功能之一。,a,123,2.5.2,进程和线程的关系,(1),线程是进程的一个组成部分。 每个进程在创建时通常只有一个线程，需要时这个线程可以创建其它线程。 ,(2),进程的多线程都在进程的地址空间活动。,(3),资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源配额中扣除并分配给它。,(4),处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。 ,(5),线程在执行过程中， 需要同步。,a,124,2.5.3,线程的类型,在操作系统中，系统能否感知到线程的存在呢？这个问题涉及到将线程放在用户空间还是放在系统空间进行管理。,在某些操作系统中，系统感知不到线程的存在。换言之，线程完全在用户空间进行管理。那么，当一个线程将被阻塞时，它在停止之前选择并启动它的后继线程，而不必由操作系统内核进行控制。,在另外一些系统中，操作系统知道每个进程中有多少个线程，所以当一个线程被阻塞时，操作系统会选择下一个线程运行，它可能来自同一个进程，也可以来自其它进程。为了进行调度，核心必须设有一张线程控制表，其中列出了系统中所有的线程，类似于进程控制表所起的作用。,a,125,这两种选择的性能相差很远。在进程发生切换时，在用户空间管理的线程比需要操作系统核心调用的线程要快得多。这表明，将线程管理放在用户空间比较合理。而另一方面，当线程完全在用户空间管理时，若一个线程阻塞（例如，请求,I/O,服务或处理页面中断等），则操作系统核心会将线程所属的整个进程阻塞，因为它甚至不知道线程的存在。这表明，将线程放在系统空间进行管理更适宜。目前的做法是两种选择都被采用，同时还提出了各种混合方案。,不同类型的线程有着不同的属性和使用方法，以下讨论两种主要的线程类型。,a,126,*,内核线程,内核线程的特点：,A,、一个内核线程可以独立工作，不需要与一个用,户进程联系起来。,B,、内核线程的创建与撤消是由系统的内部需求决,定的，用来负责执行一个指定的任务，它共享,系统的程序与全局数据，具有自己的堆栈。,C,、内核线程能够被单独调度并使用标准的系统同,步机制。,a,127,D,、内核线程的创建和使用开销不是很大，它们,使用的资源是内核堆栈和在它们不运行时用,来保存寄存器上下文的一个内存区域，当然,还需要一些数据结构来保存调度和同步信息。,E,、内核线程间的上下文切换是很快的，因为内,存映射不用刷新。,F,、内核线程运行在系统空间，系统中有一张线,程表，列出了所有的内核线程，系统可以选,择内核线程运行。,a,128,*,用户线程,用户线程的特点：,A,、用户线程运行在用户空间，内核无,需也无法感知它。,B,、每个用户线程仅需一个栈和程序计,数器,PC,切换速度快。,C,、当一个用户线程被阻塞时,它在停,止之前选择并启动它的后继线程。,D,、用户线程的实现是可能的，因为用,户线程的上下文可以在没有内核干,预的情况下被保存和恢复。,a,129,E,、,每一个用户线程有自己的用户堆栈，,一块用来保存用户级寄存器上下文以,及如信号屏蔽等状态信息的内存区域。,F,、通过保存当前线程的堆栈和寄存器内容，,以及装入新调度线程的那些堆栈和寄存,器内容，可实现用户线程间的调度和上,下文的切换。,a,130,普通进程上的用户线程,a,131,2.6,进程互斥与同步,a,132,2.6.1,并发控制,进程间的同步,多个进程在执行过程中，为了共享资源与相互合作而在执行次序上的协调，称为,同步,。,例：有用户作业程序，其形式是：,Z=func 1(x)*func 2(y),其中,func 1(x),，,func 2(y),均是一个,复杂函数， 为了加快本题的计算速度，可用两个进程,P1,、,P2,各计算一个函数,。 进程,P2,计算,func 2(y),，进程,P1,在计算完,func 1(x),之后， 与进程,P2,的计算结果相乘， 以获得最终结果,Z,。,a,133,进程,P1,和,P2,间的同步,a,134,2.,进程间的互斥,当某一进程访问某一资源时，不允许别的进程同时访问，这种限制称为,互斥,。,就其本质来讲，互斥仍是一种同步。,资源互斥使用例,a,135,3.,并发控制的内容,* 竞争资源,多个进程因为使用共享资源而产生竞争关系，在抢占使用资源时可能导致使用失败，都达不到目的，因而要有信息交换以保证各得其所。,临界资源,：一次仅允许一个进程访问的资,源。,a,136,例如，若有两个进程,P1,、,P2,，共享一个公用变量,c,，初值为,8,，,P1,、,P2,所做工作如下：,P1 P2,L1,：,a = c,；,L4,：,b = c,；,L2,：,a = a+1,；,L5,：,b = b-1,；,L3,：,c = a,；,L6,：,c = b,；,试看下述两种执行情况：,若语句执行顺序为,L1,，,L2,，,L3,，,L4,，,L5,，,L6,，则,c = 8,；,(2),若语句执行顺序为,L1,，,L2,，,L4,，,L5,，,L3,，,L6,，则,c = 7,。,a,137,显然，上述结果是不能令人满意的。,P1,、,P2,是进程，每个进程中语句执行顺序是不变的，而两个进程的语句是可以交叉执行的，它们以哪种方式交叉执行是不可预知的。,a,138,临界区,：,进程访问临界资源的程序段。,在一个系统中，可以用某些方法或某种机制保证进程对临界区的互斥访问，一个好的解决方案应该遵循以下条件：,(1),任何两个进程不能同时处于临界区内（,忙则等待,）；,(2),进程在临界区外只作有限时间的等待（,有限等待,）；,(3),如果临界区空闲，则只要有进程申请就立即让其进入（,空闲让进,）；,(4),等待临界区时,释放,CPU,（,让权等待,）。,a,139,*,共享协作,系统中还有许多软资源，如共享变量、表格、队列、栈等被处理成临界资源，必须保证数据的一致性，以避免多个进程对它们访问时出现问题。,a,140,*,通信协作,系统中当进程进行通信合作时，各个进程之间要建立连接，各个进程需要同步和协调。,a,141,2.6.2,互斥和同步的解决策略,进程控制并发的关键就是控制进程同步与并发。具体解决方法有：,* 软件方法,* 硬件方法,* 信号量方法,* 管程方法,* 消息传递方法,a,142,2.6.3,互斥和同步的解决方法之一：软件方法,软件方法很难控制进程间的同步与互斥，并可能会大大增加系统的额外开销。,1,、初步设想,int turn=0; /*,共享的全局变量*,/,p0 p1, ,while (turn!=0) while (turn!=1) , ,turn=1; turn=0;, ,a,143,存在的问题：,* 进程严格交替进入临界区，导致降低系统性能。,* 任何进程在临界区内或外失败，其它进程将可能因为等待使用使用临界区，而无法向前推进。因为两个进程相互依赖对方对临界区使用权的修改。,a,144,2,、第一次改进,int flag 2=0,0; /*,共享的全局变量*,/,p0 p1, ,while (flag 1!=0) while (flag 0!=0),flag 0 =1; flag 1 =1;, ,flag 0 =0; flag 1 =0;, ,a,145,存在的问题：,* 如果进程在临界区内失败，导致其它进程永久阻塞。,* 如果进程在刚刚判断结束时被中断（也就是判断和置位不是一个原子操作，中间可能被中断），则导致同时进入临界区。,a,146,3,、第二次改进,int flag 2=0,0; /*,共享的全局变量*,/,p0 p1, ,flag 0 =1; flag 1 =1;,while (flag 1!=0) while (flag 0!=0) , ,flag 0 =0; flag 1 =0;, ,a,147,存在的问题：,* 如果进程在临界区内失败，导致其它进程永久阻塞。,* 如果进程在刚刚置位结束时被中断（也就是置位和判断不是一个原子操作，中间可能被中断），则导致都进不了临界区，即死锁。,a,148,4,、第三次改进,int flag 2=0,0; /*,共享的全局变量*,/,p0 p1,
展开阅读全文