时间片，从多任务系统说起

Original 我是可乐可乐

之前文章提到过时间片的概念，当时限于篇幅没有细说，现在展开来讨论一下。

时间片(Time slice or quantum)，简单的讲，就是把一段较长的时间，划分成多个较短的时间片段，然后利用这些时间片段去执行不同的任务。比如说，你一边工作一边玩手机，或者一边看本篇文章一边猜测作者很帅，这其实就涉及时间片的概念了。

在计算机科学中，时间片指的是分时操作系统分配给每个正在运行的进程微观上的一段CPU时间。上帝视角去看CPU，就会发现这家伙一会服务程序A，一会跑去服务程序B，又一会跑去服务C……但是CPU这货跑动的速度非常快，受到余晖效应影响，你可能会看到有无数个CPU同时服务所有的程序。

想要细说时间片的由来，就不得不追溯到上古时期。鸿蒙初开，天地混沌，电脑曾经是个奢侈品，使用电脑的人需要去排队。没错，人需要排队等着分配电脑资源。那会的电脑是单任务的，一群人事先规划好电脑使用需求，然后由专人把要执行的任务输入电脑。然后大家就可以先去喝杯咖啡，两小时后回来查看运行结果。

但是，即便是上古的电脑，运行速度也是相当快的，于是乎，有人想着，能不能让多个人同时使用一台电脑呢？

有可能你会想，CPU不是多核的吗？每个核上跑不同的程序，是不是就可以同时供多人使用了呢？是的，多个核是可以真正并行地运行多个程序，但是一个CPU能有多少个核呢？

即便是价值一万多人民币的i9-9980XE，也就18个核，而现代化的PC同时运行几百个程序是很正常的事。很显然，靠核心实现多人共享是不现实的。更何况，多核心处理器出现的很晚，其设计目的也不是为了真正并行执行多个程序，而是为了解决单核CPU运行速度难以进一步提升的问题。

于是乎，多任务操作系统应运而生了。最先出现的是一种被称为协作式多任务的系统(Cooperative multitasking)，协作式指的是多个任务之间互相协作。其核心思想就是，假定每个程序都是善意的、理性的，各个程序不会长时间霸占CPU，占用CPU一段时间后，会主动让出CPU，这样其他程序就能够获得CPU的使用权。协作式多任务系统，本质上是一个所有程序共同参与系统管理的系统，这样好不好呢？答案很悲催，并不好。

原因也很简单，程序本身没有善恶之分，但是设计程序的人可能有不可告人的秘密。程序本身也无所谓理性或者感性，但是设计程序的人却有水平高低之分。

协作式多任务系统遇到的第一个问题便是存在安全隐患。假如一个程序挂死，整个系统就不可用了。很多时候，一个恶意程序可能一直霸占CPU资源，其他程序也就都饿死了。

其次是编程会变得更加复杂。程序运行时无法获知其他程序的运行状态，切换时机不好把握。比如说，一个等待外设接入的程序，到底是一直占用CPU等待外设接入，还是先让出CPU呢？比如说键盘程序主动让出了CPU，播放器获得CPU开始播放小短片，这个时候有人过来了，你努力敲击键盘的Win+D，却发现键盘程序无法响应，尴不尴尬！

为了解决上面说的这种尴尬场景，中断机制和抢占式多任务系统横空出世。难怪恩格斯会说，一个市场需求往往比十所大学更能拉动技术进步。

中断产生时，可以立即停止正在运行的程序，然后跳转到中断的处理函数，去执行一些不可告人的事。

有了中断机制，又有多任务处理的需求，出现抢占式多任务系统(Preemptive multitasking)就很自然了。当今几乎所有的主流操作系统都是抢占式的，包括Windows、macOS、Linux(包括Android)以及iOS等。

抢占式多任务系统什么意思呢？抢占指的是利用中断机制，每隔一段时间产生一个中断，中断产生时暂停任何一个正在执行的程序，一般通过PUSH指令保存现场，也就是保存当前寄存器以及程序断点等信息。然后调用调度器，再由调度器决定把CPU分给其他程序使用。

这样就不难看出协作式和抢占式多任务处理系统的区别了。协作式系统是一个所有程序共同参与管理的系统，看似友好，实际上问题多多。而抢占式系统把管理权集中给调度程序，看似专横，但是却成了当下所有主流操作系统的调度机制，so interesting？

其实，抢占式多任务系统一般来说也不是绝对可抢占的。一般来说，内核态和用户态都是可抢占的。比如Windows NT, Linux kernel 2.6.x及以上的版本。但是一些基于Linux二次开发的厂商，会把Linux内核态改成非抢占的。内核不可抢占最大的好处便是可以大大简化内核的设计，但是这在一定程度上降低了内核响应速度。其次，内核态需要高效执行的程序如果被抢占打断，很可能产生竞争条件，进而导致死锁问题(可以参考另一篇文章：锁，知其然知其所以然)。

那么，到底多久抢占一次呢？这个时间间隔其实就是时间片了。抢占式系统调度方式涉及诸多调度算法。简单的讲，常规的调度涉及两种方式。

程序执行完毕退出、阻塞等待外设、等待数据、获取信号量、等待消息等，都会让出CPU。
时间片到期，系统使用一个周期性的中断来管理时间片，中断服务函数内判断时间片是否过期。

对于后者，时间片到底多大呢？首先，如果这个时间片过大，比如说1s，那么当你手机开了10个应用，你打开第10个应用可能就需要等待10s，这显然是不能忍的。反之，如果时间片很小，比如说80微秒，假如调度器本身需要耗时20微秒，那么就会有20%的CPU周期被白白浪费了。那到底多久比较合适呢？翻看Linux源码发现，Linux默认的时间片RR_TIMESLICE是100ms。

需要说明的是，Linux分配给各个进程执行的时间也并不是完全等于RR_TIMESLICE，当一个优先级更高的进程需要紧急执行时，即便时间片没有到期，调度器也会切换进程。

到此，时间片的概念就介绍完了。然而，多任务系统的核心——调度算法，还基本没有涉猎。调度算法可以很简单，比如时间片轮转法，简单到可以使用循环程序实现。一堆程序排着队，排到自己就获得一个时间片，时间片到期后跑到队尾继续排队。

复杂的呢？常见的有下面这些算法：

先来先服务算法(First come first serve, FCFS)
最短作业优先(Shortest job first, SJF)
最高响应比优先算法(Highest response ratio next, HRRN)
虚拟轮转法(Virtual RR)
优先级调度算法(Priority scheduling algorithm, PSA)
多级反馈队列调度算法(Multilevel feedback)

这个世界，能够实现一个优秀调度器的人屈指可数。

厘清了时间片，却又陷入了调度器的坑。学习真的就像一个球，你膨胀的越大，未知的边界也就会越大。