1.5 Synchronization, cpu scheduling  (Page 10/10)

Originally, Unix had 1 sec. time slices. Too long. Most timesharing systems today use time slices of 10,000 - 100,000 instructions.

Implementation of priorities: run highest priority processes first, use round-robin among processes of equal priority. Re-insertprocess in run queue behind all processes of greater or equal priority.

Even round-robin can produce bad results occasionally. Go through example of ten processes each requiring 100 timeslices.

What is the best we can do?

Stcf

Shortest time to completion first with preemption. This minimizes the average response time.

As an example, show two processes, one doing 1 ms computation followed by 10 ms I/O, one doing all computation. Suppose we use 100ms time slice: I/O process only runs at 1/10th speed, effective I/O time is 100 ms. Suppose we use 1 ms time slice: then compute-bound process gets interrupted9 times unnecessarily for each valid interrupt. STCF works quite nicely.

Unfortunately, STCF requires knowledge of the future. Instead, we can use past performance to predict future performance.

Exponential queue (also called "multi-level feedback queues")

Attacks both efficiency and response time problems.

• Give newly runnable process a high priority and a very short time slice. If process uses up the time slice without blocking then decreasepriority by 1 and double time slice for next time.
• Go through the above example, where the initial values are 1ms and priority 100.
• Techniques like this one are called adaptive. They are common in interactive systems.
• The CTSS system (MIT, early 1960's) was the first to use exponential queues.

Fair-share scheduling as implemented in Unix:

• Figure out each process' "share" of CPU, based on number of processes and priorities.
• Keep a history of recent CPU usage for each process: if it is getting less than its share, boost priority. If it is getting more than itsshare, reduce priority.
• Careful: could be unstable!

Summary:

• In principle, scheduling algorithms can be arbitrary, since the system should behave the same in any event.
• However, the algorithms have crucial effects on the behavior of the system:
  • Overhead: number of context swaps.
  • Efficiency: utilization of CPU and devices.
  • Response time: how long it takes to do something.
• The best schemes are adaptive. To do absolutely best, we would have to be able to predict the future.

Priority inversion problem

There are some curious interactions between scheduling and synchronization. A classic problem caused by this interaction wasfirst observed in 1979 but Butler Lampson and David Redell at Xerox.

Suppose that you have three processes:

And suppose that you have the following critical section, S:

S: mutex.P()

. . .

. . .

mutex.V()

The three processes execute as follows:

1. P3 enters S, locking the critical section.
2. P3 is preempted by the scheduler and P2 starts running.
3. P2 is preempted by the scheduler and P1 starts running.
4. P1 tries to enter S and is blocked at the P operation.
5. P2 starts running again, preventing P1 from running.

So, what's going wrong here? To really understand this situation, you should try to work out the example for yourself, beforecontinuing to read.

• As long as process P2 is running, process P3 cannot run.
• If P3 cannot run, then it cannot leave the critical section S.
• If P3 does not leave the critical section, then P1 cannot enter.

As a result, P2 running (at medium priority) is blocking P1 (at highest priority) from running. This example is not an academicone. Many designers of real-time systems, where priority can be crucial, have stumbled over issue. You can read the original paper by Lampson and Redell to see their suggestion for handling the situation.