2.直接映象及其变换
1)规则：主存中每一块只能映像到 Cache中唯一一个特定位置，如图所示，主存的第 i块只能映像到第 i mod2ncb块位置上。如图 4.35所示：
……
Cache
块位置 0
1
2ncb-1
主存块 0
1
2nmb-1
…
2ncb-1
块 2ncb+0
2ncb+1…
2·2ncb-1
块 2·2ncb+0…
3·2ncb-1…
…
0区
1区
2区
2nmb－ ncb-1区图 4.35 直接映象规则
2)变换 过程 主存块号 块内地址 主存地址
nmnmb nmr
ncb ncr Cache地址n
c
…
2ncb项相联比较不等块失效区号
…
0
1
2ncb-1
相等访 Cache
区号
(按地址访问存贮器 )
由
2ncb
中选
1
图 4.36 直接映象的地址变换过程
3)优缺点优点：
a)所需硬件简单，只需要容量较小的按地址访问的区号标志表存贮器和少量外比较电路，因此成本低。
b)访问 Cache与访问区号表、比较区号是否相符的操作是同时进行的。当 Cache命中时就意味着省去了地址变换所花费的时间。
缺点,直接映象法最致命的缺点就是 Cache的块冲突率很高。只要有两个或两个以上经常使用的块恰好被映象到 Cache的同一个块位置时，就会使得
Cache的命中率急剧下降。而且，即使此时 Cache
中有大量的空闲块存在，仍然会发生块失效和块冲突，无法使用 Cache中的空闲块，所以,Cache的利用率很低。正是因为这个原因才使得目前采用直接映象的 Cache存贮器很少了。
3.组相联映象及其变换
1)思想：简要说明如下图 4.37所示，将 Cache空间和主存空间都分组，每组 S块 (S＝ 2s)。 Cache一共
2ncb个块，分成 Q组 (Q= 2q)，整个 Cache是一区。
主存分成与 Cache一样大小的 2nd个区，其地址按区号、组号、组内块号、块内地址分成对应的 4个字段。主存地址的组号、组内块号分别用 q,s' 字段表示，它们的宽度和位置与 Cache地址的 q,s
是一致的。
2)规则：组相联映象指的是各组之间直接映象，但组内各块间则是全相联映象。如图 4.37所示。
组号
q
组内块号
s
块内地址
ncr 组号 q 组内块号 s' 块内地址 nmr区号 nd
1位 1位2位 2位1位
ncb nmb
nc nm
块位置 0
块 0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
9
10
11
12
13
14
15
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
第 0组第 0组第 1组第 1组第 0组第 1组第 0区
(Cache容量 )
第 1区
(Cache容量 )
Cache
主存组内全相联组间直接相联图 4.37 组相联映象规则
3)讨论当组相联映象的 S值大到等于 Cache的块数 (即 s= ncb)
时就变成了全相联映象，而当 S值小到只有 1块 (即无 s
字段 )时就变成了直接映象。因此全相联映象和直接映象只是组相联映象的两个极端。在 Cache空间大小及块的大小都已经确定的情况下,Cache的总块数就定了，但结构设计者仍可以对 S和 Q值进行选择。 Q和 S
的选取主要依据对块冲突概率、块失效率、映象表复杂性和成本、查表速度等的折衷权衡。组内块数 S愈多，块冲突概率和块失效率愈低，映象表愈复杂、成本愈高，查表速度愈慢。所以通常采用在典型工作负荷下进行模拟而定。
4)地址变换组号
q
组内块号
s'
块内地址
nmr
区号
nd
组号
q
组内块号
s
块内地址
ncr
nm
nc
直接直接相联比较不等块失效 相等?
相联比较
nd s' s
nd ＋ s'
表的总容量为
2ncb ＝ 2q·2s行
2q
组中选
1
2s行
4.段相联映象在全相联、直接相联、组相联映象的基础上还可以有各种变形，段相联就是一例。段相联实质上是组相联的特例。他是采用组间全相联、组内直接映象。为了与组相联加以区别，将这种映象方式称为段相联。就是说，段相联映象是把主存和 Cache分成具有相同的 Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象。如图 4.42
所示：
块 0
块 1
块 2
Z－ 1
Cache
主存
…
块 0
块 1
块 2
Z－ 1
…
≈≈
块 0
块 1
块 2
Z－ 1
…
块 0
块 1
块 2
Z－ 1
…
≈≈
块 0
块 1
块 2
Z－ 1
…
段 0
段 0(Z个段 )
段 1
段 2nmb/Z－ 1
段 2ncb/Z－ 1
图 4.42 具有每段 Z个块的断相联映象段间全相联段内直接
4.3.3替换算法的实现当访存发生 Cache块失效，需要把主存块按所采用的映象规则装入 Cache时，如果又出现 Cache块冲突，就必须按某种策略选择将 Cache中的哪一块替换出去。 Cache——主存存贮层次的替换算法与虚拟存贮器的没有什么不同，不外乎也是 FIFO法或
LRU法，其中 LRU法最为常用。
1.堆栈法
1)思想我们在 4.2.2中讲过,LRU法是堆栈型替换算法，
也讲了对于 LRU算法，堆栈 St中由栈顶到栈底的各项（行）恒反映出到 t时刻，实存中各页被访问过的近远次序，以及每访问一页，堆栈 St中各项的变换过程。结果是此堆栈的栈顶恒存放近期最近访问过的页的页号，而栈底恒存放近期最久没有方问过的页的页号，即准备被替换掉的页的页号。那么，我们在 Cache——主存存贮层次中就可以按此思想实际组成一个硬件堆栈。
2)过程
（块号）
（块号）
（块号）
（块号）
（块号）
2ncb个寄存器需重新排列的块号都下推一行被访问的块号
（经相联比较找到）
寄存器堆栈压入
ncb位近期最近访问过的块近期最久没有访问过的块图 4.43 全相联映象 LRU法经堆栈实现（需要有相联比较功能）
3)缺点：
这种硬件堆栈既要求具有相联比较的功能，又要求能全下移、部分下移和从中间取出一项的功能，
成本较高，因此只适用于组相联且组内块数较少的
LRU替换场合。
4)变形上述这种堆栈，各块被访问的先后次序由该项在堆栈中距离栈底是近还是远来反映。为了避免堆栈中各行存放的内容经常同时进行下移，以便节省成本，我们采用另一种变形，即将存放块号的寄存器的几何位置与 Cache中的块号对应，而用寄存器存放值的大小来表示已被访问过的远近次序。以组相联为例，每一组均使用如图 4.44那样的一个寄存器组，由 2s个寄存器组成，每个寄存器为 s位宽，可以存放表示从 0到 2s－ 1的次序值。如果让越是最近访问的，其次序值愈小，则只需通过相联比较求最大值（不是相联比较相符），找到该最大值所在的寄存器号，这就是对应 Cache中应该被替换掉的块的块号。
第 0块的访问次序第 1块的访问次序第 2块的访问次序第 2s-1块的访问次序块 0
块 1
块 2
块 2s-1
2s个寄存器
S位
（其中一组）
Cache存贮器
（其中一组）
图 4.44 组相联 LRU法经寄存器实现
（每组一个，需要有相联比较功能）
2.比较对法
1)思路比较法的基本思路是让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到 LRU块。比如说有 A B
C三块，互相之间可以组合成 AB BA AC CA BC
CB6对，其中 AB和 BA,AC和 CA,BC和 CB是重复的，所以 TAB为,1”，表示 A比 B更近被访问过；
TAB
为,0”，则表示 B比 A更近被访问过。 TAC,TBC也类似定义。这样，当访问过的次序为 A B C，即最近访问过的为 A，最久未被访问过的为 C，则这三个触发器状态分别为 TAB＝ 1,TAC＝ 1,TBC＝ 1。如果访问过的次序为 B A C,C为最久未被访问过的块，则此时必有 TAB＝ 0,TAC＝ 1,TBC＝ 1。因此最久未被访问过的块 C作为被替换掉的块的话，用布尔代数式必有：
CLRU＝ TAB? TAC?TBC +TAB? TAC?TBC ＝ TAC?TBC
同理可得：
BLRU＝ TAB?TBC ； ALRU＝ TAB? TAC
因此，完全可以用门、触发器等硬件组合实现，如图 4.45所示：
& & &
0 1 0 1 0 1
TAB TAC TBC
ALRU BLRU CLRU
访问 B
访问 C
访问 A
图 4.15 用比较对法实现 LRU算法
2)分析我们来看比较对法所用的硬件量。由于每块均可能作为 LRU块，其信号需要用一个与门产生，例如
ALRU与门要有从 TAB TAC来的输入,BLRU门要有从
TAB,TBC来的输入，而与每块有关的对数个数为块数减去 1，所以与门的扇入数是块数减去 1。若 p为块数，量量组合，比较对触发器的个数应为 Cp2，即为 p(p-1)/2。表 4.2给出了比较对法块数 p的取值与门数、门的输入端数及比较对触发器数的关系。
3)总结替换算法实现的设计要围绕下面两点来考虑：
a)如何对每次访问进行记录（使用位法、堆栈法和比较对法所用的记录方法都不同）；
b)如何根据所记录的信息来判定近期内哪一块最久没有被访问过。由此可见，实现方法和所用的映象方法密切相关。
例如，对于主存 ——辅存存贮层次的全相联映象宜于采用使用位法或类似的方法，而不宜采用堆栈法和比较对法；但对于 Cache——主存存贮层次的组相联映象，因为组内块数较少，就宜于采用比较对法或堆栈法。替换算法的设计和实现也和器件的发展密切相关，随着器件技术的发展，尤其是高速相联存贮器片子的改进，已经而且必然会不断研制出新的更好的实现方法。
4.3.4 Cache的透明性及性能分析
1.Cache的透明性分析
1)两种问题的出现虽然 Cache是主存的一部分副本，主存中某单元的内容却可能在一段时间里会与 Cache中对应单元的内容不一致。例如,CPU往 Cache写入，修改了 Cache
中某单元的内容，而在主存中对应于此单元的内容却可能仍是原来的，没有改变。这时，如果 CPU或
I/O处理机及其他处理机要经主存交换信息，那么主存内容跟不上 Cache对应内容变化的这种不一致就会造成错误。
同样,I/O处理机或其他处理机已把新的内容送入主存某个区域，而 Cache中对应于此区域的副本内容却仍可能是原来的。这时，如果 CPU要从 Cache
中读取信息，也会因为这种 Cache内容跟不上主存对应内容变化的不一致而造成错误。因此，必须采取措施解决好由于读写过程中产生的 Cache和主存对应内容不一致的问题。
2)写回法写回法是在 CPU执行写操作时，只是把信息写入
Cache，仅当需要被替换时，才将已经被写入过的
Cache块先送回主存，然后再调入新块。这种方法也称为抵触修改法，类似于虚拟存贮器中进行页面替换时的情况。因此,Cache——主存存贮层次的地址映象表中需对 Cache中的每个块设置一个“修改位”，作为该块装入 Cache后是否被修改过的标志。
这样在块替换时，根据该块的修改位是否位 1，就可以决定替换时是否先将该块存回主存原来的位置。
3)写直达法写直达法也称为存直达法，它利用 Cache——主存存贮层次在处理机和主存之间的直接通路，每当处理机写入 Cache的同时，也通过此通路直接写入主存。这样，在块替换时，就不必先写回主存，而可以立即调入新页。显然，写回法是把开销花在每次需要替换的时候，而写直达法则把开销花在每次写入 Cache时都附加一个比写 Cache长的多的写主存时间。
4)写不命中处理当出现写不命中时，无论是写回法还是写直达法都有一个在写时是否取的问题。一种是不按写分配法，即当 Cache写不命中时只写入主存，该写地址单元所在块不从主存调进 Cache。另一种是按写分配法，即当 Cache不命中时除写入主存外，还把该写地址单元所在的块由主存调入 Cache。这两种策略对不同的主存修改算法，其效果不同，但命中率差别不大。目前写回法一般采用按写分配法，而写直达法则一般采用不按写分配法。
写回法和写直达法都需要有少量缓冲器。写回法中缓冲器用于暂存将要写回的块，使之不必等待被替换块写回主存后才开始进行 Cache取。写直达法中缓冲器则用于缓冲由写 Cache所要求的写回主存的内容，使 CPU不必等待这些写主存完成就能往下运行。缓冲器由要存的数据和要存入的目标地址组成。在写直达系统中容量为 4的缓冲器就可以显著改进其性能,IBM 3033就是这样用的。要注意的这些缓冲器对 Cache和主存是透明的。在设计时，要处理好可能由它们所引起的错误 (如另一个处理机要访问的主存单元的内容正好仍在缓冲器中 )。
5)两种方法对比
a)写回法有利于省去许多将中间结果写入主存的无谓开销。但是增加了 Cache的复杂性。
b)可靠性上写回法不如写直达法好。
c)具体采用哪种方法还与系统使用场合有关。
d)如果让多 CPU共享主存交换信息改成共享 Cache
交换信息，信息的一致性就能得到保证。
e)对于共享主存的多 CPU系统，绝大多数还是采用各个 CPU都有自己的 Cache的方式与共享主存连接。这样的系统由于 Cache的透明性，仅靠写直达法并不能保证同一主存单元在各个 Cache中的对应内容都一致。如下图：
要采取措施保证让有此单元的各个 Cache的内容都一致才行。
CPU A Cache a
CPU B Cache b
主存
图 4.46 每个处理机都有 Cache的共享多处理机系统解决办法：
采用播写法：即任何处理机要写入 Cache时，不仅要写入自己 Cache的目标块和主存中，还把信息或者播写到所有 Cache有此单元的地方，或者让所有 Cache有此单元的块作废以便下次访问时按缺块处理，从主存中重新调入。
控制某些共享信息（如信号灯或作业队等）不等进入 Cache。
目录表法：即在 CPU读 /写 Cache不命中时，先查主存中的目录表以判定目录块是否在别的 Cache
内，以及是否正在被修改等，然后再决定如何读写此块。
6)第二种问题
Cache内容跟不上已变化了的主存内容的问题，有两种解决办法：
a)当 I/O处理机未经 Cache往主存写入新内容的同时，由 OS经某个专用指令清除整个 Cache。这种办法的缺点是象我们在讲述用专用指令清除快表一样，会使 Cache对 OS和系统程序员成为不透明的，因此并不好。
b)当 I/O处理机往主存某个区域写入新内容时，由专用硬件自动地将 Cache内对应此区域地副本作废，而不必由 OS进行任何干预，从而保持 Cache
的透明性。
2,Cache的取算法
1)预取法为了便于硬件实现，通常只预取直接顺序的下一块，即在访问到主存的第 i块 (不论是否已取进 Cache)
时，只有第 i＋ 1块才是可能的预取块。至于何时将该块取进，可以有恒预取和不命中时预取两种不同的方法。恒预取指的是只要访问到主存的第 i块的某个字，不论 Cache是否命中，恒发预取指令。不命中时预取仅当访问第 i块不命中时，才发预取指令。
2)影响命中率的其它因素
a)块的大小：
若每块的字节数过少，预取的效果不明显。从预取的需要出发，希望块尽可能大。但若每块的字节数过多，一方面可能会预取进不需要的信息，另一方面由于 Cache容量有限，又可能把正在使用或近期使用到的信息给替换出去，反而降低了命中率。
从模拟结果来看，每块的字节数如果超过了 256，就会出现这种情况。
b)预取开销：
要预取就要有访主存开销和将它取进 Cache的访
Cache开销，还要加上把被替换的块写回主存的开销，这些开销会增加主存和 Cache的负担，干扰和延缓程序的执行。
由上可知，采用预取法的效果不能只从命中率的提高来衡量，还需要从所花费的开销多少来考虑。
而这种开销的多少可以通过对按需取进法的不命中开销与预取法的不命中开销和预取开销 (包括访存开销及对 Cache的干扰影响 )二者之和的比较来得到。
3)计算 分析设 Dc为 Cache不命中时，由主存调一块进 Cache的开销，则：
a)按需取进法的不命中开销为：
Dc × 不命中率 (按需取进法 )
b)预取法不命中的开销为：
Dc × 不命中率 (预取法 )
而预取法还应有预取开销，为此，我们设：
预取率：预取总块数 /访存总块数
Pa,预取访主存和访 Cache的开销
c)预取法取进预取块的开销为：
Pa × 预取率
访问率：访 Cache的总次数 /程序访 Cache的总次数，即 (程序访 Cache次数＋预取访 Cache次数 )/程序访 Cache次数。
Ac：由于预取访 Cache占用了 Cache，延迟、干扰了程序对 Cache的访问的预取干扰开销。
d)预取法对程序访 Cache的映象为：
Ac× (访问率－ 1)
e)结论由上计算可知，只有下式成立，即：
Dc × 不命中率 (按需取进 ) >Dc × 不命中率 (预取 )
＋ Pa × 预取率
＋ Ac× (访问率－ 1)
时，预取法才是可取的。这里，采用缓冲器技术是减少预取干扰的好办法。 Cache和主存都设置预取专用缓冲器，使预取访主存与访 Cache都尽可能在主存,Cache空闲时进行。
3.任务切换对失效率的影响
1)两种失效率
a)冷启动 (Cold－ start)失效率：
从 Cache为空 (指新进程所需的内容都未装入 Cache
内 )开始到 Cache全部被装满这一期间的失效率。
b)热启动 (Warm－ start)失效率：
从 Cache为现行进程装满之后测出的失效率。
2)影响失效率的因素
a)与任务的切换频度 (平均时间间隔 Qsw)有关
Qsw对失效率的影响和工作负荷有很大关系。比如，如果进程切换发生在用户程序因为系统需要运行管理程序来处理某个 I/O中断或时钟中断请求时，
则 Qsw值愈小，表明由管理程序切换回原先的用户程序愈快,Cache中保留的原先程序的指令和数据就愈多，即失效率愈低。但是如果进程切换是在几个用户程序之间进行，且每个进程都要更换掉 Cache
中的大部分内容时,Qsw值愈小就会使失效率愈高。
b)与 Cache的容量有关
Qsw值一定时，若容量过小，存不下该程序的工作区，那么就会有很高的热启动失效率。因此，增大 Cache的容量可使这个矛盾迅速缓解，而使失效率急剧下降；但在容量增大到基本上保护得了足够大的工作区之后，容量大小对失效率的下降就趋于平缓，也就是说增大容量对降低失效率已影响不大。
3)解决办法
a)增大 Cache容量
b)修改调度算法，使任务切换回来前，有用的信息仍能保留在 Cache中而不被破坏。
c)设置多个 Cache，例如设置两个，一个专用于管理程序，一个专用于用户程序。这样，在管态和目态之间切换时，不会破坏各 Cache中的内容。
d)对于某些操作，例如长的向量运算、长的字符行运算等，可以不经过 Cache直接进行，以避免这些操作由于使用 Cache而从 Cache中替换出大量更有希望将重新使用的数据。
4.影响 Cache存贮器性能的因素
1)不命中率与 Cache的容量、组的大小和块的大小的一般关系不命中率 1－ Hc
Cache容量组的大小一定块的大小减小
(a)
不命中率 1－ Hc
Cache容量块的大小一定组的大小减小
(b)
图 4.47 块的大小、组的大小与 Cache容量对 Cache命中率的影响
2)Cache——主存存贮层次的等效速度与命中率的关系设,tc为 Cache的访问时间；
tm为主存周期；
Hc为访 Cache的命中率；
则 Cache存贮器的等效存贮周期为：
ta＝ Hc tc＋ (1 － Hc)tm
与主存 ——辅存存贮层次不同的是一旦 Cache不命中，由于主存与 CPU之间有直接通路,CPU对第二级的访问时间就是 tm，而不是调块时间再加一个访
Cache的时间了。这样，采用 Cache比之于处理机直接访问主存，其速度提高的倍数为：
ρ＝ tm / ta ＝ tm / (Hc tc＋ (1 － Hc)tm )
＝ 1/(1－ (1－ tc/tm)Hc)
因为 Hc总是小于 1，可以令 Hc＝ α/(α+1)，代入上式得：
ρ＝ (α+1)
显然，不管 Cache本身的速度有多高，只要 Cache
的命中率有限，那么采用 Cache——主存存贮层次后，速度能提高的最大值是有限的，不会超过 α+1
倍。
tm
tm + αtc
3)Cache的容量对机器速度的影响对流水机器，机器速度与主存速度,CPU拍宽、
Cache容量的可能关系如图 4.49所示，机器的单位是
MIPS(每秒执行百万条指令 )，主存采用多体交叉存取。
a)由图可见，主存速度和 CPU周期一定时，由不用 Cache到 Cache容量从 4KB增大到 64KB，机器速度有了显著提高，尤其是在主存速度较低时。
b)还可以看出,Cache容量的增大，可以显著降低对主存速度的要求。
4)总结总之,Cache本身的速度与容量都会影响 Cache存贮器的等效访问速度。如果对 Cache存贮器的等效访问速度不满意，需要改进的话就要作具体分析，
看看现在 Cache的等效访问速度是否已接近于第一级 Cache本身的访问速度。如果尚差的较远，说明
Cache的命中率低，这个时时就不是去采用更高速度的 Cache片子来替换现有的 Cache片子，而应当从提高 Cache的命中率入手，包括调整组的大小、替换算法以及增大 Cache容量等方面着手，否则该速度是无法提高的。相反的，如果实际的等效访问速度已经非常接近于 Cache本身的访问速度还不能满足速度要求时，就只有更换更高速的 Cache片子。
否则，任何其它途径也是不会有什么效果的。因此我们不能盲目设计和改进，否则花了很大代价，却反而降低了系统的性能价格比。
4.3.5“Cache—主存 —辅存”存贮层次
1.三级存贮层次的地址变换：
CPU提供访存的虚地址可能需要变换成 Cache地址、主存地址或辅存地址。
1)对应于虚地址的单元已在 Cache中这时就需要把虚地址直接变换成 Cache地址来访问
Cache，而不是先把虚地址变换成主存实地址，再由主存实地址变换成 Cache地址，这样可以缩短地址变换的时间。
2)对应单元已在主存但尚未调入 Cache
这时则需要把虚地址经快表和慢表变换成主存实地址去访主存，对读访问以及采用按写访问还必须进行虚地址到 Cache地址的映象或变换，以便把包含对应此单元所在的一块调入或替换进 Cache。
3)对应单元还不在主存这时就需要把虚地址变换成辅存实地址去辅存调页，同时还要将虚地址映象变换成主存实地址将页调入主存，以及把虚地址映象变换成 Cache地址，
将其中的一块装入 Cache。
2.访问 Cache过程在这三级存贮层次中通常总是让页的大小恰好时块的 2的幂倍，每一块的大小又是字的 2的幂倍。而且每次用虚页号查快表和慢表以取得主存实地址和用虚地址对应 Cache块号位置的虚块号经组相联去访 Cache(Cache中每个单元存放有主存实地址和对应的数据 )同时进行。若能在快表中找到，就用由快表来的主存实地址与由 Cache中读出的主存实地址相比较。当两者相符，存在 Cache中该单元的数据就是要访问的虚、实地址的内容。写 Cache的过程与此类似。
4.4 主存保护大多数计算机系统设计成让其资源能被并行的多个用户所共享，就主存来说，就同时存有多个用户的程序和系统软件。为使系统能正常工作，应防止由于一个用户程序出错而破坏主存中其它用户的程序或系统软件，还要防止一个用户程序不合法地访问不是分配给它的主存区域，哪怕这种访问不会引起系统破坏。因此，系统结构需要为主存的使用提供存贮保护，它是多道程序和多处理机系统所必不可少的。
1.存贮区域的保护
1)主存系统的保护对于不是虚拟存贮器的主存系统可采用第二章讲过的界限寄存器方式，由系统软件经特权指令置定上、下界寄存器，从而划定每个用户程序的区域，
禁止它越界访问。由于用户程序不能改变上、下界的值，因此不论它如何出错，也只能破坏该用户自身的程序，侵犯不到别的用户程序及系统软件。
2)虚拟存贮系统由于界限寄存器方式只适用于每个用户程序占用主存一个或几个 (当有多对上、下界寄存器时 )连续的区域；而对于虚拟存贮系统，由于一个用户的各页能离散地分布于主存内，从而无法使用这种保护方式。对虚拟存贮系统的主存区域保护就需要采用页表保护和键式保护等方式。
a)页表保护每个程序都有自己的页表，其行数等于该程序的虚页数。例如它有 4页，则只能有 0,1,2,3这 4个虚页号。设由 OS建立的程序也表，这 4个虚页号分别对应于实页号 4,8,10,14，则不论虚地址如何出错，总只能影响主存中分配给该程序的第 4,8,
10,14号实页。假设虚页号错成 5，肯定不可能在该程序的页表中找到，也就访问不了主存，当然就不会映象主存中其它程序的区域。这正是虚拟存贮系统本身固有的保护机能，也是它的一大优点。为了便于实现这种保护，还可以在段表中的每行内，不仅设置页表起点，还设置段长 (页数 )项。若出现该段内的虚页号大于段长，则可以发越界中断。
这种页表保护是在没有形成主存实地址前进行的保护，使之无法形成能侵犯别的程序区域的主存地址。然而，若地址形成环节由于软、硬件方面的故障而形成了不属于本程序区域的错误主存地址时，
则上述这种保护就无能为力了。因此，还应采取进一步的保护措施，键方式就是其中成功的一种。
b)键方式是由 OS按当时主存的使用分配状况给主存的每页配一个键，称为存贮键，它相当于一把“锁”。
所有页的存贮键存在于相应的快速寄存器内，每个用户 (任务 )的各实页的页存贮键都相同。为了打开这把锁，需要有把“钥匙”，称为访问键。每个用户的访问键由 OS给定，存在处理机的程序状态字 (PSW)
或控制寄存器中。程序每次访存前，要核对主存地址所在页的存贮键是否与该道程序的访问键相符，
只有相符才准访问。这样，就是错误地形成了侵犯别的程序的主存地址，也因为这种键保护而仍然不允许访问。
c)环状保护环状保护把系统程序和用户程序按其重要性及对整个系统能否正常工作的影响程度分层，如图 4.50
所示。设 0,1,2三层是系统程序的，之外的各层是同一用户程序的分层。环号大小表示保护的级别，
环号愈大，等级愈低。在现行程序运行前，先由 OS
定好程序各页的环号，并置入也表。而后把该道程序的开始环号送入处理机内的现行环号寄存器，并且把 OS规定给该程序的上限环号 (规定该程序所能进入的最内层环号 )也置入相应的寄存器。
若是 Pi在某一时候属于 i层各页的集合，则当进程执行 P∈ Pi页内的程序时，允许访问 F∈ Pj页，这里对应的是 j≥i。但是如果是 j<i时，则需由 OS环控制例行程序判定这个内向访问是否允许和是否正确之后才能访问，否则就是出错，进入保护处理。但 j值肯定不能小于给定的上限环号。只要 j≠i，就进入中断，若允许访问，则需经特权指令把现行环号寄存器的值由 i改为 j。
这种环式保护既能保证由于用户程序的出错不至于侵犯系统程序，也能保证由于同一用户程序内的低级 (环号大 )的部分的出错而不致破坏其高级 (环号小 )的部分。这种环式保护对系统程序的研究和调试运行特别有利，因为可以做到能修改系统程序的某些部分而不必担心会影响到系统程序已设计好并调好的核心部分。
至于如何控制 j≠i的跨层访问，有的机器规定只能由规定的转移指令执行，且对和 j>i和 j<i分别只能用不同的转移指令。
2.访问方式的保护上述种种区域保护，如判越界、判建相符、判环号相符、判不超出段长等等，都是经硬件实现的，
因此速度可以是很快的。这些区域保护是对允许访问的区域可以进行任何形式的访问，而对允许区域之外，则任何形式的访问都不允许。但在实际中，
只是这种限制往往适应不了各种应用的要求，因此还得加上访问方式的保护 (限制 )。
1)对主存信息的使用可以有读 R、写 W和执行 E三种方式。相应的就有 R,W,E访问方式保护，这 3
者的逻辑组合可以反映出各种应用要求，如：
R∪ W∪ E——不允许进行任何访问；
R∪ W∪ E——可以进行任何访问；
R∩W ∪ E——只能进行读访问；
R∪ W∩E ——只能按数据进行读写；
R∪ W∩E ——只能执行，不能作为数据使用；
R∪ E∩W ——只能进行写访问；
R∪ E∩W ——不准写访问。
2)对前面讲过的各种区域保护，都可以加上相应的访问方式位以实现这种访问限制。
3)至于环式保护和也表保护，可以把 R,W,E等访问方式位设在各个程序的段、页表的各行内，使得同一环内或同一段内的各页可以有上述种种不同的访问保护，以增强灵活性。
4)在某些应用中，我么既要求能实现多个用户可读、写访问共享的数据，但又要保证只当一个用户访问完该数据后，别的用户才可以访问，以防止在一个用户还未把某个共享文件写好之前，别的用户却能把它读了去。可以采用“测试与置定”和“比较与交换”指令实现这点。所以这也是一种保护方法。
第 4章小节
4.1 存贮体系的形成与性能
1.存贮器的性能要求
1)大容量
2)低价格
3)高速度访问时间 TA
存贮周期 TM
存贮器频宽
4)结论由于存贮器的价格、速度和容量的要求是相互矛盾的，为了同时满足三方面的要求，在一个完整的存贮体系中，必须采用不同工艺的存贮器，使得信息以各种方式分布于不同的存贮体。
2.并行主存系统频宽的分析
1)类型单体单字单体多字多体单字交叉多体多字交叉
2)分析结论由于程序的转移概率不会很低，数据分布的离散性较大，所以单纯靠增大 m来提高并行主存系统的频宽是有限的，而且性价比还会随 m的增大而下降。如果采用并行主存系统仍不能满足速度上的要求，就必须从系统结构上改进，采用存贮体系。
3.存贮体系的形成与分支
1)容量需求主存 —— 辅存存贮层次 程序局部性
2)速度需求
Cache——主存存贮层次 程序局部性
3)多级 存贮层次
4.存贮体系的性能参数
1)存贮体系的每位平均价格 c
2)命中率 H=R1/(R1+R2)
3)等效访问时间
TA=HTA1+(1-H)TA2
4.2虚拟存贮器
1.管理方式
1)段式管理
a)思想：
根据程序的模块性，把一个复杂的大程序分解成多个逻辑上相对独立的模块。
b)段表为了进行段式管理，每道程序都由一个断表 (映像表 )，以存放该程序各程序段装入主存的状况信息。
段名 (号 )：实际由于段号与行对应，省略掉装入位：表征是 (1)否 (0)已调入主存地址：调入主存时，在主存的起始 (绝对 )地址段长：段的大小，限制偏移越界访问方式：只读、可写、只执行，提供访问保护
c)段表基址寄存器断表长度,该道程序的断数 (断表行数 )
断表基地址,程序的断表在主存中的起始地址
d)虚拟地址基号 (程序号 ):断表在断表基址寄存器的位置段号,段在断表中的位置段内位移,所访问单元在段内的偏移
e)实主存管理表占用区域表可用区域表
f)可用区域分配算法首先分配算法最佳分配算法
2)页式管理思想,把主存空间和程序空间都机械的等分成固定大小的页 (页面大小因机器不同而异，一般在 512
到几 kB)然后按页顺序编号。
3)段页式管理思想：把内存机械的等分成固定大小的页，把程序按模块分段，每个段分成与主存页面大小相同的页，每道程序通过一个断表和相应于每段的一组页表来进行定位。
问题：二次查表，费时间
2.页式虚拟存贮器的构成
1)地址映像与变换
a)地址映像就是将虚存单元按某种规则装入 (定位于 )实存，
即建立多用户虚地址 NS与实存地址 np的对应关系。
b)地址变换指的是程序按这种映像关系装入实存后，在执行时多用户虚地址 NS如何变换成对应的实地址 np。
c)全相联映像让每道程序的任何虚页可以映像装入到主存的任何实页位置
2)替换算法
a)目的当辅存中的页面调入主存发生页面争用时，只有强制腾出主存中某页后才能接纳从辅存调来的新页面。替换算法就是解决具体从主存中选择哪一页作为被替换的页。
b)原则有高的主存命中率算法便于实现辅助软、硬件成本尽量低
c)常用算法随机算法 (Random,RAND)
先进先出算法 (First In First Out,FIFO)
近期最少使用算法 (Least Recently Used,LRU)
优化替换算法 (OPT)——衡量标准
d)堆栈型替换算法保证命中率随主存页数的增加只可能提高，至少不会下降。
e)页面失效频率法 (PFF)
根据各道程序运行中的主存页面失效率的高低,由
OS来动态调节分配给每道程序的实页数。
3)影响命命中率的因素
a)与替换算法有关
b)命中率与页地址流有关
c)与主存容量 (即分配给程序的主存页数 )有关
4)虚拟存贮器工作的全过程
P144图 4.25页式虚拟存贮器工作原理
3.页式虚拟存贮器实现中的问题
1)页面失效处理后援寄存器技术预判技术解决方法 替换算法页面大小不能过大
2)提高虚拟存贮器等效访问速度的措施快表 ——慢表散列快表 ——硬件实现散列函数
3)影响主存命中率和 CPU效率的某些因素
a)与 Sp有关
P150图 4.30 页面大小 Sp,容量 S1与命中率 H的关系曲线图
b)命中率与主存容量 S1有关
P151图 4.31命中率 H与容量 S1的关系图
c)与所采用的页面调度策略有关
4.3高速缓冲存贮器 (Cache)
1.基本结构特点,9个方面 (与虚拟存贮器对比 )
2.地址的映像与变换
1)全相联映像和变换
a)规则：主存中的任意一块均可映像装入到 Cache
内的任意一块的位置。
b)地址变换过程
c)优缺点块冲突率低；代价大，查表速度难以提高。
2)直接映像及其变换规则：主存中每一块只能映像到 Cache中唯一一个特定位置：主存的第 i块只能映像到第 imod2ncb块位置上。相当于把主存空间按 Cache空间分区，每区内各块只能按位置一一对应到 Cache相应位置上。
3)组相联映象及其变换规则：把主存按 Cache大小分区，整个 Cache是一区，每个区再分成相等的组，组内分块。组间直接映象，组内各块全相联映象。
4)段相联映象规则：把主存和 Cache分成具有相同的 Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象，实质上就是组相联映象的特例。
3.替换算法的实现
1)堆栈法思想：栈顶恒存放近期最久访问过的页的页号，
而栈底恒存放近期最久没有访问过的页的页号，即准备被替换掉的页的页号。按此思想组成一个硬件堆栈。
2)比较对法思路：让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到 LRU块。
4,Cache的透明性及性能分析
1)Cache的透明性分析
a)写回法在 CPU执行写操作时，只是把信息写入 Cache，
仅当需要被替换时，才将已经被写入过的 Cache块先送回主存，然后再调入新块。
b)写直达法也称为存直达法，它利用 Cache——主存存贮层次在处理机和主存之间的直接通路，每当处理机写入 Cache的同时，也通过此通路直接写入主存。
2) Cache的取算法
a)预取法
b)块的大小
c)预取开销
3)任务切换对失效率的影响
a)与任务的切换频度 (平均时间间隔 Qsw)有关
b)与 Cache的容量有关
4)影响 Cache存贮器性能的因素
a)不命中率与 Cache的容量、组的大小和块的大小的一般关系看 P168图 4.47块的大小、组的大小与 Cache容量对
Cache命中率的影响。
b)Cache——主存存贮层次的等效速度与命中率的关系
5.Cache——主存 ——辅存存贮层次
1)对应于虚地址的单元已在 Cache中
2)对应单元已在主存但尚未调入 Cache
3)对应单元还不在主存
4.4主存保护
1.存贮区域的保护
1)页表保护
2)键方式
3)环式保护
2.访问方式的保护第 4章习题处理
1.某虚拟存贮器共 8个页面，每页为 1024个字，时间主存为 4096个字，采用页表法进行地址映象。映象表内容如右图：
1)列出会发生页面失效的全部虚页号；
2)按以下虚地址计算主存实地址：
0,3728,1023,1024，
2055,7800,4096,6800。
实页号 装入位
1
1
0
0
1
0
1
0
3
1
2
3
2
1
0
0
【 分析 】 要找出会发生页面失效的全部虚页号，关键是搞清楚页表法进行地址映象所用的虚页表的构成。
要由虚地址计算出主存的实地址，首先应根据题意将虚、实地址中各个字段及其位数确定下来。由于虚拟存贮器共 8个页面，
每个页面大小为 1024字，
实页号 装入位
1
1
0
0
1
0
1
0
3
1
2
3
2
1
0
0
虚页号
0
1
2
3
4
5
6
7
可知，虚页号字段为 3位二进制位 (23＝ 8)，页内位移字段为 10位二进制位 (210＝ 1024)。由于虚实页面大小是一样的，实际主存为 4096个字，不难得到实页号字段为 2位 (22＝ 4)，页内位移为 10位 (210＝ 1024)，
所以：
虚页号 页内位移实页号 页内位移虚地址字段实地址字段
3位 10位
10位2位这样，根据题目所给的虚地址可以按下面方法来计算出虚页号和页内位移量。其中，虚页号为：
虚地址 /页面大小 ——取整数页内位移量为：
虚地址－虚页号 × 页面大小或,虚地址％页面大小 ——取余数计算主存实地址为：
实页号 × 页面大小＋页内位移量
【 解答 】 1)发生页面失效的全部虚页号就是映象表中装入位为 0的行所对应的虚页号，即 2,3,5,7。
2)由虚地址计算主存实地址的情况见下表：
虚地址 虚页号 页内位移 装入位 实页号 页内位移 实地址
0
3728
1023
1024
2055
7800
4096
6800
0
3
0
1
2
7
4
6
0
656
1023
0
7
632
0
656
1
0
1
1
0
0
1
1
3 0
页面失效
3 1023
1 0
页面失效页面失效
2 0
0 656
3072
无
4095
1024
2048
656
无无
2.设某程序保护 5个虚页，其页地址为 4,5,3,2，
2,5,1,3。当使用 LRU算法替换时，为获得最高的命中率，至少分配给该程序几个实页？其可能的最高命中率为多少？
【 分析 】 由于 LRU替换算法是堆栈型替换算法，因而随着分配给该道程序的实页数增加，实页命中率只会上升，至少是不会下降的。但是，当实页数增加到一定程度后，其命中率就不会再提高了。
如果要增加分配给该道程序的实页数，只会导致实存空间的利用率下降。所以，只要分别求出分配给该道程序不同实页数时的命中率，找出大到最高命中率时所分配的最少实页数即可。
【 解答 】 用堆栈对页地址流处理一次的过程如下表所示，其中 H表示命中率。
页地址流堆栈内容实页数
4 5 3 2 5 1 3 2 2 5 1 3
S(1)
S(2)
S(3)
S(4)
S(5)
S(6)
时间 t 1 2 3 4 5 6 7 8 9 10 11 12
n=1
n=2
n=3
n=4
n≥5
4 5 3 2 5 1 3 2 2 5 1 3
4 5 3 2 5 1 3 3 2 5 1
4 5 3 2 5 1 3 2 51
4 4 2 53 3 215
4 4 4 4 4 4 4
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
模拟结果表明，使用 LUR替换算法，对该程序至少应分配 4个实页。如果只分配 3个实页，其页面命中率只有 3/12，太低；而分配实页数多于 4页后，其页面命中率不会再有提高。所以，分配给该程序 4个实页即可，其可能的最高命中率为 H＝ 7/12。
作业：
1.存贮器最大频宽 模 m交叉编址 程序局部性堆栈型替换算法 最佳分配算法 段页式管理不命中预取法 组相联映象 写回法优化算法 环保护 键保护
7,15,18,19，
1)规则：主存中每一块只能映像到 Cache中唯一一个特定位置，如图所示，主存的第 i块只能映像到第 i mod2ncb块位置上。如图 4.35所示：
……
Cache
块位置 0
1
2ncb-1
主存块 0
1
2nmb-1
…
2ncb-1
块 2ncb+0
2ncb+1…
2·2ncb-1
块 2·2ncb+0…
3·2ncb-1…
…
0区
1区
2区
2nmb－ ncb-1区图 4.35 直接映象规则
2)变换 过程 主存块号 块内地址 主存地址
nmnmb nmr
ncb ncr Cache地址n
c
…
2ncb项相联比较不等块失效区号
…
0
1
2ncb-1
相等访 Cache
区号
(按地址访问存贮器 )
由
2ncb
中选
1
图 4.36 直接映象的地址变换过程
3)优缺点优点：
a)所需硬件简单，只需要容量较小的按地址访问的区号标志表存贮器和少量外比较电路，因此成本低。
b)访问 Cache与访问区号表、比较区号是否相符的操作是同时进行的。当 Cache命中时就意味着省去了地址变换所花费的时间。
缺点,直接映象法最致命的缺点就是 Cache的块冲突率很高。只要有两个或两个以上经常使用的块恰好被映象到 Cache的同一个块位置时，就会使得
Cache的命中率急剧下降。而且，即使此时 Cache
中有大量的空闲块存在，仍然会发生块失效和块冲突，无法使用 Cache中的空闲块，所以,Cache的利用率很低。正是因为这个原因才使得目前采用直接映象的 Cache存贮器很少了。
3.组相联映象及其变换
1)思想：简要说明如下图 4.37所示，将 Cache空间和主存空间都分组，每组 S块 (S＝ 2s)。 Cache一共
2ncb个块，分成 Q组 (Q= 2q)，整个 Cache是一区。
主存分成与 Cache一样大小的 2nd个区，其地址按区号、组号、组内块号、块内地址分成对应的 4个字段。主存地址的组号、组内块号分别用 q,s' 字段表示，它们的宽度和位置与 Cache地址的 q,s
是一致的。
2)规则：组相联映象指的是各组之间直接映象，但组内各块间则是全相联映象。如图 4.37所示。
组号
q
组内块号
s
块内地址
ncr 组号 q 组内块号 s' 块内地址 nmr区号 nd
1位 1位2位 2位1位
ncb nmb
nc nm
块位置 0
块 0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
9
10
11
12
13
14
15
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
第 0组第 0组第 1组第 1组第 0组第 1组第 0区
(Cache容量 )
第 1区
(Cache容量 )
Cache
主存组内全相联组间直接相联图 4.37 组相联映象规则
3)讨论当组相联映象的 S值大到等于 Cache的块数 (即 s= ncb)
时就变成了全相联映象，而当 S值小到只有 1块 (即无 s
字段 )时就变成了直接映象。因此全相联映象和直接映象只是组相联映象的两个极端。在 Cache空间大小及块的大小都已经确定的情况下,Cache的总块数就定了，但结构设计者仍可以对 S和 Q值进行选择。 Q和 S
的选取主要依据对块冲突概率、块失效率、映象表复杂性和成本、查表速度等的折衷权衡。组内块数 S愈多，块冲突概率和块失效率愈低，映象表愈复杂、成本愈高，查表速度愈慢。所以通常采用在典型工作负荷下进行模拟而定。
4)地址变换组号
q
组内块号
s'
块内地址
nmr
区号
nd
组号
q
组内块号
s
块内地址
ncr
nm
nc
直接直接相联比较不等块失效 相等?
相联比较
nd s' s
nd ＋ s'
表的总容量为
2ncb ＝ 2q·2s行
2q
组中选
1
2s行
4.段相联映象在全相联、直接相联、组相联映象的基础上还可以有各种变形，段相联就是一例。段相联实质上是组相联的特例。他是采用组间全相联、组内直接映象。为了与组相联加以区别，将这种映象方式称为段相联。就是说，段相联映象是把主存和 Cache分成具有相同的 Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象。如图 4.42
所示：
块 0
块 1
块 2
Z－ 1
Cache
主存
…
块 0
块 1
块 2
Z－ 1
…
≈≈
块 0
块 1
块 2
Z－ 1
…
块 0
块 1
块 2
Z－ 1
…
≈≈
块 0
块 1
块 2
Z－ 1
…
段 0
段 0(Z个段 )
段 1
段 2nmb/Z－ 1
段 2ncb/Z－ 1
图 4.42 具有每段 Z个块的断相联映象段间全相联段内直接
4.3.3替换算法的实现当访存发生 Cache块失效，需要把主存块按所采用的映象规则装入 Cache时，如果又出现 Cache块冲突，就必须按某种策略选择将 Cache中的哪一块替换出去。 Cache——主存存贮层次的替换算法与虚拟存贮器的没有什么不同，不外乎也是 FIFO法或
LRU法，其中 LRU法最为常用。
1.堆栈法
1)思想我们在 4.2.2中讲过,LRU法是堆栈型替换算法，
也讲了对于 LRU算法，堆栈 St中由栈顶到栈底的各项（行）恒反映出到 t时刻，实存中各页被访问过的近远次序，以及每访问一页，堆栈 St中各项的变换过程。结果是此堆栈的栈顶恒存放近期最近访问过的页的页号，而栈底恒存放近期最久没有方问过的页的页号，即准备被替换掉的页的页号。那么，我们在 Cache——主存存贮层次中就可以按此思想实际组成一个硬件堆栈。
2)过程
（块号）
（块号）
（块号）
（块号）
（块号）
2ncb个寄存器需重新排列的块号都下推一行被访问的块号
（经相联比较找到）
寄存器堆栈压入
ncb位近期最近访问过的块近期最久没有访问过的块图 4.43 全相联映象 LRU法经堆栈实现（需要有相联比较功能）
3)缺点：
这种硬件堆栈既要求具有相联比较的功能，又要求能全下移、部分下移和从中间取出一项的功能，
成本较高，因此只适用于组相联且组内块数较少的
LRU替换场合。
4)变形上述这种堆栈，各块被访问的先后次序由该项在堆栈中距离栈底是近还是远来反映。为了避免堆栈中各行存放的内容经常同时进行下移，以便节省成本，我们采用另一种变形，即将存放块号的寄存器的几何位置与 Cache中的块号对应，而用寄存器存放值的大小来表示已被访问过的远近次序。以组相联为例，每一组均使用如图 4.44那样的一个寄存器组，由 2s个寄存器组成，每个寄存器为 s位宽，可以存放表示从 0到 2s－ 1的次序值。如果让越是最近访问的，其次序值愈小，则只需通过相联比较求最大值（不是相联比较相符），找到该最大值所在的寄存器号，这就是对应 Cache中应该被替换掉的块的块号。
第 0块的访问次序第 1块的访问次序第 2块的访问次序第 2s-1块的访问次序块 0
块 1
块 2
块 2s-1
2s个寄存器
S位
（其中一组）
Cache存贮器
（其中一组）
图 4.44 组相联 LRU法经寄存器实现
（每组一个，需要有相联比较功能）
2.比较对法
1)思路比较法的基本思路是让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到 LRU块。比如说有 A B
C三块，互相之间可以组合成 AB BA AC CA BC
CB6对，其中 AB和 BA,AC和 CA,BC和 CB是重复的，所以 TAB为,1”，表示 A比 B更近被访问过；
TAB
为,0”，则表示 B比 A更近被访问过。 TAC,TBC也类似定义。这样，当访问过的次序为 A B C，即最近访问过的为 A，最久未被访问过的为 C，则这三个触发器状态分别为 TAB＝ 1,TAC＝ 1,TBC＝ 1。如果访问过的次序为 B A C,C为最久未被访问过的块，则此时必有 TAB＝ 0,TAC＝ 1,TBC＝ 1。因此最久未被访问过的块 C作为被替换掉的块的话，用布尔代数式必有：
CLRU＝ TAB? TAC?TBC +TAB? TAC?TBC ＝ TAC?TBC
同理可得：
BLRU＝ TAB?TBC ； ALRU＝ TAB? TAC
因此，完全可以用门、触发器等硬件组合实现，如图 4.45所示：
& & &
0 1 0 1 0 1
TAB TAC TBC
ALRU BLRU CLRU
访问 B
访问 C
访问 A
图 4.15 用比较对法实现 LRU算法
2)分析我们来看比较对法所用的硬件量。由于每块均可能作为 LRU块，其信号需要用一个与门产生，例如
ALRU与门要有从 TAB TAC来的输入,BLRU门要有从
TAB,TBC来的输入，而与每块有关的对数个数为块数减去 1，所以与门的扇入数是块数减去 1。若 p为块数，量量组合，比较对触发器的个数应为 Cp2，即为 p(p-1)/2。表 4.2给出了比较对法块数 p的取值与门数、门的输入端数及比较对触发器数的关系。
3)总结替换算法实现的设计要围绕下面两点来考虑：
a)如何对每次访问进行记录（使用位法、堆栈法和比较对法所用的记录方法都不同）；
b)如何根据所记录的信息来判定近期内哪一块最久没有被访问过。由此可见，实现方法和所用的映象方法密切相关。
例如，对于主存 ——辅存存贮层次的全相联映象宜于采用使用位法或类似的方法，而不宜采用堆栈法和比较对法；但对于 Cache——主存存贮层次的组相联映象，因为组内块数较少，就宜于采用比较对法或堆栈法。替换算法的设计和实现也和器件的发展密切相关，随着器件技术的发展，尤其是高速相联存贮器片子的改进，已经而且必然会不断研制出新的更好的实现方法。
4.3.4 Cache的透明性及性能分析
1.Cache的透明性分析
1)两种问题的出现虽然 Cache是主存的一部分副本，主存中某单元的内容却可能在一段时间里会与 Cache中对应单元的内容不一致。例如,CPU往 Cache写入，修改了 Cache
中某单元的内容，而在主存中对应于此单元的内容却可能仍是原来的，没有改变。这时，如果 CPU或
I/O处理机及其他处理机要经主存交换信息，那么主存内容跟不上 Cache对应内容变化的这种不一致就会造成错误。
同样,I/O处理机或其他处理机已把新的内容送入主存某个区域，而 Cache中对应于此区域的副本内容却仍可能是原来的。这时，如果 CPU要从 Cache
中读取信息，也会因为这种 Cache内容跟不上主存对应内容变化的不一致而造成错误。因此，必须采取措施解决好由于读写过程中产生的 Cache和主存对应内容不一致的问题。
2)写回法写回法是在 CPU执行写操作时，只是把信息写入
Cache，仅当需要被替换时，才将已经被写入过的
Cache块先送回主存，然后再调入新块。这种方法也称为抵触修改法，类似于虚拟存贮器中进行页面替换时的情况。因此,Cache——主存存贮层次的地址映象表中需对 Cache中的每个块设置一个“修改位”，作为该块装入 Cache后是否被修改过的标志。
这样在块替换时，根据该块的修改位是否位 1，就可以决定替换时是否先将该块存回主存原来的位置。
3)写直达法写直达法也称为存直达法，它利用 Cache——主存存贮层次在处理机和主存之间的直接通路，每当处理机写入 Cache的同时，也通过此通路直接写入主存。这样，在块替换时，就不必先写回主存，而可以立即调入新页。显然，写回法是把开销花在每次需要替换的时候，而写直达法则把开销花在每次写入 Cache时都附加一个比写 Cache长的多的写主存时间。
4)写不命中处理当出现写不命中时，无论是写回法还是写直达法都有一个在写时是否取的问题。一种是不按写分配法，即当 Cache写不命中时只写入主存，该写地址单元所在块不从主存调进 Cache。另一种是按写分配法，即当 Cache不命中时除写入主存外，还把该写地址单元所在的块由主存调入 Cache。这两种策略对不同的主存修改算法，其效果不同，但命中率差别不大。目前写回法一般采用按写分配法，而写直达法则一般采用不按写分配法。
写回法和写直达法都需要有少量缓冲器。写回法中缓冲器用于暂存将要写回的块，使之不必等待被替换块写回主存后才开始进行 Cache取。写直达法中缓冲器则用于缓冲由写 Cache所要求的写回主存的内容，使 CPU不必等待这些写主存完成就能往下运行。缓冲器由要存的数据和要存入的目标地址组成。在写直达系统中容量为 4的缓冲器就可以显著改进其性能,IBM 3033就是这样用的。要注意的这些缓冲器对 Cache和主存是透明的。在设计时，要处理好可能由它们所引起的错误 (如另一个处理机要访问的主存单元的内容正好仍在缓冲器中 )。
5)两种方法对比
a)写回法有利于省去许多将中间结果写入主存的无谓开销。但是增加了 Cache的复杂性。
b)可靠性上写回法不如写直达法好。
c)具体采用哪种方法还与系统使用场合有关。
d)如果让多 CPU共享主存交换信息改成共享 Cache
交换信息，信息的一致性就能得到保证。
e)对于共享主存的多 CPU系统，绝大多数还是采用各个 CPU都有自己的 Cache的方式与共享主存连接。这样的系统由于 Cache的透明性，仅靠写直达法并不能保证同一主存单元在各个 Cache中的对应内容都一致。如下图：
要采取措施保证让有此单元的各个 Cache的内容都一致才行。
CPU A Cache a
CPU B Cache b
主存
图 4.46 每个处理机都有 Cache的共享多处理机系统解决办法：
采用播写法：即任何处理机要写入 Cache时，不仅要写入自己 Cache的目标块和主存中，还把信息或者播写到所有 Cache有此单元的地方，或者让所有 Cache有此单元的块作废以便下次访问时按缺块处理，从主存中重新调入。
控制某些共享信息（如信号灯或作业队等）不等进入 Cache。
目录表法：即在 CPU读 /写 Cache不命中时，先查主存中的目录表以判定目录块是否在别的 Cache
内，以及是否正在被修改等，然后再决定如何读写此块。
6)第二种问题
Cache内容跟不上已变化了的主存内容的问题，有两种解决办法：
a)当 I/O处理机未经 Cache往主存写入新内容的同时，由 OS经某个专用指令清除整个 Cache。这种办法的缺点是象我们在讲述用专用指令清除快表一样，会使 Cache对 OS和系统程序员成为不透明的，因此并不好。
b)当 I/O处理机往主存某个区域写入新内容时，由专用硬件自动地将 Cache内对应此区域地副本作废，而不必由 OS进行任何干预，从而保持 Cache
的透明性。
2,Cache的取算法
1)预取法为了便于硬件实现，通常只预取直接顺序的下一块，即在访问到主存的第 i块 (不论是否已取进 Cache)
时，只有第 i＋ 1块才是可能的预取块。至于何时将该块取进，可以有恒预取和不命中时预取两种不同的方法。恒预取指的是只要访问到主存的第 i块的某个字，不论 Cache是否命中，恒发预取指令。不命中时预取仅当访问第 i块不命中时，才发预取指令。
2)影响命中率的其它因素
a)块的大小：
若每块的字节数过少，预取的效果不明显。从预取的需要出发，希望块尽可能大。但若每块的字节数过多，一方面可能会预取进不需要的信息，另一方面由于 Cache容量有限，又可能把正在使用或近期使用到的信息给替换出去，反而降低了命中率。
从模拟结果来看，每块的字节数如果超过了 256，就会出现这种情况。
b)预取开销：
要预取就要有访主存开销和将它取进 Cache的访
Cache开销，还要加上把被替换的块写回主存的开销，这些开销会增加主存和 Cache的负担，干扰和延缓程序的执行。
由上可知，采用预取法的效果不能只从命中率的提高来衡量，还需要从所花费的开销多少来考虑。
而这种开销的多少可以通过对按需取进法的不命中开销与预取法的不命中开销和预取开销 (包括访存开销及对 Cache的干扰影响 )二者之和的比较来得到。
3)计算 分析设 Dc为 Cache不命中时，由主存调一块进 Cache的开销，则：
a)按需取进法的不命中开销为：
Dc × 不命中率 (按需取进法 )
b)预取法不命中的开销为：
Dc × 不命中率 (预取法 )
而预取法还应有预取开销，为此，我们设：
预取率：预取总块数 /访存总块数
Pa,预取访主存和访 Cache的开销
c)预取法取进预取块的开销为：
Pa × 预取率
访问率：访 Cache的总次数 /程序访 Cache的总次数，即 (程序访 Cache次数＋预取访 Cache次数 )/程序访 Cache次数。
Ac：由于预取访 Cache占用了 Cache，延迟、干扰了程序对 Cache的访问的预取干扰开销。
d)预取法对程序访 Cache的映象为：
Ac× (访问率－ 1)
e)结论由上计算可知，只有下式成立，即：
Dc × 不命中率 (按需取进 ) >Dc × 不命中率 (预取 )
＋ Pa × 预取率
＋ Ac× (访问率－ 1)
时，预取法才是可取的。这里，采用缓冲器技术是减少预取干扰的好办法。 Cache和主存都设置预取专用缓冲器，使预取访主存与访 Cache都尽可能在主存,Cache空闲时进行。
3.任务切换对失效率的影响
1)两种失效率
a)冷启动 (Cold－ start)失效率：
从 Cache为空 (指新进程所需的内容都未装入 Cache
内 )开始到 Cache全部被装满这一期间的失效率。
b)热启动 (Warm－ start)失效率：
从 Cache为现行进程装满之后测出的失效率。
2)影响失效率的因素
a)与任务的切换频度 (平均时间间隔 Qsw)有关
Qsw对失效率的影响和工作负荷有很大关系。比如，如果进程切换发生在用户程序因为系统需要运行管理程序来处理某个 I/O中断或时钟中断请求时，
则 Qsw值愈小，表明由管理程序切换回原先的用户程序愈快,Cache中保留的原先程序的指令和数据就愈多，即失效率愈低。但是如果进程切换是在几个用户程序之间进行，且每个进程都要更换掉 Cache
中的大部分内容时,Qsw值愈小就会使失效率愈高。
b)与 Cache的容量有关
Qsw值一定时，若容量过小，存不下该程序的工作区，那么就会有很高的热启动失效率。因此，增大 Cache的容量可使这个矛盾迅速缓解，而使失效率急剧下降；但在容量增大到基本上保护得了足够大的工作区之后，容量大小对失效率的下降就趋于平缓，也就是说增大容量对降低失效率已影响不大。
3)解决办法
a)增大 Cache容量
b)修改调度算法，使任务切换回来前，有用的信息仍能保留在 Cache中而不被破坏。
c)设置多个 Cache，例如设置两个，一个专用于管理程序，一个专用于用户程序。这样，在管态和目态之间切换时，不会破坏各 Cache中的内容。
d)对于某些操作，例如长的向量运算、长的字符行运算等，可以不经过 Cache直接进行，以避免这些操作由于使用 Cache而从 Cache中替换出大量更有希望将重新使用的数据。
4.影响 Cache存贮器性能的因素
1)不命中率与 Cache的容量、组的大小和块的大小的一般关系不命中率 1－ Hc
Cache容量组的大小一定块的大小减小
(a)
不命中率 1－ Hc
Cache容量块的大小一定组的大小减小
(b)
图 4.47 块的大小、组的大小与 Cache容量对 Cache命中率的影响
2)Cache——主存存贮层次的等效速度与命中率的关系设,tc为 Cache的访问时间；
tm为主存周期；
Hc为访 Cache的命中率；
则 Cache存贮器的等效存贮周期为：
ta＝ Hc tc＋ (1 － Hc)tm
与主存 ——辅存存贮层次不同的是一旦 Cache不命中，由于主存与 CPU之间有直接通路,CPU对第二级的访问时间就是 tm，而不是调块时间再加一个访
Cache的时间了。这样，采用 Cache比之于处理机直接访问主存，其速度提高的倍数为：
ρ＝ tm / ta ＝ tm / (Hc tc＋ (1 － Hc)tm )
＝ 1/(1－ (1－ tc/tm)Hc)
因为 Hc总是小于 1，可以令 Hc＝ α/(α+1)，代入上式得：
ρ＝ (α+1)
显然，不管 Cache本身的速度有多高，只要 Cache
的命中率有限，那么采用 Cache——主存存贮层次后，速度能提高的最大值是有限的，不会超过 α+1
倍。
tm
tm + αtc
3)Cache的容量对机器速度的影响对流水机器，机器速度与主存速度,CPU拍宽、
Cache容量的可能关系如图 4.49所示，机器的单位是
MIPS(每秒执行百万条指令 )，主存采用多体交叉存取。
a)由图可见，主存速度和 CPU周期一定时，由不用 Cache到 Cache容量从 4KB增大到 64KB，机器速度有了显著提高，尤其是在主存速度较低时。
b)还可以看出,Cache容量的增大，可以显著降低对主存速度的要求。
4)总结总之,Cache本身的速度与容量都会影响 Cache存贮器的等效访问速度。如果对 Cache存贮器的等效访问速度不满意，需要改进的话就要作具体分析，
看看现在 Cache的等效访问速度是否已接近于第一级 Cache本身的访问速度。如果尚差的较远，说明
Cache的命中率低，这个时时就不是去采用更高速度的 Cache片子来替换现有的 Cache片子，而应当从提高 Cache的命中率入手，包括调整组的大小、替换算法以及增大 Cache容量等方面着手，否则该速度是无法提高的。相反的，如果实际的等效访问速度已经非常接近于 Cache本身的访问速度还不能满足速度要求时，就只有更换更高速的 Cache片子。
否则，任何其它途径也是不会有什么效果的。因此我们不能盲目设计和改进，否则花了很大代价，却反而降低了系统的性能价格比。
4.3.5“Cache—主存 —辅存”存贮层次
1.三级存贮层次的地址变换：
CPU提供访存的虚地址可能需要变换成 Cache地址、主存地址或辅存地址。
1)对应于虚地址的单元已在 Cache中这时就需要把虚地址直接变换成 Cache地址来访问
Cache，而不是先把虚地址变换成主存实地址，再由主存实地址变换成 Cache地址，这样可以缩短地址变换的时间。
2)对应单元已在主存但尚未调入 Cache
这时则需要把虚地址经快表和慢表变换成主存实地址去访主存，对读访问以及采用按写访问还必须进行虚地址到 Cache地址的映象或变换，以便把包含对应此单元所在的一块调入或替换进 Cache。
3)对应单元还不在主存这时就需要把虚地址变换成辅存实地址去辅存调页，同时还要将虚地址映象变换成主存实地址将页调入主存，以及把虚地址映象变换成 Cache地址，
将其中的一块装入 Cache。
2.访问 Cache过程在这三级存贮层次中通常总是让页的大小恰好时块的 2的幂倍，每一块的大小又是字的 2的幂倍。而且每次用虚页号查快表和慢表以取得主存实地址和用虚地址对应 Cache块号位置的虚块号经组相联去访 Cache(Cache中每个单元存放有主存实地址和对应的数据 )同时进行。若能在快表中找到，就用由快表来的主存实地址与由 Cache中读出的主存实地址相比较。当两者相符，存在 Cache中该单元的数据就是要访问的虚、实地址的内容。写 Cache的过程与此类似。
4.4 主存保护大多数计算机系统设计成让其资源能被并行的多个用户所共享，就主存来说，就同时存有多个用户的程序和系统软件。为使系统能正常工作，应防止由于一个用户程序出错而破坏主存中其它用户的程序或系统软件，还要防止一个用户程序不合法地访问不是分配给它的主存区域，哪怕这种访问不会引起系统破坏。因此，系统结构需要为主存的使用提供存贮保护，它是多道程序和多处理机系统所必不可少的。
1.存贮区域的保护
1)主存系统的保护对于不是虚拟存贮器的主存系统可采用第二章讲过的界限寄存器方式，由系统软件经特权指令置定上、下界寄存器，从而划定每个用户程序的区域，
禁止它越界访问。由于用户程序不能改变上、下界的值，因此不论它如何出错，也只能破坏该用户自身的程序，侵犯不到别的用户程序及系统软件。
2)虚拟存贮系统由于界限寄存器方式只适用于每个用户程序占用主存一个或几个 (当有多对上、下界寄存器时 )连续的区域；而对于虚拟存贮系统，由于一个用户的各页能离散地分布于主存内，从而无法使用这种保护方式。对虚拟存贮系统的主存区域保护就需要采用页表保护和键式保护等方式。
a)页表保护每个程序都有自己的页表，其行数等于该程序的虚页数。例如它有 4页，则只能有 0,1,2,3这 4个虚页号。设由 OS建立的程序也表，这 4个虚页号分别对应于实页号 4,8,10,14，则不论虚地址如何出错，总只能影响主存中分配给该程序的第 4,8,
10,14号实页。假设虚页号错成 5，肯定不可能在该程序的页表中找到，也就访问不了主存，当然就不会映象主存中其它程序的区域。这正是虚拟存贮系统本身固有的保护机能，也是它的一大优点。为了便于实现这种保护，还可以在段表中的每行内，不仅设置页表起点，还设置段长 (页数 )项。若出现该段内的虚页号大于段长，则可以发越界中断。
这种页表保护是在没有形成主存实地址前进行的保护，使之无法形成能侵犯别的程序区域的主存地址。然而，若地址形成环节由于软、硬件方面的故障而形成了不属于本程序区域的错误主存地址时，
则上述这种保护就无能为力了。因此，还应采取进一步的保护措施，键方式就是其中成功的一种。
b)键方式是由 OS按当时主存的使用分配状况给主存的每页配一个键，称为存贮键，它相当于一把“锁”。
所有页的存贮键存在于相应的快速寄存器内，每个用户 (任务 )的各实页的页存贮键都相同。为了打开这把锁，需要有把“钥匙”，称为访问键。每个用户的访问键由 OS给定，存在处理机的程序状态字 (PSW)
或控制寄存器中。程序每次访存前，要核对主存地址所在页的存贮键是否与该道程序的访问键相符，
只有相符才准访问。这样，就是错误地形成了侵犯别的程序的主存地址，也因为这种键保护而仍然不允许访问。
c)环状保护环状保护把系统程序和用户程序按其重要性及对整个系统能否正常工作的影响程度分层，如图 4.50
所示。设 0,1,2三层是系统程序的，之外的各层是同一用户程序的分层。环号大小表示保护的级别，
环号愈大，等级愈低。在现行程序运行前，先由 OS
定好程序各页的环号，并置入也表。而后把该道程序的开始环号送入处理机内的现行环号寄存器，并且把 OS规定给该程序的上限环号 (规定该程序所能进入的最内层环号 )也置入相应的寄存器。
若是 Pi在某一时候属于 i层各页的集合，则当进程执行 P∈ Pi页内的程序时，允许访问 F∈ Pj页，这里对应的是 j≥i。但是如果是 j<i时，则需由 OS环控制例行程序判定这个内向访问是否允许和是否正确之后才能访问，否则就是出错，进入保护处理。但 j值肯定不能小于给定的上限环号。只要 j≠i，就进入中断，若允许访问，则需经特权指令把现行环号寄存器的值由 i改为 j。
这种环式保护既能保证由于用户程序的出错不至于侵犯系统程序，也能保证由于同一用户程序内的低级 (环号大 )的部分的出错而不致破坏其高级 (环号小 )的部分。这种环式保护对系统程序的研究和调试运行特别有利，因为可以做到能修改系统程序的某些部分而不必担心会影响到系统程序已设计好并调好的核心部分。
至于如何控制 j≠i的跨层访问，有的机器规定只能由规定的转移指令执行，且对和 j>i和 j<i分别只能用不同的转移指令。
2.访问方式的保护上述种种区域保护，如判越界、判建相符、判环号相符、判不超出段长等等，都是经硬件实现的，
因此速度可以是很快的。这些区域保护是对允许访问的区域可以进行任何形式的访问，而对允许区域之外，则任何形式的访问都不允许。但在实际中，
只是这种限制往往适应不了各种应用的要求，因此还得加上访问方式的保护 (限制 )。
1)对主存信息的使用可以有读 R、写 W和执行 E三种方式。相应的就有 R,W,E访问方式保护，这 3
者的逻辑组合可以反映出各种应用要求，如：
R∪ W∪ E——不允许进行任何访问；
R∪ W∪ E——可以进行任何访问；
R∩W ∪ E——只能进行读访问；
R∪ W∩E ——只能按数据进行读写；
R∪ W∩E ——只能执行，不能作为数据使用；
R∪ E∩W ——只能进行写访问；
R∪ E∩W ——不准写访问。
2)对前面讲过的各种区域保护，都可以加上相应的访问方式位以实现这种访问限制。
3)至于环式保护和也表保护，可以把 R,W,E等访问方式位设在各个程序的段、页表的各行内，使得同一环内或同一段内的各页可以有上述种种不同的访问保护，以增强灵活性。
4)在某些应用中，我么既要求能实现多个用户可读、写访问共享的数据，但又要保证只当一个用户访问完该数据后，别的用户才可以访问，以防止在一个用户还未把某个共享文件写好之前，别的用户却能把它读了去。可以采用“测试与置定”和“比较与交换”指令实现这点。所以这也是一种保护方法。
第 4章小节
4.1 存贮体系的形成与性能
1.存贮器的性能要求
1)大容量
2)低价格
3)高速度访问时间 TA
存贮周期 TM
存贮器频宽
4)结论由于存贮器的价格、速度和容量的要求是相互矛盾的，为了同时满足三方面的要求，在一个完整的存贮体系中，必须采用不同工艺的存贮器，使得信息以各种方式分布于不同的存贮体。
2.并行主存系统频宽的分析
1)类型单体单字单体多字多体单字交叉多体多字交叉
2)分析结论由于程序的转移概率不会很低，数据分布的离散性较大，所以单纯靠增大 m来提高并行主存系统的频宽是有限的，而且性价比还会随 m的增大而下降。如果采用并行主存系统仍不能满足速度上的要求，就必须从系统结构上改进，采用存贮体系。
3.存贮体系的形成与分支
1)容量需求主存 —— 辅存存贮层次 程序局部性
2)速度需求
Cache——主存存贮层次 程序局部性
3)多级 存贮层次
4.存贮体系的性能参数
1)存贮体系的每位平均价格 c
2)命中率 H=R1/(R1+R2)
3)等效访问时间
TA=HTA1+(1-H)TA2
4.2虚拟存贮器
1.管理方式
1)段式管理
a)思想：
根据程序的模块性，把一个复杂的大程序分解成多个逻辑上相对独立的模块。
b)段表为了进行段式管理，每道程序都由一个断表 (映像表 )，以存放该程序各程序段装入主存的状况信息。
段名 (号 )：实际由于段号与行对应，省略掉装入位：表征是 (1)否 (0)已调入主存地址：调入主存时，在主存的起始 (绝对 )地址段长：段的大小，限制偏移越界访问方式：只读、可写、只执行，提供访问保护
c)段表基址寄存器断表长度,该道程序的断数 (断表行数 )
断表基地址,程序的断表在主存中的起始地址
d)虚拟地址基号 (程序号 ):断表在断表基址寄存器的位置段号,段在断表中的位置段内位移,所访问单元在段内的偏移
e)实主存管理表占用区域表可用区域表
f)可用区域分配算法首先分配算法最佳分配算法
2)页式管理思想,把主存空间和程序空间都机械的等分成固定大小的页 (页面大小因机器不同而异，一般在 512
到几 kB)然后按页顺序编号。
3)段页式管理思想：把内存机械的等分成固定大小的页，把程序按模块分段，每个段分成与主存页面大小相同的页，每道程序通过一个断表和相应于每段的一组页表来进行定位。
问题：二次查表，费时间
2.页式虚拟存贮器的构成
1)地址映像与变换
a)地址映像就是将虚存单元按某种规则装入 (定位于 )实存，
即建立多用户虚地址 NS与实存地址 np的对应关系。
b)地址变换指的是程序按这种映像关系装入实存后，在执行时多用户虚地址 NS如何变换成对应的实地址 np。
c)全相联映像让每道程序的任何虚页可以映像装入到主存的任何实页位置
2)替换算法
a)目的当辅存中的页面调入主存发生页面争用时，只有强制腾出主存中某页后才能接纳从辅存调来的新页面。替换算法就是解决具体从主存中选择哪一页作为被替换的页。
b)原则有高的主存命中率算法便于实现辅助软、硬件成本尽量低
c)常用算法随机算法 (Random,RAND)
先进先出算法 (First In First Out,FIFO)
近期最少使用算法 (Least Recently Used,LRU)
优化替换算法 (OPT)——衡量标准
d)堆栈型替换算法保证命中率随主存页数的增加只可能提高，至少不会下降。
e)页面失效频率法 (PFF)
根据各道程序运行中的主存页面失效率的高低,由
OS来动态调节分配给每道程序的实页数。
3)影响命命中率的因素
a)与替换算法有关
b)命中率与页地址流有关
c)与主存容量 (即分配给程序的主存页数 )有关
4)虚拟存贮器工作的全过程
P144图 4.25页式虚拟存贮器工作原理
3.页式虚拟存贮器实现中的问题
1)页面失效处理后援寄存器技术预判技术解决方法 替换算法页面大小不能过大
2)提高虚拟存贮器等效访问速度的措施快表 ——慢表散列快表 ——硬件实现散列函数
3)影响主存命中率和 CPU效率的某些因素
a)与 Sp有关
P150图 4.30 页面大小 Sp,容量 S1与命中率 H的关系曲线图
b)命中率与主存容量 S1有关
P151图 4.31命中率 H与容量 S1的关系图
c)与所采用的页面调度策略有关
4.3高速缓冲存贮器 (Cache)
1.基本结构特点,9个方面 (与虚拟存贮器对比 )
2.地址的映像与变换
1)全相联映像和变换
a)规则：主存中的任意一块均可映像装入到 Cache
内的任意一块的位置。
b)地址变换过程
c)优缺点块冲突率低；代价大，查表速度难以提高。
2)直接映像及其变换规则：主存中每一块只能映像到 Cache中唯一一个特定位置：主存的第 i块只能映像到第 imod2ncb块位置上。相当于把主存空间按 Cache空间分区，每区内各块只能按位置一一对应到 Cache相应位置上。
3)组相联映象及其变换规则：把主存按 Cache大小分区，整个 Cache是一区，每个区再分成相等的组，组内分块。组间直接映象，组内各块全相联映象。
4)段相联映象规则：把主存和 Cache分成具有相同的 Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象，实质上就是组相联映象的特例。
3.替换算法的实现
1)堆栈法思想：栈顶恒存放近期最久访问过的页的页号，
而栈底恒存放近期最久没有访问过的页的页号，即准备被替换掉的页的页号。按此思想组成一个硬件堆栈。
2)比较对法思路：让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到 LRU块。
4,Cache的透明性及性能分析
1)Cache的透明性分析
a)写回法在 CPU执行写操作时，只是把信息写入 Cache，
仅当需要被替换时，才将已经被写入过的 Cache块先送回主存，然后再调入新块。
b)写直达法也称为存直达法，它利用 Cache——主存存贮层次在处理机和主存之间的直接通路，每当处理机写入 Cache的同时，也通过此通路直接写入主存。
2) Cache的取算法
a)预取法
b)块的大小
c)预取开销
3)任务切换对失效率的影响
a)与任务的切换频度 (平均时间间隔 Qsw)有关
b)与 Cache的容量有关
4)影响 Cache存贮器性能的因素
a)不命中率与 Cache的容量、组的大小和块的大小的一般关系看 P168图 4.47块的大小、组的大小与 Cache容量对
Cache命中率的影响。
b)Cache——主存存贮层次的等效速度与命中率的关系
5.Cache——主存 ——辅存存贮层次
1)对应于虚地址的单元已在 Cache中
2)对应单元已在主存但尚未调入 Cache
3)对应单元还不在主存
4.4主存保护
1.存贮区域的保护
1)页表保护
2)键方式
3)环式保护
2.访问方式的保护第 4章习题处理
1.某虚拟存贮器共 8个页面，每页为 1024个字，时间主存为 4096个字，采用页表法进行地址映象。映象表内容如右图：
1)列出会发生页面失效的全部虚页号；
2)按以下虚地址计算主存实地址：
0,3728,1023,1024，
2055,7800,4096,6800。
实页号 装入位
1
1
0
0
1
0
1
0
3
1
2
3
2
1
0
0
【 分析 】 要找出会发生页面失效的全部虚页号，关键是搞清楚页表法进行地址映象所用的虚页表的构成。
要由虚地址计算出主存的实地址，首先应根据题意将虚、实地址中各个字段及其位数确定下来。由于虚拟存贮器共 8个页面，
每个页面大小为 1024字，
实页号 装入位
1
1
0
0
1
0
1
0
3
1
2
3
2
1
0
0
虚页号
0
1
2
3
4
5
6
7
可知，虚页号字段为 3位二进制位 (23＝ 8)，页内位移字段为 10位二进制位 (210＝ 1024)。由于虚实页面大小是一样的，实际主存为 4096个字，不难得到实页号字段为 2位 (22＝ 4)，页内位移为 10位 (210＝ 1024)，
所以：
虚页号 页内位移实页号 页内位移虚地址字段实地址字段
3位 10位
10位2位这样，根据题目所给的虚地址可以按下面方法来计算出虚页号和页内位移量。其中，虚页号为：
虚地址 /页面大小 ——取整数页内位移量为：
虚地址－虚页号 × 页面大小或,虚地址％页面大小 ——取余数计算主存实地址为：
实页号 × 页面大小＋页内位移量
【 解答 】 1)发生页面失效的全部虚页号就是映象表中装入位为 0的行所对应的虚页号，即 2,3,5,7。
2)由虚地址计算主存实地址的情况见下表：
虚地址 虚页号 页内位移 装入位 实页号 页内位移 实地址
0
3728
1023
1024
2055
7800
4096
6800
0
3
0
1
2
7
4
6
0
656
1023
0
7
632
0
656
1
0
1
1
0
0
1
1
3 0
页面失效
3 1023
1 0
页面失效页面失效
2 0
0 656
3072
无
4095
1024
2048
656
无无
2.设某程序保护 5个虚页，其页地址为 4,5,3,2，
2,5,1,3。当使用 LRU算法替换时，为获得最高的命中率，至少分配给该程序几个实页？其可能的最高命中率为多少？
【 分析 】 由于 LRU替换算法是堆栈型替换算法，因而随着分配给该道程序的实页数增加，实页命中率只会上升，至少是不会下降的。但是，当实页数增加到一定程度后，其命中率就不会再提高了。
如果要增加分配给该道程序的实页数，只会导致实存空间的利用率下降。所以，只要分别求出分配给该道程序不同实页数时的命中率，找出大到最高命中率时所分配的最少实页数即可。
【 解答 】 用堆栈对页地址流处理一次的过程如下表所示，其中 H表示命中率。
页地址流堆栈内容实页数
4 5 3 2 5 1 3 2 2 5 1 3
S(1)
S(2)
S(3)
S(4)
S(5)
S(6)
时间 t 1 2 3 4 5 6 7 8 9 10 11 12
n=1
n=2
n=3
n=4
n≥5
4 5 3 2 5 1 3 2 2 5 1 3
4 5 3 2 5 1 3 3 2 5 1
4 5 3 2 5 1 3 2 51
4 4 2 53 3 215
4 4 4 4 4 4 4
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
模拟结果表明，使用 LUR替换算法，对该程序至少应分配 4个实页。如果只分配 3个实页，其页面命中率只有 3/12，太低；而分配实页数多于 4页后，其页面命中率不会再有提高。所以，分配给该程序 4个实页即可，其可能的最高命中率为 H＝ 7/12。
作业：
1.存贮器最大频宽 模 m交叉编址 程序局部性堆栈型替换算法 最佳分配算法 段页式管理不命中预取法 组相联映象 写回法优化算法 环保护 键保护
7,15,18,19，
