什么是进程的调度? 对于多道程序设计的程序，就会有多个进程或者线程在同时竞争CPU。对于单核系统，调度问题就是选择下一个要运行的进程或者线程。
进程切换的代价是比较大的，包括用户态到内核态的切换、保存当前进程的状态、内存映射的改变、调度程序以及载入新进程的状态；另外，会导致高速缓存的失效
- 进程是CPU密集型还是IO密集型。IO密集型可能会需要尽快运行，并且很快就阻塞。CPU密集型可以会长期占用CPU
- 何时调度。创建进程、进程退出、进程阻塞以及IO中断发生
- 是否支持抢占。支持抢占的调度，可以不必等待当前进程运行完或阻塞，直接上CPU运行
- 批处理。 批处理系统下，不需要特别快的响应速度，所以可以考虑非抢占以及每个进程都有长时间的抢占算法。指标主要是: 吞吐量、周转时间以及CPU利用率
- 交互式。 交互式系统下，抢占是必须的，因为操作者会希望比较快的得到响应。考虑的指标主要是最小响应时间、均衡性⌚️
- 实时。 实时系统下，最重要的是满足截止时间要求，即在一定的时间内完成任务
- 先来先服务(FCFS)。 最简单的方式，非抢占式的先来先服务，把任务作为一个队列🚶🚶🚶🚶，先来先服务。缺点是，无法体现任务的轻重缓急，达不到理想的指标性能
- 最短作业优先。 非抢占式下，即当一个任务完成时，从任务队列中挑选最短的一个作业执行。相对于先来先服务，提高了一些性能。运行时间必须提前掌握
- 最短剩余时间优先。 即最短作业优先的抢占版本。调度程序总是选择剩余运行时间最短的作业执行。每当一个新的作业📃到达，如果运行时间比当前进程的剩余运行时间短，就挂起当前进程并切换到新的进程
- 轮转调度。 最简单且最公平的方法，给每个进程分配一个时间片⏲️。时间片耗尽时，进程会下CPU并加入到就绪队列的末尾。问题的关键是选择合适的时间片
- 优先级调度。 进程有轻重缓急，于是给进程设置不同的优先级，每次调度优先级最高的进程运行。当然，这样可能会导致低优先级进程饥饿。解决方案是，实行奖惩机制，高优先级进程耗尽时间片时降低它的优先级(nice值)
- 多级队列。 给不同优先级的进程队列，设置不同单位的时间片。同时，也实行奖惩机制，耗尽时间片会改变进程的队列级别
- 高响应比优先调度。 动态优先权，根据奖惩机制，使作业的优先登记随着等待时间的增加而以速率a提高。 优先权 = （等待⌛️时间+要求服务时间）/要求服务时间；也就是(响应时间)/要求服务时间
线程的调度，取决于支持的是内核级线程还是用户级线程
对于用户级线程，内核不知道线程的存在，就给了进程很大的自主权。内核只是调度进程，进程中的调度程序选择哪个线程来运行。
对于内核级线程，线程的调度就交给了系统完成
一个进程由于其运行空间的不同，从而有内核线程和用户进程的区分，内核线程运行在内核空间，之所以称之为线程是因为它没有虚拟地址空间，只能访问内核的代码和数据，而用户进程则运行在用户空间，但是可以通过中断，系统调用等方式从用户态陷入内核态。
用户进程运行在用户空间上，而一些通过共享资源实现的一组进程我们称之为线程组，Linux下内核其实本质上没有线程的概念，Linux下线程实际上是与其他进程共享某些资源的进程而已。但是我们习惯上还是称它们为线程或者 轻量级进程LWP
因此，Linux上进程分3种，内核线程(或者叫核心进程)、用户进程、用户线程，当然如果更严谨的，也可以认为用户进程和用户线程都是用户进程
因此如前面的博文所述，进程和线程都被维护为一个task_struct结构，线程和进程被同等对待来进行调度。
- 实时先入先出: 有最高的优先级，不会被其他线程抢占，除非是另外一个刚刚准备好的且优先级更高的实时先入先出线程(下面会着重介绍实时先入先出)
- 实时轮转线程: 轮转体系，分配一个时间片，时间到了就可以被抢占。时间片消耗完就进入实时轮转线程列表的末尾。其实，这两种都不是真的实时，因为执行的最后期限无法确定，只是比分时线程有更高的优先级
实时线程的优先级从0-99， 0是实时线程的最高优先级，99是实时线程的最低优先级，实时线程只有静态优先级，内核不会再根据休眠，执行时间等因素而对其优先级做调整。高优先级执行到无法执行了，才轮到低优先级进程执行
传统的非实时线程，优先级从100-139。 Linux系统根据非实时线程的优先级分配时间量。普通非实时线程，根据动态优先级进行调度。而动态优先级是由静态优先级(static_prio)调整而来。Linux下，静态优先级不可见，但是可以通过nice值来影响静态优先级。ps -el中的NI就是nice值，PRI为进程优先级
Linux进程调度原理
Linux使用一个重要的结构， 调度队列。每个CPU有自己的调度队列，包括两个数组: 活动的和过期失效的 每个数组包括了140个链表头，对应140个优先级链表。
调度器从正在活动数组中选择一个优先级最高的任务，如果时间片耗尽失效，就加入到过期失效数组中。如果进程在时间片内被阻塞，那么在时间片失效之前，等待的事件发生就可以继续运行，放回到正在活动的数组中。如果活动数组没有任务了，调度器交换指针，使得活动数组和失效数组调换。(每个任务都有时间片)
上述结构中，不同优先级被赋予不同的时间片长度，优先级越高的进程，时间片越长。
Linux采用 静态优先级与动态优先级 结合的方式。Linux采用了奖惩机制，目的在于奖励互动进程以及惩罚占用CPU的进程。一个进程初始被赋予了一个优先级，耗尽和阻塞会改变nice值，活动🎡与过期进程转换时，动态改变进程优先级。
另外对于多核处理器，运行队列数据结构与某一处理器相对应，调度器尽量进行亲和调度，即将之前在某个处理器上运行过的任务再次调入该处理器
调度器只考虑可以运行的任务，不可运行的任务和正在等待各种IO操作的或内核事件的任务被放入等待队列中。每一种等待某种事件的任务组成一个等待队列。等待队列的头部包含一个指向任务链表的指针以及一个自旋锁。
不断判断锁是否能够被成功获取，直到获取锁🔒才会退出循环♻️(while)
获取锁的线程一直处于活跃状态，但是没有执行任何有效的任务，所以就会造成忙等(busy-waiting)。
参考深入理解自旋锁
为实现保护共享资源而提出的一种锁机制。 自旋锁与互斥锁比较类似，为了解决对某项资源的互斥使用。但是，互斥锁，如果资源被占用，就睡眠等(非忙等)，而自旋锁比较固执(忙等)，一直循环在那看是否该自旋锁的保持者已经释放了锁🔒。
- 分时系统具有 多路性、独立性及时性和交互性，与批处理相比，系统开销大，资源利用率与系统接纳的作业有关，适合小的不成熟的作业。批处理和分时是以作业为单位进行处理的系统，是一个通用系统。
- 多路性。一台计算机与若干台终端相连接，终端上的这些用户可以同时或基本同时使用计算机
- 交互性。用户的操作方式是联机方式，即用户通过终端采用人-机绘画的方式直接控制程序运行，同程序进行交互
- 独占性。由于系统采用时间片轮转的办法使一台计算机同时为许多终端用户服务，因此客观效果使这些用户彼此间都感觉不到别人也在使用这台计算机，就像独占一样
- 及时性。用户请求能在很短时间内获得响应