37.2° Blog

1.软件实现

1.1单标志法

• 在进入区只做“检查”，不“上锁”
• 在退出区把临界区的使用权转交给另一个进程（相当于在退出区即给另一进程“解锁”，又给自己上锁）
• 主要问题：不遵循“空闲让进”原则

int ture = 0;  // ture 表示当前允许进入临界区的进程号，表达“谦让”。

P0进程：

while(ture != 0);  // 1
critical section;  // 2
true = 1;      // 3
remainder section;  // 4

P1进程：

while(ture != 1);  // 5
critical section;  // 6
true = 0;      // 7
remainder section;  // 8

turn的初值为0，即刚开始只允许0号进程进入临界区。

若P1先上处理机运行，则会一直卡在5。直到P1的时间片用完，发生调度，切换P0上处理机运行。

代码1不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即使切换回P1，P1依然会卡在5。只有P0在退出区将true改为1，P1才能进入临界区。

1.2双标志先检查法

• 在进入区先“检查”后“上锁”，退出区“解锁”
• 主要问题：不遵循“忙则等待”原则

bool falg[2];    // 表示进入临界区意愿的数组
flag[0] = false;  
flag[1] = false;  // 刚开始设置两个进程都不想进入临界区

P0进程：

while(flag[1]);    // 1  
flag[0] = true;    // 2  
critical section;  // 3
flag[0] = false;  // 4
remainder section;  

P1进程：

while(flag[0]);    // 5  如果此时P0想进入临界区，P1就一直循环等待
flag[1] = true;    // 6  标记P1进程想要进入临界区
critical section;  // 7  访问临界区
flag[1] = false;  // 8  访问完临界区，修改标记，P1不想用临界区
remainder section;  

若按照1,5,2,4,3,7...的顺序执行，P0和P1将会同时访问临界区。

双标志先检查法的主要问题是：违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。

1.3双标志后检查法

• 在进入区先“加锁”后“检查”，退出区“解锁”
• 主要问题：不遵循“空闲让进、有限等待”原则，可能导致“饥饿”

bool falg[2];    // 表示进入临界区意愿的数组
flag[0] = false;  
flag[1] = false;  // 刚开始设置两个进程都不想进入临界区

P0进程：

flag[0] = true;    // 1
while(flag[1]);    // 2
critical section;  // 3
flag[0] = false;  // 4
remainder section;  

P1进程：

flag[1] = true;    // 5  标记P1想要进入临界区
while(flag[0]);    // 6  如果P0也想进入临界区，则P1循环等待
critical section;  // 7  访问临界区
flag[1] = false;  // 8  访问完临界区，修改标记，P1不想使用临界区
remainder section;  

若按照1,5,2,6...的顺序执行，P0和P1将都无法进入临界区。

双标志后检查法虽然解决了“忙则等待”的问题，但是又违反“空闲让进、有限等待”原则。会因各进程都长期无法访问临界资源而产生“饥饿”现象。

1.4 Peterson算法

结合双标志位法、单标志位法的思想。如果双方都争着想进入临界区，可以让进程尝试“孔融让梨”（谦让）。

• 在进入区“主动争取—主动谦让—检查对方是否想进，己方是否谦让”
• 主要问题：不遵循”让权等待“原则，会发生”忙等“

bool falg[2];    // 表示进入临界区意愿的数组,初始值都是false
int ture = 0    // turn 表示优先让那个进程进入临界区

P0进程：

flag[0] = true;          // 1  主动争取
trun = 1;            // 2  主动谦让
while(flag[1] && turn == 1);   // 3    检查对方是否也想使用，且最后一次是不是自己说了客气话
critical section;        // 4
flag[0] = false;        // 5
remainder section;  

P1进程：

flag[1] = true;          // 6  表示自己想进入临界区
turn = 0;              // 7  可以让对方优先进入临界区
while(flag[0] && turn == 0);   // 8   对方想进，且最后一次是自己“让梨”，拿自己循环等待
critical section;        // 9  
flag[1] = false;        // 10  访问完临界区，表示自己已经不想访问临界区了
remainder section;  

Peterson算法用软件方式解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

2. 硬件实现方法

.2.1中断屏蔽法

• 使用“开/关中断”指令实现
• 优点：简单高效
• 缺点：只是适用于单处理机；只适用于操作系统内核进程

2.2 TestAndSet指令

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

• old记录是否已被上锁；再将lock设为true；检查临界区是否已被上锁（若已上锁，则循环重复前几步）
• 优点：实现简单；使用于多处理机环境
• 缺点：不满足“让权等待”

// 布尔型共享变量 lock 表示当前临界区是否被加锁
// true 表示已加锁，false 表示未加锁
bool TestAndSet(bool* lock)
{
    bool old;
    old = *lock;  // old用来存放lock原来的值
    *lock = true;  // 无论之前是否已加锁，都将lock设为true
    return old;    // 返回old原来的值
}

// 以下是使用 TSL 指令实现互斥的算法逻辑
while(TestAndSet (&lock));  // “上锁”并“检查”
临界区代码段...
lock = false;    // “解锁”
剩余区代码段...

若刚开始lock是false，则TSL返回old值为false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TSL后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比于软件实现方式，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

2.3 Swap

Swap指令是用硬件实现的，执行的的过程中不允许被中断，只能一气呵成。

// Swap 指令的作用是交换两个变量的值
Swap(bool* a, bool* b)
{
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 以下用 Swap 指令实现互斥的算法逻辑
// lock 表示当前临界区是否被加锁
bool old = true;
while(old == true)
    Swap(&lock, &old);
临界区代码段...
lock = false;
剩余区代码段...

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old变量上），再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。