操作系统-进程与线程（进程同步与互斥，进程互斥的软硬件实现方式）

1. 进程同步与互斥

同步：

首先进程具有异步特性，异步性是指：并发的进程各自是独立的，运行速度是不可预知的。

操作系统提供了同步的机制来控制进程运行的先后顺序。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
eg：管道文件的读取进程需要等待写进程写入才可以读取。

互斥：

临界资源：只允许一个进程使用的资源称为临界资源

临界区（临界段）：进程中访问临界资源的代码段
进入区：实现互斥的代码段（上锁）
退出区：实现互斥的代码段（解锁）

对临界资源的访问必须互斥的访问，互斥又称为间接制约关系。

进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

为了保证性能：

1. 如果临界区没有进程，则申请临界区的进程可以立即进去临界区
2. 如果临界区中有进程访问，则其他申请临界区的进程需要等待
3. 对于所有申请访问临界区的进程，需要保证在有限的时间内让其进入临界区，防止饥饿问题
4. 如果进程无法进入临界区，应该立即脱离CPU调度。防止CPU处于忙等待状态

2.进程互斥的软件实现方式

Ⅰ单标志法

思路：
每个进程访问临界区的权限只能由另一个进程提供。保证了任意时刻临界区只有一个进程访问资源
伪代码如下：

只有p0进程修改了turn为1时，p1进程才可能进入临界区。p1进入临界区后p0不可能进入临界区。

缺点：

1. 各个进程只能轮流的使用临界区，如果turn编号进程不使用临界资源，其他的进程也无法使用这个临界资源。

Ⅱ 双标志先检查法

思路：
设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0]=ture意味着0号进程P0现在想要进入临界区。
每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

伪代码如下：

缺点：

1. 这个算法在并发情况下可能出现问题。
   p0进程在①②两步才会申请到锁，这两个操作不是原子的，如果p0进程在①步执行完后发生进程切换。
   CPU开始调度p1进程，因为p0进程还没有把flag[0]设置为true，所以进程p1也会进入临界区。
   这样就导致临界区有两个进程，会出现数据不一致问题。

Ⅲ 双标志后检查法

具体思路与双标志先检查法类似，这里直接列出伪代码：

缺点：

1. 仍然在并发场景下
   p0进程将flag[0]数组设置为true后进程切换，CPU调度p1进程将flag[1]设置为true。
   这就会导致两个进程都卡在while循环上，两个进程都进不去临界区。这两个线程会产生饥饿问题

Ⅳ peterson算法

思路：
结合单标志法和双标志法，当有多个进程申请临界资源时，其他进程做出谦让，让一个进程访问临界资源

伪代码如下：

每一个进程在进入临界区前都会做两件事：

1. 声明自己要进入临界区
2. 允许对方进程优先进入临界区

在并发场景下分析不同执行步骤：
①②③⑥⑦⑧ p0进程进入临界区
①⑥②③ p0进程进入临界区
①⑥②⑦⑧ p0进程进入临界区
都不会发生多个进程出现在临界资源上

缺点：

1. 进程如果没有进入临界区，这个进程没有脱离CPU，CPU处于忙等状态。

3.进程互斥的硬件实现方法

Ⅰ中断屏蔽法

利用开/关中断指令实现
（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

优点：

1. 简单，高效

缺点

1. 不适合多处理器的场景
2. 关中断，开中断指令只能在内核态使用，不能在用户态使用。只有内核进程才可以使用。

Ⅱ TestAndSet指令

TestAndSet指令又称为TSL指令。
TSL指令由硬件实现，执行过程中不允许被打断

//布尔型共享变量lock表示当前临界区是否被加锁
//true表示已加锁，false表示未加锁
bool TestAndSet (bool *lock){
	bool old;
	old = *lock;//old用来存放lock原来的值
	*lock = true;//无论之前是否已加锁,都将lock设为true
	return old;//返回lock原来的值
}
//以下是使用TSL 指令实现互斥的算法逻辑
while (TestAndSet (&lock));//”上锁"并“检查”
//临界区代码段...
lock = false;//“解锁""
//剩余区代码段...
1
2
3
4
5
6
7
8
9
10
11
12
13

分析：
若刚开始 lock是false，则TSL返回的old值为 false，while循环条件不满足，直接跳过循环，进入临界区，此时锁的值变为true。若刚开始lock是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成

优点：

1. 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
2. 适用于多处理机环境

缺点：

1. 临界资源上锁时，进程不能及时解除CPU调度，CPU会出现忙等状态。

Ⅲ Swap指令

Swap指令是用硬件实现的，执行的过程不允许被中断

Swap指令作用是交换两个变量的值，但是这个交换是原子的。

// Swap指令的作用是交换两个变量的值
Swap (bool *a, bool *b){
	bool temp;
	temp = *a;
	*a=*b;
	*b = temp;
}
//以下是用Swap指令实现互斥的算法逻辑
//lock表示当前临界区是否被加锁
bool old = true;
while (old == true)
	Swap (&lock,&old );
临界区代码段..
lock = false;
剩余区代码段...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如果old为lock为true，则进程会一直循环处理。直到lock为false才会跳出循环执行临界区代码段。