载入中
|
| 我的分类 |
载入中 |
| 日志更新 |
|
|
| 最新评论 |
|
|
| 站内搜索 |
载入中 |
| 留言板 |
载入中 |
| 链接 |
|
| 管理我的BLOG |
载入中 |
| Blog信息 |
载入中 |
![[rss]](/user1/2746/upload/200510207079.gif) (推荐！)
 (不推荐)
|
|
| |
进程代数的几种有用扩展
翔 发表于 2007-1-24 10:08:00 |
Some Useful Extensions of Process Algebras
CSP、CCS这两种经典进程代数的表达能力有时并不能满足我们的要求，因此人们不断对其进行扩展，比如Pi Calculus就是对CCS加入了mobility，即通道传通道的功能。最近因工作需要，收集了一些进程代数扩展的文章，列举如下：
经典进程代数只支持一对一通讯。若要实现广播、多播，可以参考A Broadcast-based Calculus for Communicating Systems，和A Calculus of Broadcasting Systems. 这里实现broadcast的思路就跟在以太网上做broadcast一样：操作语义中c!和c?通讯后，要把c!写到箭头上，而不是写一个内部动作\tau。这样可以把c!信号传递给下一个可能的接收者。
操作系统中运行的进程支持优先级的概念，但优先级也是经典进程代数中缺少的一个东西。这方面的扩展可以参考Priority in Process Algebras一文。这里的想法是进程仍然有固定的优先级，但通讯操作则有不同的优先级。文章讨论了一个看似自然但是错误的语义，然后给出了一个正确的语义，关键是除了普通的\tau之外，还要定义一个“高优先级”的\tau。文章还指出优先级的概念其实可以分为静态的、动态的、全局的、局部的等等，分别需要定义不同的语义。
根据BPEL规范，如果并行进程的一支出错需要终止，要把其他分支也杀掉。这个就叫做forced termination。实现技术其实不是很困难，在我们的文章Semantics of BPEL4WS-like fault and compensation handling里就有，此处略。
学CSP时我们知道，trace不能表达进程全部的语义，比如内部选择和外部选择就不能通过trace来区分，因而标准的做法是加入failure/divergence这个复杂的模型。其实有一个更好的办法，就是对trace稍作改造，通过巧妙的语义定义（加入一个idling action \delta），就可以在统一的trace框架下表达全部语义，无需引入多余的failure/divergence概念。文章可以参考Retracing the Semantics of CSP，以及Traces, Pomsets, Fairness and Full Abstraction for Communicating Processes。虽然idea非常好，但是这两篇文章写的不是很清楚，还要好好想想。
这个在上面提到的Retracing the Semantics of CSP中就有定义。作者说action trace的一大好处就是非常容易扩展。此外还有一篇文章Towards A Truly Concurrent Model for Processes Sharing Resources，应该更全面。
- asynchronous communication
这个我还没有仔细研究。Retracing the Semantics of CSP也提出了一个解决方案，看起来非常简洁，但是其正确性还值得怀疑……
总结：这篇blog对进程代数的扩展作了个小survey。内容不是很全，比如real time什么的都没有提到。不知道有没有类似的文章？如果没有，说不定就可以去投稿了，呵呵。
|
|
Re:进程代数的几种有用扩展
icebaby(游客)发表评论于2007-9-4 8:30:00 |
 请问FDR如何安装阿？那个licence怎么申请？谢谢 |
|
Re:进程代数的几种有用扩展
游客(游客)发表评论于2007-1-25 20:52:00 |
| 等着阅读你的“投稿”。 |
|
|
