跳转至

cpu调度

分离策略和机制

  • 低级机制: how 如何做到，解决问题底层需要做哪些事情
  • 高级策略: which 哪个策略可以优雅的使用低级机制解决问题

受限直接直接执行

直接执行：

  1. 在进程列表中创建一个进程条目
  2. 分配内存
  3. 从磁盘加载代码到内存
  4. 找到入口函数
  5. 跳转到入口函数开始执行

为什么需要受限：

  • 避免外部代码直接操作硬件造成损失

trap

用户模式（user mode）

  • 在此种模式下，用户运行的代码不能直接操作硬件，直接发出操作硬件的指令会导致系统终止该进程，但是可以通过系统调用来使用

内核模式（kernel mode）

  • 操作系统运行在此模式，此模式可以执行所有操作
  • 操作系统需要向用户提供一些系统调用，让用户模式下的进程可以正常使用如IO这样的功能
  • 大多数操作系统提供几百个调用（详见 POSIX 标准）

陷阱（trap）指令

  • 内核通过在启动时设置陷阱表（trap table）来实现
  • 操作系统在启动时做的第一件事，就是告诉硬件在发生某些异常事件时要运行哪些代码，操作系统通常通过某种特殊的指令，通知硬件这些陷阱处理 程序的位置
  • 一旦硬件被通知，它就会记住这些处理程序的位置，直到下一次重新启动机器， 并且硬件知道在发生系统调用和其他异常事件时要做什么（即跳转到哪段代码）
  • 系统调用比如open()看起来就像过程调用一样，这是因为它确实是一个过程调用，在C代码的库中定义的，隐藏在过程调用内部的是著名的陷阱指令
  • 代码库使用与内核一致的调用约定来将参数放在众所周知的位置（例如，在栈中或特定的寄存器中），将系统调用号也放入一个众所周知的位置（同样，放在栈或寄存器中），然后执行上述的陷阱指令
  • 因此，C库中进行系统调用的部分是用汇编手工编码的，因为它们需要仔细遵循约定，以便正确处理参数和返回值，以及执行硬件特定的陷阱指令

当普通程序需要使用内核才能进行的高权限操作时，使用系统调用执行trap指令陷入内核，此时硬件将程序寄存器状态压入内核栈并修改PC跳转到陷阱处理代码，由内核执行代码并返回，然后由硬件弹出内核栈恢复寄存器并修改PC跳转到普通程序中断的位置，恢复用户态继续执行

进程间切换

  1. 协作方式：等待系统调用
  2. 非协作方式：操作系统进行控制

等待系统调用：

  • 在这种风格下，操作系统相信系统的 进程会合理运行。运行时间过长的进程被假定会定期放弃 CPU，以便操作系统可以决定运 行其他任务

操作系统进行控制

  • 时钟设备可以编程为每隔几毫秒产生一次中断。产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序（interrupt handler）会运行。此时，操作系统重新获得 CPU 的控制权，因此可以做它想做的事：停止当前进程，并启动另一个进程

保存和恢复上下文

  • 为了保存当前正在运行的进程的上下文，操作系统会执行一些底层汇编代码，来保存通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针，然后恢复寄存器、程序计数器，并切换内核栈，供即将运行的进程使用
  • 现代处理器的上下文切换时间在微秒-亚微秒级别，由于时钟周期决定了计算机运行的速度，所以主频越高的计算机切换时间越短

调度策略（sheduling policy，有时称为 discipline）

调度指标

  1. 周转时间（turnaround time）: 任务的周转时间定义为任务完成时间减去任务到达系统的时间
  2. 响应时间（response time）: 响应时间定义为从任务到达系统到首次运行的时间

算法

  1. FIFO（First In First Out 或 FIFO）: 先到达先运行，运行到结束继续运行下一个
  2. SJF （Shortest Job First，SJF）: 时间短的任务优先运行，运行到结束继续运行下一个
  3. STCF（Shortest Time-to-Completion First）: 时间短的任务优先运行，抢占式的
  4. RR （Round-Robin）: 在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束

更一般地说，任何公平（fair）的政策（如 RR），即在小规模的时间内将 CPU 均匀分配 到活动进程之间，在周转时间这类指标上表现不佳。事实上，这是固有的权衡：如果你愿意不公平，你可以运行较短的工作直到完成，但是要以响应时间为代价。如果你重视公平性，则响应时间会较短，但会以周转时间为代价

多级反馈队列（MLFQ）

MLFQ让操作系统持有很多进程队列，他们有不同的优先级（从高到低），每个优先级的时间片长度也不一样（越低越长），根据以下规则对进程进行调度。在开始的时候将任务放入最高优先级队列，根据进程占用时间片的行为（一次性或累计消耗限定的时间片额度）降级到下层队列，从而让IO密集型交互程序保持高优先级（因为这些程序会经常进入IO，放弃CPU），让低优先级队列（CPU密集型进程）定期boost到最高优先级队列，则可以保证其在CPU被IO密集型进程占满时不被饿死

  • 规则 1：如果 A 的优先级 > B 的优先级，运行 A（不运行 B）。
  • 规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。
  • 规则 3：工作进入系统时，放在最高优先级（最上层队列）。
  • 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次 CPU），就降低其优先级（移入低一级队列）。
  • 规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列（boost）。

MLFQ 有趣的原因是：它不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的优先级。通过这种方式，MLFQ 可以同时满足各种工作的需求：对于短时间运行的交互型工作，获得类似于 SJF/STCF 的很好的全局性能，同时对长时间运行的 CPU 密集型负载也可以公平地、不断地稳步向前。

比例份额（proportional-share）

彩票调度分配给进程一定的彩票份额，总和为1。比例份额利用了随机性替代决策，很轻量，在一定调度量级后各进程的cpu时间一定是趋近与进程彩票数量的比例的

  • 彩票调度的难点在于比例的分配，如何确定进程间的比例是个问题。
  • 解决方案就是步长调度，但是步长调度仍然存在难以解决的进程加入系统的问题。
  • 这也是为什么比例份没有被广泛使用的原因。
  • 但是它仍然有适合的领域，比如vmware虚拟机的内存分配，提前确定的份额解决了比例份额最大的问题。

多处理调度

后面再说