LECTURE 7 scribe notes: Jia-Yu Aw, Alexander Liming Yang
CS111 Scheduling and Processes

Scheduling

On any typical computer system, there will be more than one process running at once. The OS has to delegate CPU time and other system resources to each process. The usual goals of a personal computer OS is to be fair (letting all processes get their turn) while running as smoothly as possible. These issues will be discussed later.

This issue of delegation is called Scheduling, which can be broken into two main categories: (1) Mechanisms and (2) Policy.

Mechanisms

The mechanism is the way the scheduler operates. This is simple- it doesn't deal with the decisions behind why processes are scheduled the way they are. If there is an incoming or waiting process whose turn is to execute, the current running process would give up the system resources. Whether a machine has 8 cores or 1 core, the mechanism should delegate processes the same way.

It can do this with the abstract function yield():

int main (void) { int sum = 0; for (long int i = 0; i < 100000000; ++i) { sum ^ 11; // we don't want to yield every iteration - expensive if (i % 65536 == 0) yield(); } return sum & 0xff; }

What is yield(), really?

yield() would be where the running process does nothing, waiting idly until it's time for it to run again. It's not the same as sleep(), although sleep(0) is a good approximation to a yield(). To do nothing, we could have a no-op system call, and the OS would get the hint to give the CPU to a different thread.

In reality, yield() can be any system call, such as getpid(), because then control would be passed over to the kernel, and the kernel then can transfer control as it likes without the current running process' knowing.

Methods

There are three ways to do use yield(): (1) Polling; (2) Busy waiting; (3) Blocking. We want the method that utilizes CPU time the most optimally.

(1) Polling while(!ready()) yield();
(2) Busy waiting while (!ready()) yield();

Polling and Busy waiting are both simple and obvious solutions, but they chew up CPU time, and we don't want that. We do want to yield, but would rather free up the CPU by telling the OS that we are waiting for some device to become ready, then come wake us up so that we can continue. This is

(3) Blocking wait_for(device D);

(Note: This sounds well and good, but how do we know when to unblock? We'd still need (1) or (2), so mechanisms still aren't optimal...)

The component of the OS that uses the mechanisms is the kernel scheduler, which, for each process P, records in the process table what P is waiting for.

E.g. Process table

what this process is waiting for | +---------------------v----------------------+ | | reg | | | | Process table entry +--------------------------------------------+

With this mechanism, the policy only worries about unblocked processes; blocked processes are invisible. The mechanism has abstracted all these details for the policy.

Don't assume cooperation

Polling, busy waiting and blocking all assume cooperation among processes. This is a mostly reasonable assumption, but software is written by humans and by default there will be bugs, especially since most programmers write code for each other but are not always cooperative. We just can't assume peaceful cooperation all the time. SEASnet, for example, is overrun with CS students trying new things that they don't entirely understand.

Solutions

So ther kernel can make a running process yield when it makes a system call. We would want the process to yield() if it is iterating through a loop or recursing many times.

But some loops don't have any system calls.

Most programmers don't insert yield() into their code

What alternative solutions are there?

1. Smart compilers that insert yield()'s
But current compilers are too dumb to decide when to stick yield()'s into the code. A compiler could stick yield() in every for loop, no matter how short it loops for, and it would have to for every function because of recursion. This is too slow.

2. Change the (Virtual) Machine
Every 10ms, the machine inserts a yield() system call. This is more feasible:

A typical machine has a timer interrupt, where the motherboard periodically sends signals to the CPU via bussing.

The CPU traps and enters the kernel

The kernel returns when it feels like: (1) immediately; (2) schedules other processes, then returns from a later timer interrupt.

Pre-emptive scheduling

By changing the VM, Linux does pre-emptive scheduling.

The upsides of this are that there are:

No runaway processes

No yield()'s in code

The downsides:

Complicates critical sections (where we cannot have blocks). For example, in gzip, we can't have an arbitrary block when we're renaming the .tmp file to a real file.

More generally, any pair of instructions that can't have delays- or it would be expensive to reload resources again- can have an arbitrary delay inserted.

Besides, this doesn't solve the actual problems. An infinite for loop would never escape.

Linux offers the -ulimit SIGXCPU option, where loops will only iterate finitely, but this is not robust.

Real time scheduling

In real-time scheduling, there are two deadlines to consider:

hard- which absolutely should not be missed;

soft- which we can miss sometimes.

1. Hard deadlines: such as automobile braking systems

Here the scheduler prioritizes Predictability over Performance

Timer interrupts/ Blocks are avoided in favor of Polling/ Busy waiting

The cache is turned off

2. Soft deadlines: such as video playback

Performance > Predictability

We can afford to miss a few frames or lag on the video quality (but of course if we do it too much users would give up).

Two scheduling algorithms

1. Earliest Deadline First + Pre-emption

This is simple, but one process might hog all the CPU time, so pre-emption rips control from the process, or kills it, before it finishes. Problems with this: If the CPU is overwhelmed, every process would chug along slowly, and the scheduler would constantly switch contexts and so everything poorly.

2. Add priorities

Rate-monotonic scheduling will assign higher priorities to more frequent tasks.

(2.) would solve (1.), and both together would be a pretty good scheduler.

Policy

The policy of scheduling determines which process can run and will run next.

Policy Issues

1. Long Term Scheduling Issues

This policy deals with the long term scheduling policy, where the scheduler will decide what will happen in a large time period (next few days or so). The major goal of this policy is to decide which process will be admitted into the system, for example:

fork() < 0

This means that the kernel has decided to not allow this process to run. Usually, programmers can get around this by trying over and over again until the scheduler allows them to run. For example:

for(int i = 0; i < 5; i++) { p = fork(); if(p < 0 && errno == EAGAIN) { sleep(1 << i); continue(); } if(p >= 0) break; }

Here we just keep asking the kernel for a process, and if we can't get one we sleep and try again later.

2. Medium Term Scheduling Issues

This policy deals with which process is going to run in the next few seconds. To gauge which processes will actually be running in the next few seconds we can look at where the processes are stored. If the processes are stored in RAM, then most likely they will be running soon. If they are stored on disk, then they might have to wait a little big longer to run.

3. Short Term Scheduling Issues

This policy deals with the very next processes to run. In this case there is actually a dispatcher that figures out the scheduling of the next few prcoesses. One of the problems the short term scheduling policy has to resolve is who runs if the runnable processes are greater than the number of CPUs. Which process will get to run next? (rhetorical)

Scheduling Metrics

There are a few values to consider when deciding which process should run next. These are

1. Wait Time - the total amount of time we have to wait before we can run

2. Runtime - the total amount of time it takes to run the program

3. Response Time - the total amount of time it takes before the application starts outputting

4. Context Switching Time - the total amount of time it takes to switch from one process to another

5. Turnaround Time - the total amount of time from when the application comes in to be processed to when it finishes processing

Arrival  Exec   1st Output                Finish

   |       |         |                       |

-------------------------------------------------------------> t

[AAAAAAAA][TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT]

|<------>||<------------Run Time------------>|

   Wait Time

|<-------->|

   Response Time

|<------------------------------------------>|

   Turnaround Time

Some other scheduling metrics that do not have to deal with the running processes themselves include:

1. Throughput - the number of jobs per second going through the system

2. Utilization - the percentage of time doing useful work

3. Fairness - whether or not every admitted job will eventually finish

It's important to note that all of these scheduling metrics are competing jobs. This means that it is impossible to satisfy every constraint perfectly since by reducing one it will cause another one to increase.

Scheduling Policies

1. First Come, First Served (FCFS)

Job# Arival Runtime Waittime A 0 5 0 B 1 2 4+d C 2 9 5+2d D 3 4 13+3d

The scheduler will look like this

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 ----------------------------------------------------------- t [AAAAAAAAAA][BBBB][CCCCCCCCCCCCCCCCCCCCCCCCCCC][DDDDDDDDDD] Average Wait Time = 5.5 + 1.5d Average Turnaround Time = 10.5 + 1.5d

This system is a fair system because everyone will finish, but the wait timer can generally take up a long amount of time if there are long jobs needed to be done.

2. Shortest Job First (Unfair System!)

SJF picks the job with the shortest runtime. The advantage of this is that small processes will finish quickly and won't have to wait on large ones to finish; however, large processes may be pre-empted by these smaller ones preventing them from every running. The benefit of this scheduling policy is that the average wait time is shorter, but the runtimes need to be known in advance for this to work properly.

Taking the same jobs as listed above for FCFS, the new waittimes and turnaround times become:


Average Wait Time = 4.25 + 1.5d

Average Turnaround Time = 8.5 + 1.5d

3. First Come, First Serve with Pre-Emption

FCFS with pre-emption is just like a FCFS except that it cycles through all of the active processes instead of waiting for them to finish. Effectively, this means that there will a greater amount of context switching, but the wait time and turnaround time will decrease. In general, this is the best method out of all of them because the wait times and turnaround times are smaller, but the system is still fair so long jobs can complete.


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20

----------------------------------------------------------- t

[A][B][C][D][A][B][C][D][A][C][D][A][C][D][A][CCCCCCCCCCCC]

Priority

One of the ways the scheduler can decide who runs is based off a given priority given to each process. The idea is that the priority with the higher number is able to run more often. Similar to FCFS with Pre-Emption, the scheduler will do a round-robin style switching between running applications and based off of the priority will determine who goes next.

1. Niceness

The Niceness factor used on linux systems helps to determine your priority. In general, it is a value ranging from -19 (which is downright cruel) to 19 (which is the nicest you can get). The nicer you are the more time you will give to other processes. The meaner you are the more time you will use the CPU for yourself. Applications can only increase their niceness, as decreasing niceness is reserved for kernel level applications.

nice(3); // only root can pass negative numbers

2. Other factors

Besides the niceness level, the operating system (unix) will look at other factors like how often someone is running in order to determine priority. In general, it is a combination of factors.

priority = niceness + some_other_stuff;

For example, students on the SEASnet machines will have a lower priority than the faculty who will have a lower priority than the system administrators.