The Problem of De-Synchronized Metronomes

While studying operating systems, I found an important resource called The Little Book of Semaphores that illustrates several examples of concurrent programming exercises, particularly on semaphores.

For those of you who are a bit unfamiliar or have never seen concurrent programming in your career, let’s take a step back. Every process that we run that runs for the operating system competes with all other running processes to take control of the most valuable resource: the CPU. The scheduling algorithm decides how long the process can occupy the CPU and in case of changing processes, choose the next one that will be entitled to the CPU.

With time-sharing and multi-scheduling algorithms (e.g. Round Robin), processes advance concurrently, with the illusion that they are running in parallel. What actually happens internally is the very fast rotation of processes within the CPU so that each of the processes does a little of the useful work. As long as the processes were independent (i.e., they did not influence and were not influenced by any other process), the problem of data sharing never arose. However, when multiple processes concurrently with each other want to share a resource, how they are scheduled can affect the end result.

If two processes want to synchronize, it is necessary to adopt techniques that go beyond the simple shared “variable” since multiple processes, accessing data differently (both reading and writing), can lead to data inconsistency. These techniques are based on the use of semaphores, positive integer variables that can only be manipulated by P() (decreases the value of the semaphore) and V() (increases the value of the semaphore). Inspired by The Little Book of Semaphores, I tried to invent a synchronization problem.

The Problem

Problem: Imagine we have N metronomes, each having a different oscillation frequency. When placed close together, metronomes of different frequencies tend to balance each other, i.e. they tend to have all their oscillation frequencies equal, “in phase”. Using semaphores, try to implement the metronome process, knowing that there is a shared variable called average containing the average of all values of the frequencies of N metronomes. Each time you change the frequency, you need to recalculate the average. At the beginning, all metronomes have a different random (valid) frequency. The final goal is to synchronize the different metronomes with each other, i.e. that all oscillation frequencies are equal.

Have fun :)

If you have a solution and want to know if it’s valid, send it to me at blog@nicolo.dev.

Translations