第 6章 分布式存储管理东北大学信息学院于 戈
2002年 7月
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
2
主要内容
6.1 分布式共享内存（ DSM）
6.2 一致性模型
6.3 基于页面的 DSM
6.4 DSVM的应用
6.5 习题
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
3
6.1分布式共享内存（ DSM)
CPU与存储器连接模型
单片机
理想的共享存储器多处理机
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
4
UNIX共享内存举例
System call Description
int shmget(key,size,
ishmflg);
returns the SM identifier associated with
key.
void *shmat(shmid,
*shmaddr,shmflg);
attaches the SM segment associated
with the shmid to the data segment of
the calling process.
int shmdt(const void
*shmaddr);
detaches from the calling process's
data segment the SM segment
located at shmaddr.
int shmctl(shmid,cmd,
*buf)
provides a variety of SM control
operations as specified by cmd,
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
5
层次结构
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
6
1,多处理器结构
2,带缓存的多处理器结构
总线仲裁机制：集中式和非集中式基于总线的多处理机
CPU
内存总线
(a)
总线
(b)
缓存
CPUCPU CPU
内存缓存
CPU
缓存
CPU
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
7
通写缓冲 (write-though)一致性协议事件 对本地 CPU操作响应 对远程 CPU响应读失败
（ miss）
从内存中取得数据并存储到缓存中（ M?C）
（无动作）
读命中
(hit)
从本地缓存中取得数据 （无动作）
写失败 更新内存中的数据并存储到缓存中（ C? M ）
（无动作）
写命中 更新存储器和缓存
（ M?C? M ）
置为无效
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
8
缓存拥有权（ ownership）协议
Cache分成若干个 cache块
每个 Cache块处于三种状态：
1,Invalid－数据无效
2,Clean－与存储器数据一致
3,Dirty－数据被更新，与存储器数据一致
各 CPU监听（ snoopy）其它 CPU在总线的操作
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
9
缓存拥有权协议举例
1,W初始状态 (W1)
2,A读 W(W1)
3,A写 W(W2)
4,A再写 W(W3)
5,C读写 W(W3)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
10
缓存拥有权（ ownership）协议
多个 CPU可有读拥有权
只有一个 CPU有写拥有权
当一个 CPU写一个数据
– 取得对该数据的拥有权
– 其它 CPU将该数据的缓存块置为,invalid”
– 在本地缓存块中，写数据，并置为,dirty”
– 适当时候，刷新存储区，或提供给其它
CPU
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
11
缓存拥有权（ ownership）协议
特点
1,通过各 CPU对总线的监听保持缓存一致性
2,该协议实现在存储器管理单元中
3,整个算法在一个存储器周期中完成
召回（ callback）协议
如果用软件实现
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
12
6.2 一致性模型
缓存一致性（ coherency）
– 数据在各个缓存中的值保持一致
一致性模型
– 软件与存储器间的约定（ contract）
– 如果软件遵守约定的规则，存储器就能工作正常。
– 如果软件违反了这些规定，存储器就不再保证操作的正确性
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
13
严格一致性
从存储器地址 X处读出的值为最近写入 X的值
非严格一致性
P1,W(x)1
P2,R(x)1
P1,W(x)1
P2,R(x)0 R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
14
顺序一致性
如果所有进程执行的结果，等同于它们的操作按某种顺序执行的结果。
每一进程的操作都按程序规定的顺序执行 。
所有进程看到相同的内存访问操作次序
例：运行同一个程序得到的两个可能的结果
P1,W(x)1
P2,R(x)0 R(x)1
P1,W(x)1
P2,R(x)1 R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
15
3个并行执行的进程
4种正确的执行顺序顺序一致性举例
print(b,c);
(a)
a=1;
print(a,c);
(b)
b=1;
print(a,b);
(c)
c=1;
a=1; a=1; b=1; b=1;
print(b,c); b=1; c=1; a=1;
b=1; print(a,c); print(a,b); c=1;
print(a,c); print(b,c); print(a,c); print(a,c);
c=1; c=1; a=1; print(b,c);
print(a,c); print(a,b); print(b,c); print(a,b);
(a) (b) (c) (d)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
16
因果一致性
对于因果相关的写操作，所有进程看到的执行顺序应相同。
并发写操作在不同 CPU看到的顺序可能不同
P1,W(x)1 W(x)3
P2,R(x)1 W(x)2
P3,R(x)1 R(x)3 R(x)2
P4,R(x)1 R(x)2 R(x)3
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
17
因果一致性举例
（ 1）违反因果一致性
（ 2）符合因果一致性
P1,W(x)1
P2,R(x)1 W(x)2
P3,R(x)2 R(x)1
P4,R(x)1 R(x)2
P1,W(x)1
P2,W(x)2
P3,R(x)2 R(x)1
P4,R(x)1 R(x)2
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
18
管道内存（ PRAM ）一致性
同一个进程的写操作的执行次序，其它进程看到的都相同
不同进程的写操作的执行次序，不同进程看到的可以是不同的
例：符合 PRAM一致性，但不符合因果一致性
P1,W(x)1
P2,R(x)1 W(x)2
P3,R(x)1 R(x)2
P4,R(x)2 R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
19
处理机一致性
与 PRAM一致性相似
附加条件：
– 存储相关性：对于任意存储器地址 X,对于写入 X的顺序是全局一致的。
– 写入不同地址,对于不同进程来看,不需要相同顺序
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
20
弱一致性
同步变量：广播导出所有写操作,导入所有写操作
对同步变量的访问 必须 是顺序一致 性 的 。
在所有前 面 的写操作完成之前,不能访问同步变量 。
在前面所有同步变量的访问完成前,不能访问（读或写）数据。
P1,W(x)1 W(x)2 S
P2,R(x)1 R(x)2 S
P3,R(x)2 R(x)1 S
P1,W(x)1 W(x)2 S
P2,S R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
21
释放一致性
Acquire操作：要进入临界区
Release操作：退出临界区
规则
– 在访问共享变量前,所有先前的 acquire都必须完成 。
– 在进行 release前,先前的所有读写操作都必须结束 。
– acquire和 release访问必须满足处理机一致性
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
22
释放一致性
急性释放一致性 (EAGER release consistency)
– 当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机
惰性释放一致性（ LAZY release consistency）
– 在执行释放时，不发送任何数据。
– 在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值
P1,Acq(L) W(x)1 W(x)2 Rel(L)
P2,Acq(L) R(x)2 Rel(L)
P3,R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
23
入口一致性
（ 1）只有某一进程的保护共享变量全部被更新以后，
该进程才允许执行同步变量的获取访问；
（ 2）在一进程以互斥模式访问该进程的同步变量之前，
不允许其他进程持有此同步变量，即使在非互斥模式下；
（ 3）在结束互斥模式下对一个同步变量的访问后，任意其他进程必须与该变量的拥有者核查，才能试图以非互斥模式访问该同步变量。
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
24
一致性模型总结不用同步操作一致性 说明严格 所有的共享访问事件都有绝对时间顺序顺序 所有进程都以相同的顺序检测到所有的共享访问事件因果 所有进程都以相同的顺序检测到所有因果联系的事件
PRAM 所有的进程按照预定的顺序检测到来自一个处理器的写操作,来自其它处理器的写操作不必以相同的顺序看见处理器 PRAM一致性 +存储器相关性
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
25
一致性模型总结
同步操作一致性 说明弱 同步完成后,共享数据才可能保持一致释放 当离开临界区时,共享数据就保持一致入口 当进入临界区时,和该临界区相关的共享数据保持一致
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
26
6.3 基于页面的 DSM
页块：地址空间管理的基本单位
0 1 2 3 4 5 6 7 8 9
CPU 1
0 2 5
9
CPU 2
1 3 6
8
CPU 3
4 7
CPU 4
存储器
(a)
全局共享地址空间
1011 15121314
11
10 1214
13 15
(b)
CPU 1
0 2 5
9
CPU 2
1 3 6
8
CPU 3
4 7
CPU 4
11
1214
13 15
10
(c)
CPU 1
0 2 5
9
CPU 2
1 3 6
8
CPU 3
4 7
CPU 4
11
10 1214
13 15
10
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
27
实现技术
虚拟地址空间
内存映射（ memory mapping）
缺页中断（ pagefault）
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
28
存储映射技术
两个进程共享同一个文件
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
29
存储映射技术
s is an error code addr are memory addresses
len is a length prot controls protection
flags are miscellaneous bits
fdis a file descriptor offset is a file offset
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
30
页面的大小
错误共享：两个无关的变量位于同一页使用 A的代码使用 B的代码处理器 1 处理器 2
共享页面两个无关的共享变量
A
B
A
B
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
31
处理机读页举例
P W
拥有者
1.读
P R
拥有者
1.读
P R拥有者 1.读页面处理器 1 处理器 2
R
P R 1.读
P 1.请求复制2.将页标志为 R
3.读
P
R
拥有者
R
拥有者
W
拥有者 1.请求降级2.请求复制
3.将页标志为 R
4.读
(a)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
32
处理机写页举例
P W
拥有者
1.写
P R
拥有者 1.将页标志为 W
2.写入
P R
拥有者 1.无效的拷贝
2.将页标志为 W
3.写入
R
P R
1.请求置无效
2.请求拥有者
3.将页标志为 W
4.写入
P
1.请求置无效
2.请求拥有者3.请求页面
4.将页标志为 W
5.写入
P
R
拥有者
R
拥有者
W
拥有者 1.请求置无效2.请求拥有者
3.请求页面
4.将页标志为 W
5.写入(b)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
33
拥有者定位协议
四消息协议
三消息协议
P 拥有者页面管理器
3.请求
4.响应 P 拥有者页面管理器
3.响应
(a) (b)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
34
寻找拷贝
.
每个页面的拥有者通过拷贝集得知哪个其它 CPU正共享该页面
3
2
4
2
1
3
4
2
4
5
34 2 3 4 1 页面
CPU 1 CPU 2 CPU 3 CPU 4 CPU 5
拷贝集网络
4 3 1 2
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
35
6.4 DSM应用举例
分布并行式对象数据库系统 FISH
Network ＯＳ（Ｓｏｌａｒｉｓ，Ｌｉｎｕｘ，ＷｉｎｄｏｗｓＮＴ）
Wakashi
Persistent Objects（conforming to
ODMG2.0）
Object Programming Lang.（C++binding）
Inada
Warasa
Visual Interface
Object Query Language（OQL）
Persistent Distributed Shared Memory)
Transaction Control (Lock,Recovery)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
36
分布透明性
Fragment 1
copy
Fragment 2
copy
Query 1 Query 2
Database
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
37
存储器映射技术
client1
database local disk cache
site1 site n
heap
server 1 server i server
n
heap heap
DSVMmapping
Local disk cache
memorymapping
Network
DSVMmapping
client i client n
disk mapping local disk
caching
local disk cachingsite i
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
38
进程结构
RPC Socket
serverproces
s serverthread
Server
client
process client thread
cleint
serverproces
s serverthread
locktable
Server
client process client
thread
client
lock table
Site 1 Site 2
RPC
Socket
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
39
基于 pagefault的封锁
Transaction_Begin( );
。。。O1->amount = O2->amount+500;
。。。
Transcation_End( );
Server
Receive requesting;
check locking table;
Grant locking;
send response;
Pagefault
exception
Client
get addr.,conflict type
get page number
send locking requestset attr,(read/write)
Locking table;
memory object tabele
Oid addr size
pid type user
(3)
(1) (2)
(7) (4)
(6) (5)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
40
习 题
1,在内存一致性模型的讨论中，经常提到软件和内存的约定。为什么需要这样的约定，举例说明？
2,下图为顺序一致性内存的一个例子。对 P2做少量改动，使它破坏顺序一致性。
3,释放一致性的大多数实现方法是在 release时同步共享变 量,而不是在 acquire时同步,但为什么还需要 acquire 操作？
P1,W(x)1
P2,R(x)0 R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
41
习 题
4,在如下并行执行的进程 P1和 P2，列出顺序一致性所允许的 6种语句交叉执行情况 。
5,假设两个变量 a和 b,恰好位于基于分页的 DSM系统的同一页上。然而，它们都不是共 享变量。是否会发生错误共享？
a=1; b=1;
If (b==0) kill (P2) if(a==0) kill (P1)
(a) P1 （ b) P2
2002年 7月
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
2
主要内容
6.1 分布式共享内存（ DSM）
6.2 一致性模型
6.3 基于页面的 DSM
6.4 DSVM的应用
6.5 习题
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
3
6.1分布式共享内存（ DSM)
CPU与存储器连接模型
单片机
理想的共享存储器多处理机
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
4
UNIX共享内存举例
System call Description
int shmget(key,size,
ishmflg);
returns the SM identifier associated with
key.
void *shmat(shmid,
*shmaddr,shmflg);
attaches the SM segment associated
with the shmid to the data segment of
the calling process.
int shmdt(const void
*shmaddr);
detaches from the calling process's
data segment the SM segment
located at shmaddr.
int shmctl(shmid,cmd,
*buf)
provides a variety of SM control
operations as specified by cmd,
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
5
层次结构
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
6
1,多处理器结构
2,带缓存的多处理器结构
总线仲裁机制：集中式和非集中式基于总线的多处理机
CPU
内存总线
(a)
总线
(b)
缓存
CPUCPU CPU
内存缓存
CPU
缓存
CPU
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
7
通写缓冲 (write-though)一致性协议事件 对本地 CPU操作响应 对远程 CPU响应读失败
（ miss）
从内存中取得数据并存储到缓存中（ M?C）
（无动作）
读命中
(hit)
从本地缓存中取得数据 （无动作）
写失败 更新内存中的数据并存储到缓存中（ C? M ）
（无动作）
写命中 更新存储器和缓存
（ M?C? M ）
置为无效
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
8
缓存拥有权（ ownership）协议
Cache分成若干个 cache块
每个 Cache块处于三种状态：
1,Invalid－数据无效
2,Clean－与存储器数据一致
3,Dirty－数据被更新，与存储器数据一致
各 CPU监听（ snoopy）其它 CPU在总线的操作
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
9
缓存拥有权协议举例
1,W初始状态 (W1)
2,A读 W(W1)
3,A写 W(W2)
4,A再写 W(W3)
5,C读写 W(W3)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
10
缓存拥有权（ ownership）协议
多个 CPU可有读拥有权
只有一个 CPU有写拥有权
当一个 CPU写一个数据
– 取得对该数据的拥有权
– 其它 CPU将该数据的缓存块置为,invalid”
– 在本地缓存块中，写数据，并置为,dirty”
– 适当时候，刷新存储区，或提供给其它
CPU
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
11
缓存拥有权（ ownership）协议
特点
1,通过各 CPU对总线的监听保持缓存一致性
2,该协议实现在存储器管理单元中
3,整个算法在一个存储器周期中完成
召回（ callback）协议
如果用软件实现
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
12
6.2 一致性模型
缓存一致性（ coherency）
– 数据在各个缓存中的值保持一致
一致性模型
– 软件与存储器间的约定（ contract）
– 如果软件遵守约定的规则，存储器就能工作正常。
– 如果软件违反了这些规定，存储器就不再保证操作的正确性
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
13
严格一致性
从存储器地址 X处读出的值为最近写入 X的值
非严格一致性
P1,W(x)1
P2,R(x)1
P1,W(x)1
P2,R(x)0 R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
14
顺序一致性
如果所有进程执行的结果，等同于它们的操作按某种顺序执行的结果。
每一进程的操作都按程序规定的顺序执行 。
所有进程看到相同的内存访问操作次序
例：运行同一个程序得到的两个可能的结果
P1,W(x)1
P2,R(x)0 R(x)1
P1,W(x)1
P2,R(x)1 R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
15
3个并行执行的进程
4种正确的执行顺序顺序一致性举例
print(b,c);
(a)
a=1;
print(a,c);
(b)
b=1;
print(a,b);
(c)
c=1;
a=1; a=1; b=1; b=1;
print(b,c); b=1; c=1; a=1;
b=1; print(a,c); print(a,b); c=1;
print(a,c); print(b,c); print(a,c); print(a,c);
c=1; c=1; a=1; print(b,c);
print(a,c); print(a,b); print(b,c); print(a,b);
(a) (b) (c) (d)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
16
因果一致性
对于因果相关的写操作，所有进程看到的执行顺序应相同。
并发写操作在不同 CPU看到的顺序可能不同
P1,W(x)1 W(x)3
P2,R(x)1 W(x)2
P3,R(x)1 R(x)3 R(x)2
P4,R(x)1 R(x)2 R(x)3
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
17
因果一致性举例
（ 1）违反因果一致性
（ 2）符合因果一致性
P1,W(x)1
P2,R(x)1 W(x)2
P3,R(x)2 R(x)1
P4,R(x)1 R(x)2
P1,W(x)1
P2,W(x)2
P3,R(x)2 R(x)1
P4,R(x)1 R(x)2
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
18
管道内存（ PRAM ）一致性
同一个进程的写操作的执行次序，其它进程看到的都相同
不同进程的写操作的执行次序，不同进程看到的可以是不同的
例：符合 PRAM一致性，但不符合因果一致性
P1,W(x)1
P2,R(x)1 W(x)2
P3,R(x)1 R(x)2
P4,R(x)2 R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
19
处理机一致性
与 PRAM一致性相似
附加条件：
– 存储相关性：对于任意存储器地址 X,对于写入 X的顺序是全局一致的。
– 写入不同地址,对于不同进程来看,不需要相同顺序
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
20
弱一致性
同步变量：广播导出所有写操作,导入所有写操作
对同步变量的访问 必须 是顺序一致 性 的 。
在所有前 面 的写操作完成之前,不能访问同步变量 。
在前面所有同步变量的访问完成前,不能访问（读或写）数据。
P1,W(x)1 W(x)2 S
P2,R(x)1 R(x)2 S
P3,R(x)2 R(x)1 S
P1,W(x)1 W(x)2 S
P2,S R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
21
释放一致性
Acquire操作：要进入临界区
Release操作：退出临界区
规则
– 在访问共享变量前,所有先前的 acquire都必须完成 。
– 在进行 release前,先前的所有读写操作都必须结束 。
– acquire和 release访问必须满足处理机一致性
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
22
释放一致性
急性释放一致性 (EAGER release consistency)
– 当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机
惰性释放一致性（ LAZY release consistency）
– 在执行释放时，不发送任何数据。
– 在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值
P1,Acq(L) W(x)1 W(x)2 Rel(L)
P2,Acq(L) R(x)2 Rel(L)
P3,R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
23
入口一致性
（ 1）只有某一进程的保护共享变量全部被更新以后，
该进程才允许执行同步变量的获取访问；
（ 2）在一进程以互斥模式访问该进程的同步变量之前，
不允许其他进程持有此同步变量，即使在非互斥模式下；
（ 3）在结束互斥模式下对一个同步变量的访问后，任意其他进程必须与该变量的拥有者核查，才能试图以非互斥模式访问该同步变量。
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
24
一致性模型总结不用同步操作一致性 说明严格 所有的共享访问事件都有绝对时间顺序顺序 所有进程都以相同的顺序检测到所有的共享访问事件因果 所有进程都以相同的顺序检测到所有因果联系的事件
PRAM 所有的进程按照预定的顺序检测到来自一个处理器的写操作,来自其它处理器的写操作不必以相同的顺序看见处理器 PRAM一致性 +存储器相关性
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
25
一致性模型总结
同步操作一致性 说明弱 同步完成后,共享数据才可能保持一致释放 当离开临界区时,共享数据就保持一致入口 当进入临界区时,和该临界区相关的共享数据保持一致
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
26
6.3 基于页面的 DSM
页块：地址空间管理的基本单位
0 1 2 3 4 5 6 7 8 9
CPU 1
0 2 5
9
CPU 2
1 3 6
8
CPU 3
4 7
CPU 4
存储器
(a)
全局共享地址空间
1011 15121314
11
10 1214
13 15
(b)
CPU 1
0 2 5
9
CPU 2
1 3 6
8
CPU 3
4 7
CPU 4
11
1214
13 15
10
(c)
CPU 1
0 2 5
9
CPU 2
1 3 6
8
CPU 3
4 7
CPU 4
11
10 1214
13 15
10
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
27
实现技术
虚拟地址空间
内存映射（ memory mapping）
缺页中断（ pagefault）
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
28
存储映射技术
两个进程共享同一个文件
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
29
存储映射技术
s is an error code addr are memory addresses
len is a length prot controls protection
flags are miscellaneous bits
fdis a file descriptor offset is a file offset
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
30
页面的大小
错误共享：两个无关的变量位于同一页使用 A的代码使用 B的代码处理器 1 处理器 2
共享页面两个无关的共享变量
A
B
A
B
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
31
处理机读页举例
P W
拥有者
1.读
P R
拥有者
1.读
P R拥有者 1.读页面处理器 1 处理器 2
R
P R 1.读
P 1.请求复制2.将页标志为 R
3.读
P
R
拥有者
R
拥有者
W
拥有者 1.请求降级2.请求复制
3.将页标志为 R
4.读
(a)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
32
处理机写页举例
P W
拥有者
1.写
P R
拥有者 1.将页标志为 W
2.写入
P R
拥有者 1.无效的拷贝
2.将页标志为 W
3.写入
R
P R
1.请求置无效
2.请求拥有者
3.将页标志为 W
4.写入
P
1.请求置无效
2.请求拥有者3.请求页面
4.将页标志为 W
5.写入
P
R
拥有者
R
拥有者
W
拥有者 1.请求置无效2.请求拥有者
3.请求页面
4.将页标志为 W
5.写入(b)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
33
拥有者定位协议
四消息协议
三消息协议
P 拥有者页面管理器
3.请求
4.响应 P 拥有者页面管理器
3.响应
(a) (b)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
34
寻找拷贝
.
每个页面的拥有者通过拷贝集得知哪个其它 CPU正共享该页面
3
2
4
2
1
3
4
2
4
5
34 2 3 4 1 页面
CPU 1 CPU 2 CPU 3 CPU 4 CPU 5
拷贝集网络
4 3 1 2
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
35
6.4 DSM应用举例
分布并行式对象数据库系统 FISH
Network ＯＳ（Ｓｏｌａｒｉｓ，Ｌｉｎｕｘ，ＷｉｎｄｏｗｓＮＴ）
Wakashi
Persistent Objects（conforming to
ODMG2.0）
Object Programming Lang.（C++binding）
Inada
Warasa
Visual Interface
Object Query Language（OQL）
Persistent Distributed Shared Memory)
Transaction Control (Lock,Recovery)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
36
分布透明性
Fragment 1
copy
Fragment 2
copy
Query 1 Query 2
Database
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
37
存储器映射技术
client1
database local disk cache
site1 site n
heap
server 1 server i server
n
heap heap
DSVMmapping
Local disk cache
memorymapping
Network
DSVMmapping
client i client n
disk mapping local disk
caching
local disk cachingsite i
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
38
进程结构
RPC Socket
serverproces
s serverthread
Server
client
process client thread
cleint
serverproces
s serverthread
locktable
Server
client process client
thread
client
lock table
Site 1 Site 2
RPC
Socket
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
39
基于 pagefault的封锁
Transaction_Begin( );
。。。O1->amount = O2->amount+500;
。。。
Transcation_End( );
Server
Receive requesting;
check locking table;
Grant locking;
send response;
Pagefault
exception
Client
get addr.,conflict type
get page number
send locking requestset attr,(read/write)
Locking table;
memory object tabele
Oid addr size
pid type user
(3)
(1) (2)
(7) (4)
(6) (5)
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
40
习 题
1,在内存一致性模型的讨论中，经常提到软件和内存的约定。为什么需要这样的约定，举例说明？
2,下图为顺序一致性内存的一个例子。对 P2做少量改动，使它破坏顺序一致性。
3,释放一致性的大多数实现方法是在 release时同步共享变 量,而不是在 acquire时同步,但为什么还需要 acquire 操作？
P1,W(x)1
P2,R(x)0 R(x)1
2002-7-12
东北大学软件所 于戈 第六章 分布式存储管理
41
习 题
4,在如下并行执行的进程 P1和 P2，列出顺序一致性所允许的 6种语句交叉执行情况 。
5,假设两个变量 a和 b,恰好位于基于分页的 DSM系统的同一页上。然而，它们都不是共 享变量。是否会发生错误共享？
a=1; b=1;
If (b==0) kill (P2) if(a==0) kill (P1)
(a) P1 （ b) P2
