计算机操作系统 - INDEX

63分钟阅读

进程管理

进程线程基础知识

什么是进程？计算机进行资源分配，调度的基本单位，每个进程都有自己的程序计数器（PC），运行这个进程的时候，通过PC指向要运行的内存块，以此运行一个进程 CPU如何执行进程的？并发/并行 并发就是CPU在某个瞬间，一个CPU核心依次运行多个进程，但执行得太快，导致有这些进程同步运行的错觉

并行就是CPU有多个核心，一个核心中只运行一个进程，并且同步运行

进程并发运行的时候，从一个进程切换到另一个进程之前，得记录下当前进程的状态信息，以便下次回到这个进程可以恢复执行

所以，进程有这运行－暂停－运行的活动规律

进程的状态 因此，在一个进程的活动期间具备三种基本状态： －运行状态：该进程占用着CPU －就绪状态：可运行，由于其他进程占用而暂停 －阻塞状态：该进程正在等待某一事件发生（I/O）而暂停运行，及时有这CPU控制权，也无法运行 另外两种基本状态： － 创建状态：进程正在被创建 － 结束状态：进程在系统当中消失

file-20250415121237040 有时候有大量的进程处于阻塞状态，此时大量占用内存是我们不希望看到的，因此，我们需要把这些阻塞进程从内存换出到外存当中，为了描述已经移动到外存的阻塞进程，我们专门给这种状态起一个名字 － 挂起状态

而挂起状态又分为两种状态： － 阻塞挂起状态：进程在外存，并等待某个事件发生 － 就绪挂起状态：进程在外存，但只要进入内存，就立刻运行 file-20250415121331193除了因内存不足而让进程在外存当中，还有一下原因： － 通过sleep让进程间歇性挂起，工作原理为设置定时器，到期唤醒进程 － 用户希望挂起一个程序

进程的结构

进程控制块（process control block PCB）这样的数据结构用来描述进程的

PCB是进程存在的唯一标识 PCB包含哪些信息呢？ － 进程标识符：唯一标识一个进程 － 用户标识符：标识用户 － 进程当前状态： － 进程优先级 － 资源分配清单 － CPU相关信息

那么PCB之间是用什么数据结构来进行组织的呢？链表 把具有相同状态的进程用链表链在一起，组成各种队列 所有处于就绪状态的进程链在一起：就绪队列 所有处于阻塞状态的进程链在一起：阻塞队列 file-20250415121355158 因为单核CPU只有一个运行指针，因此单核CPU在同一时间只能运行一个进程

进程的各个控制过程

创建、终止、阻塞、唤醒

创建进程

操作系统允许一个进程创建另一个进程，允许子进程继承父进程的所有资源

创建进程过程： － 申请空白PCB，并向PCB里面填入信息 － 为该进程分配计算机资源，例如内存空间 － 将PCB插入到就绪队列，等待被调度

终止进程

进程的三种终止方式： － 正常结束 － 异常结束 － 外界干预（kill掉）

子进程终止时，将继承的资源还给父进程 父进程终止时，该父进程的子进程变为孤儿进程，会被1号进程收养，由1号进程对他们完成状态收集工作

终止进程过程如下： － 寻找该进程的PCB － 如果处于执行状态，终止执行，并归还资源 － 如果有子进程，将子进程给1号进程管理 － 归还全部资源 － 将其从所在队列中删除PCB

阻塞进程

－ 找到阻塞进程标识号对应的PCB － 如果为运行状态，则保护现场，将状态变为阻塞状态，停止运行 － 将PCB插入到阻塞队列中

唤醒进程

－ 从阻塞队列中找掉对应的PCB － 将其从阻塞队列中移出，将状态变为就绪状态 － 将这个PCB插入就绪队列中，等待被调用

进程的上下文切换

什么叫做进程的上下文切换？ 由一个进程切换到另一个进程运行，就是进程的上下文切换

什么叫做CPU的上下文？ CPU寄存器，程序计数器PC等等CPU要运行所依赖的环境，称之为CPU的上下文

CPU的上下文切换就不难理解了，保存上一个任务的CPU上下文信息，跳转到新的CPU上下文，运行新任务

这里所说的任务，主要包含：进程，线程，和中端。根据任务的不同，可以把CPU上下文切换分为

  1. 进程上下文切换
  2. 线程上下文切换
  3. 中端上下文切换

进程上下文切换过程如下：

  • 保存前进程的上下文
  • 加载后进程的上下文
  • 执行后进程

常见进程上下文切换的场景：

  • 当某个进程的时间片消耗完，将当前进程从运行状态切换为就绪状态，内核从就绪队列中选择另一个进程运行
  • 资源不足时，这个进程被挂起，等待资源充足时再运行，此时运行其他进程
  • 有更高优先级的进程需要运行

线程

什么是线程？CPU调度的最小单位，一个进程可能包含多个线程，各个线程之间共享信息，资源，每个线程自己也有单独的私有变量 file-20250415163817413

缺点是当其中一个线程崩溃，其他线程也会崩溃

进程的比较

  • 进程是调度资源的最小单位，线程是CPU调度的最小单位
  • 进程拥有完整的资源，线程只有必不可少的资源，如寄存器和栈
  • 线程同样具有就绪阻塞运行三种基本状态，同样具有状态之间的转换关系
  • 相较于进程，线程能减少并发时间与空间

为什么能减少？

  • 线程占用资源少
  • 线程创建时间快（只需创建必要信息）
  • 线程销毁时间快（只需销毁必要信息）

线程的上下文切换

  • 当进程中只有一个线程时：此时可以理解为进程=线程，线程的上下文切换等于线程的上下文切换
  • 进程中有多个线程时：进程之内的上下文切换只会切换私有变量，共享的资源不会改变，当切换的是两两进程之间时，就相当于进程的上下文切换

线程的实现

线程的三种实现方式：

  • 用户线程：在用户空间实现的线程，不受内核管控，例如Java中的new Thead()方法
  • 内核线程：由内核掌控
  • 轻量级进程（lightweight process LWP）：介于线程与进程之间，是内核线程的高度抽象

三种线程该如何理解 这些线程之间的联系：

  • 用户线程通过轻量级线程与内核线程之间绑定，实现高并行
  • 每个LWP对应一个内核线程

为何用户线程不受内核管理？ 用户线程中的线程控制块（Thead Control BLock TCB）是基于用户态的管理库实现的，内核是看不到TCB，只能看到PCB。

为什么这样设计？

  • 每个进程需要有私有的线程控制块（TCB）列表，用于管理自己的线程状态信息。
  • 而且TCB由用户态线程库函数维护，可用于不支持线程的操作系统 file-20250422083613743

与之相对的内核线程，他的TCB是由内核进行管理调度的 file-20250422084227089 LWP是由内核支持的用户线程，一个进程对应一个或者多个LWP，一个LWP映射一个内核。 一般来说，一个进程代表一个程序实例，而LWP代表程序中的执行线程，而执行线程相比于普通的进程不需要很多状态信息，=＝只需要最小的执行上下文和统计信息＝＝。

LWP与用户线程的对应关系

  • 1:1
  • 1:N
  • N:M file-20250422085150691

调度

调度即选择某个进程运行（这里的进程为只有主线程的进程，调度的应该是线程，因为线程是CPU调度的最小单位）

调度时机：状态发生变化的时候，例如 就绪态→运行态 调度算法的基本类别：

  • 非抢占式调度算法：等待某个进程运行到阻塞或者退出才会调度另外一个进程，即没有时钟中断这一过程
  • 抢占式调度算法：如果某进程在该时段结束时还在运行，会挂起此进程，运行另外一个进程。即发生了时钟中断，时间片机制 调度原则：
  • CPU利用率要高
  • 系统吞吐量高
  • 周转，等待，响应时间少

调度算法

调度进程所涉及到的时间概念：

  • 到达时间：提交该进程的时间点

  • 开始时间：开始执行该线程的时间点

  • 等待时间：开始时间-到达时间

  • 服务时间：执行该进程所需要的时间

  • 完成时间：执行完该进程的时间点，即开始时间+服务时间

  • 周转时间：一个进程从提交到完成的时间，可以理解为：完成时间-到达时间。用于衡量批处理操作系统的性能，关注的是一个任务从头到尾的“全生命周期”有多长

  • 带权周转时间= 周转时间 / 服务时间

  • 响应时间：用户提交进程到第一次响应的时间段，可以理解为：开始时间-到达时间 调度时间概念轴

先说单核CPU的常见调度算法

先来先服务（First Come First Serve FCFS）算法

  • 非抢占式调度算法
  • 每次选择就绪队列的头部进程，让他运行直到退出或者阻塞，才会再选择一个头部进程运行
  • 不利于I/O繁忙型任务，适合FCFS长作业

最短作业优先调度算法

  • 优先运行时间片最小（服务时间最小）的进程，非抢占式。从当前已到达且就绪的进程中，选择服务时间最短的进程执行。
  • 对长作业任务不利

他可以最小化平均周转时间。因为它总是优先执行那些最快完成的任务，但对于长任务的响应时间就很长。

时间片轮转调度算法

  • 最古老，简单，公平，使用最广的算法
  • 每个进程配分配到一个时间片运行，时间片用完后会释放出来此进程，分配给另一个进程，如果在时间片用完之间进程运行完毕，直接进行切换

file-20250423084030641 选取一个时间片的值也很关键，太高太低会降低CPU效率。一般设为20－50ms

他能有效最小化响应时间，但平均周转时间可能会拉长

以下算法是这三种的改进算法

最短剩余时间调度算法

  • 是对最短作业优先的改进，增加了抢占策略
  • 根据剩余时间来选择最短剩余时间的进程。
  • 增加了抢占策略，当有优先级高的会抢占当前执行资源

最高响应比优先调度算法

主要用于权衡短作业与长作业

  • 每次调度进程时，先计算【响应比优先级】数值最高的进程投入运行 file-20250423083248741
  • 等待时间是可以计算的，而要求服务时间是无法计算的，因此这个算法为理想算法，现实中是实现不了的

最高优先级调度算法

有两种方式将每个进程设置了优先级

  • 静态优先级：进程创建时就设置好了优先级
  • 动态优先级：随着进程的动态变化调整优先级，例如随着等待时间增加，优先级也会增加

也有两种调度方式执行算法

  • 抢占式：就绪队列中出现优先级比他高的，挂起此进程，选择优先级高的进程
  • 非抢占式：运行完当前线程再从就绪队列中选择优先级高的进程运行

多级反馈队列调度算法

他是时间片轮转算法与最高优先级算法的综合

进程间的通讯方式

管道

Linux的命令中，|是一个管道，作用是将前一个的输出，作为后一个的输入

$ ps auxf | grep mysql

但这里的通信是单向的。且这个管道没有名字，因此叫做匿名管道，有名的叫做命名管道

所谓管道，就是内核中的一段缓存，写入与读取都是在内核中的内存中进行的，另外管道的输入输出是无格式的流且大小受限制

Pasted image 20250607085515

创建管道的时候会返回两个描述符 读取端fd[0] 写入段fd[1]

使用fork创建子进程，创建的子进程会复制父进程的文件描述符，这样就做到了两个进程各 有两个「fd[0]与fd[1]」，因为两个进程都有读写段，为了避免混乱，我们关闭一段的读取，关闭另一段的写入

Pasted image 20250607085846

但这里还只是单向通信，也就是管道的实现过程，但在shell实际情况不是这样的。 在 shell 里面执行 A | B 命令的时候，A 进程和 B 进程都是 shell 创建出来的子进程，A 和 B 之间不存在父子关系，它俩的父进程都是 shell。

Pasted image 20250607090349 我们可以得知， 对于匿名管道，它的通信范围是存在父子关系的进程 。因为管道没有实体，也就是没有管道文件，只能通过 fork 来复制父进程 fd 文件描述符，来达到通信的目的。

另外， 对于命名管道，它可以在不相关的进程间也能相互通信 。因为命令管道，提前创建了一个类型为管道的设备文件，在进程里只要使用这个设备文件，就可以相互通信。

消息队列

消息队列就是将通信的内容发送到内核的消息链表当中，需要这些消息的时候就去链表里拿就行了

但消息链表也存在通信不及时，附件大小有限制等问题

内存共享

将两个进程之间不同的虚拟内存地址映射到相同的物理内存地址，就可以不需要拷贝到各自的内存当中，直接在这个相同的物理内存间通信了

Pasted image 20250607091637

信号量

在使用共享内存的过程中会有一个问题：当两个进程同时修改某一个数据的时候，会发生冲突，为了解决使用共享内存中进程间发生冲突的问题，会引入一个保护机制，这个保护机制就是信号量

信号量其实是一个整型的计数器，表示资源的数量，通过计时器的状态，来实现进程间的互斥与同步 。

控制信号量有两个原子操作：

  • P操作：信号量-1，if(信号量<0) 表示资源占用，进程需阻塞等待 else (信号量>=0) 表示有资源可使用，进程正常执行
  • V操作：信号量+1，if(信号量⇐0) 表示有阻塞进程，于是会唤醒阻塞进程，else (信号量>0) 则表明当前没有阻塞中的进程

P 操作是用在进入共享资源之前，V 操作是用在离开共享资源之后，这两个操作是必须成对出现的。 Pasted image 20250607092625

具体的过程如下：

  • 进程 A 在访问共享内存前，先执行了 P 操作，由于信号量的初始值为 1，故在进程 A 执行 P 操作后信号量变为 0，表示共享资源可用，于是进程 A 就可以访问共享内存。
  • 若此时，进程 B 也想访问共享内存，执行了 P 操作，结果信号量变为了 -1，这就意味着临界资源已被占用，因此进程 B 被阻塞。
  • 直到进程 A 访问完共享内存，才会执行 V 操作，使得信号量恢复为 0，接着就会唤醒阻塞中的线程 B，使得进程 B 可以访问共享内存，最后完成共享内存的访问后，执行 V 操作，使信号量恢复到初始值 1。

可以发现，信号初始化为 1 ，就代表着是 互斥信号量 ，它可以保证共享内存在任何时刻只有一个进程在访问，这就很好的保护了共享内存。

但这样进程之间的执行顺序是随机的，有时候我们希望有些进程之间是相互依赖，顺序进行的，这时候就可以把初始信号量设为0 Pasted image 20250607092846

具体过程：

  • 如果进程 B 比进程 A 先执行了，那么执行到 P 操作时，由于信号量初始值为 0，故信号量会变为 -1，表示进程 A 还没生产数据，于是进程 B 就阻塞等待；
  • 接着，当进程 A 生产完数据后，执行了 V 操作，就会使得信号量变为 0，于是就会唤醒阻塞在 P 操作的进程 B；
  • 最后，进程 B 被唤醒后，意味着进程 A 已经生产了数据，于是进程 B 就可以正常读取数据了

可以发现，信号初始化为 0 ，就代表着是 同步信号量 ，它可以保证进程 A 应在进程 B 之前执行。

信号

这里的信号和信号量是完全不同的概念 信号量是用于解决进程间共享内存的冲突问题的一个保护机制

信号是进程间唯一的异步通信方式，例如Ctrl+C 产生 SIGINT 信号，终止该进程

用户进程收到信号后有以下三种处理方式

  • 执行默认操作：Linux对每种信号都规定了默认的执行操作，收到信号直接执行
  • 捕捉信号：为某个信号编写一个信号处理函数，一旦信号发生，就执行这个函数
  • 忽略信号：当我们不希望处理某些信号，可以进行忽略，但SIGKILL 和 SEGSTOP是无法被忽略的，它们用于在任何时候中断或结束某一进程。

SOCKET

以上都是在同一台电脑上的进程之间进行通信，而socket不仅可以在同一台主机之间的进程间通信，还可以在不同主机的进程间通信

Socket是操作系统提供给应用程序（进程）的一套接口（API），通过调用socket相关的函数（例如 socket(), bind(), listen(), connect(), accept(), send(), recv(), close() 等），来使用TCP IP模型进行网络通信。没有这套API，进程是无法进行网络通信的，也就无法在不同的主机间进行通信

值得注意的是，Socket与端口号是完全不同的两个概念，端口号用于在TCP IP模型的传输层中，用于标识主机特定的进程，而Socket是一套API，需要通信的数据会通过这套API来传递给传输层，以此进行网络通信

在传输层的不同协议中，Socket会调用不同的API来进行不同主机进程间的通信

同一主机不同进程之间 实现本地进程间通信： 「本地字节流 socket 」类型是 AF_LOCAL 和 SOCK_STREAM，「本地数据报 socket 」类型是 AF_LOCAL 和 SOCK_DGRAM。

在TCP协议中 Pasted image 20250607102056

需要注意的是：监听的 socket 和真正用来传送数据的 socket，是「 两个 」 socket，一个叫作 监听 socket ，一个叫作 已完成连接 socket

对于UDP协议 Pasted image 20250607102249

多线程冲突问题

竞争与协作

因为线程是可以在同一个进程之间共享资源的，比如代码段、堆空间、数据段，当多个线程同时进行时，就会涉及到资源的竞争问题，会导致共享资源的混乱，就跟上面多个进程之间共享资源时，遇到的问题是一样的。

互斥 当多线程相互竞争共享变量的时候，就称之为竞争，我们希望多个线程操作共享变量的时候，只有一个线程在操作，其他线程不能操作，这样的线程就是互斥的，我们可以在可能互斥的代码中添加临界区的概念，即它是访问共享资源的代码片段，一定不能给多线程同时执行

同步

有时候我们希望某些线程是顺序执行，相互依赖的，让多个线程密切合作，以实现共同的任务 所谓同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步

同步机制遵循的四个规则:

  • 空闲让进: 当没有进程处于临界区时，任何有权进入临界区的进程都应被允许立即进入。
  • 忙则等待: 当已有进程进入其临界区时，其他试图进入临界区的进程必须等待。
  • 有限等待: 对任何一个希望进入临界区的进程，它等待的时间必须是有限的，不能被无限延迟（防止“饥饿”）。
  • 让权等待: 当进程不能进入其临界区时，应立即释放处理器，防止进程陷入“忙等”状态。

互斥与同步的实现

为了实现进程/线程间正确的协作，主要提供了两种方法来实现

  • 锁 ：加锁、解锁操作；
  • 信号量 ：P、V 操作；

锁

任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。这样可以实现线程的互斥

Pasted image 20250607135503

根据锁的实现不同，可以分为「忙等待锁」和「无忙等待锁」。

信号量

这与进程里讲的信号量一样，执行P，V操作，通过查看互斥信号量，来决定是否执行该线程。

对于两个并发线程，互斥信号量的值仅取 1、0 和 -1 三个值，分别表示：

  • 如果互斥信号量为 1，表示没有线程进入临界区；

  • 如果互斥信号量为 0，表示有一个线程进入临界区；

  • 如果互斥信号量为 -1，表示一个线程进入临界区，另一个线程等待进入。

  • P 操作 ：将 sem 减 1 ，相减后，如果 sem < 0 ，表示没有可用的资源了，线程/进程会被阻塞，进程/线程进入等待队列，直到被V操作唤醒；

  • V 操作 ：将 sem 加 1 ，相加后，如果 sem <= 0 ，说明还有线程还在阻塞当中，唤醒等待中的队首进程/线程，让它从阻塞状态变为就绪状态，可以继续执行；

互斥的实现，就需要把sem的初始值为1，这样当一个线程进入临界区，执行P操作，sem=0，另外一个线程就不能进入临界区了

同步的实现，就是把sem的初始值设为0，需要先执行的线程，执行完毕后，执行V操作，sem1，此时另外一个线程就能执行了，这样实现了线程的同步执行（同步这个词还是有点混淆，感觉用顺序执行好些）

P、V操作原语 Pasted image 20250626084322

生产者/消费者问题

Pasted image 20250607142029生产者-消费者问题描述：

  • 生产者 在生成数据后，放在一个缓冲区中；
  • 消费者 从缓冲区取出数据处理；
  • 任何时刻， 只能有一个 生产者或消费者可以访问缓冲区；

我们需要三个信号量：

  • 互斥信号量mutex ,用于互斥访问缓冲区，初始化值为 1；
  • 满信号量fullBuffers 用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；
  • 空信号量emptyBuffers 用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）； Pasted image 20250607142629

哲学家就餐问题

读者-写者问题

死锁

死锁就是两个线程保护各自的资源而使用了互斥锁，但双方又在等待对方释放锁

死锁的四个条件：

  • 互斥条件：双方都要为各自使用的资源使用互斥锁
  • 持有并等待：持有自己的资源，等待其他的资源，等待过程当中又不会释放自己的资源
  • 不可剥夺：自己资源使用完前，是不能被其他线程所获取
  • 环路等待：线程之间等待资源的路径形成环路* Pasted image 20250608083806

避免死锁的发生

仅需要修改产生死锁的四个条件之一就能打破死锁了

最常见的方法是：打破环路等待，即资源有序分配法 仅需让产生死锁的这几个线程获取资源的顺序一样，就能避免死锁

Pasted image 20250608084917

这里AB都是以，21的顺序来获取资源，这时候就不满足死锁的环路等待条件，也就破解了死锁

银行家算法

银行家算法

互斥锁与自旋锁

互斥锁与自旋锁是所有锁中最基本的锁，因此单独需要将这两个单独拿出来讲解对比

互斥锁与自旋锁都是锁，有加锁和解锁两个基本方法，只是他们各自的实现不同

互斥锁

互斥锁在加锁解锁的过程当中，是有内核参与的，一旦加锁失败，会从用户态转换到内核态，在转换状态的过程当中会有开销：切换线程就需要把线程当中的私有的数据，寄存器等不同享的数据切换到内核态。直到锁释放，才能让等待的锁拿到CPU资源

Pasted image 20250608091936

  • 当线程加锁失败时，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程运行；
  • 接着，当锁被释放时，之前「睡眠」状态的线程会变为「就绪」状态，然后内核会在合适的时间，把 CPU 切换给该线程运行。

这时候如果线程的执行时间小于上下文切换开销的时间，那么就很尴尬了，因此互斥锁对于线程执行时间短的就不适合

自旋锁

如果你能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁。

自旋锁是通过 CPU 提供的 CAS 函数，在「用户态」完成加锁和解锁操作，不会主动产生线程上下文切换。因此会快些，开销小些

自选锁加锁失败的线程会「忙等待」，简单来说就是while循环，但一般用的是CPU的PAUSE指令，来实现「忙等待」

适合异步、协程等在用户态切换请求的编程方式

自旋锁与互斥锁使用层面比较相似，但实现层面上完全不同： 当加锁失败时，互斥锁用「线程切换」来应对，自旋锁则用「忙等待」来应对 。

乐观锁与悲观锁

前面说的互斥锁与自旋锁都属于悲观锁，之所以说悲观，因为这些锁都认定修改共享资源的概率比较高，想要修改资源必须得先加锁

但乐观锁就不同，他认为修改共享资源的概率比较低，就不会在修改资源的时候加锁，而是修改完成了过后才开始验证这段资源有没有发生资源冲突，如果没有，那么操作完成，如果有，就放弃本次操作。

乐观锁是怎么来验证修改资源有没有发生冲突呢？ git举例就是先让用户修改，在提交的时候查看当前的版本号，如果不一值就不会提交

因此乐观锁也叫做无锁编程，乐观锁虽然去除了加锁解锁的操作，但是一旦发生冲突，重试的成本非常高，所以 只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

内存系统

当CPU运行多个进程的时候，如果直接操作的物理内存地址，就很有可能发生一个进程的数据覆盖另外一个进程的情况，因此操作系统引入了虚拟内存地址这个概念，不同的进程分配不同的虚拟地址，而操作系统自动的把不同虚拟地址的内存映射到不同的物理地址上，这样能达成进程间内存互不干扰的目的。

于是，这里就引出了两种地址的概念：

  • 我们程序所使用的内存地址叫做 虚拟内存地址 （ Virtual Memory Address ）
  • 实际存在硬件里面的空间地址叫 物理内存地址 （ Physical Memory Address ）。

操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存，如下图所示：

Pasted image 20250626113138

虚拟、物理地址映射实现

操作系统为了实现这种映射，引入了一种非常重要的内存管理方式，叫做页式内存管理

在页式内存管理中，内存被分成固定大小的块：

  • 虚拟内存被分成一个个固定大小的块，叫做页（Page）。
  • 物理内存被分成一个个大小相同的块，叫做页帧（Page Frame）。

内存管理单元（MMU）通过管理这两种块的映射表：页表 来实现映射。

每个进程都有自己的一个页表，记录了它所有虚拟页到物理页帧的映射关系。页表的每一行都对应一个虚拟页，并记录了它在物理内存中的对应位置（页帧号）。

当你访问一个虚拟地址时，CPU 中的**内存管理单元（MMU）**就会做以下事情：

  1. 它会从虚拟地址中解析出页号和页内偏移。
  2. 它会根据页号去查询当前进程的页表，找到对应的页帧号。
  3. 它将页帧号与页内偏移组合起来，就得到了真实的物理地址。
  4. 最后，它用这个物理地址去访问物理内存。

虚拟内存可以比实际内存大得多

拥有了页式内存管理，操作系统就没必要一次性把所有数据都加载到内存里面，而是按需调页

  • 先把第一页调度到内存当中
  • 运行一段时间后访问一个不存在的物理页帧时，就会发生页面中断，即缺页

当发生缺页中断时，操作系统需要立即处理它：

  1. 暂停当前进程的运行。
  2. 检查缺页中断，确定是哪个虚拟页不在内存中。
  3. 从外存（比如硬盘）中找到这个虚拟页。
  4. 将它加载到物理内存中的一个空闲页帧。
  5. 更新进程的页表，记录新的映射关系。
  6. 恢复被暂停的进程，让它重新执行刚刚失败的指令。

但是，如果物理内存中的所有页帧都已经被占满了，那怎么办？

这时，为了给新来的页面腾出空间，操作系统就必须选择一个页帧中的旧页面，把它从物理内存中“踢”出去。

这个选择旧页面的过程，就是我们接下来要讨论的页面置换（Page Replacement）。

页面置换算法

页面置换算法的目标是：选择一个合适的页面被淘汰，以最大程度地减少未来的缺页次数。

缺页就是CPU尝试访问一个内存地址的时，发现此内存地址不存在与物理内存当中。

注：缺页次数=置换次数+页帧数，缺页率=缺页次数/访问序列长度。

最佳置换算法 (Optimal)

算法步骤

  1. 发生缺页中断时，检查内存（物理页框）是否有空闲位置。
    • 如果有，则将新页面直接装入空闲位置，无需置换。
    • 如果没有，则必须执行页面置换。
  2. 执行置换时，考察当前内存中所有已加载的页面。
    • 查看这些页面在未来的页面引用串中的出现情况。
    • 找到那个下一次被访问离当前时间点最远的页面。
    • 如果某个页面在未来再也不会被访问，那么它就是最佳的淘汰对象。
  3. 将找到的“最佳”页面置换出去，然后将新的页面装入它所空出的位置。

先进先出算法 (FIFO)

算法步骤

  1. 建立一个队列：用一个队列来管理当前在内存中的所有页面，队列的顺序代表了页面进入内存的先后次序。
  2. 发生缺页中断时：
    • 如果内存有空闲物理块，则将新页面装入，并将其加入到队列的尾部。
    • 如果内存已满，则必须执行页面置换。
  3. 执行置换时：
    • 将位于队列头部的页面（最老的页面）从内存中移出。
    • 将新页面装入被释放的物理块中，并将其加入到队列的尾部。

最近最久未使用算法 (LRU)

LRU算法的核心思想是：当发生缺页中断且内存已满时，优先置换掉那个在最近的历史中距离现在最久未被访问过的页面

要实现LRU，系统必须能够追踪每个页面最后一次被使用的时间。这通常通过以下两种方式实现：

  1. 计数器 (Counters)：为每个页表项关联一个时间戳（或计数器）。每次访问一个页面时，就将当前的系统时间或一个递增的逻辑时钟值更新到该页面的时间戳。当需要置换时，就遍历所有内存页，找到时间戳最小（即最老）的那个页面进行置换。这种方法开销较大。

  2. 栈 (Stack)：用一个栈结构来维护所有在内存中的页面。每当一个页面被访问（无论是命中还是缺页调入），就将它从当前位置移动到栈顶。这样，栈顶永远是最近被使用的页面，而栈底永远是最近最久未使用的页面。当需要置换时，只需简单地淘汰栈底的页面即可。这种方法在教学和模拟中最为常用。

时钟置换算法 (Clock)

时钟置换算法，又称为二次机会算法 (Second-Chance Algorithm)，其设计目标是为了在不引入巨大硬件开销的前提下，实现一个性能接近于LRU的页面置换算法

算法的核心思想是，给每一个在内存中的页面一次“额外的机会”。当需要置换页面时，我们不去淘汰一个最近刚刚被访问过的页面。如何判断“最近被访问过”呢？它并不像LRU那样记录精确的时间，而是使用一个更简单的标志——访问位 (Use Bit / Access Bit)。

  • 如果一个页面的访问位是1，说明它最近被用过，那么就给它一次机会，暂时不换出它。
  • 如果一个页面的访问位是0，说明它在最近一段时间内没有被使用过，那么它就成为一个合适的淘汰对象。

磁盘调度算法

磁盘调度算法的目的很简单，就是为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的。 假设有下面一个请求序列，每个数字代表磁道的位置：

98，183，37，122，14，124，65，67

先来先服务

先来先服务（ First-Come，First-Served，FCFS ），顾名思义，先到来的请求，先被服务。

那按照这个序列：

98，183，37，122，14，124，65，67

最短寻道时间优先

最短寻道时间优先（ Shortest Seek First，SSF ）算法的工作方式是，优先选择从当前磁头位置所需寻道时间最短的请求，还是以这个序列为例子：

98，183，37，122，14，124，65，67

那么，那么根据距离磁头（ 53 位置）最近的请求的算法，具体的请求则会是下列从左到右的顺序：

65，67，37，14，98，122，124，183

但这个算法可能存在某些请求的 饥饿 ，因为本次例子我们是静态的序列，看不出问题，假设是一个动态的请求，如果后续来的请求都是小于 183 磁道的，那么 183 磁道可能永远不会被响应，于是就产生了饥饿现象，这里 产生饥饿的原因是磁头在一小块区域来回移动

扫描算法

为了防止这个问题，可以规定： 磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（ Scan ）算法 。

这种算法也叫做电梯算法，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。

还是以这个序列为例子，磁头的初始位置是 53：

98，183，37，122，14，124，65，67

那么，假设扫描调度算先朝磁道号减少的方向移动，具体请求则会是下列从左到右的顺序：

37，14， 0 ，65，67，98，122，124，183

扫描调度算法性能较好，不会产生饥饿现象，但是存在这样的问题，中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异

循环扫描算法

扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的方向进行扫描，使得每个磁道的响应频率基本一致。

循环扫描（ Circular Scan, CSCAN ）规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且 返回中途不处理任何请求 ，该算法的特点，就是 磁道只响应一个方向上的请求 。

还是以这个序列为例子，磁头的初始位置是 53：

98，183，37，122，14，124，65，67

那么，假设循环扫描调度算先朝磁道增加的方向移动，具体请求会是下列从左到右的顺序：

65，67，98，122，124，183， 199 ， 0 ，14，37

磁头先响应了右边的请求，直到碰到了最右端的磁道 199，就立即回到磁盘的开始处（磁道 0），但这个返回的途中是不响应任何请求的，直到到达最开始的磁道后，才继续顺序响应右边的请求。

循环扫描算法相比于扫描算法，对于各个位置磁道响应频率相对比较平均。

文件系统

文件系统组成

文件呢系统的基本组成部分有：

  • 文件：对用户来说是一个独立的数据单元
  • 目录：操作系统使用目录来组织文件，形成一套树状结构，帮助管理和导航文件
  • 文件元数据：记录本文件的大小，权限，名称，创建/修改实现等
  • 文件系统接口：操作系统同一的API让用户可以与文件系统进行交互

不同的操作系统具体表现这些组成成分会有不同，但概念是相通的，就以linux为例：

  • 文件：存储实际数据的独立数据单元
  • 索引节点：记录文件在物理磁盘的位置，可以作为唯一标识符，还记录文件的元信息，例如大小，权限，创建/修改时间
  • 目录项：记录一个文件的多个文件名，索引节点的指针，还有与其他目录项的层级关系*

虚拟文件系统

文件系统的种类众多，而操作系统希望 对用户提供一个统一的接口 ，于是在用户层与文件系统层引入了中间层，这个中间层就称为 虚拟文件系统（ Virtual File System，VFS ）。

VFS 定义了一组所有文件系统都支持的数据结构和标准接口，这样程序员不需要了解文件系统的工作原理，只需要了解 VFS 提供的统一接口即可。

Pasted image 20250610091522

文件的逻辑结构

堆文件

堆是最简单的文件组织形式。数据按他们到达的顺序被采集，每个记录由一串数组组成。堆的目仅仅是积累大量的数据并保存，例如html文件

顺序文件

顺序文件是最常见的文件组织形式。在这类文件中，每个记录都使用固定的格式。所有记录都有同的长度，并且由相同数目、长度固定的域按照特定的顺序组成

顺序文件通常用于批处理应用中，并且如果这类应用涉及到对所有记录的处理，则采用顺序文件常是最佳的解决方案

索引顺序文件

通过增加文件索引和溢出文件的特性，克服了顺序文件的缺点，让文件既可以保留顺序结构，又可以进行快速查找定位

Pasted image 20250610094309

索引文件

索引文件扩展了索引的概念，这使得用户可以根据需求建立两种类型的索引。

  • 完全索引：索引包含对主文件中每条记录的索引项。为了便于搜索，索引本身往往被组织成顺序文件。
  • 部分索引：索引仅包含部分记录的索引项，或者只包含那些兴趣域的记录的索引项。对于长度可变的记录，的记录并不包含所有的域

直接或散列文件

  • 支持随机存取
  • 满足对文件动态增加和删除的要求
  • 不依赖索引，存取速度快
  • 无法对文件顺序存取，只能按照关键字存取
  • 文件多次增删以后，桶结构不合理
  • 溢出桶满而基桶内容空

文件物理结构

连续存放

根据文件中的「起始位置」和「长度」就能把这段文件的数据放在一段连续的物理磁盘空间当中，这些信息都能在文件的元数据当中找到。

Pasted image 20250610165943 连续空间存放的方式虽然读写效率高， 但是有「磁盘空间碎片」和「文件长度不易扩展」的缺陷。

非连续存放

解决连续存放的缺陷就需要让存放的数据以一种更灵活的方式存放，即可以不需要连续存放，为了实现不连续存放，我们可以采取链表或者索引的方式

我们先看看链表

链表的方式存放是 离散的，不用连续的 ，于是就可以 消除磁盘碎片 ，可大大提高磁盘空间的利用率，同时 文件的长度可以动态扩展 。根据实现的方式的不同，链表可分为「 隐式链表 」和「 显式链接 」两种形式。

  • 隐式链表：在文件头中包含上一个数据块的指针和下一个数据块的指针。缺点在于不能直接访问想要的数据块，想要访问特定的数据块必须从头开始查找
  • 显式链表：将每个数据块的指针存在内存当中的一个表里，就既可以让数据块不连续存储，又可以直接找到特定的数据块了

Pasted image 20250611082907

但由于这张表是在内存当中的，因此对大容量的数据来说不合适用这种方式

我们再来看看索引的方式

刚刚上面说的显示链表不能支持有效访问

给每个数据块上加上索引，就能进行直接访问 Pasted image 20250611084425

当这个索引数据块所要记录的索引实在是太大了，就给这个索引数据块加上一个指向下一个索引数据块的指针，就可以拓展索引数据块的大小，这个就叫做「链式索引块 」

Pasted image 20250611084733

还有另外一种组合方式是索引 + 索引的方式，这种组合称为「 多级索引块 」，实现方式是 通过一个索引块来存放多个索引数据块

Pasted image 20250611084830

目录的存储

之前都是讲的文件本身数据的存储，而目录本身也是一种文件，在这个文件中可以查看，导航本目录的各个文件

Pasted image 20250611085416

通常，第一项是「.」，表示当前目录，第二项是「..」，表示上一级目录，接下来就是一项一项的文件名和 inode。

为了增加读取的效率，可以将保存目录的格式改为 哈希表 ，对文件名进行哈希计算，把哈希值保存起来

硬链接与软链接

有时候我们希望给某个文件取个别名，那么在 Linux 中可以通过 硬链接（ Hard Link ） 和 软链接（ Symbolic Link ） 的方式来实现

硬链接就理解为为一个文件起了别名，但文件内容并没变 软链接就理解为 为这个文件增加了一个快捷方式，指向这个文件，本身快捷方式不包含文件的内容数据。

特性硬链接软链接（符号链接）
本质文件的另一个名称/入口指向另一个文件或目录的独立文件
数据与原始文件共享数据自身不含数据，只存目标路径
删除删除一个不影响其他，数据只有所有链接都删除才释放目标删除后，链接失效
跨文件系统否是
链接目录否是
大小与原始文件相同很小，只包含路径信息

文件I/O

常见的有

  • 缓冲与非缓冲 I/O
  • 直接与非直接 I/O
  • 阻塞与非阻塞 I/O VS 同步与异步 I/O

缓冲与非缓冲I/O

  • 缓冲 I/O，利用的是标准库的缓存实现文件的加速访问，而标准库再通过系统调用访问文件。
  • 非缓冲 I/O，直接通过系统调用访问文件，不经过标准库缓存。

这里所说的「缓冲」特指标准库内部实现的缓冲。

直接与非直接 I/O

这是在磁盘这种存储方式基础上讨论的 根据是「否利用操作系统的缓存」，可以把文件 I/O 分为直接 I/O 与非直接 I/O ：

  • 直接 I/O，不会发生内核缓存和用户程序之间数据复制，而是直接经过文件系统访问磁盘。
  • 非直接 I/O，读操作时，数据从内核缓存中拷贝给用户程序，写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候写入数据到磁盘。

阻塞与非阻塞 I/O VS 同步与异步 I/O

典型操作系统的文件管理系统

FAT

为软盘开发的文件系统，最大的特点是采用了文件分配表

文件分配表 采用簇（cluster）作为基本分配单位，簇的容量与磁盘的最大容量有关，簇的最小值是1个扇区，最大值是8个扇区。FAT16采用16位的空间表示簇编号，故得名FAT16 Pasted image 20250611093540

优缺点

  • 简单，易实现
  • 操作系统普遍支持
  • 文件存取的效率低下
  • 不能管理更大的磁盘分区(2TB,FAT32)
  • 不能管理更大的文件(4GB,FAT32)

NTFS

New Technology File System 是微软转本为 Windows NT开发的文件系统，适用于Windows2000及后续的Windows系统。NTFS在FAT基础上提供了许多新特性：

  • 使用了64位磁盘地址，更好支持大容量磁盘：
  • 支持长文件名，可识别多语言字符
  • 采用了日志记录，保障数据一致性和简单容错
  • 文件加密、文件压缩等功能