Maxw的小站

树莓派镜像下载、配置与自定义内核安装流程

1. 下载并写入指定树莓派镜像

为避免因购买或借用的树莓派设备时间不同导致的系统版本不一致，建议大家统一下载指定的树莓派镜像作为起点。

• 将 MicroSD 卡插入 USB 读卡器，并连接到你的电脑。
• 下载并安装最新版 Raspberry Pi Imager。
• 下载课程指定的树莓派镜像：2022-01-28-raspios-bullseye-armhf.zip（约1.2GB，解压后近4GB）。
• 解压 zip 文件，得到 .img 镜像文件。
• 打开 Raspberry Pi Imager，选择“CHOOSE OS”→“Use custom”，选中刚才解压的 .img 文件。
• 选择“CHOOSE SD CARD”，选中你的 MicroSD 卡（注意不要选错，否则会清空数据）。
• 进入高级设置（齿轮图标，或 Windows 下用 Ctrl+Shift+X），建议修改主机名为唯一值（如包含你的用户名），以免与他人冲突。
• 勾选“Enable SSH”，选择“Use password authentication”，设置用户名和强密码（建议不要用默认密码）。
• 勾选“Set locale settings”，设置时区（如美国中部用 America/Chicago），键盘布局选 us。
• 点击“Save”，然后点击“WRITE”写入镜像。
• 写入完成后，卸载 MicroSD 卡，插入树莓派并开机。

2. 首次启动与 SSH 连接

• 树莓派首次启动可能需要几分钟，启动后通过 SSH 连接（如 ssh piuser@pihost，用户名和主机名为你设置的）。
• 若主机名无法解析，可在路由器管理页面查找树莓派的 IP 地址，再用 ssh 连接。

3. 初始设置与系统升级

• 首次登录会看到“Welcome to the Raspberry Pi”向导，按提示设置国家、语言、时区、键盘等。
• 可能会再次提示设置密码，可直接关闭。
• 为防止欢迎界面反复出现，运行：

  1	sudo apt purge piwiz

• 升级系统和驱动：

  1 2	sudo apt-get update sudo apt-get upgrade

• 升级完成后重启树莓派。

4. 网络设置与信息收集

• 连接 WiFi，打开终端，运行：

  1	ifconfig wlan0

  记录 MAC 地址（ether 后面的六组十六进制数）。
• 运行：

  1	hostname -I

  记录 IP 地址。

5. 传输并安装自编译内核与模块

• 用 ssh 连接学校提供的linux工作平台，进入你编译内核的目录：

  1	cd /project/scratch01/compile/"your username"/linux_source

• 打包模块和内核启动文件：

  1 2	tar -C modules/lib -czf modules.tgz modules tar -C linux/arch/arm -czf boot.tgz boot

• 在树莓派上新建 linux_source 目录，进入后用 sftp 下载上述两个压缩包：

  1 2 3 4 5

  sftp [学校统一登陆平台key]@shell.cec.学校曾用简称.edu cd /project/scratch01/compile/"your username"/linux_source get modules.tgz get boot.tgz quit

• 备份 /usr/lib/modules 和 /boot 目录（或 /lib/modules，视系统而定）：

  1 2	sudo cp -r /usr/lib/modules ~/Desktop/modules_backup sudo cp -r /boot ~/Desktop/boot_backup

• 解压并安装新内核和模块：

  1 2 3 4 5 6 7 8

  tar -xzf modules.tgz tar -xzf boot.tgz cd modules sudo cp -rd * /usr/lib/modules # 或 /lib/modules cd .. sudo cp boot/dts/*.dtb /boot/ sudo cp boot/dts/overlays/*.dtb* /boot/overlays sudo cp boot/dts/overlays/README /boot/overlays

• 树莓派 3B+：

  1	sudo cp boot/zImage /boot/kernel7.img

• 树莓派 4/4B：

  1	sudo cp boot/zImage /boot/kernel7l.img

6. 验证新内核

• 重启树莓派，运行：

  1

  uname -a

  检查输出是否包含你设置的本地版本字符串、编译日期等。
• 若未生效，编辑 /boot/config.txt，在 [pi4] 段落前加一行：

  1	arm_64bit=0

  再重启并用 uname -a 检查。

7. 备份与后续建议

• 建议用 svn、git 等工具备份你的代码，也可在多台树莓派间做冗余，防止系统崩溃或锁死导致数据丢失。
• sudo passwd root更新root密码（忘记密码用）
• sudo raspi-config中可以更改主机名
• 在树莓派的桌面环境中，可以使用快捷键 Ctrl + Alt + T 快速打开终端

用户管理

• sudo adduser 新用户名创建新用户
• usermod -aG sudo username将username用户加入sudoers组
• 执行visudo命令并在文件中添加username ALL=(ALL) NOPASSWD:ALL-赋予username用户执行所有sudo命令权限，不需要密码提示
• sudo userdel --remove --force pi删除默认账号

树莓派 Linux 内核源码下载与编译流程

1. 下载适用于树莓派的内核源码

一般项目可以直接去 kernel.org 下载 Linux 源码，但本课程针对树莓派，需要用树莓派官方维护的内核版本（在 https://github.com/raspberrypi）。

在你的 /project/scratch01/compile/user-name/ 目录下，新建 linux_source 文件夹用于存放源码和编译文件：

1
2

mkdir linux_source
cd linux_source

下载指定版本的树莓派内核源码（此过程可能需要20-30分钟）：

1

wget https://github.com/raspberrypi/linux/archive/raspberrypi-kernel_1.20210527-1.tar.gz

解压源码包：

1

tar -xzf raspberrypi-kernel_1.20210527-1.tar.gz

解压后会得到一个新目录，建议用 mv 命令重命名为 linux，便于后续操作。解压完成后请删除 .tar.gz 文件以节省空间。

进入 linux 目录，运行以下命令查看内核版本：

1

make kernelversion

并用文本编辑器（如 emacs、vim、nano）打开 Makefile，查看前几行定义的内核版本常量，记录 NAME 常量的值。

2. 针对树莓派 4/4B 的设备树修改

如果你使用的是 Raspberry Pi 4 或 4B，需要修改设备树文件 arch/arm/boot/dts/bcm2711.dtsi，找到 arm-pmu 条目，将 compatible 行改为：

1

compatible = "arm,cortex-a72-pmu", "arm,cortex-a15-pmu", "arm,armv8-pmuv3";

3. 配置交叉编译环境

添加交叉编译器和新版 gcc 到 PATH（并将以下两行添加到 ~/.bashrc 文件末尾，确保下次登录自动生效）：

1
2

module add arm-rpi
module add gcc-8.3.0

4. 配置内核

对于 Raspberry Pi 3B+，运行：

1

make -j8 ARCH=arm CROSS_COMPILE=arm-linux-gnueabihf- bcm2709_defconfig

对于 Raspberry Pi 4/4B，运行：

1

make -j8 ARCH=arm CROSS_COMPILE=arm-linux-gnueabihf- bcm2711_defconfig

这会生成树莓派的默认内核配置。

5. 自定义内核配置

进入菜单配置界面：

1

make ARCH=arm CROSS_COMPILE=arm-linux-gnueabihf- menuconfig

• 在 "General setup" -> "Local version" 里，添加你的唯一标识（如 -v7 或 -v7l 后面加你的名字，无空格）。
• 修改 "Preemption Model" 选项为 "Preemptible Kernel (Low-Latency Desktop)"，以获得更低延迟的抢占模型。
• 启用 ARM 性能监控单元驱动（"Kernel Performance Events and Counters"），并确保 "Profiling support" 也已启用。
• 任选一个有趣的选项，按 H 键查看简介，记录该选项的名称、简介和符号（symbol），并简述为何选择 "Preemptible Kernel (Low-Latency Desktop)"（提示：该模式适合需要低延迟响应的场景，如桌面或实时应用）。

保存并退出配置。

6. 编译内核

记录编译开始和结束时间：

1

date>>time.txt; make -j8 ARCH=arm CROSS_COMPILE=arm-linux-gnueabihf- zImage modules dtbs; date>>time.txt

编译完成后，创建用于存放模块的目录：

1

mkdir ../modules

安装内核模块：

1

make -j8 ARCH=arm CROSS_COMPILE=arm-linux-gnueabihf- INSTALL_MOD_PATH=../modules modules_install

7. 回答与说明

• 用 cat time.txt 查看编译所用时间。
• 说明为何要用交叉编译器：因为 linuxlab 服务器的架构与树莓派不同，必须用交叉编译器生成适用于 ARM 架构的内核和模块。

总结
本流程涵盖了树莓派专用 Linux 内核源码的下载、解压、配置、定制、编译和模块安装，并介绍了如何设置交叉编译环境和设备树修改。通过这些步骤，你可以为树莓派编译和定制属于自己的 Linux 内核。

与众不同的“野兽”：内核与用户空间的区别

Linux 内核与普通用户空间程序相比，有许多独特之处。这些差异并不一定让内核开发更难，但确实让它与用户空间开发大不相同。内核开发有一些“特殊规则”，有些显而易见，有些则不那么直观。主要区别包括：

1. 内核无法使用 C 标准库（libc）和标准 C 头文件。
2. 内核使用 GNU C 语言编写。
3. 内核没有用户空间的内存保护机制。
4. 内核中不能轻易执行浮点运算。
5. 内核每个进程的栈空间很小且固定。
6. 由于内核有异步中断、支持抢占和多处理器（SMP），因此同步和并发问题非常重要。
7. 可移植性很重要。

下面简要解释这些差异：

没有 libc 或标准头文件

与用户空间程序不同，内核不会链接标准 C 库（libc）或其他外部库。主要原因是速度和体积——完整的 C 库太大、效率太低，不适合内核使用。

不用担心，内核自己实现了很多常用的 libc 函数。例如，常见的字符串操作函数在 lib/string.c 中实现，只需包含 <linux/string.h> 头文件即可使用。

头文件

内核源码只能包含内核源码树中的头文件，不能引用外部头文件或库。
- 基础头文件位于源码根目录的 include/ 目录下。例如，<linux/inotify.h> 实际路径为 include/linux/inotify.h。 - 架构相关的头文件位于 arch/<architecture>/include/asm，如 x86 架构下为 arch/x86/include/asm，引用时用 <asm/ioctl.h>。

没有 printf()，用 printk()

内核没有 printf()，但提供了类似的 printk() 用于内核日志输出。例如：

1

printk("Hello world! A string '%s' and an integer '%d'\n", str, i);

1

printk(KERN_ERR "this is an error!\n");

GNU C

和大多数 Unix 内核一样，Linux 内核主要用 C 语言编写。但它并不是严格的 ANSI C，而是大量使用了 gcc（GNU 编译器套件）提供的各种语言扩展。内核开发者会用到 ISO C99 和 GNU C 的扩展特性，这使得 Linux 内核基本只能用 gcc 编译（近年 Intel C 编译器也支持了大部分 gcc 特性，可以编译内核）。目前推荐使用 gcc 4.4 或更高版本。

C99 的扩展比较常见，而 GNU C 的扩展则是 Linux 内核代码区别于普通 C 项目的重要原因。下面介绍几个常见的 GNU C 扩展：

内联函数（Inline Functions）

C99 和 GNU C 都支持内联函数（inline function）。内联函数会在每个调用点直接插入函数体，避免了函数调用和返回的开销（如寄存器保存/恢复），有利于编译器整体优化调用者和被调用者的代码。但缺点是会增加代码体积和内存消耗。

内核开发者通常只对小型、对性能要求高的函数使用内联。大函数或不常用的函数不建议内联。

内联函数的声明方式如下：

1

static inline void wolf(unsigned long tail_size)

• static inline 关键字用于定义内联函数。
• 内联函数的声明要在使用前，否则编译器无法内联。
• 通常内联函数会放在头文件中（因为是 static，不会导出符号）。

内核更倾向于用内联函数而不是复杂的宏，因为内联函数有类型安全和可读性好等优点。

内联汇编（Inline Assembly）

gcc 支持在 C 代码中嵌入汇编指令，这在与硬件密切相关的内核代码中很有用。用法如下：

1
2
3

unsigned int low, high;
asm volatile("rdtsc" : "=a" (low), "=d" (high));
/* low 和 high 现在分别保存了 64 位 tsc 的低 32 位和高 32 位 */

• asm 关键字用于插入汇编代码。
• 这种用法主要用于体系结构相关或对性能极致要求的代码。
• 大部分内核代码还是用 C 语言编写，汇编只用于底层和关键路径。

分支预测注解（Branch Annotation）

gcc 提供了分支预测指令，可以告诉编译器某个条件分支更可能被执行，从而优化生成的代码。内核通过 likely() 和 unlikely() 宏来使用这些特性。

例如：

1
2
3
4
5
6
7

if (unlikely(error)) {
    /* 这里假设 error 很少为真 */
}

if (likely(success)) {
    /* 这里假设 success 几乎总为真 */
}

没有内存保护

当用户空间程序非法访问内存时，内核可以捕获错误，发送 SIGSEGV 信号并终止该进程。但如果内核自身非法访问内存，后果就不可控了（毕竟，谁来保护内核呢？）。内核中的内存违规会导致 oops（严重内核错误）。因此，在内核中绝不能非法访问内存，比如解引用 NULL 指针——在内核里，这样的错误代价更高！

另外，内核内存是不可换页的（not pageable），即内核占用的每一字节物理内存都不能被换出。你在内核里多用一点内存，系统可用物理内存就少一点。每次想给内核加新功能时，请记住这一点！

不能（轻易）使用浮点运算

用户空间进程使用浮点指令时，内核会负责从整数模式切换到浮点模式。具体做法依赖于体系结构，通常是通过陷阱（trap）实现的。

但内核自身不能像用户空间那样方便地使用浮点运算，因为内核无法轻松地“陷阱”自己。内核里用浮点数需要手动保存和恢复浮点寄存器等操作，非常麻烦。简而言之：不要在内核里用浮点运算！ 除极少数特殊情况外，内核代码中基本没有浮点操作。

小而固定的栈空间

用户空间可以在栈上分配大量变量，包括大结构体和大数组，因为用户空间的栈很大且可以动态增长。但内核栈既不大也不能动态扩展，而是小且固定的。

• 栈的具体大小依赖于体系结构。例如 x86 架构下，栈大小可在编译时配置为 4KB 或 8KB。
• 通常，32 位系统为 8KB，64 位系统为 16KB，每个进程有自己的内核栈，这个大小是固定的。

因此，内核开发时要避免在栈上分配大对象。

同步与并发

内核容易出现竞态条件（race condition）。与单线程的用户空间程序不同，内核有多种并发访问共享资源的情况，必须通过同步机制防止竞态：

• Linux 是抢占式多任务操作系统，进程会被调度器随时切换，内核需要在这些任务间同步。
• Linux 支持对称多处理（SMP），多个处理器上的内核代码可能同时访问同一资源。
• 中断是异步发生的，可能在访问资源时被打断，导致中断处理程序也访问同一资源。
• 内核本身是可抢占的，内核代码可能被抢占，切换到另一个访问同一资源的代码。

常见的同步机制有自旋锁（spinlock）和信号量（semaphore）。后续章节会详细介绍。

可移植性的重要性

虽然用户空间程序不一定要追求可移植性，但 Linux 作为一个可移植操作系统，必须保证代码能在多种体系结构上正确编译和运行。体系结构相关的代码要放在专门的目录下，体系结构无关的代码要保持通用。

一些基本规则包括：保持字节序中立、支持 64 位、不要假设字长或页面大小等。后续章节会详细讨论可移植性。

内核源码相关

获取内核源码

当前的 Linux 源代码总是可以在 http://www.kernel.org 官方网站上以完整的 tarball（用 tar 命令创建的归档文件）和增量补丁的形式获得。 可以利用Elixir Cross Referencer网站在线查看源码

使用 Git

你可以用 Git 获取 Linus 主线最新的源码树：

1

git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git

1

git pull

安装内核源码

内核 tarball 以 GNU zip（gzip）和 bzip2 两种格式发布。bzip2 是默认且推荐的格式，因为它通常压缩得更好。bzip2 格式的内核包名为 linux-x.y.z.tar.bz2，其中 x.y.z 是内核版本号。下载源码后，解压和解包很简单。如果你的 tarball 是 bzip2 压缩的，运行：

1

tar xvjf linux-x.y.z.tar.bz2

1

tar xvzf linux-x.y.z.tar.gz

源码安装与开发位置

内核源码通常安装在 /usr/src/linux。但你不应该在这个目录下开发，因为你的 C 库可能会链接到这里的内核版本。此外，修改内核源码不应需要 root 权限——建议在你的 home 目录下开发，只在安装新内核时用 root。即使安装新内核，也不要动 /usr/src/linux。

使用补丁

在 Linux 内核社区，补丁是交流的通用语言。你会以补丁的形式分发你的代码更改，也会以补丁的形式接收别人的代码。增量补丁可以让你轻松地从一个内核版本升级到下一个，无需每次都下载完整的大包，只需应用增量补丁即可，节省带宽和时间。要应用增量补丁，在内核源码目录下运行：

1

patch -p1 < ../patch-x.y.z

内核源码树结构简介

Linux 内核源码树（source tree）被划分为多个目录，每个目录下又包含许多子目录。下表列出了源码树根目录下的主要目录及其说明：

源码树根目录下的一些文件

• COPYING：内核许可证（GNU GPL v2）。
• CREDITS：内核主要开发者名单。
• MAINTAINERS：各子系统和驱动的维护者名单。
• Makefile：内核主 Makefile，用于编译和构建整个内核。

配置内核（Configuring the Kernel）

因为 Linux 源码是开放的，所以你可以在编译前根据自己的需求进行配置和定制。实际上，你可以只为你需要的功能和驱动编译支持。配置内核是编译前的必经步骤。由于内核功能丰富、支持的硬件种类繁多，配置选项也非常多。

内核配置选项（Configuration Options）

内核配置通过一系列以 CONFIG_ 开头的选项控制，例如 CONFIG_SMP 控制对称多处理（SMP）支持。设置该选项即启用 SMP，未设置则禁用。配置选项既决定编译哪些文件，也通过预处理指令影响源码。

• 布尔型（Boolean）：只有 yes 或 no 两种状态。比如 CONFIG_PREEMPT。
• 三态（Tristate）：yes、no 或 module。module 表示编译为可动态加载的模块（.ko 文件）；yes 表示直接编译进内核镜像。
• 字符串或整数：用于指定某些参数值，比如数组大小，这些不会影响编译流程，而是作为宏被源码访问。

发行版内核与自定义内核

各大 Linux 发行版（如 Ubuntu、Fedora）自带的内核都是预编译好的，通常会启用大部分常用功能，并把绝大多数驱动编译为模块，以便支持各种硬件。但如果你想深入学习或开发内核，还是需要自己编译内核，并选择合适的模块。

配置工具

内核提供了多种配置工具：

• 文本命令行工具
  

  1	make config

  逐项询问每个选项，适合有耐心的用户。

• 基于 ncurses 的图形界面
  

  1	make menuconfig

  推荐使用，界面友好，选项分门别类。

• 基于 GTK+ 的图形界面
  

  1	make gconfig

  适合喜欢图形界面的用户。

这些工具会把配置选项分为不同类别（如“处理器类型与特性”），你可以浏览、修改各项配置。

快速生成默认配置

如果你不想从零开始配置，可以用默认配置：

1

make defconfig

配置文件的位置与管理

所有配置选项最终会保存在源码根目录下的 .config 文件中。你也可以直接编辑这个文件（很多内核开发者都这么做），只需搜索并修改对应的配置项即可。

如果你用现有的 .config 文件，或者升级到新内核后想沿用旧配置，可以用：

1

make oldconfig

复制当前内核配置

如果当前内核启用了 CONFIG_IKCONFIG_PROC，你可以直接从 /proc/config.gz 拷贝当前内核的配置：

1
2

zcat /proc/config.gz > .config
make oldconfig

编译内核

配置好后，只需一条命令即可编译内核：

1

make

降低编译输出噪音（Minimizing Build Noise）

在编译内核时，终端会输出大量信息。为了减少这些“噪音”，但又能看到警告和错误，可以将 make 的标准输出重定向到文件：

1

make > ../detritus

如果需要查看详细输出，可以阅读该文件。由于警告和错误信息会输出到标准错误（stderr），通常你不需要关心标准输出。实际上，你可以直接把输出丢到“黑洞”：

1

make > /dev/null

这样所有无用的输出都会被丢弃，只在终端显示警告和错误。

并行编译（Spawning Multiple Build Jobs）

make 支持并行编译，可以同时运行多个编译任务，大大加快多核系统上的编译速度。方法如下：

1

make -jN

其中 N 是并行任务数。通常建议每个处理器核心分配1~2个任务。例如，16核机器可以这样：

1

make -j32 > /dev/null

此外，使用如 distcc 或 ccache 等工具也能进一步提升编译速度。

安装新内核（Installing the New Kernel）

内核编译完成后，需要安装。安装方式依赖于你的硬件架构和引导程序（boot loader），请查阅对应引导程序的文档。

以 x86 + grub 为例：

1. 将 arch/i386/boot/bzImage 复制到 /boot，并命名为如 vmlinuz-version。
2. 编辑 /boot/grub/grub.conf，为新内核添加启动项。

如果使用 LILO：

1. 编辑 /etc/lilo.conf，添加新内核项。
2. 重新运行 lilo 命令。

安装模块（Installing Modules）

模块的安装是自动且与架构无关的。只需以 root 权限运行：

1

make modules_install

System.map 文件

编译过程中还会在源码根目录生成 System.map 文件。它是一个符号查找表，用于将内核符号映射到内存地址，在调试时可以把地址转换为函数或变量名。

总结一下课堂笔记，不然总是放在不知道哪个作业文件夹里找不到

操作系统与内核概述

内核是操作系统的最核心部分，负责管理硬件资源（如CPU、内存、硬盘等），并为上层软件提供服务。内核运行在“内核空间”，拥有对硬件的完全控制权，而普通应用程序运行在“用户空间”，只能通过内核提供的接口访问硬件。

应用程序与内核的交互主要通过系统调用完成。比如：

• 当你在 C 语言程序里调用 printf("hello\n") 时，实际上发生了多层调用。printf() 负责格式化和缓冲数据，最终会调用 write() 函数，把数据写到终端。write() 是一个库函数，它最终会触发 write 系统调用，由内核把数据真正输出到屏幕。
• 类似地，open() 库函数几乎只做一件事，就是调用 open 系统调用，让内核帮你打开一个文件。
• 还有一些库函数，比如 strcpy()，只是单纯地在内存中复制数据，根本不会和内核打交道。

简单来说： - 你写的应用程序通过库函数（如 printf()、open()）间接或直接调用系统调用（如 write、open），由内核完成实际的硬件操作。 - 有些库函数（如 strcpy()）只在用户空间工作，不需要内核参与。

内核还负责处理中断。比如你敲键盘时，键盘控制器会发出中断信号，内核收到后会执行相应的中断处理程序，把你输入的内容读出来。

在任何给定时刻，每个处理器正在做以下三件事中的一件：

• 在用户空间，在进程上下文中执行用户代码
• 在内核空间，在进程上下文中，代表特定进程执行操作（包括空闲进程）
• 在内核空间，在中断上下文中，不与任何进程关联，处理中断

Linux 与经典 Unix 内核设计

• 单一内核/宏内核（Monolithic Kernel）
  经典 Unix 和 Linux 都采用单一内核设计。单一内核就是把所有核心功能（如进程管理、内存管理、文件系统、驱动等）都放在一个大程序里，在同一个内存空间中运行。这样做的好处是：
  • 内核内部各部分可以直接调用彼此的函数，通信效率高，性能好。
  • 设计和实现相对简单。
• 微内核（Microkernel）
  微内核把内核功能拆分成多个独立的“服务器”，有的在内核空间，有的在用户空间。它们之间通过消息传递（IPC）通信。优点是：
  • 各部分相互隔离，一个崩溃不会影响其他部分，系统更稳定。
  • 更容易替换和扩展功能。 缺点是：
    
  • 消息传递比直接函数调用慢，频繁切换上下文会影响性能。
  • 实际上，很多微内核系统（如 Windows NT、Mach）为了性能，后来又把大部分服务放回了内核空间。
• Linux 的做法
  Linux 是单一内核，但吸收了微内核的一些优点，比如模块化设计、支持内核线程、可以动态加载内核模块等。
  • Linux 所有核心功能都在内核空间，通信用直接函数调用，性能高。
  • 同时，Linux 也很灵活，可以按需加载或卸载功能模块。

Linux 虽然继承了 Unix 的理念和 API，但并不基于任何特定 Unix 变体，因此可以灵活选择或创新最佳技术方案。

• 动态内核模块：Linux 支持内核模块的动态加载和卸载，增强了灵活性和可扩展性。
• 对称多处理器（SMP）支持：Linux 从早期就支持 SMP，而许多传统 Unix 系统最初并不支持。
• 抢占式内核：Linux 内核支持抢占，允许内核任务被中断，提高了实时性和响应速度，而大多数传统 Unix 内核不是抢占式的。
• 线程与进程统一：Linux 内核不区分线程和进程，所有进程本质上是一样的，只是有些进程共享资源。
• 面向对象的设备模型：Linux 采用了现代的设备管理方式，如设备类、热插拔和 sysfs。
• 精简与创新：Linux 有选择地实现功能，忽略了被认为设计不佳或无实际价值的传统 Unix 特性（如 STREAMS）。
• 开放与自由：Linux 的功能集来源于开放的开发模式，只有经过充分论证、设计清晰、实现扎实的功能才会被采纳。

Linux 内核版本

• 稳定版 (Stable)： 次版本号为偶数 (如 2.4, 2.6, 4.18, 5.10)。适合生产环境部署，主要更新是错误修复和新驱动。
• 开发版 (Development)： 次版本号为奇数 (如 2.5, 3.1)。代码快速变化，包含实验性功能，不稳定。
• 版本号格式： 主版本.次版本.修订版本[.稳定版本] (如 2.6.30.1)。
  • 主版本.次版本 定义内核系列 (如 2.6)。
  • 修订版本 表示同一系列内的主要发布。
  • .稳定版本 (可选) 表示在主要发布后的小更新，专注于关键错误修复。

62.不同路径

想清楚要怎么推导每个格子，可以怎么推导

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)return 1;
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for(int i = 1;i<m;i++){
            for(int j = 1;j<n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

63. 不同路径 II

问题分析

1. 起点(0,0)未特殊处理：
   • 当i=0, j=0时（起点），您的代码会进入else分支（因为不满足前三个条件）。
   • 在else分支中，它计算dp[i][j] = dp[i-1][j] + dp[i][j-1]，但i-1 = -1、j-1 = -1（非法索引），导致未定义行为（崩溃或错误结果）。
2. 边界条件不完整：
   • 当起点有障碍物时，虽能设为0，但后续计算仍可能依赖无效索引。
   • 初始化dp为全1是冗余的，且可能掩盖问题（实际值会被覆盖）。

修复后的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i<m;i++){
            for(int j = 0; j<n;j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else if(i == 0 && j == 0){
                    dp[i][j] = 1;
                }else if(i == 0){
                    dp[i][j] = dp[i][j-1];
                }else if(j == 0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

343. 整数拆分 （可跳过）

我直接用贪心法，辗转减去3来写了 动态规划思路如下：

• 遍历 \(j\)（\(1 \leq j < i\)），比较 \((i - j) \times j\) 和 \(dp[i - j] \times j\)，取最大值。
• j * (i - j) 是把整数拆分为两个数相乘。
• j * dp[i - j] 是把整数拆分为两个及以上的数相乘。
• 如果用 dp[i - j] * dp[j]，则相当于强制把一个数拆成四份及以上。

递推公式为： dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

为什么还要比较 dp[i] 呢？
因为每次计算 dp[i] 时，都要保证它是当前的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int integerBreak(int n) {
        if(n <= 3)return n-1;
        int pd = 1;
        while(n > 3){
            if(n == 4){
                pd = pd * 4;
                n = 0;
            }else{
                n = n - 3;
                pd = pd * 3;
            }
        }
        if(n > 0){
            pd = pd * n;
        }
        return pd;
    }
};

96.不同的二叉搜索树 （可跳过）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int numTrees(int n) {
        if(n <= 2)return n;
        vector<int> dp(n+1, 0);
        dp[0] = 1;// 方便计算
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<=n ;i++){
            int cnt = 0;
            for(int j = 1; j<=i; j++){
                cnt += dp[j-1] * dp[i-j];
            }
            dp[i] = cnt;
        }
        return dp[n];
    }
};

509. 斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int fib(int n) {
        if(n == 0)return 0;
        if(n == 1){
            return 1;
        }else if(n > 1 ){
            return fib(n-1)+fib(n-2);
        }
        return -1;
    }
};

70. 爬楼梯

递归超时了，得用数组算。如果用两个有效数字的数组重复计算还能再省空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2){
            return n;
        }
        vector<int> dp(n+1, 1);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

746. 使用最小花费爬楼梯

重点是跟着输出的dp数组看推导过程哪里有错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int stairs = cost.size();
        if(stairs == 1)return 0;
        if(stairs == 2)return min(cost[0], cost[1]);
        vector<int> dp(cost.size(), -1);
        dp[stairs-1] = cost[stairs-1];//back()
        dp[stairs-2] = cost[stairs-2];
        for(int i = (stairs-3); i>=0; i--){
            dp[i] = cost[i]+ min(dp[i+1], dp[i+2]);
        }
        // for(auto i: dp){
        //     cout<<i<<" ";
        // }
        return min(dp[0], dp[1]);
    }
};

56. 合并区间

错误分析

1. 合并逻辑错误（关键问题）：

   1	intervals[i] = (intervals[i-1][0], intervals[i][1]); // 错误写法

   • 语法错误：使用逗号运算符 (a, b) 实际返回 b，导致区间被错误赋值为 [0, intervals[i][1]]（起始点丢失）。
   • 逻辑错误：合并时结束点未取两者最大值。正确做法：结束点应为 max(intervals[i-1][1], intervals[i][1])，否则可能丢失覆盖范围（如合并 [1,5] 和 [2,3] 会得到 [1,3] 而非 [1,5]）。
2. 重叠条件不精确：

   1	if(intervals[i-1][1] >= intervals[i][0]) // 边界情况处理不当

   • 题目要求：若前区间结束点 等于 后区间起始点（如 [1,2] 和 [2,3]），应合并为 [1,3]。当前条件 >= 正确，但合并操作错误导致结果异常。
3. 性能问题：
   • 拷贝开销：cmp 函数参数为传值（vector<int> a, b），应改为 传引用（const vector<int>& a, b）避免不必要的拷贝。
   • 额外空间：使用 incl 标记数组非必需，经典解法可优化空间复杂度。
4. 边界处理缺失：
   • 当输入为空时，应直接返回空数组，但代码未显式处理 intervals.size() == 0 的情况（依赖 size <= 1 返回，逻辑正确但不够清晰）。

比较合并贪心解法（可以ac）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) { // 传引用
        return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        if (intervals.size() <= 1) return intervals;
        vector<bool> incl(intervals.size(), true);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i-1][1] >= intervals[i][0]) {
                // 正确合并：起始点取前一个，结束点取两者最大值
                intervals[i][0] = intervals[i-1][0];
                intervals[i][1] = max(intervals[i-1][1], intervals[i][1]);
                incl[i-1] = false;
            }
        }
        vector<vector<int>> result;
        for (int j = 0; j < intervals.size(); j++) {
            if (incl[j]) result.push_back(intervals[j]);
        }
        return result;
    }
};

经典贪心解法思路

1. 按起始点排序区间。
2. 动态合并：
   • 初始化结果数组 merged。
   • 遍历每个区间：
     • 若 merged 为空 或 当前区间与 merged 最后一个区间不重叠（current[0] > merged.back()[1]），直接加入。
     • 否则，更新 merged 最后一个区间的结束点：max(merged.back()[1], current[1])。

经典贪心解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (const auto& interval : intervals) {
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            } else {
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }
        return merged;
    }
};

738.单调递增的数字

题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。 例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。 > 这一点如果想清楚了，这道题就好办了。

此时是从前向后遍历还是从后向前遍历呢？ 从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。 这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。 那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

处理逻辑易错

• 当发现 digits[i-1] < digits[i] 时，代码只修改了当前低位（设为9）和当前高位（减1），但没有处理更高位的影响
  • 高位减1后可能破坏与更前高位的单调性（例：100 的处理）
  • 未将所有受影响低位置为 9（例：100 的个位未置9）
• 示例验证（输入 n=100）： 分解 digits = [0, 0, 1] # 个位=0, 十位=0, 百位=1 遍历 i=1：0==0 → 跳过 遍历 i=2：0<1 → 十位置9, 百位减1 → digits=[0,9,0] 结果 = 010⁰ + 910¹ + 0*10² = 90 # 预期应为99

数字组合计算易错

• 错误代码：res += 10 * (i-1) * digits[i-1]
• 问题：
  • 错误使用乘法 10*(i-1) 而非指数 10^(i-1)
  • 导致计算结果完全错误（如个位贡献 10*0*digits[0]=0）
• 正确计算：应使用 pow(10, i-1) * digits[i-1]

💡 黄金法则：需要修改数字的每一位时，优先考虑 to_string → 字符串处理 → stoi 流程，比数学运算更直观可靠！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string(n);
        int flag = str.size();
        for(int i = (str.size() - 1);i>0;i--){
            if(str[i-1] > str[i]){
                flag = i;
                str[i-1]--;
            }
        }
        for(int i = 0; i<str.size();i++){
            if(i >= flag){
                str[i] = '9';
            }
        }
        return stoi(str);
    }
};

968.监控二叉树

其实我的思路和题解的想法已经很接近了，但是总结地没有那么到位，导致缺漏数量的情况

确定遍历顺序

在二叉树中可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。

1
2
3
4
5
6
7
8

int traversal(TreeNode* cur) {
    // 空节点，该节点有覆盖
    if (终止条件) return ;
    int left = traversal(cur->left);    // 左
    int right = traversal(cur->right);  // 右
    逻辑处理                            // 中
    return ;
}

返回状态类型

• 0：该节点不在摄像头覆盖范围
• 1：本节点有摄像头
• 2：本节点在摄像头覆盖范围

递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖），这样就可以在叶子节点的父节点放摄像头了。

1
2

// 空节点，该节点有覆盖
if (cur == NULL) return 2;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int cmr = 0;
    int coverStat(TreeNode* root){
        if(!root)return 2;
        int left = coverStat(root->left);
        int right = coverStat(root->right);
        if(left == 2 && right == 2){
            return 0;
        }
        if(left == 0 || right == 0){
            cmr++;
            return 1;
        }
        if(left == 1 || right == 1){
            return 2;
        }
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        int rcv = coverStat(root);
        if(rcv == 0)cmr++;
        return cmr;
    }
};

452. 用最少数量的箭引爆气球

💡 题解逻辑如下：

• 如果当前气球的 起点 > 上一个交集的最右端点，说明它不能和之前的箭共用，需要再发一支箭。
  • 更新 end 为当前气球的 end，建立新的交集窗口。
• 否则，当前气球和前面的箭是重叠的，它们能一起被射中。
  • 更新 end = min(end, points[i][1]) 是为了缩小交集范围，因为未来能共用这支箭的气球，必须跟所有已合并气球都有交集。

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

    class Solution { public: static bool cmp(vector<int> a, vector<int> b){ return a[0] < b[0]; } int findMinArrowShots(vector<vector<int>>& points) { sort(points.begin(), points.end(), cmp); int arr = 1; if(points.size() == 0)return 0; int end = points[0][1]; for(int i = 1; i<points.size();i++){ if(end < points[i][0]){ end = points[i][1]; arr++; }else{ end = min(end, points[i][1]); } } return arr; } };

435. 无重叠区间

思路步骤：

1. 排序区间（预处理）：
   • 使用自定义比较器 cmp 对所有区间进行排序。
   • 排序规则：按起始点升序（优先比较 intervals[i][0]）。若起始点相同，则按结束点升序（比较 intervals[i][1]）。
   • 按结束点排序效率可以更高
2. 初始化关键变量：
   • 最大不重叠区间计数器 intv = 1（至少包含第一个区间）。
   • 当前覆盖的结束点 end = intervals[0][1]（以第一个区间的结束点作为初始基准）。
3. 遍历处理每个区间（从第二个区间开始，即 i = 1）：
   • 检查重叠：比较当前区间起始点 intervals[i][0] 与当前结束点 end。
     • 情况1：有重叠（intervals[i][0] < end）：
       • 更新 end = min(end, intervals[i][1])（关键贪心选择：取最小结束点）。
       • 不增加计数器 intv（因为重叠区间不能同时保留，这里隐含选择了结束点更小的区间以正确计算无重叠区间个数）。
     • 情况2：无重叠（intervals[i][0] >= end）：
       • 更新 end = intervals[i][1]（将结束点设为当前区间的结束点）。
       • 增加计数器 intv++（表示成功添加一个新的不重叠区间）。
4. 计算结果：
   • 需要移除的最小区间数 = 总区间数 intervals.size() - 最大不重叠区间数 intv。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    static bool cmp(vector<int> a, vector<int>b){
        if(a[0] < b[0]){
            return true;
        }else if(a[0] == b[0] && a[1] < b[1]){
            return true;
        }
        return false;
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        // for(auto i: intervals){
        //     cout<<i[0]<<" "<<i[1]<<", ";
        // }
        int intv = 1;
        int end = intervals[0][1];
        if(intervals.size() <= 1)return 0;
        for(int i = 1; i< intervals.size();i++){
            if(intervals[i][0] < end){
                end = min(end, intervals[i][1]);
            }else{
                end = intervals[i][1];
                intv++;
            }
        }
        return intervals.size() - intv;
    }
};

763.划分字母区间

由题解： 在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。 可以分为如下两步：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27] = {0};
        for(int i = 0;i<s.size();i++){
            hash[s[i] - 'a'] = i;
        }
        vector<int> result;
        int right = 0;
        int end = 0;
        for(int i = 0;i<s.size();i++){
            right = max(right, hash[s[i] - 'a']);
            if(right == i){
                result.push_back(right - end +1);
                right++;
                end = right;
            }
        }
        return result;
    }
};

134. 加油站

初始思路：

1. 先找一段正收益连续区间（油量盈余最大的起点）
   • 用 curMax 累加正收益段，记录最大盈余时的起点 maxSt。
   • 如果遇到油不够的站点，就重置 curMax 并将 start 改为下一个站点。
   • 如果到最后一站没找完，循环一圈回来继续查找。
2. 再从 maxSt 模拟绕一圈
   • 从 maxSt 出发，逐站加减油量，确认是否能绕完整圈。
   • 只要中途油量不足就返回 -1。

⚠️ 存在的问题：

其实这种逻辑完善完善也是可以做出来的，题解中有，就是比较繁琐

✅ 更优的做法（贪心 + 一次遍历）：

只要 总油量 ≥ 总花费，一定有解。解的起点是：当前累加油量一旦为负，就从下一个站点重启。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tank = 0;
        int startInd = 0;
        int total = 0;
        for(int i = 0; i < gas.size(); i++){
            int store = gas[i] - cost[i];
            total += store;
            tank += store;
            if(tank < 0){
                startInd = i + 1;
                tank = 0;
            }
        }
        return total < 0 ? -1 : startInd;
    }
};

135. 分发糖果

这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就会顾此失彼。 题解采用了两次贪心的策略： * 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。 * 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candy;
        candy.push_back(1);
        for(int i = 1;i<ratings.size();i++){
            if(ratings[i] > ratings[i-1]){
                candy.push_back(candy[i-1] + 1);
            }else{
                candy.push_back(1);
            }
        }
        int total = 0;
        for(int i = (ratings.size()-1); i>0;i--){
            if(ratings[i-1] > ratings[i] && candy[i-1] <= candy[i]){
                candy[i-1] = candy[i] + 1;
            }
            total += candy[i];
        }
        total += candy[0];
        return total;
    }
};

860.柠檬水找零

这题不用map,用两个整数表示5和10的钞票数也是可以的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        map<int, int> changes;
        changes[5] = 0;
        changes[10] = 0;
        for(int i = 0; i<bills.size();i++){
            int exc = bills[i] - 5;
            if(exc == 0){
                changes[5]++;
            }else if(exc == 5){
                changes[5]--;
                changes[10]++;
            }else if(exc == 15){
                if(changes[10] >= 1){
                    changes[10]--;
                    changes[5]--;
                }else{
                    changes[5] -= 3;
                }
            }
            if(changes[5] < 0)return false;
        }
        return true;
    }
};

406.根据身高重建队列

看题解可知，当身高是按照从高到矮，第二个数字从小到大排列的时候，按顺序插入即可满足条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    static bool cmp(const vector<int> a, const vector<int> b){
        if(a[0] > b[0]){
            return true;
        }else if(a[0] == b[0] && a[1] < b[1]){
            return true;
        }
        return false;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> que;
        for(int i = 0; i<people.size();i++){
            int insPos = people[i][1];
            std::list<vector<int>>::iterator p = que.begin();
            while(insPos > 0){
                p++;
                insPos--;
            }
            que.insert(p, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};