计算机体系结构中的调度问题是什么？

通用的调度问题在不同的领域以不同的方式描述。生产管理中作业排序的经典问题影响了这个问题的大多数解决方案，这些解决方案通常假设有一组可以为一组消费者提供服务的资源。主要目标是找到一种有效的策略来管理消费者访问资源的方式，以优化某些期望的性能指标。

在分布式系统中，调度问题之所以出现，是因为程序或程序集的并发部分必须在时间和空间上进行安排，以便优化系统的整体性能。程序可以被视为任务的集合，这些任务可以串行或并行运行。任务之间存在一些必须强制执行的优先级约束。

调度的目标是确定将任务分配给处理单元以及执行任务的顺序。如果构成程序的任务之间没有优先级关系，则此问题被称为任务分配问题。

将程序任务调度到多处理器系统上的问题通常在一般情况下以及在几种特殊情况下都被认为是NP完全问题。只有少数已知的、多项式时间的调度算法。调度问题的难处理性导致了大量的启发式算法，每种算法都可能在不同的情况下工作。

调度技术可以根据程序任务信息的可用性分为确定性和非确定性。在确定性调度中，所有关于要调度的任务及其相互关系的信息在执行时间之前都是完全已知的。

在非确定性调度中，某些信息在程序执行之前可能未知。条件分支和循环是可能导致非确定性的两种程序结构。可以使用静态或动态方法来调度非确定性程序。

动态调度通常实现为某种负载平衡启发式算法。动态调度的缺点是程序运行时确定调度所产生的开销。在确定性（静态）调度中，程序中的每个任务都静态地分配给特定的处理器，并且每次提交任务执行时，都将其分配给该处理器。静态和动态方法的组合称为混合方法。

Ginni

更新于：2021年7月24日

2K+ 次浏览

启动你的职业生涯

完成课程获得认证

开始学习