In this lab, we will use semaphores to synchronize processes according to the semantics of the readers/writers model. For more details, the lecture slides on processes synchronization is available (cf. lecture notes, slides 60 to 64).
The semantics of the readers/writers model is as follows:
• When a writer is modifying the shared resource (i.e. is in the critical section), no other process (neither readers, nor writers) is enabled to access the resource (enter the critical section),
• When a reader is reading the resource (i.e. is in the critical section), writers cannot access the resource (i.e. enter the critical section), but other readers can access the resource (i.e. enter the critical section).
| Semaphore operation | C POSIX API |
| Init(sem, counter) | sem=sem_open(Name,O_CREAT, 0644, counter)
Role of parameters: • Name : Name of the semaphore, this name must start with / • O_CREAT : specify the action of the operation call, here we use it to create a new semaphore. • 0644 : access rights (reading and writing here). |
| P(sem) | sem_wait(sem) |
| V(sem) | sem_post(sem) |
To begin with, we start with a program without any synchronization, but for which two semaphores (namely lock and readers_lock) have been initialized. The objective will be to add the synchronization of readers and writers, and to verify that the synchronization is correctly implemented.
The C code of the program we are going to complete is available here.
Remarks about this program:
• the shared resource is a file called readers.dat.
• Semaphores are created as follows:
- if ((lock = sem_open("LOCK", O_CREAT, 0644, counter)) == SEM_FAILED)
- if ((readers_lock = sem_open("READERSLOCK", O_CREAT, 0644, counter)) == SEM_FAILED)
The produced executable (rwlab) can be run by:
• ./rwlab 3 2
The executable will launch 3 readers and 2 writers (see the C code to see how forks are used to create readers and writers).
The file semaph.h is provided in order to define the names of semaphores, as required by Unix systems. Its content is :
| semaph.h |
|
/* This file is used to : * 1 - define the name of Unix semaphores, * 2 - define the name of the file that will be the shared resource of our program. * This file will contain the number of readers (readers_nb), as used in first and last functions. */ /* Definition of semaphores */ #define LOCK "/sem55" #define READERSLOCK "/sem66" #define BARRIER "/sem77" /* The file being the shared resource */ #define SHARED_RES "readers.dat" |
The semaphore BARRIER will be used in a latter section of this lab.
In case of a problem (typically if you quit the rdlab program with a Ctrl+c signal), this program enables to cleanup existing semaphores. On a Linux system, semaphores are located in the /dev/shm folder, and can be removed using the rm command. Obviously, you will have to compile and execute the provided program to cleanup existing semaphores.
The objective is to make sure that we are not preventing several readers from concurrently accessing the shared resource.
Compile and execute the program to verify that the readers/writers problem is
not correctly solved by the current implementation. For instance, run:
./rwlab 0 2
./rwlab 2 1
$ ./rwlab 0 0
main : ./rwlab : fin
$ ./rwlab 4 0
========================= Reader 0 is first -> sem_wait
========================= Reader 0 is in CS --Time : 46:27
========================= Reader 2 is in CS --Time : 46:27
========================= Reader 3 is in CS --Time : 46:27
========================= Reader 1 is in CS --Time : 46:27
========================= Reader 0 exits CS --Time : 46:37
main : state 0000 (hexa)
========================= Reader 1 exits CS --Time : 46:38
main : state 0100 (hexa)
========================= Reader 2 exits CS --Time : 46:39
main : state 0200 (hexa)
========================= Reader 3 exits CS --Time : 46:40
========================= Reader 3 finished last -> sem_post
main : state 0300 (hexa)
main : ./rwlab : end
We will now synchronize readers and writers in order to implement the readers/writers model as presented in the lecture.
Compete the writer function of the program. As a first step, we do not deal with the writers starvation problem: unfair implementations is accepted.
To verify that your implementation is correct, execute the following scenarios and verify the execution trace you obtain is consistent with the one proposed hereafter.
1. We first verify that mutual exclusion is ensured between writers.
$ ./rwlab 0 2
******************** Writer 0 starts : 04:59
******************** Writer 0 enters CS -- Date : 04:59 (iteration : 0)
******************** Writer 1 starts : 04:59
******************** Writer 0 exits CS -- Date : 05:02 (iteration : 0)
******************** Writer 1 enters CS -- Date : 05:02 (iteration : 0)
******************** Writer 1 exits CS -- Date : 05:06 (iteration : 0)
******************** Writer 0 enters CS -- Date : 05:06 (iteration : 1)
******************** Writer 0 exits CS -- Date : 05:09 (iteration : 1)
******************** Writer 1 enters CS -- Date : 05:09 (iteration : 1)
******************** Writer 1 exits CS -- Date : 05:13 (iteration : 1)
******************** Writer 0 enters CS -- Date : 05:13 (iteration : 2)
******************** Writer 0 exits CS -- Date : 05:16 (iteration : 2)
******************** Writer 1 enters CS -- Date : 05:16 (iteration : 2)
Writer 0 : fin
******************** Writer 1 exits CS -- Date : 05:20 (iteration : 2)
main : state 0000 (hexa)
Writer 1 : fin
main : state 0100 (hexa)
main : ./ecrlec : fin
2. We check the readers/writers model is correctly implemented:
$ ./rwlab 6 2
******************** Writer 0 starts : 15:48
******************** Writer 0 enters CS -- Date : 15:48 (iteration : 0)
******************** Writer 1 starts : 15:48
========================= Reader 0 is first -> sem_wait
******************** Writer 0 exits CS -- Date : 15:51 (iteration : 0)
******************** Writer 1 enters CS -- Date : 15:51 (iteration : 0)
******************** Writer 1 exits CS -- Date : 15:55 (iteration : 0)
========================= Reader 0 is in CS --Time : 15:55
========================= Reader 2 is in CS --Time : 15:55
========================= Reader 3 is in CS --Time : 15:55
========================= Reader 4 is in CS --Time : 15:55
========================= Reader 5 is in CS --Time : 15:55
========================= Reader 1 is in CS --Time : 15:55
========================= Reader 0 exits CS --Time : 16:05
main : state 0000 (hexa)
========================= Reader 4 exits CS --Time : 16:05
main : state 0400 (hexa)
========================= Reader 5 exits CS --Time : 16:06
========================= Reader 1 exits CS --Time : 16:06
main : state 0100 (hexa)
main : state 0500 (hexa)
========================= Reader 2 exits CS --Time : 16:07
main : state 0200 (hexa)
========================= Reader 3 exits CS --Time : 16:08
========================= Reader 3 finished last -> sem_post
******************** Writer 0 enters CS -- Date : 16:08 (iteration : 1)
main : state 0300 (hexa)
******************** Writer 0 exits CS -- Date : 16:11 (iteration : 1)
******************** Writer 1 enters CS -- Date : 16:11 (iteration : 1)
******************** Writer 1 exits CS -- Date : 16:15 (iteration : 1)
******************** Writer 0 enters CS -- Date : 16:15 (iteration : 2)
******************** Writer 0 exits CS -- Date : 16:18 (iteration : 2)
******************** Writer 1 enters CS -- Date : 16:18 (iteration : 2)
Writer 0 : fin
******************** Writer 1 exits CS -- Date : 16:22 (iteration : 2)
main : state 0000 (hexa)
Writer 1 : fin
main : state 0100 (hexa)
main : ./rwlab : fin
Finally, our objective is to avoid the potential starvation of writers.
Now we need one more semaphore that will stop new readers from accessing the critical section when a writer is waiting for entering the critical section. The semaphore is called BARRIER you will have to create it; and to use it in the reader and writer functions.
Finally, to test the program, we need to add much more readers than writers. Here is an example of test:
$./rwlab 12 6
******************** Writer 2 starts : 29:33
******************** Writer 2 enters CS -- Date : 29:33 (iteration : 0)
...
...
******************** Writer 5 enters CS -- Date : 29:41 (iteration : 0)
========================= Reader 0 is first -> sem_wait
******************** Writer 5 exits CS -- Date : 29:46 (iteration : 0)
========================= Reader 0 is in CS --Time : 29:46
========================= Reader 2 is in CS --Time : 29:46
========================= Reader 1 is in CS --Time : 29:46
========================= Reader 3 is in CS --Time : 29:46
========================= Reader 4 is in CS --Time : 29:46
========================= Reader 5 is in CS --Time : 29:46
========================= Reader 6 is in CS --Time : 29:46
========================= Reader 7 is in CS --Time : 29:46
========================= Reader 0 exits CS --Time : 29:56
========================= Reader 4 exits CS --Time : 29:56
========================= Reader 1 exits CS --Time : 29:57
========================= Reader 5 exits CS --Time : 29:57
========================= Reader 2 exits CS --Time : 29:58
========================= Reader 6 exits CS --Time : 29:58
========================= Reader 3 exits CS --Time : 29:59
========================= Reader 7 exits CS --Time : 29:59
HERE, INCOMING READERS HAVE BEEN STOPPED TO ALLOW WRITERS TO ACCESS THE CRITICAL SECTION.
========================= Reader 7 finished last -> sem_post
******************** Writer 3 exits CS -- Date : 30:06 (iteration : 0)
******************** Writer 1 enters CS -- Date : 30:06 (iteration : 0)
HERE READERS ARE BEING QUEUED
========================= Reader 8 is first -> sem_wait
...
******************** Writer 2 exits CS -- Date : 30:15 (iteration : 1)
******************** Writer 1 enters CS -- Date : 30:54 (iteration : 2)
******************** Writer 1 exits CS -- Date : 30:58 (iteration : 2)
A NEW SET OF READERS ACCESS THE CRITICAL SECTION
========================= Reader 8 is in CS --Time : 30:58
========================= Reader 9 is in CS --Time : 30:58
========================= Reader 10 is in CS --Time : 30:58
========================= Reader 11 is in CS --Time : 30:58
========================= Reader 8 exits CS --Time : 31:08
========================= Reader 9 exits CS --Time : 31:09
========================= Reader 10 exits CS --Time : 31:10
========================= Reader 11 exits CS --Time : 31:11
========================= Reader 11 finished last -> sem_post
...
©(Copyright)
Bertrand Dupouy- Contact : Petr Kuznetsov (surname . name @ telecom-paristech.fr)
- Last Modified, sept 26, 2013.