第四章 并发与同步
1. 进程同步与进程互斥
进程同步：指多个进程中发生的事件存在某种时序关系，必须协同动作，相互配合，以共同完成一个任务。
进程互斥： 指由于共享资源所要求的排他性，进程间要相互竞争，以使用这些互斥资源。
2. 进程互斥解决方法
进程互斥的解决有两种做法：一是由竞争各方平等协商；二是引入进程管理者，由管理者来协调竞争各方对互斥资源的使用。
3. 资源共享 3 个层次
互斥（ MutualExclusion）：保证资源的互斥使用是指多个进程不能同时使用同一个资源，这是正确使用资源的最基本要求；
死锁（ Deadlock）：避免死锁是指避免多个进程互不相让，避免出现都得不到足够资源的情况，从而保证系统功能的正常运行；
饥饿（ Starvation）：避免饥饿是指避免某些进程一直得不到资源或得到资源的概率很小，从而保障系统内资源使用的公平性。
4. 相互感知度划分：
相互感知的程度 | 交互关系 | 一个进程对其他进程的影响 | 潜在的控制问题 |
相互不感知（完全不了解 其他进程的存在） | 竞争 （ Competition） | 一个进程的操作对其他进 程的结果无影响 | 互斥、死锁、饥饿 |
间接感知（双方都与第 3 方交互，如共享资源） | 通过共享进行协作 | 一个进程的结果依赖于从其他进程获得的信息 |
互斥、死锁、饥饿 |
直接感知（ 双方直接交互，如通信） | 通过通信进行协作 | 一个进程的结果依赖于从其他进程获得的信息 | 死锁、饥饿 |
5. 临界资源的访问过程
● 进入区（ Entry Section）：为了进入临界区使用临界资源，在进入区要检查可否进入临界区；如果可以进入临界区，通常设置相应的“ 正在访问临界区” 标志， 以阻止其他进程同时进入临界区。
● 临界区（Critical Section）： 进程中访问临界资源的一段代码。
● 退出区（Exitt Section）： 将“ 正在访问临界区” 标志清除。
● 剩余区（Remainder Section）： 代码中的其余部分。 6.进程同步机制准则
空闲则入:任何同步机制都必须保证任何时刻最多只有一个进程位于临界区。当有进程位于临界区时，任何其他进程均不能进入临界区。
忙则等待：当已有进程处于其临界区时，后到达的进程只能在进入区等待。
有限等待：为了避免死锁等现象的出现，等待进入临界区的进程不能无限期地“ 死等”。
让权等待：因在进入区等待而不能进入临界区的进程，应释放处理机，转换到阻塞状态，以使得其他进程有机会得到处理机的使用权。
7. 进程互斥的硬件方法
目前，在平等协商时通常利用某些硬件指令来实现进程互斥。硬件方法的主要思路是用一条指令完成读和写两个操作，因而保证读操作与写操作不被打断。依据所采用的指令的不同，硬件方法分成 TS 指令和 Swap 指令两种。
TS(Test-and-Set)指令
TS 指令的功能是读出指定标志后把该标志设置为 TRUE。TS 指令的功能可描述成下面的函数。
Boolean TS (Boolean * lock) {
Boolean old； old=*lock； lock=TRUE； return old；
}
利用 TS 指令实现的进程互斥算法是，每个临界资源设置一个公共布尔变量 lock，表示资源的两种状态： TRUE 表示正被占用， FALSE 表示空闲， 初值为 FALSE。在进入区利用 TS 进行检查和修改标志 lock。有进程在临界区时，重复检查，直到其他进程退出时检查通过。所有要访问临界资源的进程的进入区和退出区代码是相同的。
TS 指令实现互斥的算法是：
① 测试锁变量的值，如为 1，则重复执行本命令，不断重复测试变量的值；
② 如为 0，则立即将锁变量测值置为 1，进入临界区；
③ 测试并设置指令是一条完整的指令，而在一条指令的执行中间是不会被中断的，保证了锁的测试和关闭的连续性；
④ 退出临界区时，将锁变量测试值设为 0。2）Swap 指令（或 Exchange 指令）
Swap 指令的功能是交换两个字（ 字节） 的内容。可用下面的函数描述 Swap 指令的功能。
Void SWAP(int*a, int*b){
Int temp；
temp=*a; *a=* b;*b =temp；
}
利用 Swap 指令实现的进程互斥算法是， 每个临界资源设置一个公共布尔变量 lock,初值为 FALSE;每个进程设置一个私有布尔变量 key,用于与 lock 间的信息交换在进入区利用 Swap 指令交换 lock 与 key 的内容，然后检查 key 的状态;有进程在临界区时， 重复交换和检查过程， 直到其他进程退出时检查通过。
8.硬件方法优缺点
使用硬件方法实现进程互斥，
1) 优点有以下几个方面：
使用范围广：硬件方法适用于任意数目的进程，在单处理器和多处理器环境中完全相同；
简单：硬件方法的标志设置简单、含义明确，容易验证其正确性；
支持多个临界区：在一个进程内有多个临界区时，只需为每个临界区设立一个布尔变量；
2) 其缺点有：
进程在等待进入临界区时，要耗费处理机时间，不能实现“让权等待”；
由于进入临界区的进程是从等待进程中随机选择的，有的进程可能一直选不上，从而导致“饥饿”。
9.信号量
信号量是由操作系统提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。属于低级通信方法
empty 信号量表明的是空闲资源数目；
full 信号量表明的是满的资源数目；
mutex 信号量用于实现互斥访问。
10.PV 操作
1) PV 操作由P 操作原语和V 操作原语组成（原语是不可中断的过程）对信号量进行操作。
P（S）：将信号量 S 的值减 1，即 S=S-1；如果 S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。
V（S）：将信号量 S 的值加 1，即 S=S+1；如果 S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。
2) 优点：
P、V 原语的执行， 不受进程调度和执行的打断， 从而很好地解决了原语操作的整体性。
3) 缺点：
一个信号量只能置一次初值，以后只能对之进行 P 操作或 V 操作。信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难。
核心操作 P-V 分散在各用户程序的代码中，不易控制和管理；一旦错误，后果严重，且不易发现和纠正。
11.PV 处理过程
依据对临界区访问过程的分析，信号量机制中 P 原语相当于进入区操作， V 原语相当于退出区操作。下面来分析操作系统对这两个原语操作的处理过程。
P 原语所执行的操作可用下面函数 wait(s)来描述。wait(s)
{
-- s.count；//表示申请一个资源If (s.count <0)//表示没有空闲资源
{
调用进程进入等待队列 s.queue； 阻塞调用进程；
习 |
}
}
V 原语所执行的操作可用下面函数 signal(s)来描述。
signal(s)
{
++s.count； //表示释放一个资源if(s.count<=0)//表示有进程处于阻塞状态
{
从等待队列 s.queue 中取出头一个进程 P;
进程 P 进入就绪队列;
}
}
利用操作系统提供的信号量机制，可实现临界资源的互斥访问。
在使用信号量进行共享资源访问控制时，必须成对使用 P 和 V 原语。
遗漏 P 原语则不能保证互斥访问，遗漏 V 原语则不能在使用临界资源之后将其释放给其他等待的进程。
P、V 原语的使用不能次序错误、重复或遗漏。
12. 前趋关系
利用操作系统提供的信号量机制可实现进程间的同步，即所谓的前趋关系。
13.管程
一个管程是一个由过程、变量及数据结构等组成的集合，它们组成一个特殊的模块或软件包。
进程可在任何需要的时候调用管程中的过程，但它们不能在管程之外声明的过程中直接访问管程内的数据结构。
一个管程由 4 个部门组成：管程名称，共享数据的说明，对数据进行操作的一组过程和对共享数据赋初值的语句。
管程能保障共享资源的互斥执行。
为了保证管程共享变量的数据完整性，规定管程互斥进入;
进程间同步关系：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作， 这组操作能同步进程和改变管程中的数据。
任意时刻管程中只能有一个活跃进程， 这一特性使管程能有效地完成互斥。
14. 解决进程通信 3 类方案
解决进程之间的大量信息通信的问题有 3 类方案：共享内存、消息机制以及通过共享文件进行通信，即管道通信。
1) 共享内存
在相互通信的进程之间设有一个公共内存区，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换。
2) 消息机制
进程在运行过程中，可能需要与其他的进程进行信息交换，于是进程通过某种手段发出自己的消息或接收其他进程发来的消息。
消息缓冲区通信机制
① 消息缓冲区，这是一个由消息长度、消息正文、发送者、消息队列指针组成的数据结构。
② 消息队列首指针 m_q，一般保存在 PCB 中。
③ 互斥信号量 m_mutex，初值为 1， 用于互斥访问消息队列， 在 PCB 中设置。
④ 同步信号量 m_syn，初值为 0， 用于消息计数， 在 PCB 中设置。
为实现消息缓冲通信， 要利用发送消息原语（ send)和接收消息原语（ receive)。
① 发送消息原语 send(receiver，a)。
发送进程调用 send 原语发送消息，调用参数 receiver 为接收进程名，a 为发送进程存放消息的内存区的首地址。send 原语先申请分配一个消息缓冲区， 将由 a 指定的消息复制到缓冲区， 然后将它挂入接收进程的消息队列，最后唤醒可能因等待消息而等待的接收进程。
send 原语描述如下：send(R,M)
{
根据 R 找接收进程，如果没找到， 则出错返回; 申请空缓冲区 P(s_b);
P(b_mutex); 取空缓冲区; V(b_mutex);
把消息从 M 处复制到空缓冲区; P(m_mutex);
根据 m _ q，把缓冲区挂到接收进程的消息链链尾; V(m_mutex);
V(m_syn);
}
其中，s_b 是空缓冲区个数，初值为 n,b_mutex 是空缓冲区的互斥信号量，初值为 1。
② 接收消息原语receive(a)。
接收进程调用 receive 原语接收一条消息，调用参数 a 为接收进程的内存消息区。receive 原语从消息队列中摘下第一个消息缓冲区，并复制到参数 a 所指定的消息区，然后释放该消息缓冲区。若消息队列为空，则阻塞调 用进程。
信箱通信
以发送信件以及接收回答信件为进程间通信的基本方式。
好处： 发送方和接收方不必直接建立联系，没有处理时间上的限制。发送方可以在任何时间发信，接收方也可以在任何时间收信。
规则：
① 若发送信件时信箱已满，则发送进程应被置成“ 等信箱” 状态， 直到信箱有空时才被释放。
② 若取信件时信箱中无信，则接收进程应被置成“ 等信件” 状态， 直到有信件时才被释放。
管道通信
① 管道通信是连接两个进程之间的一个打开的共享文件， 专用于进程之间进行数据通信。
② 管道通信的基础是文件系统。
③ 在对管道文件进行读写操作的过程中，发送进程和接收进程要实施正确的同步和互斥，以确保通信的正确性。
④ 管道通信具有传送数据量大的优点，但通信速度较慢。
上一篇
第三章 进程线程模型
下一篇