How Do Preemptive CPU Scheduling Algorithms Work?

TL;DR

Preemptive scheduling can interrupt a running process, return it to the ready queue, and give the CPU to another process, while non-preemptive scheduling lets the selected process complete its burst time before choosing another. Preemption can improve responsiveness through a time quantum and can also occur when a higher-priority or shorter process should run.

Transcript

Hello friends, Welcome to Gate Smashers The topic is scheduling algorithm in operating system So scheduling algorithm is a way or selecting a process from ready queue and put it in the CPU Means, according to the degree of multi programming, we tried to keep multiple processes in the ready queue And ready queue lies in the RAM Means we uses differe... Read More

Key Insights

• A scheduling algorithm is a method for selecting one process from the ready queue in RAM and assigning that process to the CPU for execution according to a defined criterion.
• A uniprocessor system executes only one process at a time, even when multiple processes are present in the ready queue, so scheduling determines which waiting process receives the CPU.
• Preemptive scheduling is a method that stops a running process before completion, places it back in the ready queue, and allows another selected process to use the CPU.
• Non-preemptive scheduling is a method that lets a selected process complete its entire burst time before the scheduler assigns the CPU to a new process.
• A time quantum is a predetermined execution interval that limits how long a process uses the CPU before it returns to the ready queue and another process receives a turn.
• The key benefit of time-based preemption is responsiveness, because processes near the end of the ready queue can receive a turn earlier instead of waiting for every preceding process to finish completely.
• Priority-based preemption occurs when a higher-priority process arrives while another process is running, causing the current process to wait in the ready queue while the higher-priority process executes.
• Preemptive algorithms include SRTF, LRTF, round robin, and priority scheduling, while non-preemptive algorithms include FCFS, shortest job first, longest job first, highest response ratio, multilevel queue, and multilevel feedback queue.

Questions & Answers

Q: What is a CPU scheduling algorithm in an operating system?

A CPU scheduling algorithm selects a process from the ready queue and assigns it to the CPU for execution. The ready queue is located in RAM and can contain multiple processes. In a uniprocessor system, only one process can execute at a time, so the algorithm determines which waiting process should run and for how long.

Q: What is the difference between preemptive and non-preemptive scheduling?

Preemptive scheduling allows the operating system to stop a process while it is still running, place it back in the ready queue, and give the CPU to another process. Non-preemptive scheduling lets the selected process finish its complete burst time first. After that process terminates, the scheduler selects a new process from the ready queue.

Q: How does a time quantum work in preemptive scheduling?

A time quantum defines how long a process may use the CPU during one turn. If a process needs more time than the assigned quantum, it runs only for that interval and then returns to the ready queue. Another process receives the CPU, and the interrupted process can continue when its next turn arrives.

Q: Why does preemptive scheduling improve responsiveness?

Preemptive scheduling improves responsiveness by dividing CPU access into limited turns instead of allowing each process to finish before the next one begins. In the classroom example, answering only two questions per student lets the last student receive attention sooner. Each student later receives another turn until all remaining questions have been answered.

Q: When can priority cause a running process to be preempted?

Priority can cause preemption when a higher-priority process arrives while another process is already running. The scheduler stops the current process, returns it to the ready queue, and assigns the CPU to the higher-priority process. The interrupted process remains available for execution later rather than being treated as completed or terminated.

Q: How does process length influence CPU scheduling decisions?

Process length can influence scheduling when one process requires less execution time than another. The scheduler may select the shorter process first so it can finish quickly, even if another process requires substantially more time. The classroom analogy compares a student with one question to another student with ten questions, with the shorter request handled first.

Q: Which algorithms use preemptive CPU scheduling?

The preemptive algorithms identified are shortest remaining time first, abbreviated SRTF, longest remaining time first, abbreviated LRTF, round robin, and priority scheduling. The transcript particularly emphasizes SRTF and round robin because questions about them frequently appear in GATE, UGC NET, college examinations, entrance examinations, and midterm examinations.

Q: Which algorithms use non-preemptive CPU scheduling?

The non-preemptive algorithms listed are first come first serve, abbreviated FCFS, shortest job first, longest job first, highest response ratio, multilevel queue, and multilevel feedback queue. Highest response ratio uses a formula to calculate a response ratio and decide which process should execute first. Priority scheduling can also be configured as non-preemptive.

Summary & Key Takeaways

• A scheduling algorithm selects a process from the ready queue in RAM and assigns it to the CPU. In a uniprocessor system, only one process can execute at a time, so the scheduler needs criteria for deciding which process runs, when it runs, and how long it receives the CPU.

• Preemptive scheduling interrupts a process while it is running, places it back in the ready queue, and selects another process for execution. A time quantum can limit each turn, allowing processes farther back in the queue to receive CPU time sooner and improving the responsiveness experienced across the waiting processes.

• Non-preemptive scheduling allows a selected process to complete its entire burst time before another process receives the CPU. The discussed preemptive algorithms include SRTF, LRTF, round robin, and priority, while non-preemptive examples include FCFS, shortest job first, longest job first, highest response ratio, and multilevel queue approaches.