《《进程管理传》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《进程管理传》PPT课件.ppt（181页珍藏版）》请在三一办公上搜索。
1、2023/8/2,1,2.1 进程的概念2.2 进程控制2.3 进程同步2.4 经典进程的同步问题2.5 管程机制2.6 进程通信2.7 线程,第二章 进程管理,2023/8/2,2,计算机系统中，最宝贵的资源是CPU。为了提高它的利用率，需要引入多道程序设计的概念。当内存储器中同时有多个程序存在时，如果不对人们熟悉的“程序”概念加以扩充，就无法刻画多个程序共同运行时系统呈现出的特征。因此，在本章将给出操作系统中的重要概念：“进程”。它将是在多道程序运行环境下，系统资源分配和独立运行的基本单位。,退出,2023/8/2,3,2.1 进程的概念,2.1.1 程序的顺序执行及其特点 前趋图 程序并
2、发执行及其特征2.1.4 进程的特征与状态2.1.5 进程控制块,2023/8/2,4,2.1.1程序的顺序执行,程序的顺序执行如图在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。一道程序执行完后另一道才能开始。,2023/8/2,5,2.1.1程序的顺序执行,仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。S1:a=x+y;S2:b=a-5;S3:c=b+1;,2023/8/2,6,程序顺序执行的特点,顺序性：一个程序开始执行必须要等到前一个程序已执行完成。绝对不可能出现在
3、一个程序运行过程中，又夹杂进另一个程序执行的现象存在。,2023/8/2,7,程序顺序执行的特点,封闭性：程序一旦开始执行，其计算结果不受外界因素影响。任何时候，位于内存中的程序可以使用系统中的一切资源，不可能有其他程序与之竞争。,2023/8/2,8,程序顺序执行的特点,可再现性：程序的结果与它的执行速度无关（即与时间无关），只要执行环境和初始条件相同，当多次重复执行一个程序时，无论不停的执行还是“走走停停”，一定会得到相同的结果。,2023/8/2,9,前趋图,概念：前趋图是一个有向无循环图。要求每个结点可用于表示一条语句、一个程序段或进程等 结点间的有向边表示在两个结点之间存在的前趋关系
4、-=(Pi,Pj)|Pi必须在Pj开始之前完成用途：表示程序的执行顺序,2023/8/2,10,前趋图,把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。,2023/8/2,11,前趋图,P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9或表示为：P=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,
5、P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着下述的前趋关系：S2S3,S3S2 这种前趋关系是不可能满足的。,对于图 2-2(a)所示的前趋图，存在下述前趋关系：,2023/8/2,12,练习,习题2S1：a:=x+y;S2:b:=z+1;S3:c:=a-b;S4:w:=c+1;,2023/8/2,13,2.1.3程序的并发执行及其特征,所谓程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。,并发与并行概念的区别？
6、Concurrency，parallel,2023/8/2,14,程序并发执行的特征,间断性失去程序的封闭性不可再现性,任何并发执行都是不可再现的吗？,2023/8/2,15,间断性：“执行的顺序性”被打破了。例：从上图中可以看出，时刻6程序A打印完毕，按说应该继续执行，但是CPU已经分配给了程序B，因此程序A只能等到时刻9在程序B请求打印时，才能重新获得CPU。这就是说，在程序A执行过程时，夹杂进了程序B的执行，打破了程序执行的顺序性，内存中多个程序的执行过程被交织在一起。从宏观上看，好几个程序都在运行着（比如，在时间区间412，程序A和程序B都在做着自己的事情；在时间区间1217，程序B和
7、程序C都在做着自己的事情）；而从微观上看，每个时刻CPU只能为一个程序服务，因此运行着的程序都是走走停停。总之，在程序并发执行时，各个程序的执行已经不再可能完全依照自己的执行次序执行了。,2023/8/2,16,封闭性被打破：程序并发执行时，多个程序共享系统中的资源，其状态可有多个程序来改变。因此，某程序在执行时必然受其他程序的影响。如可能有多个程序竞争cpu。,2023/8/2,17,不可再现性：“结果的再现性”被打破了。举例：有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B
8、以不同的速度运行。(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。,2023/8/2,18,2.1.4 进程的特征与状态,为了对并发执行的程序加以描述和控制，人们引入了“进程”。,2023/8/2,19,进程的特征（五个基本特征）,结构特征：进程是由程序段、数据段、进程控制块三部分组成,2023/8/2,20,进程的特征（五个基本特征）,动态性：（最基本特征）进程是程序的一次执行过程。“进程”
9、是一个动态的概念。程序是一组有序指令的集合，在多道程序设计环境下，它不涉及“执行”，因此是一个静态的概念。可以这么来理解，一套电影拷贝相当于一个程序，它可以长期保存；该拷贝在电影院的一次放映，就相当于一个进程。进程有生命周期。进程既然是程序的执行，或者说是“一次运行活动”。因此当系统要完成某一项工作时，它就“创建”一个进程，以便能去执行事先编写好的、完成该工作的那段程序。程序执行完毕，完成了预定的任务后，系统就“撤消”这个进程，收回它所占用的资源。一个进程创建后，系统就感知到它的存在；一个进程撤消后，系统就无法再感知到它。于是，从创建到撤消，这个时间段就是一个进程的“生命期”。进程的存在是暂时
10、的。而程序的存在是永久的。,2023/8/2,21,进程的特征（五个基本特征）,并发性：多个进程可同存于内存中，能在一段时间内同时运行（重要特征，也是os重要特征）。这正是引入进程的目的，而程序（在没有为它创建进程时）的并发执行具有不可再现性，因此程序不能正确的并发执行。,2023/8/2,22,进程的特征（五个基本特征）,独立性：独立运行的基本单位，独立获得资源和调度的基本单位。（目前有些变化）。而因程序（在没有为它创建进程时）不具有PCB，所以它是不可能在多道程序环境下独立运行的。,2023/8/2,23,进程的特征（五个基本特征）,异步性：各进程按各自独立的不可预知的速度向前推进进程与程
11、序的区别动态，静态有生命周期，永久的组成不同不是一一对应的。,2023/8/2,24,进程定义,进程有很多各式各样的定义，如：进程是程序的一次执行进程是一个程序及其数据在处理机上顺序执行时所发生的活动进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。,2023/8/2,25,进程的三种基本状态,进程间由于共同协作和共享资源，导致生命期中的状态不断发生变化。比如一个进程在等待输入/输出的完成，这时它不能继续运行。另一种情形是一个进程是可以运行的，但由于操作系统把处理机分配给了别的进程使用，于是它也只能
12、处于等待。只有当前占有CPU的进程，才真正在处于运行。进程有三种基本状态：就绪、执行、阻塞,2023/8/2,26,进程的三种基本状态,就绪状态（Ready）：存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。这些进程所处的状态为就绪状态。（可有多个进程）执行状态（Running）：正在运行的进程所处的状态为执行状态。（只有一个进程）阻塞状态（Blocked）：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃CPU而处于暂停状态，称该进程处于等待状态、阻塞状态。典型事件：请求I/O，申请缓冲空间等。（可有多个队列）,2023/8/2,27,一个进程的状
13、态，可以随着自身的推进和外界环境的变化而变化，从而使其从一种状态变迁到另一种状态。下图是进程状态变迁图，箭头表示的是状态变迁的方向，旁边标识的文字是引起这种状态变迁的原因。,2023/8/2,28,处于就绪状态与阻塞状态的进程，虽然都“暂时无法运行”，但两者有着本质上的区别。前者已做好了运行的准备，只要获得CPU就可以投入运行；而后者要等待某事件（比如输入/输出）完成后才能继续运行，因此即使此时把CPU分配给它，它也无法运行。,2023/8/2,29,练习,进程与程序的主要区别在于进程是_的，而程序是_的，一个程序可以对应_进程。下列进程状态转换中，绝对不可能发生的状态转换是（），一般不会发生
14、的状态转换是（）A 就绪执行，B 执行就绪 C 就绪阻塞D 阻塞就绪 D 阻塞执行 E 执行阻塞,2023/8/2,30,练习,D 阻塞执行：是可能的，如果一个进程因等待I/O而产生阻塞，在I/O资源释放后，若CPU处于休眠状态，此进程就可以直接从阻塞状态迁移到执行状态。C 就绪阻塞：是不可能的，一个就绪的进程不会遇到其I/O或其它资源的阻塞，只有一个处于执行状态的进程才会阻塞。,2023/8/2,31,练习,分配到必要的资源并获得处理机时的进程状态是_。A、就绪状态 B、执行状态 C、阻塞状态D、撤消状态 当_时，进程从执行状态转变为就绪状态。A、进程被调度程序选中 B、时间片到C、等待某一
15、事件 D、等待的事件发生,2023/8/2,32,练习,下面对进程的描述中，错误的是：A、进程是动态的概念 B、进程执行需要处理机C、进程是有生命周期的 D、进程是指令的集合进程是基本状态有_、_、_。进程的基本特征是_、_、_、_、_。,2023/8/2,33,进程的挂起状态,引入挂起状态主要 原因：用户的需求 父进程的需求 负荷调节的需要操作系统的需求,引入挂起状态后的进程状态转换 执行状态静止就绪 活动就绪静止就绪 活动阻塞静止阻塞静止阻塞静止就绪静止就绪活动就绪静止阻塞活动阻塞,2023/8/2,34,具有挂起状态的进程状态图,调度,时间片用完,I/O完成,I/O完成,2023/8/2
16、,35,练习,正在执行的进程由于其时间片用完被暂停执行，此时进程应从执行状态变为（）状态；处于静止阻塞状态的进程，在进程等待的事件出现后，应变为（）状态；若进程正处于执行状态时，因终端的请求而暂停下来以便研究其运行情况，这时进程应转变为（）状态；若进程已处于阻塞状态，则此时应转变为（）状态。,2023/8/2,36,进程的创建状态,创建状态：创建一个进程一般要通过两个步骤:为一个新进程创建PCB，并填写必要的管理信息；把该进程转入就绪状态并插入就绪状态之中。,引入创建状态,是为了保证进程的调度必须在创建工作完成后进行,以确保对进程控制块操作的完整性。,2023/8/2,37,进程的终止状态,终
17、止状态：终止一个进程一般要通过两个步骤:等待操作系统进行善后处理；将PCB清零，并将PCB空间返还系统。,增加的状态NULL-创建创建-活动就绪创建-静止就绪执行-终止,2023/8/2,38,2.1.5 进程控制块（Process Control Block）,一个进程创建后，需要有自己对应的程序以及该程序运行时所需的数据。但仅有程序和数据还不行，我们知道，进程在其生命期内是走走停停，停停走走的，暂时停下来以后，至少应该要有一个属于它专用的地方，来记录它暂停时的运行现场。否则，它再次被投入运行时，就无法从上次被打断的地方继续运行下去。,2023/8/2,39,因此，为了管理和控制进程，系统在
18、创建每一个进程时，都为其开辟一个专用的存储区，用以随时记录它在系统中的动态特性。而当一个进程被撤消时，系统就收回分配给它的存储区。通常，把这一存储区称为该进程的“进程控制块”PCB（Process Control Block）。,2023/8/2,40,进程控制块（Process Control Block）,为了描述和控制进程的运行，系统为每个进程定义了一个数据结构-进程控制块，它是进程实体的一部分，是操作系统中最重要的记录型数据结构。,2023/8/2,41,进程控制块的作用,进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进
19、程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的,2023/8/2,42,这样，在计算机系统内部，一个进程要由3个部分组成：程序、数据集合以及进程控制块PCB。下图表示了进程3个组成部分的可能关联情形。其中图(a)表示程序和数据集合存放在一个连续存储区的情形；图(b)表示程序和数据集合在不连续存储区的情形；图(c)表示同一个程序运行在不同数据集合上时，形成两个进程的情形。,2023/8/2,43,2023/8/2,44,随操作系统的不同，PCB的格式、大小以及内容也不尽相
20、同。一般地，在PCB中大致应包含4方面的信息。,PCB中的信息,2023/8/2,45,PCB中的信息,进程描述信息：进程标识符(process ID)，用于惟一地标识一个进程。一个进程通常有两种标识符。内部标识符：在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。外部标识符：它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。,2023/8/2,46,PCB中的信息,CPU状态信息（现场）：
21、各种寄存器值 通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。,2023/8/2,47,进程调度信息：（与进程调度与进程对换有关的信息）进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息，它们与所采用的进程调度算法
22、有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。,PCB中的信息,2023/8/2,48,进程控制信息：程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。,PCB中
23、的信息,2023/8/2,49,在多道程序设计环境里，同时会创建多个进程。当计算机系统只有一个CPU时，每次只能让一个进程运行，其他的进程或处于就绪状态，或处于阻塞状态。为了对这些进程进行管理，操作系统要做两件事。（1）把处于相同状态的进程的PCB，通过各自的队列指针链接在一起，形成一个个队列。,PCB表组织方式,2023/8/2,50,（2）为每一个队列设立一个队列头指针，它总是指向排在队列之首的进程的PCB。注：排在队尾的进程的PCB，它的“队列指针”项内容应该为“-1”，或一个特殊的符号，以表示这是该队的队尾PCB。,2023/8/2,51,在单CPU系统，任何时刻系统中都只有一个进程处
24、于执行状态，因此执行队列中只能有一个PCB；系统中所有处于就绪状态的进程的PCB排成一队，称其为“就绪队列”。一般地，就绪队列中会有多个进程的PCB排在里面，它们形成处理机分配的候选对象。如果就绪队列里没有PCB存在，则称该队列为空；所有处于阻塞状态进程的PCB，应该根据阻塞的原因进行排队，每一个都称为一个“阻塞队列”。比如等待磁盘输入/输出进程的PCB排成一个队列，等待打印机输出进程的PCB排成一个队列等。所以，系统中可以有多个阻塞队列，每个阻塞队列中可以有多个进程的PCB，也可以为空。下图是进程各队列的示意图。,2023/8/2,52,2023/8/2,53,从图上可以看出，现在名为PCB
25、1的进程正在CPU上运行，因为它的PCB排在执行队列中。现在就绪队列中有四个进程排在里面，它们分别是PCB2、PCB3、PCB7和PCB6。系统正常运行时，谁的PCB排在队列的前面，谁的PCB排在队列的后面，那是无法预料的。现在进程PCB5和PCB8排在阻塞队列1中，它们被阻塞的原因相同。现在进程PCB10、PCB9和PCB4排在阻塞队列2中，它们被阻塞的原因相同。,2023/8/2,54,PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度,PCB组织方式总结,2023/8/2,55,链接结构
26、,相同状态的进程PCB组成一个链表，不同状态对应多个不同的链表,2023/8/2,56,索引结构,对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址,2023/8/2,57,练习,如果系统中有5个进程，执行的进程最多几个，最少几个；就绪进程最多几个，最少几个；等待进程最多几个，最少几个？进程由_、_、_三部分组成，其中_是进程存在惟一标志。而_部分也可以为其他进程共享。操作系统通过_对进程进行管理。A、JCB B、PCB C、DCT D、CHCT,2023/8/2,58,2.2进程控制,进程控制就是对系统中的所有进程实施管理，进程控制一般用原语来实现。所谓原语是一种
27、特殊的系统功能调用，它可以完成一个特定的功能，其特点是原语执行时不可被中断，既具有“原子性”。,2023/8/2,59,因为：为了对进程进行有效的管理和控制，操作系统要提供若干基本的操作，以便能创建进程、撤消进程、阻塞进程和唤醒进程。这些操作对于操作系统来说是最为基本、最为重要的。为了保证执行时的绝对正确，要求它们以一个整体出现，不可分割。也就是说，一旦启动了它们的程序，就要保证做完，中间不能插入其他程序的执行序列。这就是所谓的原语。,2023/8/2,60,常用的进程控制原语,创建原语终止原语阻塞原语、唤醒原语挂起原语、激活原语,2023/8/2,61,进程的创建,进程图(Process G
28、raph)进程图是用于描述一个进程的家族关系的有向树（子进程，父进程）子进程可以继承父进程所拥有的资源,2023/8/2,62,进程的创建,引起进程创建的事件 用户登录 作业调度 提供服务 应用请求 进程创建的过程 为新进程分配唯一的进程标识符，并从PCB队列中申请一个空闲PCB。为新进程的程序和数据，以及用户栈分配相应的主存空间及其它必要分配资源。初始化PCB中的相应信息，如标识信息、处理器信息、进程控制信息等。如果就绪队列可以接纳新进程，便将新进程加入到就绪队列中。,2023/8/2,63,进程的终止,引起进程终止的事件 正常结束 异常结束 外界干预 进程终止的过程 根据被终止进程的标识符
29、，从PCB集合中检索该进程的PCB，读出进程状态。若该进程处于执行状态，则立即终止该进程的执行。若该进程有子孙进程，还要将其子孙进程终止，并准备重新分配CPU。将该进程所占用的资源回收，归还给其父进程或操作系统。将被终止进程的PCB从所在队列中移出，并撤消该进程的PCB。,2023/8/2,64,进程的阻塞与唤醒,阻塞：当一个进程所期待的某一事件尚未出现时，该进程调用阻塞原语将自己阻塞。进程阻塞是进程的自身的一种主动行为。唤醒：处于阻塞状态的进程是绝不可能叫醒它自己的，它必须由它的合作进程用唤醒原语唤醒它。,2023/8/2,65,进程的阻塞,引起进程阻塞的事件 请求系统服务 启动某种操作 新
30、数据尚未到达 无新工作可做 进程阻塞的过程 立即停止执行该进程。修改PCB中的相关信息。把进程控制块中的运行状态由“执行”状态改为“阻塞”状态，并填入等待的原因，以及进程的各种状态信息。把PCB插入到阻塞队列。根据阻塞队列的组织方式，把阻塞进程的进程控制块插入到阻塞队列中。转调度程序重新调度，运行就绪队列中的其他进程。,2023/8/2,66,进程的唤醒,引起进程唤醒的事件 请求系统服务得到满足 启动某种操作完成 新数据已经到达 有新工作可做 进程唤醒的过程 从阻塞队列中找到该进程。修改该PCB的相关内容。把阻塞状态改为就绪状态，删除等待原因等等。把进程控制块插入到就绪队列。按照就绪队列的组织
31、方式，把被唤醒的进程的PCB插入到就绪队列中。,2023/8/2,67,进程的唤醒,Block原语和wakeup原语是一对作用刚好相反的原语，因此，如果在进程中调用了阻塞原语，则必须在与之相合作的另一进程中或其他相关进程中安排唤醒原语，以能唤醒阻塞进程。,2023/8/2,68,进程的挂起与激活,引起进程挂起的事件（suspend）用户进程请求将自己挂起 父进程请求挂起子进程 进程挂起的过程 检查进程状态：有活动就绪转为静止就绪有活动阻塞转为静止阻塞把该进程的PCB复制到某指定的内存区域若进程正在执行，则转调度程序重新调度，运行就绪队列中的其他进程。,2023/8/2,69,进程的激活(act
32、ive),引起进程激活的事件 父进程或用户进程请求将挂起进程激活 进程激活的过程 将进程调入内存检查进程状态：有静止就绪转为活动就绪有静止阻塞转为活动阻塞在抢占策略中，有可能转调度程序重新调度。,2023/8/2,70,练习,为使进程由活动就绪转变为静止就绪，应用（）原语；为使进程由执行状态转变为阻塞状态，应利用（）原语；为使进程由静止就绪变为活动就绪，应利用（）原语；为使进程从阻塞状态变为就绪状态，应利用（）原语。对进程的管理和控制使用_。A、指令 B、原语 C、信号量 D、信箱,2023/8/2,71,练习,下面所述步骤中，_不是创建进程所必需的。A、由调度程序为进程分配CPUB、建立一个
33、进程控制块C、为进程分配内存D、将进程控制块链入就绪队列,2023/8/2,72,2.3 进程同步,2.3.1 基本概念 2.3.2 信号量机制 2.3.3 信号量机制的应用,2023/8/2,73,基本概念,与时间有关的错误:一飞机订票系统，两个终端，运行T1、T2进程T1:T2:.Read(x);Read(x);if x=1 then if x=1 then x:=x-1;x:=x-1;write(x);write(x);.,2023/8/2,74,并发环境下程序间的制约关系,2023/8/2,75,基本概念,进程同步的主要任务:是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程
34、序的执行具有可再现性,2023/8/2,76,多道程序间有两种制约关系：间接制约：多个操作不能同时执行，如：操作和操作不能在同时执行。（资源共享关系）直接制约：对于进程操作的时间顺序所加的某种限制，如操作应在之前执行。（相互合作关系）,2023/8/2,77,临界资源(critical resource)：一次仅允许一个进程访问的资源。如：进程共享一台打印机，若让它们交替使用则得到的结果肯定不是我们希望的。临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。并发进程对临界资源的访问必须作某种限制，否则就可能出与时间有关的错误，如：联网售票。诸进程之间用互斥的方式，实现对这种资源的共享,
35、2023/8/2,78,互斥关系,互斥互斥就是若干进程竞争进入临界段时，相互之间所形成的排它性关系。对临界段的实现，表现为对互斥关系的实现。当一个进程处于临界段时，其他的进程必须等待，直到临界段中的进程数为零。,临界段的设计原则：（1）每次至多只允许一个进程处于临界段中。（2）对于请求进入临界段的多个进程，在有限时间内只让一个进入。（3）进程只应在临界段中停留有限时间。要实现临界段，就是要寻找某一种手段来实现临界段的三条设计原则。,2023/8/2,79,临界区(critical section)：临界段，在每个进程中访问临界资源的那段程序代码。注意：临界区是对某一临界资源而言的，对于不同临界
36、资源的临界区，它们之间不存在互斥。如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。进入区：临界区前检查临界资源是否被使用的代码段。退出区：临界区后将临界资源恢复未被使用的代码段。剩余区：上述三个区以外的代码区域。,2023/8/2,80,同步机制应遵循的准则,为了禁止两个进程同时进入临界区内,可以采用软件办法或系统提供的同步机构来协调它们的关系。但是，不论用什么办法都要遵循下述准则（评判的标准）:1.空闲让进：无进程处于临界区时应允许一个请求进入临界区的进程立即进入临界区。2.忙则等待：
37、每次至多有一个进程处于临界区3.有限等待:当有若干进程欲进入它的临界区时,应在有限时间内使进程进入临界区。以免限入“死等”状态4.让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程应陷入“忙等”。,2023/8/2,81,1965年，由荷兰学者Dijkstra提出一种卓有成效的进程同步工具已被广泛应用于单处理机和多处理机系统以及计算机网络中。信号量机制由“信号量”和“P，V操作”两部分组成。信号量就是一种特殊变量，它用来表示系统中资源的使用情况，它只能由两个标准原语所访问，分别记作P操作原语，V操作原语，P，V操作是由操作系统提供的可供外部调用的两条原语。,2.3.2 信号量机
38、制,2023/8/2,82,1整型信号量的概念,概念整型信号量就是一个整型变量。信号量的操作：（1）wait(S)：称为P操作，描述为：wait（S）:while s=0 do no_op;当S=0时，一直在检测 S=S-1；（2）signal(S)：称为V操作，描述为：signal（S）S=S+1；缺点：忙等,2023/8/2,83,2记录型信号量：,在整型信号量机制中的P操作，只要是信号量S0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待
39、访问同一临界资源的情况。,2023/8/2,84,2记录型信号量：,为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：,2023/8/2,85,2记录型信号量：,定义如下：type semaphore=record value:integer;（资源数目）L:list of process;（进程链表）end信号量说明：var S semaphore;,2023/8/2,86,P操作,wait(s)s.value=s.value-1;
40、if(s.value 0)block(s.L)该进程状态置为阻塞状态 将该进程的PCB插入相应的阻塞队列末尾;,2023/8/2,87,V操作,signal(s)s.value=s.value+1;if(s.value=0)wakeup(s.L)唤醒相应阻塞队列中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列,2023/8/2,88,说明,对于P操作：S.Value的初值表示系统中某类资源的数目，对它的每次wait操作，意味着进程请求一个单位的该类资源。当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。“让
41、权等待”此时（S.value0）S.value的绝对值表示在该信号量链表中已阻塞进程的数目。,2023/8/2,89,说明,对于V操作：表示执行进程释放一个单位资源，故S.value=S.value+1操作表示资源数目加1。若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。,2023/8/2,90,关于信号量及其P、V操作，有如下几点说明。（1）对于信号量当其值大于“0”时，表示系统中对应可用资源的数目；当其
42、值小于“0”时，其绝对值表示因该类资源而被阻塞的进程的数目；当其值等于“0”时，表示系统中对应资源已经都被占用，并且没有因该类资源而被阻塞的进程（2）P操作和V操作是两个原子操作，它在执行时是不可中断的。也就是说，只要进入了P操作和V操作，这两个动作就必须顺序地做完，中间不能被打断。,2023/8/2,91,（3）从wait（S）的定义可以看出，调用它的进程有两个出路。如果对信号量当前值减1后，信号量值大于等于0，则该进程继续运行下去；否则它就被阻塞，直到有别的进程通过做signal（S）来唤醒它。但是从signal(S)的定义可以看出，调用它的进程的状态不会改变。无论对信号量当前值加1后的结
43、果如何，调用它的进程最终都是继续运行下去。（4）注意，如果一个进程在做P操作后被阻塞，到关于信号量的队列上去排队等待，其含义是将进程的PCB到此队列上排队。,2023/8/2,92,练习,临界区是_。A、一个缓冲区 B、一段共享数据区 C、一段程序 D、一个互斥资源若信号量S的初值为2，当前值为-1，则表示有_等待进程。A、0个 B、1个 C、2个 D、3个,2023/8/2,93,练习,对于记录型信号量，在执行一次wait操作时，信号量的值应当_，当其值为_时，进程应阻塞。在执行signal操作时，信号量的值应当_，当其值为_时，应唤醒阻塞队列中的进程。某一时刻、某一资源的信号量s=0，它表
44、示（）A 该时刻该类资源的可用数目为1 B 该时刻该类资源的可用数目为1C 该时刻等待该类资源的进程数目为1 D 该时刻等待该类资源的进程数目为0,2023/8/2,94,信号量的应用1用信号量解决进程间互斥问题,2023/8/2,95,利用信号量实现互斥,概念：互斥信号量是根据临界资源的类型设置的。有几种类型的临界资源就设置几个互斥信号量。它代表该类临界资源的数量，或表示是否可用，其初值一般为“1”。例题,2023/8/2,96,图：,假定把进程A程序中的临界区记为CSa，假定把进程B程序中的临界区记为CSb，如图(a)所示。所谓“CSa和CSb互斥地执行”，含义是：如果进程A已进入了CSa
45、，那么进程B就只能在其CSb的进入点处等待，不能进入，只有等到进程A退出了CSa，进程B才能进入CSb。同样地，如果进程B已进入了CSb，那么进程A就只能在其CSa的进入点处等待，不能进入。只有等到进程B退出了CSb，进程A才能进入CSa。为了保证做到这一点，设置一个初值为1的信号量S，在进程A和B的进入点处安排关于信号量S的wait操作，在进程A和B的退出点处安排关于信号量S的signal操作。这样，就能够确保CSa和CSb互斥地执行。如图(b)所示。,现在来分析一下为什么这样的安排就能够保证CSa和CSb的互斥执行。在图(b)的情形下，不失其一般性，假定进程A先于进程B做wait(S)。由
46、于S初始时取值为1，做了wait(S)后，S变为0。根据信号量上wait操作的定义，在实施减1后如果S=0，则调用进程继续运行，因此进程A进入了它的临界区。如果这时进程A的时间片到，则调度到进程B运行。当它调用信号量S的wait操作时，由于现在的S=0，于是减1后S=-10。根据信号量上wait操作的定义，在实施减1后如果S0，那么调用进程由运行状态变为阻塞状态，并到与该信号量有关的队列Vq上排队等待，直到其他进程在S上执行signal操作将其释放为止。因此进程B被阻塞（不能进入它的临界区CSb），到关于信号量S的队列Vq上去排队，等候别的进程释放它。可见，这样安排，可以保证只有一个进程进入它
47、的临界区。,2023/8/2,97,解决合作进程的执行次序问题(前趋关系),若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个前趋图来表示进程集合的执行次序。,2023/8/2,98,解决合作进程的执行次序问题(前趋关系),例：,2023/8/2,99,解决合作进程的执行次序问题(前趋关系),例：Var a,b,c,d,e,f,g;semaphore=0,0,0,0,0,0,0;begin parbegin begin S1;signal(a);signal(b);end;begin wait(a);S2;si
48、gnal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);S6;end;parend end,2023/8/2,100,例,如图，试用信号量实现这三个进程的同步。设有两个信号量SB、SC，初值均为Pa：Pb：Pc：wait(SB);wait(SC)signal(SB);signal(SC);,2023/8/2,101,利用PV操作实现同步,用信号量机制实现同步，只要
49、找出进程之间的同步关系，并为每种同步关系设置一信号量，然后再在需要等待某种动作的地方插入P操作，在被等待的动作完成之后插入V操作。,2023/8/2,102,2023/8/2,103,为了保证做到这一点，设置一个初值为0的信号量S，在进程A的X点处（即同步点），安排一个关于信号量S的P操作，在进程B的Y点处安排关于信号量S的V操作。这样，就能够确保进程A在X点处与进程B取得同步了，如图(b)所示。,2023/8/2,104,现在来分析一下，为什么这样的安排就能够保证进程A在X点与进程B取得同步。首先假定在进程B未到达Y点之前，进程A先于进程B到达了X点。由于S初始时取值为0，做了wait（S）
50、后，S变为-1。根据信号量上P操作的定义，在实施减1后如果Vs0，则调用进程由运行状态变为阻塞状态，到与该信号量有关的队列Vq上排队等待，直到其他进程在S上执行V操作将其释放为止。因此进程A被阻塞，到关于信号量S的队列Vq上去排队，等候别的进程释放它。,2023/8/2,105,这时，调度程序调度到进程B运行。当它准备好了信息后，就在信号量S上做V操作。由于现在的S=-1，加1后是S=0，因此，根据信号量上V操作的定义，在实施加1后如果S=0，则先从与该信号量有关的队列Vq上摘下一个等待进程，让它从阻塞状态变为就绪状态，到就绪队列中排队，然后调用进程继续运行。现在，在队列Vq上等待的正是进程A
