操作系统第2章进程管理讲义课件

Operating SystemOperating System6/22/20241Operating SystemOperating System第二章第二章第二章第二章 进程管理进程管理进程管理进程管理q重点重点v理解理解进程进程的含义的含义v理解和掌握同步的概念及经典理解和掌握同步的概念及经典进程同步进程同步问题问题，是本课程的重点之一是本课程的重点之一q难点难点v会写会写进程同步进程同步问题的算法问题的算法q知识点知识点v进程、线程、进程的特征、进程、线程、进程的特征、PCB、进程控制、进程控制、进程状态转换、进程状态转换、进程同步、进程通信进程同步、进程通信6/22/20242Operating SystemOperating System第二章第二章第二章第二章 进程管理进程管理进程管理进程管理q进程的基本概念进程的基本概念 q进程控制进程控制 q进程同步进程同步 q经典进程的同步问题经典进程的同步问题 q管程机制管程机制 q进程通信进程通信 q线程线程 6/22/20243Operating SystemOperating System进程的基本概念进程的基本概念进程的基本概念进程的基本概念q程序的顺序执行及其特征程序的顺序执行及其特征q前趋图前趋图q程序的并发执行及其特征程序的并发执行及其特征q进程的特征与状态进程的特征与状态q进程控制块进程控制块6/22/20244Operating SystemOperating System程序的顺序执行及其特征程序的顺序执行及其特征程序的顺序执行及其特征程序的顺序执行及其特征q两种方式两种方式v顺序执行：顺序执行：是是单道单道批处理系统的执行方式，也用于批处理系统的执行方式，也用于简单的单片机简单的单片机系统系统v并发执行：并发执行：现在的操作系统，具有许多新的特征。现在的操作系统，具有许多新的特征。引入并发执行的目的是为了提高引入并发执行的目的是为了提高资源利用率资源利用率q顺序执行的特征顺序执行的特征v顺序性顺序性：按照程序结构所指定的次序（可能有分支：按照程序结构所指定的次序（可能有分支或循环）或循环）v封闭性封闭性：独占全部资源，计算机的状态只由于该程：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定序的控制逻辑所决定v可再现性可再现性：初始条件相同则结果相同。如：可通过：初始条件相同则结果相同。如：可通过空指令控制时间关系空指令控制时间关系6/22/20245Operating SystemOperating System程序的顺序执行及其特征程序的顺序执行及其特征程序的顺序执行及其特征程序的顺序执行及其特征q仅当前一操作仅当前一操作(程序段程序段)执行完后，才能执行后继执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算程序和数据，然后进行计算，最后才能打印计算结果。结果。语句语句s1,s2,s3必须按必须按顺序执行顺序执行 S1:a=x+y;S2:b=a-5;S3:c=b+1;6/22/20246Operating SystemOperating System程序的顺序执行及其特征程序的顺序执行及其特征程序的顺序执行及其特征程序的顺序执行及其特征q IiCiPi和和S1S2S3程序的顺序执行程序的顺序执行(a)程序的顺序执行程序的顺序执行I1C1P1I2C2P2(b)三条语句的顺序执行三条语句的顺序执行S1S2S36/22/20247Operating SystemOperating System进程的基本概念进程的基本概念进程的基本概念进程的基本概念q程序的顺序执行及其特征程序的顺序执行及其特征q前趋图前趋图q程序的并发执行及其特征程序的并发执行及其特征q进程的特征与状态进程的特征与状态q进程控制块进程控制块6/22/20248Operating SystemOperating System前趋图前趋图前趋图前趋图q前趋图前趋图(Precedence Graph)是一个是一个有向无循环有向无循环图，图，记为记为DAG(Directed Acyclic Graph)，用于描述进用于描述进程之间执行的前后关系。图中的每个结点可用于程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系或前趋关系(Precedence Relation)“”q=(Pi,Pj)|Pi must complete before Pj may start,如果如果(Pi,Pj),可写成可写成PiPj，称，称Pi是是Pj的的直接前趋直接前趋，而称，而称Pj是是Pi的的直接后继直接后继。在前趋。在前趋图中，把没有前趋的结点称为图中，把没有前趋的结点称为初始结点初始结点(Initial Node)，把没有后继的结点称为把没有后继的结点称为终止结点终止结点(Final Node)6/22/20249Operating SystemOperating System前趋图前趋图前趋图前趋图q每个结点还具有一个重量每个结点还具有一个重量(Weight,权值权值)，用于用于表示该结点所含有的程序量或结点的执行时间表示该结点所含有的程序量或结点的执行时间P1P3P8P9P4P2P5P6P7(a)具有九个结点的前趋图具有九个结点的前趋图S1S2S3(b)具有循环的前趋图具有循环的前趋图6/22/202410Operating SystemOperating System前趋图前趋图前趋图前趋图q对于图对于图(a)所示的前趋图，所示的前趋图，存在下述前趋关系存在下述前趋关系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,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)应应当当注注意意，前前趋趋图图中中必必须须不不存存在在循循环环，但但在在图图(b)中中却却有有着着下述的前趋关系：下述的前趋关系：S2S3,S3S2 6/22/202411Operating SystemOperating System进程的基本概念进程的基本概念进程的基本概念进程的基本概念q程序的顺序执行及其特征程序的顺序执行及其特征q前趋图前趋图q程序的并发执行及其特征程序的并发执行及其特征q进程的特征与状态进程的特征与状态q进程控制块进程控制块6/22/202412Operating SystemOperating System程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征并发执行时的前趋图并发执行时的前趋图6/22/202413Operating SystemOperating System程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征在该例中存在下述前趋关系：在该例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1而而Ii+1和和Ci及及Pi-1是重迭的，是重迭的，亦即在亦即在Pi-1和和Ci以及以及Ii+1之间，可以并发执行。之间，可以并发执行。6/22/202414Operating SystemOperating System程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征q对于具有下述四条语句的程序段对于具有下述四条语句的程序段v S1:a=x+2v S2:b=y+4v S3:c=a+bv S4:d=c+b S1S2S3S46/22/202415Operating SystemOperating System程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征q例如有两个循环程序例如有两个循环程序A和和B，它们共享一个变量它们共享一个变量Nq程序程序A和和B以不同的速度运行以不同的速度运行(失去封闭性，导致不可再现失去封闭性，导致不可再现性）性）vN=N+1在在Print(N)和和N=0之前，此时得到的之前，此时得到的N值分别为值分别为n+1,n+1,0v N=N+1在在Print(N)和和N=0之后，此时得到的之后，此时得到的N值分别为值分别为n,0,1vN=N+1在在Print(N)和和N=0之间，此时得到的之间，此时得到的N值分别为值分别为n,n+1,0程序程序程序程序A A：N=N+1;程序程序程序程序B B：Print(N);N=0;6/22/202416Operating SystemOperating System程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征NN：n n程序程序程序程序A A：N=N+1;/N=n+1/N=n+1程序程序程序程序B B：Print(N);/N=n+1/N=n+1 N=0;/N=0/N=0程序切换程序切换程序切换程序切换NN：n n程序程序程序程序B B：Print(N);/N=n/N=n N=0;/N=0/N=0程序程序程序程序A A：N=N+1;/N=1/N=1程序切换程序切换程序切换程序切换NN：n n程序程序程序程序B B：Print(N);/N=n/N=n程序切换程序切换程序切换程序切换程序程序程序程序A A：N=N+1;/N=n+1/N=n+1程序切换程序切换程序切换程序切换程序程序程序程序B B：N=0;/N=0/N=0注意：注意：A、B程序得到的共享变程序得到的共享变量结果不同，失去封闭性、不可量结果不同，失去封闭性、不可再现性；要得到良好的控制，系再现性；要得到良好的控制，系统必须要进行管理统必须要进行管理进程控制进程控制管理管理6/22/202417Operating SystemOperating System程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征q并发执行的特征并发执行的特征v间断间断(异步异步)性性v走走停停走走停停，一个程序可能走到中途停下来，失去原，一个程序可能走到中途停下来，失去原有的时序关系；有的时序关系；v失去封闭性失去封闭性v共享资源，受其他程序的控制逻辑的影响。如：一个共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。去原有的不变特征。v失去可再现性失去可再现性v失去封闭性失去封闭性 失去可再现性；外界环境在程序的两失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征次执行期间发生变化，失去原有的可重复特征6/22/202418Operating SystemOperating System程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征程序的并发执行及其特征q并发执行并发执行失去封闭性的原因失去封闭性的原因是共享资源的影响，是共享资源的影响，去掉这种影响就行了。去掉这种影响就行了。1966年，由年，由Bernstein给出给出并发执行的条件并发执行的条件。（这里没有考虑执行速度的影。（这里没有考虑执行速度的影响。）响。）q程程序序 P(i)针针对对共共享享变变量量的的读读集集和和写写集集 R(i)和和W(i)q条件：任意两个程序条件：任意两个程序P(i)和和P(j)，有：有：vR(i)W(j)=;vW(i)R(j)=;vW(i)W(j)=;q前前两两条条保保证证一一个个程程序序的的两两次次读读之之间间数数据据不不变变化化；最后一条保证写的结果不丢掉最后一条保证写的结果不丢掉现在的问题是这个条件不好检查6/22/202419Operating SystemOperating System程序并发执行的条件（程序并发执行的条件（1966年由年由Bernstein提出）提出）若两个程序P1和P2满足下述条件，便能并发执行且有可再现性：R(P1)W(P2)R(P2)W(P1)W(P1)W(P2)=“读集读集读集读集”R(PR(Pi i)为程序 Pi 在执行期间所需参考参考的所有变量的集合。“写集写集写集写集”W(PW(Pi i)为程序 Pi 在执行期间所需改变改变的所有变量的集合。例如：S1:a:=x+y S2:b:=z+1S3:c:=a-bS4:d:=c+16/22/202420Operating SystemOperating System程序并发执行的条件（程序并发执行的条件（1966年由年由Bernstein提出）提出）S1:a:=x+y R(S1)=W(S1)=S2:b:=z+1 R(S2)=W(S2)=S3:c:=a-bR(S3)=W(S3)=S4:d:=c+1 R(S4)=W(S4)=语句S1、S2_并发，因为_。语句S1、S3_并发，因为_。语句S2、S3_并发，因为_。语句S3、S4_并发，因为_。语句S2、S4_并发，因为_。x,yazba,bccd可以R(P1)W(P2)R(P2)W(P1)W(P1)W(P2)=不能R(S3)W(S1)=a 不能不能可以R(S3)W(S2)=b R(S4)W(S3)=c 6/22/202421Operating SystemOperating System进程的基本概念进程的基本概念进程的基本概念进程的基本概念q程序的顺序执行及其特征程序的顺序执行及其特征q前趋图前趋图q程序的并发执行及其特征程序的并发执行及其特征q进程概念进程概念q进程的特征与状态进程的特征与状态q进程控制块进程控制块6/22/202422Operating SystemOperating System进程概念进程概念进程概念进程概念q何谓进程（何谓进程（Process）q如何理解进程概念？如何理解进程概念？进程与程序有何差别？进程与程序有何差别？描述性定义：计算机中的所有程序（软件），按描述性定义：计算机中的所有程序（软件），按照某种顺序运行，这种运行的过程称之为进程。照某种顺序运行，这种运行的过程称之为进程。6/22/202423Operating SystemOperating System进程概念进程概念进程概念进程概念阅读菜谱阅读菜谱准备原料准备原料烹制菜肴烹制菜肴饭菜饭菜阅读洗衣机手册阅读洗衣机手册准备衣服、洗衣粉准备衣服、洗衣粉设定参数，洗衣服设定参数，洗衣服干净衣服干净衣服程序程序输入输入运行运行输出输出程序程序输入输入运行运行输出输出分时切换分时切换洗衣进程洗衣进程洗衣进程洗衣进程做饭进程做饭进程做饭进程做饭进程6/22/202424Operating SystemOperating System进程概念进程概念进程概念进程概念q进程的核心思想进程的核心思想进程是某种类型的一个活动，它有程序、输入、进程是某种类型的一个活动，它有程序、输入、输出和状态。输出和状态。在分时操作系统中，单个在分时操作系统中，单个CPU被若干进程共享，被若干进程共享，它使用某种调度算法决定何时停止一个进程的运它使用某种调度算法决定何时停止一个进程的运行，转而为其他进程提供服务。行，转而为其他进程提供服务。6/22/202425Operating SystemOperating System进程概念进程概念进程概念进程概念q较典型的进程定义有：较典型的进程定义有：v进程是进程是程序程序的的一次执行一次执行v进程是一个程序及其数据在处理机上顺序进程是一个程序及其数据在处理机上顺序执行执行时时所所发生的活动发生的活动v进程是程序在一个数据集合上运行的过程，它进程是程序在一个数据集合上运行的过程，它是系统进行资源是系统进行资源分配和调度分配和调度的一个的一个独立单位独立单位6/22/202426Operating SystemOperating System进程的基本概念进程的基本概念进程的基本概念进程的基本概念q程序的顺序执行及其特征程序的顺序执行及其特征q前趋图前趋图q程序的并发执行及其特征程序的并发执行及其特征q进程概念进程概念q进程的特征与状态进程的特征与状态q进程控制块进程控制块6/22/202427Operating SystemOperating System进程的特征与状态进程的特征与状态进程的特征与状态进程的特征与状态q动态性动态性：进程具有：进程具有动态的地址空间动态的地址空间（数量和内容），（数量和内容），地址空间上包括：地址空间上包括：v代码代码（指令执行和（指令执行和CPU状态的改变）状态的改变）v数据数据（变量的生成和赋值）（变量的生成和赋值）v系统系统控制信息控制信息（进程控制块的建立和系统收回）（进程控制块的建立和系统收回）q独立性独立性：各进程的：各进程的地址空间相互独立地址空间相互独立，除非采用进程，除非采用进程间通信手段；间通信手段；q并发性：并发性：多个多个进程实体进程实体进程实体进程实体同存于内存中，且能在一段时同存于内存中，且能在一段时间内同时运行；引入进程实体的目的就是并发执行间内同时运行；引入进程实体的目的就是并发执行q异步性异步性：各进程按各自独立的、不可预知的速度向前：各进程按各自独立的、不可预知的速度向前推进推进q结构性结构性：程序段、数据段和程序段、数据段和程序段、数据段和程序段、数据段和PCBPCB；程序文件中通常也程序文件中通常也划分了代码段和数据段，进程的创建与撤消就是划分了代码段和数据段，进程的创建与撤消就是PCB的创建与撤消的创建与撤消6/22/202428Operating SystemOperating System2.1.4 进程的特征与状态进程的特征与状态 1.进程的特征和定义进程的特征和定义 通常的程序是不能并发执行的。应为之配置进程控制块，即PCB；而由程序段程序段、相关的数据段数据段和PCB三部分便构成了进程实体进程实体进程实体进程实体。在许多情况下所说的进程，实际上是指进程实体。所谓创建进程创建进程，实质上是创建进程实体中的PCB；而撤销进程撤销进程，实质上是撤销进程的PCB。6/22/202429Operating SystemOperating System进程概念进程概念进程概念进程概念q较典型的进程定义有：较典型的进程定义有：v进程是进程是程序程序的的一次执行一次执行v进程是一个程序及其数据在处理机上顺序进程是一个程序及其数据在处理机上顺序执行执行时时所所发生的活动发生的活动v进程是程序在一个数据集合上运行的过程，它进程是程序在一个数据集合上运行的过程，它是系统进行资源是系统进行资源分配和调度分配和调度的一个的一个独立单位独立单位q在引入了进程实体的概念后，我们可以把在引入了进程实体的概念后，我们可以把传统传统OS中的进程定义为：中的进程定义为：“进程是进程实进程是进程实体的运行过程，是系统进行资源分配和调体的运行过程，是系统进行资源分配和调度的一个独立单位度的一个独立单位”6/22/202430Operating SystemOperating System进程与程序的区别进程与程序的区别进程与程序的区别进程与程序的区别q进程是动态的，程序是静态的进程是动态的，程序是静态的：程序是有序代码：程序是有序代码的集合；进程是程序的执行。通常进程不可在计的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和算机之间迁移；而程序通常对应着文件、静态和可以复制可以复制q进程是暂时的，程序的永久的进程是暂时的，程序的永久的：进程是一个状态：进程是一个状态变化的过程，程序可长久保存变化的过程，程序可长久保存q进程与程序的组成不同进程与程序的组成不同：进程的组成包括程序、：进程的组成包括程序、数据和进程控制块（即进程状态信息）数据和进程控制块（即进程状态信息）q进程与程序的对应关系进程与程序的对应关系：通过多次执行，一个程：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可序可对应多个进程；通过调用关系，一个进程可包括多个程序包括多个程序6/22/202431Operating SystemOperating System进程的特征与状态进程的特征与状态进程的特征与状态进程的特征与状态进程的三种基本状态进程的三种基本状态进程的三种基本状态进程的三种基本状态q就绪就绪(Ready)状态状态 v可运行，已获得除可运行，已获得除CPU外的所需资源，等待分配外的所需资源，等待分配CPUv一个系统中多个处于就绪状态的进程排成一个系统中多个处于就绪状态的进程排成就绪队列就绪队列q执行执行(Running)状态状态 v占用占用CPU运行运行；处于此状态的进程的数目；处于此状态的进程的数目0时，有该类资源时，有该类资源S.value0时，该类资源已分配完毕，时，该类资源已分配完毕，|S.value|=该该信号量链表中信号量链表中已阻塞进程的数目已阻塞进程的数目v 对信号量的每次对信号量的每次signal操作，操作，S.value:=S.value+1若加若加1后仍是后仍是S.value0，表示在该信号量链表中仍表示在该信号量链表中仍有等待该资源的进程被阻塞，则应调用有等待该资源的进程被阻塞，则应调用wakeup原原语，将语，将S.L链表中的第一个等待进程唤醒。链表中的第一个等待进程唤醒。若若S.value的初值为的初值为1，表示只允许一个进程访问临，表示只允许一个进程访问临界资源，此时的信号量转化为界资源，此时的信号量转化为互斥信号量互斥信号量6/22/202495Operating SystemOperating System信号量机制信号量机制信号量机制信号量机制ANDAND型信号量型信号量型信号量型信号量qAND型信号量型信号量 在在有有些些任任务务中中，一一个个进进程程先先要要获获得得多多个个共共享享资资源源后后才才能能执执行行，若若进进程程A和和B都都要要访访问问共共享享数数据据D和和E，设设信信号号量量Dmutex和和Emutex mutex(MUTual Exclusion)的的初值均为初值均为1在两个进程中都要包含两个对在两个进程中都要包含两个对Dmutex和和Emutex的操作，的操作，即即process A:process B:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程若进程A和和B按下述次序交替执行按下述次序交替执行wait操作：操作：process A:wait(Dmutex);于是于是Dmutex=0process B:wait(Emutex);于是于是Emutex=0process A:wait(Emutex);于是于是Emutex=-1 A阻塞阻塞process B:wait(Dmutex);于是于是Dmutex=-1 B阻塞阻塞此时，此时，A和和B处于处于僵持状态，若无僵持状态，若无外力作用无法解外力作用无法解脱，称为脱，称为“死锁死锁”状态状态6/22/202496Operating SystemOperating System信号量机制信号量机制信号量机制信号量机制ANDAND型信号量型信号量型信号量型信号量qAND同步机制的基本思想是同步机制的基本思想是v将进程在整个运行过程中需要的所有资源，将进程在整个运行过程中需要的所有资源，一一次性全部地分配次性全部地分配给进程，待进程使用完后再一给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不作方式：要么全部分配到进程，要么一个也不分配。分配。由死锁理论可知，这样就可避免上述死由死锁理论可知，这样就可避免上述死锁情况的发生。为此，锁情况的发生。为此，在在wait操作中，增加了操作中，增加了一个一个“AND”条件，故称为条件，故称为AND同步，同步，或称为或称为同时同时wait操作，操作，即即Swait(Simultaneous wait)6/22/202497Operating SystemOperating System信号量机制信号量机制信号量机制信号量机制ANDAND型信号量型信号量型信号量型信号量Swait(S1,S2,Sn)if Si1 and and Sn1 then /每个资源都可用每个资源都可用 for i:=1 to n do Si:=Si-1;/分配所有资源分配所有资源 endfor else /否则，将进程放到等待资源否则，将进程放到等待资源Si的队列中的队列中 place 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 endifSsignal(S1,S2,Sn)for i:=1 to n do Si=Si+1;/释放所有资源释放所有资源 Remove all the process waiting in the queue associated with Si into the ready queue.endfor;6/22/202498Operating SystemOperating System信号量机制信号量机制信号量机制信号量机制信号量集信号量集信号量集信号量集q信号量集信号量集v在记录型信号量机制中，在记录型信号量机制中，wait(S)和和signal(S)操操作仅能对信号量施以加作仅能对信号量施以加1或减或减1操作，意味着每次操作，意味着每次只能获得或释放一个单位的临界资源，效率较低只能获得或释放一个单位的临界资源，效率较低v在有些情况下，当在有些情况下，当资源数量低于某下限值时便不予资源数量低于某下限值时便不予分配分配。因而，在每次分配之前，都必须测试该资源。因而，在每次分配之前，都必须测试该资源的数量，看其是否大于等于下限值的数量，看其是否大于等于下限值v在对在对AND型信号量机制扩充的基础上，形成一般型信号量机制扩充的基础上，形成一般化的化的“信号量集信号量集”机制机制vSwait(S1,t1,d1,Sn,tn,dn)vSsignal(S1,d1,Sn,dn)下限值下限值需求值需求值6/22/202499Operating SystemOperating System信号量机制信号量机制信号量机制信号量机制信号量集信号量集信号量集信号量集Swait(S1,t1,d1,Sn,tn,dn)if Sit1 and and Sntn then for i:=1 to n do Si:=Si-di;/一次分配一次分配d个资源个资源 endfor 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.endifSsignal(S1,d1,Sn,dn)for i:=1 to n do Si:=Si+di;/释放所有资源释放所有资源 Remove all the process waiting in the queue associated with Si into the ready queue endfor;6/22/2024100Operating SystemOperating System信号量机制信号量机制信号量机制信号量机制信号量集信号量集信号量集信号量集q一般一般“信号量集信号量集”的几种特殊情况的几种特殊情况vSwait(S,d,d)。此时在信号量集中只有一个信此时在信号量集中只有一个信号量号量S，但允许它每次申请但允许它每次申请d个资源，当现有资源个资源，当现有资源数少于数少于d时，不予分配时，不予分配vSwait(S,1,1)。此时的信号量集已蜕化为一般此时的信号量集已蜕化为一般的记录型信号量的记录型信号量(S1时时)或互斥信号量或互斥信号量(S=1时时)vSwait(S,1,0)。这是一种很特殊且很有用的信号这是一种很特殊且很有用的信号量操作。当量操作。当S1时，允许多个进程进入某特定区；时，允许多个进程进入某特定区；当当S变为变为0后，将阻止任何进程进入特定区。换言后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关之，它相当于一个可控开关6/22/2024101Operating SystemOperating System进程同步进程同步进程同步进程同步q进程同步的基本概念进程同步的基本概念q信号量机制信号量机制q信号量的应用信号量的应用6/22/2024102Operating SystemOperating System信号量的应用信号量的应用信号量的应用信号量的应用q利用信号量实现进程互斥利用信号量实现进程互斥 mutex作为互斥锁使用作为互斥锁使用Var mutex:semaphore:=1;begin parbegin process 1:begin repeat wait(mutex);critical section signal(mutex);remainder seetion until false;end process 2:begin repeat wait(mutex);critical section signal(mutex);remainder section until false;end parend 6/22/2024103Operating SystemOperating System信号量的应用信号量的应用信号量的应用信号量的应用q利用信号量实现进程互斥利用信号量实现进程互斥v利用整型信号量机制实现进程互斥时应注意，利用整型信号量机制实现进程互斥时应注意，wait(mutex)和和signal(mutex)必须必须成对成对出现出现v缺少缺少wait(mutex)会导致会导致系统混乱系统混乱，不能保证对，不能保证对临界资源的互斥访问临界资源的互斥访问v缺少缺少signal(mutex)将会使临界将会使临界资源永远不被释资源永远不被释放放，从而使因等待该资源而阻塞的进程不再被，从而使因等待该资源而阻塞的进程不再被唤醒唤醒6/22/2024104Operating SystemOperating System信号量的应用信号量的应用信号量的应用信号量的应用q利用信号量实现前趋关系利用信号量实现前趋关系v设有两个并发进程设有两个并发进程P1和和P2。P1中有语句中有语句S1，P2中中有语句有语句S2，希望在执行完希望在执行完S1后执行后执行S2v为实现这种前趋关系，可让进程为实现这种前趋关系，可让进程P1和和P2共享一个共享一个公用信号量公用信号量S，并赋初值为并赋初值为0，将，将signal(S)操作放在操作放在语句语句S1后面；而在后面；而在S2语句前插入语句前插入wait(S)操作操作v进程进程P1，S1;signal(S);v进程进程P2，wati(S);S2;v由于由于S被初始化被初始化为为0，若，若P2先执行，必定阻塞，只先执行，必定阻塞，只有在进程有在进程P1执行完使执行完使S增为增为1后，后，P2才能执行才能执行S2操操作作6/22/2024105Operating SystemOperating System2.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-10 前趋图举例 abcdefg6/22/2024106Operating SystemOperating System 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;signal(c);signal(d);end;6/22/2024107Operating SystemOperating System2.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-10 前趋图举例 abcdefg6/22/2024108Operating SystemOperating System 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;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;6/22/2024109Operating SystemOperating System2.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-10 前趋图举例 abcdefg6/22/2024110Operating SystemOperating System 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;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;6/22/2024111Operating SystemOperating System2.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-10 前趋图举例 abcdefg6/22/2024112Operating SystemOperating System 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;signal(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;6/22/2024113Operating SystemOperating System2.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-10 前趋图举例 abcdefg6/22/2024114Operating SystemOperating System 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;signal(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;6/22/2024115Operating SystemOperating System 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;signal(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 6/22/2024116Operating SystemOperating System第二章第二章第二章第二章 进程管理进程管理进程管理进程管理q进程的基本概念进程的基本概念 q进程控制进程控制 q进程同步进程同步 q经典进程的同步问题经典进程的同步问题 q管程机制管程机制 q进程通信进程通信 q线程线程 6/22/2024117Operating SystemOperating System经典进程的同步问题经典进程的同步问题经典进程的同步问题经典进程的同步问题q生产者生产者消费者问题消费者问题q哲学家进餐问题哲学家进餐问题q读者读者写者问题写者问题6/22/2024118Operating SystemOperating System生产者生产者生产者生产者消费者问题消费者问题消费者问题消费者问题q前面我们已经对生产者前面我们已经对生产者消费者问题消费者问题(The producer-consumer problem)做了一些描述，但未考虑进程的互斥做了一些描述，但未考虑进程的互斥与同步问题，因而造成了数据与同步问题，因而造成了数据Counter的不定性。由于生的不定性。由于生产者产者消费者问题是相互合作的进程关系的一种抽象，例消费者问题是相互合作的进程关系的一种抽象，例如，如，在输入时，输入进程是生产者，计算进程是消费者；在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者，而在输出时，则计算进程是生产者，而打印进程是消费者，因此，因此，该问题有很大的代表性及实用价值该问题有很大的代表性及实用价值6/22/2024119Operating SystemOperating System生产者生产者生产者生产者消费者问题消费者问题消费者问题消费者问题q利用记录型信号量解决生产者利用记录型信号量解决生产者消费者问题消费者问题 假定在生产者和消费者之间的公用缓冲池中，具有假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区个缓冲区v考虑哪些是考虑哪些是互斥资源、互斥资源、哪些是哪些是资源信号量？资源信号量？v互斥资源互斥资源缓冲区、计数器，设缓冲区、计数器，设互斥信号量互斥信号量mutex实现诸进程对缓冲池的互斥使用及计数器的实现诸进程对缓冲池的互斥使用及计数器的加减操作加减操作v资源信号量资源信号量缓冲池，设信号量缓冲池，设信号量empty和和full分分别表示缓冲池中别表示缓冲池中空缓冲区空缓冲区和和满缓冲区满缓冲区的数量。的数量。v假定这些生产者和消费者相互等效，只要缓冲池未假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息空，消费者便可从缓冲池中取走一个消息6/22/2024120Operating SystemOperating System生产者生产者生产者生产者消费者问题消费者问题消费者问题消费者问题Var mutex,empty,full:semaphore:=1,n,0;buffer:array0,n-1 of item;in,out:integer=0,0;begin parbegin producer:begin/生产者进程生产者进程 repeat producer an item nextp;/产一个产品产一个产品 wait(empty);/empty减减1 wait(mutex);/加锁加锁 buffer(in):=nextp;in:=(in+1)mod n;/移动生产指针移动生产指针 signal(mutex);/解锁解锁 signal(full);/full增增1 until false;end consumer:begin/消费者进程消费者进程 repeat wait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)mod n;signal(mutex);signal(empty);consumer the item in nextc;until false;end parend end 6/22/2024121Operating SystemOperating System生产者生产者生产者生产者消费者问题消费者问题消费者问题消费者问题q在生产者在生产者消费者问题中要消费者问题中要注意注意以下几点以下几点v在每个程序中用于实现互斥的在每个程序中用于实现互斥的wait(mutex)和和signal(mutex)必须必须成对地出现成对地出现；v对资源信号量对资源信号量empty和和full的的wait和和signal操作，同操作，同样需要样需要成对地出现成对地出现，但它们分别处于，但它们分别处于不同的进程不同的进程中。中。例如，例如，wait(empty)在生产进程中，而在生产进程中，而signal(empty)则在消费进程中，生产进程若因执行则在消费进程中，生产进程若因执行wait(empty)而阻塞，而阻塞，则以后将由消费进程将它唤醒；则以后将由消费进程将它唤醒；v在每个程序中的多个在每个程序中的多个wait操作顺序不能颠倒操作顺序不能颠倒。应先应先执行对资源信号量的执行对资源信号量的wait操作，然后再执行对互斥操作，然后再执行对互斥信号量的信号量的wait操作操作，否则可能，否则可能引起引起进程进程死锁死锁6/22/2024122Operating SystemOperating System生产者生产者生产者生产者消费者问题消费者问题消费者问题消费者问题q利用利用AND信号量解决生产者信号量解决生产者消费者问题消费者问题var mutex,empty,full:semaphore:=1,n,0;buffer:array0,n-1 of item;in out:integer =0,0;begin parbegin producer:begin repeat produce an item in nextp;Swait(empty,mutex);buffer(in):=nextp;in:=(in+1)mod n;Ssignal(mutex,full);until false;end consumer:begin repeat Swait(full,mutex);nextc:=buffer(out);out:=(out+1)mod n;Ssignal(mutex,empty);consumer the item in nextc;until false;end parend end 6/22/2024123Operating SystemOperating System2.4.1 同步和互斥混合问题同步和互斥混合问题 桌子上有一只盘子，每次只能放入一只水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子。一个儿子专等吃盘中的桔子，一个女儿专等吃盘中的苹果。Var S,SP,SO:semaphore:=1,0,0;6/22/2024124Operating SystemOperating System2.4.1 同步和互斥混合问题同步和互斥混合问题process father begin L1:have an apple;P(S);put an apple;V(SP);go to L1;end6/22/2024125Operating SystemOperating System2.4.1 同步和互斥混合问题同步和互斥混合问题process mother begin L2:have an orange;P(S);put an orange;V(SO);go to L2;end6/22/2024126Operating SystemOperating System2.4.1 同步和互斥混合问题同步和互斥混合问题process son begin L3:P(SO);get an orange;V(S);eat an orange;go to L3;end6/22/2024127Operating SystemOperating System2.4.1 同步和互斥混合问题同步和互斥混合问题process daughter begin L4:P(SP);get an apple;V(S);eat an apple;go to L4;end6/22/2024128Operating SystemOperating System经典进程的同步问题经典进程的同步问题经典进程的同步问题经典进程的同步问题q生产者生产者消费者问题消费者问题q哲学家进餐问题哲学家进餐问题q读者读者写者问题写者问题6/22/2024129Operating SystemOperating System哲学家进餐问题哲学家进餐问题哲学家进餐问题哲学家进餐问题q哲学家进餐问题（哲学家进餐问题（The Dinning Philosophers Problem）是由是由Dijkstra提出并解决的典型进程提出并解决的典型进程同步问题同步问题q问题描述问题描述v5个哲学家坐在桌子边，桌上有个哲学家坐在桌子边，桌上有5个碗和个碗和5支筷子支筷子v哲家家的生活方式是交替地进行思考和进餐哲家家的生活方式是交替地进行思考和进餐v哲学家饥饿时便拿起两边的筷子进餐，但只有当拿到哲学家饥饿时便拿起两边的筷子进餐，但只有当拿到两支后才能进餐两支后才能进餐v用餐毕，放下筷子继续思考用餐毕，放下筷子继续思考6/22/2024130Operating SystemOperating System哲学家进餐问题哲学家进餐问题哲学家进餐问题哲学家进餐问题q利用记录型信号量解决哲学家进餐问题利用记录型信号量解决哲学家进餐问题v经分析可知，放在桌子上的筷子是经分析可知，放在桌子上的筷子是临界资源临界资源，在一段时间内只允许一位哲学家使用。在一段时间内只允许一位哲学家使用。v为了实现对筷子的互斥使用，可以用一个信号为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：数组。其描述如下：Var chopstick:array0,4 of semaphore;6/22/2024131Operating SystemOperating System哲学家进餐问题哲学家进餐问题哲学家进餐问题哲学家进餐问题所有信号量均被初始化为所有信号量均被初始化为1，第第i位哲学家的活动可描述为：位哲学家的活动可描述为：repeat wait(chopsticki);wait(chopstick(i+1)mod 5);eat;signal(chopsticki);signal(chopstick(i+1)mod 5);think;until false;问题：同时拿起一侧的筷子，则问题：同时拿起一侧的筷子，则死锁死锁 如何解决？如何解决？6/22/2024132Operating SystemOperating System哲学家进餐问题哲学家进餐问题哲学家进餐问题哲学家进餐问题q可采取以下几种解决方法可采取以下几种解决方法v至多至多只允许有四位只允许有四位哲学家同时去哲学家同时去拿左边拿左边的筷子，最终的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释能保证至少有一