操作系统nachos课程设计实验报告.doc

一 题目project1：实现nachos操作系统的project1中的join（）方法，condition2类，Alarm类,Communicator类,PriorityScheduler类和Boat类project2：实现nachos操作系统的project2中的creat open read write close unlink 文件系统调用，修改UserProcess.readVirtualMemory 和UserProcess.writeVirtualMemory使操作系统能够运行多用户程序，实现exec join exit系统调用，实现LotteryScheduler类二 实验目的 熟悉nachos操作系统，深入理解操作系统内核了解用户程序的加载过程以及多用户进程的内存分配机制三 实验要求 完成nachos，提交设计文档和你的代码四 实验说明，程序代码及测试结果Project1：1 join()要求实现join（）方法，注意，其他线程没必要调用join函数，但是如果它被调用的话，也只能被调用一次。join（）方法第二次调用的结果是不被定义的，即使第二次调用的线程和第一次调用的线程是不同的。无论有没有被join，一个进程都能够正常结束（a） 设计思想当线程B执行A.join()时，将B放入A的等待队列，直到A完成时，唤醒在等待队列中的所有线程，因此需要实现join（）方法和修改finish方法（b） 源代码 public void join() Lib.debug(dbgThread, Joining to thread: + toString();Lib.assertTrue(this != currentThread);Lib.assertTrue(join_counter = 0);join_counter+;boolean status = Merrupt().disable();if (this.status != statusFinished) waitQueue.waitForAccess(KThread.currentThread(); currentThread.sleep();Merrupt().restore(status); public static void finish() Lib.debug(dbgThread, Finishing thread: + currentThread.toString();Merrupt().disable();Machine.autoGrader().finishingCurrentThread();Lib.assertTrue(toBeDestroyed = null);toBeDestroyed = currentThread;currentThread.status = statusFinished; KThread thread = currentThread().waitQueue.nextThread();if (thread != null)thread.ready();sleep();（c） 程序截图线程1每次执行打出执行的次数，每次执行过后放弃cpu，线程2打出successful，线程2执行thread1.join().通过截图可以看出代码正确2 Condition2通过使用开关中断提供原子性来直接实现条件变量，我们利用信号量提供了一个简单的实现方式，你的工作就是不直接使用信号量提供相同的实现（你或许使用锁，即使它们也间接的使用了信号量）。一旦你实现了 ，你将会有两种可选择的实现方式来提供相同的功能。你的第二种条件变量的实现必须放在Condition2中（a）设计思想Condition2是对使用该条件变量的线程进行管理，所以要把在这个条件变量上等待的进程储存起来，因此可以使用一个队列。sleep()方法是把等待该条件变量的线程阻塞，放入等待队列，直到执行了wake（）并且获得cpu才能继续执行，执行步骤：关中断，释放锁，把线程放入等待队列，获得锁，开中断 。wake（）方法是把条件变量中的线程移出，放入就绪队列。执行步骤：关中断，线程移出等待队列移入就绪队列，开中断wakeAll（）方法是将条件变量中的所有线程移出，移入就绪队列（b）源代码public void sleep() Lib.assertTrue(conditionLock.isHeldByCurrentThread(); boolean status=Merrupt().disable();conditionLock.release(); waitqueue.waitForAccess(KThread.currentThread(); KThread.currentThread().sleep(); conditionLock.acquire();Merrupt().restore(status); public void wake() Lib.assertTrue(conditionLock.isHeldByCurrentThread();boolean status=Merrupt().disable();KThread thread=waitqueue.nextThread();if (!(thread=null) thread.ready();Merrupt().restore(status); public void wakeAll() Lib.assertTrue(conditionLock.isHeldByCurrentThread();boolean status=Merrupt().disable();KThread thread=waitqueue.nextThread();while(!(thread=null) thread.ready();thread=waitqueue.nextThread();Merrupt().restore(status);（c）程序截图 线程1线程 2分别请求锁和条件变量，然后释放锁和条件变量，图中可以看出代码正确 3 Alarm类 实现Alarm类，线程调用waitUntil方法之后会终止，直到传入的时间之后才可以执行。线程没必要在等待的时间之后立刻执行，只是把它放入ready队列，等待分配cpu。可以使用一个线程队列，但是不能产生额外的线程。（a） 设计思想waitUntil（）方法使用了一个队列可以存放线程以及唤醒时间，这个队列以时间为序的有序队列。每次调用时，把当前线程和唤醒时间加入队列，等待唤醒。timerInterrupt（）方法在每一次timer产生时间中断时遍历队列，检查队列中的时间状态，当线程到了等待的时间就把线程从队列中取出放入就绪队列。KThreadWakeTime类是一个内部类用于联系线程和唤醒时间（b） 源代码public void waitUntil(long x) boolean status = Merrupt().disable();long waketime = Machine.timer().getTime() + x;KThreadWakeTime kthreadwaketime = new KThreadWakeTime(KThread.currentThread(), waketime);int size = linkedlist.size();if (size = 0)linkedlist.add(kthreadwaketime);elsefor (int i = 0; i size; i+) if (waketime = linkedlist.get(i).getWakeTime()linkedlist.add(i + 1, kthreadwaketime);KThread.currentThread().sleep();Merrupt().restore(status);public void timerInterrupt() boolean status = Merrupt().disable();long currenttime = Machine.timer().getTime();int size = linkedlist.size();if (size = 0);elsefor (int i = 0; i size; i+) if (currenttime linkedlist.get(i).getWakeTime();else KThread thread = linkedlist.get(i).getThread();thread.ready();linkedlist.remove(i);size-;i = 0;currenttime = Machine.timer().getTime();KThread.currentThread().yield();Merrupt().restore(status);public class KThreadWakeTime private KThread thread = null;private long waketime = 0;public KThreadWakeTime(KThread thread, long waketime) this.thread = thread;this.waketime = waketime;public KThread getThread() return thread;public long getWakeTime() return waketime;（c）程序截图创建一个线程在70时中止，等待500后唤醒。图中可以看出代码正确4 Communicator 利用条件变量编写发送和接收一个消息来实现Communicator类的speak（）和listen（）方法。speak（）要自动等待listen（）被调用，然后将消息传递给listen（）。同样的listen（）也要自动等待speak（）被调用，将消息传递给自己才能收到一个消息。只有消息从speak（）传递到了listen（）两个线程才能返回。在只有一个Communicator对象时也能工作起来，不能拥有缓冲区，也就是说listen（）和speak（）只有成功配对之后才能传递消息。（a）设计思想speak（）：先获得锁，然后进行判断，如果没有听者等待，就要把说者放入队列然后睡眠。如果有听者等待，就要唤醒一个听者，然后传递消息，最后释放锁。listen（）：先获得锁，然后进行判断，如果没有说者等待，就要把听者放入队列然后睡眠。如果有说者等待，就要唤醒一个说者，然后传递消息，最后释放锁。（b）public Communicator() lock=new Lock(); queue=new LinkedList(); speaker=new Condition2(lock); listener=new Condition2(lock); word=0; speakercount=0; listenercount=0; public void speak(int word) boolean intStatus = Merrupt().disable(); lock.acquire(); if(listenercount=0) speakercount+; queue.offer(word); speaker.sleep(); listener.wake(); speakercount-; else queue.offer(word); listener.wake(); lock.release(); Merrupt().restore(intStatus); return; public int listen() boolean intStatus = Merrupt().disable(); lock.acquire(); if(speakercount!=0) speaker.wake(); listener.sleep(); else listenercount+; listener.sleep(); listenercount-; lock.release(); Merrupt().restore(intStatus); return queue.poll(); （c） 程序截图线程1和线程2分别调用speak（）将20,30传递，线程3和线程4调用listen（）将消息接收。线程1和线程2执行时没有听者，双双等待，证明程序在多个说者和听者时也能工作的很好5 PriorityScheduler类通过完成实现PriorityScheduler优先级调度策略。所有的调度程序都是继承自Scheduler类，所以必须实现getPriority(), getEffectivePriority()和setPriority()方法。在调度中必须选择有效优先级最长的执行，如果有效优先级相同的线程都在等待要选择等待时间最长的。解决优先级问题的关键就是优先级反转，当一个高优先级的线程等待一个低优先级的线程时，高优先级的线程就必须把自己的有效优先级捐献给低优先级的线程，让低优先级的线程提高优先级可以尽快执行。解决这个问题的关键就是计算有效优先级，但是计算时间不能太长，所以在改变优先级的时候在计算比较合适。优先级在捐献之后不会丢失。优先级可以不断传递下去。（a） 设计思想在引入优先级的同时就需要引入一个ThreadState对象，它用来把线程和优先级绑定在一起。而且内部还有一个队列用来记录等待它的线程。在执行getEffectivePriority（）方法时，要遍历整个队列，将等待它线程的最高有效优先级取出，和自己的优先级比较，把最大的当成自己的最高有效优先级。而在遍历的过程中，如果线程还有等待的线程还要计算自己的有效优先级，所以这是一个递归搜索的过程。而在队列类中最重要的就是nextThread（）方法，它返回下一个要执行的线程。这个方法通过遍历队列，计算出所有线程的有效优先级，取出有效优先级最大的线程执行。（b） 源代码public int getEffectivePriority() effectivepriority=-1;for(int i=0;ieffectivepriority)effectivepriority=waitQueue.waitQueue.get(i).getEffectivePriority();if(effectiveprioritypriority)setPriority(effectivepriority);return priority;public KThread nextThread() Lib.assertTrue(Merrupt().disabled(); int max=-1; index=0; ThreadState state=null,temp=null; while(temp=pickNextThread()!=null) if(temp.getEffectivePriority()max)state=temp; max=temp.getEffectivePriority(); if(state=null) return null; else return waitQueue.remove(waitQueue.indexOf(state).thread; protected ThreadState pickNextThread() if(indexwaitQueue.size()index+; return waitQueue.get(index-1); return null;（c） 程序截图 创建三个线程thread1，thread2,thread3,分别赋予优先级为2,4,6，thread3中调用了thread1.join（）。运行之后，thread1得到了thread3的优先级，有效优先级最高，最先执行，当thread1执行完成之后，thread3的优先级最高，第二执行，thread2优先级最低最后执行。6 Boat 使用条件变量解决过河问题。O岛有一群人要到M岛去，但是只有一艘船，这艘船一次只能带一个大人或者两个孩子。开始必须假设至少有两个孩子（否则问题无法解决），每一个人都会划船。要为每个大人和孩子创建一个线程，这个线程就相当于一个人，他们能自己判断（思考），什么时候可以过河，而不是通过调度程序的调度。在解决问题的过程中不能出现忙等待，而且问题最终一定要解决。不符合逻辑的事情不能发生，比如在这个岛的人能知道对面岛的情况。（a） 设计思想 创建两种类型的线程大人线程和孩子线程，他们分别执行不同的行为。船设置成为条件变量，人的位置，该大人还是孩子走，船是否在一个岛上设置成为布尔变量，将问题建模为数学问题。大人进程：首先要获得锁，然后进行判断是否是大人要走，船是否在这个岛上，如果不成立大人就要等待直到成立然后大人过河，改变变量的值，到达对岸之后唤醒一个孩子把穿开回来孩子进程：首先要获得锁，首先判断是在哪个岛上；若在O岛，则判断运输过程是否已经结束，要是结束就不执行任何操作，要是没结束，判断是否是孩子走，船是否在这个岛上，如果不成立，孩子就要等待直到成立，两个孩子过河，改变变量的值，并且还要把是否结束的信息传递过来。如果结束不做任何操作，否则唤醒一个孩子进程把船开回去；若在M岛，则孩子直接过河，并且根据获得信息要求下一次是大人还是孩子过河。（b） 源代码public static void begin(int adults, int children, BoatGrader b) bg = b;parentThread = KThread.currentThread();for (int i = 0; i adults; i+)new KThread(new Runnable() public void run() AdultItinerary();).fork();for (int i = 0; i 15|fileDescriptor0|openfilefileDescriptor=null) return -1; byte temp=new bytelength; int readNumber=openfilefileDescriptor.read(temp, 0, length); if(readNumber15|fileDescriptor0|openfilefileDescriptor=null) return -1/文件未打开,出错 byte temp=new bytelength; int readNumber=readVirtualMemory(bufferAddress, temp); if(readNumber=0) return 0;/没读出数据 int writeNumber=openfilefileDescriptor.write(temp, 0, length); if(writeNumber15|fileDescriptor0|openfilefileDescriptor=null) return -1;/文件不存在，关闭出错openfilefileDescriptor.close();openfilefileDescriptor=null;return 0;private int handleUnlink(int fileAddress) String filename=readVirtualMemoryString(fileAddress,256);if(filename=null)return 0;if(ThreadedKernel.fileSystem.remove(filename) return 0;else return -1;private int findEmpty()for(int i=0;i UserKernel.memoryLinkedList.size() coff.close();Lib.debug(dbgProcess, tinsufficient physical memory);UserKernel.allocateMemoryLock.release();return false;pageTable = new TranslationEntrynumPages;/ 创建页表for (int i = 0; i numPages; i+)int nextPage=UserKernel.memoryLinkedList.remove();pageTablei = new TranslationEntry(i, nextPage, true, false, false, false);UserKernel.allocateMemoryLock.release();for (int s = 0; s coff.getNumSections(); s+) CoffSection section = coff.getSection(s);Lib.debug(dbgProcess, tinitializing + section.getName()+ section ( + section.getLength() + pages);for (int i = 0; i = 0 & length = 0& offset + length (pageSize*numPages-vaddr)length=pageSize*numPages-vaddr; if(data.length-offsetlength)length=data.length-offset; int transferredbyte=0;doint pageNum=Processor.pageFromAddress(vaddr+transferredbyte);if(pageNum=pageTable.length) return 0; int pageOffset=Processor.offsetFromAddress(vaddr+transferredbyte); int leftByte=pageSize-pageOffset; int amount=Math.min(leftByte, length-transferredbyte); int realAddress=pageTablepageNum.ppn*pageSize+pageOffset; System.arraycopy(memory, realAddress, data, offset+transferredbyte, amount);transferredbyte=transferredbyte+amount;while(transferredbyte= 0 & length = 0& offset + length (pageSize*numPages-vaddr)length=pageSize*numPages-vaddr; if(data.length-offsetlength) length=data.length-offset;int transferredbyte=0;doint pageNum=Processor.pageFromAddress(vaddr+transferredbyte);if(pageNum=pageTable.length)return 0;int pageOffset=Processor.offsetFromAddress(vaddr+transferredbyte);int leftByte=pageSize-pageOffset;int amount=Math.min(leftByte, length-transferredbyte);int realAddress=pageTablepageNum.ppn*pageSize+pageOffset;System.arraycopy(data, offset+transferredbyte, memory, realAddress, amount);transferredbyte=transferredbyte+amount;while(transferredbytelength);return transferredbyte;3 exec join exit系统调用 寄存器传递的所有的参数都是内存的地址，所以需要读写内存来获得真正参数。孩子进程的状态是私有的，所以不能使用共享内存的方式。进程号可以做为参数传递给join方法用来指明父进程将要join哪一个孩子进程。最后一个执行exit的方法将关闭系统，但是直接调用Machine.halt().(a) 设计思想exec: 先从内存中将文件名读出，然后将参数表从内存中读出，创建一个新的用户进程，将文件和参数表加载到子进程，运行子进程，同时将这个子进程的父进程置为这个进程，再将子进程加入子进程列表。join:利用进程号确定join的是哪一个进程，先遍历子进程链表，确定join的进程是子进程，获得join锁，让该进程休眠，直到子进程唤醒，子进程唤醒之后将子进程的状态存入自己的内存中exit：首先关闭coff，然后将所有的打开文件关闭，把退出的状态置入，如果该进程有父进程，看是否执行了join方法，如果执行就将其唤醒，同时将本进程从子进程链表中删除，释放内存，结束底层线程，如果是最后一个结束的进程则将系统关闭（b） 源代码private int handleExec(int fileAddress, int argc, int argvAddres