信号量 Semaphore
信号量（Semaphores）机制被用作进程/线程间同步，且包括两个原语（primitive）， down 和 up 。
信号量机制最初由 Dijkstra 在 1965 年提出，在他原始的论文中，他使用 P 和 V ，分别表示荷兰语中的 Proberen （try）和 Verhogen （raise, make higher）对应
down和up。为了简化，我们统一采用down和up进行描述。
信号量相当于一个计数器，使用一个非负的整型变量来表示当前可用资源的数量。
假设一个进程每次只请求一个资源，当一个进程请求获取某个资源时，先要读取资源对应的信号量的值。
- 当信号量为 0 时， 表示当前没有资源可再被分配（因为其他进程已经占有完了所有可用资源了，因此当前进程会进入阻塞状态（blocked）。直到信号量大于 1 时，会被唤醒，且再次请求获取资源）；
- 当信号量大于 0 时，表示当前有资源可再被分配。因此当前进程可以成功获取到资源。这个进程通过调用
down操作，以实现获取资源，并将信号量减一（以标识当前可用资源少了一个）。- 当该进程不再使用这个资源时，这个进程需要调用
up操作，以实现释放该资源，并将信号量加一（以标识当前可用资源多了一个）。 - 此后，若仍有一个或多个进程仍因等待可用资源的分配，而处于休眠状态时，内核会选择其中的一个进程以使其调用
up操作。
- 当该进程不再使用这个资源时，这个进程需要调用
从获取信号量的值、判断信号量的值（是否大于 0 ）到改变信号量的值（或者因为没有可分配的资源因而不改变信号量的值，最终进程休眠）的整个过程是一个原子操作（atomic action）。换句话说，当一个信号量操作（semaphore operation）开始后，其他进程都不能获取信号量直到这个信号量操作完成。
原子性是解决同步问题（synchronization problems）和避免竞态条件的基础。
信号量机制的实现
信号量中的两个原语（primitive）， down 和 up ，可以被实现为 down 和 up 两个系统调用（system call）。
对于单处理器系统，而操作系统可以通过在获取信号量或更新信号量（或将进程调度为休眠状态）的整个过程中禁用中断（disable interrupt）。
对于多处理器系统，信号量机制需要通过锁定变量（Lock Variables） + TSL 或 XCHG 指令实现。
信号量的分类
- Full semaphore：初始值为 0，记录当前已经被使用的资源的数量。
- Empty semaphore：初始值为系统可用资源的总数，记录当前可被使用的资源的数量。
- Binary semaphores （Mutex semaphores）：初始值为 1 ，且取值只能为 0 或 1 ，
二元信号量/互斥锁（Binary semaphores/ Mutexes）
取值只能为 0 或 1 ，初始值为 1 ，且可以被多个进程使用，以保证在同一时间只有一个进程进入临界区的信号量机制称为二元信号量（Binary semaphores），也称为互斥锁（Mutexes）。
二元信号量/互斥锁用来实现进程间的互斥。具体来说，当一个进程要即将进入临界区时，需要调用 down ，当它刚刚离开临界区时，需要调用 up ，最终互斥（Mutual Exclusion）得到了保证。
信号量的作用
信号量可以用于支持同步机制（synchronization）。而二元信号量/互斥锁（Binary semaphores/ Mutexes）是信号量的一个特例，二元信号量/互斥锁经常被用于实现多线程间的互斥（mutual exclusion）。
信号量（semaphore）是一种更高级的同步机制，mutex可以说是semaphore在仅取值0/1时的特例。Semaphore可以有更多的取值空间，用来实现更加复杂的同步，而不单单是线程间互斥。
Semantics and implementation
Counting semaphores are equipped with two operations, historically denoted as P and V (see § Operation names for alternative names). Operation V increments the semaphore S, and operation P decrements it.
The value of the semaphore S is the number of units of the resource that are currently available. The P operation wastes time or sleeps until a resource protected by the semaphore becomes available, at which time the resource is immediately claimed. The V operation is the inverse: it makes a resource available again after the process has finished using it. One important property of semaphore S is that its value cannot be changed except by using the V and P operations.
A simple way to understand wait (P) and signal (V) operations is:
- wait: Decrements the value of semaphore variable by 1. If the new value of the semaphore variable is negative, the process executing wait is blocked (i.e., added to the semaphore’s queue). Otherwise, the process continues execution, having used a unit of the resource.
- signal: Increments the value of semaphore variable by 1. After the increment, if the pre-increment value was negative (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore’s waiting queue to the ready queue.
Many operating systems provide efficient semaphore primitives that unblock a waiting process when the semaphore is incremented. This means that processes do not waste time checking the semaphore value unnecessarily.
Example
Login queue
Consider a system that can only support ten users (S=10).
- Whenever a user logs in, P is called, decrementing the semaphore S by 1.
- Whenever a user logs out, V is called, incrementing S by 1 representing a login slot that has become available.
When S is 0, any users wishing to log in must wait until S > 0 and the login request is enqueued onto a FIFO queue; mutual exclusion is used to ensure that requests are enqueued in order. Whenever S becomes greater than 0 (login slots available), a login request is dequeued, and the user owning the request is allowed to log in.
Producer–consumer problem
Refer to https://swsmile.info/post/OS-Producer-consumer-problem/