文档介绍：高级操作系统 Advanced Operating System
熊 焰
0551_3600689
中国科学技术大学计算机系
汽车防盗器
陈香兰***@
1
选举算法
许多分布式算法需要一个进程充当协调应商W公司进行联系，希望6月份能交付10万件10厘米的装饰品。W公司提出12月份交付10万件淡紫色装饰品。D公司同意对方开出的价格，但不喜欢紫色，并且希望6月份到货，而且因为自己的客户是国际客户，因此，坚持要10厘米的产品。W公司答复说10月份提供3 15/16英寸的淡紫色装饰品。经过更进一步的谈判，双方最终同意8月15日交付3 959/1024英寸的紫罗兰装饰品。
18
到此为止，双方就可以自由中断本次谈判，返回到开始谈判前的状态。
然而，一旦公司双方签订了合同，那么不论发生什么事情，他们在法律上都有责任完成该合约。
因此，在双方还未签字前，任何一方都可以反悔，就像什么都没有发生一样，但是一旦双方都签了字，他们就不能再反悔，合同就必须被执行。
19
2、多进程之间的模型
分布式系统中多进程之间的模型和商业模型相类似。
一个进程宣布它想和其他一个或几个进程开始一个事务，它们可以就不同的选择进行协商、创建、删除对象，执行一段时间的操作。
然后发起者宣布它希望其他进程能保证任务完成。
如果其他进程都同意，那么就达成了永久的协议。
如果有一个或几个进程拒绝（或在同意前崩溃），那么就会返回到事务开始前的状态。这时对象、文件、数据库等方面的副作用都不会发生。
这种要么全有要么全无的特性简化了编程人员的工作。
20
3、磁带系统模型
计算机系统中对事务的使用可以回溯到20世纪60年代。在硬盘和在线数据库出现之前，所有的文件都保存在磁带上。
假设有一个有自动盘点系统的超级市场，每天关门后，计算机对两盘作为输入的磁带进行处理:
第一盘磁带存有当天早晨开门以前的所有库存，
第二盘存有当天已销售给客户的产品和交付给供应商的产品。
计算机从两盘磁带上读取数据，并生成新的主库存磁带，如图所示：
21
这种设计的最大优点（尽管与它生活在一起的人们并没有意识到）在于
对任何原因引起的运行错误，所有的磁带都可以倒卷（rewound），其工作可以毫无损失地重新开始。
因此，老式的磁带系统具有了原子事务要么全有要么全无的特性。
22
4、在线更新数据库模型
银行在线更新数据库:
客户通过带有调制解调器的PC机连接到银行，想将一个账户下的钱取出再存入另一账户。
操作通过下面两步执行：
提取（金额，账户1）
存入（金额，账户2）
如果电话线在第一步之后第二步之前中断，那么第一个账户已被取出而第二个账户却没有存入。钱就消失在了未知的空间中。
23
将这两个操作组成一个原子事务可以解决这个问题。
要么两个都执行，要么任何一个都不执行。
需要解决的关键问题是事务执行失败后能返回到最初状态。我们真正需要的是像使用磁带时那样的对数据库倒卷的方法。这种能力是原子事务必须提供的。
24
事务模型
事务的属性和模型：
假设1：系统由一些相互独立的进程组成，每个进程都会随机出错。
假设2：通信错误已经被底层软件透明地处理
尽管通信一般来说是不太可靠的，消息会丢失，但是底层可以采用超时重发协议恢复丢失的消息。
25
假设3：稳定存储器
存储器有三种分类。
第一种是普通的RAM存储器，当电源出错或机器崩溃时会丢失信息。
第二种是磁盘存储器，它不受CPU错的影响，但磁头错会导致信息丢失。
最后一种是稳定存储器（stable storage）。它不受其他任何错误的影响。
26
1、事务原语
使用事务编程需要由操作系统提供或者由语言运行系统提供特殊的原语语句，例如：
BEGIN_TRANSACTION：标记一个事务的开始
END_TRANSACTION：结束事务并设法提交
ABORT_TRANSACTION：取消事务；恢复旧值
READ：从一个文件（或其他对象）读取数据
WRITE：将数据写入一个文件（或其他对象）
27
事物原语取决于事务中正在使用的对象类型。
在一个邮件系统中，可能有发送、接收以及转发邮件等原语。
而在一个账目系统中可能会有很大的不同，读取和写入是典型的原语应用。
在一个事务中，也允许使用普通语句、过程调用等等。
28
2、事务体
BEGIN_TRANSACTION和END_TRANSACTION
限定事务的范围。
它们之间的操作构成了事务体。
事务体中的操作要么全部执行，要么一个也不执行。
这些操作也可能是系统调用，库过程，或者是某种语言中用括号括起来的语句，这取决于应用的需要。
29
事务举例
考