BUAA-OS-Challenge Thread Model

代码修改

整个开发过程在 Lab6 现有代码基础之上进行，按功能模块逐步修改。

1. 扩展 Env 结构体

文件：include/env.h

• 新增状态宏 ENV_ZOMBIE，值为 3。该状态表示线程已退出但控制块尚未释放，用于兼容并发等待。
• 在 struct Env 中新增以下字段：
  • u_int env_tgid：线程组 ID，主线程初次创建时与自己的 env_id 相同，其他线程继承自主线程
  • int env_return_value：调用 sys_exit 时传递的返回值
  • u_int env_waits_for：当前线程正在等待哪一个线程
  • u_int env_waited_by：记录正在等待本线程退出的线程 ID
  • u_int env_wait_retptr：处于 sys_wait 阻塞状态时，记录应写入返回值的用户态地址
  • uint32_t env_futex_word：若线程阻塞在某个 futex 上，则记录对应的物理地址
• 在文件末尾声明env.c中新增函数。

struct Env {
  struct Trapframe env_tf; // saved registers
  LIST_ENTRY(Env) env_link; // free list entry
  u_int env_id; // unique id
  u_int env_asid; // address space id
  u_int env_parent_id // parent env id
  u_int env_status; // ENV_RUNNABLE etc.
  Pde *env_pgdir; // page directory (shared for threads)
  TAILQ_ENTRY(Env) env_sched_link; // scheduler list entry
  u_int env_pri; // priority
  // IPC (Lab 4)
  u_int env_ipc_value;
  u_int env_ipc_from;
  u_int env_ipc_recving;
  u_int env_ipc_dstva;
  u_int env_ipc_perm;
  u_int env_user_tlb_mod_entry; // TLB mod handler
  u_int env_runs; // number of times scheduled
  // 线程扩展
  u_int env_tgid; // thread group id
  int   env_return_value; // exit return value
  u_int env_waits_for; // which thread this env is waiting for (0 none)
  u_int env_waited_by; // which thread is waiting for this env (0 none)
  u_int env_wait_retptr; // user va to write return value when waited thread exits (0 none)
  uint32_t env_futex_word; // physical address this thread is blocked on (0 none)
};

2. 线程分配与释放函数

文件：kern/env.c

• 实现 env_alloc_thread：

  • 从 env_free_list 中取出空闲 Env 控制块
  • 共享父进程的页目录 env_pgdir
  • 初始化线程特有字段：env_tgid、env_return_value、env_waits_for、env_waited_by、env_wait_retptr、env_futex_word，均置 0。
  • 将新线程从空闲链表中移除，返回创建好的 Env 指针。

• 实现 env_free_thread：

  • asid_free释放该线程先前占用的 ASID
  • 将控制块状态设为 ENV_FREE，重新插入 env_free_list

int env_alloc_thread(struct Env **new, struct Env *parent) {
  int r;
  struct Env *e;
  e = LIST_FIRST(&env_free_list);
  if (e == NULL) {
    return -E_NO_FREE_ENV;
  }
  e->env_pgdir = parent->env_pgdir;
  e->env_user_tlb_mod_entry = parent->env_user_tlb_mod_entry;
  e->env_pri = parent->env_pri;
  e->env_runs = 0;
  if ((r = asid_alloc(&e->env_asid)) != 0) {
    return r;
  }
  e->env_asid = parent->env_asid;
  e->env_id = mkenvid(e);
  e->env_parent_id = parent->env_id;
  e->env_tgid = parent->env_tgid;
  e->env_tf = parent->env_tf;
  e->env_tf.cp0_status = STATUS_IM7 | STATUS_IE | STATUS_EXL | STATUS_UM;
  e->env_status = ENV_NOT_RUNNABLE;
  e->env_return_value = 0;
  e->env_waits_for = 0;
  e->env_waited_by = 0;
  e->env_wait_retptr = 0;
  e->env_futex_word = 0;
  e->env_ipc_recving = 0;
  e->env_ipc_value = 0;
  e->env_ipc_from = 0;
  LIST_REMOVE(e, env_link);
  *new = e;
return 0;
}

void env_free_thread(struct Env *e) {
  printk("[%08x] free thread %08x\n", curenv ? curenv->env_id : 0, e->env_id);
  asid_free(e->env_asid);
  e->env_status = ENV_FREE;
  LIST_INSERT_HEAD(&env_free_list, e, env_link);
}

3. 线程系统调用实现

文件：kern/syscall_all.c

3.1 sys_gettgid

• 直接返回 curenv->env_tgid。

int sys_gettgid() {
  return curenv->env_tgid;
}

3.2 sys_create_thread

• 参数校验：entry_point 和 stack 必须 4 字节对齐，且各自在合法用户地址范围内。
• 调用 env_alloc_thread 创建新的线程控制块。
• 设置新线程的 env_tf：
  • cp0_epc = entry_point
  • 初始实现中 sp = (u_int)stack。运行测试时出现超时。后将栈指针修改为 newenv->env_tf.regs[29] = (u_int)stack - 4 * sizeof(u_int);，超时问题解决。可能是引发了不可预知的死锁或页错误。
  • regs[4] = (u_int)arg（$a0）
  • regs[31] = 0，而线程返回后应由 mthread_exit 终止，不依赖返回地址。
• 将新线程状态设为 ENV_RUNNABLE，直接插入调度队列尾部，让其有机会被调度。

int sys_create_thread(void *(*entry_point)(void *), void *stack, void *arg) {
  if (((u_long)entry_point % 4 != 0) || ((u_long)stack % 4 != 0))
    return -E_INVAL;
  if ((u_long)entry_point >= KSEG0 || (u_long)entry_point < UTEXT)
    return -E_INVAL;
  if ((u_long)stack >= USTACKTOP || (u_long)stack < (USTACKTOP - PDMAP))
    return -E_INVAL;
  struct Env *newenv;
  int r = env_alloc_thread(&newenv, curenv);
  if (r < 0) return r;
  newenv->env_pri = curenv->env_pri;
  newenv->env_user_tlb_mod_entry = curenv->env_user_tlb_mod_entry;
  newenv->env_tgid = curenv->env_tgid;
  newenv->env_parent_id = curenv->env_id;
  newenv->env_tf.cp0_epc = (u_int)entry_point;
  newenv->env_tf.regs[29] = (u_int)stack - 4 * sizeof(u_int);  
  newenv->env_tf.regs[4]  = (u_int)arg;     
  newenv->env_tf.regs[31] = 0;
  newenv->env_status = ENV_RUNNABLE;
  TAILQ_INSERT_TAIL(&env_sched_list, newenv, env_sched_link);
return newenv->env_id;
}

3.3 sys_exit

• 将当前线程的返回值存入 curenv->env_return_value。
• 如果curenv->env_futex_word != 0，调用 futex_cleanup 从等待队列中移除。
• 将当前线程从调度链表移除，状态切换为 ENV_ZOMBIE。
• 遍历所有非空闲线程，找出正在等待本线程退出的线程：
  • 若该等待线程指定了 env_wait_retptr，则先用 page_lookup 拿到物理页，再通过 KADDR 转换为内核地址进行写入，且权限检查由 PTE_D 改为 PTE_V。
  • 写入后清空 env_wait_retptr，解除等待关系，唤醒该线程。
• 调用 schedule(1) 切换到下一个线程。

void sys_exit(int return_value) {
  curenv->env_return_value = return_value;
  // 清理 futex 等待（如果自己阻塞在 futex）
  if (curenv->env_futex_word != 0) {
    futex_cleanup(curenv);
  }
  // 从调度队列移除并变为 ZOMBIE
  if (curenv->env_status == ENV_RUNNABLE) {
    TAILQ_REMOVE(&env_sched_list, curenv, env_sched_link);
  }
  curenv->env_status = ENV_ZOMBIE;
  // 唤醒所有等待本线程的线程，并写入返回值
  for (int i = 0; i < NENV; i++) {
    if (envs[i].env_status == ENV_NOT_RUNNABLE &&
        envs[i].env_waits_for == curenv->env_id) {
      if (envs[i].env_wait_retptr != 0) {
        write_user_int(&envs[i], envs[i].env_wait_retptr, return_value);
        envs[i].env_wait_retptr = 0;
      }
      envs[i].env_waits_for = 0;
      // 唤醒线程
      envs[i].env_status = ENV_RUNNABLE;
      TAILQ_INSERT_TAIL(&env_sched_list, &envs[i], env_sched_link);
    }
  }
  curenv->env_waited_by = 0;
schedule(1);
}

3.4 sys_wait

• 参数校验 & 权限检查：return_value_ptr 必须 4 字节对齐且处于用户态合法地址范围，对应虚拟页必须有效（PTE_V）。
• 通过 envid2env 找到目标线程 target。
• 若目标线程状态已经是 ENV_ZOMBIE：写入返回值到 return_value_ptr。调用 env_free_thread 释放目标线程控制块。
• 若目标线程仍在运行：
  • 将 curenv->env_wait_retptr 设为 return_value_ptr，env_waits_for 设为目标线程 ID。
  • 将目标线程的 env_waited_by 设为本线程 ID。
  • 将自身状态设为 ENV_NOT_RUNNABLE，从就绪队列移除。
  • 执行 ((struct Trapframe *)KSTACKTOP - 1)->regs[2] = 0。这样当等待线程被 sys_exit 唤醒并调度恢复执行时，v0 寄存器即为 0，保证 syscall 返回 0 给用户态调用者。
  • 调用 schedule(1) 切换到其他线程。

int sys_wait(u_int envid, u_int return_value_ptr) {
  struct Env *target;
  Pte *pte;
  if (return_value_ptr % 4 != 0)
    return -E_INVAL;
  if (return_value_ptr < UTEXT || return_value_ptr >= KSEG0)
    return -E_INVAL;
  if (page_lookup(curenv->env_pgdir, return_value_ptr, &pte) == NULL ||
      !(*pte & PTE_D))
    return -E_INVAL;
  if (envid2env(envid, &target, 0) != 0)
    return -E_BAD_ENV;
  if (target->env_tgid != curenv->env_tgid &&
      target->env_parent_id != curenv->env_id)
    return -E_BAD_ENV;
  if (target->env_status == ENV_ZOMBIE) {
    write_user_int(curenv, return_value_ptr, target->env_return_value);
    env_free_thread(target);
    return 0;
  }
  // 目标还在运行，准备阻塞
  curenv->env_wait_retptr = return_value_ptr;
  curenv->env_waits_for = envid;
  target->env_waited_by = curenv->env_id;
  curenv->env_status = ENV_NOT_RUNNABLE;
  TAILQ_REMOVE(&env_sched_list, curenv, env_sched_link);
  ((struct Trapframe *)KSTACKTOP - 1)->regs[2] = 0;
  schedule(1);
  // 不会执行到这里，但保留
return 0;
}

4. futex 系统调用实现

文件：kern/mfutex.c

• futex_cleanup：当线程退出时，若曾阻塞在某个 futex 上，则从对应物理地址的等待队列中删除该线程记录，防止后续 WAKE 操作引用已释放的 Env。
• sys_mfutex：
  • 参数检查：uaddr 须 4 字节对齐，且在用户态合法地址范围。
  • 调用 page_lookup 将虚拟地址转换为物理地址。
  • MFUTEX_WAIT：
    • 使用 *(volatile uint32_t *)KADDR(paddr) 通过物理地址读取 futex word，确保读取一致性。
    • 若读取值不等于 val，直接返回 -E_AGAIN。
    • 若相等，则将当前线程 ID 加入该物理地址对应的等待队列，记录 env_futex_word，设置当前线程为 ENV_NOT_RUNNABLE 并从就绪链表移除。
    • 调度前设置 regs[2] = 0，使得被唤醒后 syscall 返回 0。
    • 调用 schedule(1) 阻塞自己。
  • MFUTEX_WAKE：
    • 唤醒至多 val 个等待队列中的线程。
    • 对每个符合条件的线程，清除其 env_futex_word 并使其重新就绪。

static struct FutexEntry *find_or_new(u_int paddr) {
    for (int i = 0; i < nentry; i++) {
        if (table[i].paddr == paddr) return &table[i];
    }
    if (nentry >= 64) return NULL;
    table[nentry].paddr = paddr;
    table[nentry].count = 0;
    return &table[nentry++];
}

void futex_cleanup(struct Env *e) {
    if (!e->env_futex_word) return;
    for (int i = 0; i < nentry; i++)
        if (table[i].paddr == e->env_futex_word) {
            for (int j = 0; j < table[i].count; j++)
                if (table[i].waiters[j] == e->env_id) {
                    table[i].waiters[j] = table[i].waiters[--table[i].count];
                    break;
                }
            break;
        }
    e->env_futex_word = 0;
}

int sys_mfutex(uint32_t *uaddr, u_int op, uint32_t val) {
    if ((u_int)uaddr & 3) return -E_INVAL;
    if ((u_int)uaddr < UTEXT || (u_int)uaddr >= KSEG0) return -E_INVAL;
    Pte *pte;
    struct Page *p = page_lookup(curenv->env_pgdir, (u_int)uaddr, &pte);
    if (!p || !(*pte & PTE_V)) return -E_INVAL;
    u_int paddr = page2pa(p) | ((u_int)uaddr & 0xFFF);

    if (op == MFUTEX_WAIT) {
        if (*(volatile uint32_t *)KADDR(paddr) != val) {
            return -E_AGAIN;
        }
        struct FutexEntry *e = find_or_new(paddr);
        if (!e || e->count >= 16) return -E_NO_MEM;
        e->waiters[e->count++] = curenv->env_id;
        curenv->env_futex_word = paddr; 
        curenv->env_tf.regs[2] = 0; 
        safe_dequeue(curenv, ENV_NOT_RUNNABLE);
        schedule(1);
        return 0; 

    } else if (op == MFUTEX_WAKE) {
        struct FutexEntry *e = NULL;
        for (int j = 0; j < nentry; j++) {
            if (table[j].paddr == paddr) { e = &table[j]; break; }
        }
        
        if (!e || e->count == 0) return 0;

        int woken = 0;
        int i = 0;
        while (i < e->count) {
            u_int wid = e->waiters[i];
            struct Env *w;

            if (envid2env(wid, &w, 0) == 0 && 
                w->env_status == ENV_NOT_RUNNABLE && 
                w->env_futex_word == paddr) {
              
                if (woken < (int)val) {
                    w->env_futex_word = 0;
                    safe_enqueue(w);
                    woken++;
                    e->waiters[i] = e->waiters[--e->count];
                    continue; 
                }
            } else {
                e->waiters[i] = e->waiters[--e->count];
                continue;
            }
            i++;
        }
        return 0;
    }
    
    return -E_INVAL;
}

5. 用户态线程库

根据指导书中伪代码：

lock(mutex):
1. 先尝试把 mutex.state 从 0 原子地改成 1。
2. 如果修改成功：
      说明锁原来是空闲的，当前线程已经获得锁，直接返回。
3. 如果修改失败：
      说明锁已经被其他线程持有，进入下面的慢速路径。
4. 在循环中执行以下步骤：
   4.1 原子地把 mutex.state 改成 2，并取得修改前的旧值 old（注意修改与取得旧值是一个原子操作）。
   4.2 如果 old 等于 0：
          说明在当前线程修改 state 之前，锁刚好被释放了。
          由于当前线程已经把 state 改成了 2，
          所以当前线程现在获得了锁，返回。
   4.3 如果 old 不等于 0：
          说明锁仍然被其他线程持有。
   4.4 调用 MFUTEX_WAIT，在 mutex.state 上等待，并指定期望值为 2。
   4.5 被唤醒后，重新回到循环头部，再次尝试获得锁。

unlock(mutex):
1. 原子地将 mutex.state 减 1，并取得减 1 之前的旧值 old（注意修改与取得旧值是一个原子操作）。
2. 如果 old 等于 1：
      说明锁之前是“已加锁，但没有已知等待者”的状态。
      减 1 后 mutex.state 已经变成 0。
      锁已经释放，不需要唤醒任何线程，直接返回。
3. 如果 old 不等于 1：
      说明 old 等于 2，也就是锁之前处于“已加锁，并且可能有等待者”的状态。
4. 将 mutex.state 原子地设置为 0，表示锁已经释放。
5. 调用 MFUTEX_WAKE，在 mutex.state 上唤醒最多 1 个等待线程。
6. 返回。

文件：user/lib/mthread.c

int mthread_mutex_lock(mthread_mutex_t *mutex) {
    // 1-2: 快速路径，尝试 0 → 1
    uint32_t expected = 0;
    if (__atomic_compare_exchange_n(&mutex->state, &expected, 1,
            0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
        return 0;                        // 成功获得锁
    // 3: 进入慢速路径
    for (;;) {
        // 4.1: 原子地把 state 改为 2，并取得旧值 old
        uint32_t old = __atomic_exchange_n(&mutex->state, 2, __ATOMIC_ACQUIRE);
        // 4.2: 如果 old == 0，说明刚被释放，当前线程获得锁
        if (old == 0)
            return 0;                    // 获得锁，state 已为 2
        // 4.3-4.4: old != 0，等待
        syscall_mfutex(&mutex->state, MFUTEX_WAIT, 2);
        // 4.5: 被唤醒后回到循环头部
    }
}

• 伪代码中“被唤醒后重新回到循环头部，再次尝试获得锁”，在实现中体现为 for(;😉 循环，被唤醒后再次执行 __atomic_exchange_n，而不是回到步骤 1 做 CAS 0→1。直接 exchange 2，若旧值为 0 则获得锁，同时 state 维持 2，保证后续 unlock 能正确识别等待者。

int mthread_mutex_unlock(mthread_mutex_t *mutex) {
    // 1: 原子减 1，并取得旧值 old
    uint32_t old = __atomic_fetch_sub(&mutex->state, 1, __ATOMIC_RELEASE);
    // 2: 如果 old == 1，直接返回
    if (old == 1)
        return 0;
    // 3-4: old == 2，将 state 设为 0
    __atomic_store_n(&mutex->state, 0, __ATOMIC_RELAXED);
    // 5: 唤醒最多 1 个等待线程
    syscall_mfutex(&mutex->state, MFUTEX_WAKE, 1);
    return 0;
}

• 通过 __atomic_fetch_sub 将 mutex.state 减 1 并返回旧值，实现原子地减一并取得旧值。
• 后续判断 old == 1，否则执行 store 0 和 mfutex_WAKE

6. 其他宏添加

• include/error.h 添加 E_AGAIN 100 和 E_BUSY 101。
• include/mfutex.h 定义 MFUTEX_WAIT 0 和 MFUTEX_WAKE 1。
• user/lib/syscall_lib.c 添加所有新系统调用的用户态封装函数。

---

思考题

Thinking 1

扩展线程机制后，线程与进程共用同一个调度实体 struct Env，调度器仅通过 env_status 和 env_sched_list 区分可运行的任务，并不区分是进程还是线程。因此完全可以直接复用现有的 schedule() 轮转调度逻辑，无需额外实现一套独立的调度器。

Thinking 2

同一线程组内的线程共享资源：

• 虚拟地址空间：env_pgdir 指向同一个页目录，代码段、数据段、堆等完全共有。
• 文件描述符表。
• 线程组标识 env_tgid。

独立保存的状态：

• CPU 寄存器上下文：每个线程需要独立的 env_tf，保存自己的 PC、SP、通用寄存器等。

• 用户态栈：env_tf 中的 SP 寄存器应指向各自独立的用户栈区域，否则函数调用和局部变量会相互干扰。

• env_pgdir 为线程组提供共享的地址空间。

• env_tf 用于保存和恢复线程各自的执行现场。

• 用户栈的独立划分保证了多线程在同一个地址空间中不会互相破坏调用栈。

Thinking 3

若线程调用 sys_exit 后直接释放控制块，则那些正在 sys_wait 中等待该线程退出的线程将失去获取返回值的唯一途径，或者访问已释放的内存，导致系统错误。进入 ENV_ZOMBIE 状态则保留了返回值 env_return_value 和控制块本身，等待线程可以在检测到该状态后安全地读取返回值，然后由等待者调用 env_free_thread 显式回收，从而避免访问非法内存。

Thinking 4

如果去掉状态 2，只有 0 和 1 两态，在给出的场景下：

• T3 时刻线程 A unlock 使 state 变为 0 并调用 MFUTEX_WAKE，但此时线程 B 尚未正式进入 MFUTEX_WAIT，所以 WAKE 操作实际上没有唤醒任何线程。
• T4 时刻线程 B 比较 state 发现为 0，条件满足，于是进入阻塞。
• 最终 B 永久等待，而 A 早已释放锁且不会再唤醒。

三态设计中，线程 B 在竞争锁失败时将 state 改为 2，并用 MFUTEX_WAIT(2) 阻塞。线程 A 在解锁时将 state 减 1，发现旧值为 2，于是执行 MFUTEX_WAKE，确保 B 最终被唤醒。如果 A 在 B 改 state 之前就释放了锁，B 在 exchange 时会读到 old=0，从而直接获得锁，并保留 state=2，无需等待。

Thinking 5

• 当目标线程尚未退出时，sys_wait 将当前线程标记为 ENV_NOT_RUNNABLE，并从调度链表移除。
• 修改当前 regs[2] 为 0，然后调用 schedule(1)。
• schedule从就绪列表中选择另一个可运行的 Env 调用 env_run
• env_run切换页目录并执行 env_pop_tf 以恢复新线程的上下文并回到用户态。
• 当等待的线程最终退出并唤醒本线程时，本线程被插回就绪链表，等待调度器重新选中。

env_pop_tf 恢复的就是之前在内核栈上保存的 Trapframe，其中的 regs[2]=0 使得用户态 syscall 函数返回 0，满足要求。

Thinking 6

将“读 + 比对”拆分成两步非原子操作，存在以下并发问题：

• 第一步线程 A 读取 *uaddr 得到的值与 val 相等。
• 在 A 尚未调用阻塞服务之前，另一个线程 B 可能已经修改了 *uaddr 并调用了 MFUTEX_WAKE。
• 之后 A 继续执行阻塞，而 WAKE 事件已经错过，导致 A 永久阻塞。

因此内核必须保证“比较”与“加入等待队列”这两个操作是原子的，防止中间插入状态变化。

Thinking 7

当等待队列中有 3 个阻塞线程，调用 MFUTEX_WAKE(uaddr, 10) 时，内核只会将这 3 个线程挨个唤醒，并不会因为 val 较大而发生错误或空操作。

系统调用的语义为“至多唤醒 val 个线程”，而不是严格唤醒固定数量，调用者不必提前精确知晓阻塞线程的数量，只需传递一个足够大的值即可期望全部唤醒。

Thinking 8

解决方法是维护一个记录各栈槽位的占用状态的数据结构（如位图），数组大小为 1024（4MB / 4KB）。创建线程时，遍历该结构找到第一个空闲槽，将其标记为已占用并将对应地址分配给新线程。当线程退出时根据栈地址计算出其占用的槽号，将对应位清零。这样，即使已经经历大量创建与销毁线程，只要同时存在线程数不超过 1024，栈空间都能被重复利用而不会越界。