# Szymański's algorithm

Szymański's algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Szymański's algorithm is a mutual exclusion algorithm devised by computer scientist Bolesław Szymański.

The algorithm allows mutiple processes or tasks to access a serial resource without conflict, using only linear waiting times. It has application in multitasking and communications, especially if there is a need for massive parallelism with limited waiting times for access to resources by the parallel program's components.

• Implement Szymanski's algorithm utilizing parallel processes, threads, or similar coroutines.
• Your example should implement the steps shown in the Wikipedia's pseudocode at the Wikipedia reference below.

""" Szymański's algorithm reference: Boleslaw K. Szymanski. A simple solution to Lamport's concurrent programming problem with linear wait. Proceedings of the 2nd International Conference on Supercomputing, 1988, Figure 2, Page 624. https://dl.acm.org/doi/pdf/10.1145/55364.55425 https://en.wikipedia.org/wiki/Szyma%C5%84ski%27s_algorithm """

## C#

Translation of: Julia
```using System;
using System.Collections.Concurrent;
using System.Linq;

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)
{
}

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))
{
}
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))
{
}
}
dict[id] = 4; // The door is closed
foreach (var t in others)
{
if (t >= id) continue;
while (Flag(t) > 1)
{
}
}

// 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)))
{
}
}
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();

{
}

{
}
}
}
```
Output:
```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.

```

## FreeBASIC

```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()

Dim As Any Ptr handles(1 To MAX_THREADS)
For i As Integer = 1 To MAX_THREADS
If handles(i) = 0 Then
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
End If
Next

'' Clean up when finished
Mutexdestroy(ttylock)

Sleep```
Output:
```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.```

## Julia

```using ThreadSafeDicts  # implement a single lock on all thread's shared values as a lockable Dict (keyed by a process id)

flag(id) = get(dict, id, 0)

const criticalvalue = [1]

""" test the implementation on each thread, concurrently"""
function runSzymański(id, allszy)
others = filter(!=(id), allszy)
dict[id] = 1                              # Standing outside waiting room
while !all(t -> flag(t) < 3, others)      # Wait for open door
yield()
end
dict[id] = 3                                     # Standing in doorway
if any(t -> flag(t) == 1, others)         # Another process is waiting to enter
dict[id] = 2                          # Waiting for other processes to enter
while !any(t -> flag(t) == 4, others) # Wait for a process to enter and close the door
yield()
end
end
dict[id] = 4                              # The door is closed
for t in others                           # Wait for everyone of lower ID to finish exit
t >= id && continue
while flag(t) > 1
yield()
end
end

# critical section
criticalvalue[1] += id * 3
criticalvalue[1] ÷= 2
println("Thread ", id, " changed the critical value to \$(criticalvalue[1]).")
# end critical section

# Exit protocol
for t in others                           # Ensure everyone in the waiting room has
t <= id && continue
while flag(t) ∉ [0, 1, 4]             # realized that the door is supposed to be closed

yield()
end
end
dict[id] = 0                              # Leave. Reopen door if nobody is still in the waiting room
end

function test_Szymański(N)
allszy = collect(1:N)
runSzymański(i, allszy)
end
end

test_Szymański(20)
```
Output:
```Thread 1 changed the critical value to 2.
Thread 2 changed the critical value to 4.
Thread 5 changed the critical value to 9.
Thread 9 changed the critical value to 18.
Thread 12 changed the critical value to 27.
Thread 15 changed the critical value to 36.
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.
```

## Phix

Translation of: Wren

```without js -- (no support for threads in a browser, as yet...)

integer criticalValue = 1

enum lt3, ne1, ne4, in014

function all_others(integer id,chk)
if i!=id then
integer fi = flags[i]
if (chk=lt3 and fi>=3)
or (chk=ne1 and fi==1)
or (chk=ne4 and fi==4)
or (chk=in014 and i>id and not find(fi,{0,1,4})) then
return false
end if
end if
end for
return true
end function

procedure runSzymanski(integer id)
flags[id] = 1                               // Standing outside waiting room
while not all_others(id,lt3) do             // Wait for open door
sleep(0.01)
end while
flags[id] = 3                               // Standing in doorway
if not all_others(id,ne1) then              // Another thread is waiting to enter
flags[id] = 2                           // Waiting for other threads to enter
while not all_others(id,ne4) do         // Wait for a thread to enter & close door
sleep(0.01)
end while
end if
flags[id] = 4                               // The door is closed
for t=1 to id-1 do                          // Wait for everyone of lower id to exit
while flags[t]>1 do sleep(0.01) end while
end for

// critical section
integer pcv = criticalValue
criticalValue = floor((criticalValue+id*3)/2)
printf(1,"Thread %d changed the critical value from %2d (+3*%d=%2d)/2 to %d\n",{id,pcv,id,pcv+3*id,criticalValue})
// end critical section

// exit protocol
for t=id+1 to nthreads do                   // Ensure everyone in the waiting room has
while not all_others(id,in014) do       // realized door is supposed to be closed
sleep(0.01)
end while
end for
flags[id] = 0                               // Leave. Reopen door if nobody is still
// in the waiting room
end procedure

end for
end for
-- NB: do not terminate main thread before all subthreads are done!
```
Output:

Different every time, of course.

```Thread 4 changed the critical value from  1 (+3*4=13)/2 to 6
Thread 6 changed the critical value from  6 (+3*6=24)/2 to 12
Thread 2 changed the critical value from 12 (+3*2=18)/2 to 9
Thread 1 changed the critical value from  9 (+3*1=12)/2 to 6
Thread 5 changed the critical value from  6 (+3*5=21)/2 to 10
Thread 3 changed the critical value from 10 (+3*3=19)/2 to 9
```

## Raku

```# 20230822 Raku programming solution

use OO::Monitors;

my \N = 10;

monitor Szymański {

my \$critical = 0;

method runSzymański(\$id) {
( my @others = @.tasks ).splice: \$id,1;
until @others.all ~~ 0|1|2 { \$*THREAD.yield }
if @others.any ~~ 1 {
until @others.any ~~ 4 { \$*THREAD.yield }
}
\$critical = ((my \$previous = \$critical) + \$id * 3) div 2;
say "Thread \$id changed the critical value from \$previous to \$critical";
}
}

my \$flag = Szymański.new: tasks => 0 xx N;
await Promise.allof( ^N .pick(*).map: { start { \$flag.runSzymański: \$_ } } );
```
Output:
```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```

## Wren

Translation of: Julia

Although Wren-CLI can spawn any number of fibers, the VM is single threaded and so only one fiber can run at a time. Consequently, there is never a need to lock a shared resource.

Also fibers are cooperatively scheduled and don't use OS threads so we never have to worry about context switches taking place.

The best we can do here is therefore to simulate Szymański's algorithm by randomizing the order in which the fibers start so that the output is not completely deterministic.

As Wren fibers don't have an id property, we pass one as an argument when starting the fiber.

```import "random" for Random

var rand = Random.new()

var flag = {}

var allszy = (1..6).toList

var criticalValue = 1

var runSzymanski = Fn.new { |id|
var others = allszy.where { |t| t != id }.toList
flag[id] = 1                                   // Standing outside waiting room
while (!others.all { |t| flag[t] < 3}) {       // Wait for open door
Fiber.yield()
}
flag[id] = 3                                   // Standing in doorway
if (others.any { |t| flag[t] == 1 }) {         // Another fiber is waiting to enter
flag[id] = 2                               // Waiting for other fibers to enter
while (!others.any { |t| flag[t] == 4 }) { // Wait for a fiber to enter & close door
Fiber.yield()
}
}
flag[id] = 4                                   // The door is closed
for (t in others) {                            // Wait for everyone of lower id to exit
if (t >= id) continue
while (flag[t] > 1) Fiber.yield()
}

// critical section
criticalValue = criticalValue + id * 3
criticalValue = (criticalValue/2).floor
System.print("Fiber %(id) changed the critical value to %(criticalValue).")
// end critical section

// exit protocol
for (t in others) {                            // Ensure everyone in the waiting room has
if (t <= id) continue                      // realized door is supposed to be closed
while (![0, 1, 4].contains(flag[t])) {
Fiber.yield()
}
}
flag[id] = 0                                   // Leave. Reopen door if nobody is still
// in the waiting room
}

var testSzymanski = Fn.new {
var fibers = List.filled(6, 0)
for (id in 1..6) {
fibers[id-1] = Fiber.new(runSzymanski)
flag[id] = 0
}
rand.shuffle(allszy)
for (id in allszy) {
fibers[id-1].call(id)
}
}

testSzymanski.call()
```
Output:

Sample output:

```Fiber 4 changed the critical value to 6.
Fiber 3 changed the critical value to 7.
Fiber 6 changed the critical value to 12.
Fiber 1 changed the critical value to 7.
Fiber 5 changed the critical value to 11.
Fiber 2 changed the critical value to 8.
```