Shortest Process Next

Shortest Process Next

Because shortest job first always creates the minimum average response time for batch systems, it would be nice if it could be used for interactive processes as well. To a certain extent, it can be. Interactive processes usually follow the  pattern of wait for command, execute command, wait for command, execute command, and so on. If we consider the execution of each command as a separate "job", then we could minimize overall response time by running the shortest one first. The only problem is figuring out which of the currently runnable processes is the shortest one.

One approach is to make estimates based on past behavior and run the process with the shortest estimated running time.  Assume that the estimated time per command for some terminal is T0. Now assume its next run is measured to be T1. We could update our estimate by taking a weighted sum of these two numbers, that is, aT0 + (1 - a)T1. Through the choice of a, we can decide to have the estimation process forget old runs quickly or remember them for a long time. With a = 1/2, we get successive estimates of

T0,  T0/2 + T1/2,  T0/4 + T1/4 + T2/2, T0/8 + T1/8 + T2/4 + T3/2

After three new runs, the weight of T0 in the new estimate has dropped to 1/8.

The technique of estimating the next value in a series by taking the weighted average of the current measured value and the previous estimate is sometimes called aging. It is applicable to many situations where a prediction must be made based on previous values. Aging is especially easy to implement when a = 1/2. All that is required is to add the new value to the current estimate and divide the sum by 2 (by shifting it right 1 bit).

Guaranteed Scheduling

A totally different approach to scheduling is to make real promises to the users about performance and then live up to those promises. One promise that is realistic to make and easy to live up to is this: If there are n users logged in while you are working, you will receive about 1/n of the CPU power. Likewise, on a single-user system with n processes running, all things being equal, each one should get 1/n of the CPU cycles. That seems fair enough.

To make good on this promise, the system must keep track of how much CPU each process has had since its creation. It then computes the amount of CPU each one is entitled to, namely the time since creation divided by n. Since the amount of CPU time each process has actually had is also known, it is straightforward to compute the ratio of actual CPU time consumed to CPU time entitled. A ratio of 0.5 means that a process has only had half of what it should have had, and a ratio of 2.0 means that a process has had twice as much as it was entitled to. The algorithm is then to run the process with the lowest ratio until its ratio has moved above its closest competitor.

Lottery Scheduling

While making promises to the users and then living up to them is a fine idea, it is hard to implement. On the other hand, another algorithm can be used to give equally predictable results with a much simpler implementation. It is called lottery scheduling (Waldspurger and Weihl, 1994).

The main idea is to give processes lottery tickets for various system resources, such as CPU time. Whenever a scheduling decision has to be made, a lottery ticket is chosen at random, and the process holding that ticket gets the resource. When applied to CPU scheduling, the system might hold a lottery 50 times a second, with each winner getting 20 msec of CPU time as a prize.

To paraphrase George Orwell: "All processes are equal, but some processes are more equal". More important processes can be given extra tickets, to increase their odds of winning. If there are 100 tickets outstanding, and one process holds 20 of them, it will have a 20% chance of winning each lottery. In the long run, it will get about 20% of the CPU. In contrast to a priority scheduler, where it is very hard to state what having a priority of 40 actually means, here the rule is clear: a process holding a fraction f of the tickets will get about a fraction f of the resource in question.

Lottery scheduling has many interesting features. For instance, if a new process shows up and is granted some  tickets, at the very next lottery it will have a chance of winning in proportion to the number of tickets it holds. In other words, lottery scheduling is highly responsive.

Cooperating processes may exchange tickets if they wish. For instance, when a client process sends a message to a server process and then blocks, it may give all of its tickets to the server, to increase the chance of the server running next. When the server is ended, it returns the tickets so that the client can run again. In reality, in the absence of clients, servers need no tickets at all.

Lottery scheduling can be used to solve problems that are hard to handle with other methods. One instance is a video server in which numerous processes are feeding video streams to their clients, but at different frame rates. Assume that the processes need frames at 10, 20, and 25 frames/sec. By allocating these processes 10, 20 and 25 tickets, respectively, they will automatically divide the CPU in approximately the correct proportion, that is, 10 : 20 : 25.

Fair-Share Scheduling

Until now we have assumed that each process is scheduled on its own, without regard to who its owner is. As a result, if user 1 starts up 9 processes and user 2 starts up 1 process, with round robin or equal priorities, user 1 will get 90% of the CPU and user 2 will get only 10% of it.

To avoid this situation, some systems take into account who owns a process before scheduling it. In this model, each user is allocated some fraction of the CPU and the scheduler picks processes in such a way as to enforce it. Thus if two users have each been promised 50% of the CPU, they will each get that, no matter how many processes they have in existence.

As an example, consider a system with two users, each of which has been promised 50% of the CPU. User 1 has four processes, A, B, C, and D, and user 2 has only 1 process, E. If round-robin scheduling is used, a possible scheduling sequence that meets all the constraints is this one:

A E B E C E D E A E B E C E D E . . .

However, if user 1 is entitled to twice as much CPU time as user 2, we might get

A B E C D E A B E C D E ...

Many other possibilities exist, certainly, and can be exploited, depending on what the concept of fairness is.



Tags

algorithm, process, batch systems, interactive processes, lottery scheduling