Basic Concepts:
CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among processes, the operating system can make the computer more productive. In a single-processor system, only one process can run at a time; any others must wait until the CPU is free and can be rescheduled. The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization. A process is executed until it must wait, typically for the completion of some I/O request. In a simple computer system, the CPU then just sits idle. Almost all computer resources are scheduled before use. The CPU is, of course, one of the primary computer resources.
CPU Scheduling: is the process used to maximize the CPU utilization.CPU Scheduling is done in following circumstances: When process switches from the running stage to waiting state. When process switches from the running stage to ready state. When process switches from the waiting stage to ready state.
CPU-I/O Burst Cycle:
The success of CPU scheduling depends on an observed property of processes: Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on. Eventually, the final CPU burst ends with a system request to terminate execution.
An I/O-bound program typically has many short CPU bursts. A CPU-bound program might have a few long CPU bursts. This distribution can be important in the selection of an appropriate CPU- cheduling algorithm.
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 short-term scheduler (or CPU scheduler). The scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.
- When a process switches from the running state to the waiting state.
- When a process switches from the running state to the ready state.
- When a process switches from the waiting state to the ready state.
- When a process terminates.
There are two types of scheduling 1 Preemptive or 2 Non-Preemptive Scheduling.
Preemptive Scheduling:
Tasks are usually assigned with priorities. At times it is necessary to run a certain task that has a higher priority before another task although it is running. Therefore, the running task is interrupted for some time and resumed later when the priority task has finished its execution. This is called preemptive scheduling. 2 and 3 is preemptive scheduling.
Non-Preemptive Scheduling:
When a process enters the state of running, the state of that process is not deleted from the scheduler until it finishes its service time. 1 and 4 is non-preemptive.
Dispatcher:
Another component involved in the CPU-scheduling function is the dispatcher. The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following:
- Switching context.
- Switching to user mode.
- Jumping to the proper location in the user program to restart that program.
Dispatch latency:
During the context switches, the processor is virtually idle for a fraction of time, thus unnecessary context switches should be avoided. The time it takes for the dispatcher to stop one process and start another is known as the dispatch latency.
Scheduling Criteria:
Different CPU scheduling algorithms have different properties, and the choice of a particular algorithm may favor one class of processes over another. Many criteria have been suggested for comparing CPU scheduling algorithms. The criteria include the following:
- CPU utilization: The CPU must be busy as much as possible to perform different activities. The percentage of time, the CPU is executing a process may range from 0 to 100 percent. CPU utilization is very important in real time and multiprogramming system.
- Throughput: The number of process executed by the system in a specific period of time this time unit is called through put. For long process this rate may be one process per minute. Similarly for short process, it may be 100 processes per minute.
- Turnaround time: Is the amount of time to execute one process. The turnaround time is computed by subtracting the time, when the process was created from the time is terminated.
- Waiting time: Waiting time represents the average period of time; a process spends waiting in the ready queue to get a chance for execution.
- Response time: Response time represents the average time take by the system to start responding to user request. The response time is considered in interactive systems.