Lab 11: Concurrency, semaphores, smokers

Lab preparation

Create directory lab11. Copy the following files into it:

/home/wcbrown/courses/IC221/labs/L11/prodcons.tar.gz
/home/wcbrown/courses/IC221/labs/L11/smokers.tar.gz
	

Background

In class we discussed the Bounded-Buffer Producer-Consumer concurrency problem. A solution that uses shared memory for the buffer and semaphores for mutual exclusion is provided in prodcons.tar.gz, which contains the following files:

README.txt            - a text file describing the other files in this archive
shared.h shared.c     - allocates semaphores and shared buffer
prodcons.h prodcons.c - creates producer thread and consumer thread.
producer.c            - reads characters from stdin, puts encrypted characters in the shared buffer
consumer.c            - reads characters from the shared buffer, decrypts them and prints them to stdout
crypt.h crypt.c       - implements the encryption/decryption
Makefile              - builds the solution
cleartext             - text file to be encrypted/decrypted
	

Build the program using make, and run it like this (for example):

$ ./prodcons cleartext

The producer reads characters from the text file named on the command line and puts an encrypted version of it (one character at a time) in the shared buffer. The consumer reads from the shared buffer and prints the decrypted file to stdout.

1. Examine shared.c to see how semaphores are initialized.
2. Examine prodcons.c to see how the producer and consumer threads are initiated.
3. Refer to the class notes, and carefully examine the producer() and consumer() code to understand how semaphores are used to solve this concurrency problem.

Assignment: Smokers

After accomplishing the above, you are to solve the Smokers concurrency problem, stated as follows:

Three smokers and one agent are sitting around a table. A smoker requires paper, tobacco and matches in order to smoke, but has only one of the three items: one smoker has paper, but no tobacco or matches. Another smoker has tobacco, but no paper or matches. The remaining smoker has matches, but no paper or tobacco. The smokers have an unlimited supply of their unique item, but only that item. The agent has an unlimited supply of all three items. If no-one is smoking, the agent will place two of the items at random on the table (similar to the producer 'producing'), thereby implicitly selecting a smoker. The appropriate smoker then uses these items to smoke (similar to the consumer 'consuming').

You are given an archive named smokers.tar.gz. Extract its contents. Examine the Makefile: it creates an executable program named smokers. Right now the program is incomplete, your job is to add to the bodies of agent(), paper(), matches(), and tobacco() to produce a correct simulation of the smokers scenario. Here's an example run of a correct solution. Notice how all three smokers eventually get their turn to smoke:

AGENT: MATCHES and TOBACCO
PAPER: starting.
PAPER: stopping.
AGENT: PAPER and TOBACCO
MATCHES: starting.
MATCHES: stopping.
AGENT: MATCHES and TOBACCO
PAPER: starting.
PAPER: stopping.
AGENT: MATCHES and TOBACCO
PAPER: starting.
PAPER: stopping.
AGENT: PAPER and MATCHES
TOBACCO: starting.
TOBACCO: stopping.
AGENT: PAPER and TOBACCO
MATCHES: starting.
MATCHES: stopping.
AGENT: PAPER and MATCHES
TOBACCO: starting.
^C
	

There are a few rules to your solution:

1. The only global variables allowed are the four semaphores defined in shared.h/c.
2. Output from agent() must begin with AGENT:.
3. Output from paper() must begin with PAPER:.
4. Output from matches() must begin with MATCHES:.
5. Output from tobacco() must begin with TOBACCO:.
6. Each smoker must call sleep(1 + rand()%3) between printing out that it is starting to smoke and stopping to smoke. This provides the simuation with a random duration for the smoking.
7. The agent must wait until the current smoker has finished before placing more items on the table.

Submission instructions

Be sure to put your name in all of the relevant files, and submit the lab11 directory using the submit script. Your submission must inlcude a text file README that contains your name, alpha, and answers to the following questions:

 
1. Suppose we define s1 with "sem_t s1;".  Which of the following is
   a correct call of sem_init, and why:

   a. sem_init(s1,0,0);
   b. sem_init(&s1,0,0);
   c. sem_init(*s1,0,0);

2. Consider the following (partially complete) code:

   sem_t mys;

   void* f(void *p)
   {
     sem_init(&mys,0,1);
     ... ← Code calling sem_post and sem_wait on mys
   }
   void* g(void *q)
   {
     ... ← Code calling sem_post and sem_wait on mys
   }
   int main()
   {
     pthread_t A, B;
     pthread_create(&A,NULL,f,NULL);
     pthread_create(&B,NULL,g,NULL);
     pause();
   }

   Explain why there is a race condition that causes this system to
   fail sometimes, and explain how to fix the bug.	

3. Assuming that S is a valid (i.e. initialized) semaphore, and that
   our system supports sem_post, why might the call sem_post(S) fail?
   Hint:RTFMP!

4. Given the definition

	sem_t A[10];

   What are the types of the following expressions:

   a. A
   c. A[4];
   d. &A[4]
   d. *&A[4]