[TUTO] multithreading

[microdevweb]

Hi Guys,

I show you a small tutorial about the multithreading.

Why use of multithreading?

If you want will develop, a software which manage many data, for some images, databases or anything. If you make a classical loops, you software don't work in same time, because a loop lock all future code when it works.

But if you create a thread, it runs in parallel with your code (like a executable) and it didn't lock anything except it.

Well for use it, you need some precautions:

Don't forget that, this is your os will be run the thread when it want, and usually it don't use the creating order.

We need to manage the synchronization between threads.

For do it, we have two tools to use:

• Semaphores
• Mutex

A semaphore is like a integer, but we cant only increment it or decrement it. We can also init it with a value upper or equal to 0.

We talk about (mutex) mutual exclusion in another page and after more time.

Two method exist with semaphore :

• wait
• signal

The wait method, decrement the semaphore et turn sleep the thread if the semaphore is lower at 0

The signal method, increment the semaphore et wake up a thread.

Even if semaphore use look like easy, nicely use semaphores is not a piece of cake.

An american teacher of university "Allen B. Downey" , wrote a book about semaphore usage "The Little Book of Semaphores". In his book he gives some patterns for use semaphores in some situations.

The Little Book of Semaphores

I designed some examples from this book and about variousing scenarios

Examples :

• The rendezvous
• The mutex
• Runners (part 1)
• Runners (part 2)
• Runners (part 3)
• To following soon (Ther producer and the counsumer)

[microdevweb]

Rendezvous

2 friends decide to watch a film in 2 different towns. Hours To start are not same and they want discuss about movie after watch it.

Pattern :

Code: Select all

Thread A
1 statement a1
2 aArrived.signal()
3 bArrived.wait
4 statement a2

Thread B
1 statement b1
2 bArrived.signal()
3 aArrived.wait()
4 statement b2

Purebasic solution

Code: Select all

;-----------------------------------------------------------------------------
; TUTORIAL    : MULTI THREADS
; STAGE         : rendezvous
; AUTHOR      : MicrodevWeb
; DATE           : 2020-01-17
; SCENARIO    : 2 friends decide to watch a film in 2 different towns.
;             Hours To start are Not same And they want discuss about
;             movie after watch it.
; TIME STAGE  :
; FRIEND_1
;  watch      wait on     discuss
;             RDV SPOT    about
; ----------|-----------|--------
; FRIEND_2
;  watch    wait on       discuss
;            RDV SPOT     about
; -------|--------------|--------
;-----------------------------------------------------------------------------
EnableExplicit
Global.i aArrived,bArrived ; semaphores
Global.i THR_A,THR_B       ; thread id
;-----------------------------------------------------------------------------
; THREAD FUNCTIONS
;-----------------------------------------------------------------------------
Procedure THR_Friend_a(*p)
  Debug "Friend a watch a film"
  ; random time for watch the movie
  Delay(Random(5000,1000))
  ; tell a is arrived
  SignalSemaphore(aArrived)
  ; wait friend for b
  WaitSemaphore(bArrived)
  Debug "a discuss about movie with b"
EndProcedure
Procedure THR_Friend_b(*p)
  Debug "Friend b watch a film"
  ; random time for watch the movie
  Delay(Random(5000,1000))
  ; tell b is arrived
  SignalSemaphore(bArrived)
  ; wait friend for a
  WaitSemaphore(aArrived)
  Debug "b discuss about movie with a"
 
EndProcedure
;-----------------------------------------------------------------------------
; MAIN PROGRAM
;-----------------------------------------------------------------------------
; create semaphores
aArrived = CreateSemaphore(0)
bArrived = CreateSemaphore(0)
; run threads
THR_A = CreateThread(@THR_Friend_a(),0)
THR_B = CreateThread(@THR_Friend_b(),0)
Define i
For i = 0 To 10
  Debug "The main software can count "+Str(i)
  Delay(1000)
Next
; wait for threads
WaitThread(THR_A)
WaitThread(THR_B)
Debug "END PROGRAM"
End

[microdevweb]

The mutex

The "mutex" is about a mutual exclusion, use it when a same variable will be use by different threads.

For true, a mutex is just a semaphore initialized to 1.

Two methods exist :

• Lock , Lock access for other threads.
• Unlock, unlock access for all

Example to use it

Code: Select all

;-----------------------------------------------------------------------------
; TUTORIAL    : MULTI THREADS
; STAGE       : mutex
; AUTHOR      : MicrodevWeb
; DATE        : 2020-01-17
;-----------------------------------------------------------------------------

Global THR_A,THR_B ; threads id
Global mutex       ; mutex id
Global counter = 0 ;
                   ; create mutex
mutex = CreateMutex();

#MAX = 10; Macimum to count

;------------------------------------------------------------------------------
; thread functions
;------------------------------------------------------------------------------
Procedure f_thr_a(*p)
  Repeat
    Debug "Thread A is running"
    LockMutex(mutex)    ; we lock variable access
    counter +1          ;
    Debug "A increment counter "+Str(counter)
    UnlockMutex(mutex)  ; we unlock variable access
    Delay(Random(1000,800)) ; wait some time
    If counter >= #MAX
      Debug "Thread A STOP"
      ProcedureReturn
    EndIf
  ForEver
EndProcedure
Procedure f_thr_b(*p)
  Repeat
    Debug "Thread B is running"
    LockMutex(mutex)    ; we lock variable access
    counter +1          ;
    Debug "B increment counter "+Str(counter)
    UnlockMutex(mutex)  ; we unlock variable access
    Delay(Random(1000,800)) ; wait some time
    If counter >= #MAX
      Debug "Thread B STOP"
      ProcedureReturn
    EndIf
  ForEver
EndProcedure
;------------------------------------------------------------------------------
; main
;------------------------------------------------------------------------------
; create threads
THR_A = CreateThread(@f_thr_a(),0)
THR_B = CreateThread(@f_thr_b(),0)
; waiting for threads
WaitThread(THR_A)
WaitThread(THR_B)

Debug "END OF PROGRAM"

End

[microdevweb]

Runners (part 1)
In this scenario some runners go to run for some stages. But when a runner arrive on his stage, he must be wait all other runners.

Find her a first solution with a simple barrier.

Pattern

Code: Select all

rendezvous
2
3 mutex.wait()
4 count = count + 1
5 mutex.signal()
6
7 if count == n: barrier.signal()
8
9 barrier.wait()
10 barrier.signal()
11
12 critical point

However, we have a problem, after one stage and when all runners are arrived, the barrier still open and the code don't works for next stages.


For testing that, change this value to 2 or more.

Code: Select all

#N_STAGE = 2

purebasic code

Code: Select all

;-----------------------------------------------------------------------------
; TUTORIAL    : MULTI THREADS
; STAGE       : runners part 1
; AUTHOR      : MicrodevWeb
; DATE        : 2020-01-18
; SCENARIO    : any runners run go some stages, but when a runner
;               will on his stage he must be wait of all runners arrived.
;
;-----------------------------------------------------------------------------
#N_RUNNERS = 10
#N_STAGE = 1

Structure _runner
  number.i        ; the number of runner
  thr.i           ; the id of the thread
  current_stage.i ; the current stage of runner
EndStructure

Global._runner Dim t_runners(#N_RUNNERS)
Global.i barrier,mutex ; smaphore id
Global n_runner        ; number of runners used by thread

;-----------------------------------------------------------------------------
; THREADS FUNCTIONS
;-----------------------------------------------------------------------------
Procedure runner_thr(*p._runner)
  With *p
    Debug "runner "+Str(\number)+" is running"
    Repeat
      ; go to next stage
      \current_stage +1
      Delay(Random(2000,500)) ; the runner need some time to arrived on his stage
      Debug "runner "+Str(\number)+" is arrived on stage "+Str(\current_stage)+" and wait"
      LockMutex(mutex) ; mutual exclusion
      n_runner +1
      UnlockMutex(mutex)
      ; if all runner are arrived
      If n_runner = #N_RUNNERS
        SignalSemaphore(barrier)
      EndIf
      WaitSemaphore(barrier)
      SignalSemaphore(barrier)
      Debug "runner "+Str(\number)+" make his critical work"
    Until \current_stage >= #N_STAGE
  EndWith
EndProcedure
;-----------------------------------------------------------------------------
; MAIN
;-----------------------------------------------------------------------------
; initiation
; -> mutex and semaphore
mutex = CreateMutex()
barrier = CreateSemaphore(0)

; create runners and threads
Define i
For i = 1 To #N_RUNNERS
  With t_runners(i-1)
    \number = i
    \thr = CreateThread(@runner_thr(),@t_runners(i-1))
  EndWith
Next
; wait for all threads
For i = 1 To #N_RUNNERS
  With t_runners(i-1)
    WaitThread(\thr)
  EndWith
Next 
Debug "END OF PROGRAM"

End

[microdevweb]

Runners (part 2)

For resolve the problem when we have more stages, we need to create a second barrier. This barrier still open at starting.

Pattern

Code: Select all

1 turnstile = Semaphore(0)
2 turnstile2 = Semaphore(1)

1 # rendezvous
2
3 mutex.wait()
4 count += 1
5 if count == n:
6 turnstile2.wait() # lock the second
7 turnstile.signal() # unlock the first
8 mutex.signal()
9
10 turnstile.wait() # first turnstile
11 turnstile.signal()
12
13 # critical point
14
15 mutex.wait()
16 count -= 1
17 if count == 0:
18 turnstile.wait() # lock the first
19 turnstile2.signal() # unlock the second
20 mutex.signal()
21
22 turnstile2.wait() # second turnstile
23 turnstile2.signal()

Purebasic code

Note: As you'll see, the code turn really less easy. And we need to make it on reusable solution. I'll show you that in the next part.

Code: Select all

;-----------------------------------------------------------------------------
; TUTORIAL    : MULTI THREADS
; STAGE       : runners part 1
; AUTHOR      : MicrodevWeb
; DATE        : 2020-01-18
; SCENARIO    : any runners run go some stages, but when a runner
;               will on his stage he must be wait of all runners arrived.
;
;-----------------------------------------------------------------------------
#N_RUNNERS = 10
#N_STAGE = 5

Structure _runner
  number.i        ; the number of runner
  thr.i           ; the id of the thread
  current_stage.i ; the current stage of runner
EndStructure

Global._runner Dim t_runners(#N_RUNNERS)
Global.i barrier_1,barrier_2,mutex ; smaphore id
Global n_runner                    ; number of runners used by thread

;-----------------------------------------------------------------------------
; THREADS FUNCTIONS
;-----------------------------------------------------------------------------
Procedure runner_thr(*p._runner)
  With *p
    Debug "runner "+Str(\number)+" is running"
    Repeat
      ; go to next stage
      \current_stage +1
      Delay(Random(2000,500)) ; the runner need some time to arrived on his stage
      Debug "runner "+Str(\number)+" is arrived on stage "+Str(\current_stage)+" and wait"
      LockMutex(mutex) ; mutual exclusion
      n_runner +1     
      ; if all runner are arrived
      If n_runner = #N_RUNNERS ; all runners arrived along barrier 1
        WaitSemaphore(barrier_2)   ; close barrier 2
        SignalSemaphore(barrier_1) ; open barrier 1
      EndIf
      UnlockMutex(mutex) ; end of mutual exclusion
     
      WaitSemaphore(barrier_1)    ; close barrier 1
      SignalSemaphore(barrier_1)  ; open barrier 1
     
      Debug "runner "+Str(\number)+" make his critical work"
     
      ; barrier 2 management
      LockMutex(mutex) ; mutual exclusion
      n_runner -1
      If n_runner = 0   ; all runners arrived alonf barrier 2
        WaitSemaphore(barrier_1)   ; close barrier 1
        SignalSemaphore(barrier_2) ; open barrier 2
      EndIf
      UnlockMutex(mutex) ; end of mutual exclusio
     
      WaitSemaphore(barrier_2)   ; close barrier 2
      SignalSemaphore(barrier_2) ; open barrier 2
    Until \current_stage >= #N_STAGE
  EndWith
EndProcedure
;-----------------------------------------------------------------------------
; MAIN
;-----------------------------------------------------------------------------
; initiation
; -> mutex and semaphore
mutex = CreateMutex()
barrier_1 = CreateSemaphore(0)
barrier_2 = CreateSemaphore(1)

; create runners and threads
Define i
For i = 1 To #N_RUNNERS
  With t_runners(i-1)
    \number = i
    \thr = CreateThread(@runner_thr(),@t_runners(i-1))
  EndWith
Next
; wait for all threads
For i = 1 To #N_RUNNERS
  With t_runners(i-1)
    WaitThread(\thr)
  EndWith
Next 
Debug "END OF PROGRAM"
End

[microdevweb]

Runners (part 3)

As i was promised you, find below a reusable solution with a module for do it. I opted for an object approach.

D_BARRIERS module

Code: Select all

;-----------------------------------------------------------------------------
; TUTORIAL    : MULTI THREADS
; MODULE      : double barriers
; AUTHOR      : MicrodevWeb
; DATE        : 2020-01-18
;-----------------------------------------------------------------------------
DeclareModule D_BARRIERS
  Interface OBJECT
    ; --------------------------------------------------------------------------
    ; PUBLIC METHOD : wait
    ; PROCESS       : wait for all threads
    ; ARGUMENTS     : VOID
    ; RETURN        : VOID
    ; --------------------------------------------------------------------------
    wait()
    ; --------------------------------------------------------------------------
    ; PUBLIC METHOD : free
    ; PROCESS       : free objet
    ; ARGUMENTS     : VOID
    ; RETURN        : VOID
    ; --------------------------------------------------------------------------
    free()
  EndInterface
  ; --------------------------------------------------------------------------
  ; CONSTRUCTOR   : new
  ; ARGUMENTS     : number_of_threads.i -> number of threads
  ; RETURN        : new instance of barriers
  ; --------------------------------------------------------------------------
  Declare new(number_of_threads.i)
EndDeclareModule
Module D_BARRIERS
  EnableExplicit
  Structure _BARRIERS
    *methods
    barrier_1.i  ; semaphore
    barrier_2.i
    mutex.i      ; mutex
    n.i          ; n threads
    count.i      ; counter
  EndStructure
  ; --------------------------------------------------------------------------
  ; CONSTRUCTOR   : new
  ; ARGUMENTS     : number_of_threads.i -> number of threads
  ; RETURN        : new instance of barriers
  ; --------------------------------------------------------------------------
  Procedure new(number_of_threads.i)
    Protected *this._BARRIERS = AllocateStructure(_BARRIERS)
    With *this
      \n = number_of_threads
      \count = 0
      \barrier_1 = CreateSemaphore(0)
      \barrier_2 = CreateSemaphore(1)
      \mutex = CreateMutex()
      \methods = ?S_MTH
      ProcedureReturn *this
    EndWith
  EndProcedure
  ; --------------------------------------------------------------------------
  ; PUBLIC METHOD : wait
  ; PROCESS       : wait for all threads
  ; ARGUMENTS     : VOID
  ; RETURN        : VOID
  ; --------------------------------------------------------------------------
  Procedure wait(*this._BARRIERS)
    With *this
      LockMutex(\mutex) ; mutual exclusion
      \count +1     
      ; if all runner are arrived
      If \count = \n ; all threads arrived along barrier 1
        WaitSemaphore(\barrier_2)   ; close barrier 2
        SignalSemaphore(\barrier_1) ; open barrier 1
      EndIf
      UnlockMutex(\mutex) ; end of mutual exclusion
     
      WaitSemaphore(\barrier_1)    ; close barrier 1
      SignalSemaphore(\barrier_1)  ; open barrier 1
     
      ; barrier 2 management
      LockMutex(\mutex) ; mutual exclusion
      \count -1
      If \count = 0   ; all threads arrived alonf barrier 2
        WaitSemaphore(\barrier_1)   ; close barrier 1
        SignalSemaphore(\barrier_2) ; open barrier 2
      EndIf
      UnlockMutex(\mutex) ; end of mutual exclusio
     
      WaitSemaphore(\barrier_2)   ; close barrier 1
      SignalSemaphore(\barrier_2) ; open barrier 2
    EndWith
  EndProcedure
  ; --------------------------------------------------------------------------
  ; PUBLIC METHOD : free
  ; PROCESS       : free objet
  ; ARGUMENTS     : VOID
  ; RETURN        : VOID
  ; --------------------------------------------------------------------------
  Procedure free(*this._BARRIERS)
    With *this
      FreeSemaphore(\barrier_1)
      FreeSemaphore(\barrier_2)
      FreeMutex(\mutex)
      FreeStructure(*this)
    EndWith
  EndProcedure
 
  DataSection
    S_MTH:
    Data.i @wait()
    Data.i @free()
    E_MTH:
  EndDataSection
EndModule

As you see, that turn the main code a very easier.

[b]Runners code[/b]

[code]
;-----------------------------------------------------------------------------
; TUTORIAL    : MULTI THREADS
; STAGE       : runners part 3
; AUTHOR      : MicrodevWeb
; DATE        : 2020-01-18
; SCENARIO    : any runners run go some stages, but when a runner
;               will on his stage he must be wait of all runners arrived.
;
;-----------------------------------------------------------------------------
#N_RUNNERS = 10
#N_STAGE = 5

Structure _runner
  number.i        ; the number of runner
  thr.i           ; the id of the thread
  current_stage.i ; the current stage of runner
EndStructure

Global._runner Dim t_runners(#N_RUNNERS)
Global.D_BARRIERS::OBJECT myBarriers = D_BARRIERS::new(#N_RUNNERS)
;-----------------------------------------------------------------------------
; THREADS FUNCTIONS
;-----------------------------------------------------------------------------
Procedure runner_thr(*p._runner)
  With *p
    Debug "runner "+Str(\number)+" is running"
    Repeat
      ; go to next stage
      \current_stage +1
      Delay(Random(2000,500)) ; the runner need some time to arrived on his stage
      Debug "runner "+Str(\number)+" is arrived on stage "+Str(\current_stage)+" and wait"
      myBarriers\wait()
      Debug "runner "+Str(\number)+" make his critical work"
    Until \current_stage >= #N_STAGE
  EndWith
EndProcedure
;-----------------------------------------------------------------------------
; MAIN
;-----------------------------------------------------------------------------
; create runners and threads
Define i
For i = 1 To #N_RUNNERS
  With t_runners(i-1)
    \number = i
    \thr = CreateThread(@runner_thr(),@t_runners(i-1))
  EndWith
Next
; wait for all threads
For i = 1 To #N_RUNNERS
  With t_runners(i-1)
    WaitThread(\thr)
  EndWith
Next 
; free barriers object
myBarriers\free()
Debug "END OF PROGRAM"
End

[/code]

[Joris]

Thanks for this stuff to study.

[BarryG]

Agreed; thank you. Will come in handy in future.