1. 并发程序的基本概念

• 程序顺序性
  • 内部顺序性：CPU严格按照顺序执行指令
  • 外部顺序性：程序员设计程序时往往用顺序设计的思想
• 顺序程序特性
  • 程序执行的顺序性
  • 计算环境的封闭性： 程序执行时犹如独占资源
  • 计算结果的确定性
  • 计算过程的可再现性
• 并发进程
  • 无关的并发进程：一组并发进程，在不同变量集上运行
  • 交往的并发进程：一组并发进程，共享某些变量，相互影响
• 并发进程制约关系
  • 进程互斥：争夺某一个资源
  • 进程同步：共同完成某一个任务，协调先后顺序
  • 发生问题：
    • 与时间有关的错误：结果错误、永远等待
• 临界区：
  • 临界资源：一次只能被一个进程使用的资源（互斥共享变量）
  • 临界区：是个程序段，是并发进程中与互斥共享变量相关的程序段
  • 相关的临界区：两个进程的临界区有相同的临界资源（必须互斥进入）
  • 问题：
    • 多个并发进程访问临界资源存在制约关系
    • 如果两个进程同时处在相关的临界区，会发生与时间有关的错误
  • 临界区管理的要求：
    • 一次至多允许一个进程停留在相关临界区
    • 一个进程不能无限制停留在临界区内
    • 一个进程不能无限制等待进入临界区内
  • 临界区嵌套使用
  • 

2. 并发程序控制和问题

• 临界区管理实现：
  • 思路：判断锁和获取锁要作为原子操作，不然会死锁或时间错误
  • 实现：
    • 原子指令：测试并建立锁指令、对换指令（忙式等待，效率不高）
    • 中断控制：进出临界区时开关中断，这样临界区执行时就不会被中断，自然实现了原子性
      • 这个时操作系统的原语，是操作系统解决这个问题的办法
      • 不建议用户程序使用，因为无法保证程序员设计出短小精悍的原语
    • PV操作：用信号量，“申请-等待队列-中断恢复”
  • 生产者消费者问题：
    • 
• 进程间通信
  • 信号量：低级通信方式
  • 信件：进程通信机制（直接通信、间接通信）
  • 基于流：多个进程共同使用一个缓冲区
  • RPC：远程过程调用
• 死锁
  • 概念：两个进程分别等待对方占有的资源
  • 死锁的产生
    • 互斥：进程互斥地使用资源
    • 占有和等待：一个进程得不到资源，就等待且不释放已有资源
    • 不剥夺：进程不能从另一个进程抢走资源
    • 循环等待：每个进程都等待它前一个进程所持有的资源
  • 死锁的防止
    • 破坏上述四个条件之一即可
    • eg. 层次分配：资源分成多个层次，一个进程获得某个资源后只能获得比他层次更高的资源　　
  • 死锁的避免：银行家算法
  • 死锁的检测：
    • 

    • 算法：warshall闭包