Szymański's algorithm: Difference between revisions
Content added Content deleted
m (→{{header|Julia}}: n not used) |
m (typo in text) |
||
Line 5: | Line 5: | ||
The algorithm allows mutiple processes or tasks to access a serial resource without conflict, using only linear waiting times. |
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 |
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 |
;Task |
Revision as of 03:07, 5 July 2023
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
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.