分布式系统与WEB服务(3)

南京理工大学计算机学院分布式系统与WEB服务第五章分布式系统文件共享南京理工大学计算机学院分布式系统与WEB服务5.1共享文件的语义两个以上的用户共享同一个文件时，会产生多种情况，从而产生不同的语义．故文件服务时必须精确定义服务的读写语义。一.UNIX语义(时间顺序)对于单处理机而言，在UNIX系统中，其读操作的语义是，读取的结果是它前面最近一次写操作形成的结果。写操作的语义是，若先后连续有两个写操作，则文件结果决定于后面的写操作。因此，最后形成的语义是严格意义下的时间序操作。南京理工大学计算机学院分布式系统与WEB服务在对分布式文件系统中的文件进行读操作时，能看到以前所有对该文件执行写操作的效果。特别是，客户对于已打开文件的写操作可立即为其它打开此文件的客户所见。客户可共享文件当前位置的指针。这样，一个客户将指针向前推进时将影响所有共享客户的视图。此种语义的特点是易于理解和实现。二.会话语义对于打开文件的写操作可以立即为本地客户所见，远程的客户也同时打开该文件，但却不可见。一旦文件关闭，对此文件所作的修改仅为后面进行的操作所见，该文件已经打开的各副本不表现这些修改.南京理工大学计算机学院分布式系统与WEB服务三.不可改变文件语义一但文件为共享文件，则所有用户均不能再修改它。这里的不可改变有两个含义：一是其名字不可再变；二是其内容不可改变。这样，不可改变的文件的名字代表该文件的固定内容，而不再是信息存储机制。这一语义非常简单，易于实现，但应用起来，很不灵活．四.事务语义用户若要访问一个文件或了组文件，首先要执行一个启动事务的操作,表示下面的操作必须独立执行，然后对文件进行读写操作，当工作完成后，再执行一个结束事务的操作。南京理工大学计算机学院分布式系统与WEB服务其关键特性是,保证事务期间的所有文件操作按序执行，而不受其它用户的干扰，也就是说，在事务内部严格具有UNIX语义、显然，事务语义是一种比较实用的文件语义。事务的完成要求一个客户机与一个或几个服务器进行协作。南京理工大学计算机学院分布式系统与WEB服务5．2原子事务在分布式系统中，原子事物又简称事物，事务实际上就是一组逻辑上连续执行的操作，其具有动态性，有三种状态：①提交事务中的文件数据项的修改永久保存②中止由于同其他事务冲突或硬件故障导致事务中止③临时事务执行中的存在的临时状态南京理工大学计算机学院分布式系统与WEB服务5.2.1事务的特性事务具有以下四个特性,简称ACID特性①原子性(Atomic):即事务的作用要么完整，要么没有。②一致性(Consistent)：事务处理不影响系统中的不变性：意思是，当系统具有某种不变特性需要保持时，在事务执行前后该不变性一定要保持。例如，银行业务系统中有一个关键的不变特性是“金钱不灭”，经过内部任何转帐之后，银行的总钱数是不变的。③孤立性(Isolated)：并发的事务不会相互影响，多个事务处理可并发执行，其结果和各事务处理串行执行结果一样，也叫串行等价性。南京理工大学计算机学院分布式系统与WEB服务三个事务A、B、C被三个独立的进程同时执行,若顺序执行其结果为1、2或3BEGIN_TRANSACTIONABEGIN_TRANSACTIONBBEGIN_TRANSACTIONCX=0;X=0;X=0;X=X+1;X=X+2;X=X+3;END_TRANSACTIONEND_TRANSACTIONEND_TRANSACTION时间调度1x=0;x=x+1;x=0;x=x+2;x=0;x=x+3;合法调度2x=0;x=0;x=x+1;x=x+2;x=0;x=x+3;合法调度3x=0;x=0;x=x+1;x=0;x=x+2;x=x+3;不合法南京理工大学计算机学院分布式系统与WEB服务④持久性(Durable)：如果事务处理成功完成、则结果将永不消失，除非发生硬故障。5.2.2事务需求银行基本业务服务服务过程解释存款(账号，数额)将指定数额的款项存入给定账号取款(账号，数额)从给定账号取出指定数额的款项平衡(账号)返回给定账号的当前平衡总平衡()返回该客户所有账号的总平衡开始事务处理(标号)开始指定标号的事务处理结束事务处理(标号)结束指定标号的事务处理流产事务处理(标号)迫使指定标号的事务处理流产南京理工大学计算机学院分布式系统与WEB服务银行服务的例子开始事务处理(T)；K：取款(A，100)；K：存款(B，100)；K：取款(C，200)；K：存款(B，200)；结束事务处理(T)我们将用T、U、V代表事务处理标号，用K、M、N代表不同的银行分行，用A、B、C代表客户的分行账号，一个客户发出的一系列服务过程调用就可以合并为一次事务处理。南京理工大学计算机学院分布式系统与WEB服务5．3并发控制并发控制的主要目标是满足事务处理的一致性(串行等价性),最早的方法:A.某一时刻只允许执行一个事务B在启动多个事物操作之前先检查是否满足一致性缺点:解决的不好.为弥补不足.提出下面三种方法.南京理工大学计算机学院分布式系统与WEB服务5.3.1加锁当某一事务访问一共享数据项时，由服务器对该数据项加锁，当完成访问时，再由服务器开锁，以便于其它事务访问。在上锁期间，只有锁定该数据项的事务才能对其访问，这样就保证了在某一时刻访问数据进程的唯一性和确定性。一.基本原理一个锁可由三都分组成：①一个二值逻辑变量，用以指示上锁／开锁；②一个类似于信号灯的条件变量；③访问该锁的宿主事务标识符南京理工大学计算机学院分布式系统与WEB服务实现上锁机制时，需要注意锁的粒度。粒度是指被加锁的数据项的大小，粒度越细，则并行度越高，反之，并行度越低。对整个文件加锁是一种极端情况，这时候，事务串行执行。在下面的讨论中，上锁一般施加于文件中的数据项上。锁定机制是分两个阶段进行的。一个事务在工作过程中，可分为“生长”和“消亡”两个阶段。生长阶段需要上锁，消亡阶段需要开锁，这就是两阶段锁定机制。在生长阶段，事务处于临时状态，其临时数据不为其它事务所见。在消亡阶段，临时数据要变成永久数据，为了保持事务的特性，必须在事务关闭的最后，才能开锁。南京理工大学计算机学院分布式系统与WEB服务二、几种加锁方案1．最简单的加锁方法在这种方案中，文件服务器对客户事务访问的每一个数据项加锁，而在事务完成(或中止)时打开所有的锁，当另一事务试图访问已上锁的数据项时，它必须等待到开锁为止。2.读／写锁方案由于简单锁定机制不必要地将所有访问到的数据项锁定，从而降低了事务的并发性。特别是当事务中均是读操作时，便没有必要上锁。南京理工大学计算机学院分布式系统与WEB服务基于这种分析，提出了读／写锁方案，即允许多个事务并发读同一数据项，只允许一个事务写一个数据项。也称为“多读／单写”方法。在这种方法中，对于读操作，还不能放弃上锁，因为不上锁，可能会有其它事务修改它，造成不一致。为此，要采用两种不同的锁，即读锁和写锁对于访问的所有数据项均可上读锁，只对写操作访问的数据项上写锁。上写锁的数据项不能被其它事务所访问，上读锁的数据项只能为其它事务读，但不能写。南京理工大学计算机学院分布式系统与WEB服务上锁和开锁的基本规则如示:1．当客户在事务中访问数据项时，有如下情况：①如果数据项还未上锁，服务器将其锁定，并让客户防问该数据项；②如果数据项已被其它事务上锁，客户必须等待该锁打开：③如果服务器已经锁定了本事务中的一个数据项，客户可以继续防问。④如果事务想要写自己已上有读锁的数据项，应当将读锁改为写锁。2.当事务提交或中止时，服务器打开它为该事务锁定的所有数据项。南京理工大学计算机学院分布式系统与WEB服务3.读写锁的死锁问题以上两种方法都在一定程度上提高了并发性，但与此同时也会带来另一个问题——死锁。所谓死锁就是一组事务中的每个操作都处于上锁且又等待开锁的状态，例如以下两个事务U和T，在时间顺序上依次采取如下动作，结果将导致死锁。T等待事务U释放读锁b，而它本身又对其加读锁引起事务U对其解锁的等待，由此，便导致了互相牵制。解决方法有如下4种南京理工大学计算机学院分布式系统与WEB服务①在事务开始执行前便对其所要访问的数据加锁，这虽能预防死锁，但却降低了资源共享率。②给资源规定一个序号，申请资源时必须按序号单调递增或递减的方向申请，这种方法也降低了并行性。③通过资源申请占有图来检测有无死锁，一旦发现死锁便由服务器中止一个事务来打破循环占有等待，解决死锁。④“时限”控制，是文件系统中较常用的方法，即给每个锁规定一个时间段。在此时段内，该锁是稳定的，若超出此时限后，该锁便变成易损锁，若此时没有别的事务对上锁数据项竞争，则该锁继续保持；否则的话，便打破此锁，与此同时，原上锁事务中止。这种方法也有两个不足，第一是增加了系统开销；第二是“时限”的取值问题南京理工大学计算机学院分布式系统与WEB服务4．意向写锁读／写锁中读锁的存在阻止了其它事务对其进行写操作，在一定程度上降低了并发性。然而事务的执行要经过两个阶段，在临时阶段，写操作实际上只是将改写的内容写到一个临时缓冲区中，并未改写实际的数据项。只有在提交阶段才写回数据项，基于此原理可把读／写锁改成意向写锁和提交锁来提高并发性.南京理工大学计算机学院分布式系统与WEB服务5.3.2乐观的并发控制方法一.问题的提出使用锁机制处理并发控制时存在一些缺陷：①分布式系统中的锁机制是一种额外的开销。例如，在只有读操作的事务中，锁可以保证所读的数据项不被别的事务修改，但这种锁只有在最坏的情况下才有必要。又例如，两个客户进程并发地对n个数据项进行增值运算，若它们同时启动，执行时间量也相同，以互不相关的序列访问数据项，并且各自使用一个事务来访问和增值数据项，则这两个程序试图同时访问同一数据项的机会仅有1／n，也即每n个事务中实际有用的锁只有一次。南京理工大学计算机学院分布式系统与WEB服务②使用锁机制会导致死锁，并且没有令人满意的死锁解决算法。在锁机制中，只有在一个事务终止时才释放它的所有锁，这明显有损于并发性。正是基于以上原因，有人提出另一种算法——乐观的并发控制方法。之所以称其为“乐观”，是基于这样一种假设，两个客户的事务同时访问某一数据的可能性很小,因此两个事务可以执行下去，直至发出C1oseTransaction请求。当产生冲突时，一般要中止一些事务，并由客户重新启动。这样，每个事务便分为以下三个阶段：南京理工大学计算机学院分布式系统与WEB服务1.读阶段：在这一阶段中，每个事务有一个待更新数据的临时版本。读请求可以立即执行，如果有临时版本存在，则要访问最近提交的数据值。而写请求以一种其它事务不可见的形式缓存起来，若有几个并发事务，可能会同时存在同一数据项的几个不同的临时值。另外，针对于每一个事务需要设置两个集合：读集合和写集合，读集合列出事务所读的数据项的集合，而写集合则列出事务创建、修改、删除的数据项集合。2.确认阶段：当服务器收到CloseTransaction请求之后，进入这个阶段，在该阶段中，对该事务进行确认是否可以将该事务的写操作结果永久保存下来。南京理工大学计算机学院分布式系统与WEB服务如果事务确认成功，则进入写阶段(写操作结果记录到相关文件中，事务成功完成，发出commit);否则，要解决冲突，需要中止某些事务。确认阶段是建立在一致性基础上的，即如果事务执行的结果等价于各个事务顺序执行的结果，则该事务视为确认成功。3.写阶段：如果一个事务确认成功，则临时版本记录的所有修改均可以变为永久性修改。只读事务可以在确认通过后立即提交。写事务在临时版本中的数据变为永久数据之后立即提交。南京理工大学计算机学院分布式系统与WEB服务二、事务的确认确认是利用读写冲突规则来保证一组重叠事务(即当前事务还未提交便已开始的事务)的调度符合一致性,当一个事务完成第一阶段工作后,为其指定一个事务号，若该事务确认成功完成,则事务号被保留下来：否则，若事务未被确认，或事务是只读事务，则释放该事务号．确认工作主要基于两个事务操作的冲突来完成的对于两个重叠事务Ti和TJ，必须满足下