The long-term scheduler decides which processes are going to be loaded on the ready queue, if too many process are to be served by the CPU a high occurrence of context switches is generated which could lead to a decrease in the processor's performance and to have long waiting time for the resources to be freed, and too few processes in queue indicates a poor CPU utilization.
The shortterm scheduler decides which process in the ready queue is to be served by the CPU. In general the short-term scheduler is invoked more frequently than the long-term scheduler since it is less frequent to add a new processes to the ready queue than swapping processes between CPU and ready queue. Due of the importance of the decisions taken by the long-term scheduler, if it is not well implemented it would seriously affect the system's performance (CPU under usage or process overload).
Consider two CPU scheduling algorithms for a single CPU: Round-Robin scheduling and (non-preemptive) Shortest-Job-First scheduling. Assume that there is no time lost during context switching. Given five processes with arrival times and expected CPU time:
A) Assuming Shortest-Job-First scheduling, draw a Gantt chart to show when each process executes on the CPU. Also compute the average waiting time.
B) Repeat for Round-Robin scheduling, assuming a time quantum of size = 6.
Consider a computer system with virtual memory and recall that the long-term
scheduler controls the "degree of multiprogramming" (the number of processes in memory).
A) Define thrashing and its relationship to the degree of multiprogramming.
There are diverse ways in which an OS can manage data from secondary storage for use in main
memory. One memory management schema is referred to as paging, in which the OS retrieves data from secondary storage in same size blocks called pages.
Trashing occurs in paging systems, it is caused by under allocation of the minimum number of pages required by a process, forcing it to continuously page fault. Trashing can be detected by evaluating the level of CPU utilization compared to the level of multiprogramming. It can be eliminated by reducing the level of multiprogramming.
References:
http://ustcsserver01.tripod.com/YEAR2/fallsem/COMP252/pastp/final00F_tr.pdf,
http://en.wikipedia.org/wiki/Paging
B) Draw a typical graph of CPU utilization as a function of the degree of multiprogramming and
describe why it has this shape.
As the illustration shows, CPU utilization of a system can be improved by using multiprogramming. Let P be the fraction of time that a process spends away from the CPU. If there is one process in memory, the CPU utilization is (1-P). If there are N processes in memory, the probability of N processes waiting for an I/O is P*P...*P (N times). The CPU utilization is ( 1 - P^N ) where N is called the multiprogramming level (MPL) or the degree of multiprogramming. As N increases, the CPU utilization increases. While this equation indicates that a CPU continues to work more efficiently as more and more processes are added, logically, this cannot be true. Once the system passes the point of optimal CPU utilization, it thrashes.
Reference: http://cs.gmu.edu/cne/modules/vm/green/multip.html
Now, the system is measured to determine the utilization of the CPU and the utilization of the disk used for swapping pages. For each of the following possible measurements, state (YES/NO) whether the CPU utilization would be expected to increase if the degree of multiprogramming was increased. Provide a brief explanation in each case.
A) CPU utilization 13%; disk utilization (multiprogramming)97%
No. The system is spending most of the time serving page faults, i.e. trashing. We should decrease degree of multiprogramming in this case.
B) CPU utilization 13%; disk utilization 3%
Yes. The system is underutilized, we should increase the degree of multiprogramming to increase the CPU utilization.
C) CPU utilization 87%; disk utilization 3%
Yes. CPU utilization is sufficiently high to leave the system in the current state. However,it is possible to increase the CPU utilization by a moderated increase in the degree of multiprogramming without causing the system to crash.
D) CPU utilization 87%; disk utilization 97%
No. If we increase the multiprogramming level, the system if it is not already crashing ,it will most probably crash.
Consider N processes sharing the CPU in a round-robin fashion (N>=2). Assume that each context switch takes S msec and that each time quantum is Q msec. For simplicity, assume that processes never block on any event and simply switch between the CPU and the ready queue.
In the following your answers should be functions of N, S and T.
A) Find the maximum value of Q such that no process will ever go more than T msec between starting times on the CPU?
T = time between starting times
T = NQ + NS
T = N ( Q + S )
Q = ( T / N ) - S
Maximum Q = ( T / N ) – S
B) Find the maximum value of Q such that no process will ever go more than T msecs between executing instructions on the CPU?
T = time between stop and start again
T = ( N – 1) Q + NS
Q = (T – NS)/(N - 1)
Maximum Q = (T – NS)/(N - 1)
