Pintos 线程系统详解（一）：线程结构
详细解析 Pintos 中 struct thread 的定义和线程的内存布局，理解线程是如何在内存中表示的。
Pintos 线程系统详解（一）：线程结构
概述
本文档详细解析 Pintos 中线程的核心数据结构 struct thread。理解这个结构是理解整个线程系统的基础。
Pintos 采用了一种独特的设计：每个线程占用一个完整的 4KB 页。线程结构体位于页的底部，而线程的内核栈从页的顶部向下增长。这种设计使得通过栈指针就能快速定位到线程结构体。
原始代码
thread.h 中的类型定义
1
2
3
4
5
6
7
8
9
/** Thread identifier type.
You can redefine this to whatever type you like. */
typedef int tid_t;
#define TID_ERROR ((tid_t) -1) /**< Error value for tid_t. */
/** Thread priorities. */
#define PRI_MIN 0 /**< Lowest priority. */
#define PRI_DEFAULT 31 /**< Default priority. */
#define PRI_MAX 63 /**< Highest priority. */
thread.h 中的线程状态枚举
1
2
3
4
5
6
7
8
/** States in a thread's life cycle. */
enum thread_status
{
THREAD_RUNNING, /**< Running thread. */
THREAD_READY, /**< Not running but ready to run. */
THREAD_BLOCKED, /**< Waiting for an event to trigger. */
THREAD_DYING /**< About to be destroyed. */
};
thread.h 中的 struct thread 定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct thread
{
/* Owned by thread.c. */
tid_t tid; /**< Thread identifier. */
enum thread_status status; /**< Thread state. */
char name[16]; /**< Name (for debugging purposes). */
uint8_t *stack; /**< Saved stack pointer. */
int priority; /**< Priority. */
struct list_elem allelem; /**< List element for all threads list. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /**< List element. */
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint32_t *pagedir; /**< Page directory. */
#endif
/* Owned by thread.c. */
unsigned magic; /**< Detects stack overflow. */
};
thread.c 中的魔数定义
1
2
3
4
/** Random value for struct thread's `magic' member.
Used to detect stack overflow. See the big comment at the top
of thread.h for details. */
#define THREAD_MAGIC 0xcd6abf4b
前置知识
1. 为什么需要线程结构？
操作系统需要管理多个执行流（线程），这需要：
- 保存执行状态：当线程不运行时，保存其寄存器、栈指针等
- 调度信息：优先级、状态等，供调度器使用
- 身份标识：线程 ID、名称，用于标识和调试
- 链接信息：将线程组织成各种数据结构（链表等）
2. Pintos 的 4KB 页设计
Pintos 选择让每个线程占用一个 4KB（4096 字节）页，这是一个巧妙的设计：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
内存地址（升序）
▲
│
4096 ├───────────────────────────────────┐
│ │
│ Kernel Stack │
│ │ │
│ │ │
│ ▼ │
│ (向下增长) │
│ │
│ │
│ (未使用空间) │
│ │
│ │
├───────────────────────────────────┤
│ magic │ ← 栈溢出检测
│ (其他字段) │
│ name[16] │
│ status │
0 │ tid │ ← struct thread 起始
└───────────────────────────────────┘
设计优点：
- 快速定位：通过栈指针可以立即找到线程结构
1 2
// 将栈指针向下对齐到页边界，就得到 struct thread 的地址 struct thread *t = (struct thread *) (esp & ~0xfff);
栈溢出检测：如果栈向下增长太多，会覆盖
magic字段- 简化内存管理：分配/释放线程只需一次页操作
3. 内存对齐
页大小是 4096 字节（2^12），页边界地址的低 12 位都是 0：
1
2
3
4
5
6
页边界地址示例：
0x0000_0000
0x0000_1000
0x0000_2000
...
0xFFFF_F000
4. list_elem 结构
Pintos 使用侵入式链表（intrusive list），即链表节点嵌入到数据结构中：
1
2
3
4
5
struct list_elem
{
struct list_elem *prev; /* Previous list element. */
struct list_elem *next; /* Next list element. */
};
通过 list_entry 宏可以从链表节点获取包含它的结构体：
1
2
#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
((STRUCT *) ((uint8_t *) (LIST_ELEM) - offsetof (STRUCT, MEMBER)))
逐字段详解
1. tid_t tid - 线程标识符
1
tid_t tid; /**< Thread identifier. */
作用：唯一标识一个线程。
类型：tid_t 是 int 的别名，方便以后修改。
取值：
- 从 1 开始递增分配
TID_ERROR (-1)表示错误
分配机制（在 allocate_tid() 中）：
1
2
3
4
5
6
7
8
9
10
11
12
static tid_t
allocate_tid (void)
{
static tid_t next_tid = 1; // 静态变量，全局唯一
tid_t tid;
lock_acquire (&tid_lock); // 加锁保证原子性
tid = next_tid++;
lock_release (&tid_lock);
return tid;
}
2. enum thread_status status - 线程状态
1
enum thread_status status; /**< Thread state. */
可能的值：
| 状态 | 含义 | 所在位置 |
|---|---|---|
THREAD_RUNNING | 正在 CPU 上运行 | 唯一（单核） |
THREAD_READY | 准备运行，等待调度 | ready_list |
THREAD_BLOCKED | 等待某事件 | 某个等待队列 |
THREAD_DYING | 即将被销毁 | 无 |
状态转换图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
创建
│
▼
┌──────────────┐
│ BLOCKED │
│ (初始状态) │
└──────────────┘
│
│ unblock
▼
┌──────────────┐ 被调度选中 ┌──────────────┐
│ RUNNING │◄─────────────│ READY │
│ (运行中) │ │ (就绪态) │
└──────────────┘ └──────────────┘
│ │ ▲
│ │ yield/时间片耗尽 │
│ └────────────────────────┘
│
│ exit
▼
┌──────────────┐
│ DYING │
│ (将销毁) │
└──────────────┘
3. char name[16] - 线程名称
1
char name[16]; /**< Name (for debugging purposes). */
作用：仅用于调试，帮助识别线程。
限制：最多 15 个字符 + 1 个终止符 \0。
使用场景：
- 调试输出
- 错误信息
thread_name()函数返回
4. uint8_t *stack - 保存的栈指针
1
uint8_t *stack; /**< Saved stack pointer. */
这是最关键的字段之一！
作用：保存线程不运行时的栈指针位置。
何时使用：
- 线程被切换出去时，保存当前栈指针到此处
- 线程被切换回来时，从此处恢复栈指针
与上下文切换的关系（在 switch.S 中）：
1
2
3
4
5
6
7
8
# 保存当前栈指针到旧线程的 stack 字段
mov thread_stack_ofs, %edx # 获取 stack 字段的偏移量
movl SWITCH_CUR(%esp), %eax # 获取当前线程指针
movl %esp, (%eax,%edx,1) # cur->stack = esp
# 从新线程的 stack 字段恢复栈指针
movl SWITCH_NEXT(%esp), %ecx # 获取下一线程指针
movl (%ecx,%edx,1), %esp # esp = next->stack
5. int priority - 优先级
1
int priority; /**< Priority. */
作用：决定线程的调度优先级。
取值范围：
1
2
3
#define PRI_MIN 0 // 最低优先级
#define PRI_DEFAULT 31 // 默认优先级
#define PRI_MAX 63 // 最高优先级
注意：基础 Pintos 没有实现优先级调度，这是 Project 1 的任务之一。
6. struct list_elem allelem - 全局线程列表元素
1
struct list_elem allelem; /**< List element for all threads list. */
作用：将所有线程链接到 all_list 链表。
用途：
- 遍历所有线程（如
thread_foreach()） - 调试和统计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 全局线程列表 */
static struct list all_list;
/* 遍历所有线程 */
void
thread_foreach (thread_action_func *func, void *aux)
{
struct list_elem *e;
for (e = list_begin (&all_list); e != list_end (&all_list);
e = list_next (e))
{
struct thread *t = list_entry (e, struct thread, allelem);
func (t, aux);
}
}
7. struct list_elem elem - 通用列表元素
1
struct list_elem elem; /**< List element. */
作用：用于将线程加入各种队列。
使用场景（互斥使用）：
- 在
ready_list中（状态为 READY） - 在信号量的等待队列中（状态为 BLOCKED）
为什么可以复用？
因为一个线程在任一时刻只能处于一个状态：
READY状态 → 在ready_list中BLOCKED状态 → 在某个等待队列中RUNNING状态 → 不在任何队列中
8. uint32_t *pagedir - 页目录（用户程序）
1
2
3
#ifdef USERPROG
uint32_t *pagedir; /**< Page directory. */
#endif
作用：指向用户进程的页目录。
条件编译：只在 USERPROG 定义时存在。
用途：
- 进程切换时激活正确的地址空间
- 内核线程此字段为 NULL
9. unsigned magic - 魔数
1
unsigned magic; /**< Detects stack overflow. */
作用：检测栈溢出。
原理：
- 初始化时设置为特定值：
1 2
#define THREAD_MAGIC 0xcd6abf4b t->magic = THREAD_MAGIC;
- 检查时验证：
1 2 3 4 5
static bool is_thread (struct thread *t) { return t != NULL && t->magic == THREAD_MAGIC; }
- 如果栈向下增长过多，会覆盖
magic，导致检测失败。
检测时机：
thread_current()每次调用都会检查- 检测失败会触发 assertion 失败
struct thread 内存布局详图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
偏移量 字段 大小(字节) 说明
───────────────────────────────────────────────────────
0 tid 4 线程ID
4 status 4 状态
8 name[16] 16 名称
24 stack 4 栈指针
28 priority 4 优先级
32 allelem.prev 4 ─┐
36 allelem.next 4 ─┴─ allelem (8字节)
40 elem.prev 4 ─┐
44 elem.next 4 ─┴─ elem (8字节)
48 pagedir (if USERPROG) 4 页目录指针
52 magic 4 魔数
───────────────────────────────────────────────────────
总大小: 约 56 字节（不含 USERPROG 为 52 字节）
剩余空间：
- 页大小：4096 字节
- struct thread：约 56 字节
- 可用于栈：约 4040 字节
全局数据结构
thread.c 中的全局变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/** List of processes in THREAD_READY state */
static struct list ready_list;
/** List of all processes */
static struct list all_list;
/** Idle thread */
static struct thread *idle_thread;
/** Initial thread, the thread running init.c:main() */
static struct thread *initial_thread;
/** Lock used by allocate_tid() */
static struct lock tid_lock;
数据结构关系图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
all_list (所有线程)
┌─────────────────────────────────────────────────────────────┐
│ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ main │───►│ idle │───►│thread_A │───►│thread_B │ │
│ │ thread │◄───│ thread │◄───│ │◄───│ │ │
│ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ initial_thread (可能在 ready_list 或等待队列) │
│ │
└─────────────────────────────────────────────────────────────┘
ready_list (就绪线程)
┌─────────────────────────────────────────────────────────────┐
│ │
│ ┌─────────┐ ┌─────────┐ │
│ │thread_A │───►│thread_B │ │
│ │ (READY) │◄───│ (READY) │ │
│ └─────────┘ └─────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
running_thread() 函数
这是一个精妙的函数，利用了 4KB 页设计：
1
2
3
4
5
6
7
8
9
10
11
12
13
/** Returns the running thread. */
struct thread *
running_thread (void)
{
uint32_t *esp;
/* Copy the CPU's stack pointer into `esp', and then round that
down to the start of a page. Because `struct thread' is
always at the beginning of a page and the stack pointer is
somewhere in the middle, this locates the current thread. */
asm ("mov %%esp, %0" : "=g" (esp));
return pg_round_down (esp);
}
工作原理：
1
2
3
4
5
6
7
8
9
10
11
12
13
4KB 页
┌─────────────────┐ 0x8001000 (页顶)
│ │
│ Kernel Stack │
│ │ │
│ ▼ │
│ ESP ──────────│◄── 当前栈指针位于此处
│ │
│ │
│ │
├─────────────────┤
│ struct thread │
└─────────────────┘ 0x8000000 (页底) = pg_round_down(ESP)
pg_round_down 的实现：
1
2
3
4
5
6
7
/* 向下取整到页边界 */
#define PGSIZE 4096
#define PGMASK (PGSIZE - 1) // 0xFFF
static inline void *pg_round_down (const void *va) {
return (void *) ((uintptr_t) va & ~PGMASK);
}
例如：
- ESP = 0x8000F00
- pg_round_down(ESP) = 0x8000F00 & ~0xFFF = 0x8000000
常见问题
Q1: 为什么 struct thread 放在页底部而不是顶部？
答：这是为了让 running_thread() 能工作。栈指针在页内某处，向下取整（pg_round_down）就能得到页起始地址，也就是 struct thread 的地址。如果 struct thread 在页顶，就需要向上取整后再计算偏移，更复杂。
Q2: 为什么栈空间只有约 4KB？这够用吗？
答：对于内核线程来说，4KB 通常够用。但要注意：
- 不要使用大的局部数组
- 不要深度递归
- 需要大内存时用
malloc()或palloc_get_page()
Q3: magic 字段为什么能检测栈溢出？
答：
- struct thread 在页底部
- magic 字段在 struct thread 的末尾（最高地址处）
- 栈从页顶向下增长
- 如果栈溢出，首先会覆盖 magic 字段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
正常情况:
┌─────────────┐
│ Stack │
│ ↓ │
│ (空间) │
├─────────────┤
│ magic ✓ │ <- 未被覆盖
│ ... │
└─────────────┘
溢出情况:
┌─────────────┐
│ Stack │
│ ↓ │
│ ↓↓↓↓ │
├─────────────┤ <- 栈已经越界
│ magic ✗ │ <- 被栈数据覆盖！
│ ... │
└─────────────┘
Q4: 为什么 elem 字段可以在不同队列中复用？
答：因为一个线程在任一时刻只能处于一种状态：
- READY → 在 ready_list 中
- BLOCKED → 在某个等待队列中
- RUNNING → 不在任何队列中
这是互斥的，所以同一个 elem 字段可以安全复用。
Q5: tid_t 为什么是 int 而不是 unsigned int？
答：使用有符号 int 可以用 -1 (TID_ERROR) 表示错误，这是 Unix 系统的常见做法。
练习思考
计算题：假设 struct thread 占用 64 字节（含 USERPROG），那么内核栈最多可以使用多少字节？
设计题：如果想让每个线程有 8KB 的栈空间，需要修改哪些地方？
分析题：如果没有 magic 字段，栈溢出会导致什么后果？
扩展题：如何实现一个函数
thread_stack_usage()，返回当前线程已使用的栈空间？思考题：为什么 Pintos 不使用
current_thread全局变量来保存当前线程指针，而要每次通过栈指针计算？
下一步
理解了线程结构后，下一篇文档将介绍线程的生命周期，包括状态转换和各状态的含义。
本文由作者按照 CC BY 4.0 进行授权