第 11 天 - 计算并发数

主要观点:通过 4 步过程 S = abcd 和 3 步过程 T = xyz,研究并发和交错的有效交错情况,在研究通信进程模型时遇到此问题,通过 Raku 语言暴力求解,先将问题简化为计算不同状态下的交错数,递归公式为ct(4, 3) = ct(3, 3) + ct(4, 2) + ct(3, 2),基础情况为ct(0, 0) = 1ct(x, 0) = ct(0, x) = 1,后将问题扩展到 N 个进程,需计算所有至少有一个步骤剩余的进程的组合,通过 Raku 语言的grepcombinations等函数实现,最终得到计算交错数的函数gc,此问题对于估计并发系统的行为数量很重要,两个进程的交错数由 Delannoy 数描述,多于两个进程可参考相关论文。
关键信息:

  • 有效交错的定义,如abxcyzd是有效交错,baxcyzd不是。
  • 递归计算交错数的公式及基础情况。
  • Raku 语言中用于实现的函数grepcombinations等的作用。
  • 扩展到 N 个进程时的处理方式及相关问题。
    重要细节:
  • 函数gc中通过判断$val.none|$val.one > 0来确定是否继续计算。
  • 在处理进程组合时,通过克隆数组并对对应索引的元素进行递减操作。
  • 对于多于两个进程的情况,参考相关论文计算“更高维 Delannoy 路径”。
阅读 7
0 条评论