进程同步中 Dekker 的算法

在本文中，我们将讨论进程同步中的Dekker 算法。但在讨论 Dekker 算法 之前，我们必须了解进程同步的挑战和重要性。

进程同步简介

计算机系统中多个进程的同时协调称为进程同步。在讨论多进程环境（其中多个任务或进程同时运行）时，我们需要机制来共享对共享资源的访问，即内存、文件和设备。应执行进程同步以确保两个同时访问公共数据的过程不会产生冲突。

进程同步中的挑战

进程同步存在一些常见挑战。其中一些如下：

• 竞态条件 (Race Conditions)： 计算过程的最终结果依赖于事件发生时间的条件。
• 互斥 (Mutual Exclusion)： 要求将一个进程限制在一个单一的步骤中，这可以使用锁变量和监视器等软件工具来实现。
• 死锁 (Deadlocks)： 当两个或多个进程因为相互等待释放共享资源而无法继续执行时。
• 饥饿 (Starvation)： 某些进程可能永远被拒绝访问资源，从而阻碍了进度。

进程同步的重要性

操作系统运行的稳定性、可靠性和准确性都基于成功的同步。未能配备适当同步机制的系统可能会导致不可预测和不愉快的后果，例如系统崩溃、数据损坏等等。同步机制允许我们创建一个稳定有效的多进程环境。

同步： 操作系统通常是并发的，并且并行执行多个任务；因此，它们需要同步，例如共享内存，其中各种进程和任务可以与系统完整性进行交互。如果信息被多次使用或被不同的处理器使用，那么对于信息的可靠性来说，同步至关重要。

Dekker 算法简介

Dekker 算法 以荷兰数学家 Thorens Veenendaal Dekker 的名字命名。该问题的经典解决方案之一是 J. Dekker。这是1968年提出的一项算法，它提供了一种在两个进程使用单一用途资源且不会遭受数据丢失和死锁的条件下进行同步的方法。

Dekker 算法很简单，但主要为双进程系统设计。该算法使用标志常量和自旋变量来同步到临界区，以便一次只有一个进程能够获得访问权限，从而限制了其他进程。通过对这些变量进行适当的调整，可以在不使用硬件支持提供的原子指令的情况下实现同步。

算法的理论方面

Dekker 算法 依赖于互斥规则以及在进入临界区之前所需的基本规则。该算法通过采用以下关键组件来实现此目的：

• 标志变量 (Flag Variables)： 为每个进程使用一个标志，用于指示参与同步的进程进入临界区的意图。它充当了沟通进程进入临界区条件的手段。
• 轮转变量 (Turn Variable)： 最后，使用一个不同的因素，通常称为 “turn” 变量，来决定一个给定的方法能否继续进入临界区域。这个 turn 变量 在进程之间切换，提供了平等的访问机会。
• 条件语句 (Conditional Statements)： 该算法使用测试标志和轮转变量的条件语句。它也被称为互斥协议。这些语句引导执行路径，确保只有满足定义的条件才能进入临界区。

Dekker 算法通过正确利用这些参数和条件来实现互斥，而不依赖于 T&S (Test and Set) 或 CAS (Compare and Swap) 指令。该算法的优点在于其简单性，但又在仅涉及两个进程的情况下非常有效。

与其他同步算法的比较

通常将其他同步算法与 Dekker 算法进行比较，以解决临界区问题。值得注意的比较包括：

• Peterson 算法： 与 Dekker 算法一样，Peterson 协议允许两个进程实现互斥。这两种算法都使用标志变量和条件语句，但实现细节不同。
• Test-and-Set 和 Swap-based 算法： 一些采用 test-and-set 或 swap 原子指令的同步算法使用互斥。虽然它们在某些情况下可能更有效，但此类协议需要特殊的硬件支持。
• Dijkstra 的信号量 (Semaphore)： Edsger Dijkstra 引入了信号量，而不是单个进程，作为一种通用的同步机制，允许多个进程同步对共享资源的访问。信号量有助于解决比 Dekker 算法设计的更复杂的情况。

应根据这些要求、涉及的进程数量和底层硬件的特性来选择同步算法。尽管 Dekker 算法很少用于现代多核系统，但它仍然是学习进程协调概念的重要课程。

Turn 变量

轮转变量 (turn variable) 对所有进程都是通用的，并标识了有权进入其临界区的进程。

• 值：它们通常被赋予反映进程 ID 的值，并指示谁将 next 获得临界区的控制权。
• 作用：轮转变量对于确定哪个进程应首先进入临界区至关重要。它提供了一种在不同进程之间轮流以及公平分配资源的方式。
• 代码中的使用：在算法的伪代码或实现中，会检查并设置轮转变量以决定进程是否可以进入其临界区。

标志变量 (Flag Variable)

它们也被称为标志变量，指示特定进程对临界区的意图。

• 目的：对于每个进程，都有一个标志变量。这些标志显示进程何时进入其临界区或进入临界区。
• 值：标志通常表示 true 或 false，考虑到进程可能已准备好或未准备好。
• 代码中的使用：该算法使用标志变量作为控制机制，以确定特定进程是否想要进入其临界区域。它们决定了是否值得进行此类程序。

这些变量的作用

• 协调：轮转变量和标志变量的结合使用可确保对临界区的访问得到正确控制。轮转变量使进程轮流，而标志变量指示进程是否已准备好访问其临界区。
• 进入条件：进程通过设置其标志变量并尊重轮转变量来指示其意图，以确保是时候让进程进入临界区了。
• 互斥：Dekker 算法通过仔细协作匹配这些变量的值来提供互斥。临界区一次只能有一个进程，而进程轮流访问它。

Dekker 算法涉及的步骤

初始化：每个进程将标志初始化为 false，表示它不会向临界区移动。此外，轮转变量采用二进制值，对应于哪个进程将 first 进入临界区。

进程 A 进入临界区：进程 A 将其标志设置为TRUE，以表示其进入CS (临界区) 的意图。其次，它确保进程 B 的“标志”也已提高，因为它表明 B 也需要进入临界区。但是，如果进程 A 先执行，则轮转变量设置为 1，这意味着进程 B 将 first 进入临界区。之后，进程 A 进入一个忙等待循环，该循环包含频繁的检查以确认它是否应该访问临界区。

进程 B 进入临界区：进程 B 标记为 true，并打算进入临界区。之后，它交叉检查进程 B 的标志是否为 true，这意味着进程 B 也想进入临界区。但是，如果是这种情况，进程 B 会将轮转变量设置为零，这意味着进程 A 应该 first 进入临界区。一旦进程 B 进入其忙等待状态，它就会不断检查其进入临界区的机会。

进程 A 退出临界区：当进程 A 进入临界区时，它执行临界区的代码，并将其标志设置为 false，表示它已完成执行。此外，程序将轮转变量设置为一，这表示进程 B 可以进入临界区域。

进程 B 退出临界区：当进程 B 获得对临界区的访问权限时，它会执行临界区代码，并将自己的标志设置为 false，这意味着它已完成临界区。之后，其轮转值被设置为 0，这意味着 A 进程现在可以前往临界区。

重复：此循环根据轮转变量的值和每个进程的标志设置，交替重复这些步骤。

Python 代码

让我们用 Python 代码来实现进程同步中的Dekker 算法。

代码解释

CustomMutex 类

• 初始化后，CustomMutex 类包含两个标志（self.flags）和一个轮转变量（self.turn）。
• flags 数组显示了线程必须进入临界区的意图。
• 轮转变量决定了哪个线程将进入临界区。

Lock 方法

• 在 lock 方法中获取互斥量构成进入临界区。
• 参数 current_thread 用于调用线程。
• other_thread 是指向另一个线程的指针。
• 之后，该方法使用设置为 true 的标志来指示其访问临界区的意图。

Unlock 方法

• unlock 方法释放互斥量，进程退出临界区。
• 参数 current_thread 象征着调用 unlock 方法的线程。
• 它只将当前线程的标志设置为'False'，这意味着它已离开临界区域。

critical_section 函数

• 这是一个虚拟例程，代表临界区。
• 进入程序的临界区时，此方法将线程号作为参数，以打印一条消息显示线程在临界区的状态，模拟临界区内的一些操作，最后报告退出。
• 最后，它调用 unlock 方法，从而释放互斥量。

thread_function 函数

• 所有线程都将此函数作为其主要目标。
• 使用 lock 方法进入临界区，随后是 critical_section。
• 调用 unlock 方法退出临界区。

示例用法

• 两个线程thread_1 和thread_2 调用 thread_function，其线程号为 0 或 1。
• 线程启动，主程序等待完成。

执行流程

• 在进入临界区之前，每个线程都必须使用其 lock 方法锁定互斥量。互斥量确保一次只有一个线程可以访问临界区。
• 当线程退出其临界区时，它会解锁互斥量，让其他线程进入。

Dekker 算法的正确性条件

互斥

• 条件：在一段时间内，只允许一个进程进入临界区。
• 解释：这是通过使用“turn”和“flag”变量来指导进程进入临界区来实现的。

进度

• 条件：为了让一个进程在尚未进入临界区时获得访问权限，存在一种可能性。
• 解释：算法的忙等待循环意味着一个进程等待并不断检查激活的条件。

有界等待 (Bounded Waiting)

• 条件：然而，在进程表示其进入意图后，其他进程进入临界区的次数是有限的。
• 解释：最后，轮转变量确保进程依次访问标准部分，从而消除了单个进程持续控制临界区的情况。

进程速度独立性

• 条件：算法的准确性不应依赖于进程与其他进程的速度比较。
• 解释：该算法使用轮转变量和标志变量，以便进程在不影响其各自执行速度的情况下获得进入临界区的机会。

Dekker 算法的局限性

Dekker 算法的一些局限性如下：

• 仅限于两个进程

然而，Dekker 算法专门为两个竞争进程设计。添加超过两个进程需要修改算法，这可能会导致增加复杂性。

• 忙等待 (Busy-Waiting)

忙等待是一种常用的算法，可以避免在使用高效调度器时可能发生的上下文切换。在循环中，它们在等待时验证当前条件并消耗 CPU，从而浪费了这些资源。

• 依赖于共享内存

Dekker 算法中的进程通信假定使用共享内存。在缺乏共享内存的系统中，必须采用其他同步方法。

• 无抢占处理

如果操作系统调度程序能够进行抢占，该算法可能会失败。

用例和示例

尽管 Dekker 算法简单且仅限于两个进程，但在某些只需要简单互斥解决方案的情况下，它仍然有其狭窄但相关的应用领域。以下是一些 Dekker 算法可以应用的使用案例和场景：

• 嵌入式系统

在两个关键进程争夺资源的实时嵌入式系统中，Dekker 算法可以有效地避免互斥，而无需繁琐的硬件支持。

• 教育目的

Dekker 算法长期以来一直被用作教学工具，以解释 CS 课程中进程同步的基础知识。它易于理解，适合教程目的。

• 双进程环境

如果系统仅包含两个关键竞争进程争夺同一资源，则可以有效地使用 Dekker 算法。如果更复杂的同步协议过于昂贵，则它仍然适用。

• 资源访问协调

当两个进程必须同步对共享资源（如文件或打印机）的访问时，我们可以使用 Dekker 算法来防止冲突并确保有序访问。

• 小型系统

如果整个系统规模较小，并且 Dekker 算法的简单性优于对更复杂同步机制的需求，那么它可以成为一个务实的选择（Otter，2013）。

• 非抢占环境

该算法使用抢占方法，即当前进程被终止以便启动另一个进程；因此，此类系统不适合该算法，因为它们不支持进程抢占。

• 同等进程速度

与其他算法相比，当两个进程以大约相同的速度运行时，Dekker 算法的性能通常很高。这意味着执行顺序与执行速度无关。

实现 Dekker 算法的挑战和考虑因素

竞态条件

• 挑战：该算法采用忙等待，并且可能容易出现竞态条件，因为多个进程可以同时进入临界区。
• 考虑：为此，必须有一种强大的实现策略，涉及原子操作和硬件同步机制来处理竞态条件。

死锁

• 挑战：虽然 Dekker 算法克服了经典的死锁问题，但有可能错误地修改它，导致进程无法进一步进行的死锁情况。
• 考虑：必须确保算法充分解决了所有可能的情况，以最大限度地减少操作无限期阻塞的发生。

互斥违反

• 挑战：如果一个进程未能被其共享变量正确处理，或者存在不充分的同步逻辑，导致两个或多个进程同时通过临界区，就会发生访问冲突。
• 考虑：为避免互斥问题，应确保进行严格的测试、代码审查，并遵循算法的原则。

抢占问题

• 挑战：目前，如果操作系统抢占进程，该算法将无法处理。抢占可能导致意外的活动或同步问题。
• 考虑：在某些情况下可能发生抢占时，可能需要额外的措施或其他同步方案。

可扩展性问题

• 挑战：Dekker 算法适用于两个进程；将其扩展到更多进程需要进行大量调整，这使得大型系统使用该方法不方便。
• 考虑：在多进程场景下，研究其他更灵活、可扩展的异步同步方法是有价值的。

饥饿

• 挑战：尽管如此，它并不保证公平对待，因为一个进程可能会被饿死，而另一个进程会不断重新进入临界区。
• 考虑：在公平性至关重要的情况下，可能更倾向于处理饥饿的其他同步方法。

缺乏普遍适用性

• 挑战：然而，在当今复杂且快速变化的计算环境中，该算法可能并不总是适合所有情况。
• 考虑：必须评估应用程序的需求和系统的属性。探索可能更有效地处理所述场景中问题的其他同步算法。

代码可读性和维护性

• 挑战：等待和低同步级别的代码可能使其可读性降低，从而难以维护。
• 考虑：通过彻底记录代码并考虑模块化和代码可读性，也可以维护或修改代码。