实验一 Nachos调度系统
一、概述本实验首先对Nachos作一简要的介绍，然后要求完成有关线程调度的练习。我们提供了一部分该模拟器的代码框架，但非常有限，它不包括文件系统、网络支持、虚存和用户级编程支持，只有线程结构----SWITCH程序和相关的一些材料。实验的任务就是：读懂这些代码，并实现5个调度算法：先来先服务（FCFS）、优先级（抢占式、非抢占式）、轮转和多级排队。
二、任务
2.1 预备
(1) 阅读有关实验材料。
仔细下载并阅读本实验说明和源代码。实验说明和源代码包含在下面zip文件中：
http://os.cs.tsinghua.edu.cn/2001_OS_Experiments/2001-04-21%20mp1.zip
阅读关于Nachos更为详细的说明，如论文“A Road Map through Nachos”(http://os.cs.tsinghua.edu.cn/2000HomepageForOs/2000-04-10%20RoadMap.zip)等。
(2) 取得在Linux下展开源代码包。
cp /home/experiments/mp1.tar.gz,
gunzip mp1.tar.gz
tar –xvf mp1.tar
(3) 编译源代码
cd mp1/threads
gmake depend
gmake
(4) 运行一简单测试
,/nachos
2.2 调度算法的实现需要修改的文件：scheduler.h,scheduler.cc。
(1) 实现FCFS
找到文件scheduler.cc中的Scheduler::FindNextToRun()，这是实现调度算法的函数，它基于Scheduler::SetSchedPolicy()中设置的调度策略来实现相应的调度算法。最简单的调度算法是FCFS，写出代码，从ReadyList中找出下一个运行的线程并返回（参见文件list.h和list.cc）。代码写完后，如前所述重新编译，运行test0以检查运行结果。
(2) 实现优先级调度实现FCFS调度算法后，在Nachos线程中引入优先级，并实现一个基于优先级的调度器。线程优先级是一个介于MIN PRIORITY和MAX PRIORITY（在Threads类中定义）间的整数。在线程创建期间，如果没有赋予线程优先级，则它的优先级与父线程相等。进程创建的第一个线程的优先级设为NORM PRIORITY（在Threads类中定义）。
修改线程调度器，使它按降序调度下一个线程，若两线程优先级相等，则仍按FCFS调度。
注意：
在测试期间不要用SetPriority方法动态改变线程优先级；
抢占式优先级调度和非抢占式优先级调度均需实现（分别用test1和test2测试）。
(3) 实现轮转调度修改线程调度器，使它轮流调度每一个线程。用test3检查运行结果。
(4) 实现多级排队调度修改线程调度器，实现多级排队调度。系统中的队列数由Scheduler::SetNumQueue()设置，该函数由实验者自己完成，另外，各队列可享有不同的优先级（可参照基于优先级调度器中优先级的生成方法设置），而每个队列中的线程采用FCFS策略。代码完成并编译后，用test4检查结果。
2.3 提交结果实验分组进行，每两个人一组。电子文档部分请用WinZip压缩后交教师（Mailto,xyong@csnet4.cs.tsinghua.edu.cn）。
实验报告（包括书面报告和电子文档）；
源代码中修改过的文件；
三、有关Nachos的一些细节
该实验涉及到的文件有：
main.cc ---- 建立系统环境，调用函数ThreadTest();
threadtest.cc ---- 调用相应的测试函数进行测试；
test.?.cc ---- 由threadtest.cc调用的测试函数，test.0.cc是缺省测试函数；
thread.h,thread.cc ---- 线程数据结构和线程操作，如线程创建、线程睡眠和线程结束。
运行Thread::Sleep()要特别小心（当它被调用时，假定中断是关
闭的）；
Scheduler.h,scheduler.cc ---- 管理线程的运行；
List.h,list.cc ---- 通用列表管理（C++中的LISP）；
System.h,system.cc ---- Nachos的启动/停止程序；
Utility.h,utility.cc ---- 一些有用的定义和调试程序；
Switch.h,switch.cc ---- 启动线程和上下文交换的汇编语言程序；
Interrupt.h,interrupt.cc ---- 打开/关闭中断；
Timer.h,timer.cc ---- 仿真一个周期性引发中断的时钟；
Stats.h ---- 收集相关统计信息。
一、概述本实验首先对Nachos作一简要的介绍，然后要求完成有关线程调度的练习。我们提供了一部分该模拟器的代码框架，但非常有限，它不包括文件系统、网络支持、虚存和用户级编程支持，只有线程结构----SWITCH程序和相关的一些材料。实验的任务就是：读懂这些代码，并实现5个调度算法：先来先服务（FCFS）、优先级（抢占式、非抢占式）、轮转和多级排队。
二、任务
2.1 预备
(1) 阅读有关实验材料。
仔细下载并阅读本实验说明和源代码。实验说明和源代码包含在下面zip文件中：
http://os.cs.tsinghua.edu.cn/2001_OS_Experiments/2001-04-21%20mp1.zip
阅读关于Nachos更为详细的说明，如论文“A Road Map through Nachos”(http://os.cs.tsinghua.edu.cn/2000HomepageForOs/2000-04-10%20RoadMap.zip)等。
(2) 取得在Linux下展开源代码包。
cp /home/experiments/mp1.tar.gz,
gunzip mp1.tar.gz
tar –xvf mp1.tar
(3) 编译源代码
cd mp1/threads
gmake depend
gmake
(4) 运行一简单测试
,/nachos
2.2 调度算法的实现需要修改的文件：scheduler.h,scheduler.cc。
(1) 实现FCFS
找到文件scheduler.cc中的Scheduler::FindNextToRun()，这是实现调度算法的函数，它基于Scheduler::SetSchedPolicy()中设置的调度策略来实现相应的调度算法。最简单的调度算法是FCFS，写出代码，从ReadyList中找出下一个运行的线程并返回（参见文件list.h和list.cc）。代码写完后，如前所述重新编译，运行test0以检查运行结果。
(2) 实现优先级调度实现FCFS调度算法后，在Nachos线程中引入优先级，并实现一个基于优先级的调度器。线程优先级是一个介于MIN PRIORITY和MAX PRIORITY（在Threads类中定义）间的整数。在线程创建期间，如果没有赋予线程优先级，则它的优先级与父线程相等。进程创建的第一个线程的优先级设为NORM PRIORITY（在Threads类中定义）。
修改线程调度器，使它按降序调度下一个线程，若两线程优先级相等，则仍按FCFS调度。
注意：
在测试期间不要用SetPriority方法动态改变线程优先级；
抢占式优先级调度和非抢占式优先级调度均需实现（分别用test1和test2测试）。
(3) 实现轮转调度修改线程调度器，使它轮流调度每一个线程。用test3检查运行结果。
(4) 实现多级排队调度修改线程调度器，实现多级排队调度。系统中的队列数由Scheduler::SetNumQueue()设置，该函数由实验者自己完成，另外，各队列可享有不同的优先级（可参照基于优先级调度器中优先级的生成方法设置），而每个队列中的线程采用FCFS策略。代码完成并编译后，用test4检查结果。
2.3 提交结果实验分组进行，每两个人一组。电子文档部分请用WinZip压缩后交教师（Mailto,xyong@csnet4.cs.tsinghua.edu.cn）。
实验报告（包括书面报告和电子文档）；
源代码中修改过的文件；
三、有关Nachos的一些细节
该实验涉及到的文件有：
main.cc ---- 建立系统环境，调用函数ThreadTest();
threadtest.cc ---- 调用相应的测试函数进行测试；
test.?.cc ---- 由threadtest.cc调用的测试函数，test.0.cc是缺省测试函数；
thread.h,thread.cc ---- 线程数据结构和线程操作，如线程创建、线程睡眠和线程结束。
运行Thread::Sleep()要特别小心（当它被调用时，假定中断是关
闭的）；
Scheduler.h,scheduler.cc ---- 管理线程的运行；
List.h,list.cc ---- 通用列表管理（C++中的LISP）；
System.h,system.cc ---- Nachos的启动/停止程序；
Utility.h,utility.cc ---- 一些有用的定义和调试程序；
Switch.h,switch.cc ---- 启动线程和上下文交换的汇编语言程序；
Interrupt.h,interrupt.cc ---- 打开/关闭中断；
Timer.h,timer.cc ---- 仿真一个周期性引发中断的时钟；
Stats.h ---- 收集相关统计信息。
