KT

同步与互斥_trr3m4e4v3uu3duy

最后修改于

同步实现#

软件实现：单标志、双标志都不可用，仅 peterson 可用

p0(){
  while(p1turn);
  // do;
  p1turn = true;
}
p1(){
  while(!p1turn);
  // do;
  p1turn = false;
}

p0(){
  while(flag[0]);
  flag[1] = true;
  // do;
  flag[1] = false;
}
p1(){
  while(flag[1]);
  flag[0] = true;
  // do;
  flag[0] = false;
}

p0(){
  flag[1] = true;
  while(flag[0]);
  // do;
  flag[1] = false;
}
p1(){
  flag[0] = true;
  while(flag[1]);
  // do;
  flag[0] = false;
}

p0(){
  flag[0] = true;
  turn=1;
  while(flag[1]&&turn == 1);
  // do;
  flag[0] = false;
}
p1(){
  flag[1] = true;
  turn=0;
  while(flag[0]&&turn == 0);
  // do;
  flag[1] = false;
}

硬件实现：中断屏蔽和特殊指令TestAndSet&Swap

bool TestAndSet(bool *lock) {
    boolean old;
    old = *lock;
    *lock = tur;
    return old;
}

void Swap(bool *a,bool *b) {
  boolean temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

#

互斥#

互斥锁：获得锁 / 释放锁。主要缺点在于忙等待。
信号量 P（获取）V（释放）：

wait(S) {
    while(S<=0);
    S-=1;
}
signal(S) {
    S++;
}

typedef struct {
    int value;
    struct process *L;
} semaphore;
void wait(semaphore S) {
    S.value--;
    if (S.value < 0) {
        addProcessToBlock(S.L);
        block(S.L);
    }
}
void signal(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        P = getProcessToWake(S.L);
        wakeup(P);
    }
}

管程：为共享资源抽象出来的数据结构，通过操作该数据结构实现资源互斥。

class Monitor {
    shared_resource S = 5;
    take(){
        S--
    }
    give(){
        S--
    }
}

条件变量