

Task

Define a data type consisting of a fixed number of 'buckets', each containing a nonnegative integer value, which supports operations to:

 get the current value of any bucket
 remove a specified amount from one specified bucket and add it to another, preserving the total of all bucket values, and clamping the transferred amount to ensure the values remain non-negative

In order to exercise this data type, create one set of buckets, and start three concurrent tasks:

 As often as possible, pick two buckets and make their values closer to equal.
 As often as possible, pick two buckets and arbitrarily redistribute their values.
 At whatever rate is convenient, display (by any means) the total value and, optionally, the individual values of each bucket.


The display task need not be explicit; use of e.g. a debugger or trace tool is acceptable provided it is simple to set up to provide the display.


This task is intended as an exercise in atomic operations.   The sum of the bucket values must be preserved even if the two tasks attempt to perform transfers simultaneously, and a straightforward solution is to ensure that at any time, only one transfer is actually occurring — that the transfer operation is atomic.




declare
  %%
  %% INIT
  %%
  NBuckets = 100
  StartVal = 50
  ExpectedSum = NBuckets * StartVal
 
  %% Makes a tuple and calls Fun for every field
  fun {Make Label N Fun}
     R = {Tuple.make Label N}
  in
     for I in 1..N do R.I = {Fun} end
     R
  end
 
  Buckets = {Make buckets NBuckets fun {$} {Cell.new StartVal} end}
  Locks = {Make locks NBuckets Lock.new}
  LockList = {Record.toList Locks}
 
  %%
  %% DISPLAY
  %%
  proc {Display}
     Snapshot = {WithLocks LockList
                 fun {$}
                    {Record.map Buckets Cell.access}
                 end
                }
     Sum = {Record.foldL Snapshot Number.'+' 0}
  in
     {Print Snapshot}   
     {System.showInfo "  sum: "#Sum}
     Sum = ExpectedSum %% assert
  end
 
  %% Calls Fun with multiple locks locked and returns the result of Fun.
  fun {WithLocks Ls Fun}
     case Ls of L|Lr then
        lock L then
           {WithLocks Lr Fun}
        end
     [] nil then {Fun}
     end
  end
 
  %%
  %% MANIPULATE
  %%  
  proc {Smooth I J}
     Diff = @(Buckets.I) - @(Buckets.J) %% reading without lock: by design
     Amount = Diff div 4
  in
     {Transfer I J Amount}
  end
 
  proc {Roughen I J}
     Amount = @(Buckets.I) div 3 %% reading without lock: by design
  in
     {Transfer I J Amount}
  end
 
  %% Atomically transfer an amount from From to To.
  %% Negative amounts are allowed;
  %% will never make a bucket negative.
  proc {Transfer From To Amount}
     if From \= To then
        %% lock in order (to avoid deadlocks)
        Smaller = {Min From To}
        Bigger = {Max From To}
     in
        lock Locks.Smaller then
           lock Locks.Bigger then
              FromBucket = Buckets.From
              ToBucket = Buckets.To
              NewFromValue = @FromBucket - Amount
              NewToValue = @ToBucket + Amount
           in
              if NewFromValue >= 0 andthen NewToValue >= 0 then
                 FromBucket := NewFromValue
                 ToBucket := NewToValue
              end
           end
        end
     end
   end
 
  %% Returns a random bucket index.
  fun {Pick}
     {OS.rand} mod NBuckets + 1
  end
in
  %%
  %% START
  %%
  thread for do {Smooth {Pick} {Pick}} end end
  thread for do {Roughen {Pick} {Pick}} end end
  for do {Display} {Time.delay 50} end