时间戳可以用于同步具有竞争条件的进程吗？

Question

我想知道是否可以使用 timestamp 来解决进程同步问题，当竞争条件发生时？
下面是 entry 的算法 以及 退出部分 对于每个想要进入临界区的进程。入口部分使用 FCFS（先来先服务）技术来访问临界区。

    interested[N] is shared array of N integers where N is number of processes.

    // This section executed when process enters critical section.
    entry_section (int processNumber) {
        interested [processNumber] = getCurrentTimeStamp ();  // Gets the current timestamp.
        index = findOldestProcessNumber (interested);         // Find the process number with least timestamp.
        while (index != processNumber);
    }

    // This section executed when process leaves critical section.
    exit_section (int processNumber) {
        interested [processNumber] = NULL;
    }

据我所知，该算法满足同步的所有条件，即互斥、进度、有界等待和可移植性。那么，我说得对吗？

感谢您抽出时间。

Answer 1

您的代码只是一个草图，但它很可能不会适用于所有情况。

如果没有锁并且所有函数都使用非原子操作，则无法保证代码会正确执行。它与第一个示例本质上相同 here，除了您使用的是数组并假设您不需要原子性，因为每个进程将只访问它自己的元素。

让我试着想出一个反例。

一些小的说明。

据我了解，每个过程的省略部分是运行在一个循环中

while(!processExitCondition)
{
    // some non-critical code
    ...
    // your critical section as in the question
    entry_section (int processNumber) {
        interested [processNumber] = getCurrentTimeStamp ();  // Gets the current timestamp.
        index = findOldestProcessNumber (interested);         // Find the process number with least timestamp.
        while (index != processNumber);
    }

    // This section executed when process leaves critical section.
    exit_section (int processNumber) {
        interested [processNumber] = NULL;
    }
    // more non-critical code
    ...
}

在我看来，调度部分应该是忙等待，不断获取最旧的进程：

while (findOldestProcessNumber (interested) != processNumber);

否则，您的所有线程都可以立即挂在无限 while 循环中，除了第一个将执行一次并在之后立即挂起的线程。

现在你的调度函数 findOldestProcessNumber (interested); 有一些有限的执行时间，如果我关于进程外循环存在的假设 while(!processExitCondition) 正确，这个执行时间可能恰好比关键部分之前或之后的代码。结果，完成的进程可以在 findOldestProcessNumber (interested); 迭代它之前返回到 interested 数组，如果 getCurrentTimeStamp (); 是低保真度（比如秒），你可以让两个进程进入临界区立刻。想象一下，在 findOldestProcessNumber (interested); 中添加一个长时间的睡眠，这样会更容易看出它是如何发生的。

你可以说这是一个人为的例子，但关键是不能保证进程将如何相互交错，所以你的同步依赖于代码的某些部分执行特定时间的假设"large" 或 "small" 就够了。这只是使用这些假设来伪造原子操作的尝试。

你可以想出相反的想法来让它发挥作用。假设您可以为每个调用者实现 getCurrentTimeStamp () 到 return 一个唯一的时间戳。要么是一个简单的原子计数器，硬件保证只有一个进程可以增加它，要么在内部使用原子锁（互斥锁），它是自己的关键部分，如果你愿意，它会忙于等待这个锁为每个调用进程提供一个不同的系统时钟值让它成为一个实时的。但是通过单独的 findOldestProcessNumber (interested) 调用，我发现很难想出一种方法来保证它。我不能说这是不可能的，但它变得越复杂，你就越有可能只是隐藏没有互斥保证。

所以最简单的带锁（mutex）的解决方案是最好的。在您的代码片段中，在您的关键部分周围添加一个互斥锁，您当前的进入和退出代码仅用于以先到先得的方式进行调度，并且互斥锁为您提供互斥保证。

如果你想要一个无锁的解决方案，你可以使用 Boost lockfree queue or implement a lockless ring buffer to push the processes number the queue in entry_section and then wait for it to get its turn, although 就像它看起来的那样直观。

Answer 2

简短而贴心，这是此方法的两个问题。

您所有的进程都在忙等待。这意味着即使进程不能进入临界区，它仍然不能休息。这意味着 os 调度程序需要不断地调度所有感兴趣的进程，即使它们没有产生有意义的输出。这会损害性能和功耗。
这是大的。不能保证两个进程不会有相同的时间戳。这可能不太可能，但当您想保证互斥以防止竞争条件时，可能性并不是您要寻找的。

时间戳可以用于同步具有竞争条件的进程吗？

Can timestamp be used in synchronization of processes having Race Condition?

synchronization

operating-system

process