调度这两个词一定不陌生，学习操作系统时知道这是操作系统的核心功能之一. 而在 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 权威指南
閱讀更多 皮拉圖斯 的文章
