1)负载共享调度算法 负载共享( load sharing)调度算法的基本思想是:进程并不分配给一个 处理器,系统维护一个全局性就绪线程队列,当一个处理器空闲时,就 选择一个就绪线程占有处理器运行。这一算法有如下优点 ⑩●把负载均分到所有的可用处理器上,保证了处理器效率的提高 ⑩●不需要一个集中的调度程序,一旦一个处理器空闲,操作系统的调度 程序就可以运行在该处理器上以选择下一个运行的线程。 ⑩●运行线程的选择可以采用各种可行的策略(雷同与前面介绍的各种进 程调度算法)。 这一算法也有一些不足: ⑩●就绪线程队列必须被互斥访问,当系统包括很多处理器,并且同时有 多个处理器同时挑选运行线程时,它将成为性能的瓶颈 ⑩●被抢占的线程很难在同一个处理器上恢复运行,因此当处理器带有高 速缓存时,恢复高速缓存的信息会带来性能的下降。 ⑩●如果所有的线程都被放在一个公共的线程池中的话,所有的线程获得 处理器的机会是相同的。如果一个程序的线程希望获得较高的优先级, 进程切换将导致性能的折衷
1）负载共享调度算法 • 负载共享（load sharing）调度算法的基本思想是：进程并不分配给一个 处理器，系统维护一个全局性就绪线程队列，当一个处理器空闲时，就 选择一个就绪线程占有处理器运行。这一算法有如下优点： l 把负载均分到所有的可用处理器上，保证了处理器效率的提高。 l不需要一个集中的调度程序，一旦一个处理器空闲，操作系统的调度 程序就可以运行在该处理器上以选择下一个运行的线程。 l 运行线程的选择可以采用各种可行的策略（雷同与前面介绍的各种进 程调度算法）。 • 这一算法也有一些不足： l 就绪线程队列必须被互斥访问，当系统包括很多处理器，并且同时有 多个处理器同时挑选运行线程时，它将成为性能的瓶颈。 l被抢占的线程很难在同一个处理器上恢复运行，因此当处理器带有高 速缓存时，恢复高速缓存的信息会带来性能的下降。 l如果所有的线程都被放在一个公共的线程池中的话，所有的线程获得 处理器的机会是相同的。如果一个程序的线程希望获得较高的优先级， 进程切换将导致性能的折衷
尽管有这样一些缺点,均分负载调度算法依然 是多处理器系统最常用的线程调度算法。如著 名的mach操作系统,它包括一个全局共享的就 绪线程队列,并且每一个处理器还对应于一个 局部的就绪线程队列,其中包括了一些临时绑 定到该处理器上的就绪线程,处理器调度时首 先在局部就绪线程队列中选择绑定线程,如没 有,才到全局就绪线程队列中选择未绑定线程
• 尽管有这样一些缺点，均分负载调度算法依然 是多处理器系统最常用的线程调度算法。如著 名的mach操作系统，它包括一个全局共享的就 绪线程队列，并且每一个处理器还对应于一个 局部的就绪线程队列，其中包括了一些临时绑 定到该处理器上的就绪线程，处理器调度时首 先在局部就绪线程队列中选择绑定线程，如没 有，才到全局就绪线程队列中选择未绑定线程
2)群调度算法 群调度( gang scheduling)算法的基本思想是: 把一组相关的线程在同一时间一次性调度到一组 处理器上运行。它具有以下的优点 当紧密相关的进程同时执行时,同步造成 的等待将减少,进程切换也相应减少,系统性能 自然得到提高 由于一次性同时调度一组处理器,调度的 代价也将减少。 从上面两个优点来看,群调度算法针对多线程并 行执行的单个应用来说具有较好的效率,因此它 被广泛应用在支持细粒度和中粒度并行的多处理 器系统中
2）群调度算法 • 群调度（gang scheduling）算法的基本思想是： 把一组相关的线程在同一时间一次性调度到一组 处理器上运行。它具有以下的优点： l 当紧密相关的进程同时执行时，同步造成 的等待将减少，进程切换也相应减少，系统性能 自然得到提高。 l 由于一次性同时调度一组处理器，调度的 代价也将减少。 • 从上面两个优点来看，群调度算法针对多线程并 行执行的单个应用来说具有较好的效率，因此它 被广泛应用在支持细粒度和中粒度并行的多处理 器系统中
3)处理器专派调度算法 处理器专派( dedicated processor assignment)调度算法的基 本思想是:给一个应用专门指派一组处理器,一旦一个应 用被调度,它的每一个线程被分配一个处理器并一直占有 这个处理器运行直到整个应用运行结束。采用这一算法之 后,这些处理器将不适用多道程序设计,即该应用的一个 线程阻塞后,该线程对应的处理器不会被调度给其他线程, 而将处于空闲状态。 显然,这一调度算法追求的是通过高度并行来达到最快的 执行速度,它在应用进程的整个生命周期避免进程调度和 切换,且毫不考虑处理器的使用效率。对于高度并行的计 算机系统来说,可能包括几十或数百个处理器,它们完全 可以不考虑单个处理器的使用效率,而集中关注于提高计 算效率。处理器专派调度算法适用于此类系统的调度。 最后值得指出的是,无论从理论上还是从实践中都可以证 明,任何一个应用任务,并不是划分的越细,使用的处理 器越多,它的求解速度就越快。在多处理器并行计算环境 中,任何一种算法的加速比提高是有上限的
3）处理器专派调度算法 • 处理器专派（dedicated processor assignment）调度算法的基 本思想是：给一个应用专门指派一组处理器，一旦一个应 用被调度，它的每一个线程被分配一个处理器并一直占有 这个处理器运行直到整个应用运行结束。采用这一算法之 后，这些处理器将不适用多道程序设计，即该应用的一个 线程阻塞后，该线程对应的处理器不会被调度给其他线程， 而将处于空闲状态。 • 显然，这一调度算法追求的是通过高度并行来达到最快的 执行速度，它在应用进程的整个生命周期避免进程调度和 切换，且毫不考虑处理器的使用效率。对于高度并行的计 算机系统来说，可能包括几十或数百个处理器，它们完全 可以不考虑单个处理器的使用效率，而集中关注于提高计 算效率。处理器专派调度算法适用于此类系统的调度。 • 最后值得指出的是，无论从理论上还是从实践中都可以证 明，任何一个应用任务，并不是划分的越细，使用的处理 器越多，它的求解速度就越快。在多处理器并行计算环境 中，任何一种算法的加速比提高是有上限的
4)动态调度算法 在实际应用中,一些应用提供了语言或工具以允许动态地改变进程中 的线程数,这就要求操作系统能够调整负载以提高可用性。 动态调度( dynamic scheduling)算法的基本思想是由操作系统和应用 进程共同完成调度。操作系统负责在应用进程之间划分处理器。应用 进程在分配给它的处理器上执行可运行线程的子集,哪一些线程应该 执行,哪一些线程应该挂起完全是应用进程自己的事(当然系统可能 提供一组缺省的运行库例程)。相当的应用将得益于操作系统的这 特征时,但一些单线程进程则不适用这一算法。 ·在这一算法中,当一个进程达到或要求新的处理器时,操作系统的调 度程序主要限制处理器的分配,并且按照下面的步骤处理: ⑩●如果有空闲的处理器,满足要求 ⑩●否则,对于新到达进程,这从当前分配了一个以上处理器的进程手 中收回一个,并把它分配给新到达进程 ⑩●如果一部分要求不能被满足,则保留申请直到出现可用的处理器或 要求取消。 ⑩●当释放了一个或多个处理器后,扫描申请处理器的进程队列,按照 先来先服务的原则把处理器逐一分配给每个申请进程直到没有可用处 理器
4）动态调度算法 • 在实际应用中，一些应用提供了语言或工具以允许动态地改变进程中 的线程数，这就要求操作系统能够调整负载以提高可用性。 • 动态调度（dynamic scheduling）算法的基本思想是由操作系统和应用 进程共同完成调度。操作系统负责在应用进程之间划分处理器。应用 进程在分配给它的处理器上执行可运行线程的子集，哪一些线程应该 执行，哪一些线程应该挂起完全是应用进程自己的事（当然系统可能 提供一组缺省的运行库例程）。相当的应用将得益于操作系统的这一 特征时，但一些单线程进程则不适用这一算法。 • 在这一算法中，当一个进程达到或要求新的处理器时，操作系统的调 度程序主要限制处理器的分配，并且按照下面的步骤处理： l 如果有空闲的处理器，满足要求。 l 否则，对于新到达进程，这从当前分配了一个以上处理器的进程手 中收回一个，并把它分配给新到达进程。 l 如果一部分要求不能被满足，则保留申请直到出现可用的处理器或 要求取消。 l 当释放了一个或多个处理器后，扫描申请处理器的进程队列，按照 先来先服务的原则把处理器逐一分配给每个申请进程直到没有可用处 理器