Implement locks without semaphores

Question

I am working on a school project (explains my restrictions in the question). My question is how to implement locks without semaphores in NACHOS. Although a NACHOS specific answer would be great, what I am looking for is a push in the right direction. So far, from my understanding, monitors use locks which use semaphores (mutexes really). Initially we thought to replace semaphores with monitors to implement locks, however, that didn't make sense.

Are you allowed to disable interrupts? – templatetypedef Feb 16 '12 at 00:53 — templatetypedef, Feb 16 '12 at 00:53

score 0 · Answer 1 · answered Dec 08 '12 at 06:13

Lock can be implemented by 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
}

score 0 · Answer 2 · answered Apr 22 '17 at 17:55

At first check whether the current holder of the lock is the current thread or not. Then use interrupt on-off and sleep to achieve lock. After a thread wakes from sleep, it should again check whether the lock is busy or free, because waking up a thread only passes it to the ready queue. Some other thread may meanwhile acquire the lock again before this thread can acquire the lock.

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

}

score 0 · Answer 3 · answered Feb 16 '12 at 00:40

0

You might want to think about spin-locks which do busy-waiting and do not require semaphore.However in a uniprocessor spin-locks are not used.

answered Feb 16 '12 at 00:40

vjain27

3,514
9
41
60

Implement locks without semaphores

3 Answers3