操作系统第二章1

1、Operating SystemOperating SystemPage 12022-3-14Operating SystemOperating SystemPage 22022-3-14q重点重点v理解理解进程进程的含义的含义(PCB,(PCB,进程状态进程状态) )v理解和掌握同步的概念及经典理解和掌握同步的概念及经典进程同步进程同步问题问题 ，是本课，是本课程的重点之一程的重点之一q难点难点v会写会写进程同步进程同步问题的算法问题的算法q知识点知识点v进程、线程、进程的特征、进程、线程、进程的特征、PCBPCB、进程控制、进程状态、进程控制、进程状态转换、转换、 进程同步、进程通信进程同

2、步、进程通信Operating SystemOperating SystemPage 32022-3-14q 前驱图和程序执行前驱图和程序执行q 进程的描述进程的描述q 进程控制进程控制 q 进程同步进程同步 q 经典进程的同步问题经典进程的同步问题 q 进程通信进程通信 q 线程线程 Operating SystemOperating SystemPage 42022-3-14q单道批处理系统顺序执行q多道程序系统并发执行v在系统中同时存在几个相互独立的程序，这些程序在系统中交叉执行，共享系统中的资源，提高资源利用率。但也会引起一系列的问题，包括：对资源的竞争、程序间的合作与协同、进程间的通

3、信。q要解决这些问题，用程序的概念已经不能描述在内存中运行的状态，必须引入新的概念进程。Operating SystemOperating SystemPage 52022-3-14q前趋图前趋图更好的描述程序的顺序更好的描述程序的顺序/并发执行并发执行q程序的顺序执行程序的顺序执行q程序的并发执行程序的并发执行 Operating SystemOperating SystemPage 62022-3-14q前趋图前趋图(Precedence Graph)是一个是一个有向无循环有向无循环图，图，用于用于描述进程之间执行的前后关系。描述进程之间执行的前后关系。图中的每个结点可用图中的每个结点可用

4、于描述一个于描述一个程序段或进程程序段或进程，乃至一条语句；结点间的，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的有向边则用于表示两个结点之间存在的偏序偏序(Partial (Partial Order)Order)或前趋关系或前趋关系(Precedence Relation)(Precedence Relation)“”q如果如果(Pi, Pj)(Pi, Pj), ,可写成可写成PiPjPiPj，称，称PiPi是是PjPj的的直接前直接前趋趋，而称，而称PjPj是是PiPi的的直接后继直接后继, ,必须必须PiPi执行完成后再执行执行完成后再执行PjPj。没有前趋的结点称为。没有

5、前趋的结点称为初始结点初始结点(Initial Node)(Initial Node)，没有后继的结点称为没有后继的结点称为终止结点终止结点(Final Node)(Final Node)Operating SystemOperating SystemPage 72022-3-14q每个结点还具有一个每个结点还具有一个权值权值(Weight)(Weight)，用于表示该，用于表示该结点所含有的程序量或结点的执行时间结点所含有的程序量或结点的执行时间P1P3P8P9P4P2P5P6P7(a) 具有九个结点的具有九个结点的前趋图前趋图S1S2S3(b) 具有循环的具有循环的图图，不是前驱图不是前驱

6、图Operating SystemOperating SystemPage 82022-3-14q前趋图前趋图更好的描述程序的顺序更好的描述程序的顺序/并发执行并发执行q程序的顺序执行程序的顺序执行q程序的并发执行程序的并发执行 Operating SystemOperating SystemPage 92022-3-14q程序运行的两种方式程序运行的两种方式v顺序执行顺序执行: 例如：先输入，再计算，最例如：先输入，再计算，最后输出后输出v并发执行并发执行 Operating SystemOperating SystemPage 102022-3-14q仅当前一操作仅当前一操作( (程序段程

7、序段) )执行完后，才能执行后继操执行完后，才能执行后继操作。作。例如，在进行计算时，总须先输入用户的程序例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。和数据，然后进行计算，最后才能打印计算结果。语句语句S1,S2,S3必须按必须按顺序执行顺序执行 S1: a =x+y; S2: b =a-5; S3: c =b+1;Operating SystemOperating SystemPage 112022-3-14q IiCiPi和和S1S2S3程序的顺序执行程序的顺序执行 (a) 程序的顺序执行程序的顺序执行I1C1P1I2C2P2(b) 三条语句的顺序执

8、行三条语句的顺序执行S1S2S3Operating SystemOperating Systemq顺序执行的特征顺序执行的特征v顺序性顺序性：一个操作完成后开始下一个操作：一个操作完成后开始下一个操作v封闭性封闭性：独占资源，资源：独占资源，资源的状态只由该程序决定，的状态只由该程序决定，执行结果不受外界因素影响执行结果不受外界因素影响v可再现性可再现性：重复执行时，初始条件相同则结果相重复执行时，初始条件相同则结果相同同 ，无论，无论“走走停停走走停停”还是还是“不停顿不停顿” Page 122022-3-14Operating SystemOperating SystemPage 1320

9、22-3-14q前趋图前趋图更好的描述程序的顺序更好的描述程序的顺序/并发执行并发执行q程序的顺序执行程序的顺序执行q程序的并发执行程序的并发执行 Operating SystemOperating SystemPage 142022-3-14宏观上同时执行，微观上交替执行。宏观上同时执行，微观上交替执行。一个程序的执行尚未结束，另一个程序的执行已经一个程序的执行尚未结束，另一个程序的执行已经开始开始, ,实际上某时刻只有一个程序在实际上某时刻只有一个程序在CPUCPU上运行。上运行。q程序的并发执行可描述为程序的并发执行可描述为: :S0cobegin S1,S2SncoendSn+1Ope

10、rating SystemOperating SystemPage 152022-3-14P1P2P3P4I1I2I3I4C1C2C3C4无前驱关系的程序段，可并发执行无前驱关系的程序段，可并发执行Operating SystemOperating SystemPage 162022-3-14在该例中存在下述前趋关系：在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而而Ii+1和和Ci及及Pi-1是重迭的，无前趋关系（互不依赖），是重迭的，无前趋关系（互不依赖），即即Ii+1和和Ci及及Pi-1可以并发执行。可以并发执行。Operating Syst

11、emOperating SystemPage 172022-3-14q 对于具有下述四条语句的程序段对于具有下述四条语句的程序段v S1: a =x+2v S2: b =y+4v S3: c =a+bv S4: d =c+b S1S2S3S4S1 S2可并发执行Operating SystemOperating SystemPage 182022-3-14q并发执行的特征并发执行的特征v间断间断(异步异步)性性 走走停停走走停停 ，一个程序可能走到中途停下来，失去原有的，一个程序可能走到中途停下来，失去原有的时序关系；时序关系；v失去封闭性失去封闭性共享资源共享资源(包括数据包括数据)，会受其

12、他程序的影响。如：一个程，会受其他程序的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。要使用的资源被其他程序占用。的不变特征。要使用的资源被其他程序占用。v失去可再现性失去可再现性失去封闭性失去封闭性 失去可再现性；外界环境在程序的两次执失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征行期间发生变化，失去原有的可重复特征Operating SystemOperating SystemPage 192022-3-14q 例如有例如有两个循环程序两个循环程序A和和B，它们共享一个变量，它们共享

13、一个变量N=nq 程序程序A和和B以不同的速度运行以不同的速度运行(失去封闭性，导致不可再现性）失去封闭性，导致不可再现性）v N=N+1N=N+1在在Print(N)Print(N)和和N=0N=0之前，此时得到的之前，此时得到的N N值分别为值分别为n+1, n+1, n+1n+1, 0, 0v N=N+1N=N+1在在Print(N)Print(N)和和N=0N=0之后，此时得到的之后，此时得到的N N值分别为值分别为n n, 0, 1, 0, 1v N=N+1N=N+1在在Print(N)Print(N)和和N=0N=0之间，此时得到的之间，此时得到的N N值分别为值分别为n n, n

14、+1, 0, n+1, 0N =N+1;Print(N); N =0 ;Operating SystemOperating SystemPage 202022-3-14N =N+1;Print(N); N =0 ;Print(N); N =0 ;N =N+1;Print(N); N =N+1;N =0;注意：注意：A、B程序得到的共享变程序得到的共享变量结果不同，失去封闭性、不可量结果不同，失去封闭性、不可再现性；要得到良好的控制，系再现性；要得到良好的控制，系统必须要进行管理统必须要进行管理进程控制进程控制管理管理Operating SystemOperating SystemPage 21

15、2022-3-14Operating SystemOperating SystemPage 222022-3-14q 要得到良好的控制，系统：要得到良好的控制，系统：v执行过程要进行管理执行过程要进行管理 进程控制管理进程控制管理v需要一个能反映或记录程序执行过程中共享资源需要一个能反映或记录程序执行过程中共享资源/ /变量的基本单位变量的基本单位 进程进程Operating SystemOperating SystemPage 232022-3-14q 并发执行并发执行失去封闭性的原因失去封闭性的原因是共享资源的影响，去掉这种影是共享资源的影响，去掉这种影响就行了。响就行了。1966年，由年

16、，由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 前两条保证一个程序的两次读之间数据不变化；最后一条保前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉证写的结果不丢掉现在的问题是这个条件不好检查Operating SystemOperating Syste

17、mPage 242022-3-14程序并发执行的条件（程序并发执行的条件（1966年由年由Bernstein提出）提出）若两个程序P1和P2满足下述条件，便能并发执行且有可再现性：R(P1)W(P2)R(P2)W(P1)W(P1)W(P2) = 为程序 Pi 在执行期间所需参考参考的所有变量的集合。为程序 Pi 在执行期间所需改变改变的所有变量的集合。例如：S1: a := x + y S2: b := z + 1S3: c := a - bS4: d := c + 1Operating SystemOperating SystemPage 252022-3-14程序并发执行的条件（程序并发执

18、行的条件（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(

19、S3)=c Operating SystemOperating SystemPage 262022-3-14q前驱图和程序执行前驱图和程序执行q进程的描述进程的描述q进程控制进程控制 q进程同步进程同步 q经典进程的同步问题经典进程的同步问题 q进程通信进程通信 q线程线程 Operating SystemOperating System在多道程序环境下，程序并发执行，执行过程具有在多道程序环境下，程序并发执行，执行过程具有间断性，程序已经无法描述这种状况。间断性，程序已经无法描述这种状况。q进程的定义和特征q进程的状态及转换q进程管理中的数据结构（PCB）Page 272022-3-14Op

20、erating SystemOperating SystemPage 282022-3-14q何谓进程（何谓进程（Process） q如何理解进程概念？如何理解进程概念？进程与程序有何差别？进程与程序有何差别？Operating SystemOperating SystemPage 292022-3-14q较典型的进程定义有：较典型的进程定义有：v进程是进程是程序程序的的一次执行；一次执行；v进程是一个程序及其数据在处理机上顺序进程是一个程序及其数据在处理机上顺序执行时执行时所所发生的活动；发生的活动；v进程是程序在一个数据集合上运行的过程，它是进程是程序在一个数据集合上运行的过程，它是系统进

21、行资源系统进行资源分配和调度分配和调度的一个的一个独立单位；独立单位；Operating SystemOperating SystemPage 302022-3-14q程序与进程对照程序与进程对照 q程序程序 进程进程1. 1. 唱歌的曲谱唱歌的曲谱 演唱演唱2. 2. 剧本剧本 演出演出3. 3. 菜谱菜谱 烹饪烹饪Operating SystemOperating SystemPage 312022-3-14阅读菜谱阅读菜谱准备原料准备原料烹制菜肴烹制菜肴饭菜饭菜阅读洗衣机手册阅读洗衣机手册准备衣服、洗衣粉准备衣服、洗衣粉设定参数，洗衣服设定参数，洗衣服干净衣服干净衣服程序程序输入输入运行

22、运行输出输出程序程序输入输入运行运行输出输出分时切换分时切换Operating SystemOperating SystemPage 322022-3-14q 程序是有序指令的集合，是一个静态概念，程序是有序指令的集合，是一个静态概念，可以作为程序可以作为程序文件被长久保存，反复使用。文件被长久保存，反复使用。 进程是一次执行过程，一个动态的概念，进程是一次执行过程，一个动态的概念，具有生命期具有生命期， 可创建和撤销。可创建和撤销。q 进程是一个独立的运行单位，可与其他进程并行进程是一个独立的运行单位，可与其他进程并行(或并发或并发)运行，而程序不能。运行，而程序不能。q 进程是资源分配和处

23、理机调度的基本单位。进程是资源分配和处理机调度的基本单位。q 进程与程序的组成不同进程与程序的组成不同：进程的组成包括程序、数据和进：进程的组成包括程序、数据和进程控制块（即进程状态信息）。程控制块（即进程状态信息）。q 进程与程序的对应关系进程与程序的对应关系：通过多次执行，一个程序可对应：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序多个进程；通过调用关系，一个进程可包括多个程序Operating SystemOperating SystemPage 332022-3-14q结构特征结构特征：；进程的创建与撤消就是；进程的创建与撤消就是PCBPCB的创建与撤消的

24、创建与撤消q动态性动态性： 一次执行过程，有一定的生命周期一次执行过程，有一定的生命周期q并发性：并发性：多个多个同存于内存中，且能在一同存于内存中，且能在一段时间内同时运行段时间内同时运行( (并发执行并发执行) ) q独立性独立性： 独立运行、独立分配资源、独立接受调独立运行、独立分配资源、独立接受调度度q异步性异步性：各进程按各自独立的、不可预知的速度：各进程按各自独立的、不可预知的速度向前推进向前推进Operating SystemOperating SystemPage 342022-3-14q进程的定义与特征进程的定义与特征q进程的状态及转换进程的状态及转换q进程控制块进程控制块O

25、perating SystemOperating SystemPage 352022-3-14q 就绪就绪(Ready)状态状态 v可运行，已获得除可运行，已获得除CPU外的所需资源，等待分配外的所需资源，等待分配CPUv一个系统中多个处于就绪状态的进程排成一个系统中多个处于就绪状态的进程排成就绪队列就绪队列q 执行执行(Running)状态状态 v占用占用CPU运行运行；处于此状态的进程的数目；处于此状态的进程的数目0 创建成功，从父进程返回，其值为创建成功，从父进程返回，其值为子进程的子进程的PID号号 -1 创建失败创建失败q产生的子进程会复制父进程的数据与堆栈空间，并产生的子进程会复制

26、父进程的数据与堆栈空间，并继承父进程的用户代码、环境变量、已打开的文件继承父进程的用户代码、环境变量、已打开的文件和资源限制等。和资源限制等。Operating SystemOperating SystemPage 782022-3-14#include int main( ) int p1;while(p1=fork()=-1);if(p1=0) printf(“I am child 1n”); /子进程子进程else /父进程父进程 printf(“I am parentn”); return 0;Operating SystemOperating SystemPage 792022-3-

27、14q父进程创建子进程后，父子进程分支中的程序各自父进程创建子进程后，父子进程分支中的程序各自私有，其余部分，包括创建前和分支结束后的程序私有，其余部分，包括创建前和分支结束后的程序段，均为父子进程共享。段，均为父子进程共享。例：例：#include main( )int p1;while(p1=fork()=-1);if(p1=0) putchar(b);elseputchar(a);putchar(y);输出结果：输出结果：byayOperating SystemOperating SystemPage 802022-3-14q如果对如果对fork()调用后的返回值不加以判断，不区调用后的

28、返回值不加以判断，不区分父子进程各自的程序空间，则分父子进程各自的程序空间，则fork()后面的程后面的程序为父子共享。序为父子共享。例：例： #include main( )fork();fork();putchar(A);输出结果：输出结果：AAAAOperating SystemOperating SystemPage 812022-3-142. 进程终止进程终止格式：格式：void exit(int status)其中其中status是子进程向父进程发送的终止消息，是子进程向父进程发送的终止消息，父进程用父进程用wait()系统调用接收这个消息。系统调用接收这个消息。3. 进程睡眠进程

29、睡眠格式：格式：sleep(int n)功能：进程睡眠功能：进程睡眠n秒。执行进程会挂起，把处理秒。执行进程会挂起，把处理机让出来。机让出来。Operating SystemOperating SystemPage 822022-3-144. 父进程等待子进程父进程等待子进程格式：格式：pid_t wait(int *stat_addr, 0 )功能：等待任意一个子进程终止。功能：等待任意一个子进程终止。Operating SystemOperating SystemPage 832022-3-14#include main( )int p1;while(p1=fork()=-1);if (p

30、10)wait(0);putchar(A);else /sleep(10); putchar(B); exit(0);Operating SystemOperating SystemPage 842022-3-14q前驱图和程序执行前驱图和程序执行q进程的描述进程的描述q进程控制进程控制 q进程同步进程同步 q经典进程的同步问题经典进程的同步问题 q进程通信进程通信 q线程线程 Operating SystemOperating SystemPage 852022-3-142.4 进进 程程 同同 步步 进程并发执行虽然提高了资源利用率，但是进程并发执行虽然提高了资源利用率，但是进程会争用资源

31、进程会争用资源(打印机、共享变量打印机、共享变量)，可能会，可能会引引起错误。起错误。 进程同步的主要任务，是使并发执行的诸进进程同步的主要任务，是使并发执行的诸进程之间能有效的程之间能有效的共享资源共享资源和和相互合作相互合作，从而使程，从而使程序的执行具有序的执行具有可再现性可再现性。Operating SystemOperating SystemPage 862022-3-14q进程同步的基本概念进程同步的基本概念q信号量机制信号量机制q信号量的应用信号量的应用Operating SystemOperating SystemPage 872022-3-14q 进程间有两种形式的制约关系进

32、程间有两种形式的制约关系v间接相互制约关系，又称为间接相互制约关系，又称为 互斥互斥 由于共享某种互斥资源，如由于共享某种互斥资源，如CPUCPU、I/OI/O设备等设备等v直接相互制约关系直接相互制约关系这种制约源于进程之间的合作关系。合作的进程这种制约源于进程之间的合作关系。合作的进程为完成一个任务，执行需要按照一定的次序。为完成一个任务，执行需要按照一定的次序。如进程如进程A A向向B B提供数据，当输入缓冲空时，提供数据，当输入缓冲空时，B B不能得到不能得到数据而阻塞；反之当缓冲满时，数据而阻塞；反之当缓冲满时，A A无法写入而阻塞，无法写入而阻塞，又称为又称为 同步同步 Opera

33、ting SystemOperating SystemPage 882022-3-14共享变量的修改冲突！共享变量的修改冲突！Operating SystemOperating SystemPage 892022-3-14同步进程间是一同步进程间是一种种关系关系门诊医生：门诊医生： 开开化验单；化验单； 等等化验结果；化验结果； 继续诊病；继续诊病；化验员：化验员： 等等化验单；化验单； 化验；化验； 填写化验结果；填写化验结果； 病人就诊病人就诊进程同步的例子进程同步的例子Operating SystemOperating SystemPage 902022-3-14q生产者生产者-消费者消

34、费者(producer-consumer)问题问题v有一群生产者进程在生产产品，并将这些产品提供给有一群生产者进程在生产产品，并将这些产品提供给多个消费者进程去消费。多个消费者进程去消费。v一个具有一个具有n n个个缓冲区缓冲区的缓冲池用来存放产品的缓冲池用来存放产品v生产者进程将它所生产的产品放入一个缓冲区中；生产者进程将它所生产的产品放入一个缓冲区中；v消费者进程可从一个缓冲区中取走产品去消费。消费者进程可从一个缓冲区中取走产品去消费。v所有的生产者进程和消费者进程必须保持所有的生产者进程和消费者进程必须保持同步同步，即即不不允许消费者进程到一个空缓冲区去取产品；也不允许允许消费者进程到一

35、个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品中投放产品. .Operating SystemOperating SystemPage 912022-3-14inoutcount=2n个缓冲个缓冲区的缓冲区的缓冲池池v生产者生产者-消费者问题消费者问题解决思路解决思路利用一个数组来表示上述的具有利用一个数组来表示上述的具有n个个(0，1，n-1)缓冲区的缓冲区的缓冲池。缓冲池。用输入指针用输入指针in来指示来指示下一个下一个可可投放产品投放产品的缓冲区，每当生产的缓冲区，每当生产者进程生产并投放一个产品后，者进

36、程生产并投放一个产品后，in=in+1；用一个输出指针；用一个输出指针out来指示来指示下一个下一个可从中可从中获取产品获取产品的缓冲区，每当消费者进程的缓冲区，每当消费者进程取走一个产品后，取走一个产品后，out=out+1。 设缓冲池的组织是循环缓冲，故应把输入指针加设缓冲池的组织是循环缓冲，故应把输入指针加1表示成表示成 in:=(in+1)% n；输出指针加；输出指针加1表示成表示成out:=(out+1) % n引入了一个整型变量引入了一个整型变量counter表示产品数量表示产品数量, 其初始值为其初始值为0。Operating SystemOperating SystemPage

37、 922022-3-14v生产者生产者-消费者问题消费者问题解决思路解决思路指针指针in和和out初始化为初始化为1对于生产者当对于生产者当counter=n时，应执行时，应执行 空操作空操作 ，而对于，而对于消费者进程当消费者进程当counter=0时应执行时应执行空操作空操作生产者和消费者进程中各设一局部变量生产者和消费者进程中各设一局部变量nextp和和nextc ， nextp用于暂时存放刚生产出来的产品用于暂时存放刚生产出来的产品 nextc用于暂时存放用于暂时存放 要消费的产品要消费的产品 Operating SystemOperating SystemPage 932022-3-

38、14producer( ) /*生产者进程生产者进程 while(1) produce an item in nextp; /生产一个产品生产一个产品while (counter=n) ; bufferin=nextp; /将产品存入缓冲区将产品存入缓冲区 in=(in+1) % n; /修改缓冲区指针修改缓冲区指针 counter=counter+1; /修改计数器修改计数器 consumer() /*消费者进程消费者进程 while(1) while (counter=0) ; nextc=bufferout;out= (out+1) % n; counter =counter-1; co

39、nsume the item in nextc; Operating SystemOperating SystemPage 942022-3-14q两段程序在两段程序在顺序执行顺序执行时其结果也会是正确的，但若时其结果也会是正确的，但若并发执并发执行行时，就会出现差错；时，就会出现差错；q问题就在于共享变量问题就在于共享变量countercounter。生产者对它做。生产者对它做加加1 1操作，消操作，消费者对它做费者对它做减减1 1操作，这两个操作在用机器语言实现时，操作，这两个操作在用机器语言实现时， 常可用下面的形式描述常可用下面的形式描述 生产者生产者 ： 消费者：消费者：vregis

40、ter1=counter; register2=counter;vregister1=register1+1; register2=register2-1;vcounter=register1; counter=register2; . .Operating SystemOperating SystemPage 952022-3-14 假设：counter的当前值是5。 如果按下述顺序执行： register1 = counter; register1 = register1+1; register2 = counter; register2 = register2-1; counter =

41、register1; counter = register2; register1 = counter;register1 = register1+1;counter = register1;register2 = counter;register2 = register2-1;counter = register2;(register1=5)(register1=6)(register2=5)(register2=4)(counter=6)(counter=4)counter的值应为的值应为5，但此时得到的是，但此时得到的是4。表明此时的程序已失去再现性。表明此时的程序已失去再现性。解决此问

42、题的关键应是将解决此问题的关键应是将counter作为临界资源处理作为临界资源处理Operating SystemOperating SystemPage 962022-3-14q 临界资源临界资源(Critical Resouce)v一次仅允许一个一次仅允许一个进程使用的资源进程使用的资源系统中许多硬件如打印机等，飞机订票系统中的系统中许多硬件如打印机等，飞机订票系统中的变量变量xv不论是不论是硬件临界资源硬件临界资源还是还是软件临界资源软件临界资源，多，多个进程必须个进程必须互斥互斥地对它进行访问，即一个访地对它进行访问，即一个访问完一个再访问。问完一个再访问。 所以需要对进程访问临界资源

43、所以需要对进程访问临界资源( (访问临界资源访问临界资源的那段代码的执行的那段代码的执行) )进行控制。进行控制。Operating SystemOperating SystemPage 972022-3-14q临界区（临界区（critical section）v在每个进程中访问临界资源的那段代码称为在每个进程中访问临界资源的那段代码称为临界区临界区(critical section)v每个进程进入临界区之前应先每个进程进入临界区之前应先对欲访问的临界资源进对欲访问的临界资源进行检查行检查，看是否正在被访问。如果此刻该临界资源未，看是否正在被访问。如果此刻该临界资源未被访问，该进程可进入临界区

44、，并设置它正在被访问被访问，该进程可进入临界区，并设置它正在被访问的标志，在临界区的标志，在临界区之前之前执行的这段检查代码称为执行的这段检查代码称为进入进入区（区（entry section）v在临界区在临界区之后之后也要加上一段代码，用于将临界区被访也要加上一段代码，用于将临界区被访问的标志恢复为未被访问的标志，称为问的标志恢复为未被访问的标志，称为退出区（退出区（exit section）Operating SystemOperating SystemPage 982022-3-14临界区临界区Operating SystemOperating SystemPage 992022-3-1

45、4producer: repeat /*生产者进程生产者进程produce an item in nextp; /生产一个产品生产一个产品while counter=n do no-op; bufferin =nextp; /将产品存入缓冲区将产品存入缓冲区 in =in+1 mod n; /修改缓冲区指针修改缓冲区指针 counter =counter+1; /修改计数器修改计数器 until false;consumer: repeat /*消费者进程消费者进程 while counter=0 do no-op; nextc =bufferout;out = (out+1) mod n;

46、counter =counter-1; consume the item in nextc; until false; Operating SystemOperating SystemPage 1002022-3-14可把一个访问临界资源的循环进程描述如下：repeat critical section; remainder section;until false; entry sectionexit section 进入区, 进行检查，上锁 临界区 退出区,恢复可访问标志，开锁 剩余区检查和上锁之间不能被打断Operating SystemOperating SystemPage 10120

47、22-3-14q 要对进程的同步和互斥进行管理和控制，保证其按照正确要对进程的同步和互斥进行管理和控制，保证其按照正确的方式执行而并非随机的并发执行，这样的机构称为的方式执行而并非随机的并发执行，这样的机构称为同步同步机制。机制。q 同步机制应遵循的规则同步机制应遵循的规则v空闲让进空闲让进当无进程处于临界区时，应允许一个进程进入临界区当无进程处于临界区时，应允许一个进程进入临界区v忙则等待忙则等待 当已有进程进入临界区时，其他进程必须等待当已有进程进入临界区时，其他进程必须等待v有限等待有限等待 对要求访问临界资源的进程，应保证在有限时间内进入自己的临对要求访问临界资源的进程，应保证在有限时

48、间内进入自己的临界区，防止界区，防止死等死等v让权等待让权等待 当进程不能进入自己的临界区时，应立即释放处理机，防止当进程不能进入自己的临界区时，应立即释放处理机，防止忙忙等等Operating SystemOperating SystemPage 1022022-3-14q进程同步的基本概念进程同步的基本概念q信号量机制信号量机制q信号量的应用信号量的应用Operating SystemOperating SystemPage 1032022-3-14q1965年，荷兰学者年，荷兰学者Dijkstra提出的信号量提出的信号量（Semaphores）机制是一种有效的进程同步工具）机制是一种有效

49、的进程同步工具q目前，信号量机制已广泛应用于单处理机、多处目前，信号量机制已广泛应用于单处理机、多处理机以及计算机网络中理机以及计算机网络中q信号量信号量是是OS提供的管理公有资源的有效手段提供的管理公有资源的有效手段q信号量的值代表可用资源实体的数量信号量的值代表可用资源实体的数量q使用前申请一个资源（使用前申请一个资源（P操作），用完后归还资操作），用完后归还资源（源（V操作）操作）Operating SystemOperating Systemq公共电话厅里有多个电话，如某人要打电话，首先公共电话厅里有多个电话，如某人要打电话，首先要进行申请，看是否有电话空闲，要进行申请，看是否有电话空

50、闲，若有电话空闲，若有电话空闲，则可以使用电话，则可以使用电话，如果电话亭里所有电话都有人正如果电话亭里所有电话都有人正在使用，那后来的人只有排队等候在使用，那后来的人只有排队等候。当某人用完电。当某人用完电话后，则有空电话腾出，正在排队的第一个人就可话后，则有空电话腾出，正在排队的第一个人就可以使用电话。以使用电话。 v某人要打电话，首先要进行申请，相当于执行一某人要打电话，首先要进行申请，相当于执行一次次P操作，申请一个可用资源（电话）；操作，申请一个可用资源（电话）；v某人用完电话，则有空电话腾出，相当于执行一某人用完电话，则有空电话腾出，相当于执行一次次V操作，释放一个可用资源（电话）

51、。操作，释放一个可用资源（电话）。Page 1042022-3-14Operating SystemOperating Systemq信号量机制发展：信号量机制发展：v整型信号量整型信号量 v记录型信号量记录型信号量 v信号量集信号量集Page 1052022-3-14Operating SystemOperating SystemPage 1062022-3-14q整型信号量整型信号量v整型信号量定义为一个整型量整型信号量定义为一个整型量(表示资源数量表示资源数量)，除初始，除初始化外，仅能通过两个标准的原子操作化外，仅能通过两个标准的原子操作wait(S)和和signal(S)来访问。来访

52、问。这两个操作一直被分别称为这两个操作一直被分别称为(wait)P、(signal)V操作。操作。 wait和和signal操作可描述为：操作可描述为： wait(S): while (S0) ; S=S-1; signal(S): S=S+1; vwait(S)和和signal(S)是是原子操作原子操作，执行时是不可中断的。，执行时是不可中断的。 wait申请一个资源，申请一个资源，signal释放一资源。释放一资源。v缺点：缺点：信号量信号量S0时时“忙等忙等”，未遵循，未遵循“让权等待让权等待”Operating SystemOperating SystemPage 1072022-3-

53、14q记录型信号量记录型信号量v采取了采取了“让权等待让权等待”的策略，不存在的策略，不存在“忙等忙等”现现象。象。v在采取了在采取了“让权等待让权等待”的策略后，又会出现多个的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，除了进程等待访问同一临界资源的情况。为此，除了需要一个用于代表需要一个用于代表资源数目资源数目的整型变量的整型变量valuevalue外，外，还应增加一个还应增加一个进程链表进程链表L L，用于链接所有等待进程。，用于链接所有等待进程。v记录型信号量定义如下：记录型信号量定义如下： typedef struct int value ; list of proce

54、ss L; semaphore;Operating SystemOperating SystemPage 1082022-3-14wait(S)和和signal(S)操作可描述为：其中操作可描述为：其中S为信号量为信号量wait(semaphore S) S.value=S.value-1; / 请求一个该类资源请求一个该类资源 if (S.value0) block(S.L); /该类资源已分配完毕该类资源已分配完毕, ,调用调用blockblock原语，进行自我阻塞并放弃处理机、插入到信号量的等待原语，进行自我阻塞并放弃处理机、插入到信号量的等待进程链表进程链表S.LS.L中中 signa

55、l(semaphore S) S.value=S.value+1;/释放一个资源释放一个资源 if (S.value0) wakeup(S.L);/有等待进程，唤醒第一个等有等待进程，唤醒第一个等待进程待进程 Operating SystemOperating SystemPage 1092022-3-14v 在记录型信号量机制中，在记录型信号量机制中，S.valueS.value的初值表示的初值表示系统中系统中某类某类资源的数目资源的数目， 因而又称为因而又称为资源信号量资源信号量v 对信号量对信号量S.valueS.value每次每次waitwait操作，操作， S.value=S.val

56、ue-1S.value=S.value-1S.value0S.value0时，表示有该类资源时，表示有该类资源S.valueS.value0 0时，该类资源已分配完毕，时，该类资源已分配完毕，|S.value|=|S.value|=该该信号量链表中信号量链表中已阻塞进程的数目已阻塞进程的数目v 对信号量的每次对信号量的每次signalsignal操作，操作， S.value=S.value+1S.value=S.value+1若若S.value0S.value0，表示在该信号量链表中仍有等待该资，表示在该信号量链表中仍有等待该资源的进程被阻塞，则应调用源的进程被阻塞，则应调用wakeupwak

57、eup原语，将原语，将S.LS.L链表中链表中的第一个等待进程唤醒。的第一个等待进程唤醒。u若若S.valueS.value的初值为的初值为1 1，表示只允许一个进程访问临界资，表示只允许一个进程访问临界资源，此时的信号量转化为源，此时的信号量转化为互斥信号量互斥信号量Operating SystemOperating SystemPage 1102022-3-14q进程同步的基本概念进程同步的基本概念q信号量机制信号量机制q信号量的应用信号量的应用Operating SystemOperating SystemPage 1112022-3-14q利用信号量实现进程互斥使用资源利用信号量实现进

58、程互斥使用资源q解题步骤解题步骤：v确定临界资源及确定临界资源及个数个数；v确定信号量的初值确定信号量的初值( (临界资源的个数临界资源的个数) )，若初值为，若初值为1 1信号信号量转化为量转化为互斥信号量互斥信号量；v确定进程的确定进程的关键工作步关键工作步（使用临界资源的），写出（使用临界资源的），写出伪伪代码代码。1.1.使用使用P(wait)P(wait)操作和操作和signal(signal)signal(signal)操作对进程互斥进操作对进程互斥进行控制行控制(P(P操作和操作和V V操作分别位于临界区前后操作分别位于临界区前后) )。Operating SystemOpera

59、ting SystemPage 1122022-3-14例例1：过独木桥。：过独木桥。P1 P2 上桥上桥 ； 上桥；上桥； 由西向东过独木桥；由西向东过独木桥； 由东向西过独木桥；由东向西过独木桥； 下桥；下桥； 下桥；下桥； P1P2Operating SystemOperating SystemPage 1132022-3-14分析分析：进程：进程P1、P2因竞争独木桥这个资源而成为互斥关系。因竞争独木桥这个资源而成为互斥关系。设设：信号量：信号量m表示独木桥资源，初值为表示独木桥资源，初值为1表示资源可用。表示资源可用。 semaphore m=1; cobegin p1() / p2

60、() coendOperating SystemOperating SystemPage 1142022-3-14q利用信号量实现进程互斥使用资源应注意：利用信号量实现进程互斥使用资源应注意：vwait(mutex)wait(mutex)和和signal(mutex)signal(mutex)必须必须成对成对出现出现v缺少缺少wait(mutex)wait(mutex)会导致会导致系统混乱系统混乱，不能保证对临界资，不能保证对临界资源的互斥访问源的互斥访问v缺少缺少signal(mutex)signal(mutex)将会使临界将会使临界资源永远不被释放资源永远不被释放，从，从而使因等待该资源而