SHRI G.P.M.

DEGREE COLLEGE OF SCIENCE & COMMERCE

Department of Computer
Affiliated to University of Mumbai

Experiment No.—1A : Producer-consumer problem using shared memory

Aim:

To implement the Producer-Consumer problem using shared memory in C and understand inter-
process communication and synchronization using semaphores.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the concept of the Producer-Consumer problem in operating systems.

2. Learn how shared memory facilitates communication between processes.

3. Apply semaphores for synchronization to avoid race conditions.

4. Write and execute a C program that demonstrates process coordination.

5. Analyze the behavior of concurrent processes in a controlled environment.

Theory:

1. Introduction
The Producer-Consumer problem is a classical example of process synchronization in
operating systems.
It illustrates how two types of processes—producers and consumers—share a common
buffer in a coordinated way to prevent conflicts.
This experiment demonstrates shared memory for inter-process communication and
semaphores for synchronization, ensuring that producers do not overwrite unconsumed data
and consumers do not read empty buffer slots.
The fork() system call enables concurrent execution of producer and consumer processes,
while semaphores ensure mutual exclusion and orderly execution.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2. Numbered Theory Sections

2.1 Producer-Consumer Concept

• Definition: The Producer-Consumer problem involves coordinating producer and

consumer processes to share a limited-size buffer without conflict.
• Key Points:
1. Producer: Generates data items and inserts them into the buffer. Must wait if
the buffer is full.
2. Consumer: Removes data items from the buffer for processing. Must wait if
the buffer is empty.
3. Problem: Without proper synchronization, simultaneous access may lead to
data inconsistency, race conditions, or buffer overflow/underflow.
• Example Table – Buffer States:

Buffer Index Producer Action Consumer Action

0 Inserts item 1 Wait (empty)
1 Inserts item 2 Consumes item 1
2 Wait (full) Consumes item 2

2.2 Shared Memory

• Definition: Shared memory is a segment of memory accessible by multiple processes

for direct data exchange.
• Implementation in C:
o shmget() – Create shared memory segment.
o shmat() – Attach shared memory to a process.
o shmdt() – Detach shared memory from a process.
o shmctl() – Control operations (e.g., delete memory segment).
• Advantages:
o Fast data exchange without intermediate files.
o Direct memory access reduces communication overhead.
• Code mapping:

shmid = shmget(SHM_KEY, sizeof(SharedBuffer), IPC_CREAT | 0666);

shm = (SharedBuffer *) shmat(shmid, NULL, 0);
shmdt((void *) shm);
shmctl(shmid, IPC_RMID, NULL);
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2.3 Semaphores and Synchronization

• Definition: A semaphore is a variable used to control access to shared resources in

concurrent processes.
• Types:
o Binary Semaphore: Acts as a mutex (0 or 1).
o Counting Semaphore: Tracks multiple resources or buffer slots.
• Functions in C:
o semget() – Create semaphore set.
o semop() – Perform wait (P) or signal (V) operations.
o semctl() – Initialize or control semaphore values.
• Purpose in this experiment:
o Ensures mutual exclusion while producer and consumer access the buffer.
o Prevents race conditions and guarantees orderly execution.
• Code mapping:

semid = semget(SEM_KEY, 3, IPC_CREAT | 0666);

semctl(semid, MUTEX, SETVAL, arg);
sem_wait_op(semid, MUTEX); // Wait (P)
sem_signal_op(semid, MUTEX); // Signal (V)

2.4 Fork Function and Process Creation

• Definition: fork() creates a new child process as a copy of the parent.

• Purpose in this experiment:
o Parent process → producer
o Child process → consumer
o Both run concurrently sharing the same memory buffer.
• Code mapping:

pid_t pid = fork();

if (pid == 0) { /* consumer */ }
else { /* producer */ }

2.5 Buffer Management

• The shared buffer is implemented as a circular queue.

• Producer pointer (in) – next insertion position.
• Consumer pointer (out) – next removal position.
• Semaphores track empty and full slots.
• Example Table – Circular Buffer Movement:
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Step Buffer State Producer Index (in) Consumer Index (out)

1 Empty 0 0
2 1 item 1 0
3 2 items 2 0
4 Full 0 0

2.6 Algorithm / Flow

1. Create shared memory and initialize buffer (in = 0, out = 0).

2. Create semaphores: MUTEX = 1, EMPTY = BUFFER_SIZE, FULL = 0.
3. Fork the process into producer (parent) and consumer (child).
4. Producer process:
o Wait(EMPTY), Wait(MUTEX)
o Insert item into buffer (buffer[in] = item)
o Signal(MUTEX), Signal(FULL)
o Print item produced (printf)
5. Consumer process:
o Wait(FULL), Wait(MUTEX)
o Remove item from buffer (item = buffer[out])
o Signal(MUTEX), Signal(EMPTY)
o Print item consumed (printf)
6. Repeat steps 4–5 for all items (10 iterations in code).
7. Cleanup: detach shared memory and remove semaphores.

3. Summary

• The Producer-Consumer problem demonstrates process synchronization and inter-

process communication.
• Shared memory allows efficient data exchange.
• Semaphores ensure mutual exclusion and prevent race conditions.
• Circular buffer management avoids overflow and underflow.
• fork() enables concurrent execution of producer and consumer, while looped
production and consumption along with output statements allow observation of the
process in action.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Code:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sem.h>
#include <sys/types.h>
#include <sys/wait.h>

#define BUFFER_SIZE 10
#define SHM_KEY 0x1234
#define SEM_KEY 0x5678

// Semaphore indices
#define MUTEX 0
#define EMPTY 1
#define FULL 2

// Structure for shared buffer

typedef struct {
int buffer[BUFFER_SIZE];
int in;
int out;
} SharedBuffer;

// Union required for semctl()

union semun {
int val;
struct semid_ds *buf;
unsigned short *array;
};

// Semaphore wait (P)

void sem_wait_op(int semid, int semnum) {
struct sembuf op;
op.sem_num = semnum;
op.sem_op = -1;
op.sem_flg = 0;
semop(semid, &op, 1);
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

// Semaphore signal (V)

void sem_signal_op(int semid, int semnum) {
struct sembuf op;
op.sem_num = semnum;
op.sem_op = 1;
op.sem_flg = 0;
semop(semid, &op, 1);
}

int main() {
int shmid, semid;
SharedBuffer *shm;

// Create shared memory

shmid = shmget(SHM_KEY, sizeof(SharedBuffer), IPC_CREAT | 0666);
if (shmid == -1) {
perror("shmget failed");
exit(1);
}

// Attach shared memory

shm = (SharedBuffer *) shmat(shmid, NULL, 0);
if (shm == (void *) -1) {
perror("shmat failed");
exit(1);
}

// Initialize buffer pointers

shm->in = 0;
shm->out = 0;

// Create semaphores
semid = semget(SEM_KEY, 3, IPC_CREAT | 0666);
if (semid == -1) {
perror("semget failed");
exit(1);
}

// Initialize semaphores
union semun arg;
[Link] = 1;
semctl(semid, MUTEX, SETVAL, arg); // mutex = 1
[Link] = BUFFER_SIZE;
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

semctl(semid, EMPTY, SETVAL, arg); // empty = BUFFER_SIZE

[Link] = 0;
semctl(semid, FULL, SETVAL, arg); // full = 0

// Fork process
pid_t pid = fork();

if (pid < 0) {
perror("fork failed");
exit(1);
} else if (pid == 0) {
// Consumer Process
int i;
for (i = 0; i < 10; i++) {
sem_wait_op(semid, FULL);
sem_wait_op(semid, MUTEX);

int item = shm->buffer[shm->out];

printf("Consumer consumed: %d\n", item);
shm->out = (shm->out + 1) % BUFFER_SIZE;

sem_signal_op(semid, MUTEX);
sem_signal_op(semid, EMPTY);

sleep(1);
}
shmdt((void *) shm);
} else {
// Producer Process
int i;
for (i = 0; i < 10; i++) {
int item = i + 1;

sem_wait_op(semid, EMPTY);
sem_wait_op(semid, MUTEX);

shm->buffer[shm->in] = item;
printf("Producer produced: %d\n", item);
shm->in = (shm->in + 1) % BUFFER_SIZE;

sem_signal_op(semid, MUTEX);
sem_signal_op(semid, FULL);
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

sleep(1);
}

wait(NULL); // Wait for child to finish

// Cleanup
shmdt((void *) shm);
shmctl(shmid, IPC_RMID, NULL);
semctl(semid, 0, IPC_RMID);
}

return 0;
}

Output:
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Learning Outcomes:

1. Successfully implement inter-process communication using shared memory.

2. Correctly apply semaphores for synchronization, ensuring no race conditions occur.
3. Effectively manage a circular buffer with proper insertion (in) and removal (out) pointers.
4. Execute concurrent processes using fork(), demonstrating simultaneous producer and consumer
operations.
5. Accurately display program output showing synchronized production and consumption of items.

Course Outcomes:

Students gain a thorough understanding of process synchronization and inter-process

communication in operating systems. They learn to implement shared memory for efficient
data exchange between concurrent processes and use semaphores to prevent race
conditions. By managing a circular buffer and observing the coordinated execution of
producer and consumer processes via fork(), students develop practical skills in writing
synchronized, concurrent programs. This experiment reinforces concepts of mutual
exclusion, resource management, and orderly execution, equipping students with both
conceptual knowledge and hands-on experience applicable to more complex systems
programming tasks.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Conclusion:

Successfully implemented synchronized producer and consumer processes using shared memory and
semaphores. Efficiently managed the circular buffer, ensured orderly production and consumption,
and avoided race conditions, thereby fulfilling the aim of demonstrating a robust inter-process
communication system in C.

Viva Questions:

1. What is the Producer-Consumer problem and why is it important in operating systems?

2. How does shared memory facilitate communication between the producer and consumer
processes?
3. What is the role of semaphores in this experiment, and how do Wait (P) and Signal (V) operations
work?
4. How does the circular buffer work, and what are the roles of in and out pointers?
5. Why is the fork() system call used, and how does it help in process synchronization in this
experiment?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—1B : Producer-Consumer using Message Passing

Aim:

To implement the Producer-Consumer problem using message passing in C and understand inter-
process communication, synchronization, and coordination between processes via a message queue.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the Producer-Consumer problem and its relevance in operating systems.

2. Learn how message queues facilitate communication between processes.

3. Apply process synchronization techniques using message passing to avoid conflicts.

4. Write and execute a C program demonstrating producer and consumer coordination.

5. Analyze and observe the behavior of concurrent processes using messages.

Theory:

1. Introduction

The Producer-Consumer problem is a classical example of process synchronization in

operating systems. It demonstrates how producer and consumer processes coordinate to
share data without conflicts. Unlike shared memory, this experiment uses message queues to
exchange data between processes, ensuring synchronization and preventing data loss.

The fork() system call is used to create a consumer process, while the producer process
sends messages to the message queue. The consumer receives messages, ensuring orderly
communication.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2. Producer-Consumer & Message Passing

2.1 Producer-Consumer Concept

• Definition: Coordination of producer and consumer processes to share data using a

controlled mechanism (here, message queues).
• Key Points:
1. Producer: Creates data items and sends them as messages. Waits if the
consumer is not ready.
2. Consumer: Receives messages from the producer for processing. Waits if no
messages are available.
3. Problem: Without proper communication, messages may be lost or processed
out of order.
• Example Table – Message Flow:

Step Producer Action Consumer Action Message Queue State

1 Sends item 1 Wait (queue empty) 1 item in queue
2 Sends item 2 Receives item 1 1 item in queue
3 Sends item 3 Receives item 2 1 item in queue

2.2 Message Queues

• Definition: A message queue is a kernel-managed data structure allowing

processes to communicate by sending and receiving messages.
• Functions in C:
o msgget() – Create a new message queue or access an existing one.
o msgsnd() – Send a message to the queue.
o msgrcv() – Receive a message from the queue.
o msgctl() – Control operations on the queue (e.g., delete).
• Purpose in this Experiment:
o Facilitates inter-process communication without shared memory.
o Ensures synchronized transfer of produced items to the consumer.
• Code Mapping:

msgid = msgget(MSG_KEY, IPC_CREAT | 0666); // Create message queue

msgsnd(msgid, &msg, MSG_SIZE, 0); // Send message
msgrcv(msgid, &msg, MSG_SIZE, 1, 0); // Receive message
msgctl(msgid, IPC_RMID, NULL); // Cleanup
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2.3 Fork Function and Process Creation

• Definition: fork() creates a child process that runs concurrently with the parent
process.
• Purpose in this Experiment:
o Parent process: Producer
o Child process: Consumer
o Both execute simultaneously and communicate through the message queue.
• Code Mapping:

pid_t pid = fork();

if(pid == 0){ /* Consumer */ }
else { /* Producer */ }

2.4 Algorithm / Steps

1. Create a message queue using msgget().

2. Fork the process into producer (parent) and consumer (child).
3. Producer Process:
o Generate items.
o Send each item as a message using msgsnd().
o Print the sent item.
4. Consumer Process:
o Receive messages using msgrcv().
o Print the received item.
o Repeat until all items are consumed.
5. Cleanup: Delete the message queue using msgctl().

3. Summary

• The Producer-Consumer problem demonstrates inter-process communication and

synchronization.
• Message queues enable ordered and safe communication between processes.
• fork() allows concurrent execution of producer and consumer processes.
• Proper coordination ensures no message loss and maintains the correct sequence of
production and consumption.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/ipc.h>
#include <sys/msg.h>
#include <sys/types.h>
#include <sys/wait.h>

#define MSG_KEY 0x1234

#define MSG_SIZE sizeof(struct message) - sizeof(long)
#define NUM_ITEMS 10

// Message structure
struct message {
long msg_type;
int data;
};

int main() {
int msgid;
pid_t pid;

// Create message queue

msgid = msgget(MSG_KEY, IPC_CREAT | 0666);
if (msgid < 0) {
perror("msgget failed");
exit(1);
}

pid = fork();

if (pid < 0) {
perror("fork failed");
exit(1);
}

if (pid == 0) {
// Consumer process
struct message msg;
for (int i = 0; i < NUM_ITEMS; i++) {
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

if (msgrcv(msgid, &msg, MSG_SIZE, 1, 0) < 0) {

perror("msgrcv failed");
exit(1);
}
printf("Consumer received: %d\n", [Link]);
sleep(1);
}
} else {
// Producer process
struct message msg;
for (int i = 0; i < NUM_ITEMS; i++) {
msg.msg_type = 1;
[Link] = i + 1;
if (msgsnd(msgid, &msg, MSG_SIZE, 0) < 0) {
perror("msgsnd failed");
exit(1);
}
printf("Producer sent: %d\n", [Link]);
sleep(1);
}

wait(NULL); // Wait for consumer

// Cleanup message queue

msgctl(msgid, IPC_RMID, NULL);
}

return 0;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Output:

Learning Outcomes:

1. Successfully implement inter-process communication using message queues.

2. Correctly coordinate producer and consumer processes, ensuring synchronized message
transfer.
3. Effectively use the fork() system call to execute concurrent processes.
4. Demonstrate orderly production and consumption of data without message loss.
5. Observe and analyze the behavior of concurrent processes communicating via messages.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Course Outcomes:

Students develop a thorough understanding of process synchronization and inter-process

communication using message queues. They learn to implement a controlled communication
channel between producer and consumer processes, ensuring orderly transfer of data without loss
or conflict. By using fork() to create concurrent processes and managing message sending and
receiving, students gain practical skills in writing synchronized programs. This experiment reinforces
concepts of mutual exclusion, process coordination, and communication mechanisms, equipping
students with knowledge applicable to more advanced systems programming and concurrent
application development.

Conclusion:

Successfully implemented synchronized producer and consumer processes using message passing in
C. Efficiently coordinated message sending and receiving to maintain the correct order of data
transfer, ensured orderly production and consumption, and avoided message loss, thereby fulfilling
the aim of demonstrating a robust inter-process communication system.

Viva Questions:

1. What is the Producer-Consumer problem and why is it important in operating systems?

2. How do message queues facilitate communication between producer and consumer processes?
3. What is the role of fork() in this experiment, and how does it enable concurrent execution?
4. How does the program ensure synchronized sending and receiving of messages?
5. Why is it necessary to delete the message queue after the experiment using msgctl()?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—2A : Multithreaded Summation

Aim:

To write a multithreaded program in C that calculates the summation of non-negative integers using
the Runnable-like approach with threads, ensuring synchronized updates to a shared sum variable.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the concept of multithreading and its advantages in concurrent execution.

2. Learn how to implement threads in C using the pthread library.
3. Apply mutex locks to synchronize access to shared resources and prevent race conditions.
4. Divide computational tasks among multiple threads to achieve parallel summation.
5. Execute and observe the behavior of multithreaded programs for correctness and efficiency.

Theory:

1. Introduction
Multithreading allows a program to execute multiple threads concurrently, improving
efficiency for computational tasks. In this experiment, threads are used to calculate the
summation of non-negative integers. Each thread computes a partial sum over a specific
range, and the results are accumulated into a shared global sum. Synchronization is
maintained using a mutex, ensuring that updates to the global sum are thread-safe and free
from race conditions.

2. Multithreading

2.1 Multithreading Concept

• Definition: Multithreading is the execution of multiple threads within a single

process. Threads share memory but run independently.
• Key Points:
1. Threads execute concurrently, improving computation efficiency.
2. Shared variables require synchronization to prevent inconsistent results.
3. Each thread can perform a portion of a task (here, partial summation).
• Example Table – Thread Execution for N = 7, 8 Threads:
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Thread Range Partial Sum

T1 0–0 0
T2 1–1 1
T3 2–2 2
T4 3–3 3
T5 4–4 4
T6 5–5 5
T7 6–6 6
T8 7–7 7

2.2 Thread Data Structure and Runnable Concept

• Definition: Each thread needs parameters specifying the range of numbers it will
sum. In C, we define a structure ThreadData containing start and end.
• Code Mapping:

typedef struct {
int start;
int end;
} ThreadData;

• Runnable Interface Concept: The thread function partial_sum(void* arg) acts

as the “task” executed by each thread.

2.3 Thread Creation and Execution

• Definition: Threads are created using pthread_create(). Each thread receives a

pointer to its ThreadData.
• Code Mapping:

pthread_create(&threads[i], NULL, partial_sum, (void*) &thread_data[i]);

• Joining Threads: The main thread waits for all child threads to finish using
pthread_join().

pthread_join(threads[i], NULL);
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2.4 Mutex and Synchronization

• Definition: Mutex ensures mutual exclusion, preventing multiple threads from

updating the shared global sum simultaneously.
• Code Mapping:

pthread_mutex_lock(&sum_mutex);
global_sum += local_sum;
pthread_mutex_unlock(&sum_mutex);

• Purpose: Ensures race conditions are avoided, and the final global sum is correct.

2.5 Range Division and Work Allocation

• Logic: The total range 0…N is divided among threads to balance workload:
1. chunk_size = (N + 1) / num_threads
2. remainder = (N + 1) % num_threads
• Assignment: Threads get chunk_size numbers, and the first remainder threads
receive 1 extra number to cover all integers.
• Code Mapping:

thread_data[i].start = start;
thread_data[i].end = start + chunk_size - 1;
if (remainder > 0) {
thread_data[i].end++;
remainder--;
}
start = thread_data[i].end + 1;

2.6 Algorithm / Steps

1. Input a non-negative integer N.

2. Input the number of threads num_threads.
3. Initialize global sum to 0 and create a mutex.
4. Divide the range 0…N among threads using chunk_size and remainder.
5. Create threads and assign them their respective ranges.
6. Each thread calculates its partial sum and updates the global sum (mutex-protected).
7. Wait for all threads to finish (pthread_join).
8. Destroy the mutex and print the final global sum.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

3. Summary

• Multithreading enables concurrent computation, improving efficiency.

• Mutexes guarantee synchronized access to shared variables, avoiding race
conditions.
• Proper range allocation ensures all numbers are included and workload is balanced.
• Threads perform partial sums, contributing to the final global sum.
• The experiment demonstrates thread creation, execution, synchronization, and
coordination in a multithreaded environment.

Code:

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

#define MAX_THREADS 10

// Global sum and mutex

long long global_sum = 0;
pthread_mutex_t sum_mutex;

// Structure for thread parameters

typedef struct {
int start;
int end;
} ThreadData;

// Thread function
void* partial_sum(void* arg) {
ThreadData* data = (ThreadData*) arg;
long long local_sum = 0;

for (int i = data->start; i <= data->end; i++) {

local_sum += i;
}

// Lock before updating global sum

pthread_mutex_lock(&sum_mutex);
global_sum += local_sum;
pthread_mutex_unlock(&sum_mutex);
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

pthread_exit(NULL);
}

int main() {
int N, num_threads;
pthread_t threads[MAX_THREADS];
ThreadData thread_data[MAX_THREADS];

// Input N
printf("Enter a non-negative integer N: ");
scanf("%d", &N);

if (N < 0) {
printf("Error: N must be non-negative.\n");
return 1;
}

// Input number of threads

printf("Enter number of threads (1-%d): ", MAX_THREADS);
scanf("%d", &num_threads);

if (num_threads < 1 || num_threads > MAX_THREADS) {

printf("Error: Invalid number of threads.\n");
return 1;
}

// Initialize mutex
pthread_mutex_init(&sum_mutex, NULL);

// Calculate range for each thread

int chunk_size = (N + 1) / num_threads;
int remainder = (N + 1) % num_threads;
int start = 0;

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

thread_data[i].start = start;
thread_data[i].end = start + chunk_size - 1;
if (remainder > 0) {
thread_data[i].end++;
remainder--;
}
start = thread_data[i].end + 1;
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

pthread_create(&threads[i], NULL, partial_sum, (void*)

&thread_data[i]);
}

// Join threads
for (int i = 0; i < num_threads; i++) {
pthread_join(threads[i], NULL);
}

// Destroy mutex
pthread_mutex_destroy(&sum_mutex);

// Print result
printf("Sum of 0 to %d = %lld\n", N, global_sum);

return 0;
}

Output:

Learning Outcomes:

1. Successfully implement a multithreaded program to calculate the summation of non-negative

integers.
2. Correctly create and manage threads using the pthread library in C.
3. Effectively synchronize access to shared resources using mutex locks, avoiding race conditions.
4. Divide computational tasks among multiple threads and combine results to obtain the final sum.
5. Observe and analyze the behavior of concurrent execution, ensuring accurate summation across
threads.

Course Outcomes:

Students develop a strong understanding of multithreading and concurrent programming concepts.

They learn to create and manage threads using the pthread library, synchronize shared resources
with mutexes, and effectively divide computational tasks among multiple threads. By implementing
a summation program, students gain hands-on experience in coordinating concurrent execution and
ensuring data integrity, reinforcing their understanding of thread management, synchronization
mechanisms, and practical applications of parallel computing in C.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Conclusion:

Successfully implemented a multithreaded program to calculate the summation of non-negative

integers. Efficiently created and managed threads, synchronized access to the shared sum using mutex
locks, and ensured accurate and orderly computation across concurrent threads, thereby fulfilling the
aim of demonstrating practical multithreading and synchronization in C.

Viva Questions:

1. What is the purpose of using threads in this program instead of sequential execution?
2. How does the pthread_mutex_t ensure synchronization of the global sum?
3. How is the workload divided among multiple threads in this program?
4. What is the role of pthread_create() and pthread_join() in thread management?
5. What could happen if mutex locks were not used when updating the shared variable?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—2B : Multi-threaded Prime Number Generator

Aim: To write a multithreaded C program that outputs all prime numbers less than or equal to a user-
specified number, demonstrating concurrent execution using threads.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the concept of multithreading and how threads execute concurrently.

2. Learn how to implement threads in C using the pthread library.
3. Apply thread synchronization techniques when necessary to manage shared resources.
4. Divide computational tasks among multiple threads for parallel execution.
5. Execute and observe the behavior of multithreaded programs for correctness and efficiency.

Theory:

1. Introduction
Multithreading allows a program to execute multiple threads concurrently within a single
process. Each thread operates independently but shares the same process memory,
enabling efficient parallel execution of tasks. In this experiment, multithreading is used to
find all prime numbers less than or equal to a user-specified number. Each thread is
responsible for checking a subset of numbers, allowing the workload to be divided and
executed concurrently. This approach demonstrates practical multithreading, task
division, and parallel computation in C using the pthread library.

2. Multithreading and Primes

2.1 Multithreading Concept

• Definition: Multithreading is the concurrent execution of multiple threads within a

single process. Threads share memory but execute independently, allowing faster and
more efficient computation.
• Key Points:
1. Threads improve program efficiency by performing tasks concurrently.
2. Each thread can execute a part of a larger task (here, checking a range of
numbers for primality).
3. Shared data must be accessed carefully if threads update it to prevent race
conditions.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

• Example Table – Thread Task Allocation for N = 5, 4 Threads:

Thread Range Numbers Checked
T1 2–2 2
T2 3–3 3
T3 4–4 4
T4 5–5 5

2.2 Prime Number Concept and Checking

• Definition: A prime number is a natural number greater than 1 that has no positive
divisors other than 1 and itself.
• Prime Checking Logic:
1. Numbers less than 2 are not prime.
2. 2 is the first prime number.
3. Even numbers greater than 2 are not prime.
4. Odd numbers are checked by dividing them by all odd integers up to their
square root.
• Code Mapping:

int is_prime(int num) {

if (num < 2) return 0;
if (num == 2) return 1;
if (num % 2 == 0) return 0;
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) return 0;
}
return 1;
}

2.3 Thread Data Structure and Task Allocation

• Definition: Each thread requires information about the range of numbers it will
check. This is achieved using a ThreadData structure containing start and end.
• Code Mapping:

typedef struct {
int start;
int end;
} ThreadData;

• Purpose: Divides the overall range among threads to balance workload and ensure all
numbers are processed.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2.4 Thread Creation and Execution

• Definition: Threads are created using pthread_create(). Each thread executes the
function find_primes(), which checks numbers in its assigned range.
• Joining Threads: The main program waits for all threads to complete using
pthread_join().
• Code Mapping:

pthread_create(&threads[i], NULL, find_primes, (void*)&thread_data[i]);

pthread_join(threads[i], NULL);

• Purpose: Ensures concurrent execution while maintaining orderly program

completion.

2.5 Range Division Among Threads

• Logic: The total numbers from 2 to N are divided among num_threads threads:
1. range = (N - 1) / num_threads
2. The last thread may handle any remaining numbers to cover all integers up to N.
• Code Mapping:

int range = (N - 1) / num_threads;

int start = 2;
for (int i = 0; i < num_threads; i++) {
thread_data[i].start = start;
thread_data[i].end = (i == num_threads - 1) ? N : start + range - 1;
start = thread_data[i].end + 1;
}

• Purpose: Ensures efficient workload distribution and balanced parallel execution.

2.6 Algorithm / Steps

1. Input the upper limit N.

2. Input the number of threads num_threads.
3. Initialize thread data structures with start and end ranges.
4. Create threads using pthread_create(), each executing the prime-checking
function.
5. Threads check numbers in their assigned range and print primes.
6. Wait for all threads to complete using pthread_join().
7. Program ends after all threads finish and all prime numbers up to N are printed.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

3. Summary

• Multithreading allows concurrent checking of numbers, improving execution

efficiency.
• The ThreadData structure enables clear division of tasks among threads.
• Each thread independently identifies prime numbers in its assigned range.
• pthread_create() and pthread_join() manage thread execution and program
synchronization.
• The experiment demonstrates practical multithreading, task division, and parallel
computation in C.

Flag Purpose
-lm Links the math library (libm) for functions like sqrt(), pow(), etc.
-lpthread Links the POSIX threads library for pthread_create(), pthread_join(),
etc.

• gcc — GNU C Compiler

• newnameoffile.c — your source file
• -o pc — output binary name (pc)
• -lpthread — links the pthread library (threads)
• -lm — links the math library (for sqrt())

Then you can execute it like: ./pc

Code:

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

#define MAX_THREADS 10

// Structure to hold thread data

typedef struct {
int start;
int end;
} ThreadData;

// Function to check if a number is prime

int is_prime(int num) {
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

if (num < 2) return 0;

if (num == 2) return 1;
if (num % 2 == 0) return 0;
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0)
return 0;
}
return 1;
}

// Thread function to find primes in a given range

void* find_primes(void* arg) {
ThreadData* data = (ThreadData*) arg;
for (int i = data->start; i <= data->end; i++) {
if (is_prime(i)) {
printf("Prime: %d\n", i);
}
}
pthread_exit(NULL);
}

int main() {
int N, num_threads;
pthread_t threads[MAX_THREADS];
ThreadData thread_data[MAX_THREADS];

// Input upper limit N

printf("Enter the upper limit (N): ");
scanf("%d", &N);
if (N < 2) {
printf("There are no primes less than 2.\n");
return 0;
}

// Input number of threads

printf("Enter number of threads (1-%d): ", MAX_THREADS);
scanf("%d", &num_threads);

if (num_threads < 1 || num_threads > MAX_THREADS) {

printf("Invalid number of threads.\n");
return 1;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

// Divide the range among threads

int range = (N - 1) / num_threads; // start from 2 to N
int start = 2;
for (int i = 0; i < num_threads; i++) {
thread_data[i].start = start;
thread_data[i].end = (i == num_threads - 1) ? N : start + range - 1;
start = thread_data[i].end + 1;

pthread_create(&threads[i], NULL, find_primes,

(void*)&thread_data[i]);
}

// Wait for threads to finish

for (int i = 0; i < num_threads; i++) {
pthread_join(threads[i], NULL);
}

return 0;
}

Output:

Learning Outcomes:

1. Successfully implemented multithreading and executed threads concurrently.

2. Successfully created and managed threads in C using the pthread library.
3. Successfully applied synchronization techniques to manage shared resources.
4. Successfully divided computational tasks among multiple threads for parallel execution.
5. Successfully observed and verified the correct behavior of multithreaded programs.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Course Outcomes:

Students successfully developed a strong understanding of multithreading and concurrent

programming. They implemented and managed threads using the pthread library, synchronized
tasks where necessary, and efficiently divided computational workloads among threads. By
executing a program to determine prime numbers, students gained hands-on experience in
coordinating concurrent execution and verifying program correctness, reinforcing practical skills in
parallel computing and thread management.

Conclusion:

Successfully implemented a multithreaded program to find prime numbers up to a given limit.

Efficiently created and managed threads, divided the computational workload among them, and
ensured correct concurrent execution. Observed accurate identification of prime numbers across
threads, thereby fulfilling the aim of demonstrating practical multithreading, parallel computation,
and thread coordination in C.

Viva Questions:

1. What is the purpose of using threads in this program instead of sequential execution?
2. How is the range of numbers divided among multiple threads?
3. What is the role of the pthread_create() and pthread_join() functions?
4. How does the program ensure correct identification of prime numbers in a concurrent
environment?
5. Why is the is_prime() function necessary, and how does it work?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—3A : Synchronization to Bound the Buffer Problem

Aim:

To implement the bounded-buffer (Producer-Consumer) problem using multithreading in C,

demonstrating synchronization with mutexes and condition variables to ensure orderly production
and consumption of items in a shared buffer.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the concept of thread synchronization and how it helps in coordinating producer and
consumer threads.

2. Learn how to use mutexes to ensure mutual exclusion while accessing shared resources.

3. Apply condition variables to signal and wait for buffer state changes (full/empty).

4. Implement a bounded buffer using threads to manage concurrent production and consumption.

5. Observe and analyze the behavior of synchronized threads in a controlled environment.

Theory:

1. Introduction
In concurrent programming, multiple threads may need to access and manipulate shared
resources simultaneously. If proper synchronization is not enforced, this can lead to race
conditions, inconsistent data, or program crashes. The Bounded Buffer problem (a version
of the Producer-Consumer problem) is a classical example used to illustrate thread
coordination and synchronization mechanisms.

In this problem:

• A producer thread generates data items and places them into a fixed-size buffer.
• A consumer thread removes items from the buffer for processing.
• The buffer has a maximum capacity, so the producer must wait if the buffer is full,
and the consumer must wait if the buffer is empty.

This experiment demonstrates synchronization using mutexes (mutual exclusion) and

condition variables, which ensures threads can safely share resources without data
corruption.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2. Synchronization Concepts in Bounded Buffer Problem

2.1 Producer-Consumer Concept

• Definition: A design pattern where producers create data and consumers process it
using a shared buffer.
• Key Points:
1. Producer: Adds items to the buffer. Must wait if the buffer is full.
2. Consumer: Removes items from the buffer. Must wait if the buffer is empty.
3. Buffer State Management: Ensures that no data is lost, overwritten, or
skipped.
• Example Table – Buffer Operations:

Step Producer Action Consumer Action Buffer State

1 Produces item 1 Waits (empty) [1]
2 Produces item 2 Consumes item 1 [2]
3 Produces item 3 Consumes item 2 [3]
4 Waits (full) Consumes item 3 []

This table shows how producers and consumers coordinate through the buffer state, waiting
when necessary.

2.2 Mutex (Mutual Exclusion)

• Definition: A mutex is a synchronization primitive that allows only one thread to

enter a critical section at a time.
• Purpose in Experiment: Prevents simultaneous modification of shared buffer
variables (in, out, count), which could otherwise lead to inconsistent data.
• Code Mapping:

pthread_mutex_lock(&mutex); // Enter critical section

// Access buffer (add/remove item)
pthread_mutex_unlock(&mutex); // Exit critical section

2.3 Condition Variables

• Definition: Condition variables are used to make threads wait for a particular
condition before proceeding.
• Purpose in Experiment:
o Producer waits when the buffer is full (count == BUFFER_SIZE).
o Consumer waits when the buffer is empty (count == 0).
o They allow threads to sleep instead of busy-waiting, improving efficiency.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

• Code Mapping:

// Producer waits if buffer is full

pthread_cond_wait(&not_full, &mutex);

// Signal consumer that buffer is not empty

pthread_cond_signal(&not_empty);

2.4 Circular Buffer Concept

• Definition: A circular buffer allows the producer and consumer to wrap around the
array when the end is reached, efficiently using space.
• Implementation in Experiment:
o in points to the index where the producer will add the next item.
o out points to the index where the consumer will remove the next item.
o Indices are updated using modulo operation: (index + 1) % BUFFER_SIZE.
• Benefit: Avoids shifting elements and ensures smooth continuous operation.

2.5 Algorithm / Steps

1. Initialize a buffer of fixed size, a mutex, and two condition variables (not_full,
not_empty).
2. Producer thread:
o Generate items one by one.
o Wait if the buffer is full (pthread_cond_wait).
o Insert item into buffer and update in and count.
o Signal consumer that buffer is not empty (pthread_cond_signal).
3. Consumer thread:
o Wait if buffer is empty (pthread_cond_wait).
o Remove item from buffer and update out and count.
o Signal producer that buffer is not full (pthread_cond_signal).
4. Repeat until all items are produced and consumed.
5. Wait for threads to complete using pthread_join.
6. Destroy mutex and condition variables.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

3. Summary

• Demonstrates thread synchronization using mutexes and condition variables.

• Ensures safe concurrent access to a shared buffer.
• Properly handles full and empty buffer conditions, preventing data loss or overflow.
• Illustrates practical bounded buffer problem, a foundation for many real-world
producer-consumer scenarios.
• Shows effective use of circular buffer for efficient resource utilization and smooth
producer-consumer coordination.

Code:

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

#define BUFFER_SIZE 5
#define PRODUCE_COUNT 10

int buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int count = 0;

pthread_mutex_t mutex;
pthread_cond_t not_full;
pthread_cond_t not_empty;

// Producer thread function

void* producer(void* arg) {
for (int i = 0; i < PRODUCE_COUNT; i++) {
int item = i + 1;

pthread_mutex_lock(&mutex);

while (count == BUFFER_SIZE) {

// Buffer is full, wait for not_full signal
pthread_cond_wait(&not_full, &mutex);
}

// Add item to buffer

 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

buffer[in] = item;
printf("Producer produced: %d\n", item);
in = (in + 1) % BUFFER_SIZE;
count++;

// Signal that buffer is not empty

pthread_cond_signal(&not_empty);
pthread_mutex_unlock(&mutex);

sleep(1); // simulate production delay

}

pthread_exit(NULL);
}

// Consumer thread function

void* consumer(void* arg) {
for (int i = 0; i < PRODUCE_COUNT; i++) {
pthread_mutex_lock(&mutex);

while (count == 0) {
// Buffer is empty, wait for not_empty signal
pthread_cond_wait(&not_empty, &mutex);
}

int item = buffer[out];

printf("Consumer consumed: %d\n", item);
out = (out + 1) % BUFFER_SIZE;
count--;

// Signal that buffer is not full

pthread_cond_signal(&not_full);
pthread_mutex_unlock(&mutex);

sleep(1); // simulate consumption delay

}

pthread_exit(NULL);
}

int main() {
pthread_t prod_thread, cons_thread;
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

// Initialize mutex and condition variables

pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&not_full, NULL);
pthread_cond_init(&not_empty, NULL);

// Create producer and consumer threads

pthread_create(&prod_thread, NULL, producer, NULL);
pthread_create(&cons_thread, NULL, consumer, NULL);

// Wait for both threads to finish

pthread_join(prod_thread, NULL);
pthread_join(cons_thread, NULL);

// Destroy synchronization primitives

pthread_mutex_destroy(&mutex);
pthread_cond_destroy(&not_full);
pthread_cond_destroy(&not_empty);

return 0;
}

Output:
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Learning Outcomes:

1. Successfully implemented synchronization to manage a bounded buffer using threads.

2. Successfully created and managed producer and consumer threads in C using the pthread library.
3. Successfully applied mutex and condition variables to ensure safe access to the shared buffer.
4. Successfully coordinated concurrent production and consumption, avoiding buffer overflows and
underflows.
5. Successfully observed and verified orderly execution of threads, demonstrating correct producer-
consumer synchronization.

Course Outcomes:

Students successfully developed a strong understanding of thread synchronization and inter-thread

communication in C. They implemented and managed producer and consumer threads using
mutexes and condition variables, ensuring safe and orderly access to a shared bounded buffer. By
executing a program that coordinates concurrent production and consumption, students gained
practical skills in synchronization mechanisms, race condition prevention, and concurrent program
design, reinforcing their knowledge of operating system concepts and multithreaded application
development.

Conclusion:

Successfully implemented a multithreaded program to coordinate producer and consumer threads

with a bounded buffer. Efficiently used mutexes and condition variables to synchronize access,
prevent race conditions, and ensure orderly production and consumption. Observed correct inter-
thread communication and safe handling of shared resources, thereby fulfilling the aim of
demonstrating practical synchronization techniques in C.

Viva Questions:

1. What is the bounded buffer problem, and why is synchronization required in this scenario?
2. Explain how mutexes ensure mutual exclusion in the producer-consumer program.
3. What role do condition variables play in managing full and empty buffer states?
4. Describe how a circular buffer is implemented in this experiment and its advantages.
5. What could happen if synchronization primitives were not used in this multithreaded program?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—3B : Reader-Writer Problem using Synchronization

Aim:

To implement the Reader-Writer problem in C using threads, mutexes, and synchronization

mechanisms, ensuring that multiple readers can read simultaneously while writers get exclusive
access to the shared resource.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the Reader-Writer problem and its significance in concurrent programming.

2. Learn to implement multiple reader and writer threads in C using pthreads.

3. Apply mutex locks to protect shared resources and prevent race conditions.

4. Coordinate access so that multiple readers can read simultaneously, but writers get exclusive
access.

5. Observe and analyze the behavior of synchronized reader and writer threads in a controlled
environment.

Theory:

1. Introduction
In multithreaded programming, multiple threads often need to access shared resources
simultaneously. Improper access can cause race conditions, data inconsistency, or program
crashes.

The Reader-Writer Problem is a classical synchronization problem that deals with

controlling access to a shared resource:

• Multiple readers can read the resource at the same time.

• Writers must have exclusive access to update the resource.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

This experiment demonstrates how to synchronize readers and writers using mutexes to
ensure:

• Readers do not conflict with writers.

• Writers have exclusive access.
• Data consistency is maintained throughout concurrent operations.

2. Synchronization Concepts in Reader-Writer Problem

2.1 Reader-Writer Concept

Definition: Coordination of threads to allow multiple readers or a single writer to access
shared data safely.

Key Points:

• Readers can read concurrently.

• Writers require exclusive access.
• Synchronization prevents race conditions.

Example Table – Access Pattern:

Step Action Shared Data Access Type

1 Reader 1 reads 0 Read
2 Writer 1 writes 10 Write
3 Reader 2 reads 10 Read
4 Writer 2 writes 20 Write
5 Reader 3 reads 20 Read

2.2 Mutex (Mutual Exclusion)

Definition: Mutex allows only one thread at a time to access a critical section.

Purpose in Experiment:

• Protects read_count so multiple readers do not corrupt its value.

• Ensures safe modification of shared resource when writers write.

Code Mapping:

pthread_mutex_lock(&mutex); // Enter critical section

// Access shared resource or update read_count
pthread_mutex_unlock(&mutex); // Exit critical section
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2.3 Writer Lock

Definition: A separate mutex (write_lock) ensures only one writer can write at a time.

Purpose in Experiment:

• Writers get exclusive access to shared data.

• Readers can coordinate through read_count to block writers while reading.

Code Mapping:

pthread_mutex_lock(&write_lock);
// Write operation
pthread_mutex_unlock(&write_lock);

2.4 Reader Thread Execution

• Lock mutex and increment read_count.

• If this is the first reader, lock write_lock to block writers.
• Unlock mutex.
• Read the shared resource.
• Lock mutex and decrement read_count.
• If this is the last reader, unlock write_lock.
• Unlock mutex.

Purpose: Allows multiple readers to read concurrently while blocking writers only if
necessary.

2.5 Writer Thread Execution

• Lock write_lock.
• Write to shared resource.
• Unlock write_lock.

Purpose: Ensures that writers have exclusive access, preventing any readers from accessing
data while writing.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2.6 Algorithm / Steps

1. Initialize mutex and write_lock.

2. Create multiple reader and writer threads.
3. Readers:
o Increment read_count under mutex.
o First reader locks write_lock.
o Read shared data.
o Last reader unlocks write_lock.
4. Writers:
o Lock write_lock.
o Update shared data.
o Unlock write_lock.
5. Use pthread_join to wait for all threads to finish.
6. Destroy mutexes.

3. Summary

• Demonstrates thread synchronization for multiple readers and exclusive writers.

• Uses mutexes and write locks to prevent race conditions.
• Allows concurrent reading but ensures exclusive writing.
• Reinforces understanding of inter-thread communication, resource sharing, and
data consistency in multithreaded programs.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Code:

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

pthread_mutex_t mutex; // For protecting shared variables

pthread_mutex_t write_lock; // For writers to get exclusive access

int read_count = 0; // Number of active readers

// Shared resource
int shared_data = 0;

void* reader(void* arg) {

int id = *((int*)arg);

pthread_mutex_lock(&mutex);
read_count++;
if (read_count == 1) {
// First reader locks writers out
pthread_mutex_lock(&write_lock);
}
pthread_mutex_unlock(&mutex);

// Reading (simulated)
printf("Reader %d: reading shared_data = %d\n", id, shared_data);
sleep(1); // Simulate read time

pthread_mutex_lock(&mutex);
read_count--;
if (read_count == 0) {
// Last reader unlocks writers
pthread_mutex_unlock(&write_lock);
}
pthread_mutex_unlock(&mutex);

pthread_exit(NULL);
}
void* writer(void* arg) {
int id = *((int*)arg);
pthread_mutex_lock(&write_lock);
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

// Writing (simulated)
shared_data += 10;
printf("Writer %d: writing shared_data = %d\n", id, shared_data);
sleep(1); // Simulate write time

pthread_mutex_unlock(&write_lock);

pthread_exit(NULL);
}

int main() {
pthread_t readers[5], writers[2];
int reader_ids[5] = {1, 2, 3, 4, 5};
int writer_ids[2] = {1, 2};

// Initialize mutexes
pthread_mutex_init(&mutex, NULL);
pthread_mutex_init(&write_lock, NULL);

// Create reader and writer threads

pthread_create(&readers[0], NULL, reader, &reader_ids[0]);
sleep(1);
pthread_create(&writers[0], NULL, writer, &writer_ids[0]);
sleep(1);
pthread_create(&readers[1], NULL, reader, &reader_ids[1]);
pthread_create(&readers[2], NULL, reader, &reader_ids[2]);
sleep(1);
pthread_create(&writers[1], NULL, writer, &writer_ids[1]);
pthread_create(&readers[3], NULL, reader, &reader_ids[3]);
pthread_create(&readers[4], NULL, reader, &reader_ids[4]);

// Wait for all threads to finish

for (int i = 0; i < 5; i++)
pthread_join(readers[i], NULL);
for (int i = 0; i < 2; i++)
pthread_join(writers[i], NULL);

// Destroy mutexes
pthread_mutex_destroy(&mutex);
pthread_mutex_destroy(&write_lock);
return 0;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Output:

Note:
The exact order of output may vary across executions because threads in a multithreaded program
execute concurrently. The operating system’s thread scheduler determines the sequence of
execution, leading to minor variations each time the program runs. However, the synchronization
ensures that:

• Multiple readers can read simultaneously.

• Writers always have exclusive access while writing.

• No race conditions or data inconsistencies occur.

Learning Outcomes:

1. Successfully implemented the Reader-Writer problem using multithreading in C.

2. Successfully synchronized reader and writer threads to prevent race conditions.
3. Successfully applied mutexes to protect shared resources.
4. Successfully coordinated multiple readers and writers to allow concurrent reads and exclusive
writes.
5. Successfully observed and verified correct execution of the Reader-Writer synchronization
mechanism.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Course Outcomes:

Students successfully developed a strong understanding of thread synchronization and inter-thread

communication in C. They implemented the Reader-Writer problem, coordinated multiple readers
and writers using mutexes, and ensured safe access to shared resources. By executing this program,
students gained practical skills in handling concurrent reads and exclusive writes, preventing race
conditions, and managing multithreaded synchronization in real-world scenarios.

Conclusion:

Successfully implemented a multithreaded Reader-Writer program in C. Efficiently coordinated

multiple readers and writers using mutex locks to ensure safe concurrent access and exclusive write
access to shared data. Observed correct synchronization, prevented race conditions, and verified that
the program maintains data consistency, thereby fulfilling the aim of demonstrating practical thread
synchronization in a shared resource scenario.

Viva Questions:

1. What is the purpose of using separate mutexes for readers and writers?
2. How does the program ensure that multiple readers can read simultaneously?
3. How does the program prevent writers from accessing the shared data while readers are reading?
4. What happens if the read_count variable is not properly synchronized?
5. Why is it important to destroy the mutexes at the end of the program?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—3C : Sleeping Barber Problem using Synchronization

Aim:

To implement the Sleeping Barber problem in C using threads, mutexes, and condition variables to
manage synchronization between the barber and multiple customers, ensuring proper coordination
of sleeping, waking, and servicing behavior.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the Sleeping Barber problem and its significance in process synchronization.
2. Learn to implement multiple customer threads and a barber thread using pthreads in C.
3. Apply mutex locks and condition variables to coordinate access between barber and customers.
4. Ensure that the barber sleeps when no customers are present and wakes up when a customer
arrives.
5. Observe and analyze how concurrent threads manage limited resources (chairs) to prevent race
conditions.

Theory:

1. Introduction
The Sleeping Barber problem is a classic synchronization problem in operating systems and
concurrent programming. It models a barber shop scenario to illustrate thread coordination
and resource sharing.

• A barber gives haircuts to customers.

• If there are no customers, the barber sleeps until a customer arrives.
• A limited number of chairs are available for waiting customers.
• If all chairs are occupied, a new arriving customer leaves.

The problem highlights how multiple threads (barber and customers) interact with a shared
resource (the barber and chairs) while avoiding race conditions, lost signals, and ensuring
correct order of operations.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2. Key Concepts in Synchronization

2.1 Shared Resources

• Barber: The resource that can serve one customer at a time.

• Chairs: Represent a waiting area for customers. The number of chairs limits the
queue.
• Shared variables in code:
o waiting_customers → tracks number of customers waiting.
o barber_sleeping → indicates barber state (1 = sleeping, 0 = awake).

2.2 Mutex (Mutual Exclusion)

• A mutex ensures that only one thread at a time can access critical sections, like
updating waiting_customers.
• Without a mutex, multiple customers arriving simultaneously could corrupt shared
data, causing incorrect counts or missed haircuts.

Code Reference:

pthread_mutex_lock(&mutex); // Enter critical section

// Update waiting_customers
pthread_mutex_unlock(&mutex); // Exit critical section

2.3 Condition Variables

Condition variables allow threads to sleep and wait efficiently until a specific condition
occurs, instead of busy-waiting.

• customer_ready → barber waits on this if there are no customers.

• barber_ready → customer waits on this until barber is ready to give a haircut.

Code Reference:

pthread_cond_wait(&customer_ready, &mutex); // Barber sleeps

pthread_cond_signal(&barber_ready); // Barber signals customer
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2.4 Barber Thread Logic

• Barber continuously checks for customers:

1. Locks mutex.
2. If no customers (waiting_customers == 0), barber sleeps on
customer_ready.
3. If customers are waiting:
▪ Decrement waiting_customers.
▪ Signal a customer using barber_ready.
4. Unlock mutex.
5. Perform haircut (simulate with sleep).
• Key idea: Barber is consumer, serving customers one by one.

Code Flow Connection:

• pthread_cond_wait → barber sleeps until customer signals.

• pthread_cond_signal → barber signals a specific customer to proceed.

2.5 Customer Thread Logic

• Customer arrives and locks mutex to check available chairs:

1. If chairs available (waiting_customers < NUM_CHAIRS):
▪ Increment waiting_customers.
▪ Signal customer_ready to wake barber if sleeping.
▪ Wait for barber using barber_ready.
▪ Get haircut.
2. Else: customer leaves if no chair available.
• Unlock mutex after operation.

Code Flow Connection:

• waiting_customers++ → customer joins the queue.

• pthread_cond_wait(&barber_ready, &mutex) → waits until barber is ready.
• Ensures synchronized access and prevents multiple customers from starting haircut
simultaneously.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2.6 Circular Flow – How Threads Interact

1. Barber sleeps if no customer.

2. Customer arrives:
o Finds free chair → increments waiting_customers.
o Signals barber.
o Waits for barber_ready signal.
3. Barber wakes, serves customer, and signals them.
4. Customer receives haircut and leaves.
5. Repeat until all customers are served.

This flow ensures:

• Barber doesn’t waste CPU cycles waiting actively.

• Customers wait their turn.
• Maximum chairs constraint is respected.
• No race conditions on shared variables.

2.7 Algorithm / Steps

1. Initialize mutex and condition variables (barber_ready, customer_ready).

2. Create barber thread.
3. Create customer threads with random arrival times.
4. Each customer:
o Lock mutex.
o Check chair availability.
o Increment waiting_customers if possible.
o Signal barber (customer_ready).
o Wait for barber (barber_ready).
o Unlock mutex.
5. Barber thread:
o Wait for customers (customer_ready).
o Decrement waiting_customers.
o Signal customer (barber_ready).
o Perform haircut.
6. Wait for all customer threads using pthread_join.
7. Destroy mutex and condition variables.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

3. Summary

• Demonstrates thread synchronization using mutexes and condition variables.

• Handles limited resources (barber and chairs) efficiently.
• Ensures barber sleeps when idle and wakes on customer arrival.
• Prevents race conditions on shared variables (waiting_customers).
• Customers either wait or leave if the waiting area is full.
• A practical example of producer-consumer problem with bounded buffer analogy.

Code:

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

#define NUM_CUSTOMERS 10
#define NUM_CHAIRS 3

// Mutex for critical section

pthread_mutex_t mutex;

// Condition variables
pthread_cond_t barber_ready;
pthread_cond_t customer_ready;

// Shared variables
int waiting_customers = 0;
int barber_sleeping = 1;

// Barber thread function

void* barber(void* arg) {
while (1) {
pthread_mutex_lock(&mutex);

// Wait if no customers
while (waiting_customers == 0) {
printf("Barber: No customers, going to sleep.\n");
pthread_cond_wait(&customer_ready, &mutex);
}

// Serve next customer

 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

waiting_customers--;
printf("Barber: Cutting hair. Waiting customers: %d\n",
waiting_customers);

pthread_cond_signal(&barber_ready); // Signal customer

pthread_mutex_unlock(&mutex);

// Simulate haircut
sleep(2);
printf("Barber: Done cutting hair.\n");
}
return NULL;
}

// Customer thread function

void* customer(void* arg) {
int id = *((int*)arg);
free(arg);

pthread_mutex_lock(&mutex);

if (waiting_customers < NUM_CHAIRS) {

waiting_customers++;
printf("Customer %d: Waiting. Total waiting: %d\n", id,
waiting_customers);

pthread_cond_signal(&customer_ready); // Wake barber

pthread_cond_wait(&barber_ready, &mutex); // Wait for barber
printf("Customer %d: Getting haircut.\n", id);
} else {
printf("Customer %d: No chair available, leaving.\n", id);
}

pthread_mutex_unlock(&mutex);
return NULL;
}

int main() {
pthread_t barber_thread;
pthread_t customer_threads[NUM_CUSTOMERS];

// Initialize mutex and condition variables

pthread_mutex_init(&mutex, NULL);
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

pthread_cond_init(&barber_ready, NULL);
pthread_cond_init(&customer_ready, NULL);

// Create barber thread

pthread_create(&barber_thread, NULL, barber, NULL);

// Create customer threads with random arrival

for (int i = 0; i < NUM_CUSTOMERS; i++) {
sleep(rand() % 3); // Random arrival time
int* id = malloc(sizeof(int));
*id = i + 1;
pthread_create(&customer_threads[i], NULL, customer, id);
}

// Wait for all customer threads

for (int i = 0; i < NUM_CUSTOMERS; i++) {
pthread_join(customer_threads[i], NULL);
}

// Barber continues indefinitely; for demo, cancel thread

printf("All customers have been processed.\n");
pthread_cancel(barber_thread);

// Clean up
pthread_mutex_destroy(&mutex);
pthread_cond_destroy(&barber_ready);
pthread_cond_destroy(&customer_ready);

return 0;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Output:

Learning Outcomes:

1. Successfully understood the Sleeping Barber problem and its significance in process
synchronization.
2. Successfully implemented multiple customer threads and a barber thread using pthreads in C.
3. Successfully applied mutex locks and condition variables to coordinate access between barber
and customers.
4. Successfully ensured that the barber sleeps when no customers are present and wakes up when
a customer arrives.
5. Successfully observed and verified how concurrent threads manage limited resources (chairs) to
prevent race conditions.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Course Outcomes:

Students successfully developed a strong understanding of process synchronization and inter-thread

communication in C. They implemented the Sleeping Barber problem, coordinated multiple
customer and barber threads, and applied mutexes and condition variables to manage shared
resources. By executing this experiment, students gained practical skills in handling limited
resources, preventing race conditions, and ensuring orderly execution of concurrent threads in real-
world scenarios.

Conclusion:

Successfully implemented a multithreaded Sleeping Barber program in C. Efficiently coordinated

barber and customer threads using mutexes and condition variables, ensuring the barber sleeps when
no customers are present and wakes when customers arrive. Managed limited chairs effectively,
prevented race conditions, and observed correct thread synchronization, thereby fulfilling the aim of
demonstrating practical process synchronization and resource management in concurrent
programming.

Viva Questions:

1. What is the purpose of using mutexes and condition variables in the Sleeping Barber problem?
2. How does the program ensure that the barber sleeps when no customers are present?
3. How are waiting customers managed when there are limited chairs?
4. What happens if mutexes are not used in this program?
5. Why is it necessary to cancel or stop the barber thread at the end of the program?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—4 : FCFS Scheduling Algorithm

Aim:

To implement the First-Come, First-Served (FCFS) CPU scheduling algorithm in C, calculate the waiting
time and turnaround time for each process, and determine the average waiting and turnaround times.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the concept of CPU Scheduling and its importance in process management.
2. Learn the working principle of the First Come First Serve (FCFS) scheduling algorithm.
3. Implement the FCFS scheduling algorithm using C programming.
4. Calculate and analyze Waiting Time and Turnaround Time for multiple processes.
5. Evaluate the performance of FCFS scheduling by computing average waiting and turnaround times
for given inputs.

Theory:

1. Introduction

In an operating system, multiple processes compete for CPU time. The CPU scheduler
decides which process gets the CPU next based on a specific scheduling algorithm. Among
these, the First Come First Serve (FCFS) scheduling algorithm is the simplest and most
intuitive form of CPU scheduling.

The FCFS algorithm follows the FIFO (First In, First Out) principle — meaning the
process that arrives first in the ready queue gets executed first. Once the CPU is assigned to a
process, it runs till completion without being preempted or interrupted by another process.

This type of scheduling is non-preemptive, meaning that once the CPU starts executing a
process, it cannot stop until that process completes. Any new process arriving in the
meantime must wait until the current one is finished.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Real-life Analogy:

Imagine a queue at a movie ticket counter. The customer who comes first is served first, and
others wait in line until it’s their turn. Similarly, in FCFS scheduling, processes are served in
the order they arrive.

This simple idea ensures fairness — every process gets a turn — but can also cause
inefficiency if long processes arrive before shorter ones, leading to what’s called the convoy
effect, where shorter processes are delayed unnecessarily.

2. Basic Concept of FCFS

The FCFS scheduling algorithm schedules processes based solely on their arrival time.
The key characteristic is no preemption — once a process starts, it keeps the CPU until it
finishes execution.

Let’s break this down:

• Processes enter the ready queue as they arrive.

• The CPU is allocated to the first process in the queue.
• The process executes for its entire burst time (the time it needs on the CPU).
• After it finishes, the next process in the queue gets the CPU.
• This continues until all processes are executed.

If the CPU becomes idle (no process in the queue), it simply waits until the next process
arrives.

3. Important Terms and Definitions

Term Description
Arrival Time (AT) The time at which a process arrives and becomes ready for
execution.
Burst Time (BT) The total amount of CPU time required by a process for
execution.
Completion Time (CT) The time at which a process finishes execution.
Waiting Time (WT) The total time a process spends waiting in the ready queue before
getting CPU time.
Formula: WT = Start Time – Arrival Time
Turnaround Time (TAT) The total time taken from process arrival to its completion.
Formula: TAT = WT + BT
Average Waiting Time The average of all waiting times.
(AWT) Formula: AWT = ΣWT / n
Average Turnaround Time The average of all turnaround times.
(ATAT) Formula: ATAT = ΣTAT / n
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

4. Step-by-Step Working of FCFS

Step 1: Input and Sorting

• The number of processes and their arrival and burst times are entered.
• The processes are sorted by their arrival time, ensuring that the earliest arriving
process executes first.

Step 2: Execution Flow

• A variable current_time keeps track of the CPU’s current time.

• For each process:
o If current_time < arrival_time, the CPU remains idle until the process
arrives.
o Once the process starts, its waiting time is calculated as the difference
between its start time and arrival time.
o The process runs for its burst time, updating current_time.
o Its turnaround time is then calculated as waiting time + burst time.

Step 3: Results and Metrics

• After all processes finish, the algorithm displays:

o Each process’s arrival, burst, waiting, and turnaround times.
o The average waiting and average turnaround times of all processes.

This gives a clear picture of how long processes waited and how efficiently the CPU was
utilized.

5. Example for Understanding

Let’s consider an example with 4 processes:

Process Arrival Time Burst Time

P1 3 8
P2 3 5
P3 5 5
P4 4 7
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Step 1: Sort by Arrival Time

Since P1 and P2 arrive together, P1 is taken first because it appears first in the list.
So, the order of execution: P1 → P2 → P4 → P3

Step 2: Calculate Waiting & Turnaround Times

PID Arrival Burst Waiting Turnaround

P1 3 8 0 8
P2 3 5 8 13
P4 4 7 12 19
P3 5 5 18 23

Step 3: Averages

Average Waiting Time = (0 + 8 + 12 + 18) / 4 = 9.5

Average Turnaround Time = (8 + 13 + 19 + 23) / 4 = 15.75

6. Advantages of FCFS

1. Simple to implement — uses a basic queue structure.

2. Fair — every process gets CPU in order of arrival.
3. No starvation — every process is eventually served.
4. Predictable — easy to estimate completion order.

7. Disadvantages of FCFS

1. Non-preemptive: Once a process starts, it cannot be interrupted.

2. Convoy Effect: Short processes get delayed behind long ones.
3. Poor response time: Not suitable for interactive or real-time systems.
4. Idle CPU time: If the first process arrives late, the CPU remains idle.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

8. Real-world Analogy

Imagine a single-barber shop where customers arrive at different times.

• The barber serves the first customer who arrived first.

• Others must wait until the barber finishes the current haircut.
• If a customer arrives while the barber is free, they are immediately served.
This analogy perfectly represents how FCFS handles processes — simple, fair, but
sometimes inefficient when longer “customers” arrive first.

9. Summary

The FCFS scheduling algorithm is the foundation for understanding CPU scheduling.
It ensures fairness and is easy to implement, but it is not efficient for all types of workloads
due to the convoy effect.

Despite its limitations, FCFS is crucial for learning:

• The concept of non-preemptive scheduling,

• The role of arrival and burst times, and
• How to calculate and analyze waiting and turnaround times.

In short, FCFS helps students grasp the fundamental mechanics of process scheduling,
serving as a stepping stone to advanced algorithms like SJF, Round Robin, and Priority
Scheduling.

10. Gantt Chart Illustration

The Gantt chart represents the timeline of process execution. For the earlier example:

Process Arrival Burst

P1 3 8
P2 3 5
P4 4 7
P3 5 5

Execution Order (FCFS): P1 → P2 → P4 → P3

 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Step-by-step timeline:

1. Time 0–3: CPU idle (no process has arrived yet).

2. Time 3–11: P1 executes (burst time 8).
3. Time 11–16: P2 executes (burst time 5).
4. Time 16–23: P4 executes (burst time 7).
5. Time 23–28: P3 executes (burst time 5).

Gantt Chart Representation

Time: 0 3 11 16 23 28
|-----|-------|-------|-------|-------|
CPU: Idle P1 P2 P4 P3

• Idle period (0–3): CPU waits for the first process to arrive.
• Execution blocks: Each process executes continuously for its burst time.
• Completion times: P1 = 11, P2 = 16, P4 = 23, P3 = 28

11. Observations from the Gantt Chart

1. Fair Execution: Processes are served in order of arrival.

2. Waiting Time: Calculated as start time − arrival time for each process.
3. Turnaround Time: Calculated as completion time − arrival time.
4. Convoy Effect Visible: Shorter processes (like P2 or P3) must wait if a longer
process (like P1 or P4) is executing.

Code:

#include <stdio.h>

typedef struct {
int pid;
int arrival_time;
int burst_time;
int waiting_time;
int turnaround_time;
} Process;

// Function to calculate waiting and turnaround times

void calculateTimes(Process p[], int n) {
int current_time = 0;
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

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

if (current_time < p[i].arrival_time) {
current_time = p[i].arrival_time; // CPU waits if process hasn't
arrived
}

p[i].waiting_time = current_time - p[i].arrival_time;

current_time += p[i].burst_time;
p[i].turnaround_time = p[i].waiting_time + p[i].burst_time;
}
}

// Function to display process table

void printTable(Process p[], int n) {
printf("\nPID\tArrival\tBurst\tWaiting\tTurnaround\n");
for (int i = 0; i < n; i++) {
printf("P%d\t%d\t%d\t%d\t%d\n",
p[i].pid,
p[i].arrival_time,
p[i].burst_time,
p[i].waiting_time,
p[i].turnaround_time);
}
}

// Function to calculate and display averages

void calculateAverage(Process p[], int n) {
float total_wait = 0, total_turnaround = 0;

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

total_wait += p[i].waiting_time;
total_turnaround += p[i].turnaround_time;
}

printf("\nAverage Waiting Time: %.2f", total_wait / n);

printf("\nAverage Turnaround Time: %.2f\n", total_turnaround / n);
}

int main() {
int n;
Process p[100];

printf("Enter number of processes: ");

 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

scanf("%d", &n);

printf("Enter Arrival Time and Burst Time for each process:\n");

for (int i = 0; i < n; i++) {
p[i].pid = i + 1;
printf("Process %d:\n", p[i].pid);
printf("Arrival Time: ");
scanf("%d", &p[i].arrival_time);
printf("Burst Time: ");
scanf("%d", &p[i].burst_time);
}

// Sort processes by arrival time (FCFS requirement)

for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i].arrival_time > p[j].arrival_time) {
Process temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}

calculateTimes(p, n);
printTable(p, n);
calculateAverage(p, n);

return 0;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Output:

Learning Outcomes:

1. Successfully understood the First-Come, First-Served (FCFS) scheduling algorithm and its role in
process scheduling.
2. Successfully implemented process scheduling in C using arrays and structures.
3. Successfully calculated waiting times and turnaround times for multiple processes.
4. Successfully handled processes based on their arrival times, ensuring correct execution order.
5. Successfully computed and verified average waiting time and average turnaround time for all
processes.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Course Outcomes:

Students successfully developed a strong understanding of process scheduling in operating systems.

They implemented the First-Come, First-Served (FCFS) scheduling algorithm in C, calculated waiting
and turnaround times, and ensured processes were executed in the correct order based on arrival
times. By performing this experiment, students gained practical skills in analyzing scheduling
performance, computing averages, and managing multiple processes efficiently in a simulated
environment.

Conclusion:

The First-Come, First-Served (FCFS) scheduling algorithm was successfully implemented in C. The
program demonstrated how processes are scheduled based on their arrival times, calculated
individual waiting and turnaround times accurately, and computed average waiting and turnaround
times for all processes. Through this practical, students observed the behavior of FCFS scheduling,
understood its advantages and limitations, and gained hands-on experience in process management,
sequence execution, and performance analysis in operating systems.

Viva Questions:

1. What is the main principle behind the First-Come, First-Served (FCFS) scheduling algorithm?
2. How does the program calculate waiting time for each process?
3. How is turnaround time computed in this program?
4. What happens if two processes have the same arrival time?
5. Why is it important to sort processes by arrival time before scheduling?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—5 : Shortest Job First (Non-preemptive) Scheduling

Aim:

To implement the Shortest Job First (SJF) CPU scheduling algorithm without preemption in C, calculate
the waiting time and turnaround time for each process, and determine the average waiting and
turnaround times.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the Shortest Job First (SJF) scheduling algorithm and its significance in CPU scheduling.
2. Learn the difference between preemptive and non-preemptive SJF scheduling.
3. Implement the non-preemptive SJF scheduling algorithm in C using arrays and structures.
4. Calculate waiting time, turnaround time, and completion time for multiple processes.
5. Analyze and compare the efficiency of SJF scheduling with other CPU scheduling algorithms such
as FCFS.

Theory:

1. Introduction
In operating systems, CPU scheduling is essential for managing how processes are
executed. The Shortest Job First (SJF) scheduling algorithm is a non-preemptive CPU
scheduling strategy that selects the process with the smallest burst time (execution time)
from the ready queue to execute next.

• Non-preemptive means once a process starts execution, it runs to completion without

interruption.
• SJF aims to minimize average waiting time and average turnaround time,
improving CPU efficiency.
• It is particularly effective in scenarios where processes have varying burst times.

Real-life Analogy:
Imagine a print shop where multiple print jobs arrive. The printer always chooses the job that
will take the least time to complete next. This ensures shorter jobs are completed quickly,
preventing long waiting times for smaller tasks.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2. Key Concepts in SJF Scheduling

• Arrival Time (AT): The time when a process enters the ready queue.
• Burst Time (BT): The CPU execution time required by the process.
• Completion Time (CT): The time at which a process finishes execution.
• Turnaround Time (TAT): Total time spent by a process from arrival to completion.
Formula: TAT = CT − AT
• Waiting Time (WT): Time a process spends waiting in the ready queue before
execution.
Formula: WT = TAT − BT

3. Working of Non-Preemptive SJF Scheduling

1. At any given time, select the process with the shortest burst time from the ready
queue that has already arrived.
2. Execute the selected process to completion.
3. Update completion time, waiting time, and turnaround time for that process.
4. Repeat steps 1–3 until all processes are executed.
5. If no process has arrived yet, CPU remains idle until the first process arrives.

Tie-breaker Rule:
If two or more processes have the same burst time, select the one that arrived earlier.

4. Step-by-Step Example

Process Arrival Time Burst Time

P1 4 5
P2 3 5

• At time 3, P2 has arrived (burst 5). CPU executes P2.

• At time 8, P1 has arrived (burst 5). CPU executes P1.

PID AT BT CT TAT WT
P1 4 5 13 9 4
P2 3 5 8 5 0

Average TAT: (9 + 5)/2 = 7.0

Average WT: (4 + 0)/2 = 2.0
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

5. Advantages of SJF
1. Minimizes average waiting time compared to FCFS.
2. Efficient for processes with known burst times.
3. Reduces the turnaround time for shorter processes.

6. Disadvantages of SJF
1. Requires prior knowledge of burst times, which may not always be available.
2. Longer processes may experience starvation if short processes keep arriving.
3. Non-preemptive version cannot adapt if a shorter process arrives while a longer
process is running.

7. Summary
Non-preemptive SJF scheduling provides an optimized way to reduce waiting time and
turnaround time for processes. It is simple, fair for shorter jobs, but may cause starvation
for longer processes. Understanding SJF lays the foundation for learning preemptive
scheduling techniques like Shortest Remaining Time First (SRTF).
8. Gantt Chart Illustration

Processes:

Process Arrival Time Burst Time

P1 4 5
P2 3 5

Step-by-step execution timeline (SJF, non-preemptive):

1. Time 0–3: CPU idle (no process has arrived yet)

2. Time 3–8: P2 executes (burst time 5)
3. Time 8–13: P1 executes (burst time 5)

Gantt Chart Representation:

Time: 0 3 8 13
|----|------|------|
CPU: Idle P2 P1
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Observations from Gantt Chart:

1. Idle Time: CPU waits until the first process arrives.

2. Process Order: P2 executes first because it arrives earlier, even though both have the
same burst time.
3. Waiting Times:
o P2: WT = 0 (starts at arrival)
o P1: WT = 8 − 4 = 4
4. Turnaround Times:
o P2: TAT = 8 − 3 = 5
o P1: TAT = 13 − 4 = 9

Code:

#include <stdio.h>

typedef struct {
int pid; // Process ID
int arrival_time;
int burst_time;
int completion_time;
int turnaround_time;
int waiting_time;
int is_completed;
} Process;

int main() {
int n, time = 0, completed = 0;
float total_turnaround = 0, total_waiting = 0;
Process p[100];

printf("Enter number of processes: ");

scanf("%d", &n);

// Input arrival and burst times

for (int i = 0; i < n; i++) {
p[i].pid = i + 1;
printf("Process %d Arrival Time: ", p[i].pid);
scanf("%d", &p[i].arrival_time);
printf("Process %d Burst Time: ", p[i].pid);
scanf("%d", &p[i].burst_time);
p[i].is_completed = 0;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

while (completed != n) {
int idx = -1;
int min_bt = 1e9;

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

if (p[i].arrival_time <= time && !p[i].is_completed) {
if (p[i].burst_time < min_bt) {
min_bt = p[i].burst_time;
idx = i;
}
if (p[i].burst_time == min_bt) {
// Tie-breaker: earlier arrival
if (p[i].arrival_time < p[idx].arrival_time) {
idx = i;
}
}
}
}

if (idx != -1) {
// Process the selected job
p[idx].completion_time = time + p[idx].burst_time;
p[idx].turnaround_time = p[idx].completion_time -
p[idx].arrival_time;
p[idx].waiting_time = p[idx].turnaround_time - p[idx].burst_time;

total_turnaround += p[idx].turnaround_time;
total_waiting += p[idx].waiting_time;

time = p[idx].completion_time;
p[idx].is_completed = 1;
completed++;
} else {
// No process is ready, increment time
time++;
}
}

// Output the table

printf("\nPID\tAT\tBT\tCT\tTAT\tWT\n");
for (int i = 0; i < n; i++) {
printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

p[i].pid,
p[i].arrival_time,
p[i].burst_time,
p[i].completion_time,
p[i].turnaround_time,
p[i].waiting_time);
}

printf("\nAverage Turnaround Time: %.2f\n", total_turnaround / n);

printf("Average Waiting Time: %.2f\n", total_waiting / n);

return 0;
}

Output:

Learning Outcomes:

1. Successfully understood the Shortest Job First (SJF) scheduling algorithm and its significance in
CPU scheduling.
2. Successfully distinguished between preemptive and non-preemptive SJF scheduling.
3. Successfully implemented the non-preemptive SJF scheduling algorithm in C using arrays and
structures.
4. Successfully calculated waiting time, turnaround time, and completion time for multiple
processes.
5. Successfully analyzed and compared the efficiency of SJF scheduling with other CPU scheduling
algorithms such as FCFS.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Course Outcomes:

Students successfully developed a strong understanding of CPU scheduling and process

management in operating systems. They implemented the Shortest Job First (SJF) non-preemptive
scheduling algorithm in C, calculated waiting time, turnaround time, and completion time for
multiple processes, and analyzed the execution order of processes. By performing this experiment,
students gained practical skills in evaluating scheduling efficiency, comparing SJF with other
scheduling algorithms like FCFS, and managing multiple processes effectively in a simulated
environment.

Conclusion:

The non-preemptive Shortest Job First (SJF) scheduling algorithm was successfully implemented in C.
The program accurately scheduled processes based on their burst times, calculated individual waiting
times, turnaround times, and completion times, and determined the average metrics. Through this
practical, students observed how SJF minimizes average waiting time compared to FCFS, understood
the behavior of non-preemptive scheduling, and gained hands-on experience in process sequencing,
performance analysis, and efficient CPU utilization. The experiment reinforced theoretical knowledge
of CPU scheduling and demonstrated practical application in operating systems.

Viva Questions:

1. What is the main principle behind the Shortest Job First (SJF) scheduling algorithm?
2. How does non-preemptive SJF differ from preemptive SJF?
3. How are waiting time, turnaround time, and completion time calculated in this program?
4. What happens if two processes have the same burst time?
5. Why does SJF usually result in a lower average waiting time compared to FCFS?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—6 : Round Robin (RR) Scheduling Algorithm

Aim:

To implement the Round Robin (RR) CPU scheduling algorithm in C, allocate CPU time to each process
using a fixed time quantum, calculate waiting time and turnaround time for each process, and
determine the average waiting and turnaround times.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the Round Robin (RR) scheduling algorithm and its significance in CPU scheduling.
2. Learn how time quantum affects process execution and CPU utilization.
3. Implement the Round Robin scheduling algorithm in C using arrays and structures.
4. Calculate waiting time, turnaround time, and completion time for multiple processes.
5. Analyze the performance of RR scheduling and compare it with other algorithms like FCFS and SJF.

Theory:

1. Introduction

Round Robin (RR) is a preemptive CPU scheduling algorithm designed to share the CPU
fairly among all ready processes. It assigns a fixed time slice called time quantum to each
process in the ready queue. When a process’s time quantum expires, the CPU switches to the
next process, ensuring that no process waits indefinitely.

• RR is widely used in time-sharing systems, where response time and fairness are
critical.
• Unlike FCFS, RR prevents long processes from blocking shorter ones for extended
periods.
• Preemption ensures that every process gets regular CPU attention.
• When a process executes for its TQ and is not finished, it is preempted and placed at
the end of the ready queue.
• The next process in the queue is given CPU time, and this cycle continues until all
processes are completed.
• RR is effective for interactive systems where response time and fairness are critical.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Real-life Analogy:
Imagine multiple customers at a single ATM. Each customer is allowed to use the machine
for a fixed time (time quantum). Once their time expires, the next customer uses the ATM,
and the previous customer waits for their next turn. This cycle continues until all customers
are done.

2. Key Concepts in RR Scheduling

Term Description
Time Quantum (TQ) Fixed duration for which a process executes before preemption.
Arrival Time (AT) Time at which a process enters the ready queue.
Burst Time (BT) Total CPU time required by a process.
Remaining Time (RT) Remaining CPU time for the process to complete.
Waiting Time (WT) Total time a process spends waiting in the ready queue.
Turnaround Time (TAT) Total time taken from process arrival to completion.
Completion Time (CT) Time at which a process finishes execution.

Formulas:

• Waiting Time (WT) = Turnaround Time (TAT) − Burst Time (BT)

• Turnaround Time (TAT) = Completion Time (CT) − Arrival Time (AT)

3. Algorithm for RR Scheduling

1. Initialize time = 0.
2. Input arrival time, burst time, and time quantum for all processes.
3. Initialize remaining_time = burst_time for all processes.
4. Repeat until all processes are completed:
a. For each process in the ready queue:
o If arrival_time <= time and remaining_time > 0:
▪ If remaining_time > TQ, execute for TQ and update
remaining_time -= TQ.
▪ Else, execute for remaining_time and mark process as completed.
▪ Update completion_time, turnaround_time, and waiting_time.
o If no process has arrived, increment time.
5. Calculate average waiting time and average turnaround time.
6. Display the results in tabular form.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

4. Step-by-Step Working

1. All ready processes are maintained in a circular queue.

2. CPU executes the first process in the queue for time quantum (TQ).
3. If the process completes within TQ, it leaves the queue.
4. If the process does not complete, it is moved to the end of the queue with remaining
burst time updated.
5. Repeat steps 2–4 until all processes are completed.
6. If no process has arrived at the current time, the CPU remains idle until the next
process arrives.

Observations:

• RR ensures fair CPU allocation to all processes.

• Smaller TQ improves response time but may increase context-switching overhead.
• Larger TQ may behave like FCFS, reducing fairness.

Example:

Input:
Process AT BT
P1 0 5
P2 1 3
P3 2 1

Time Quantum (TQ) = 2

Step-by-step Execution:

1. Time 0–2: P1 executes for 2 units → Remaining = 3

2. Time 2–4: P2 executes for 2 units → Remaining = 1
3. Time 4–5: P3 executes fully → Remaining = 0, completes
4. Time 5–7: P1 executes next 2 units → Remaining = 1
5. Time 7–8: P2 executes remaining 1 unit → completes
6. Time 8–9: P1 executes remaining 1 unit → completes
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Completion, Turnaround, and Waiting Times

Formulas:

• TAT = Completion Time − Arrival Time

• WT = TAT − Burst Time

PID AT BT Completion TAT WT

P1 0 5 9 9 4
P2 1 3 8 7 4
P3 2 1 5 3 2

Average WT: (4 + 4 + 2)/3 = 3.33

Average TAT: (9 + 7 + 3)/3 = 6.33

5. Gantt Chart (ASCII style)

Time: 0 2 4 5 7 8 9
|-----|-----|-----|-----|-----|-----|
CPU: P1 P2 P3 P1 P2 P1

Observations:

1. Idle Time: None. CPU starts immediately.

2. Process Execution: Each process executes in slices of the quantum.
3. Waiting Time: Accumulated while waiting for its turn.
4. Turnaround Time: Total time from arrival to completion.
5. CPU Utilization: High; all processes executed efficiently in round-robin order.

6. Advantages of RR Scheduling

1. Fair allocation of CPU to all processes.

2. Reduces starvation, as every process gets repeated chances.
3. Suitable for time-sharing systems requiring good response time.

7. Disadvantages of RR Scheduling

1. Frequent context switches may reduce CPU efficiency.

2. Performance depends heavily on time quantum selection.
3. Not ideal for processes with highly varying burst times.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

8. Summary

Round Robin scheduling is a preemptive, fair, and cyclic CPU allocation strategy. It
ensures all processes get CPU attention, prevents starvation, and is highly suitable for
interactive systems. Proper selection of time quantum balances response time and CPU
efficiency. Gantt charts illustrate the execution timeline and help calculate waiting and
turnaround times.

Code:

#include <stdio.h>

typedef struct {
int pid;
int burst_time;
int remaining_time;
int waiting_time;
int turnaround_time;
int arrival_time;
} Process;

int main() {
int n, time_quantum, time = 0, completed = 0;
Process p[100];

printf("Enter number of processes: ");

scanf("%d", &n);

// Input arrival and burst times for all processes

for (int i = 0; i < n; i++) {
p[i].pid = i + 1;
printf("Process %d Arrival Time: ", p[i].pid);
scanf("%d", &p[i].arrival_time);
printf("Process %d Burst Time: ", p[i].pid);
scanf("%d", &p[i].burst_time);
p[i].remaining_time = p[i].burst_time;
p[i].waiting_time = 0;
p[i].turnaround_time = 0;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

printf("Enter Time Quantum: ");

scanf("%d", &time_quantum);

int done;

// Loop until all processes are completed

while (completed != n) {
done = 1;

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

// Process must have arrived and have remaining time
if (p[i].arrival_time <= time && p[i].remaining_time > 0) {
done = 0;

if (p[i].remaining_time > time_quantum) {

time += time_quantum;
p[i].remaining_time -= time_quantum;
} else {
time += p[i].remaining_time;
p[i].remaining_time = 0;
completed++;

p[i].turnaround_time = time - p[i].arrival_time;

p[i].waiting_time = p[i].turnaround_time -
p[i].burst_time;
}
} else if (p[i].arrival_time > time) {
// If no process has arrived yet, increment time to next
arrival
if (done == 1) {
time = p[i].arrival_time;
done = 0;
i--; // Recheck this process after updating time
}
}
}
}

// Display results
printf("\nPID\tAT\tBT\tWT\tTAT\n");
float total_wt = 0, total_tat = 0;
for (int i = 0; i < n; i++) {
printf("P%d\t%d\t%d\t%d\t%d\n",
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

p[i].pid,
p[i].arrival_time,
p[i].burst_time,
p[i].waiting_time,
p[i].turnaround_time);

total_wt += p[i].waiting_time;
total_tat += p[i].turnaround_time;
}

printf("\nAverage Waiting Time: %.2f\n", total_wt / n);

printf("Average Turnaround Time: %.2f\n", total_tat / n);

return 0;
}

Output:
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Learning Outcomes:

1. Successfully understood the Round Robin (RR) scheduling algorithm and its significance in CPU
scheduling.
2. Successfully learned how time quantum affects process execution and CPU utilization.
3. Successfully implemented the Round Robin scheduling algorithm in C using arrays and structures.
4. Successfully calculated waiting time, turnaround time, and completion time for multiple
processes.
5. Successfully analyzed the performance of RR scheduling and compared it with other algorithms
like FCFS and SJF.

Course Outcomes:

Students successfully developed a comprehensive understanding of CPU scheduling using the Round
Robin (RR) algorithm. They implemented the RR scheduling algorithm in C, calculated waiting time,
turnaround time, and completion time for multiple processes, and observed the effect of time
quantum on CPU utilization and process execution order. Through this practical, students gained
practical skills in evaluating RR performance, comparing it with other scheduling algorithms like FCFS
and SJF, and managing multiple processes efficiently in a simulated environment.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Conclusion:

The Round Robin (RR) scheduling algorithm was successfully implemented in C. The program
accurately scheduled processes based on their arrival times and time quantum, calculated individual
waiting times, turnaround times, and completion times, and determined the average metrics. Through
this practical, students observed how RR ensures fair CPU allocation, efficient process rotation, and
minimized starvation, thereby achieving the aim of demonstrating practical process scheduling,
performance analysis, and effective CPU utilization in operating systems.

Viva Questions:

1. What is the main principle behind the Round Robin (RR) scheduling algorithm?
2. How does the time quantum affect the execution and waiting time of processes?
3. How are waiting time, turnaround time, and completion time calculated in this program?
4. What happens if a process’s burst time is less than the time quantum?
5. How does Round Robin compare to FCFS and SJF in terms of fairness and CPU utilization?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—7 : Banker's Algorithm

Aim:

To implement the Banker's Algorithm in C to determine whether the system is in a safe state, calculate
the need matrix, and find a safe sequence of process execution if it exists.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the Banker's Algorithm and its role in deadlock avoidance in operating systems.

2. Learn how to determine if a system is in a safe state.

3. Implement the Banker's Algorithm in C using matrices and arrays.

4. Calculate the Need matrix and track resource allocation for multiple processes.

5. Analyze the safe sequence and resource allocation to prevent deadlocks.

Theory:

1. Introduction
The Banker's Algorithm is a deadlock avoidance algorithm in operating systems. It ensures
that resource allocation never leads the system into an unsafe state. Each process declares its
maximum resource requirement, and the system checks whether granting requests keeps it in
a safe state. This algorithm is especially significant in multi-processing systems where
deadlocks must be prevented.

2. Key Concepts / Terms

Term Description
Allocation Resources currently assigned to a process.
Max Maximum resources a process may need.
Need Remaining resources a process may request (Need = Max − Allocation).
Available Resources currently available for allocation.
Safe State A state where there exists at least one sequence of execution allowing all
processes to finish.
Unsafe A state where no safe sequence exists; could lead to deadlock.
State
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

3. Algorithm / Step-by-Step Procedure

1. Input Allocation, Max, and Available matrices.

2. Calculate Need = Max − Allocation.
3. Initialize Finish[i] = false for all processes.
4. Find a process i such that Need[i] ≤ Available and Finish[i] = false.
o If found, allocate resources temporarily, add its Allocation to Available, mark
Finish[i] = true, add process to safe sequence.
5. Repeat Step 4 until all processes are finished or no such process is found.
6. If all Finish[i] = true → system is in safe state; else → unsafe state.

4. Step-by-Step Working / Example

Input:

• Processes = 5, Resources = 3
• Allocation Matrix:

P0: 0 1 0
P1: 2 0 0
P2: 3 0 2
P3: 2 1 1
P4: 0 0 2

• Max Matrix:

P0: 7 5 3
P1: 3 2 2
P2: 9 0 2
P3: 2 2 2
P4: 4 3 3

• Available: 3 3 2

Execution:

• Step 1: Check P1 → Need ≤ Available → Yes, execute → update Available

• Step 2: Check P3 → Need ≤ Available → Yes, execute → update Available
• Step 3: Check P4 → Need ≤ Available → Yes, execute → update Available
• Step 4: Check P0 → Need ≤ Available → Yes, execute → update Available
• Step 5: Check P2 → Need ≤ Available → Yes, execute → update Available

Safe Sequence: P1 → P3 → P4 → P0 → P2
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

5. Gantt Chart

Time: 0 1 2 3 4 5
CPU: P1 --> P3 --> P4 --> P0 --> P2

(Here, each arrow represents the completion of a process in order of the safe sequence.)

6. Observations

1. System is in a safe state; all processes can complete without deadlock.

2. Safe sequence ensures fair resource allocation.
3. Proper calculation of Need and Available is critical.

7. Advantages / Disadvantages

Advantages:

• Prevents deadlock proactively.

• Ensures safe sequence of execution.

Disadvantages:

• Requires knowledge of maximum resource needs in advance.

• Complex to implement for large systems.

8. Summary
The Banker's Algorithm is an essential deadlock avoidance technique. It simulates resource
allocation to check for safe states and ensures all processes can complete without waiting
indefinitely. Understanding this algorithm is crucial for designing reliable multi-processing
systems.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Code:

#include <stdio.h>

#define MAX_PROCESSES 10
#define MAX_RESOURCES 10

int main() {
int n, m; // Number of processes and resources
int alloc[MAX_PROCESSES][MAX_RESOURCES]; // Allocation matrix
int max[MAX_PROCESSES][MAX_RESOURCES]; // Max matrix
int need[MAX_PROCESSES][MAX_RESOURCES]; // Need matrix
int avail[MAX_RESOURCES]; // Available vector
int finish[MAX_PROCESSES] = {0}; // Finish array
int safe_seq[MAX_PROCESSES];

// Input number of processes and resources

printf("Enter number of processes: ");
scanf("%d", &n);
printf("Enter number of resources: ");
scanf("%d", &m);

// Input Allocation matrix

printf("\nEnter Allocation matrix:\n");
for (int i = 0; i < n; i++) {
printf("Process %d: ", i);
for (int j = 0; j < m; j++) {
scanf("%d", &alloc[i][j]);
}
}

// Input Max matrix

printf("\nEnter Max matrix:\n");
for (int i = 0; i < n; i++) {
printf("Process %d: ", i);
for (int j = 0; j < m; j++) {
scanf("%d", &max[i][j]);
}
}

// Input Available resources

printf("\nEnter Available resources: ");
for (int i = 0; i < m; i++) {
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

scanf("%d", &avail[i]);
}

// Calculate Need matrix = Max - Allocation

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
need[i][j] = max[i][j] - alloc[i][j];
}
}

// Banker's Algorithm to find safe sequence

int count = 0;
while (count < n) {
int found = 0;
for (int i = 0; i < n; i++) {
if (!finish[i]) {
int j;
for (j = 0; j < m; j++) {
if (need[i][j] > avail[j])
break;
}
if (j == m) {
// Process can be satisfied
for (int k = 0; k < m; k++) {
avail[k] += alloc[i][k];
}
safe_seq[count++] = i;
finish[i] = 1;
found = 1;
}
}
}
if (!found) {
printf("\nSystem is NOT in a safe state.\n");
return 1;
}
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

// Print the safe sequence

printf("\nSystem is in a SAFE state.\nSafe Sequence: ");
for (int i = 0; i < n; i++) {
printf("P%d", safe_seq[i]);
if (i != n - 1) printf(" -> ");
}
printf("\n");

return 0;
}

Output:
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Learning Outcomes:

1. Successfully understood the Banker's Algorithm and its significance in avoiding deadlocks in
operating systems.

2. Successfully learned how to calculate Need, Allocation, and Available matrices for multiple
processes and resources.

3. Successfully implemented the Banker's Algorithm in C to determine if a system is in a safe state.

4. Successfully identified a safe sequence of process execution when the system is safe.

5. Successfully analyzed resource allocation scenarios and understood how the algorithm prevents
unsafe states and potential deadlocks.

Course Outcomes:

Students successfully developed a comprehensive understanding of resource allocation and

deadlock avoidance in operating systems. They implemented the Banker's Algorithm in C to calculate
Need, Allocation, and Available matrices, determined safe states, and identified safe sequences for
multiple processes. Through this practical, students gained hands-on experience in evaluating
system safety, analyzing resource requests, and applying deadlock prevention techniques effectively
in simulated environments.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Conclusion:

The Banker's Algorithm was successfully implemented in C to manage resource allocation and
ensure system safety. The program accurately calculated the Need, Allocation, and Available
matrices, verified safe states, and identified safe sequences for all processes. Through this practical,
students observed how the algorithm prevents deadlocks, ensures fair resource distribution, and
maintains system stability, thereby achieving the aim of demonstrating practical deadlock avoidance
and safe resource management in operating systems.

Viva Questions:

1. What is the main purpose of the Banker's Algorithm in operating systems?

2. How is the Need matrix calculated, and why is it important?
3. What conditions must be satisfied for a system to be in a safe state?
4. What happens if a process requests resources that exceed the available amount?
5. How does the Banker's Algorithm help in preventing deadlocks?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—8 : FIFO Page Replacement

Aim:

To implement the First-In-First-Out (FIFO) page replacement algorithm in C, simulate page requests
using a reference string, track page faults and hits, and determine the total number of page faults for
a given number of frames.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the FIFO (First-In-First-Out) page replacement algorithm and its significance in
memory management.
2. Learn how page faults occur and how to track them in a system.
3. Implement the FIFO page replacement algorithm in C using arrays.
4. Simulate memory frames and page reference strings to observe page replacement behavior.
5. Analyze total page faults and hits to evaluate algorithm efficiency.

Theory:

1. Introduction
The FIFO (First-In-First-Out) page replacement algorithm is a classical memory management
technique used in operating systems to handle page faults. When a process references a page
that is not currently in memory, a page fault occurs. FIFO resolves this by replacing the
oldest page in memory, ensuring a simple and predictable approach to memory management.

• FIFO is commonly used in teaching operating system concepts due to its simplicity.
• Although easy to implement, FIFO does not always minimize page faults.
• It demonstrates the concept of memory frames, page hits, and page faults.

Real-life Analogy:
Imagine a queue at a ticket counter: the person who came first gets served first. Similarly, in
FIFO, the page that entered memory first is replaced first when a new page needs space.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2. Key Concepts / Terms

Term Description
Page A fixed-length block of virtual memory.
Frame A fixed-length block in physical memory where a page can reside.
Page Fault Occurs when the requested page is not in memory.
Hit Occurs when the requested page is already present in memory.
FIFO First-In-First-Out replacement policy; oldest page is replaced first.
Queue Front / Used to track which page entered memory first and which is next for
Rear replacement.

3. Algorithm / Step-by-Step Procedure

1. Initialize all memory frames as empty.

2. For each page in the reference string:
o If the page is already in memory → Hit; no replacement required.
o If the page is not in memory → Page Fault:
▪ Replace the oldest page in memory (front of the queue).
▪ Load the new page into memory at the rear of the queue.
3. Update front and rear pointers of the queue.
4. Keep a count of page faults and page hits.
5. Repeat until all pages in the reference string are processed.
6. Display total page faults at the end of the process.

4. Step-by-Step Working / Example

Input:

• Number of frames = 5
• Page Reference String = 7, 5, 47, 5, 65, 4, 7, 7, 5
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Execution Table:

Step Page Frame Status Event Page Faults

1 7 [7 - - - -] PF 1
2 5 [7 5 - - -] PF 2
3 47 [7 5 47 - -] PF 3
4 5 [7 5 47 - -] Hit 3
5 65 [7 5 47 65 -] PF 4
6 4 [7 5 47 65 4] PF 5
7 7 [7 5 47 65 4] Hit 5
8 7 [7 5 47 65 4] Hit 5
9 5 [7 5 47 65 4] Hit 5

Observations:

• Total Page Faults = 5

• Total Page Hits = 4
• FIFO replaces the oldest page when a page fault occurs.
• If a page is already in memory, it results in a hit, and frames remain unchanged.

5. Gantt Chart

Time: 0 1 2 3 4 5 6 7 8
Page: 7 5 47 5 65 4 7 7 5
Event: PF PF PF H PF PF H H H
Frames: [7 - - - -]
[7 5 - - -]
[7 5 47 - -]
[7 5 47 - -]
[7 5 47 65 -]
[7 5 47 65 4]
[7 5 47 65 4]
[7 5 47 65 4]
[7 5 47 65 4]

• PF → Page Fault
• H → Hit
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

6. Observations / Key Takeaways

1. FIFO always removes the page that has been in memory the longest.
2. Total page faults provide insight into the efficiency of the algorithm.
3. Page hits reduce unnecessary replacements, improving system performance.
4. FIFO is simple but can lead to more page faults in some scenarios (Belady’s
anomaly).
5. Queue-based implementation makes tracking the oldest page straightforward.

7. Advantages / Disadvantages

Advantages:

• Simple and easy to implement.

• Demonstrates basic concepts of page replacement and memory management.
• Suitable for small systems or educational purposes.

Disadvantages:

• Not optimal; may result in more page faults than other algorithms.
• Subject to Belady’s anomaly, where adding more frames increases page faults.
• Does not consider frequency or recency of page usage.

8. Summary
The FIFO page replacement algorithm provides a simple approach to handling page faults in
memory management. By replacing the oldest page in memory, it ensures a predictable and
straightforward behavior. While easy to implement, FIFO is not always the most efficient and
may result in unnecessary page faults in certain reference patterns. Understanding FIFO is
essential for grasping the fundamentals of virtual memory and page replacement strategies in
operating systems.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Code:

#include <stdio.h>

#define MAX_FRAMES 10
#define MAX_PAGES 100

int main() {
int frames[MAX_FRAMES];
int page_sequence[MAX_PAGES];
int front = 0, rear = 0;
int page_faults = 0;
int num_frames, num_pages;

// Initialize frames
for (int i = 0; i < MAX_FRAMES; i++) {
frames[i] = -1;
}

// Input number of frames

printf("Enter number of frames (max %d): ", MAX_FRAMES);
scanf("%d", &num_frames);

// Input number of pages

printf("Enter number of pages in the reference string (max %d): ",
MAX_PAGES);
scanf("%d", &num_pages);

// Input page reference string

printf("Enter the page reference string:\n");
for (int i = 0; i < num_pages; i++) {
scanf("%d", &page_sequence[i]);
}

printf("\nPage replacement process using FIFO:\n");

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

int current_page = page_sequence[i];
int found = 0;

// Check if page is already in frames

for (int j = 0; j < num_frames; j++) {
if (frames[j] == current_page) {
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

found = 1;
break;
}
}

if (!found) {
// Page fault occurs
frames[rear] = current_page;
rear = (rear + 1) % num_frames;
if (page_faults >= num_frames) {
front = (front + 1) % num_frames;
}
page_faults++;

// Print current frame status

printf("Page %d -> [", current_page);
for (int k = 0; k < num_frames; k++) {
if (frames[k] != -1)
printf("%d", frames[k]);
else
printf("-");
if (k != num_frames - 1)
printf(" ");
}
printf("] Page Fault\n");
} else {
// Page hit
printf("Page %d -> [", current_page);
for (int k = 0; k < num_frames; k++) {
if (frames[k] != -1)
printf("%d", frames[k]);
else
printf("-");
if (k != num_frames - 1)
printf(" ");
}
printf("] Hit\n");
}
}
printf("\nTotal Page Faults: %d\n", page_faults);

return 0;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Output:

Learning Outcomes:

1. Successfully understood the FIFO page replacement algorithm and its significance in memory
management.
2. Successfully learned how page faults occur and how they affect CPU and memory performance.
3. Successfully implemented the FIFO page replacement algorithm in C using arrays and queues.
4. Successfully tracked and calculated page faults for a given page reference string.
5. Successfully analyzed memory allocation and compared FIFO’s performance with other page
replacement strategies.

Course Outcomes:

Students successfully developed a strong understanding of memory management and page

replacement strategies in operating systems. They implemented the FIFO page replacement
algorithm in C, simulated page references, calculated page faults, and analyzed memory allocation
efficiency. Through this practical, students gained hands-on experience in evaluating the behavior of
FIFO, understanding how page faults occur, and comparing FIFO with other replacement strategies
to optimize memory usage in real-time systems.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Conclusion:

The FIFO page replacement algorithm was successfully implemented in C. The program accurately
simulated page references, maintained the frame queue, detected page hits and faults, and calculated
the total number of page faults. Through this practical, students observed how FIFO replaces the
oldest page in memory, understood the impact of frame size on page faults, and gained practical
experience in memory management techniques, thereby achieving the aim of demonstrating effective
page replacement and analyzing memory allocation efficiency.

Viva Questions:

1. What is the main principle behind the FIFO page replacement algorithm?
2. How does FIFO decide which page to replace when a page fault occurs?
3. How do the number of frames affect the number of page faults in FIFO?
4. What is the difference between a page hit and a page fault?
5. Can FIFO suffer from Belady’s anomaly? Explain.

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—9 : LRU Page Replacement

Aim:

To implement the Least Recently Used (LRU) page replacement algorithm in C, simulate page requests
using a reference string, track page hits and page faults, and determine the total number of page faults
for a given number of memory frames.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Learning Objectives:

1. Understand the Least Recently Used (LRU) page replacement algorithm and its significance in
memory management.

2. Learn how page faults occur and how LRU tracks the least recently used pages.

3. Implement the LRU page replacement algorithm in C using arrays.

4. Simulate memory frames and page reference strings to observe page replacement behavior.

5. Analyze total page faults and hits to evaluate algorithm efficiency.

Theory:

1. Introduction

The Least Recently Used (LRU) page replacement algorithm is a fundamental memory
management technique in operating systems. It is used to handle page faults in virtual
memory systems by replacing the page that has not been accessed for the longest time.

• LRU is crucial in multi-tasking systems where minimizing page faults is necessary for
performance.
• By predicting that recently used pages are more likely to be used again, LRU provides
a practical approach to approximate the optimal page replacement strategy.
• This algorithm is widely implemented in operating systems, cache management, and
memory-intensive applications.

Real-life Analogy:
Consider a library with limited shelf space. When a new book arrives and all shelves are full,
the librarian removes the book that hasn’t been borrowed for the longest time. Similarly,
LRU replaces the page that has not been used for the longest duration.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

2. Key Concepts / Terms

Term Description
Page A fixed-length block of virtual memory.
Frame A fixed-length block in physical memory to store a page.
Page Fault Occurs when a referenced page is not in memory.
Hit Occurs when the requested page is already present in memory.
LRU Least Recently Used page replacement policy; replaces the page with the
oldest last usage.
Recent Array used to track last usage time for each frame.
Array

Formulas:
While LRU does not use formulas like CPU scheduling, the concept of "last usage time" is
crucial:

• Replace page i if recent[i] is minimum (least recently used).

3. Algorithm / Step-by-Step Procedure

1. Initialize all memory frames as empty.

2. Initialize an array to track the last usage time of each page in memory.
3. For each page in the reference string:
a. If the page is in memory → Hit: update its usage time.
b. If the page is not in memory → Page Fault:
o If an empty frame exists, place the page there.
o Else, find the frame with the smallest usage time (least recently used) and
replace it.
4. Update the usage time array after every page access.
5. Increment the page fault counter when a page is replaced.
6. Repeat until all pages in the reference string are processed.
7. Display total page faults at the end of the process.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

4. Step-by-Step Working / Example

Input:

• Number of frames = 2
• Page Reference String = 4, 5, 4, 3, 4

Execution Table:

Step Page Frame Status Event Page Faults

1 4 [4 -] PF 1
2 5 [4 5] PF 2
3 4 [4 5] Hit 2
4 3 [3 5] PF 3
5 4 [4 3] PF 4

Observations:

• Initially, pages 4 and 5 caused page faults and were loaded into empty frames.
• Page 4 later caused a Hit since it was already in memory.
• Page 3 replaced page 4’s least recently used frame (page 4 had been used longer ago),
resulting in a page fault.
• Total Page Faults = 4, Total Page Hits = 1

5. Gantt Chart
Time: 0 1 2 3 4
Page: 4 5 4 3 4
Event: PF PF H PF PF
Frames: [4 -]
[4 5]
[4 5]
[3 5]
[4 3]

• PF → Page Fault
• H → Hit
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

6. Observations / Key Takeaways

1. LRU replaces the page that has not been accessed for the longest time.
2. Page hits reduce unnecessary replacements and improve performance.
3. The total number of page faults depends on the number of frames and the reference
string pattern.
4. LRU is more efficient than FIFO in most real-world usage patterns.
5. The algorithm requires tracking the usage of all pages, which may increase overhead.

7. Advantages / Disadvantages

Advantages:

• Reduces page faults compared to FIFO in many scenarios.

• Retains frequently used pages in memory longer.
• Simple concept and straightforward to simulate.

Disadvantages:

• Requires extra memory to store usage information.

• Slightly more complex to implement than FIFO.
• Overhead may be high for large numbers of frames or high-frequency page accesses.

8. Summary

The LRU page replacement algorithm efficiently handles memory by removing the least
recently used page on a page fault. By keeping track of page usage history, LRU improves
system performance and reduces page faults compared to FIFO. Understanding LRU is
crucial for optimizing memory utilization and designing effective virtual memory systems in
operating systems.

• gcc — GNU C Compiler

• Ex9.c — your source file
• -o pc — output binary name (pc)
• -lm — links the math library (for sqrt())

Then you can execute it like: ./pc

 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Code:

#include <stdio.h>

#define MAX_FRAMES 10
#define MAX_PAGES 100

int main() {
int frames[MAX_FRAMES], recent[MAX_FRAMES];
int page_sequence[MAX_PAGES];
int num_frames, num_pages;
int page_faults = 0, time = 0;

// Initialize frames
for (int i = 0; i < MAX_FRAMES; i++) {
frames[i] = -1;
recent[i] = -1;
}

// Input number of frames

printf("Enter number of frames (max %d): ", MAX_FRAMES);
scanf("%d", &num_frames);

// Input number of pages

printf("Enter number of pages in the reference string (max %d): ",
MAX_PAGES);
scanf("%d", &num_pages);

// Input page reference string

printf("Enter the page reference string:\n");
for (int i = 0; i < num_pages; i++) {
scanf("%d", &page_sequence[i]);
}

printf("\nPage replacement process using LRU:\n");

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

int current_page = page_sequence[i];
int found = 0;

// Check if page is already in frames (Hit)

for (int j = 0; j < num_frames; j++) {
if (frames[j] == current_page) {
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

found = 1;
recent[j] = time++; // Update usage time
break;
}
}

if (!found) {
// Page Fault
int replace_index = -1;

// Look for an empty frame

for (int j = 0; j < num_frames; j++) {
if (frames[j] == -1) {
replace_index = j;
break;
}
}

// If no empty frame, find least recently used

if (replace_index == -1) {
int lru_time = recent[0];
replace_index = 0;

for (int j = 1; j < num_frames; j++) {

if (recent[j] < lru_time) {
lru_time = recent[j];
replace_index = j;
}
}
}

frames[replace_index] = current_page;
recent[replace_index] = time++;
page_faults++;

// Print current frame status

printf("Page %d -> [", current_page);
for (int k = 0; k < num_frames; k++) {
if (frames[k] != -1)
printf("%d", frames[k]);
else
printf("-");
if (k != num_frames - 1)
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

printf(" ");
}
printf("] Page Fault\n");
} else {
// Page Hit
printf("Page %d -> [", current_page);
for (int k = 0; k < num_frames; k++) {
if (frames[k] != -1)
printf("%d", frames[k]);
else
printf("-");
if (k != num_frames - 1)
printf(" ");
}
printf("] Hit\n");
}
}

printf("\nTotal Page Faults: %d\n", page_faults);

return 0;
}

Output:
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Learning Outcomes:

1. Successfully understood the Least Recently Used (LRU) page replacement algorithm and its
importance in efficient memory management.
2. Successfully learned how page faults occur and how the LRU algorithm identifies and replaces
the least recently used pages.
3. Successfully implemented the LRU page replacement algorithm in C using arrays and logical
tracking mechanisms.
4. Successfully simulated memory frames and page reference strings to observe and analyze the
behavior of page replacement.
5. Successfully evaluated total page faults and hits to assess the effectiveness and performance of
the LRU algorithm.

Course Outcomes:

Students successfully developed a strong understanding of memory management and page

replacement strategies in operating systems. They implemented the Least Recently Used (LRU) page
replacement algorithm in C, simulated page references, calculated page faults, and observed
memory frame behavior. Through this practical, students gained hands-on experience in tracking the
least recently used pages, analyzing page replacement efficiency, and comparing LRU performance
with other strategies to optimize memory utilization in real-time systems.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Conclusion:

The Least Recently Used (LRU) page replacement algorithm was successfully implemented in C. The
program accurately simulated page references, tracked page hits and faults, and maintained memory
frames based on the least recently used principle. Through this practical, students observed how LRU
minimizes unnecessary replacements compared to simpler strategies like FIFO, understood the impact
of frame size on page faults, and gained practical experience in memory management techniques. This
achieved the aim of demonstrating effective page replacement and analyzing memory allocation
efficiency in operating systems.

Viva Questions:

1. What is the main principle behind the Least Recently Used (LRU) page replacement algorithm?
2. How does LRU decide which page to replace when a page fault occurs?
3. How are page hits and page faults identified in the LRU algorithm?
4. How does the number of frames affect the total page faults in LRU?
5. Compare LRU with FIFO in terms of page replacement efficiency and practical usage.

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Experiment No.—10 : File System Implementation

Aim:

To implement and design a simple file system in C that simulates file creation, reading, deletion, and
listing on a virtual disk, using block-based storage management.

Tools Used:

Programming Language: C

Compiler/IDE: Visual Studio, GCC, or any other suitable IDE

Operating System/Environment: Windows Subsystem for Linux (WSL) or Linux-based system

Storage Simulation: Virtual disk file (virtual_disk.bin) to simulate block-based storage

Learning Objectives:

1. Successfully understand the structure and design of a simple file system using C.

2. Learn how to simulate disk storage using a virtual disk file.

3. Implement basic file operations: create, read, delete, and list files.

4. Understand block allocation, file metadata, and directory management.

5. Analyze file system behavior, storage utilization, and block allocation efficiency.

Theory:

1. Introduction

A File System is a method and data structure that the operating system uses to control how
data is stored and retrieved on a storage medium. Without a file system, data would be one
large block, making it impossible to distinguish between different files.

This practical implements a simple file system in C using a virtual disk file, allowing us to
simulate file storage and operations without a real disk. The file system supports the
following operations:

• Create File – allocate space on the disk, store content, and update metadata.
• Read File – retrieve file content from the virtual disk.
• Delete File – remove the file’s metadata and mark blocks as free.
• List Files – display all files in the directory with their metadata.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Significance

• Provides hands-on understanding of block-based storage, file metadata, and

directory structures.
• Illustrates concepts of contiguous memory allocation, virtual disks, and basic file
operations.
• Helps in understanding memory management in operating systems and simulating
disk-based storage systems in a controlled environment.

Real-life Analogy

Think of the virtual disk as a library shelf:

• Each block is a slot on the shelf.

• Each file is a book that occupies a certain number of slots.
• The directory is the library catalog that keeps track of which book is on which slots,
its size, and its name.

When a new book (file) comes in:

• If slots are available → place the book.

• If a book needs to be removed → update catalog and free the slots.

2. Key Concepts / Terms

Term Description
Virtual Disk Simulated storage file that acts as a disk.
Block Fixed-size unit of storage on the virtual disk.
File Entry Metadata structure storing filename, starting block, number of blocks,
size, and usage flag.
Directory Array of File Entries representing all files on the disk.
Block Mechanism to assign disk blocks to a file; here, contiguous allocation is
Allocation used.
Page / Block Size of each storage block; in this case, 512 bytes.
Size
Maximum Files Maximum number of files the system can track, e.g., 100.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

3. Algorithm / Step-by-Step Procedure

1. Initialize File System

o Check if virtual disk exists; if not, create a file of size 1 MB filled with zeros.
o Initialize the directory with empty entries (is_used = 0).
2. Create File
o Input filename and content.
o Calculate number of blocks required (ceil(file_size / block_size)).
o Search for contiguous free blocks on the virtual disk.
o If space exists, write content to disk and update directory metadata.
3. Read File
o Input filename.
o Search the directory for a matching entry.
o Retrieve content from the virtual disk using starting block and size.
4. Delete File
o Input filename.
o Search the directory and mark is_used = 0.
o Freed blocks can now be reused for new files.
5. List Files
o Iterate through the directory and display metadata of all files in use.
6. Repeat
o Continue until the user exits the program.

4. Step-by-Step Working / Example

Input Example:

• Create files [Link] and [Link].

• [Link] content = "Hello World"
• [Link] content = "Data Structures"

Execution Table:

Step Operation File Name Disk Blocks Allocated Status

1 Create File [Link] 0–0 Success
2 Create File [Link] 1–1 Success
3 Read File [Link] 0–0 Output Content
4 List Files - - [Link], [Link]
5 Delete File [Link] 0 Success
6 List Files - - [Link]
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

5. Observations / Key Takeaways

1. Files occupy contiguous blocks on the disk.

2. Directory metadata helps track file locations and sizes.
3. Creating, reading, deleting, and listing files can be simulated without an actual disk.
4. The file system uses a simple contiguous allocation strategy; fragmentation may occur.
5. Disk space management and metadata tracking are crucial for file system integrity.

6. Advantages / Disadvantages

Advantages:

• Simple to understand and implement.

• Provides hands-on experience with disk storage simulation.
• Helps in understanding basic file management concepts.

Disadvantages:

• Contiguous allocation may lead to fragmentation.

• Limited scalability; only a fixed number of files and blocks.
• No advanced features like directories, permissions, or indexing.

7. Summary

This practical demonstrates the design of a basic file system in C using a virtual disk file.
Students gain experience in block allocation, file metadata management, and basic file
operations. By simulating file storage on a virtual disk, learners can understand how
operating systems manage disk storage, allocate space to files, and maintain directories,
achieving the aim of the experiment.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Code:

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

#define DISK_FILE "virtual_disk.bin"

#define DISK_SIZE (1024 * 1024) // 1 MB
#define BLOCK_SIZE 512
#define MAX_FILES 100
#define MAX_FILENAME 32

typedef struct {
char filename[MAX_FILENAME];
int start_block;
int num_blocks;
int size;
int is_used;
} FileEntry;

FileEntry directory[MAX_FILES];

// Initializes virtual disk and directory

void init_file_system() {
FILE *disk = fopen(DISK_FILE, "rb");
if (!disk) {
// Create new virtual disk
disk = fopen(DISK_FILE, "wb");
char zero = 0;
for (int i = 0; i < DISK_SIZE; i++)
fwrite(&zero, 1, 1, disk);
fclose(disk);
printf("Virtual disk created.\n");
} else {
fclose(disk);
}

// Initialize file directory

for (int i = 0; i < MAX_FILES; i++) {
directory[i].is_used = 0;
}
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

// Find free contiguous blocks on disk

int find_free_blocks(int num_blocks) {
int used_blocks[DISK_SIZE / BLOCK_SIZE] = {0};

// Mark used blocks

for (int i = 0; i < MAX_FILES; i++) {
if (directory[i].is_used) {
for (int j = 0; j < directory[i].num_blocks; j++) {
used_blocks[directory[i].start_block + j] = 1;
}
}
}

// Search for contiguous free blocks

int free_count = 0;
for (int i = 0; i < (DISK_SIZE / BLOCK_SIZE); i++) {
if (used_blocks[i] == 0) {
free_count++;
if (free_count == num_blocks) {
return i - num_blocks + 1;
}
} else {
free_count = 0;
}
}

return -1; // Not enough space

}

// Create a file
void create_file() {
char name[MAX_FILENAME];
char content[1024];

printf("Enter file name: ");

scanf("%s", name);

printf("Enter file content: ");

getchar(); // consume newline
fgets(content, sizeof(content), stdin);
int size = strlen(content);
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

int blocks_needed = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;

int start_block = find_free_blocks(blocks_needed);

if (start_block == -1) {
printf("Not enough disk space!\n");
return;
}

FILE *disk = fopen(DISK_FILE, "rb+");

fseek(disk, start_block * BLOCK_SIZE, SEEK_SET);
fwrite(content, 1, size, disk);
fclose(disk);

// Add to directory
for (int i = 0; i < MAX_FILES; i++) {
if (!directory[i].is_used) {
strcpy(directory[i].filename, name);
directory[i].start_block = start_block;
directory[i].num_blocks = blocks_needed;
directory[i].size = size;
directory[i].is_used = 1;
break;
}
}

printf("File '%s' created successfully.\n", name);

}

// List all files

void list_files() {
printf("Files in file system:\n");
for (int i = 0; i < MAX_FILES; i++) {
if (directory[i].is_used) {
printf("Name: %s | Size: %d bytes | Blocks: %d\n",
directory[i].filename,
directory[i].size,
directory[i].num_blocks);
}
}
}

// Read a file
void read_file() {
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

char name[MAX_FILENAME];
printf("Enter file name to read: ");
scanf("%s", name);

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

if (directory[i].is_used && strcmp(directory[i].filename, name) == 0)
{
char buffer[BLOCK_SIZE * directory[i].num_blocks + 1];
FILE *disk = fopen(DISK_FILE, "rb");
fseek(disk, directory[i].start_block * BLOCK_SIZE, SEEK_SET);
fread(buffer, 1, directory[i].size, disk);
buffer[directory[i].size] = '\0';
fclose(disk);
printf("File Content:\n%s\n", buffer);
return;
}
}

printf("File not found!\n");

}

// Delete a file
void delete_file() {
char name[MAX_FILENAME];
printf("Enter file name to delete: ");
scanf("%s", name);

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

if (directory[i].is_used && strcmp(directory[i].filename, name) == 0)
{
directory[i].is_used = 0;
printf("File '%s' deleted.\n", name);
return;
}
}

printf("File not found!\n");

}

int main() {
init_file_system();

int choice;
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

while (1) {
printf("\nSimple File System Menu:\n");
printf("1. Create File\n");
printf("2. Read File\n");
printf("3. Delete File\n");
printf("4. List Files\n");
printf("5. Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);

switch (choice) {
case 1: create_file(); break;
case 2: read_file(); break;
case 3: delete_file(); break;
case 4: list_files(); break;
case 5: exit(0);
default: printf("Invalid choice!\n");
}
}

return 0;
}
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Output:
SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Learning Outcomes:

1. Successfully understood the design and implementation of a simple file system in C.

2. Successfully learned how to create, read, list, and delete files in a simulated virtual disk
environment.
3. Successfully implemented memory block allocation and tracked file metadata using arrays and
structures.
4. Successfully simulated the concept of a virtual disk and understood the relationship between file
size, blocks, and storage.
5. Successfully analyzed file operations, observed resource usage, and ensured proper file
management in a controlled environment.

Course Outcomes:

Students successfully developed a strong understanding of file system design and management in
operating systems. They implemented a simple file system in C, including creating, reading, listing,
and deleting files on a simulated virtual disk. Through this practical, students gained hands-on
experience in managing file metadata, block allocation, and storage space, and they learned to
ensure efficient file operations while maintaining system integrity. This practical reinforced concepts
of file handling, disk management, and memory organization in real-world operating systems.
 SHRI G.P.M. DEGREE COLLEGE OF SCIENCE & COMMERCE
Department of Computer
Affiliated to University of Mumbai

Conclusion:

The simple file system was successfully implemented in C, simulating a virtual disk with block-based
storage. The program allowed users to create, read, list, and delete files while managing disk space
efficiently. Through this practical, students observed how file metadata, block allocation, and storage
management work together to provide a functional file system. The implementation reinforced the
importance of organized storage, efficient access, and proper handling of file operations, achieving
the aim of demonstrating basic file system design and management in operating systems.

Viva Questions:

1. What is the purpose of creating a virtual disk in this file system implementation?
2. How does the program keep track of files and their locations on the disk?
3. Explain how a file is read from the virtual disk. What happens if the file does not exist?
4. How does the program determine free space when creating a new file?
5. What are the advantages and limitations of this simple file system design?

For Faculty use:

Correction Parameters Formative Timely Completion of Attendance Learning

Assessment[40%] Practical[40%] Attitude[20%]