概念
进程同步
在多道程序环境下，进程是并发执行的，这带来了异步性——即每个进程都以各自独立、不可预知的速度向前推进。然而，某些进程之间必须相互协作，一个进程的执行可能需要等待另一个进程提供数据或发出信号，这就要求它们按照某种先后次序来执行。进程同步的主要任务就是对多个相关进程在执行次序上进行协调，以确保它们能够正确地协同工作。
进程互斥
进程互斥是进程同步的一种特殊情况，主要解决对临界资源的独占式访问问题。临界资源是指一次仅允许一个进程使用的资源（如硬件打印机、共享数据结构等）。互斥机制保证了在任意时刻，至多有一个进程处于访问该资源的临界区代码段中。
互斥的四个部分
进入区：检查临界资源是否可以访问，如果可以，需要“上锁”
临界区：访问临界资源的代码
退出区：负责“解锁”
剩余区：其余代码
互斥需要遵循的原则
空闲让进：如果此时临界资源没有被访问，就应该让进程访问临界资源
忙则等待：如果此时临界资源正在被访问，其他试图访问的进程需要等待
有限等待：正在等待的进程应该在有限的时间内被响应
让权等待：正在等待的进程需要放弃处理机，避免忙等
进程互斥
进程互斥的软件实现方法
单标志法
turn的初值为0，表示刚开始只能由进程p0访问临界区资源，如果进程p1要访问临界区资源，就会卡在while循环，直到时间片用完，换p0进程上处理机运行，直到p0进程使用完临界区并将turn置为1，p1进程才能够访问临界区。
但是当p0进程暂时不需要使用临界区，而p1进程需要使用临界区时，由于turn的值为0，所以p1进程必须要等到p0进程是用完临界区并将turn置为1时，才能使用临界区，因此违背了空闲让进的原则。
int turn = 0; // 表示允许进入临界区的进程号
// 进程P0
while(turn != 0); // 进入区
// 临界区代码
turn = 1; // 退出区
// 进程P1
while(turn != 1); // 进入区
// 临界区代码
turn = 0; // 退出区
双标志先检查法
设置一个bool型数组，数组的各个元素表示各进程是否想要进入临界区的意愿，当进程p0想要进入临界区时，要先检查p1是否想要进入临界区，即检查flagp[1]是否等于true，若flag[1]为true，则进程p0会卡在while循环，直到p1进程访问完临界区并将flag[1]置为false，p0检查到flag[1]为flase，才能进入临界区。
另外在程序并发运行的情况下，可能p0执行完①指令后，发现可以进入临界区，接着下处理机换p1进程上处理机运行，当p1进程运行到①指令时，由于p0进程还没有执行②指令，因此p1进程也认为自己可以进入临界区，因此这种方法并不能保证互斥性，违背了忙则等待的特性。
原因在于①②命令不是一气呵成地执行
bool flag[2] = {false, false}; // 表示进程是否想进入临界区
// 进程Pi (i=0或1)
while(flag[j]); // ① 先检查对方是否想进入
flag[i] = true; // ② 设置自己标志
// 临界区代码
flag[i] = false; // 退出区
双标志后检查法
设置一个bool型数组，数组的各个元素表示各进程是否想要进入临界区的意愿，当进程p0想要进入临界区时，要先表达自己的意愿，即将flag[0]置为true，然后再检查p1是否想要进入临界区，这样就避免了忙则等待问题。
但与此同时在程序并发运行的情况下，可能p0执行完①指令后，接着下处理机换p1进程上处理机运行，当p1进程运行完①指令后，之后无论是谁在处理机运行都会发现对方把flag置为true，违背了空闲让进和有限等待原则，即发生了死锁
原因同样在于①②命令不是一气呵成地执行
bool flag[2] = {false, false};
// 进程Pi
flag[i] = true; // ① 先设置自己标志
while(flag[j]); // ② 再检查对方标志
// 临界区代码
flag[i] = false;
Peterson算法
设置一个bool型数组和turn，当进程p0想要进入临界区时，要先表达自己的意愿，即将flag[0]置为true，然后要将turn置为1，表示谦让让对方先使用，Peterson解决了双标志检查法可能违背的忙则等待、空闲让进和有限等待的问题，这主要在于每个进程在申请临界区时都会表示谦让(turn=j)，但由于turn是共享变量，最后写入turn的进程实际上失去了优先权。因为while循环条件检查turn == j，如果turn最终等于对方的编号，那么自己就能通过等待；如果turn等于自己的编号，那么自己就需要等待。这保证了同一时刻只有一个进程能通过while循环进入临界区。
bool flag[2] = {false, false};
int turn = 0;
// 进程Pi
flag[i] = true; // 表示自己想进入
turn = j; // 让对方先进入
while(flag[j] && turn == j); // 对方想进入且是对方的轮次则等待
// 临界区代码
flag[i] = false;
进程互斥的硬件实现方法
中断屏蔽法
利用开中断、关中断实现
TestAndSet
bool TestAndSet(bool *lock) {
bool old = *lock;
*lock = true;
return old;
}
// 使用方式
while(TestAndSet(&lock)); // 忙等待
// 临界区代码
lock = false;
Swap指令
void Swap(bool *a, bool *b) {
bool temp = *a;
*a = *b;
*b = temp;
}
// 使用方式
bool key = true;
do {
Swap(&lock, &key);
} while(key);
// 临界区代码
lock = false;
互斥锁
acquire(); // 获取锁（忙等待或阻塞）
// 临界区代码
release(); // 释放锁
信号量机制
信号量的定义
typedef struct {
int value; // 资源数量
struct process *L; // 等待队列
} semaphore;
P、V操作
void P(semaphore S) { // wait/down操作
S.value--;
if(S.value < 0) {
block(S.L); // 阻塞当前进程
}
}
void V(semaphore S) { // signal/up操作
S.value++;
if(S.value <= 0) {
wakeup(S.L); // 唤醒一个等待进程
}
}
信号量实现进程的同步、互斥
实现进程互斥
semaphore mutex = 1; // 互斥信号量
process Pi() {
P(mutex);
// 临界区代码
V(mutex);
}
实现进程同步
// 保证代码段A在代码段B之前执行
semaphore S = 0; // 同步信号量
// 进程P1
代码段A;
V(S);
// 进程P2
P(S);
代码段B;
经典同步问题
生产者消费者问题
semaphore mutex = 1; // 互斥访问缓冲区
semaphore empty = n; // 空闲缓冲区数量
semaphore full = 0; // 已用缓冲区数量
// 生产者
producer() {
while(1) {
生产一个产品;
P(empty); // 申请空缓冲区
P(mutex); // 申请缓冲区访问权
将产品放入缓冲区;
V(mutex);
V(full); // 增加满缓冲区
}
}
// 消费者
consumer() {
while(1) {
P(full); // 申请有产品的缓冲区
P(mutex);
从缓冲区取出产品;
V(mutex);
V(empty); // 增加空缓冲区
消费产品;
}
}
多生产者多消费者问题
semaphore plate = 1; // 盘子互斥
semaphore apple = 0; // 苹果数量
semaphore orange = 0; // 橘子数量
爸爸() { 放苹果; V(apple); }
妈妈() { 放橘子; V(orange); }
儿子() { P(orange); 取橘子; }
女儿() { P(apple); 取苹果; }
读者写者问题
semaphore rw = 1; // 读写互斥
int count = 0; // 读者计数
semaphore mutex = 1; // 保护count
// 写者
writer() {
P(rw);
写操作;
V(rw);
}
// 读者
reader() {
P(mutex);
if(count == 0) P(rw); // 第一个读者加锁
count++;
V(mutex);
读操作;
P(mutex);
count--;
if(count == 0) V(rw); // 最后一个读者解锁
V(mutex);
}
哲学家进餐问题
哲学家进餐问题主要用于解决死锁问题，由于每个进程都需要持有两个资源，因此就会有死锁的可能
管程
对PV操作的封装