3.12 一个有快表和慢表的页式虚拟存储器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存容量8M字节。
(1) 写出多用户虚地址的格式，并标出各字段的长度。
(2) 写出主存地址的格式，并标出各字段的长度。
(3) 快表的字长为多少位？分几个字段？各字段长度为多少位？
(4) 慢表的容量是多少个存储字？每个存储字的长度为多少位？
(5) 画出多用户虚地址经快表或慢表变换成主存实地址的逻辑示意图。

3.13 一个虚拟存储器按字节编址，最多有256个用户，每个用户最多要用4096页，每页1K字节。主存容量16M字节，快表按地址访问，共32个存储字，快表地址码经散列变换得到，为减少散列冲突，快表分为两组，有两套独立的相等比较电路。
(1) 写出多用户虚地址和主存地址的格式，并标出各字段的长度。
(2) 散列变换部件的输入位数和输出位数各为多少？
(3) 每个相等比较电路的位数是多少？
(4) 快表每个存储字的总长度为多少位？分哪几个字段？各字段的长度为多少位？
(5) 画出多用户虚地址经快表变换成主存地址的逻辑示意图。

3.14 在页式虚拟存储器中，一个程序由P1～P5共5个页面组成。在程序执行过程中依次访问到的页面如下：
P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2
假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LRU和OPT三种页面替换算法对这3页主存进行调度。
(1) 画出主存页面调入、替换和命中的情况表。
(2) 统计三种页面替换算法的页命中率。

3.15 一个程序由5个虚页组成，采用LRU替换算法，在程序执行过程中依次访问的页地址流如下：
P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3
(1) 可能的最高页命中率是多少？
(2) 至少要分配给该程序多少个主存页面才能获得最高的命中率。
(3) 如果在程序执行过程中每访问一个页面，平均要对该页面内的存储单元访问1024次，求访问存储单元的命中率。

3.16 一个程序由1200条指令组成，每条指令的字长均为4个字节。假设这个程序访问虚拟存储器的字地址流依次为：12，40，260，280，180，800，500，560，600，1100，1200，1000。采用FIFO页面替换算法，分配给这个程序的主存容量为2048个字节。在下列不同的页面大小情况下，分别写出这个程序执行过程中依次访问的虚存页地址流，并计算主存的页命中率。
(1) 页面大小为1024个字节。
(2) 页面大小为512个字节。
(3) 页面大小为2048个字节
(4) 比较(1)、(2)、(3)，可以得出什么结论？
(5) 如果把分配给该程序的主存容量增加到4096个字节，页面大小为1024个字节，再做一遍，由此又可以得出什么结论？

3.17 在计算机系统中设置虚拟存储器和Cache的主要目的各是什么？试列举出这两种存储系统在具体实现上的至少4个方面的差别，并说明主要理由。

3.18 假设在一个采用组相联映象方式的Cache中，主存有B0～B7共8块组成，Cache有2组，每组2块，每块的大小为16个字节，采用LRU块替换算法。在一个程序执行过程中依次访问这个Cache的块地址流如下：
B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3
(1) 写出主存地址的格式，并标出各字段的长度。
(2) 写出Cache地址的格式，并标出各字段的长度。
(3) 画出主存与Cache之间各个块的映象对应关系。
(4) 如果Cache的各个块号为C0、C1、C2和C3，列出程序执行过程中Cache的块地址流情况。
(5) 如果采用FIFO替换算法，计算Cache的块命中率。
(6) 采用LRU替换算法，计算Cache的块命中率。
(7) 如果改为全相联映象方式，再做(5)和(6)，可以得出什么结论？
(8) 如果在程序执行过程中，每从主存装入一块到Cache，则平均要对这个块访问16次。请计算在这种情况下的Cache命中率。

3.19 在一个采用组相联映象方式的Cache中，Cache的容量为16KB。主存采用模8低位交叉方式访问，每个存储体的字长为32位，总容量为8MB。要求Cache的每一块在一个主存周期内分别从8个存储体中取得，Cache的每一组内共有4块。要求采用按地址访问存储器方式构成相联目录表，实现主存地址到Cache地址的变换，并采用4个相等比较电路。
(1) 设计主存地址格式，并标出各字段的长度。
(2) 设计Cache地址格式，并标出各字段的长度。
(3) 相联目录表的行数（即地址个数）是多少？
(4) 设计相联目录表每一行的格式，并标出每一个字段的长度。
(5) 每个比较电路的位数是多少？
(6) 画出主存地址经相联目录表变换成Cache地址的逻辑示意图

3.20 一个采用组相联映象方式的Cache，要求Cache的每一块在一个主存周期内取得。主存采用4个存储体的低位交叉方式访问，每个存储体的字长为4个字节，总容量为1MB。Cache的容量为1KB，每一组内有4块。采用按地址访问存储器构成相联目录表，实现主存地址到Cache地址的变换，采用4个相等比较电路。
(1) 设计主存地址格式，并标出各字段的长度。
(2) 设计Cache地址格式，并标出各字段的长度。
(3) 设计相联目录表结构，求出该表的行数及每一行的格式。
(4) 每一个比较电路的位数？
(5) 画出实现组相联地址变换的逻辑示意图。

3.21 一个采用组相联映象方式的Cache共有8块，分成两组，用硬件的比较对法实现LRU块替换算法。
(1) 共需要多少个触发器？多少个与门？
(2) 画出其中一组的逻辑图。

3.22 对于一个采用组相联映象方式和FIFO替换算法的Cache，发现它的等效访问时间太长；为此，提出如下改进建议：
(1) 增大主存的容量。
(2) 提高主存的速度。
(3) 增大Cache的容量。
(4) 提高Cache的速度。
(5) Cache的总容量和组大小不变，增大块的大小。
(6) Cache的总容量和块大小不变，增大组的大小。
(7) Cache的总容量和块大小不变，增加组数。
(8) 替换算法由FIFO该为LRU。
请分析以上改进建议对等效访问时间有何影响，其影响的程度如何？

3.23 在一个Cache中，有n块要采用相联映象方式访问，现设计一个n行×n列的触发器阵列来实现LRU替换算法，其行和列的编号都从1到n。当Cache的第n块被访问时，先把触发器阵列的第n行全部置"1"，然后把第n列全部置"0"。这样，在任何时刻，触发器阵列中二进制值最小的行号就是近期最少访问过的Cache块号。现假设n＝4，访问Cache的块地址流为1、2、3、4、4、2、3、1、4、3、4、3、2，请验证这一结论的正确性。