1.并发

如果逻辑控制流在时间上是重叠，那么它们就是并发的，操作系统提供三种基本的构造并发程序的方法:进程、I/O多路复用、线程

进程

  1. 每个逻辑控制流 都是一个进程，由内核来调度和维护
  2. 因为进程有独立的虚拟地址空间，和其他进程通信，控制流必须使用某种显式的进程间通信IPC进制

基于进程的并发编程，对于在父，子进程间共享状态信息，进程有一个非常清晰的模型

  • 共享文件表，但是不共享用户地址空间
  • 进程拥有独立的虚拟地址空间
  1. 优点:一个进程不可能不小心覆盖另一个进程的虚拟存储空间，消除许多令人迷惑的错误
  2. 缺点:独立的地址空间使得进程间共享信息也很困难，必须使用显式的IPC(进程间通信)机制，速度比较慢，进程控制和IPC的开销都很大

I/O多路复用

  1. 应用程序在一个进程的上下文中显示地调度它们自己的逻辑流
  2. 逻辑流被模型化为状态机，数据到达文件描述符后，主程序显式地从一个状态转换到另一个状态
  3. 因为程序是一个单独的进程，所以所有的流都共享同一个地址空间
  • 使用select函数，要求内核挂起进程，只有一个或多个I/O事件发生后，才将控制返回给应用程序

线程

  1. 线程是运行在一个单一进程上下文中的逻辑流，由内核调度
  2. 像进程一样由内核进行调度
  3. 而且像I/O多路复用一流一样共享一个虚拟地址空间

  • 线程就是运行在进程上下文中的逻辑流，由内核调度，每个线程都有它自己的线程上下文。

  • 不共享

  1. 包括一个唯一的整数线程ID(Thread ID,TID).
  2. 栈和栈指针
  3. 程序计数器
  4. 通用目的寄存器和条件码
  • 共享
  1. 所有运行在该进程里的线程共享该进程的整个虚拟地址空间
  2. 共享 包括代码，数据，堆，共享库和打开的文件
  • 与进程执行时区别
  1. 线程的上下文切换的开销比进程的小得多，快得多
  2. 线程不是按照严格的父子层次来组织
  3. 和一个进程相关的线程组成一个线程池

2.线程同步

共享变量

共享变量十分方便，但是他们也引入了同步错误的可能性。同一个程序每次运行的顺序都可能不同，这些顺序中有一些将会产生正确结果，但是其他的不会，这就是同步错误

信号量

具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作称为P和V

  • P(s),Proberen，测试
  1. 如果s是非零的，那么P操作将s减1，并且立即返回
  2. 如果s为零，那么就挂起这个线程，直到s变为非零
  3. 而一个V操作会重启这个线程
  4. 在重启之后，P操作将s减1，并将控制返回给调用者
  • V(s),Verhogen，增加
  1. V操作将s加1.
  2. 如果有任何线程阻塞在P操作等待s变成非零，那么V操作随机会重启这些线程中的一个。
  3. 然后将s减去1，完成它的P操作。
  • P操作和V操作都是不可分割的，也就是自身确保了是一个带有安全轨迹的操作
  • P和V的定义确保了一个正在运行的程序绝不可能进入这样一种状态，也就是不可能有负值，这个属性叫做信号量不变性
  • 将每个共享变量(或一组相关的共享变量) 与一个信号量s联系起来，然后用P(s)和V(s)操作相应的临界区包围起来

3.利用信号量

互斥锁

  • 提供互斥为目的的二元信号量常常也称为互斥锁(mutex)
  1. 在一个互斥锁上执行P操作叫做互斥锁加锁
  2. 在一个互斥锁上执行V操作叫做互斥锁解锁
  3. 对一个互斥锁加了锁还没有解锁的线程称为占用这个互斥锁

生产者-消费者 问题

  • 生产者线程反复地生成新的项目，并把它们插入到缓冲区中
  • 消费者线程不断地从缓冲区取出这些项目，然后消费使用它们
  • 插入和取出项目都涉及更新共享变量
  1. 必须保证对缓冲区的访问是互斥的
  2. 还需要调度对缓冲区的访问
  3. 如果缓冲区是满的，那么生产者必须等待直到有一个槽位变为可用
  4. 如果缓冲区是空的，那么消费者必须等待知道有一个项目变为可用

读者-写者 问题

  • 一组并发的线程要访问同一个数据对象
  • 修改对象的线程叫做写者
  • 只读对象的线程叫做读者
  1. 写者必须拥有对对象的独占访问
  2. 读者可以和无限多个其他读者共享对象
  3. 一般来说有无数个并发的读者和写者

第一类读者-写者问题

  • 读者优先，要求不让读者等待，除非已经把一个使用权限赋予了一个写者。换句话说，读者不会因为有一个写者在等待而等待

  • 信号量w控制对访问共享对象的临街区的访问

  • 读者

  1. w只对第一个读者上锁
  2. w对最后一个走的读者解锁
  • 写者
  1. 写者只要进入临界区就对w上锁
  2. 写者只要离开临界区就对w解锁

第二类读者-写者问题

  • 写者优先，要求一但一个写者准备好可以写，它就会尽可能地完成它的写操作。同第一类不同，在一个写者到达后的读者必须等待，即使这个写者也是在等待

4.线程安全

四种线程不安全函数类

  • 不保护共享变量的函数
  1. 解决方案，利用P，V这样的同步操作来保护共享的变量
  • 保持跨越多个调用状态的函数，因为产生的结果依赖于上一个next的值
  1. 解决方案: 重写
  2. 使得它不能依赖static，而是依靠调用者在参数中传递状态信息
  3. 缺点: 需要在曾经成千上百个不同的调用位置，修改，十分麻烦
  • 返回指向静态变量的指针的函数，因为一个正在被一个线程使用的变量，可能偷偷被另一个线程悄悄覆盖
  1. 解放方案：重写函数:让调用者传递存放的结果的指针
  2. 加锁-拷贝技术:在一个调用位置，互斥锁加锁。调用线程不安全函数，将函数返回的结构拷贝到一个私有的存储器。然后互斥锁，解锁。
  • 调用线程不安全函数的函数

5.死锁

  • 指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进

  • 产生死锁的必要条件

  1. 互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用
  2. 请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放
  3. 不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放
  4. 环路等待条件：在发生死锁时，必然存在一个进程–资源的环形链

解决死锁的基本方法

  • 预防死锁
  1. 资源一次性分配：一次性分配所有资源，这样就不会再有请求了：（破坏请求条件）
  2. 只要有一个资源得不到分配，也给这个进程不分配其他的资源：（破坏请保持条件）
  3. 可剥夺资源：即当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源（破坏不可剥夺条件）
  4. 资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）
  • 避免死锁
  1. 银行家算法
  2. 首先需要定义状态和安全状态的概念。系统的状态是当前给进程分配的资源情况
  3. 因此，状态包含两个向量Resource（系统中每种资源的总量）和Available（未分配给进程的每种资源的总量）及两个矩阵Claim（表示进程对资源的需求）和Allocation（表示当前分配给进程的资源）
  4. 安全状态是指至少有一个资源分配序列不会导致死锁。当进程请求一组资源时，假设同意该请求，从而改变了系统的状态，然后确定其结果是否还处于安全状态
  5. 如果是，同意这个请求；如果不是，阻塞该进程直到同意该请求后系统状态仍然是安全的
  • 检测死锁
  1. 首先为每个进程和每个资源指定一个唯一的号码
  2. 然后建立资源分配表和进程等待表
  • 解除死锁
  1. 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；
  2. 撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等