星期四, 10月 15, 2009

CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Answers to Tutorial 5 Questions

Q1 Define the difference between Preemptive and Non-preemptive scheduling. State why strict non-preemptive scheduling is unlikely to be used in a computer centre, suggest a better scheme for interactive users.


Preemptive scheduling allows a process to be interrupted in the midst of its execution, taking the CPU away from it and allocating it to another process.

Non-preemptive scheduling ensures that a process relinquishes control of the CPU only when it finishes with its current burst.

Non-preemptive would not likely be used in a computer centre, especially in a time sharing system, because it cannot guarantee that each user gets a share of the CPU at regular intervals. Non-preemptiveness allows programs to run infinitely long thus making turnaround time (response time) for other submitted jobs even longer.

Round-Robin is a preemptive scheme that makes use of interrupt/context switching operation to allow processor switching between jobs. Long jobs cannot delay shorter ones, because short jobs are guaranteed of getting the processor periodically. Interactive users will thus receive the processor frequently enough to maintain good response times.





Q2 Explain the difference in degree to which the following scheduling algorithms discriminate in favour of short jobs.(i) First Come, First Served(ii) Round Robin(iii) Multi-level feedback queues


(i) First Come, First Served (FCFS) - discriminates against short jobs since any short jobs arriving after long jobs will have a long waiting time.
(ii) Round-Robin - treats all jobs equally (giving them equal bursts of CPU time) so short jobs will be able to leave the system faster since they will finish first.
(iii) Multi-Level Feedback Queues - discriminate very favourably toward short jobs since it works similar to the round robin algorithm.






Q3 What effect does the size of time quantum have on the performance of a round robin (RR) algorithm?



At one extreme, if the time quantum is extremely large, the RR policy is the same as the FCFS policy. If the time quantum is small, it must be large with respect to context switch, otherwise overhead is too high.






Q4 What advantage is there in having different quantum sizes on different levels of a multi-level feedback queuing system ?



The advantage is that the short jobs will have highest priority if they are shorter than the initial quantum. This serves them fast and frees the CPU to concentrate on longer jobs.
The jobs that are pushed to the next level (lower priority), now can be given more time than the initial quantum since the goal is to run as many programs as fast as possible with minimal delays to other programs.
Therefore, by increasing the quantum with the level, shorter jobs will be allowed higher priority, and longer jobs will be allowed to run simultaneously with minimum delays.