Notes

Provide a pseudo-code and a concise description of your design. In particular, describe the requirements you have identified for mutual exclusion and synchronization.

The program runs for the simulation of customers waiting for queuing, in the queuing and shopping in a shop. Each customer is represented by a thread and a thread of guard is also identified for managing the queue and opens the door for customer’s entry. As there are loads of customer thread are executing concurrently, some of the codes are being protected by mutual exclusion to avoid two threads accessing the same variables at the same time. Semaphores are also declared for signaling purposes, for example, signaling the guard when the queue is full. Implementation of the code is being explained by the pseudo-code below.

Pseudo-code:

// the main function
int main(int argc, char *argv[]){
// declaration of some vatiables
.....

// create the thread for guard
create one thread for guard.

//create one thread for each of the consumer
for every consumer{
create thread for consumer.
}

//join threads
for every consumer{
join thread for all consumers.
}

join the guard thread.

//show statistics
cout total_customers_entered_queue
cout total_customers_left_shop
cout avg_trial
cout avg_wait
cout avg_dur
}

// implementation for the guard thread
void* TheGuard(void *param){
if the queue is not full{
//wait for the queue to be full
sem_wait(&Full_Queue);

// print QUEUE FULL alert when it is full
cout<<"QUEUE FULL"<<endl;
}

lock

// counting the number of customers who have left the shop
if 10 customers have left{ // shop empty
//issue sem wait signal to empty shop
sem_wait(&Empty_Shop);

//for counting the customer in the coming queue
set customer counter = 0;

//print SHOP EMPTY alert
cout<<"Shop Empty"<<endl;

if queue == 10{ // if the queue is full
// open the door.
doorOpen == true
print Guard <x,y,z>: DOOR OPEN.

//all customers in the queue have gone into the shop.
set the queue = 0

// close the door after customers gone in.
doorOpen == false
}
}
if all cusomters have shopped
end the guard's job.

unlock
}
pthread_exit(NULL);
}

// implementation for the customer threads
void* Customer(void *param){
//customer arrives at different time
sleep for some time within A.

//when the queue is full
while(headCount == 10){
lock
//customer tries to join the queue
total number of trials to queue++
record start time
unlock

//customer hang around and come back later when the queue is full
sleep for some time with range B.
lock
record end time
}

//wait for signal where the queue is open for queueing again.
lock
headCount++ //increment the no. of people in the queue by one
unlock

//Queue is full
lock
Queue++
record start queue time
total custumer queued++

//for the 10th person in the queue
if (Queue == 10)
//tell the guard that the queue is full
sem_post(&Full_Queue);
unlock

// for the shop is empty
lock
//guard opens the door to let people in
while(doorOpen==false);
Out_Queue++ //denote a customer moved from queue to shop
record stop queue time.

//each customer will shop for a while within time C.
sleep for some time within C.

if all people moved into the shop{
//tell the guard
sem_post(&Guard);
unlock

lock
//Queue line again
sem_post(&Wait_Queue);
headCount=0;
unlock

lock
//after customer leaves the shop
customerLeave++;
customer_Shop_Total++;

//the last person leaves the shop
if 10th person leaves
//singal empty shop
sem_post(&Empty_Shop);
unlock

//quit the thread
pthread_exit(NULL);
}

Describe the role and function of each (group of) thread(s) created.

There are total 2types of role defined in the functions, generated in pthreads in the main. They are the customer and guard, with the arrangement of line in waiting and shopping queue. Seven mutex lock and four semaphores are created in the co-operation between the customer and theguard function. There are mutual exclusions and sync when the customer enters the queue, or the queue is full, as well as when the guard notice the shop is empty, or full.

State the initial value and describe the role of each mutex lock and semaphore created. In particular, explain how they are used to achieve mutual exclusion and synchronization.

In the customer type of threads, the customer function define its characteristics through waiting time, empty/full waiting queue and as well as the empty/full shopping queue generated by four types of semaphore with the signal to the guard. At first, the customer will have a random time A generated by the sleep() and rand() function, to random access the waiting queue. If they find the queue full, Mutex A and B will control the trail and duration and soon they will hang around in a random time B. Since the upper limit for the waiting queue is per 10 customers, mutex lock C and D will control the number of headcount and also current queue time initially generated by the sem_wait in Wait_Queue semaphores. The Wait Queue semaphore is initially 10 defined in main, with the increase of customers (signaling the sem_wait() function), it will decrease down to 0 and the semaphore of the full_queue will be increased from 0 to 1. The guard will be told that a full queue is obtained and door will opened in Mutex E until the shop is empty, noticing by another semaphore with the sem signal from 0 to 1 in co-operation with another mutex lock with the confirm of single time operation. Once the transferred of the customer from waiting queuing to shopping queue is done, the wait queue semaphore will issue the sem signal code until its value become 0 again in Mutex F (with empty waiting queue again)and G(for the control of custom leave and number of the total customer in the shop).

On the other hand, in the TheGuard Function, the guard control the leaving customer from the shop and notice if there is empty shop via a single mutex lock and all the four types of semaphores. As introduced above, the guard will issue sem wait signal of the full queue semaphore of 1 back to 0 if the shop door is open. When the random time C is over for all customer in the shop, the guard will issue the sem wait signal of the empty shop semaphores for notice if there are any full waiting queues afterwards for loop transfer again. The guard semaphores ifself will also be signal a sem wait call to release that new transform is available for full waiting queue of customers.