Atomic updates

Atomic updates
You are encouraged to solve this task according to the task description, using any language you may know.

Define a data type consisting of a fixed number of 'buckets', each containing an nonnegative integer value, which supports operations to get the current value of any bucket and to transfer value from one bucket to another, preserving the total of all bucket values.

Create one set of buckets, and start three concurrent tasks:

1. As often as possible, pick two buckets and make their values closer to equal.
2. As often as possible, pick two buckets and arbitrarily redistribute their values.
3. 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.

E

In E, any computation occurs in a particular vat. Over its lifetime, a vat executes many individual computations, turns, which are taken from a queue of pending events. The eventual send operator <- puts message-sends on the queue.

Since a vat executes only one turn at a time, each turn is atomic; since the below implementation of the transfer operation does not invoke any other code, the transfer operation is itself automatically atomic and will always preserve the total value provided that it does not have any bugs.

In this example, the tasks are in the same vat as the buckets, but it would be straightforward to write them to live in separate vats.

Works with: E-on-Java

This example uses a Java AWT window to display the current state of the buckets.

<lang e>#!/usr/bin/env rune pragma.syntax("0.9")

def pi := (-1.0).acos() def makeEPainter := <unsafe:com.zooko.tray.makeEPainter> def colors := <awt:makeColor>

1. --------------------------------------------------------------
2. --- Definitions

/** Execute 'task' repeatedly as long 'indicator' is unresolved. */ def doWhileUnresolved(indicator, task) {

 def loop() {
   if (!Ref.isResolved(indicator)) {
     task()
     loop <- ()
   }
 }
 loop <- ()

}

/** The data structure specified for the task. */ def makeBuckets(size) {

   def values := ([100] * size).diverge() # storage
   def buckets {
       to size() :int { return size }
       /** get current quantity in bucket 'i' */
       to get(i :int) { return values[i] }
       /** transfer 'amount' units, as much as possible, from bucket 'i' to bucket 'j'
           or vice versa if 'amount' is negative */
       to transfer(i :int, j :int, amount :int) {
           def amountLim := amount.min(values[i]).max(-(values[j]))
           values[i] -= amountLim
           values[j] += amountLim
       }
   }
   return buckets

}

/** A view of the current state of the buckets. */ def makeDisplayComponent(buckets) {

 def c := makeEPainter(def paintCallback {
   to paintComponent(g) {
     def pixelsW := c.getWidth()
     def pixelsH := c.getHeight()
     def bucketsW := buckets.size()

     g.setColor(colors.getWhite())
     g.fillRect(0, 0, pixelsW, pixelsH)
     
     g.setColor(colors.getDarkGray())
     var sum := 0
     for i in 0..!bucketsW {
       sum += def value := buckets[i]
       def x0 := (i       * pixelsW / bucketsW).floor()
       def x1 := ((i + 1) * pixelsW / bucketsW).floor()
       g.fillRect(x0 + 1, pixelsH - value,
                  x1 - x0 - 1, value)
     }
     
     g.setColor(colors.getBlack())
     g."drawString(String, int, int)"(`Total: $sum`, 2, 20)
   }
 })
 c.setPreferredSize(<awt:makeDimension>(500, 300))
 return c

}

1. --------------------------------------------------------------
2. --- Application setup

def buckets := makeBuckets(100) def done # Promise indicating when the window is closed

1. Create the window

def frame := <unsafe:javax.swing.makeJFrame>("Atomic transfers") frame.setContentPane(def display := makeDisplayComponent(buckets)) frame.addWindowListener(def mainWindowListener {

 to windowClosing(event) :void {
   bind done := null
 }
 match _ {}

}) frame.setLocation(50, 50) frame.pack()

1. --------------------------------------------------------------
2. --- Tasks

1. Neatens up buckets

var ni := 0 doWhileUnresolved(done, fn {

 def i := ni
 def j := (ni + 1) %% buckets.size()
 buckets.transfer(i, j, (buckets[i] - buckets[j]) // 4)
 ni := j

})

1. Messes up buckets

var mi := 0 doWhileUnresolved(done, fn {

   def i := (mi + entropy.nextInt(3)) %% buckets.size()
   def j := (i + entropy.nextInt(3)) %% buckets.size() #entropy.nextInt(buckets.size())
   buckets.transfer(i, j, (buckets[i] / pi).floor())
   mi := j

})

1. Updates display at fixed 10 Hz
2. (Note: tries to catch up; on slow systems slow this down or it will starve the other tasks)

def clock := timer.every(100, def _(_) {

 if (Ref.isResolved(done)) { 
   clock.stop()
 } else {
   display.repaint()
 }

}) clock.start()

1. --------------------------------------------------------------
2. --- All ready, go visible and wait

frame.show() interp.waitAtTop(done)</lang>