1、信号量

1.1 信号量的基本结构

关于如何使用信号量来设计生产者 - 消费者模型这里不做介绍。本节主要是想通过生产者 - 消费者模型来理解信号量的基本结构。我们先看看信号量的基本结构：
首先信号量是一个结构体

struct semaphore{
	char *name;// 信号量的名字（这个其实可有可无）
    int value; // 记录资源个数,就像 empty 一样。这个值不一定非要大于等于0，也可以是小于0的数，在后文有解释。
    PCB *queue;// 记录等待在该信号量上的进程，方便之后进行唤醒。可以理解这是个队列，里面可以记录很多线程。
};

然后就是对信号量的操作（P/V 操作。其中P是指消费者，会消费资源；V是指生产者，会生产资源）

P(semaphore s){
    s.value--;
    if(s.value < 0) 
    	sleep(s.queue);  // 将当前线程睡眠，并将当前线程记录到 s.queue 队列中
}

V(semaphore s){
    s.value++;
    if(s.value <= 0)
    	wakeup(s.queue);// 唤醒 s.queue 队列中的线程。
}

有了信号量的基本结构后，我们在通过生产者 - 消费者模型来理解信号量的基本结构。为了方便分析，下面的信号量不使用结构体定义，信号量的操作函数（P、V）也是直接内联到代码中，下面代码中定义的互斥锁，是为了保护临界资源，至于互斥锁的实现原理个人认为应该和 1.2节：信号量临界区保护类似。

#define BUFFER_SIZE 10      
item buffer[BUFFER_SIZE];  // 循环队列，队尾入，队首出（临界资源）
int in = out = 0;          // in为队尾，out为队首

int empty = BUFFER_SIZE;   // empty为队列中空位置的个数（信号量）
int full = 0;              // full为队列中的元素个数（信号量）
mutex_def mutex;           // 互斥锁

生产者进程不断生产 item，并将其存放到 buffer 队列中，消费者进程则不断从 buffer 队列中“消费” item。为了保证生产者进程和消费者进程能够有序推进，可以将它们设计为如下形式：

/*******生产者进程*******/
while (true) {
	empty--;      // P 操作，生产者消费 buffer 中的空位置
    if(empty < 0)//若队列中已经没有空位置了则生产者停下
    	sleep(生产者进程);
    	
    mutex.lock();   // 上锁，这里上锁仅仅是为了确保只有一个线程执行下面两条语句
    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
    mutex.unlock();   // 解锁
    
    full++;       // V 操作，生产者生产资源并放如了 buffer 中
    if(full <= 0)// 想想这里 full<=0 是什么意思？
    	wakeup(消费者进程);
}
/*******消费者进程*******/
while (true) {
	full--;
    if(full < 0) // 若队列为空则消费者停下
    	sleep(消费者进程);
    	
    mutex.lock();   // 上锁
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
	mutex.unlock();   // 解锁
	
    empty++;
    // empty<=0 表示队列已经满了，目前还有生产者进程处于睡眠状态，但是现在已经有1个空位置了（empty++ 产生了一个空位置），因此需要唤醒一个生产者进程。
    if(empty <= 0)
    	wakeup(生产者进程);
}

程序中的 empty 和 full 就是两个信号量。这里以 empty 为例来分析信号量。在上面的程序中 empty 有2个功能：（1）记录队列中空位置的个数；（2）根据 empty 的值来决定是否睡眠或唤醒生产者进程。什么是信号量? 记录一些信息(量)，并根据这个信息决定睡眠还是唤醒(信号)。可以看出信号量有两个部分，量用来记录，信号用来sleep和wakeup。 相对于信号只有“有“或者”无“两种含义来说，信号量有着更多的含义。empty 的值有三种情况：

1. empty > 0，表示 buffer 中还有 empty 个空位置；
2. empty == 0，表示 buffer 中已经没有空位置（队列已满）；
3. empty < 0，表示 buffer 中还缺 empty 个空位置，即有 -empty 个进程需要向 buffer 存放生产好的 item，不过 buffer 已经没有空位置了，所以这 -empty 个进程会进入睡眠状态；

1.2 信号量临界区保护

在上一节的 P\V 操作中， s.value-- 和 s.value++ 在CPU中并不是一条指令完成的。如 s.value-- 可能是由几条指令组成：

register = s.value;  // register为寄存器
register = register - 1;
s.value = register;

若几个进程同时调用了 P 操作，那么 s.value 运算结果可能就会产生错误。因此对 value 的加减运算应该加锁，即以上的3条指令应该一次完成，中间不能被打断。对信号量临界区的保护有3种方式：

1. 面包店算法。可以有纯软件实现，缺点就是效率低
2. 开关中断。在对 value 进行加减运算前，关闭中断，防止切换到其他进程，在运算结束后再打开中断。这个办法实现起来简单一些，但是只能再单CPU系统中使用，对于多CPU系统不适用。
3. 硬件原子指令法。做一条硬件指令，用来检测锁是否已经被锁上。这种方式可以用于多CPU系统，但是这个需要硬件支持。如下图所示，TestAndSet() 为一条指令，函数内的操作都是一条指令完成，该函数用于检测锁是否已经被锁上。

1.2.1 轮换法

1.2.2 Peterson算法

结合了标记和轮转两种思想

标记为1，并且该1就1执行

1.2.3 面包店算法

1.2.4 关中断

1.2.5 硬件原子指令法

用临界区保护信号量，用信号量实现线程同步

2、Linux0.11中的进程同步案例

Linux0.11 中虽然没有实现信号量，但是有进程同步的地方。本节以 Linux0.11 中读磁盘的程序为例，看看 Linux0.11 中是如何做到进程同步的。下面是关于 Linux0.11 访问磁盘的介绍：

Linux 0.11访问磁盘的基本处理办法是在内存中划出一段磁盘缓存，用来加快对磁盘的访问。进程提出的磁盘访问请求首先要到磁盘缓存中去找，如果找到直接返回；如果没有找到则申请一段空闲的磁盘缓存，以这段磁盘缓存为参数发起磁盘读写请求。请求发出后，进程要睡眠等待（因为磁盘读写很慢，应该让出CPU让其他进程执行）。这种方法是许多操作系统（包括现代Linux、UNIX等）采用的较通用的方法。 ——摘取自实验指导书

发出读写请求的函数是由 make_request() 完成的，make_request() 中会调用 lock_buffer() 使进程进入睡眠。 lock_buffer() 函数如下：

// bh 为申请的内存缓冲区，bu中还有一个锁 b_lock，用于标记缓冲区是否被锁定
static inline void lock_buffer(struct buffer_head * bh){
    cli();                 		// 关中断
    while (bh->b_lock)  		// 若 b_lock == 1 则进入睡眠
    	sleep_on(&bh->b_wait);  // 将当前进程睡眠在bh->b_wait
    bh->b_lock=1;          		// 缓冲区上锁
    sti();                	 	// 开中断
}

可以看出Linux0.11是利用开关中断来保护信号量临界区的。sleep_on函数如下：

// p 是等待队列的队头指针
void sleep_on(struct task_struct **p){
	struct task_struct *tmp; // 注意tmp是再内核栈中，而每一个进程都有一个内核栈。
...
	tmp = *p;     //tmp指向队头
	*p = current; //p指向当前指针
	current->state = TASK_UNINTERRUPTIBLE;   // 将当前进程设为阻塞态
	schedule();   //切到下一个进程去执行
	// 当前进程被唤醒后，就会从这里重新开始执行。若 tmp 不为空则将tmp进程改为就绪态。
	// 当tmp变为运行态后，又会从这里开始执行，从而又唤醒tmp的下一个进程，如此往复
	// 直到将等待队列中的全部进程全部唤醒。
	if (tmp)     
		tmp->state=0;
}

sleep_on() 比较难理解，其是它是通过 tmp 这个局部变量来形成一个等待队列的。看看下面这个图就容易理解了：

当请求成功，并获取到磁盘内容后，磁盘会引发系统中断来唤醒请求的进程：

static inline void unlock_buffer(struct buffer_head * bh){
...
    bh->b_lock = 0;       // 解锁缓冲区
    wake_up(&bh->b_wait); // 唤醒请求磁盘的进程
}

wake_up() 的实现如下：

void wake_up(struct task_struct **p){
	if (p && *p) {
		(**p).state=0;  // 将 p 置为就绪态
		*p=NULL;
	}
}