CPU Scheduling Levels, Objectives, Criteria and Algorithms

Scheduling Levels

• Short-term plan: the short-term processor assignment, CPU-resident and rapid.
• Medium-term plan: the swapping of processes, suspending and resuming them.
• Long-term plan: the creation of process jobs.

Scheduling Objectives

• Fairness
• Maximum CPU utilization
• Maximum execution capacity
• Predictability for interactive users
• Balance and avoidance of overload
• Minimization of the use of resources
• Security of priorities

Scheduling Criteria

• CPU utilization: the percentage of time the CPU is busy.
• Throughput: the number of processes completed per unit of time.
• Turnaround time: the time from submission until a process completes.
• Waiting time: the total time a process spends waiting in the ready queue.
• Response time: the time from a request until the first response is produced.
• Service ratio: the ratio between execution time and waiting time.

Scheduling Policies

• Preemptive policies: a running process can be interrupted and moved to a queue, allowing other processes to use the processor.
• Non-preemptive policies: a process keeps the CPU until it terminates or blocks.

Scheduling Algorithms

• FCFS or FIFO: service in order of arrival.
• Round Robin (RR): time-sharing among processes.
• SJF: the shortest job goes first.
• SRT: the shortest remaining time goes first.
• Priority: based on priorities.
• Multilevel feedback queues with or without feedback.

FCFS: first come, first served.

The dispatcher executes the first process in the ready queue until it terminates or blocks. It is non-preemptive. When the current process ceases execution, the process selected is the oldest one in the queue. Processes that charge I/O and processes that are CPU-bound are handled in this way. The waiting time can be long.

Round Robin (RR)

• It is designed for time-sharing systems.
• Each process receives a time slice called a quantum (q).
• At the end of the quantum, the process is preempted and moved to the end of the ready queue.
• The ready queue is handled as a FIFO queue.
• The value of q changes the behavior of the system.
• It penalizes I/O-bound processes less than CPU-bound ones.

SJF: the shortest job first.

It can be preemptive or non-preemptive, with the same objectives as RR. It requires knowing the execution time of each process in advance, which is difficult without experience. It gives good waiting times for short processes and is predictable.

SRT: shortest remaining time first.

It is the preemptive variant of SJF: when a new process arrives with a shorter remaining time than the running one, the running process is preempted. It is very efficient, but it needs to know the remaining time of each process.

Priorities

• Priorities are assigned according to the urgency and resource needs of each process.
• Assignment can be static or dynamic.
• Static priorities cannot be modified; dynamic priorities can be modified during execution.

Priority Algorithms

• Assign the processor to the process with the highest priority.
• For equal priorities, use FCFS.
• SRN is an algorithm with priority inversely proportional to the remaining time.
• Main problem: starvation.
• Solution: aging.
• It can be preemptive or non-preemptive.

Multiple Queues

• Processes are assigned to different queues depending on their needs and type.
• Scheduling between queues: fixed priority, preemptive or not.
• Scheduling within queues: RR or FCFS.

Multilevel Feedback Queues

• Feedback: processes can change queues during execution (dynamic priority).
• Feedback case: a process moves to a lower-priority queue after several quanta (the quantum may vary).
• CPU-bound processes are placed in lower-priority queues, while I/O-bound processes stay in higher-priority queues.
• The algorithm used is usually a combination of algorithms.