MyException - 我的异常网
当前位置:我的异常网» 系统运维 » Operation System - Peterson's Solution算法

Operation System - Peterson's Solution算法 解决多线程摩擦

www.MyException.Cn  网友分享于:2014-05-15  浏览:5次
Operation System - Peterson's Solution算法 解决多线程冲突

Person's solution 是用来一种基于软件的解决关键区域问题的算法(critical-section).

它并非完美的,有可能不正确地工作。而且是限制解决两个进程同步的问题。

但是它很简单,很原始,学习起来也是很轻松的。

代码如下:

do {
     flag[i] = true;
     turn = j;
     while (flag[j] && turn == j);
     critical section
     flag[i] = false;
     remainder section
} while (true);

flag[]其实是一个2个变量的数组。这里的i标志一个进程,而j标志另一个进程。

critical section代表是需要互斥进入的一个区间,比如需要修改一些关键的共享数据,这个时候不能让两个进程同时修改,否则就会出现不可预知的结果了。记得好像见过阿里巴巴笔试有这样的题目。

有remainder section并非关键区域,所做的操作是可以并行操作的,结果互不影响。

这里主要的目的就是两个进程互斥地进入critical section。

那么为什么这个算法是可行的呢?

这样的算法可行,需要满足三个条件:

1 Mutual exclusion: 互斥进入

2 Progress : 在非remaider section的进程能在一定时间内进入critical section

3 Bounded waiting: 保证一个进程的等待时间不会过长


分析:

假设1 : 两个进程P1, P2同时执行了do语句:语句执行为:P1 flag[i] = true; P2 flag[j] = true; P1 turn = j; P2 turn = i; P1 while(flag[j] && turn == j) ;

这个时候由于P2已经执行了turn = i语句,所以turn == i,那么P1的语句while(flag[j] && turn == j)的turn ==j就为假了,所以这个时候退出循环,P1进入critical section。

然后P2 while (flag[i] && turn == i);因为这个时候flag[i] 和turn ==i都为真,那么P2就处于等待状态。因为P1和P2是等同的,所以这个情况下,只能有一个进程可以进入critical section的。条件1成立。

如果继续执行,那么就可以分析条件2也是成立的:因为P1进入了critical section之后执行完毕,退出来,那么flag[i] = false,这个语句执行之后,P2 while(flag[i] && turn == i)的flag[i]就为假了。之歌时候P2就可以进入critical section了。

那么继续分析条件3,可以知道P2的等待时间只是P1执行critical section的时间。这个等待时间一般不会过长。

其他情况就更加不会冲突了,可以列举所有语句执行的顺序知道,无论两个进程的语句如何执行,这个算法都是成立的。


--参考资料:Operating System Concepts



文章评论

看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
老程序员的下场
老程序员的下场
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
漫画:程序员的工作
漫画:程序员的工作
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
编程语言是女人
编程语言是女人
我的丈夫是个程序员
我的丈夫是个程序员
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
 程序员的样子
程序员的样子
Java程序员必看电影
Java程序员必看电影
每天工作4小时的程序员
每天工作4小时的程序员
程序员的鄙视链
程序员的鄙视链
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员和编码员之间的区别
程序员和编码员之间的区别
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
旅行,写作,编程
旅行,写作,编程
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
那些争议最大的编程观点
那些争议最大的编程观点
为什么程序员都是夜猫子
为什么程序员都是夜猫子
中美印日四国程序员比较
中美印日四国程序员比较
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
总结2014中国互联网十大段子
总结2014中国互联网十大段子
鲜为人知的编程真相
鲜为人知的编程真相
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员应该关注的一些事儿
程序员应该关注的一些事儿
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
代码女神横空出世
代码女神横空出世
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员必看的十大电影
程序员必看的十大电影
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
一个程序员的时间管理
一个程序员的时间管理
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员都该阅读的书
程序员都该阅读的书
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我是如何打败拖延症的
我是如何打败拖延症的
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有