Status
Done
实验目的
实验内容：
使用操作系统信号量机制，编写程序解决N线程屏障问题。
包括：
- 分析说明Nachos的信号量是如何实现的。
- 在Nachos中是如何创建及运行并发(而非线程自己主动调用Yield放弃CPU)线程的。
- 先按“The Little Book of Semaphores”中6.4小节中的代码实现N线程屏障。用不同的随机数种子seed测试(./nachos -rs seed)，是否会发现有可能多个线程均判定自己为最后一个到达的线程，这个现象是什么原因造成的？该现象会导致N线程屏障出现与有题目要求不一致的错误码？
- 请修改代码消除上面3中出现的现象。
- 用不同的随机数种子测试，是否会发现各线程打印输出的rendezvous行的顺序，基本就是线程被创建的顺序(0,1,2…9)的现象？这是为什么，难道-rs选项没有起作用？试验在打印输出rendezvous之前加延迟(用软件空循环耗时)或Linux的sleep能否解决此问题，并解释为什么。
- 请试着修改代码解决上面5出现的现象。提示：不用修改Nachos的核心实现代码，修改的是我们编写的N线程屏障的代码。
参阅：
"The Little Book of Semaphores V2.2.1 -Allen B. Downey 2016.pdf"，3.6.4
code/lab3/n3
code/lab3/n3readme.txt
code/lab3/n3screen.txt
“操作系统课程设计 指导教程 -张鸿烈 2012.pdf”，P39，2.2.4中的说明
code/demo1/
注1：若Lab3全部完成，演示提交的代码为6中完成的。
实验步骤与内容
分析说明Nachos的信号量是如何实现的
信号量 Semaphore
信号量的实现位于threads/synch的Semaphore类。
【synch.h】信号量的私有属性有信号量的值，它是一个阀门。线程等待队列中存放所有等待该信号量的线程。信号量有两个操作：P操作和V操作，这两个操作都是原子操作。
name定义了信号量的名称，用于调试；value是信号量的初始值，例如mutex互斥锁，该值应该为1；queue是等待该信号量配额的线程队列，当线程执行P操作但信号量的value为0时，线程阻塞，被加入到这个等待队列中，直到信号量被其他线程释放。queue的类型为List，是一个单链表的实现。
【synch.cc】P操作：
当value等于0时，
- 将当前运行线程放入线程等待队列。
- 当前运行线程进入睡眠状态，并切换到其它线程运行。
当value大于0时，value--。
【synch.cc】V操作：
如果线程等待队列中有等待该信号量的线程，取出其中一个将其设置成就绪态，准备运行。
value++;
锁机制 Lock
锁机制是线程进入临界区的工具。一个锁有两种状态，BUSY和FREE。当锁处于FREE态时，线程可以取得该锁后进入临界区，执行完临界区操作之后，释放锁；当锁处于BUSY态时，需要申请该锁的线程进入睡眠状态，等到锁为FREE态时，再取得该锁。实现位于threads/synch的Lock类。
【synch.cc】Acquire方法、Release方法
锁有两个操作Acquire和Release，它们都是原子操作。
Acquire | 申请锁：
当锁处于BUSY态，进入睡眠状态。
当锁处于FREE态，当前线程获得该锁，继续运行 |
Release | 释放锁（注意：只有拥有锁的线程才能释放锁）
将锁的状态设置成FREE态，如果有其它线程等待该锁，将其中的一个唤醒，进入就绪态。 |
条件变量 Condition
条件变量和信号量与锁机制不一样，它是没有值的。（实际上，锁机制是一个二值信号量，可以通过信号量来实现）当一个线程需要的某种条件没有得到满足时，可以将自己作为一个等待条件变量的线程插入所有等待该条件变量的队列；只要条件一旦满足，该线程就会被唤醒继续运行。条件变量总是和锁机制一同使用。
【synch.cc】条件变量有三个操作Wait、Signal以及BroadCast，所有的这些操作必须在当前线程获得一个锁的前提下，而且所有对一个条件变量进行的操作必须建立在同一个锁的前提下。
在Nachos中是如何创建及运行并发(而非线程自己主动调用Yield放弃CPU)线程的
首先分析一下demo1中的代码，测试运行代码结果如下：
【注意】此处使用的-rs参数是初始化随机种子，固定的随机中心，cpu产生中断就是一样的所以每次的数据结果都一样，要获得不一样的结果只需修改-rs参数的值即可，示例如下，具体原理在后面会讨论
ring
文件ring.cc和ring.h定义和实现了一个为生产者和消费者使用的环形缓冲类Ring。
1.【ring.h】 定义slot类和Ring类
2.【ring.cc】slot类的构造函数，用于初始化一个缓冲区槽对象。
thread_id：表示生产该消息的线程 ID。
value：表示消息的值。
此类仅用于存储一个消息的数据，字段包括消息的生产者 ID 和具体的值。
3.【ring.cc】Ring类方法的实现，包含构造函数、析构函数、Put方法、Get方法、Empty方法、Full方法
构造函数初始化缓存区的大小，in指向下一个可用的空槽位置，用于生产者放置消息；out指向下一个可读的槽位置，用于消费者取出消息。buffer动态分配一个slot 类型数组，作为环形缓冲区的存储。其中in和 out的移动会通过取模操作实现循环队列。
析构函数释放构造函数中分配的动态内存 buffer，避免内存泄漏。
prodcon++.cc
1.【prodcons++.cc】首先定义常量：
- 环形缓冲区大小为 3
- 生产者和消费者线程各有 2 个
- 每个生产者生产 5 条消息
- 名称长度、字符串缓冲区长度和文件名长度的限制
2.【prodcons++.cc】全局变量声明：
3.【prodcons++.cc】生产者线程函数
4.【prodcons++.cc】消费者线程函数
5.【prodcons++.cc】主函数 ProdCons
阐释nachos中如何创建并运行并发线程
创建线程并运行
由对demo1的代码分析可知，创建线程的步骤是先使用new Thread操作创建一个线程，然后调用其Fork方法，将该线程对应的函数和参数传入。
每个线程对应一个 Thread 对象，该对象记录线程的状态（如 READY、RUNNING、BLOCKED 等）以及与其执行相关的信息（如堆栈、上下文）
Fork 函数负责将线程添加到可调度队列并为其分配资源。
Nachos 的调度器（Scheduler）负责选择合适的线程并将 CPU 分配给该线程。
【以上详见Lab2】
Nachos中并发的实现机制
CPU 会在多个进程之间切换，在任一时刻，系统中有若干进程处在起点和终点之间，这些进程被认为是在运行着，这就是我们所说的并发处理。
Nachos 模拟并发的关键在于时间片轮转调度。时间片的时长由 Nachos 的计时器（
Timer）确定，可以是固定值或随机值。调度由以下模块完成：
1.计时器触发中断【machine/timer.cc】当时间片到期时，运行中断处理程序前，调用该方法获取下一次的时间，使用
interrupt->Schedule安排下一次中断的时间2.时间片的设定
【machine/sysdep.cc】如果使用-rs参数，使用其初始化随机数种子
【machine/timer.cc】调用随机算法指定下一个中断时间，否则使用一个固定的中断时间
3.线程切换
在Schedule中的Run函数内包括一行SWITCH语句
通过汇编指令切换上下文，而调用该函数的只有Thread的Yield和Sleep函数。
其中Sleep函数是线程结束后调用的，而Yield函数既可以由线程自己调用主动放弃CPU，也可以由Interrupt中的OneTick函数调用。而OneTick函数作为模拟前进的CPU时钟，会在特定时刻被执行，当发现当前时间为Schedule安排的下一次中断时间后，就调用当前线程的Yield函数，替当前线程放弃CPU，进行上下文切换，模拟了时间片到期进行上下文切换的过程。
【interrupt.cc】OneTick在时间片到期时调用Yield
OneTick会在两种情况下被调用：
- 在内核态下，由关中断切换至开中断时，OneTick会被调用。大致来看，管程、信号量、Fork和Yield的原子操作会涉及切换中断的操作。
- 在用户态下，Machine::Run不断的取指令，执行用户程序的指令，并调用OneTick。该函数在用户线程开始运行时执行，无限循环，永不返回。
对于用户线程，在虚拟机的帮助下，任何指令的执行都会更新系统时钟，Nachos可以很好地模拟真实的时间片长度，从而实现自然的并发。而对于系统线程，由于命令是在宿主机上执行的，Nachos没有办法为每一条指令更新系统时钟，只能通过统计开中断次数大致地模拟系统时钟的增加，在特殊情况下能够体现出并发。
对于实验二的系统线程，每个线程只会调用5次printf，不会更新系统时钟，自然也无法体现时间片轮转。然而实验三中N线程屏蔽会大量使用信号量操作，从而很好地驱动系统时钟，使得时间片轮转机制能够正常运作。
实现N线程屏障
先按“The Little Book of Semaphores”中6.4小节中的代码实现N线程屏障。用不同的随机数种子seed测试(./nachos -rs seed)，是否会发现有可能多个线程均判定自己为最后一个到达的线程，这个现象是什么原因造成的？该现象会导致N线程屏障出现与有题目要求不一致的错误码？
什么是N线程屏障？
N线程屏障（N-thread barrier）是一种同步机制，用于确保多个线程在达到某个点之前都会被阻塞，直到所有线程都到达该点后才能继续执行。它提供了一种线程同步的方式，以便在多线程环境中协调并发操作。
N线程屏障中的N表示参与屏障同步的线程数量。当N个线程都到达屏障位置时，屏障将打开，所有线程将被释放并可以继续执行后续的操作。如果有任何一个线程到达屏障位置之前发生阻塞（未到达屏障位置），则其他线程也会被阻塞，直到所有线程都准备好后才会继续执行。
测试运行
The Little Book of Semaphores可在下面的网址中下载阅读：
参考本书3.6.4 Barrier solutioon的内容，可知：
当每个线程通过时，它会向信号量发出信号量，以便下一个线程可以通过。
这种模式，即快速连续的 wait 和 signal，出现的频率足够高，以至于它有一个名字；它被称为turnstile，因为它允许一次通过一个线程，并且可以被锁定以阻止所有线程。
在初始状态 （零） 下，旋转门被锁定。第 n 个线程解锁它，然后所有 n 个线程都通过。
按照文档实现N线程屏障
1.新建threadsbar.cc文件
注意到在入口文件main.cc中，已经声明了ThreadsBarrier函数，并在启动线程时调用
2.在Makefile.local中添加
3.参考demo1定义数组及信号量
4.实现ThreadBarrier()方法
创建mutex信号量，用于互斥访问count，初值为1；创建barrier信号量作为屏障，初值为0。启动相应N_THREADS数量的线程：
5.按照文档3.6.4的内容实现BarThread(_int which)方法
测试分析
测试结果如下：
现在更换不同的seed来测试
发现有可能出现多个线程均判定自己为最后一个到达的线程的情况，如上图所示。
分析原因，可能是在对count==N_THREADS做判断时，count没有收到mutex信号量的保护，因此可能当thread7进行完count++后发生了上下文切换，由thread2执行上述过程，此时thread2执行到if语句，发现count==N_THREADS，判定自己为最后一个到达的线程，执行if内部的操作；之后thread7再次在CPU上运行时，由于此时判断条件依旧成立，所以thread7也认为自己是最后一个到达的线程。
修改代码消除上面出现的现象
出现这种现象的本质是修改count与执行if语句之间发生了上下文切换，只需要将这两个步骤设定为同一原子操作即可。把if语句移动到mutex解锁之前即可解决。
测试结果如下：
问题解决
rendezvous的顺序问题
用不同的随机数种子测试，是否会发现各线程打印输出的rendezvous行的顺序，基本就是线程被创建的顺序(0,1,2…9)的现象？这是为什么，难道-rs选项没有起作用？试验在打印输出rendezvous之前加延迟(用软件空循环耗时)或Linux的sleep能否解决此问题，并解释为什么。
用不同的随机数种子测试，确实会发现各线程打印输出的rendezvous行的顺序，基本就是线程被创建的顺序(0,1,2…9)的现象。
下面试验在打印输出rendezvous之前加延迟(用软件空循环耗时)或Linux的sleep能否解决此问题
在多次更换seed尝试中发现，并没有太大的变化，完全无法达到lab3screen所演示的效果
这是由于nachos中的每个系统线程实际上对应宿主机linux上的用户线程，线程的调度受到宿主机操作系统的管理。而如前文所述，nachos自身还模拟了一套线程上下文切换机制，在interrupt的OneTick函数中可被触发，该函数模拟时钟前进，并在模拟的时间片到期时通过主动调用当前线程的Yield函数强制使线程下CPU，以模拟时间片到期上下文切换的过程。Yield函数中调用了scheduler的Run函数，使当前nachos线程对应的宿主机的用户线程放弃CPU。
我们通过空循环耗时消耗的主要是当前线程对应的宿主机的用户线程的时间片，而非nachos中模拟的时间片。这导致-rs参数的不同对每个线程运行时消耗tick几乎没有影响，故无法达到预期的效果。我们应该拥抱nachos的模拟环境，通过nachos为我们提供的一系列模拟函数来模拟时间的前进。
方法：使用空循环耗时
未解决原因：Nachos线程运行时有3种状态，Idle状态、系统态、用户态。Idle状态中机器时钟会前进；系统态则是用户程序开中断一次增加10个tick；用户态则是执行一条用户指令增加1个tick。而在本次实验中，线程只有Idle状态和系统态的转换，使用空循环属于增加用户态的tick，对于本次实验中的总时钟前进无效。
方法：使用Linux中的sleep
未解决原因：Linux中的sleep作用对象为线程，而Nachos中是实例化Thread类对象并使用fork创建模拟线程，即Nachos上创建的并不是真正的线程。使用Linux中的sleep只会对Linux中真正的线程nachos起作用，但不会对Nachos中模拟线程运行的总时钟前进起到任何作用。
解决上述问题
1.添加MakeTicks函数
2.在BarThread函数中调用MakeTicks
得到与预期相同的测试结果！
在实验过后我查看了老师提供的实现代码：
这段代码是通过不断切换中断状态（从关闭到打开），模拟 Nachos 系统中多个时钟 tick 的推进，【interrupt.cc】而在setLevel中实则是调用了OneTick来实现时钟前进，因此原理是一样的。
结论分析与体会
在实验中，我首先深入学习了Nachos系统中信号量的实现原理，了解了其核心操作P和V的逻辑以及如何在操作系统中实现线程间的同步与互斥。此外，还掌握了Nachos创建和运行并发线程的基本流程。通过这些知识的积累，为实验后续任务打下了基础。
接着，根据《The Little Book of Semaphores》中关于并发控制的相关内容，我尝试实现了一个简单的N线程屏障问题。在实验指导书的分步提示下，我逐步发现最初实现中的问题，并逐步优化代码。
实验过程中，通过测试，我观察到Nachos模拟环境与真实操作系统的运行机制存在显著差异，尤其是时钟前进的行为。在真实系统中，时钟是硬件自动推进的，而在Nachos中，需要通过调用
OneTick函数手动推动时钟。通过这一特性，我在模拟环境中成功解决了线程同步的时钟问题，完成了实验目标。