CPU SCHEDULING

CPU Scheduling

CPU and I/O Burst Cycle

• The execution of a process consists of a cycle of CPU execution and I/O wait.

A process begins with a CPU burst, followed by an I/O burst, followed by another CPU burst and so on. The last CPU burst will end will a system request to terminate the execution.

• The CPU burst durations vary from process to process and computer to computer.

An I/O bound program has many very short CPU bursts.

A CPU bound program might have a few very long CPU bursts.

Types of Scheduling

The key to the multiprogramming is scheduling. There are four types of scheduling that an OS has to perform. These are:

• Long Term scheduling

>>>The long term scheduling determines which programs are admitted to the system for processing. Thus, it controls the level of multiprogramming.

>>>Once admitted, a job or a user program becomes a process and is added to the queue for the short term scheduling (in some cases added to a queue for medium term scheduling).

>>>Long term scheduling is performed when a new process is created.

>>>The criteria used for long-term scheduling may include first-come-first serve, priority, expected execution time, and I/O requirements.

• Medium-Term Scheduling

>>>The medium-term scheduling is a part of swapping function. This is a decision to add a process to those that are at least partially in main memory and therefore available for execution.

>>>The swapping-in decision is made on the need to manage the degree of multiprogramming and the memory requirements of the swapped-out process.

>>>Short-Term Scheduling

>>>A decision of which ready process to execute next is made in short-term scheduling.

>>>I/O Scheduling

>>>The decision as to which process’s pending I/O requests shall be handled by the available I/O device is made in I/O scheduling.

CPU Scheduler

• Whenever, the CPU becomes idle, the OS must select one of the processes in the ready-queue to be executed.

The selection process is carried out the short-term scheduler or CPU scheduler. The CPU scheduler selects a process from the ready queue and allocates the CPU to that process.

• CPU scheduling decisions may take place when a process:

1.The running process changes from running to waiting state (current CPU burst of that process is over).

2.The running process terminates

3. A waiting process becomes ready (new CPU burst of that process begins)

4. The current process switches from running to ready stat (e.g. because of timer interrupt).

• Scheduling under 1 and 2 is nonpreemptive.

Once a process is in the running state, it will continue until it terminates or blocks itself.

• Scheduling under 1 and 2 is preemptive.

Currently running process may be interrupted and moved to the Ready state by OS.

Allows for better service since any one process cannot monopolize the processor for very long

Dispatcher

• Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:

Switching context

Switching to user mode

Jumping to the proper location in the user program to restart that program

• Dispatch latency – time it takes for the dispatcher to stop one process and start another running.