Skip to content
Search

Scheduling

lastmod 2025-02-02created 2017-01-302 edits

Scheduling is an operating system technique that makes multiprogramming possible. By appropriately allocating resources such as the CPU to processes, the operating system can improve system performance.

Types

  • Long-term scheduling
  • Medium-term scheduling
  • Short-term scheduling

Levels

Level 1 scheduling
Also called job scheduling. Decides which jobs are allowed to actually use the resources in the system first. Because it admits jobs into the system, it is also called admission scheduling.
Level 2 scheduling
Decides which processes get to occupy the CPU first. It controls the short-term load on the system by suspending and reactivating processes, which lets the system run appropriately. It acts as a buffer between job admission (level 1) and CPU allocation (level 3).
Level 3 scheduling
Decides which process to allocate the CPU to when it becomes available.

Non-preemptive and preemptive

Depending on when scheduling is applied, it can be divided into two kinds: non-preemptive and preemptive. Non-preemptive scheduling runs only in situations 1 and 4 of the decision points above, while preemptive scheduling runs in all situations from 1 to 4.

Non-preemptive Scheduling
Once a process is allocated the CPU, it is guaranteed to keep running until it terminates or voluntarily stops because of an I/O request. It is fair because processes are handled in order, response time can be predicted regardless of which process comes next, the scheduler is invoked less often than with preemption, and there is less overhead from context switching. It suits batch processing systems. A drawback is that throughput can drop, since one process with a long CPU time can keep many processes with short CPU times waiting for a long time.
Preemptive Scheduling
Even while a process has been allocated the CPU and is running, another process can stop the running process and forcibly take over the CPU. CPU time can be given equally to all processes. It suits interactive time-sharing systems that require fast response times, and can control urgent processors. In this approach, "the operating system preempts the processor resources" and distributes them based on certain criteria when each process makes a request.

Static scheduling and dynamic scheduling

Depending on whether process priorities change, scheduling can be divided into static scheduling and dynamic scheduling.

  • Static Scheduling: The priority given to a process does not change. Also called fixed-priority scheduling.
  • Dynamic Scheduling: Process priorities change during scheduling. Also called variable-priority scheduling.

Scheduling algorithms

When implementing a scheduling algorithm, some of the various goals of scheduling may conflict with each other. Writing an algorithm takes into account whether the system is batch or interactive, the ratio of CPU to I/O usage, whether priorities are assigned and, if so, the degree of preemption for the process, and the page fault rate. Scheduling algorithms include the following.

  • Non-preemptive process scheduling
    • FCFS scheduling (First Come First Served Scheduling)
    • SJF scheduling (Shortest Job First Scheduling)
    • HRRN scheduling (Highest Response Ratio Next Scheduling)
  • Preemptive process scheduling
    • RR scheduling (Round Robin Scheduling)
    • SRTF scheduling (Shortest Remaining-Time First Scheduling)
    • Multilevel Queue Scheduling
    • Multilevel Feedback Queue Scheduling
    • RM scheduling (Rate Monotonic Scheduling)
    • EDF scheduling (Earliest Deadline First Scheduling)

Evaluation criteria

Scheduling algorithms can be evaluated by the following criteria.

  • CPU Utilization: The proportion of total system time during which the CPU is processing work.
  • Throughput: The number of processes the CPU completes per unit of time.
  • Response Time: In an interactive system, the time from a request until the response starts to arrive.
  • Waiting Time: The total time a process spends waiting in the ready queue.
  • Turnaround Time: The time it takes a process from start to finish.

See also

Favorite site

author Zer0 sitemap