CPU Scheduling Simulation

This is an individual assignment. You may collaborate with your peers in sharing design ideas, but you may not share code.

One of the most important jobs of a modern operating system is managing the various processes in the system. The goal of this project is to enhance your understanding of process management and your programming skills by implementing two scheduling policies:

  1. First Come First Serverd (FCFS)
  2. Round Robin (RR)
The input to your program is a text file containing information about the system processes. Each line in the text file has three pieces of information:
  1. A string (label) that uniquely identifies a process
  2. The arrival time for the process
  3. The CPU burst time for the process
For example, the line
   P2 7 11
states that the process P2 arrives at time 7 and requires 11 time units to run to completion. For simplicity, we assume assume that each process consists of a single CPU burst (no I/O bursts), and processes are listed in the input file in order of their arrival time. We further assume that an interrupted process gets placed at the back of the Ready queue, and a newly arrived process gets placed at the back of the Ready queue as well.

Sample Execution

Assume that you have created a file process.txt with the following data:
   P0 0 3
   P1 1 6
   P2 5 4
   P3 7 3
If you invoke your scheduler (executable cpu-scheduler) using the command
    cpu-scheduler process.txt
then your program should have a behavior similar to the following:
            CPU Scheduling Simulation
Select the scheduling algorithm [1,2 or 3]:
1. First Come First Served (FCFS)
2. Round Robin (RR)
3. Exit

       First Come First Served Scheduling

[0-3]   P0 running 
[3-9]   P1 running 
[9-13]  P2 running 
[13-16] P3 running 

Turnaround times: P0[3], P1[8], P2[8], P3[9]
Wait times:       P0[0], P1[2], P2[4], P3[6]

Average turnaround time: 7.00
Average wait time: 3.00

Hit any key to continue ... 

            CPU Scheduling Simulation
Select the scheduling algorithm[1,2 or 3]:
1. First Come First Served (FCFS)
2. Round Robin (RR)
3. Exit

Enter the time quantum: 2

             Round Robin Scheduling

[0-2]   P0 running
[2-4]   P1 running
[4-5]   P0 running
[5-7]   P1 running
[7-9]   P2 running
[9-11]  P3 running
[11-13] P1 running
[13-15] P2 running
[15-16] P3 running

Turnaround times: P0[5], P1[12], P2[10], P3[9]
Wait times:       P0[2], P1[6],  P2[6],  P3[6]

Average turnaround time: 9.00
Average wait time: 5.00

Project Specifications

In your csc1600 directory, create a new directory called scheduling and a C program file called cpu-scheduler.c. Use incremental programming techniques to develop the code for your scheduler in consecutive stages:
  1. Write a function
        void ReadProcessTable(char * filename); 
    that reads the input file into a global data structure. This structure may be an array of processes, with each entry of the following type:
        typedef struct {
             char * name;
             int arrival;
             int cpuburst;
             int turnaround;
             int wait;
        } Process;
        Process processtable[MAX_PROCESS]; 
    Note that you will need to allocate memory dynamically for name, since no static memory has been allocated by the definition above. Use fopen, fscanf and fclose to handle the input file.

  2. Once your code for the first step compiles and runs without errors, write a function
        void PrintProcessTable();
    that simply outputs the data stored in the global processtable structure filled in by the ReadProcessTable call. Verify that the output is identical to the data stored in the input file.

  3. Next implement a function
        void FCFS();
    You will need to keep track of the current time by means of a variable (global or local)
        int current_time;
    Your FCFS function should initialize this variable to zero and advance it to the time of the next event in each iteration through the process list. This function should only update the processtable data structure. To print out the statistics on the turnaround times and wait times, write another function called
        void PrintStatistics();
    This function should work independent on the scheduling algorithm used (FCFS or RR).

  4. Once you have FCFS working properly, move on to implementing the Round Robin scheduling method
        void RR(int quantum);
    This function must iterate through the list of processes multiple times. In each round (loop iteration), it schedules all active processes to run quantum time units or less, depending on the cpu burst time left for each process. To keep track of the remaining cpu burst for each process, you could use a local copy of the cpu bursts
        int cpuburstcopy[MAX_PROCESS];
    and update it in each round. The local copy is necessary so that the global structure processtable remains unaltered (and could be used by FCFS, for instance). In addition to this structure, you might also need to maintain an index in the process table, say first, that marks the entry for the first process with positive (non-zero) remaining cpu burst time.

Submission Instructions

In your csc1600/scheduling directory create a text file named readme (not readme.txt, or README, or Readme, etc.) that contains:
  1. Your name and assignment number.
  2. A description of whatever help (if any) you received from others outside of class.
  3. An indication of how much time you spent doing the assignment outside of class.
  4. Your assessment of the assignment: Did it help you to learn? What did it help you to learn? Do you have any suggestions for improvement? Etc.
  5. Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.
Descriptions of your code should not be in the readme file. Instead they should be integrated into your code as comments. Your readme file should be a plain text file. Do not create your readme file using Microsoft Word or any other word processor.

Turn in a printout copy of the readme and cpu-scheduler.c files, and a sample output. You will need to copy and paste your code into a text or a Word document in Windows, since you cannot print directly from Unix.

Leave the source code for all exercises in your directory csc1600/scheduling. Do not make any changes to these files after the due date for this assignment.


35     Total points possible
10 Program compiles successfully and runs
10 FCFS produces the correct output
10 RR produces the correct output
  5 Your readme file is present and includes all required components

Have fun!