Linux内核

Linux内核Buddy System伙伴系统与Slab分配器深度实战

Buddy System伙伴系统与Slab分配器深度解析:从伙伴算法的free_list分裂合并机制,到Slab/Slob/Slub三种分配器的对象缓存设计;涵盖页面迁移类型(UNMOVABLE/MOVABLE/RECLAIMABLE)、内存碎片整理(compaction)、GFP分配标志体系、kmem_cache的Partial/Full/Free三链表管理、/proc/slabinfo与/proc/buddyinfo的实战监控手段,以及生产级调优最佳实践

Linux 内核 SLUB 分配器深度实战:从伙伴系统接口到 Slab 着色、本地 CPU 缓存与 Freelist 随机化的工程全解

完整剖析 Linux 内核 SLUB 分配器:从伙伴系统之上构建的对象缓存层出发,深度拆解每 CPU 热缓存加速路径、Slab 着色消除 Cache Thrashing、Freelist 随机化安全防护、NUMA 节点感知分配、kmalloc_caches 通用大小层级、以及 kmemleak/KASAN 等调试机制。附生产环境 GFP 标志选型表与 SLUB vs SLAB 性能基准。

并查集深度实战:从等价划分、路径压缩到按秩合并与可撤销/持久化的工程全解

系统拆解并查集(Disjoint Set Union)的第一性原理:用有根森林表示等价类划分,find/union 如何把"是否连通"转化为"根是否相同"。从朴素实现的 O(n) 退化陷阱出发,推导两大核心优化——路径压缩(迭代版,规避 Python 递归爆栈)与按秩/按大小合并——二者叠加把摊还复杂度钉死在反阿克曼函数 α(n)(物理可观测尺度内 α(n)≤4,近似常数)。进而展开变体谱系:加权/种类并查集、可撤销并查集(仅按大小合并+栈回滚,禁用路径压缩)、持久化并查集、DSU on tree、离线动态连通性、网格并查集。给出 Kruskal MST/连通分量/图像分割/等式约束/类型合一 等应用对照表、12 项生产陷阱清单(递归压缩爆栈、索引混淆、可撤销误用压缩等)与可复现 Python 工具箱。与本站 布隆过滤器/Count-Min Sketch/HyperLogLog/布谷鸟哈希 共同构成"概率与高性能数据结构工程"系列,前者提供确定性精确的等价类划分,后者提供概率近似的集合成员/频率/基数估计,工程栈中互补共存。

线段树与树状数组深度实战:从区间查询的第一性原理、lazy 标记到滑动窗口指标、订单簿与延迟直方图聚合的工程全解

区间,是几乎所有"可观测"系统的隐形骨架:实时大盘的滚动求和、限流器的滑动窗口计数、行情系统的档位聚合与 VWAP、推理服务的延迟直方图与分位告警、合并排序的归并段、文本与 DNA 的 LCP 数组……这些场景的共同点是——**数据在持续被单点更新,而你又必须随时回答"某一段区间的聚合值(和 / 最大 / 最小 / 计数)是多少"**。当你发现自己在用 `sum(arr[l:r+1])` 反复遍历…