C Implementations of Core OS Algorithms and Concepts
Operating System Concepts: C Code Implementations
1. Process Management and Inter-Process Communication (IPC)
1a. Process Creation using fork()
This program demonstrates the creation of a child process using the fork() system call and distinguishes between the parent and child processes.
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
int main() {
pid_t pid, mypid, myppid;
pid = getpid();
printf("Before fork: Process id is %d\n", pid);
pid = fork();
if (pid < 0) {
perror("fork() failure\n");
return 1;
}
if (pid == 0) { // Child process
printf("This is child process\n");
mypid = getpid();
myppid = getppid();
printf("Process id is %d and PPID is %d\n", mypid, myppid);
} else { // Parent process
sleep(2);
printf("This is parent process\n");
mypid = getpid();
myppid = getppid();
printf("Process id is %d and PPID is %d\n", mypid, myppid);
printf("Newly created process id or child pid is %d\n", pid);
}
return 0;
}1b. Process Replacement using execv()
This example shows how execv() replaces the current process image (example.c) with a new one (hello.c).
example.c
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
printf("PID of example.c = %d\n", getpid());
char *args[] = {"Hello", "C", "Programming", NULL};
execv("./hello", args);
// This line is only reached if execv fails
printf("Back to example.c");
return 0;
}hello.c
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
printf("We are in Hello.c\n");
printf("PID of hello.c = %d\n", getpid());
return 0;
}1c. Parent Waiting for Child using wait()
The wait() system call ensures that the parent process pauses execution until one of its children terminates.
#include <unistd.h>
#include <sys/types.h>
#include <stdio.h>
#include <sys/wait.h>
int main() {
pid_t p;
printf("before fork\n");
p = fork();
if (p == 0) {
printf("I am child having id %d\n", getpid());
printf("My parent's id is %d\n", getppid());
} else {
wait(NULL);
printf("My child's id is %d\n", p);
printf("I am parent having id %d\n", getpid());
}
printf("Common\n");
return 0;
}2. CPU Scheduling Algorithms
2a. First Come, First Served (FCFS) Scheduling
#include <stdio.h>
int main() {
int bt[20], wt[20], tat[20], i, n;
float wtavg, tatavg;
printf("\nEnter the number of processes -- ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
printf("\nEnter Burst Time for Process %d -- ", i);
scanf("%d", &bt[i]);
}
wt[0] = wtavg = 0;
tat[0] = tatavg = bt[0];
for (i = 1; i < n; i++) {
wt[i] = wt[i-1] + bt[i-1];
tat[i] = tat[i-1] + bt[i];
wtavg = wtavg + wt[i];
tatavg = tatavg + tat[i];
}
printf("\n\tPROCESS\t\tBURST TIME\tWAITING TIME\tTURNAROUND TIME\n");
for (i = 0; i < n; i++) {
printf("\n\t P%d \t\t %d \t\t %d \t\t %d", i, bt[i], wt[i], tat[i]);
}
printf("\n\nAverage Waiting Time -- %f", wtavg / n);
printf("\nAverage Turnaround Time -- %f", tatavg / n);
return 0;
}2b. Shortest Job First (SJF) Scheduling
#include <stdio.h>
int main() {
int bt[20], p[20], wt[20], tat[20], i, j, n, total = 0, totalT = 0, pos, temp;
float avg_wt, avg_tat;
printf("Enter number of processes:");
scanf("%d", &n);
printf("\nEnter Burst Time:\n");
for (i = 0; i < n; i++) {
printf("p%d:", i + 1);
scanf("%d", &bt[i]);
p[i] = i + 1; // Process ID initialization
}
// Sorting processes based on Burst Time (SJF)
for (i = 0; i < n; i++) {
pos = i;
for (j = i + 1; j < n; j++) {
if (bt[j] < bt[pos])
pos = j;
}
// Swap Burst Time
temp = bt[i];
bt[i] = bt[pos];
bt[pos] = temp;
// Swap Process ID
temp = p[i];
p[i] = p[pos];
p[pos] = temp;
}
// Calculate Waiting Time
wt[0] = 0;
for (i = 1; i < n; i++) {
wt[i] = 0;
for (j = 0; j < i; j++)
wt[i] += bt[j];
total += wt[i];
}
avg_wt = (float)total / n;
printf("\nProcess\t Burst Time \tWaiting Time\tTurnaround Time");
// Calculate Turnaround Time and print results
for (i = 0; i < n; i++) {
tat[i] = bt[i] + wt[i];
totalT += tat[i];
printf("\np%d\t\t %d\t\t %d\t\t\t%d", p[i], bt[i], wt[i], tat[i]);
}
avg_tat = (float)totalT / n;
printf("\n\nAverage Waiting Time=%f", avg_wt);
printf("\nAverage Turnaround Time=%f", avg_tat);
return 0;
}2c. Round Robin (RR) Scheduling
#include <stdio.h>
int main() {
int n;
printf("Enter Total Number of Processes:");
scanf("%d", &n);
int burst_time[n]; // Original burst time
int wait_time = 0, ta_time = 0, arr_time[n], temp_burst_time[n];
int x = n; // Number of remaining processes
for (int i = 0; i < n; i++) {
printf("Enter Details of Process %d \n", i + 1);
printf("Arrival Time: ");
scanf("%d", &arr_time[i]);
printf("Burst Time: ");
scanf("%d", &burst_time[i]);
temp_burst_time[i] = burst_time[i];
}
int time_slot;
printf("Enter Time Slot (Quantum):");
scanf("%d", &time_slot);
int total = 0, counter = 0, i; // 'total' acts as current time
printf("\nProcess ID\tBurst Time\tTurnaround Time\tWaiting Time\n");
for (total = 0, i = 0; x != 0; ) {
if (temp_burst_time[i] <= time_slot && temp_burst_time[i] > 0) {
total = total + temp_burst_time[i];
temp_burst_time[i] = 0;
counter = 1;
} else if (temp_burst_time[i] > 0) {
temp_burst_time[i] = temp_burst_time[i] - time_slot;
total += time_slot;
}
// Process completion check
if (temp_burst_time[i] == 0 && counter == 1) {
x--;
int turnaround_time = total - arr_time[i];
int waiting_time = turnaround_time - burst_time[i];
printf("P%d\t\t %d\t\t %d\t\t\t %d\n", i + 1, burst_time[i], turnaround_time, waiting_time);
wait_time += waiting_time;
ta_time += turnaround_time;
counter = 0;
}
// Context switching logic
if (i == n - 1) {
i = 0;
} else if (arr_time[i + 1] <= total) {
i++;
} else {
i = 0;
}
}
float average_wait_time = wait_time * 1.0 / n;
float average_turnaround_time = ta_time * 1.0 / n;
printf("\nAverage Waiting Time: %f", average_wait_time);
printf("\nAverage Turnaround Time: %f", average_turnaround_time);
return 0;
}2d. Priority Scheduling Algorithm
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int main() {
int n;
printf("Enter Number of Processes: ");
scanf("%d", &n);
int b[n], p[n], index[n]; // b: burst time, p: priority, index: process ID
for (int i = 0; i < n; i++) {
printf("Enter Burst Time and Priority Value for Process %d: ", i + 1);
scanf("%d %d", &b[i], &p[i]);
index[i] = i + 1;
}
// Sorting based on Priority (Higher number = Higher Priority assumed)
for (int i = 0; i < n; i++) {
int a = p[i], m = i;
for (int j = i; j < n; j++) {
if (p[j] > a) {
a = p[j];
m = j;
}
}
// Swap priority, burst time, and index
swap(&p[i], &p[m]);
swap(&b[i], &b[m]);
swap(&index[i], &index[m]);
}
int t = 0; // Current time
printf("\nOrder of Process Execution is:\n");
for (int i = 0; i < n; i++) {
printf("P%d is executed from %d to %d\n", index[i], t, t + b[i]);
t += b[i];
}
printf("\nProcess ID\tBurst Time\tWait Time\tTurn Around Time\n");
int wait_time = 0;
for (int i = 0; i < n; i++) {
int turnaround_time = wait_time + b[i];
printf("P%d\t\t %d\t\t %d\t\t %d\n", index[i], b[i], wait_time, turnaround_time);
wait_time += b[i];
}
return 0;
}3. Synchronization: Producer-Consumer Problem
3. Producer-Consumer Simulation using Semaphores
This program simulates the classic Producer-Consumer problem using integer variables to represent semaphores (mutex, full, empty).
#include <stdio.h>
#include <stdlib.h>
int mutex = 1;
int full = 0;
int empty = 10, data = 0;
void producer() {
--mutex;
++full;
--empty;
data++;
printf("\nProducer produces item number: %d\n", data);
++mutex;
}
void consumer() {
--mutex;
--full;
++empty;
printf("\nConsumer consumes item number: %d.\n", data);
data--;
++mutex;
}
int main() {
int n, i;
printf("\n1. Enter 1 for Producer\n2. Enter 2 for Consumer\n3. Enter 3 to Exit");
for (i = 1; i > 0; i++) {
printf("\nEnter your choice: ");
scanf("%d", &n);
switch (n) {
case 1:
if ((mutex == 1) && (empty != 0)) {
producer();
} else {
printf("The Buffer is full. New data cannot be produced!");
}
break;
case 2:
if ((mutex == 1) && (full != 0)) {
consumer();
} else {
printf("The Buffer is empty! New data cannot be consumed!");
}
break;
case 3:
exit(0);
break;
}
}
return 0;
}4. Inter-Process Communication (IPC) using Named Pipes (FIFO)
4a. FIFO Writer Process
#include <stdio.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
int main() {
int fd;
char *myfifo = "/tmp/myfifo";
// Create the FIFO (Named Pipe)
mkfifo(myfifo, 0666);
printf("Run Reader process to read the FIFO File\n");
// Open FIFO for writing (O_WRONLY blocks until a reader opens it)
fd = open(myfifo, O_WRONLY);
write(fd, "Hi", sizeof("Hi")); // write "Hi" to the FIFO
close(fd);
unlink(myfifo); // remove the FIFO file system entry
return 0;
}4b. FIFO Reader Process
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#define MAX_BUF 1024
int main() {
int fd;
char *myfifo = "/tmp/myfifo";
char buf[MAX_BUF];
// Open FIFO for reading (O_RDONLY blocks until a writer opens it)
fd = open(myfifo, O_RDONLY);
read(fd, buf, MAX_BUF);
printf("Writer: %s\n", buf);
close(fd);
return 0;
}5. Deadlock Avoidance: Banker’s Algorithm
5a. Safety Algorithm Implementation
This program determines if the system is currently in a safe state by finding a safe sequence of process execution.
#include <stdio.h>
#include <stdbool.h>
#define MAX_PROCESSES 5
#define MAX_RESOURCES 3
int available[MAX_RESOURCES];
int maximum[MAX_PROCESSES][MAX_RESOURCES];
int allocation[MAX_PROCESSES][MAX_RESOURCES];
int need[MAX_PROCESSES][MAX_RESOURCES];
bool isSafe(int processes, int resources) {
int work[MAX_RESOURCES];
bool finish[MAX_PROCESSES] = {false};
int safeSequence[MAX_PROCESSES];
int count = 0;
// Initialize Work vector
for (int i = 0; i < resources; i++) {
work[i] = available[i];
}
while (count < processes) {
bool found = false;
for (int i = 0; i < processes; i++) {
if (!finish[i]) {
bool canProceed = true;
// Check if Need <= Work
for (int j = 0; j < resources; j++) {
if (need[i][j] > work[j]) {
canProceed = false;
break;
}
}
if (canProceed) {
// Work = Work + Allocation
for (int k = 0; k < resources; k++) {
work[k] += allocation[i][k];
}
safeSequence[count++] = i;
finish[i] = true;
found = true;
}
}
}
if (!found) {
printf("The system is not in a safe state.\n");
return false;
}
}
printf("The system is in a safe state.\n");
printf("Safe sequence: ");
for (int i = 0; i < processes; i++) {
printf("P%d ", safeSequence[i]);
}
printf("\n");
return true;
}
int main() {
int processes = MAX_PROCESSES;
int resources = MAX_RESOURCES;
printf("Enter the available resources (R1 R2 R3): ");
for (int i = 0; i < resources; i++) {
scanf("%d", &available[i]);
}
printf("Enter the maximum resources matrix for each process:\n");
for (int i = 0; i < processes; i++) {
printf("Process %d: ", i);
for (int j = 0; j < resources; j++) {
scanf("%d", &maximum[i][j]);
}
}
printf("Enter the allocation matrix for each process:\n");
for (int i = 0; i < processes; i++) {
printf("Process %d: ", i);
for (int j = 0; j < resources; j++) {
scanf("%d", &allocation[i][j]);
need[i][j] = maximum[i][j] - allocation[i][j]; // Calculate need matrix
}
}
printf("\nInitial State:\n");
printf("Available Resources: ");
for (int i = 0; i < resources; i++) {
printf("%d ", available[i]);
}
printf("\n");
printf("Need Matrix:\n");
for (int i = 0; i < processes; i++) {
for (int j = 0; j < resources; j++) {
printf("%d ", need[i][j]);
}
printf("\n");
}
if (isSafe(processes, resources)) {
printf("The system can proceed safely.\n");
} else {
printf("The system cannot proceed safely, deadlock may occur.\n");
}
return 0;
}5b. Resource Request Algorithm Implementation
This extension of the Banker’s Algorithm checks if a new resource request can be granted without leading to an unsafe state.
#include <stdio.h>
#include <stdbool.h>
#define MAX_PROCESSES 5
#define MAX_RESOURCES 3
int available[MAX_RESOURCES];
int maximum[MAX_PROCESSES][MAX_RESOURCES];
int allocation[MAX_PROCESSES][MAX_RESOURCES];
int need[MAX_PROCESSES][MAX_RESOURCES];
// Helper function to check for a safe state
bool isSafe(int processes, int resources) {
int work[MAX_RESOURCES];
bool finish[MAX_PROCESSES] = {false};
int safeSequence[MAX_PROCESSES];
int count = 0;
for (int i = 0; i < resources; i++) {
work[i] = available[i];
}
while (count < processes) {
bool found = false;
for (int i = 0; i < processes; i++) {
if (!finish[i]) {
bool canProceed = true;
for (int j = 0; j < resources; j++) {
if (need[i][j] > work[j]) {
canProceed = false;
break;
}
}
if (canProceed) {
for (int k = 0; k < resources; k++) {
work[k] += allocation[i][k];
}
safeSequence[count++] = i;
finish[i] = true;
found = true;
}
}
}
if (!found) {
return false;
}
}
printf("The system is in a safe state.\nSafe sequence: ");
for (int i = 0; i < processes; i++) {
printf("P%d ", safeSequence[i]);
}
printf("\n");
return true;
}
bool requestResources(int processID, int request[], int processes, int resources) {
// Step 1: Check if Request <= Need
for (int i = 0; i < resources; i++) {
if (request[i] > need[processID][i]) {
printf("Error: Process has exceeded its maximum claim (Request > Need).\n");
return false;
}
}
// Step 2: Check if Request <= Available
for (int i = 0; i < resources; i++) {
if (request[i] > available[i]) {
printf("Error: Not enough resources available (Request > Available).\n");
return false;
}
}
// Step 3: Tentatively allocate resources
for (int i = 0; i < resources; i++) {
available[i] -= request[i];
allocation[processID][i] += request[i];
need[processID][i] -= request[i];
}
// Step 4: Check for safety
if (isSafe(processes, resources)) {
printf("Resources allocated successfully to Process %d.\n", processID);
return true;
} else {
// Step 5: Rollback
printf("Unsafe state detected! Rolling back resource allocation.\n");
for (int i = 0; i < resources; i++) {
available[i] += request[i];
allocation[processID][i] -= request[i];
need[processID][i] += request[i];
}
return false;
}
}
int main() {
int processes = MAX_PROCESSES;
int resources = MAX_RESOURCES;
printf("Enter the available resources (R1 R2 R3): ");
for (int i = 0; i < resources; i++) {
scanf("%d", &available[i]);
}
printf("Enter the maximum resources matrix for each process:\n");
for (int i = 0; i < processes; i++) {
printf("Process %d: ", i);
for (int j = 0; j < resources; j++) {
scanf("%d", &maximum[i][j]);
}
}
printf("Enter the allocation matrix for each process:\n");
for (int i = 0; i < processes; i++) {
printf("Process %d: ", i);
for (int j = 0; j < resources; j++) {
scanf("%d", &allocation[i][j]);
need[i][j] = maximum[i][j] - allocation[i][j]; // Calculate the need matrix
}
}
printf("\nInitial State:\n");
printf("Available Resources: ");
for (int i = 0; i < resources; i++) {
printf("%d ", available[i]);
}
printf("\n");
printf("Need Matrix:\n");
for (int i = 0; i < processes; i++) {
for (int j = 0; j < resources; j++) {
printf("%d ", need[i][j]);
}
printf("\n");
}
int processID;
int request[MAX_RESOURCES];
printf("\nEnter the process ID requesting resources (0 to %d): ", processes - 1);
scanf("%d", &processID);
printf("Enter the requested resources (R1 R2 R3): ");
for (int i = 0; i < resources; i++) {
scanf("%d", &request[i]);
}
if (requestResources(processID, request, processes, resources)) {
printf("Request granted.\n");
} else {
printf("Request denied.\n");
}
return 0;
}6. Memory Management Allocation Schemes
6a. First Fit Algorithm
#include <stdio.h>
#define max 25
int main() {
int frag[max], b[max], f[max], i, j, nb, nf, temp;
static int bf[max], ff[max]; // bf: block flag, ff: file fits block
printf("\n\tMemory Management Scheme - First Fit");
printf("\nEnter the number of blocks:");
scanf("%d", &nb);
printf("Enter the number of files:");
scanf("%d", &nf);
printf("\nEnter the size of the blocks:-\n");
for (i = 1; i <= nb; i++) {
printf("Block %d:", i);
scanf("%d", &b[i]);
}
printf("Enter the size of the files :-\n");
for (i = 1; i <= nf; i++) {
printf("File %d:", i);
scanf("%d", &f[i]);
}
for (i = 1; i <= nf; i++) {
for (j = 1; j <= nb; j++) {
if (bf[j] != 1) {
temp = b[j] - f[i];
if (temp >= 0) {
ff[i] = j;
break;
}
}
}
if (ff[i] != 0) { // Check if a block was found
frag[i] = temp;
bf[ff[i]] = 1;
} else {
frag[i] = -1; // Indicate no fit
}
}
printf("\nFile No:\tFile Size:\tBlock No:\tBlock Size:\tFragment\n");
for (i = 1; i <= nf; i++) {
if (ff[i] != 0) {
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", i, f[i], ff[i], b[ff[i]], frag[i]);
} else {
printf("%d\t\t%d\t\tN/A\t\tN/A\t\tN/A (No Fit)\n", i, f[i]);
}
}
return 0;
}6b. Best Fit Algorithm
#include <stdio.h>
#define max 25
int main() {
int frag[max], b[max], f[max], i, j, nb, nf, temp, lowest = 10000;
static int bf[max], ff[max];
printf("\n\tMemory Management Scheme - Best Fit");
printf("\nEnter the number of blocks:");
scanf("%d", &nb);
printf("Enter the number of files:");
scanf("%d", &nf);
printf("\nEnter the size of the blocks:-\n");
for (i = 1; i <= nb; i++) {
printf("Block %d:", i);
scanf("%d", &b[i]);
}
printf("Enter the size of the files :-\n");
for (i = 1; i <= nf; i++) {
printf("File %d:", i);
scanf("%d", &f[i]);
}
for (i = 1; i <= nf; i++) {
for (j = 1; j <= nb; j++) {
if (bf[j] != 1) {
temp = b[j] - f[i];
if (temp >= 0) {
if (lowest > temp) {
ff[i] = j;
lowest = temp;
}
}
}
}
if (ff[i] != 0) { // Check if a block was found
frag[i] = lowest;
bf[ff[i]] = 1;
} else {
frag[i] = -1;
}
lowest = 10000;
}
printf("\nFile No\tFile Size \tBlock No\tBlock Size\tFragment\n");
for (i = 1; i <= nf; i++) {
if (ff[i] != 0) {
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", i, f[i], ff[i], b[ff[i]], frag[i]);
} else {
printf("%d\t\t%d\t\tN/A\t\tN/A\t\tN/A (No Fit)\n", i, f[i]);
}
}
return 0;
}6c. Worst Fit Algorithm
#include <stdio.h>
#define max 25
int main() {
int frag[max], b[max], f[max], i, j, nb, nf, temp, highest = 0;
static int bf[max], ff[max];
printf("\n\tMemory Management Scheme - Worst Fit");
printf("\nEnter the number of blocks:");
scanf("%d", &nb);
printf("Enter the number of files:");
scanf("%d", &nf);
printf("\nEnter the size of the blocks:-\n");
for (i = 1; i <= nb; i++) {
printf("Block %d:", i);
scanf("%d", &b[i]);
}
printf("Enter the size of the files :-\n");
for (i = 1; i <= nf; i++) {
printf("File %d:", i);
scanf("%d", &f[i]);
}
for (i = 1; i <= nf; i++) {
for (j = 1; j <= nb; j++) {
if (bf[j] != 1) {
temp = b[j] - f[i];
if (temp >= 0) {
if (highest < temp) {
ff[i] = j;
highest = temp;
}
}
}
}
if (ff[i] != 0) { // Check if a block was found
frag[i] = highest;
bf[ff[i]] = 1;
} else {
frag[i] = -1;
}
highest = 0;
}
printf("\nFile No:\tFile Size:\tBlock No:\tBlock Size:\tFragment\n");
for (i = 1; i <= nf; i++) {
if (ff[i] != 0) {
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", i, f[i], ff[i], b[ff[i]], frag[i]);
} else {
printf("%d\t\t%d\t\tN/A\t\tN/A\t\tN/A (No Fit)\n", i, f[i]);
}
}
return 0;
}