主要观点:通过 4 步过程 S = abcd
和 3 步过程 T = xyz
,研究并发和交错的有效交错情况,在研究通信进程模型时遇到此问题,通过 Raku 语言暴力求解,先将问题简化为计算不同状态下的交错数,递归公式为ct(4, 3) = ct(3, 3) + ct(4, 2) + ct(3, 2)
,基础情况为ct(0, 0) = 1
和ct(x, 0) = ct(0, x) = 1
,后将问题扩展到 N 个进程,需计算所有至少有一个步骤剩余的进程的组合,通过 Raku 语言的grep
、combinations
等函数实现,最终得到计算交错数的函数gc
,此问题对于估计并发系统的行为数量很重要,两个进程的交错数由 Delannoy 数描述,多于两个进程可参考相关论文。
关键信息:
- 有效交错的定义,如
abxcyzd
是有效交错,baxcyzd
不是。 - 递归计算交错数的公式及基础情况。
- Raku 语言中用于实现的函数
grep
、combinations
等的作用。 - 扩展到 N 个进程时的处理方式及相关问题。
重要细节: - 函数
gc
中通过判断$val.none|$val.one > 0
来确定是否继续计算。 - 在处理进程组合时,通过克隆数组并对对应索引的元素进行递减操作。
- 对于多于两个进程的情况,参考相关论文计算“更高维 Delannoy 路径”。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。