第4章 并发与同步
单选题3题 多选题1题
4.1 进程间的作用
进程间的同步
- 两个程序在并发执行后，得到的共享变量的结果是不同的，其根本原因是：共享资源，使得程序的计算结果与并发程序的执行速度有关
- 多进程并发环境下，各进程之间存在相互制约关系，故需要对程序的执行顺序和速度进行控制
- 进程同步是指多个进程中发生的事件存在某种时序关系，必须协同动作，相互配合，以共同完成一个任务
- 两个并发进程包含同一共享变量
- 一个进程在等待另一 个进程向它发送消息
- 在打印数据时，读数据进程、处理数据进程和打印结果进程
- 不同的用户在各自的电脑上打同一盘网络麻将
- 汽车装配流水线上的各道工序
进程间的互斥
进程互斥是指由于共享资源所要求的排他性，进程间要互相竞争，以使用这些互斥资源
- 解决方法一：由竞争各方平等协商
- 解决方法二：由管理者来协调竞争各方对互斥资源的使用
计算机系统中资源共享的程度可分成三个层次：互斥、死锁和饥饿
相互感知的成都 交互关系 一个进程对其他进程的影响 潜在的控制问题 相互不感知（完全不了解其他进程的存在） 竞争 一个进程的操作对其他进程的结果无影响 互斥、死锁、饥饿 间接感知（双方都与第三方交互，如共享资源） 通过共享进行协作 一个进程的结果依赖于从其他进程获得的信息 互斥、死锁、饥饿 直接感知（双方直接交互，如通信） 通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息 死锁、饥饿 临界资源是指计算机系统中的需要互斥使用的硬件或软件资源，如外设、共享代码段、共享数据结构
- 进入区：为了进入临界区使用临界资源,在进入区要检查可否进入临界区
- 临界区：进程中访问临界资源的一段代码。
- 退出区：将“正在访问临界区”标志清除。
- 剩余区：代码中的其余部分。
- 在操作系统中采用的进程同步机制应遵循的准则：空闲则入、忙则等待、有限等待、让权等待
(1) 进程互斥的软件做法
- 基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志。
- 互斥算法1——单标志
- 互斥算法2——双标志、先检查
- 互斥算法3——双标志、先修改标志
- 互斥算法4——双标志、先修改、后检查、后修改者等待
(2) 进程互斥的硬件做法
- 基本思路是用一条指令完成读和写两个操作，因而保证读操作与写操作不被打断。
- 依据所采用的指令的不同，硬件方法分成TS指令和Swap指令两种。
- TS指令的功能是读出指定标志后把该标志设置为TRUE。
- 利用TS指令实现的进程互斥算法是，每个临界资源设置一个公共布尔变量lock，表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲，初值为FALSE
- 利用Swap指令实现的进程互斥算法是，每个临界资源设置一个公共布尔变量lock，初值为FALSE；每个进程设置一个私有布尔变量key，用于与lock间的信息交换。
4.2 信号量(Semaphore)
信号量的概念
- 信号量是由操作系统提供的管理公有资源的有效手段。
- 信号量是一种进程同步机制，每个信号量结构有两部分组成：
- s.count——当s.count>=0时，表示当前的空闲资源数；当s.count<0时，其绝对值表示当前等待临界区的进程数
- s.queue——存放阻塞在该信号量的各进程的标识
- 信号量使用P、V原语，其执行不被打断，从而很好地解决了原语操作的整体性
- 信号量机制中P原语相当于进入区操作，V原语相当于退出区操作。
- 利用操作系统提供的信号量机制，可实现临界资源的互斥访问。
- 为临界资源设置一个互斥信号量mutex，其初值为1
- 在每个进程中将临界区代码置于 P(mutex)和V(mutex) 原语之间。
- 在使用信号量进行共享资源访问控制时，必须成对使用P和V原语。
- 遗漏P原语则不能保证互斥访问
- 遗漏V原语则不能在使用临界资源之后将其释放给其他等待的进程。
- P、V原语的使用不能次序错误、重复或遗漏。
- 利用操作系统提供的信号量机制可实现进程间的同步，即所谓的前趋关系
经典的进程同步问题
(1) 简单生产者-消费者问题
- 生产者进程P不能往已经“满”的缓冲区中放入产品，设置信号量empty，其初值为1，用于指示空缓冲区数量
- 消费者进程Q也不能从已经“空”的缓冲区中取出产品，设置信号量full，初值为0，用于指示满缓冲区数量。
(2) 多个生产者-消费者问题
- 该环形缓冲池由k个大小相等的缓冲区组成，每个缓冲区能容纳一个产品，生产者每次往空缓冲区送个产品；消费者每次从满缓冲区取出一个产品。
- 生产者进程不断地生产产品并把它们放入缓冲池内，消费者进程不断地从缓冲池内取产品并消费之。这里既存在同步问题，也存在互斥问题。
(3) 读者-写者问题的解决方案 假定有某个共享文件F ,系统允许若干进程对文件F进行读或写。这里把要读文件的进程称为读者，把要写文件的进程称为写者。读者和写者必须遵守如下的规定：
- 多个进程可以同时读文件F
- 任一个进程在对文件F进行写时，不允许其他进程对文件进行读或写
- 当有进程正在读文件时不允许任何进程去写文件。
4.3 管程与进程通信
管程
(1) 概念及组成
- 定义
- 一个由过程、变量及数据结构等组成的集合
- 组成一个特殊的模块或软件包
- 结构
- 管程名称，共享数据的说明
- 对数据进行操作的一组过程和对共享数据赋初值的语句
- 一次只能由一个进程在管程内活动
(2) 主要特性
- 模块化：一个管程是一个基本程序单位，可以单独编译
- 抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码。
- 信息隐蔽：管程是半透明的，管程中的外部过程（函数）实现了的功能，在其外部则是不可见的。
(3) 其他特性
- 管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数） 来间接地访问管程中的共享变量
- 任一时刻管程中只能有一个活跃进程，规定管程互斥进入;
- 管程通常是用来管理资源的，在管程中应当设有进程等待队以及相应的等待及唤醒操作。
- 管程是编程语言的组成部分，可以采用与其他过程调用不同的方法来处理对管程的调用。
- 进入管程时的互斥由编译器负责，通常是用一个互斥量或二元信号量。
(4) 条件变量
- 引入条件变量以及相关的两个操作wait和signal，其目的是进程在无法继续运行时调用进程自身阻塞。
- 当一个管程过程无法继续运行时，会在某个条件变量（如fulI）上执行wait操作，导致调用进程自身阻塞，并且还将另一个以前等在管程之外的进程调入管程。
- 另一个进程可以唤醒正在睡眠的伙伴进程,可以通过对其伙伴正在等待的一个条件变量执行signal完成。
- P等待Q继续，直到Q退出或等待（Hoare提出）
- Q等待P继续，直到P等待或退出
- 规定唤醒为管程中最后一个可执行的操作（BrinchHansen提出）
(5) Pthread中的互斥与同步
解决线程互斥问题的基本思想是使用一个可以加锁和解锁的互斥量来保护临界区
一些与互斥量相关的Pthread调用
线程调用 描述 pthread_mutex_init 创建一个互斥量 pthread_mutex_destroy 撤销一个互斥量 pthread_mutex_lock 获得一个锁或阻塞 pthread_mutex_trylock 获得一个锁或失败 pthread_mutex_unlock 释放一个锁 一些与条件变量相关的Pthread调用
线程调用 描述 pthread_cond_init 创建一个条件变量 pthread_cond_destroy 撤销一个条件变量 pthread_cond_wait 阻塞以等待一个信号 pthread_cond_signal 向另一个线程发信号来唤醒它 pthread_cond_broadcast 向多个线程发信号让它们全部唤醒
- 定义
进程通信
- 低级通信
- P、V操作——无法实现大量信息的交换
- 高级通信
- 共享内存——通过共享的公共内存区
- 消息机制——类似于邮局收发信件的方式
- 管道通信——通过共享文件进行通信
(1) 共享内存
- 在相互通信的进程之间设有一个公共内存区，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换。
- 两个问题
- 怎样提供共享内存
- 公共内存中的读写互斥问题
- 操作系统一般只提供要共享的内存空间，而处理进程间在公共内存中的互斥关系则是程序开发人员的责任。
(2) 消息机制
消息缓冲通信：利用内存中公用消息缓冲区实现进程之间的信息交换
具体内容
- 消息缓冲区——由消息长度、消息正文、发送者、消息队列指针组成的数据结构
- 消息队列——首指针m_ q，一般保存在PCB中
- 互斥信号量——m_mutex初值为1，用于互斥访问消息队列，在PCB中设置
- 同步信号量——m_syn初值为0，用于消息计数，在PCB中设置
- 发送消息原语send(receiver, a)
消息缓冲通信
为实现消息缓冲通信，要利用发送消息原语(send)和接受消息原语(receive)
- 发送消息原语send(receivers)：发送进程调用send原语发送消息，调用参数receiver为接收进程名，a为发送进程存放消息的内存区的首地址。
- 接受消息原语receive(a)：接受进程调用receive原语接受一条消息，调用参数a为接受进程的内存消息区
(3) 信箱通信
- 为了实现进程间的通信，可以设立一个通信机构——信箱，以发送信件以及接收回答信件为进程间通信的基本方式。
- 一个信箱的结构可以由**“信箱说明”和“信箱体”**两部分组成。
- 信箱说明
- 可存信件数：信箱的容量大小。
- 已有信件数：信箱中已有信件的数量
- 可存信件的指针：当前可存入的封信的位置。
- 为了实现信箱通信，必须提供相应的原语，如创建信箱原语、撤销信箱原语、发送信件原语和接收信件原语等。
- 采用信箱通信的最大好处是，发送方和接收方不必直接建立联系，没有处理时间上的限制。
- 为避免信件丢失和错误地送出信件，信箱通信应有的规则：
- 若发送信件时信箱已满，则发送进程应被置成**“等信箱”**状态，直到信箱有空时才被释放
- 若取信件时信箱中无信，则接收进程应被置成**“等信件”**状态，直到有信件时才被释放
(4) 管道通信
- 管道是连接两个进程之间的一个打开的共享文件，专用于进程之间进行数据通信。
- 发送进程可以从管道一端写入数据流，每次写入的信息长度是可变的
- 接收进程在需要时可以从管道的另一端读出数据，读出单位长度也是可变的。
- 在对管道文件进行读写操作的过程中，发送进程和接收进程要实施正确的同步和互斥，以确保通信的正确性。
- 管道通信机制中的同步与互斥都由操作系统自动进行，对用户是透明的。
- 管道通信具有传送数据量大的优点，但通信速度较慢。
- 低级通信
预览: