操作系统

Jan 10, 2025

82 mins read

CS Basic

Cs basic

1. 第一章操作系统概述

1.1 操作系统概念、特征

操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理的组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境集合。

并发

并发是指两个或多个事件在同一时间间隔内发生。操作系统的并发是通过分时得以实现的。操作系统的并发性是指计算机系统中同时存在多个运行着的程序，因此它具有处理和调度多个程序同时执行的能力。

共享

资源共享就是共享，系统中的资源可供内存中多个并发执行的进程同时使用，可分为以下两种。

互斥共享方式

比如打印机，不能同时打印两份内容，不然会造成内容混淆。
同时访问方式

交替的对该资源进行访问 “分时共享”。

虚拟

操作系统中利用了多种虚拟技术，分别用来实现虚拟处理机、虚拟内存和虚拟外部设备。

在虚拟处理器技术中，让多道程序并发执行来分时使用一台处理器，虽然只有一台处理器，但是能同时为多个用户服务。把一台物理上的CPU虚拟为多态逻辑上的CPU称为虚拟处理器。

虚拟存储器，从逻辑上来扩充存储器的容量。

虚拟设备技术，将一台物理IO设备虚拟为多台逻辑上的IO设备，允许多个用户同时访问的共享设备。

异步

在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

操作系统的目标和功能

为了给多道程序提供良好的运行环境，操作系统应该具有：处理器管理、存储器管理、文件管理和设备管理，还必须向用户提供接口，同时操作系统可用来扩充机器，以提供更方便的服务、更高的资源利用率。

处理器管理

对处理器的管理可归结为对进程的管理，主要功能有：进程控制、进程同步、进程通信、死锁处理、处理器调度等。
存储器管理

方便用户使用以及提高内存的利用率，存储器管理应具备：内存分配、地址映射、内存保护、共享和内存扩充等。
文件管理

包括文件的存储空间管理、目录管理和文件读写管理、文件保护。
设备管理

完成用户的IO请求，主要包括混充管理、设备分配、设备处理和虚拟设备等。

为了方便用户使用操作系统，操作系统还提供了用户接口，分为以下两类。

命令接口

使用命令接口进行作业控制的主要方式有两种：联机命令接口和脱机命令接口。
程序接口

程序接口由一组系统调用命令组成，用户可以直接使用命令向系统提出各种请求。

操作系统的结构

简单结构、模块化结构、分层式结构、微内核结构。

1.3 操作系统的运行环境

操作系统在具体实现上划分了用户态、核心态。

操作系统内核包括以下4方面：

时钟管理

操作系统需要通过时钟管理，向用户提供标准的系统时间。通过时钟中断的管理，可以实现进程切换。
中断机制

引入中断机制是为了提高多道程序运行环境中CPU的利用率。
原语

原语处于操作系统最底层，是最接近硬件的部分；具有原子性（一气呵成，不可中断）；运行时间短、调用频繁。
系统控制的数据结构及处理

常见的基本操作有以下3种，进程管理、存储器管理、设备管理。

中断和异常

引入核心态和用户态之后，就需要考虑如何在这两种状态下切换。**中断是让操作系统内核夺回CPU使用权的唯一途径。**内核工作在核心态，应用程序工作在用户态，系统不允许用户使用核心态的功能，但是它们又必须使用。

中断（外中断）

中断信号来源于CPU外部，与当前执行的指令无关。比如说时钟中断和I/O中断请求，当输入输出任务完成时，向CPU发送中断信号，或时钟部件每隔50ms发送一个中断信号。
异常（内中断）

源于CPU执行指令内部，比如程序的非法操作。

一些由用户态转为核心态的例子：1）用户程序要求系统服务 2）发生一次中断 3）用户程序产生错误 4）用户程序企图执行特权指令

2. 第二章进程管理

2.1 进程与线程

进程控制块（PCB）描述进程的基本情况和运行状态，PCB是进程存在的唯一标志。

进程由PCB、程序段、数据段组成。

进程的特征

动态性(最基本的特性)、并发性、独立性、异步性、结构性。

独立性：能够独立运行、独立获得资源、独立接受调度的基本单位。

异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供进程同步机制来解决异步问题。

进程的组织

进程的组织方式分为链接方式、索引方式。

进程控制

进程控制相关原语：创建、终止、阻塞、唤醒、切换，用原语实现进程控制（一气呵成）。

创建进程的过程如下：

申请一个空白的PCB
分配资源和必要的空间
初始化PCB
将PCB插入就绪队列，等待被调度运行

终止进程的过程如下：

从PCB集合中找到终止进程的PCB
如果进程正在运行，剥夺CPU，将CPU分配给其他进程
终止其所有子进程
将该进程拥有的所有资源归还给父进程 / 操作系统
删除PCB

阻塞和唤醒进程的过程如下：

切换进程的过程如下：

将运行环境信息存入PCB
将PCB移入相应队列
选择另一个进程执行，并更新其PCB
根据PCB恢复新进程所需的运行环境

无论哪个进程控制原语，要做的无非3件事情：

更新PCB中信息
将PCB插入合适的队列
分配/回收资源

进程的状态与转换

注意区别就绪状态和等待状态：就绪状态是指进程仅缺少处理器，只要活得处理器资源就立即执行；而等待状态是指进程需要其他资源或等待某一事件，即使处理器空闲也不能运行。

如果有大量处于阻塞状态的进程，进程会占用物理内存空间，但是物理内存空间是有限的，所以要解决这样的问题引入了虚拟内存管理。

在虚拟内存管理中，通常会把阻塞状态的进程换出到硬盘，等到再次运行时再换入物理内存。

挂起状态还可以分为：

阻塞挂起状态：进程再外存，并等待着某个事件的出现。

就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行。

进程的通信

通信方法分为共享存储、消息传递、管道通信。

共享存储
消息传递

分为直接通信（直接告诉操作系统进程B的地址，让其发送）和间接通信（发送到信箱中，等待进程B接受）方式。
管道通信

像是循环队列一样，先进先出。

线程概念和多线程模型

引入线程是为了减小程序在并发执行时所付出的时空开销，比如：QQ应用程序打视频的同时要打字、传文件。

线程不拥有系统资源，同一进程的各线程间共享进程的资源，进程内的线程对其他进程不可见。

线程是独立调度的基本单位，进程是资源拥有的基本单位。

一对一模型

一个用户级线程映射到一个内核级线程，一个进程占用多个内核级线程。
多对一模型

多个用户级线程映射到一个内核级线程
多对多模型

n个用户级线程映射到m个内核级线程（n >= m）

2.2 调度

一个作业从开始到完成，需要经历三级调度：作业调度（高级调度）、内存调度（中级调度）、进程调度（低级调度）

什么时候会调度？

当前运行进程主动放弃处理机（进程完成/发生异常。主动请求阻塞）
当前运行进程被动放弃处理机（时间片用完/处理更紧急的事/更高优先级）

什么时候不能进行进程调度/切换？

在处理中断的过程中
进程在操作系统内核程序临界区中
在原子操作过程中

进程调度的方式

非剥夺调度方式（只允许进程主动放弃处理机）

只有运行进程阻塞或退出才触发调度程序工作。
剥夺调度方式（可以抢占处理机）

每个时钟中断或k个时钟中断会触发调度程序工作。

调度算法评价指标

CPU利用率 = 忙碌的时间 / 总时间

系统吞吐量 = 总共完成多少道作业 / 总共花了多少时间

周转时间 = 作业完成时间 - 作业提交时间 | 平均周转时间 = 各作业周转时间之和 / 作业数

带权周转时间 = 作业周转时间 / 作业实际运行时间（ >= 1）平均带权周转时间 = 各作业带权周转时间 / 作业数

等待时间 = 进程建立后等待被服务的时间之和

响应时间 = 提交请求到首次响应所用的时间

先来先服务FCFS（first-come first-served）

类似排队，按照先后顺序进行服务。不会导致饥饿。非抢占式。

优点：公平

缺点：对短作业不利

短作业优先SJF（shortest job first）

非抢占式，运行时间越短的越先被服务。

下图，p1先到达，其他作业还没有到达，所以先执行p1。7s执行结束后所有作业都已经到达，选择运行时间最短的执行。

最短剩余时间优先SRTN（shortest remaining time next）

抢占式的短作业优先算法SRTN

下图，p1先到达先执行，在2s之后p2到达，而p2运行时间比p1短，所以抢占处理机运行p2。运行了2s之后p3到达，p3的运行时间小于p2，所以运行p3。1s之后p3完成，p4刚好到达，此时p2运行时间最短，依次处理。

优点：最短平均等待时间（作业到达时间差不多的时候）

缺点：长作业不利，可能会导致饥饿（如果一直有短作业到来）

高响应比优先HRRN

在每次调度时计算各个作业的响应比，选择响应比最高的作业为其服务。非抢占式，不会导致饥饿。

p1进程先到达，运行p1直到完成。在7s时，p2到达时间2s已经等待了5s，p3等待3s，p4等待2s。响应比是（等待时间 + 运行时间）/ 运行时间。p3响应比最高，先运行p3，以此类推。

优点：综合了FCFS和SJF的优点。

等待时间相同时，要求服务时间短的优先（SJF 的优点）要求服务时间相同时，等待时间长的优先（FCFS 的优点）

以上3种调度算法适合于早期的批处理系统，对于用户来说无法区分任务的紧急程度。所以引出交互式系统调度算法。

时间片轮转调度算法（RR）

伴随着分时操作系统出现，按照各进程到达就绪队列的顺序，轮流让各进程执行一个时间片（如100ms），若进程没有在一个时间片内执行完，就会被剥夺处理机，将进程重新放到就绪队列的队尾重新排队。抢占式算法，由时钟装置发出时钟中断来通知CPU时间片已到。

如果时间片太大，使得每个进程都可以在一个时间片就能完成，就会退化成FCFS调度算法。

如果时间片太小，进程切换过于频繁，系统会花费大量时间切换进程，而实际执行的时间减少。

优点：公平、响应快

缺点：不区分紧急程度、切换进程会有开销

优先级调度算法

每个作业都有各自的优先级，调度时选择优先级最高的作业执行。会发生饥饿（不断有优先级更高的作业）。

下图是非抢占式的优先级调度算法，优先级相同时选择先到达的执行。

也有抢占式的优先级调度算法，当新作业到达时，如果优先级高于当前进程，则可以抢占处理机。

就绪队列未必只有一个，也有静态优先级和动态优先级（优先级可在过程中变化）。

多级反馈队列调度算法

其他算法的折中权衡，抢占式算法，会导致饥饿。

1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。

2.新进程到达时先进入第一级队列，按照FCFS原则等待被分配时间片。如果时间片用完，则进入下一级队列队尾。如果此时已经再最下级的队列，则重新放回该队列队尾。

3.只有第k级队列为空时，才会为k+1级队头的进程分配时间片。

下图中，p1先到达进入第1级队列中先执行，第1级队列时间片为1，之后p1时间片结束进入到第2级队列中，同时p2到达，运行p2后同样放入到第2级队列p1后面（队尾），执行时间片2s后p1还没执行完则放入第3级队列中，再执行第2级队列中的p2。在执行1s之后p3到达了，这个时候p3进入到第1级队列中，抢占了处理机。运行完p3后再运行，p2继续运行2个单位的时间片，最后执行p1。

优点：公平、新到达的进程很快得到响应（RR），短进程较少时间可以完成（SPF），避免用户作假（缩短进程时间）、可灵活调整各类进程的偏好程度（CPU密集型进程、I/O密集型进程）

多级队列调度算法

2.3 进程同步与互斥

进程同步与互斥概念

并发性带来了异步的问题，所以需要进程同步来解决。

进程互斥分为4个部分：进入区、临界区、退出区、剩余区。

空闲让进

临界区空闲时，可以允许一个进程进入临界区。
忙则等待

当进入临界区时，其他试图进临界区的进程必须等待。
有限等待

应该保证在有限时间内进入临界区，防止饥饿。
让权等待

当进程不能进入临界区时，应当立即释放处理机，避免进程忙等待。

进程互斥软件实现方法有单标志法、双标志先检查、双标志后检查、Peterson算法。

单标志法

两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，每个进程进入临界区的权限只能被另一个进程赋予。

缺点：违背了空闲让进原则

双标志先检查

设置布尔型数组flag[]，比如flag[0] = true代表0号进程想进入临界区。每个进程在进入临界区之前检查有没有别的进程想进入临界区，如果没有就将自己设置为true之后访问临界区。

缺点**：违反了忙则等待原则**（并发运行时，两个进程可能会同时进入临界区，因为检查和上锁的动作不是一气呵成，可能会发生进程调度）

双标志后检查

防止双标志先检查的缺点，所以先上锁，后检查。

缺点：违背了空闲让进和有限等待原则（当两个进程都想进入临界区，检查后都进不了临界区，会产生饥饿现象）

Peterson算法

如果双方都想进入临界区，那么就谦让。结合了双标志法和单标志法的思想。如果对方也谦让，判断是谁最后谦让。如果是最后谦让的进程，那么等待，优先权交给其他进程。

缺点：没有遵循让权等待原则（如果进不了临界区，也依然占用CPU资源）

进程互斥的硬件实现方法有中断屏蔽方法、TestAndSet（TS指令 / TSL指令）、Swap指令（XCHG指令）

中断屏蔽方法

和原语相似，利用开中断 / 关中断指令使得某个进程在访问临界区时，不允许发生进程切换，也就不可能发生两个同时访问临界区的情况。

缺点：只适合单处理机和操作系统内核进程

TS指令

用硬件实现，不允许被中断，只能一气呵成。

TS指令读取一个内存位置（通常是一个锁变量）的值，并将其设置为一个新的值（通常是true，表示锁已被占用）。
如果读取到的值是false（表示没有被上锁），则TS指令返回false，并将锁变量设置为true，表示当前进程或线程成功获得了锁。
如果读取到的值是true（表示锁已被占用），则TS指令返回true，表示当前进程或线程未能获得锁。

bool TestAndSet(bool *lock) {
    bool oldValue = *lock;
    *lock = true; // 占用锁
    return oldValue;
}

Swap指令

和TS一样用硬件实现，不允许被中断。

使用swap函数交换锁变量和临时变量，逻辑同TS指令一样。

缺点：不满足让权等待原则，暂时无法进入临界区的进程会占用CPU并循环执行TS指令，从而导致忙等。

TS指令和Swap指令区别：

操作对象不同：TS指令操作一个内存位置（锁变量），而Swap指令操作两个内存位置（锁变量和临时变量）。
实现机制不同：TS指令通过读取并设置锁变量的值来实现互斥，而Swap指令通过交换锁变量和临时变量的值来实现互斥。

互斥锁和自旋锁

互斥锁：一次只能一个线程拥有互斥锁，其他线程只有等待。互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒。

实际上互斥锁的一种可能的实现是先自旋一段时间，当自旋的时间超过阀值之后再将线程投入睡眠中，因此在并发运算中使用互斥锁（每次占用锁的时间很短）的效果可能不亚于使用自旋锁

自旋锁：如果进线程无法取得锁，进线程不会立刻放弃CPU时间片，而是一直循环尝试获取锁，直到获取为止。如果别的线程长时期占有锁，那么自旋就是在浪费CPU做无用功，但是自旋锁一般应用于加锁时间很短的场景，这个时候效率比较高。

优点：等待并不是一直占用处理机，等时间片用完也会下处理机。如果上锁时间短，等待代价低，不用切换进程上下文，其他核会正常工作。

信号量机制

dijsktra提出，信号量就是一个变量，可以用一个信号量来表示系统中某种资源的数量，比如系统中只有一台打印机，就可以设置一个初值为1的信号量。

一对原语：wait(S)和signal(S)，简称为P、V操作。

P操作（wait）：对信号量减1，Svalue –。如果信号量值小于0，则进程阻塞。

V操作（signal）：对信号量加1，Svalue ++。如果有阻塞的进程，则唤醒一个。

整型信号量

缺点：忙等，不满足让权等待原则。

记录型信号量

为了改进整型信号量的忙等缺点，引入记录型信号量。要能够自己判断什么条件下需要执行block / wakeup。

Eg：有两台打印机，初始时S.value = 2，有p1,p2,p3,p4进程，S.value = 0时资源恰好分配完，当S.value = -2时表示有2个进程正在等待。如果S.value在++之后仍然<0说明有进程还在等待资源，于是在signal中唤醒处于等待队列的队头进程。

信号量机制实现进程互斥

规划临界区
设置互斥信号量mutex，初值为1
临界区之前对信号量执行P操作
临界区之后对信号量执行V操作

信号量机制实现进程同步

设置同步信号量S，初始为0
在“前操作”之后执行V(S)
在“后操作”之前执行P(S)

用信号量实现前驱关系

生产者消费者问题

缓冲区没满 → 生产者生产

缓冲区没空 → 消费者消费

full表示产品数量

empty表示空闲缓冲区数量

每生产一个产品后empty –，full ++；每消耗一个产品后full –，empty ++；

QA：能否改变相邻P、V操作的顺序？

不能，因为假如生产者执行p(mutex)变为0，再执行p(empty)，由于已经没有空闲缓冲区，所以阻塞，因此切换回消费者进程，执行p(mutex)，由于mutex = 0，所以消费者也被阻塞，出现死锁状态。

所以实现互斥的P操作一定要在实现同步的P操作之后。V操作不会导致阻塞，所以V操作顺序可以互换。

多生产者-多消费者问题

设想一家四口，父亲和母亲分别向盘子里放苹果和橘子，而女儿和儿子分别会吃苹果和橘子，一个盘子只能放一个水果，只有盘子中有水果时才可以拿来吃。

父母放水果的时候，盘子资源减少，水果资源增加。儿女吃水果的时候，盘子资源增加，水果资源减少。

吸烟者问题

假设有3个抽烟者和1个供应者，每个抽烟者都需要3种材料：烟草、纸和胶水。第一个抽烟者拥有烟草、第二个拥有纸、第三个拥有胶水。供应者无限地提供这三种材料，每次将其中2种材料放到桌子上提供给缺少这两种材料的抽烟者，这样的过程一直重复。

设置一个整型变量i实现轮流让吸烟者吸烟。

读者-写者问题

有读者和写者两组并发进程，当两个以上的读进程同时访问共享数据时不会产生副作用。但是当写进程和其他进程同时访问共享数据时，会发生数据不一致的错误。因此要求如下：

允许多个读者同时读
只允许1个写者往里写
在写者写的时候不允许其他读者 / 写者工作
写者写之前，应该让已有的读者 / 写者全部退出

哲学家进餐问题

与之前问题的区别是每个哲学家需要有2个临界资源才可以开始吃饭，而且容易发生死锁。

下图中，当0号哲学家拿了两双筷子后吃饭，1号哲学家由于mutex已经被0号释放，所以继续执行下面代码，但是在P(chopsstick[i])他想拿起左筷子的时候阻塞。从而2号哲学家因为mutex=0而也被阻塞。

如果想避免哲学家进餐的死锁问题有如下方案：

进行限制，如：最多允许4个哲学家同时进餐，这样可以保证至少有一个可以拿到2双筷子。
奇数号哲学家拿左边筷子，偶数号拿起右边筷子，这样可以保证相邻两个哲学家如果其中一个拿起筷子，另一个会被阻塞。

管程

信号量机制存在的问题：编写程序困难、易出错。所以引入管程。目的：更方便地实现进程互斥和同步。

编译器负责实现各进程互斥地进入管程中的过程。

管程实际上是定义的一种数据结构和控制进程的一些操作的集合。

2.4 死锁

定义：在并发环境下，各进程因竟争自由而造成的一种互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

死锁发生的4个必要条件：

互斥条件：必须互斥使用的资源的争抢才会导致死锁。
不剥夺条件：进程所获得资源在使用完之前，不能由其他进程强行夺走，只能主动释放。
请求和保持条件：已经保持了至少一个资源，但又提出了新的资源请求，而该资源被其他进程占有，请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

怎么避免死锁？

破坏死锁产生的4个必要条件。

破坏互斥条件：把互斥使用的资源改造为允许共享使用，采用SPOOLing技术。

破坏不剥夺条件：1. 当请求的新资源得不到满足时，必须立即释放保持的所有资源，以后需要再重新申请。

2. 将想要的资源强行剥夺，一般需要剥夺给优先级更高的进程使用。

破坏请求和保持条件：采用静态分配方法，即在进程运行前一次性申请完它所需要的全部资源。

破坏循环等待条件：采用顺序资源分配法，给系统中资源编号，规定每个进程必须按编号递增的顺序请求资源，小编号等待大编号。
防止系统进入不安全状态（如：银行家算法）。

银行家算法（Dijkstra）核心思想：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态（可能会发生死锁），以此来决定是否答应新资源的分配请求。
1. 检查此次申请是否超过了之前声明的最大需求数
2. 检查此时系统剩余的可用资源是否还能满足这次请求
3. 试探着分配更改各数据结构
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态
允许死锁的发生，但操作系统需要负责检测死锁的发生，然后解除死锁。

两种节点：进程结点、资源结点

两条边：进程结点一>资源结点、资源结点一>进程结点

图中p1进程可以像R2拿走一个空闲资源，并完成该进程后归还R1的资源，使P2能够成功申请，于是所有边会消去，则称该图可完全简化。而不可完全简化的，会发生死锁。

解除死锁的方法：
- 资源剥夺法：挂起（暂时放在外存上）某些死锁进程，并抢占它的资源。但应该防止挂起进程饥饿。
- 撤销进程法：强制撤销死锁进程，剥夺这些进程的资源。缺点：代价大，功亏一篑。
- 进程回退法：设置还原点，让死锁进程回退。

3. 第三章内存管理

3.1 内存管理基础

内存管理的概念

内存管理的功能有：内存空间的分配与回收、地址转换（逻辑地址→物理地址）、内存空间的扩充、存储保护。

如何将指令中的逻辑地址转化为物理地址？

三种装入方式

绝对装入

知道装入模块从内存的什么时候开始装，适用于单道程序环境。编译时确定物理地址，装入时已经将地址转成物理地址。
可重定位装入（静态重定位）

装入时加上起始物理地址。必须分配其要求的全部内存空间，如果没有足够内存就不能装入作业，运行期间不用再移动，也不能再申请内存空间。
动态运行时装入（动态重定位）

动态运行时装入，编译链接后的装入模块都是从0开始，装入内存后并不会立即把逻辑地址转换成物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。需要重定位寄存器。

特点：可以将程序分配到不连续的存储区，运行时动态申请内存。

三种链接方式

操作系统在对内存进行管理时都管理些什么？

1.内存空间分配与回收 2.对内存空间进行扩充 3.地址转换 4.内存保护（上下限寄存器 / 重定位寄存器、界地址寄存器）

覆盖与交换

覆盖技术

用来解决程序大小超过物理内存总和的问题，将程序分为多个段，常用的段放在固定区，不常用的段放在覆盖区里，需要时再调用。

交换技术

PCB会常驻内存，不会被换出外存。

内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中已具备运行条件的进程换入内存。

什么时候会内存交换？

比如在发现进程运行时经常发生缺页，说明内存紧张，可以换出一些进程，如果缺页率下降，就可以暂停换出。

交换技术主要是在不同进程之间进行，而覆盖则用于同一个程序中。由于覆盖技术要求给程序段之间的覆盖结构，使得其对用户和程序员不透明，所以对于主存无法存放用户程序的矛盾，现在操作系统是通过虚拟内存技术来解决的，覆盖技术则已成为历史；而交换技术在现代操作系统中仍具有较强的生命力。

连续分配管理方式

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上。

外部碎片：内存中的某些空闲分区由于太小而难以利用。

单一连续分配

内存分为系统区和用户区，有内部碎片没有外部碎片。

固定分区分配

分区大小相等 / 分区大小不等

建立分区说明表，每个表项包括对应分区的大小、起始地址、状态。无外部碎片，会产生内部碎片，如果程序太大所有分区都无法满足需求，不得不使用覆盖技术，所以会降低性能。
动态分区分配
- 空闲分区表
- 空闲分区链
没有内部碎片但是有外部碎片，可通过紧凑技术来解决外部碎片，就是操作系统不时地对进程进行移动和整理，像是windows系统中地磁盘整理程序。

动态分区分配算法

首次适应算法

空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。综合看性能最好。

缺点：每次查找要经过小的空闲分区，增大了查找的开销。

最佳适应算法

空闲分区按容量递增次序链接（尽可能多地留下大空间，优先使用小空间），每次分配内存时顺序查找到第一个大小满足要求的空闲分区。

缺点：每次选择最小分区进行分配，会留下越来越多小的、难以利用的内存块，因此会产生很多外部碎片。

最坏适应算法

为了解决最佳适应算法的问题–留下太多小外部碎片，按容量递减次序链接。

缺点：大分区被迅速用完导致大进程到达无处安放。

邻近适应算法

解决了首次适应算法的缺陷（查找开销大），每次查找从上次查找结束的位置开始检索。

缺点：如果低地址有更小的分区可以被满足，就可以保留高地址的大分区。而邻近适应算法会同样概率地使用到高地址大分区，导致大进程无处安放，实际上比首次适应算法还要差。

基本分页存储管理

非连续分配方式允许一个程序分散的装入不相邻的内存分区中，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。

分页存储管理方式中，又根据运行作业时是否要把作业所有页面都装入内存中才能运行分为基本分页存储管理和请求分页存储管理

由于固定分区会产生内部碎片，动态分区会产生外部碎片，两种技术对内存的利用率都低。我们希望尽量避免碎片地产生所以引出分页思想。

什么是分页存储？

将内存空间分为一个个大小相等的分区，每个分区就是一个页框（页帧、内存卡、物理块、物理页面），每个页框有编号（页框号），从0开始。

将进程的逻辑地址空间也分成跟页框大小相等的多个部分，每个部分称为一个页 / 页面。每个页面也有编号（页号）。

为了知道进程里的每个页面在内存中的位置，操作系统要给每个进程建立一张页表，通常存储在PCB中

虽然进程的各个页面是离散存放的，但是页面内部是连续存放的。

逻辑地址A对应的物理地址 = P号页面在内存中的起始地址+页内偏移量W

页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的起始地址和页表长度放在PCB中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

快表

快表（联想寄存器）TLB，是一种访问速度比内存块很多的高速缓存，用来存放最近访问的页表项的副本。与此对应，内存中的页表常称为慢表。

首先会进行越界异常的判断，发现没有越界，然后进入到快表查询，由于第一次上处理器，所以快表中没有信息，所以去慢表中查找，将最近使用过的页表项复制一份到快表中。下次查找时可以加快地址变换，直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元。（一次访存）。如果快表没有命中，则访问某个逻辑地址需要两次访存（1查页表2查内存单元）。如果快表已满，则需要按照算法对旧的页表项进行替换。

一般快表的命中率可以达到90%，这样，分页带来的速度损失就降到10%。快表的有效性是基于著名的局部性原理。

局部性原理：

时间局部性

如果执行了某条指令，不久后这条指令很可能会再次执行。（循环）
空间局部性

一旦程序访问了某个存储单元，不久之后，附近的存储单元也很有可能被访问。（很多数据在内存中连续存放）

TLB和普通Cache区别——TLB只有页表项的副本，普通Cache中可能有其他各种数据的副本。

单级页表存在两个问题

必须连续存放，当页表很大时需要占用很多个连续的页框。

没必要让整个页表常驻内存，因为进程一段时间内可能只需要访问某几个特定页面。

为了解决第一个问题所以引出两级页表

第二个问题，如果想访问的页面不在内存中，则会产生缺页中断（内中断），然后将目标页面从外存调入内存。

两级页表的访存次数为3次

第一次：访问内存中的页目录表

第二次：访问内存中的二级页表

第三次：访问目标内存单元

基本分段存储管理

按照程序自身的逻辑关系划分为若干个段，每个段都有段名在内存中占据连续空间。

段号的位数决定了每个进程最多可以分为几个段，段内地址位数决定每个段的最大长度是多少。

假如有逻辑地址A为（2，1024），首先判断段号是否越界，然后查询对应的段表项，检查段内地址是否超过段长（分页存储不会判断页内偏移量是否越界），如果超过则产生越界中断，否则继续执行

分页和分段的区别

页是信息的物理单位，分页的主要目的是为了实现离散分配，提高内存率，是系统行为对用户不可见。

段是信息的逻辑单位，分段对用户是可见的，用户编程时需要显式地给出段名。

分段比分页更容易实现信息的共享和保护，因为页面不是按照逻辑模块划分的。

分页的用户进程地址空间是一维的，分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名也要给出段内地址。

不能被修改的代码称为纯代码或可重入代码（不属于临界资源）才可以被共享。

段页式管理

由于分段会产生外部碎片，而分页可能有少量内部碎片并且不利于共享，结合了两者的优点，分段+分页=段页式管理。

一个进程在分段后，每一段分页。每个段对应一个段表项，由段号、页表长度、页表存放块号（页表起始地址）组成，段页式管理的地址结构是二维的。

需要3次访存，第一次访问段表，第二次访问页表，第三次访问目标内存单元。

3.2 虚拟内存

传统存储管理分为连续分配（单一连续分配、固定分区分配、动态分区分配）和非连续分配（基本分页存储、基本分段存储、基本段页式存储），它们的缺点是：

一次性：作业必须一次性全部装入内存后才可以允许。当一个游戏上百个G，就无法运行了。或者无法运行大量作业，导致多道程序并发度下降。

驻留性：一旦作业被装入内存中，就会一直驻留在内存中直到作业结束，浪费了宝贵的内存资源。

虚拟内存的定义

基于局部性原理，将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存。

当访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存。

如果内存空间不够，由操作系统负责将内存中暂时用不到的信息换出外存。

特征

多次性：无需把作业一次性全部装入内存中，允许被分成多次调入内存。

对换性：在作业运行时无需一直常驻内存，允许换入、换出。

虚拟性：逻辑上扩充内存的容量，使用户看到的内存容量远大于实际容量。

虚拟内存的实现需要建立在离散分配的内存管理方式基础上，操作系统要提供请求调页功能和页面置换功能。

请求分页管理方式

页表机制不同于基本分页系统，请求分页系统在一作业运行之前不要求全部一次性调入内存，因此在作业的运行过程中，必然会出现要访问的页不在内存的情况，如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此，在请求页表项中增加了四个字段：状态位P、访问字段A、修改位M、外存地址。

增加的四个字段说明如下：

状态位P：是否已调入内存。

访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考。

修改位M：表示该页在调入内存后是否被修改过。

外存地址：用于指出该也在外存上的地址，通常是物理块号，供调入该页时参考。

缺页中断机构

当访问的页面不在内存时，就产生一个缺页中断（内中断），然后由操作系统的缺页中断处理程序处理中断。

缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块；如果没有，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。

地址变换过程

CPU检索快表，

如果在快表中则修改访问位和修改位，形成物理地址。
如果不在快表中
- 页在内存中，则访问页表，修改快表、修改访问位和修改位，形成物理地址。
- 页不在内存中，则产生缺页中断请求调页，保留CPU现场，从外存中找到缺页
  - 如果内存没有满，则换入内存修改页表
  - 如果内存满了，则选择一页换出，如果换出该页被修改过则将该页写回外存，换入内存修改页表。

页面置换算法

由于页面的换入换出需要磁盘I/O，会有较大的开销，所以好的页面置换算法应该追求更少的缺页率。

最佳置换算法（OPT）

每次选择淘汰的页面将是以后永不使用 / 在最长时间内不再被访问的页面。

比如下图中访问4号页面时，由于访问4号之后会访问2，3，0。0号页面是最后一次访问，所以要替换0变为4。

缺点：操作系统无法提前预判页面访问序列，所以理想的最佳置换算法是无法实现的。

先进先出置换算法（FIFO）

每次选择淘汰的页面是最早进入内存的页面。

为进程分配的物理块增大时，缺页次数不减反增。——Belady异常（只有FIFO会产生Belady异常）

缺点：算法性能差，因为先进入的页面可能最常被访问。

最近最久未使用置换算法（LRU）

least recently used，每次淘汰的是最近最久未使用的页面，页表项中记录该页面自上次被访问以来所经历的时间t。

比如图中当访问3号页面时，内存块满了，于是往前查找最近最久未使用的页面：8，1，2，7，则是7被替换掉。

缺点：需要专门的硬件支持，算法开销大。

时钟置换算法（CLOCK）

CLOCK算法是一种性能和开销都均衡的算法。为每个页面设置一个访问位，如果是1则表示最近访问过，如果是0则表示最近没访问过。将内存中的页面都通过链接指针链接成一个循环队列，被扫描过的页面从1变0，如果扫到0则该页换出，最多经过两轮扫描。

改进型的时钟置换算法

由于简单的时钟置换算法只考虑到一个页面有没有最近被访问过。优先替换未被修改过的页面主要是为了减少I / O操作，提高效率，如果一个页面被修改，在替换前必须先写回磁盘，以保证数据不会丢失。

修改位为0的时候表示没有被修改过，修改位为1的时候表示被修改过。比如（1，1）表示最近被访问过且被修改过。最多进行4次扫描。

第一轮扫描（最近没访问且没修改）：不修改任何标志位，如果找到（0，0）则替换

第二轮扫描（最近没访问但修改过）：扫描过的访问位设置为0，如果找到（0，1）则替换

第三轮扫描（最近访问过但没修改过）：不修改任何标志位，如果找到（0，0）则替换

第四轮扫描（最近访问过并且修改过）：如果找到（0，1）则替换

页面分配策略

驻留集：请求分页存储管理中给进程分配的物理块的集合。

固定分配：为每个进程分配一组固定数目的物理块，在运行期间不再改变，即驻留集大小不变。

可变分配：先为每个进程分配一定数目的物理块，在运行期间适当调整，即驻留集大小可变。

局部置换：发生缺页时只能选进程自己的物理块进行置换。

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

	局部置换	全局置换
固定分配	√	×
可变分配	√	√

可变分配全局置换：只要缺页就分配新物理块

可变分配局部置换：要根据发生缺页的频率来动态地增加 / 减少进程的物理块

何时调入页面？

1）预调页策略。运行前 根据局部性原理，一次调入若干个相邻的页可能比一次调入一页更高效。但如果调入的一批页面中大厦多数都未被访问，则又是低效的。所以就需要采用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存。但目前预调页的成功率仅约50%。这种策略主要用于进程的首次调入时，程序员指出应该先调入哪些页。

2）请求调页策略。运行时 进程在运行中需要访问的页面不在内存而提出的请求，由系统将所需页面调入内存。这种策略调入的页一定会被访问，且这种策略比较易于实现，故在目前的虚拟存储器中大多采用此策略。它的缺点在于每次调入一页，会花费过多的IO开销。

何处调入页面？

外存（磁盘）分为对换区（连续分配，读写速度快）和文件区（离散分配，读写速度慢）

如果对换区空间足够，就都放在对换区；如果系统缺少足够的对换区，凡是不会被修改的数据都直接从文件区调入，修改过的数据从对换区换入换出。

UNIX方式：与进程有关的文件都存放在文件区，故未运行过的页面都应从文件区调入。曾经运行过的但有被换出的页面，由于是被放在对换区，因此下次调入时应从对换区调入。

抖动（颠簸）现象

刚换出的页面马上又换入内存，刚换入的页面又马上换出外存。产生原因是：进程频繁访问的页面数目高于可用的物理块数。（分配给进程的物理块不够）

如何判断要分配多少物理块？

工作集：在某段时间间隔里，进程实际访问页面的集合。

驻留集大小不能小于工作集大小，否则会频繁缺页。

内存映射文件

传统文件I/O需要read()/write()系统调用，会涉及用户态到内核态的切换，开销大。

操作系统将磁盘文件的某个部分映射到进程的虚拟地址空间mmap()，进程可以像访问内存一样读写数据。

多个进程可以映射同一文件，方便共享。