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

山东大学计算机学院操作系统实验报告操作系统课程设计 操作系统课程设计报告 学院：计算机科学与技术学院 专业：计算机科学与技术 班级：20*级*班 姓名：* 学号：20* 操作系统课程设计 目录 一 二 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4. 实验平台. 4 Project1建立线程系统 . 4 要求 . 4 分析 . 4 方案 . 4 实现代码 . 5 要求 . 6 分析 . 6 方案 . 7 实现代码 . 7 要求 . 9 分析 . 9 方案 . 10 实现代码 . 10 要求 . 12 分析 . 13 方案 . 13 实现代码 . 13 要求 . 16 分析 . 16 方案 . 17 实现代码 . 17 要求 . 21 分析 . 21 方案 . 22 实现代码 . 22 Task1.1实现KThread.join . 4 Task1.2利用中断提供原子性，直接实现条件变量 . 6 Task1.3实现waitUntil . 9 Task1.4用条件变量，不使用信号量，实现同步发送接收消息，speak，listen .12 Task1.5完成PriorityScheduler实现优先级调度 .16 Task1.6 .21 三 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4. Project2多道程序设计 . 31 要求 . 32 分析 . 32 方案 . 33 实现代码 . 35 要求 . 40 分析 . 41 方案 . 41 实现代码 . 42 要求 . 49 分析 . 49 方案 . 49 实现代码 . 51 Task2.1 .32 Task2.2 .40 Task2.3 .49 操作系统课程设计 Task2.4 .54 1. 2. 3. 4. 要求 . 54 分析 . 54 方案 . 54 实现代码 . 54 操作系统课程设计 一 实验平台 开发语言：Java 开发工具：Eclipse Luna 操作系统：Ubuntu14.04 二 Project1建立线程系统 Task1.1实现KThread.join 1. 要求 实现Implement KThread.join函数。注意：其它的线程不必调用join函数，但是如果它被调用的话，也只能被调用一次。 对join函数第二次调用的执行结果是不被定义的。 2. 分析 Join函数的作用即为等待某线程运行完毕. 当前线程 (唯一一个正在运行的线程) A调用另一个线程 (处于就绪状态) B的join函数时 (A 和 B 在Nachos中均为KThread类型对象), A被挂起, 直到B运行结束后, join函数返回, A才能继续运行。 3. 方案 原KThread的join中的Lib.assertTrue(this != currentThread)已经实现线程只能调用一次join方法，根据要求，在调用join方法时，让当前运行线程休眠，并将当前运行的线程加入到一个阻塞队列中。在线程结束时，finish函数循环唤醒所有被阻塞的线程。 操作系统课程设计 4. 实现代码 public void join Lib.debug(dbgThread, "Joining to thread: " + toString); Lib.assertTrue(this != currentThread); boolean intStatus = Machine.interrupt.disable; if (status != statusFinished) waitForJoin.waitForAccess(currentThread); public static void finish Lib.debug(dbgThread, "Finishing thread: " + KThread.sleep; currentThread.toString); Machine.interrupt.disable; Machine.autoGrader.finishingCurrentThread; Lib.assertTrue(toBeDestroyed = null); toBeDestroyed = currentThread; 操作系统课程设计 currentThread.status = statusFinished; KThread waitThread; while (waitThread = currentThread.waitForJoin.nextThread) != null) waitThread.ready; sleep; Task1.2利用中断提供原子性，直接实现条件变量 1. 要求 通过利用中断有效和无效所提供的原子性实现条件变量。我们已经提供类似的例子用例实现信号量。你要按此提供类似的条件变量的实现，不能直接利用信号量来实现。在你完成时要提供条件变量的两种实现方法。你的第二种条件变量实现要放在nachos.threads.Condition2中。 2. 分析 threads.Lock类提供了锁以保证互斥. 在临界代码区的两端执行Lock.acquire 和Lock.release 即可保证同时只有一个线程访问临界代码区. 条件变量建立在锁之上, 由threads.Condition实现, 它是用来保证同步的工具. 每一个条件变量拥有一个锁变量 (该锁变量亦可被执行acquire和release操作, 操作系统课程设计 多个条件变量可共享同一个锁变量). 当处于临界区内的拥有某锁L的当前线程对与锁L联系的条件变量执行sleep操作时, 该线程失去锁L并被挂起. 下一个等待锁L的线程获得锁L (这个过程由调度程序完成) 并进入临界区. 当拥有锁L的临界区内的当前线程对与锁L联系的条件变量执行wake操作时 (通常调用wake之后紧接着就是Lock.release), 等待在该条件变量上的之多一个被挂起的线程 (由调用sleep引起) 被重新唤醒并设置为就绪状态. 若执行wakeall操作, 则等待在该条件变量上的所有被挂起的线程都被唤醒. 3. 方案 condition.sleep 采用waiter.P 实现休眠 (waitor是一个信号量) 并将waitor放入信号量队列, 在我们的实现中改成用KThread.sleep实现休眠并将当前线程放入线程队列, 并在sleep函数开始/结尾处屏蔽/允许中断以保证原子性。 condition.wake中从等待信号量队列中取出信号量并对其进行V操作实现唤醒, 在我们的实现中改成从线程队列中取出线程用KThread.ready 实现唤醒 (同样要在wake函数开始/结尾处屏蔽/允许中断)。 wakeall函数的实现依赖于wake. 只需不断地wake 直到队列为空为止. 4. 实现代码 private ThreadQueue waitQueue = ThreadedKernel.scheduler.newThreadQueue(false); private boolean hasWaiter = false; public void sleep 操作系统课程设计 Lib.assertTrue(conditionLock.isHeldByCurrentThread); boolean intStatus = Machine.interrupt.disable; waitQueue.waitForAccess(KThread.currentThread); hasWaiter = true; conditionLock.release; KThread.sleep; conditionLock.acquire; Machine.interrupt.restore(intStatus); public void wake Lib.assertTrue(conditionLock.isHeldByCurrentThread); boolean intStatus = Machine.interrupt.disable; KThread thread = waitQueue.nextThread; if (thread != null) thread.ready; 操作系统课程设计 else hasWaiter=false; Machine.interrupt.restore(intStatus); public void wakeAll Lib.assertTrue(conditionLock.isHeldByCurrentThread); while (hasWaiter) wake; Task1.3实现waitUntil 1. 要求 通过实现waitUntil方法来完成Alarm类。 2. 分析 一个线程通过调用waitUntil函数来挂起它自己，直到now+x后才被唤醒。在实时操作中，对线程是非常有用的，例如实现光标每秒的闪烁。这里并不要求线程被唤醒后马上执行它，只是在它等待了指定时间后将它。放入等待队列中。不要通过产生任何附加的线程来实现waitUntil函数，你仅需要修改waitUntil操作系统课程设计 函数和时间中断处理程序。waitUntil函数并不仅限于一个线程使用，在任意时间，任意多的线程可以调用它来阻塞自己。 3. 方案 于Alarm类有关的是machine.Timer类. 它在大约每500个时钟滴答使调用回调函数 (由Timer.setInterruptHandler函数设置). 因此, Alarm类的构造函数中首先要设置该回调函数Alarm.timerInterrupt. 为了实现waitUntil, 需要在Alarm类中实现一个内部类Waiter, 保存等待的线程及其唤醒时间.在调用waitUntil(x) 函数时, 首先得到关于 该线程的信息: (线程: 当前线程, 唤醒时间: 当前时间+x), 然后构造新的Waiter对象, 并调用sleep操作使当前线程挂起. 在时钟回调函数中 (大约每500个时钟间隔调用一次) 则依次检查队列中的每个对象。 如果唤醒时间大于当前时间, 则将该对象移出队列并执行wake操作将相应线程唤醒。 4. 实现代码 class Waiter Waiter(long wakeTime,KThread thread) private long wakeTime; private KThread thread; this.wakeTime=wakeTime; this.thread=thread; 操作系统课程设计 public void waitUntil(long x) boolean intStatus = Machine.interrupt.disable; long wakeTime = Machine.timer.getTime + x; Waiter waiter = new Waiter(wakeTime,KThread.currentThread); waitlist.add(waiter); System.out.println(KThread.currentThread.getName +"线程休眠，时间为："+Machine.timer.getTime+",应该在 "+wakeTime+"醒来."); KThread.sleep; Machine.interrupt.restore(intStatus); public void timerInterrupt Waiter waiter; for(int i=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; private LinkedList<Waiter> waitlist; Task1.4用条件变量，不使用信号量，实现同步发送接收消息，speak，listen 1. 要求 使用条件变量来实现一个字长信息的发送和接收同步。使用void speak(int word) 和 int listen函数来实现通讯类的通讯操作。speak函数具有原子性，在相同地Communicator类中等待listen函数被调用，然后将此字发生给listen函数。一旦传送完毕，两个函数都返回。 操作系统课程设计 2. 分析 对一个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都需要等待. 3. 方案 每个Communicator有一个锁 (保证操作的原子性) 和与该锁联系的两个条件变量用于保证speaker和listener间的同步. 在speak函数中, 首先检查若已经有一个speaker在等待(speaknum>0) 或无listener等待, 则挂起. 否则设置变量, 准备数据并唤醒一个listener. 在listen函数中, 增加一个listener后, 首先唤醒speaker, 然后将自己挂起以等待 speaker准备好数据再将自己唤醒. 这个问题其实是一个缓冲区长度为0的生产者/消费者问题. 4. 实现代码 public Communicator lock = new Lock; con = new Condition(lock); 操作系统课程设计 public void speak(int word) lock.acquire; if(speaknum>0|listennum=0) if(listennum>0) this.word=word; System.out.println(KThread.currentThread.getName+"线程说"+this.word); lock.release; public int listen con.wakeAll; listennum=0; speaknum+; con.sleep; 操作系统课程设计 lock.acquire; while(listennum>0|speaknum=0) if(speaknum>0) KThread.currentThread.yield; System.out.println(KThread.currentThread.getName+"线程听到"+this.word); listennum=0; lock.release; private Lock lock; return this.word; con.wake; speaknum-; listennum+; con.sleep; listennum-; 操作系统课程设计 private Condition con; private int word; private static int speaknum; private static int listennum; Task1.5完成PriorityScheduler实现优先级调度 1. 要求 通过完成PriorityScheduler类在Nachos中实现优先级调度。优先级调度是实时系统中的关键构建模块。 2. 分析 在Nachos中, 所有的调度程序都继承抽象类Scheduler. 系统已经提供了一个简单的轮转调度器 RoundRobinScheduler, 它对所有线程不区分优先级而采用简单的FIFO队列进行调度. 我们实现的优先级调度类PriorityScheduler也继承自Scheduler. 优先级调度的传统算法如下: 每个线程拥有一个优先级 (在Nachos中, 优先级是一个0到7之间的整数, 默认为1). 在线程调度时, 调度程序选择一个拥有最高优先级的处于就绪状态的线程运行. 这种算法的问题是可能出现 “饥饿” 现象: 设想有一个低优先级的线程处于临界区中运行而高优先级的线程在临界