前言：我是ZK老师铁粉！！！
1. 实验目的
（1）通过阅读相关源码，掌握NachOS调度的数据结构和实现过程；
（2）对NachOS线程描述进行完善，增加关于调度的内容；
（3）掌握NachOS线程调度的算法。
2. 实验内容
（1）在NachOS线程描述中增加调度优先级的数据成员，并完善就绪队列管理的成员方法；
（2）实现基于优先级的FCFS调度；
（3）调度时，线程的产生和调度须同时进行，并且要构建它们的线程家族树。
线程的创建及调度和分配CPU的流程：
-
main线程会占用CPU，执行SelfTest函数 -
然后
SelfTest函数可以创建一个线程 -
main线程会执行Fork函数，Fork函数将新线程放入就绪队列中 -
Fork函数执行完毕后，会通过当前线程执行Yield函数让出CPU，就绪队列中调度一个符合要求的线程分配CPU -
新线程会执行
SimpleThread函数，我们可以让SimpleThread也创建线程，且为当前线程的子线程，以此验证当前线程是否执行且可以创建新线程 -
子线程创建完毕后，也会执行
Fork函数，执行完毕后接着执行Yield函数 -
放弃CPU后，就绪队列调度符合要求的一个线程分配CPU
-
直至线程数达到最大限制，就不会新建线程
-
在每次创建新线程时，我们可以记录当前线程和新线程的父子关系，便于后续打印家族树
-
我采用数据结构中的邻接表存储线程之间的父子关系，然后定义一个新函数，打印家族树
-
新函数可以放在
SelfTest的底部，就绪队列中线程全部调度运行完后，无线程可调度时，再次分配CPU给main函数，执行自定义打印方法。
上述逻辑实现了边产生边调度、构建线程家族树。
基于优先级的FCFS调度在线程加入就绪队列时进行操作。
通宵七天七夜阅读相关源码，看懂了大部分的NachOS线程调度的算法，完美的完成了设定的实验目的。
3. 我的步骤
为了便于理解算法思路，我不会按照运行顺序修改各种代码，而是按照每个功能定义使用顺序。
3.1 在threads文件夹中实行的操作
在 thread.cc 中，创建一个动态数组存储家族树，也就是邻接表（学过图论的熟悉）。
//算竞写法 #include <cstdlib> #include <ctime> //随机数需要 #include <vector> //用vector来存图 static Thread* myThread[MAX_SIZE]; //线程数组 vector<int>t_value[MAX_SIZE]; //以图存树
在 thread.cc 中，编写 PrintThreadTree 函数递归输出家族树。此函数需放在 selfTest 之前，后面代码并未声明此函数。
在 thread.h 中，修改最大线程数，这个决定我们能新建多少个线程，最大线程数少一些更容易了解线程运行流程。
在 thread.h 中，声明一个新的构造函数，在后面的 thread.cc 中会具体实现。
定义每个线程的id号和优先级，用来实现按优先级分配。
在 thread.cc 中，重载一个构造函数（记住，可以说是新建一个，而不是修改原有的），赋值线程号，从 1 开始分配，优先级会通过函数参数提供。构造函数重载即通过不同的函数参数调用不同的构造函数。
这个构造函数会在新建时运行，后续的 new Thread(tname, p); 即调用构造函数。
Thread::Thread(const char* threadName, int priority)
{
if (++threadNum >= MAX_SIZE) {
cout << " 达到最大线程数：" << MAX_SIZE << " ";
ASSERT(threadNum <= MAX_SIZE);
}
int i = 0;
for (i = 0; i < MAX_SIZE; i++) {
if (Tstatus[i] == 0) { //如果线程号未被使用，便执行以下操作
this->tid = i + 1; // 给线程赋上一个id号， 因为是从0开始计算，所id号需要加1
Tstatus[i] = 1; //将该线程号状态置为1，表示已经被使用了
break;
}
}
this->priority = priority;
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
for (int i = 0; i < MachineStateSize; i++) {
machineState[i] = NULL; // not strictly necessary, since
// new thread ignores contents
// of machine registers
}
space = NULL;
} 在 thread.cc 中，修改 SelfTest 函数。该测试函数会在程序刚开始时就被 main 线程调用，且只调用一次。
我在这里通过 main 线程创建第一个线程优先级随机数分配，通过 Fork 函数将该线程加入到就绪队列中。
然后调用 Yield 函数使 main 线程让出CPU，从就绪队列中调度一个线程分配CPU。
在就绪队列为空后，main 线程会继续占用CPU，执行后续。
后续执行我新加的 PrintThreadTree 函数打印线程家族树。
void
Thread::SelfTest()
{
//---------------------------------------------------以下为源代码被注释bgn
/*DEBUG(dbgThread, "Entering Thread::SelfTest");
//Thread *t = new Thread("forked thread");
//t->Fork((VoidFunctionPtr) SimpleThread, (void *) 1);
//kernel->currentThread->Yield();
//SimpleThread(0);*/
//----------------------------------------------------以上为源代码被注释end
DEBUG(dbgThread, "Entering Thread::SelfTest");
srand(time(0) + threadNum); //设置一个随机种子
int p = rand() % (5) + 1;
myThread[threadNum] = new Thread("th1", p);
myThread[threadNum]->Fork((VoidFunctionPtr)SimpleThread, (void*)myThread[threadNum]);
kernel->currentThread->Yield();
//for (int i = 1; i <= 7; ++i)
//{
// if (t_value[i - 1].empty()) continue;
// for (int j = 0; j < (int)t_value[i - 1].size(); ++j) {
// cout << t_value[i - 1][j] <<"\n";
// }
//}
cout << "\n线程家族树为：\n";
PrintThreadTree(1, 0);
} 在 thread.cc 中，修改 Yield 函数。Yield 函数会让出CPU，将当前线程加入就绪队列，再从就绪队列中调度一个线程，分配CPU。
void
Thread::Yield()
{
Thread* nextThread;
IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
ASSERT(this == kernel->currentThread);
DEBUG(dbgThread, "Yielding thread: " << name);
//---------------------------------------以下为修改处bgn
kernel->scheduler->ReadyToRun(this);
//---------------------------------------以上为修改处end
nextThread = kernel->scheduler->FindNextToRun();
if (nextThread != NULL) {
//----------------------------------------以下代码被注释bgn
//kernel->scheduler->ReadyToRun(this);
//----------------------------------------以上代码被注释end
kernel->scheduler->Run(nextThread, FALSE);
}
(void)kernel->interrupt->SetLevel(oldLevel);
} 在 thread.cc 中，重新写个 SimpleThread 函数。因为前面创建新线程时，使用了 Fork((VoidFunctionPtr)SimpleThread, (void*)xxx) ，所以当某个新线程获得CPU后会运行 SimpleThread 函数。
我们使用循环让当前线程创建多个新线程。
如果当前线程数没有达到最大值，就随机一个优先级，创建新线程且赋值优先级。输出验证几号线程创建新线程。
记录新线程由几号线程创建，便于后续输出线程家族树。
然后通过 Fork 放入就绪队列。
接着让出CPU，实现边创建边调度。下面图片第一次输出后面敲错了，不是\t而是\n
static vod
SimpleThread(Thread* t) //传入线程
{
//IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
for (int i = 1; i <= 3; ++ i) //每一个线程调用三次
{
cout << endl << "优先级为" << t->priority << " 的 " << t->tid << "号线程正在进行 第" << i << "次调度\n";
if (threadNum < MAX_SIZE) { //未达到最大线程数
srand(time(0) + threadNum); //设置一个随机种子
int p = rand() % (5) + 1;
myThread[threadNum] = new Thread("thi", p);
cout << "优先级为" << t->priority << " 的 " << t->tid << "号线程创建了,优先级为" << myThread[threadNum]->priority << " 的 " << myThread[threadNum]->tid << "号线程" << endl;
t_value[t->tid - 1].push_back(myThread[threadNum]->tid); //几号线程创建了几号线程,存入图中
myThread[threadNum]->Fork((VoidFunctionPtr)SimpleThread, (void*)myThread[threadNum]);
}
else {
cout << "已达最大线程数，无法再创建线程\n";
}
kernel->currentThread->Yield();
}
} 在 scheduler.cc 中修改 ReadyToRun 函数。该函数功能为将函数参数对应线程加入就绪队列中。如果为空，可以直接加入队尾；不为空，按照我们下面的新建的 NewSort 方法以优先级和到来顺序插入就绪队列某一位置。
3.2 在lib文件夹中实行的操作
在 list.h 中，创建一个新的 Newsort 方法，实现按优先级调度和先来先服务。
ZK老师：在放入时或者取出时进行顺序的排序，可以实现不同调度算法。人生中许多事情的成功与否也是如此，往往取决于我们选择何时“放入”（开始行动）或“取出”（收获成果）。孔子说的“时也，命也”，以及古希腊的”kairos“（恰当时机）也是同样的道理。
在 list.cc 中，编写 Newsort 方法。因为使用的是单链表，下面就是一个普通的排序算法。
4.优化部分和修改问题
还有几个可能优化的地方：
-
我采用一个List单调放不同的优先级线程来实现调度，可以使用多个List存放不同优先级线程，算法速度能达到 ，通过索引找到对应List，放入后面即可
-
也可以采用二叉堆的数据结构，将平均时间复杂度从 优化到
-
我使用邻接表存储线程父子关系，也可使用链式前向星或者利用指针链表式的存储，例如线程类里定义父节点指针和子节点指针、兄弟节点指针等。
-
可以在每次创建新进程后打印家族树，需注意我打印树函数未声明，需将该函数申明或者放于前列，后面函数才能调用
-
可以删除节点，可以只在邻接表中删除节点不在空间中删除，邻接表实现非常简单，也可以简单的实现托孤。
-
还能可持久化维护，保存历史家族树，修改邻接表的存储方式，转为指针，参考可持久化线段树
京公网安备 11010502036488号