CPU Scheduling

CPU Scheduling is a key concept in computer multitasking, multiprocessing operating system and real-time operating system designs. Scheduling refers to the way processes are assigned to run on the available CPUs, since there are typically many more processes running than there are available CPUs. This assignment is carried out by software known as a scheduler and dispatcher.

The scheduler is concerned mainly with:

• CPU utilization - to keep the CPU as busy as possible.
• Throughput - number of processes that complete their execution per time unit.
• Turnaround - total time between submission of a process and its completion.
• Waiting time - amount of time a process has been waiting in the ready queue.
• Response time - amount of time it takes from when a request was submitted until the first response is produced.
• Fairness - Equal CPU time to each thread.

1.     First in first out

Also known as First­ Come, First ­Served (FCFS), it’s the simplest scheduling algorithm, FIFO simply queues processes in the order that they arrive in the ready queue.

• Since context switches only occur upon process termination, and no reorganization of the process queue is required, scheduling overhead is minimal.
• Throughput can be low, since long processes can hog the CPU
• Turnaround time, waiting time and response time can be low for the same reasons above
• No prioritization occurs, thus this system has trouble meeting process deadlines.
• The lack of prioritization does permit every process to eventually complete, hence no starvation.

2.     Shortest remaining time

Also known as Shortest­ Job­ First (SJF). With this strategy the scheduler arranges processes with the least estimated processing time remaining to be next in the queue. This requires advanced knowledge or estimations about the time required for a process to complete.

• If a shorter process arrives during another process' execution, the currently running process may be interrupted, dividing that process into two separate computing blocks. This creates excess overhead through additional context switching. The scheduler must also place each incoming process into a specific place in the queue, creating additional overhead.
• This algorithm is designed for maximum throughput in most scenarios.
• Waiting time and response time increase as the process' computational requirements increase. Since turnaround time is based on waiting time plus processing time, longer processes are significantly affected by this. Overall waiting time is smaller than FIFO, however since no process has to wait for the termination of the longest process.
• No particular attention is given to deadlines; the programmer can only attempt to make processes with deadlines as short as possible.
• Starvation is possible, especially in a busy system with many small processes being run.

3.     Round-robin scheduling

The scheduler assigns a fixed time unit per process, and cycles through them.

• RR scheduling involves extensive overhead, especially with a small time unit.
• Balanced throughput between FCFS and SJF, shorter jobs are completed faster than in FCFS and longer processes are completed faster than in SJF.
• Fastest average response time, waiting time is dependent on number of processes, and not average process length.
• Because of high waiting times, deadlines are rarely met in a pure RR system.
• Starvation can never occur, since no priority is given. Order of time unit allocation is based upon process arrival time, similar to FCFS.

Scheduling algorithm	CPU Utilization	Throughput	Turnaround time	Response time	Deadline handling	Starvation free
First In First Out	Low	Low	High	Low	No	Yes
Shortest Job First	Medium	High	Medium	Medium	No	No
Round-robin scheduling	High	Medium	Medium	High	No	Yes

PIYUSH THAKUR (CR)

POOJA SUTAR      (ACR)

IHM MUMBAI