计算机体系结构 4：存储系统

在一台计算机中，通常有多种不同的存储器。

它们就形成一个存储系统，这个存储器：

• 性能上，接近速度最快的那个存储器，
• 存储容量上，接近容量最大的那个存储器，
• 价格上，接近最便宜的那个存储器。

主要是因为在实际的程序运行过程中，有 80% 运行的代码用着 20% 的常用指令，具体请猛击：《计算机系统结构[第二课摘要]》无处不在的缓存、局部性原理。
 

---

存储器概览

存储器按 [存储介质] 分类：

• 半导体存储器：内存、U盘、固态硬盘
• 磁存储器：磁带、磁盘

存储器按 [存取方式] 分类：

• 随机存储器（RAM）：随机读取、与编号无关
• 串行存储器：顺序查找、与编号有关
• 只读存储器（ROM）：只读不写
   

---

主存储辅存储器

计算机断电时，主存储器（内存）的数据会丢失？

内存其实是一个 随机存储器（RAM），RAM 通过电容存储数据，必须每隔一段时间刷新一次。

如果因为断电，有一段时间电子没有刷新，那电容里面的电子就会丢失，数据也就丢失了。
 

---

动态内存管理

早期计算机编程并不需要过多的存储空间，随机计算机的不断发展，存储管理成为了必要。

存储管理主要是为了解决 3 个问题：

• 确保计算机有足够的内存处理数据
• 确保程序可以从可用内存中获取一部分内存使用
• 确保程序可以归还使用后的内存，以供重复使用

动态内存管理机制，主要包含两方面内容：

• 用户申请内存空间时，系统如何分配；
• 用户使用内存空间完成后，系统如何及时回收。

另外，内存不断分配与回收的过程，会产生诸多内存碎片，但通过利用数据结构、分配算法，内存碎片化的问题能够得到有效的解决。

p.s. 这里的用户，不是普通意义上的用户，可能是一个普通的变量，一个应用程序，一个命令等等。只要是向系统发出内存申请的，都可以称之为用户

 

---

分配

操作系统分配空间的方式有 3 种：

• 单一连续分配，最简单分配形式，只能在单用户、单进程的操作系统中使用；
• 固定分区分配，支持多程序分配，内存空间被划分为若干个区域，一个块对应一个程序；
• 动态分区分配，以进程的实际需要，动态分配内存空间。

对于初始状态下的内存来说，整个空间都是一个空闲块（还未分配出去的内存区），但是随着不同的用户不断地提出存储请求，就会有许多占用块（已经分配给用户的的内存区），分配顺序是从内存的低地址向高地址分配。

整个内存区就会分割成两个大部分：

• 低地址区域会产生很多占用块；
• 高地址区域还是空闲块。

但是当某些用户运行结束，所占用的内存区域就变成了空闲块。

此时，就形成了占用块和空闲块犬牙交错的状态。当后续用户请求分配内存时，系统有两种分配方式：

• 系统继续利用高地址区域的连续空闲块分配给用户，不去理会之前分配给用户的内存区域的状态。直到分配无法进行，也就是高地址的空闲块不能满足用户的需求时，系统才会去回收之前的空闲区，重新组织继续分配；
• 当用户运行一结束，系统马上将其所占空间进行回收。当有新的用户请求分配内存时，系统遍历所有的空闲块，从中找出一个合适的空闲块分配给用户。

通常，使用方案2。

我们会借助数据结构，如顺序存储的【状态表】。

状态表里有若干个分区，每个分区都有一个状态，1表示已分配，0表示未分配。

还有链式存储的【状态链】。

如果某个区是空闲的，那就组合起来。因为可能每个区的大小都不一样，所以每个结点都需要记录可存储的容量。

内存分配的过程：

• 分配内存时顺序查找（低地址–>高地址）合适的内存区
• 若没有空闲区，则该次分配失败
  这是[首次适应算法]，但这个算法有一个问题。

因为每次都从低地址开始遍历，那左边的空间被不断划分，就会产生许多很小的内存碎片。

于是，提出了不能每次都从低地址开始分配，下一次分配应该接着上一次分配的地址，这是[循环适应算法]，是[首次适应算法]的改进。

还有[最佳适应算法]，它要求所有空闲区链表按容量大小排序，遍历空闲区链表获取最佳的空闲块。

[最佳适应算法]可以找到最佳的空间区匹配，避免大材小用，浪费不必要的空间。

以及[快速适应算法]，在存储的时候就分层次的存储，大、中、小的空闲区分开存储。
 

---

回收

回收时，一共有 4 种情形：

分开讨论：

图1，空闲区在回收区的上面，且地址相邻。

• 不需要新建链表结点，只需要把[空闲区1]的容量增大为新的空闲区[空闲区1+回收区]

图2，空闲区在回收区的下面，且地址相邻。

• 将回收区与空闲区1合并，空闲区1的地址更新为回收区的首地址

图3，回收区位于俩个空闲区之间。

• 将空闲区1、空闲区2、回收区合并，新的空闲区首地址是空闲区1的首地址。

图4，回收区

• 为回收区创建新的空闲结点，插入到相应的空闲区链表中去。
   

---

存储管理方式

动态内存分配是物理角度的存储管理方式，而段页式管理是进程角度的存储管理方式。

操作系统是如何管理进程空间的呢？
 

---

页式管理

首先得学一个概念：【页面】。

字、字块是相对物理空间的定义，而页面是相对逻辑空间的定义。

页式管理：

• 将【进程逻辑空间】等分为【若干大小的页面】
• 相应的把【物理内存空间】分成与【页面大小的物理块】
• 以【页面】为单位，把【进程空间】装进【物理内存中分散的物理块】

按页管理，容易产生内存碎片。

因为页的大小是固定的，而内存块的有大有小。

页面比匹配的内存块小时，就会有内存碎片，所以，页面大小应该定制在一个合理的值。

页面大小通常是 [512, 8000] 字节。

通过页式存储管理，可以知道【进程逻辑空间】的每个页面都放在【内存的物理块】中，但我们怎么知道【进程的某个页面】分配到【具体的哪个字块】呢？

我们还得学一个概念：【页表】。

【页表】：记录进程逻辑空间与物理空间的映射。

地址（编号）的设计，也与页式管理相关，地址分为俩部分：

• 大概位置：页号
• 精确位置：页内偏移

但因为现在计算机系统支持的逻辑地址空间非常大，如 32 达到了 $2^{32}（4G）$232（4G）。

一个页面是 $4K$4K（最多 $8 K$8K），那 $2^{32} / 4K = 2^{20}$232/4K=220。

$2^{20} = 1M$220=1M，如果每个页表项占 $1B$1B，一共就有 $1M$1M 个页表项，每个进程仅页表项就要占用 $1MB$1MB 的内存空间。

所以，我们采用【多级页表】。

多级页表：

• 根页表：存储的是二级页表
• 二级页表：存储的是内存空间

这里面的算法设计：请猛击《查表法》。
 

---

段式管理

页式存储管理会遇到一个问题，如果有一段连续的逻辑分布在多个页面中，会大大减低执行效率。

段式管理：

• 将【进程逻辑空间】划分为【若干段】（不等分，页式管理等分）
• 段的长度由连续逻辑的长度决定，如主函数main()、子程序段、子函数等

和页式管理一样，段式管理也需要一个【段表】管理空间。

因为段的长度是不等分的，所以结构上会有一些不同。

段表的结构：

• 大概位置：段号
• 精确位置：首地址 + 段长（对比页式管理，多一个段的首地址）

段式、页式对比：

• 【相同】：离散的管理了进程的逻辑空间

【不同的是】：

• 页是物理单位，分页是为了合理的利用空间，页大小由硬件固定，页表信息是一维的。

• 段是逻辑单位，分段是为了满足用户的需求，段长度可动态变化，段表信息是二维的。
   

---

段页式管理

段页式管理，截取段式、页式俩者之长。

• 分页可以有效提高内存利用率
• 分段可以更好的满足用户需求

俩俩结合，就形成了【段页式管理】。

段页式管理：

• 先将【逻辑空间】按段式管理分成【若干段】
• 再把【段内空间】按页式管理等分成【若干页】

 

---

高速缓存

冯·诺伊曼架构中一个永恒的研究热点：怎样给处理器提供稳定的指令和数据流，喂饱饥饿的CPU，技术突破主要集中于：

• 转移猜测技术：提供稳定的指令流
• 高速缓存技术：提供稳定的数据流

IT行业随着《摩尔定律》的发展，CPU的性能每18个月翻一番，而主存（内存）的性能却没有什么提升。

现在CPU和主存（内存）速度之间，已经形成了一个巨大的剪刀差。

于是，为了让快速的 CPU 不必等待慢速的输入输出设备，引入了一个高速缓存Cache。

其实就是一块小空间，用来缓存数据，将数据先放入缓冲区中，再将缓冲区中的所有数据一次性地写或读存储器。

就像生活里的仓库和工作，工厂（CPU）生产任何东西都要从仓库(内存)拿材料，加工之后也得放入仓库。

随着《摩尔定律》的发展，工厂的生产能力呈指数级增长。

在生产的过程中，因为仓库运输能力的限制，工厂总是要等仓库准备好了才能生产。

为了减少这种不必要的时间开销，就在工厂里建了一个小仓库（高速缓存）。

 

---

Cache结构

Cache是内存的一个子集，但单位按一个字节算，而是按 32 or 64 个字节算(块)。

Cache的每个块都要保存它的地址(Tag)；以及记录它的状态(State)，该块是否有效、有木有被改写等。

对于Cache，若按其特点、分类，可以从 3 个方面来描述。

• Cache块的位置怎么放，有[直接相联]、[全相联]、[组相联]；

[直接相联]：

[全相联]：

[组相联]：

[三者对比]：

• Cache与内存的数据关系（写策略），有[全写法]、[写回法];

• Cache替换机制，有[随机替换]、[先进先出]、[最近最少使用]、[最优替算法]。

教室的座位已经满了（Cache满了），这时又来了一个，那教室里必须得有一个人出去：

• 随机替换：抓阄；
• 先进先出：来的最早的出去；
• 最近最少使用：最不好好听课的出去；
• 最优替算法：按某种逻辑选出一个出去。
   

---

Cache性能优化

前置知识：局部性原理 --> 请猛击《计算机系统结构 2》。

借用局部性原理，写一些软件优化。

软件优化主要是通过提高程序的局部性来提高 Cache 命中率。

示例1: 数组合并

/* 优化前 */
int a[size];
int b[size];

// 数组a、数组b如果是一起访问的，存储的时候先存完 a 的数据，再存储 b 的数据，那 a[i]、b[i] 隔的挺远。

/* 优化后 */
struct _merge{
    int a;
    int b;
}merge[size];

// 为了提高程序的局部性，需要把 a[i]、b[i] 放一起，可以定义成一个结构体数组。

示例2：循环交换

/* 优化前 */
for(int i=0; i<100; i++)           // 先访问列
    for(int j=0; j<5000; j++)      // 再访问行
        do sth...
        
/* 优化后 */
for(int i=0; i<5000; i++)          // 先访问行
    for(int j=0; j<100; j++)       // 再访问列
        do sth...

// 因为内存是按行存储的，同一行的数据是紧挨着的，但同一列的数据却是分散的，先访问列，再访问行的局部性不好，Cache命中率不高。

示例3：循环合并

/* 优化前 */
for(int i=0; i<N; i++)
	for(int j=0; j<N; j++)
		do sth 1...
		
for(i=0; i<N; i++)
	for(j=0; j<N; j++)
		do sth 2...
				
/* 优化后 */
for(int i=0; i<N; i++)
	for(int j=0; j<N; j++){
		do sth 1...
		do sth 2...
  }

// 由于数组很大，内循环访问时，外循环取进 Cache 中的数据已经被替换了，Cache失效。可以把俩个循环合并在一起，每个元素访问俩次，增加了局部性。

示例4：分块访问

/* 优化前 */
for(int i=0; i<N; i++)
	for(int j=0; j<N; j++){
		r = 0;
		for(int k=0; k<N; k++)
		    r += y[i][k] * z[k][j];
		    
		x[i][j] = r;
  }
  
// N*N的矩阵相乘，矩阵按 y 行访问，矩阵按 z 行访问，但由于矩阵很大，Cache放不下，所以采用分块的矩阵乘法，块大小 = B*B
  
/* 优化后 */
for(int jj=0; jj<N; jj++)
	for(int kk=0; kk<N; kk++)
		for(int i=0; i<N; i++)
			for(int j=jj; j<min(jj+B-1, N); j++){
				r = 0
				for(int k=kk; k<min(kk+B-1, N); k++)
					r += y[i][k] * z[k][j];
				
				x[i][j] = x[i][j] + r;
}

通过[数组合并]、[循环交换]、[循环合并]、[分块访问]等程序优化手段，可以大幅度提高性能。

但CPU与主存交互时，如果主存缺页，那么就会采用替换算法，从辅存载入内存页面数据。

这就是虚拟内存的置换算法，替换策略发生在 Cache-主存、主存-辅存层次。

Cache-主存层主要是为了解决【速度】问题。

主存-辅存层主要是为了解决【容量】问题。

他们的算法都是一样，如FIFO、LRU、LFU等。
 

---

虚拟内存

前置知识：局部性原理 --> 请猛击《计算机系统结构 2》。

一个游戏 十几G，而计算机物理内存只有 4G，那这个游戏是怎么运行起来的？

类似这时候（物理内存不够用），就要引入虚拟内存了。

因为有局部性原理，我们程序运行时，无需全部装载到内存，一部分即可。

虚拟内存实际是物理内存的扩充，速度接近于主存，成本接近于辅存。
 

---

FIFO缓存置换算法：先进先出

# -*- encoding=utf-8 -*-

from computer_principle.DoubleLinkedList import DoubleLinkedList, Node


class FIFOCache(object):
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.map = {}
        self.list = DoubleLinkedList(self.capacity)

    def get(self, key):
        if key not in self.map:
            return -1
        else:
            node = self.map.get(key)
            return node.value

    def put(self, key, value):
        if self.capacity == 0:
            return

        if key in self.map:
            node = self.map.get(key)
            self.list.remove(node)
            node.value = value
            self.list.append(node)
        else:
            if self.size == self.capacity:
                node = self.list.pop()
                del self.map[node.key]
                self.size -= 1
            node = Node(key, value)
            self.list.append(node)
            self.map[key] = node
            self.size += 1

    def print(self):
        self.list.print()


if __name__ == '__main__':
    cache = FIFOCache(2)
    cache.put(1, 1)
    cache.print()
    cache.put(2, 2)
    cache.print()
    print(cache.get(1))
    cache.put(3, 3)
    cache.print()
    print(cache.get(2))
    cache.print()
    cache.put(4, 4)
    cache.print()
    print(cache.get(1))

最好是直接打开编译器，看源码。
 

---

LRU缓存置换算法：最近最久未使用算法

# -*- encoding=utf-8 -*-


from computer_principle.DoubleLinkedList import DoubleLinkedList, Node


class LRUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.list = DoubleLinkedList(self.capacity)

    def get(self, key):
        if key in self.map:
            node = self.map[key]
            self.list.remove(node)
            self.list.append_front(node)
            return node.value
        else:
            return -1

    def put(self, key, value):
        if key in self.map:
            node = self.map.get(key)
            self.list.remove(node)
            node.value = value
            self.list.append_front(node)
        else:
            node = Node(key, value)
            # 缓存已经满了
            if self.list.size >= self.list.capacity:
                old_node = self.list.remove()
                self.map.pop(old_node.key)

            self.list.append_front(node)
            self.map[key] = node

    def print(self):
        self.list.print()


if __name__ == '__main__':
    cache = LRUCache(2)
    cache.put(2, 2)
    cache.print()
    cache.put(1, 1)
    cache.print()
    cache.put(3, 3)
    cache.print()
    print(cache.get(1))
    cache.print()
    print(cache.get(2))
    cache.print()
    print(cache.get(3))
    cache.print()

最好是直接打开编译器，看源码。
 

---

LFU算法：最近最少使用算法

# -*- encoding=utf-8 -*-


from computer_principle.DoubleLinkedList import DoubleLinkedList, Node


class LFUNode(Node):
    def __init__(self, key, value):
        self.freq = 0
        super(LFUNode, self).__init__(key, value)


class LFUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        # key: 频率, value: 频率对应的双向链表
        self.freq_map = {}
        self.size = 0

    # 更新节点频率的操作
    def __update_freq(self, node):
        freq = node.freq

        # 删除
        node = self.freq_map[freq].remove(node)
        if self.freq_map[freq].size == 0:
            del self.freq_map[freq]

        # 更新
        freq += 1
        node.freq = freq
        if freq not in self.freq_map:
            self.freq_map[freq] = DoubleLinkedList()
        self.freq_map[freq].append(node)

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map.get(key)
        self.__update_freq(node)
        return node.value

    def put(self, key, value):
        if self.capacity == 0:
            return

        # 缓存命中
        if key in self.map:
            node = self.map.get(key)
            node.value = value
            self.__update_freq(node)

        # 缓存没有命中
        else:
            if self.capacity == self.size:
                min_freq = min(self.freq_map)
                node = self.freq_map[min_freq].pop()
                del self.map[node.key]
                self.size -= 1
            node = LFUNode(key, value)
            node.freq = 1
            self.map[key] = node
            if node.freq not in self.freq_map:
                self.freq_map[node.freq] = DoubleLinkedList()
            node = self.freq_map[node.freq].append(node)
            self.size += 1

    def print(self):
        print('***************************')
        for k, v in self.freq_map.items():
            print('Freq = %d' % k)
            self.freq_map[k].print()
        print('***************************')
        print()


if __name__ == '__main__':
    cache = LFUCache(2)
    cache.put(1, 1)
    cache.print()
    cache.put(2, 2)
    cache.print()
    print(cache.get(1))
    cache.print()
    cache.put(3, 3)
    cache.print()
    print(cache.get(2))
    cache.print()
    print(cache.get(3))
    cache.print()
    cache.put(4, 4)
    cache.print()
    print(cache.get(1))
    cache.print()
    print(cache.get(3))
    cache.print()
    print(cache.get(4))
    cache.print()

最好是直接打开编译器，看源码。
 

---

OPT 算法：最优替算法

最好是直接打开编译器，看源码。