本篇将会介绍进程调度、中断、内存管理，本篇是本系列的最后一篇，完毕后将会开启操作系统的IO讲解

进程调度

Dos系统与进程调度

• 我们都知道，Dos系统是无法运行多个程序的，同一时间只能有一个程序可以运行
• 但是只有一个程序使用CPU，这样无法完全压榨出CPU的性能，为了提高效率，人们开始考虑多任务执行

多任务(MultiTask)调度的概念

• 多任务调度有两种不同的调度方式

  1. 非抢占式

     这种调度策略之下，只要一个进程占据了CPU资源，那么只要这个进程不主动释放CPU资源，那么这个进程占有的CPU资源就不会被其他进程抢占，其他进程只能等着

  2. 抢占式

     在这种调度策略之下，一个进程的CPU占有资源是可以被内核管理的

Linux 2.5 的进程调度

• 在 Linux 2.5 版本的时代，内核的调度策略是经典Unix的O(1)策略，内核会按照时间片将CPU资源平均分配给其他所有的进程，例如我们的时间片为10ms，那么内核就会按照10ms一个间隔轮流地将不同的进程拿到CPU中去执行。

  这种调度策略对于服务器交互友好，但是对于用户交互来说不友好

• O(1)调度策略的特点

  • 对服务器友好

    当不同的客户端尝试连接服务器的时候，这个服务器会公平地分配资源给客户端，保证每一个客户端连接都有同样的执行时间，这就是对服务器友好

  • 对用户交互不友好

    我们可以想象，当一个用户在一个图形化界面中点击了一个按钮后总要停顿一会儿才给响应，这会让人非常的烦，这就是对用户交互不友好

  • 存在时间片浪费

    如果我们有一个线程的执行时间为5ms，但是却被线程赋予了10ms的时间片，这样就会有资源的浪费

Linux 2.6.23 的线程调度

• 从2.5版本到现在的版本，中间经历了十几年的时间，在这段时间内，内核不断地发展，而2.6.23版本就是我们现代Linux操作系统的进程调度策略

• 完全公平调度算法(Completely Fair Schedule，CFS)

  • 这个算法其实非常的简单，但是却是Linux调度策略的核心之一，这个算法的逻辑就是：每一个进程都有自己的虚拟时钟（vruntime），当一个进程处于执行状态的时候，这个进程的vruntime就会累加，如果这个进程没有处于执行状态的话，这个进程的vruntime就不会变动。每一次内核执行的时候都会挑选vruntime较小的进程执行

• Linux进程的分类

  • 从Linux角度来说，进程只会有两种分类

    1. 普通进程

       普通进程执行的调度策略就是SCHEDULE_NORMAL，这个调度策略的实现就是依靠的CFS来实现的

       普通进程之间也是有优先级(-15~20)的差距的，不同的优先级也会对进程的vruntime造成影响，最后的结果就是优先级越高，就可以得到更多的执行时间

    2. 实时进程

       实时进程和普通进程有一个差距，就是所有实时进程的优先级都要比普通进程高，如果有一个实时进程和普通进程同时争用cpu资源的话，那么肯定是实时进程得到CPU资源，并且直到实时进程结束之前，普通进程都无法得到CPU资源

       实时进程执行的调度策略有两种，并且是根据不同的优先度来选择的，分别是SCHEDULE_FIFO、SCHEDULE_RR

       当两个实时进程的优先级不同时那么这么两个进程之间就会执行SCHEDULE_FIFO，也就是优先级越高越先执行，并且直到优先级高的线程执行完毕之前，优先级低的线程都无法得到CPU资源

       当两个实时进程的优先级相同的时候，执行的调度策略就是SCHEDULE_RR，优先级相同的进程之间以轮询的方式共享CPU资源

  • 除了Linux角度以外，程序员也从自己的角度对进程进行了分类

    1. IO密集型：这种进程大部分时间都花费在IO上面，花了很多时间来等待磁盘中返回的资源
    2. 计算密集型：这种进程的大部分时间都花费在计算上面

操作系统的中断

中断的简单介绍

• 操作系统的中断是非常复杂的过程，我们这里只会做简单的介绍

操作系统中断的实例

• 我们自己在使用操作系统的时候经常会出现某一个程序卡死的情况，这个时候如果我们一直不断地点击鼠标，或者不断地敲击键盘，那么我们的电脑就有可能弹出一个弹窗，这个弹窗会询问我们是否要中断程序，这就是一个中断的实例

中断的分类

中断的类型一般被分为两种，是从不同角度来分析的

1. 内中断：内中断的信号来源于CPU内部、与当前执行的指令有关。如整数除0。这种一般也被称为软中断
2. 外中断：外中断的信号来源于CPU外部、与当前执行的指令无关。如用户强制结束一个进程、IO设备完成操作发生的中断信号。这种也一般被称呼为硬中断

中断的过程

1. 执行完每个指令后，CPU都要检查当前是否有外部中断信号。
2. 如果检测到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSW、程序计数器、各种通用寄存器）。
3. 根据中断信号类型转入相应的中断处理程序。
4. 恢复进程的CPU环境并退出中断，返回原进程继续往下执行。

操作系统内存管理之分页

操作系统的分页发展历史

• 最开始的时候，我们都是使用的Dos系统，Dos系统只能同时支持运行一个程序，但是这对CPU的效率利用无法达到最大，这是一种非常浪费的现象，为了解决这一状况，人们开始尝试让操作系统中可以跑多个进程
• 在当时，操作系统的大小都不大，别说内存中要跑多个程序了，能够完整地跑起来一个就已经谢天谢地了，如果要装下多个进程的话就会出现内存撑爆的现象
• 在这个时候，就有一个人想出了一个解决方法——分页

分页的逻辑

• 当我有一个操作系统，准备在这个里面跑几个程序，那么当我把程序双击开始执行的时候，在物理地址里面其实是没有一次性将所有的程序内容加载进入操作系统中的，他是将一个完整的程序划分成了一个个的块儿，这个块儿的默认大小就是4k，并且在内存中也会将内存划分成为一个个的块儿，每一块儿的默认大小也是4k。将程序划分出来的块儿叫做分页，把内存划分出来的块儿叫做页框

  

• 当我们的一个程序需要执行的时候，例如qq.exe需要执行，qq.exe的主方法在第3块儿，于是操作系统就会将第3块儿加载到内存中然后执行，如果第3块儿用到了第4块儿的话就会把第4块儿也加载到内存中，这样就实现了用什么就加载什么的结构，这样让内存可以尽可能运行更多的进程

LRU算法与分页交换技术

• 当我们的内存已经满了的时候，我们又需要将一个分页加载到内存中，这个时候我们就要使用分页交换技术了
• 分页交换技术的核心算法就是LRU（Least Recently Used），当一个新的分页想要添加进入内存却发现内存已经满了的时候，我们会将内存中最不常用的分页加入到swap分区中，然后将新的分页放入内存中。这个swap空间就存在于硬盘空间，而这个就是LRU算法的逻辑

LUR算法的实现

• LRU算法可谓是经典中的经典，很多大厂的面试都要求手撕，leetcode的146题也是LRU算法，只要有缓存的地方就有LRU，这里我们就来详细解释通过演进的方式来讲解LRU算法

  1. 版本1

     我们完全可以用一个容器来装分页对象，这个对象里面可以保存这个对象最近被使用的信息，这样其实就可以实现基础的LRU，如果我们容器满了，想要继续分页交换的时候，只需要按照这个容器顺序遍历一遍，找到最不常使用的分页对象，将它放到swap区，然后把新的分页对象装到容器中就可以了

     版本1理论上是可以使用的，但是我们可以明显感受到这个方案的缺点——

     • 从容器中找到分页对象的时间复杂度为O(n)，如果想要找到一个分页对象，就只能从头到尾遍历一遍，没有其他办法
     • 线性表对空间的利用天生有缺陷，如果我们的某个分页不需要使用了，把他清理出内存，那么在线性表中就会出现一个窟窿，如果新的分页想要填下这个窟窿，就需要遍历线性表来找窟窿，如果想要提升效率，不遍历直接在最后面添加，就会非常浪费空间

  2. 版本2

     我们如果想要解决版本1的缺点的话，我们完全可以使用HashMap+LinkedList的方式来解决，我们首先维护一个HashMap，这个HashMap的Key就是分页对象的标识，类似hash、id之类的，value中就保存了这个对象的物理地址，这样就可以通过map以O(1)的时间复杂度完成分页对象的查找。

     我们还可以利用链表结构调整位置的快速的特性，只要保证链表的头部永远是最不常使用的分页，那么在更换分页的时候就可让链表的头部直接进入swap分区，然后让新的分页直接添加到链表的末尾

     版本2已经比较不错了，但是还是存在一个问题

     • 如果某一个分页对象被再次使用了，需要将这个对象从链表的其他位置切换到链表最末尾，但是一个链表中的Node的位置转移是需要知道这个Node的pre的，如果我们使用单向链表，在改动节点的位置的时候时间复杂度还是O(n)

  3. 版本3

     我们如果想要解决版本2的问题其实非常简单，只要把单向链表改动成为双向链表就可以完美解决，而这也是Linux底层的LRU算法的实现

操作系统内存管理之虚拟地址

虚拟地址发展史

• 当人们通过分页技术解决了内存撑爆问题后，还有一个问题一直困扰着人们，那就是进程间的相互打扰。
• 在以前，所有的程序都跑在了内存中，大家都知道自己是内存中众多程序的一个，知道自己真实物理地址的位置，在那个时代的操作系统，例如win98，你一天不死机个几次都不好意思说自己是win98。
• 这是因为，大家都知道自己在内存中的物理地址，非常有可能出现的事情就是我这个程序将我的数据写到了操作系统的空间中，这样就会导致操作系统直接崩溃
• 为了解决这个问题，人们引入了虚拟地址

虚拟地址简介

• 在引入了虚拟地址的概念后，跑在操作系统中的程序就再也无法知道自己在物理内存中的真实地址了。
• 操作系统给程序营造出了一种假象——整个操作系统中只有这一个程序在运行，所有的内核资源都归它独享

虚拟地址讲解前的一些知识补充

1. CPU如何识别指令和数据

   我们平时说的总线总线，以为就只有一条，其实这是不对的，总线可以分为简单分成三种

   1. 数据总线：可以简单理解，数据总线就是用来传输数据的
   2. 地址总线：顾名思义，这个总线传输的都是地址
   3. 控制总线：用来传输控制信号和传输信号的

   CPU怎么知道传来的是什么类型的数据？就是通过识别不同的总线来判断的，从数据总线来的就当成数据；从地址总线来的就作为地址；从控制总线来的就作为控制信号

   ps：为什么32位系统的最大内存容量为4G？那是因为32位系统的地址总线最大只能同时传输32位bit，也就是说32位系统的最大寻址宽度就是2^32次方个位置，在内存中，基本的单位就是字节（byte），也就是说，32位的系统可以最大描绘出2^32次方个地址，每一个地址的容量是一个字节，也就是说这个32位系统的地址总线一次性可以最多表示2^32 Byte，折合GB就是4GB

   pps：既然32位的系统最大内存容量为4G，那么64位系统的最大寻址空间是不是2^64字节？是，也不是，说是的原因是，理论上是可以支持2^64字节，但是因为2^64次方寻址空间实在太大了，市面上没有一台机器有这么大的内存，于是这些计算机生产的厂商就“偷工减料”，地址总线最高只有48位，折合有256T

2. 程序分段

   一个硬盘中的程序其实是被分成了非常多段的，这是在编译阶段完成的，这会让程序更加的方便管理

3. 逻辑地址、线性地址、物理地址

   逻辑地址是一个分页在数据段中的地址，例如这个分页在数据段中的第一位，这个分页的逻辑地址就是0

   线性地址就是这个分页的基地址+逻辑地址，基地址就是这个程序的数据段位置

   物理地址就是这个分页真正的位置，这个位置是以线性地址为基础，通过MMU模块来进行转换的，MMU就是Memory Manage Unit，这个转换的过程非常麻烦，我们称呼为内存映射，通过内存映射就可以将线性地址变为真正的物理地址，这个物理地址只有内核知道，进程自己是不知道的

虚拟地址

• 虚拟地址就是一个程序被分配到一个虚拟出来的空间，程序会以为这个空间是专属于自己的，在这片空间分配自己的地址，但是这个分配的地址不是真实存在的，这篇地址是虚拟的。这片虚拟的地址可以通过MMU进行内存映射，将虚拟地址映射成为真正的物理地址，这样就可以保证多个进程之间无法相互打扰，极大提升了安全性