prog-05.pdf

Programming Assignment #5

CSci 430, Spring 2019

Dates:

Assigned: Monday April 15, 2019 Due: Wednesday May 1, 2019 (before Midnight)

Objectives:

� Understand short-term process scheduling.

� Work with data structures to implement a round-robin scheduler.

� Look at e�ects of di�erent time slice quantum sizes on the round-robin scheduling algorithm.

� Use C/C++ to implement vector and matrix data structures, get practice in creating and using such data structures in C/C++.

Description:

Our textbooks chapter 9 discusses several possible short-term process scheduling policies. In this programming assignment exercise we will implement two of the preemptive policies, the simple shortest remaining time policy (SRT) and the round-robin scheduler with preemptive time slicing. Your program will be given a simple input �le, indicating the process name, its arrival time and its total service time, the same as the process scheduling examples from our textbook in Table 9.4 and Figure 9.5. You will simulate the execution of the required schedulers. As in previous assignments, you program will need to work non-interactively and be callable from the command line. The program will be provided with the �le name of a �le with process information, in the format discussed below. Your program will also be given the time slicing quantum parameter it is to use for the simulation, if round-robin scheduling is selected. Your program will need to output the results of running the set of simulated processes using the selected scheduling policy with the indicated time slice for the round-robin scheduler. Your program will have to output its results exactly as shown below in the required output format. Your program will also need to calculate some summary statistics for the simulated processes, including the turnaround time and Tr/Ts ratio for each process, and the mean Tr and Tr/Ts values for the given simulation.

Process simulation �le formats

The �les with the information about the processes to be simulated are fairly simple, and have the same information that our textbook uses to illustrate the process scheduling examples. Each simulation �le contains multiple rows of data, where each row consists of the process name, its arrival time, and its service time. Here is an example:

1

A 0 3

B 2 6

C 4 4

D 6 5

E 8 2

This �le is named process-01.sim in the zip archive of �les I have given you to get started on this assignment. This is also the same set of processes and start/service times used for all of the examples in table 9.4 and �gure 9.5.

Running Simulations

As with previous assignments you are required to support using your simulation from the command line. Your program will take the name of the �le containing the process information �rst. The next parameter will be either 'rr' to perform round-robin scheduling, or 'srt' if shortest remaining time policy is to be simulated. Finally, a 3rd parameter will be supplied for the round-robin scheduler, the time slice quantum to use. An example of running your �nished program should look like this:

$ ./p3 process-01.sim rr 4

A A A B B B B C C C C D D D D B B E E D

Name Fnsh T_r T_r/T_s

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

A 3 3 1

B 17 15 2.5

C 11 7 1.75

D 20 14 2.8

E 19 11 5.5

Here we are running the simulation using the set of process information given in the previous section and with a time slice quantum of 4.

Required Output

As shown above, your program must generate 2 bits of output. First of all, while running the simulation of the selected scheduling policy, you should display the process names in the order they are run. In the previous example, the sequence of scheduled/run processes was:

A A A B B B B C C C C D D D D B B E E D

This indicates that process A ran �rst (times 0, 1 and 2), followed by B running 4 times (times 3 to 7), etc. You are required to output the sequence of process runs as the �rst line of output, with a single space in between each process name as shown.

After the processes have run, you need to calculate and display the statistics for the processes that you just simulated. In our previous example, the statistics for our round-robin simulation with a time quantum of 4 time slices were:

Name Fnsh T_r T_r/T_s

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

A 3 3 1

B 17 15 2.5

C 11 7 1.75

2

D 20 14 2.8

E 19 11 5.5

For each process, you need to output the time when it �nished, the turnaround time (Tr) and the ratio of the turnaround time to the service time (Tr/Ts).

I have provided a zip �le with a �le named p3-start.cpp as a template to get you started. In addition, I have provided you with two process simulation �les, named process-01.sim and process-02.sim, with 2 sets of process information you can simulate. There are several examples of correct results generated for the two sets of inputs, named things like process-01-q1.res, process-01-q4.res, process-01-srt.res, etc. These are the correct results you should get for running your simulation with round-robin scheduling for various time quantums or for shortest remaining time scheduling.

3

prog-05.zip

p5-start.cpp

p5-start.cpp

/**
 *  @author  Jane Student
 *  @cwid    123 45 678
 *  @class   CSci 430, Spring 2018
 *  @ide     Visual Studio Express 2010
 *  @date    November 15, 2018
 *  @assg    prog-04
 *
 *  @description  This program implements a simulation of process
 *    scheduling policies.  In this program, we implement round-robin
 *    scheduling, where the time slice quantum can be specified as
 *    as a command line parameter.  And we also implement shortest
 *    remaining time (SRT) scheduling policy
 */
#include   < stdlib . h >
#include   < iostream >
#include   < iomanip >
#include   < fstream >
#include   < string >
#include   < list >
using   namespace  std ;


// global constants
// I won't test your round robin implementation with more than 20 processes
const   int  MAX_PROCESSES  =   20 ;
const   int  NO_PROCESS  =   0 ;

// Simple structure, holds all of the information about processes, their names
// arrival and service times, that we are to simulate.
typedef   struct
{
  string processName ;
   int  arrivalTime ;
   int  serviceTime ;
   // holds running count of time slices for current time quantum, when
   // serviceTime == quantum, time slice is up
   int  sliceTime ;
   // holds total number of time steps currently run, when == to
   // serviceTime process is done
   int  totalTime ;
   // holds time when process finishes, used to calculate final stats,
   // like T_r, T_r/T_s
   int  finishTime ;
   // a boolean flag, we will set this to true when the process is complete
   bool  finished ;
}   Process ;

// Process table, holds table of information about processes we are simulating
typedef   struct
{
   int  numProcesses ;
   Process *  process [ MAX_PROCESSES ];
}   ProcessTable ;


/** Create process table
 * Allocate memory for a new process table.  Load the process
 * information from the simulation file into a table with the process
 * information needed to perform the simulation.  At the same time we
 * initialize other information in process table for use in the
 * simulation.  Return the newly created ProcessTable
 *
 *  @param  processFilanem The name (char*) of the file to open and read
 *         the process information from.
 *  @param  processTable This is actually a return parameter.  This
 *         should be a pointer to an already allocated array of
 *         Process structure items.  We will fill in this structure
 *         and return the process information.
 *
 *  @returns  ProcessTable* The newly allocated and initialized ProcessTable
 *         structure.
 */
ProcessTable *  createProcessTable ( char *  processFilename )
{
  ifstream simprocessfile ( processFilename );
   ProcessTable *  processTable ;
   int  pid ;
  string processName ;
   int  arrivalTime ;
   int  serviceTime ;

   // If we can't open file, abort and let the user know problem
   if   ( ! simprocessfile . is_open ())
   {
    cout  <<   "Error: could not open process simulation file: "
          <<  processFilename  <<  endl ;
    exit ( 1 );
   }

   // Format of file is
   // ProcessName1 ArrivalTime1 ServiceTime1
   // ProcessName2 ArrivalTime2 ServiceTime2
   // ...
   // ProcessNameN ArrivalTimeN ServiceTimeN
   //
   // Where the name is any arbitray string identifier, and ArrivalTime
   // and ServiceTime are integer values
  pid  =   0 ;
  processTable  =   new ( ProcessTable );
   while   ( simprocessfile  >>  processName  >>  arrivalTime  >>  serviceTime )
   {
     // allocate a new process to hold information
     Process *  process  =   new ( Process );
    processTable -> process [ pid ]   =  process ;

     // load information into process read from simulation file
    process -> processName  =  processName ;
    process -> arrivalTime  =  arrivalTime ;
    process -> serviceTime  =  serviceTime ;

     // initialize other process information for the simulaiton
    process -> sliceTime  =   0 ;
    process -> totalTime  =   0 ;
    process -> finishTime  =   0 ;
    process -> finished  =   false ;

    pid ++ ;
   }

   // Set the number of processes we need to simulate information in
   // the process table
  processTable -> numProcesses  =  pid ;

   return  processTable ;
}


/** Display process table
 * Convenience method, dump all of the information about the processes
 * in a process table to stdout.
 *
 *  @param  processTable The table, a pointer to type ProcessTable
 *           struct, with the information we are to display
 */
void  displayProcessTable ( ProcessTable *  processTable )
{
  cout  <<   "Process Table num = "   <<  processTable -> numProcesses  <<  endl ;
  cout  <<   "PID Name Arrv Srvc"   <<  endl ;
  cout  <<   "------------------"   <<  endl ;
   for   ( int  pid = 0 ;  pid  <  processTable -> numProcesses ;  pid ++ )
   {
     Process *  p  =  processTable -> process [ pid ];
    cout  <<  setw ( 2 )   <<  right  <<  pid  <<   ") " ;
    cout  <<  setw ( 4 )   <<  left  <<  p -> processName  <<   " " ;
    cout  <<  setw ( 4 )   <<  right  <<  p -> arrivalTime  <<   " " ;
    cout  <<  setw ( 4 )   <<  right  <<  p -> serviceTime  <<   " " ;
    cout  <<  endl ;
   }
}


/** Round robin scheduler simulator
 * The main routine for performing the round robin preemptive
 * scheduler simulator.  We expect the time quantum to already be
 * specified and given to us as the first parameter.  The file name
 * with the process arrival and service time information is given as
 * the second parameter.  We simulate preemptive round robin
 * scheduling of all of the processes until there are no longer any
 * processes left in the system (all processes have exceeded their
 * service time and have exited).
 *
 *  @param  processTable A pointer to a ProcessTable structure holding
 *      information about the processes, arrival times and durations
 *      that we are simulating execution of.
 *  @param  quantum An integer value holding the time slice quantum we
 *      are using for this simulation.
 */
void  roundRobinScheduler ( ProcessTable *  processTable ,   int  quantum )
{
   // Implement the round robin scheduler here
  cout  <<   "<roundRobinScheduler> entered, quantum: "   <<  quantum  <<  endl ;
}


/** shortest remaining time simulator
 * The main routine for performing the shortest remaining time
 * preemptive scheduler simulator.  The file name with the process
 * arrival and service time information is given as the first
 * parameter.  We simulate preemptive shortest remaining time
 * scheduling of all of the processes until there are no longer any
 * processes left in the system (all processes have exceeded their
 * service time and have exited).
 *
 *  @param  processTable A pointer to a ProcessTable structure holding
 *      information about the processes, arrival times and durations
 *      that we are simulating execution of.
 */
void  shortestRemainingTime ( ProcessTable *  processTable )
{
   // Implement the shortest remaining time policy here
  cout  <<   "<shortestRemainingTime> entered"   <<  endl ;
}


/** Main entry point of round robin scheduler
 * The main entry point of the round robin scheduler simulator.  The main funciton
 * checks the command line arguments, and calls the simulation function if correct
 * arguments were supplied.   We expect two command line arguments, which are the
 * time slice quantum value we are to use for this preemptive scheduler simulation,
 * and the name of the simulation file holding the process arrival and service
 * time information.
 *
 *  @param  argc The argument count
 *  @param  argv The command line argument values. We expect argv[1] to be the
 *              time slice quantum parameter (int format) and argv[2] to be the
 *              name of the process simulation file (charcter string)
 */
int  main ( int  argc ,   char **  argv )
{
  string policy ;
   ProcessTable *  processTable ;
   int  quantum  =   0 ;

   // If not all parameters provides, abort and let user know of problem
   if   ( argc  <   3   ||  argc  >   4 )
   {
    cout  <<   "Error: expecting process simulation file and scheduling policy as command line parameters"
      <<  endl ;
    cout  <<   "Usage: "   <<  argv [ 0 ]   <<   " process-file.sim [rr|srt] [quantum]"   <<  endl ;
    exit ( 1 );
   }

   // load process table and parse command line arguments
  processTable  =  createProcessTable ( argv [ 1 ]);
   // just to confirm that process table loaded correctly.  You should
   // comment out or remove this as it is not asked for as part of the
   // output for the assignment simulation
  displayProcessTable ( processTable );

   // determine policy to simulate
  policy . assign ( argv [ 2 ]);

   // perform simulation of indicated scheduling policy
   if   ( policy  ==   "rr" )
   {
     if   ( argc  !=   4 )
     {
      cout  <<   "Error: time quantum must be provided for round robin `rr` scheduling policy"   <<  endl ;
      exit ( 1 );
     }
    quantum  =  atoi ( argv [ 3 ]);
     if   (   ( quantum  <=   0 )   ||   ( quantum  >   1000 )   )
     {
      cout  <<   "Error: received bad time slice quantum parameter: "   <<  argv [ 1 ]   <<  endl ;
      cout  <<   "       valid values are integers in range from 1 to 1000"   <<  endl ;
      exit ( 1 );
     }

    roundRobinScheduler ( processTable ,  quantum );
   }
   else   if   ( policy  ==   "srt" )
   {
    shortestRemainingTime ( processTable );
   }
   else
   {
    cout  <<   "Error: unknown process scheduling policy: "   <<  policy  <<  endl ;
   }
}

prog-05.pdf

Programming Assignment #5

CSci 430, Spring 2019

Dates:

Assigned: Monday April 15, 2019 Due: Wednesday May 1, 2019 (before Midnight)

Objectives:

� Understand short-term process scheduling.

� Work with data structures to implement a round-robin scheduler.

� Look at e�ects of di�erent time slice quantum sizes on the round-robin scheduling algorithm.

� Use C/C++ to implement vector and matrix data structures, get practice in creating and using such data structures in C/C++.

Description:

Our textbooks chapter 9 discusses several possible short-term process scheduling policies. In this programming assignment exercise we will implement two of the preemptive policies, the simple shortest remaining time policy (SRT) and the round-robin scheduler with preemptive time slicing. Your program will be given a simple input �le, indicating the process name, its arrival time and its total service time, the same as the process scheduling examples from our textbook in Table 9.4 and Figure 9.5. You will simulate the execution of the required schedulers. As in previous assignments, you program will need to work non-interactively and be callable from the command line. The program will be provided with the �le name of a �le with process information, in the format discussed below. Your program will also be given the time slicing quantum parameter it is to use for the simulation, if round-robin scheduling is selected. Your program will need to output the results of running the set of simulated processes using the selected scheduling policy with the indicated time slice for the round-robin scheduler. Your program will have to output its results exactly as shown below in the required output format. Your program will also need to calculate some summary statistics for the simulated processes, including the turnaround time and Tr/Ts ratio for each process, and the mean Tr and Tr/Ts values for the given simulation.

Process simulation �le formats

The �les with the information about the processes to be simulated are fairly simple, and have the same information that our textbook uses to illustrate the process scheduling examples. Each simulation �le contains multiple rows of data, where each row consists of the process name, its arrival time, and its service time. Here is an example:

1

A 0 3

B 2 6

C 4 4

D 6 5

E 8 2

This �le is named process-01.sim in the zip archive of �les I have given you to get started on this assignment. This is also the same set of processes and start/service times used for all of the examples in table 9.4 and �gure 9.5.

Running Simulations

As with previous assignments you are required to support using your simulation from the command line. Your program will take the name of the �le containing the process information �rst. The next parameter will be either 'rr' to perform round-robin scheduling, or 'srt' if shortest remaining time policy is to be simulated. Finally, a 3rd parameter will be supplied for the round-robin scheduler, the time slice quantum to use. An example of running your �nished program should look like this:

$ ./p3 process-01.sim rr 4

A A A B B B B C C C C D D D D B B E E D

Name Fnsh T_r T_r/T_s

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

A 3 3 1

B 17 15 2.5

C 11 7 1.75

D 20 14 2.8

E 19 11 5.5

Here we are running the simulation using the set of process information given in the previous section and with a time slice quantum of 4.

Required Output

As shown above, your program must generate 2 bits of output. First of all, while running the simulation of the selected scheduling policy, you should display the process names in the order they are run. In the previous example, the sequence of scheduled/run processes was:

A A A B B B B C C C C D D D D B B E E D

This indicates that process A ran �rst (times 0, 1 and 2), followed by B running 4 times (times 3 to 7), etc. You are required to output the sequence of process runs as the �rst line of output, with a single space in between each process name as shown.

After the processes have run, you need to calculate and display the statistics for the processes that you just simulated. In our previous example, the statistics for our round-robin simulation with a time quantum of 4 time slices were:

Name Fnsh T_r T_r/T_s

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

A 3 3 1

B 17 15 2.5

C 11 7 1.75

2

D 20 14 2.8

E 19 11 5.5

For each process, you need to output the time when it �nished, the turnaround time (Tr) and the ratio of the turnaround time to the service time (Tr/Ts).

I have provided a zip �le with a �le named p3-start.cpp as a template to get you started. In addition, I have provided you with two process simulation �les, named process-01.sim and process-02.sim, with 2 sets of process information you can simulate. There are several examples of correct results generated for the two sets of inputs, named things like process-01-q1.res, process-01-q4.res, process-01-srt.res, etc. These are the correct results you should get for running your simulation with round-robin scheduling for various time quantums or for shortest remaining time scheduling.

3

processtable-01.sim

A 0 3 B 2 6 C 4 4 D 6 5 E 8 2

processtable-02.sim

A 0 4 B 1 7 C 4 5 D 4 5 E 7 2 F 8 5 G 10 1 H 10 4 I 12 6

processtable-03.sim

A 0 3 B 2 4 C 3 5 D 3 8 E 3 2 F 5 6 G 7 9 H 7 4 I 8 3 J 8 5 K 8 4 L 10 6

Makefile

all: p5sol p5: p5-start.cpp g++ -g $< -o $@ p5sol: p5-solution.cpp g++ -g $< -o p5 debug: p5-solution.cpp g++ -DDEBUG_BUILD=1 -g $< -o p5 p5test: ./p5 processtable-01.sim rr 1 > sim-01-rr-1.tst @diff -s -q sim-01-rr-1.tst sim-01-rr-1.res ./p5 processtable-01.sim rr 4 > sim-01-rr-4.tst @diff -s -q sim-01-rr-4.tst sim-01-rr-4.res ./p5 processtable-01.sim srt > sim-01-srt.tst @diff -s -q sim-01-srt.tst sim-01-srt.res ./p5 processtable-02.sim rr 1 > sim-02-rr-1.tst @diff -s -q sim-02-rr-1.tst sim-02-rr-1.res ./p5 processtable-02.sim rr 4 > sim-02-rr-4.tst @diff -s -q sim-02-rr-4.tst sim-02-rr-4.res ./p5 processtable-02.sim srt > sim-02-srt.tst @diff -s -q sim-02-srt.tst sim-02-srt.res ./p5 processtable-03.sim rr 1 > sim-03-rr-1.tst @diff -s -q sim-03-rr-1.tst sim-03-rr-1.res ./p5 processtable-03.sim rr 5 > sim-03-rr-5.tst @diff -s -q sim-03-rr-5.tst sim-03-rr-5.res ./p5 processtable-03.sim srt > sim-03-srt.tst @diff -s -q sim-03-srt.tst sim-03-srt.res @rm sim-01-rr-1.tst sim-01-rr-4.tst sim-01-srt.tst sim-02-rr-1.tst sim-02-rr-4.tst sim-02-srt.tst sim-03-rr-1.tst sim-03-rr-5.tst sim-03-srt.tst p5zip: zip ../prog-05.zip p5-start.cpp prog-05.pdf processtable-01.sim processtable-02.sim processtable-03.sim Makefile *.res p5solzip: zip ../prog-05-sol.zip p5-solution.cpp processtable-*.sim sim-*.res clean: rm -f p5 sim-*.tst core* *~

sim-01-rr-1.res

sim-01-rr-4.res

sim-01-srt.res

sim-02-rr-1.res

sim-02-rr-4.res

sim-02-srt.res

sim-03-rr-1.res

sim-03-rr-5.res

sim-03-srt.res

Programming Assignment #5

CSci 430, Spring 2019

Dates:

Assigned: Monday April 15, 2019 Due: Wednesday May 1, 2019 (before Midnight)

Objectives:

� Understand short-term process scheduling.

� Work with data structures to implement a round-robin scheduler.

� Look at e�ects of di�erent time slice quantum sizes on the round-robin scheduling algorithm.

� Use C/C++ to implement vector and matrix data structures, get practice in creating and using such data structures in C/C++.

Description:

Our textbooks chapter 9 discusses several possible short-term process scheduling policies. In this programming assignment exercise we will implement two of the preemptive policies, the simple shortest remaining time policy (SRT) and the round-robin scheduler with preemptive time slicing. Your program will be given a simple input �le, indicating the process name, its arrival time and its total service time, the same as the process scheduling examples from our textbook in Table 9.4 and Figure 9.5. You will simulate the execution of the required schedulers. As in previous assignments, you program will need to work non-interactively and be callable from the command line. The program will be provided with the �le name of a �le with process information, in the format discussed below. Your program will also be given the time slicing quantum parameter it is to use for the simulation, if round-robin scheduling is selected. Your program will need to output the results of running the set of simulated processes using the selected scheduling policy with the indicated time slice for the round-robin scheduler. Your program will have to output its results exactly as shown below in the required output format. Your program will also need to calculate some summary statistics for the simulated processes, including the turnaround time and Tr/Ts ratio for each process, and the mean Tr and Tr/Ts values for the given simulation.

Process simulation �le formats

The �les with the information about the processes to be simulated are fairly simple, and have the same information that our textbook uses to illustrate the process scheduling examples. Each simulation �le contains multiple rows of data, where each row consists of the process name, its arrival time, and its service time. Here is an example:

1

A 0 3

B 2 6

C 4 4

D 6 5

E 8 2

This �le is named process-01.sim in the zip archive of �les I have given you to get started on this assignment. This is also the same set of processes and start/service times used for all of the examples in table 9.4 and �gure 9.5.

Running Simulations

As with previous assignments you are required to support using your simulation from the command line. Your program will take the name of the �le containing the process information �rst. The next parameter will be either 'rr' to perform round-robin scheduling, or 'srt' if shortest remaining time policy is to be simulated. Finally, a 3rd parameter will be supplied for the round-robin scheduler, the time slice quantum to use. An example of running your �nished program should look like this:

$ ./p3 process-01.sim rr 4

A A A B B B B C C C C D D D D B B E E D

Name Fnsh T_r T_r/T_s

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

A 3 3 1

B 17 15 2.5

C 11 7 1.75

D 20 14 2.8

E 19 11 5.5

Here we are running the simulation using the set of process information given in the previous section and with a time slice quantum of 4.

Required Output

As shown above, your program must generate 2 bits of output. First of all, while running the simulation of the selected scheduling policy, you should display the process names in the order they are run. In the previous example, the sequence of scheduled/run processes was:

A A A B B B B C C C C D D D D B B E E D

This indicates that process A ran �rst (times 0, 1 and 2), followed by B running 4 times (times 3 to 7), etc. You are required to output the sequence of process runs as the �rst line of output, with a single space in between each process name as shown.

After the processes have run, you need to calculate and display the statistics for the processes that you just simulated. In our previous example, the statistics for our round-robin simulation with a time quantum of 4 time slices were:

Name Fnsh T_r T_r/T_s

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

A 3 3 1

B 17 15 2.5

C 11 7 1.75

2

D 20 14 2.8

E 19 11 5.5

For each process, you need to output the time when it �nished, the turnaround time (Tr) and the ratio of the turnaround time to the service time (Tr/Ts).

I have provided a zip �le with a �le named p3-start.cpp as a template to get you started. In addition, I have provided you with two process simulation �les, named process-01.sim and process-02.sim, with 2 sets of process information you can simulate. There are several examples of correct results generated for the two sets of inputs, named things like process-01-q1.res, process-01-q4.res, process-01-srt.res, etc. These are the correct results you should get for running your simulation with round-robin scheduling for various time quantums or for shortest remaining time scheduling.

3

Previous Next

Get help from top-rated tutors in any subject.

Efficiently complete your homework and academic assignments by getting help from the experts at homeworkarchive.com