操作系统教学02.pptx

进程的基本概念 进程控制 进程同步 经典进程的同步问题 进程通信 线程 第二章 进程管理第1页/共255页l 人类的擅长逻辑程序（代码、数据）l 计算机的擅长数字运算（指令、逻辑关系）l OS负责将逻辑程序转换为CPU动作,进程是这一转换过程的中间结构2.1 进程的基本概念程序和数据进程结构指令流第2页/共255页程序的顺序执行：仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。2.1.1 程序的顺序执行及其特征第3页/共255页程序顺序执行时的特征顺序性封闭性 可再现性2.1.1 程序的顺序执行及其特征第4页/共255页前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“”。=(Pi,Pj)|Pi must complete before Pj may start,如果(Pi,Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。2.1.2 前趋图第5页/共255页P=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)第6页/共255页程序的并发执行2.1.3 程序的并发执行及其特征在该例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1在Pi-1和Ci以及Ii+1之间，可以并发执行多个程序同时在系统中运行，这些程序的执行在时间上是重叠的，即前一程序的执行尚未结束，后一程序的执行已经开始。第7页/共255页程序的并发执行2.1.3 程序的并发执行及其特征第8页/共255页间断性相互制约将导致并发程序具有“执行暂停执行”这种间断性的活动规律。失去封闭性某程序执行时，必然受到参与并发执行的其它程序的影响不可再现性计算结果与并发程序执行速度有关。即同一程序，使用相同输入、在相同环境下运行，却可能获得完全不同的结果。程序并发执行时的特征第9页/共255页不可再现性的例子：l两个并发执行的程序A和B，如下所示：A：N:=N+1；B：print（N）；N:=0；l 分析：1）并发：A、B交替占用CPU执行；2）异步性导致：CPU交替执行A、B的语句时顺序可能不同！l 设某次循环前，N的值为8,CPU执行顺序 打印结果 N的值1)N:=N+1;print(N);N:=0;9 02)print(N);N:=0;N:=N+1;8 13)print(N);N:=N+1;N:=0;8 0第10页/共255页多道程序环境下，程序的执行属于并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征因此，通常的程序不能参加并发执行为此，引入“进程”第11页/共255页为什么要有进程？为什么要有进程？第12页/共255页引入进程后第13页/共255页引入进程引入进程第14页/共255页进程是一个具有一定独立功能的程序关于某个数据集合的一次可以并发执行的运行活动。计算机中的所有程序（软件），按照某种顺序运行，这种运行的过程称之为进程。进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。2.1.4 进程的特征与状态多道程序环境下，如何能使程序并发执行？如何对并发执行的程序加以控制和描述？第15页/共255页l进程和程序的区别很微妙l想象一位好厨艺的科学家正在为女儿烘制生日蛋糕。有食谱，有原料：面粉、鸡蛋、糖、香草汁等等。在这个比喻中，食谱就是程序(即用适当形式描述的算法)，科学家就是处理机(CPU)，各种原料就是输入数据。进程就是厨师阅读食谱、取来各种原料、以及烘制蛋糕的一系列动作的总和。第16页/共255页l现在假设科学家的儿子哭着跑了进来，说他被一只蜜蜂螫了。科学家就记录下他照着食谱做到哪儿了(保存进程的当前状态)，然后拿出一本急救手册，按照其中的指示处理螫伤。l这里，我们看到处理机从一个进程(做蛋糕)切换到另一个高优先级的进程(实施医疗救治)，每个(进程)拥有各自的程序(食谱和急救书)。当蜜蜂螫伤处理完之后，科学家又回来做蛋糕，从他离开时的那一步继续做下去。l关键思想是：一个进程是某种类型的一个活动，它有程序、输入、输出、及状态。单个处理机被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。第17页/共255页进程基本概念进程基本概念阅读菜谱阅读菜谱准备原料准备原料烹制菜肴烹制菜肴饭菜饭菜阅读洗衣机手册阅读洗衣机手册准备衣服、洗衣粉准备衣服、洗衣粉设定参数，洗衣服设定参数，洗衣服干净衣服干净衣服程序程序输入输入运行运行输出输出程序程序输入输入运行运行输出输出分时切换分时切换洗衣进程洗衣进程洗衣进程洗衣进程做饭进程做饭进程做饭进程做饭进程第18页/共255页l 进程的核心思想进程是某个程序在某个数据集合上的运行过程，它有程序、输入、输出和状态。在分时操作系统中，单个CPU被若干进程共享，它使用某种调度算法决定何时停止一个进程的运行，转而为其他进程提供服务。第19页/共255页操作系统维护一个程序计数器，在进程间切换操作系统维护一个程序计数器，在进程间切换对每一个进程而言，都有独立的计数器和对每一个进程而言，都有独立的计数器和CPUCPU时间时间操作系统实现分时，任意时刻只有一个进程运行操作系统实现分时，任意时刻只有一个进程运行第20页/共255页进程是程序的执行，属于动态，程序是静态的进程的存在是暂时的，程序的存在是永久的进程程序数据PCB(进程控制块，process control block)，即进程是一个程序及其数据在处理机上顺序地执行时所发生的活动。一个程序可以对应多个进程一个进程可以包含多个程序进程同程序的差别第21页/共255页一个程序对应两个进程第22页/共255页一个进程包括多个程序第23页/共255页结构特征 程序段、相关数据段和PCB（进程控制块）进程实体动态性 由创建而产生，由调度而执行，由撤销而消亡 并发性 进程的重要特征，操作系统的重要特征独立性独立运行、独立分配资源、独立接受调度 异步性 按各自独立、不可预知的速度向前推进进程的特征第24页/共255页进程执行时的间断性，决定了进程可能具有多种状态。运行态：正在占用CPU运行程序阻塞态：等待外部事件发生，无法占用CPU就绪态：可运行，但其他进程正在占用CPU进程的三种基本状态第25页/共255页运行态运行态阻塞态阻塞态就绪态就绪态进程就绪，可以运行状态转换：进程等待外部事件，阻塞OS决定由哪个进程占用CPU，进程调度？第26页/共255页l运行态变为就绪态l 强制终止某进程的运行（系统原因）l运行态变为阻塞态l 运行进程等待外部事件发生（自身原因）l阻塞态变为就绪态l 外部事件已经发生，可准备运行l就绪态变为运行态l 停止其他进程运行后，运行该进程占用CPU第27页/共255页l问题1：为什么不能从阻塞态变为运行态呢？l问题2：为什么不能从就绪态变为阻塞态呢？l答案：l三种状态的变换体现了OS的资源管理作用l进程的核心思想在于运行CPU资源的分配第28页/共255页新（New）状态：是一个进程刚刚建立，但还未将它送入就绪队列时的状态。终止（Terminated）状态：一个进程已经正常结束或异常结束，OS已将它从就绪队列中移出，但尚未将它撤消时的状态。挂起状态（暂停执行或不接受调度）终端用户的请求 父进程请求 负荷调节的需要（实时系统）操作系统的需要进程的复杂状态第29页/共255页是一个进程刚刚建立，但还未将它送入就绪队列时的状态一个进程已经正常结束或异常结束，OS已将它从就绪队列中移出，但尚未将它撤消第30页/共255页活动活动挂起挂起事件事件发生发生事件事件发生发生等待等待事件事件挂起挂起调度调度超时超时释放释放活动活动挂起挂起第31页/共255页 请在并发运行示意图中标识程序A、B的状态课堂讨论第32页/共255页l 重要的术语 Cocurrency&Parallel&MultiProgramming Program&Process&Thread Running&Ready&Block&Suspend Dispatch&Activate&Suspend&Wakel 重要的思想 程序与进程：静态和动态的思想 多道程序：并发与互斥的思想 进程管理：杂七杂八好烦哪？第33页/共255页l为描述和控制进程的运行，系统为每个进程定义了一个数据结构进程控制块。lPCB（Process Control Block），是进程实体的一部分，记录了操作系统所需的、用于描述进程当前状况以及控制进程运行的全部信息。lOS是根据PCB来对并发执行的进程进行控制和管理的。l进程控制块是进程存在的惟一标志。当系统创建一个进程时，必须为它设置一个 PCB，然后根据PCB的信息对进程实施控制管理，进程任务完成时，系统收回它的PCB，进程也随之消亡。2.1.5 进程控制块第34页/共255页l进程标识信息：PID,PPIDl用于惟一地标识一个进程。一个进程通常有两种标识符：1）内部标识符，数字标识符；2）外部标识符，它由创建者提供，描述进程的家族关系。l处理器状态信息：PC,PSW,堆栈指针、寄存器l进程调度信息：与进程调度和进程对换有关的信息，包括：进程状态、进程优先级、进程调度所需的其它信息、事件l进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针进程控制块中的信息第35页/共255页第36页/共255页思考：PCB是进程存在的唯一标志 为什么？因因为为PCB PCB 1 1、包包含含了了进进程程的的描描述述信信息息和和控控制制信信息息，2 2、是是进进程程的的动动态态特特征征的的集集中中反反映映，3 3、系系统统根根据据PCBPCB而而感感知知某某一一进进程程的的存存在在，所所以以PCBPCB是是进进程程存存在在的的唯唯一一标标志志。(只只有有在在多多任任务务即即多多道道批处理系统中，才可能建立批处理系统中，才可能建立PCBPCB结构，该系统才具有进程活动结构，该系统才具有进程活动)第37页/共255页进程控制块的组织方式链接方式系统中可能拥有数十个、数百个乃至数千个PCB，如何组织？第38页/共255页进程控制块的组织方式索引方式第39页/共255页进程的基本概念 进程控制 进程同步 经典进程的同步问题 进程通信 线程 第二章 进程管理第40页/共255页进程控制是指：进程的创建、撤消，进程状态转换的控制进程控制由进程控制原语、系统调用实现的进程控制第41页/共255页为了对进程控制，系统中必须设置一个机构，它具有创建撤消以及进程通讯和资源管理等功能，这样结构称为OS的内核(kernel)。内核本身并非一个进程，而是硬件的首次延伸，即它是加到硬件上的第一层软件。内核是通过执行各种原语操作来实现各种控制和管理功能的。第42页/共255页原语是机器指令的延伸，是用若干条机器指令构成的，用以完成特定功能的一段程序。为保证操作的正确性，原语在执行期间是不可分割的。(1)(1)创建进程原语创建进程原语 (2)(2)撤消进程原语撤消进程原语 (3)(3)挂起进程原语挂起进程原语 (4)(4)解挂进程原语解挂进程原语(5)(5)阻塞进程原语阻塞进程原语(6)(6)唤醒进程原语唤醒进程原语(7)(7)调度进程运行原语调度进程运行原语(8)(8)改变优先级原语改变优先级原语第43页/共255页2.2.1 进程的创建l进程图(Process Graph)：描述一个进程家族关系的有向树。l结点表示进程l有向边表示进程之间的父子关系l根表示进程家族的祖先l子进程可以继承父进程所拥有的资源第44页/共255页引起创建进程的事件(1)用户登录（分时系统）(2)作业调度（批处理系统）(3)提供服务（打印进程）(4)应用请求 系统内核创建进程系统内核创建进程应用程序创建进程应用程序创建进程第45页/共255页进程的创建步骤(Creation of Process)调用进程创建原语Create（）(1)申请空白PCB (2)为新进程分配资源（内存等）(3)初始化进程控制块 (4)将新进程插入就绪队列 第46页/共255页程程序序中中的的第第1 1语语句句是是调调用用查查找找进进程程名名过过程程“Get Get Internal Internal Name Name”，参参数数为为进进程程外外部部名名n n。该该过过程程查查找找PCBPCB集集合合，如如已已有有此此同同样样外外部部名名进进程程则则返返回回出出错错消消息息，否否则则返返回回一一个个空空闲闲的的PCBPCB内部标识号内部标识号i i。第第2 2语语句句是是把把进进程程外外部部名名n n登登记记到到第第i i个个PCBPCB的的相相应应外外部部名名表表目目中。中。语句语句3 3是往是往PCBPCB中登记优先数。中登记优先数。语语句句4 4登登记记现现场场状状态态初初始始值值 S0S0到到 相相 应应 的的 现现 场场 保保 留留 区区 中中 或或CpustateCpustate中。中。procedure Create(n,Sprocedure Create(n,S0 0,k,k0 0,M,M0 0,R,R0 0)beginbegin/请求分配请求分配PCBPCB空间空间 i:=Get Internal Name(n);i:=Get Internal Name(n);/初始化初始化PCB PCB Id(i):=n;Id(i):=n;Priority(i):=kPriority(i):=k0 0;Cpustate(i):=SCpustate(i):=S0 0;Main Store(i):=MMain Store(i):=M0 0;Resources(i):=RResources(i):=R0 0;Status(i):=Status(i):=ReadysReadys Parent(i):=CALLERParent(i):=CALLER/插入就绪队列插入就绪队列Insert(RL,i);Insert(RL,i);endend建立进程原语的工作大致描述为：第47页/共255页 ，分分别别记记入入主主存存和和资资源源的的初初始始占占有有情情况况，这这是是由由父父进进程程将将自自己己的的一一部部分分资资源源分分给给子子进进程的。程的。是是把把进进程程初初始始状状态态置置为为“挂起就绪挂起就绪”。语语句句 中中CALLERCALLER代代表表调调用用本本过过程程的的父父进进程程之之内内部部标标识识号号，将将它它记记入入子子进进程程PCBPCB的的父父进进程程名名这这一一栏。栏。语语句句也也是是调调用用插插入入过过程程InsertInsert，其其中中RLRL表表示示就就绪绪队队列列，即即把把进程进程i i插入就绪队列。插入就绪队列。procedure Create(n,Sprocedure Create(n,S0 0,k,k0 0,M,M0 0,R,R0 0)beginbegin/请求分配请求分配PCBPCB空间空间 i:=Get Internal Name(n);i:=Get Internal Name(n);/初始化初始化PCB PCB Id(i):=n;Id(i):=n;Priority(i):=kPriority(i):=k0 0;Cpustate(i):=SCpustate(i):=S0 0;Main Store(i):=MMain Store(i):=M0 0;Resources(i):=RResources(i):=R0 0;Status(i):=Status(i):=ReadysReadys Parent(i):=CALLERParent(i):=CALLER/插入就绪队列插入就绪队列Insert(RL,i);Insert(RL,i);endend第48页/共255页引起进程终止(Termination of Process)的事件l 正常结束l 异常结束l 越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障l 外界干预l操作员或操作系统干预（如死锁）、父进程请求、父进程中止 2.2.2 进程的终止第49页/共255页进程的终止过程l 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态l 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度l 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程l 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统l 将被终止进程(它的PCB)从所在队列(或链表)中移出第50页/共255页l引起进程阻塞与唤醒的事件l请求系统服务 l启动某种操作 l新数据尚未到达 l无新工作可做 2.2.3 进程的阻塞与唤醒第51页/共255页 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。1.立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞；2.将PCB插入阻塞队列；3.转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。进程的阻塞过程第52页/共255页 当被阻塞进程所期待的事件出现时，则由有关进程调用唤醒原语wakeup()，将等待该事件的进程唤醒。1、把被阻塞的进程从阻塞队列中移出2、将其PCB中的现行状态由阻塞改为就绪3、然后再将该PCB插入到就绪队列中进程的唤醒过程第53页/共255页 当出现了引起进程挂起的事件时，系统将利用挂起原语suspend()将指定进程挂起。1.检查被挂起进程的状态，活动就绪改为静止就绪；活动阻塞改为静止阻塞。2.把该进程的PCB复制到指定内存区域。3.若被挂起的进程正在执行，则转向调度程序重新调度。2.2.4 进程的挂起与激活进程的挂起第54页/共255页当发生激活进程的事件时，系统将利用激活原语active()将指定进程激活。1.将进程从外存调入内存，检查其现行状态，静止就绪改为活动就绪；静止阻塞改为活动阻塞。2.假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度。2.2.4 进程的挂起与激活进程的激活第55页/共255页进程控制原语与进程状态转换的对应第56页/共255页UNIX系统实例：1-进程家族树1、系统初启后，由系统核心程序建立init进程。init进程读取文件/etc/ttys，该文件告诉系统共有几个终端并提供每个终端的说明。init进程将为每个终端生成一个子进程，然后将自己阻塞直到所有子进程结束。2、每个子进程等待用户登记（login）使用系统，接着执行shell命令解释程序。3、图例系统中有三个终端。运行在终端0上的子进程仍在等待用户登录；在终端1上的子进程已成功登录了用户，正运行shell等待命令输入；在终端2上的子进程也成功登录了用户，该用户正运行cp程序，cp是shell的子进程，shell 则等待该进程结束。cp结束后，shell再接收输入，创建新进程执行新输入命令。第57页/共255页UNIX系统实例：2-相关系统调用1.fork系统调用：功能：建立子进程返回值：fork对子进程返回0，对父进程返回子进程的标识符。具体描述：子进程是父进程的一个副本，这就允许父进程可以很容易地与子进程通信。父子进程都从fork后的那条指令继续执行。2.exec系统调用：输入参数：新程序名，功能：以指定程序覆盖当前进程的程序代码。3.wait系统调用：输入参数：进程号功能：等待指定进程结束。第58页/共255页UNIX系统实例：3-shell的内部部分代码显示命令提示符等待用户输入命令行对命令行分析和解释，得到要运行的程序（例如cp）及其运行参数if(pid=fork()0)/*父进程代码，典型地如：*/wait(pid);/*等待该子进程结束*/显示下一个命令提示符else/*子进程代码，典型地如：*/exec(cp,L);第59页/共255页进程的基本概念 进程控制 进程同步 经典进程的同步问题 进程通信 线程 第二章 进程管理第60页/共255页l并发执行的诸进程：既有独立性又有制约性。独立性是指各进程都可独立地向前推进；制约性是指由于资源共享和进程合作所引起的进程之间的相互依赖和相互制约的关系。2.3 进程的同步进程同步进程同步的主要任务，是使并发执行的诸进程之间的主要任务，是使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行能有效的共享资源和相互合作，从而使程序的执行具有可再现性。具有可再现性。第61页/共255页u 进程并行运行时相互制约(进程发消息限制另一进程运行)，而制约关系归结为互斥和同步u 同步指两个事件的发生有着某种时序上的关系(先，后)u 互斥资源的使用要排它使用，防止竞争冲突(不同时使用，但无先后次序)(作为一种特殊同步)2.3.1 进程同步的基本概念第62页/共255页SpoolerSpooler目录问题（互斥）目录问题（互斥）Out：4In：7进程进程A：N_f_s=In;/In=7InsertFileIntoSpooler(N_f_s);In=N_f_s+;/In=8进程进程B B：N_f_s=In;=In;/In=8/In=8InsertFileIntoSpooler(N_f_s);InsertFileIntoSpooler(N_f_s);In=N_f_s+;In=N_f_s+;/In=9/In=94：File15：File26：File37：Null8：NullSpooler目录目录进程切换，一切正常进程切换，一切正常第63页/共255页SpoolerSpooler目录问题（互斥）目录问题（互斥）Out：4In：7进程进程A：N_f_s=In;/In=7进程进程B：N_f_s=In;/In=7InsertFileIntoSpooler(N_f_s);In=N_f_s+;/In=84：File15：File26：File37：Null8：NullSpooler目录目录进程切换进程切换进程进程A：InsertFileIntoSpooler(N_f_s);In=N_f_s+;/In=8进程切换，进程进程切换，进程B数据丢失数据丢失第64页/共255页同步问题举例（同步问题举例（1 1）l Get、Copy、Put为三个并发的程序l F、G为保存多条数据的缓冲区，S、T为临时缓冲区l 三个程序顺序执行，可将F的值经过S、T保存到G中l 正常情况下，不存在任何问题，但是程序运行顺序发生变化时，结果可能出错第65页/共255页同步问题举例（2）初始状态FSTG分析程序运行顺序3，4，5221，2G、C、P4，5331，2，3正确G、P、C4，5331，2，2错误C、P、G4，5321，2，2错误C、G、P4，5321，2，2错误P、C、GP、G、C第66页/共255页“司机售票员司机售票员”问题（同步）问题（同步）问题分析两个独立进程如何保持同步？现实应用中存在大量的类似实例司机进程While(True)启动公车；驾驶公车；停止公车；售票员进程While(True)关车门；卖车票；开车门；正确运行过程While(True)（司机）启动公车；（售票员）关车门；（司机）驾驶公车；（售票员）卖车票（司机）停止公车；（售票员）开车门；第67页/共255页引入一个重要的概念临界资源。只能排它使用的资源称为临界资源。一次仅允许一个进程使用的资源。第68页/共255页例：二人合作存款例：二人合作存款cobeginPA:N:=count N:=N+100 count:=N;PB:M:=count M:=M+200由由 count:=Mcoendcs1cs2cs1cs2countcs临界区临界区临界资源临界资源执行速度的不同，导致结果不唯一。count是一个互斥性使用的变量(有排它性)。第69页/共255页生产者-消费者问题第70页/共255页由于生产者和消费者并发运行，且共享变量counter counter，造成：第71页/共255页结论：counter是临界资源，生产者和消费者应互斥访问。即：虽然生产者、消费者并发执行，但在执行counter的加1、减1的语句时，只能顺序进行。即：只能按可能性中A或B的顺序进行，绝不能交替进行。临界资源实例：打印机、磁带机、只能排它使用的变量、表格、队列。非临界资源：磁盘。临界区(段)将访问临界资源的那段程序从概念上分离出来称为临界区。(对临界区的访问必须是互斥的)第72页/共255页可把一个访问临界资源的循环进程描述如下：repeat 进入区进入区 critical section;临界区临界区 退出区退出区 remainder section;剩余区剩余区 until false;第73页/共255页怎么才能保证诸进程间互斥地执行临界区(段)以访问共享变量呢？(即解决了临界区对临界资源的访问，就解决了互斥问题)可用软件方法，更多设置同步机构同步机制应遵循的原则：有空让进、忙则等待、有限等待、让权等待第74页/共255页u Diskstra于1965年提出临界段设计原则：u 每次至多只允许一个进程处于临界段之中u 如果有多个进程同时要求进入临界区，应在有限时间内使其中之一进入u 进程只能在临界区中逗留有限时间第75页/共255页假如有两个进程Pi和Pj，它们共享一个临界资源R。如何用软件方法使进程Pi和Pj能互斥地访问资源R呢？程序上如何实现互斥使用临界资源第76页/共255页利用软件解决进程互斥问题算法算法算法算法1 1 1 1 设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号，若turn=i，表示允许Pi进程进入临界区。该算法可确保每次只允许一个进入临界区 Pj进程:repeat while turnj do no op Critical section turn=iRemain Section until falsePi进程:repeat while turni do no op Critical section turn=jRemain Section until false但采用强制两个进程轮流进入临界区，很容易造成资源利用不充分。缺点：强制两进程轮流进入临界区；不能保证“空闲让进”第77页/共255页利用软件解决进程互斥问题算法算法算法算法2 2 2 2l在每一个进程访问临界区资源之前，先动查看一下临界资源是否正被访问，若正被访问，该进程需等待，否则才进入自己的临界区。设置了一个数组 flag，如第i个元素值为false表示Pi进程未进入临界区，值为true表示Pi进程进入临界区。Pi:repeat while flagj do no_op;flagi:=true;critical_section;flagi:=false;remainder section;until false Pj:repeat while flagi do no_op;flagj:=true;critical_section;flagj:=false;remainder section;until false 缺点：会出现Pi和Pj同时进入临界区错误。先检测对方进程状态标志后再置自己标志，由于在检测和放置中可插入另一个进程时检测操作，会造成二个进程在分别检测后同时进入临界区。解决了“空闲让进”，但又违背了“忙则等待”第78页/共255页利用软件解决进程互斥问题算法算法算法算法3 3 3 3算法2是先检测对方进程状态标志后再置自己标志，由于在检测和放置中可插入另一个进程时检测操作，会造成二个进程在分别检测后同时进入临界区。为此算法3采用先设置自己标志后再检测对方状态标志，它的程序如下。Pj:repeat flagj:=true;while flagi do no_op;critical_section;flagj:=false;remainder section;until falsePi:repeat flagi:=true;while flagj do no_op;critical_section;flagi:=false;remainder section;until false缺点：可能出现二个进程先后同时设置后再分别检测对方状态标志，造成对缺点：可能出现二个进程先后同时设置后再分别检测对方状态标志，造成对方都不能进入临界区，无限期等待。解决了方都不能进入临界区，无限期等待。解决了“忙则等待忙则等待”，但又违背了，但又违背了“空空闲让进闲让进”和和“有限等待有限等待”第79页/共255页利用软件解决进程互斥问题算法算法算法算法4 4 4 4说明：说明：Flagi=true PiFlagi=true Pi要进或正进要进或正进turn=jturn=j应轮到应轮到PjPjPi第80页/共255页l组合了算法组合了算法1 1和算法和算法3 3，既实现了，既实现了“空闲让进空闲让进”，又保证了，又保证了“忙则等待忙则等待”l为了防止二进程进入临界区而无限期等待，又为了防止二进程进入临界区而无限期等待，又设置变量设置变量turnturn，表示不允许进入临界区的编号，表示不允许进入临界区的编号，每个进程在先设置自己标，每个进程在先设置自己标志后再设置志后再设置turnturn标志，不允许另一个进程进入，这时再同时标志，不允许另一个进程进入，这时再同时检测另一个进程状态标志和不允许进入标志，这样可以保证检测另一个进程状态标志和不允许进入标志，这样可以保证当二个进程同时要求进入临界区时，只允许一个进程进入临当二个进程同时要求进入临界区时，只允许一个进程进入临界区。界区。l缺点：四种算法全部属于缺点：四种算法全部属于“忙等待忙等待”方式，现在已很少使用。方式，现在已很少使用。第81页/共255页由于中断的原因，使得一个进程在对一个公用变量先取来并检测其值，然后修改的这两个动作中，可以插入其它进程对此公用变量的访问和修改，从而破坏了此公用变量数据的完整性和正确性。许多大型机（如IBM370等）和微型机（如Intel 86等）中都提供了专用的硬件指令，这些指令全部允许对一个字中的内容进行检测和修正，或交换两个字的内容。这些操作都是在一个存储周期中完成，或者说由一条指令来完成，不可能有中断，用这些指令就可以解决临界区问题。利用硬件解决进程互斥问题第82页/共255页为了解决同类临界区互斥问题，可以为每类临界区设置一把锁。在程序中锁可以用一个变量lock来表示，锁有两种状态：false 打开状态，资源空闲，可以进入临界区。true关闭状态，资源被占用，不可进入临界区。显然，为解决同类临界区互斥问题，只要在每个进程进入临界区前，执行关锁操作，以阻止别的进程进入临界区，退出临界区后，要执行开锁操作，好让别的进程进入临界区。第83页/共255页开锁操作：lock false，任何机器一条指令可以实现。关锁操作：共有3步 （1）测试lock的值是false，才可关锁。（2）lock true （3）原lock值为true时，返回。等待别的进程释放资源后开锁。前两步应作为一个整体来执行，不可分开，这样才能保证在前两步之间，lock不被别的进程改变。这一点在许多机器中都提供了专门的硬件指令来实现。不同的机器，指令略有不同，但基本功能是相同的，例如在IBM370系列机中的TS指令（test and set），和在Intel 8086中的XCHG（交换指令）。第84页/共255页检测和设置（TS）的功能可用PASCAL语言描述如下：function TS(var lock：boolean):boolean；begin TS:=lock;Lock:=true;EndC+语言描述如下:bool TS(bool&lock)if(lock=true)return true;elselock=true;return false;第85页/共255页l程序中的第一条语句用于检查TS指令执行后的TS状态。若为false表示资源空闲，进程可进入临界区；否则，不断测试执行TS指令后的TS变量值，直至其为false。l当进程退出临界区时，设置变量lock为false，以允许其它进程进入临界区。l 可为每个临界资源设置一个可为每个临界资源设置一个布尔变量布尔变量1ock1ock，并赋予其初值，并赋予其初值为为falsefalse，以表示资源空闲。，以表示资源空闲。利用利用TSTS指令实现互斥的循环进指令实现互斥的循环进程可描述为：程可描述为：利用利用TSTS实现进程互斥实现进程互斥第86页/共255页l 在利用Swap实现进程互斥时，可为临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中再利用一个局部布尔变量key。利用Swap指令实现进程互斥的循环进程可描述为：利用交换指令利用交换指令SwapSwap实现进程互斥实现进程互斥第87页/共255页锁方法缺点：l“忙等”，违背了“让权等待”原则l 某种临界资源只能一个进程使用l 很难用它解决复杂的同步问题第88页/共255页信号量机制是荷兰计算机科学家Dijkstra于1965年提出的一种卓有成效的进程同步工具。引入新的数据结构定义：信号量利用信号量，提供更为复杂的原语级操作从根本上解决“潜在竞争条件”问题可以方便的推广到一般情况，适用于多进程的互斥与同步2.3.2 信号量机制第89页/共255页最初Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation)wait(S)和signal(S)来访问，这两个操作一直被分别称为P、V操作。信号量机制整型信号量wait(S):while S0 do no-op S=S-1;signal(S):S=S+1;Wait操作，只要信号量S 0，就会不断测试，忙等，违背让权等待。第90页/共255页思考题：设有两个优先级相同的进程思考题：设有两个优先级相同的进程P1P1、P2P2如下。令信号量如下。令信号量S1S1、S2S2的初值为的初值为0 0，已知，已知z=2z=2，试问，试问P1P1、P2P2并发运行后并发运行后x=?y=?z=?(x=?y=?z=?(北航北航2001)2001)进程P1 P1 进程P2 P2 y:=1;x:=1;y:=y+2;x:=x+1;V(S1);P(S1);z:=y+1;x:=x+y;P(S2);V(S2);y:=z+y;z:=z+x;第91页/共255页l y:=z+y在z:=z+x之前 x=5,y=12,z=9l y:=z+y在z:=z+x之后 x=5,y=7,z=9结果第92页/共255页记录型信号量机制，是一种不存在“忙等”现象的进程同步机制，实现了“让权等待”的策略。会出现多个进程等待访问同一临界资源问题。除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量第93页/共255页信号量机制记录型信号量数据结构数据结构type semaphore=record value:integer;L:list of process;endprocedure wait(S)var S:semaphore;begin S.value:=S.value-1;if S.value0 then block(S,L)endprocedure signal(S)var S:semaphore;begin