6.1 Semaphores

:material-circle-edit-outline: 约 701 个字 :fontawesome-solid-code: 25 行代码 :material-clock-time-two-outline: 预计阅读时间 3 分钟

操作系统（本）2024-11-05 第 7-8 节

Semaphores（信号量）

ch6 Process Synchronization.pdf

【操作系统】信号量机制 - 华仔要长胖 - 博客园

我们直接讲记录型信号量：信号量（Semaphores）的数据结构由一个值 value 和一个进程链表指针 L 组成，信号量的值代表了资源的数目，链表指针链接了所有等待访问该资源的进程。

信号量就是一个整型计数器，记录当前可用资源的数量

信号量 S 用于互斥，S.value 初值为 1。

PV 操作

通过对信号量 S 进行两个标准的原子操作 wait(S)和 signal(S)，可以实现进程的同步和互斥

这两个操作又常被称为 P、V 操作，其定义如下：

P(S) wait
- 将信号量 S 的值减 1，即 S.value = S.value-1；
- 如果 S.value≥0，则该进程继续执行
- 否则该进程置为等待状态，排入等待队列。
V(S) signal
- 将信号量 S 的值加 1，即 S.value = S.value+1；
- 如果 S.value > 0，则该进程继续执行；
- 否则释放 S.L 中第一个的等待进程。

实际上，S.value 代表可用的资源数目，当它的值大于 0 时，表示当前可用资源的数量；当它的值小于 0 时，其绝对值表示等待使用该资源的进程个数。

P 意味着请求分配一个单位资源，S.value 减 1，当 S.value < 0 时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。
V 操作意味着释放一个单位资源，因此 S.value 加 1；若 S≤0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

整型信号量

信号量 S 就是一个于代表资源数目的整型量，没有进程链表，无法实现“让权等待”的准则。

[!TIP] 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态

Counting semaphore （计数信号量）
- value 随便取值

Binary semaphore（二值信号量）
- value 只能取 0 和 1，也叫 mutex locks

 Semaphore mutex;    //  initialized to 1
 do {
     wait (mutex);
     // Critical Section
     signal (mutex);
     // remainder section
 } while (TRUE);

这是一个 spinlock

记录型信号量

就是我们一开始定义的

typedef struct {
    int value;
    struct process *list;
} semaphore;

针对进程，我们增加了两个操作

block()
- place the process invoking the operation on the appropriate waiting queue.
  - 将当前进程放入等待队列
- running → waiting
wakeup()
- remove one of processes in the waiting queue and place it in the ready queue.
  - 将等待队列的进程放入就绪队列
- waiting→ready

相应地，wait(S)和 signa(S)操作可描述为：

wait(semaphore *S) { 
    S->value--; 
    if (S->value < 0) { 
        add this process to S->list; 
        block(); 
    } 
}

signal(semaphore *S) { 
    S->value++; 
    if (S->value <= 0) { 
        remove a process P from S->list; 
        wakeup(P); 
    }
}

Deadlock and Starvation

我没学

Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes

Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended

Priority Inversion - Scheduling problem when lower-priority process holds a lock needed by higher-priority process

Review Questions

P 申请，V 释放，两者要成对出现，上厕所总得出来是吧
就无法实现互斥了，和之前的算法一样，可以同时执行 P
循环检查条件是否成立，没成立就一直等待，不能完全避免，可以缓解
略，就是空闲处理机数量，注意小于 0 反映有进程在等，需要释放的同时马上给它

1-n
4
[-2,3]