操作系统设计中的核心问题是关于进程和线程管理：多道程序设计（单处理器系统中的多个进程）、多处理技术（管理多处理器的多个进程）、分布式处理技术（管理多台分布式计算机中多个进程的执行）。支持并发进程的基本要求是加强互斥能力，可由操作系统或语言编译器支持的互斥解决方案。这里将讨论三种方法：信号量、管程和消息传递。
并发相关的关键术语：
| 术语 | 说明 |
|---|---|
| 原子操作 | 一个或多个指令的序列，对外是不可分的；即没有其他进程可以看到其中间状态或者中断此操作 |
| 临界区 | 是一段代码，在这段代码中进程将访问共享资源，当另外一个进程已经在这段代码中运行时，这个进程就不能在这段代码中执行 |
| 死锁 | 两个或两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而不能继续执行，这样的情形叫做死锁 |
| 活锁 | 两个或两个以上进程为了响应其他进程中的变化而持续改变自己的状态但不能做有用的工作，这样的情形叫做活锁 |
| 互斥 | 当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源，这种情形叫做互斥 |
| 竞争条件 | 多个线程或者进程在读写一个共享数据时候，结果依赖于它们执行的相对时间，这种情形叫做竞争 |
| 饥饿 | 是指一个可运行的进程尽量能继续执行，但被调度器无限期的忽视，而不能被调度执行的情况 |
中断禁用：在单处理器机器中，并发进程不能重叠，只能交替。此外，一个进程将一直运行，直到它调用了一个系统服务或被中断。因此为保证互斥，只需要保证一个进程不被中断就可以了，这种能力可以通过系统内核为启用和禁用中断定义的原语来提供。
while(true) {
/* 禁用中断 */
/* 临界区 */
/* 启用中断 */
/* 其余部分 */
}由于临界区不能被中断，所以可以保证互斥。但是，该方法的代价非常高，由于处理器被限制于只能交替执行程序，因此执行的效率将会有明显的降低。第二个问题是该方法不能用于多处理器结构中，当一个计算机系统包括多个处理器时，就有可能（典型地）有一个以上的进程同时执行，在这种情况下，禁用中断是不能保证互斥的。
专用机器指令：在多处理器配置中，几个处理器共享内存。在这种情况下，处理器间的行为是无关的，表现出一种对等的关系，处理器之间没有支持互斥的中断机制。在硬件级别上，对存储单元的访问排斥对相同单元的其他访问。基于这一点，处理器的设计者提出了一些机器指令，用于保证两个动作的原子性。在一个取指周期中该指令执行的过程中，任何其它指令访问内存将被阻止。
CAS(compare and swap)，该指令用一个测试值（testval）检查一个内存单元（*word）。若该内存单元的当前值是testval，就用newval取代该值，否则保持不变。该指令的另一个版本返回一个布尔（boolean）值：交换发生时为真（true），否则为假（false），几乎所有处理器家族（x86、IA64、sparc、390等）中都支持该指令的某个版本。
int compare_and_swap(int* word, int testval, int newval) {
int oldval;
oldval = *word;
if (oldval == testval) *word = newval;
return oldval;
}共享变量初始化为0，唯一可以进入临界区的进程是发现bolt等于0的那个进程。所有试图进入临界区的其他进程进入忙等待模式。术语忙等待（busy waiting）或者（spin waiting）指的是这样一种技术：进程在得到临界区的访问权限之前，它只能继续执行测试变量的指令来得到访问权，除此之外不能做其他事情。当一个进程离开临界区时，它把bolt重置为0，此时只有一个等待进程被允许进入临界区。
/* program mutualexclusion */
const int n = /* 进程个数 */
int bolt;
void P(int i) {
while (true) {
while(compare_and_swap(bolt, 0, i) == 1)
/* 不做任何事情(进程自旋或忙等待) */;
/* 临界区执行代码 */
bolt = 0;
/* 其余部分 */
}
}
void main() {
bolt = 0;
parbegin(P(1), P(2), ,,,,P(n));
}专用机器指令的问题：1）使用了忙等待。因此，当一个进程正在等待进入临界区时，它会继续消耗处理器时间；2）可能饥饿，当一个进程离开一个临界区并且有多个进程正在等待时，选择哪一个等待进程是任意的。因此，某些进程可能被无限期地拒绝进入。3）可能死锁，进程P1执行专门指令（如compare&swap、exchange）并进入临界区，然后P1被中断并把处理器让给具有更高优先级的P2。如果P2试图使用同一资源，由于互斥机制，它将会被拒绝访问。因此，它会进入忙等待循环。但是，由于p1比p2优先级低，它将永远不会被调度执行。
现在转向讨论操作系统和用于提供并发性的程序语言设计机制，在解决并发进程问题的过程中，第一个重要的进展是1965年Dijkstra的论文[DIJK65]。Dijkstra参与了一个操作系统的设计，其基本原理是：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。为通过信号量s传送信号，进程可执行原语semSignal(s)；为了通过信号量s接收信号，进程可执行原语semWait(s)；如果相应的信号仍然没有发送，则进程被挂起，直到发送完为止。
为了达到预期的效果，可把信号量看做是一个具有整数值的变量，在它之上定义三个操作：
1）一个信号量可以初始化为非负数。
2）semWait操作使信号量减1。如果值变成负数，则执行semWait的进程被阻塞。否则，进程将继续执行。
3）semSignal操作使信号量加1。如果小于或者等于零，则被semWait操作阻塞的进程被解除阻塞。
struct semaphore {
int count;
queueType queue;
}
void semWait(semaphore s) {
s.count--;
if (s.count < 0) {
/* 把当前进程插入到队列当中 */
/* 阻塞当前进程 */
}
}
void semSignal(semaphore s) {
s.count++;
if (s.count <= 0) {
/* 把进程p从队列当中移除 */
/* 把进程p插入到就绪队列 */
}
}semWait和semSignal原语被假设是原子操作，其中二元信号量提供了更严格的形式，一个二元信号量的值只能是0或者1，可以使用下面三种操作：
1）一个二元信号量可以初始化成0或者1。
2）semWaitB操作检查信号的值，如果值为0，那么进程执行semWaitB就会受阻，如果值为1，那么将值改变为0，并且继续执行该进程。
3）semSignalB操作检查是否有任何进程在该信号量上受阻，如果有，那么通过semWaitB操作，受阻的进程就会被唤醒，如果没有进程受阻，那么值被设置为1。
struct binary_semaphore {
enum {zero, value} value;
queueType queue;
}
void semWaitB(binary_semaphore s) {
if (s.value == one)
s.value = zero;
else {
/* 把当前进程插入到等待队列当中 */
/* 阻塞当前进程 */
}
}
void semSignalB(binary_semaphore s) {
if (s.queue is empty())
s.value = one;
else {
/* 把进程p从等待队列中移除 */
/* 把进程p插入到就绪队列中 */
}
}不论是计数信号量还是二元信号量，都需要使用队列来保存在信号量上等待的进程。这就产生一个问题，进程按照什么顺序从队列中移出。最公平的策略是先进先出（FIFO），被阻塞时间最久的进程最先从队列释放。采用这个策略定义的信号量称之为强信号量（strong semaphore），没有规定进程从队列中移出顺序的信号量称之为弱信号量（weak semaphore）。对于相应的互斥算法，强信号量保证不会饥饿，而弱信号量不能保证。
互斥问题：使用信号量s解决互斥问题，设有n个进程，用数组表示P(i)表示，所有的进程都需要访问共享资源。每个进程中进入临界区前执行semWait(s)，如果s的值为负数，则进程被挂起；如果值为1，则s被减为0，进程立即进入临界区；由于s不再为正，因而其他任何进程都不能进入到临界区。
const int n = /* 进程数 */
semaphore s = 1;
void P(int i) {
while (true) {
semWait(s);
/* 临界区 */
semSignal(s);
/* 其它部分 */
}
}
void main() {
parbegin(P(1), P(2), ..., P(n));
}执行分析：假设有三个进程（A、B、C）访问一个受信号量lock保护的共享资源。进程A执行semWait(lock);由于信号量在本次semWait操作时为1，因而A可以立即进入临界区，并把信号量的值置为0；当B和C都执行semWait(lock)时候，信号量数值变为-2，两个进程都处于阻塞的状态。当A进程执行完成后调用semSignal()操作，会将信号量值+1 ，同时从阻塞队列中取出阻塞时间最长的B，之后执行B相关的业务逻辑。
生产者/消费者问题：分析一种在并发处理中最常见的一类问题：生产者/消费者问题，描述如下：有一个或多个生产者生产某种类型的数据（记录、字符），并放置在缓冲区中；有一个消费者从缓冲区中取数据，每次取出一项；系统保证避免对缓冲区的重复操作，也就是说，在任何时候只有一个主体（生产者或消费者）可以访问缓冲区。问题要确保这种情况：1）当缓冲区已满时，生产者不会继续向其中添加数据；2）当缓冲区为空时，消费者不会从中移走数据。
/* program producerconsumer */
int n;
binary_semaphore s = 1, delay = 0;
void producer() {
while (true) {
produce();
semWaitB(s);
append();
n++;
if (n == 1) semSignalB(delay);
semSignalB(s);
}
}
void consumer() {
int m; /* 局部变量 */
semWaitB(delay);
while (true) {
semWaitB(s);
take();
n--;
m = n;
semSignalB(s);
consume();
if (m == 0) semWaitB(delay);
}
}
void main() {
n = 0;
parbegin(producer, consumer);
}使用二元信号量解决无限缓冲区生产者/消费者问题的正确方法，在consumer()通过引入辅助变量m解决消费者缓冲区中不存在的元素问题。
管程是一个程序设计语言结构，它提供了一种原始的但功能强大且灵活的工具，但更易于控制。管程的概念在[HOAR74]中第一次定义，管程结构在很多程序设计语言中都得到了实现，包括并发Pascal、Java等。其主要特点如下：
1）局部数据变量只能被管程的过程访问，任何外部过程都不能访问。
2）一个进程通过调用管程的一个过程进入管程。
3）在任何时候，只能有一个进程在管程中执行，调用管程的任何其它进程都会被阻塞，以等待管程可用。
通过给进程强加规定，管程可以提供一种互斥机制：管程中的数据变量每次只能被一个进程访问到。因此，可以把一个共享数据结构放在管程中，从而提供对它的保护。如果管程中的数据代表某些资源，那么管程为访问这些资源提供了互斥机制。
/* program producerconsumer */
monitor bounderbuffer;
char buffer[N]； /* 分配N个数据项空间 */
int nextin, nextout; /* 缓冲区指针 */
int count; /* 缓冲区中数据项的个数 */
cond notfull, notempty; /* 为同步设置的条件变量 */
void append(char x) {
if (count == N) cwait(notfull); /* 缓冲区满，防止溢出 */
buffer[nextin] = x;
nextin = (nextin + 1) % N;
count++;
/* 缓冲区中数据项个数增一 */
csignal(nonempty); /* 释放任何一个等待的进程 */
}
void take (char x) {
if (count == 0) cwait(notempty); /* 缓冲区空，防止下溢 */
x = buffer[nextout];
nextout = (nextout + 1) % N;
count --; /* 缓冲区中数据项个数减一 */
csignal(notfull); /* 释放任何一个等待的进程 */
}
{ /* 管程体 */
nextin = 0; nextout = 0; count = 0; /* 缓冲区初始化为空 */
}使用管程解决有界缓冲区的生产者、消费者问题的方法，如果没有进程在条件x上等待，csignal（x）的执行将不会产生任何效果。
void producer() {
char x;
while(true) {
produce(x);
append(x);
}
}
void consumer() {
char x;
while(true) {
take(x);
consume(x);
}
}
void main() {
parbegin(producer, consumer);
}进程交互时，必须满则两个基本要求：同步和通信。为实施互斥，进程间需要同步；为了合作，进程间需要交换信息，提供这些功能的一种方法是消息传递。消息传递还有一个优点，即它可在分布式系统、共享内存的多处理器系统和单处理器系统实现。
消息传递系统可以有多种形式，本节将给出关于这类系统典型特征的一般介绍。消息传递的实际功能以一对原语的形式系统：
send(destination, message)
receive(source, message)
这是进程间进行消息传递所需要的最小操作集。一个进程以消息（message）的形式给另一个指定的目标（destination）进程发送信息；进程通过执行receive原语接收消息，receive原语中指明发送消息的源进程（source）和消息。
-
列出与并发相关的四种设计问题？
答：进程之间的通信、资源的共享和竞争、多个进程活动的同步以及为进程分配处理器时间。
-
产生并发的三种上下文环境是什么？
答：多个应用程序、结构化应用程序、操作系统结构。
-
执行并发进程的最基本的要求是什么？
答：强制相互排斥能力。
-
列出进程间的三种互相知道的程度，并简单地给出各自的定义。
答：彼此不知道的进程，这些是独立独立的过程，不希望一起工作；进程间接相互了解，这些进程不一定通过各自的进程
id相互了解，但共享对某个对象（例如I/O缓冲区）的访问。进程彼此直接了解，这些进程能够通过进程id相互通信，并且旨在共同进行某些活动。 -
竞争进程和合作进程间有什么区别？
答：竞争进程需要同时访问同一资源，例如磁盘、文件或打印机。协作进程或者共享对一个公共对象（例如内存缓冲区）的访问权限，或者能够彼此通信，并且在某些应用程序或活动的执行中进行协作。
-
列出与竞争进程相关的三种控制问题，并简单地给出各自的定义。
答：相互排斥，竞争进程只能访问 { 都希望一次访问一个资源 } 的资源，互斥机制必须强制执行这项一次性政策。死锁，如果竞争进程需要互斥一个以上资源的访问权限，则如果每个进程都控制了一个资源并正在等待另一个资源，则可能发生死锁。饥饿，一组竞争进程中的一个可能会无限期地拒绝访问所需资源，因为该组中的其他成员正在垄断该资源。
-
列出对互斥的要求。
答：1）必须强制相互排斥，在具有相同资源或共享对象的关键部分的所有进程中，一次只能将一个进程放入其关键部分；2）在非关键部分停止的过程必须这样做，而不会干扰其它进程；3）可能无法无限期延迟需要访问的关键部分的进程：没有死锁或饥饿；4）当关键部分中没有任何进程时，必须允许任何请求进入其关键部分的进程；5）没有关于相对处理速度或处理器数量的假设；6）一个进程仅在有限时间内保留在其关键区域内。
-
在信号量上可以执行什么操作？
答：1）信号量可以初始化非负值；2）等待操作减小信号量值，如果该值变为负数，则执行等待的过程将会被阻塞；3）信号量操作会增加信号量的值。如果该值不是正数，那么将取消阻止由等待操作阻止的进程。
-
二元信号量和一般信号量有什么区别？
答：二进制信号量只能采用值
0和1，常规信号量可以采用任何整数值。 -
强信号量和弱信号量有什么区别？
答：强信号量要求使用先进先出策略解除对该信号量阻塞的进程，弱信号量并不指示解除阻塞的进程的顺序。
-
什么是管程？
答：管程是编程语言构造，提供抽象的数据类型和对一组过程的互斥访问。
-
对于消息、阻塞和无阻塞有什么区别？
答：有两个方面，发送和接收原语。在一个过程中执行发送原语时，有两种可能性：发送过程被阻塞直到收到消息为止，否则没有。同样，当进程发出接收原语的时，有两种可能性：如果先前已经发送一条消息，则接收该消息并继续执行。如果没有等待消息，则要么阻止该过程直到消息到达，要么继续执行该过程，放弃尝试接收。
-
通常与读者-写者问题相关联有哪些条件？
答：1）任何数量的阅读器都可以同时读取文件；2）一次只能有一个写入器可以写入文件；3）如果写入者正在写入文件，则没有读取者可以读取它。