Reference

nachos-java Task1.1 Join 包括后面几篇，有proj1的5个task讲解
Nachos Project2思路、代码
https://blog.csdn.net/qq_26919935/article/details/53149690
代码主要参考，但也需要修改 soohyunc/nachos

@[TOC]

1 建立线程系统

1.1 Kthread.join()

1.1.1 题目要求

实现KThread.join()。注意，另一个线程不必调用join()，但是如果调用了它，则必须只调用它一次。在同一个线程上第二次调用join()的结果是未定义的，即使第二个调用者与第一个调用者是不同的线程。无论是否联接，线程都必须正常执行。

1.1.2 解决方案

当A线程调用B线程的join方法时，B线程阻塞A线程并获得控制权，将A线程加入阻塞队列，在B线程完成后A继续运行。详细过程见注释。

1.1.3 代码实现

public void join() {
    Lib.debug(dbgThread, "Joining to thread: " + toString());
    Lib.assertTrue(this != currentThread);
    Lib.assertTrue(joinCount == 0);
    //关中断；获取当前线程的状态
    boolean intStatus = Machine.interrupt().disable();
    if(status!=statusFinished){
        joinCount += 1;
        //将当前运行中的线程加到阻塞队列中
        waitQueue.waitForAccess(currentThread);
        waitQueue.acquire(this);
        readyQueue.waitForAccess(this);
        //当前线程睡眠，放弃占用CPU
        sleep();
    }
    //保存当前的状态，等到中断结束回到当前线程时可以接下去执行
    Machine.interrupt().restore(intStatus);
}

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;
    do {
        waitThread = currentThread.waitQueue.nextThread();
        if (waitThread != null)
            waitThread.ready();
    } while (waitThread != null);
    sleep();
}

1.1.4 测试

public static void joinTest() {
    System.out.println("\n任务phase1.1");
    Lib.debug(dbgThread, "开始join方法测试");
    KThread bThread = new KThread(new JoinTest());
    bThread.setName("新线程").fork();
    System.out.println("A线程运行中");
    System.out.println("A线程暂停");
    bThread.join();
    System.out.println("A线程恢复运行");
}

任务phase1.1

A线程运行中

A线程暂停

B线程运行中

B线程结束运行

A线程恢复运行

Machine halting!

1.2 Condition

1.2.1 题目要求

直接实现条件变量，通过使用中断启用和禁用来提供原子性。系统提供了一个使用信号量的示例实现;要求在不直接使用信号量的情况下提供等效的实现(当然，可以使用锁，即使它们间接使用信号量)。条件变量的第二个实现必须驻留在类nachos.threads.Condition2中。

1.2.2 解决方案

使用Lock和thread的waitQueue实现。

sleep方法中将当前线程加入waitQueue并睡眠。

wake方法中取出waitQueue中的一个进程并启动。

wakeAll方法中以依次取出waitQueue中所有的进程并启动。

期间注意开关中断，防止数据结构变化不一致，详细过程见注释。

1.2.3 代码实现

public Condition2(Lock conditionLock) {
    this.conditionLock = conditionLock;
    waitQueue = new LinkedList<>();
}

public void sleep() {
    //   Lib.assertTrue(conditionLock.isHeldByCurrentThread());
    conditionLock.release();
    boolean preState = Machine.interrupt().disable();//关中断
    waitQueue.add(KThread.currentThread());//将当前线程加入到waitQueue中
    KThread.currentThread().sleep();//让当前线程睡眠
    Machine.interrupt().restore(preState);//恢复中断
    conditionLock.acquire();
}

public void wake() {
    Lib.assertTrue(conditionLock.isHeldByCurrentThread());
    boolean preState = Machine.interrupt().disable();//关中断
    if(!waitQueue.isEmpty()){//唤醒waitQueue中的一个线程
        KThread a = waitQueue.removeFirst();//取出waitForQueue中一个线程
        a.ready();//将取出的线程启动
    }
    Machine.interrupt().restore(preState);//恢复中断
}

1.2.4 测试

将所有Condition替换为Condition2后，join正常运行即可证明编写正确

1.3 Alarm

1.3.1 题目要求

实现waitUntil(long x)方法来完成Alarm类，线程调用waitUntil暂停自己的执行，直到时间至少提前到现在+ x。

1.3.2 解决方案

WaitForAlarmThread类维护线程和他所要等待的时间

Waituntil方法先计算出唤醒线程的时间，在将线程加入等待链表中并睡眠

Nachos系统每隔500个ticks调用一次timerInterrupt方法，遍历等待链表中的线程，判断是否到达等待时间，如果到达，则线程移出并唤醒。

（注：对于ticks的详细解读，见之后的拓展部分）

1.3.3 代码实现

class WaitForAlarmThread{
    long wakeTime;
    KThread thread;
    public WaitForAlarmThread(long wakeTime,KThread thread){
        this.wakeTime=wakeTime;
        this.thread=thread;
    }
}

public void waitUntil(long x)
{
    // for now, cheat just to get something working (busy waiting is bad)
    boolean preState = Machine.interrupt().disable();//关中断
    long wakeTime = Machine.timer().getTime()+x;//计算唤醒的时间
    WaitForAlarmThread waitForAlarmThread = new WaitForAlarmThread(wakeTime, KThread.currentThread());
    waitForAlarmThreadList.add(waitForAlarmThread);//将线程加入到等待链表中
    KThread.sleep();//让该线程睡眠
    Machine.interrupt().restore(preState);//恢复中断
}

public void timerInterrupt()
{
    boolean preState = Machine.interrupt().disable();//关中断
    for(WaitForAlarmThread t : waitForAlarmThreadList){
        if(t.wakeTime<=Machine.timer().getTime()){//如果达到唤醒时间，将其从链表中移除并唤醒该线程
            waitForAlarmThreadList.remove(t);
            t.thread.ready();
        }
    }
    KThread.currentThread().yield();
    Machine.interrupt().restore(preState);//恢复中断
}

1.3.4 测试

public static void AlarmTest() {
    KThread a = new KThread(new Runnable() {
        public void run() {
            System.out.println("线程a启动");
            for (int i = 0; i < 5; i++) {
                if (i == 2) {
                    System.out.println("线程a sleep，now：" + Machine.timer().getTime() + ", expect: after 1000 clicks");
                    Alarm.alarm().waitUntil(1000);
                    System.out.println("线程a wake，now：" + Machine.timer().getTime());
                }
                System.out.println(" thread 1 looped " + i + " times");
                //          KThread.currentThread().yield();
            }
        }
    });
    a.fork();
    System.out.println("\n测试Alarm：");
    for (int i = 0; i < 5; i++) {
        if (i == 2) {
            System.out.println("thread main sleep，now：" + Machine.timer().getTime() + ", expect: after 8000 clicks");
            Alarm.alarm().waitUntil(8000);
            System.out.println("thread wake, now：" + Machine.timer().getTime());
        }

        System.out.println(" thread 0 looped " + i + " times");
        KThread.currentThread().yield();
    }
}

测试Alarm：

thread 0 looped 0 times

线程a启动

thread 1 looped 0 times

thread 1 looped 1 times

线程a sleep，now：30, expect: after 1000 clicks

thread 0 looped 1 times

thread main sleep，now：50, expect: after 8000 clicks

线程a wake，now：1540

thread 1 looped 2 times

thread 1 looped 3 times

thread 1 looped 4 times

thread wake, now：8080

thread 0 looped 2 times

thread 0 looped 3 times

thread 0 looped 4 times

Machine halting!

1.4 Communicator

1.4.1 题目要求

使用条件变量(不要使用信号量!)实现一个单词消息的同步发送和接收(也称为ada风格的会合)。使用操作、void speak(int word)和int listen()实现通信器类。

1.4.2 解决方案

用继承自Condition2类的ComunicatorCondition类作为条件变量，并重写了sleep方法：判断是否存在对应的speaker或listener完成通讯，没有则睡眠

speaker调用speak方法，speaker数目+1，先检查有无listener，如果没有则睡眠，有listener或者被唤醒后，唤醒一个listener，完成通讯，listener数目-1

listener调用listen方法，listener数目+1，先检查有无speaker，如果没有则睡眠，有speaker或者被唤醒后，唤醒一个speaker，完成通讯，speaker数目-1

1.4.3 代码实现

public void sleep() {
    if (getNum() == 0) {
        String header = isSpeaker ? "speaker" : "listener";
        System.out.println(header + "Num=" + communicator.getListenerNum() + " , " + header + " wait");
        condition.sleep();
    }
}

public int getNum() {
    if(isSpeaker)
        return communicator.getSpeakerNum();
    else
        return communicator.getListenerNum();
}

public void speak(int word) {
    boolean preState = Machine.interrupt().disable();
    lock.acquire();
    speakerNum++;
    canSpeak.sleep();
    canListen.wake();
    this.word = word;
    listenerNum--;
    lock.release();
    Machine.interrupt().restore(preState);
}

public int listen() {
    boolean preState = Machine.interrupt().disable();
    lock.acquire();
    listenerNum++;
    canListen.sleep();
    canSpeak.wake();
    speakerNum--;
    lock.release();
    Machine.interrupt().restore(preState);
    return word;
}

1.4.4 测试

public static void SpeakTest() {
    System.out.println("\n测试Communicator类：");
    Communicator c = new Communicator();
    new KThread(new Speaker(c)).setName("Speaker").fork();
    for (int i = 0; i < 5; ++i) {
        System.out.println("listener listening " + i);
        int x = c.listen();
        System.out.println("listener listened, word = " + x);
        KThread.yield();
    }
}

测试Communicator类：

listener listening 0

listener listened, word = -1

speaker speaking word:0

listener listening 1

listener listened, word = -1

listener listening 2

listener listened, word = -1

listener listening 3

listener listened, word = -1

listener listening 4

listener listened, word = -1

Machine halting!

1.5 PriorityScheduler

1.5.1 题目要求

通过完成PriorityScheduler类在Nachos中实现优先级调度。

1.5.2 解决方案

ThreadState储存线程和他的优先级，用一个hashset来记录等待的线程

calculateEffectivePriority方法计算线程的有效优先级，遍历等待队列中的线程，找出队列中所有线程中最大的有效优先级，即为线程的有效优先级

waitForAccess 方法将线程加入等待队列，并重新计算有效优先级

acquire 设置队列的队列头

nextThread 获得下一个线程

1.5.3 代码实现

public KThread nextThread() {
    Lib.assertTrue(Machine.interrupt().disabled());
    // implement me
    ThreadState x = pickNextThread();//下一个选择的线程
    if(x == null)//如果为null,则返回null
        return null;
    acquire(x.thread);
    return x.thread;
}

public int calculateEffectivePriority() {
    int res = priority;
    for(PriorityQueue acquired : acquiredQueues) {
        //比较acquired中的所有等待队列中的所有线程的优先级
        ThreadState ts = acquired.wait.peek();

        if(ts != null && ts.effectivePriority > res) {
            res = ts.effectivePriority;
            break;
        }
    }
    res = priority >= res ? priority : res;
    return res;
}

public int getEffectivePriority() {
    if(waitQueue != null && !waitQueue.transferPriority)
        return priority;
    // implement me
    int res = calculateEffectivePriority();
    if(waitQueue!=null && res != effectivePriority) {
        (waitQueue).wait.remove(this);
        (waitQueue).wait.add(this);
    }
    effectivePriority = res;
    if(waitQueue!=null && waitQueue.lockholder != null)
        if(waitQueue.lockholder.effectivePriority < res)
            waitQueue.lockholder.effectivePriority = effectivePriority;
    return res;
}

public void waitForAccess(PriorityQueue waitQueue) {
    // implement me
    Lib.assertTrue(Machine.interrupt().disabled());
    if(this.waitQueue != waitQueue) {
        release(waitQueue);
        this.waitQueue = waitQueue;
        waitQueue.add(this);
        if(waitQueue.lockholder != null)
            waitQueue.lockholder.getEffectivePriority();
    }
}

public void acquire(PriorityQueue waitQueue) {
    // implement me
    Lib.assertTrue(Machine.interrupt().disabled());
    if(waitQueue.lockholder != null)
        waitQueue.lockholder.release(waitQueue);
    waitQueue.wait.remove(this);//如果这个队列中存在该线程，删除
    waitQueue.lockholder = this;
    acquiredQueues.add(waitQueue);
    this.waitQueue = null;
    getEffectivePriority();
    // Lib.assertTrue(waitQueue.isEmpty());
}

1.5.4 测试

public static void PriorityTest() {
    boolean status = Machine.interrupt().disable();//关中断，setPriority()函数中要求关中断
    System.out.println();
    final KThread a = new KThread(new KThread.PingTest(1)).setName("thread1");
    new PriorityScheduler().setPriority(a, 2);
    System.out.println("thread1的优先级为：" + new PriorityScheduler().getThreadState(a).priority);
    KThread b = new KThread(new KThread.PingTest(2)).setName("thread2");
    new PriorityScheduler().setPriority(b, 4);
    System.out.println("thread2的优先级为：" + new PriorityScheduler().getThreadState(b).priority);
    KThread c = new KThread(new Runnable() {
        public void run() {
            for (int i = 0; i < 5; i++) {
                if (i == 2)
                    a.join();
                System.out.println(" thread 3 looped " + i + " times");
                //          KThread.currentThread().yield();
            }
        }
    }).setName("thread3");
    new PriorityScheduler().setPriority(c, 6);
    System.out.println("thread3的优先级为：" + new PriorityScheduler().getThreadState(c).priority);
    a.fork();
    b.fork();
    c.fork();
    Machine.interrupt().restore(status);
}

线程3在循环到第2次时，join线程1，于是线程1先执行，线程1执行完之后，就绪的进程有线程2和线程3，因为线程3优先级比线程2高，故先执行线程3

thread1的优先级为：2

thread2的优先级为：4

thread3的优先级为：6

thread 3 looped 0 times

thread 3 looped 1 times

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 3 looped 2 times

thread 3 looped 3 times

thread 3 looped 4 times

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

Machine halting!

1.6 Boat

1.6.1 题目要求

一些夏威夷成人和儿童正试图从Oahu到Molokai。不幸的是，他们只有一艘船，可以最大限度地携带两个孩子或一个成年人（但不是一个孩子和一个成年人）。这条船可以划回瓦胡岛，但它需要一名驾驶员这样做。

安排一个解决方案，把所有人从Oahu胡转移到Molokai。可以假设至少有两个孩子。

1.6.2 解决方案

根据题意，Adult和Child并没有什么区别，需要注意的是，不允许一个船上出现1+1的情形，所以应该先考虑2+0，再考虑2+1，如果先考虑1+1，可能没有剩余的等待者。另外M岸必须至少有一个Adult和一个Child等待，以备返程接人。

流程比较复杂，我画了活动图见下方，child同理。

图中没有相似说明的是，要注意各岸各类人数目的加减，必须一致，并且需要在其他线程被唤醒并继续运行之前执行。另外，因为有waitOnO和canGo两道condition，如果wake了waitOnO，但没有释放当前线程的控制权，那么接下来即便wake了canGo，sleep在wait上的线程因为没有继续执行，并没有“上船”，这样有些数目的加减就有问题，所以要注意各个需要yield的地方。

1.6.3 代码实现

Adult、Child同理

static void AdultSailOnce() {
    adultWaitAtO.sleep();
    if (empty) {
        AdultPilot();
        if (childNumO > 0 || adultNumO > 0) {
            if (childNumO == 1 && adultNumO == 0) {
                childNumM--;
                childWaitAtM.wake();
                adultNumM++;
                adultWaitAtM.sleep();
            } else if (adultNumM > 0) {
                adultWaitAtM.wake();
                adultWaitAtM.sleep();
            }
        }
    } else {
        canGo.sleep();
        bg.AdultRideToMolokai();

        if(adultNumM == 0) {
            adultNumM++;
            adultWaitAtM.sleep();
        }

    }

    //回
    if ((childNumO > 0 || adultNumO > 0) && !(childNumO == 1 && adultNumO == 0)) {
        bg.AdultRowToOahu();
        adultNumO++;
        if (adultNumO > 0)
            adultWaitAtO.wake();
        else
            childWaitAtO.wake();
        empty = true;
        AdultSailOnce();
    }

}

static void AdultPilot() {
    empty = false;
    adultNumO--;
    if (adultNumO >= 1) {
        adultNumO--;
        wake(adultWaitAtO);
        if (childNumO >= 1) {
            childNumO--;
            wake(childWaitAtO);
        } else if (adultNumO >= 1) {
            adultNumO--;
            wake(adultWaitAtO);
        }
    } else if (childNumO >= 2) {
        wake(childWaitAtO);
        wake(childWaitAtO);
        childNumO -= 2;
    }
    canGo.wakeAll();
    bg.AdultRowToMolokai();

    lock.release();
    KThread.yield();
    lock.acquire();
}

static void wake(Condition condition) {
    condition.wake();
    lock.release();
    KThread.yield();
    lock.acquire();
}

1.6.4 测试

public static void selfTest() {
    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);
}

Testing Boats with only 2 children

A child has forked.

A child has forked.

Child rowing to Molokai.

Child arrived on Molokai as a passenger.

Testing Boats with 2 children, 1 adult

An adult as forked.

A child has forked.

A child has forked.

Adult rowing to Molokai.

Child arrived on Molokai as a passenger.

Child arrived on Molokai as a passenger.

Testing Boats with 3 children, 3 adults

An adult as forked.

An adult as forked.

An adult as forked.

A child has forked.

A child has forked.

A child has forked.

Adult rowing to Molokai.

Adult arrived on Molokai as a passenger.

Child arrived on Molokai as a passenger.

Adult rowing to Oahu.

Adult rowing to Molokai.

Adult arrived on Molokai as a passenger.

Child arrived on Molokai as a passenger.

Child rowing to Oahu.

Child rowing to Molokai.

Child arrived on Molokai as a passenger.

Machine halting!

1.7 拓展：Timer

Alarm中有提到Ticks，那么Nachos是怎么模拟时钟周期的？

Stats类中以整数保存了TimerTicks=500（中断检查间隔）、UserTick=1（用户级别单位tick）、KernelTick=10（内核级别单位tick）、totalTicks、kernelTicks、userTicks（后三个记录累计ticks）；

在Timer类的scheduleInterrupt方法中，

private void scheduleInterrupt() {
    int delay = Stats.TimerTicks;
    delay += Lib.random(delay / 10) - (delay / 20);
    privilege.interrupt.schedule(delay, "timer", timerInterrupt);
}

根据中断间隔，（正态分布地）模拟生成了一个下一个interrupt检查的时间，

private void timerInterrupt() {
    scheduleInterrupt();
    scheduleAutoGraderInterrupt();
    lastTimerInterrupt = getTime();
    if (handler != null)
        handler.run();
}

当到了设置好的时间点（total=last+delay）时，调用timerInterrupt方法，其中run之前设置好的handler（在Alarm类中我们设置过）。

那么ticks又是怎么累加的呢？

public void run() {
    Lib.debug(dbgProcessor, "starting program in current thread");
    registers[regNextPC] = registers[regPC] + 4;
    Machine.autoGrader().runProcessor(privilege);
    Instruction inst = new Instruction();
    while (true) {
        try {
            inst.run();
        } catch (MipsException e) {
            e.handle();
        }
        privilege.interrupt.tick(false);
    }
}

在Processor类的run方法死循环中不断调用tick方法，追溯下去

private void tick(boolean inKernelMode) {
    Stats stats = privilege.stats;
    if (inKernelMode) {
        stats.kernelTicks += Stats.KernelTick;
        stats.totalTicks += Stats.KernelTick;
    } else {
        stats.userTicks += Stats.UserTick;
        stats.totalTicks += Stats.UserTick;
    }

    if (Lib.test(dbgInt))
        System.out.println("== Tick " + stats.totalTicks + " ==");

    enabled = false;
    checkIfDue();
    enabled = true;
}

我们就可以看到累加的地方了。