Implementing semaphore by using mutex operations a

问题:

Some time ago had an interview and was asked to implement Semaphore by using mutex operations and primitives only (he allowed int to be considered as atomic). I came with solution below. He did not like busy/wait part -- while (count >= size) {} -- and asked to implement locking instead by using more primitive types and mutexes. I did not manage to come with improved solution. Any ideas how it could be done?

struct Semaphore {
int size;
atomic<int> count;
mutex updateMutex;

Semaphore(int n) : size(n) { count.store(0); }

void aquire() {
    while (1) {
        while (count >= size) {}
        updateMutex.lock();
        if (count >= size) {
            updateMutex.unlock();
            continue;
        }
        ++count;
        updateMutex.unlock();
        break;
    }
}

void release() {
    updateMutex.lock();
    if (count > 0) {
        --count;
    } // else log err
    updateMutex.unlock();
}
};

回答1:

EDIT - use a second mutex for queuing intstead of threads

Since a mutex already have proper thread-support, it can be used to queue the threads (instead of doing it explicitly as I first had tried to do). Unless the mutex is restricted to only let the owner unlock it (a lock?), then this solution doesn't work.

I found the solution in Anthony Howe's pdf that I came across when searching. There are two more solutions given there as well. I changed the names to make more sense for this example.

more or less pseudo code:

Semaphore{
    int n;
    mutex* m_count;         //unlocked initially
    mutex* m_queue;         //locked initially
};

void wait(){
    m_count.lock();
    n = n-1;
    if(n < 0){
        m_count.unlock();
        m_queue.lock();     //wait
    }
    m_count.unlock();       //unlock signal's lock
}

void signal(){
    m_count.lock();
    n = n+1;

    if(n <= 0){
        m_queue.unlock();   //leave m_count locked
    }
    else{
        m_count.unlock();
    }
}

回答2:

I'd wager this is not possible to implement without a busy-loop using mutexes only.

If not busy-looping, you have to block somewhere. The only blocking primitive you've got is a mutex. Hence, you have to block on some mutex, when the semaphore counter is zero. You can be woken up only by the single owner of that mutex. However, you should woken up whenever an arbitrary thread returns a counter to the semaphore.

Now, if you are allowed condition variables, it's an entirely different story.

回答3:

as @chill pointet out, the solution I did write down here will not work, as locks have unique ownership. I guess in the end you will revert to busy wait (if you are not allowed to use condition variables). I leave it here if ppl. have the same idea they see that this DOES NOT WORK ;)

struct Semaphore {
int size;
atomic<int> count;
mutex protection;
mutex wait;

Semaphore(int n) : size(n) { count.store(0); }

void aquire() {
    protection.lock();
    --count;
    if (count < -1) {
        protection.unlock();
        wait.lock();
    }
    protection.unlock();
}

void release() {
    protection.lock();
    ++count;
    if (count > 0) {
        wait.unlock();
    }
    protection.unlock();
}
};