精华内容
下载资源
问答
  • 程序正确证明与并行程序设计

    千次阅读 2011-11-12 21:18:58
    程序正确证明与并行程序设计 (2011-08-20 20:27:59) 标签: 校园 分类: 工作篇 理论计算机科学   关于计算和计算机械的数学理论,也称为计算理论或计算机科学的数学基础。理论...
     
    

    程序正确性证明与并行程序设计

    (2011-08-20 20:27:59)
    标签:

    校园

    分类: 工作篇

    理论计算机科学

     

    关于计算和计算机械的数学理论,也称为计算理论或计算机科学的数学基础。理论计算机科学主要包括:①自动机论与形式语言理论②程序理论③形式语义学④算法分析和计算复杂性理论

     

    学科的产生  在几千年的数学发展史中,人们研究了各种各样的计算,创立了许许多多的算法,但以计算或算法本身的性质为研究对象的数学理论却是到20世纪30年代才发展起来的。当时为了要解决数学基础的某些理论问题,即是否有的问题不是算法可解的,数理逻辑学家提出了几种不同的(后来证明是彼此等价的)算法定义,从而建立了算法理论(即可计算性理论)。30年代前期,K.哥德尔和S.C.克林尼等人创立了递归函数论,将数论函数的算法可计算性刻划为递归性。30年代中期,A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念,将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论,对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机(称为图灵机)中的一种通用机就是存储程序型的。

     

    学科内容

      在这些领域中,自动机理论和形式语言理论是50年代发展起来的。前者的历史还可以上溯到30年代,因为图灵机就是一类自动机(无限自动机)。50年代以来一些学者开始考虑与现实的计算机更相似的理想计算机,J.诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。王浩在50年代中期提出了一种图灵机的变种,这是一种比原来的图灵机更接近现实机器的机器。他还提出一种存储带上的内容不能清除的机器,并证明这种机器是与图灵机等价的。60年代前期,又有人提出具有随机存取存储器的计算机(简称RAM)以及多带图灵机等。

    形式语言理论

      导源于数理语言学中的乔姆斯基理论。在这种理论中,形式语言分为四种:①0型语言;②1型语言;③2型语言;④3型语言。相应地存在着0型、1型、2 型、3型四种形式文法。1型语言又名上下文有关语言,2型语言又名上下文无关语言,3型语言又名正则语言。其中2型语言最受人注意。60年代中期,还发现了这四类语言与四类自动机之间的对应关系(见表)

     

      在上表中,左边所列的语言恰好是右边与之对应的自动机所能识别的语言(见形式语言理论)。

    程序设计理论

      包括程序正确性证明和程序验证,它的一些基本概念和方法是40年代后期诺伊曼和图灵等人提出的。诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。后来图灵又证明了一个子程序的正确性。他的方法是:设有一给定的程序,且有变量X1,X2,…,Xn以及输入谓词P(X1,…,Xn)与输出谓词Q(X1,…,Xn)。如果能证明下列事实:若在程序执行前谓词P(X1,…,Xn)成立,则在程序执行后,谓词Q(X1,…,Xn)成立,程序的正确性得证。

     

      图灵的这一结果长期未引起注意,一直到P.瑙尔在1963年和E.F.费洛伊德在1966年重新提出这一方法后,才引起计算机科学界的重视。此后,有不少理论工作者在从事这方面的研究。但正如E.W.戴克斯特拉在70年代中期曾指出的,实际有效的方法是边设计边验证,在设计完毕时证明或验证的过程也同时结束。J.T.施瓦兹和M.戴维斯70年代后期提出了一种他们称之为“正确程序技术”的软件技术。这种方法是先选定成千种基本程序模块,并借助已知的各种验证方法(包括程序正确性证明)来保证这些基本程序的正确性。然后再提出一组能保持正确性的程序组合规则。这样,就可以通过不断的组合,生成各种各样的程序。

     

      有人指出,程序正确性证明技术所发展出来的“循环不变式”,即一个程序中的某一循环的入口或出口点上所附的谓词,有些文献中称作“归纳断言”,可以用来供程序研究用。也就是说,不像过去那样,对一个给定的程序找出其若干个循环不变式,然后借助这些不变式来证明这个程序的正确性;而是在编制这个程序之前,根据对这一程序的要求,找出若干个循环不变式,然后根据这些不变式来生成这个程序。

     

      自动程序设计的概念也是从40年代提出的。图灵在1947年的一篇论文中,提出借助定理证明的方法来设计程序。他的想法大致如下:设要求设计一个程序,使成为计算一个给定的递归函数F(X)的程序,并令F(n)=m(这里n是任一自然数,m是自然数),需要找到一个证明F(n)=m的构造性证明。在有了这样一个构造性证明以后,就可以从这个证明中提取出F(X)的求值算法,然后生成所需要的程序。图灵的这一思想长时间不为人所知。1969年又有人独立地提出了这一想法。

     

      程序语言的形式语法的研究,从50年代中期起有了较大的发展。而形式语义的研究自60年代以来虽有不少研究工作者从事这方面的工作,提出几种不同的语义理论,主要是操作语义学、指称语义学或称数学语义学、公理语义学和代数语义学,但仍没有一种公认在软件技术中够用的形式语义学,因而需要提出一种更适于用到实际计算中的新的语义学。

     

      在程序正确性证明和形式语义学中应用的程序逻辑,是60年代末发展起来的。这是谓词逻辑的一种扩充。原来的谓词逻辑中是没有时间概念的,所考虑的推理关系是在同一时间里的关系。程序是一种过程,一个程序的输入谓词与输出谓词之间的逻辑关系就不是同一时间里的关系。因此,在有关程序性质的推理中,原来的谓词逻辑不够用,需要有一种新的逻辑。

     

      60年代末,E.恩格勒等人创立了算法逻辑。C.A.R.霍尔也创立了一种程序逻辑。这种逻辑是在原来的逻辑上增加一个程序算子而得到的。例如,可以将程序作为一种新的算子置于一个谓词公式的前面,如表达式

     

      {S}P(X1,…,Xn)表示在程序S执行完毕时,谓词P(X1,…,Xn)成立(这里的)X1,…,Xn是程序S 中的变量)。

    算法分析和计算复杂性理论

      关于算法的复杂性的研究。关于这一领域的名称曾有争论。一般认为,各类具体算法的复杂性的研究称作算法分析,而一般算法复杂性的研究称作计算复杂性理论。计算复杂性理论原是可计算理论的一支,是以各种可计算函数(即递归函数)的计算复杂性(在早期称作“计算难度”)为其研究对象的。可计算性分为理论可计算性和实际可计算性两种。作为可计算性理论一支的计算复杂性理论,是以前者的复杂程度为其研究对象的;而作为计算机科学一个领域的复杂性理论,则是以后者的复杂程度为其研究对象的。

     

      这一分支的基本问题是要弄清楚实际可计算函数类的结构和一些性质。实际可计算性是一个直观的概念。如何对这一概念进行精确的描述,是一个并不容易的问题。60年代中期以来,有关的研究工作者一般是以计算时间多项式有界的函数作为实际可计算的函数。这实际上是一个论题,而不是一个可以在数学中加以证明或否证的命题。有人指出,在有关的多项式次数较高时(如n的情形),很难说是实际可计算的。

     

      另一个带根本性的问题是:确定性机器与非确定性机器的解题能力的比较问题。人们早已知道,确定性图灵机与非确定性图灵机的解题能力是相等的。因为非确定性机器虽比确定性机器效率高,而如果计算时间没有限制,则确定性机器总可以用穷举的方法来模拟非确定性机器。因此,二者的解题能力是一样的。但在计算时间多项式有界时,二者的解题能力是否相等,这就是有名的P=? NP问题。

     

      关于计算和算法(包括程序)的研究,对串行计算的性质研究较多,而对并行计算性质的研究则还很不够(特别是对异步的并行计算更是如此)。因此,关于并行计算的研究很可能将成为计算机理论的研究重点。

     

     

     
     
     
    程序算法的正确性和效率
    1、算法的正确性判定
    研究计算机算法的目的是为了有效地求出问题的解,用计算机语言描述的算法要在计算机上运行,这引出了对算法效率的分析和讨论。例如在象棋比赛中,对任意给出的一种棋局,可以设计一种算法判断这一棋局的输赢,算法需要从开局起对所有棋子可能进行的移动、移动前后的每一对策作检查,做出应走的棋步。计算步骤是有穷的,但在计算机上运算这一算法需要很长的时间。这就说明计算机只能运行在有穷步内终止的算法。
        设计出算法后,应证明该算法对所有可能的合法输入都能计算出正确的结果,这一工作称为算法确认。算法确认与描述实现这一算法的手段无关,例如可以用不同计算机语言来实现这一算法。用算法语言描述构成的程序在计算机上运行,也应证明该程序是正确的,这一工作称为程序证明。
        对程序的测试包括调试和作时空分布图。调试程序是在抽象数据集上执行程序,确定是否会产生错误的结果,如果出现错误,进行修改,再做测试。调试只能指出程序有错误,而不能指出程序不存在错误。程序的正确性证明是计算机科学一个重要的研究领域。作时空分布图是用各种给定的测试数据,去调试已经证明是正确的程序,测定一个算法得出运算结果所用去的时间和空间,给出时空分布图,验证对算法所作的分析是否正确,找出算法最优化的有效逻辑位置,优化算法的效率。
    2、算法的最优性
    求解一个问题,如果规定了算法所允许的运算类型,则所有可能的算法构成了解决这个问题的一个算法类,判断一个算法是否最优的依据,是该算法的平均性态分析。若在选择的算法类中,如果一个算法比所有的算法执行的基本运算少,此算法应该是最优的。
        判断一个算法是否最优,并不需要对算法类中的每一个算法逐个进行分析,可以根据这个算法类的特性,确定所需运算次数的下界,在算法类中所有运算次数等于这个下界的算法是最优的,这也说明最优算法不是惟一的。需要做两件工作确定解决一个问题至少需要多少次运算:① 设计一个有效率的算法A,分析A并找到一个函数F,使对尺度为n的输入,A最多做F(n)次基本运算;② 对某一函数G,证明一个定理,表明对所考虑的算法类中的任何一个算法,存在一个尺度为n的输入,使算法至少要做G(n)次基本运算。
        若函数F与G相等,则算法A是最优的;若不相等,则可能存在一个更好的算法或更好的下界。
    3、分析算法
       (1) 分析算法的两个主要内容
        要分析一个算法首先要确定使用哪些算法以及执行这些算法所用的时间。运算可以分为两类,一类是基本运算,包括加、减、乘、除四种基本的整数算术运算以及浮点算术、比较、对变量赋值和过程调用等。这些运算所用的时间不同,但都是花费一个固定量的时间。另一类运算由一些基本运算的任意长序列组成,以两个字符串的比较运算为例,可以看做是一系列字符比较指令运算,而字符比较指令可以使用移位和位比较指令。比较两个字符的运算时间是固定的,是某一个常数值,而比较两个字符串的运算时间值则与字符串的长度相关。
        其次是确定能反映出算法在各种情况下工作的测试数据集,设计和编制出能够产生最优、最差运算结果的输入数据配置,这些数据配置能够代表可能出现的典型情况。数据配置的设计是创造性的工作,应能最大限度地适应算法,反映算法运行的环境和功能要求。
       (2) 分析算法的两个阶段
        对一个算法作出分析分为两个阶段,即事前分析和事后测试。
        事前分析(priori analysis),求出该算法的一个时间界限函数,用于对计算时间的渐进表示,假定某一算法的计算时间是f(n),其中变量n表示输入或输出量,它可以是两者之和,也可以是它们之一的一种测度,例如数组的维数、图的边数等,f(n)与机器和语言有关。g(n)是在事前分析中确定的某个形式很简单的函数,是独立于机器和语言的函数,例如nm、logN、2n、n!等。给出定义:
        若存在两个正常数c和n0,对于所有的n≥n0,下式成立
                    |f(n)| ≤ c| g(n)|
    记作
                         f(n)= O(g(n))
        因此,当讲一个算法具有O(g(n))的计算时间时,指的是若该算法用n值不变的同一类数据在某台机器上运行时,所用的时间是小于| g(n)|的一个常数倍,所以g(n)是计算时间f(n)的一个上界函数,f(n)的数量级就是g(n),在确定f(n)的数量级时总是试图求出最小的g(n),使得f(n)= O(g(n))。
        事后测试(posteriori testing),收集该算法的执行时间和实际占用空间的统计资料,是在对算法进行设计、确认、事前分析、编码和调试后要做的工作,即作时空性能分布图,事后测试的结果与所用机器相关。要确定算法的精确计算时间,必须了解时钟的精确度以及计算机所用操作系统的工作方式。为避免因所用机器不同而出现误差,有两种可以选用的方法:一种方法是增加输入规模,直到得到算法所需的可靠的时间总量;第二种方法是取足够大的算法重复因子r,将该算法执行r次,然后用总的时间去除以r。
        例如,对于事前分析为O(g(n))时间的算法,选择按输入不断增大其规模的数据集,用这些数据集在计算机上运行算法程序,得出算法所使用的时间,画出这一数量级的时间曲线,并与事前分析所得出的曲线比较。
     

     
     
     
    一。什么是程序的正确性?

    设P是一个抽象问题,x是P的一个输入实例,对于具体的输入x,我们所期望的正确解用f(
    x)来表示,这里f是某种函数关系,它表明了问题P的输入和正确输出之间的对应关系。


    设Q是一个用来解决问题P的确定性程序,Q的输入和对应的输出之间的关系用函数g表示,
    换句话说,对于输入x,程序Q给出的输出是g(x)。

    注意,上一句中强调的“确定性程序”说明对于同样的输入该程序只能得到同样的输出,
    也就是相当于该程序没有side effect,这也是我们可以把一个程序的输入输出之间的关系
    看作一个函数关系的必要条件(否则同一个x就对应了多个不同的g(x)了)。

    在上述定义的条件下,我们说程序Q是正确的,当且仅当函数f = g。

    二。为什么需要引入正确性的证明?

    根据程序正确性的定义,要判断两个程序相等,也就是判断两个函数相等。有两种基本方
    法:

    1。外延相等(Extensional Equality):

    在Zermelo-Fraenkel set theory里有一条Axiom of extension,该公理内容如下:

    \forall A, \forall B, A = B \leftrightarrow  (\forall C, C \in A \leftrightarr
    ow C \in B)

    该公理的意思是说,两个集合外延相等当且仅当它们内部的元素一一对应相等,这条公里
    也可以看作是对“两个集合相等”的定义。因为一个函数就是一个关系,即一个二元对的
    集合,所以根据该公理我们可以定义两个函数外延相等:

    设f, g为函数,则
    (\forall x, f(x) = g(x)) \leftrightarrow f = g

    (注:我们可用一个特殊的符号表示“无定义”,这样当x使得f(x)无定义的时候根据f(x
    )=g(x)可知g(x)也无定义。)

    换句话说,两个函数外延相等是指他们的函数图像相等。

    数学中通常采用的函数相等性定义都是指外延相等,但在计算机科学中外延相等有时候并
    不合理。例如f是冒泡排序的函数,g是快速排序的函数,f和g对于输入的n各元素输出都是
    这n个元素从小到大的排列,从外延性上看函数f和g是相等的,但是在程序设计中不能把他
    们当作同一个函数,因为他们的运行效率不同。

    外延相等的另一个重要的缺陷是,很难证明两个函数外延相等,因为根据定义,必须对所
    有的输入x都有f(x)=g(x)才能说f=g,但实际问题中可取的输入可能是无穷多的,不可能对
    无穷多的输入一一验证。

    通常我们采用测试数据来验证程序,就是在无穷多的输入中取几个特定的输入x,并对f(x
    )和g(x)做验证。假设测试数据的样本空间为集合W,
    \forall x \in W, f(x) = g(x)
    仅仅是f=g的必要条件而不是充分条件。所以这种验证方法只能找出程序可能的错误,却无
    法证明程序的正确性。

    2。内涵相等(Intensional Equality):

    在集合论中,两个集合内涵相等定义如下:

    \forall A, \forall B, A = B \leftrightarrow (\forall C, A \in C \leftrightarro
    w B \in C)

    该定义的意思是,两个集合内涵相等当且仅当它们属于同样的集合。如果把“属于某个集
    合”看作是“满足某个性质”,则两个集合内涵相等当且仅当它们满足同样的性质。

    所以两个函数相等,可以定义为:

    设f和g为函数,P为一个谓词,则
    (\forall P, \forall x, P(f(x)) = P(g(x))) \leftrightarrow f = g

    换句话说,f和g相等当且仅当它们对于同一个输入x的输出f(x)和g(x)都满足或都不满足相
    同的性质P,这里P是任意一个谓词。

    事实上,Hoare的公理化证明就是利用内涵相等来证明一个程序的正确性。顺便说一下,利
    用数学归纳法对一个包含无限子命题的命题的证明实际上也是利用了这种内涵相等的概念


    三。Hoare公理化证明的优点:

    简单来说就是:化无限为有限,不需要对所有的输入进行一一验证,而只需要证明程序的
    输入和输出之间满足某个特定的性质,从而利用内涵性证明程序的正确性。


    四。Hoare公理化证明的缺点:

    1。Hoare提出的那几条公理并不完备,对于复杂的程序,要构造一个完备的公理系统非常
    复杂,需要很多公理; 
    2。即使完整地构造了Hoare的程序公理系统,要证明这个公理系统的完备性和一致性也非
    常复杂,我不知道是否有人做过这件事了。 
    3。在公理系统内定理的形式化证明本身也是一个很复杂的问题,目前尚无非常有效的算法
    来进行定理自动证明。 

    --
    这个世界的一切都值得怀疑,除了正在怀疑着的自我

     
     
     
     
     
    形式化(一)程序正确性证明
    首先要明确什么是程序的正确性这个概念。对于F<P>G,程序的正确性分为两种,一种是完全正确性,指的是程序P一定停机,如果P执行前F断言为真,那么执行P后G断言也为真。还有一种是部分正确性,指的是,如果P停机,那么P执行前F为真,执行后G为真。也就是完全正确性还要多一个一定停机的证明。
    我主要看了一下部分正确性证明。也就是如果停机,那么执行前的断言为真,执行后的断言也一定要是真。这个的证明方法,最出名的是归纳断言法和公理化方法。提出者分别是Floyd和hoare。这两种方法的细节可以参考《软件开发的形式化方法》这本书。我这里只交代一下我所学到的精髓。
    归纳断言法的核心思想就是找出证明程序正确性的一些逻辑表达式,或者叫检验条件。通过证明这些检验条件为真,证明整个程序为真。具体是这么做的,把程序插入断点,这些断点只插在开头,结尾,以及循环开始处。接着在这些断点处建立断言,其实就是程序处于这些位置的时候具有的性质,也是一些逻辑表达式。有了这些断点和断言以后,这些断点就把程序分割成了一段一段的通路。这些通路通过是有条件的,记做R。那么每条通路就可以得出一个检验条件,形式为P(X,Y)^R(X,Y)->Q(X,Y'),也就是通路开头的断言并上通过通路需要的条件蕴含通路末尾的断言。注意通路末尾的断言中Y因为通路的运算转变成了Y‘。有了这些检验条件后,只需要根据各种显而易见的公理,事实(比如gcd(y1,y2)=gcd(y1,y2-y1))证明这些检验条件永真即可证明程序的部分正确性。X表示的是程序的输入,Y表示程序的中间变量,Z表示程序的输出。程序开头的断言描述的输入要满足的条件,是关于X的逻辑表达式。程序中间断点的断言是描述中间变量Y和输入X之间的关系,以及中间变量自己要满足的逻辑表达式。程序结尾处的断点的断言是描述输出Z与输出X之间的关系的逻辑表达式。
    公理化方法是归纳断言法的扩展,区别就在于通过引入了1条赋值公理和4条推理规则规范了归纳断言法中检验条件的抽取,这里检验条件被称为逻辑表达式LOG。本质都是一样的,都是希望把程序的部分正确性演化为一些逻辑表达式的正确。这就是形式化的方法的引入。这里再明确一个概念:不变式。不变式就是指形如{W(X)} Q {U(X,Y)},描述了程序的一个动态的需要保持的性质,它与断言的区别在于,断言描述的式程序处于某个断点处的性质,而不变式是程序整个过程中都要保持的性质(逻辑表达式)。其中,W(X)和U(X,Y)是断言,Q是一段程序。证明Q的正确性就要证明这个不变式的正确性。这个不变式可以利用1条赋值公理和4条推理规则划分为更小的不定式,然后这些不定式最后通过赋值公理转化为LOG逻辑表达式。最终这些逻辑表达式的证明就跟归纳断言法的一样了。你注意观查会发现公理化方法得出的逻辑表达式和归纳断言法得出的检验条件是一样的。只是公理化方法得出这些逻辑表达式的过程严密了一些。
    总结,程序部分正确性的证明,实际上就是设置断点,然后在断点处用断言(逻辑表达式)描述程序的性质,相当于程序在该点处应该具有的性质,然后描述断点之间的通路,也就是小程序片段(分到最后应该就是赋值表达式,这点可以从公理化方法中看出,最后由不变式转化为条件逻辑表达式必然用到赋值公理)执行需要的条件。假设通路开始的性质为真,执行通路的条件为真,那么就一定要求通路结束处的性质为真。这样一段通路一段通路的证明下去,最后就合成了整个程序的部分正确性。
     
     
    形式化(二)软件规格规约方法及语言
    什么是软件规格?软件规格就是对软件所要满足的需求的描述,包括需求规格,功能规格,性能规格以及设计规格。其中需求规格是描述用户对该软件的要求的,功能规格和性能规格是描述“做什么”的问题,以及速度,资源的限制。设计规格解决“怎么做”的问题。
    软件规格分为形式化和非形式化两种。我们研究形式化的软件规格,形式化的软件规格其语法和语意均为精确的无二意的。通过形式化的软件规格,我们可以做软件的自动生成,也是以后程序正确性证明工作的基础。现在不清楚对于测试用例的自动生成有没有作用。
    把软件规格形式化的方法叫做软件规格规约方法。描述形式化的软件规格的语言叫做软件规格语言。
    软件规约方法主要包括两个方面的工作,一个是过程的抽象,一个是数据的抽象。过程的抽象也就是我们不关心具体任务完成的过程,只是对任务要完成的功能进行精确描述。过程抽象可以采用的方法有前后断言法和HOS法。他们都是基于一阶谓词演算来刻画输入和输出之间的关系的。前后断言法是先描述接口,然后用前后断言描述功能。前后断言就是指输入定义域上的关系(前断言),输入定义域和输出值域笛卡尔积上的关系(后断言)。这样就完全规范了程序的过程的功能性,要完成什么工作。绝对没有歧义。至于具体的过程却不关心。HOS方法更简单一些,它通过一些条件以及递归表达式来描述软件过程,写起来很像程序。刚才描述的过程的抽象,那么数据的抽象我们如何做呢?主要有两种方法,一种是代数方法,通过抽象代数中的公理化方法来刻画抽象数据类型中运算的性质。第二种方法是模型方法,这种方法就是《数据结构》课本上给出的那种ADT,就是利用已有的抽象数据类型来构造出待定义的抽象数据类型,用抽象模型(抽象方法的定义)来刻画待定义的抽象数据类型中的运算功能。这里我重点讲一下代数方法,模型方法可以参考《数据结构》。代数方法产生的抽象数据类型的规约ADT-SP由两部分组成,一部分是语法部分Syntax,一部分是公理部分Axiom。Syntax描述程序中所有的用到的已知和待定义的类型名,以及定义域和值域上以及定义域和值域笛卡尔积上的运算符。注意只是描述这些运算从定义域到值域的映射,比如integer->integer。还需要另外一部分Axiom部分描述这些运算应该满足的公理,比如POP(new Stack)=false,就是弹空栈要出错之类的。这样有了过程抽象,也有了数据抽象,就可以得出形式化的软件规格了。
    如何书写这些形式化的软件规格呢?这就需要我们采用软件规格语言来写。具体分为两类:面向模型和面向性质的。面向模型的包括:VDM,Z,petri网,自动机。面向性质的包括:代数规约,时序逻辑等。我的理解是面向模型的方法是要构建模型,由小模型一点一点描述出整个软件的模型,通过模型来描述这个软件的规格。面向性质则是用代数,逻辑的表达式来描述软件要满足的性质,通过性质的描述来说明这个软件的规格。后面我会重点介绍应用比较多的Z语言。
    最后有个问题就是,软件规格描述出来了,如何确保这个软件规格是正确合适的?我认为通过两个性质来保证,一个是一致性,一个是完备性。一致性就是说,在我们描述的规格中,每一个合法输入都有输出与之对应,并且满足前后断言法那种后断言描述的输入与输出要保持的关系。这是保证我们的规格是正确的,没有错误在里面。完备性是指我们的规格可以导出所有用户的要求。就是说我们把用户的要求用输入X输出Y之间的谓词表达式来表示这些要求。Ri(X,Y)表示一条要求,那么SS是Ri的集合,就是所有的用户要求。我们说的完备性就是SS中的每一条Ri都可以由我们规格中描述的X与Y的关系推导出。
     
     
    形式化规约语言的分类及特点
    Z,VDM,和Larch是较早发展起来的形式规约语言,它们重点研究顺序性系统的行为描述.采用的方法是:用集合,关系,函数等数学概念来描述系统的状态,状态的迁移用前后断言(条件)来表示.同时,另一类方法如:CSP,CCS,Statecharts,时序逻辑则重点描述并发系统的行为,它们用序列,树结构,及事件的偏序集合来描述系统行为.另外,形式规约语言RAISE能够描述具有大规模状态空间的系统,LOTOS能够处理大型复杂并发系统.
     
     
     
     
     
     
     
     
     

    并行程序设计

      目前并行程序设计的状况是:①并行软件的发展落后于并行硬件;②和串行系统的应用软件相比,现今的并行系统应用软件甚少且不成熟;③并行软件的缺乏是发展并行计算的主要障碍;④而且这种状态仍在继续.
      其原因是:①并行程序设计不但包含了串行程序设计,而且还包含了更多的富有挑战性的问题;②串行程序设计仅有一个普遍被接受的冯*诺依曼模型,而并行计算模型虽有好多,但没有一个被共同认可;③并行程序设计对环境工具的要求远比串行程序设计先进得多;④串行程序设计比较适合于自然习惯,且人们在过去积累了大量的编程知识和宝贵的软件财富.
      并行程序设计:对于所希望的应用,很多并行代码似乎不存在的;即使有,也常不能用于用户的并行机上.因为并行代码原来都是为不同的并行结构写的.
      它的问题是:至今并行算法范例不能被很好地理解和广泛地接受;并行程序设计是建立在不同的计算模型上的,而它们没有能像冯*诺依曼模型那样被普遍的接受和认可.绝大部分被使用的并行程序设计语言都是Fortran和C的推广,他们都不能够充分地表达不同并行结构的特点,既不成熟也不通用.并行程序设计工具依赖于具体的并行结构和计算机代的更迭,既不通用也不稳定,在某个并行平台上开发的并行程序很难移植到别的或将来的并行机上.
      目前并行编程类型逐渐汇聚于两类:用于PVP,SMP和DSW的共享变量的单地址空间模型和用于MPP和机群的消息传递的多地址空间模型.
      并行编程模型逐渐汇聚于三类标准模型:数据并行(如:HPF),消息传递(如:MPI和PVM),和共享变量(如OpenMp).
      现在人们希望高性能的并行机应是具有单一系统映像的巨大的工作站,使得很多用户都能利用增强处理能力和储存容量来运行多个串行作业,这就是所谓的串行程序并行系统SPPS.
      当我们在实际的并行机上设计并行程序时,绝大部分均是采用扩展Fortran和C语言的办法,目前有三种扩展的办法:一是库函数法:除了串行语言所包含的库函数外,一组新的支持并行性和交互操作的库函数(如MPI消息传递库和POSIXPthreads多线程库)引入到并行程序设计中。二是新语言结构法:采用某些新的语言结构来帮助并行程序设计以支持并行性和交互操作(如Fortran 90 中的聚集数组操作); 三是编译制导法:程序设计语言保持不变,但是将称之为编译制导的格式注释引入到并行程序中.
     
     
     
    本文介绍了什么是程序的完全正确性、部分正确性、终止性,并通过实例,介绍了利用不变式断言法和计数器方法分别证明程序的部分正确性和终止性的具体方法步骤。
    展开全文
  • OS X上基于OpenMP进行并行程序开发

    千次阅读 2016-08-31 20:31:11
    OpenMP是目前被广泛接受的,用于共享内存并行系统的多处理器程序设计的一套指导的编译处理方案。它提供了对并行算法的高层的抽象描述。本文主要来讨论在OS X系统上利用GCC来开发基于OpenMP的并发程序的基本方法

    OpenMP是目前被广泛接受的,用于共享内存并行系统的多处理器程序设计的一套指导性的编译处理方案。它提供了对并行算法的高层的抽象描述,程序员通过在源代码中加入专用的pragma来指明自己的意图,由此编译器可以自动将程序进行并行化,并在必要之处加入同步互斥以及通信。在Windows下利用Visual Studio来开发基于OpenMP的并发程序已有很多现成的资料可查,本文主要来讨论在OS X系统上利用GCC来开发基于OpenMP之并发程序的基本方法。

    在前面的文章《OS X上安装Homebrew和GCC的图文攻略》里,我们已经在OS X上搭建了一个GCC的开发环境。注意新版的Xcode已经不再支持OpenMP,因此你仍然需要安装并配置一个纯GCC的环境,而非用苹果的clang来进行映射。


    打开Terminal,然后新建一个子目录来存放即将要编辑的程序源文件,再用nano新建一个新的CPP文件:

    > mkdir omp_test
    > cd omp_test
    > nano omp_test.cpp

    然后在nano中编辑如下所示之示例代码:

    #include <iostream>
    #include <cmath>
    #include <vector>
    #include <omp.h>
    
    int main( int argc, char* argv[] )
    {
        omp_set_num_threads( 8 );
    
        double pi = acos( -1.0 );
    
        std::cout << "Allocating memory ..." << std::endl;
        std::vector<double> my_vector( 128000000, 0.0 );
        std::cout << "Done!" << std::endl << std::endl;
    
        std::cout << "Entering main loop ... " << std::endl;
    
    #pragma omp parallel for
        for( int i=0; i < my_vector.size(); i++ )
        {
            my_vector[i] = exp( -sin( i*i + pi*log(i+1) ) );
        }
        std::cout << "Done!" << std::endl;
    
        return 0;
    }

    你的代码编辑界面应该是类似下面这样的:
    这里写图片描述

    nano是Unix和类Unix系统中的一个文本编辑器,我们这里不打算详细讨论它的使用方法,你可以查阅相关资料以了解更多。

    当然你也完全可以在拥有GUI的Sublime Text下来编辑你的源代码,我们这里仅仅是要让大家体验一下在命令行模式下开发的感觉。

    接下来我们就来编辑Makefile文件,请在Terminal上使用下面命令:

    > nano Makefile

    跟前面编辑源代码的方法类似,在nano中编辑如下所示的内容:

    CC := g++-5
    # replace this with your correct compiler as identified above
    
    ARCH := core2 # Replace this with your CPU architecture.
    # core2 is pretty safe for most modern machines. 
    
    CFLAGS := -march=$(ARCH) -O3 -fopenmp -m64 -std=c++11
    
    COMPILE_COMMAND := $(CC) $(CFLAGS)
    
    OUTPUT := my_test
    
    all: omp_test.cpp
        $(COMPILE_COMMAND) -o $(OUTPUT) omp_test.cpp
    
    clean:
        rm -f *.o $(OUTPUT).*

    编辑完成后退出nano回到Terminal,然后在命令下输入:

    > make
    > ./my_test

    刚刚编写的OpenMP程序就会被执行,输出应该如下:
    Allocating memory …
    Done!

    Entering main loop …
    Done!

    最后是一个可能 Troubling shooting(尽管上面的代码我已经做了调整,应该不会出现下面这个问题): If the make command gives errors like “** missing separator”, then you need to replace the white space (e.g., one or more spaces) at the start of the “$(COMPILE_COMMAND)” and “rm -f” lines with a single tab character.

    后续我们还会介绍更多关于OpenMP并行编程方法的技术。


    参考文献:

    http://mathcancer.blogspot.com.au/2016/01/PrepOSXForCoding-Homebrew.html
    最后补刀一个来自Intel的绝佳OpenMP编程入门视频课程:
    https://www.youtube.com/watch?v=nE-xN4Bf8XI&feature=youtu.be&list=PLLX-Q6B8xqZ8n8bwjGdzBJ25X2utwnoEG

    (全文完)

    展开全文
  • JAVA并行程序基础 学习笔记

    千次阅读 多人点赞 2021-03-13 09:08:24
    学习资料:《深入理解计算机系统》,《Java高并发程序设计》,《Java并发编程实战》,《Java并发编程的艺术》,《Java核心技术卷1》多线程一章,极客时间王宝令的Java并发编程实战课程… 以下大部分阐述来自上述书籍...

    学习资料:《深入理解计算机系统》,《Java高并发程序设计》,《Java并发编程实战》,《Java并发编程的艺术》,《Java核心技术卷1》多线程一章,极客时间王宝令的Java并发编程实战课程…

    以下大部分阐述来自上述书籍与课程中个人认为很重要的部分,也有部分心得体会,如有不准确的地方,欢迎评论区告诉我。后续还会更新并发包,并发算法等各种并发相关笔记,点点关注不迷路!ヽ(✿゚▽゚)ノ

    一.概念辨析

    1.进程 & 线程

    进程:操作系统对一个正在运行的程序的一种抽象。在一个系统上可以同时运行多个进程,而每个进程都好像在独占地使用硬件。(进程是线程的容器)
    而并发运行,则是说一个进程的指令和另一个进程的指令是交错执行的。这种机制叫做上下文切换。
    举例:当你双击一个exe程序时,这个.exe文件的指令就会被加载,那么你就能得到一个关于这个程序的进程。进程是活的,是正在被执行的,你可以通过任务管理器看到你电脑正在执行的进程。

    在这里插入图片描述

    线程:一个进程由将多个称为线程的执行单元组成,每个线程都运行在进程的上下文中,并共享同样的代码和全局数据。因为多线程之间比多进程之间更容易共享数据,也因为线程一般来说都比进程更高效。线程可以实现宏观上的“同时”执行,实际上是快速切换线程来达到几乎同时执行的效果。也可以称线程为轻量级进程,它是程序执行的最小单位。多核处理器中,同一个进程的不同线程也可以在不同的cpu上同时运行,此时就需要考虑通过锁,来保证操作的原子性。

    多进程与多线程的本质区别:每个进程都拥有自己的一整套变量,而线程则共享数据。多线程比多进程开销小得多。(当然也要看具体的操作系统,Windows和Linux是不同的,Windows开进程开销大,Linux开线程开销大,因此 Windows 多线程学习重点是要大量面对资源争抢与同步方面的问题,Linux 下的学习重点大家要学习进程间通讯的方法)

    2.同步 & 异步

    同步 Synchronous方法调用一旦开始,调用者必须等到方法调用返回后,才能继续后续的行为。

    异步 Asynchronous方法调用更像一个消息传递,一旦开始,方法调用就会立即返回,调用者就可以继续后续的操作。

    举例
    比如有一个计算圆周率小数点后 100 万位的方法pai1M(),这个方法可能需要执行俩礼拜,如果调用pai1M()之后,线程一直等着计算结果,等俩礼拜之后结果返回,就可以执行 printf(“hello world”)了,这个属于同步;如果调用pai1M()之后,线程不用等待计算结果,立刻就可以执行 printf(“hello world”),这个就属于异步。

    区别:同步就是要等到整个流程全部结束,而异步只是传递一个接下来要去做什么什么事情的消息,然后就会去干其他事。

    同步,是 Java 代码默认的处理方式。如果你想让你的程序支持异步,可以通过下面两种方式来实现:

    1.调用方创建一个子线程,在子线程中执行方法调用,这种调用我们称为异步调用;
    2.方法实现的时候,创建一个新的线程执行主要逻辑,主线程直接return,这种方法我们一般称为异步方法。

    3.并行 & 并发

    并行 Parallel:多个cpu实例或者多台机器同时执行一段处理逻辑,是真正的同时。

    并行二定律

    1.Amdahl定律 加速比=1/[F+(1-F)/n](n为处理器储量,F为并行比例) 由此可见,为了提高系统的速度,仅仅增加CPU处理器数量不一定能起到有效的作用。需要根本上修改程序的串行行为,提高系统内并行化的模块比重。

    2.Gustafson定律 加速比=n-F(n-1) 如果串行化比例很小,并行化比例很大,那么加速比就是处理起个数,只要不断累加处理起,就能获得更快的速度

    并发 ConCurrent:通过cpu调度算法,让用户看上去同时执行,实际上从cpu操作层面不是真正的同时。并发往往在场景中有公用的资源,那么针对这个公用的资源往往产生瓶颈,我们会用TPS或者QPS来反应这个系统的处理能力。

    总述
    并行就是同时进行,并发则是上下文快速切换(进程的运行不仅仅需要CPU,还需要很多其他资源,如内存,显卡,GPS,磁盘等等,统称为程序的执行环境,也就是程序上下文。)。单核处理器中,为了避免一个进程一直在使用CPU,调度器快速切换CPU给不同进程,于是在使用者看来程序是在同时运行,这就是并发,而实际上CPU在同一时刻只在运行一个进程。
    CPU进程无法同时刻共享,但是出现一定要共享CPU的需求呢?此时线程的概念就出现了。线程被包含在进程当中,进程的不同线程间共享CPU和程序上下文。(共享进程分配到的资源)单CPU进行进程调度的时候,需要读取上下文+执行程序+保存上下文,即进程切换。
    如果这个CPU是单核的话,那么在进程中的不同线程为了使用CPU核心,则会进行线程切换,但是由于共享了程序执行环境,这个线程切换比进程切换开销少了很多。在这里依然是并发,唯一核心同时刻只能执行一个线程。
    如果这个CPU是多核的话,那么进程中的不同线程可以使用不同核心,真正的并行出现了。

    4.死锁、饥饿、活锁

    死锁:所有线程互相占用了对方的锁,导致所有线程挂起。
    死锁四条件:
    1.互斥,共享资源 X 和 Y 只能被一个线程占用;
    2.占有且等待,线程 T1 已经取得共享资源 X,在等待共享资源 Y 的时候,不释放共享资源 X;
    3.不可抢占,其他线程不能强行抢占线程 T1 占有的资源;
    4.循环等待,线程 T1 等待线程 T2 占有的资源,线程 T2 等待线程 T1 占有的资源,就是循环等待。

    解决方法:破坏死锁后三个条件的任意其一(互斥一般不应被破坏)。
    1.对于“占用且等待”这个条件,我们可以一次性申请所有的资源,这样就不存在等待了。若申请不成功,wait();申请成功了,notifyAll()。
    2.对于“不可抢占”这个条件,占用部分资源的线程进一步申请其他资源时,如果申请不到,可以主动释放它占有的资源,这样不可抢占这个条件就破坏掉了。
    3.对于“循环等待”这个条件,可以靠按序申请资源来预防。所谓按序申请,是指资源是有线性顺序的,申请的时候可以先申请资源序号小的,再申请资源序号大的,这样线性化后自然就不存在循环了。

    饥饿:某些线程因为某些原因(优先级过低)无法获得所需的资源,导致无法运行。

    活锁:两个线程互相释放资源给对方,从而导致没有一个线程可以同时拿到所有资源正常执行。(出电梯时,和一个进电梯的人互相谦让,导致进电梯的人进不了,出电梯的人出不去)
    解决方法:让等待时间设定为随机值。

    为了处理这种异常情况,可以通过 jstack 命令或者Java VisualVM这个可视化工具将 JVM 所有的线程栈信息导出来,完整的线程栈信息不仅包括线程的当前状态、调用栈,还包括了锁的信息。

    5.锁 & 监视器(管程)

    锁为实现监视器提供必要的支持。

    是对象内存堆中头部的一部分数据。JVM中的每个对象都有一个锁(或互斥锁),任何程序都可以使用它来协调对对象的多线程访问。如果任何线程想要访问该对象的实例变量,那么线程必须拥有该对象的锁(在锁内存区域设置一些标志)。所有其他的线程试图访问该对象的变量必须等到拥有该对象的锁有的线程释放锁(改变标记)。锁,应是私有的、不可变的、不可重用的。
    细粒度锁:用不同的锁对受保护资源进行精细化管理,能够提升性能。

    1) 锁用来保护代码片段,任何时刻只能有一个线程执行被保护 的代码。
    2) 锁可以管理试图进入被保护代码的线程
    3) 锁可以拥有一个或者多个相关的条件对象
    4) 每个条件对象管理那些已经进入被保护的代码段,但还不能运行的线程

    用锁的最佳实践
    永远只在更新对象的成员变量时加锁
    永远只在访问可变的成员变量时加锁
    永远不在调用其他对象的方法时加锁

    监视器 Monitor是一中同步结构,它允许线程同时互斥(使用锁)和协作,即使用等待集(wait-set)使线程等待某些条件为真的能力。监视器也可以叫管程,意思是管理共享变量以及对共享变量的操作过程,让他们支持并发。管程和信号量是等价的,所谓等价指的是用管程能够实现信号量,也能用信号量实现管程。但是管程更容易使用,所以 Java 选择了管程。管程理论上能解决一切并发问题。

    他们是应用于同步问题的人工线程调度工具。讲其本质,首先就要明确monitor的概念,Java中的每个对象都有一个管程,来监测并发代码的重入。在非多线程编码时该管程不发挥作用,反之如果在synchronized 范围内,管程发挥作用。

    管程至少有两个等待队列。一个是进入管程的等待队列一个是条件变量对应的等待队列。后者可以有多个。

    wait/notify/notifyAll必须存在于synchronized块中。并且,这三个关键字针对的是同一个管程。这意味着wait之后,其他线程可以进入同步块执行。

    当某代码并不持有管程的使用权时,去wait或notify,会抛出java.lang.IllegalMonitorStateException。也包括在synchronized块中去调用另一个对象的wait/notify,因为不同对象的管程不同,同样会抛出此异常。

    管程三大模型:Hasen 模型、Hoare 模型和 MESA 模型

    1)Hasen 模型,要求 notify() 放在代码的最后,这样 T2 通知完 T1 后,T2 就结束了,然后 T1再执行,这样就能保证同一时刻只有一个线程执行。

    2)Hoare 模型,T2 通知完 T1 后,T2 阻塞,T1 马上执行;等 T1执行完,再唤醒 T2,也能保证同一时刻只有一个线程执行。但是相比 Hasen 模型,T2 多了一次阻塞唤醒操作。

    3)MESA 管程,T2 通知完 T1 后,T2 还是会接着执行,T1 并不立即执行,仅仅是从条件变量的等待队列进到入口等待队列里面。这样做的好处是 notify()不用放到代码的最后,T2 也没有多余的阻塞唤醒操作。但是也有个副作用,就是当 T1 再次执行的时候,可能曾经满足的条件,现在已经不满足了,所以需要以循环方式检验条件变量。

    Hasen 是执行完,再去唤醒另外一个线程。
    Hoare,是中断当前线程,唤醒另外一个线程,执行完再去唤醒。
    Mesa是进入等待队列(不一定有机会能够执行)。

    MESA 管程特有的编程范式:
    while(条件不满足) {
    	 wait();
    }
    

    Java 参考了 MESA 模型,语言内置的管程(synchronized)对 MESA 模型进行了精简。MESA 模型中,条件变量可以有多个,Java 语言内置的管程里只有一个条件变量,而 Java SDK 并发包实现的管程支持多个条件变量,不过并发包里的锁,需要开发人员自己进行加锁和解锁操作。

    二.并发编程的核心问题

    分工指的是如何高效地拆解任务并分配给线程。类似于“烧水泡茶”问题。

    同步指的是线程之间如何协作。当某个条件不满足时,线程需要等待,当某个条件满足时,线程需要被唤醒执行。

    互斥则是保证同一时刻只允许一个线程访问共享资源。也就是所谓的“线程安全”。核心技术为“锁”。

    三.并发的隐患

    【补充】

    数据竞争: 当多个线程同时访问同一数据,并且至少有一个线程会写这个数据的时候,如果我们不采取防护措施,那么就会导致并发 Bug。

    竞态条件,指的是程序的执行结果依赖线程执行的顺序。当你看到代码里出现 if 语句的时候,就应该立刻意识到可能存在竞态条件,因为可能同时在一个状态的时候,有多个线程通过了这个条件,然而他们之后的操作都可能使得这个条件不成。解决办法就是让这些方法之间互斥,例如可以采用单例模式,然后让所有方法以单例为加锁对象同步。

    1.缓存导致的可见性问题

    可见性:一个线程对共享变量的修改,另外一个线程能够立刻看到。

    volatiole变量的写先于读发生,保证了它的可见性。

    多核时代,每颗 CPU 都有自己的缓存,当多个线程在不同的 CPU 上执行时,这些线程操作的位置是不同的 CPU缓存,他们之间不具有可见性。

    2.线程切换带来的原子性问题

    原子性:一个或者多个操作在 CPU 执行的过程中不被中断的特性。

    “原子性”的本质其实不是不可分割,不可分割只是外在表现,其本质是多个资源间有一致性的要求,操作的中间状态对外不可见。

    举例

    例1:同时向一个变量发起两次修改请求,可能会导致变量修改失败。

    补充
    若要对一个变量进行操作
    至少需要三条 CPU 指令:

    指令 1:把变量从内存加载到 CPU 的寄存器;
    指令 2:在寄存器中修改变量;
    指令 3:将结果写入内存/缓存。

    在线程A将结果写入内存之前,线程B可能已经读入了初始的变量值。 然后线程A将修改结果写入内存后,线程B也将结果写入内存。这会导致线程A的修改被完全覆盖,因为线程B的初始值读入的是线程A修改之前的变量值。

    例2:在32位的系统上,读写long(64位数据)

    使用双线程同时对long型数据进行写入或读取。
    如果新建多个线程同时改变long型数据的值,最后的值可能是乱码。因为是并行读入的,所以可能读的时候错位了。

    3.编译带来的有序性

    有序性:程序按照代码的先后顺序执行。 编译器为了优化性能,有时候会改变程序中语句的先后顺序,例如程序中:“a=6;b=7;”编译器优化后可能变成“b=7;a=6”,有时候会导致意想不到的bug。
    (指令重排对于CPU处理性能是十分必要的)

    举例

    在 Java 领域一个经典的案例就是利用双重检查创建单例对象,例如下面的代码:在获取实例 getInstance() 的方法中,我们首先判断 instance 是否为空,如果为空,则锁定 Singleton.class 并再次检查 instance 是否为空,如果还为空则创建 Singleton 的一个实例。

    public class Singleton {
      static Singleton instance;
      static Singleton getInstance(){
        if (instance == null) {
          synchronized(Singleton.class) {
            if (instance == null)
              instance = new Singleton();
            }
        }
        return instance;
      }
    }
    

    假设有两个线程 A、B 同时调用 getInstance() 方法,他们会同时发现 instance == null ,于是同时对Singleton.class 加锁,此时 JVM 保证只有一个线程能够加锁成功(假设是线程 A),另外一个线程则会处于等待状态(假设是线程B); 线程 A 会创建一个 Singleton 实例,之后释放锁,锁释放后,线程 B 被唤醒,线程 B再次尝试加锁,此时是可以加锁成功的,加锁成功后,线程 B 检查 instance == null 时会发现,已经创建过 Singleton实例了,所以线程 B 不会再创建一个 Singleton 实例。

    这看上去一切都很完美,无懈可击,但实际上这个 getInstance() 方法并不完美。问题出在哪里呢?出在 new 操作上,我们以为的new 操作应该是:

    分配一块内存 M;
    在内存 M 上初始化 Singleton 对象;
    然后 M 的地址赋值给 instance 变量。

    但是实际上优化后的执行路径却是这样的:

    分配一块内存 M;
    将 M 的地址赋值给 instance 变量;
    最后在内存 M 上初始化 Singleton 对象。

    优化后会导致什么问题呢?

    我们假设线程 A 先执行 getInstance() 方法,当执行完指令 2 时恰好发生了线程切换,切换到了线程B 上; 如果此时线程 B 也执行 getInstance() 方法,那么线程 B 在执行第一个判断时会发现 instance != null ,所以直接返回 instance。 而此时的 instance 是没有初始化过的,如果我们这个时候访问 instance 的成员变量就可能触发空指针异常。

    在这里插入图片描述

    解决方案1:将Instance声明为volatitle,前面的重排序在多线程环境中将会被禁止

    public class Singleton {
    private static volatile Singleton sInstance;
    public static Singleton getInstance() {
        if (sInstance == null) {
            synchronized (Singleton.class) {
                if (sInstance == null) {
                    sInstance = new Singleton();
                }
            }
       }
       return sInstance;
    }
    private Singleton() {}
    }
    

    解决方案2:静态内部类

    public class Singleton {
        private Singleton(){};
        private static class Inner{
            private static Singleton SINGLETION=new Singleton();
        }
        public static Singleton getInstance(){
            return Inner.SINGLETION;
        }
    }  
    

    静态内部类不会随着外部类的初始化而初始化,他是要单独去加载和初始化的,当第一次执行getInstance方法时,Inner类会被初始化。

    静态对象SINGLETION的初始化在Inner类初始化阶段进行,类初始化阶段即虚拟机执行类构造器()方法的过程。

    虚拟机会保证一个类的()方法在多线程环境下被正确的加锁和同步,如果多个线程同时初始化一个类,只会有一个线程执行这个类的()方法,其它线程都会阻塞等待。

    解决方法3:原子类 AtomicInteger

    详情请见文末java并发包中的原子类

    四.解决原子性,可见性和有序性

    我们已经知道,导致可见性的原因是缓存,导致有序性的原因是编译优化,那解决可见性、有序性最直接的办法就是禁用缓存和编译优化,但是这样问题虽然解决了,我们程序的性能可就堪忧了。

    合理的方案应该是按需禁用缓存以及编译优化。那么,如何做到“按需禁用”呢?对于并发程序,何时禁用缓存以及编译优化只有程序员知道,那所谓“按需禁用”其实就是指按照程序员的要求来禁用。所以,为了解决可见性和有序性问题,只需要提供给程序员按需禁用缓存和编译优化的方法即可。

    Java 内存模型是个很复杂的规范,本质上可以理解为,Java 内存模型规范了 JVM 如何提供按需禁用缓存和编译优化的方法。具体来说,这些方法包括 volatile、synchronized 和 final 三个关键字,以及六项 Happens-Before 规则。

    volatile

    volatile 关键字并不是 Java 语言的特产,古老的 C 语言里也有,它最原始的意义就是禁用 CPU 缓存。当你使用了这个变量,就等于告诉了虚拟机,这个变量极有可能会被某些程序或线程修改。为了确保这个变量被修改后,应用程序范围内的所有线程都能看到这个改动,虚拟机必须得进行一些特殊的手段。

    volatile是轻量级的synchronized,如果使用恰当,它比synchronized的使用和执行成本更低,因为他不会引起上下文切换和调度。

    多线程的内存模型:main memory(主存)、working memory(线程栈),在处理数据时,线程会把值从主存load到本地栈,完成操作后再save回去(volatile关键词的作用:每次针对该变量的操作都激发一次load and save)。

    针对多线程使用的变量如果不是volatile或者final修饰的,很有可能产生不可预知的结果(另一个线程修改了这个值,但是之后在某线程看到的是修改之前的值)。其实道理上讲同一实例的同一属性本身只有一个副本。但是多线程是会缓存值的,本质上,volatile就是不去缓存,直接取值。在线程安全的情况下加volatile会牺牲性能。但相比较synchronized和锁,性能更佳。与普通变量相比,就是写入的操作慢一点,因为会加入许多内存屏障指令。

    内存屏障(memory barrier)是一个CPU指令。基本上,它是这样一条指令:
    a) 确保一些特定操作执行的顺序;
    b) 影响一些数据的可见性(可能是某些指令执行后的结果)。编译器和CPU可以在保证输出结果一样的情况下对指令重排序,使性能得到优化。插入一个内存屏障,相当于告诉CPU和编译器先于这个命令的必须先执行,后于这个命令的必须后执行。内存屏障另一个作用是强制更新一次不同CPU的缓存。例如,一个写屏障会把这个屏障前写入的数据刷新到缓存,这样任何试图读取该数据的线程将得到最新值,而不用考虑到底是被哪个cpu核心或者哪颗CPU执行的。

    内存屏障(memory barrier)和volatile什么关系?上面的虚拟机指令里面有提到,如果你的字段是volatile,Java内存模型将在写操作后插入一个写屏障指令,在读操作前插入一个读屏障指令。这意味着如果你对一个volatile字段进行写操作,你必须知道:1、一旦你完成写入,任何访问这个字段的线程将会得到最新的值。2、在你写入前,会保证所有之前发生的事已经发生,并且任何更新过的数据值也是可见的,因为内存屏障会把之前的写入值都刷新到缓存。

    1.原 子 性

    volatile并不能直接替代锁的作用,他只能保证可见性和有序性,但volatile保证不了原子性操作!!!!!

    修改一个变量值的JVM指令:

    mov    0xc(%r10),%r8d ; Load
    inc    %r8d           ; Increment
    mov    %r8d,0xc(%r10) ; Store
    lock addl $0x0,(%rsp) ; StoreLoad Barrier
    

    从Load到store到内存屏障,一共4步,其中最后一步jvm让这个最新的变量的值在所有线程可见,也就是最后一步让所有的CPU内核都获得了最新的值,但中间的几步(从Load到Store)是不安全的,中间如果其他的CPU修改了值将会丢失。

    最简单的一个例子是调用多次一个线程进行i++操作:

    一个变量i被volatile修饰,两个线程想对这个变量修改,都对其进行自增操作也就是i++,i++的过程可以分为三步,首先获取i的值,其次对i的值进行加1,最后将得到的新值写回到缓存中。
    线程A首先得到了i的初始值100,但是还没来得及修改,就阻塞了,这时线程B开始了,它也得到了i的值,由于i的值未被修改,即使是被volatile修饰,主存的变量还没变化,那么线程B得到的值也是100,之后对其进行加1操作,得到101后,将新值写入到缓存中,再刷入主存中。根据可见性的原则,这个主存的值可以被其他线程可见。
    问题来了,线程A已经读取到了i的值为100,也就是说读取的这个原子操作已经结束了,所以这个可见性来的有点晚,线程A阻塞结束后,继续将100这个值加1,得到101,再将值写到缓存,最后刷入主存,所以即便是volatile具有可见性,也不能保证对它修饰的变量具有原子性。

    除此之外,还有一个很重要的点。在JAVA中,Integer 属于不变对象,也就是说,如果你要修改一个值为1的Integer对象,实际上是新建一个值为2的Interger对象,i=Integer.valueOf(i.intValue()+1),

    2.可见性 & 顺序性

    为了解决volatile所带来的可能的可见性问题,jdk1.5以后添加了Happens-Before 规则,它规定了哪些指令不能重排。

    Happens-Before
    1)程序顺序原则:一个线程内保证语义的串行性。
    2)volatile规则:volatile变量的写先于读发生,这保证了它的可见性 。
    3)传递性:A先于B,B先于C,那么A必然先于C。
    4)管程中锁规则:解锁必须在加锁前。
    5)线程的start()方法先于它的每一个动作。
    6)线程的所有操作先于线程的终结(Thread.join())。
    7)线程的中断先于被中断线程的代码。
    8)对象的构造函数的执行、结束先于finalize()方法。

    1)程序顺序原则

    符合单线程里面的思维:程序前面对某个变量的修改一定是对后续操作可见的

    2 & 3)volatile 变量规则+传递性
    举例:
    在这里插入图片描述
    如果线程 B 读到了“v=true”,那么线程 A 设置的“x=42”对线程 B 是可见的。也就是说,线程 B 能读到 x = 42 。

    4)管程中锁的规则

    管程:是一种通用的同步原语,在 Java 中指的就是 synchronized,synchronized 是 Java 里对管程的实现。synchronized 关键字及 wait()、notify()、notifyAll() 这三个方法都是管程的组成部分。

    举例

    在多线程环境下,synchronized块中的方法获取了lock实例的monitor,如果实例相同,那么只有一个线程能执行该块内容

    public class Thread1 implements Runnable {
       Object lock;
       public void run() {  
           synchronized(lock){// 此处自动加锁
             ..do something
           }
       }// 此处自动解锁
    }
    

    也可以直接用于方法: 相当于上面代码中用lock来锁定的效果,实际获取的是Thread1类的monitor。更进一步,如果修饰的是static方法,则锁定该类所有实例。

    public class Thread1 implements Runnable {
       public synchronized void run() {  
            ..do something
       }
    }
    

    5)线程 start() 规则

    如果线程 A 调用线程 B 的 start() 方法(即在线程 A 中启动线程 B),那么该 start() 操作 Happens-Before 于线程 B 中的任意操作。

    6)线程 join() 规则

    如果在线程 A 中,调用线程 B 的 join() 并成功返回,那么线程 B 中的任意操作 Happens-Before 于该 join() 操作的返回

    synchronized

    关键字synchronized的作用是实现线程之间的同步,他的工作是对同步的代码枷锁,使得每一次,只能有一个线程进入同步块,从而保证线程之间的安全性。

    Java 编译器会在 synchronized 修饰的方法或代码块前后自动加上加锁 lock() 和解锁 unlock()

    三种使用方法:
    1.指定加锁对象
    2.直接作用于实例方法,锁定的是当前实例对象 this。
    3.直接作用于静态方法,锁定的是当前类的 Class 对象

    class X {
      // 修饰非静态方法
      synchronized void foo() {
        // 临界区
      }
      // 修饰静态方法
      synchronized static void bar() {
        // 临界区
      }
      // 修饰代码块
      Object obj = new Object()void baz() {
        synchronized(obj) {
          // 临界区
        }
      }
    }  
    

    实例方法要求thread指向的接口是同一个,
    而静态方法则不需要。

    五.多线程

    【拓】

    1.为什么要用多线程?

    提升 CPU 和 I/O 设备的利用率。

    2.线程数量最佳为多少?

    对于 CPU 密集型的计算场景,理论上“线程的数量 =CPU 核数”就是最合适的。不过在工程上,线程的数量一般会设置为“CPU 核数
    +1”,这样的话,当线程因为偶尔的内存页失效或其他原因导致阻塞时,这个额外的线程可以顶上,从而保证 CPU 的利用率。

    对于 I/O 密集型的计算场景,最佳线程数 =CPU 核数 * [ 1 +(I/O 耗时 / CPU 耗时)]

    3.局部变量需要多线程吗?
    不需要。局部变量存放在线程各自的的调用栈里,而每个线程都有自己独立的调用栈,不会共享,所以自然也就没有并发问题。

    1.线程的状态

    打开JAVA的Thread类里的State枚举类,可以看到

    public enum State {
    	NEW,
    	RUNNABLE,
    	BLOCKED,
    	WAITING,
    	TIMED_WAITING,
    	TERMINATED;
    }
    

    在这里插入图片描述
    1)Runnable to Blocked

    只有一种场景会触发这种转换,就是线程等待 synchronized 的隐式锁。synchronized 修饰的方法、代码块同一时刻只允许一个线程执行,其他线程只能等待,这种情况下,等待的线程就会从 RUNNABLE 转换到 BLOCKED 状态。而当等待的线程获得 synchronized 隐式锁时,就又会从 BLOCKED 转换到 RUNNABLE 状态。

    2)Runnable to Waiting

    1.获得 synchronized 隐式锁的线程,调用无参数的 Object.wait() 方法。

    2.调用无参数的 Thread.join() 方法。其中的 join() 是一种线程同步方法,例如有一个线程对象 thread A,当调用 A.join() 的时候,执行这条语句的线程会等待 thread A 执行完,而等待中的这个线程,其状态会从 RUNNABLE 转换到 WAITING。当线程 thread A 执行完,原来等待它的线程又会从 WAITING 状态转换到 RUNNABLE。

    3.调用 LockSupport.park() 方法。其中的 LockSupport 对象,Java 并发包中的锁,都是基于它实现的。调用 LockSupport.park() 方法,当前线程会阻塞,线程的状态会从 RUNNABLE 转换到 WAITING。调用 LockSupport.unpark(Thread thread) 可唤醒目标线程,目标线程的状态又会从 WAITING 状态转换到 RUNNABLE。

    3)Runnable to TIMED_WAITING
    WAITING和TIMED_WAITING都是等待状态,TIMED_WAITING 和 WAITING 状态的区别,仅仅是触发条件多了超时参数。.

    4)New to Runnable
    重写run或者实现Runnable接口或者继承Thread

    5)Runnable to Terminated
    线程执行完 run() 方法后,会自动转换到 TERMINATED 状态,当然如果执行 run() 方法的时候异常抛出,也会导致线程终止。有时候我们需要强制中断 run() 方法的执行,可以调用 interrupt() 方法。

    2.线程的基本操作(JAVA)

    1)新建一个线程
    Thread t1 = new Thread(){
                @Override
                public void run() {
                    ..do something
                }
            };
    t1.start();
    

    一般的类要实现线程,可以继承Thread类,当然也可以使用Runnable接口。最常使用的还是用正则表达式重写run函数。
    构造方法:public Thread(Runnable targert)

    2)终止线程

    不建议用已经被废弃的stop() ,因为它会自动释放被终止对象的锁。

    推荐使用的是用一个volatile修饰的布尔型变量来决定是否退出。

    volatile boolean stopme =false;
    public void stopMe(){
    	stopme = true;
    }
    ...
    while(true){
    	if(stopme){
    		break;
    	}
    	. . do something
    }
    
    3)线程中断

    三个方法

    1public void Thread.interrupt()
    	通知目标线程中断,也就是设置中断标志位。
    2public boolean Thread.isInterrupted()
    	判断当前线程是否被中断,也就是检查中断标志位
    3public static boolean Thread.interrupted()
    	判断是否被中断,并清除当前中断标志位
    

    Thread.sleep()方法会让当前线程休眠若干时间,它会抛出InterruptedException中断异常。此时,它会清除中断标记。所以我们应该在异常处理中再次将其中断

    try{
    	Thread.sleep(2000);
    } catch (InterruptedException e) {
    	System.ot,println("xxx");
    	Thread.currentThread().interrupt();
    	}
    	
    
    4)等待和通知

    wait()和notify()是Object类的方法。
    在一个实例对象上,在一个synchronzied语句中,调用wait()方法后,当前线程就会在这个对象上等待,并释放锁。直到有其他线程执行了notify()/notifyAll()。使用notify()/notifyAll()后,会唤醒处于等待状态的线程,是他们的状态变为Runnable。
    wait()会释放锁而sleep()不会。

    挂起(suspend)和继续执行(resume)已被废弃。

    5)等待线程结束和谦让

    join()是等待方法,该方法将一直等待到它调用的线程终止。

    Join方法实现是通过wait()在当前线程对象实例上。 当main线程调用t.join()时候,main线程会获得线程对象t的锁(wait 意味着拿到该对象的锁),调用该对象的wait(等待时间),直到该对象唤醒main线程 ,比如退出后。这就意味着main线程调用t.join时,必须能够拿到线程t对象的锁。

    用途:在很多情况下,主线程生成并起动了子线程,如果子线程里要进行大量的耗时的运算,主线程往往将于子线程之前结束,但是如果主线程处理完其他的事务后,需要用到子线程的处理结果,也就是主线程需要等待子线程执行完成之后再结束,这个时候就要用到join()方法了。(个人理解就是wait() + notify())

    不要在应用程序中,在Thread对象实例上使用类似wait()方法或者notify()方法等,可能会和API互相影响。

    yield()是谦让方法,它会让当前线程让出CPU,但线程还是会进行CPU资源的争夺。如果你觉得一个线程不是非常重要,又害怕占用过多资源,可以使用它来给其他线程更多的工作机会。

    6)线程组

    如果线程数量很多,而且功能分配明确,可以将相同功能的线程放置在同一个线程组里。
    activeCount()返回活动线程总数(不精确的)
    list()返回线程组中所有线程的信息。

    public class Test implements Runnable{
        public static void main(String[] args) {
            ThreadGroup tg = new ThreadGroup("GroupName");
            Thread t1 = new Thread(tg,new Test(),"ThreadName1");
            Thread t2 = new Thread(tg,new Test(),"ThreadName2");
            t1.start();
            t2.start();
            System.out.println(tg.activeCount());
            tg.list();
        }
    
        @Override
        public void run() {
            String groupAndName = Thread.currentThread().getThreadGroup().getName()+" - "+Thread.currentThread().getName();
            while(true){
                System.out.println("I am "+groupAndName);
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    

    7.守护线程

    守护线程是系统的守护者,他会在后台完成一些系统性的服务。如果应用内只有守护线程,那么JAVA虚拟机就会退出。

    t.setDaemon(true);
    t.start();
    

    设置守护线程必须得在start之前,不然该线程会被当作用户线程,永远无法停止。

    8.线程优先级

    内置三个优先级,数字越大优先级越高。【1,10】
    高优先级的线程 倾向于 更快地完成。

    至于问什么是倾向而不是一定,是因为JAVA线程的实现是采用1:1线程模型,也就是每个轻量级进程都有一个操作系统内核的支持,但问题是 不是所有的操作系统都有10个优先级,比如说windows中只有七个,那么当然就无法满足严格的优先级顺序。
    除此之外,windows还有优先级推进器,就是一个线程被切换频繁时,系统可能会越过优先级去为它分配执行时间,从而减少线程频繁切换带来的损耗。总而言之,不能太过依赖于优先级。

    public final static int MIN_PRIORITY = 1;
    public final static int NORM_PRIORITY = 5;
    public final static int MAX_PRIORITY = 10;
    

    并发包学习链接

    展开全文
  • 快速掌握用python写并行程序

    千次阅读 2018-11-04 11:31:44
    这就要说下我前几天做的一个作业了,当时我用python写了个程序,结果运行了一天,这个速度可让我愁了,我还怎么优化,怎么交作业啊。于是小子就去各大论坛寻丹问药了,终于让我发现可以用并行计算来最大化压榨电脑的...

    小子今天想来谈谈“并行计算”,作为一个非科班人员,我为什么去捣鼓这么一个在科班里也比较专业的问题了。这就要说下我前几天做的一个作业了,当时我用python写了个程序,结果运行了一天,这个速度可让我愁了,我还怎么优化,怎么交作业啊。于是小子就去各大论坛寻丹问药了,终于让我发现可以用并行计算来最大化压榨电脑的CPU,提升计算效率,而且python里有multiprocessing这个库可以提供并行计算接口,于是小子花1天时间改进程序,终于在规定时间内做出了自己满意的结果,上交了作业。之后,小子对并行计算充满了兴趣,于是又重新在Google上游历了一番,大致弄清了GPU、CPU、进程、线程、并行计算、分布式计算等概念,也把python的multiprocessing耍了一遍,现在小子也算略有心得了,所以来此立碑,以示后来游客。
    小子本文分为四部分,一是大数据时代现状,其二是面对挑战的方法,然后是用python写并行程序,最后是multiprocessing实战。

    一、大数据时代的现状

    当前我们正处于大数据时代,每天我们会通过手机、电脑等设备不断的将自己的数据传到互联网上。据统计,YouTube上每分钟就会增加500多小时的视频,面对如此海量的数据,如何高效的存储与处理它们就成了当前最大的挑战。
    但在这个对硬件要求越来越高的时代,CPU却似乎并不这么给力了。自2013年以来,处理器频率的增长速度逐渐放缓了,目前CPU的频率主要分布在3~4GHz。这个也是可以理解的,毕竟摩尔定律都生效了50年了,如果它老人家还如此给力,那我们以后就只要静等处理器频率提升,什么计算问题在未来那都不是话下了。实际上CPU与频率是于能耗密切相关的,我们之前可以通过加电压来提升频率,但当能耗太大,散热问题就无法解决了,所以频率就逐渐稳定下来了,而Intel与AMD等大制造商也将目标转向了多核芯片,目前普通桌面PC也达到了4~8核。

    二、面对挑战的方法

    咱们有了多核CPU,以及大量计算设备,那我们怎么来用它们应对大数据时代的挑战了。那就要提到下面的方法了。

    2.1 并行计算

    并行(parallelism)是指程序运行时的状态,如果在同时刻有多个“工作单位”运行,则所运行的程序处于并行状态。图一是并行程序的示例,开始并行后,程序从主线程分出许多小的线程并同步执行,此时每个线程在各个独立的CPU进行运行,在所有线程都运行完成之后,它们会重新合并为主线程,而运行结果也会进行合并,并交给主线程继续处理。

     

    图一、多线程并行


    图二是一个多线程的任务(沿线为线程时间),但它不是并行任务。这是因为task1与task2总是不在同一时刻执行,这个情况下单核CPU完全可以同时执行task1与task2。方法是在task1不执行的时候立即将CPU资源给task2用,task2空闲的时候CPU给task1用,这样通过时间窗调整任务,即可实现多线程程序,但task1与task2并没有同时执行过,所以不能称为并行。我们可以称它为并发(concurrency)程序,这个程序一定意义上提升了单个CPU的使用率,所以效率也相对较高。

     

    图二、多线程并发


    并行编程模型:

     

    • 数据并行(Data Parallel)模型:将相同的操作同时作用于不同数据,只需要简单地指明执行什么并行操作以及并行操作对象。该模型反映在图一中即是,并行同时在主线程中拿取数据进行处理,并线程执行相同的操作,然后计算完成后合并结果。各个并行线程在执行时互不干扰。
    • 消息传递(Message Passing)模型:各个并行执行部分之间传递消息,相互通讯。消息传递模型的并行线程在执行时会传递数据,可能一个线程运行到一半的时候,它所占用的数据或处理结果就要交给另一个线程处理,这样,在设计并行程序时会给我们带来一定麻烦。该模型一般是分布式内存并行计算机所采用方法,但是也可以适用于共享式内存的并行计算机。

    什么时候用并行计算:

    1. 多核CPU——计算密集型任务。尽量使用并行计算,可以提高任务执行效率。计算密集型任务会持续地将CPU占满,此时有越多CPU来分担任务,计算速度就会越快,这种情况才是并行程序的用武之地。
    2. 单核CPU——计算密集型任务。此时的任务已经把CPU资源100%消耗了,就没必要使用并行计算,毕竟硬件障碍摆在那里。
    3. 单核CPU——I/O密集型任务。I/O密集型任务在任务执行时需要经常调用磁盘、屏幕、键盘等外设,由于调用外设时CPU会空闲,所以CPU的利用率并不高,此时使用多线程程序,只是便于人机交互。计算效率提升不大。
    4. 多核CPU——I/O密集型任务。同单核CPU——I/O密集型任务。

    2.2 改用GPU处理计算密集型程序

    GPU即图形处理器核心(Graphics Processing Unit),它是显卡的心脏,显卡上还有显存,GPU与显存类似与CPU与内存。
    GPU与CPU有不同的设计目标,CPU需要处理所有的计算指令,所以它的单元设计得相当复杂;而GPU主要为了图形“渲染”而设计,渲染即进行数据的列处理,所以GPU天生就会为了更快速地执行复杂算术运算和几何运算的。
    GPU相比与CPU有如下优势:

    1. 强大的浮点数计算速度。
    2. 大量的计算核心,可以进行大型并行计算。一个普通的GPU也有数千个计算核心。
    3. 强大的数据吞吐量,GPU的吞吐量是CPU的数十倍,这意味着GPU有适合的处理大数据。

    GPU目前在处理深度学习上用得十分多,英伟达(NVIDIA)目前也花大精力去开发适合深度学习的GPU。现在上百层的神经网络已经很常见了,面对如此庞大的计算量,CPU可能需要运算几天,而GPU却可以在几小时内算完,这个差距已经足够别人比我们多打几个比赛,多发几篇论文了。

    3.3 分布式计算

    说到分布式计算,我们就先说下下Google的3篇论文,原文可以直接点链接去下载:

    Google在2003~2006年发表了这三篇论文之后,一时之间引起了轰动,但是Google并没有将MapReduce开源。在这种情况下Hadoop就出现了,Doug Cutting在Google的3篇论文的理论基础上开发了Hadoop,此后Hadoop不断走向成熟,目前Facebook、IBM、ImageShack等知名公司都在使用Hadoop运行他们的程序。

    分布式计算的优势:
    可以集成诸多低配的计算机(成千上万台)进行高并发的储存与计算,从而达到与超级计算机媲美的处理能力。

    三、用python写并行程序

    在介绍如何使用python写并行程序之前,我们需要先补充几个概念,分别是进程、线程与全局解释器锁(Global Interpreter Lock, GIL)。

    3.1 进程与线程

    进程(process):

    • 在面向线程设计的系统(如当代多数操作系统、Linux 2.6及更新的版本)中,进程本身不是基本运行单位,而是线程的容器。
    • 进程拥有自己独立的内存空间,所属线程可以访问进程的空间。
    • 程序本身只是指令、数据及其组织形式的描述,进程才是程序的真正运行实例。 例如,Visual Studio开发环境就是利用一个进程编辑源文件,并利用另一个进程完成编译工作的应用程序。

    线程(threading):

    • 线程有自己的一组CPU指令、寄存器与私有数据区,线程的数据可以与同一进程的线程共享。
    • 当前的操作系统是面向线程的,即以线程为基本运行单位,并按线程分配CPU。

    进程与线程有两个主要的不同点,其一是进程包含线程,线程使用进程的内存空间,当然线程也有自己的私有空间,但容量小;其二是进程有各自独立的内存空间,互不干扰,而线程是共享内存空间。
    图三展示了进程、线程与CPU之间的关系。在图三中,进程一与进程二都含有3个线程,CPU会按照线程来分配任务,如图中4个CPU同时执行前4个线程,后两个标红线程处于等待状态,在CPU运行完当前线程时,等待的线程会被唤醒并进入CPU执行。通常,进程含有的线程数越多,则它占用CPU的时间会越长。

     

    图三、进程、线程与CPU关系

     

    3.2 全局解释器锁GIL:

    GIL是计算机程序设计语言解释器用于同步线程的一种机制,它使得任何时刻仅有一个线程在执行。即便在多核心处理器上,使用 GIL 的解释器也只允许同一时间执行一个线程。Python的Cpython解释器(普遍使用的解释器)使用GIL,在一个Python解释器进程内可以执行多线程程序,但每次一个线程执行时就会获得全局解释器锁,使得别的线程只能等待,由于GIL几乎释放的同时就会被原线程马上获得,那些等待线程可能刚唤醒,所以经常造成线程不平衡享受CPU资源,此时多线程的效率比单线程还要低下。在python的官方文档里,它是这样解释GIL的:

    In CPython, the global interpreter lock, or GIL, is a mutex that prevents multiple native threads from executing Python bytecodes at once. This lock is necessary mainly because CPython’s memory management is not thread-safe. (However, since the GIL exists, other features have grown to depend on the guarantees that it enforces.)

    可以说它的初衷是很好的,为了保证线程间的数据安全性;但是随着时代的发展,GIL却成为了python并行计算的最大障碍,但这个时候GIL已经遍布CPython的各个角落,修改它的工作量太大,特别是对这种开源性的语音来说。但幸好GIL只锁了线程,我们可以再新建解释器进程来实现并行,那这就是multiprocessing的工作了。

    3.3 multiprocessing

    multiprocessing是python里的多进程包,通过它,我们可以在python程序里建立多进程来执行任务,从而进行并行计算。官方文档如下所述:

    The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads.
    我们接下来介绍下multiprocessing的各个接口:

    3.3.1 进程process

    multiprocessing.Process(target=None,  args=())
        target: 可以被run()调用的函数,简单来说就是进程中运行的函数
        args: 是target的参数
    
    process的方法:
        start(): 开始启动进程,在创建process之后执行
        join([timeout]):阻塞目前父进程,直到调用join方法的进程执行完或超时(timeout),才继续执行父进程
        terminate():终止进程,不论进程有没有执行完,尽量少用。

    示例1

    from multiprocessing import Process
    
    def f(name):
        print 'hello', name
    
    if __name__ == '__main__':
        p = Process(target=f, args=('bob',)) # p进程执行f函数,参数为'bob',注意后面的“,”
        p.start() # 进程开始
        p.join() # 阻塞主线程,直至p进程执行结束

    3.3.2 进程池Process Pools

    class multiprocessing.Pool([processes])
        processes是进程池中的进程数,默认是本机的cpu数量
    方法:
        apply(func[, args[, kwds]])进程池中的进程进行func函数操作,操作时会阻塞进程,直至生成结果。
        apply_async(func[, args[, kwds[, callback]]])与apply类似,但是不会阻塞进程
        map(func, iterable[, chunksize])进程池中的进程进行映射操作
        map_async(func, iterable[, chunksize[, callback]])
        imap(func, iterable[, chunksize]):返回有序迭代器
        imap_unordered(func, iterable[, chunsize]):返回无序迭代器
        close():禁止进程池再接收任务
        terminate():强行终止进程池,不论是否有任务在执行
        join():在close()或terminate()之后进行,等待进程退出

    示例2

    from multiprocessing import Pool
    
    def f(x):
        return x*x
    
    if __name__ == '__main__':
        p = Pool(5) # 创建有5个进程的进程池
        print(p.map(f, [1, 2, 3])) # 将f函数的操作给进程池

    3.3.3 Pipes & Queues

    multiprocessing.Pipe([duplex])
        返回两个连接对象(conn1, conn2),两个连接对象分别访问pipe的头和尾,进行读写操作
        Duplex: True(default),创建的pipe是双向的,也即两端都可以进行读写;若为False,则pipe是单向的,仅可以在一端读,另一端写,此时与Queue类似。
    
    multiprocessing.Queue([maxsize])
        qsize():返回queuemember数量
        empty():如果queue是空的,则返回true
        full():如果queuemember数量达到maxsize,则返回true
        put(obj):将一个object放入到queueget():从队列中取出一个object并将它从queue中移除,FIFO原则
        close():关闭队列,并将缓存的object写入pipe

    示例

    from multiprocessing import Pool
    import time
    def f(x):
        return x*x
    if __name__ == '__main__':
        pool = Pool(processes=4)              # start 4 worker processes
        result = pool.apply_async(f, (10,))   # evaluate "f(10)" asynchronously in a single process
        print result.get(timeout=1)           # prints "100" unless your computer is *very* slow
        print pool.map(f, range(10))          # prints "[0, 1, 4,..., 81]"
        it = pool.imap(f, range(10))
        print it.next()                       # prints "0"
        print it.next()                       # prints "1"
        print it.next(timeout=1)              # prints "4" unless your computer is *very* slow
        result = pool.apply_async(time.sleep, (10,))
        print result.get(timeout=1)           # raises multiprocessing.TimeoutError

    3.3.4 进程锁multiprocessing.Lock

    当一个进程获得(acquire)锁之后,其它进程在想获得锁就会被禁止,可以保护数据,进行同步处理。
         acquire(block=True, timeout=None):尝试获取一个锁,如果blocktrue,则会在获得锁之后阻止其它进程再获取锁。
         release():释放锁

    3.3.5 共享内存——Value, Array

    共享内存通常需要配合进程锁来处理,保证处理的顺序相同。

    multiprocessing.Value(typecode_or_type, *args[, lock])
        返回一个ctype对象,
        创建c = Value(‘d’, 3.14),调用c.value()
    multiprocessing.Array(typecode_or_type, size_or_initializer, *, lock=True)
        返回一个ctype数组,只能是一维的
        Array(‘i’, [1, 2, 3, 4])
    Type code C Type Python Type Minimum size in bytes
    'b' signed char int 1
    'B' unsigned char int 1
    'u' Py_UNICODE Unicode character 2
    'h' signed short int 2
    'H' unsigned short int 2
    'i' signed int int 2
    'I' unsigned int int 2
    'l' signed long int 4
    'L' unsigned long int 4
    'q' signed long long int 8
    'Q' unsigned long long int 8
    'f' float float 4
    'd' double float 8

    3.3.6 其它方法

    multiprocessing.active_children():返回当前进程的所有子进程
    multiprocessing.cpu_count():返回本计算机的cpu数量
    multiprocessing.current_process():返回当前进程

    3.3.7 注意事项:

    1. 尽量避免共享数据
    2. 所有对象都尽量是可以pickle的
    3. 避免使用terminate强行终止进程,以造成不可预料的后果
    4. 有队列的进程在终止前队列中的数据需要清空,join操作应放到queue清空后
    5. 明确给子进程传递资源、参数

    windows平台另需注意:

    • 注意跨模块全局变量的使用,可能被各个进程修改造成结果不统一
    • 主模块需要加上if name == 'main':来提高它的安全性,如果有交互界面,需要加上freeze_support()

    四、multiprocessing实战

    process、lock与value尝试:

    import multiprocessing as mp
    import time
    
    def job(v, num, l):
        l.acquire() # 锁住
        for _ in range(5):
            time.sleep(0.1) 
            v.value += num # 获取共享内存
            print(v.value)
        l.release() # 释放
    
    
    def multicore():
        l = mp.Lock() # 定义一个进程锁
        #l = 1
        v = mp.Value('i', 0) # 定义共享内存
        p1 = mp.Process(target=job, args=(v,1,l)) # 需要将lock传入
        p2 = mp.Process(target=job, args=(v,3,l)) 
        p1.start()
        p2.start()
        p1.join()
        p2.join()
    
    if __name__=='__main__':
        multicore()

    上述代码即对共享内存叠加5次,p1进程每次叠加1,p2进程每次叠加3,为了避免p1与p2在运行时抢夺共享数据v,在进程执行时锁住了该进程,从而保证了执行的顺序。我测试了三个案例:

    1. 直接运行上述代码输出[1, 2, 3, 4, 5, 8, 11, 14, 17, 20],运行时间为1.037s
    2. 在1的基础上注释掉锁(上述注释了三行),在没有锁的情况下,输出[1, 4, 5, 8, 9, 12, 13, 15, 14, 16],运行时间为0.53s
    3. 在2的基础上将p1.join()调到p2.start()前面,输出为[1, 2, 3, 4, 5, 8, 11, 14, 17, 20],运行时间为1.042s.

    可以发现,没锁的情况下调整join可以取得与加锁类似的结果,这是因为join即是阻塞主进程,直至当前进程结束才回到主进程,若将p1.join()放到p1.start()后面,则会马上阻塞主进程,使得p2要稍后才开始,这与锁的效果一样。
    如果如上述代码所示,p1.join()在p2.start()后面,虽然是p1先join(),但这时只是阻塞了主进程,而p2是兄弟进程,它已经开始了,p1就不能阻止它了,所以这时如果没锁的话p1与p2就是并行了,运行时间就是一半,但因为它们争抢共享变量,所以输出就变得不确定了。

    pool

    import multiprocessing as mp
    #import pdb
    
    def job(i):
        return i*i
    
    def multicore():
        pool = mp.Pool()
        #pdb.set_trace()
        res = pool.map(job, range(10))
        print(res)
        res = pool.apply_async(job, (2,))
        # 用get获得结果
        print(res.get())
        # 迭代器,i=0时apply一次,i=1时apply一次等等
        multi_res = [pool.apply_async(job, (i,)) for i in range(10)]
        # 从迭代器中取出
        print([res.get() for res in multi_res])
    
    multicore()

    pool其实非常好用,特别是map与apply_async。通过pool这个接口,我们只有指定可以并行的函数与函数参数列表,它就可以自动帮我们创建多进程池进行并行计算,真的不要太方便。pool特别适用于数据并行模型,假如是消息传递模型那还是建议自己通过process来创立进程吧。

    总结

    小子这次主要是按自己的理解把并行计算理了下,对进程、线程、CPU之间的关系做了下阐述,并把python的multiprocessing这个包拎了拎,个人感觉这个里面还大有学问,上次我一个师兄用python的process来控制单次迭代的运行时间(运行超时就跳过这次迭代,进入下一次迭代)也是让我涨了见识,后面还要多多学习啊。
    感谢您花费宝贵的时间阅读到这里,希望能有所收获,也欢迎在评论区进行交流。

    推荐好文:
    multiprocessing官方文档
    python多进程的理解 multiprocessing Process join run(推荐好文)
    多进程 Multiprocessing

    展开全文
  • 并行程序设计导论 第三章习题

    千次阅读 2015-04-03 01:11:26
    在问候程序中,如果strlen(greeting)代替strlen(greeting)+1来计算进程1、2、…、comm_sz-1发送消息的长度,会发生什么情况?如果用MAX_STRING代替strlen(greeting)+1又会是什么结果?你可以解释这些结果吗? 解答...
  • MPI并行程序的调试技巧

    千次阅读 2014-05-19 22:06:49
    是的,你没有必要每个process都加,可以只针对有代表的process加上(例如你用到master-slave的架构那么就挑个master跟slave呗~)。 神马?「代表」很难选?! 我们可以把while循环改成: ```c while...
  • 在项目程序已经完成好的情况下不需要大幅度的修改源代码,只需要加上专用的pragma来指明自己的意图,由此编译器可以自动将程序进行并行化,并在必要之处加入同步互斥以及通信。当选择忽略这些pragma,或者编译器不...
  • 所以,有必要加强宣传,翻新大家的认知。 首先,天地倒悬,结论先行:当你需要并行时,优先考虑不需要线程间共享数据的设计,其次考虑共享Immutable的数据,最糟情况是共享Mutable数据。这个最糟选择,意味着最差...
  • 序号分别为350、360、371,随着环境变量中默认线程数的变化,发现对于350程序,线程数设置从1到4时,运算时间逐渐减少,当线程数设置超过4以后,运行总时间稳定在125s左右,这与omp并行程序一般的运行规律存在冲突;...
  • Matlab并行运算

    千次阅读 2014-06-06 17:14:31
    本身写的程序就很容易实现并行化,因为beamline之间并没有考虑相互作用。等于可以拆成n个线程并行,要是有550核的话,估计1ms就算完了。。。 先转下网上找到的资料。 一、Matlab并行计算原理梗概 Matl
  • 关于并行

    千次阅读 2015-07-05 17:13:33
    所谓并行性(parallelism)是指计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。只要在时间上相互重叠,就...从计算机系统中执行程序的角度看,并行等级从低到高分为: 指令内部:一条指令内部各个微操作
  • [并行计算] 1. 并行计算简介

    万次阅读 多人点赞 2017-07-20 15:30:07
    这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的先导。因此,它只涵盖了并行计算的基础知识,实用于刚刚开始熟悉该主题的初学者。
  • java并行

    千次阅读 2019-08-13 15:55:58
    在java7之前,处理并行数据非常麻烦. 第一:你得明确的把包含的数据结构分成若干子部分. 第二:你要给每个子部分分配独立的线程. 第三:你需要在恰当的时候对他们进行同步,来避免不希望出现的竞争条件,等待所有线程完成,...
  • 什么是并行计算?

    千次阅读 2020-01-15 14:26:19
    最近项目需要实现程序并行化,刚好借着翻译这篇帖子的机会,了解和熟悉并行计算的基本概念和程序设计。帖子的原文见这里。 这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的...
  • 并行计算模型

    千次阅读 2019-06-21 17:09:42
    并行计算指的在同一时刻存在...我们有必要了解GPU的并计算模型。 对并行计算模式进行分类是了解CPU和GPU并行计算区别的有效方式。一种分类的方法是按照实现并行的层次分,即底层的并行或是高层的并行。主要可以分...
  • 一,为大规模多核处理器设计应用程序 如果有成百个或上千个并发执行的线程或进程,如何设计或如何管理IPC则是一件非常令人生畏的事情。“应用程序设计” 本身就是一个非常宽泛的术语。对于不同类型和级别的开发人员...
  • 并行计算与MPI

    万次阅读 2019-06-01 16:54:08
    并行计算 1.1. 相关背景 (1)从1986年到2002年,微处理器的性能以平均50%的速度不断提升。但从2002年开始,单处理器的性能提升速度下降到每年大约20%,这个差距是巨大的。所以,从2005年起,大部分主流的CPU制造商...
  • OpenMp 并行加速

    千次阅读 2017-12-27 19:49:09
    OpenMp是由OpenMP Architecture Review Board牵头提出的,并已被广泛接受的,用于共享内存并行系统的多线程程序设计的一套指导注释(Compiler Directive)。OpenMP支持的编程语言包括C语言、C++和Fortran;而支持...
  • 计算机指令级并行

    千次阅读 2012-12-17 22:17:46
    提高桌面级计算机指令级并行度的方法 ... 作者:未知 厚朴教育来源:转载 点击数:525 更新时间:2011-7-24 ... 并行计算从其并行的粒度来看,分为指令级、循环级、过程级、子程序级、作业级;而从并行
  • linux下并行计算

    千次阅读 2013-02-02 14:49:24
    高性能并行计算所处理的问题具有程序规模庞大、编写困难、计算量大、...本文将介绍如何借助Linux来构建并行计算系统,以及如何在Linux平台下开发MPI和PVM并行程序。    并行计算环境 并行计算是提高计算机系统计算
  • 非规则计算中的局部并行性

    千次阅读 2009-04-09 12:28:00
    如计算流体力学、计算分子动力学等是经典的非规则计算,由于其计算依赖关系和访存模式的非规则,使得非规则计算程序通常表现出极少的局部和数据重用、动态非连续存储访问和大量细粒度并行。   Ø   ...
  • matlab 多核并行编程

    万次阅读 2016-02-19 13:59:37
    Parallel Computing Toolbox(并行计算工具箱)中加入了并行循环parfor-loops,对于每一步可以独立于其他步的循环,计算效率可以有较大幅度的提高。以前简单的for循环for-loop是顺序的(sequentially)执行每一步循环...
  • 并行计算基础

    千次阅读 2012-11-16 09:51:02
    并行计算是一门交叉学科,涵盖的内容非常广泛,包括并行机体系结构、编译系统、并行算法、并行编程、并行软件技术、并行性能优化与评价、并行应用等。从交叉学科的角度,并行计算可以定义为连接并行机系统和实际应用...
  • 并发、并行和协程

    千次阅读 2018-05-04 22:23:46
    几乎所有’正式’的程序都是多线程的,以便让用户或计算机不必等待,或者能够同时服务多个请求(如 Web 服务器),或增加性能和吞吐量(例如,通过对不同的数据集并行执行代码)。 并发和...
  • 指令级并行

    千次阅读 2018-07-02 16:49:08
    指令级并行流水线提高的是指令带宽(吞吐率),而不是单条指令的执行速度相关限制了流水线性能的发挥 结构相关:需要更多的硬件资源 数据相关:需要定向,编译器调度 控制相关:尽早检测条件,计算目标地址,延迟...
  • Matlab 使用 GPU 并行计算

    万次阅读 多人点赞 2017-06-17 19:53:05
    在学习使用matlab,看到一篇好... 科学计算 | Matlab 使用 GPU 并行计算 2016-10-31 18:14 | SPACEofPHD Matlab下直接使用GPU并行计算(预告) 小引言 说它小是因为它只是博士论文的
  • 最简单的并行计算——OpenMP的使用

    万次阅读 2018-01-20 00:25:14
    一种应用程序界面(API,即Application Program Interface),是一种单进程多线程并行的实现和方法,也可以认为是共享存储结构上的一种编程模型,可用于共享内存并行系统的多线程程序设计的一套指导注释(Compiler...
  • openMP(并行计算) 超简单快速上手

    千次阅读 2015-12-06 21:29:30
    OpenMp是并已被广泛接受的,用于共享内存并行系统的多处理器程序设计的一套指导的编译处理方案。 OpenMP支持的编程语言包括C语言、C++和Fortran; OpenMp提供了对并行算法的高层的抽象描述,程序员通过在源代码中...
  • CUDA 高性能并行计算入门

    万次阅读 多人点赞 2018-03-09 10:40:08
    CUDA 高性能并行计算入门 (UPDATE IN 2018.3.8) 1.更新pitch索引操作的描述 概述 什么是CUDA? CUDA(Compute Unified Device Architecture)是 NVIDIA公司开发的一种计算架构,可以利用NVIDIA系列显卡对一些...
  • 使用OpenMP并行化常见算法

    千次阅读 2020-02-10 22:22:09
    OpenMP并行化常见算法 openmp是强大的并行编译库,可以动态地设置多线程,使用方便。 这里我将以搜索算法为例,介绍如何用OpenMP把常见算法并行化。 旅行商问题 旅行商问题已经老生常谈了。指在有向带权图内,寻找一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 94,646
精华内容 37,858
热门标签
关键字:

并行程序的必要性