Ӧо
APPLICATION RESEARCH OF COMPUTERS
2000Vol.17No.2P.16-19



洢һģо
ơ޾
ժ Ҫ ˷ֲʽ洢ϵͳ(ģӣ)ͨýṹҳƣ˸ִ洢һģ͵ȷԻΪ˵ڷֲʽ±̵һЩص㡣󣬻߱˵Ĺߣģӣϵͳܵ⡣
ؼ ֲʽ洢 һģ ӳ
1 о
Ŀǰ缼ļ緢չռϵͳŷֲлķչǫ̈Эͬһ߼ϵͳ(ǵ)崦һֱǹоص㡣ΪﵽĿ꣬洢һԵоǻǱֲ֤ʽϵͳȷмЧʵĹؼ
2 ϵͳṹ
DSMϵͳ߱һͻ/ĽṹҰں˼ûģ飬ͼ1ʾУͻָʹDSMϵͳûӦó򣬵ȻڵڵϿжͻ̣Ϊֿ֧ͻ̷DSMϵͳĲṩһһû̬µDSM

ͼ1DSMϵͳͨýṹʾͼ
DSMϵͳҳṹͼ2ʾһҳȡزӳ䵽ûں˵ĵַռ估ɽSwapȫ̡

ͼ2DSMϵͳҳṹ
3 һģ
ν洢һģ(Memory Consistency Model)ʵϵͳӦóԱ֮һԼӦһĹڴϵͳӦɻȷĴ洢ʽ֮ƻԼĹ洢ʵȷԲܱ֤
ĳ洢һģͶԹ洢ϵͳжദķôƣӶӰ졣ֲʽ洢ϵͳ(DSM)һĿһͨĹվȺһķҳַռ䣬ʹڹվȺ֮гЧڳڵ֮ϵС򵥵ıУÿҳһȷĻУԱҳĲѯٶȵͬڶڴķٶȣԶ̻ҳѯΥź(SIGSEGV)⽫³뵽ϵͳ֮Уɲϵͳȱҳжϣϵͳ֮һϢԶ̻ҵҳ沢ȴԶ̻ҳ͹ػԶҳ֮ΥźŵָִܼС
ΪﵽĿ꣬ҪһڴϵͳDSMϵͳеҳʴϵ㴦ȡݲɱҪͬ
ǰDSMϵͳУĳֻҳڶϾиԿдҳ棬һ㶼һ(Owner)άһԣԶ̷ʱԶ̽㷢󲢴㴦ȡظÿдҳ档ͨ£һдҳ棬DSMϵͳֻһӦóԱȽϴʱֶÿһдҳֻάһĲԽصƿάĲܼܵƿЧӦִһµ⣬ڶ֮άݵһԣΪ⣬һԴ洢ģ͡˵նһԵҪǿ˳򣬿Ϊ¼ࡣ
3.1 ϸһģ(Strict Consistency)
ǶһҪϸһģͣκζڴλXĶλXдֵ
DSMϵͳУһģͣӳٵӰ죬ʵ֡DSMϵͳʵֵĶһģͣǶϸһģڲ̶ͬϵķɣڵ£κδ洢жϸһԵҪϸһģϸһģ͵Ĵ洢еıȽϼͼ3W(x)aʾӦߵĽ̽xֵΪaR(x)bʾӦߵĽ̶ȡxֵxֵΪb

ͼ3ϸһģ(ˮƽʱ)
3.2 ˳һģ(Sequential Consistency)
˳һԶԴ洢ƽϸһ˳һԵĴ洢Ҫµ
(1)ÿڲ˳ȷģ
(2)CPUϵĽ̶ĳ洢ԪִвôǵĲ˳ȷģһ̶ܸ֪ЩͬĲ˳
ĺ̷ֱָڲͬĻϲִʱֻҪеĽ̶ͬ˳ʴ洢ôκЧĽִжǿɽܵġ˳һģУʱ䲻ӰһԵأĵǣн̱ܸܵһµڴС
˳һģͲȷ̵һζܹһдֵͼ4(a)ĳһִʱܻͼ4(b)Ľûʽ֮ͬ£һͬĳȷܻͬĽ

ͼ4ͬһֿܵĽ(ˮƽʾʱ)
3.3 һģ(Causal Consistency)
Ƕ˳һģ͵ҪھǱϵĲ֮䱣һµ˳һԵ£Ǳصдͬ˳򱻸֪дڲͬĻϿвͬ˳
һԵĴ洢ϵͳУǺϷģ˳һԻϸһģУǷǷ

ͼ5һȫһԴ洢¼
3.4 ܵһģ(Pipelined RAM)
ܵһģǶһģ͵ĽһĳһɵдܹбĽ̰ظ֪ӲͬдԲͬĽ̿вͬ˳ͼ6ʾ

ͼ6PRSMģеһϷ¼
PRAMģʵ֣һʵϣԲ֪ͬд˳ûб֤Ǵͬһ(Դ)д밴򵽴еḶ̌Ǵһܵһ֮⣬PRAMģУɲ̲ͬдȫǲеġ
3.5 һģ(Weak Consistency)
PRAMģ֮ϸһģȣܹøõܣΪͬһ(Դ)ĽȻ˱밴ʹбĽ̵Ҫ󣬹ʶԺܶӦóԣȻܵģ͵ơеĽ̶Ҫ󿴵едĽǰؿдĽûбҪڴˣģ͵ĿܹصӰӦóܡǵмڴ²ûбҪȥǱһҪһķɣֻҪдʱŽȥ֮⣬һжȫеġΪͬĿģһģͬ
һģͱ
(1)ͬķ˳һԵҪ
(2)ͬķʣֻǰдڸ֮ɡ
(3)ݵĲ(д)ֻǰĶͬķ֮ɡ
һ˵еĽ̶ͬ˳֪жͬķʡһ̷ĳͬʱѶԸͬķʹ㲥ȥڸý̶ԸͬĲɹ֮ǰκαĽ̶ͬķʶ
ڶ˵ͬķʻᵼ¶ڴˢµĽһ֮ͬôǰдͬʱȷɡĳ̶һ˸ֵ֮ͨͬȥ
˵һڶһ(ͬ)ʱܻͨͬøùݵֵ

ͼ7һϷһԷ

ͼ8һǷһԷ
3.6 ͷһģ(Release Consistency)
ͬķʣһģһ⣺޷ֽ׼ٽѾɶԹĲ׼˳ٽǽ¶ȡͬ
(1)ֲдĽȥ
(2)ӱĻռݵֵ
ܽ˳ٽֿʵһָΪЧĴ洢һģͩͷһģ͡ͷһģṩͬAcquireReleaseĳ̽ҪٽʱִAcquire˳ٽʱִReleaseҲԲٽդ(Barrier)ͬʵͷһЭ顣դһͬƣҪеĽȫĳһ֮ͬ󣬸ִ̲ܼС
AcquireReleaseǿ԰ĳЩĹάǵһԡȻӦóȷ֪ҪάһԵݣҲӦóıһЩЭ鿪ˣͼ9ʾ

ͼ9һϷͷһԷ
ͨһֲʽ洢ϵͳͷһԣµĹ(1)ĳֻڳɹAcquire֮󣬲ȷһ㹲(ǹͬ)ʵȷԡ(2)ĳֻɶԹݵĶд֮Releaseɡ(3)AcquireReleaseܵһҪ
Ϊ˸һܣһʵͷһģ͵Э鱻֮Ϊͷһ(Lazy Release Consistency)֮Ӧһʵֱ֮Ϊͷһ(Eager Release Consistency)֮ڣͷһЭRelease֮󣬽޸ĵݴ͸бḶ̌Ľ̶ӵдݵһڱطǡʵпܱĽ̲Ҫùݣ˷˴Ҫӳ١ͷһЭRelease֮󣬲ڴµݣڱĽִAcquire֮ɱĽȡݵʱӦ󲢰ѹݵֵ͸ضḶ̌ϵͳֻߡ
3.7 һģ(Entry Consistency)
һٽԵһģBershad1993ĵһģ͡ҪԱٽĿʼͽʱʹAcquireReleaseͷһԲͬǣҪÿĳͬͬդԲзһĲͬԪΪҪͬԪؼӲֻͬеͬAcquire֮صĹݲŵõһԱ֤һģҲͬͷһģ߲ͣդڶͬAcquire֮󣬲ȷҪЩݡ
ΪֻĹҪͬÿһͬٶͬAcquireReleaseĿͬʱͬٽвӶ˲ԡĴҪÿҪһͬӶһЩԡ
ͬʹù£
ÿͬһǰӵ(ȡͬĽ)ӵ߿ԶٽظĲϷκϢʱһôͬĽҪǰӵ߷һϢԻöͬȨͬĹֵڷǻ֮£ͬʱӵĳֻͬܶԹݽжд㵥һԵǣ
(1)ڵǰӵ߶ݵĸ²δ֮ǰִһ̶ͬAcquire
(2)ĳԻģʽĳͬڸýͷŴ֮ͬǰκαĽ̼ʹڷǻģʽ¶޷øͬ
(3)ĳԻģʽһͬڸýɲ֮κν̶Դͬĺ̷ǻʣֻڳΪͬӵ֮ɡ
4 ģʽ
һϵйҳɵַռDSMϵͳĺģ֮ΪDSMͼַռĽڷǰȾ
ȣһΨһDSMʶϵͳеDSMΣ֪ƸDSMDSMַ
һDSMʶͨ󴴽һµDSMѴڵDSMвѯã̱֮ΪAttachһĳDSM󣬽ӦDSMͨMapϵͳӳ䵽̵ĵַռУӶڴռķ񡣽ɶDSMķ֮󣬽DSMDetach
ԻΪͳĻ㷨PetersonЭ(Entry Protocol)㷨ڷֲʽ¶ʧЧУʾȡǲűʾ
Peterson̻㷨ͼ10(a)XiΪʱiͼ÷ٽڣ̶ͼȡٽʱYٲãָʾĸ̿ٽ˴ڵ¿ԺܺõعDSM֮£ûпǵͨӳٵӰ죬뽫´Ľͼ10(b)ʾ̾ٽĺ

ͼ10ͳ㷨DSMʧЧʾͼ
DSM£㷨ǿܵģͼ11ʾͻͨ򻥳Require󼰵ȴAckȲ,Ա֤ܹؽٽͨRealeaseͨ汾˳ٽڽܸͻĻʱŶӴֻڶλĿͻAckϢĿͻڵȴܷAckϢ״̬ʵ㷨ҲǶĳЩ洢һģͬ(LockդBarrier)ʽ

ͼ11DSM¼ʽN-̻㷨
5 
һxyĳxyֵʼΪ0P1P2ִиóP1xֵȸΪ1ȻȡyֵP2yֵȸΪ1ȻȡxֵʱһԴ洢УP1P20ֵǲġ
дʱΪwʱΪrϢӳٵʱΪ(ͼ12ʾ)w+r<ӣP1P2ıֵֻ0δµֵΪϢӳʱʵϾϢʱ䣬ĳһûյϢ֮ǰ֪ڱĽе¼ԣһԹ洢ϵͳУȻw+rݦӡӶԵó½ۣһЭôӼôֻܻҪʵֵһһԹ洢ôȻ(Slow)ϵͳܱȻܵͨӳٵӰ졣ͬԭ򣬶һҪϸģͣϸһģͻ˳һģͣҲǲá

ͼ12ϢӳٵӰ
6 ع
йѧԺJIAJIAϵͳ˴ĲԼܷĹJIAJIAʵֵһֱ֮ΪһԵЭ飬ͨʽļ(Lock)դ(Barrier)ʵͬҪĸĽ֮ڣ
(1) ÿ鴫䷽ʽ
JIAJIAõUDPЭ飬ʵֵһֲɿݰͨţңԾдͨӦóԣUDPЭ̫ͨ(EtherNet)طͳȥԵ̫ΪˣǲӲṩBLTܣͨPUT/GETʵֿ鴫䣬ͨŲ̫ͨΪ鴫ͨŵĴϵͳܻ˸ơڿ鴫䷽ʽеӦóŽõļٱȣң̫֮ͨµʱķȣҲߡ
(2) ֹϵͳںʵ
DSMϵͳдձԵһǣӦóйҪԶݶò뵽ϵͳ֮Сֽ/ܵʱķ൱ģڲÿ鴫䷽ʽͨŴֽ֮/ܵĿͳΪϵͳܵƿڣⲿֹڽ֮С
(3)һѰӲ֧
ĿȻѧ(ڵӳзֲʽϵͳо)
ѧѧϵ
ƣѧԺ ɳ 410073
޾ѧԺ ɳ 410073
ѧԺ ɳ 410073
٣й豸ϵͳ̹˾о  100039
ο
1Andrew S. Tanenbaum. Distributed Operating Systems
2Phillip W.Hutto and Mustaque Ahamad. Slow Memory: Weakening Consistency to Enhance Concurrency in Distributed Shared Memories. IEEE 1990
3Pedro Souto and Eugene W.Stark. A Distributed Shared Memory Facility for FreeBSD. USENIX Association. 1997 Annual Technical Conference
4Hu Weiwu, Shi Weisong, Tang Zhimin and Li Ming. A Lock-Based Cache Coherence Protocol for Scope Consistency. Vol.13 No.2 J.of Comput. Sci.&Technol. Mar.1998
5L.lftode, J.P.Singh and K.Li. Scope Consistency: A Bridge between Release Consistency and Entry Consistency. Theory Comput.Systems 31. 451473(1998)
6Steven K. Reinhardt, Member, IEEE, Robert W.Pfile, and David A.Wood, Member, IEEE. Hardware Support for Flexible Distributed Shared Memory IEEE 1998
ոڣ1999921
