Scheduling

Rose Liu - 804035209

Rand Lee - 204015860

Scheduling is surprisingly hard. Just ask John Deasy, the LA school district superintendent who was fired for implementing faulty scheduling system. The purpose of scheduling is to properly hand out scare resources. In the case of Operating Systems, this is generally CPU time

Consider the following scheduling problem:

We have P threads to run

We have C CPUs

If P<=C. then we have no problem. Each process can run on it's own CPU. However, this is not commonly the case. The more common case is when P > C. This is when scheduling get tricky:

We can think of scheduling as having 2 categories, represented by the following two questions:

1. What policies to use?

- This category is very abstract and high level.

- Policy answers the question, "What's the general rule for how CPUs are used?"

2. What mechanisms to use?

- One example of mechanisms is attempting to figure out how much CPU time can used before process X gives CPU to process Y

- Mechanisms are 0S specific and very low level. This category handles the nitty gritty details of scheduling.

Let us consider the case of scheduling when we have 1 CPU. C = 1:

One method we can implement is Cooperative Scheduling. This is the simplest method

-With cooperative scheduling, we assume that all threads and processes are polite. This means that every now and then they will communicate with the scheduler and check if another process is waiting to run

- e.g. In Linus's version of cooperative scheduling, every system call consults the scheduler (It does not always have to be the case that system calls specifically consult the scheduler. This protocol may be implemented with other processes as well.)

- In Linux, each system call calls the yield command, yield(). This tells the scheduler that now is a good time to schedule another thread or process.

Let's review this example in the context of process, P1:

- P1 - read(…);

- When the system call read is called, the process registers are pushed on to kernel stack

- The machine then copies the P1 register values into its process table

- After the current values of this process, P1 are stored. The process "yields" by allowing another process to run. When it yields and the CPU eventually gets back to P1, it can continue computation where it left off, with the values all still saved in the process table.

One problem with this method of cooperative scheduling is that if a system call is never made, the current process will never yield. O there processes will not be called and will not have a chance to run.

- Cooperative scheduling does not allow for this condition. Every recursion/loop generates the yield() command for each of its iterations. The original Mac OS used this form of cooperative scheduling .

In the case described above, with 1 CPU, we can see that cooperative scheduling makes race conditions less likely. While the code is out of whack (in the midst of computation), the code makes no system calls and does not call yield(). The program does system calls before or after these code blocks. This way, no races are generated in this specific area of the code.

Waiting

Waiting is an important area of consideration in scheduling. Consider the following system call:

read(fd, buf, sizeof but)

-fd is a pipe. However, what if kernel's pipe buffer is empty? We want kernel to wait until pipe gets data

There are three ways for the kernel to wait:

1. Busy Waiting - This tells the kernel to keep checking until there is data in the pipe. The code for this looks like:

while(p->bytes == 0)
continue;

The PRO to busy waiting is that it is simple. However, this method times up the CPU. If there is only 1 CPU and the system is using cooperative scheduling, this method will loop forever, as no other process can populate the pipe with data.

2. Polling - This method combines busy waiting and yielding. The code for this method looks like:

while(p->bytes == 0)
yield();

Consider the case where there are 10,000 processes, 9,999 writes to a pipe, and 1 reader. This highlights an essential problem with polling. A huge overhead occurs when we unnecessarily yield to processes (i.e. w2-w9,999). Ultimately, when you poll, you spend most of your CPU time polling.

r - read a byte {computation}
yields;
w1 - writes
yields;
w2
.
. } These processes wake up, see that the pipe is full and all yield. (This overhead is unnecessary)

3. Blocking - In this method, the kernel keeps track of which processes are runnable and the scheduler only looks at runnable processes. We can avoid polling.busy waiting by implementing this process. It is almost as simple and has no hangs. It's pro is that it is faster. However, it is trickier in that we must be VERY CAREFUL and make sure that we correctly make runnable and non runnable processes.

The previous descriptions have all been descriptions of scheduling mechanisms. Let's consider policies now.

In an operating system, the scheduler must give the right priority to each process. There are certain scheduling metrics that we can measure to calculate this priority.

Let us first consider the case of assembly line scheduling. We can draw comparisons to Ford's assembly line process.

1)The first step of the assembly line is order arrival. This is when the Ford factory receives an order for a batch of model T's. In machines, this step is the arrival of computations to do.

- i.e. execvp("sort",…)

The factory/machine must then wait. We can not immediately build model T's, as the factory may be busy building model A's. We must reset the assembly line in preparation of assembling a different model, just as we must reset the kernel's registers with the correct values for the computation.

2. The second step of the assembly line is the start of production . The car assembly, or computation begins.

- i.e. man(….) runs

3. The third milestone of the assembly line is when the first outputs start to come out. The time that elapses between step 1, above and this step is called the response time. For batch applications, response time is not a big deal. However, for interactive apps, response time matters. Consider the case of the keyboard. Keystrokes must output immediately when a key is pressed. We must immediately get something to display or happen to make our customers happy.

4. The final milestone is when the computation, or order assemblage, completes. The time that elapses between step 1, above and this step is called the turnaround time. The time that elapses between step 2, above and this step is called the execution time.

Scheduler Metrics

To measure OS scheduler efficiency, we can measure the wait, turn around, and response times. We examine the average of these times for meaningful metrics. To calculate these times, we run a mix of processes, comparable to the batch that you'd use in real life.

The variance of the wait, turn around, and response time is also meaningful. Think again about keystrokes. we prefer higher average times with lower variances. Users have expectations. and we must ensure predictability

Another important metric is fairness. Fairness is a property where a runnable process always eventually will run, no matter what. We want to ensure that our scheduling policy is fair. The opposite of fairness is starvation - when a runnable process never runs. We want to avoid starvation. An unfair scheduler will have an average response time of infinity in its worst case if the process never runs.

Sometimes, we can assign metric to fairness. However, with the simple system we have described so far, fairness is not a value, but a boolean. Our scheduler is either fair or not fair.

Utilization is another important metric for evaluating scheduling efficiency. It describes what percent of the factory capacity is being used. Utilization does not count waiting or polling CPU time or the overhead from system calls. It only takes into consideration useful work: work done by processes. Ideally we want to utilize 100% of the CPUs. However in practice, we can not achieve this, but we try to get as close as possible.

Simple Scheduler Example

First in First Out - FIFO Scheduling Policy

Over time, this is how the processes are executed.

The "_" character refers to a GAP. This is the context switch time. (0.1 sec)

FIFO is a fair policy. No method will ever starve. It is simple, but long processes can hog the CPU. This is called the Convoy Effect. FIFO results in higher average times and higher variances.

Shortest Job First - SSJ Scheduling Policy.

This policy assumes we know the process runtime for every process. Given this assumption, it is only feasible in production environments for repeated operations.

Over time, this is how the processes are executed:

SJU is the better scheduling algorithm for this test case. It has a better average wait time. However, starvation is possible here if there is a long job in the queue and short jobs keep coming in.

Pop Quiz: Question: When is FIFO better than SJU?
Answer: Never! if there is no preemption and runtime is known in advance, SJU will always be the better policy.

Priority Scheduler

Priorities can be assigned to policies. In operating systems, the priority level decreases as priority number increases. Priority 1 is a high priority. Priority 10 is a low priority. Linux calls priority niceness, to make this inverse relationship more intuitive. Processes that are meaner (less nice) run first. We always run the process with the highest priority or that is least nice first.

Niceness can range from -19 to 19 and the default value is 0. The follow is example code to change the niceness of a process

$nice make gcc

- "nice" sets priority. adds 10 to niceness

- Adding the flag, "-n 20" will add 20 to the process's original niceness
- Adding the flag, "-n -20" will subtract 20 to the process's original niceness. Only the root user can subtract niceness and make a process meaner. This is a safety measure.

FIFO is a form of priority scheduling where priority is the negative of the arrival time. priority = -arrivaltime.

SJF is a form of priority scheduling where priority is the negative of the run time. priority = -runtime.

Priority is tricky to get right, and can be calculated as any of the following (or a combination of the following):

-niceness
-arrival time
-CPU time limit

Are these methods of calculating priority fair? Yes! If the arrival time is big enough that it ultimately wins out in terms of priority.

External priorities are priorities that are set by the user. For example, niceness, as we've seen above can be set by the user.

Internal priorities are priorities that are set by the system OS. For example whether or not a process is in RAM or in Disk. Processes in RAM are of higher priority and processes in disk are of lower priority, generally.

Real time scheduling

Hard Real Time - This type of scheduling employs HARD DEADLINES. Think about a nuclear power plant. Accuracies matter. Processes can not miss a deadline. Variance is bad, and predictability is more important than performance.

e.g. One way to limit the variance is to disable CPU cache. Because we test our program with the cache off, we should run it with cache off, to ensure consistent testing/production behavior. Safety comes first.

With hard real time scheduling, polling is common and interrupts and signals are rare.

Soft Real Time - This type of scheduling employs soft deadlines. Some deadlines can be missed as long as most of the deadlines are met. Think about a video player. If a frame is a missed, the user will forget about it when the next frame appears. With soft real time scheduling, performance matters. There are lots of algorithms that can be employed in this case.

- i.e. The earliest deadline first policy. For this policy, what happens if a deadline passes? We must drop the process in order to avoid hanging or starvation.