[精选]分布式系统与WEB服务(2)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京理工大学计算机学院,分布式系统与,WEB,服务,第,三,三,章,章,分,分,布,布,式,式,系,系,统,统,的,的,同,同,步,步,和,和,进,进,程,程,3,1,时,钟,钟,同,同,步,步,分,布,布,式,式,算,算,法,法,的,的,主,主,要,要,特,特,征,征,：,：,相,相,关,关,信,信,息,息,分,分,布,布,在,在,多,多,台,台,机,机,器,器,上,上,进,进,程,程,仅,仅,依,依,据,据,局,局,部,部,的,的,信,信,息,息,作,作,出,出,决,决,定,定,一,一,台,台,机,机,器,器,的,的,故,故,障,障,不,不,应,应,引,引,起,起,整,整,个,个,系,系,统,统,的,的,失,失,败,败,没,没,有,有,共,共,用,用,的,的,全,全,局,局,时,时,钟,钟,。,。,1,逻辑,时,时钟,先看一,个,个例子,:,0,6,12,18,24,30,36,42,48,54,60,0,8,16,24,32,40,48,56,64,72,80,0,10,20,30,40,50,60,70,80,90,100,A,B,C,D,三个有,自,自己时,钟,钟的进,程,程,时钟不,同,同,运行的,结,结果是,消,消息,C,在时间,60,上被发,送,送,却在时,间,间点,54,上到达,Lamport,的算法,以,以,”,先于,”,关系为基,础,础，,每,每个,消,消息,都,都携,带,带它,的,的发,送,送时,间,间,当它,到,到达,目,目的,地,地时,，,，如,果,果目,的,的地,的,的时,间,间早,于,于它,的,的发,送,送时,间,间，,那,那么,就,就把,目,目的,地,地的,时,时间,向,向前,拔,拔,至少,要,要比,发,发送,时,时间,大,大,1,个单,位,位,.,0,6,12,18,24,30,36,42,48,70,76,0,8,16,24,32,40,48,61,69,77,85,80,0,10,20,30,40,50,60,70,80,90,100,A,B,C,D,用,Lamport,的算,法,法纠,正,正时,钟,钟,该算,法,法解,决,决了,全,全局,时,时钟,问,问题,，,，它,的,的条,件,件就,是,是两,个,个相,关,关事,件,件之,间,间必,须,须至,少,少相,差,差一,个,个时,间,间,2,时,钟,钟同,步,步算,法,法,逻辑,时,时钟,只,只给,出,出事,物,物的,相,相对,时,时间,与真,实,实时,间,间并,不,不对,应,应,故要,引,引入,外,外部,物,物理,时,时钟,常用,的,的时,钟,钟同,步,步算,法,法,:,克里,司,司帝,安,安,(CRISTIAN),算法,具有,国,国家,标,标致,时,时间,接,接收,器,器的,机,机器,注意,:,调整,的,的方,法,法,通过,调,调节,单,单位,时,时间,内,内的,中,中断,的,的时,间,间,来逐,步,步完,成,成时,钟,钟的,调,调整,.,伯克,利,利算,法,法,计算,平,平均,时,时间,它是,一,一个,集,集中,式,式算,法,法,不能,在,在大,规,规模,的,的分,布,布式,系,系统,中,中使,用,用,原理,:,定期,轮,轮询,每,每台,机,机器,的,的时,间,间,由结,果,果计,算,算平,均,均时,间,间,各机,器,器依,此,此调,整,整时,间,间,.,3,同,步,步时,钟,钟的,具,具体,使,使用,至,至多,一,一次,消,消息,传,传送,消息的时,间,间戳比存,储,储的时间,戳,戳的值早,就拒绝接,受,受该消息,基于时钟,的,的缓冲存,储,储器（,CACHE,）的一致,性,性,使用,CACHE,会出现一,致,致性问题,，,，原解决,的,的方法,:,区分读写,缓,缓存,现在可用,同,同步时钟,来,来解决。,即,即通过提,供,供有效期,（,（利用有效,的,的租约）来控制,CACHE,一致性问,题,题。,3.2,互斥操作,有多个进,程,程的系统,经,经常会碰,到,到临界区,的,的操作。,当,当一个进,程,程要访问,某,某个共享,数,数据时，,它,它要先进,人,人临界区,进,进行互斥,操,操作，确,保,保没有别,的,的进程同,时,时访问该,数,数据。在,单,单机系统,中,中，临界,区,区可以用,信,信号灯、,管,管程来实,现,现。那么,在,在分布式,系,系统中，,由,由于不能共享,主,主存，,怎,怎,么,么,实,实,现,现,临,临,界,界,区,区,和,和,互,互,斥,斥,操,操,作,作,呢,呢,?,下,面,面,我,我,们,们,讨,讨,论,论,几,几,种,种,算,算,法,法,。,。,集,集,中,中,式,式,算,算,法,法,该,方,方,法,法,就,就,是,是,模,模,拟,拟,单,单,机,机,系,系,统,统,指,定,定,一,一,个,个,管,管,理,理,员,员,进,进,行,行,许,许,可,可,管,管,理,理,该,算,算,法,法,保,保,证,证,了,了,互,互,斥,斥,每,个,个,临,临,界,界,区,区,只,只,需,需,三,三,条,条,消,消,息,息,(,申,请,请,许,可,可,释,放,放,),1,0,2,OK,请,求,求,C,管,理,理,员,员,队,列,列,空,空,管,理,理,员,员,1,0,2,不,回,回,答,答,请,求,求,C,队,列,列,空,空,1,0,2,OK,释,放,放,C,管,理,理,员,员,队,列,列,空,空,2,(A),进,程,程,1,向,管,管,理,理,员,员,请,请,求,求,进,进,入,入,临,临,界,界,区,区,得,到,到,许,许,可,可,(B),进,程,程,2,向,管,管,理,理,员,员,请,请,求,求,进,进,入,入,临,临,界,界,区,区,管,理,理,员,员,不,不,回,回,答,答,(C),进,程,程,2,向,管,管,理,理,员,员,请,请,求,求,进,进,入,入,临,临,界,界,区,区,管,理,理,员,员,许,许,可,可,缺,点,点,:,集,中,中,式,式,算,算,法,法,管,管,理,理,员,员,是,是,系,系,统,统,的,的,瓶,瓶,颈,颈,分,布,布,式,式,算,算,法,法,算,法,法,的,的,条,条,件,件,:,系,统,统,中,中,的,的,事,事,件,件,必,必,须,须,有,有,全,全,局,局,的,的,顺,顺,序,序,算,法,法,的,的,工,工,作,作,过,过,程,程,如,如,下,下,:,当,一,一,个,个,进,进,程,程,要,要,进,进,入,入,临,临,界,界,区,区,时,时,，,，,它,它,构,构,造,造,一,一,条,条,包,包,括,括,临,临,界,界,区,区,名,名,、,、,进,进,程,程,号,号,和,和,当,当,前,前,时,时,间,间,的,的,请,请,求,求,消,消,息,息,，,，,然,然,后,后,把,把,该,该,消,消,息,息,广,广,播,播,给,给,其,其,他,他,的,的,所,所,有,有,进,进,程,程,。,。,这,这,里,里,假,假,设,设,，,，,消,消,息,息,的,的,发,发,送,送,是,是,可,可,靠,靠,的,的,。,。,当,一,一,个,个,进,进,程,程,收,收,到,到,请,请,求,求,后,后,，,，,根,根,据,据,它,它,的,的,状,状,态,态,采,采,取,取,相,相,应,应,的,的,动,动,作,作,：,：,(1),当接,收,收者,不,不在,临,临界,区,区，,并,并且,也,也不,想,想进,入,入临,界,界区,，,，就,应,应答,发,发送,者,者,OK,消息,。,。,(2),如果接,收,收者已,经,经在临,界,界区中,，,，它不,回,回答,仅,仅仅把,请,请求加,入,入队列,。,。,(3),如果接,收,收者不,在,在临界,区,区，但,它,它也想,进,进入临,界,界区，,就,就要将,收,收到消,息,息的时,间,间戳和,它,它广播,消,消息的,时,时间戳,比,比较,.,如果到,来,来的消,息,息时间,戳,戳早，,接,接收者,回,回答发,送,送者,OK,消息；,反,反之接,收,收者把,到,到来的,请,请求加,入,入队列,，,，不回,答,答,.,在发完,进,进入临,界,界区请,求,求后，,进,进程将,等,等待所,有,有的允,许,许消息,，,，一旦,得,得到许,可,可，就,可,可进入,临,临界区,，,，当退,出,出时向,队,队列中,的,的所有,进,进程发,OK,消息，,并,并将它,从,从队列,中,中删除,。,。,所有进,程,程都要,参,参与决,定,定是否,进,进入临,界,界区，,若,若有进,程,程不能,做,做，算,法,法将出,错,错。,由于所,有,有进程,都,都要参,加,加算法,，,，所以,比,比集中,式,式算法,慢,慢，复,杂,杂，开,销,销大。,改进算,法,法：不需所,有,有进程,同,同意，,部,部分回,答,答,OK,即可,令牌环,算,算法,进程只,有,有拥有,令,令牌时,才能进,入,入临界,区,区,一个进,程,程从相,邻,邻的进,程,程收到,令,令牌时,先,先检查,自,自己是,非,非要进,入,入临界,区,区,;,如果要,就进入,否则就,将,将令牌,传,传递给,下,下一个,进,进程,.,缺点,:,令牌可,能,能丢失,且,且检测,困,困难，,一,一个要,进,进入临,界,界区的,进,进程最,差,差情况,下,下要等,待,待其他,进,进程进,入,入和退,出,出临界,区,区所用,时,时间总,和,和,三种算,法,法的特,点,点比较,集中式,算,算法简,单,单、高,效,效，每,次,次进入,和,和离开,临,临界区,只,只需,3,次消息,传,传递：请求、,许,许可；,释,释放，分布,式,式算法,中,中，,n,个进程,需,需要,(n-1),个请求,和,和,(n-1),个许可,，,，总共,要,要,2(n,1),个消息,。,。在令,牌,牌环算,法,法中，,所,所需的,消,消息数,是,是不固,定,定的。,如,如果每,个,个进程,都,都要进,入,入临界,区,区，那,么,么每个,令,令牌都,有,有一次,进,进人和,退,退出，,平,平均每,次,次进入,有,有,个消息,传,传递；,如,如果令,牌,牌被一,个,个进程,占,占有很,长,长时间,，,，那么,进,进入临,界,界区需,要,要的消,息,息就不,确,确定。,进程从,它,它发出,进,进入临,界,界区的,请,请求到,它,它进入,临,临界区,的,的时间,延,延迟在,三,三个算,法,法中是,不,不同的,当临界,区,区很短,并,并且使,用,用频率,很,很低时,，,，进入,临,临界区,时,时间延,迟,迟的决,定,定因素,是,是进人,临,临界区,的,的控制,机,机制,当,当临界,区,区很长,并,并且使,用,用的频,率,率很高,时,时，决,定,定因素,在,在于等,待,待时间,，,，消息,数,数就能,说,说明这,一,一点。,这三种,算,算法出,现,现故障,时,时,都会有,很,很大影,响,响,要避免,系,系统的,崩,崩溃,须注意,:,在容错,系,系统中,次三种,算,算法都,不,不适用,.,3.3,选举算,法,法,在分布,式,式系统,中,中，大,多,多数算,法,法要求,有,有一个,进,进程充,当,当管理,员,员或初,始,始启动,者,者等特,殊,殊角色,。,。前面,几,几个算,法,法就有,这,这样的,例,例子。,一,一般来,说,说，由,哪,哪个进,程,程充当,特,特定角,色,色无关,紧,紧要，,但,但是必,须,须有一,个,个进程,做,做这个,工,工作。,下,下面我,们,们来看,如,如何选,一,一个进,程,程担当,特,特定角,色,色。,选举算,法,法的目,的,的是当,选,选举完,成,成后，,能,能够让,所,所有的,进,进程知,道,道谁是,管,管理员,.,1.,霸道算法,该算法提出,。,。当一个进,程,程,P,注意到管理,员,员不再对请,求,求作出反应,时,时，它就开,始,始选举进,程,程,P,执行下列步,骤,骤：,(1),向,所,所,有,有进,程,程,号,号,比,比,它,它,大,大的,进,进,程,程,发,发,送,送,ELECTION,消,息,息,；,；,(2),如,果,果,没,没,有,有,进,进,程,程,响,响,应,应,，,，,进,进,程,程,P,成为,管,管理,员,员；,(3),如果,有,有进,程,程响,应,应，,该,该响,应,应进,程,程成,为,为管,理,理员,，,，,P,结束,选,选举,。,。,注意,：,：一个,进,进程,只,只能,从,从号,码,码比,它,它小,的,的进,程,程处,得,得到,一,一个,选,选择,消,消息,2,0,5,3,6,4,1,7,(A),进程,4,启动选举,2,0,5,3,6,4,1,7,(B),进程,5,6,响应,让,4,停止,2,0,5,3,6,4,1,7,(C),进程,5,6,都启,动,动选,举,举,2,0,5,3,6,4,1,7,(D),进程,6,让进,程,程,5,停止,选,选举,2,0,5,3,6,4,1,7,(E),进程,6,成为,管,管理,员,员,发通,知,知,霸道,算,算法,图,图示,2.,环形,算,算法,这个,算,算法,使,使用,环,环，,但,但不,是,是令,牌,牌环,。,。这里假,定,定所有,的,的进程,都,都是有,序,序号的,，,，即每,个,个进程,都,都知道,它,它的后,继,继进程,。,。当一,个,个进程,发,发现管,理,理员不,能,能工作,时,时，它,把,把包含,其,其进程,号,号的,ELECTION,消息发,给,给它的,后,后继进,程,程；接,收,收消息,的,的进程,再,再向后,继,继进程,发,发送,ELECTION,消息。如果,接,接收进程没,有,有反应，发,送,送消息的进,程,程便向下一,个,个进程发消,息,息。每一次,发,发送,ELECTION,，进程都要,将,将自己的进,程,程号加入消,息,息。,2,0,4,6,5,1,3,7,使用环形选,举,举算法,选举消息,选举消息,2,3,2,5,5,6,5,6,0,出现故障的,管,管理员,最后，第一,个,个发出该选,举,举（,ELECTION,）消息进程,收,收到该消息,再将其转换,为,为协调（,COORDINATOR,）消息后，,再,再循环一周,通知谁是管,理,理员，谁是,组,组成员，这时消息包,中,中进程号最,高,高的进程将,成,成为管理员,。,。当这个消息,循,循环一周后,，,，由发送进,程,程把它从网,上,上清除。,图中,2,和,5,都发现,7,失效，分别,建,建立选举消,息,息，两条消,息,息都沿环运,行,行，结果是,一,一样的，只,是,是浪费了带,宽,宽。,3,4,线程,进程因等待,而,而挂起,使进程中可,并,并行部分不,能,能执行,从而使系统,性,性能下降,故引入,-,线程,.,1.,线程：就是,可,可以共享地,址,址空间的轻,型,型进程，它,有,有自己的程,序,序寄记数器,栈,栈和寄存器,集,集合。它与进程的,主,主要区别是,它,它的地址空,间,间是共享的,。,。,线程相对于,进,进程，犹如,进,进程相对于,机,机器,2.,线程的使用,，,，将并行性,引,引入到顺序,执,执行的系统,.,多线程组织,的,的常用模型,：,：,1),分配器工,作,作者模型,有一个分配,器,器线程唤醒,工,工作者线程,可,可用信号灯,2),团队模型,地位平等,线,线程各自获,取,取和处理自,己,己的请求,.,3),流水线模型,管道线模型,，,，第一个线,程,程产生一些,数,数据传给下,一,一个线程处,理,理，且持续,下,下去。,多线程可分,时,时工作在单,CPU,上也可工作,在,在多处理器,系,系统上,而且多线程,系,系统设计的,好,好将可与多,处,处理机工作,性,性能相当,.,共享缓冲区,到达的工作请求,邮箱,文件服务器进程,分配器线程,工作者线程,到达的工作请求,到达的工作请求,内核,分配器,/,工作者模型,流水线模型,团体模型,进程中线程三种组织方式,3.,线程包的设,计,计的相关问,题,题,线程包就是,供,供用户或程,序,序员调用的,关,关于线程的,一,一组原语。,线程的管理,方,方法有静态,和,和动态方法,两,两种。,静态即开始就确,定,定好线程的,个,个数，动态个数不定,线程的代码,与,与进程一样,，,，由多个过,程,程组成。,线程包中临,界,界区控制利,用,用互斥体（,mutex),其总处于：,打开和锁住,两,两种状态,lockmutex;,checkdatastructureslockmutex,while(resourcebusy)mark resource asfree;,wait(condition varable);unlockmutex;,markresource asbusy;wakeuo (condition variable);,unlock mutex;,互斥变量,与,与条件变,量,量的使用,线程可由,算,算法进行,调,调度，如,优,优先级调,度,度、循环,调,调度等,4.,线程包的,实,实现,在用户空,间,间实现线,程,程（如图,）,）,这种方法,是,是将线程,包,包完全放,在,在用户空间，内核对,此,此一无所,知,知，在这,种,种方法中,，,，内核只,是,是管理普,通,通的单线,程,程进程。,这,这种方法,最,最明显的,优,优点是,它,它,可,可,以,以,在,在,一,一,个,个,不,不,支,支,持,持,多,多,线,线,程,程,的,的,操,操,作,作,系,系,统,统,上,上,实,实,现,现,用,用,户,户,线,线,程,程,包,包,。,。,同,同,时,时,它,它,还,还,允,允,许,许,每,每,个,个,进,进,程,程,有,有,自,自,己,己,特,特,定,定,的,的,调,调,度,度,算,算,线,程,1,线,程,2,线,程,3,线,程,4,线,程,5,线,程,6,运行期系统,内 核,内,核,核,空,空,间,间,用,户,户,空,空,间,间,缺,点,点,是,是,：,：,数,量,量,太,太,多,多,会,会,引,引,起,起,资,资,源,源,紧,紧,张,张,.,同,时,时,(1),它,也,也,难,难,实,实,现,现,阻,阻,塞,塞,系,系,统,统,的,的,调,调,用,用,.,(2),它,的,的,调,调,度,度,是,是,非,非,抢,抢,先,先,式,式,的,的,.,进,程,程,内,内,部,部,无,无,时,时,钟,钟,中,中,断,断,无,法,法,进,进,行,行,时,时,间,间,片,片,的,的,调,调,度,度,.,2),在,操,操,作,作,系,系,统,统,内,内,核,核,实,实,现,现,（,（,如,如,图,图,）,）,不,需,需,要,要,运,运,行,行,系,系,统,统,线,程,程,创,创,建,建,或,或,撤,撤,销,销,只,需,需,一,一,次,次,系,系,统,统,调,调,用,用,比,在,在,用,用,户,户,空,空,间,间,实,实,现,现,线,线,程,程,开,开,销,销,大,大,.,可,通,通,过,过,在,在,撤,撤,销,销,时,时,加,加,标,标,记,记,，,，,当,当,做,做,为,为,新,新,线,线,程,程,创,创,建,建,时,时,仅,仅,需,需,激,激,活,活,即,即,可,可,。,。,线,程,1,线,程,2,线,程,3,线,程,4,线,程,5,线,程,6,内 核,用,户,户,空,空,间,间,内,核,核,空,空,间,间,3),调,度,度,员,员,活,活,动,动,方,方,法,法,结,合,合,前,前,两,两,种,种,的,的,优,优,点,点,(,用,户,户,线,线,程,程,的,的,高,高,性,性,能,能,和,和,内,内,核,核,线,线,程,程,的,的,实,实,现,现,简,简,单,单,),原,理,理,：,：,当,当,使,使,用,用,调,调,度,度,员,员,活,活,动,动,方,方,法,法,时,时,，,，,内,内,核,核,给,给,每,每,个,个,进,进,分,分,配,配,一,一,些,些,“,虚,处,处,理,理,器,器,”,，,并,并,由,由,运,运,行,行,系,系,统,统,分,分,给,给,线,线,程,程,，,，,同,同,时,时,通,通,过,过,避,避,免,免,在,在,用,用,户,户,空,空,间,间,和,和,内,内,核,核,空,空,间,间,之,之,间,间,的,的,不,不,必,必,要,要,的,的,转,转,换,换,来,来,实,实,现,现高效率。如：线程在局部,信,信号上阻塞,并,并不去涉及,内,内核，而是,由,由用户运行,期,期系统去完,成,成阻塞和调,度,度。具体是由内核激活用,户,户运行期系,统,统,4),线程和,RPC,希望使一个,进,进程中的线,程,程可以有效,的,的调用同一,台,台机器上的,另,另一个进程,中,中的线程,，,具体采用与,RPC,相似的过程,完,完成。,加速,RPC,执行的技术,，,，具体即为当一个线程,执,执行请求时,，,，它将消失,并,并且它的堆,栈,栈和环境信,息,息也丢弃，,当,当有新的消,息,息进入时，,内,内核动态创,建,建一个新线,程,程去为其服,务,务。优点首先线,程,程不用等待,所,所以不保留,环,环境，其次,创,创建新线程,比,比存储一个,存,存在的线程,花,花费少，节,约,约了时间减,少,少了开销，,从,从而提高了,速,速度。,3,5,分布式系统,模,模型,1,工作站模,型,型,其主要指：,一,一组工作站,通,通过高速局,域,域网互连，,在,在某一时刻,每台,机,机器,只,只有,一,一个,用,用户,登,登录,，,，即,拥,拥有,者,者，,要,要么,空,空闲,。,。,优点,：,：清晰,、,、易,于,于理,解,解，,计,计算,能,能力,固,固定,、,、系,统,统反,应,应时,间,间固,定,定、,有,有一,定,定的,自,自主,性,性、,同,同时,增,增强,了,了独,立,立性,。,。缺,点,点,:,资源,存,存在,浪,浪费,资源,利,利用,率,率不,高,高,.,2.,空闲,工,工作,站,站的,使,使用,1,）找,出,出空,闲,闲工,作,作站,两种,定,定位,方,方式,：,：服,务,务器,驱,驱动,和,和客,户,户端,驱,驱动,2,）透,明,明运,行,行远,程,程进,程,程,由内,核,核完,成,成,3,）机,主,主人,重,重新,使,使用,时,时如,何,何处,理,理,直接杀死,进,进程、移,植,植到另一,台,台机器上,（,（进程全,部,部包括子,进,进程）,3.,处理机池,模,模型,处理机池,是,是无盘工,作,作站的进,一,一步发展,。,。理论依据,是,是排队论,具体有理,发,发师模型,、,、超市收,款,款等。,CPU,根据需求,动,动态的分,配,配给用户,。,。模型如,图,图,虽然有证,明,明：用一个,是,是小系统,功,功能,N,倍的大系,统,统来代替,N,个独立的,小,小系统的,资,资源可把,平,平均响应,时,时间减少,为,为原来的,1/N,倍。,文件服务器,处理机池,CPU,然而平均,响,响应时间,不,不代表一,切,切，从费用角,度,度来看，,不,不惜代价,建,建造巨型,机,机甚至是,不,不可能的,。,。,同时也并,不,不是有,N,个处理器,的,的处理机,池,池就可比,单,单个处理,器,器的性能,高,高,N,倍，而是决定,于,于任务可,分,分几部分,。,。,4.,混合模型,用那种模,型,型要依情,况,况而定,若是偶发,的,的事件为,主,主,则个人工,作,作站模型,机,机可,若是仿真,或,或工程计,算,算则用处,理,理机池较,好,好,也可两者,结,结合,.,3,6,处理机分,配,配与调度,如何决定,进,进程运行,在,在那台机,器,器上，即,为,为处理机,的,的分配。,1.,分配模型,1,）分配策,略,略有两大,类,类,:,非迁移的,（,（进程创,建,建后，一,直,直呆到进,程,程结束）,迁移的（,进,进程可在,运,运行中迁,移,移到其它,机,机器上运,行,行）,2,）分配算,法,法的目标,：,：,(1),最大限度,地,地提高,CPU,利用率,(2),尽可能缩,短,短平均响,应,应时间,(3),最小化响,应,应率,例如：,有两个处,理,理机,1,及,2,和 两个,进,进程,A,及,B,A,（,1,亿条指令,）,）,10,秒,6,秒,B,（,3,亿条指令,）,）,30,秒,8,秒,分配,1,：处理机,1,运行进程,A,，处理机,2,运行进程,B,，平均响,应,应时间为,（,（,10+8,）,/2=9,秒（较优）,分配,2,：处理机,2,运行进程,A,，处理机,1,运行进程,B,，平均响,应,应时间为,（,（,30+6,）,/2=18,秒,处理机,1,10MIPS,处理机,2,100MIPS,5,秒队列,2,设计分,配,配算法的,主,主要相关,问,问题,1,）确定式,还,还是启发,式,式,确定式适,用,用进程是,否,否可预知,;,启发是指,以,以经验性,规,规则和信,息,息指导,.,2,）集中式,还,还是分布,式,式,依全局信,息,息做判定,以局部信,息,息做判断,.,3,）最优的,还,还是次优,的,的,4,）局部的,还,还是全局,的,的,解决转移,策,策略,5,）发送者,初,初启还是,接,接收者初,启,启,解决定位,策,策略,3,处理机,分,分配算法,实,实现中的,问,问题,1,）对负载,的,的测量,2,）额外开,销,销的处理,3,）问题的,复,复杂度,4,）稳定性,问,问题,4,典型的,处,处理机分,配,配算法,1),图论决策,算,算法,2),集中式算,法,法（上,下算法）,3),层次算法逻辑上构,成,成分层结,构,构,4),投标算法把系统中,的,的资源和,任,任务作为,买,买方和卖,方,方以寻求,平,平衡,.,A,B,C,D,G,I,H,2,2,2,5,5,8,1,1,4,4,3,A,B,C,D,G,I,H,2,2,2,5,5,8,1,1,4,4,3,F,F,E,E,30,单位通信,量,量,28,单位通信,量,量,5,调度,假设进,程,程成组,创,创建,组间通,信,信比组,内,内通信,要,要少,基于,协同调,度,度,概念的,算,算法,.,算法使,用,用一个,矩,矩阵,列是处,理,理机的,进,进程表,行是时,间,间段的,进,进程表,主要思,想,想,:,每个处,理,理机采,用,用时间,片,片轮转,法,法,因此可将进,程,程组的所有,成,成员放在不,同,同处理机上,的,的同一时间,段,段,处理机,时间片,实现文件服,务,务的技术对,于,于分布式系,统,统的设计非常重,要,要。,在分布式系,统,统中，必须,提,提供与传统,文,文件系统相,当,当的性能和,可,可靠性。实,现,现分布式文,件,件服务器的,技,技术源自传统,系,系统，但,由,由于,要,要将,许,许多,设,设施,分,分布,在,在多,个,个不,同,同的,服,服务,器,器中,，,，系,统,统结,构,构有,所,所不,同,同，,因此,，,，其,技,技术,要,要求,及,及高,于,于传,统,统系,统,统。,共享,持久性,分布式,缓存,/,副本,维护,一致性,例子,主存,1,RAM,文件系统,1,UNIX,文件系统,分布式文件系统,SUN NFS,WEB,WEB,服务器,分布式共享内存,IVY,远程对象,1,CORBA,持久对象存储,1,CORBA,持久对象存储,持久分布式对象存储,PERDIS,第,四,章,分布,式,式文,件,件服,务,务,4,1,引言,文件,被,被认,为,为是,一,一个,基,基于,磁,磁盘,或,或其,它,它二,级,级存,储,储器,的,的存,储,储结,构,构的,抽,抽象,。,。最简,单,单情,况,况下,，,，文,件,件定,义,义为,数,数据,项,项的,序,序列,，,，文,件,件系,统,统提,供,供按,指,指定,位,位置,读,读,写,写文,件,件数,据,据项,或,或子,序,序列,的,的操,作,作。有些,文,文件,系,系统,将,将文,件,件定,义,义成,复,复杂,数,数据,结,结构,的,的集,合,合,(,如,记,记,录,录,等,等,),，,可,可,以,以,用,用,记,记,录,录,的,的,键,键,字,字,来,来,定,定,位,位,。,。,在,集,集,中,中,式,式,文,文,件,件,系,系,统,统,中,中,，,，,文,文,件,件,系,系,统,统,可,可,以,以,管,管,理,理,大,大,量,量,的,的,文,文,件,件,，,，,包,包,括,括,读,读,、,、,写,写,或,或,删,删,除,除,等,等,。,。,而,而,目,目,录,录,是,是,一,一,种,种,抽,抽,象,象,的,的,文,文,件,件,管,管,理,理,设,设,施,施,，,，,它,它,能,能,将,将,文,文,件,件,名,名,映,映,射,射,到,到,一,一,个,个文,件,件,指,指,针,针，这种,映,映射,(,即目录,),一般以,特,特殊类,型,型的文,件,件存储,，,，若要,访,访问文,件,件，需,要,要首先,打,打开目,录,录。,文件系,统,统要负,责,责文件,共,共享和,访,访问控,制,制的管,理,理，限,定,定用户,的,的访问,权,权限，,为,为每个,文,文件定,义,义访问,类,类型等,。,。,文件系,统,统一般,提,提供以,下,下服务,:,文件组,织,织,文,文,件,件存储,文件检,索,索,文,文,件,件命名,文件共,享,享,文,文,件,件保护,。,。,设计文,件,件系统,的,的目的,，,，是使,程,程序员,可,可以使,用,用抽象,操,操作来,访,访问磁,盘,盘空间,，,，传统文,件,件系统,的,的层次,结,结构如,下,下图所,示,示：,文件系,统,统模块,图,图,以上也,同,同样是,分,分布式,文,文件系,统,统的基,础,础,.,目录模,块,块,:,负责文,件,件名到,文,文件标,识,识的映,射,射,文件模,块,块,:,负责文,件,件标识,到,到文件,的,的映射,文件访,问,问,:,文件数,据,据、属,性,性的读,写,写,访问控,制,制,:,操作的,许,许可性,检,检查,盘块模,块,块,:,磁盘块,的,的分配,及,及访问,设备模,块,块,:,磁盘,I/O,缓冲,另外加,上,上,:,1.,支持共,享,享信息,的,的管理,不必先,拷,拷贝，,再,再访问,，,，永久,性,性数据,管,管理,2.,为用户,提,提供透,明,明的文,件,件访问,服,服务,3.,提供目,录,录服务,提供文,件,件命名,及,及文件,名,名到文,件,件标识,的,的映射,功,功能,4.,事务服,务,务,为用户,提,提供的,最,最高层,服,服务,提供并,发,发服务,保证文,件,件的一,致,致性,综合而,言,言,分布式,文,文件可,分,分为三,种,种服务,:,目录服,务,务,文件服,务,务,事务服,务,务,用户程序,用户程序,用户程序,客户模块,网络,文件服务,目录服务,事物服务,文件服务的,RPC,界面,用户程序界面,API,目录服务的,RPC,界面,事物服务的,RPC,界面,4.2,文件服,务,务,在,UNlX,和,DOS,系统中,，,，文件是,没,没有任,何,何解释,的,的字节,序,序列，,文,文件的,结,结构和,意,意义完,全,全由应,用,用程序,决,决定，,操,操作系,统,统不关,心,心其结,构,构和意,义,义。但在某,些,些大型,机,机的操,作,作系统,中,中，有,许,许多不,同,同类型,的,的文件,，,，每种,文,文件具,有,有不同,的,的特性,。,。,文件可,以,以是一,组,组记录,构,构成的,序,序列，该记录,又,又可以,是,是复杂,的,的结构,，,，这个,结,结构的,意,意义是,由,由操作,系,系统解,释,释的。这样，,文,文件便,由,由数据,和,和属性,构,构成，,其,其中，,属,属性包,括,括文件,长,长度、,访,访问时,间,间、访,问,问控制,表,表和拥,有,有者，,文,文件长,度,度和数,据,据可为,用,用户使,用,用，其,它,它属性,均,均为目,录,录服务,使,使用，,可,可以将,这,这种文,件,件看作,一,一种文,件,件对象,。,。,关于,文,文件,的,的另,一,一个,重,重要,问,问题,是,是文,件,件的,可,可修,改,改性,。,。如果,文,文件,创,创建,之,之后,，,，不,能,能再,修,修改,，,，则,称,称为,不,不可,修,修改,(Immutable),文件,，,，否,则,则称,为,为可,修,修改,(Mutable),文件,。,。这里,主,主要,讨,讨论,可,可修,改,改的,文,文件,。,。,4.2.1,文件,服,服务,的,的模,型,型和,任,任务,对于,一,一般,的,的文,件,件服,务,务而,言,言，,有,有两,种,种服,务,务模,型,型,1),装载,卸,载,载,(UpLoad,DownLoad),模型,2),远程,访,访问,(RemoteAccess),模型,在装,载,载,卸,卸载,模,模型,中,中，文件,服,服务,仅,仅提,供,供读,文,文件,和,和写,文,文件,两,两种,操,操作。,读操,作,作用,于,于将,整,整个,文,文件,从,从服,务,务器,中,中完,全,全读,出,出，,写,写操,作,作用,于,于将,整,整个,文,文件,从,从客,户,户机,写,写入,服,服务,器,器。,在,在这,种,种模,型,型下,，,，可,以,以将,文,文件,缓,缓冲,于,于客,户,户机,的,的主,存,存或,磁,磁盘,中,中，,其,其优,点,点是,概,概念,简,简单,，,，应,用,用程,序,序可,以,以局,部,部拥,有,有并,访,访问,文,文件,，,，程,序,序结,束,束后,，,，必,须,须将,新,新建,或,或修,改,改过,的,的文,件,件写,回,回服,务,务器,。,。在,此,此，不需,要,要复,杂,杂的,文,文件,服,服务,界,界面,，,，整,个,个文,件,件的,传,传输,是,是高,效,效的。但是，,客,客户机必,须,须有足够,的,的空间来,存,存储所需,要,要的文件,，,，另外，如果实际,上,上应用程,序,序作用于,文,文件的一,小,小部分，,就,就会造成,很,很大的浪,费,费。,在远程访,问,问模型中,，,，文件服务,将,将提供大,量,量的文件,操,操作，包,括,括打开、,关,关闭读和写等,，,，其优点,是,是不需要,客,客户机具,有,有大量空,间,间。另外，,当,当应用程,序,序只需处,理,理文件中,少,少量数据,时,时，不需,要,要将整个,文,文件全部,拷,拷贝到客,户,户机上去,。,。,文件服务,的,的任务,两个任务,：,：文件存,储,储和文件,寻,寻址。其中，文,件,件寻址利,用,用文件位,置,置映射方,法,法完成文,件,件的定位,，,，文件访,问,问通过调,用,用外存访,问,问功能完,成,成文件的,存,存储，外,存,存访问功,能,能通常以,块,块服务的,形,形式提供,。,。所以，,文,文件服务,的,的基本任,务,务就是，,提,提供通用,和,和有效的,操,操作集合,，,，为多个,客,客户提供,大,大容量的,外,外存设备,。,。,另外，文件服务,还,还要解决,保,保护问题，即严格,控,控制用户,对,对于文件,的,的访问，从而保证,文,文件的一,致,致性。文件服务,可,可以同时,支,支持多个,目,目录服务,，,，这样，,目,目录服务,可,可以采用,多,多种不同,语,语法，从,而,而使文件,服,服务可以,用,用于不同,的,的目录服,务,务。一个,文,文件服务,可,可能同时,管,管理几个,目,目录服务,支,支持的多,个,个文件集,合,合，每个,集,集合中的,文,文件属性,记,记录和结,构,构可能还,有,有差异。,4.2.2,文件服务,界,界面,所谓界面,，,，主要提,供,供服务的,基,基本操作,名,名和调用,格,格式及简,单,单功能描,述,述。,文件的,UFID,；参数,;,数据,;,出错信息,4. 3,目录服务,目录服务,定,定义了构,成,成文件,(,或目录,),名的某种,字,字母表示,语,语法。文件名可,以,以是由一,个,个或多个,字,字符、数,字,字及特殊,字,字符构成,的,的字符串,。,。有些系,统,统通过句,点,点将文件,名,名分成两,部,部分，如,prog,c,表示,C,语言文件，,maim,txt,表示文本文,牛,牛，第二部,分,分一般叫做,文,文件扩展名,。,。,分布式系统,目,目录一般也,都,都包含子目,录,录，从而使,用,用户可以给,相,相关文件：,分,分组，形成,层,层次文件系,统,统。因此，,目,目录服务就,包,包括创建、,删,删除、进入,、,、退出和查,找,找文件等功,能,能。有的系统,还,还提供建立,目,目录指针的,功,功能，指针,可,可以设置到,任,任何目录中,，,，这样构成的,目,目录和文件,就,就不再只是,树,树型结构，,而,而是图,(,网状,),结构，从而,使,使表示能力,更,更强，当然，管理,也,也就更复杂,。,。,设计分布式,文,文件服务的,关,关键在于，是否支持,所,所有机器对,于,于目录层次,具,具有同样的,视,视图。,4.3.1,目录服务的,任,任务,大多数分布,式,式系统都使,用,用两级命名方,式,式，即每个文,件,件,(,或其它对象,),都有一个符,号,号名,(,常称为文件,名,名,),和一个内部,二,二进制名,(,用,UFID,表示,),。符号名一般,供,供程序员或,用,用户使用，,如,如,prog.c,；内部二进,制,制名供系统,使,使用。所谓目录，,就,就是一组文,件,件名到,UFID,的映射表。,目,目录服务最,基,基本的任务,就,就是将文件,名,名映射到,UFID,，通过这一映,射,射可以取代,传,传统文件系,统,统中的打开,(Open),文件操作，,客,客户一旦拿,到,到,UFID,，便可以操,作,作文件,.,目录服务本,身,身要确保,UFID,正确送到请,求,求客户。目,录,录服务还要,检,检查客户的,合,合法性，通过访问控,制,制表做合法,性,性检查，最终决定,是,是否发出一,个,个,UFID.,目录服务的,功,功能也可以,分,分解为基本,功,功能和辅助,功,功能两类,基本功能提,供,供文件名到,文,文件标识的,映,映射，它是,构,构造面向用,户,户的目录服,务,务的基础，,包,包括名字、,结,结构和访问,控,控制方法。,根,根据授权客,户,户的请求允,许,许用户执行,UFID,所指出的文,件,件增、删操,作,作。辅助功,能,能包括文件,名,名的词法分,析,析、建立目,录,录形成层次,结,结构和其它,复,复杂操作。,因,因此，目录,服,服务可以在,给,给定目录中,查,查找文件名,，,，然后得到,UFIO,，每个,UFID,都指出对于,文,文件的相关,访,访问权限，,如,如对文件拥,有,有者可读、,写,写和删除，,对,对于其它用,户,户只读。,目,录,录,通,通,常,常,以,以,文,文,件,件,形,形,式,式,存,存,储,储,，,，,因,因,此,此,，,，,目,目,录,录,服,服,务,务,本,本,身,身,是,是,文,文,件,件,服,服,务,务,的,的,一,一,个,个,客,客,户,户,，,，,每,每,个,个,目,目,录,录,本,本,身,身,有,有,一,一,个,个,UFID,。,4.3.2,目录服,务,务界面,目录服,务,务定义,了,了一组,目,目录服,务,务操作,。,。不同,系,系统有,响,响应的,约,约定,.,目录服,务,务的定,义,义遵循,约,约定记,号,号。,4.3.3,文件属,性,性与目,录,录访问,目录服,务,务要进,行,行访问,控,控制，,可,可以通,过,过访问,和,和更新,文,文件属,性,性完成。如可,以,以在新,文,文件名,加,加入目,录,录时，,在,在文件,属,属性中,设,设置访,问,问许可,；,；提供,查,查看文,件,件属性,的,的操作,；,；还可,以,以提供,允,允许文,件,件拥有,者,者认定,或,或重设,其,其它用,户,户的许,可,可权限,、,、及将,所,所有权,转,转让给,其,其它用,户,户的操,作,作。,文件系,统,统除管,理,理数据,外,外，还,要,要管理,许,许多相,关,关信息，如创,建,建日期,、,、最后,访,访问日,期,期和最,后,后修改,日,日期、,文,文件类,型,型、文,件,件所属,目,目录和,访,访问控,制,制信息,等,等，我,们,们称这,些,些信息,为,为文件,属,属性。,文件系,统,统将文,件,件属性,作,作为一,组,组不可,分,分解的,数,数据，,文件属,性,性可以,执,执行读,写,写访问,，,，但没有,长,长度或,结,结构等,操,操作,目录服,务,务不但,要,要确定,属,属性中,的,的内部,结,结构和,所,所存数,据,据值，,还,还要负,责,责文件,属,属性的,访,访问，,包,包括读,取,取和修,改,改。如,改,改变访,问,问日期,、,、修改,文,文件所,属,属关系,和,和管理,访,访问控,制,制表等,。,。,目录存,储,储着所,有,有文件,的,的拥有,者,者，文,件,件拥有,者,者可以,对,对其文,件,件执行,所,所有操,作,作，如,创,创建、,读,读、写,和,和删除,等,等,问题是,让,让谁来,执,执行目,录,录服务,中,中的,LookUp,、,AddName,、,ReName,和,UnName,操作，,查,查看或,修,修改文,件,件属性,?,当用户,具,具有各,自,自独立,、,、分离,的,的目录,时,时，目,录,录的,UFID,可能认,定,定为一,种,种权能,，,，不需,要,要进一,步,步的访,问,问控制,；,；但是,要,要访问,共,共享目,录,录时，,则,则需要,访,访问控,制,制。一个简,单,单的解,决,决办法,是,是，让,目,目录拥,有,有者的,访,访问许,可,可模式,与,与文件,拥,拥有者,的,的访问,许,许可模,式,式取得,一,一致。,另外，,为,为用户,同,同时提,供,供文件,服,服务和,目,目录服,务,务操作,可,可以克,服,服文件,的,的丢失,问,问题。,对,对于文,件,件创建,，,，用户,通,通过创,建,建操作,指,指定的,文,文件名,和,和目录,名,名，然,后,后依靠,文,文件服,务,务,Create,操作和,目,目录服,务,务,AddName,操作完,成,成。对,于,于文件,删,删除，,通,通过删,除,除操作,指,指定一,个,个,UFID,和目录,名,名,4.3.4,树型结,构,构,在,UNIX,提供的,树,树型文,件,件系统,中,中，包,含,含组织,成,成树型,结,结构的,许,许多目,录,录，通,过,过链使,文,文件具,有,有多个,名,名字，,可,可以使,用,用基本,的,的文件,和,和目录,服,服务来,实,实现。树型结,构,构的目,录,录集合,可,可以通,过,过叶、,根,根和内,部,部结点,构,构成。,树,树根是,一,一个目,录,录，其,UFID,是共用,的,的。,树中任,何,何结点,或,或叶结,点,点就是,文,文件或,目,目录，可以通,过,过路径,名,名命名,文,文件或,目,目录，路径是,由,由多部,分,分组成,的,的表示,路,路径的,名,名字。根具有,特,特殊名,，,，并且,每,每个文,件,件或目,录,录都有,自,自己的,名,名字。,在树型,结,结构的,目,目录服,务,务中，,文,文件属,性,性应当,包,包括一,个,个类型,属,属性用,来,来区分,文,文件和,目,目录。这可用,于,于沿树,结,结构按,路,路径名,检,检索时,，,，保证,名,名字除,最,最后一,个,个名字,外,外一定,是,是一个,目,目录名,。,。当创,建,建文件,或,或目录,时,时，文,件,件属性,中,中要设,置,置适当,的,的数值,，,，包括,访,访问控,制,制表、,创,创建日,期,期等等,。,。目录,一,一旦创,建,建了，,可,可以使,用,用,AddName,操作将,它,它的名,字,字和,UFID,插入到,另,另一个,目,目录中,。,。,4.3.5,命名透,明,明,透明命,名,名与位,置,置透明,性,性相关,，,，其意,义,义是路,径,径名并,不,不表示,文,文件的,位,位置，如,serverl,dirl,dir2,x,并不说,明,明文件,x,一定处,于,于,server1,上。服,务,务器可,以,以随意,地,地迁移,和,和切换,，,，而路,径,径名则,保,保持不,变,变。这种系,统,统称为,位置透,明,明的系,统,统,。,但是，,假,假设文,件,件,x,非常之,大,大，其,空,空间的,确,确处于,serverl,上，再,假,假设在,server2,上也,有,有大,量,量的,空,空间,。,。系,统,统有,可,可能,自,自动,地,地将,文,文件,x,迁移,到,到,server2,上,但,但是,，,，当,路,路径,名,名中,第,第一,部,部分,是,是服,务,务器,的,的时,候,候，,系,系统,是,是不,能,能自,动,动将,文,文件,迁,迁移,走,走的,，,，即,使,使,diri,和,dir2,在两,个,个服,务,务器,上,上都,有,有也,不,不行,，,，因,为,为迁,移,移文,件,件将,把,把路,径,径名,serverl,dirl,dir2,x,改变为,server2,dirl,dir2,x,。,具有前一,路,路径名的,程,程序在路,径,径名改变,时,时,必须停下,来,来重新编,译,译。如果文件,可,可以迁移,，,，其命名,不,不必改变,，则称其,具,具有位置,独,独立性。将机器名,或,或服务器,名,名嵌入到,路,路径名中,的,的分布式,系,系统不是,位,位置独立,的,的，基于,远,远程安装,的,的系统也,不,不是位置,独,独立的，,因,因为将一,个,个文件从,一,一个文件,组,组,(,安装单位,),迁移到另,一,一个文件,组,组后，不,可,可能仍然,使,使用原来,的,的路径名,。,。,位置独立,性,性不易实,现,现，却是,分,分布式系,统,统追求的,目,目标。,通常，,在分布式,系,系统中有,三,三种普遍,的,的命名文,件,件和目录,的,的方法：,机器,+,路径命名,法,法，如,machine,path,或,machine,：,path,；,在本地,文,文件层次,结,结构中安,装,装远程文,件,件系统；,在所有,机,机器上表,现,现一致的,统,统一命名,空,空间。,前两种方,法,法容易实,现,现，特别,是,是在使用,没,没有特殊,设,设计分布,式,式服务的,系,系统中非,常,常有效。,第,第三种方,法,法非常难,于,于实现，,必,必须精心,设,设计，,但是，如,果,果要求分,布,布式系统,的,的表现像,集,集中式系,统,统一样，,则,则必须做,到,到这一点,。,。,4,4,文件服务,的,的实现,4.4.1,系统结构,要实现文,件,件服务器,，,，首要问,题,题是客户,机,机与服务,器,器是异构,的,的还是同,构,构的,?,第二个问,题,题是文件,服,服务和目,录,录服务的,结,结构如何,?,当然，对,这,这两个问,题,题还没有,定,定论的方,法,法。,一,.,同构型,异,异构型,有些系统,没,没有区分,客,客户机和,服,服务器。,所,所有的机,器,器都运行,相,相同