Long-term scheduling is used to admit new processes to the system and is done whenever a user wants to create a new process.

Medium-term scheduling is used to swap processes between secondary storage and main memory and is done periodically to ensure the CPU utilization is high and that the page fault rate is low.

Short-term scheduling is used to allocate the CPU to a process and is done whenever a process has its timeslice expire, or when the current process needs to perform some I/O.

All of these scheduling algorithms try to order the queue according to the next CPU burst a process is likely to have. Since it is not possible to look into the future or examine the process and know the length of the next burst, this quantity must be estimated. This is done by using past CPU bursts to predict future burst. The estimate of the next CPU burst is calculated as a weighted, exponential average. The previous CPU burst is given weight alpha and the current estimate is given weight (1 - alpha). By varying alpha, more weight can be given to the most recent CPU burst, allowing for faster reaction to changes in a process but also a highly varying estimate. Giving weight to the previous estimate allows the estimate to change more smoothly. In effect, the estimation equation gives an exponentially smaller weight to CPU bursts the farther in the past they occurred.

A small quantum reduces the response time for all processes, which is important for interactive processes. However, a long quantum reduces the overhead of process switching, which increases throughput and CPU utilization. A short quantum is useful for a general-purpose computer. A long quantum is useful for a batch system. You might have a system that uses a short quantum when there are jobs that need a quick response time, then lengthens the quantum when heavy computation needs to be done.

A I/O bound process is favored by a multilevel feedback queueing scheduler because jobs that use the CPU heavily will be moved to low priority queues. This will leave the I/O bound processes in the higher priority queues.

The issue here is that a program spends much of its time waiting for I/O to complete. In a multithreaded program, one KLT can make the blocking system call, while the other KLTs can continue to run. On a uniprocessor machine, a process that would otherwise have to block for all these calls can continue to run its other threads.

a.      Assume the scheduler in the OS will not start a job unless there are four tape drives available. When a job is started, four drives are assigned immediately and are not released until the job finishes. What is the maximum number of jobs that can be in progress at once? What is the maximum and minimum number of tape drives that may be left idle as a result of this policy?

If a conservative policy is used, at most 20/4 = 5 processes can be active simultaneously. Because one of the drives allocated to each process can be idle most of the time, at most 5 drives will be idle at a time. In the best case, none of the drives will be idle.

b.      Suggest an alternative policy to improve tape drive utilization and at the same time avoid system deadlock. What is the maximum number of jobs that can be in progress at once? What are the bounds on the number of idling tape drives?

To improve drive utilization, each process can be initially allocated with three tape drives. The fourth one will be allocated on demand. In this policy, at most floor(20/3) = 6 processes can be active simultaneously. The minimum number of idle drives is 0 and the maximum number is 2.

Perform the same analysis as depicted for this set.

             0         5        10        15        20

             | | | | | | | | | | | | | | | | | | | | |

FCFS     P1 ------

         P2        ----------

         P3                  ----

         P4                      ----------

         P5                                ----------

RR q=1   P1 -- --    --    

         P2    -- --    -- -- --

         P3          --    --

         P4                    -- -- -- -- --

         P5                          -- -- -- ----

RR q=4   P1 ------        

         P2        --------    --  

         P3                ----

         P4                      --------        --

         P5                              -------- --

SPN      P1 ------        

         P2            ----------

         P3        ----

         P4                      ----------

         P5                                ----------

SRT      P1 ------        

         P2            ----------

         P3        ----

         P4                      ----------

         P5                                ----------

HRRN     P1 ------

         P2        ----------

         P3                  ----

         P4                      ----------

         P5                                ----------

FB q=1   P1 -- --      --

         P2    --    --    ---- --

         P3        -- --     

         P4                   -- -- -- -- -- 

         P5                          -- -- -- ----

FB q=2^i P1 -- ----

         P2    --      ---- ----

         P3          --    --     

         P4                      ------ ----

         P5                            --    --------

For feedback queueing with a quantum of 1, I assume that when a process is taken off the processor and placed in a lower priority queue, it is not eligible to go right back onto the processor. It must wait another quantum. For feedback queueing with a quantum of 2i, I assume that a newly arriving process can't preempt the current process until it is done with its quantum. This is different from the book's assumption and therefore different from Figure 9.5 in the book.

Here are the metrics:

               1     2     3     4     5

       Ta      0     1     3     9    12

       Ts      3     5     2     5     5

================================================

FCFS   Tf      3     8    10    15    20

       Tq      3     7     7    6     8    6.20

     Tq/Ts   1.00 1.40 3.50 1.20 1.60   1.74

================================================

RR q=1 Tf      6    11     8    18    20

       Tq      6    10     5     9     8    7.60

     Tq/Ts   2.00 2.00 2.50 1.80 1.60   1.98

================================================

RR q=4 Tf      3    10     9    19    20

       Tq      3     9     6    10     8    7.20

     Tq/Ts   1.00 1.80 3.00 2.00 1.60   1.88

================================================

SPN    Tf      3    10     5    15    20

       Tq      3     9     2     6     8    5.60

     Tq/Ts   1.00 1.80 1.00 1.20 1.60   1.32

================================================

SRT    Tf      3    10     5    15    20

       Tq      3     9     2     6     8    5.60

     Tq/Ts   1.00 1.80 1.00 1.20 1.60   1.32

================================================

HRRN   Tf      3    10     5    15    20

       Tq      3     7     7     6     8    6.20

     Tq/Ts   1.00 1.40 3.50 1.20 1.60   1.74

================================================

FB q=1 Tf      7    11     6    18    20

       Tq      7    10     3     9     8    7.40

     Tq/Ts   2.33 2.00 1.50 1.80 1.60   1.85

================================================

FB q=1 Tf      4    10     8    16    20

       Tq      4     9     5     7     8    7.00

     Tq/Ts   1.33 1.80 2.50 1.40 1.60   1.81

================================================

Assume the following burst-time pattern for a process: 6,4,6,4,13,13,13, and assume that the initial guess is 10.

Process    Running Time      Priority

   A           15                4

   B            9                7

   C            3                3

   D            6                1

   E           12                6

a. round robin with a time quantum of 1 minute

1 2 3 4 5   Elapsed Time

============================

A B C D E   5

A B C D E   10

A B C D E   15

A B     D E   19

A B     D E   23

A B     D E   27

A B        E   30

A B        E   33

A B        E   36

A           E   38

A           E   40

A           E   42

A               43

A               44

A               45

Process Turnaround Time

========================

A        45

B        35

C        13

D        26

E        42

Average Turnaround Time = 32.2 minutes

b. priority scheduling

Process Priority Turnaround Time

==================================

B        7         9

E        6        21

A        4        36

C        3        39

D        1        45

Average Turnaround Time = 30 minutes

c. FCFS (run in order 15, 9, 3, 6, and 12)

Process Turnaround Time

========================

A        15

B        24

C        27

D        33

E        45

Average Turnaround Time = 28.8 minutes

d. shortest job first

Process Running Time Turnaround Time

======================================

C            3          3

D            6          9

B            9          18

E           12          30

A           15          45

Average Turnaround Time = 21 minutes

Develop scheduling diagrams for this set of tasks.

Discuss how priorities could be assigned to guarantee the response time of 0.1 ms for the impact sensor and to handle each of the other critical units before the next interrupt is produced.

The impact sensor must be given the highest priority because its required response time is less than the service time for each of the other interrupts types; no other subsystem can share this highest priority.

The air conditioner can be given the lowest priority level because its function is not safety-critical.

We have two priority levels left for three subsystems.

Because the engine temperature monitor has a maximum service time of 100 ms it must have a lower priority than the display and fuel/ignition subsystems, which need several hundreds of service periods per second.

Finally, the display and fuel/ignition subsystems can share the same priority level since each can be served after the other without exceeding the time available before the next interrupt.

For example, if the fuel/ignition subsystem service starts right before the display interrupt, a total of 1.2 ms will elapse before the service routines of both interrupts are completed, whereas there is 1/800 sec - 1.25 ms available before the next dashboard display interrupt arrives.

Note that we have ignored the service time for impact sensor subsystem interrupts that have the highest priority because they occur very infrequently, and when they do, all else becomes unimportant.