Events That Trigger Scheduling

A Process Voluntarily Gives Up the CPU

1. Normal process termination: after completing all tasks, a process exits, such as by calling the exit() system call. The CPU becomes idle, so the scheduler needs to choose the next process from the ready queue.
2. Process blocking: a process enters the blocked state because it needs to wait for a resource, such as I/O, a semaphore, or a lock, and voluntarily releases the CPU.
3. Voluntary yielding: some systems support system calls such as yield() that let a process voluntarily give up the CPU.

The System Forcibly Takes the CPU

1. Arrival of a higher-priority process: a new process enters the ready queue and has a higher priority than the currently running process.
2. Time slice exhaustion: in round-robin scheduling, the current process uses up its time slice, such as 10ms, and is forcibly moved to the end of the ready queue, triggering scheduling.

Hardware Interrupts

1. Clock interrupt: the operating system periodically generates clock interrupts through a timer, and the kernel checks whether scheduling is needed in the interrupt handler.
2. I/O interrupt: after an I/O device completes data transfer, it generates an interrupt signal. The kernel checks in the interrupt handler whether any blocked process can be awakened and scheduled.

Scheduling Algorithm Evaluation Metrics

Common Scheduling Algorithms

FCFS, SJF

Batch systems focus on improving throughput and reducing average turnaround time. Their processes are mostly background tasks without real-time interaction needs, so they commonly use these algorithms:

• FCFS, First Come First Served: in the RQ (Ready Queue), schedule processes by the order in which they enter the queue.
• SJF, Shortest Job First: choose the job with the shortest estimated running time.

PS, RR, MLFQ

Interactive systems, such as Windows and Linux desktops, focus on shortening response time and preserving user experience. They need frequent process switching and commonly use these preemptive algorithms:

• PS, Priority Scheduling: priority^[1] scheduling algorithm.
  • HRRN, High Response Ratio Next: a compromise between FCFS and SJF that uses response ratio^[2] as the priority criterion.
• RR, Round Robin: assign the CPU to the process at the front of the ready queue. After the process runs for one time slice, a timer interrupt stops it and moves it to the end of the queue, then assigns the CPU to the new front process for another time slice.
• MLQ, MultiLevel Queue: divide running processes into different ready queues according to their characteristics, and assign different scheduling algorithms to each queue.
  • MLFQ, MultiLevel Feedback Queue: assigns different priorities to queues and gives high-priority queues shorter time slices. After a process enters memory, it is first placed at the end of the first queue. When it runs, if it does not finish within one time slice, it is demoted to the next queue. The OS schedules processes in higher-priority queues first, and only schedules RQ₁ when RQ₀ is empty, and so on.

EDF, LLF

• EDF, Earliest Deadline First: determines task priority according to deadlines. The earlier the deadline, the higher the priority.
• LLF, Least Laxity First: sorts by laxity^[3]. The task with the smallest laxity is placed at the front of the queue, and the scheduler always chooses the front task in the ready queue. When a task is running, scheduling only occurs when a waiting task’s laxity becomes 0; otherwise scheduling does not occur.