3

我正在研究多线程并试图理解信号量和互斥的概念。我在网上找到的大多数示例都使用某种库（例如pthread）来实现信号量或互斥量，但我更感兴趣的是实现一个建立临界区的简单信号量——不超过一个线程访问特定内存区域。

对于这项任务，我相信我需要一个互斥锁（如果我正确理解术语，也就是二进制信号量）。我可以看到信号量如何通过将代码段“锁定”到单个线程来防止竞争条件，但是是什么阻止了信号量本身发生竞争条件？

我想象一个二进制信号量来保存一个int值来跟踪锁：

Semaphore
---------
int lock = 1;

unsigned P(void){
    if(lock > 0){
        lock--;
        return 0; /* success */
    }
    return 1; /* fail */
}

void V(void){
    lock++;
}

假设两个线程同时调用该P函数，它们都同时到达if(lock > 0)检查并将条件评估为真——这将创建一个竞争条件，其中两个线程都被授予同时访问同一内存区域的权限。

那么是什么阻止了这种竞争条件在现实世界的信号量实现中发生呢？

4

3 回答 3

4

锁定和释放semaphores和/或mutexes作为atomic操作发生，这意味着 CPU 不能从当前进程中退出。这确保了一旦启动互斥锁（它由单个或几个 CPU 指令（微代码）组成），该进程就会保持 CPU 直到锁定/释放完成。
实现线程也有不同的方法，可以是 CPU（内核空间）的直接支持，也可以是用户空间中的库（例如pthreads）。

来自OSDev.org

原子操作是始终执行的操作，没有任何其他进程能够读取或更改在操作期间读取或更改的状态。它作为一个步骤有效地执行，并且在处理多个独立进程的许多算法中是一个重要的质量，无论是在同步还是在不需要同步的情况下更新共享数据的算法中。

这也是一篇关于原子性的好文章（尽管在 Delphi 中）。

于 2013-04-23T13:16:08.797 回答
3

实现大多数锁定原语的最常见（尽管绝对不是唯一）方法是比较和设置指令。正常的移动指令只会将内存位置的值设置为您要求的任何值，而比较和设置指令确实“仅当内存位置的值为 Y 时，才会自动将此内存位置设置为值 X，然后如果操作成功与否，设置一些标志”。关键字“原子”是 CPU 可以在硬件中确保没有其他任何东西可以干扰该操作。

使用比较和交换指令，您的示例P可以实现为：

int oldlock;
retry:
oldlock = lock;
if (oldlock > 0) {
    if (compare_and_swap(&lock, oldlock, oldlock - 1))
        goto retry;
    return 0;
}
return 1;

当然现实比这复杂得多，但是比较和设置很容易理解和解释，并且具有可以实现（几乎？）所有其他锁定原语的好特性。

这是维基百科的文章。

于 2013-04-23T13:29:03.127 回答
2

semaphorea （或 a mutex）和“正常”之间的区别并variable没有那么大。那些为您提供此功能的库只是确保semaphore只能通过原子操作访问。有多种方法可以实现：

  • 保证原子访问的特殊汇编指令，例如：TSL或XCHG.

  • 在访问变量之前关闭调度程序interrupts，然后再次打开它们。因此调度程序无法从 CPU 中删除您的进程。但是您必须知道，这只适用于单 CPU 系统。

  • 使用特定于语言的功能，例如 Java 的synchronise关键字。

如何使用TSL指令的示例：

enter_region:        ; A "jump to" tag; function entry point.

  tsl reg, flag      ; Test and Set Lock; flag is the
                     ; shared variable; it is copied
                     ; into the register reg and flag
                     ; then atomically set to 1.

  cmp reg, #0        ; Was flag zero on entry_region?

  jnz enter_region   ; Jump to enter_region if
                     ; reg is non-zero; i.e.,
                     ; flag was non-zero on entry.

  ret                ; Exit; i.e., flag was zero on
                     ; entry. If we get here, tsl
                     ; will have set it non-zero; thus,
                     ; we have claimed the resource
                     ; associated with flag.

leave_region:
  move flag, #0      ; store 0 in flag
  ret                ; return to caller

顺便说一句，正如您已经正确指出的那样， amutex只是一种特殊的 a semaphore，仅允许FALSE（0在 C 中表示为）和TRUE（由1或任何其他值表示!= 0）作为它的内部int变量。从而使其成为所谓的binary semaphore.

于 2018-07-30T21:48:43.210 回答