You have been asked to test the effectiveness of the following different schedul

Question

You have been asked to test the effectiveness of the following different scheduling algorithms for different types of queuing applications. First-In-First-Out (FIFO): The jobs are processed in the arriving order. The job at the front of the queue is served until it has completed. That job is then removed from the queue. The next job at the front of the queue is served until it has completed and then it is removed from the queue. This process is continued until the queue is empty Shortest-Job-First (SJF): The job with the shortest processing time is processed first until it has completed. That job is then removed from the queue. The next job with smallest processing is then served until it has completed and then it is removed from the queue. This process is continued until the queue is empty.

Explanation / Answer

a) First In First Out Page Replacement algorithm

Page replacement algorithm are needed to decide which page needed to be replaced when new page comes in. Whenever a new page is referred and not present in memory, page fault occurs.
Page Fault
A page fault is a type of interrupt, raised by the hardware when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory.

First In First Out

This is the simplest page replacement algorithm. In this algorithm, operating system keeps track of all pages in the memory in a queue, oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.

Java code for First In First Out

import java.io.*;
public class FIFO
{
public static void main(String[] args) throws Exception
{
int f,p,num=0, pageHit=0;
int pages[];
int frame[];
boolean flag = true;

BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter number of frames : ");
f = Integer.parseInt(br.readLine());
System.out.println("Enter number of pages : ");
p = Integer.parseInt(br.readLine());

frame = new int[f];
pages = new int[p];

for(int i=0; i<f; i++)
{
frame[i] = -1;
}

System.out.println("Enter page number : ");
for(int i=0;i<p;i++)
pages[i] = Integer.parseInt(br.readLine());

for(int i=0; i<p; i++)
{
flag = true;
int page = pages[i];
for(int j=0; j<f; j++)
{
if(frame[j] == page)
{
flag = false;
pageHit++;
break;
}
}
if(num == f)
num = 0;

if(flag)
{
frame[num] = page;
num++;
}
System.out.print("frame : ");
for(int k=0; k<f; k++)
System.out.print(frame[k]+" ");
System.out.println();

}
System.out.println("No. of page hit : "+pageHit);
}
}

Output:

C:java>javac FIFO.java

C:java>java FIFO
Enter number of frames :
4
Enter number of pages :
22
Enter page number :
1
2
3
4
5
3
4
1
6
7
8
7
8
9
7
8
9
5
4
5
4
2
frame : 1 -1 -1 -1
frame : 1 2 -1 -1
frame : 1 2 3 -1
frame : 1 2 3 4
frame : 5 2 3 4
frame : 5 2 3 4
frame : 5 2 3 4
frame : 5 1 3 4
frame : 5 1 6 4
frame : 5 1 6 7
frame : 8 1 6 7
frame : 8 1 6 7
frame : 8 1 6 7
frame : 8 9 6 7
frame : 8 9 6 7
frame : 8 9 6 7
frame : 8 9 6 7
frame : 8 9 5 7
frame : 8 9 5 4
frame : 8 9 5 4
frame : 8 9 5 4
frame : 2 9 5 4
No. of page hit : 9

C:java>

b) Shortest Job First:

this algorithm associates with each process the length of the process's next CPU burst time.

When CPU is available,it is assigned to the process that has the smallest next CPU burst.

If the next CPU bursts of two processes are the same,FCFS scheduling is used to break the tie.

Java program for Shortest Job First CPU scheduling algorithm

import java.util.Scanner;

class sjf {
public static void main(String args[])
{
int process[] = new int[10];
int ptime[] = new int[10];
int wtime[] = new int[10];
int temp, n, total=0;
float avg=0;
Scanner get = new Scanner(System.in);

System.out.println("Enter Number of Processes:");
n = get.nextInt();
for(int i=0;i<n;i++)
{
System.out.println("Enter Process "+(i+1)+" ID: ");
process[i] = get.nextInt();
System.out.println("Enter Process "+(i+1)+" Burst Time: ");
ptime[i] = get.nextInt();
}

for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)   
{   
if(ptime[i]>ptime[j])
{
temp = ptime[i];
ptime[i] = ptime[j];
ptime[j] = temp;
temp = process[i];
process[i] = process[j];
process[j] = temp;
}
}
}

wtime[0] = 0;
for(int i=1;i<n;i++)
{
wtime[i] = wtime[i-1]+ptime[i-1];
total = total + wtime[i];
}
avg = (float)total/n;
System.out.println("P_ID P_TIME W_TIME");
for(int i=0;i<n;i++)
{
System.out.println(process[i]+" "+ptime[i]+" "+wtime[i]);
}
System.out.println("Total Waiting Time: "+total);
System.out.println("Average Waiting Time: "+avg);
}
}

Output

C:java>javac sjf.java

C:java>java sjf
Enter Number of Processes:
4
Enter Process 1 ID:
1
Enter Process 1 Burst Time:
16
Enter Process 2 ID:
2
Enter Process 2 Burst Time:
3
Enter Process 3 ID:
3
Enter Process 3 Burst Time:
4
Enter Process 4 ID:
4
Enter Process 4 Burst Time:
2
P_ID P_TIME W_TIME
4 2 0
2 3 2
3 4 5
1 16 9
Total Waiting Time: 16
Average Waiting Time: 4.0

C:java>

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.