Classical Process Synchronization Problems using Semaphores
1. Bounded Buffer (Producer-Consumer) Problem
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#define SIZE 5
int buffer[SIZE];
int in = 0, out = 0;
sem_t empty, full;
pthread_mutex_t mutex;
void* producer(void* arg) {
int item = 1;
while (1) {
sem_wait(&empty);
pthread_mutex_lock(&mutex);
buffer[in] = item;
printf("Produced: %d\n", item);
in = (in + 1) % SIZE;
item++;
pthread_mutex_unlock(&mutex);
sem_post(&full);
sleep(1);
}
}
void* consumer(void* arg) {
int item;
while (1) {
sem_wait(&full);
pthread_mutex_lock(&mutex);
item = buffer[out];
printf("Consumed: %d\n", item);
out = (out + 1) % SIZE;
pthread_mutex_unlock(&mutex);
sem_post(&empty);
sleep(2);
}
}
int main() {
pthread_t p, c;
sem_init(&empty, 0, SIZE);
sem_init(&full, 0, 0);
pthread_mutex_init(&mutex, NULL);
pthread_create(&p, NULL, producer, NULL);
pthread_create(&c, NULL, consumer, NULL);
pthread_join(p, NULL);
pthread_join(c, NULL);
return 0;
}
2. Reader-Writer Problem
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t wrt;
pthread_mutex_t mutex;
int readcount = 0;
int data = 0;
void* reader(void* arg) {
int id = *(int*)arg;
while (1) {
pthread_mutex_lock(&mutex);
readcount++;
if (readcount == 1)
sem_wait(&wrt);
pthread_mutex_unlock(&mutex);
printf("Reader %d reads data = %d\n", id, data);
sleep(1);
pthread_mutex_lock(&mutex);
readcount--;
if (readcount == 0)
sem_post(&wrt);
pthread_mutex_unlock(&mutex);
sleep(1);
}
}
void* writer(void* arg) {
int id = *(int*)arg;
while (1) {
sem_wait(&wrt);
data++;
printf("Writer %d writes data = %d\n", id, data);
sem_post(&wrt);
sleep(2);
}
}
int main() {
pthread_t r1, r2, w1;
int id1 = 1, id2 = 2, id3 = 1;
sem_init(&wrt, 0, 1);
pthread_mutex_init(&mutex, NULL);
pthread_create(&r1, NULL, reader, &id1);
pthread_create(&r2, NULL, reader, &id2);
pthread_create(&w1, NULL, writer, &id3);
pthread_join(r1, NULL);
pthread_join(r2, NULL);
pthread_join(w1, NULL);
return 0;
}
3. Dining Philosophers Problem
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#define N 5
sem_t chopstick[N];
void* philosopher(void* num) {
int id = *(int*)num;
while (1) {
printf("Philosopher %d is thinking\n", id);
sleep(1);
sem_wait(&chopstick[id]);
sem_wait(&chopstick[(id + 1) % N]);
printf("Philosopher %d is eating\n", id);
sleep(2);
sem_post(&chopstick[id]);
sem_post(&chopstick[(id + 1) % N]);
printf("Philosopher %d finished eating\n", id);
}
}
int main() {
pthread_t phil[N];
int id[N];
for (int i = 0; i < N; i++) {
sem_init(&chopstick[i], 0, 1);
id[i] = i;
}
for (int i = 0; i < N; i++)
pthread_create(&phil[i], NULL, philosopher, &id[i]);
for (int i = 0; i < N; i++)
pthread_join(phil[i], NULL);
return 0;
}
4. Banker’s Algorithm
#include <stdio.h>
int main() {
int n, m, i, j, k, p;
printf("Enter no. of processes: ");
scanf("%d", &n);
printf("Enter no. of resources: ");
scanf("%d", &m);
int alloc[n][m], max[n][m], avail[m], need[n][m];
int finish[n], safe[n], ind = 0;
printf("Enter Allocation matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&alloc[i][j]);
printf("Enter Max matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&max[i][j]);
printf("Enter Available resources:\n");
for(i=0;i<m;i++)
scanf("%d",&avail[i]);
// Need = Max - Allocation
printf("\nNeed matrix:\n");
for(i=0;i<n;i++){
for(j=0;j<m;j++){
need[i][j] = max[i][j] - alloc[i][j];
printf("%d ", need[i][j]);
printf("\n");
// Safety Check Function
for(i=0;i<n;i++) finish[i]=0;
for(k=0;k<n;k++){
for(i=0;i<n;i++){
int flag=0;
if(finish[i]==0){
for(j=0;j<m;j++)
if(need[i][j]>avail[j]){ flag=1; break; }
if(flag==0){
for(j=0;j<m;j++)
avail[j]+=alloc[i][j];
safe[ind++]=i;
finish[i]=1;
}
}
int safeFlag=1;
for(i=0;i<n;i++)
if(finish[i]==0) safeFlag=0;
if(safeFlag){
printf("\nSystem is in SAFE state.\nSafe sequence: ");
for(i=0;i<n;i++)
printf("P%d ",safe[i]);
} else {
printf("\nSystem is NOT in safe state.");
return 0;
// ----- Resource Request -----
printf("\n\nEnter process number making request (0-%d): ", n-1);
scanf("%d",&p);
int req[m];
printf("Enter request for each resource:\n");
for(i=0;i<m;i++)
scanf("%d",&req[i]);
// Check request ≤ need and request ≤ available
int valid=1;
for(i=0;i<m;i++){
if(req[i]>need[p][i] || req[i]>avail[i])
valid=0;
if(valid){
// Temporarily allocate
for(i=0;i<m;i++){
avail[i]-=req[i];
alloc[p][i]+=req[i];
need[p][i]-=req[i];
// Check safety again
for(i=0;i<n;i++) finish[i]=0;
ind=0;
for(k=0;k<n;k++){
for(i=0;i<n;i++){
int flag=0;
if(finish[i]==0){
for(j=0;j<m;j++)
if(need[i][j]>avail[j]){ flag=1; break; }
if(flag==0){
for(j=0;j<m;j++)
avail[j]+=alloc[i][j];
safe[ind++]=i;
finish[i]=1;
safeFlag=1;
for(i=0;i<n;i++)
if(finish[i]==0) safeFlag=0;
if(safeFlag){
printf("\nRequest can be granted.\nSystem remains in SAFE state.\nSafe sequence:
");
for(i=0;i<n;i++)
printf("P%d ",safe[i]);
} else {
printf("\nRequest cannot be granted. System would be UNSAFE.");
} else {
printf("\nRequest is invalid (exceeds need or available).");
return 0;
5. Memory management
#include <stdio.h>
void allocate(int b[], int m, int p[], int n, int type)
int a[10], i, j, pos;
for (i = 0; i < n; i++)
a[i] = -1;
for (i = 0; i < n; i++)
pos = -1;
for (j = 0; j < m; j++)
if (b[j] >= p[i])
if (type == 1)
pos = j; // First Fit
break;
if (type == 2 && (pos == -1 || b[j] < b[pos]))
pos = j; // Best Fit
if (type == 3 && (pos == -1 || b[j] > b[pos]))
pos = j; // Worst Fit
}
if (pos != -1)
a[i] = pos;
b[pos] -= p[i];
if (type == 1)
printf("\n--- First Fit ---\n");
if (type == 2)
printf("\n--- Best Fit ---\n");
if (type == 3)
printf("\n--- Worst Fit ---\n");
printf("Process\tSize\tBlock\n");
for (i = 0; i < n; i++)
if (a[i] != -1)
printf("%d\t%d\t%d\n", i + 1, p[i], a[i] + 1);
else
printf("%d\t%d\tNot Allocated\n", i + 1, p[i]);
}
int main()
int m, n, i;
int b1[10], b2[10], b3[10], p[10];
printf("Enter no. of blocks: ");
scanf("%d", &m);
printf("Enter block sizes: ");
for (i = 0; i < m; i++)
scanf("%d", &b1[i]);
b2[i] = b3[i] = b1[i];
printf("Enter no. of processes: ");
scanf("%d", &n);
printf("Enter process sizes: ");
for (i = 0; i < n; i++)
scanf("%d", &p[i]);
allocate(b1, m, p, n, 1); // First Fit
allocate(b2, m, p, n, 2); // Best Fit
allocate(b3, m, p, n, 3); // Worst Fit
return 0;
6. Page replacement
#include <stdio.h>
int main() {
int n, i, j, k, f, page[50], frame[10], count=0, hit, min, pos[10];
printf("Enter length of reference string: ");
scanf("%d",&n);
printf("Enter reference string: ");
for(i=0;i<n;i++)
scanf("%d",&page[i]);
printf("Enter frame size: ");
scanf("%d",&f);
// ----- FIFO -----
for(i=0;i<f;i++) frame[i]=-1;
count=0; hit=0;
for(i=0;i<n;i++){
int flag=0;
for(j=0;j<f;j++)
if(frame[j]==page[i]){ flag=1; hit++; break; }
if(flag==0){
frame[count%f]=page[i];
count++;
printf("\nFIFO Page Faults: %d", n-hit);
printf("\nFIFO Hit Ratio: %.2f", (float)hit/n);
printf("\nFIFO Miss Ratio: %.2f\n", (float)(n-hit)/n);
// ----- LRU -----
for(i=0;i<f;i++) frame[i]=-1;
count=0; hit=0;
for(i=0;i<n;i++){
int flag=0;
for(j=0;j<f;j++)
if(frame[j]==page[i]){ flag=1; hit++; pos[j]=i; break; }
if(flag==0){
int least=0;
for(j=1;j<f;j++)
if(pos[j]<pos[least]) least=j;
for(j=0;j<f;j++)
if(frame[j]==-1){ least=j; break; }
frame[least]=page[i];
pos[least]=i;
}
}
printf("\nLRU Page Faults: %d", n-hit);
printf("\nLRU Hit Ratio: %.2f", (float)hit/n);
printf("\nLRU Miss Ratio: %.2f\n", (float)(n-hit)/n);
// ----- OPTIMAL -----
for(i=0;i<f;i++) frame[i]=-1;
count=0; hit=0;
for(i=0;i<n;i++){
int flag=0;
for(j=0;j<f;j++)
if(frame[j]==page[i]){ flag=1; hit++; break; }
if(flag==0){
int farthest=-1, replace=-1;
for(j=0;j<f;j++){
int next=-1;
for(k=i+1;k<n;k++)
if(frame[j]==page[k]){ next=k; break; }
if(next==-1){ replace=j; break; }
if(next>farthest){ farthest=next; replace=j; }
for(j=0;j<f;j++)
if(frame[j]==-1){ replace=j; break; }
frame[replace]=page[i];
}
printf("\nOPTIMAL Page Faults: %d", n-hit);
printf("\nOPTIMAL Hit Ratio: %.2f", (float)hit/n);
printf("\nOPTIMAL Miss Ratio: %.2f\n", (float)(n-hit)/n);
return 0;