[科普中国]-多处理器调度

多处理器系统

多处理器系统是包含两个或更多处理器的计算机系统。与单处理器系统相比，在速度、性能、可靠性等方面都有很大提高，相应地，在结构和管理上也变得更为复杂。多处理器系统分为松散耦合多处理器系统（或称集群系统）、紧密耦合多处理器系统。

1、松散耦合多处理器系统（或称集群系统）

这是一组相对自主系统的集合体，每台处理器有自己的内存和I/O通道。每台处理器上有自己的操作系统。往往通过高速通信线路互连在一起。

2、紧密耦合多处理器系统

一组处理器共享一个内存，并且在一个操作系统的集中控制下工作。最常用的模式是对称多处理器（Symmetric MultiProcessor, SMP）结构。该结构中所有处理器都是同构的。该系统的操作系统负责管理由各个处理器组成的集合体，其中任一成员都可控制 I/O设备或对内存单元进行访问。操作系统是浮动的，可从一个处理器转到另一个处理器上。当前负责管理系统表格和系统函数的处理器称为“执行机”。任何时候担当执行机的处理器只能有一个，这样可预防对全局系统信息的竞争。1

多处理器调度方法多处理器调度包括如下三个相关的方面：

1、给处理器分配进程，即把进程加到某个处理器所对应的就绪队列中。如果多处理器的体系结构是相同的，最简单的调度方法就是把所有处理器看做一个资源池，根据要求把进程分配给处理器。常用的分配方式有静态分配（即把一个进程固定地分给一个处理器）和动态分配（即把系统中所有就绪进程放入一个全局队列，从中选出进程并分派到任何可用的处理器上）两种。

2、在单个处理器上是否使用多道程序技术。在传统的多处理器中，每个单一的处理器应在若干进程之间进行切换，以便获得高利用率和良好性能。如果一个应用程序由多线程的单个进程实现，它运行在多处理器上，那么保持每个处理器尽可能地忙不再是最重要的因素。在这种情况下，一般考虑的焦点是为应用程序提供更好的性能。如果组成一个应用程序的所有线程同时运行，其性能最好。

3、实际分派进程。在多处理器系统中，方法越简单，开销越少，效率就越高。有统计资料表明，在双CPU系统中，进程采用FCFS调度算法与采用轮转法、最短剩余时间优先法相比较，系统吞吐量的变化很小。所以，对于多处理器系统来说，采用简单的FCFS算法或带有静态优先级的FCFS算法是合适的。

为了防止多个处理器同时从一个就绪队列中选择进程时出现的竞争问题，可以采用转锁（Spin Lock）方式实现互斥。但简单的转锁方式存在“循环等待”问题—— 当一个进程占用转锁时，如果其他进程也要用该锁，就得循环测试并等待，直至那个进程释放该锁。有些系统采用“灵巧”调度（Smart Scheduling），即得到转锁的进程设置一个全局标志，声明它当前占用该锁。当它释放该锁时，就清除该标志。调度程序不让占有转锁的进程停止，而是多给它一点儿运行时间，使之尽快完成临界区工作，从而释放该锁。

多处理器系统中线程调度方式多处理器系统中线程调度通常有如下四种方式：

1、负载共享

它不把进程分给具体的处理器，系统维护一个全局的就绪线程队列，当某个处理器空闲时，就从该队列中选择一个线程。

负载共享的方法有：

① FCFS，即按顺序排队，选队首线程投入运行。

② 最少线程数优先（Smallest Number of Threads First），即共享就绪队列按优先级构造，具有未调度线程个数最少的作业其线程的优先级最高。

③ 抢占式最少线程数优先，是对最少线程数优先法的改造。如果新到来的作业所拥有的线程个数比当前运行作业的还少，就发生抢占。

负载共享方式的优点是负载分布在不同的处理器上；不需要集中调度，操作系统的调度程序可以运行在不同的处理器上。同时它也有若干缺点：对该全局队列占用的内存区必须互斥访问，可能成为瓶颈问题；由于被抢占的线程未必能在相同的处理器上恢复执行，因而降低本地高速缓存的效率；把所有线程看做公用线程池，一个进程的所有线程未必能同时获得处理器，从而严重损害处理器性能。

2、成组调度

这种方法把一组相关线程作为一个单位同时调到一组处理器上运行，一一对应，所有成组线程一起开始和结束它们的时间片。

成组调度可使一个进程的所有线程一起运行，若其中一个线程向另一个发出请求，能立即得到该信息且能立即回答。因此在一个时间片中，同一个进程的各线程间可以发送和接收大量的信息，大大方便了线程间的通信。

3、专用处理器分配

这是成组调度的极端形式。当一个进程被调度时，它的每个线程被分配到一个处理器上，在该进程完成之前，处理器由相应的线程专用。

这种方法会浪费处理器的时间。当一个线程为了与另一个线程同步而等待I/O时，该线程专用的处理器就闲置了。但是，在由几十甚至上百个处理器组成的高度并行系统中，处理器的利用率不再是最重要的问题。此外，在一个应用程序的生存期中完全避免了进程切换，因而大大加速了程序的执行。

4、动态调度

这种方法允许在进程执行期间动态改变其线程的数目。操作系统的调度职责主要限 于处理器的分配，并且遵循以下原则：当一个作业请求一个或多个处理器时，如果有空闲的处理器，就使用它们，以满足请求；否则，如果提出请求的作业是刚到来的，则从当前分得多个处理器的任何一个作业中拿出一个处理器分给该作业；如果任一部分请求都不能满足，该作业就保持未完成状态，直至有处理器可供它使用或该作业取消这个请求；当释放一个或多个处理器时，扫描当前尚未处理过的请求处理器的作业队列，且为队列中尚未分到处理器的每个作业分配一个处理器，然后再次扫描该队列，按FCFS方式分配其余的处理器。动态调度方法优于成组调度或专用处理器分配方法，但是这种方法的开销较大。2