Nachos同步机制实习报告.doc

精品文档同步机制实习报告善良的大姐姐2015.3.30目录一：总体概述3二：任务完成情况3任务完成列表（Y/N）3具体Exercise的完成情况3三：遇到的困难以及解决方法12四：收获及感想12内容五：参考文献13一：总体概述Lab3首先要求阅读Nachos系统提供的同步机制代码，即Semaphore的实现。其次要求修改底层源代码，达到“扩展同步机制，实现同步互斥实例”的目标。具体来说，即要求在Semaphore的基础上，实现Lock锁和Mesa管程的Condition（条件变量）。此外，还要利用编写的同步机制，来实现互斥实例，进而证明同步机制编写的正确性。二：任务完成情况任务完成列表（Y/N）Exercise1Exercise2Exercise3Exercise4Challenge1Challenge2YesYesYesYesYesYes具体Exercise的完成情况Exercise1：调研任务：调研Linux中实现的同步机制调研情况：Linux的同步机制包括好几层。第一层：原子操作。以x86体系结构为例，定义在linuxX.X/include/asm-i386/atomic.h文件中。文件内定义了原子类型atomic_t，其仅有一个字段counter，用于保存32位数据。其中原子操作函数atomic_inc完成自加原子操作。第二层：自旋锁。以x86体系结构为例，定义在linuxX.X/include/asm-i386/spinlock.h文件中。其中_raw_spin_lock完成自旋锁的加锁功能。自旋锁达到的效果为，在等待锁的线程会不断地申请锁，直到获得锁或是时间片用尽从而离开CPU。第三层：信号量以x86体系结构为例，定义在linuxX.X/include/asm-i386/semaphore.h文件中。信号量的申请操作使用down函数，释放操作使用up函数。即通常所说的PV操作。区别于自旋锁，当一个进程在等待一个锁时，会让出CPU进入休眠状态，直到其他进程释放锁后，将该进程放入可运行队列。Exercise2：源代码阅读任务阅读下列源代码，理解Nachos现有的同步机制。code/threads/synch.h和code/threads/synch.cccode/threads/synchlist.h和code/threads/synchlist.cc阅读情况Synch.cc(h)文件中有三个类：Semaphore, Lock, Condition。其中Semaphore是已经编写完成的。主要功能是：通过一个名字和一个初始值可以初始化一个Semaphore。P函数的作用是：判断当前线程能否进入临界区，如果可以（即初始值0），则进入，且初始值减一；如果不能（即初始值0），则将当前线程放入Semaphore的等待队列中，线程进入休眠状态。V函数的作用是：如果Semaphore的等待队列不为空，将等待队列的队头线程取出来，将其状态标识为ReadyToRun，并且初始值加1。另外两个类是本次作业需要完成的，会在之后说明。Synchlist.cc(h)文件中包括一个Synchlist类，实现了一个互斥访问的队列。 具体来说，类中有一个Append函数，用于将元素加入队列；有一个Remove函数，用于将队头元素移出队列。而互斥访问的实现方式为：用Lock锁将Append函数体和Remove函数体保护起来。保证了二者至多只有一个可以被被CPU运行，直到函数体结束。（即线程切换的中断不会造成线程交替运行） 这两个函数模拟了monitor（管程）的函数体互斥性，因此在之后的作业中会用到。Exercise3：实现锁和条件变量任务可以使用sleep和wakeup两个原语操作（注意屏蔽系统中断），也可以使用Semaphore作为唯一同步原语（不必自己编写开关中断的代码）。 完成情况1. Lock简述：使用Semaphore作为同步原语，定义的时候创建一个初始值为1的Semaphore。对应的，Acquire函数就是执行Semaphore的P函数，Release函数就是执行Semaphore的V函数。验证正确性：采用基于优先级抢占式调度，一个线程递归生成优先级更高的线程。如果没有Lock，那么当前线程就会被抢占，那么运行结果会是这样：再接连输出after fork接连输出before fork但若在线程一开始加上了互斥锁，那么只有当当前线程运行结束后，它fork出来的线程才能获得锁，才能运行，运行结果如下：一个线程输出了before fork和after fork之后，另一个线程才能输出2. Condition简述：修改情况简单解释新增List变量conditionlist容纳正在等待某个signal的线程Wait函数：1. 对传入的Lock参数执行Release2. 关中断3. 将当前线程加入conditionlist，当前线程Sleep4. 对传入的Lock参数执行Acquire5. 开中断Release的原因是，由于管程的互斥访问性，当一个线程需要wait一个signal时，需要让出CPU。而在Nachos系统中，管程的互斥访问是由Lock保证的，为了防止死锁，需要在当前线程进入休眠之前释放lock。当线程再次被唤醒时，需要再次Acquire这把锁。Signal函数：1. 关中断2. 如果conditionlist队列不为空，将队头线程取出，并放入ReadyToRun队列3. 开中断Signal函数即唤醒一个正在等待这个条件变量的线程。Broadcast函数：1. 关中断2. 将conditionlist队列中所有线程取出，并放入ReadyToRun队列3. 开中断Broadcast函数即唤醒所有正在等待这个条件变量的线程。Exercise4：实现同步互斥实例任务基于Nachos中的信号量、锁和条件变量，采用两种方式实现同步和互斥机制应用（其中使用条件变量实现同步互斥机制为必选题目）。具体可选择“生产者-消费者问题”、“读者-写者问题”、“哲学家就餐问题”、“睡眠理发师问题”等。（也可选择其他经典的同步互斥问题）完成情况1. 基于Nachos信号量实现“生产者-消费者”问题（基于时间片轮转调度，时间片长度随机。为了使得中断有可能在任何地方发生，在所有临界区中的代码语句后面都调用了interrupt-onetick）修改情况：新增测试变量和函数简单解释测试变量：1. isFull信号量，初始值为02. isEmpty信号量，初始值为N（N为生产者可以放入的最大数量，设为5）3. M1信号量4. 生产数组如果生产数组内元素数量达到N，则会被isFull信号量阻塞，生产者需要等待；如果生产数组内元素数量为0，则会被isEmpty信号量阻塞，消费者需要等待。M1信号量用于保证生产数组的互斥访问。Producer函数1. isEmpty-P()2. 在M1信号量保护下访问生产数组，加入一个元素3. isFull-V()由于IsEmpty信号量初始值为N，则生产者最多可以进入producer函数N次；相应的，isFull信号量会被释放至多N次Consumer函数1. isFull-P()2. 在M1信号量保护下访问生产数组，移出一个元素3. isEmpty-V()由于isFull信号量在生产者生产之后会被释放，因此此时消费者可以消费。相应的，isEmpty信号量被释放，使得生产者可以继续生产。Test_Producer函数For循环40次，调用producer函数生产者生产（至多）40次。（因为可以有多个生产者）Test_consumer函数For循环40次，调用consumer函数消费者消费（至多）40次。（因为可以有多个消费者）ThreadTest函数新生成1个生产者线程（装载Test_producer函数）和2个消费者线程（装载Test_consumer函数）测试结果截图：生产者放入队列的元素两个消费者交替消费元素发生时间片中断，切换线程2. 基于Nachos的条件变量实现“生产者-消费者”问题（基于时间片轮转调度，时间片长度随机。为了使得中断有可能在任何地方发生，在所有临界区中的代码语句后面都调用了interrupt-onetick）修改情况：增改测试变量和函数简单解释Synchlist.cc:新增变量1. ListEmpty条件变量2. ListFull条件变量3. Listcount计数值1和2同信号量部分的isEmpty和isFull语义计数值用于判断生产队列是否满了Append函数：1. 加锁2. 如果生产队列满，等待ListEmpty条件变量3. 否则将新元素加入生产队列4. Signal listFull条件变量5. 解锁加锁解锁保证管程函数执行的互斥性。如果生产队列满，则等待消费者消费之后，发送listEmpty条件变量。生产之后，发送listFull条件变量，激活等待消费的消费者Remove函数1. 加锁2. 如果生产队列空，等待listFull条件变量3. 否则从生产队列头取出一个元素4. Siignal listEmpty条件变量5. 解锁是Append函数的对偶版本。Monitor_producer函数For循环40次，往Synchlist管程里的队列放入元素同test_producerMonitor_consumer函数For循环40次，消费Synchlist管程里的队列的元素同test_consumerThreadTest函数新生成1个生产者线程（装载Monitor_producer函数）和2个消费者线程（装载Monitor_consumer函数）测试结果截图：两个消费者交替消费，并且不需要和生产者同步。生产者加锁进入管程测试情况详细分析：消费者2试图加锁进入管程，但由于管程互斥锁此时在消费者1手中，因此消费者2继续等待此时发生了中断 线程切换消费者1加锁进入管程（失败，由于生产队列满）释放管程互斥锁进入等待isEmpty信号的状态（进入队列+sleep）生产者试图继续加锁进入管程解锁管程互斥锁发送isFull信号放入第5个元素（最多为5）Challenge1：实现barrier任务可以使用Nachos 提供的同步互斥机制（如条件变量）来实现barrier，使得当且仅当若干个线程同时到达某一点时方可继续执行。完成情况增改处简单解释Condition类：1. 增加waitcount计数值，表示等待条件变量的队列中的线程个数2. 增加Barrier函数，在函数中，判断waitcount是否达到规定值，如果达到，则广播所有队列中的线程；否则令当前线程进入等待状态若还没达到规定值，则线程需要等待；若达到了，则释放所有等待线程。这样就可以使得规定值个数的线程“同步”运行其中，规定值设为3新增Barrier类：仿照synchlist类，实现了一个互斥访问的管程。在管程函数里，调用barrier函数测试函数：新建3个线程，每个线程用for循环调用同一个Barrier类的函数10次意图让线程均输出了i之后，再接着输出i+1测试结果截图未使用Barrier: 使用Barrier 同步（三个线程均输出i之后才进入下一个，interrupt表示时间片到了切换线程。）不同步Challenge2：实现read/write lock任务基于Nachos提供的lock(synch.h和synch.cc)，实现read/write lock。使得若干线程可以同时读取某共享数据区内的数据，但是在某一特定的时刻，只有一个线程可以向该共享数据区写入数据。完成情况（基于时间片轮转调度，时间片长度随机。为了使得中断有可能在任何地方发生，在reader函数和writer函数所有的代码语句后面都调用了interrupt-onetick）修改情况：增改变量及函数简单解释变量：Lock mutexLock wMutex用于保护共享变量rc（记录读者数量）W用于读者和写者访问临界区的互斥性Reader函数1. Mutex上锁2. Rc加1。如果rc等于1，w上锁3. Mutex解锁4. 读操作5. Mutex上锁6. Rc减1。如果rc等于0，w解锁Mutex解锁Mutex保护共享变量rc，因为可以允许多个读者处于读状态，因此rc可能会被多个读者同时访问，需要保护起来。W互斥读者和写者，第一类读写者问题是读者优先，因此若临界区内有读者，写者就会被w阻塞在临界区外，直到所有读者离开临界区。Writer函数1. W上锁2. 写操作3. W解锁写者能够进入临界区当且仅当临界区内没有读者。但写者在临界区内的时候，读者不能进入。测试函数：新建一个写者和两个读者，并且让他们分别写（读）10次。测试结果截图：读者可以同时读。（start和finish之间可以认为是临界区）写者在临界区里时，即使发生了interrupt（线程切换），也无法让读者进入。即读者和写者不能同时访问临界区三：遇到的困难以及解决方法困难1：我在完成lab2线程调度实验中，在readyToRun函数中对当前线程执行了yield操作，导致lab3中V函数的原子性被破坏。（V函数会调用readyToRun函数）解决方式：将线程Yield的过程单独封装成一个函数，readyToRun函数仅仅负责将当前线程放入可执行队列当中。对于新建的一个线程（可能可以抢占当前线程），先调用该函数，判断是否抢占。如果抢占，则让当前线程yield；否则，调用readyToRun函数。困难2：思考如何实现condition的wait函数，曾一度觉得synchlist中会造成死锁解决方式：详细了解了管程机制之后，发现只要在wait函数中，先对传入的Lock参数执行释放（Release）操作，当前线程再进入休眠状态，问题就可以解决了。困难3：在写“生产者-消费者”问题的测试函数时，从队列中读出来的值总是等于最后一个加入队列的值（比如加入队列1,2,3,4，读出来会是4,4,4,4） 解决方式：由于传入的是(void *)，是一个指针。因此我直接传入了for循环中的i的地址，这就导致了i