You will implement a framework for CPU scheduling with three scheduling algorith

ID: 3680041 • Letter: Y

Question

You will implement a framework for CPU scheduling with three scheduling algorithms: FIFO, round robin, and shortest remaining job first (SRJF). Jobs arrive at the CPU scheduler at arbitrary times ranging from 1 to 20 time slots and at least 15 jobs. When a job arrives, its computation time is known. Assume that all jobs involve only computation, and perform no Input/Output. Jobs thus need to run on the CPU for a total duration equal to their known computation times. When they complete, they leave the system.

Explanation / Answer

FIFO algorithm:

First-Come, First-Served (FCFS) Scheduling

A FIFO acts like any normal queue whether, it is a line in a cinema, a checkout line in a store, or a queue for a ticket booth. The first person or process to arrive (First In) is the first one to be dealt with (First Out). If one person goes through the line and then decides they forgot something then they have to go back through.

This is exactly how OS's with this design let programs conduct their business. One person (aka: process) at a time.

Implementation

To implement this, you can create a queue, an abstract data type (ADT) that can be constructed from a linked list data structure. The system can dequeue the next process from the front of the queue, run the process until completion (or enqueue the process at the end of the line in more complex schemes), then enqueue the process at the end of the line, allowing the next process to use the CPU.

Advantages:

· simple

· easy

· first come, first served

Disadvantages:

· This scheduling method is nonpreemptive, that is, the process will run until it finishes.

· Because of this nonpreemptive scheduling, short processes which are at the back of the queue have to wait for the long process at the front to finish

· CONVOY EFFECT

CPU bound jobs will hold CPU until exit or I/O (but I/O rare for CPU-bound thread)

· long periods where no I/O requests issued, and CPU held

· Result: poor I/O device utilization

Example 1

PROCESS

ARRIVAL TIME

BURST TIME

Gantt chart

0 24 27 30

PROCESS

WAIT TIME

TURN AROUND TIME

Total Wait Time

0 + 24 + 27 = 51 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes)

51/3 = 17 ms

Total Turn Around Time

24 + 27 + 30 = 81 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)

81 / 3 = 27 ms

3 jobs/30 sec = 0.1 jobs/sec

Example 2

In the above example, if order of process arriving is p2, p3, p1 instead of p1, p2, p3 then

Gantt chart

0 3 6 30

PROCESS

WAIT TIME

TURN AROUND TIME

Total Wait Time

6 + 0 + 3 = 9 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes)

9/3 = 3 ms

Total Turn Around Time

30 + 3 + 6 = 39 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)

39 / 3 = 13 ms

Throughput

3 jobs/30 sec = 0.1 jobs/sec

Thus, it can be clearly stated that scheduling of processes can significantly reduce waiting and turn around time.

Example 3

PROCESS

ARRIVAL TIME

BURST TIME

Gantt chart

0 80 100 110 130 180

PROCESS

WAIT TIME

TURN AROUND TIME

100

110

130

180

Total Wait Time

0 + 80 + 100 + 110 + 130 = 420 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes)

420/5 = 84 ms

Total Turn Around Time

80 + 100 + 110 + 130 + 180 = 600 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)

600/5 = 120 ms

Throughput

5 jobs/180 sec = 0.2778 jobs/sec

Code to implement fifo algorithm

#include<stdio.h>

#include<conio.h>

#include<process.h>

void main()

{

char p[10][5];

int tot=0,wt[10],i,n;

float avg=0;

clrscr();

printf("enter no of processes:");

scanf("%d",&n);

for(i=0;i<n;i++)

{

printf("enter process%d name: ",i+1);

scanf("%s",&p[i]);

printf("enter process time");

scanf("%d",&pt[i]);

}

wt[0]=0;

for(i=1;i<n;i++)

{

wt[i]=wt[i-1]+et[i-1];

tot=tot+wt[i];

}

avg=(float)tot/n;

printf("p_name P_time w_time ");

for(i=0;i<n;i++)

printf("%s %d %d ",p[i],et[i],wt[i]);

printf("total waiting time=%d avg waiting time=%f",tot,avg);

getch();

}

Shortest-Job-First (SJR) Scheduling

Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time.

Two schemes:

1. non pre- emptive – once CPU given to the process it cannot be preempted until completes its CPU burst.

2. preemptive – if a new process arrives with CPU burst length less than remaining time of current executing

process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF).

SJF is optimal – gives minimum average waiting time for a given set of processes.

Shortest-Remaining-Time (SRT) Scheduling

The SRT is the preemtive counterpart of SJF and useful in time-sharing environment.

In SRT scheduling, the process with the smallest estimated run-time to completion is run next, including new arrivals.

In SJF scheme, once a job begin executing, it run to completion.

In SJF scheme, a running process may be preempted by a new arrival process with shortest estimated run-time.

Process Arrival Time Burst Time

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4

SJF (non-preemptive)

0 7 8 12 16

Average waiting time = [0 +(8-2)+(7-4) +(12-5)] /4 =4

Example of Preemptive SJF

Proces Arrival Time Burst Time

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4

SJF (preemptive)

0 2 4 5 7 11 16

Average waiting time = (9 + 1 + 0 +2)/4 =3

Implementation of srt algorithm

#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: ");

scanf("%d",&n);

printf("enter arrival time ");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

printf("enter burst time ");

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(" Average waiting time = %lf ",avg/n);

printf("Average Turnaround time = %lf",tt/n);

return 0;

}

Round Robin (RR)

Each process is given a certain amount of CPU time (a time slice), and if it is not finished by the end of the time slice, the process is moved to the back of the process queue, and the next process in line is moved to the CPU.

A common variant on Round Robin allows a process to give up the remainder of its time slice if it doesn't need it. This might be because it is waiting for a particular event, or because it is completed.

Analogy

At a mall, the cashier offers each customer a certain amount of time to checkout their items, and if they aren't done with their items by the time set by the cashier, the customer must go to the back of the line and wait. This repeats until all items are checked out.

Advantages and Disadvantages

If the set time is too short, then too much process switching will take place and the design will become slow. If the set time is too long, then the system may become unresponsive, time wasting and would emulate First Come First Served.

Example of RR with Time Quantum = 4

Process Burst Time

P1 24

P2 3

P3 3

The Gantt chart is:

0 4 7 10 14 18 22 26 30

Average waiting time = [(30-24)+4+7]/3 = 17/3 =5.66

Implementation of RR algorithm

#include<stdio.h>

#include<conio.h>

#include<process.h>

#include<string.h>

void main()

{

char p[10][5];

int et[10],wt[10],timer=3,count,pt[10],rt,i,j,totwt=0,t,n=5,found=0,m;

float avgwt;

clrscr();

for(i=0;i<n;i++)

{

printf("enter the process name : ");

scanf("%s",&p[i]);

printf("enter the processing time : ");

scanf("%d",&pt[i]);

}

m=n;

wt[0]=0;

i=0;

{

if(pt[i]>timer)

{

rt=pt[i]-timer;

strcpy(p[n],p[i]);

pt[n]=rt;

et[i]=timer;

n++;

}

else

{

et[i]=pt[i];

}

i++;

wt[i]=wt[i-1]+et[i-1];

}while(i<n);

count=0;

for(i=0;i<m;i++)

{

for(j=i+1;j<=n;j++)

{

if(strcmp(p[i],p[j])==0)

{

count++;

found=j;

}

if(found!=0)

{

wt[i]=wt[found]-(count*timer);

count=0;

found=0;

}

for(i=0;i<m;i++)

{

totwt+=wt[i];

}

avgwt=(float)totwt/m;

for(i=0;i<m;i++)

{

printf(" %s %d %d",p[i],pt[i],wt[i]);

}

printf(" total waiting time %d ",totwt);

printf("total avgtime %f",avgwt);

}

PROCESS

ARRIVAL TIME

BURST TIME

Navigate

You will implement a calculator using stacks and queues in C++. You may use the

You will implement a framework for CPU scheduling with three scheduling algorith

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

You will implement a framework for CPU scheduling with three scheduling algorith

Question

Explanation / Answer

Related Questions

Navigate