Day 13
1. 虚拟内存
单片机是没有操作系统的，所以每次写完代码，都需要借助工具把程序烧录进去，这样程序才能跑起来。
另外，单片机的 CPU 是直接操作内存的物理地址。
在这种情况下，如果第一个程序在 2000 的位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容，所以同时运行两个程序是根本行不通的，这两个程序会立刻崩溃。
操作系统是如何解决这个问题呢？
这里关键的问题是两个程序都引用了绝对物理地址，而这正是最需要避免的。
可以把进程所使用的地址隔离开，即让操作系统为每个进程分配独立的一套虚拟地址，互不干涉。但是有个前提每个进程都不能访问物理地址，至于虚拟地址最终怎么落到物理内存里，对进程来说是透明的，操作系统已经把这些都安排的明明白白了。
操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。
如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。
于是，这里就引出了两种地址的概念：
- 程序所使用的内存地址叫做虚拟内存地址（Virtual Memory Address）
- 实际存在硬件里面的空间地址叫物理内存地址（Physical Memory Address）。
操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存，如下图所示：
操作系统通过内存分段和内存分页管理虚拟地址与物理地址之间的关系， 内存分段较早提出。
内存分段
程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来。
分段机制下，虚拟地址和物理地址是如何映射的？
分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量。
-
段选择因子就保存在段寄存器里面。段选择因子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
-
虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。
在上面，知道了虚拟地址是通过段表与物理地址进行映射的，分段机制会把程序的虚拟地址分成 4 个段，每个段在段表中有一个项，在这一项找到段的基地址，再加上偏移量，于是就能找到物理内存中的地址，如下图：
如果要访问段 3 中偏移量 500 的虚拟地址，可以计算出物理地址为，段 3 基地址 7000 + 偏移量 500 = 7500。
分段的办法很好，解决了程序本身不需要关心具体的物理内存地址的问题，但它也有一些不足之处：
- 第一个就是内存碎片的问题。
- 第二个就是内存交换的效率低的问题。
分段为什么会产生内存碎片的问题？
来看看这样一个例子。假设有 1G 的物理内存，用户执行了多个程序，其中：
- 游戏占用了 512MB 内存
- 浏览器占用了 128MB 内存
- 音乐占用了 256 MB 内存。
这个时候，如果关闭了浏览器，则空闲内存还有 1024 - 512 - 256 = 256MB。
如果这个 256MB 不是连续的，被分成了两段 128 MB 内存，这就会导致没有空间再打开一个 200MB 的程序。
内存分段会出现内存碎片吗？
内存碎片主要分为，内部内存碎片和外部内存碎片。
内存分段管理可以做到段根据实际需求分配内存，所以有多少需求就分配多大的段，所以不会出现内部内存碎片。
但是由于每个段的长度不固定，所以多个段未必能恰好使用所有的内存空间，会产生了多个不连续的小物理内存，导致新的程序无法被装载，所以会出现外部内存碎片的问题。
解决外部内存碎片的问题就是内存交换。
可以把音乐程序占用的那 256MB 内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，不能装载回原来的位置，而是紧紧跟着那已经被占用了的 512MB 内存后面。这样就能空缺出连续的 256MB 空间，于是新的 200MB 程序就可以装载进来。
这个内存交换空间，在 Linux 系统里，也就是常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换。
分段为什么会导致内存交换效率低的问题？
对于多进程的系统来说，用分段的方式，外部内存碎片是很容易产生的，产生了外部内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。
因为硬盘的访问速度要比内存慢太多了，每一次内存交换，都需要把一大段连续的内存数据写到硬盘上。
所以，如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。
为了解决内存分段的外部内存碎片和内存交换效率低的问题，就出现了内存分页。
内存分页
分段的好处就是能产生连续的内存空间，但是会出现外部内存碎片和内存交换的空间太大的问题。
要解决这些问题，那么就要想出能少出现一些内存碎片的办法。另外，当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点，这样就可以解决问题了。这个办法，也就是内存分页（Paging）。
分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，叫页（Page）。在 Linux 下，每一页的大小为 4KB。
虚拟地址与物理地址之间通过页表来映射，如下图：
页表是存储在内存里的，内存管理单元 （MMU）就将虚拟内存地址转换成物理地址。
而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。
分页是怎么解决分段的外部内存碎片和内存交换效率低的问题？
内存分页由于内存空间都是预先划分好的，也就不会像内存分段一样，在段与段之间会产生间隙非常小的内存，这正是分段会产生外部内存碎片的原因。而采用了分页，页与页之间是紧密排列的，所以不会有外部碎片。
但是，因为内存分页机制分配内存的最小单位是一页，即使程序不足一页大小，最少只能分配一个页，所以页内会出现内存浪费，所以针对内存分页机制会有内部内存碎片的现象。
如果内存空间不够，操作系统会把其他正在运行的进程中的最近没被使用的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。
更进一步地，分页的方式使得在加载程序的时候，不再需要一次性都把程序加载到物理内存中。完全可以在进行虚拟内存和物理内存的页之间的映射之后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。
分页机制下，虚拟地址和物理地址是如何映射的？
在分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址，见下图。
总结一下，对于一个内存地址转换，其实就是这样三个步骤：
- 把虚拟内存地址，切分成页号和偏移量；
- 根据页号，从页表里面，查询对应的物理页号；
- 直接拿物理页号，加上前面的偏移量，就得到了物理内存地址。
下面举个例子，虚拟内存中的页通过页表映射为了物理内存中的页，如下图：
这看起来似乎没什么毛病，但是放到实际中操作系统，这种简单的分页是肯定是会有问题的。
简单的分页有什么缺陷吗？
有空间上的缺陷。
因为操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大。
在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万 （2^20） 个页，每个页表项需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。
这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。
那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。
多级页表
要解决上面的问题，就要采用多级页表（Multi-Level Page Table）。
对于单页表的实现方式，在 32 位和页大小 4KB 的环境下，一个进程的页表需要装下 100 多万个页表项，并且每个页表项是占用 4 字节大小的，于是相当于每个页表需占用 4MB 大小的空间。
把这个 100 多万个页表项的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个页表项，形成二级分页。如下图所示：
分了二级表，映射 4GB 地址空间就需要 4KB（一级页表）+ 4MB（二级页表）的内存，这样占用空间不是更大了吗？
当然，如果 4GB 的虚拟地址全部都映射到了物理内存上的话，二级分页占用空间确实是更大了，但是，往往不会为一个进程分配那么多内存。
其实应该换个角度来看问题，还记得计算机组成原理里面无处不在的局部性原理么？计算机在执行某个程序时，倾向于使用最近使用的数据，即处理器在访问某些数据时短时间内存在重复访问，某些数据或者位置访问的概率极大，大多数时间只访问局部的数据。
每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。
如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？
为什么不分级的页表就做不到这样节约内存呢？
从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。
把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这一切都要归功于对局部性原理的充分应用。
对于 64 位的系统，变成了四级目录，分别是：
- 全局页目录项 PGD（Page Global Directory）；
- 上层页目录项 PUD（Page Upper Directory）；
- 中间页目录项 PMD（Page Middle Directory）；
- 页表项 PTE（Page Table Entry）；
TLB（Translation Lookaside Buffer）
多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。
程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。
可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们，就在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB ，通常称为页表缓存、转址旁路缓存、快表等。
在 CPU 芯片里面，封装了内存管理单元（Memory Management Unit）芯片，它用来完成地址转换和 TLB 的访问与交互。
有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。
TLB 的命中率其实是很高的，因为程序最常访问的页就那么几个。
段页式内存管理
内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为段页式内存管理。
段页式内存管理实现的方式：
- 先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
- 接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；
这样，地址结构就由段号、段内页号和页内位移三部分组成。
用于段页式地址变换的数据结构是每一个程序一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号，如图所示：
段页式地址变换中要得到物理地址须经过三次内存访问：
- 第一次访问段表，得到页表起始地址；
- 第二次访问页表，得到物理页号；
- 第三次将物理页号与页内位移组合，得到物理地址。
可用软、硬件相结合的方法实现段页式地址变换，这样虽然增加了硬件成本和系统开销，但提高了内存的利用率。
Linux 内存布局
那么，Linux 操作系统采用了哪种方式来管理内存呢？
先看看 Intel 处理器的发展历史。
早期 Intel 的处理器从 80286 开始使用的是段式内存管理。但是很快发现，光有段式内存管理而没有页式内存管理是不够的，这会使它的 X86 系列会失去市场的竞争力。因此，在不久以后的 80386 中就实现了页式内存管理。也就是说，80386 除了完成并完善从 80286 开始的段式内存管理的同时还实现了页式内存管理。
但是这个 80386 的页式内存管理设计时，没有绕开段式内存管理，而是建立在段式内存管理的基础上，这就意味着，页式内存管理的作用是在由段式内存管理所映射而成的地址上再加上一层地址映射。
由于此时由段式内存管理映射而成的地址不再是“物理地址”了，Intel 就称之为“线性地址”（也称虚拟地址）。于是，段式内存管理先将逻辑地址映射成线性地址，然后再由页式内存管理将线性地址映射成物理地址。
这里说明下逻辑地址和线性地址：
- 程序所使用的地址，通常是没被段式内存管理映射的地址，称为逻辑地址；
- 通过段式内存管理映射的地址，称为线性地址，也叫虚拟地址；
逻辑地址是段式内存管理转换前的地址，线性地址则是页式内存管理转换前的地址。
Linux 采用的管理内存的方式
Linux 内存主要采用的是页式内存管理，但同时也不可避免地涉及了段机制。
这主要是上面 Intel 处理器发展历史导致的，因为 Intel X86 CPU 一律对程序中使用的地址先进行段式映射，然后才能进行页式映射。既然 CPU 的硬件结构是这样，Linux 内核也只好服从 Intel 的选择。
但是事实上，Linux 内核所采取的办法是使段式映射的过程实际上不起什么作用。也就是说，“上有政策，下有对策”，若惹不起就躲着走。
Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间（32 位环境下），也就是所有的段的起始地址都是一样的。这意味着，Linux 系统中的代码，包括操作系统本身的代码和应用程序代码，面对的地址空间都是线性地址空间（虚拟地址），这种做法相当于屏蔽了处理器中的逻辑地址概念，段只被用于访问控制和内存保护。
Linux 的虚拟地址空间的分布
在 Linux 操作系统中，虚拟地址空间的内部又被分为内核空间和用户空间两部分，不同位数的系统，地址空间的范围也不同。比如最常见的 32 位和 64 位系统，如下所示：
通过这里可以看出：
32位系统的内核空间占用1G，位于最高处，剩下的3G是用户空间；64位系统的内核空间和用户空间都是128T，分别占据整个内存空间的最高和最低处，剩下的中间部分是未定义的。
再来说说，内核空间与用户空间的区别：
- 进程在用户态时，只能访问用户空间内存；
- 只有进入内核态后，才可以访问内核空间的内存；
虽然每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存。
接下来，进一步了解虚拟空间的划分情况，用户空间和内核空间划分的方式是不同的，内核空间的分布情况就不多说了。
以 32 位系统为例，用户空间分布的情况如下图：
通过这张图可以看到，用户空间内存，从低到高分别是 6 种不同的内存段：
- 代码段，包括二进制可执行代码；
- 数据段，包括已初始化的静态常量和全局变量；
- BSS段，包括未初始化的静态变量和全局变量；
- 堆段，包括动态分配的内存，从低地址开始向上增长；
- 文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关 (opens new window)）；
- 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是
8 MB。当然系统也提供了参数，以便自定义大小；
上图中的内存布局可以看到，代码段下面还有一段内存空间的（灰色部分），这一块区域是保留区，之所以要有保留区这是因为在大多数的系统里，认为比较小数值的地址不是一个合法地址，例如，通常在 C 的代码里会将无效的指针赋值为 NULL。因此，这里会出现一段不可访问的内存保留区，防止程序因为出现 bug，导致读或写了一些小内存地址的数据，而使得程序跑飞。
在这 7 个内存段中，堆和文件映射段的内存是动态分配的。比如说，使用 C 标准库的 malloc() 或者 mmap() ，就可以分别在堆和文件映射段动态分配内存。
总结
为了在多进程环境下，使得进程之间的内存地址不受影响，相互隔离，于是操作系统就为每个进程独立分配一套虚拟地址空间，每个程序只关心自己的虚拟地址就可以，实际上大家的虚拟地址都是一样的，但分布到物理地址内存是不一样的。作为程序，也不用关心物理地址的事情。
每个进程都有自己的虚拟空间，而物理内存只有一个，所以当启用了大量的进程，物理内存必然会很紧张，于是操作系统会通过内存交换技术，把不常使用的内存暂时存放到硬盘（换出），在需要的时候再装载回物理内存（换入）。
那既然有了虚拟地址空间，那必然要把虚拟地址映射到物理地址，这个事情通常由操作系统来维护。
那么对于虚拟地址与物理地址的映射关系，可以有分段和分页的方式，同时两者结合都是可以的。
内存分段是根据程序的逻辑角度，分成了栈段、堆段、数据段、代码段等，这样可以分离出不同属性的段，同时是一块连续的空间。但是每个段的大小都不是统一的，这就会导致外部内存碎片和内存交换效率低的问题。
于是，就出现了内存分页，把虚拟空间和物理空间分成大小固定的页，如在 Linux 系统中，每一页的大小为 4KB。由于分了页后，就不会产生细小的内存碎片，解决了内存分段的外部内存碎片问题。同时在内存交换的时候，写入硬盘也就一个页或几个页，这就大大提高了内存交换的效率。
再来，为了解决简单分页产生的页表过大的问题，就有了多级页表，它解决了空间上的问题，但这就会导致 CPU 在寻址的过程中，需要有很多层表参与，加大了时间上的开销。于是根据程序的局部性原理，在 CPU 芯片中加入了 TLB，负责缓存最近常被访问的页表项，大大提高了地址的转换速度。
Linux 系统主要采用了分页管理，但是由于 Intel 处理器的发展史，Linux 系统无法避免分段管理。于是 Linux 就把所有段的基地址设为 0，也就意味着所有程序的地址空间都是线性地址空间（虚拟地址），相当于屏蔽了 CPU 逻辑地址的概念，所以段只被用于访问控制和内存保护。
另外，Linux 系统中虚拟空间分布可分为用户态和内核态两部分，其中用户态的分布：代码段、全局变量、BSS、函数栈、堆内存、映射区。
虚拟内存有什么作用？
-
虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，可以把它换出到物理内存之外，比如硬盘上的 swap 区域。
-
由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。
-
页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。
2. 调度算法
进程调度算法
进程调度算法也称 CPU 调度算法，毕竟进程是由 CPU 调度的。
当 CPU 空闲时，操作系统就选择内存中的某个就绪状态的进程，并给其分配 CPU。
什么时候会发生 CPU 调度呢？通常有以下情况：
- 当进程从运行状态转到等待状态；
- 当进程从运行状态转到就绪状态；
- 当进程从等待状态转到就绪状态；
- 当进程从运行状态转到终止状态；
其中发生在 1 和 4 两种情况下的调度称为非抢占式调度，2 和 3 两种情况下发生的调度称为抢占式调度。
非抢占式的意思就是，当进程正在运行时，它就会一直运行，直到该进程完成或发生某个事件而被阻塞时，才会把 CPU 让给其他进程。
而抢占式调度，顾名思义就是进程正在运行的时，可以被打断，使其把 CPU 让给其他进程。那抢占的原则一般有三种，分别是时间片原则、优先权原则、短作业优先原则。
为什么第 3 种情况也会发生 CPU 调度呢？
假设有一个进程处于等待状态，但是它的优先级比较高，如果该进程等待的事件发生了，它就会转到就绪状态，一旦它转到就绪状态，如果的调度算法是以优先级来进行调度的，那么它就会立马抢占正在运行的进程，所以这个时候就会发生 CPU 调度。
那第 2 种状态通常是时间片到的情况，因为时间片到了就会发生中断，于是就会抢占正在运行的进程，从而占用 CPU。
调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），而不能影响进程真在使用 CPU 的时间和 I/O 时间。
接下来，说说常见的调度算法：
- 先来先服务调度算法
- 最短作业优先调度算法
- 高响应比优先调度算法
- 时间片轮转调度算法
- 最高优先级调度算法
- 多级反馈队列调度算法
先来先服务调度算法
最简单的一个调度算法，就是非抢占式的先来先服务（First Come First Severd, FCFS）算法了。
顾名思义，先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。
这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。
FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。
最短作业优先调度算法
最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。
这显然对长作业不利，很容易造成一种极端现象。
比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。
高响应比优先调度算法
前面的先来先服务调度算法和最短作业优先调度算法都没有很好的权衡短作业和长作业。
那么，高响应比优先 （Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。
每次进行进程调度时，先计算响应比优先级**，然后把响应比优先级最高的进程投入运行**，响应比优先级的计算公式：
从上面的公式，可以发现：
-
如果两个进程的等待时间相同时，要求的服务时间越短，响应比就越高，这样短作业的进程容易被选中运行；
-
如果两个进程要求的服务时间相同时，等待时间越长，响应比就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会；
时间片轮转调度算法
最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法。
每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。
- 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
- 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；
另外，时间片的长度就是一个很关键的点：
- 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
- 如果设得太长又可能引起对短作业进程的响应时间变长。将
通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。
最高优先级调度算法
前面的时间片轮转算法做了个假设，即让所有的进程同等重要，也不偏袒谁，大家的运行时间都一样。
但是，对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。
进程的优先级可以分为，静态优先级或动态优先级：
- 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
- 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。
该算法也有两种处理优先级高的方法，非抢占式和抢占式：
- 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
- 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
但是依然有缺点，可能会导致低优先级的进程永远不会运行。
多级反馈队列调度算法
多级反馈队列（Multilevel Feedback Queue）调度算法是时间片轮转算法和最高优先级算法的综合和发展。
顾名思义：
- 多级表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
- 反馈表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；
来看看，它是如何工作的：
- 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
- 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
- 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；
可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。
内存页面置换算法
在了解内存页面置换算法前，得先谈一下缺页异常（缺页中断）。
当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。那它与一般中断的主要区别在于：
-
缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完成后检查和处理中断信号。
-
缺页中断返回到该指令的开始重新执行该指令，而一般中断返回回到该指令的下一个指令执行。
来看一下缺页中断的处理流程，如下图：
- 在 CPU 里访问一条 Load M 指令，然后 CPU 会去找 M 所对应的页表项。
- 如果该页表项的状态位是有效的，那 CPU 就可以直接去访问物理内存了，如果状态位是无效的，则 CPU 则会发送缺页中断请求。
- 操作系统收到了缺页中断，则会执行缺页中断处理函数，先会查找该页面在磁盘中的页面的位置。
- 找到磁盘中对应的页面后，需要把该页面换入到物理内存中，但是在换入前，需要在物理内存中找空闲页，如果找到空闲页，就把页面换入到物理内存中。
- 页面从磁盘换入到物理内存完成后，则把页表项中的状态位修改为有效的。
- 最后，CPU 重新执行导致缺页异常的指令。
上面所说的过程，第 4 步是能在物理内存找到空闲页的情况，那如果找不到呢？
找不到空闲页的话，就说明此时内存已满了，这时候，就需要页面置换算法选择一个物理页，如果该物理页有被修改过（脏页），则把它换出到磁盘，然后把该被置换出去的页表项的状态改成无效的，最后把正在访问的页面装入到这个物理页中。
页表项通常有如下图的字段：
其中：
- 状态位：用于表示该页是否有效，也就是说是否在物理内存中，供程序访问时参考。
- 访问字段：用于记录该页在一段时间被访问的次数，供页面置换算法选择出页面时参考。
- 修改位：表示该页在调入内存后是否有被修改过，由于内存中的每一页都在磁盘上保留一份副本，因此，如果没有修改，在置换该页时就不需要将该页写回到磁盘上，以减少系统的开销；如果已经被修改，则将该页重写到磁盘上，以保证磁盘中所保留的始终是最新的副本。
- 硬盘地址：用于指出该页在硬盘上的地址，通常是物理块号，供调入该页时使用。
虚拟内存的管理整个流程：
所以，页面置换算法的功能是，当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。
那其算法目标则是，尽可能减少页面的换入换出的次数，常见的页面置换算法有如下几种：
- 最佳页面置换算法（OPT）
- 先进先出置换算法（FIFO）
- 最近最久未使用的置换算法（LRU）
- 时钟页面置换算法（Lock）
- 最不常用置换算法（LFU）
最佳页面置换算法
最佳页面置换算法基本思路是，置换在未来最长时间不访问的页面。
所以，该算法实现需要计算内存中每个逻辑页面的下一次访问时间，然后比较，选择未来最长时间不访问的页面。
举个例子，假设一开始有 3 个空闲的物理页，然后有请求的页面序列，那它的置换过程如下图：
在这个请求的页面序列中，缺页共发生了 7 次（空闲页换入 3 次 + 最优页面置换 4 次），页面置换共发生了 4 次。
这很理想，但是实际系统中无法实现，因为程序访问页面时是动态的，是无法预知每个页面在下一次访问前的等待时间。
所以，最佳页面置换算法作用是为了衡量你的算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的。
先进先出置换算法
既然无法预知页面在下一次访问前所需的等待时间，那可以选择在内存驻留时间很长的页面进行中置换，这个就是先进先出置换算法的思想。
还是以前面的请求的页面序列作为例子，假设使用先进先出置换算法，则过程如下图：
在这个请求的页面序列中，缺页共发生了 10 次，页面置换共发生了 7 次，跟最佳页面置换算法比较起来，性能明显差了很多。
最近最久未使用的置换算法
最近最久未使用（LRU）的置换算法的基本思路是，发生缺页时，选择最长时间没有被访问的页面进行置换，也就是说，该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。
这种算法近似最优置换算法，最优置换算法是通过未来的使用情况来推测要淘汰的页面，而 LRU 则是通过历史的使用情况来推测要淘汰的页面。
还是以前面的请求的页面序列作为例子，假设使用最近最久未使用的置换算法，则过程如下图：
在这个请求的页面序列中，缺页共发生了 9 次，页面置换共发生了 6 次，跟先进先出置换算法比较起来，性能提高了一些。
虽然 LRU 在理论上是可以实现的，但代价很高。为了完全实现 LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。
困难的是，在每次访问内存时都必须要更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作。
所以，LRU 虽然看上去不错，但是由于开销比较大，实际应用中比较少使用。
时钟页面置换算法
那有没有一种即能优化置换的次数，也能方便实现的算法呢？
时钟页面置换算法就可以两者兼得，它跟 LRU 近似，又是对 FIFO 的一种改进。
该算法的思路是，把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。
当发生缺页中断时，算法首先检查表针指向的页面：
- 如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；
- 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止；
时钟页面置换算法的工作流程图：
了解了这个算法的工作方式，就明白为什么它被称为时钟（Clock）算法了。
最不常用算法
最不常用（LFU）算法，这名字听起来很调皮，但是它的意思不是指这个算法不常用，而是当发生缺页中断时，选择访问次数最少的那个页面，并将其淘汰。
它的实现方式是，对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。
看起来很简单，每个页面加一个计数器就可以实现了，但是在操作系统中实现的时候，需要考虑效率和硬件成本的。
要增加一个计数器来实现，这个硬件成本是比较高的，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表长度很大，是非常耗时的，效率不高。
但还有个问题，LFU 算法只考虑了频率问题，没考虑时间的问题，比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。
那这个问题的解决的办法还是有的，可以定期减少访问的次数，比如当发生时间中断时，把过去时间访问的页面的访问次数除以 2，也就说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大了被置换的概率。
磁盘调度算法
磁盘的结构如下图：
常见的机械磁盘是上图左边的样子，中间圆的部分是磁盘的盘片，一般会有多个盘片，每个盘面都有自己的磁头。右边的图就是一个盘片的结构，盘片中的每一层分为多个磁道，每个磁道分多个扇区，每个扇区是 512 字节。那么，多个具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面，如上图里中间的样子。
磁盘调度算法的目的很简单，就是为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的。
寻道的时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，必然可以节省一些不必要的寻道时间，从而提高磁盘的访问性能。
假设有下面一个请求序列，每个数字代表磁道的位置：
98，183，37，122，14，124，65，67
初始磁头当前的位置是在第 53 磁道。
接下来，分别对以上的序列，作为每个调度算法的例子，那常见的磁盘调度算法有：
- 先来先服务算法
- 最短寻道时间优先算法
- 扫描算法
- 循环扫描算法
- LOOK 与 C-LOOK 算法
先来先服务
先来先服务（First-Come，First-Served，FCFS），顾名思义，先到来的请求，先被服务。
那按照这个序列的话：
98，183，37，122，14，124，65，67
那么，磁盘的写入顺序是从左到右，如下图：
先来先服务算法总共移动了 640 个磁道的距离，这么一看这种算法，比较简单粗暴，但是如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散，那先来先服务算法在性能上就会显得很差，因为寻道时间过长。
最短寻道时间优先
最短寻道时间优先（Shortest Seek First，SSF）算法的工作方式是，优先选择从当前磁头位置所需寻道时间最短的请求，还是以这个序列为例子：
98，183，37，122，14，124，65，67
那么，那么根据距离磁头（ 53 位置）最近的请求的算法，具体的请求则会是下列从左到右的顺序：
65，67，37，14，98，122，124，183
磁头移动的总距离是 236 磁道，相比先来先服务性能提高了不少。
但这个算法可能存在某些请求的饥饿，因为本次例子是静态的序列，看不出问题，假设是一个动态的请求，如果后续来的请求都是小于 183 磁道的，那么 183 磁道可能永远不会被响应，于是就产生了饥饿现象，这里产生饥饿的原因是磁头在一小块区域来回移动。
扫描算法
最短寻道时间优先算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。
为了防止这个问题，可以规定：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（Scan）算法。
这种算法也叫做电梯算法，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。
还是以这个序列为例子，磁头的初始位置是 53：
98，183，37，122，14，124，65，67
那么，假设扫描调度算先朝磁道号减少的方向移动，具体请求则会是下列从左到右的顺序：
37，14，0，65，67，98，122，124，183
磁头先响应左边的请求，直到到达最左端（ 0 磁道）后，才开始反向移动，响应右边的请求。
扫描调度算法性能较好，不会产生饥饿现象，但是存在这样的问题，中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异。
循环扫描算法
扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的方向进行扫描，使得每个磁道的响应频率基本一致。
循环扫描（Circular Scan, CSCAN ）规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。
还是以这个序列为例子，磁头的初始位置是 53：
98，183，37，122，14，124，65，67
那么，假设循环扫描调度算先朝磁道增加的方向移动，具体请求会是下列从左到右的顺序：
65，67，98，122，124，183，199，0，14，37
磁头先响应了右边的请求，直到碰到了最右端的磁道 199，就立即回到磁盘的开始处（磁道 0），但这个返回的途中是不响应任何请求的，直到到达最开始的磁道后，才继续顺序响应右边的请求。
循环扫描算法相比于扫描算法，对于各个位置磁道响应频率相对比较平均。
LOOK 与 C-LOOK算法
前面说到的扫描算法和循环扫描算法，都是磁头移动到磁盘最始端或最末端才开始调换方向。
那这其实是可以优化的，优化的思路就是磁头在移动到最远的请求位置，然后立即反向移动。
那针对 SCAN 算法的优化则叫 LOOK 算法，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求。
而针 C-SCAN 算法的优化则叫 C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。
