Szymański's algorithm: Difference between revisions
m remove dup typo |
m →{{header|Julia}}: don't use threadid, use a per coroutine internally generated program process id to allow the number of processes to be > max threads. |
||
Line 15: | Line 15: | ||
;* [[https://dl.acm.org/doi/10.1145/55364.55425 ACM digital entry for Szymański's paper]] |
;* [[https://dl.acm.org/doi/10.1145/55364.55425 ACM digital entry for Szymański's paper]] |
||
""" |
|||
=={{header|Julia}}== |
|||
<syntaxhighlight lang="julia">""" |
|||
Szymański's algorithm reference: |
Szymański's algorithm reference: |
||
Boleslaw K. Szymanski. A simple solution to Lamport's concurrent programming problem with linear wait. |
Boleslaw K. Szymanski. A simple solution to Lamport's concurrent programming problem with linear wait. |
||
Line 24: | Line 23: | ||
""" |
""" |
||
using ThreadSafeDicts # implement a single lock on all |
using ThreadSafeDicts # implement a single lock on all thread's shared values as a lockable Dict (keyed by thread id) |
||
const dict = ThreadSafeDict() |
const dict = ThreadSafeDict() |
||
Line 32: | Line 31: | ||
""" test the implementation on each thread, concurrently""" |
""" test the implementation on each thread, concurrently""" |
||
function runSzymański(allszy) |
function runSzymański(id, allszy) |
||
id = Threads.threadid() |
|||
others = filter(!=(id), allszy) |
others = filter(!=(id), allszy) |
||
dict[id] = 1 # Standing outside waiting room |
dict[id] = 1 # Standing outside waiting room |
||
Line 39: | Line 37: | ||
yield() |
yield() |
||
end |
end |
||
dict[id] = 3 # Standing in doorway |
dict[id] = 3 # Standing in doorway |
||
if any(t -> flag(t) == 1, others) # Another process is waiting to enter |
if any(t -> flag(t) == 1, others) # Another process is waiting to enter |
||
dict[id] = 2 # Waiting for other processes to enter |
dict[id] = 2 # Waiting for other processes to enter |
||
Line 71: | Line 69: | ||
end |
end |
||
function test_Szymański() |
function test_Szymański(N) |
||
allszy = collect(1: |
allszy = collect(1:N) |
||
@Threads.threads for |
@Threads.threads for i in eachindex(allszy) |
||
runSzymański(allszy) |
runSzymański(i, allszy) |
||
end |
end |
||
end |
end |
||
test_Szymański() |
test_Szymański(20) |
||
</syntaxhighlight>{{out}} |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Thread |
Thread 1 changed the critical value to 2. |
||
Thread |
Thread 2 changed the critical value to 4. |
||
Thread |
Thread 5 changed the critical value to 9. |
||
Thread |
Thread 9 changed the critical value to 18. |
||
Thread |
Thread 12 changed the critical value to 27. |
||
Thread |
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. |
|||
</pre> |
</pre> |
||
Revision as of 09:06, 7 July 2023
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.
- 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
""" 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(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) @Threads.threads for i in eachindex(allszy) runSzymański(i, allszy) end
end
test_Szymański(20)
</syntaxhighlight>
- 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
Uses threads rather than tasks. While there is a task_yield(), there isn't a thread_yield() [maybe I should add one], so used sleep(0.01) instead.
without js -- (no support for threads in a browser, as yet...) constant nthreads = 6 sequence flags = repeat(0,nthreads) integer criticalValue = 1 enum lt3, ne1, ne4, in014 function all_others(integer id,chk) for i=1 to nthreads do 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 sequence threads = repeat(0,nthreads) for id=1 to nthreads do threads[id] = create_thread(runSzymanski,{id},CREATE_SUSPENDED) end for for id in shuffle(tagset(nthreads)) do resume_thread(threads[id]) end for -- NB: do not terminate main thread before all subthreads are done! wait_thread(threads)
- 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
Wren
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.