子非鱼的技术博客

序言

二叉树题型的算法主要分为回溯，动态规划，迭代三类。从本质上三者都是在遍历算法基础上的修改。回溯关心的是在每个结点的访问过程中如何更新结果；动态规划关心的是如何拆解出子问题，不具体分析每个结点的状态，而是通过划分子问题让其通过基本问题递归解决；迭代主要是指BFS层序遍历，适用于与深度（或高度）相关的问题求解

二叉树基本结构

1. 二叉树

1
2
3
4
5
6
7

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 多叉树

1
2
3
4
5

class TreeNode {
public:
    int val;
    vector<TreeNode *> children;
};

二叉树遍历

1. 递归遍历

前序位置：刚进入当前子树根结点的时候（已知根结点信息）

回溯框架

回溯算法求解时要考虑三个问题

1. 路径：已经做出的选择
2. 选择列表：当前可以做的选择，即孩子结点的情况（剪枝做的就是精简孩子结点，避免重复讨论，反映到代码里就是对于某些情况直接continue调过）
3. 结束条件：何时到达决策树的底层，返回结果

求解的关键在于画出决策树，并运用合理的剪枝条件。不要跳出此框架自己去想新写法，很容易漏解或者多解

1
2
3
4
5
6
7
8
9
10

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

全排列问题

排列问题（元素不重复不可复选）

选择列表：避免选当前路径上已经选择过的数字

解决方法：引入used数组，记录从根结点到当前结点的路径信息，判断数字是否被使用

文件系统操作

整体架构

在文件系统和应用程序间有一层抽象层，称为虚拟文件系统（VFS）

• VFS作为抽象层向应用层提供了统一的文件接口（read，write等）
• VFS实现了一些公共的功能，如Directory Cache和Page Cache等
• 规范了接口

VFS向应用层提供统一接口，具体实现不同文件系统有不同实现，VFS将函数指针指向对应函数

核心操作

文件系统的注册

在Linux中，具体文件系统通常是一个内核模块，在内核模块被加载时完成文件系统的注册

磁盘挂载

磁盘的工作原理

磁盘读写的过程

1. 磁盘移动，找到要读的柱面（cylinder，简称C）
2. 从柱面选择具体读哪个磁道（magnetic head，简称H），选择对应的磁头上电（每次只能有一个磁头上电）
3. 旋转磁盘，将对应磁道中要读写的那个扇区（sector，简称S）转到磁头下方
4. 开始读写，将扇区中的内容读到内存缓存区中，或者将内存缓存区中的内容写到该扇区中

生磁盘的使用

第一层抽象：从扇区到磁盘块请求（抽象读写请求）

正常寻址需要通过CHS三维向量，但是可以通过一位扇区编号编址

磁盘读写时间 = 寻道时间（选择柱面）+旋转时间（选择+读取扇区）+传输时间（磁生电活电生磁）

其中寻道时间占主导，故每次只读/写一个扇区是对于时间的浪费，故一次读/写多个扇区，称为块

第二层抽象：多个进程产生的磁盘请求队列（抽象读写方法）

传统IO

传统IO过程

1. CPU发起IO请求，每次只能请求一个字
2. 磁盘数据写入缓冲区后，通过IO中断通知CPU
3. CPU将缓冲区数据通过寄存器写入内核缓冲区（内存中）
4. CPU将内核缓冲区（内存中）的数据拷贝到用户缓冲区（内存中）

缺点

1. CPU效率低下：CPU需要频繁得处理IO请求
2. 传输效率低下：数据先从磁盘缓冲区拷贝到寄存器后才到拷贝到内存

引入DMA后的IO

将数据搬运的工作全部交给DMA控制器，CPU不需要参与

引入DMA后的IO过程

1. CPU发送IO请求到DMA
2. DMA拷贝磁盘数据到内核缓冲区
3. DMA拷贝完后向CPU发送IO中断请求
4. CPU将内核缓冲区的数据拷贝到用户缓冲区

第七章 中断

中断与异常

中断执行过程

当通过键盘给当前进程输入参数时的流程（IO中断）

中断流程

1. 用户键盘输入
2. 键盘控制器生成扫描码并触发中断 (IRQ1)
3. CPU 暂停当前进程，响应中断
4. CPU执行中断处理程序，获取键盘输入
5. 恢复被中断的任务
6. 用户进程读取缓冲区输入（系统调用，使用“陷阱”内中断）

用户如何使用系统其他资源（系统调用）

用户态的程序只能使用内存中用户段，不能使用内核段。内核态可以访问任何内存数据。

第六章 操作系统安全

缓冲区溢出攻击

原理

缓冲区溢出通常发生在程序使用固定大小的内存缓冲区来存储用户输入时，没有对输入数据的长度进行适当检查。攻击者利用这一点，将过大的输入数据注入缓冲区，导致：

• 覆盖关键数据：覆盖函数的返回地址、指针或其他重要变量。

• 注入恶意代码：将攻击代码注入溢出的内存区域，并操纵程序跳转到攻击代码执行。

• 控制程序执行流：通过覆盖返回地址或函数指针，改变程序的正常执行逻辑。

解决办法

• 栈随机化

• 栈破坏检测

• 限制可执行代码区域

操作系统安全算法

1. 用户身份验证：散列算法

第五章 指令系统结构

指令

执行流程

1. 取指阶段：以PC作为第一个字节的地址，从内存中读出10个字节
2. 译码阶段：指令字段译码，将操作数的值写到ALU读取的寄存器位置
3. 执行阶段：ALU根据操作数和操作码计算值
4. 访存阶段：读写内存位置
5. 写回阶段：将结果值写入寄存器
6. 更新PC：更新PC指向下一条指令的地址

指令示例

irmovq

将一个 64 位的立即数（常数）加载到目标寄存器中

pushq

第一章 绪论

计算机体系结构

计算机启动后发生了什么

1. 上电自检

   主板的固件（BIOS 或 UEFI）执行硬件检测，检查 CPU、内存、显卡、键盘等设备是否正常

2. 加载 BIOS 或 UEFI

   1. CPU 开始执行 0xFFFFFFF0 地址处的指令，该地址处是一条 JUMP 指令，这条指令清空了基址寄存器的值，并让指令跳回到 BIOS 开始处（物理地址为 0xF0000，参考上图 0xF0000 处的标识）以执行 BIOS

   2. BIOS 或 UEFI 固件初始化计算机硬件，完成底层配置。

   3. 确认引导顺序（启动顺序），如硬盘、USB 设备或网络启动。

   4. 加载引导程序（Bootloader）的第一部分，通常位于启动设备的引导扇区。

3. 主引导记录（Master Boot Record, MBR）

   BIOS 从指定的启动设备中读取主引导记录

4. 启动加载器（Bootloader）

   启动加载器是一个小型程序，负责加载操作系统内核（常用：GRUB多操作系统支持，配置灵活；Windows Boot Manager用于加载 Windows 操作系统）

5. 内核初始化

   操作系统内核接管硬件的控制。执行真正的根文件系统中的 /sbin/init 进程，即系统的 1 号进程。此后，系统的控制权就全权交给 /sbin/init 进程了

6. 系统初始化

   /sbin/init 进程是系统其它所有进程的父进程，当它接管了系统控制权后，它会根据 /etc/inittab 文件来执行相应的脚本，从而完成一系列的系统初始化操作

7. 用户登陆

程序是如何运行的

准备阶段：

1. 通过shell获取可执行程序地址，参数和环境变量
2. 通过fork创建子进程
3. 通过execve替换当前进程的地址空间，使用加载器将程序加载到内存中
4. shell调用wait 或 waitpid 系统调用等待子进程执行结束

运行阶段：

如何写一个递归算法

1. 确定问题：给当前的算法一个符合计算机处理流程的解释。例如对于斐波那契数数列求解int fib(int n)，应该翻译成计算数列第n项并返回数列的值

2. 解决基准问题：思考当输入值为基础值时，其返回的结果是什么。该步用于确定递归终止条件。例如对于汉诺塔问题，在只有一块积木时只需要将其从From移到Target即可

3. 拆解问题：考虑在当前的普通输入时，应该如何解决问题。例如对于斐波那契数数列求解，当前应该返回的值是fib(n-1)+fib(n-2)。

   ❗️❗️不要尝试去思考其内部具体是如何执行的，只要把当前函数当作一个已经实现的库函数即可。否则只会越绕越晕。

递归算法举例分析

二叉树遍历

1. 确定问题：遍历以root为根结点的二叉树
2. 解决基准问题：当root为空指针时返回
3. 拆解问题：在访问完当前结点后，继续遍历左子树（具体说：遍历以root->left为根结点的二叉树），继续遍历右子树（具体说：遍历以root->right为根结点的二叉树）