dijkstra算法的實(shí)踐與提高

1、What’s wrong?,public int listen() { lock.acquire(); if (!present) // 如果沒(méi)有留言 empty.sleep(); // 則睡眠 // 取得留言int word = buffer;present = false; // 喚醒正在等待發(fā)言的人 full.wake(); lock.relea

2、se(); return word;},public void speak(int word) { lock.acquire(); if (present) // 如果已有留言 full.sleep(); // 則睡眠 // 留言 buffer = word; present = true; // 喚醒正在等待接受留言的人 e

3、mpty.wake(); lock.release();},Wrong or Not?,public class KThread { ... /* Unique identifer for this thread. Used to deterministically compare threads. */ private int id = numCreated++; /*

4、Number of times the KThread constructor was called. */ private static int numCreated = 0; ...},How to Read code?,Case Study: KThread和TCB的構(gòu)造順序分析 一個(gè)KThread必然有一個(gè)TCB嗎？ 每個(gè)TCB必然在運(yùn)行一個(gè)KThread嗎？ 先有第一個(gè)TCB，還有

5、先有第一個(gè)KThread？,KThread和TCB的構(gòu)造順序分析——先有雞還是先有蛋？,首先被構(gòu)造出的是TCB，在Machine.main完成各種環(huán)境初始化后，最后一句寫(xiě)的是： new TCB().start(new Runnable() { public void run() { autoGrader.start(privilege);

6、 }});其實(shí)，autoGrader.start會(huì)構(gòu)造一個(gè)Kernel的實(shí)例(根據(jù)Nachos.coff的設(shè)置，目前就是ThreadKernel)，并且調(diào)用Kernel.initialize令其自我初始化轉(zhuǎn)入ThreadKernel.initialize，ThreadKernel首先裝入自己需要的Scheduler和FileSystem, 然后鬼使神差般地寫(xiě)了一句： new KThread(null);這就是最

7、早的KThread的實(shí)例。（我們稱它叫“new KThread No1”）,KThread和TCB的構(gòu)造順序分析——new KThread(null)？,注意這么構(gòu)造KThread是可疑的。因?yàn)樵谶^(guò)程里沒(méi)有保存對(duì)這個(gè)實(shí)例的引用，所以這個(gè)KThread永遠(yuǎn)沒(méi)有機(jī)會(huì)被fork()！ public void initialize(String[] args) { new KThrea

8、d(null); // “new KThread No1” } 檢查整個(gè)工程，我們沒(méi)有發(fā)現(xiàn)其他地方有這么寫(xiě)的，這么做的目的何在？我們需要看看KThread的構(gòu)造函數(shù)干了什么： if (currentThread !=

9、null) { // currentThread是靜態(tài)全局變量， // 其初值默認(rèn)為空 tcb = new TCB(); } else { // 可見(jiàn)第一次進(jìn)KThread()是執(zhí)行這里 …,KThread和TCB

10、的構(gòu)造順序分析——if (currentThread != null)?,… // 接上 else { readyQueue = ThreadedKernel.

11、 scheduler.newThreadQueue(false); readyQueue.acquire(this); currentThread = this; tcb = TCB.currentTCB(); // 這句話非常重要，我們?cè)谙旅鏁?huì)分析到 createIdleThread(); } 進(jìn)入了”else”這

12、個(gè)模塊之后，currentThread被立即賦值了，結(jié)合上下文的語(yǔ)意，我們可以推測(cè)這個(gè)”else”模塊不會(huì)被執(zhí)行第二次。于是我們斷言： 首次調(diào)用KThread的構(gòu)造函數(shù)，作用僅僅是初始化！,KThread和TCB的構(gòu)造順序分析——改造“new KThread No1”,根據(jù)上述分析，“new KThread No1” 和直覺(jué)上大相徑庭，似乎改寫(xiě)成KThread.initialize(); 會(huì)更自然一點(diǎn)，那為何需要這么寫(xiě)？

13、 public void initialize(String[] args) { new KThread(null); // 是不是 KThread.initialize(); 更自然？ } （提示：currentThread = this 這

14、句話揭示了問(wèn)題的答案） 我們的目標(biāo)是研究每個(gè)KThread是如何和一個(gè)TCB綁定并且運(yùn)行起來(lái)的，“new KThread No1”沒(méi)有給我們提供有用的東西。幸運(yùn)的是，它的一個(gè)子過(guò)程：createIdleThread引起了我們的注意：,KThread和TCB的構(gòu)造順序分析——IdleThread,private static void createIdleThread() { idleThread = new

15、 KThread(new Runnable() { public void run() { while (true) yield();

16、 }}); // “new KThread No2” idleThread.setName(“idle”).fork(); }我們又看到一句new KThread(….); 可以叫作“new KThread No2”。與”No1” 不同，這一次currentThread 不為null了，于是，KThread的構(gòu)造函數(shù)只會(huì)執(zhí)行一句話： if (currentThread

17、 != null) { tcb = new TCB(); },KThread和TCB的構(gòu)造順序分析——creatIdleThread,private static void createIdleThread() { idleThread = new KThread(new Runnable() {

18、 public void run() { while (true) yield(); }}); // “new KThread No2” idleThre

19、ad.setName(“idle”).fork(); }我們又看到一句new KThread(….); 可以叫作“new KThread No2”。與”No1” 不同，這一次currentThread 不為null了，于是，KThread的構(gòu)造函數(shù)只會(huì)執(zhí)行一句話： if (currentThread != null) { tcb = new TCB();

20、 },KThread和TCB的構(gòu)造順序分析——summary,,,interrupt().enable(),Main TCB Created By Machine():,kernel.initialize,new KThread(null),kernel.run();,kernel.terminate();,createIdleThread,currentThread = this,tcb = TCB.current

21、TCB,tcb=new TCB(),初始化內(nèi)核,開(kāi)啟中斷,啟動(dòng)內(nèi)核,中止內(nèi)核,初始化全局變量,建立空閑線程,內(nèi)核自檢,kernel.selfTest();,,TCB Created By Main TCB:,yield();,yield();,……,,,tcb=new TCB(),,Boat.selfTest();,……,,tcb=new TCB(),process.execute ( shellProgram …,Other Re

22、search Topic:,KThread與TCB的退出機(jī)制、中斷處理、TCB在java上的調(diào)度機(jī)制涉及到TCB.die()及privilege機(jī)制，interrupt也很復(fù)雜Coff的格式與讀入過(guò)程Coff的格式是目標(biāo)文件的一種常見(jiàn)格式，網(wǎng)上介紹很多Elevator及Rider的可視化實(shí)現(xiàn)Elevator和Rider是在threads包里的兩個(gè)類(lèi)，本來(lái)是第一階段的壓軸題，后來(lái)被Boat取代了。題意是要求模擬電梯和乘客的行為，

23、有趣的是Base code里有現(xiàn)成的GUI可供使用Mips處理器指令集的實(shí)現(xiàn)我們可以通過(guò)Processor看看如何用軟件實(shí)現(xiàn)一個(gè)Mips處理器文件系統(tǒng)目前的文件系統(tǒng)是非常簡(jiǎn)單的。參見(jiàn)FileSystem和OpenFile兩個(gè)接口，只不過(guò)是利用了java虛擬機(jī)已經(jīng)提供的實(shí)現(xiàn)，能進(jìn)一步擴(kuò)展,推薦讀物,《Code Reading》The Open Source PerspectiveWritten By Diomidis Spin

24、ellis Translated By 趙學(xué)良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 sy

25、stem. 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 problem

26、s.,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 "

27、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.

28、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 m

29、ust 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 th

30、row 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 dis

31、k 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

32、 second call is not guaranteed to return. This thread must not be the current thread.,Join: test case 1,,public void run() { KThread.currentThread().join(); Lib.assertNotReached( “This thread must not be

33、the current thread” );},Test the behavior when a thread joins to itself:,Join: test case 2,Test the behavior when the parent threads join to their children respectively:,,,,,,,,,,,,,,,,,,,,,Join: test case 3,Test the b

34、ehavior 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——o