common-lisp - 如何利用 SBCL 提供的信号量来对抗竞争条件

Question

就我对信号量的了解而言，信号量用于保护可计数且易受竞争条件影响的资源。但是在阅读信号量的 SBCL 文档时，我无法弄清楚如何正确使用提供的信号量实现来保护资源。

我记得通常的工作流程是:

一个进程想要检索受信号量保护的一些
数据(为了这个例子，这是一个简单的队列)。作为
信号量计数器为 0，进程等待

另一个进程将一些东西放入队列中，因为信号量是
递增，向所有等待进程发送信号

考虑到交错的可能性，人们必须保护这些资源访问中的任何一个，因为它们可能不按该顺序或根本没有任何线性顺序。因此例如Java 将每个类解释为一个隐式监视器并提供一个 syncronized程序员可以使用关键字来定义一次只能由一个进程访问的 protected 区域。

我如何在 common-lisp 中模拟这个功能，因为我很确定我当前的代码和没有信号量一样线程安全，因为信号量不知道要保护什么代码。

;;the package 
(defpackage :tests (:use :cl :sb-thread)) 
(in-package :tests)

(defclass thread-queue ()
  ((semaphore
    :initform (make-semaphore :name "thread-queue-semaphore"))
   (in-stack
    :initform nil)
   (out-stack
    :initform nil)))


(defgeneric enqueue-* (queue element)
  (:documentation "adds an element to the queue"))

(defgeneric dequeue-* (queue &key timeout)
  (:documentation "removes and returns the first element to get out"))

(defmethod enqueue-* ((queue thread-queue) element)
  (signal-semaphore (slot-value queue 'semaphore))
  (setf (slot-value queue 'in-stack) (push element (slot-value queue 'in-stack))))


(defmethod dequeue-* ((queue thread-queue) &key timeout)
  (wait-on-semaphore (slot-value queue 'semaphore) :timeout timeout)
  (when (= (length (slot-value queue 'out-stack)) 0)
    (setf (slot-value queue 'out-stack) (reverse (slot-value queue 'in-stack)))
    (setf (slot-value queue 'in-stack) nil))
  (let ((first (car (slot-value queue 'out-stack))))
    (setf (slot-value queue 'out-stack) (cdr (slot-value queue 'out-stack)))
    first))


(defparameter *test* (make-instance 'thread-queue))

(dequeue-* *test* :timeout 5)

(enqueue-* *test* 42)

(enqueue-* *test* 41)

(enqueue-* *test* 40)

(dequeue-* *test* :timeout 5)

(dequeue-* *test* :timeout 5)

(dequeue-* *test* :timeout 5)

(dequeue-* *test* :timeout 5)

Answer 1

您已经拥有了一个 count = 0 的信号量，消费者在此等待。
您还需要一个围绕访问您的堆栈的独占锁(可能每个堆栈一个)，或者一个无锁队列。如果您想要/必须使用信号量，二进制信号量可以用作排他锁。

编辑:
在SBCL中，您已经拥有lock-free queues ，您可能想要使用其中之一而不是两个堆栈。另一种可能性是使用 atomic operations .
最后，如果这仍然不适合您，请使用 mutex , 包装访问和更新内部堆栈的代码 with-mutex或 with-recursive-lock .
请务必使用锁/互斥锁 后 从信号量中醒来，而不是 附近等待信号量，否则你就失去了信号量给你的优势，即有可能连续唤醒多个服务员，而不是一次唤醒一个。
您可以在 SBCL manual 中阅读有关这些内容的所有信息。 .
另外，我认为已经做了一些工作将 SBCL 中每个类似锁的东西重命名为 lock ，根据 this blog post ，但我不知道它的状态，它指出将支持旧名称一段时间。

您几乎肯定还需要一个 count = limit 的信号量用于生产者，以不超过您的队列限制。
在您的 enqueue-* ，您应该向信号量发出信号 后 更新队列。 setf不需要，push已经将列表的新头部存储到位。
在您的 dequeue-* , length应用于列表时是一个冗长的函数，但使用 null 检查列表是否为空很便宜或 endp .而不是走 car并存储 cdr ，您可以使用 pop ，它正是这样做的。