并发是所有问题的基础，也是操作系统设计的基础。
和并发的相关的关键术语
临界区： 是一段代码，在这段代码中进程访问共享资源，当另一个进程已在这个代码中运行，其他进程不能在这段代码中执行。
忙等待：进程得不到共享资源时，仍不主动放弃CPU，不断检测资源是否可用，尽管CPU可能被剥夺，被其它进程抢占，因而是低效的。
阻塞式等待：进程得不到共享资源时将进入阻塞状态，让出CPU给其他进程使用，因而是高效的。
饥饿：指一个可运行的进程尽管能继续运行，但被调度器无限期地忽视，而不能被调度执行的情况。
死锁：两个或两个以上的进程因为其中的每个进程都在等待其他进程做完某些事情而不能继续执行。例如线程T1 获得了资源R1，线程T2 获得了资源R2，然后，T1申请获得资源R2，同时T2 申请获得资源R1。此时，两个线程将永久阻塞，死锁的情况就出现了。
活锁：两个或两个以上的进程为了响应其他进程中的变化而继续改变自己的状态，但不做有用的工作。 考虑一台打印机分配的例子，当有多个进程需要打印文件时，系统按照短文件优先的策略排序，该策略具有平均等待时间短的优点，似乎非常合理，但当短文件打印任务源源不断时，长文件的打印任务将被无限期地推迟，导致饥饿。在忙式等待条件下发生的饥饿，称为活锁。
互斥：当一个进程在临界区访问共享资源时，其他进程不能进入临界区访问任何共享资源。
竞争条件：多个线程或者进程在读写一个共享数据时结果依赖于它们执行的相对时间。
系统资源：
1.处理器时间；2.存储器；3.文件；4.I/O设备。
进程交互：
| 关系 | 一个进程对其他进程的影响 | 潜在的控制问题 | 举例 | |
| 进程间相互不知道对方 | 竞争 |
1.一个进程结果与其他进程的活动无关 2.进程的计时可能会受到影响 |
1.互斥 2.死锁（可复用的资源） 3.饥饿 |
每个进程都不影响所使用资源的状态。 I/O设备、存储器、处理器时间 |
| 进程间接知道对方 | 通过共享合作 |
1.一个进程结果可能依赖于从其他进程获得的消息 2.进程的计时可能会受到影响 |
1.互斥 2.死锁（可复用的资源） 3.饥饿 |
由于进程可能对共享数据的状态的修改，进程必须保持合作，确保共享数据的完整性。 因为数据保存在资源中，所以要涉及到互斥；但是有两种模式（读和写）访问共享数据， 只有写操作必须保持互斥。 共享变量、共享文件、数据库 |
| 进程直接知道对方 | 通过通信合作 |
1.一个进程结果可能依赖于从其他进程获得的消息 2.进程的计时可能会受到影响 |
1.死锁（可消费的资源） 2.饥饿 |
消息传递过程中，没有共享任何对象，所以不需要互斥。 |
互斥实现
1.硬件支持
1.1中断禁用
由于一个进程运行，直到调用了一个操作系统服务或中断。因此互斥只需保证进程在临界区不被中断就可以了，可通过系统内核为启用中断和禁用中断的原语来实现。
缺点：代价高；仅适合单处理器，不适合多处理器；
1.2专用机器指令
testset指令
testset操作是原子的，不可被中断。实现原理如下:
boolean testset(int i) { if(i == 0) { i = 1; return true; } else return false; }
echange 指令
echange操作是原子的，不可被中断。实现原理如下:
void exchange(int register, int memory) { int temp; temp = register; register = memory; memory = temp; }
机器指令方法的特点：
1）.适用于在单处理器或共享内存的多处理器上的任何数目的进程。
2）.简单。
3）.可支持多个临界区，每个临界区都有自己的变量的定义。
机器指令方法的缺点：
1）.使用了忙等待，效率低。
2）.可能饥饿。多个进程等待进入一个临界区的时候。
3）.可能死锁。如果p1进入临界区setction，后来p1被中断，中断处理后，切换到进程p2，可是p2也要访问临界区section中的资源。由于互斥机制，p2被拒绝访问，进入忙等待循环。
2.信号量
基本原理；两个或两个进程可以通过简单的信号进行合作，一个进程可以被迫在某个位置停止，直到它收到一个特定的信号。
信号量可以看做是一个具有整数值的变量，共定义三个操作：
1）. 一个信号量可以初始化为非负变量。
2）.semwait使信号量减1。如果变成负数，则执行semwait的进程被阻塞，否则，进程继续进行。
3）.semsignal使信号加1。如果小于等于0，则被semwait阻塞的进程被解除阻塞。
二元信号量
1）. 一个信号量可以初始化为1或0。
2）.semwait，如果信号量为1，信号量变为0，进程继续进行。如果信号量为0，进程被阻塞。
3）.semsignal，如果队列为空，信号量变为1。否则，从队列取出一被阻塞的进程，改为就绪状态。
信号量用于生产者/消费者问题
问题描述：有一个或多个生产者产生某种类型的数据（记录、字符），并放置在缓冲区中；有一个消费者从缓冲区中取数据，每次取一项。系统保证避免对缓冲区的重复操作，也就是任一时刻只有一个消费者或生产者可以访问缓冲区。
方法1.二元信号量解决无限缓冲区生产者消费者
int n; binary_semaphore s = 1; binary_semaphore e = 0; void produce() { while(true) { produce(); semWaitB(s); append(); n ++; if(n == 1) semSignalB(e); semSignalB(s); } } void consumer() { while(true) { semWaitB(e); semWaitB(s); take(); n --; m = n; semSignalB(s); consum(); if( m == 0) semWaitB(e); } } void main(） { n = 0; parbegin(producer, consumer); }
方法2.计数信号量解决有限环形缓冲区生产者消费者
int n; semaphore s = 1; semaphore n = 0; semaphore e = sizeofbuffer; void produce() { while(true) { produce(); semWait(e); semWait(s); append(); semSignal(s); semSignal(n); } } void consumer() { while(true) { semWait(n); semWait(s); take(); semSignal(s); semSignal(e); consum(); } } void main(） { n = 0; parbegin(producer, consumer); }
管程
管程是由一个或多个过程，一个初始化序列和局部数据组成的软件模块。其特点是
1）.局部数据变量只能被管程的过程访问。
2）.一个过程通过调用管程的一个过程进入管程。
3）.任何时候，只有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变为可用。
管程提供的互斥机制：任何时候，管程的数据变量只有一个进程可以访问到。
管程仅仅提供互斥操作是不够。线程可能需要等待某个条件
为真，才能继续执行。在一个忙等待(busy waiting)循环中
while not( ) do skip
将会导致所有其它进程都无法进入临界区使得该条件为真，该管程发生死锁.一个管程的程序在运行一个线程前会先取得互斥锁，直到完成线程或是线程等待某个条件被满足才会放弃互斥锁。
通过使用条件变量提供对同步的支持。概念上，一个条件变量就是一个线程队列(queue), 其中的线程正等待某个条件变为真。每个条件变量
关联着一个断言
. 当一个线程等待一个条件变量，该线程不算作占用了该管程，因而其它线程可以进入该管程执行，改变管程的状态，通知条件变量其关联的断言在当前状态下为真.
因此对条件变量存在两种主要操作:
wait c被一个线程调用，以等待断言被满足后该线程可恢复执行. 线程挂在该条件变量上等待时，不被认为是占用了管程.signal c(有时写作notify c)被一个线程调用，以指出断言现在为真.
当一个通知(signal)发给了一个有线程处于等待中的条件变量，则有至少两个线程将要占用该管程: 发出通知的线程与等待该通知的某个线程. 只能有一个线程占用该管程，因此必须做出选择。两种理论体系导致了两种不同的条件变量的实现:
- 阻塞式条件变量(Blocking condition variables)，把优先级给了被通知的线程.
- 阻塞式条件变量(Nonblocking condition variables)，把优先级给了发出通知的线程.
阻塞式条件变量
东尼·霍尔与Per Brinch Hansen最早提出的是阻塞式条件变量. 发出通知(signaling)的线程必须等待被通知(signaled)的线程放弃占用管程（或者离开管程，或者等待某个条件变量）。
设每个管程对象有两个线程队列
e是入口队列s是已经发出通知的线程队列.
设对于每个条件变量, 有一个线程队列
这些队列会公平(fair)调度，甚至实现为先进先出.发出通知的线程转入等待，但会比在线程入口的队列有更高优先权被调度，这称为"通知且急迫等待"。
非阻塞式条件变量
非阻塞式条件变量 (也称作"Mesa风格"条件变量或"通知且继续"(signal and continue)条件变量), 发出通知的线程并不会失去管程的占用权. 被通知的线程将会被移入管程入口的e队列. 不需要s队列.
非阻塞式条件变量经常把signal操作称作notify — . 也常用notify all操作把该条件变量关联的队列上所有的线程移入e队列.
可以把断言关联于条件变量，因而wait 返回时期望为真. 但是，这必须确保发出通知的线程结束到被通知的线程恢复执行这一时间段内，保持为真. 这一时间段内可能会有其它线程占用过管程。因此通常必须把每个wait操作用一个循环包裹起来：
while not(
) do wait c
其中是一个条件，强于. 操作notify 与notify all 被视为"提示"(hints)某个等待队列的可能为真. 上述循环的每一次迭代，表示失去了一次通知。
运用阻塞式条件变量的管程解决生产者/消费者问题：
monitor bounderbuffer; char buffer[N]; int nextin, nextout; int count; cond notfull, notempty; void append(char x) { while(count == 0) cwait(notfull); nextin = (nextin + 1)%N; buffer[nextin] = x; count ++; signal(notempty); } void take(char x) { while(count == N) cwait(notempty); x = buffer[nextout]; nextout = (nextout + 1) % N; count --; signal(notfull); } {nextin = 0; nextout = 0; count = 0;} void producer() { char x; while(true） { produce(x); append(x); } } void consumer(） { char x； while(true) { taker(x); consume(x); } }
消息传递
用于进程间通信和同步的消息系统的设计特点
| 同步 |
send： 阻塞/非阻塞 receive: 阻塞/非阻塞 一般send为非阻塞，receive为阻塞。 |
| 寻址 |
直接：send/receive（隐式/显式） 间接：静态（信箱，端口）/动态/所有权（一般为创建进程所有，创建进程一般为接收进程） |
| 格式 | 内容、长度（固定/不固定） |
| 排队原则 | FIFO/优先级 |
使用send非阻塞，receive阻塞，间接寻址的消息传递机制解决消费者/生产者问题：
capacity = 缓冲区大小 null = 空消息; int i; void produce() { message pmsg; while(true) { receive(mayproduce, pmsg); pmsg = produce(); send(mayconsume, pmsg); } } void consumer() { message cmsg; while(true) { receive(mayconsume, cmsg); consum(cmsg); send(mayproduce, null); } } void main(） { create_mailbox(mayproduce); create_mailbox(mayconsume); for(i = 0; i < capacity; i++) send(mayproduce, null); parbegin(producer, consumer); }
读者/写者问题
读者写者(Reader-Writer Problem)问题是一个经典的并发程序设计问题，是经常出现的一种同步问题。所谓读者写者问题，是指保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。
问题定义如下：有一个被许多进程共享的数据区，可以是一个文件，或者主存的一块空间，甚至可以是一组处理器寄存器。一些只读取这个数据区的进程（reader）和一些只往数据区中写数据的进程（writer）。以下假设共享数据区是文件。这些读者和写者对数据区的操作必须满足以下条件：读—读允许；读—写互斥；写—写互斥。这些条件具体来说就是：
（1）任意多的读进程可以同时读这个文件；
（2）一次只允许一个写进程往文件中写；
（3）如果一个写进程正在往文件中写，禁止任何读进程或写进程访问文件；
（4）写进程执行写操作前，应让已有的写者或读者全部退出。这说明当有读者在读文件时不允许写者写文件。
Reader和Writer的同步问题分为读者优先、弱写者优先（公平竞争）和强写者优先三种情况，它们的处理方式不同。
对于读者-写者问题，有三种解决方法：
1、读者优先
除了上述四个规则外，还增加读者优先的规定，当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。这说明只要有一个读者活跃，那么随后而来的读者都将被允许访问文件，从而导致写者长时间等待，甚至有可能出现写者被饿死的情况。
int readcount; semaphore x = 1, wsem = 1; void consumer() { while(true) { semWait(x); count ++; if(readcount == 1) semWait(wsem); semSignal(x); READUNIT(); semWait(x); readcount --; if(readcount == 0) semSignal(wsem); semSignal(x); } } void producer() { while(true) { semWait(wsem); WRITEUNIT(); semSignal(wsem); } } void main(） { readcount = 0; parbegin(producer, consumer); }
2、写者优先
除了上述四个规则外，还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。当一个写者声明想写文件时，不允许新的读者再访问文件。
int writecount, readcount; semaphore x = 1, y = 1, z = 1, rsem = 1, wsem = 1; void consumer() { while(true) { semWait(z);
semWait(rsem);
semWait(x); readcount ++; if(readcount == 1) semWait(wsem); semSignal(x);
semSignal(resm);
semSignal(z); READUNIT(); semWait(x); readcount --; if(readcount == 0) semSignal(wsem); semSignal(x); } } void producer() { while(true) { semWait(y); writecount ++; if(writecount == 1) semWait(rsem); semSignal(y); semWait(wsem); WRITEUNIT(); semSignal(wsem); semWati(y); writecount --; if(writecount == 0) semSignal(rsem); semSignal(y); } } void main(） { readcount = 0; parbegin(producer, consumer); }