Home | Projects | Notes > Operating Systems > Synchronization Problem - Producer/Consumer Problem

Synchronization Problem - Producer/Consumer Problem

Introduction

In dealing with the design synchronization and concurrency mechanisms, it is useful to be able to relate the problem at hand to known problems, and to be able to test any solution in terms of its ability to solve these known problems.
One of the several problems that appear frequently is the producer/consumer problem. (Another is, readers/writers problem)

Producer/Consumer Problem

Definition
One or more producers generating some type of data (records, characters) and placing them into the buffer. A consumer is removing items from the buffer, one at a time.
Need to ensure that
- Only one producer or consumer may access the buffer at a time.
- A producer does not try to add to a full buffer.
- A consumer does not try to take from an empty buffer.

Solutions to the Producer/Consumer Problem Using Semaphores

Solutions to the Infinite-Buffer Producer/Consumer Problem

An INCORRECT solution to the Infinite-Buffer Producer/Consumer Problem using binary semaphores:


xxxxxxxxxx
42
1
/* An incorrect solution to the Infinite-Buffer Producer/Consumer Problem using binary semaphores. */
2

3
int n;
4
binary_sempahore s = 1; /* sempahore to protect operations on buffer and variable 'n' */
5
binary_semaphore delay = 0; /* 0 means buffer is empty so consumer should delay consuming */
6

7
void producer()
8
{
9
    while (true)
10
    {
11
        produce();
12
        semWaitB(s);
13
        append();
14
        n++;
15
        if (n == 1)
16
            semSignalB(delay); /* let the consumer know that there is an item in the buffer */
17
        semSignalB(s);
18
    }
19
}
20

21
void consumer()
22
{
23
    semWaitB(delay);
24
    
25
    while (true)
26
    {
27
        semWaitB(s);
28
        take();
29
        n--;
30
        semSignalB(s);
31
        consume();
32
        if (n == 0)
33
            semWaitB(delay); /* if buffer is empty, transition to blocking state until there is
34
                                the buffer becomes non-empty */
35
    }
36
}
37

38
void main()
39
{
40
    n = 0;
41
    parbegin(producer, consumer);
42
}

The problem occurs when n gets updated between L29 and L32 due to the preemption of the producer. For this solution to work correctly, it must be guaranteed that updated made to n in L29 must be preserved until it gets tested in L32.

Possible scenario for the problem:

	Producer	Consumer	s	n	Delay
1			1	0	0
2	`semWaitB(s)`		0	0	0
3	`n++`		0	1	0
4	`if (n == 1) semSignalB(delay)`		0	1	1
5	`semSignalB(s)`		1	1	1
6		`semWaitB(delay)`	1	1	0
7		`semWaitB(s)`	0	1	0
8		`n--`	0	0	0
9		`semSignalB(s)`	1	0	0
10	`semWaitB(s)`		0	0	0
11	`n++`		0	1	0
12	`if (n == 1) semSignalB(delay)`		0	1	1
13	`semSignalB(s)`		1	1	1
14		`if (n == 0) semWaitB(delay)`	1	1	1
15		`semWaitB(s)`	0	1	1
16		`n--`	0	0	1
17		`semSignalB(s)`	1	0	1
18		`if (n == 0) semWaitB(delay)`	1	0	0
19		`semWaitB(s)`	0	0	0
20		`n--`	0	-1	0
21		`semSignalB(s)`	1	-1	0

Notice that before n in L8 can even be tested by the subsequent if statement, the producer kicks in in L10 and updates n in its code. When n became 0 in L8, semWaitB(delay) should've been called by the subsequent if statement, but it didn't happen and this inconsistency results in an invalid value for n, which is -1.

A CORRECT solution to the Infinite-Buffer Producer/Consumer Problem using binary semaphores:

To correct the above mentioned problem, you can introduce an additional variable m to consumer() code to capture the value of n:


xxxxxxxxxx
22
1
/* A correct solution to the Infinite-Buffer Producer/Consumer Problem using binary semaphores. */
2

3
...
4
    
5
void consumer()
6
{
7
    semWaitB(delay);
8
    
9
    while (true)
10
    {
11
        semWaitB(s);
12
        take();
13
        n--;
14
        m = n; /* capture the value of 'n' */
15
        semSignalB(s);
16
        consume();
17
        if (m == 0) /* no matter what, 'm' still contains the correct 'n' value to be tested! */
18
            semWaitB(delay);
19
    }
20
}
21

22
...

A solution to the Infinite-Buffer Producer/Consumer Problem using counting semaphores:


xxxxxxxxxx
32
1
/* A solution to the Infinite-Buffer Producer/Consumer Problem using counting semaphores */
2

3
semaphore n = 0, s = 1;
4

5
void producer()
6
{
7
    while (true)
8
    {
9
        produce();
10
        semWait(s);
11
        append();
12
        semSignal(s);
13
        semSignal(n);
14
    }
15
}
16

17
void consumer()
18
{
19
    while (true)
20
    {
21
        semWait(n);
22
        semWait(s);
23
        take();
24
        semSignal(s);
25
        consume();
26
    }
27
}
28

29
void main()
30
{
31
    parbegin(producer, consumer);
32
}

A Solution to the Bounded-Buffer Producer/Consumer Problem

A solution to the Bounded-Buffer Producer/Consumer Problem using counting semaphores:


xxxxxxxxxx
33
1
const int sizeofbuffer = /* buffer size */;
2
semaphore s = 1, n = 0, e = sizeofbuffer;
3

4
void producer()
5
{
6
    while (true)
7
    {
8
        produce();
9
        semWait(e);
10
        semWait(s);
11
        append();
12
        semSignal(s);
13
        semSignal(n);
14
    }
15
}
16

17
void consumer()
18
{
19
    while (true)
20
    {
21
        semWait(n);
22
        semWait(s);
23
        take();
24
        semSignal(s);
25
        semSignal(e);
26
        consume();
27
    }
28
}
29

30
void main()
31
{
32
    parbegin(producer, consumer);
33
}

References

Stallings, W. (2018). Operating Systems: Internals and Design Principles (9th ed.). Pearson Education, Inc.