计算机操作系统-并发控制

什么是并发控制

操作系统中可能有多道程序同时运行的情况，需要对程序进行同步与互斥的控制，以实现并发控制。

并发控制的关键问题

1. 死锁
2. 饥饿

互斥

• 多道程序系统中存在许多进程，它们共享各种资源，然而有很多资源一次只能供一个进程使用。一次仅允许一个进程使用的资源称为临界资源（如 打印机等）。那么我们的多个程序就需要保证不同时的去访问临界资源（我们称这段访问临界资源的代码为临界区）。这个保障不同时的机制就叫互斥，顾名思义：互相排斥。
  互斥的要求（满足以下程序进入临界区的要求才能保证互斥正常执行）

1. 空闲让进（因为，当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。）
2. 忙则等待（如果当前已有程序进入临界区，访问临界资源，则请求进入临界区的进程应该等待）
3. 有限等待（对等待规定时间或者次数限制，否则会陷入死等）
4. 让权等待（如果进程无法进入自己的临界区要及时释放，避免其他进程死等）

互斥的具体实现方法

• 软件方法
  主要是Dekker互斥算法和Peterson互斥算法，（由于只能用于两个进程，这里不再赘述）

• 硬件方法
   1. 屏蔽中断
    由于一个程序执行的时候，有可能因为调度算法的原因，被系统中断，然后执行另一个程序，因此可以直接屏蔽中断让程序一直执行不被打断。但是显然，这样的方法程序就会不受控制，不太完美。
   2. Test and Set指令
    属于系统原语（执行过程不会被打断）
    Test and Set伪代码

    function testset(var i:integer):boolen;
      begin
      if i = 0 then       
        begin
          i := 1;
          testset := true;
        end
      else testset := false
      end.
  

  上述代码就是Test and Set 最根本的思想就是验证一个标识变量i，如果为0就是可以进入临界区，然后重置为1表示已经有进程进去了，然后返回true。如果已经发现是1，就是有程序进去了，就得返回false。
  使用伪代码

      program mutualexculusion;
      const n := ...;/*进程数*/
      var flag:integer; //标识整数
      procedure P(i:integer);
      begin
        repeat
      repeat {nothing} untill testset(flag);
        <临界区>;
        flag := 0;
        <其余位置>
       forever
      end;

  上述代码就是先设置一个本地的flag标识标识是否有进程，然后不断的去调用testset，得到true就进入临界区访问临界资源，结束后重置flag，如果得到false就直接再次循环
  显然testset原语会不断的循环存在忙则等待的问题
 2. Exchange指令(也是原语）

    procedure exchange ( var r :register; var m :memory);
    var temp;
    begin 
      temp :=m;
      m:=r;
      r:= temp;
    end.

 

    program mutualexclusion;
    const n=...;/*进程数*
    var bolt:integer;
    procedure P(i:integer);
    varkey:integer;
      begin
       repeat
        key:=1;
        repeat exchange(key,bolt) until key=0;
        <临界区>;
        bolt:=0;
        <其余部分>
        forever
      end;

优点 1.适用于单处理器或者共享主存的多处理器中任意数量的进程2.简单并且容易证明3.可以用于支持多临界区
缺点 1.忙等待消耗处理器时间2.当进程离开临界区并且多个进程在等待的时候可能导致饥饿3.死锁：如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求,那么高优先级进程会获得处理器并等待临界区

• 信号量（极其重要，其实不仅可以做互斥，也可以同步，其实也是在交换信息，后面详细说明）
    信号量就是一个整形变量，有一个队列用来放正在排队想要使用这一资源的进程
  
    信号量通过wait申请，signal释放
    伪代码

  注意到，wait操作就是上来先将信号量减去1，signal先加上1.因此，wait操作中如果count < 0则说明已经没有资源了，在signal中如果 >= 0意味着存在资源（这就是一种进程间最简单的通信）。
  同时也会自身阻塞和被阻塞唤醒这也是一种同步
  
  信号量类型
  1.互斥信号量（信号量最大只能1，只允许一个程序拿到信号量）
  2.资源信号量（大于1的整型，运行多个程序拿到信号量，模拟出了资源的利用）

同步

同步：是指散布在不同进程之间的若干程序片段，它们的运行必须严格按照一定的先后次序来运行，这种次序依赖于要完成的任务。比如数据的收发，必须发送方发送了接收方才能收。

同步是一种更为复杂的互斥吗，而互斥是一种特殊的同步。互斥是两个进程或线程之间不可以同时运行，它们会互相排斥，必须等待其中的一个运行完，另一个才可以运行。而同步也是不可以同时运行，并且还需要按照某种顺序来运行。
（互斥是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法控制对资源的访问顺序，同步是指在互斥的基础上实现对资源的有序访问）

• 刚刚的信号量其实就是一种同步方法（经典的消费生产者问题就使用这种方法来同步消费者和生产者）
• 管程机制（其实就是用面向对象方法，用编程语言实现的信号量，方便开发者使用）详细点击此处
• 消息传递（通过消息传递通信来控制同步，不再赘述） 详细点击此处

需要解决的两大问题（之后会开一篇详细说）

• 死锁
    死锁的产生
    1、互斥条件 每一资源或者被分配给一个进程，或者空闲。
    2、占有并请求条件 已分配到了一些资源的进程可以申请新的资源
    3、不可剥夺条件 已分配给某些进程的资源不可被剥夺，只能有占有它的进程使用完后主动释放
    4、循环等待条件 系统必然存在一条有两个或两个以上的进程组成的循环，联众的每一个进程都在等待相邻进程所占用的资源
  可以通过上面的条件来预防死锁（都不太理想）
  还有一种著名的银行家算法来避免死锁
• 饥饿
  由于分配的不公平产生，进程在信号量内无限等待。