Jump to content
Sign in to follow this  
Wolfgang-R3f-

Critical section, mutex, atomicity, "spawn/execVM"...

Recommended Posts

Hello,

First apologies for starting a new thread, but i really did not find any clear answers about multithread programming in scripts... dispite i found the questions...

Is there anywhere any sample of sqf script (for ArmaII Op Arrowhead) that would ensure atomicity in a chunck of code ?

Thank's for yours answers.

Edited by Wolfgang[R3f]
grammar

Share this post


Link to post
Share on other sites

I haven't come across any way to ensure atomicity; no semaphores or other safe ways to achieve this.

Share this post


Link to post
Share on other sites

Here is a peace of code, and test.

I think the code is working properly, i need test now.

Enjoy.

the test:

Spawning 100 thread trying to read and write a global variable at the same time.

variable = 0;

critical = [100] call R3FFUNC_CreateCriticalSection;

R3FFUNC_TestCritical_Writer =

{

private ["_threadID", "_variableBefore"];

_threadID = _this select 0;

while { True } do

{

[critical, _threadID] call R3FFUNC_LockCriticalSection;

_variableBefore = variable;

sleep 1;

variable = _variableBefore + 1;

diag_log format ["[%1] (%2 -> %3)", _threadID, _variableBefore, variable];

[critical, _threadID] call R3FFUNC_UnlockCriticalSection;

};

};

R3FFUNC_TestCritical =

{

for [ {_i = 0 }, { _i < 100 }, { _i = _i + 1 } ] do

{

[_i] spawn R3FFUNC_TestCritical_Writer;

};

};

[] call R3FFUNC_TestCritical;

the critical section code:

Lamport's bakery algorithm in sqf script.

// ********************************************************************************************

// Copyright © 2010 Team ~R3F~

//

// This program is free software under the terms of the GNU General Public License version 3.

// You should have received a copy of the GNU General Public License

// along with this program. If not, see <http://www.gnu.org/licenses/>.

//

// @authors team-r3f.org

// @version 1.0

// @date 16/09/2010

//

// critical section implementation based on

// http://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm

// http://black.goucher.edu/~kelliher/cs42/sep27.html

// ********************************************************************************************/

R3FFUNC_InitArray =

{

private ["_array", "_size", "_defaultValue"];

_array = _this select 0;

_size = _this select 1;

_defaultValue = _this select 2;

_array set [_size - 1, _defaultValue];

for [ {_i = 0 }, { _i < _size }, { _i = _i + 1 } ] do

{

_array set [_i, _defaultValue];

};

};

R3FFUNC_MaxValueInArray =

{

private ["_array", "_size", "_maxValue"];

_array = _this select 0;

_size = _this select 1;

_maxValue = 0;

if (_size > 0) then

{

_maxValue = _array select 0;

};

for [ {_i = 1 }, { _i < _size }, { _i = _i + 1 } ] do

{

_maxValue = _maxValue max (_array select _i);

};

_maxValue

};

R3FFUNC_CreateCriticalSection =

{

private ["_maxThreadCount", "_critical", "_entering", "_number"];

_maxThreadCount = _this select 0;

_critical = [[], [], _maxThreadCount];

_entering = _critical select 0;

_number = _critical select 1;

[_entering, _maxThreadCount, False] call R3FFUNC_InitArray;

[_number, _maxThreadCount, 0] call R3FFUNC_InitArray;

diag_log format ["CRITICAL", _critical];

_critical

};

R3FFUNC_LockCriticalSection =

{

private ["_critical", "_threadId", "_maxNumber", "_number", "_entering", "_maxThreadCount"];

_critical = _this select 0;

_threadId = _this select 1;

_entering = _critical select 0;

_number = _critical select 1;

_maxThreadCount = _critical select 2;

assert (_threadId < count _entering);

assert (_threadId < count _number);

_entering set [_threadId, True];

_maxNumber = [_number, _maxThreadCount] call R3FFUNC_MaxValueInArray;

_number set [_threadId, _maxNumber + 1];

_entering set [_threadId, False];

for [ { _j = 0 }, { _j < _maxThreadCount }, { _j = _j + 1 } ] do

{

waitUntil { not ( _entering select _j ) };

waitUntil { not ( ( (_number select _j) != 0) and

( ( (_number select _j) < (_number select _threadId) ) or (((_number select _j) == (_number select _threadId)) and (_j < _threadId))) ) ; };

};

diag_log format ["[%1] ENTER", _threadID];

};

R3FFUNC_UnlockCriticalSection =

{

private [ "_critical", "_threadId", "_number"];

_critical = _this select 0;

_threadId = _this select 1;

diag_log format ["[%1] LEAVE", _threadID];

_number = _critical select 1;

_number set [_threadId, 0];

};

Feel free to try and repport any bug.

---------- Post added at 08:48 PM ---------- Previous post was at 08:40 PM ----------

With Critical Section:

"CRITICAL"

"[18] ENTER"

"[18] (0 -> 1)"

"[18] LEAVE"

"[49] ENTER"

"[49] (1 -> 2)"

"[49] LEAVE"

"[48] ENTER"

"[48] (2 -> 3)"

"[48] LEAVE"

"[50] ENTER"

"[50] (3 -> 4)"

"[50] LEAVE"

"[0] ENTER"

"[0] (4 -> 5)"

"[0] LEAVE"

"[47] ENTER"

"[47] (5 -> 6)"

"[47] LEAVE"

"[99] ENTER"

"[99] (6 -> 7)"

"[99] LEAVE"

"[1] ENTER"

"[1] (7 -> 8)"

"[1] LEAVE"

"[98] ENTER"

"[98] (8 -> 9)"

"[98] LEAVE"

"[96] ENTER"

"[96] (9 -> 10)"

"[96] LEAVE"

Without Critical Section:

"[19] (0 -> 1)"

"[49] (0 -> 1)"

"[50] (1 -> 2)"

"[1] (0 -> 1)"

"[2] (0 -> 1)"

"[3] (0 -> 1)"

"[4] (0 -> 1)"

"[5] (0 -> 1)"

"[6] (0 -> 1)"

"[7] (0 -> 1)"

"[8] (0 -> 1)"

"[9] (0 -> 1)"

"[10] (0 -> 1)"

"[11] (0 -> 1)"

"[12] (0 -> 1)"

"[13] (0 -> 1)"

"[14] (0 -> 1)"

"[15] (0 -> 1)"

"[16] (0 -> 1)"

"[17] (0 -> 1)"

"[18] (0 -> 1)"

"[19] (1 -> 2)"

"[20] (1 -> 2)"

"[21] (1 -> 2)"

"[22] (1 -> 2)"

"[23] (1 -> 2)"

"[24] (1 -> 2)"

"[25] (1 -> 2)"

"[26] (1 -> 2)"

"[27] (1 -> 2)"

"[28] (1 -> 2)"

"[29] (1 -> 2)"

"[30] (1 -> 2)"

"[31] (1 -> 2)"

Edited by Wolfgang[R3f]

Share this post


Link to post
Share on other sites

My testing indicates that statements can be considered atomic which leads to a considerably simpler implementation for critical sections. :)


#define REGISTER_THREAD_ID(ID)  _currentThreadId=ID
#define NULL_ID -1

createCriticalSection=
{
   [true,NULL_ID,0] ;
};

enterCriticalSection={
  [color="Red"] //if we already own the critical section, there is no need to reacquire it[/color]
   if ((_this select 1) != _currentThreadId) then {
     [color="Red"]  //test and set control variable[/color]
       waitUntil{ [_this select 0,_this set [0,false]] select 0} ;
    [color="Red"]   //register ourselves as the owner[/color]
       _this set [1,_currentThreadId];
   }; 
  [color="Red"] //increment reentrancy counter[/color]
   _this set [2,(_this select 2) +1];
};

leaveCriticalSection={
   [color="Red"]//decrement reentrancy counter[/color]
   _this set [2,(_this select 2) -1];
  [color="Red"] //clear ownership and relinquish control if at top of stack[/color]
   if ((_this select 2) ==0) then {
       _this set [1,NULL_ID];
       _this set [0,true];
   };
};

test harness


testThread={
   REGISTER_THREAD_ID(_this select 0);
   while {true} do {
       testSection call enterCriticalSection;
       testVar =_currentThreadId;
       sleep random 1 ;
       if (testVar !=_currentThreadId) then {
           player sidechat format ["%1 Error-another thread entered critical section %2 %3",
           time,testVar,_currentThreadId] ;
       };
       testSection call leaveCriticalSection;
       sleep random 1;
   };
};

monitorThread={
   while {true} do {
       player sideChat format ["%1 thread %2 has critical section",time,testVar] ;
       sleep 1;
   };

   } ;

runtest={
   testVar = 0;
   testSection = call createCriticalSection;
   for "_i" from 1 to 500 do {
       [_i] spawn testThread;
   };
   [] spawn monitorThread ;
};

[] spawn {
   sleep 1;
   call runtest ;
   } ;

If you are not bothered about supporting reentrancy then it's really trivial...


createCriticalSection=
{
   [true] ;
};

enterCriticalSection={
   [color="Red"]  //test and set control variable[/color]
         waitUntil{ [_this select 0,_this set [0,false]] select 0} ;
};

leaveCriticalSection={
       _this set [0,true];
};


Share this post


Link to post
Share on other sites

i was thinking about simplifying things... waitUntil seems to be not interruptible and may change things a lot...

i'll look at your code with care...

thx.

Edited by Wolfgang[R3f]

Share this post


Link to post
Share on other sites
waitUntil seems to be not interruptible and may change things a lot...

I strongly suspect (but haven't thoroughly tested) that individual statements are atomic but that compound statements are interruptable, This test

func={
_z = _this select 0;
   while {a==b} do {
       a=_z;
       b=_z;
       sleep 0.0001;
       } ;
   player sidechat format ["INTERRUPTED %1 %2",a,b];
}

runtest={
   a=1;b=1;
   for "_i" from 1 to 1000 do {
       [_i] spawn { _this call func;} ;
   };
};

[] spawn {
   sleep 1;
   call runtest ;
   } ;

Does show interruptions although replacing func code that ought to be equivalent...

func ={
   _z = _this select 0;
   waituntil {
       a=_z;
       b=_z;
       a!=b;
       } ;
   player sidechat format ["INTERRUPTED %1 %2",a,b]; 
};

I haven't (yet) been able to see interruptions. In any case, my earlier code above assumes only that statements are atomic - I haven't yet found a counter-example of this. :)

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
Sign in to follow this  

×