秋雨 De Blog

一个技术小白的个人博客

关于进程互斥-Peterson(皮特森)算法的讨论

首先我们用c++实现一个功能 两个线程通过for循环输出0 1 2 3 4 5 6 7 8 9 用c++并发执行来实现。
我们希望程序的输出为:

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .

那么代码可能会是这样的:

#include<thread>
#include<iostream>
void t1(){
for (int s = 0; s < 10; s++) cout << s<<" "; //输出函数
	cout << endl;	//打印回车
}
void t2(){
for (int s = 0; s < 10; s++) cout << s<<" "; //输出函数
	cout << endl;	//打印回车
}
int main()
{//并发执行f1与f2线程
	for (int i = 0;i < 3; i++)
	{
		thread f1(t1);
		thread f2(t2);
		f1.join();//等待f1线程结束
		f2.join();//等待f2线程结束
	}
	system("pause");
}

但此时程序的输出:

00 1 12 2 3 34 54 56 67 78 89 90 01 2 3 4 5 61 72 83 94
5 6 7 8 9
0 01 12 23 34 4 55 66 77 88 99
请按任意键继续. . .

这不是我们想要的程序输出
所以我们需要通过一种方法来限制不让两个线程随意的打印输出到屏幕
下面介绍一种算法来限制两个线程:

#include<thread>
#include<iostream>
using namespace std;
int tun;				//标志位
bool i[2] = {false,false};//初始化
void tc(int a)			//退出屏幕打印函数
{
	i[a] = false;
}
void t1()				//输出函数t1
{
	i[0] = true;		//当前进程准备进行屏幕打印
	tun = 0;			//将tun设置为要进入屏幕打印的进程
	while (tun==0&&i[1]==true);	//循环等待进入屏幕打印
	for (int s = 0; s < 10; s++) cout << s<<" "; //输出函数
	cout << endl;	//打印空格
	tc(0);  //退出打印屏幕
}
void t2()	//输出函数t2
{
	i[1] = true;	//当前进程准备进行屏幕打印
	tun = 1;		//将tun设置为要进入屏幕打印的进程
	while (tun == 1 && i[0] ==true);	//循环等待进入屏幕打印
	for (int s = 0; s < 10; s++) cout << s << " ";	//输出函数
	cout << endl;	//打印空格
	tc(1);	//退出打印屏幕
}
int main()
{//并发执行f1与f2线程程
	for (int i = 0;i < 3; i++)
	{
		thread f1(t1);
		thread f2(t2);
		f1.join();//等待f1线程结束
		f2.join();//等待f2线程结束
	}
	system("pause");
}

此时打印的数字为:

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .

下面来讲解一下这个算法。现在线程1正在打印屏幕,如果他不调用退出函数,那么线程2里面的i[0]==true永远为真,所以线程2就会一直在循环(这种情况叫做忙等待),当调用了退出函数,那么线程2也就进行了打印。这种算法就是著名的 Peterson算法 。这么看代码可能不是很好懂,如果感兴趣,你可以尝试用vs实现以下这个代码。
在这里打印的屏幕的cout函数段称为临界区临界区段。
可能会有人觉得用互斥锁,或者警告变量的方法都可以实现。但是有一个问题需要我们考虑。
先拿锁变量(用一个布尔变量来代表临界区的锁)来说,如果在线程1在查看锁是打开的状态的时候,进程2也发现他是打开的状态,这样就会发生两个进程同时在打印的状态。
再来说说警告变量(用一个值来表示下一个要进入临界区的线程),如果一个线程1做完打印的程序,他就会把变量变成0,但此时线程0并不想进入打印屏幕,而线程1很快又要进入临界区,此时就会发生两个进程都在临界区外的状况。说明这不是 一个很好的方法。
1981年,G.L.peterson发现一种特别好的互斥方法,此方法就是 Peterson算法的。 Peterson 算法的源码为:

#define FLASE 0
#define TRUE  1
#define N 2                           /*进程的数量*/
int turn;                             /*标志位*/
int interested[N]                     /*所有值初始化为0(FALSE)*/
void enter_region(int process)        /*进程是0或1*/
{
    int other;                       /*定义另一个进程号*/
    other=1-process;                 /*另一个进程*/
    interested[process]=TRUE;        /*表示当前进程需要进入临界区*/
    turn=process                     /*将turn设置为当前进程*/
    while(turn==process&&interested[other]==TRUE);
     /*other进程想要进入临界区,把turn变为other,因为process进程为true便陷入循环(忙等待)但只有当porcess进程调用leave_region退出临界区,此时other进程的enter_region函数while循环interested[other]==TRUE成立才会使other进程退出循环进入临界区*/
}
void leave_region(int process)       /*进程推出临界区调用函数*/
{
    interested(process)=FALSE;       /*进程process退出临界区*/
}

有描述错误的地方欢迎指教。
参考书籍:现代操作系统(原书第四版)

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注