Post

进程同步

Posted Updated
By lreverse
12 min read
进程同步

互斥与临界区问题

  • 竞争条件：多个进程并发访问和操作同一组数据，并且执行结果与访问发生的特定顺序有关
    • 避免竞争条件的一个尝试：给共享数据上锁（每次只允许一个进程操作）
  • 临界资源：每次只允许一个进程使用的资源
  • 临界区：在每个进程中，访问临界资源的那段程序
  • 临界区问题的解决法则
    1. 互斥进入：如果一个进程在临界区中执行，则其他进程不允许进入
    2. 有空让进：若干进程要求进入空闲临界区时，应该使某个进程进入到临界区
    3. 有限等待：从进程发出进入请求到允许进入，不能无限等待
    4. 让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待

把临界资源的访问分为4个部分

  • 进入区：为了进入临界区使用临界资源，在进入区要检查可否进入临界区。
    • 若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区
  • 临界区：进程中访问临界资源的代码
  • 退出区：将正在访问临界区的标志清除
  • 剩余区：代码中的其余部分

临界区问题解决方法

如何进入和退出临界区，以达到进程互斥及同步的目的

1. 一般软件方法

轮换法

进程P0

1
2
3
4

while(turn != 0);
# 临界区
turn = 1;
# 剩余区

进程P1

1
2
3
4

while(turn != 1);
# 临界区
turn = 0;
# 剩余区
  • 问题：
    • 只能交替进入，不满足有空让进

标记法

进程P0

1
2
3
4
5

flag[0] = true;
while(flag[1]);
# 临界区
flag[0] = false;
# 剩余区

进程P1

1
2
3
4
5

flag[1] = true;
while(flag[0]);
# 临界区
flag[1] = false;
# 剩余区
  • 问题：
    • P0和P1的进入请求可能会无限等待

Peterson算法

  • 轮转和标记的结合

进程P0

1
2
3
4
5
6

flag[0] = true;
turn = 1;
while(flag[1] && turn == 1);
# 临界区
flag[0] = false;
# 剩余区

进程P1

1
2
3
4
5
6

flag[1] = true;
turn = 0;
while(flag[0] && turn == 0);
# 临界区
flag[1] = false;
# 剩余区

面包店算法

  • 处理多个进程
  • 每个进程都获得一个序号，序号最小的进入
  • 进程离开时序号为0，不为0的序号即标记

进程Pi

1
2
3
4
5
6
7
8
9

choosing[i] = true;
num[i] = max(num[0], ..., num[n-1]) + 1;
choosing[i] = false;
for(j = 0; j < n; j++){
	while(choosing[j]);
	while((num[j]!=0) && (num[j], j)<(num[i], i));
}
# 临界区
num[i] = 0;

2. 关中断方法

  • 阻止进程调度
  • 简单，但是风险高
    • 若一个进程关中断后不再开中断，则系统可能会因此终止
1
2
3
4

cli();
# 临界区
sti();
# 剩余区

3. 硬件原子指令方法

  • TestAndSet指令：原子操作
1
2
3
4
5
6

boolean TestAndSet(boolean *lock)
{
	boolean old = *loack;
	*lock = true;
	return old;
}

1
2
3
4

while(TestAndSet(&lock));
# 临界区
lock = false;
# 剩余区

4. 信号量方法

Dijkstra提出信号量概念

信号量定义：1个数据结构+2个基本操作

1
2
3
4
5
6
7

struct semaphore
{
	int value;   // 记录资源个数或等待资源进程个数
	PCB *queue;  // 等待在该信号量上的进程队列
}
P(semaphore s);  // 分配资源或组织进程排队等待并记录排队进程数
V(semaphore s);  // 资源归还或唤醒等待的进程
  • 信号量
    • 一个确定的二元组$(s, q)$
    • value >= 0：表示系统中当前可用资源的数目
    • value < 0：表示系统中因请求该类资源而被阻塞的进程数目
  • P操作（wait()）
    • s.value = s.value - 1;
      • 若s.value >= 0，则进程继续执行
      • 若s.value < 0，则进程被阻塞，并将该进程插入到信号量s的等待队列s.queue中
  • V操作（signal()）
    • s.value = s.value + 1;
      • 若s.value > 0，则进程继续执行
      • 若s.value <= 0，则从信号量s的等待队列s.queue中移出第一个进程，使其变为就绪态
  • 优先级翻转问题
    • 基于优先级抢占方式，即当一个高优先级任务访问共享资源时，资源已被一低优先级任务占有，而这个低优先级任务在访问共享资源时可能又被其它一些中等优先级任务抢占，因此造成高优先级任务被许多具有较低优先级任务阻塞。
    • 解决方法：
      • 优先级天花板：当任务申请某资源时，把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级
      • 优先级继承：占有资源的低优先级任务阻塞了高优先级任务时，提升低优先级到高优先级
  • 应用
    • 实现进程同步
    • 实现进程互斥
    • 实现前驱关系

5. 锁

  • POSIX threads是支持多核平台上进行多线程编程的一套API。
  • 线程同步最典型的方法就是用Pthreads提供的锁机制
    • 互斥锁（Mutex）
    • 自旋锁（Spin lock）
    • 读写锁（Read/Write lock）

若一个双核的机器上有两个线程（线程A和线程B），它们分别运行在Core0和Core1上。

  • 互斥锁
    • sleep-waiting
    • 线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁，而此时这个锁正被线程B所持有，那么线程A就会被阻塞
    • Core0会在此时进行上下文切换，将线程A置于等待队列中。而Core0就可以运行其他的任务而不必进行忙等待
  • 自旋锁
    • busy-waiting
    • 线程A使用pthread_spin_lock操作去请求锁，那么线程A就会一直在Core0上进行忙等待并不停的进行锁请求，直到得到这个锁为止
  • 比较
    • 互斥锁更适用于临界区持锁时间比较长的操作
      • IO，代码复杂，循环量大，竞争激烈，单核处理器
    • 自旋锁主要用在临界区持锁时间非常短且CPU资源不紧张的情况下
      • 通常多用在多核的服务器
      • 短期自旋不引起调度和上下文切换，效率更高
  • 读写锁
    • 读写不同的特殊互斥锁
    • 一个读写锁同时只能有一个写者或多个读者，但不能同时既有读者又有写者
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

int ticket = 50;
std::mutex ticket_mtx;

void testThread()
{
	while (1)
	{
		ticket_mtx.lock();
		if (ticket <= 0)
		{
			std::cout << "thread " << std::this_thread::get_id() << " gone\n";
			ticket_mtx.unlock();
			break;
		}
		ticket--;
		std::cout << "thread " << std::this_thread::get_id() << ": " << ticket << std::endl;
		ticket_mtx.unlock();
	}
	
}

int main()
{

	std::thread t1(testThread);
	std::thread t2(testThread);
	std::thread t3(testThread);

	t1.join();
	t2.join();
	t3.join();

	std::cin.get();
	return 0;
}

进程同步

  • 多个进程按确定的协作顺序执行
    • 简单地说：进程B的y操作需要使用到进程A的x操作的结果，所以需要保证先执行进程A的x操作，再执行进程B的y操作
  • 生产者—消费者问题——互斥与同步控制
    • 使用信号量方法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

semaphore fullBuffers = 0;    // 仓库中已填满的货架个数
semaphore emptyBuffers = BUFFER_SIZE;  // 仓库货架空闲个数
semaphore mutex = 1;    // 生产-消费互斥信号
Producer()
{
	while(True)
	{
		生产商品;
		emptyBuffers.P();
		mutex.P();
		商品存入仓库;
		mutex.V();
		fullBuffers.V();
	}
}
Consumer()
{
	while(True)
	{
		fullBuffers.P();
		mutex.P();
		从仓库中取走商品;
		mutex.V();
		emptyBuffers.V();
		消费商品;
	}
}
  • 哲学家进餐问题
    • 若看到有筷子就拿起的话（贪心算法），就容易导致死锁；而如果不仅考虑眼前一步，还考虑下一步，即考虑能不能一次拿起两根筷子，就会避免死锁问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14

semaphore chopstick[5] = {1, 1, 1, 1, 1};  // 初始化信号量
semaphore mutex = 1;  // 取筷子的信号量
Pi(){  // i号哲学家的进程
	while(True){
		mutex.P();
		chopstick[i].P();         // 取左筷子
		chopstick[(i+1)%5].P();   // 取右筷子
		mutex.V();
		eat;
		chopstick[i].V();         // 放回左筷子
		chopstick[(i+1)%5].V();   // 放回右筷子
		think;
	}
}
Course, 操作系统
This post is licensed under CC BY 4.0 by the author.