集中式和分布式操作系统中的同步互斥比较教学

武秀川　翟一鸣　任满杰

摘要:本文对集中式操作系统和分布式操作系统中的同步互斥机制进行了对比分析,并对这两种系统中的互斥策略通过比较教学法进行了进一步研究。

关键词:操作系统;集中式系统;分布式操作系统;同步;互斥

中图分类号:G642 文献标识码:B

1引言

分布计算系统中的各种资源是在地理上和物理上分布的,这种分布会造成信号传播过程中的延迟以及部分失效,因此与单机操作系统相比,分布计算系统的资源管理和资源调度更加复杂。

在研究生的“分布式操作系统”和本科生的“操作系统”教学过程中,通过分布式系统和集中式系统中对资源的同步互斥机制进行比较教学,使得学生对互斥算法的了解更为透彻,分别取得了较好的教学效果。

2系统中的同步

无论集中式系统还是分布式系统中,为了实现多进程有效共享系统中的各类资源,都需要用同步机构进行互斥控制系统进行资源的调度和管理。在单机集中式系统中通常使用信号灯以及P-V操作进行同步控制并实现互斥算法,而在分布式系统中使用报文进行通信以实现互斥控制。由于集中式系统和分布式系统所采用的同步机构不同,因此要求也不同。

集中式系统和分布式系统中实现同步均可以用硬件方法也可以用软件方法,通过比较教学使学生加深理解。

2.1集中式系统中的同步

集中式系统中同步的硬件实现方法是借助于TS(Test and Set)、Compare-and-Swap以及Fetch-and-Add等硬件机器指令,具体做法是通过为每个可共享的资源设置一个锁,通过进入临界区时的关锁和退出临界区时的开锁以达到对共享的临界资源的互斥同步控制。该方法虽然可以实现互斥且实现简单,但是不符合“让权等待”的同步机制准则。

集中式系统中同步的软件实现方法通常是采用信号量机制。最简单的是整型信号量机制,通过两个标准的P、V操作实现资源的互斥使用。为了使得多个同类资源能够被有效的互斥使用,在信号量机制的概念中引入记录型信号量加以实现。采用AND型信号量可以较为有效的避免多个进程同时要求多种共享资源时发生死锁的问题。为了让进程能够一次使用多个同类资源而且不用进行多次等待操作(P操作),又使用信号量集机制进行控制。

实际上互斥是一种特殊的同步,软件方法中还经常使用Dekker算法和Peterson等算法简单的实现进程间的互斥。此外还有管程等同步控制机制。

2.2分布式系统中的同步

在分布式系统中由于没有共享的主存,因此主要使用报文进行通信以实现同步。总的来说,分布式系统中的同步系统其本质就是使得各种使用共享资源的操作或活动形成一个有序序列,或者说同步机构的目的就是给使用资源的多个进程提供某种方法和手段使分布式系统保持一个一致的状态,如多副本文件系统的一致性等。

分布式系统中实现硬件同步的方法一般是采用物理时钟、事件计数器、顺序器等。物理时钟方法中,时钟服务器从WWV或GEOS处获得UTC,根据系统和用户的需要以集中式物理时钟的方式或分布式物理时钟的方式实现同步控制。在教学的过程中,要给学生着重说明这里的集中式物理时钟方式中的集中式与单机系统中的集中式的不同。这里所谓的集中式物理方式是指在分布式系统中由时钟服务器统一的以基于广播的方式和请求驱动的方式向整个分布式系统提供同步所需要的时钟。在基于广播的方式中,集中的时钟服务员定期的向分布式系统中的各个成员广播当前的时间,由接收到广播时间的各个成员对时间进行处理。与此不同的是在集中式物理时钟的请求驱动方式中,由系统中的各个成员向集中式的时钟服务员发出请求以求获得当前的时间。分布式系统中的集中式物理时钟服务员的可靠性差,同时也是系统的瓶颈,因为时钟服务员的崩溃可能导致系统的崩溃。分布式系统中的分布式物理时钟与上述集中式物理时钟的方法不同,它是由系统中的各个成员在规定的时间内向其它成员广播它的当前时间并按照约定的方法进行时间的校正。

由于分布式系统中资源的广泛分布性,很难准确地获得系统中每个机器确切的时钟值,因此实际上很难做到准确地同步,所以一般在分布式系统中更多的采用基于Lamport“在先发生关系”的逻辑时钟进行逻辑时钟校正以给分布式系统中的各个事件一个惟一的排序,从而达到同步的目的。

分布式系统中实现互斥同步控制的最简单的方法是在并发执行的各个进程中选定一个进程作为协调者。当任一个进程想进入临界区时,首先要向协调者进程发送请求报文申请临界区进入许可。协调者进程根据目前临界区中的进程情况或者同意或者拒绝请求者进程进入临界区。这样的过程是通过报文的传递进行的。如果目前临界区内已有进程的话协调者或者拒绝或者不回答请求的进程。无论是哪种方式,系统都要设置一个缓冲队列用来存放被阻塞的请求进程。当临界区被退出后,由退出进程向协调者进程发送一个释放报文,协调者进程将进入临界区许可报文发送给相应的被阻塞队列中的第一个进程,使其退出等待队列进入临界区。显然该算法的实现机制保证不会出现饿死和死锁现象。该方法实际上是在分布式系统中模仿单机集中式系统的实现方式,存在同样的问题即性能效率低,可靠性差。

分布式互斥算法中的所有进程都是平等的,没有协调者进程的角色。互斥算法一般分为基于令牌的和非基于令牌的两大类。

在教学过程中主要介绍具有代表性的两个算法,以使学生对分布式互斥算法有清晰的理解。

非基于令牌的分布式互斥算法,典型的是Lamport时间戳算法。为了讨论上的简单,假定消息是按它们被发送的顺序被接收,而且发出的消息最后一定会被接收到。每个进程均可向其他任何进程直接发送报文,每个进程均有一个申请队列,队列中最初只有一项T0:P0申请,这里的P0是最初获得资源的进程,T0是比其他任何逻辑时钟值均小的初值。

Lamport时间戳分布式互斥算法由以下5条规则组成。

(1) 一个进程Pi如果为了申请资源,它向其它各个进程发送具有时间戳Tm:Pi的申请资源的报文,并把此报文也放到自己的申请队列中;

(2) 一个进程Pj如果收到具有时间戳Tm:Pi的申请资源的报文,它把此报文放到自己的申请队列中,并将向Pi发送一个带有时间戳的承认报文。如果Pj正在临界区或正在发送自己的申请报文,则此承认报文要等到Pj从临界区中退出之后或Pj发送完自己的申请报文之后再发送,否则立即发送;

(3) 一个进程Pi如果想释放资源,它先从自己的申请队列中删除对应的Tm:Pi申请报文,并向所有其他进程发送具有时间戳的Pi释放资源的报文;

(4) 一个进程Pj如果收到Pi释放资源的报文,它从自己的申请队列中删除Tm:Pi申请报文;

(5) 当满足下述两个条件时,申请资源的进程Pi获得资源:

①Pi的申请队列中有Tm:Pi申请报文,并且根据时间戳它排在所有其它进程发来的申请报文前面;

②Pi收到所有其它进程的承认报文,其上面的时间戳值大于Tm。

教学过程中请同学思考:在上述算法中,某进程进入一次临界区需要交换多少个报文?了解了上述互斥算法的过程,学生很容易得出结论:任何进程进入一次临界区需要3*(n-1)个报文。进而可以启发学生根据规则对上述算法进行改进从而使得任何一个进程进入一次临界区最多需要3*(n-1)个报文,如果互斥使用临界资源的进程数目很多时,可以大大地降低交换报文的通信开销。

基于令牌的分布式互斥算法中对于各进程更具公平性的是基于时间戳的令牌互斥算法。令牌是一个特殊的报文,该报文中包含了发送该令牌的进程的进程状态表。每个进程保持一张进程状态表,记录它所知的进程状态,进程状态包括该进程是否为请求进程,以及得到该状态的时间。

算法如下:

(1) 初始化时,每个进程的状态表中各个进程均为非请求状态,时钟值为0,并任意指定一个进程为令牌的持有者。

(2) 请求时,一个进程请求进入临界区时,如果它持有令牌,它不发送任何请求报文,将自己的进程状态表中相应于自己一栏的状态改为请求态,并记录该状态的时钟值,直接进入临界区。如果它不持有令牌,则它向所有其它进程发送带有时间戳的请求报文。发出请求报文后,将自己的进程状态表中相应于自己一栏的状态改为请求态,并记录该状态的时钟值。

(3) 收到请求时,当进程A收到进程B的请求报文时,A将B的请求报文中的时间戳同A的进程状态表中B的时间值进行比较。若B的请求报文中的时间戳大于A的进程状态表中B的时间值,则A修改自己的进程状态表。将A的进程状态表中对应于B的一栏改为请求状态,并记录此状态的时间。

(4) 退出临界区时,进程A退出临界区后,将自己的进程状态表中关于自己的一栏改为非请求状态,时钟值加1,并将该时钟值作为该状态的时间。然后检查其进程状态表中是否记录有某个进程处于请求状态,若有,则从处于请求状态的进程中选取一个请求最早的进程B(具有最小的时间戳),将令牌传送给它,并在令牌中附上A的进程状态表。

(5) 收到令牌时,收到令牌的进程把随令牌传来的进程状态表和自己的进程状态表进行比较。若随令牌传来的进程状态表中某进程的时间戳大于自己的进程状态表中相应进程的时间戳,则将自己的进程状态表中相应进程的状态和时间戳改成随令牌传来的进程状态表中相应的状态和时间戳。

在该算法中,当进程不持有令牌时算法需要交换n个报文,其中的n-1个为请求报文,一个用于传送令牌。而当请求进入临界区的进程持有令牌时,互斥算法显然不需要交换报文。

3结束语

通过研究生“分布式操作系统”和本科生“操作系统”的教学实践表明,在教学过程中通过这样的比较教学容易引起学生的兴趣,从而能够激发学生的学习热情和对问题的较为深入的思考,收到了较好的教学效果。

参考文献:

[1] 徐高潮,胡亮,鞠九滨. 分布计算系统[M]. 北京:高等教育出版社,2004.

[2] 张尧学,史美林,张高. 计算机操作系统教程[M]. 3版. 北京:清华大学出版社,2006.

[3] 庞丽萍. 操作系统原理[M].3版.武汉:华中科技大学出版社,2000.

[4] Andrew S. Tanenbaum. Distributed Operating Systems[M]. 陆丽娜,伍卫国,刘隆国,等译. 北京:电子工业出版社,1999.

[5] 汤子氵赢,哲凤屏,汤小丹. 计算机操作系统教程(修订版)[M]. 西安:西安电子科技大学出版社,2001.

[6] 任满杰,刘树刚,李军红.操作系统原理实用教程[M].北京:电子工业出版社,2006.

[7] Andrew S. Tanenbaum,Albert S. Woodhull. Operating Systems Design and Implementation[M]. 2nd ed. Upper Saddle River,NJ. Prentice- Hall International,Inc. 1996.

[8] Lamport L. Time,clock,and the order of events in a distributed system[J]. Communications of the ACM,July 1978,21(7):558-568.