并发性：互斥与同步 操作系统设计中的核心问题是关于进程和线程的管理。并发是所有问题的基础，也是操作系统设计的基础。并发包括许多设计问题，其中有进程间通信、资源共享与竞争（例如内存、文件、I/O访问）、多个进程活动的同步以及分配给进程的处理器时间等。和并发相关的一些关键术语：原子操作一个或多个指令的序列，对外是不可分的；即没有其他进程可以看到其中间状态或者中断此操作临界区是一段代码，在这段代码中进程将访问共享资源，当另外一个进程已经在这段代码中运行时，这个进程就不能在这段代码中执行。死锁两个或两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而不能继续执行，这样的情形叫做死锁活锁两个或两个以上进程为了响应其他进程中的变化而持续改变自己的状态但不做有用的工作，这样的情形叫做活锁互斥当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源，这种情形叫做互斥竞争条件多个线程或者进程在读写一个共享数据时，结果依赖于它们执行的相对时间，这种情形叫做竞争饥饿是指一个可运行的进程尽管可能继续执行，但被调度器无限期地忽视，而不能被调度执行的情况1.并发的原理在单处理器系统的情况下，出现问题的原因是中断可能会在进程中任何地方停止指令的执行；在多处理器系统的情况下，不仅同样的条件可以引发问题，而且当两个进程同时执行并且都试图访问同一个全局变量时，也会引发问题。这两类问题的解决方案是相同的：控制对共享资源的访问1.1 竞争条件竞争条件发生在多个进程或线程读写数据时，其最终的结果依赖于多个进程的指令执行顺序。1.2 操作系统关注的问题并发会带来哪些设计和管理问题？操作系统必须能够记住各个活跃的进程操作系统必须为每个进程分配和释放各种资源。操作系统必须保护每个进程的数据和物理资源，避免其他进程的无意干涉一个进程的功能和输出结果必须与执行速度无关。1.3 进程的交互知道程度关系一个进程对其他进程的影响潜在的控制问题进程之间不知道对方的存在竞争1.一个进程的结果与其他进程的活动无关 2.进程的执行时间可能会受影响互斥、死锁（可复用的资源）、饥饿进程间接知道对方的存在（如共享对象）通过共享合作1.一个进程的结果可能依赖于从其他进程获得的信息 2.进程的执行时间可能会受到影响互斥、死锁（可复用的资源）、饥饿、数据一致性进程直接知道对方的存在（它们有可用的通信原语）通过通信合作1.一个进程的结果可能依赖于从其他进程获得的信息2.进程的计时可能会受到影响死锁（可消费的资源）、饥饿2. 信号量现在讨论操作系统和用于提供并发性的程序设计语言机制。基本原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。任何复杂的合作需求都可以通过适当的信号结构得到满足，为了发信号，需要使用一个被称作信号量的特殊变量。为通过信号量s发送信号，进程可执行原语semSignal(s)（V操作）；为通过信号量s接收信号，进程可执行原语semWait(s)（P操作）；如果相应的信号仍然没有发送，则进程被挂起，直到发送完为止。为了达到预期的效果，可以把信号量看做是一个具有整数值的变量，在它之上定义三个操作：1）一个信号量可以初始化成非负数2）semWait操作使信号量减1。如果值变成负数，则执行semWait的进程被阻塞。否则进程继续执行。3）semSignal操作使信号量加1。如果值小于或者等于零，则被semWait操作阻塞的进程被解除阻塞。除了这三种操作外，没有任何其他方法可以检查或操作信号量。解释：开始时，信号量的值为零或正数。如果该值为正数，则该值等于发出semWait操作后可立即继续执行的进程的数量。如果该值为零（或者由于初始化，或者由于有等于信号量初值的进程已经等待），则发出semWait操作的下一个进程会被阻塞，此时该信号量的值变为负值。之后，每个后续的semWait操作都会使信号量的负值更大。该负值等于正在等待接触阻塞的进程的数量。在信号量为负值的情形下，每一个semSignal操作都会将等待进程中的一个进程解除阻塞。在信号量为负值的情形下，每一个semSignal操作都会将等待进程中的一个进程解除阻塞。2.1 互斥使用信号量s解决互斥问题的方法。设有n个进程，用数组P(i)表示，所有的进程都需要访问共享资源。每个进程中进入临界区前执行semWait(s),如果s的值为负，则进程被挂起；如果值为1，则s被减为0，进程立即进入临界区；由于s值不再为正，因而其他任何进程都不能进入临界区。/* program mutualexeclusion */ 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)); }