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

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

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

调度的目标是确定任务到处理元素的分配以及任务执行的顺序。如果构成程序的任务之间没有优先关系，这个问题就称为任务分配问题。

众所周知，在多处理器系统上调度程序任务的问题通常是NP完全问题，在一些特殊情况下也是如此。只有少数已知的多项式时间调度算法。调度问题的棘手性导致了大量的启发式方法，每种方法都可能在不同的情况下起作用。

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

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

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