## 简介

本文用于记录软考中，与编程算法有关的题目。

如有想要记录的题目，欢迎评论补充！

> 关注公众号“**月上老狗**”，发送“**软件设计师**”，获取历年软件设计师软考真题。
> 
> ![image](https://images.oldmoon.top/images/dingdangdog/dingdangdog-1680842466920.jpg)



## 算法策略

1. 分治策略（`Divide and Conquer`）：（最常见的二分法）分治策略将原问题分解成若干个规模较小且结构与原问题相似的子问题，递归地解决这些子问题，并将子问题的解合并起来得到原问题的解。对应的排序算法：归并排序和快速排序。
2. 贪心策略（`Greedy Strategy`）：贪心策略在每一步都选择当前状态下的最优解，希望通过局部最优解的累积达到全局最优解。
3. 动态规划（`Dynamic Programming`）：动态规划通过将原问题分解成若干个子问题，并以自底向上或自顶向下的方式求解子问题，从而得到原问题的最优解。
4. 回溯法（`Backtracking`）：回溯法是一种通过在问题的所有可能解空间中搜索解，并逐步构建解的方法，直到找到满足约束条件的解或者确定无解为止。
5. 线性规划（`Linear Programming`）：线性规划是一种通过线性函数构建模型，并通过线性不等式约束找到最优解的方法。
6. 模拟退火（`Simulated Annealing`）：模拟退火是一种通过模拟物理退火过程来寻找最优解的随机搜索算法，通过接受较差的解以避免陷入局部最优解。
7. 遗传算法（`Genetic Algorithm`）：遗传算法是一种受自然界进化过程启发的优化算法，通过模拟生物进化过程中的遗传、变异、选择等操作来寻找最优解。

## 排序算法

1. **有哪些排序算法？**

> 参考：【[常见排序算法原理及其时间复杂度](https://oldmoon.top/post/303)】

2. **现需要对一个基本有序的数组进行排序，此时最适宜采用什么排序算法？时间复杂度是多少？**

> 对于一个基本有序的数组进行排序，最适合使用的排序算法是 **插入排序**（`Insertion Sort`）。插入排序在处理基本有序的数组时非常高效，其时间复杂度可以接近 `O(n)`。
> 
> 插入排序的优势：
> 1. 适应性强：插入排序在处理已经基本有序的数据时，性能非常好，接近线性时间复杂度 `O(n)`。
> 2. 稳定性：插入排序是稳定的排序算法，不会改变相同元素的相对顺序。
> 3. 原地排序：插入排序是一种原地排序算法，只需要常数级别的额外空间 `O(1)`。
> 
> 插入排序的工作原理：插入排序通过构建一个有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体步骤如下：
> 1. 从第一个元素开始，该元素可以认为已经被排序。
> 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
> 3. 如果已经排序的元素大于新元素，则将该元素移到下一位置。
> 4. 重复步骤 `3`，直到找到已排序的元素小于或者等于新元素的位置。
> 5. 将新元素插入到该位置后。
> 6. 重复步骤 `2-5`。
> 
> 时间复杂度分析：
> - 最坏情况下：当数组是逆序时，插入排序需要进行大量的移动操作，时间复杂度为 `O(n^2)`。
> - 最优情况下：当数组已经完全有序时，插入排序只需进行一次比较，时间复杂度为 `O(n)`。
> - 平均情况下：一般情况下时间复杂度为 `O(n^2)`，但对于基本有序的数组，插入排序仍然能够表现出接近 `O(n)` 的时间复杂度。

## 二叉树

1. 假设某消息中只包含7个字符`{a,b,c,d,e,f,g}`，这7个字符在消息中出现的次数为`{5，24，8，17，34，4，13}`，利用哈夫曼树(最优二叉树)为该消息中的字符构造符合前缀編码要求的不等长编码。各字符的编码长度分别为( )。 

- A. `a:4,b:2,c:3,d:3,e:2,f:4,g:3`
- B. `a:6,b:2,c:5,d:3,e:1,f:6,g:4`
- C. `a:3,b3:,c:3,d:3,e:3,f:2,g:3`
- D. `a:2,b:6,c:3,d:5,e:6,f:1,g:4`

> 解析：由题意可知各字符及其出现的频率：`a:5, b:24, c:8, d:17, e:34, f:4, g:13`，哈夫曼树(最优二叉树)是优先编码出现最多的字符，所以由大到小一次是 `e、b、d、g、c、a、f`，最小的两个字符为同一个节点分支，所以分别是 `e:1,b:2,d:3,g:4,c:5,a:6,f:6`，所以 *选择B*。

2. 设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含k个结点时，其二叉链表结点中必有( )个空的孩子指针。

> 解析：在二叉树中，每个节点最多有两个孩子，因此每个节点有两个孩子指针。在二叉链表表示法中，如果一个节点没有左孩子或右孩子，那么对应的孩子指针就为空。
>
> 对于包含k个节点的二叉树，总共有2k个孩子指针。然而，除了根节点外，每个节点都是其父节点的一个孩子，因此有k-1个孩子指针被使用。所以，二叉链表节点中必有2k - (k - 1) = **k + 1**个空的孩子指针。

3. 根据其使用频率为其构造哈夫曼编码。以下编码方案中（ ？）是不可能的。

> 哈夫曼编码是一种无损数据压缩算法，通过构建一棵二叉树，将频率较高的字符用较短的编码表示，频率较低的字符用较长的编码表示，从而实现数据的压缩。哈夫曼编码的关键特性是前缀码：任何编码都不是其他编码的前缀，这确保了解码的唯一性和正确性。
> 判断一组数据是否哈夫曼编码的步骤：
> 1. 检查前缀属性：哈夫曼编码中，任何一个代码都不是另一个代码的前缀。
> 2. 解码数据：使用哈夫曼树（解码树）从左到右逐位解码数据。如果解码过程中遇到无法识别的代码，则该数据不是哈夫曼编码。
> 3. 检查唯一性：哈夫曼编码中，每个符号都有一个唯一的代码。
如果解码过程中遇到相同的代码对应不同的符号，则该数据不是哈夫曼编码。

|选项|分析|
|--|--|
|A. `{111, 110, 101, 100, 0}`|正确。|
|B. `{0000, 0001, 001, 01, 1}`|正确。|
|C. `{11, 10, 01, 001, 000}`|正确。|
|D. `{11, 10, 011, 010, 000}`|不正确。因为哈夫曼编码可以认为是由哈夫曼树得来，而哈夫曼树的构造过程是自底向上的，最外层叶子节点必然是偶数个，但D选项最外层叶子节点是`011/010/000`三个，所以D不正确。|

4. Kruskal算法求解最小生成树，用的是什么算法策略？最小生成树是什么？Kruskal算法又是什么？

> 最小生成树（Minimum Spanning Tree，简称MST）是一棵包含图中所有顶点的树，并且具有最小的总权值。在一个连通的带权无向图中，其最小生成树是一棵权值和最小的生成树。
>
> Kruskal算法是一种用于求解最小生成树的贪心算法。其基本思想是按边的权值从小到大选择边，并保证选择的边不构成环，直到选出了n-1条边为止（n为图中顶点的个数）。Kruskal算法的具体步骤如下：
> 1. 将图中的所有边按权值从小到大进行排序。
> 2. 依次选择排序后的边，如果该边不与已选择的边构成环，则将其加入最小生成树的集合中。
> 3. 直到最小生成树中的边数达到n-1为止，其中n为图中顶点的个数。

权值：使用 Kruskal 求得的最小生成树就是连接所有顶点权值最小的通路，权值就是通路上的值之和。

## 加密算法

0. 常见加密算法的加密策略：

- AES（`Advanced Encryption Standard`）：加密策略：对称加密算法，使用相同的密钥进行加密和解密。支持128位、192位和256位密钥长度。运作方式：将明文分块，每个块与密钥进行混淆运算，反复执行多轮的代换和置换操作，最终生成密文。
- RSA（`Rivest-Shamir-Adleman`）：加密策略：非对称加密算法，使用一对公钥和私钥。运作方式：发送方使用接收方的公钥对数据进行加密，接收方使用自己的私钥对数据进行解密。RSA算法基于数论中的大数分解问题，依赖于两个大素数的乘积难以分解的特性。
- ECC（`Elliptic Curve Cryptography`）：加密策略：非对称加密算法，利用椭圆曲线上的离散对数问题来实现加密。优点：相比RSA等算法，ECC在相同的安全强度下使用的密钥长度更短，计算量更小，适合于资源受限的环境。
- MD5（`Message Digest Algorithm 5`）：加密策略：哈希算法，将任意长度的输入转换为128位的输出。特点：MD5是一种不可逆的哈希算法，相同的输入会产生相同的输出，不同的输入产生不同的输出，但是不能从输出推导出输入。
- SHA-256（`Secure Hash Algorithm 256位`）：加密策略：哈希算法，将任意长度的输入转换为256位的输出。特点：SHA-256是一种安全性更高的哈希算法，相比MD5更难以碰撞，用于验证数据的完整性和生成数字签名等场景。

1. 以下加密算法中适合对大量的明文消息进行加密传输的是( )。 

| 选项 | 分析 |
| -------- | ------------------------------------------------------------ |
| A. RSA | RSA是一种**非对称加密算法**，用于加密和数字签名。 它使用公钥和私钥配对，适用于安全通信、数字签名和密钥交换。 |
| B. SHA-1 | SHA-1也是一种**信息摘要算法**，用于确保数据完整性。 它产生160位的散列值，目前仍然安全，但不推荐使用，因为存在更安全的替代算法。 **注意**：SHA-1已被证实存在碰撞漏洞，不再被广泛推荐使用。 |
| C. MD5 | MD5是一种**信息摘要算法**，用于确保信息传输的完整性。 它将任意长度的输入转换为128位（16字节）的散列值，通常用于校验文件完整性或密码存储。 **注意**：MD5已被攻破，不适合用于安全性认证，如SSL公开密钥认证或数字签名。 |
| D. RC5 | 正确。RC5术语对称加密算法。适合对大量明文消息进行加密传输的是**对称加密算法**。 其中，高度安全且常用的对称加密算法之一是AES。 |

2. 假定用户A、B分别在`I1`和`I2`两个CA处取得了各自的证书，下面( )是A、B互信的必要条件 

| 选项 | 分析 |
| --------------------- | ------------------------------------------------------------ |
| A. A、B互换私钥 | 正确。 在公钥基础设施（PKI）中，用户A和B分别在证书颁发机构（CA）`I1`和`I2`处取得了各自的证书。 这些证书包含了用户的公钥和一些身份信息，并由CA进行签名。 为了实现A和B的互信，他们需要交换各自的公钥，而不是私钥。私钥应该始终保持私密，不应该与任何人共享。 同时，CA的公钥需要被广泛分发，以便任何人都可以验证由CA签名的证书。 但是，CA的私钥也应该保持私密，不应该与任何人共享。 |
| B. A、B互换公钥 | |
| C. `I1`、`I2`互换私钥 | |
| D. `I1`、`I2`互换公钥 | |

软考真题1：算法相关题目

## 总结

前面的几个章节，我们学习了操作系统相关的众多考点，这里给大家整理一下这些考点的清单：

|考点|考题类型|分值|出现概率|文章|
|----|----|--|--|------|
|操作系统概念|理论|1|低|软考知识点10|
|进程|理论|1|低|软考知识点10|
|线程|理论|1|低|软考知识点10|
|进程调度模型|理论、计算|1-2|中|软考知识点11|
|PV操作|理论|1|中|软考知识点11|
|PV模型与信号量|理论、计算|1-3|高|软考知识点11|
|死锁|理论、计算|1|低|软考知识点12|
|进程资源图|理论|1|低|软考知识点12|
|存储方式分类|理论|1|低|软考知识点13|
|段式存储|理论、计算|1|低|软考知识点13|
|页式存储|理论、计算|1-2|中|软考知识点13|
|磁盘的组成|理论|1|低|软考知识点14|
|磁盘读取时间|理论、计算|1-2|中|软考知识点14|
|磁盘读取方式（移臂调度）|理论、计算|1-2|中|软考知识点14|
|IO管理软件分层|理论|1|中|软考知识点15|
|文件相关概念|理论|1|中|软考知识点15|
|文件索引分层|理论、计算|1-2|中|软考知识点15|
|作业管理|理论|1|低|未讲到的其他知识|

同学们可以参考本表格进行针对性学习。

> 关注公众号“**月上老狗**”，发送“**软件设计师**”，获取历年软件设计师软考真题。
> 
> ![image](https://images.oldmoon.top/images/dingdangdog/dingdangdog-1680842466920.jpg)

## 声明

本表格仅是个人总结内容，不保证与考试内容完全相符！

软考知识点总结2：操作系统相关知识

## 简介

今天主要介绍一下IO管理软件和文件管理相关知识，因为IO管理软件这个知识点很小，所以在这里一并介绍。

文件管理相关的知识考点较为分散，一般都是概念理解型题目，注意理解即可，主要考点有：
1. 文件概念；
2. 树形结构（相对路径、绝对路径）；
3. 位示图；
4. 索引文件。

> 关注公众号“**月上老狗**”，发送“**软件设计师**”，获取历年软件设计师软考真题。
> 
> ![image](https://images.oldmoon.top/images/dingdangdog/dingdangdog-1680842466920.jpg)



## IO管理软件

IO管理软件是操作系统的重要组成部分，主要负责管理计算机系统中的输入输出设备。常见的考点包括IO管理的基本概念、分层结构及每个层次的具体作用。以下是IO管理软件的分层结构及每个层次的作用：
- 用户层（`User Level`）
- 设备独立性层（`Device-Independent Software Layer`）
- 设备驱动程序层（`Device Drivers Layer`）
- 中断处理层（`Interrupt Handlers Layer`）
- 硬件层（`Hardware Layer`）

### 用户层

用户层是应用程序和操作系统交互的层次。应用程序通过系统调用来请求IO操作，向操作系统提交IO请求，并接收IO操作完成后的数据。用户层的主要工作：
1. 提供用户接口，使用户程序能够请求IO操作。
2. 处理高层次的IO操作，如文件读写、网络通信等。

### 设备独立性层

设备独立性层提供设备无关的IO操作接口，使应用程序无需关心具体的设备细节。负责实现设备独立的功能，如缓冲区管理、错误处理和设备分配。设备独立性层的主要工作：
1. 设备分配：管理设备的分配和释放，确保设备的合理使用。
2. 缓冲区管理：管理IO缓冲区，确保数据在设备和内存之间的有效传输。
3. 错误处理：处理IO操作中的错误，提供统一的错误报告机制。

### 设备驱动程序层

设备驱动程序是设备无关性层和硬件层之间的桥梁，负责实现设备特定的操作。直接与硬件设备进行交互，执行具体的IO操作。设备驱动程序层的主要工作：
1. 初始化设备：在系统启动时对设备进行初始化，使其进入可用状态。
2. 执行IO操作：实现设备特定的读写操作，将高层次的IO请求转换为设备特定的命令。
3. 中断处理：处理设备发出的中断信号，通知操作系统IO操作的完成情况。

### 中断处理层
中断处理层负责处理来自硬件设备的中断请求，确保系统及时响应设备的状态变化。中断处理程序在设备操作完成后被触发，负责处理和清理中断。中断处理层的主要工作：
1. 保存上下文：在处理中断时保存当前的CPU状态，以便中断处理完成后恢复。
2. 处理中断：根据中断类型执行相应的处理操作，如读取数据、更新状态等。
3. 恢复上下文：中断处理完成后恢复CPU状态，继续执行被中断的程序。

### 硬件层

硬件层是物理设备本身，负责实际的数据传输和控制操作。包括各种输入输出设备，如磁盘、打印机、网络接口等。硬件层的主要工作：
1. 设备控制：硬件层执行具体的控制操作，如读写磁盘、发送网络数据等。
2. 数据传输：实现数据在设备和系统之间的物理传输。

## 文件管理

### 文件的概念

文件是数据集合的逻辑单元，是计算机存储信息的基本单位。每个文件都有一个文件名和文件属性，属性包括文件类型、大小、创建时间、修改时间、权限等。

> 拓展：文件可以类比现实世界的书籍、纸张、文件等信息集合，这些信息在计算机中，可以统称为“文件”。

### 树形结构

文件系统通常采用树形目录结构，以根目录为起点，向下扩展为多个子目录和文件。树形结构的文件地址表示方式，一般有两种：
- 相对路径：从当前工作目录出发，指向目标文件或目录的路径。
- 绝对路径：从根目录出发，完整地描述文件或目录的路径。

例题：以Linux系统为例，在当前目录为 `/home/user` 的情况下，文件 `docs/report.txt` 的相对路径为 `docs/report.txt`，绝对路径为 `/home/user/docs/report.txt`。

> 拓展：在Linux系统中，一个系统一般只有一个根目录：`/`，但Windows系统略有不同，因为Windows系统中的文件管理默认是分区的，也就是常见的 `C / D / E` 这些盘符，根目录也就有了多个，即 `C / D / E` 等。 

### 位示图

位示图是一种空间管理方法，利用位图来记录磁盘块的使用情况，其中“位”可以认为是“比特位”。每个磁盘块对应位图中的一位，1 表示已使用，0 表示空闲。

位示图中还有一个“字”的概念，假设一个字有8个比特位，即一个字可以表示8个磁盘块是否可以使用。

注意：“字”一般默认从 1 开始编号，而“位”一般默认从 0 开始编号。

考试中，可能会告诉你一个“字”的位长，然后给出一些磁盘块序号，从而求取其位置在第几个字的第几位，总而言之也是简单的数学计算，注意审题即可。

### 索引文件

索引文件通过索引表来管理文件，索引表记录文件中每个逻辑块对应的物理块位置。索引表可以是单级索引、多级索引或组合索引。

#### 多级索引

多级索引（`Multilevel Indexing`）是一种分层次管理文件数据块的方法。一级索引表记录指向二级索引表的指针，二级索引表记录指向三级索引表的指针，依此类推，直到最后一级索引表记录指向实际数据块的指针。

假设一个文件系统采用多级索引方式来存储文件，索引表的结构如下：

1. 一级索引表（一级指针）：包含指向二级索引表的指针，每个指针指向一个完整的二级索引表。一级索引表的大小决定了可以有多少个二级索引表。
2. 二级索引表（二级指针）：包含指向三级索引表的指针，每个指针指向一个完整的三级索引表。二级索引表的大小决定了可以有多少个三级索引表。
3. 三级索引表（三级指针）：包含指向实际数据块的指针，每个指针指向一个完整的数据块。三级索引表的大小决定了可以管理多少个数据块。

示例：假设每个索引表最多可以包含 256 个指针，一个数据块的大小是 4 KB。我们有一个大文件需要多级索引来存储。
由以上数据，我们可以得到如下几个结论：
1. 文件大小和数据块数量：假设文件大小为 4 MB。每个数据块为 4 KB，因此文件需要 `4MB / 4KB = 1024` 个数据块。
2. 一级索引表：假设一个一级索引表可以包含 256 个指针，因此它可以指向 256 个二级索引表。
3. 二级索引表：每个二级索引表也可以包含 256 个指针，因此它可以指向 256 个三级索引表。
4. 三级索引表：每个三级索引表可以包含 256 个指针，因此它可以指向 256 个数据块。

多级索引的优缺点

- 优点：扩展性好：适用于非常大的文件，因为可以通过增加索引级别来管理更多的数据块。灵活性高：可以根据文件的大小动态调整索引级别。
- 缺点：索引表占用空间：多级索引需要额外的索引表存储空间。查找时间增加：需要多次访问索引表才能找到实际的数据块，增加了查找时间。

#### 例题：计算多级索引表的数量
题目：一个文件系统采用三级索引来管理文件。假设每个索引表最多包含 256 个指针，每个数据块的大小是 4 KB。现在有一个大小为 100 MB 的文件。请计算该文件需要的多级索引表的数量。

解答步骤：

1. 计算数据块数量：

> 已知：文件大小为 100 MB，数据块大小为 4 KB。 
> 计算文件需要的数据块数量： 
> 数据块数量 = `100MB / 4KB` = `100 × 1024KB / 4 KB` = `25600` 个数据块

2. 计算三级索引表的数量：

> 已知：每个三级索引表可以包含 256 个指向数据块的指针。 
> 需要的三级索引表数量： 
> 三级索引表数量 = `25600 / 256` = `100` 个三级索引表

3. 计算二级索引表的数量：

> 已知：每个二级索引表可以包含 256 个指向三级索引表的指针。 
> 需要的二级索引表数量： 
> 二级索引表数量 = `100 / 256` = `0.39` = `1` 个二级索引表

4. 计算一级索引表的数量：

> 已知：每个一级索引表可以包含 256 个指向二级索引表的指针。 
> 需要的一级索引表数量： 
> 一级索引表数量 = `1 / 256` = `0.004` = `1` 个一级索引表

答案：该文件需要的多级索引表数量为：`100` 个三级索引表；`1` 个二级索引表；`1` 个一级索引表

软考知识点15：文件管理相关知识

## 简介

关于磁盘的考试题目并不常见，但是也有一定的概率出现。磁盘的考点主要有：
1. 磁盘的组成；
2. 磁盘读取时间计算（根据题意计算，很简单）；
3. 移臂调度算法；

> 关注公众号“**月上老狗**”，发送“**软件设计师**”，获取历年软件设计师软考真题。
> 
> ![image](https://images.oldmoon.top/images/dingdangdog/dingdangdog-1680842466920.jpg)



## 磁盘的组成

从表面来说，磁盘内部有以下几个组成部分需要牢记：

- 盘片（`Platter`）：盘片是磁盘存储数据的主要介质，通常是由铝或玻璃制成的圆形薄片，表面涂有磁性材料。数据通过磁化盘片表面的微小区域来进行存储。
- 盘面（`Surface`）：每个盘片有两个表面（上表面和下表面）。每个表面都可以用来存储数据。
- 磁头（`Read/Write Head`）：磁头位于磁盘的臂架（`Arm`）上，负责读写数据。通过在盘片表面上方移动，磁头可以在不同位置读取或写入数据。
- 主轴（`Spindle`）：主轴是一种旋转轴，所有的盘片都安装在主轴上。通过电动机驱动，使盘片高速旋转，通常达到每分钟数千转（`RPM`）。

除以上几个主要部分外，还有一些比较抽象的部分，了解即可：

- 轨道（`Track`）：轨道是盘片表面上的同心圆，每个轨道被分成若干扇区。轨道是数据存储的基本单位，磁头在轨道上移动读取或写入数据。
- 扇区（`Sector`）：扇区是轨道上的一个固定长度的存储单元，通常为`512字节`或`4KB`。扇区是数据存取的基本单位，操作系统按扇区来读写数据。
- 缓存（`Cache/Buffer`）：缓存是一种高速存储器，位于磁盘和主机之间。用于临时存储数据，提高读写速度和效率。
- 控制电路（`Controller Electronics`）：控制电路包括磁盘控制器和接口电路。负责磁盘的读写操作、数据传输和错误校验等。
- 接口（`Interface`）：接口是磁盘与计算机系统之间的数据传输通道。常见接口包括`SATA`、`SAS`、`NVMe`等，用于连接磁盘与主板或其他控制器。
- 保护外壳（`Enclosure`）：外壳是保护磁盘内部组件的外部结构。防止灰尘、湿气和物理损伤等环境因素对磁盘的影响。

这些部分共同协作，使得磁盘能够高效地存储和读取数据，广泛应用于各种计算机系统中。在软考中，了解这些基本结构和作用有助于理解磁盘工作原理和性能优化。

## 磁盘读取时间

一般认为，磁盘读取数据的时间包括以下几个主要组成部分：
1. 寻道时间：需按照数据存储轨道的时间。
2. 扇区读取时间：找到并读取扇区中数据的时间。
3. 数据传输时间：将读取到的数据传出到内存的时间。

**注意：以上几个时间是考试中常见的几个组成部分，当然实际上读取数据并不仅仅是由这些部分组成，所以还是要根据题意再去计算，一般就是小学难度的加减乘除，注意读题即可！**

## 移臂调度算法

移臂调度算法用于磁盘访问过程中优化磁头移动顺序，以减少寻道时间和提高磁盘效率。常见的移臂调度算法有以下几种：

- 先来先服务（FCFS，First-Come, First-Served）
- 最短寻道时间优先（SSTF，Shortest Seek Time First）
- 扫描算法（SCAN）
- 循环扫描（C-SCAN，Circular SCAN）
- 循环提升扫描（C-LOOK）

### 先来先服务

- 概念：按照请求到达的先后顺序进行磁头调度。
- 优点：简单易实现，不需要复杂的算法。
- 缺点：性能较差，可能会导致长时间的寻道延迟（即“队尾效应”）。
- 使用场景：适用于简单的磁盘调度场景，或者系统负载较轻的情况下。

### 最短寻道时间优先
- 概念：优先处理距离当前磁头位置最近的请求。
- 优点：相对减少了平均寻道时间，提高了效率。
- 缺点：容易导致“饥饿”现象，远离当前磁头位置的请求可能长期得不到服务。
- 使用场景：适用于系统负载较轻、请求比较均匀的情况下。

### 扫描算法
- 概念：磁头在磁盘上向一个方向移动，处理途中所有的请求，直到到达某个端点，然后反向移动，重复这一过程。
- 优点：相对于FCFS和SSTF，减少了磁头移动的范围，提高了效率。
- 缺点：端点处的请求可能会等待较长时间。
- 使用场景：适用于请求较多且比较分散的情况下，如传统硬盘的文件系统操作。

### 循环扫描
- 概念：磁头在一个方向上移动处理请求，到达端点后迅速返回起始端，再次向相同方向移动处理请求。
- 优点：平均响应时间更稳定，避免了端点处请求长时间等待的问题。
- 缺点：返回起始端的过程中会有额外的无用移动时间。
- 使用场景：适用于对响应时间一致性要求较高的系统。

### 循环提升扫描
- 概念：类似于C-SCAN，但磁头只移动到最后一个请求的位置，然后直接返回起始端，减少了无用的磁头移动。
- 优点：进一步减少了无用的磁头移动，提高了效率。
- 缺点：实现相对复杂。
- 使用场景：适用于高性能存储系统，如数据库管理系统。

### 常见使用场景

常见使用场景：
- 最短寻道时间优先(`SSTF`)：适用于磁盘请求较少或相对均匀的场景。
- 扫描算法(`SCAN`)：广泛应用于多用户操作系统的文件系统中。
- 循环提升扫描(`C-SCAN`)：适用于需要一致响应时间的高性能存储系统，如大型数据库服务器。

在实际应用中，选择合适的移臂调度算法可以显著提升磁盘的性能和响应速度。`SSTF`、`SCAN`和`C-SCAN`是最常用的算法，它们在不同的使用场景中各有优势。根据系统的具体需求和特点，选择适合的算法可以有效地优化磁盘访问效率。

软考知识点14：磁盘管理相关知识

## 简介

段式存储和页式存储是计算机系统中用于管理内存的一些重要技术，尤其是在内存管理和虚拟内存机制中。

这部分考点可能会考察概念的理解，也可能会出现部分需要计算的题目。

> 关注公众号“**月上老狗**”，发送“**软件设计师**”，获取历年软件设计师软考真题。
> 
> ![image](https://images.oldmoon.top/images/dingdangdog/dingdangdog-1680842466920.jpg)



## 段式存储
**段式存储（Segmentation）** 是一种内存管理方案，它将程序和数据划分为若干个段（Segment）。每个段有一个段号和一个段内地址。

段式存储的主要特点和考点包括：

### 基本概念

- 段（Segment）：一个段是一段逻辑上相关的内存区域，例如一个程序模块、数据数组、堆栈等。每个段都有一个段号和段内地址。
- 段表（Segment Table）：段表存储每个段的起始地址和长度，用于地址转换。

### 地址转换

逻辑地址由段号和段内地址组成。地址转换通过查段表实现，将逻辑地址转换为物理地址。地址转换公式：
> 物理地址 = 段基址 + 段内地址

### 优缺点

- 优点：支持用户视角的逻辑内存划分，提高程序模块化和共享性。每个段可以有不同的保护和共享属性，提高安全性。
- 缺点：内存碎片问题：段的大小不同，容易产生外部碎片。段表开销：需要维护段表，增加内存管理的复杂度。

## 页式存储

**页式存储（Paging）** 也是一种内存管理方案，它将内存划分为固定大小的页（Page）和页框（Frame）。

### 基本概念

- 页（Page）：逻辑内存划分为固定大小的块，称为页。
- 页框（Frame）：物理内存也划分为固定大小的块，称为页框。
- 页表（Page Table）：页表存储每个页对应的页框号，用于地址转换。

### 地址转换

逻辑地址由页号和页内偏移组成。地址转换通过查页表实现，将逻辑地址转换为物理地址。地址转换公式：
> 物理地址 = 页框基址 + 页内偏移

### 优缺点

- 优点：解决了内存碎片问题：页和页框大小固定，有效减少了外部碎片。内存利用率高：物理内存可以分散存放，内存利用率提高。
- 缺点：页表开销：每个进程都有一个页表，增加了内存管理的开销。地址转换开销：每次内存访问都需要通过页表进行地址转换，可能影响性能。

## 段页式存储
**段页式存储（Segmented Paging）** 结合了段式存储和页式存储的优点。

### 基本概念

- 逻辑内存先划分为段，每个段再划分为页。
- 需要维护段表和每个段对应的页表。

### 地址转换

- 逻辑地址包含段号、页号和页内偏移。
- 地址转换过程：先查段表获取段基址，再查段对应的页表获取页框基址，最后计算物理地址。

### 优点

1. 结合了段式存储的逻辑划分和页式存储的固定大小分块，提高内存管理效率。
2. 既减少了内存碎片问题，又支持灵活的内存保护和共享。

## 应考建议
在《软件设计师》考试中，关于段式存储和页式存储的考点主要包括：

- 基本概念和术语：理解段、页、页框、段表、页表等基本概念。
- 地址转换过程：掌握段式存储和页式存储的地址转换过程和公式（几乎不考）。
- 优缺点对比：能够对比段式存储和页式存储的优缺点，以及它们在实际应用中的适用场景。
- 综合应用：理解段页式存储的原理和优势，能解释其工作机制。

### 例题（难）

在一个页式存储管理系统中，假设逻辑地址空间为 `16` 位，页大小为 `4KB`。已知某个逻辑地址为 `0x3A45`，请计算该地址存储在物理内存的哪个页框中，假设页表如下：

|逻辑页|物理页|
|----|----|
| 0 | 3 |
| 1 | 5 |
| 2 | 1 |
| 3 | 7 |
| 4 | 2 |
| 5 | 6 |
| 6 | 4 |
| 7 | 0 |

#### 解答过程

1. 确定页大小和页号

页大小为 `4KB`，即 `2^12` 字节。因此，逻辑地址的低 `12` 位为页内偏移，高 `4` 位为页号。
逻辑地址为 `0x3A45`（`16` 进制），转换为二进制为：`0011 1010 0100 0101`。

2. 提取页号和页内偏移：

页号：高 `4` 位 `0011`，即 `3`（十进制）。
页内偏移：低 `12` 位 `1010 0100 0101`，即 `0xA45`（十进制为 `2629`）。

3. 查找页表：

页表显示页 `3` 映射到页框 `7`。

4. 计算物理地址：

物理页框号为 `7`，物理页框基地址为页框号乘以页大小。
页大小为 `4KB`，即 `4096` 字节。
页框基地址 = `7 × 4KB` = `7 × 4096` = `28672`（十进制）或 `0x7000`（`16` 进制）。

5. 计算最终物理地址：

物理地址 = 页框基地址 + 页内偏移。
物理地址 = `0x7000 + 0xA45 = 0x7A45`。

6. 答：
逻辑地址 `0x3A45` 对应的物理地址是 `0x7A45`。该地址存储在物理内存的页框 `7` 中。

软考知识点13：段式存储、页式存储

twitter:card

twitter:title

twitter:site

twitter:image

努力做一只帅气、有才、豁达的老狗！

twitter:description

程序员,笔记,Bug记录,编程技术,AI,Java,Node,Golang,个人博客,资源分享,月上老狗,dingdangdog

考点	考题类型	分值	出现概率	文章
操作系统概念	理论	1	低	软考知识点10
进程	理论	1	低	软考知识点10
线程	理论	1	低	软考知识点10
进程调度模型	理论、计算	1-2	中	软考知识点11
PV操作	理论	1	中	软考知识点11
PV模型与信号量	理论、计算	1-3	高	软考知识点11
死锁	理论、计算	1	低	软考知识点12
进程资源图	理论	1	低	软考知识点12
存储方式分类	理论	1	低	软考知识点13
段式存储	理论、计算	1	低	软考知识点13
页式存储	理论、计算	1-2	中	软考知识点13
磁盘的组成	理论	1	低	软考知识点14
磁盘读取时间	理论、计算	1-2	中	软考知识点14
磁盘读取方式（移臂调度）	理论、计算	1-2	中	软考知识点14
IO管理软件分层	理论	1	中	软考知识点15
文件相关概念	理论	1	中	软考知识点15
文件索引分层	理论、计算	1-2	中	软考知识点15
作业管理	理论	1	低	未讲到的其他知识