Skip to content

Batch Job Scheduling Algorithms

According to the nature of the operating system, job scheduling algorithms can be divided into the following two types:

Single-channel batch processing job scheduling algorithm

  • Definition: In a single-channel batch processing system, only one job is loaded and run at a time, and the job occupies all system resources during execution. The system will schedule the next job only after the job is executed.
  • Features:
  • The job occupies all computer resources during execution.
  • The system resource utilization rate is low, especially when the job performs I/O operations, the CPU will be idle waiting.
  • Usually used in early computer systems or environments with limited resources.

Common algorithms:

First Come First Served Algorithm (FCFS)

  • Definition: Each scheduling selects jobs according to the order in which the jobs enter the "input well" backup job queue, and the jobs that enter the queue first are preferentially transferred to the main memory, resources are allocated, processes are created, and they are placed in the process ready queue to run.
  • Features: FCFS is a non-preemptive scheduling algorithm, which is easy to implement and embodies fairness, but is not efficient. It only considers waiting time and does not consider the length of job service time.
  • Advantages: Simple, easy to implement, and guarantees fairness.
  • Disadvantages: It is not good for short jobs, but good for long jobs and CPU-busy jobs, and not good for I/O-busy jobs. Therefore, FCFS is not often used as the main scheduling algorithm.

Short Job First (SJF)

  • Definition: When scheduling, the length of job running time is used as the standard, and the job with the shortest running time is selected from the backup job queue and loaded into the main memory for operation.
  • Features: Short jobs are selected first, which helps to improve the overall response efficiency of the system.

Highest Response Ratio First (HRRF)

  • Definition: It takes into account both the waiting time and the running time of jobs, calculates the response ratio of all jobs, and selects the job with the highest response ratio to be loaded into the main memory for operation.
  • Response ratio formula: Response ratio = (job waiting time + job running time) / job running time
  • Features: Comprehensively consider waiting time and running time to ensure fairness and efficiency.

Priority number scheduling algorithm

  • Definition: Determine a priority number for each job, arrange jobs into multiple queues according to different priority numbers, and prioritize the jobs with the highest priority number and sufficient resources to load into the main memory for operation.
  • Priority number determination principle:
  • Give higher priority to jobs with urgent time requirements.
  • Give higher priority to jobs with large I/O volume, and lower priority to jobs with large CPU volume.

Classification scheduling algorithm (balanced scheduling algorithm)

  • Definition: According to the system operation status and the job's demand for resources, first classify the jobs, and then the scheduler selects jobs from different job classes in turn, so as to make jobs with different resources execute at the same time as much as possible to ensure balanced resource utilization.

Multi-tasking batch job scheduling algorithm

  • Definition: In a multi-tasking batch processing system, the system supports multi-tasking design, allowing multiple jobs to be loaded into memory at the same time, so that when a job is waiting for I/O operations, the CPU can schedule other jobs to execute, thereby improving the resource utilization of the system.
  • Features:
  • Through multi-tasking design, the system can process multiple jobs concurrently, improving resource utilization and system throughput.
  • Multiple jobs can be run at the same time, each job uses CPU and I/O resources separately.

  • Suitable for modern multi-tasking operating systems, it can significantly improve system performance.

  • Common algorithms:

  • High-level scheduling (job scheduling):
  • Responsible for selecting appropriate jobs from the backup job queue to load into memory to improve system throughput.
  • Common strategies include first-come-first-served, priority scheduling, scheduling by job size, etc.
  • Low-level scheduling (process scheduling):
  • Responsible for selecting the next process to be executed in the ready process queue in memory.
  • Common algorithms include time slice rotation, shortest remaining time priority, priority scheduling, etc.
  • Intermediate scheduling (memory scheduling):
  • Use swapping technology to move some jobs to external memory when memory space is insufficient to free up memory space.
  • Responsible for dynamically adjusting the number of jobs in memory and balancing system load.

Comparison between the two

Features Single-channel batch processing job scheduling algorithm Multi-channel batch processing job scheduling algorithm
Concurrency Not supported, only one job is executed at a time Supported, multiple jobs can be executed concurrently
Resource utilization Low, CPU is often idle waiting High, make full use of CPU and I/O
System complexity Simple, fewer scheduling strategies Complex, requiring high-level, medium-level and low-level scheduling
Applicable scenarios Scenarios with limited resources and small tasks Modern multi-tasking, multi-user systems
Typical algorithms First come first served, short job priority, highest response ratio Time slice rotation, priority scheduling, job scheduling

Summary

  • Single-channel batch processing job scheduling algorithm Suitable for environments with limited resources, relatively simple, but low resource utilization, not suitable for modern multi-tasking systems
  • Multi-process batch job scheduling algorithm can make full use of system resources and improve the utilization of CPU and I/O devices. It is a standard design pattern of modern operating systems.