《进程和处理机管理》PPT课件.ppt

第3章进程和处理机管理,目录,31进程的概念和定义32进程的状态和进程控制块3.3进程控制34进程的互斥与同步3.5进程通信36进程调度37死锁38线程,31进程的概念和定义,操作系统是一个动态系统，在持续的运动过程中完成各种使命、实现各项功能。因此，要了解操作系统各模块间的动态连接关系和相互制约关系就不能用静态的程序概念来刻画操作系统。因此引进一个新的观点进程观点，以便钻进操作系统内部去观察操作系统各模块的动态变化情况。311为什么引入进程312进程的定义,311为什么引入进程,应该说，组织用户使用计算机的机制是随着计算机操作系统的发展而进化的。在监督程序时代是以作业形势表示程序运行的。那时，作业以同步方式串行地运行每个作业步。当操作系统发展到分时系统时，为了开发同一个作业中不同作业步之间的并发，作业机制已不能满足需要，因而引进了进程机制，让进程来实现作业步的执行。但随着多处理机计算机的出现，用户希望一个作业步中的程序还能够同时在多个处理机上运行，因此进程的机制得到了进一步发展，让一个进程同时拥有多个线程，让多个线程在不同处理机上运行。,1.算法我们可以把算法定义为：问题求解步骤的精确描述。算法具有如下性质：解题算法是一个有穷动作序列；动作序列仅有一个初始动作；序列中每一个动作仅有一个后继动作；序列终止表示问题解决还是没有得到解决。,2.程序程序是对一个复杂的计算（问题）用一种形式化的语言对其初始数据与操作进行形式化描述的一个算法。当一个程序在运行之际，可以区分出三个不同的实体。(1)用来描述过程的一组指令，即“过程”；(2)处理机，即执行该过程的机构；(3)环境，即处理机能够直接感知或能够加以改造的那个外部世界。“一切听从程序的指挥”。,2.程序,因此,程序的主要特点是：(1)按“过程”所规定的操作，以严格顺序来执行，每一步都应在下一步开始之前完成（不存在并行）。这一特点就是我们所说的程序的顺序性。(2)环境处在“程序”的完全控制之下，它决不以任何方式变化，除非这种变化是程序所采取的步骤导致的结果。这个特点被称为程序的封闭性。(3)除了要求在合理的时间内获得结果外，任一操作所花费的时间对程序的运行而言是无关紧要的，即使在任一操作之间有一暂时间歇也没有关系。程序所产生的结果是其输入数据的函数而与时间无关。只要程序执行的初始条件相同，其结果是可以再现的。,3.程序的并行执行和资源的共享,为了合理地使用系统资源，充分发挥各种资源的作用，最大限度地提高系统的效率，引进多道程序设计技术。又由于计算机技术的不断发展而出现了中断技术、分时处理和各种新型结构，如多CPU系统的出现，导致现代操作系统出现了许多诸如并发性、资源共享性等许多新的特征。（1）并行操作（2）资源共享,4.程序并行执行的特征,程序的并行执行虽然增加了系统的处理能力和机器的利用率，但也产生了与顺序程序不同的新特征。（1）失去了程序的封闭性（2）程序并行执行时的相互制约关系,312进程的定义,通过上述分析可知，程序在并行执行时已不能描述不封闭性和“执行-暂停-执行”活动规律，需要有一种新的概念工具来描述下列特征：能描述“计算”这一现象；能描述“执行-暂停-再执行”这一活动规律；能为并行执行的“计算”的制约关系提供协调和共享资源的机构。这样的新概念称为进程或任务。,2.进程与程序的主要区别,(1)程序只是指令的有序集合，是静态的描述，没有运行的含义，所以程序是静止的；进程是程序的一次运行活动，是动态的概念。(2)进程是一个独立运行的单位，共享资源的实体，能与其他进程并发执行，而程序则不然。操作系统中以资源管理的中心思想来看，进程可以看成是资源的顾客和使用者。(3)一个程序可以对应多个进程，反过来，一个进程至少对应一段程序。逻辑上，每个进程有自己的处理机和程序，实际上两个进程可以共享同一段程序或同一个处理机，所以进程不等价于程序，也不等价于处理机，它是执行期间的对。(4)静态地观察进程，其实体是由程序和数据两部分构成，与程序没有什么区别。,3.进程的特征,进程具有如下的特征：（1）动态特征进程的实质是并行程序的一次执行过程，因此，动态特征是进程的最基本的特征。其动态性表现在它可以由创建而产生、由调度而执行、由于得不到资源而暂停，由撤消而消亡。进程存在一个生命周期。（2）并行特征引入进程的目的是使程序能并行执行，以提高资源的利用率。（3）独立特征进程是独立运行的单位，也是系统进行资源分配和调度的独立单位。（4）异步特征进程按照各自独立的，不可预知的速度向前推进，所以要求系统提供某种设施使进程间能协调操作和共享资源，保证它们协调运行。（5）结构特征进程是有结构的，体现在每个进程有一个记录进程当前信息的进程控制块（PCBProcessControlBlock）。每个进程都是由一个程序段和相应数据集以及进程控制块三部分组成。在UNIX操作系统中将这三部分称为“进程映象”，它把进程定义为：进程映象的执行。,引入进程这一概念后，就可以很方便地动态地描述操作系统了，但引入进程也有不利之处：(1)必须为设置进程付出一定的空间开销，因为并行执行的操作系统本身就复杂，如，必须设置进程管理并为并行执行的各进程之间的同步和协调建立某些机构，由于并行执行就必须考虑避免死锁等问题而使系统复杂化。另外，每个进程都必须有一个进程控制块（PCB），它也占用了一部分内存空间。(2)必须为设置进程付出一定的时间开销，因为运行一个复杂的系统软件将花费更多的处理机时间。,32进程的状态和进程控制块,321进程的状态进程是动态的，它存在着生命周期。它有诞生（创建）和灭亡（撤消）过程，在它的生命周期中又反映出它的执行-暂停-再执行的活动规律，进程最主要的特征是具有状态。进程在其活动期间具有两种状态：自由状态和等待状态。任一进程在任一时刻有且只有这两种状态之一。自由状态又可分为：运行状态和就绪状态。,321进程的状态,就绪状态（Ready）该进程已经获得了除了处理机以外的全部资源并准备好运行，但由于进程数多于处理机数目，所以此进程不能占用处理机执行，一旦为其分配到处理机该进程便立即执行。,321进程的状态,执行状态（Executive）进程获得了处理机等必要的资源，该进程已占用处理机，其程序正在处理机上执行。,321进程的状态,阻塞状态（Block）正在执行中的进程，由于发生了某一事件而使之暂时无法执行下去（如，等待I/O操作完成，或由于同步、互斥而等待）而处于暂停状态，即该进程的运行受到了阻塞（即等待状态或睡眠状态）。,进程的三种不同状态,322进程的状态演变,进程的状态不是一成不变的，它是随着自身的推进和外界条件的变化而变化的。下图为简单的进程状态演变图及演变事由。,应该说明的是:（1）在进程的生命周期中，处于执行状态的进程因为某一事件（如I/O请求等事件）出现而变成阻塞状态，当该事件消除后，被阻塞的进程并不恢复到执行状态，而转变为就绪状态等待再一次重新被进程调度程序调度。这是因为当该进程被阻塞时，为了使处理机不空闲，进程调度程序立即将处理机分配给另一个处于就绪状态的进程。（2）当进程从运行状态变为就绪或阻塞状态时，必须保留它的运行的现场信息，以便将来恢复运行。（3）处于同一状态的进程可以构成队列，系统中可以有一个运行队列、但是在只有一个处理机的情况下，任一时刻处于运行状态的进程只能有一个。系统中可以有一个或多个就绪队列和若干个等待队列，由于同一个原因而等待的进程应该属于同一个等待队列，相应每个队列设有指针，指向相应队列的首部。,323进程控制块（Processcontrolblock）,在进程的生命周期中，进程可以处于各种不同的状态，如何描述进程及其状态？进程控制块是表示进程存在的唯一实体。当创建一个进程时，必须为其设置一个进程控制块（PCB），由它对进程进行管理和控制。不同系统的进程控制块所包含的信息不尽相同，大体上都包括以下几项：,（1）进程标识符（Identification）（2）现行状态（Status）（3）CPU状态保护区（4）进程程序的起始地址（5）资源清单（6）进程优先数（7）队列指针或队列表（8）进程的家族信息,3.3进程控制,进程控制的功能是对系统中的全部进程实施有效的管理，它有创建进程和撤消进程的能力。1.进程家族与分类2.进程控制的基本操作,331进程家族与分类,1.进程家族进程的家族结构有两种：一种是非结构系统；另一种是树型结构系统。在非结构系统中管理程序直接对全部进程实施管理，它可以实施创建进程和撤消进程等操作。各进程之间的关系也是“平等”的。,在树型结构的进程家族中，一个父进程可以创建一个子进程而形成一个进程家族。如图3-9（a）给出了非结构系统进程家族示意图;图3-9（b）给出了树型结构的进程家族的示意图。,1.进程家族,进程的家族结构有两种：一种是非结构系统；另一种是树型结构系统。在非结构系统中管理程序直接对全部进程实施管理，它可以实施创建进程和撤消进程等操作。各进程之间的关系也是“平等”的，如图3-9（a）所示。在树型结构的进程家族中，一个父进程可以创建一个子进程而形成一个进程家族。图3-9（b）给出了树型结构的进程家族的示意图。,1.进程家族,1.进程家族,树型结构的优点是：（1）资源分配严格，子进程可以分配到父进程所拥有的资源，用完后立即归还，一个进程家族所占有的全部资源应该在其祖先所拥有的资源范围内。（2）进程的控制灵活，当一个进程被分配完成某一任务时，它能够创建若干进程去分别完成各子功能。（3）进程层次清晰，关系明确。所以，树型结构的系统获得了广泛应用。,2进程分类,进程按服务对象可分为：系统进程与用户进程。完成指定的系统功能的进程称为系统进程；完成用户作业所需做的工作的进程称为用户进程，如，编译、运行系统等。系统进程按其占内存的情况又可分为：长存进程和暂存进程两大类，长存进程的数据块、程序块等长期驻留在内存；暂存进程的程序块等不是长期驻留在内存中，需要时才把它们调入内存。,332进程控制的基本操作,为了对进程进行控制和通信，在系统中必须设置一个机构，它具有创建、撤消、进程通信和资源管理等功能，这样的机构称为操作系统的内核（Kernel），系统的其他部分是由它们建造的。内核本身并非一个进程，而是一组基本原语操作，是由软件实现的内核功能，内核通过执行各种原语操作来实现各种控制和管理功能。内核是硬件的首次延伸，它扩大了CPU的功能。,原语是机器指令的延伸，是由若干条机器指令构成的用以完成特定功能的一段程序，为了保证操作的正确性，原语在执行期间是不可分割的。引入原语的目的是允许进程内部并行操作，且可以动态地创建一个进程；允许系统生成许多不同的版本以适应不同用户的需要，系统执行时灵活组装成不同的操作系统；使系统结构清晰。用于对进程进行管理和控制操作的基本原语有：,创建原语(Create)撤消原语（Destroy）以上两个原语使进程从无到有，从有到无。唤醒原语（Wakeup）阻塞原语（Block）以上两个原语使进程发生各种状态变化。挂起原语（Suspend）激活原语（Action)以上两个原语使进程从活动到静止,从静止到活动。,34进程的互斥与同步,进程的状态是基于一定的原因和条件而变化的，而这些原因和条件又常常是由于进程之间的相互制约关系而引起的。系统中诸进程之所以有这种关系，主要原因是由于进程对资源的共享性，由于这种共享的特征，使系统中本来没有逻辑关系的进程因为互相竞争资源而产生了制约关系。这种关系的基本形式是：“进程资源进程”，这是进程间通过资源而发生的一种间接关系。由于系统对进程所请求的许多资源常常是互斥满足的，所以这种关系表现为互斥关系（竞争关系）。,系统中为了完成同一个任务而创建了若干进程，它们之间必然是伙伴进程（进程合作），如某作业的一组并行进程共同完成一项任务，有时它们要在某点上互相等待和互通消息，这种关系的基本形式是：“进程进程”，这是进程之间的一种直接关系，表现了进程之间的协同工作的特性，称为进程间的同步关系。,341临界区（Criticalsection）,计算机中的某些资源是共享资源，但是有些共享资源具有如下特征：即一次仅允许一个进程使用，我们把一次仅允许一个进程使用的资源称为“临界资源”（Criticalresource）。例如，有两个进程A，B共享一台打印机，若让它们任意使用，则可能将两个进程的输出结果交织在一起，很难区分。为了解决这一问题，可以在A进程使用打印机时先申请，一旦系统将打印机分配给A进程后就由它一直占用，此时若B进程也要使用打印机就必须等待，直到A进程用完释放打印机后B进程方可使用，即它们必须互斥地使用打印机。这里打印机就是一种临界资源。,访问临界资源的那段程序称之为“临界区”。为了使临界资源互斥地被使用，必须使临界区互斥地被执行，即诸进程访问临界区时必须互斥。为了做到禁止一组进程同时访问它们的临界区，而提出了临界区的准则如下：,（1）不能假设各并发进程的相对执行速度，即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区。（2）当有若干进程欲访问它们的临界区时，应在有限时间内使一个进程访问临界区，不应互相阻塞而彼此都无法访问，这就是有空让进的原则，使共享资源能够充分利用。（3）每次至多有一个进程处于临界区内，这体现了互斥的基本含义。（4）进程仅在临界区内逗留有限时间，使等待访问临界区的进程是有限等待。,由上述准则得临界区的调度原则如下：（1）当无进程访问临界区时，允许一个进程立即访问其临界区。（2）当某一进程已访问了它的临界区时，其他试图访问临界区的进程必须等待。（3）当某一进程离开临界区时，若有等待访问临界区的进程，则允许其中的一个进程进入临界区访问。,342进程互斥,1.互斥的加锁实现这是一种借助一条硬指令Test和Set来实现互斥的一种同步机构。此方法是对临界区加锁以实现互斥。当某个进程进入临界区之后，为了阻止其他进程进入临界区，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能进入临界区。为此设置一个变量W，代表临界区的状态，W也称为锁或锁位。当W=0时，表示临界区可以进入；当W=1时，表示临界区已被占用，企图进入临界区的进程必须等待。,关锁原语Lockw:关锁原语l:ifw=1thengotolelsew:=1；开锁原语开锁原语unlockw:w:=0下面的程序表示了两个并行的循环进程用关锁和开锁原语实现互斥的情况(CS1和CS2表示两个进程的各自临界区)。,Beginintegerw;W:=0;Cobeginprocess1BeginL1:lockw;CS1;Unlock;Program1;GotoL1;EndProcess2BeginL2:lockw;CS2;Unlock;Program2;GotoL2;EndCoendEnd,这样的一个同步机构能有效地保证进程互斥地访问临界区，但对于不能进入临界区的进程却在不断地测试锁位W，以等待它为零，这就造成了处理机时间的浪费。改进的方法是将忙式等待改成忙式挂起，当某进程所需临界资源被占用时，应使该进程阻塞，把它插入到等待队列中，此时CPU分配给其他进程，一旦该资源被释放就立即检查等待队列，若等待队列空，则开锁表示资源可以使用；若等待队列不空，则从该等待队列中移出一个进程，将其置于就绪状态并插入就绪队列。修改后的关锁和开锁原语如下：,关锁原语Lockw:ifw=1then测试W的值BeginBlock(n);insert(wl,n);scheduler若临界区中有进程，则阻塞自己并插入到等待队列中，此时CPU空闲，引起进程调度。EndElsew:=1;若临界区中无进程，则关锁表示占用开锁原语临界区；Unlockw:ifwlnullthen若等待队列不空，则BeginRemove(wl,q);从等待队列中移出q，Status(q):=ready;将进程q置于就绪状态，Insert(rl,q);将其插入就绪队列。EndW:=0;开锁。,2信号量和P,V操作荷兰计算机科学家E.W.Dijkstra于1965年提出了信号量的概念，并引入两个新的原语操作P和V（P和V分别是荷兰语Passeren和Verhoog的第一个字母，相当于英文的Pass和Increment的意思）。采用P,V操作原语，大大简化了进程的同步和互斥的实现。P和V这两个原语操作在非负整形变量上，这些变量称为信号量。,信号量是表示资源的物理实体，是一个与队列有关的整形变量，其值仅能由P和V操作来改变。操作系统利用它的状态对进程和资源进行管理。按信号量的用途不同可将其分为：公用信号量。它联系着一组并行进程，初始值为1，每个进程都可以对它施加P或V操作，通常它是为实现进程的互斥而设置。私用信号量。它联系着一组共行进程，初始值为0或某个正整数n，仅允许拥有它的进程对它施加P操作，通常用来实现进程的同步。,P操作P操作记为P(S),其中S为一个信号量的值，每执行一次P操作，就意味着申请一个单位的资源，由于信号量的值用来表示资源数量，所以执行一次P操作，信号量的值就减1。此时若S0，则进程继续执行；若S0则阻塞该进程，并将其插入到该信号量的等待队列中等待。,ProcedureP(S)BeginLockoutinterrupts;关中断；S:=S-1;信号量的值减1；IfS0thenbegin如果s0，说明已经没有此类资源，故进程Status(q):=block;q的申请得不到满足，将其阻塞；Insert(Q,q);将q插入到该资源的等待队列中；否则继续Unlockinterrupts;开中断；End;请读者注意，程序中为什么判断S0则进程继续执行；若S0则从信号量的等待队列中移出一个进程并赋予该进程为就绪状态，将其插入到就绪队列中。,ProcedureV(S)BeginLockoutinterrupts;关中断；S:=S+1;信号量的值加1；IfS0thenbegin如果S0，说明有等待该资源的进程；Remove(Q,r);则将该进程从等待队列中移出；Status:=ready;并将其状态改为就绪；Insert(RL,r);end;插入到就绪队列；Unlockinterrupts;开中断；End;也请读者仔细分析一下，在V操作中为什么判断S0，而不是S0？,信号量的特征为：信号量的值一般表示单位资源的数量，若S0时其绝对值表示该资源上等待的进程数目。一个信号量的初始值不能置为负，但在执行n次P操作后它可以变为负值，此时表示系统中已没有这类资源，因此，请求该资源的进程将被阻塞，将其排在该信号量的等待队列上，此时信号量S的绝对值等于该信号量队列上的进程数目。信号量的值=信号量的初始值-P操作的次数+V操作的次数。执行V操作就意味着释放一个单位的资源，若S0则表示信号量请求队列中仍有请求该资源而被阻塞的进程，因此，应将该队列的第一个进程唤醒，使之状态转换为就绪。,利用信号量实现进程互斥首先讨论两个循环执行的进程P1和P2，在它们都要访问它们的临界区时如何做到互斥。为使这两个进程能够做到互斥地访问临界区，写出如下的算法程序。其中S为公用信号量，其初始值为1。,BeginCobeginP1:beginL1:P(S)CS1;V(S);Program1;GotoL1EndP2:beginL2:p(S);CS2;V(S);Program2;GotoL2EndCoendEnd,上述例子中对于这两个进程而言，信号量的取值仅有1，0，-1这3个值。当S=1时，表示临界区中无进程；当S=0时，表示临界区中有一个进程；当S=-1时，表示有一个进程进入了临界区，另一个进程等待进入而阻塞。,343进程的同步,1.进程同步的概念同步是指进程执行在时间上的先后次序的限制条件。系统中的诸进程共同完成一个任务，它们相互合作，协调运行，有时在它们之间还需要交换信息。因此有的进程必须等待另一个进程发来消息后才能继续执行，它们在某点上要互相等待。,生产者与消费者问题一个作为生产者的进程生产消息，然后把它放入共享的缓冲区中。相应地，一个消费者进程从缓冲区中取走消息进行处理。假设该缓冲区可以存放n个大小相等的消息（即由n个缓冲器组成，每个缓冲器中存放一个消息）。如下图所示：,生产者和消费者的同步规则如下：生产者企图将一个消息放入已满的缓冲区时要等消费者取走一个消息之后；消费者企图从空的缓冲器中取走消息时，要等生产者放入一个之后。为此，设置两个私用信号量empty和full，用于进程之间的同步。其中，empty信号量表示可用的空缓冲器的数目，初始值为n，full信号量表示消息数目，初始值为0。缓冲器是共享的临界资源，要求两个进程互斥地对其操作，故设置一个公用信号量mutex，初始值为1（表示没有进程进入临界区），它用于实现进程互斥。生产者与消费者对于n个缓冲器的互斥与同步问题的描述如下：,beginsemaphoremutex,empty,full;mutex:=1;empty:=n;full:=0;cobeginproducer:beginL1:producenextmessage;P(empty);P(mutex);Addtobuffer;V(mutex);V(full);GotoL1;End;Consumer:beginL2:P(full);P(mutex);Takefrombuffer;V(mutex);V(empty);Consumeproduct;GotoL2;End;Coend;,如果将生产者进程或消费者进程中的P(empty)和P(mutex)或P(full)和P(mutex)的次序颠倒，会造成死锁而使两个进程都无法执行。这是因为若生产者（消费者）进程先执行P(mutex)操作，就意味着它将申请临界区资源，如果它不阻塞可以继续执行,当执行到P(empty)（或P(full)）而阻塞时，必须启动另外一个进程执行，另一个进程当执行到P(mutex)时，也会因为临界区的互斥而阻塞，从而导致两个进程都无法执行下去，故产生死锁。请读者分析一下V操作的次序可否颠倒。,实际使用的是将n个缓冲器构成一个环形缓冲区，如图3-13所示。工作时只要不是生产者进程的速度过快，以至于使缓冲区全满，或者消费者进程执行的速度过快而使缓冲区全空，那么缓冲区的容量将是无限大的。它将使缓冲区由有界变为无界。图3-13环形缓冲区生产者(往空缓冲区中送消息)消费者(从满缓冲区中取消息)。,3.5进程通信,进程之间的信息交换称为进程通信。进程之间的所有通信情况都归结为互斥和同步两类，而严格说来，互斥也是一种同步，是一种很特殊的同步，前面已经讨论过。同步又可以分为信号同步和信件同步两种。,信号同步：发送者只给对方发送一简单信号（同步的双方互相明白该信号的寓意）。信件同步：发送者给对方发送一复杂信件。例如，用户进程要输出结果时，请求输出进程为它服务，用户进程将要输出的信息在内存中的头地址、输出信息的个数、输出格式以及在哪一台设备上输出等信息作为一个信件发送给输出进程，输出进程在尚未收到信件之前暂停执行，收到信件后，分析信件并按要求完成输出工作。交通控制程序提供了专门的机构来实现进程通信，这种机构通常叫做通信原语。,通信原语通常分为低级通信原语和高级通信原语两类。低级通信原语如关锁与开锁原语以及上一节所介绍的PV操作原语等。它们只能完成简单的信号传递，通信的效率低。高级通信原语如消息缓冲或信箱等通信手段完成的通信，这些通信方法是以较高的效率传递大批信息。,351消息缓冲（messagebuffer）,Hansen于1973年首先提出用消息缓冲作为进程通信的基本手段，并在RC4000系统中实现了。消息缓冲是进程之间的高级通信工具，它实现了以较高的效率在进程之间传递大批数据的的直接通信方式。为了实现这种通信方式，系统必须提供相应的原语。如发送消息（send）原语和读取消息（read）原语。所谓消息就是一组信息。消息缓冲区是包含如下信息的缓冲区：（1）指向发送进程的指针Sptr；（2）指向下一个消息缓冲区的指针Nptr；（3）消息长度Size；（4）消息正文Text。,352信箱（mailbox）,信箱是用以存放信件的。利用信箱通信就是由发送进程申请建立一个与接收进程链接的信箱，然后发送进程将欲发送的消息送往信箱中，接收进程从信箱中取出消息，从而完成进程之间的信息交换。设置信箱的最大好处就是发送进程和接收进程之间没有处理时间上的限制。一个信箱可以看作是发送进程和接收进程之间的大小固定的私有数据结构，它不像消息缓冲区那样被系统内所有的进程所共享。信箱逻辑上可以分成两部分，即有关信箱描述的信箱头和由若干个格子组成的信箱体，其中每个格子可以存放一个信件。格子的数目和每个格子的大小由创建信箱时确定。,36进程调度,进程调度是本章中叙述的核心层中原语调用的一个例行程序。在多道程序系统中，用户进程数往往多于处理机数目从而导致多个进程争夺处理机，同时，系统进程也要使用处理机。因此就应该按照一定的算法，动态地把处理机分配给就绪队列中的某个进程。这个任务由进程调度程序完成。,361进程调度的功能,进程调度的功能可归结如下：（1）记住系统中所有进程的状态、优先级和所用资源情况。作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征等记录在各进程的进程控制块表中，并根据各进程的状态特征和资源要求，将各进程的进程控制块表排成相应的队列。进程调度模块通过进程控制块中所记载的信息来掌握系统中所有进程的执行情况和状态特征。（2）根据各进程的情况，当处理机空闲时，按照确定的进程调度算法将处理机分配给处于就绪状态的某个进程并确定分配给它多长时间。（3）将处理机交给选中的进程并启动执行。,362引起进程调度的原因,引起进程调度的原因有以下几种：（1）正在执行的进程执行完毕。系统将收回该进程所占用的全部资源，包括处理机资源。如果此时不从就绪队列中重新选择一个进程占用处理机，将使得处理机空闲，从而造成处理机资源的极大浪费。（2）执行中的进程自己调用了阻塞原语将自己阻塞起来进入睡眠等待状态。（3）执行中的进程提出了I/O请求后被阻塞。（4）执行中的进程执行了某种原语操作而阻塞，如P操作、关锁原语操作等。（5）在分时系统中，分配给该进程运行的时间片已经用完。（6）在执行完系统调用，当系统程序返回用户进程时，可认为系统进程执行完毕，从而可以调度选择一个新的用户进程执行。（7）在可剥夺方式下，就绪队列中的某进程的优先级变得高于当前执行进程的优先级时会引起进程调度。,363进程调度算法,1.最高优先级优先（HPF）调度算法2.轮转法（Roundrobin）,最高优先级优先（HPF）调度算法,（1）进程类型（2）作业要求的资源（3）外部优先级和作业到达时间,2.轮转法（Roundrobin）,（1）简单轮转法系统响应时间：当进程数目一定时，时间片正比于系统响应时间。就绪队列中的进程数目：当响应时间一定时，时间片反比于就绪队列中的进程数目。进程转换时间计算机处理能力（2）可变时间片轮转法（3）多队列轮转法,37死锁,371死锁问题的提出及举例372产生死锁的原因373解决死锁问题的三种途径374系统状态图和进程资源图375死锁的预防376死锁的检测377死锁的解除,371死锁问题的提出及举例,死锁问题是Dijkstra于1965年在研究银行家算法时首先提出来的，后来Havender等人又进一步认识这一现象并将其发展。实际上，死锁是一个具有普遍性的现象，在各个领域乃至日常生活中也屡见不鲜。研究死锁问题是保证操作系统正确可靠运行必须考虑的课题。,并行进程的执行虽然改善了系统资源的利用率，提高了系统的处理能力。但并行执行的风险增大了，因为并发进程执行的结果与时间有关，且对临界资源的管理或操作不当（如在生产者与消费者问题中的P操作的次序颠倒时等等）就会产生死锁。,银行家算法问题假设某银行拟将一定数量的资金供给一定数量的顾客共享使用。规定：（1）每个顾客必须预先申请他对资金的最大需求量，但不得超过银行共享资金的总和；（2）每个顾客的借款方式是一个单位一个单位地进行，每次交易借款额为一个资金单位；（3）银行对顾客提出的每次交易，将根据当时的资金数量，依照一定的原则，或立即成交或让顾客等待一段时间后再成交，但须确保顾客等待的时间是有限的，每个顾客的借款总额不得超过其最大申请量；（4）当且仅当每个顾客的借款总额达到他的最大申请量后，他才能且必须在有限时间内归还其全部借款。,如果在某一时刻银行能与所有的顾客成交，则称此时刻的状态是安全的，如果永远不具有成交的可能性，则说是不安全的。顾客的状态可用他的现时借款额和进一步申请额来刻画：剩余申请量=最大申请量-已借款额银行的状态则可用它的限定的资金总额和库存的资金来刻画：库存资金=资金总额-各顾客已借款额之和,假设银行共有10个资金，现有3个顾客与银行进行交易，这3个顾客分别为甲、乙和丙,顾客甲的最大申请额为8个资金，顾客乙的最大申请额为3个资金，顾客丙的最大申请额为9个资金，都不超过银行的现有资金总和。现在银行已经借给顾客甲4个资金，借给顾客乙2个资金，借给顾客丙2个资金。那么，顾客甲还需要资金4个，顾客乙还需要资金1个，顾客丙尚需资金7个，银行库存资金为2个，状态如下图（a）所示。,如果银行现在和顾客乙进行交易，即借给顾客乙1个资金，顾客乙就已经达到了其最大申请量3个资金，在有限时间内顾客乙将这3个资金全部归还给银行，此时，银行库存资金就变成了4个，此时的状态如下图（b）所示。接着银行和顾客甲进行成交，即将库存的4个资金借给顾客甲，顾客甲就达到了其最大申请量，在有限时间内顾客甲归还他所借的资金，使库存资金变成8个，其状态如下图（c）所示。然后，银行和顾客丙进行交易，借给顾客丙7个资金，顾客丙也达到了其最大申请量，用完后归还，此时，银行收回了全部10个资金。银行的最终状态如下图（d）所示。可见按照这样的交易方式进行，系统是安全的。,如果不按照上述方式交易，如，当系统处于下图（a）状态时，银行草率地把库存的2个资金借给了丙1个，此时的状态如下图（b）。由于此时银行的库存还有1个资金，然后，银行再和顾客乙完成交易，即借给顾客乙1个资金，顾客乙就达到了其最大申请量，用完后归还其所借的3个资金。这时，银行的库存只有3个资金，状态如下图(c)，银行使用这3个资金无论是与顾客甲还是与顾客丙都无法交易下去，因为这两个顾客都得不到最大满足，也就是说，银行永远也不能收回其全部资金。我们说银行按照这样的交易方式进行交易是不安全的。,死锁的定义：当某进程提出资源请求后，使得若干进程在无外力作用下，永远不能再继续前进，我们称这种情况为系统发生了死锁或僵局。或当两个或两个以上的进程因竞争系统资源而无休止的相互等待时，称这些进程