I'm doing dining philosophers in cljs and wanted to recreate the standard deadlock situation before moving to the standard deadlock prevention strategies. However, I'm unable to actually trigger deadlock here. Does anyone see anything that would not allow the cyclic deadlock?

playing with it some more, it seems that there is no context switching between the (<! left) and (<! right) takes. if i put a small timeout channel take there it does happen. I thought it was a bit more cooperative multitasking there but it doesn't seem like it

That is because you are buffering the channels

The buffer immediately accepts 1 item, without having to wait for a consumer

Why would they switch?

If you find what you're looking for in the channel immediately, it won't context switch

It will once something is waiting only

Otherwise it would just slow down the whole process

But, it does switch from the put to the take

You can think of it as a rendez-vous

put waits for a taker and take waits for a puter

Well, up to the buffer, so like @hiredman said, in your case the puter won't wait for the taker unless the buffer is full and the taker won't wait for the puter unless the buffer is empty

So the buffers control when things get to switch in a way. That said, from what I understand, two takes in a row won't switch if the take immediately succeeds.

I believe the context switch is round-robin? Actually, can someone confirm? So if you have something putting super quickly, and something taking a more slowly, it won't starve other processes, since between each rendez-vous of the put/take, it'll make a visit to the other processes

I like to think of it as I am the process. As I'm doing something, I won't stop to do anything else, until I reach a point where I can't continue on my current task, because I'm waiting for something, that's when I'll wonder off and see if there's anything else I can do in the mean time. Rince and Repeat

the context switch is a fifo queue

as in, go blocks are scheduled by being put on the end of a queue, which some threads are pulling tasks off and running

there is no central list of go blocks that is traversed to schedule them

the way they are schedule is the go macro turns them into callbacks attached to channels, and when something happens on the channel the callback is put on the queue

having no central scheduler/controller is one of the most clever parts of core.async imo (esp when you look at alts etc)

Couldn't that open the door for starvation?

If two process just ping-pong with each other forever

they still wait in the queue

if A and B are ping ponging, then first A runs, which puts B on the queue and puts A "to sleep", and then B is taken off the queue and run, which puts A on the queue and puts B "to sleep"

at any point something else could be put on the queue which would be process beforeish(there are acutally multiple threads consuming and running tasks) the next A or B

there have been bugs related to this I think in the cljs implementation, where it would try to optimize by skipping the queue step, would easily results in starvation on a js vm because you only have one thread

That's exactly the scenario I was thinking. I can see how the thread pool for processed on the JVM would help a bit, but it still seems at least theoretically prone to it

no, given a fifo queue it won't happen, if you go through each step of A and B ping ponging, and assume at some point something else puts something on the queue, you can show eventually it reaches the front of the queue ahead of any work for A and B

Right, but how is that something else going to do that, if A and B are ping ponging

in the specific case of core.async, core.async itself has multiple threads in its pool and the jvm has multiple threads outside of core.async

but even if you are restrict yourself to a single thread and only core.async, it is still the case

in order for a task to be starved it must exist first

if the task exists for core.async it is either currently running, attached as a callback to some channel, or in the queue to be run

if it is attached to some channel that means it is waiting for activity on that channel and has nothing to do

when a task has nothing to do it cannot be starved (by definition starvation is a task with work to do not being able to get time to run)

so in order for a task to be starved it is either currently running or currently in the queue

"in order for a task to be starved it must exist first", hum, is this true? wouldn't task start processing before every go block is evaluated?

it is true

Say you had a go-loop just taking and puting on a channel

if you write a go block you cannot complain it is being starved because it is never run in my repl

and later you have another go trying to put a "stop" on it, which should sto the go-loop from ping-ponging

if you write a program you cannot say it is being starved by the scheduler if you never run it

And we are in ClojureScript with only one thread ?

the problem with taking clojurescript as an example is I have seen people writing patches for cljs choose performance over what in my estimation is "correct" over and over again, so it feels like thin ice

The key invariants are: at some point one of the processes must yield (do some channel operation that can't complete immediately so it registers itself as a callback on the channel) and when it does complete the task must pass through the fifo queue before running again

(def a (async/chan 1))
(async/put! a 10)
(do (async/go-loop [a a]
      (let [v (async/<! a)]
        (println v)
        (async/>! a 20)
        (when v
          (recur a))))
    (async/go (async/>! a false)))

I think something like that

Logically, given a single threaded environment, I feel it would starve the second go process, and thus infinite loop

that is not two processes ping ponging

Hum..., isn't each recur a new process?

no

and even if it was, you would have successive processes doing stuff to a, not two processes ping ponging

True, sorry, I guess I meant with a buffer of 0:

(def a (async/chan))
  (async/put! a 10)
  (do (async/go-loop [a a]
        (let [v (async/<! a)]
          (println v)
          (async/>! a 20)
          (when v
            (recur a))))
      (async/go (println "ending the loop")
                (async/>! a false)))

Otherwise the first go-loop never yielded

not sure what changing the buffer size is supposed to change about it not being two processes ping ponging

Well, on the take of a, a continuation of the rest is created and put on the queue no ?

a ping pong is A sending a ping to B then waiting for a pong, B waiting for the ping, then sending a pong to A, then A sending a ping to B

right, so here I'm using the same loop for that, put its like sending a ping to itself 😛

Okay, I mean you can do it with two seperate go block as well

you cannot

But I was seeing this as recursion

recursion is not the same thing as multiple processes

if instead of saying "couldn't two ping ponging processes lead to starvation" you said "couldn't an infinite loop that does nothing but read and write to a channel that no one else is reading and writing to lead to starvation", the answer is yes, because those are different things

(do
  (def a (async/chan))
  (async/put! a 10)
  (async/go-loop [a a]
    (when a
      (async/>! a 20)
      (recur a)))
  (async/go-loop [a a]
    (when a
      (println (async/<! a))
      (recur a)))
  (async/go (println "ending the loop")
            (async/close! a)))

but even then I think it maybe a case where cljs has "optimized" things and it breaks things

What about this, this infinite loops, but isn't that due to starvation?

unless I just have a bug

Even in Clojure it infinite loops

nah, I was wrong, I was just checking the code

closing a doesn't end the loops

because you don't stop looping when a is closed

well, possibly my repl chokes because of the print, and it could eventually close

Wouldn't, oh ya

sorry

a is always truthy

ya, got confused with my old version

Hum... okay not sure how to create a repro of the scenario I'm imagining then 😛

on clojure that will terminate always anyway because you need at least 8 tasks not yielding

Alright, well I can't make it fail 😛

This works as well, in clojure and cljs:

(do
  (def a (async/chan))
  (def keep-going (atom true))
  (async/go-loop [a a]
    (when @keep-going
      (async/>! a 20)
      (recur a)))
  (async/go-loop [a a]
    (when @keep-going
      (println (async/<! a))
      (recur a)))
  (async/go (println "ending the loop")
            (reset! keep-going false)
            (async/close! a)))

So, something makes the third go block execute, even though the first and second ping/pong between putting and taking

I think its got something to do with the evaluation actually

Ya, if I just send those 3 forms to the REPL, then it infinite loops, but wrapped in a do it doesn't, will try from a file