进程同步 Process Synchronization
1.Background 背景
- 同时访问共享数据可能会导致数据不一致。
- 保持数据一致性需要机制来确保有序执行合作过程。
共享内存解决方案（第3章）限制缓冲区问题同时允许缓冲区中最多n–1个项目。 使用所有N个缓冲区的解决方案并不简单。假设我们通过添加一个变量计数器来修改生产者-消费者代码，该计数器被初始化为0，并且每次将新项目添加到缓冲区时都自增。
即 生产者-消费者问题 （count++/count–）
in machine language 指令扩展:
count++ register1 = counter register1 = register1 + 1
counter = register1
count — register1 = counter register1 = register1 – 1
counter = register1
上下文切换时会导致生产者和消费者的数据不同步。
上下文切换有可能只保存了寄存器状态，没有保存到内存里。
- Atomic operation means an operation that completes in its entirety without interruption.
- 原子操作是指不中断地完整完成的操作。
Race condition（竞争条件）：多个进程访问和同时处理共享数据。 共享数据的最终值取决于哪个过程最后完成。执行的结果取决于特定的顺序进行访问。
- 为防止竞争情况，必须同步并发进程
进程之间竞争资源面临三个控制问题：
| 互斥（mutual exclusion ) | 指多个进程不能同时使用同一个资源 |
| 死锁（deadlock ) | 指多个进程互不相让，都得不到足够的资源。永远得不到资源 |
| 饥饿（starvation ) | 指一个进程长时间得不到资源（其他进程可能轮流占用资源）。资源分配不公平 |
2.临界区问题（n个进程竞争使用某些共享数据）
- 每个进程都有一个代码段，称为关键区（临界区），可以在其中访问共享数据。
- 问题——确保当一个进程在其关键部分执行时，不允许其他进程在其关键部分执行。
临界资源：一次只允许一个进程使用(访问)的资源。如：硬件打印机、磁带机等，软件的消息缓冲队列、变量、数组、缓冲区等。
临界区：访问临界资源的那段代码。伪码：
do {
entry section //进入区
critical section //临界区
exit section //退出区
reminder section //剩余区
} while (1);
解决方案必须满足：
1.Mutual Exclusion（互斥）：如果进程Pi在其关键部分中执行，则其他进程无法在其关键部分中执行。
2.Progress（空闲让进）：如果在关键部分没有执行任何流程，并且有一些进程希望进入其关键部分，则不能无限期地推迟选择下一步将进入关键部分的进程。
3.Bounded Waiting（有限等待）。 在一个进程提出进入其关键部分的请求之后以及在该请求被批准之前，允许其他进程进入其关键部分的次数必须存在界限
*4.让权等待-不是必须的
3.Peterson算法
| Algorithm 1 | |
Shared variables:
|
|
P0:
do {
while (turn != 0) ;
critical section
turn = 1;
remainder section
} while (1);
|
P1:
do {
while (turn != 1) ;
critical section
turn = 0;
remainder section
} while (1);
|
| 缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之 后，Pj使用临界区之前，Pi不可能再次使用临界区。（Satisfies mutual exclusion, but not progress 没有空闲让进） | |
| Algorithm 2 | |
Shared variables:
|
|
P0:
do {
flag[0] = true;
while (flag[1]) ;
critical section
flag [0] = false;
remainder section
} while (1);
|
P1:
do {
flag[1] = true;
while (flag[0]) ;
critical section
flag [1] = false;
remainder section
} while (1);
|
| 缺点：P0和P1可能都进入不了临界区。当P0执行了flag[0] := true后， 然后P1执行了flag[1] := true，这样两个进程都无法进入临界区。（Satisfies mutual exclusion, but not progress requirement.） | |
| Algorithm 3 (Peterson) | |
|
|
P0:
do { flag[0]= true;
turn = 1;
while (flag[1] and turn == 1) ;
critical section
flag[0] = false;
remainder section
} while (1);
|
P1:
do { flag[1]= true;
turn = 0;
while (flag[0] and turn == 0) ;
critical section
flag[1] = false;
remainder section
} while (1);
|
| Meets all three requirements; solves the critical-section problem for two processes. | |
| Multiple-Process Solutions Bakery Algorithm (面包房算法)，Lamport | |
Shared data:
|
|
do {
choosing[i] = true;
number[i] = max(number[0], number[1], …, number [n – 1])+1;
choosing[i] = false;
for (j = 0; j < n; j++)
{ while (choosing[j]) ;
while ((number[j] != 0) && (number[j],j) < (number[i],i)) ;
}
critical section
number[i] = 0;
remainder section
} while (1);
|
|
4.Synchronization Hardware 硬件同步
1.测试与设置 Test-and-Set
Hardware features can make the programming task easier and improve system efficiency.
Hardware instruction: Test and modify the content of a word atomically.
Shared data:
- boolean lock = false;
boolean TestAndSet(boolean &target) {
boolean rv = target;
target = true;
return rv;
}
while(1) {
while (TestAndSet(lock)) ;
critical section
lock = false;
remainder section
};
硬件方法的优点
- 适用于任意数目的进程，在单处理器或多处理器上
- 简单，容易验证其正确性
- 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量
硬件方法的缺点
- 等待要耗费CPU时间，不能实现”让权等待”
- 可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上
- 可能死锁：单CPU情况下,P1执行特殊指令(swap)进入临界区，这时拥有更高优先级P2执行 并中断P1,如果P2又要使用P1占用的资源，按照资源分配规则拒绝P2对资源的要求，陷入忙 等循环。然后P1也得不到CPU，因为P1比P2优先级低。
解决饥饿问题：
Boolean waiting[n], lock ;//to be initialize to false
while(1) {
waiting[i]=true;
key= true;
while ( waiting[i] && key ) key=TestAndSet(lock);
waiting[i]=false;
critical section;
j= (i+1) % n ;
while ((j != i) && !waiting[j]) j= (j+1) % n ;
if (j == i) lock = false ;
else waiting[j] = false ;
remainder section ;
}
2.自旋锁 spinlock
- Windows、Linux内核用来达到多处理器互斥的机制“自旋锁”，它类同于TS 指令机制。自旋锁是一个与共用数据结构有关的锁定机制。
- 自旋锁像它们所保护的数据结构一样，储存在共用内存中。为了速度和使用任 何在处理器体系下提供的锁定机构，获取和释放自旋锁的代码是用汇编语言写的。例如在Intel处理器上，Windows使用了一个只在486处理器或更高处理器上运行的指令。
- 当线程试图获得自旋锁时，在处理器上所有其它工作将终止。因此拥有自旋锁的线程永远不会被抢先，但允许它继续执行以便使它尽快把锁释放。内核对于使用自旋锁十分小心，当它拥有自旋锁时，它执行的指令数将减至最少。
0 条评论