Critical Sections

The proper use of the built-in procedures in Critical Sections for handling the concurrency with other threads.

Preamble:

A critical section is a part of a multi-threading program that has to be executed as atomic actions (no concurrence with other threads executing similar actions):

- It is a piece of a program that requires mutual exclusion of access.
- Typically, the critical section accesses a shared resource, such as a data structure, a peripheral device, or a network connection, that does not allow multiple concurrent accesses.

When a program starts up, one thread already begins running immediately. This is usually called the "main" thread of the program, because it is the one that is executed when a program begins:

- It is the thread from which user may spawn other "child" threads (which in turn may spawn other "sub-child" threads).
- Often, it must be the last thread to finish execution because it performs various shutdown actions (as a "child" thread must also do so with respect to its eventual "sub-child" threads spawned).
- But other than that, it can also compete (with its own critical sections) with all other threads explicitly spawned by user.

Basic algorithms

Using the built-in procedures provided by FreeBASIC, the method to ensure exclusive use of a critical section may be designed in a algorithm either asynchronous or synchronous, which applies to the threads.

Basic algorithm for an asynchronous method using a mutex:

By getting the mutex locking, the thread can take the exclusive control to access the shared resource.
When shared resource access is ended, the thread unlocks the mutex.

Algorithm:

'   Mutexlock
'   |
'   Critical section of code
'   |
'   Mutexunlock

Basic algorithm for a synchronous method using a condwait then a condsignal/condbroadcast (and mutex):

The thread waits for a Boolean predicate is indeed true and also a condition signal (condwait) before executing its critical section.
When shared resource access is ended, the thread sets another Boolean predicate then sends a condition signal to other thread(s) (condsignal or condbroadcast).

Algorithm:

'   Mutexlock
'   |
'   While my_predicate <> True
'   |   Condwait
'   Wend
'   my_predicate = False
'   |
'   Critical section of code
'   |
'   other_predicate = True
'   Condsignal or Condbroadcast
'   |
'   Mutexunlock

Similar algorithm with waiting-for, then signaling are put in reverse order:

'   Mutexlock
'   |
'   Critical section of code
'   |
'   other_predicate = True
'   Condsignal or Condbroadcast
'   |
'   While my_predicate <> True
'   |   Condwait
'   Wend
'   my_predicate = False
'   |
'   Mutexunlock

Examples

In the two following examples, the shared resource is the input/output display device:

- Print its counter for each of 6 user threads (and read the flag 'quit').
- Catching a key-press (any one) for the main thread (and if yes, set the flag 'quit' to 'true').

The outputting procedure ('Sub Counter()') has voluntarily a tempo between cursor positioning and printing, and also a repositioning of text cursor at middle of line before ending, in order to thoroughly check that there is no overlap between the critical sections executions (at opposite, one can see the result by removing some code dedicated to mutual exclusion processing).
A different tempo value is set at the end of each thread loop (from smaller to bigger).
A structure (UDT) groups all variables necessary to the threads. A pointer to each UDT instance is passed to each thread at its creation phase (with threadcreate).

Asynchronous method example using one mutex for all threads:

' User thread algorithm (same principle for the main thread):
'
'   Do
'   |
'   |   Mutexlock
'   |   |
'   |   Critical section of code
'   |   |
'   |   Mutexunlock
'   |   |
'   |   Sleep my_tempo, 1
'   |
'   Loop Until quit = true
'
' There is no any advantage or disadvantage between threads for running their critical sections.

Type UDT
Dim As Integer number
Dim As Integer tempo
Dim As Any Ptr pThread
Dim As ULongInt count
Static As Any Ptr pMutex
Static As Integer numberMax
Static As Integer quit
End Type
Dim As Any Ptr UDT.pMutex
Dim As Integer UDT.numberMax
Dim As Integer UDT.quit

Sub Counter (ByVal pt As UDT Ptr)
With *pt
Locate .number, .number, 0
Sleep 5, 1
.count += 1
Print .count;
Locate .number, 30 + .number, 0
End With
End Sub

Sub Thread (ByVal p As Any Ptr)
Dim As Integer myquit
Dim As UDT Ptr pUDT = p
With *pUDT
Do
MutexLock(.pMutex)
Counter(pUDT)
myquit = .quit
MutexUnlock(.pMutex)
Sleep .tempo, 1
Loop Until myquit = 1
End With
End Sub

UDT.numberMax = 6
Dim As UDT u(0 To UDT.numberMax)
For I As Integer = 0 To UDT.numberMax
u(I).number = i
u(I).tempo = 100 + 15 * I - 95 * Sgn(I)
Next I
UDT.pMutex = MutexCreate

Dim As Single t = Timer
For I As Integer = 1 To UDT.numberMax
u(I).pThread = ThreadCreate(@Thread, @u(I))
Next I

Dim As String s
Do
MutexLock(UDT.pMutex)
s = Inkey
If s <> "" Then
UDT.quit = 1
End If
MutexUnlock(UDT.pMutex)
Sleep u(0).tempo, 1
Loop Until s <> ""

For I As Integer = 1 To UDT.numberMax
ThreadWait(u(I).pThread)
Next I
t = Timer - t

MutexDestroy(UDT.pMutex)
Dim As ULongInt c
For I As Integer = 1 To UDT.numberMax
c += u(I).count
Next I
Locate UDT.numberMax+2, 1
Print CULngInt(c / t) & " increments per second"

Sleep

Output example:

'   159
'    127
'     105
'      85
'       78
'        71
'
'   63 increments per second

Different result values because asynchronous counting (decreasing count values because increasing tempo values).

Synchronous method example using a condwait then a condbroadcast (and one mutex) for all threads:

' User thread algorithm (same principle for the main thread):
'
'   Do
'   |
'   |   Mutexlock
'   |   |
'   |   While thread_priority_number <> my_number
'   |   |   Condwait
'   |   Wend
'   |   |
'   |   Critical section of code
'   |   |
'   |   thread_priority_number = next thread_priority_number
'   |   Condbroadcast
'   |   |
'   |   Mutexunlock
'   |   |
'   |   Sleep my_tempo, 1
'   |
'   Loop Until quit = true
'
' The critical sections of the threads are run synchronously one after the other, with a predefined order.

Type UDT
Dim As Integer number
Dim As Integer tempo
Dim As Any Ptr pThread
Dim As ULongInt count
Static As Integer threadPriorityNumber
Static As Any Ptr pMutex
Static As Any Ptr pCond
Static As Integer numberMax
Static As Integer quit
End Type
Dim As Integer UDT.threadPriorityNumber
Dim As Any Ptr UDT.pMutex
Dim As Any Ptr UDT.pCond
Dim As Integer UDT.numberMax
Dim As Integer UDT.quit

Sub Counter (ByVal pt As UDT Ptr)
With *pt
Locate .number, .number, 0
Sleep 5, 1
.count += 1
Print .count;
Locate .number, 30 + .number, 0
End With
End Sub

Sub Thread (ByVal p As Any Ptr)
Dim As Integer myquit
Dim As UDT Ptr pUDT = p
With *pUDT
Do
MutexLock(.pMutex)
While .threadPriorityNumber <> .number '' synchronous condwait for expected condition
CondWait(.pCond, .pMutex)
Wend
Counter(pUDT)
myquit = .quit
.threadPriorityNumber = (.threadPriorityNumber + 1) Mod (.numberMax + 1)
CondBroadcast(.pCond)
MutexUnlock(.pMutex)
Sleep .tempo, 1
Loop Until myquit = 1
End With
End Sub

UDT.numberMax = 6
Dim As UDT u(0 To UDT.numberMax)
For I As Integer = 0 To UDT.numberMax
u(I).number = i
u(I).tempo = 100 + 15 * I - 95 * Sgn(I)
Next I
UDT.pMutex = MutexCreate
UDT.PCond = CondCreate

Dim As Single t = Timer
For I As Integer = 1 To UDT.numberMax
u(I).pThread = ThreadCreate(@Thread, @u(I))
Next I

Dim As String s
Do
MutexLock(UDT.pMutex)
While UDT.threadPriorityNumber <> u(0).number
CondWait(UDT.pCond, UDT.pMutex)
Wend
s = Inkey
If s <> "" Then
UDT.quit = 1
End If
UDT.threadPriorityNumber = (UDT.threadPriorityNumber + 1) Mod (UDT.numberMax + 1)
CondBroadcast(UDT.pCond)
MutexUnlock(UDT.pMutex)
Sleep u(0).tempo, 1
Loop Until s <> ""

For I As Integer = 1 To UDT.numberMax
ThreadWait(u(I).pThread)
Next I
t = Timer - t

MutexDestroy(UDT.pMutex)
CondDestroy(UDT.pCond)
Dim As ULongInt c
For I As Integer = 1 To UDT.numberMax
c += u(I).count
Next I
Locate UDT.numberMax+2, 1
Print CULngInt(c / t) & " increments per second"

Sleep

Output example:

'   116
'    116
'     116
'      116
'       116
'        116
'
'   51 increments per second

Same result values because synchronous counting (despite of increasing tempo values).

Weird synchronous algorithm using a mutex for each thread, by self lock and mutual unlock:

- When one thread has run its critical section, it unlocks the mutex of the next thread and attempts to re-obtain its own mutex.
- At initialization all mutexes are locked, except the mutex of the main thread.

' User thread (#N) algorithm (same principle for the main thread):
'
'   Do
'   |
'   |   Mutexlock(own thread mutex (#N))
'   |   |
'   |   Critical section of code
'   |   |
'   |   Mutexunlock(next thread mutex (#N+1))
'   |   |
'   |   Sleep tempo, 1
'   |
'   Loop Until quit = 1

Type UDT
Dim As Integer number
Dim As Integer tempo
Dim As Any Ptr pThread
Dim As ULongInt count
Static As Any Ptr pMutex(Any)
Static As Integer numberMax
Static As Integer quit
End Type
Dim As Any Ptr UDT.pMutex(Any)
Dim As Integer UDT.numberMax
Dim As Integer UDT.quit

Sub Counter (ByVal pt As UDT Ptr)
With *pt
Locate .number, .number, 0
Sleep 5, 1
.count += 1
Print .count;
Locate .number, 30 + .number, 0
End With
End Sub

Sub Thread (ByVal p As Any Ptr)
Dim As Integer quit
Dim As UDT Ptr pUDT = p
With *pUDT
Do
MutexLock(.pMutex(.number))
Counter(pUDT)
quit = .quit
MutexUnlock(.pMutex((.number + 1) Mod (UDT.numberMax + 1)))
Sleep .tempo, 1
Loop Until quit = 1
End With
End Sub

UDT.numberMax = 6
ReDim UDT.pMutex(UDT.numberMax)
Dim As UDT u(0 To UDT.numberMax)
For I As Integer = 0 To UDT.numberMax
u(I).number = i
u(I).tempo = 100 + 15 * I - 95 * Sgn(I)
UDT.pMutex(I) = MutexCreate
MutexLock(UDT.pMutex(I))
Next I
MutexUnlock(UDT.pMutex(u(0).number))

Dim As Single t = Timer
For I As Integer = 1 To UDT.numberMax
u(I).pThread = ThreadCreate(@Thread, @u(I))
Next I

Dim As String s
Do
MutexLock(UDT.pMutex(u(0).number))
s = Inkey
If s <> "" Then
UDT.quit = 1
End If
MutexUnlock(UDT.pMutex((u(0).number + 1) Mod (UDT.numberMax + 1)))
Sleep u(0).tempo, 1
Loop Until s <> ""

For I As Integer = 1 To UDT.numberMax
ThreadWait(u(I).pThread)
Next I
t = Timer - t

For I As Integer = 0 To UDT.numberMax
MutexDestroy(UDT.pMutex(I))
Next I
Dim As ULongInt c
For I As Integer = 1 To UDT.numberMax
c += u(I).count
Next I
Locate UDT.numberMax+2, 1
Print CULngInt(c / t) & " increments per second"

Sleep

Output example:

'   102
'    102
'     102
'      102
'       102
'        102
'
'   51 increments per second

Same result values because synchronous counting (despite of increasing tempo values).

See also

Back to Programmer's Guide

Critical Sections - FreeBASIC Wiki Manual | FBWiki

Critical Sections