How to resolve the algorithm Checkpoint synchronization step by step in the Scala programming language
How to resolve the algorithm Checkpoint synchronization step by step in the Scala programming language
Table of Contents
Problem Statement
The checkpoint synchronization is a problem of synchronizing multiple tasks. Consider a workshop where several workers (tasks) assembly details of some mechanism. When each of them completes his work they put the details together. There is no store, so a worker who finished its part first must wait for others before starting another one. Putting details together is the checkpoint at which tasks synchronize themselves before going their paths apart. The task Implement checkpoint synchronization in your language. Make sure that the solution is race condition-free. Note that a straightforward solution based on events is exposed to race condition. Let two tasks A and B need to be synchronized at a checkpoint. Each signals its event (EA and EB correspondingly), then waits for the AND-combination of the events (EA&EB) and resets its event. Consider the following scenario: A signals EA first and gets blocked waiting for EA&EB. Then B signals EB and loses the processor. Then A is released (both events are signaled) and resets EA. Now if B returns and enters waiting for EA&EB, it gets lost. When a worker is ready it shall not continue before others finish. A typical implementation bug is when a worker is counted twice within one working cycle causing its premature completion. This happens when the quickest worker serves its cycle two times while the laziest one is lagging behind. If you can, implement workers joining and leaving.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Checkpoint synchronization step by step in the Scala programming language
Source code in the scala programming language
import java.util.{Random, Scanner}
object CheckpointSync extends App {
val in = new Scanner(System.in)
/*
* Informs that workers started working on the task and
* starts running threads. Prior to proceeding with next
* task syncs using static Worker.checkpoint() method.
*/
private def runTasks(nTasks: Int): Unit = {
for (i <- 0 until nTasks) {
println("Starting task number " + (i + 1) + ".")
runThreads()
Worker.checkpoint()
}
}
/*
* Creates a thread for each worker and runs it.
*/
private def runThreads(): Unit =
for (i <- 0 until Worker.nWorkers) new Thread(new Worker(i + 1)).start()
class Worker(/* inner class instance variables */ var threadID: Int)
extends Runnable {
override def run(): Unit = {
work()
}
/*
* Notifies that thread started running for 100 to 1000 msec.
* Once finished increments static counter 'nFinished'
* that counts number of workers finished their work.
*/
private def work(): Unit = {
try {
val workTime = Worker.rgen.nextInt(900) + 100
println("Worker " + threadID + " will work for " + workTime + " msec.")
Thread.sleep(workTime) //work for 'workTime'
Worker.nFinished += 1 //increases work finished counter
println("Worker " + threadID + " is ready")
} catch {
case e: InterruptedException =>
System.err.println("Error: thread execution interrupted")
e.printStackTrace()
}
}
}
/*
* Worker inner static class.
*/
object Worker {
private val rgen = new Random
var nWorkers = 0
private var nFinished = 0
/*
* Used to synchronize Worker threads using 'nFinished' static integer.
* Waits (with step of 10 msec) until 'nFinished' equals to 'nWorkers'.
* Once they are equal resets 'nFinished' counter.
*/
def checkpoint(): Unit = {
while (nFinished != nWorkers)
try Thread.sleep(10)
catch {
case e: InterruptedException =>
System.err.println("Error: thread execution interrupted")
e.printStackTrace()
}
nFinished = 0
}
}
print("Enter number of workers to use: ")
Worker.nWorkers = in.nextInt
print("Enter number of tasks to complete:")
runTasks(in.nextInt)
}
You may also check:How to resolve the algorithm Date format step by step in the LiveCode programming language
You may also check:How to resolve the algorithm GUI/Maximum window dimensions step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Mutual recursion step by step in the Idris programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the TXR programming language
You may also check:How to resolve the algorithm Babbage problem step by step in the Tiny Craft Basic programming language