Tuesday, 18 August 2015

Implementation of FirstFit, BestFit and WorstFit algorithms


First-fit:    Allocate the first hole that is big enough.
Best-fit:    Allocate the smallest hole that is big enough; must search entire list, unless ordered by size.Produces the smallest leftover hole.
Worst-fit:  Allocate the largest hole; must also search entire list. Produces the largest leftover hole.
                   How to satisfy a request of size n from a list of free holes.
First-fit and best-fit better than worst-fit in terms of speed and storage utilization.




import java.util.Scanner;
class Memory
{
int Nop,Noh;
int temp[];
int Psize[];
int Hsize[];
Scanner sc=new Scanner(System.in);
void inputData()
{
System.out.println("enter the total number of processes:");
Nop=sc.nextInt();
System.out.println("enter the total number of Holes");
Noh=sc.nextInt();
Psize=new int[Nop];
Hsize=new int[Noh];
System.out.println("enter the process size of each process:");
for(int i=0;i<Nop;i++)
{
Psize[i]=sc.nextInt();
}
System.out.println("enter the hole size of each hole:");
for(int i=0;i<Noh;i++)
{
Hsize[i]=sc.nextInt();
}
}
void display()
{
System.out.println("process size of each process is :");
for(int i=0;i<Nop;i++)
System.out.print(Psize[i]);
System.out.println("hole size of each hole is:");
for(int i=0;i<Noh;i++)
System.out.print(Hsize[i]);
}
void sort()
{
temp=new int[Noh];
for(int i=0;i<Noh;i++)
temp[i]=Hsize[i];
for(int i=0;i<Noh-1;i++)
{
for(int j=i+1;j<Noh;j++)
{
if(Hsize[i]>Hsize[j])
{
int temp=Hsize[i];
Hsize[i]=Hsize[j];
Hsize[j]=temp;
}
}
}
}
void FirstFit()
{
int i_freg=0,e_freg=0;
int flag[]=new int[Noh];
int j;
for(int i=0;i<Nop;i++)
{
for(j=0;j<Noh;j++)
{
if(flag[j]==0 && Hsize[j]>=Psize[i])
{
flag[j]=1;
i_freg=i_freg+Hsize[j]-Psize[i];
break;
}
}
if(j==Noh)
System.out.printf("\n\nTHERE IS NO SPACE FOR PROCESS %d ",i);
}
for(int i=0;i<Noh;i++)
{
if(flag[i]==0)
e_freg=e_freg+Hsize[i];
}
System.out.format("\n\nTOTAL SUM OF INTERNAL FRAGMENTATION = %d ",i_freg);
System.out.format("\n\nTOTAL SUM OF EXTERNAL FRAGMENTATION = %d ",e_freg);
}
void bestFit()
{
int i_freg=0,e_freg=0;
int flag[]=new int[Noh];
int j;

for(int i=0;i<Nop;i++)
{
for(j=0;j<Noh;j++)
{
if(flag[j]==0 && Hsize[j]>=Psize[i])
{
flag[j]=1;
i_freg=i_freg+Hsize[j]-Psize[i];
break;
}
}
if(j==Noh)
System.out.format("\n\nTHERE IS NO SPACE FOR PROCESS %d ",i);
}
for(int i=0;i<Noh;i++)
{
if(flag[i]==0)
e_freg=e_freg+Hsize[i];
}
System.out.format("\n\nTOTAL SUM OF INTERNAL FRAGMENTATION = %d ",i_freg);
System.out.format("\n\nTOTAL SUM OF EXTERNAL FRAGMENTATION = %d ",e_freg);

for(int i=0;i<Noh;i++)
Hsize[i]=temp[i];
}
void worstFit()
{
int i_freg=0,e_freg=0;
int flag[]=new int[Noh];
int j;
for(int i=0;i<Nop;i++)
{
for(j=Noh-1;j>=0;j--)
{
if(flag[j]==0 && Hsize[j]>=Psize[i])
{
flag[j]=1;
i_freg=i_freg+Hsize[j]-Psize[i];
break;
}
}
if(j<0)
System.out.format("\n\nTHERE IS NO SPACE FOR PROCESS %d ",i);
}
for(int i=0;i<Noh;i++)
{
if(flag[i]==0)
e_freg=e_freg+Hsize[i];
}
System.out.format("\n\nTOTAL SUM OF INTERNAL FRAGMENTATION = %d ",i_freg);
System.out.format("\n\nTOTAL SUM OF EXTERNAL FRAGMENTATION = %d ",e_freg);

for(int i=0;i<Noh;i++)
Hsize[i]=temp[i];
}
}
class MemoryTest
{
public static void main(String args[])
{
Memory m1=new Memory();
Scanner sc=new Scanner(System.in);
m1.inputData();
while(true)
{
System.out.println();
System.out.println();
System.out.println();
System.out.println();
System.out.println("press 1 for Best Fit:");
System.out.println("press 2 for First Fit:");
System.out.println("press 3 for Worst Fit:");
System.out.println("press 4 for Exit:");
System.out.println("Select the algorithm for memory management:");
int ch=sc.nextInt();
switch(ch)
{
case 1: System.out.println("BEST FIT ALGORITHM:");
m1.sort();
m1.bestFit();
break;

case 2: System.out.println("FIRST FIT ALGORITHM:");
m1.FirstFit();
break;

case 3: System.out.println("WORST FIT ALGORITHM:");
m1.sort();
m1.worstFit();
break;
case 4: 
System.exit(0);
default:
System.out.println("enter the right choice:");
}
}
}
}






Posted by at No comments:

Implementation of Priority Scheduling

Priority Based Scheduling

  • Each process is assigned a priority. Process with highest priority is to be executed first and so on.
  • Processes with same priority are executed on first come first serve basis.
  • Priority can be decided based on memory requirements, time requirements or any other resource requirement.



import java.util.Scanner;
class Priority
{
Scanner sc=new Scanner(System.in);
int MaxProcess=sc.nextInt();
int Pid[]=new int[MaxProcess];
int Burst[]=new int[MaxProcess];
int Wait[]=new int[MaxProcess];
int Trt[]=new int[MaxProcess];
int Arrival[]=new int[MaxProcess];
int Prior[]=new int[MaxProcess];
void input()
{
for(int i=0;i<MaxProcess;i++)
{
System.out.format("enter the process-id for this %d",(i+1));
Pid[i]=sc.nextInt();
System.out.format("enter the burst time for this p%d",Pid[i]);
Burst[i]=sc.nextInt();
System.out.format("enter the  priority for this p%d",Pid[i]);
Prior[i]=sc.nextInt();
System.out.format("enter the arrival time for this p%d",Pid[i]);
Arrival[i]=sc.nextInt();
}
       System.out.println("the process-id and burst time is:\n");
       System.out.println("process-id\t\tbursttime\t\tpriority\t\tarrival\n");
for(int i=0;i<MaxProcess;i++)
{
System.out.format("%d\t\t\t%d\t\t\t%d\t\t\t%d\n",Pid[i],Burst[i],Prior[i],Arrival[i]);
}
}
void turnAroundTime()
{
for(int i=0;i<MaxProcess;i++)
{
Trt[i]=Wait[i]+Burst[i];
}
}
void waitingTime()
{
int i,Total;
Wait[0]=0;
Total=Arrival[0];
for(i=1;i<MaxProcess;i++)
{
Total=Total+Burst[i-1];
Wait[i]=Total-Arrival[i];;
}
}
void displaySort()
{
System.out.println("after sorting on the basis of arrival time:");
float sum1=0,sum2=0;
System.out.println("p-id\tbursttime\tpriority\tarrival\twaittime\tturntime\n");
for(int i=0;i<MaxProcess;i++)
System.out.format("%d\t%d\t\t%d\t\t%d\t%d\t\t%d\n",Pid[i],Burst[i],Prior[i],Arrival[i],Wait[i],Trt[i]);
}
void display()
{
float sum1=0,sum2=0;
System.out.println("p-id\tbursttime\tpriority\tarrival\twaittime\tturntime\n");
for(int i=0;i<MaxProcess;i++)
System.out.format("%d\t%d\t\t%d\t\t%d\t%d\t\t%d\n",Pid[i],Burst[i],Prior[i],Arrival[i],Wait[i],Trt[i]);
for(int i=0;i<MaxProcess;i++)
{
sum1=sum1+Wait[i];
sum2=sum2+Trt[i];
}
System.out.format("waiting time is %f\n",sum1/MaxProcess);
System.out.format("totalrunaroundtime is %f\n",sum2/MaxProcess);
}

void sort()
{
for(int i=0;i<MaxProcess-1;i++)
{
  for(int j=i+1;j<MaxProcess;j++)
{
if(Prior[i]>Prior[j])
{
int temp1=Arrival[i];
Arrival[i]=Arrival[j];
Arrival[j]=temp1;

int temp2=Burst[i];
Burst[i]=Burst[j];
Burst[j]=temp2;

int temp3=Pid[i];
Pid[i]=Pid[j];
Pid[j]=temp3;
int temp4=Prior[i];
Prior[i]=Prior[j];
Prior[j]=temp4;

}
}
}
int temp=0;
int min=Arrival[0];
for(int i=1;i<MaxProcess;i++)
{
if(min>Arrival[i])
{
min=Arrival[i];
temp=i;
}
}
int f1=Arrival[temp];
int f2=Burst[temp];
int f3=Pid[temp];
int f4=Prior[temp];
for(int i=temp;i>0;i--)
{
Arrival[i]=Arrival[i-1];
Burst[i]=Burst[i-1];
Pid[i]=Pid[i-1];
}
Burst[0]=f2;
Arrival[0]=f1;
Pid[0]=f3;
Prior[0]=f4;
}
void drawGanttChart()
{

System.out.println();
for(int i=0;i<MaxProcess;i++)
{
  for(int j=0;j<Burst[i];j++)
System.out.print("|");

System.out.format(" p%d ",Pid[i]);
}
}

}
class PriorityTest
{
public static void main(String args[])
{
System.out.println("enter the total number of process:");
Priority p1=new Priority();
p1.input();
p1.sort();
p1.displaySort();
p1.waitingTime();
p1.turnAroundTime();
p1.display();
p1.drawGanttChart();
}
}
Posted by at No comments:

Implementation of Shortest Job First Scheduling algorithm

Shortest Job First (SJF)

  • Best approach to minimize waiting time.
  • Impossible to implement
  • Processer should know in advance how much time process will take







import java.util.Scanner;
class Sjf
{
Scanner sc=new Scanner(System.in);
int MaxProcess=sc.nextInt();
int Pid[]=new int[MaxProcess];
int Burst[]=new int[MaxProcess];
int Wait[]=new int[MaxProcess];
int Trt[]=new int[MaxProcess];
int Arrival[]=new int[MaxProcess];
void input()
{
for(int i=0;i<MaxProcess;i++)
{
System.out.format("enter the process-id for this %d",(i+1));
Pid[i]=sc.nextInt();
System.out.format("enter the burst time for this p%d",Pid[i]);
Burst[i]=sc.nextInt();
System.out.format("enter the arrival time for this p%d",Pid[i]);
Arrival[i]=sc.nextInt();
}
    System.out.println("the process-id and burst time is:\n");
    System.out.println("process-id\t\tbursttime\t\tarrival\n");
for(int i=0;i<MaxProcess;i++)
{
System.out.format("%d\t\t\t%d\t\t\t%d\n",Pid[i],Burst[i],Arrival[i]);
}
}
void turnAroundTime()
{
for(int i=0;i<MaxProcess;i++)
{
Trt[i]=Wait[i]+Burst[i];
}
}
void waitingTime()
{
int i,Total;
Wait[0]=0;
Total=Arrival[0];
for(i=1;i<MaxProcess;i++)
{
Total=Total+Burst[i-1];
Wait[i]=Total-Arrival[i];;
}
}
void displaySort()
{
System.out.println("after sorting on the basis of arrival time:");
float sum1=0,sum2=0;
System.out.println("process-id\t bursttime\t arrival \t waiting time\t turnaroundtime\n");
for(int i=0;i<MaxProcess;i++)
System.out.format("%d\t\t\t%d\t\t%d\t\t%d\t\t%d\n",Pid[i],Burst[i],Arrival[i],Wait[i],Trt[i]);
}
void display()
{
float sum1=0,sum2=0;
System.out.println("process-id\t bursttime\t arrival \t waiting time\t turnaroundtime\n");
for(int i=0;i<MaxProcess;i++)
System.out.format("%d\t\t\t%d\t\t%d\t\t%d\t\t%d\n",Pid[i],Burst[i],Arrival[i],Wait[i],Trt[i]);
for(int i=0;i<MaxProcess;i++)
{
sum1=sum1+Wait[i];
sum2=sum2+Trt[i];
}
System.out.format("waiting time is %f\n",sum1/MaxProcess);
System.out.format("totalrunaroundtime is %f\n",sum2/MaxProcess);
}

void sort()
{
for(int i=0;i<MaxProcess-1;i++)
{
  for(int j=i+1;j<MaxProcess;j++)
{
if(Burst[i]>Burst[j])
{
int temp1=Arrival[i];
Arrival[i]=Arrival[j];
Arrival[j]=temp1;

int temp2=Burst[i];
Burst[i]=Burst[j];
Burst[j]=temp2;

int temp3=Pid[i];
Pid[i]=Pid[j];
Pid[j]=temp3;

}
}
}
int temp=0;
int min=Arrival[0];
for(int i=1;i<MaxProcess;i++)
{
if(min>Arrival[i])
{
min=Arrival[i];
temp=i;
}
}
int f1=Arrival[temp];
int f2=Burst[temp];
int f3=Pid[temp];
for(int i=temp;i>0;i--)
{
Arrival[i]=Arrival[i-1];
Burst[i]=Burst[i-1];
Pid[i]=Pid[i-1];
}
Burst[0]=f2;
Arrival[0]=f1;
Pid[0]=f3;
}
void drawGanttChart()
{

System.out.println();
for(int i=0;i<MaxProcess;i++)
{
  for(int j=0;j<Burst[i];j++)
System.out.print("|");

System.out.format(" p%d ",Pid[i]);
}
}

}
class SjfTest
{
public static void main(String args[])
{
System.out.println("enter the total number of process:");
Sjf s1=new Sjf();
s1.input();
s1.sort();
s1.displaySort();
s1.waitingTime();
s1.turnAroundTime();
s1.display();
s1.drawGanttChart();
}
}



Posted by at No comments:

Implementation of First Come First Serve Scheduling alogrithm

       First Come First Serve (FCFS)

  • Jobs are executed on first come, first serve basis.
  • Easy to understand and implement.
  • Poor in performance as average wait time is high.




import java.util.Scanner;
class Fcfs
{
Scanner sc=new Scanner(System.in);
int MaxProcess=sc.nextInt();
int Pid[]=new int[MaxProcess];
int Burst[]=new int[MaxProcess];
int Wait[]=new int[MaxProcess];
int Trt[]=new int[MaxProcess];
int Arrival[]=new int[MaxProcess];
void input()
{
for(int i=0;i<MaxProcess;i++)
{
System.out.format("enter the process-id for this %d",(i+1));
Pid[i]=sc.nextInt();
System.out.format("enter the burst time for this p%d",Pid[i]);
Burst[i]=sc.nextInt();
System.out.format("enter the arrival time for this p%d",Pid[i]);
Arrival[i]=sc.nextInt();
}
    System.out.println("the process-id and burst time is:\n");
    System.out.println("process-id\t\tbursttime\t\tarrival\n");
for(int i=0;i<MaxProcess;i++)
{
System.out.format("%d\t\t\t%d\t\t\t%d\n",Pid[i],Burst[i],Arrival[i]);
}
}
void turnAroundTime()
{
for(int i=0;i<MaxProcess;i++)
{
Trt[i]=Wait[i]+Burst[i];
}
}
void waitingTime()
{
int i,Total;
Wait[0]=0;
Total=Arrival[0];
for(i=1;i<MaxProcess;i++)
{
Total=Total+Burst[i-1];
Wait[i]=Total-Arrival[i];;
}
}
void displaySort()
{
System.out.println("after sorting on the basis of arrival time:");
float sum1=0,sum2=0;
System.out.println("process-id\t bursttime\t arrival \t waiting time\t turnaroundtime\n");
for(int i=0;i<MaxProcess;i++)
System.out.format("%d\t\t\t%d\t\t%d\t\t%d\t\t%d\n",Pid[i],Burst[i],Arrival[i],Wait[i],Trt[i]);
}
void display()
{
float sum1=0,sum2=0;
System.out.println("process-id\t bursttime\t arrival \t waiting time\t turnaroundtime\n");
for(int i=0;i<MaxProcess;i++)
System.out.format("%d\t\t\t%d\t\t%d\t\t%d\t\t%d\n",Pid[i],Burst[i],Arrival[i],Wait[i],Trt[i]);
for(int i=0;i<MaxProcess;i++)
{
sum1=sum1+Wait[i];
sum2=sum2+Trt[i];
}
System.out.format("waiting time is %f\n",sum1/MaxProcess);
System.out.format("totalrunaroundtime is %f\n",sum2/MaxProcess);
}

void sort()
{
for(int i=0;i<MaxProcess-1;i++)
{
  for(int j=i+1;j<MaxProcess;j++)
{
if(Arrival[i]>Arrival[j])
{
int temp1=Arrival[i];
Arrival[i]=Arrival[j];
Arrival[j]=temp1;

int temp2=Burst[i];
Burst[i]=Burst[j];
Burst[j]=temp2;

int temp3=Pid[i];
Pid[i]=Pid[j];
Pid[j]=temp3;

}
}
}
}
void drawGanttChart()
{

System.out.println();
for(int i=0;i<MaxProcess;i++)
{
  for(int j=0;j<Burst[i];j++)
System.out.print("|");

System.out.format(" p%d ",Pid[i]);
}
}

}
class FcfsTest
{
public static void main(String args[])
{
System.out.println("enter the total number of process:");
Fcfs f1=new Fcfs();
f1.input();
f1.sort();
f1.displaySort();
f1.waitingTime();
f1.turnAroundTime();
f1.display();
f1.drawGanttChart();
}
}




Posted by at No comments:
Subscribe to: Posts (Atom)