山东大学计算机学院操作系统实验报告

操作系统课程设计 学院：计算机科学与技术学院专业：计算机科学与技术班级：20**级*班姓名：***学号：20**********目录实现代码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利用中断提供原子性，直接实现条件变量要求通过利用中断有效和无效所提供的原子性实现条件变量。我们已经提供类似的例子用例实现信号量。你要按此提供类似的条件变量的实现，不能直接利用信号量来实现（你可以使用lock，虽然它间接地调用了信号量）。在你完成时要提供条件变量的两种实现方法。你的第二种条件变量实现要放在nachos.threads.Condition2中。分析threads.Lock类提供了锁以保证互斥.在临界代码区的两端执行Lock.acquire()和Lock.release()即可保证同时只有一个线程访问临界代码区.条件变量建立在锁之上,由threads.Condition实现,它是用来保证同步的工具.每一个条件变量拥有一个锁变量(该锁变量亦可被执行acquire和release操作,多个条件变量可共享同一个锁变量).当处于临界区内的拥有某锁L的当前线程对与锁L联系的条件变量执行sleep操作时,该线程失去锁L并被挂起.下一个等待锁L的线程获得锁L(这个过程由调度程序完成)并进入临界区.当拥有锁L的临界区内的当前线程对与锁L联系的条件变量执行wake操作时(通常调用wake之后紧接着就是Lock.release),等待在该条件变量上的之多一个被挂起的线程(由调用sleep引起)被重新唤醒并设置为就绪状态.若执行wakeall操作,则等待在该条件变量上的所有被挂起的线程都被唤醒.方案condition.sleep采用waiter.P()实现休眠(waitor是一个信号量)并将waitor放入信号量队列,在我们的实现中改成用KThread.sleep()实现休眠并将当前线程放入线程队列,并在sleep函数开始/结尾处屏蔽/允许中断以保证原子性。condition.wake中从等待信号量队列中取出信号量并对其进行V操作实现唤醒,在我们的实现中改成从线程队列中取出线程用KThread.ready()实现唤醒(同样要在wake函数开始/结尾处屏蔽/允许中断)。wakeall函数的实现依赖于wake().只需不断地wake直到队列为空为止.实现代码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实现waitUntil要求通过实现waitUntil（intx）方法来完成Alarm类。分析一个线程通过调用waitUntil函数来挂起它自己，直到now+x后才被唤醒。在实时操作中，对线程是非常有用的，例如实现光标每秒的闪烁。这里并不要求线程被唤醒后马上执行它，只是在它等待了指定时间后将它。放入等待队列中。不要通过产生任何附加的线程来实现waitUntil函数，你仅需要修改waitUntil函数和时间中断处理程序。waitUntil函数并不仅限于一个线程使用，在任意时间，任意多的线程可以调用它来阻塞自己。方案于Alarm类有关的是machine.Timer类.它在大约每500个时钟滴答使调用回调函数(由Timer.setInterruptHandler函数设置).因此,Alarm类的构造函数中首先要设置该回调函数Alarm.timerInterrupt().为了实现waitUntil,需要在Alarm类中实现一个内部类Waiter,保存等待的线程及其唤醒时间.在调用waitUntil(x)函数时,首先得到关于该线程的信息:(线程:当前线程,唤醒时间:当前时间+x),然后构造新的Waiter对象,并调用sleep操作使当前线程挂起.在时钟回调函数中(大约每500个时钟间隔调用一次)则依次检查队列中的每个对象。如果唤醒时间大于当前时间,则将该对象移出队列并执行wake操作将相应线程唤醒。实现代码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();//线程进入就绪状态 } else waitlist.add(waiter);} KThread.currentThread().yield();}privateLinkedList<Waiter>waitlist;Task1.4用条件变量，不使用信号量，实现同步发送接收消息，speak，listen要求使用条件变量来实现一个字长信息的发送和接收同步。使用voidspeak(intword)和intlisten()函数来实现通讯（Communicator）类的通讯操作。speak函数具有原子性，在相同地Communicator类中等待listen函数被调用，然后将此字发生给listen函数。一旦传送完毕，两个函数都返回（listen函数返回此字）。分析对一个Communicator类的对象c,线程A先调用c.speaker(x)发送一个字后被挂起,直到另一线程B调用c.listen()收到这个字x后,A和B同时返回.类似地,线程B先调用c.listen(x)后被挂起,直到另一线程B调用c.speaker(x)发送一个字后,A和B同时返回.同时需要注意在一个Communicator上有多个spaker和listener的情形.此时的speaker和listener只能是一对一的,即一个speaker只能将数据发送到一个listener,一个listener也只能接收来自一个spekaer的数据,其余的speakers和listeners都需要等待.方案每个Communicator有一个锁(保证操作的原子性)和与该锁联系的两个条件变量用于保证speaker和listener间的同步.在speak函数中,首先检查若已经有一个speaker在等待(speaknum>0)或无listener等待,则挂起.否则设置变量,准备数据并唤醒一个listener.在listen函数中,增加一个listener后,首先唤醒speaker,然后将自己挂起以等待speaker准备好数据再将自己唤醒.这个问题其实是一个缓冲区长度为0的生产者/消费者问题.实现代码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实现优先级调度要求通过完成PriorityScheduler类在Nachos中实现优先级调度（priorityscheduling）。优先级调度是实时系统中的关键构建模块。分析在Nachos中,所有的调度程序都继承抽象类Scheduler.系统已经提供了一个简单的轮转调度器RoundRobinScheduler,它对所有线程不区分优先级而采用简单的FIFO队列进行调度.我们实现的优先级调度类PriorityScheduler也继承自Scheduler.优先级调度的传统算法如下:每个线程拥有一个优先级(在Nachos中,优先级是一个0到7之间的整数,默认为1).在线程调度时,调度程序选择一个拥有最高优先级的处于就绪状态的线程运行.这种算法的问题是可能出现“饥饿”现象:设想有一个低优先级的线程处于临界区中运行而高优先级的线程在临界区外等待.由于前者优先级较低,它可能不会被调度器选中从而高优先级的线程也不得不浪费时间等待.为解决上述优先级反转问题,需要实现一种“让出”优先级的机制(PriorityDonation):提高拥有锁的低优先级线程的优先级以使它迅速完成临界区,不使其它较高优先级的线程等待太久.提高后的优先级称为有效优先级,它可以不断变化.实际调度时就是以有效优先级为评判标准的.方案在ThreadState类中增加两个表即LinkedList<>类，存放的对象是PriorityQueue，即优先级队列对象。一个表用来记录该线程所占用资源的优先队列resourcesIHave，另一个表用来记录该线程所想占有的资源的优先队列resourceIWant。resourcesIHave作为发生优先级反转时，捐献优先级计算有效优先级的来源依据，resourceIWant用来为线程声明得到资源做准备。waitForAccess（）将需要等待获得资源的线程加入一个等待队列等待调度。getEffectivePriority（）计算有效优先级时，遍历等待队列中所用线程的有效优先级，找出最大的优先级即可。实现代码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要求用以上实现的线程互斥/同步机制解决一个过河问题。成人和小孩都试图从oahu出发到molokai。一只船只可以携带最多两个小孩或一个成人（但不能是一个小孩和一个成人）。船上可划回瓦胡岛，但这么做需要一个引航员。安排一个能让所有人到molokai岛的解决方案分析需要记录的信息:O岛上大人/小孩的人数M岛上大人/小孩的人数船的位置(在O岛还是M岛)船的状态(空/半满/全满)(半满指只有一个小孩,全满指有两个小孩或一个大人)初始状态:大人和小孩都在O岛上船在O岛船为空对于大人比较简单.若满足以下条件则独自乘船过河(每个大人过且仅过一次河,线程即告结束),否则(在O岛)等待:O岛上只有一个小孩或没有小孩船在O岛船为空对于小孩,分以下5种情况讨论某小孩在O岛,船在O岛,船为空,O岛上的小孩数大于等于2:该小孩上船等另外一个小孩上船后,两人一起划船过河到M某小孩在O岛,船在O岛,船为空,O岛上没有大人:该小孩上船过河某小孩在O岛,且不属于以上三种情况:等待某小孩在M岛,船在O岛:等待当所有的大人运完了之后开始运大人，当运过去两个大人后，O岛出现了两个孩子，这个时候这两个孩子划船过河，即使此时大人还没有完全被运送完全。返程：只有小孩可以有返程路线，大人返程没有意义。方案使用三个锁变量保证互斥,三个条件变量保证同步。实现代码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要求实现六个系统调用creat,open,read,write,close,unlink分析系统共提供了七个系统调用：halt(停机,已经提供)，creat(创建并打开磁盘文件)，open(打开磁盘文件)，read(读IO,可以是磁盘或屏幕)，write(写IO)，close(关闭IO)，unlink(删除磁盘文件)。要确保如下几点：稳定性,不能因为一个进程的非法系统调用就使操作系统崩溃,而应该返回错误代码。halt调用只能由第一个进程(rootprocess)执行。系统调用需要读写内存时,通过readVirtualMemory和writeVirtualMemory进行。文件名以null结尾,不超过256字符。如果系统调用出错,应返回-1。为每个打开的IO文件分配一个“文件描述符”,用整数表示.每个进程最多可以拥有16个。其中0和1应分配给标准输入和标准输出(即屏幕)，这由SynchConsole类管理。不同进程可以用相同的文件描述符处理不同的文件。Nachos已经提供了一个简单的文件系统FileSystem（Machine包中）,通过ThreadedKernel.fileSystem访问。系统不需要考虑文件访问的互斥等问题。方案create系统调用为了实现“文件描述符”,为每个进程开一张大小为16的数组(本地描述符表),下标为描述符编号,内容为文件对象(OpenFile类型,描述符未使用为null).此外,需要一个全局的Hashtable(全局文件表),key为文件名,value为该文件名被多少个进程打开。在Creat系统调用中，一般进行如下操作：用readVirtualMemoyString读取文件名通过UserKernel.fileSystem.open打开文件(第二个参数为true表示创建新文件)维护本地描述符表(返回一个内容为null的项目的下标作为描述符,将文件对象填入)维护全局文件表(如果全局表中没有此文件名,将(文件名,1)放入,否则将原来的元组的value加1)返回文件描述符open系统调用在Open系统调用中进行如下操作:从内存读取文件名通过UserKernal.fileSystem.open打开文件(第二个参数为false)维护本地描述符表维护全局文件表返回文件描述符read系统调用Read系统调用的三个参数依次为:文件描述符,写入的内存地址,读取的字节数。在Read系统调用中进行如下操作:从本地描述符表中得到文件对象通过OpenFile.read读取文件内容将文件内容写入内存返回写入内存的字节数write系统调用Write系统调用的三个参数依次为:文件描述符,读内存的地址,写入文件的字节数.在Write系统调用中进行如下操作:从本地描述符表中得到文件对象访问内存,得到要写入文件的内容通过OpenFile.write写文件返回写入文件的字节数close系统调用Close系统调用的唯一一个参数为文件描述符.在Close系统调用中进行如下操作:从本地描述符中得到文件对象通过OpenFile.close关闭文件从本地描述符表中移出文件对象从全局文件表中移出文件名的引用(若value为1,将其中的元组删除,否则将value减1)返回0unlink系统调用一般地，在Unlink调用中只需读取文件名并执行fileSystem.remove方法删除文件即可。但是，一个文件可能被多个进程打开而不能立即删除，必须等所有打开这个文件的进程都关闭该文件后才能删除。因此，在Unlink调用中还要检查文件名在全局文件表中的情况：若在全局文件表中不存在，则立即删除。否则，将文件名添加到删除队列中。这样，在Close系统调用中还要增加如下内容：若文件关闭后它在全局文件表中已经不存在且文件名在删除队列中，则此时执行删除文件操作，并将文件从删除文件中移出。halt系统调用调用Machine.halt之前先判断系统中是否还有进程在执行，若没有则停机。健壮性以上系统调用只是在一般情况下函数的执行流程。为了提高系统的健壮性,在系统调用中还要进行下列错误检查（-1表示出错）:文件名长度不得超过256字符,不得含有非法字符或空。打开,创建文件时,局部描述符表不能满,文件名不能在删除队列中.fileSystem的操作返回值必须正确。readVirtualMemory和writeVirtualMemory的返回值必须正确。实现代码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要求实现多进程内存分配和访问分析由于Nachos支持多道程序设计,所以理所当然地不同进程应分配完全不同的物理内存。Nachos不支持动态内存分配,所以需要分配的内存在装入程序时就可以确定了(代码,数据,堆栈部分)。故在装入程序时就为每个进程一次性分配固定的物理内存,在进程结束时收回它们。这里还需要实现如下简单的虚拟内存方案:每个进程的地址空间是连续的虚拟内存,但这些连续的虚拟页面在物理内存中却不一定是连续的。这个方案的简单之处在于,虚拟空间的总容量和物理空间的总容量相等,映射机制只是从虚拟内存到物理内存的一一映射。除了内存的分配,内存的读写也要体现出映射机制。方案系统提供了页表pageTable，它以虚拟页号为下标，其中的每个项目是一个machine.TranslationEntry类型的对象，它存放了一个页的下列信息：物理页号，虚拟页号，是否有效，是否只读，是否被用过，是否脏。在UserKernel中定义一个全局队列freePages用于存放当前空闲的物理页面号，一个保护全局队列的锁pageLock。开始时，freePages包括所有的物理页面。当启动新进程时,UserProcess.load负责从磁盘装入进程。其中需要我们完善的是过程UserProcess.loadSections。该过程完成如下操作：该进程需要的页面数已知，保存在numPage变量中。分配物理页(UserKernel.allocatePages)时从freePages中出队相应数量的页面(返回的是物理页号的数组)。整个需要装入的进程是一个machine.Coff类型的对象,，它包括若干个段。每个段是一个machine.CoffSection类型的对象，它又包括若干个页。Nachos中的虚拟地址是如下安排的：一个32位的地址，低10位是页偏移量，高22位是页号，页号的安排如下：第1个段的第1个页面的虚拟页面号为0，第2个页面的虚拟页面号为1...第1个段完后，第2个段继续按此方法编号。得到可用的物理页号后,，就装入所有的段。即为段中每个虚拟页在pageTable中创建一个新的TranslationEntry对象并为其赋上相应的虚拟页号和物理页号等信息，然后调用CoffSection.loadPage将页的内容读入。在进程结束时，UserProcess.unloadSections负责将所有段卸载。对于页表中所有的页面，只要将其虚拟页号放入freePages队列即可（UserKernel.releasePage）。UserProcess.readVirtualMemory读虚拟内存。它可以读取任何虚拟地址开始的任意数目的字节(在进程可访问的内存范围内)。首先，得32位虚拟页号、偏移量。然后，获得物理地址，最后写入指定数组。类似地，UserProcess.writeVirtualMemory写虚拟内存，其方法与readVirtualMemory类似.只是注意取页面时要检查页面是否为只读。实现代码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要求实现系统调用exec,join,exit分析这三个系统调用与进程调度有关。其中：exec启动一个新的进程；join与线程中的join操作类似，等待某进程结束后当前线程继续；exit退出当前进程。需要注意的是：父进程和子进程不共享任何的内存，文件或其它状态。只有父进程能对子进程进行join操作。例如A执行B，B执行C，则A不允许joinC，而B允许joinC。需要为每个进程分配一个唯一的进程编号。exit操作将使当前进程立即结束，如果父进程对其进行join操作，返回代码应返回。(5)最后一个调用exit的进程将使系统停机。方案exec系统调用在该系统调用中,第一个参数为文件名地址,第二个参数为参数个数,第三个参数为参数表指针.需要做的工作是:读虚拟内存获得文件名处理参数.首先用第三个参数作为虚拟内存地址得到参数表数组的首址,然后用readVirtualMemoryString依次读出每个参数用UserProcess.newUserProcess创建子进程,将子进程加入到父进程私有的一个HashSet中用saveState保存当前进程状态用UserProcess.execute方法执行子进程返回子进程编号join系统调用该系统调用中,第一个参数为子进程编号,第二个参数一个地址,用于保存子进程的返回值.需要做的工作是:检查childProcesses,如果子进程编号不在其中则出错返回如果子进程编号在childProcesses中却不在globalProcesses中,说明子进程已经运行结束,则也返回并从childProcesses中移出该子进程在子进程的joinSignal上执行P操作挂起当前进程(需要在exit系统调用中增加对当前线程的joinSignal进行V操作)等子进程返回时,得到返回代码将其写入第二个参数表示的地址中exit系统调用该系统调用的唯一参数为返回值.需要做的工作为:关闭所有打开的文件调用unloadsections释放内存从globalProcesses中移出当前进程编号如果是最后一个进程(globalProcesses为空)调用Kernel.kernel.terminate()停机调用KThread.finish方法结束当前线程(在Nachos中每个用户进程只有一个线程)实现代码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