operating-system - 实现没有信号量的锁

Question

我正在做一个学校项目（解释我在问题中的限制）。我的问题是如何在 NACHOS 中实现没有信号量的锁。虽然 NACHOS 的具体答案会很棒，但我正在寻找的是朝着正确方向的推动。到目前为止，据我了解，监视器使用使用信号量的锁（实际上是互斥锁）。最初我们想用监视器替换信号量来实现锁，然而，这没有意义。

Answer 1

锁可以通过 Thread:Sleep 来实现。

class Lock {
  public:
    Lock(char* debugName);          // initialize lock to be FREE
    ~Lock();                // deallocate lock
    char* getName() { return name; }    // debugging assist

    void Acquire(); // these are the only operations on a lock
    void Release(); // they are both *atomic*

    bool isHeldByCurrentThread() { return (thread == currentThread); }  // true if the current thread
                    // holds this lock.  Useful for
                    // checking in Release, and in
                    // Condition variable ops below.

  private:
    char* name;             // for debugging
    // plus some other stuff you'll need to define
    Thread *thread;     //the thread who holds this lock
    enum value {FREE, BUSY};
    List *queue;
};

Lock::Lock(char* debugName):name(debugName), thread(NULL), value(FREE), queue(new List())
{ }
Lock::~Lock()
{
    delete queue;
}
void Lock::Acquire()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);   // disable interrupts
    if (value == BUSY) {
        queue->Append((void *)currentThread);
        currentThread->Sleep();
    }
    value = BUSY;
    thread = currentThread;
    (void) interrupt->SetLevel(oldLevel);   // re-enable interrupts
}
void Lock::Release()
{
    Thread *nextThread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);   // disable interrupts
    nextThread = (Thread *)queue->Remove();
    if (nextThread != NULL)    // make thread ready, consuming the V immediately
        scheduler->ReadyToRun(nextThread);
    value = FREE;
    (void) interrupt->SetLevel(oldLevel);   // re-enable interrupts
}

Answer 2

您可能想考虑执行忙等待且不需要信号量的自旋锁。但是在单处理器中不使用自旋锁。

Answer 3

首先检查锁的当前持有者是否是当前线程。然后使用中断开关和睡眠来实现锁定。线程从睡眠中唤醒后，它应该再次检查锁是忙还是空闲，因为唤醒线程只会将它传递到就绪队列。同时，其他线程可能会在该线程获得锁之前再次获得锁。

void Lock::Acquire() {
    ASSERT(!isHeldByCurrentThread());  // cannot acquire a lock twice

    IntStatus oldLevel = interrupt->SetLevel(IntOff);   // disable interrupts
    while (freeOrBusy == 'b') {
        queue->Append((void *)currentThread);
        currentThread->Sleep();
    }
    freeOrBusy = 'b';
    currentHolder = currentThread;
    (void) interrupt->SetLevel(oldLevel);   // re-enable interrupts
}

void Lock::Release() {
    ASSERT(isHeldByCurrentThread());

    IntStatus oldLevel = interrupt->SetLevel(IntOff);
    freeOrBusy = 'f';
    currentHolder = NULL;

    Thread *thread = (Thread *)queue->Remove();   // "queue" is the list of threads waiting
    if (thread != NULL)    // make thread ready
       scheduler->ReadyToRun(thread);  

    (void) interrupt->SetLevel(oldLevel);

}