Friday, 1 July 2016

FICS, SJF, ROUND ROBIN

CPU SCHEDULING: FIRST COME FIRST SERVE
WITH ARRIVAL TIME
AIM:
To write a C program to implement the array representation of the CPU scheduling
algorithm first come first serve using arrival time.
PROBLEM DESCRIPTION:
CPU scheduler will decide which process should be given the CPU for its
execution. For this it uses different algorithm to choose among the process. One among
that algorithm is FCFS algorithm.
In this algorithm the process which arrive first is given the cpu after finishing its request
only it will allow cpu to execute other process
ALGORITHM:
Step 1: Create the number of process.
Step 2: Get the ID and Service time for each process.
Step 3: Initially, Waiting time of first process is zero and Total time for the first
process is the starting time of that process.
Step 4: Calculate the Total time and Processing time for the remaining processes.
Step 5: Waiting time of one process is the Total time of the previous process. Step 6:
Total time of process is calculated by adding Waiting time and Service
time.
Step 7: Total waiting time is calculated by adding the waiting time for lack process.
Step 8: Total turn around time is calculated by adding all total time of each process.
Step 9: Calculate Average waiting time by dividing the total waiting time by total
number of process.
Step 10: Calculate Average turn around time by dividing the total time by the
number of process.
Step 11: Display the result.

Program 


#include<stdio.h>
#include<string.h>
#include<conio.h>
main()
{
char pn[10][10],t[10];
int arr[10],bur[10],star[10],finish[10],tat[10],wt[10],i,j,n,temp;
int totwt=0,tottat=0;
//clrscr();
printf("Enter the number of processes:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the Process Name, Arrival Time & Burst Time:");
scanf("%s%d%d",&pn[i],&arr[i],&bur[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(arr[i]<arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
temp=bur[i];
bur[i]=bur[j];
bur[j]=temp;
strcpy(t,pn[i]);
strcpy(pn[i],pn[j]);
strcpy(pn[j],t);
}
}
}
for(i=0;i<n;i++)
{
if(i==0)
star[i]=arr[i];
else
star[i]=finish[i-1];
wt[i]=star[i]-arr[i];
finish[i]=star[i]+bur[i];
tat[i]=finish[i]-arr[i];
}
printf("\nPName Arrtime Burtime WaitTime  Start TAT Finish");
for(i=0;i<n;i++)
{
printf("\n%s\t%3d\t%3d\t%3d\t%3d\t%6d\t%6d",pn[i],arr[i],bur[i],wt[i],star[i],tat[i],finis
h[i]);
totwt+=wt[i];
tottat+=tat[i];
}
printf("\nAverage Waiting time:%f",(float)totwt/n);
printf("\nAverage Turn Around Time:%f",(float)tottat/n);
getch();
return 0;
}

OUTPUT:

Input:

Enter the number of processes: 3
Enter the Process Name, Arrival Time & Burst Time: p1 2 4
Enter the Process Name, Arrival Time & Burst Time: p2 3 5
Enter the Process Name, Arrival Time & Burst Time: p3 1 6

Output:

PName Arrtime   Burtime   WaitTime        Srart  TAT  Finish
p3     1   6 0  1 6 7
p1     2  4 5  7 9 11
p2     3  5 8  11 13 16

Average Waiting Time: 4.3333333

Average Turn Around Time: 9.33333333 
------------------------

-----------------------------
CPU SCHEDULING: SHORTEST JOB FIRST.
AIM: To write a C program to implement the CPU scheduling algorithm for shortest job first.
PROBLEM DESCRIPTION:
Cpu scheduler will decide which process should be given the CPU for its execution.
For this it uses different algorithm to choose among the process. One among that algorithm
is SJF algorithm.
In this algorithm the process which has less service time given the cpu after finishing
its request only it will allow cpu to execute next other process.
ALGORITHM:
Step 1: Get the number of process.
Step 2: Get the id and service time for each process.
Step 3: Initially the waiting time of first short process as 0 and total time of
first short is process the service time of that process.
Step 4: Calculate the total time and waiting time of remaining process.
Step 5: Waiting time of one process is the total time of the previous process.
Step 6: Total time of process is calculated by adding the waiting time and
service
time of each process.
Step 7: Total waiting time calculated by adding the waiting time of each process.
Step 8: Total turn around time calculated by adding all total time of each
process. Step 9: Calculate average waiting time by dividing the total waiting
time by total
number of process.
Step 10: Calculate average turn around time by dividing the total waiting time
by total number of process.
Step 11: Display the result.

Program :

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
int et[20],at[10],n,i,j,temp,st[10],ft[10],wt[10],ta[10];
int totwt=0,totta=0;
float awt,ata;
char pn[10][10],t[10];
clrscr();
printf("Enter the number of process:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter process name, arrival time & execution time:");
flushall();
scanf("%s%d%d",pn[i],&at[i],&et[i]);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(et[i]<et[j])
{
temp=at[i];
at[i]=at[j];
at[j]=temp;
temp=et[i];
et[i]=et[j];
et[j]=temp;
strcpy(t,pn[i]);
strcpy(pn[i],pn[j]);
strcpy(pn[j],t);
}
}
for(i=0;i<n;i++)
{
if(i==0)
st[i]=at[i];
else
st[i]=ft[i-1];




wt[i]=st[i]-at[i];
ft[i]=st[i]+et[i];
ta[i]=ft[i]-at[i];
totwt+=wt[i];
totta+=ta[i];
}
awt=(float)totwt/n;
ata=(float)totta/n;
printf("\nPname\tarrivaltime\texecutiontime\twaitingtime\ttatime");
for(i=0;i<n;i++)
printf("\n%s\t%5d\t\t%5d\t\t%5d\t\t%5d",pn[i],at[i],et[i],wt[i],ta[i]);
printf("\nAverage waiting time is:%f",awt);
printf("\nAverage turnaroundtime is:%f",ata);
getch();
}

OUTPUT:


Input:

Enter the number of processes: 3
Enter the Process Name, Arrival Time & Burst Time: 1 4 6
Enter the Process Name, Arrival Time & Burst Time: 2 5 15
Enter the Process Name, Arrival Time & Burst Time: 3 6 11

Output:

Pname    arrivaltime   executiontime   waitingtime  tatime
1       4  6  0 6
3      6  11  4 15
2  5  15  16 31

Average Waiting Time: 6.6667
Average Turn Around Time: 17.3333
 -----------------
--------
Aim: Write a C program to implement the various process scheduling mechanisms such
           as Round Robin Scheduling.

PROBLEM DESCRIPTION: CPU scheduler will decide which process should be given the CPU for its execution. For this it use different algorithm to choose among the process. One among that algorithm is Round robin algorithm. In this algorithm we are assigning some time slice .The process is allocated according to the time slice, if the process service time is less than the time slice then process itself will release the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue .If the CPU burst of the currently running process is longer than time quantum, the timer will go off and will cause an interrupt to the operating system. A context switch will be executed and the process will be put at the tail of the ready queue.
Algorithm for RR

1. The queue structure in ready queue is of First In First Out (FIFO) type.
2. A fixed time is allotted to every process that arrives in the queue. This fixed time is known as time slice or time quantum.
3. The first process that arrives is selected and sent to the processor for execution. If it is not able to complete its execution within the time quantum provided, then an interrupt is generated using an automated timer.
4. The process is then stopped and is sent back at the end of the queue. However, the state is saved and context is thereby stored in memory. This helps the process to resume from the point where it was interrupted.
5. The scheduler selects another process from the ready queue and dispatches it to the processor for its execution. It is executed until the time Quantum does not exceed.
6. The same steps are repeated until all the process are finished.
The round robin algorithm is simple and the overhead in decision making is very low. It is the best scheduling algorithm for achieving better and evenly distributed response time.


Program:
#include<stdio.h>
int main()
{
  int count,j,n,time,remain,flag=0,time_quantum;
  int wait_time=0,turnaround_time=0,at[10],bt[10],rt[10];
  printf("Enter Total Process:\t ");
  scanf("%d",&n);
  remain=n;
  for(count=0;count<n;count++)
  {
    printf("Enter Arrival Time and Burst Time for Process Process Number %d :",count+1);
    scanf("%d",&at[count]);
    scanf("%d",&bt[count]);
    rt[count]=bt[count];
  }
  printf("Enter Time Quantum:\t");
  scanf("%d",&time_quantum);
  printf("\n\nProcess\t|Turnaround Time|Waiting Time\n\n");
  for(time=0,count=0;remain!=0;)
  {
    if(rt[count]<=time_quantum && rt[count]>0)
    {
      time+=rt[count];
      rt[count]=0;
      flag=1;
    }
    else if(rt[count]>0)
    {
      rt[count]-=time_quantum;
      time+=time_quantum;
    }
    if(rt[count]==0 && flag==1)
    {
      remain--;
      printf("P[%d]\t|\t%d\t|\t%d\n",count+1,time-at[count],time-at[count]-bt[count]);
      wait_time+=time-at[count]-bt[count];
      turnaround_time+=time-at[count];
      flag=0;
    }
    if(count==n-1)
      count=0;
    else if(at[count+1]<=time)
      count++;
    else
      count=0;
  }
  printf("\nAverage Waiting Time= %f\n",wait_time*1.0/n);
  printf("Avg Turnaround Time = %f",turnaround_time*1.0/n);
  
  return 0;
}










---------------------------------------------------------


Program : Priority Scheduling Algorithm

What is Priority Scheduling Algorithm?
In priority scheduling algorithm each process has a priority associated with it and as each process hits the queue, it is stored in based on its priority so that process with higher priority are dealt with first. It should be noted that equal priority processes are scheduled in FCFS order.
To prevent high priority processes from running indefinitely the scheduler may decrease the priority of the currently running process at each clock tick (i.e., at each clock interrupt). If this action causes its priority to drop below that of the next highest process, a process switch occurs. Alternatively, each process may be assigned a maximum time quantum that it is allowed to run. When this quantum is used up, the next highest priority process is given a chance to run.

Limitations
The problem occurs when the operating system gives a particular task a very low priority, so it sits in the queue for a larger amount of time, not being dealt with by the CPU. If this process is something the user needs, there could be a very long wait, this process is known as “Starvation” or “Infinite Blocking”.

IMPLEMENTATION OF PRIORITY SCHEDULING ALGORITHM 
1. Start the process 
2.  Get the number of processes to be inserted 
3. Get the corresponding priority of processes 
4.  Sort the processes according to the priority and allocate the one with highest priority to execute first 
5.  If two process have same priority then FCFS scheduling algorithm is used 
6.  Calculate the total and average waiting time and turn around time 
7.  Display the values 
8. Stop the process 

Program :
#include<stdio.h>

int main()
{
    int bt[20],p[20],wt[20],tat[20],pr[20],i,j,n,total=0,pos,temp,avg_wt,avg_tat;
    printf("Enter Total Number of Process:");
    scanf("%d",&n);

    printf("\nEnter Burst Time and Priority\n");
    for(i=0;i<n;i++)
    {
        printf("\nP[%d]\n",i+1);
        printf("Burst Time:");
        scanf("%d",&bt[i]);
        printf("Priority:");
        scanf("%d",&pr[i]);
        p[i]=i+1;           //contains process number
    }

    //sorting burst time, priority and process number in ascending order using selection sort
    for(i=0;i<n;i++)
    {
        pos=i;
        for(j=i+1;j<n;j++)
        {
            if(pr[j]<pr[pos])
                pos=j;
        }

        temp=pr[i];
        pr[i]=pr[pos];
        pr[pos]=temp;

        temp=bt[i];
        bt[i]=bt[pos];
        bt[pos]=temp;

        temp=p[i];
        p[i]=p[pos];
        p[pos]=temp;
    }

    wt[0]=0;    //waiting time for first process is zero

    //calculate waiting time
    for(i=1;i<n;i++)
    {
        wt[i]=0;
        for(j=0;j<i;j++)
            wt[i]+=bt[j];

        total+=wt[i];
    }

    avg_wt=total/n;      //average waiting time
    total=0;

    printf("\nProcess\t    Burst Time    \tWaiting Time\tTurnaround Time");
    for(i=0;i<n;i++)
    {
        tat[i]=bt[i]+wt[i];     //calculate turnaround time
        total+=tat[i];
        printf("\nP[%d]\t\t  %d\t\t    %d\t\t\t%d",p[i],bt[i],wt[i],tat[i]);
    }

    avg_tat=total/n;     //average turnaround time
    printf("\n\nAverage Waiting Time=%d",avg_wt);
    printf("\nAverage Turnaround Time=%d\n",avg_tat);

    return 0;
}




-------------------------------------------------------

How do I write a C program to implement a SRTF (Shortest Remaining Time First) scheduling algorithm, 

What is SRTN

Shortest remaining time, also known as shortest remaining time first (SRTF), is a scheduling method that is a preemptive version of shortest job next scheduling. In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, processes will always run until they complete or a new process is added that requires a smaller amount of time.
Shortest remaining time is advantageous because short processes are handled very quickly. The system also requires very little overhead since it only makes a decision when a process completes or a new process is added, and when a new process is added the algorithm only needs to compare the currently executing process with the new process, ignoring all other processes currently waiting to execute.

#include <stdio.h>
int main() 
{
 int a[10],b[10],x[10],i,j,smallest,count=0,time,n;
 double avg=0,tt=0,end;
  printf("enter the number of Processes:\n");
  scanf("%d",&n); 
 printf("enter arrival time\n");
 for(i=0;i<n;i++)
 scanf("%d",&a[i]);
 printf("enter burst time\n");
 for(i=0;i<n;i++)
 scanf("%d",&b[i]); 
 for(i=0;i<n;i++)
 x[i]=b[i];

  b[9]=9999;
  
 for(time=0;count!=n;time++)
 {
   smallest=9;
  for(i=0;i<n;i++)
  {
   if(a[i]<=time && b[i]<b[smallest] && b[i]>0 )
   smallest=i;
  }
  b[smallest]--;
  if(b[smallest]==0)
  {
   count++;
   end=time+1;
   avg=avg+end-a[smallest]-x[smallest];
   tt= tt+end-a[smallest];
  }
 }
 printf("\n\nAverage waiting time = %lf\n",avg/n);
    printf("Average Turnaround time = %lf",tt/n);
    return 0;
}
output:-
enter the number of Processes:
4
enter arrival time
0
1
2
3
enter burst time
8
4
9
5


Average waiting time = 6.500000
Average Turnaround time = 13.000000
--------------------------------
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)