Thread starvation question

[Josip Gracin]

Hi!

In the ants simulation, the evaporator runs a transaction for each
cell. What if it had to do it all in a single transaction? It would
enter a transaction, start modifying all the cells, and by the time it
was ready to commit the transaction, what are the chances that no
other thread had modified a cell and committed the change, causing the
evaporator's transaction to restart?

Seems to me that large transactions (i.e. transactions that modify
lots of refs) could easily be starved out by many small transactions.

[Rich Hickey]

Absolutely - transactions, magical as they are, still don't remove
issues of contention from system design. They just ensure coordination
correctness. Any program with a long-running/wide-ranging writing
activity contending for resources with many lightweight writing
activities is going to face challenges.

There's not a single recipe for handling this. One way is to break up
the big job, as does the ant sim for evaporation. Another technique,
well supported by the Clojure STM, is to make as many of the write
operations as possible commutative.

It ends up that evaporation is commutative, and evaporate could run
successfully as a single transaction like this (moving the dosync
around the entire loop and changing alter to commute):

(defn evaporate
"causes all the pheromones to evaporate a bit"
[]
(dosync
(dorun
(for [x (range dim) y (range dim)]
(let [p (place [x y])]
(commute p assoc :pher (* evap-rate (:pher @p))))))))

commutes, like reads, never block writers, commuters, or other
readers, nor are they impeded by concurrent writes.

If you must alter in a wide-ranging/longer-running transaction, one
technique is to rip through all refs you intend to use with 'ensure'
before starting the work, thus locking them for this transaction and
avoiding proceeding speculatively only to fail late in the
transaction. The STM does have transaction age and lock barging logic
to ensure that one of multiple wide-ranging transactions will proceed.

Yet another technique is to feed all altering work for a logical set
of data through a single agent, thus serializing it while still
supporting concurrent reads and commutes.

There is no one-size-fits all concurrency strategy/recipe, but I think
you'll find, once you become familiar with all of the options, Clojure
provides a small yet powerful and easy-to-use set of tools for
architecting something that works well and correctly.

Rich