Two-level scheduling: Difference between revisions

Revision as of 18:21, 1 November 2004

Revision as of 02:30, 10 November 2004

Line 1:

'''Two-level scheduling''' is a [[Computer science]] term to describe a method to more efficiently doperform process [[scheduling]] that involves [[swapped out]] [[process (computing)|processes]]es.

Consider this problem; A system contain 50 running processes all with equal priority. However, the system's [[memory]] can only hold 10 processes in memory simultaneously. Therefore, there will always be 40 processes swapped out written on [[virtual memory]] on the [[harddisk]]. The time taken to swap out and swap in a process is 50 ms respectively.

With straightforward [[Round-robin scheduling]], at every time a [[context- switch]] occurs, there would be an 80% probability (40/50, if it chooses randomly among the processes) that a process would need to be swapped in. If that occurs, then obviously a process also need to be swapped out. Swapping in and out of memory is costly, and the scheduler would waste much of its time doing unneeded swaps.

That is where two-level scheduling enters the picture. It uses two different schedulers, one '''lower-level scheduler''' which can only select among those processes in memory to run. That scheduler could be a Round-robin scheduler. The other scheduler is the '''higher-level scheduler''' whoswhose only concern is to swap in and swap out processes from memory. It does its scheduling much less often than the lower-level scheduler since swapping takes so much time.

Thus, the higher-level scheduler selects among those processes in memory that hashave ranrun for a long time and swaps them out. They are replaced with processes on disk that hashave not ranrun for a long time. Exactly how it selects processes is up to the implementation of the higher-level scheduler. A compromise has to be made involving the following variables:

* [[response time]]: A process should not be swapped out for too long. Then some other process (or the user!) will have to wait needlessy long. If this variable is not considered [[starvation]] may occur and a process may not complete at all.

Line 13:

* Priority: The higher the priority of the process, the longer it should stay in memory so that it completes faster.

== Linux ==

[[Linux]] does not use two-level scheduling. <!-- the reason why to be written -->

'''References''': [[Andrew S. Tanenbaum|Tanenbaum]], [[Woodhull]], ''Operating Systems: Design and Implementation'', p.92