第二章-进程描述与控制课件

计算机操作系统主讲教师：张静课程主要内容课程主要内容操作系统引论（1章）进程管理（2-3章）存储管理（4章）设备管理（5章）文件管理（6章）操作系统接口（7章）从进程的观点研究操作系统n把OS看作是由若干个可独立运行的程序和一个可对这些程序进行协调控制的核心（内核）组成。这些运行的程序称为进程，它是资源分配和独立运行的基本单位，每一进程都完成某一特定任务，而OS的内核则必须要控制和协调这些进程的运行，解决进程之间的通信，并从系统可并发工作为出发点，实现并发进程间通信，并解决由此带来的共享资源的竞争问题。第第2 2章章 进程的描述与控制进程的描述与控制n进程的基本概念与控制n进程的基本概念n进程控制n线程的基本概念nUNIX中进程的描述与控制n进程同步与通信n进程同步n经典进程的同步问题n管程机制n进程通信nUNIX中进程的同步与通信n调度与死锁（第3章）2.1 前趋图和程序执行n前趋图n程序顺序执行n程序并发执行一、前趋图的定义3有向无循环图,记DAG（Directed Acyclic Graph）124567结点，可表一语句、程序段或进程前趋关系初始结点终止结点前趋关系：P1 P2，P2 P5，P5 P7 P1 P3，P3 P5 P1 P4 ，P6 P7直接前趋直接后继Eg1：以下三条语句的前趋图为：s1:a:=x+y s2:b:=a-5 s3:c:=b+1 Eg2:S1：a:=x+2 S2:b:=y+4 S3:c:=a+b S4:d:=c+6 s1s2s3s1s2s3s4返回二、程序顺序执行二、程序顺序执行n程序执行时，必须按照某种先后次序逐个执行程序执行时，必须按照某种先后次序逐个执行nEg s1:a:=x+y s2:b:=a-5 s3:c:=b+1n程序顺序执行时有如下特征：n顺序性n封闭性n可再现性s1s2s3返回三、程序并发执行在处理一批作业时，有的程序可实现并发执行在处理一批作业时，有的程序可实现并发执行n n S1：a:=x+2 S2:b:=y+4 S3:c:=a+b S4:d:=c+6I1I2I3I4C1C2C3C4P1P2P3P4s1s2s3s4三、程序并发执行三、程序并发执行n程序并发执行时的特征n间断性n失去封闭性n不可再现性例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N:=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。这样，可能出现下述三种情况(假定某时刻变量N的值为n)。(1)N:=N+1在Print(N)和N:=0之前，此时得到的N值分别为n+1，n+1，0。(2)N:=N+1在Print(N)和N:=0之后，此时得到的N值分别为n，0，1。(3)N:=N+1在Print(N)和N:=0之间，此时得到的N值分别为n，n+1，0。（补充）（补充）程序并发执行的条件（Bernstein)2.2 2.2 进程的描述进程的描述一、一、进程进程processprocess的定义的定义 1）进程是程序的一次执行。2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。3）进程是程序在一个数据集合上的运行过程，它是系统进行资源分配和调度的一个独立单位。4）进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程实体（映像）：进程实体（映像）：程序程序+数据数据+进程控制块（进程控制块（PCBPCB）二、进程的特征二、进程的特征1）动态性2）并发性3）独立性 4）异步性 程序进程概念静态动态所在存储器外存内存存在时间永久有生命期组成有序指令程序段,数据段,PCB对应关系一个程序可对应多个进程一个进程可对应多个程序三、进程与程序的主要区别三、进程与程序的主要区别四、四、进程状态进程状态 为了刻画了整个进程，可以将一个进程的生命周期划分为一组状态：1、进程的5种状态（三种基本状态三种基本状态）nNew新建/创建:进程正在创建中的状态nReady就绪就绪:进程已获得了除处理机以外的所有资源，等待分配处理机执行的等待状态。nRunning运行/执行执行:当一个进程获得必要的资源并正在处理机上执行的状态。nBlock等待/阻塞阻塞:正在执行的进程由于发生某事件而暂时无法执行下去，此时进程所处的状态。nTerminated终止/撤消/退出：进程执行完毕，释放所占资源的状态。进程在运行期间并非固定处于某个状态，而是不断从一个状态转换到另一个状态。2 2、进程状态转换、进程状态转换3 3、进程的挂起状态、进程的挂起状态 在某些系统中，为了更好地管理和调度进程，引入了挂起状态：n挂起状态挂起状态/静止状态：静止状态：程序在运行期间，由于某种需要，往往要将进程暂停执行，使其静止下来，以满足其需要。这种静止状态就称为进程的挂起状态。引起挂起状态的原因引起挂起状态的原因 终端用户的需要终端用户的需要父进程的需要父进程的需要操作系统的需要操作系统的需要对换的需要对换的需要负荷调节的需要负荷调节的需要 引入挂起原语后三个进程状态的转换n活动就绪-静止就绪n活动阻塞-静止阻塞n静止就绪-活动就绪n静止阻塞-活动阻塞具有挂起状态的进程状态具有挂起状态的进程状态 在引入挂起状态后，就增加了挂起状态（静止状态）与非挂起状态（活动状态）间的转换，如图所示：返回4 4、进程管理中的数据结构、进程管理中的数据结构 OS管理的数据结构一般分为四类：内存表、设备表、文件表和进程表（PCB）。（1 1）进程控制块）进程控制块PCBPCB 是操作系统为了管理和控制进程的运行而为每一个进程定义的一个数据结构，它记录了系统管理进程所需的全部信息。系统根据PCB而感知进程的存在，PCB是进程存在的唯一标志。PCB常驻内存.（2 2）进程控制块）进程控制块PCBPCB的作用的作用 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。u作为独立运行基本单位的标志u能实现间断性运行方式u提供进程管理所需要的信息u提供进程调度所需要的信息u实现与其它进程的同步和通信（3 3）进程控制块）进程控制块PCBPCB中的信息中的信息 根据操作系统的要求不同，PCB所包含信息有些不同，但通常包含以下信息：进程标志符进程标志符：(1)内部标识符(2)外部标识符处理机状态（断点信息）处理机状态（断点信息）：即处理机中各种寄存器（通用寄存器、指令计数器、程序状态字PSW等）的内容.进程调度进程调度：记录了进程调度的相关信息（状态、优先级、事件等）。进程控制进程控制：记录了系统对进程控制的信息（程序和数据的地址、同步机制、资源清单、链接指针）（4 4）进程控制块）进程控制块PCBPCB的组织方式的组织方式 在一个系统中，通常存在着许多进程，它们所处的状态不同，为了方便进程的调度和管理，需要将各进程的PCB用适当方法组织起来。目前常用的组织方式有：链接方式链接方式 图示 把同一状态的PCB链接成一个队列，这样就形成了就绪队列、阻塞队列等。索引方式索引方式 图示 将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB，不同状态对应不同的索引表。3 3 线性方式线性方式 1PCB90PCB89PCB77PCB6 PCB58PCB40PCB33PCB24PCB1执行指针就绪队列指针阻塞队列指针空闲队列指针按链接方式组织PCB按索引方式组织PCB1PCB90PCB89PCB77PCB6 PCB58PCB40PCB33PCB24PCB1执行指针就绪表指针阻塞表指针就绪索引表阻塞索引表2.3 2.3 进程的控制进程的控制 进程控制是进程管理中最基本的功能，即对系统中所有的进程实施有效的管理，其功能包括进程的创建、撤消、阻塞与唤醒等，这些功能一般是由操作系统的内核中的原语来实现的。处理机的执行状态处理机的执行状态 为防止OS及其关键数据（如PCB等)不被用户有意或无意破坏,通常将处理机的执行状态分为两种处理机状态特权(执行指令,访问）程序系统态系统态(核心态核心态 管态管态)较高(一切指令,所有R及存储区)OS内核用户态（目态）用户态（目态）较低(规定指令,指定R及存储区)用户程序一、一、OS OS 内核内核 在现代OS中，常把一些功能模块（与硬件紧密相关的、常用设备的驱动程序及运行频率较高的）放在紧靠硬件的软件层次中，加以特殊保护，同时把它们常驻内存，以提高OS的运行效率，这部分功能模块就称OS的内核。目的：便于软件保护、提高OS运行效率 内核是基于硬件的第一层软件扩充，它为系统控制和管理进程提供了良好的环境。处理机的执行状态：系统态（管态、内核态）、用户态（目态）OS内核的两大功能n支撑功能中断处理、时钟管理、原语操作n资源管理功能进程管理、存储器管理、设备管理 原语(Primitive)是由若干条指令组成的，用于完成一定功能的一个过程。它与一般过程的区别在于：它们是“原子操作(Action Operation)”。原子操作，是不可分割的基本单位，在执行中不允许被中断。原子操作在管态下执行，常驻内存。二、二、进程的创建进程的创建 一个进程可以创建若干个新进程，新创建的进程又可以创建子进程，为了描述进程之间的创建关系，引入了进程图（如下图所示：）（1 1）进程图）进程图：又称为进程树或进程家族树，是描述进程家族关系的一棵有向树。ABDECF父进程祖先进程子进程（2 2）引起进程创建的事件）引起进程创建的事件 在多道程序环境中，只有进程才可以在系统中运行。为了使一个程序能运行，必须为它创建进程。导致进程创建的事件有：u用户登录用户登录作业调度作业调度提供服务提供服务应用请求应用请求（3 3）进程的创建）进程的创建 操作系统一旦发现了要求创建进程的事件后，便调用进程创建原语create()按以下过程创建一新进程：申请一个空闲的申请一个空闲的PCBPCB为新进程分配资源为新进程分配资源对对PCBPCB初始化初始化将将PCBPCB插入就绪队列插入就绪队列返回一个进程标识号返回一个进程标识号（进程控制块）PCB的初始化包括：初始化标识信息，将系统分配的标识符和父进程标识符填入新PCB中；初始化处理机状态信息，使程序计数器指向程序的入口地址，使栈指针指向栈顶；初始化处理机控制信息，将进程的状态设置为就绪状态或静止就绪状态，通常把新建立的设置为最低优先级，除非用户以显式方式提出高优先级要求。如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列 一个进程在完成其任务后，应加以撤消，以便及时释放其占有的各类资源。（1 1）导致进程撤消的事件）导致进程撤消的事件u进程正常结束u进程异常结束u外界干预 三、三、进程的终止进程的终止n正常结束正常结束：系统中，都有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统调用。当程序运行到Holt指令时，将产生一个中断，通知OS进程已经完成。在分时系统中，用户可利用Logs off去表示进程运行完毕，同样可产生一个中断，通知OS进程已运行完毕。异常结束：异常结束：（1）越界错误。程序访问的存储区越出该进程的区域。(2)保护错。进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件。(3)非法指令。试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令。(4)特权指令错。进程试图去执行一条只允许OS执行的指令。(5)运行超时。进程的执行时间超过指定最大值。(6)等待超时。进程等待某事件的时间超过规定的最大值。(7)算术运算错。进程试图去执行一个被禁止的运算，例如被0除。(8)I/O故障。这是指在I/O过程中发生了错误等。n外界干预：外界干预：是指进程应外界的请求而终止运行。这些干预有：(1)操作员或系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程。(2)父进程请求。由于父进程具有终止自己的任何子孙进程的权力，因而当父进程提出请求时，系统将终止该进程。(3)父进程终止。当父进程终止时，OS也将它的所有子孙进程终止。（2）进程的终止过程进程的终止过程如果系统中发生了上述要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止指定的进程。1)根据进程标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。3)若有子孙进程，应将所有子孙进程予以终止4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。5)被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。在运行？在运行？NYNY由标识符在由标识符在PCBPCB集中找集中找PCBPCB并读状态并读状态归还占有资源归还占有资源从所在队列从所在队列(索引表索引表)撤消撤消PCBPCB中止运行重置调度标志中止运行重置调度标志终止所有子孙进程终止所有子孙进程有子孙进程？有子孙进程？当一个进程期待的事件尙未出现时，该进程调用阻塞原语block()（功能：将进程由执行状态转为阻塞状态）将自己阻塞起来。对于处于阻塞状态的进程，当该进程期待的事件出现时，由其它相关进程调用唤醒原语wakeup()（功能：将进程由阻塞状态变为就绪状态）将阻塞的进程唤醒，使其进入就绪状态。（1）引起进程阻塞和唤醒的事件请求系统服务启动某种操作新数据尚未到达无新工作可做四、进程的阻塞与唤醒四、进程的阻塞与唤醒停止执行停止执行修改修改PCBPCB中的状态中的状态（执行（执行-阻塞）阻塞）插入到相应的阻塞队列插入到相应的阻塞队列另调度一就绪进程，切换另调度一就绪进程，切换CPUCPU（保留阻塞进程的（保留阻塞进程的CPUCPU状态）状态）将阻塞进程移出阻塞队列将阻塞进程移出阻塞队列插入到就绪队列插入到就绪队列另调度一就绪进程，切换另调度一就绪进程，切换CPUCPU（保留阻塞进程的（保留阻塞进程的CPUCPU状态）状态）修改修改PCBPCB中的状态中的状态（阻塞（阻塞-就绪）就绪）（2 2）进程的阻塞过程）进程的阻塞过程（3 3）进程的唤醒过程）进程的唤醒过程 当引起进程挂起的事件发生时，系统就将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。当发生激活进程的事件时，系统就将利用激活原语active()将指定进程激活。1 1、引起进程的挂起与激活的事件引起进程的挂起与激活的事件五五、进程的挂起与激活、进程的挂起与激活2、进程的挂起过程检查该进程状态检查该进程状态修改修改PCBPCB中的状态中的状态*（活动（活动-静止）静止）复制复制PCBPCB至指定内存区域至指定内存区域运行？运行？另调度另调度一就绪进程一就绪进程3、进程的激活过程NY将挂起进程从外存调入内存将挂起进程从外存调入内存决定是否需重新调度决定是否需重新调度修改修改PCBPCB中的状态中的状态*（静止（静止-活动）活动）活动就绪？活动就绪？2.4 2.4 进程同步进程同步n进程同步进程同步是指对多个相关进程在执行次序上进行协调，它的目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性；或系统中诸进程之间在逻辑上的相互制约的关系（直接的-同步；间接的互斥）。n用来实现同步的机制称为同步机制。如：信号量机制；管程机制。一、进程同步的基本概念一、进程同步的基本概念（1 1）两种形式的制约关系）两种形式的制约关系系统中诸进程之间在逻辑上存在着两种制约关系：n直接制约关系（进程同步）直接制约关系（进程同步）：即为完成同一个任务的诸进程间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。这种制约主要源于进程间的合作。n间接制约关系（进程互斥）间接制约关系（进程互斥）：是进程共享独占型资源而必须互斥执行的间接制约关系。n同步与互斥比较同步与互斥比较同同 步步互互 斥斥进程-进程进程-资源-进程时间次序上受到某种限制竞争到某一物理资源时不允许进程工作相互清楚对方的存在及作用，交换信息不一定清楚其进程情况往往指有几个进程共同完成一个任务往往指多个任务多个进程间通讯制约例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间例：交通十字路口，单轨火车的拨道岔（2 2）临界资源、临界区）临界资源、临界区n一次只允许一个进程使用的资源称为临界资源一次只允许一个进程使用的资源称为临界资源，如打印机，绘图机；变量，数据等，诸进程间采取互斥方式式实现对这种临界资源的共享，从而实现并行程序的封闭性。例例：有两个进程A和B，它们共享一个变量x，且两个进程按以下方式对变量X进行访问和修改:其中R1和R2为处理机中的两个寄存器。A与B均对X+1，即X+2。若按另一顺序对变量进行修改：结果x只加了1.A:R1=X;B:R2=X;A:R1=R1+1;X=R1;B:R2=R2+1;X=R2;A:R1=X;R1=R1+1;X=R1;B:R2=X;R2=R2+1;X=R2;（1 1）变量）变量X X必必需按临界资源需按临界资源处理。处理。（2 2）每个进程）每个进程中访问临界资中访问临界资源的那段代码源的那段代码称为临界区称为临界区 为了保证临界资源的正确使用，可以把临界资源的访问临界资源的访问过程过程分成以下几部分：进入区临界区退出区剩余区v进入区增加在临界区前面的一段代码，用于检查欲访问的临界资源此刻是否被访问。v退出区增加在临界区后面的一段代码，用于将临界资源的访问标志恢复为未被访问标志。v剩余区进程中除了进入区、临界区及退出区之外的其余代码。（3 3）同步机制应遵循的规则）同步机制应遵循的规则q有空让进有空让进(空闲让进）空闲让进）q互斥（忙则等待）互斥（忙则等待）q有限等待有限等待q让权等待让权等待 要进入临界区的若干进程必须满足要进入临界区的若干进程必须满足：（1）一次只允许一个进程进入临界区（2）任何时候，处于临界区的进程不得多于一个（3）进入临界区的进程要在有限的时间内退出（4）如果不能进入自己的临界区，则应让出处理机资源解决临界区（互斥）问题的几类方法：解决临界区（互斥）问题的几类方法：（1）软件方法（2）硬件方法（3）P-V操作进入区临界区退出区剩余区同步机制二、硬件同步机制u硬件方法硬件方法 用硬件方法来解决临界区问题，即定义一些特殊指令，如用硬件方法来解决临界区问题，即定义一些特殊指令，如TEST TEST、SETSET、SWAPSWAP等指令，有效地实现了进程互斥，但不满足等指令，有效地实现了进程互斥，但不满足“让权等待让权等待”。锁开进入，锁关等待锁开进入，锁关等待 测试和关锁操作必须连续测试和关锁操作必须连续1.1.关中断：关中断：优点：保证了对锁的测试和关锁操作的连续性和完整性，有效优点：保证了对锁的测试和关锁操作的连续性和完整性，有效保证了互斥保证了互斥 缺点：滥用关中断权力后果严重缺点：滥用关中断权力后果严重 关中断时间多长影响系统效率关中断时间多长影响系统效率 不适用多处理机系统不适用多处理机系统 有效解决同步问题的方法有效解决同步问题的方法信号机制信号机制为临界资源加锁的方法2.2.利用利用Test-and-SetTest-and-Set指令实现互斥指令实现互斥nTS指令一般性描述：boolean TS(boolean*lock)boolean old;old=*lock;*lock=TRUE;return old;循环程序：do while TS(&lock);critical section;lock=FALSE;remainder section;while(TRUE);3.利用Swap指令实现进程互斥 对换指令，XCHG指令，用于交换两个字的内容。其处理过程描述如下：void swap(boolean*a,boolean*b)boolean temp;temp=*a;*a=*b;*b=temp;循环程序：do key=TRUE;do swap(&lock,&key);while(key!=FALSE);临界区操作；lock=FALSE;while(TRUE);忙等三、信号量机制n信号量机制是荷兰科学家E.W.Dijkstra在1965年提出的一种同步机制，也称为P、V操作。由最初的整型信号量发展为记录型信号量，进而发展为信号量集。n整型信号量整型信号量n记录型信号量记录型信号量n信号量集（信号量集（ANDAND信号量集、一般信号量集）信号量集、一般信号量集）1 1、整型信号量、整型信号量n整型信号量整型信号量非负整数，除了初始化外，只能通过两个原子操作waitwait和signalsignal（P P，V V）来访问。nwaitwait和和signalsignal操作描述操作描述：wait(S)wait(S)while S while S 0 0 测试有无可用资源 S-S-；可用资源数减一个单位 signal(S)S+;signal(S)S+;主要问题主要问题：只要S S 0 0，waitwait操作就不断地测试（忙等），因而，未做到“让权等待”。2 2、记录型信号量、记录型信号量n基本思想基本思想 1、设置一个代表资源数目的整型变量valuevalue（资源信号量）2、设置一链表L L用于链接所有等待的进程记录型信号量的数据结构记录型信号量的数据结构 typedef struct int value;struct process_control_block*list;semaphore;waitwait和和signalsignal操作描述操作描述：wait(semaphore*S)wait(semaphore*S)S.value-;S.value-;if S.value0 block(S.list);if S.value=1 and and Sn=1)for(i:=1;i=n;i+)Si-;break;elseplace the process in the waiting queue associated with the first Si found with Si1，and set the program count of this process to the beginning of Swait operation Ssignal(S1，S2，Sn)while(TRUE)for(i:=1;i=t1 and and Sn=tn)for(i:=1;i=n;i+)Si=Si-di；else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation.Ssignal(S1，d1，Sn，dn)for(i:=1;i1时)或互斥信号量(S=1时)。(3)Swait(S，1，0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。四、信号量的应用四、信号量的应用1.1.利用信号量实现进程互斥利用信号量实现进程互斥 利用信号量可以方便地解决临界区问题（进程互斥）。为临界资源设置一互斥信号量mutex，初值为1，取值（-1,0,1），则实现进程P1和P2互斥的描述：Semaphore mutex=1P1()while(1)wait(mutex);临界区临界区;signal(mutex);剩余区；剩余区；P2（）（）while(1)wait(mutex);临界区临界区;signal(mutex);剩余区；剩余区；2.2.利用信号量描述前趋关系利用信号量描述前趋关系 信号量可用来描述程序或语句间的前趋关系。n设有两个并发执行的进程P1和P2。P1中有语句S1；P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系，我们只须使进程P1和P2共享一个公用信号量S，并赋予其初值为0，将signal(S)操作放在语句S1后面；而在S2语句前面插入wait(S)操作，即在进程P1中，用S1；signal(S)；在进程P2中，用wait(S)；S2；前趋图举例 p1()S1；signal(a)；signal(b)；p2()wait(a)；S2；signal(c)；signal(d)；p3()wait(b)；S3；signal(e);p4()wait(c)；S4；signal(f)；p5()wait(d)；S5；signal(g)；p6()wait(e)；wait(f)；wait(g)；S6;main()semaphore a,b,c,d,e,f,g;a.value=b.value=c.value=d.value=e.value=f.value=g.value=0;cobegin p1();p2();p3();p4();p5();p6();coend五、管程机制n信号量机制实现进程同步的问题信号量机制实现进程同步的问题 用信号量机制实现进程间的同步和互斥，即方便又有效。但存在以下两个问题：v 每个访问临界资源的进程都必须自备同步操作（P、V操作），这使大量的同步操作分散在各个进程中，给系统的管理带来麻烦。v会因同步操作使用不当而导致系统死锁。n解决方法解决方法-管程（管程（Monitors)Monitors)Dijkstra于1971年提出，为每个共享资源设立一个“秘书”来管理对它的访问。一切来访者都要通过秘书，而秘书每次仅允许一个来访者（进程）来访问共享资源。这样既便于系统管理共享资源，又能保证进程的互斥访问和同步。1973年，Hanson和Hoare又把“秘书”概念发展为管程概念。一、管程的基本概念基本思想基本思想 把访问某种临界资源的所有进程的同步操作都集中起来，构成一个所谓的“秘书秘书”进程（管程）进程（管程），凡是访问临界资源的进程，都需要报告“秘书”，由秘书来实现诸进程的同步。管程的定义管程的定义 一个数据结构一个数据结构和在该数据结构上能被并发进程所执行的一组操作一组操作，这组操作能同步进程和改变管程中的数据。如下图所示。管程由四部分组成：管程由四部分组成：管程的名称；局部于管程内部的共享数据结构说明；对该数据结构进行操作的一组过程；对局部于管程内部的共享数据设置初始值的语句。管程的语法描述：Monitor monitor_name share variable declarations;cond declarations;public:void P1()void P2()/管程主体 initialization code;管程特性：(1)模块化。管程是一个基本程序单位，可以单独编译。(2)抽象数据类型。管程中不仅有数据，而且有对数据的操作。(3)信息掩蔽。管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见。管程和进程不同，主要体现在以下几个方面：(1)虽然二者都定义了数据结构，但进程定义的是私有数据结构PCB，管程定义的是公共数据结构，如消息队列等；(2)二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关的操作，而管程主要是进行同步操作和初始化操作；(3)设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题；(4)进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样被调用，因而管程为被动工作方式，进程则为主动工作方式；(5)进程之间能并发执行，而管程则不能与其调用者并发；(6)进程具有动态性，由“创建”而诞生，由“撤销”而消亡，而管程则是操作系统中的一个资源管理模块，供进程调用。条件变量条件变量 在管程机制中，当某进程通过管程请求临界资源未能满足时，管程便调用wait原语使该进程等待，但等待的原因可能有多个，为了加以区别，在P，V操作前，引入条件变量加以说明。（1 1）条件变量的定义格式）条件变量的定义格式 Var x,y:condition （2 2）对条件变量执行的两种操作）对条件变量执行的两种操作nWait操作 如x.wait用来将执行进程挂到与条件变量x相应的等待队列上。nSignal操作 如x.signal用来唤醒与条件变量x相应的等待队列上的一个进程。2.5 2.5 经典进程的同步问题经典进程的同步问题 在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：生产者生产者消费者问题消费者问题哲学家进餐问题哲学家进餐问题读者读者写者问题写者问题一、一、“生产者生产者消费者消费者”问题问题n问题描述问题描述 P1P2pmc1c2cmn设置两个同步信号量及一互斥信号量设置两个同步信号量及一互斥信号量empty：说明空缓冲单元的数目，其初值为有界缓冲区的大小说明空缓冲单元的数目，其初值为有界缓冲区的大小n n。Full：说明满缓冲单元的数目（即产品数目），其初值为说明满缓冲单元的数目（即产品数目），其初值为0.0.Mutex:说明该有界缓冲区是一临界资源，必须互斥使用，说明该有界缓冲区是一临界资源，必须互斥使用，其初值为其初值为1 1。1.记录型信号量解决“生产者消费者”问题int in=0,out=0;item buffern;semaphore mutex=1，empty=n，full=0；void proceducer()do producer an item nextp；wait(empty)；wait(mutex);bufferin=nextp；in=(in+1)%n；signal(mutex)；signal(full)；while(TRUE);void consumer()do wait(full)；wait(mutex)；nextc=bufferout；out=(out+1)%n;signal(mutex)；signal(empty)；consumer the item in nextc；while(TRUE);void main()cobegin proceducer();consumer();coend“生产者-消费者”问题中应注意1.互斥信号量的P,V操作在每一程序中必须成对出现.2.资源信号量(full,empty)也必须成对出现,但可分别处于不同的程序中.3.多个P操作顺序不能颠倒.4.先执行资源信号量的P操作,再执行互斥信号量的P操作,否则可能引起进程死锁.5.它是一个同步问题：（1）消费者想要取产品，有界缓冲区中至少有一个单元是满的。（2）生产者想要放产品，有界缓冲区中至少有一个是空的。6.它是一互斥问题 有界缓冲区是临界资源，因此，各生产者进程和各消费者进程必须互斥执行。返回2 2利用利用ANDAND信号量解决生产者信号量解决生产者消费者问题消费者问题 对于生产者消费者问题，也可利用AND信号量来解决，即用Swait(empty，mutex)来 代 替 wait(empty)和 wait(mutex)；用Ssignal(mutex，full)来 代 替 signal(mutex)和 signal(full)；用Swait(full，mutex)来 代 替 wait(full)和 wait(mutex)，以 及 用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)。利用AND信号量来解决生产者消费者问题的算法描述如下：int in=0,out=0;item buffern;semaphore mutex=1，empty=n，full=0；void proceducer()do producer an item nextp；Swait(empty,mutex);bufferin=nextp；in=(in+1)%n；Ssignal(mutex,full)；while(TRUE);void consumer()do Swait(full,mutex)；nextc=bufferout；out=(out+1)%n;Ssignal(mutex,empty)；consumer the item in nextc；while(TRUE);void main()cobegin proceducer();consumer();coend3.3.用管程机制解决生产者用管程机制解决生产者消费者问题消费者问题建立Producer-consumer(PC)管程n put(x)过程 生产者利用此过程将自已的消息放到缓冲池中，若发现缓冲已满（count n),则等待。nget(x)过程 消费者利用此过程将缓冲池中的消息取走，若发现缓冲已空（count 0),则等待。过程cwait和csignal对条件变量notfull和notempty进行操作 （1）cwait(condition)当管程被一个进程占用时，其他进程调用该过程时阻塞，并挂在条件condition队列上 （2）csignal(condition)唤醒在cwait执行后阻塞在条件condition队列上的进程，如果这样的进程不止一个，则选择其中一个实施唤醒操作；如果队列为空，则无操作而返回。PCPC管程可描述如下管程可描述如下Monitor procducerconsumer item bufferN;int in,out;condition notfull,notempty;int count;public:void put(item x)if(count=N)cwait(notfull);bufferin=x;in=(in+1)%N;count+;csignal(notempty);Void get(item x)if(count=0)cwait(notempty);x=bufferout;out=(out+1)%N;count-;csignal(notfull);in=0;out=0;count=0;PC生产者生产者消费者描述消费者描述void producer()void producer()item x;item x;while(TRUE)while(TRUE)produce an item in nextp;produce an item in nextp;PC.put(x);PC.put(x);Void consumer()Void consumer()item x;item x;while(TRUE)PC.get(x);while(TRUE)PC.get(x);consume the item in nextc;consume the item in nextc;void main()cobegin proceducer();consumer();coend 二、二、“哲学家进餐哲学家进餐”问题问题n问题描述：问题描述：有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。n哲学家进餐问题可看作是并发进程并发执行时，处理共享资源的一个有代表性的问题。哲学家进餐结构图所有信号量均被初始化为1，第i位哲学家的活动可描述为：dowait(chopsticki)；wait(chopstick(i+1)%5)；eat；signal(chopsticki)；signal(chopstick(i+1)%5)；think；while(TRUE);三、三、“读者读者写者写者”问题问题n问题描述：问题描述：一个数据对象（数据文件或记录）可被多个进程共享。其中，reader进程要求读，writer 进程要求写或修改。允许多个reader进程同时读共享数据，但绝不允许一个writer进程与其它的reader进程或writer进程同时访问，即writer进程必须与其它进程互斥访问共享对象。n“读者读者写者写者”问题的同步算法描述问题的同步算法描述 设置一个共享变量和两个信号量：设置一个共享变量和两个信号量：共享变量Readcount：记录当前正在读数据集的读进程数目，初值为0。读互斥信号量Rmutex：表示读进程互斥地访问共享变量 readcount，初值为1.写互斥信号量wmutex：表示写进程与其它进程（读、写）互斥地访问数据集，初值为1.“读者读者写者写者”问题的解决问题的解决读者写者问题可描述如下:semaphore rmutex=1，wmutex=1；int readcount=0；void reader()do wait(rmutex)；if(readcount=0)wait(wmutex)；readcount+；signal(rmutex)；perform read operation；wait(rmutex)；readcount-；if(readcount=0)signal(wmutex)；signal(rmutex)；while(TRUE)；void writer()do wait(wmutex)；perform write operation；signal(wmutex)；while(TRUE)；void main()cobegin reader();writer();coend 利用信号量集机制解决读者写着问题 最多只允许RN个读者同时读int RN;semaphore L=RN,mx=1;void reader()do Swait(L,1,1);Swait(mx,1,0);perform read operation;Ssignal(L,1);while(TRUE)；void writer()do Swait(mx,1,1;L,RN,0);perform read operation;Ssignal(mx,1);while(TRUE)；void main()cobegin reader();writer();coend信号量例题1.桌子上有一个空盘子，只允许放一个水果。爸爸可以向盘中放苹果，也可以向盘中放橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一个水果，请用信号量实现爸爸、儿子、女儿三个“并发进程”的同步。爸爸、儿子、女儿的同步过程描述如下：Semaphore empty=1,orange=apple=0;father：do wait(empty);将水果放入盘中；if（放入的是橘子）signal(orange);else signal(apple);while(1);Son:do wait(orange);从盘中取出橘子；signal(empty);吃橘子；while(1);Daughter:do wait(apple);从盘中取出苹果；signal（empty）；吃苹果；while(1);2.6 进程通信高级通信一、进程通信的类型一、进程通信的类型 进程通信是指进程之间的信息交换。根据所交换的信息量的多少分为：v低级通信低级通信 进程之间交换的信息量较少且效率低。如进程同步和互斥。v高级通信高级通信 进程之间交换的信息量较多且效率高。又分：共享存储器系统共享存储器系统 指进程之间通过对共享存储区读写来交换数据。消息传递系统消息传递系统 指进程间的通信以消息为单位，程序员可通过通信原语 实现通信，按其实现方式不同可分为：直接通信方式直接通信方式 发送进程直接把消息发送给接收进程。间接通信方式间接通信方式 发送进程把消息发送到某个中间实体（信箱），接收进 程从中取得消息。管道通信系统管道通信系统 发送进程（写进程）以字符流形式将大量数据送入管道（管道：用于连接读进程和写进程以实现它们之间通信的共享文件管道：用于连接读进程和写进程以实现它们之间通信的共享文件。），接收进程（读进程）从管道接收数据。客户机客户机-服务器系统服务器系统 实现方法：实现方法：套接字、远程过程调用和远程方法调用 二、*消息传递系统 -直接通信方式（消息缓冲通信）发送进程利用OSOS所提供的发送命令，直接把消息发送给接收进程。n要求：发送进程和接收进程都以显式方式提供对方的标识符。n系统提供的两条通信原语：nSend(Receiver,message);发送一个消息给接收进程；nReceive(Sender,message);接收Sender发来的消息；n生产者-消费者问题的解决 repeat.Produce an item in nextp;.send(consumer,nextp);until false;repeat.Receive(producer,nextc);.consume the item in nextc until false二、消息传递系统 -间接通信方式（信箱通信）发送进程把消息发送到某个中间实体（信箱），接收进程从中取得消息。n系统提供的若干条原语系统提供的若干条原语n信箱创建和撤消原语n两条通信原语Send(mailbox,message)将一个消息发送给指定信箱；Receive(mailbox,message)从指定信箱中接收一个消息；n信箱的分类：信箱的分类：私用信箱、公用信箱、共享信箱2.7 2.7 线程线程 线程是近年来操作系统领域出现的一个非常重要的技术，其引入进一步提高了程序并发执行的程度，从而进一步提高了资源的利用率和系统的吞吐量。线程的基本概念线程间的同步和通信内核支持线程和用户级线程线程控制 一、线程的基本概念一、线程的基本概念1 1线程的引入线程的引入操作系统中引入进程的目的，是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量，那么，在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。进程的两个基本属性:进程是一个可拥有资源的独立单位；进程同时又是一个可独立调度和分派的基本单位。正是由于进程有这两个基本属性，才使之成为一个能独立运行的基本单位，从而也就构成了进程并发执行的基础。然而，为使程序能并发执行，系统还必须进行以下的一系列操作。1)创建进程系统在创建一个进程时，必须为它分配其所必需的、除处理机以外的所有资源，如内存空间、I/O设备，以及建立相应的PCB。2)撤消进程系统在撤消进程时，又必须先对其所占有的资源执行回收操作，然后再撤消PCB。3)进程切换对进程进行切换时，由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，因而须花费不少的处理机时间。换言之，由于进程是一个资源的拥有者，因而在创建、撤消和切换中，系统必须为之付出较大的时空开销。正因如此，在系统中所设置的进程，其数目不宜过多，进程切换的频率也不宜过高，这也就限制了并发程度的进一步提高。2 2线程与进程的比较线程与进程的比较线程的组成主要包括：（1）一个被称为线程ID（thread ID，线程标识符）的唯一标识符；（2）两个栈，分别用于记录在内核模式下和用户模式下执行的；（3）一个被称为线程局部存储器（TLS，thread-local storage）的私有存储区域，各个子系统、运行库和DLL都会用到该存储区域；（4）一组代表处理器状态的CPU寄存器中的内容；（5）有时候线程也有它们自己的安全环境，如果多线程服务器应用程序要模仿其客户的安全环境，则往往可以利用线程的安全环境。1)调度 在传统的操作系统中，作为拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位，把传统进程的两个属性分开，使线程基本上不拥有资源，这样线程便能轻装前进，从而可显著地提高系统的并发程度。在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。2)并发性在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，使得操作系统具有更好的并发性，从而能更加有效地提高系统资源的利用率和系统的吞吐量。例如，在一个未引入线程的单CPU操作系统中，若仅设置一个文件服务进程，当该进程由于某种原因而被阻塞时，便没有其它的文件服务进程来提供服务。在引入线程的操作系统中，则可以在一个文件服务进程中设置多个服务线程。当第一个线程等待时，文件服务进程中的第二个线程可以继续运行，以提供文件服务；当第二个线程阻塞时，则可由第三个继续执行，提供服务。显然，这样的方法可以显著地提高文件服务的质量和系统的吞吐量。3)拥有资源不论是传统的操作系统，还是引入了线程的操作系统，进程都可以拥有资源，是系统中拥有资源的一个基本单位。一般而言，线程自己不拥有系统资源(也有一点必不可少的资源)，但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，如已打开的文件、I/O设备等，可以供该进程中的所有线程所共享。4)系统开销在创建或撤消进程时，系统都要为之创建和回收进程控制块，分配或回收资源，如内存空间和I/O设备等，操作系统所付出的开销明显大于线程创建或撤消时的开销。类似地，在进程切换时，涉及到当前进程CPU环境的保存及新被调度运行进程的CPU环境的设置，而线程的切换则仅需保存和设置少量寄存器内容，不涉及存储器管理方面的操作，所以就切换代价而言，进程也是远高于线程的。此外，由于一个进程中的多个线程具有相同的地址空间，在同步和通信的实现方面线程也比进程容易。在一些操作系统中，线程的切换、同步和通信都无须操作系统内核的干预。5）地址空间被创建的线程共享所属进程的地址空间，每个线程有自己的执行堆栈和程序计数器为其执行上下文；而进程与子进程之间的地址空间是相互独立的。6）通信由于同一进程的多个线程共享相同的地址空间，这些线程之间的同步与通信的实现过程也简单多了，不需要内核干预，或者通过变量访问即可完成某些通信工作。而进程之间的通信需要通过专门的通信机制来实现。3 3线程的属性线程的属性在多线程OS中，通常是在一个进程中包括多个线程，每个线程都是作为利用CPU的基本单位，是花费最小开销的实体。线程具有下述属性。(1)轻型实体。线程中的实体基本上不拥有系统资源，只是有一点必不可少的、能保证其独立运行的资源，比如，在每个线程中都应具有一个用于控制线程运行的线程控制块TCB，用于指示被执行指令序列的程序计数器，保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。(2)独立调度和分派的基本单位。在多线程OS中，线程是能独立运行的基本单位，因而也是独立调度和分派的基本单位。由于线程很“轻”，故线程的切换非常迅速且开销小。(3)可并发执行。在一个进程中的多个线程之间可以并发执行，甚至允许在一个进程中的所有线程都能并发执行；同样，不同进程中的线程也能并发执行。(4)共享进程资源。在同一进程中的各个线程都可以共享该进程所拥有的资源，这首先表现在所有线程都具有相同的地址空间(进程的地址空间)。这意味着线程可以访问该地址空间中的每一个虚地址；此外，还可以访问进程所拥有的已打开文件、定时器、信号量机构等。4 4线程的状态线程的状态(1)状态参数。在OS中的每一个线程都可以利用线程标识符和一组状态参数进行描述。状态参数通常有这样几项：寄存器状态，它包括程序计数器PC和堆栈指针中的内容；堆栈，在堆栈中通常保存有局部变量和返回地址；线程运行状态，用于描述线程正处于何种运行状态；优先级，描述线程执行的优先程度；线程专有存储器，用于保存线程自己的局部变量拷贝；信号屏蔽，即对某些信号加以屏蔽。(2)线程运行状态 线程在运行时也具有下述三种基本状态:执行状态，表示线程正获得处理机而运行；就绪状态，指线程已具备了各种执行条件，一旦获得CPU便可执行的状态；阻塞状态，指线程在执行中因某事件而受阻，处于暂停执行时的状态。5 5线程的创建和终止线程的创建和终止在多线程OS环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人