进程同步
同步概述
引入：
问题：
进程协作时需要相互通信；进程通信方式通常有两种：==消息传递 + 共享内存==
共享内存方式涉及多个进程对公共区域的操作
-> 多个进程可能 ==同时== 对公共区域进行操作，造成公共区域的 ==数据不一致性== （==并行==）
解释：进程 A 正在对公共区域进行写操作，进程 B 同时对公共区域进行读操作，那么读出来的数据和存储的数据很可能不一致
-> 某个进程正在对公共区域进行操作，另一个进程 ==抢占== 当前进程的处理器使用权，造成公共区域的 ==数据不一致性== （==并发==）
解释：进程 A 执行计算后得到相应的数据打算向公共区域中写入，进程 B 直接抢占处理器的使用权，导致进程 A 无法写入，那么读出来的
数据也会和将要存储的数据不一致
方式：==同步== -> 利用机制确保各个协作进程之间按照规定的顺序执行 / 利用机制确保各个协作进程不会 ==并发== 操作公共资源
解释：某个进程正在操作公共区域时，其余的进程只能够按照顺序依次等待执行，相当于对当前的公共区域上锁了
解释：每个进程并不仅仅只是对公共区域操作，某个进程对公共区域操作结束后，仍然可能继续操作其他的数据
非抢占式就可以允许当前进程继续执行，抢占式就会允许其他进程开始对公共区域操作，因为已经有进程在等待操作公共区域了
细节：单核处理器通常在修改变量时禁止中断打断当前进程的执行；多核处理器通常是采用同步方式解决
注：多核处理器需要对每个计算核都禁止中断，是非常低效的行为
概念：
==竞争条件==：多个进程并发访问和操作同一数据并且执行结果 ==和特定访问顺序有关== 的情况
/*
1. 利用生产者消费者问题进行解释
2. 笔记中此前使用循环队列解决生产者消费者问题，导致缓冲区容量始终少 1
3. 在这里加以改进使用公共变量 counter 来记录缓冲区数据项的数量
4. 正是因为使用公共变量 counter 就会导致竞争条件的出现
*/// 假设 counter 默认值为 5
// 生产者
while (true)
{
while (counter == BUFFER_SIZE)
{
// 如果公共变量等于缓冲区大小证明缓冲区已满 -> 生产者进入空循环中等待 -> 直到缓冲区不满为止
}
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
/*
1. 生产者生产完数据项之后 -> 修改自己寄存器中数据项数量的值
2. 此时消费者想要对缓冲区进行读取 -> 处理器切换至消费者 -> 此时生产者还没来得及对公共变量做出修改
3. 生产者寄存器中的值显然是 6，但是公共变量仍然是 5
---------------------------------------------------------> 消费者进程执行结束
生产者继续执行 -> 将寄存器的值赋给公共变量 -> 此时公共变量显然为 6 ！
*/
counter++;
}// 消费者
while (true)
{
while (counter == 0)
{
// 如果公共变量等于0证明缓冲区中没有数据项 -> 消费者进入空循环等待 -> 直到缓冲区中存在数据项为止
}
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
/*
1. 消费者消费完数据项后 -> 修改自己寄存器中的数据项的值
2. 生产者进程想要继续执行 -> 处理器切换至生产者 -> 此时消费者也没有来得及对公共变量做出修改
3. 消费者寄存器的值显然是 4 ！但是公共变量仍然为 5
---------------------------------------------------------> 生产者进程执行结束
消费者进程继续执行 -> 将寄存器中的值赋给公共变量 -> 此时公共变量显然为 4 (6 -> 4)
*/
counter--;
}
/*
总结：由于生产者进程 -> 消费者进程 -> 生产者进程 -> 消费者进程 这种执行顺序导致了公共变量的不一致
如果不允许进程对公共区域进行并发操作，那么顺序显然就是 生产者进程 -> 消费者进程，不会造成公共变量的不一致
这种类似的情况都称之为竞争条件，执行的结果和特定的顺序有关
*/代码区域
进入区：判断进程是否可以进入临界区的代码段 + 对临界资源上锁的代码段（如果进程可以进入）
==临界区==：对共享区域进行访问的 ==代码段==
注：同步可以说是解决进程通信的问题，也可以说就是解决临界区的实现问题，怎么才能够确保临界区中只存在一个进程
退出区：释放临界资源的锁的代码段
剩余区：进程需要执行的剩余代码段
同步条件：
互斥(mutual exclusion)：临界区中存在进程正在执行，==不允许== 其余进程进入临界区执行
进步(progress)：想进入临界区的进程可以 ==参与选择进入== ，不想要进入临界区的进程不允许进入
有限等待(bounded waiting)：想进入临界区的进程不能 ==无限地等待== 下去
解释：因为可能存在多个进程同时在进入区中等待，需要避免某个进程始终在等待进入临界区
每个同步方式都应该满足这三个条件 -> 同步方式的进入区和退出区必须满足这三个条件
解释：因为进入区和退出区才是控制进程进入临界区的关键，临界区只是对公共区域操作的代码而已
同步方式
软件同步
Peterson
内容：
boolean[] flag：想要进入临界区的进程都将其在数组中的对应位置置为true注：想要进入临界区的进程将标志位置为
true并不代表一定能够进入，必须要另外一个进程 “谦让” 自己才可以进入int turn：表示当前进程优先让另一个进程执行解释：这个参数最好不要理解成轮到哪个进程进入临界区的意思，否则可能算法理解会有问题
适用情况：仅适用于两个进程的同步方式
代码：
/*
1. pid 表示执行该代码段的进程的进程标识符，opid 表示另一个进程的进程标识符
2. opid = 1 -pid；这也就是为什么 Peterson 方式只适用于两个进程，要是再多来一个进程就会把它当成第一个进程
*/
void synchronize(int pid)
{
do
{
// 1. 代表进程标识符为 pid 的进程想要进入临界区
flag[pid] = true;
// 2. 当前进程希望让另一个进程优先进入临界区 (或者理解为询问另一个进程是否想要进入临界区)
turn = opid;
// 3. 此时由于当前进程希望另一个进程优先进入临界区，那么剩下的显然就看另一个进程自己是否想要进入了
// -> 如果另一个进程想要进入，那么显然当前进程就必须进入循环进行空等待 (如果另一个进程想要进入，那么证明另一个进程显然是先来的)
// -> 如果另一个进程不想进入，那么显然当前进程可以直接进入临界区
while(flag[opid] && turn == opid)
{
// 空等待
}
/* 临界区 */
flag[pid] = false; // 退出区
/* 剩余区 */
}while(true)
}
硬件同步
注：这里用 C 语言代替汇编指令集表示，仅仅只是一种抽象，落实到不同的指令集上是不同的
TestAndSet
内容：
bool *lock：每个进程都可以操作的全局变量；初始化为false适用情况：适用于多个进程的同步方式
缺陷：没有满足有限等待的条件？
代码：
/*
1. 进入函数后先将当前锁的值记住
2. 无论当前锁的值为什么，都修改为 true
*/
bool testAndSet(bool *lock)
{
bool temp = *lock;
*lock = true;
// 返回锁之前的值；锁的值为 false 就代表临界资源没有上锁，锁的值为 true 就代表邻接资源上锁
return temp;
}
void synchronize()
{
do
{ // 1. 只要当前的锁为 false，就证明没有进程在临界区中，当前进程就可以进入临界区
// 2. 其余进程想要进入临界区时，拿到锁的值为 true，所以函数返回的值也为 true，无法进入临界区中
while(testAndSet(&lock))
{
// 空等待
}
/* 临界区 */
lock = false; // 退出区；3. 当前进程退出临界区后，修改锁的值，其余进程就可以进入了
/* 剩余区 */
}while(true)
}
Swap
内容：
bool *key：用于和lock进行交换，判断当前临界区中是否存在进程 局部变量- ``bool *lock
：每个进程都可以操作的 <a style="color:red;">全局变量</a>；初始化为false`
适用情况：适用于多个进程的同步方式
缺陷：(1) 没有满足有限等待的条件？ (2) 实现非常的复杂
代码
void Swap (bool *a, bool *b)
{
boolean temp = *a;
*a = *b;
*b = temp:
}
void synchronize()
{
while (true)
{
// 1. 默认临界区中是存在进程的所以才会初始化为 true
key = true;
while (key)
{
// 2. 锁的值和 key 的值交换：
// -> 如果锁的值为 false，那么交换后 key 显然也是 false，那么就证明临界区中不存在进程
// -> 如果锁的值为 true，那么交换后 key 仍然会为 true，那么会当前进程会继续交换
Swap(&lock, &key);
}
/* 临界区 */
lock = false; // 退出区
/* 剩余区 */
}
}
中断屏蔽
互斥锁
- 内容
- 优点 & 缺点：
- 优点：相比于硬件同步实现非常简单
- 缺点：忙等待
- 代码：
信号量
定义：信号量是只能够通过
wait()+signal()操作的 ==整型== 公共变量2. wait 函数用于实现进入区；signal 函数用于实现退出区
void wait()
{
while(S <= 0) // 你可能会在这里产生疑问，信号量的值怎么为负的呢？明显只要有一个进程在临界区，S 就只能够为 0 呀？之后会解释
{
// 空等待
}
S--; // 因为进程进入临界区了，所以信号量需要减少
}void signal()
{
S++;// 代表当前进程退出临界区，所以信号量需要增加
}分类：
二进制信号量：信号量的值 ==只能== 够为 1 和 0
计数信号量：信号量的值等于公共资源的数量（信号量的值可以为 ==大于等于 0 的整数== ）
实现：
普通实现
semaphore mutex = 1;
void synchronize()
{
do
{
wait(mutex); // 进入区
/* 临界区 */
signal(mutex); // 退出区
/* 剩余区 */
}while(true)
}改进实现
typedef struct
{
int mutex;
struct process *list;
}semaphore
void wait(semaphore *S)
{
S->value--;
if (S->value < 0)
{
add this process to S->List;
block(); // 让当前进程进入阻塞态
}
}
void signal(semaphore *S)
{
S->value++;
if (S->value <= 0)
{
remove a process P from S->List;
wakeup(P); // 让当前进程进入就绪态
}
}