操作系統(tǒng)課程設(shè)計(jì)-代碼分析及設(shè)計(jì)實(shí)現(xiàn)及測(cè)試報(bào)告

1、<p>　　操作系統(tǒng)課程設(shè)計(jì)報(bào)告</p><p><b>　　目錄</b></p><p><b>　　目錄2</b></p><p><b>　　一、 前期工作3</b></p><p><b>　　1.1平臺(tái)搭建3</b></p&

2、gt;<p><b>　　二、 代碼分工3</b></p><p><b>　　三、設(shè)計(jì)及實(shí)現(xiàn)4</b></p><p>　　3.1 Task1.1 KThread.join()4</p><p>　　3.1.1 要求分析4</p><p>　　3.1.2 設(shè)計(jì)方案4<

3、/p><p>　　3.1.3 實(shí)現(xiàn)代碼4</p><p>　　3.1.4 測(cè)試代碼及結(jié)果5</p><p>　　3.2 Task1.2 condition2類(lèi)7</p><p>　　3.2.1 要求分析7</p><p>　　3.2.2 設(shè)計(jì)方案8</p><p>　　3.2.3 實(shí)現(xiàn)代碼

4、8</p><p>　　3.2.4 測(cè)試代碼及結(jié)果8</p><p>　　3.3 Task1.3 alram類(lèi)11</p><p>　　3.3.1 要求分析11</p><p>　　3.3.2 設(shè)計(jì)方案11</p><p>　　3.3.3 實(shí)現(xiàn)代碼12</p><p>　　3.3.4

5、 測(cè)試代碼及結(jié)果12</p><p>　　3.4 Task1.4 communicator類(lèi)14</p><p>　　3.4.1要求分析14</p><p>　　3.4.2 設(shè)計(jì)方案14</p><p>　　3.4.3 實(shí)現(xiàn)代碼14</p><p>　　3.4.4 測(cè)試代碼及結(jié)果15</p>

6、<p>　　3.5 Task1.5 priority scheduler類(lèi)17</p><p>　　3.5.1 要求分析17</p><p>　　3.5.2 設(shè)計(jì)方案17</p><p>　　3.5.3 實(shí)現(xiàn)代碼18</p><p>　　3.5.4 測(cè)試代碼及結(jié)果18</p><p>　　3.6 T

7、ask1.6 boat類(lèi)23</p><p>　　3.6.1 要求分析23</p><p>　　3.6.2 設(shè)計(jì)方案23</p><p>　　3.6.3 實(shí)現(xiàn)代碼23</p><p>　　3.6.4 測(cè)試代碼及結(jié)果30</p><p>　　3.7 Task2.1 系統(tǒng)調(diào)用creat, open, read,

8、write, close, unlink30</p><p>　　3.7.1 要求分析30</p><p>　　3.7.2 設(shè)計(jì)方案31</p><p>　　3.7.3 實(shí)現(xiàn)代碼32</p><p>　　3.7.4 測(cè)試代碼及結(jié)果34</p><p>　　3.8 Task2.2 多進(jìn)程內(nèi)存分配及訪問(wèn)35&l

9、t;/p><p>　　3.8.1 要求分析35</p><p>　　3.8.2 設(shè)計(jì)方案35</p><p>　　3.8.3 實(shí)現(xiàn)代碼36</p><p>　　3.8.4 測(cè)試代碼及結(jié)果39</p><p>　　3.9 Task2.3 系統(tǒng)調(diào)用exec, join, exit41</p><p

10、>　　3.9.1 要求分析41</p><p>　　3.9.2 設(shè)計(jì)方案41</p><p>　　3.9.3 實(shí)現(xiàn)代碼42</p><p>　　3.9.4 測(cè)試代碼及結(jié)果43</p><p>　　3.10 Task2.4 Lottery Schedule類(lèi)44</p><p>　　3.10.1 要求分析

11、44</p><p>　　3.10.2 設(shè)計(jì)方案45</p><p>　　3.10.3 實(shí)現(xiàn)代碼45</p><p>　　3.10.4 測(cè)試代碼及結(jié)果45</p><p><b>　　總結(jié)48</b></p><p><b>　　前期工作</b></p>

12、<p><b>　　1.1平臺(tái)搭建</b></p><p>　　Nachos For Java</p><p>　　phrase1部分：IDE環(huán)境可采用Eclipse。</p><p>　　Phase 2及以后階段：需要把C程序編譯成MIPS二進(jìn)制文件COFF，需要MIPS的C編譯器 mips-x86.linux-xgcc(ub

13、untu12.04平臺(tái)下)。</p><p><b>　　代碼分工</b></p><p><b>　　三、設(shè)計(jì)及實(shí)現(xiàn)</b></p><p>　　3.1 Task1.1 KThread.join()</p><p>　　3.1.1 要求分析</p><p>　　Join()

14、方法的含義：當(dāng)前線程a在運(yùn)行，執(zhí)行b.join(),則a阻塞，直到線程b結(jié)束，a繼續(xù)執(zhí)行。</p><p>　　Join函數(shù)的作用即為等待某線程運(yùn)行完畢。當(dāng)前線程 (唯一一個(gè)正在運(yùn)行的線程) A調(diào)用另一個(gè)線程 (處于就緒狀態(tài)) B的join函數(shù)時(shí) (A 和 B 在Nachos中均為KThread類(lèi)型對(duì)象)，A被掛起，直到B運(yùn)行結(jié)束后， join函數(shù)返回，A才能繼續(xù)運(yùn)行。注意在一個(gè)KThread對(duì)象上只能調(diào)用一次j

15、oin，且當(dāng)前線程不能對(duì)自身調(diào)用join。</p><p>　　3.1.2 設(shè)計(jì)方案</p><p>　　為每個(gè)線程創(chuàng)建一個(gè)線程隊(duì)列joinqueue，joinqueue由對(duì)本線程調(diào)用join方法的其他線程對(duì)象構(gòu)成，可“捐贈(zèng)”優(yōu)先級(jí) ，以及布爾形變量joined，判斷本線程是否被其他線程調(diào)用過(guò)join方法，以及一個(gè)判斷線程狀態(tài)方法IsAlive()。</p><p>

16、;　　假設(shè)當(dāng)前線程A調(diào)用就緒線程B的join函數(shù). 在join函數(shù)中線程A被添加到線程B的線程隊(duì)列joinqueue中，將線程A“休眠”, 線程B得到執(zhí)行，在線程B結(jié)束時(shí)(此時(shí)線程B成為當(dāng)前線程, 發(fā)生在KThead.finish函數(shù)中) 選擇B的joinqueue的nextThread()執(zhí)行, A喚醒并繼續(xù). </p><p>　　3.1.3 實(shí)現(xiàn)代碼</p><p>　　在KThre

17、ad.java 中: </p><p>　　private ThreadQueue joinQueue = null; </p><p>　　private boolean Joined = false;</p><p>　　public boolean IsAlive(){</p><p>　　if(this.status==sta

18、tusNew||status==statusReady||</p><p>　　status==statusRunning||status==statusBlocked)</p><p>　　return true;</p><p>　　else return false;</p><p><b>　　}</b><

19、/p><p>　　public void join() {</p><p><b>　　//</b></p><p>　　if (!this.IsAlive()) return;</p><p>　　while (IsAlive()) {</p><p><b>　　//</b>

20、;</p><p>　　this.joinQueue.acquire(this);</p><p><b>　　//</b></p><p><b>　　}</b></p><p>　　this.joinQueue.waitForAccess(KThread.currentThread());<

21、;/p><p>　　KThread.sleep();</p><p><b>　　//</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　public static void finish() {&l

22、t;/p><p><b>　　///</b></p><p>　　if (currentThread.Joined) {</p><p>　　currentThread.joinQueue.nextThread().ready();</p><p><b>　　}</b></p><

23、;p><b>　　///</b></p><p><b>　　}</b></p><p>　　3.1.4 測(cè)試代碼及結(jié)果</p><p>　　創(chuàng)建AThread和Bthread兩個(gè)線程，AThread循環(huán)打印“AThread循環(huán)第..次”語(yǔ)句，Bthread開(kāi)始打印“B_thread 就緒”語(yǔ)句，中間執(zhí)行AThrea

24、d。Join（）方法，最后打印“B_thread執(zhí)行結(jié)束”語(yǔ)句。</p><p><b>　　測(cè)試代碼:</b></p><p>　　package nachos.threads;</p><p>　　import nachos.machine.*;</p><p>　　public class KThreadTest

25、{</p><p>　　public KThreadTest() {</p><p><b>　　}</b></p><p>　　public static void simpleJoinTest() {</p><p>　　KThread A_thread = new KThread(new KThreadTest.A

26、_thread(5));</p><p>　　KThread B_thread = new KThread(new KThreadTest.B_thread(A_thread));</p><p>　　B_thread.fork();</p><p>　　B_thread.join();</p><p><b>　　}</b&

27、gt;</p><p>　　public static class B_thread implements Runnable {</p><p>　　B_thread(KThread joinee) {</p><p>　　this.joinee = joinee;</p><p><b>　　}</b></p&g

28、t;<p>　　public void run() {</p><p>　　System.out.println("B_thread 就緒");</p><p>　　System.out.println("Forking and joining A_thread...");</p><p>　　this.join

29、ee.fork();</p><p>　　this.joinee.join();</p><p>　　System.out.println("B_thread 執(zhí)行結(jié)束");</p><p><b>　　}</b></p><p>　　private KThread joinee;</p>

30、<p><b>　　}</b></p><p>　　public static class A_thread implements Runnable {</p><p>　　A_thread(int num) {</p><p>　　this.num = num;</p><p><b>　　}&

31、lt;/b></p><p>　　public void run() {</p><p>　　System.out.println("A_thread 就緒");</p><p>　　System.out.println("A_thread開(kāi)始執(zhí)行");</p><p>　　// This sho

32、uld just kill some cycles</p><p>　　for (int i = 0; i < this.num; ++i) {</p><p>　　System.out.println("A_thread 循環(huán) 第" + i + " 次");</p><p>　　KThread.currentThrea

33、d().yield();</p><p><b>　　}</b></p><p>　　System.out.println("A_thread 執(zhí)行結(jié)束");</p><p><b>　　}</b></p><p>　　private int num;</p>&l

34、t;p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　測(cè)試結(jié)果：</b></p><p>　　3.2 Task1.2 condition2類(lèi)</p><p>　　3.2.1 要求分析</p><p>　

35、　threads.Lock類(lèi)提供了鎖以保證互斥. 在臨界代碼區(qū)的兩端執(zhí)行Lock.acquire() 和Lock.release() 即可保證同時(shí)只有一個(gè)線程訪問(wèn)臨界代碼區(qū). 條件變量建立在鎖之上, 由threads.Condition實(shí)現(xiàn), 它是用來(lái)保證同步的工具. 每一個(gè)條件變量擁有一個(gè)鎖變量 (該鎖變量亦可被執(zhí)行acquire和release操作, 多個(gè)條件變量可共享同一個(gè)鎖變量). 當(dāng)處于臨界區(qū)內(nèi)的擁有某鎖Lock的當(dāng)前線程對(duì)與

36、鎖Lock聯(lián)系的條件變量執(zhí)行sleep操作時(shí), 該線程失去鎖L并被掛起. 下一個(gè)等待鎖L的線程獲得鎖L (這個(gè)過(guò)程由調(diào)度程序完成) 并進(jìn)入臨界區(qū). 當(dāng)擁有鎖L的臨界區(qū)內(nèi)的當(dāng)前線程對(duì)與鎖L聯(lián)系的條件變量執(zhí)行wake操作時(shí) (通常調(diào)用wake之后緊接著就是Lock.release), 等待在該條件變量上的至多一個(gè)被掛起的線程 (由調(diào)用sleep引起) 被重新喚醒并設(shè)置為就緒狀態(tài). 若執(zhí)行wakeall操作, 則等待在該條件變量上的所有被掛起

37、的線程都被喚醒. threads.condition已經(jīng)實(shí)現(xiàn)了一個(gè)條件變量 (采用信號(hào)量實(shí)現(xiàn)), 題目要求用屏蔽/禁止中斷</p><p>　　3.2.2 設(shè)計(jì)方案</p><p>　　為每個(gè)條件變量添加一個(gè)鎖conditionLock和一個(gè)Kthread對(duì)象組成的等待隊(duì)列waitqueue，condition.sleep 將調(diào)用sleep（）的線程加入到等待隊(duì)列，釋放鎖，并阻塞，以便其他

38、線程喚醒它，一旦’喚醒’立即要求鎖，并在sleep函數(shù)開(kāi)始/結(jié)尾處屏蔽/允許中斷以保證原子性;condition.wake中從等待隊(duì)列中取出線程進(jìn)行ready()實(shí)現(xiàn)喚醒, </p><p>　　(同樣要在wake函數(shù)開(kāi)始/結(jié)尾處屏蔽/允許中斷), wakeall函數(shù)的實(shí)現(xiàn)依賴(lài)于wake. 只需不斷地wake 直到隊(duì)列為空為止. </p><p>　　3.2.3 實(shí)現(xiàn)代碼</p&g

39、t;<p>　　見(jiàn)threads/condition2.java </p><p>　　private Lock conditionLock;</p><p>　　private LinkedList<KThread> waitQueue;</p><p>　　public void sleep() {</p><p&g

40、t;<b>　　//</b></p><p>　　waitQueue.add(KThread.currentThread());</p><p>　　conditionLock.release();</p><p>　　KThread.sleep();</p><p>　　conditionLock.acquire();

41、</p><p><b>　　//</b></p><p><b>　　}</b></p><p>　　public void wake() {</p><p><b>　　//</b></p><p>　　waitQueue.remove().read

42、y();</p><p><b>　　//</b></p><p><b>　　}</b></p><p>　　3.2.4 測(cè)試代碼及結(jié)果</p><p>　　創(chuàng)建共有條件變量c2test，一個(gè)臨界資源count和三個(gè)線程，thread1，thread2，thread3，初始化三個(gè)線程后thread

43、1，thread2調(diào)用c2test.sleep()后開(kāi)始“睡眠”，thread3調(diào)用c2test.wakeAll()喚醒所有線程，thread1，thead2開(kāi)始交替訪問(wèn)臨界資源count并更改其“余額”數(shù)值。</p><p><b>　　測(cè)試代碼:</b></p><p>　　package nachos.threads;</p><p>　

44、　import nachos.machine.*;</p><p>　　public class Condition2Test { </p><p>　　Lock condlock = new Lock();</p><p>　　Condition2 c2test = new Condition2(condlock);</p><p>　　p

45、ublic Condition2Test(){ </p><p><b>　　}</b></p><p>　　public void simpleCondition2Test(){ </p><p>　　System.out.println("\n ****Condition2Test is now executing.***

46、*");</p><p>　　System.out.println("初始化賬戶(hù)余額為10000");</p><p>　　final MyCount myCount = new MyCount("0000001", 10000); //創(chuàng)建并發(fā)訪問(wèn)的賬戶(hù)</p><p>　　KThread thread1 = n

47、ew KThread(new Runnable() {</p><p>　　public void run() {</p><p>　　new SaveThread("張三", myCount, 2000);</p><p>　　System.out.println("張三 goes to sleep");</p>

48、<p>　　condlock.acquire();</p><p>　　c2test.sleep();</p><p>　　System.out.println("張三 reacquires lock when woken.");</p><p>　　condlock.release();</p><p>　

49、　System.out.println("張三 is awake!!!");</p><p>　　myCount.save(2000," 張三");</p><p><b>　　}</b></p><p><b>　　});</b></p><p>　　KTh

50、read thread2 = new KThread(new Runnable() {</p><p>　　public void run() {</p><p>　　new SaveThread("李四", myCount, 2000);</p><p>　　System.out.println("李四 goes to sleep&

51、quot;);</p><p>　　condlock.acquire();</p><p>　　c2test.sleep();</p><p>　　System.out.println("李四 reacquires lock when woken.");</p><p>　　condlock.release();</

52、p><p>　　System.out.println("李四 is awake!!!");</p><p>　　myCount.save(2000," 李四");</p><p><b>　　}</b></p><p><b>　　});</b></p&g

53、t;<p>　　KThread thread3 = new KThread(new Runnable() {</p><p>　　public void run() {</p><p>　　System.out.println("thread 3 Waking up the thread");</p><p>　　condlock.

54、acquire();</p><p>　　c2test.wakeAll();</p><p>　　condlock.release();</p><p>　　System.out.println("張三 and 李四 woke up by wakeAll");</p><p><b>　　}</b>&

55、lt;/p><p><b>　　});</b></p><p>　　thread1.fork();</p><p>　　thread2.fork();</p><p>　　thread3.fork();</p><p>　　thread1.join();</p><p>　　t

56、hread2.join();</p><p>　　thread3.join();</p><p>　　System.out.println("****Condition2Test finished.****\n");</p><p>　　} </p><p><b>　　} </b&

57、gt;</p><p>　　class SaveThread extends KThread { </p><p>　　private String name; //操作人 </p><p>　　private MyCount myCount; //賬戶(hù) </p><p>　　private int

58、 x; //存款金額 </p><p>　　SaveThread(String name, MyCount myCount, int x) { </p><p>　　this.name = name; </p><p>　　this.myCount = myCount; </p><p>

59、　　this.x = x; </p><p><b>　　} </b></p><p>　　public void run() { </p><p>　　myCount.save(x, name); </p><p><b>　　} </b></p><p><b>

60、;　　} </b></p><p>　　class MyCount { </p><p>　　private String id; //賬號(hào) </p><p>　　private int cash; //賬戶(hù)余額 </p>

61、;<p>　　Lock lock = new Lock();//賬戶(hù)鎖 </p><p>　　Condition2 c2test = new Condition2(lock);</p><p>　　MyCount(String id, int cash) { </p><p>　　this.id = id; </p><p

62、>　　this.cash = cash; </p><p><b>　　} </b></p><p>　　public void save(int x, String name) { </p><p>　　lock.acquire(); //獲取鎖 </p><p>　　if

63、 (x > 0) { </p><p>　　cash += x; //存款 </p><p>　　System.out.println(name + "存款" + x + "，當(dāng)前余額為" + cash); </p><p><b>　　} </b></p

64、><p>　　lock.release(); //釋放鎖 </p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　測(cè)試結(jié)果：</b></p><p>　　3.3 Task1.3 a

65、lram類(lèi)</p><p>　　3.3.1 要求分析</p><p>　　一個(gè)線程調(diào)用waitUntil(x) 后, 它即被掛起. 在當(dāng)前時(shí)鐘走過(guò)x個(gè)滴答后, 該線程被重新喚醒. 線程被喚醒后并不一定立即進(jìn)入運(yùn)行態(tài), 只要將其放入就緒隊(duì)列中即可. 另外, 多個(gè)線程可以分別調(diào)用waitUntil函數(shù)。</p><p>　　3.3.2 設(shè)計(jì)方案</p>&

66、lt;p>　　于Alarm類(lèi)有關(guān)的是machine.Timer類(lèi). 它在大約每500個(gè)時(shí)鐘滴答使調(diào)用回調(diào)函數(shù) (由Timer.setInterruptHandler函數(shù)設(shè)置). 因此, Alarm類(lèi)的構(gòu)造函數(shù)中首先要設(shè)置該回調(diào)函數(shù)Alarm.timerInterrupt(). </p><p>　　為了實(shí)現(xiàn)waitUntil, 需要在Alarm類(lèi)中實(shí)現(xiàn)一個(gè)隊(duì)列 Alarm.alarmQueue. 隊(duì)列中的每

67、個(gè)項(xiàng)目是 (線程, 喚醒時(shí)間, 相應(yīng)條件變量) 的三元組. 在調(diào)用waitUntil(x) 函數(shù)時(shí), 首先得到關(guān)于</p><p>　　以上三元組的信息: (線程: 當(dāng)前線程, 喚醒時(shí)間: 當(dāng)前時(shí)間+x, 新分配的條件變量), 然后將該元組放入隊(duì)列中, 并對(duì)條件變量sleep操作使當(dāng)前線程掛起. 在時(shí)鐘回調(diào)函數(shù)中 (大約每500個(gè)時(shí)鐘間隔調(diào)用一次) 則依次檢查隊(duì)列中的每個(gè)三元組. 如果喚醒時(shí)間大于當(dāng)前時(shí)間, 則將

68、元組移出隊(duì)列并對(duì)元組中的條件變量執(zhí)行wake操作將相應(yīng)線程喚醒. </p><p>　　3.3.3 實(shí)現(xiàn)代碼</p><p>　　public void timerInterrupt() {</p><p><b>　　//</b></p><p>　　while(!alarmqueue.isEmpty() &&

69、amp; (alarmqueue.peek().wakeTime <= Machine.timer().getTime())){</p><p>　　AlarmThread thread = alarmqueue.remove();</p><p>　　thread.waitThread.ready();</p><p><b>　　}</b&

70、gt;</p><p><b>　　// </b></p><p><b>　　}</b></p><p>　　public void waitUntil(long x) {</p><p><b>　　//</b></p><p>　　Alarm

71、Thread thread = new AlarmThread(KThread.currentThread(), wakeTime,conditionlock);</p><p>　　alarmqueue.add(thread);</p><p>　　KThread.sleep();</p><p><b>　　//</b></p>

72、<p><b>　　}</b></p><p>　　private KThread waitThread;</p><p>　　private Condition timecondition;</p><p>　　private long wakeTime;</p><p>　　3.3.4 測(cè)試代碼及結(jié)果&

73、lt;/p><p>　　創(chuàng)建5個(gè)線程，依次“睡眠”20000ticks，線程醒來(lái)后各自打印出睡眠開(kāi)始時(shí)間，要求睡眠時(shí)間，醒來(lái)時(shí)間，以及實(shí)際睡眠時(shí)間。</p><p><b>　　測(cè)試代碼： </b></p><p>　　public static void selfTest(int numOfTest){</p><p&g

74、t;　　Runnable a = new Runnable() {</p><p>　　public void run() {</p><p>　　AlarmTestThread();</p><p><b>　　}</b></p><p><b>　　};</b></p><p

75、>　　for(int i=0; i<numOfTest; i++){</p><p>　　int numOfThreads = 5;</p><p>　　print("Creating " + numOfThreads + " num of threads");</p><p>　　for(int j=0; j&l

76、t;numOfThreads; j++){</p><p>　　KThread thread = new KThread(a);</p><p>　　thread.setName("thread");</p><p>　　thread.fork(); }</p><p>　　ThreadedKernel.alarm.wai

77、tUntil(30000000); </p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　static void AlarmTestThread(){</p><p>　　long sleepTime =20000;</p><p

78、>　　long timeBeforeSleep = Machine.timer().getTime();</p><p>　　ThreadedKernel.alarm.waitUntil(sleepTime);</p><p>　　long timeAfterSleep = Machine.timer().getTime();</p><p>　　long a

79、ctualSleepTime = timeAfterSleep - timeBeforeSleep;</p><p>　　print(KThread.currentThread().toString() + " 被要求在： " + timeBeforeSleep + " 睡眠 " + sleepTime + " ticks");</p>&

80、lt;p>　　print(KThread.currentThread().toString() + " 被喚醒時(shí)間： " + Machine.timer().getTime() + "要求睡眠時(shí)間：: " + sleepTime + " ticks, 實(shí)際睡眠時(shí)間: " + actualSleepTime);</p><p><b>　　

81、}</b></p><p>　　public static void print(String Message) {</p><p>　　System.out.println(Message);</p><p><b>　　}</b></p><p><b>　　測(cè)試結(jié)果：</b><

82、;/p><p>　　3.4 Task1.4 communicator類(lèi)</p><p><b>　　3.4.1要求分析</b></p><p>　　用條件變量實(shí)現(xiàn)Communicator類(lèi)中的speaker()和listen()函數(shù)一個(gè)鎖lock</p><p>　　兩個(gè)條件變量speaker(lock)，listener(

83、lockw)用來(lái)用來(lái)控制聽(tīng)說(shuō)動(dòng)作。</p><p>　　3.4.2 設(shè)計(jì)方案</p><p>　　每個(gè)Communicator有一個(gè)鎖 lock(保證操作的原子性) 和與該鎖聯(lián)系的兩個(gè)條件變量用于保證speaker和listener間的同步. 在speak函數(shù)中, 首先檢查若已經(jīng)有一個(gè)speaker在等待(message變量) 或無(wú)listener等待, 則掛起. 否則設(shè)置message變

84、量, 準(zhǔn)備數(shù)據(jù)并喚醒一個(gè)listener. 在listen函數(shù)中, 增加一個(gè)listener后, 若speaker數(shù)目非零且listener數(shù)目為1（及恰好可以配對(duì)）首先喚醒speaker, 然后將自己掛起以等待 speaker準(zhǔn)備好數(shù)據(jù)再將自己?jiǎn)拘? 這個(gè)問(wèn)題其實(shí)是一個(gè)緩沖區(qū)長(zhǎng)度為0的生產(chǎn)者/消費(fèi)者問(wèn)題。</p><p>　　3.4.3 實(shí)現(xiàn)代碼</p><p>　　Communicat

85、or.java</p><p>　　int speakersize,listenersize;</p><p>　　int Message; </p><p>　　Condition speaker,listener;</p><p>　　public void speak(int word) {</p><p>&l

86、t;b>　　//</b></p><p>　　while(speakersize!=0)</p><p>　　{speaker.sleep();}</p><p>　　this.Message=word;</p><p>　　speakersize++;</p><p>　　while(listene

87、rsize==0)</p><p>　　{speaker.sleep();}</p><p>　　listener.wake();</p><p>　　speakersize--;</p><p>　　speaker.wake();</p><p><b>　　//</b></p>

88、<p><b>　　}</b></p><p>　　public int listen() {</p><p><b>　　//</b></p><p>　　listenersize++;</p><p>　　if(listenersize==1&&speakersize!

89、=0)</p><p>　　speaker.wake();</p><p>　　listener.sleep();</p><p>　　int myMessage = this.Message;</p><p>　　listenersize--;</p><p><b>　　//</b></

90、p><p>　　return myMessage;</p><p><b>　　}</b></p><p>　　3.4.4 測(cè)試代碼及結(jié)果</p><p><b>　　測(cè)試代碼：</b></p><p>　　package nachos.threads;</p>&

91、lt;p>　　import nachos.machine.*;</p><p>　　import java.util.ArrayList;</p><p>　　import java.util.Random;</p><p>　　public class CommunicatorTest {</p><p>　　public Commu

92、nicatorTest(){ </p><p>　　Message = 1;</p><p>　　numOfSpeakers = 5;</p><p>　　numOfListeners = 5;</p><p>　　communicator = new Communicator();</p><p><b>

93、　　}</b></p><p>　　public void commTest(int num){</p><p>　　System.out.println("\nCommunicatorTest開(kāi)始"); </p><p>　　for (int i=0; i<num; i++){ </p><p>　　c

94、reateSpeakers(numOfSpeakers);</p><p>　　createListeners(numOfListeners);</p><p>　　print("\n 演講者: " + numOfSpeakers);</p><p>　　print(" 收聽(tīng)者: " + numOfListeners + &q

95、uot;\n");</p><p>　　sleep(numOfSpeakers+numOfListeners);</p><p>　　print("\n 演講者與收聽(tīng)者創(chuàng)建完畢");</p><p><b>　　}</b></p><p>　　print(" Communic

96、ator Test結(jié)束 ");</p><p><b>　　}</b></p><p>　　public void sleep(int numThreadsCreated){</p><p>　　ThreadedKernel.alarm.waitUntil(numThreadsCreated*100);</p><

97、p><b>　　}</b></p><p>　　public class Listener implements Runnable{</p><p>　　public void run(){</p><p>　　int messageToRecieve = communicator.listen();</p><p&g

98、t;　　System.out.print(Message);</p><p>　　print(" " + KThread.currentThread().getName() + " 收到信息 " + messageToRecieve);</p><p><b>　　}</b></p><p><

99、b>　　}</b></p><p>　　public class Speaker implements Runnable{</p><p>　　public void run(){</p><p>　　communicator.speak(Message++);</p><p>　　System.out.print(Mess

100、age);</p><p>　　print(" " + KThread.currentThread().getName() + " 發(fā)出信息 " + Message); </p><p><b>　　}</b></p><p><b>　　}</b&g

101、t;</p><p>　　public void createSpeakers(int speakers){</p><p><b>　　int j;</b></p><p>　　for(j=1; j<=speakers; j++){ </p><p>　　KThread speaker

102、Thread = new KThread(new Speaker());</p><p>　　speakerThread.setName("Speaker" + j);</p><p>　　speakerThread.fork();</p><p><b>　　};</b></p><p><b

103、>　　}</b></p><p>　　public void createListeners(int listeners){</p><p><b>　　int k;</b></p><p>　　for(k=1; k<=listeners; k++){ </p><p>　　KThr

104、ead listenerThread = new KThread(new Listener());</p><p>　　listenerThread.setName("Listener" + k);</p><p>　　listenerThread.fork(); </p><p><b>　　}</b&

105、gt;</p><p><b>　　}</b></p><p>　　public static void print(String Message) {</p><p>　　System.out.println(Message);</p><p><b>　　}</b></p><

106、;p>　　public static int MAX_THREADS = 245;</p><p>　　private int Message; </p><p>　　private Communicator communicator;</p><p>　　private int numOfSpeakers;</p><p>　　pri

107、vate int numOfListeners;</p><p><b>　　}</b></p><p><b>　　測(cè)試結(jié)果：</b></p><p>　　3.5 Task1.5 priority scheduler類(lèi)</p><p>　　3.5.1 要求分析</p><p&g

108、t;　　實(shí)現(xiàn)優(yōu)先級(jí)調(diào)度。優(yōu)先級(jí)調(diào)度的傳統(tǒng)算法如下: 每個(gè)線程擁有一個(gè)優(yōu)先級(jí) (在Nachos中, 優(yōu)先級(jí)是一個(gè)0到7之間的整數(shù), 默認(rèn)為1， 在線程調(diào)度時(shí), 調(diào)度程序選擇一個(gè)擁有最高優(yōu)先級(jí)的處于就緒狀態(tài)的線程運(yùn)行. 這種算法的問(wèn)題是可能出現(xiàn) “饑餓” 現(xiàn)象: 設(shè)想有一個(gè)低優(yōu)先級(jí)的線程處于臨界區(qū)中運(yùn)行而高優(yōu)先級(jí)的線程在臨界區(qū)外等待. 由于前者優(yōu)先級(jí)較低, 它可能不會(huì)被調(diào)度器選中從而高優(yōu)先級(jí)的線程也不得不浪費(fèi)時(shí)間等待. 需要實(shí)現(xiàn)一種 “讓

109、出” 優(yōu)先級(jí)的機(jī)制 (Priority Donation) : 提高擁有鎖的低優(yōu)先級(jí)線程的優(yōu)先級(jí)以使它迅速完成臨界區(qū), 不使其它較高優(yōu)先級(jí)的線程等待太久. 重新計(jì)算后的優(yōu)先級(jí)稱(chēng)為有效優(yōu)先級(jí), 它可以不斷變化. 以有效優(yōu)先級(jí)為評(píng)判標(biāo)準(zhǔn)。</p><p>　　3.5.2 設(shè)計(jì)方案</p><p>　　要完善的的PriorityScheduler繼承自Scheduler。</p>

110、<p>　　每個(gè)KThread類(lèi)的線程都有一個(gè)ThreadState類(lèi)型的 “線程狀態(tài)” 對(duì)象. 它保存了線程的優(yōu)先級(jí)priority, 有效優(yōu)先級(jí)effectivepriority以及正在等待該線程的線程隊(duì)列IHave，該線程正在等待的線程隊(duì)列Iwant。</p><p>　　不同的調(diào)度器有不同類(lèi)型的線程隊(duì)列 (均繼承自ThreadQueue)， 線程隊(duì)列由threadstate對(duì)象組成，是否可提高擁

111、有鎖線程優(yōu)先級(jí)取決于創(chuàng)建隊(duì)列時(shí)transferPriority的值，它有兩個(gè)重要方法: waitForAccess (KThread thread) 和 acquire (KThread thread). 前者將一個(gè)線程加入等待隊(duì)列(實(shí)際上加入的是該線程的線程狀態(tài)); 后者將一個(gè)線程從等待隊(duì)列中取出, 表示該線程當(dāng)前處于運(yùn)行狀態(tài). 這兩個(gè)方法中, 首先找出相應(yīng)線程的線程狀態(tài), 再對(duì)線程狀態(tài)執(zhí)行相應(yīng)的waitForAccess和acqui

112、re操作 (對(duì)隊(duì)列的真正操作是在ThreadState.waitForAccess和ThreadState.acquire中完成的). </p><p>　　設(shè)置, 返回, 增加, 減少優(yōu)先級(jí)的函數(shù)在Scheduler中. ThreadQueue.nextThread 返回當(dāng)前隊(duì)列中有效優(yōu)先級(jí)最高的線程以運(yùn)行之. 而對(duì)某線程有效優(yōu)先級(jí)的計(jì)算在ThreadState.getEffectivePriority中. 當(dāng)

113、該線程沒(méi)有正在等待該線程的線程隊(duì)列時(shí)，其有效優(yōu)先級(jí)等于其原始優(yōu)先級(jí)，不然其有效優(yōu)先級(jí)增加到不小于其等待隊(duì)列IHave中各線程的有效優(yōu)先級(jí)的最大值。它也有兩個(gè)重要方法: waitForAccess (PriorityQueue waitQueue) 和 acquire (PriorityQueue waitQueue). 前者將waitqueue從IHave中移出（如果有的話），加入到Iwant中；后者將waitqueue從Iwant中移

114、出（如果有的話），加入到IHave中。</p><p>　　3.5.3 實(shí)現(xiàn)代碼</p><p>　　實(shí)現(xiàn)代碼見(jiàn)PriorityScheduler.java</p><p>　　3.5.4 測(cè)試代碼及結(jié)果</p><p>　　測(cè)試方法：創(chuàng)建兩個(gè)可捐贈(zèng)優(yōu)先級(jí)q1，q2及一個(gè)不可捐贈(zèng)優(yōu)先級(jí)隊(duì)列q3，三個(gè)優(yōu)先級(jí)分別高中低線程l，m，h。第一次將l，

115、m加到q1隊(duì)列，l，m加到q2隊(duì)列，測(cè)試q1的nextthread是m。分別測(cè)試優(yōu)先級(jí)是否“捐贈(zèng)”，低優(yōu)先級(jí)線程提告優(yōu)先級(jí)后是否被選中執(zhí)行。</p><p><b>　　測(cè)試代碼：</b></p><p>　　package nachos.threads;</p><p>　　import nachos.machine.*;</p>

116、<p>　　import nachos.threads.*;</p><p>　　import java.util.*;</p><p>　　public final class PrioritySchedulerTest {</p><p><b>　　/**</b></p><p>　　* A very

117、 simple test of priority donation.</p><p><b>　　*/</b></p><p>　　public static void simplePrioritySchedulerTest() {</p><p>　　final boolean intStatus = Machine.interrupt().

118、disable();</p><p>　　final Scheduler s = new PriorityScheduler();</p><p>　　// Enable priority donation.</p><p>　　final ThreadQueue q1 = s.newThreadQueue(false);</p><p>　

119、　final ThreadQueue q2 = s.newThreadQueue(false);</p><p>　　final ThreadQueue q3 = s.newThreadQueue(true);</p><p>　　final Runnable dummyRunnable = new Runnable() {</p><p>　　public voi

120、d run() {</p><p>　　// do nothing</p><p><b>　　}</b></p><p><b>　　};</b></p><p>　　// Create dummy Threads</p><p>　　final KThread lowPr

121、iorityThread = new KThread(dummyRunnable);</p><p>　　final KThread mediumPriorityThread = new KThread(dummyRunnable);</p><p>　　final KThread highPriorityThread = new KThread(dummyRunnable);</p

122、><p>　　// Link dummy Threads with dummy ThreadState</p><p>　　s.setPriority(lowPriorityThread, PriorityScheduler.priorityMinimum);</p><p>　　s.setPriority(mediumPriorityThread, PriorityS

123、cheduler.priorityDefault);</p><p>　　s.setPriority(highPriorityThread, PriorityScheduler.priorityMaximum);</p><p>　　// Test that effectivePriorities start as the initial priorities</p><

124、;p>　　Lib.assertTrue(s.getEffectivePriority(lowPriorityThread) == PriorityScheduler.priorityMinimum);</p><p>　　Lib.assertTrue(s.getEffectivePriority(mediumPriorityThread) == PriorityScheduler.priorityDefau

125、lt);</p><p>　　Lib.assertTrue(s.getEffectivePriority(highPriorityThread) == PriorityScheduler.priorityMaximum);</p><p>　　// Low priority and Medium priority thread are on the ready queue</p>

126、;<p>　　q1.waitForAccess(lowPriorityThread);</p><p>　　q1.waitForAccess(mediumPriorityThread);</p><p>　　q2.waitForAccess(lowPriorityThread);</p><p>　　q2.waitForAccess(mediumPri