2021SC@SDUSC

文章目錄

• 配置文件
• 創建線程
• 測試代碼
• 題目 1
• 題目 2
• 題目 3
• 題目 4
• 題目 5
• 題目 6
• 源碼

配置文件

在與nachos同層目錄下創建nachos.conf文件，將nachos/proj1/nachos.conf中的內容復制進去（直接復制文件也行）。

Machine.stubFileSystem = false Machine.processor = false Machine.console = false Machine.disk = false Machine.bank = false Machine.networkLink = false ElevatorBank.allowElevatorGUI = true NachosSecurityManager.fullySecure = false ThreadedKernel.scheduler = nachos.threads.RoundRobinScheduler #nachos.threads.PriorityScheduler Kernel.kernel = nachos.threads.ThreadedKernel

創建線程

在 Nachos 中，我們要如何去創建一個線程呢？將目光聚集到nachos/threads/KThread.java，在類的注釋中，我們能找到答案。

要創建一個新線程，首先得聲明一個實現Runnable接口的類，并實現里面的run方法。

class PiRun implements Runnable {public void run() {// compute pi...} }

該類的對象將在實例化KThread時作為參數傳入，線程在創建后我們可以調用它的fork方法使它運行。

PiRun p = new PiRun(); new KThread(p).fork();

測試代碼

我們可以在nachos/threads/KThread.java下的selfTest方法中寫我們的測試代碼，比如我們讓控制臺打印一行數字。

public static void selfTest() {Lib.debug(dbgThread, "Enter KThread.selfTest");System.out.println(123456789);new KThread(new PingTest(1)).setName("forked thread").fork();new PingTest(0).run(); }

進入nachos/machine/Machine.java中，從main入口點運行這個程序，控制臺輸出如下。

nachos 5.0j initializing... config interrupt timer user-check grader 123456789 *** thread 0 looped 0 times *** thread 1 looped 0 times *** thread 0 looped 1 times *** thread 1 looped 1 times *** thread 0 looped 2 times *** thread 1 looped 2 times *** thread 0 looped 3 times *** thread 1 looped 3 times *** thread 0 looped 4 times *** thread 1 looped 4 times Machine halting!Ticks: total 2130, kernel 2130, user 0 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: page faults 0, TLB misses 0 Network I/O: received 0, sent 0

我們清楚地看到，我們想要的內容在第 2 行打印出來了。

題目 1

實現 Kthread 的 join() 函數。join() 函數的作用是，B 線程調用了 A.join()，B 線程應該等待，直到 A 結束后再執行。

實驗大綱中給出的提示是：為每個 Kthread 增添一個等待隊列，里面存放所有需要等待該線程執行結束后才能繼續執行的線程。然后當該線程執行結束后，將所有等待隊列中的線程喚醒。

現在，nachos/threads/KThread.java下的join方法中不存在業務邏輯代碼，需要等待我們去完善。

在構思等待隊列waitQueue怎么寫之前，我們先看一下就緒隊列readyQueue的寫法。

public KThread() {if (currentThread != null) {tcb = new TCB();} else {readyQueue = ThreadedKernel.scheduler.newThreadQueue(false);readyQueue.acquire(this);...} }public void ready() {...if (this != idleThread)readyQueue.waitForAccess(this);... }private static void runNextThread() {KThread nextThread = readyQueue.nextThread();... }private static ThreadQueue readyQueue = null;

readyQueue在創建第一個線程的時候進行實例化。當某線程調用ready方法的時候，該線程會進入到就緒隊列中，等待調度。在runNextThread中，readyQueue會調用nextThread方法，獲取隊列中下一個線程。

值得一說的是，acquire方法會通知隊列，一個線程已經得到訪問權限，此時其他線程不能得到執行。但是，nextThread方法會將訪問權限轉移到隊列中的下一個線程，這樣的話，得到訪問權限的線程就可以運行了。

我們可以仿照readyQueue的方式，來構建我們的waitQueue，但要注意幾點不同：

• 一個內核中，一個就緒隊列就足夠了，但等待隊列不行，每個線程都可能有它們各自的等待隊列，所以，waitQueue不能是靜態變量；
• 某個線程的等待隊列中，訪問權限的轉移需要該線程finish之后才能轉移，而非yield（讓出 CPU）或sleep（休眠）；
• 在join方法中，因為涉及到當前線程的切換，所以我們需要進行關中斷以及恢復中斷；
• CPU 的使用權會在當前線程離開后交給就緒隊列中的第一個線程，而在等待隊列中的線程只等待隊列的所屬線程，隊列中的線程之間不存在誰等著誰的關系，所以在等待隊列的所屬線程finish之后，讓隊列中的所有線程都進入就緒狀態。

在KThread類中聲明變量waitThreadList：

private LinkedList<KThread> waitThreadList = null;

在構造函數中將waitThreadList初始化：

public KThread() {...// 初始化等待線程列表waitThreadList = new LinkedList<>(); }

join方法如下：

public void join() {Lib.debug(dbgThread, "Joining to thread: " + toString());Lib.assertTrue(this != currentThread);// 關中斷，同時獲取到之前的中斷狀態boolean intStatus = Machine.interrupt().disable();// 如果該線程（調用 join 方法的線程）未處于完成狀態if (this.status != statusFinished) {// 將當前線程（正在運行的線程）添加到等待線程列表waitThreadList.add(KThread.currentThread());// 讓當前線程進入休眠狀態currentThread.sleep();}// 恢復中斷Machine.interrupt().restore(intStatus); }

完善finish方法：

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;// 遍歷當前線程的等待線程列表for (KThread waitThread : currentThread().waitThreadList) {// 讓等待線程進入就緒裝填waitThread.ready();}sleep(); }

測試程序：

public static void test1() {System.out.println("\n<--- 題目 1 開始測試 --->\n");// 創建 A 線程KThread threadA = new KThread(new Runnable() {@Overridepublic void run() {for (int i = 0; i < 5; i++) {// 如果就緒隊列中有其他線程，那么該線程讓出 CPU，進入就緒隊列System.out.println("A 線程嘗試讓出 CPU");currentThread.yield();}System.out.println("A 線程運行結束");}});// 創建 B 線程KThread threadB = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("B 線程開始運行");// A 線程加入System.out.println("A 線程加入");threadA.join();System.out.println("B 線程結束運行");// 要在兩個線程都結束的時候打印下面語句System.out.println("\n<--- 題目 1 結束測試 --->\n");}});// 啟動線程threadB.fork();threadA.fork(); }

修改selfTest方法：

public static void selfTest() {Lib.debug(dbgThread, "Enter KThread.selfTest");test1();}

啟動主程序，控制臺打印如下：

nachos 5.0j initializing... config interrupt timer user-check grader<--- 題目 1 開始測試 --->B 線程開始運行 A 線程加入 A 線程嘗試讓出 CPU A 線程嘗試讓出 CPU A 線程嘗試讓出 CPU A 線程嘗試讓出 CPU A 線程嘗試讓出 CPU A 線程運行結束 B 線程結束運行<--- 題目 1 結束測試 --->Machine halting!Ticks: total 2110, kernel 2110, user 0 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: page faults 0, TLB misses 0 Network I/O: received 0, sent 0Process finished with exit code 0

題目 2

提供一個不使用信號量工具來實現的條件變量。條件變量的作用是，當一個進程/線程執行過程中發現有一些前提條件沒有完成，那么這個進程/線程可以使用條件變量掛起，直到其他進程/線程前提條件完成再將該進程/線程喚醒。

實驗大綱中給出的提示是：為每個條件變量實現一個隊列，使用條件變量的線程在該條件變量的隊列上掛起，喚醒時從隊列中移除。

在nachos/threads下，有兩個條件變量類，分別是Condition和Condition2。它們的區別是：前者是基于信號量的實現，后者是通過關中斷進行同步的實現。根據題目要求，我們選擇后者，我們需要補全Condition2.java中的方法。

根據提示，我們需要創建一個等待線程列表，當調用sleep方法時，我們將當前線程添加到等待列表，而當調用wake（wakeAll）方法時，我們將一個（全部）線程從等待列表中取出，讓它們進入就緒隊列。

創建等待隊列waitThreadList：

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

sleep方法如下：

public void sleep() {Lib.assertTrue(conditionLock.isHeldByCurrentThread());conditionLock.release();// 關中斷，并獲取之前的中斷狀態boolean intStatus = Machine.interrupt().disable();// 將當前線程添加到等待線程列表waitThreadList.add(KThread.currentThread());KThread.currentThread().sleep();// 恢復中斷Machine.interrupt().restore(intStatus);conditionLock.acquire(); }

wake方法如下：

public void wake() {Lib.assertTrue(conditionLock.isHeldByCurrentThread());// 關中斷，并獲取之前的中斷狀態boolean intStatus = Machine.interrupt().disable();// 如果等待線程列表非空if (!waitThreadList.isEmpty()) {// 獲取等待線程隊列的第一個線程KThread thread = waitThreadList.removeFirst();if (thread != null) {// 讓它進入就緒狀態thread.ready();}}// 恢復中斷Machine.interrupt().restore(intStatus); }

wakeAll方法如下：

public void wakeAll() {Lib.assertTrue(conditionLock.isHeldByCurrentThread());// 關中斷，并獲取之前的中斷狀態boolean intStatus = Machine.interrupt().disable();// 遍歷條件變量中所有等待的線程for (KThread thread : waitThreadList){// 讓這些線程進入就緒狀態thread.ready();}// 清空等待列表waitThreadList.clear();// 恢復中斷Machine.interrupt().restore(intStatus); }

回到nachos/threads/KThread.java，測試程序如下：

public static void test2() {System.out.println("\n<--- 題目 2 開始測試 --->\n");// 創建鎖以及條件變量Lock lock = new Lock();Condition2 condition = new Condition2(lock);// 創建 A 線程KThread threadA = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("A 線程開始運行");// 獲得鎖lock.acquire();// 掛起當前線程System.out.println("A 線程進入休眠狀態");condition.sleep();System.out.println("A 線程被喚醒");// 釋放鎖lock.release();System.out.println("A 線程結束運行");}});// 創建 B 線程KThread threadB = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("B 線程開始運行");// 獲得鎖lock.acquire();// 掛起當前線程System.out.println("B 線程進入休眠狀態");condition.sleep();System.out.println("B 線程被喚醒");// 釋放鎖lock.release();System.out.println("B 線程結束運行");System.out.println("\n<--- 題目 2 結束測試 --->\n");}});// 創建 C 線程KThread threadC = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("C 線程開始運行");// 獲得鎖lock.acquire();// 喚醒所有線程System.out.println("C 線程嘗試喚醒所有線程");condition.wakeAll();// 釋放鎖lock.release();System.out.println("C 線程結束運行");}});// 啟動線程threadA.fork();threadB.fork();threadC.fork(); }

在selfTest方法調用一下test2方法中，即可在運行時執行上述代碼。打印信息如下：

nachos 5.0j initializing... config interrupt timer user-check grader<--- 題目 2 開始測試 --->A 線程開始運行 A 線程即將被掛起 B 線程開始運行 B 線程即將被掛起 C 線程開始運行 C 線程嘗試喚醒所有線程 C 線程結束運行 A 線程被喚醒 A 線程結束運行 B 線程被喚醒 B 線程結束運行<--- 題目 2 結束測試 --->Machine halting!Ticks: total 2160, kernel 2160, user 0 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: page faults 0, TLB misses 0 Network I/O: received 0, sent 0Process finished with exit code 0

題目 3

實現 Alarm 中的 waitUntil(long) 方法。作用是使得一個內核線程等待一段時間后再繼續執行。

實驗大綱中給出的提示是：在 Alarm 中實現一個隊列，所有 waitUntil() 等待的線程都在隊列里，然后每次時鐘中斷時檢查隊列，將到時間的線程喚醒。

實際上，用普通的先出先出隊列是不合適的。因為線程的最早喚醒時刻是進入休眠的時刻加休眠的時間，休眠之間足夠長的話，早進入休眠狀態的線程不一定就能早被喚醒。因此，我們用普通的鏈表就行了。

進入nachos/threads/Alarm.java，鏈表以及鏈表中的元素聲明如下（別忘記引入java.util.LinkedList）：

// 等待中的線程以及它的喚醒時間 private static class WakeInfo {private KThread thread;private long wakeTime;private WakeInfo(KThread thread, long waitTime) {this.thread = thread;this.wakeTime = waitTime;}private KThread getThread() {return this.thread;}private long getWakeTime() {return this.wakeTime;} }LinkedList<WakeInfo> list;

在Alarm的構造方法中將鏈表進行初始化：

public Alarm() {// 鏈表初始化list = new LinkedList<WakeInfo>();Machine.timer().setInterruptHandler(new Runnable() {public void run() {timerInterrupt();}}); }

在waitUnitl方法中，根據當前線程以及最早喚醒時間創建一個WakeInfo，并將它添加到鏈表中：

public void waitUntil(long x) {// 關中斷，并獲取之前的中斷狀態boolean intStatus = Machine.interrupt().disable();// 計算被喚醒的時間long wakeTime = Machine.timer().getTime() + x;// 創建一個 WakeInfo，并將它添加到鏈表中去list.add(new WakeInfo(KThread.currentThread(), wakeTime));// 讓當前線程進入睡眠狀態KThread.currentThread().sleep();// 恢復中斷Machine.interrupt().restore(intStatus); }

檢查處于休眠狀態的線程，如果到喚醒時間了，就把它放入就緒隊列中：

public void timerInterrupt() {// 關中斷，并獲取之前的中斷狀態boolean intStatus = Machine.interrupt().disable();// 遍歷鏈表中的每一個元素for (WakeInfo wakeInfo : list) {// 如果當前時間超過線程的喚醒時間if (Machine.timer().getTime() >= wakeInfo.getWakeTime()) {// 將該線程添加到就緒隊列wakeInfo.getThread().ready();// 從線程鏈表中移出這個元素list.remove(wakeInfo);}}// 當前線程讓出 CPUKThread.currentThread().yield();// 恢復中斷Machine.interrupt().restore(intStatus); }

回到nachos/threads/KThread.java中，該題目的測試程序如下：

public static void test3(){System.out.println("\n<--- 題目 3 開始測試 --->\n");// 創建 A 進程KThread threadA = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("A 線程開始運行");// 等待時間以及計算最早喚醒時刻long waitTime = 100;long earliestWakeTime = waitTime + Machine.timer().getTime();System.out.println("A 線程將要休眠，最早喚醒時刻：" + earliestWakeTime);// 讓線程 A 進入休眠狀態ThreadedKernel.alarm.waitUntil(waitTime);// 實際喚醒時刻以及與最早喚醒時刻的差值long actualWakeTime = Machine.timer().getTime();System.out.println("A 線程退出休眠，實際喚醒時刻：" + actualWakeTime);System.out.println("A 線程兩時刻差值：" + (actualWakeTime - earliestWakeTime));}});// 創建 B 進程KThread threadB = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("B 線程開始運行");// 等待時間以及計算最早喚醒時刻long waitTime = 1000;long earliestWakeTime = waitTime + Machine.timer().getTime();System.out.println("B 線程將要休眠，最早喚醒時刻：" + earliestWakeTime);// 讓線程 B 進入休眠狀態ThreadedKernel.alarm.waitUntil(waitTime);// 實際喚醒時刻以及與最早喚醒時刻的差值long actualWakeTime = Machine.timer().getTime();System.out.println("B 線程退出休眠，實際喚醒時刻：" + actualWakeTime);System.out.println("B 線程兩時刻差值：" + (actualWakeTime - earliestWakeTime));System.out.println("\n<--- 題目 3 結束測試 --->\n");}});// 啟動線程threadA.fork();threadB.fork(); }

在selfTest方法調用一下test3方法中，即可在運行時執行上述代碼。打印信息如下：

nachos 5.0j initializing... config interrupt timer user-check grader<--- 題目 3 開始測試 --->A 線程開始運行 A 線程將要休眠，最早喚醒時刻：160 B 線程開始運行 B 線程將要休眠，最早喚醒時刻：1070 A 線程退出休眠，實際喚醒時刻：510 A 線程兩時刻差值：350 B 線程退出休眠，實際喚醒時刻：1540 B 線程兩時刻差值：470<--- 題目 3 結束測試 --->Machine halting!Ticks: total 2070, kernel 2070, user 0 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: page faults 0, TLB misses 0 Network I/O: received 0, sent 0Process finished with exit code 0

題目 4

使用條件變量實現一個類似于生產者消費者功能的程序。

實驗大綱中給出的提示是：利用信號量或者鎖等同步工具實現的一個進程同步問題的程序。更具體的說，是一個經典的生產者消費者問題。

因為在做題目 2 的時候，我們按照題目要求，使用鎖實現了條件變量，所以為了減少時間成本，在該題目中，我們沿用之前的知識。如果對信號量感興趣的話，可以去閱讀nachos/threads/Condition.java中的代碼。

我們進入nachos/threads/Communicator.java中，實現其中的線程同步。

這個類中，它允許多個說者同時等待著寫數據，也允許多個聽者同時等待著讀數據，但是，它不允許讓說者和聽者都處于等待狀態。

說者在使用speak方法的時候，如果發現有聽者正在等待著讀數據，那么它在執行方法的時候便不會阻塞住，如果發現此時沒有聽者在等待著，那么它在生產一定量數據之后便會進入休眠狀態，等待聽者來喚醒它。聽者在使用listen方法的時候同理。

為了實現同步，我們需要創建一個鎖，然后將這個鎖傳入進說者的條件變量和聽者的條件變量中。除此之外，我們還需要記錄一下處于休眠狀態的說者和聽者的數量，以便于決定在發送或接收數據的時候決定是否要等待。

變量的定義及初始化如下：

public Communicator() {lock = new Lock();speakerCondition = new Condition2(lock);listenerCondition = new Condition2(lock);wordQueue = new LinkedList<>(); }// 鎖和條件變量 private Lock lock; private Condition2 speakerCondition; private Condition2 listenerCondition;// 存儲 word 的隊列 private Queue<Integer> wordQueue;// 處于休眠狀態的 speaker 和 listener 的數量，二者不可同時大于 0 private int sleepSpeakerCount; private int sleepListenerCount;

speak方法如下：

public void speak(int word) {// 獲得鎖lock.acquire();// 將 word 存入隊列wordQueue.offer(word);// 如果此時沒有 listener 處于休眠狀態if (sleepListenerCount == 0) {// 讓 speaker 進入休眠狀態，等待 listener 喚醒sleepSpeakerCount++;speakerCondition.sleep();} else {// 喚醒一個 listenerlistenerCondition.wake();sleepListenerCount--;}// 釋放鎖lock.release(); }

listen方法如下：

public int listen() {// 獲得鎖lock.acquire();// 如果此時沒有 speaker 處于休眠狀態if (sleepSpeakerCount == 0) {// 讓 listener 進入休眠狀態，等待 speaker 喚醒sleepListenerCount++;listenerCondition.sleep();} else {// 喚醒一個 speakerspeakerCondition.wake();sleepSpeakerCount--;}// 獲取 wordint word = wordQueue.poll();// 釋放鎖lock.release();return word; }

回到nachos/threads/KThread.java中，該題目的測試程序如下：

public static void test4(){System.out.println("\n<--- 題目 4 開始測試 --->\n");Communicator communicator = new Communicator();// 創建 A 進程KThread threadA = new KThread(new Runnable() {@Overridepublic void run() {// A 線程不斷發送信息for (int i = 0; i < 5; i++) {System.out.println("A 線程說：" + (i + 1));communicator.speak(i + 1);}}});// 創建 B 進程KThread threadB = new KThread(new Runnable() {@Overridepublic void run() {// B 線程不斷接收信息for (int i = 0; i < 5; i++) {System.out.println("B 線程準備聽");int word = communicator.listen();System.out.println("B 線程聽到了：" + word);}System.out.println("\n<--- 題目 4 結束測試 --->\n");}});// 啟動線程threadA.fork();threadB.fork(); }

在selfTest方法調用一下test4方法中，即可在運行時執行上述代碼。打印信息如下：

nachos 5.0j initializing... config interrupt timer user-check grader<--- 題目 4 開始測試 --->A 線程說：1 B 線程準備聽 B 線程聽到了：1 B 線程準備聽 A 線程說：2 A 線程說：3 B 線程聽到了：2 B 線程準備聽 B 線程聽到了：3 B 線程準備聽 A 線程說：4 A 線程說：5 B 線程聽到了：4 B 線程準備聽 B 線程聽到了：5<--- 題目 4 結束測試 --->Machine halting!Ticks: total 2450, kernel 2450, user 0 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: page faults 0, TLB misses 0 Network I/O: received 0, sent 0Process finished with exit code 0

題目 5

實現優先級調度。

實驗大綱中給出的提示是：為每一個線程設定一個優先級的值，調度時找出優先級最高的線程進行調度。該題還有一個注意點，便是優先級傳遞，例如：A 線程需要等待 B 線程執行結束后才能執行，并且 A 線程優先級比 B 線程要高，那么在 A 線程等待 B 線程執行的時候，B 線程的優先級應該提高到與 A 線程相同。在這里提供一個效率不高的思路，在每次調度時，先計算每個線程經過傳遞后的實際優先級，然后再從每個線程中找出實際優先級最大的線程進行調度。

在之前幾個題目，我們選擇的調度方式是循環調度，里面的隊列是先進先出隊列：從就緒隊列中取出第一個線程，當它結束運行之后，如果想再次進入等待隊列，它需要到隊列的末尾。

在nachos/threads/RoundRobinScheduler.java，我們可以看到里面隊列的實現方式。在內部類FifoQueue中，我們發現它只有四個方法，分別是waitForAccess、nextThread、acquire和print。而先進先出隊列與優先級隊列的不同之處就在于它們對接下來要運行的線程的選擇不同，也就是說，我們只需要把關注點放到nextThread中就行了。

優先級隊列的代碼在同目錄下的PriorityScheduler.java中，里面的內部類有兩個，一個就是優先級隊列，另外一個用來綁定線程和它的優先級。在我們的Kthread類中，它并沒有任何變量來表示它的優先級大小（可能是由于在非優先級調度中，優先級沒實際作用），而ThreadState的出現有點組合式繼承的意思，在Kthread的基礎上多了一個表示優先級的整型變量priority。

ThreadState中的關鍵方法是getEffectivePriority，我們按照實驗大綱中給出的提示，將某線程的等待隊列遍歷一遍，獲取里面最高的優先級，返回它與該線程的優先級的最高值。

需要注意的是，在題目 1 中，我們在nachos/threads/KThread.java中聲明了一個waitThreadList變量用來存放等待線程，當時我們設置它的可見性為private，為了讓該類能夠訪問到它，我們需要把可見性設置為缺省、protected或public（只要不是私有就行），或者寫一個 get 方法：

// 獲取等待線程列表 public LinkedList<KThread> getWaitThreadList() {return waitThreadList; }

getEffectivePriority的實現如下：

public int getEffectivePriority() {// 有效優先級初始值int effectivePriority = getPriority();// 遍歷該線程的等待線程列表for (KThread waitThread : thread.getWaitThreadList()) {// 等待線程的有效優先級int targetPriority = getThreadState(waitThread).getEffectivePriority();// 如果等待線程的有效優先級更高if (effectivePriority < targetPriority) {// 進行優先級傳遞effectivePriority = targetPriority;}}return effectivePriority; }

按照上述的思路，waitForAccess和acquire的實現也可以參考先進先出隊列，具體實現如下：

public void waitForAccess(PriorityQueue waitQueue) {Lib.assertTrue(Machine.interrupt().disabled());// 將線程加入優先級隊列中去waitQueue.list.add(this); }public void acquire(PriorityQueue waitQueue) {Lib.assertTrue(Machine.interrupt().disabled());// 斷言此時優先級隊列中內容為空Lib.assertTrue(waitQueue.list.isEmpty()); }

setPriority方法需要加一步有效性檢測：

public void setPriority(int priority) {if (this.priority == priority)return;// 如果設置的優先級在有效范圍值之外的話，打印信息并返回if (priority < priorityMinimum || priority > priorityMaximum) {System.out.println("優先級設置失敗");return;}this.priority = priority; }

在PriorityQueue類中，對比FifoQueue，鏈表中的元素由KThread換成ThreadState，print直接照搬：

public void print() {Lib.assertTrue(Machine.interrupt().disabled());// 打印所有線程for (Iterator i = list.iterator(); i.hasNext(); ) {System.out.print(i.next() + " ");} }// 優先級隊列中的線程列表 private LinkedList<ThreadState> list = new LinkedList<>();

根據注釋，transferPriority表示是否允許優先級從等待線程轉移到擁有此隊列的線程。在獲取下一個要運行的線程的時候，如果transferPriority為false，那么就用線程本身的優先級做比較，如果transferPriority為true，那么就用經優先級傳遞后的線程的優先級做比較。nextThread和pickNextThread的實現如下：

public KThread nextThread() {Lib.assertTrue(Machine.interrupt().disabled());ThreadState threadState = pickNextThread();if (threadState == null) {return null;}// 將該線程移除后返回list.remove(threadState);return threadState.thread; }protected ThreadState pickNextThread() {ThreadState nextThreadState = null;// 當前最大優先級int currentMaxPriority = -1;// 遍歷優先級隊列中的每一個線程for (ThreadState threadState : list) {// 根據是否可以傳遞優先級，獲取到實際用于比較的優先級int threadPriority;if (transferPriority) {// 線程包括其等待隊列中最高的優先級threadPriority = threadState.getEffectivePriority();} else {// 線程本身的優先級（未傳遞）threadPriority = threadState.getPriority();}// 選擇優先級更高的線程if (threadPriority > currentMaxPriority) {nextThreadState = threadState;currentMaxPriority = threadPriority;}}return nextThreadState; }

至此，PriorityScheduler實現完畢，我們需要對它進行測試。在寫測試程序之前，我們需要改一個地方。因為，此時運行程序時，默認的調度程序是RoundRobinScheduler，我們需要修改配置文件，讓默認的調度程序改為PriorityScheduler。與nachos同目錄下，有一個名為nachos.conf的文件，我們需要修改它的ThreadedKernel.scheduler項：

ThreadedKernel.scheduler = nachos.threads.PriorityScheduler

進入nachos/threads/KThread.java，不允許優先級傳遞的測試程序如下：

public static void test5() {System.out.println("\n<--- 題目 5 開始測試 --->\n");PriorityScheduler scheduler = new PriorityScheduler();KThread threadA = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("A 線程開始運行，初始優先級為 2");System.out.println("A 線程嘗試讓出 CPU");yield();System.out.println("A 線程重新使用 CPU");System.out.println("A 線程結束運行");}});KThread threadB = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("B 線程開始運行，初始優先級為 4");System.out.println("B 線程嘗試讓出 CPU");yield();System.out.println("B 線程重新使用 CPU");System.out.println("B 線程結束運行");// // 允許優先級傳遞時打印下面的語句 // System.out.println("\n<--- 題目 5 結束測試 --->\n");}});KThread threadC = new KThread(new Runnable() {@Overridepublic void run() {System.out.println("C 線程開始運行，初始優先級為 6");System.out.println("C 線程嘗試讓出 CPU");yield();System.out.println("C 線程重新使用 CPU");System.out.println("C 線程等待 A 線程");threadA.join();System.out.println("C 線程重新使用 CPU");System.out.println("C 線程結束運行");// 不允許優先級傳遞時打印下面的語句System.out.println("\n<--- 題目 5 結束測試 --->\n");}});scheduler.getThreadState(threadA).setPriority(2);scheduler.getThreadState(threadB).setPriority(4);scheduler.getThreadState(threadC).setPriority(6);threadA.fork();threadB.fork();threadC.fork(); }

在selfTest方法調用一下test5方法中，即可在運行時執行上述代碼。打印信息如下：

nachos 5.0j initializing... config interrupt timer user-check grader<--- 題目 5 開始測試 --->C 線程開始運行，初始優先級為 6 C 線程嘗試讓出 CPU C 線程重新使用 CPU C 線程等待 A 線程 B 線程開始運行，初始優先級為 4 B 線程嘗試讓出 CPU B 線程重新使用 CPU B 線程結束運行 A 線程開始運行，初始優先級為 2 A 線程嘗試讓出 CPU A 線程重新使用 CPU A 線程結束運行 C 線程重新使用 CPU C 線程結束運行<--- 題目 5 結束測試 --->Machine halting!Ticks: total 2110, kernel 2110, user 0 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: page faults 0, TLB misses 0 Network I/O: received 0, sent 0Process finished with exit code 0

要想讓優先級能夠傳遞，我們需要修改KThread的構造函數，讓傳入就緒隊列創建方法的參數值為true。

public KThread() {if (currentThread != null) {tcb = new TCB();} else {// 參數表示是否允許優先級傳遞readyQueue = ThreadedKernel.scheduler.newThreadQueue(true);readyQueue.acquire(this);...} }

稍微改動一下test5，將結束語句的打印放到 B 線程的執行程序的末尾，然后運行這個允許優先級傳遞測試程序，打印信息如下：

nachos 5.0j initializing... config interrupt timer user-check grader<--- 題目 5 開始測試 --->C 線程開始運行，初始優先級為 6 C 線程嘗試讓出 CPU C 線程重新使用 CPU C 線程等待 A 線程 A 線程開始運行，初始優先級為 2 A 線程嘗試讓出 CPU A 線程重新使用 CPU A 線程結束運行 C 線程重新使用 CPU C 線程結束運行 B 線程開始運行，初始優先級為 4 B 線程嘗試讓出 CPU B 線程重新使用 CPU B 線程結束運行<--- 題目 5 結束測試 --->Machine halting!Ticks: total 2110, kernel 2110, user 0 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: page faults 0, TLB misses 0 Network I/O: received 0, sent 0Process finished with exit code 0

存在的問題：

當我們采用優先級調度的時候，我們每一次切換線程，遞歸獲取有效優先級的方法就要調用一次，這存在大量無意義的計算，我們需要一種緩存機制，當我們不通過join或setPriority改變線程優先級的時候，有效優先級直接用我們保存的值，而非重新計算。

優化思路 1：

用一個布爾值來表示有效優先級是否有重新計算的必要，用這種方式，我們便能以極小的改動代價來大幅度提升我們的系統性能。

在nachos/threads/KThread.java中聲明這個布爾值。

// 優先級狀態：之前的優先級順序是否有效，true 表示有效 private static boolean priorityStatus = false;// 獲取優先級狀態 public static boolean getPriorityStatus() {return priorityStatus; }// 改變優先級狀態 public static void setPriorityStatus(boolean status) {priorityStatus = status; }

join方法中使這個值置為false，表示當前的有效優先級有必要重新計算。

public void join() {Lib.debug(dbgThread, "Joining to thread: " + toString());Lib.assertTrue(this != currentThread);// 關中斷，同時獲取到之前的中斷狀態boolean intStatus = Machine.interrupt().disable();// 使之前的優先級順序失效this.setPriorityStatus(false);// 如果該線程（調用 join 方法的線程）未處于完成狀態if (this.status != statusFinished) {// 將當前線程（正在運行的線程）添加到等待線程列表waitThreadList.add(KThread.currentThread());// 讓當前線程進入休眠狀態currentThread.sleep();}// 恢復中斷Machine.interrupt().restore(intStatus); }

進入到nachos/threads/PriorityScheduler.java中的ThreadState類中，聲明優先優先級并在構造方法中進行初始化：

// 有效優先級 protected int effectivePriority;public ThreadState(KThread thread) {this.thread = thread;setPriority(priorityDefault);// 設置有效優先級this.effectivePriority = this.priority; }

獲取有效優先級的方法以及設置有效優先級的方法如下：

public int getEffectivePriority() {// 嘗試使用之前保存的數據if (KThread.getPriorityStatus()) {return effectivePriority;}// 重新計算有效優先級effectivePriority = priority;// 遍歷該線程的等待線程列表for (KThread waitThread : thread.getWaitThreadList()) {// 等待線程的有效優先級int targetPriority = getThreadState(waitThread).getEffectivePriority();// 如果等待線程的有效優先級更高if (effectivePriority < targetPriority) {// 進行優先級傳遞effectivePriority = targetPriority;}}return effectivePriority; }public void setPriority(int priority) {if (this.priority == priority)return;// 如果設置的優先級在有效范圍值之外的話，打印信息并返回if (priority < priorityMinimum || priority > priorityMaximum) {System.out.println("優先級設置失敗");return;}// 將保存的有效優先級設置為無效KThread.setPriorityStatus(false);this.priority = priority; }

同文件下的PriorityQueue類中，我們修改pickNextThread方法。我們在重新計算完有效優先級后，需要將現在的有效優先級設置為可用的，下次調度不需要重新計算。

protected ThreadState pickNextThread() {ThreadState nextThreadState = null;// 當前最大優先級int currentMaxPriority = -1;// 遍歷優先級隊列中的每一個線程for (ThreadState threadState : list) {// 根據是否可以傳遞優先級，獲取到實際用于比較的優先級int threadPriority;if (transferPriority) {// 線程包括其等待隊列中最高的優先級threadPriority = threadState.getEffectivePriority();} else {// 線程本身的優先級（未傳遞）threadPriority = threadState.getPriority();}// 選擇優先級更高的線程if (threadPriority > currentMaxPriority) {nextThreadState = threadState;currentMaxPriority = threadPriority;}}if (list.size() != 0) {// 將保存的有效優先級設置為有效KThread.setPriorityStatus(true);}return nextThreadState; }

優化思路 2：

雖然添加一個表示是否需要重新計算的標志位可以大幅度減少重新計算的次數，但是現在還是存在一些計算的浪費。因為當標志位為false時，我們重新計算了所有線程的有效優先級，但是只有調用join或setPriority的線程或與它有等待關系的線程的優先級需要計算。

現在的設計存在著一些問題，雖然一個進程知道它所擁有的等待隊列中的所有線程，但它不知道它在哪個線程的等待隊列中。如果這個問題可以解決的話，那么當我們去改變一個線程的優先級或讓它加入到別的線程的等待隊列中去的時候，我們只需要遞歸地去改變等待隊列的擁有者的有效優先級即可。

為達到這個目標，一個線程中，我們不僅要聲明等待該線程的隊列，也要聲明該線程所等待的隊列。這樣的話，題目 1 的join方法也需要做出調整。但是由于做題目 5 之前，一次聲明兩個隊列的操作看上去有點“多余”，為了保證讀者有更流暢的閱讀體驗，這里不對該題目的優化思路 2 進行實現。

題目 6

利用同步工具實現一個過橋游戲的程序。

實驗大綱中給出的提示是：與第四題類似，是一個利用信號量或者鎖等同步工具實現的一個進程同步問題。

進入到課程官網，我們發現題目要求我們去實現nachos/threads/Boat.java中的方法。游戲規則是：一群大人和小孩（不少于兩個）要去一個島，他們只有一艘小船，小船能承載兩個小孩或一個大人。

注意，這個類原先引入了nachos/ag/AutoGrader.java中的方法，這些方法都是打印語句。因為我想自定義打印，所以我把所有與AutoGrader有關的變量、方法都刪去了。

全局變量的聲明如下：

// 條件變量 private static Lock lock; private static Condition2 boatCondition; private static Condition2 adultsCondition; private static Condition2 startChildrenCondition, endChildrenContidion;// 起點人數 private static int startAdultsCount, startChildrenCount; private static int endChildrenCount; // 船上人數 private static int boatAdultsCount, boatChildrenCount;// 船是否在起點 private static boolean boatStart;// 是否都到達目的地 private static boolean success;

AdultItinerary方法的實現如下：

private static void AdultItinerary() {// 獲得鎖lock.acquire();// 如果終點沒有小孩，等待if (boatStart && endChildrenCount == 0) {adultsCondition.sleep();}// 大人劃船去終點（省略上下船過程）System.out.println("大人劃船去了終點");boatAdultsCount --;startAdultsCount--;boatStart = false;// 喚醒一個小孩endChildrenContidion.wake();// 釋放鎖lock.release(); }

ChildItinerary方法的實現如下：

private static void ChildItinerary() {// 只要沒全部到達終點，就一直循環while (!success) {// 獲得鎖lock.acquire();// 如果船在起點if (boatStart) {// 如果船上人滿了if (boatAdultsCount == 1 || boatChildrenCount == 2) {// 在起點睡眠，等待小孩喚醒startChildrenCondition.sleep();}// 如果船上沒有小孩else if (boatChildrenCount == 0) {// 上船startChildrenCount--;boatChildrenCount++;// 喚醒一下在起始點睡眠的小孩System.out.println("小孩：來個人開船");startChildrenCondition.wake();// 在船上睡眠，等別的小孩叫我boatCondition.sleep();// 被叫醒之后，到終點System.out.println("小孩坐船去了終點");boatChildrenCount--;endChildrenCount++;// 喚醒一個在終點的小孩System.out.println("小孩：檢查一下人全了嗎？不全的話回去接人");endChildrenContidion.wake();// 在終點睡眠，需要接人或全員到終點之后被喚醒endChildrenContidion.sleep();}// 如果船上有一個小孩else {boatStart = false;// 叫醒那個在船上睡眠的小孩System.out.println("小孩：我上船了，我帶你去終點");boatCondition.wake();// 到達終點System.out.println("小孩劃船去了終點");startChildrenCount--;endChildrenCount++;// 在終點睡眠，需要接人或全員到終點之后被喚醒endChildrenContidion.sleep();}}// 如果船在終點else {// 人員全部轉移完畢if (startChildrenCount == 0 && startAdultsCount == 0) {success = true;System.out.println("小孩：人全了");System.out.println("\n<--- 題目 6 結束測試 --->\n");// 叫醒所有小孩endChildrenContidion.wakeAll();}// 人員未轉移結束，并且現在船上無人else if (boatChildrenCount == 0) {// 劃船回去（省略上下船過程）System.out.println("小孩：現在起點還有 " + startAdultsCount + " 個大人");System.out.println("小孩：現在起點還有 " + startChildrenCount + " 個小孩");System.out.println("小孩：我得回起點去接他們");System.out.println("小孩劃船回到了起點");endChildrenCount--;startChildrenCount++;boatStart = true;// 有大人還在起始點且終點還有小孩if (startAdultsCount != 0 && endChildrenCount != 0) {// 喚醒一個大人System.out.println("小孩：讓大人上船");boatAdultsCount++;adultsCondition.wake();// 讓大人劃船，這個小孩先睡覺startChildrenCondition.sleep();}}}// 釋放鎖lock.release();}

測試程序如下：

public static void selfTest() {System.out.println("\n<--- 題目 6 開始測試 --->\n");begin(1, 2); }public static void begin(int adults, int children) {// 參數校驗if (adults < 0 || children < 2) {System.out.println("數據異常");return;}// 初始化條件變量lock = new Lock();boatCondition = new Condition2(lock);adultsCondition = new Condition2(lock);startChildrenCondition = new Condition2(lock);endChildrenContidion = new Condition2(lock);// 初始化初始人數startAdultsCount = adults;startChildrenCount = children;// 初始化船的位置boatStart = true;// 創建并運行大人線程for (int i = 0; i < adults; i++) {new KThread(new Runnable() {@Overridepublic void run() {AdultItinerary();}}).fork();}// 創建并運行小孩線程for (int i = 0; i < children; i++) {new KThread(new Runnable() {@Overridepublic void run() {ChildItinerary();}}).fork();} }

最后，在nachos/threads/KThreads.java的selfTest方法中調用上面的測試程序，然后運行，打印語句如下：

nachos 5.0j initializing... config interrupt timer user-check grader<--- 題目 6 開始測試 --->小孩：來個人開船 小孩：我上船了，我帶你去終點 小孩劃船去了終點 小孩坐船去了終點 小孩：檢查一下人全了嗎？不全的話回去接人 小孩：現在起點還有 1 個大人 小孩：現在起點還有 0 個小孩 小孩：我得回起點去接他們 小孩劃船回到了起點 小孩：讓大人上船 大人劃船去了終點 小孩：現在起點還有 0 個大人 小孩：現在起點還有 1 個小孩 小孩：我得回起點去接他們 小孩劃船回到了起點 小孩：來個人開船 小孩：我上船了，我帶你去終點 小孩劃船去了終點 小孩坐船去了終點 小孩：檢查一下人全了嗎？不全的話回去接人 小孩：人全了<--- 題目 6 結束測試 --->Machine halting!Ticks: total 2560, kernel 2560, user 0 Disk I/O: reads 0, writes 0 Console I/O: reads 0, writes 0 Paging: page faults 0, TLB misses 0 Network I/O: received 0, sent 0Process finished with exit code 0

源碼

項目地址：https://gitee.com/GongY1Y/nachos-study

總結

以上是生活随笔為你收集整理的【操作系统】Nachos 内核线程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。