Prerequisite Knowledge

Difference Between Preemptive and Non-Preemptive Scheduling?

Non-Preemptive Scheduling: Once a process starts executing, the operating system will not allocate the CPU to other processes until the process voluntarily releases it.

Preemptive Scheduling: The operating system can forcibly pause the execution of a running process and allocate the CPU to another process. This means that even if a process has not completed its execution, the operating system can interrupt its running.

Common Process Scheduling Algorithms

First-Come, First-Served Scheduling Algorithm

• Non-Preemptive (FCFS, First Come First Served)
• Processes are queued in the order they arrive, executing the process that entered the queue first until it completes or blocks, then proceeding to the next process in line.
• Disadvantage: If a long job is queued behind many short jobs, the long job will take a long time to execute, causing short jobs to wait longer, which is not favorable for short jobs.

Shortest Job First Scheduling Algorithm

• Non-Preemptive (SJF, Shortest Job First)
• Shorter jobs are prioritized, which helps improve system throughput.
• Disadvantage: Not favorable for long jobs; when there are many short jobs, long jobs may not get executed.

Highest Response Ratio Next Scheduling Algorithm

• Non-Preemptive (HRRN, Highest Response Ratio Next)
• This algorithm balances short and long jobs, calculating the priority/response ratio of each job during scheduling.

• If thewaiting times are the same, the shorter service time has a higher response ratio, thusshort jobs are executed first.
• If the processes have the samerequired service time, the longer waiting time results in a higher response ratio, thuslong jobs are executed first.
• Disadvantage: Requires calculating priority each time, increasing system overhead.

Round-Robin Scheduling Algorithm

• Preemptive (RR, Round-Robin)
• Uses time slices to allocate CPU time, allowing each process to receive response within a certain time interval, treating each thread equally.
• Time Slice: Each process is allocated a time period to run.
• If the time slice is too short, it will lead to frequent context switching, increasing system overhead.
• If the time slice is too long, it is not favorable for short jobs, leading to long response times for short jobs.
• Typically, the time slice is set between 20ms to 50ms.

Priority Scheduling Algorithm

• IncludesPreemptive and Non-Preemptive (Priority Scheduling)
• Generally, scheduling is done based on process priority.
• Processes are scheduled based on urgency, usually dynamically adjusting the priority; if execution time is too long, the priority is lowered; if waiting time is too long, the priority is increased.
• Non-Preemptive: When a higher priority process appears in the ready queue, the current process completes before selecting the higher priority process.
• Preemptive: When a higher priority process appears in the ready queue, the current process is suspended, and the higher priority process is scheduled to run.
• Disadvantage: Lower priority processes may never get executed.

Multilevel Feedback Queue Scheduling Algorithm

• Preemptive (Multilevel Feedback Queue)
• Multilevel: Indicates multiple queues, with priority decreasing from high to low, and shorter time slices for higher priority.
• Feedback: If a new process joins a higher priority queue, the currently running process is immediately stopped to allow the higher priority process to run.
• Multiple queues are set up, arranged by priority, with shorter time slices for higher priority queues.
• In the same queue, processes are scheduled using the round-robin algorithm.
• New processes will be queued in the higher priority queue; if not completed within the allocated time slice, they will switch to the next lower priority queue.
• Only when the high priority queue is empty will the next lower priority queue be called.
• When a process enters the high priority queue, the currently running process is stopped, placed at the end of its queue, and the high priority process is run.
• This algorithm accommodates both long and short jobs, providing good response times for both.