調度這兩個詞一定不陌生，學習操作系統時知道這是操作系統的核心功能之一. 而在 golang 的語言中，也實現了對 goroutine 的調度，極大的提升了效率. 在分佈式系統 kubernetes 中，也實現了許多調度器，並開放給開發者根據業務需求進行定製.
簡述調度
操作系統的發展過程中. 經歷了單用戶操作系統、批處理操作系統、分時操作系統和實時操作系統等發展，從僅僅支持一個用戶程序到支持多任務、併發、多核並行，以此滿足越來越多的需求. 使得計算機的體驗越來越好. 也使得如今計算機被眾多用戶、企業使用.
而在互聯網爆發後，數據量暴漲. 單個的操作系統的計算資源已經不能滿足企業的需求. 分佈式操作系統開始進入萬千企業，開源分佈式系統 kubernetes 迅速發展，微服務、雲原生、容器等掀起了技術浪潮，極大的擴充了計算資源.
在另一方面，隨著 CPU 的快速發展，單個 CPU 的計算資源也十分強大了. 操作系統以線程、進程為單位的資源分配，在多線程、進程切換時消耗了許多額外的資源. 編程語言層面也在進行資源利用率提升，golang 語言率先主打協程，在 runtime 中對資源進行分配，細化計算資源的調度粒度，從而提升資源利用率.
而無論是多任務處理、多核並行還是雲計算時代以及編程語言 runtime，計算資源的分配都用到了調度系統，本文將簡述下面三類調度系統:
- 操作系統調度: 以線程(進程)為單位的調度，由操作系統進行調度
- 編程語言 runtime 調度: 以協程為單位的調度 (go runtime)
- 分佈式調度( kubernetes ): 以容器 pod 為單位的調度，實現了十分豐富的調度策略，並提供 API 供開發者開發調度器, 滿足業務需求.
操作系統調度
操作系統中的調度涉及到進程調度、網絡調度、I/O調度，其中進程調度是操作系統的核心功能. 進程調度能夠確保一段時間內多個任務都能被合理的處理，而不是一直等待. 經典的操作系統的調度分為搶佔式和非搶佔式調度，並按照調度方法又有 FCFS、SJF、高優先權、多級反饋、時間片輪轉等調度算法. 它們能夠適應於不同的應用場景.
2.1 搶佔式調度
搶佔式調度: 一旦進程佔用 CPU 就一直運行，直到終止或等待.
非搶佔式調度: 可以強行剝奪正在使用 CPU 的進程，分配給其它進程.
2.2 調度算法
隨著處理器計算能力的提升，應用場景的不斷豐富，操作系統在調度算法上也在不斷改進，以能夠適應更多的場景. 經典的調度算法有以下這些:
- 先來先服務(FCFS): 最簡單的調度算法，FCFS 調度算法每次都選取最早進入隊列的任務. 這種方法相對公平，但是當隊列前面有一些很長的作業時，就會導致一些短作業也需要等待很長時間，造成平均等待時間過長.
- 短作業優先(SJF): 短作業優先彌補了先來先服務的缺點，它可以使得平均等待時間最短. 優先執行下次執行 CPU 時間短的作業. 但是短作業優先缺點也很明顯，需要知道下次 CPU 執行的時間.
- 高優先權優先調度算法: 在進程創建時給進程分配優先級，調度時候按照最高優先級進行優先調度. 按照優先級調度的算法可以分為靜態優先權和動態優先權，靜態優先級運行時不改變. 動態優先權會在運行時根據策略改變，避免一個進程長期壟斷 CPU.
- 高響應比優先調度: 響應比 R = (等待時間+要求服務時間)/要求服務時間. 高響應比優先調度根據計算得出的響應比，越高的越優先調度. 它是對 FCFS 和 SJF 的一種綜合平衡. 確保短作業儘量優先執行的同時，也讓長作業不會一直等待.
- 時間片輪轉調度: 主要用於分時系統的調度算法. 它將執行時間進行分片，每個在隊列中的進程只能執行一個時間片的時間，然後必須釋放處理器放進隊列的尾部，等待再次運行，直到進程執行完成. 而適當的選擇時間片大小能夠充分利用處理器，平衡等待時間.
- 多級反饋隊列調度算法: 多級反饋隊列調度算法綜合了時間片輪轉和高優先級調度算法. 它有多個調度隊列，隊列的優先級依次遞減，而隊列的時間片依次遞增. 也就是第一個隊列優先級最高，時間片大小最小. 目的是讓短作業儘量的優先級最高的執行完成，而長作業也不至於一直等待，也有機會被執行.
Go Runtime 併發調度
go 在處理協程上，使用了 GPM 調度模型，從而支持高效的併發調度. 如下圖 2 ，內核線程與邏輯處理器是多對多的關係即 M:N. 從而提升併發效率. GPM 各個模塊的解釋如下:
- G: 即 Goroutine，更輕量級的線程，保存著上下文信息.
- P: Processor，是邏輯處理器. 將 goroutine 綁定邏輯處理器 P 的本地隊列後，才會被調度. Processor 提供了相關的執行環境(Context)，如內存分配狀態(mcache)，任務隊列(G)等
- M: 它才是真正的計算資源，是系統線程.
- 全局隊列（Global Run Queue）: 未分配 Processor 的 Goroutine 保存在全局隊列中. Processor 或 M 都可以從全局隊列中取出 G .
- 本地隊列（Local Run Queue）: 是 Processor 的隊列，當隊列為空時，會從全局隊列或其它隊列補充 Goroutine.
Kubernetes 調度
在雲計算時代，Kubernetes 帶動了雲原生及私有云的熱潮，它起源於 Google 內部迭代了 20 多年的 Borg 系統. 通過 Kubernetes，讓中小企業也可以使用大規模分佈式系統. Kubernetes 的三大核心組件之一是 schduler ，裡面實現了許多調度策略，用來將容器 pod 分配到合適的 node 節點中.
相比於操作系統的調度，kubernetes 的調度需要考慮更多的資源，比如 CPU、GPU、網絡、區域等. 它的調度策略也更加豐富，並開放接口供開發使用. 下圖 1 是 kubernetes 的架構圖.
圖1 kubernetes 架構圖
3.1 數據收集
在 kubernetes 集群中，每個 Node 節點上都會啟動一個 kubelet 服務進程. 它用於處理 Master 節點下發到本節點的任務，管理 Pod 及 Pod 中的容器. kubelet 會在 kube-api-server 上註冊節點信息，並定期向 Master 中上報 node 節點的資源使用情況，通過 cAdvisor 監控容器和節點信息. API Server 將這些數據存儲在 etcd 中.
3.2 調度流程
kubernetes 的調度模塊是 kube-scheduler 負責的. 它的作用是將待調度的 Pod 按照調度算法和策略綁定的合適的 Pod 上，並將綁定的信息寫入 etcd 中. 主要涉及到對象包括待調度 Pod 列表、可用 Node 列表、調度算法和策略.
kubernetes scheduler 默認調度流程包含下面倆步:
1) 預選調度策略: 遍歷所有目標 Node，篩選出符合要求的候選節點. Kubernetes 內置了一些預選策略(Predicates) 可以選擇.
2) 優選調度策略: 在第一步的基礎上，採用優選策略(Priority)計算出每個候選節點的積分，最終使用積分最高的節點.
3.3 調度策略
kubernetes 提供許多默認的調度策略. 同時也可以根據業務常見自定義編寫調度策略，可以通過插件形式加入 kubernetes 中.
預選策略包括:
- PodFitsResources：節點上剩餘的資源是否大於 Pod 請求的資源
- PodFitsHost：如果 Pod 指定了 NodeName，檢查節點名稱是否和 NodeName 匹配
- PodFitsHostPorts：節點上已經使用的 port 是否和 Pod 申請的 port 衝突
- PodSelectorMatches：過濾掉和 Pod 指定的 label 不匹配的節點
- NoDiskConflict：已經 mount 的 volume 和 Pod 指定的 volume 不衝突，除非它們都是隻讀的
- CheckNodeDiskPressure：檢查節點磁盤空間是否符合要求
- CheckNodeMemoryPressure：檢查節點內存是否夠用
優選策略包括:
- LeastRequestedPriority：通過計算 CPU 和內存的使用率來決定權重，使用率越低權重越高，當然正常肯定也是資源是使用率越低權重越高，能給別的 Pod 運行的可能性就越大.
- SelectorSpreadPriority：為了更好的高可用，對同屬於一個 Deployment 或者 RC 下面的多個 Pod 副本，儘量調度到多個不同的節點上，當一個 Pod 被調度的時候，會先去查找該 Pod 對應的 controller，然後查看該 controller 下面的已存在的 Pod，運行 Pod 越少的節點權重越高.
- ImageLocalityPriority：就是如果在某個節點上已經有要使用的鏡像節點了，鏡像總大小值越大，權重就越高.
- NodeAffinityPriority：這個就是根據節點的親和性來計算一個權重值，後面我們會詳細講解親和性的使用方法.
- CalculateNodeLabelPriority: 如果指定了該策略，則 scheduler 會通過 RegisterCustomPriorityFunction 方法註冊策略. 策略用於判斷列出的標籤在備選節點中存在時, 是否選擇該備選節點. 如果節點的標籤在優選策略中的標籤列表中且 presence 值為 true，或者相反標籤不在列表中且 presence 為 false 則 score 為 10 分，否則 score = 0 分.
- BalancedResourceAllocation: 該策略主要用於從備選節點列表中選出各項資源使用率最均衡的節點.
1. 進程與進程管理 | 進程調度 [https://zhuanlan.zhihu.com/p/31868972]
2. 最短作業優先(SJF)調度算法(詳解版)[http://c.biancheng.net/view/1244.html]
3. kubernetes 調度器解析[https://zhuanlan.zhihu.com/p/47047550]
4. kubernetes 權威指南
閱讀更多 皮拉圖斯 的文章
