How to create a FIFO/strong semaphore

Question

I need to code my own FIFO/strong semaphore in C#, using a semaphore class of my own as a base. I found this example, but it's not quite right since I'm not supposed to be using Monitor.Enter/Exit yet.

These are the methods for my regular semaphore, and I was wondering if there was a simple way to adapt it to be FIFO.

public virtual void Acquire()
{

    lock (this)
    {

        while (uintTokens == 0)
        {

            Monitor.Wait(this);

        }

        uintTokens--;

    }

}

public virtual void Release(uint tokens = 1)
{

    lock (this)
    {

        uintTokens += tokens;
        Monitor.PulseAll(this);

    }

}

Not quite pertinent to your question, but you may want to avoid using `lock(this)` code pattern as it can lead to deadlocks. See http://stackoverflow.com/a/251668/1556108 — LB2, May 01 '14 at 20:13
Do you mean to use ConcurrentQueue as a base? The teacher wanted us to make all the utilities for ourselves, so we don't use any inbuilt concurrency tools. I have my own Channel class though. Thanks for the tip LB2, the teacher had no problem with it but I'll get around to changing it anyway. — SlashThingy, May 01 '14 at 20:24
I checked the source code of [`SemaphoreSlim.WaitAsync`](https://referencesource.microsoft.com/mscorlib/system/threading/SemaphoreSlim.cs.html#4772c1d9756a4a9a), and it seems that it is FIFO already. Each task created for the awaiting is stored in a queue implemented as a double linked list. — Theodor Zoulias, Jun 04 '20 at 07:11

Servy · Answer 1 · 2014-05-01T20:23:57.650

So SemaphoreSlim gives us a good starting place, so we'll begin by wrapping one of those in a new class, and directing everything but the wait method to that semaphore.

To get a queue like behavior we'll want a queue object, and to make sure it's safe in the face of multithreaded access, we'll use a ConcurrentQueue.

In this queue we'll put TaskCompletionSource objects. When we want to have something start waiting it can create a TCS, add it to the queue, and then inform the semaphore to asynchronously pop the next item off of the queue and mark it as "completed" when the wait finishes. We'll know that there will always be an equal or lesser number of continuations as there are items in the queue.

Then we just wait on the Task from the TCS.

We can also trivially create a WaitAsync method that returns a task, by just returning it instead of waiting on it.

public class SemaphoreQueue
{
    private SemaphoreSlim semaphore;
    private ConcurrentQueue<TaskCompletionSource<bool>> queue =
        new ConcurrentQueue<TaskCompletionSource<bool>>();
    public SemaphoreQueue(int initialCount)
    {
        semaphore = new SemaphoreSlim(initialCount);
    }
    public SemaphoreQueue(int initialCount, int maxCount)
    {
        semaphore = new SemaphoreSlim(initialCount, maxCount);
    }
    public void Wait()
    {
        WaitAsync().Wait();
    }
    public Task WaitAsync()
    {
        var tcs = new TaskCompletionSource<bool>();
        queue.Enqueue(tcs);
        semaphore.WaitAsync().ContinueWith(t =>
        {
            TaskCompletionSource<bool> popped;
            if (queue.TryDequeue(out popped))
                popped.SetResult(true);
        });
        return tcs.Task;
    }
    public void Release()
    {
        semaphore.Release();
    }
}

There's a lot of things in there that we haven't been taught, which means that we're not really meant to use them. Wait, for example. Also, I have my own Channel class (thread-safe queue), which I suppose can be used. — SlashThingy, May 01 '14 at 20:24
@FreddieAppsHero You're welcome to follow the same model using your own tools, if you prefer. — Servy, May 01 '14 at 20:27
My own semaphores lacks WaitAsync, and it'd probably be frowned upon to extend it any more. — SlashThingy, May 01 '14 at 20:33
Note that when a Task becomes completed as a result of SetResult, the TaskScheduler might decide to inline the execution, or schedule the execution. E.g. you have no real FIFO guarantee with this implementation I believe. Came here, because I built something similar, which I believe doesn't have the strong FIFO guarantee either. — Tohnmeister, Dec 12 '22 at 09:52
@Tohnmeister Indeed, doing a simple test this is not working as expected — kbronctjr, Mar 28 '23 at 13:09

score 1 · Answer 2 · answered Dec 31 '18 at 09:47

I have created a FifoSemaphore class and I am successfully using it in my solutions. Current limitation is that it behaves like a Semaphore(1, 1).

public class FifoSemaphore
{
    private readonly object lockObj = new object();

    private List<Semaphore> WaitingQueue = new List<Semaphore>();


    private Semaphore RequestNewSemaphore()
    {
        lock (lockObj)
        {
            Semaphore newSemaphore = new Semaphore(1, 1);
            newSemaphore.WaitOne();
            return newSemaphore;
        }
    }

    #region Public Functions

    public void Release()
    {
        lock (lockObj)
        {
            WaitingQueue.RemoveAt(0);
            if (WaitingQueue.Count > 0)
            {
                WaitingQueue[0].Release();
            }
        }
    }

    public void WaitOne()
    {
        Semaphore semaphore = RequestNewSemaphore();
        lock (lockObj)
        {
            WaitingQueue.Add(semaphore);
            semaphore.Release();

            if(WaitingQueue.Count > 1)
            {
                semaphore.WaitOne();
            }
        }
        semaphore.WaitOne();

    }

    #endregion
}

Usage is just like with a regular semaphore:

FifoSemaphore fifoSemaphore = new FifoSemaphore();

On each thread:

fifoSemaphore.WaitOne();
//do work
fifoSemaphore.Release();

How to create a FIFO/strong semaphore

2 Answers2

Linked