内容一：总体概述

本次 lab 的主要内容是在理解 Nachos 线程管理机制的基础上进行扩展，添加 UID 和 TID 两个成员变量，并增加相应的维护机制；此外，还需要设置 Nachos 允许同时存在的最大线 程数并增加 TS 指令。本次 lab 的重点在于理解 Nachos 的线程管理机制，在理解的基础上进一步拓展其功能。

内容二：任务完成情况

任务完成列表（Y/N）

	exercise1	exercise2	exercise3	exercise4
完成情况	Y	Y	Y	Y

具体Exercise的完成情况

Exercise1 调研

Linux中进程控制块的基本实现方式：
每一个进程由一个对应的task_struct数据结构描述，用来维护进程的相关信息。其中包含有：
（1） 进程状态。一共有TASK_RUNNING（可运行）、TASK_INTERRUPTIBLE（可中断的等待状态）、TASK_UNINTERRUPTIBLE（不可中断的等待状态）、TASK_STOPPED（暂停）、TASK_ZOMBIE（僵死）、TASK_SWAPPING（换入/换出）六种状态。
（2） 进程调度信息。决定系统中哪个进程最应该运行，进程的调度策略分为SCHED_OTHER（其他调度）、SCHED_FIFO（先来先服务调度）、SCHED_RR（时间片轮转调度）三种。
（3） 标识符（PID）。每个进程由一个唯一的标识符确定，PID是一个32位的无符号整数，被顺序编号，用户程序通过PID调度进程。
（4） 进程通信有关信息（IPC）。管理进程之间数据的交流。
（5） 进程链接信息。管理进程之间的父/子关系，使进程之间的协作更加方便。
（6） 时间和定时器信息。记录进程从创建到终止使用CPU的时间，以便进行统计、计费等有关操作。
（7） 文件系统信息。记录进程使用文件的情况。
（8） 虚拟内存信息。管理每个进程的地址空间（虚拟空间）。
（9） 页面管理信息。当物理内存不足时，负责进行页面的交换。
（10） 和处理器相关的环境信息。当进程暂时停止运行时，处理器必须保存上下文信息在进程的thread_struct结构中，当进程被调度重新运行时再恢复这些环境。
（11） 其他。

与Nachos中进程控制块的基本实现方式的异同：
Nachos的进程控制块相关信息定义在code/threads/thread.h中，其中只包含有stackTop指针（指向栈顶）、stack指针（指向栈底）、status（JUST_CREATED, RUNNING, READY, BLOCKED）、name、machineState（保存其他未运行进程寄存器的状态）。相比较Linux中PCB的实现方式，Nachos中的信息较少，实现较为简单，只有一些基本的状态参数和基本的操作函数。

Exercise2 源代码阅读

main.cc是Nachos整个程序的入口，其中对整个Nachos中的数据结构进行了初始化，此外解析命令行传入的参数，根据不同的参数进而调用Nachos的不同方法。

threadtest.cc提供了thread的测试方法，当testnum被设置成1的时候，ThreadTest函数会进一步调用ThreadTest1函数，ThreadTest1函数会创建一个线程，该线程会进一步fork出一个子线程，两个线程都去调用SimpleThread函数，通过线程的Yield函数自动放弃占用CPU，实现两个线程交替输出。

thread.h提供了Thread类的定义，其中包括栈顶指针、栈底指针、线程名字、线程状态、寄存器状态等变量，也声明了Fork()、Yield()、Sleep()、Finish()、CheckOverflow()、setStatus()、getName()、Print()、ThreadAllocate()这些针对线程操作的函数。

thread.cc中对thread类的构造函数、析构函数以及各个成员函数进行了具体化，如Fork()通过分配并初始化堆栈，将一个线程放入准备队列；CheckOverflow()检查栈是否溢出；Finish()设置threadToBeDestroyed为当前线程，并调用Sleep()函数；Sleep()将当前线程的状态设置为BLOCKED，寻找下一个即将运行的线程；Yield()寻找下一个即将运行的线程，通过scheduler->Run()使新的线程占用CPU运行；StackAllocate()为线程分配需要的堆栈空间。其中Fork()、Finish()、Sleep()、Yield()的操作都是原子的，通过interrupt->SetLevel(IntOff)保存中断层次关闭中断，在操作完成后再恢复原状态。

Exercise3 扩展线程的数据结构

第一步：先在thread.h中为Thread类添加了UID和TID两个int型的变量，然后声明了get_UID()和get_TID()两个函数，分别返回该线程的UID和TID。

第二步：在system.cc中定义一个长度为128的int型数组TID_list，用于记录已经被占用的TID编号，在Initialize()函数内将其初值赋为0。之后在system.h中外部声明这个数组。

第三步：在thread.cc中为UID和TID两个成员变量进行维护。首先在构造函数中，对于一个新的线程，调用系统getuid()函数获得UID编号，顺序遍历TID_list找到第一个没有被占用的TID编号。接下来在析构函数中，当一个线程被释放时，将其占用的TID编号恢复空闲，方便之后的线程使用。

Exercise4 增加全局线程管理机制

第一步：如Exercise3中所述，将TID_list的大小设置为128，即Nachos中最多能同时存在128个线程。在thread.cc的构造函数中，当找不到一个空闲的TID编号时，将当前线程的TID编号设为-1，通过ASSERT( TID != -1 )使程序强制终止。

第二步：增加一个TS命令，为了显示当前系统中所有线程的信息和状态，需要为每个线程保存一个指向它的指针。于是在system.cc中定义长度为128的指针数组threadPointer，用来指向对应TID编号的线程，同时在system.h中外部声明该数组。

第三步：在thread.cc中构造函数中，设置新创建线程TID编号对应的指针指向该线程；在析构函数中，让对应指针指向NULL。

第四步：由于需要打印线程状态，所以在thread.h中为Thread类添加成员函数get_status()，用来返回当前线程的状态。

第五步：在threadtest.cc中创建相应的测试函数ThreadTest2()和ThreadTest3()，分别对应testnum为2和3的情况。其中ThreadTest2中创建超过128个线程用来测试最大线程数量；ThreadTest3中打印所有现存线程的name, UID, TID和status。并在main.cc中添加为测试最大线程数量和TS指令设置相应testnum的程序。

最大线程数量测试结果如下：

TS指令测试结果如下：

内容三：遇到的困难以及解决方法

困难1 不知道怎么设置当前线程的UID

一开始我尝试将所有线程的UID都设置为0，但之后在上网查阅资料的过程中了解到，linux系统中可以通过包含两个头文件<unistd.h>和<sys/types.h>进而调用getuid()函数获得当前UID，问题得到解决。

内容四：收获及感想

通过完成这次lab，我对Nachos的线程管理机制有了更加深入的理解，同时通过调研linux中进程控制块的实现，对二者的区别有了更加清晰的认识。

在做lab之前我也调研阅读了关于Nachos的一些文献，其中对于Nachos的线程管理机制也有描写，但是读书不如亲自动手来的效果好，在做完lab之后，才可以说对于书中的描述有了更加深刻的理解。

内容五：对课程的意见和建议

我建议讨论课的时候可以大家多交流交流自己lab的实现方式，看看有没有一些比较好的想法，也可以看看大家有没有碰到一些相同的问题，可以讨论一起解决，一起进步。

关于Nachos源码的问题我也遇到了一个，就是Nachos中线程第一次运行时不会调用scheduler::run，因此导致不会释放之前的线程。我在析构函数中添加打印函数后，发现对于test1的结果只有一个线程被回收了。经过群里讨论助教说明了是Nachos本身的问题。

内容六：参考文献

[1] Andrew S. Tanenbaum著．陈向群 马洪兵 译 .现代操作系统［Ｍ］．北京：机械工业出版社，2011：47-95．
[2] linux进程控制块task_struct描述:
https://blog.****.net/jnu_simba/article/details/11724277?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
[3] linux系统编程之进程: https://www.cnblogs.com/mickole/p/3185889.html