Description:This piece of code was a demonstration of CPU scheduling algorithms for an undergraduate class in operating systems.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define min( a, b ) (((a) < (b))?(a):(b))
#define max( a, b ) (((a) > (b))?(a):(b))
#define MAXRUN 1000
// structure for process data
typedef struct
{
int id;
int arrival;
int burst;
int used;
int wait;
int start;
} process;
/**
* length
* calculate the number of digits a given number is composed of
* @param number the number to break down into digits
* @return the number of digits in <i>number</i>
*/
int length( int number )
{
int len = 1;
while ( number /= 10 )
{
// determines decades
++len;
}
return len;
}
/**
* getNumber
* Prompt the user for input, expect a minimum valid value, and respond with
* an invalid prompt if necessary. This will continue to request input until
* the minimum accepted value is received.
* @param question The initial prompt for the user's input
* @param invalid The invalid prompt to use if necessary
* @param minimum The minimum acceptable value
* @return the validated value entered by the user
*/
int getNumber( const char *question, const char *invalid, int minimum )
{
//requesting an input number and prints invalid and asks again. will
//require correction if less than 0.
int first = 1;
int out = minimum - 1;
// loop until input is valid
do
{
// If this isn't the first time this loop has run then the user entered
// an invalid value during the last iteration.
if ( !first )
{
printf( "\n\n%s ", invalid );
}
else
{
first = 0;
}
printf( "%s> ", question );
// wait for numerical input from the user
scanf( "%d", &out );
}
while( out < minimum );
return out;
}
/**
* getDetails
* Prompt the user for details concerning the arrival and burst times for a
* given process.
* @param proc A pointer to the process to manipulate. The process should have a
* "good" id associated with it.
*/
void getDetails( process *proc )
{
//initializing structure
proc->arrival = -1;
proc->burst = -1;
proc->used = 0;
proc->wait = 0;
proc->start = -1;
char question[50];
//prompts for user to the arrival time
sprintf( question, "Arrival time for P%d", proc->id );
proc->arrival = getNumber( question, "Invalid arrival time.", 0 );
//prompts for user to the burst time
sprintf( question, "Burst time for P%d", proc->id );
proc->burst = getNumber( question, "Invalid burst time.", 1 );
}
/**
* outputTime
* Generates the time axis for the Gantt chart
* @param len The number of time slices needed for the Gantt chart
*/
void outputTime( int len )
{
int l = length( len );
int mag;
int c, j;
char k;
int i;
for( i = 0; i < l; ++i )
{
mag = 1;
for ( j = i+1; j < l; ++j )
{
mag *= 10;
}
printf( (i == l-1) ? " Time " : " " );
for ( c = 1; c <= len; ++c )
{
k = (c/mag) % 10;
printf( "%c ", (k > 0 || i == l-1) ? '0' + k : ' ' );
}
printf( "\n" );
}
}
/**
* outputRule
* Generate a horizontal rule
* @param the length of the horizontal rule to generate
*/
void outputRule( int len )
{
//automatically prints ---- the proper length to match gantt chart length
printf("-----------");
int i;
for (i = 0; i < len; ++i )
{
printf("--");
}
printf("\n");
}
/**
* outputGantt
* Output a Gantt Chart
* @param len The number of time slices required to display the chart
* @param processes Pointer to the array of processes
* @param num The number of processes
* @param run
*/
void outputGantt( int len, process *processes, int num, int *run )
{
//prepare to print Gantt chart
int j,i;
printf("Gantt\n");
outputRule( len );//prints -------- top of chart
outputTime( len );//prints time units
outputRule( len );//prints -------- bottom of chart
for (i = 0; i < num; ++i )
{
printf( " P%-9d", processes[i].id );
for( j = 0; j < len; ++j )
{
printf( "%c ", (run[ j ] == i) ? 'x' : ' ' );
}
printf("\n");
}
outputRule( len );
}
/**
* PSPN
* Premptive Shortest Process Next scheduling algorithm
* @param processes The array of processes
* @param num The number of processes
* @param run The time slice pool
* @param Max The maximum number of time slices
* @param minAdmit The first arrival time for the processes
* @return The number of time slices required
*/
int PSPN( process* processes, int num, int *run, int Max, int minAdmit )
{
int j, i;
int len = 0;
int done;
for( i = 0; i < Max; ++i )
{
done = 0;
// process decision algorithm
for ( j = 0; j < num; ++j )
{
// check to see if the process has arrived and is still running
if ( i + minAdmit >= processes[ j ].arrival && processes[ j ].used < processes[ j ].burst )
{
// if another process already is in this time slice
if ( run[ i ] >= 0 )
{
// if the incoming process has a shorter burst time
if ( processes[ run[ i ] ].burst > processes[ j ].burst )
{
++processes[ run[i] ].wait;
run[ i ] = j;
}
}
else
{
run[ i ] = j;
}
}
// increment the counter of processes that have completed as necessary
if ( processes[ j ].used == processes[ j ].burst )
{
++done;
}
}
// check to see if this is the processes first time slice
if ( processes[ run[ i ] ].start < 0 )
{
processes[ run[ i ] ].start = i;
}
// check to see if all processes are done executing
if ( done == num )
{
len = i;
break;
}
++processes[ run[ i ] ].used;
}
return len;
}
/**
* calculateWait
* Calculate the time spent waiting across all processes
* @param processes The array of processes
* @param num The number of processes
* @return The total wait time
*/
int calculateWait( process *processes, int num )
{
int wait = 0, i;
for (i = 0; i < num; ++i )
{
wait += processes[ i ].wait + processes[i].start - processes[i].arrival;
}
return wait;
}
/**
* outputChart
* Generate the chart of processes
* @param processes The array of processes
* @param num The number of processes
*/
void outputChart( process *processes, int num )
{
int i;
printf( " Process Arrival Time Burst-Time\n" );
printf( "-----------------------------------------\n" );
for (i = 0; i < num; ++i )
{
printf( " P%-11d%-17d%d\n", processes[ i ].id, processes[ i ].arrival, processes[ i ].burst );
}
printf( "-----------------------------------------\n" );
}
/**
* initalizeRun
* Initalize the time slice pool
* @param run The time slice pool to manipulate
* @param Max The size of the time slice pool
*/
void initializeRun( int *run, int Max )
{
int i;
for ( i = 0; i < Max; ++i )
{
run[ i ] = -1;
}
}
/**
* gatherDetails
* Gather all the details necessary for the processes requested
* @param processes The array of processes to manipulate
* @param num The number of processes
* @return The earliest arrival time
*/
int gatherDetails( process *processes, int num )
{
int i, minAdmit = INT_MAX;
for (i = 0; i < num; ++i )
{ //request from user the arrival and burst times for each process.
printf( "\n" );
processes[ i ].id = i + 1;
getDetails( &processes[ i ] );
minAdmit = min( minAdmit, processes[ i ].arrival );
//determines earliest arrival time.
}
return minAdmit;
}
/**
* main
* primary function for the program
* @param argc Number of arguments to the program (unused)
* @param argv Array of argument strings
*/
int main (int argc, const char * argv[])
{
process *processes;
int num = 0;
int minAdmit = 0;
int run[ MAXRUN ];
printf( "\n" );
num = getNumber( "Please enter the number of processes", "Invalid number.", 1 );
// allocates memory for processes
processes = (process *) malloc( sizeof( process ) * num );
initializeRun( run, MAXRUN );
gatherDetails( processes, num );
printf( "\n\n" );
// prepare to print data chart about process details entered.
outputChart( processes, num );
printf( "\n\n" );
//end if details chart for processes (top chart printed)
int len = PSPN( processes, num, run, MAXRUN, minAdmit );
outputGantt( len, processes, num, run );
int wait = calculateWait( processes, num );
printf( "\nAverage wait time: %.2f\n", ((float)wait)/num );
free( processes );
return 0;
}