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.