操作系统nachoes一些问题与解决方法
山东大学操作系统课设，自己做的过程中的遇到的一些问题，如果有参考价值可以使用：
- 一些粗略的问题和感想
- 详细project1思路与解决
- 详细project2思路和解决
一些粗略的问题和感想
首先，我花了很长时间在了解 Nachos 的运行机制与框架上，尤其是与 java 虚拟机 线程的关系，但在具体实现中，仍然感到抓住系统的大体构架有些难度。每次修改时，会有种牵一发而动全身的感觉。
前几周，看完实验要求后，感觉前几节上课讲的 nachos 的基本原理、运行机制， 安全防护之类的与实验关系不大，但我留下了笔记。这些细节的操作在写代码的时候起了很大的作用。
开始做实验时，我第一步可能和别人不太一样，我是先把nachos里面的代码注释基本上都翻译了一遍，用这个方法来加深我对nachos系统主体框架的理解。第二步真正进入实验，刚才沈立返讲了第一个实验，那我就不讲了。但是稍微讲一下自己遇到的问题，就是个线程的时候测试没错，多个线程一起创建就会有错，改正方法是：主动调用等待队列的所有线程，每一次都要用到nextThread方法。
后面ｐｒｏｊｅｃｔ１里面的几个问题其实和第一个差不多，都是同步的问题，基本都是当一个线程运行着，其他有线程创建了或者是要执行，要实现原子性，所以需要加锁进入等待队列ｓｌｅｅｐ，然后当前线程执行完就唤醒其他线程，他们就释放锁准备执行。其中出现的一个问题是，我在条件变量那个题时，想成了让线程去调用线程。查了一下资料发现，线程由执行状态转变为阻塞状态是有线程自己调用阻塞原语实现的。进程要就绪，是另一个发现者进程（或系统中断（实验三ALArm））调用唤醒原语来实现的。
还有一个当时遇到的问题是关于waitUntil多次运行得到的唤醒时间都是一致的这一点，最初阅读源码发现唤醒正在等待特定的时间唤醒的进程是由系统中断的handler来处理的，该中断的触发时间是一个随机数，并且在500跳左右浮动，然后每次中断时间多次运行都是一致的，开始考虑为什么是相同的。思考之后，觉得可能是随机数生成器的种子一直是设置的一个定值，为了找到生成器种子的设定我和同学讨论并且解读了相关部分的源码，并且当时为了确定setSeed方法的调用地点，还在该方法内部抛出了一个null pointer异常，来通过java的异常track来查看调用递归序列，找到了设置的地点，最终发现seed一直都被设置为0，所以所有的生成序列都是相同的
第六个主要是逻辑上的问题，一定是孩子先过去，然后就是相关操作和条件的控制。（speak?）都是条件变量的问题，而且比较独立。方案是：使用一个锁变量保证互斥,四个条件变量保证同步。结构如下：首先创建大人线程和孩子线程——获取锁——唤醒一个孩子进程——释放锁。 。刚才韩楚怡讲了我就不详细讲了。
只有小孩可以有返程路线，大人返程没有意义；要避 免出现当大人到 M 岛上而没有孩子在 M 岛上出现这种情况。开始之前让所有人 sleep, 然后 begin()叫醒一个 child, 然后每次一个人干完了活叫醒另一个然 后自己睡，所有人都是被动的，相比所有人都主动竞争当驾驶员或乘客，这样可 以避免冲突。
现在遇到的问题，就是第五个问题中感觉自己写完了，但是运行的不是很对，要实现nachos中的优先级调度。问了同学，说是需要改一下conf文件，但是我还没有实验。
大概就是这些
关于两个进程之间进行的通信的设计，采用一个等待队列的设计，因为同一时段队列中只可能存在一种进程，全是speaker或者全是listener，因为假设如果存在speaker、listener同时在队列中，那么当第一个非相同类型的进程准备进入队列的时候，就会取出一个相对类型的进程进行通信，这样就造成队列中只会有一种类型的进程在等待着，因此就只需要有一个队列存在就可以了。
单做第一个ｊｏｉｎ，大概花了2周的时间，开始总感觉自己找不到题目的脉络，后来就和同学一起讨论，发现这就是个线程同步的问题。比如当Ａ线程正在运行时，Ａ执行Ｂ．ｊｏｉｎ（），则Ｂ开始运行，Ａ就被挂起，Ｂ结束后才能再执行Ａ。关键一点是Ｊｉｏｎ完后需要唤醒等待队列中的所有线程，因为在这期间，并不一定只有两个线程在执行。所以修改ｆｉｎｉｓｈ的时候要注意它既可以主动被调用也可以直接调用，而且不能结束当前运行的线程。在测试的时候也是遇到这个问题，两个线程的时候测试没错，多个线程一起创建就会有错，改正方法是：
KThread waitThread= currentThread.waitJoinQueue.nextThread(); //调用等待队列上的第一个进程;
while (waitThread != null) //while
{
waitThread.ready(); //唤醒等待队列上所有被阻塞的进程
waitThread= currentThread.waitJoinQueue.nextThread(); //调用等待队列上的第一个进程
}
主动调用等待队列的所有线程，每一次都要用到nextThread方法。
详细project1思路与解决
Task 1 实现 KThread.join()
要求
实现KThread.join()函数。注意：其他线程没必要调用join()，但是一旦调用只能调用一次。对一个线程调用两次join()的行为是未定义的，即使第二个调用者是一个不同的线程。无论一个线程是否被调用都要能够正常执行结束。
分析
join()函数的作用应为，若A线程调用 B.join()，则A线程需要刮起，等待B线程执行结束再继续执行。
方案
在KThread类中添加一个阻塞队列，每次其他线程调用该线程的join()方法时都阻塞在该队列中，当该线程执行结束时，将队列中阻塞的线程取出并加入就绪队列。
实现代码
修改KThread.join()和KThread.finish().
public void join() {
Lib.debug(dbgThread, “Joining to thread: ” + toString());
Lib.assertTrue(this != currentThread);
boolean iniStatus = Machine.interrupt().disable();
if (status != statusFinished) {
waitForJoin.waitForAccess(currentThread);
KThread.sleep();
}
Machine.interrupt().restore(iniStatus);
}
public static void finish() {
Lib.debug(dbgThread, "Finishing thread: " + currentThread.toString());
Machine.interrupt().disable();
Machine.autoGrader().finishingCurrentThread();
Lib.assertTrue(toBeDestroyed == null);
toBeDestroyed = currentThread;
currentThread.status = statusFinished;
KThread waitThread = null;
while ((waitThread = currentThread.waitForJoin.nextThread()) != null) {
waitThread.ready();
}
sleep();
}
测试代码
将如下代码添加入 KThread.selfTest() 方法
/* Task 1 test */
System.out.println(“Task 1 Test begin:”);
KThread kt = new KThread(new PingTest(1));
kt.fork();
kt.join();
// new KThread(new PingTest(1)).setName(“forked thread”).fork();
new PingTest(0).run();
Task 2 通过开关中断提供原子性/直接实现条件变量
要求
通过开关中断提供原子性，直接实现条件变量。我们提供了一个使用信号量实现的例子。你的工作是实现一个相同的功能而不直接利用信号量（你可以使用锁，即使锁间接地使用了信号量）。一旦你完成，你将拥有两个能提供完全相同功能的实现。你的第二个实现需要在nachos.threads.Condition2类内部实现。
分析
我们通过开关中断来保证完整性Machine.interupt().disable(),Machine.interupt().restore(boolean)，同时，我们通过Lock.acquire()和Lock.release()，来保证同时只有一个线程访问临界代码区。每个条件变量拥有一个锁变量，这一点跟Condition的构造是很类似的。
方案
sleep()方法中通过关中断来保证完整性，并且在sleep之前将锁释放掉，通过KThread.sleep()来休眠。
wake()通过ready()方法将一个线程加入就绪队列，来实现唤醒。
wakeAll()基于wake()来实现的，将等待队列中的每一个都wake()一次，并从队列中移除。
实现代码
实现Condition2.sleep(),Condition2.wake()和Condition2.wakeAll()，另外，本部分的测试将于Task4的测试一起进行。
public void sleep() {
Lib.assertTrue(conditionLock.isHeldByCurrentThread());
boolean iniStatus = Machine.interrupt().disable();
waitQueue.waitForAccess(KThread.currentThread());
conditionLock.release();
KThread.sleep();
conditionLock.acquire();
Machine.interrupt().restore(iniStatus);
}
public void wake() {
Lib.assertTrue(conditionLock.isHeldByCurrentThread());
boolean iniStatus = Machine.interrupt().disable();
KThread kt;
if ((kt = waitQueue.nextThread()) != null) {
kt.ready();
}
Machine.interrupt().restore(iniStatus);
}
public void wakeAll() {
Lib.assertTrue(conditionLock.isHeldByCurrentThread());
boolean iniStatus = Machine.interrupt().disable();
KThread kt;
while ((kt = waitQueue.nextThread()) != null) {
kt.ready();
}
Machine.interrupt().restore(iniStatus);
}
Task 3 实现Alarm.WaitUntil(long x)方法
要求
通过实现waitUntil(long x)方法来实现Alarm类。线程通过调用waitUntil来阻塞运行知道到达now+x时间再继续运行。不要创建新的线程来实现waikUntil()，需要修改waitUntil()和时钟中断处理器。waitUntil是不能限制在一个线程上的，任意数量的线程都能调用并且可以在任意时间阻塞。
注意：全局只有一个Alarm对象。
分析
首先，我们不能另开一个线程进行计时然后到时间唤醒这个线程，但是要求中给出提示，我们可以运用时钟中断来处理这个事情，给时钟中断添加处理器。
方案
由于Machine.Timer类大约每个500个时钟周期调用回调函数，我们为中断添加处理器（通过Timer.setInteruptHandler()来设置）。为了实现waitUntil()需要在Alarm类内部添加内部类Waiter，包含属性Thread,wakeTime，每当有线程调用waitUntil()方法便将该线程与其该唤醒的时间构成Waiter对象，并加入队列。每次时钟中断时，将队列中元素取出，查看是否到达唤醒时间，如果到达则可以将该线程取出，如果未到达，便重新放入等待队列。
关于测试时，调用waitUntil唤醒时间多次运行均为定值的原因分析
首先，我们知道只有在时钟中断的时候才会检查该线程是否到达唤醒时间。
然后，我们在每次调用时钟中断时，输出以下当前时间，发现输出的序列是一样的。
在之后实现阅读源码之后发现在Machine.Timer类中的scheduleInterrupt()为设置下次中断时间的方法。具体源码如下：
private void scheduleInterrupt() {
int delay = Stats.TimerTicks;
delay += Lib.random(delay / 10) - (delay / 20);
privilege.interrupt.schedule(delay, “timer”, timerInterrupt);
}
便发现，delay是通过Lib.random()得到下一次中断时间的。继续研究之后发现，random函数中调用的random对象在初始化时，将种子设为了0.
private static long randomSeed = 0;
Lib.seedRandom(randomSeed);
所以导致random每次生成的随机数序列都是一致的，也就导致了每次运行的中断时间都是一致的，进而导致唤醒时间是确定的。
实现代码
以下为Waiter内部类的实现，以及timerInterrupt(),waitUntil()的实现。
public void timerInterrupt() {
Waiter waiter;
for (int i = 0; i < waiterList.size(); i++) {
waiter = waiterList.remove();
if (waiter.wakeTime <= Machine.timer().getTime()) {
System.out.println(“Wake up thread ：” + waiter.thread.getName() + ” at ” + Machine.timer().getTime());
waiter.thread.ready();
} else {
waiterList.add(waiter);
}
}
KThread.currentThread().yield();
}
class Waiter {
Waiter(long wakeTime, KThread thread) {
this.wakeTime = wakeTime;
this.thread = thread;
}
private long wakeTime;
private KThread thread;
}
public void waitUntil(long x) {
boolean iniStatus = Machine.interrupt().disable();
long wakeTime = Machine.timer().getTime() + x;
Waiter waiter = new Waiter(wakeTime, KThread.currentThread());
waiterList.add(waiter);
System.out.println(KThread.currentThread().getName() + " thread sleeps at " + Machine.timer().getTime()
+ " and should wake at " + wakeTime + ".");
KThread.sleep();
Machine.interrupt().restore(iniStatus);
}
测试代码
将如下代码置于KThread.selfTest()之内。
/* Task 3 test */
System.out.println(“\nTask 3 Test begin:”);
ThreadedKernel.alarm.waitUntil(1000);
System.out.println(“Task 3 Test end.”);
Task 4 实现同步发送接受消息的Communicator
要求
通过条件变量（不要使用信号量），实现同步发送接受消息。实现Communicator.speak()，Communicator.listen().
speak()自动等待到另一个线程调用该Communicator对象的listen()方法，并且将信息通过listen()传递给另一个线程。
传递完成之后，两线程都可以返回。你的解决方案需要保证即使有多个说者和听者也能正常运行。每个communicator只能使用一个锁。如果你使用了多个锁，那你就会把事情搞复杂。
分析与方案
当一个线程调用speak()方法时，在以下情况下需要休眠：
队列中有多个线程等待speak
队列中没有线程等待listen
如下情况需唤醒一个等待listen线程：
队列中无speak线程，且存在listen线程
当一个线程调用listen()方法时，在在以下情况下需要休眠：
队列中有多个线程等待listen
队列中没有线程等待speak
如下情况需唤醒一个等待speak线程：
队列中无listen线程，且存在speak线程
实现代码
实现speak(),listen()方法，添加必要的属性
private Lock lock;
private Condition2 con;
private int speakNum;
private int listenNum;
private int word;
public void speak(int word) {
lock.acquire();
if (speakNum > 0 || listenNum == 0) {
speakNum++;
con.sleep();
speakNum--;
}
if (listenNum > 0) {
con.wake();
}
this.word = word;
System.out.println(KThread.currentThread().getName() + " speak " + word + ".");
lock.release();
}
public int listen() {
lock.acquire();
if (listenNum > 0 || speakNum == 0) {
listenNum++;
con.sleep();
listenNum--;
}
if (speakNum > 0) {
con.wake();
lock.release();
KThread.yield();
lock.acquire();
}
int word = this.word;
System.out.println(KThread.currentThread().getName() + " listen " + word + ".");
lock.release();
return word;
}
测试代码
如下代码添加入KThread.selfTest()，该测试对task2 & 4 一起进行测试。
/* Task 2 & 4 test */
System.out.println("\nTask 2 & 4 Test begin:");
Communicator com = new Communicator();
KThread kt1 = new KThread(new ComTest(0, com));
kt1.fork();
KThread.yield();
new ComTest(1, com).run();
System.out.println("Task 2 & 4 Test end.");
Task 5 实现优先级调度
要求
通过完成PriorityScheduler类来实现nachos中的优先级调度。优先级调度是实时系统中的关键构建模块。
注意： 要使用优先级调度，你需要在nachos.conf文件中明确出ThreadedKernel.scheduler的值从nachos.threads.RoundRobinScheduler改为nachos.threads.PriorityScheduler.
分析
在nachos中, 所有的调度程序都继承抽象Scheduler. 系统已经提供了一个简单的轮转调度器 RoundRobinScheduler, 它对所有线程不区分优先级而采用简单的FIFO队列进行调度. 我们实现的优先级调度类PriorityScheduler也需要继承自Scheduler.
传统优先级调度算法的问题是可能出现 “饥饿” 现象: 设想有一个低优先级的线程处于临界区中运行而高优先级的线程在临界区外等待. 由于前者优先级较低, 它可能不会被调度器选中从而高优先级的线程也不得不浪费时间等待.
为解决上述优先级反转问题, 需要实现一种 “让出” 优先级的机制 (Priority Donation) : 提高拥有锁的低优先级线程的优先级以使它迅速完成临界区, 不使其它较高优先级的线程等待太久. 提高后的优先级称为有效优先级。实际调度时就是以有效优先级为评判标准的。
方案
在ThreadState类中增加一个List对象存放的分别是该对象持有的资源的等待队列，方便计算有效优先级。
waitForAccess()将需要等待获得资源的线程加入一个等待队列等待调度。
getEffectivePriority()计算有效优先级时，遍历该对象持有的资源的等待队列中所用线程的有效优先级，找出最大的优先级即可。
实现代码
以下分别为waitForAccess(),getEffectivePriority(),pickNextThread()等方法及相关必要支持方法的实现代码。
public void waitForAccess(KThread thread) {
Lib.assertTrue(Machine.interrupt().disabled());
getThreadState(thread).waitForAccess(this);
}
public KThread nextThread() {
Lib.assertTrue(Machine.interrupt().disabled());
if (pickNextThread() == null)
return null;
KThread thread = pickNextThread().thread;
getThreadState(thread).acquire(this);
return thread;
}
protected ThreadState pickNextThread() {
if (waitQueue.isEmpty())
return null;
ThreadState toPick = getThreadState((KThread)waitQueue.getFirst());
for (KThread kt : waitQueue) {
ThreadState ts = getThreadState(kt);
if (ts.getEffectivePriority() > toPick.getEffectivePriority())
toPick = ts;
}
return toPick;
}
public int getEffectivePriority() {
if (effectivePriority != expiredEffectivePriority)
return effectivePriority;
effectivePriority = priority;
if (waiters == null)
return effectivePriority;
for (KThread kt : waiters.waitQueue) {
ThreadState ts = getThreadState(kt);
if (ts.priority > effectivePriority) {
effectivePriority = ts.priority;
}
}
return effectivePriority;
}
public void waitForAccess(PriorityQueue waitQueue) {
waitQueue.waitQueue.add(this.thread);
if (waitQueue.transferPriority && waitQueue.lockHolder != null)
waitQueue.lockHolder.effectivePriority = expiredEffectivePriority;
}
测试代码
将如下代码添加入KThread.selfTest()中进行测试。
/* Task 5 test */
System.out.println(“\nTask 5 Test begin:”);
boolean iniStatus = Machine.interrupt().disable();
KThread kt2 = new KThread(new PingTest(2));
KThread kt3 = new KThread(new PingTest(3));
KThread kt4 = new KThread(new PingTest(4));
PriorityScheduler ps = new PriorityScheduler();
ThreadQueue tq1 = ps.newThreadQueue(true);
ThreadQueue tq2 = ps.newThreadQueue(false);
tq1.waitForAccess(kt4);
tq2.waitForAccess(kt3);
tq2.waitForAccess(kt2);
tq1.acquire(kt2);
ps.setPriority(kt2, 2);
ps.setPriority(kt3, 3);
ps.setPriority(kt4, 4);
System.out.println("kt2's Priority is " + ps.getPriority(kt2));
System.out.println("kt2's effectivePriority is " + ps.getEffectivePriority(kt2));
System.out.println("kt3's Priority is " + ps.getPriority(kt3));
System.out.println("kt3's effectivePriority is " + ps.getEffectivePriority(kt3));
KThread temp = tq2.nextThread();
temp.fork();
temp.join();
Machine.interrupt().restore(iniStatus);
System.out.println("Task 5 Test end.");
要求
用以上实现的线程互斥/同步机制解决一个过河问题。
成人和小孩都试图从oahu出发到molokai。一只船只可以携带最多两个小孩或一个成人（但不能是一个小孩和一个成人）。船上可划回oahu岛，但这么做需要一个引航员。
安排一个能让所有人到molokai岛的解决方案。
分析
需要记录的信息：
O岛上的大人/小孩的人数
M岛上的大人/小孩的人数
船的位置（O岛/M岛）
船的状态（满/半满/全满）
初始状态：
大人和小孩都在O岛上
船在O岛
船为空
我们可以采取如下策略： 若O岛上存在两个或以上孩子则两个孩子一起开船过河，另一个孩子把船开回来，一直到只有O岛上只有一个孩子，然后让一个大人乘船过去，再让一个孩子乘船回来，不断进行如上判断，直到所有人都到达M岛。
方案
三个条件变量，三个互斥锁，具体见代码
实现代码
public static void begin(int adults, int children, BoatGrader b) {
// Store the externally generated autograder in a class
// variable to be accessible by children.
bg = b;
lock1 = new Lock();
childrenWaitOnOahu = new Condition(lock1);
lock2 = new Lock();
adultWaitOnOahu = new Condition(lock2);
lock3 = new Lock();
childrenReadyOnMolokai = new Condition(lock3);
for (int i = 0; i < adults; i++) {
new KThread(new Adult(childrenWaitOnOahu, adultWaitOnOahu, childrenReadyOnMolokai)).setName(“adult ” + i + ” “).fork();
}
for (int i = 0; i < children - 1; i++) {
new KThread(new Child(childrenWaitOnOahu, adultWaitOnOahu, childrenReadyOnMolokai)).setName("child " + i + " ")
.fork();
}
KThread t = new KThread(new Child(childrenWaitOnOahu, adultWaitOnOahu, childrenReadyOnMolokai));
t.setName("child " + children + " ");
t.fork();
KThread.currentThread().yield();
lock1.acquire();
childrenWaitOnOahu.wake();
lock1.release();
t.join();
}
static void AdultItinerary() {
bg.initializeAdult(); // Required for autograder interface. Must be the
// first thing called.
// DO NOT PUT ANYTHING ABOVE THIS LINE.
adultOnOahu++;
lock2.acquire();
adultWaitOnOahu.sleep();
bg.AdultRowToMolokai();
adultOnOahu--;
adultOnMolokai++;
lock2.release();
lock3.acquire();
childrenReadyOnMolokai.wake();
lock3.release();
/*
* This is where you should put your solutions. Make calls to the
* BoatGrader to show that it is synchronized. For example:
* bg.AdultRowToMolokai(); indicates that an adult has rowed the boat
* across to Molokai
*/
}
static void ChildItinerary() {
bg.initializeChild(); // Required for autograder interface. Must be the
// first thing called.
// DO NOT PUT ANYTHING ABOVE THIS LINE.
childrenOnOahu++;
lock1.acquire();
childrenWaitOnOahu.sleep();
lock1.release();
while (true) {
if (pilot != 1) {
if (childrenOnOahu > 1) {
lock1.acquire();
childrenWaitOnOahu.wake();
pilot = 1;
bg.ChildRowToMolokai();
childrenOnOahu--;
childrenOnMolokai++;
lock1.release();
lock3.acquire();
childrenReadyOnMolokai.sleep();
lock3.release();
} else {
lock2.acquire();
adultWaitOnOahu.wake();
lock2.release();
// bg.AdultRideToMolokai();
lock1.acquire();
childrenWaitOnOahu.sleep();
lock1.release();
continue;
}
} else {
if (adultOnOahu != 0) {
bg.ChildRideToMolokai();
childrenOnOahu–;
childrenOnMolokai++;
lock3.acquire();
childrenReadyOnMolokai.wake();
lock3.release();
lock3.acquire();
childrenReadyOnMolokai.sleep();
lock3.release();
} else {
lock3.acquire();
over = true;
bg.ChildRideToMolokai();
childrenOnOahu–;
childrenOnMolokai++;
childrenReadyOnMolokai.wakeAll();
lock3.release();
}
}
if (over == true) {
break;
} else {
pilot = 3;
bg.ChildRowToOahu();
childrenOnOahu++;
childrenOnMolokai--;
continue;
}
}
}
测试代码
将Boat.selfTest();加入ThreadedKernel.selfTest()，并将如下代码在Boat类中编辑好。
public static void selfTest() {
/* Task 6 test */
System.out.println(“\nTask 6 Test begin:”);
BoatGrader b = new BoatGrader();
// System.out.println(“\n Testing Boats with only 2 children“);
// begin(0, 2, b);
System.out.println("\n ***Testing Boats with 2 children, 1 adult***");
begin(1, 2, b);
// System.out.println(“\n Testing Boats with 3 children, 3 adults“);
// begin(3, 3, b);
System.out.println(“Task 6 Test end.”);
}
Phase 1 运行结果展示
nachos 5.0j initializing…randomSeed is 0
config interrupt timer processor console user-check grader
Task 1 Test begin:
* thread 1 looped 0 times
* thread 1 looped 1 times
* thread 1 looped 2 times
* thread 1 looped 3 times
* thread 1 looped 4 times
* thread 0 looped 0 times
* thread 0 looped 1 times
* thread 0 looped 2 times
* thread 0 looped 3 times
* thread 0 looped 4 times
Task 1 Test end.
Task 3 Test begin:
main thread sleeps at 140 and should wake at 1140.
Wake up thread ：main at 1530
Task 3 Test end.
Task 2 & 4 Test begin:
(unnamed thread) speak 345.
main listen 345.
(unnamed thread) speak 346.
main listen 346.
(unnamed thread) speak 347.
main listen 347.
(unnamed thread) speak 348.
main listen 348.
(unnamed thread) speak 349.
main listen 349.
Task 2 & 4 Test end.
Task 5 Test begin:
kt2’s Priority is 2
kt2’s effectivePriority is 4
kt3’s Priority is 3
kt3’s effectivePriority is 3
* thread 2 looped 0 times
* thread 2 looped 1 times
* thread 2 looped 2 times
* thread 2 looped 3 times
* thread 2 looped 4 times
Task 5 Test end.
Task 6 Test begin:
Testing Boats with 2 children, 1 adult
An adult as forked.
A child has forked.
A child has forked.
**Child rowing to Molokai.
**Child arrived on Molokai as a passenger.
**Child rowing to Oahu.
**Adult rowing to Molokai.
**Child rowing to Oahu.
**Child rowing to Molokai.
**Child arrived on Molokai as a passenger.
Task 6 Test end.
详细project2思路和解决
Task 1 实现系统调用（部分）
要求
实现六个系统调用creat,open, read, write, close, unlink,完善halt系统调用。
分析
要确保如下几点：
1. 稳定性, 不能因为一个进程的非法系统调用就使操作系统崩溃, 而应该返回错误代码。
2. halt() 调用只能由第一个进程 (root process) 执行。
3. 系统调用需要读写内存时, 通过readVirtualMemory和writeVirtualMemory进行。
4. 文件名以null结尾, 不超过256字符。
5. 为每个打开的I/O文件分配一个 “文件描述符”, 用整数表示。每个进程最多可以拥有16个。 其中0和1应分配给标准输入和标准输出 (即屏幕)， 这由SynchConsole类管理。不同进程可以用相同的文件描述符处理不同的文件。
6. Nachos已经提供了一个简单的文件系统FileSystem（Machine包中）,通过ThreadedKernel.fileSystem访问。
7. 系统不需要考虑文件访问的互斥等问题。
方案
create为创建文件的系统调用，可以每个线程建一个大小为16的数组存储其打开的文件。通过readVirtualMemoyString读取文件名，通过UserKernel.fileSystem.open打开文件 (第二个参数为true 表示创建新文件)。
open为打开文件的系统调用，通过UserKernal.fileSystem.open打开文件 (第二个参数为false)
read系统调用为读取文件的系统调用，通过OpenFile.read读取文件内容
write系统调用为写入文件的系统调用，通过OpenFile.write写入文件内容
close系统调用为关闭文件的系统调用，通过OpenFile.close关闭文件。
unlink一般地，在Unlink调用中只需读取文件名并执行fileSystem.remove方法删除文件即可。
halt系统调用,调用Machine.halt之前先判断系统中是否还有进程在执行，若没有则停机。
实现代码
以下为系统调用的实现
private int getUnusedFileDescriptor() {
for (int i = 0; i < this.openFiles.length; ++i) {
if (this.openFiles[i] == null) {
return i;
}
}
return -1;
}
private int handleCreate(final int pName) {
final String fileName = readVirtualMemoryString(pName, MAX_FILENAME_LENGTH);
for (int i = 0; i < this.openFiles.length; i++) {
if (this.openFiles[i] != null && this.openFiles[i].getName().equals(fileName)) {
return i;
}
}
final int fileDescriptor = this.getUnusedFileDescriptor();
if (fileDescriptor == -1)
return -1;
final OpenFile file = ThreadedKernel.fileSystem.open(fileName, true);
this.openFiles[fileDescriptor] = file;
return fileDescriptor;
}
private int handleOpen(final int pName) {
final int fileDescriptor = this.getUnusedFileDescriptor();
final String fileName = readVirtualMemoryString(pName, MAX_FILENAME_LENGTH);
final OpenFile file = ThreadedKernel.fileSystem.open(fileName, false);
this.openFiles[fileDescriptor] = file;
return fileDescriptor;
}
private int handleRead(final int fileDescriptor, final int pBuffer, final int count) {
final OpenFile file = this.openFiles[fileDescriptor];
final byte[] tmp = new byte[count];
final int numBytesRead = file.read(tmp, 0, count);
final int numBytesWritten = writeVirtualMemory(pBuffer, tmp, 0, numBytesRead);
return numBytesWritten;
}
private int handleWrite(final int fileDescriptor, final int pBuffer, final int count) {
final OpenFile file = this.openFiles[fileDescriptor];
final byte[] tmp = new byte[count];
final int numBytesToWrite = readVirtualMemory(pBuffer, tmp);
return file.write(tmp, 0, numBytesToWrite);
}
private int handleClose(final int fileDescriptor) {
OpenFile file = openFiles[fileDescriptor];
openFiles[fileDescriptor] = null;
file.close();
return 0;
}
private int handleUnlink(final int pName) {
String fileName = readVirtualMemoryString(pName, MAX_FILENAME_LENGTH);
boolean flag = false;
for (int i = 0; i < openFiles.length; i++) {
if ((openFiles[i] != null) && (openFiles[i].getName().equals(fileName))) {
openFiles[i] = null;
flag = true;
break;
}
}
if (flag)
return 0;
else
return -1;
}
并添加如下方法，通过如下方法来设置标准I/O
public void setStandardIO() {
openFiles[0] = UserKernel.console.openForReading();
openFiles[1] = UserKernel.console.openForWriting();
}
Task 2 实现多道程序运行的内存分配
要求
实现多道程序运行的支持。
分析
提出一种管理全局物理内存的方法，并且，不同进程之间不会产生重叠，并且进程不会申请堆内存。可以使用全局链表来存放可使用的物理内存页，并且在访问共享变量时注意不同进程间同步。保证进程在退出时，释放所有申请的内存。
修改UserProcess.readVirtualMemory和UserProcess.writeVirtualMemory,通过这两个方法来在内核和内存之间传递数据。可以借助Machine.processor().getMemory()，Machine.processor().getNumPhysPages()等方法来实现。
修改UserProcess.loadSections()，以便于进程能分配他需要的内存页。并且该方法应该建立起pageTable，如果不能获得足够内存应该返回错误信息，以便exec()返回结果。
方案
通过全局boolean数组来控制物理内存的分配，并记录总页数以及可用页数。
分配页表需要用Lock作互斥处理。
readVirtualMemory，writeVirtualMemory借助pageTable来实现
loadSections需要注意不能存入的情况，并利用pageTable来处理虚拟内存与物理内存地址的转换。
实现代码
以下为readVirtualMemory和writeVirtualMemory的实现代码
public int readVirtualMemory(int vaddr, byte[] data, int offset, int length) {
Lib.assertTrue(offset >= 0 && length >= 0 && offset + length <= data.length);
byte[] memory = Machine.processor().getMemory();
if (vaddr < 0 || vaddr >= numPages * pageSize)
return 0;
int byteNum = 0;
do {
int pageIndex = Processor.pageFromAddress(vaddr + byteNum);
if (pageIndex < 0 || pageIndex >= pageTable.length)
return 0;
int pageOffset = Processor.offsetFromAddress(vaddr + byteNum);
int bytesLeftInPage = pageSize - pageOffset;
int bytesToRead = Math.min(bytesLeftInPage, length - byteNum);
int physicalAddr = Processor.makeAddress(pageTable[pageIndex].ppn, pageOffset);
System.arraycopy(memory, physicalAddr, data, offset + byteNum, bytesToRead);
byteNum += bytesToRead;
} while (byteNum < length);
return byteNum;
}
public int writeVirtualMemory(int vaddr, byte[] data, int offset, int length) {
Lib.assertTrue(offset >= 0 && length >= 0 && offset + length <= data.length);
byte[] memory = Machine.processor().getMemory();
if (vaddr < 0 || vaddr >= numPages * pageSize)
return 0;
int byteNum = 0;
do {
int pageIndex = Processor.pageFromAddress(vaddr + byteNum);
if (pageIndex < 0 || pageIndex >= pageTable.length || pageTable[pageIndex].readOnly)
return 0;
int pageOffset = Processor.offsetFromAddress(vaddr + byteNum);
int bytesLeftInPage = pageSize - pageOffset;
int bytesToWrite = Math.min(bytesLeftInPage, length - byteNum);
byteNum += bytesToWrite;
} while (byteNum < length);
byteNum = 0;
do {
int pageIndex = Processor.pageFromAddress(vaddr + byteNum);
int pageOffset = Processor.offsetFromAddress(vaddr + byteNum);
int bytesLeftInPage = pageSize - pageOffset;
int bytesToWrite = Math.min(bytesLeftInPage, length - byteNum);
int physicalAddr = Processor.makeAddress(pageTable[pageIndex].ppn, pageOffset);
System.arraycopy(data, offset + byteNum, memory, physicalAddr, bytesToWrite);
byteNum += bytesToWrite;
} while (byteNum < length);
return byteNum;
}
以下为loadSections和unloadSections的实现代码
protected boolean loadSections() {
// Synchronization
UserKernel.getgFreePagesLock().acquire();
System.out.println(“numPages is ” + numPages + ” free pages is ” + UserKernel.getFreeNumPage());
if (numPages > UserKernel.getFreeNumPage()) {
coff.close();
Lib.debug(dbgProcess, "\tinsufficient physical memory");
UserKernel.getgFreePagesLock().release();
return false;
}
pageTable = UserKernel.getPageTable(numPages);
UserKernel.getgFreePagesLock().release();
int cnt = 0;
// load sections
for (int s = 0; s < coff.getNumSections(); s++) {
CoffSection section = coff.getSection(s);
Lib.debug(dbgProcess,
"\tinitializing " + section.getName() + " section (" + section.getLength() + " pages)");
for (int i = 0; i < section.getLength(); i++) {
// int vpn = section.getFirstVPN() + i;
// pageTable[cnt].vpn = vpn;
section.loadPage(i, pageTable[cnt++].ppn);
}
}
return true;
}
/**
* Release any resources allocated by <tt>loadSections()</tt>.
*/
protected void unloadSections() {
UserKernel.getgFreePagesLock().acquire();
UserKernel.releasePageTable(pageTable);
pageTable = null;
UserKernel.getgFreePagesLock().release();
}
以下为getPageTable与releasePageTable的实现代码
public static TranslationEntry[] getPageTable(int num) {
TranslationEntry[] pageTable = new TranslationEntry[num];
int cnt = 0;
for (int i = 0; i < globalFreePages.length && cnt < num; i++) {
if (globalFreePages[i]) {
TranslationEntry tmp = new TranslationEntry();
tmp.ppn = i;
tmp.vpn = cnt;
tmp.valid = true;
tmp.readOnly = false;
pageTable[cnt++] = tmp;
globalFreePages[i] = false;
}
}
freeNumPage -= pageTable.length;
return pageTable;
}
public static void releasePageTable(TranslationEntry[] pageTable) {
freeNumPage += pageTable.length;
for (int i = 0; i < pageTable.length; i++) {
globalFreePages[pageTable[i].ppn] = true;
}
}
Task 3 实现系统调用（剩余）
要求
实现系统调用exec,join和exit
分析
join直能由一个线程的父线程调用
join传递的参数为exec的返回结果，并且processID需保证全局唯一。
exit调用时需要清空内存，及打开的文件等，并且能够将status放回给join(父线程调用)
最后一个调用exit的线程需要负责关机，通过Kernel.kernel.terminate()来关闭nachos
方案
记录下全局HashMap记录下所有未结束线程，并记录每个线程的父线程，方便join时查询
exec需要注意不能载入内存的情况
exit做好善后处理，清空各种占有的资源
实现代码
以下为这三个系统调用的实现
private int handleExec(final int pName, final int argc, final int argv) {
String filename = readVirtualMemoryString(pName, MAX_FILENAME_LENGTH);
String[] args = new String[argc];
// System.out.println(“argc = ” + argc);
for (int i = 0; i < argc; i++) {
byte[] tmp = new byte[4];
readVirtualMemory(argv + i * 4, tmp);
int vaddr = Lib.bytesToInt(tmp, 0);
args[i] = readVirtualMemoryString(vaddr, MAX_FILENAME_LENGTH);
// System.out.println(args[i]);
}
// System.out.println(“processID = ” + processID);
// for (TranslationEntry item : pageTable) {
// System.out.println(item.ppn);
// }
UserProcess userProcess = UserProcess.newUserProcess();
userProcess.pProcessID = processID;
if (!userProcess.execute(filename, new String[] {})) {
ufProcessNum–;
ufProcesses.remove(userProcess.processID);
return -1;
}
// System.out.println(“processID = ” + userProcess.processID);
// for (TranslationEntry item : userProcess.pageTable) {
// System.out.println(item.ppn);
// }
return userProcess.processID;
}
class JoinInfo {
public UserProcess process;
public int status;
public JoinInfo(UserProcess process, int status) {
this.process = process;
this.status = status;
}
}
private int handleJoin(final int pid, final int saddr) {
UserProcess tmp = ufProcesses.get(pid);
if (tmp == null)
return 1; // already complete
if (tmp.pProcessID != processID)
return -1; // not his child
// System.out.println(“handleJoin ” + this.thread.getName());
JoinInfo joinInfo = new JoinInfo(this, 0);
tmp.waitForJoin.add(joinInfo);
boolean status = Machine.interrupt().disable();
UThread.sleep();
Machine.interrupt().restore(status);
byte[] stmp = Lib.bytesFromInt(joinInfo.status);
writeVirtualMemory(saddr, stmp);
int sta = joinInfo.status;
if (sta == 0)
return 1;
else
return 0;
}
private void handleExit(final int status) {
for (OpenFile file : openFiles) {
if (file != null) {
file.close();
file = null;
}
}
// System.out.println(“handleExit : sta is ” + status);
while (!waitForJoin.isEmpty()) {
JoinInfo joinInfo = waitForJoin.remove();
joinInfo.status = status;
boolean iniStatus = Machine.interrupt().disable();
joinInfo.process.thread.ready();
Machine.interrupt().restore(iniStatus);
}
UserKernel.getgFreePagesLock().acquire();
UserKernel.releasePageTable(pageTable);
UserKernel.getgFreePagesLock().release();
pageTable = null;
ufProcesses.remove(processID);
ufProcessNum--;
coff.close();
if (ufProcessNum > 0)
UThread.finish();
else
Kernel.kernel.terminate();
}
Task 4 实现彩票调度
要求
彩票调度 (Lottery Schedule) 和Task 1.5的优先级调度非常类似，只是下面两点作了改变：
“优先级” 的概念变成了 “彩票”，即表示该线程下次被运行的几率
在调度过程中，并不是选择彩票数最多的线程运行，而是随机抽取一张彩票，让彩票的主人运行。这样，彩票越多，下次得到的运行机会就越大。
分析
getEffectivePriority需要改变为对持有的资源的等待队列中的线程的优先级进行求和，而不是求最大值。
pickNextThread需要在所有线程中根据各自的概率大小从中随机选择一个线程运行。
实现代码
public ThreadQueue newThreadQueue(boolean transferPriority) {
return new LotteryQueue(transferPriority);
}
protected class LotteryQueue extends PriorityQueue {
protected ThreadState pickNextThread() {
if (waitQueue.isEmpty())
return null;
int totTicket = 0;
for (KThread kt : waitQueue) {
ThreadState ts = getThreadState(kt);
totTicket += ts.getEffectivePriority();
}
Random random = new Random();
int randomLottery = random.nextInt(totTicket);
int t = 0;
ThreadState toPick = null;
for (KThread kt : waitQueue) {
ThreadState ts = getThreadState(kt);
t += ts.getEffectivePriority();
if (t > randomLottery) {
toPick = ts;
break;
}
}
return toPick;
}
LotteryQueue(boolean transferPriority) {
super(transferPriority);
}
}
protected class LotteryState extends ThreadState {
public LotteryState(KThread thread) {
super(thread);
}
public int getEffectivePriority() {
if (effectivePriority != expiredEffectivePriority)
return effectivePriority;
effectivePriority = priority;
if (waiters == null)
return effectivePriority;
for (KThread kt : waiters.waitQueue) {
ThreadState ts = getThreadState(kt);
effectivePriority += ts.priority;
}
return effectivePriority;
}
}
Phase 2 运行结果展示
Testing the console device. Typed characters
will be echoed until q is typed.
q
q
numPages is 17 free pages is 64
nachos%
nachos% sh
sh
numPages is 17 free pages is 47
nachos% test1
test1
numPages is 16 free pages is 30
Calling ‘creat(filename)’… done!
Calling ‘fd = open(filename)’… done!
Return value fd = 3
Calling ‘Write(buffer, buffersize, fd)’ …done!
Calling ‘Read(buf, 40, fd)’ … Done
Begin to print the 40 Bytes content of a nachos file:
Hello! This is the test for Task2.1.
[2] Done (0)
nachos% exit
exit
[1] Done (0)
nachos% exit
exit
Machine halting!
Ticks: total 243886289, kernel 175374270, user 68512019
Disk I/O: reads 0, writes 0
Console I/O: reads 21, writes 362
Paging: page faults 0, TLB misses 0
Network I/O: received 0, sent 0