3.1. 进程互斥与同步

int turn = 0;  // 表示当前允许进入临界区的进程号
// P0 进程        P1 进程
while (turn != 0);    while (turn != 1);   // 进入区
critical section;    critical section;    // 临界区
turn = 1;        turn = 0;      // 退出区
remainder section;    remainder section;  // 剩余区

bool flag[2];
flag[0] = false; flag[1] = false;
// P0 进程        P1 进程
while (flag[1]);    while (flag[0]);    // 进入区
flag[0] = true;      flag[1] = true;    // 标记某一进程想要进入临界区
critical section;    critical section;    // 临界区
flag[0] = false;    flag[1] = false;  // 退出区
remainder section;    remainder section;  // 剩余区

bool flag[2];
flag[0] = false; flag[1] = false;
// P0 进程        P1 进程
flag[0] = true;      flag[1] = true;    // 标记某一进程想要进入临界区
while (flag[1]);    while (flag[0]);    // 进入区
critical section;    critical section;    // 临界区
flag[0] = false;    flag[1] = false;  // 退出区
remainder section;    remainder section;  // 剩余区

bool flag[2];
int turn = 0;
// P0 进程
flag[0] = true;          // }
turn = 1;            // }进入区
while (flag[1] && turn == 1);  // }
critical section;
flag[0] = false;
remainder section;
// P1 进程
flag[1] = true;          // 表示自己想进入临界区
turn = 0;            // 可以考虑让对方先进入
while (flag[0] && turn == 0);  // 对方想进，且最后一次是自己“让梨”，那就自己等待
critical section;
flag[1] = false;
remainder section;

...
关中断;  // 不允许当前进程被中断
临界区;
开中断;  // 当前进程访问完临界区
...

// bool 型共享变量 lock 表示当前临界区是否被上锁
bool TestAndSet(bool *lock) {
  bool old;
  old = *lock;  // old 用来存放 lock 原来的值
  *lock = true;  // 无论之前是否上锁，都被上锁
  return old;    // 返回 lock 旧值
}
// 使用 TSL 指令实现互斥的算法逻辑
while (TestAndSet(&lock));  // 上锁并检查
critical section;
lock = false;    // 解锁
remainder section;

void Swap(bool *a, bool* b) {
  bool temp = *a;
  *a = *b;
  *b = temp;
}
// bool 型共享变量 lock 表示当前临界区是否被上锁
bool old = true;
while (old == true)
  Swap(&lock, &old);
critical section;
lock = false;    // 解锁
remainder section;

int S = 1;
// wait 原语，相当于“进入区”
void wait(int S) {
  while (S <= 0);  // 如果资源数不够，则循环等待
  S = S - 1;       // 如果够用，则占用一个
}
// signal 原语，相当于“”
void signal(int S) {
  S = S + 1;     // 使用完后释放
}
// 进程 P0            // 进程 P1
wait(S);       wait(S);
使用资源... /*临界区*/ 使用资源...
signal(S);           signal(S);

typedef struct {    // 记录型信号量的定义
  int value;      // 剩余资源数
  struct process *L;  // 等待队列
} semaphore;
// 某进程需要使用资源时，通过 wait 申请
void wait(semaphore S) {
  S.value--;
  if (S.value < 0)  // 使用 block 原语使进程进入阻塞态
    block(S.L);    // 并挂到信号量 S 的等待队列中
}
// 进程使用完后通过 signal 释放
void signal(semaphore S) {
  S.value++;
  if (S.value <= 0)  // 释放后若还有别的进程在等待这种资源
    wakeup(S.L);  // 用 wakeup 原语唤醒等待队列中的一个进程，变为就绪态
}

P1() {
  // 代码 1
  // 代码 2
  // 代码 3
}
P2() {
  // 代码 4
  // 代码 5
  // 代码 6
}

semaphore S = 0;
P1() {
  // 代码 1
  // 代码 2
  V(S);
  // 代码 3
}
P2() {
  P(S);
  // 代码 4
  // 代码 5
  // 代码 6
}

monitor Demo {  // 定义一个名称为 Demo 的管程
  // 定义共享数据结构，对应某种共享资源
  struct S;
  // 对共享数据结构初始化的语句
  init_code() {
    S = 5;
  }
  // 过程 1: 申请一个资源
  take_away() {
    S--;
  }
  // 过程 2: 归还一个资源
  give_back() {
    S++;
  }
}

monitor Demo {
  struct S;  // 共享数据变量
  condition x;  // 定义一个条件变量
  init_code() { /* ... */}
  take_away() {
    if (S <= 0)
      x.wait()  // 资源不够，在条件变量 x 上阻塞等待

    // 资源足够，分配资源，做一系列相应处理
  }
  give_back() {
    // 归还资源，做一系列相应的处理
  if (waitingQueue.length > 0)  // 有进程在等待
    x.signal()  // 唤醒一个阻塞的进程
  }
}