山东大学操作系统课设nachos.docx

1、山东大学操作系统课设nachos操作系统课程设计实验报告对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.

2、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 thre

3、ads (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.1 Implements Join() method一、问题描述1. Note that another thread does not have to call joi

4、n(), 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函数，在

5、线程完成运行即将终止时检查其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, J

6、oining 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(); waitJoi

7、nQueue.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.g

8、etName(); 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. Prov

9、ide 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 wai

10、tQueue: 该条件变量等待的线程构成的队列3.sleep(): 其他线程在该条件变量上的等待即进入该条件变量的waitQueue陷入阻塞状态4.wake(): 唤醒该条件变量中等待的某个线程5.wakeAll(): 即对wake()方法的循环调用，直到队列中没有线程为止三、实现代码1.相关变量private Lock conditionLock;private ThreadQueue waitQueue;他们在构造器中完成初始化public Condition2(Lock conditionLock) this.conditionLock = conditionLock; waitQueu

11、e = 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.currentT

12、hread().sleep(); /System.out.println(+); conditionLock.acquire();/executed after waken up Machine.interrupt().restore(intStatus); 3.wake()public void wake() Lib.assertTrue(conditionLock.isHeldByCurrentThread(); boolean intStatus = Machine.interrupt().disable(); KThread t = waitQueue.nextThread(); if

13、(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.inte

14、rrupt().restore(intStatus);四、方案总结1. 我们采用ThreadQueue对象来实现等待队列而非简单的利用一个LInkedList，这样保证了这个队列的调度算法与调度器的一致性，也免除了自己在wake方法中到底wake哪个线程的纠结。2.ThreadQueue.nextThread对于队列中没有线程的情况返回null值，故我们通过检查它的返回值来确定队列里有没有线程。3.线程陷入阻塞之前放弃锁，恢复就绪状态再获取锁。Task 1.3 Complete the implementation of Alarm Class一、问题描述1. Implemente the w

15、aitUntil(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. yo

16、u 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.

17、nachos系统每隔大概500个时间间隔会调用一次timerInterrupt()，于是我们在这个函数中检查list中等待的线程是否已经完成了等待，比较标准为当前系统时刻大于等于线程应该被唤醒的时刻4.waitUntil函数：在这个函数被线程调用后，调用时刻与函数接收的参数运算后得到线程应该被唤醒的时刻，如果这个时刻还没到达我们就把这个线程和他的唤醒时刻放到threadTime类中进入list中。三、实现代码1.一些相关变量：LinkedList list = new LinkedList();/used to store threadTime2.threadTime类：/*added*/ p

18、rivate 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 w

19、aiting 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;iwakeTime) list.add(i,tt); else if

20、(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=(threadTime) list.get(i).getTime() (threadTime) list.get(i).getThread().ready

21、(); 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

22、 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 Communica

23、tor4. Each communicator should only use exactly one lock.二、解决方案按照题目中的线索我们应该利用条件变量完成相关功能。Communicator对象可以调用speak和listen方法进行通信。对于speak方法：首先检查是否有listener，如果没有就进入等待，如果有就唤醒listener把信息传递过去然后退出。对于listen方法：首先检查是否有speaker，如果没有就进入等待，如果有就唤醒speaker收听信息。对于communicator类，我们应该保存speaker和listener的条件变量，以及能说明两者数目的相关数值变

24、量。三、实现代码1.相关变量：LinkedList words; Condition2 speaker; Condition2 listener; int num_speaker,num_listener,num_words;Lock lock;变量在构造器中的初始化 public Communicator() words = new LinkedList(); lock = new Lock(); speaker = new Condition2(lock); listener = new Condition2(lock); num_words = 0; num_speaker = 0; n

25、um_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.curren

26、tThread().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.sle

27、ep(); 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.当且仅当一次成功的信息传递完成时线程才可以

28、退出。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

29、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