2.
FCFS:
FCFS Scheduling – Tiny Algorithm
1. Start
2. Input number of processes and their burst times
3. Set WT[0] = 0
4. For each i = 1 to n-1:
→ WT[i] = WT[i-1] + BT[i-1]
5. For each i = 0 to n-1:
→ TAT[i] = WT[i] + BT[i]
6. Display WT and TAT
7. Stop
FCFS Scheduling – Shortest C Program
#include <stdio.h>
int main() {
int n, i, bt[10], wt = 0, tat = 0;
printf("Enter no. of processes: ");
scanf("%d", &n);
for (i = 0; i < n; i++) scanf("%d", &bt[i]);
printf("P\tBT\tWT\tTAT\n");
for (i = 0; i < n; i++) {
printf("P%d\t%d\t%d\t%d\n", i+1, bt[i], wt, wt + bt[i]);
tat += wt + bt[i];
wt += bt[i];
}
printf("Avg TAT = %.2f\n", (float)tat / n);
return 0;
}
Input:
Enter no. of processes: 3
538
Output:
P BT WT TAT
P1 5 0 5
P2 3 5 8
P3 8 8 16
Avg TAT = 9.67
SJF:
Shortest Job First (SJF) Scheduling – Small Algorithm
1. Start
2. Input n and burst times BT[i]
3. Sort burst times in ascending order
4. Set WT[0] = 0
5. For each process i = 1 to n-1:
→ WT[i] = WT[i-1] + BT[i-1]
6. For each process i = 0 to n-1:
→ TAT[i] = WT[i] + BT[i]
7. Display P, BT, WT, and TAT
8. Stop
Super Short SJF Scheduling C Program
#include <stdio.h>
int main() {
int n, i, j, bt[10], wt[10], tat[10], temp;
scanf("%d", &n);
for (i = 0; i < n; i++) scanf("%d", &bt[i]);
// Sort burst times
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (bt[i] > bt[j]) { temp = bt[i]; bt[i] = bt[j]; bt[j] = temp; }
}
}
wt[0] = 0;
for (i = 1; i < n; i++) wt[i] = wt[i - 1] + bt[i - 1];
for (i = 0; i < n; i++) {
tat[i] = wt[i] + bt[i];
printf("P%d\t%d\t%d\t%d\n", i + 1, bt[i], wt[i], tat[i]);
}
return 0;
}
Sample Input & Output
Input:
4
6873
Output:
P1 3 0 3
P2 6 3 9
P3 7 9 16
P4 8 16 24
Priority scheduling:
Priority Scheduling – Tiny Algorithm
1. Start
2. Input n, burst times BT[i], and priorities P[i]
3. Sort processes based on priority (lower priority number = higher priority)
4. Set WT[0] = 0
5. For each i = 1 to n-1:
→ WT[i] = WT[i-1] + BT[i-1]
6. Calculate TAT[i] = WT[i] + BT[i]
7. Display P, BT, Priority, WT, and TAT
8. Stop
Priority Scheduling – Short C Program
#include <stdio.h>
int main() {
int n, i, j, bt[10], wt[10], tat[10], pr[10], temp;
scanf("%d", &n);
for (i = 0; i < n; i++) scanf("%d %d", &bt[i], &pr[i]);
// Sort by priority
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (pr[i] > pr[j]) {
temp = pr[i]; pr[i] = pr[j]; pr[j] = temp;
temp = bt[i]; bt[i] = bt[j]; bt[j] = temp;
}
}
}
wt[0] = 0;
for (i = 1; i < n; i++) wt[i] = wt[i - 1] + bt[i - 1];
for (i = 0; i < n; i++) {
tat[i] = wt[i] + bt[i];
printf("P%d\t%d\t%d\t%d\t%d\n", i + 1, bt[i], pr[i], wt[i], tat[i]);
}
return 0;
}
Sample Input & Output
Input:
4
61
83
72
34
Output:
P1 6 1 0 6
P3 7 2 6 13
P2 8 3 13 21
P4 3 4 21 24
Round Robin:
Round Robin Scheduling – Ultra Simplified Algorithm
1. Start
2. Input n (number of processes), burst times BT[], and time quantum TQ
3. Repeat until all processes finish: → Subtract TQ from each process's remaining
burst time
4. Calculate and display waiting and turnaround times
5. Stop
Ultra Small Round Robin Scheduling – C Program
#include <stdio.h>
int main() {
int n, tq, i, bt[10], rem_bt[10], wt[10] = {0};
scanf("%d %d", &n, &tq);
for (i = 0; i < n; i++) {
scanf("%d", &bt[i]);
rem_bt[i] = bt[i];
}
int time = 0, done;
do {
done = 1;
for (i = 0; i < n; i++) {
if (rem_bt[i] > 0) {
done = 0;
if (rem_bt[i] <= tq) time += rem_bt[i], wt[i] = time - bt[i], rem_bt[i] = 0;
else rem_bt[i] -= tq, time += tq;
}
}
} while (!done);
for (i = 0; i < n; i++)
printf("P%d: WT = %d, TAT = %d\n", i+1, wt[i], wt[i] + bt[i]);
return 0;
}
Sample Input & Output
Input:
44
6873
Output:
P1: WT = 2, TAT = 8
P2: WT = 6, TAT = 14
P3: WT = 7, TAT = 14
P4: WT = 2, TAT = 5
3. Inter Process Communication Strategy
Simplified Algorithm
1. Start
2. Use shmget() to create shared memory.
3. Use shmat() to attach shared memory to process.
4. Write data (Producer) or read data (Consumer).
5. Detach with shmdt() and remove shared memory with shmctl().
6. Stop
Shortest C Program for IPC using Shared Memory
Producer Program:
#include <stdio.h>
#include <sys/ipc.h>
#include <sys/shm.h>
int main() {
int shmid = shmget(1234, 1024, 0666 | IPC_CREAT);
char *shm_ptr = (char*) shmat(shmid, NULL, 0);
printf("Enter data: ");
fgets(shm_ptr, 1024, stdin);
shmdt(shm_ptr);
return 0;
}
Consumer Program:
#include <stdio.h>
#include <sys/ipc.h>
#include <sys/shm.h>
int main() {
int shmid = shmget(1234, 1024, 0666);
char *shm_ptr = (char*) shmat(shmid, NULL, 0);
printf("Data: %s", shm_ptr);
shmdt(shm_ptr);
shmctl(shmid, IPC_RMID, NULL);
return 0;
}
Sample Input & Output
Producer Input:
Hello IPC!
Consumer Output:
Data: Hello IPC!
4. implement mutusl excludion by semapahore
Here is a short and understandable version of the Producer-Consumer problem using
semaphores:
Simplified Algorithm
1. Initialize two semaphores: empty (for empty slots) and full (for full slots).
2. Producer:
o Wait for an empty slot (empty semaphore).
o Produce an item and place it in the buffer.
o Signal that a full slot is available (full semaphore).
3. Consumer:
o Wait for a full slot (full semaphore).
o Consume an item from the buffer.
o Signal that an empty slot is available (empty semaphore).
4. Repeat.
Short and Understandable C Program
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#define MAX 5
int buffer[MAX], in = 0, out = 0; // Buffer and pointers
sem_t empty, full; // Semaphores for empty and full slots
// Producer function
void* producer(void* arg) {
while(1) {
sem_wait(&empty); // Wait for an empty slot
buffer[in] = rand() % 100; // Produce an item (random number)
printf("Produced: %d\n", buffer[in]);
in = (in + 1) % MAX; // Update the producer index
sem_post(&full); // Signal that a full slot is available
sleep(1);
}
}
// Consumer function
void* consumer(void* arg) {
while(1) {
sem_wait(&full); // Wait for a full slot
printf("Consumed: %d\n", buffer[out]); // Consume the item
out = (out + 1) % MAX; // Update the consumer index
sem_post(&empty); // Signal that an empty slot is available
sleep(1);
}
}
int main() {
pthread_t prod, cons;
// Initialize semaphores
sem_init(&empty, 0, MAX); // Initially, all slots are empty
sem_init(&full, 0, 0); // Initially, no slots are full
// Create producer and consumer threads
pthread_create(&prod, NULL, producer, NULL);
pthread_create(&cons, NULL, consumer, NULL);
// Wait for threads to complete
pthread_join(prod, NULL);
pthread_join(cons, NULL);
// Destroy semaphores
sem_destroy(&empty);
sem_destroy(&full);
return 0;
}
Sample Output
Produced: 54
Consumed: 54
Produced: 23
Consumed: 23
...
Explanation:
• Producer creates an item and places it in the buffer, then signals that a full slot is
available.
• Consumer waits for a full slot, consumes the item, and then signals that an empty
slot is available.
• Semaphores are used to synchronize the processes and manage the buffer slots.
5A. Banker algorithm to avoid dealock
Here's the most compact version of the Banker's Algorithm:
Minimal C Program
#include <stdio.h>
#include <stdbool.h>
#define P 5
#define R 3
int available[] = {3, 3, 2}, max[P][R] = {{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}},
alloc[P][R] = {{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}}, need[P][R];
void calcNeed() { for (int i = 0; i < P; i++) for (int j = 0; j < R; j++) need[i][j] =
max[i][j] - alloc[i][j]; }
bool isSafe() {
int work[R]; bool finish[P] = {0};
for (int i = 0; i < R; i++) work[i] = available[i];
for (int count = 0; count < P; ) {
bool progress = 0;
for (int i = 0; i < P; i++) if (!finish[i]) {
bool canRun = 1;
for (int j = 0; j < R; j++) if (need[i][j] > work[j]) { canRun = 0; break; }
if (canRun) { for (int j = 0; j < R; j++) work[j] += alloc[i][j]; finish[i] = 1;
count++; progress = 1; }
}
if (!progress) return 0;
}
return 1;
}
int main() {
calcNeed();
int req[] = {1, 0, 2}, process = 1;
if (req[0] <= available[0] && req[1] <= available[1] && req[2] <= available[2]) {
for (int i = 0; i < R; i++) {
available[i] -= req[i];
alloc[process][i] += req[i];
need[process][i] -= req[i];
}
printf(isSafe() ? "Request granted.\n" : "Request denied.\n");
} else printf("Request denied.\n");
return 0;
}
Explanation:
• calcNeed(): Calculates the need matrix.
• isSafe(): Checks if the system remains in a safe state after the request.
• Request Handling: Verifies if the request can be granted and checks the safe state.
Sample Output:
Request granted.
5B. deadlock detection algorithm
Here’s an extremely compact version of the Deadlock Detection algorithm in C:
Minimal Deadlock Detection C Program
#include <stdio.h>
#define P 5
#define R 3
int available[] = {3, 3, 2}, alloc[P][R] = {{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}},
max[P][R] = {{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}, need[P][R];
void calcNeed() { for (int i = 0; i < P; i++) for (int j = 0; j < R; j++) need[i][j] =
max[i][j] - alloc[i][j]; }
int deadlock() {
int work[R]; bool finish[P] = {0};
for (int i = 0; i < R; i++) work[i] = available[i];
for (int count = 0; count < P;) {
int progress = 0;
for (int i = 0; i < P; i++) if (!finish[i]) {
int canRun = 1;
for (int j = 0; j < R; j++) if (need[i][j] > work[j]) { canRun = 0; break; }
if (canRun) { for (int j = 0; j < R; j++) work[j] += alloc[i][j]; finish[i] = 1;
count++; progress = 1; }
}
if (!progress) return 1;
}
return 0;
}
int main() { calcNeed(); printf(deadlock() ? "Deadlock\n" : "No deadlock\n"); return
0; }
Explanation:
• calcNeed(): Calculates the Need matrix.
• deadlock(): Detects deadlock by checking if any process cannot finish.
• Main: Calculates the need and prints if there's deadlock or not.
Sample Output:
Deadlock
7. Implement threading
Here’s a shorter C program for Threading and Synchronization along with a
simple algorithm and output:
Short C Program for Threading and Synchronization
#include <stdio.h>
#include <pthread.h>
pthread_mutex_t lock;
int counter = 0;
void* increment(void* arg) {
pthread_mutex_lock(&lock);
counter++;
pthread_mutex_unlock(&lock);
return NULL;
}
int main() {
pthread_t threads[5];
pthread_mutex_init(&lock, NULL);
for (int i = 0; i < 5; i++) pthread_create(&threads[i], NULL, increment, NULL);
for (int i = 0; i < 5; i++) pthread_join(threads[i], NULL);
printf("Counter: %d\n", counter);
pthread_mutex_destroy(&lock);
return 0;
}
Short Algorithm:
1. Initialize Mutex: Use pthread_mutex_init() to initialize the mutex.
2. Create Threads: Use pthread_create() to create threads. Each thread increments
the counter.
3. Lock and Unlock Mutex: Use pthread_mutex_lock() and
pthread_mutex_unlock() to synchronize access to the shared resource (counter).
4. Wait for Threads: Use pthread_join() to wait for all threads to finish.
5. Destroy Mutex: Use pthread_mutex_destroy() to destroy the mutex after use.
Sample Output:
Counter: 5
8.Paging technique
Here’s an even more concise version of the Paging Techniques program with a
simple algorithm:
Minimal C Program for Paging Techniques
#include <stdio.h>
int pageTable[4] = {-1, -1, -1, -1}; // Page Table
int memory[4] = {0}; // Physical Memory
void accessMemory(int page) {
if (pageTable[page] == -1) {
for (int i = 0; i < 4; i++) {
if (memory[i] == 0) {
pageTable[page] = i;
memory[i] = page;
printf("Page %d loaded into frame %d\n", page, i);
return;
}
}
}
printf("Accessing page %d in frame %d\n", page, pageTable[page]);
}
int main() {
accessMemory(2);
accessMemory(1);
accessMemory(2);
return 0;
}
Simple Algorithm:
1. Initialize Page Table: Set all entries in the page table to -1 (not in memory).
2. Access Memory:
o If the page is not in memory (pageTable[page] == -1), find an empty frame
and load the page.
o If the page is in memory, access the corresponding frame.
3. Output: Print which page is loaded or accessed.
Sample Output:
Page 2 loaded into frame 0
Page 1 loaded into frame 1
Accessing page 2 in frame 0
