计算机操作系统.ppt

计算机操作系统,第三章 进程管理,进程概述,处理机管理是解决处理机的分配问题处理机管理的两个阶段处理机时间分配进程管理的主要功能进程的三种状态,为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。在本章中，我们将讨论进程概念、进程控制和进程间关系。,预备知识操作系统概念和特征 操作系统的基本类型：批处理OS、分时OS、实时OS多道的概念：内存中同时存在多个作业,第3章 进程管理,3.1 进程(PROCESS)3.2 进程控制3.3 线程(THREAD)3.4 进程调度3.5 进程互斥和同步3.6 进程间通信(IPC,INTER-PROCESS COMMUNICATION)3.7 死锁问题(DEADLOCK),3.1 进程(PROCESS),3.1.1 程序的顺序执行和并发执行3.1.2 进程的定义和描述3.1.3 进程的状态转换,返回,3.1.1 程序的顺序执行和并发执行,程序的执行有两种方式：顺序执行和并发执行顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。,顺序执行的特征,顺序性：处理机的操作严格按规定顺序执行封闭性：程序执行时，独占系统资源，计算机的状态只由该程序的控制逻辑所决定可再现性：当初始条件相同时，程序多次执行的结果相同,一个程序执行的结果可以重复显现,如果出现错误也能在对应的地点出现,P1：a=x+yP2:b=a-5P3:c=b+1,资源共享,资源共享就是指计算机中并发执行的多个程序交替使用计算机硬件和软件资源。操作系统提供两种资源共享的方法：1、由操作系统统一管理和分配，一般系统中的硬件资源采用这种方法共享。2、由进程自行使用。,并发执行的特征,多个程序共享系统资源、多个程序并发执行 间断(异步)性：走走停停，一个程序可能走到中途停下来，失去原有的时序关系；失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。失去可再现性：外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。程序与计算不再一一对应、出现相互制约的关系 并发执行失去封闭性的原因是资源共享,程序并发执行的条件Bernstein,P1：a=5P2：b=6P3：c=a+bP4：d=c+1,P1、P2可以并发执行吗？P3、P4可以并发执行呢？,问题？,P1：a=5P2:b=6R(P1)=W(P1)=aR(P2)=W(P2)=bR(P1)W(P2)=R(P2)W(P1)=W(P1)W(P2)=R(P1)W(P2)R(P2)W(P1)W(P1)W(P2)=P1、P2可以并发执行,Bernstein条件例1,Bernstein条件例2,P3：c=a+bP4:d=c+1R(P3)=a,bW(P3)=cR(P4)=cW(P4)=dR(P3)W(P4)=R(P4)W(P3)=cR(P3)W(P4)R(P4)W(P3)W(P3)W(P4)=cP3、P4不能并发执行,2.1.2 进程的定义和描述,1.进程的定义,可并发执行的一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程,即程序在并发环境中的执行过程。是系统进行资源分配和调度与分派的基本单位。,引入多进程，提高了对硬件资源的利用率，但又带来额外的空间和时间开销，增加了OS 的复杂性。,1.进程与程序的区别,进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。,并发性：进程能真实地描述并发执行，而程序不具有这种特征。进程具有创建其他进程的功能。操作系统中的每一个程序都是在一个进程现场中运行。,2.进程的特征,动态性：进程具有动态的地址空间，地址空间上包括：代码（指令执行和CPU状态的改变）数据（变量的生成和赋值）系统控制信息（进程控制块的生成和删除）独立性：各进程的地址空间相互独立，除非采用进程间通信手段；并发性、异步性结构性：代码段、数据段和核心段（在地址空间中）；程序文件中通常也划分了代码段和数据段，而核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）,进程分为系统进程和用户进程 系统进程是操作系统用来管理系统资源并行活动的并发软件用户进程是可以独立执行的用户程序段，它是整个操作系统服务的对象，是系统资源的实际享有者。系统进程和用户进程的区别：（1）系统进程之间的关系由操作系统自己负责，用户进程之间的关系主要由用户自己负责。（2）系统进程直接管理有关的软、硬设备的活动；用户进程只能间接地和系统资源发生关系。（3）在进程调度中，系统进程的优先级高于用户进程。,3.2 进程控制,3.2.1 两状态进程模型3.2.2 三状态进程模型3.2.3 五状态进程模型3.2.4 挂起进程模型3.2.5 进程结构、进程控制块及组织方式3.2.6 进程控制,3.2.1 两状态进程模型,1.状态,运行状态(Running)：占用处理机资源；暂停状态(Not-Running)：等待进程调度分配处理机资源；两状态模型无法区分暂停进程表中的就绪和阻塞,2.转换,进程创建(Enter)：系统创建进程，形成PCB，分配所需资源，排入暂停进程表(可为一个队列)；调度运行(Dispatch)：从暂停进程表中选择一个进程(要求已完成I/O操作)，进入运行状态；暂停运行(Pause)：用完时间片或启动I/O操作后，放弃处理机，进入暂停进程表；进程结束(Exit)：进程运行中止；,3.2.2 三状态进程模型,就绪状态,运行状态,阻塞状态,分到cpu,等待IO或事件,中断,IO或事件完成,进程的基本状态,运行态正在CPU 上执行就绪态万事俱备,就差cpu阻塞态等待事件，无法运行 进程的动态性是由它的状态及转换体现出来的 进程的信息存在PCB中 进程的状态转换是在一定条件下实现的,转换,就绪运行 cpu空闲，而且就绪的级别高 运行阻塞 需要等待某个条件，这个条件出现之前就放弃 阻塞就绪 这个进程等待的时间已经满足运行就绪 运行的进程分给的时间片已经用完说明:进程之间的状态转换并非都是可逆的进程之间的状态转换并非都是主动的进程在运行态才是真正的运行,3.2.3 五状态进程模型,进程基本状态是对进程动态过程的简单描述,具有创建和终止状态的进程状态的五状态模型就是对暂停状态的细化。,五状态进程模型(状态变迁),等待事件或I/O完成,1.状态,运行状态(Running)：占用处理机资源；处于此状态的进程的数目小于等于CPU的数目。在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）。就绪状态(Ready)：进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配CPU就可执行。可以按多个优先级来划分队列，如：时间片用完低优，I/O完成中优，页面调入完成高优阻塞状态(Blocked)：由于进程等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行。,新建状态(New)：进程刚创建，但还不能运行(一种可能的原因是OS对并发进程数的限制)；如：分配和建立PCB表项（可能有数目限制）、建立资源表格（如打开文件表）并分配资源，加载程序并建立地址空间表。终止状态(Exit)：进程已结束运行，回收除PCB之外的其他资源。,2.转换,创建新进程：创建一个新进程，以运行一个程序。可能的原因为：用户登录、OS创建以提供某项服务、批处理作业调度运行(Dispatch)：从就绪进程表中选择一个进程，进入运行状态；释放(Release)：由于进程完成或失败而中止进程运行，进入结束状态；运行到结束：分为正常退出Exit和异常退出abort（执行超时或内存不够，非法指令或地址，I/O失败，被其他进程所终止）就绪或阻塞到结束：可能的原因有：父进程可在任何时间中止子进程；,超时（Timeout）：由于用完时间片或高优先进程就绪等导致进程暂停运行；事件等待（Event Wait）：进程要求的事件未出现而进入阻塞；可能的原因包括：申请系统服务或资源、通信、I/O操作等；事件出现（Event Occurs）：进程等待的事件出现；如：操作完成、申请成功等；,注：对于五状态进程模型，一个重要的问题是当一个事件出现时如何检查阻塞进程表中的进程状态。当进程多时，对系统性能影响很大。一种可能的作法是按等待事件类型，排成多个队列。,3.2.4 挂起进程模型,由于进程优先级的引入，一些低优先级进程可能等待较长时间，从而被对换至外存。挂起:把内存中暂时不能或不需要运行的进程从内存换到外存.引起挂起的原因:系统资源的需要 调节竞争或消除故障的需要 终端用户的需要 调节进程的需要,引入挂起的目的是：提高处理机效率：就绪进程表为空时，要提交新进程，以提高处理机效率；为运行进程提供足够内存：资源紧张时，暂停某些进程，如：CPU繁忙（或实时任务执行），内存紧张用于调试：在调试时，挂起被调试进程（从而对其地址空间进行读写）,挂起状态的进程状态转换图,1.状态,活动就绪状态(Ready)：进程在内存且可立即进入运行状态；活动阻塞状态(Blocked)：进程在内存并等待某事件的出现；静止阻塞状态（Blocked,suspend）：进程在外存并等待某事件的出现；静止就绪状态（Ready,suspend）：进程在外存，但只要进入内存，即可运行；,注：这里只列出了意义有变化或新的状态。,2.转换,挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况：活动阻塞到静止阻塞：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程；活动就绪到静止就绪：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程；激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况：静止就绪到活动就绪：没有就绪进程或静止就绪进程优先级高于就绪进程时，会进行这种转换；静止阻塞到活动阻塞：当一个进程释放足够内存时，系统会把一个高优先级静止阻塞进程（系统认为会很快出现所等待的事件）转换为活动阻塞；,事件出现（Event Occurs）：进程等待的事件出现；如：操作完成、申请成功等；可能的情况有：活动阻塞到活动就绪：针对内存进程的事件出现；静止阻塞到静止就绪：针对外存进程的事件出现,1.进程结构,进程控制块 程序段 每个进程都要有相应的程序，进程是程序的执行过程，当然离不开程序私有数据块,进程的组成模型,3.2.5 进程结构、进程控制块及组织方式,4.进程控制块(PCB,process control block),每个进程在OS中有登记表项（可能有总数目限制），OS据此对进程进行控制和管理（PCB中的内容会动态改变），不同OS则不同处于核心段，通常不能由应用程序自身的代码来直接访问，而要通过系统调用。,进程控制块是对进程本质属性的描述,由OS维护的用来记录进程相关信息的一块内存。引入PCB的作用：就是使进程能成为独立运行的单位，并可和其他进程并发执行。,5.进程控制块的内容,进程描述信息：进程标识符(process ID)，唯一，通常是一个整数；进程名，通常基于可执行文件名（不唯一）；用户标识符(user ID),由进程创建者提供;进程控制信息：当前状态；优先级(priority)；代码执行入口地址；程序的外存地址；运行统计信息（执行时间、页面调度）；进程间同步和通信；阻塞原因资源占用信息：虚拟地址空间的现状、打开文件列表CPU现场保护结构：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）操作系统就是根据进程控制块提供的信息来对进程实行调度和管理。,6.进程与PCB的关系,每个进程有唯一的PCB 操作系统依据PCB管理进程 利用PCB实现进程的动态、并发 PCB是进程存在的唯一标志 进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正感知的部分。,7.PCB的组织方式,线性方式链接方式：同一状态的进程PCB通过指针链接成一队列，多个状态对应多个不同的队列各状态的进程形成不同的队列：就绪链表、阻塞链表索引方式：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表，每个索引表中记录着具有相应状态的所有进程的PCB在PCB表中的位置。各状态的进程行形成不同的索引表：就绪索引表、阻塞索引表,具有较高的特权，能执行一切命令，访问所有寄存器和存储区。,3.2.6 进程控制功能,具有较低特权，只能执行规定的命令，访问指定的寄存器和存储区。,进程的创建与撤消,硬件的第一次延伸。系统将一些与硬件紧密相关的模块放在内核中断处理时钟管理内核在执行某些基本操作时，往往是利用原语操作实现的。,内核与原语,原语,原语由若干条指令构成、用于完成一定功能的过程。原语是“原子操作”，是一个不可分割的操作。原语是操作系统核心，由程序模块组成，运行在管态，常驻内存，由系统进程调用。,primitive,用户登录新作业进入系统提供服务应用请求,进程创建,申请空白PCB为进程分配资源初始化PCB初始化进程描述信息初始化处理机状态信息初始化进程控制信息将新进程插入就绪队列,进程创建,创建,继承(inherit)：子进程可以从父进程中继承用户标识符、环境变量、打开文件、文件系统的当前目录、控制终端、已经连接的共享存储区、信号处理例程入口表等不被继承：进程标识符，父进程标识符spawn创建并执行一个新进程；新进程与父进程的关系可有多种：覆盖(_P_OVERLAY)、并发(_P_NOWAIT or _P_NOWAITO)、父进程阻塞(_P_WAIT)、后台(_P_DETACH)等。,父子进程的fork()返回值不同，Parent PID的值不同 getppid()fork()创建子进程之后，执行返回父进程，或调度切换到子进程以及其他进程fork创建一个新进程（子进程），子进程是父进程的精确复制。在子进程中返回为0；在父进程中，返回子进程的标识。子进程是从fork调用返回时在用户态开始运行的。父进程的返回点与子进程的开始点是相同的。exec用一个新进程覆盖调用进程。它的参数包括新进程对应的文件和命令行参数。成功调用时，不再返回；否则，返回出错原因。,创建：fork(),exec(),UNIX进程创建,进程正常结束进程异常结束外界干预,查找撤消进程的PCB若进程处于执行状态，终止之，并进行进程调度若有子孙，予以终止归还资源从所在队列移出,进程的阻塞与唤醒,请求系统服务启动某种操作数据尚未到达无新工作可做,停止进程的执行将进程插入阻塞队列，改变进程在PCB中的状态重新调度,将进程从阻塞队列解下将进程插入就绪队列改变进程在PCB中的状态,检查被挂起进程的状态如进程处于就绪状态，将进程从就绪状态变为静止就绪状态如进程处于阻塞状态，将进程从阻塞状态变为静止阻塞状态如进程正在运行，将进程变为静止就绪状态，并重新调度,检查被激活进程的状态如进程处于静止就绪状态，将进程从静止就绪状态变为就绪状态如进程处于静止阻塞状态，将进程从静止阻塞状态变为阻塞状态若系统为抢占式系统，则进行进程调度,3.3 线程(THREAD),3.3.1 线程的引入3.3.2 进程和线程的比较3.3.3 线程的类型3.3.4 线程的特点,返回,引入线程的目的是简化进程间的通信，以小的开销来提高进程内的并发程度。,由于进程是资源拥有者，因而在进程的创建、撤消和切换中系统必须为之付出较大的时间、空间开销。因此，系统中所设置的进程的数目不宜过多，进程切换的频率不宜过高,这就限制了进程并发程度的提高。,进程有两个基本属性进程是拥有资源的独立单位进程是独立调度和分派的基本单位,2.3.1 线程的引入,进程：资源分配单位（存储器、文件）和CPU调度（分派）单位。线程：作为CPU调度单位，而进程只作为其资源分配单位。只拥有必不可少的资源，如：线程状态、寄存器上下文和栈同样具有就绪、阻塞和执行三种基本状态同属一个进程的线程共享进程所拥有的全部资源一个线程可以创建和撤销另一个线程线程的优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。线程的创建时间比进程短；线程的终止时间比进程短；同进程内的线程切换时间比进程短；由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信；,线程是进程中的一个实体，是系统独立调度和分派的基本单位,线程的定义,线程的属性之一,进程与线程的关系,操作系统中的进程和线程可以设计为以上四种,3.3.2进程与线程的关系,2.3.2 进程和线程的比较,地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享某进程内的线程在其他进程不可见通信：线程间可以直接读写进程数据段（如全局变量）来进行通信需要进程同步和互斥手段的辅助，以保证数据的一致性,进程和线程比较,进程是资源的拥有者线程不拥有资源，只有TCB及堆栈,调度 线程调度快，同一进程中，线程的切换不会引起进程的切换，需要空间小。进程因拥有资源，调度时因负担过重而缓慢。并发性 在引入线程的操作系统中，不仅进程之间可以并发执行，一个进程中的多个线程之间亦可并发执行。拥有资源 进程是资源的拥有者，一般线程自己不拥有系统资源，一个进程的代码段、数据段以及系统资源，可供同一进程的其他所有线程共享。系统开销 进程切换的开销远远大于线程切换的开销，线程的切换省去了资源的回收。,进程和线程比较,同一进程中的多个线程具有相同的地址空间，线程之间的同步和通信变得比较容易，线程之间的切换、同步和通信都无须操作系统内核的干预。,3.3.3线程的类型,依赖于内核，线程的创建、撤消和切换都由内核实现。在内核中有线程控制块（TCB），内核根据TCB感知线程的存在，并对线程进行控制 内核维护进程和线程的上下文信息；线程切换由内核完成；一个线程发起系统调用而阻塞，不会影响其他线程 的运行。时间片分配是以线程为单位的，所以多线程的进程获得更多CPU时间。,用户线程的维护由应用进程完成；内核不了解用户线程的存在；用户线程切换不需要内核特权；,不依赖于OS核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程，调度由应用软件内部进行，无需用户态/核心态切换，所以速度特别快。线程与内核无关，内核也不知道线程的存在。一个线程发起系统调用而阻塞，则整个进程在等待。时间片分配以进程为单位，多线程则每个线程就慢。,用户级线程与内核级线程,用户级线程与内核级线程的比较,用户级线程的切换，因发生在一个应用进程之间，无须通过中断进入OS内核，而且切换的规则也比较简单。用户级线程比内核级线程切换速度快,用户级线程在调用系统调用是以进程为单位。而内核级线程的系统调用是以线程为单位，因此比较轻装。用户级线程不如内核级线程,用户级线程不如内核级线程合理,3.3.4线程的特点,（1）创建线程无需另外分配资源；（2）线程间的互操作在同一地址空间；（3）线程能独立运行,3.4进程调度,3.4.1 进程调度的职能3.4.2 进程调度方式3.4.3 进程调度算法,3.4.1 进程调度的职能,进程调度程序具有的主要功能：（1）记录系统中所有进程的有关情况（2）确定分配处理机的原则（3）分配处理机给进程（4）从进程收回处理机,引起进程调度的相关因素：（1）正在运行的进程运行完毕；（2）运行中的进程要求I/O；（3）执行某种原语操作；（4）一个比正在运行进程优先数更高的进程申请运行；（5）分配给运行进程的时间片已经用完。,3.4.2进程调度的方式,可剥夺方式 可剥夺方式也被称为抢占方式。在这种方式下，允许一个进程按照某种原则，抢占其它进程占有的处理机。抢占采用优先权（也就是说，如果一个进程比正在运行进程的优先级高，则它可以抢占处理机而运行）、短进程、时间片原则，采用剥夺式调度的系统能及时处理紧急事件。不可剥夺方式不可剥夺方式也被称为非抢占方式。采用这种调度方式时，一旦把处理机分配给某个进程，该进程将一直执行下去，直到运行完毕或因某种原因不能运行，才把处理机分配给其它进程，决不允许其它进程强占正在运行进程占有的处理机。该方式算法简单，系统开销小，但不能反映出进程的优先级特征。,3.4.3进程调度算法,1、先来先服务 对于进程调度，从就绪队列中选择最先进入该队列的进程，分配处理机，使之运行。2、轮转调度算法思想进程按FCFS在就绪队列排队，调度程序把CPU分配给队首进程，令其执行一个时间片，一个时间片执行完毕将进程排在队尾,并将处理器的下一个时间片分配给就绪队列中的队首进程。,q=1与q=4时进程运行情况,3、分级轮转法算法思想：根据进程的类型不同,将进程就绪队列分为若干个独立的就绪队列,不同的就绪队列赋予不同的优先数,优先级高的就绪队列先调度,同一就绪队列采用统一调度算法。,算法思想从就绪队列中选择优先数最高的进程，将处理机分配给它。根据已占有处理机的进程是否可被剥夺可分为优先占有法和优先剥夺法。优先占有的原理是：一旦某个最高优先数的进程分得处理机后，只要不是因其自身原因被阻塞而不能继续运行时，会一直运行到结束。优先剥夺法的原理是：一个正在运行的进程即使时间片未用完，只要就绪队列中有一个比它优先数更高的进程，优先数更高的进程就可以抢占正在运行的进程的CPU，投入运行。,4、优先数调度算法,优先数类型静态优先数：每个进程的优先数在其生存期间保持不变。确定因素：进程类型、运行时间、作业的优先数。动态优先数：进程的优先数在该进程的存在期间可以改变。确定因素：等待时间、运行时间。特点：综合考虑各种情况,时间片大小的确定响应时间T=进程数目N*时间片q响应时间T当N一定，T与q成正比。T若要求快，则q也要小。就绪队列的进程数NT一定，q与N成反比。N越多，q要小。进程的转换时间 进程调度花费时间长短有关系统的处理能力保证用户键入的常用命令能在一个时间片内处理完毕。,算法思想根据作业的性质和类型不同，将就绪队列再分为若干个子队列，每个进程分属于一个队列。在多级队列的基础上，不但设多个队列，且为每个队列赋予不同的优先权，第一个队列的优先权最高，第二个队列次之，其余队列的优先权逐个降低，各个队列中的进程执行时间片大小逐渐增大。前n-1个队列采用先来先服务的调度策略，新创建的进程投入第一个队列队尾。最后一个队列采用轮转调度策略。调度从第一个队列进行，仅当第一个队列为空时，才调度第二个队列中的进程。队列之间的进程调度采用优先级可抢占式调度策略。,多级反馈队列调度算法,多级反馈队列调度算法,多级反馈队列调度算法基于剥夺式，使用动态优先级机制。,3.5 进程互斥和同步,3.5.1 互斥算法3.5.2 信号量(semaphore)3.5.3 经典进程同步问题3.5.4 管程(monitor)3.5.5 进程互斥和同步举例,返回,3.5.1 互斥算法,3.5.1.1临界资源3.5.1.2临界区的访问过程3.5.1.3同步机制应遵循的准则3.5.1.4进程互斥的软件方法3.5.1.5进程互斥的硬件方法,3.5 进程的同步与互斥,OS引入进程后，由于进程的异步性，可能会导致程序执行结果的不确定性，使程序执行时出现不可再现性。进程互斥与同步的主要任务是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。,基本概念,同步：指多个进程中发生的事件存在着某种时序关系，它们必须按规定时序执行，以共同完成一项任务。互斥：多个进程不能同时使用同一资源。临界资源：某段时间内仅允许一个进程使用的资源，如打印机、磁带机等硬件设备或变量、队列等数据。引起资源不可共享的原因：一是资源的物理特性；二是某些资源如果被几个进程使用，则一个进程的动作可能会干扰其它进程的动作。,3.5.1.1临界资源,进程间资源访问冲突共享变量的修改冲突操作顺序冲突进程间的制约关系间接制约：进行竞争独占分配到的部分或全部共享资源，“互斥”直接制约：进行协作等待来自其他进程的信息，“同步”,多个进程在对其进行访问时（关键是进行写入或修改），必须互斥地进行,如硬件或软件（如外设、共享代码段、共享数据结构）,有些共享资源可以同时访问，如磁盘、光盘等外存设备.,多道程序环境进程之间存在资源共享，进程的运行时间受影响,共享变量的修改冲突,进程的交互关系：可以按照相互感知的程度来分类,死锁，指多个进程互不相让，都得不到足够的资源；饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）,3.5.1.2临界区的访问过程,临界区,临界区是一个进程访问临界资源的那段程序代码。,临界区(critical section)：进程中访问临界资源的一段代码。进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志退出区(exit section)：用于将正在访问临界区标志清除。剩余区(remainder section)：代码中的其余部分。进程间的互斥可以描述为禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。,3.5.1.3同步机制应遵循的准则,空闲则入：其他进程均不处于临界区；忙则等待：已有进程处于其临界区；有限等待：等待进入临界区的进程不能死等；让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）,3.5.1.4进程互斥的软件方法,有两个进程Pi,Pj，其中的Pi,算法1：单标志,设立一个公用整型变量 turn：描述允许进入临界区的进程标识在进入区循环检查是否允许本进程进入：turn为i时，进程Pi可进入；在退出区修改允许进入进程标识：进程Pi退出时，改turn为进程Pj的标识j；,缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi让出临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区,致使临界资源没有进程访问,违背了进程同步机制中的”空闲让进”的原则.,算法2：双标志、先检查,设立一个标志数组flag：描述进程是否在临界区，初值均为FALSE。表示所有进程都未进入临界区。若flagi=true,表示进程进入临界区执行。在每个进程进入临界区时，先查看临界资源是否被使用，若正在 使用，该进程等待，否则才可进入。解决了“空闲让进”问题。在退出区修改本进程在临界区的标志；,优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。按下面序列执行时，会同时进入。即在检查对方flag之后和切换自己flag之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能连续进行,违背了“忙则等待”的同步原则。,算法3：双标志、后检查,类似于算法2，与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。,缺点：Pi和Pj可能都进入不了临界区。按下面序列执行时，会都进不了临界区。即在切换自己flag之后和检查对方flag之前有一段时间，结果都切换flag，都检查不通过,最终导致并发进程在While语句上等待,违背了“空闲让进”的原则。,算法4(Petersons Algorithm)：先修改、后检查、后修改者等待,结合算法1和算法3，是正确的算法turn=j;描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后：检查对方flag，如果不在临界区则自己进入空闲则入否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入先到先入，后到等待,表示只有进程j的标志flagj为进程j,并且标志turn为进程j时,才表示进程j访问临界区.,3.5.1.5进程互斥的硬件方法,完全利用软件方法，有很大局限性（如不适于多进程），导致一个进程在执行这两条（一条是看对方的标志，一条是设置自己的标志）指令时被另一个进程中断,最终产生进程对临界区的不正确访问,现在已很少采用。可以利用某些硬件指令其读写操作由一条指令完成，因而保证读操作与写操作不被打断；禁止中断专用机器指令TS（Test and Set）指令,Lock有两种状态：当lock=false时，表示资源空闲;当lock=true时，表示资源正在被使用。为了实现互斥，每个临界资源设置一个公共布尔变量lock，其初值为false,表示资源空闲。利用TS指令实现互斥。在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；,TS（Test and Set）指令,缺点：没有做到：“让权等待”。,硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点等待要耗费CPU时间，不能实现让权等待可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上可能死锁,3.5.2 信号量和P、V原语(semaphore),前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量（信号量代表可用资源实体的数量）就是OS提供的管理公有资源的有效手段。,进程间互斥和同步是一种通信方式，进程通过修改信号灯或其他方式通知另一进程。通信原语是实现进程间同步与互斥的一种工具。P操作和V操作是低级通信原语，消息缓冲是高级通信原语。,Lock和unlock大部分同步方案采用某个物理实体实现通信，进程通信原语中关锁和开锁是最简单的原语。在这两个原语中设置一个公共变量X代表某个临界资源的状态。X=0 表示资源可用。X=1 表示资源正在使用。进程使用临界资源必须做以下三个不可分割的操作：（1）检查X的值（2）进入临界区，访问临界资源（3）释放临界区资源，置X为0（开锁）。,1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识信号量只能通过初始化和两个标准的原语来访问作为OS核心代码执行，不受进程调度的打断初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量）若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数,1.P原语wait(s),-s.count;/表示申请一个资源;if(s.count 0)/表示没有空闲资源;调用进程进入等待队列s.queue;阻塞调用进程;,2.V原语signal(s),+s.count;/表示释放一个资源；if(s.count=0)/表示有进程处于阻塞状态；从等待队列s.queue中取出一个进程P;进程P进入就绪队列;,V原语通常唤醒进程等待队列中的头一个进程,有两个优先级相同的进程P1和P2，各自执行的操作如如下，信号量S1和S2的初值都为0，试问P1、P2并发执行后，x、y、z得值各是多少？P1：P2:Begin Begin y:=1;x:=1;y:=y+3;x:=x+5;V(S1);P(S1);z:=y+1;x:=y+x;P(S2);V(S2);y:=y+z;z:=x+z;end;end;,3.利用信号量实现互斥,为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏,4.利用信号量来描述前趋关系,前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个互斥信号量S12，其初值为0,3.5.3 经典进程同步问题,1.生产者消费者问题(the producer-consumer problem),问题描述：指有两组进程共享一个环形的缓冲池。一组进程被称为生产者，另一组进程被称为消费者。缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲区可以容纳一个产品。若干进程通过有限的共享缓冲区交换数据生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。,采用信号量机制：full是满数目，初值为0，empty是空数目，初值为N。实际上，full+empty=Nmutex用于访问缓冲区时的互斥，初值是1 每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁(为什么？),用信号量解决“生产者-消费者”问题,void consumer()/消费者进程while(true)P(full);P(mutex);data_c=bufferj;j=(j+1)%n;V(mutex);V(empty);consume the item in data_c;,semaphore mutex=1;semaphore empty=n;semaphore full=0;,int i,j;ITEM buffern;ITEM data_p,data_c;,void producer()/生产者进程 while(true)produce an item in data_p;P(empty);P(mutex);bufferi=data_p;i=(i+1)%n;V(mutex);V(full);,若两个P操作顺序颠倒会产生死锁 在缓冲区全部为满时会引起生产者进程进入缓冲区访问，却不能放入产品的问题，而此时消费者进程也不能进入缓冲区取走产品，生产者与消费者进程发生死锁；在缓冲区全部为空时会引起消费者进程进入缓冲区访问，却不能取走产品的问题，而此时生产者进程也不能进入缓冲区放产品，生产者与消费者进程发生死锁；,2.读者写者问题(the readers-writers problem),问题描述：一个数据对象若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求写操作，对此，我们把只想读的进程称为“读者”，而把要求写的进程称为“写者”。对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读写”互斥，“写写”互斥，读读允许,采用信号量机制：Wmutex表示允许写，初值是1。公共变量Rcount表示“正在读”的进程数，初值是0；Rmutex表示对Rcount的互斥操作，初值是1。,void reader()/*读者进程*/while(true)P(Rmutex);if(Rcount=0)P(Wmutex);Rcount=Rcount+1;V(Rmutex);read;/*执行读操作*/P(Rmutex);Rcount=Rcount-1;if(Rcount=0)V(Wmutex);V(Rmutex);,Semaphore Wmutex,Rmutex=1,1;int Rcount;,用信号量解决读者-写者问题,void writer()/*写者进程*/while(true)P(Wmutex);write;/*执行写操作*/V(Wmutex);,哲学家进餐问题,五个哲学家，他们的生活方式是交替地思考和进餐。哲学家们共用一张圆桌，围绕着圆桌而坐，在圆桌上有五个碗和五支筷子，每两个哲学家之间放一支；平时哲学家进行思考，饥饿时拿起其左、右的两支筷子，试图进餐，进餐完毕将两支筷子放回原处,又进行思考。这里的问题是哲学家只有拿到靠近他的两支筷子才能进餐，而拿到两支筷子的条件是他的左、右邻居此时都没有进餐。