Indian Institute of Technology, Patna

Department of Computer Science and Engineering

CS3101: Operating System
Lab Assignment: Student Guide

Question 1 Guide: Multi-Stage Pipeline Simulation

Assignment Overview
This problem introduces you to multi-threaded programming using Pthreads, mutexes, and
condition variables. You will simulate a 3-stage workflow: producers generate data, proces-
sors transform it, and a consumer collects results.
Your Task
1. Implement 2 Producer threads that generate random integers (0–99).

2. Implement 2 Processor threads that square each number.

3. Implement 1 Consumer thread that logs results into an array or file.

4. Use two bounded buffers of size 10 each to pass data between stages.

5. Stop after exactly N = 50 integers and terminate gracefully.

Key Concepts and Tools
• Producer-Consumer Problem: Classic synchronization challenge.

• Mutexes (pthread mutex t): Ensure mutual exclusion on shared buffers.

• Condition Variables (pthread cond t): Enable threads to wait without busy-waiting.

• Bounded Buffers: Circular arrays for inter-thread communication.

Mini Example: Producer–Consumer with One Buffer

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define BUFFER_SIZE 5
#define N 10 // total items to produce/consume
int buffer[BUFFER_SIZE];
int in = 0, out = 0, count = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;
pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;

void* producer(void* arg) {

for (int i = 0; i < N; i++) {
int item = rand() % 100;

1
 pthread_mutex_lock(&lock);
while (count == BUFFER_SIZE)
pthread_cond_wait(&not_full, &lock);
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
count++;
printf("Producer produced: %d (count=%d)\n", item, count);
pthread_cond_signal(&not_empty);
pthread_mutex_unlock(&lock);
sleep(1);
}
return NULL;
}

void* consumer(void* arg) {

for (int i = 0; i < N; i++) {
pthread_mutex_lock(&lock);
while (count == 0)
pthread_cond_wait(&not_empty, &lock);
int item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
printf("Consumer consumed: %d (count=%d)\n", item, count);
pthread_cond_signal(&not_full);
pthread_mutex_unlock(&lock);
sleep(2);
}
return NULL;
}

int main() {
pthread_t prod, cons;
pthread_create(&prod, NULL, producer, NULL);
pthread_create(&cons, NULL, consumer, NULL);
pthread_join(prod, NULL);
pthread_join(cons, NULL);
printf("=== Simulation Complete ===\n");
return 0;
}
Instructions for Creating and Executing Files
• Save your file as q1.c.
• Compile with:
gcc q1.c -o q1 -pthread

• Run with:
./q1

2
Question 2 Guide: Matrix Multiplication Using Threads in C
Assignment Overview
In this problem, you will implement **matrix multiplication** using multi-threading. Each
element of the result matrix C[i][j] will be computed by a separate thread, demonstrating par-
allel computation.
Your Task

1. Declare matrices A, B, and C as global variables.

2. For each element C[i][j], create one thread to compute it.

3. Each thread computes the **dot product** of the ith row of A and the jth column of B.

4. Store the result in C[i][j].

5. Join all threads in the main function and print the final matrix.

Key Concepts and Tools

• Pthreads: Create and manage multiple threads.

• Struct Arguments: Pass row/column indices to threads safely.

• Parallel Computation: Each thread writes to a unique cell, so no mutex is required.

Implementation Skeleton

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define M 3
#define K 3
#define N 3

int A[M][K], B[K][N], C[M][N];

typedef struct {
int row;
int col;
} cell;

void* compute_cell(void* arg) {

cell* c = (cell*) arg;
int sum = 0;
for(int k = 0; k < K; k++)
sum += A[c->row][k] * B[k][c->col];
C[c->row][c->col] = sum;
free(c);
pthread_exit(NULL);
}

3
int main() {
pthread_t threads[M*N];
int t=0;
// Initialize A and B
for(int i=0;i<M;i++)
for(int j=0;j<K;j++)
A[i][j] = i+j;
for(int i=0;i<K;i++)
for(int j=0;j<N;j++)
B[i][j] = i+1;
// Create threads
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cell* c = malloc(sizeof(cell));
c->row = i; c->col = j;
pthread_create(&threads[t++], NULL, compute_cell, c);
}
}
// Join threads
for(int i=0;i<M*N;i++)
pthread_join(threads[i], NULL);
// Print result
printf("Result matrix C:\n");
for(int i=0;i<M;i++){
for(int j=0;j<N;j++)
printf("%d ", C[i][j]);
printf("\n");
}
return 0;
}

Sample Output

Result matrix C:
3 3 3
6 6 6
9 9 9

Instructions for Creating and Executing Files

• Save your file as q2.c.

• Compile with: gcc q2.c -o q2 -pthread

• Run with: ./q2

4
Question 3: The Royal Banquet – Philosophers’ Dilemma
Scenario:
The King of a great kingdom is hosting a Royal Banquet for philosophers. The banquet has
unique challenges:

• Dynamic Guests: Philosophers may join late or leave early.

• Limited Cutlery: F < N forks; each philosopher needs 2 to eat.

• Fairness Decree: If a philosopher waits more than T seconds, they must be prioritized.

• The Waiter: Central coordinator ensuring no deadlock or starvation.

Banquet Duration: 60 seconds. At the end, the Waiter prints a Banquet Report:
• Number of times each philosopher ate.

• Average waiting time for each philosopher.

• Maximum waiting time before eating.

Your Task:

• Design a concurrency solution using C, pthreads, and synchronization primitives.

• Philosophers are threads, forks are shared mutexes, waiter is a monitor thread.

• Ensure no deadlock, no starvation, and fairness.

• Track statistics and print report at the end.

Key Concepts:
• Mutex Locks: Protect fork resources from simultaneous access.

• Monitor/Waiter Thread: Centralized coordinator to avoid deadlocks and enforce fair-

ness.

• Condition Variables: Philosophers wait until forks are available or priority is granted.

• Fairness/Starvation Prevention: Track waiting time and prioritize philosophers who

waited too long.

• Dynamic Thread Management: Philosophers may join/leave during simulation.

Implementation Checklist:
1. Create philosopher threads with unique IDs.

2. Initialize F mutexes for forks (F < N ) and one waiter thread.

3. Implement philosopher logic:

• Think for random time.

• Request forks from waiter.

5
 • Eat when forks are allocated.
• Release forks back to waiter.
• Update personal statistics (eat count, wait time).

4. Implement Waiter/monitor logic:

• Track which forks are available.

• Allow a philosopher to pick up forks only if both are free.
• Prioritize philosophers who waited > T seconds.
• Signal philosophers when forks are available.

5. Run the simulation for 60 seconds, then print the Banquet Report.
Hints:
• Use an array of mutexes for forks.

• Use an array or struct to track each philosopher’s statistics.

• Use pthread cond t for signaling when forks become available.

• Random delays (sleep(rand() % t)) simulate thinking and eating times.

• Ensure the waiter avoids deadlocks even if multiple philosophers request forks simulta-
neously.
Standard Dining Philosophers Implementation (for reference):

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define N 5 // Number of philosophers

pthread_mutex_t forks[N];
pthread_t philosophers[N];

void *philosopher(void *num) {

int id = *(int *)num;
int left = id;
int right = (id + 1) % N;

for(int i = 0; i < 3; i++) {

printf("Philosopher %d is thinking.\n", id);
sleep(rand() % 3);

// Deadlock avoidance: pick up lower-numbered fork first

if (id % 2 == 0) {
pthread_mutex_lock(&forks[left]);
pthread_mutex_lock(&forks[right]);
} else {

6
 pthread_mutex_lock(&forks[right]);
pthread_mutex_lock(&forks[left]);
}

printf("Philosopher %d is eating.\n", id);

sleep(rand() % 2);

pthread_mutex_unlock(&forks[left]);
pthread_mutex_unlock(&forks[right]);

printf("Philosopher %d finished eating.\n", id);

}
pthread_exit(NULL);
}

int main() {
int ids[N];

for(int i = 0; i < N; i++)

pthread_mutex_init(&forks[i], NULL);

for(int i = 0; i < N; i++) {

ids[i] = i;
pthread_create(&philosophers[i], NULL, philosopher, &ids[i]);
}

for(int i = 0; i < N; i++)

pthread_join(philosophers[i], NULL);

for(int i = 0; i < N; i++)

pthread_mutex_destroy(&forks[i]);

printf("Dinner is over.\n");
return 0;
}

Sample Output (truncated):

Philosopher 0 is thinking...
Philosopher 1 is thinking...
Philosopher 2 is thinking...
Philosopher 3 is thinking...
Philosopher 4 is thinking...
Philosopher 0 is eating...
Philosopher 2 is eating...
Philosopher 0 finished eating...
...
Dinner is over.

Instructions for Creating and Executing Files:

• Save your file as q3.c.

7
 • Compile with: gcc q3.c -o q3 -pthread

• Run with: ./q3 6 4

where 6 is the number of philosophers and 4 is the number of forks