我们现在知道，需要锁和条件变量来解决各种相关的、有趣的并发问题。多年前，首先认识到这一点的人之中，有一个就是 Edsger Dijkstra(虽然很难知道确切的历史)。 他出名是因为图论中著名的“最短路径”算法，因为早期关于结构化编程的论战 “Goto 语句是有害的”，还因为他引入了名为信号量的同步原语，正是这里我们要学习的。事实上，Dijkstra 及其同事发明了信号量，作为与同步有关的所有工作的唯一原语。你会看到，可以使用信号量作为锁和条件变量。
信号量是一个有正整数值的对象，在POSIX标准中，有
sem_wait()和sem_post()两个函数可以来操作它。信号量是需要初始化的，初始化后才可供使用。初始值的设置是很考究的，具体设为多少需要根据场景来决定。这里通过第三个参数将信号量s的值初始化为1。其中第二个参数是0，表示信号量在同一个进程的多个线程时共享的。
初始化信号量之后，我们就可以使用
sem_wait()和sem_post()两个函数来与这个信号量交互了。我们暂时先不关注这两个函数的具体实现，先关注如何使用这两个原语。这里需要注意这连个原语的使用：在调用sem_wait()的时候，信号量必须要大于等于1，否则它会将调用线程挂起。
而调用sem_post()时，它会直接增加信号量的值，如果有在等待的线程，则会唤醒其中一个。
同时，我们也可以得出，当这个值是负数时，这个值就是正在等待线程的个数，因为值是0的时候，表示有线程已经在使用这个信号量了，其它线程再调用
sem_wait()时会将其再减1，然后挂起。二值信号量(锁)
我们通过一个例子来使用信号量。将信号量作为锁，如下列代码所示，我们会用
sem_wait()和sem_post()来将临界区包围。举例来说明，假设我们现在有连个线程，T1和T2，T1调用
sem_wait()将信号量的值减为0。然后会立即返回(相当于执行了空函数)。接着进入临界区，随后再调用sem_post()，再将信号量重置为1，因为现在没有其它线程在等待，所以也不会唤醒其它线程。实际的过程如下表。信号量的值 | T1 | T2 |
1 | ㅤ | ㅤ |
1 | 调用 sem_wait() | ㅤ |
0 | sem_wait()返回 | ㅤ |
0 | (临界区) | ㅤ |
0 | 调用 sem_post() | ㅤ |
1 | sem_post()返回 | ㅤ |
如果现在发生了另一种情况，即在T1持有锁时(T1已进入临界区)，另一个线程T2调用
sem_wait()尝试抢锁。这种情况下T2把信号量的值从0减为-1，然后挂起等待。T1再次执行，随后调用sem_post()，将信号量的值增加到0，接着唤醒等待的线程1去抢锁。当线程1执行结束后，再把信号量的值恢复为1。下图展示了这个例子。
我们可以用信号量来实现锁了。且这个锁只有两种状态(持有和不持有)，所以这种用法有时也叫做二值信号量(binary semaphore)。实际这种信号量也有一些更简单的实现，我们这里使用了更为通用的信号量作为锁。
信号量来实现条件变量
之前我们学习了条件变量可以等待某一个条件满足后，等待线程再重新执行。这里我们也可以用信号量来实现条件变量。我们只需要将sem_wait()和sem_post()分开在不同线程中调用就可以了。
我们先看一下这个例子。父线程创建了一个子线程，然后等待它结束。
我们预期希望得到以下输出：
问题来了，我们该如何使用信号量来实现这个效果。其实我们从代码中已经看到了，父线程调用
sem_wait()，子线程调用sem_post()即可实现，但是在这个例子中，信号量的初始值应该设置成多少呢？(回想一下，然后再往下读)
这里的初始值应该设置成0，为什么呢？我们来试想一下这两种情况。
第一种父线程创建了子线程，但子线程还没有立即执行，随后父线程调用
sem_wait()，我们希望父线程等待子线程结束，所以初始值应该设置成0。
第二种情况，父线程创建了子线程后立即执行。子线程先调用
sem_post()(会将信号量从0加到1)，但是没有在等待的线程，所以什么都不会发生。然后当父线程有机会运行时，调用sem_wait()，会发现信号量的值变成1了，那么会立即返回(相当于执行了一个空函数)。
生产者/消费者(有界缓冲区)问题
我们在上一章的条件变量中也有提到这个问题，那时候是通过两个信号量empty和full分别表示缓存空了，或者满了，当时还用到了以下的get和put函数。
如下是我们使用信号量尝试解决有界缓冲区问题的版本
这个例子中，生产者会等待缓冲区为空，然后加入数据。相反的，消费者会等待缓冲区数据满了后在从中取出数据来消费。我们先假设MAX=1(数组中就只有一个缓冲区)来验证是否有效。
假设我们有两个线程，一个生产者和一个消费者，运行在同一颗CPU上的场景。消费者先运行，在调用sem_wait(&full)。因为初始时full的信号值是0，将其减为-1，然后睡眠，等待生产者线程调用sem_post(&full)将其填满，符合预期。
假设生产者随后就运行，执行到sem_wait(&empty)，因为empty的初始值是1，将其减为0，然后生产者线程继续执行，不会停止。生产者线程将数据加入到缓冲区，随后发出sem_post(&full)，将&full从-1加到1，表示缓冲区已满，然后唤醒刚刚在等待的消费者。
我们再把限制放宽一点，将缓冲区大小调大一点MAX=10，同时有多个生成者以及消费者线程。就会产生出竞态条件了。在没有提示的情况下，你可以发现是哪里产生的吗？如果没有发现的话，可以观察下put()和get()的代码。
我们来理解一下，假设两个生产者线程几乎同时在调用put()(这是有可能的，因为缓冲区的大小是10)， 生产者线程T1先运行，在put函数中执行了
buffer[fill] = value(假设现在fill是0)往缓冲区中加入了一条数据，此时发生了中断，切换到生产者线程T2运行，它也在put函数中执行了buffer[fill] = value，那么问题就出现了，生产者线程T1刚刚插入的数据就会被覆盖了！我们不允许这样的错误发生。解决方案：增加互斥
其实我们也看到了，这里忘记了加锁，我们需要加一把互斥锁，向缓冲区加入元素和增加缓冲区的索引是临界区，需要使用锁来保持原子性，这里我们继续使用二值信号量来新增一个锁，来解决这个问题，如下是代码。
这样我们就把锁加上了，但是，如果眼尖的话，会发现我们这样的话会造成死锁。想想看，为什么呢？答案是这样的，假设有两个线程，一个生产者和一个消费者，消费者先运行，将锁获取成功，然后继续获取信号量
sem_wait(&full)，因为现在缓冲区是空的，所以会挂起等待。注意，此时消费者是持有锁的。接着，生产者开始运行，如果它可以成功运行的话，那么他就可以生成数据，然后唤醒消费者。但重要的是，它无法运行，因为它获取不到锁。锁被生产者占用了，因此生产者只能挂起等待。这样就出现了循环等待的现象。消费者在等待full信号量，生产者可以发送full信号量，但是它却在等互斥量。这就是一个典型的死锁。
其实需要解决这个问题很简单，只需要调换下位置就行了。将锁的获取和释放紧挨着临界区即可
读者-写者 锁
这个问题来源于对更加灵活锁定原语的渴望，它认为不同的数据结构需要不同的锁。如一个并发链表同时会有很多个插入和查找，插入操作会修改链表的状态，而查找不会，所以，对于查找来说，可以执行多个查找。读者-写者(reader-write lock)就是来完成这种操作的。
这个锁的实现，写锁就是普通的互斥锁。亮点在于读锁，只要一个读者获取了读锁，那么它的兄弟，其它读者都可以蜂拥一起进入。(readers 会记录当前读者的数量)且第一个读者还会拿着写锁，防止这些读锁在读取的过程中数据发生了更改。当最后一个读者读完之后，会把写锁释放掉。
代码如下：
这个方案是可行的(符合预期)，但是有一个问题，那就是写锁可能会饿死。最后还要注意一点，这个读者-写者锁相比其它简单快速的锁方案，在性能上没有优势。
提示：简单的笨方法可能更好(Hill定律)
我们不要小看一个概念，即简单的笨方法可能最后。某些时候简单的自旋锁反而是最有效的，因为他容易实现且高效。虽然读者-写者锁听起来很酷，但是它更复杂，复杂也就意味着慢，因此，我们应该总是优先尝试简单的笨方法。
这种受简单吸引的思想，在多个地方都能发现。一个早期来于是Mark Hill的学位论文，研究CPU设计缓存。Hill发现更简单的直接映射缓存比花哨的集合关联性设计更加有效(其中一个原因是在缓存中，越简单的设计，查找的更快)。
Hill简单地总结了结论：”大而笨更好“。因为我们将这种类似的建议叫做Hill定律。
哲学家就餐问题
哲学家就餐问题(dining philosopher’s problem)，是一个著名的并发问题，它是由Dijkstra提出并解决的。这个问题之所以著名，是因为它很有意思，可是实用性其实不高。但是它很经典，它的名气以至于我们必须要在这里讲(就类似于学编程的经典题目：水仙花数)。
而且面试中很有可能会出现这道题，如果面试遇到了这道题，但却没做过，可能你会怪操作系统的老师没有没有教过这个题。
这个题的基本情况是：假定有5个”哲学家“围着一个圆桌，一共有5把餐叉，每两位哲学家之间有一把餐叉。哲学家有时候需要用餐，有时候会暂停下来思考一会，不需要餐叉。当哲学家需要进餐时，需要左手和右手一共拿到两把餐叉，才可以吃到东西。这个餐叉的竞争带来的同步问题，就是我们在并发编程中研究它的原因。
以下是每个哲学家的基本循环：
这个问题的关键在于getforks()和putforks()，保证没有死锁，就不会有哲学家饿死，并且并发度更高(尽可能让更多的哲学家吃到东西)。
根据Downey的解决方案，我们会用一些辅助函数，帮助我们构建解决方案。它们是：
当哲学家p希望用左手边叉子，就调用left(p)，当他希望调用右手边叉子，就调用right(p)。模运算解决了最后一个哲学家(p=4)右手边叉子编号的问题，就是餐叉0。
有缺陷的方案
我们来做第一次尝试，我们用5个信号量来做
sem_t forks[5]。假设我们把每个信号量都用1来初始化(在fork数组中)。同时每个哲学家都知道自己的编号。那我们就可以来完善getforks()和putfroks()函数，如下代码：初步来看，这个代码很好理解，但是它是有问题的。每个哲学家在就餐时，会依次先拿起左手边餐叉，再拿起右手边餐叉。释放的时候也是一样的顺序。看起来很简单，但其实是有问题的。
问题的关键在于会产生死锁(deadlock)。假设每个哲学家都拿到了左手边餐叉，那它们都会阻塞等待另一个餐叉。因为所有的餐叉都被占用了。后续我们会更深入的学习死锁，这里只需要知道这个方案是行不通的就可以了。
新方案：避免依赖
有一个最简单的方法可以来解决上述的问题，就是修改某个或某些哲学家的去餐叉顺序。实际Dijkstra自己也是这样解决的。具体来说，假设哲学家4(编号最大的一个)去餐叉的顺序不同。相应代码如下：
最后一个哲学家会尝试先拿右手边的餐叉，再拿左手边的餐叉，所以这样就不会出现所有哲学家都拿着餐叉。最差的情况下，哲学家4会拿不到餐叉，那它左手边的餐叉会被哲学家3获取。那么这个等待的循环就被打破了。
还有一些类似的很“著名”的问题，如吸烟者问题(cigarette smoker’s problem)，理发师问题(sleeping barber problem)，这些题有些名字很吸引人，它们也经常出现在一些考研的考题上。
如何实现信号量
最后，我们用底层的同步原语(锁和条件变量)，来实现自己的信号量，名字叫做Zemaphore。这很简单，如下：
可以看到，只使用了一个一个锁，一个条件变量和一个状态就实现了一个基础的信号量。
很奇怪，利用信号量来实现锁和条件变量，是棘手得多的问题。某些富有经验的并发程序员曾经在 Windows 环境下尝试过，随之而来的是很多缺陷[B04]。你自己试一下，看看是否能明白为什么使用信号量实现条件变量比看起来更困难。
使用select
3）采用1）中的分页存储管理方式，一个代码段的起始虚拟地址为0000 8000H，其长度为8KB,
被装载到从物理地址0090 0000H开始的连续主存空间中。
页表从主存0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增)。
请计算出该代码段对应的两个页表项的 物理地址、这两个页表项中的页框号，以及代码页面2的起始物理地址。
