セマフォなしでロックを実装する

Question

私は学校プロジェクトに取り組んでいます（私の制限事項を説明しています）。私の質問は、NACHOSでセマフォなしでロックを実装する方法です。 NACHOSの具体的な回答は素晴らしいですが、私が探しているのは正しい方向へのプッシュです。これまでのところ、私の理解から、モニターはセマフォーを使用するロックを使用しています（mutexは本当です）。最初は、セマフォーをモニターと置き換えてロックを実装すると考えましたが、これは意味をなさないものでした。

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); 

}