Nachos同步機(jī)制實(shí)習(xí)報(bào)告.doc

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