高级操作系统

2020/1/181高级操作系统AdvancedOperatingSystem熊焰[e-mail]0551_3600689中国科学技术大学计算机系2020/1/182第二章分布式系统同步分布式系统时钟同步分布式互斥分布式选举算法分布式系统死锁2020/1/1832.1分布式系统时钟同步在分布式系统中：进程之间的通信：采用消息传递(Message-passing)，而不是通过共享存储器进行通信的。与进程通信密切相关的问题：进程之间是如何彼此协作和同步的。例如，分布式系统中临界区是如何实现的以及资源是如何分配的？在单机系统中，临界区、互斥和同步一般都是采用信号灯和管程等方法来解决的。这些方法却并不能很好地应用于分布式系统，其原因是这些方法都是建立在共享存储器2020/1/1842.1分布式系统时钟同步基础上的。两个采用信号灯进行交互的进程必须能够访问到这个信号灯。如果这两个进程是运行在同一台机器上，那么它们只要将信号灯存放在机器的内核中，就可以共享到这个信号灯。但是，如果它们运行在不同的机器上，则共享信号灯的方法再也无效了。因此，需要一些新的方法来解决分布式系统中进程间交互的问题。在这一章我们将讨论分布式系统中与进程间协作和同步有关的问题。首先，我们引入时间的度量，因为时间在分布式同步中起着重要的作用，其次,介绍分布式互斥和选举算法;最后,讨论分布式系统的死锁。2020/1/1852.1分布式系统时钟同步分布式系统中的同步比单机系统中的同步要复杂的多,原因是前者必须使用分布式算法。在分布式系统中,由某一个机器收集整个系统的所有信息,然后,让这个进程考察这些信息并作出一个决定通常是不大可能的,也不是人们所希望的。因此,分布式算法应具有下列特性:1.相关的信息是分布在多个机器上的。2.进程根据局部信息来作出决定。3.对系统中任一个机器的失败应能容错。4.不存在公共时钟或其它全局时间源。2020/1/1862.1分布式系统时钟同步前三点表明由一个机器收集所有的信息进行处理是不可能的。例如,在资源分配时,将所有请求发送给一个管理者进程,由它根据表中的信息来考察所有的请求并决定资源的分配。这在分布式系统中必将造成某一个进程负担过重。此外,一个分布式系统应该比单机系统更可靠。如果一个机器崩溃了,其余的机器应能继续工作,而不至于使系统瘫痪。第四点也是非常重要的。在单机系统中,时间是确定的。如果一个进程想要知道时间,则它可以调用一个系统调用由内核告诉它当前的时间值。如果一个进程先得到时间值而另一个进程后得到时间值,那么,先得到的时间值一定比后得到的时间值小，然而,在分布式系统中,所有机器要在时间上达到一致是非常困难的。2020/1/1872.1分布式系统时钟同步首先,我们看一看在分布式系统中缺乏全局时间所产生的影响。考察Unix中的make程序。通常,一个大程序分成多个源文件。这样,对其中某一个文件的修改只需要对被修改的这个文件进行重编译,而无须对所有的源文件进行编译。当调用make程序时，Make程序考察所有源文件和对应目标文件的修改时间。如果源文件input.c的修改时间为2155且对应目标文件input.o的修改时间为2151,那么,make程序知道input.c已被修改。input.c必须被重新编译。如果output.c的修改时间为2144且对应目标文件output.o的修改时间为2145,则不需要对output.c进行重新编译。Make程序在考察完所有源文件和其对应目2020/1/1882.1分布式系统时钟同步标文件的修改时间后决定那些文件需要重新编译并调用编译器对其进行编译。在分布式环境中,由于无法在全局时间上达到一致,所以,情况并非这样简单。假定output.o的修改时间为2144,在这以后,outpu-t.c被修改并被赋予的时间为2143,原因是output.c所在机器上的时钟要比output.o所在机器上的时钟慢。所以,make程序不调用编译器进行编译，结果,最终可执行二进制程序将含有由新老源文件所生成的目标文件，导致该可执行程序无法运行而程序员却不知道原因而一直寻找程序代码的错误。因此，在分布式系统中，时钟同步是非常重要的，也是必不可少的。2020/1/1892.1分布式系统时钟同步2.1.1逻辑时钟同步算法所有计算机上都有一个：记录时间的电路---称之为时钟---它实际上是一个定时器---一个以某个频率进行震荡的石英晶体。与定时器相关的两个寄存器分别称之为计数器和保持寄存器。晶体每震荡一次,计数器就减一。当计数器变为0时,一个中断产生并将保持寄存器的值重新装入到计数器中。因此,我们可以对定时器进行编程使得定时器每秒钟中断60次。每一次中断称之为一次时钟滴答。在单机系统中,时钟快一点或慢一点都无关紧要,因为单机上的所有进程都使用同一个时钟。每一个进程所得到的时钟值在本机内是一致的。但是,在分2020/1/18102.1分布式系统时钟同步2.1.1逻辑时钟同步算法布式系统中,情况与单机系统完全不同。虽然每一个晶体震荡器的频率相当稳定,但也无法保证不同机器上晶体的震荡频率完全相同。实际上,分布式系统中，n个计算机上的时钟值都不相同。因此,需要一种方法将所有机器上的时钟进行同步。Lamport在1978年指出时钟同步是可能的并提出了一个逻辑时钟同步算法。在1990年,Lamport扩展了他的工作。Lamport指出时钟的同步不是绝对的。如果两个进程并不交互,则它们的时钟就无须同步。2020/1/18112.1分布式系统时钟同步2.1.1逻辑时钟同步算法原因是时钟不同步不会产生什么问题。系统中的进程不需要在事件发生的确切时间上达成一致而只需要在事件发生的先后顺序上达成一致即可。在make例子中,make只需要知道input.c是否比input.o生成的早即可,而无须知道input.c和input.o确切的生成时间。在许多应用中,只要所有机器都认可某一时间就足够了,而这个时间无须与收音机每小时广播的时间相同。例如,尽管现在真正的时间是10:02,但只要所有机器都认为现在是10:00,我们说系统的时钟是同步的。我们把这种并不一定是真正时间但所有机器都一致认可的时钟称之为逻辑时钟。如果我们2020/1/18122.1分布式系统时钟同步2.1.1逻辑时钟同步算法增加一个条件:所有的时钟不仅一致而且与实际时间之间的误差不超过某个值。那么,这种时钟我们称之为物理时钟。为了将逻辑时钟进行同步,Lamport定义了一种称之为在之前发生的关系。表达式a→b读做”a在b之前发生”。它表示所有的进程都认为事件a先发生,而事件b后发生。a→b存在于下列两种情况:1.如果a和b都是同一个进程中的两个事件且a在b之前发生,则a→b为真。2.如果a是一个进程发送一个消息的事件且b是另一个进程接收该消息的事件,则a→b为真。2020/1/18132.1分布式系统时钟同步2.1.1逻辑时钟同步算法在之前发送是一个传递关系,如果a→b且b→c,则a→c。如果两个事件x和y分别发生在两个不同的进程内且x和y不是同一个消息的发送和接收事件,则x→y不为真,y→x亦不为真。我们将这两个事件称之为是并发事件。度量时间的方法：对于每一个事件a,我们给a分配一个所有进程都认可的时间值C(a)。这种时间值必须具有一个特性:如果a→b,则C(a)C(b)。时钟时间C是一直向前走的(即增加)，不会向后退(即减少)。时间的修改只能增加而不能减少。2020/1/18142.1分布式系统时钟同步2.1.1逻辑时钟同步算法例如，图2-1（a）中有三个进程。每一个进程都运行在不同的机器上且每一个机器都有一个自己的时钟以各自的速度走时。当进程0中的时钟滴答6次时，进程1滴答8次，而进程3滴答10次。每一个时钟的走时速度是恒定的。在时间为6时,进程0发送了一个消息A给进程1。进程1在时间为16时收到了消息。如果消息中含有消息开始发送的时间值6,则进程1认为该消息的传输花费了10次滴答。同理,消息B从进程1传输到进程2花费了16次滴答。但是,由进程2发给进程1的消息C在发送时的时间值为60而在接收时的时间值为56。这样,消息C的传输时间为负值。2020/1/18152.1分布式系统时钟同步2.1.1逻辑时钟同步算法0120120000006A8106A8101216201216201824B301824B302432402432403040503040503648C603648C6042567042617048D648048D698054729070779060801007685100(a)(b)图2-1.(a)三个进程,每一个进程都有自己的时钟。三个时钟都以不同的速度走时。(b)Lamport修改时钟算法。2020/1/18162.1分布式系统时钟同步2.1.1逻辑时钟同步算法Lamport解决这个问题的算法：每一个消息都含有一个发送者时钟的发送时间,当消息到达时,接收者将自己时钟的接收时间与发送时间相比较。如果接收时间小于等于发送时间,则接收者的时钟被修改成发送时间加1。如果接收时间大于发送时间,则不改变接收者的时钟。因此,消息C到达进程1的时间改为61,消息D到达进程0的时间改为70(见图2-1(b))。Lamport算法还必须满足一个要求：任意两个事件的时间之差至少为1。如果一个进程连续发送或接收两个消息,则这两个消息的时间之差也至少为1。我们对不同进程内两个同时发生的事件是这样赋时间值的:2020/1/18172.1分布式系统时钟同步2.1.1逻辑时钟同步算法事件发生的时间值与该事件所属进程的进程号连接起来,中间用’.’加以分隔。例如,进程1和进程2中两个事件恰好同时在时间为40时发生。进程1中的事件发生时间为40.1而进程2中的事件发生时间为40.2。由此我们可以对系统中所有事件按如下方法赋时间值:1.在同一进程中,如果事件a在事件b之前发生,则C(a)C(b)。2.如果a和b分别是一个消息的发送和接收事件,则C(a)C(b)。3.对所有事件a和b,C(a)≠C(b)。2020/1/18182.1分布式系统时钟同步2.1.2物理时钟同步算法如果某台机器有一个接收器接收标准时间,那么,时钟同步算法的目的就是让所有机器的时钟与该机器的时钟进行同步。如果没有一台机器具有接收器且每一台机器都有自己的时钟,那么,时钟同步算法的目的就是使得所有机器的时钟尽可能地一致。假定每一个机器都有一个每秒中断H次的定时器。定时器中断一次,中断处理程序就将软件时钟加1。该软件时钟保存滴答(即中断)次数。我们定义这个软件时钟的值为C。当UTC(一种标准的时间源)时间为t,则机器p上时钟值为Cp(t)。在理想情况下,对于所有的p和t,Cp(t)=t。换句话说,dC/dt=1。2020/1/18192.1分布式系统时钟同步2.1.2物理时钟同步算法实际的定时器不可能每一秒精确地滴答H次。一个具有H=60的定时器应该每小时周期地滴答216,000次。但世界上最先进定时器芯片的相对误差是10-5。这就意味着一个机器时钟每小时的滴答值在215,998至216,002范围内。更确切地说,如果存在某个常数ρ使得：1-ρ≤dC/dt≤1+ρ则该定时器的误差在允许的范围之内。常数ρ由厂商设定。有时也称之为最大漂移率。当dC/dt1时,时钟太快。当dC/dt1时,时钟太慢。只有dC/dt=1时,时钟不快不慢。2020/1/18202.1分布式系统时钟同步2.1.2物理时钟同步算法如果两个时钟朝着UTC两个相反的方向漂移,则在它们同步后的Δt时刻,它们之间的相差为2ρΔt。如果操作系统的设计者要保证任意两个时钟相差不超过δ，则时钟必须每δ/2ρ秒同步一次。Cristian算法：假定：有一台机器拥有一个接收器。我们称这台机器为时间服务器。算法：每一台机器周期地(周期低于δ/2ρ秒)向时间服务器发送一个消息请求获得当前标准时间。时间服2020/1/18212.1分布式