Implementing semaphore by using mutex operations and primitives

user_2890398 0
Viewed 20230

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();
}
};
mutex c++11 c++ semaphore
5 Answers

That's true because technically there are some parts in your code that have no need to exist. 1- you used atomic datatypes atomic<int> count; which will take very few more cycles in execution and it is useless as long as incrementing and decrementing are locked by updateMutex.lock(); code so there is no other thread can change it during the locked state.

2- you put while (count >= size) {} which is also useless because you checked count again after the spinlock statement which is necessary and the one important here. "remember spinlock is a while(1)" when the mutex is taken by another thread.

besides if you decided to use int count; with some compiler's optimizations, maybe your code won't re-read count value!! for optimization, remember your semaphore is supposed to be used by different threads!! so you need to make it volatile, to avoid this problem.

at last, let me rewrite your code in a more performant way.

struct Semaphore {
int size;
volatile int count;
mutex updateMutex;

Semaphore(int n) : size(n), count(0) {}

void aquire() {
    while (1) {
        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();
    }

 };
user_170720780

lemme try this

`

# number of threads/workers
w = 10
# maximum concurrency
cr = 5
r_mutex = mutex()
w_mutex = [mutex() for x in range(w)]

# assuming mutex can be locked and unlocked by anyone 
# (essentially we need a binary semaphore)

def acquire(id):

    r_mutex.lock()
    cr -= 1
    # r_mutex.unlock()
    
    # if exceeding maximum concurrency
    if cr < 0:
        # lock twice to be waken up by someone
        w_mutex[id].lock()
        r_mutex.unlock()
        w_mutex[id].lock()
        w_mutex[id].unlock()
        return

    r_mutex.unlock()

    
    
       
def release(id):

    r_mutex.lock()
    cr += 1
    # someone must be waiting if cr < 0
    if cr <= 0:
        # maybe you can do this in a random order
        for w in w_mutex:
            if w.is_locked():
                w.unlock()
                break
    r_mutex.unlock()

`

user_115487870
Related