讲解EECS 338、辅导C/C++编程、讲解C/C++语言、辅导bounded-buffer

EECS 338 Homework 7

General requirements:

Due at 11:59 PM on the posted due date.

Create a typed report for discussion questions and program output.

Upload a single, compressed file (e.g. zip) to Canvas that contains all required files (programs + report).

All work should be your own, as explained in the Academic Integrity policy from the syllabus.

Include either a single makefile that compiles all programs or a separate makefile for each.

1. Implement a semaphore-based solution for the bounded-buffer problem presented in Section 5.7.1 of the

textbook to analyze the sequence below, and answer the questions that follow. Be sure to use global

variables where appropriate (e.g. semaphores).

a. The parent thread initializes the semaphores (mutex, full, and empty) and creates a child thread.

b. The parent thread is a producer and uses a loop to store N values in a buffer of size N / 2. Use any

values you wish. After producing each value, print a message indicating which loop iteration the parent

is in. For example:

Parent iteration #2

c. The child thread immediately sleeps when created such that the buffer has time to fill up with N / 2

values before proceeding. For example, sleep for 1 or 2 seconds. This is intended to allow a competition

between the producer and consumer after the buffer has filled up.

d. The child thread is a consumer. Upon awakening from the forced sleep, the child thread uses a loop to

read and print N values (one at a time) from the buffer. After consuming each value, print a message

indicating which loop iteration the child is in and the value that was consumed. Below is an example

where the child thread consumed a value “40” during its iteration #3:

Child iteration #3. data = 40

Note that, when this step begins, the child will signal(empty) after consuming its 1st value. This will

unblock the parent and begin a competition between the producer and consumer.

Analysis questions (put responses in your report):

a. What is the output?

b. Based on the output, briefly describe the apparent order of when the parent and child are each

executing their critical sections (between wait(mutex) and signal(mutex)). Do they each take turns

(parent, child, parent, child, etc.) or is there a different pattern? Is it the same every time you run the

program?

c. Provide an explanation for the particular order you observed in (b), based on how the three semaphores

operate.

d. We know that output from concurrent processes does not necessarily prove the order in which they

were executed. Do the following to provide evidence of the exact order of when the parent and child

are each executing their critical sections.

Modify your program in some way to determine the ordering. For example, you could create a global

array to store a history, protected within the critical section (CS), where each thread writes its own ID

value (e.g. 1 for the parent and 2 for the child). An index value (global variable) could be used for

updating the array. In this approach, suppose the actual CS order was parent, child, parent, child, etc.

As the shared index is incremented by the threads, the array would be filled with values {1, 2, 1, 2,

etc.}. Because only one process adds a value to the array at a time, we can deduce the order in which

their CS’s were executed. You could print the array values at the end. You may use a different

approach if you wish.

In your report: (i) Explain how your modification works. (ii) Provide the output. (iii) Explain whether

it agrees with your observations from (b) and explanation from (c).

2. Using 2 producer threads and 2 consumer threads, implement a semaphore-based solution for the boundedbuffer

problem presented in Section 5.7.1 of the textbook. Design and analyze the program as described

? Chris Fietkiewicz

below.

a. The parent thread initializes the semaphores (mutex, full, and empty) and creates 4 child threads (see

below). Tip: If you wish to pass an argument to a child thread, the P-thread example from the textbook

(Fig. 4.9) provides an example and was provided as threads1.c with Lecture #9.

b. Two child threads are producers. Each uses a loop to store N unique values in a buffer of size N / 2

(total of 2N values). Each producer should use different values. After producing each value, print a

message indicating which producer is printing and which loop iteration it is in. For example:

Producer #2, iteration #5

c. The other two child threads are consumers and immediately sleep when created such that the buffer has

time to fill up with N / 2 values before proceeding. For example, sleep for 1 or 2 seconds. This is

intended to allow a competition after the buffer has filled up.

d. Upon awakening from the forced sleep, each of two consumer child threads uses a loop to read and

print N values (one at a time) from the buffer. After consuming each value, print a message indicating

which consumer is printing, the loop iteration it is in, and the value that was consumed. Below is an

example where a consumer thread consumed a value “40” during its iteration #3:

Consumer #1, iteration #3. data = 40

e. Include the same mechanism you used for the problem #1 analysis, part (d), to determine the exact

ordering of when each child thread (producers and consumers) is in its critical section. If you use the

previous suggestion of using an array, you could give each child thread a unique ID number (1, 2, 3, 4)

and have each child store its ID in the array (e.g. 1, 2, 3, 4, 1, 2, 3, 4, etc.). After the parent thread joins

all 4 child threads, it should print this history.

Analysis questions (put responses in your report):

a. What is the output, including any information printed for part (e)?

b. How many CPU cores are you using? (Type “nproc” to get the number.)

c. Based on the output, including the ordering info from part (e), describe the apparent order of when the

producers and consumers each executing their critical sections (between wait(mutex) and

signal(mutex)). Do they each take turns (producer, consumer, producer, consumer, etc.) or is there a

different pattern? Is it the same every time you run the program?

3. Modify the semaphore-based solution for the bounded-buffer problem presented in Section 5.7.1 of the

textbook as shown below. Note that, in the consumer algorithm, the sem_wait and sem_post calls are

reversed (in bold), as compared to the correct algorithm. This version will not work correctly.

Producer (normal):

sem_wait(&empty);

sem_wait(&mutex);

// Critical section

sem_post(&mutex);

sem_post(&full);

Consumer (modified):

sem_wait(&mutex);

sem_wait(&full);

// Critical section

sem_post(&empty);

sem_post(&mutex);

a. Implement this as a program with 2 threads, as in problem #1. You do not need to include a mechanism

for historical analysis, as in the analysis, part (d). What is the output?

b. Explain the behavior of this modified algorithm and why it does not work, in terms of the semaphores.