Szymański's algorithm: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (7 intermediate revisions by 4 users not shown) | |||
Line 1:
{{draft task}}
<em>Szymański's algorithm</em>
The algorithm allows mutiple processes or tasks to access a serial resource without conflict, using only linear waiting times.
Line 15:
;* [[https://dl.acm.org/doi/10.1145/55364.55425 ACM digital entry for Szymański's paper]]
"""
Szymański's algorithm reference:
Boleslaw K. Szymanski. A simple solution to Lamport's concurrent programming problem with linear wait.
Line 24 ⟶ 23:
"""
=={{header|C#}}==
{{trans|Julia}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Concurrent;
using System.Linq;
using System.Threading;
class Program
{
private static ConcurrentDictionary<int, int> dict = new ConcurrentDictionary<int, int>();
private static int criticalValue = 1;
private static readonly object lockObject = new object();
static void Main(string[] args)
{
TestSzymanski(20);
}
static int Flag(int id)
{
return dict.GetOrAdd(id, 0);
}
static void RunSzymanski(int id, int[] allszy)
{
var others = allszy.Where(t => t != id).ToArray();
dict[id] = 1; // Standing outside waiting room
while (others.Any(t => Flag(t) >= 3))
{
Thread.Yield();
}
dict[id] = 3; // Standing in doorway
if (others.Any(t => Flag(t) == 1))
{
dict[id] = 2; // Waiting for other processes to enter
while (!others.Any(t => Flag(t) == 4))
{
Thread.Yield();
}
}
dict[id] = 4; // The door is closed
foreach (var t in others)
{
if (t >= id) continue;
while (Flag(t) > 1)
{
Thread.Yield();
}
}
// critical section
lock (lockObject)
{
criticalValue += id * 3;
criticalValue /= 2;
Console.WriteLine($"Thread {id} changed the critical value to {criticalValue}.");
}
// end critical section
// Exit protocol
foreach (var t in others)
{
if (t <= id) continue;
while (!new[] { 0, 1, 4 }.Contains(Flag(t)))
{
Thread.Yield();
}
}
dict[id] = 0; // Leave. Reopen door if nobody is still in the waiting room
}
static void TestSzymanski(int N)
{
int[] allszy = Enumerable.Range(1, N).ToArray();
var threads = allszy.Select(i => new Thread(() => RunSzymanski(i, allszy))).ToArray();
foreach (var thread in threads)
{
thread.Start();
}
foreach (var thread in threads)
{
thread.Join();
}
}
}
</syntaxhighlight>
{{out}}
<pre>
Thread 1 changed the critical value to 2.
Thread 2 changed the critical value to 4.
Thread 3 changed the critical value to 6.
Thread 4 changed the critical value to 9.
Thread 5 changed the critical value to 12.
Thread 6 changed the critical value to 15.
Thread 7 changed the critical value to 18.
Thread 8 changed the critical value to 21.
Thread 9 changed the critical value to 24.
Thread 10 changed the critical value to 27.
Thread 11 changed the critical value to 30.
Thread 12 changed the critical value to 33.
Thread 13 changed the critical value to 36.
Thread 14 changed the critical value to 39.
Thread 15 changed the critical value to 42.
Thread 16 changed the critical value to 45.
Thread 17 changed the critical value to 48.
Thread 18 changed the critical value to 51.
Thread 19 changed the critical value to 54.
Thread 20 changed the critical value to 57.
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vb">Const MAX_THREADS = 6
Dim Shared As Any Ptr ttylock
Dim Shared As Integer criticalValue = 1
Sub thread( Byval userdata As Any Ptr )
''
'' This MutexLock makes simultaneously running threads wait for each
'' other, so only one at a time can continue and print output.
'' Otherwise, their Locates would interfere, since there is only one
'' cursor.
''
'' It's impossible to predict the order in which threads will arrive
'' here and which one will be the first to acquire the lock thus
'' causing the rest to wait.
''
Mutexlock ttylock
Dim As Integer id = Cint(userdata)
criticalvalue += id * 3
criticalvalue \= 2
Sleep 25, 1
Print Using "Thread # changed the critical value to ##."; id; criticalvalue
'' MutexUnlock releases the lock and lets other threads acquire it.
Mutexunlock ttylock
End Sub
'' Create a mutex to syncronize the threads
ttylock = Mutexcreate()
'' Create child threads
Dim As Any Ptr handles(1 To MAX_THREADS)
For i As Integer = 1 To MAX_THREADS
handles(i) = Threadcreate(@thread, Cptr(Any Ptr, i))
If handles(i) = 0 Then
Print "Error creating thread:"; i
Exit For
End If
Next
'' This is the main thread. Now wait until all child threads have finished.
For i As Integer = 1 To MAX_THREADS
If handles(i) <> 0 Then
Threadwait(handles(i))
End If
Next
'' Clean up when finished
Mutexdestroy(ttylock)
Sleep</syntaxhighlight>
{{out}}
<pre>Thread 1 changed the critical value to 2.
Thread 4 changed the critical value to 7.
Thread 3 changed the critical value to 8.
Thread 2 changed the critical value to 7.
Thread 5 changed the critical value to 11.
Thread 6 changed the critical value to 14.</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">using ThreadSafeDicts # implement a single lock on all thread's shared values as a lockable Dict (keyed by a process id)
const dict = ThreadSafeDict()
Line 32 ⟶ 208:
""" test the implementation on each thread, concurrently"""
function runSzymański(id, allszy)
others = filter(!=(id), allszy)
dict[id] = 1 # Standing outside waiting room
Line 71 ⟶ 246:
end
function test_Szymański(N)
allszy = collect(1:
@Threads.threads for
runSzymański(i, allszy)
end
end
test_Szymański(20)
</syntaxhighlight>{{out}}
<pre>
Thread
Thread
Thread
Thread
Thread
Thread
Thread 18 changed the critical value to 45.
Thread 3 changed the critical value to 27.
Thread 6 changed the critical value to 22.
Thread 10 changed the critical value to 26.
Thread 13 changed the critical value to 32.
Thread 16 changed the critical value to 40.
Thread 19 changed the critical value to 48.
Thread 4 changed the critical value to 30.
Thread 7 changed the critical value to 25.
Thread 11 changed the critical value to 29.
Thread 14 changed the critical value to 35.
Thread 17 changed the critical value to 43.
Thread 20 changed the critical value to 51.
Thread 8 changed the critical value to 37.
</pre>
Line 170 ⟶ 359:
Thread 3 changed the critical value from 10 (+3*3=19)/2 to 9
</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku" line># 20230822 Raku programming solution
use OO::Monitors;
my \N = 10;
monitor Szymański {
has @.tasks;
my $critical = 0;
method runSzymański($id) {
@.tasks[$id] = 1;
( my @others = @.tasks ).splice: $id,1;
until @others.all ~~ 0|1|2 { $*THREAD.yield }
@.tasks[$id] = 3;
if @others.any ~~ 1 {
@.tasks[$id] = 2;
until @others.any ~~ 4 { $*THREAD.yield }
}
@.tasks[$id] = 4;
until @.tasks[^$id].all ~~ 0|1 { $*THREAD.yield }
$critical = ((my $previous = $critical) + $id * 3) div 2;
say "Thread $id changed the critical value from $previous to $critical";
until @.tasks[$id^..*-1].all ~~ 0|1|4 { $*THREAD.yield }
@.tasks[$id] = 0
}
}
my $flag = Szymański.new: tasks => 0 xx N;
await Promise.allof( ^N .pick(*).map: { start { $flag.runSzymański: $_ } } );</syntaxhighlight>
{{out}}
<pre>Thread 6 changed the critical value from 0 to 9
Thread 1 changed the critical value from 9 to 6
Thread 5 changed the critical value from 6 to 10
Thread 4 changed the critical value from 10 to 11
Thread 7 changed the critical value from 11 to 16
Thread 9 changed the critical value from 16 to 21
Thread 8 changed the critical value from 21 to 22
Thread 3 changed the critical value from 22 to 15
Thread 2 changed the critical value from 15 to 10
Thread 0 changed the critical value from 10 to 5</pre>
=={{header|Wren}}==
Line 181 ⟶ 414:
As Wren fibers don't have an id property, we pass one as an argument when starting the fiber.
<syntaxhighlight lang="
var rand = Random.new()
| |||