Matrix Multiplication

TILE和THREAD

首先，我们需要使用 TILE 和 THREAD 来对我们的输入张量进行分块，分块有两种策略：连续分块 和 交错分块

连续分块下，我们的内存模型为：

block-beta

columns 10

block:header0:10
    columns 2
    space:2
    t0("thread (0, 0)")
    t1("thread (0, 1)")
end

block:t00:5
    columns 4
    b00t00("tile(0, 0)") b00t01("tile(0, 1)") b00t02("tile(0, 2)") b00t03("...")
    b00t10("tile(1, 0)") b00t11("tile(1, 1)") b00t12("tile(1, 2)") b00t13("...")
end

block:t01:5
    columns 4
    b01t00("tile(0, 0)") b01t01("tile(0, 1)") b01t02("tile(0, 2)") b01t03("...")
    b01t10("tile(1, 0)") b01t11("tile(1, 1)") b01t12("tile(1, 2)") b01t13("...")
end

block:header1:10
    columns 2
    space:2
    t2("thread (1, 0)")
    t3("thread (1, 1)")
end

block:t02:5
    columns 4
    b02t00("tile(0, 0)") b02t01("tile(0, 1)") b02t02("tile(0, 2)") b02t03("...")
    b02t10("tile(1, 0)") b02t11("tile(1, 1)") b02t12("tile(1, 2)") b02t13("...")
end

block:t03:5
    columns 4
    b03t00("tile(0, 0)") b03t01("tile(0, 1)") b03t02("tile(0, 2)") b03t03("...")
    b03t10("tile(1, 0)") b03t11("tile(1, 1)") b03t12("tile(1, 2)") b03t13("...")
end

class t00,t01,t02,t03 animate
class t0,t1,t2,t3 purple
class header0,header1 transparent

classDef transparent fill:none,stroke:none,color:inherit;
classDef content fill:#fff,stroke:#ccc;
classDef animate stroke:#666,stroke-dasharray: 8 4,stroke-dashoffset: 900,animation: dash 20s linear infinite;
classDef yellow fill:#FFEB3B,stroke:#333,color:#000,font-weight:bold;
classDef blue fill:#489,stroke:#333,color:#fff,font-weight:bold;
classDef pink fill:#FFCCCC,stroke:#333,color:#333,font-weight:bold;
classDef light_green fill:#e8f5e9,stroke:#695;
classDef green fill:#695,color:#fff,font-weight:bold;
classDef purple fill:#968,stroke:#333,color:#fff,font-weight:bold;
classDef gray fill:#ccc,stroke:#333,font-weight:bold;
classDef error fill:#bbf,stroke:#f65,stroke-width:2px,color:#fff,stroke-dasharray: 5 5;
classDef coral fill:#f8f,stroke:#333,stroke-width:4px;
classDef orange fill:#fff3e0,stroke:#ef6c00,color:#ef6c00,font-weight:bold;

什么是卷积

在数学、信号处理以及深度学习（卷积神经网络 CNN）中，卷积（Convolution） 是一种通过两个函数生成第三个函数的数学运算，表征了一个函数在另一个函数之上滑动时，两者重叠部分的累积效果。而对于 连续域和离散域，我们的处理方式是完全不一样的：

• 在连续域中，函数 \(f\) 和 \(g\) 的卷积定义为：\[(f * g)(t) = \int_{-\infty}^{\infty} f(\tau)g(t - \tau) d\tau\]

• 在离散域（如图像处理）中，定义为：\[(f * g)[n] = \sum_{m=-\infty}^{\infty} f[m]g[n - m]\]

卷积的一个典型例子：复利

假设：

本文所有代码可以在 test-cuda 下查看。

下面的图展示的是 CUDA 编程中一种非常经典的算法模式：并行规约（Parallel Reduction）。简单来说，它的目的是将一个大数组中的所有元素“折叠”成一个值（比如求和、求最大值或最小值）。

block-beta

columns 25
    space
    a0 a1 a2 a3 a4 a5 a6 a7
    b0 b1 b2 b3 b4 b5 b6 b7
    c0 c1 c2 c3 c4 c5 c6 c7

r1("r1")

sum0("sum"):2 sum1("sum"):2 sum2("sum"):2 sum3("sum"):2
sum4("sum"):2 sum5("sum"):2 sum6("sum"):2 sum7("sum"):2
sum8("sum"):2 sum9("sum"):2 sum10("sum"):2 sum11("sum"):2

r2("r2")

sum12("sum"):4 sum13("sum"):4
sum14("sum"):4 sum15("sum"):4
sum16("sum"):4 sum17("sum"):4

r3("r3")

sum18("sum"):8
sum19("sum"):8
sum20("sum"):8

space:25

r4("r4")
s("cross"):24

sum18 --"跨block通信"--> s
sum19 --"跨block通信"--> s
sum20 --"跨block通信"--> s

class a0,a1,a2,a3,a4,a5,a6,a7 green
class b0,b1,b2,b3,b4,b5,b6,b7 blue
class c0,c1,c2,c3,c4,c5,c6,c7 orange

class sum0,sum1,sum2,sum3,sum12,sum13 green
class sum4,sum5,sum6,sum7,sum14,sum15 blue
class sum8,sum9,sum10,sum11,sum16,sum17 orange

class sum18,sum19,sum20 gray

class r1,r2,r3,r4 purple

class s error



%% 样式定义
classDef content fill:#fff,stroke:#ccc;
classDef animate stroke:#666,stroke-dasharray: 8 4,stroke-dashoffset: 900,animation: dash 20s linear infinite;
classDef yellow fill:#FFEB3B,stroke:#333,color:#000,font-weight:bold;
classDef blue fill:#489,stroke:#333,color:#fff,font-weight:bold;
classDef pink fill:#FFCCCC,stroke:#333,color:#333,font-weight:bold;
classDef light_green fill:#e8f5e9,stroke:#695;
classDef green fill:#695,color:#fff,font-weight:bold;
classDef purple fill:#968,stroke:#333,color:#fff,font-weight:bold;
classDef gray fill:#ccc,stroke:#333,font-weight:bold;
classDef error fill:#bbf,stroke:#f65,stroke-width:2px,color:#fff,stroke-dasharray: 5 5;
classDef coral fill:#f8f,stroke:#333,stroke-width:4px;
classDef orange fill:#fff3e0,stroke:#ef6c00,color:#ef6c00,font-weight:bold;

第一层（最上方）：每个 Block 内部的线程开始成对地读取数据。例如，线程 0 读取位置 0 和位置 1 的数，将它们相加。

逐级折叠：

环境配置

CUDA 开发环境的配置流程虽不算复杂，但主流的实现方案均存在明显的体验短板：

• macOS 远程对接 Linux 开发：这种在 macOS 系统下通过远程连接 Linux 环境开发的方式，核心痛点包括：
  • 多数 IDE 对跨平台编译、调试（DEBUG）的支持度不足，功能完整性和稳定性欠佳；
  • 开发过程中易遇到不影响核心功能但影响体验的小问题，整体使用感受较差；
  • 核心问题在于算力资源（算例）多按小时租赁且成本较高，为控制开销频繁启停实例时，需反复配置开发环境，严重降低开发效率。
• Windows 原生开发：该方案能满足基础开发流程需求，但核心问题集中在适配性和工具层面：
  • 行业内多数 CUDA 相关依赖框架、技术文档均基于 Linux 环境开发和撰写，迁移到 Windows 时，需额外花费精力寻找适配方案，甚至手动调整兼容逻辑；
  • 核心开发工具 Visual Studio 体积臃肿、配置项繁杂，对新手不友好，且易因配置不当引发环境问题。

经过我一段时间的摸索和测试，目前找到了一个比较好的解决方案：Windows + WSL(Ubuntu) + VSCode(WSL Plugin) 来作为开发环境，即有极高的兼容性，同时对于习惯于 linux 开发的我来说更顺手。最重要的是，这一套环境的配置远低于其他的环境配置，这里我们介绍一下怎么搭建这个开发环境。

本文是自己动手实现raft的前置文章，旨在分析raft协议的内部实现原理。作者在网上搜索了大量的文献和资料，向这些作者表达我的敬意。这里也推荐阅读本文的人可以参考这几篇经典的文章：

• raft原论文
• raft论文（翻译版）
• raft算法可视化

概述

在我们探讨 raft 算法之前，我们需要搞清楚为什么我们需要一个如此复杂的算法：我们用数据库举例：

在传统的单机数据库下，我们其实也会有所谓的一致性需求 -- 就是我们的事务。当我们在执行一个 SQL 语句时会存在 IO 操作，而这个 IO 操作和我们分布式系统的 IO 操作是没有本质区别的 -- 他们都有概率失败。例如：假设我们存在一个 SQL 写入语句，这个语句写入的字段中包含了一个超大字段，这个超大字段超过了操作系统的单次 IO 写入大小，那么操作系统必然会把这个写入语句拆分成多次 IO 操作。那现在我们面临的问题是：

• 假设这个语句被拆分为两次 IO 操作：
  • 第一次 IO 操作成功了，第二次 IO 操作时磁盘满了无法写入怎么办？
  • 第一次 IO 操作成功了，在第二次 IO 操作之前机器重启了怎么办？

需要注意的是，linux下的网络编程是一个非常琐碎的过程，所以我们在这里只是实现了最简单的版本：

• 只支持 IPv4；
• 只支持通过 Linux Bridge/Veth Pari；
• 对 Subnet 的网段进行了限制，并且只允许通过后台默认分配，不允许用户自定义；

在实现的过程中，我们也有很多的地方因为太过于繁琐直接省略了：

• 对于我们分配网段/分配IP的管理，只记录在内存中，并没有做持久化；
• 虽然根据职责对系统进行了分层，但是整个的架构和接口设计都比较随意；
• EndpointId 和 ContainerId 没有分开，也就限制了我们每个容器只能接入一个网络；
• 虽然对各个组件之间通过接口做了解耦，但是实际在代码实现中未实现完全解耦；
• 错误处理不严谨，很多地方在失败时都没有进行回滚操作；
• 没有增加跨子网路由，所以现在只能容器之间通信，而不能实现容器通过宿主机的网卡与外网通信。

在我们前面的文章 build my own docker from scratch 中，我们实现了：

• 通过 namespace 对容器实现资源虚拟化；
• 通过 cgroup 对容器的资源进行限制和管理；
• 通过 daemon 进程来实现对整体资源的管理；

今天我们要开始实现一个对 docker 来说至关重要的特性：network namespace 的管理。从这一节，我们也可以体会到为什么我们要使用一个额外的 daemon 进程来对我们容器进行管理 -- 从之前的视角中，我们可以看到大量的缺点：

• 引入了额外的复杂性；
• 大量通过 UDS 通信导致的异步行为使得程序的编码和DEBUG都更加困难；
• 中心化的服务降低了程序的健壮性。

发现问题

最近在尝试实现一个简单的 docker，在实现的过程中我试图将对linux的cgroup文件操作抽象为一个独立的接口 subsystem，但是对于不同的类型的文件他的结构完全不一样：

• 对于 cgroup.procs，他的文件中存储的是一个以 \n 分割的 pid 数组；
• 对于 cpu.max，他的文件中存储的是以空格分隔的两个数字；

1
2
3
4
5

cat /sys/fs/cgroup/system.slice/docker-0a7f5c9459f832ac7bb539e6e61dac51a4a4f66c5dbc1bbb963d0ec3f01d31ae.scope/cgroup.procs
#1435205

cat /sys/fs/cgroup/system.slice/docker-0a7f5c9459f832ac7bb539e6e61dac51a4a4f66c5dbc1bbb963d0ec3f01d31ae.scope/cpu.max
# max 100000

所以，我尝试直接将他做出如下抽象：

build my own docker from scratch

Docker is an OS‑level virtualization (or containerization) platform, which allows applications to share the host OS kernel instead of running a separate guest OS like in traditional virtualization.

前言

本文基于 OpenCloudOS 操作系统以及 x86_64 平台，go1.24.11 语言开发测试，全部代码位于 tiny-docker。

1 2 3 4 5 6 7 8

uname -a # Linux VM-0-10-opencloudos 6.6.117-45.1.oc9.x86_64 #1 SMP Tue Dec 16 11:49:47 CST 2025 x86_64 x86_64 x86_64 GNU/Linux go version # go version go1.24.11 linux/amd64 docker --version # Docker version 29.1.3, build f52814d

Docker 是基于 Linux Namespace 和 Cgroup 实现的轻量级虚拟化平台。相较于传统虚拟机（如 Oracle VirtualBox），Docker 无需模拟硬件和运行独立内核，仅通过内核级的资源隔离与限制实现 “虚拟环境”，因此更轻量级（毫秒级启动）、资源占用更低 —— 同一台宿主机上的所有容器共享宿主机内核，这是容器与虚拟机的核心区别。

uCore并发

sequenceDiagram
    title 银行家算法 - 安全场景（sequenceDiagram）
    银行家算法 ->> 数据结构存储: 初始化请求（读取Available/Allocation/Need）
    数据结构存储-->>银行家算法: 返回初始数据（Available={}, Work={}, Finish=[F,F]）
    
    %% 第一次循环:找满足条件的线程
    银行家算法 ->> 银行家算法: 遍历线程，检查条件（Need[i][j] ≤ Work[j] 且 Finish[i]=F）
    银行家算法 ->> 数据结构存储: 查询线程1的Need/Finish
    数据结构存储-->>银行家算法: 线程1:Need={200:1}，Finish=F
    银行家算法 ->> 银行家算法: 线程1:Need > Work → 不满足
    银行家算法 ->> 数据结构存储: 查询线程2的Need/Finish
    数据结构存储-->>银行家算法: 线程2:Need={}，Finish=F
    银行家算法 ->> 银行家算法: 线程2:Need ≤ Work → 满足
    
    %% 模拟线程2释放资源
    银行家算法 ->> 数据结构存储: 模拟线程2执行完毕，请求更新Work（Work += 线程2的Allocation{200:1}）
    数据结构存储-->>银行家算法: Work更新成功（Work={200:1}）
    银行家算法 ->> 数据结构存储: 请求标记线程2的Finish=true
    数据结构存储-->>银行家算法: Finish更新成功（Finish=[F,T]）
    
    %% 第二次循环:找满足条件的线程
    银行家算法 ->> 银行家算法: 重新遍历线程（仅线程1未完成）
    银行家算法 ->> 数据结构存储: 查询线程1的Need/Work
    数据结构存储-->>银行家算法: 线程1:Need={200:1}，Work={200:1}
    银行家算法 ->> 银行家算法: 线程1:Need ≤ Work → 满足
    
    %% 模拟线程1释放资源
    银行家算法 ->> 数据结构存储: 模拟线程1执行完毕，请求更新Work（Work += 线程1的Allocation{100:1}）
    数据结构存储-->>银行家算法: Work更新成功（Work={100:1,200:1}）
    银行家算法 ->> 数据结构存储: 请求标记线程1的Finish=true
    数据结构存储-->>银行家算法: Finish更新成功（Finish=[T,T]）
    
    %% 判定结果
    银行家算法 ->> 银行家算法: 检查所有Finish是否为true
    银行家算法-->>外部: 输出判定结果 → 系统安全（无死锁风险）

引言

线程定义

简单地说，线程是进程的组成部分，进程可包含1 – n个线程，属于同一个进程的线程共享进程的资源， 比如 地址空间、打开的文件等。基本的线程由线程ID、执行状态、当前指令指针 (PC)、寄存器集合和栈组成。 线程是可以被操作系统或用户态调度器独立调度（Scheduling）和分派（Dispatch）的基本单位。进程是线程的资源容器， 线程成为了程序的基本执行实体。

进程间通信

基于文件的管道

1
2
3
4
5
6
7

// os/src/fs/pipe.rs

pub struct Pipe {
    readable: bool,
    writable: bool,
    buffer: Arc<Mutex<PipeRingBuffer>>,
}

通过 buffer 字段还可以找到该管道端所在的管道自身。后续我们将为它实现 File Trait ，之后它便可以通过文件描述符来访问。

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

// os/src/fs/pipe.rs

const RING_BUFFER_SIZE: usize = 32;

#[derive(Copy, Clone, PartialEq)]
enum RingBufferStatus {
    FULL,
    EMPTY,
    NORMAL,
}

pub struct PipeRingBuffer {
    arr: [u8; RING_BUFFER_SIZE],
    head: usize,
    tail: usize,
    status: RingBufferStatus,
    write_end: Option<Weak<Pipe>>,
}