汽车销售合同Title

高级操作系统AdvancedOperatingSystem熊焰[e-mail]0551_3600689中国科学技术大学计算机系汽车防盗器陈香兰@2007.3.21分布式系统同步（续）23.3选举算法许多分布式算法需要一个进程充当协调者、发起者、排序者或者其他特定的角色例如：集中式互斥算法中的协调者进程通常，选择哪个进程充当协调者并不重要，重要的是要有进程负责,并且需要所有进程的一致认可。陈香兰@2007.3.21分布式系统同步（续）3最大进程号如果所有进程的地位都相同，没有特性上的区别，就无法选择其中一个为特殊进程；假设每个进程都有一个特殊的号，通常选举算法总是找拥有最大号的进程，将它指定为协调者，不同的选举算法在选举时采用不同的方法。陈香兰@2007.3.21分布式系统同步（续）4选举的目的我们假设每个进程都知道所有其他进程的进程号，但不知道目前哪些进程在工作，哪些进程不在工作；选举算法的目的是在选举开始后，确保在所有进程都同意的基础上选出协调者。陈香兰@2007.3.21分布式系统同步（续）5两个选举算法欺负（Bully）算法环算法陈香兰@2007.3.21分布式系统同步（续）63.3.1欺负（Bully）算法Bully算法由Garcia-Molina在1982年提出当一个进程P发现协调者不再响应请求时，它就发起选举。进程P负责选举如下：1.P向所有进程号比它大的进程发送选举（ELECTION）消息；2.若无人响应，P获胜成为协调者；3.若有进程号比它大的进程响应，响应者接管，P的工作完成。由于总是进程号最大的进程获胜，故该算法命名为欺负算法。陈香兰@2007.3.21分布式系统同步（续）7欺负（Bully）算法在某一时刻，一个进程只能从进程号比它小的进程那里得到一个选举（ELECTION）消息，当它到达时，接收者就发送回OK消息，表明它的存在并接管，然后接收者主持选举（除非它正在主持别的选举）。除了一个进程外即进程号最大的进程，其余进程都会放弃选举，这个进程就是新的协调者，它将选举获胜的消息发送给所有进程，告之自己是新的协调者。若一个进程刚刚崩溃过，但又很快恢复，它主持选举，若它刚好是当前运行进程中号最大的，它就会获得选举的胜利，从而接管协调者的工作。陈香兰@2007.3.21分布式系统同步（续）8欺负（Bully）算法举例一组由0~7号共8个进程组成，开始7号进程是协调者，但是它突然发生了故障，进程4第一个注意到这一点，所以它向所有比它进程号大的进程，即进程5、6、7发送选举消息。陈香兰@2007.3.21分布式系统同步（续）9进程5和6接收消息后发送回OK。进程4接收到第一个应答时就知道自己已经结束了，因为已经有比它进程号大的进程即将接管它的工作成为新的协调者，它就等待着看谁将在选举中获胜。陈香兰@2007.3.21分布式系统同步（续）10进程5和6都主持选举，每个进程仅把消息发送给比自己进程号大的进程陈香兰@2007.3.21分布式系统同步（续）11进程6向进程5发OK消息，进程5收到OK消息后停止选举，而这个时候进程6知道进程7已经死了，所以，它将是获胜者。陈香兰@2007.3.21分布式系统同步（续）12进程6接管，向所有的运行进程发送COORDINATOR协调者消息进程4收到消息，发现进程7已死，进程6是新协调者，进程4就可继续工作。这样，进程7的失效得到了处理陈香兰@2007.3.21分布式系统同步（续）133.3.2环算法环算法（基于没有令牌的环）假设所有的进程是按物理或逻辑环排序的，每个进程都知道谁是它的下邻居。当一个进程发现协调者不再起作用时，它就创建一个包含它自身进程号的选举消息发送给它的下邻居。如果下邻居失效，消息将绕过它到达它的下邻居，或者再下一个，直到找到一个运行进程。每一个发送者都将自己的进程号加入到消息表中。陈香兰@2007.3.21分布式系统同步（续）14最后，消息到达了始发者手中，始发者接收到包括自己进程号的消息后，将消息的类型转化为协调者消息，该消息将再一次绕环运行，向所有的进程通知谁是协调者（在成员表中进程号最大的那个）。当消息循环一周后，被销毁，每个进程都恢复工作。陈香兰@2007.3.21分布式系统同步（续）15举例进程2、5同时发现前任协调者进程7失效，它们各自建立一个选举消息沿环发送。陈香兰@2007.3.21分布式系统同步（续）16最终，两条消息都将沿环运动，进程2和5分别将它们转化成协调者消息，消息中有完全一样的成员，相互顺序也相同，当两条消息再绕环一周后，均被销毁，有多余的消息循环没有坏处，最多是浪费了一点带宽。陈香兰@2007.3.21分布式系统同步（续）173.4原子事务迄今为止我们研究的所有同步技术本质上都是处于底层的，比如信号量。这些技术都需要编程人员涉及互斥、临界区管理、死锁预防、崩溃恢复等问题的细节。而程序员喜欢的是更高层次的抽象，也就是要隐藏这些技术问题，允许编程人员将精力集中在算法和进程如何并行运行上。这样的抽象是存在的，而且被广泛应用在分布式系统中。我们称其为原子事务，或简称事务。术语原子操作也被广泛使用。陈香兰@2007.3.21分布式系统同步（续）183.4.1原子事务简介1、商业模型原子事务的最初模型来源于商业社会。假设D公司需要一批装饰品，他们与潜在的供应商W公司进行联系，希望6月份能交付10万件10厘米的装饰品。W公司提出12月份交付10万件淡紫色装饰品。D公司同意对方开出的价格，但不喜欢紫色，并且希望6月份到货，而且因为自己的客户是国际客户，因此，坚持要10厘米的产品。W公司答复说10月份提供315/16英寸的淡紫色装饰品。经过更进一步的谈判，双方最终同意8月15日交付3959/1024英寸的紫罗兰装饰品。陈香兰@2007.3.21分布式系统同步（续）19到此为止，双方就可以自由中断本次谈判，返回到开始谈判前的状态。然而，一旦公司双方签订了合同，那么不论发生什么事情，他们在法律上都有责任完成该合约。因此，在双方还未签字前，任何一方都可以反悔，就像什么都没有发生一样，但是一旦双方都签了字，他们就不能再反悔，合同就必须被执行。陈香兰@2007.3.21分布式系统同步（续）202、多进程之间的模型分布式系统中多进程之间的模型和商业模型相类似。一个进程宣布它想和其他一个或几个进程开始一个事务，它们可以就不同的选择进行协商、创建、删除对象，执行一段时间的操作。然后发起者宣布它希望其他进程能保证任务完成。如果其他进程都同意，那么就达成了永久的协议。如果有一个或几个进程拒绝（或在同意前崩溃），那么就会返回到事务开始前的状态。这时对象、文件、数据库等方面的副作用都不会发生。这种要么全有要么全无的特性简化了编程人员的工作。陈香兰@2007.3.21分布式系统同步（续）213、磁带系统模型计算机系统中对事务的使用可以回溯到20世纪60年代。在硬盘和在线数据库出现之前，所有的文件都保存在磁带上。假设有一个有自动盘点系统的超级市场，每天关门后，计算机对两盘作为输入的磁带进行处理:第一盘磁带存有当天早晨开门以前的所有库存，第二盘存有当天已销售给客户的产品和交付给供应商的产品。计算机从两盘磁带上读取数据，并生成新的主库存磁带，如图所示：陈香兰@2007.3.21分布式系统同步（续）22这种设计的最大优点（尽管与它生活在一起的人们并没有意识到）在于对任何原因引起的运行错误，所有的磁带都可以倒卷（rewound），其工作可以毫无损失地重新开始。因此，老式的磁带系统具有了原子事务要么全有要么全无的特性。陈香兰@2007.3.21分布式系统同步（续）234、在线更新数据库模型银行在线更新数据库:客户通过带有调制解调器的PC机连接到银行，想将一个账户下的钱取出再存入另一账户。操作通过下面两步执行：1.提取（金额，账户1）2.存入（金额，账户2）如果电话线在第一步之后第二步之前中断，那么第一个账户已被取出而第二个账户却没有存入。钱就消失在了未知的空间中。陈香兰@2007.3.21分布式系统同步（续）24将这两个操作组成一个原子事务可以解决这个问题。要么两个都执行，要么任何一个都不执行。需要解决的关键问题是事务执行失败后能返回到最初状态。我们真正需要的是像使用磁带时那样的对数据库倒卷的方法。这种能力是原子事务必须提供的。陈香兰@2007.3.21分布式系统同步（续）253.4.2事务模型事务的属性和模型：假设1：系统由一些相互独立的进程组成，每个进程都会随机出错。假设2：通信错误已经被底层软件透明地处理尽管通信一般来说是不太可靠的，消息会丢失，但是底层可以采用超时重发协议恢复丢失的消息。陈香兰@2007.3.21分布式系统同步（续）26假设3：稳定存储器存储器有三种分类。第一种是普通的RAM存储器，当电源出错或机器崩溃时会丢失信息。第二种是磁盘存储器，它不受CPU错的影响，但磁头错会导致信息丢失。最后一种是稳定存储器（stablestorage）。它不受其他任何错误的影响。陈香兰@2007.3.21分布式系统同步（续）271、事务原语使用事务编程需要由操作系统提供或者由语言运行系统提供特殊的原语语句，例如：1.BEGIN_TRANSACTION：标记一个事务的开始2.END_TRANSACTION：结束事务并设法提交3.ABORT_TRANSACTION：取消事务；恢复旧值4.READ：从一个文件（或其他对象）读取数据5.WRITE：将数据写入一个文件（或其他对象）陈香兰@2007.3.21分布式系统同步（续）28事物原语取决于事务中正在使用的对象类型。在一个邮件系统中，可能有发送、接收以及转发邮件等原语。而在一个账目系统中可能会有很大的不同，读取和写入是典型的原语应用。在一个事务中，也允许使用普通语句、过程调用等等。陈香兰@2007.3.21分布式系统同步（续）292、事务体BEGIN_TRANSACTION和END_TRANSACTION限定事务的范围。它们之间的操作构成了事务体。事务体中的操作要么全部执行，要么一个也不执行。这些操作也可能是系统调用，库过程，或者是某种语言中用括号括起来的语句，这取决于应用的需要。陈香兰@2007.3.21分布式系统同步（续）30事务举例考虑到合肥火车站买一张从合肥到长沙的座票。由于没有直达火车，只能买联票。合肥阜阳；阜阳武汉；武汉长沙。下面通过3个操作预定了这3条独立的路线的座票。BEGIN_TRANSACTIONreserve合肥-阜阳reserve阜阳-武汉reserve武汉-长沙END_TRANSACTION陈香兰@2007.3.21分布式系统同步（续）31事务举例（cont’d）现在假设前两条路线已经预定成功，但是第三条已经定满了。那么事务就会因此而中止，前两个预定的结果也将被取消——售票系统的数据库恢复到了事务开始前的状态，就像什么也没有发生一样。BEGIN_TRANSACTIONreserve合肥-阜阳reserve阜阳-武汉武汉-长沙已满ABORT_TRANSACTION陈香兰@2007.3.21分布式系统同步（续）323、事务的特性事务有四个重要的特性，它们是：1.原子性（Atomic）：对外部世界来说，事务的发生是不可分割的；2.一致性（Consistent）：事务不会破坏系统的恒定；3.孤立性（Isolated）：并发的事务不会互相干扰；4.持久性（Durable）：一旦一个事务提交，改变就是永远存在的。这几个属性通常按其字母简称为ACID。陈香兰@2007.3.21分布式系统同步（续）331）事务的原子性所有事务具有的第一个特性是原子性。这个特性确保了每个事务要么全部发生，要么全部不发生。如果发生，就是不可分割的瞬间的操作。当一个事务处在处理过程中，其他进程