SE205: Lab on Concurrent Systems Programming in POSIX

Laurent Pautet (pautet@telecom-paristech.fr)

Index


1 Lab on Concurrent Systems Programming in POSIX

Objectives

The objective of this lab is to implement in C a blocking queue service of fixed size like the Java ArrayBlockingQueue service. Thus, you will be able to experiment in detail some POSIX concurrency tools.

This lab does not cover all of the tools POSIX provides for dealing with concurrency. It illustrates the operation of some of them. Course material on tasks can be found here. You can see the complete documentation of POSIX functions related to threads by following this link.

Sources

You will find all the sources in this compressed archive. The practical work on patterns for concurrent systems is based on the first 4 questions, i.e. the implementations of a blocking queue of fixed size with conditional variables used to enforce blocking, non-blocking and timed semantics.

How to submit your work To send your work to your teacher, you will build an archive compressing a directory with your name (<Firstname.Lastname>) and containing only the files .c and .h.

How To Debug

To find your errors, we strongly recommend that you use gdb. It is critical to debug your C programs using gdb and not filling your program with printf. If you have a memory problem (SIGSEGV, ...), do:

gdb ./main_protected_buffer
(gdb) run test-00.txt

In case of a problem, the program will stop on the incorrect memory access. To understand the issue, use gdb commands:

MacOS

For MacOS users, it will be necessary to make your gdb operational and MacOS does not facilitate the task. You will find the procedure by following this link . If this link is not sufficient, there are many guides to solve this problem.


1.1 Process creation and termination in order of creation

We consider the main_protected_buffer.c file . This program creates producers and consumers which exchange data using a shared buffer. We focus first on the creation of producers and consumers.

Producers run main_producer procedure and output data (integers) in a protected_buffer circular buffer that we will protect against concurrent access. Consumers execute the main procedure main_consumer and consume the produced data in the same way.

The accesses of producers and consumers can be made according to several semantics. They can be blocking, non-blocking, or timed, that is to say that if they block, they will not block more than a given amount of time.

Producers and consumers adopt a periodic behavior. All periods from a common start time start_time, they produce or consume data then wait for the next period to start over. For example, the producers reactivate every start_time + n * producer_period where n represents the number of activations.

Input data

The scenarios are provided in the test-<XY>.txt files and are described as follows.

The number of producers (n_producers), that of consumers (n_consumers), the size of the buffer circular (buffer_size), the semantics of access for consumers (sem_consumers) and for producers (sem_producers) (0 for blocking, 1 for non- blocking, 2 for timed) or the periods of producers (producer_period) and consumers (consumer_period) are configured using a file which name is passed on the command line. Note that the consumers can be blocking while the producers are non-blocking. The value 0 of the sem_impl parameter indicates that we are using the implementation with variables conditional and the value 1 that we use the implementation with semaphores.

#sem_impl
0
#sem_consumers
0
#sem_producers
0
#buffer_size
1
#n_values
10
#n_consumers
2
#n_producers
5
#consumer_period
5000
#producer_period
5000

Output data

The output lines consist of several fields. The first one indicates the value of the clock in second. The second one the name of the task and the following one the number of the task. The last two fields indicate the operation and the input or output data. In the example below, on the date 000, the producer attached to thread 2 performs the put operation of data 200 in blocking mode (B). The value 200 corresponds to producer 2 (hundreds value) and to (first) production 0 of this server (value of units).

000 [producer 02] put (B) - data=200

It should also be noted that when we have P producers and C consumers, the producers will produce C times, and consumers will consume P times. Thus, under normal circumstances, all data produced is consumed.

Complete the main_protected_buffer.c file to create as many producers and consumers than requested and then wait for the termination of producers and consumers. Save the identifiers of consumers and producers in the tasks table.

You can test your code by doing:

> ./main_protected_buffer test-00.txt

If you are using the test-00.txt file listed above, you will need to verify that you are creating the correct number of consumers and producers. By consulting the 3rd field of outputs below, we can actually note that there are 2 consumers and 5 producers as specified in test-00.txt. The other information is not relevant at this stage.

...
start consumer 0
start consumer 1
start producer 2
start producer 3
start producer 4
start producer 5
start producer 6
...

1.2 Buffer protected against concurrent access (var cond / blocking)

We will implement a circular buffer protected against concurrent access in the file cond_protected_buffer.c. To do this, we can use the implantation of a non-protected circular buffer provided in the files circular_buffer.c and circular_buffer.h. Check available functions in file circular_buffer.h.

Complete the protected_buffer_t structure. It only contains an non-protected circular buffer currently. You will have to add POSIX synchronization tools.

Complete the cond_protected_buffer_init, cond_protected_buffer_get and cond_protected_buffer_put so that it offers the following services:

  • cond_protected_buffer_init : initializes the circular buffer protected against concurrent access and provides a number of slots passed as parameter.
  • cond_protected_buffer_get : remove an element from the protected circular buffer according to a FIFO policy. The operation must be protected against concurrent access. If the buffer is empty, the call will be blocking until a slot is filled. The operation will also unblock blocked producers if the buffer was previously full. We will be careful to limit unnecessary releases.
  • cond_protected_buffer_put : add an element to the protected circular buffer according to a FIFO policy. The operation must be protected against concurrent access. If the buffer is full, the call will be blocking until a slot becomes free. The operation will unblock consumers blocked if the buffer was previously empty. We will be careful to limit unnecessary releases.

Test the correct functioning of the protected circular buffer using the main program of the file main_protected_buffer.c. You can use the test case test-00.txt. We will note the instants when consumers and producers are supposed to block. Normally, with this semantics, all data produced must be consumed. Typically, in the test-00.txt example, we expects to have an output like:

...
000 [producer 02] put (B) - data=200
000 [consumer 00] get (B) - data=200
000 [producer 03] put (B) - data=300
000 [consumer 01] get (B) - data=300
000 [producer 04] put (B) - data=400
005 [consumer 00] get (B) - data=400
005 [producer 05] put (B) - data=500
005 [consumer 01] get (B) - data=500
...

in which each data is consumed, and consumed only once.


1.3 Buffer protected against concurrent access (var cond / non-blocking)

We will implement in the cond_protected_buffer.c file concurrent accesses to the circular buffer protected similar to the previous ones. However, the semantics of these accesses will this time be non-blocking. The producer will return with a boolean return code if it succeeded in immediately adding an element in the buffer. The consumer will indicate by a null pointer or not on a data if it has succeeded in immediately removing an item from the buffer. However, the buffer should still be protected against concurrent access.

Complete the cond_protected_buffer_remove and cond_protected_buffer_add procedures so that they offer the services indicated.

Test the correct functioning of the protected circular buffer using the main program of the file main_protected_buffer.c.

You can use the scenarios, test-01.txt and test-02.txt. We will verify that consumers and producers do not get blocked and execute as expected. The test-01.txt scenario has more than producers than consumers, the size 1 buffer will soon be full and some producers will fail to deposit their data.

Below, on date 000, consumer 00 is trying to consume while the buffer is empty (data = NULL). Then, the 5 producers produce data but the size of the buffer being 1, only the data produced by the first producer 01 will be stored in the buffer. This is confirmed on the date 005, when the consumer consumes and removes the data 100 stored first and not the data 500 last stored. Moreover, at date 010 , data 101 is consumed again and not data 200 or 501. The failure of the producer is indicated by a produced NULL data. Note the indication (U) to signify non-blocking semantics.

...
000 [consumer 00] remove (U) - data=NULL
000 [producer 01] add (U) - data=100
000 [producer 02] add (U) - data=NULL
000 [producer 03] add (U) - data=NULL
000 [producer 04] add (U) - data=NULL
000 [producer 05] add (U) - data=NULL
005 [consumer 00] remove (U) - data=100
005 [producer 01] add (U) - data=101
005 [producer 02] add (U) - data=NULL
005 [producer 03] add (U) - data=NULL
005 [producer 04] add (U) - data=NULL
005 [producer 05] add (U) - data=NULL
010 [consumer 00] remove (U) - data=101
...

In the test-02.txt scenario, on the contrary, it is the consumers who will fail to extract data.

...
000 [consumer 00] remove (U) - data=NULL
000 [consumer 01] remove (U) - data=NULL
000 [consumer 02] remove (U) - data=NULL
000 [consumer 03] remove (U) - data=NULL
000 [consumer 04] remove (U) - data=NULL
000 [producer 05] add (U) - data=500
005 [consumer 00] remove (U) - data=500
005 [consumer 01] remove (U) - data=NULL
005 [consumer 02] remove (U) - data=NULL
005 [consumer 03] remove (U) - data=NULL
...

1.4 Buffer protected against concurrent access (var cond / timed)

We will implement in the cond_protected_buffer.c file concurrent accesses to the circular buffer protected similar to the previous ones. However, the semantics of these accesses will this time be timed. If the operation cannot be performed immediately, it waits until it can, but will not wait beyond a given deadline (which corresponds to a date ie an absolute time). note that if a consumer or a producer is unblocked, and its operation is not successful despite this notification, it must resume its wait operation until it succeeds or the deadline occurs. In this case, it returns a special value as before (NULL).

Complete the cond_protected_buffer_poll and cond_protected_buffer_offer procedures so that it offers the indicated services. We will use the POSIX tools in their timed version.

Test the correct functioning of the protected circular buffer using the main program of the file main_protected_buffer.c. You can use the test cases, test-03.txt and test-04.txt. You will check that consumers and producers remain blocked for as long as possible and activate themselves as expected.

For example, in the test-04.txt scenario, the producer 05 puts a data consumed data immediately by the first consumer. Then the next 4 consumers fail to consume a data and are released on the following period ie on date 05.

...
000 [producer 05] offer (T) - data=500
000 [consumer 00] poll (T) - data=500
005 [consumer 04] poll (T) - data=NULL
005 [consumer 02] poll (T) - data=NULL
005 [consumer 01] poll (T) - data=NULL
005 [consumer 03] poll (T) - data=NULL
005 [producer 05] offer (T) - data=501
005 [consumer 00] poll (T) - data=501
010 [consumer 02] poll (T) - data=NULL
010 [consumer 01] poll (T) - data=NULL
010 [consumer 04] poll (T) - data=NULL
010 [consumer 03] poll (T) - data=NULL
010 [producer 05] offer (T) - data=502
...

Same scenario for producers in test-03.txt,

...
000 [producer 01] offer (T) - data=100
000 [consumer 00] poll (T) - data=100
000 [producer 02] offer (T) - data=200
005 [producer 04] offer (T) - data=NULL
005 [producer 03] offer (T) - data=NULL
005 [producer 05] offer (T) - data=NULL
005 [consumer 00] poll (T) - data=200
005 [producer 01] offer (T) - data=101
010 [producer 03] offer (T) - data=NULL
010 [producer 05] offer (T) - data=NULL
010 [producer 02] offer (T) - data=NULL
010 [producer 04] offer (T) - data=NULL
010 [consumer 00] poll (T) - data=101
...

At last, test that your implementation is correct when the consumers are timed blocking and the producers are non-blocking (test-05.txt) ...

000 [producer 01] add (U) - data=100
000 [consumer 00] poll (T) - data=100
000 [producer 02] add (U) - data=200
000 [producer 03] add (U) - data=NULL
000 [producer 04] add (U) - data=NULL
000 [producer 05] add (U) - data=NULL
005 [consumer 00] poll (T) - data=200
005 [producer 01] add (U) - data=101
005 [producer 02] add (U) - data=NULL
005 [producer 03] add (U) - data=NULL
005 [producer 04] add (U) - data=NULL
005 [producer 05] add (U) - data=NULL
010 [consumer 00] poll (T) - data=101
020 [consumer 00] poll (T) - data=NULL
...
050 [consumer 00] poll (T) - data=NULL
...

... and when the consumers are non-blocking and the producers are timed blocking (test-06.txt).

...
000 [consumer 00] remove (U) - data=NULL
000 [consumer 01] remove (U) - data=NULL
000 [consumer 02] remove (U) - data=NULL
000 [consumer 03] remove (U) - data=NULL
000 [consumer 04] remove (U) - data=NULL
000 [producer 05] offer (T) - data=500
005 [consumer 00] remove (U) - data=500
005 [consumer 01] remove (U) - data=NULL
005 [consumer 02] remove (U) - data=NULL
005 [consumer 03] remove (U) - data=NULL
005 [consumer 04] remove (U) - data=NULL
005 [producer 05] offer (T) - data=501
015 [producer 05] offer (T) - data=NULL
...
050 [producer 05] offer (T) - data=NULL
...

1.5 Waiting until a given date

In the code for producer main_producer and consumer main_consumer, you use the delay_until function to suspend the thread until the next deadline (deadline).

Analyze the delay_until procedure from file utils.c. Explain how this procedure can make the task wait well beyond the deadline if the execution of gettimeofday is not immediately followed by the execution of nanosleep.

By using the POSIX functions, especially those from the previous question, you will provide an alternative implementation of delay_until which will not present the drawback noted in the previous paragraph.

You will verify that the previous scenarios work normally.


1.6 Buffer protected against concurrent access (semaphore / blocking)

We implement again the semantics of previous concurrent accesses, but this time we are going to use semaphores. Instead of using conditional variables to block execution, you will be using semaphores. You will notice that, unlike the version with the conditional variables, you will necessarily use two queues. You will modify the files sem_protected_buffer.h and sem_protected_buffer.c.

The requested work and the expected result are the same as in the section Buffer protected against concurrent access (var cond / blocking). However, you must use the scenario file test-10.txt in order to test your work.


1.7 Buffer protected against concurrent access (semaphore / non-blocking)

We implement again the semantics of previous concurrent accesses, but this time we are going to use semaphores. Instead of using conditional variables to block execution, you will be using semaphores. You will modify the files sem_protected_buffer.h and sem_protected_buffer.c.

The requested work and the expected result are the same as in the section Buffer protected against concurrent access (var cond / non-blocking). However, you must use the scenario files test-11.txt and test-12.txt in order to test your work.


1.8 Buffer protected against concurrent access (semaphore / timed)

We implement again the semantics of previous concurrent accesses, but this time we are going to use semaphores. Instead of using conditional variables to block execution, you will be using semaphores. You will modify the files sem_protected_buffer.h and sem_protected_buffer.c.

The requested work and the expected result are the same as in the section Buffer protected against concurrent access (var cond / timed). However, you must use the scenario files test-13.txt and test-14.txt in order to test your work.

At last, test that your implementation is correct when the consumers are timed blocking and the producers are non-blocking (test-15.txt) and when the consumers are non-blocking and the producers are timed blocking (test-16.txt).