面试官问我：线程同步的几种方式？我画一张结构图甩他脸上！

unset unset 简要回答 unset unset

软件实现方法：

1. 单标志法 ：仅适用于两个进程之间的同步，通过一个标志位实现互斥（例如设置一个共享的整型变量标志turn，用于表示程序进入临界区的权限），但通常不符合实际需求，违背了“ 空闲让进 ”准则。
2. 双标志先检查法 ：仅适用于两个进程的同步，进程在进入临界区 前 检查对方标志位，如果对方标志位为TRUE则等待，否则将自身标志位置为TRUE，该方法不能保证进程对临界资源的互斥使用，违背了“ 忙则等待 ”准则。
3. 双标志后检查法 ：仅适用于两个进程的同步，进程在进入临界区 后 检查对方标志位，可能导致两个进程均陷入无限等待，违背了“ 有限等待 ” 和 “ 空闲让进 ”准则。
4. Peterson算法 ：结合 单标志位 和 双标志后检查法，解决忙等待和死锁问题，但不满足“ 让权等待 ”准则，且 只能 处理 两个进程之间 的临界区问题。

硬件实现方法：

1. 关中断方法 ：在进入临界区前关中断，退出临界区后开中断。
2. 硬件指令方法 ：TSL（Test and Set Lock）：通过硬件指令实现原子操作。Swap：通过硬件指令交换两个变量的值。

高级同步机制：

• 信号量 ：用于实现同步和互斥，支持P()和V()操作。
• 管程 ：将共享资源和操作封装在一起，提供了一种结构化的同步方式。
• 屏障 ：用于确保多个进程或线程在某个点之前不会继续执行。
• 条件变量 ：用于在多个进程或线程之间传递状态信息。

unset unset 详细回答 unset unset

软件实现方法：

1. 单标志法 ：设置一个 共享 的变量标志，比如整型变量turn，表示程序进入临界区的权限，可以取值为0或1； 单标志法适用于两个进程 ，以P0进程和P1进程为例，当turn取0时，进程P0可以进入临界区；当turn取1时，进程P1可以进入临界区；当进程P0退出临界区时，通过将turn置为1将 进入临界区的权限 转让给进程P1，进程P1的退出同理。算法可用伪代码描述如下：

   //进程P0
   while (TRUE) {
    while (turn != 0); //"进入区";如果turn = 1，说明进程P1还未退出临界区，此时进程P0会阻塞在while循环中。
    临界区;
    turn = 1;   //"退出区";允许进程P1进入临界区，将 进入临界区的权限 转让给进程P1。
    剩余区;    //其余部分代码
   }
   //进程P1
   while (TRUE) {
    while (turn != 1); //"进入区"; 检查标志
    临界区;
    turn = 0;   //"退出区"; 转让权限
    剩余区;    
   }
   

   该方法的问题在于 强制要求进程轮流进入临界区 ，但这样不符合实际需求，违背了“ 空闲让进 ”准则。

2. 双标志先检查法 ：与“单标志法”相比，将共享变量turn改为数组flag[2]，进程在进入临界区 前 检查对方标志位——如果对方标志位为TRUE则等待，否则将自身标志位 置为TRUE，表示自己正在使用临界资源，退出临界区后再将自身标志位置为FALSE，表示自己已经退出临界区，以进程Pi和进程Pj为例，双标志先检查法用伪代码描述如下：

   while (TRUE) {
    while (flag[j]);  //检查对方进程是否正在使用临界资源。
    flag[i] = TRUE;   //将自身flag标志位置为TRUE，表示本进程已进入临界区。
    临界区;
    flag[i] = FALSE;  //将自身flag标志位置为FALSE，表示本进程已经退出临界区。
    剩余区;
   }
   

   该方法的问题在于， 两个进程可能同时进入临界区 ，违背了“ 忙则等待 ”准则，因此该方法不能保证进程对临界资源的互斥使用。

3. 双标志后检查法 ：调整了“双标志先检查法”中更改自身标志位和准入检测的顺序， 先设置标志，再进行准入检测，避免了进程同时进入临界区的情况 。在进入临界区 后 检查对方标志位，以进程Pi和进程Pj为例，双标志后检查法用伪代码描述如下：

   while (TRUE) {
    flag[i] = TRUE;  //调整了前两条语句的执行顺序。
    while (flag[j]);
    临界区;
    flag[i] = FALSE;
    剩余区;
   }
   

   该方法的问题在于，可能导致两个进程均陷入无限等待（两个进程均无法跳出while循环），违背了“ 有限等待 ” 和 “ 空闲让进 ”准则。

4. Peterson算法 ：结合 单标志位 和 双标志后检查法，既设置flag标志，用于表明进程是否希望进入临界区，又设置共享变量turn，用于规定进程进入临界区的顺序。Peterson算法 满足互斥条件，空闲让进条件和有限等待条件 ，但不满足“ 让权等待 ”准则，且 只能 处理 两个进程之间 的临界区问题，不符合实际需求。Peterson算法可用伪代码描述如下：

   while (TRUE) {
    flag[i] = TRUE;  //先表示当前进程希望进入临界区。
    turn = j;   //再进行谦让，允许对方进入临界区。
    while (flag[j] && turn == j); //如果对方也想进入临界区，而自己又表示了谦让，那就让对方先进临界区，自己则等待。
    临界区;
    flag[i] = FALSE; //退出临界区时，将自身flag标志置为FALSE，表示退出临界区。
    剩余区;
   }
   

   可见，仅凭软件机制仍有不足之处。

硬件实现方法：

1. 关中断方法 ：在进入临界区前关中断，暂停进程调度，让进程独占处理机，当进程退出临界区后开中断；关中断方法 满足了“空闲让进”，“忙则等待” 和 “有限等待” ；关中断方法 不适用于多处理器环境 ，因为即使同时关闭了所有核心的中断，也不能阻止其他核心上正在执行的进程。
2. 硬件指令方法 ：TSL（Test and Set Lock）：通过硬件指令实现原子操作。Swap：又称exchange指令，通过硬件指令交换两个变量的值。

高级同步机制：

• 信号量 ：由荷兰科学家Dijkstra在1965年首次提出“信号量”机制，其基本原理是在几个进程之间使用简单的信号来实现同步；在操作系统中，信号量是一种关联一类临界资源的 数据结构 ， 信号量的不同值表示一个临界资源的不同状态 ；信号量机制可以用于实现同步和互斥，支持 P()和V()操作 。信号量的绝对值就是等待该资源的进程数；若信号量的值小于0，说明该资源恰好被分配完。P(S)表示申请一个资源S，若资源不够则阻塞等待（wait）；V(S)表示释放一个资源S，若有进程在等待该资源，则唤醒一个正在等待的进程（release）。
• 管程 ：引入管程的目的主要是集中管理分散于不同进程的临界区，防止进程违反同步操作。管程是一个 软件模块 ，由一些公共变量及其描述和访问所有这些变量的函数组成。进程对共享资源的请求、释放和其他操作必须通过同一个管程来实现。当多个进程请求访问同一资源时，会根 据资源的情况接受或拒绝 ， 确保每次只有一个进程进入临界区 ，有效实现进程互斥。管程包含了 面向对象 的思想，将表达共享资源的数据结构和对其进行操作的进程封装在一个对象中，并封装了同步操作，从而对进程隐藏同步的细节，简化了调用同步功能的接口。
• 屏障 ：屏障是一种同步机制，用于确保多个进程或线程在某个点之前不会继续执行；当进程或线程 到达屏障时 ，它会 等待 ，直到所有进程或线程都到达屏障后才继续执行；屏障机制适合需要多个进程或线程同步执行的场景，如并行计算、多阶段任务。
• 条件变量 ：条件变量是一种同步机制，用于在多个进程或线程之间传递状态信息；进程或线程在条件不满足时等待，条件满足时被唤醒；通常与互斥锁一起使用，以避免竞争条件。

unset unset 知识拓展 unset unset

• 文中提到的四种 高级同步机制 ，如下图所示：