山東大學計算機學院操作系統(tǒng)實驗報告

操作系統(tǒng)課程設計 學院：計算機科學與技術學院專業(yè)：計算機科學與技術班級：20**級*班姓名：***學號：20**********目錄實現(xiàn)代碼publicvoidjoin(){ Lib.debug(dbgThread,"Joiningtothread:"+toString()); Lib.assertTrue(this!=currentThread);booleanintStatus=Merrupt().disable();if(status!=statusFinished){waitForJoin.waitForAccess(currentThread); KThread.sleep(); }}publicstaticvoidfinish(){ Lib.debug(dbgThread,"Finishingthread:"+currentThread.toString()); Merrupt().disable(); Machine.autoGrader().finishingCurrentThread(); Lib.assertTrue(toBeDestroyed==null); toBeDestroyed=currentThread; currentThread.status=statusFinished; KThreadwaitThread; while((waitThread=currentThread.waitForJoin.nextThread())!=null){ waitThread.ready(); } sleep();}Task1.2利用中斷提供原子性，直接實現(xiàn)條件變量要求通過利用中斷有效和無效所提供的原子性實現(xiàn)條件變量。我們已經(jīng)提供類似的例子用例實現(xiàn)信號量。你要按此提供類似的條件變量的實現(xiàn)，不能直接利用信號量來實現(xiàn)（你可以使用lock，雖然它間接地調(diào)用了信號量）。在你完成時要提供條件變量的兩種實現(xiàn)方法。你的第二種條件變量實現(xiàn)要放在nachos.threads.Condition2中。分析threads.Lock類提供了鎖以保證互斥.在臨界代碼區(qū)的兩端執(zhí)行Lock.acquire()和Lock.release()即可保證同時只有一個線程訪問臨界代碼區(qū).條件變量建立在鎖之上,由threads.Condition實現(xiàn),它是用來保證同步的工具.每一個條件變量擁有一個鎖變量(該鎖變量亦可被執(zhí)行acquire和release操作,多個條件變量可共享同一個鎖變量).當處于臨界區(qū)內(nèi)的擁有某鎖L的當前線程對與鎖L聯(lián)系的條件變量執(zhí)行sleep操作時,該線程失去鎖L并被掛起.下一個等待鎖L的線程獲得鎖L(這個過程由調(diào)度程序完成)并進入臨界區(qū).當擁有鎖L的臨界區(qū)內(nèi)的當前線程對與鎖L聯(lián)系的條件變量執(zhí)行wake操作時(通常調(diào)用wake之后緊接著就是Lock.release),等待在該條件變量上的之多一個被掛起的線程(由調(diào)用sleep引起)被重新喚醒并設置為就緒狀態(tài).若執(zhí)行wakeall操作,則等待在該條件變量上的所有被掛起的線程都被喚醒.方案condition.sleep采用waiter.P()實現(xiàn)休眠(waitor是一個信號量)并將waitor放入信號量隊列,在我們的實現(xiàn)中改成用KThread.sleep()實現(xiàn)休眠并將當前線程放入線程隊列,并在sleep函數(shù)開始/結尾處屏蔽/允許中斷以保證原子性。condition.wake中從等待信號量隊列中取出信號量并對其進行V操作實現(xiàn)喚醒,在我們的實現(xiàn)中改成從線程隊列中取出線程用KThread.ready()實現(xiàn)喚醒(同樣要在wake函數(shù)開始/結尾處屏蔽/允許中斷)。wakeall函數(shù)的實現(xiàn)依賴于wake().只需不斷地wake直到隊列為空為止.實現(xiàn)代碼privateThreadQueuewaitQueue=ThreadedKernel.scheduler.newThreadQueue(false);privatebooleanhasWaiter=false;publicvoidsleep(){Lib.assertTrue(conditionLock.isHeldByCurrentThread());booleanintStatus=Merrupt().disable();waitQueue.waitForAccess(KThread.currentThread());hasWaiter=true;conditionLock.release();KThread.sleep();conditionLock.acquire();Merrupt().restore(intStatus);}publicvoidwake(){Lib.assertTrue(conditionLock.isHeldByCurrentThread()); booleanintStatus=Merrupt().disable(); KThreadthread=waitQueue.nextThread(); if(thread!=null) thread.ready(); else hasWaiter=false; Merrupt().restore(intStatus);}publicvoidwakeAll(){ Lib.assertTrue(conditionLock.isHeldByCurrentThread()); while(hasWaiter) wake();}Task1.3實現(xiàn)waitUntil要求通過實現(xiàn)waitUntil（intx）方法來完成Alarm類。分析一個線程通過調(diào)用waitUntil函數(shù)來掛起它自己，直到now+x后才被喚醒。在實時操作中，對線程是非常有用的，例如實現(xiàn)光標每秒的閃爍。這里并不要求線程被喚醒后馬上執(zhí)行它，只是在它等待了指定時間后將它。放入等待隊列中。不要通過產(chǎn)生任何附加的線程來實現(xiàn)waitUntil函數(shù)，你僅需要修改waitUntil函數(shù)和時間中斷處理程序。waitUntil函數(shù)并不僅限于一個線程使用，在任意時間，任意多的線程可以調(diào)用它來阻塞自己。方案于Alarm類有關的是machine.Timer類.它在大約每500個時鐘滴答使調(diào)用回調(diào)函數(shù)(由Timer.setInterruptHandler函數(shù)設置).因此,Alarm類的構造函數(shù)中首先要設置該回調(diào)函數(shù)Alarm.timerInterrupt().為了實現(xiàn)waitUntil,需要在Alarm類中實現(xiàn)一個內(nèi)部類Waiter,保存等待的線程及其喚醒時間.在調(diào)用waitUntil(x)函數(shù)時,首先得到關于該線程的信息:(線程:當前線程,喚醒時間:當前時間+x),然后構造新的Waiter對象,并調(diào)用sleep操作使當前線程掛起.在時鐘回調(diào)函數(shù)中(大約每500個時鐘間隔調(diào)用一次)則依次檢查隊列中的每個對象。如果喚醒時間大于當前時間,則將該對象移出隊列并執(zhí)行wake操作將相應線程喚醒。實現(xiàn)代碼classWaiter{Waiter(longwakeTime,KThreadthread){ this.wakeTime=wakeTime; this.thread=thread;}privatelongwakeTime;privateKThreadthread;}publicvoidwaitUntil(longx){booleanintStatus=Merrupt().disable(); longwakeTime=Machine.timer().getTime()+x; Waiterwaiter=newWaiter(wakeTime,KThread.currentThread()); waitlist.add(waiter); System.out.println(KThread.currentThread().getName() +"線程休眠，時間為："+Machine.timer().getTime()+",應該在 "+wakeTime+"醒來."); KThread.sleep(); Merrupt().restore(intStatus);}publicvoidtimerInterrupt(){Waiterwaiter;for(inti=0;i<waitlist.size();i++){ waiter=waitlist.remove(); if(waiter.wakeTime<=Machine.timer().getTime()) { System.out.println("喚醒線程："+waiter.thread.getName()+"，時間為："+Machine.timer().getTime()); waiter.thread.ready();//線程進入就緒狀態(tài) } else waitlist.add(waiter);} KThread.currentThread().yield();}privateLinkedList<Waiter>waitlist;Task1.4用條件變量，不使用信號量，實現(xiàn)同步發(fā)送接收消息，speak，listen要求使用條件變量來實現(xiàn)一個字長信息的發(fā)送和接收同步。使用voidspeak(intword)和intlisten()函數(shù)來實現(xiàn)通訊（Communicator）類的通訊操作。speak函數(shù)具有原子性，在相同地Communicator類中等待listen函數(shù)被調(diào)用，然后將此字發(fā)生給listen函數(shù)。一旦傳送完畢，兩個函數(shù)都返回（listen函數(shù)返回此字）。分析對一個Communicator類的對象c,線程A先調(diào)用c.speaker(x)發(fā)送一個字后被掛起,直到另一線程B調(diào)用c.listen()收到這個字x后,A和B同時返回.類似地,線程B先調(diào)用c.listen(x)后被掛起,直到另一線程B調(diào)用c.speaker(x)發(fā)送一個字后,A和B同時返回.同時需要注意在一個Communicator上有多個spaker和listener的情形.此時的speaker和listener只能是一對一的,即一個speaker只能將數(shù)據(jù)發(fā)送到一個listener,一個listener也只能接收來自一個spekaer的數(shù)據(jù),其余的speakers和listeners都需要等待.方案每個Communicator有一個鎖(保證操作的原子性)和與該鎖聯(lián)系的兩個條件變量用于保證speaker和listener間的同步.在speak函數(shù)中,首先檢查若已經(jīng)有一個speaker在等待(speaknum>0)或無listener等待,則掛起.否則設置變量,準備數(shù)據(jù)并喚醒一個listener.在listen函數(shù)中,增加一個listener后,首先喚醒speaker,然后將自己掛起以等待speaker準備好數(shù)據(jù)再將自己喚醒.這個問題其實是一個緩沖區(qū)長度為0的生產(chǎn)者/消費者問題.實現(xiàn)代碼publicCommunicator(){lock=newLock();con=newCondition(lock);}publicvoidspeak(intword){lock.acquire();if(speaknum>0||listennum==0){ speaknum++; con.sleep();}if(listennum>0){ con.wakeAll(); listennum=0;}this.word=word;System.out.println(KThread.currentThread().getName()+"線程說"+this.word);lock.release();}publicintlisten(){lock.acquire();while(listennum>0||speaknum==0){ listennum++; con.sleep(); listennum--;}if(speaknum>0){ con.wake(); speaknum--;}KThread.currentThread().yield();System.out.println(KThread.currentThread().getName()+"線程聽到"+this.word);listennum=0;lock.release(); returnthis.word;}privateLocklock;privateConditioncon;privateintword;privatestaticintspeaknum;privatestaticintlistennum;Task1.5完成PriorityScheduler實現(xiàn)優(yōu)先級調(diào)度要求通過完成PriorityScheduler類在Nachos中實現(xiàn)優(yōu)先級調(diào)度（priorityscheduling）。優(yōu)先級調(diào)度是實時系統(tǒng)中的關鍵構建模塊。分析在Nachos中,所有的調(diào)度程序都繼承抽象類Scheduler.系統(tǒng)已經(jīng)提供了一個簡單的輪轉調(diào)度器RoundRobinScheduler,它對所有線程不區(qū)分優(yōu)先級而采用簡單的FIFO隊列進行調(diào)度.我們實現(xiàn)的優(yōu)先級調(diào)度類PriorityScheduler也繼承自Scheduler.優(yōu)先級調(diào)度的傳統(tǒng)算法如下:每個線程擁有一個優(yōu)先級(在Nachos中,優(yōu)先級是一個0到7之間的整數(shù),默認為1).在線程調(diào)度時,調(diào)度程序選擇一個擁有最高優(yōu)先級的處于就緒狀態(tài)的線程運行.這種算法的問題是可能出現(xiàn)“饑餓”現(xiàn)象:設想有一個低優(yōu)先級的線程處于臨界區(qū)中運行而高優(yōu)先級的線程在臨界區(qū)外等待.由于前者優(yōu)先級較低,它可能不會被調(diào)度器選中從而高優(yōu)先級的線程也不得不浪費時間等待.為解決上述優(yōu)先級反轉問題,需要實現(xiàn)一種“讓出”優(yōu)先級的機制(PriorityDonation):提高擁有鎖的低優(yōu)先級線程的優(yōu)先級以使它迅速完成臨界區(qū),不使其它較高優(yōu)先級的線程等待太久.提高后的優(yōu)先級稱為有效優(yōu)先級,它可以不斷變化.實際調(diào)度時就是以有效優(yōu)先級為評判標準的.方案在ThreadState類中增加兩個表即LinkedList<>類，存放的對象是PriorityQueue，即優(yōu)先級隊列對象。一個表用來記錄該線程所占用資源的優(yōu)先隊列resourcesIHave，另一個表用來記錄該線程所想占有的資源的優(yōu)先隊列resourceIWant。resourcesIHave作為發(fā)生優(yōu)先級反轉時，捐獻優(yōu)先級計算有效優(yōu)先級的來源依據(jù)，resourceIWant用來為線程聲明得到資源做準備。waitForAccess（）將需要等待獲得資源的線程加入一個等待隊列等待調(diào)度。getEffectivePriority（）計算有效優(yōu)先級時，遍歷等待隊列中所用線程的有效優(yōu)先級，找出最大的優(yōu)先級即可。實現(xiàn)代碼publicvoidwaitForAccess(PriorityQueuewaitQueue){waitQueue.waitQueue.add(this.thread);if(!waitQueue.transferPriority)waitQueue.lockHolder.effectivePriority=expiredEffectivePriority;}publicvoidacquire(PriorityQueuewaitQueue){waitQueue.waitQueue.remove(this.thread); waitQueue.lockHolder=this;waitQueue.lockHolder.effectivePriority=expiredEffectivePriority;waitQueue.lockHolder.waiters=waitQueue;}publicintgetEffectivePriority(){if(effectivePriority!=expiredEffectivePriority) returneffectivePriority; effectivePriority=priority;if(waiters==null)returneffectivePriority;for(Iteratori=waiters.waitQueue.iterator();i.hasNext();){ThreadStatets=getThreadState((KThread)i.next());if(ts.priority>effectivePriority){effectivePriority=ts.priority;}} returneffectivePriority;}protectedinteffectivePriority=expiredEffectivePriority;protectedstaticfinalintexpiredEffectivePriority=-1;protectedPriorityQueuewaiters=null;publicKThreadnextThread(){Lib.assertTrue(Merrupt().disabled()); if(pickNextThread()==null) returnnull; KThreadthread=pickNextThread().thread;getThreadState(thread).acquire(this);returnthread;}protectedThreadStatepickNextThread(){if(waitQueue.isEmpty())returnnull; ThreadStatetoPick=getThreadState((KThread)waitQueue.getFirst());for(Iteratori=waitQueue.iterator();i.hasNext();){ThreadStatets=getThreadState((KThread)i.next());if(ts.getEffectivePriority()>toPick.getEffectivePriority()) toPick=ts;}returntoPick;}LinkedList<KThread>waitQueue=newLinkedList<KThread>();ThreadStatelockHolder=null;Task1.6要求用以上實現(xiàn)的線程互斥/同步機制解決一個過河問題。成人和小孩都試圖從oahu出發(fā)到molokai。一只船只可以攜帶最多兩個小孩或一個成人（但不能是一個小孩和一個成人）。船上可劃回瓦胡島，但這么做需要一個引航員。安排一個能讓所有人到molokai島的解決方案分析需要記錄的信息:O島上大人/小孩的人數(shù)M島上大人/小孩的人數(shù)船的位置(在O島還是M島)船的狀態(tài)(空/半滿/全滿)(半滿指只有一個小孩,全滿指有兩個小孩或一個大人)初始狀態(tài):大人和小孩都在O島上船在O島船為空對于大人比較簡單.若滿足以下條件則獨自乘船過河(每個大人過且僅過一次河,線程即告結束),否則(在O島)等待:O島上只有一個小孩或沒有小孩船在O島船為空對于小孩,分以下5種情況討論某小孩在O島,船在O島,船為空,O島上的小孩數(shù)大于等于2:該小孩上船等另外一個小孩上船后,兩人一起劃船過河到M某小孩在O島,船在O島,船為空,O島上沒有大人:該小孩上船過河某小孩在O島,且不屬于以上三種情況:等待某小孩在M島,船在O島:等待當所有的大人運完了之后開始運大人，當運過去兩個大人后，O島出現(xiàn)了兩個孩子，這個時候這兩個孩子劃船過河，即使此時大人還沒有完全被運送完全。返程：只有小孩可以有返程路線，大人返程沒有意義。方案使用三個鎖變量保證互斥,三個條件變量保證同步。實現(xiàn)代碼packagenachos.threads;importnachos.ag.BoatGrader;publicclassBoat{staticBoatGraderbg;staticintchildrenOnOahu=0;staticintchildrenOnMolokai=0;staticintadultOnOahu=0;staticintadultOnMolokai=0;staticintpilot=0;staticbooleanover;staticLocklock1;staticConditionchildrenWaitOnOahu;staticLocklock2;staticConditionadultWaitOnOahu;staticLocklock3;staticConditionchildrenReadyOnMolokai;publicstaticvoidbegin(intadults,intchildren,BoatGraderb){ bg=b; lock1=newLock(); childrenWaitOnOahu=newCondition(lock1); lock2=newLock(); adultWaitOnOahu=newCondition(lock2); lock3=newLock(); childrenReadyOnMolokai=newCondition(lock3); for(inti=0;i<adults;i++){ newKThread(newAdult(childrenWaitOnOahu,adultWaitOnOahu,childrenReadyOnMolokai)).setName("adult").fork(); } for(inti=0;i<children-1;i++){ newKThread(newChild(childrenWaitOnOahu,adultWaitOnOahu,childrenReadyOnMolokai)).setName("child").fork(); } KThreadt=newKThread(newChild(childrenWaitOnOahu,adultWaitOnOahu,childrenReadyOnMolokai)); t.setName("child"); t.fork(); KThread.currentThread().yield(); lock1.acquire(); childrenWaitOnOahu.wake(); lock1.release(); t.join();}staticvoidAdultItinerary(){ bg.initializeAdult(); adultOnOahu++; lock2.acquire(); adultWaitOnOahu.sleep(); bg.AdultRowToMolokai(); adultOnOahu--; adultOnMolokai++; lock2.release(); lock3.acquire(); childrenReadyOnMolokai.wake(); lock3.release();}staticvoidChildItinerary(){ bg.initializeChild(); childrenOnOahu++; lock1.acquire(); childrenWaitOnOahu.sleep(); lock1.release(); while(true){ if(pilot!=1){ if(childrenOnOahu>1){ lock1.acquire(); childrenWaitOnOahu.wake(); pilot=1; bg.ChildRowToMolokai(); childrenOnOahu--; childrenOnMolokai++; lock1.release(); lock3.acquire(); childrenReadyOnMolokai.sleep(); lock3.release(); }else{ lock2.acquire(); adultWaitOnOahu.wake(); lock2.release(); bg.AdultRideToMolokai(); lock1.acquire(); childrenWaitOnOahu.sleep(); lock1.release(); continue; } }else{ if(adultOnOahu!=0){ bg.ChildRideToMolokai(); childrenOnOahu--; childrenOnMolokai++; lock3.acquire(); childrenReadyOnMolokai.wake(); lock3.release(); lock3.acquire(); childrenReadyOnMolokai.sleep(); lock3.release(); }else{ lock3.acquire(); over=true; bg.ChildRideToMolokai(); childrenOnOahu--; childrenOnMolokai++; childrenReadyOnMolokai.wakeAll(); lock3.release(); } } if(over==true){break;} else{ pilot=3; bg.ChildRowToOahu(); childrenOnOahu++; childrenOnMolokai--; continue; }}}staticvoidSampleItinerary(){ System.out.println("\n***EveryonepilesontheboatandgoestoMolokai***"); bg.AdultRowToMolokai(); bg.ChildRideToMolokai(); bg.AdultRideToMolokai(); bg.ChildRideToMolokai();}}privatestaticclassChildimplementsRunnable{Child(ConditionchildrenWaitOnOahu,ConditionadultWaitOnOahu,ConditionchildrenReadyOnMolokai){ this.location_now=location_now; this.childrenWaitOnOahu=childrenWaitOnOahu; this.adultWaitOnOahu=adultWaitOnOahu; this.childrenReadyOnMolokai=childrenReadyOnMolokai;} publicvoidrun(){ ChildItinerary();}privateintStatus; privateintlocation_now;//1:Oahu,2:MolokaiprivateConditionchildrenWaitOnOahu;privateConditionadultWaitOnOahu;privateConditionchildrenReadyOnMolokai;}privatestaticclassAdultimplementsRunnable{ Adult(ConditionchildrenWaitOnOahu,ConditionadultWaitOnOahu,ConditionchildrenReadyOnMolokai){ this.childrenWaitOnOahu=childrenWaitOnOahu; this.adultWaitOnOahu=adultWaitOnOahu; this.childrenReadyOnMolokai=childrenReadyOnMolokai; } publicvoidrun(){ AdultItinerary(); } privateConditionchildrenWaitOnOahu; privateConditionadultWaitOnOahu; privateConditionchildrenReadyOnMolokai;}}Project2多道程序設計Task2.1要求實現(xiàn)六個系統(tǒng)調(diào)用creat,open,read,write,close,unlink分析系統(tǒng)共提供了七個系統(tǒng)調(diào)用：halt(停機,已經(jīng)提供)，creat(創(chuàng)建并打開磁盤文件)，open(打開磁盤文件)，read(讀IO,可以是磁盤或屏幕)，write(寫IO)，close(關閉IO)，unlink(刪除磁盤文件)。要確保如下幾點：穩(wěn)定性,不能因為一個進程的非法系統(tǒng)調(diào)用就使操作系統(tǒng)崩潰,而應該返回錯誤代碼。halt調(diào)用只能由第一個進程(rootprocess)執(zhí)行。系統(tǒng)調(diào)用需要讀寫內(nèi)存時,通過readVirtualMemory和writeVirtualMemory進行。文件名以null結尾,不超過256字符。如果系統(tǒng)調(diào)用出錯,應返回-1。為每個打開的IO文件分配一個“文件描述符”,用整數(shù)表示.每個進程最多可以擁有16個。其中0和1應分配給標準輸入和標準輸出(即屏幕)，這由SynchConsole類管理。不同進程可以用相同的文件描述符處理不同的文件。Nachos已經(jīng)提供了一個簡單的文件系統(tǒng)FileSystem（Machine包中）,通過ThreadedKernel.fileSystem訪問。系統(tǒng)不需要考慮文件訪問的互斥等問題。方案create系統(tǒng)調(diào)用為了實現(xiàn)“文件描述符”,為每個進程開一張大小為16的數(shù)組(本地描述符表),下標為描述符編號,內(nèi)容為文件對象(OpenFile類型,描述符未使用為null).此外,需要一個全局的Hashtable(全局文件表),key為文件名,value為該文件名被多少個進程打開。在Creat系統(tǒng)調(diào)用中，一般進行如下操作：用readVirtualMemoyString讀取文件名通過UserKernel.fileSystem.open打開文件(第二個參數(shù)為true表示創(chuàng)建新文件)維護本地描述符表(返回一個內(nèi)容為null的項目的下標作為描述符,將文件對象填入)維護全局文件表(如果全局表中沒有此文件名,將(文件名,1)放入,否則將原來的元組的value加1)返回文件描述符open系統(tǒng)調(diào)用在Open系統(tǒng)調(diào)用中進行如下操作:從內(nèi)存讀取文件名通過UserKernal.fileSystem.open打開文件(第二個參數(shù)為false)維護本地描述符表維護全局文件表返回文件描述符read系統(tǒng)調(diào)用Read系統(tǒng)調(diào)用的三個參數(shù)依次為:文件描述符,寫入的內(nèi)存地址,讀取的字節(jié)數(shù)。在Read系統(tǒng)調(diào)用中進行如下操作:從本地描述符表中得到文件對象通過OpenFile.read讀取文件內(nèi)容將文件內(nèi)容寫入內(nèi)存返回寫入內(nèi)存的字節(jié)數(shù)write系統(tǒng)調(diào)用Write系統(tǒng)調(diào)用的三個參數(shù)依次為:文件描述符,讀內(nèi)存的地址,寫入文件的字節(jié)數(shù).在Write系統(tǒng)調(diào)用中進行如下操作:從本地描述符表中得到文件對象訪問內(nèi)存,得到要寫入文件的內(nèi)容通過OpenFile.write寫文件返回寫入文件的字節(jié)數(shù)close系統(tǒng)調(diào)用Close系統(tǒng)調(diào)用的唯一一個參數(shù)為文件描述符.在Close系統(tǒng)調(diào)用中進行如下操作:從本地描述符中得到文件對象通過OpenFile.close關閉文件從本地描述符表中移出文件對象從全局文件表中移出文件名的引用(若value為1,將其中的元組刪除,否則將value減1)返回0unlink系統(tǒng)調(diào)用一般地，在Unlink調(diào)用中只需讀取文件名并執(zhí)行fileSystem.remove方法刪除文件即可。但是，一個文件可能被多個進程打開而不能立即刪除，必須等所有打開這個文件的進程都關閉該文件后才能刪除。因此，在Unlink調(diào)用中還要檢查文件名在全局文件表中的情況：若在全局文件表中不存在，則立即刪除。否則，將文件名添加到刪除隊列中。這樣，在Close系統(tǒng)調(diào)用中還要增加如下內(nèi)容：若文件關閉后它在全局文件表中已經(jīng)不存在且文件名在刪除隊列中，則此時執(zhí)行刪除文件操作，并將文件從刪除文件中移出。halt系統(tǒng)調(diào)用調(diào)用Machine.halt之前先判斷系統(tǒng)中是否還有進程在執(zhí)行，若沒有則停機。健壯性以上系統(tǒng)調(diào)用只是在一般情況下函數(shù)的執(zhí)行流程。為了提高系統(tǒng)的健壯性,在系統(tǒng)調(diào)用中還要進行下列錯誤檢查（-1表示出錯）:文件名長度不得超過256字符,不得含有非法字符或空。打開,創(chuàng)建文件時,局部描述符表不能滿,文件名不能在刪除隊列中.fileSystem的操作返回值必須正確。readVirtualMemory和writeVirtualMemory的返回值必須正確。實現(xiàn)代碼privateinthandleCreate(Stringname){OpenFilefile=ThreadedKernel.fileSystem.open(name,true); FD.put(FDCounter,file); if(GlobalFileTable.containsKey(name)){ if(!GlobalFileTable.get(name).status()){ GlobalFileTable.get(name).link(); FD.put(FDCounter,file); } elsereturn-1; }else{GlobalFileTable.put(name,newFileRec(file));FD.put(FDCounter,file);} returnFDCounter++; }privateinthandleOpen(Stringname){ OpenFilefile=ThreadedKernel.fileSystem.open(name,false); if(file==null){ return-1; } if(GlobalFileTable.containsKey(name)){ if(GlobalFileTable.get(name).status()){ GlobalFileTable.get(name).link(); FD.put(FDCounter,file); } elsereturn-1; }else{ GlobalFileTable.put(name,newFileRec(file)); FD.put(FDCounter,file); } returnFDCounter++;}privateinthandleRead(intFDnumber,intbuffer,intcount){ OpenFilefile=FD.get(FDnumber); if(file==null) return-1; byte[]buf=newbyte[count]; intstat=file.read(buf,0,count); if(writeVirtualMemory(buffer,buf)!=count) return-1; returncount;}privateinthandleWrite(intFDnumber,intbuffer,intcount){OpenFilefile=FD.get(FDnumber); if(file==null) return-1; byte[]buf=newbyte[count]; if(readVirtualMemory(buffer,buf)!=count) return-1; returncount; }privateinthandleClose(intFDnumber){ OpenFilefile=FD.get(FDnumber); if(file==null) return-1; Stringname=FD.get(FDnumber).getName(); FD.remove(FDnumber); GlobalFileTable.get(name).unlink(); if(GlobalFileTable.get(name).status()&&GlobalFileTable.get(name).GetCount()==0) GlobalFileTable.get(name).GetFile().getFileSystem().remove(name); file.close(); return0;}privateinthandleUnlink(Stringname){ if(GlobalFileTable.containsKey(name)){ GlobalFileTable.get(name).close(); if(GlobalFileTable.get(name).GetCount()==0) GlobalFileTable.get(name).GetFile().getFileSystem().remove(name); } else{ if(!UserKernel.fileSystem.remove(name)) return-1; } return0;}Task2.2要求實現(xiàn)多進程內(nèi)存分配和訪問分析由于Nachos支持多道程序設計,所以理所當然地不同進程應分配完全不同的物理內(nèi)存。Nachos不支持動態(tài)內(nèi)存分配,所以需要分配的內(nèi)存在裝入程序時就可以確定了(代碼,數(shù)據(jù),堆棧部分)。故在裝入程序時就為每個進程一次性分配固定的物理內(nèi)存,在進程結束時收回它們。這里還需要實現(xiàn)如下簡單的虛擬內(nèi)存方案:每個進程的地址空間是連續(xù)的虛擬內(nèi)存,但這些連續(xù)的虛擬頁面在物理內(nèi)存中卻不一定是連續(xù)的。這個方案的簡單之處在于,虛擬空間的總容量和物理空間的總容量相等,映射機制只是從虛擬內(nèi)存到物理內(nèi)存的一一映射。除了內(nèi)存的分配,內(nèi)存的讀寫也要體現(xiàn)出映射機制。方案系統(tǒng)提供了頁表pageTable，它以虛擬頁號為下標，其中的每個項目是一個machine.TranslationEntry類型的對象，它存放了一個頁的下列信息：物理頁號，虛擬頁號，是否有效，是否只讀，是否被用過，是否臟。在UserKernel中定義一個全局隊列freePages用于存放當前空閑的物理頁面號，一個保護全局隊列的鎖pageLock。開始時，freePages包括所有的物理頁面。當啟動新進程時,UserProcess.load負責從磁盤裝入進程。其中需要我們完善的是過程UserProcess.loadSections。該過程完成如下操作：該進程需要的頁面數(shù)已知，保存在numPage變量中。分配物理頁(UserKernel.allocatePages)時從freePages中出隊相應數(shù)量的頁面(返回的是物理頁號的數(shù)組)。整個需要裝入的進程是一個machine.Coff類型的對象,，它包括若干個段。每個段是一個machine.CoffSection類型的對象，它又包括若干個頁。Nachos中的虛擬地址是如下安排的：一個32位的地址，低10位是頁偏移量，高22位是頁號，頁號的安排如下：第1個段的第1個頁面的虛擬頁面號為0，第2個頁面的虛擬頁面號為1...第1個段完后，第2個段繼續(xù)按此方法編號。得到可用的物理頁號后,，就裝入所有的段。即為段中每個虛擬頁在pageTable中創(chuàng)建一個新的TranslationEntry對象并為其賦上相應的虛擬頁號和物理頁號等信息，然后調(diào)用CoffSection.loadPage將頁的內(nèi)容讀入。在進程結束時，UserProcess.unloadSections負責將所有段卸載。對于頁表中所有的頁面，只要將其虛擬頁號放入freePages隊列即可（UserKernel.releasePage）。UserProcess.readVirtualMemory讀虛擬內(nèi)存。它可以讀取任何虛擬地址開始的任意數(shù)目的字節(jié)(在進程可訪問的內(nèi)存范圍內(nèi))。首先，得32位虛擬頁號、偏移量。然后，獲得物理地址，最后寫入指定數(shù)組。類似地，UserProcess.writeVirtualMemory寫虛擬內(nèi)存，其方法與readVirtualMemory類似.只是注意取頁面時要檢查頁面是否為只讀。實現(xiàn)代碼publicstaticvoidreleasePage(intppn){pageLock.acquire();freePages.add(newInteger(ppn));pageLock.release();}publicstaticint[]allocatePages(intlen){ pageLock.acquire();int[]ppns=newint[len];for(inti=0;i<len;i++){ IntegerintO=(Integer)freePages.removeFirst(); if(intO==null){//空閑頁已取完 for(i--;i>=0;i--){ freePages.add(newInteger(ppns[i])); } pageLock.release(); returnnull; } ppns[i]=intO.intValue(); } pageLock.release(); returnppns;}privatestaticLockpageLock;privatestaticLinkedListfreePages;protectedbooleanloadSections(){ if(numPages>Mcessor().getNumPhysPages()){ coff.close(); Lib.debug(dbgProcess,"\tinsufficientphysicalmemory"); returnfalse; } int[]ppns=UserKernel.allocatePages(numPages); if(ppns==null){ coff.close(); Lib.debug(dbgProcess,"\tinsufficientphysicalmemory"); returnfalse; }pageTable=newTranslationEntry[numPages]; for(ints=0;s<coff.getNumSections();s++){CoffSectionsection=coff.getSection(s); Lib.debug(dbgProcess,"\tinitializing"+section.getName()+"section("+section.getLength()+"pages)"); for(inti=0;i<section.getLength();i++){ intvpn=section.getFirstVPN()+i; intppn=ppns[vpn]; pageTable[vpn]=newTranslationEntry(vpn,ppn,true,section.isReadOnly(),false,false); section.loadPage(i,ppn); } } returntrue; }publicintreadVirtualMemory(intvaddr,byte[]data,intoffset,intlength){ Lib.assertTrue(offset>=0&&length>=0&&offset+length<=data.length); byte[]memory=Mcessor().getMemory();//pageSize*getNumPhysPages(). intbyteNum=0; do{ intpageIndex=Processor.pageFromAddress(vaddr+byteNum); if(pageIndex<0||pageIndex>=pageTable.length) return0; intpageOffset=Processor.offsetFromAddress(vaddr+byteNum); intbytesLeftInPage=pageSize-pageOffset; intbytesToRead=Math.min(bytesLeftInPage,length-byteNum); intphysicalAddr=Processor.makeAddress(pageTable[pageIndex].ppn,pageOffset); System.arraycopy(memory,physicalAddr,data,offset+byteNum,bytesToRead); byteNum+=bytesToRead; }while(byteNum<length); returnbyteNum;}publicintwriteVirtualMemory(intvaddr,byte[]data,intoffset,intlength){ Lib.assertTrue(offset>=0&&length>=0&&offset+length<=data.length); byte[]memory=Mcessor().getMemory(); intbyteNum=0; do{ intpageIndex=Processor.pageFromAddress(vaddr+byteNum); if(pageIndex<0||pageIndex>=pageTable.length||pageTable[pageIndex].readOnly) return0; intpageOffset=Processor.offsetFromAddress(vaddr+byteNum); intbytesLeftInPage=pageSize-pageOffset; intbytesToWrite=Math.min(bytesLeftInPage,length-byteNum); byteNum+=bytesToWrite; }while(byteNum<length); byteNum=0; do{ intpageIndex=Processor.pageFromAddress(vaddr+byteNum); intpageOffset=Processor.offsetFromAddress(vaddr+byteNum); intbytesLeftInPage=pageSize-pageOffset; intbytesToWrite=Math.min(bytesLeftInPage,length-byteNum); intphysicalAddr=Processor.makeAddress(pageTable[pageIndex].ppn,pageOffset); System.arraycopy(data,offset+byteNum,memory,physicalAddr,bytesToWrite); byteNum+=bytesToWrite; }while(byteNum<length);returnbyteNum;}Task2.3要求實現(xiàn)系統(tǒng)調(diào)用exec,join,exit分析這三個系統(tǒng)調(diào)用與進程調(diào)度有關。其中：exec啟動一個新的進程；join與線程中的join操作類似，等待某進程結束后當前線程繼續(xù)；exit退出當前進程。需要注意的是：父進程和子進程不共享任何的內(nèi)存，文件或其它狀態(tài)。只有父進程能對子進程進行join操作。例如A執(zhí)行B，B執(zhí)行C，則A不允許joinC，而B允許joinC。需要為每個進程分配一個唯一的進程編號。exit操作將使當前進程立即結束，如果父進程對其進行join操作，返回代碼應返回。(5)最后一個調(diào)用exit的進程將使系統(tǒng)停機。方案exec系統(tǒng)調(diào)用在該系統(tǒng)調(diào)用中,第一個參數(shù)為文件名地址,第二個參數(shù)為參數(shù)個數(shù),第三個參數(shù)為參數(shù)表指針.需要做的工作是:讀虛擬內(nèi)存獲得文件名處理參數(shù).首先用第三個參數(shù)作為虛擬內(nèi)存地址得到參數(shù)表數(shù)組的首址,然后用readVirtualMemoryString依次讀出每個參數(shù)用UserProcess.newUserProcess創(chuàng)建子進程,將子進程加入到父進程私有的一個HashSet中用saveState保存當前進程狀態(tài)用UserProcess.execute方法執(zhí)行子進程返回子進程編號join系統(tǒng)調(diào)用該系統(tǒng)調(diào)用中,第一個參數(shù)為子進程編號,第二個參數(shù)一個地址,用于保存子進程的返回值.需要做的工作是:檢查childProcesses,如果子進程編號不在其中則出錯返回如果子進程編號在childProcesses中卻不在globalProcesses中,說明子進程已經(jīng)運行結束,則也返回并從childProcesses中移出該子進程在子進程的joinSignal上執(zhí)行P操作掛起當前進程(需要在exit系統(tǒng)調(diào)用中增加對當前線程的joinSignal進行V操作)等子進程返回時,得到返回代碼將其寫入第二個參數(shù)表示的地址中exit系統(tǒng)調(diào)用該系統(tǒng)調(diào)用的唯一參數(shù)為返回值.需要做的工作為:關閉所有打開的文件調(diào)用unloadsections釋放內(nèi)存從globalProcesses中移出當前進程編號如果是最后一個進程(globalProcesses為空)調(diào)用Kernel.kernel.terminate()停機調(diào)用KThread.finish方法結束當前線程(在Nachos中每個用戶進程只有一個線程)實現(xiàn)代碼privateinthandleExec(Stringfile,String[]argv){ UserProcessprocess=UserProcess.newUserProcess(); intPID=UserProcess.GenerateID(); process.SetProcessID(PID); ChildProcess.put(PID,process); if(!process.execute(file,argv)) return-1; ProcessAlive++; retur