Skip to content

Instantly share code, notes, and snippets.

@seymores
Last active January 17, 2017 16:40
Show Gist options
  • Save seymores/18c874aaf0ff78df18c0d27038539658 to your computer and use it in GitHub Desktop.
Save seymores/18c874aaf0ff78df18c0d27038539658 to your computer and use it in GitHub Desktop.
Description of solution for Question 2. Test for ref consistency in multi-threaded environment
;; Question 2
;; 1. Create a unit test that reproduces the problem
;; 2. Explain what is going wrong
;; 3. Fix the bug
;; 0. Start with the ref a, ref b and the advance-* functions
(def a (ref 1))
(def b (ref 1))
(defn advance-a []
(dosync
(if (< (+ @a @b) 3)
(alter a inc))))
(defn advance-b []
(dosync
(if (< (+ @a @b) 3)
(alter b inc))))
; //////////////////////////////////////////////////////////////////////////
;; 1. Lets get some helpful functions
(defn reset
"Reset @a and @b to default state, useful for testing"
[]
(dosync
(ref-set a 1)
(ref-set b 1)))
;; 2. delay-then-run is use to simulate a multi-threaded environment with delays.
;; Another alternative is to use Future instead of this Java-ish thread method.
(defn delay-then-run
"Run the given function after the specified delay in another thread"
[func delay]
(.start (Thread. (fn [] (Thread/sleep delay) (func)))))
;; 3. A simple test run function to call advance-a and advance-b at the same time in different thread.
(defn testrun []
(do
(reset)
(delay-then-run advance-a 10)
(delay-then-run advance-b 10)))
(defn check
"Simply return the deref a and deref b in tuple"
[]
[@a @b])
(check)
; most of the time returns [2 2], expected to be [1 2] or [2 1], violating (<= (+ @a @b) 3) invariant
(clojure.test/is (not (= [2 2] (check))))
; Will fail with
; FAIL in () (form-init6496152475416413181.clj:1)
;
; expected: (not (= [2 2] (check)))
; actual: (not (not true))
; false
;; *Explanation*
;; At this point surprised to see @a = 2 and @b = 2, breaking the **(<= (+ @a @b) 3)** invariant.
;; advance-b (could be advance-a function too) at the execution of the thread run time are holding
;; the read-time value of a and b, but dosync doesn't gurantee the refs didn't change state outside
;; of the transaction before commit.
;; There is a history mechanism in place which stores a number of previous values for each Ref but
;; still same problem of invariant on read data.
;; *Solution*
;; The use of 'ensure' will prevent write skew -- to protect Ref from modification by other transactions
;; The below changes -- added `(ensure a) (ensure b)` to advance-a and advance-b will fix this bug.
(defn advance-a []
(dosync
(ensure a)
(ensure b)
(if (< (+ @a @b) 3)
(alter a inc))))
(defn advance-b []
(dosync
(ensure a)
(ensure b)
(if (< (+ @a @b) 3)
(alter b inc))))
;; 4. Lets run the test again and check
(defn testrun []
(do
(reset)
(delay-then-run advance-a 10)
(delay-then-run advance-b 10)))
(check)
; returns [1 2] most of the time and consistently never [2 2], doesn't violate the (<= (+ @a @b) 3) invariant again.
(clojure.test/is (not (= [2 2] (check))))
; Pass this test ✅
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment