The critical section problem

• ENG
• FRA
• DEU
• ITA
• ESP

1. Home
2. Creations
3. Forum
4. Contributions
5. Documentation

HOME

Home

CREATIONS

Creations

Thymio Discovery kits

FORUM

Forum

CONTRIBUTIONS

R2T2

Thool

Contributor centre

DOCUMENTATION

Aseba Studio

This page describes an exploration of the critical section problem using Thymios.

Specification of the critical section problem

In the previous page, we saw examples of two Thymios running at the same time. In the first example, the Thymios changed colours independently and did not interfere with each other. In the second example, the two Thymios wanted to cross the same intersection; in the absence of synchronization, they crashed.

The problem of two Thymios wanting to access the same intersection can be generalized into the critical section problem. In this problem, two or more processes are doing their own processing, but occasionally they need to run instructions called the critical section. The program must satisfy the following specification:

• Mutual exclusion: no more than one process can be in its critical section at any one time. In the example: no two Thymios enter the intersection at the same time.
• Freedom from deadlock: at least one process can always enter the critical section. In the example: it doesn't happen that all Thymios are not able to enter the intersection.
• Freedom from starvation: if one specific process wants to enter the critical section, eventually it does. In the example, if one Thymio wants to enter the intersection, eventually it does.

The project presented on the rest of this page describes how several Thymios try to share a single parking place (the critical section). It demonstrates what happens if no synchronization is done and two solutions that achieve synchronization.

Implementation with the Thymios

Several Thymios are travelling on a road forming a loop. Occasionally, they need to go shopping and look for a parking place. Initially, the robot should be placed on the road outside the parking place. The behaviour of the Thymios must respect the specification of the critical section problem:

• Only one Thymio can access a parking place at any one time (mutual exclusion).
• A Thymio which is looking for a parking place will eventually find one (freedom from deadlock and starvation).

The program in the Thymios will implement a state machine. At any time, the program is in one of several states and the program decides to make a transition from one state to another depending on what it senses. The initial state is the road state.

Part 1: No synchronization

We are first going to let the Thymios try to park with synchronization.

Here is the state machine implemented by the program in a Thymio:

Road: In this state, the robot is moving along the road.
Line following and collision avoidance are performed.
Action: This state corresponds to the decision making when the robot approaches the turn to the parking place.
The variable looking is checked and depending on the result, either line following or line crossing are performed.
Parking: This state corresponds to the moment when the Thymio is in the parking place.
The robot remains parked for a random period of time.

The following diagram shows the road, the turn to the parking place and the parking place:

The behaviour of the Thymios with the program is shown in the following video:

What happened?

The solution is not correct because the two Thymios enter the parking place at the same time so mutual exclusion is not achieved. Any Thymio can decide to enter the parking intersection without checking if a robot is already there. We need a synchronization mechanism which can sense that a Thymio is in the parking place and prevent other ones from trying to enter. The following sections demonstrate two synchronization mechanisms.

To go further:

Try to think about situations in real life when we encounter the critical section problem. How is it solved?

Show solution

The following examples are different situation that can be associated with the critical section problem. But you can think about many more.

• Buying meat at the butchers: you can take a ticket at the counter and wait for your number to be called.
• When you want to go to the toilet in a restaurant: if the toilet is already occupied, you go back to your table and have to try again later.
• When you want to see the doctor: you make an appointment in advance.
• A lottery ticket: only one random person is going to win the prize.

Not all these examples can be applied to programming. However, some synchronisation mechanisms are inspired by some of those real life solutions.

Part 2: Synchronization with a spinlock

A spinlock is a synchronization mechanism which regulates who can access the critical section. When a process wants to enter the critical section, it first requests the lock. It the request is denied, the process loops, continuously requesting the lock until permission is granted. This behaviour is called busy waiting because the process is still executing without doing anything useful.

We use an additional Thymio to implement the spinlock. When it grants a Thymio permission to access the parking place (indicated by a red light), any other Thymios that request the lock will "waste their time" in a separate loop. When the Thymio leaves the parking place, it will release the lock (indicated by a green light) and one of the Thymios in the waiting loop will be able to enter the parking place.

Here is the state diagram for the Thymio spinlock:

Free: This state corresponds to the actions when the parking place is free.
The spinlock transmits FREE.
Occupied: This state corresponds to the actions when the parking place is occupied.
The spinlock transmits OCCUPIED.

The state diagram for the moving Thymio also changes because it needs to request permission to enter the parking place:

Road: In this state, the robot is moving along the road.
Line following and collision avoidance are performed. The Thymio transmits My ID + out of the parking.
Action: This state corresponds to the decision making when the robot approaches the turn to the parking place.
The Thymio performs either line following or line crossing. The Thymio transmits My ID + out of the parking.
Parking: This state corresponds to the moment when the Thymio is in the parking place.
The robot remains parked for a random period of time and transmits My ID + in the parking.
Enter: In this state a Thymio must decide if it can enter the parking place.
The Thymio performs either line following or line crossing. It transmits My ID + out of the parking.
Busywait: The robot moves indefinitely in the loop.
Line following is performed. The Thymio transmits My ID + out of the parking.

The following diagram extends the previous one to show the waiting loop:

The behaviour of the Thymios with the program is shown in the following video:

What happened?

This solution achieves mutual exclusion; no two Thymios will enter the parking place at the same time.

To go further:

The spinlock is a correct solution, but is it energy efficient?

Show solution

A problem with the spinlock is that the waiting robots are engaged in busy waiting: they are travelling in a circle, wasting energy. It would be better if they could wait somewhere without doing anything until the parking place is freed.

Consider, now, the behaviour demonstrated in the following video. Keep track of which Thymio enters the loop first.

What happened? What is the problem with this kind of behaviour?

Show solution

The blue robot overtakes the orange robot. Although the blue robot arrived after the orange robot it enters the parking place first. The driver of the orange robot is likely to be very upset, so we should look for a better solution!

The problem is that there is no queue such as you have in a bank or a bakery. A queue ensures first-come, first-served. Here the Thymios travel in the waiting loop and the one which just happens to be closest to the intersection when the parking place is freed is the one which enters first.

The next solution solves both these problems.

Part 3: Synchronization with a binary semaphore

A binary semaphore is a synchronization mechanism with a queue; this solves the problem of overtaking and enables the solution to achieve freedom from starvation. A binary semaphore blocks the processes in its queue; this solves the problem of busy waiting.

To implement this semaphore, we replace the Thymio spinlock by a Thymio semaphore. The semaphore has a table named tab_queue in which it stores the identities of the Thymios in the queue, and a variable id_in for the identity of the Thymio currently in the parking place. The semaphore can add Thymios to the queue both when the parking place is free or when it is occupied.

Free: This state corresponds to the actions when the parking place is free.
The semaphore transmits ID of first Thymio in line + FREE and manage tab_queue.
Occupied: This state corresponds to the actions when the parking place is occupied.
The semaphore transmits ID of the first Thymio in line + OCCUPIED and manage tab_queue.

Here is the state diagram for the Thymio modified for the semaphore:

Road: In this state, the robot is moving along the road.
Line following and collision avoidance are performed. The Thymio transmits My ID + out of the parking.
Action: This state corresponds to the decision making when the robot approaches the turn to the parking place.
Either line following or line crossing is performed. The Thymio transmits My ID + out of the parking.
Parking: This state corresponds to the moment when the Thymio is in the parking place.
The robot remains parked for a random period of time and transmits My ID + in the parking.
Queue: This state corresponds to the wait in the queue.
The robot waits until it is in front of the queue. It transmits Thymio ID + in the queue.

The following diagram extends the previous one to show the queue:

The behaviour of the Thymios with the program is shown in the following video:

What happened?

This program is a correct solution to the critical section problem. The Thymios are waiting first-come, first-served in the queue for the parking place, and while they wait their motors are off.

To go further:

What happens if we add more Thymios?

Show solution

If we add too many Thymios, the queue is going to be full. It might even block the Thymios running normally on the road. In our example, the size of the queue is determined by the physical path of the road, and we would have trouble extending it after a certain point.

In computer programming, however, this is rarely a problem as the queue is big enough so that we don't need to worry about it and as it can be extended .

What happens if a Thymio forgets to signal that it is leaving the parking place?

Show solution

If a Thymio forgets to signal the semaphore that it is leaving the parking place, the semaphore still thinks that there is a Thymio in the parking place and will not enable any other Thymio to enter it, even though it the parking spot is free. This will block the whole program as after a while, all the processes will be blocked, waiting to enter the critical section.
This problem is the one that makes the semaphore complicated to implement as, in more complex programs, we might use several semaphores. We need to make sure that every process signals the semaphore every time it is entering and leaving the parking.

How could we implement a solution for two parking spots?

Show solution

The semaphore we have implemented here is called a binary semaphore, because the semaphore takes only two values 0 and 1 (occupied and free). With a binary semaphore, only one process can access the critical section at any time. A general semaphore can take on any positive value (free, one process in the critical section, two processes in the critical section…).
A general semaphore could be used to implement a parking lot containing more than one parking place.

Conclusion

We have shown how to solve the critical section problem, which is the most fundamental problem in concurrent programming. Two synchronization methods were used: the spinlock, which suffers from busy waiting and overtaking, and the binary semaphore, which uses a queue to avoid busy waiting and overtaking.

We invite you to study this fascinating subject and learn about other synchronization mechanisms.

Do it yourself

• To construct the tracks for the Thymios to follow, print out the PDF files of the track segments that are contained in this archive.

• The source code of the programs is available in this archive.