# 同步原语

#### 自旋锁SpinLock的实现

​		自旋锁是实现信号量等其他同步原语的基本，因此首先需要利用硬件同步指令实现自旋锁。实现方法也是比较简单的，我们将自旋锁封装成类，内部存储`lock`变量，对外提供三个操作，`TryLock`，`Unlock`，`Lock`，与硬件提供的方法进行对应。我们使用的硬件的方法为TestAndSet，即尝试原子地设置内存为某个值并返回旧值，编译器为我们提供了`__sync_lock_test_and_set`调用。

* TryLock：调用一次TS，如果成功修改，则表明上锁成功，否则返回失败
* Unlock：调用编译器提供的`__sync_lock_release`原子地将`lock`变量清0
* Lock：不断TryLock直至成功（即自旋）

###### 应用场景

​		自旋锁由于由忙等开销，一般用于实现其他更强大的同步对象，如信号量。直接使用它进行保护容易导致当前时间片的浪费（不过在多核之间则可以有效提升性能）。



#### 信号量Semaphore的设计与实现

​		信号量是一个非常强大的同步工具，可以组合出各式各样的用法。在我们设计中信号量的成员如下：

###### 枚举标志：作为调用信号量方法时的参数传入，表示特殊的功能

* TryWait：尝试等待，如果无法获取资源就返回
* KeepWait：保持等待，为Wait的默认参数，一直等到成功获取资源为止
* SignalAll：唤醒在此信号量上等待的所有进程
* SignalOne：唤醒一个等待的进程

###### 内部保护成员

* Head、Tail：信号量所维护的等待链表，目前采用的时FIFO唤醒顺序
* value：信号量内部所维护的资源值

###### 公开成员函数

* Wait：等待并获取信号量的一个资源，参数默认为一直等待，可以传入尝试等待，也可以传入一个非0值表示等待的时长，如果这么长时间内无法获取资源，则返回`false`，成功获取资源后返回`true`
* Signal：唤醒在此信号量上等待的进程，默认参数为1，可以传入枚举标志来唤醒所有，或传入一个正整数表示需要唤醒的数量。如果想唤醒的数量大于等待的进程的数量，则多余的资源会累加到信号量中。
* Value：获取信号量当前的值，尽管获取到值后可能立刻失效，不过可以用于需要预估资源数等的场合。
* ~Semaphore：信号量的析构函数，析构时会自动唤醒所有正在等待的进程。
* Semaphopre：信号量的构造函数，将资源数初始化为某个给定值。此外，拷贝构造函数、移动拷贝构造/赋值类的函数均表明了delete关键字，表明禁用这一功能，防止误用。



###### 信号量Wait的实现方法

​		总体上与各类OS课本上描述的一致。首先所有要操作的部分都要处于关中断和全局进程自旋锁的保护下。然后尝试获取资源，如果资源数不够，根据参数的标志位，判断是否要直接返回`false`还是进行等待。如需要等待，信号量将当前进程加入自己的等待队列尾部并设置进程为`S_Sleeping`。这个等待队列的结点是进程对象的一部分，因为我们考虑到一个进程只可能在一个信号量上等待，如果需要等待多个，也可以用信号量的组合来实现。

​		如设置了超时，则额外设置超时目标时间，在超过这个时间点后调度器会强制解除进程的阻塞态。结束阻塞后，信号量需要将进程从当前的等待队列中移除。不过如果是因为超时返回的，需要返还一个资源计数。

###### 信号量的Signal实现方法

​		首先还是要保护中间处理的过程。如果是要唤醒所有，则唤醒数量会自动设为等待的进程数量。信号量的值然后会加上提供的资源数，随后唤醒不超过提供的资源数个在等待的进程，即将它们设为`S_Ready`并等待调度器调度。

###### 信号量的拓展功能

​		我个人而言是很喜欢信号量的设计的，实现了信号量之后，我们就可以移植我先前封装过的Windows和Linux平台上的`Barrier`和`MultiSemaphore`控制类了，来为我们的系统提供更多强大的功能，不过考虑到时间关系暂时还未移植。

​		在我们的设计中，父进程等待子进程也是用信号量实现的，大体思路为获取已结束的进程中和所需相同PID的子进程，如果获取得到则返回，获取不到则使用信号量等待子进程唤醒。具体流程可以见0x31文档的等待子进程部分。

​		此外，`sleep`系统调用我们也是使用信号量实现的，因为我们的信号量支持超时返回功能，因此如果一个进程需要`sleep`，那么可以创建一个初值为0的信号量，并在上面`Wait`所需的时长，而不使用`Signal`功能。当然，如果要实现等待事件等功能都可以类似的用信号量完成。



#### 互斥锁Mutex的实现

​		互斥锁我们没有额外重新实现，而是使用了信号量，将初值设为1，这样就可以作为互斥锁来使用了。`Wait`操作即`Lock`，`Signal`操作即`Unlock`。不过对于递归锁这样的特殊要求的锁，可能后面还是要重新设计。



---------------------

By：qianpinyi

2022.06.05