http:^^www.cs.wisc.edu^~cs537-1^scheduling.html

This data set contains WWW-pages collected from computer science departments of various universities

The second statement of <samp><font color="0f0fff">swap_process</font></samp> saves a pointer to that stack
frame in <samp><font color="0f0fff">pcb</font></samp>.
The third statement then loads <samp><font color="0f0fff">SP</font></samp> with a pointer to <samp><font color="0f0fff">P1</font></samp>'s
stack frame for <samp><font color="0f0fff">swap_process</font></samp>.
Now, when the procedure returns, it will be a return to whatever
procedure called <samp><font color="0f0fff">swap_process</font></samp> in process <samp><font color="0f0fff">P1</font></samp>.
    
<a name="cs_impl"> <h3> Implementing Critical Sections </h3> </a>
<p>
The final piece in the puzzle is to implement <samp><font color="0f0fff">begin_cs</font></samp> and
<samp><font color="0f0fff">end_cs</font></samp>.
There are several ways of doing this, depending on the hardware
configuration.
First suppose there are multiple CPU's accessing a single shared memory
unit.
Generally, the memory or bus hardware <em>serializes</em> requests to
read and write memory words.
For example, if two CPU's try to write different values to the same
memory word at the same time, the net result will be one of the two values,
not some combination of the values.
Similarly, if one CPU tries to read a memory word at the same time another
modifies it, the read will return either the old or new value--it will not
see a ``half-changed'' memory location.
Surprisingly, that is all the hardware support we need to implement
critical sections.
<p>
The first solution to this problem was discovered by the Dutch mathematician
T. Dekker.
A simpler solution was later discovered by Gary Peterson.
Peterson's solution looks deceptively simple.
To see how tricky the problem is, let us look at a couple of simpler-- but
incorrect--solutions.
For now, we will assume there are only two processes, <samp><font color="0f0fff">P0</font></samp> and <samp><font color="0f0fff">P1</font></samp>.
The first idea is to have the processes take turns.
<pre><font color="0f0fff">
    shared int turn;             // 1 or 2, depending on 
    void begin_cs(int i) {       // process i's version of begin_cs
        while (turn != i) { /* do nothing */ }
    }
    void end_cs(int i) {         // process i's version of end_cs
        turn = 1 - i;            // give the other process a chance.
    }
</font></pre>
This solution is certainly <em>safe</em>, in that it never allows both
processes to be in their critical sections at the same time.
The problem with this solution is that it is not <em>live</em>.
If process <samp><font color="0f0fff">P0</font></samp> wants to enter its critical section and <samp><font color="0f0fff">turn == 1</font></samp>,
it will have to wait until process <samp><font color="0f0fff">P1</font></samp> decides to enter and then
leave its critical section.
Since we will only used critical sections to protect short operations
(see the implementation of semaphores
<!WA5><a href="#semaphore_impl">above</a>), it is reasonable to assume that
a process that has done <samp><font color="0f0fff">begin_cs</font></samp> will soon do <samp><font color="0f0fff">end_CS</font></samp>,
but the converse is not true:  There's no reason to assume that the
other process will want to enter its critical section any time in the
near future (or even at all!).
<p>
To get around this problem, a second attempt to solve the problem uses
a shared array <samp><font color="0f0fff">critical</font></samp> to indicate which processes are in
their critical sections.
<pre><font color="0f0fff">
    shared boolean critical[] = { false, false };
    void begin_cs(int i) {
        critical[i] = true;
        while (critical[1 - i]) { /* do nothing */ }
    }
    void end_cs(int i) {
        critical[i] = false;
    }
</font></pre>
This solution is unfortunately prone to deadlock.
If both processes set their <samp><font color="0f0fff">critical</font></samp> flags to <samp><font color="0f0fff">true</font></samp> at
the same time, they will each loop forever, waiting for the other
process to go ahead.
If we switch the order of the statements in <samp><font color="0f0fff">begin_cs</font></samp>, the solution
becomes unsafe.
Both processes could check each other's <samp><font color="0f0fff">critical</font></samp> states at the same
time, see that they were <samp><font color="0f0fff">false</font></samp>, and enter their critical sections.
Finally, if we change the code to
<pre><font color="0f0fff">
    void begin_cs(int i) {
        critical[i] = true;
        while (critical[1 - i]) {
            critical[i] = false;
            /* perhaps sleep for a while */
            critical[i] = true;
        }
    }
</font></pre>
<em>livelock</em> can occur.
The processes can get into a loop in which each process sets its own
<samp><font color="0f0fff">critical</font></samp> flag, notices that the other <samp><font color="0f0fff">critical</font></samp> flag is
<samp><font color="0f0fff">true</font></samp>, clears its own <samp><font color="0f0fff">critical</font></samp> flag, and repeats.
<p>
Peterson's (correct) solution combines ideas from both of these attempts.
Like the second ``solution,'' each process signals its desire to enter
its critical section by setting a shared flag.
Like the first ``solution,'' it uses a <samp><font color="0f0fff">turn</font></samp> variable, but it
only uses it to break ties.
<pre><font color="0f0fff">
    shared int turn;
    shared boolean critical[] = { false, false };
    void begin_cs(int i) {
        critical[i] = true;     // let other guy know I'm trying
        turn = 1 - i;           // be nice: let him go first
        while (
            critical[j-1]  // the other guy is trying
            &amp;&amp; turn != i   // and he has precedence
        ) { /* do nothing */ }
    }
    void end_cs(int i) {
        critical[i] = false;    // I'm done now
        
    }
</font></pre>
<p>
Peterson's solution, while correct, has some drawbacks.
First, it employs a busy wait (sometimes called a <em>spin lock</em>)
which is bad for reasons suggested above.
However, if critical sections are only used to protect very short
sections of code, such as the <samp><font color="0f0fff">down</font></samp> and <samp><font color="0f0fff">up</font></samp> operations on
semaphores as above, this isn't too bad a problem.
Two processes will only rarely attempt to enter their critical sections
at the same time, and even then, the loser will only have to ``spin'' for
a brief time.
A more serious problem is that Peterson's solution only works for two processes.
Next, we present three solutions that work for arbitrary numbers of
processes.
<p>
Most computers have additional hardware features that make the
critical section easier to solve.
One such feature is a ``test and set'' instruction that sets a memory location
to a given value and <em>at the same time</em> records in the CPU's unshared
state information about the location's previous value.
For example, the old value might be loaded into a register, or
a condition code might be set to indicate whether the old value was zero.
Tanenbaum presents in Fig 2-9 on page 39 a solution using test-and-set.
Here is a version using Java-like syntax
<pre><font color="0f0fff">
    shared boolean lock = false;    // true if any process is in its CS
    void begin_cs() {               // same for all processes
        for (;;) {
            boolean key = testAndSet(lock);
            if (!key)
                return;
        }
    }
    void end_cs() {
        lock = false;
    }
</font></pre>
Some other computers have a <samp><font color="0f0fff">swap</font></samp> instruction that swaps the
value in a register with the contents of a shared memory word.
<pre><font color="0f0fff">
    shared boolean lock = false;    // true if any process is in its CS
    void begin_cs() {               // same for all processes
        boolean key = true;
        for (;;) {
            swap(key, lock)
            if (!key)
                return;
        }
    }
    void end_cs() {
        boolean key = false;
        swap(key, lock)
    }
</font></pre>
<p>
The problem with both of these solutions is that they do not necessarily
prevent <em>starvation</em>.
If several processes try to enter their critical sections at the same time,
only one will succeed (safety) and the winner will be chosen in a bounded
amount of time (liveness), but the winner is chosen essentially randomly,
and there is nothing to prevent one process from winning all the time.
The ``bakery algorithm'' of Leslie Lamport solves this problem.
When a process wants to get service, it takes a ticket.
The process with the lowest numbered ticket is served first.
The process id's are used to break ties.
<pre><font color="0f0fff">
    static final int N = ...;         // number of processes

    shared boolean choosing[] = { false, false, ..., false };
    shared int ticket[] = { 0, 0, ..., 0 };

    void begin_cs(int i) {
        choosing[i] = true;
        ticket[i] = 1 + max(ticket[0], ..., ticket[N-1]);
        choosing[i] = false;
        for (int j=0; j&lt;N; j++) {
            while (choosing[j]) { /* nothing */ }
            while (ticket[j] != 0
                &amp;&amp; (
                    ticket[j] &lt; ticket[i]
                    || (ticket[j] == ticket[i] &amp;&amp; j &lt; i)
                ) { /* nothing */ }
        }
    }
    void end_cs(int i) {
        ticket[i] = 0;
    }
</font></pre>
<p>
Finally, we note that all of these solutions to the critical-section
problem assume multiple CPU's sharing one memory.
If there is only one CPU, we cannot afford to busy-wait.
However, the good news is that we don't have to.
All we have to do is make sure that the short-term scheduler (to be
discussed in the next section) does not switch processes while
a process is in a critical section.
One way to do this is simply to block interrupts.
Most computers have a way of preventing interrupts from occurring.
It can be dangerous to block interrupts for an extended period of time,
but it's fine for very short critical sections, such as the ones used
to implement semaphores.
Note that a process that blocks on a semaphore does not need mutual exclusion
the whole time it's blocked; the critical section is only long enough to
decide whether to block.

<a name="short_term_sched"> <h3> Short-term Scheduling </h3> </a>
<p>
<!WA6><a href="http://www.cs.wisc.edu/~cs537-1/processes.html#using_states">Earlier</a>, we called a process
that is not blocked ``runnable'' and said that a runnable process is either
<em>ready</em> or <em>running</em>.
In general, there is a list of runnable processes called the <em>ready
list</em>.
Each CPU picks a process from the ready list and runs
it until it blocks.
It then chooses another process to run, and so on.
The implementation of semaphores
<!WA7><a href="#semaphore_impl">above</a> illustrates this.
This switching among runnable processes is called <em>short-term
scheduling</em><!WA8><a href="#footnote"><sup>1</sup></a>, and the algorithm that
decides which process to run and how long to run it is called a short-term
scheduling <em>policy</em> or <em>discipline</em>.
Some policies are <em>preemptive</em>, meaning that the CPU may switch
processes even when the current process isn't blocked.
<p>
Before we look at various scheduling policies, it is worthwhile to 
think about what we are trying to accomplish.
There is a tension between maximizing overall efficiency and giving
good service to individual ``customers.''
From the system's point of view, two important measures are
<dl>
<dt><b>Throughput.</b>
<dd>The amount of useful work accomplished per unit time.
This depends, of course, on what constitutes ``useful work.''
One common measure of throughput is jobs/minute (or second, or hour,
depending on the kinds of job).
<dt><b>Utilization.</b>
<dd>For each device, the <em>utilization</em> of a device is the fraction
of time the device is busy.
A good scheduling algorithm keeps all the devices (CPU's, disk drives, etc.)
busy most of the time.
</dl>
Both of these measures depend not only on the scheduling algorithm, but
also on the <em>offered load</em>.
If load is very light--jobs arrive only infrequently--both throughput
and utilization will be low.
However, with a good scheduling algorithm, throughput should increase
linearly with load until the available hardware is saturated and throughput
levels off.
<center>
<!WA9><img align=top src="http://www.cs.wisc.edu/~cs537-1/loadgraph.gif">
</center>
<p>
Each ``job''<!WA10><a href="#footnote"><sup>2</sup></a> also wants good service.
In general, ``good service'' means good response:
It is starts quickly, runs quickly, and finishes quickly.
There are several ways of measuring response:
<dl>
<dt><b>Turnaround.</b>
<dd>The length of time between when the job arrives in the system and when
it finally finishes.
<dt><b>Response Time.</b>
<dd>The length of time between when the job arrives in the system and when
it starts to produce output.
For interactive jobs, response time might be more important than turnaround.
<dt><b>Waiting Time.</b>
<dd>The amount of time the job is ready (runnable but not running).
This is a better measure of scheduling quality than turnaround, since
the scheduler has no control of the amount of time the process spends
computing or blocked waiting for I/O.
<dt><b>Penalty Ratio.</b>
<dd>Elapsed time divided by the sum of the CPU and I/O demands of the
the job.
This is a still better measure of how well the scheduler is doing.
It measures how many times worse the turnaround is than it would be
in an ``ideal'' system.
If the job never had to wait for another job, could allocate each I/O device
as soon as it wants it, and experienced no overhead for other operating
system functions, it would have a penalty ratio of 1.0.
If it takes twice as long to complete as it would in the perfect system,
it has a penalty ration of 2.0.
</dl>
To measure the overall performance, we can then combine the performance
of all jobs using any one of these measures and any way of combining.
For example, we can compute <em>average waiting time</em> as the average
of waiting times of all jobs.
Similarly, we could calculate the sum of the waiting times, the
average penalty ratio, the variance in response time, etc.
There is some evidence that a high variance in response time can be
more annoying to interactive users than a high mean (within reason).
<p>
Since we are concentrating on short-term (CPU) scheduling, one useful
way to look at a process is as a sequence of <em>bursts</em>.
Each burst is the computation done by a process between the time
it becomes ready and the next time it blocks.
To the short-term scheduler, each burst looks like a tiny ``job.''
<h4>First-Come-First-Served</h4>
<p>
The simplest possible scheduling discipline is called <em>First-come,
first-served</em> (FCFS).
The ready list is a simple queue (first-in/first-out).
The scheduler simply runs the first job on the queue until it blocks, then
it runs the new first job, and so on.
When a job becomes ready, it is simply added to the end of the queue.
<p>
Here's an example, which we will use to illustrate all the scheduling
disciplines.
<center>
<table align=center width="50%" compact boarder=0>
<tr align="center">