Threads Example Worksheet
The Threads package provides user level commands for using threads in Maple. Threads allow for multiple paths of execution to be running at the same time. This can allow Maple to perform a greater number of computations per second when running on a multi-core machine.
To access the Threads package you must be running the multithreaded Maple engine. Please see the multithreaded page for information on how to start multithreaded Maple engine and for more general information on the multithreaded Maple engine and its limitations. This example worksheet assumes that you are running a multithreaded kernel. To test this execute the following line
restart;
kernelopts( multithreaded );
true
If the command above returned false then you are not running the multithreaded kernel and this worksheet will not function properly.
Create Threads
The Task Programming Model
Note: The Task Programming Model is the preferred way to write a multithreaded program in Maple. Although the Threads:-Create method still exists, the Task Programming Model has significant advantages over the explicit thread programming required when using the Threads:-Create method. See examples/Task.
The Threads[Create] function is used to start a new thread. The first argument passed into Threads[Create] is an expression that will be evaluated in the new thread. Threads[Create] returns an integer that can be used to identify the thread. For example, the Threads[Wait] function can be used to suspend the execution of one thread until other threads have completed. A thread can also get its own identifier by calling Threads[Self].
p := proc() printf( "Thread:-Self() = %d\n", Threads:-Self() ); end proc;
procprintfThread:-Self() = %d\n,Threads:-Selfend proc
id := Threads:-Create( p() );
1
Thread:-Self() = 1
Threads:-Self();
0
Threads:-Wait( id );
Threads:-Wait( seq( Threads:-Create( p() ), i=1..10 ) );
Thread:-Self() = 2 Thread:-Self() = 3
Thread:-Self() = 5 Thread:-Self() = 6 Thread:-Self() = 4 Thread:-Self() = 7 Thread:-Self() = 8 Thread:-Self() = 9 Thread:-Self() = 10 Thread:-Self() = 11
Critical Sections
A critical section is a block of code where a thread can access data that is global between threads. If multiple threads are both in a critical section at the same time, they could modify the global data at the same time. This could leave the global data in an invalid state. To protect critical sections, the Threads package provides mutexes. Mutexes allow a programmer to guarantee that only one thread may enter a critical section at a time. For more information see the Mutex help page.
The following example shows what can happen if multiple threads are allowed to enter a critical section.
p := proc( ) global count; print( count ); count := count+1; end proc;
procglobalcount;printcount;count:=count+1end proc
count := 1;
This creates ten threads to run the function p. One might expect to see the numbers printed from one to ten. Instead the same number may be printed multiple times and other numbers not printed at all.
2
3
4
5
6
8
9
By using a mutex, the critical section can be protected and the expected output is received.
p := proc( m ) global count; Threads:-Mutex:-Lock( m ); print( count ); count := count+1; Threads:-Mutex:-Unlock( m ); end proc;
procmglobalcount;Threads:-Mutex:-Lockm;printcount;count:=count+1;Threads:-Mutex:-Unlockmend proc
m := Threads:-Mutex:-Create();
Threads:-Wait( seq( Threads:-Create( p(m) ), i=1..10 ) );
7
10
Threads:-Mutex:-Destroy( m );
Synchronization
It is very useful for threads to be able to control the execution of other threads. To allow for this, the Threads package provides condition variables. A condition variable allows a thread to put itself to sleep. Another thread is then able to wake that thread up so that it can continue executing. This can be useful in many situations. For example if one thread needs the results of a computation being performed in another thread, then it can wait on the condition variable until the result is available. For more details see the Condition Variable help page.
The following example shows the interaction between a single thread that is producing jobs (called the Producer) and multiple threads that are consuming the jobs (called Consumers). There are two condition variables used. The first, called cp, is used to allow the Producer thread to wait while there are jobs to be performed. When Consumers need more jobs they can signal the Producer to start producing more jobs. After signaling the Producer, a Consumer waits on the second condition variable, cc. Once the Producer has generated more jobs it can awaken Consumers by signaling on cc.
Producer := proc( m, cp, cc, max, mindiff ) global tab, e; local i,j,n; Threads:-Mutex:-Lock( m ); j := 0; tab[ "maxjob" ] := mindiff; tab[ "curjob" ] := 1; for j from 1 to mindiff do tab[ j ] := 2*j; end do; Threads:-ConditionVariable:-Signal( cp ); Threads:-Mutex:-Unlock( m ); n := false; while ( e ) do Threads:-Mutex:-Lock( m ); j := tab[ "maxjob" ]; if ( j - tab[ "curjob" ] > mindiff/2 ) then n := true; Threads:-ConditionVariable:-Wait( cp, m ); end if; for i from j to tab[ "curjob" ] + mindiff do tab[ i ] := 2*i; end do; tab[ "maxjob" ] := tab[ "curjob" ] + mindiff; if ( n ) then Threads:-ConditionVariable:-Broadcast( cc ); n := false; end if; Threads:-Mutex:-Unlock( m ); end do; end proc:
Consumer := proc( m, cp, cc, max ) global tab, e; local n, i, j, num; num := 0; while ( num < max ) do Threads:-Mutex:-Lock( m ); while ( tab[ "curjob" ] = tab[ "maxjob" ] ) do Threads:-ConditionVariable:-Signal( cp ); Threads:-ConditionVariable:-Wait( cc, m ); end do; n := tab[ "curjob" ]; j := tab[ n ]; tab[ "curjob" ] := n + 1; Threads:-Mutex:-Unlock( m ); j := add( i, i=1..j ); num := num+1; Threads:-Mutex:-Lock( m ); tab[ n ] := j; Threads:-Mutex:-Unlock( m ); end do; end proc:
tab := table( ): m := Threads:-Mutex:-Create();
cc := Threads:-ConditionVariable:-Create();
cp := Threads:-ConditionVariable:-Create();
e := true:
Start the Producer thread. We wait on cp until the Producer thread has started.
Threads:-Mutex:-Lock( m ); id1 := Threads:-Create( Producer( m, cp, cc, 31, 10 ) );
32
Threads:-ConditionVariable:-Wait( cp, m ); Threads:-Mutex:-Unlock( m );
Start the Consumer threads. They will each consume 100 jobs and there are 5 threads so we should process 500 jobs.
id2 := [ seq( Threads:-Create( Consumer( m, cp, cc, 100 ) ), i=1..5 ) ];
33,34,35,36,37
Wait for the Consumer threads to finish.
Threads:-Wait( op( id2 ) ); Threads:-Mutex:-Lock( m );
Shutdown the Producer thread.
e := false: Threads:-ConditionVariable:-Signal( cp ); Threads:-Mutex:-Unlock( m ); Threads:-Wait( id1 );
Check the number of processed jobs.
print( tab[ "curjob" ] );
501
Check the results of one job.
print( tab[233] );
108811
print( add( i, i=1..2*233 ) );
More Examples
Sub-division
The following simple example shows how a problem that can be sub-divided maybe made parallel.
MAdd := proc( s, e, threadnum ) local n, i, j, out, blocks, section; n := e-s+1; out := table(); section := floor( n/threadnum ); blocks := [ s, seq( section*i+s, i=1..threadnum-1 ), e+1 ]; Threads:-Wait( seq( Threads:-Create( add( j[i], j[i]=blocks[i]..blocks[i+1]-1), out[i] ), i = 1..threadnum ) ); add( out[i], i=1..threadnum ); end proc;
procs,e,threadnumlocaln,i,j,out,blocks,section;n:=e − s+1;out:=table;section:=floorn/threadnum;blocks:=s,seqsection*i+s,i=1..threadnum − 1,e+1;Threads:-WaitseqThreads:-Createaddj[i],j[i]=blocks[i]..blocks[i+1] − 1,out[i],i=1..threadnum;addout[i],i=1..threadnumend proc
MAdd( 1, 10^5, 1 );
5000050000
MAdd( 1, 10^5, 2 );
MAdd( 1, 10^5, 4 );
Coding Monkeys
This example will show how mutexes and condition variables can be used to control access to shared resources. In this model we have N monkeys sitting around a circular table. Between two monkeys sitting beside each other is a computer monitor, thus there are N monitors. These monkeys are computer programmers who need to write code, unfortunately they will only write code if they can use both of the monitors they are sitting beside.
To model this situation, we will create an array of data structures to model the monitor. Each data structure has a state, which indicates if the monitor is being used, a mutex, which allows a thread to update the data structure, and a condition variable which is used for a thread to wait for a monitor to be come available.
CodingMonkeys := module()
export Init, Start, Cleanup;
local computer, N, lines, maxlines,
getComputer,
waitForComputer,
getComputers,
releaseComputer,
releaseComputers;
getComputer := proc( i )
local got;
Threads:-Mutex:-Lock( computer[i][2] );
if ( computer[i][1] = "free" ) then
computer[i][1] := "in use";
got := true;
else
got := false;
end if;
Threads:-Mutex:-Unlock( computer[i][2] );
return got;
end proc;
waitForComputer := proc( i )
if ( computer[i][1] = "in use" ) then
Threads:-ConditionVariable:-Wait( computer[i][3], computer[i][2] );
releaseComputer := proc( i )
computer[i][1] := "free";
Threads:-ConditionVariable:-Signal( computer[i][3] );
getComputers := proc( i )
local i1, i2;
if ( i = N ) then
i1 := 1;
i2 := N;
i1 := i;
i2 := i+1;
while ( true )
do
if ( not getComputer( i1 ) ) then
waitForComputer( i1 );
if ( getComputer( i2 ) ) then
break;
releaseComputer( i1 );
end do;
releaseComputers := proc( i )
releaseComputer( 1 );
releaseComputer( N );
releaseComputer( i );
releaseComputer( i+1 );
Init := proc( n, m )
local i;
lines := table();
maxlines := m;
N := n;
for i from 1 to N
computer[i] := [ "free", Threads:-Mutex:-Create(),
Threads:-ConditionVariable:-Create() ];
lines[i] := 0;
Start := proc( { print:=false } )
local p,i,threads;
if ( print ) then
p := proc( i )
while ( lines[i] < maxlines )
getComputers( i );
lines[i] := lines[i]+1;
releaseComputers( i );
:-print( i, lines[i] );
threads := [ seq( Threads:-Create( p( i ) ), i=1..N ) ];
Threads[Wait]( op(threads) );
return eval(lines);
Cleanup := proc()
Threads:-Mutex:-Destroy( computer[i][2] );
Threads:-ConditionVariable:-Destroy( computer[i][3] );
end module;
modulelocalcomputer,N,lines,maxlines,getComputer,waitForComputer,getComputers,releaseComputer,releaseComputers;exportInit,Start,Cleanup;end module
CodingMonkeys:-Init( 11, 10 );
CodingMonkeys:-Start();
table( [( 1 ) = 10, ( 2 ) = 10, ( 3 ) = 10, ( 5 ) = 10, ( 4 ) = 10, ( 7 ) = 10, ( 6 ) = 10, ( 10 ) = 10, ( 11 ) = 10, ( 8 ) = 10, ( 9 ) = 10 ] )
CodingMonkeys:-Cleanup();
Return to Index of Example Worksheets
Download Help Document
