How to Manage a Critical Section of the code of a Thread in FB

Forum for discussion about the documentation project.
fxm
Posts: 8348
Joined: Apr 22, 2009 12:46
Location: Paris (suburb), FRANCE

How to Manage a Critical Section of the code of a Thread in FB

Postby fxm » Dec 14, 2015 19:15

A critical section is a part of a multi-threading program that may not be concurrently executed by more than one of the program processes:
- 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.

The algorithm to ensure exclusive use of a critical section may be designed either in a process either asynchronous or synchronous, which applies to the threads.


1) ASYNCHRONOUS PROCESS EXAMPLES

1.1) Asynchronous process using one flag (a boolean variable) per thread
By putting 'true' its own flag means that the thread wants take the exclusive control to access the shared resource (when shared resource access is ended, the thread resets its own flag to 'false').

1.1.1) Asynchronous wait for expected condition, including a sleep in order to release CPU time
After putting its own flag to 'true', the thread waits that all other flags are set to 'false' before entering its critical section.
When shared resource access is ended, the thread resets its own flag to 'false'.

Algorithm:

Code: Select all

'   my_thread_flag = true
'   Do
'   |  Sleep 5
'   Loop Until number_of_thread_flag_true = 1
'   .....
'   Critical section of code
'   .....
'   my_thread_flag = false
This algorithm does not work because of the case of infinite blocking of the thread in its waiting loop (as soon as at least 2 threads wait at same time).

1.1.2) Asynchronous jump if not expected condition
After putting its own flag to 'true', the thread verifies if all other flags are set to 'false' before entering its critical section, otherwise the thread jumps its critical section and continues.
In all cases (after running its critical section or only jumping), the thread resets its own flag to 'false'.

Algorithm:

Code: Select all

'   my_thread_flag = true
'   If number_of_thread_flag_true = 1 Then
'   | .....
'   | Critical section of code
'   | .....
'   End If
'   my_thread_flag = false
There is no case of infinite blocking of the thread, but in general, some threads may be strongly advantaged or disadvantaged compared to others for running their critical sections.

1.1.3) Asynchronous repeat awake then sleep, until expected condition
After putting its own flag to 'true', the thread verifies if all other flags are set to 'false' before entering its critical section, otherwise the thread resets its own flag to 'false' before sleeping up to a new attempt.
When shared resource access is ended, the thread resets its own flag to 'false'.

Algorithm:

Code: Select all

'   Do
'   |  my_thread_flag = true
'   |  If number_of_thread_flag_true = 1 Then
'   |  |  Exit Do
'   |  End If
'   |  my_thread_flag = false
'   |  Sleep 5
'   Loop
'   .....
'   Critical section of code
'   .....
'   my_thread_flag = false
There is no case of infinite blocking of the thread, but in general, some threads may be strongly advantaged or disadvantaged compared to others for running their critical sections.

1.2) Asynchronous process using one mutex for all threads
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:

Code: Select all

'   Mutexlock
'   | .....
'   | Critical section of code
'   | .....
'   Mutexunlock
There is no any advantage or disadvantage between threads for running their critical sections.


2) SYNCHRONOUS PROCESS EXAMPLES

2.1) Synchronous process using a priority number among the threads
The thread which has the priority runs its critical section, then passes the priority to the next thread.

2.1.1) Synchronous wait for expected condition, including a sleep in order to release CPU time
The thread waits for its turn before executing its critical section.
When shared resource access is ended, the thread passes the priority to the next thread in the thread number list.

Algorithm:

Code: Select all

'   While thread_priority_number <> my_number
'   |  Sleep 5
'   Wend
'   .....
'   Critical section of code
'   .....
'   thread_priority_number = next thread_priority_number
The critical sections of the threads are run synchronously one after the other, with a predefined order.

2.1.2) Synchronous wait for expected condition, including a condwait then a condbroadcast (and mutex) in order to release CPU time
The thread waits for its turn and also a condition signal (condwait) before executing its critical section.
When shared resource access is ended, the thread passes the priority to the next thread in the thread number list, then send a condition signal to all other threads (condbroadcast).

Algorithm:

Code: Select all

'   Mutexlock
'   |  While thread_priority_number <> my_number
'   |  |  Condwait
'   |  Wend
'   |  .....
'   |  Critical section of code
'   |  .....
'   |  thread_priority_number = next thread_priority_number
'   |  Condbroadcast
'   Mutexunlock
The critical sections of the threads are run synchronously one after the other, with a predefined order.

2.2) Synchronous process 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, and the main thread enters directly in its critical section (code of the main thread slightly different of the other thread, with the self lock pushed at end).

Algorithm for main thread (#0):

Code: Select all

'   |  .....
'   |  Critical section of code
'   |  .....
'   Mutexunlock(next thread mutex (#0+1))
'   Mutexlock(own thread mutex (#0))
Algorithm for user thread (#N):

Code: Select all

'   Mutexlock(own thread mutex (#N))
'   |  .....
'   |  Critical section of code
'   |  .....
'   Mutexunlock(next thread mutex (#N+1))
The critical sections of the threads are run synchronously one after the other, with a predefined order.


See all the examples in the following post.
Last edited by fxm on May 10, 2018 11:14, edited 14 times in total.
fxm
Posts: 8348
Joined: Apr 22, 2009 12:46
Location: Paris (suburb), FRANCE

Re: How to Manage a Critical Section of the code of a Thread in FB

Postby fxm » Dec 14, 2015 19:18

All examples for the previous post:

In the 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 exclusion processing).

- Example for §1.1.1: Asynchronous wait for expected condition, including a sleep in order to release CPU time

Code: Select all

' User thread algorithm (same principle for the main thread):
'
'   Do
'   |  my_thread_flag = true
'   |  Do
'   |  |  Sleep 5
'   |  Loop Until number_of_thread_flag_true = 1
'   |  .....
'   |  Critical section of code
'   |  .....
'   |  my_thread_flag = false
'   |  Sleep my_tempo
'   Loop Until quit = true
'
' This algorithm does not work because of the case of infinite blocking of the thread in its waiting loop (as soon as at least 2 threads wait at same time).


Type UDT
  Dim As Integer number
  Dim As Integer tempo
  Dim As Any Ptr pThread
  Dim As Ulongint count
  Static As Integer threadFlagArray(Any)
  Static As Integer numberMax
  Static As Integer quit
  Declare Static Function NumberOfThreadFlag () As Integer
End Type
Dim As Integer UDT.threadFlagArray(Any)
Dim As Integer UDT.numberMax
Dim As Integer UDT.quit
Static Function UDT.NumberOfThreadFlag () As Integer
  Dim As Integer n
  For I As Integer = 0 To UDT.numberMax
    n += UDT.threadFlagArray(I)
  Next I
  Return n
End Function

Sub Counter (Byval pt As UDT Ptr)
  With *pt
    Locate .number, .number, 0
    Sleep 5
    .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
      .threadFlagArray(.number) = 1
      Do
        Sleep 5
      Loop Until .NumberOfThreadFlag() = 1
      Counter(pUDT)
      quit = .quit
      .threadFlagArray(.number) = 0
      Sleep .tempo
    Loop Until quit = 1
  End With
End Sub


UDT.numberMax = 6
Redim UDT.threadFlagArray(0 To 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)
Next I


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
  UDT.threadFlagArray(u(0).number) = 1
  Do
    Sleep 5
  Loop Until UDT.NumberOfThreadFlag() = 1
  s = Inkey
  If s <> "" Then
    UDT.quit = 1
  End If
  UDT.threadFlagArray(u(0).number) = 0
  Sleep u(0).tempo
Loop Until s <> ""

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

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
Blocking for that process!

- Example for §1.1.2: Asynchronous jump if not expected condition

Code: Select all

' User thread algorithm (same principle for the main thread):
'
'   Do
'   |  my_thread_flag = true
'   |  If number_of_thread_flag_true = 1 Then
'   |  | .....
'   |  | Critical section of code
'   |  | .....
'   |  End If
'   |  my_thread_flag = false
'   |  Sleep my_tempo
'   Loop Until quit = true
'
' There is no case of infinite blocking of the thread, but in general, some threads are strongly advantaged or disadvantaged compared to others 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 Integer threadFlagArray(Any)
  Static As Integer numberMax
  Static As Integer quit
  Declare Static Function NumberOfThreadFlag () As Integer
End Type
Dim As Integer UDT.threadFlagArray(Any)
Dim As Integer UDT.numberMax
Dim As Integer UDT.quit
Static Function UDT.NumberOfThreadFlag () As Integer
  Dim As Integer n
  For I As Integer = 0 To UDT.numberMax
    n += UDT.threadFlagArray(I)
  Next I
  Return n
End Function

Sub Counter (Byval pt As UDT Ptr)
  With *pt
    Locate .number, .number, 0
    Sleep 5
    .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
      .threadFlagArray(.number) = 1
      If .NumberOfThreadFlag() = 1 Then
        Counter(pUDT)
      End If
      quit =.quit
      .threadFlagArray(.number) = 0
      Sleep .tempo
    Loop Until quit = 1
  End With
End Sub


UDT.numberMax = 6
Redim UDT.threadFlagArray(0 To 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)
Next I

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
  UDT.threadFlagArray(u(0).number) = 1
  If UDT.NumberOfThreadFlag() = 1 Then
    s = Inkey
    If s <> "" Then
      UDT.quit = 1
    End If
  End If
  UDT.threadFlagArray(u(0).number) = 0
  Sleep u(0).tempo
Loop Until s <> ""

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

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

Code: Select all

407
 380
  243
   156
    153
     105

28 increments per second

- Example for §1.1.3: Asynchronous repeat awake then sleep, until expected condition

Code: Select all

' User thread algorithm (same principle for the main thread):
'
'   Do
'   |  Do
'   |  |  my_thread_flag = true
'   |  |  If number_of_thread_flag_true = 1 Then
'   |  |  |  Exit Do
'   |  |  End If
'   |  |  my_thread_flag = false
'   |  |  Sleep 5
'   |  Loop
'   |  .....
'   |  Critical section of code
'   |  .....
'   |  my_thread_flag = false
'   |  Sleep my_tempo
'   Loop Until quit = true
'
' There is no case of infinite blocking of the thread, but in general, some threads are strongly advantaged or disadvantaged compared to others 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 Integer threadFlagArray(Any)
  Static As Integer numberMax
  Static As Integer quit
  Declare Static Function NumberOfThreadFlag () As Integer
End Type
Dim As Integer UDT.threadFlagArray(Any)
Dim As Integer UDT.numberMax
Dim As Integer UDT.quit
Static Function UDT.NumberOfThreadFlag () As Integer
  Dim As Integer n
  For I As Integer = 0 To UDT.numberMax
    n += UDT.threadFlagArray(I)
  Next I
  Return n
End Function

Sub Counter (Byval pt As UDT Ptr)
  With *pt
    Locate .number, .number, 0
    Sleep 5
    .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
      Do
        .threadFlagArray(.number) = 1
        If .NumberOfThreadFlag() = 1 Then
          Exit Do
        End If
        .threadFlagArray(.number) = 0
        Sleep 5
      Loop
      Counter(pUDT)
      quit = .quit
      .threadFlagArray(.number) = 0
      Sleep .tempo
    Loop Until quit = 1
  End With
End Sub


UDT.numberMax = 6
Redim UDT.threadFlagArray(0 To 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)
Next I

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
  Do
    UDT.threadFlagArray(u(0).number) = 1
    If UDT.NumberOfThreadFlag() = 1 Then
      Exit Do
    End If
    UDT.threadFlagArray(u(0).number) = 0
    Sleep 5
  Loop
  s = Inkey
  If s <> "" Then
    UDT.quit = 1
  End If
  UDT.threadFlagArray(u(0).number) = 0
  Sleep u(0).tempo
Loop Until s <> ""

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

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

Code: Select all

416
 132
  283
   120
    242
     104

32 increments per second

- Example for §1.2: Asynchronous Process using one mutex for all threads

Code: Select all

' User thread algorithm (same principle for the main thread):
'
'   Do
'   |  Mutexlock
'   |  | .....
'   |  | Critical section of code
'   |  | .....
'   |  Mutexunlock
'   |  Sleep my_tempo
'   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
    .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)
        Counter(pUDT)
        quit = .quit
      Mutexunlock(.pMutex)
      Sleep .tempo
    Loop Until quit = 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
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

Code: Select all

220
 188
  147
   130
    114
     104

62 increments per second

- Example for §2.1.1: Synchronous wait for expected condition, including a sleep in order to release CPU time

Code: Select all

' User thread algorithm (same principle for the main thread):
'
'   Do
'   |  While thread_priority_number <> my_number
'   |  |  Sleep 5
'   |  Wend
'   |  .....
'   |  Critical section of code
'   |  .....
'   |  thread_priority_number = next thread_priority_number
'   |  Sleep my_tempo
'   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 Integer numberMax
  Static As Integer quit
End Type
Dim As Integer UDT.threadPriorityNumber
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
    .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
      While .threadPriorityNumber <> .number
        Sleep 5
      Wend
      Counter(pUDT)
      quit = .quit
      .threadPriorityNumber = (.threadPriorityNumber + 1) Mod (.numberMax+1)
      Sleep .tempo
    Loop Until quit = 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

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
  While UDT.threadPriorityNumber <> u(0).number
    Sleep 5
  Wend
  s = Inkey
  If s <> "" Then
    UDT.quit = 1
  End If
  UDT.threadPriorityNumber = (UDT.threadPriorityNumber + 1) Mod (UDT.numberMax+1)
  Sleep u(0).tempo
Loop Until s <> ""

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

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

Code: Select all

106
 106
  106
   106
    106
     106

31 increments per second

- Example for §2.1.2: Synchronous wait for expected condition, including a condwait then a condbroadcast (and mutex) in order to release CPU time

Code: Select all

' 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
'   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
    .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)
        While .threadPriorityNumber <> .number  '' synchronous condwait for expected condition
          Condwait(.pCond, .pMutex)
        Wend
        Counter(pUDT)
        quit = .quit
        .threadPriorityNumber = (.threadPriorityNumber + 1) Mod (.numberMax+1)
        Condbroadcast(.pCond)
      Mutexunlock(.pMutex)
      Sleep .tempo
    Loop Until quit = 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
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

Code: Select all

105
 105
  105
   105
    105
     105

48 increments per second
Compared to previous example, adding 'condwait' and 'condbroadcast' (and mutex) increases the complexity but also improves the execution time.

Example for §2.2: Synchronous process using a mutex for each thread, by self lock and mutual unlock

Code: Select all

' Main thread (#0) algorithm:
'
'   Do
'   |  |  .....
'   |  |  Critical section of code
'   |  |  .....
'   |  Mutexunlock(next thread mutex (#0+1))
'   |  Mutexlock(own thread mutex (#0))
'   |  Sleep my_tempo
'   Loop Until key <> ""

' User thread (#N) algorithm:
'
'   Do
'   |  Mutexlock(own thread mutex (#N))
'   |  |  .....
'   |  |  Critical section of code
'   |  |  .....
'   |  Mutexunlock(next thread mutex (#N+1))
'   |  Sleep tempo
'   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
    .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
    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

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
    s = Inkey
    If s <> "" Then
      UDT.quit = 1
    End If
  Mutexunlock(UDT.pMutex((u(0).number +1) Mod (UDT.numberMax+1)))
  Mutexlock(UDT.pMutex(u(0).number))
  Sleep u(0).tempo
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

Code: Select all

103
 103
  103
   103
    103
     103

28 increments per second
The worst execution time among the 3 synchronous processes!
Last edited by fxm on May 10, 2018 11:16, edited 7 times in total.
fxm
Posts: 8348
Joined: Apr 22, 2009 12:46
Location: Paris (suburb), FRANCE

Re: How to Manage a Critical Section of the code of a Thread in FB

Postby fxm » Dec 15, 2015 20:55

What happens if calling 'Condsignal()' or 'Condbroadcast()' without mutex locked?

About the above example for §2.1.2, I take this opportunity to recall that:
- The mutex must always be also locked while executing 'Condsignal()' or 'Condbroadcast()' to wake up a thread (it may be unlocked but only after 'Condsignal()' or 'Condbroadcast()').
- If the mutex is not locked (or even if the mutex is unlocked only just before executing 'Condsignal()' or 'Condbroadcast()'), the behavior may become unpredictable (it may work or not, depending on the threads configuration and execution real time).

In this above example for §2.1.2:
- If one at least 'Mutexunlock()' is moved just before its 'Condbroadcast()', the program hangs very quickly.
- Although some users certify that the mutex can always be unlocked just before 'Condsignal()' or 'Condbroadcast()', and others more cautious assert that one can do it only for a 'Condbroadcast()', experiment shows the opposite!

The general rule is that:
- The condition must not be signaled (by 'Condsignal()' or 'Condbroadcast()') between the time a thread locks the mutex and the time it waits on the condition variable ('Condwait()'), otherwise it seems that it may damage the waiting queue of threads on that condition variable.
- Thus to avoid that and follow this rule, it is necessary that the mutex remains locked when the condition is signaled.
Last edited by fxm on May 10, 2018 8:09, edited 1 time in total.
fxm
Posts: 8348
Joined: Apr 22, 2009 12:46
Location: Paris (suburb), FRANCE

Re: How to Manage a Critical Section of the code of a Thread in FB

Postby fxm » May 13, 2016 16:51

When is it not mandatory to protect by a Mutex one shared variable between several threads?

When accessing to shared variables between several threads, all their accesses must be generally put inside blocks [Mutexlock ..... Mutexunlock], in all threads:
- When the shared variable is only one simple predefined numeric type of size <= sizeof(integer) (only one assembler instruction for access), Mutex use may be not mandatory.
- But if this is for example one shared variable LongInt with a win32 compilation, it is advised here to use a Mutex (otherwise the reading phase by a thread may be interlaced with the writing phase of another thread).

That is because to access a variable in memory (for reading or for writing), a processor uses its internal registers.
A N-bit processor has N-bit registers but none greater:
- So one only assembler instruction allows it to access a N-bit variable in memory.
- at opposite, to access a 2N-bit variable, it must use 2 assembler instructions.
- If between these two assembler instructions (for writing), another thread accesses this same variable (for reading), the got value may be incoherent (N-bit highest and N-bit lowest incoherent together).

This behavior can be checked with a graphic program using two threads and a shared LongInt (64-bit) without Mutex:
- by compiling in 32-bit, many read values are incoherent.
- by compiling in 64-bit, no read value is incoherent.

Compile the below test program:
- in 32-bit => many erroneous points not on the circle but anywhere in the square containing the circle (if you uncomment the four lines 33/35/53/55 to activate the Mutex, then all the got points are now on the circle only),
- in 64-bit => all points are valid, on the circle only, even if the Mutex is not activated.

Code: Select all

'- The "user-defined thread" computes the points coordinates on a circle,
'  and write those in a LongInt (32-bit & 32-bit = 64-bit)
'- The "main thread" plots the points from the LongInt value.
'
'Behavior:
'- The first point must be pre-determined.
'- Nothing prevents that a same calculated point could be plotted several times
'(depends on execution times of the loops between main thread and user thread).
'- Nothing prevents that a calculated point could be not plotted
'(same remark on the loop times).
'
'Remark:
'Voluntarily, there is no Sleep in the loop of each thread (normally strongly discouraged),
'but this is just in this special case to amplify the behavior effects to observe.


Union Point2D
    Dim As Longint xy
    Type
        Dim As Long y
        Dim As Long x
    End Type
End Union

Dim As Any Ptr handle
Dim Shared As Any Ptr mutex
Dim Shared As Integer quit

Sub Thread (ByVal param As Any Ptr)
    Const pi As Single = 4 * Atn(1)
    Dim As Point2D Ptr p = param
    Do
        Dim As Point2D P2D0
        Dim As Single teta = 2 * pi * Rnd
        P2D0.x = 320 + 200 * Cos(teta)
        P2D0.y = 240 + 200 * Sin(teta)
'        Mutexlock(mutex)
        p->xy = P2D0.xy
'        Mutexunlock(mutex)
'        Sleep 5
    Loop Until quit = 1
End Sub


Screen 12

Dim As Point2D P2D
P2D.x = 520
P2D.y = 240

mutex = MutexCreate
handle = ThreadCreate(@Thread, @P2D)

Dim As Integer c

Do
    Dim As Point2D P2D0
'    Mutexlock(mutex)
    P2D0.xy = P2D.xy
'    Mutexunlock(mutex)
    PSet (P2D0.x, P2D0.y), c
    c = (c Mod 15) + 1
'    Sleep 5
Loop Until Inkey <> ""
 
quit = 1
ThreadWait(handle)
Mutexdestroy(mutex)
Last edited by fxm on May 10, 2018 8:09, edited 1 time in total.
fxm
Posts: 8348
Joined: Apr 22, 2009 12:46
Location: Paris (suburb), FRANCE

Re: How to Manage a Critical Section of the code of a Thread in FB

Postby fxm » May 19, 2016 16:46

Why it is mandatory to put CondWait within a While loop for checking a Boolean predicate (set by other thread before activate CondSignal or CondBroadcast)?

Code: Select all

While predicate <> true
  Condwait(handle, mutex)
Wend

In all documentations, it is highly advisable to do so, mainly justified to fight against eventual spurious wake-ups.

This is probably true, but it is also advisable to do so to avoid to loose a CondSignal (or CondBroadcast) if it is prematurely activated while the receiving thread is not yet waiting on CondWait (the signal is lost forever):
- In that case, the receiving thread has even not yet locked the mutex before that CondSignal (or CondBroadcast) is activated.
- So the predicate will already true before the receiving thread reaches the While loop, inducing that CondWait is downright skipped, so avoiding a definitive blocking phenomenon.

Let two threads (thread #0 in main program, thread #1 in a user procedure, each that prints its number in a loop), having about the same execution time, and each one synchronizing the other in order to well interlace their numbers (by using one mutex, two condition variables and CondSignal/CondWait):

- Without a While loop on predicate, the program hangs quickly (Ctrl-C to quit):

Code: Select all

'          Thread#0               XOR + <==>             Thread#1
'.....                                          .....
'MutexLock(mut)                                 MutexLock(mut)
'  Do_something_with_exclusion                    Do_something_with_exclusion
'  CondWait(cond#1, mut) <----------------------- CondSignal(cond#1)
'  Do_something_with_exclusion <---------.        Do_something_with_exclusion
'  CondSignal(cond#2) ------------------ | -----> CondWait(cond#2, mut)
'  Do_something_with_exclusion     .---- | -----> Do_something_with_exclusion
'MutexUnlock(mut) -----------------'     '----- MutexUnlock(mut)
'.....                                          .....


Dim As Any Ptr handle
Dim Shared As Any Ptr mutex
Dim Shared As Any Ptr cond1
Dim Shared As Any Ptr cond2
Dim Shared As Integer quit

Sub Thread (ByVal param As Any Ptr)
    Do
        Mutexlock(mutex)
        Print "1";
        CondSignal(cond1)
        CondWait(cond2, mutex)
        If quit = 1 Then
            Mutexunlock(mutex)
            Exit DO
        End If
        Mutexunlock(mutex)
        Sleep 1
    Loop
End Sub


mutex = MutexCreate
cond1 = CondCreate
cond2 = CondCreate
handle = ThreadCreate(@Thread)

Do
    Mutexlock(mutex)
    CondWait(cond1, mutex)
    Print "0";
    CondSignal(cond2)
    If Inkey <> "" Then
        quit = 1
        Mutexunlock(mutex)
        Exit Do
    End If
    Mutexunlock(mutex)
    Sleep 1
Loop
 
ThreadWait(handle)
Mutexdestroy(mutex)
CondDestroy(cond1)
CondDestroy(cond2)
Print

Sleep

- With a While loop on predicate around each CondWait, no blocking phenomenon:

Code: Select all

'          Thread#0               XOR + <==>             Thread#1
'.....                                          .....
'MutexLock(mut)                                 MutexLock(mut)
'  Do_something_with_exclusion                    Do_something_with_exclusion
'  While bool#1 <> true <------------------------ bool#1 = true
'    CondWait(cond#1, mut) <--------------------- CondSignal(cond#1)
'  Wend <-----------------------------------.     Do_something_with_exclusion
'  bool#1 = false               .---------- | --> While bool#2 <> true
'  Do_something_with_exclusion  |   .------ | ----> CondWait(cond#2, mut)
'  bool#2 = true ---------------'   |   .-- | --> Wend
'  CondSignal(cond#2) --------------'   |   |     bool#2 = false
'  Do_something_with_exclusion          |   |     Do_something_with_exclusion
'MutexUnlock(mut) ----------------------'   '-- MutexUnlock(mut)
'.....                                          .....


Dim As Any Ptr handle
Dim Shared As Any Ptr mutex
Dim Shared As Any Ptr cond1
Dim Shared As Any Ptr cond2
Dim Shared As Integer new1
Dim Shared As Integer new2
Dim Shared As Integer quit

Sub Thread (ByVal param As Any Ptr)
    Do
        Mutexlock(mutex)
        Print "1";
        new1 = 1
        CondSignal(cond1)
        While new2 <> 1
            CondWait(cond2, mutex)
        Wend
        new2 = 0
        If quit = 1 Then
            Mutexunlock(mutex)
            Exit DO
        End If
        Mutexunlock(mutex)
        Sleep 1
    Loop
End Sub


mutex = MutexCreate
cond1 = CondCreate
cond2 = CondCreate
handle = ThreadCreate(@Thread)

Do
    Mutexlock(mutex)
    While new1 <> 1
        CondWait(cond1, mutex)
    Wend
    new1 = 0
    Print "0";
    new2 = 1
    CondSignal(cond2)
    If Inkey <> "" Then
        quit = 1
        Mutexunlock(mutex)
        Exit Do
    End If
    Mutexunlock(mutex)
    Sleep 1
Loop
 
ThreadWait(handle)
Mutexdestroy(mutex)
CondDestroy(cond1)
CondDestroy(cond2)
Print

Sleep
Last edited by fxm on May 10, 2018 8:09, edited 1 time in total.
fxm
Posts: 8348
Joined: Apr 22, 2009 12:46
Location: Paris (suburb), FRANCE

Re: How to Manage a Critical Section of the code of a Thread in FB

Postby fxm » May 20, 2016 20:39

What is the chronology of code execution of 2 critical sections (with a mutex locking and a conditional variable signaling) that compete between 2 threads?

Chronology for one thread signaling which occurs:
1) while another thread is waiting (within a While loop on predicate),
2) before another thread is waiting (within a While loop on predicate).

Code: Select all

#define while_loop_on_predicate

Dim As Any Ptr handle
Dim Shared As Any Ptr mutex
Dim Shared As Any Ptr cond
Dim As Integer sleep0
Dim As Integer sleep1
#ifdef while_loop_on_predicate
Dim Shared As Integer ready
#endif


Sub Thread1 (ByVal param As Any Ptr)
  Sleep *Cast(Integer Ptr, param)
  Mutexlock(mutex)
  Color 11 : Print "    Thread#1 locks the mutex"
  Color 11 : Print "    Thread#1 executes code with exclusion"
  #ifdef while_loop_on_predicate
  ready = 1
  #endif
  Color 11 : Print "    Thread#1 is signaling"
  CondSignal(cond)
  Color 11 : Print "    Thread#1 executes post-code with exclusion"
  Color 11 : Print "    Thread#1 unlocks the mutex"
  Mutexunlock(mutex)
End Sub

Sub Thread0 (ByVal param As Any Ptr)
  Sleep *Cast(Integer Ptr, param)
  Mutexlock(mutex)
  Color 10 : Print "  Thread#0 locks the mutex"
  Color 10 : Print "  Thread#0 executes pre-code with exclusion"
  #ifdef while_loop_on_predicate
  While ready <> 1
  #endif
    Color 10 : Print "  Thread#0 is waiting"
    CondWait(cond, mutex)
    Color 10 : Print "  Thread#0 is waked"
  #ifdef while_loop_on_predicate
  Wend
  #endif
  Color 10 : Print "  Thread#0 executes code with exclusion"
  #ifdef while_loop_on_predicate
  ready = 0
  #endif
  Color 10 : Print "  Thread#0 unlocks the mutex"
  Mutexunlock(mutex)
End Sub


mutex = MutexCreate
cond = CondCreate

sleep0 = 0
sleep1 = 1000
Color 7 : Print "Chronology for Thread#1 signaling while Thread#0 is waiting:"
handle = ThreadCreate(@Thread1, @sleep1)
Thread0(@sleep0)
ThreadWait(handle)
Color 7 : Print "Thread#1 finished": Print
Sleep 1000

sleep0 = 1000
sleep1 = 0
Color 7 : Print "Chronology for Thread#1 signaling before Thread#0 is waiting:"
handle = ThreadCreate(@Thread1, @sleep1)
Thread0(@sleep0)
ThreadWait(handle)
Color 7 : Print "Thread#1 finished": Print


Mutexdestroy(mutex)
CondDestroy(cond)
Sleep
Output part 1 - Chronology for Thread#1 signaling while Thread#0 is waiting:

Code: Select all

Chronology for Thread#1 signaling while Thread#0 is waiting:
  Thread#0 locks the mutex
  Thread#0 executes pre-code with exclusion
  Thread#0 is waiting
    Thread#1 locks the mutex
    Thread#1 executes code with exclusion
    Thread#1 is signaling
    Thread#1 executes post-code with exclusion
    Thread#1 unlocks the mutex
  Thread#0 is waked
  Thread#0 executes code with exclusion
  Thread#0 unlocks the mutex
Thread#1 finished
Output part 2 - Chronology for Thread#1 signaling before Thread#0 is waiting:

Code: Select all

Chronology for Thread#1 signaling before Thread#0 is waiting:
    Thread#1 locks the mutex
    Thread#1 executes code with exclusion
    Thread#1 is signaling
    Thread#1 executes post-code with exclusion
    Thread#1 unlocks the mutex
  Thread#0 locks the mutex
  Thread#0 executes pre-code with exclusion
  Thread#0 executes code with exclusion
  Thread#0 unlocks the mutex
Thread#1 finished

If CondWait is not within a While loop on predicate (by putting in comment the first line of above program), one can check in the second case (thread#1 signaling before thread#0 waiting), that thread#0 remains blocked in its waiting phase (Ctrl-C to quit).
Last edited by fxm on May 10, 2018 8:10, edited 1 time in total.
fxm
Posts: 8348
Joined: Apr 22, 2009 12:46
Location: Paris (suburb), FRANCE

Re: How to Manage a Critical Section of the code of a Thread in FB

Postby fxm » Oct 16, 2017 12:33

User input-line function, but fully thread safe!

The "Input" keyword may be not thread safe, when another thread must also access to input/output resource.
In addition, we cannot enclosed the "Input" keyword inside a mutex locking (as we can do it for the "Inkey" keyword), because while the inputing line would be not completed and validated, the other threads that want to also access to input/output would be fully blocked (waiting for mutex unlocking).

Thread safe input-line function (versus input/output resource)
Input position, prompt message, sleeping time, line-blanking command, mutex pointer can be passed to the following "threadInput()" function that simulates a simplified input function, but thread safe, by using a looping around the "Inkey" keyword (all input/output keywords must be enclosed inside a mutex locking block, and the cursor position must be restored at each mutex locking block ending):

Code: Select all

Function threadInput (Byval row As Integer, Byval column As Integer, Byref prompt As String = "", Byval sleeptime As Integer = 15, Byval blank As Integer = 0, Byval mutex As Any Ptr = 0) As String
  Dim As Integer r
  Dim As Integer c
  Dim As String inputchr
  Dim As String inputline
 
  Mutexlock(mutex)
    r = Csrlin()
    c = Pos()
    Locate row, column
    Print prompt & "? _";
    Locate r, c
  Mutexunlock(mutex)
 
  Do
    Mutexlock(mutex)
      r = Csrlin()
      c = Pos()
      Locate row, column + Len(inputline) + Len(prompt) + 2
      inputchr = Inkey
      If Len(inputchr) = 1 Then
        If Asc(inputchr) >= 32 Then
          Print inputchr & Chr(95);
          Locate , pos - 1
          inputline &= inputchr
        Elseif Asc(inputchr) = 08 and Len(inputline) > 0 Then
          Locate , pos - 1
          Print chr(95) & " ";
          Locate , Pos() - 2
          inputline = Left(inputline, Len(inputline) - 1)
        End If
      End If
      Locate r, c
    Mutexunlock(mutex)
    Sleep sleeptime
  Loop Until inputchr = Chr(13)
 
  If blank <> 0 Then
    Mutexlock(mutex)
      r = Csrlin()
      c = Pos()
      Locate row, column + Len(prompt) + 2
      Print Space(Len(inputline) + 1);
      Locate r, c
    Mutexunlock(mutex)
  End If
 
  Return inputline
End Function

From the previous code "Example for §1.2: Asynchronous Process using one mutex for all threads", now the running multi-threading code is waiting for the "quit" command in order to exit the program:

Code: Select all

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


Function threadInput (Byval row As Integer, Byval column As Integer, Byref prompt As String = "", Byval sleeptime As Integer = 15, Byval blank As Integer = 0, Byval mutex As Any Ptr = 0) As String
  Dim As Integer r
  Dim As Integer c
  Dim As String inputchr
  Dim As String inputline
 
  Mutexlock(mutex)
    r = Csrlin()
    c = Pos()
    Locate row, column
    Print prompt & "? _";
    Locate r, c
  Mutexunlock(mutex)
 
  Do
    Mutexlock(mutex)
      r = Csrlin()
      c = Pos()
      Locate row, column + Len(inputline) + Len(prompt) + 2
      inputchr = Inkey
      If Len(inputchr) = 1 Then
        If Asc(inputchr) >= 32 Then
          Print inputchr & Chr(95);
          Locate , pos - 1
          inputline &= inputchr
        Elseif Asc(inputchr) = 08 and Len(inputline) > 0 Then
          Locate , pos - 1
          Print chr(95) & " ";
          Locate , Pos() - 2
          inputline = Left(inputline, Len(inputline) - 1)
        End If
      End If
      Locate r, c
    Mutexunlock(mutex)
    Sleep sleeptime
  Loop Until inputchr = Chr(13)
 
  If blank <> 0 Then
    Mutexlock(mutex)
      r = Csrlin()
      c = Pos()
      Locate row, column + Len(prompt) + 2
      Print Space(Len(inputline) + 1);
      Locate r, c
    Mutexunlock(mutex)
  End If
 
  Return inputline
End Function


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
    .count += 1
    Print .count;
  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)
        Counter(pUDT)
        quit = .quit
      Mutexunlock(.pMutex)
      Sleep .tempo
    Loop Until quit = 1
  End With
End Sub


Screen 12
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

Do
Loop Until Lcase(threadInput(8, 1, """quit"" for exit", 10, 1, UDT.pMutex)) = "quit"

UDT.quit = 1

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 + 4, 1
Print Culngint(c / t) & " increments per second"

Sleep

Return to “Documentation”

Who is online

Users browsing this forum: No registered users and 0 guests