CS 111 Scribe Notes: Lecture 7 Scheduling Algorithms (4/20/09)

by Achint Goel and Christopher Knight

(continued from last lecture)

Signals (in the operating system)

Introduction to UNIX Signals Programming

Pros

• A good way to centrally manage a tricky business (arguably applicable to any part of an operating system).
• Arguably faster than a pipe.
• Allows O.S. to manage processes by grabbing their attention, for example, power failure.
  

Cons

• Increases complexity.
• Makes processes trickier to write reliably because the application has to safely and reliably be able to handle a signal in between any two given instructions.
• Creates unreliability due to lack of consistency in internals.
• Signals break modularity because they allow processes to cross module barriers.

Alternatives to Signals

For example, lets examine the case of a power failure while a process is running. There will be a dedicated file located somewhere where the application can access (i.e. /dev/signal) that contains a single byte of information. This byte will indicate whether there is power to the system or not (i.e. 1 for power and 0 for no power). The applications will then have to read this byte to check for a power failure at set intervals (i.e. every 5 ms).

Pros

• This presents a simpler API because the only thing the application needs to do is open and read the file.
• More reliable because the application is in control the whole time, thus there are no surprises.
  

Cons

• Polling is very inefficient because the application must continuously read until there is a change of state.
• Complicates the application code because responsibility is placed on the application instead of the kernel.
  

It is possible to address the cons of this alternative method in two possible ways:

Blocking Read:

• Read from the file but instead of reading at every set interval, the read can block until a new signal arrives (the byte value changes from 1 for power to 0 for no power).
• The problem with this approach is that since the process is blocked while waiting for a change of power state, the application cannot execute any of its actual code.
  

Multithreading:

• To fix this, lets have a separate thread that is delegated to reading the file for a signal of power failure.
• Now the application can still get its work done because its main thread will no longer be blocked.
  

But how will the signal checking thread tell the main thread that there is a power failure without signals? This all leads to the need for signals and the ability to cross virtualization barriers.

(end of previous lecture)

Scheduling Overview

Scheduling Wiki

Scheduling exists in every aspect of life. It is the study of how to share limited resources across many users. In the world of computing, this used to be done manually. There would be many users seeking to run their applications on a single machine. They would have to hand their applications to the operator, who would then choose which program to run next.

Cons

• Operator can lose stuff.
• Program switch time can be too long because it is dependent on the operators ability to choose and physically mount the application.
• Operator can make poor decisions about what program to run next, i.e. he/she could be bribed.
• The program that he chooses to run could have a bug, i.e. an infinite loop.
  

Because of all these cons, we should automate!

A simple but automated method to scheduling is where each process decides which process to run next. This method is called cooperative scheduling and is often used in embedded applications.

• One way this method could work is that when a process is about to exit (i.e. exit() in user mode), it decides which process to run next from a run queue (i.e. managed FIFO, where the first process into the queue is the first process out of the queue).
• Another method that could be used to accomplish cooperative scheduling is using yield(), where the process decides which process to run next but doesn't exit. Instead it puts itself at the end of the run queue (if using FIFO). 

Most system calls have a yield feature built in so that other processes can run while the kernel handles the syscall. This greatly increases performance and CPU utilization.

• The catch to this method of scheduling is processes that are doing a lot of useful computation without using any system calls.  The timeline of such a program would begin with several system calls but then would extend for a very long time without any systems calls (i.e. three days in a heavy computation) before ending with some system calls.
• This process is a hog while doing its computation because of the long string of instructions without any system calls or yield statements.

To solve this problem, we would like to have the ability to insert yields at runtime. In Linux, this is called a timer interrupt. Every 10 ms, the hardware traps and the kernel takes control. This acts as if the application called yield(). This idea of forcing a process to yield is called preemptive scheduling. 

Cooperative vs. Preemptive

Cooperative Scheduling:

• Programs only give up the CPU when they want to give up the CPU, which reduces program complexity.  However, this can lead to infinite loops holding onto the processor forever.
• Apple used cooperative scheduling initially.
  

Preemptive Scheduling:

• A program has to be prepared to lose the processor between any two instructions. This increases program complexity.
• Because programs are all forced to yield eventually, programs that enter into infinite loops will no longer lock up their machines. However, they still remain in the queue and continue to be scheduled. So the infinite loop problem isn't solved, but preemptive scheduling helps.
  

Better Managing the Infinite Loop Problem:

• One method is by setting limits as to how long a process is allowed to run before it is killed off. This will stop all infinite loops but the tradeoff is that some legitimate processes that happen to have a long run time will inadvertently be killed off as well.  In UNIX, there is a signal for this type of situation called SIGXCPU. This is sent to a process when it surpasses the set time limit.
• Another method is through simple human intervention (i.e. manually killing of processes when they take too long).  This can be done using ^C, which sends the SIGINT signal or the kill command.  Kill alone can be caught and possibly ignored while kill -9 will always kill the process.
  

Scale of Scheduling

When scheduling is being discussed in the context of computer science, it can be viewed at one of many different layers.

• Big Picture: Admission policy that determines what application code is let into the queue to begin with.
• Middle Ground: The decision as to which program gets to be loaded into RAM.
• Short Term: Determining who will get to run on the CPU.

We are primarily concerned with the short term.  When examining algorithms at the short term level, they can, for the most part, be abstracted and reapplied at the other levels.  When comparing scheduling agorithms, it becomes necessary to determine the "better" choice.  Initially, there is no clear way to do this, thus some metrics must be defined.

Metrics for Schedulers:

• Wait Time: Amount of time from initial placement into the queue until it begins executing.
• Response Time: Amount of time from initial placement into the queue until the first output from the given program.
• Runtime: Time elapsed from program start time until program exits.
• Turnaround Time: Amount of time elapsed from initial placement into the queue until program completion.
• Context Switching Time: Amount of time that it takes for the machine to switch from one line of execution to another.
• Utilization: The percentage of time the CPU is doing real work.
• Throughput: The number of jobs per second (assuming equal length jobs).
• "Fairness": The need to avoid unbounded wait time.

When examining these metrics, its common to look for things such as the average wait time, the worst case response time, etc.

Scheduling Examples

(All units in seconds)

Example 1: First Come First Serve Scheduling

Assuming that it takes ε seconds in between jobs to switch to the next job, and if each letter corresponds to 1 second of that job running, then the job scheduling would look as the following:

• AAA ε BB ε CCCCCCC

The wait time for the following jobs to start is:

• Job A: 0
• Job B: 2 + ε 
• Job C: 3 + (2ε)
  

This means the average wait time for a job to start is (5/3) + ε .

Assuming the same conditions as above, the turnaround time for each of the following jobs is:

• Job A: 3 
• Job B: 4 + ε 
• Job C: 10 + (2ε) 
  

This means the average turnaround time for a job is (17/3) + ε.

The total time it takes to finish all the jobs is 12 + (2ε), and the cpu is utilized for 12 (3 for Job A, 2 for Job B, and 7 for Job C), so the utilization is 12/(12 + (2ε)) %

Example 2: First Come First Serve Scheduling

Assuming that it takes ε second in between jobs to switch to the next job, and if each letter corresponds to 1 second of that job running, than the job scheduling would look as the following:

• BB ε CCCCCCC ε AAA

The wait time for the following jobs to start is:

• Job A: 7 + (2ε)
• Job B: 0
• Job C: 1 + ε
  

This means the average wait time for a job to start is (8/3) + ε.

Assuming the same conditions as above, the turnaround time for each of the following jobs is:

• Job A: 10 + (2ε)
• Job B: 2
• Job C: 8 + ε
  

This means the average turnaround time for a job is (20/3) + ε.

Example 3: Shortest Job First

If we assume the same arrival times, run times, and assumptions as Ex. 2 for Jobs A, B, C, but change the scheduling to SJF (shortest job first), then the job scheduling would look as the following:

• BB ε AAA ε CCCCCCC

The wait time for the following jobs to start is:

• Job A: ε
• Job B: 0
• Job C: 4 +(2ε)

This means the average wait time for a job to start is (4/3) + ε and the average turnaround time for a job is (16/3) + ε.

Pros to SJF:

• Average wait time is minimized

Cons to SJF:

• A process that takes a longer time could starve if processes that take a shorter time to complete keep on continuously arriving

Preemption and Scheduling

We can break up each of the jobs into shorter time segment pieces (i.e. 10 ms pieces) and then sequentially schedule each piece of the job separately (i.e. Preemption + FCFS).

• This scheduling algorithm is referred to as round-robin scheduling.  The way this algorithm works is that each job gets a quantum of time (i.e. 10 ms), and is run for that quantum time, and then put at the end of the scheduling run queue.

For example, if we assume the quantum is 1 second, and we assume the same arrival time and run time as Ex. 2, and that it takes ε seconds in between jobs to switch to the next job, and if each letter corresponds to 1 second of that job running, than the job scheduling would look as the following:

• B ε C ε A ε B ε C ε A ε C ε A ε CCCC

The wait time for the following jobs to start is:

• Job A: 2ε
• Job B: 0
• Job C: ε
  

This means the average wait time for a job to start is ε seconds.  Although this average wait time is the best so far, the round robin approach increases the turnaround time for a job compared to FCFS or SJF.

The total time it takes to finish all the jobs is 12 + (8ε) seconds, and the cpu is utilized for 12 seconds (3 seconds for Job A, 2 seconds for Job B, and 7 seconds for Job C), which gives us a utilization value of 12/(12 + (8ε))%.

If you were to shrink the quantum for a job, then:

• The utilization would decrease.
• The turnaround time for a job would increase, since you would be switching jobs more often and spending less time for each piece of a job.
• The average wait time would decrease because the piece of the preceding job would take less time to finish.
  

In Linux, the typical quantum time for a job is around 10 ms.  This is primarily because human beings don't have sesitive enough perception to notice a time of this length.  This gives a "snappy" feel to the user interaction.