計算機體系結構中的排程問題是什麼？

通用的排程問題在不同的領域以不同的方式描述。生產管理中作業排序的經典問題影響了這個問題的大多數解決方案，這些解決方案通常假設有一組可以為一組消費者提供服務的資源。主要目標是找到一種有效的策略來管理消費者訪問資源的方式，以最佳化某些期望的效能指標。

在分散式系統中，排程問題之所以出現，是因為程式或程式集的併發部分必須在時間和空間上進行安排，以便最佳化系統的整體效能。程式可以被視為任務的集合，這些任務可以序列或並行執行。任務之間存在一些必須強制執行的優先順序約束。

排程的目標是確定將任務分配給處理單元以及執行任務的順序。如果構成程式的任務之間沒有優先順序關係，則此問題被稱為任務分配問題。

將程式任務排程到多處理器系統上的問題通常在一般情況下以及在幾種特殊情況下都被認為是NP完全問題。只有少數已知的、多項式時間的排程演算法。排程問題的難處理性導致了大量的啟發式演算法，每種演算法都可能在不同的情況下工作。

排程技術可以根據程式任務資訊的可用性分為確定性和非確定性。在確定性排程中，所有關於要排程的任務及其相互關係的資訊在執行時間之前都是完全已知的。

在非確定性排程中，某些資訊在程式執行之前可能未知。條件分支和迴圈是可能導致非確定性的兩種程式結構。可以使用靜態或動態方法來排程非確定性程式。

動態排程通常實現為某種負載平衡啟發式演算法。動態排程的缺點是程式執行時確定排程所產生的開銷。在確定性（靜態）排程中，程式中的每個任務都靜態地分配給特定的處理器，並且每次提交任務執行時，都將其分配給該處理器。靜態和動態方法的組合稱為混合方法。

Ginni

更新於：2021年7月24日

2K+ 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始學習