How to resolve the algorithm Atomic updates step by step in the Java programming language

Published on 12 May 2024 09:40 PM
#Java

How to resolve the algorithm Atomic updates step by step in the Java programming language

Table of Contents

Problem Statement

Define a data type consisting of a fixed number of 'buckets', each containing a nonnegative integer value, which supports operations to: In order to exercise this data type, create one set of buckets, and start three concurrent tasks:

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.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Atomic updates step by step in the Java programming language

Atomic Updates

This Java program demonstrates how to perform concurrent updates on an array using atomic operations. It implements two threads that modify the array elements while a third thread prints the updated values periodically.

Class Structure:

  • Buckets: This class represents an array of integer values. It provides synchronized methods for accessing and transferring values between buckets atomically.
  • AtomicUpdates: This is the main class. It initializes the array, creates the threads to perform updates and printing, and starts them.

Main Method:

  • Generates an array of random integer values.
  • Creates an instance of the Buckets class using the initial values.
  • Starts three threads:
    • Equalizer: Transfers a random amount between two buckets until the difference between bucket values is less than half.
    • Transferrer: Transfers random amounts between buckets continuously.
    • Printer: Prints the current array values every 3 seconds.

Equalizer Thread:

  • Randomly selects two buckets, srcIndex and dstIndex.
  • Calculates the amount to transfer as half the difference between their values.
  • Transfers the amount atomically using the Buckets.transfer method.

Transferrer Thread:

  • Randomly selects two buckets and a random amount to transfer.
  • Transfers the amount atomically using the Buckets.transfer method.

Printer Thread:

  • Sleeps for 3 seconds.
  • Prints the total value and the array values.

Synchronization:

  • The Buckets.data array is synchronized to ensure that only one thread can modify it at a time.
  • The Buckets.getBucket, Buckets.transfer, and Buckets.getBuckets methods are synchronized to prevent data races.

Key Features:

  • Concurrency: Uses multiple threads to modify the array concurrently.
  • Atomic Operations: Performs updates using synchronized methods to ensure that changes are made atomically.
  • Data Integrity: Maintains the sum of array values throughout the concurrent updates.

Source code in the java programming language

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class AtomicUpdates {

    private static final int NUM_BUCKETS = 10;

    public static class Buckets {
        private final int[] data;

        public Buckets(int[] data) {
            this.data = data.clone();
        }

        public int getBucket(int index) {
            synchronized (data) {
                return data[index];
            }
        }

        public int transfer(int srcIndex, int dstIndex, int amount) {
            if (amount < 0)
                throw new IllegalArgumentException("negative amount: " + amount);
            if (amount == 0)
                return 0;

            synchronized (data) {
                if (data[srcIndex] - amount < 0)
                    amount = data[srcIndex];
                if (data[dstIndex] + amount < 0)
                    amount = Integer.MAX_VALUE - data[dstIndex];
                if (amount < 0)
                    throw new IllegalStateException();
                data[srcIndex] -= amount;
                data[dstIndex] += amount;
                return amount;
            }
        }

        public int[] getBuckets() {
            synchronized (data) {
                return data.clone();
            }
        }
    }

    private static long getTotal(int[] values) {
        long total = 0;
        for (int value : values) {
            total += value;
        }
        return total;
    }

    public static void main(String[] args) {
        ThreadLocalRandom rnd = ThreadLocalRandom.current();

        int[] values = new int[NUM_BUCKETS];
        for (int i = 0; i < values.length; i++)
            values[i] = rnd.nextInt() & Integer.MAX_VALUE;
        System.out.println("Initial Array: " + getTotal(values) + " " + Arrays.toString(values));

        Buckets buckets = new Buckets(values);
        new Thread(() -> equalize(buckets), "equalizer").start();
        new Thread(() -> transferRandomAmount(buckets), "transferrer").start();
        new Thread(() -> print(buckets), "printer").start();
    }

    private static void transferRandomAmount(Buckets buckets) {
        ThreadLocalRandom rnd = ThreadLocalRandom.current();
        while (true) {
            int srcIndex = rnd.nextInt(NUM_BUCKETS);
            int dstIndex = rnd.nextInt(NUM_BUCKETS);
            int amount = rnd.nextInt() & Integer.MAX_VALUE;
            buckets.transfer(srcIndex, dstIndex, amount);
        }
    }

    private static void equalize(Buckets buckets) {
        ThreadLocalRandom rnd = ThreadLocalRandom.current();
        while (true) {
            int srcIndex = rnd.nextInt(NUM_BUCKETS);
            int dstIndex = rnd.nextInt(NUM_BUCKETS);
            int amount = (buckets.getBucket(srcIndex) - buckets.getBucket(dstIndex)) / 2;
            if (amount >= 0)
                buckets.transfer(srcIndex, dstIndex, amount);
        }
    }

    private static void print(Buckets buckets) {
        while (true) {
            long nextPrintTime = System.currentTimeMillis() + 3000;
            long now;
            while ((now = System.currentTimeMillis()) < nextPrintTime) {
                try {
                    Thread.sleep(nextPrintTime - now);
                } catch (InterruptedException e) {
                    return;
                }
            }

            int[] bucketValues = buckets.getBuckets();
            System.out.println("Current values: " + getTotal(bucketValues) + " " + Arrays.toString(bucketValues));
        }
    }
}

You may also check:How to resolve the algorithm List comprehensions step by step in the Clojure programming language
You may also check:How to resolve the algorithm Thue-Morse step by step in the SQL programming language
You may also check:How to resolve the algorithm Brownian tree step by step in the zkl programming language
You may also check:How to resolve the algorithm GUI/Maximum window dimensions step by step in the Delphi programming language
You may also check:How to resolve the algorithm Caesar cipher step by step in the Julia programming language