高级操作系统复习.doc

高级操作系统复习第一章1.什么是分布式系统?分布式系统是若干独立计算机的集合，它们对于用户来说就像单个相关系统。2.分布式系统中透明性的种类、定义。访问透明性：隐藏数据表示形式以及访问方式的不同。位置透明性：隐藏数据所在位置。迁移透明性：隐藏资源是否已移动到另一个位置。重定位透明性：隐藏资源是否在使用中已移动到另一个位置。复制透明性：隐藏资源是否已被复制。并发透明性：隐藏资源是否由若干相互竞争的用户共享。故障透明性：隐藏资源的故障和恢复。持久性透明性：隐藏资源（软件）位于内存里或在磁盘上。3.分布式系统中有哪几种扩展性？扩展技术有哪些？分布式系统有三中扩展性：（1）规模上的扩展：可以方便地把更多的用户和资源加入到系统中去（2）地域上的扩展：用户和资源相隔更远（3）管理上的扩展：跨越多个管理机构扩展技术有三种：（1）隐藏通信等待时间，包括异步通信和减少通信量（2）使用分布技术，比如分割组件，分散到系统中，如DNS和WWW（3）采用复制技术，比如多拷贝4.分布式操作系统、网络操作系统和基于中间件分布式系统之间的区别。项目分布式操作系统网络操作系统基于中间件的分布式系统多处理器系统多计算机系统透明度很高高低高所有的节点使用的操作系统是否相同是是否否操作系统拷贝数目1NNN通信基于的实体共享内存消息文件特定模型资源管理全局，集中管理全局，分布管理各节点自行管理各节点自行管理可扩展性否部分是各系统不同开放性封闭的封闭的开放的开放的5.什么是客户端-服务器模型？客户端-服务器模型分成，服务器端和客户端，服务器端和客户端进行交互完成一定的功能。服务器端是实现某个特定服务的进程，客户端是向服务器请求服务的进程，它向服务器发送一个请求，随后等待服务器的应答。这种客户-服务器的交互也称为请求-应答行为。6.分布式系统中的硬件（1）根据是否共享存储器分为：多处理器系统：共享存储器多计算机系统：不共享存储器 同构的：相同计算机，单一互联网络 异构的：不同计算机，通过不同网络互连（2）根据网络互连体系结构分为：总线型：使用一根主干线连接交换型：各机器之间用独立线路相连第二章1.什么是远程过程调用？远程过程调用的步骤。远程过程调用是指本地程序调用位于其他机器上的进程，调用方通过消息的形式把参数传递到被调用方的进程，然后等待被调用方执行完后用消息的方式把结果传回调用方。具体步骤是：（1）客户过程以正常的方式调用客户存根（2）客户存根生成一个消息，然后调用本地操作系统（3）客户端操作系统将消息发送给远程操作系统（4）远程操作系统将消息交给服务器存根（5）服务器存根将参数提取出来，然后调用服务器（6）服务器执行要求的操作，操作完成后将结果返回给服务器存根（7）服务器存根将结果打包成一个消息，然后调用本地操作系统（8）服务器操作系统将含有结果的消息发送回客户端操作系统（9）客户端操作系统将消息交给客户存根（10）客户存根将结果从消息中提取出来，返回给调用它的客户过程2.什么是远程对象调用？远程对象调用指的是在本地调用位于其他机器上的对象，和远程过程调用主要的区别在于方法被调用的方式。在远程对象调用中，远程接口使每个远程方法都具有方法签名。如果一个方法在服务器上执行，但是没有相匹配的签名被添加到这个远程接口上，那么这个新方法就不能被远程对象调用的客户方所调用。在远程过程调用中，当一个请求到达远程过程调用的服务器时，这个请求就包含了一个参数集和一个文本值。 3.消息持久通信与暂时通信的区别？消息持久通信指的是，需要传输的消息在提交之后由通信系统来储存，直到将其交付给接受者为止，在将消息成功交付给下一个服务器之前消息一直储存在通信服务器上，因此发送消息的程序不必在发送消息后保持运行，同样要接受消息的应用程序在消息提交的时候可以不处于运行状态。消息暂时通信指的是通信系统只是在发送和接收消息的应用程序运行期间存储消息，否则消息就会被丢弃。4.消息同步通信与异步通信的区别？异步通信特征在于发送者要把传输的消息提交之后立即执行其他的程序，这意味着该消息存储在位于发送端主机的本地缓冲区里中，或者存储在送达的第一个通信服务器上的缓冲区上中。而对于同步通信来说，发送者在提交信息之后会被阻塞直到消息已经到达并储存在接收主机的本地缓冲区中以后也就是消息确实已经传到接收者之后，才会继续执行其他程序。5.给出示意图，能够判断消息通信的类型。a)持久异步通信 b)持久同步通信c)暂时异步通信 d)基于接收的暂时同步通信e)基于交付的暂时同步通信 f)基于响应的暂时同步通信第三章1.进程和线程的比较。进程定义为执行中的程序。未引入线程前是资源分配单位（存储器、文件）和CPU调度（分配）单位。线程是CPU调度单位，拥有线程状态、寄存器上下文和栈这些资源，也有就绪、阻塞和执行三种基本状态。（1）对于地址空间和其他资源（如打开文件）来说，进程间是相互独立的，同一进程的各线程间共享该进程地址空间和其他资源某进程内的线程在其他进程不可见。（2）在通信上，进程间通信通过IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信需要进程同步和互斥手段的辅助，以保证数据的一致性。（3）在调度上，线程上下文切换比进程上下文切换要快得多。线程是CPU调度单位，而进程只作为其他资源分配单位。线程的创建时间比进程短；线程的终止时间比进程短；同进程内的线程切换时间比进程短；因此，多线程能提高性能，线程不像进程那样彼此隔离，并受到系统自动提供的保护，因此多线程应用程序开发需要付出更多努力2.多线程服务器的优点？多线程技术不仅能够显著简化服务器代码，还能够使得应用并行技术来开发高性能的服务器变得更加容易，即使在单处理器系统上也是如此。多线程能够保留顺序处理的思路，使用阻塞性系统的系统调用，仍然能到达并行处理的目的，提高了系统的性能。3.代码迁移的动机有哪些？代码迁移指的是将程序（或执行中的程序）传递到其它计算机。迁移动机：（1）实现负载均衡：将进程从负载重的系统迁移到负载轻的系统，从而改善整体性能。（2）改善通信性能：交互密集的进程可迁移到同一个节点执行以减少通信开销，当进程要处理的数据量较大时，最好将进程迁移到数据所在的节点。（3）可用性：需长期运行的进程可能因为当前运行机器要关闭而需要迁移（4）使用特殊功能：可以充分利用特定节点上独有的硬件或软件功能（5）灵活性：客户首先获取必需的软件，然后调用服务器4.进程对资源的绑定类型有哪些？5.资源对机器的绑定类型有哪些？掌握迁移代码时，根据引用本地资源方式不同应采取的做法。进程对资源的绑定类型有三类，分别是按标志符（URL）、按值和按类型。资源对机器绑定类型分成：未连接（数据文件）、附着连接（数据库）和紧固连接（本地设备）三类。6.处理机分配的超载者启动的分布式启发式算法思想。算法描述：当一个进程创建时，若创建该进程的机器发现自己超载，就将询问消息发送给一个随机选择的机器，询问该机器的负载是否低于一个阀值。1）如果是，那么该进程就被传送到该机器上去运行。2）否则，就再随机地选择一台机器进行询问。这个过程最多执行N次，若仍然找不到一台合适的机器，那么算法将终止，新创建的进程就在创建它的机器上运行。算法分析：当整个系统负载很重的时候，每一个机器都不断地向其他机器发送询问消息以便找到一台机器愿意接收外来的工作。在这种情况下，所有机器的负载都很重，没有一台机器能够接收其它机器的工作，所以，大量的询问消息不仅毫无意义，而且还给系统增添了巨大的额外开销。7.处理机分配的欠载者启动的分布式启发式算法思想。算法描述：在这个算法中，当一个进程结束时，系统就检查自己是否欠载。如果是，它就随机地向一台机器发送询问消息。如果被询问的机器也欠载，则再随机地向第二台、第三台机器发送询问消息。如果连续N个询问之后仍然没有找到超载的机器，就暂时停止询问的发送，开始处理本地进程就绪队列中的一个等待进程，处理完毕后，再开始新一轮的询问。如果既没有本地工作也没有外来的工作，这台机器就进入空闲状态。在一定的时间间隔以后，它又开始随机地询问远程机器。算法分析：在欠载者启动的分布式启发式算法中，当系统繁忙时，一台机器欠载的可能性很小。即使有机器欠载，它也能很快地找到外来的工作。在系统几乎无事可做时，算法会让每一台空闲机器都不间断地发送询问消息去寻找其它超载机器上的工作，造成大量的系统额外开销。但是，在系统欠载时产生大量额外开销要比在系统过载时产生大量额外开销好得多。8.什么软件代理？举例说明其作用。软件代理是一些独立的单元，能与其他的代理进行协作，一同执行任务。定义为对环境的变化做出反应，并且启动这种变化的自治进程，而且可以与用户代理或其他代理协同。与进程的区别在于能够对自己执行操作，在适当的时候采取主动。代理分类：合作代理：通过协作达到某个共同的目标：会议安排移动代理：能够在不同机器间迁移接口代理：协助最终用户使用应用程序，拥有学习能力：促成买卖信息代理：管理来自多个信息源的信息：排序、过滤和比较固定信息代理：电子邮件代理移动信息代理：网络漫游，搜集所需信息第四章1.DNS 名称解析的方法有哪两种？各自优缺点？(1)迭代名称解析：每个服务器只能解析自己下面的路径服务器，把服务器的地址给解析程序，然后解析程序继续访问下一个服务器一直到实体。优点：名称服务器而外负担小缺点：通信开销大(2) 递归名称解析：在每一台服务器都使用递归解析。优点：缓存效果更有效；减少通信开销缺点：要求名称服务器有较高性能2.移动实体的定位的方法有哪些?简单方法有：(1)广播和多播(2)转发指针高级方法有：(1)基于起始位置的方法(2)分层方法3.描述分层方法中查找一实体的过程。（1）希望定位实体E的客户向它所在的叶域D的目录节点发送了一个查找请求（2）如果叶域D的目录节点中没有存储该实体的位置记录，那么就说明该实体现在不在D中。因此这个节点会把请求转发给它的父节点。（3）如果父节点也没有E的位置记录，那么就会把查找请求转发给更高一层的域，依次类推（4）如果节点M存储了E的位置记录，那么一旦请求到达M后，就可以知道E位于节点M代表的域中，M存储了一条位置记录，其中包含了一个指向其子域的指针（5）然后M就把请求转发给那个子域的目录节点，那个子域会依次向树的下方转发请求，直到请求最终到达叶节点为止。存储在叶节点的位置记录会包含E在哪一个叶域中的地址。（6）将该地址返回给发送请求的客户。4.描述分层方法中插入一实体的过程。（1）实体E在叶域D中创建了一个复制实体，需要在这个复制实体中插入E的地址。插入操作从D的叶节点开始，然后D会立即把插入请求转发给它的父节点。（2）父节点也转发插入请求，直到插入请求到达已经为E存储了位置记录的目录节点M为止。（3）节点M在E的位置记录中存储了一个指针，这个指针指向转发插入请求的那个子节点，该子节点会建立一条关于E的位置记录，这条位置记录中包含一个指针，该指针指向转发请求的下一层节点。这个过程会连续进行，直到到达发起请求的叶节点为止（4）最后，那个叶节点会建立一条记录，这条记录包含实体在关联叶域中的位置。5.掌握删除无引用实体的方法。（1）引用计数方法：包括简单引用计数和高级引用计数方法在通信不可靠的情况下维护正确的引用计数所存在的问题a)向其他进程复制引用计数之后再递增引用计数 b) 解决方法a)加权引用计数中权数的初始值 b)创建新引用时的权数值在引用的部分权数达到1时创建一个间接权数 在世代引用计数中创建和复制引用（2）引用列表方法：在骨架端维护一张明确的列表，持续跟踪引用他的代理。优点：不需要可靠通信；进程发生故障时，容易保持引用列表的一致性缺点：引用列表的规模问题-分发租用第五章1.Lamport 时间戳算法的思想？(1)网络上的每个系统（站点）维护一个计数器，起时钟的作用(2)每个站点有一个数字型标识,消息的格式为（m,Ti,i）,m为消息内容， Ti为时间戳， i为站点标识(3)当系统发送消息时，将时钟加一(4)当系统j接收消息时，将它的时钟设为当前值和到达的时间戳这两者的最大者加一(5)在每个站点，时间的排序遵循以下规则:对来自站点i的消息x和站点j的消息y,如果 Ti<Tj或 Ti=Tj，且i<j 则说消息x早于消息y2.什么是(一致的)全局状态？全局状态：定义了每个进程的本地状态和正在传输中的消息.可以用“切口”的图示表示（下）一致的全局状态：如果已经记录了一个进程P收到了来自进程Q的一条消息，那么也应该记录Q确实已经发送了那条消息。（a） 一致的切口 （b）不一致的切口分布式快照算法：分布式快照反映了该系统可能处于的状态，它的基本思想是，每个进程记录它的状态，对每个进入通道来记录发送给它的消息。对每个通道，进程记录在它自己记录下状态后和在发送方记录下它自己状态之前到达的任何消息。3.选举算法中Bully 算法和环算法的思想？选择一个进程作为协调者、发起者或其他特殊角色，一般选择进程号最大的进程（假设每个进程都知道其他进程的进程号，但不知道是否还在运行）它的目的是保证在选举之行后，所有进程都认可被选举的进程。Bully算法：当进程P注意到需要选举一个进程作协调者时：(1)向所有进程号比它高的进程发ELECTION消息(2)如果得不到任何进程的响应，进程P获胜，成为协调者(3)如果有进程号比它高的进程响应，该进程接管选举过程，进程P任务完成(4)当其他进程都放弃，只剩一个进程时，该进程成为协调者(5)一个以前被中止的进程恢复后也有选举权进程 4 启动选举进程 5 和进程 6 响应，接管选举，成为协调者进程 6 响应进程 5 的消息，接管选举，进程 6 成为协调者，通知所有进程4.选举算法中环算法的思想？不使用令牌，按进程号排序，每个进程都知道自己的后继者，当进程P注意到需要选举一个进程作协调者时：(1)创建一条包含该进程号的ELECTION消息，发给后继进程(2)后继进程再将自己的进程号加入ELECTION消息，依次类推(3)最后回到进程P，它再发送一条COORDINATOR消息到环上，包含新选出的协调者进程（进程号最大者）和所有在线进程，这消息在循环一周后被删除，随后每个进程都恢复原来的工作。5.掌握分布式互斥的三种算法及其区别？A.集中式算法：如果一个进程要进入临界区，它要向协调者发送一个请求信息，说明它想要进入哪个临界区并请求允许：（1） 如果当前没有其它进程在该临界区，协调者就发送允许进入的应答消息。收到应答后，该请求进程即进入临界区。（2） 若当前有进程在该临界区，协调者不能同意该请求，拒绝进入的方法依系统而定（可以不发送应答或发一个“拒绝请求”的应答）。B,分布式算法：（1）当进程想进入临界区时，它向所有其他进程发一条打了时间戳的消息Request（2）当收到所有其他进程的Reply消息时，就可以进入临界区了（3）当一个进程收到一条Request消息时，必须返回一条Reply消息： 如该进程自己不想进入临界区，则立即发送Reply消息 如该进程想进入临界区，则把自己的Request消息时间戳与收到的Request消息时间戳相比较， 如自己的晚，则立即发送Reply消息 否则，就推迟发送Reply消息a) 进程 0 和 2 都想进入临界区b) 进程 0 的时间戳低，抢先进入临界区c) 进程 0 退出临界区后，发应答给进程2，进程2 随后进入临界区C,令牌环算法：（1）构造进程逻辑环,环中为每个进程分配了一个位置（2）令牌在环上顺序循环传播（3）获得令牌的当前进程 若想进入临界区，则进入；退出时将令牌向后传；不允许使用同一令牌进入另一临界区 若不想进入临界区，则直接将令牌向后传；（4）令牌丢失时产生新令牌（5）某进程崩溃时，绕过该进程三种互斥算法的比较算法每次进/出临界区所需消息次数进入前的延迟 (消息次数)问 题集中式32协调者崩溃分布式2 ( n 1 )2 ( n 1 )任一进程崩溃令牌环1 to ¥0 to n 1 丢失令牌，进程崩溃6.掌握实现事务的两种方法。（1）私有工作空间：当一个进程开始一个事务时，为进程提供一个私有工作空间，包含进程有权访问的所有对象。进程的读写操作在私有工作空间进行，而不对实际的文件系统进行。如果事务中止，私有工作空间被释放，指向的私有块被删除。如果事务提交，私有索引被移到父辈空间，不再被访问的块被释放掉。a) 包含三个块的文件及其索引b) 块0被修改，块3被添加后的情况 c）事务提交之后（3） 写前日志（writeahead log）：先写日志，再做实际修改。日志内容：哪个事务在对文件进行修改，哪个文件和数据被改动，新值和旧值是什么日志写入后，改动才被写入文件事务中止，使用写前日志回退到原来的状态；借助稳定存储器中的写前日志：当系统崩溃后，完成事务或取消事务7.死锁预防的等-死算法和伤-等算法（1）等-死算法：由于使用了时间戳，当请求被占用的资源时只可能有两种情况： 老进程请求被新进程占用的资源， 或者，新进程请求被老进程占用的资源一种情况应该允许进程等待，另一种情况应该中止进程。也即等-死算法（2）伤-等算法：允许抢占：假设只允许老进程抢占新进程，因此图a被标记为抢先，图b为等待。这种算法称为伤-等算法（wound-wait），因为一个事务可能会受到伤害（实际是被中止）而其他的事务等待。8.举例说明集中式的死锁检测中的假死锁问题。PA和PB运行在机器0上，C运行在机器1上。共有三种资源S，R和T。如图，一开始A拥有S并想请求R，但B正在使用R；C拥有T并想请求S。协调者看到的情况如图c所示。这种配置是安全的。一旦B结束运行，A就可以得到R然后结束，并释放C所等待的S。过一会儿，B释放R并请求T，这是一个完全合法的安全操作。机器0向协调者发送一条消息声明它释放R，机器1向协调者发送了一条消息声明进程B正在等待它的资源T。不幸的是，机器1的消息首先到达，这导致协调者生成了一幅如图d所示的资源图。根据上图中的信息，协调者将错误的得出死锁存在的结论，并中止某个进程。这种情况称为假死锁。由于信息的不完整和延迟，使得分布式系统中的许多死锁算法产生了类似的假死锁问题。9.分布式的死锁检测Chandy-Misra-Haas 算法的思想？Chandy-Misra-Haas算法允许进程一次请求多个资源（如锁）而不是一次一个。通过允许多个请求同时进行使得事务的增长阶段加速。这使得一个进程可以同时等待两个或多个进程。机器1上的进程3正在等待两个资源，一个由进程4占有，一个由进程5占有。一些进程正在等待本地资源，例如进程1。一些进程，如进程2在等待其他机器上的资源。当某个进程等待资源时，例如P0等待P1，将调用Chandy-Misra-Haas算法。生成一个探测消息并发送给占用资源的进程。消息由三个数字构成：阻塞的进程，发送消息的进程，接受消息的进程。由P0到P1的初始消息包含三元组（0，0，1）。消息到达后，接受者检查以确认它自己是否也在等待其他进程。若是，就更新消息，字段1保持不变，字段2改成当前进程号，字段3改为等待的进程号。然后消息接着被发送到等待的进程。若存在多个等待进程，就要发送多个不同的消息。不论资源在本地还是在远程，该算法一直继续下去。图中（0，2，3），（0，4，6），（0，5，7）和（0，8，0）都是远程消息。若消息转了一圈后又回到最初的发送者，即字段1所列的进程，就说明存在一个有死锁的环路系统。第六章1.复制的目的和代价。目的：提高可靠性和提高性能。代价：引起服务器数量扩展以及地理区域扩展，那么在一致性上的代价就高了；网络通信开销；强一致性导致要求的原子操作很难快速完成。解决办法：放宽一致性方面的限制，放宽程度取决于复制数据的访问和更新模式以及数据的用途。2.能区分是否符合严格一致性、顺序一致性、因果一致性、FIFO 一致性、弱一致性、释放一致性、入口一致性。共享数据读操作和写操作时的一致性问题：一致性模型实质上是进程和数据存储间的约定，如果进程同意遵守某些规则，数据存储将正常进行。正常情况下，进程的读操作应该返回最后一次写操作的结果。没有全局时钟，精确定义哪次写操作是最后一次写操作是困难的。作为全局时钟的替代，产生了一系列一致性模型，每种模型都有效地限制了一个数据项上执行一次读操作所应返回的值。严格一致性：任何对数据项X的读操作将返回最近一次对X进行写操作的值。对所有进程来说，所有写操作都是瞬间可见的，系统维护着一个绝对的全局时间顺序。a) 严格的一致性存储 b) 非严格的一致性存储线性化和顺序一致性：顺序一致性对存储器的限制比严格一致性要弱一些，要满足以下的条件： （1） 每个进程的内部操作顺序是确定不变的； （2） 假如所有的进程都对某一个存储单元执行操作，那么，它们的操作顺序是确定的，即任一进程都可以感知到这些进程同样的操作顺序。a) 顺序一致的数据存储 b) 非顺序一致的数据存储因果一致性：所有进程必须以相同的顺序看到具有潜在因果关系的写操作，不同机器上的进程可以以不同的顺序看到并发的写操作。当一个读操作后面跟着一个写操作的时候，这两个事件有潜在的因果关系，同样，读操作也作为为读操作提供数据的写操作因果相关。没有因果关系的操作可以看作是并发的，并发的操作的顺序是不考虑的。上图是因果一致性存储允许的，但顺序和严格一致性存储不允许的顺序a)违背因果一致性的时间存储顺序 b)符合因果一致性的时间存储顺序FIFO一致性模型是在因果一致性模型上的进一步弱化，它满足下面的条件：由某一个进程完成的写操作可以被其他所有的进程按照顺序感知到，而从不同进程中来的写操作对不同的进程可以有不同的顺序。一致性表现在要求任何位置都可以按顺序看到某个单一进程的写操作。弱一致性：同步变量S仅有一个关联操作synchronization(S),该操作同步数据存储的所有本地拷贝。弱一致性模型必须满足的条件有下面几点: (1)对同步变量的访问满足一致性的要求:说明所有进程都以相同的顺序看到同步变量进行的所有操作(2)对同步变量的访问，只有在以前的写操作在各处都完成之后才能进行。强迫在所有备份上完成所有的写操作.(3)对数据的操作（读或写），只有在以前的对同步变量的操作完成之后才能进行。 保证所得到的数值是最新值.a) 对弱一致性有效的时间顺序 b) 对弱一致性无效的时间顺序b之所以不对，是因为P2执行了同步，因此访问R(x)的时候应该是b值不是a值。释放一致性：弱一致性存在的问题是，当同步变量被访问时，数据存储不知道此次访问是因为进程结束对共享数据的写操作，还是因为进程将开始读数据而进行的。释放一致性使用两种类型的同步变量来代替原来的一种同步变量：获取Acquire操作用于表明进程进入临界区释放Release操作用于表明进程退出临界区P1执行获取操作，两次改变x的值，然后释放操作。P2执行获取操作，并读取数据项x。可以保证，进程P2得到执行释放后的值，也就是b，（除非P2在P1执行获取操作之前执行获取操作）。如果P2在P1没有执行释放操作之前执行获取操作，那么获取操作等待释放操作的完成。P3没有执行获取，所以没有看到一致的值是可以理解的。入口一致性：要求每个普通的共享数据都要与某种同步变量（如锁）关联思想：使得多个包含不同共享数据的临界区可以同时执行，从而增加系统的并行度，付出的代价是每个共享数据与某种同步变量关联的额外开销和复杂性满足入口一致性的条件是：(1)在一个进程可以获取一个同步变量前，所有由该同步变量保护的共享数据相对与该进程已经更新完毕(2)在一个进程被允许以独占模式访问某同步变量之前，任何别的进程不可以拥有该同步变量，即使以非独占模式下拥有。(3)在一个进程以独占模式访问一个同步变量之后，在对该同步变量的所有者检查之前，任何其他进程都不能执行下一个非独占访问。入口一致性和释放一致性的区别就在于，释放一致性对临界区加锁，这个临界区可以放很多共享数据，入口一致性对临界区的每一个共享数据单独加锁，粒度更低，并发性更高。不使用同步操作的一致性模型：ConsistencyDescription严格所有共享访问按绝对时间排序线性化所有进程以相同顺序看到所有的共享访问。而且，访问是根据全局时间戳排序的顺序所有进程以相同顺序看到所有的共享访问。访问不是根据时间排序的因果所有进程以相同顺序看到因果相关的共享访问。FIFO所有进程以不同进程提出写操作的顺序相互看到写操作。来自不同进程的写操作可以不必总是以相同的顺序出现。使用同步操作的一致性模型：ConsistencyDescription弱只有在执行一次同步后，共享数据才被认为是一致的释放退出临界区时，使共享数据成为一致的入口进入临界区时，使属于一个临界区的共享数据成为一致的3.能区分是否符合单调读、单调写、写后读和读后写。单调读：如果一个进程读取数据项x的值，那么该进程对x执行的任何后续读操作将总是得到第一次读取的那个值或更新的值。进程 P 对同一数据存储的两个不同本地备份执行的读操作a) 提供单调读一致性的数据存储 b) 不提供单调读一致性的数据存储.单调写：如果一个进程对数据项x执行的写操作必须在该进程对x执行的任何后续写操作之前完成。进程 P 对同一数据存储的两个不同本地备份执行的写操作，类似以数据为中心的FIFO一致性a) 提供单调写一致性的数据存储 b) 不提供单调写一致性的数据存储写后读：一个进程对数据项x执行的写操作结果总会被该进程对x执行的任何后续读操作看见。这个一致性保证，写操作的结果可以被所有的后续读操作看到。a) 提供写后读一致性的数据存储 b) 不提供写后读一致性的数据存储读后写：同一个进程对数据项x执行的读操作之后的写操作，保证发生在与x读取之相同或更新的值上。也就是说，进程对数据项x所执行的任何后续的写操作都会在x的拷贝上执行，而该拷贝是用该进程最近读取的值更新的。读后写一致性用于保证，网络新闻组的用户只有在已经看到原文章之后才能看到他的回应文章。a) 提供读后写一致性的数据存储 b) 不提供读后写一致性的数据存储4.掌握基于主备份的写协议。在基于主备份的协议中，每个数据项x都有一个关联的主备份，负责协调x的写操作，根据主备份是否被固定在一个远程服务器上，或将主备份移动到启动写操作的进程那里之后写操作是否可在进程本地执行，可将基于主备份的写协议分为远程写协议和本地写协议。基于主备份的远程写协议：（1）所有读操作和写操作都被转发到一个固定的服务器上。（2）从一致性角度看，主机备份协议允许进程在本地可用的副本上执行读操作，但必须向一个固定的主拷贝上转发写操作的协议。a) 主机备份协议 b)基于主备份的远程写协议基于主备份的本地写协议：（1）每个数据项都只有一个单一拷贝，每当一个进程要在某个数据项上执行操作时，先将那个数据项的单一拷贝传送到这个进程，然后在执行相应操作。（2）主机备份的本地写协议，多个连续的写操作可在本地进行，而读操作的进程还可以访问它们的本地拷贝，其中主备份移动到要执行更新的进程那里，并且支持离线操作。a) 基于主备份的本地写协议 b)主机备份协议的本地写协议5.掌握基于复制的写协议。复制的写协议：写操作可以在多个副本上执行，分为主动复制和基于法定数目的协议。主动复制的写操作：可以在多个副本上执行，每个副本对应一个进程，该进程执行更新操作.潜在问题：(1)写操作导致更新传播，操作需要在各地按相同顺序进行，时间戳和定序器来实现。（2）被复制的调用，如下图中C被调用多次。解决办法：给b和b的复本分配一个相同的，唯一的标识符，然后使用B的协调器将请求发送到c的所有复本上，c处理完后将消息反馈到c的协调器上，然后由c的协调器将消息复制到b的所有复本上。基于法定数目的协议：要求客户在读或写一个复制的数据项之前向多个服务器提出请求，并获得他们的许可。与前边的主动复制的差异在于，主动复制要将更新传递到所有的复本上去。Gifford方法：客户在读写一个复制的数据时，先向多个服务器提出请求，获得许可;读团体NR和写团体NW, N个副本NR+NW>N; NW>N/2表决算法的三个实例a)读集合和写集合的正确选择 b)可能导致写写冲突的读集合和写集合c)读集合和写集合的正确选择，ROWA (read one, write all)第七章1.什么叫容错性？容错意味着系统即使发生故障也能提供服务，容错与可靠性相联系，包含以下需求：可用性（Availability）：任何给定的时刻都能及时工作可靠性（Reliability）：系统可以无故障的持续运行安全性（Safety）：系统偶然出现故障能正常操作而不会造成任何灾难可维护性（Maintainability）：发生故障的系统被恢复的难易程度2.掩盖故障的冗余有哪几种？信息冗余：增加信息，如海明码校验；时间冗余：多次执行一个动作，如事务；物理冗余：增加额外的设备或进程。3.拜占庭将军问题Lamport 证明在具有m个故障进程的系统中，只有存在2m+1的正常工作的进程才能达成协议。三个忠诚将军和一个叛徒的问题，叛徒通过发送错误和矛盾来组织忠诚将军达成协议。假设现在将军们要相互告知自己的兵力，将军三是叛徒。每个人都将自己收到的向量发给其他所有的将军。(a) 将军宣布他们的兵力(b)(a)基础上每个将军的向量(c)每个将军收到的向量这个时候，将军们把自己收到的向量中，哪一个数出现得最多就把他纪录到自己的向量中去，因此将军124都可以看到相同的消息：（1,2，UNKNOWN，4）。但是如果有两个忠诚将军和一个叛徒将军，就不能判断了。4.什么叫原子多播？在分布式系统中经常需要保证消息要么被发送给所有的进程，要么就不向任何进程一个也不发送。另外，如果传送的话，通常还需要所有的消息都按相同的顺序发送给所有的进程。这种方式称为原子多播。原子多播确保没有故障的进程对数据库保持一致；当一个副本从故障中恢复并重新加入组时，原子多播强制它与其他组成员按保持一致虚拟同步：保证多播到组视图的消息被传送给组中的每个正常进程，如果发送消息的进程在多播期间失败，则消息或者传递给剩余的所有消息，或者被每个进程忽略。具有这种属性的可靠多播称为虚拟同步。所有多播都在视图改变之间进行消息排序：（1）可靠不排序的多播：对接收不同进程发送的消息的次序不做任何保证（2）FIFO顺序的多播：按照消息发送的顺序传送同一进程的消息，对不同进程发送的消息的传送顺序没有约束（3）按因果关系排序的多播：按因果关系排序多播来保留消息间的因果关系（4）全序多播：无论消息传送是无序、 FIFO顺序还是按因果关系排序，对所有的组成员按相同的次序传送提供了全序的消息传送的虚拟同步可靠多播称为原子多播5.基本的可靠多播方法的思想？存在的问题。可靠多播:发送到一个进程组的消息被传递到该组的每个成员。基本的可靠多播方法：假定所有的接受者已知且进程不会失败，而且在通信运行期间不会有进程加入或离开组发送进程为它发送的每个多播消息分配一个序列号。假定消息按它们被发送的次序进行接收。在这种方式中，接受者很容易探测到消息丢失。每个多播消息都在发送者本地的一个历史缓存器中进行存储。假定发送者知道接收者，那么发送者就简单地在每个接收者都返回一个确认之前在历史缓存器中保留消息。如果接收者探测到它丢失了一个消息，那么就返回一个否定确认，请求发送者重发。作为选择，发送者可以在某个时间内没有接收到所有确认的情况下自动重发消息。存在的问题是：不能支持过多的接收者，如果有N个接收者，那么发送者必须准备接收至少N个确认。如果有很多的接收者，那么发送者可能被大量的反馈消息淹没，称为反馈拥塞。6.分布式提交两阶段提交的思想？在两段提交协议中，将提交分成两个阶段，每个阶段有两步（1）（2）属于第一阶段（3）（4）属于第二阶段：（1） 协调者向所有的参与者发送一个VOTE_REQUEST消息。（2） 当参与者收到VOTE_REQUEST消息时，就向协调者返回一个VOTE_COMMIT消息通知协调者它已经准备好本地提交事务中属于它的部分，否则返回一个VOTE_ABORT消息。（3） 协调者收集来自参与者的所有选票。如果所有的参与者都表决提交，那么就向所有的参与者发送一个GLOBAL_COMMIT消息，如果有一个参与者表决取消，协调者决定取消事务并多播一个GLOBAL_ABORT消息。（4） 每个提交表单的参与者等待协调者的最后反应。如果参与者收到GLOBAL_COMMIT消息，就在本地提交事务，否则收到GLOBAL_ABORT，就在本地取消事务。a) 2PC中的协调者的有限状态机 b) 2PC中的参与者的有限状态机参与者一旦投票，则失去自主能力，必须等待协调者的最终决定，可能造成阻塞可能的阻塞状态：参与者在INIT状态等待协调者的VOTE_REQUEST消息;协调者在WAIT状态等待来自每个参与者的表决;参与者在READY状态等待协调者发送的全局表决消息;7.分布式提交三阶段提交的思想？三段式的提出主要为了避免协调者崩溃后，参与者在协调者恢复之前无法解除阻塞的问题。阶段1同两阶段方式阶段2如果任意一个参与者投票中止事务，那么协调者就发GLOBAL_ABORT消息；否则如事务可以提交，就发送一个PREPARE_COMMIT消息。只有在每个参与者都确认它已经准备提交时，协调者才发送最后的GLOBAL