实现没有信号量的锁

Question

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

Answer 1

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

Answer 2

锁可以通过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 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); 

}