Nachos同步机制实习报告

同步机制实习报告

善良的大姐姐 2015.3.30

目录

一：总体概述 ................................................................................... 3 二：任务完成情况 ............................................................................ 3 任务完成列表（Y/N） ................................................................ 3 具体Exercise的完成情况 ........................................................... 3 三：遇到的困难以及解决方法 ...................................................... 12 四：收获及感想 ............................................................................. 12 内容五：参考文献 .......................................................................... 13

2

一：总体概述

Lab3首先要求阅读Nachos系统提供的同步机制代码，即Semaphore的实现。其次要求修改底层源代码，达到“扩展同步机制，实现同步互斥实例”的目标。具体来说，即要求在Semaphore的基础上，实现Lock锁和Mesa管程的Condition（条件变量）。此外，还要利用编写的同步机制，来实现互斥实例，进而证明同步机制编写的正确性。

二：任务完成情况

任务完成列表（Y/N）

Exercise1 Yes Exercise2 Yes Exercise3 Yes Exercise4 Yes Challenge1 Yes Challenge2 Yes 具体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进入休眠状态，直到其他进程释放锁后，将该进程放入可运行队列。

3

Exercise2：源代码阅读

任务

阅读下列源代码，理解Nachos现有的同步机制。 code/threads/synch.h和code/threads/synch.cc code/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，那么当前线程就会被抢占，那么运行结果会是这样：

4

接连输出before fork 再接连输出after fork

但若在线程一开始加上了互斥锁，那么只有当当前线程运行结束后，它fork出来的线程才能获得锁，才能运行，运行结果如下：

一个线程输出了before fork和after fork之后，另一个线程才能输出

2. Condition

简述：

修改情况 新增List变量conditionlist Wait函数：

简单解释 容纳正在等待某个signal的线程 Release的原因是，由于管程的互斥访问5

1. 对传入的Lock参数执行Release 2. 关中断 3. 将当前线程加入conditionlist，当前线程Sleep 4. 对传入的Lock参数执行Acquire 5. 开中断 Signal函数： 1. 关中断 2. 如果conditionlist队列不为空，将队头线程取出，并放入ReadyToRun队列 3. 开中断 Broadcast函数： 1. 关中断 2. 将conditionlist队列中所有线程取出，并放入ReadyToRun队列 3. 开中断

性，当一个线程需要wait一个signal时，需要让出CPU。而在Nachos系统中，管程的互斥访问是由Lock保证的，为了防止死锁，需要在当前线程进入休眠之前释放lock。当线程再次被唤醒时，需要再次Acquire这把锁。 Signal函数即唤醒一个正在等待这个条件变量的线程。 Broadcast函数即唤醒所有正在等待这个条件变量的线程。 Exercise4：实现同步互斥实例

任务

基于Nachos中的信号量、锁和条件变量，采用两种方式实现同步和互斥机制应用（其中使用条件变量实现同步互斥机制为必选题目）。具体可选择“生产者-消费者问题”、“读者-写者问题”、“哲学家就餐问题”、“睡眠理发师问题”等。（也可选择其他经典的同步互斥问题） 完成情况

1. 基于Nachos信号量实现“生产者-消费者”问题

（基于时间片轮转调度，时间片长度随机。为了使得中断有可能在任何地方发生，在所有临界区中的代码语句后面都调用了interrupt->onetick） 修改情况： 新增测试变量和函数 测试变量： 1. isFull信号量，初始值为0 2. isEmpty信号量，初始值为N（N为生产者可以放入的最大数量，设为5） 3. M1信号量 4. 生产数组 Producer函数 1. isEmpty->P() 2. 在M1信号量保护下访问生产数组，加入一个元素 3. isFull->V() Consumer函数

简单解释 如果生产数组内元素数量达到N，则会被isFull信号量阻塞，生产者需要等待；如果生产数组内元素数量为0，则会被isEmpty信号量阻塞，消费者需要等待。 M1信号量用于保证生产数组的互斥访问。 由于IsEmpty信号量初始值为N，则生产者最多可以进入producer函数N次；相应的，isFull信号量会被释放至多N次 由于isFull信号量在生产者生产之后会被6

1. isFull->P() 2. 在M1信号量保护下访问生产数组，移出一个元素 3. isEmpty->V() Test_Producer函数 For循环40次，调用producer函数 Test_consumer函数 For循环40次，调用consumer函数 ThreadTest函数 新生成1个生产者线程（装载Test_producer函数）和2个消费者线程（装载Test_consumer函数）

测试结果截图：

释放，因此此时消费者可以消费。相应的，isEmpty信号量被释放，使得生产者可以继续生产。 生产者生产（至多）40次。（因为可以有多个生产者） 消费者消费（至多）40次。（因为可以有多个消费者） 生产者放入队列的元素 发生时间片中断，切换线程 两个消费者交替消费元素

2. 基于Nachos的条件变量实现“生产者-消费者”问题

（基于时间片轮转调度，时间片长度随机。为了使得中断有可能在任何地方发生，在所有临界区中的代码语句后面都调用了interrupt->onetick） 修改情况：

增改测试变量和函数 Synchlist.cc: 新增变量 1. ListEmpty条件变量 2. ListFull条件变量

简单解释 1和2同信号量部分的isEmpty和isFull语义 计数值用于判断生产队列是否满了 7

3. Listcount计数值 Append函数： 1. 加锁 2. 如果生产队列满，等待ListEmpty条件变量 3. 否则将新元素加入生产队列 4. Signal listFull条件变量 5. 解锁 加锁解锁保证管程函数执行的互斥性。 如果生产队列满，则等待消费者消费之后，发送listEmpty条件变量。 生产之后，发送listFull条件变量，激活等待消费的消费者 Remove函数 是Append函数的对偶版本。 1. 加锁 2. 如果生产队列空，等待listFull条件变量 3. 否则从生产队列头取出一个元素 4. Siignal listEmpty条件变量 5. 解锁 Monitor_producer函数 For循环40次，往Synchlist管程里的队列放入元素 Monitor_consumer函数 For循环40次，消费Synchlist管程里的队列的元素 ThreadTest函数 新生成1个生产者线程（装载Monitor_producer函数）和2个消费者线程（装载Monitor_consumer函数）

测试结果截图：

同test_producer 同test_consumer 两个消费者交替消费，并且不需要和生产者同步。

8

测试情况详细分析： 生产者加锁进入管程 放入第5个元素（最多为5） 发送isFull信号 解锁管程互斥锁 生产者试图继续加锁进入管程 （失败，由于生产队列满）释放管程互斥锁 进入等待isEmpty信号的状态（进入队列+sleep） 消费者1加锁进入管程 此时发生了中断 线程切换 消费者2试图加锁进入管程，但由于管程互斥锁此时在消费者1手中，因此消费者2继续等待

Challenge1：实现barrier

任务

可以使用Nachos 提供的同步互斥机制（如条件变量）来实现barrier，使得当且仅当若干个线程同时到达某一点时方可继续执行。 完成情况 增改处 Condition类： 1. 增加waitcount计数值，表示等待条件变量的队列中的线程个数 2. 增加Barrier函数，在函数中，判断waitcount是否达到规定值，如果达到，则广播所有队列中的线程；否则令当前线程进入等待状态 新增Barrier类： 仿照synchlist类，实现了一个互斥访问的管程。在管程函数里，调用barrier函数 测试函数： 新建3个线程，每个线程用for循环调用同一

简单解释 若还没达到规定值，则线程需要等待；若达到了，则释放所有等待线程。这样就可以使得规定值个数的线程“同步”运行 其中，规定值设为3 意图让线程均输出了i之后，再接着输出i+1 9

个Barrier类的函数10次 测试结果截图 未使使用Barrier

用

Barrier:

同步（三个线程均输出i之后才进入下一个，interrupt表示时间片到了切换线程。） 不同步

Challenge2：实现read/write lock

任务

基于Nachos提供的lock(synch.h和synch.cc)，实现read/write lock。使得若干线程可以同时读取某共享数据区内的数据，但是在某一特定的时刻，只有一个线程可以向该共享数据区写入数据。

完成情况

（基于时间片轮转调度，时间片长度随机。为了使得中断有可能在任何地方发生，在

reader函数和writer函数所有的代码语句后面都调用了interrupt->onetick） 修改情况：

增改变量及函数 变量： Lock mutex Lock w 简单解释 Mutex用于保护共享变量rc（记录读者数量） W用于读者和写者访问临界区的互斥性 10

Reader函数 1. Mutex上锁 2. Rc加1。如果rc等于1，w上锁 3. Mutex解锁 4. 读操作 5. Mutex上锁 6. Rc减1。如果rc等于0，w解锁 Mutex解锁 Writer函数 1. W上锁 2. 写操作 3. W解锁 测试函数： 新建一个写者和两个读者，并且让他们分别写（读）10次。

测试结果截图：

Mutex保护共享变量rc，因为可以允许多个读者处于读状态，因此rc可能会被多个读者同时访问，需要保护起来。 W互斥读者和写者，第一类读写者问题是读者优先，因此若临界区内有读者，写者就会被w阻塞在临界区外，直到所有读者离开临界区。 写者能够进入临界区当且仅当临界区内没有读者。但写者在临界区内的时候，读者不能进入。 读者可以同时读。（start和finish之间可以认为是临界区）

写者在临界区里时，即使发生了interrupt（线程切换），也无法让读者进入。即读者和写者不能同时访问临界区

11

三：遇到的困难以及解决方法

困难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的值虽然在变化，但i的地址是不变的，所以读出来总会等于最后一个加入队列的值。之后专门创建了一个buffer数组，使得不同的值对应不同的地址，问题就解决了。

困难4：一开始是用lock的acquire和release实现condition，但测试函数结果和预期的不相符

解决方式：经过研究，我发现，造成错误的原因，是lock的release函数，会使得value值增加。这就意味着，即使等待信号的队列为空，signal函数也会释放一个资源。这样之后，若还有wait函数调用，就不会被阻塞，而是直接通过。这不符合管程中wait和signal的语义（我查了上学期操作系统的课件，课件上说，若是等待队列为空，则signal函数为空操作）。于是我将Lock换成了队列，当队列不为空的时候才让signal和broadcast函数起作用。

四：收获及感想

这次的lab消耗了比预期多的时间，主要问题在于condition的实现。需要仔细了解了管程机制之后，才知道如何编写。详情可参看【困难4】。此外，测试函数也需要开动脑筋，

12

不仅需要写出来，而且还要通过合适位置的输出，来判断程序是否按照自己预期的样子运行。这个过程同样需要对同步机制有较好理解，才能理清楚。

做了这次lab，觉得自己对于同步机制又多了一层了解，而且代码和报告均是自己独立完成，没有参考网上前人的报告，觉得挺高兴的！

内容五：参考文献

[1]陈向群 同步机制 操作系统课件2014版

[2]linux同步机制 网络博客

[3]小组成员：王丰 condition的实现方式 讨论

13

本文来源：https://www.bwwdw.com/article/hiy6.html