操作系统原理 Operating System Principles 四川大学计算机学院 段 磊 leiduan@scu.edu.cn 2014 Spring

进程同步使得进程之间能够相互协作和有序使用资源。 进程通信是进程之间数据的相互交换和信息的相互传递。 第4章 进程同步与进程通信 进程同步使得进程之间能够相互协作和有序使用资源。 进程通信是进程之间数据的相互交换和信息的相互传递。

本章目录 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.7 线程的同步和通信 2018/12/31 《计算机操作系统》- 第4章

4.1 进 程 并 发 并发是操作系统的基本特征 进程并发使得程序执行的特点发生了变化 4.1.1 程序的顺序执行 程序的顺序性包括 4.1 进 程 并 发 并发是操作系统的基本特征 进程并发使得程序执行的特点发生了变化 4.1.1 程序的顺序执行 程序的顺序性包括 程序的内部顺序性 程序的外部顺序性 2018/12/31 《计算机操作系统》- 第4章

4.1 进 程 并 发 并发是操作系统的基本特征 进程并发使得程序执行的特点发生了变化 4.1.1 程序的顺序执行 程序的顺序性包括 4.1 进 程 并 发 并发是操作系统的基本特征 进程并发使得程序执行的特点发生了变化 4.1.1 程序的顺序执行 程序的顺序性包括 程序的内部顺序性 程序的外部顺序性 2018/12/31 《计算机操作系统》- 第4章

4.1.1 程序的顺序执行 程序的内部顺序性 程序的外部顺序性 4.1.1 程序的顺序执行 程序的内部顺序性 一个程序的操作代码在计算机处理器上按照顺序执行，一个代码结束后，后一个代码才能开始。 程序的外部顺序性 如果一项任务由多个程序模块组成，程序模块的运行也需要按照调用顺序执行，即程序模块之间的顺序性。 2018/12/31 《计算机操作系统》- 第4章

程序顺序执行具有的特点 顺序性 封闭性 再现性 每个操作必须在上一个操作完成后才能开始；一个程序模块执行完成后另一个程序模块才能开始。 程序运行独占系统全部资源，程序执行的结果除初始条件外，由程序本身决定，不会受到任何其它程序和外界因素的干扰。 再现性 针对相同的数据集合，程序执行的结果总是相同的。中断对程序执行的最终结果没有影响。程序执行的结果是可再现的。 2018/12/31 《计算机操作系统》- 第4章

在多道程序并发执行环境下，处理器的利用率低，系统性能差。 传统的程序顺序执行在多道程序环境下已不适合。 程序顺序执行的不足 限制了多个程序模块的并发执行。 在多道程序并发执行环境下，处理器的利用率低，系统性能差。 传统的程序顺序执行在多道程序环境下已不适合。 2018/12/31 《计算机操作系统》- 第4章

在多道程序环境下，程序是按照多个进程并发执行的。 进程的并发性是指一组进程执行在时间点上交替，在时间段上重叠。 4.1.2 进程的并发性 在多道程序环境下，程序是按照多个进程并发执行的。 进程的并发性是指一组进程执行在时间点上交替，在时间段上重叠。 2018/12/31 《计算机操作系统》- 第4章

进程的并发性 进程并发环境下，一个输入进程还没有完成，另一个计算进程已经开始；或者一个计算进程还没有完成，另一个输出进程已经开始。程序的外部顺序性不再存在。 并发进程之间可能是交互的，相关的。可能在同一时间段内，多个进程执行相同的软件代码，或多个进程共享某些变量，或多个进程请求同一硬件资源，一个进程的执行可能影响到其他进程的执行结果，并发进程之间具有制约关系。 2018/12/31 《计算机操作系统》- 第4章

如果N的初始值为0，程序A、B执行的顺序不同，产生的结果也不同。 进程并发性举例 例如，两个计数程序A、B，都为： N = N + 1； print（N）； 其中，计数值N是共享变量。 如果N的初始值为0，程序A、B执行的顺序不同，产生的结果也不同。 2018/12/31 《计算机操作系统》- 第4章

print（N）； /* 此时打印出的结果为1*/ 程序B：N = N + 1； print（N）； /* 此时打印出的结果为2*/ 进程并发性举例（续） A → B 程序A：N = N + 1； print（N）； /* 此时打印出的结果为1*/ 程序B：N = N + 1； print（N）； /* 此时打印出的结果为2*/ 2018/12/31 《计算机操作系统》- 第4章

print（N）； /* 此时打印出的结果为1*/ 程序A：N = N + 1； print（N）； /* 此时打印出的结果为2*/ 进程并发性举例（续） B → A 程序B：N = N + 1； print（N）； /* 此时打印出的结果为1*/ 程序A：N = N + 1； print（N）； /* 此时打印出的结果为2*/ 2018/12/31 《计算机操作系统》- 第4章

程序A：print(N)；/* 此时打印出的结果为2*/ 程序B：print(N)；/* 此时打印出的结果为2*/ 进程并发性举例（续） A → B → A → B (A、B交替进行) 程序A：N=N+1； 程序B：N=N+1； 程序A：print(N)；/* 此时打印出的结果为2*/ 程序B：print(N)；/* 此时打印出的结果为2*/ 程序运行出现了不可再现性！ 2018/12/31 《计算机操作系统》- 第4章

进程并发执行的特点 间断性 制约性 不可再现性 失去封闭性 进程并发执行充分利用计算机资源，提高了效率。 多个并发进程共享处理器，执行过程是断断续续的，呈现间断性。 制约性 并发进程存在相互制约关系，系统必须对运行次序进行协调。 不可再现性 并发进程交替执行，如果存在共享变量等关系，程序执行的先后不同，会使共享变量的值不同。 失去封闭性 一个进程的执行环境与其它进程有关，程序执行失去了封闭性。 进程并发执行充分利用计算机资源，提高了效率。 2018/12/31 《计算机操作系统》- 第4章

并发执行的进程以各自的速度向前推进，相互之间构成了相互竞争资源和相互协作的关系。 4.1.3 进程间的竞争和协作 并发执行的进程以各自的速度向前推进，相互之间构成了相互竞争资源和相互协作的关系。 1．进程间的竞争 多道程序并发执行环境下，进程的执行失去了封闭性。并发进程相互共处在一个系统中，一个进程的执行必然会影响到其他进程。 2018/12/31 《计算机操作系统》- 第4章

进程间的竞争 共享的资源分为： 互斥共享资源：只有一个进程对资源访问，访问结束并释放后，另外的进程才能访问该资源。 同时共享资源：多个进程可并发访问，不需要一个进程访问结束，其他的进程就可访问的资源。 进程对互斥共享资源的竞争要求OS对进程操作采取同步措施，从时间上和顺序上加以限制，使得进程之间相互制约地使用这些资源，保证资源的完整性。 2018/12/31 《计算机操作系统》- 第4章

由于每个进程都以独立地不可知的速度向前推进，需要具有协作关系的进程需要在某些协调点上相互协调、相互等待，使得双方都能够顺利地运行直至完成。 进程间的协作 由于每个进程都以独立地不可知的速度向前推进，需要具有协作关系的进程需要在某些协调点上相互协调、相互等待，使得双方都能够顺利地运行直至完成。 协作的进程之间存在数据或变量等的共享关系，进程的推进顺序受到一定的限制，进程推进需要按照特定的顺序进行，否则会发生进程执行结果的不可再现与不确定的情况。 2018/12/31 《计算机操作系统》- 第4章

在并发进程之间存在相互协作关系时，系统需要采取同步措施，确保进程以合理的顺序推进，确保进程运行的可再现性和结果的确定性。 进程间的协作 在并发进程之间存在相互协作关系时，系统需要采取同步措施，确保进程以合理的顺序推进，确保进程运行的可再现性和结果的确定性。 并发进程之间的互斥共享资源关系最终也是进程之间的一种协作关系，即并发进程协作共享资源，也是进程同步关系。 2018/12/31 《计算机操作系统》- 第4章

4.1.4 进程同步 生产者和消费者问题 并发进程的共享资源问题 并发进程之间的协作问题 2018/12/31 《计算机操作系统》- 第4章

生产者与消费者问题 问题描述 一个有限空间的共享缓冲区，负责存放货物 生产者向缓冲区中放物品，缓冲区满则不能放 消费者从缓冲区中拿物品，缓冲区空则不能拿 生产者进程 消费者进程 （如何体现进程的同步） 2018/12/31 《计算机操作系统》- 第4章

生产者与消费者问题 缓冲池：数组表示，具有n个(0，1，…，n-1)缓冲区 Var n，integer； 输出指针out：指示下一个可从中获取产品的缓冲区 缓冲池采用循环组织，故： 输入指针加1表示成 in:= (in+1) mod n； 输出指针加1表示成out:= (out+1) mod n。 当 (in+1) mod n = out时表示缓冲池满；而in=out则表示缓冲池空。 整型变量counter：生产者进程投放产品使counter加1；消费者进程取走产品使counter减1。 Var n，integer； type item=…； var buffer: array［0，1，…，n-1］ of item； in，out: 0，1，…，n-1； counter: 0，1，…，n； 2018/12/31 《计算机操作系统》- 第4章

生产者与消费者问题 生产者进程 消费者进程 consumer: repeat producer: repeat produce an item in nextp； while counter=n do no-op； buffer［in］:=nextp； in:=in+1 mod n； counter:=counter+1； until false； 消费者进程 consumer: repeat while counter=0 do no-op； 　　nextc:=buffer［out］； 　　out:=(out+1) mod n； 　　counter:=counter-1； 　　consumer the item in nextc； 　 until false； 2018/12/31 《计算机操作系统》- 第4章

生产者、消费者进程分析 生产者进程 → 消费者进程 生产者进程和消费者进程并发运行 不存在资源的竞争，不会出现问题。 生产者进程和消费者进程并发运行 生产者进程和消费者进程对缓冲区竞争使用 出现生产者进程与消费者进程之间不能协作的问题。 当缓冲区中已经装满产品时，生产者进程得到缓冲区的访问权，生产者进程无法进行生产。 生产者进程与消费者进程都需要对变量counter进行访问，对共享变量的访问可能造成数据不一致。 2018/12/31 《计算机操作系统》- 第4章

生产者与消费者问题 问题的出现 两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述： （问题何在？） register1:=counter； 　register2:=counter； register1:=register1+1；　register2:=register2-1； counter:=register1； 　counter:=register2； 2018/12/31 《计算机操作系统》- 第4章

生产者与消费者问题 register1:=counter； 　register2:=counter； register1:=register1+1；　register2:=register2-1； counter:=register1； 　counter:=register2； 程序的执行已经失去了再现性。为了预防产生这种错误，解决此问题的关键是应把变量counter作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量counter。 register1:=counter； (register1=5) register1:=register1+1； (register1=6) register2:=counter； (register2=5) register2:=register2-1； (register2=4) counter:=register1； (counter=6) counter:=register2； (counter=4) 2018/12/31 《计算机操作系统》- 第4章

生产者与消费者问题 A1→B1→A2→B2→A3→B3 A1→A2→A3→B1→B2→B3 A1→B1→A2→B2→B3→A3 经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为9，最后count的值为9。 A1→A2→A3→B1→B2→B3 经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。 A1→B1→A2→B2→B3→A3 count的值为11。 在进程并发环境下，竞争使用的资源和共享访问的变量，如果在程序中不采取同步措施，实现互斥访问和有序访问，则会出现数据不一致等问题。 A1: register1:=counter； 　 B1: register2:=counter； A2: register1:=register1+1； B2: register2:=register2-1； A3: counter:=register1； B3: counter:=register2； 2018/12/31 《计算机操作系统》- 第4章

生产者与消费者问题 A1→B1→A2→B2→A3→B3 A1→A2→A3→B1→B2→B3 A1→B1→A2→B2→B3→A3 经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为9，最后count的值为9。 A1→A2→A3→B1→B2→B3 经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。 A1→B1→A2→B2→B3→A3 count的值为11。 在进程并发环境下，竞争使用的资源和共享访问的变量，如果在程序中不采取同步措施，实现互斥访问和有序访问，则会出现数据不一致等问题。 2018/12/31 《计算机操作系统》- 第4章

本章目录 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.7 线程的同步和通信 2018/12/31 《计算机操作系统》- 第4章

再次说明：程序的制约方式 间接制约方式 直接制约方式 由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行。 直接制约方式 通常在那些逻辑上相关的程序段之间发生的，一般是由于各种程序段要求共享信息引起的。 2018/12/31 《计算机操作系统》- 第4章

进程同步 基本概念 信号量机制 信号量的应用 制约关系的两种形式 临界资源 临界区 整型、记录型、AND型、信号量集 实现进程互斥 实现前趋关系 2018/12/31 《计算机操作系统》- 第4章

进程的同步（直接作用） 进程的同步：synchronism 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。 具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态 2018/12/31 《计算机操作系统》- 第4章

临界资源：critical resource 进程的互斥（间接作用） mutual exclusion 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥 临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量 2018/12/31 《计算机操作系统》- 第4章

“司机－售票员”问题（同步） 司机进程 While(True) { 启动公车； 驾驶公车； 停止公车； } 售票员进程 关车门； 卖车票； 开车门； } 正确运行过程 While(True) { （售票员）关车门 （司机）启动公车； （司机）驾驶公车； （售票员）卖车票 （司机）停止公车； （售票员）开车门； } 2018/12/31 《计算机操作系统》- 第4章

Spooler目录问题（互斥） 4：File1 5：File2 6：File3 7：Null 8：Null ……… Spooler目录 Out：4 In：7 进程A：N_f_s = In; //In == 7 InsertFileIntoSpooler(N_f_s); In=N_f_s++; //In == 8 进程切换，一切正常 进程B：N_f_s = In; //In == 8 InsertFileIntoSpooler(N_f_s); In=N_f_s++; //In == 9 2018/12/31 《计算机操作系统》- 第4章

Spooler目录问题（互斥） Out：4 In：7 4：File1 5：File2 6：File3 7：Null 8：Null ……… 进程A： N_f_s = In; //In == 7 进程切换 进程B： N_f_s = In; //In == 7 InsertFileIntoSpooler(N_f_s); In=N_f_s++; //In == 8 进程切换，进程B数据丢失 进程A： InsertFileIntoSpooler(N_f_s); In=N_f_s++; //In == 8 2018/12/31 《计算机操作系统》- 第4章

4.2.1 临界资源和临界区 互斥共享的资源称为临界资源。 在程序中对临界资源访问的代码部分称为临界区。 4.2.1 临界资源和临界区 互斥共享的资源称为临界资源。 在生产者和消费者进程中，缓冲区和变量count都是临界资源。 在程序中对临界资源访问的代码部分称为临界区。 进程访问临界资源前都要判断该资源能否访问， 如果能访问，进入到临界区访问临界资源； 如果不能访问，则需要等待，直到该资源能够访问； 访问结束后，需要将资源归还，使其他进程能够知道临界资源已经被当前进程访问结束。 2018/12/31 《计算机操作系统》- 第4章

临界资源和临界区 步骤 临界资源与临界区 While ( 1 ) { } …… entry_section; //申请进入 critical_section; //临界区 exit_section; //声明退出 ……… } 2018/12/31 《计算机操作系统》- 第4章

4.2.2 进程同步准则 空闲让进： 忙则等待： 有限等待： 让权等待： 当无进程在互斥区时，任何有权使用互斥区的进程可进入 4.2.2 进程同步准则 空闲让进： 当无进程在互斥区时，任何有权使用互斥区的进程可进入 忙则等待： 不允许两个以上的进程同时进入互斥区 有限等待： 任何进入互斥区要求应在有限时间内得到满足 让权等待： 处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权 2018/12/31 《计算机操作系统》- 第4章

程序设计时，进入区是判别能否访问临界资源的关键。 如果进程能访问临界资源，则通过进入区，进入临界区访问临界资源； 进程同步准则 程序设计时，进入区是判别能否访问临界资源的关键。 如果进程能访问临界资源，则通过进入区，进入临界区访问临界资源； 否则，进程不能进入临界区访问临界资源； 当进程访问临界资源完后，通过退出区，释放临界资源。 2018/12/31 《计算机操作系统》- 第4章

软件方法在共享内存的单处理机或多处理机系统中实现进程的并发。 4.2.3 早期的临界区管理方法 1．软件方法 软件方法在共享内存的单处理机或多处理机系统中实现进程的并发。 软件方法假定基于内存访问级别的一些基本互斥，对内存同一位置的同时访问将被排序，而访问的顺序并不事先指定。 不需要硬件或操作系统或程序设计语言的任何支持。 2018/12/31 《计算机操作系统》- 第4章

早期的临界区管理方法 – 软件方法 算法1：临界区标志法 算法2：先判断对方进程标志的进程数组标志法 为了实现临界区的管理，采用标志来表示哪个并发进程可以进入临界区访问。 确保每次只有一个进程进入临界区，但强制两个进程轮流进入临界区。违背进程同步机制中“空闲让进”原则 算法2：先判断对方进程标志的进程数组标志法 进程每次访问临界资源前，首先查看其他进程访问临界资源的标志。如果其他进程标志处于正在访问，则进程等待。 违背了“忙则等待”的同步准则 2018/12/31 《计算机操作系统》- 第4章

早期的临界区管理方法 – 软件方法 算法3：先设置自己标志的进程数组标志法 算法4：双标志法 违背了“空闲让进”的同步准则 标志flag用于表示每个进程是否访问临界资源，标志turn用于表示临界资源此时是否有对方进程在访问。 应用性非常方便的进程同步算法 在临界区访问标志算法中，出现了违背“忙则等待”或“空闲让进”准则的根本原因在于管理临界区标志要用两条指令，一条指令是看对方的标志，一条指令是设置自己的标志。 2018/12/31 《计算机操作系统》- 第4章

早期的临界区管理方法 – 硬件方法 2．硬件方法 要保证进程在执行这两条指令时不被中断，可以采取锁的方式。如果临界区没有被访问，则锁是打开的，在进程访问临界区时，只要进程一进入临界区，则系统立即上锁，直到访问临界区的进程离开临界区才打开锁。 测试锁和上锁这两个操作不能分开，否则会造成多个进程测试到锁打开而同时上锁的现象，引起冲突。 进程在执行这两个操作期间在处理器上的运行不能被中断。软件方法来解决有一定局限性和难度，现一般借助于硬件设施。 2018/12/31 《计算机操作系统》- 第4章

早期的临界区管理方法 – 硬件方法 优点： 缺点： 实现简单：只需要硬件指令就可实现。 适用性强：可用于多并发进程单CPU系统或共享内存多CPU系统。 支持多个临界区：每个临界区用单独的变量定义，对临界区的多少没有限制，可支持多个临界区。 缺点： 耗费处理器时间：采用忙等待，处理器空闲时间增多。 进程产生饥饿现象：一个进程离开临界区并唤醒阻塞等待的其它进程，可能阻塞更早的进程长期得不到唤醒，产生饥饿现象。 可能产生死锁：在单处理器系统中，进程执行特殊指令并进入临界区，拥有更高优先级的进程抢占，但得不到没有释放的临界资源，于是这两个进程发生死锁。 2018/12/31 《计算机操作系统》- 第4章

早期的临界区管理方法 – 硬件方法 （1）禁止中断方法 （2）测试并建立指令 （3）对换指令 最简单的方法 影响计算机效率 不能及时处理重要程序 在多处理器下方法失效 （2）测试并建立指令 （3）对换指令 2018/12/31 《计算机操作系统》- 第4章

本章目录 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.7 线程的同步和通信 重点与难点 2018/12/31 《计算机操作系统》- 第4章

在信号量同步机制中，有“检测”和“归还”两个重要的操作 信号量机制 信号量（semaphore）机制 解决并发进程同步的工具 在信号量同步机制中，有“检测”和“归还”两个重要的操作 荷兰语 “Proberen” 的意思为“检测”，用P操作表示； 荷兰语 “Verhogen” 的意思为“增量”，用V操作表示。“增量”即增加一个可以使用的临界资源，也就是“归还”的意思。 2018/12/31 《计算机操作系统》- 第4章

P操作表示同步进程发出的检测信号量操作，检测是否能够使用临界资源 信号量机制 P操作表示同步进程发出的检测信号量操作，检测是否能够使用临界资源 如果能使用，则检测通过，进程可以访问临界资源； 如果不能使用，则等待，直到访问临界区的进程将临界资源归还后，等待的进程才能够访问临界资源。 V操作表示访问完临界资源的进程通知等待进程已经完成了临界资源的访问，将临界资源释放。 2018/12/31 《计算机操作系统》- 第4章

信号量机制强调P操作和V操作都是原子操作。 原子操作是不可分割的操作，原语。即通常所说的“要么做，要么不做”，而不可能操作没有完成就被终止。 2018/12/31 《计算机操作系统》- 第4章

4.3.1 整型信号量 整型信号量 设S为一个需要初始化值的正整型量。对S的访问只能通过P、V操作。 P操作 4.3.1 整型信号量 整型信号量 设S为一个需要初始化值的正整型量。对S的访问只能通过P、V操作。 P操作 wait（S）： while S≤0 do no-op S:＝S－1; V操作 signal（S）： S:＝S＋1; 2018/12/31 《计算机操作系统》- 第4章

S>0，表示临界资源可以访问，P(s)中的检测语句通过，调用P(s)的进程可以访问临界资源。 整型信号量 S>0，表示临界资源可以访问，P(s)中的检测语句通过，调用P(s)的进程可以访问临界资源。 S≤0，表示有进程在访问临界资源，此时临界资源处于忙，调用P(s)的进程只能等待，直到s的值大于0，才可以访问临界资源。 2018/12/31 《计算机操作系统》- 第4章

将各进程对临界区访问置于P(mutex)和V(mutex)之间 整型信号量的应用－实现进程互斥 例4-3 输入进程和计算进程共用缓冲区，如图所示。输入 进程I和计算进程P并发执行，缓冲区是竞争访问的临界资 源，缓冲区的大小为n。用整型信号量实现进程同步。 公共缓冲区 P I 为缓冲区设置整型信号量mutex; 设mutex的初值为1 将各进程对临界区访问置于P(mutex)和V(mutex)之间 2018/12/31 《计算机操作系统》- 第4章

整型信号量的应用－实现进程互斥 Pi: /* 输入进程 */ begin while(输入未完成) Pc： /* 计算进程 */ { … P(mutex); /* 如果缓冲区装满，则等待 */ 将一批输入数据放入缓冲区; V(mutex); } end; Pc： /* 计算进程 */ begin while(计算未完成) { P(mutex); /* 如果缓冲区为空，则等待 */ 从缓冲区中拿出一批数据; V(mutex); 计算; … } end; coend; 2018/12/31 《计算机操作系统》- 第4章

整型信号量的应用－实现进程互斥 例4-3 分析： 对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 例4-3 分析： 对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。 2018/12/31 《计算机操作系统》- 第4章

整型信号量的应用－实现进程互斥 例4-3 分析： 对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 例4-3 分析： 对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。 对于计算进程： 只要缓冲区不为空，则进程能够从缓冲区中取走数据。 缓冲区是否为空，需要用P(mutex)去检测，如果P(mutex)检测通过，进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。 2018/12/31 《计算机操作系统》- 第4章

整型信号量的应用－实现进程互斥 例4-3 分析： 对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 例4-3 分析： 对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。 对于计算进程： 只要缓冲区不为空，则进程能够从缓冲区中取走数据。 缓冲区是否为空，需要用P(mutex)去检测，如果P(mutex)检测通过，进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。 对于输入进程和计算进程： 如果两个进程都能够访问缓冲区，哪个进程先访问缓冲区，关键在于哪个进程先执行P(mutex)。 先执行的进程先进入缓冲区访问；后执行P(mutex)的进程等待，直到先进入缓冲区访问的进程用V(mutex)释放缓冲区为止。 2018/12/31 《计算机操作系统》- 第4章

整型信号量的应用－实现进程同步 I 公共缓冲区 P 例4-3 在例4-3的基础上，当输入进程和计算进程之间共 用的缓冲区中只能装入一条数据时，用整型信号量实现输 入进程和计算进程的同步。 设置两个整型信号量is和ps 用于输入进程和计算进程协调访问缓冲区 初值分别设置为1和0 I 公共缓冲区 P 当缓冲区中只能装入一条数据时，输入进程每次放入一 条数据后，要等待计算进程取走数据才能再放入下一条 数据。 2018/12/31 《计算机操作系统》- 第4章

整型信号量的应用－实现进程同步 Pi: /* 输入进程 */ begin while(输入未完成) Pc： /* 计算进程 */ { … P(is); 将一批输入数据放入缓冲区; V(ps); } end; Pc： /* 计算进程 */ begin while(计算未完成) { P(ps); 从缓冲区中拿出一批数据; V(is); 计算; … } end; coend; 2018/12/31 《计算机操作系统》- 第4章

整型信号量的应用－实现进程同步 例4-4 分析： 信号量的设置是关键： 将信号量is的初值设置为1，ps的初值设置为0。 例4-4 分析： 信号量的设置是关键： 将信号量is的初值设置为1，ps的初值设置为0。 总是输入进程先进入缓冲区放入数据，计算进程先等待。 输入进程将一条数据放入缓冲区后释放ps，计算进程才能进入缓冲区取走一条数据。 对于输入进程： 如果计算进程没有进入缓冲区取走一条数据，输入进程不能再进入缓冲区放数据，因为输入进程需要计算进程释放缓冲区is。 对于计算进程： 如果没有输入进程释放缓冲区ps，计算进程不能多次连续进入缓冲区取走数据。 2018/12/31 《计算机操作系统》- 第4章

整型信号量的应用－实现进程前趋图 a,b,c,d,e,f,g:semaphore : = 0,…,0 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; S 1 2 4 3 5 6 S 1 S 2 S 3 S 4 S 5 S 6 2018/12/31 《计算机操作系统》- 第4章

在整型信号量中，P操作开始需要测试临界资源是否能够访问，即判断s≤0是否满足。 4.3.2 记录型信号量 在整型信号量中，P操作开始需要测试临界资源是否能够访问，即判断s≤0是否满足。 如果满足，表示进程不能进入临界区访问，进程此时“do nothing”，即什么都不做而等待。这时的等待没有放弃CPU执行权。这违背了“让权等待”的同步准则，造成处理器资源的浪费。 2018/12/31 《计算机操作系统》- 第4章

记录型信号量 解决忙等问题，实现让权等待 记录所有等待同一资源的进程 P操作 wait（S）： S.value＝ S.value－1 if S.value<0 then block（S,L） V操作 S.value＝ S.value＋1 if S.value≤0 then wakeup（S,L） 2018/12/31 《计算机操作系统》- 第4章

记录型信号量 理解： 记录型信号量在整型信号量的基础上进行了改进，让不能进入临界区的进程“让权等待”，即进程状态由运行转换为阻塞状态，进程进入阻塞队列中等待。 若信号量s的s.value的值为正数，该正数表示可对信号量可进行的P操作的次数，即实际可以使用的临界资源数。 若信号量s的s.value的值为负值，表示有多个进程申请临界资源，而又不能得到，在阻塞队列等待。s.value的绝对值表示在阻塞队列等待临界资源的进程个数。 2018/12/31 《计算机操作系统》- 第4章

AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集P原语为Swait AND型信号量集V原语为Ssignal 2018/12/31 《计算机操作系统》- 第4章

AND型信号量 理解： 死锁的产生？ 死锁的预防与解决？ 解决的办法是将进程所需要的资源一次性地全部分配给进程，等进程运行完后再全部一起释放。先让一个进程完成后，另一个进程才申请资源，得到资源并完成。也就是将并发的进程分为先完成进程和后完成进程。 AND型信号量集是将进程在运行中所需要的临界资源全部一次性分配给进程，等进程用完后再全部一起释放。如果进程有一个临界资源没有得到，进程也不可能推进，必须将所分配到的临界资源全部归还。即要么全部得到向前推进，要么一个也不能要而等待。这样的资源分配策略可以避免死锁。 2018/12/31 《计算机操作系统》- 第4章

4.3.4 信号量集 当进程需要申请的临界资源种类较多，每类临界资源个数较多时，如果用记录型信号量，进程每次只能一次申请或释放一个临界资源，非常麻烦。因此，引入信号量集。 2018/12/31 《计算机操作系统》- 第4章

信号量机制 整型信号量 记录型信号量 AND型信号量 信号量集 基本信号量原理 多个进程申请同一类资源 同一进程申请多个不同资源 同一进程申请多个同类资源 多个进程申请多个不同资源 信号量机制的对比 2018/12/31 《计算机操作系统》- 第4章

2 信号量机制 信号量按联系进程的关系分成二类： 公用信号量（互斥信号量） 私用信号量（同步信号量） 2 信号量机制 它为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施加P操作（即可申请资源），而由其合作进程对它施加V操作（即释放资源）。 信号量按联系进程的关系分成二类： 公用信号量（互斥信号量） 私用信号量（同步信号量） 它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均可对它施加P、V操作，即都可申请和释放该临界资源，其初始值置为1。取值意义如下： 信号量s＝1 ；表示资源空闲，可供使用。 信号量s＝0 ；表示资源已被占用，无其它进程等待。 信号量s＝-n ；表示资源已被占用，还有n个进程因等待资源而阻塞。 2018/12/31 《计算机操作系统》- 第4章

例题补充与讲解：1 知识点：进程的前趋图 题目： 思路： 已知一个求值公式如下所示，如果A、B已赋值，请画出该公式求值过程的前趋图 分辨可以并发进行的运算 保存计算的中间结果，并为每条语句命名 2018/12/31 《计算机操作系统》- 第4章

例题补充与讲解：1 2018/12/31 《计算机操作系统》- 第4章

例题补充与讲解：2 知识点：信号量的应用 题目： 思路： 设有一个作业由四个进程组成，这四个进程必须按右图的次序运行，试用P、V操作表达四个进程的同步关系。 思路： 设三个同步信号量b1、b2、b3，分别表示进程T2、T3、T4是否可以开始执行，初值为0。 2018/12/31 《计算机操作系统》- 第4章

例题补充与讲解：2 b2,b3,b4:semaphore : = 0,0,0 T1: { ... V(b2); V(b3); } T2: { P(b2); ... V(b4); } T3: { P(b3); ... V(b4); } T4: { P(b4); P(b4); ... } （因在T2和T3中都对b4做了V操作，所以T4要用两个P操作） 2018/12/31 《计算机操作系统》- 第4章

例题补充与讲解：3 进程P1 进程P2 y = 1; y = y + 2; V(S1); z = y + 1; P(S2); y = z + y; 进程P2 x = 1; x = x + 1; P(S1); x = y + x; V(S2); z = x + z; 知识点：信号量的应用 题目： 设有两个优先级相同的进程P1和P2如下，信号量S1和S2的初值为0。请问P1、P2并发执行结束后，x、y、z的值分别是多少？ 思路： P1和P2具有相同的优先级，并发，具有顺序的不确定性； 信号量S1和S2使得语句的执行顺序具有了制约关系 绘制对应的前趋图 2018/12/31 《计算机操作系统》- 第4章

例题补充与讲解：3 进程P1 进程P2 S1: y = 1; S2: y = y + 2; V(S1); S3: z = y + 1; S4: y = z + y; 进程P2 S5: x = 1; S6: x = x + 1; P(S1); S7: x = y + x; V(S2); S8: z = x + z; x = 5; y = 12; z = 9 2018/12/31 《计算机操作系统》- 第4章

提问环节－关于临界区的管理 软件方法 硬件方法 信号量机制 整型信号量 记录型信号量 AND型信号量 信号量集 临界区标志法 基本信号量原理 进程数组标志法1 进程数组标志法2 双标志法 硬件方法 缺陷 信号量机制 整型信号量 基本信号量原理 记录型信号量 多个进程申请同一类资源 AND型信号量 同一进程申请多个不同资源 信号量集 同一进程申请多个同类资源 多个进程申请多个不同资源 2018/12/31 《计算机操作系统》- 第4章

本章目录 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 生产者－消费者问题 读者－写者问题 哲学家就餐问题 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.7 线程的同步和通信 重点与难点 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 假设缓冲池中有n个缓冲区，每个缓冲区存放一个消息； 可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问； 利用empty和full计数信号量分别表示空缓冲及满缓冲的数量。 又假定这些生产者和消费者互相等效，只要缓冲池未满，生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。 同步问题： 生产者：P进程不能往“满”的缓冲区中放产品； 消费者：C进程不能从“空”的缓冲区中取产品。 2018/12/31 《计算机操作系统》- 第4章

同步与互斥问题 互斥信号量 mutex：防止多个进程同时进入临界区 同步信号量 empty和full：保证事件发生的顺序 缓冲区满时，Producer停止运行 缓冲区空时，Consumer停止运行 概念差别——互斥与同步（并发的两个要素） 互斥：保护临界区，防止多个进程同时进入 同步：保证进程运行的顺序合理 2018/12/31 《计算机操作系统》- 第4章

同步/互斥信号量的使用方法 互斥信号量 同步信号量 同步信号量和互斥信号量的操作顺序 必定成对出现： 进入临界区——临界区——退出临界区 未必成对出现，依赖于同步关系的性质 同步信号量和互斥信号量的操作顺序 基本原则：互斥信号量永远紧邻临界区 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 生产者P： 消费者C: Wait(empty); Wait(mutex); Buffer(in)=nextp; mutex,full,empty:semaphore mutex :=1; full:=0; empty:=n; 生产者P： Wait(empty); Wait(mutex); Buffer(in)=nextp; in:=(in+1) mod n; Signal(mutex); Signal(full); 消费者C: Wait(full); Wait(mutex); netxc=buffer(out); out:=(out+1) mod n; Signal(mutex); Signal(empty); 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 P： Wait(empty); empty=n full=0 Wait(mutex); mutex=1 Buffer(in)=nextp; in:=(in+1) mod n; Signal(mutex); Signal(full); empty=n full=0 mutex=1 in,out=0 生产者和消费者之间的约束：临界区。 生产者在生产时，消费者不能消费。 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 P： Wait(empty); empty=n full=0 Wait(mutex); mutex=1 Buffer(in)=nextp; in:=(in+1) mod n; Signal(mutex); Signal(full); empty=n full=0 mutex=1 in,out=0 控制： 缓冲区满时不能继续生产，制约生产者进程P。 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 C： empty=n Wait(full); full=0 Wait(mutex); mutex=1 netxc=buffer(out); out:=(out+1) mod n; Signal(mutex); Signal(empty); empty=n full=0 mutex=1 in,out=0 生产者和消费者之间的约束：临界区。 生产者在生产时，消费者不能消费。 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 C： empty=n Wait(full); full=0 Wait(mutex); mutex=1 netxc=buffer(out); out:=(out+1) mod n; Signal(mutex); Signal(empty); empty=n full=0 mutex=1 in,out=0 控制： 缓冲区空时不能继续消费，制约消费者进程C。 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 说明 P： C： wait和signal操作成对出现； 对资源信号量的wait操作在前 对互斥信号量的wait操作在后 Wait(empty); Wait(mutex); Buffer(in)=nextp; in:=(in+1) mod n; Signal(mutex); Signal(full); C： Wait(full); Wait(mutex); netxc=buffer(out); out:=(out+1) mod n; Signal(mutex); Signal(empty); 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 P： P： Wait(empty); Wait(mutex); Buffer(in)=nextp; in:=(in+1) mod n; Signal(mutex); Signal(full); 用AND型信号量解决同一问题 P： Wait(empty,mutex); Buffer(in)=nextp; in:=(in+1) mod n; Signal(mutex,full); 2018/12/31 《计算机操作系统》- 第4章

生产者-消费者问题 C： C： Wait(full); Wait(mutex); netxc=buffer(out); out:=(out+1) mod n; Signal(mutex); Signal(empty); 用AND型信号量解决同一问题 C： Wait(full,mutex); netxc=buffer(out); out:=(out+1) mod n; Signal(mutex,empty); 2018/12/31 《计算机操作系统》- 第4章

读者-写者问题 有两组并发进程: 要求： 读者和写者,共享一组数据区 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作 2018/12/31 《计算机操作系统》- 第4章

信号量描述 互斥关系分析 同步关系分析 读者和写者不能同时进入共享数据区 多个写者不能同时进入共享数据区 多个读者可以同时进入共享数据区 读者进入缓冲区，写者必须等待 写者进入缓冲区，读者必须等待 读者优先：一旦有读者进入后续读者均可进入 合理顺序：读者在先来的写者之后 写者优先：只要有写者等待后续读者必须等待 2018/12/31 《计算机操作系统》- 第4章

信号量描述 如果读者来： 如果写者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待 2018/12/31 《计算机操作系统》- 第4章

读者-写者问题 两个进程： Readcount：正在读取的进程数目 Reader、Writer 读者与写者间的互斥信号量：Wmutex＝1 多个读者间的互斥信号量：Rmutex＝1 Readcount：正在读取的进程数目 Readcount＝0时允许写 2018/12/31 《计算机操作系统》- 第4章

读者-写者问题 wait(rmutex); If readcount=0 then wait(wmutex); Readcount:=readcount+1; signal(rmutex); ……执行读取操作 Readcount:=readcount-1 if readcount=0 then signal(wmutex); 读者部分 2018/12/31 《计算机操作系统》- 第4章

读者-写者问题 wait(wmutex); ……执行写操作 signal(wmutex); 写者部分 2018/12/31 《计算机操作系统》- 第4章

增加限制条件，即同时读取的读者数不能超过RN L,mx:=RN,1 信号量集： 读者-写者问题 增加限制条件，即同时读取的读者数不能超过RN L,mx:=RN,1 信号量集： Swait(S,d,t); Ssignal(S,d) S为信号量，d为需求量，t为下限值 读者： Swait(L,1,1); Swait(mx,1,0); ……执行读取操作 Ssignal(L,1); 写者： Swait(mx,1,1;L,RN,0); ……执行写操作 Ssignal(mx,1); 2018/12/31 《计算机操作系统》- 第4章

读者优先的信号量解法 Reader进程 While(TRUE) { P(mutex); rcount++; if(rcount == 1) P(write); V(mutex); Read_Action(); rcount--; if(rcount == 0) V(write); } Writer进程 While(TRUE) { P(Write); Write_Action(); V(write); } typedef int semph semph mutex = 1; semph write = 1; int rcount = 0; 2018/12/31 《计算机操作系统》- 第4章

合理顺序的信号量解法 Reader进程 While(TRUE) { P(concur); P(rmutex); rcount++; if(rcount == 1) P(write); V(rmutex); V(concur); Read_Action(); P(mutex); rcount--; if(rcount == 0) V(write); V(mutex); } Writer进程 While(TRUE) { P(wmutex); wcount++; if(wcount == 1) P(concur); V(wmutex); P(Write); Write_Action(); V(write); wcount--; if(wcount == 0) V(concur); } typedef int semph semph rmutex = 1; semph wmutex = 1 semph write = 1; semph concur = 1; int rcount = 0; int wcount = 0; 2018/12/31 《计算机操作系统》- 第4章

哲学家就餐问题 互斥关系分析 同步关系分析 特殊情况考虑 筷子：同一时刻只能有一个哲学家拿起筷子 就餐：只有获得两个筷子后才能进餐 死锁：如果每个哲学家都拿起一只筷子，都饿死 并行程度：五只筷子允许两人同时进餐 2018/12/31 《计算机操作系统》- 第4章

哲学家就餐问题的直观解法 思考1：这样的解法有何问题？ 思考2：对左右的叉子是否可用进行验证，这样的修改有何优缺点？ 哲学家进程 #define N 5 void philosopher(int i) { While(TRUE) think（）； take_forks(i); take_forks((i + 1) % N); eat(); put_forks(i); put_forks((i + 1) % N); } 思考1：这样的解法有何问题？ 思考2：对左右的叉子是否可用进行验证，这样的修改有何优缺点？ 思考3：需要引入几个信号量才能实现最优化的解法呢？ 2018/12/31 《计算机操作系统》- 第4章

哲学家就餐问题 为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子； 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之； 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿。 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：1 题目： 分析： 变量设置： 进程描述： dish：表示盘子是否为空，初值=1； apple：表示盘中是否有苹果，初值=0； banana：表示盘中是否有香蕉，初值=0。 题目： 桌上有一个盘子，可以存放一个水果。父亲总是把苹果放在盘子中，母亲总是把香蕉放在盘子中；一个儿子专等吃盘中的香蕉，一个女儿专等吃盘中的苹果。 分析： 四人公用一个盘子； 盘子每次只能放一个水果，当盘子为空时，父母均可尝试放水果，但一次只能有一人成功； 盘中是香蕉，儿子吃，女儿等； 盘中是苹果，女儿吃，儿子等。 进程描述： Father：父亲放置水果的进程； Mother：母亲放置水果的进程； Son：儿子吃水果的进程； Daughter：女儿吃水果的进程。 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：1 dish：盘子是否为空，1 apple：盘中是否有苹果，0 banana：盘中是否有香蕉，0 Father: P ( dish ); 将苹果放入盘中； V ( apple ); Son: P ( banana ); 从盘中取出香蕉； V ( dish ); 吃香蕉； Mother: P ( dish ); 将香蕉放入盘中； V ( banana ); Daughter: P ( apple ); 从盘中取出苹果； V ( dish ); 吃苹果； 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：2 题目： 分析： 变量设置： 进程描述： mutex1：用于实现对水井的互斥使用，初值=1； mutex2：用于实现对水缸的互斥使用，初值=1； empty：用于记录水缸还可以装入的桶数，初值=10； full：用于记录水缸中已装入的桶数，初值=0； count：用于记录可用水桶数，初值=3。 题目： 水入缸供老和尚饮用。水缸可容纳10桶水。水井很窄，每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可同时进行。请给出取水、入水的算法描述。 取水：从井中取水，从缸中取水 入水：水倒入缸中 分析： 水缸和水井互斥，即水井每次容纳一个水桶进出，水缸也是如此；井中取水、倒水入缸、取水出缸，每次用水桶1个；水缸中可以装水10桶。 进程描述： Get：从井中取水入缸； Use：从缸中取水饮用。 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：2 mutex1：对水井的互斥使用，1 mutex2：对水缸的互斥使用，1 empty：缸可以装入的桶数，10 full：缸中已装入的桶数，0 count：可用水桶数，3 进程同步应用示例讲解：2 Get: P ( empty ); P ( count ); P ( mutex1 ); 井中取水； V ( mutex1 ); P ( mutex2 ); 倒水入缸； V ( mutex2 ); V ( count ); V ( full ); Use: P ( full ); P ( count ); P ( mutex2 ); 缸中取水； V ( mutex2 ); V ( empty ); V ( count ); 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：3 题目： 有一座桥如图所示，车流如图中箭头所示。桥上不允许两车交会，但允许同方向多辆车依次通行（即桥上可以有多个同方向的车）。 用P、V操作实现交通管理，以防止桥上堵塞。 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：3 分析： 车辆过桥时，提出过桥申请，如桥上无对方车辆则过桥； 若该车为本方向第一辆车，应阻塞对方车辆过桥； 当本方向无车辆过桥时，允许对方车辆过桥； 同方向的多辆车可依次过桥，如果对方提出过桥申请，则阻塞本方向后续车辆过桥，待桥上车辆过完后，对方车辆过桥。 同方向车辆的控制类似于读者-写者问题 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：3 进程描述： 变量设置： North、South：分别代表北方、南方车辆过桥的进程 mutexN：用于实现北方车辆互斥访问变量countN，初值=1； mutexS：用于实现南方车辆互斥访问变量countS，初值=1； wait：用于实现双方申请过桥车辆的排队，初值=1； countN：用于记录当前北方正在过桥及已申请过桥的车辆数，初值=0； countS：用于记录当前南方正在过桥及已申请过桥的车辆数，初值=0； 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：3 mutexN：北方车辆互斥访问变量countN，1 mutexS：南方车辆互斥访问变量countS，1 wait：双方申请过桥车辆的排队，1 countN：北方正在过桥及已申请过桥的车辆数，0 countS：南方正在过桥及已申请过桥的车辆数，0 进程同步应用示例讲解：3 North: P ( wait ); P ( mutexN ); if (countN==0) P( mutexS)//本方向第一辆车，阻塞对方车辆过桥 countN ++； V ( mutexN ); V ( wait ); 车辆过桥； countN --； if (countN==0) V( mutexS)//本方向最后一辆车允许对方车辆过桥 2018/12/31 《计算机操作系统》- 第4章

进程同步应用示例讲解：3 mutexN：北方车辆互斥访问变量countN，1 mutexS：南方车辆互斥访问变量countS，1 wait：双方申请过桥车辆的排队，1 countN：北方正在过桥及已申请过桥的车辆数，0 countS：南方正在过桥及已申请过桥的车辆数，0 进程同步应用示例讲解：3 South: P ( wait ); P ( mutexS ); if (countS==0) P( mutexNS)//本方向第一辆车，阻塞对方车辆过桥 countS ++； V ( mutexS ); V ( wait ); 车辆过桥； countS --； if (countS==0) V( mutexN)//本方向最后一辆车允许对方车辆过桥 2018/12/31 《计算机操作系统》- 第4章

本章目录 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.7 线程的同步和通信 2018/12/31 《计算机操作系统》- 第4章

用管程解决同步问题比用信号量解决同步问题更加简单。 管程机制作为同步工具，便于在高级语言编程中实现。 4.5 管程 管程(monitor)：新的同步机制 用管程解决同步问题比用信号量解决同步问题更加简单。 管程机制作为同步工具，便于在高级语言编程中实现。 2018/12/31 《计算机操作系统》- 第4章

信号量实现进程同步，P、V操作随临界资源的访问分散在各个进程中，编写程序时容易造成P、V操作的顺序混乱而出现进程死锁。 4.5.1 管程的定义 信号量实现进程同步，P、V操作随临界资源的访问分散在各个进程中，编写程序时容易造成P、V操作的顺序混乱而出现进程死锁。 用管程实现进程同步，可将对临界资源的操作集中在一起，以过程调用的形式提供给访问临界资源的进程使用。 2018/12/31 《计算机操作系统》- 第4章

只有进入管理的进程才有机会访问临界资源，管程忽略临界资源的内部结构形式和实现细节。 管程的定义 只有进入管理的进程才有机会访问临界资源，管程忽略临界资源的内部结构形式和实现细节。 管程的定义：一组数据结构和数据结构上的一组相关操作被称为管程。 一个管程定义了一个数据结构和能为并发进程所执行的在该数据结构上的一组操作。 2018/12/31 《计算机操作系统》- 第4章

访问完临界资源的进程需要唤醒阻塞等待同一资源的进程 管程的特点 管程保护了管程中的信息 只有定义在数据结构上的管程所提供的过程才能访问该数据结构。 并发进程互斥调用管程提供的过程 任一时刻，只有一个进程能调用管程提供的过程 任一时刻，在管程中只能有一个进程运行 访问完临界资源的进程需要唤醒阻塞等待同一资源的进程 2018/12/31 《计算机操作系统》- 第4章

管程的结构 管程只有一个入口和一个出口 并发进程在管程外等待调用管程中的过程 如果进程在管程中不能访问临界资源，则在管程中阻塞等待访问完临界资源的进程将其唤醒 2018/12/31 《计算机操作系统》- 第4章

管程的定义 管程是临界资源监控器。 在保护临界资源前提下，控制对临界资源的访问 type <管程名> = monitor <管程变量说明>； define <能被其他模块引用的过程名列表>； use <(要引用的模块外定义的)过程名列表>； procedure <过程名>（<形式参数表>）； begin <过程体>； end； … <管程的局部数据初始化语句>； 管程是临界资源监控器。 在保护临界资源前提下，控制对临界资源的访问 define定义的过程，可以被进程或其他管程模块引用，而未定义的过程则仅在管程内部使用。 管程要引用模块外定义过程，必须用use说明。 2018/12/31 《计算机操作系统》- 第4章

若干进程互斥共享1个临界资源时，管程的定义 管程中用define子句声明(可以在模块外引用)：申请get和释放put两个过程，分别表示进入管程过程和退出管程过程。 管程中用use子句声明(模块外定义的操作): PP(condition)和VV(condition) 两个原子操作 操作PP(condition)表示进入管程的进程在不能访问临界资源时，在条件condition上阻塞等待临界资源。 操作VV(condition)表示访问完临界资源的进程释放临界资源时，唤醒在条件condition上阻塞等待所释放的临界资源的进程。 2018/12/31 《计算机操作系统》- 第4章

procedure get /* 进入管程的过程调用 */ begin type MS = MONITOR var busy； var condition; define get， put; use PP，VV; procedure get /* 进入管程的过程调用 */ begin if busy then PP(condition)； /* 如果临界资源忙时，进程调用PP阻塞*/ busy：=true； end； procedure put /* 退出管程的过程调用 */ busy：=false； /* 将临界资源的状态设置为闲 */ VV(condition)； /* 唤醒阻塞等待所释放临界资源的进程 */ begin /* 管程变量初始化 */ busy：=false； 2018/12/31 《计算机操作系统》- 第4章

4.5.2 Hoare和Hansen观点 现象：在管程中的进程，在某一条件变量condition上执行操作VV后，如果在管程中有进程处于阻塞等待该进程释放的临界资源，则执行操作VV的进程会唤醒该阻塞进程。执行操作VV的进程和被唤醒的进程，会同时调用管程中的过程。因此，执行操作VV(condition)的进程正调用管程的退出过程，而被操作VV(condition)唤醒的过程正调用管程的进入过程。而根据管程的互斥访问条件，不允许两个进程同时访问管程中的进程。 为了防止这种现象的发生，Hoare和Hanse提出了两种不同的观点。 2018/12/31 《计算机操作系统》- 第4章

Hoare观点 操作VV是管程的过程中的最后一个操作。 如果一个阻塞进程P1在阻塞等待被唤醒时，进程P2发出了唤醒进程P1的操作VV，则进程P1被唤醒后立即恢复在管程中执行，同时进程P2用操作PP阻塞自己。当进程P1访问完管程中的临界资源，结束对管程中的过程调用或被其它条件阻塞时，进程P2才被进程P1用操作VV唤醒并恢复调用管程中的过程。 2018/12/31 《计算机操作系统》- 第4章

Hansen观点 进程P1在阻塞等待被唤醒时，进程P2发出了唤醒进程P1的操作VV，进程P2继续执行的同时，条件被保存。当进程P2离开管程时，进程P1才会通过重新检查条件来试图恢复在管程中的执行。 2018/12/31 《计算机操作系统》- 第4章

Hansen管程方法实现生产者—消费者问题 4.5.3 管程的应用 Hansen管程方法实现生产者—消费者问题 在管程中定义变量notfull和notempty作为调用管程中过程的条件，认为只要生产者可以生产，则notfull的值为true；只要消费者可以消费，则notempty的值为true。 用Hansen管程方法实现读者—写者问题 用两个计数器rc和wc分别对读者进程和写者进程计数； 用R和W表示允许读和写的条件； 2018/12/31 《计算机操作系统》- 第4章

本章目录 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.7 线程的同步和通信 2018/12/31 《计算机操作系统》- 第4章

进程通信的类型 共享存储器系统 消息传递系统 管道（Pipe）通信 基于共享数据结构的通信方式 基于共享存储区的通信方式 直接通信方式 间接通信方式 管道（Pipe）通信 共享文件 2018/12/31 《计算机操作系统》- 第4章

进程通信的类型 共享存储器系统 步骤 评价 基于共享数据结构的通信方式 基于共享存储区的通信方式 向操作系统申请共享存储区 挂接共享存储区到进程的存储空间 需要进程互斥读写存储区 通信结束后归还存储区 评价 适合进程之间通信量大的情况下 优点是高效、快速 2018/12/31 《计算机操作系统》- 第4章

进程通信的类型 消息结构与消息原语 共享存储器系统 消息传递系统 管道（Pipe）通信 直接通信方式 引入该方法的PCB问题描述 消息由消息头和消息体组成。消息头包括发送进程标志、指向消息队列中下一个消息的指针和消息长度。消息正文是消息体。 共享存储器系统 基于共享数据结构的通信方式 基于共享存储区的通信方式 消息传递系统 直接通信方式 间接通信方式 管道（Pipe）通信 共享文件 直接通信方式 Send(Receiver,message) 发送一个消息给接收进程 Receive(Sender,message) 接收Sender发来的消息 引入该方法的PCB问题描述 2018/12/31 《计算机操作系统》- 第4章

消息传递系统--直接通信方式 首先调用“寻找目标进程的PCB”的程序查找接收进程的PCB，如果接收进程存在，申请一个存放消息的缓冲区，消息缓冲区为空时，接收此消息的进程因等待此消息的到来而处于阻塞状态，则唤醒此进程，并把消息的内容、发送原语的进程名和消息等，复制到预先申请的存放消息的缓冲区，且将存放消息的缓冲区连接到接收进程的PCB上；如果接收进程不存在，则由系统给出一个“哑”回答；最后控制返回到发送消息的进程继续执行，或转入进程调度程序重新分配处理机。 2018/12/31 《计算机操作系统》- 第4章

进程通信的类型 间接通信方式 共享存储器系统 消息传递系统 管道（Pipe）通信 消息传递的相关问题 通过作为共享数据结构的实体（即信箱） 私用信箱 公用信箱 共享信箱 进程通信的类型 共享存储器系统 基于共享数据结构的通信方式 基于共享存储区的通信方式 消息传递系统 直接通信方式 间接通信方式 管道（Pipe）通信 共享文件 一对一关系 多对一关系 一对多关系 多对多关系 消息传递的相关问题 通信链路 消息的格式 进程同步方式 2018/12/31 《计算机操作系统》- 第4章

消息缓冲队列 2018/12/31 《计算机操作系统》- 第4章

进程通信的类型 共享存储器系统 消息传递系统 管道（Pipe）通信 基于共享数据结构的通信方式 基于共享存储区的通信方式 直接通信方式 间接通信方式 管道（Pipe）通信 共享文件 2018/12/31 《计算机操作系统》- 第4章

进程通信的类型 基本原理 共享存储器系统 消息传递系统 管道（Pipe）通信 特点 借助于一个特殊的共享文件连接发送进程和接收进程。发送进程向管道写入信息，接收进程从管道读信息。 是一种单向的传递信息方式，先进入管道的信息首先从管道中流出。发送进程只能写入信息，接收进程只能接收信息。 从实现机理上说，就是发送进程将发送的信息写入文件，接收进程从文件中读出信息。因此管道需要作为文件引用。 进程通信的类型 共享存储器系统 基于共享数据结构的通信方式 基于共享存储区的通信方式 消息传递系统 直接通信方式 间接通信方式 管道（Pipe）通信 共享文件 特点 在通信前需要创建管道 利用管道通信的进程双方需要同步 2018/12/31 《计算机操作系统》- 第4章

UNIX的管道 类别 无名管道：是操作系统提供的资源，可以被所有的进程使用。限制：每次打开管道的进程，只能是与自己进程相关的进程（子进程）共享对管道的操作，完成相互之间的通信。 有名管道：克服无名管道使用上的限制，所有的进程都可以共享对管道的操作，相互之间通过管道通信。 2018/12/31 《计算机操作系统》- 第4章

本章目录 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.1 进程并发 4.2 临界区管理 4.3 信号量机制 4.4 用信号量解决经典进程同步问题 4.5 管程 4.6 进程通信 4.7 线程的同步和通信 2018/12/31 《计算机操作系统》- 第4章

线程之间的同步 机制： 机制1：互斥锁 互斥锁、条件变量、信号量 用于线程之间对互斥共享资源竞争访问的同步机制。 互斥锁的操作开销低，实施简单，适合用于访问频率 高的环境。 同一进程中的线程，共享进程的地址空间，对进程的 数据和程序段访问频率高。对这样的线程，适合用互 斥锁机制实现线程之间的同步。 互斥锁存在两个状态：开锁（unlock）和关锁 （lock），可以用两条命令对互斥锁进行操作。其中 的lock操作相当于将访问的数据段关上，unlock操作 相当于将访问的数据段打开。 2018/12/31 《计算机操作系统》- 第4章

线程之间的同步 机制2：条件变量 针对互斥锁用于线程同步时可能造成的死锁问题，引入了条件变量，将条件变量与互斥锁结合使用 占有资源的线程在使用完资源后，按照右边的描述释放该资源，用wakeup(condition variable)语句唤醒所有指定变量上的阻塞线程。这样，在同一条件下阻塞的所有线程都被唤醒，避免了同一变量下的线程死锁。 lock mutex /* mutex为互斥锁*/ lock mutex check data structures; mark resources as free; while (resources busy); unlock mutex; wait(condition variable); wakeup(condition variable); mark resources as busy; unlock mutex; 2018/12/31 《计算机操作系统》- 第4章

线程之间的同步 机制3：信号量 在进程同步下的信号量机制同样可以用于线程同步，只是为了提高效率，需要分别向进程和线程设置相应的信号量。 私有信号量 公有信号量 2018/12/31 《计算机操作系统》- 第4章

线程之间的同步 机制3：信号量 在进程同步下的信号量机制同样可以用于线程同步，只是为了提高效率，需要分别向进程和线程设置相应的信号量。 私有信号量用于同一进程中的线程同步时。私有信号量的数据结构存放在线程所在进程的地址空间中，为进程所拥有，可以被同一进程的所有线程使用。 由于操作系统并不知道私有信号量的存在，所以，一旦发生私有信号量的占有者结束占有，而没有释放私有信号量占用的空间，操作系统无法对该空间清0，也不能将其传送给下一个请求它的线程。 机制3：信号量 在进程同步下的信号量机制同样可以用于线程同步，只是为了提高效率，需要分别向进程和线程设置相应的信号量。 私有信号量 公有信号量 公有信号量既可用于不同进程之间的线程，又可用于同一进程的线程。公有信号量的数据结构存放在操作系统存储空间，由操作系统管理。 与私有信号量不同，如果信号量的占有者在结束时没有释放该公有信号量，操作系统会自行回收信号量占用的空间，并通知下一进程。因此，公有信号量是一种安全的同步机制。 2018/12/31 《计算机操作系统》- 第4章

线程之间的通信 机制： 共享存储区通信 线程之间的通信与进程之间的通信非常相似，可以用共享存储区通信、消息通信和管道通信。 该方式对于线程通信，特别是同一进程的线程之间的通信极具优势。 属于同一进程的线程，由于共享进程的地址空间，线程之间的通信可以利用这样的优势。通信的线程双方可以将发送或接收的信息放到共享的进程地址空间。 需要注意的是，对该共享空间的访问需要采取线程同步措施，如可以用互斥锁，也可以用信号量。 2018/12/31 《计算机操作系统》- 第4章

本章小结 两大部分内容： 进程同步： 进程同步 进程通信 用于解决并发进程之间的互斥与协作关系问题 实现方法：硬件方法和软件方法，其中信号量机制和管程机制是解决进程同步的有效工具 2018/12/31 《计算机操作系统》- 第4章

本章小结（续） 信号量机制： 通过信号量和P、V操作，既能够使并发进程对临界资源的访问做到访问、等待的形式，消除了相互的竞争，又能够使需要协作的进程协调执行顺序、相互配合向前推进。 管程机制： 通过对临界资源的隐藏，以过程调用形式提供给并发进程应用，系统限制一次只能一个并发进程对过程进行调用，避免了并发进程之间对临界资源访问的竞争，适用于存在多种临界资源的复杂环境下的进程同步问题。 2018/12/31 《计算机操作系统》- 第4章

本章小结（续） 进程通信： 三种通信方式：共享存储区通信、消息通信和管道 通信 这三种通信方式适合在进程之间需要通信信息量大的环境下 三种通信方式：共享存储区通信、消息通信和管道 通信 这三种通信方式适合在进程之间需要通信信息量大的环境下 共享存储区通信快捷、可靠 消息通信实现容易、灵活 管道通信方便、直接 2018/12/31 《计算机操作系统》- 第4章

本章小结（续） 在UNIX操作系统和Windows操作系统中，管道通信既适合进程之间的通信，又适合线程之间的通信 操作系统提供有无名管道和有名管道两种通信形式，操作系统环境为程序开发提供了有力支持 2018/12/31 《计算机操作系统》- 第4章

作业通过发送电子邮件附件形式提交到到助教老师邮箱： 练习 4.15，4.17，4.18 作业通过发送电子邮件附件形式提交到到助教老师邮箱： 谢昭阳 1183135172@qq.com (周二) 赵 静 1215052241@qq.com (周四) 作业文件名命名要求： OS_学号_姓名_n.doc （n为当章节序号） 如一个合法文件名： OS_95002_张三_4.doc 2018/12/31 《计算机操作系统》- 第4章

Any Question? Thank you ! 2018/12/31 《计算机操作系统》- 第4章