【学习笔记】操作系统之哲学原理

深碍√TFBOYSˉ_ 2022-09-03 09:21 160阅读 0赞

###  ###

*  引言：
 *   *  魔术与管理
     *  用户程序与操作系统
 *  进程、内存和文件
 *   *  进程原理
     *  进程的状态
     *  操作系统管理进程
     *  进程调度
     *  调度算法
     *   *  1.先来先服务调度算法
         *  2.时间片轮转算法
         *  3.短任务优先算法
         *  4.优先级调度算法
         *  5.混合调度算法
     *  进程调度的过程

# 引言： #

很多人都觉得操作系统枯燥、乏味，甚至令人厌烦。更有人说懂不懂操作系统没有关系。不是很多人在学习操作系统之前就已经写过程序了吗？有的人甚至已经写过很大很复杂的程序了。可见，不懂操作系统并不妨碍我们学习使用计算机。 如果读者这样想，我劝你再想一想。你虽然写过程序，可你知道程序到底是如何在计算机上运行的吗？如果不知道，你怎么敢肯定你的程序总会运行正确呢？你怎么敢说你写的程序最大限度地利用了系统的能力呢？一个人觉得操作系统没用，那是因为他不知道怎么用，或者他没有用操作系统的意愿。说明白一点，如果你认为操作系统没有用，那是因为你的编程和程序开发处在一个低级的水平上。如果你掌握了操作系统，你的编程水平将显著提高。 换句话说，操作系统有没有用，我的回答是"As you will"。你如果有意愿或者有行动使用操作系统，操作系统就是有用的；如果你没有意愿或行动，则操作系统就是没有用的。

程序的运行至少需要如下四个因素：  
★ 程序设计语言。  
★ 编译系统。  
操作系统。  
★ 指令集结构（计算机硬件系统）。

我们可以给操作系统下定义：  
★ 操作系统是一个软件系统；  
★ 操作系统使计算机变得好用（将人类从繁琐、复杂的对机器掌控的任务中解脱）；  
★ 操作系统使计算机运作变得有序（操作系统掌控计算机上所有的事情）。总结起来就是：操作系统是掌控计算机上所有事情的软件系统。  
从这个定义可以引申出操作系统的功能：  
★ 替用户及其应用管理计算机上的软硬件资源。  
★ 保证计算机资源的公平竞争和使用。  
★ 防止对计算机资源的非法侵占和使用。  
★ 保证操作系统自身正常运转

## 魔术与管理 ##

提升上面所列的操作系统功能，可以得出操作系统所扮演的两个根本角色：管理者和魔术家。只要记住了这两个角色，就差不多明白了什么是操作系统。

魔术家角色 魔术家的目标是把差的东西变好，把少的东西变多，把复杂变简单。同样，操作系统将计算机以一个更加容易、更加方便、更加强大的方式呈现给用户。例如，如果在裸机上直接编程是很困难的，因为各种数据转移均需要用户自己来控制，对不同设备要用不同命令来驱动，而这对一般人很难胜任。操作系统将这些工作从用户手中接过来，从而让用户感觉编程是一件容易的事（相对来说，编程对于有些人来说永远很难）， 操作系统通过进程抽象让每一个。 用户感觉有一台自己独享的CPU；通过虚拟内存抽象，让用户感觉物理内存空间具有无限扩张性，这就是把少变多。当然，操作系统的把少变多不是无中生有，变多也不是无限多，只是针对磁盘容量的大小。  
管理者角色 操作系统管理计算机上软硬件资源。例如，操作系统对CPU、内存、磁盘等的管理，使得不同用户之间或者同一用户的不同程序之间可以安全有序地共享这些硬件资源。那怎么让用户很好地利用这些硬件资源呢？就是分块（parcel out），把硬件分块给应用程序使用。这里关键的原则是有效和公平，这是管理者的必备素质。有效指的是不能浪费资源，公平指的是每个人都有可能享有资源，即不能有不公平的现象。当然真正的公平是没有的事，这很像人类生活的现实。不过追求公平却是我们的本能，在虚拟世界里尽可能公平一点还是非常应该的，至少应该是设计操作系统时的不懈追求。

根据管理的资源不同，操作系统具体功能如下：  
★ CPU管理，即如何分配CPU给不同应用和用户。  
★ 内存管理：即如何分配内存给不同应用和用户。  
★ 外存管理：即如何分配外存（磁盘）给不同应用和用户。  
★ I/O管理：即如何分配输入输出设备给应用和用户。 除了对上述资源进行管理和抽象外，操作系统作为掌控一切的软件系统，其自身必须是稳定和安全的，即操作系统自己不能出现故障。因此，操作系统的设计还需包括如下两项：  
★ 健壮性管理：即如何确保操作系统自身的正常运作。  
★ 安全性管理：即如何防止非法操作和入侵

CPU管理就是将要介绍的进程管理。进程管理的主要目的有3个：第一个是公平，即每个程序都有机会使用CPU。第二个是非阻塞（non-blocking），即任何程序不能无休止地阻挠其他程序的正常推进。如果一个程序在运行过程中需要输入输出或者因别的什么事情而发生阻塞，这个阻塞不能妨碍别的进程继续前进。就像人类世界，缺了谁地球照样旋转。第三个是优先级。在人类生活中人的地位不完全一样，地位高的就比地位低的优先级高。人类把自己生活中的这种关系搬到操作系统里面，就有了优先级的概念，即某些程序比另外一些程序优先级高。如果优先级高的程序开始运行，则优先级低的程序就要让出资源。就像我们经常说的，我们坚决反对大锅饭，应该让一部分人（程序）先富起来。

内存管理主要是管理缓存、主存、磁盘、磁带等存储介质所形成的内存架构。为此目的，操作系统设计人员发明了虚拟内存的概念，即将物理内存（缓存和主存）扩充到外部存储介质（磁盘、光盘和磁带）上。这样内存的空间就大大地增加了，能够运行的程序的大小也大大地增加了。内存管理的另一个目的是让很多程序共享同一个物理内存。这就需要对物理内存进行分割和保护，不让一个程序访问另一个程序所占的内存空间，专业术语称为运行时不能越界。在生活中，就是我家的东西不希望你跑来拿。  
外存管理通常也称为存储管理，它就是众所周知的文件系统了。文件系统的主要目的是将磁盘变成一个很容易使用的存储媒介以提供给用户使用。这样我们在访问磁盘时无须了解磁盘的物理属性或数据在磁盘上的精确位置，诸如磁道、磁柱、扇面等。当然，文件系统还可以建立在光盘和磁带上。只是使用最为频繁的文件系统都以磁盘为介质。  
I/O管理也称为设备管理，就是管理输入输出设备。I/O管理的目的有两个：一是屏蔽不同设备的差异性，即用户用同样的方式访问不同的设备，从而降低编程的难度；二是提供并发访问，即将那些看上去并不具备共享特性的设备（如打印机）变得可以共享。

## 用户程序与操作系统 ##

操作系统上下分别是虚拟机器界面和物理机器界面。处于物理机器下面的是硬件，而硬件和操作系统的关系将是本书的关注点。处于虚拟机器界面上面的是应用软件，应用软件和操作系统的关系不是本书的重点，而是系统编程或底层编程等课程的关注点。在这里，我们只想来简要讨论一下应用程序和操作系统的关系，因为这个关系对理解操作系统非常重要。 那么，操作系统和应用程序之间是什么关系呢？很显然，操作系统为用户程序提供了一个虚拟机器界面，而应用程序运行在这个界面之上。但这个答案似乎太抽象，并不能帮助深入理解它们之间的关系。前面讲过，操作系统是一个程序，而用户程序也是程序，程序和程序之间能有什么关系呢？无非是调用和被调用的关系。 那操作系统和用户程序之间到底谁是调用者，谁是被调用者呢？答案似乎很清楚：操作系统通过虚拟机器界面为用户程序提供各种服务，用户程序在运行过程中不断使用操作系统提供的服务来完成自己的任务。例如，用户程序在运行过程中需要读写磁盘，这个时候就需要调用操作系统的服务来完成磁盘读写操作；如果需要收发数据包，也需要调用操作系统的服务来完成。当调用这些服务时，控制从用户程序转移到操作系统，而操作系统在完成这些服务后将控制返回给用户程序。在这种思维模式下，用户程序是主程序，而操作系统是子程序。  
但是有正就有反，这就是哲学中的矛盾论。如果我们从另一个角度来看，会得出相反的结论。系统启动之后最先启动的是什么程序？操作系统。用户程序不能在操作系统启用之前启动（除非是很厉害的病毒）。在此之后，每次启动一个用户程序，都相当于操作系统将控制转移给用户程序；而在用户程序执行完毕后，控制又回到操作系统。这样看上去，操作系统是主程序，它在一生当中不断调用各种应用程序，而每个应用程序执行完之后再回到操作系统。就这样循环往复，直到无穷或机器关闭。在此种思维模式下，操作系统是主程序，用户程序是子程序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]  
　操作系统为主程序，用户程序为子程序的图示

# 进程、内存和文件 #

进程是操作系统里面的核心概念。它指的是一个运动中的程序。从名字上看，进程表示的就是进展中的程序。一个程序一旦在计算机里运行起来，它就成为一个进程。操作系统对进程的管理通过进程表来实现。进程表里存放的是关于进程的一切信息。在任何时候，进程所占有的全部资源，包括分配给该进程的内存、内核数据结构和软资源形成一个进程核（core）。核快照（core image）代表的是进程在某一特定时刻的状态。 如果在Linux或UNIX操作系统下编写程序，在出现分段错误（segmentation fault）时，操作系统会自动进行核倒出（core dump）。“核倒出”把所有计算机的状态保存在一个文件中，通过阅读这个文件的内容可以得知溢出时的进程状况，从而帮助调试程序。 进程与进程之间可以通信、同步、竞争，并在一定情况下可能形成死锁。内存是操作系统里面的另一个核心概念。它是进程的存放场所。如何对内存进行管理，使得数据的读写具有高效率、高安全、高空间利用率和位置透明的特性是内存管理所要达到的目的。 ==文件是操作系统提供的外部存储设备的抽象，它是程序和数据的最终存放地点。==如何让用户的数据存放变得容易、方便、可靠和安全是文件系统要解决的问题。

## 进程原理 ##

顾名思义，计算机是用来进行计算的，或者说计算机的基本功能是计算功能。而进行计算的关键部件是计算机的芯片，即CPU。CPU能够按照一定的顺序进行正确计算是在一个指挥者的控制之下完成的。这个指挥者就是操作系统。操作系统对CPU进行管理的重要手段就是进程模型，或者说进程是操作系统这个魔术师施法的道具。 进程是操作系统演化过程中的一个里程碑，由于进程的出现，人类希望的并发从理想变为了现实。从根本上说，进程出现的动机是人类渴望的并发。进程的出现也让操作系统的复杂性大为增加：由于需要对进程进行分离存储而导致出现内存管理；由于需要让不同进程有条不紊地往前推进而导致进程调度的出现。显然，理解进程对理解操作系统十分重要，对其进行管理也就理所当然地成为操作系统的一个关键职责。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]  
进程从根本上说是操作系统对CPU进行的抽象和装扮

那么什么是进程呢？顾名思义，进程就是进展中的程序，或者说进程是执行中的程序。就是说，一个程序加载到内存后就变为进程。即： 进程=程序+执行 进程在Multics操作系统出现前叫做工作（job）。工作是IBM用于多道批处理程序设计中的概念。由于历史的原因，Multics操作系统的研发人员不愿意承用IBM发明的术语，而将工作改为了进程（process）。那么进程出现的动机是什么呢？ 什么是进展中的程序呢？  
从物理内存的分配来看，每个进程占用一片内存空间，从这点上说，进程就是内存的某片空间。由于在任意时刻，CPU只能执行一条指令，因此任意时刻在CPU上执行的进程只有一个，而到底执行哪条指令由物理程序计数器指定。也就是说，在物理层面上，所有进程共用一个程序计数器。 而从逻辑层面上来看，每个进程可以执行，也可以暂时挂起让别的进程执行，之后又可以接着执行。这样，进程就需要某种办法记住每次挂起时自己所处的执行位置，这样才能在下次接着执行时从正确的地点开始。因此，从这个角度看，每个进程有着自己的计数器，记录其下一条指令所在的位置。从逻辑上说，程序计数器可以有很多个。 而从时间上看，每个进程都必须往前推进。在运行一定的时间后，进程都应该完成了一定的工作量，即每次进程返回，它都处在上次返回点之后。这就像古希腊哲学家赫拉克里特说过的：“一个人不能两次踏入同一条河流。  
对于操作系统来说，进程是其提供的一种抽象，目的是通过并发来提高系统利用率，同时还能缩短系统响应时间。这种抽象听上去很不错。但这种抽象是如何实现的呢？或者说，操作系统如何实现进程呢？ 首先，任何抽象都需要有一个物理基础。对于进程来说，其物理基础就是程序。程序运行在计算机上，而在计算机上运行首先需要解决的问题是进程的存储：给进程分配合适的内存，让其有一个安身之处。由于多个进程可能同时并存，因此进程的存储需要考虑如何让多个进程共享同一个物理内存而不发生冲突。操作系统解决这个问题的手段是内存管理。 此外，进程运行实际上是指进程在CPU上执行。那么如何将CPU在多个进程之间进行交接或切换，这就是进程实现需要解决的另一个问题。操作系统解决这个问题的手段就是进程调度：决定在什么时候让什么进程使用CPU

多道编程的好处  
人们发明进程是为了支持多道编程，而进行多道编程的目的则是提高计算机CPU的效率，或者说系统的吞吐量。例如，如果一个进程有20%的时间使用CPU进行计算，另外80%的时间用来进行I/O，则如果使用单道编程，CPU的利用率只有20%。但如果同时运行两个这样的进程，即进行所谓的2道编程，则CPU利用率将提高到36%（CPU只在两个进程同时进行I/O时才处于闲置状态，因此CPU的利用率为1-0.8×0.8=36%）。这里忽略了进程切换所需要的系统消耗。

## 进程的状态 ##

我们前面说过，进程可以在CPU上执行，也可以处于挂起状态。显然，一个进程至少有这么两种状态。那么进程还有别的状态吗？ 如果进程在CPU上执行，自然就是执行状态。而如果是挂起状态呢？那就得看是什么原因挂起的。因为操作系统在进行进程调度时要从挂起的进程中选择一个来执行，所以清楚一个进程挂起的原因对调度的有效推进十分重要。 那么进程挂起有哪些原因呢？首先是一个进程在运行过程中执行了某种阻塞操作，如读写磁盘由于阻塞操作需要等待结果后才能继续执行，因此操作系统将把这个进程挂起，让其他进程运转。另外一种情况是一个进程执行的时间太长了，为了公平，操作系统将其挂起，让其他进程也有机会执行。 这两种挂起的原因十分不同：第一种挂起是进程自身的原因。这个时候，即使把CPU控制权交给它，它也无法运行。第二种挂起是操作系统的原因。进程自己并无问题。只要把CPU交给进程，它就可以立即运行。这样，如果将挂起进程分为这样两类，操作系统在进程调度时就只需要查看第二类进程，而无须浪费时间查看第一类进程。 因此，将进程分为3种状态：执行、阻塞和就绪，如图4-5所示。 在3种状态之间可以进行各种转换。如果每个状态都可以转换为另外一种状态，则一共有6种转换：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 2]  
★ 执行→就绪  
★ 执行→阻塞  
★ 阻塞→就绪  
★ 就绪→执行  
★ 阻塞→执行  
★ 就绪→阻塞  
问题是，上面的转换并不是都可以发生。一个进程在执行时，因为运行时间太长，操作系统可以将其挂起，转换为就绪状态，因此第1种转换是可以的。在进程执行过程中如果执行了某种阻塞操作，则进入阻塞状态，因此第2种转换也是可以的。一个阻塞的进程在其等待的资源到达后，就可以随时执行，进入就绪状态，因此第3种转换也是可以的。最后，就绪进程由操作系统调度到CPU上就进入执行状态，因此第4种转换也是可以的。 但是第5、第6两种转换是不可以的。我们前面讲过，阻塞进程即使被给予CPU，也无法执行，因此操作系统在调度时并不会在阻塞队列里挑选。因此，阻塞状态无法转换为执行状态。对于处于就绪状态的进程来说，因为它并没有执行，自然无法进入阻塞状态。这就像一个人停滞不前，自然就不会有任何人成为其障碍。因此，就绪状态无法转换为阻塞状态

## 操作系统管理进程 ##

与一个社会管理人的过程类似，操作系统要管理进程就要维护关于进程的一些信息。当一个进程产生时，操作系统也需要为其创建记录。操作系统用于维护进程记录的结构就是进程表或进程控制块（Process Control Block, PCB）。这个进程表或PCB中存放的就是有关该进程的资料。那么进程表里有什么资料呢？显然，不同的操作系统维护的进程资料不尽相同。但一般来说，维护的资料信息应当包括寄存器、程序计数器、状态字、栈指针、优先级、进程ID、信号、创建时间、所耗CPU时间、当前持有的各种句柄等。而采纳的数据结构主要是线性表、链表和结构（struct），当然也可能使用树和图（网络）结构。例如，Solaris的进程表就使用了上述4种数据结构。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 3]

进程创建在不同的操作系统里方法也不一样。例如，**UNIX将进程创建分为两个步骤：第1步是fork，创建一个与自己完全一样的新进程；第2步是exec，将新的进程的地址空间用另一个程序的内容覆盖，然后跳转到新程序的起始地址，从而完成新程序的启动**。而Windows使用一个系统调用就可以完成进程创建。这个系统调用就是CreateProcess。在调用该函数时我们把欲执行的程序名称作为参数传过来，创建新的页表，而不需要复制别的进程。 UNIX和Windows的进程创建过程各有优缺点。UNIX的创建过程要灵活一些，因为我们既可以自我复制，也可以启动新的程序。而自我复制在很多情况下是很有用的。例如，Web服务器在每收到一个用户请求后，就创建一个新的一模一样的进程来服务用户请求。而在Windows下，复制自我就要复杂一些了。而且，共享数据只能通过参数传递来实现。

--------------------

## 进程调度 ##

进程的调度就是操作系统进程管理的一个重要组成部分。其任务是选择下一个要运行的进程。那么如何进行选择呢？要探明这一点，首先需要确定操作系统进程调度的目标是什么。有了目标，我们就知道选择什么进程最合适了。 那么操作系统进程调度的目标是什么呢？这需要对进程使用CPU的模式进行分析。那么进程在执行时有什么样的模式呢？

一般来说，程序使用CPU的模式有3种：一种是程序大部分时间在CPU上执行；另一种是程序大部分时间在进行输入输出；还有一种是程序介于前两种模式之间。  
第1种程序运行的模式是在CPU上执行较长时间，接着进行短暂的输入，然后又在CPU上进行较长的运算，之后又进行短暂的输入输出操作，就这样循环往复。这种程序由于使用CPU的时间远远长于其用于输入输出上的时间，因此称为CPU导向（CPU-bound）或计算密集型程序。计算密集型程序通常是科学计算方面的程序。计算宇宙大爆炸各种参数的程序、矩阵乘法程序等就都是CPU导向的程序。  
第2种程序则与第1种相反，这种程序的大部分时间用来I/O，每次I/O后进行短暂的CPU执行，因此称为I/O导向（I/O-bound）或输入输出密集型程序。一般来说，人机交互式程序均属于这类程序。如游戏程序以及讲课时使用的PPT程序，都属于I/O导向的程序。  
第3种程序自然介乎二者之间，既有长时间的CPU执行部分，又有长时间的I/O部分。或者说，这种程序使用CPU和I/O的时间相差不大。这种程序称为平衡型程序。例如，网络浏览或下载、网络视频等就属于此类程序。 自然，对于不同性质的程序，调度所要达到的目的也有所不同。例如，对于I/O导向的程序来说，响应时间非常重要；而对于CPU导向的程序来说，周转时间（turnaround）就比较重要；对于平衡型程序来说，进行某种响应和周转之间的平衡就显得重要。

CPU调度就是要达到极小化平均响应时间、极大化系统吞吐率、保持系统各个功能部件均处于繁忙状态和提供某种貌似公平的机制。 极小化平均响应时间就是要极小化用户发出命令和看到某种结果之间所花费的时间，即减少做一件工作平均等待的时间；极大化系统吞吐率就是要在单位时间内完成尽可能多的程序，就是单位时间内能完成的工作数量，即整个系统运行效率高；保持系统各个功能部件繁忙就是要让CPU和输入输出设备均处于忙碌状态。由于CPU非常昂贵，让其闲置显然是一种浪费，因此保持CPU繁忙十分重要。就像生命非常珍贵，因此要一直保持学习繁忙状态，才能不浪费生命。 提供公平就是要让各个程序感到某种“平等”，即在CPU面前“人人平等”。公平是任何系统都应该努力达到的目标。因为没有公平，该系统对用户的吸引力就会急剧下降。这就像一个国家或者社会，如果缺乏公平，公民对该国家的认同度就会急剧下降一样。 对于不同的系统来说，在调度目标方面也有一些细微的不同。例如，对于批处理系统来说，由于用户并不坐在计算机前面等待结果，响应时间就显得不太重要，但系统吞吐率、CPU利用率和周转时间则很重要。 对于交互式系统来说，由于用户在等待计算机，因此响应时间要很快。但在这里要注意的是适度性（proportionality）。适度性就是响应时间要和期望值相匹配。这里是说你不要超越用户的期望。比如，用户期待1秒钟的响应时间，你就给他1秒钟的响应时间，而不必提供0.1秒钟的响应时间。这是因为，提供超出用户期望的响应会增加系统设计的难度，而又不会提高用户的满意度（对于一个人来说，1秒钟和0.1秒钟的差别并不是很大）。 对于实时系统来说，调度就是要达到在截止时间前完成所应该完成的任务和提供性能可预测性。

## 调度算法 ##

### 1.先来先服务调度算法 ###

缩写为FCFS（First Come First Serve）。谁先来，就先服务谁。这个算法所有地球人都能想到。因为先来先到是人的本性中的一种公平观念，而且生活实际中这种规则随处可见。例如，我们排队买东西或者办理政务体现的就是先来先到原则。 先来先到的一个隐含条件就是不能抢占，一个程序一旦启动就一直运行到结束或者受阻塞为止。这是因为一旦允许抢占，就破坏了先来先到的原则。先来先到的优点就是简单，人人都能理解，实现起来容易。而缺点则是短的工作有可能变得很慢，因为其前面有很长的工作。这样就造成用户的交互式体验也比较差。例如，现在有两个程序：A需要运行100秒，B需要运行1秒。A程序与B程序几乎同时启动，但B就是慢了一点儿，排在A之后执行，则需要等待100秒。这样A的响应时间为100秒，而B的响应时间则为101秒，从而，平均响应时间100.5秒。那么响应时间非常慢。就像我们排队办理事情，你要办理的事情只要几分钟就可办好，而你前面的一个人办理的事情因为复杂需要1个小时。这个时候你要等在他后面就十分不高兴。这个时候你就想，要是每个人轮流办理10分钟事务的话，那多好呀。  
自然，研究进程调度的人也想到了这一点，而这种轮流办理的调度方式就是时间片轮转。

### 2.时间片轮转算法 ###

时间片轮转算法是对FCFS算法的一种改进，其主要目的是改善短程序的响应时间。其方法就是周期性地进行进程切换。例如，每1秒钟进行一次进程轮换。这样，短程序排在长程序后面也可以很快得到执行。因此长程序执行1秒后就得把CPU让出来。这样整个系统的响应时间就得到了改善。以前面的A、B程序为例，A需要运行100秒，B需要运行1秒。使用FCFS时系统平均响应时间为100.5秒。而使用时间片轮转，则A在执行1秒后，CPU切换到进程B，在执行1秒后，B结束，A接着执行99秒。这样A的响应时间是101秒，而B的响应时间为2秒。系统的平均响应时间是51.5秒。这显然比FCFS的效率强多了。 仔细的读者可能已经看出，系统响应时间依赖于时间片的选择。我们因为选择了1秒钟的时间片，上述系统的响应时间是51.5秒。如果时间片是10秒钟，则上述系统的平均响应时间将是65秒。如果选择别的时间片，则响应时间还将不同。那我们自然想知道，到底选择多大的时间片才合适呢？ 显然，如果选择的时间片过大，时间片轮转将越来越像FCFS，当选择的时间片超过任何一个程序所需要的执行时间长度时，则完全退化为FCFS。而如果选择的时间片过小，则进程切换所用的系统消耗将太多，使得系统的大部分时间花在进程的上下文切换上，而用来真正执行程序的有用时间很少，从而降低系统效率，并造成浪费。

那如何选择一个合适的时间片呢？做研究。我们需要知道进行一次进程切换所用系统消耗和我们能够承受的整个系统消耗，就可以得出合适的时间片。例如，如果每次进程切换需要消耗0.1毫秒的CPU时间，则选择10毫秒的时间片将浪费约1%的CPU时间在上下文切换上；如果选择5毫秒的时间片，则浪费约为2%；20毫秒的时间片，则浪费约为0.5%。如果我们能够承受的CPU浪费为1%，则选择10毫秒的时间片就很合理。

### 3.短任务优先算法 ###

那么时间片轮转真的那么公平吗？当然不是。如果每个人的能力一样，大家轮流坐庄当然比较公平，问题是每个人的能力并不完全一样。让一个能力很差的人与一个能力很好的人轮流执政恐怕没有多少人会同意。我们不是因为不满大锅饭而提出让一部分人先富起来吗？而时间片轮转就是大锅饭！

从前面可以看出，时间片轮转改善了所谓的系统响应时间的论断也不一定经得起推敲。更为重要的是，时间片轮转所达到的系统响应时间并不是我们所能达到的响应时间下限。如果有30个用户，其中一个用户只需要1秒钟时间执行，而其他29个用户需要30秒钟执行，如果因为某种原因，这个只要1秒钟的程序排在另外29个程序的后面轮转，则它需要等待29秒钟才能执行（假定时间片为1秒）。这个程序的响应时间和交互体验就变得非常差。 那要改善短任务排在长任务后面轮转而造成响应时间和交互体验下降的办法就是短任务优先（Shorted Time to Completion First, STCF）算法。这种算法的核心是所有的程序并不都一样，而是有优先级的区分。具体来说，就是短任务的优先级比长任务的高，而我们总是安排优先级高的程序先运行。就像晚辈在公交汽车上见到长辈需要让座一样。 短任务优先算法有两个变种：任务优先算法的原理是让已经在CPU上运行的程序执行到结束或阻塞，然后在所有候选的程序中选择需要执行时间最短的进程来执行。抢占式短任务优先算法则是每增加一个新的进程就需要对所有进程（包括正在CPU上运行的进程）进行检查，谁的时间短，就运行谁。 显然，由于短任务优先总是运行需要执行时间最短的程序，因此其系统平均响应时间在目前已经讨论过的几种调度算法里面是最优的。这就是STCF算法的优点。事实上，在所有非抢占调度算法中，STCF算法的响应时间最优。而在所有抢占调度算法中，抢占式STCF算法的响应时间最优。一种是非抢占，一种是抢占。非抢占短任务优先算法的原理是让已经在CPU上运行的程序执行到结束或阻塞，然后在所有候选的程序中选择需要执行时间最短的进程来执行。抢占式短任务优先算法则是每增加一个新的进程就需要对所有进程（包括正在CPU上运行的进程）进行检查，谁的时间短，就运行谁。  
但STCF调度算法也有缺点。第一是可能造成长程序无法得到CPU时间而导致“饥饿”。除此之外，还有一个重大缺点，就是我们怎么知道每个进程还需要运转多久？难道我们能够预测将来不成？就好像你第一次做某种事情时怎么知道需要多长时间呢？ 这个时候就需要做研究！我们可以用一些启发式（heuristic）方法来进行估算，例如，根据程序大小来推测一个程序所需CPU执行时间。但这个方法并不可靠。另外一个办法就是先将每个程序运行一遍，记录其所用CPU时间，这样在以后的运行中，即可根据这个实测数据来进行STCF调度了。

### 4.优先级调度算法 ###

前面介绍的STCF算法有一个缺点是可能造成长进程“饥饿”。但这个问题比较容易解决，使用优先级即可。优先级调度算法的原理是给每个进程赋予一个优先级，每次需要进程切换时，找一个优先级最高的进程进行调度。这样，如果赋予长进程一个高优先级，则该进程就不会再“饥饿”。事实上，STCF算法本身就是一种优先级调度，只不过它给予短进程高优先级而已。 优先级调度的优点是可以赋予重要的进程以高优先级以确保重要任务能够得到CPU时间。其缺点则与STCF算法一样，低优先级的进程可能会“饥饿”。不过，这个问题在优先级调度算法里比在STCF里好解决：只要动态地调节优先级即可。例如，在一个进程执行特定CPU时间后将其优先级降低一个级别，或者将处于等待进程的优先级提高一个级别。这样，一个进程如果等待时间很长，其优先级将因持续提升而超越其他进程的优先级，从而得到CPU时间。这样，“饥饿”现象就可以防止。 不过，优先级调度还有一个缺点，就是响应时间不能保证，除非将一个进程的优先级设置为最高。即使将优先级设置为最高，但如果每个人都将自己进程的优先级设为最高，则响应时间还是无法保证。

### 5.混合调度算法 ###

之前介绍的所有算法都存在缺点，我们自然想设计一个算法合并它们的优点，摒弃它们的缺点。这就是所谓的混合调度算法。该算法的原理是将所有进程分成不同的大类，每个大类为一个优先级。如果两个进程处于不同的大类，则处于高优先级大类的进程优先执行；如果两个进程处于同一个大类，则采用时间片轮转来执行。混合调度算法的示意图如图5-3所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 4]

自然，CPU调度算法并不只有上面介绍的几种。由于不同系统的目标不同，不同进程的性质和重要性不同，因此进程调度也就不同。事实上，调度算法非常多，有兴趣的读者可以参阅有关调度方面的大量论文。

## 进程调度的过程 ##

前面的内容讨论了进程调度的含义及各种调度算法，但调度一个进程对于操作来说意味着什么却并没有解释。那么在更换进程的时候到底有哪些操作需要完成呢？首先，当然需要将当前进程的状态予以保护，以便将来能够重新执行。然后是将选中的进程的环境布置好，这包括设置寄存器、栈指针、状态字等操作。最后是跳转到选中的进程，也就是设置或恢复其程序计数器。下面给出的是调度进程时操作系统所执行的操作概览： ★ 因时序或外部中断或进程挂起而导致操作系统获得CPU控制权。  
★ 操作系统在所有就绪的进程中按照某种算法遴选进程。  
★ 如果选中的是非当前进程，则操作系统将当前进程（中断或挂起的进程）状态予以保护。  
★ 将选中的进程的环境布置好（设置寄存器、栈指针、状态字等）。  
★跳转到选中的进程

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20220829/5224d761b7954a79b5fb26ef369c2129.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]: /images/20220829/96226198f13d41789ee6949b15a04ed4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 2]: /images/20220829/59ff7aa5665748edbd25e2b92055c467.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 3]: /images/20220829/06adc0420b95492a85ee00438ff9abcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 4]: /images/20220829/dae053c84e164bab8d5c411456f4ce00.png