Tuesday, 24 May 2016

Long and medium term scheduling os

Types of scheduling - Long and medium term scheduling

In single task operating systems the issue of scheduling is trivial: after the system has set up the execution environment of a process, CPU control is given to it until the process itself exits. In a pun, the system is not operating at all during the program's execution, save for providing services through subroutine calls. It's only with multi-tasking operating systems that scheduling becomes a top entry in a designer's agenda.

In many multitasking systems the processor scheduling subsystem operates on three levels, differentiated by the time scale at which they perform their operations. In this sense we differentiate among:

Long term scheduling: which determines which programs are admitted to the system for execution and when, and which ones should be exited.

Medium term scheduling: which determines when processes are to be suspended and resumed;
Short term scheduling (or dispatching): which determines which of the ready processes can have CPU resources, and for how long.
Taking into account the states of a process, and the time scale at which state transition occur, we can immediately recognise that

dispatching affects processes
the medium term scheduling affects processes
the long term scheduling affects processes
Long term scheduling obviously controls the degree of multiprogramming in multitasking systems, following certain policies to decide whether the system can honour a new job submission or, if more than one job is submitted, which of them should be selected. The need for some form of compromise between degree of multiprogramming and throughput seems evident, especially when one considers interactive systems. The higher the number of processes, in fact, the smaller the time each of them may control CPU for, if a fair share of responsiveness is to be given to all processes. Moreover we have already seen that a too high number of processes causes waste of CPU time for system housekeeping chores (trashing in virtual memory systems is a particularly nasty example of this). However, the number of active processes should be high enough to keep the CPU busy servicing the payload (i.e. the user processes) as much as possible, by ensuring that - on average - there always be a sufficient number of processes not waiting for I/O.

Simple policies for long term scheduling are

Simple First Come First Served (FCFS): it's essentially a FIFO scheme. All job requests (e.g. a submission of a batch program, or an user trying to log in in a time shared system) are honoured up to a fixed system load limit, further requests being refused tout court, or enqueued for later processing.
Priority schemes. Note that in the context of long term scheduling ``priority'' has a different meaning than in dispatching: here it affects the choice of a program to be entered the system as a process, there the choice of which ready process process should be executed.
Medium term scheduling is essentially concerned with memory management, hence it's very often designed as a part of the memory management subsystem of an OS. Its efficient interaction with the short term scheduler is essential for system performances, especially in virtual memory systems. This is the reason why in paged system the pager process is usually run at a very high (dispatching) priority level.

Courtesy : http://www.cim.mcgill.ca/~franco/OpSys-304-427/lecture-notes/node38.html