推荐于2018-02-28
展开全部
判定方法分为两个步骤:
- 步骤1:产生调度的优先图;
- 步骤2:采用一个合适的算法(如基于深度优先或广度优先的环检测算法,这是《图论》课程中的内容)检查优先图中是否有有向环。如果有,则该调度就不是冲突可串行化的,否则就是冲突可串行化的。
设S是一个调度,由S构造一个有向图,称为优先图。该图由两部分G=(V,E)组成,其中V是顶点集,E是边集。顶点集由所有参与调度的事务组成。边集由满足下列三个条件之一的边Ti→Tj组成:
- Ti的write(Q)在Tj的read(Q)之前执行;
- Ti的read(Q)在Tj的write(Q)之前执行;
- Ti的write(Q)在Tj的write(Q)之前执行;如果有向图中存在边Ti→Tj,则在任何与S等价的串行调度S'中,Ti都必须出现在Tj之前,即如下所示:<…, Ti,…, Tj,…>。
注意,在画优先图时,不管有多少对冲突的指令使得存在有向边Ti→Tj,在优先图中只画一条从Ti到Tj的边,而不是多条。
- 步骤1:产生调度的优先图;
- 步骤2:采用一个合适的算法(如基于深度优先或广度优先的环检测算法,这是《图论》课程中的内容)检查优先图中是否有有向环。如果有,则该调度就不是冲突可串行化的,否则就是冲突可串行化的。
设S是一个调度,由S构造一个有向图,称为优先图。该图由两部分G=(V,E)组成,其中V是顶点集,E是边集。顶点集由所有参与调度的事务组成。边集由满足下列三个条件之一的边Ti→Tj组成:
- Ti的write(Q)在Tj的read(Q)之前执行;
- Ti的read(Q)在Tj的write(Q)之前执行;
- Ti的write(Q)在Tj的write(Q)之前执行;如果有向图中存在边Ti→Tj,则在任何与S等价的串行调度S'中,Ti都必须出现在Tj之前,即如下所示:<…, Ti,…, Tj,…>。
注意,在画优先图时,不管有多少对冲突的指令使得存在有向边Ti→Tj,在优先图中只画一条从Ti到Tj的边,而不是多条。
2013-07-14
展开全部
你好哦。
有幸看到你的问题。
但是又很遗憾到现在还没有人回答你的问题。也可能你现在已经在别的地方找到了答案,那就得恭喜你啦。
可能是你问的问题有些专业了,没人会。或者别人没有遇到或者接触过你的问题,所以帮不了你。建议你去问题的相关论坛去求助,那里的人通常比较多,也比较热心,可能能快点帮你解决问题。
祝你好运~!
希望我的回答也能够帮到你!
谢谢
有幸看到你的问题。
但是又很遗憾到现在还没有人回答你的问题。也可能你现在已经在别的地方找到了答案,那就得恭喜你啦。
可能是你问的问题有些专业了,没人会。或者别人没有遇到或者接触过你的问题,所以帮不了你。建议你去问题的相关论坛去求助,那里的人通常比较多,也比较热心,可能能快点帮你解决问题。
祝你好运~!
希望我的回答也能够帮到你!
谢谢
本回答被网友采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询