计算机操作系统复习串讲第五讲

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

2、g SystemOperating SystemBy LLHPage 32022-3-25q两种方式两种方式v顺序执行：顺序执行：是是单道单道批处理系统的执行方式，批处理系统的执行方式，也用于也用于简单的单片机简单的单片机系统系统v并发执行：并发执行：现在的操作系统，具有许多新的现在的操作系统，具有许多新的特征。引入并发执行的目的是为了提高特征。引入并发执行的目的是为了提高资源资源利用率利用率Operating SystemOperating SystemBy LLHPage 42022-3-25q顺序执行的特征顺序执行的特征(1)(1)顺序性：顺序性：处理机的操作严格按照程序所处理机的操作严

3、格按照程序所规定的顺序执行。规定的顺序执行。(2)(2)封闭性：封闭性：程序运行时独占全机资源，其程序运行时独占全机资源，其执行结果不受外界因素影响。执行结果不受外界因素影响。(3)(3)可再现性：可再现性：只要程序执行时的环境和初只要程序执行时的环境和初始条件相同，当程序重复执行时都将获得始条件相同，当程序重复执行时都将获得相同的结果。相同的结果。Operating SystemOperating SystemBy LLHPage 52022-3-25q前趋图前趋图(Precedence Graph)是一个是一个有向无循有向无循环环图，记为图，记为DAG(Directed Acyclic G

4、raph)，用于描述进程之间执行的前后关系。图中的用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序个结点之间存在的偏序(Partial Order)或前或前趋关系趋关系(Precedence Relation)“”Operating SystemOperating SystemBy LLHPage 62022-3-25q每个结点还可具有一个重量每个结点还可具有一个重量(Weight, 权值权值)，用于用于表示该结点所含有的程序量或结点

5、的执行时间。表示该结点所含有的程序量或结点的执行时间。P1P3P8P9P4P2P5P6P7（a a）具有九个结点的前趋图）具有九个结点的前趋图S1S2S3（b b）具有循环的图）具有循环的图Operating SystemOperating SystemBy LLHPage 72022-3-25并发执行时的前趋图并发执行时的前趋图P1P2P3P4I1I2I3I4C1C2C3C4Operating SystemOperating SystemBy LLHPage 82022-3-25q例如有两个循环程序例如有两个循环程序A和和B，它们共享一个变，它们共享一个变量量NN = N + 1;Print

6、( N ); N = 0 ;q程序程序A和和B以不同的速度运行以不同的速度运行(失去封闭性，导失去封闭性，导致不可再现性）致不可再现性）Operating SystemOperating SystemBy LLHPage 92022-3-25q并发执行的特征并发执行的特征v间断间断(异步异步)性性 走走停停走走停停，一个程序可能走到中途，一个程序可能走到中途停下来，失去原有的时序关系；停下来，失去原有的时序关系；Operating SystemOperating SystemBy LLHPage 102022-3-25q并发执行的特征并发执行的特征v失去封闭性失去封闭性 共享资源，受其他程序的

7、控制逻辑的影响。共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。另一个程序修改，失去原有的不变特征。v失去可再现性失去可再现性 失去封闭性失去封闭性 失去可再现性；外界环境失去可再现性；外界环境在程序的两次执行期间发生变化，失去原在程序的两次执行期间发生变化，失去原有的可重复特征有的可重复特征Operating SystemOperating SystemBy LLHPage 112022-3-25q动态性动态性：执行、创建、调度、撤销。：执行、创建、调度、撤销。q独立性独立性：运行、分配资源、调

8、度。：运行、分配资源、调度。q并发性：并发性：多个多个同存于内存中，且同存于内存中，且能在一段时间内同时运行；引入进程实体能在一段时间内同时运行；引入进程实体的目的就是并发执行的目的就是并发执行q异步性异步性：各进程按各自独立的、不可预知：各进程按各自独立的、不可预知的速度向前推进的速度向前推进q结构性结构性：；进程的创建与撤消就是；进程的创建与撤消就是PCB的创建的创建与撤消。与撤消。Operating SystemOperating SystemBy LLHPage 122022-3-251. 进程的特征和定义进程的特征和定义 通常的程序是不能并发执行的。应为之配置进通常的程序是不能并发执

9、行的。应为之配置进程控制块，即程控制块，即PCB；而由而由程序段程序段、相关的、相关的数据数据段段和和PCB三部分便构成了三部分便构成了。在许多情。在许多情况下所说的进程，实际上是指进程实体。况下所说的进程，实际上是指进程实体。所谓所谓创建进程创建进程，实质上是创建进程实体中的，实质上是创建进程实体中的PCB；而而撤销进程撤销进程，实质上是撤销进程的，实质上是撤销进程的PCB。Operating SystemOperating SystemBy LLHPage 132022-3-25q就绪就绪(Ready)状态状态 v可运行，已获得除可运行，已获得除CPU外的所需资源，等待外的所需资源，等待分

10、配分配CPUv一个系统中多个处于就绪状态的进程排成一个系统中多个处于就绪状态的进程排成就就绪队列绪队列q执行执行(Running)状态状态v占用占用CPU运行运行；处于此状态的进程的数目；处于此状态的进程的数目=CPU的数目的数目v没有其它进程可以执行时（如所有进程都在没有其它进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的阻塞状态），通常会自动执行系统的idle进进程。程。Operating SystemOperating SystemBy LLHPage 142022-3-25q阻塞阻塞(Blocked)状态状态 v等待某种条件（如等待某种条件（如I/O操作或进程同步），操作

11、或进程同步），在条件满足之前在条件满足之前无法继续执行无法继续执行。该事件发生。该事件发生前即使把处理机分配给该进程，也无法运行前即使把处理机分配给该进程，也无法运行v通常阻塞进程也排成一个通常阻塞进程也排成一个阻塞队列阻塞队列Operating SystemOperating SystemBy LLHPage 152022-3-25就绪就绪阻塞阻塞执行执行I/O完成完成I/O请请求求进程调度进程调度时间片完时间片完Operating SystemOperating SystemBy LLHPage 162022-3-25图图 2-5 进程的五种基本状态及其转换进程的五种基本状态及其转换 就绪

12、阻塞执行时间片完进程调度I/O完成I/O请求创建创建 终止终止 3. 创建状态和终止状态创建状态和终止状态 Operating SystemOperating SystemBy LLHPage 172022-3-25活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O具具有有挂挂起起状状态态的的进进程程状状态态图图I/O完成Operating SystemOperating SystemBy LLHPage 182022-3-25q为了描述和记录进程的运行变化过程，并使之为了描述和记录进程的运行变化过程，并使之能正确运行，系统能正确运行，系统为每个进程建立一个进程控为每个

13、进程建立一个进程控制块制块。从结构上看，每个进程由程序段、数据从结构上看，每个进程由程序段、数据段和进程控制块三部分组成。段和进程控制块三部分组成。进程控制块进程控制块PCB，用于记录进程的属性特征用于记录进程的属性特征,是操作系统中最重是操作系统中最重要的记录型数据结构。要的记录型数据结构。v创建一个进程时为其建立创建一个进程时为其建立PCB，进程控制块进程控制块是进程存在的标志；是进程存在的标志；v进程运行时，系统通过进程运行时，系统通过PCB了解进程运行状了解进程运行状态，并控制和管理进程；态，并控制和管理进程；v进程结束时，收回进程结束时，收回PCB，进程随之消亡。，进程随之消亡。Op

14、erating SystemOperating SystemBy LLHPage 192022-3-253进程控制块的组织方式进程控制块的组织方式q 链接方式链接方式 把具有同一状态的把具有同一状态的PCB用其中的用其中的链接字链接成一个队列，可以形成链接字链接成一个队列，可以形成就绪队列就绪队列、若干个若干个阻塞队列阻塞队列和和空白队列空白队列.Operating SystemOperating SystemBy LLHPage 202022-3-25PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB930879010执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针

15、阻塞队列指针空闲队列指针空闲队列指针.Operating SystemOperating SystemBy LLHPage 212022-3-25q索引方式索引方式 系统根据所有进程的状态建立几系统根据所有进程的状态建立几张张索引表索引表，如，如就绪索引表就绪索引表、阻塞索引表阻塞索引表等，等，并把各索引表在内存的首地址记录在专用并把各索引表在内存的首地址记录在专用单元中。索引表中记录的是单元中。索引表中记录的是PCB在在PCB表表中的地地址中的地地址Operating SystemOperating SystemBy LLHPage 222022-3-25执行指针执行指针就绪索引表就绪索引表

16、PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表阻塞索引表就绪表指针就绪表指针阻塞表指针阻塞表指针Operating SystemOperating SystemBy LLHPage 232022-3-25q职责是对系统中全部进程实施有效管理，职责是对系统中全部进程实施有效管理，包括包括v创建新进程创建新进程v终止已结束进程终止已结束进程v终止由于某事件而无法运行下去的进程终止由于某事件而无法运行下去的进程v负责进程的状态转换负责进程的状态转换q进程控制由进程控制由OS的内核通过原语来实现。的内核通过原语来实现。 Operating SystemOperating Syste

17、mBy LLHPage 242022-3-25q一旦操作系统发现了要求创建新进程的事件后，一旦操作系统发现了要求创建新进程的事件后，便调用进程创建原语便调用进程创建原语Creat( )按下述步骤创建按下述步骤创建一个新进程。一个新进程。为新进程分配资源为新进程分配资源 初始化进程控制块初始化进程控制块将创建的进程置于就绪队列将创建的进程置于就绪队列 PCBPCBPCBPCB就绪队列就绪队列申请空白申请空白PCBOperating SystemOperating SystemBy LLHPage 252022-3-25q引起进程终止的事件引起进程终止的事件v正常结束正常结束v异常结束异常结束越界

18、错误、保护措、非法指令、特权指令错、越界错误、保护措、非法指令、特权指令错、超时、超时、I/O故障等故障等v外界干预外界干预操作员或操作系统干预操作员或操作系统干预 如发生了死锁，由如发生了死锁，由操作员或操作系统终止该进程操作员或操作系统终止该进程父进程请求父进程请求父进程终止父进程终止Operating SystemOperating SystemBy LLHPage 262022-3-25q 进程阻塞进程阻塞：正在执行的进程因等待一个事件，：正在执行的进程因等待一个事件，让出让出CPU.q 进程唤醒：进程唤醒：当一个等待事件发生后，将被该事当一个等待事件发生后，将被该事件阻塞的进程唤醒件

19、阻塞的进程唤醒(从阻塞队列移入就绪队列从阻塞队列移入就绪队列)。q 引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件v请求系统服务请求系统服务 v启动某种操作启动某种操作 v新数据尚未到达新数据尚未到达v无新工作可做无新工作可做Operating SystemOperating SystemBy LLHPage 272022-3-25q 进程的挂起进程的挂起v当当出现引起进程挂起的事件出现引起进程挂起的事件时，系统将利用时，系统将利用挂起原语挂起原语suspend( )将指定进程或处于阻塞状将指定进程或处于阻塞状态的进程挂起态的进程挂起vsuspend()原语的执行过程原语的执行过程首先检查被

20、挂起进程的状态：首先检查被挂起进程的状态： 活动就绪活动就绪静止就绪静止就绪 活动阻塞活动阻塞静止阻塞静止阻塞若被挂起的进程正在执行，则转向调度程若被挂起的进程正在执行，则转向调度程序重新调度序重新调度Operating SystemOperating SystemBy LLHPage 282022-3-25q 进程的激活过程进程的激活过程v当发生激活进程的事件时，系统将利用激当发生激活进程的事件时，系统将利用激活原语活原语active( )将指定进程激活将指定进程激活vactive()原语执行过程原语执行过程激活原语先将进程从外存激活原语先将进程从外存调入内存调入内存，检查该进程的现行状态：

21、检查该进程的现行状态： 静止就绪静止就绪活动就绪活动就绪 静止阻塞静止阻塞活动阻塞活动阻塞Operating SystemOperating SystemBy LLHPage 292022-3-25q进程的基本概念进程的基本概念 q进程控制进程控制 q进程同步进程同步 q经典进程的同步问题经典进程的同步问题 q进程通信进程通信 q线程线程 Operating SystemOperating SystemBy LLHPage 302022-3-252.3 进进 程程 同同 步步 进程同步的主要任务是对多个相关进程在执进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间

22、行次序上进行协调，以使并发执行的诸进程之间能有效的能有效的共享资源共享资源和和相互合作相互合作，从而使程序的执，从而使程序的执行具有可再现性。行具有可再现性。Operating SystemOperating SystemBy LLHPage 312022-3-25q互斥定义：当多个进程因为争夺临定义：当多个进程因为争夺临界资源而互斥执行称为进程的界资源而互斥执行称为进程的互斥。互斥。制约关系：间接制约。制约关系：间接制约。临界资源：也称独占资源，是指在临界资源：也称独占资源，是指在一段时间内只允许一个进程访问的一段时间内只允许一个进程访问的资源。例如打印机，磁带机，也可资源。例如打印机，磁带

23、机，也可以是进程共享的数据、变量等。以是进程共享的数据、变量等。Operating SystemOperating SystemBy LLHPage 322022-3-25q 生产者生产者-消费者消费者(producer-consumer)问题问题v 有一群生产者进程在生产产品，并将这些产有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设程与消费者进程能并发执行，在两者之间设置了一个具有置了一个具有n个个缓冲区缓冲区的缓冲池，生产者的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；进程将它

24、所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都费。尽管所有的生产者进程和消费者进程都是以是以异步异步方式运行的，但它们之间必须保持方式运行的，但它们之间必须保持同步同步，即不允许消费者进程到一个空缓冲区，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品满产品且尚未被取走的缓冲区中投放产品Operating SystemOperating SystemBy LLHPage 332022-3-25q不论是不

25、论是硬件临界资源硬件临界资源还是还是软件临界资源软件临界资源，多个进，多个进程必须程必须互斥互斥地对它进行访问地对它进行访问q每个进程中访问临界资源的那段代码即每个进程中访问临界资源的那段代码即临界区临界区q每个进程进入临界区之前应先每个进程进入临界区之前应先对欲访问的临界资对欲访问的临界资源进行检查源进行检查，看是否正在被访问。如果此刻该临，看是否正在被访问。如果此刻该临界资源未被访问，该进程可进入临界区，并设置界资源未被访问，该进程可进入临界区，并设置它正在被访问的标志，在临界区它正在被访问的标志，在临界区之前之前执行的这段执行的这段代码称为代码称为进入区进入区q临界区临界区之后之后也要加

26、上一段代码，用于将临界区被也要加上一段代码，用于将临界区被访问的标志恢复为未被访问的标志，称为访问的标志恢复为未被访问的标志，称为退出区退出区Operating SystemOperating SystemBy LLHPage 342022-3-253. 临界区临界区(critical section) 可把一个访问临界资源的循环进程描述如下：可把一个访问临界资源的循环进程描述如下：while(1) entry section; /进入区进入区 critical section; /临界区临界区 exit section; /退出区退出区 remainder section; /其它部分其它部

27、分Operating SystemOperating SystemBy LLHPage 352022-3-25q同步机制应遵循的规则同步机制应遵循的规则v空闲让进空闲让进当临界区空闲时，应允许一个进程进入临界区当临界区空闲时，应允许一个进程进入临界区v忙则等待忙则等待 当已有进程进入临界区时，其他进程必须等待当已有进程进入临界区时，其他进程必须等待v有限等待有限等待 对要求访问临界资源的进程，应保证在有限时间对要求访问临界资源的进程，应保证在有限时间内进入自己的临界区，防止内进入自己的临界区，防止死等死等v让权等待让权等待 当进程不能进入自己的临界区时，应立即释放处当进程不能进入自己的临界区时

28、，应立即释放处理机，防止理机，防止忙等忙等Operating SystemOperating SystemBy LLHPage 362022-3-25q进程同步的基本概念进程同步的基本概念q信号量机制信号量机制q信号量的应用信号量的应用Operating SystemOperating SystemBy LLHPage 372022-3-25q 并发执行时，会出现差错并发执行时，会出现差错ax=count;ax=ax+1;count=ax;bx=count;bx=ax-1;count=bx;count+;count-;Operating SystemOperating SystemBy LLH

29、Page 382022-3-25q信号量机制是由荷兰学者信号量机制是由荷兰学者Dijkstra在在 1965年提年提出的一种进程同步机制。出的一种进程同步机制。q信号量的特殊性：信号量的特殊性：u信号量信号量只能通过只能通过初始化初始化和和两个标准的原语两个标准的原语来访来访问，且访问过程问，且访问过程不受进程调度的打断。不受进程调度的打断。u必须置一次且只能置一次初值；必须置一次且只能置一次初值；u初值不能为负数初值不能为负数(可分配的资源数量可分配的资源数量)；u只能执行只能执行wait、signal操作操作(P、V操作操作) P、V分别是荷兰语的分别是荷兰语的test(proberen)

30、和和increment(verhogen)Operating SystemOperating SystemBy LLHPage 392022-3-25q信号量类型信号量类型: :v整型信号量：未遵循整型信号量：未遵循“让权等待让权等待”的准则的准则v记录型信号量记录型信号量vAND型信号量型信号量v信号量集信号量集Operating SystemOperating SystemBy LLHPage 402022-3-25q由于整型信号量存在由于整型信号量存在”忙等忙等“问题，有了记录型信问题，有了记录型信号量。号量。q记录型信号量的数据结构定义如下：记录型信号量的数据结构定义如下：struct

31、 semaphore integer value; / 可分配资源可分配资源 Pointer_PCB L; / 等待进程队列等待进程队列 ;Operating SystemOperating SystemBy LLHPage 412022-3-25q记录型信号量记录型信号量v采取了采取了“让权等待让权等待”的策略，是一种不的策略，是一种不存在存在“忙等忙等”现象的进程同步机制。现象的进程同步机制。v在记录型信号量机制中，除了需要一个在记录型信号量机制中，除了需要一个用于代表用于代表资源数目资源数目的整型变量的整型变量value外，外，还应增加一个还应增加一个进程链表进程链表L，用于链接所，用于

32、链接所有被该资源阻塞的进程。有被该资源阻塞的进程。Operating SystemOperating SystemBy LLHPage 422022-3-25vwait(s)操作操作 (原语原语)也叫也叫P操作：荷兰语操作：荷兰语“proberen”“检测检测”之意。之意。意味着请求分配一个单位资源。意味着请求分配一个单位资源。wait(s) / 请求分配资源请求分配资源 s.value -; if (s.value 0) /没有空闲资源，没有空闲资源，调用进程调用进程 block(s.L); /被阻塞，进入被阻塞，进入s的等待队列；的等待队列；PCBPCBPCBPCB和和s相关的等待队列相关

33、的等待队列PCBOperating SystemOperating SystemBy LLHPage 432022-3-25 也叫也叫V操作：荷兰语操作：荷兰语“verhogen”“增量增量”之意，之意， 意味着释放一个单位资源。意味着释放一个单位资源。 signal(s) / 释放资源释放资源 s.value +; if (s = 0) /有进程被阻塞有进程被阻塞, 从等待队列中唤从等待队列中唤 wakeup(s.L); / 醒一个进程醒一个进程, 使其进入就绪状态使其进入就绪状态vsignal(s)操作操作 (原语原语)PCBPCBPCB和和s相关的等待队列相关的等待队列PCBPCBOpe

34、rating SystemOperating SystemBy LLHPage 442022-3-25例例 桌上有一个空盘子，只允许放一个水果。爸爸桌上有一个空盘子，只允许放一个水果。爸爸可以向盘中放苹果，也可以向盘中放橘子，儿子可以向盘中放苹果，也可以向盘中放橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一个水果，请用定当盘空时，一次只能放一个水果，请用P、V操作实现爸爸、儿子、女儿三个操作实现爸爸、儿子、女儿三个“并发进程并发进程”的的同步。同步。Operating SystemOperating SystemBy LL

35、HPage 452022-3-25分析：分析：这是一个明显的同步问题，也称为生产者这是一个明显的同步问题，也称为生产者和消费者问题。和消费者问题。 爸爸可以向盘子中放入两类水果：橘子、苹爸爸可以向盘子中放入两类水果：橘子、苹果；然后儿子、女儿每人可以消费其中的一种水果；然后儿子、女儿每人可以消费其中的一种水果。果。 爸爸是生产者，子女是消费者，也就是只有爸爸是生产者，子女是消费者，也就是只有爸爸放入水果，子女才能消费水果；只有子女消爸爸放入水果，子女才能消费水果；只有子女消费完水果，爸爸才能再次放入水果。费完水果，爸爸才能再次放入水果。Operating SystemOperating Sys

36、temBy LLHPage 462022-3-25设设empty、orange和和apple分别为爸爸、儿子和女儿分别为爸爸、儿子和女儿的私用信号量。的私用信号量。empty表示盘子是否为空，其含义表示盘子是否为空，其含义是爸爸是否可以开始放入水果，初值为是爸爸是否可以开始放入水果，初值为1表示可以表示可以放；放；orange表示盘中是否有橘子，其含义是儿子是表示盘中是否有橘子，其含义是儿子是否可以开始取橘子，其初值为否可以开始取橘子，其初值为0表示不能取橘子；表示不能取橘子；apple表示盘中是否有苹果，其含义是女儿是否可以表示盘中是否有苹果，其含义是女儿是否可以开始取苹果，其初值为开始取苹

37、果，其初值为0表示不能取苹果。则爸爸、表示不能取苹果。则爸爸、儿子和女儿的同步过程描述如下：儿子和女儿的同步过程描述如下：Operating SystemOperating SystemBy LLHPage 472022-3-25while(1) P(empty); 将水果放入盘中将水果放入盘中; if (放入的是橘子放入的是橘子) V(orange); else V(apple);while(1) P(orange); 从盘中取出橘子从盘中取出橘子; V(empty); 吃橘子；吃橘子；while(1) P(apple); 从盘中取出苹果从盘中取出苹果; V(empty); 吃苹果；吃苹果；

38、semaphore empty=1, orange=0, apple=0;父亲进程：父亲进程： 儿子进程：儿子进程： 女儿进程：女儿进程：Operating SystemOperating SystemBy LLHPage 482022-3-25q在有些任务中，一个进程先要获得多个共享资源在有些任务中，一个进程先要获得多个共享资源后才能执行，若进程后才能执行，若进程A和和B都要访问共享数据都要访问共享数据D和和E，设信号量，设信号量Dmutex和和Emutex的初值均为的初值均为1q在两个进程中都要包含两个对在两个进程中都要包含两个对Dmutex和和Emutex的操作，的操作， 即即 proc

39、ess A: process B: wait(Dmutex); wait(Emutex); wait(Emutex); wait(Dmutex); 若进程若进程A和和B交替执行交替执行wait操作，将出现死锁操作，将出现死锁Operating SystemOperating SystemBy LLHPage 492022-3-25qAND同步机制的基本思想是同步机制的基本思想是 AND型信号量是指同时需要多种资源且每种资型信号量是指同时需要多种资源且每种资源都需占用一个时的信号量操作。用一个原语源都需占用一个时的信号量操作。用一个原语申请整段代码需要的多个临界资源，要么全部申请整段代码需要的多

40、个临界资源，要么全部分配给它，要么一个都不分配。我们称分配给它，要么一个都不分配。我们称AND型型信号量集信号量集P原语为原语为Swait（Simultaneous Wait），），V原语为原语为Ssignal（Simultaneous Signal）。）。Operating SystemOperating SystemBy LLHPage 502022-3-25qAND同步机制的基本思想是同步机制的基本思想是 在在Swait中，各个信号量的次序并不重要，虽中，各个信号量的次序并不重要，虽然这会对进程归入哪个阻塞队列产生影响，但然这会对进程归入哪个阻塞队列产生影响，但由于是对资源全部分配或不分

41、配，所以总有进由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此程获得全部资源并在推进之后释放资源，因此不会出现死锁。不会出现死锁。Operating SystemOperating SystemBy LLHPage 512022-3-25Swait(S1, S2, , Sn) if( Si1 & & Sn1 ) / 每个资源都可用每个资源都可用 for( i=1;i= n;i+) Si = Si - 1; / 分配所有资源分配所有资源 else /否则，将进程放到等待资源否则，将进程放到等待资源Si的队列中的队列中 将该进程加入第一个出现将该进程

42、加入第一个出现Si1的的Si的等待队列，的等待队列， 并将其恢复地址设置为并将其恢复地址设置为Swait的开始地址的开始地址; Operating SystemOperating SystemBy LLHPage 522022-3-25Ssignal(S1, S2, , Sn) for( i=1; i=n; i+ ) Si = Si + 1; /释放所有资源释放所有资源 将将Si的等待队列中的所有进程移入到就绪队列的等待队列中的所有进程移入到就绪队列 ; Operating SystemOperating SystemBy LLHPage 532022-3-25q进程同步的基本概念进程同步的基

43、本概念q信号量机制信号量机制q信号量的应用信号量的应用Operating SystemOperating SystemBy LLHPage 542022-3-25S1：是否允许司机启动汽车，初值为：是否允许司机启动汽车，初值为0S2：是否允许售票员开门，初值为：是否允许售票员开门，初值为0semaphore s1=0, s2=0;司机进程：司机进程：while (1) P(S1); 启动汽车启动汽车; 正常行车；正常行车； 到站停车；到站停车； V(S2);售票员进程售票员进程:while (1) 关车门关车门; V(S1)； 售票售票 P(S2)； 开车门；开车门； 上下乘客；上下乘客；Op

44、erating SystemOperating SystemBy LLHPage 562022-3-25q设有两个并发进程设有两个并发进程P1和和P2。P1中有语句中有语句S1，P2中有语句中有语句S2，希望在执行完，希望在执行完S1后执行后执行S2p1: S1； signal(S);semaphore S=0; / 公共信号量，初值设为公共信号量，初值设为0P2: wati(S); S2; S1S1、S2S2语句的顺序执行语句的顺序执行S1S2Operating SystemOperating SystemBy LLHPage 572022-3-25图图 2-12 前趋图举例前趋图举例 S4

45、S5S3S1S6S2abcdefg semaphore a=0,b=0,c=0,d=0,e=0,f=0,g= 0;PS1() S1; signal(a); signal(b); PS2() wait(a); S2; signal(c); signal(d); PS3() wait(b); S3; signal(e); PS4() wait(c); S4; signal(f); PS5() wait(d); S5; signal(g); PS6() wait(f); wait(g); wait(e); S6; Operating SystemOperating SystemBy LLHPage

46、592022-3-25q进程的基本概念进程的基本概念 q进程控制进程控制 q进程同步进程同步 q经典进程的同步问题经典进程的同步问题 q进程通信进程通信 q线程线程 Operating SystemOperating SystemBy LLHPage 602022-3-25q生产者生产者消费者问题消费者问题q哲学家进餐问题哲学家进餐问题q读者读者写者问题写者问题struct semaphore integer value; / 可分配资源可分配资源 Pointer_PCB L; / 等待进程队列等待进程队列 ;Operating SystemOperating SystemBy LLHPage

47、 612022-3-25q 有一群生产者进程在生产产品，并将这些产品有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一消费者进程能并发执行，在两者之间设置了一个具有个具有n个个缓冲区缓冲区的缓冲池，生产者进程将它所的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以生产者进程和消费者进程都是以异步异步方式运行方式运行的，但它们

48、之间必须保持的，但它们之间必须保持同步同步，即不允许消费，即不允许消费者进程到一个空缓冲区去取产品；也不允许生者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品冲区中投放产品Operating SystemOperating SystemBy LLHPage 622022-3-252. 多个生产者，多个消费者，公用多个生产者，多个消费者，公用n个环形缓冲区个环形缓冲区v在这种情况中，生产者与消费者存在同步关系，在这种情况中，生产者与消费者存在同步关系，而且各个生产者之间、各个消费者之间存在互而且各个生产者之间、

49、各个消费者之间存在互斥关系斥关系,他们必须互斥地访问缓冲区。他们必须互斥地访问缓冲区。 in,outOperating SystemOperating SystemBy LLHPage 632022-3-25v考虑哪些是考虑哪些是互斥资源、互斥资源、哪些是哪些是资源信号量？资源信号量？v互斥资源互斥资源缓冲区、计数器，设缓冲区、计数器，设互斥信号量互斥信号量mutex实现诸进程对缓冲池的互斥使用及指针实现诸进程对缓冲池的互斥使用及指针的加的加1操作操作v资源信号量资源信号量缓冲池，设信号量缓冲池，设信号量empty和和full分分别表示缓冲池中别表示缓冲池中空缓冲区空缓冲区和和满缓冲区满缓冲区

50、的数量。的数量。v假定这些生产者和消费者相互等效，只要缓冲假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个缓冲池未空，消费者便可从缓冲池中取走一个消息消息Operating SystemOperating SystemBy LLHPage 642022-3-25解题如下：解题如下：v定义四个信号量：定义四个信号量：vempty表示缓冲区是否为空，初值为表示缓冲区是否为空，初值为n。vfull表示缓冲区中是否为满，初值为表示缓冲区中是否为满，初值为0。vmutex1生产者之间的互斥信号

51、量，初值为生产者之间的互斥信号量，初值为1。vmutex2消费者之间的互斥信号量，初值为消费者之间的互斥信号量，初值为1。v设缓冲区的编号为设缓冲区的编号为0n 1，定义两个指针，定义两个指针in和和out，分别是生产者进程和消费者进程使用的指，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。针，指向下一个可用的缓冲区。Operating SystemOperating SystemBy LLHPage 652022-3-25生产者进程生产者进程while( 1 ) 生产一个产品生产一个产品; P(empty); P(mutex1); 产品送往产品送往bufferin; in=

52、(in+1)%n; V(mutex1); V(full);消费者进程消费者进程while(i) P(full); P(mutex2); 从从bufferout中取出产品中取出产品; out=(out+1)%n; V(mutex2) V(empty);semaphore empty=n, full= 0, mutex1=1, mutex2=1;int in=0, out=0;Operating SystemOperating SystemBy LLHPage 662022-3-25生产者进程生产者进程while( 1 ) 生产一个产品生产一个产品; Swait(empty,mutex); 产品送

53、往产品送往bufferin; in=(in+1)%n; Ssignal(full,mutex);消费者进程消费者进程while(i) Swait(full,mutex); 从从bufferout中取出产品中取出产品; out=(out+1)%n; Ssignal(mutex,empty);semaphore empty=n, full= 0, mutex=1;int in=0, out=0;Operating SystemOperating SystemBy LLHPage 672022-3-25q生产者生产者消费者问题消费者问题q哲学家进餐问题哲学家进餐问题q读者读者写者问题写者问题Oper

54、ating SystemOperating SystemBy LLHPage 682022-3-25q进程的基本概念进程的基本概念 q进程控制进程控制 q进程同步进程同步 q经典进程的同步问题经典进程的同步问题 q进程通信进程通信 q线程线程 Operating SystemOperating SystemBy LLHPage 692022-3-25q进程的基本概念进程的基本概念 q进程控制进程控制 q进程同步进程同步 q经典进程的同步问题经典进程的同步问题 q进程通信进程通信 q线程线程 Operating SystemOperating SystemBy LLHPage 702022-3-

55、25q进程通信的类型进程通信的类型q消息传递通信的实现方法消息传递通信的实现方法q消息传递系统实现中的若干问题消息传递系统实现中的若干问题q消息缓冲队列通信机制消息缓冲队列通信机制 信号量机制就是一种进程通信方式！信号量机制就是一种进程通信方式！缺点：（缺点：（1）交换的信息量比较少；交换的信息量比较少； （2）效率低；效率低； （3）对用户不透明。）对用户不透明。Operating SystemOperating SystemBy LLHPage 712022-3-25进程通信：为协调完成某一任务，几个进程间应保持联系，进程通信：为协调完成某一任务，几个进程间应保持联系， 即交换一定数量的信

56、息。即交换一定数量的信息。：仅交换少量的数据和一些状态，如前述的同步：仅交换少量的数据和一些状态，如前述的同步 与互斥方式。（与互斥方式。（P、V操作）操作）：交换信息量大，用户可直接利用：交换信息量大，用户可直接利用OS提供的通信提供的通信 命令高效的传送大量数据。（命令高效的传送大量数据。（OS隐去了实现细隐去了实现细 节，对用户是透明的。）节，对用户是透明的。）效率低效率低通信对用户不透明通信对用户不透明1. 共享存储器系统共享存储器系统2. 消息传递系统消息传递系统3. 管道通信系统管道通信系统Operating SystemOperating SystemBy LLHPage 722

57、022-3-251. 共享存储器系统共享存储器系统(Shared-Memory System)v基于共享数据结构的通信方式基于共享数据结构的通信方式要求诸进程共享某些数据结构，借以实现进程要求诸进程共享某些数据结构，借以实现进程间的数据交换。如生产者间的数据交换。如生产者消费者问题中，用消费者问题中，用有界缓冲区来实现通信有界缓冲区来实现通信对用户对用户不透明不透明，程序员负担重，操作系统效率，程序员负担重，操作系统效率低，只低，只适合传递少量适合传递少量数据，属于数据，属于低级通信方式低级通信方式v 基于共享存储区的通信方式基于共享存储区的通信方式在存储器中划出一块共享存储区，诸进程可通在存

58、储器中划出一块共享存储区，诸进程可通过对共享存储区中的数据读写来实现通信过对共享存储区中的数据读写来实现通信属于高级通信，属于高级通信，适合传送大量适合传送大量数据数据 Operating SystemOperating SystemBy LLHPage 732022-3-252. 消息传递系统消息传递系统(Message passing system)v进程之间的数据交换，是以格式化的进程之间的数据交换，是以格式化的消息消息(message)为单位的；在计算机网络中，又把为单位的；在计算机网络中，又把message称为称为报文报文v实现方式：程序员直接利用系统提供的一组实现方式：程序员直接利

59、用系统提供的一组通信通信命令命令(原语原语)进行通信。进行通信。v消息传递系统的通信方式属于高级通信方式。可消息传递系统的通信方式属于高级通信方式。可分为分为直接通信方式直接通信方式和和间接通信方式间接通信方式v优点：传递信息量大、对用户透明、应用广泛优点：传递信息量大、对用户透明、应用广泛v广泛应用于单机系统、多机系统、计算机网络广泛应用于单机系统、多机系统、计算机网络Operating SystemOperating SystemBy LLHPage 742022-3-252. 消息传递系统消息传递系统(Message passing system)1）直接通信方式。）直接通信方式。 发送

60、进程直接将消息发送给接收进程，并将消发送进程直接将消息发送给接收进程，并将消息挂在接收进程的消息队列上，接收进程从息挂在接收进程的消息队列上，接收进程从消息队列中取得消息。消息队列中取得消息。 2）间接通信方式。）间接通信方式。 发送进程发送消息到发送进程发送消息到“信箱信箱”中，接收进程从中，接收进程从“信箱信箱”中取得消息，相应的系统称为电子中取得消息，相应的系统称为电子邮件系统。邮件系统。Operating SystemOperating SystemBy LLHPage 752022-3-253. 管道管道(Pipe)通信（共享文件方式）通信（共享文件方式）v管道管道是指用于连接一个读进程和一个写进程