5.1 Basic Concept of CPU Scheduling

Alternating sequence of CPU and I/O bursts.

CPU–I/O Burst Cycle

Process execution consists of a cycle of CPU execution and I/O wait.

Histogram of CPU-burst durations.

 

CPU Scheduler

 

Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the CPU scheduler, which selects a process from the processes in memory that are ready to execute and allocates the CPU to that process. 

A ready queue can be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered linked list.

The records in the queues are generally process control blocks (PCBs) of the processes.

 

 

 

 

Preemptive and Nonpreemptive Scheduling

 

CPU-scheduling decisions may take place under the following four circumstances:

1. When a process switches from the running state to the waiting state (for example, as the result of an I/O request or an invocation of wait() for the termination of a child process)
2. When a process switches from the running state to the ready state (for example, when an interrupt occurs)
3. When a process switches from the waiting state to the ready state (for example, at completion of I/O)
4. When a process terminates

1,4 => Nonpreemptive

2,3 => Preemptive

Under nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to the waiting state.

 

Preemptive scheduling can result in race conditions when data are shared among several processes.

Preemption also affects the design of the operating-system kernel.

 

Because interrupts can, by definition, occur at any time, and because they cannot always be ignored by the kernel, the sections of code affected by inter- rupts must be guarded from simultaneous use. The operating system needs to accept interrupts at almost all times. 

So that these sections of code are not accessed concurrently by several processes, they disable interrupts at entry and reenable interrupts at exit.

 

 

 

 

Dispatcher

The dispatcher is the module that gives control of the CPU’s core to the process selected by the CPU scheduler. 

 

• Switchingcontextfromoneprocesstoanother
• Switchingtousermode
• Jumpingtotheproperlocationintheuserprogramtoresumethatprogram

 

The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency.

The role of the dispatcher.

 

/proc file system to determine the number of context switches for a given process.

         cat /proc/2166/status

voluntary ctxt switches 150

non voluntary ctxt switches 8

 

Notice the distinction between voluntary and nonvoluntary context switches. A voluntary context switch occurs when a process has given up control of the CPU because it requires a resource that is currently unavailable (such as blocking for I/O.) A nonvoluntary context switch occurs when the CPUhas been taken away from a process, such as when its time slice has expired or it has been preempted by a higher-priority process.