22BCE11444 Dhruv Jadhav

School of Computer Science

&
Engineering

OPERATING SYSTEM
CSE3003
LAB FILE

REGISTRATION NUMBER: 22BCE11444

NAME: DHRUV JADHAV

Submitted to Submitted by
Dr. Santosh Kumar Sahoo Dhruv Jadhav
22BCE11444 Dhruv Jadhav

CONTENT

Ex no. Experiment Title Page Faculty

no. Sign
Study of Hardware/Software requirement of various operating
1.
system.
2. Implement CPU scheduling policies
3. Implement file storage allocation techniques
4. Implementation of Contiguous allocation techniques
5. Calculation of external and internal fragmentation.
Implementation of Compaction for the continually changing
6.
memory layout and calculate total movement of data
7. Implementation of resource allocation graph (RAG).
8. Implementation of Banker’s Algorithm.
Conversion of resource allocation graph (RAG) to wait-for-
9.
graph(WFG) for each type of method used for storing graph.
Implement the solution for Bounded Buffer (Producer
Consumer) problem usinginter process communication technique
Semaphores.
10. Implement the solution for Readers-Writers problem using inter
processcommunication technique – Semaphores.
Implement the solution for Dining-Philosopher problem using
inter processcommunication technique – Semaphores.
I. Write a program where parent process take average of the odd
numbers and child
process will take the average of even numbers present in a given
Aadhar number of a person. Use FORK and JOIN construct.
11.
II. Write a program where parent process finds additive primes
and child process
finds circular prime for a given prime list array. Use FORK and
JOIN construct.
22BCE11444 Dhruv Jadhav

Observation:
Process Management:

File Management:
22BCE11444 Dhruv Jadhav

1. FCFS (First Come First Serve)

22BCE11444 Dhruv Jadhav

2. SJF (Shortest Job First - Non-Preemptive)

22BCE11444 Dhruv Jadhav

3. Priority Scheduling (Preemptive)

processes = [
{'pid': 'P1', 'arrival': 0, 'burst': 5, 'priority': 2},
{'pid': 'P2', 'arrival': 1, 'burst': 3, 'priority': 1},
{'pid': 'P3', 'arrival': 2, 'burst': 1, 'priority': 3},
{'pid': 'P4', 'arrival': 3, 'burst': 2, 'priority': 2}
]

for p in processes:
p['remaining'] =
p['burst'] p['start'] =
None p['completed'] =
False

time = 0
completed_count = 0
order = []
total_wt = total_tat = 0

while completed_count < len(processes):

ready = [p for p in processes if p['arrival'] <= time and not
p['completed']] if ready:
highest = min(ready, key=lambda x:
x['priority']) if highest['start'] is None:
highest['start'] = time
highest['remaining'] -= 1
if highest['remaining'] == 0:
highest['completed'] = True
highest['completion'] = time +
1
highest['turnaround'] = highest['completion'] -
highest['arrival'] highest['waiting'] = highest['turnaround']
- highest['burst'] total_wt += highest['waiting']
total_tat += highest['turnaround']
order.append(highest)
22BCE11444 Dhruv Jadhav

4. Multilevel Queue Scheduling (Foreground -

RR, Background - FCFS)
from queue import Queue

foreground =
Queue() background
= Queue()
time_quantum = 2
time = 0

for p in processes:
p['remaining'] =
p['burst'] p['waiting'] =
0
p['turnaround'] = 0
p['started'] = False

completed = []
total_wt = total_tat = 0

while len(completed) < len(processes):

# Enqueue all processes that have just
arrived for p in processes:
if p['arrival'] == time:
if p['queue'] == 'foreground':
foreground.put(p)
else:
background.put(p)

if not
foreground.empty():
proc =
foreground.get() if
not proc['started']:
proc['start_time'] = time
proc['started'] = True
run_time = min(time_quantum, proc['remaining'])

# Check for new arrivals during the

run_time for t in range(1, run_time + 1):
time += 1
for p in processes:
if p['arrival'] == time:
if p['queue'] == 'foreground':
foreground.put(p)
else:
background.put(p)
22BCE11444 Dhruv Jadhav

proc['remaining'] -=
run_time if
proc['remaining'] > 0:
foreground.put(proc
) else:
proc['turnaround'] = time - proc['arrival']
proc['waiting'] = proc['turnaround'] -
proc['burst'] total_wt += proc['waiting']
total_tat += proc['turnaround']
completed.append(proc)

elif not
background.empty():
proc =
background.get() if
not proc['started']:
proc['start_time'] = time
proc['started'] = True

# Check for new arrivals during the background job

run_time = proc['remaining']
for t in range(1, run_time +
1): time += 1
for p in processes:
if p['arrival'] == time:
if p['queue'] == 'foreground':
foreground.put(p)
else:
background.put(p)

proc['remaining'] = 0
proc['turnaround'] = time - proc['arrival']
proc['waiting'] = proc['turnaround'] - proc['burst']
total_wt += proc['waiting']
total_tat += proc['turnaround']
completed.append(proc)
22BCE11444 Dhruv Jadhav

Observation:
(a) Contiguous Allocation using Array

(b) Linked List Allocation

import random

class Block:
def init (self, index):
self.index = index
self.next = None

def linked_allocation(free_blocks,
file_size): if len(free_blocks) <
file_size:
return None

blocks = random.sample(free_blocks,
file_size) head = Block(blocks[0])
current = head
for i in range(1, file_size):
current.next = Block(blocks[i])
22BCE11444 Dhruv Jadhav

current = current.next
return head

free_blocks = list(range(1, 21))

head = linked_allocation(free_blocks, 4)
current = head
while current:
print(f"Block {current.index}", end=" ->
") current = current.next

(c) Indexed Allocation

22BCE11444 Dhruv Jadhav

Python Code Implementation:

def first_fit(blocks, processes):
allocation = [-1] *
len(processes) temp_blocks =
blocks.copy()
for i in range(len(processes)):
for j in range(len(temp_blocks)):
if temp_blocks[j] >=
processes[i]: allocation[i]
= j temp_blocks[j] -=
processes[i] break
return allocation, temp_blocks

def best_fit(blocks, processes):

allocation = [-1] *
len(processes) temp_blocks =
blocks.copy()
for i in range(len(processes)):
best_idx = -1
for j in range(len(temp_blocks)):
if temp_blocks[j] >= processes[i]:
if best_idx == -1 or temp_blocks[j] <
temp_blocks[best_idx]: best_idx = j
if best_idx != -1:
allocation[i] = best_idx
temp_blocks[best_idx] -=
processes[i] return allocation,
temp_blocks

def worst_fit(blocks, processes):

allocation = [-1] *
len(processes) temp_blocks =
blocks.copy()
for i in range(len(processes)):
worst_idx = -1
for j in range(len(temp_blocks)):
if temp_blocks[j] >= processes[i]:
if worst_idx == -1 or temp_blocks[j] >
temp_blocks[worst_idx]: worst_idx = j
if worst_idx != -1:
allocation[i] =
worst_idx
temp_blocks[worst_idx] -=
processes[i] return allocation,
temp_blocks

# Input blocks and processes

blocks = [100, 500, 200, 300,
22BCE11444 Dhruv Jadhav

600]
processes = [212, 417, 112, 426]
22BCE11444 Dhruv Jadhav

# Run all 3 techniques

ff_allocation, ff_free = first_fit(blocks, processes)
bf_allocation, bf_free = best_fit(blocks, processes)
wf_allocation, wf_free = worst_fit(blocks, processes)

def print_result(title, allocation, free_blocks): print(f"\

n{title}")
for i, a in
enumerate(allocation): if a
!= -1:
print(f"Process {i+1} ({processes[i]} KB) -> Block
{a+1}") else:
print(f"Process {i+1} ({processes[i]} KB) -> Not Allocated")
print("Remaining Free Space:", free_blocks)

print_result("First-Fit Allocation", ff_allocation,

ff_free) print_result("Best-Fit Allocation",
bf_allocation, bf_free) print_result("Worst-Fit
Allocation", wf_allocation, wf_free)
22BCE11444 Dhruv Jadhav

Python Code Implementation:

# Contiguous Allocation with Fragmentation Calculation

files = [212, 417, 112, 426] # File sizes in KB

memory_blocks = [100, 500, 200, 300, 600] # Free memory block sizes in KB

def allocate(strategy):
blocks = memory_blocks.copy()
allocation = [-1] * len(files)
internal_frag = [0] *
len(files)

if strategy == 'first_fit':
for i, fsize in
enumerate(files): for j in
range(len(blocks)):
if blocks[j] >=
fsize:
allocation[i] =
j
internal_frag[i] = blocks[j] -
fsize blocks[j] = -1 # Mark
block as used break

elif strategy == 'best_fit':

for i, fsize in enumerate(files):
best_index = -1
for j in
range(len(blocks)): if
blocks[j] >= fsize:
if best_index == -1 or blocks[j] <
blocks[best_index]: best_index = j
if best_index != -1:
allocation[i] =
best_index
internal_frag[i] = blocks[best_index] - fsize
blocks[best_index] = -1

elif strategy == 'worst_fit':

for i, fsize in enumerate(files):
worst_index = -1
for j in
range(len(blocks)): if
blocks[j] >= fsize:
if worst_index == -1 or blocks[j] >
blocks[worst_index]: worst_index = j
if worst_index != -1:
allocation[i] =
22BCE11444 Dhruv Jadhav

worst_index
internal_frag[i] = blocks[worst_index] -
fsize blocks[worst_index] = -1
22BCE11444 Dhruv Jadhav

# Internal Fragmentation
total_internal = sum(internal_frag)

# External Fragmentation: sum of all unused

blocks external_frag = 0
for j in
range(len(blocks)): if
blocks[j] != -1:
external_frag += blocks[j]

return allocation, total_internal,

external_frag # Run all three strategies

strategies = ['first_fit', 'best_fit',
'worst_fit']
results = {}

for s in strategies:
alloc, internal, external = allocate(s)
results[s] = {
'allocation': alloc,
'internal_fragmentation': internal,
'external_fragmentation': external
}

# Print Results
"
print("\nObservation Table: Fragmentation )
print("Strategy | Internal Frag (KB) | External Frag
(KB)")
print(" ")
for strategy in strategies:
sname = strategy.replace('_', ' ').title().ljust(14)
i_frag = results[strategy]['internal_fragmentation']
e_frag = results[strategy]['external_fragmentation']
print(f"{sname} | {str(i_frag).ljust(20)} |
{e_frag}")
22BCE11444 Dhruv Jadhav

# Files (in KB)

files = [212, 417, 112, 426]

# Initial memory blocks (in KB)

initial_blocks = [100, 500, 200, 300,
600]

# Simulate memory with inserted files (first-fit allocation before

compaction) def first_fit_allocation(blocks, files):
memory = [{'size': b, 'allocated': False, 'file': None} for b in blocks]
internal_frag = 0
movement = 0

for f in files:
for block in memory:
if not block['allocated'] and block['size'] >= f:
block['allocated'] = True
block['file'] = f
internal_frag += block['size']
- f break

return memory, internal_frag

# Compaction Logic
def perform_compaction(memory):
# Move all allocated blocks to the
beginning compacted_memory = []
total_movement = 0

# Accumulate allocated
blocks for block in memory:
if block['allocated']:
compacted_memory.append({'size': block['file'], 'allocated':
True, 'file': block['file']})
total_movement += block['file'] # Simulate moving file data

# Add remaining as a single unallocated block (external fragment)

total_free = sum(block['size'] for block in memory if not
block['allocated']) if total_free > 0:
compacted_memory.append({'size': total_free, 'allocated': False, 'file':
None})

return compacted_memory, total_movement

# Run allocation
memory, internal_before = first_fit_allocation(initial_blocks, files)
22BCE11444 Dhruv Jadhav

# Show memory before compaction

print("\nMemory Layout Before
Compaction:") for i, block in
enumerate(memory):
print(f"Block {i+1}: Size = {block['size']} KB, Allocated =
{block['allocated']}, File = {block['file']}")

# Perform compaction
compacted_memory, data_movement = perform_compaction(memory)

# Show memory after compaction print("\

nMemory Layout After Compaction:") for
i, block in enumerate(compacted_memory):
print(f"Block {i+1}: Size = {block['size']} KB, Allocated =
{block['allocated']}, File = {block['file']}")

# Final Observation
internal_after = 0 # Internal fragmentation removed
external_after = sum(block['size'] for block in compacted_memory
if not block['allocated'])
# Observation Table
print("\nObservation Table: Compaction
Analysis") print(" "
print("Fragmentation Type )
| Before Compaction | After Compaction")
print(" ")
print(f"Internal | {internal_before:<20} |
Fragmentation {internal_after}")
| 0 | {external_after}")
print(f"External | | {data_movement}
Fragmentation print(f"Total N/A KB")
")
22BCE11444 Dhruv Jadhav

Observation:
Case 1: Single Instance of Resources

the Resource Allocation Graph (RAG) for Case 1 where each resource has only one
instance:

 Green edges show allocations (e.g., R1 is allocated to P1).

 Red edges show requests (e.g., P3 is requesting R1).

 Circles represent Processes, and Squares represent Resources.

22BCE11444 Dhruv Jadhav

Case 2: Multiple Instance of Resources

Here's the Resource Allocation Graph (RAG) for the case where multiple instances of
resources exist.

 Processes (P1, P2, P3) are shown as circles.

 Resources (R1, R2) are shown as squares with instance numbers (e.g.,
R1_1, R1_2).

 Green arrows represent allocations (resource → process).

 Red arrows represent requests (process → resource).

22BCE11444 Dhruv Jadhav

class ResourceAllocationGraph:
def init (self, processes, resources, instances=None):
self.processes = processes
self.resources = resources
self.instances = instances if instances else {r: 1 for r in resources}
self.graph = {}

# Initialize nodes
for p in
processes:
self.graph[p] = []
for r in resources:
for i in range(self.instances[r]):
self.graph[f"{r}_{i+1}"] = []

def allocate(self, resource, instance_num,

process): # Resource instance -> Process
self.graph[f"{resource}_{instance_num}"].append(process)

def request(self, process, resource,

instance_num): # Process -> Resource
instance
self.graph[process].append(f"{resource}_{instance_num}")

def display_graph(self):
print("\n--- Resource Allocation Graph (Adjacency List)
---") for node in self.graph:
print(f"{node} --> {self.graph[node]}")

#
# G Example usage (Case 2: Multiple
instances) processes = ['P1', 'P2', 'P3']
resources = ['R1', 'R2']
instances = {'R1': 2, 'R2': 2}

rag = ResourceAllocationGraph(processes, resources, instances)

# Allocations (Resource instance → Process)

rag.allocate('R1', 1, 'P1')
rag.allocate('R2', 2, 'P2')

# Requests (Process → Resource instance)

rag.request('P1', 'R2', 1)
rag.request('P2', 'R1', 2)
rag.request('P3', 'R1', 1)

rag.display_graph()
22BCE11444 Dhruv Jadhav

Banker’s Algorithm

def calculate_need(maximum, allocation):

need = []
for i in
range(len(maximum)):
row = []
for j in range(len(maximum[0])):
row.append(maximum[i][j] - allocation[i]
[j])
need.append(row)
return need

def is_safe_state(processes, available, maximum,

allocation): n = len(processes)
m = len(available)
need = calculate_need(maximum, allocation)

finish = [False] *
n safe_sequence =
[] work =
available[:]

print("\nNeed
Matrix:") for i in
range(n):
print(f"P{i}:", need[i])

while len(safe_sequence) < n:

allocated_in_this_round =
False for i in range(n):
if not finish[i] and all(need[i][j] <= work[j] for j in
range(m)): for j in range(m):
work[j] += allocation[i][j]
safe_sequence.append(processes[
i]) finish[i] = True
allocated_in_this_round = True
if not
allocated_in_this_round:
break

is_safe = len(safe_sequence) ==
n return is_safe, safe_sequence

# Sample input
processes = ["P0", "P1", "P2", "P3", "P4"]
22BCE11444 Dhruv Jadhav

available = [3, 3, 2]
22BCE11444 Dhruv Jadhav

maximum = [
[7, 5,
3],
[3, 2,
2],
[9, 0,
2],
[2, 2,
2],
[4, 3, 3]
[0, 1, 0],
[2, 0, 0],
[3, 0, 2],
[2, 1, 1],
[0, 0, 2]
]

# Run Banker's algorithm

safe, sequence = is_safe_state(processes, available, maximum,
allocation)

# Output
print("\nBanker’s Algorithm
Result:") if safe:
print("✅ The system is in a SAFE state.")
print("Safe sequence:", " → ".join(sequence))
else:
print("❌ The system is in an UNSAFE state. Deadlock may
22BCE11444 Dhruv Jadhav

Implementation:
import networkx as nx
import matplotlib.pyplot as plt

# Step 1: Create Resource Allocation Graph

(RAG) rag = nx.DiGraph()

# Sample Input: P1 → R1, R1 → P2, P2 → R2, R2 → P1

(Deadlock) rag.add_edge('P1', 'R1') # P1 requests R1
rag.add_edge('R1', 'P2') # R1 is held by P2
rag.add_edge('P2', 'R2') # P2 requests R2
rag.add_edge('R2', 'P1') # R2 is held by P1

# Step 2: Visualize RAG

plt.figure(figsize=(8,
6)) pos =
nx.spring_layout(rag)
nx.draw(rag, pos, with_labels=True, node_size=2000, node_color='skyblue',
font_size=12, font_weight='bold', arrows=True)
plt.title("Resource Allocation Graph (RAG)")
plt.show()

# Step 3: Convert RAG to Wait-For Graph

(WFG) wfg = nx.DiGraph()

for u, v in rag.edges():
if u.startswith('P') and
v.startswith('R'): for successor in
rag.successors(v):
if successor.startswith('P'):
wfg.add_edge(u, successor)

# Step 4: Visualize WFG

plt.figure(figsize=(6,
5)) pos =
nx.spring_layout(wfg)
nx.draw(wfg, pos, with_labels=True, node_size=2000, node_color='lightgreen',
font_size=12, font_weight='bold', arrows=True)
plt.title("Wait-For Graph (WFG)")
plt.show()

# Step 5: Detect Deadlock (Cycle

Detection) try:
cycle = nx.find_cycle(wfg, orientation='original')
print("Deadlock Detected! Cycle:", cycle)
except nx.NetworkXNoCycle:
22BCE11444 Dhruv Jadhav

print("No Deadlock Detected.")

Observation:
22BCE11444 Dhruv Jadhav

Implementation:
import java.util.concurrent.*;

public class BoundedBuffer {

static Semaphore empty = new Semaphore(5);
static Semaphore full = new Semaphore(0);
static Semaphore mutex = new Semaphore(1);
static int[] buffer = new int[5];
static int in = 0, out = 0;

static class Producer extends Thread {

public void run() {
int item = 0;
try {
while (true) {
empty.acquire();
mutex.acquire();
buffer[in] =
item;
System.out.println("Produced: " +
item); in = (in + 1) % 5;
item++;
mutex.release();
full.release();
Thread.sleep(1000);
}
} catch (Exception e) {}
}
}

static class Consumer extends Thread {

public void run() {
try {
while (true) {
full.acquire();
mutex.acquire();
int item = buffer[out];
System.out.println("Consumed: " +
item); out = (out + 1) % 5;
mutex.release();
empty.release();
Thread.sleep(1500);
}
} catch (Exception e) {}
22BCE11444 Dhruv Jadhav

}
}

public static void main(String[] args)

{ new Producer().start();
new Consumer().start();
}
}
22BCE11444 Dhruv Jadhav

Implementation:
import java.util.concurrent.*;

public class ReadersWriters {

static Semaphore mutex = new
Semaphore(1); static Semaphore wrt =
new Semaphore(1); static int readCount
= 0;

static class Reader extends Thread

{ public void run() {
try {
mutex.acquire(
); readCount+
+;
if (readCount == 1)
wrt.acquire();
mutex.release();

System.out.println("Reader is reading");

Thread.sleep(1000);

mutex.acquire(
);
readCount--;
if (readCount == 0)
wrt.release();
mutex.release();

} catch (Exception e) {}
}
}

static class Writer extends Thread

{ public void run() {
try {
wrt.acquire();
System.out.println("Writer is
writing"); Thread.sleep(1000);
wrt.release();
} catch (Exception e) {}
}
}

public static void main(String[] args)

{ new Reader().start();
22BCE11444 Dhruv Jadhav

new
Writer().start();
new
Reader().start();
}

Implementation:
import java.util.concurrent.*;

public class DiningPhilosophers {

static Semaphore[] forks = new Semaphore[5];
static Semaphore mutex = new Semaphore(1);

static class Philosopher extends

Thread { int id;

Philosopher(int id) {
this.id = id;
}

public void run() {

try {
while (true) {
System.out.println("Philosopher " + id + " is
thinking."); Thread.sleep((int)(Math.random() * 1000));

mutex.acquire(); // avoid deadlock

forks[id].acquire();
forks[(id + 1) % 5].acquire();
mutex.release();

System.out.println("Philosopher " + id + " is

eating."); Thread.sleep(1000);

forks[id].release();
22BCE11444 Dhruv Jadhav

forks[(id + 1) % 5].release();
}
} catch (Exception e) {}
}
}

public static void main(String[] args)

{ for (int i = 0; i < 5; i++)
forks[i] = new
Semaphore(1); for (int i = 0; i
< 5; i++)
new Philosopher(i).start();
}
}
22BCE11444 Dhruv Jadhav

Implementation:
public class AadharAverage {

public static void main(String[] args) throws InterruptedException {

String aadhar = "987654321098"; // Example Aadhar
number int[] digits = new int[aadhar.length()];

for (int i = 0; i < aadhar.length(); i++)

{ digits[i] = aadhar.charAt(i) - '0';
}

Thread parent = new Thread(() ->

{ int sum = 0, count = 0;
for (int d : digits)
{ if (d % 2 !=
0) {
sum += d;
count++;
}
}
double avg = (count > 0) ? (double) sum / count : 0;
System.out.println("Parent (Odd) Average: " + avg);
});

Thread child = new Thread(() -

> { int sum = 0, count =
0;
for (int d : digits)
{ if (d % 2 ==
0) {
sum += d;
count++;
}
}
double avg = (count > 0) ? (double) sum / count : 0;
System.out.println("Child (Even) Average: " + avg);
});

child.start(); // Fork
child.join(); // Join (Child finishes before Parent)
parent.start();
}
}
22BCE11444 Dhruv Jadhav

Implementation:
public class PrimeFORKJOIN {
static int[] primeArray = {2, 3, 5, 7, 11, 13, 17, 31, 37, 113, 197, 199};

public static void main(String[] args)

{ Thread child = new Thread(() ->
{
System.out.println("Child Thread: Circular
Primes:"); for (int num : primeArray) {
if (isCircularPrime(num)) {
System.out.println(num + " is a Circular Prime");
}
}
});

child.start(); // FORK

try {
child.join(); // JOIN
} catch (InterruptedException e) {
e.printStackTrace();
}

System.out.println("\nParent Thread: Additive

Primes:"); for (int num : primeArray) {
if (isAdditivePrime(num)) {
System.out.println(num + " is an Additive Prime");
}
}
}

static boolean isPrime(int n)

{ if (n <= 1) return
false;
for (int i = 2; i <= Math.sqrt(n);
i++) if (n % i == 0) return
false;
return true;
}

static boolean isAdditivePrime(int

n) { int sum = 0, temp = n;
while (temp > 0) {
sum += temp %
10; temp /= 10;
}
22BCE11444 Dhruv Jadhav

return isPrime(n) && isPrime(sum);

}

static boolean isCircularPrime(int

n) { if (!isPrime(n)) return
false; String num =
String.valueOf(n);
for (int i = 0; i < num.length(); i++)
{ num = num.substring(1) +
num.charAt(0);
if (!isPrime(Integer.parseInt(num))) return false;
}
return true;
}