7月31日学习笔记

第十二讲 多处理机调度

12.2 多处理机调度概述

单队列多处理器调度（SQMS） 1、缺乏可扩展性（scalability）；2、缓存亲和性（cache affinity）弱

尽可能让进程在同一个CPU上运行，保持一些进程的亲和度的同时，可能需要牺牲其他进程的亲和度来实现负载均衡

多队列处理器调度（Multi-Queue Multiprocessor Scheduling，MQMS）

在MQMS中，基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则，比如轮转或其他任何可能的算法

当一个进程进入系统后，系统会依照一些启发性规则（如随机或选择较空的队列）将其放入某个调度队列。这样一来，每个CPU调度之间相互独立，就避免了单队列的方式中由于数据共享及同步带来的问题

根据不同队列的调度策略，每个CPU从两个进程中选择，决定谁将运行，例如，轮转调度

具有可扩展性。队列的数量会随着CPU的增加而增加，因此锁和缓存争用的开销不是大问题

具有良好的缓存亲和度。所有进程都保持在固定的CPU上，因而可以很好地利用缓存数据

负载不均 load imbalance

如何解决：进程移动，又叫迁移（migration）。通过进程的跨CPU迁移，可以真正实现负载均衡

工作窃取（work stealing）

进程量较少的（源）队列不定期地“偷看”其他（目标）队列是不是比自己的进程多

如果目标队列比源队列（显著地）更满，就从目标队列“窃取”一个或多个进程，实现均衡负载

如果太频繁地检查其他队列，就会带来较高的开销，可扩展性不好

如果检查间隔太长，又可能会带来严重的负载不均

12.3 O(1)调度

SMP和Linux内核

在Linux2.0早期，SMP支持一个“大锁”组成，这个“大锁”对操作系统内部的访问进行串行化

在2.2前的内核中，SMP实现在用户级，Linux内核本身并不能因为有多个处理器而得到加速

在2.4内核后，SMP实现在核心级，使用多处理器可以加快内核的处理速度。一开始的调度器是复杂度为O(n)的调度算法