《嵌入式实时操作系统及应用开发》Chapter2

第二章

进程管理(1)第二章

进程管理〔1〕

2.1进程的概念和PCB2.2进程控制2.3线程第二章

进程管理2.1进程的根本概念

程序的顺序执行及特征1.根本概念程序：一个在时间上按严格次序、顺序执行的操作序列。程序的顺序执行：一个具有独立功能的程序独占处理机，直至得到最终结果的过程。操作：数据处理的一种规那么，一经启动就需要在有限时间内完成。计算：假设干操作严格顺序执行的集合。2.程序的顺序执行在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。通常一个程序可分成假设干个程序段，它们必须按照某种先后次序执行，仅当前一操作执行后，才能执行后继操作。例如：进行计算。I:输入操作C:计算操作P:打印操作。在进行计算时，总是先输入用户的程序和数据，然后进行计算，最后将结果打印出来。3.语句的顺序执行S1：a:=x+yS2：b:=a-5S3：c:=b+1如以下图，语句S2必须在a被赋值后才能执行；S3也只能在b被赋值后才能执行。4.程序的顺序执行的特征顺序性：一个程序的各个局部的执行，严格地按照某种先后次序执行；封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源；可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不管它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。程序顺序执行的特性，为程序员检测和校正程序的错误带来很大方便。2.1.2.前趋图为了描述一个程序的各局部(程序段或语句)间的依赖关系，或者是一个大的计算的各个子任务间的因果关系，我们常常采用前趋图方式。图2-1九个结点的前趋图前趋图〔续〕P1为初始结点，P9为终止结点每个结点还具有一个重量。该前趋图，存在下面的前趋关系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9；或表示为：Ｐ={P1,P2,P3,P4,P5,P6,P7,P8,P9}

={(P1,P2),(P1,P3),(P1,P4),

(P2,P5),(P3,P5),(P4,P6),

(P4,P7),(P5,P8),(P6,P8),

(P7,P9),(P8,P9)}前趋图〔续〕前趋图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边表示两个结点之间存在的偏序(Partial_Order)或前趋关系(Precedence_Relation)“→”＝{(Pi,Pj)|在Pj开始前Pi必须完成}如果(Pi,Pj)∈→，可写成Pi→Pj，Pi是Pj的直接前趋，Pj是Pi的直接后继。前趋图中必须不存在循环，如以下图不是前趋图。2.1.3程序并发执行及特征1.并发环境：

在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的2.程序的并发执行在对一批程序进行处理时，可以并发执行。例如，输入、计算、打印三个程序对一批作业进行处理时，存在以下的前趋关系：Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1图2-2并发执行时的前趋图在上例中存在下述前趋关系：Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1在Pi-1和Ci以及Ii+1之间，可以并发执行。对于具有下述四条语句的程序段：S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b图2-3四条语句的前趋关系3.程序的并发执行的特征不可再现性：由于程序的并发执行，打破了由另一程序独占系统资源的封闭性，因而破坏了可再现性。间断性：程序并发执行时，由于它们共享资源或程序之间相互合作完成一项共同任务，因而使程序之间相互制约。通信性：对于相互合作的程序，为了更有效地协调运行，相互之间进行通信。独立性：并发程序在运行过程中，既然是作为一个独立的运行实体，它也必然具有作为一个单位去获得资源的独立性。4.多道程序设计

定义：Multiprogramming多道程序设计是指允许多个程序同时进入内存并运行〔引入目的是为了提高系统效率〕与并发不完全是一个概念，但效果相似考虑因素：在多道程序环境下如何向用户提供效劳在并发程序之间如何正确传递消息〔通讯〕如何对CPU进行调度，保证每个用户相对公平地得到CPU如何管理其他资源当各用户对资源使用上发生冲突时，如何处理竞争 对CPU只能通过调度来解决竞争问题，而对于其他资源通过申请—分配—使用—回收的方法进行管理，当且仅当占有CPU的时候才可以申请，否那么要排队等候

2.1.4进程的特征与状态

1.进程的概念进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位进程是可与其他程序并发执行的程序，在一个数据集合上的运行过程。它是系统进行资源分配和调度的一个独立单位。2.进程的特征动态性：进程的实质是程序的一次执行过程， 进程是动态产生，动态消亡的，进程在其生命周期内，在三种根本状态之间转换并发性：任何进程都可以同其他进程一起向前推进独立性：进程是一个能独立运行的根本单位，同时也是系统分配资源和调度的独立单位；异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进结构特征：为了控制和管理进程，系统为每个进程设立一个进程控制块－PCB。3.进程与程序的区别程序是静态的，进程是动态的;进程更能真实地描述并发,而程序不能;一个程序可对应多个进程，反之亦然;进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的;程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的；进程是系统分配调度的独立单位，能与其他进程并发执行;进程是由程序和数据两局部组成的进程具有创立其他进程的功能，而程序没有4.进程创立与中止1〕进程何时创立提交一个批处理作业用户登录由OS创立，用以向一用户提供效劳(如：打印文件)由已存在的一进程创立一个用户程序可创立成多个进程进程何时中止批处理作业发出暂停〔Halt〕指令用户退出登录进程执行一中止效劳请求出错及失败因素5.进程中止的原因正常结束给定时限到缺少内存存储器出界保护性出错：例子:写只读文件算术错超出时间：进程等待超过对某事件的最大值I/O失败无效指令：如试图执行数据特权指令操作系统干预：如当死锁发生时父进程请求中止某一子进程父进程中止，所以子进程也中止运行就绪等待图2－4进程的状态及其转换

进程状态〔续〕当进程已分配到除CPU以外的所有必要资源时，它便处于就绪状态，一旦获得CPU，便立即执行。已获得CPU的进程进入执行状态。正在执行的进程，由于发生某个事件而暂时无法执行时，便放弃处理机而进入阻塞状态。由于执行的进程变为阻塞状态后，调度程序立即把处理机分配给另一个就绪进程；因此，阻塞进程的事件消失后，进程不会立即恢复到执行状态，而转变为就绪状态，重新等待处理机。2〕进程状态转换条件在进程运行过程中，由于自身进展情况及外界环境的变化，这三种根本状态可以依据一定的条件相互转换：就绪-->运行调度程序选择一个新的进程运行运行-->就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态进程状态转换条件〔续〕运行-->等待当一进程必须等待时OS尚未完成效劳对一资源的访问尚不能进行初始化I/O且必须等待结果等待某一进程提供输入(IPC)等待-->就绪当所等待的事件发生时创立状态终止状态挂起状态〔调节负载，对换，父进程，操作系统，终端用户〕3〕其他状态创立(新new)状态OS已完成为创立一进程所必要的工作已构造了进程标识符已创立了管理进程所需的表格但还没有允许执行该进程(尚未同意)因为资源有限终止〔退出exit)状态中止后进程移入该状态它不再有执行资格表格和其它信息暂时由辅助程序保存例子:为处理用户帐单而累计资源使用情况的财务程序当数据不再需要后，进程(和它的表格)被删除4〕具有挂起操作的进程状态转换图有的系统有时希望能人为地把进程挂起，使之处于静止状态，以便研究其执行情况或对它进行修改。以下图示出了具有挂起状态的进程状态演变图。图2－5具有挂起状态的进程状态演变图

五状态进程模型准备退出：父进程可中止子进程七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起5〕新状态转换(中期调度)阻塞-->阻塞挂起当所有进程都阻塞，OS会安排空间让一就绪进程进入内存阻塞挂起-->就绪挂起当等待的事件发生时(状态信息已在OS中)就绪挂起-->就绪当内存中没有就绪进程时就绪-->就绪挂起(较少见)当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时7.进程控制块〔PCB〕系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的1)进程控制块的内容进程标识符：标识一个进程的编号，也称为进程的内部名；现性状态：说明进程的当前状态；现场保存区：保存进程由执行状态变为其它状态时的CPU现场信息；程序与数据地址：该进程的程序和数据所在位置信息；互斥与同步机构：实现进程间互斥与同步时所必须的机构；进程控制块的内容〔续〕进程通信机制：用于实现进程间的通信所需的数据结构；优先级：表示进程使用CPU时优先级别的一个整数；资源清单：列出进程拥有的资源的记录；连接字：给出本进程所在队列中的下一个进程的PCB首址；家族联系：用于说明本进程与其它家族成员间的关系。2)进程映象(进程要素)用户程序用户数据栈用于过程调用和参数传递进程控制块PCB(执行上下文)控制进程所需的数据(进程属性)，包括:进程标识符信息处理器状态信息进程控制信息3〕进程控制块的组织方式为了有效地对进程控制块进行管理，应该采用适当的方式把它们组织起来。目前常用的组织方式有以下两种：按链接方式组织PCB(队列)不同状态进程分别组成队列 运行队列、就绪队列、等待队列按索引方式组织PCB(表)对具有相同状态的进程，分别设置各自的PCB索引表，说明PCB在PCB表中的地址〔其他方式：线性表或链表〕按索引方式组织PCB按链接方式组织PCBPCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn......空PCB运行态就绪态等待1等待26751015

2.2进程控制

1.进程控制的主要任务

进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。

2.进程图

进程图是一棵有向树(如以下图)，结点代表进程。一棵树表示一个家族，根结点为该家族的祖先(Ancestor)。

3.进程图和前趋图之间的差异

前趋图描述的是任务(或进程)之间的前趋关系；只有在前趋进程完成后，其后继进程才能运行；在进程图中，创立者和被创立者可以并发执行，也可以父进程等待其所有的子进程结束后再执行，这完全取决于创立原语和创立者的需要。

4.内核与原语

内核：加在硬件上的第一层软件，通过执行各种原语操作来实现各种控制和管理功能，具有创立、撤消、进程通信、资源管理的功能。内核的根本功能支撑功能：中断处理、时钟管理、原语操作资源管理功能：进程管理、存贮管理、设备管理原语：是由假设干条机器指令所构成，用以完成特定功能的一段程序。5.进程控制创立、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。进程创立原语进程撤消原语阻塞原语唤醒原语挂起原语激活原语

1)创立原语

功能：创立一个具有指定标识符进程入口信息：进程标识符、优先级、进程开始地址、初始CPU状态、资源清单等。进程创立过程创立一个PCB赋予一个统一进程标识符为进程映象分配空间初始化进程控制块许多默认值(如:状态为New，无I/O设备或文件...)设置相应的链接如:把新进程加到就绪队列的链表中

创立原语的实现过程

2)进程的撤消原语

功能：撤消一个指定的进程入口信息：被撤消的进程名实现:收回进程所占有的资源,撤消该进程的PCB

引起撤消的原因

正常结束异常结束〔越界错、保护错、特权指令错、非法指令、运行超时、I/O故障等〕外界干预〔操作员干预、父进程请父进程终止〕

撤消原语的实现过程

3)进程阻塞处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。

进程的阻塞原语

功能：停止调用进程的执行，变为等待。入口信息：可省

阻塞原语的实现过程

4)进程的唤醒原语

功能：唤醒某一处于等待队列当中的进程。入口信息：被唤醒进程的名字引起唤醒的原因系统效劳由不满足到满足I/O完成新数据到达进程提出新请求〔效劳〕

唤醒原语的实现过程

5)进程的挂起与激活

挂起原语的功能：自身挂起、挂起具有指定标识符的进程、将其进程及其全部或局部“子孙”挂起。激活原语功能：使处于静止状态的进程变为活动。6.系统核心1)系统核心： 向上提供多个无中断的虚拟机器 在核心内不允许中断2)特点：为进程运行提供一个舞台核心常驻内存设计短小精焊3)核心的组成

中断处理进程管理:调度控制通讯互斥同步等原语管理:在核心中提供一系列原语，同步,通信，创立，撤消等4)队列管理

队列数据结构:指向队首的表指针三个队列:运行，就绪，等待队列排队方式:排队首排队尾插队出队方式:队首出队/队中出队队列管理:中断之后，进程调度之前5)现场管理

保存现场;注意顺序,中断之后第一步恢复现场:恢复时机，进程调度最后一步时钟管理:以固定频率+1-1用途:进入绝对时钟间隔时钟进行分析比较6)虚时钟每个进程分配给一个虚时钟来记录CPU时间,这个时钟称为虚时钟。虚时钟存放在PCB中，属于现场的一局部，进程运行时，将虚时钟放入内存开辟的专门单元，离开CPU那么放在PCB中。核心处理流程:7)内核的执行特点由中断驱动的:中断→内核→退出内核执行是连续的内核执行过程中在中断屏蔽状态下内核使用特权指令

思考题1．如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个,最少几个；等待进程最多几个，最少几个？2.有没有这样的状态转换，为什么？ 等待—运行；就绪—等待3.一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能4.举3个日常生活中类似进程的例子第二章

进程管理2.3线程

2.3线程

1.进程的两个根本属性：资源的拥有者：给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源〔文件，I/O设备〕，有状态、优先级、调度调度单位：进程是一个执行轨迹以上两个属性构成进程并发执行的根底

2.线程的引入对进程系统必须完成的操作：创立进程撤消进程进程切换缺点：时间空间开销大，限制并发度的提高线程的引入〔续1〕在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度线程：有时称轻量级进程，进程中的一个运行实体，是一个CPU调度单位，资源的拥有者还是进程或称任务线程的引入〔续2〕线程：有执行状态〔状态转换〕不运行时保存上下文有一个执行栈有一些局部变量的静态存储可存取所在进程的内存和其他资源可以创立、撤消另一个线程

3.线程的特点

是进程的一个实体，可作为系统独立调度和分派的根本单位。不拥有系统资源〔只拥有附属进程的全部资源，资源是分配给进程〕一个进程中的多个线程可并发执行。〔进程可创立线程执行同一程序的不同局部〕系统开销小、切换快。〔进程的多个线程都在进程的地址空间活动〕单进程、单线程单进程、多线程多进程、一个进程一个线程多进程、一个进程多个线程

4.线程和进程的关系PCB用户栈单线程进程模型用户地址空间核心栈线程控制块：包含了寄存器映像，线程优先数和线程状态信息PCB多线程进程模型用户地址空间用户栈核心栈线程控制块用户栈核心栈线程控制块用户栈核心栈线程控制块5.引入线程的好处创立一个新线程花费时间少〔结束亦如此〕两个线程的切换花费时间少〔如果机器设有“存储[恢复]所有存放器”指令，那么整个切换过程用几条指令即可完成〕因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核适合多处理机系统例子1：LAN中的一个文件效劳器，在一段时间内需要处理几个文件请求因此有效的方法是：为每一个请求创立一个线程在一个SMP机器上：多个线程可以同时在不同的处理器上运行例子2：一个线程显示菜单，并读入用户输入；另一个线程执行用户命令考虑一个应用：由几个独立局部组成，这几个局部不需要顺序执行，那么每个局部可以以线程方式实现当一个线程因I/O阻塞时，可以切换到同一应用的另一个线程

6.线程与进程的比较

调度：线程作为调度的根本单位，同进程中线程切换不引起进程，当不同进程的线程切换才引起进程切换；进程作为拥有资源的根本单位。并发性：一个进程间的多个线程可并发。拥有资源：线程仅拥有隶属进程的资源；进程是拥有资源的独立单位。系统开销：进程大；线程小。

7.线程的实现机制用户级线程核心级线程两者结合方法1)用户级线程〔ULT〕由应用程序完成所有线程的管理通过线程库(用户空间)一组管理线程的过程核心不知道线程的存在线程切换不需要核心态特权调度是应用特定的

对用户级线程的核心活动核心不知道线程的活动，但仍然管理线程的进程的活动当线程调用系统调用时，整个进程阻塞但对线程库来说，线程仍然是运行状态

即线程状态是与进程状态独立的

用户级线程的优点和缺点优点：线程切换不调用核心调度是应