山东大学操作系统课设nachos(共58页).docx

精选优质文档-倾情为你奉上操作系统课程设计实验报告对Nachos系统的完善班级：计软13.4 分组：第八组 Phase 0一、写在前面二、需要明确的是：Run nachos à ThreadKernel is called to create nachos kernel à initialize() initializes nachos kernel à selfTest() tests this kernel à run() is supposed to run user programs latterSome Crucial requirements: 1. Only modify nachos.conf according to the project specifications.2. Do not modify any classes in the nachos.machine package, the nachos.ag package, or the nachos.security package.3. Do not add any new packages to your project.4. Do not modify the API for methods that the autograder uses.5. Do not directly use Java threads (the java.lang.Thread class).6. Do not use the synchronized keyword in any of your code.7. Do not directly use Java File objects (in the java.io package).Phase 1：Build a thread system for kernel processesTask 1.1Implements Join() method一、问题描述1. Note that another thread does not have to call join(), but if it is called, it must be called only once.2. A thread must finish executing normally whether or not it is joined.二、解决方案线程B在线程A运行的过程中调用join方法，阻塞线程A的运行获取运行权，此时线程A等待线程B完成运行后重新运行。实现要求：1.每个线程拥有自己的waitJoinQueue，里面存放了由于自己的join而被阻塞无法执行的线程。2.由于我们对每个线程添加了waitJoinQueue切里面存有在等待的线程，故而我们需要修改finish函数，在线程完成运行即将终止时检查其waitJoinQueue，唤醒队列中在等待的线程。三、实现代码 1. 声明KThread.waitJoinQueue:public ThreadQueue waitJoinQueue;2.初始化KThread.waitJoinQueue:waitJoinQueue = ThreadedKernel.scheduler.newThreadQueue(true);注意这段代码在KThread构造器中，无论是否有currentThread都要有这段代码，这段代码应该出现两次3.Join()public void join() Lib.debug(dbgThread, "Joining to thread: " + toString(); Lib.assertTrue(this != currentThread); /*for join method*/ Lib.assertTrue(joinCounter = 0); joinCounter+; boolean intStatus = Machine.interrupt().disable(); if(this.status != statusFinished) /System.out.println(this.getName()+" in join "+currentThread.getName(); waitJoinQueue.waitForAccess(currentThread); currentThread.sleep(); Machine.interrupt().restore(intStatus); /*for join method*/ 4.finish()中添加的部分/*for join method*/ KThread t = currentThread.waitJoinQueue.nextThread(); if(t!=null) /System.out.println("currentThread: "+currentThread.getName()+" next thread: "+t.getName(); t.ready(); /*for join method*/四、方案总结1.waitJoinQueue的初始化要求在每个线程中都得到执行。因为之前没考虑到出现了错误这里特别说一下。2.Joincounter静态全局变量记录join方法被调用的次数以控制其满足题目要求3.一定要记得修改finish方法唤醒waitJoinQueue中等待的线程Task 1.2 Implement condition variables directly一、问题描述1. Provide atomicity by using interrupt enable and disable.2. Provide an equivalent implementation without directly using semaphores (you may of course still use locks, even though they indirectly use semaphores).3. Your second implementation of condition variables must reside in class nachos.threads.Condition2.二、解决方案1. Lock conditionLock: 利用锁完成实现2.ThreadQueue waitQueue: 该条件变量等待的线程构成的队列3.sleep(): 其他线程在该条件变量上的等待即进入该条件变量的waitQueue陷入阻塞状态4.wake(): 唤醒该条件变量中等待的某个线程5.wakeAll(): 即对wake()方法的循环调用，直到队列中没有线程为止三、实现代码1.相关变量private Lock conditionLock;private ThreadQueue waitQueue;他们在构造器中完成初始化public Condition2(Lock conditionLock) this.conditionLock = conditionLock; waitQueue = ThreadedKernel.scheduler.newThreadQueue(true); 2.sleep():public void sleep() Lib.assertTrue(conditionLock.isHeldByCurrentThread(); boolean intStatus = Machine.interrupt().disable();conditionLock.release();/System.out.println("-");waitQueue.waitForAccess(KThread.currentThread();KThread.currentThread().sleep();/System.out.println("+");conditionLock.acquire();/executed after waken upMachine.interrupt().restore(intStatus); 3.wake()public void wake() Lib.assertTrue(conditionLock.isHeldByCurrentThread(); boolean intStatus = Machine.interrupt().disable(); KThread t = waitQueue.nextThread(); if(t!=null) t.ready(); Machine.interrupt().restore(intStatus);4.wakeAll()public void wakeAll() Lib.assertTrue(conditionLock.isHeldByCurrentThread(); boolean intStatus = Machine.interrupt().disable(); KThread t = waitQueue.nextThread(); while(t!=null) t.ready(); t = waitQueue.nextThread(); Machine.interrupt().restore(intStatus);四、方案总结1. 我们采用ThreadQueue对象来实现等待队列而非简单的利用一个LInkedList，这样保证了这个队列的调度算法与调度器的一致性，也免除了自己在wake方法中到底wake哪个线程的纠结。2.ThreadQueue.nextThread对于队列中没有线程的情况返回null值，故我们通过检查它的返回值来确定队列里有没有线程。3.线程陷入阻塞之前放弃锁，恢复就绪状态再获取锁。Task 1.3 Complete the implementation of Alarm Class一、问题描述1. Implemente the waitUntil(long x) method.2. There is no requirement that threads start running immediately after waking up; just put them on the ready queue in the timer interrupt handler after they have waited for at least the right amount of time.3. Do not fork any additional threads to implement waitUntil().4. you need only modify waitUntil() and the timer interrupt handler. waitUntil is not limited to one thread.二、解决方案1.threadTime类: 我们要处理的是线程在某个时间点调用waitUntil方法等待一个时间间隔后重新开始执行的问题，在这个问题中，线程与时间紧密结合。ThreadTime类中将会保存线程信息以及线程应该被唤醒的时刻。2.LinkedList list: alarm中的等待序列，这个序列中保存了所有调用了waitUntil方法进入等待状态的线程的threadTime类。3.nachos系统每隔大概500个时间间隔会调用一次timerInterrupt()，于是我们在这个函数中检查list中等待的线程是否已经完成了等待，比较标准为当前系统时刻大于等于线程应该被唤醒的时刻4.waitUntil函数：在这个函数被线程调用后，调用时刻与函数接收的参数运算后得到线程应该被唤醒的时刻，如果这个时刻还没到达我们就把这个线程和他的唤醒时刻放到threadTime类中进入list中。三、实现代码1.一些相关变量：LinkedList list = new LinkedList();/used to store threadTime2.threadTime类：/*added*/ private class threadTime KThread thread = null; long time = 0; threadTime(KThread thread, long time) this.thread = thread; this.time = time; KThread getThread() return thread; long getTime() return time; 3.waitUntil函数public void waitUntil(long x) / for now, cheat just to get something working (busy waiting is bad) boolean intStatus = Machine.interrupt().disable(); long wakeTime = Machine.timer().getTime() + x; threadTime tt = new threadTime(KThread.currentThread(),wakeTime); if(wakeTime > Machine.timer().getTime() if(list.size()=0) list.add(tt); else for(int i=0;i<list.size();i+) if( (threadTime) list.get(i).getTime()>wakeTime) list.add(i,tt); else if(i=list.size()-1) list.add(i+1,tt); KThread.currentThread().sleep(); Machine.interrupt().restore(intStatus);4.timerInterrupt中检查list中线程是否等待完成的代码while(list.size()>0) long currentTime = Machine.timer().getTime(); for(int i=0;i<list.size();i+)/smaller index means earlier step into this queue, having wait a longer time in turn if(currentTime>=(threadTime) list.get(i).getTime() (threadTime) list.get(i).getThread().ready(); list.remove(i); i=0; currentTime = Machine.timer().getTime(); break; 四、方案总结1.线程进入等待的规律是：早调用waiUntil方法的线程早进入等待，如果同一时刻有两个线程都满足等待完成条件，由于早调用方法的线程更早进入等待序列，这意味着他等待了更久的时间，那么他会早一步离开等待序列，这满足了题目的要求。2.要检查调用函数的线程等待时间是不是已经过去了。Task 1.4 implement synchronous send and receive of one word message using condition variables一、问题描述1. Implement the Communicator class with operations, void speak(int word) and int listen().2. Neither thread may return from listen() or speak() until the word transfer has been made.3. Your solution should work even if there are multiple speakers and listeners for the same Communicator4. Each communicator should only use exactly one lock.二、解决方案按照题目中的线索我们应该利用条件变量完成相关功能。Communicator对象可以调用speak和listen方法进行通信。对于speak方法：首先检查是否有listener，如果没有就进入等待，如果有就唤醒listener把信息传递过去然后退出。对于listen方法：首先检查是否有speaker，如果没有就进入等待，如果有就唤醒speaker收听信息。对于communicator类，我们应该保存speaker和listener的条件变量，以及能说明两者数目的相关数值变量。三、实现代码1.相关变量：LinkedList words; Condition2 speaker; Condition2 listener; int num_speaker,num_listener,num_words;Lock lock;变量在构造器中的初始化 public Communicator() words = new LinkedList<Integer>(); lock = new Lock(); speaker = new Condition2(lock); listener = new Condition2(lock); num_words = 0; num_speaker = 0; num_listener = 0;2.speak()public void speak(int word) boolean status = Machine.interrupt().disable(); lock.acquire(); if(num_listener=0) words.add(word); speaker.sleep(); num_words+; num_speaker+; listener.wake(); else listener.wake(); words.add(word); num_listener-; System.out.println(KThread.currentThread().getName()+" speaked "+ word); lock.release(); Machine.interrupt().restore(status);3.listener()public int listen() boolean status = Machine.interrupt().disable(); lock.acquire(); if(num_speaker=0) num_listener+; speaker.wake(); listener.sleep(); else num_speaker-; speaker.wake(); listener.sleep(); lock.release(); Machine.interrupt().restore(status); System.out.println(KThread.currentThread().getName()+" listened "+ words.peek(); return (int) words.pop();四、方案总结1.可能由于对相关要求认识不够清晰明确，于题目要求的a zero-length bounded buffer不同，我们采用了一个链表来保存speaker想要传输的信息2.利用锁来保持操作的原子性，起到了操作互斥的作用3.当且仅当一次成功的信息传递完成时线程才可以退出。4.在我的实现中，要求speaker listener线程成对存在，与课上某些同学演示的不同。Task 1.5 implement priority scheduling in nachos一、问题描述1. Change a line in nachos.conf that specifies the scheduler class to use.2. You must implement the methods getPriority(), getEffectivePriority(), and setPriority().3. In choosing which thread to dequeue, the scheduler should always choose a thread of the highest effective priority. If multiple threads with the same highest priority are waiting, the scheduler should choose the one that has been waiting in the queue the longest.4. A partial fix for this problem is to have the waiting thread donate its priority to the low priority thread while it is holding the lock.5. Be sure to implement Scheduler.getEffectivePriority(), which returns the priority of a thread after taking into account all the donations it is receiving.6. The Lock class does not need to be modified.二、解决方案1.这部分我们处理的问题是线程调度的问题，调度的标准设置为线程的优先级，所以首先要在线程对象中完成对线程优先级修改的函数的实现，方便后面设置修改线程优先级完成试验的测试过程。KThread类中setPriority()和getPriority()以及getStatus()方法都是为了此次试验完成而设定。（getStatus再后来不断修改实现方式的过程中没有起到作用，不过一开始是想要利用它得到现成的ThreadState对象。）2.作为一个调度器，其中肯定少不了等待队列，这个队列应该用什么样的数据结构才能达到目的是一个问题。一开始的时候参照源代码(PriorityScheduler raw code)引入的包中含有HashSet和TreeSet两种数据结构，查阅资料刚发现HashSet在对象的存储添加方面颇有优势，而TreeSet则是能够自动按照指定的标准为结构内的对象进行排序。初步的认识过程中，我认为这个调度算法中的关键在于选择优先级最大的线程赋予其执行权，而TreeSet提供了选择最大优先级线程的便利，能够有效简化pickNextThread()等部分代码，故而利用TreeSet实现了等待队列。不过在后来的测试过程中我发现一旦线程进入等待队列(TreeSet实现)后，想要修改其优先级变成一件比较复杂的事情，考虑再三，我还是决定只是用一个简单的链表来作为等待队列，不过在ThreadState类上我还保留了曾经为了使用TreeSet结构而实现的Comparable接口的痕迹作为留念。3.关于ThreadState的理解。这个类在调度过程中十分关键，他保存了线程的必要的相关信息（我们可以根据需要修改添加其内容）。在本次实现中，我添加了线程的priority属性，以及保存线程所在的所有等待队列的对象myQueues。4.关于保存线程所有等待队列的对象myQueues。因为涉及到优先级捐献（优先级转置或者优先级继承）功能的实现，这个过程需要我们从需要进行优先级捐献的线程的所有队列中拿出来一个最大的优先级赋给该线程，以确保线程的执行，避免出现因为低优先级且占有资源线程却得不到执行的情况产生的其他线程的饥饿现象。关于myQueues的数据结构的选择，我选择了在对象添加删除等处理方面颇具优势的HashSet，并且定义其中保存的对象为PriorityQueue，这意味着我用链表实现的等待队列将无法进入myQueues保存。这部分在后面的叙述中会加以说明。5.关于pickNextThread和nextThread方法。这个部分十分简单，pickNextThread只是按照线程的优先级在调度器的等待队列中选取一个优先级符合要求（即优先级最大）的线程返回他的ThreadState对象。基于pickNextThread实现的基础上，nextThread的功能更加容易实现，他只要把pickNextThread选取的线程的状态置为就绪即可。6.关于getEffectivePriority。该方法是实现优先级继承功能的关键。先说这个方法的功能实现。我们通过该方法获取一个线程的有效优先级（即其所属的等待队列中所有线程中最高的一个优先级数值），这个优先级将用于赋给该线程，确保该线程的运行顺利进行以避免第四条中提到的饥饿现象。在该方法的实现过程中，首先我们遍历myQueues(其中保存了该线程的所属的所有PriorityQueue类型的等待队列)，在其中选取一个最大的优先级赋在一个局部变量中暂时保存下来。就像之前提到的，myQueues是一个保存PriorityQueue对象的HashSet，这意味着在我的实现中有些不属于PriorityQueue对象的等待队列无法通过对myQueues的便利得到。在这次实现中我把这样的队列单拉出来进行遍历，其实只有一个waitJoinQueue，把这样的非PriorityQueue的等待队列的最大优先级与之前的myQueues中获取的最大优先级以及线程本身的优先级进行对比，选出其中最大的一个返回作为该线程的优先级即完成了该方法的任务。后面针对于Join方法的优先级继承情况做出了测试。三、实现代码1.相关变量在ThreadState中/* The thread with which this object is associated. */ protected KThread thread;protected HashSet<PriorityQueue> myQueues;/* The priority of the associated thread. */protected int priority;在PriorityQueue中LinkedList<ThreadState> waitQueue;上述变量初始化：this.thread = thread; priority = priorityDefault; myQueues = new HashSet<PriorityQueue>();waitQueue = new LinkedList<ThreadState>();2.KThread类中getPriority,SetPriority，getStatus方法public void setPriority(int priority) boolean status = Machine.interrupt().disable(); ThreadedKernel.scheduler.setPriority(this,priority); Machine.interrupt().restore(status); public int getPriority() int priority = 0; ThreadState ts=(ThreadState) this.schedulingState; priority = ts.getPriority(); return priority; /public int getPriority()/return priority;/*by Vam*/public int getStatus()return status;/*by Vam*/3. PriorityQueue.pickNextThread()protected ThreadState pickNextThread() / implement me/just find the thread with the highest ePriorityif(waitQueue.isEmpty()/System.out.println("null.");return null;else/System.out.println(ThreadState) waitQueue.last().getEffectivePriority();ThreadState res=null;for(ThreadState ts: waitQueue)if(res=null)res = ts;elseif(ts.getPriority()>res.getPriority()res = ts;return res;4. PriorityQueue.nextThread()public KThread nextThread() Lib.assertTrue(Machine.interrupt().disabled();/ implement meif(pickNextThread()=null)return null;KThread thread = pickNextThread().thread;getThreadState(thread).acquire(this);return thread;5. ThreadState.getEffectivePriority()public int getEffectivePriority() / implement me /1.joinQueue /2.lockwaitQueue /3.semophoreQueue/4.condtion/if(this.getThread().getName().equals("k")/System.out.println("-k in getEffectivePriority-"); int effectivePriority=priority; for(PriorityQueue queue: myQueues) if(queue.transferPriority) if(queue.waitQueue.size()<=0) break; ThreadState res=null; for(ThreadState ts:queue.waitQueue) if(res=null) res = ts; else if(ts.getPriority()>res.getPriority() /System.out.println(ts.getThread().getName()+"t"+ts.getPriority()+"t"+res.getThread().getName()+"t"+res.getPri