紅黑樹和單個runqueue有什麼區別？

Question

我一直在嘗試理解這兩者之間的區別，因爲它們適用於用於選擇在某些CPU調度程序中運行的任務的不同算法。

在左邊放置最低時間需求進程並選擇從左邊運行的節點的RB樹和將它們放置在最短作業第一級的隊列之間有什麼區別？

Answer 1

單個隊列在搜索時O（1）的時間複雜度爲^[1]，因爲它可以將下一個進程彈出執行。插入也有O（1），因爲它將新項目放在隊列的末尾。這種循環調度程序被使用，例如，在早期的Linux內核中。缺點是所有任務都是以相同的順序執行的。

爲了解決這個問題，一個簡單的改進是保持用O（1）彈出隊列首部，並根據優先級和/或時間要求在插入隊列中搜索合適的插槽，從而具有O（n）。有些調度程序保留多個隊列（甚至是一個優先隊列），這些隊列的運行時間因實施和需求而異。

另一方面，紅黑樹的時間複雜度爲O（log n），以便插入時獲得下一個進程和。紅黑樹的原理是，它保持與每一個操作的平衡，從而保持高效率，而不需要進一步的優化操作。優先級隊列也可以在內部使用紅黑樹來實現。

（Linux）調度程序的一個很好的起點是IBM站點上的CFS article，它也有一組很好的引用。