-
实模式
将实模式主要先了解内存寻址
我们的代码分为代码段、数据段等，所有的内存寻址都是根据 段基址：段内偏移 来访问的，这样的地址形式称为逻辑地址，为什么搞这么复杂呢？因为早期的8086处理器寄存器宽度只有16位，16位的寄存器只能进行 64 KB 的寻址，而 8086 有 20 根地址线，按照地址线来计算可以进行 1 MB 的寻址，所以16 位宽度的寄存器是显然不能满足需求的，为了解决这个问题，聪明的程序员想出了用 段基址：段内偏移 的方式来扩展寻址空间。
实际物理地址 = 段基址 << 4(左移四位) + 段内偏移。这样两个 16 位的寄存器合在一起，宽度便成了 20 位。
在实模式下，段寄存器直接存放的就是段基址，比如 CPU 中用来存放当前指令地址的 CS：IP 寄存器，CS 中存放的便是代码段的基址。这样就会出现一个问题，超级不安全，程序可以随意访问任何物理地址，就像逛菜市场一样，无拘无束。为了不让某些非法分子到处瞎转悠，保护模式孕育而生！
-
保护模式
在保护模式下，很重要的一点就是段寄存器不是直接存放段基址了，而是存放着段选择子（选择子也可以叫做selector，索引描述符）。从这里可以看到，我们访问段寄存器就不是放的地址，其实访问的是一张表叫做GDT(全局描述符表)
保护模式下的寻址方式如下：
-
段寄存器存放段选择子；
-
CPU 根据段选择子从GDT中找到对应段描述符；
-
从段描述符中取出段基址。
-
根据之前的公式，结合段基址和段内偏移，计算出物理地址。
保护模式的开关主要存在在CR0控制寄存器中的相关标志位中。
除了寻址方式不同外，保护模式还增加了一个特权级的特性。特权级共四层，0为最高特权级，为内核代码所运行级别，3为最低特权级，为用户程序所运行级别。段描述符中会记录访问当前段所需特权级，程序在访问一个段时需要先构建段选择子，段选择子中中有两位专门负责表示当前程序请求访问目标段的时的特权级，即为RPL。一般来说，RPL = CPL，CPL即为当前程序所在代码段的特权级，存在CS寄存器中的后两位（因为CS 寄存器存放的就是当前代码段的段选择子）。目标段的特权级被称为DPL，当程序访问目标段的时候，如果 DPL 特权比 CPL 和 RPL 中任何一个高，那么就会拒绝访问，从而起到了保护作用
-
-
总体描述
当 PC 的电源打开后， 80x86 结构的CPU将自动进入实模式，并从地址0xFFFF0开始自动执行程序代码，这个地址通常是ROM BIOS 中的地址。 PC 机的BIOS将执行系统的某些硬件检测和诊断功能 ，并在物理地址0处开始设置和初始化中断向量。此后，它将可启动设备的第一个扇区（磁盘引导扇区， 512 字节）读入内存绝对地址 0x7C00 处， 并跳转到这个地方开始引导启动机器运行了。 启动设备通常是软驱或是硬盘。
上图表示从系统加电开始执行程序的顺序
-
具体描述
-
总结：x86 PC刚开机时固化在ROM中的BIOS程序开始运行，当完成加电自检等操作后，会从磁盘中寻找boot引导程序加载。CPU处于实模式（实模式的寻址CS:IP，CS左移4位）
-
开机时，CS=0xFFFF；IP=0x0000，寻址0xFFFF0(ROM BIOS的地址)
-
检查RAM，键盘，显示器，软硬磁盘（加电自检）
-
将磁盘0磁头0磁道第1扇区(引导扇区)读入0x7c00处
-
引导扇区就是启动设备的第一个扇区
-
启动设备信息被设置在CMOS(用来存储时钟和硬件配置信息)中
-
因此，磁盘的第一个扇区上存放着开机后第一段我们可以控制的程序
-
-
设置cs=0x7c00， ip=0x0000
-
在实模式下：cs左移4位+ip
保护模式下：cs查表+ip（GDT表 ）
首先进程是对一个正在运行程序的抽象，这样我们才好去定义，利用它。
一个进程就是一个程序执行的实例，该程序得到CPU，有程序计数器，寄存器和当前变量值等 。
有一个比喻来说明程序和进程之间的关系：程序就是做蛋糕的食谱，这个食谱是存储到书上的。当我们(CPU)想做蛋糕的时候就把食谱调出来，而做蛋糕的各种材料就是输入数据。那么进程就是我们阅读食谱，把材料混合操作等这一系列操作的总和。
因此可以说进程是某种活动，他得到CPU，有输入，输出和状态。
一下几种事件的发生会创建进程
- 系统初始化
- 一个正在运行的程序执行了创建进程的系统调用，以便协助其工作
- 用户请求创建新进程，比如用户打开多个窗口
- 一个批处理作业的初始化。不常见，仅在大型机的批处理系统中有应用。
在unix系统中，只有一个系统调用能用来创建新进程：fork命令。这个系统调用函数会创建一个和父进程相同的副本，两个进程拥有相同的内存映像
但是父进程和子进程各自拥有不同的地址空间。
注意的是不可写的内存区是共享的，有些可以使得程序在父进程和子进程间共享是因为这个程序不能被修改。
或者子进程可以通过写时复制共享父进程的内存，即读的时候可以共享，写的时候即要修改一部分内存的时候必须先将内存复制，然后在自己的私有内存上进行修改才行。
有以下几种情况会引起进程终止
- 进程正常退出。即进程完成了自己的工作，编译器通过一个系统调用告诉操作系统该进程已经结束工作可以收回，在unix中时exit函数。
- 进程执行的时候发现错误退出，自愿的行为。比如要编译一个不存在的文件。
- 由进程引起的错误而退出，非自愿的。通常这类情况是由程序中的错误造成的，比如除零，执行非法指令，引用一块不存在的内存。
- 被其他进程杀死，非自愿。有一个进程执行了系统调用通知操作系统杀死某个进程。
>
- 就绪态。可以运行，但因为其他进程正在运行而暂停
- 阻塞态。除非某种外部事件发生，否则就会被一直挂起
- 运行态。实际上正在占用CPU的进程。
一个进程刚被创建的时候是就绪状态。当一个进程在概念上不能运行的时候就会被阻塞，有两种情况。第一种是等待后续的输入，因此进程挂起是程序自身的原因，比如用户键入命令之前无法执行。第二种是一个概念上可以运行的进程被迫停止，因为操作系统调度了另一个进程占用了CPU，由系统造成的。
就绪态和执行态之间的转换是进程调度程序控制的，进程调度程序是操作系统的一部分。系统认为一个进程占用处理器时间已经很长，决定让其他进程使用就会发生执行到就绪的转变。当有外部事件发生时，某进程就可以由阻塞态变成就绪状态，进入调度程序的调度。
为了实现进程，操作系统中维护了一张表，叫做进程表。进程表是由进程表项(进程控制块)所组成的，一个进程的全部信息就保存在进程控制块中。
每当创建一个进程的时候，linux系统就会为该进程在内存中创建一个task_struct结构体。**这个task_struct结构体就是进程表。**这个结构体或者说进程表存放的是进程在运行过程中与该进程有关的所有信息，其中比如文件描述符就包括在其中。里面的信息如下图所示：
在计算机内存底部的固定区域有一个位置叫做中断向量(可能叫中断指针数组好理解)的地方，这些中断指针数组指向中断程序的入口地址。加入当磁盘中断发生时候，进程A正在运行，那么中断硬件就会将A进程的进程控制块中的寄存器，程序计数器，程序状态字等压入堆栈，随后计算机就跳入到中断指针所指的位置，然后中断服务程序就开始接管工作。
中断发生后系统底层的工作步骤：
- 由计算机硬件将进程管理相关的信息压入堆栈
- 计算机跳转到中断指针所指向的程序入口，装入新的程序计数器
- 汇编语言来保存寄存器的值
- 汇编语言来设置新的堆栈
- 运行由C语言写的中断服务程序
- 调度程序决定下一个运行的进程（哪个进程获得CPU）
- 将控制转给一段汇编代码，为当前的进程装入寄存器的值、内存映射并启动该进程
对于中断的理解：
中断就是干扰别人做事。从计算机方面来说就是干扰CPU做事。而CPU是干啥的？cpu是执行指令的!
所以cpu在执行指令的时候能感受到干扰信号，即中断信号。CPU的工作粒度是机器指令级别的，在每条机器指令执行结束后就会检查一下是否有中断信号产生。就比如你在玩游戏，别人喊你，你不用去轮询有没有人喊你，直接就能听到有没有人喊你。
所以CPU的硬件特性决定中断处理机制也及其高效。
有了进程，还需要多线程的理由：
在一个应用程序中同时发生着多种活动（可以想象一下word应用，打字、显示、磁盘备份等工作。当磁盘备份的时候按理来说鼠标键盘不能用，因为CPU不在这些控制上。）其中某些活动会随着时间的推移被阻塞，如果我们将这些应用分解成可以准并行运行的多个顺序线程，设计模型会比较简单。如果不这样设计，你得考虑单线程下的两种情况吧。第一种是顺序进行，但是阻塞，就得等阻塞的应用得到相应的输出你才能继续进行下面的活动，在阻塞的时候CPU是没有被利用的。第二种就是有限状态机，回调函数这种的。这种非阻塞调用，当没有资源的时候返回一个值，然后等资源来了，就中断然后去处理这个资源，这在编程上会比较复杂。
从上面的理由可以看出，有了进程后我们就不用考虑中断，定时器和上下文切换这种繁琐的概念。同时线程之间共享同一个地址空间和所用可用数据的能力。
线程比进程更加的轻量级，所以比进程更容易创建和撤销。在许多系统中，创建一个线程比进程快10-100倍。
从性能方面来讲，如果存在着大量计算和I/O处理，多线程允许这些操作彼此并行进行，会加快程序的执行速度。
举个多线程的例子，字处理软件比如word这些。第一个线程和用户交互，捕捉用户的操作。第二个线程在得到输入通知的时候在后台自动进行格式处理。第三个线程周期性的将文档中的内容写到磁盘上。如果用到三个进程的话是做不到的，因为这是同一份文件，而进程之前说了，可以一起读，但是是写时复制，必须是不同的内存空间上进行。
另一个例子就是web服务器。
其实介绍了线程我们可以感受到线程和进程的区别，不要在乎细微的区别。从大方向我们可以看到，线程是相同程序之间的协作关系，线程的出现为的是让程序更好的高效工作。而进程更多的是不同程序之间的关系，有一种互相竞争的属性在里面。
进程模型其实就是资源分组处理和执行。那么对于不同资源分组处理很好理解，这也是进程的意义所在，可以想象一下，同一资源是否还需要分组呢？当然需要，我上面已经说了。举了打字程序和web服务器的例子就能很好的说明。
题外话，说一说程序计数器，寄存器，堆栈是干嘛的，为啥需要。
- 程序计数器。主要用来记录接下来该执行哪一条指令
- 寄存器。用来保存当前进程\线程的工作变量
- 堆栈。用来记录程序执行历史，每一个栈帧保存了一个已经调用但是还没有返回的过程。在该栈帧中存放了相应过程的局部变量以及过程调用完成之后返回的地址。因为每个线程或进程会有自己的任务，有不同的调用过程，这就是为什么每个线程也需要有自己的栈帧的原因。
以上这三个是每一个线程都独有的东西，而不是公共的。
下图表示各个线程共有和独有的：
因为所有线程都有完全一样的地址空间，因此所以共享全局变量。
又因为每一个线程都可以访问公共空间的内存，因此一个线程可以读、写、清除另一个线程的堆栈。
不同的进程来自不同的应用程序，他们彼此之间可能有敌意，因为一个进程总是由某一个应用程序所有，但是应用创建线程是为了让他们之间相互合作而不是竞争。
放在用户空间的线程对内核空间来说就是按照单进程管理，这样有的操作系统不支持线程但也可以运行。
在用户空间中实现的线程，每个进程都有一个专属的线程表，记录了线程的属性比如线程的程序计数器、堆栈、寄存器和状态等。
- 优点
- 当一个线程运行完成的时候，可以调用线程调度程序来选择另一个要运行的线程。保存线程状态的过程和调度程序都只是本地过程，所以启动他们比内核调用效率高，同时不需要陷入内核，不需要进行上下文切换，不需要对内存高速缓存刷新，快
- 用户级线程允许每个进程都有一套定制的调度算法。、
- 比较好的扩展性，因为在内核空间中的内核线程需要一定固定的表格空间和堆栈空间，如果内核线程的数量很大的话，会非常消耗内存。
- 缺点
- 如何实现阻塞？假如有一个线程读取键盘，但是没有任何敲击键盘的行为，如果让该线程进行系统调用，由于内核感知不到线程的存在会阻塞该进程，导致进程中的所有线程都会停止。因此我们用户实现线程是能够实现阻塞但是不能影响其他线程。第一种方式是非阻塞，比如没有输入就返回0字节，但是这需要修改操作系统，如果改变read的一些东西会修改许多用户程序这显然不现实。第二种是如果某个调用阻塞，会提前通知。
- 如果一个用户控件实现的线程开始运行，其他线程就不能运行除非让该线程放弃CPU。但是一个单独的线程内部没有时钟信号(中断)的，所以不可能采用轮转的方式实现线程调度。如果让线程也有时钟，一是会增大开销二是会和系统使用的时钟发生冲突。
在内核中有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或者撤销一个已有的线程时，会进行系统调用，通过对内存表的更新完成创建和撤销工作。内核的线程表保存了每个线程的寄存器，栈帧、程序计数器等。
所有能够阻塞线程的调用都是以系统调用的形式实现。当一个线程阻塞时，内核根据其选择会运行同一个进程中处于就绪状态的线程或者另一个进程中的线程。而在用户级线程中只能运行自己进程中的线程，直到被CPU剥夺使用权。
提高内核线程创建和撤销的开销方法是当撤销某个线程时不直接删除其线程表中的表项和数据结构，而是把它标志为不可运行的，其内核数据结构没有收到影响。当创建某个新线程时就重启那些被标志位不可运行的线程，这样节省开销。
使用内核级线程，然后将内核级线程和用户级线程多路复用起来。内核只识别内核级线程调度，其中一些内核级线程会被多个用户级线程复用。在这种模型中，每个内核线程有一个可以轮流使用的用户级线程集合。
进程间通信不仅仅考虑通信的问题，主要解决一下三个问题：
- 一个进程如何把信息传递给另外一个(传递)
- 确保两个进程或者更多进程之间不会出现冲突。比如两个进程抢一个火车座位（互斥）
- 进程执行的正确顺序。比如进程A产生数据进程B打印，那么进程B就必须等待有数据了才能打印（同步）
进程的互斥和同步都放在一起说，但是要注意其区别。
要注意线程也有后面两个问题，但是线程没有第一个问题。但是不同地址空间需要通信的线程数据其实是不同进程之间的通信。
-
竞态条件
即两个或者多个进程读写某些共享数据，会产生争用的情况，两个或多个线程竞相访问数据，而最后的结果取决于进程运行的精确时序。
比如当A进程检查到内存中某个值，标记完成后在准备修改时，检测到时钟中断，然后CPU切换到进程B。此时进程B把相同内存中的某个值给改了，然后时钟中断切回到进程A，由于A标记了值，不知道进程B修改了，就会把这个值修改一遍。
-
临界区
出现竞争条件的原因是多个进程同时读取了公共内存或者公共文件造成的。
我们把对公共内存进行访问的一段程序称为临界区。
这个在c++面试资料里面的操作系统那部分也有说到，在这里就不在赘述
下图是抽象的角度看待进程间互斥的：
-
屏蔽中断
最暴力的方案就是在进程进入临界区后立即屏蔽中断，并且在完成任务之后再打开中断。
对于单处理器来说，由于CPU只有发生中断才进行切换，这样就不用担心切换到其他进程了。但是把中断的权利交给进程是不明智的，因为如果一个进程屏蔽中断后不再打开，整个系统可能会因此而停止。
如果说是多处理器，屏蔽中断指令仅针对一个CPU处理器有效，而其他处理器操作的进程照样还是能够进入公共内存区进行读写。所以主要是多核处理器时代来说屏蔽中断没啥吊用。
-
锁变量
这个也有问题，主要是锁变量这个东西也是公共的，谁都能加锁，那不和操作公共内存区没啥区别吗。
当进程A检查锁是0的时候恰巧进程B也检查到锁是0，所以俩进程又进去同时修改内存了
-
轮换法
如图所示，这是两个进程之间轮换的，分别是进程0和进程1
对于进程0来说检查turn=0进入内存区域操作，结束后出来把turn=1。然后进程1发现turn=1就可以进内存区操作。
问题：当进程0结束完成后将turn=1。如果此时进程0还想再进去就会被阻塞，只能等待进程1进去吧turn值修改才能使用公共内存，这样显然不合理，进程0被一个其他进程阻塞，这是不允许的。
-
几个经典的进程间通信的问题
生产者消费者问题，银行家就餐，读和写问题
放在c++面试操作系统里面了
-
信号量
其实信号量这个概念就是从生产者消费者问题里面来的。
具体操作谷歌吧
要切记检查变量，修改变量以及可能发生的阻塞操作作为一个原子操作进行的。
信号量的用途就是实现同步的。
-
互斥量
当多个处于就绪状态的进程/线程竞争CPU的时候就会出现调度问题。
-
分类
几乎所有进程的I/O请求和计算都是交替发生的。CPU计算一段时间后发出一个系统调用以便读取文件，在完成系统调用之后CPU又开始处理文件。
计算密集型进程：CPU绝大多数时间花在计算上。
I/O密集型进程：CPU绝大时间花费在等待I/O上。
随着CPU速度越来越快，更多倾向于I/O密集型，因为CPU的改进比磁盘改进快的多，都花费时间在I/O上了。
- 何时调度
- 父进程创建子进程后，这两个进程都处于就绪状态，可以任意决定。
- 在一个进程退出时必须进行调度决策，从就绪队列中选择一个。如果没有就绪的进程，调度程序会让操作系统提供一个空闲的进程。
- 当进程阻塞时，必须选择运行另外一个进程。
- 当发生I/O中断时必须做出调度决策
- 调度系统分类
- 批处理系统
- 交互式
- 实时系统
-
轮转调度
最古老、最简单、最公平的调度方式。每个进程被分配一个时间段叫做时间片，即允许该进程在该时间段中运行。如果时间片结束后该进程的CPU就会被剥夺分配给另一个进程。如果该进程在时间片内阻塞，则会立刻切换CPU。
时间片设置的时间太短会造成过多的CPU切换，降低CPU的效率。设置时间太长可能对短的交互时间边长。所以一般设置成20-50ms。
-
优先级调度
轮转调度做了一个假设即所有进程优先级相同。但事实上很多进程的优先级是不同的。每个进程被赋予一个优先级，高的先得到CPU。一般结合时间片来用，即时间片结束后次优先级的进程就得到了机会运行。
-
多级队列
对于进程设立优先级类。属于最高优先级类的进程运行一个时间片，属于次高优先级进程分配两个时间片，以此类推。当一个进程用完分配的时间片后被移到下一类。
-
最短进程优先
-
保证调度
-
彩票调度
由于多线程并不能感知时钟的存在，因此这个线程可以按照意愿任意运行多长时间。如果该线程用完了进程的全部时间片，内核就会选择另一个内核运行。
用户级线程：内核选进程，然后运行时系统选择线程
内核级线程：内核直接选择哪一个线程。
用户级线程的线程切换需要少量的机器指令，而内核级线程需要完整的上下文切换，修改内存映像，使高速缓存失效，这样会导致若干数量及的延迟。另一方面，使用内核线程时一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。
用户级线程可以为应用程序定值专门的线程调度程序。而在内核线程中内核从来不了解每个线程的作用。
目前在使用的电脑都是分层存储器体系，即MB的高速缓存cache，GB的内存和TB的磁盘存储。
-
1、无存储器抽象
早期计算机没有存储器抽象，每一个程序都是直接访问物理内存。这种情况下在内存中同时运行两个程序是不可能的，因为如果第一个程序比如在内存2000的位置写入一个新的值，那么第二个程序运行的时候就会擦掉第一个程序的值。
但是即使没有抽象概念，运行两个程序也是可能的。。。
操作系统把当前内存中的内容保存在磁盘文件中，然后把下一个程序读入到内存中再运行就行，即某个时间内内存只有一个程序在运行就不会发生冲突。（最早期的交换的概念）
还有就是借助硬件来实现并发运行多个程序，比如IBM360中内存被划分为2KB的块，每个块有一个4位的保护键，保护键存储在CPU的特殊寄存器中。一个运行中的程序如果访问的保护键与操作系统中保存的不相符，则硬件会捕获到该异常，由于只有操作系统可以修改保护键，因此这样就可以防止用户进程之间、用户进程和操作系统间的干扰。
-
2、地址空间（存储抽象）
把物理地址暴露给进程会带来几个问题：
- 如果用户进程可以寻址内存中的每一个字节，就可以很容易的破坏操作系统，从而时电脑出故障。
- 想要同时运行多个程序比较困难
在之前所说的解决多个程序在内存中互不影响的办法主要有两个：保护和重定位，也就是说并不是所有内存你都能访问，因此出现了地址空间的概念。
地址空间是一个进程可用于寻址内存的一套地址的集合。每个进程都有自己的地址空间，并且这个地址空间独立于其他进程的地址空间
最开始的地址空间的解决办法是动态重定位，就是简单地把每个进程的地址空间映射到物理内存的不同部分。但是也有问题，即每个进程都有内存，如果同时运行多个进程，那所需要的内存是很庞大的，这个ram数远远超过存储器支持的。比如在Linux和Windows中，计算机完成引导后会启动50-100个进程，那你需要的空间可大了去了。
处理上述内存超载问题有两个办法，就是交换技术和虚拟内存。
交换技术就是把一个进程完整的调入内存，使得该进程完整运行一段时间后在调入磁盘。但是这样的话，你把一个完整的进程调入进去，可能很大程度只会使用一部分内存，这样是不划算的。
所以有了虚拟内存，每个进程的一部分调入内存。
-
3、虚拟内存
这个要重点说
根据上面所说，虚拟内存就是来解决“程序大于内存的问题”，即如何不把程序内存全部装进去。
虚拟内存的基本思想是每个程序都拥有自己的地址空间，这些空间被分割成多个块儿。每一块儿被称作一页或者页面。每一个页面有连续的地址范围。这些页面被映射到物理内存，但是并不是所有的页面都必须在内存中才能运行。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失部分装入物理内存并重新执行指令。
虚拟内存 使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如RAM）的使用也更有效率。
在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作使用具有同样地址的物理内存字。在使用虚拟内存的情况下，虚拟地址不是直接被送到内存总线上的，而是被送往内存管理单元MMU，然后MMU把虚拟地址映射为物理内存地址
在这里MMU是作为CPU芯片的一部分，通常就是这样的。
具体页表中虚拟地址与物理内存地址之间的映射关系如下：
上图可以看到虚拟地址被划分成多个页面组成的单位，而物理内存地址中对应的是页框的概念。页面和页框的大小通常是一样的，在这里是4KB作为例子，实际系统中可能是512KB-1GB。上图虚拟地址空间有64KB，物理内存有32KB，因此由16个虚拟页面和8个页框。请记住，ram和也磁盘之间的交换总是以整个页面为单位进行的。
比如当程序访问地址0的时候，其实是访问虚拟地址，然后将虚拟地址0送到MMU，MMU根据映射关系发现虚拟地址0在页面0-4095这个页面上，然后根据映射找到实际物理内存地址是第二个页框，即8192，然后把地址8192送到总线上。内存对MMU是一无所知的，他只看到了一个读写8192的请求并执行。
当程序访问了一个未被映射的页面，即虚拟地址没有对应的页框索引。此时MMU注意到该页面没有映射，使CPU陷入到操作系统，即缺页中断或者缺页错误（page fault）。随后操作系统找到了一个很少使用的页框并把该页框内容写入磁盘，然后把需要访问的页面读到刚才被回收的那个页框上，修改映射关系，重新启动引起中断的指令就好。
例如如果操作系统放弃页框1，即重新映射页框1，那么重新改变映射关系，将页面8装入物理地址4096（页框1），并且对MMU映射做两处修改：①由于页框1之前被页面1映射，因此要将页面1标记为未映射，使得以后对页面1的访问都将导致缺页中断。②把虚拟页面8的叉号改为1，表明虚拟页面8映射到页框1上去，当指令重新启动时候就会产生新的映射。
MMU的内部操作：
输入虚拟地址8196的二进制在最底下即0010000000000100，用MMU映射机进行映射，这16位虚拟地址被分解成4位的页号+12位的偏移量。4位页号表示16个页面，是页面的索引，12位的位偏移可以为一页内的全部4096个字节编址。
虚拟地址到物理地址的映射可以概括如下：虚拟地址被分成虚拟页号+偏移量。虚拟页号是一个页表的索引，可以有该索引即页面号找到对应的页框号，然后将该页框号放到16位地址的前4位，替换掉虚拟页号，就形成了送往内存的地址。可以参考上面那个图中，两个二进制字符串的替换形式。如下图：
页表的目的是将虚拟页面映射为页框，从数学角度说页表是一个函数，输入参数是虚拟页号，输出结果是物理页框号。
页表的结构如下：
页表项中最重要的字段就是页框号(Page frame number)。毕竟，页表到页框最重要的一步操作就是要把此值映射过去。下一个比较重要的就是在/不在位，如果此位上的值是 1，那么页表项是有效的并且能够被使用。如果此值是 0 的话，则表示该页表项对应的虚拟页面不在内存中，访问该页面会引起一个缺页异常(page fault)。保护位(Protection) 告诉我们哪一种访问是允许的，啥意思呢？最简单的表示形式是这个域只有一位，0 表示可读可写，1 表示的是只读。修改位(Modified) 和 访问位(Referenced) 会跟踪页面的使用情况。当一个页面被写入时，硬件会自动的设置修改位。修改位在页面重新分配页框时很有用。如果一个页面已经被修改过（即它是 脏 的），则必须把它写回磁盘。如果一个页面没有被修改过（即它是 干净的），那么重新分配时这个页框会被直接丢弃，因为磁盘上的副本仍然是有效的。这个位有时也叫做 脏位(dirty bit)，因为它反映了页面的状态。访问位(Referenced) 在页面被访问时被设置，不管是读还是写。这个值能够帮助操作系统在发生缺页中断时选择要淘汰的页。不再使用的页要比正在使用的页更适合被淘汰。这个位在后面要讨论的页面置换算法中作用很大。最后一位用于禁止该页面被高速缓存，这个功能对于映射到设备寄存器还是内存中起到了关键作用。通过这一位可以禁用高速缓存。具有独立的 I/O 空间而不是用内存映射 I/O 的机器来说，并不需要这一位。
分页系统中要考虑两个问题：
-
虚拟地址到物理地址的映射必须非常快
由于每次访问内存都需要进行虚拟地址到物理地址的映射，所有的指令最终都必须来自内存，并且很多指令也会访问内存中的操作数。因此每条指令进行多次页表访问是必要的。如果执行一条指令需要1ns，则页表查询必须在0.2ns之内完成，以避免映射成为主要的瓶颈。
-
如果虚拟地址空间很大，页表也会很大
现代计算机使用的虚拟地址至少为32位，而且越来越多的64位。假设一个页面大小为4KB，则32位的地址空间将有100万页，那么64位地址空间更多了。一个页表有100万条表项，你个存储开销就很大。而且每个进程都有自己的页表还
所以我们接下来主要解决的就是这两个问题。
大多数优化技术都是从内存中的页表开始的，因为这里面会存在这有巨大影响的问题。比如一条1字节指令要把一个寄存器中的数据复制到另一个寄存器，在不分页的情况下这条指令只访问一次内存。有了分页机制之后，会因为要访问页表而引起多次的内存访问。同时，CPU的执行速度会被内存中取指令执行和取数据的速度拉低，所以会使性能下降。解决方案如下：
由于大多数程序总是对少量页面进行多次访问，因此只有很少的页表项会被反复读取，而其他页表项很少会被访问。针对这个问题，为计算机设置一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不必再去访问页表通过MMU得到物理地址，这个设备叫做转换检测缓冲区又叫做快表（TLB）。通常在MMU中，包含少量的表项，实际中应该有256个，每一个表项都记录了一个页面相关信息，即虚拟页号、修改为、保护码、对应的物理页框号，如下表所示：
| 有效位 | 虚拟页面号 | 修改位 | 保护位 | 页框号 |
|---|---|---|---|---|
| 1 | 140 | 1 | RW | 31 |
| 1 | 20 | 0 | R X | 38 |
| 1 | 130 | 1 | RW | 29 |
| 1 | 129 | 1 | RW | 62 |
| 1 | 19 | 0 | R X | 50 |
| 1 | 21 | 0 | R X | 45 |
| 1 | 860 | 1 | RW | 14 |
| 1 | 861 | 1 | RW | 75 |
TLB 其实就是一种内存缓存，用于减少访问内存所需要的时间，它就是 MMU 的一部分，TLB 会将虚拟地址到物理地址的转换存储起来，通常可以称为地址翻译缓存(address-translation cache)。TLB 通常位于 CPU 和 CPU 缓存之间，它与 CPU 缓存是不同的缓存级别。下面我们来看一下 TLB 是如何工作的。
当一个 MMU 中的虚拟地址需要进行转换时，硬件首先检查虚拟页号与 TLB 中所有表项进行并行匹配，判断虚拟页是否在 TLB 中。如果找到了有效匹配项，并且要进行的访问操作没有违反保护位的话，则将页框号直接从 TLB 中取出而不用再直接访问页表。如果虚拟页在 TLB 中但是违反了保护位的权限的话（比如只允许读但是是一个写指令），则会生成一个保护错误(protection fault) 返回。上面探讨的是虚拟地址在 TLB 中的情况，那么如果虚拟地址不再 TLB 中该怎么办？如果 MMU 检测到没有有效的匹配项，就会进行正常的页表查找，然后从 TLB 中逐出一个表项然后把从页表中找到的项放在 TLB 中。当一个表项被从 TLB 中清除出，将修改位复制到内存中页表项，除了访问位之外，其他位保持不变。当页表项从页表装入 TLB 中时，所有的值都来自于内存。
下面给出流程图：
软件 TLB 管理
直到现在，我们假设每台电脑都有可以被硬件识别的页表，外加一个 TLB。在这个设计中，TLB 管理和处理 TLB 错误完全由硬件来完成。仅仅当页面不在内存中时，才会发生操作系统的陷入(trap)。
但是有些机器几乎所有的页面管理都是在软件中完成的。
在这些计算机上，TLB 条目由操作系统显示加载。当发生 TLB 访问丢失时，不再是由 MMU 到页表中查找并取出需要的页表项，而是生成一个 TLB 失效并将问题交给操作系统解决。操作系统必须找到该页，把它从 TLB 中移除（移除页表中的一项），然后把新找到的页放在 TLB 中，最后再执行先前出错的指令。然而，所有这些操作都必须通过少量指令完成，因为 TLB 丢失的发生率要比出错率高很多。
无论是用硬件还是用软件来处理 TLB 失效，常见的方式都是找到页表并执行索引操作以定位到将要访问的页面，在软件中进行搜索的问题是保存页表的页可能不在 TLB 中，这将在处理过程中导致其他 TLB 错误。改善方法是可以在内存中的固定位置维护一个大的 TLB 表项的高速缓存来减少 TLB 失效。通过首先检查软件的高速缓存，操作系统 能够有效的减少 TLB 失效问题。
TLB 软件管理会有两种 TLB 失效问题，当一个页访问在内存中而不在 TLB 中时，将产生 软失效(soft miss)，那么此时要做的就是把页表更新到 TLB 中（我们上面探讨的过程），而不会产生磁盘 I/O，处理仅仅需要一些机器指令在几纳秒的时间内完成。然而，当页本身不在内存中时，将会产生硬失效(hard miss)，那么此时就需要从磁盘中进行页表提取，硬失效的处理时间通常是软失效的百万倍。在页表结构中查找映射的过程称为 页表遍历(page table walk)。如图：
上面的这两种情况都是理想情况下出现的现象，但是在实际应用过程中情况会更加复杂，未命中的情况可能既不是硬失效又不是软失效。一些未命中可能更软或更硬。比如，如果页表遍历的过程中没有找到所需要的页，那么此时会出现三种情况：
- 所需的页面就在内存中，但是却没有记录在进程的页表中，这种情况可能是由其他进程从磁盘掉入内存，这种情况只需要把页正确映射就可以了，而不需要在从硬盘调入，这是一种软失效，称为
次要缺页错误(minor page fault)。 - 基于上述情况，如果需要从硬盘直接调入页面，这就是
严重缺页错误(major page falut)。 - 还有一种情况是，程序可能访问了一个非法地址，根本无需向 TLB 中增加映射。此时，操作系统会报告一个
段错误(segmentation fault)来终止程序。只有第三种缺页属于程序错误，其他缺页情况都会被硬件或操作系统以降低程序性能为代价来修复
上面引入TLB加快虚拟地址到物理地址的转换，另一个要解决的问题就是处理巨大的虚拟空间，有两种解决方法：多级页表和倒排页表。
从整体来过一遍虚拟地址的概念，虚拟存储器的基本思想是：程序、数据和堆栈的总大小可能超过可用的物理内存的大小。由操作系统把程序当前使用的那些部分保留在主存中，而把其他部分保存在磁盘上。例如，对于一个16MB的程序，通过仔细地选择在每个时刻将哪4MB内容保留在内存中，并在需要时在内存和磁盘间交换程序的片段，这样这个程序就可以在一个4MB的机器上运行。
由程序产生的地址被称为虚拟地址，它们构成了一个虚拟地址空间。在使用虚拟存储器的情况下，虚拟地址不是被直接送到内存总线上，而且是被送到内存管理单元(Memory Management Unt,MMU)，MMU把虚拟地址映射为物理内存地址。
虚拟地址空间以页面为单位划分。在物理内存中对应的单位称为页帧。页面和页帧的大小总是一样的。
-
页表在哪儿
任何进程的切换都会更换活动页表集，Linux中为每一个进程维护了一个tast_struct结构体（进程描述符PCB），其中tast_struct->mm_struct结构体成员用来保存该进程页表。在进程切换的过程中，内核把新的页表的地址写入CR3控制寄存器。CR3中含有页目录表的物理内存基地址，如下图：
-
为什么省空间？
假如每个进程都有4GB的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到4GB，何必去映射不可能用到的空间呢？一级页表覆盖了整个4GB虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。
如果每个页表项都存在对应的映射地址那也就算了，但是，绝大部分程序仅仅使用了几个页，也就是说，只需要几个页的映射就可以了，如下图（左），进程1的页表，只用到了0,1,1024三个页，剩下的1048573页表项是空的，这就造成了巨大的浪费，为了避免内存浪费，计算机系统开发人员想出了一个方案，多级页表。
下面计算一下上图（右）的内存占用情况，对于一级页表来说，假设一个表项是4B，则
一级页表占用：1024 * 4 B= 4K
2级页表占用 = (1024 * 4 B) * 2 = 8K。
总共的占用情况是 12K，相比只有一个页表 4M，节省了99.7%的内存占用。
因此引入多级页表的原因就是避免把全部页表一直保存在内存中。
-
《深入理解计算机操作系统》 中的解释
假设32位的虚拟地址被划分为10位的PT1域、10位的PT2域和12位的偏移量域，工作过程如下：当一个虚拟地址被送到MMU时，MMU首先提取PT1域并把该值作为访问顶级页表的索引。由于虚拟空间为32G，顶级页表有2^10(PT1)^=1024个表项，则二级页表有2^10(PT2)^=1024个表项，每一个二级页表都含有虚拟地址对应物理地址的页框号，该页框号与偏移量结合便形成物理地址，放到地址总线送入内存中。
如果没有多级页表，则32位虚拟内存应该有100万个页面，这个存储开销是很大的，而有了多级页表，则实际只需要4个页表，顶级页表、0、1、1024这四个，顶级页表中的其他表项的“在/不在”为被设置为0，访问他们是强制产生一个缺页中断。
针对不断分级的页表的替代方案是倒排页表，实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项。
对于64位虚拟地址，4KB的页，4GB的RAM，一个倒排页表仅需要1048576个表项。
由于4KB的页面，因此需要2^64^/2^12^=2^52^个页面，但是1GB物理内存只能有2^18^个4KB页框
虽然倒排页表节省了大量的空间，但是它也有自己的缺陷：那就是从虚拟地址到物理地址的转换会变得很困难。当进程 n 访问虚拟页面 p 时，硬件不能再通过把 p 当作指向页表的一个索引来查找物理页。而是必须搜索整个倒排表来查找某个表项。另外，搜索必须对每一个内存访问操作都执行一次，而不是在发生缺页中断时执行。解决这一问题的方式时使用 TLB。当发生 TLB 失效时，需要用软件搜索整个倒排页表。一个可行的方式是建立一个散列表，用虚拟地址来散列。当前所有内存中的具有相同散列值的虚拟页面被链接在一起。如下图所示
如果散列表中的槽数与机器中物理页面数一样多，那么散列表的冲突链的长度将会是 1 个表项的长度，这将会大大提高映射速度。一旦页框被找到，新的（虚拟页号，物理页框号）就会被装在到 TLB 中。
当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出，以便为调入的页面腾出空间。如果被换出的页面在内存驻留期间被修改过，则必须写回磁盘更新，如果没有被修改过，不需要写回磁盘。
当发生缺页中断时候，可以随机的选择一个页面置换，但如果每次都选择不常使用的页面会提高性能。因为被频繁使用的页面在正常认知中都不可能要被换出，这会带来没必要的开销问题。
多说一句，页面置换思想在别的问题上也存在用武之地：
- 计算机的高速缓存cache。高速缓存满了之后就必须要丢掉，但是相比页面置换花费时间短，因为都是在内存中操作和获得，而内存没有寻道时间也没有旋转延迟。
- Web服务器。服务器把经常访问的页面放入存储器的高速缓存中，但当高速缓存已经满同时要访问一个不在高速缓存中的页面时候，就必须置换高速缓存中的某些web页面。不一样的地方在于高速缓存中的web页面不会被修改，虚拟内存中的页面有可能被修改过。
页面置换中的相关计算问题
缺页率：缺页次数/总次数
命中次数：总次数-缺页次数
接下来说一下具体的页面置换算法
该算法是一个理想算法，具体实现如下：
每个页面都有一个标记，记录了访问该页面要到多少条指令才能访问到。很显然，我们应该替换掉指令数最大的那个页面，比如页面A的指令数为2（两条指令后），页面B的指令数为1000（1000条指令后访问），这样我们就可以轻易淘汰页面B。
但是这个算法的问题是无法实现，因为在缺页中断时操作系统无法预知每个页面将在什么时候被访问到
可用作其他算法的性能评价的依据（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，这样会得到访问序列，根据这个序列来预知未来，在第二遍运行时即可使用最优算法），看一个实例：
如图，在0时刻时，内存中已经有了访问序列(a,b,c,d)，页帧表中可以看出给程序分配了4个物理页框，但是整个程序需要访问5个页面（abcde），物理页框不够，会产生页替换。随着时间的运行，在1-4 时间段内，都不会产生缺页中断，直到t=5 ,需要访问e，但是e的虚拟页不在内存中，需要选一个页替换出去。基于最优置换算法，选取离下一次访问时间最长的那个页是要被选择替换出去的，计算得出d访问时间距离为10，值最大，将d替换出去，把d留出的物理页空间给e。
结论：直到 t=10时，最优页面置换算法一共产生2次中断。
为了能够使得操作系统收集有用的统计信息，在大部分具有虚拟内存的计算机上，系统为每一个页面设置了两个状态位。当页面被访问时（读或者写）设置R位，当页面被修改时设置M位（这两个位都用01表示）。这些位包含在每一个页表项中，每次访问内存中时候会更新这些位。一旦某些位被设置为1，就保持1直到操作系统将他复位。
可以有R和M构造一个简单的页面置换算法，当启动一个进程时候，两个状态位由操作系统设置为0，R在每次时钟中断后就被清零，以区别最近没有被访问的页面和访问的页面。当发生缺页中断时，操作系统检查RM值，分为以下4类：
- 没有被访问没有被修改
- 没有被访问但被修改（这种情况一般由第四类过来，R位被时钟中断清零）
- 已被访问但没有修改
- 已被访问已被修改
该算法需要淘汰一个没有被访问但已修改页面，因为被频繁使用的的干净的页面总归要占据主要位置的。
基本思路：选择在内存中驻留时间最长的页面并将它淘汰。 具体来说，系统中维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。 当发生一个缺页中断时，把链首位置的页面淘汰出局，并把新的页面添加到链表的末尾。
**缺点：**性能较差，调出的页面有可能是经常要访问的页面，并且有Belady现象 (给的物理页越多，缺页就越多)。
在0时刻时，内存中已经有了访问序列(a,b,c,d)，页帧表中可以看出给跑的程序分配了4个物理页帧，但是整个程序需要访问5个页，物理页 不够，会产生页替换。随着时间的运行，在1-4 时间段内，都不会产生缺页中断，直到t=5 ,需要访问e，但是e的虚拟页不在内存中，需要选一个页替换出去。基于FIFO换算法，链表顺序为 a - b -c -d ，计算当前内存中驻留时间最久的页即a，将a替换出去，把a留出的物理页空间给e。接下来，当t=7时，访问a,a已经在t=5 时被替换出去了，产生一次中断，基于FIFO，将b换成a。
。。。。
结论：FIFO算法一共产生了5次中断，多于最优页面置换算法。
先进先出页面置换算法有一个缺点就是是按照时间来排序的，那如果最先进去的在链表首位的是经常要用的页面，把这个页面换出去是非常耗费效率的事情，因此该算法就是在先进先出算法上做一个简单的修改。
**含义：**检查最老页面（位于链首的页面）的R位。如果R位是0表明这个页面又老有没有被使用过，就直接换出该页面。如果R为1，则将R置为0.然后将该页面放到链尾处，这个时候这个页面相当于一个新的页面。非常的简单易懂。
在链表中移动页面降低效率又没有必要，因此更好的办法就是把所有页面保存在环形链表中，用指针指向最老的页面。如果发生缺页中断，算法首先检查指针指向的页面，如果R位是0就淘汰出局，并把新的页面插入该位置，然后指针下一移位。如果R是1就把指针下移，该工作模式更像是一个时钟，因此叫做时钟置换。
由于很久未被使用的页面在未来一段时间内仍然不会被使用（程序局部性原理），根据该思想就实现一个算法：在缺页中断发生时，置换未使用时间最长的页面，叫做LRU。
**实现：**在内存中维护一个所有页面的链表，最近最多使用的在表头，最近最少使用的在表尾。主要难点在于每次访问内存时候都必须更新整个链表（每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首）。在链表中找到一个页面，删除他，然后把它移动到表头是一个非常费时的操作，即使用硬件实现也是一样的。
用软件实现LRU的解决方案如下：
首先是NFU方案，该算法将没一个页面与一个软件技术器关联，计数器的初始值为0，每次缺页中断就由操作系统扫描内存中的所有页面，将所有页面的R位的值（0或1）加到计数器上，这个计数器大体上各个页面被访问的频繁程度，发生缺页中断时候置换计数器上值最小的页面。但是这个方案有个缺点就是计数器的值不会归零，导致会出现问题，即置换那些有用的页面而不是不再使用的页面，因此又出现了下面的改进算法。
老化算法，只是对NFU方案进行了小小的修改，用来模拟LRU。首先在R位被加到计数器上时将计数器右移一位，然后将R的值加到计数器的最左端。计数器用二进制表示哈。工作图如下：
上图a表示在时钟滴答0的时候访问了页面0245，因此最左边的值为1，对应上面五个页面的R位，就是这样看。
发生缺页中断的时候操作系统会比较六个计数器中的值然后置换最小的那个，这样就不会误伤。
在实践中，如果时钟滴答是20ms，则8位一般够用。
前提知识
在分页系统中刚启动进程时候，内存中是没有页面的，因此CPU试图取第一条指令时就会产生一次缺页中断，使操作系统装入含有第一条指令的页面。其他因为访问全局数据和堆栈引起的缺页中断也会紧接着发生。因此，页面是在需要的时候才会被装入，而不是预先装入。
一个进程当前正在使用的页面的集合称为工作集。如果一个工作集被装入到内存，那么进程在运行到下一运行阶段之前，不会产生很多缺页中断。如果内存比较小装不下一个工作集，就会产生大量缺页中断导致运行速度变得缓慢，因为几个纳秒就可以执行完一条指令，而需要几十毫秒才能从磁盘上读取一个页面。如果每执行几条指令就引发一次缺页中断，那么称该程序发生了颠簸
在多道程序设计系统中,经常把进程转移到磁盘上(移走全部页面),但是再转换回来就很容易发生缺页中断,遂引入工作集模型,确保进程在运行前,它的工作集就已经在内存中了.在程序运行前预先装入其工作集页面也称为预先调页.
最好的算法是老化算法和工作集时钟算法，他们分别基于LRU和工作集，都具有良好的页面调度性能，可以有效地实现。
我们说缺页中断发生时候会选择一个被页面来置换，但有一个主要问题就是怎样在相互竞争的可运行进程之间分配内存？因此有两种选择
**局部页面置换算法：**局部页面置换指的是只在本进程相关的页面中找一个进行置换。
**全局页面置换算法：**在所有的进程中找到一个合适的页面进行置换，这个页面可能是属于其他进程的。
全局算法在通常情况下工作的要比局部算法好，特别是当工作集大小随着进程运行时间而发生变化的情况下更明显。如果使用局部算法，即便有大量的空闲页框存在，工作集的增长也会导致颠簸。如果工作集缩小了，局部算法又会浪费内存。
要确定最佳页面大小需要在几个因素之间进行权衡，不存在全局最优。
文章更倾向于选择小页面，有几个理由：
- 随便选择一个正文段、数据段或堆栈段很可能不会恰好装满整个页面，平均情况下最后一个页面中有一半会是空的，而另一半空间就会被浪费掉了，这属于内部碎片。根据这方面考虑，还是小页面更好一点
- 如果一个程序每个阶段需要4KB内存，但是页面大小为32KB，就会浪费掉这些内存，但是页面大小如果是4KB就不会产生浪费。
小页面又有一些不足之处：
- 页面小意味着程序需要更多的页面，因此页表也就会变得更大。**由于内存与磁盘之间的传输一般是一次一页，传输中的大部分时间都花在寻道和旋转延迟上，所以传输一个小页面所用的时间和传输一个大页面基本是相同的。**因此装入64个512字节的页面需要64×10ms，但是装入4个8KB的页面只需要4×12ms
- 每次CPU从一个进程切换到另一个进程时都必须把新进程的页表装入硬件寄存器中。页面越小，页表越多意味着装入寄存器花费的时间就会越长，而且页表占用的空间也会随着页面减小而增大。
小页面能够更充分的利用TLB空间。假设程序使用的内存为1MB，工作单元为64KB。若使用4KB的页面，则程序将至少占用TLB中的16个表项。使用2MB的页面时，1TLB表就够了。由于TLB表相对比较稀缺，条件允许的情况下使用大页面是值得的。为了进行必要的平衡，操作系统有时会为系统中的不同部分使用不同的页面大小。比如内核使用大页面，用户进程使用小页面。
思想：进程可以通过发起一个系统调用将一个文件映射到其虚拟地址空间的一部分。在多数实现中，在映射共享的页面时候不会实际读入页面的内容，而是在访问页面时才会被每次一页的读入，磁盘文件则被当做后备存储。
如果两个或以上的进程同时映射了同一个文件，他们就可以通过共享内存来通信。 一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时候，可以看到上面有一个进程写操作的结果。
如果发生缺页中断时系统中有大量的空闲页框，此时分页系统工作在最佳状态。
如果每个页框都被占用，而且被修改过得话，当换入一个新页面时，旧页面应该首先被写回磁盘。
为保证有足够的空间页框，很多分页系统有一个称为分页守护进程的后台进程，它在大多数时候是睡眠的，但定期被唤醒已检查内存状态。如果空闲页框过少，分页守护进程通过预定的页面置换算法选择页面换出内存，如果这些页面被修改过，则写回磁盘。
与分页有关的工作主要有四段：进程创建时，进程执行时，缺页中断时，进程终止时。
-
进程创建时
创建一个新进程的时候，操作系统要确定程序和数据在初始化时有多大，并为他们创建一个页表。然后OS还要在内存中为页表分配空间并对其初始化。
当进程被换出时，页表就不需要驻留在内存中了，但是运行的时候必须在内存中。
OS在磁盘交换区中分配内存，以便在一个进程换出时在磁盘上有放置次进程的空间。OS还要用程序正文和数据对交换区初始化，这样当新进程发生缺页中断时候，可以调入需要的页面。
最后，OS必须把有关页表和磁盘交换区的信息存储在进程表中。
-
进程执行时
当调度一个新进程时候，必须重置MMU，刷新TLB，以清除以前的进程遗留的痕迹。新进程的页表必须成为当前页表，通常是复制该页表或者把指向该页表的指针放入某个硬件寄存器来实现的
在进程初始化时可以把该进程的部分或者全部页面装入内存以防止缺页中断
-
缺页中断时
当发生缺页中断时，OS通过读取硬件寄存器来确定是哪个虚拟地址造成了缺页中断，并在磁盘上对该页面进行定位。
然后找到合适的页框来存放新页面，必要时还要置换老的页面，然后把所需的页面读入页框。
然后回退程序计数器，使得程序计数器指向引起缺页中断的指令，并重新执行该指令。
-
进程终止时
进程退出的时候OS释放进程的页表，页面和页面在磁盘上所占用的空间。如果某些页面与其他进程共享，则当最后使用他的进程终止时才释放内存和磁盘。
-
硬件陷入内核，在堆栈中保存程序计数器。大多数机器将当前的指令，各种状态信息保存在特殊的CPU寄存器中。
-
启动一个汇编代码保存通用寄存器和其他易失信息，防止被操作系统破坏
-
当操作系统收到缺页中断信号后，定位到需要的虚拟页面。
-
找到发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。
如果不一致则杀掉该进程
如果地址有效且没有保护错误发生，系统会检查是否有空闲页框。如果没有空闲页框就执行页面置换算法淘汰一个页面。
-
如果选择的页框对应的页面发生了修改，即为“脏页面”，需要写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至全部把内容写到磁盘。
-
一旦页框是干净的，则OS会查找要发生置换的页面对应磁盘上的地址，通过磁盘操作将其装入。在装入该页面的时候，产生缺页中断的进程仍然被挂起，运行其他可运行的进程
-
当发生磁盘中断时表明该页面已经被装入，页表已经更新可以反映其位置，页框也被标记为正常状态。
-
恢复发生缺页中断指令以前的状态，程序计数器重新指向引起缺页中断的指令
-
调度引发缺页中断的进程
-
该进程恢复寄存器和其他状态信息，返回用户空间继续执行。
在没有分段之前我们讨论的都是一维的虚拟内存，如下图所示：
可以看到有调用堆栈、语法分析树、常量表、源程序正文、符号表这五部分。
堆栈的增长或者缩小是不可预估的，但是其他四个部分都是随着程序的运行而不断增长的。那么这个时候分配就是个问题了，这几个部分应该怎么分配才会在之间不会出现冲突呢？我们需要一个不需要程序员管理表扩展和收缩的方法。
因此一个直观并且通用的方法是在机器上提供多个互相独立的称为段的地址空间。每个段由一个从0到最大的线性地址序列构成。不同段的长度可以不同，段的长度在运行期间可以动态的改变。
每个段都构成了一个独立的地址空间，所以可以独立的增长或者减小而不影响到其他的段。如果一个在某个段中的堆栈需要更多的空间，就可以立刻得到需要的空间，因为其地址空间中没有其他的东西阻止其增长。段都很大，被装满的可能性很小。
对比两种存储管理的方法：
共同点：
段式存储和页式存储都离散地管理了进程的逻辑空间
不同点：
- 页是物理单位，段是逻辑单位
- 分页是为了合理利用空间，分段是为了满足用户要求
- 页的大小由硬件固定，段的长度可以动态的变化
- 页表信息是一维的，段表信息是二维的
集分页和分段有点于一体的一种存储管理方法
- 分页可以有效提高内存利用率
- 分段可以更好满足用户需求
段页式存储管理先将逻辑空间按段氏管理分成若干段再把段内空间按页式管理分成若干页，如下图：
考察几类死锁
了解如何出现，如何避免
大部分死锁都可资源有关。
**资源的定义：**在进程对设备，文件取得排他性访问时，有可能出现死锁。这类需要排他性使用的对象叫做死锁，资源可以使硬件设备或者一组信息。分为两类，可抢占资源和不可抢占资源。
-
可抢占资源
定义：可以从拥有他的进程中抢占而不会产生任何副作用，存储器就是一类可抢占资源。
比如现在A进程拥有了打印机，但是内存被B进程所占用，因此会产生死锁的风险。但是我们可以将B进程换出内存，把A进程换入内存就可以实现抢占进程B的内存，这样的内存资源就是可抢占的。
-
不可抢占资源
定义：在不引起相关的计算失败的情况下，无法把相关资源从占有他的进程处抢占过来。（反过来说就是如果这些资源被抢占了， 那么会引起相关操作失败）。比如磁盘光刻机，如果一个进程A开始刻录磁盘，但是突然刻录机被进程B占用了，那么这次磁盘刻录将失败，磁盘会被划坏。
+++
因此某个资源是否可以抢占主要取决于上下文环境。
总体来说死锁与不可抢占资源有关，有关抢占资源而引发的潜在死锁可以通过进程之间重新分配资源而化解，因此我们这里只关注不可抢占资源引起的死锁。
使用一个资源的过程可以概括为如下的三部分：
- 请求资源
- 使用资源
- 释放资源
当一个进程请求资源失败时，通常会处于请求资源、休眠、再请求这个循环中。这个进程虽然没有阻塞，但是确实没有做有价值的工作，实际和阻塞是一样的。
+++
死锁简介
死锁定义：如果一个进程集合中的每一个进程都在等待其他进程才能引发的事件，那么该进程就是死锁的。
由于所有进程都在等待，所以没有一个进程能够唤醒该进程集合中的其他进程的事件，因此所有的进程都只好无限等待下去
在大多数情况下每个进程所等待的是其他进程所释放的资源。换句话说就是产生死锁的进程集合中的每一个进程都在等待另一个死锁进程已经占有的资源，但是由于所有进程都不允许，任何一个都无法释放资源。这叫做资源死锁，是最常见的类型。
+++
发生资源死锁的四个必要条件：
- 互斥条件。每个资源要么分配给了一个进程，要么就是可用的。
- 占有和等待条件。已经得到某个资源的进程可以请求新的资源
- 不可抢占条件。已经分配给一个进程的资源不能强制性的被抢占，只能由占有它的进程释放掉
- 环路等待条件。死锁发生时，系统中一定有两个或两个以上的进程组成环路，该环路中的每个进程都等待着下一个进程所占用的资源。
死锁发生时，这四个条件一定是同时满足的，如果其中任意一条不成立就不会发生死锁！
+++
有四种处理死锁的策略：
- 忽略该问题
- 检测死锁并回复
- 仔细对资源进行分配
- 通过破坏引起死锁的必要条件之一
鸵鸟算法：把头埋在沙子里，当做无事发生。
有些人认为不论多大代价都要避免死锁，有的人认为假如死锁没五年发生一次，而每个月系统都因为硬件故障，编译错误而崩溃，那么大多数人肯定不会以性能损失和可用性为代价防止死锁
+++
这种技术指的是系统并不阻止死锁的产生，而是允许死锁发生，当检测到发生死锁后采取相应措施恢复
-
每种类型一个资源的死锁检测
每种资源类型只有一个资源，比如扫描仪、刻录机、磁带机等，但是每个设备只有一台，不能有多台。
我们可以为一个系统构造一个资源分配图，如下：
上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。
图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
+++
-
每种类型多个资源的死锁检测
如果有多种相同资源的存在就需要用另一种办法检测死锁。
上图中，有三个进程四个资源，每个数据代表的含义如下：
- E 向量：资源总量
- A 向量：资源剩余量
- C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
- R 矩阵：每个进程请求的资源数量
进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。
算法总结如下：
每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。
- 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
- 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
- 如果没有这样一个进程，算法终止。
+++
现在我们知道了如何检测死锁，但是另一个问题是何时去检测他们。
- 每当有资源请求时去检测，越早发现越好，但是这样会占用昂贵的CPU时间
- 每个k分钟检测一次，或当CPU的使用频率降到某一阈值的时候去
考虑到CPU使用效率的原因，如果死锁进程数达到了一定数量，就没有多少进程可以运行了，所以CPU会经常性空闲。
-
利用抢占恢复
在不通知原进程的情况下，将某一资源从一个进程强行取走给另外一个进程使用，接着又送回，这种做法是否可行取决于该资源本身的特性。用这种方法恢复通常来说比较困难或者不太可能。若选择挂起某个进程，则取决于那一个进程比较容易回收资源
-
利用回滚恢复
周期性的对进程进行备份，就是将进程的状态写入一个文件以备以后重启。这个行为叫做检查点检查，检查点中不仅包括存储映像，还有状态资源。同时新的检查点不应该覆盖原有的文件，而应该写到新文件中去。
有死锁发生就回滚到某一个时间点，该时间点后的所有工作全部丢失
-
通过杀死进程恢复
最直接最野蛮，就是打破环中的进行，或者原则环外的一个进程牺牲掉。
大多数系统中，一次只能请求一个资源。系统必须能够判断分配资源是否安全，并且只能在保证安全的条件下分配资源、因此是否存在一种算法总能正确作出选择从而避免死锁？答案是肯定的，但条件是必须事先获得一些信息。
图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。
定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。
一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。
上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态
上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。
检查一个状态是否安全的算法如下：
- 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
- 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
- 重复以上两步，直到所有进程都标记为终止，则状态时安全的。
如果一个状态不是安全的，需要拒绝进入这个状态。
-
破坏互斥条件
-
破坏占有并等待条件
-
破坏不可抢占条件
-
破坏环路等待条件
在面试那一篇文章中都有写。