Chymyst / chymyst-core

Declarative concurrency in Scala - The implementation of the chemical machine
Apache License 2.0
155 stars 11 forks source link

Implement granular locking #115

Closed winitzki closed 7 years ago

winitzki commented 7 years ago

Implement two locking principles:

  1. Decreasing monotonicity: Once a lock is obtained on a subset of items, there cannot be a further lock obtained on a larger subset while still holding the lock on a smaller subset. The only change in locking can be the release of the lock on the entire subset or on a part of the subset.
  2. Non-contention: We lock the items only because we cannot reach the correct decision without examining these items, and because other agents need to be prevented from withdrawing these items while we are still examining them. We release the lock on an item only when we learn that the correct decision can still be reached without using that item.
winitzki commented 7 years ago

Latest PRs increased granularity but did not implement the algorithms described here. It appears that these algorithms will not significantly improve performance or will degrade it, while introducing immense complexity into the imperative core of Chymyst.