进程互斥的实现方法

进程互斥的软件实现方法

• 软件实现方法的思想：在进入区设置并检查一些标志 来标明是否有进程在临界区中,若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

单标志法

• 思想就是两个进程再访问临界区后会把使用临界区的权限转交给另一个进程 用turn来记录当前能进入临界区的进程号
• 缺点
  • 
    • 因为一个进程进入临界区的权限是由其他进程给予的，所以肯定会按照顺序区访问临界区，这种轮流访问访问带来的问题违背的就是空闲让进的原则

双标志先检查法

• 思想：设置一个布尔型型数组flag，数组中的各个元素用来标记个进程想进入临界区的意愿，默认值都是false，如果一个进程想进入临界区，就先查看当前是否有别的进程想进入临界区 通过轮询实现
• 但是因为进入区的检查和上锁不是原子操作，所以发生切换问题，会导致两个进程可能同时访问临界区，违法了忙则等待

双标志后检查法

• 因为先检查，后上锁因为原子性问题会导致违法忙则等待，所以双标志后检查法将上锁放到前面，先上锁后检查
• 但是可能会导致空闲让进和有限等待的问题 因为原子性，可能把把两个进程的标志都变成上锁状态

Peterson算法

• 这个算法就是采用一种孔融让梨的思想，当我们一个进程想进入临界区的时候，先将自己的标志为改为true，然后将turn改为对方的进程号（表示如果两个进程都在争资源，就先让对方进入） 进入区的职能就是 1主动争取 2主动谦让 3检查对方是否想用和最后一次是否是自己主动谦让
• 缺点：没有满足让权等待

硬件实现进程互斥

中断屏蔽方法

• 中断屏蔽方法利用开/关中断指令实现（与原语实现思想相同），也就是某进程开始访问临界区到访问结束都不允许被中断，也就不能进行进程切换，因此也就不能发生同时访问临界区的情况
• 缺点：
  • 这种方式是不适用于多处理机的操作系统，因为如果多个CPU同时访问一个临界资源，会导致破坏忙则等待的问题
  • 而且开/关中断这种操作是特权指令，只适用于操作系统内核进程，不适合用于用户进程

TestAndSet指令

• TSL指令是由硬件实现的，执行的过程是不允许被中断的，只能一气合成

• 需要一个共享变量 lock,用来表示临界区是否被占有，true表示已加锁，false表示未加锁

• TSL的内部逻辑是 每次进入 不管有没有加锁，都直接加锁，然后返回old值（原本lock的值）

  • 执行TSL指令时，它的内部运转逻辑：
  • 假设lock现在为false，代表临界资源A空闲，那么我就可以访问这个资源，同时将lock=true，提醒别的进程，这个临界资源A我正在使用，让他们等等
  • 假设lock为true，代表临界资源正在有人使用，所以我必须等待，并且将lock=true，并不影响什么，所以没关系，只是为了让lock为false时可以上锁，将上锁与检查在一个TSL指令完成。

• TSL指令想上锁和检查的变成一气呵成的原子操作

• 还是不满足让权等待的原则，因为暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，而导致忙等

Swap指令

• old是每个进程都要进行的一步，都必须将old=true
• 分析一下这样做的原因：
• 因为lock是某一特定临界资源的共享变量，当每一个进程准备访问这个特定的临界资源时，初始化old=true，然后进入while循环进行交换，如果当前lock是false,则交换后old=false,则当前进程可以跳出循环进入临界区代码段，同时因为交换，lock=old=true上锁，不让别的进程来打扰，别的进程会因为lock变为true,一直在while循环等待,当我使用完临界资源，则将lock=false,此时别的进程再交换old和lock就能判断old=false,可以跳出循环，使用临界资源。