通过使用互斥操作和原语来实现信号量 [英] Implementing semaphore by using mutex operations and primitives

问题描述

前一段时间有一个采访，并要求实现
Semaphore通过使用互斥操作和原语只有
（他允许int被认为是原子的）。我下面的解决方案。
他不喜欢忙/等待部分 - while（count> = size）{} - 并要求实现锁定，而使用更原始的
类型和互斥体。我没有设法带来改进的解决方案。
任何想法如何做？

  struct Semaphore {
 int size; 
 atomic< int>计数; 
 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（）; 
} 
}; 
  

解决方案

我相信发布函数在我的）应该告诉等待线程运行，而不是让下一个线程忙等待。

我没有在C ++中编程，但这样的东西可能是他们在想什么。线程支持通常包括从操作系统虽然...我因此不知道是否是一个原始。

伪代码：

  Semaphore {
 int n; 
 int size; 
 thread_queue waitQ; //线程等待信号量
 mutex * m1; 
}; 
 
 void wait（）{
 m1.lock（）; 
 if（n> 0&& n< size）{
 n = n-1; 
 m1.unlock（）; 
} 
 else {
 waitQ.enqueue（current_thread）; //将线程添加到队列
 m1.unlock（）; 
 block_thread（）; // block this thread 
} 
} 
 
 void signal（）{
 m1.lock（）; 
 if（waitQ！= EMPTY）{
 p = s.waitQ.dequeue（）; // dequeue next thread waiting 
 m1.unlock（）; 
 wake_thread（p）; //在队列中运行下一个线程
 else {
 n = n + 1; 
 m1.unlock（）; 
} 
} 
  

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

解决方案

I believe that the release function (signal in mine) should tell the waiting thread to run instead of letting next thread busy-wait.

I haven't programmed in C++ before but something like this might be what they had in mind. The thread-support is usually included from the OS though... I'm therefore not sure if it is a primative.

pseudo code:

            Semaphore{
                int n;
                int size;
                thread_queue waitQ; //threads waiting for semaphore
                mutex* m1; 
            };

            void wait(){
                m1.lock();
                if(n > 0 && n < size){
                    n = n - 1;
                    m1.unlock();
                    }
                else{
                    waitQ.enqueue(current_thread); //add thread to queue
                    m1.unlock();
                    block_thread(); //block this thread
                }
            }

            void signal(){
                m1.lock();
                if(waitQ != EMPTY){
                    p = s.waitQ.dequeue(); //dequeue next thread waiting
                    m1.unlock();
                    wake_thread(p); //run next thread in queue
                else{
                    n = n + 1;
                    m1.unlock();
                }
            }

这篇关于通过使用互斥操作和原语来实现信号量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！