计算机操作系统 第二章 进程管理(1)

第二章进程管理本章内容2.1进程的基本概念2.2进程控制2.3进程同步2.4经典的进程同步问题2.5进程通信2.6线程2.1进程的基本概念现代操作系统的基本特征是并发与共享。为了描述程序在并发执行时对资源的共享，我们需要一个概念，来描述程序在执行时的动态特征，这个概念就是进程。进程是资源分配和独立运行的基本单位。2.1.1程序顺序执行及其特征1．程序的顺序执行程序：是一个在时间上按严格次序顺序执行的操作序列，是一个静态的概念。程序的顺序执行：操作系统依次执行一个程序，在程序的整个执行过程中该程序独占处理机等所有的系统资源，直至得到最终结果。顺序执行是单道批处理系统的执行方式。程序的顺序执行给程序的编制、调试带来很大方便，其缺点是计算机系统效率不高。语句的顺序执行：S1：a=x+yS2：b=a-5S3：c=b+1程序段的顺序执行：2．程序顺序执行时的特征（1）顺序性：一个程序各个部分，严格地按照程序结构所规定的次序执行。（2）封闭性：程序在封闭的环境下运行，运行时独占全部系统资源。计算机的状态完全由该程序的控制逻辑决定。程序执行得到的结果由给定的初始条件决定，不受外界因素的影响。（3）可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，将获得相同的结果。在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。2.1.2前趋图为了描述一个程序的各部分（程序段或语句）间的依赖关系，或者是一个大的计算的各个子任务间的前后顺序关系，我们常常采用前趋图方式。前趋图：一个有向无循环图，记为DAG（DirectedAcyclicGraph）。如P27图2-2前趋图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边表示两个结点之间存在的偏序或前趋关系“→”若Pi→Pj，则称Pi是Pj的直接前趋，Pj是Pi的直接后继。初始结点(InitialNode)：没有前趋的结点。终止结点(FinalNode)：没有后继的结点。2.1.3程序的并发执行及其特征1．程序的并发执行多个程序同时进入内存，在一个处理器上交替执行。宏观上并发，微观上是交替。输入I、计算C、打印P三者合作对一批作业进行处理时，存在以下的前趋关系：Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1而Ii+1、Ci和Pi-1之间则可以并发执行。2．程序并发执行时的特征（1）间断性：程序并发执行时，由于它们共享资源或程序之间相互合作完成一项共同任务，致使程序之间相互制约。相互制约将导致并发程序具有“执行——暂停——执行”间断性的活动规律。（2）失去封闭性：多程序共享资源，资源的状态将受多个程序影响而改变，致使每个程序会受其他程序的控制逻辑的影响。（3）不可再现性：失去封闭性－失去可再现性；外界环境在程序的两次执行期间发生变化，也就失去了原有的可重复特征。3．并发执行产生的影响程序并发执行，是为了增强计算机系统的处理能力和提高资源利用率所采取的一种技术。但也导致了资源共享和资源竞争，从而改变程序的执行环境，导致一些在顺序执行方式下可正常工作的程序在并发执行时不能正常工作。为此，操作系统必须通过有效管理来保证并发执行程序的封闭性和可再现性。2.1.4进程的特征与状态1．进程的定义与特征进程概念：进程是一个具有一定独立功能的程序，在一个数据集合上的一次动态运行过程。它是系统进行资源分配和调度的一个独立单位。从操作系统管理的角度出发，进程实体由程序段、相关的数据段和PCB三部分构成。（1）结构特征进程包含了数据集合和运行于其上的程序。为了控制和管理进程，系统为每个进程设立一个进程控制块——PCB，是操作系统用于记录和刻划进程状态及有关信息的数据结构。OS依据PCB对进程进行控制和管理，PCB中的内容会随进程推进而动态改变。进程的特征（2）动态性进程是进程实体的一次执行过程，是动态概念，它具有生命周期，由创建而产生，由调度而执行，由撤销而消亡。同时进程地址空间的大小和内容都是动态变化的。程序是一组有序指令集合，是静态概念，所以，程序作为一种系统资源是永久存在的。进程的特征（3）并发性多个进程同存于内存中，且能同时运行。（4）独立性进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位。各进程的地址空间也相互独立。（5）异步性由于进程间的相互制约，使进程具有执行的间断性，进程按各自独立的、不可预知的速度向前推进。也即并发性。进程的特征2．进程的基本状态一个进程的生命期可以划分为一组状态，这些状态刻划了整个进程。系统根据PCB结构中的状态值控制进程。三态模型五态模型三态模型运行（running）态：占有处理器正在运行。就绪（ready）态：指具备运行条件，等待系统分配处理器以便运行。当进程已分配到除CPU以外的所有必要资源时，它便处于就绪状态，一旦获得CPU，便立即执行。阻塞（blocked）态：也称为等待（wait）态或睡眠（sleep）态，指不具备运行条件，正在等待某个事件的完成。三态的转换一个进程在创建后将处于就绪状态。在进程运行过程中，由于自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：P31等待事件就绪运行阻塞调度超时事件出现进程三态模型及其状态转换三态的转换就绪--运行：调度程序选择一个新的进程运行运行--就绪：运行进程用完了时间片，或出现优先级更高的进程，运行进程被中断，返回就绪队列。运行--阻塞：进程要求的事件未出现或等待某一事件完成而进入阻塞状态。阻塞--就绪：进程等待的事件出现。五态模型引入专门的创建态（New）和退出态（Exit）。创建状态：进程正在创建过程中，还不能运行。OS要创建PCB、建立资源表格并分配资源、加载程序并建立地址空间。退出状态：进程已结束运行，等待系统回收PCB和其他资源（包括PCB中信息）。五态的转换3．挂起状态用户有时希望能人为地暂停进程执行，使之处于静止状态，以便研究其执行情况或对它进行修改。在操作系统引入虚拟存储技术后，需要进一步区分进程地址空间是位于内存还是外存。因而引入挂起状态。挂起状态：进程在外存，等待激活进入内存。分为：就绪挂起和阻塞挂起。（1）引入挂起状态的原因终端用户的请求父进程请求负荷调节的需要操作系统的需要（2）引入挂起后进程状态的转换引入挂起状态后，将原来的就绪状态和阻塞状态进行了细分。单就绪状态分为：活动就绪和静止就绪；单阻塞状态分为：活动阻塞和静止阻塞。引入挂起状态的进程状态图超时引入挂起后进程状态的转换挂起（suspend）：把一个进程的状态改为挂起静止状态，如将进程从内存转到外存。活动就绪静止就绪：当有高优先级阻塞进程和低优先级就绪进程时，系统会选择挂起低优先级进程。活动阻塞静止阻塞：当要求提交新进程或运行就绪进程时，系统要求更多内存资源，会进行此转换。运行静止就绪：对抢占式分时系统，有高优先级阻塞进程因事件出现而进入静止就绪时，系统可能会挂起当前运行进程。引入挂起后进程状态的转换激活（activate）：挂起态到非挂起态的转换，如把一个进程从外存转到内存。静止就绪活动就绪：静止就绪进程优先级高于活动就绪进程或没有了就绪进程时，系统会激活静止就绪进程。静止阻塞活动阻塞：当内存足够时，系统会把一个高优先级静止阻塞进程激活。系统认为会很快出现该进程所等待的事件。被挂起的进程不能参与进程调度，进程进入与结束挂起状态是由操作系统与父进程操作的。2.1.5进程控制块1．进程控制块的作用进程控制块PCB（processcontrolblock）：系统为每个进程配置的一个数据结构，里面存放了用于描述该进程当前情况和控制进程运行所需的全部信息。系统利用PCB来控制和管理进程。进程创建时，系统为之建立一个PCB，进程结束时回收PCB。PCB中的内容会随进程的推进而动态改变，它是系统感知进程存在的唯一标志。系统将所有的PCB组织成若干个链表（队列），存放在操作系统专门开辟的PCB区中。2．进程控制块中的信息（1）进程标识符用于唯一地标识一个进程。进程通常有两种标识符：内部标识符：由系统分配的一个唯一的数值型序号，供系统内部使用。外部标识符：由创建者给出，由文本组成。外部标识符供用户访问该进程使用。此外还有家族关系标识，如父进程标识、子进程标识、用户标识等。2．进程控制块中的信息（2）处理机状态（现场信息）进程运行时各种环境信息保存在CPU的寄存器中。PCB中保存的此信息即断点处CPU中各现场信息。寄存器包括：通用、指令计数器PC、程序状态字PSW、用户/系统栈指针。2．进程控制块中的信息（3）进程调度信息进程当前状态：指明进程当前状态。进程优先级各种计时信息：进程已执行时间总和、占用CPU时间总和、等待时间总和等。事件：等待事件、等待原因2．进程控制块中的信息（4）进程控制信息程序段和数据段指针通信信息：与进程同步和进程通信相关的信息，如消息队列指针、信号量等。资源清单：包括进程所需全部资源、已经分得的资源清单（如主存资源、I/O设备、打开文件表等）。链接指针：给出本进程所在队列中的下一个进程的PCB首址。进程标识当前状态优先数现场保留区指示处于同一状态进程的链指针资源清单进程起始地址家族关系其他3．进程控制块的组织方式（1）链接方式将具有同一状态的PCB链接成一个队列。多个状态的进程对应不同的链表，如就绪队列、若干个阻塞队列、空白队列等。（2）索引方式将同一状态的进程归入一个索引表。根据进程的状态，分别设置几张索引表，如就绪索引表、阻塞索引表等。每个索引表的表目中，记录相应PCB在PCB表中的地址。各索引表在内存的首地址记录在内存的专用单元中。2.2进程控制进程控制的任务：进程控制的功能是创建、撤消进程以及完成进程状态的转换。一般是通过执行OS内核中具有特定功能的程序段——原语操作来实现。操作系统对进程的控制是依据用户命令和系统状态决定的，用户在一定程序上可以对进程的状态进行控制，主要体现在进程的创建与退出、挂起与激活上。内核与原语内核：加在硬件上的第一层软件，通过执行各种原语操作来实现各种控制和管理功能，具有创建进程、撤消进程、进程通信、资源管理的功能。内核的基本功能：支撑功能：中断处理、时钟管理、原语操作资源管理功能：进程管理、存贮管理、设备管理原语：是由若干条机器指令构成，用以完成特定功能的一段程序。原语程序段是一个不可分割的基本单位，不可以并发执行。即原语是原子操作，要么全做，要么全部不做。2.2.1进程的创建1．进程图（PorcessGraph）用于描述一个进程家族关系的有向树。如P43图2-11：一棵树代表一个家族，图中结点代表进程，根结点为该进程家族的祖先。子进程创建：子进程继承父进程所拥有的资源，父子进程常常要相互通信和协作。子进程结束：要求父进程对其作某些善后处理，将从父进程那里获得的资源归还父进程。父进程撤消：将撤消所有的子进程2．引起创建进程的事件（1）用户登录：分时系统中系统将为每一个合法注册用户建立一个进程。（2）作业调度（3）提供服务：运行中的进程提出请求后，系统将为之专门创建一个服务进程提供需要的服务。（4）应用请求（父进程创建子进程）3．进程的创建无论是系统创建还是父进程创建，都必须调用创建原语creat()来实现。其操作步骤：（1）申请空白PCB。为新进程获得一个惟一的进程标识符，并从PCB总链中申请空白PCB。（2）为新进程分配资源。包含程序段、数据段、用户栈的内存空间。（3）初始化进程控制块：进程标识、状态、优先级、进程开始地址、初始CPU状态、资源清单等（4）设置相应的链接：把新进程添加到就绪队列的链表中2.2.2进程的终止一个进程完成了特定的工作或出现了严重的异常后，操作系统则收回它占有的地址空间和进程控制块，此时就说撤销了一个进程。1．引起进程终止的事件（1）正常结束：进程已完成所要求的工作。（2）异常结束越界错、保护错、特权指令错、非法指令、运行超时、等待超时、运算错、I/O故障等（3）外界干预：进程应外界的请求而终止运行操作员或OS干预、父进程请求撤销子