Bo2SS

Course Content#

Process Scheduling#

• Process scheduling is a kernel subsystem that users cannot control.
• The main task of process scheduling is to determine which ready process should run first.
• Ready processes are non-blocking processes that are ready to run and do not need to wait for blocking.
• Blocking processes are sleeping processes [not using CPU] that need to be awakened by the kernel.

Three-State Model#

• Blocked, Ready, Running
• 
• Blocked processes do not occupy system resources; ready processes need to wait for kernel scheduling; running processes block when there is an IO request or waiting for an event.

👉 Five-State Model

• 
• Added new and terminated states.

From Single Task to Multi-Task#

• DOS is a single-task operating system that only runs one process at a time.
  • Processes run in an interleaved manner, similar to multitasking.
• Multiprocessors can achieve true parallelism.
  • Concurrency vs Parallelism
  • Concurrency: Many tasks are performed within a time period.
  • Parallelism: As many tasks can run simultaneously as there are CPUs.
• The core of scheduling: which process to run and for how long.

Time Slice#

Strongly affects the global behavior and performance of the system.

• Too long
  • 👍: Improves system throughput and overall performance.
  • ×: Reduces concurrent execution; users experience noticeable delay [decreased responsiveness, long scheduling intervals due to excessive applications].
• Too short
  • 👍: Improves interactive performance.
  • ×: A lot of time is spent on scheduling; the performance improvement brought by temporal locality is greatly reduced.
    • Temporal locality: Cache, memory [cache is gradually built over time].
    • Spatial locality: Preparing data for adjacent space in advance.
    • Implies learning and prediction.
• Therefore, it is difficult to determine the length of the time slice. The solution is to simply not use time slices and instead use a completely fair scheduling algorithm.
  • The system adjusts based on the ready queue and priority.
  • The allocation of scheduling time and priority is essentially to better serve the user and is not unfair.
  • See the following section for details on the Completely Fair Scheduler.

Processor-Bound and IO-Bound Processes#

Based on the characteristics of how processes use the CPU, it depends on whether the processor or IO is used more.

• Processor-bound
  • [Processes that consume the entire available time slice]
  • Requires a large amount of CPU resources and consumes all the CPU allocated by the scheduler.
  • For example: while(1);, it is easy to reach 100% CPU usage.
  • Requirements for time slices
    • Expect longer time slices to maximize cache hits and complete tasks as soon as possible [without wasting resources].
• IO-bound
  • [Processes that spend most of their time in a blocked state or waiting for resources]
  • Often blocked on file IO operations: files, networks, keyboards, mice [such as listening to music, typing]; or do nothing except request kernel to perform IO operations [such as cp].
  • Requirements for time slices
    • Need shorter time slices, scheduled as quickly as possible, with a seamless feeling.
    • The process will only run for a very short time, then block on kernel resources; interrupts are used.

Scheduler Classification#

Cooperative Scheduler#

[Non-interventional, not practical]

• The process will continue to run until it ends on its own.
• The operating system does not intervene.

Preemptive Scheduler#

[Time slice-based]

• The kernel allocates time slices to processes. When the time slice is used up, the process is suspended [without using any resources] and another process is executed.
  • When there are no other ready processes, the kernel reallocates time slices to processes that have already been executed.
• The scheduler arranges the order and duration of process execution.
• [PS]
  • Enters the ready queue in the new state and exits the ready queue in the terminated state [five-state model].
  • Considers priority, and all processes have a chance to be executed.

Completely Fair Scheduler#

[Non-time slice-based]

CFS: Completely Fair Scheduler

• Given N processes, each process is allocated 1 / N of the processor time.
• Priority and weight
  • The higher the priority, the smaller the value, and the larger the weight.
  • The default priority is 0 and the weight is 1.
• Target latency: fixed scheduling period
• Minimum granularity: to avoid too small target latency resulting in very short running time for each process

👉 Fair Quota

Tips#

• I am a CPU: This World is Slow! Dead! - WeChat Official Account
  • Interesting article, understanding the speed gap between CPUs and hard drives, networks