顺序性不但指一个程序模块内部，也指两个程序模块之间
内部顺序性 一个程序在处理器上的执行是严格按序的，只有前一个操作结束后，才能开始后继操作外部顺序性 一个计算任务需要若干不同程序完成，这些程序也按照调用次序严格有序执行一个处理器在几个进程之间的多路复用，是对有限物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率
并发程序设计 （concurrent programming）
一个程序被设计成可与其他程序并发执行的程序设计方法并发程序特点
对于单处理器系统，可让处理器和各I/O设备同时工作，发挥硬部件的并行能力对于多处理器系统，可让各进程在不同处理器上物理地并行，加快计算速度 简化程序设计任务并发进程的无关性是进程的执行与时间无关的一个充分条件
只要要满足Bernstein条件，并发执行的程序就可以保持封闭性和可再现性
对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现，甚至无法再现
结果不唯一：飞机售票问题永远等待：内存资源管理问题资源竞争的两个控制问题
死锁(Deadlock)问题：因争夺资源陷入永远等待的状态饥饿(Starvation) 问题：由于其他进程总是优先于它，而被调度程序无限期地拖延而不能被执行解决途径：分配策略
最简单策略解决策略：FCFS资源分配策略进程同步（synchronization）指两个以上进程基于某个条件来协调它们的活动
一个进程的执行依赖于协作进程的消息或信号当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调
临界区（critical section）
并发进程中与共享变量有关的程序段临界资源
共享变量代表的资源，即一次仅能供一个进程使用的资源竞争条件(race condition)
当多个并发进程访问临界资源时，结果依赖于它们执行的相对速度，便称出现了竞争条件与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知
如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误临界区调度原则（Dijkstra）
一次至多一个进程能够进入临界区内执行如果已有进程在临界区，其他试图进入的进程应等待进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入总结
互斥使用、有空让进忙则等待、有限等待择一而入、算法可行硬件假设
通常假设具有存储器访问级的基本互斥性对内存中的同一个单元同时访问时，必定由存储器进行仲裁使其串行化 硬件、操作系统或语言未提供任何支持采用标志方式，即用标志来表示哪个进程可进入临界区
为每个进程设置相应的标志位进程在临界区时设置其值为true，不在时为false进入临界区前先测试其他进程的标志位Peterson算法
为每个进程设置标志，当标志值为true时表示此进程要求进入临界区另外，再设置一个指示器turn以指示可以由哪个进程进入临界区当turn＝i时，则可由进程Pi进入临界区本质：inside声明自己需要使用， turn谦让其他进程使用
turn作为共享变量，不可能同时为不同的数，所以一定可以有一方执行。
实现互斥的最简单方法
进入临界区时关中断，进程退出临界区时开中断，这样进程的执行再也不会被打断Linux系统：
关中断内核函数：cli()(clear interrupt)开中断内核函数：sti()(set interrupt)关中断方法的缺点
不适合作为通用的互斥机制，关中断的时间过长会影响性能和系统效率不适用于多处理器系统，一个处理器关中断，并不能防止进 程在其他处理器上执行相同的临界区代码若将这项权力赋予用户也存在危险，如果用户未开中断，则系统可能因此而终止测试并设置机器指令TS（Test and Set）
可把这条指令看做函数，它有布尔型参数x和返回条件码当TS（&x）测到x值为true时，则置x为false，且根据所测试到的x值形成条件码 bool TS(bool &x) { if(x) { x=false; //修改x的值 return true; } else //返回条件码，不修改x return false; }TS指令实现进程互斥
把一个临界区与一个布尔型变量s相关联变量s代表临界资源的状态，把它看成一把锁，s的初值置为true，表示没有进程在临界区内，资源可用系统利用TS指令实现临界区的上锁和开锁原语操作本质：TS基于原语单向修改成false，其他进程单项修改成true
对换指令的功能是交换两个字的内容
void SWAP(bool &a, bool &b) { bool temp=a; a=b; b=temp; }SWAP可简单而有效地实现互斥，方法是
为每个临界区设置布尔型锁变量，如lock当其值为false时，表示无进程在临界区内本质：任意时刻只让一个进程拥有false（其实建立在指令为不可分割的最小执行单元？也不太准确，单条指令是否一定会被完整执行和指令本身功能，处理器设计等有关系，所以更好的是把swap理解为原语？）
生产者—消费者问题（producer-consumer problem）
是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等解决好生产者—消费者问题就解决好了一类并发进程的同步问题生产者和消费者进程的交替执行会导致进程永远等待：
当consumer检测到counter = 0后，进程切换到producer生产产品，但是其wakeup signal在consumer没有睡眠时是无效的，当producer在缓冲区快速生产满产品后会sleep，此时切换回consumer，consumer执行sleep，造成所有进程睡眠等待。问题分析
不正确结果并不是因为并发进程共享缓冲区，而是因为它们访问缓冲区的速度不匹配解决途径
进程同步：通过交换信号或消息来调整并发进程推进速前面方法解决临界区调度问题的缺点
软件算法：太过复杂，效率低下硬件方法：采用忙式等待测试法，浪费CPU时间将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重用户编程负担信号量和P、V操作（E.W.Dijkstra，1965年）
信号量只能由同步原语PV对其操作
原语：内核中执行时不可被中断的过程（通常由多条特定指令组成）P操作原语和V操作原语：用于发送和接收信号若协作进程的相应信号仍未送到，则进程被挂起直至信号到达为止利用信号量和PV 操作既可解决并发进程竞争问题，又可解决并发进程协作问题按用途分类
公用信号量：联系一组并发进程，相关进程均可在此信号量上执行PV操作 初值置为1，用于实现进程互斥私有信号量：联系一组并发进程，仅允许此信号量所拥有的进程执行P操作，而其他相关进程可在其上施行V操作 初值往往为0或正整数，多用于并发进程同步按取值分类
二元信号量：主要用于解决进程互斥问题一般信号量：又称计数信号量，允许取大于 1的整型值，主要用于解决进程同步问题哲学家就餐问题：死锁
解决办法1：
//至多允许四个哲学家同时吃 semaphore count=4；// sem_t count; sem_init(count, 0, 4); semaphore fork[5];//... for (int i=0;i<5;i++) fork[i]=1; Cobegin process philosopher_i( ) {/*i= 0,1,2,3,4*/ while(true) { think( ); P(count);//sem_wait(count) P(fork[i]);//sem_wait(fork[i]) P(fork[(i+1)%5]);//... eat( ); V(fork[i]);//sem_post(fork[i]) V(fork[(i+1)%5]);//... V(count);//sem_post(count) } } coend解决办法二：
//取到手边的两把叉子或者一把都不取 Semaphore mutex=1； semaphore fork[5]; for (int i=0;i<5;i++) fork[i]=1; Cobegin process philosopher_i( ) {/*i= 0,1,2,3,4*/ while(true) { think( ); P(mutex); P(fork[i]); P(fork[(i+1)%5]); V(mutex); eat( ); V(fork[i]); V(fork[(i+1)%5]); } } coend生产者-消费者问题：同步问题
一个生产者、一个消费者共享一个缓冲区多个生产者、多个消费者共享多个缓冲区解决基本思路： 可设置两个信号量empty和full，其初值分别为1和0
empty ：生产者判断能否向缓冲区放入产品full：消费者判断能否从缓冲区取出产品在对共享资源操作时，通过mutex的PV操作进出临界区
信号量和PV操作缺陷
共享资源的管理分散在各个进程，不利于对临界资源管理难以防止有意/无意的违法同步操作管程（P. Hansen, C. Hoare）引入背景
在进程共享内存的前提下，集中和封装针对一个共享资源的所有访问把相关的共享变量及其操作集中在一起统一控制和管理，可方便管理和使用共享资源便于用高级语言来书写程序，也便于程序正确性验证管程思想：
把分散在各进程中的临界区集中起来管理，并把共享资源用数据结构抽象地表示由于临界区是访问共享资源的代码段，建立一个“秘书”程序（管程）管理到来的访问管程属性
共享性：管程中的过程可被进程共享安全性：管程的局部变量只能由该管程的过程访问，管程过程不可访问任何非局部于它的变量互斥性：任一时刻，最多只能一个进程进入管程信号量与管程的功能是等价的
如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁
不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关
必要条件分析
前3个条件是死锁存在的必要条件，但不是充分条件第4个条件是前3个条件同时存在时所产生的结果，故条件并不完全独立只要能破坏4个必要条件之一，就可以防止死锁
破坏第一个条件 使资源可同时访问而不是互斥使用破坏第二个条件 静态分配破坏第三个条件 采用剥夺式调度方法：申请资源未果时主动释放资源，然后去等待破坏第四个条件 采用层次分配策略，将系统中所有资源排列到不同层次中 一个进程得到某层的一个资源后，只能再申请较高一层的资源 当进程释放某层的一个资源时，必须先释放占用的较高层资源 当进程获得某层的一个资源后，如果想申请同层的另一个资源，必须先释放同层中的已占用资源按序分配策略：层次策略的变种
把系统的所有资源排一个顺序：系统若共有n个进程，共有m个资源，用ri表示第i个资源，于是这m个资源是r1, r2, ……, rm规定如果进程不得在占用资源ri(1≤i≤m)后再申请rj(j<i)按这种策略分配资源时系统不会发生死锁允许系统中同时存在前三个必要条件，通过合适的资源分配算法确保不会出现进程循环等待链，从而避免死锁
用银行家算法避免死锁：
操作系统（银行家）操作系统管理的资源(周转资金)进程（要求贷款的客户）银行家算法——进程启动拒绝法：
系统中若要启动一个新进程工作，其对资源Ri的需求当前系统中所有进程对资源Ri的最大资源需求数加上启动的新进程的最大资源需求数不超过系统拥有的最大数这个算法考虑最坏的情况，即所有进程同时要使用它们声明的资源最大需求数，因此很难是最优的系统性安全的定义：在时刻T0系统是安全的,仅当存在一个进程序列P1, …, Pn，对进程Pk满足公式 Need[k,i] ≤Available [i]+ ∑Allocation[j,i]，k=1, …, n，i=1, …, m
公式左边表示进程Pk尚缺少的资源Available[i]（即Vi）是T0时刻系统尚可用于分配且为Pk所想要的那类资源数∑Allocation[j,i]表示排在进程Pk之前的所有进程所占用的Pk所需要的资源总数进程Pk所需资源若不能立即被满足，但在所有Pj（j＝1，2，…，k－１）运行完成后可以满足当Pk释放全部资源后，Pk＋１也能获得资源以完成任务系统中的所有进程进入进程集合
在安全状态下系统收到进程的资源请求后，先把资源试探性分配给它系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较 在进程集合中找到剩余资源能满足最大需求量的进程，从而保证这个进程运行完毕并归还全部资源 把这个进程从集合中去掉, 系统的剩余资源将更多，反复执行上述步骤最后检查进程集合 若为空，表明本次申请可行，系统处于安全状态，可实施本次分配 否则，有进程执行不完，系统处于不安全状态，本次资源分配暂不实施，让申请进程等待解决死锁问题的一条途径是死锁检测和解除
这种方法对资源分配不加任何限制，也不采取死锁避免措施系统定时地运行死锁检测程序，判断系统内是否已出现死锁如果检测到系统已发生死锁，再采取措施解除它：基于进程—资源分配图确定死锁的方法：
如果进程-资源分配图中无环路，则此时系统没有发生死锁如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生死锁。此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则 环路的存在只是产生死锁的必要条件而不是充分条件进程-资源分配图简化：
如果能在进程-资源分配图中消去此进程的所有请求边和分配边，成为孤立结点经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的死锁定理
系统为死锁状态的充分条件是当且仅当该状态的进程-资源分配图是不可完全简化的根据系统保存的检查点，让所有进程回退，直到足以解除死锁 这种措施要求系统建立保存检查点、回退及重启机制
检测到死锁时，如果存在未卷入死锁的进程，随着这些进程执行结束后有可能释放足够的资源来解除死锁
并发进程之间的交互必须满足两个基本要求：同步和通信
进程通信IPC（InterProcess Communication）:进程之间互相交换信息的工作
Unix基本通信机制
信号(signal)通信机制管道(pipeline)通信机制 System V IPC通信机制消息传递(message passing)通信机制信号量(semaphore)通信机制共享内存(shared memory)通信机制UNAT&T的Bell与加大伯克利的BSD是两大主力
Bell致力于改进传统的进程IPC，形成了SYSTEM Ⅴ IPC机制BSD在改进IPC的同时，把网络通信规程(TCP/IP)实现到UNIX内核中，出现了socket网络通信机制软中断 ：
中断与异常要通过硬件设施来产生中断请求，称为硬中断不必由硬件产生中断源而引发的中断称为软中断软中断是利用硬中断的概念，采用软件方法对中断机制进行模拟，实现宏观上的异步执行“信号”是一种软中断机制相同点
两者在概念上是“一致”的两者都是“异步”的两者均采用“向量表”实现两者均有“屏蔽”设施不同点
前者由硬件和软件相结合来实现，后者则完全由软件实现中断向量表和中断处理程序（全部由系统提供）均位于系统空间信号向量表虽然处于系统空间，但信号处理程序由应用程序提供，并在用户空间执行管道(pipeline)是连接读写进程的一个特殊文件
允许进程按先进先出方式传送数据，也能使进程同步执行操作发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括 （管道）文件的创建、打开、关闭和读写匿名管道是半双工的
数据只能向一个方向流动要求双向通信时，需要建立两个匿名管道只能用于具有亲缘关系的进程通信
亲缘关系指具有共同祖先，如父子进程或者兄弟进程之间匿名管道对于管道两端的进程而言，是一个特殊文件
写入的内容每次都添加在管道缓冲区的末尾，每次都是从缓冲区的头部读出数据又称FIFO，克服只能用于具有亲缘关系的进程之间通信的限制
FIFO提供一个与路径名的关联，以FIFO的文件形式存在于文件系统中，通过FIFO不相关的进程也能交换数据FIFO遵循先进先出，对管道及FIFO的读总是从开始处返回数据，对它们的写则把数据添加到末尾指两个或多个进程共同拥有一块内存区，该区中的内容可被进程访问
在不同进程之间传递数据的机制
消息传递的复杂性 进程地址空间隔离，发送进程无法将消息直接复制到接收进程的地址空间中，只能由操作系统完成消息传递基本原语（阻塞/同步问题） 发送消息：向一个给定目标进程发送一条消 接收消息：从一个给定源进程接收一条消息消息传递特点 正在执行的进程间可在任何时刻发送/请求消息 消息传递机制与进程的阻塞和释放紧密联系 一个进程在某一时刻的执行依赖于另一进程的消息或等待其他进程对发出消息的回答 消息传递提供了进程同步能力，进一步扩充了并发进程间对数据的共享send()操作
同步/阻塞：发送进程执行send()后，等待接收进程回答消息后才继续进行异步/非阻塞：发送进程执行send()后，将消息传送到接收进程的信箱后继续运行，直到某个时刻需要接收进程送来回答消息时，才查询和处理receive()
同步/阻塞：接收进程执行receive()后直到消息交付完成，都处于等待消息的状态异步/非阻塞：执行receive()后不要求接收进程等待，当它需要消息时，再接收并处理消息IPC资源
表示单独的消息队列、共享内存或信号量集合具有相同类型的接口函数
信号量实现进程同步消息队列以异步方式为通信频繁、但数据量少的进程通信提供服务共享主存为数据量大的进程间通信提供服务共同点
通过 System V IPC对象通信时，需传递该对象的唯一IPC标识符访问System V IPC对象时必须经过许可检验System V IPC对象的访问权限由对象创建者设置IPC通信机制将IPC标识符作为对系统资源表的索引利用线程间共享的全局变量实现同步 条件变量使线程睡眠等待特定条件出现（无需轮询） 使用方法
通常条件变量和互斥锁同时使用一个线程因等待“条件变量的条件成立”而挂起另一个线程使"条件成立"（给出条件成立信号）一般自旋锁：
最多只能被一个可执行线程持有自旋锁采用忙式等待，直至资源被解锁 ；二值信号量不必循环等待信号量，而是进入等待队列读者写者自旋锁： 多进程可以并发地持有读锁，写锁仅有一个进程能持有
自旋锁作用：在SMP系统中，自旋锁最重要的特点是内核例程在等待锁被释放时一直占据着某个 CPU，用来保护那些只需简短访问数据结构的操作，如 从双向队列链表中增加或删除一个元素 因此，在内核需要进程同步的位置，自旋锁使用得比较频
