操作系统原理与实例分析PPT课件第二章进程管理.ppt

《操作系统原理与实例分析PPT课件第二章进程管理.ppt》由会员分享，可在线阅读，更多相关《操作系统原理与实例分析PPT课件第二章进程管理.ppt（207页珍藏版）》请在三一办公上搜索。

1、第二章 进程管理,2.1 进程的引入,2.1.1 程序顺序执行与并发执行,程序的执行顺序1程序的顺序执行 例子：S1：a：x+y；S2：b：a-5；S3：c：b+1；,2程序顺序执行时的特征（1）顺序性：处理机的操作严格按照程序所规定的顺序执行。（2）封闭性：程序运行时独占全机资源，程序一旦开始执行，其执行结果不受外界因素影响。（3）可再现性：只要程序执行时的环境和初始条件相同，都将获得相同的结果。（不论它是从头到尾不停顿地执行，还是“停停走走”地执行）,3.程序的并发执行,4.程序并发执行时的特征,1）间断性:由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间

2、，形成了相互制约的关系。相互制约将导致并发程序具有“执行暂停执行”这种间断性的活动规律。2）失去封闭性:是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。3）不可再现性:程序在并发执行时，由于失去了封闭性，导致不可再现性。,例如，有两个循环程序A和已它们共享一个变量N。程序A每执行一次时，都要做N：=N1操作；程序B每执行一次时，都要执行Print（N）操作，然后再将N置成“0”。程序A和B以不同的速度运行。这样，可能出现其计算结果不可再现性，亦即，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。,例子：变量X为

3、共享变量，程序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。还可有许多其它组合,并发执行的条件：达到封闭性和可再现性,并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。,程序 P(i)针对共享变量的读集和写集 R(i)和W(i)条件：任意两个程序P(i)和P(j)，有：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;前两条保证一个程序的两次读之间数

4、据不变化；最后一条保证写的结果不丢掉。现在的问题是这个条件不好检查。,并发和并行区别,并发是指在某一时间间隔内计算机系统中存在着多个程序活动。并行是指在同一时刻计算机内有多个程序都在执行，这只有在多CPU的系统中才能实现。在单CPU的计算机系统中，多个程序是不可能同时执行的。并发是从宏观上（这种“宏观”也许不到一秒的时间）看多个程序的运行活动，这些程序在串行的、交错的运行，由操作系统负责这些程序之间的运行切换，人们从外部宏观上观察，有多个程序都在系统中运行。,2.1.2 进程的概念和特征1、进程的定义 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的基

5、本单位。,进程与程序的区别和相互关系程序 进程静态的指令序列 动态的程序执行过程一程序可对应 一个进程对应至少有多个进程 一个程序在工作永久性软件资源 暂存资源,动态产生过程 资源分配和调度的单位,2、进程的特征动态性：进程是程序在并发系统内的一次执行，一个进程有一个从产生到消失的生命期，是进程的最基本的特征；并发性：正是为了描述程序在并发系统内执行的动态特性才引入了进程，没有并发就没有进程，是进程的最重要的特征，正是因为并发性，才提高了系统资源的利用率和系统的吞吐量；独立性：每个进程的程序都是相对独立的顺序程序，可以按照自己的方向和速度独立地向前推进；异步性：指进程的执行进度，或推进速度不可

6、预测，而与同时驻留在内存的其它进程有关；制约性：进程之间的相互制约，主要表现在互斥地使用资源和相关进程之间必要的同步和通讯；结构性：进程=PCB+程序+数据集合,3、引入进程后需要解决的问题*增加了空间开销*额外的时间开销*更难控制*处理机的竞争尤为突出,2.1.3 进程的结构 为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块（PCB）组成。进程控制块是操作系统感知进程存在的唯一标志。程序部分描述进程本身所要完成的功能，而“私有数据块”是接受程序规定操作的一组存储单元的内容，是操作的对象。进程控制块是在进程创建时产生的，当进程存在于系统时（运行），进程控制块就标识了这个

7、进程。,PCB包含了进程的描述信息和控制信息，通常有如下项目：(1)标识符(2)存贮信息(3)现场状态(4)优先数(5)现场信息(6)链接字(或称队列指针)(7)族系关系(8)资源清单(9)其他,*标识符 分为外部标识符和内部标识符。外部标识符由创建进程者提供，通常由字母、数字等组成，在用户或其它进程访问该进程时使用。内部标识符是一个整数。在操作系统的PCB表区中，有多个PCB表，每个PCB表有一个序号，通常将这个序号做为内部标识符，以方便系统使用。*程序地址 进程的程序部分在内存及外存的地址，或描述程序地址信息的段表地址、页表地址等。,*数据地址 进程的数据部分在内存及外存的地址，或描述数据

8、地址信息的段表地址、页表地址等。*状态 进程当前所处的状态，即就绪状态、执行状态及阻塞状态，已经被创建的进程的状态必为此三者之一。,*CPU状态保护区 CPU状态信息主要由通用寄存器、程序计数器PC、程序状态字PSW以及用户栈指针等组成，也称为中断点现场信息。CPU状态保护区用以保护进程被中断而暂停执行时CPU的状态信息，以便进程重新获得CPU时能够重布现场，从上次被中断处继续执行。,*进程优先级 进程优先级是用以描述进程使用处理机的优先级别的整数，是优先级调度算法中调度的依据。通常数值越小，优先级别越高。优先级可以处理成不变的，称为静态优先级，也可以处理成可变的，称为动态优先级。,*通信信息

9、 进程通信时需要使用的信息，包括标志位、信号或信号量、消息队列信息等。如消息缓冲通信机制中，在进程的PCB表中，需要有消息队列队首指针、消息个数及互斥使用消息队列的信号量等。,*资源信息 进程对资源的需求及已经分配资源的清单。*队列指针 除了执行状态的进程外，其余的进程PCB表都处于某一就绪队列或某一阻塞队列中。队列指针用于指向进程所在队列中下一个PCB表的首地址。,*家族指针 进程在运行过程中可以创建新进程来协同完成同一任务。创建者称为父进程，被创建者称为子进程。父进程PCB表中有指向子进程的PCB表的指针，子进程的PCB表中有指向父进程的PCB表的指针，这就是家族指针，它可以将一个家族的进

10、程联系起来，形成进程家族树。,进程控制块的组织 为了便于管理，系统把所有的PCB用适当方式组织起来。一般说来，大致有以下三种组织方式：(1)线性表方式(2)索引方式(3)链接方式,2.2 进程的状态,2.2.1 进程执行轨迹,例 假设内存中有3个进程A、B、C，他们的程序代码已全部装入内存。若A、C两进程需要执行12条指令，B进程需要执行4条指令，且B进程执行到第4条指令处必须等待I/O,2.2.2 两状态进程模型,在两状态模型中进程可能处于如下两种状态中：执行(Running）非执行（Not-running）,两状态队列模型,进程的创建,进程的终止,接上表,导致进程状态转换的事件,2.2.3

11、 五状态进程模型,Running：占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机）Ready：准备执行Blocked：等待某事件发生才能执行，如等待I/O完成等New：进程已经创建，但未被OS接纳为可执行进程，并且程序还在辅存，PCB在内存Exit：因停止或取消，被OS从执行状态释放,Null New：新创建进程首先处于新状态,NewReady：OS接纳新状态进程为就绪进程Ready Running：OS只能从就绪进程中选一个进程执行Running Exit：执行状态的进程执行完毕，或被取消，则转换为退出状态RunningReady：分时系统中，时间片用完，或优先级高的进程到来，将终

12、止优先级低的进程的执行Running Blocked：执行进程需要等待某事件发生。通常因进程需要的系统调用不能立即完成，而阻塞,Blocked Ready：当阻塞进程等待的事件发生，就转换为就绪状态Ready Exit：某些系统允许父进程在任何情况下终止其子进程。若一个父进程终止，其子孙进程都必须终止。Blocked Exit：因为它自身退出了，或者是因为某种原因被取消。,Using Two Queues,2.2.4 进程的挂起状态,这个问题的出现是由于进程优先级的引入，一些低优先级进程可能等待较长时间，从而被对换至外存。这样做的目的是：提高处理机效率：就绪进程表为空时，要提交新进程，以提高处

13、理机效率；为运行进程提供足够内存：资源紧张时，暂停某些进程，如：CPU繁忙（或实时任务执行），内存紧张；,被挂起进程的原因,用于调试：在调试时，挂起被调试进程（从而对其地址空间进行读写）；操作系统的需要：操作系统可能挂起后台进程或一些服务进程，或某些可能导致系统故障的进程；父进程的需求：父进程可能挂起子进程。,被挂起进程的特征,不能被调度执行。可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能执行。为了阻止进程执行，可以通过代理使进程挂起。代理可以是进程自身或父进程、或OS。只有实施挂起操作的进程才能使之由挂起状态转换为其他状态。,One Suspend St

14、ate,一个挂起,Two Suspend States,具有挂起状态的进程状态转换,BlockedBlocked/Suspend：OS通常将阻塞进程换出，以腾出内存空间Blocked/SuspendReady/Suspend:当Blocked/Suspend进程等待的事件发生时，可以将其转换为Ready/suspendReady/SuspendReady：OS需要调入一个进程执行时ReadyReady/Suspend：挂起就绪进程，释放足够的内存空间New Ready/suspend（NewReady）：新进程创建后，可以插入到就绪队列或Ready/suspend队列。若无足够的内存分配给新进

15、程，则需要New Ready/Suspend,具有挂起状态的进程状态转换（续）,Blocked/SuspendBlocked：当Blocked/Suspend队列中有一个进程的阻塞事件可能会很快发生，则可将一个Blocked/Suspend进程换入内存，变为BlockedRunningReady/Suspend：当执行进程的时间片用完时，会转换为Ready。或，一个高优先级的Blocked/Suspend进程正好变为非阻塞状态，OS可以将执行进程转换为Ready/Suspend状态AllExit：通常，Running Exit。但某些OS中，父进程可以终止其子进程，使任何状态的进程都可转换为退

16、出状态,2.3 进程的控制,2.3.1 执行模式 处理机有核心态和用户态两种执行状态 核心态：由设备中断、异常、自陷、信号（即软中断）等进入，这种状态具有较高的特权，允许使用全部机器资源与机器指令，是操作系统程序执行时的状态。用户态：处理机在这种状态下只能使用指定的机器指令，不能使用如I/O、改变机器状态、修改存储保护等指令，并且只允许访问用户自己的存储区，是用户程序执行时的状态。,2.3.2 操作系统内核 没有配置任何软件的计算机称为裸机，操作系统是在裸机上添加多层软件形成的。通常将与硬件紧密相关的部分，如中断处理程序、设备驱动程序及进程从创建到撤消包括进程状态变迁中用到的公共操作等集中在一

17、起，常驻内存，作为裸机上添加的第一层软件，叫做内核。,操作系统内核的功能 运行频率高的功能模块大都放在操作系统的内核来实现。1、资源管理的功能*进程管理 进程的创建和终止、进程调度、进程状态转换、进程之间的同步和通信、以及PCB管理等等。*存储管理 为进程分配空间、实现内存保护和对换功能、对内存进行分段和分页管理的等等。*I/O设备管理 I/O缓冲区管理、为进程分配I/O通道和设备等等,2、支持功能*I/O中断处理 中断 处理功能既是内核的最基本功能，也是整个操作系统赖以活动的基础，即操作系统的一切重要活动都最终依赖于中断。*原语操作 操作系统内核的功能大都通过执行各种原语来实现的。,原语：是

18、机器指令的延伸，是由若干条机器指令构成的、完成特定功能的一个过程。原子操作：指一个操作中的所有动作，要么全做，要么全不做，即原子操作是一个不可分割的操作。在单处理机中，操作的原子性可以通过屏蔽中断来实现。时钟管理 时钟就是操作系统运行的脉搏。,2.3.3 进程控制1、进程的创建和撤消 进程的创建,进程的撤消,2、进程的阻塞和唤醒 阻塞是进程自己通过调用阻塞原语自己阻塞自己，而唤醒操作则由操作系统或其它相关进程调用唤醒原语来唤醒，进程自己无法自己唤醒自己。进程阻塞的原因：*进程请求I/O服务，无论获得I/O服务与否，通常都要暂时放弃CPU；*某些原语操作，如P操作等可能引起进程阻塞；*某些系统进

19、程工作时占用CPU，无事可做时，则调用阻塞原语将自己阻塞。,进程的阻塞,进程唤醒的原因：*进程请求的I/O操作完成；*某些原语操作，如V操作等可以解封阻塞进程；*某些系统进程有事可做时，用唤醒原语将其唤醒。,进程的唤醒,3、进程的挂起与激活 根据进程所处状态，挂起原语可以有三种处理：*完成进程从活动就绪状态到静止就绪状态的转变;*完成进程从活动阻塞状态到静止阻塞状态的转变;*若进程是执行状态，则转变为静止就绪状态。,挂起对象：*进程请求挂起自身；*父进程挂起子进程。挂起方式如下：*挂起一个具有指定标识符的进程；*挂起某个进程及其所有子孙进程。采用这种挂起方式可以避免进程被挂起而其子孙进程仍在活

20、动而带来的问题。,进程挂起,进程的激活,4、进程切换进程切换的大致的两个步骤：*保护被切换进程的现场；*恢复投入运行的现场。,2.4 进程调度,2.4.1 进程调度的目标、原则和方式 1.交通控制程序 交通控制程序(Traffic Controller)是J.H.Saltzer于 1966 年起的名字。他把操作系统中指挥各个进程的工作比作一个交通警察，而把各个进程比作车辆。它们之间有时要竞争，有时要合作，交通警察就要保证它们协调一致，互不冲突。在操作系统中，交通控制程序的主要职能是管理进程状态之间的转变和协调进程间的通讯。,2.进程调度程序 在进程状态的变化中，从就绪到运行的转变是由一个专门的

21、程序来完成的，该程序称为进程调度程序。进程调度称为“低级”调度，是相对作业调度而言的。进程调度程序所要完成的是把一台物理的CPU转变为多台虚拟的CPU或者多台逻辑的CPU。,3.引起进程调度的原因*现运行进程运行结束或者因任务完成而正常结束，或者因出现错误而异常结束。*现运行进程因某种原因，比如I/O请求，从运行进入阻塞状态。*现运行进程执行某种原语操作，如P操作、阻塞原语等，进入阻塞状态。*一个具有更高优先级的进程要求使用处理机，即进入就绪队列。*分配给该进程运行的时间片已用完。,4.进程调度程序的功能*记住系统中所有进程的状态、优先数和资源需求情况。对于动态优先数，还须按一定算法定期地对它

22、进行计算。*确定调度算法，决定把处理机分配给哪个进程和分配多长时间。某个进程正在运行时，如果有优先级更高的进程进入就绪队列，是继续运行原进程还是分配处理机给优先级更高的进程，由调度方式确定。*分配处理机给进程。,5.进程调度方式 所谓进程调度方式，是指当一个进程正在处理机上运行时，若有某个更为紧迫或更为重要的进程需要进行处理，或者说，如果有更高优先级的进程进入就绪队列时，如何分配处理机。通常有两种进程调度方式：,通常有两种进程调度方式：*非剥夺方式 进程一旦获得CPU就一直执行，直到完成或发生某事件（如请求I/O服务、P操作等）而阻塞，其它的进程方可运行。这种调度方式简单，容易实现，但是一个进

23、程的运行往往可能导致多数进程长期得不到服务，所以非抢占方式不适宜有多个竞争用户的通用系统。*剥夺方式 允许在逻辑上可执行的进程暂时放弃CPU。抢占方式的调度策略（如时间片轮转、优先级等）允许非执行进程在满足某种条件时抢占执行进程所占用的CPU。,6.进程调度的目标 进程调度要满足两个方面的目标：*满足用户的需求-交互式用户对响应时间的要求；-批处理系统用户对作业周转时间的要求；-实时系统对任务截止时间的要求。*满足系统的需求-系统吞吐量；-处理机利用率；-各类资源的平衡使用；-公平性；-优先级。,7.进程调度原则 A.面向用户的原则*响应时间 响应时间：是指从用户通过键盘提交一个请求开始，直到

24、系统首次产生响应为止的时间。常用于评价分时系统的性能。响应时间包括3个部分时间的总和：（1）从键盘输入的请求信息传送到处理机的时间；（2）处理机对请求信息进行处理的时间；（3）将响应结果发送到输出终端的时间。,*周转时间 周转时间：指从作业提交给系统开始，到作业完成为止的这段时间间隔，也叫作业周转时间。常用于批处理系统的性能。周转时间包括4个部分时间的总和：（1）作业在外存排队等待调度的时间；（2）进程在就绪队列中等待调度的时间（可能多次等待）；（3）进程被处理机执行的时间。（4）等待I/O操作完成的时间。,*截止时间 截止时间：指实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间

25、。常用于评价实时系统的性能。,B.面向系统的原则*系统吞吐量 系统吞吐量：指单位时间内系统所完成的作业数。常用于评价批处理系统的性能。*处理机利用率 处理机利用率：指处理机被使用的频率。对于衡量大中型机的多用户系统是一个重要的指标。对于但用户微机或某些实时系统，则并非很重要。,*各种资源的平衡使用 多道程序系统的目标之一就是提高系统资源的利用率，因此，调度算法有责任是系统中的各种资源都尽量处于忙碌状态。该原则同时适合中级调度和高级调度。*公平性 调度算法应该对所有进程公平，而不偏袒任何进程。,*优先权 优先权是调度算法需要考虑的一个重要因素。优先权高的进程应该优先调度。确定优先权的高低的方式：

26、*静态优先权*动态优先权,2.4.2 进程调度的类型 按照算法所运行的系统类型，可以分为：*批处理调度*分时调度*实时调度*多处理机调度,按照调度的层次，可以分为：*高级调度（长程调度）*低级调度（短程调度）*中级调度（中程调度）,*高级调度 即作业调度或宏观调度。其任务是对那些提交给系统后被收容的作业,按照一定策略选择出某些作业,为其分配内存等必要的资源,建立与之对应的进程,并将进程的PCB表放入就绪队列中,使其具备参与竞争使用CPU的权利。,作业调度,高级调度要考虑的两个问题：*选择多少个作业进入内存，为之创建进程，这取决于多道程序度。*选择哪些作业，这取决于高级调度算法。可用的高级调度算

27、法有：-先来先服务-短作业优先-基于优先级调度-响应比高者优先 注意：如果系统不支持作业处理功能，也就 不会有高级调度。,*低级调度 即进程调度或微观调度。其任务是在进入内存并处于就绪队列的进程中,确定哪个进程真正获得CPU及其使用CPU的时间。用执行指针指向选中进程的PCB表，将它从就绪队列移出并重布现场，使其运行。现代操作系统都支持低级调度。,进程调度,*中级调度 将就绪状态细化为内存就绪和外存就绪状态，阻塞状态细化为内存阻塞和外存阻塞状态后，中级调度完成进程在内存与外存之间的对换。其任务是周期性地将那些在内存中暂时不用的进程换出并放到外存，而将那些在外存上需要运行的进程换入到内存。,中级

28、调度,处理机的三级调度,2.4.3 进程调度算法 下面是几项主要的评估标准：（）平均周转时间 作业从提交时刻is到完成时刻ic所经历的时间称为该作业的周转时间，即icis；进程从进入就绪队列的时刻ir到执行完本次周期的时刻ic称为该进程的周转时间i，即iicir。于是，个作业的平均周转时间或个进程的平均周转时间为：,（）平均带权周转时间 作业的周转时间Ti与其实际运行时间i之比 称为该作业的带权周转时间，即，同样，进程的周转时间与其本次周期的时值之比 称为该进程的带权周转时间。于是，个作业或个进程的平均带权周转时间为：,（）平均等待时间 进程从进入就绪队列那一时刻ir到获得的那一时刻ip所经历

29、的时间称为它的等待时间i，即iipir，那么个进程的平均等待时间为：通常，用来衡量不同调度算法对同一作业流或同一进程集的调度性能，用来衡量不同进程调度算法对同一进程集的调度性能，而用来衡量同一调度算法对不同作业流或不同进程集的调度性能。,现代操作系统采用了以下几种调度算法：*先来先服务（FCFS）在先来先服务算法中，进程到达就绪队列时按先后顺序排队。选择进程去执行时，始终选队首进程。进程获得CPU后，直至执行完或发生某等待事件，才释放CPU。,先来先服务算法（）本质上是非剥夺式的，如果可剥夺，则不能保证原则的实施。先来先服务算法（）优点：实现简单 先来先服务算法（）缺点：*对短进程不公平，使排

30、在队列后面的短进程要等待很长时间，增加整个系统的平均周转时间。*不利于I/O型进程，未能有效利用系统资源*采用非剥夺调度方式，未考虑进程的紧迫程度，不适合分时系统和事务处理系统。,因此，先来先服务算法（）算法常常和其它调度算法混合使用，算法适合高级调度、中级调度和低级调度。,平均周转时间和平均带权周转时间,考虑三个进程、和，它们的本次周期的时值分别为、和，且以、的次序处于就绪队列中，不妨认为它们进入就绪队列的相对时刻均为。于是，在调度下，其执行过程可表示如下：,、和的等待时间分别为、和，周转时间分别为、和，故它们的平均等待时间和平均周转时间分别为：,*短进程优先 短进程优先算法本质上是非剥夺式

31、的，如果可剥夺，则不能保证原则的实施。短进程优先算法优点：降低了平均等待时间，提高了系统的吞吐量。短进程优先算法缺点：*算法需要预测进程的预期执行时间，当进程还没运行时，很难准确预测进程的执行时间。*该算法总是优先调度短进程，有可能导致长进程饥饿，对长进程不公平。*采用非剥夺调度方式，未考虑进程的紧迫程度，不适合分时系统和事务处理系统。,*时间片轮转调度法（）算法是一种剥夺式的进程调度算法，它依据公平服务的原则，将时间划分成一个个的时间片（记为S），并以为单位，轮转地为各个就绪进程一次分配一个时间片。常用于分时系统和事务处理系统 时间片轮转调度算法优点：*解决了短进程和长进程的不公平问题；*对

32、计算型的进程较有利；*满足分时系统用户对响应时间的要求。,时间片轮转调度算法缺点：*不适合批处理系统的进程调度。*不利于I/O型的进程。,时间片轮转调度算法的时间片选择时注意的问题：*不能太短，太短会使进程切换非常频繁，从而降低处理机的效率；*不能太长，太长将无法满足交互式用户对响应时间的要求。因此，时间片大小的设置要综合考虑系统的最大用户数、响应时间的要求和系统效率等多种因素。,以前述的三个进程为例，考察算法的执行情况及其调度性能。设，则有：,进程首先执行一个时间片并被剥夺，其周期所剩余的 放到以后执行；执行一个时间片后也被剥夺；的时值为，不足一个时间片。第二轮开始，又由先执行一个时间片后被

33、剥夺；这次只执行。至此，和的周期已先后完成，故随后连续个时间片都分给了，直至完成，在最后一个时间片里，只执行了。容易算出，该例的平均等待时间和平均周转时间分别为：,其中，为系统的响应时间上限，为系统中的进程数目上限。例如，设，则0.1。,*基于优先级的调度算法 优先级通常是用一个整型数来表示，称为优先数。对于不同的系统，既可以用较大的数也可以用较小的数来表示较高的优先级，这并无统一的规定。,优先级的设置考虑的因素：*进程完成功能的重要性；*进程完成功能的紧迫性；*为均衡系统资源的使用，指定 进程（作业）优先级；*进程对资源的占有程度。,确定优先权的高低的方式：*静态优先权 在进程运行期间其优先

34、级一直不变，*动态优先权 随着进程的运行其优先级要改变，其变化考虑的典型因素有：根据进程运行时间的剩余时间的 减少而上升，以使要执行结束 的进程尽快结束；根据进程在队列等待时间的增加而上 升，以不至于饥饿。动态确定优先级的时刻一般在每个时钟 中断或需要进程切换时。,设有五个就绪进程，它们各自的本次周期的长度、初始优先数及进入就绪队列的相对时刻如下所示：,在非剥夺的静态设置方式下，执行情况如下：,在进程执行完时，已进入就绪队列，因其优先级较高，故先于和之前执行。可算得这些进程的平均等待时间、平均周转时间以 及平均带权周转时间分别为：,*剩余时间最短者优先算法 根据进程运行时间的剩余时间最短者优先

35、级最高，以使要执行结束的进程尽快结束。本质上是剥夺型的短进程优先调度算法。剥夺是根据时间片。,*响应比高者优先算法 根据进程等待时间和进程的预期执行时间纳入优先级的运算。使进程的优先级与等待时间成正比，与进程执行时间成反比。响应比：响应时间需运行时间（已等待时间需运行时间）需运行时间 已等待时间需运行时间 响应比高者优先算法优点：是长进程和短进程都得到合理的运行机会。响应比高者优先算法缺点：很难估计进程的剩余执行时间。,*反馈调度算法 多级反馈队列就是综合了、和的 一种进程调度算法，其基本思想如下：（）系统按优先级别设置个就绪进程队列，第一级队列的优先级最高，以下逐级降低，第级队列的优先级最低

36、；（）每个就绪队列对应有一个时间片Si（i，2,，n），且有；,多级反馈队列,2.4.4 实时系统与实时任务调度实时系统 实时系统：指能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行的计算机系统。实时系统分为实时控制系统和实时信息处理系统。实时控制系统：指要求进行实时控制的系统，主要用于生产过程和实时采集现场数据。,实时信息处理系统：指能对信息进行实时处理的系统，该系统由一台或多台主机通过通信线路连接成百上千个远程终端，主机根据终端来的请求进行信息检索和处理，并在很短的时间内为用户做出正确的回答。,实时任务 实时任务：指具有及时性要求的、常常被重复执

37、行的特定进程，在实时系统中常称为任务。按照任务执行是否呈现周性来划分任务有：*周性性实时任务 要求按照指定的周期循环执行。*非周期实时任务 任务执行无指定的周期性，但必须要联系着一个截止时间（包括开始截止时间和完成截止时间）。,按照对截止时间的要求可以划分为：*硬实时任务 系统必须满足任务对截止时间的要求。*软实时任务 联系着一个截止时间，但并不严格。,实时调度的目标 实时系统的关键即任务调度，调度策略主要考虑如何使硬实时任务在其规定的截止时间内完成，同时尽可能使软硬实时任务也能在其规定的截止时间内完成。大多数现代实时操作系统无法直接处理任务的截止时间，只能尽量提高响应速度，以尽快地调度任务。

38、,实时调度算法 常采用的算法有：*最早截止时间优先调度算法*速度单调调度算法（RMS）即根据任务的周期大小给进程优先级，最短周期的任务具有最高优先级。任务周期：指一个任务到达至下一任务到达之间的时间范围。任务速度：指周期的倒数。,2.5 线程,2.5.1 线程的定义 线程可定义为“进程内的一个执行单位”，或者定义为“进程内的一个可调度的实体”。在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。负责处理机调度的程序称为线程调度程序，它是操作系统内核的重要组成部分，线程调度也是内核的主要功能之一。,2.5.2 进程和线程的关系(1)线程是进程的一个组成部分。每个进程在创建时通常只

39、有一个线程，需要时这个线程可以创建其它线程。(2)进程的多线程都在进程的地址空间活动。(3)资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源配额中扣除并分配给它。(4)处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。(5)线程在执行过程中，需要同步。,2.5.3 线程的类型 在操作系统中，系统能否感知到线程的存在呢？这个问题涉及到将线程放在用户空间还是放在系统空间进行管理。在某些操作系统中，系统感知不到线程的存在。换言之，线程完全在用户空间进行管理。那么，当一个线程将被阻塞时，它在停止之前选择并启动它的后继线程，而不必由操作系统内核进行控

40、制。在另外一些系统中，操作系统知道每个进程中有多少个线程，所以当一个线程被阻塞时，操作系统会选择下一个线程运行，它可能来自同一个进程，也可以来自其它进程。为了进行调度，核心必须设有一张线程控制表，其中列出了系统中所有的线程，类似于进程控制表所起的作用。,这两种选择的性能相差很远。在进程发生切换时，在用户空间管理的线程比需要操作系统核心调用的线程要快得多。这表明，将线程管理放在用户空间比较合理。而另一方面，当线程完全在用户空间管理时，若一个线程阻塞（例如，请求 I/O服务或处理页面中断等），则操作系统核心会将线程所属的整个进程阻塞，因为它甚至不知道线程的存在。这表明，将线程放在系统空间进行管理更

41、适宜。目前的做法是两种选择都被采用，同时还提出了各种混合方案。不同类型的线程有着不同的属性和使用方法，以下讨论两种主要的线程类型。,*内核线程 内核线程的特点：A、一个内核线程可以独立工作，不需要与一个用 户进程联系起来。B、内核线程的创建与撤消是由系统的内部需求决 定的，用来负责执行一个指定的任务，它共享 系统的程序与全局数据，具有自己的堆栈。C、内核线程能够被单独调度并使用标准的系统同 步机制。,D、内核线程的创建和使用开销不是很大，它们 使用的资源是内核堆栈和在它们不运行时用 来保存寄存器上下文的一个内存区域，当然 还需要一些数据结构来保存调度和同步信息。E、内核线程间的上下文切换是很快

42、的，因为内 存映射不用刷新。F、内核线程运行在系统空间，系统中有一张线 程表，列出了所有的内核线程，系统可以选 择内核线程运行。,*用户线程 用户线程的特点：A、用户线程运行在用户空间，内核无 需也无法感知它。B、每个用户线程仅需一个栈和程序计 数器PC,切换速度快。C、当一个用户线程被阻塞时,它在停 止之前选择并启动它的后继线程。D、用户线程的实现是可能的，因为用 户线程的上下文可以在没有内核干 预的情况下被保存和恢复。,E、每一个用户线程有自己的用户堆栈，一块用来保存用户级寄存器上下文以 及如信号屏蔽等状态信息的内存区域。F、通过保存当前线程的堆栈和寄存器内容，以及装入新调度线程的那些堆栈

43、和寄存 器内容，可实现用户线程间的调度和上 下文的切换。,普通进程上的用户线程,2.6 进程互斥与同步,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。,进程P1 和P2 间的同步,2.进程间的互斥 当某一进程访问某一资

44、源时，不允许别的进程同时访问，这种限制称为互斥。就其本质来讲，互斥仍是一种同步。,资源互斥使用例,3.并发控制的内容*竞争资源 多个进程因为使用共享资源而产生竞争关系，在抢占使用资源时可能导致使用失败，都达不到目的，因而要有信息交换以保证各得其所。临界资源：一次仅允许一个进程访问的资 源。,例如，若有两个进程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，L

45、4，L5，L3，L6，则c=7。,显然，上述结果是不能令人满意的。P1、P2是进程，每个进程中语句执行顺序是不变的，而两个进程的语句是可以交叉执行的，它们以哪种方式交叉执行是不可预知的。,临界区：进程访问临界资源的程序段。在一个系统中，可以用某些方法或某种机制保证进程对临界区的互斥访问，一个好的解决方案应该遵循以下条件：(1)任何两个进程不能同时处于临界区内（忙则等待）；(2)进程在临界区外只作有限时间的等待（有限等待）；(3)如果临界区空闲，则只要有进程申请就立即让其进入（空闲让进）；(4)等待临界区时,释放CPU（让权等待）。,*共享协作 系统中还有许多软资源，如共享变量、表格、队列、栈等

46、被处理成临界资源，必须保证数据的一致性，以避免多个进程对它们访问时出现问题。,*通信协作 系统中当进程进行通信合作时，各个进程之间要建立连接，各个进程需要同步和协调。,2.6.2 互斥和同步的解决策略 进程控制并发的关键就是控制进程同步与并发。具体解决方法有：*软件方法*硬件方法*信号量方法*管程方法*消息传递方法,2.6.3 互斥和同步的解决方法之一：软件方法 软件方法很难控制进程间的同步与互斥，并可能会大大增加系统的额外开销。1、初步设想 int turn=0;/*共享的全局变量*/p0 p1 while(turn!=0)while(turn!=1)turn=1;turn=0;,存在的问题

47、：*进程严格交替进入临界区，导致降低系统性能。*任何进程在临界区内或外失败，其它进程将可能因为等待使用使用临界区，而无法向前推进。因为两个进程相互依赖对方对临界区使用权的修改。,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;,存在的问题：*如果进程在临界区内失败，导致其它进程永久阻塞。*如果进程在刚刚判断结束时被中断（也就是判断和置位不是一个原子操作，中间可能被中断），则导致同时进入临界区。,3、第二次改进 int flag

48、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;,存在的问题：*如果进程在临界区内失败，导致其它进程永久阻塞。*如果进程在刚刚置位结束时被中断（也就是置位和判断不是一个原子操作，中间可能被中断），则导致都进不了临界区，即死锁。,4、第三次改进 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;延迟一小段时间 延迟一

49、小段时间 flag 0=1;flag 1=1;flag 0=0;flag 1=0;,存在的问题：*如果进程在临界区内失败，导致其它进程永久阻塞。*如果进程条件判断和赋值进行交替执行，导致反复的僵局。,5、成功的Dekker互斥算法 int flag 2=0,0;/*共享的全局变量，表示临界区状态*/int turn=0或1;/*共享的全局变量，表示进入临界区的顺序*/p0 p1 flag 0=1;flag 1=1;while(flag 1)while(flag(0)if(turn=1)if(turn=0)flag 0=0;flag 1=0;while(turn=1)while(turn=0)f

50、lag 0=1;flag 1=1;turn=1；turn=0；flag 0=0;flag 1=0;,6、Peterson的互斥算法int flag 2=0,0;/*共享的全局变量，表示临界区状态*/int turn=1;/*共享的全局变量，表示进入临界区的顺序*/p0 p1 flag 0=1;flag 1=1;turn=1;turn=0;while(flag 1,软件方法总结：*采用软件方法实现进程互斥使用临界区资源 是很困难的，通常能实现两个进程的互斥，很难控制多个进程的互斥。*算法可能出现死锁或互斥失败等严重问题。*软件方法不能解决“忙等”现象，降低系统效 率,2.6.4 互斥和同步的解决