Nachos同步機制實習報告.doc

精品文檔同步機制實習報告善良的大姐姐2015.3.30目錄一：總體概述3二：任務完成情況3任務完成列表（Y/N）3具體Exercise的完成情況3三：遇到的困難以及解決方法12四：收獲及感想12內容五：參考文獻13一：總體概述Lab3首先要求閱讀Nachos系統(tǒng)提供的同步機制代碼，即Semaphore的實現(xiàn)。其次要求修改底層源代碼，達到“擴展同步機制，實現(xiàn)同步互斥實例”的目標。具體來說，即要求在Semaphore的基礎上，實現(xiàn)Lock鎖和Mesa管程的Condition（條件變量）。此外，還要利用編寫的同步機制，來實現(xiàn)互斥實例，進而證明同步機制編寫的正確性。二：任務完成情況任務完成列表（Y/N）Exercise1Exercise2Exercise3Exercise4Challenge1Challenge2YesYesYesYesYesYes具體Exercise的完成情況Exercise1：調研任務：調研Linux中實現(xiàn)的同步機制調研情況：Linux的同步機制包括好幾層。第一層：原子操作。以x86體系結構為例，定義在linuxX.X/include/asm-i386/atomic.h文件中。文件內定義了原子類型atomic_t，其僅有一個字段counter，用于保存32位數(shù)據(jù)。其中原子操作函數(shù)atomic_inc完成自加原子操作。第二層：自旋鎖。以x86體系結構為例，定義在linuxX.X/include/asm-i386/spinlock.h文件中。其中_raw_spin_lock完成自旋鎖的加鎖功能。自旋鎖達到的效果為，在等待鎖的線程會不斷地申請鎖，直到獲得鎖或是時間片用盡從而離開CPU。第三層：信號量以x86體系結構為例，定義在linuxX.X/include/asm-i386/semaphore.h文件中。信號量的申請操作使用down函數(shù)，釋放操作使用up函數(shù)。即通常所說的PV操作。區(qū)別于自旋鎖，當一個進程在等待一個鎖時，會讓出CPU進入休眠狀態(tài)，直到其他進程釋放鎖后，將該進程放入可運行隊列。Exercise2：源代碼閱讀任務閱讀下列源代碼，理解Nachos現(xiàn)有的同步機制。code/threads/synch.h和code/threads/synch.cccode/threads/synchlist.h和code/threads/synchlist.cc閱讀情況Synch.cc(h)文件中有三個類：Semaphore, Lock, Condition。其中Semaphore是已經(jīng)編寫完成的。主要功能是：通過一個名字和一個初始值可以初始化一個Semaphore。P函數(shù)的作用是：判斷當前線程能否進入臨界區(qū)，如果可以（即初始值0），則進入，且初始值減一；如果不能（即初始值0），則將當前線程放入Semaphore的等待隊列中，線程進入休眠狀態(tài)。V函數(shù)的作用是：如果Semaphore的等待隊列不為空，將等待隊列的隊頭線程取出來，將其狀態(tài)標識為ReadyToRun，并且初始值加1。另外兩個類是本次作業(yè)需要完成的，會在之后說明。Synchlist.cc(h)文件中包括一個Synchlist類，實現(xiàn)了一個互斥訪問的隊列。 具體來說，類中有一個Append函數(shù)，用于將元素加入隊列；有一個Remove函數(shù)，用于將隊頭元素移出隊列。而互斥訪問的實現(xiàn)方式為：用Lock鎖將Append函數(shù)體和Remove函數(shù)體保護起來。保證了二者至多只有一個可以被被CPU運行，直到函數(shù)體結束。（即線程切換的中斷不會造成線程交替運行） 這兩個函數(shù)模擬了monitor（管程）的函數(shù)體互斥性，因此在之后的作業(yè)中會用到。Exercise3：實現(xiàn)鎖和條件變量任務可以使用sleep和wakeup兩個原語操作（注意屏蔽系統(tǒng)中斷），也可以使用Semaphore作為唯一同步原語（不必自己編寫開關中斷的代碼）。 完成情況1. Lock簡述：使用Semaphore作為同步原語，定義的時候創(chuàng)建一個初始值為1的Semaphore。對應的，Acquire函數(shù)就是執(zhí)行Semaphore的P函數(shù)，Release函數(shù)就是執(zhí)行Semaphore的V函數(shù)。驗證正確性：采用基于優(yōu)先級搶占式調度，一個線程遞歸生成優(yōu)先級更高的線程。如果沒有Lock，那么當前線程就會被搶占，那么運行結果會是這樣：再接連輸出after fork接連輸出before fork但若在線程一開始加上了互斥鎖，那么只有當當前線程運行結束后，它fork出來的線程才能獲得鎖，才能運行，運行結果如下：一個線程輸出了before fork和after fork之后，另一個線程才能輸出2. Condition簡述：修改情況簡單解釋新增List變量conditionlist容納正在等待某個signal的線程Wait函數(shù)：1. 對傳入的Lock參數(shù)執(zhí)行Release2. 關中斷3. 將當前線程加入conditionlist，當前線程Sleep4. 對傳入的Lock參數(shù)執(zhí)行Acquire5. 開中斷Release的原因是，由于管程的互斥訪問性，當一個線程需要wait一個signal時，需要讓出CPU。而在Nachos系統(tǒng)中，管程的互斥訪問是由Lock保證的，為了防止死鎖，需要在當前線程進入休眠之前釋放lock。當線程再次被喚醒時，需要再次Acquire這把鎖。Signal函數(shù)：1. 關中斷2. 如果conditionlist隊列不為空，將隊頭線程取出，并放入ReadyToRun隊列3. 開中斷Signal函數(shù)即喚醒一個正在等待這個條件變量的線程。Broadcast函數(shù)：1. 關中斷2. 將conditionlist隊列中所有線程取出，并放入ReadyToRun隊列3. 開中斷Broadcast函數(shù)即喚醒所有正在等待這個條件變量的線程。Exercise4：實現(xiàn)同步互斥實例任務基于Nachos中的信號量、鎖和條件變量，采用兩種方式實現(xiàn)同步和互斥機制應用（其中使用條件變量實現(xiàn)同步互斥機制為必選題目）。具體可選擇“生產者-消費者問題”、“讀者-寫者問題”、“哲學家就餐問題”、“睡眠理發(fā)師問題”等。（也可選擇其他經(jīng)典的同步互斥問題）完成情況1. 基于Nachos信號量實現(xiàn)“生產者-消費者”問題（基于時間片輪轉調度，時間片長度隨機。為了使得中斷有可能在任何地方發(fā)生，在所有臨界區(qū)中的代碼語句后面都調用了interrupt-onetick）修改情況：新增測試變量和函數(shù)簡單解釋測試變量：1. isFull信號量，初始值為02. isEmpty信號量，初始值為N（N為生產者可以放入的最大數(shù)量，設為5）3. M1信號量4. 生產數(shù)組如果生產數(shù)組內元素數(shù)量達到N，則會被isFull信號量阻塞，生產者需要等待；如果生產數(shù)組內元素數(shù)量為0，則會被isEmpty信號量阻塞，消費者需要等待。M1信號量用于保證生產數(shù)組的互斥訪問。Producer函數(shù)1. isEmpty-P()2. 在M1信號量保護下訪問生產數(shù)組，加入一個元素3. isFull-V()由于IsEmpty信號量初始值為N，則生產者最多可以進入producer函數(shù)N次；相應的，isFull信號量會被釋放至多N次Consumer函數(shù)1. isFull-P()2. 在M1信號量保護下訪問生產數(shù)組，移出一個元素3. isEmpty-V()由于isFull信號量在生產者生產之后會被釋放，因此此時消費者可以消費。相應的，isEmpty信號量被釋放，使得生產者可以繼續(xù)生產。Test_Producer函數(shù)For循環(huán)40次，調用producer函數(shù)生產者生產（至多）40次。（因為可以有多個生產者）Test_consumer函數(shù)For循環(huán)40次，調用consumer函數(shù)消費者消費（至多）40次。（因為可以有多個消費者）ThreadTest函數(shù)新生成1個生產者線程（裝載Test_producer函數(shù)）和2個消費者線程（裝載Test_consumer函數(shù)）測試結果截圖：生產者放入隊列的元素兩個消費者交替消費元素發(fā)生時間片中斷，切換線程2. 基于Nachos的條件變量實現(xiàn)“生產者-消費者”問題（基于時間片輪轉調度，時間片長度隨機。為了使得中斷有可能在任何地方發(fā)生，在所有臨界區(qū)中的代碼語句后面都調用了interrupt-onetick）修改情況：增改測試變量和函數(shù)簡單解釋Synchlist.cc:新增變量1. ListEmpty條件變量2. ListFull條件變量3. Listcount計數(shù)值1和2同信號量部分的isEmpty和isFull語義計數(shù)值用于判斷生產隊列是否滿了Append函數(shù)：1. 加鎖2. 如果生產隊列滿，等待ListEmpty條件變量3. 否則將新元素加入生產隊列4. Signal listFull條件變量5. 解鎖加鎖解鎖保證管程函數(shù)執(zhí)行的互斥性。如果生產隊列滿，則等待消費者消費之后，發(fā)送listEmpty條件變量。生產之后，發(fā)送listFull條件變量，激活等待消費的消費者Remove函數(shù)1. 加鎖2. 如果生產隊列空，等待listFull條件變量3. 否則從生產隊列頭取出一個元素4. Siignal listEmpty條件變量5. 解鎖是Append函數(shù)的對偶版本。Monitor_producer函數(shù)For循環(huán)40次，往Synchlist管程里的隊列放入元素同test_producerMonitor_consumer函數(shù)For循環(huán)40次，消費Synchlist管程里的隊列的元素同test_consumerThreadTest函數(shù)新生成1個生產者線程（裝載Monitor_producer函數(shù)）和2個消費者線程（裝載Monitor_consumer函數(shù)）測試結果截圖：兩個消費者交替消費，并且不需要和生產者同步。生產者加鎖進入管程測試情況詳細分析：消費者2試圖加鎖進入管程，但由于管程互斥鎖此時在消費者1手中，因此消費者2繼續(xù)等待此時發(fā)生了中斷 線程切換消費者1加鎖進入管程（失敗，由于生產隊列滿）釋放管程互斥鎖進入等待isEmpty信號的狀態(tài)（進入隊列+sleep）生產者試圖繼續(xù)加鎖進入管程解鎖管程互斥鎖發(fā)送isFull信號放入第5個元素（最多為5）Challenge1：實現(xiàn)barrier任務可以使用Nachos 提供的同步互斥機制（如條件變量）來實現(xiàn)barrier，使得當且僅當若干個線程同時到達某一點時方可繼續(xù)執(zhí)行。完成情況增改處簡單解釋Condition類：1. 增加waitcount計數(shù)值，表示等待條件變量的隊列中的線程個數(shù)2. 增加Barrier函數(shù)，在函數(shù)中，判斷waitcount是否達到規(guī)定值，如果達到，則廣播所有隊列中的線程；否則令當前線程進入等待狀態(tài)若還沒達到規(guī)定值，則線程需要等待；若達到了，則釋放所有等待線程。這樣就可以使得規(guī)定值個數(shù)的線程“同步”運行其中，規(guī)定值設為3新增Barrier類：仿照synchlist類，實現(xiàn)了一個互斥訪問的管程。在管程函數(shù)里，調用barrier函數(shù)測試函數(shù)：新建3個線程，每個線程用for循環(huán)調用同一個Barrier類的函數(shù)10次意圖讓線程均輸出了i之后，再接著輸出i+1測試結果截圖未使用Barrier: 使用Barrier 同步（三個線程均輸出i之后才進入下一個，interrupt表示時間片到了切換線程。）不同步Challenge2：實現(xiàn)read/write lock任務基于Nachos提供的lock(synch.h和synch.cc)，實現(xiàn)read/write lock。使得若干線程可以同時讀取某共享數(shù)據(jù)區(qū)內的數(shù)據(jù)，但是在某一特定的時刻，只有一個線程可以向該共享數(shù)據(jù)區(qū)寫入數(shù)據(jù)。完成情況（基于時間片輪轉調度，時間片長度隨機。為了使得中斷有可能在任何地方發(fā)生，在reader函數(shù)和writer函數(shù)所有的代碼語句后面都調用了interrupt-onetick）修改情況：增改變量及函數(shù)簡單解釋變量：Lock mutexLock wMutex用于保護共享變量rc（記錄讀者數(shù)量）W用于讀者和寫者訪問臨界區(qū)的互斥性Reader函數(shù)1. Mutex上鎖2. Rc加1。如果rc等于1，w上鎖3. Mutex解鎖4. 讀操作5. Mutex上鎖6. Rc減1。如果rc等于0，w解鎖Mutex解鎖Mutex保護共享變量rc，因為可以允許多個讀者處于讀狀態(tài)，因此rc可能會被多個讀者同時訪問，需要保護起來。W互斥讀者和寫者，第一類讀寫者問題是讀者優(yōu)先，因此若臨界區(qū)內有讀者，寫者就會被w阻塞在臨界區(qū)外，直到所有讀者離開臨界區(qū)。Writer函數(shù)1. W上鎖2. 寫操作3. W解鎖寫者能夠進入臨界區(qū)當且僅當臨界區(qū)內沒有讀者。但寫者在臨界區(qū)內的時候，讀者不能進入。測試函數(shù)：新建一個寫者和兩個讀者，并且讓他們分別寫（讀）10次。測試結果截圖：讀者可以同時讀。（start和finish之間可以認為是臨界區(qū)）寫者在臨界區(qū)里時，即使發(fā)生了interrupt（線程切換），也無法讓讀者進入。即讀者和寫者不能同時訪問臨界區(qū)三：遇到的困難以及解決方法困難1：我在完成lab2線程調度實驗中，在readyToRun函數(shù)中對當前線程執(zhí)行了yield操作，導致lab3中V函數(shù)的原子性被破壞。（V函數(shù)會調用readyToRun函數(shù)）解決方式：將線程Yield的過程單獨封裝成一個函數(shù)，readyToRun函數(shù)僅僅負責將當前線程放入可執(zhí)行隊列當中。對于新建的一個線程（可能可以搶占當前線程），先調用該函數(shù)，判斷是否搶占。如果搶占，則讓當前線程yield；否則，調用readyToRun函數(shù)。困難2：思考如何實現(xiàn)condition的wait函數(shù)，曾一度覺得synchlist中會造成死鎖解決方式：詳細了解了管程機制之后，發(fā)現(xiàn)只要在wait函數(shù)中，先對傳入的Lock參數(shù)執(zhí)行釋放（Release）操作，當前線程再進入休眠狀態(tài)，問題就可以解決了。困難3：在寫“生產者-消費者”問題的測試函數(shù)時，從隊列中讀出來的值總是等于最后一個加入隊列的值（比如加入隊列1,2,3,4，讀出來會是4,4,4,4） 解決方式：由于傳入的是(void *)，是一個指針。因此我直接傳入了for循環(huán)中的i的地址，這就導致了i