进程和处理机管理.pptx

第第3章章 进程和处理机管理进程和处理机管理 目录目录 3 31 1 进程的概念和定义进程的概念和定义进程的概念和定义进程的概念和定义 3 32 2 进程的状态和进程控制块进程的状态和进程控制块进程的状态和进程控制块进程的状态和进程控制块 3.3 3.3 进程控制进程控制 3 34 4 进程的互斥与同步进程的互斥与同步 3.5 3.5 进程通信进程通信 3 36 6 进程调度进程调度 3 37 7 死锁死锁 3 38 8 线程线程31 进程的概念和定义进程的概念和定义 操作系统是一个动态系统，在持续的运动过程中完操作系统是一个动态系统，在持续的运动过程中完成各种使命、实现各项功能。因此，要了解操作系成各种使命、实现各项功能。因此，要了解操作系统各模块间的动态连接关系和相互制约关系就不能统各模块间的动态连接关系和相互制约关系就不能用静态的程序概念来刻画操作系统。因此引进一个用静态的程序概念来刻画操作系统。因此引进一个新的观点新的观点进程观点，以便钻进操作系统内部去进程观点，以便钻进操作系统内部去观察操作系统各模块的动态变化情况观察操作系统各模块的动态变化情况。3 31 11 1 为什么引入进程为什么引入进程3 31 12 2 进程的定义进程的定义311 为什么引入进程n n应该说，组织用户使用计算机的机制是随着计算机操作系应该说，组织用户使用计算机的机制是随着计算机操作系统的发展而进化的。在监督程序时代是以作业形势表示程统的发展而进化的。在监督程序时代是以作业形势表示程序运行的。那时，作业以同步方式串行地运行每个作业步。序运行的。那时，作业以同步方式串行地运行每个作业步。当操作系统发展到分时系统时，为了开发同一个作业中不当操作系统发展到分时系统时，为了开发同一个作业中不同作业步之间的并发，作业机制已不能满足需要，因而引同作业步之间的并发，作业机制已不能满足需要，因而引进了进程机制，让进程来实现作业步的执行。但随着多处进了进程机制，让进程来实现作业步的执行。但随着多处理机计算机的出现，用户希望一个作业步中的程序还能够理机计算机的出现，用户希望一个作业步中的程序还能够同时在多个处理机上运行，因此进程的机制得到了进一步同时在多个处理机上运行，因此进程的机制得到了进一步发展，让一个进程同时拥有多个线程，让多个线程在不同发展，让一个进程同时拥有多个线程，让多个线程在不同处理机上运行。处理机上运行。n n1.算法算法n n我们可以把算法定义为：问题求解步骤我们可以把算法定义为：问题求解步骤的精确描述。算法具有如下性质：的精确描述。算法具有如下性质：n n解题算法是一个有穷动作序列；解题算法是一个有穷动作序列；n n动作序列仅有一个初始动作；动作序列仅有一个初始动作；n n序列中每一个动作仅有一个后继动作；序列中每一个动作仅有一个后继动作；n n序列终止表示问题解决还是没有得到解序列终止表示问题解决还是没有得到解决。决。n n2.2.程序程序程序程序n n程序是对一个复杂的计算（问题）用一种形程序是对一个复杂的计算（问题）用一种形程序是对一个复杂的计算（问题）用一种形程序是对一个复杂的计算（问题）用一种形式化的语言对其初始数据与操作进行形式化式化的语言对其初始数据与操作进行形式化式化的语言对其初始数据与操作进行形式化式化的语言对其初始数据与操作进行形式化描述的一个算法。描述的一个算法。描述的一个算法。描述的一个算法。n n当一个程序在运行之际，可以区分出三个不当一个程序在运行之际，可以区分出三个不同的实体。同的实体。n n(1)(1)用来描述过程的一组指令，即用来描述过程的一组指令，即“过程过程”；n n(2)(2)处理机，即执行该过程的机构；处理机，即执行该过程的机构；n n(3)(3)环境，即处理机能够直接感知或能够加以环境，即处理机能够直接感知或能够加以改造的那个外部世界。改造的那个外部世界。“一切听从程序的指一切听从程序的指挥挥”。2.程序n n因此因此,程序的主要特点是：程序的主要特点是：n n(1)(1)按按“过程过程”所规定的操作，以严格顺序来执行，每所规定的操作，以严格顺序来执行，每一步都应在下一步开始之前完成（不存在并行）。这一步都应在下一步开始之前完成（不存在并行）。这一特点就是我们所说的程序的顺序性。一特点就是我们所说的程序的顺序性。n n(2)(2)环境处在环境处在“程序程序”的完全控制之下，它决不以任何的完全控制之下，它决不以任何方式变化，除非这种变化是程序所采取的步骤导致的方式变化，除非这种变化是程序所采取的步骤导致的结果。这个特点被称为程序的封闭性。结果。这个特点被称为程序的封闭性。n n(3)(3)除了要求在合理的时间内获得结果外，任一操作所除了要求在合理的时间内获得结果外，任一操作所花费的时间对程序的运行而言是无关紧要的，即使在花费的时间对程序的运行而言是无关紧要的，即使在任一操作之间有一暂时间歇也没有关系。程序所产生任一操作之间有一暂时间歇也没有关系。程序所产生的结果是其输入数据的函数而与时间无关。只要程序的结果是其输入数据的函数而与时间无关。只要程序执行的初始条件相同，其结果是可以再现的执行的初始条件相同，其结果是可以再现的 。3.程序的并行执行和资源的共享n n为了合理地使用系统资源，充分发挥各种资源的为了合理地使用系统资源，充分发挥各种资源的作用，最大限度地提高系统的效率，引进多道程作用，最大限度地提高系统的效率，引进多道程序设计技术。又由于计算机技术的不断发展而出序设计技术。又由于计算机技术的不断发展而出现了中断技术、分时处理和各种新型结构，如多现了中断技术、分时处理和各种新型结构，如多CPUCPU系统的出现，导致现代操作系统出现了许多系统的出现，导致现代操作系统出现了许多诸如并发性资源共享性等许多新的特征。诸如并发性、资源共享性等许多新的特征。n n（1 1）并行操作）并行操作 n n（2 2）资源共享）资源共享4.程序并行执行的特征n n程序的并行执行虽然增加了系统的处理能力和机器的利用率，但也产生了与顺序程序不同的新特征。n n（1）失去了程序的封闭性n n（2）程序并行执行时的相互制约关系312 进程的定义n n通过上述分析可知，程序在并行执行时已不能通过上述分析可知，程序在并行执行时已不能通过上述分析可知，程序在并行执行时已不能通过上述分析可知，程序在并行执行时已不能描述不封闭性和描述不封闭性和描述不封闭性和描述不封闭性和“执行执行执行执行-暂停暂停暂停暂停-执行执行执行执行”活动规律，活动规律，活动规律，活动规律，需要有一种新的概念工具来描述下列特征：需要有一种新的概念工具来描述下列特征：需要有一种新的概念工具来描述下列特征：需要有一种新的概念工具来描述下列特征：n n能描述能描述能描述能描述“计算计算计算计算”这一现象；这一现象；这一现象；这一现象；n n能描述能描述能描述能描述“执行执行执行执行-暂停暂停暂停暂停-再执行再执行再执行再执行”这一活动规律；这一活动规律；这一活动规律；这一活动规律；n n能为并行执行的能为并行执行的能为并行执行的能为并行执行的“计算计算计算计算”的制约关系提供协调的制约关系提供协调的制约关系提供协调的制约关系提供协调和共享资源的机构。和共享资源的机构。和共享资源的机构。和共享资源的机构。n n这样的新概念称为进程或任务。这样的新概念称为进程或任务。这样的新概念称为进程或任务。这样的新概念称为进程或任务。2.进程与程序的主要区别n n(1)(1)程序只是指令的有序集合，是静态的描述，没有运程序只是指令的有序集合，是静态的描述，没有运行的含义，所以程序是静止的；进程是程序的一次运行的含义，所以程序是静止的；进程是程序的一次运行活动，是动态的概念。行活动，是动态的概念。n n(2)(2)进程是一个独立运行的单位，共享资源的实体，能进程是一个独立运行的单位，共享资源的实体，能与其他进程并发执行，而程序则不然。操作系统中以与其他进程并发执行，而程序则不然。操作系统中以资源管理的中心思想来看，进程可以看成是资源的顾资源管理的中心思想来看，进程可以看成是资源的顾客和使用者。客和使用者。n n(3)(3)一个程序可以对应多个进程，反过来，一个进程至一个程序可以对应多个进程，反过来，一个进程至少对应一段程序。逻辑上，每个进程有自己的处理机少对应一段程序。逻辑上，每个进程有自己的处理机和程序，实际上两个进程可以共享同一段程序或同一和程序，实际上两个进程可以共享同一段程序或同一个处理机，所以进程不等价于程序，也不等价于处理个处理机，所以进程不等价于程序，也不等价于处理机，它是执行期间的机，它是执行期间的 对。对n n(4)(4)静态地观察进程，其实体是由程序和数据两部分构静态地观察进程，其实体是由程序和数据两部分构成，与程序没有什么区别。成，与程序没有什么区别。3.进程的特征n n进程具有如下的特征：进程具有如下的特征：n n（1 1）动态特征）动态特征n n进程的实质是并行程序的一次执行过程，因此，动态特征是进程进程的实质是并行程序的一次执行过程，因此，动态特征是进程的最基本的特征。其动态性表现在它可以由创建而产生、由调度的最基本的特征。其动态性表现在它可以由创建而产生、由调度而执行、由于得不到资源而暂停，由撤消而消亡。进程存在一个而执行、由于得不到资源而暂停，由撤消而消亡。进程存在一个生命周期生命周期。n n（2 2）并行特征）并行特征n n引入进程的目的是使程序能并行执行，以提高资源的利用率。引入进程的目的是使程序能并行执行，以提高资源的利用率。n n（3 3）独立特征）独立特征n n进程是独立运行的单位，也是系统进行资源分配和调度的独立单进程是独立运行的单位，也是系统进行资源分配和调度的独立单位。位。n n（4 4）异步特征）异步特征n n进程按照各自独立的，不可预知的速度向前推进，所以要求系统进程按照各自独立的，不可预知的速度向前推进，所以要求系统提供某种设施使进程间能协调操作和共享资源，保证它们协调运提供某种设施使进程间能协调操作和共享资源，保证它们协调运行。行。n n（5 5）结构特征）结构特征n n进程是有结构的，体现在每个进程有一个记录进程当前信息的进进程是有结构的，体现在每个进程有一个记录进程当前信息的进程控制块（程控制块（PCB Process Control BlockPCB Process Control Block）。每个进程都是由一个程）。每个进程都是由一个程序段和相应数据集以及进程控制块三部分组成。在序段和相应数据集以及进程控制块三部分组成。在UNIXUNIX操作系统操作系统中将这三部分称为中将这三部分称为“进程映象进程映象”，它把进程定义为：进程映象的，它把进程定义为：进程映象的执行。执行。n n引入进程这一概念后，就可以很方便地动态地引入进程这一概念后，就可以很方便地动态地描述操作系统了，但引入进程也有不利之处：描述操作系统了，但引入进程也有不利之处：n n(1)(1)必须为设置进程付出一定的空间开销，因为必须为设置进程付出一定的空间开销，因为并行执行的操作系统本身就复杂，如，必须设并行执行的操作系统本身就复杂，如，必须设置进程管理并为并行执行的各进程之间的同步置进程管理并为并行执行的各进程之间的同步和协调建立某些机构，由于并行执行就必须考和协调建立某些机构，由于并行执行就必须考虑避免死锁等问题而使系统复杂化。另外，每虑避免死锁等问题而使系统复杂化。另外，每个进程都必须有一个进程控制块（个进程都必须有一个进程控制块（PCBPCB），它），它也占用了一部分内存空间。也占用了一部分内存空间。n n(2)(2)必须为设置进程付出一定的时间开销，因为必须为设置进程付出一定的时间开销，因为运行一个复杂的系统软件将花费更多的处理机运行一个复杂的系统软件将花费更多的处理机时间。时间。32 进程的状态和进程控制块进程的状态和进程控制块n n3 32 21 1 进程的状态进程的状态进程的状态进程的状态n n进程是动态的，它存在着生命周期。它有诞生进程是动态的，它存在着生命周期。它有诞生（创建）和灭亡（撤消）过程，在它的生命周期（创建）和灭亡（撤消）过程，在它的生命周期中又反映出它的执行中又反映出它的执行-暂停暂停-再执行的活动规律进再执行的活动规律，进程最主要的特征是具有状态。进程在其活动期间程最主要的特征是具有状态。进程在其活动期间具有两种状态：自由状态和等待状态。任一进程具有两种状态：自由状态和等待状态。任一进程在任一时刻有且只有这两种状态之一。自由状态在任一时刻有且只有这两种状态之一。自由状态又可分为：运行状态和就绪状态。又可分为：运行状态和就绪状态。321 进程的状态n n就绪状态（Ready）该进程已经获得了除了处理机以外的全部资源并准备好运行，但由于进程数多于处理机数目，所以此进程不能占用处理机执行，一旦为其分配到处理机该进程便立即执行。321 进程的状态n n执行状态（Executive）进程获得了处理机等必要的资源，该进程已占用处理机，其程序正在处理机上执行。321 进程的状态n n阻塞状态（Block）正在执行中的进程，由于发生了某一事件而使之暂时无法执行下去（如，等待I/O操作完成，或由于同步、互斥而等待）而处于暂停状态，即该进程的运行受到了阻塞（即等待状态或睡眠状态）。进程的三种不同状态进程的三种不同状态 就 绪阻 塞执 行 进程的状态322 进程的状态演变n进程的状态不是一成不变的，它是随着自身的推进和外界条件的变化而变化的。下图为简单的进程状态演变图及演变事由。进程调度执 行就 绪阻 塞事件结束时间片到图3-5 简单的进程状态演变图n n应该说明的是应该说明的是:n n（1 1）在在进进程程的的生生命命周周期期中中，处处于于执执行行状状态态的的进进程程因因为为某某一一事事件件（如如I/OI/O请请求求等等事事件件）出出现现而而变变成成阻阻塞塞状状态态，当当该该事事件件消消除除后后，被被阻阻塞塞的的进进程程并并不不恢恢复复到到执执行行状状态态，而而转转变变为为就就绪绪状状态态等等待待再再一一次次重重新新被被进进程程调调度度程程序序调调度度。这这是是因因为为当当该该进进程程被被阻阻塞塞时时，为为了了使使处处理理机机不不空空闲闲，进进程程调调度度程程序序立立即即将将处处理理机机分配给另一个处于就绪状态的进程。分配给另一个处于就绪状态的进程。n n（2 2）当当进进程程从从运运行行状状态态变变为为就就绪绪或或阻阻塞塞状状态态时时，必须保留它的运行的现场信息，以便将来恢复运行。必须保留它的运行的现场信息，以便将来恢复运行。n n（3 3）处于同一状态的进程可以构成队列，系统中）处于同一状态的进程可以构成队列，系统中可以有一个运行队列、但是在只有一个处理机的情可以有一个运行队列、但是在只有一个处理机的情况下，任一时刻处于运行状态的进程只能有一个。况下，任一时刻处于运行状态的进程只能有一个。系统中可以有一个或多个就绪队列和若干个等待队系统中可以有一个或多个就绪队列和若干个等待队列，由于同一个原因而等待的进程应该属于同一个列，由于同一个原因而等待的进程应该属于同一个等待队列，相应每个队列设有指针，指向相应队列等待队列，相应每个队列设有指针，指向相应队列的首部。的首部。相应队列指针名称状态现场优先数指针Proc2Run870Proc3Block785Proc4Block750Proc5Block650Proc6Ready518Proc7Block449Proc8Ready37nProc9Block290ProcnReady1026137runningreadyC1C2C3CmProc1Block894 进程队列 时间片到进程调度事件结束某一事件用户提交收容就绪阻塞完成用户执行进程状态模型进程调度发生某一事件时间片到挂起唤醒执 行活动就绪静止就绪活动阻塞激活挂起唤醒激活挂起静止阻塞创建具有挂起状态的进程状态转换图323 进程控制块（Process control block）n n在进程的生命周期中，进程可以处于各种不同的状态，如何描述进程及其状态？进程控制块是表示进程存在的唯一实体。当创建一个进程时，必须为其设置一个进程控制块（PCB），由它对进程进行管理和控制。n n不同系统的进程控制块所包含的信息不尽相同，大体上都包括以下几项：n n（1）进程标识符（Identification）n n（2）现行状态（Status）n n（3）CPU状态保护区n n（4）进程程序的起始地址n n（5）资源清单n n（6）进程优先数n n（7）队列指针或队列表n n（8）进程的家族信息3.3 进程控制进程控制 进程控制的功能是对系统中的全部进程实施有效的管理，它有创建进程和撤消进程的能力。1.进程家族与分类 2.进程控制的基本操作331 进程家族与分类n n1.进程家族进程家族n n进程的家族结构有两种：一种是非结构系进程的家族结构有两种：一种是非结构系统；另一种是树型结构系统统；另一种是树型结构系统。n n在非结构系统中管理程序直接对全部进程实施管理，它可以实施创建进程和撤消进程等操作。各进程之间的关系也是“平等”的。n n在树型结构的进程家族中，一个父进程可以创建一个子进程而形成一个进程家族。如图3-9（a）给出了非结构系统进程家族示意图;图3-9b）给出了树型结构的进程家族的示意图。进程A进程n进程B管理程序(a)ABCDEFHGIJK(b)进程家族的结构1.进程家族n n进程的家族结构有两种：一种是非结构系统；另一种是树型结构系统。在非结构系统中管理程序直接对全部进程实施管理，它可以实施创建进程和撤消进程等操作。各进程之间的关系也是“平等”的，如图3-9（a）所示。在树型结构的进程家族中，一个父进程可以创建一个子进程而形成一个进程家族。图3-9（b）给出了树型结构的进程家族的示意图。1.进程家族进程A进程n进程B管理程序(a)ABCDEFBHGIJK(b)图3-9 进程家族的结构1.进程家族n n树型结构的优点是：树型结构的优点是n n（1 1）资源分配严格，子进程可以分配到父进程所）资源分配严格，子进程可以分配到父进程所拥有的资源，用完后立即归还，一个进程家族所拥有的资源，用完后立即归还，一个进程家族所占有的全部资源应该在其祖先所拥有的资源范围占有的全部资源应该在其祖先所拥有的资源范围内。内。n n（2 2）进程的控制灵活，当一个进程被分配完成某）进程的控制灵活，当一个进程被分配完成某一任务时，它能够创建若干进程去分别完成各子一任务时，它能够创建若干进程去分别完成各子功能。功能。n n（3 3）进程层次清晰，关系明确。所以，树型结构）进程层次清晰，关系明确。所以，树型结构的系统获得了广泛应用。的系统获得了广泛应用。2进程分类n n进程按服务对象可分为：进程按服务对象可分为：系统进程系统进程系统进程系统进程与与用户进程用户进程用户进程用户进程。完成指定的系统功能的进程称为系统进程；完成完成指定的系统功能的进程称为系统进程；完成用户作业所需做的工作的进程称为用户进程，如，用户作业所需做的工作的进程称为用户进程，如，编译、运行系统等。系统进程按其占内存的情况编译、运行系统等。系统进程按其占内存的情况又可分为：长存进程和暂存进程两大类，长存进又可分为：长存进程和暂存进程两大类，长存进程的数据块、程序块等长期驻留在内存；暂存进程的数据块、程序块等长期驻留在内存；暂存进程的程序块等不是长期驻留在内存中，需要时才程的程序块等不是长期驻留在内存中，需要时才把它们调入内存。把它们调入内存。332 进程控制的基本操作n n为了对进程进行控制和通信，在系统中必须设置为了对进程进行控制和通信，在系统中必须设置一个机构，它具有创建、撤消、进程通信和资源一个机构，它具有创建、撤消、进程通信和资源管理等功能，这样的机构称为操作系统的内核管理等功能，这样的机构称为操作系统的内核（KernelKernel），系统的其他部分是由它们建造的），系统的其他部分是由它们建造的。内内核本身并非一个进程，而是一组基本原语操作，核本身并非一个进程，而是一组基本原语操作，是由软件实现的内核功能，内核通过执行各种原是由软件实现的内核功能，内核通过执行各种原语操作来实现各种控制和管理功能。内核是硬件语操作来实现各种控制和管理功能。内核是硬件的首次延伸，它扩大了的首次延伸，它扩大了CPUCPU的功能。的功能。n n原语是机器指令的延伸，是由若干条机器指令构成的用以完成特定功能的一段程序，为了保证操作的正确性，原语在执行期间是不可分割的。引入原语的目的是允许进程内部并行操作，且可以动态地创建一个进程；允许系统生成许多不同的版本以适应不同用户的需要，系统执行时灵活组装成不同的操作系统；使系统结构清晰。用于对进程进行管理和控制操作的基本原语有：n n创建原语创建原语(Create)(Create)n n撤消原语（撤消原语（DestroyDestroy）n n以上两个原语使进程从无到有，从有到无。以上两个原语使进程从无到有，从有到无。n n唤醒原语（唤醒原语（WakeupWakeup）n n阻塞原语（阻塞原语（BlockBlock）n n以上两个原语使进程发生各种状态变化。以上两个原语使进程发生各种状态变化。n n挂起原语（挂起原语（SuspendSuspend）n n激活原语激活原语 （Action)Action)n n以上两个原语使进程从活动到静止以上两个原语使进程从活动到静止,从静止到从静止到活动。活动。34 进程的互斥与同步进程的互斥与同步 进程的状态是基于一定的原因和条件而变化的，进程的状态是基于一定的原因和条件而变化的而这些原因和条件又常常是由于进程之间的相互而这些原因和条件又常常是由于进程之间的相互制约关系而引起的。系统中诸进程之所以有这种制约关系而引起的。系统中诸进程之所以有这种关系，主要原因是由于进程对资源的共享性，由关系，主要原因是由于进程对资源的共享性，由于这种共享的特征，使系统中本来没有逻辑关系于这种共享的特征，使系统中本来没有逻辑关系的进程因为互相竞争资源而产生了制约关系。这的进程因为互相竞争资源而产生了制约关系。这种关系的基本形式是：种关系的基本形式是：“进程进程资源资源进程进程”，这是进程间通过资源而发生的一种间接关系。由这是进程间通过资源而发生的一种间接关系。由于系统对进程所请求的许多资源常常是互斥满足于系统对进程所请求的许多资源常常是互斥满足的，所以这种关系表现为互斥关系（竞争关系）。的，所以这种关系表现为互斥关系（竞争关系）。n n系统中为了完成同一个任务而创建了若干进程，它们之间必然是伙伴进程（进程合作），如某作业的一组并行进程共同完成一项任务，有时它们要在某点上互相等待和互通消息，这种关系的基本形式是：“进程进程”，这是进程之间的一种直接关系，表现了进程之间的协同工作的特性，称为进程间的同步关系。341 临界区（Critical section）n n计算机中的某些资源是共享资源，但是有些共计算机中的某些资源是共享资源，但是有些共享资源具有如下特征：即一次仅允许一个进程享资源具有如下特征：即一次仅允许一个进程使用，我们把一次仅允许一个进程使用的资源使用，我们把一次仅允许一个进程使用的资源称为称为“临界资源临界资源”（Critical resourceCritical resource）。例如，）。例如，有两个进程有两个进程A A，B B共享一台打印机，若让它们任共享一台打印机，若让它们任意使用，则可能将两个进程的输出结果交织在意使用，则可能将两个进程的输出结果交织在一起，很难区分。为了解决这一问题，可以在一起，很难区分。为了解决这一问题，可以在A A进程使用打印机时先申请，一旦系统将打印进程使用打印机时先申请，一旦系统将打印机分配给机分配给A A进程后就由它一直占用，此时若进程后就由它一直占用，此时若B B进进程也要使用打印机就必须等待，直到程也要使用打印机就必须等待，直到A A进程用进程用完释放打印机后完释放打印机后B B进程方可使用，即它们必须进程方可使用，即它们必须互斥地使用打印机。这里打印机就是一种临界互斥地使用打印机。这里打印机就是一种临界资源。资源。n访问临界资源的那段程序称之为“临界区”。为了使临界资源互斥地被使用，必须使临界区互斥地被执行，即诸进程访问临界区时必须互斥。为了做到禁止一组进程同时访问它们的临界区，而提出了临界区的准则如下：n n（1 1）不能假设各并发进程的相对执行速度，）不能假设各并发进程的相对执行速度，即各并发进程享有平等的、独立的竞争共有资即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以临界区内任一指令结束时，其他并发进程可以进入临界区。进入临界区。n n（2 2）当有若干进程欲访问它们的临界区时，）当有若干进程欲访问它们的临界区时，应在有限时间内使一个进程访问临界区，不应应在有限时间内使一个进程访问临界区，不应互相阻塞而彼此都无法访问，这就是有空让进互相阻塞而彼此都无法访问，这就是有空让进的原则，使共享资源能够充分利用。的原则，使共享资源能够充分利用。n n（3 3）每次至多有一个进程处于临界区内，这）每次至多有一个进程处于临界区内，这体现了互斥的基本含义。体现了互斥的基本含义。n n（4 4）进程仅在临界区内逗留有限时间，使等）进程仅在临界区内逗留有限时间，使等待访问临界区的进程是有限等待待访问临界区的进程是有限等待 。n n由上述准则得临界区的调度原则如下：n n（1）当无进程访问临界区时，允许一个进程立即访问其临界区。n n（2）当某一进程已访问了它的临界区时，其他试图访问临界区的进程必须等待。n n（3）当某一进程离开临界区时，若有等待访问临界区的进程，则允许其中的一个进程进入临界区访问。342 进程互斥n n1.1.互斥的加锁实现互斥的加锁实现互斥的加锁实现互斥的加锁实现n n这是一种借助一条硬指令这是一种借助一条硬指令这是一种借助一条硬指令这是一种借助一条硬指令TestTest和和和和SetSet来实现互斥的一种同步来实现互斥的一种同步来实现互斥的一种同步来实现互斥的一种同步机构。此方法是对临界区加锁以实现互斥。当某个进程进机构。此方法是对临界区加锁以实现互斥。当某个进程进机构。此方法是对临界区加锁以实现互斥。当某个进程进机构。此方法是对临界区加锁以实现互斥。当某个进程进入临界区之后，为了阻止其他进程进入临界区，它将锁上入临界区之后，为了阻止其他进程进入临界区，它将锁上入临界区之后，为了阻止其他进程进入临界区，它将锁上入临界区之后，为了阻止其他进程进入临界区，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区，直到它退出临界区时为止。并发进程在申请进入临界区，直到它退出临界区时为止。并发进程在申请进入临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界临界区时，首先测试该临界区是否是上锁的。如果该临界临界区时，首先测试该临界区是否是上锁的。如果该临界临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能区已被锁住，则该进程要等到该临界区开锁之后才有可能区已被锁住，则该进程要等到该临界区开锁之后才有可能区已被锁住，则该进程要等到该临界区开锁之后才有可能进入临界区。为此设置一个变量进入临界区。为此设置一个变量进入临界区。为此设置一个变量进入临界区。为此设置一个变量WW，代表临界区的状态，代表临界区的状态，代表临界区的状态，代表临界区的状态，WW也称为锁或锁位。当也称为锁或锁位。当也称为锁或锁位。当也称为锁或锁位。当W=0W=0时，表示临界区可以进入；当时，表示临界区可以进入；当时，表示临界区可以进入；当时，表示临界区可以进入；当W=1W=1时，表示临界区已被占用，企图进入临界区的进程必时，表示临界区已被占用，企图进入临界区的进程必时，表示临界区已被占用，企图进入临界区的进程必时，表示临界区已被占用，企图进入临界区的进程必须等待。须等待。须等待。须等待。n n关锁原语Lock w:n n关锁原语关锁原语n n l:if w=1 then goto l else w:=1；n n开锁原语开锁原语n n开锁原语 unlock w:n n w:=0n n下面的程序表示了两个并行的循环进程用关锁和开锁原语实现互斥的情况(CS1和CS2表示两个进程的各自临界区)。n nBegin integer w;Begin integer w;n n W:=0;W:=0;n nCobegin process1Cobegin process1n n Begin Begin n n L1:lock w;L1:lock w;n n CS1;CS1;n n Unlock;Unlock;n n Program1;Program1;n n Goto L1;Goto L1;n n End Endn n Process2 Process2n n Begin Beginn n L2:lock w;L2:lock w;n n CS2;CS2;n n Unlock;Unlock;n n Program2;Program2;n n Goto L2;Goto L2;n n End Endn nCoendCoendn nEndEndn n这样的一个同步机构能有效地保证进程互斥地这样的一个同步机构能有效地保证进程互斥地访问临界区，但对于不能进入临界区的进程却访问临界区，但对于不能进入临界区的进程却在不断地测试锁位在不断地测试锁位WW，以等待它为零，这就造，以等待它为零，这就造成了处理机时间的浪费。改进的方法是将忙式成了处理机时间的浪费。改进的方法是将忙式等待改成忙式挂起，当某进程所需临界资源被等待改成忙式挂起，当某进程所需临界资源被占用时，应使该进程阻塞，把它插入到等待队占用时，应使该进程阻塞，把它插入到等待队列中，此时列中，此时CPUCPU分配给其他进程，一旦该资源分配给其他进程，一旦该资源被释放就立即检查等待队列，若等待队列空，被释放就立即检查等待队列，若等待队列空，则开锁表示资源可以使用；若等待队列不空，则开锁表示资源可以使用；若等待队列不空，则从该等待队列中移出一个进程，将其置于就则从该等待队列中移出一个进程，将其置于就绪状态并插入就绪队列。修改后的关锁和开锁绪状态并插入就绪队列。修改后的关锁和开锁原语如下：原语如下：n n关锁原语关锁原语n nLock w:if w=1 then Lock w:if w=1 then 测试测试WW的值的值n n Begin Begin n n Block(n);insert(wl,n);scheduler Block(n);insert(wl,n);scheduler 若临界区中有进程，则阻塞自若临界区中有进程，则阻塞自己并插入到等待队列中，此时己并插入到等待队列中，此时CPUCPU空闲，引起进程调度。空闲，引起进程调度。n n EndEndn n Else w:=1;Else w:=1;若临界区中无进程，则关锁表示占若临界区中无进程，则关锁表示占用用n n开锁原语开锁原语 临界区；临界区；n nUnlock w:if wlnull then Unlock w:if wlnull then 若等待队列不空，则若等待队列不空，则n n BeginBeginn n Remove(wl,q);Remove(wl,q);从等待队列中移出从等待队列中移出q q，n n Status(q):=ready;Status(q):=ready;将进程将进程q q置于就绪状态，置于就绪状态，n n Insert(rl,q);Insert(rl,q);将其插入就绪队列。将其插入就绪队列。n n EndEndn n W:=0;W:=0;开锁。开锁。n n2信号量和信号量和P,V操作操作n n荷兰计算机科学家荷兰计算机科学家E.W.Dijkstra于于1965年年提出了信号量的概念，并引入两个新的提出了信号量的概念，并引入两个新的原语操作原语操作P和和V（P和和V分别是荷兰语分别是荷兰语Passeren和和Verhoog的第一个字母，相当的第一个字母，相当于英文的于英文的Pass和和Increment的意思）。采的意思）。采用用P,V操作原语，大大简化了进程的同步操作原语，大大简化了进程的同步和互斥的实现。和互斥的实现。P和和V这两个原语操作在这两个原语操作在非负整形变量上，这些变量称为信号量。非负整形变量上，这些变量称为信号量。n n信号量是表示资源的物理实体，是一个与队列信号量是表示资源的物理实体，是一个与队列有关的整形变量，其值仅能由有关的整形变量，其值仅能由P P和和V V操作来改变。操作来改变。操作系统利用它的状态对进程和资源进行管理。操作系统利用它的状态对进程和资源进行管理。n n按信号量的用途不同可将其分为：按信号量的用途不同可将其分为：n n 公用信号量。公用信号量。它联系着一组并行进程，初它联系着一组并行进程，初始值为始值为1 1，每个进程都可以对它施加，每个进程都可以对它施加P P或或V V操作，操作，通常它是为实现进程的互斥而设置。通常它是为实现进程的互斥而设置。n n 私用信号量。私用信号量。它联系着一组共行进程，初它联系着一组共行进程，初始值为始值为0 0或某个正整数或某个正整数n n，仅允许拥有它的进程，仅允许拥有它的进程对它施加对它施加P P操作，通常用来实现进程的同步。操作，通常用来实现进程的同步。n nP操作n nP操作记为P(S),其中S为一个信号量的值，每执行一次P操作，就意味着申请一个单位的资源，由于信号量的值用来表示资源数量，所以执行一次P操作，信号量的值就减1。此时若S0，则进程继续执行；若S0则阻塞该进程，并将其插入到该信号量的等待队列中等待。n nProcedure P(S)Procedure P(S)n nBeginBeginn n Lock out interrupts;Lock out interrupts;关中断；关中断；n n S:=S-1;S:=S-1;信号量的值减信号量的值减1 1；n n If S0 then begin If S0 then begin 如果如果s0s0，说明已经没有此，说明已经没有此类资源，故进程类资源，故进程n n Status(q):=block;qStatus(q):=block;q的申请得不到满足，将其的申请得不到满足，将其阻塞；阻塞；n n Insert(Q,q);Insert(Q,q);将将q q插入到该资源的等待队列插入到该资源的等待队列中；否则继续中；否则继续n n Unlock interrupts;Unlock interrupts;开中断；开中断；n nEnd;End;n n请读者注意，程序中为什么判断请读者注意，程序中为什么判断S0S0则进程继续执行；若S0则从信号量的等待队列中移出一个进程并赋予该进程为就绪状态，将其插入到就绪队列中。n nProcedure V(S)Procedure V(S)n nBeginBeginn n Lock out interrupts;Lock out interrupts;关中断；关中断；n n SS+1;S:=S+1;信号量的值加信号量的值加1 1；n n If S0 then begin If S0 then begin 如果如果S0S0，说明有等待该，说明有等待该资源的进程；资源的进程；n nRemove(Q,r);Remove(Q,r);则将该进程从等待队列中移则将该进程从等待队列中移出；出；n nStatus:=ready;Status:=ready;并将其状态改为就绪；并将其状态改为就绪；n nInsert(RL,r);end;Insert(RL,r);end;插入到就绪队列；插入到就绪队列；n n Unlock interrupts;Unlock interrupts;