CPU Scheduler

  1. CPU调度器从进程ready队列中选择，并为他们分配CPU资源

  2. 当进程处于以下情况时，会发生CPU调度：

    1. 从running切换到waiting状态，如等待I/O
    2. 从running切换到ready状态，如中断发生
    3. 从waiting切换到ready状态，如I/O完成
    4. 进程结束

  3. 只存在1和4的调度是非抢占式的

    一旦CPU被分配给一个进程，这个进程会保持它直到进程结束或等待I/O

    nonpreemptive scheduling，也叫cooperative scheduling

  4. 包含2和3的调度是抢占式的

    抢占式调度需要硬件支持，如timer

    需要同步原语 (synchronization primitives)

  5. 是否需要同步 Single Core Multi-Core
    抢占式 需要 需要
    非抢占式 不需要 需要

Preemption

用户抢占 User Preemption (即使不支持内核抢占的硬件，也是支持用户抢占的)

  1. 从system call返回到user-space
  2. 从interrupt handler返回到user-space
  3. 不是发生在用户态的！是运行在用户态的线程/进程进行资源抢占，只能发生在内核态

内核抢占 Kernel Preemption

  1. When an interrupt handler exits, before returning to kernel-space
  2. When kernel code becomes preemptible again
  3. If a task in the kernel explicitly calls schedule()
  4. If a task in the kernel blocks (which results in a call to schedule() )

Scheduling Criteria

Turnaround time：任务提交到结束的时间

Waiting time：在ready队列中等待的时间

Response time：任务提交到响应的时间

Scheduling Algorithm

  1. First-come, first-served scheduling (FCFS)

    是非抢占式的

  2. Shortest-job-first scheduling (SJF)

    可以是抢占式的，也可以是非抢占式的

    抢占式：Shortest-Remaining-Time-First

    优：平均等待时间最少 可证明最优

    劣：运行时很难知道需要多少时间

  3. Priority scheduling 注意数字大不一定优先级高

    可以抢占式，也可以非抢占式 (区分的关键在于，当新任务到来时需不需要重新进行调度)

    会导致饥饿问题：low priority processes may never execute

    解决方法：aging——逐步增加较长时间等待的进程的优先级

  4. Round-robin scheduling (RR)

    以循环的方式调度

    注意，P2只需要3个时间单位就能完成，不需要等q=4都用完，P3在第7个时间单位就能被调度，不是8

  5. Multilevel queue scheduling

    多级队列调度，ready队列被分为成单独的队列

    e.g., foreground (interactive) and background (batch) processes

  6. Multilevel feedback queue scheduling

    1. a process can move between the various queues

      • it tries to infer the type of the processes (interactive? batch?)

      • aging can be implemented this way

    2. the goal is to give interactive and I/O intensive process high priority

多处理器调度

对于多处理器调度，有两种方式：

  1. asymmetric multiprocessing

    • only one processor makes scheduling decisions, I/O processing, and other activity

    • other processors act as dummy processing units

  2. symmetric multiprocessing (SMP) ：each processor is self-scheduling

    • scheduling data structure are shared, needs to be synchronized

    • used by common operating systems

SMP：Symmetric multiprocessing，每个处理器都是自我调度的

• All threads may be in a common ready queue (a)

• Or each processor may have its own private queue of threads (b)

CMT：chip multithreading 芯片多线程（？

好好好又没听

负载均衡

对于SMP，有两种方法

  1. Push migration: periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs
  2. Pull migration: idle processors pulls waiting task from busy processor

处理器亲和性 processor affinity

  1. Soft affinity：no guarantees，操作系统尽力使一个线程运行在同一个处理器上
  2. Hard affinity：由进程指定一组它可能在上面运行的处理器

NUMA和CPU调度

如果操作系统支持numa，它将内存分配给线程运行的CPU

实时CPU调度

软实时系统：Critical real-time tasks have the highest priority, but no guarantee as to when tasks will be scheduled

硬实时系统：task must be serviced by its deadline，不会处理很复杂的任务

Linux调度

支持负载均衡，是NUMA-aware的，有Scheduling domain的概念

Scheduling domain is a set of CPU cores that can be balanced against one another.

Domains are organized by what they share (i.e. cache memory.)

Goal is to keep threads from migrating between domains