CS 451 Operating Systems Multilevel Feedback Scheduler Using Real Timer
In this assignment, you will be writing a scheduler called mlfScheduler to schedule processes to run, using multilevel feedback scheduling algorithm. There are 2 queues in this multilevel feedback system. Every process enters the system in first queue and gets equal amount of time (called time slice given in seconds) on the CPU. If it does not finish its code when scheduled off the first queue, then it moves to the second queue which is run using FCFS schedule. That is, the process is run until it completely finishes its burst when it is scheduled from the second queue. The CPU will first run all processes in the first queue and then run all processes in the second queue.
It is assumed that processes given in the input file have arrived in that order. They are moved to first queue for processing. If a process does not finish execution when processed from the first queue, it is then placed in the second queue for FCFS processing. The scheduler keeps time and schedules processes in accordance with the schedule and when a process finishes, it leaves the system. A process may leave the system from the first queue if its burst time is less than time slice allocated to first queue. Otherwise it will leave after being processed from second queue.
The name of the input file containing all the PIDS and corresponding burst times and the time slice for the first queue are given in the command line.
For example when the program is run with the command
./mlfScheduler input.txt 10
The time slice for first queue is 10.
The mlfScheduler creates one child process for each process in the file, and schedules according to the multilevel feedback queuing algorithm. It ensures that, at every instant of time, there is only one process running and the running process is the one chosen by scheduling algorithm. A process is taken off the CPU either when the running process finishes its time slice in the first queue or the process finishes its burst in the first queue before time slice expires or finishes its burst in the second queue.
The input file to the scheduler consists of m (m <=100) lines, each line contains a process id (0 to m-1), and, the CPU burst of each process, separated by one or more spaces. The CPU burst time is given in seconds and time slice is also given in seconds. The entries in each line may be separated by spaces or tabs and any number of them. Your program should handle this with no errors. No other type of errors is expected in the input file. There will be a header line in the input file which is not processed. Some process id’s may be missing due to
those processes having completed already. The process IDs will be in the order of increasing values.
For example, input.txt may contain the following and time slice = 10 (time slice is provided in the command line)
Process ID Burst
0 18
4 4
6 12
….
The scheduler keeps time to determine which process needs to be scheduled next on the CPU. When another process needs to be scheduled, due to time slice expiration of the running process in the first queue, the running process is suspended and the new process is run. When it is time for the suspended process to run, it is resumed and it is run. When a process finishes its entire burst, the scheduler terminates that process.
Thus, the scheduler switches processes on the CPU by suspending the one process, and resuming another process. The suspensions and resumptions are done by sending signals to the corresponding child processes
The scheduler keeps track of how long the child has been running by using an interval timer, as described in detail, later in this document. The timer is set to go off every 1 second amount of time so the scheduler can do its scheduling.
For simplicity, each child process executes the same code. It will start with a random10 digit number, say 1234567890, and simply find the next prime number higher than the starting number. The primality checking algorithm we use is a trivial one, in which number n is decided to be prime, if it is not divisible by any number between 2 to n. This algorithm is chosen so that CPU is kept busy during the burst time of the process. Keeping the starting number large will keep the CPU busy. Note that you have to use long unsigned int as the type for the variable storing the number being checked for primality.
Each child process should print to standard out, first time when it is started, when (and if) it is suspended, and when it is completed. When a child process first gets the CPU, it should print the first number that it is checking to verify primality. When a child process is suspended, it should print the largest number that it determined to be prime. When the process finally finishes its burst it should print the largest number it found to be prime. No intermediate prime numbers should be printed.
The output from your scheduler should include its scheduling activities: A line when it schedules a process for the first time, each time the scheduler suspends a process or resumes a process, and each time it terminates a process.
SAMPLE RUN
Process Burst
0 18
3 4
6 12
%./mlfScheduler input.txt 10
Scheduler: Time Now: 0 second.
Scheduling to Process 0 (PID 1314) for the time slice of 10 seconds.
(When a process scheduled for the first time, it prints the following)
Process 0: my PID is 1314: I just got started. I am starting with the
number 233343434 to find the next prime number.
Scheduler: Time Now: 10 seconds.
Suspending Process 0 and moving it to FCFS queue and scheduling
Process 3 (Pid 1315) for the time slice of 4 seconds.
(When a process is suspended… it prints the following)
Process 0: my PID is 1314: I am about to be suspended… Highest prime number I found is 5754853343.
(When a process scheduled for the first time, it prints the following)
Process 3: my PID is 1315: I just got started. I am starting with the number 9848288302 to find the next prime number.
Scheduler: Time Now: 14 seconds.
Terminating Process 3 and scheduling Process 6 (Pid 1316) for the time slice of 10 seconds.
(When a process completes, it prints the following)
Process 3: my PID is 1315: I am leaving the system. The largest prime
I found was 567293842908
(When a process scheduled for the first time, it prints the following)
Process 6: my PID is 1316: I just got started. I am starting with the
number 9848288302 to find the next prime number.
Scheduler: Time Now: 24 seconds.
Suspending Process 6 and moving it to FCFS queue scheduling.
NO MORE PROCESSES IN QUEUE 1. MOVING TO QUEUE 2. Resuming process 0
(NOTE: A resumed process does not print anything)
Scheduler: Time now is 32 seconds. Terminating Process 0 and resuming
Process 6.
(When a process completes, it prints the following)
Process 0: my PID is 1314: I am leaving the system. The largest prime
I found was 2974924709324
Scheduler: Time now is 34 seconds. Terminating process 6
(When a process completes, it prints the following)
Process 6: my PID is 1316: I am leaving the system. The largest prime
I found was 9239343948324
Scheduler: No more processes to run. Bye
All the prime numbers in the output above are made-up. It shows you the format and what is expected. For example, you could be printing a different prime number.
Attacking the Problem:
Prior Knowledge: Everyone should have prior experience of using fork, exec and signal handling. There is some help provided below on these topics. If you need additional help, please stop by and I will be happy to help.
Suspending and Resuming Child Processes:
Your main (parent) program will suspend the child process that is currently running when the time slice expiration is indicated by the parent’s timer. The suspension is done by sending signal of SIGTSTP (not SIGSTP) to the child to suspend and SIGCONT to resume. Both of these signals can be handled in the child so that the child can do the printout when the signal is received. Note that sending SIGSTP will stop the child but this signal cannot have a handler. So, child will stop but will be unable to print when it receives the signal. The parent can use the
kill(pid, signal_num)
function call to send the signal to the child by providing it pid in the kill call.
Keeping track of time in the scheduler:
To keep track of running time of a child, the parent uses the real interval timer which measures
the real “wall clock time”. This is the timer that will be used by the scheduler to schedule,
suspend and resume processes. When the timer goes off it sends SIGALRM which can then handle the suspension and resumption of process as needed. The timer is set using code along these lines..
struct itimerval timer;
/* Install timer_handler as the signal handler for SIGALRM. */
/* The timer goes off 1 seconds after installation of the timer. timer.it_value.tv_sec = 1;
timer.it_value.tv_usec =0;
/* … and every 10 seconds after that. */ timer.it_interval.tv_sec = 1; timer.it_interval.tv_usec =0;
/* Start a real timer. It counts down whenever this process is executing. */
setitimer (ITIMER_REAL, &timer, NULL);
while (1) { }
…
For additional help, read the man page for setitimer
Signal Handling:
To handle signals that are send by timer, you need to set up signal handler. You need write a function, and set up signal handler so that the function runs whenever the specified signal is received.
It can be done as follows: If you need additional help, read man pages for sigaction, and
memset
struct sigaction sa;
/* Install timer_handler as the signal handler for SIGALRM. */
memset (&sa, 0, sizeof (sa));
sa.sa_handler = &timer_handler;
sigaction (SIGALRM, &sa, NULL);
Note that entire scheduler code for scheduling is done in the handler!
How to start a child process by the scheduler
After you fork the child, use one of the exec suite of calls to execute the child process in the child. Of course you should have prime.o file ready to execute, so you can use in inside exec. Send needed parameters to the child in exec call. This will help the child process to print this information. This will be in argv of the child.
How to stop a child process by the scheduler
When a child process has completed its burst (as calculated by the scheduler), send a signal
SIGTERM. The child prints an output (shown above) and exits the system.
How to write code for child processes.
In a separate file, say prime.c, you should write a main function as if it is an independent program.
It should print its first message saying that it has started (shown above), then stay in an infinite loop trying to find large prime number.
The child must contain signal handlers for the signals expected from the parent. (SIGTSTP, SIGCONT and SIGTERM).
The child should stay in a forever loop finding higher and higher primes and handling arriving signals
Notes:
1. Since there are multiple processes running on the CPU, and do not have a dedicated CPU, when the scheduler (main) processes schedules a child, the child may not run immediately. However, for the purposes of this assignment, we will assume that child process starts immediately after it is scheduled by the scheduler. So, when the parent process counts k real seconds, we assume that the child that is currently scheduled ran for k real seconds.
2. Global variable usage is permitted. You will need them. In Operating System class, global variable usage is common. Enjoy using them!
3. Always end every printf with “\n”. It completes the buffer and makes printout happen. Otherwise signals will forbid a printout from completion.
4. As you develop you will find issues where there are too many processes ‘hanging around’ the system. You may use “ps –aef” command to see which processes are running and kill undesired processes during debugging by using “kill <pid>” command
5. The child processes get killed in the end (alas!) so the scheduler need not issue waitpid.
Original Work
This assignment must be the original work of you. Unless you have explicit permission, you may not include code from any other source or have anyone else write code for you.
Use of unattributed code is considered plagiarism and will result in academic misconduct proceedings as described in the Syllabus.
