Assignment
1. Consider the following C code:
#include
#include
#include
int a = 0;
int main(){
fork();
printf("%d\n", ++a);
fork();
printf("%d\n", ++a);
fork();
printf("%d\n", ++a);
exit(0);
}
• Including the original process, how many processes end up calling exit()? Show
your work or modified code and output showing the correct count.
• What is one possible output of this program? Explain.
2. Included here is a trivial threaded program. The intended purpose is to construct a list of numbers from 1 to MAX-1, where each number occurs only once. Run the program and report what you observe in the output (hint: use wc to count the number of lines in the output), answering the questions: Is the output correct? If it is incorrect, why is it incorrect?
Now, if you've found that the output is incorrect, fix the program to produce the intended output. Describe what you've done, explaining why it works. Include your source as part of the answer.
Also, In your answer, include the execution times you've observed for both the original program and for one you've fixed to produce correct output. (see: man time) Try to answer at least the following: How is the execution time different? Why is it different? How does the result change your expectations of improving performance by dividing work into threads?
Hint 1: Look at man pages for sem init, sem wait, sem post.
Hint 2: Develop and test your code on os.cs.siue.edu. It will save you a headache.
Hint 3: Compile with the pthread library, e.g. gcc -lpthread yourprogram.
#include
#include
#define MAX 100000
FILE* out;
int main() {
pthread_t f3_thread, f2_thread, f1_thread;
void *f1();
int i = 0;
out = fopen("numbers", "w+");
pthread_create(&f1_thread,NULL,f1,&i);
pthread_create(&f2_thread,NULL,f1,&i);
pthread_create(&f3_thread,NULL,f1,&i);
pthread_join(f1_thread, NULL);
pthread_join(f2_thread, NULL);
pthread_join(f3_thread, NULL);
fclose(out);
return 0;
}
void *f1(int *x){
while(*x < MAX){
fprintf(out,"%d\n", *x);
(*x)++;
}
pthread_exit(0);
}
3. Here is another trivial threaded program. Each thread simply prints the value of the passed argument (ignore compiler warnings; we are abusing the argument pointer to pass an integer). Enter this program and run it a bunch of times. You'll notice that the order of thread execution is random. Without changing main(), use semaphores to enforce that threads always get executed in order, so that what is printed are the values 1, 2, and 3, in that order.
#include
#include
int main() {
pthread_t thread1, thread2, thread3;
void *f1();
pthread_create(&thread1,NULL,f1,1);
pthread_create(&thread2,NULL,f1,2);
pthread_create(&thread3,NULL,f1,3);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
pthread_join(thread3, NULL);
return 0;
}
void *f1(int x){
printf("%d\n", x);
pthread_exit(0);
}
4. Rewrite the following to working C code. Write a main() that creates five threads (one for each philosopher). Demonstrate that your solution works by printing something when each philosopher changes state. Let the program exit when each philosopher has eaten at least twice.
#define N 5 //num of philosophers
#define LEFT (i+N-1)%N //num of i's left neighbor
#define RIGHT (i+1)%N //num of i's right neighbor
#define THINKING 0 //philosopher is thinking
#define HUNGRY 1 //philosopher is hungry
#define EATING 2 //philosopher is eating
typedef int semaphore; //semaphores are a special kind of int
int state[N]; //array to keep track of everyone's state
semaphore mutex = 1; //mutual exclusion for critical regions
semaphore s[N]; //one semaphore per philosopher
void philosopher(int i) //philosopher number, from 0 to N-1
{
while(TRUE){ //repeat forever
think(); //philosopher is thinking
take_forks(i); //acquire two forks or block
eat(); //yum-yum, spaghetti
put_forks(i); //put both forks back on table
}
}
void take_forks(int i) //i: philosopher number, from 0 to N-1
{
down(&mutex); //enter critical region
state[i] = HUNGRY; //record fact that philosopher i is hungry
test(i); //try to aquire two forks
up(&mutex); //exit critical region
down(&s[i]); //block if forks were not aquired
}
void put_forks(i) //i: philosopher number, from 0 to N-1
{
down(&mutex); //enter critical region
state[i] = THINKING; //philosopher has finished eating
test(LEFT); //see if left neighbor can now eat
test(RIGHT); //see if right neighbor can now eat
up(&mutex); //exit critical region
}
void test(i) //i: philosopher number, from 0 to N-1
{
if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){
state[i] = EATING;
up(&s[i]);
}
}
5. Rewrite the following to working C code. Write a main() that creates two threads, one for the consumer and one for the producer. You must use a bounded buffer having a size N > 1. Demonstrate that your implementation works (print at least when an item is added to the buffer, when an item is removed from the buffer, when the buffer is full, and when the buffer is empty). Turn in code and output.
#define N 100 //number of slots in the buffer
typedef int semaphore; //semaphores are a special kind of int
semaphore mutex = 1; //controls access to critical region
semaphore empty = N; //counts empty buffer slots
semaphore full = 0; //counts full buffer slots
void producer(void)
{
int item;
while(TRUE){ //TRUE is a constant 1
item = produce_item(); //generate something to put in buffer
down(&empty); //decrement empty count
down(&mutex); //enter critical region
insert_item(item); //put new item in buffer
up(&mutex); //leave critical region
up(&full); //increment count of full slots
}
}
void consumer(void)
{
int item:
while(TRUE){ //infinite loop
down(&full); //decrement full count
down(&mutex); //enter crtiical region
item = remove_item(); //take item from buffer
up(&mutex); //leave critical region
up(&empty); //increment count of empty slots
consume_item(item); //do something with the item
}
}