Maxw的小站

代码随想录 | 八股-c++动态内存分配

发表于 2025-07-26 分类于 comp basic

new和malloc有什么区别

new和malloc在C++中都用于动态内存分配，但它们之间有几个关键的区别：

语法层面： new是C++的操作符，可以直接用来分配对象或数组。 malloc是一个函数，通常需要包含头文件，并且只分配原始内存。类型安全： new是类型安全的，它会根据分配的对象类型进行正确的内存分配和构造函数调用。 malloc 不是类型安全的，它只分配原始内存，不调用构造函数。返回类型是 void*，需要强制类型转换为具体的指针类型。构造与析构：使用 new 分配的对象在对象生命周期结束时需要使用 delete 来释放，delete 会自动调用对象的析构函数。使用 malloc 分配的内存需要使用 free 来释放，free 不会自动调用析构函数，因此如果分配的是对象数组，需要手动调用析构函数。异常安全性： new在分配失败时会抛出std::bad_alloc异常。 malloc在分配失败时返回NULL指针。管理机制： C++中的new和delete通常由编译器实现，可能包含一些额外的内存管理机制。 C语言的malloc和free由C标准库提供，与编译器无关。总结来说，new和malloc都是动态内存分配的手段，但new提供了类型安全和构造/析构的自动化，而malloc则提供了更底层的内存分配方式，需要手动管理构造和析构。在C++中，推荐使用new来分配对象，以保持类型安全和自动化的资源管理。

delete 和 free 有什么区别？

delete和free都是用来释放动态分配的内存，但它们有不同的使用方式：

语法：

delete是C++中的关键字，用于释放由new分配的对象。 free是C语言中的函数，通常包含在<stdlib.h>头文件中，用于释放由malloc分配的内存。对象销毁：

当使用 delete 释放对象内存时，C++ 编译器会自动调用对象的析构函数，释放与对象相关的资源，并执行对象的清理工作。 free 仅释放内存，不调用析构函数。因此，如果使用 malloc 分配了 C++ 对象的内存，需要手动调用析构函数后再调用 free。数组处理：

如果是数组，C++提供了delete[]来释放整个数组的内存，而C语言中仍然使用free，没有区分单个对象和数组。返回值:

free 没有返回值，即使内存释放失败，也不会反馈任何信息。

delete 之后，指针会自动置为 nullptr

类型检查:

delete 进行类型检查，确保删除的对象类型与 new 分配时的类型一致。

free 不进行类型检查，因为它只处理 void* 类型的指针。

总结来说，delete和free都是用来释放动态内存的，但它们分别用于C++和C语言中的内存管理。delete适用于C++对象，会自动调用析构函数；而free适用于C语言分配的内存，不涉及对象的析构。

堆区和栈区的区别

堆（Heap）和栈（Stack）是程序运行时两种不同的内存分配区域

内存分配：

栈是由编译器自动管理的，用于存储局部变量和函数调用的上下文信息。栈上的对象在定义它们的块或函数调用结束后自动销毁。栈的内存分配和释放速度很快，因为栈的内存管理是连续的，不需要搜索空闲内存。堆由程序员手动管理的，用于存储动态分配的对象。堆上的对象需要程序员手动释放，否则可能导致内存泄漏。堆的内存分配和释放速度通常比栈慢，因为可能需要搜索合适的内存块，并且涉及内存碎片整理。大小限制：

栈的大小通常有限制，远小于堆的大小，且在不同系统和编译器中可能不同。堆的大小通常很大，受限于系统可用内存。使用场景：

栈主要用于存储函数参数、局部变量等。堆用于存储生存期不受限于单个函数调用的对象，如使用 new 或 malloc 分配的对象。

补充：如何定义只能在堆上或栈上生成对象的类

在 C++ 中，可以通过控制构造函数和析构函数的访问权限来限制对象只能在堆上或栈上创建。以下是两种实现方式的详细说明和代码示例：

1. 只能在堆上创建对象（禁止栈上创建）

核心原理：私有析构函数 + 智能指针管理生命周期
关键点： - 私有析构函数阻止栈对象自动销毁 - 静态工厂函数返回智能指针 - 智能指针自定义删除器调用 destroy() - destroy() 调用 delete this（需谨慎使用） - 禁用拷贝构造/赋值

#include <memory>

class HeapOnly {
public:
    // 工厂函数：返回带有自定义删除器的 unique_ptr
    static std::unique_ptr<HeapOnly, void(*)(HeapOnly*)> create() {
        return {
            new HeapOnly(), 
            [](HeapOnly* p) { p->destroy(); } // 自定义删除器
        };
    }

    // 销毁函数（必须公开）
    void destroy() {
        delete this; // 调用私有析构函数
    }

    // 禁用拷贝操作
    HeapOnly(const HeapOnly&) = delete;
    HeapOnly& operator=(const HeapOnly&) = delete;

private:
    HeapOnly() = default;       // 私有构造
    ~HeapOnly() = default;      // 私有析构
};

// 使用示例
auto obj = HeapOnly::create();  // 只能在堆上创建

2. 只能在栈上创建对象（禁止堆上创建）

核心原理：禁用 new 操作符

class StackOnly {
public:
    StackOnly() = default;
    ~StackOnly() = default;

private:
    // 禁用 new 操作符
    void* operator new(size_t) = delete;
    void* operator new[](size_t) = delete;
    void* operator new(size_t, void* p) = delete; // 禁用 malloc + placement new
};

// 使用示例
StackOnly stackObj;           // 合法：栈上创建
// auto heapObj = new StackOnly(); // 编译错误：new 被禁用

⚠️ 注意：delete this 是特殊技术，必须确保： - 对象通过 new 创建 - 调用 delete this 后不再访问任何成员 - 通常只用于精确控制生命周期的场景

操作系统基础 | 3.4 系统调用实验

发表于 2025-07-23 更新于 2025-09-27 分类于 os basic ， lab

必做练习

练习1

准备好实验报告

练习2

我们将通过 libc 包装器发起系统调用（标准用户程序调用内核的方式）。系统调用完整列表可通过 man 2 syscalls 查看手册页。
1. 启动树莓派，在终端中脱离 Linux 源码目录新建用户程序目录
2. 创建文件 lib_call.c，编写 C 程序：
- 使用库函数 getuid 读取并打印用户 ID
- 尝试用 setuid 将 ID 设为 0（root）并报告是否成功
- 再次读取并打印用户 ID
3. 通过 man 2 getuid 和 man 2 setuid 查阅：
- 函数调用语法和返回值类型
- 编译所需的头文件
4. 错误检查：若 setuid 失败，输出错误原因（使用 strerror(errno)）。
- 相关手册页：man 3 printf, man 3 strerror, man 3 errno
5. 在实验机上编译运行：

1	gcc lib_call.c -o lib_call && ./lib_call

练习3

从树莓派用户程序目录执行：
1. 通过 sftp 从 shell.cec.学校简称.edu 获取 lib_call.c
2. 在树莓派上编译并运行程序（分别用普通用户和 sudo 权限运行）

练习4

修改程序使用原生系统调用接口（man 2 syscall）：
1. 复制 lib_call.c 为 native_call.c
2. 将 getuid/setuid 替换为 syscall
3. 通过 Linux 源码确定 ARM 系统调用号：
- 查看 arch/arm/include/uapi/asm/unistd.h
- 查看生成的 arch/arm/include/generated/uapi/asm/unistd-common.h
4. 使用常量（如 __NR_getuid）而非硬编码数字
5. 可能需包含头文件 asm/unistd.h
6. 在树莓派上编译运行

练习5

为内核添加两个新系统调用（各打印一条内核日志）：
任务清单
1. 在内核中声明函数原型
2. 实现函数逻辑
3. 分配系统调用号
4. 更新 ARM 系统调用表
5. 更新系统调用总数

操作步骤
1. 登录用于交叉编译的Linux主机 → 进入 Linux 源码目录
2. 修改前备份文件（如 cp syscalls.h syscalls.h.092125）

声明函数原型（在 include/linux/syscalls.h 底部添加）：

1
2
3

// 092125
asmlinkage long sys_noargs(void); 
asmlinkage long sys_onearg(int arg);

练习6

实现系统调用函数：
1. 在 arch/arm/kernel/ 创建文件：
- sys_noargs.c（无参数函数）
- sys_onearg.c（带参数函数）
2. sys_noargs.c 内容参考

#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/sched.h>
#include <linux/syscalls.h>

//这个宏定义了一个不携带参数的系统调用，它定义于syscalls.h
SYSCALL_DEFINE0( noargs ){
// print out a simple message indicating the function was called, and return SUCCESS
printk("Someone invoked the sys_noargs system call");
return 0;  
}

sys_onearg.c 模板：

//这个宏定义了携带一个参数的系统调用，它定义于syscalls.h
SYSCALL_DEFINE1(onearg, int, arg) {
    printk("Received argument: %d\n", arg); 
    return 0; // 返回适当值
}

练习7

添加文件到构建系统：
修改 arch/arm/kernel/Makefile：
1. 备份原文件(例如Makefile.092125) 2. 在 obj-y 列表末尾添加（不在 \ 后）：

1	sys_noargs.o sys_onearg.o

练习8

更新系统调用表：
修改 arch/arm/tools/syscall.tbl：
1. 备份原文件（例如 syscall.tbl.092125 ） 2. 在末尾添加（分配新调用号）：

1	(调用号) ... （系统调用名称）（实际调用的函数名）

练习9

编译并验证新内核：
1. 在 Linux 源码根目录执行：

1	make clean

2. 修改本地版本标识：
- 编辑 .config 文件
- 更新 CONFIG_LOCALVERSION 值（如 -syscallstudio）
3. 按实验1/2的步骤编译安装内核
4. 树莓派上运行：

uname -a

练习10

调用新系统调用：
1. 通过 sftp 获取 arch/arm/include/generated/uapi/asm/unistd-common.h
2. 复制到 GCC 头文件目录：

1	sudo cp unistd-common.h /usr/include/arm-linux-gnueabihf/asm

3. 创建 new_call.c（基于 native_call.c）：
- 将 getuid 调用号替换为 __NR_...
- 将 setuid 调用号替换为 __NR_...
- 为单参数调用声明变量（勿直接传常量）
4. 编译运行后检查内核日志：

dmesg

可选拓展练习

完成任意拓展练习后简述收获（附问题答案）。

练习1
用汇编接口实现系统调用（参考课堂 ARM 调用流程），使用 GCC 内联汇编（asm 扩展）。
> 提示：详细流程见 man 2 syscall，内核入口代码见 arch/arm/kernel/entry-common.S。

练习2
实现读取周期计数器（CCNT）的系统调用：
1. 下载性能监控头文件至 arch/arm/include/asm
2. 声明函数原型：asmlinkage long sys_read_ccnt(unsigned long long *val)
3. 创建 sys_read_ccnt.c（参考模板）
4. 更新 Makefile 和 syscall.tbl
5. 编写程序连续调用两次，计算调用耗时（周期数）

练习3
修复 read_ccnt 的安全缺陷：
1. 使用 copy_to_user() 替代直接写入用户指针
2. 失败时返回 -EFAULT

代码随想录 | 刷题-动态规划6

发表于 2025-07-23 更新于 2025-08-06 分类于 leetcode

322. 零钱兑换

#include <limits>
#include <algorithm> // 包含 std::min 和 std::max
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, std::numeric_limits<int>::max());// 每个amount需要的最少coin数
        // 第一遍遍历需要把coins中有的coin数置1，所以dp[0] = 0方便+1
        dp[0] = 0;
        // 针对每个amount, 遍历减去coin看哪一种最少
        for(int i = 0; i<=amount; i++){
            for(int j = 0; j< coins.size();j++){
                if((i - coins[j]) >= 0 && dp[i - coins[j]] < std::numeric_limits<int>::max()){
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == std::numeric_limits<int>::max() ? -1 : dp[amount];
    }
};

279.完全平方数

class Solution {
public:
    int numSquares(int n) {
        // 完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) { // 遍历背包
            for (int j = 1; j * j <= i; j++) { // 遍历物品
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};

139.单词拆分

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for(int i = 1; i<=s.size(); i++){
            for(int j = 0; j<i; j++){
                string subS = s.substr(j, i-j);
                if(wordSet.find(subS) != wordSet.end() && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

操作系统项目 | perf验证性能瓶颈

发表于 2025-07-19 分类于 rust os

使用 `perf` 验证性能瓶颈

用 perf 找系统慢在哪，就像给系统做一次‘全身CT扫描’加‘血液化验’。在我那个操作系统框架项目里，我们特别关心调度算法在任务多到快‘撑爆’的时候表现如何（超负荷场景）。这个过程大概是这样的：

‘挂号’与‘检查’ (启动Perf & 记录数据)：
- 我先给系统‘挂号’，告诉 perf 我要检查什么：CPU 干了啥、内存怎么用的、任务等了多久、程序内部函数调用了多少次等等。这些信息就是‘检查项目’（perf 事件，如 cycles, instructions, cache-misses, context-switches, sched:sched_stat_runtime, sched:sched_stat_wait 等）。
- 然后，我让系统开始‘干活’（运行特定负载，模拟超负荷），同时 perf 就像个精密的仪器在旁边‘抽血化验’、‘拍片子’，全程记录下所有关键指标（perf record -e <事件列表> -ag -- sleep 30 或针对特定进程/命令）。
- 这个负载是精心设计的，包含不同类型（CPU计算狂、慢悠悠的I/O读写手、要求准时完成的‘急脾气’任务）和不同数量的任务，把它们一股脑儿塞给系统，看它啥时候‘顶不住’。
‘看化验单’与‘读CT片’ (分析Perf报告)：
- 等系统跑完，perf 会生成一份厚厚的‘检查报告’（perf report）。这份报告特别有用：
  - ‘谁最累？’ (CPU时间分布)： 报告会列出哪个程序、哪个函数吃掉最多的CPU时间（Overhead 列）。如果某个调度器函数或者内核里处理任务切换/通信(IPC)的函数占比异常高，那它可能就是‘罪魁祸首’。
  - ‘效率高不高？’ (指令效率)： 我重点看 CPI 或 IPC。CPI 是说CPU执行一条指令平均花了多少个时钟周期，IPC 是反过来（一个周期执行多少条指令）。理想值： 现代CPU在跑得很顺的代码时，IPC 应该接近1甚至更高（比如1.5-2.0+）。瓶颈信号： 如果整个系统或者关键函数的 IPC 掉得很低（比如低于0.5），或者 CPI 飙升（比如>2.0），那CPU可能没在高效干活，而是在‘空等’或者‘干杂活’。
  - ‘等得久不久？’ (调度延迟)： 报告里能看到任务从‘准备好’到‘真正上CPU跑’等了多久（sched:sched_stat_wait）。合理范围： 在超负荷前，这个等待时间应该比较稳定且符合预期（比如微秒到毫秒级，看系统要求）。瓶颈信号： 如果这个等待时间在超负荷时急剧增加（比如从毫秒级跳到几十甚至几百毫秒），或者大量时间花在 sched 相关的内核函数上，说明调度器本身或者任务太多成了瓶颈，任务在‘排队等CPU等太久’。
  - ‘找东西慢不慢？’ (缓存失效)： cache-misses 事件特别重要。CPU从自己高速缓存(L1/L2/L3)拿数据比去慢悠悠的主内存(RAM)拿快百倍。合理范围： 有一定比例的 cache-misses 是正常的。瓶颈信号： 如果 cache-misses 率非常高（比如LLC Last Level Cache miss rate > 5-10%，具体看CPU和负载），或者某个关键数据结构相关的代码段 cache-misses 特别多，说明CPU经常‘找不到需要的东西’，得跑去慢速内存取，这会严重拖慢速度，是内存访问瓶颈的典型标志。
  - ‘沟通顺畅吗？’ (IPC开销)： 在微内核里，任务间沟通(IPC)是大事。我会专门看花在内核处理IPC消息的函数（比如消息复制、权限检查、调度切换）上的时间占比。合理范围： IPC本身就有成本，时间占比应该相对稳定。瓶颈信号： 如果IPC处理时间占比在超负荷时不成比例地暴增，或者 context-switches (上下文切换次数) 高得吓人，说明系统资源大量消耗在‘传话’和‘换人’上了，任务本身的‘正事’反而没时间做，这就是通信开销过大或调度切换太频繁的瓶颈。
‘病灶’在哪？ (我们发现的瓶颈)： 在我们的超负荷测试中，perf 的‘化验单’清晰地指出了几个‘病灶’：
- ‘沟通成本’太高 (IPC开销陡增)： 当任务数量超过某个阈值，花在内核处理IPC上的CPU时间占比从正常的 ~15% 一下子跳到 40%+！perf report 显示 ipc_send, ipc_receive 及相关内核锁函数耗时剧增。同时 context-switches 也翻倍了。这说明微内核架构的‘双刃剑’——隔离性好但沟通成本高——在重压下成了主要瓶颈。
- ‘找东西’越来越慢 (Cache效率下降)： LLC cache-misses 率在超负荷时从 ~3% 升高到 12%+。结合 annotate 功能看热点代码，发现是调度器内部的任务队列数据结构访问冲突加剧，导致多个CPU核心频繁互相使对方的缓存失效 (False Sharing)，逼得CPU频繁去慢速内存找数据。
- ‘急脾气’任务被耽误 (调度延迟波动)： sched:sched_stat_wait 显示实时任务的等待时间方差(jitter)在超负荷时变得很大，偶尔出现远超截止期限的等待峰值。perf 指向调度器在重载下决策变慢，以及非实时任务过多挤占了CPU资源。
‘化验单’靠谱吗？ (判断数据合理性)： 光看一次‘化验’结果不行，得判断数据靠不靠谱：
- ‘对照实验’： 我会在相同硬件、相同负载下，跑不同的调度算法配置或内核版本，用 perf 收集数据对比。如果瓶颈指标（如IPC耗时、Cache Miss率）的变化趋势一致，且能解释性能差异（如吞吐量下降、延迟上升），数据就合理。
- ‘符合常识’： 数据要符合计算机原理。比如：
  - CPI 不可能无限低（受限于CPU物理极限）。
  - 一个纯计算任务如果 IPC 很低且 cache-misses 不高，那瓶颈可能在指令依赖或分支预测失败(branch-misses)。
  - 调度延迟不可能为0，总有个基础开销。
- ‘多指标印证’： 单一指标可能误导。比如高 %sys (内核态CPU占用) 是瓶颈信号，但必须结合 perf report 看具体是内核哪部分耗时。高 cache-misses 是信号，但要看 annotate 确认热点代码位置是否合理。
- ‘可重复性’： 多次运行测试，关键指标（如平均延迟、最大延迟、瓶颈函数占比）的波动应在小范围内，结果要能稳定复现。
- ‘符合理论模型’ (效用边界分析)： 我们用 perf 采集的响应时间、CPU利用率等数据，输入到调度理论模型（如排队论模型）中计算‘效用边界’。如果模型预测的系统饱和点、性能拐点与 perf 观测到的实际瓶颈出现点（如IPC开销暴增、延迟突变的负载阈值）能吻合，那这些 perf 数据及其揭示的瓶颈就非常可信了。

代码随想录 | 刷题-动态规划5

发表于 2025-07-12 更新于 2025-07-23 分类于 leetcode

518. 零钱兑换 II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<uint64_t> dp(amount + 1, 0); // 防止相加数据超int
        dp[0] = 1;
        // 第一轮循环应该将所有j = coins[i]置1
        // 想清楚这一点，就可以明确组合数的状态转移方程和排列数不一样
        for(int i = 0; i<coins.size(); i++){
            int coin = coins[i];
            for(int j = coin; j<(amount+1); j++){
                dp[j] += dp[j - coins[i]];
            }
            // cout<<"coins[i]="<<coins[i]<<endl;
            // for(int d:dp)cout<<d<<' ';
            // cout<<endl;
        }
        
        return dp[amount];
    }
};

377. 组合总和 Ⅳ

如果求组合数就是外层for循环遍历物品，内层for遍历背包，因为物品处理顺序固定。如果求排列数就是外层for遍历背包，内层for循环遍历物品，因为每个容量下都重新扫描所有物品。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for(int j = 0;j<=target;j++){
            for(int i = 0; i<nums.size();i++){
                if((j - nums[i])>=0 && dp[j] <= INT_MAX - dp[j - nums[i]]){
                    dp[j] += dp[j - nums[i]];
                }
            }
            // for(auto d:dp)cout<<d<<' ';
            // cout<<endl;
        }
        return dp[target];
    }
};

70. 爬楼梯（进阶）

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

代码随想录 | 刷题-动态规划4

发表于 2025-07-10 更新于 2025-07-13 分类于 leetcode

01背包问题中一维和二维 dp 的遍历顺序

一维 dp：倒序遍历容量

原因：倒序遍历可以保证每个物品只被放入一次。
原理：每次更新 dp[j] 时，使用的是上一轮（未加入当前物品）的状态，避免重复加入同一个物品。
举例：
- 物品0，重量1，价值15
- 正序遍历：dp[2] = dp[1] + 15 = 30（物品0被加了两次，错误！）
- 倒序遍历：dp[2] = dp[1] + 15 = 15，dp[1] = dp[0] + 15 = 15（每个容量只加一次物品0）

二维 dp：正序遍历容量

原因：二维 dp 的 dp[i][j] 都是通过上一层 dp[i-1][j] 计算的，本层不会覆盖上一层，所以不会重复加入物品。
原理：每一层代表一个物品，状态转移只依赖于上一层，天然保证每个物品只选一次。

1049. 最后一块石头的重量 II

目标：将所有石头分成两组，使两组总重量尽量接近，最后剩下的石头重量就是两组重量差的绝对值。
转化为01背包问题：每个石头只能选一次，背包容量为所有石头重量和的一半，尽量让一组的重量最大且不超过容量。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        int hlf_sum = 0;
        for(int s: stones){
            sum += s;
        }
        hlf_sum = sum / 2; // 注意hlf_sum / 2是向下取整的

        vector<int> dp(1501, 0); // 一定要保证dp[j]是可以比较的，所以我们选择重量为j
        for(int i = 0; i<stones.size();i++){
            for(int j = hlf_sum; j>=stones[i]; j--){
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        
        return sum - dp[hlf_sum] * 2;
    }
};

494. 目标和

该问题可以转化为一个子集和问题：在数组中找到一些数字，使它们的和等于 (target + sum(nums)) / 2（记为 bagSize），每个数字只能使用一次。以下是详细步骤：

问题转化：
- 设加法总和为 x，则减法总和为 sum - x。
- 根据条件 x - (sum - x) = target，解得 x = (target + sum) / 2。
- 问题转化为：在 nums 中选取若干数字，使它们的和等于 bagSize，求选取方案数。
边界条件：
- 若 abs(target) > sum，无解。
- 若 (target + sum) 为奇数，无解（bagSize 必须是整数）。
动态规划：
- 使用一维数组 dp[j] 表示装满容量 j 的背包的方案数。
- 初始化 dp[0] = 1（空集方案）。
- 遍历每个数字，逆序更新 dp 数组（避免重复使用数字）。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 回溯法容易超时
        int sum = 0;
        for(int n:nums){
            sum += n;
        }
        int sz = (target + sum) / 2;
        if((target + sum) % 2 == 1)return 0;
        if(abs(target) > sum)return 0;
        vector<int> dp(sz+1, 0);
        dp[0] = 1;
        for(int i = 0; i<nums.size();i++){
            for(int j = sz; j >= nums[i]; j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[sz];
    }
};

代码解释

初始化：
- dp[0] = 1：表示容量为0的背包有1种方案（不选任何数字）。
- 其他位置初始化为0。
遍历更新：
- 对每个数字 num，从 bagSize 到 num 逆序遍历。
- 更新公式：dp[j] += dp[j - num]，表示：
  - 不选 num达成j：方案数保持 dp[j]。
  - 选 num达成j：方案数加上 dp[j - num]（剩余容量 j - num 的方案数）。
示例：
- nums = [1, 1, 1, 1, 1], target = 3：
  - total = 5, bagSize = (3 + 5) / 2 = 4。
  - dp 数组初始为 [1, 0, 0, 0, 0]。
  - 遍历每个 1 后，dp[4] = 5（5种组合方式）。

复杂度

时间复杂度：O(n × bagSize)，其中 n 为数组长度。
空间复杂度：O(bagSize)。

474.一和零

本题容易被看成多重背包问题，识别清楚问题本质就容易做了

class Solution {
public:
    vector<int> count(string s){
        vector<int> cnt;
        int zeroes = 0, ones = 0;
        for(char c:s){
            if(c == '0')zeroes++;
            if(c == '1')ones++;
        }
        cnt.push_back(zeroes);
        cnt.push_back(ones);
        return cnt;
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i = 0; i<strs.size();i++){
            vector<int> cnt = count(strs[i]);
            if(cnt[0] > m || cnt[1] > n){
                continue;
            }
            for(int a = m; a >= cnt[0]; a--){
                for(int b = n; b >= cnt[1]; b--){
                    dp[a][b] = max(dp[a][b], dp[a-cnt[0]][b-cnt[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

操作系统基础 | 信号量和条件变量

发表于 2025-07-05 更新于 2025-07-08 分类于 os basic

🚦 信号量 (Semaphore) - 停车场模型

口诀：“计数资源，进出加减”
- 像一个停车场管理员： - wait() = 抬起杆子放车进（资源-1） - post() = 落下杆子放车出（资源+1） - 核心：管数量（剩余车位）

// 超简版信号量实现（C++20标准）
#include <semaphore>
std::counting_semaphore<5> parking(5); // 5个车位

void car(int id) {
    parking.acquire();      // 等车位（杆子抬起）
    std::cout << "Car " << id << " parked\n";
    parking.release();      // 开走（杆子落下）
}

🚥 条件变量 (Condition Variable) - 奶茶店模型

口诀：“条件不满足，解锁等通知”
- 像奶茶店取餐： - wait() = 没奶茶时放下号码牌睡觉 - notify() = 奶茶做好后叫号唤醒顾客 - 核心：管条件（奶茶是否做好）

// 条件变量基本结构
std::mutex mtx;
std::condition_variable cv;
bool milktea_ready = false; // 关键条件

// 顾客线程
void customer() {
    std::unique_lock lock(mtx);
    cv.wait(lock, []{ return milktea_ready; }); // 没奶茶就睡
    std::cout << "Got milktea!\n";
}

// 店员线程
void staff() {
    {
        std::lock_guard lock(mtx);
        milktea_ready = true; // 奶茶做好
    }
    cv.notify_all(); // 大喊：奶茶好了！
}

🔑 对比记忆表

特征	信号量	条件变量
核心思想	资源计数器（还剩几个？）	条件检查（事情发生了吗？）
操作	`wait()`减资源，`post()`加资源	`wait()`休眠，`notify()`唤醒
锁依赖	自带锁机制	必须搭配mutex使用
适用场景	连接池/限流	任务协调/事件等待
生活比喻	停车场进出系统	奶茶店叫号系统

🧠 记忆技巧

信号量记数字：
- 看到“允许N个线程访问” → 选信号量
- 代码看到.acquire()/.release() → 信号量
条件变量查状态：
- 看到“当XX发生时唤醒” → 选条件变量
- 代码看到cv.wait(锁, lambda条件) → 条件变量
必背两句话：
- 信号量：“资源不够就阻塞，释放资源就加一”
- 条件变量：“条件不满足时解锁等待，满足时加锁执行”

🌰 1分钟实战场景

// 场景：仅允许3个线程同时下载
std::counting_semaphore down_sem(3); 

void download() {
    down_sem.acquire();    // 占位
    // ...下载操作...
    down_sem.release();    // 释放
}

// 场景：线程等待服务器启动
std::condition_variable cv;
bool server_ready = false;

void client() {
    std::unique_lock lk(mtx);
    cv.wait(lk, []{ return server_ready; }); // 等就绪
    // ...连接服务器...
}

void server() {
    // ...启动服务...
    server_ready = true;
    cv.notify_all(); // 通知所有客户端
}

用条件变量实现信号量

即用条件变量（condition variable）和互斥锁（mutex）来模拟信号量的 P/V 操作。

如果多个资源场景，各线程对资源的要求条件复杂，容易发生死锁的话，建议使用条件变量的实现

例如哲学家吃饭问题，每个哲学家都先拿起自己右手边的叉子，就会产生死锁，没有哲学家再能拿起左手边的叉子并吃饭。

P 操作（等待/获取资源）
1
2
3
4
5
6
7
void P(sem_t *sem) {
hold(&sem->mutex) {
while (!COND)
cond_wait(&sem->cv, &sem->mutex);
sem->count--;
}
}
- 先加锁（hold mutex），保证对信号量的操作是原子的。
- 如果条件不满足（如 count <= 0），就用条件变量等待（cond_wait），并自动释放 mutex，直到被唤醒。
- 被唤醒后再次加锁，检查条件，满足则 count--，表示获取一个资源。
V 操作（释放/归还资源）
1
2
3
4
5
6
void V(sem_t *sem) {
hold(&sem->mutex) {
sem->count++;
cond_broadcast(&sem->cv);
}
}
- 加锁，count++，表示释放一个资源。
- 用条件变量唤醒所有等待线程（cond_broadcast）。

用信号量实现条件变量

用信号量实现条件变量的 wait/broadcast 操作：

1. wait 函数

void wait(struct condvar *cv, mutex_t *mutex) {
    mutex_lock(&cv->lock);
    cv->nwait++;
    mutex_unlock(&cv->lock);

    mutex_unlock(mutex);
    P(&cv->sleep);
    mutex_lock(mutex);
}

cv->nwait++：记录当前有多少线程在等待条件变量（进入等待队列）。
mutex_unlock(mutex)：释放主互斥锁，允许其他线程进入临界区修改条件。
P(&cv->sleep)：在信号量 sleep 上等待（阻塞），直到被唤醒。
mutex_lock(mutex)：被唤醒后，重新获得主互斥锁，继续执行。

2. broadcast 函数

void broadcast(struct condvar *cv) {
    mutex_lock(&cv->lock);
    for (int i = 0; i < cv->nwait; i++) {
        V(&cv->sleep);
    }
    cv->nwait = 0;
    mutex_unlock(&cv->lock);
}

mutex_lock(&cv->lock)：保护 nwait 变量，防止并发修改。
for (int i = 0; i < cv->nwait; i++) V(&cv->sleep);：唤醒所有等待的线程（每个线程对应一次 V 操作）。
cv->nwait = 0;：重置等待计数。
mutex_unlock(&cv->lock)：释放锁。

信号量实现条件变量出现的问题

线程T2调用wait()，此时已经把自己标记为等待（nwait++），但还没真正阻塞（还没执行P）。
这时，因为其它线程的操作，另一个线程T1调用broadcast()，唤醒了所有等待线程（V操作），并继续执行。
此时nwait已经归零，T2就会睡死

从理论上来说，我们希望nwait++, mutex_unlock和P操作是原子性的，并且mutex_unlock和P操作不可以互换位置（会在睡时一直持有锁，死锁了），但是实际上我们需要操作系统用类似条件变量的机制帮我们实现wait和release的原子性，这样就套娃了

代码随想录 | 八股-HTTP版本

发表于 2025-07-04 更新于 2025-07-27 分类于 comp basic

HTTP1.0和HTTP1.1的区别

🚗 连接方式：从“一次一请”到“多次复用” * HTTP 1.0： 默认短连接。浏览器每请求一个资源（图片、CSS、JS等），都要和服务器建立一次新的TCP连接，用完后立即关闭。 * HTTP 1.1： 默认持久连接。浏览器和服务器建立一个TCP连接后，可以在这个连接上连续发送多个请求和接收多个响应通过Connection: keep-alive头来实现持久连接。

🏠 Host头：从“单间平房”到“共享公寓” * HTTP 1.0： 请求中没有Host请求头。服务器认为一个IP地址就对应一个网站（一个“主机”）。想象成：一个门牌号只住一户人家。 * HTTP 1.1： 请求中必须包含Host请求头。指明请求要访问的是服务器上的哪个虚拟主机/域名。这使虚拟主机托管成为可能（一台服务器托管多个不同域名的网站）。象成：一个门牌号（服务器IP）里住了好几户人家（不同网站），送快递必须写明收件人姓名（Host头）才知道送到哪户。

🚀 请求处理：从“排队等”到“连续发”（理论上） * HTTP 1.0： 客户端必须等前一个请求的响应完全返回后，才能发送下一个请求。想象成：收费站，前一辆车完全通过栏杆落下再抬起，后一辆车才能进。 * HTTP 1.1： 支持管道化。客户端可以在一个连接上连续发送多个请求，而不用等待每个响应。服务器必须按照收到请求的顺序返回响应。想象成：收费站允许连续进多辆车，出来的顺序必须和进去的顺序一致。（理论上提升速度，但实践中问题多，较少用）

🧊 缓存控制：从“简单指示”到“精细管理” * HTTP 1.0： 主要用If-Modified-Since/Expires（绝对过期时间）和Pragma: no-cache（简单不缓存）控制缓存。功能简单，不够灵活。 * HTTP 1.1： 引入了更强大、更精细的Cache-Control头。可以指定max-age（相对过期时间）、no-cache（需重新验证）、no-store（禁止存储）、public``private等众多指令。（缓存控制能力大大增强！）也可使用If-None-Match/Etag

⏳ 带宽优化：从“全有全无”到“按需取件” * HTTP 1.0： 如果下载大文件中断，必须从头开始重新下载。 * HTTP 1.1： 支持断点续传。使用Range请求头可以指定只请求资源的一部分（如从第1000个字节开始），服务器用206 Partial Content状态码和Content-Range响应头回部分内容。想象成：下载电影断网了，续播时可以从上次断开的地方继续下载，不用重头看。

📦 分块传输：从“等菜齐”到“边做边上” * HTTP 1.0： 服务器必须在知道资源的完整长度（Content-Length）后才能开始发送响应。对于动态生成的内容，需要等全部生成完才能发送。 * HTTP 1.1： 引入了分块传输编码。服务器可以将响应分成多个“块”发送，并在最后一个块发送完毕后标记结束。使用Transfer-Encoding: chunked响应头。想象成：厨房边菜边端上桌，不用等所有菜都做好。（提升动态内容响应速度，减少延迟）

📝 错误处理：从“模糊”到“更明确” * HTTP 1.1： 新增了一些状态码，提供更精确的错误信息： * 409 Conflict：请求与服务器当前状态冲突。 * 410 Gone：资源被永久删除（比404 Not Found更明确）。 * 100 Continue：客户端发送大请求体前，先询问服务器是否愿意接收，服务器同意（100 Continue）后再发完整请求。避免带宽浪费。 * 响应格式： HTTP 1.1 要求响应行中必须包含原因短语（如 HTTP/1.1 200 OK），而 1.0 只要求状态码是可选的（虽然实践中通常都有）。

HTTP2.0与HTTP1.1的区别？

一句话记忆：HTTP/2 = 更快、更智能、更省资源！

1️⃣ 传输方式：从“文本排队”到“二进制分帧”

HTTP/1.1：
- 用纯文本格式发送请求和响应（比如 GET /index.html HTTP/1.1）。
- 多个请求必须排队串行处理（即使开了管道化也有队头阻塞问题）。
- 想象： 邮局用明信片寄信，一次只能寄一张，必须等回信才能寄下一张，效率低。✉️➡️✉️➡️✉️
HTTP/2：
- 将数据拆分成更小的二进制帧（Frame）（头部帧 HEADERS + 数据帧 DATA）。
- 同一个连接上，多个请求/响应的帧可以混合发送、并行传输，互不阻塞！
- 想象： 快递公司把包裹拆成小件，打上标签，通过立体分拣通道同时运输，到目的地再组装。📦📦📦 → 🚚💨

👉 核心价值：彻底解决队头阻塞，大幅提升并发效率！

2️⃣ 连接方式：从“多路排队”到“真·多路复用”

HTTP/1.1：
- 虽然支持持久连接（一个TCP连多个请求），但响应必须按顺序返回（队头阻塞）。
- 浏览器通常开 6~8个TCP连接 并行请求资源（但占用资源多）。
HTTP/2：
- 一个TCP连接 上即可实现 成百上千个流的并行传输（每个流是一个请求/响应）。
- 帧自带流ID标识，接收方能按ID重组数据，无需排队等待！
- 想象： 从多条乡间小路 → 升级成一条双向十车道高速路，所有车辆（请求）畅通无阻。🛣️🚗🚙🚕

👉 核心价值：一个连接解决所有请求，省资源、低延迟！

3️⃣ 头部信息：从“重复臃肿”到“高效压缩”

HTTP/1.1：
- 每次请求都携带大量重复的文本头部（如Cookie、User-Agent），不压缩。
- 浪费带宽（尤其小文件请求时，头部可能比数据还大）。
HTTP/2：
- 使用 HPACK 算法压缩头部：
  - 客户端和服务端维护“头部字典”，相同头部只传索引；
  - 用霍夫曼编码压缩文本。
- 头部大小减少 30%~90%！
- 想象： 从每次寄信都手写完整地址 → 改用电子二维码扫码寄件，地址库自动匹配。📮→📲

👉 核心价值：大幅节省带宽，加快小资源加载！

4️⃣ 服务器主动推送：从“被动响应”到“主动送货”

HTTP/1.1：
- 服务器只能被动响应客户端请求。
- 浏览器需解析HTML后，再请求CSS/JS/图片等依赖资源。
HTTP/2：
- 服务器可主动推送客户端可能需要的资源（如CSS/JS）！
- 客户端可缓存推送内容，下次直接使用。
- 想象： 点外卖时，商家不仅送米饭，还主动附赠了筷子和纸巾（你知道你一定会需要）。🍚+🥢+🧻

👉 核心价值：减少请求往返次数，加速页面渲染！

5️⃣ 优先级与流量控制：更智能的资源调度

HTTP/2：
- 客户端可为请求标记优先级（如CSS > 图片），服务器优先处理高优先级流。
- 支持精细的流量控制（基于每个流控制传输速率）。
HTTP/1.1： 无法真正实现优先级调度（依赖浏览器启发式策略）。

⚠️ 注意：

HTTP/2 未加密，但所有主流浏览器只支持 HTTP/2 Over TLS（即 HTTPS）。
HTTP/2 解决了应用层队头阻塞，但 TCP 层仍有队头阻塞（丢包会阻塞所有流）。
这是 HTTP/3（基于QUIC/UDP）要解决的下一代问题！

HTTP3.0有了解过吗？

🚀 核心一句话：HTTP/3 = 抛弃TCP！拥抱QUIC！ > 解决 HTTP/2 的终极痛点：TCP 的队头阻塞！

1️⃣ 底层协议革命：从 TCP 到 QUIC（基于UDP）

HTTP/1.1 & HTTP/2： 都跑在 TCP 协议之上。
- TCP 问题： 如果传输中丢了一个包，后续所有包都要等待重传（即使它们属于不同请求），这就是 TCP 队头阻塞。
- 想象： 快递车队走一条单行道，前一辆车抛锚，后面所有车都得堵着等（无论是不是同一批货物）。🚚❌🚛🚗🚐
HTTP/3： 彻底抛弃 TCP，改用全新协议 QUIC（Quick UDP Internet Connections），运行在 UDP 之上。
- QUIC 优势： 每个请求/响应流是独立传输的，丢包只影响当前流，其他流畅通无阻！
- 想象： 快递改用无人机配送，每件包裹独立飞行路线，一个包裹出问题，其他包裹照常送达。✈️📦➡️🏠 | ✈️📦➡️🏠 | 💥📦❌ | ✈️📦➡️🏠
  👉 核心价值：彻底消灭传输层队头阻塞，网络波动时性能大幅提升！

2️⃣ 建连速度飞跃：0-RTT 与 1-RTT 握手

HTTP/1.1 & HTTP/2（TCP+TLS）：
- 首次连接需 TCP 三次握手（1.5 RTT） + TLS 握手（1~2 RTT） = 总计 2~3.5 RTT 延迟才能发送数据。
HTTP/3（QUIC）：
- 首次连接：1-RTT 握手（QUIC 将传输和加密握手合并）。
- 重连用户：0-RTT 握手！客户端缓存了服务器密钥，首次请求可直接带上加密数据。
- 想象： 进地铁站——旧方式：先排队买票（TCP握手），再安检（TLS握手）；新方式：刷脸直接进（0-RTT）！🎫→🛂→🚇 → 😃🔜🚇
  👉 核心价值：首次访问更快，重复访问“闪电启动”！

3️⃣ 连接迁移：网络切换不断线

HTTP/1.1 & HTTP/2：
- 连接绑定 IP + 端口 + TCP协议。切换网络（如WiFi→4G）会导致IP变化，连接必须重建！
HTTP/3（QUIC）：
- 使用 连接ID（Connection ID） 唯一标识连接。
- 切换网络时，只要客户端能通信，连接ID不变，会话无缝延续！
- 想象： 旧手机卡换手机要重新插卡激活；eSIM卡换手机自动联网，号码不变。📱➡️📱 = ❌ vs 📱➡️📱 = ✅
  👉 核心价值：移动端福音！地铁进隧道、WiFi切5G，视频会议不中断！

4️⃣ 内嵌加密：安全是强制要求

QUIC 协议设计之初就强制加密（使用 TLS 1.3）。
没有明文的 QUIC！ 所有头部和载荷默认加密。
对比： HTTP/2 的加密（HTTPS）是可选但事实强制，HTTP/3 直接内嵌到协议层。
👉 核心价值：提升安全性，防止运营商劫持、降低中间设备干扰。

5️⃣ 改进的多路复用 & 头部压缩

多路复用： 继承 HTTP/2 的流多路复用（一个连接并发多个流），且由于基于 QUIC，无队头阻塞。
头部压缩： 升级为 QPACK 算法（类似 HTTP/2 的 HPACK，但适应 QUIC 乱序特性）。
👉 核心价值：在 HTTP/2 高效基础上，更稳定！

代码随想录 | 刷题-动态规划3

发表于 2025-06-30 更新于 2025-07-02 分类于 leetcode

416. 分割等和子集

动态规划的正确性： - 每次迭代考虑一个新物品的所有可能组合 - 在使用一维dp数组时，倒序遍历保证状态转移只依赖上一轮结果

原始思路主要问题：

// 伪代码
int cnt = target;
for (遍历每个数字) {
    if (cnt >= 当前数字) cnt -= 当前数字; // 强制选择
    if (dp[cnt]) ... // 但dp从未更新！
}

贪心选择错误：强制按顺序选择数字，不能处理非连续选择也可以使用布尔值判断：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int eq = 0;
        for(int n : nums){
            eq += n;
        }
        if(eq % 2 == 1){
            return false;
        }else{
            eq = eq / 2;
        }
        vector<bool> dp(eq+1, false);
        dp[0] = true;
        int cnt = eq;
        for(int n : nums){
            for(int e = eq; e>=n; e--){
                if(dp[e - n]){
                    dp[e] = true;
                }
                if(dp[eq])return true;
            }
        }
        return false;
    }
};

操作系统基础 | 3.3 系统调用实现

发表于 2025-06-29 分类于 os basic

UAPI 文件位置

问题背景：
内核头文件中，内联函数往往需要引用其他头文件的结构体或常量，但这些头文件之间又存在相互依赖，导致无法直接引用，只能用 #define 代替，降低了代码质量。

解决方案：
David 提出将内核头文件中的用户空间 API 内容（即用户空间可见的定义）拆分到新的 uapi/ 子目录下的对应头文件中。这样做有以下好处：

简化内核专用头文件，减少体积。
明确区分用户空间与内核空间的 API，减少头文件间复杂的相互依赖。
便于追踪用户空间 API 的变更，方便 C 库维护者、脚本语言绑定、测试、文档等相关项目。

拆分方法：
一般头文件结构如下：

/* 头部注释 */

#ifndef _XXXXXX_H
#define _XXXXXX_H

[用户空间定义]

#ifdef __KERNEL__

[内核空间定义]

#endif /* __KERNEL__ */

[用户空间定义]

#endif /* _XXXXXX_H */

所有未被 #ifdef __KERNEL__ 包裹的内容，移动到 uapi/ 目录下的新头文件。
#ifdef __KERNEL__ 内的内容保留在原头文件，但移除 #ifdef 和 #endif。
头部注释保留并复制到新文件。
原头文件需添加 #include <include/uapi/path/to/header.h>，放在已有 #include 之后。
若原文件没有 #ifdef __KERNEL__，则直接重命名为 uapi/ 文件。

技术实现要点

头文件结构调整：将所有未被 #ifdef __KERNEL__ 包裹的内容迁移到 uapi/ 目录下的新头文件，原文件只保留内核专用部分，并通过 #include 引用新的 uapi 头文件。
自动化脚本辅助：由于头文件风格多样，David Howell 编写了大量 shell/Perl 脚本自动完成拆分，并对特殊情况通过预处理标记进行“辅导”。
兼容性与构建保证：拆分后，内核和用户空间的构建流程保持兼容，确保包含关系和功能不变。

社区讨论与挑战

大规模变更的审查难题：一次性修改数千文件、数十万行代码，难以人工逐行审查。社区建议主要审查思路和脚本实现，并通过自动化构建和对比二进制产物来验证正确性。
头文件包含路径的争议：有开发者质疑 uapi 头文件是否应包含内核头文件，实际实现中为兼容性和构建需要，uapi 头文件在内核构建时会包含内核头文件，但用户空间只见到 uapi 头文件。
隐式依赖与编译优化：有建议借此机会清理隐式包含、优化编译速度，但这属于更大范围的重构，超出了本次拆分的目标。
自动化工具的局限：与 Java 等语言不同，C 语言的预处理器和头文件机制更为复杂，自动化脚本难以覆盖所有边界情况，仍需人工干预和后续维护。

系统调用源码指引（以 ARM 架构为例）

系统调用的实现高度依赖于具体架构，包括调用方式和可用的系统调用种类。以下是 ARM 架构下与系统调用密切相关的核心源码文件：

include/linux/syscalls.h
提供所有内核系统调用的架构无关的前向声明。该文件定义了内核内部调用系统调用函数的接口。
arch/arm/include/uapi/asm/unistd.h
定义了 ARM 架构下系统调用号的相关内容。
arch/arm/kernel/entry-common.S
提供 ARM 架构下系统调用的入口汇编实现。
arch/arm/tools/syscall.tbl
负责将系统调用号及其对应的函数地址注册到 ARM 硬件的系统调用表中。

此外，以下文件虽然与系统调用无关，但涉及系统启动（这是内核执行的另一种方式）：

init 目录
包含内核初始化相关代码。
init/main.c
提供了 start_kernel 函数，这是 Linux 内核启动后执行的第一个 C 语言函数，且一旦调用永不返回。在此之前，内核仅通过架构相关的汇编代码和固件运行。
（参考：《Linux 设备驱动》第16章对 main.c 和 start_kernel 的介绍）