文章介绍计算机操作系统基础。

概念基础

操作系统概念

操作系统是管理系统资源、控制程序执行、改善人机界面、提供各种服务，并合理组织计算机工作流程和为用户方便而有效地使用计算机提供良好运行环境的最基本的系统软件。

系统调用

系统调用是一种中介角色，把用户和硬件隔离开来，应用程序只有通过系统调用才可以请求系统服务并使用系统资源。系统调用的作用：

• 内核可以基于权限和规则对资源访问进行裁决，保证系统的安全性；
• 系统调用对资源进行抽象，提供一致性接口，避免用户在使用资源时发生错误，且使编程效率提高；

当 CPU 执行程序中预设的由访管指令实现的系统调用时，会产生异常信号，通过中断机制，处理器的状态由用户态转变为核心态，进入操作系统并执行相应的内核函数，以获得操作系统服务；当系统调用执行完毕时，控制返回至发出系统调用的程序，系统调用是应用程序获得操作系统服务的唯一途径。

内核是一组程序模块，作为可信软件来提供支持进程并发的基本功能和基本操作，通常驻留在内存空间，运行于核心态，具有访问硬件设备和所有主存空间的权限，是仅有的能够执行特权指令的程序。有了内核的支撑，机器功能得到扩展，进程运行环境得到改善，安全性得到保证，系统效率得到提高。

fork()

fork() 是 UNIX 或类UNIX 中的分叉函数，fork 函数将运行着的程序分成2个（几乎）完全一样的进程，每个进程都启动一个从代码的同一位置开始执行的线程。这两个进程中的线程继续执行，就像是两个用户同时启动了该应用程序的两个副本。

fork 系统调用用于创建一个新进程，称为子进程，它与进程（称为系统调用fork的进程）同时运行，此进程称为父进程。创建新的子进程后，两个进程将执行 fork() 系统调用之后的下一条指令。子进程使用相同的PC（程序计数器），相同的CPU寄存器，在父进程中使用的相同打开文件。

由于在复制时复制了父进程的堆栈段，所以两个进程都停留在fork函数中，等待返回。因此fork函数会返回两次，一次是在父进程中返回，另一次是在子进程中返回，这两次的返回值是不一样的。

//一次调用两次返回值，是在各自的地址空间返回，意味着现在有两个基本一样的进程在执行, 无参数。
pid_t fork(void);

fork调用的一个奇妙之处就是它仅仅被调用一次，却能够返回两次，它可能有三种不同的返回值：

• 如果成功创建一个子进程，对于父进程来说返回子进程ID；
• 如果成功创建一个子进程，对于子进程来说返回值为0；
• 如果为-1表示创建失败；

fork 如何知道一个进程是父进程还是子进程：这涉及到 fork 本身的功能，它的作用是克隆进程，也就是将原先的一个进程再克隆出一个来，克隆出的这个进程就是原进程的子进程，这个子进程和其他的进程没有什么区别，同样拥有自己的独立的地址空间。不同的是子进程是在fork返回之后才开始执行的，就像一把叉子一样，执行 fork 之后，父子进程就分道扬镳了，所以 fork 这个名字就很形象，叉子的意思。

孤儿进程和僵尸进程

在UNIX/Linux中，正常情况下，子进程是通过父进程创建的，子进程在创建新的进程。子进程的结束和父进程的运行是一个异步过程，即父进程无法预测子进程什么时候结束。当一个 进程完成它的工作终止之后，它的父进程需要调用 wait() 或者 waitpid() 系统调用取得子进程的终止状态。

孤儿进程

一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被 init 进程(进程号为1)收养，并由 init 进程对它们完成状态收集工作。孤儿进程是没有父进程的进程，孤儿进程这个重任就落到了 init 进程身上，init进程就好像是一个民政局，专门负责处理孤儿进程的善后工作。每当出现一个孤儿进程的时候，内核就把孤儿进程的父进程设置为init，而 init 进程会循环地 wait() 它的已经退出的子进程。这样，当一个孤儿进程结束其生命周期的时候，init 进程就会代表党和政府出面处理它的一切善后工作。因此孤儿进程并不会有什么危害。

僵尸进程

一个进程使用 fork 创建子进程，如果子进程退出，而父进程并没有调用 wait 或 waitpid 获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中，这种进程称之为僵死进程。UNIX 提供了一种机制可以保证只要父进程想知道子进程结束时的状态信息，就可以得到。这种机制就是：在每个进程退出的时候，内核释放该进程所有的资源,包括打开的文件,占用的内存等。但是仍然为其保留一定的信息(包括进程号，退出状态，运行时间等)。直到父进程通过wait / waitpid 来取时才释放。但这样就导致了问题，如果进程不调用wait / waitpid的话， 那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所能使用的进程号是有限的，如果大量的产生僵死进程，将因为没有可用的进程号而导致系统不能产生新的进程. 此即为僵尸进程的危害，应当避免。

处理器管理

中断

中断是指在程序执行过程中，遇到急需处理的事件时，暂时中止现行程序在CPU上的运行，转而执行相应的事件处理程序，待处理完成后在返回断点或调度其他程序执行。例如，从磁带上读入一组信息，当发现读入操作有误时，将产生读数据中断，操作系统停止当前的工作，并组织磁带退回重读这一组信息，这样就有可能克服错误。

强迫性中断和自愿性中断

按中断事件的性质和激活方式可将中断分成两类：强迫性中断和自愿性中断。

• 强迫性中断不是正在运行的程序所期待的，是由随机事件或外部请求信息引起的。强迫性中断事件有以下几种：
  • 机器故障中断：机器执行指令过程中硬件可能出现种种事件，例如，电源故障、通路校验错误、主存出错等；
  • 程序性中断：程序执行过程中可能发生种种例外情况，例如：非操作码错误、定点溢出、除数为0、地址越界；
  • 外部中断：由计算机系统外部发送中断信号，反映外界对本机的种种要求，例如，时钟中断、控制台中断、它机中断等；
  • 输入输出中断：来自通道、控制器、设备的中断能够反应I/O操作情况，例如：设备出错、传输结束、启动失败等；
• 自愿性中断事件是正在运行的程序所期待的，是由于执行“访管指令”而引起的，它表示运行程序对操作系统由某种需求，一旦机器执行访管指令，就会使CPU状态从用户态转向核心态，停止现行程序的执行而转入内核的相应系统调用例程进行处理。例如：要求操作系统协助启动外部设备工作。

硬中断和软中断

按中断事件的来源和实现手段划分可以将中断划分为硬中断和软中断。

• 硬中断可划分为外中断和内中断：
  • 外中断又称中断或异步中断，是指来自处理器之外的信号，包括时钟中断、键盘中断、它机中断和设备中断等。外中断又分为可屏蔽中断和不可屏蔽中断，各个中断具有不同的中断优先级，表示事件的紧急程度，在处理高一级中断时，往往会部分或全部屏蔽低级中断；
  • 内中断又称异常或同步中断，是指来自处理器内部的中断信号，通常是由于在程序执行过程中，发现与当前指令关联的、不正常的或错误的事件。
• 软中断：外中断和内中断（中断和异常）要通过硬件设施来产生中断请求，他们都是硬中断。与其对应的，不必由硬件产生中断源而引发的中断称为软中断。软中断利用硬中断中的概念，采用软件方法对中断机制进行模拟，实现宏观上的异步执行。软中断可分为两种：
  • “信号”是一种软中断机制，信号的发送者相当于中断源，而信号的接收者必然是一个进程（相当于CPU）；
  • “软件中断”是另一种软件中断机制，其第一个典型应用的例子是 Linux 中的 bottom half，它的升级就是Linux中最复杂、最庞大的软中断子系统 softirq 机制；第二个典型应用例子是 Windows 中由内核发出的Dispatch/DPC 和 APC 等中断，用于启动线程调度。延迟过程调用和异步过程调用的执行；

硬中断和软中断的类比

“中断”（硬中断）：用于外部设备对CPU的中断（中断正在运行的任何程序），转向中断处理程序执行；

“异常”（硬中断）：因指令执行不正常而中断CPU（中断正在执行这条指令的程序），转向异常处理程序执行；

“软件中断”（软中断）：用于硬中断服务程序对内核的中断，在上半部分中发出软件中断（即标记下半部分），使得中断下半部分在适当时刻获得处理；

“信号”（软中断）：用于内核或进程对某个进程的中断，向进程通知某个特定事件发生或迫使进程执行信号处理程序。

中断/异常的过程：

1. 发现中断源：在中断未被屏蔽的前提下，硬件发现中断/异常事件，并由CPU相应中断/异常请求。当发生多个中断源时，将根据预定的优先级先后相应中断请求；
2. 保护现场：暂停当前程序的运行，硬件将中断点的现场信息（PSW）保存至核心栈，使得中断处理程序/异常处理程序在运行时，不会破坏中断程序中的有用信息，以便在中断结束后返回源程序继续运行；
3. 转向中断/异常事件的处理程序：这时处理器状态已从用户态切换至核心态，中断处理程序/异常处理程序开始工作；
4. 恢复现场：当中断处理结束后，恢复PSW，重新返回中断点以便执行后续指令。

进程

进程定义

进程是操作系统中最基本、最重要的概念，是在多道程序系统出现后，为了刻画系统内部的动态状况、描述运行程序的活动规律而引进的新概念，所有多道程序设计操作系统都建立在进程的基础上。

从理论的角度看，进程的概念是对当前运行程序的活动规律的抽象；从实现角度看，进程是一种数据结构，用来准确刻画系统动态变化的内在规律，有效地管理和调度在计算机系统主存运行的程序。

引入进程的目的，一是为了刻画系统的动态性，发挥系统的并发性；二是解决共享性，正确地描述程序的执行状态。

所以，进程的定义如下：进程是可并发执行的程序在某个数据集合上的一次计算活动，也是操作系统进行资源分配和保护的基本单位。

进程状态

三态模型：

• 运行态：进程占用处理器运行的状态；
• 就绪态：进行具备运行条件，等待系统分配处理器以便其运行的状态；
• 等待态：又称阻塞态或睡眠态，指系统不具备运行条件，正在等待某个事件完成的状态；

五态模型：

在很多系统中，增加两个进程状态，新建态和终止态

新建态：进程被创建时的状态，进程尚未进入就绪状态。创建进程要通过两个步骤，首先，为进程分配所需的资源，建立必要的管理信息，然后，置此进程为就绪态，等待被执行；

终止态：进程完成任务，到达正常结束点，或因出现无法克服的错误而异常终止，或被操作系统及有终止权限的进程所终止时所处的状态；

处理器调度算法

先来先服务（FCFS）

• 按作业进入系统后背作业队列的先后次序来挑选作业，先进入系统的作业将优先被挑选进入主存，创建用户进程，分配所需资源，然后移入就绪队列；
• 非剥夺式调度算法；
• 只顾作业的等待时间，未考虑作业要求服务时间的长短，不利于短作业而优待长作业，不利于I/O繁忙型作业而有利于CPU繁忙型作业；
• FCFS算法同样适用于进程/线程调度，每次从就绪队列中选择最先进入此队列的进程/线程，它一直运行，直至完成或出现等待事件而被阻塞而让出处理器为止；

需要说明的是，在进行处理器调度时，允许作业调度和进程/线程调度分别采用不同的调度算法，而且往往需要采用不同的调度算法处理这两级调度。

最短作业优先（SJF）

• 以进入系统的作业所要求的CPU运行时间的长短为标准，总是选取预计计算时间最短的作业投入运行；
• 非剥夺式调度算法；
• 需要预先直到作业所需的CPU运行时间，很难精确估算；忽视作业的等待时间，进入系统时间早但计算时间长的长作业有可能出现饥饿现象；
• SJF也可以用于低级调度，借用作业的估计运行时间作为进程/线程的估计运行时间，调度时从就绪队列中选择一个估计运行时间最短者投入运行。若具有相同的估计运行时间，就对其按照FCFS算法处理；

最短剩余时间

• 上面的最短作业优先算法是非剥夺式，可将其改造为剥夺式调度算法；

• 假设当前某进程/线程正在运行，如果有新进程/线程移入就绪队列，若它的所需的CPU运行时间比当前运行进程/线程所需的剩余CPU时间还短，抢占式最短作业优先算法强行剥夺当前执行者的控制权，调度新进程/线程执行，这叫做最短剩余时间优先算法；

响应比最高优先

• 响应比最高优先是介于FCFS和SJF算法之间的一种折衷的非剥夺式算法，即考虑作业的等待时间，又考虑作业的处理时间，这样既照顾短作业又不会使长作业等待时间过长；
• 缺点是每次计算各道作业的响应比会导致一定的时间开销，其性能比SJF略差。等待时间与处理时间之和是系统对作业的响时间，它与处理时间的比值称为响应比。

优先级调度

• 根据确定的优先级来选取进程/线程，总是选择就绪队列中的优先级最高者投入运行；
• 系统可以预先规定策略：剥夺式与非剥夺式；
• 进程/线程的优先级的确定可采用静态式/动态式，基本原则是：正在运行的进程/线程随着占用CPU的时间的增加，逐渐降低其优先级；就绪队列中等待CPU的进程/线程随着等待时间的增加，逐渐提高其优先级，这样可以克服静态优先级饥饿的问题。

轮转调度

• 也称时间片调度算法。调度程序每次把CPU分配给就绪队列队首进程/线程使用规定的时间间隔，称为时间片。就绪队列中每个进程/线程轮流地运行一个时间片，当时间片耗尽，就强迫当前运行的进程/线程让出处理器，转而排列到就绪队列的尾部，等待下一轮调度；
• 剥夺式调度；
• 系统耗费在进程/线程切换上的开销比较大，这个开销与时间片取值有关；

多级反馈队列调度

• 操作系统建立一个多个就绪队列，每个队列对应一个优先级，第一个队列的优先级最高，其后的队列的优先级逐渐降低；
• 较高优先级队列的进程/线程分配给较短的时间片，较低优先级队列的进程/线程分配给较长的时间片，最后一个队列进程/线程按FCFS算法进行调度；
• 处理器调度每次先从第一个队列选取执行者，同一队列中的进程/线程按照FCFS原则排队，只有在未选到时，才从较低一级的就绪队列中选取，仅当前面所有队列为空时，才会运行最后一个就绪队列中的进程/线程；

同步、通信与死锁

进程通信

进程间通信主要包括管道、系统 IPC（包括消息队列、信号量、信号、共享内存等） 、以及套接字 socket。

• 管道

  管道主要包括无名管道和命名管道：管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。

  • 普通管道 PIPE：
    • 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端；
    • 它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）；
    • 它可以看成是一种特殊的文件，对于它的读写也可以使用普通的 read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中；
  • 命名管道 FIFO：
    • FIFO 可以在无关的进程之间交换数据；
    • FIFO 有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。

• 系统 IPC

  • 消息队列
    • 消息队列，是消息的链接表，存放在内核中。 一个消息队列由一个标识符（即队列 ID）来标记。消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等特点。具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；
    • 特点
      • 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级；
      • 消息队列独立于发送与接收进程。 进程终止时，消息队列及其内容并不会被删除；
      • 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取；
  • 信号量 semaphore
    • 信号量（semaphore） 与已经介绍过的 IPC 结构不同，它是一个计数器，可以用来控制多个进程对共享资源的访问。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据；
    • 特点
      • 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存；
      • 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作；
      • 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数；
      • 支持信号量组；
  • 信号 signal
    • 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；
  • 共享内存 Shared Memory
    • 它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。 这种方式需要依靠某种同步操作，如互斥锁和信号量等
    • 特点
      • 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取；
      • 因为多个进程可以同时操作，所以需要进行同步；
      • 信号量 + 共享内存通常结合在一起使用，信号量用来同步对共享内存的访问；
  • 套接字 SOCKET
    • 与其他通信机制不同的是， SOCKET 可用于不同主机之间的进程通信；

线程间通信与同步

• 临界区：通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问；

• 互斥量 Synchronized/Lock：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问；

• 信号量 Semphare：为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般需要限制同一时刻访问此资源的最大线程数目；

• 事件(信号) Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作；

协程

协程非常类似于线程。但是协程是协作式多任务的，而线程是抢占式多任务的。这意味着协程提供并发性而非并行性。

协程超过线程的好处是它们可以用于硬性实时的语境（在协程之间的切换不需要涉及任何系统调用或任何阻塞调用），这里不需要用来守卫关键区块的同步性原语（primitive）比如互斥锁、信号量等，并且不需要来自操作系统的支持。

有可能以一种对调用代码透明的方式，使用抢占式调度的线程实现协程，但是会失去某些利益，特别是对硬性实时操作的适合性和相对廉价的相互之间切换。

死锁

死锁产生

• 互斥条件：系统中存在临界资源，进程应互斥地使用这些资源；

• 占有和等待条件：进程在请求资源得不到满足而等待时，不释放已占有的资源；

• 不剥夺条件：已被占用的资源只能由属主释放，不允许被其他进程剥夺；

• 循环等待条件：存在循环等待链，其中，每个进程都在链中等待下一个进程所持有的资源，造成这组进程处于永远等待状态；

前三个条件是死锁存在的必要条件，但不是充分条件，第4个条件是前3个条件同时存在时所产生的结果，故条件并不完全独立。但是，单独考虑每个条件是有用的，只要能破坏4个必要条件中的一个，就可以防止死锁。

解决死锁问题有三种策略和方法：死锁防止、死锁避免、死锁检测和解除。

死锁防止

死锁的防止是指系统预先确定资源分配策略，进程按此规定来申请和使用资源，保证死锁有一个必要条件不会被满足，使得系统不发生死锁；其缺点是降低系统的并发性质，资源利用率低。

死锁避免

死锁避免允许系统中同时存在前3个必要条件，通过合适的资源分配算法确保不会出现进程循环等待链，从而避免死锁。

死锁避免方法能支持更多的进程并发执行，它不是对进程随意强加规则，而是动态地确定是否分配资源给提出请求的进程。如果一个进程当前请求的资源会导致死锁，系统将拒绝启动该进程；如果一个资源的分配会导致下一步死锁，系统会拒绝本次分配。

银行家算法是的死锁避免算法，但缺乏实用价值。

死锁检测与恢复

对资源的分配加以适当的限制可防止和避免死锁的发生，但是不利于进程对系统资源的充分共享。解决死锁的另一条路径是死锁检测和解除，这种方法对资源的分配不施加任何限制，也不采取死锁避免措施，系统定时地运行死锁检测程序，判断是否已经出现死锁，如果检测到系统已死锁，再采取措施解除它。

这种方法的难点在于：要确定何时运行死锁检测算法，如果这一算法执行的很频繁，将会浪费处理器时间；如果执行太稀疏，则死锁进程和系统资源会一直被锁定。

存储管理

存储管理是操作系统的重要组成部分，负责管理计算机系统的重要资源-主存储器。由于任何程序和数据必须占用主存空间才能得以执行和处理，因此，存储管理的优劣直接影响操作系统的性能。主存储器对数据的存取比处理器处理数据的速度慢得多，通过高速缓存可以部分缩小差距，但高效的主存管理仍然是操作系统设计中重要课题。

主存空间一般分为两部分：一部分是系统区，用于存放操作系统内核程序和数据结构等，另一部分是用户区，用于存放应用程序和数据。存储管理对核心区和用户区都提供相应的支持和管理。尽管现代计算机的主存容量不断增大，但仍不能保证有足够大的空间支持大型应用和系统程序及数据的使用。操作系统的主要任务之一是尽可能方便用户使用和提高主存利用率。存储管理的主要作用如下：

• 分配和去配：进程可请求对主存区的独占式使用，主存区的请求和释放即主存空间的分配和去配操作由存储管理完成；

• 抽象和映射：主存储器被抽象，使得进程认为分配给他的地址空间是一个大且连续地址所组成的数组，或者把主存储器抽象成二维地址空间，以支持模块化程序设计；同时建立抽象机制支持进程用逻辑地址来映射到物理主存单元，实现地址转换；

• 隔离和共享：系统负责隔离已分配给进程的主存区，互不干扰免遭破坏，确保进程对存储单元的独占式使用，以实现存储保护功能；系统允许多个进程共享存储区，在这种情况下，超越隔离机制并授权进程允许共享访问，达到既能提高主存利用率又能共享主存某区内信息的目的；

• 主存扩容：物理主存容量不应限制应用程序的大小，主存和辅助存储器被抽象为虚拟主存，允许用户的虚拟地址空间大于主存物理地址空间，存储管理自动在不同的存储层次中移动信息；

堆和栈

参考资料

• 管理方式：栈由编译器自动管理；堆由程序员控制，使用方便，但易产生内存泄露；

• 生长方向：栈向低地址扩展(即”向下生长”)，是连续的内存区域；堆向高地址扩展(即”向上生长”)，是不连续的内存区域。这是由于系统用链表来存储空闲内存地址，自然不连续，而链表从低地址向高地址遍历；

• 空间大小：栈顶地址和栈的最大容量由系统预先规定(通常默认2M 或 10M)；堆的大小则受限于计算机系统中有效的虚拟内存，32位 Linux 系统中堆内存可达2.9G 空间；

• 存储内容：栈在函数调用时，首先压入主调函数中下条指令(函数调用语句的下条可执行语句)的地址，然后是函数实参，然后是被调函数的局部变量。本次调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的指令地址，程序由该点继续运行下条可执行语句。堆通常在头部用一个字节存放其大小，堆用于存储生存期与函数调用无关的数据，具体内容由程序员安排；

• 分配方式：栈可静态分配或动态分配。静态分配由编译器完成，如局部变量的分配。动态分配由 alloca 函数在栈上申请空间，用完后自动释放。堆只能动态分配且手工释放；

• 分配效率：栈由计算机底层提供支持：分配专门的寄存器存放栈地址，压栈出栈由专门的指令执行，因此效率较高。堆由函数库提供，机制复杂，效率比栈低得多。Windows 系统中 VirtualAlloc 可直接在进程地址空间中分配一块内存，快速且灵活；

• 分配后系统响应：只要栈剩余空间大于所申请空间，系统将为程序提供内存，否则报告异常提示栈溢出。

• 操作系统为堆维护一个记录空闲内存地址的链表。当系统收到程序的内存分配申请时，会遍历该链表寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点空间分配给程序。若无足够大小的空间(可能由于内存碎片太多)，有可能调用系统功能去增加程序数据段的内存空间，以便有机会分到足够大小的内存，然后进行返回。，大多数系统会在该内存空间首地址处记录本次分配的内存大小，供后续的释放函数(如free/delete)正确释放本内存空间。此外，由于找到的堆结点大小不一定正好等于申请的大小，系统会自动将多余的部分重新放入空闲链表中；

• 碎片问题：栈不会存在碎片问题，因为栈是先进后出的队列，内存块弹出栈之前，在其上面的后进的栈内容已弹出。而频繁申请释放操作会造成堆内存空间的不连续，从而造成大量碎片，使程序效率降低。可见，堆容易造成内存碎片；由于没有专门的系统支持，效率很低；由于可能引发用户态和内核态切换，内存申请的代价更为昂贵。所以栈在程序中应用最广泛，函数调用也利用栈来完成，调用过程中的参数、返回地址、栈基指针和局部变量等都采用栈的方式存放。所以，建议尽量使用栈，仅在分配大量或大块内存空间时使用堆；

• 使用栈和堆时应避免越界发生，否则可能程序崩溃或破坏程序堆、栈结构，产生意想不到的后果。

连续存储管理

固定分区存储管理

固定分区存储管理的基本思想是：主存空间被划分成数目固定不变的分区，各分区的大小不等，每个分区只装入一个作业，若多个分区中都装有作业，则它们可以并发执行，这是支持多道程序设计的最简单的存储管理技术。

地址转换与存储保护

磁盘中的装载代码模块所使用的是逻辑地址，其逻辑地址集合称为进程的逻辑地址空间。逻辑地址可以是一维的，这时逻辑地址限制在从0开始的顺序排列的地址空间内；逻辑地址空间也可以是二维的，这是整个程序被分为若干段，每段都有不同的编号，段内地址从0开始顺序编址。

物理主存储器从统一的基地址开始顺序编址的存储单元称为物理地址或绝对地址，物理地址的总体构成物理地址空间。需要注意的是，物理地址空间是由存储器地址总线扫描出来的空间，其大小取决于实际安装的主存容量。

把逻辑地址转化为物理地址的过程称为地址重定位、地址映射或地址转换。与静态地址重定位相比，动态地址重定位具有允许程序在主存中移动、便于程序共享和主存利用率高等优点。

可变分区存储管理

常用的可变分区分配算法有以下五种：

• 最先适应分配算法：最先适应分配算法顺序查找未分配区表或链表，直至找到第一个能满足长度要求的空闲分区为止，分割此分区，一部分分配给作业，另一部分仍为空闲区（若有）；
• 下次适应分配算法：下次适应分配算法总是从未分配区的上一次扫描结束处顺序查找未分配区表或链表，直至找到第一个能满足长度要求的空闲区为止。这是最先适应分配算法的变种，能缩短平均查找时间，且存储空间利用率更加均衡，不会导致小空闲区集中于主存储器的一端；
• 最优适应分配算法：最优适应分配算法扫描整个未分配区表或链表，从空闲区挑选一个能满足用户进程要求的最小的分区进行分配。此算法保证不会分割更大的区域，使得装入大作业的要求容易得到满足。同时，通常把空闲区按长度递增顺序排列，查找时总是从最小的一个空闲区开始，直至找到满足要求的分区为止，此时最优适应分配算法等同于最先适应分配算法。此算法主存利用率好，所找出的分区如果正好满足要求则是最合适的。如果比所要求的分区略大则分割后使剩下的空闲分很小，难以利用，其查找时间也是最长的；
• 最坏适应分配算法：最坏适应分配算法扫描整个未分配区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是使剩下二点空闲区不至过小，对中小型作业有利。采用此分配算法可把空闲区按照长度递减顺序排列，查找时只需看第一个分区能否满足进程需求，这样使最坏适应分配算法的查找效率很高，此时，最坏适应分配算法等同于最先适应分配算法；
• 快速适应分配算法：快速适应分配算法为那些经常用到的长度的空闲区设立单独的空闲区链表；

分页存储管理

用分区方式管理存储器，每道程序要求占用主存的一个或多个连续存储区域，导致主存中产生“碎片”。有时为了接纳新作业，往往需要移动已在主存的信息，这样不仅不方便，而处理器的开销太大。

采用分页存储管理允许程序存放到若干不相邻的空闲块中，既可免除移动信息工作，又可以充分利用主存空间，消除动态分区法中的”碎片“问题，从而提高主存空间的利用率。

相关概念

页面：进程逻辑地址空间划分成大小相等的区，每个区称为页面或页，页号从0开始依次编号；

页框：页框又称页帧，把主存物理地址空间分成大小相等的区，其大小与页面大小相等，每个区是一个物理块或页框，块号从0开始依次编号；

逻辑地址：分页存储器的逻辑地址由两部分组成，页号和页内偏移，格式为：页号 页内偏移；

页号表示地址所在页面的编号，后面部分表示页内偏移。计算机地址总线通常是32位，页面尺寸若规定为12位（页长 4KB），那么，页号共20位，表示地址空间最多包含2^20个页面。

采用分页存储管理时，逻辑地址是连续的，用户在编制程序时仍使用相对地址，不必考虑如何分页，由硬件地址转换机构和操作系统的管理来决定页面尺寸，从而确定主存分块大小。进程在主存中的每个页框内的地址是连续的，但页框之间的地址可以不连续，进程主存地址由连续到离散的变化为虚拟存储器的实现奠定了基础。

页表：使用动态地重定位技术，让程序在执行时动态地进行地址变换，由于程序以页面为单位进行存储，所以为每个页面设立一个重定位寄存器，这些重定位寄存器地集合称为页表。页表是操作系统为进程建立的，是程序页面和主存对应页框的对照表，页表中的每一栏指明程序中的一个页面和分得页框的对应关系。使用页表的目的是把页面映射为页框。

快表

页表可存放在一组寄存器中，地址转换时只要从相应寄存器中取值就可以得到页框号，这样做虽然能加快地址转换，但硬件代价太高；页表也可以放在主存中，这样做可以降低系统开销，但是按照给定逻辑地址进行读写操作时，至少访问主存两次：一次访问页表，另一次根据物理地址访问指令或存取数据，这样降低运算速度，比通常执行指令的速度慢一半。

为了提高运算速度，在硬件中设置相联存储器，用来存放进程最近访问的部分页表项，也称转换后缓冲（Transaction Lookaside Buffer， TLB）或者快表，它是分页存储管理的重要组成部分。

快表的存取时间远小于内存，速度快但造价高，故容量较小，只能存放几十个页表项。快表包含页号和对应的页框号，当把页号交给快表后，它通过并行匹配同时对所有快表项进行比较，如果找到，则立即输出页框号，并形成物理地址；如果找不到，再查找主存中的页表以形成物理地址，同时将页号及页框号登记到快表中，当快表已满且要登记新页时，系统需要淘汰旧的快表项，最简单的策略就是先进先出，总是淘汰最先登记的页。需要注意的是，快表和高速换粗是不同的，两者再一个系统中可同时使用，前者记录最近转换的页号及页框号，后者保存最近实际访问的指令或者数据副本。

多级页表

现代操作系统普遍支持2^32~2^64B容量的逻辑地址空间，采用分页存储管理时，页表相当大。

以Windows为例，其运行的Intel x86 平台具有32位地址，规定页面4KB（2^12）, 那么4GB（2^32）的逻辑地址空间由1M（2^20）个页组成，若每个页表项占用4B，则需要占用4MB（2^20）连续主存空间来存放页表，这还是一个进程的地址空间。对于地址空间为64位的系统而言，问题会更加复杂。

为此， 页表和页面一样也需要进行分页，这就是多级页表的概念。具体做法是：把整个页表分割成许多小页表，每个小页表称为页表页，其大小与页框长度相同，于是，每个页表页含有若干页表表项。

分段存储管理

促使存储管理方式从固定分区到动态分区，从分区方式向分页方式发展的主要原因是要提高主存空间利用率。那么，分段存储管理的引入主要满足用户（程序员）编程和使用上的要求，其他存储管理技术难以满足这些要求。

在分页存储管理中，经链接编辑处理得到一维地址结构的可装配目标模块，这是从0开始编址的单一连续逻辑地址空间，虽然可以把程序划分成页面，但页面与源程序并不存在逻辑关系，也就难以对源程序以模块为单位进行分配、共享和保护。事实上，程序更多是采用分段结构，高级语言往往采用模块化程序设计方法。应用程序由若干程序段（模块）组成，例如，由主程序段、子程序段、数据段和工作区段组成，每段都从0开始编址，有各自的名字和长度，且实现不同的功能。

分段存储管理把进程的逻辑地址空间分成多段，二维逻辑地址形式为：段号 段内位移。分段存储管理的实现基于可变分区存储管理的原理。可变分区以整个作业为单位来划分和连续存放，也就是说，作业在分区内是连续存放的，但独立作业之间不一定连续存放。而分段方法是以段位单位来划分和连续存放，为作业的各段分配一个连续的主存空间，而各段之间不一定连续。在进行存储分配时，应为进入主存的作业建立段表，各段在主存中的情况可由段表来记录，它指出主存中各分段的段号、段起始地址和段长度。在撤销进程时，回收所占用的主存空间，并清除此进程的段表。

分段和分页的比较

分段是信息的逻辑单位由源程序的逻辑结构及含义所决定，是用户可见的，段长由用户根据需求来决定，段起始地址可以从任何主存地址开始。在分段方式中，源程序（段号、段内位移）经链接装配后仍保持二维（地址）结构，引入目的是满足用户模块化程序设计的需要。

分页是信息的物理单位与源程序的逻辑结构无关，是用户不可见的，页长由系统（硬件）确定，页面只能从页大小的整数倍地址开始。在分页方式中，源程序（分页、页内位移）经链接装配后变成一维（地址）结构，引入的目的是实现离散分配并提高主存利用率。

虚拟存储管理

前面介绍的存储管理称为实存管理，必须为进程分配足够的主存空间，装入其全部信息，否则进程无法运行。把进程的全部信息装入主存后，实际上并非同时使用，有些部分运行一遍，有些部分甚至从来不使用，进程在运行时不用的，或暂时不用的，或某些条件下才用的程序和数据，全部驻留于主存中是对宝贵存储资源的一种浪费，降低主存的利用率。于是，提出新的想法：不必装入进程的全部信息，仅将当前使用部分先装入主存，其余部分存放在磁盘中，待使用时由系统自动将其装进来，这就是虚拟存储管理技术的基本思路。

虚拟存储器的定义：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换的功能，能从逻辑上为用户提供一个比物理主存容量大得多的、可寻址的”主存储器“。

虚拟内存使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如 RAM）的使用也更有效率。目前，大多数操作系统都使用了虚拟内存，如 Windows 家族的“虚拟内存”；Linux 的“交换空间”等。

局部性原理

局部性原理表现在以下两个方面：

• 时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作；

• 空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的；

时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。

空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。

请求分页虚拟存储管理

MMU

现代处理器使用的是一种称为虚拟寻址(Virtual Addressing) 的寻址方式。使用虚拟寻址，CPU 需要将逻辑地址翻译成物理地址，这样才能访问到真实的物理内存。完成虚拟地址转换为物理地址转换的硬件是 CPU 中的 MMU。

注：操作系统的存储管理依靠底层硬件的支撑来完成任务，此硬件称为主存管理部件（Memory Management Unit，MMU），它提供地址转换和存储保护功能，并支持虚拟存储管理和多任务管理。

虚拟地址空间的作用

没有虚拟地址空间的时候，程序直接访问和操作的都是物理内存，会存在以下问题：

• 用户程序可以访问任意内存，寻址内存的每个字节，这样就很容易（有意或者无意）破坏操作系统，造成操作系统崩溃；

• 想要同时运行多个程序比较困难。例如微信在运行的时候给内存地址 1xxx 赋值后，QQ 音乐也同样给内存地址 1xxx 赋值，那么 QQ 音乐对内存的赋值就会覆盖微信之前所赋的值，这可能会造成微信崩溃；

总结来说：如果直接把物理地址暴露出来的话会带来严重问题，比如可能对操作系统造成伤害以及给同时运行多个程序造成困难。

虚拟内存技术使得不同进程在运行过程中， 它所看到的是自己独自占有了当前系统的 4G 内存。所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。 事实上，在每个进程创建加载时，内核只是为进程“创建” 了虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data 段）拷贝到物理内存中， 只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射），等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。还有进程运行过程中， 要动态分配内存，比如 malloc 时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

请求分页系统、 请求分段系统和请求段页式系统都是针对虚拟内存的， 通过请求实现内存与 外存的信息置换。

虚拟内存的好处

• 扩大地址空间；

• 内存保护：每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。虚存还对特定 的内存地址提供写保护，可以防止代码或数据被恶意篡改；

• 公平内存分配。采用了虚存之后，每个进程都相当于有同样大小的虚存空间；

• 当进程通信时，可采用虚存共享的方式实现；

• 当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存；

• 虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把 CPU 交给另一个进程使用。在内存中可以保留多个进程，系统并发度提高；

• 在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片；

虚拟内存的代价

• 虚存的管理需要建立很多数据结构，占用额外的内存；

• 虚拟地址到物理地址的转换，增加了指令的执行时间；

• 页面的换入换出需要磁盘 I/O，较为耗时；

• 如果一页中只有一部分数据，会浪费内存。

虚拟内存技术的实现

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。虚拟内存的实现有以下三种方式：

• 请求分页存储管理 ：建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。

• 请求分段存储管理 ：建立在分段存储管理之上，增加了请求调段功能、分段置换功能。请求分段储存管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。

• 请求段页式存储管理

请求分页存储与分页存储

请求分页存储管理建立在分页管理之上，根本区别是是否将程序全部所需的全部地址空间都装入主存，请求分页存储管理不要求将作业全部地址空间同时装入主存，这也是请求分页存储管理可以提供虚拟内存的原因。

不管是上面那种实现方式，一般都需要：

• 一定容量的内存和外存：在载入程序的时候，只需要将程序的一部分装入内存，而将其他部分留在外存，然后程序就可以执行了；

• 缺页中断：如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序；

• 虚拟地址空间 ：逻辑地址到物理地址的变换；

页面置换算法

在多道程序的正常运行过程中，属于不同进程的页面被分散存放在准村页框中，当发生缺页中断时，如果已无空闲页框，系统要选择一个驻留页面继进行淘汰。这里讨论的是所有驻留页面都可作为置换对象的情况，而不管页面所属进程的全局页面替换算法。

注：缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。在这个时候，被内存映射的文件实际上成了一个分页交换文件。

最佳页面置换算法

OPT 选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在主存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。一般作为衡量其他置换算法的方法。

先进先出页面置换算法

FIFO总是淘汰最先调入主存的页面，即选择在主存中驻留时间最久的页面进行淘汰。

最近最久未使用页面置换算法

LRU淘汰的页面是在最近一段时间内最久未被访问的那一页，是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还要被使用，而那些在较长时间内未被使用的页面可能不会立即被使用。

LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。

第二次机会页面替换算法

FIFO算法会把经常使用的页面淘汰掉，为了避免这一点，可对算法继续宁改造，把FIFO算法也页表中的”引用位“结合起来使用，这就是 Second Chance Replacement算法。

实现思想如下：首先检查FIFO页面队列中的队首，这是最早进入主存的页面，如果其”引用位“是0.那么这个页面既时间长又没有用，选择此页面淘汰，如果是1，说明虽然它进入主存的时间比较早，但最近仍然使用，于是将其引用位清0，并把这个页面移至队尾，把它看作一个新调入的页，再给一次机会。

时钟轮转

如果利用标准队列机制构造 FIFO 队列，SCR算法可能会产生频繁的出队和入队，实现代价较大，可采用循环队列机制构造页面队列，形成类似于钟表面的环形表，队列指针相当于钟表面上的指针，指向可能淘汰的页面，这就是时钟页面淘汰算法的得名。此算法和 SCR 本质上没有什么区别，仅仅是实现方法有所改变，仍然要使用页表中的“引用位”，把进程已调入主存的页面链接成循环队列，用指针指向循环队列中下一个将被替换的页面。

最少使用页面置换算法

Least Frequently Used 选择在之前时期使用最少的页面作为淘汰页。

参考资料

操作系统教程第四版 - 高等教育出版社

JavaGuide - 操作系统

孤儿进程与僵尸进程总结

wiki - 协程

廖雪峰 - 协程

虚拟内存

Linux虚拟地址空间布局