北大操作系统nachos实习报告——第一部分线程机制实习.doc

线程机制实习报告姓名：马亮 学号：1001210767日期：2011年4月4日目录内容一：总体概述3内容二：任务完成情况3任务完成列表（Y/N）3具体Exercise的完成情况3内容三：遇到的困难以及解决方法20内容四：收获及感想20内容五：对课程的意见和建议20内容六：参考文献21内容一：总体概述通过为期四周的进程部分的实习，使得我对进程的状态转换、调度、同步和互斥、进程间通信等原理有了更为直观的感受，加深了对于理论的理解。通过动手做的过程，将书本上的理论知识转化为代码的实现，能够很好的巩固这些知识点。对于之前不甚了解的管程和条件变量等概念，也通过实验和教材阅读有了更好的掌握。重新捡起荒废了多年的C+，实验的过程还能帮助我重新掌握C+编程，受益匪浅。内容二：任务完成情况任务完成列表（Y/N）Exercise1Exercise2Exercise3Exercise4Exercise5Exercise6第一周YYY第二周YYY第三周Y第四周NNNYNN具体Exercise的完成情况第一周Exercise1 增加“用户 ID、线程 ID”两个数据成员,同时在 Nachos 现有的线程管理机制中增加对这两个数据成员的维护机制。增加“挂起(suspending) ”状态,即可以将当前线程映像保存在磁盘文件而不是内存中。设计思想线程ID从0开始递增，线程结束后它所使用的ID应该被收回，以便分配给新的线程。为实现上面的设想，用一个整数数组ThreadID来标识线程ID的分配情况，ThreadID0为1表示0号线程ID已经分配，否则表示未分配。新线程建立时从下标0开始依次向后遍历数组，找到第一个可使用的线程ID（数组元素值为0的下标），分配此线程ID，并将数组元素值置1。线程结束时需要将它的ID对应下标的值置0，以便将此ID重复利用。修改代码Thread.h中声明private的成员变量uid、tid，声明public的成员方法getThreadID()，getUserID()在system.h中声明全局数组变量ThreadID，用来存储线程ID的分配情况：在system.cc中增加ThreadID的声明:在Initialize方法中对ThreadID数组进行初始化：在Thread.cc中的构造函数和析构函数中增加获取线程ID和释放线程ID的代码：在Thread.cc中增加获取当前线程ID和用户ID的方法getThreadID()、getUserID()对于用户ID，由于系统中不存在用户的概念，暂且只增加用户ID的声明和获取方法，不实现具体的操作系统用户功能。对于增加“挂起(suspending) ”状态,只需修改thread.h中的ThreadStatus枚举常量，增加SUSPENDING状态即可，具体的功能实现由于还未涉及到磁盘操作，暂不实现：运行效果为了体现进程ID的修改效果，ThreadTest测试类SimpleThread方法中输出线程编号时改为通过currentThread-getThreadID()来获得，而不是通过传入的which来获得：同时多加几个线程：运行效果如下：可看到通过currentThread-getThreadID()可获得正确的ID值。Exercise2在 Nachos 中增加对线程数量的限制, 使得 Nachos 中最多能够同时存在 128 个用户线程。设计思想增加全局变量threadCount，对在运行的线程进行计数，线程Fork时threadCount+，并判断是否超出最大线程数，超出的话直接返回，不执行接下来的分配存储空间等操作。Finish时threadCount-。修改代码System.h中增加全局变量System.cc中初始化Thread类的Fork函数和Finish函数中对其值进行操作运行效果修改MAX_THREAD_COUNT的值为2，运行四个线程：输出结果如下：可见线程3、4因为到达系统线程上限而没有运行，达到预期效果。Exercise3修改线程调度算法,实现基于优先级的抢占式调度算法。设计思想从nachos系统的scheduler.cc文件中可看出Nachos实现了先进先出（FIFO）的调度算法。调度类Scheduler管理这一个就绪队列list，它的成员函数ReadyToRun (Thread *thread)将指定线程插入到队列的队尾。它的另一个成员函数FindNextToRun ()则从list队首摘出一个就绪线程准备运行。为了实现基于优先级的抢占式调度算法，首先给线程增加priority属性，规定最高优先级为0，最低为10。通过修改Scheduler类的ReadyToRun方法，使得线程按照优先级的顺序插入就绪队列相应的位置。修改Thread类的Yield方法，使得当前线程让出CPU时比较它的优先级和就绪队列中优先级最高的线程的优先级（即就绪队列队首的线程），来决定是让出CPU还是继续占据CPU。修改代码修改Thread.h，加入线程优先级相关的声明：修改Thread.cc，加入获取优先级和设置优先级的方法，设置优先级时注意将优先级限制在最高优先级和最低优先级之间：同时在构造函数中设置新建线程的默认优先级为5：修改Scheduler类的ReadyToRun方法，使得进程按照优先级从高到低的顺序加入到就绪队列相应的位置上：修改Thread类的Yield方法，使得每次当前线程让出CPU时判断当前线程的优先级和就绪队列里第一个线程（也是优先级最高的线程）的优先级谁高谁低，如果当前线程优先级高，则继续执行当前线程；如果就绪队列里的第一个线程优先级高，则当前线程让出CPU；如果一样高，则依旧为时间片轮转策略：运行效果修改测试方法，设置每个线程的优先级：得到执行结果如下：可见线程按照它们的优先级被调度，并且相同优先级的线程按照时间片轮转调度。第二周Exercise1阅读源码synch.h, synch.cc。在synch.h中声明了三个类，分别是Semaphore信号量类，Lock锁类和Condition条件变量类。在synch.cc中已经给出了Semaphore的具体实现，Lock和Condition类做了空实现。Semaphore类中实现了PV操作的方法，因为都是原子性操作，所以方法先关中断，执行完再开中断。方法的实现比较简单。P操作如果信号量为0，把当前进程挂到此信号量的阻塞队列上，如果不是，信号量减一。V操作如果此信号量的阻塞队列上有进程，则调度，然后对信号量加一。Exercise2& Exercise3实现锁和条件变量。设计思想Nachos中已经预留了lock和condition的定义，只需加入具体代码实现即可。修改代码Synch.h中lock类的定义加入信号量semaphore和锁持有者lockHolder的声明：Synch.h中Condition类的定义加入等待队列queue和锁持有者lock的声明：Synch.cc中增加Lock类的实现代码，如下：Synch.cc中增加Condition类的实现代码，如下：运行效果运行效果需要通过下面的练习来验证。第三周Exercise1实现同步互斥实例。设计思想因为对nachos系统的整体把握还不够有信心，选择做较简单的生产者消费者问题，并且暂时还没搞明白如何编写用户态程序进行测试，故在ThreadTest中模拟生产者和消费者线程的运行。使用上一题编写的条件变量实现生产者消费者问题。修改代码修改ThreadTest类，模拟生产者和消费者线程，首先声明需要用到的锁和条件变量以及缓冲区然后编写生产者线程：编写消费者线程：修改ThreadTest1方法，运行生产者和消费者线程：运行效果生产者和消费者按照预期顺序执行。Exercise2用信号量实现生产者消费者问题。只需声明两个信号量：信号量Producer初值设为1，信号量Consumer初值设为0。一个互斥量：mutex用于对缓冲区互斥操作。对于生产者，只需：Producer-P();Mutex-P();Produce();Mutex-V();Consumer-V();对于消费者，只需：Consumer-P();Mutex-P();Consumer();Mutex-V();Producer-V();第四周Exercise1选作了实现Barrier的题目设计思想设置一个信号量，初值取负数，barrier线程对此信号量进行P操作。然后若干个线程都在某一点对此信号量进行V操作，直到足够的V操作使得信号量变为正值时，才能触发barrier线程继续往下执行。修改代码修改Synch.cc中Semaphore的P操作，将条件从value=0修改为value=0，以便能支持负信号量：在ThreadTest类中声明一个信号量，初值置为-2：在ThreadTest中定义Barrier和Thread1、Thread2、Thread3三个待执行线程，Thread1、Thread2、Thread3接收用户输入，如果用户指定他们运行下去，则他们对b信号量发出V操作，Barrier线程中对b信号量执行P操作，因为b的初值为-2，当且仅当Thread1、Thread2、Thread3三个线程都发出V操作后，Barrier线程才能继续往下执行。修改ThreadTest1方法，加载上面的四个线程，以便运行测试：运行效果依次输入y，使三个线程运行到barrier，如下：内容三：遇到的困难以及解决方法困难1荒废C+多年，并且之前一直搞JAVA，也没有用C+写过什么像样的东西。这次使用C+做实习，重新捡起教材学习C+。由于语言的不熟悉，代码修改和编译时遇到很多问题。为了高质量的完成实习，需要尽快熟悉C+。困难2对于条件变量的使用不是很明白，阅读了教材和课件的相关部分，发现讲解的不多。虽然答题知道是怎么回事了，但不像信号量和互斥锁那样熟悉，对于它的使用方式也不甚明确。接下来还需要再多查查资料，彻底搞明白。内容四：收获及感想通过这次实习，对于进程部分众多抽象的知识点都有了较好的掌握。通过实际阅读代码和编写代码，很好的消化掉这些知识点，感觉收获颇多。同时借助实习机会重新学习C+的相关知识，能够全面的掌握主流编程语言，是这门课的附加收获。感想是，搞了几年JAVA，C+完全是个菜鸟了啊，