Scribd
Upload
8 views35 pages

OS Scheduling Algorithms Lab Report

This lab report presents various operating system scheduling algorithms, including FCFS, LRU, Priority, SJF, Optimal LRU, Page Replacement, and Round Robin. Each algorithm is accompanied by source code written in Java, demonstrating how to implement these scheduling techniques. The report is submitted by Sajal Udash as part of the Artificial Intelligence course at Kantipur College of Management and Information Technology.

Uploaded by

udashsajal8
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views35 pages

OS Scheduling Algorithms Lab Report

This lab report presents various operating system scheduling algorithms, including FCFS, LRU, Priority, SJF, Optimal LRU, Page Replacement, and Round Robin. Each algorithm is accompanied by source code written in Java, demonstrating how to implement these scheduling techniques. The report is submitted by Sajal Udash as part of the Artificial Intelligence course at Kantipur College of Management and Information Technology.

Uploaded by

udashsajal8
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

A

LAB REPORT

ON
Operating System

BY

Sajal Udash

Exam Roll No: 11369/20

Submitted to:
Indra PC

Department of Computer Science


Kantipur College of Management and Information Technology

In partial fulfillment of the requirements for the Course


Artificial Intelligience

Mid Baneshwor, Kathmandu

Jan, 2025

1
Contents
1. Write a program of FCFC algorithm in context of os?.........................................................................3
1.1. Source Code.....................................................................................................................................3
2. Write a program of Lru algorithm in context of os?.............................................................................6
2. Write a program of Priority algorithm in context of os?......................................................................8
1. Write a program of Sjf algorithm in context of os?............................................................................10
2. Write a program of Optimal LRU in context of os?..........................................................................14
3. Write a program of Page Replacement in context of os?.................................................................17
4. Write a program of Round Robin in context of os?..........................................................................21
5. Write a program of Banker Algorithm in context of os?...................................................................23
6. Write a program of Worst Fit in context of os?.................................................................................27
7. Write a program of Base Fit in context of os?....................................................................................31
8. Write a program of Next Fit in context of os?....................................................................................34

2
1. Write a program of FCFC algorithm in context of os?
1.1. Source Code

import [Link];
class Process {
int pid;
int arrivalTime;
int burstTime;
int completionTime;
int turnAroundTime;
int waitingTime;

public Process(int pid, int arrivalTime, int burstTime) {


[Link] = pid;
[Link] = arrivalTime;
[Link] = burstTime;
}
}

public class FCFS {

public static void main(String[] args) {


Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of processes: ");


int n = [Link]();

Process[] processes = new Process[n];

3
for (int i = 0; i < n; i++) {
[Link]("Enter arrival time of process " + (i + 1) + ": ");
int arrivalTime = [Link]();
[Link]("Enter burst time of process " + (i + 1) + ": ");
int burstTime = [Link]();
processes[i] = new Process(i + 1, arrivalTime, burstTime);
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (processes[i].arrivalTime > processes[j].arrivalTime) {
Process temp = processes[i];
processes[i] = processes[j];
processes[j] = temp;
}
}
}
int currentTime = 0;
for (Process process : processes) {
if (currentTime < [Link]) {
currentTime = [Link];
}
[Link] = currentTime + [Link];
[Link] = [Link] - [Link];
[Link] = [Link] - [Link];
currentTime = [Link];
}
[Link]("\nProcess\tArrival\tBurst\tCompletion\tTurnaround\tWaiting");
for (Process process : processes) {
[Link]([Link] + "\t" + [Link] + "\t" + [Link] + "\t" +
[Link] + "\t\t" + [Link] + "\t\t" + [Link]);

4
}
double totalTurnAroundTime = 0, totalWaitingTime = 0;
for (Process process : processes) {
totalTurnAroundTime += [Link];
totalWaitingTime += [Link];
}

[Link]("\nAverage Turnaround Time: %.2f\n", totalTurnAroundTime / n);


[Link]("Average Waiting Time: %.2f\n", totalWaitingTime / n);

[Link]();
}
}

Output

5
2. Write a program of Lru algorithm in context of os?
2.1. Source code
import [Link].*;
public class LRUCache {
private final int capacity;
private final LinkedHashSet<Integer> cache;
public LRUCache(int capacity) {
[Link] = capacity;
[Link] = new LinkedHashSet<>();
}
public void accessPage(int page) {
if ([Link](page)) {
[Link](page);
}
else if ([Link]() == capacity) {
int first = [Link]().next(); // Get the first element
[Link](first); // Remove the least recently used page
[Link]("Page " + first + " removed (LRU).");
}
[Link](page);
[Link]("Page " + page + " added.");
}
public void displayCache() {
[Link]("Cache: " + cache);
}

public static void main(String[] args) {


Scanner scanner = new Scanner([Link]);

[Link]("Enter the capacity of the LRU cache: ");

6
int capacity = [Link]();

LRUCache lruCache = new LRUCache(capacity);

[Link]("Enter the sequence of page references (-1 to stop):");


while (true) {
int page = [Link]();
if (page == -1) break;

[Link](page);
[Link]();
}

[Link]();
}
}

OUTPUT

1. Write a program of Priority algorithm in context of os?


1.1. Source code

7
import [Link];
import [Link];
import [Link];

class Process {
int id;
int arrivalTime;
int burstTime;
int priority;
int completionTime;
int turnaroundTime;
int waitingTime;

Process(int id, int arrivalTime, int burstTime, int priority) {


[Link] = id;
[Link] = arrivalTime;
[Link] = burstTime;
[Link] = priority;
}
}
public class PriorityScheduling {
public static void main(String[] args) {
List<Process> processes = new ArrayList<>();
[Link](new Process(1, 0, 10, 2));
[Link](new Process(2, 2, 5, 0));
[Link](new Process(3, 3, 8, 1));
priorityScheduling(processes);

[Link]("Process\tArrival\tBurst\tPriority\tCompletion\tTurnaround\tWaiting");
for (Process p : processes) {
[Link]("P%d\t%d\t%d\t%d\t\t%d\t\t%d\t\t%d\n",
[Link], [Link], [Link], [Link],
[Link], [Link], [Link]);
}
}

public static void priorityScheduling(List<Process> processes) {

[Link]([Link]((Process p) -> [Link]).thenComparingInt(p ->


[Link]));

int currentTime = 0;
for (Process process : processes) {
// If the CPU is idle, move the current time to the process's arrival time
if (currentTime < [Link]) {
currentTime = [Link];

8
}

[Link] = currentTime + [Link];


currentTime += [Link];

[Link] = [Link] - [Link];

[Link] = [Link] - [Link];


}
}
}

Output

1. Write a program of Sjf algorithm in context of os?


Source code
import [Link];
import [Link];
import [Link];

9
class Process {
int id;
int arrivalTime;
int burstTime;
int completionTime;
int turnaroundTime;
int waitingTime;

Process(int id, int arrivalTime, int burstTime) {


[Link] = id;
[Link] = arrivalTime;
[Link] = burstTime;
}
}

public class SJFScheduling {


public static void main(String[] args) {

List<Process> processes = new ArrayList<>();


[Link](new Process(1, 0, 7));
[Link](new Process(2, 2, 4));
[Link](new Process(3, 4, 1));
[Link](new Process(4, 5, 4));

sjfScheduling(processes);

[Link]("Process\tArrival\tBurst\tCompletion\tTurnaround\tWaiting");
for (Process p : processes) {
[Link]("P%d\t%d\t%d\t%d\t\t%d\t\t%d\n",

10
[Link], [Link], [Link],
[Link], [Link], [Link]);
}
}

public static void sjfScheduling(List<Process> processes) {

List<Process> completed = new ArrayList<>();


int currentTime = 0;

while ([Link]() < [Link]()) {

List<Process> available = new ArrayList<>();


for (Process p : processes) {
if (![Link](p) && [Link] <= currentTime) {
[Link](p);
}
}

if (![Link]()) {
Process shortest = [Link]()
.min([Link](p -> [Link]))
.orElse(null);

[Link] = currentTime + [Link];


currentTime += [Link];

11
[Link] = [Link] - [Link];
[Link] = [Link] - [Link];

[Link](shortest);
} else {

currentTime++;
}
}
}
}

Output

12
13
2. Write a program of Optimal LRU in context of os?
2.1. Source code
import [Link].*;

public class OptimalPageReplacement {


public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the number of frames: ");
int frameCount = [Link]();
[Link]("Enter the number of pages: ");
int pageCount = [Link]();
int[] pages = new int[pageCount];
[Link]("Enter the reference string (page numbers):");
for (int i = 0; i < pageCount; i++) {
pages[i] = [Link]();
}
List<Integer> frames = new ArrayList<>();
int pageFaults = 0;

[Link]("\nPage Replacement Process:");


for (int i = 0; i < pageCount; i++) {
int currentPage = pages[i];
if (![Link](currentPage)) {
pageFaults++;
if ([Link]() == frameCount) {
int pageToReplace = findOptimalPage(frames, pages, i + 1);
[Link]("Page " + pageToReplace + " removed (Optimal replacement).");
[Link]([Link](pageToReplace));
}
[Link](currentPage);

14
[Link]("Page " + currentPage + " added to the frame.");
} else {
[Link]("Page " + currentPage + " accessed (No page fault).");
}
[Link]("Current frames: " + frames);
}

[Link]("\nTotal page faults: " + pageFaults);


[Link]();
}
private static int findOptimalPage(List<Integer> frames, int[] pages, int startIndex) {
Map<Integer, Integer> futureUsage = new HashMap<>();
for (int framePage : frames) {
boolean found = false;
for (int j = startIndex; j < [Link]; j++) {
if (pages[j] == framePage) {
[Link](framePage, j);
found = true;
break;
}
}
if (!found) {
[Link](framePage, Integer.MAX_VALUE);
}
}
int pageToReplace = -1;
int farthestUsage = -1;
for (int framePage : frames) {
int nextUse = [Link](framePage);
if (nextUse > farthestUsage) {

15
farthestUsage = nextUse;
pageToReplace = framePage;
}
}

return pageToReplace;
}
}

Output

3. Write a program of Page Replacement in context of os?


Source code
import [Link].*;

16
public class PageReplacement {
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the number of frames: ");
int frameCount = [Link]();
[Link]("Enter the number of pages: ");
int pageCount = [Link]();
int[] pages = new int[pageCount];
[Link]("Enter the reference string (page numbers):");
for (int i = 0; i < pageCount; i++) {
pages[i] = [Link]();
}
Set<Integer> frames = new HashSet<>();
Map<Integer, Integer> pageIndices = new HashMap<>();
int pageFaults = 0;

[Link]("\nPage Replacement Process:");


for (int i = 0; i < pageCount; i++) {
int currentPage = pages[i];
if (![Link](currentPage)) {
pageFaults++;
if ([Link]() == frameCount) {
int lruPage = findLeastRecentlyUsed(pageIndices);
[Link](lruPage);
[Link](lruPage);
[Link]("Page " + lruPage + " removed (Least Recently Used).");
[Link](currentPage);
[Link]("Page " + currentPage + " added to the frame.");
} else {

17
[Link]("Page " + currentPage + " accessed (No page fault).");
}
[Link](currentPage, i);
[Link]("Current frames: " + frames);
}

[Link]("\nTotal page faults: " + pageFaults);


[Link]();
}
private static int findLeastRecentlyUsed(Map<Integer, Integer> pageIndices) {
int lruPage = -1;
int minIndex = Integer.MAX_VALUE;

for ([Link]<Integer, Integer> entry : [Link]()) {


if ([Link]() < minIndex) {
minIndex = [Link]();
lruPage = [Link]();
}
}

return lruPage;
}
}

Output

18
19
4. Write a program of Round Robin in context of os?
Source code

import [Link];
import [Link];

class Process {
int id;
int arrivalTime;
int burstTime;
int remainingTime;
int completionTime;
int turnaroundTime
int waitingTime;

Process(int id, int arrivalTime, int burstTime) {


[Link] = id;
[Link] = arrivalTime;
[Link] = burstTime;
[Link] = burstTime;
}
}

public class RoundRobin {


public static void main(String[] args) {
Process[] processes = {
new Process(1, 0, 5),
new Process(2, 1, 3),
new Process(3, 2, 8),
new Process(4, 3, 6)

20
};
int timeQuantum = 3;
roundRobinScheduling(processes, timeQuantum);
[Link]("Process\tArrival\tBurst\tCompletion\tTurnaround\tWaiting");
for (Process p : processes) {
[Link]("P%d\t%d\t%d\t%d\t\t%d\t\t%d\n",
[Link], [Link], [Link],
[Link], [Link], [Link]);
}
}

public static void roundRobinScheduling(Process[] processes, int timeQuantum) {


Queue<Process> readyQueue = new LinkedList<>();
int currentTime = 0;
int processIndex = 0;
while (processIndex < [Link] && processes[processIndex].arrivalTime <= currentTime) {
[Link](processes[processIndex]);
processIndex++;
}

while (![Link]()) {
Process currentProcess = [Link]();
int executionTime = [Link]([Link], timeQuantum);
[Link] -= executionTime;
currentTime += executionTime;
while (processIndex < [Link] && processes[processIndex].arrivalTime <= currentTime)
{
[Link](processes[processIndex]);
processIndex++;
}

21
if ([Link] > 0) {
[Link](currentProcess);
} else {
[Link] = currentTime;
[Link] = [Link] - [Link];
[Link] = [Link] - [Link];
}
}
}
}

Output

5. Write a program of Banker Algorithm in context of os?


Source code

22
import [Link];

public class BankersAlgorithm {

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
[Link]("Enter the number of processes: ");
int numProcesses = [Link]();
[Link]("Enter the number of resources: ");
int numResources = [Link]();
int[][] allocation = new int[numProcesses][numResources];
[Link]("Enter the Allocation matrix:");
for (int i = 0; i < numProcesses; i++) {
for (int j = 0; j < numResources; j++) {
allocation[i][j] = [Link]();
}
}
int[][] maximum = new int[numProcesses][numResources];
[Link]("Enter the Maximum matrix:");
for (int i = 0; i < numProcesses; i++) {
for (int j = 0; j < numResources; j++) {
maximum[i][j] = [Link]();
}
}
int[] available = new int[numResources];
[Link]("Enter the Available resources:");
for (int i = 0; i < numResources; i++) {
available[i] = [Link]();
}

23
int[][] need = new int[numProcesses][numResources];
for (int i = 0; i < numProcesses; i++) {
for (int j = 0; j < numResources; j++) {
need[i][j] = maximum[i][j] - allocation[i][j];
}
}
boolean isSafe = bankersAlgorithm(allocation, maximum, available, need, numProcesses,
numResources);

if (isSafe) {
[Link]("The system is in a safe state.");
} else {
[Link]("The system is NOT in a safe state.");
}

[Link]();
}

public static boolean bankersAlgorithm(int[][] allocation, int[][] maximum, int[] available,


int[][] need, int numProcesses, int numResources) {
boolean[] finished = new boolean[numProcesses];
int[] safeSequence = new int[numProcesses];
int[] work = [Link]();
int count = 0;

while (count < numProcesses) {


boolean found = false;
for (int i = 0; i < numProcesses; i++) {
if (!finished[i]) {
boolean canProceed = true;

24
for (int j = 0; j < numResources; j++) {
if (need[i][j] > work[j]) {
canProceed = false;
break;
}
}

if (canProceed) {
for (int j = 0; j < numResources; j++) {
work[j] += allocation[i][j];
}
safeSequence[count++] = i;
finished[i] = true;
found = true;
}
}
}

if (!found) {

return false;
}
}

[Link]("Safe Sequence: ");


for (int i = 0; i < numProcesses; i++) {
[Link]("P" + safeSequence[i] + " ");
}
[Link]();

25
return true;
}
}

Output

6. Write a program of Worst Fit in context of os?


Source code
import [Link];

public class WorstFit {


public static void main(String[] args) {

26
Scanner scanner = new Scanner([Link]);

[Link]("Enter number of memory blocks: ");


int blockCount = [Link]();
int[] blocks = new int[blockCount];
boolean[] allocated = new boolean[blockCount];
[Link]("Enter sizes of the memory blocks:");
for (int i = 0; i < blockCount; i++) {
blocks[i] = [Link]();
}
[Link]("Enter number of processes: ");
int processCount = [Link]();
int[] processes = new int[processCount];
[Link]("Enter sizes of the processes:");
for (int i = 0; i < processCount; i++) {
processes[i] = [Link]();
}
for (int i = 0; i < processCount; i++) {
int worstIndex = -1;
for (int j = 0; j < blockCount; j++) {
if (!allocated[j] && blocks[j] >= processes[i]) {
if (worstIndex == -1 || blocks[j] > blocks[worstIndex]) {
worstIndex = j;
}
}
}
if (worstIndex != -1) {
[Link]("Process " + (i + 1) + " of size " + processes[i]
+ " allocated to block " + (worstIndex + 1) + " of size " + blocks[worstIndex]);
blocks[worstIndex] -= processes[i]; // Reduce the block size

27
allocated[worstIndex] = blocks[worstIndex] == 0; // Mark block as allocated if fully used
} else {
[Link]("Process " + (i + 1) + " of size " + processes[i] + " cannot be
allocated.");
}
}
[Link]("\nRemaining memory in each block:");
for (int i = 0; i < blockCount; i++) {
[Link]("Block " + (i + 1) + ": " + blocks[i]);
}

[Link]();
}
}

Output

28
29
7. Write a program of Base Fit in context of os?
Source code

import [Link];
public class BestFit {
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the number of memory blocks: ");
int blockCount = [Link]();
int[] blocks = new int[blockCount
[Link]("Enter the sizes of the memory blocks:");
for (int i = 0; i < blockCount; i++) {
blocks[i] = [Link]();
}
[Link]("Enter the number of processes: ");
int processCount = [Link]();
int[] processes = new int[processCount];
[Link]("Enter the sizes of the processes:");
for (int i = 0; i < processCount; i++) {
processes[i] = [Link]();
}
for (int i = 0; i < processCount; i++) {
int bestIndex = -1;
for (int j = 0; j < blockCount; j++) {
if (blocks[j] >= processes[i]) {
if (bestIndex == -1 || blocks[j] < blocks[bestIndex]) {
bestIndex = j;
}
}
}

30
if (bestIndex != -1) {
[Link]("Process " + (i + 1) + " of size " + processes[i]
+ " allocated to block " + (bestIndex + 1) + " of size " + blocks[bestIndex]);
blocks[bestIndex] -= processes[i];
} else {
[Link]("Process " + (i + 1) + " of size " + processes[i] + " cannot be
allocated.");
}
}

[Link]("\nRemaining memory in each block:");


for (int i = 0; i < blockCount; i++) {
[Link]("Block " + (i + 1) + ": " + blocks[i]);
}

[Link]();
}
}

Output

31
32
8. Write a program of Next Fit in context of os?
Source code
import [Link];

public class NextFit {


public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the number of memory blocks: ");
int blockCount = [Link]();
int[] blocks = new int[blockCount];
[Link]("Enter the sizes of the memory blocks:");
for (int i = 0; i < blockCount; i++) {
blocks[i] = [Link]();
}
[Link]("Enter the number of processes: ");
int processCount = [Link]();
int[] processes = new int[processCount];
[Link]("Enter the sizes of the processes:");
for (int i = 0; i < processCount; i++) {
processes[i] = [Link]();
}

int lastAllocatedIndex = 0;

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


boolean allocated = false;
for (int j = 0; j < blockCount; j++) {
int index = (lastAllocatedIndex + j) % blockCount;
if (blocks[index] >= processes[i]) {
[Link]("Process " + (i + 1) + " of size " + processes[i]

33
+ " allocated to block " + (index + 1) + " of size " + blocks[index]);
blocks[index] -= processes[i];
lastAllocatedIndex = index;
allocated = true;
break;
}
}

if (!allocated) {
[Link]("Process " + (i + 1) + " of size " + processes[i] + " cannot be
allocated.");
}
}
[Link]("\nRemaining memory in each block:");
for (int i = 0; i < blockCount; i++) {
[Link]("Block " + (i + 1) + ": " + blocks[i]);
}

[Link]();
}
}

Output

34
35

You might also like