• 首页
  • 留言板
  • 关于
秋雨 De Blog
一个技术小白的个人博客
  1. 首页
  2. 操作系统
  3. 正文

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

2021年5月1日 4868点热度 4人点赞 4条评论

首先我们用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>
using namespace std;
void enter_region() {
	for (int s = 0; s < 10; s++) cout << s << " "; //输出函数
	cout << endl;	//打印回车
}
int main()
{//并发执行f1与f2线程
	for (int i = 0; i < 3; i++)
	{
		thread f1(enter_region);
		thread f2(enter_region);
		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
请按任意键继续. . .

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

//c++实现
#include<thread>
#include<iostream>
using namespace std;
atomic<int> tun;				//线程安全标志位,模拟原子操作
bool i[2] = { false };//初始化
void leave_region(int process)			//退出屏幕打印函数
{
	i[process] = false;
}
void enter_region(int process)				//输出函数
{
	i[process] = true;		//当前进程准备进行屏幕打印
	tun = process;             //将tun设置为要进入屏幕打印的进程
	int other = 1 - process;   //获取另外一个线程
	while (tun == process && i[other] == true);	//循环等待屏幕打印(临界区)空闲
	for (int s = 0; s < 10; s++) cout << s << " "; //输出函数
	cout << endl;	//打印空格
	leave_region(process);  //退出打印屏幕
}
int main()
{//并发执行两个线程
	for (int i = 0; i < 3; i++)l
	{
		thread f1(enter_region,1);
		thread f2(enter_region,0);
		f1.join();//等待f1线程结束
		f2.join();//等待f2线程结束
	}
	system("pause");
}
//java的实现
import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicInteger;

public class fun {
    public static boolean completion[]={false,false}; //初始化
    //标志位.模拟原子操作
    public static AtomicInteger falg=new AtomicInteger(); 
    public static void main(String[] args) throws InterruptedException {
        for (int j=0;j<10;j++){
            Thread thread1=new Thread(()->enter_region(1));
            Thread thread2=new Thread(()->enter_region(0));
            thread1.start();
            thread2.start();
            thread1.join();
            thread2.join();
        }
    }

    public static void enter_region(int process){ //输出函数 enter_region
        int other=1-process;
        completion[process]=true; ////当前进程准备进行屏幕打印
        falg.set(process);
        while (falg.get()==process&& completion[other]==true);//循环等待进入屏幕打印
        for (int i = 0; i < 10; i++) System.out.print(i+" ");//输出函数
        System.out.println();
        leave_region(process);//退出屏幕打印
    }

    public static void leave_region(int process){
        completion[process]=false;
    }

}

此时打印的数字为:

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实现以下这个代码。 后期增加了java的实现方法,可以自己复制跑一次,在这里打印的屏幕函数段称为临界区或临界区段。
可能会有人觉得用互斥锁,或者警告变量的方法都可以实现。但是有一个问题需要我们考虑。
先拿锁变量(用一个布尔变量来代表临界区的锁)来说,如果在线程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退出临界区*/
}



参考书籍:现代操作系统(原书第四版)

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2021年9月4日

fallrain

种一棵树最好的时间是十年前,其次是现在。

点赞
< 上一篇

文章评论

  • 我在吃大西瓜呢

    你好,我想问一下 ,加入是4个进程呢?Peterson算法如何实现呢?

    2021年11月12日
    回复
    • fallrain

      @我在吃大西瓜呢 皮特森算法并不适合多线程的情况下,但可以考虑从采用队列的方式来实现

      2021年11月12日
      回复
  • 我在吃大西瓜呢

    int turn;
    int turnGroup;
    int interested[n];
    int interestedGroup[n/2];

    void lock( int process)
    {
    // 判断是那一组
    int group = process%2;
    int otherGroup = 1 - group;
    interestedGroupt[group] = true;
    turnGroup = group;
    // 组竞争锁
    while (turnGroup == group && interestedGroup[otherGroup] == true){}
    // 组内竞争
    int other = (process+2)%4;
    interested[other] = true;
    turn = process;
    while (turn == process && interested[other] == true){}
    }

    void unlock(int process)
    {
    int group = process%2;
    interestedGroupt[group] = false;
    interested[process] = false;
    }

    特地回来回复一下,这是我们老师给的答案,希望对未来学习的孩子们有帮助吧

    2021年11月16日
    回复
    • fallrain

      @我在吃大西瓜呢 好 谢谢

      2021年11月16日
      回复
  • razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
    回复 我在吃大西瓜呢 取消回复

    fallrain

    种一棵树最好的时间是十年前,其次是现在。

    最新 热点 随机
    最新 热点 随机
    spring 6:HTTP Interface——获取HTTP服务的代理类并放置到IOC容器内 服务端使用C++实现非阻塞的websocket 基于socket实现一个简易的web服务器——非阻塞的模式 wordpress自定义小工具增加友链(二) 基于socket实现一个简易的web服务器 关于进程互斥-Peterson(皮特森)算法的讨论
    服务端使用C++实现非阻塞的websocket spring 6:HTTP Interface——获取HTTP服务的代理类并放置到IOC容器内 基于socket实现一个简易的web服务器 spring-boot重试机制:Guava-Retrying shiro框架多realm登录认证配置 调度算法
    友情连接
    猫饭莲梦青语范文泉博客迎風别葉CODING手艺人
    最近评论
    踏雪飞鸿 发布于 6 个月前(04月06日) 来一起友情链接呀。。
    大雁养老 发布于 11 个月前(10月18日) 太专业了。看一半看不懂了
    云门网 发布于 1 年前(08月17日) 很漂亮的代码,谢谢站长无私分享。 :smile:
    ukk 发布于 1 年前(08月07日) 可以啊我也去掉了。
    我在吃大西瓜呢 发布于 2 年前(11月16日) int turn; int turnGroup; int interested[n]; int...
    最近留言
    大脸猫 发布于 10 个月前(11月15日) :razz:
    april 发布于 1 年前(07月09日) 支持一下,博主快来更新啦
    yingfeng 发布于 1 年前(05月21日) 咕咕咕
    ivkeji 发布于 2 年前(05月30日) 这就博主自己弄的留言板吗?
    麦兜 发布于 3 年前(02月23日) :eek: 不明觉厉,加油加油!

    吉ICP备18007356号

    吉公网安备22020302000184号

    Theme Kratos Made By Seaton Jiang

    COPYRIGHT © 2023 秋雨 De blog ALL RIGHTS RESERVED