[关闭]
@yanglt7 2018-05-22T07:31:39.000000Z 字数 4470 阅读 1111

第9章：同步互斥

操作系统

9.1 背景

并发进程的正确性

进程并发执行的好处

并发创建新进程时的标识分配

原子操作（Atomic Operation）

9.2 现实生活中的同步问题

进程的交互关系：相互感知程度

相互感知的程度 交互关系 进程间的影响
相互不感知（完全不了解其他进程的存在） 独立 一个进程的操作催其他进程的结果无影响
间接感知（双方都与第三方交互，如共享资源） 通过共享进行协作 一个进程的结果依赖于共享资源的状态
直接感知（双方直接交互，如通信） 通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息

9.3 临界区（critical section）

临界区访问规则

临界区的实现方法

禁用中断

不同的临界区实现机制的比较

9.4 禁用硬件中断

缺点

9.5 基于软件的同步方法

第一次尝试

  1. int turn = 0
  2. turn == i//表示允许进入临界区的线程 
  1. do {
  2.     while (turn != i);//条件不成立就可以进入临界区
  3.     critical section
  4.     trun = j;
  5.     remainder section
  6. }  while (1);

第二次尝试

  1. int flag[2];
  2. flag[0] = flag[1] = 0;
  3. flag[i] == 1;//表示线程Ti是否在临界区
  1. do {
  2.     while (flag[j] == 1);
  3.     flag[i] = 1;
  4.     critical section
  5.     flag[i] = 0;
  6.     remainder section 
  7. } while (1);

第三次尝试

  1. int flag[2];
  2. flag[0] = flag[1] = 0;
  3. flag[i] == 1;//表示线程Ti想要进入临界区
  1. do {
  2.     flag[i] = 1;
  3.     while (flag[j] == 1);
  4.     critical section
  5.     flag[i] = 0;
  6.     remainder section
  7. } whlie (1);

Peterson算法

  1. int turn;
  2. boolean flag[];//表示进程是否准备好进入临界区
  1. flag[i] = true;
  2. turn = j;
  3. while (flag[j] && turn ==j) //两个条件只要一个不满足就能进去
  1. flag[i] = false;
  1. do {
  2.     flag[i] = true;
  3.     turn = j;
  4.     while (flag[j] && turn == j);
  5.         critical section
  6.     flag[i] = false;
  7.         remainder section
  8. } while (1);

Dekkers算法

  1. flag[0] := false; 
  2. flag[1] := false;
  3. turn := 0;//orl
  5. do {
  6.     flag[i] = true;
  7.     while flag[j] == true {
  8.         if turn != i {
  9.             flag[i] := false
  10.             while turn != i{}
  11.                 flag[i] := true
  12.         }
  13.     }
  14.     critical section
  15.     turn := j
  16.     flag[i] = false;
  17.     remainder section
  18. } while (true);

N线程的软件方法（Eisenberg 和 McGuire）

turn i-1 i i+1 i+2 n-1 0
处理循环 处理循环 处理循环 处理循环 处理循环 处理循环 处理循环 处理循环 处理循环

9.6 更高级的抽象方法

锁（lock）

  1. lock_next_pid -> Acquire();
  2. new_pid = next_pid++;
  3. lock_next_pid -> Release();

原子操作指令

使用TS指令实现自旋锁（spinlock）

  1. class Lock {
  2.     int value = 0;//初始化锁里的初值为0
  3. }
  4. Lock :: Acquire() {
  5.     while （test-and-set（value））;//spin
  6.     //构造它的请求操作原语，即用TS指令去把value的值读出来，并且往里写1。
  7.     //如果是1，则这个操作就相当于是个检查，如果是0，则设为1，循环结束。
  8. }
  1. Lock :: Release() {
  2.     value = 0;
  3. }

无忙等待锁

  1. Lock :: Acquire() {
  2.     while （test-and-set（value））;//spin
  3. }
  4. Lock :: Release() {
  5.     value = 0;
  6. }
  1. class Lock {
  2.     int value = 0;
  3.     WaitQueue q;//在锁的数据结构里加上一个等待队列，即等待这个锁的相应的进程所排的队列
  4. }
  5. Lock :: Acquire() {
  6.     while （test-and-set（value））;{
  7.         and this TCB to wait queue q;
  8.         schedule();
  10.     }
  11. }
  1. Lock :: Release() {
  2.     value = 0;//表示释放锁
  3.     remove one thread t from q;
  4.     wakeup(t);//将线程从等待队列放到就绪队列。等待时，就处于放弃CPU使用权的状态，实现了让权等待
  5. }

原子操作指令锁的特征

同步方法总结

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注