实时系统中的调度
实时系统(real-time) 是一个时间扮演了重要作用的系统。实时系统可以分为两类，硬实时(hard real time) 和 软实时(soft real time) 系统，前者意味着必须要满足绝对的截止时间；后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。
实时系统中的事件可以按照响应方式进一步分类为周期性(以规则的时间间隔发生)事件或 非周期性(发生时间不可预知)事件。一个系统可能要响应多个周期性事件流，根据每个事件处理所需的时间，可能甚至无法处理所有事件。例如，如果有 m 个周期事件，事件 i 以周期 Pi 发生，并需要 Ci 秒 CPU 时间处理一个事件，那么可以处理负载的条件是
只有满足这个条件的实时系统称为可调度的，这意味着它实际上能够被实现。一个不满足此检验标准的进程不能被调度，因为这些进程共同需要的 CPU 时间总和大于 CPU 能提供的时间。
下面我们来了解一下内存管理，你需要知道的知识点如下
地址空间
如果要使多个应用程序同时运行在内存中，必须要解决两个问题：保护和 重定位。第一种解决方式是用保护密钥标记内存块，并将执行过程的密钥与提取的每个存储字的密钥进行比较。这种方式只能解决第一种问题（破坏操作系统），但是不能解决多进程在内存中同时运行的问题。
还有一种更好的方式是创造一个存储器抽象：地址空间(the address space)。就像进程的概念创建了一种抽象的 CPU 来运行程序，地址空间也创建了一种抽象内存供程序使用。
基址寄存器和变址寄存器
最简单的办法是使用动态重定位(dynamic relocation)技术，它就是通过一种简单的方式将每个进程的地址空间映射到物理内存的不同区域。还有一种方式是使用基址寄存器和变址寄存器。
- 基址寄存器：存储数据内存的起始位置
- 变址寄存器：存储应用程序的长度。
每当进程引用内存以获取指令或读取、写入数据时，CPU 都会自动将基址值添加到进程生成的地址中，然后再将其发送到内存总线上。同时，它检查程序提供的地址是否大于或等于变址寄存器 中的值。如果程序提供的地址要超过变址寄存器的范围，那么会产生错误并中止访问。
交换技术
在程序运行过程中，经常会出现内存不足的问题。
针对上面内存不足的问题，提出了两种处理方式：最简单的一种方式就是交换(swapping)技术，即把一个进程完整的调入内存，然后再内存中运行一段时间，再把它放回磁盘。空闲进程会存储在磁盘中，所以这些进程在没有运行时不会占用太多内存。另外一种策略叫做虚拟内存(virtual memory)，虚拟内存技术能够允许应用程序部分的运行在内存中。下面我们首先先探讨一下交换
交换过程
下面是一个交换过程
刚开始的时候，只有进程 A 在内存中，然后从创建进程 B 和进程 C 或者从磁盘中把它们换入内存，然后在图 d 中，A 被换出内存到磁盘中，最后 A 重新进来。因为图 g 中的进程 A 现在到了不同的位置，所以在装载过程中需要被重新定位，或者在交换程序时通过软件来执行；或者在程序执行期间通过硬件来重定位。基址寄存器和变址寄存器就适用于这种情况。
交换在内存创建了多个 空闲区(hole)，内存会把所有的空闲区尽可能向下移动合并成为一个大的空闲区。这项技术称为内存紧缩(memory compaction)。但是这项技术通常不会使用，因为这项技术会消耗很多 CPU 时间。
空闲内存管理
在进行内存动态分配时，操作系统必须对其进行管理。大致上说，有两种监控内存使用的方式
位图(bitmap)空闲列表(free lists)
使用位图的存储管理
使用位图方法时，内存可能被划分为小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位，0 表示空闲， 1 表示占用（或者相反）。一块内存区域和其对应的位图如下
位图提供了一种简单的方法在固定大小的内存中跟踪内存的使用情况，因为位图的大小取决于内存和分配单元的大小。这种方法有一个问题是，当决定为把具有 k 个分配单元的进程放入内存时，内容管理器(memory manager) 必须搜索位图，在位图中找出能够运行 k 个连续 0 位的串。在位图中找出制定长度的连续 0 串是一个很耗时的操作，这是位图的缺点。（可以简单理解为在杂乱无章的数组中，找出具有一大长串空闲的数组单元）
使用链表进行管理
另一种记录内存使用情况的方法是，维护一个记录已分配内存段和空闲内存段的链表，段会包含进程或者是两个进程的空闲区域。可用上面的图 c 来表示内存的使用情况。链表中的每一项都可以代表一个 空闲区(H) 或者是进程(P)的起始标志，长度和下一个链表项的位置。
当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以为创建的进程（或者从磁盘中换入的进程）分配内存。我们先假设内存管理器知道应该分配多少内存，最简单的算法是使用 首次适配(first fit)。内存管理器会沿着段列表进行扫描，直到找个一个足够大的空闲区为止。 除非空闲区大小和要分配的空间大小一样，否则将空闲区分为两部分，一部分供进程使用；一部分生成新的空闲区。首次适配算法是一种速度很快的算法，因为它会尽可能的搜索链表。
首次适配的一个小的变体是 下次适配(next fit)。它和首次匹配的工作方式相同，只有一个不同之处那就是下次适配在每次找到合适的空闲区时就会记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次匹配算法那样每次都会从头开始搜索。
另外一个著名的并且广泛使用的算法是 最佳适配(best fit)。最佳适配会从头到尾寻找整个链表，找出能够容纳进程的最小空闲区。
虚拟内存
尽管基址寄存器和变址寄存器用来创建地址空间的抽象，但是这有一个其他的问题需要解决：管理软件的不断增大(managing bloatware)。虚拟内存的基本思想是，每个程序都有自己的地址空间，这个地址空间被划分为多个称为页面(page)的块。每一页都是连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，硬件会立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。
分页
大部分使用虚拟内存的系统中都会使用一种 分页(paging) 技术。在任何一台计算机上，程序会引用使用一组内存地址。当程序执行
MOV REG,1000
这条指令时，它会把内存地址为 1000 的内存单元的内容复制到 REG 中（或者相反，这取决于计算机）。地址可以通过索引、基址寄存器、段寄存器或其他方式产生。
这些程序生成的地址被称为 虚拟地址(virtual addresses) 并形成虚拟地址空间(virtual address space)，在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存中线上，读写操作都使用同样地址的物理内存。在使用虚拟内存时，虚拟地址不会直接发送到内存总线上。相反，会使用 MMU(Memory Management Unit) 内存管理单元把虚拟地址映射为物理内存地址，像下图这样
下面这幅图展示了这种映射是如何工作的
页表给出虚拟地址与物理内存地址之间的映射关系。每一页起始于 4096 的倍数位置，结束于 4095 的位置，所以 4K 到 8K 实际为 4096 - 8191 ，8K - 12K 就是 8192 - 12287
在这个例子中，我们可能有一个 16 位地址的计算机，地址从 0 - 64 K - 1，这些是虚拟地址。然而只有 32 KB 的物理地址。所以虽然可以编写 64 KB 的程序，但是程序无法全部调入内存运行，在磁盘上必须有一个最多 64 KB 的程序核心映像的完整副本，以保证程序片段在需要时被调入内存。
页表
虚拟页号可作为页表的索引用来找到虚拟页中的内容。由页表项可以找到页框号（如果有的话）。然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成物理地址。
因此，页表的目的是把虚拟页映射到页框中。从数学上说，页表是一个函数，它的参数是虚拟页号，结果是物理页框号。
通过这个函数可以把虚拟地址中的虚拟页转换为页框，从而形成物理地址。
页表项的结构
下面我们探讨一下页表项的具体结构，上面你知道了页表项的大致构成，是由页框号和在/不在位构成的，现在我们来具体探讨一下页表项的构成
页表项的结构是与机器相关的，但是不同机器上的页表项大致相同。上面是一个页表项的构成，不同计算机的页表项可能不同，但是一般来说都是 32 位的。页表项中最重要的字段就是页框号(Page frame number)。毕竟，页表到页框最重要的一步操作就是要把此值映射过去。下一个比较重要的就是在/不在位，如果此位上的值是 1，那么页表项是有效的并且能够被使用。如果此值是 0 的话，则表示该页表项对应的虚拟页面不在内存中，访问该页面会引起一个缺页异常(page fault)。
保护位(Protection) 告诉我们哪一种访问是允许的，啥意思呢？最简单的表示形式是这个域只有一位，0 表示可读可写，1 表示的是只读。
修改位(Modified) 和 访问位(Referenced) 会跟踪页面的使用情况。当一个页面被写入时，硬件会自动的设置修改位。修改位在页面重新分配页框时很有用。如果一个页面已经被修改过（即它是 脏 的），则必须把它写回磁盘。如果一个页面没有被修改过（即它是 干净的），那么重新分配时这个页框会被直接丢弃，因为磁盘上的副本仍然是有效的。这个位有时也叫做 脏位(dirty bit)，因为它反映了页面的状态。
访问位(Referenced) 在页面被访问时被设置，不管是读还是写。这个值能够帮助操作系统在发生缺页中断时选择要淘汰的页。不再使用的页要比正在使用的页更适合被淘汰。这个位在后面要讨论的页面置换算法中作用很大。
最后一位用于禁止该页面被高速缓存，这个功能对于映射到设备寄存器还是内存中起到了关键作用。通过这一位可以禁用高速缓存。具有独立的 I/O 空间而不是用内存映射 I/O 的机器来说，并不需要这一位。
页面置换算法
下面我们就来探讨一下有哪些页面置换算法。
最优页面置换算法
最优的页面置换算法的工作流程如下：在缺页中断发生时，这些页面之一将在下一条指令（包含该指令的页面）上被引用。其他页面则可能要到 10、100 或者 1000 条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。
最优化的页面算法表明应该标记最大的页面。如果一个页面在 800 万条指令内不会被使用，另外一个页面在 600 万条指令内不会被使用，则置换前一个页面，从而把需要调入这个页面而发生的缺页中断推迟。计算机也像人类一样，会把不愿意做的事情尽可能的往后拖。
这个算法最大的问题时无法实现。当缺页中断发生时，操作系统无法知道各个页面的下一次将在什么时候被访问。这种算法在实际过程中根本不会使用。
最近未使用页面置换算法
为了能够让操作系统收集页面使用信息，大部分使用虚拟地址的计算机都有两个状态位，R 和 M，来和每个页面进行关联。每当引用页面（读入或写入）时都设置 R，写入（即修改）页面时设置 M，这些位包含在每个页表项中，就像下面所示
因为每次访问时都会更新这些位，因此由硬件来设置它们非常重要。一旦某个位被设置为 1，就会一直保持 1 直到操作系统下次来修改此位。
如果硬件没有这些位，那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟。当启动一个进程时，将其所有的页面都标记为不在内存；一旦访问任何一个页面就会引发一次缺页中断，此时操作系统就可以设置 R 位(在它的内部表中)，修改页表项使其指向正确的页面，并设置为 READ ONLY 模式，然后重新启动引起缺页中断的指令。如果页面随后被修改，就会发生另一个缺页异常。从而允许操作系统设置 M 位并把页面的模式设置为 READ/WRITE。
可以用 R 位和 M 位来构造一个简单的页面置换算法：当启动一个进程时，操作系统将其所有页面的两个位都设置为 0。R 位定期的被清零（在每个时钟中断）。用来将最近未引用的页面和已引用的页面分开。
当出现缺页中断后，操作系统会检查所有的页面，并根据它们的 R 位和 M 位将当前值分为四类：
- 第 0 类：没有引用 R，没有修改 M
- 第 1 类：没有引用 R，已修改 M
- 第 2 类：引用 R ，没有修改 M
- 第 3 类：已被访问 R，已被修改 M
尽管看起来好像无法实现第一类页面，但是当第三类页面的 R 位被时钟中断清除时，它们就会发生。时钟中断不会清除 M 位，因为需要这个信息才能知道是否写回磁盘中。清除 R 但不清除 M 会导致出现一类页面。
NRU(Not Recently Used) 算法从编号最小的非空类中随机删除一个页面。此算法隐含的思想是，在一个时钟内（约 20 ms）淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好，NRU 的主要优点是易于理解并且能够有效的实现。
先进先出页面置换算法
另一种开销较小的方式是使用 FIFO(First-In,First-Out) 算法，这种类型的数据结构也适用在页面置换算法中。由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾。在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾。
第二次机会页面置换算法
我们上面学到的 FIFO 链表页面有个缺陷，那就是出链和入链并不会进行 check 检查，这样就会容易把经常使用的页面置换出去，为了避免这一问题，我们对该算法做一个简单的修改：我们检查最老页面的 R 位，如果是 0 ，那么这个页面就是最老的而且没有被使用，那么这个页面就会被立刻换出。如果 R 位是 1，那么就清除此位，此页面会被放在链表的尾部，修改它的装入时间就像刚放进来的一样。然后继续搜索。
这种算法叫做 第二次机会(second chance)算法，就像下面这样，我们看到页面 A 到 H 保留在链表中，并按到达内存的时间排序。
a）按照先进先出的方法排列的页面；b）在时刻 20 处发生缺页异常中断并且 A 的 R 位已经设置时的页面链表。
假设缺页异常发生在时刻 20 处，这时最老的页面是 A ，它是在 0 时刻到达的。如果 A 的 R 位是 0，那么它将被淘汰出内存，或者把它写回磁盘（如果它已经被修改过），或者只是简单的放弃（如果它是未被修改过）。另一方面，如果它的 R 位已经设置了，则将 A 放到链表的尾部并且重新设置装入时间为当前时刻（20 处），然后清除 R 位。然后从 B 页面开始继续搜索合适的页面。
寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过，该算法就会被简化为单纯的 FIFO 算法。具体来说，假设图 a 中所有页面都设置了 R 位。操作系统将页面依次移到链表末尾，每次都在添加到末尾时清除 R 位。最后，算法又会回到页面 A，此时的 R 位已经被清除，那么页面 A 就会被执行出链处理，因此算法能够正常结束。
时钟页面置换算法
一种比较好的方式是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。如下图所示
当缺页错误出现时，算法首先检查表针指向的页面，如果它的 R 位是 0 就淘汰该页面，并把新的页面插入到这个位置，然后把表针向前移动一位；如果 R 位是 1 就清除 R 位并把表针前移一个位置。重复这个过程直到找到了一个 R 位为 0 的页面位置。了解这个算法的工作方式，就明白为什么它被称为 时钟(clokc)算法了。
最近最少使用页面置换算法
在前面几条指令中频繁使用的页面和可能在后面的几条指令中被使用。反过来说，已经很久没有使用的页面有可能在未来一段时间内仍不会被使用。这个思想揭示了一个可以实现的算法：在缺页中断时，置换未使用时间最长的页面。这个策略称为 LRU(Least Recently Used) ，最近最少使用页面置换算法。
虽然 LRU 在理论上是可以实现的，但是从长远看来代价比较高。为了完全实现 LRU，会在内存中维护一个所有页面的链表，最频繁使用的页位于表头，最近最少使用的页位于表尾。困难的是在每次内存引用时更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常耗时的操作，即使使用硬件来实现也是一样的费时。
用软件模拟 LRU
尽管上面的 LRU 算法在原则上是可以实现的，但是很少有机器能够拥有那些特殊的硬件。上面是硬件的实现方式，那么现在考虑要用软件来实现 LRU 。一种可以实现的方案是 NFU(Not Frequently Used，最不常用)算法。它需要一个软件计数器来和每个页面关联，初始化的时候是 0 。在每个时钟中断时，操作系统会浏览内存中的所有页，会将每个页面的 R 位（0 或 1）加到它的计数器上。这个计数器大体上跟踪了各个页面访问的频繁程度。当缺页异常出现时，则置换计数器值最小的页面。
只需要对 NFU 做一个简单的修改就可以让它模拟 LRU，这个修改有两个步骤
- 首先，在 R 位被添加进来之前先把计数器右移一位；
- 第二步，R 位被添加到最左边的位而不是最右边的位。
修改以后的算法称为 老化(aging) 算法，下图解释了老化算法是如何工作的。
我们假设在第一个时钟周期内页面 0 - 5 的 R 位依次是 1，0，1，0，1，1，（也就是页面 0 是 1，页面 1 是 0，页面 2 是 1 这样类推）。也就是说，在 0 个时钟周期到 1 个时钟周期之间，0，2，4，5 都被引用了，从而把它们的 R 位设置为 1，剩下的设置为 0 。在相关的六个计数器被右移之后 R 位被添加到 左侧 ，就像上图中的 a。剩下的四列显示了接下来的四个时钟周期内的六个计数器变化。
CPU正在以某个频率前进，该频率的周期称为
时钟滴答或时钟周期。一个 100Mhz 的处理器每秒将接收100,000,000个时钟滴答。
当缺页异常出现时，将置换（就是移除）计数器值最小的页面。如果一个页面在前面 4 个时钟周期内都没有被访问过，那么它的计数器应该会有四个连续的 0 ，因此它的值肯定要比前面 3 个时钟周期内都没有被访问过的页面的计数器小。
这个算法与 LRU 算法有两个重要的区别：看一下上图中的 e，第三列和第五列
工作集时钟页面置换算法
当缺页异常发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法还是比较浪费时间的。一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息，这种算法称为WSClock(工作集时钟)。由于它的实现简单并且具有高性能，因此在实践中被广泛应用。
与时钟算法一样，所需的数据结构是一个以页框为元素的循环列表，就像下面这样
工作集时钟页面置换算法的操作：a) 和 b) 给出 R = 1 时所发生的情形；c) 和 d) 给出 R = 0 的例子
最初的时候，该表是空的。当装入第一个页面后，把它加载到该表中。随着更多的页面的加入，它们形成一个环形结构。每个表项包含来自基本工作集算法的上次使用时间，以及 R 位（已标明）和 M 位（未标明）。
与时钟算法一样，在每个缺页异常时，首先检查指针指向的页面。如果 R 位被是设置为 1，该页面在当前时钟周期内就被使用过，那么该页面就不适合被淘汰。然后把该页面的 R 位置为 0，指针指向下一个页面，并重复该算法。该事件序列化后的状态参见图 b。
现在考虑指针指向的页面 R = 0 时会发生什么，参见图 c，如果页面的使用期限大于 t 并且页面为被访问过，那么这个页面就不会在工作集中，并且在磁盘上会有一个此页面的副本。申请重新调入一个新的页面，并把新的页面放在其中，如图 d 所示。另一方面，如果页面被修改过，就不能重新申请页面，因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。毕竟，有可能存在一个老的，没有被修改过的页面可以立即使用。
原则上来说，所有的页面都有可能因为磁盘I/O 在某个时钟周期内被调度。为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回 n 个页面。一旦达到该限制，就不允许调度新的写操作。
那么就有个问题，指针会绕一圈回到原点的，如果回到原点，它的起始点会发生什么？这里有两种情况：
- 至少调度了一次写操作
- 没有调度过写操作
在第一种情况中，指针仅仅是不停的移动，寻找一个未被修改过的页面。由于已经调度了一个或者多个写操作，最终会有某个写操作完成，它的页面会被标记为未修改。置换遇到的第一个未被修改过的页面，这个页面不一定是第一个被调度写操作的页面，因为硬盘驱动程序为了优化性能可能会把写操作重排序。
对于第二种情况，所有的页面都在工作集中，否则将至少调度了一个写操作。由于缺乏额外的信息，最简单的方法就是置换一个未被修改的页面来使用，扫描中需要记录未被修改的页面的位置，如果不存在未被修改的页面，就选定当前页面并把它写回磁盘。
页面置换算法小结
我们到现在已经研究了各种页面置换算法，现在我们来一个简单的总结，算法的总结归纳如下
| 算法 | 注释 |
|---|---|
| 最优算法 | 不可实现，但可以用作基准 |
| NRU(最近未使用) 算法 | 和 LRU 算法很相似 |
| FIFO(先进先出) 算法 | 有可能会抛弃重要的页面 |
| 第二次机会算法 | 比 FIFO 有较大的改善 |
| 时钟算法 | 实际使用 |
| LRU(最近最少)算法 | 比较优秀，但是很难实现 |
| NFU(最不经常食用)算法 | 和 LRU 很类似 |
| 老化算法 | 近似 LRU 的高效算法 |
| 工作集算法 | 实施起来开销很大 |
| 工作集时钟算法 | 比较有效的算法 |
-
最优算法在当前页面中置换最后要访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准。 -
NRU算法根据 R 位和 M 位的状态将页面氛围四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现，但是性能不是很好。存在更好的算法。 -
FIFO会跟踪页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面，因此这个算法也不是一个很好的选择。 -
第二次机会算法是对 FIFO 的一个修改，它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用，就会进行保留。这个改进大大提高了性能。 -
时钟算法是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会花费更少的时间来执行算法。 -
LRU算法是一个非常优秀的算法，但是没有特殊的硬件(TLB)很难实现。如果没有硬件，就不能使用 LRU 算法。 -
NFU算法是一种近似于 LRU 的算法，它的性能不是非常好。 -
老化算法是一种更接近 LRU 算法的实现，并且可以更好的实现，因此是一个很好的选择 -
最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。
WSClock是另外一种变体，它不仅能够提供良好的性能，而且可以高效地实现。
总之，最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法，但实际上这两个可能是最重要的。