操作系统进程管理

第四章进程管理4.1进程(PROCESS)4.2进程控制4.3线程(THREAD)4.4进程互斥和同步4.5进程间通信(IPC,INTER-PROCESSCOMMUNICATION)4.6死锁问题(DEADLOCK)4.7进程其他方面的举例为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。在本章中，我们将讨论进程概念、进程控制和进程间关系。4.1进程(PROCESS)4.1.1程序的顺序执行和并发执行4.1.2进程的定义和描述4.1.3进程的状态转换4.1.4操作系统代码的执行返回4.1.1程序的顺序执行和并发执行•程序的执行有两种方式：顺序执行和并发执行。–顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；–现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。•顺序执行的特征–顺序性：按照程序结构所指定的次序（可能有分支或循环）–封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定–可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。•并发执行的特征–间断(异步)性：走走停停，一个程序可能走到中途停下来，失去原有的时序关系；–失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。–失去可再现性：失去封闭性－失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。并发执行的条件：达到封闭性和可再现性•程序P(i)针对共享变量的读集和写集R(i)和W(i)•条件：任意两个程序P(i)和P(j)，有：–R(i)W(j)=;–W(i)R(j)=;–W(i)W(j)=;并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。（这里没有考虑执行速度的影响。）前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。现在的问题是这个条件不好检查。4.1.2进程的定义和描述•它对应虚拟处理机、虚拟存储器和虚拟外设等资源的分配和回收；•引入多进程，提高了对硬件资源的利用率，但又带来额外的空间和时间开销，增加了OS的复杂性；1.进程的定义一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。2.进程的特征•动态性：进程具有动态的地址空间（数量和内容），地址空间上包括：–代码（指令执行和CPU状态的改变）–数据（变量的生成和赋值）–系统控制信息（进程控制块的生成和删除）•独立性：各进程的地址空间相互独立，除非采用进程间通信手段；•并发性、异步性：虚拟•结构化：代码段、数据段和核心段（在地址空间中）；程序文件中通常也划分了代码段和数据段，而核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）3.进程与程序的区别•进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。•进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。•进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。•进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。4.处理机调度器（dispatcher）•把处理机从一个进程切换到另一个进程；•防止某进程独占处理机；处理机调度器是操作系统中的一段代码，它完成如下功能：5.进程控制块(PCB,processcontrolblock)•每个进程在OS中的登记表项（可能有总数目限制），OS据此对进程进行控制和管理（PCB中的内容会动态改变），不同OS则不同•处于核心段，通常不能由应用程序自身的代码来直接访问，而要通过系统调用，或通过UNIX中的进程文件系统(/proc)直接访问进程映象(image)。文件名为进程标识（如：00316），权限为创建者可读写。进程控制块是由OS维护的用来记录进程相关信息的一块内存。进程控制块的内容•进程描述信息：–进程标识符(processID)，唯一，通常是一个整数；–进程名，通常基于可执行文件名（不唯一）；–用户标识符(userID)；进程组关系(processgroup)•进程控制信息：–当前状态；–优先级(priority)；–代码执行入口地址；–程序的外存地址；–运行统计信息（执行时间、页面调度）；–进程间同步和通信；阻塞原因•资源占用信息：虚拟地址空间的现状、打开文件列表•CPU现场保护结构：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）6.PCB的组织方式•链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表–各状态的进程形成不同的链表：就绪链表、阻塞链表•索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表–各状态的进行形成不同的索引表：就绪索引表、阻塞索引表PCBTableReadyBlockedPCBTableIndexTableReadyBlocked7.进程上下文•用户级上下文：进程的用户地址空间（包括用户栈各层次），包括用户正文段、用户数据段和用户栈；•寄存器级上下文：程序寄存器、处理机状态寄存器、栈指针、通用寄存器的值；•系统级上下文：–静态部分（PCB和资源表格）–动态部分：核心栈（核心过程的栈结构，不同进程在调用相同核心过程时有不同核心栈）进程上下文是对进程执行活动全过程的静态描述。进程上下文由进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成。核心态和用户态•用户态时不可直接访问受保护的OS代码；•核心态时执行OS代码，可以访问全部进程空间。4.1.3进程的状态转换4.1.3.1两状态进程模型4.1.3.2五状态进程模型4.1.3.3挂起进程模型4.1.3.1两状态进程模型Not-RunningRunningDispatchPauseEnterExitProcessorEnterQueueDispatchExitPause(a)状态变迁图(b)队列结构1.状态•运行状态(Running)：占用处理机资源；•暂停状态(Not-Running)：等待进程调度分配处理机资源；2.转换•进程创建(Enter)：系统创建进程，形成PCB，分配所需资源，排入暂停进程表(可为一个队列)；•调度运行(Dispatch)：从暂停进程表中选择一个进程(要求已完成I/O操作)，进入运行状态；•暂停运行(Pause)：用完时间片或启动I/O操作后，放弃处理机，进入暂停进程表；•进程结束(Exit)：进程运行中止；4.1.3.2五状态进程模型两状态模型无法区分暂停进程表中的可运行和阻塞，五状态模型就是对暂停状态的细化。AdmitRunningNewExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseCreate五状态进程模型(状态变迁)AdmitReadyQueueDispatchTime-outEventWaitReleaseProcessorBlockedQueueEventOccurs五状态进程模型(单队列结构)AdmitReadyQueueDispatchTime-outReleaseProcessorEvent1WaitEvent1QueueEvent1OccursEvent2WaitEvent2QueueEvent2Occurs五状态进程模型(多队列结构)1.状态•运行状态(Running)：占用处理机资源；处于此状态的进程的数目小于等于CPU的数目。–在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）。•就绪状态(Ready)：进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配CPU就可执行。–可以按多个优先级来划分队列，如：时间片用完－低优，I/O完成－中优，页面调入完成－高优•阻塞状态(Blocked)：由于进程等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行。如：等待I/O操作的完成。•创建状态(New)：进程刚创建，但还不能运行(一种可能的原因是OS对并发进程数的限制)；如：分配和建立PCB表项（可能有数目限制）、建立资源表格（如打开文件表）并分配资源，加载程序并建立地址空间表。•结束状态(Exit)：进程已结束运行，回收除PCB之外的其他资源，并让其他进程从PCB中收集有关信息（如记帐，将退出码exitcode传递给父进程）。2.转换•创建新进程：创建一个新进程，以运行一个程序。可能的原因为：用户登录、OS创建以提供某项服务、批处理作业。•收容(Admit,也称为提交)：收容一个新进程，进入就绪状态。由于性能、内存、进程总数等原因，系统会限制并发进程总数。•调度运行(Dispatch)：从就绪进程表中选择一个进程，进入运行状态；•释放(Release)：由于进程完成或失败而中止进程运行，进入结束状态；–运行到结束：分为正常退出Exit和异常退出abort（执行超时或内存不够，非法指令或地址，I/O失败，被其他进程所终止）–就绪或阻塞到结束：可能的原因有：父进程可在任何时间中止子进程；•超时（Timeout）：由于用完时间片或高优先进程就绪等导致进程暂停运行；•事件等待（EventWait）：进程要求的事件未出现而进入阻塞；可能的原因包括：申请系统服务或资源、通信、I/O操作等；•事件出现（EventOccurs）：进程等待的事件出现；如：操作完成、申请成功等；注：对于五状态进程模型，一个重要的问题是当一个事件出现时如何检查阻塞进程表中的进程状态。当进程多时，对系统性能影响很大。一种可能的作法是按等待事件类型，排成多个队列。4.1.3.3挂起进程模型•这个问题的出现是由于进程优先级的引入，一些低优先级进程可能等待较长时间，从而被对换至外存。这样做的目的是：–提高处理机效率：就绪进程表为空时，要提交新进程，以提高处理机效率；–为运行进程提供足够内存：资源紧张时，暂停某些进程，如：CPU繁忙（或实时任务执行），内存紧张–用于调试：在调试时，挂起被调试进程（从而对其地址空间进行读写）AdmitRunningNewExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendActivate单挂起进程模型AdmitRunningReadySuspendExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendNewEventOccursActivateSuspendActivateAdmitSuspend双挂起进程模型1.状态•就绪状态(Ready)：进程在内存且可立即进入运行状态；•阻塞状态(Blocked)：进程在内存并等待某事件的出现；•阻塞挂起状态（Blocked,suspend）：进程在外存并等待某事件的出现；•就绪挂起状态（Ready,suspend）：进程在外存，但只要进入内存，即可运行；注：这里只列出了意义有变化或新的状态。2.转换•挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况：–阻塞到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程；–就绪到就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程；–运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态；•激活（Activate）：把一个进程从外存转到内存；可能有以下几种情