操作系统

第一章 计算机 OS 概论

操作系统是控制管理计算机系统的硬软件，分配调度资源的系统软件。

OS 概念

OS 是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以方便用户使用计算机的程序集合。OS 是配置在计算机硬件上的第一层系统软件，是对硬件系统的首次扩充；是硬件系统和应用软件间的桥梁；是用户与计算机硬件进行交互的接口；是计算机系统资源的管理者。

操作系统的发展

单道批系统：内存中始终仅存一道作业运行。没有交互能力。

多道批系统：在内存中存放 多 道作业运行，运行结束或出错，自动调度 内存 中的另一道作业运行。没有交互能力。

前一个程序执行 IO 时让下一个程序占用 CPU。

分时系统

多路性、独立性、及时性、交互性，如 UNIX。在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。例如银行 ATM 机器。

实时系统

计算机及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致的运行。

OS四大基本特征 ☆

OS 的 4 个特征：并发、共享、虚拟、异步。

① 并发：一段时间间隔内多个进程（线程）并发执行，是宏观上的并行，微观上的串行。基本特征。

② 共享：系统中的资源可供内存中多个并发执行的进程或线程共同使用，宏观是多个任务同时用，微观是交替互斥。基本特征。

③ 虚拟：通过某种技术将物理实体变为若干个逻辑上的对应物。技术有时分复用和空分复用。

④ 异步：进程以人们不可预知的速度向前推进，执行结果不确定。

程序并发执行导致程序失去了封闭性，不可再现（每次执行的结果不同）。封闭性是指程序在执行过程中，其结果仅由初始条件决定，不受外界因素的影响。

OS 五大功能

OS 的 5 大功能：处理机管理、存储器管理、设备管理、文件管理、接口管理。

① 处理机管理：进程（线程）是处理机调度的单位，因而实际上是对进程（线程）的管理（控制、通信、调度、同步和互斥）。

② 存储器管理：内存的分配、回收和保护、地址转换、虚拟内存的实现等。

③ 设备管理：设备的分配与回收、缓冲区管理、磁盘调度、设备虚拟等。

④ 文件管理：文件存储空间的管理、文件目录管理、文件共享与保护等。

⑤ 接口管理：用户接口、程序接口、命令接口和网络接口。

OS 系统结构

OS主要有四种系统结构：整体式、模块化，分层式，微内核。

内核是操作系统最基本、最核心的部分。。通常将一些与硬件紧密相关的模块（如中断处理程序等）、各种常用设备的驱动程序以及运行频率较高的模块（如时钟管理模块、进程调度模块和公用基本操作模块等）都安排在紧靠硬件的软件层次中，让它们常驻内存，进而形成了所谓的 OS 内核。

OS 内核的主要功能有： ① 支撑功能，包括中断处理、时钟管理和原语操作等； ② 资源管理功能，包括进程管理、存储器管理、设备管理等 原语： 是一种特殊的程序，具有原子性，在执行过程中是不允许被中断的。原子操作在内核态下执行，常驻内存。

第二章 进程的描述与控制

2.1 进程概念

定义：是程序的一次执行，是一个程序及其数据在处理机上顺序执行时所发生的活动，是系统进行资源分配和调度的一个独立单位。

进程的实体构成；程序段、数据段、PCB(进程控制块)。

高级调度将程序从外存调入内存，分配内存创建进程，进入进程就绪队列，根据调度算法进行进程调度，等待 CPU 处理。

前趋图

2.2 ⭐进程状态

三种基本状态：运行、就绪、阻塞（三角形转换）

进程可以主动完成状态转换，也可以被动完成。进程可以同时处于多个状态。进程可以挂起自己。挂起进程不可以自我激活。

进程控制：进程控制一般是由 OS 内核中的一组原语（若干条指令组成的原子操作）来实现的。

一个进程去创建另一个进程的四类事件：用户登录，作业调度，提供服务，应用请求。

调用进程创建原语步骤：申请空白 PCB，为新进程分配资源，初始化进程控制块（初始化标识信息，处理机状态信息，处理机控制信息），将新进程插入就绪队列，启动调度。使用：wait 函数，fork 函数

进程的终止过程：根据 PID 找到 PCB 读出该进程的状态，立即终止该进程的执行，重新进行调度，将其所有子孙进程终止，将被终止进程所拥有的全部资源，归还给其父进程或者归还给系统，将 PCB 从所在队列中移出。 使用：exit，abort，return

进程的等待与睡眠：孤儿进程（父进程先于子进程 exit），僵尸进程（子进程先于父进程 exit）

进程的阻塞与唤醒

引起进程阻塞和唤醒的四类事件： 1）向系统请求共享资源失败。 2）等待某种操作的完成：如 I/O 操作时进程进入阻塞状态，I/O 完成后，被中断处理程序唤醒。 3）新数据尚未到达。处理数据的进程 A 阻塞，输入数据的进程 B 完成后去唤醒 A。 4）无新工作可做, 如此时使用 sleep（）进入休眠

阻塞过程：事件发生，进程调用 block 原语，更改 PCB 状态并将 PCB 插入阻塞队列，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换

唤醒过程：事件发生，调用唤醒原语 wakeup( )，移出阻塞队列，更改状态，插入到就绪队列。

进程的挂起：事件出现，系统调用 suspend()，检查进程状态并改为静止就绪或者静止阻塞，复制 PCB。

进程激活：事件出现，调用 active()，检查进程状态并改为活动就绪或者活动阻塞。

2.3 ⭐进程控制块PCB

PCB的四个作用

1.独立运行基本单位的标志。能实现间断性运行方式。（保护 CPU 现场）

2.提供进程管理所需要的信息。（OS 通过 PCB 对进程实施控制和管理。）

3.提供进程调度所需要的信息。（提供进程状态、优先级等信息）

4.实现与其它进程的同步与通信。（消息队列指针，信号量等）

PCB的内容

进程标识符信息：内部标识符 PID，外部标识符进程名。 处理器状态信息：各种寄存器，包括通用寄存器，PC,PSW,SP。 进程调度信息：进程状态、优先级、事件等。 进程控制信息：程序和数据的地址，进程同步和通信机制，资源清单，链接指针。

PCB的三种组织方式

1）链接方式：把具有同一状态的 PCB，用其中的链接字链接成一个队列

2）索引方式：相同状态进程的 PCB 组织在一张表格中，系统根据所有进程的状态建立几张索引表，系统分别记载各 PCB 表格的起始地址。

3）多级队列

2.4 进程的同步

2.4.1 核心概念

• 临界资源：需互斥访问的资源（如打印机、共享变量）。
• 临界区：进程中访问临界资源的代码段。
• 核心要求：任何时刻仅允许一个进程进入临界区；进程无法进入临界区时需立即释放处理机（让权等待）。
• 同步机制四大规则：空闲让进、忙则等待、有限等待、让权等待。

2.4.2 同步实现机制

（1）硬件同步机制（基础）

1. 关中断：禁止CPU响应中断，避免进程切换（简单但影响系统并发性）。
2. Test and Set（TS）指令：原子操作，测试并设置资源状态，实现互斥。
3. Swap指令：原子交换操作，通过交换内存值标记资源占用状态。

（2）信号量（Semaphore）机制（核心）

基本规则

• wait（P操作）与signal（V操作）必须配对，且先执行wait、后执行signal。
• 资源申请顺序：先申请资源信号量，再申请互斥信号量，不可颠倒。

信号量物理含义

• 初值 S.value ≥ 0，表示系统中某类资源的总数：
  • S.value > 0：可用资源数为S.value；
  • S.value = 0：无可用资源；
  • S.value = 1：退化为互斥信号量（控制临界资源互斥访问）；
  • S.value < 0：|S.value| 为等待该信号量的进程数（仅记录型信号量）。

信号量分类

类型	定义与操作	缺点/特点
整型信号量	整型变量，仅通过wait/Signal原子操作访问（P/V操作）。	未遵循“让权等待”，会导致“忙等”（进程占用CPU循环检测资源状态）。
记录型信号量	包含value（资源数）和list（等待队列）的结构体，核心实现让权等待。	解决“忙等”问题，是实际应用最广的信号量类型。
AND型信号量	一次性申请所有所需资源，满足“AND”条件后才执行，否则阻塞。	避免资源分步申请导致的死锁（如哲学家就餐问题）。
信号量集	可分配多个单位的临界资源，支持“一次申请N个资源”的场景。	适配多资源批量申请的需求。

记录型信号量代码实现

// 信号量结构体定义
typedef struct {
    int value;                  // 资源数目（初值≥0）
    struct process_control_block* list; // 等待该信号量的进程队列
} semaphore;

// wait(P操作)：申请资源
wait(semaphore* S) {
    S->value--; // 尝试获取资源
    if (S->value < 0) {
        block(S->list); // 资源不足，进程阻塞并释放CPU（让权等待）
    }
}

// signal(V操作)：释放资源
signal(semaphore* S) {
    S->value++; // 释放资源
    if (S->value <= 0) {
        wakeup(S->list); // 唤醒等待队列中的首个进程
    }
}

（3）管程机制（了解）

• 本质：封装了共享数据和操作共享数据的过程，实现进程同步的高级抽象。
• 核心规则：
  • 局部数据仅能被管程内的过程访问；
  • 任何时刻仅允许一个进程进入管程执行。

2.4.3 经典同步问题（核心应用）

（1）生产者-消费者问题

• 场景：生产者生产数据放入缓冲区，消费者从缓冲区取数据消费，需保证缓冲区互斥访问、空/满同步。
• 核心：将缓冲区计数器作为临界资源，通过信号量实现“空缓冲区数（empty）、满缓冲区数（full）、互斥锁（mutex）”的同步与互斥。

（2）哲学家就餐问题

• 场景：5个哲学家循环思考/就餐，需同时获取左右两根筷子才能就餐，易出现死锁。
• 解决方案：
  • 记录型信号量：为每根筷子设信号量（初值1），但可能死锁；
  • AND型信号量：一次性申请两根筷子，满足条件才占用，避免死锁。

// AND型信号量解决哲学家就餐问题
semaphore chopstick[5] = {1, 1, 1, 1, 1}; // 每根筷子初始可用
philosopher(int i) {
    while (true) {
        think(); // 思考
        Swait(chopstick[i], chopstick[(i+1)%5]); // 同时申请左右筷子
        eat(); // 就餐
        Ssignal(chopstick[i], chopstick[(i+1)%5]); // 同时释放左右筷子
    }
}

（3）读者-写者问题

• 核心规则：读者优先（允许多个读者同时读，写者需等待所有读者退出后才能写）。
• 关键：区分“读操作（共享）”和“写操作（互斥）”，通过信号量控制读写互斥、写写互斥。

2.4.4 同步机制例题

题目：3个进程P1（生产者）、P2（奇数消费者）、P3（偶数消费者）互斥使用N个单元的缓冲区，用信号量实现同步互斥。

信号量定义：

• empty = N：空缓冲区数目（资源信号量）；
• odd = 0：缓冲区中奇数数目（同步信号量）；
• even = 0：缓冲区中偶数数目（同步信号量）；
• mutex = 1：缓冲区互斥访问锁（互斥信号量）。

伪代码实现：

// 信号量初始化
semaphore empty = N, even = 0, odd = 0, mutex = 1;

// 生产者进程P1
P1:
while (1) {
    x = produce(); // 生成数据
    P(empty);      // 申请空缓冲区
    P(mutex);      // 申请缓冲区互斥锁
    put(x);        // 放入缓冲区
    V(mutex);      // 释放互斥锁
    if (x % 2 == 0) V(even); // 偶数则唤醒P3
    else V(odd);             // 奇数则唤醒P2
}

// 奇数消费者进程P2
P2:
while (1) {
    P(odd);        // 申请奇数数据
    P(mutex);      // 申请互斥锁
    getodd();      // 取奇数
    countodd();    // 统计奇数
    V(mutex);      // 释放互斥锁
    V(empty);      // 释放空缓冲区
}

// 偶数消费者进程P3
P3:
while (1) {
    P(even);       // 申请偶数数据
    P(mutex);      // 申请互斥锁
    geteven();     // 取偶数
    counteven();   // 统计偶数
    V(mutex);      // 释放互斥锁
    V(empty);      // 释放空缓冲区
}

2.5 进程间通信（IPC）

2.5.1 六大IPC方式总览

通信方式	核心原理	核心能力	典型场景
管道通信	内核开辟缓冲区，连接读/写进程，以字符流传输数据。	单向/双向传输字节流，仅亲缘进程可用（匿名管道）。	简单的进程间数据传输（如shell管道）。
消息队列通信	内核维护的消息链表，进程按类型发送/接收消息。	可传递结构化数据，非实时。	进程间异步传递消息（如系统通知）。
信号量通信	计数器标记资源状态，通过P/V操作实现互斥/同步。	无数据传递，仅控制资源访问。	共享内存/文件的互斥访问。
信号通信	操作系统/进程发送事件通知，进程按信号类型处理。	仅传递事件类型，无业务数据。	进程终止（SIGKILL）、中断（Ctrl+C）。
共享内存通信	多个进程映射同一块物理内存，直接读写。	传输效率最高，需同步机制配合。	大量数据高速传输（如视频处理）。
套接字通信	基于网络/本地端口，跨主机/跨进程传输数据。	支持网络通信，通用性最强。	网络应用（如客户端-服务器）。

2.5.2 信号量 vs 信号

维度	信号量通信	信号通信
核心目的	解决共享资源竞争（互斥/同步）	传递事件通知（告知进程发生某件事）
数据传递能力	无（仅标记资源状态）	极有限（仅传递信号类型）
触发方式	进程主动执行P/V操作	操作系统/其他进程主动发送
处理方式	进程根据信号量值决定等待/占用	进程执行处理函数/默认行为/忽略

2.5.3 进程间通信机制详解补充

（1）共享存储器系统

• 共享数据结构：如有界缓冲区，仅适用于少量数据传输；
• 共享存储区：进程映射同一块物理内存，进程可以直接读写（效率最高），无需内核拷贝数据，但是无内置同步机制，需手动加锁（信号量 / 互斥量）防止竞态。

（2）管道（Pipe）通信

类型	创建方式	通信范围	生命周期
匿名管道	pipe()	仅血缘进程（父子/兄弟）	随进程退出自动销毁
命名管道(FIFO)	mkfifo()	任意进程（无血缘限制）	以文件形式存在，需显式删除

管道本质是内核中的单向缓存，通过文件描述符操作，默认半双工（双向通信需创建两个管道）。

匿名管道核心操作流程（以ls | more为例）

核心逻辑：Shell通过pipe+fork+dup2+exec实现命令间数据传递，步骤可简化为：

1. 创管道：Shell调用pipe()生成读端fd[0]、写端fd[1]；
2. 子进程1（ls）：关读端 → 重定向stdout到写端 → 关原写端 → exec执行ls（输出写入管道）；
3. 子进程2（more）：关写端 → 重定向stdin到读端 → 关原读端 → exec执行more（从管道读数据）；
4. 父进程：关闭自身管道两端，等待子进程结束。

管道读写规则

• 空管道读：有写端则阻塞，无写端则返回0（EOF）；
• 满管道写：阻塞等待空间；
• 读端全关：写操作触发SIGPIPE（默认终止进程）；
• 写端全关：读剩余数据后返回0（EOF）。

管道释放规则

• 进程通过close()关闭管道描述符；
• 内核仅在所有读/写端描述符都关闭时，才销毁管道缓存、释放资源。

（3）消息传递方式

• 直接通信：进程通过send(目标进程, 消息)/receive(源进程, 消息)直接交互；
• 间接通信：通过中间实体（信箱、消息缓冲队列）传递消息。

内核级存储：消息队列是内核维护的消息链表，与管道不同，它独立于进程存在，通过唯一的队列 ID标识； 消息结构：每个消息包含 类型字段（长整型） + 数据长度 + 实际数据，类型字段是其核心特色； 核心优势：支持异步通信、按类型选择性读取、生命周期不依赖进程。

核心操作（4 个关键函数）

函数	核心作用	关键说明
msgget()	创建新队列 / 获取已有队列 ID	需指定键值（key），可通过 IPC_PRIVATE 创建私有队列
msgsnd()	向队列尾端发送消息	支持阻塞（默认）/ 非阻塞模式，消息按类型追加
msgrcv()	从队列读取消息	可指定读取特定类型的消息（非严格 FIFO）
msgctl()	管理队列（删除 / 查看状态）	常用 IPC_RMID 显式删除队列，否则内核重启才释放

2.6 线程与线程控制

线程概述

线程是独立运行的基本单位,因而也是独立调度和分派的基本单位。而进程作为资源拥有的基本单位。在一些操作系统中，线程的切换、同步和通信都无须操作系统内核的干预。 线程可以分为用户级和内核级。内核级能充分利用CPU，但代价也大。

⭐进程与线程的区别

比较维度	进程 (Process)	线程 (Thread)
调度性	资源分配的基本单位	CPU 调度的基本单位 ★
系统开销	开销大（创建/销毁/切换需资源隔离）	开销小（共享内存，切换快）★
独立性	内存隔离，互不影响（独立地址空间）★	共享进程内存，相互可见（需同步机制）
并行性	多进程需 IPC 通信，效率较低	多线程天然共享内存，并行高效 ★
拥有资源	拥有独立资源（内存、文件、设备等）★	共享进程资源，仅私有栈/寄存器等少量资源

⭐五种线程同步方式

1. 互斥锁(Mutex) ：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。

2. 读写锁（Read-Write Lock） ：允许多个线程同时读取共享资源，但只有一个线程可以对共享资源进行写操作。

3. 信号量(Semaphore) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。

4. 屏障（Barrier） ：屏障是一种同步原语，用于等待多个线程到达某个点再一起继续执行。当一个线程到达屏障时，它会停止执行并等待其他线程到达屏障，直到所有线程都到达屏障后，它们才会一起继续执行。比如 Java 中的 CyclicBarrier 是这种机制。

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

第三章 ⭐处理机调度与死锁

3.1 调度概述

3.1.1 调度的三级分类

调度级别	别称	核心操作	适用系统	调度频度
高级调度	作业调度、长程调度	将外存作业调入内存，创建 PCB，插入就绪队列	批处理系统	最低（分钟级）
中级调度	交换调度、中程调度	将外存静止就绪进程重新调入内存，转为活动就绪	分时 / 批处理系统（缓解内存压力）	中等
低级调度	进程调度、短程调度	从就绪队列选取进程，分配处理机	所有操作系统	最高（毫秒级）

3.1.2 调度性能评价指标

• 周转时间：周转时间 = 完成时间 - 到达时间
• 带权周转时间：带权周转时间 = 周转时间 / 服务时间
• 核心评价依据：平均带权周转时间，数值越小表示调度算法性能越好

3.2 作业调度

1. 核心数据结构：作业控制块（JCB），是作业管理系统管理和控制作业运行的依据。
2. 作业三阶段：与进程状态一一对应
   • 收容阶段 → 后备状态
   • 运行阶段 → 进程的运行 / 就绪 / 阻塞状态
   • 完成阶段 → 完成状态

3.3 ⭐进程调度

1. 核心任务

   • 保存当前进程的处理机现场信息
   • 从就绪队列选取待调度进程
   • 恢复选中进程的现场信息，分配处理机

2. 调度机制组成

   • 排队器：组织就绪队列
   • 分派器：执行处理机分配
   • 上下文切换器：完成进程上下文的切换

3.3.2 调度方式

调度方式	触发条件	核心特点
非抢占式	进程阻塞、运行完毕或无法继续执行	调度频率低，系统开销小
抢占式	新增高优先级就绪进程、进程执行原语操作等	响应速度快，系统开销大

3.3.3 进程优先级设定依据

• 进程的重要性与紧迫性
• 进程资源占用特性（如短进程赋予高优先级）
• 进程类型（如系统进程优先级高于用户进程）

3.4 实时调度

3.4.1 常用实时调度算法

1. 最早截止时间优先算法（EDF）
   • 核心规则：任务的截止时间越早，优先级越高，排在就绪队列队首
   • 适用场景：周期性 / 非周期性实时任务
2. 最低松弛度优先算法（LLF）
   • 松弛度计算公式：松弛度 = 完成截止时间 - 剩余运行时间 - 当前时间
   • 核心规则：松弛度越小，任务优先级越高；松弛度为 0 时触发抢占

LLF例题：假如在一个实时系统中，有两个周期性实时任务 A 和 B 任务，A 要求每 20ms 执行一次，执行时间为 10ms；任务 B 只要求每 50ms 执行一次，执行时间为 25ms

3.4.2 实时调度关键问题：优先级倒置

1. 发生条件
   • 低优先级进程（L）持有高优先级进程（H）所需的共享资源
   • 系统支持抢占式调度，存在中间优先级进程（M）
   • 时序触发：H 因等待资源阻塞，M 就绪后抢占 L 的 CPU，导致 L 无法释放资源
2. 典型场景 L 持有资源 R→H 就绪并等待 R→M 就绪抢占 L→L 暂停，H 长期阻塞
3. 解决办法：动态优先级继承 当高优先级进程 H 等待低优先级进程 L 的资源时，临时将 L 的优先级提升至 H 的级别，使其尽快执行并释放资源

⭐七个进程调度算法

算法名称	核心规则	优点	缺点	适用场景
1. 先来先服务（FCFS）	按进程到达顺序调度	公平、实现简单	不利于短进程，CPU 利用率低	批处理系统、CPU 繁忙型进程
2. 短作业优先（SJF）	优先调度估计运行时间最短的进程	吞吐量高，平均等待时间短	长作业饥饿，需预估运行时间	批处理系统
3. 优先级调度算法（PSA）	按进程优先级高低调度	响应紧急任务	低优先级进程饥饿	实时系统、分时系统
4. 高响应比优先调度（HRRN）	优先权公式：(等待时间+服务时间)/服务时间	兼顾短进程与长进程	需动态计算响应比，开销大	批处理系统
5. 轮转调度算法（RR）	FCFS + 时间片轮转，时钟中断触发抢占	响应速度快，公平性好	时间片设置影响性能，不利于 I/O 密集型进程	分时系统
6. 多级反馈队列调度算法	① 多队列 + 优先级递减 ② 优先级越高，时间片越短 ③ 未完成进程降级入下一级队列 ④ 高优先级队列空闲时调度低优先级队列	兼顾公平与效率，性能最优	实现复杂	通用操作系统（主流算法）
7. 基于公平原则的调度算法	保证调度：保障进程绝对运行时间 公平分享调度：按用户数分配 CPU 时间	公平性强	系统开销大	注重公平性的分时系统
多级反馈队列算法补充规则：未执行完时间片的进程被抢占后，不降级，排入原队列末尾，下次调度时分配完整时间片

调度算法例题与公式

• 周转时间 = 执行时间 + 等待时间
• 带权周转时间 = 周转时间 / 执行时间
• 核心计算步骤：确定作业执行顺序 → 计算单个作业周转时间与带权周转时间 → 求平均值评价算法性能

（1）作业执行顺序

（2）周转时间和带权周转时间

3.5 ⭐死锁概述

定义：两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

死锁的进程都不能运行、释放资源、被唤醒

产生死锁的原因可归结为两点：（1）竞争资源：可重用资源的竞争，可消耗资源的竞争（2）进程间推进顺序非法 。 死锁发生的**四个必要条件：

1. 互斥：资源必须处于非共享模式，即一次只有一个进程可以使用。如果另一进程申请该资源，那么必须等待直到该资源被释放为止。

2. 占有并等待：一个进程至少应该占有一个资源，并等待另一资源，而该资源被其他进程所占有。

3. 非抢占：资源不能被抢占。只能在持有资源的进程完成任务后，该资源才会被释放。

4. 循环等待：有一组等待进程 {P0, P1,..., Pn}， P0 等待的资源被 P1 占有，P1 等待的资源被 P2 占有，……，Pn-1 等待的资源被 Pn 占有，Pn 等待的资源被 P0 占有。

3.6 ⭐预防和避免死锁

三个预防方式

互斥条件必须保证，只能破坏其余三个条件。

1、系统规定所有进程在开始运行之前都必须一次性地申请其在整个运行过程所需的全部资源。

2、当一个已经保持了某些资源的进程再提出新的资源请求而不能立即得到满足时 必须释放它已经保持了的所有资源 。 待以后需要时再重新申请 。（比较难）

3、系统将所有资源按类型进行线性排队，并赋予不同的序号。 所有进程对资源的请求必须严格按照资源序号递增的次序提出。

避免

安全状态：是指系统能按某种进程顺序如 依次为 n 个进程分配其所需资源 直至其最大需求 使每个进程都可顺利地完成。

避免死锁的实质：确保系统在安全状态

避免死锁的条件：

• 预先必须申明每个进程需要的资源总量；
• 进程之间相互独立 其执行顺序取决于系统安全 而非进程间的同步要求；
• 系统必须提供固定数量的资源供进程使用；避免死锁的限制

⭐银行家算法！

• n个进程：$P_1, P_2, ..., P_n$
• m类资源：$R_1, R_2, ..., R_m$

1. 可利用资源向量：$\text{available}[j] = k$ ，表示资源 $R_j$ 类当前有 $k$ 个可用。
2. 最大需求矩阵：$\text{Max}[i,j] = k$，表示进程 $P_i$ 对资源 $R_j$ 的最大请求量为 $k$。
3. 分配矩阵：$\text{Allocation}[i,j] = k$，表示进程$P_i$已分配到 $k$个资源 $R_j$。
4. 需求矩阵：$\text{Need}[i,j] = k$，表示进程 $P_i$ 还需要 $k$ 个资源 $R_j$。

三个矩阵的关系

$\text{Need}[i,j] = \text{Max}[i,j] - \text{Allocation}[i,j]$

设 $\text{Request}_i$ 是进程 $P_i$ 的请求向量，系统按以下步骤检查：

1. 检查请求合法性 若 $\text{Request}_i[j] \leq \text{Need}[i,j]$，则进入步骤2； 否则出错（请求资源超过进程声明的最大需求）。
2. 检查资源可用性 若 $\text{Request}_i[j] \leq \text{Available}[j]$，则进入步骤3； 否则 $P_i$ 阻塞等待（无足够可用资源）。

系统试探性为进程 $P_i$ 分配资源，并更新数据结构： \begin{align*} \text{Available}[j] &= \text{Available}[j] - \text{Request}_i[j] \\ \text{Allocation}[i,j] &= \text{Allocation}[i,j] + \text{Request}_i[j] \\ \text{Need}[i,j] &= \text{Need}[i,j] - \text{Request}_i[j] \end{align*}

安全性检查

银行家算法例题

由 5 个进程组成进程集合 P={P0，P1，P2，P3，P4}，系统中有 3 类资源 A，B，C，假设在某时刻有表所示的进程资源分配情况。

请问当 x，y，z 取下列值时，系统是否处于安全状态？ （1）1，4，0；（2）0，6，2；（3）1，1，1；（4）0，4，7。

3.7 ⭐死锁的检测和解除

检测

死锁定理：如果资源分配图中不存在环路，则系统中不存在死锁。

判断结点是否处于阻塞状态：观察该结点申请的资源能否被分配。

若能消去资源分配图中所有结点的连接边 使全部结点都成为孤立结点 则称该图是可完全简化图；若不能使该图完全简化 则称该图是不可完全化简图 。可以证明： 当且仅当系统某状态 S 所对应的资源分配图是不可完全化简的，则 S 是死锁状态 。 该充分条件称为死锁定理 。

解除

1、 剥夺资源 。 从其它进程剥夺足够数量资源给死锁进程 以解除死锁状态 。 2、 撤消进程 。

遵循最小代价原则：尽量牺牲最小的进程

哲学家问题互斥信号量改进解法：先让四位哲学家吃饭（阻塞第五位），第一位吃完了再唤醒第五位

第四章 ⭐存储器管理

MMU 将虚拟地址翻译为物理地址的主要机制有 3 种:

1. 分段机制

2. 分页机制

3. 段页机制 其中，现代操作系统广泛采用分页机制。

4.1 存储器层次结构

一个有效的存储分配机制，应具有如下 3 个功能： (1)记住每个存储区域的状态： 哪些是已分配的，哪些是可以用作分配的。 (2)实施分配： 在系统程序或用户提出申请时，按所需的量给予分配；修改相应的分配记录表。 (3)接收系统或用户释放的存储区域： 并相应地修改分配记录表。

解决存储分配问题的三种方式 1.直接指定方式 2.静态分配方式：存储分配是在装入时实现的。

3.动态分配方式 Dynamic：

(1)作业在存储空间中的位置，在装入时确定； (2)在执行过程中可根据需要申请附加的存储空间； (3)一个作业已占用的部分存储区域不再需要时，可以要求归还给系统。即：这种存储分配机制能接受不可预测的分配和释放存储区域的请求，实现个别存储区域的分配和回收； (4)存储区域的大小是可变的； (5)允许作业在内存中“搬家”。

名空间：一个用高级语言编制的源程序，我们说它存在于由程序员建立的 符号名字空间 。 地址空间：程序用来访问信息所用地址单元的集合是逻辑 相对 地址的集合， 由 编译程序 生成 。

4.2 程序的装入和链接

装入

根据存储空间的分配方式，将一个装入模块装入内存时，可采用三种方式：

• 绝对装入：生成绝对地址代码，直接按地址装入，程序中的 逻辑地址与实际内存地址完全相同， 适用于单道程序。

• 可重定位装入（静态重定位）：经 编译 得到的目标模块中为 相对地址 （通常从 0 开始），即地址都是相对于 0 开始的。装入内存时，相对地址（数据、指令地址）要作出相应的修改以得到正确的物理地址，这个修改的过程称为 重定位 。 静态重定位：地址变换是在 装入内存时一次完成 的，且以后不能移动。一般情况下 物理地址 相对地址 内存中的起始地址。

• 动态运行时装入（动态重定位）：装入程序将装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是 把这种地址转换推迟到程序 执行时 进行。 在硬件地址变换机构的支持下，随着对每条指令或数据的访问自动进行地址变换，故称为 动态重定位 。

链接

链接程序的功能，是将经过编译后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。 根据链接时间的不同 ，可把链接分成三种。

• 静态链接：1.将相对地址进行修改。 即将除第一个模块外的相对地址修改成装入模块中的相应的相对地址。

  2.变换外部调用符号。 即将每个模块中所用的外部调用符号，都变换为相对地址。

• 装入时动态链接：装入内存时边装入边链接，便于模块修改和共享。 若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将其装入内存。

• 运行时动态链接：将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，由 OS 去找到该模块，将它装入内存，并链接到调用模块上。节省大量内存，最常用。

4.3 连续分配存储管理方式

性能指标：

内零头 Internal Fragment：分配给用户但用户没有使用的空间，多分配的空间 外零头 External Fragment：没有分配但无法分配的空间，太小而无法分配， 分不出去的空间

单一连续分配

只有一个进程在内存，内存分为系统区（低址）和用户区，仅支持单用户，简单但内存利用率低。

固定分区分配

• 内存在系统启动时划分为固定大小分区，支持多道程序，分区大小可相等或不等，存在内零头（分区内未利用空间）。

• 数据结构：分区说明表记录分区状态、大小和地址。

当有作业要装入内存时，内存分配程序 检索分区说明表，从中找出一个 尚未使用的满足大小要求 的分区分配给该作业，然后修改分区的状态；如果找不到合适的分区就拒绝为该作业分配内存。 存储空间利用率低，几乎不用。

动态分区分配

分区大小动态变化，数量可定可变（可变更灵活），数据结构为空闲分区表或链表。涉及动态分区的主要操作有分配内存 和 回收内存（当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链 表 中找到相应的插入点 ） 。

分区分配算法

顺序搜索的动态分区分配算法

• 最佳适应：选择最小足够大分区，易产生小碎片，回收麻烦。

• 最坏适应：选择最大空白分区，减少碎片但缺乏大空闲区。

• 首次适应：每个空白区按其在存储空间中 地址递增 的顺序链在一起，即每个后继空白区的起始地址总是比前者的大。在为作业分配存储区域时，从这个空白区链的始端开始查找，选择第一个足以满足请求的空白块。

• 下次适应：把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。分区分布更均匀。

索引搜索的动态分区分配算法

• 快速适应： 将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。同时，在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的 索引表 ，该表的每一个表项记录了对应类型空闲分区链表表头的指针。分配过程： 根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行分配即可。

• 伙伴系统管理算法

⭐伙伴系统算法

高效分配与回收，二叉树能快速查找，适合分页机制，碎片少。

哈希算法

用空间表中的分布规律，建立哈希函数，构造一张 哈希表，以空闲分区大小为关键字 ，每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配。

可重定位分区分配

引入紧凑技术：一个最简单而直观的解决零头问题的办法是，定时地或者在内存紧张时，把存储空间中的空白区合并为一个大的连续区。需动态重定位寄存器支持地址转换。

4.4 ⭐分页存储管理方式

一次性：要求将作业全部装入内存后方能运行。 驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。

基本概念

• 页面与物理块：逻辑地址划分为页（页面大小由 机器的地址结构 决定。某一机器只能采用一种大小的页面，通常在 1KB~8KB 之间），内存划分为等大物理块，最后一页可能产生页内碎片（内零头）。

数据结构

1 ）页表 每个进程对应 1 个页表，描述该进程的各页面在内存中对应的物理块号 。页表中包括 页号 、 物理块号（还可有 存取控制字段对存储块中的内容进行保护）。全部页表集中存放在 主存的系统专用区 中，只有系统有权访问页表，保证安全。 2 ）作业表 整个系统 1 张，记录作业的页表情况，包含进程号、页表长度、页表始址等信息。 3 ）空闲块表 整个系统 1 张，记录主存 当前空闲块。这几个表都放在内存中。

地址结构：在页式管理系统中将地址空间分成大小相同页面 。将 内存空间分成与页面相同大小的存储块。逻辑地址=页号+页内偏移量，如 32 位系统中页号占 20 位，偏移量占 12 位（页面大小 4KB）。 计算时注意 1K = 1024 设有一逻辑地址 A ，页面大小为 L ，则在分页存储管理方式中，它的地址被转换： 页号 P=INT[A/L] ，页内位移量 W=A MOD L 如有逻辑地址为： 2170 ，页面大小为 1KB ，则 P=INT[2170/1024]=2 W=2170 MOD 1024=122

地址变换

地址变换机构的功能是将用户的逻辑地址 转变为内存中的 物理地址 。逻辑地址由 页号 和 页内位移量 组成。页的大小和内存物理块的大小是相同的，所以页内位移量即为物理块内 位移 量。关键是 页号到物理块号的转换 ，由 页表 完成。

页表一般放在内存里。然后用页表寄存器 PTR：记录 当前运行的进程的 页表在内存中的 始址 和 页表长度 。平时存于 PCB 中，要运行时才装入 PTR。

无快表的地址转换过程

1 根据逻辑地址 计算出页号和页内偏移量； 2 从 PTR 中得到页表首址 然后检索页表查找指定页面对应的页框号； 3 用页框号乘以页面大小获得其对应的起始地址，并将其送入物理地址的高端 。 4 将页内偏移量送入物理地址低端 形成完整的物理地址 。

• 快表（TLB）：缓存近期访问页表项，**降低内存访问次数，**将内存访问次数从 2 次（第一次访问页表，以得到物理地址，第二次访问物理地址，以得到数据）减为 1 次，提高效率。

1 根据逻辑地址中的页号 查找快表中是否存在对应的页表项 。 2 若快表中存在该表项 称为 命中 hit 取出其中的页框号 加上页内偏移量 计算出物理地址 。 3 若快表中不存在该页表项 称为 命中失败 则再查找页表 找到逻辑地址中指定页号对应的页框号 。 同时 更新快表 将该表项插入快表中 。 并计算物理地址。

访问内存的有效时间 EAT：从进程发出指定逻辑地址的访问请求，经过地址变换，再到内存中找到对应的物理单元并取出数据，所花费的总时间 。访问快表会耗费时间，所以要求快表有较高的命中率。

• 两级页表：外层页表映射内层页表物理块，逻辑地址=外层页号（10 位）+内层页号（10 位）+偏移量（12 位），解决单级页表占用连续内存问题（如 32 位系统页表需 8MB 连续空间）。

• 多级页表：建立页表“树”，减少每级页表的长度。对于大地址空间(64 bits) 系统，多级页表变得 繁琐

• 反置页表 IPT： 想要避免一个进程一个页表。为主存中的每一个物理块建立一个页表项并按照块号排序；该表每个表项包含正在访问该物理块的 进程标识、页号及特征位 用来完成主存物理块到访问进程的页号的转换。给出进程标识和页号 用它们去比较 IPT, 若整个反置页表中未能找到匹配的页表项 说明该页不在主存 产生 请求调页中断 请求操作系统调入 否则 该表项的序号便是物理块号 块号加上位移便形成物理地址。

对换

对换指把内存中暂不能运行的进程或暂时不用的程序和数据，换到外存上，以腾出足够的内存空间，把已具备运行条件的进程或其所需的程序和数据换入内存。 对换是系统行为，是提高内存利用率的有效措施，常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。系统中可设一个对换进程，执行换进内存、换出至外存操作。

外存划分

外存分为文件区和对换区两部分：

1. 文件区用于存放文件，管理重点是提高存储空间利用率，采用离散分配方式（文件可分成多块，存储于不邻接区域，用指针相连）。

2. 对换区

   • 用于存放从内存换出的进程，进程在外存存放时间短、换入换出频繁，管理重点是提高换入换出速度，采用连续分配方式（进程存放到连续存储空间中）。

   • 系统配置相应数据结构（如空闲分区表或空闲分区链）管理对换区的空闲盘块，空闲分区表的每个表目包含对换分区首址和长度（基本单位为盘块）。

   • 对换区采用连续分配方式，其空间的分配与回收方法与动态分区方式时内存的分配与回收雷同。

对换分类

• 分类： 整体对换/进程对换（以进程为单位）； 页/分段对换。

• 关键操作：

  • 换出：选择阻塞态、睡眠态进程（无则选就绪态）、低优先级进程，释放内存。

  • 换入：选择就绪且换出时间久的进程，调入内存，直至无就绪且换出进程或无法获得足够内存空间为止。

4.5 分段存储管理方式

分段存储符合程序模块化设计的思想。段是信息的逻辑单位，可以为共享过程建立一个独立的段，便于实现程序和数据的共享，分段保护，动态链接，动态增长 。相比分页，

1. 基本概念

   • 分段：逻辑地址划分为段（如代码段、数据段），段长可变，逻辑地址=段号+段内偏移量（二维地址）。

   • 段表：记录段号、段基址和段长，用于地址变换。

2. 地址变换

   • 实现分段管理的关键在于，如何保证分段 二维 地址空间中的一个作业在线性 一维 的存储空间中正确运行 。 也就是说，如何把分段地址结构变换成线性的地址结构，和分页管理一样，可采用 动态重定位技术 ，即通过地址变换机构来实现。

   • 为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。在系统内存中为每个进程建立一张段映射表，简称 段表 。每个段在表中占有一个表项，其中记录了该段在内存中的 起始地址 又称为 基址 和 段的长度 。检查段号和段内偏移量是否越界，段基址+偏移量得到段物理地址。

   

   

若段表放在内存中，每访问一个数据需要访问内存 2 次。可设置联想存储器（快表），以提高访问速度。

对于可重入代码（允许多个进程同时访问的只读代码），可以大大节省内存。分段的共享是通过两个作业段表的相应表目都指向同一物理副本，但一个公共过程在不同作业中无需赋予相同的段号。

4.6 段页式存储管理方式

• 基本原理：先分段再分页，逻辑地址=段号+段内页号+页内偏移量。

• 数据结构：段表（记录段对应的页表起始地址）和页表（记录页与物理块映射）。

地址变换机构

需三次内存访问（访问段表 → 页表 → 物理地址），系统开销大但综合分段和分页优点。可以设置快表 ，表项应包括段号、页号、物理块号

4.7 虚拟存储器基础

背景：常规存储的一次性和驻留性 严重降低内存利用率，减少系统吞吐量。覆盖：应用程序手动 把需要的指令和数据保存在内存中。 对换：操作系统自动 把暂时不能执行的程序保存到外存中。

总结来说，虚拟内存主要提供了下面这些能力：

• 隔离进程：物理内存通过虚拟地址空间访问，虚拟地址空间与进程一一对应。每个进程都认为自己拥有了整个物理内存，进程之间彼此隔离，一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。

• 提升物理内存利用率：有了虚拟地址空间后，操作系统只需要将进程当前正在使用的部分数据或指令加载入物理内存。

• 简化内存管理：进程都有一个一致且私有的虚拟地址空间，程序员不用和真正的物理内存打交道，而是借助虚拟地址空间访问物理内存，从而简化了内存管理。

• 多个进程共享物理内存：进程在运行过程中，会加载许多操作系统的动态库。这些库对于每个进程而言都是公用的，它们在内存中实际只会加载一份，这部分称为共享内存。

• 提高内存使用安全性：控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性。

• 提供更大的可使用内存空间：可以让程序拥有超过系统物理内存大小的可用内存空间。这是因为当物理内存不够用时，可以利用磁盘充当，将物理内存页（通常大小为 4 KB）保存到磁盘文件（会影响读写速度），数据或代码页会根据需要在物理内存与磁盘之间移动。 如果没有虚拟内存的话，程序直接访问和操作的都是物理内存，看似少了一层中介，但多了很多问题。

具体有什么问题呢？ 这里举几个例子说明(参考虚拟内存提供的能力回答这个问题)：

1. 用户程序可以访问任意物理内存，可能会不小心操作到系统运行必需的内存，进而造成操作系统崩溃，严重影响系统的安全。

2. 同时运行多个程序容易崩溃。比如你想同时运行一个微信和一个 QQ 音乐，微信在运行的时候给内存地址 1xxx 赋值后，QQ 音乐也同样给内存地址 1xxx 赋值，那么 QQ 音乐对内存的赋值就会覆盖微信之前所赋的值，这就可能会造成微信这个程序会崩溃。

3. 程序运行过程中使用的所有数据或指令都要载入物理内存，根据局部性原理，其中很大一部分可能都不会用到，白白占用了宝贵的物理内存资源。

---

著作权归JavaGuide(javaguide.cn)所有 基于MIT协议 原文链接：https://javaguide.cn/cs-basics/operating-system/operating-system-basic-questions-02.html

虚拟存储器

是指具有请求调入功能和置换功能能从逻辑上对内存容量加以扩充的一种存储器系统 。采用请求存储管理方式实现--在纯分页/段系统的基础上增加了请求调页/段 、 页面/分段置换 两大功能。

需要硬件支持：1.请求分 页/段 的 页/段 表机制。2.缺 页/段 中断机构。3.地址变换机构。

核心思想

• 基于局部性原理（时间局限性：循环操作重复访问；空间局限性：邻近地址访问），允许程序部分装入内存，运行时动态调入所需页/段，淘汰暂不用页/段。

• 逻辑容量=内存+外存，速度接近内存，成本接近外存。

**特征：**虚拟性是以多次性和对换性为基础的；而多次性和对换性又必须建立在离散分配的基础上。

过程：1. 基于 局部性原理 。一个作业运行前，仅将那些 当前要运行的页面（段）装入内存 启动运行，其余暂在外存。

2. 若运行所需页面（段）不在内存，则利用 请求调页（段） 功能将其调入内存。

3. 若此时内存满，则利用 置换 功能，将内存中暂时不用的部分页面（段）调至外存，再将所需页面（段）调入。

4.8 请求分页存储管理

作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由 OS 将其从辅存调入主存，如果内存无空块，则根据某种算法选择一个页淘汰以便装入新的页面。

硬件支持

• 请求页表机制 ： 在请求分页系统中所需要的主要数据结构是页表。在请求分页系统中的每个页表项如下所示

• 

  字段	作用
  页框号 Q	物理内存空间（实际存储单元），也就是块号
  状态位 P	标志页是否在内存（1=在，0=不在）
  访问位 A	记录页访问频率（统计缺页率）
  修改位 M	标记页是否被修改（置换时优先换出未修改页，减少 I/O）
  外存地址	页在外存的存储位置

• 缺页中断机构：缺页中断 是一种特殊的中断，要求在指令执行中间得到服务，即发现所要访问的指令或数据不在内存时产生 缺页中断 并处理。系统在出现页面故障时，保存部分完成的指令的状态。此外，还需要使用一条特殊的返回指令，确保在出现 缺页中断处恢复该指令的处理。

• 地址变换机构：增加了如产生和处理缺页中断，从内存中换出一页的功能等。逻辑地址 → 页号+偏移量，查页表/快表获取物理块号，拼接物理地址。

内存分配策略

为进程分配物理块的问题

① 最小物理块数的确定

给每个进程所分配物理块数目越少，则进程执行中的缺页率越高，进程的执行速度也减慢。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式，如单地址指令且直接寻址，则 2，对于前面在缺页中断机构中要发生 6 次中断的情况，至少要为每个进程分配 6 个物理块。

② 物理块的分配策略

• 固定分配局部置换：进程运行期间物理块数固定，置换范围仅限自身页面（如分配 3 块，缺页时从 3 块中选换）。

• 可变分配全局置换（常用）：系统保留空闲块队列，缺页时优先分配新块，满则从任意进程置换（常用，灵活性高）。

• 可变分配局部置换：根据进程缺页率动态调整块数，置换仅限自身页面（实现复杂，需统计开销）。

③ 物理块的分配算法

• 平均分配算法：各个进程平均分配。

• 按比例分配算法：根据进程页数占总页数的权进行分配。

• 考虑优先权的分配算法：一部分按比例，一部分按优先级。

页面调入策略

何时调页： 两种策略。

• 1.请求调页：缺页时调入，初始缺页率高，后续稳定（常用）。

• 2.预调页：预测调入相邻页，成功率约 50%，适用于局部性强的程序。

从何处调页： 有两种区域，三种情况。

• 对换区：存放修改过的页，连续分配，I/O 速度快。

• 文件区：存放未修改的页（如程序代码），离散分配，首次调入从文件区，换出时不回写。

  1.系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页的速度。

  2.系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。

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

页面调入过程：整个页面的调入过程对用户是透明的。

① 每当程序所要访问的页面未在内存时，便向 CPU 发出一缺页中断。 ② 中断处理程序首先保留 CPU 环境，分析中断原因后，转入缺页中断处理程序。 ③ 如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果此页已被修改，则必须将它写回磁盘。 ④ 然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为 1 ””，并将此页表项写入快表中。 ⑤ 形成所要访问数据的物理地址，再去访问内存数据。

缺页率 f：逻辑空间为 n 页，内存物理块数为 m(m<=n)，在运行期间访问页面成功 S 次，失败 F 次，总访问次数为 A=S+F 次，则 f=F/A

页面置换算法 ☆

作用：需要调入页面时，选择内存中哪个或哪些物理页面被置换。

FIFO：只需要建立一个替换指针，始终指向最早调入主存的一页。

LRU：当进程访问某物理块时，要将相应寄存器的最高位置成 1 。系统每隔一定时间（例如 100 ms ）将寄存器右移一位。具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。每当进程访问时某页面时，便将该页面号从栈中移出，压入栈顶。这样栈底则是最近最久未使用页面的页面号。

LFU：为页面设置移位寄存器，记录每个页面的访问次数

CLOCK：置换程序 从上次停止位置开始检查页面的访问位。如果是 0 ，就选择该页换出若为 1 ，则重新将它置 0 ，暂不换出，而给该页第二次驻留内存的机会。

算法	核心逻辑	缺页率	实现难度
最佳算法 OPT	淘汰最远未来访问页（理论最优）	最低	无法实现
先进先出 FIFO	淘汰最早进入内存即驻留时间最长的页（队列实现），容易误删	较高	简单
最近最久未使用 LRU	淘汰最近最久未访问页（需记录访问时间，移位寄存器或栈实现）	较低	复杂
最少使用 LFU	选择到当前时间为止被访问次数最少的页面被置换。
最近未用 Clock	循环检查访问位 A，A=0 则换出（A=1 置 0，给予第二次机会）	中等	中等
改进型 Clock	优先换出 A=0 且 M=0 的页（未访问+未修改），其次 A=0/M=1（未访问+已修改）	较低	中等

4.9 抖动与工作集

有效访问时间是指访问存储器所需时间的平均值。

当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存。 如果被交换出去的页面或段很快将被进程使用，则又需要将其换入内存。如果系统花费大量的时间把程序和数据 频繁地换入和换出内存 而不是执行用户指令，那么，称系统出现了 抖动 。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。 **根本原因：选择的页面或段不恰当。**抖动产生的原因有：进程分配的物理块太少，置换算法选择不当，全局置换使抖动传播。

• 多道程序度过高 → 单个进程物理块不足/置换策略不当 →频繁缺页 → 系统忙于置换，形成恶性循环 →cpu 利用率急剧下降。

工作集（w(t,⊿)）

• 定义：进程在时间窗口 ⊿ 内访问的页面集合，反映当前活跃页面。 ⊿ 称为工作集的窗口尺寸

• 作用：通过监控工作集大小，动态调整进程物理块数，预防抖动（如 ⊿=100ms 时，统计最近 100ms 内访问的页面）。

D 是所有进程的工作集大小之和，m 是当前内存物理容量。

预防措施

采取局部置换策略；引入工作集的算法；L=S 准则：L 缺页之间的平均时间， S 平均缺页服务时间；选择暂停的进程。

4.10 请求分段存储管理

在请求分段系统中，程序运行之前，只需先调入若干个分段（不必调入所有的分段），便可启动运行。当所访问的段不在内存中时，发出缺段请求，OS 将所缺的段调入内存。

段表机制

段名	段长	段的基址	存取方式	状态位 P	访问位 A	修改位 M	增补位	外存地址

• 存取方式：定义进程对该内存段的访问权限

• 增补位：标志段是否在运行中动态增长（如栈段、数据段）。

• 外存始址：段在外存的起始地址，支持动态调段。

段缺中断机构

地址变换机构

分段共享与保护

• 配置一个共享段表：记录共享段的进程计数（count）、存取权限（如只读/读写），不同进程可通过不同段号共享同一物理段。

• 保护机制：

  • 1.越界检查：段号 ≥ 段表长度或偏移量 ≥ 段长时触发中断。 2.存取控制检查。

  • 3.环保护：0 环（内核）特权最高，3 环（用户程序）最低，低环可访问同环或高环数据，调用同环或低环服务。

第五章 输入输出系统

5.1 I/O 系统概述

核心功能 1.设备分配 2.设备映射 3.设备驱动 4.I/O 缓冲区的管理

I/O 系统层次模型

层次	功能描述
用户层	发出 I/O 请求（如系统调用read/write），通过库函数调用内核接口。
设备独立性软件	实现逻辑设备到物理设备映射（逻辑设备表 LUT），管理设备分配与释放。
设备驱动程序	将抽象请求转换为设备特定指令（如磁盘块号 → 磁道/扇区），启动设备控制器。
中断处理程序	响应设备中断，处理 I/O 完成事件，恢复进程上下文。
设备硬件	包括设备控制器、通道、物理设备（如磁盘、打印机）。

5.2 I/O 设备与控制器

设备分类

• 按传输单位：

  • 块设备：以数据块为单位（如磁盘，块大小 512B~4KB），支持 DMA 传输。

  • 字符设备：以字符为单位（如键盘、串口），采用中断驱动。

• 按共享性：

  • 独占设备：同一时间仅允许一个进程访问（如打印机）。

  • 虚拟设备：通过 SPOOLing 技术将独占设备虚拟为多逻辑设备（如虚拟打印机）。

设备控制器

设备控制器是 CPU 与 I/O 设备之间的接口，它接收从 CPU 发来的命令，并去控制 I/O 设备工作。

• 功能：接收 CPU 命令（如读/写），实现数据缓冲（解决速度不匹配），支持差错检测（如奇偶校验）。

• 组成：命令寄存器（CR）、内存地址寄存器（MAR）、数据寄存器（DR）、数据计数器（DC）。

I/O 通道

I/O 通道设备通道是一种特殊的执行 I/O 指令的处理机，引入目的是使一些原来由 CPU 处理的 I/O 任务转由通道来承担。

优点：①DMA 直接存储器存取 方式显著地减少了 CPU 的干预 。 ② 只需向 I/O 通道发送一条 I/O 指令，即可完成一组相关的读（或写）操作及有关控制。 ③ 可实现 CPU 、通道和 I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

• 类型：

  • 字节多路通道：按字节交叉服务低速设备（如终端），子通道共享主通道。

  • 数组多路通道：支持高速设备（如磁盘），一次传输一个数据块，效率高。

• 瓶颈解决：采用多通路 I/O 系统，增加设备到主机的通路数，避免单通道拥堵。

5.3 中断与设备驱动 ☆

中断处理层的主要工作 有：进行进程上下文的切换，对处理中断信号源进行测试，读取设备状态和修改进程状态等

中断处理程序的处理流程☆

1. 程序完成当前指令后测试是否有未响应的中断信号

2. 保护现场--被中断进程的 CPU 环境：硬件自动保存 PSW 和 PC，保存在中断保留区（栈），然后把被中断进程的 CPU 现场信息 即包括所有的 CPU 寄存器，如通用寄存器、段寄存器等内容 都压入中断栈中

3. 由处理机对各个中断源进行测试，以确定引起本次中断的 I/O 设备，并发送一应答信号给发出中断请求的进程，使之消除该中断请求信号

4. 然后将相应的设备中断处理程序的入口地址装入到程序计数器中，使处理机转向中断处理程序

5. 执行中断处理程序

6. 该程序首先从设备控制器中读出设备状态，以判别本次中断是正常完成中断，还是异常结束中断。随后返回或者继续处理。

7. 恢复现场：从栈中取出进程上下文，继续执行被中断程序。

设备驱动程序

• 功能：

  • 转换请求：将逻辑块号转换为物理地址（如磁盘块 → 柱面/盘面/扇区）。

  • 启动设备：向控制器发送命令（如启动磁盘读扇区3），处理 DMA 传输。

• 控制方式： ☆

  • 程序 I/O（轮询）：CPU 循环检测设备状态，效率极低（如早期打印机）。

  • 中断驱动：设备完成后发中断，CPU 仅处理数据（如键盘输入）。

  • DMA 方式：控制器直接读写内存，CPU 仅参与块传输开始/结束（如磁盘读写）。

  • I/O 通道控制方式：DMA 方式的发展，它可进一步减少 CPU 的干预，即把对 一个 数据块的读（或写）为单位的干预，减少为对 一组 数据块的读（或写）及有关的控制和管理为单位的干预。

5.4 设备无关性与用户层软件

应用程序独立于具体使用的物理设备。为了实现设备独立性而引入了 逻辑设备 和 物理设备 这两个概念。在应用程序中，使用逻辑设备名称来请求使用某类设备；而系统在实际执行时，还必须使用物理设备名称。设备独立性使得设备分配更灵活，易于实现 I/O 重定向。

逻辑设备映射

逻辑设备表（LUT）：记录逻辑设备名、物理设备号、驱动程序入口。

逻辑设备名	物理设备号（设备描述）	驱动程序入口
/dev/lp	7（激光打印机）	0x7000

设备独立性软件

功能：(1)执行所有设备的公有操作。① 对独立设备的分配与回收；② 将逻辑设备名映射为物理设备名，进一步可以找到相应物理设备的驱动程序；③ 对设备进行保护，禁止用户直接访问设备；④ 缓冲管理 ⑤ 差错控制 ⑥ 提供独立于设备的逻辑块

(2)向用户层 或文件层 软件提供统一接口

SPOOLing 技术（假脱机）

是一种计算机操作系统中的输入 / 输出（I/O）技术，用于将数据从低速设备（如打印机、磁带机）高效地传输到高速设备（如内存或磁盘），或反之。其核心思想是通过缓冲技术和多道程序设计，将独占设备模拟为共享设备，从而提高系统资源利用率和吞吐量。

• 组成：

  • 输入井/输出井：磁盘上的虚拟缓存区，模拟脱机输入/输出。

  • 输入/输出进程：负责数据在磁盘与设备间的传输（如打印进程将数据写入输出井）。

• 优点：

  • （1 ）提高了 I O 的速度，缓和了 CPU 与低速 I O 设备之间速度不匹配的矛盾。

  • （2 ）将独占设备改造为共享设备

  • （3 ）实现了虚拟设备功能 SPOOLing 系统实现了将独占设备变换为若干台对应的逻辑设备的功能。

5.5 缓冲区管理

缓冲类型

• 单缓冲：仅一个缓冲区，CPU 与设备交替使用（如键盘输入），效率低。

• 双缓冲：两个缓冲区交替填充/提取（如视频播放），提升并行性。

• 循环缓冲：多个缓冲区组成环形队列，分为空缓冲区（E）、满缓冲区（F）、工作缓冲区（C），适用于阵发性数据传输（如网络数据包接收）。

• 缓冲池：公共缓冲区，包含空缓冲队列（emq）、输入队列（inq）、输出队列（outq），支持多设备共享（如磁盘与打印机共享缓冲池）。

缓冲区的分配和回收

5.6 磁盘系统和磁盘调度

磁盘性能

• 寻道时间（Ts）：磁头移动到目标磁道的时间，公式：Ts = m×n + s（m=移动每一条磁道花费的时间，s=启动磁臂的时间，n 为磁头移动经过的磁道数）。

• 旋转延迟（Tr）：扇区旋转到磁头下的平均时间，公式：Tr = 1/(2r)（r 为转速）。

• 传输时间（Tt）：读写数据的时间，公式：Tt = b/(rN)（b 为数据量，N 为磁道字节数）。

调度算法对比 ☆

算法	核心逻辑	优缺点
FCFS	按请求顺序服务	公平但效率低，磁头来回移动（如请求序列：55→58→39→…）。
SSTF	优先处理距离当前磁道最近的请求	减少寻道时间，但可能导致“饥饿”（如频繁短距离请求阻塞长距离请求）。
SCAN	磁头双向扫描，优先处理移动方向上的请求（类似电梯）	平衡公平性与效率，避免饥饿，但可能延迟反向请求（如磁头向外时忽略向内请求）。
CSCAN	磁头单向扫描，到达终点后立即返回起点（循环扫描）	确保均匀处理，减少延迟差异，适合高密度磁盘。
LOOK	LOOK 算法对 SCAN 算法进行了改进，如果磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向，依此往复。
C-LOOK	C-LOOK 算法对 C-SCAN 算法进行了改进，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回,并且磁头只需要返回到有磁道访问请求的位置即可。

第六章 文件管理

6.1 文件系统基础

组成

• 数据项：最小逻辑单位，分为基本数据项（如学号、姓名）和组合数据项（如工资=基本工资+工龄工资）。

• 记录：相关数据项集合，描述对象属性（如学生记录包含学号、成绩）。

• 文件：有结构文件（记录集合）和无结构文件（字符流，如 UNIX 文件）。

文件属性与类型 属性：类型、长度、物理位置、创建时间等。

分类维度	类型
用途	系统文件（如内核）、用户文件（如文档）、库文件（如标准子例程）
数据形式	源文件（.c）、目标文件（.obj）、可执行文件（.exe）
存取控制	只执行文件、只读文件、读写文件
组织形式	普通文件、目录文件、特殊文件（I/O 设备）

文件系统功能：管理存储空间（分配/回收）、目录（按名存取）、文件 I/O 操作、文件共享与保护、提供接口（命令行/系统调用）。

文件操作

• 打开文件：将目录项读入内存，返回文件描述符（如 Linux 的open()）。

• 读写操作：定长记录通过偏移量直接访问，变长记录需遍历索引表。

• 关闭/删除：释放资源，删除目录项并回收存储空间。

6.2 文件物理和逻辑结构

逻辑结构类型

• 顺序文件：记录按时间或关键字排序，定长记录支持直接访问（如Ai = i×L），变长记录需累加长度查找。

• 索引文件：通过索引表（键-指针对）加速访问，适合变长记录，但增加存储开销。

• 索引顺序文件：分组索引（如每 50 条记录一组），检索效率为顺序文件的 √N 倍（如 10000 条记录，平均查找 100 次）。

文件的物理结构即文件的外存分配方式，是从系统的角度来看文件，从文件在物理介质上的存放。有三种外存分配方式。

连续分配（顺序分配）

连续分配要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，文件目录中为每个文件建立一个表项 其中记载文件的第一个数据块地址及文件长度 。

缺点是要求有连续存储空间并且必须事先知道文件的长度。

链接分配

链接文件： 采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为 链接文件。

1.隐式链接

在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件 第一个盘块 和最后一个盘块 的指针。而每个盘块中都含有一个指向下一个盘块的指针。

缺点在于：它只适合于顺序访问，对随机访问是极其低效的。为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个 簇 。

2.显式链接

用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。 整个磁盘仅设置一张文件分配表（FAT，File Allocation ）。在该表中，凡是属于某一文件的第一个盘块号，均作为文件地址被填入相应文件的 FCB 的“ 物理地址 ”字段中。与隐式链接的关键区别在于，指针被单独存放而不是和盘块一起。

缺点：不能支持高效的随机/直接存取，仅适合顺序存取，FAT 需占用较大的内存空间。

索引分配

单级索引分配

为每个文件分配一个索引块（表），再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。

支持直接访问，基于数据块分区能消除外部碎片。缺点是索引块占用外存空间较大，一个数据块不一定能容纳一个大文件的分区索引。

多级索引分配

当文件太大，其一级索引块太多时，应为这些索引块再建立一级索引，形成 两级索引分配方式。

假设每个盘块大小为 1KB ，每个盘块号占 4 个字节，则在一个索引块中可放 256 个文件物理块的盘块号。在两级索引时，最多可包含的存放文件的盘块的盘块号总数为 256*256=64K 个盘块号。可以得出：采用两级索引时，所允许的文件最大长度为 64MB 。

混合索引

每个文件的索引表为 13 个索引项。最前面 10 项直接登记存放文件信息的物理块号（直接寻址）如果文件大于 10 块，则利用第 11 项指向一个物理块，假设每个盘块大小为 4KB ，每个盘块号占 4 个字节，该块中最多可放 1K 个盘块号（一次间接寻址）。对于更大的文件还可利用第 12 和第 13 项作为二次和三次间接寻址。

6.3 文件存储空间管理

存储空间的基本分配单位是磁盘块。其分配方法与内存的分配有许多相似之处，即同样可采取连续分配方式或离散分配方式。

空闲分区表

空闲表法属于连续分配方式，它为每个文件分配适合于 可变大小分区的连续分配 方式 ，它为每个文件分配一块连续的存储空间，即 系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项 ，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。

对交换分区一般都采用连续分配方式。 对于文件系统，当文件较小 (14 个盘块） 时，仍采用连续分配方式，为文件分配相邻接的几个盘块； 当文件较大时，便采用离散分配方式。

空闲链表法

空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种。适合于非连续存储文件 。

空闲盘块链

当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。

空闲盘区链

分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。

为了提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。每个分区结点内容：起始盘块号、盘块数、指向下一个空闲盘区的指针。

位示图

利用二进制位 0 、 1 表示存储空间中存储块的使用状态。空闲分区 :0 ，已分配分区 :1 。磁盘上的所有盘块都有一个二进制位与之对应，由所有盘块所对应的位构成一个集合，称为位示图。 通常可用 m × n 个位数来构成位示图，并使 m ×n 等于磁盘的总块数，也可描述为一个二维数组 map。

分配：根据位示图进行盘块分配时，可分三步进行： (1) 顺序扫描位示图 ，从中找出一个或一组其值为 0”的二进制位 (2) 将所找到的一个或一组二进制位转换成与之相应的盘块号。 假定找到的其值为“ 0” 的二进制位位于位示图的第 i 行、第 j 列，则其相应的盘块号应按下式计算：b = n( i -1) + j (3) 修改位示图， 令 map[ i,j ]=1 。

回收： (1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为： i = \left\lfloor \frac{b - 1}{n} \right\rfloor + 1, \quad j = (b - 1)\mod n + 1

(2) 修改位示图。令 map[ i , j ] =0 。

占用空间小，找连续空闲分区方便，但不适合大磁盘。

成组链接法

将磁盘所有空闲盘块分组；设置_空闲盘块号栈_，存放当前可用的一组空闲盘块的盘块号(最多 100 个号)，和栈中尚有的空闲盘块总数 N；后一组的所有盘块号以及盘块总数登记在前一组的第一个盘块中……依次类推，组与组之间形成链接关系；最后一组少登记一个盘块号，多登记一个空闲盘块链的结束标志。

分配：1、首先检查空闲盘块号栈是否上锁（互斥访问），如未上锁，便从栈顶取出一空闲盘块号，将与它对应的盘块分配给用户，然后将栈顶指针下移一格。2、若该盘块号已是栈底，即 S.free(0) ，这是当前栈中最后一个可分配的盘块号。 3 、由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，应调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去 其中的有用数据已读入栈中 。4、然后，再分配一相应的缓冲区 作为该盘块的缓冲区 。5、最后，把栈中的空闲盘块数减 1 并返回。

回收：将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加 1 的操作。当栈中空闲盘块号数目已达到 100 时，表示栈已满，便将现有栈中的 100 个盘块号，记入新回收的盘块中，再将其盘块号作为新的栈底。

6.4 文件目录

对目录管理的要求如下：实现“按名存取”。 提高对目录的检索速度。文件共享。 允许文件重名。 文件控制块 FCB： 用于描述和控制文件的数据结构，是文件存在的标志，保存在文件目录中，一个 FCB 就是一个目录项。FCB 内容：基本信息、地址信息（卷、起始地址、文件长度）、访问控制信息、使用信息。FCB 可以将部分文件信息存储在索引节点中。（如 UNIX）从文件管理角度看，文件由 FCB 和文件体（文件本身）两部分组成。

文件目录： 文件控制块的有序集合。为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件。

目录结构

• 单级目录：所有文件在一张表中，简单但存在查找慢、重名冲突问题。

• 两级目录：主目录 MFD+用户目录 UFD。

多级目录（树型）

树形目录： 主目录被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点。系统中的每一个文件都有惟一的路径名。为每个进程设置一个当前目录 ，又称为 工作目录 进程对各文件的访问都相对于当前目录 而进行。

• 绝对路径：从根目录开始（如/home/user/file.txt）。

• 相对路径：从当前目录开始（如./file.txt）。

目录查询

线性搜索法

哈希法

建立了一张 Hash 索引文件目录，系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找。

6.5 文件共享与访问控制

文件共享方式

实质：从不同位置访问同一个文件。 核心步骤： 找到文件的目录项； 读取文件在外存的起始地址。

1. 链接目录项共享（软链接原理）

• 实现机制：

  • 在文件目录项中设置链接指针，指向共享文件的目录项。

  • 访问时通过链接指针定位到共享文件目录项，读取起始位置等信息。

• 计数管理：

  • 新增共享用户（进程）时，共享文件目录项的共享计数+1；

  • 用户撤销共享时，共享计数-1；

  • 删除条件：仅当共享用户数为 1 时，允许删除共享文件。

2. 索引结点共享（硬链接）

• 多个目录项指向同一索引结点（inode），通过count字段记录链接数。

• 删除条件：仅当count=0时，才真正删除文件。

• Linux 中执行ln f1 f2命令，创建硬链接，使f1与f2共享同一 inode。

  

3. 符号链共享（软链接）

• 创建一个LINK 类型的独立文件（如命名为 F），写入目标文件的路径名，并存储在共享方目录中。 如 Linux 中执行ln -s f1 f3命令创建软链接。

4.URL 共享 ：访问时需解析路径名，通过路径找到目标文件

⭐硬链接和软链接的区别

在 Linux/类 Unix 系统上，文件链接（File Link）是一种特殊的文件类型，可以在文件系统中指向另一个文件。常见的文件链接类型有两种：

1、硬链接（Hard Link）

• 在 Linux/类 Unix 文件系统中，每个文件和目录都有一个唯一的索引节点（inode）号，用来标识该文件或目录。硬链接通过 inode 节点号建立连接，硬链接和源文件的 inode 节点号相同，两者对文件系统来说是完全平等的（可以看作是互为硬链接，源头是同一份文件），删除其中任何一个对另外一个没有影响，可以通过给文件设置硬链接文件来防止重要文件被误删。

• 只有删除了源文件和所有对应的硬链接文件，该文件才会被真正删除。

• 硬链接具有一些限制，不能对目录以及不存在的文件创建硬链接，并且，硬链接也不能跨越文件系统。

• ln 命令用于创建硬链接。

• 每个文件系统都有自己的独立 inode 表，且每个 inode 表只维护该文件系统内的 inode。如果在不同的文件系统之间创建硬链接，可能会导致 inode 节点号冲突的问题，即目标文件的 inode 节点号已经在该文件系统中被使用。

2、软链接（Symbolic Link 或 Symlink）

• 软链接和源文件的 inode 节点号不同，而是指向一个文件路径。

• 源文件删除后，软链接依然存在，但是指向的是一个无效的文件路径。

• 软连接类似于 Windows 系统中的快捷方式。

• 不同于硬链接，可以对目录或者不存在的文件创建软链接，并且，软链接可以跨越文件系统。

• ln -s 命令用于创建软链接。

文件共享安全

文件共享的有效控制涉及两个方面：同时存取 ，存取权限

文件保护

系统为所有对象设置一个允许进程实施操作的操作集 任何对对象的操作必须符合操作集中的规定 防止未授权进程访问对象 。

6.5 Linux 文件系统

“一切皆是文件”。Unix/Linux 中允许不同的文件系统共存，如 ext2, ext3, vfat 等。通过统一的文件操作 API/ 系统调用即可对系统中的任意文件进行操作而无需考虑其所在的具体文件系统格式

结构

虚拟文件系统 VFS 是 Linux 内核中的一个软件层，对内实现文件系统的抽象，允许不同的文件系统共存，对外向应 用程序提供统一的文件系统接口，VFS 定义了所有文件系统都支持的基本、抽象接口和数据结构。

文件在磁盘中的表现形式

超级块 ：用于存储文件系统的控制信息的数据结构。描述文件系统的状态、文件系统类型、大小、区块数、索引节点数等，存放 于磁盘的特定扇区中。 索引节点：用于存储文件的元数据（文件的基本信息的一个数据结构，包含诸如文件的大小、拥有者、创建时间、数据块 目录块位置等信息。目录块 ：存放目录文件的内容。数据块 ：存放非目录文件的内容

目录文件中每个目录项由两部分组成：所包含文件的文件名，文件名对应的索引节点（ inode ）号 ls i 命令列出目录文件内容，即文件名和索引节点号

文件在内核的表现形式

内核使用的三种表来表示进程使用的文件

文件描述符表：files_struct 结构。每个进程用一个 files_struct 结构来记录其文件使用情况。

文件表：file 结构。主要用于建立进程和磁盘上的文件的对应关系。文件表和物理文件的关系类似进程和程序的关系，一个物理文件可能存在多个对应的文件表（打开多次）。

文件描述符：对于内核而言，所有打开文件都用文件描述符标识。

目录项对象：dentry 结构。方便查找文件的索引节点。一个路径的各个组成部分，不管是目录还是普通的文件，都是一个目录项对象

索引节点表：inode 结构。文件系统中的每个物理文件由一个索引节点表（索引节点对象）描述，且只能由一个索引节点对象描述。 索引节点指向物理文件的具体存储位置，对于物理文件是唯一的，并且随物理文件的存在而存在。

第七章 UNIX/Linux 系统入门

7.1 Linux 简介

Linux 是一套免费使用和自由传播的类 Unix 操作系统 是一个基于 POSIX 和 UNIX 的 多用户 、 多任务 、 支持多线程和多 CPU 的操作系统，继承了 Unix 以网络为核心的设计思想，是一个性能稳定的多用户网络操作系统 。

Linux 操作系统由 Linux 内核， LinuxShell， Linux 文件系统，Linux 应用程序 四大主要部分组成。 Shell 是系统的 用户界面 提供了用户与 内核 进行交互操作的一种 接口，实际上 Shell 是一个命令 解释器 ，它 解释 由用户输入的 命令 并且把它们 送到内核 。Linux 系统的 Shell 是命令语言、命令 解释程序 及 程序设计语言 的统称。bash 是 shell 的一个具体实现。

Linux 核心特征：多用户、多进程。通过账户管理、权限管理、进程管理来实现。

Linux 的发行版本实质在于 Linux 核心加上外围的实用程序组成的一个大软件包 ，如 RedHat,Ubuntu。

Linux 常用基础命令整理表

命令分类	命令	核心功能	常用选项/参数	补充说明
🌟 用户管理	useradd [选项] 用户名	添加新用户	-c：注释信息 -d：指定主目录 -g：初始组 -G：附加组 -m：创建主目录 -s：指定shell -u：指定UID
	usermod [选项] 用户名	修改用户属性	同 useradd 核心选项（-c/-d/-g/-G/-s/-u）
	userdel [选项] 用户名	删除用户	-r：同时删除主目录及文件
	passwd [选项] [用户名]	设置/修改用户密码	-d：删除密码 -l：锁定账户 -u：解锁账户 -e：强制下次登录改密码	无用户名时修改当前用户密码
🌟 组管理	groupadd [选项] 组名	添加新用户组	-g：指定GID
	groupdel 组名	删除用户组	—	仅能删除无用户关联的空组
🌟 登录/会话	login [用户名]	登录系统	—	终端环境下使用
	logout	退出登录shell	—	仅适用于登录shell，普通shell用exit
	exit	退出当前shell会话	—	等价快捷键：Ctrl+D
	su [选项] [用户名]	切换用户	-/-l：登录式切换（重置环境） -c "命令"：执行单次命令 -m/-p：保留环境 -s：指定shell	su root 临时切换，su - root 完全切换
	pkill -KILL -t 终端名	强制退出指定终端会话	—	需root权限，例：pkill -KILL -t pts/0
🌟 基础导航	date	显示当前日期时间	—	可加参数格式化输出（如 date +%Y-%m-%d）
	who	显示当前登录用户信息	—	含用户名、终端、登录时间
	pwd	显示当前工作目录	—	绝对路径输出
	cd	切换工作目录	-：返回上次目录 ~：返回主目录 ..：返回上级目录	无参数时默认返回主目录
🌟 目录/文件操作	ls	列出目录内容	-l：长格式（权限/大小等） -a：显示隐藏文件 -h：易读大小 -R：递归显示 -t：按修改时间排序
	mkdir	创建目录	-p：递归创建多级目录 -m 权限：指定目录权限（如 mkdir -m 755 test）
	rmdir	删除空目录	-p：递归删除空父目录	仅能删除空目录，非空用 rm -r
	rm	删除文件/目录	-r：递归删除目录 -f：强制删除（无提示） -i：删除前确认	慎用 rm -rf（强制递归删除）
	cp	复制文件/目录	-r：递归复制目录 -i：覆盖前确认 -v：显示进度 -p：保留文件属性
	mv	移动/重命名文件/目录	-i：覆盖前确认 -v：显示进度	同目录下移动=重命名
	ln	创建链接文件	-s：创建软链接 -f：强制覆盖已有链接	无 -s 为硬链接
🌟 文件查看	cat	显示文件内容	-n：显示行号 -E：显示行结束符（$）	适合小文件，大文件用 more/less
	more	分页显示文件内容	—	仅支持向后翻页
	less	分页显示文件内容	—	支持前后翻页、搜索（/关键词）
	head	显示文件开头内容	-n 行数：指定显示行数（默认前10行）	head -5 test.txt 显示前5行
	tail	显示文件结尾内容	-n 行数：指定行数（默认后10行） -f：实时跟踪文件变化	tail -f log.txt 监控日志
🌟 打印管理	lp	打印文件	-d 打印机名：指定打印机
	lpstat	显示打印队列状态	-t：显示所有打印机/任务详情
	cancel	取消打印作业	—	需指定作业号/打印机名
	lpr	提交打印任务	-P 打印机名：指定打印机
	lpq	显示打印队列	-P 打印机名：指定查看的队列
	lprm	删除打印队列任务	—
🌟 权限管理	chmod	修改文件/目录权限	-R：递归修改 u/g/o：用户/组/其他 +r/-r：添加/移除读权限 +w/-w：添加/移除写权限 +x/-x：添加/移除执行权限	也可直接用数字（如 chmod 755 test.sh）
	chown	修改文件所有者/组	-R：递归修改 所有者:组：指定新属主和属组（如 chown root:root test.txt）	需root权限
	chgrp	修改文件所属组	-R：递归修改	需root/文件所有者权限
🌟 进程管理	fg	后台作业移到前台	—	配合 jobs 查看后台作业号
	kill	终止进程	-9：强制终止（SIGKILL） -15：正常终止（默认）	需指定进程PID（如 kill -9 12345）
	ps	显示进程状态	-ef：所有进程详细信息 -aux：所有用户进程+资源占用	`ps -ef

7.2 进程运行与监控

进程的启动

创建进程

▪ 在 shell 中执行命令或可执行文件：由 shell 进程调用 fork 函数创建子进程 ▪ 在代码中（已经存在的进程中）调用 fork 函数创建子进程

Linux 系统中进程 0( PID=0 ）是由内核创建，其他所有进程都是由父进程调用 fork 函数所创建的 ▪ Linux 系统中进程 0 在创建子进程 init 进程（ PID=1 ）后，进程 0 就转为交换进程或空闲进程 ▪ 进程 1 init 进程是系统中其他所有进程的共同祖先

fork 函数

子进程是父进程的副本，子进程复制 拷贝父进程的 PCB 、用户空间（数据段、堆和栈），父子进程共享正文段（只读）。 父进程继续执行 fork 函数调用之后的代码。子进程也从 fork 函数调用之后的代码开始执行。 为了提高效率 fork 后并不立即复制父进程数据段 、 堆和栈 采用了写时复制机制 Copy On Write，即当父子进程任意之一要修改数据段、堆、栈时，进行复制操作，并且仅复制修改区域

fork 使用场景：1、父进程希望复制自己（共享代码，复制数据空间），但父子进程执行相同代码中的不同分支，如网络并发服务器中，父进程等待客户端的服务请求。当请求达到，父进程调用 fork 创建子进程处理该请求，而父进程继续等待下一个服务请求

2、父子进程执行不同的可执行文件（父子进程具有完全不同的代码段和数据空间），子进程从 fork 返回后，立即调用 exec 类函数执行另外一个可执行文件

vfork 用于创建新进程，而该新进程的目的是执行另外一个可执行文件。由于新程序将有自己的地址空间，因此子进程并不复制父进 程的地址空间。子进程在调用 exec 或 exit 之前，在父进程的地址空间中运行，vfork 函数保证子进程先执行，在它调用 exec 或者 exit 之后，父进程才会继续被调度执行（父进程处于不可中断睡眠状态）

环境变量

环境变量一般是指操作系统中指定操作系统运行环境的一些参数。它相当于一个指针，想要查看变量的值，需要加上$。 每个进程都有一张环境变量表，环境变量表是一个字符指针数组每个指针指向一个以‘ 0’ 结尾的环境字符串。Main 函数的第三个参数就是环境表地址。通过全局的环境指针（environ）可以直接访问环境变量表（字符串数组）头文件 unistd.h extern char **environ; 环境变量字符串形式为“name=value”，name 是环境变量名称，value 为环境变量赋值

设置环境变量的三种方法：putenv，setenv，unsetenv

进程的运行控制

六个 exec 函数

进程调用 exec 系列函数在进程中加载执行另外一个可执行文件， exec 系列函数替换了当前进程（执行该函数的进程）的正文段、数据段、堆和栈（来源于加载的可执行文件），但并不修改 PCB.会让进程从可执行文件的 main 函数开始重新执行。

l：表示 list，每个命令行参数都说明为一个单独的参数 v：表示 vector，命令行参数放在数组中 e：表示由函数调用者提供环境变量表 p：表示通过环境变量 PATH 来指定路径，查找可执行文件

进程的监测

终止

1. 正常终止：从 main 函数中执行 return 返回。在任意代码中调用 exit 函数或 _exit 函数。

2. 异常终止：在任意代码中调用 abort 函数。接收到终止信号。

3. exit 和 return 的区别： exit 是一个函数，有参数。 exit 执行完后把控制权交给系统。 return 是函数执行完后的返回。 return 执行完后把控制权交给调用函数。 exit 和 abort 的区别：exit 是正常终止进程， abort 是异常终止。

获知子进程状态改变

主动获取：调用 wait 或 waitpid 函数等待子进程状态信息改变，并获取其状态信息。直到有子进程进入终止或暂停状态，则 wait 函数会立即返回。 异步通知：当一个进程发生特定的状态变化（进程终止、暂停以及恢复）时，内核向其父进程发送 SIGCHLD 信号。父进程可以选择忽略该信号，也可以对信号进行处理（默认为忽略）

7.3 操作系统接口与应用开发

三种接口：

1. 命令接口 方便用户直接或间接控制自己的作业。分为 联机用户接口 交互式方式运行的命令与脱机用户接口 批处理用户接口

2. 程序接口 为用户程序在执行中访问系统资源而设置 是用户程序取得操作系统服务的唯一途径 。它由一组系统调用组成 。 每一个系统调用都是一个能完成特定功能的子程序 。

3. 图形接口 采用了图形化的操作界面 用非常容易识别的各种图标来将系统的各项功能 、 各种应用程序和文件直观逼真地表示出来 。

系统调用

各种版本的 UNIX 系统都提供了定义明确、数量有限、可直接进入内核的入口点，这些入口点被称为系统调用（ system calls）

系统调用在用户空间进程和硬件设备之间添加了一个中间层，该层的主要作用有两个 1.为用户空间提供了一种硬件的抽象界面，例如，当需要读文件时，应用程序可以不管磁盘类型和介质，甚至不用去管文件所在的文件系统到底是哪种类型； 2.系统调用保证了系统的稳定和安全。

Linux 系统调用通过 C 库（如 glibc）向应用程序暴露，而非直接提供裸接口。 C 库实现了完整的 UNIX/Linux API，包括标准的 C 库函数和系统调用封装。

对于系统调用，控制是由原来的用户态转换为系统态，这是借助于中断和陷入机制来完成的，在该机制中包括中断和陷入硬件机构及中断与陷入处理程序两部分。

• 设备管理：完成设备（输入输出设备和外部存储设备等）的请求或释放，以及设备启动等功能。

• 文件管理：完成文件的读、写、创建及删除等功能。

• 进程管理：进程的创建、撤销、阻塞、唤醒，进程间的通信等功能。

• 内存管理：完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

⭐用户态切换到内核态的 3 种方式

1. 系统调用（Trap）：这是最主要的方式，是应用程序主动发起的。比如，当我们的程序需要读取一个文件或者发送网络数据时，它无法直接操作磁盘或网卡，就必须调用操作系统提供的接口（如 read(),send()), 这会触发一次从用户态到内核态的切换。

2. 中断（Interrupt）：这是被动的，由外部硬件设备触发。比如，当硬盘完成了数据读取，会向 CPU 发送一个中断信号，CPU 会暂停当前用户态的程序，切换到内核态去处理这个中断。

3. 异常（Exception）：这也是被动的，由程序自身错误引起。比如，我们的代码执行了一个除以零的操作，或者访问了一个非法的内存地址（缺页异常），CPU 会捕获这个异常，并切换到内核态去处理它。 在系统的处理上，中断和异常类似，都是通过中断向量表来找到相应的处理程序进行处理。区别在于，中断来自处理器外部，不是由任何一条专门的指令造成，而异常是执行当前指令的结果。