design a programming solution to the bounded-buffer problem using the producer a
ID: 3762425 • Letter: D
Question
design a programming solution to the bounded-buffer problem using the producer and consumer processes shown in Figures 5.9 and 5.10. The solution presented in Section 5.7.1 uses three semaphores: empty and full, which count the number of empty and full slots in the buffer, and mutex, which is a binary (or mutualexclusion) semaphore that protects the actual insertion or removal of items in the buffer. For this project, you will use standard counting semaphores for
empty and full and a mutex lock, rather than a binary semaphore, to represent mutex. The producer and consumer—running as separate threads—will move items to and froma buffer that is synchronizedwith the empty, full, andmutex
structures. You can solve this problem using either Pthreads or the Windows API.
The Buffer Internally, the buffer will consist of a fixed-size array of type buffer item (which will be defined using a typedef). The array of buffer item objects will be manipulated as a circular queue. The definition of buffer item, along
with the size of the buffer, can be stored in a header file such as the following:
/* buffer.h */
typedef int buffer item;
#define BUFFER SIZE 5
The buffer will be manipulated with two functions, insert item() and remove item(), which are called by the producer and consumer threads, respectively. A skeleton outlining these functions appears in Figure 5.24. The insert item() and remove item() functions will synchronize the producer and consumer using the algorithms outlined in Figures 5.9 and
5.10. The buffer will also require an initialization function that initializes the mutual-exclusion object mutex along with the empty and full semaphores. The main() function will initialize the buffer and create the separate producer and consumer threads. Once it has created the producer and consumer threads, the main() function will sleep for a period of time and, upon awakening, will terminate the application. The main() function will be passed three parameters on the command line:
1. How long to sleep before terminating
2. The number of producer threads
3. The number of consumer threads
The Producer and Consumer Threads The producer thread will alternate between sleeping for a random period of time and inserting a random integer into the buffer. Random numbers will be produced using the rand() function, which produces random integers between 0 and RAND MAX. The consumer will also sleep for a random period of time and, upon awakening, will attempt to remove an item from the buffer. An outline of the producer and consumer threads appears in Figure 5.26. As noted earlier, you can solve this problem using either Pthreads or the Windows API. In the following sections, we supply more information on each
of these choices.Pthreads Thread Creation and Synchronization Creating threads using the Pthreads API is discussed in Section 4.4.1. Coverage of mutex locks and semaphores using Pthreads is provided in Section 5.9.4. Refer to those sections for specific instructions on Pthreads thread creation and synchronization.
Windows
Section 4.4.2 discusses thread creation using the Windows API. Refer to that
section for specific instructions on creating threads.
Windows Mutex Locks
Mutex locks are a type of dispatcher object, as described in Section 5.9.1. The
following illustrates how to create a mutex lock using the CreateMutex()
function:
#include <windows.h>
HANDLE Mutex;
Mutex = CreateMutex(NULL, FALSE, NULL);
The first parameter refers to a security attribute for the mutex lock. By setting this attribute to NULL, we disallow any children of the process creating this mutex lock to inherit the handle of the lock. The second parameter indicates
whether the creator of the mutex lock is the lock’s initial owner. Passing a value of FALSE indicates that the thread creating the mutex is not the initial owner. (We shall soon see how mutex locks are acquired.) The third parameter allows us to name the mutex. However, because we provide a value of NULL, we do not name the mutex. If successful, CreateMutex() returns a HANDLE to the mutex lock; otherwise, it returns NULL. In Section 5.9.1, we identified dispatcher objects as being either signaled or nonsignaled. A signaled dispatcher object (such as a mutex lock) is available for ownership. Once it is acquired, it moves to the nonsignaled state. When it is released, it returns to signaled.
WaitForSingleObject(Mutex, INFINITE);
The parameter value INFINITE indicates that we will wait an infinite amount of time for the lock to become available. Other values could be used that would allow the calling thread to time out if the lock did not become available within
a specified time. If the lock is in a signaled state, WaitForSingleObject() returns immediately, and the lock becomes nonsignaled. A lock is released (moves to the signaled state) by invoking ReleaseMutex()—for example, as
follows:
ReleaseMutex(Mutex);
Windows Semaphores
Semaphores in the Windows API are dispatcher objects and thus use the same signaling mechanism as mutex locks. Semaphores are created as follows:
#include <windows.h>
HANDLE Sem;
Sem = CreateSemaphore(NULL, 1, 5, NULL);
The first and last parameters identify a security attribute and a name for the semaphore, similar to what we described for mutex locks. The second and third parameters indicate the initial value and maximum value of the semaphore. In
this instance, the initial value of the semaphore is 1, and its maximum value is 5. If successful, CreateSemaphore() returns a HANDLE to the mutex lock; otherwise, it returns NULL. Semaphores are acquired with the same WaitForSingleObject() function as mutex locks.We acquire the semaphore Sem created in this example by
using the following statement:
WaitForSingleObject(Semaphore, INFINITE);
If the value of the semaphore is > 0, the semaphore is in the signaled state
and thus is acquired by the calling thread. Otherwise, the calling thread blocks
indefinitely—as we are specifying INFINITE—until the semaphore returns to
the signaled state.
The equivalent of the signal() operation forWindows semaphores is the
ReleaseSemaphore() function. This function is passed three parameters:
1. The HANDLE of the semaphore
2. How much to increase the value of the semaphore
3. A pointer to the previous value of the semaphore
We can use the following statement to increase Sem by 1:
ReleaseSemaphore(Sem, 1, NULL);
Both ReleaseSemaphore() and ReleaseMutex() return a nonzero value if
successful and 0 otherwise.
Mutex locks are acquired by invoking the WaitForSingleObject() function.
The function is passed the HANDLE to the lock along with a flag indicating
how long to wait. The following code demonstrates how the mutex lock created
above can be acquired:
Explanation / Answer
Take an example that a circular buffer with two pointers in and out to indicate the next available position for depositing data and the position that contains the next data to be retrieved. See the diagram below. There are two groups of threads, producers and consumers. Each producer deposits a data items into the in position and advances the pointer in, and each consumer retrieves the data item in position out and advances the pointer out.
producer will produce an item and place it in a bound-buffer for the consumer. Then the consumer will remove the item from the buffer and print it to the screen.
bound-buffer it is a container with a limit. We have to be very careful in our case that we don’t over fill the buffer or remove something that isn’t there; in c this will produce a segmentation fault.
Here is an example of how registers work when you increment a counter-
register1 = counter;
register1 = register1 + 1;
counter = register1;
Now image two threads manipulating this same example but one thread is decrementing –
(T1) register1 = counter; [register1 = 5]
(T1) register1 = register1 + 1; [register1 = 6]
(T2) register2 = counter; [register2 = 5]
(T2) register2 = register2 – 1; [register2 = 4]
(T1) counter = register1; [counter = 6]
(T2) counter = register2; [counter = 4]
Create the producer threads.
Create the consumer threads.
Put main() to sleep().
Exit the program.
If you are kind of rusty on how pthreads work, I have a previous tutorial that may be some help in understanding them:
Prime numbers using POSIX threads on Linux in [C]
That will give you a clearer picture on how to create a pthread.
Time for the code…
CODE:
/* buffer.h */
typedef int buffer_item;
#define BUFFER_SIZE 5
/* main.c */
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include "buffer.h"
#define RAND_DIVISOR 100000000
#define TRUE 1
/* The mutex lock */
pthread_mutex_t mutex;
/* the semaphores */
sem_t full, empty;
/* the buffer */
buffer_item buffer[BUFFER_SIZE];
/* buffer counter */
int counter;
pthread_t tid; //Thread ID
pthread_attr_t attr; //Set of thread attributes
void *producer(void *param); /* the producer thread */
void *consumer(void *param); /* the consumer thread */
void initializeData() {
/* Create the mutex lock */
pthread_mutex_init(&mutex, NULL);
/* Create the full semaphore and initialize to 0 */
sem_init(&full, 0, 0);
/* Create the empty semaphore and initialize to BUFFER_SIZE */
sem_init(&empty, 0, BUFFER_SIZE);
/* Get the default attributes */
pthread_attr_init(&attr);
/* init buffer */
counter = 0;
}
/* Producer Thread */
void *producer(void *param) {
buffer_item item;
while(TRUE) {
/* sleep for a random period of time */
int rNum = rand() / RAND_DIVISOR;
sleep(rNum);
/* generate a random number */
item = rand();
/* acquire the empty lock */
sem_wait(&empty);
/* acquire the mutex lock */
pthread_mutex_lock(&mutex);
if(insert_item(item)) {
fprintf(stderr, " Producer report error condition ");
}
else {
printf("producer produced %d ", item);
}
/* release the mutex lock */
pthread_mutex_unlock(&mutex);
/* signal full */
sem_post(&full);
}
}
/* Consumer Thread */
void *consumer(void *param) {
buffer_item item;
while(TRUE) {
/* sleep for a random period of time */
int rNum = rand() / RAND_DIVISOR;
sleep(rNum);
/* aquire the full lock */
sem_wait(&full);
/* aquire the mutex lock */
pthread_mutex_lock(&mutex);
if(remove_item(&item)) {
fprintf(stderr, "Consumer report error condition ");
}
else {
printf("consumer consumed %d ", item);
}
/* release the mutex lock */
pthread_mutex_unlock(&mutex);
/* signal empty */
sem_post(&empty);
}
}
/* Add an item to the buffer */
int insert_item(buffer_item item) {
/* When the buffer is not full add the item
and increment the counter*/
if(counter < BUFFER_SIZE) {
buffer[counter] = item;
counter++;
return 0;
}
else { /* Error the buffer is full */
return -1;
}
}
/* Remove an item from the buffer */
int remove_item(buffer_item *item) {
/* When the buffer is not empty remove the item
and decrement the counter */
if(counter > 0) {
*item = buffer[(counter-1)];
counter--;
return 0;
}
else { /* Error buffer empty */
return -1;
}
}
int main(int argc, char *argv[]) {
/* Loop counter */
int i;
/* Verify the correct number of arguments were passed in */
if(argc != 4) {
fprintf(stderr, "USAGE:./main.out <INT> <INT> <INT> ");
}
int mainSleepTime = atoi(argv[1]); /* Time in seconds for main to sleep */
int numProd = atoi(argv[2]); /* Number of producer threads */
int numCons = atoi(argv[3]); /* Number of consumer threads */
/* Initialize the app */
initializeData();
/* Create the producer threads */
for(i = 0; i < numProd; i++) {
/* Create the thread */
pthread_create(&tid,&attr,producer,NULL);
}
/* Create the consumer threads */
for(i = 0; i < numCons; i++) {
/* Create the thread */
pthread_create(&tid,&attr,consumer,NULL);
}
/* Sleep for the specified amount of time in milliseconds */
sleep(mainSleepTime);
/* Exit the program */
printf("Exit the program ");
exit(0);
}
Here, we have the output for the program. As you can see we told main to quit after 10 seconds and we produced 10 producer and 10 consumer threads.
You can try this also
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.