Szymański's algorithm: Difference between revisions
Content added Content deleted
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> |
||