Fair Critical Section (Linux)

Is Entrance into a Windows Critical Section an atomic operation?

You read done outside the critical section. That is a race condition. If you want to look at the value of done, you need to do it before you leave the critical section.

You might see a write to done from another thread, triggering the assert before the write to criticalValue is visible to the thread that saw the write to done.

If the critical section protects criticalValue and done, then it is an error to access either of them without being in the critical section unless you are sure every thread that might access them has terminated. Your code violates this rule.

providing critical section for threads in c++

Just use two counters and a boolean to implement a basic "take a number" scheme.

One counter, released_thread, indicates which thread may proceed. This is logically equivalent to the "now serving" indicator.

The other, next_waiter, indicates which thread waits next. This is logically equivalent to the next number that will be taken

A boolean indicates whether the thread is permitted to proceed and when it is finished, so the executive knows when to call the next number.

The algorithms are as follows:

To wait:

1. Acquire the lock.

2. Note the value of the next_waiter variable and increment it.

3. Broadcast (notify all) the condition variable.

4. Wait on the condition variable until the boolean is true and the released_thread counter is equal to the value noted in step 2.

5. Release the lock.

6. When finished, acquire the lock, set the boolean to false, broadcast the condition variable, and release the lock.

Executive:

1. Acquire the lock.

2. Wait on the condition variable until the boolean is false and next_waiter is not equal to released_thread.

3. Increment released_thread and set the boolean to true.

4. Broadcast the condition variable.

5. Go to step 2.

Fairness: Where can it be better handled?

There has been research done on revoking ownership of mutexes in order to ensure equal sharing or to detect and avert deadlock. However, this really is overkill and not worth the effort, especially since it opens up a whole new can of worms such as how a program should behave if it was in the midst of some computation and it lost ownership of its resources. It's really up to the application to ensure that its various threads play fair with with each other and consume resources in a way that won't deadlock.

I should point out that there is another option, albeit of a slightly different variety, and that is the use of the message passing style of parallel programming. With message passing, the synchronization is all implicit in the communication; no explicit synchronization is required, which helps to avert such errors.

Synchronization between threads using Critical Section

The real problem here is "ThreadA is always in critical section". ThreadA should not be locking the critical section indefinitely.

In C#, your code for ThreadA would look something like:

Message message;

// Only lock critical section for the time it takes to modify the queue
lock(_messageQueueLock){
   message = _messageQueue.Dequeue();
}

// do something with the message

In my opinion, the following general rules of thumb should be observed when using critical sections:

• Enter and exit the critical section as quickly as possible (i.e. minimize the amount of code in the critical section).
• Use critical sections to protect a resource/asset (e.g. shared memory, queue, list, etc.)
• Avoid using critical sections to protect function/method calls. If you are making function/method calls from within a critical section... you are increasing the probability of creating deadlocks.
• Avoid trying to lock a critical section from within a critical section. Failing to do so may result in potential deadlocks within your application.
• Avoid trying to access an external resource (e.g. executing a database SQL query) while in a critical section.
• Where it makes sense, I generally like to use the following naming convention for critical sections: if the asset that is being protected is called messageQueue... then I would name the critical section messageQueueLock

Great quote from Microsoft: "When you use multithreading of any sort, you potentially expose yourself to very serious and complex bugs" [SOURCE: MSDN]

Same critical section being called in function and subfunction

Is my analysis correct and does this mean that it's advised to have different critical sections for main and sub functions?

From Microsoft Docs (emphasis mine):

After a thread has ownership of a critical section, it can make
additional calls to EnterCriticalSection or TryEnterCriticalSection
without blocking its execution. This prevents a thread from
deadlocking itself while waiting for a critical section that it
already owns. The thread enters the critical section each time
EnterCriticalSection and TryEnterCriticalSection succeed. A thread
must call LeaveCriticalSection once for each time that it entered the
critical section.

So no, what you described should not happen. It is perfectly fine to enter the critical section multiple times and it is required to leave it exactly as many times.

---

Related Topics