Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implementing semaphore by using mutex operations and primitives

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();
}
};
like image 488
user2890398 Avatar asked Dec 12 '13 04:12

user2890398


People also ask

Can you implement a semaphore using the mutex?

Any problem that can be solved with semaphores can also be solved with condition variables and mutexes. We can prove that's true by using condition variables and mutexes to implement a semaphore.

What is semaphores explain about its uses to implement mutex?

The correct use of a semaphore is for signaling from one task to another. A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects. By contrast, tasks that use semaphores either signal or wait—not both.

How semaphore is implemented?

Semaphore implementation Semaphores can be implemented inside the operating system by interfacing with the process state and scheduling queues: a thread that is blocked on a semaphore is moved from running to waiting (a semaphore-specific waiting queue).

What is semaphore primitive?

A semaphore is a very general synchronization primitive, and most other synchronization operations can be reduced to semaphore operations (this is how Nachos implements locks and condition variables). Semaphores are in most cases too basic an abstraction to be used effectively.


1 Answers

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.

like image 82
chill Avatar answered Sep 23 '22 03:09

chill