Geek Culture
Published in

Geek Culture

Resources Race Competition

a little bit of theory

Monza 2005 — Micheal Schumacher win the Italian GP (Picture from the web)

Introduction

During the last year, I was in charge of designing and realizing an event-driven system. One of the topics I discussed the most is the concurrency access to shared resources. I needed several times to argue how to guarantee safe access to shared data in a distributed multithread environment.

Those discussions inspired me to write this story and the following. I would like to get back to basic and explore concurrent access implications together.

A common example

To have a common background, let me introduce you to an example.

Let’s assume the following code run in a multithreading environment on a single-core machine. These simplifications do not eliminate the problem but allow us to face it.

Look at the C code behind:

void add(char[] *input)
{
scanf("%s",input);
printf("%s",input);
}

This function has a pointer as input and returns nothing. It reads from the keyword then echos them. For those who are unfamiliar with the C language, have a tour here.

I point out that the pointer is a shared resource. In fact, in a multithreaded environment, all threads share the same memory location.

The following is a probable scenario:

example run

This run prints “ciao” twice while “hello” never. The scenario exists because we cannot make any assumption about:

  • order of step execution;
  • relatively speed of each thread.

If you would like to avoid such a situation, we need to work on an algorithm that allows us to access the shared variable securely.

Protecting resources

According to OS Theory, we have to be in a hurry of three aspects:

  • Mutual Exclusion;
  • Deadlock;
  • Starvation.

when accessing shared resources.

We define mutual exclusion as the need for a thread to access exclusively a shared resource. We refer to the portion of code that accesses the shared resource as the critical section. When we design an algorithm, we must guarantee no more than a thread runs the critical section at the same time.

Your synchronization schema must avoid deadlock and starvation problems.

Deadlock is a sort of Mexican stall for threads: I will try to explain using another example.

Mexican Stall from Sergio Leone‘s The Good, The Bad and The Ugly (picture from the web)

Let’s consider two threads T¹ and T² which both need to use R¹ and R². What can happen is:

  • R¹ locks T¹;
  • R² locks T²;
  • T¹ needs R² to complete;
  • T² needs R¹ to complete.

Both threads are blocked in a stall and cannot continue, just like in a western movie.

Starvation happens when a process waits to access one resource for an infinite unit of time. This problem arises because thread executions time and the scheduler behavior are unknown a priori.

One of the first solutions was enunciated by Dijkstra in [1]. Today it is considered passed, but it is the ground on which subsequent were built.

In the following chapter, I’ll present some basic primitives implemented by OS and programming languages that allow you to create your synchronization schemas.

Semaphore

Semaphore is the simples primitive which allows two or more processes to cooperate.

You can think of a semaphore as a shared numeric variable that you can access only using an atomic method. When I use atomic, I say that the scheduler cannot interrupt process execution.

A Semaphore exposes a constructor and two methods:

  • wait: that subtracts 1 to the variable;
  • signal: that sums 1 to the variable

After a waiting call, if the semaphore is negative, the caller process blocks and it cannot continue its execution.

Semaphores do not solve synchronization problems on their own. You need to create an algorithm that uses them.

The simplest one realizes a critical section using a binary semaphore:

s = semaphore(mysem);
wait(s);
#let's start critical section
[...]
signal(s);

Let’s assume the semaphore is initialized elsewhere in a shared code part.

The first incoming thread calls the wait value and it gets back the control because 0 is an admitted positive value and could start the critical section.

While it is working, another thread comes and calls the wait primitive. It cannot goes on because the semaphore became -1. When the first thread calls the signal method, the second one is allowed to continue.

One of the most common problems solved with the use of semaphores is the reader-writer problem. You have a shared memory and two types of processes: writers and readers.

Reader threads do not modify shared resource states than you could assume that there could be more than one executing the critical section. In the meanwhile, more than a writer is not allowed to run in the critical path. We cannot allow the interleaving of a reader and a writer as well.

I do not want to deal with this problem here, you can find the solution in the literature, have a look at the Bibliography section.

Semaphore, as they are defined, has some limitations. The most important one is the fact that semaphores do not solve the mutual exclusion. This involves that it is easy to make mistakes: deadlock and starvation are still possible. In fact, in the classical definition, the time a thread is waiting for a signal is not bounded.

Monitor

Monitors are more complex objects than semaphores. In an Object-Oriented fashion design, you can think of a monitor as an Object which encapsulates the shared needed data. You can access shared data only using Monitor exposed methods that manage mutual exclusion.

For construction, the Monitor guarantee only one process is running into the critical section. We can consider the monitor a more error-prone solution than semaphore because you cannot forget any signal to close the critical section.

To guarantee a sort of synchronization in the execution of methods, Monitors allow what are called condition variables. A condition variable allows a monitor procedure to interrupt the execution if tested false. To provide such behavior, these variables admit two methods:

  • wait(): the thread whose calling this method is blocked and enqueued till the condition is true;
  • signal(): wake up the first enqueued thread.

These operations are straight different from the semaphore’s ones. If no thread is enqueued and the signal() runs a no operation scenario.

Monitor represents an easier primitive than semaphore. It does not solve the mutual exclusion problem as well as you have to use the conditions properly. Furthermore, readers cannot access the same buffer together using a monitor.

Messaging

Another way to let processes coordinating is messaging.

This method allows process synchronization and sharing of data. To exchange messages, we define a couple of primitives:

  • send(destination, message)
  • receive(source, message)

The first, allows the process to send a message to a process/destination, the second to receive a message.

The implementation type you give to those primitives, the way the processes synchronize and solve the mutual exclusion problem change. Both the operations could be blocking or not blocking.

In a blocking scenario:

  • send: the thread waits for its counterpart to receive the message;
  • receive: if a message is produced, the thread receives it. If a message is still not produced, the thread stops.

Rather, in a non-blocking scenario:

  • send: the thread sends the message and goes on
  • receive: the thread receives a message only if it is still produced.

Exchanging messages do not solve the synchronization problem. It is a valid tool you can use to build your algorithm. This primitive is very important because it is the acceptable solution for a distributed system.

Conclusions

This story would be the first of a series that will talk about process synchronization. In this one, I talked about the theory behind my everyday job.

The stories will talk about the way programming languages allow you to realize those primitives, I promise.

If you are interested, stay tuned!

Bibliography

  • [1] E.W. DijkstraSolution of a Problem in Concurrent Programming Control — Communication of the ACM
  • [2] J. Bacon, T. Harris Operating Systems: Concurrent and Distributed Software Design — Addison Wesley
  • [3] W. Stalling Operating Systems Internals and Design Principles Third Edition — Jackson (Italian version)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store