Chapter 4: Processor Management, Flynn and McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Co. (1997)

Lesson B: Shortest Job Next, Priority Scheduling, Shortest Remaining Time, Round Robin, Multiple Level Queues, About Interrupts, Conclusion

Problems 7, 8, 9, 10 or 12

Problem 7.  Given the following information:

Draw a time line for each of the following scheduling algorithms.  (It may be helpful to first compute a start and finish time for each job.)

The number pairs in the tables below indicate [(Job Number).(CPU Cycles Remaining)]

1. First Come First Served (Nonpreemptive)

2. Shortest Job Next (Nonpreemptive)

3. Shortest Remaining Time (Preemptive)

4. Round robin (using a time quantum of 2, ignore context switching and natural wait). (Preemptive).  Assume that new jobs entering a queue at time T are ahead of jobs that are suspended at time T.  (You might have made the opposite assumption.  You will get a different answer.  That is OK.  State and be consistent with your assumption.) 

Problem 8.  Using the same information given for exercise 7, complete the chart by computing waiting time and turnaround time for every job for each of the following scheduling algorithms (ignoring context switching overhead).

1. First Come First Served

2. Shortest Job Next

3. Shortest Remaining Time

4. Round Robin (using a time quantum of 2)

Problem 9.  Using the same information given for exercise 7, compute the average waiting time and average turn-around time for each of the following scheduling algorithms and determine which one gives the best results.

For this specific job stream, the Shortest Remaining Time policy yields the best average total waiting time and average turn-around time.

Problem 10.  Consider a variation of round robin in which a process that has used its full time quantum is returned to the end of the READY queue, while one that has used half of its time quantum is returned to the middle of the queue and one that has used one-fourth of its time quantum goes to a place one-fourth of the distance away from the beginning of the queue.

Discussion:  A full time quantum is the amount of time allocated per time slice.  Why might a job be suspended prior to completing its time quantum?  What kinds of interrupts exist besides a time quantum interrupt?

1. What is the objective of this scheduling policy?

A job that has generates an interrupt in a time slice that is much shorter than a time quantum might be doing this frequently in an external resource intensive application, such as external storage, to complete its task.  If the job were placed at the bottom of the Ready queue, it would take a long time to complete its task.  The proposed scheduling policy would accelerate I/O-bound jobs through the system. 

The text's answer book remarks that this approach achieves good and relatively evenly distributed terminal response time.

2. Discuss the advantage and disadvantage of its implementation.

A benefit is that resources dedicated to only that particular process could be released sooner to serve another task.  This would permit the computer center to service more I/O-bound jobs per day.  This is important in a computer center that uses disk packs and tape drives.  This is a common environment for business data processing.

This policy tends to slow down the progress of CPU-bound jobs that must wait for I/O bound jobs.

In a computer center providing an interactive data base service, such as a technical library, your desire is to reduce the revisit time per customer.  If the time quantum is chosen to be less than 2 seconds, you are better off placing the job at the end of the queue and servicing the next customer.  Otherwise, you might end up locking out some customers.

Problem 12.  Some guidelines for selecting the "right" time quantum were given in this chapter.  As a system designer, how would you know when you have chosen the "best" time quantum?  What factors would make this time quantum best from the user's point of view?  What factors would make this time quantum best from the system's point of view?

Answer:  You need to have determine what your performance goals should be.  To determine if you have met your performance goals, you must measure the variables needed for computing your measure of effectiveness.  These constitute a sample of the job mix actually run at the computer center.  You expect the "right" time quantum to change when the nature of the job mix changes.

The text's answer book says that you know you have chosen a good time quantum when:

• Interactive processes generate short response times.
• System resources are equitably shared among processes.
• Majority of short processes execute within one time quantum.

Technically, the time quantum must strike a balance between responsiveness and task completion.  Throughput is degraded by context-switching time.  During a detailed assessment, you want to record the time quantum in use, the process control block each time a process changes state, cost to the customer, and customer satisfaction.  Of course, your best data input for customer satisfaction is your help line.  From the individual records, you obtain system-wide statistics for service provided as a function of time quantum.

A customer chooses interactive use of a computer when he wants near-real-time response.  Processes initiated by interactive users tend to require short amounts of time.  Fast turn-around time is important.  This favors a short time quantum.  A customer chooses batch mode to obtain desired results economically, which favors a long time quantum.

To determine if you have chosen the best time quantum, you can run real experiments by actually varying the time quantum to determine the direction of change in performance.  You also can use measured data as inputs to a simulation and determine the changes in performance according to your measure of effectiveness.  In computer science, this question is addressed by queuing theory.