存档

文章标签 ‘程序正确性’

程序的正确性的一些理解–再谈一致性协议

2011年8月27日 sigma 没有评论 5,239 views

这几天,看论文,有个东西一直困惑我。那就是,如何判断程序是正确的,又如何判断程序的执行是正确的。下面谈谈我个人很直白,很初级的理解

个人以为,简单直白讲,程序正确,就是程序能做程序员预期希望做的事;程序执行正确,就是程序能够在一定输入下,输出程序员(设计者)所希望的输出。

个人以为,对于冯诺依曼机器,程序的输入包括:

整个程序空间的内存初始值以及任何改变程序空间内存的事件。

    对串行程序,上面的输入很好理解,其实就是内存初始值,以及各种外部改变内存的IO事件。一句话,串行程序的输入,其实就是内存输入(包括初始值以及外部改变的值)。并且,前述的输入可以确定地决定程序的输出。
    对串行程序,正确的程序,个人以为,就是能够处理程序员所定义的所有输入并得到期望的输出;程序的正确执行,也就是计算机能够将正确的程序得到期望的输出。其实,这里的正确,是基于程序员和计算机的一种协定,即计算机的指令集及每条指令的功能;正确的程序强调的是,程序元能用这套指令集实现所期望的功能;正确的执行,强调的是,计算机能够按指令定义及规范正确的执行每一条指令。
    而对于并行程序,理论上输入也只有这些,但是,现代的并行机器(多核,多处理机),由于同一份内存有多个备份,这时候,程序内部的内存改变,也是影响程序最终的输出。因为,不同备份的内存会出现不一致的情况,而消除不一致的值传播却不是瞬间的,甚至不是固定时间的。也就是说,不同备份内存值改变(包括因为其他备份传播导致的值更新)的时间也能成为一个伪输入,影响最终的结果。
    这时候,程序员和计算机,除了指令集约定,就需要新的约定,那就是一致性约定。对于计算机(或者对于计算机设计者)来说,希望这个值传播能够随意传播,时间没有限制,顺序也没有限制,因为,这样可以乱序执行,可以不用等待,可以提高计算机性能。而对于程序员,希望这个值传播是瞬间的,每个线程,只需要一改写内存,其他的内存备份,马上得到更新。

程序员所希望的一致性协议,叫做严格一致性,但是,这是这从物理上都是不可实现的,计算机肯定更无法实现。而计算机希望的一致性,则是不靠谱的,因为,那种情况下,程序员无法写出具有确定性输出的程序,因为很可能,在程序执行完毕后,同一地址对应不同的内存备份不一样,这时候,到底取哪个值,是一个问题。对于这种计算机来说,并行程序已经无所谓正确与否了。

阅读全文…

无觅相关文章插件,快速提升流量