What’s wrong? public int listen() { lock.acquire(); if (!present) // 如果没有留言 empty.sleep(); // 则睡眠 // 取得留言 int word = buffer; present = false; // 唤醒正在等待发言的人 full.wake(); lock.release(); return word; } public void speak(int word) { lock.acquire(); if (present) // 如果已有留言 full.sleep(); // 则睡眠 // 留言 buffer = word; present = true; // 唤醒正在等待接受留言的人 empty.wake(); lock.release(); }

Wrong or Not? public class KThread { ... /* Unique identifer for this thread. Used to deterministically compare threads. */ private int id = numCreated++; /* Number of times the KThread constructor was called. */ private static int numCreated = 0; }

How to Read code? Case Study: KThread和TCB的构造顺序分析 一个KThread必然有一个TCB吗？

KThread和TCB的构造顺序分析 ——先有鸡还是先有蛋？ 首先被构造出的是TCB，在Machine.main完成各种环境初始化后，最后一句写的是： new TCB().start(new Runnable() { public void run() { autoGrader.start(privilege); }}); 其实，autoGrader.start会构造一个Kernel的实例(根据Nachos.coff的设置，目前就是ThreadKernel)，并且调用Kernel.initialize令其自我初始化 转入ThreadKernel.initialize，ThreadKernel首先装入自己需要的Scheduler和FileSystem, 然后鬼使神差般地写了一句： new KThread(null); 这就是最早的KThread的实例。（我们称它叫“new KThread No1”）

KThread和TCB的构造顺序分析 ——new KThread(null)？ 注意这么构造KThread是可疑的。因为在过程里没有保存对这个实例的引用，所以这个KThread永远没有机会被fork()！ public void initialize(String[] args) { new KThread(null); // “new KThread No1” } 检查整个工程，我们没有发现其他地方有这么写的，这么做的目的何在？我们需要看看KThread的构造函数干了什么： if (currentThread != null) { // currentThread是静态全局变量， // 其初值默认为空 tcb = new TCB(); } else { // 可见第一次进KThread()是执行这里 …

KThread和TCB的构造顺序分析 ——if (currentThread != null)? … // 接上 else { readyQueue = ThreadedKernel. scheduler.newThreadQueue(false); readyQueue.acquire(this); currentThread = this; tcb = TCB.currentTCB(); // 这句话非常重要，我们在下面会分析到 createIdleThread(); } 进入了”else”这个模块之后，currentThread被立即赋值了，结合上下文的语意，我们可以推测这个”else”模块不会被执行第二次。于是我们断言： 首次调用KThread的构造函数，作用仅仅是初始化！

KThread和TCB的构造顺序分析 ——改造“new KThread No1” KThread.initialize(); 会更自然一点，那为何需要这么写？ public void initialize(String[] args) { new KThread(null); // 是不是 KThread.initialize(); 更自然？ } （提示：currentThread = this 这句话揭示了问题的答案） 我们的目标是研究每个KThread是如何和一个TCB绑定并且运行起来的，“new KThread No1”没有给我们提供有用的东西。幸运的是，它的一个子过程：createIdleThread引起了我们的注意：

KThread和TCB的构造顺序分析 ——IdleThread private static void createIdleThread() { idleThread = new KThread(new Runnable() { public void run() { while (true) yield(); }}); // “new KThread No2” idleThread.setName(“idle”).fork(); } 我们又看到一句new KThread(….); 可以叫作“new KThread No2”。与”No1” 不同，这一次currentThread 不为null了，于是，KThread的构造函数只会执行一句话： if (currentThread != null) { tcb = new TCB();

KThread和TCB的构造顺序分析 ——creatIdleThread private static void createIdleThread() { idleThread = new KThread(new Runnable() { public void run() { while (true) yield(); }}); // “new KThread No2” idleThread.setName(“idle”).fork(); } 我们又看到一句new KThread(….); 可以叫作“new KThread No2”。与”No1” 不同，这一次currentThread 不为null了，于是，KThread的构造函数只会执行一句话： if (currentThread != null) { tcb = new TCB();

KThread和TCB的构造顺序分析 ——summary Main TCB Created By Machine(): TCB Created By Main TCB: 初始化内核 kernel.initialize yield(); 初始化全局变量 new KThread(null) yield(); tcb=new TCB() currentThread = this …… tcb = TCB.currentTCB 建立空闲线程 createIdleThread Boat.selfTest(); 开启中断 interrupt().enable() …… 内核自检 tcb=new TCB() kernel.selfTest(); tcb=new TCB() 启动内核 kernel.run(); process.execute ( shellProgram … 中止内核 kernel.terminate();

Other Research Topic: KThread与TCB的退出机制、中断处理、TCB在java上的调度机制 涉及到TCB.die()及privilege机制，interrupt也很复杂 Coff的格式与读入过程 Coff的格式是目标文件的一种常见格式，网上介绍很多 Elevator及Rider的可视化实现 Elevator和Rider是在threads包里的两个类，本来是第一阶段的压轴题，后来被Boat取代了。题意是要求模拟电梯和乘客的行为，有趣的是Base code里有现成的GUI可供使用 Mips处理器指令集的实现 我们可以通过Processor看看如何用软件实现一个Mips处理器 文件系统 目前的文件系统是非常简单的。参见FileSystem和OpenFile两个接口，只不过是利用了java虚拟机已经提供的实现，能进一步扩展 问题： Semaphore、Condition等等的ThreadQueue private ThreadQueue waitQueue = ThreadedKernel.scheduler .newThreadQueue(false); Why false?

推荐读物 《Code Reading》 The Open Source Perspective Written By Diomidis Spinellis Translated By 赵学良 14th Annual Software Development Productivity award

Nachos Phase 3

feature The third phase of Nachos is to investigate the interaction between the TLB, the virtual memory system, and the file system. You will continue to use the stub file system. I hope you has been already familiar with it … we provide you with a new package, nachos.vm, with two new classes, VMKernel and VMProcess. open-ended design problems.

TLB For this phase, the processor knows nothing about page tables. Instead, the processor only deals with a software-managed cache of page table entries, called the TLB. If the translation is not in the TLB (a "TLB miss"), the processor causes a trap to the OS kernel. Then it is the kernel's responsibility to load the mapping into the TLB

Paging when a TLB miss fault occurs, the kernel should check its own page table. If the page is not in memory, it should read the page in from disk, set the page table entry to point to the new page, install the page table entry, and resume the execution of the user program. Of course, the kernel must first find space in memory for the incoming page, potentially writing some other page back to disk, if it has been modified.

Swapping On a page fault, the kernel must decide which page to replace; ideally, it will throw out a page that will not be referenced for a long time, keeping in memory those pages may be referenced soon. Another consideration is that if the replaced page has been modified, the page must first be saved to disk before the needed page can be brought in

Any question?

Join Waits for this thread (not the current thread) to finish. If this thread is already finished, return immediately. This method must only be called once; the second call is not guaranteed to return. This thread must not be the current thread.

Join: test case 1 Test the behavior when a thread joins to itself: public void run() { KThread.currentThread().join(); Lib.assertNotReached( “This thread must not be the current thread” ); }

Join: test case 2 Test the behavior when the parent threads join to their children respectively:

Join: test case 3 Test the behavior when the threads joined in a circle.

Join: discussion How to avoid check the dependency relation when we handle the join() call? perhaps we may refer to the UNIX system call’s restriction——only parent is allowed to join its child thread?