回复 cjmcn-sh 关于线程同步:哲学家问题(0分)

  • 主题发起人 主题发起人 小雨哥
  • 开始时间 开始时间

小雨哥

Unregistered / Unconfirmed
GUEST, unregistred user!
原贴中你提出的问题,我在帖子里给了一个答案,回头我又特别向高手请教了一番,得到正式的答复是:这个问题叫“哲学家用餐问题”。其核心思想还不是简单的同步,savetime告诉我其中还有一个条件,就是哲学家不能随便拿筷子,每个哲学家只能拿他自己左和右边的筷子。
这样,我上次帖子中的答案就少了左右确定模式,那个答案就像是筷子总管,不论谁的筷子,在进入哲学家餐厅后统统上缴,由一个统一的筷子总管来分配筷子和管理不要让某些哲学家撑死而让某些哲学家饿死。
依照标准的哲学家用餐问题,上面的答案显然不能满足要求了。为了满足这些除了思想以外,连筷子都不能凑齐的可怜的哲学家们的用餐需要,于是就存在了二种自管理模式:贪婪模式和自律模式。
 
贪婪模式,这是基于抢先式的一种行为,每个哲学家都瞪着眼看住自己左边或右边的那二根筷子,只要发现一根就先抢到手,直到抢到全部的二根后,这个哲学家就可以进餐了。
通常,我们可以把筷子作为信号量,抢到一根筷子是基本条件,抢到二根筷子是充分条件,这样就可以对每个哲学家的行为归结为:检查信号量A是否满足--->检查信号量B是否满足--->任何满足条件的都先拿到手并宣布信号量被占用--->全部满足--->用餐--->释放信号量--->进入下一轮抢夺,如果未满足--->继续检查未满足的信号量直到成功。
这就意味着假如某一个时刻这些哲学家都仅仅抢到了一根筷子,程序就陷入锁死。如果这些哲学家的行为是一个多线程的并发行为,那么在一个为多 CPU 设计的并行系统中运行这个模拟的时候,这种死锁很快会发生,即便在家用电脑上,这种情况也要发生(迟早而已)。
 
非常谢谢~!QQ中的挂历是你么?真的很谢谢你。呵呵~昨天的粗鲁不要介意!谢谢,呵呵,正在加油学习
 
呵呵,刚刚去写了一段很过瘾的代码,所以中断了一下,现在我接着继续上面的帖子。
QQ因为弄一个什么密码锁,结果造成了无法使用中文密码,我向腾讯投诉了这个巨BUG,腾讯给了个2004的补丁,上是能上了,新版本就不能用了,所以我干脆把大部分工作都转到MSN上去了,以免腾讯再来个BUG,把我的资料全冲光就不好玩了。
贪婪模式的编程非常容易,就是对每个哲学家来说不断地检查自己希望夺得的信号量是否发出信标,这个信号量就是筷子,它开始于一个发出信标的状态,每个哲学家对抢夺来的信号量负责发出占用信号,以避免其他哲学家来抢夺。但不管如何穷极机巧,死锁很难避免。
有一部分高手认为贪婪模式下也有可能协商好避免死锁的办法,就是全部信号量经过一个仲裁器管理,一旦仲裁器发现发生死锁的局面后,由仲裁器强制仲裁。这个想法非常好,问题是仲裁器很难明白怎么样的信号量的组合是表示发生了死锁。在我看来,甚至把仲裁器放在哪里都是一个问题,仲裁逻辑本身也会是一个非常复杂的问题。
 
请问能留下msn的地址么?我的是wjwmww5201@hotmail.com有东西想问,最近正在学习这方面的知识,有很多不能理解,能帮我解惑么?谢谢
 
这样看来要让这些可怜的哲学家避免僵在那里饿死的唯一办法就是自律了。
自律模式是基于哲学家都仅作出有限抢夺而来的。对于5个哲学家的情况,每次最多就是2个哲学家可以获得筷子,剩下一只筷子谁也不去抢夺,让它保持发出信标的状态,直到有更多的筷子加入信标状态,抢夺行为才开始发生。这样就完全避免了可能的死锁。
我有个演示代码写好了,现在没在手边,回头把代码贴上来就可以发现,这个代码非常简单,每个哲学家只管对他将要释放的筷子发出信标就可以了。
 
好的。非常感谢!产生死锁要有四个条件。屏蔽掉可能可以防死锁.
 
另外有个小小的请求。能把演示的源代码和编译好的一同发给我么?
 
高手就是高手!呵呵,谁说DFW高手都走了?只不过高手没兴趣回答那些基础的只要翻翻书就能找到答案的弱智问题。高手更愿意花费经历来思考有深度有意思的问题,对把,小雨哥?嘿嘿,又一次受教了,能加我Q不?或者msn也行
QQ: 185845281
msn: awensoft(at)hotmail.com
有空和您交流交流:)
 
呵呵,记得原来给小雨哥发过邮件的,可是好像邮件地址忘记了,郁闷哦。
 
哎。怎么能忘掉呢??期待中。估计是吃饭去了~等待中......
 
呵呵,记性不好,回头看看还保留了文件不。
 
zqw0117~找到了没有啊~~现在都快疯了。要跳楼了!
 
小雨哥~在不在啊吧代码贴上来看一下吧。
 
哲学家的行为简单地可以归结为:思索-->用餐-->继续思索。
于是可以把行为描述为:
type
TRhilosopher = class(TThread)
private
FTableware: array[0..1] of THandle;
FNameOrder: integer;
FDining: Boolean;
procedure ToPaintComport;
protected
procedure Execute;
override;
procedure Dining(Enter: Boolean);
virtual;
procedure Thinking;
virtual;
public
constructor Create(KitA, KitB: THandle;
NameOrder: integer);
end;

这是一个线程对象,创建的时候就已经明确了将要关心的筷子(KitA,KitB)和名字(NameOrder),
执行起来以后,这个线程对象将顺序完成思索和用餐工作:Tinking、Dining。详细协议如下:
constructor TRhilosopher.Create(KitA, KitB: THandle;
NameOrder: integer);
begin
FTableware[0] := KitA;
FTableware[1] := KitB;
FNameOrder := NameOrder;
FreeOnTerminate := True;
Randomize;
inherited Create(False);
end;

procedure TRhilosopher.Execute;
begin
while (not Terminated)do
begin
if WaitForMultipleObjects(2, @FTableware, True, INFINITE) = WAIT_OBJECT_0 then
begin
Dining(True);
// 进入用餐
Dining(False);
// 退出用餐
Thinking;
// 继续思索
end;
end;
end;

procedure TRhilosopher.Dining(Enter: Boolean);
begin
if Enter then
begin
FDining := True;
ToPaintComport;
Sleep(Random(500) + 100);
// 吃饭消耗时间
end
else
begin
FDining := False;
ToPaintComport;
Sleep(Random(1));
ReleaseSemaphore(FTableware[0], 1, nil);
ReleaseSemaphore(FTableware[1], 1, nil);
end;
end;

procedure TRhilosopher.Thinking;
begin
Sleep(Random(500)+3000);
// 思索消耗时间
end;

procedure TRhilosopher.ToPaintComport;
begin
// 非必需的,目的是在窗体上画出效果
case FNameOrder of
1: Form1.Draw1(FDining);
2: Form1.Draw2(FDining);
3: Form1.Draw3(FDining);
4: Form1.Draw4(FDining);
5: Form1.Draw5(FDining);
end;
end;

其中的 ToPaintComport 方法本身不是这个题目中必需的,在这里添加了这个方法,是因为我代码中有将哲学家线程对象中的行为画到窗体上的步骤(标准应该把这个方法放入Synchronize中,我省略了)。
 
打包的原代码,未包含 exe ,需要自己编译一下(我的环境是 Delphi7)。
http://www.delphibbs.com/keylife/images/u179470/RhilX.rar
 
以上所有这些可以在这里被代码化的一个重要原因是我们仅仅思考了单机上的运行。实际上这个问题还要复杂一些。我和savetime就讨论到了不借助系统的支持如何来实现的状况,以及如何把这个问题放到真正的多处理器环境。这样,这个问题就非常难解,最后的结论是,我们可以做到某种程度的实现,但不能保证在任何环境下都是正确的。
 
非常谢谢啊!!!真的很感谢你!
 
太漂亮了!我真是笨啊,在C++里面做不出来,在Delphi里也做不出来。现在心里有谱了,呵呵,人多就是好,有高人就更好!
 
那如何让这个程序一直运行呢?怎么只运行了一次 就结束了?
 
后退
顶部