本题要求对分布式系统中的共享资源问题与多副本数据问题进行综述。以下答案将根据您提供的资料进行组织和引用。
五、综述题
1、哪些问题与共享资源相关，以及对应的解决办法？
在分布计算系统中，共享资源的使用是核心问题之一。由于资源的分散性、多重性以及不可预知的报文延迟，资源管理和同步变得复杂。与共享资源相关的核心问题包括互斥访问、并发控制和死锁，以及确保系统整体处于一致状态。
| 共享资源相关问题 | 问题描述与后果 | 对应的解决办法（或机制） |
|---|---|---|
| 互斥访问 (Mutual Exclusion) | 某些资源（如可写文件、可修改的主存区域、外部设备）在任一时刻只允许一个进程使用。需要对活动的执行进行排序。 | 互斥算法：用于保证任一时刻只有一个进程访问临界区。包括： - 集中式互斥算法 - Lamport 时间戳算法 - Ricart-Agrawala 算法 - Maekawa 互斥算法（基于请求子集） - 令牌环互斥算法（如简单令牌环、基于时间戳的令牌算法） |
| 死锁 (Deadlock) | 多个进程因竞争资源或通信报文而陷入循环等待，导致系统无法继续执行。死锁发生的四个必要条件：互斥、不可剥夺、占有并等待、循环等待。 | 死锁处理策略 (PAID)： -预防：通过打破四个死锁条件之一（如，进程开始前同时获得所有资源，或资源编号排序）。 -避免：动态分配资源，确保系统处于安全状态。 -检测与恢复：允许死锁发生，然后通过检测算法（如集中式、路径推动、边跟踪、快照算法）发现并解除死锁。 |
| 并发控制 (Concurrency Control) | 多个事务处理并发访问共享数据时，可能导致丢失更新或检索不一致，使数据库处于不一致状态。 | 可串行化调度：要求多个事务并发执行的结果与它们串行执行的结果相同。 基于锁的并发控制： -两阶段封锁 (2PL)：分为增长阶段和收缩阶段，保证一致性。 -严格两阶段封锁：事务处理一直占有锁直到操作完成，解决层叠回退问题。 |
| 资源状态一致性 (Consistency) | 由于报文延迟不可预知，合作进程看到的系统状态可能不一致。同步机构目的是提供手段，使系统保持一致状态。 | 同步机构： - 集中式同步机构（简单但有瓶颈、不可靠）。 -分布式同步机构（性能和可靠性更高，如多重逻辑时钟、循环令牌）。 -逻辑时钟/向量时钟：给事件提供一个唯一的排序，处理因果关系。 |
| 数据保护与访问控制 (Protection) | 阻止非法用户访问、修改或干扰系统数据。 | 访问控制：对用户身份鉴别，并限制其访问权限。 加密技术：包括传统加密方法和公开密钥加密方法，确保数据传输和存储的保密性、完整性。 |
2、请说明分布计算系统的多副本数据的必要性，说明本课程那些内容与多数据副本相关？
分布式系统采用多副本数据（数据复制）的必要性
多副本数据（或文件复制）是分布式系统容错和性能优化的关键措施。其主要必要性体现在以下三个方面：
- 高可用性 (High Availability) 和可靠性 (Reliability)：文件复制是一种冗余措施。即使某个机器、存储介质或通信出现故障，其他副本仍可访问，保证系统能够继续运行。
- 性能改进 (Performance Improvement)：
- 通过将数据副本放置在离访问进程最近的位置，可以缩短服务时间，提高响应速度。
- 多副本数据可以减少服务员的负载和网络通信量，从而增强系统的可扩充性。
- 资源冗余 (Resource Redundancy)：复制是资源冗余的一种形式，使得在实现冗余时，各种冗余资源互相替换变得容易，提高了操作的可靠性。
与多数据副本相关的课程内容
多副本数据的使用在分布式系统设计中引入了**一致性（Consistency）**的复杂挑战，因为必须确保所有副本看起来像一个单一的逻辑实体。因此，本课程中许多内容都围绕着如何高效、透明地管理这些副本，并保持它们之间的一致性：
透明性 (Transparency)：
- 复制透明：这是分布式文件系统（DFS）期望达到的目标之一。它要求文件或其他对象的多个副本同时存在于系统中，但这种情况对用户是不可见的，对对象的修改应同时作用在所有副本上。
数据一致性模型 (Data Consistency Models)：
- 这些模型定义了进程与数据存储之间关于数据访问的约定。由于存在副本，不同的进程对数据项的读写顺序可能不一致，因此需要定义一致性级别，包括严格一致性、顺序一致性、相关一致性、弱一致性、释放一致性和进入一致性等。
复制控制算法 (Replication Control Algorithms)：
- 这些算法专门用于保证兼容可串行化和维持数据库多副本间的相互一致性。
- 表决法：如法定数方法 (Quorum)。该方法定义了读定额（NR）和写定额（NW），只有在获得足够数量的服务员同意后才能进行操作，并且必须满足NR+NW>NNR + NW > NNR+NW>N（N为副本总数）。
- 非表决法：如主站点方法（所有请求发送到一个主节点处理） 和循环令牌方法（令牌携带顺序号以建立请求的全排序）。
分布式文件系统中的缓存与一致性 (DFS Caching and Consistency)：
- 客户端缓存文件数据是数据复制的一种形式。缓存方案必须解决“如何决定各个顾客缓存中的数据是否一致”的问题。
- 更新策略：如“关闭时写”策略。
- 有效性检验：包括顾客发动的方法和服务员发动的方法。
分布式共享存储器（DSM）中的缓存一致性协议：
- DSM通过虚拟地址空间实现了物理上分布、逻辑上共享的存储器。由于数据可以在节点间移动并缓存，要求解决各副本的一致性问题。
- 探听缓存方法 (Snooping)：用于共享总线环境中，如 Berkeley 协议。
- 目录协议 (Directory Protocol)：通过在共享存储器中设置目录来跟踪数据块副本的位置，避免广播。
- DSM一致性协议分类：写无效协议（写操作使其他副本无效，维持一个可写副本和多个只读副本）和写更新协议（每次写都要更新所有副本）。
