Atomic updates: Difference between revisions

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''.

<br><br>

 

=={{header|Ada}}==

with Ada.Numerics.Discrete_Random;

end;

end loop;

The array of buckets is a protected object which controls access to its state. The task Equalize averages pairs of buckets. The task Mess_Up moves content of one bucket to another. The main task performs monitoring of the buckets state. Sample output:

<pre>

 

=={{header|AutoHotkey}}==

loop, %Buckets% {

Random, rnd, 0,50

Res.= ">"

return Res

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

The BBC BASIC interpreter is single-threaded so the 'concurrent' tasks are implemented by timer events. In this context an 'atomic' update means one which takes place within a single BASIC statement, so it cannot be 'interrupted'. Two (or more) buckets can be updated atomically by making them RETURN parameters of a procedure.

DIM Buckets%(100)

PROC_killtimer(tid1%)

PROC_killtimer(tid2%)

 

=={{header|C}}==

 

{{libheader|pthread}}

#include <stdlib.h>

#include <stdbool.h>

for(i=0; i < N_BUCKETS; i++) pthread_mutex_destroy(bucket_mutex+i);

return EXIT_SUCCESS;

 

===With OpenMP===

Compiled with <code>gcc -std=c99 -fopenmp</code>. The <code>#pragma omp critical</code> ensures the following block is entered by one thread at a time.

#include <stdlib.h>

#include <omp.h>

 

return 0;

595 800 2508 2750 470 1209 283 314 601 470 Sum: 10000

5 521 3339 1656 351 1038 1656 54 508 872 Sum: 10000

.

752 490 385 2118 1503 508 384 509 1110 2241 Sum: 10000

 

This C# implementation uses a class to hold the buckets and data associated with them. The ThreadSafeBuckets class implements thread-stability, and ensures that two threads cannot operate on the same data at the same time. Additionally, the class uses a seperate mutex for each bucket, allowing multiple operations to occur at once if they do not alter the same buckets.

 

- The previous implementation tracked a "swapped" state - which seems a harder way to tackle the problem. You need to acquire the locks in the correct order, not swap i and j

 

using System; //Rand class

using System.Threading; //Thread, Mutex classes

}

}

 

Sample Output:

11 17 19 1 18 1 12 35 26 16 = 156

</pre>

 

=={{header|Clojure}}==

Function returning a new map containing altered values:

(let [{f-bal from t-bal to} m

f-bal (- f-bal amt)

(if (or (neg? f-bal) (neg? t-bal))

(throw (IllegalArgumentException. "Call results in negative balance."))

Since clojure data structures are immutable, atomic mutability occurs via a reference, in this case an atom:

Now for the test:

(let [{a-val a b-val b} m

diff (- a-val b-val)

 

(.start thread-eq)

 

=={{header|Common Lisp}}==

Depends on libraries in Quicklisp. STMX is a library that provides Software Transactional Memory.

 

(defpackage :atomic-updates

(setf *running* t)

(bt:make-thread (lambda () (runner (constantly 0.5))))

{{out}}

#<SB-THREAD:THREAD "Anonymous thread" RUNNING {10058441D3}>

ATOMIC-UPDATES> (loop repeat 3 do (print-buckets) (sleep 1))

Buckets: #(1 2 3 3 2 8 33 23 0 8 4 11 24 2 3 5 32 8 2 26)

Sum: 200

 

=={{header|D}}==

This implements a more scalable version than most of the other languages, by using a lock per bucket instead of a single lock for the whole array.

 

import std.conv: text;

import std.random: uniform, Xorshift;

task!equalize(data).executeInNewThread();

task!display(data).executeInNewThread();

{{out}}

<pre>N. transfers, buckets, buckets sum:

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

 

pragma.syntax("0.9")

 

 

frame.show()

 

=={{header|Erlang}}==

[0,11,7,0,4,16,7,0,10,0] = 55

</pre>

-module( atomic_updates ).

-export( [buckets/1, buckets_get/2, buckets_get_all/1, buckets_move_contents/4, task/0] ).

buckets_move_contents( Amount, From, To, Buckets ),

redistribute_loop( N, Buckets ).

 

=={{header|Euphoria}}==

if src < 1 or src > length(s) or dest < 1 or dest > length(s) or amount < 0 then

return -1

printf(1," sum: %d\n", {sum(buckets)})

task_yield()

 

Output:

The Buckets class is thread safe and its private higher-order Lock function ensures that locks are taken out in order (to avoid deadlocks):

 

open System.Threading

 

Thread.Sleep 100

bucket.Print()

 

This program performs a million concurrent transfers. Typical output is:

 

[|100; 100; 100; 100; 100; 100; 100; 100; 100; 100|] = 1000

[|119; 61; 138; 115; 157; 54; 82; 58; 157; 59|] = 1000

[|208; 147; 18; 25; 178; 159; 23; 170; 36; 36|] = 1000

Press any key to continue . . .

 

=={{header|Go}}==

 

import (

}

}

{{out}}

<pre>

=={{header|Groovy}}==

Solution:

 

def cells = []

}

Thread.sleep(500)

 

Output:

So, at any given time, the current value map is either in the MVar or being examined or replaced by one thread, but not both. The IntMap held by the MVar is a pure immutable data structure (<code>adjust</code> returns a modified version), so there is no problem from that the ''display'' task puts the value back before it is done printing.

 

 

import Control.Concurrent (forkIO, threadDelay)

forkIO (roughen buckets)

forkIO (smooth buckets)

 

Sample output:

The following only works in Unicon:

 

 

procedure main(A)

buckets[b1] -:= x

buckets[b2] +:= x

 

Sample run:

=={{header|Java}}==

{{works with|Java|8+}}

import java.util.concurrent.ThreadLocalRandom;

 

}

}

 

{{out}}

 

=={{header|Julia}}==

function runall()

spinner = ReentrantLock()

bucketsum() = sum(buckets)

function equalizer()

if trylock(spinner)

i, j = picktwo()

sm = buckets[i] + buckets[j]

totaltrans += 1

unlock(spinner)

end

end

function redistributor()

smallpause()

if trylock(spinner)

i, j = picktwo()

sm = buckets[i] + buckets[j]

buckets[j] = sm - buckets[i]

totaltrans += 1

function accountant()

count = 0

smallpause()

if trylock(spinner)

end

end

end

@async equalizer()

@async redistributor()

@async accountant()

end

Current state of buckets: [62, 32, 90, 50, 9, 43, 16, 71, 67, 99, 22, 44, 63, 85, 78, 7]. Total in buckets: 838

Current state of buckets: [58, 25, 41, 30, 9, 79, 42, 43, 32, 66, 110, 123, 90, 35, 13, 42]. Total in buckets: 838

Current state of buckets: [49, 63, 24, 38, 64, 79, 75, 70, 69, 68, 50, 74, 12, 60, 6, 37]. Total in buckets: 838

Current state of buckets: [32, 20, 82, 70, 54, 41, 87, 15, 15, 44, 82, 55, 17, 33, 87, 104]. Total in buckets: 838

 

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.util.concurrent.ThreadLocalRandom

thread(name = "transferrer") { buckets.transferRandomAmount() }

thread(name = "printer") { buckets.print() }

 

Sample output:

=={{header|Lasso}}==

Lasso thread objects are thread-safe by design.

data

private buckets = staticarray_join(10, void),

stdoutnl(#buckets->asString + " -- total: " + #total)

}

 

{{out}}

=={{header|Logtalk}}==

The following example can be found in the Logtalk distribution and is used here with permission. Works when using SWI-Prolog, XSB, or YAP as the backend compiler.

:- object(buckets).

 

 

:- end_object.

 

Sample output:

 

?- buckets::start.

Sum of all bucket values: 52

[11,6,10,4,0,4,5,5,4,3]

true.

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

ReplacePart[

bucks, {src -> Max[bucks[[src]] - n, 0],

dest = RandomInteger[{1, 20}]},

bucks = transfer[bucks, src, dest,

{{out}}

<pre>Original sum: &lt;number&gt;

Current sum: &lt;same number, stays fixed&gt;</pre>

This simply uses a variable named <tt>comp</tt> to determine whether or not it is currently computing something.

 

=={{header|Oz}}==

Uses a lock for every bucket. Enforces a locking order to avoid deadlocks.

 

%%

%% INIT

thread for do {Smooth {Pick} {Pick}} end end

thread for do {Roughen {Pick} {Pick}} end end

 

Sample output:

buckets(24 68 58 43 78 85 43 66 14 48 ,,,) sum: 5000

buckets(36 33 59 38 39 23 55 51 43 45 ,,,) sum: 5000

buckets(51 51 49 50 51 51 51 49 49 49 ,,,) sum: 5000

buckets(43 28 27 60 77 41 36 48 72 70 ,,,) sum: 5000

 

=={{header|PARI/GP}}==

 

=={{header|Perl}}==

use 5.10.0;

 

};

 

 

{{out}}

<pre>

child processes to handle the tasks, as this is the standard way

for general PicoLisp applications.

 

# E/R model

(class +Bucket +Entity)

 

 

# Create *Buckets buckets with values between 1 and 999

(new T '(+Bucket) 'key K 'val (rand 1 999)) )

(commit)

 

# Pick a random bucket

(de pickBucket ()

(db 'key '+Bucket (rand 1 *Buckets)) )

 

# First process

 

# Second process

 

# Third process

(unless (fork)

(loop

(printsp (: val)) )

"-- Total: "

(sum '((This) (: val)) Lst) ) )

 

Output:

<pre>70 236 582 30 395 215 525 653 502 825 129 769 722 440 708 -- Total: 6801

 

=={{header|PureBasic}}==

#TotalAmount=200

Global Dim Buckets(#Buckets)

Quit=#True ; Tell threads to shut down

WaitThread(Thread1): WaitThread(Thread2)

 

=={{header|Python}}==

This code uses a ''threading.Lock'' to serialize access to the bucket set.

 

import threading

import random

# wait until all worker threads finish

t1.join()

 

Sample Output:

 

=={{header|Racket}}==

 

(struct bucket (value [lock #:auto])

 

(thread (λ () (for ([_ (in-range 500000)]) (equalize (random 10) (random 10)))))

 

Sample output:

9 (171429). (27 169 298 9 26 184 134 27 110 16 - 1000)

10 (192857). (54 80 38 52 29 14 42 173 246 272 - 1000)

</pre>

 

=={{header|Ring}}==

# Project : Atomic updates

 

bucket = list(10)

bucket[a1] = bucket[a1] - transfer

bucket[a2] = bucket[a2] + transfer

Output:

<pre>

</pre>

 

=={{header|Ruby}}==

 

# A collection of buckets, filled with random non-negative integers.

exit 1

end

 

Sample Output:

455 455 455 455 454 454 455 455, total 3638

755 3 115 10 598 1326 515 316, total 3638 </pre>

=={{header|Run BASIC}}==

FOR i = 1 TO 10 : bucket(i) = int(RND(0)*100) : NEXT

 

bucket(a1) = bucket(a1) - transfer

bucket(a2) = bucket(a2) + transfer

<pre> Display: 24 50 50 85 63 49 50 91 10 2 Total:474

Flatten: 47 47 47 47 47 47 47 47 47 51 Total:474

=={{header|Rust}}==

{{libheader|rand}}

 

use std::sync::{Arc, Mutex};

thread::sleep(sleep_time);

}

 

=={{header|Scala}}==

object AtomicUpdates {

 

}

}

 

=={{header|Tcl}}==

<br>

{{works with|Tcl|8.5}}

package require Tk

 

tkwait window .

tsv::set still going 0

 

=={{header|zkl}}==

Threads and thread safe objects (locks, lists, ints, etc) are built in.

const N=10;

var [const]

 

fcn threadA(b){ while(1) { b.transferArb(); } }

do(10){ threadA.launch(b); } do(10){ threadE.launch(b); }

 

vm.numThreads," threads");

Atomic.sleep(2.5);

{{out}}

<pre>

</pre>

Another solution, using a Pipe as a "holding tank". Pipes are thread safe queues. This code just moves the values to and from the pipe to synchronize changes. The use of this class is the same as above, just change b:=B() to b:=C();

const N=10;

var [const]

v2;

}

 

 

{{omit from|LaTeX}}

{{omit from|M4}}

{{omit from|Make}}

{{omit from|PlainTeX}}

{{omit from|TI-89 BASIC}} <!-- Does not have concurrency or background processes. -->

{{omit from|XSLT}}