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 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.

Task

• 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.

See also

• [Wikipedia entry for Szymański's algorithm]
• [ACM digital entry for Szymański's paper]

Julia

""" 
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
"""

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

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

const criticalvalue = [1]

""" test the implementation on each thread, concurrently"""
function runSzymański(allszy)
	id = Threads.threadid()
    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()
    allszy = collect(1:Threads.nthreads())
    @Threads.threads for _ in allszy
        runSzymański(allszy)
    end
end

test_Szymański()

Output:

Thread 3 changed the critical value to 5.
Thread 5 changed the critical value to 10.
Thread 1 changed the critical value to 6.
Thread 2 changed the critical value to 6.
Thread 4 changed the critical value to 9.
Thread 6 changed the critical value to 13.

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.