资源描述：
《分布式系统_读者_与_写者_并发控制算法_廖先湜new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1息55年小型微型计算机系统第9卷第7期“”·“”分布式系统读者与写者并发控制算法廖先堤吕东明,(清华大学韭京)“读者”与“写者”。摘要本文叙述了分布式计算机系统并发控制算法也就,,是衬多个分布式独立进程并发访问13界区实现读读并行读写互斥写写互斥的。一调度其法本算法的MODULA2语言程序在THUDS分布式双机实验系统上调试结。果良好己l.套J.‘二“,“”,分布式系统共享文件的读者与写者并发控制是一个资源调度问题〔1〕即是对。多个分布式独立进程同时访问临界区进行管理这些分布于各个结点的独立进程可以划分戊“”“
2、”。,,读者和写者两大类为了保证文件的完整一致性读者可以多个进程共享临界区,。,。而读者写者之间以及写者之间必须互斥访问优先权问题存在两种解决办法〔幻一是,。给读者最小的等待延迟另一个是写优先于读〔2〕分布式计算机系统的文件管理给写进提,。。优先权允许读队列等待到全部写队列修改完成这样读者总是得到当前最新的信息如果,虽,是请求修改拷贝到几个结点中的多拷贝文件然本结点已经调度到此修改进程但是还必,,。须与各拷贝文件所在点按照分布式同步算法相互协商批准后才能进行修改〔35〕二、算法。。S是一般信号量表示文件当前状态S
3、=一1l个写进程使用临界区。S=0临界区空闲S=11个读进程占用临界区S二22个读进程并行占用临界区k=1本文件是多拷贝文件WTeount写队列记数RDeount读队列记数GOTOZXM转多拷贝文件协商处理模块.中国科学院科学基金资助的课题19。肠.本文“年3月收到GoToWritjng转完成写处理模块GoTOReading转完成并行读处理模块一。下面叙述的算法是用类PASCAL(PAsCALlike)语言书写的m‘phores,(init丫压1.e=o)Se诫or一m.ph,r,n‘Ya“e=1)BiarSe浓
4、W不iiti1lcount,cou,(inalv二o)CARDINALWTRDntitialueREADERP(r,)二0THENINCRDeount(写进权占川临界区,IFW排入读等待队列)s:二s+1,ELSEangGOTORedi,ENDvr),(Readiog15f声orm记(完成并行读棋块)P(r),,:二s一1,IFs=0ANDeount>0AND二0THENs:=s一i,WTWeoont,DECWT=一IFkTHE双GOTOZXMrn‘ELSEGOTOWiti,END.END丫r,()WRITERP
5、(r.)IF二1THEN:=一l,WWW二0THENs:二s一l-IFSIFk二1TllENGOTOZXMngEL邓GOTOW心i.ENDcELSEINCWTount(读进程占用临界区的排入写等待队列)eount(写进程占用临界区,ELSEINCWT排入写等待队列),ENDr,V()rng15perWitifor以d(完成写处理棋块)r),P(IFTcount>0ANDS二一1AND二0THENDECcount-WWWTIFK二1THEN.GOTOZXMrngELSEGOTOWiti,END.二+l,ELSEWW
6、5.二S+l,IF二1ANDS二0ANDRDcount>oWTHENREPEATeount,DECRD5.二S+一,目91GOTOReadiUNTILRDeo一:nt=o,END.ENDr),V(:上述算法表明.二,=,Teoun,ent=o,。2如果wzsowt=oRnou表示文件空闲.=0,=一,RDu=,c=,。2如果ws1contowTount。表示有一个写进程正在修改。,c,此后到达的读写进程均排入相应的等待队列中如果此写进程释放临界区而wTount>。c,=,=o,。RDount>。则互斥处理写队列直
7、到w1s时才进行整个读队列并行占用临界区.,,。3如果w=1wTcount=0则先后申请的x个读进程并行的占有临界区一旦有写,,=,unt,二o。进程到达则w二。sxwTco>。RDcount此后到达的读写进程全部排入相。应队列等待处理:二、断‘叼j育l二J一。匀1算法的并行性。并行性是多个读进程同时占用临界区:。断言算法实现了读进程并行占用临界区:写,=1,s=证明进程占用临界区前到达的全部读进程都可并行使用临界区此时w,。。x,wTcOUnt=。RDcount二0算法实现了读进程并行占用临界区。32算法的互斥
8、性。互斥性是读写进程或写写进程不能同时占用临界区、·断言:写写互斥。算法实现了读写互斥:证明,,。1)如果读进程占用临界区则s>。申请临界区的任何写进程都排入等待队列实。现了读写互斥2)如果有一个写进程占用临界区,则W=一。,任何申请互斥区的读写进程均排入相应。。的等待队列算法实现了写写互斥。33写优先于读,。写优先于读是读写二个等待队列均大于零时优先调度写队列。断言:算
