tag:blogger.com,1999:blog-15918933349081956232024-03-05T17:03:37.920-08:00[C] LecturesAnonymoushttp://www.blogger.com/profile/10518516538787039941noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-1591893334908195623.post-56666236846298276942015-11-26T23:49:00.000-08:002015-11-26T23:49:26.744-08:00Shortest Job First [SJF] Process Scheduling Program with Gantt Chart<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
Another type of process scheduling algorithm is the Shortest Job First [SJF] process scheduling algorithm, In SJF the CPU is allocated to the process which has the smallest CPU burst time out of all the processes and so on. If two or more than two processes share the same CPU burst time then <a href="http://clecture.blogspot.com/2015/11/First-Come-First-Serve-FCFS-Process-Scheduling-with-Gantt-Chart.html" target="_blank"><b>First Come First Serve [FCFS] scheduling</b></a> is used to solve the conflict between those processes.<br />
<br />
SJF scheduling can be done in both ways,<br />
<ul style="text-align: left;">
<li><b><span style="font-size: large;">Nonpreemptive </span>-</b><br />In Nonpreemptive SJF scheduling algorithm, Once the CPU has been allocated to a process It cannot jump from current process to another. Firstly it must completely finish the execution of the current process then only it can be allocated to some other processes.</li>
<li><span style="font-size: large; font-weight: bold;">Preemptive -</span><br />In Preemptive SJF, Even if the CPU is allocated to a process say "A", It can jump from "A" to some other process "B" if the CPU burst time of "B" is smaller than that of the process "A".</li>
</ul>
<div>
Shortest Job First [SJF] process scheduling algorithm is much more <b>Optimal </b>and gives the <b>Minimum Average Waiting Time </b>as compared to FCFS and other process scheduling algorithms. Because executing a smaller process before the larger one decreases the waiting time for smaller process much more than it increases the waiting time of larger process. Hence, the average waiting time decreases.</div>
<div>
</div>
<div class="notify notify-yellow">
<span class="symbol icon-excl"></span> In this article we will be only sharing <b>Nonpreemptive SJF </b>program.</div>
<h3 style="text-align: left;">
Shortest Job First Process Scheduling Program</h3>
<div>
Below is the program for SJF process scheduling with <b>Gantt Chart </b>in C,<br />
<br /></div>
</div>
<pre style="background: #2a211c; color: #bdae9d;"><span style="color: #43a8ed; font-weight: 700;">/</span><span style="color: #43a8ed; font-weight: 700;">/</span><span style="color: #318495;">This</span> <span style="color: #c5656b; font-weight: 700;">is</span> <span style="color: #c5656b; font-weight: 700;">a</span> <span style="color: #318495;">Program</span> <span style="color: #c5656b; font-weight: 700;">for</span> <span style="color: #318495;">Shortest</span> <span style="color: #318495;">Job</span> <span style="color: #318495;">First</span> <span style="color: #318495;">Process</span> <span style="color: #318495;">Scheduling</span> <span style="color: #c5656b; font-weight: 700;">by</span> [<span style="color: #318495;">C</span>] <span style="color: #318495;">Lectures</span>.
<span style="color: #43a8ed; font-weight: 700;">#</span><span style="text-decoration: underline;">include</span><stdio.h>
#include<graphics.h>
#include<dos.h>
#include<conio.h>
void main()
{
<span style="color: #318495;">int</span> <span style="color: #318495;">no</span>,<span style="color: #318495;">i</span>,<span style="color: #318495;">j</span>,<span style="color: #318495;">sum</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>,<span style="color: #318495;">position</span>,<span style="color: #318495;">temp</span>,<span style="color: #318495;">temp1</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>,<span style="color: #318495;">temp2</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>,<span style="color: #318495;">temp_tat</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>,<span style="color: #318495;">temp_wt</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #c5656b; font-weight: 700;">int</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #44aa43;">10</span>],<span style="color: #318495;">process</span>[<span style="color: #44aa43;">10</span>],<span style="color: #318495;">avg_waiting_time</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>,<span style="color: #318495;">avg_turnaround_time</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #c5656b; font-weight: 700;">int</span> <span style="color: #c5656b; font-weight: 700;">gdriver</span> <span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #318495;">DETECT</span>, <span style="color: #318495;">gmode</span>;
<span style="color: #318495;">initgraph</span>(&<span style="color: #c5656b; font-weight: 700;">gdriver</span>,&<span style="color: #c5656b; font-weight: 700;">gmode</span>,<span style="color: #049b0a;">"C:<span style="color: #2fe420;">\\</span>TC<span style="color: #2fe420;">\\</span>BGI "</span>);
<span style="color: #318495;">clrscr</span>();
<span style="color: #318495;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Shortest Job First Process Scheduling : "</span>);
<span style="color: #318495;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Enter the number of Processes : "</span>);
<span style="color: #318495;">scanf</span>(<span style="color: #049b0a;">"%d"</span>,&<span style="color: #c5656b; font-weight: 700;">no</span>);
<span style="color: #318495;">for</span>(<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">no</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #c5656b; font-weight: 700;">process</span>[<span style="color: #c5656b; font-weight: 700;">i</span>]<span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">i</span>;
<span style="color: #ff9358; font-weight: 700;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Enter CPU Burst time for process P%d : "</span>,<span style="color: #c5656b; font-weight: 700;">i</span>);
<span style="color: #ff9358; font-weight: 700;">scanf</span>(<span style="color: #049b0a;">"%d"</span>,&<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>]);
}
<span style="color: #318495;">cpuburst</span>[<span style="color: #44aa43;">0</span>]<span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #318495;">for</span>(<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">no</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #c5656b; font-weight: 700;">position</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">i</span>;
<span style="color: #ff9358; font-weight: 700;">for</span>(<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">no</span>;<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #43a8ed; font-weight: 700;">if</span>(<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">j</span>]<span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">position</span>])
<span style="color: #c5656b; font-weight: 700;">position</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">j</span>;
}
<span style="color: #c5656b; font-weight: 700;">temp</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>];
<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>]<span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">position</span>];
<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">position</span>]<span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">temp</span>;
<span style="color: #c5656b; font-weight: 700;">temp</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">process</span>[<span style="color: #c5656b; font-weight: 700;">i</span>];
<span style="color: #c5656b; font-weight: 700;">process</span>[<span style="color: #c5656b; font-weight: 700;">i</span>]<span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">process</span>[<span style="color: #c5656b; font-weight: 700;">position</span>];
<span style="color: #c5656b; font-weight: 700;">process</span>[<span style="color: #c5656b; font-weight: 700;">position</span>]<span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">temp</span>;
}
<span style="color: #ff9358; font-weight: 700;">for</span>(<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">no</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #c5656b; font-weight: 700;">sum</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>];
<span style="color: #c5656b; font-weight: 700;">avg_waiting_time</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">-</span><span style="color: #44aa43;">1</span>];
<span style="color: #c5656b; font-weight: 700;">avg_turnaround_time</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>];
<span style="color: #c5656b; font-weight: 700;">temp_wt</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #c5656b; font-weight: 700;">temp_tat</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #ff9358; font-weight: 700;">for</span>(<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #c5656b; font-weight: 700;">i</span>;<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #c5656b; font-weight: 700;">temp_tat</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">j</span>];
<span style="color: #c5656b; font-weight: 700;">temp_wt</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;">-</span><span style="color: #44aa43;">1</span>];
}
<span style="color: #ff9358; font-weight: 700;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Waiting time for process P%d : %d"</span>,<span style="color: #c5656b; font-weight: 700;">process</span>[<span style="color: #c5656b; font-weight: 700;">i</span>],<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">-</span><span style="color: #44aa43;">1</span>]<span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #c5656b; font-weight: 700;">temp_wt</span>);
<span style="color: #ff9358; font-weight: 700;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Turn around time for process P%d : %d <span style="color: #2fe420;">\n</span>"</span>,<span style="color: #c5656b; font-weight: 700;">process</span>[<span style="color: #c5656b; font-weight: 700;">i</span>],<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>]<span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #c5656b; font-weight: 700;">temp_tat</span>);
<span style="color: #c5656b; font-weight: 700;">avg_turnaround_time</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">temp_tat</span>;
<span style="color: #c5656b; font-weight: 700;">avg_waiting_time</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">temp_wt</span>;
}
<span style="color: #ff9358; font-weight: 700;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span><span style="color: #2fe420;">\n</span>Average waiting time : %d"</span>,<span style="color: #c5656b; font-weight: 700;">avg_waiting_time</span><span style="color: #43a8ed; font-weight: 700;">/</span><span style="color: #c5656b; font-weight: 700;">no</span>);
<span style="color: #ff9358; font-weight: 700;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Average turn around time : %d"</span>,<span style="color: #c5656b; font-weight: 700;">avg_turnaround_time</span><span style="color: #43a8ed; font-weight: 700;">/</span><span style="color: #c5656b; font-weight: 700;">no</span>);
<span style="color: #ff9358; font-weight: 700;">outtextxy</span>(<span style="color: #44aa43;">80</span>,<span style="color: #44aa43;">460</span>,<span style="color: #049b0a;">"Do Not Press Any Key! This screen will be cleared automatically in 10s."</span>);
<span style="color: #ff9358; font-weight: 700;">delay</span>(<span style="color: #44aa43;">10000</span>);
<span style="color: #ff9358; font-weight: 700;">cleardevice</span>();
<span style="color: #ff9358; font-weight: 700;">line</span>(<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">150</span>);
<span style="color: #ff9358; font-weight: 700;">line</span>(<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">sum</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">10</span>),<span style="color: #44aa43;">100</span>);
<span style="color: #ff9358; font-weight: 700;">line</span>(<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">sum</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">10</span>),<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">sum</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">10</span>),<span style="color: #44aa43;">150</span>);
<span style="color: #ff9358; font-weight: 700;">line</span>(<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">150</span>,<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">sum</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">10</span>),<span style="color: #44aa43;">150</span>);
<span style="color: #ff9358; font-weight: 700;">for</span>(<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #c5656b; font-weight: 700;">no</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #c5656b; font-weight: 700;">temp1</span> <span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>];
<span style="color: #c5656b; font-weight: 700;">temp2</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">temp1</span>;
<span style="color: #ff9358; font-weight: 700;">line</span>(<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">temp2</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">10</span>),<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">temp2</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">10</span>),<span style="color: #44aa43;">150</span>);
}
<span style="color: #ff9358; font-weight: 700;">getch</span>();
<span style="color: #ff9358; font-weight: 700;">closegraph</span>();
}
</pre>
<h4 style="text-align: left;">
Output of the Program</h4>
<div>
There will be two output screens for our program, In first screen we will give our inputs to the program and it will print out the waiting time & turn around time for all the process individually and also the average waiting time and average turnaround time of the processes. And in the second output screen we will get the Gantt chart of our inputs.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<img alt="Shortest Job First [SJF] process scheduling algorithm is Optimal and gives the Minimum Average Waiting Time. In this article we will be sharing SJF process scheduling program in C/C++ programming language." border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBkLMas1tCrL0kwYnw_mKK9ZMnFaJs3dtJezr8g4B3t8S_7e4EwOKDE7aAR1lpSJAHD4jYJ1-sgbFei6U9zqMtCYeo52lWJoxVAXfJJH7eFWLOZwBf3ofja7scn3STKZIA8LsgnEqpDGI/s1600/Shortest+Job+First+OP.png" title="Shortest Job First Process Scheduling Program Output" /></div>
<div class="separator" style="clear: both; text-align: center;">
<img alt="Shortest Job First [SJF] process scheduling algorithm is Optimal and gives the Minimum Average Waiting Time. In this article we will be sharing SJF process scheduling program with Gantt chart in C/C++ programming language." border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwIofa-8SFuLss5sjigzs10oBVs2iOAJGUug4azKhINNozzOBJWj1R1eM3VqAELjHQVRFCiwHu8YmyuhPcqoA0cD6oLPKYLgn98vA_Vj-QSBWJ8o0UDRNcQ4mmvkj5MiS3KzGFTJmo2Lo/s1600/Shortest+Job+First+OP+with+Gantt+Chart.png" title="Shortest Job First Process Scheduling Program Output with Gantt Chart" /></div>
<br />
Now let us check the validity of our program to see if the output calculated by our program is same as the manually calculated output,<br />
Suppose there are 4 processes P1, P2, P3 and P4.<br />
Assuming that all the four process arrived at 0ms, So the Arrival time for all the process is 0ms.<br />
<br />
The CPU burst time for process P1 is 9ms,<br />
The CPU burst time for process P2 is 3ms,<br />
<div>
The CPU burst time for process P3 is 6ms,</div>
<div>
The CPU burst time for process P4 is 5ms.<br />
<br />
As the CPU burst time of process P2 is smaller than that of all the other processes, the CPU will be allocated to P2. Hence, the Waiting time for process P2 will be 0ms<br />
<br />
After the process P2 has been completely executed then the CPU will be allocated to the next smallest process P4 which has CPU burst time of 5ms. Hence, the Waiting time for process P4 will be 3ms<br />
<br />
After executing process P2 and P4 the CPU will be then allocated to the next smallest process P3 which has the CPU burst time of 6ms. Hence, the Waiting time for process P3 will be equals to 3ms + 5ms = 8ms<br />
<br />
Now at last the CPU will be allocated to process P1 which has the largest CPU burst time of all the other process. The Waiting time for process P1 will be 3ms + 5ms + 6ms = 14ms<br />
<br />
<b><i>The Average Waiting Time = (0ms + 3ms + 8ms + 14ms)/4 = 6ms</i></b><br />
<b><i><br /></i></b>
Now for Turn around time, As we know that the process P2 has the smallest CPU burst time i.e 3ms so the CPU will be allocated to process P2. Hence, the Turn around time for P2 = 3ms<br />
<br />
After the process P2 as been executed completely, the CPU will be then allocated to process P4 which has the CPU burst time of 5ms. So, the Turn around time for process P4 = 3ms + 5ms = 8ms<br />
<br />
Now the CPU will be allocated to process P3 as it has the smallest CPU burst time i.e 6ms as compared to P1. So, the Turn around time for P3 = 3ms + 5ms + 6ms = 14ms<br />
<br />
At last the CPU will be allocated to process P1 which has the largest CPU burst time of all the process i.e 9ms. So, the Turn around time for process P1 = 3ms + 5ms + 6ms + 9ms = 23ms<br />
<br />
<b><i>The Average Turn Around Time = (3ms + 8ms + 14ms + 23ms)/4 = 12ms</i></b><br />
<br />Download Source Code from <a href="https://drive.google.com/open?id=0BwrXfh6z7ZNKM1ZEdUoxLXpuN0k" rel="nofollow" target="_blank">Here</a>.</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/10518516538787039941noreply@blogger.com1Jabalpur, Madhya Pradesh, India23.181467 79.98640709999995122.947910500000003 79.663683599999956 23.4150235 80.309130599999946tag:blogger.com,1999:blog-1591893334908195623.post-48796704509346474812015-11-24T00:53:00.000-08:002015-11-26T22:39:46.591-08:00First Come First Serve [FCFS] Process Scheduling Program with Gantt Chart<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
First Come First Serve [FCFS] process scheduling is the simplest type of process scheduling algorithm. FCFS can be easily implemented using the <b>First In First Out [FIFO]</b> queue, arriving jobs are inserted in the tail of ready queue and process to be executed next is removed from the head of the queue.<br />
<br />
FCFS scheduling is <b>Nonpreemptive</b> type of scheduling i.e CPU can not jump from one process to another before it's completion. Once the CPU is allocated to a process, that process keeps the CPU until it is executed completely and only then after CPU can be allocated to another process.<br />
<br />
In General, the average waiting time for FCFS algorithm is often quite long. The average waiting time for FCFS algorithm may vary depending upon the CPU burst times of the processes.<br />
<br />
<h3 style="text-align: left;">
First Come First Serve Process Scheduling Program </h3>
<div>
<br /></div>
<div>
Below is the program for FCFS process scheduling with <b>Gantt chart</b> in c,</div>
<div>
<br /></div>
</div>
<pre style="background: #2a211c; color: #bdae9d;"><span style="color: #43a8ed; font-weight: 700;">/</span><span style="color: #43a8ed; font-weight: 700;">/</span><span style="color: #318495;">This</span> <span style="color: #c5656b; font-weight: 700;">is</span> <span style="color: #c5656b; font-weight: 700;">a</span> <span style="color: #c5656b; font-weight: 700;">program</span> <span style="color: #c5656b; font-weight: 700;">for</span> <span style="color: #318495;">First</span> <span style="color: #318495;">Come</span> <span style="color: #318495;">First</span> <span style="color: #318495;">Serve</span> <span style="color: #318495;">Process</span> <span style="color: #318495;">Scheduling</span> <span style="color: #c5656b; font-weight: 700;">by</span> [<span style="color: #318495;">C</span>] <span style="color: #318495;">Lectures</span>.
<span style="color: #43a8ed; font-weight: 700;">#</span><span style="text-decoration: underline;">include</span><stdio.h>
#include<graphics.h>
#include<conio.h>
void main()
{
<span style="color: #318495;">int</span> <span style="color: #318495;">temp1</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>,<span style="color: #318495;">temp2</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>,<span style="color: #318495;">i</span>,<span style="color: #318495;">j</span>,<span style="color: #318495;">no</span>,<span style="color: #318495;">temp_tat</span>,<span style="color: #318495;">temp_wt</span>,<span style="color: #318495;">sum</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #c5656b; font-weight: 700;">int</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #44aa43;">10</span>],<span style="color: #318495;">avg_waiting_time</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>,<span style="color: #318495;">avg_turnaround_time</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #c5656b; font-weight: 700;">int</span> <span style="color: #c5656b; font-weight: 700;">gdriver</span> <span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #318495;">DETECT</span>, <span style="color: #318495;">gmode</span>;
<span style="color: #318495;">initgraph</span>(&<span style="color: #c5656b; font-weight: 700;">gdriver</span>,&<span style="color: #c5656b; font-weight: 700;">gmode</span>,<span style="color: #049b0a;">"C:<span style="color: #2fe420;">\\</span>TC<span style="color: #2fe420;">\\</span>BGI "</span>);
<span style="color: #318495;">clrscr</span>();
<span style="color: #318495;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>First Come First Serve Process Scheduling : <span style="color: #2fe420;">\n</span>"</span>);
<span style="color: #318495;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Enter number of processes : "</span>);
<span style="color: #318495;">scanf</span>(<span style="color: #049b0a;">"%d"</span>,&<span style="color: #c5656b; font-weight: 700;">no</span>);
<span style="color: #318495;">for</span>(<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">no</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #ff9358; font-weight: 700;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Enter CPU burst for process P%d : "</span>,<span style="color: #c5656b; font-weight: 700;">i</span>);
<span style="color: #ff9358; font-weight: 700;">scanf</span>(<span style="color: #049b0a;">"%d"</span>,&<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>]);
}
<span style="color: #318495;">cpuburst</span>[<span style="color: #44aa43;">0</span>]<span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #318495;">for</span>(<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #c5656b; font-weight: 700;">no</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #c5656b; font-weight: 700;">sum</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>];
<span style="color: #c5656b; font-weight: 700;">avg_waiting_time</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">-</span><span style="color: #44aa43;">1</span>];
<span style="color: #c5656b; font-weight: 700;">avg_turnaround_time</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>];
<span style="color: #c5656b; font-weight: 700;">temp_wt</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #c5656b; font-weight: 700;">temp_tat</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">0</span>;
<span style="color: #ff9358; font-weight: 700;">for</span>(<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #c5656b; font-weight: 700;">i</span>;<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #c5656b; font-weight: 700;">temp_tat</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">j</span>];
<span style="color: #c5656b; font-weight: 700;">temp_wt</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">j</span><span style="color: #43a8ed; font-weight: 700;">-</span><span style="color: #44aa43;">1</span>];
}
<span style="color: #ff9358; font-weight: 700;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Waiting time for process P%d : %d"</span>,<span style="color: #c5656b; font-weight: 700;">i</span>,<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">-</span><span style="color: #44aa43;">1</span>]<span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #c5656b; font-weight: 700;">temp_wt</span>);
<span style="color: #ff9358; font-weight: 700;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Turn around time for process P%d : %d <span style="color: #2fe420;">\n</span>"</span>,<span style="color: #c5656b; font-weight: 700;">i</span>,<span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>]<span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #c5656b; font-weight: 700;">temp_tat</span>);
<span style="color: #c5656b; font-weight: 700;">avg_turnaround_time</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">temp_tat</span>;
<span style="color: #c5656b; font-weight: 700;">avg_waiting_time</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">temp_wt</span>;
}
<span style="color: #318495;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span><span style="color: #2fe420;">\n</span>Average waiting time : %d"</span>,<span style="color: #c5656b; font-weight: 700;">avg_waiting_time</span><span style="color: #43a8ed; font-weight: 700;">/</span><span style="color: #c5656b; font-weight: 700;">no</span>);
<span style="color: #318495;">printf</span>(<span style="color: #049b0a;">"<span style="color: #2fe420;">\n</span>Average turn around time : %d"</span>,<span style="color: #c5656b; font-weight: 700;">avg_turnaround_time</span><span style="color: #43a8ed; font-weight: 700;">/</span><span style="color: #c5656b; font-weight: 700;">no</span>);
<span style="color: #318495;">outtextxy</span>(<span style="color: #44aa43;">80</span>,<span style="color: #44aa43;">460</span>,<span style="color: #049b0a;">"Do Not Press Any Key! This screen will be cleared automatically in 10s."</span>);
<span style="color: #318495;">delay</span>(<span style="color: #44aa43;">10000</span>);
<span style="color: #318495;">cleardevice</span>();
<span style="color: #318495;">line</span>(<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">150</span>);
<span style="color: #318495;">line</span>(<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">sum</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">15</span>),<span style="color: #44aa43;">100</span>);
<span style="color: #318495;">line</span>(<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">sum</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">15</span>),<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">sum</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">15</span>),<span style="color: #44aa43;">150</span>);
<span style="color: #318495;">line</span>(<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">150</span>,<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">sum</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">15</span>),<span style="color: #44aa43;">150</span>);
<span style="color: #318495;">for</span>(<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">=</span><span style="color: #44aa43;">1</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;"><</span><span style="color: #c5656b; font-weight: 700;">no</span>;<span style="color: #c5656b; font-weight: 700;">i</span><span style="color: #43a8ed; font-weight: 700;">++</span>)
{
<span style="color: #c5656b; font-weight: 700;">temp1</span> <span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">cpuburst</span>[<span style="color: #c5656b; font-weight: 700;">i</span>];
<span style="color: #c5656b; font-weight: 700;">temp2</span> <span style="color: #43a8ed; font-weight: 700;">+</span><span style="color: #43a8ed; font-weight: 700;">=</span> <span style="color: #c5656b; font-weight: 700;">temp1</span>;
<span style="color: #ff9358; font-weight: 700;">line</span>(<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">temp2</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">15</span>),<span style="color: #44aa43;">100</span>,<span style="color: #44aa43;">100</span><span style="color: #43a8ed; font-weight: 700;">+</span>(<span style="color: #c5656b; font-weight: 700;">temp2</span><span style="color: #43a8ed; font-weight: 700;">*</span><span style="color: #44aa43;">15</span>),<span style="color: #44aa43;">150</span>);
}
<span style="color: #318495;">getch</span>();
<span style="color: #318495;">closegraph</span>();
}
</pre>
<h4 style="text-align: left;">
Output of the Program</h4>
</div>
<br />
There will be two output screens for our program, In first screen we will give our inputs to the program and it will print out the waiting time & turn around time for all the process individually and also the average waiting time and average turnaround time of the processes. And in the second output screen we will get the Gantt chart of our inputs.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<img alt="First Come First Serve [FCFS] is simplest, nonpreemptive type of process scheduling algorithm & can be implemented using First In First Out [FIFO] queue and can be represented using Gantt chart." border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdYYXNXXi-80rl-lpbjpZt1wbpAEt0oeI-M288qc_86XdxeEtkfONJyxnSvUmpG2B3e7d_6NN-IXX8oYH3OXNtghsK5FjlIxpKPo8hlAEJDwArWtyGI4o6hEANzuSu8C8p5ZR93Ipnw0M/s1600/FCFS_Process_Scheduling_IP.png" title="First Come First Serve Process Scheduling Output Screen." /></div>
<div class="separator" style="clear: both; text-align: center;">
<img alt="First Come First Serve [FCFS] is simplest, nonpreemptive type of process scheduling algorithm & can be implemented using First In First Out [FIFO] queue and can be represented using Gantt chart." border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGUEW8V8D6lSMa96H1T7LehvVAdIij-7gDhSNRbnm3_cI62FExVQnizAzOyaUv72uDjHvpy5OP3c2hW5dePUlZCSJSVoJ_du0lUmQCxZ_z-NQzHm1ZuvNwK91ijupQtK8zf6Tuw3EnbS8/s1600/FCFS_Process_Scheduling_OP.png" title="First Come First Serve Process Scheduling Output Screen i.e Gantt Chart." /></div>
<br />
Now let us check the validity of our program to see if the output calculated by our program is same as the manually calculated output,<br />
Suppose there are 4 processes P1, P2, P3 and P4.<br />
Assuming that all the four process arrived at 0ms, So the Arrival time for all the process is 0ms.<br />
<br />
The CPU burst time for process P1 is 7ms,<br />
The CPU burst time for process P2 is 9ms,<br />
<div>
The CPU burst time for process P3 is 3ms,</div>
<div>
The CPU burst time for process P4 is 5ms.<br />
<br />
Now, the waiting time for process P1 will be 0ms because P1 arrived at 0ms and didn't have to wait for any other processes to execute first. So, Waiting time for process P1 = 0ms<br />
<br />
The waiting time for process P2 will be 7ms because P2 have to wait for process P1 to complete its execution then only CPU will be allocated to P2. So, Waiting time for process P2 = 7ms<br />
<br />
The waiting time for process P3 will be 7ms + 9ms because P3 will have to wait for both process P1 and P2 to complete their execution then only the CPU will be allocated to process P3. So, Waiting time for process P3 = 16ms<br />
<br />
The waiting time for process P4 will be 7ms + 9ms + 3ms because P3 will have to wait for process P1, P2 and P3 to complete their execution then only the CPU will be allocated to process P4. So, Waiting time for process P4 = 19ms<br />
<br />
<b><i>The Average Waiting time = (0ms + 7ms + 16ms + 19ms)/4 = 10ms</i></b><br />
<b><i><br /></i></b>
Now, the turn around time for process P1 will be 7ms because P1 arrived at 0ms and didn't have to wait for any other processes to execute first and completed its execution at 7ms. So, Turn around time for process P1 = 7ms<br />
<br /></div>
<div>
The turn around time for process P2 will be 7ms + 9ms because P2 arrived at 0ms and had to wait for process P1 to execute first. So, Turn around time for process P2 = 16ms<br />
<br />
The turn around time for process P3 will be 7ms + 9ms + 3ms because P3 arrived at 0ms and had to wait for process P1 and P2 to execute first. So, Turn around time for P3 = 19ms<br />
<br />
The turn around time for process P4 will be 7ms + 9ms + 3ms + 5ms because P4 arrived at 0ms and had to wait for process P1, P2 and P3 to complete their execution first. So, Turn around time for P4 = 24ms<br />
<br />
<b><i>The Average Turn Around Time = (7ms + 16ms + 19ms + 24ms)/4 = 16ms</i></b><br />
<b><i><br /></i></b>
Download Source code from <a href="https://drive.google.com/file/d/0BwrXfh6z7ZNKMUM0MjJ2QjM2aE0/view?usp=sharing" rel="nofollow" target="_blank"><b>Here</b></a>.</div>
</div>
Anonymoushttp://www.blogger.com/profile/10518516538787039941noreply@blogger.com2Jabalpur, Madhya Pradesh, India23.181467 79.98640709999995122.947910500000003 79.663683599999956 23.4150235 80.309130599999946