2023年山東大學(xué)計(jì)算機(jī)學(xué)院操作系統(tǒng)實(shí)驗(yàn)報(bào)告

操作系統(tǒng)課程設(shè)計(jì)報(bào)告000000000000學(xué)院:計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：20**級(jí)*班姓名：*************規(guī)定線程被喚醒后立即執(zhí)行它,只是在它等待了指定期間后將它。放入等待隊(duì)列中。不要通過(guò)產(chǎn)生任何附加的線程來(lái)實(shí)現(xiàn)waitUnti1函數(shù),你僅需要修改waitUntil函數(shù)和時(shí)間中斷解決程序。waitUntil函數(shù)并不僅限于一個(gè)線程使用在任意時(shí)間，任意多的線程可以調(diào)用它來(lái)阻塞自己。.方案于Alarm類有關(guān)的是machine.Timer類.它在大約每500個(gè)時(shí)鐘滴答使調(diào)用回調(diào)函數(shù)(由Timer.se11nterruptHand1er函數(shù)設(shè)立).因此A1arm類的構(gòu)造函數(shù)中一方面要設(shè)立該回調(diào)函數(shù)Alarm.timerlnterrupt().為了實(shí)現(xiàn)waitUnti1,需要在Alarm類中實(shí)現(xiàn)一個(gè)內(nèi)部類Waiter,保存等待的線程及其喚醒時(shí)間在調(diào)用waitUntil(x)函數(shù)時(shí)，一方面得到關(guān)于該線程的信息：(線程：當(dāng)前線程，喚醒時(shí)間：當(dāng)前時(shí)間+x),然后構(gòu)造新的Waiter對(duì)象，并調(diào)用sleep操作使當(dāng)前線程掛起.在時(shí)鐘回調(diào)函數(shù)中(大約每500個(gè)時(shí)鐘間隔調(diào)用一次)則依次檢查隊(duì)列中的每個(gè)對(duì)象。假如喚醒時(shí)間大于當(dāng)前時(shí)間，則將該對(duì)象移出隊(duì)列并執(zhí)行wake操作將相應(yīng)線程喚醒。.實(shí)現(xiàn)代碼classWaiter(Waiter(1ongwakeTime,KThreadthread)(0this.wakeTime=wakeTime;0this.thread=thread;)private1ongwakeTime;privateKThreadthread;)pub1icvoidwaitUntil(longx)(booleanintStatus=Merrupt().disable();4ongwakeTime=Machine.timer().getTime()+x;Waiterwaiter=newWaiter(wakeTime,KThread.currentThread());owaitlist.add(waiter);System.out.println(KThread.currentThread().getName()。"線程休眠，時(shí)間為:"+1\/13為沿6上面6「().9?tTime()+”，應(yīng)當(dāng)在。"+wakeTime+“醒來(lái).”);oKThread.s1eep();Merrupt().restore(intStatus);)publicvoidtimerlnterrupt()Waiterwaiter;for(inti=0;i<waitlist.size();i++)?waiter=wai11ist.remove();df(waiter.wakeTime<=Machine.timer().getTime())(System.out.printin("喚醒線程:"+waiter.thread.getName()+",時(shí)間為:"+Machine.timer().getTimeO);。waiter.thread.ready();//線程進(jìn)入就緒狀態(tài)eIsewaitlist.add(waiter);)oKThread.currentThread().yield();)privateLinkedList<Waiter>waitlist;Taskl.4用條件變量，不使用信號(hào)量，實(shí)現(xiàn)同步發(fā)送接受消息，speak,Iisten1.規(guī)定使用條件變量來(lái)實(shí)現(xiàn)一個(gè)字長(zhǎng)信息的發(fā)送和接受同步。使用voidspeak(intword)和intlisten()函數(shù)來(lái)實(shí)現(xiàn)通訊(Communicator)類的通訊操作。speak函數(shù)具有原子性，在相同地Communicator類中檔待listen函數(shù)被調(diào)用，然后將此字發(fā)生給listen函數(shù)。一旦傳送完畢，兩個(gè)函數(shù)都返回(1isten函數(shù)返回此字I.分析對(duì)一個(gè)Communicator類的對(duì)象cz線程A先調(diào)用c.speaker(x)發(fā)送一個(gè)字后被掛起，直到另一線程B調(diào)用c.listen()收到這個(gè)字x后，A和B同時(shí)返回.類似地，線程B先調(diào)用c.1isten(x)后被掛起，直到另一線程B調(diào)用c.speaker(x)發(fā)送一個(gè)字后，A和B同時(shí)返回.同時(shí)需要注旨在一個(gè)Communicator上有多個(gè)spaker和listener的情形.此時(shí)的speaker和1istener只能是一對(duì)一的，即一個(gè)speaker只能將數(shù)據(jù)發(fā)送到一個(gè)Iistener,一個(gè)listener也只能接受來(lái)自一個(gè)spekaer的數(shù)據(jù)，其余的speakers和listeners都需要等待..方案每個(gè)Communicator有一個(gè)鎖(保證操作的原子性)和與該鎖聯(lián)系的兩個(gè)條件變量用于保證speakerIistener間的同步.在speak函數(shù)中,一方面檢查若已有一個(gè)speaker在等待(speaknum>0)或無(wú)listener等待，則掛起.否則設(shè)立變量，準(zhǔn)備數(shù)據(jù)并喚醒一個(gè)listener.在listen函數(shù)中,增長(zhǎng)一個(gè)listener后，一方面喚醒speaker,然后將自己掛起以等待speaker準(zhǔn)備好數(shù)據(jù)再將自己?jiǎn)拘?這個(gè)問(wèn)題其實(shí)是一個(gè)緩沖區(qū)長(zhǎng)度為0的生產(chǎn)者/消費(fèi)者問(wèn)題..實(shí)現(xiàn)代碼publicCommunicator()(lock=newLock();con=newCondition(lock);)publicvoidspeak(intword)(lock.acquireQ;if(speaknum>01|1istennum==0)(speaknum++;oc0n.sleep();)if(1istennum>0)(。con.wakeAl1();distennum=0;)this.word=word;System.out.prin11n(KThread.currentThread().getName()+"線程說(shuō)"+this.word);ock.re1ease();)pub1icintlisten()(lock.acquire();while(listennum>0||speaknum==O)(distennum++;^con.sleep();listennum--;)if(speaknum>0)(ocon.wake();speaknum--;)KThread.currentThread().yield();Systern.out.println(KThread.currentThread().getName()+”線程聽到"+this.w。rd);listennum=O;1ock.re1ease();?returnthis.word;)privateLocklock;privateConditioncon;privateintword;privatestaticintspeaknum;privatestaticintIistennum;Taskl.5完畢Pri。rityScheduler實(shí)現(xiàn)優(yōu)先級(jí)調(diào)度.規(guī)定通過(guò)完畢PrioritySchedu1er類在Nachos中實(shí)現(xiàn)優(yōu)先級(jí)調(diào)度(priorityscheduling)o優(yōu)先級(jí)調(diào)度是實(shí)時(shí)系統(tǒng)中的關(guān)鍵構(gòu)建模塊。.分析在Nachos中，所有的調(diào)度程序都繼承抽象類Scheduler.系統(tǒng)已經(jīng)提供了一個(gè)簡(jiǎn)樸的輪轉(zhuǎn)調(diào)度器RoundRobinScheduler,它對(duì)所有線程不區(qū)分優(yōu)先級(jí)而采用簡(jiǎn)樸的FIFO隊(duì)列進(jìn)行調(diào)度.我們實(shí)現(xiàn)的優(yōu)先級(jí)調(diào)度類PrioritySchedu1er也Z嵌承自Scheduler.優(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)營(yíng).這種算法的問(wèn)題是也許出現(xiàn)〃饑餓"現(xiàn)象：設(shè)想有一個(gè)低優(yōu)先級(jí)的線程處在臨界區(qū)中運(yùn)營(yíng)而高優(yōu)先級(jí)的線程在臨界區(qū)外等待.由于前者優(yōu)先級(jí)較低，它也許不會(huì)被調(diào)度器選中從而高優(yōu)先級(jí)的線程也不得不浪費(fèi)時(shí)間等待.為解決上述優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題，需要實(shí)現(xiàn)一種"讓出"優(yōu)先級(jí)的機(jī)制(PriorityDonation):提高擁有鎖的低優(yōu)先級(jí)線程的優(yōu)先級(jí)以使它迅速完畢臨界區(qū)，不使其它較高優(yōu)先級(jí)的線程等待太久.提高后的優(yōu)先級(jí)稱為有效優(yōu)先級(jí)，它可以不斷變化.實(shí)際調(diào)度時(shí)就是以有效優(yōu)先級(jí)為評(píng)判標(biāo)準(zhǔn)的..方案SThreadState類中增長(zhǎng)兩個(gè)表即LinkedList<>類，存放的對(duì)象是PriorityQueue,即優(yōu)先級(jí)隊(duì)列對(duì)象。一個(gè)表用來(lái)記錄該線程所占用資源的優(yōu)先隊(duì)列resourcesIHave,另一個(gè)表用來(lái)記錄該線程所想占有的資源的優(yōu)先隊(duì)列resourceIWant0resourcesIHave作為發(fā)生優(yōu)先級(jí)反轉(zhuǎn)時(shí)，捐獻(xiàn)優(yōu)先級(jí)計(jì)算有效優(yōu)先級(jí)的來(lái)源依據(jù),res。urcelWant用來(lái)為線程聲明得到資源做準(zhǔn)備。waitForAccess()將需要等待獲得資源的線程加入一個(gè)等待隊(duì)列等待調(diào)度。getEffectivePriority()計(jì)算有效優(yōu)先級(jí)時(shí),遍歷等待隊(duì)列中所用線程的有效優(yōu)先級(jí)，找出最大的優(yōu)先級(jí)即可。.實(shí)現(xiàn)代碼publicvoidwaitForAccess(PriorityQueuewaitQueue)waitQueue.waitQueue.add(this.thread);if(IwaitQueue.transferPriority)waitQueue.lockHolder.effectivePriority=expiredEffectivePriority;)publicvoidacquire(PriorityQueuewaitQueue)(waitQueue.waitQueue.remove(this.thread);waitQueue.IockHo1der=this;waitQueue.lockHolder.effectivePriority=expiredEffectivePriority;waitQueue.1ockHolder.waiters=waitQueue;)pub1icintgetEffectivePriority()(if(effectivePriority!=expiredEffectivePriority)。returneffectivePriority;effeetivePriority=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；protectedstaticfina1intexpiredEffectivePriority=-1；

目錄TOC\o"1-5"\h\z實(shí)驗(yàn)平臺(tái)4Projectl線程系統(tǒng)4Taskl.l實(shí)現(xiàn)KThread.join()4.要求4.分析4.方案4.實(shí)現(xiàn)代碼4Taskl.2利用中斷提供原子性，直接實(shí)現(xiàn)條件變量6.要求6.分析6.方案7.實(shí)現(xiàn)代碼7\o"CurrentDocument"Taskl.3實(shí)現(xiàn)waitUntil9.要求9.分析9.方案10.實(shí)現(xiàn)代碼10\o"CurrentDocument"Taskl.4用條件變量，不使用信號(hào)量，實(shí)現(xiàn)同步發(fā)送接收消息，speak,listen12.要求12.分析13.方案13.實(shí)現(xiàn)代碼14\o"CurrentDocument"Taskl.5完成Priorityscheduler實(shí)現(xiàn)優(yōu)先級(jí)調(diào)度16.要求16.分析16.方案17.實(shí)現(xiàn)代碼173232323232三Project2多道程序設(shè)計(jì)protectedPriorityQueuewaiters=null;321.實(shí)1.2.求析案現(xiàn).322.3.4.isk：3233代碼36411.2.實(shí)2.3.(求析案現(xiàn).41423.4.42代碼43isk；511.2.3.實(shí)一求折案現(xiàn)5151514.代碼S3publicKThreadnextThread()(Lib.assertTrue(Merrupt().disabled());oif(pickNextThread()==nuII)。returnnull;oKThreadthread=pickNextThread().thread;getThreadState(thread).acquire(this);returnthread;)protectedThreadstatepickNextThread()(if(waitQueue.isEmpty())returnnull;0ThreadStatetoPick=getThreadState((KThread)waitQueue.getFirst());for(Iteratori=waitQueue.iterator();i.hasNext();)ThreadStatets=getThreadState((KThread)i.next())；if(ts.getEffectivePriority()>toPick.getEffectivePriorityO)toPick=ts;)returntoPick;)LinkedList<KThread>waitQueue=newLinkedList<KThread>();ThreadStatelockHo1der=null;Task1.6.規(guī)定用以上實(shí)現(xiàn)的線程互斥/同步機(jī)制解決一個(gè)過(guò)河問(wèn)題。成人和小孩都試圖從。ahu出發(fā)到molokai。一只船只可以攜帶最多兩個(gè)小孩或一個(gè)成人（但不能是一個(gè)小孩和一個(gè)成人）。船上可劃回瓦胡島，但這么做需要一個(gè)引航員。安排一個(gè)能讓所有人到m。1okai島的解決方案.分析需要記錄的信息：1）。島上大人/小孩的人數(shù)M島上大人/小孩的人數(shù)3）船的位置（在0島還是M島）4）船的狀態(tài)（空/半滿/全滿）（半滿指只有一個(gè)小孩，全滿指有兩個(gè)小孩或一個(gè)大人）初始狀態(tài)：1）大人和小孩都在。島上2）船在。島3）船為空對(duì)于大人比較簡(jiǎn)樸.若滿足以下條件則獨(dú)自乘船過(guò)河（每個(gè)大人過(guò)且僅過(guò)一次河，線程即告結(jié)束）,否則（在。島）等待：1）。島上只有一個(gè)小孩或沒有小孩2）船在。島3）船為空對(duì)于小孩，分以下5種情況討論1）某小孩在0島，船在。島，船為空，0島上的小孩數(shù)大于等于2:該小孩上船等此外一個(gè)小孩上船后，兩人一起劃船過(guò)河到M2）某小孩在。島，船在。島，船為空，0島上沒有大人：該小孩上船過(guò)河3）某小孩在。島，且不屬于以上三種情況：等待4）某小孩在M島，船在0島：等待5）當(dāng)所有的大人運(yùn)完了之后開始運(yùn)大人，當(dāng)運(yùn)過(guò)去兩個(gè)大人后Q島出現(xiàn)了兩個(gè)孩子，這個(gè)時(shí)候這兩個(gè)孩子劃船過(guò)河，即使此時(shí)大人還沒有完全被運(yùn)送完全。返程:只有小孩可以有返程路線，大人返程沒故意義。.方案使用三個(gè)鎖變量保證互斥，三個(gè)條件變量保證同步。.實(shí)現(xiàn)代碼packagenachos.threads;importnachos.ag.BoatGrader;pub1icclassBoat（taticBoatGraderbg;taticintchiIdrenOnOahu=0;taticintchildrenOnMolokai=0;staticintadu1tOnOahu=0;taticintadultOnMolokai=0;taticintpi1ot=0;staticbooleanover;staticLock1ock1;staticConditionchildrenWaitOnOahu;staticLockIock2;staticConditionadultWaitOnOahu;staticLocklock3;staticConditionchildrenReadyOnMolokai;publicstaticvoidbegin(intadults,intchi1dren,BoatGraderb)obg=b;Joek1=newLock();。childrenWaitOnOahu=newCondition(lock1);lock2=newLock();。adu1tWaitOnOahu=newCondition(1ock2);Jock3=newLock();^childrenReadyOnMolokai=newCondition(lock3);。for(inti=0;i<adults;i++)(“newKThread(newAdult(childrenWaitOnOahu,adu1tWaitOnOahu,childrenReadyOnMolokai)).setName("adult").fork();4or(inti=0;i<children-l;i++)onewKThread(newChild(childrenWaitOnOahu,adultWaitOnOahu,childrenReadyOnMolokai)).setName("child").fork();°)oKThreadt=newKThread(newChiId(chiIdrenWaitOnOahu,adultWaitOnOahuzchi1drenReadyOnMolokai));t.setName("child");4.fork();。KThread.currentThread().yield();。lockl.acquire();ochi1drenWaitOnOahu.wake();lockl.release();。t.join();)staticvoidAdu1titineraryQbg.initializeAdult();?adultOnOahu++;dock2.acquire();oadultWaitOnOahu.sleep();oobg.AduItRowToMolokai();^adultOnOahu—;oadultOnMo1okai++;?dock2.release();Iock3.acquire();childrenReadyOnMo1okai.wake();?dock3.release();)staticvoidChildItinerary()(bg.initializeChild();childrenOnOahu++;。lock1.acquire();echiIdrenWaitOnOahu.sleep();sIockl.releaseQ;whi1e(true)if(pilot!=1)。。if(chi1drenOnOahu>1)(1ockl.acquire();。chi1drenWaitOnOahu.wake();pilot=1;bg.Chi1dRowToMolokai();achildrenOnOahu-。?childrenOnMo1okai++;。oolockl.re1ease();。Iock3.acquire();。。childrenReadyOnMoIokai.sleepO;o^0|ock3.release();00Jelse(。。Jock2.acquireQ;”adu1tWaitOnOahu.wake();?oJock2.release();bg.AdultRideToMolokai();。。。。lockl.acquire();chi1drenWaitOnOahu.sleep();000000lockl.release();ocontinue;00)。}eIse(?if(adultOnOahu!=0){。。bg.ChildRideToMo1okai();o^childrenOnOahu—;。。childrenOnMolokai++;。。。Iock3.acquire();。0chiIdrenReadyOnMolokai.wake();Jock3.release();o?ooo|ock3.acquire();。。30chiIdrenReadyOnMolokai.sleep();。。1ock3.release();0)e1seooolock3.acquire();000over=true;。。。bg.ChildRideToMolokai();o。chiIdrenOnOahu--;。0chi1drenOnMolokai++;。。。hildrenReadyOnMo1okai.wakeAII();o。。。1ock3.release();oo}。}if(over==true){break;)o^else(pilot=3;abg.ChildRowToOahu();0chiIdrenOnOahu++;childrenOnMolokai--;continue;staticvoidSampleltinerary()(-System.out.printin("\n***Everyonepi1esontheboatandgoestoMolokai***");"bg.AdultRowToMolokai();obg.ChildRideToMolokai();◎bg.Adu1tRideToMolokai();。bg.ChildRideToMolokai();))privatestaticclassChildimplementsRunnable(ChiId(Conditionchi1drenWaitOnOahu,ConditionaduItWaitOnOahu,ConditionchildrenReadyOnMolokai)(。this.location_now=Iocation_now;othis.childrenWaitOnOahu=chi1drenWaitOnOahu;0this.adu1tWaitOnOahu=adu1tWaitOnOahu;this.chiIdrenReadyOnMolokai=childrenReadyOnMolokai；)0pub1icvoidrun()(oChildltinerary();)privateintStatus;privateintIocation_now;//1:0ahu,2:Mo1okaiprivateConditionchiIdrenWaitOnOahu;privateConditionadu1tWaitOnOahu;privateConditionchi1drenReadyOnMolokai;)privatestaticclassAdultimp1ementsRunnab1e(?Adult(ConditionchiIdrenWaitOnOahuzConditionaduItWaitOnOahu,Conditionchi1drenReadyOnMolokai)this.chi1drenWaitOnOahu=chiIdrenWaitOnOahu;。。ahis.adultWaitOnOahu=adultWaitOnOahu;-this,chiIdrenReadyOnMolokai=childrenReadyOnMoIokai；。publicvoidrun()(Adu11Itinerary();)privateConditionchiIdrenWaitOnOahu;oprivateConditionadultWaitOnOahu;oprivateConditionchildrenReadyOnMolokai;))三Project2多道程序設(shè)計(jì)Task2.1.規(guī)定實(shí)現(xiàn)六個(gè)系統(tǒng)調(diào)用creat,open,read,write,close,unlink.分析系統(tǒng)共提供了七個(gè)系統(tǒng)調(diào)用:halt（停機(jī)，已經(jīng)提供），ereat（創(chuàng)建并打開磁盤文獻(xiàn)）,。pen（打開磁盤文獻(xiàn)），read（讀10,可以是磁盤或屏幕》write（寫］。），dose（關(guān)閉10）,unlink（刪除磁盤文獻(xiàn)）。要保證如下幾點(diǎn)：1）穩(wěn)定性，不能由于一個(gè)進(jìn)程的非法系統(tǒng)調(diào)用就使操作系統(tǒng)崩潰，而應(yīng)當(dāng)返回錯(cuò)誤代碼。halt調(diào)用只能由第一個(gè)進(jìn)程（rootprocess）執(zhí)行。3）系統(tǒng)調(diào)用需要讀寫內(nèi)存時(shí)，通過(guò)readVirtualMemory和writeVirtualMemory進(jìn)行。4）文獻(xiàn)名以null結(jié)尾，不超過(guò)256字符。5）假如系統(tǒng)調(diào)用犯錯(cuò)，應(yīng)返回-1。6）為每個(gè)打開的10文獻(xiàn)分派一個(gè)"文獻(xiàn)描述符”，用整數(shù)表達(dá).每個(gè)進(jìn)程最多可以擁有16個(gè)。其中0和1應(yīng)分派給標(biāo)準(zhǔn)輸入和標(biāo)準(zhǔn)輸出（即屏幕），這由SynchConsole類管理。不同進(jìn)程可以用相同的文獻(xiàn)描述符解決不同的文獻(xiàn)。Nachos已經(jīng)提供了一個(gè)簡(jiǎn)樸的文獻(xiàn)系統(tǒng)FileSystem（Machine包中），通過(guò)ThreadedKernel.fileSystem訪問(wèn)。8）系統(tǒng)不需要考慮文獻(xiàn)訪問(wèn)的互斥等問(wèn)題。3.方案create系統(tǒng)調(diào)用為了實(shí)現(xiàn)"文獻(xiàn)描述符”，為每個(gè)進(jìn)程開一張大小為16的數(shù)組（本地描述符表），下標(biāo)為描述符編號(hào)，內(nèi)容為文獻(xiàn)對(duì)象（OpenFile類型,描述符未使用為null）.止匕外，需要一個(gè)全局的Hashtable（全局文獻(xiàn)表），key為文獻(xiàn)名，value為該文獻(xiàn)名被多少個(gè)進(jìn)程打開。在Creat系統(tǒng)調(diào)用中，一般進(jìn)行如下操作：a）用readVirtualMemoyString讀取文獻(xiàn)名b）通過(guò)UserKerneLfileSystem.open打開文獻(xiàn)（第二個(gè)參數(shù)為true表達(dá)創(chuàng)建新文獻(xiàn)）c）維護(hù)本地描述符表（返回一個(gè)內(nèi)容為null的項(xiàng)目的下標(biāo)作為描述符，將文獻(xiàn)對(duì)象填入）d）維護(hù)全局文獻(xiàn)表（假如全局表中沒有此文獻(xiàn)名，將（文獻(xiàn)名，1）放入，否則將本來(lái)的元組的value加1）e）返回文獻(xiàn)描述符open系統(tǒng)調(diào)用在0pen系統(tǒng)調(diào)用中進(jìn)行如下操作：a）從內(nèi)存讀取文獻(xiàn)名b）通過(guò)UserKernaI.fileSystem.open打開文獻(xiàn)（第二個(gè)參數(shù)為fa1se）c）維護(hù)本地描述符表d）維護(hù)全局文獻(xiàn)表e）返回文獻(xiàn)描述符read系統(tǒng)調(diào)用Read系統(tǒng)調(diào)用的三個(gè)參數(shù)依次為：文獻(xiàn)描述符，寫入的內(nèi)存地址,讀取的字節(jié)數(shù)。在Read系統(tǒng)調(diào)用中進(jìn)行如下操作:a）從本地描述符表中得到文獻(xiàn)對(duì)象b）通過(guò)OpenFile.read讀取文獻(xiàn)內(nèi)容c）將文獻(xiàn)內(nèi)容寫入內(nèi)存d）返回寫入內(nèi)存的字節(jié)數(shù)write系統(tǒng)調(diào)用Write系統(tǒng)調(diào)用的三個(gè)參數(shù)依次為：文獻(xiàn)描述符，讀內(nèi)存的地址，寫入文獻(xiàn)的字節(jié)數(shù).在Write系統(tǒng)調(diào)用中進(jìn)行如下操作：a）從本地描述符表中得到文獻(xiàn)對(duì)象b）訪問(wèn)內(nèi)存，得到要寫入文獻(xiàn)的內(nèi)容c）通過(guò)OpenFiIe.write寫文獻(xiàn)d）返回寫入文獻(xiàn)的字節(jié)數(shù)close系統(tǒng)調(diào)用Close系統(tǒng)調(diào)用的唯——個(gè)參數(shù)為文獻(xiàn)描述符.在C1ose系統(tǒng)調(diào)用中進(jìn)行如下操作：a）從本地描述符中得到文獻(xiàn)對(duì)象b）通過(guò)OpenFiIe.close關(guān)閉文獻(xiàn)c）從本地描述符表中移出文獻(xiàn)對(duì)象d）從全局文獻(xiàn)表中移出文獻(xiàn)名的引用（若value為L(zhǎng)將其中的元組刪除，否則將value減1）e）返回0unlink系統(tǒng)調(diào)用一般地，在Un1ink調(diào)用中只需讀取文獻(xiàn)名并執(zhí)行fileSystem.remove方法刪除文獻(xiàn)即可。但是，一個(gè)文獻(xiàn)也許被多個(gè)進(jìn)程打開而不能立即刪除，必須等所有打開這個(gè)文獻(xiàn)的進(jìn)程都關(guān)閉該文獻(xiàn)后才干刪除。因此，在Unlink調(diào)用中還要檢查文獻(xiàn)名在全局文獻(xiàn)表中的情況:若在全局文獻(xiàn)表中不存在,則立即刪除。否則，將文獻(xiàn)名添加到刪除隊(duì)列中。這樣，在C1。se系統(tǒng)調(diào)用中還要增長(zhǎng)如下內(nèi)容:若文獻(xiàn)關(guān)閉后它在全局文獻(xiàn)表中已經(jīng)不存在且文獻(xiàn)名在刪除隊(duì)列中，則此時(shí)執(zhí)行刪除文獻(xiàn)操作，并將文獻(xiàn)從刪除文獻(xiàn)中移出。halt系統(tǒng)調(diào)用調(diào)用Machine.haIt之前先判斷系統(tǒng)中是否尚有進(jìn)程在執(zhí)行，若沒有則停機(jī)。8)健壯性以上系統(tǒng)調(diào)用只是在一般情況下函數(shù)的執(zhí)行流程。為了提高系統(tǒng)的健壯性，在系統(tǒng)調(diào)用中還要進(jìn)行下列錯(cuò)誤檢查(-1表達(dá)犯錯(cuò))：a)文獻(xiàn)名長(zhǎng)度不得超過(guò)256字符，不得具有非法字符或空。b)打開，創(chuàng)建文獻(xiàn)時(shí)，局部描述符表不能滿，文獻(xiàn)名不能在刪除隊(duì)列中.fileSystem的操作返回值必須對(duì)的。readVirtualMemory和writeVirtualMemory的返回值必須對(duì)的。4.實(shí)現(xiàn)代碼privateinthandleCreate(Stringname)(OpenFiIefi1e=ThreadedKernel.fileSystem.open(name,true);。FD.put(FDCounter,file);4f(G1obalFileTable.containsKey(name))(。if(!Globa1Fi1eTable.get(name).status())(。Globa1FileTable.get(name).1ink();。qFD.put(FDCounter,fi1e);?elsereturn-1;°)else(GiobalFiIeTable.put(name,newFi1eRec(file));FD.put(FDCounterzfile);}o。returnFDCounter++;)privateinthand1eOpen(Stringname)OpenFilefile=ThreadedKerne1.fiIeSystem.open(name,false);if(fiIe==null)。return-1;)df(GlobalFileTable.containsKey(name))(oif(GiobalFileTable.get(name).status())(3oGloba1Fi1eTab1e.get(name).Iink();。oFD.put(FDCounter;file);6)?elsereturn-1;)e1se(?GlobalFileTable.put(name,newFileRec(file));FD.put(FDCounter,file);)^returnFDCounter++;)privateinthand1eRead(intFDnumber,intbuffer;intcount)(OpenFilefile=FD.get(FDnumber);"(file==null)turn-1;byte[]buf=newbyte[count];dntstat=file.read(buf,0,count);Jf(writeVirtuaIMemory(buffer;buf)!=count)oreturn-1;?returncount;)privateinthand1eWrite(intFDnumber,intbuffer,intcount)(OpenFilefiIe=FD.get(FDnumber);if(file==nu11)oreturn-1;obyte[]buf=newbyte[count];一實(shí)驗(yàn)平臺(tái)開發(fā)語(yǔ)言:Java開發(fā)工具:EclipseLuna操作系統(tǒng)：Ubuntul4.04ZProjectl建立線程系統(tǒng)Taskl.l實(shí)現(xiàn)KThread.join()1.規(guī)定實(shí)現(xiàn)ImplementKThreadJoin()函數(shù)。注意：其它的線程不必調(diào)用join函數(shù)，但是假如它被調(diào)用的話,也只能被調(diào)用一次。對(duì)j。in函數(shù)第二次調(diào)用的執(zhí)行結(jié)果是不被定義的(即使第二次調(diào)用的線程與第一次調(diào)用的線程不同工2.分析Join函數(shù)的作用即為等待某線程運(yùn)營(yíng)完畢.當(dāng)前線程(唯一個(gè)正在運(yùn)營(yíng)的線程)A調(diào)用另一個(gè)線程(處在就緒狀態(tài))B的join函數(shù)時(shí)(A和B在Nachos中均為KThread類型對(duì)象)，A被掛起，直到B運(yùn)營(yíng)結(jié)束后,join函數(shù)返回，A才干繼續(xù)運(yùn)營(yíng)。.方案原KThread的join()中的Lib.assertTrue(this!=currentThread)已經(jīng)實(shí)現(xiàn)線程只能調(diào)用一次join()方法，根據(jù)規(guī)定,在調(diào)用j。in()方法時(shí),讓當(dāng)前運(yùn)營(yíng)線程休眠，并將當(dāng)前運(yùn)營(yíng)的線程加入到一個(gè)阻塞隊(duì)列中。在線程結(jié)束時(shí),finish。函數(shù)循環(huán)喚醒所有被阻塞的線程。.實(shí)現(xiàn)代碼if(readVirtua1Memory(buffer;buf)!=count)return-1;?returncount;)privateinthandleClose(intFDnumber)[OpenFilefile=FD.get(FDnumber);?if(file==null)?Stringname=FD.get(FDnumber).getName();FD.remove(FDnumber);?！騁lobalFileTab1e.get(name).unlink();if(Gioba1FileTable.get(name).status()&&G1oba1FileTab1e.get(name).GetCount()==0)ooGIobalFileTable.get(name).GetFi1e().getFi1eSystem().remove(name);。file.close();return0;privateinthandleUn1ink(Stringname)(◎if(GlobalFi1eTabie.containsKey(name))(GlobaIFileTable.get(name).close();◎if(G1oba1FileTable.get(name).GetCount()==0)。Globa1FileTable.get(name).GetFile().getFi1eSystem().remove(name);°)。e1se(f(!UserKerne1.fileSystem.remove(name))return-1;)return0;)Task2.21.規(guī)定實(shí)現(xiàn)多進(jìn)程內(nèi)存分派和訪問(wèn).分析由于Nachos支持多道程序設(shè)計(jì),所以理所當(dāng)然地不同進(jìn)程應(yīng)分派完全不同的物理內(nèi)存。Nachos不支持動(dòng)態(tài)內(nèi)存分派，所以需要分派的內(nèi)存在裝入程序時(shí)就可以擬定了（代碼，數(shù)據(jù)，堆棧部分）。故在裝入程序時(shí)就為每個(gè)進(jìn)程一次性分派固定的物理內(nèi)存，在進(jìn)程結(jié)束時(shí)收回它們。這里還需要實(shí)現(xiàn)如下簡(jiǎn)樸的虛擬內(nèi)存方案：每個(gè)進(jìn)程的地址空間是連續(xù)的虛擬內(nèi)存，但這些連續(xù)的虛擬頁(yè)面在物理內(nèi)存中卻不一定是連續(xù)的。這個(gè)方案的簡(jiǎn)樸之處在于，虛擬空間的總?cè)萘亢臀锢砜臻g的總?cè)萘肯嗟龋成錂C(jī)制只是從虛擬內(nèi)存到物理內(nèi)存的一一映射。除了內(nèi)存的分派，內(nèi)存的讀寫也要體現(xiàn)出映射機(jī)制。.方案系統(tǒng)提供了頁(yè)表pageTabie,它以虛擬頁(yè)號(hào)為下標(biāo)，其中的每個(gè)項(xiàng)目是一個(gè)machine.Trans1ationEntry類型的對(duì)象,它存放了一個(gè)頁(yè)的下列信息：物理頁(yè)號(hào)，虛擬頁(yè)號(hào)，是否有效，是否只讀，是否被用過(guò)，是否臟。在UserKernel中定義一個(gè)全局隊(duì)列freePages用于存放當(dāng)前空閑的物理頁(yè)面號(hào)，一個(gè)保護(hù)全局隊(duì)列的鎖pageLocko開始時(shí),freePages涉及所有的物理頁(yè)面。當(dāng)啟動(dòng)新進(jìn)程時(shí)，UserProcess.load負(fù)責(zé)從磁盤裝入進(jìn)程。其中需要我們完善的是過(guò)程UserProcess.loadSectionso該過(guò)程完畢如下操作：1）該進(jìn)程需要的頁(yè)面數(shù)已知,保存在numPage變量中。分派物理頁(yè)（UserKernel.allocatePages）時(shí)從freePages中出隊(duì)相應(yīng)數(shù)量的頁(yè)面（返回的是物理頁(yè)號(hào)的數(shù)組I2）整個(gè)需要裝入的進(jìn)程是一個(gè)machine.Coff類型的對(duì)象〃它涉及若干個(gè)段。每個(gè)段是一個(gè)machine.CoffSection類型的對(duì)象，它又涉及若干個(gè)頁(yè)。Nachos中的虛擬地址是如下安排的：一個(gè)32位的地址低10位是頁(yè)偏移量，高22位是頁(yè)號(hào)，頁(yè)號(hào)的安排如下：第1個(gè)段的第1個(gè)頁(yè)面的虛擬頁(yè)面號(hào)為0,第2個(gè)頁(yè)面的虛擬頁(yè)面號(hào)為1...第1個(gè)段完后，第2個(gè)段繼續(xù)按此方法編號(hào)。3）得到可用的物理頁(yè)號(hào)后，，就裝入所有的段。即為段中每個(gè)虛擬頁(yè)在pageTab1e中創(chuàng)建一個(gè)新的TranslationEntry對(duì)象并為其賦上相應(yīng)的虛擬頁(yè)號(hào)和物理頁(yè)號(hào)等信息，然后調(diào)用CoffSection.1oadPage將頁(yè)的內(nèi)容讀入。4）在進(jìn)程結(jié)束時(shí),UserProcess.unloadSections負(fù)責(zé)將所有段卸載。對(duì)于頁(yè)表中所有的頁(yè)面，只要將其虛擬頁(yè)號(hào)放入freePages隊(duì)列即可（UserKernel.releasePageXUserProcess.readVirtualMemory讀虛擬內(nèi)存。它可以讀取任何虛擬地址開始的任意數(shù)目的字節(jié)（在進(jìn)程可訪問(wèn)的內(nèi)存范圍內(nèi)）。一方面，得32位虛擬頁(yè)號(hào)、偏移量。然后，獲得物理地址，最后寫入指定數(shù)組。類似地，UserProcess.writeVirtualMemory寫虛擬內(nèi)存,其方法與readVirtualMemory類似.只是注意取頁(yè)面時(shí)要檢查頁(yè)面是否為只讀。.實(shí)現(xiàn)代碼publicstaticvoidre1easePage（intppn）pageLock.acquire();freePages.add(newInteger(ppn));pageLock.release();)pub1icstaticint[]allocatePages(intIen)pageLock.acquire();int[]ppns=newint[1en];for(inti=0;i<1en;i++){。Integerinto=(Integer)freePages.removeFirst();"(into==null){〃空閑頁(yè)已取完。。for(i—;i>=0;i—){sfreePages.add(newInteger(ppns[i]));000J^^pageLock.release();。。returnnull;)0?ppns[i]=intO.intValue();)。pageLock.release();returnppns;)privatestaticLockpageLock;privatestaticLinkedListfreePages;protectedbooleanloadSections()(if(numPages>Mcessor().getNumPhysPages())(。coff.close();Lib.debug(dbgProcess,"\tinsufficientphysica1memory");^returnfalse;0)oint[]ppns=UserKeme1.allocatePages(numPages);if(ppns==nu11)(。coff.close();。Lib.debug(dbgProcess,"\tinsufficientphysicaImemory")；◎returnfalse;pageTable=newTranslationEntry[numPages];0for(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]=newTransiationEntry(vpn,ppn,true,section.isReadOn1y(),faIsezfaIse);?<>section.1oadPage。，ppn);?returntrue;。。)publicintreadVirtua1Memory(intvaddr;byte[]datazintoffset,int1ength)(Lib.assertTrue(offset>=0&&Iength>=0&&offset+length<=data.Iength);byte[]memory=Mcessor().getMemory();//pageSize*getNumPhysPages().dntbyteNum=0;0do(ointpagelndex=Processor.pageFromAddress(vaddr+byteNum);ooif(pageIndex<0||pagelndex>=pageTable.length)oreturn0;intpageOffset=Processor.offsetFromAddress(vaddr+byteNum);。intbytesLeftlnPage=pageSize-pageOffset;?intbytesToRead=Math.min(bytesLeftInPagezlength-byteNum);mintphysicalAddr=Processor.makeAddress(pageTable[pageIndex].ppn,pageOffset);System.arraycopy(memory,physicalAddi;data,offset+byteNum,bytesToRead);obyteNum+=bytesToRead;0)while(byteNum<Iength);returnbyteNum;publicintwriteVirtualMemory(intvaddr;byte[]datazintoffset,intlength)^Lib.assertTrue(offset>=0&&Iength>=0&&offset+length<=data.length);byte[]memory=McessorQ.getMemory();intbyteNum=0;0do(mintpageindex=Processor.pageFromAddress(vaddr+byteNum);o"if(pageIndex<0||pageindex>=pageTabIeJength||pageTable[pageindex].readOniy)。return0;intpageOffset=Processor.offsetFromAddress(vaddr+byteNum);EntbytesLeftlnPage=pageSize-pageOffset;◎intbytesToWrite=Math.min(bytesLeftInPage,length-byteNum);?byteNum+=bytesToWrite;0)while(byteNum<length);publicvoidjoin()Lib.debug(dbgThread,"Joiningtothread:"+toStringO);Lib.assertTrue(this!=currentThread);booleanintStatus=Merrupt().disab1e();if(status!=statusFinished)(waitForJoin.waitForAccess(currentThread);^KThread.sleepO;))publicstaticvoidfinish()(oLib.debug(dbgThread,"Finishingthread:"+currentThread.toString());Merrupt().disable();Machine.autoGrader().finishingCurrentThread();?Lib.assertTrue(toBeDestroyed==nuII);?toBeDestroyed=current!hread;。currentThread.status=statusFinished;byteNum=0;od。ointpagelndex=Processor.pageFromAddress(vaddr+byteNum);ointpageOffset=Processor.offsetFromAddress(vaddr+byteNum);intbytesLeftinPage=pageSize-pageOffset;ointbytesToWrite=Math.min(bytesLeftInPage,length-byteNum);intphysicaIAddr=Processor.makeAddress(pageTable[pagelndex].ppnzpageOffset);System.arraycopy(data,offset+byteNum,memory,physicalAddr,bytesToWrite);abyteNum+=bytesToWrite;)whi1e(byteNum<1ength);returnbyteNum;Task2.3.規(guī)定實(shí)現(xiàn)系統(tǒng)調(diào)用exec,join,exit.分析這三個(gè)系統(tǒng)調(diào)用與進(jìn)程調(diào)度有關(guān)。其中：exec啟動(dòng)一個(gè)新的進(jìn)程;join與線程中的join操作類似,等待某進(jìn)程結(jié)束后當(dāng)前線程繼續(xù);exit退出當(dāng)前進(jìn)程。需要注意的是：1）父進(jìn)程和子進(jìn)程不共享任何的內(nèi)存，文獻(xiàn)或其它狀態(tài)。2）只有父進(jìn)程能對(duì)子進(jìn)程進(jìn)行join操作。例如A執(zhí)行B,B執(zhí)行C,則A不允許joinC,而B允許joinCo3）需要為每個(gè)進(jìn)程分派一個(gè)唯一的進(jìn)程編號(hào)。exit操作將使當(dāng)前進(jìn)程立即結(jié)束，假如父進(jìn)程對(duì)其進(jìn)行j。in操作,返回代碼應(yīng)返回。（5）最后一個(gè)調(diào)用exit的進(jìn)程將使系統(tǒng)停機(jī)。.方案exec系統(tǒng)調(diào)用在該系統(tǒng)調(diào)用中，第一個(gè)參數(shù)為文獻(xiàn)名地址，第二個(gè)參數(shù)為參數(shù)個(gè)數(shù),第三個(gè)參數(shù)為參數(shù)表指針.需要做的工作是：a）讀虛擬內(nèi)存獲得文獻(xiàn)名b）解決參數(shù).一方面用第三個(gè)參數(shù)作為虛擬內(nèi)存地址得到參數(shù)表數(shù)組的首址，然后用readVirtualMemoryString依次讀出每個(gè)參數(shù)c）用UserProcess.newUserProcess創(chuàng)建子進(jìn)程，將子進(jìn)程加入到父進(jìn)程私有的一個(gè)HashSet中d）用saveState保存當(dāng)前進(jìn)程狀態(tài)e）用UserProcess.execute方法執(zhí)行子進(jìn)程f）返回子進(jìn)程編號(hào)join系統(tǒng)調(diào)用該系統(tǒng)調(diào)用中，第一個(gè)參數(shù)為子進(jìn)程編號(hào)，第二個(gè)參數(shù)一個(gè)地址，用于保存子進(jìn)程的返回值.需要做的工作是：a）檢查childProcesses,假如子進(jìn)程編號(hào)不在其中則犯錯(cuò)返回b）假如子進(jìn)程編號(hào)在childProcesses中卻不在globalProcesses中，說(shuō)明子進(jìn)程已經(jīng)運(yùn)營(yíng)結(jié)束，則也返回并從childProcesses中移出該子進(jìn)程c）在子進(jìn)程的joinSignal上執(zhí)行P操作掛起當(dāng)前進(jìn)程（需要在exit系統(tǒng)調(diào)用中增長(zhǎng)對(duì)當(dāng)前線程的j。inSignal進(jìn)行V操作）d）等子進(jìn)程返回時(shí)，得到返回代碼將其寫入第二個(gè)參數(shù)表達(dá)的地址中exit系統(tǒng)調(diào)用該系統(tǒng)調(diào)用的唯一參數(shù)為返回值.需要做的工作為：a）關(guān)閉所有打開的文獻(xiàn)b）調(diào)用unloadsections釋放內(nèi)存c）從globalProcesses中移出當(dāng)前進(jìn)程編號(hào)d）假如是最后一個(gè)進(jìn)程91。621「「€^，5ses為空）調(diào)用Kerne.kernel.terminate()停機(jī)e)調(diào)用KThread.finish方法結(jié)束當(dāng)前線程(在Nachos中每個(gè)用戶進(jìn)程只有一個(gè)線程).實(shí)現(xiàn)代碼privateinthandleExec(Stringfi1e,String[]argv)(。11serProcessprocess=UserProcess.newUserProcess();intPID=UserProcess.GenerateID();?process.SetProcessID(PID);?Chi1dProcess,put(PID,process);df(!process.execute(fi1e#argv))。return-1;ProcessA1ive++;?returnPID;)privateinthandleJoin(intPID,intaddr)(if(!ChiIdProcess.containsKey(PID))return-1;Chi1dProcess.get(PID).thread.join();if(Chi1dState.get(PID)==nuII)oreturn0;byte[]data={(byte)ChildState.get(PID).intValue()};writeVirtua1Memory(addrzdata);?return1;)privatevoidhandleExit(intstatus)(Lib.assertTrue(thread==KThread.currentThread());if(ParentProcess!=null)oParentProcess.ChildProcess.remove(GetProcessID());Iterator<UserProcess>ChiIdRemover=Chi1dProcess.values().iterator();whiIe(ChildRemover.hasNext())(ChiIdRemover.next().ParentProcess=null;)4terator<OpenFile>FDRemover=FD.values().iterator();whi1e(FDRemover.hasNextQ)FDRemover.next().close();oun1oadSections();if(ParentProcess!=null)oParentProcess.ChildState.put(GetProcessID(),status);0ProcessAlive—;4f(ProcessAlive==0)Kernel.kerneLterminate();KThread.finish();。Lib.assertNotReached("Cannotschedu1etheuserprocess"◎+thread.getName()+"toexit");)Task2.41.規(guī)定實(shí)現(xiàn)彩票調(diào)度2.分析彩票調(diào)度(LotterySchedule)和Task1.5的優(yōu)先級(jí)調(diào)度非常類似，只是下面兩點(diǎn)作了改變：〃優(yōu)先級(jí)〃的概念變成了〃彩票〃，即表達(dá)該線程下次被運(yùn)營(yíng)的幾率2)在調(diào)度過(guò)程中，并不是選擇彩票數(shù)最多的線程運(yùn)營(yíng),而是隨機(jī)抽取一張彩票,讓彩票的主人運(yùn)營(yíng)。這樣，彩票越多，下次得到的運(yùn)營(yíng)機(jī)會(huì)就越大。.方案我們只要修改PrioritySchedueler.java中的兩處即可實(shí)現(xiàn)彩票調(diào)度。一方面在getEffectivePriorityNachos中將選取最大優(yōu)先級(jí)的過(guò)程改成將所有等待線程的優(yōu)先級(jí)(彩票數(shù))力口至i」lockHolder±(即等待者把自己擁有的彩票給獲得鎖的線程)，另一方面將nextThread修改如下：一方面遍歷一遍隊(duì)列，計(jì)算出當(dāng)前隊(duì)列中的所有隊(duì)列的彩票總數(shù)(考慮過(guò)donation后的)numEffective,另一方面生成一個(gè)0至！］numEffective-1之間的隨機(jī)數(shù)randomLottery表達(dá)抽取的彩票最后再次遍歷一遍隊(duì)列，用累加器t計(jì)算彩票總數(shù)，當(dāng)t的當(dāng)前值大于rand0mLottery時(shí)說(shuō)明當(dāng)前循環(huán)到的線程正好落在目的區(qū)間內(nèi)，即選出該線程。.實(shí)現(xiàn)代碼pub1icintgetEffectivePriority()(if(effectivePriority!=expiredEffectivePriority)”eturneffectivePriority;effectivePriority=priority;?if(waitors==null)oreturneffectivePriority;00for(Iteratori=waitors.waitQueue.iterator();i.hasNext();)(。ThreadStatets=(ThreadState)getThreadState((KThread)i.next());◎effectivePriority+=ts.priority;)?returneffectivePriority;)pr