主要观点:通过 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) `代码` - 列表 > 引用。你还可以使用@来通知其他用户。