CPU / Process Scheduling

CPU scheduling is the basis of multi-programmed operating systems. By switching the CPU among processes, the operating system can make the computer more productive. A multiprogramming operating system allows more than one process to be loaded into the executable memory at a time and for the loaded process to share the CPU using time-multiplexing.

Goals for Scheduling :
* Utilization/Efficiency: keep the CPU busy 100% of the time with useful work.
* Throughput: maximize the number of jobs processed per hour.
* Turnaround time: from the time of submission to the time of completion, minimize the time batch users must wait for output.
* Waiting time: Minimize the waiting time i.e. sum of times spent in ready queue.
* Response Time: time from submission till the first response is produced, minimize response time for interactive users.
* Fairness: make sure each process gets a fair share of the CPU.

Some goals can be met by incorporating a notion of priority into a “base” scheduling discipline. Each job in the ready pool has an associated priority value; the scheduler favors jobs with higher priority values.
External priority values:
• imposed on the system from outside.
• reflect external preferences for particular users or tasks.
“All jobs are equal, but some jobs are more equal than others.”
• Example: Unix nice system call to lower priority of a task.
• Example: Urgent tasks in a real-time process control system.

Internal priority: system adjusts priority values internally as as an implementation technique within the scheduler. It improves fairness, resource utilization, freedom from starvation.
• drop priority of jobs consuming more than their share
• boost jobs that already hold resources that are in demand
e.g., internal sleep primitive in Unix kernels
• boost jobs that have starved in the recent past
• typically a continuous, dynamic, readjustment in response to observed conditions and events may be visible and controllable to other parts of the system.

Scheduling policies may be preemptive or non-preemptive.
* Non-Preemptive: Non-preemptive algorithms are designed so that once a process enters the running state(is allowed a process), it is not removed from the processor until it has completed its service time ( or it explicitly yields the processor).
* Preemptive: Preemptive algorithms are driven by the notion of prioritized computation. The process with the highest priority should always be the one currently using the processor. If a process is currently using the processor and a new process with a higher priority enters, the ready list, the process on the processor should be removed and returned to the ready list until it is once again the highest-priority process in the system.

First-Come-First-Served (FCFS) Scheduling

First-Come-First-Served algorithm is the simplest scheduling algorithm is the simplest scheduling algorithm. Processes are dispatched according to their arrival time on the ready queue. Being a non-preemptive discipline, once a process has a CPU, it runs to completion. The FCFS scheduling is fair in the formal sense or human sense of fairness but it is unfair in the sense that long jobs make short jobs wait and unimportant jobs make important jobs wait.
FCFS is more predictable than most of other schemes since it offers time. FCFS scheme is not useful in scheduling interactive users because it cannot guarantee good response time. The code for FCFS scheduling is simple to write and understand. One of the major drawback of this scheme is that the average time is often quite long.

CHARACTERISTICS :
o Non-preemptive.
o Ready queue is a FIFO queue.
o Jobs arriving are placed at the end of queue.
o Dispatcher selects first job in queue and this job runs to completion of CPU burst.

Advantages:
- Simple.
- Low overhead.
Disadvantages:
- Inappropriate for interactive systems.
- Large fluctuations in average turnaround time are possible.

Example :
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3.
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17

Suppose that the processes arrive in the order P2 , P3 , P1.
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than previous case.