CSC 325 Operating Systems with an Emphasis on UNIX
Assignment 13

This assignment will explore the algorithms in a simulation environment. I recommend that this assignment be completed in a group.

Simulating the Linux Scheduler

Reading about scheduling in the text can be pretty boring, but scheduling is a core part of every operating system. So, I thought it would be interesting to learn about Lnux scheduling by writing a simulator program that simlulates scheduling.

As explained in your text, Linux uses a simple priority based scheduling algorithm to choose between the current processes in the system. As you know from your reading, there are two types of processes in Linux, normal user process and real time processes. Real time processes will always run before normal user processes and they may have either of two types of policy: round robin (RR) or first come first served (FCFS).

In particular, implement the following assumptions:

• You will need to implement two algorithms:
  A time-sharing credit-based algorithm for preemptive scheduling among processes, and
  a real-time non-preemptive priority-based algorithm that can be scheduled according to RR or FCFS.
• All processes will have a priority.
• Only processes running in user mode may be preempted. Kernel mode processes may not be preenpted even if a real-time process with a higher-priority is available to run. Linux uses a credit-based system for time-sharing. The task with the highest number of credits is selected to run. Everytime a timer interrupt occurs, the currently running process loses one credit, when it's credit reaches 0, it is suspended and another process is chosen. You will need to think about how to simulate the timer.
• If no runnable processes have any credits, Linux re-accredits every process in the system according to the following rule: credits = credits/2 + priority.
• Each process must have a scheduling class that defines which algorithm should apply to the process.

Your task is to write a program that simulates scheduling in Linux. This simulation can be used, among other things for seeing how effective the Linux scheduler is under a variety of conditions. Hence the simulation will simulate conditions that would be occurring in the actual operating system, but you need not write all the code to do all the actual context swaps. In addition, for similicity, you may assume a uniform distribution for all of the necessary probability distributions. While this assumption is not realistic, it makes the programming easier. You a fixed time slice of 200ms.

You may use any of the relevant C++ libraries, such as the queue and/or priority que libraries.

Input Specifications:

• Total length of simulation time to be input from the keyboard.
• Average frequency of jobs arriving per second to be input from keyboard. You may assume that all of these jobs will arrive at random times during your simulation.
• Specifications for time-shared user-mode jobs: These are preemptable. The following information must be input, but more may be included according to your simulation requirements. As in the text, for simplicity, we will assume each user mode process has a single CPU burst which is preceded and followed by I/O bursts. (Though this seems like an extreme simplification, it is really not an unreasonable way to simulate the actual situation when there are multiple CPU bursts, because one can imagine each real process being broken up into subprocesses in this way.)
• First IO-burst time average (in milliseconds)
• CPU-burst time average (in milliseconds)
• Last IO-burst time average (in milliseconds)
• priority (Because most user processes run in either regular priority mode or with a nice setting, for simplification sake, just use one of two randomly assigned values, of either 10 (the default priority) or 5 (lower priority). In actuality, the numeric value calculated for the priority in Linux is the opposite of what we normally think of as priority, but that is a complication that is not worth fussing about.
• Specifications for real-time kernel jobs These are not preemptable. Again, the following information must be input, but more may be included according to your simulation requirements. For simplicity, we will assume each kernel mode process has a single CPU burst which is followed by an I/O burst, and that each kernel mode process can either be scheduled RR or FCFS.
• CPU-burst time average (in milliseconds)
• IO-burst time average (in milliseconds)
• priority (A randomly assigned number between -19 and 20 inclusive) Again, in actuality, the numeric value calculated for the priority in Linux is the opposite of what we normally think of as priority, but that is a complication that is not worth fussing about here. So, let's decide to make the 20 be the highest priority and -19 the lowest priority.
• boolean: FCFS or RR scheduling

Output Specifications:

• List each process by a Process ID Number as it is given a CPU time, listing the properties of the process, including how much time the process gets before it is blocked.
• When each process has completed, list response time, turnaround time, and waiting time for the process.
• At the end of the simulation, list CPU utilization and throughput.

You must use good style: using good structure, a good header, appropriate declarations, meaningful variable names, preconditions, postconditions, comment lines, etc.

Submit your C++ code, yourlastnameA13scheduling.cpp.