嵌入式系统设计师考试复习笔记之存储管理篇

嵌入式系统设计师考试复习笔记之存储管理篇

欧浩源([e-mail]) 20080721

引言

2007年下半年通过了嵌入式系统设计师的考试，一大堆的复习资料都不知道扔那里好，卖掉又有点可惜，送人又没人要。与其让当时的复习笔记沉沦书架底部，还不如整理一下让大家评论评论。2008年11月的考试也快到了，如果能帮到有需要的人，那我真是乐坏了。看看06和07年的题目，在存储管理方面的题目蛮多的，应该是一个重要考点。无论是概念、理论、分析和计算都相当容易出题。在我当时的复习笔记中这方面算最多了。这里就先拿这个点说说吧，其他的以后有时间再写了。

 

1、存储器系统的层次架构

计算机系统的存储器被组织城一个金字塔的层次结构。

自上而下为：CPU内部寄存器、芯片内部高速缓存(cache)、芯片外部高速缓存(SRAM、SDRAM、DRAM)、主存储器(FLASH、EEPROM)、外部存储器(磁盘、光盘、CF卡、SD卡)和远程二级存储器(分布式文件系统、WEB服务器)，6个层次的结构。

上述设备从上而下，依次速度更慢、容量更大、访问频率更小，造价更便宜。

 

2、高速缓存(cache)

工作原理（参照教程126页，博客画不了图）：主要利用了程序的局部性特点。

地址映象是指把主存地址空间映象到cache的地址空间。

地址变换是指当程序或数据已经装入到cache后，在实际运行过程中，把主存地址如何编程cache空间的地址。

常用的地址映象和地址变换的方式有：（教程127页）

直接映象和变换：速度快，造价低，但有局限性，不能充分利用cache的好处。

组相联地址映象和变换：速度稍慢但是命中率高。

全相联地址映象和变换：可以任意映射。

常用的cache替换算法：轮转法和随机替换算法。

高速缓存的分类：

统一cache和独立的数据/指令cache

写通cache和写回cache

读操作分配cache和写操作分配cache

 

3、存储管理单元（MMU）

MMU在CPU和物理内存之间进行地址转换，将地址从逻辑空间映射到物理空间，这个过程称为内存映射。

MMU主要完成下面的工作：

A.     虚拟存储空间到物理空间的映射。

B.     存储器访问权限的控制。

C.     设置虚拟存储空间的缓冲特性。

嵌入式系统中常常采用页式存储管理。为了管理这些页引入了页表的概念。

页表是位于内存中的表，它的每一行对应虚拟存储空间的一个页，该行包含了该虚拟内存页对应的物理内存页的地址、该页的访问权限和该页的缓冲特性等。

从虚拟地址到物理地址的变换过程就是查询页表的过程。

由于页表存储在内存中的，整个查询过程需要付出很大的代价。根据程序局部性的特点，增加了一个小容量、高速度的存储部件来存放当前访问需要的地址变换条目，这个存储部件称为：地址转换后备缓冲器(TLB)。

当CPU访问内存时，首先在TLB中查找需要的地址变换条目，如果该条目不存在，CPU再从内存中的页表中查询，并把相应的结果添加到TLB中，更新它的内容。

嵌入式系统中虚拟存储空间到物理空间的映射以内存块为单位进行。即虚拟存储空间中一块连续的存储空间被映射到物理存储空间中同样大小的一块连续存储空间。

在页表和TLB中，每一个地址变换条目实际上记录了一个虚拟存储空间的内存块的基地址与物理存储空间相对应的一个内存块的基地址之间的对应关系。

在MMU中实现虚拟地址到物理地址的映射是通过两级页表来实现的。

禁止MMU时，所有物理地址和虚拟地址相等，即使用平板存储模式。

 

4、内存保护

操作系统通常利用MMU来实现操作系统内核与应用程序之间的隔离，以及应用程序与应用程序之间的隔离。

内存保护包含两个方面的内容：

A.     防止地址越界，每个应用程序都有自己独立的地址空间。

B.     防止越权操作，每个应用程序都有自己的访问权限。

 

5、实模式与保护模式

在嵌入式系统中，常见的存储管理方案可以分为两大类：实模式和保护模式。

实模式：内存的平面使用模式。特点有：

A.     不划分“系统空间”与“用户空间”，无须进行地址映射。

B.     操作系统与应用程序之间不再有物理的边界。

C.     系统中的“任务”或“进程”，实际上全是内核线程。

在实模式下，内存布局可以分为5个段：

A.     代码段：包含操作系统和应用程序的所有代码。

B.     数据段：所有带有初始值的全局变量。

C.     BSS段：所有未带初始值的全局变量。

D.     堆空间：动态分配的内存空间。

E.     栈空间：保存上下文以及函数调用时的局部变量和形参。

在实模式存储管理方案下，主要的工作在于堆空间的管理，即如何来管理空闲的堆空间、如何来分配内存、如何来回收内存等等。

保护模式：处理器中必须有MMU硬件并启用。特点有：

A.     系统内核和用户程序都有各自独立的地址空间。

B.     每个应用程序只能访问自己的地址空间，不能去破坏操作系统和其他应用程序的代码和数据。

 

6、分区存储管理

为了实现多道程序系统而采用的最简单的内存管理。

基本思路：把整个内存划分为两大区域，即系统区和用户区，然后再把用户区划分为若干个分区，每个任务占有其中的一个分区。这样，在内存当中就同时保留多个任务，让他们共享整个用户区，从而实现多个任务的并发运行。

分区存储管理又可以分为两类：固定分区和可变分区。

固定分区：各个用户分区的个数、位置和大小一旦确定后，就固定不变，不能再修改。

优点：易于实现，系统开销较小。

缺点：内存利用率不高，分区总数固定。

可变分区：动态创建，在装入一个程序时，系统将根据它的需求和内存空间的使用情况来决定是否分配。

优点：动态变化，非常灵活。

缺点：可能存在外碎片。

在实现可变存储管理技术的时候，需要考虑三个方面的问题：

A.     内存管理的数据结构

B.     内存的分配算法

C.     内存的回收算法

 

7、地址映射

地址映射也叫地址重定位。

逻辑地址和物理地址是完全不同的，不能用逻辑地址来直接访问内存单元。

为了保证CPU在执行指令的时候，可以正确地访问内存单元，需要将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。这个过程称为：地址映射。

地址映射由存储管理单元MMU来完成。

地址映射主要有两种方式：静态地址映射和动态地址映射。

静态地址映射：当用户程序被装入内存时，直接对指令代码进行修改，一次性地实现逻辑地址到物理地址的转换。

动态地址映射：当用户程序被装入内存时，不对指令代码做任何修改，而是在程序的运行过程中，当它需要访问内存单元的时候，再来进行地址转换。

在具体实现时，这项转换工作一般是由硬件的地址映射机制来完成的。通常设置一个基地址寄存器，或者叫重定位寄存器。当一个任务被调度运行时，就把它所在分区的起始地址装入到整个寄存器中。然后，在程序运行的过程中，当需要访问某个内存单元时，硬件就会自动地将其中的逻辑地址加上基地址寄存器中的内容，从而得到实际的物理地址，并且按照这个物理地址区执行。

这个基地址寄存器位于MMU的内部，整个地址映射过程是自动运行的。从理论上说，每访问一次内存都要进行一次地址映射。

 

8、页式存储管理（重点）

基本思路：把物理内存划分为许多固定大小的内存块，称为物理页面；把逻辑地址空间也划分为大小相同的块，称为逻辑页面。当一个用户程序被装入内存时，不是以整个程序为单位，把它存放在一整块连续的区域，而是以页面为单位来进行分配的。对于一个大小为N的页面程序，需要有N个空闲的物理页面来把它装载。这些物理页面不一定是要连续的。

在页式存储管理中需要解决三个问题：数据结构、内存分配与回收、地址映射。

数据结构有两个：页表和物理页面表。

A.     页表：给出了任务逻辑页面号和内存中物理页面号之间的对应关系。

B.     物理页面表：描述内存空间中，各个物理页面的使用情况。

具体的例子请参考《教程》317页（博客中画不了图，有兴趣自己看）。

内存的分配过程：

A.     对于一个新来的任务，计算它所需要的页面数N，然后查看位示图，看是否还有N个空闲的物理页面。

B.     如果有足够的空闲物理页面，就去申请一个页表，其长度为N，并把页表的起始地址填入到该任务的控制块中。

C.     分配N个空闲的物理页面，把他们的变换填到页表中，建立逻辑页面与物理页面直接的对应关系。

D.     修改位示图，对刚刚被占用的那些物理页面进行标记。

地址映射的基本思路：

A.     逻辑地址分析：对逻辑地址，找到它所在的逻辑页面，以及它在页面内的偏移地址。

B.     页表查找：根据逻辑页面号，从页表中找出它对应的物理页面号。

C.     物理地址合成：根据物理页面号和页内偏移地址，最终确定物理地址。

逻辑地址分析：

页面的大小都是2的整数次幂。对于给定的一个逻辑地址，可以直接把它的高位部分作为逻辑页面号，把它的低位部分作为页内偏移地址。例如，假设页面的大小是4KB，即2的12次幂，逻辑地址为32为，那么在一个逻辑地址当中，最低12位为页内偏移地址，而剩下的20位就是逻辑页面号。

计算方法：

逻辑页面号＝逻辑地址/页面大小

页内偏移量＝逻辑地址％页面大小

页表查找：

页表作为操作系统的一个数据结构，通常保存在内核的地址空间中。

页表基地址寄存器用来指向页表的起始地址；页表长度寄存器用来指示页表的大小，即对于当前任务，它总共包含有多少个页面。

物理地址合成：

假设物理页面号为f，页内偏移地址为offset，每个页面大小为2ⁿ，那么相应的物理地址为：f×2ⁿ +offset。

 

9、虚拟存储管理

程序局部性原理：时间局限性和空间局限性。

虚拟页式存储管理：在页式管理的基础上，增加了请求调页和页面置换的功能。

基本思路：当一个用户程序需要调入内存去运行时，不是将这个程序的所有页面都装入内存，而是只装载部分的页面，就可以启动这个程序运行。在运行过程中，如果发现要执行的指令或者访问的数据不在内存当中，就向系统发出缺页中断请求，然后系统在处理这个中断请求时，就会将保存在外存中的相应页面调入内存，从而使该程序能继续运行。

在虚拟页式存储管理中，页表包含：逻辑页面号、物理页面号、驻留位、保护位、修改位和访问位。

常用的页面置换算法：

A.  最优页面置换算法：理想化算法。

B.      最近最久未使用算法：链表法和栈方法。寻找长时间没有被访问的页面。

C.      最不常用算法：每个页面设置一个访问计数器。

D.     先进先出算法：性能比较差。

E.      时钟页面置换算法：把页面组成环形链表，类似时钟面。

    一般来说，当一个任务刚刚启动的时候，它会不断去访问一些新的页面，然后逐步建立一个比较稳定的工作集。工作集是指当前任务正在使用的逻辑页面的集合。如果分配给一个任务的物理页面数太少，不能包含整个的工作集，任务将会造成很多缺页中断，需要频繁地进行页面置换，这种现象称为“抖动”。

 

10、相关的考试真题

（1）2007年6题：

若内存地址区间为4000H～43FFH，每个存贮单元可存储16位二进制数，该内存区域用4片存储器芯片构成，则构成该内存所用的存储器芯片的容量是 （6） 。

（6）A. 512×16bit       B. 256×8bit     C. 256×16bit     D. 1024×8bit

<答案>：C

首先计算内容空间的大小：43FFH-4000H=3FFH，其大小为1024×16bit

接着计算存储芯片的容量：(1024×16bit)/4=256×16bit=512×8bit

根据选项提供的内容，只有256×16bit符合提纲的要求。

（2）2007年23题：

页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如下图所示。假定页面的大小为8K，图中所示的十进制逻辑地址9612经过地址变换后，形成的物理地址a应为十进制 （23） 。

(博客不能显示图像) 

（23）A. 42380          B. 25996       C. 9612          D. 8192

<答案>：B

8K＝1024×8＝8192

逻辑页面号＝9612/8192=1（1号页号对应的物理地址块号为3）

页内偏移量＝9612％8192＝1420

物理地址＝3×8192＋1420＝25996

（3）2007年24题

某总线有104根信号线，其中数据总线（DB）32根，若总线工作频率为33MHz，则其理论最大传输率为 （24） 。（注：本题答案中的B表示Byte）

（24）A. 33 MB/s            B. 64MB/s     C. 132 MB/s        D. 164 MB/s

<答案>：C

每个字节8位，需要8根数据线。

数据总线有32跟，每次可以并行传输32/8=4个字节。

总线工作频率为33MHz，那么理论最大传输率为33×4＝132MHz。

（4）2007年26题

某存储器数据总线宽度为32bit，存取周期为250ns，则该存储器带宽为 （26） 。（注：本题答案中的B表示Byte）

（26）A. 8×10⁶B/s       B. 16×10⁶B/s   C. 16×10⁸B/s      D. 32×10⁶B/s

<答案>：B

存取频率为：1/0.00000025s=4000000

总线宽度为：32bit/8=4byte

存储器带宽：4×4000000＝16000000＝16×10⁶B/s

（5）2007年29～31题

在嵌入式处理器中，CACHE的主要功能由 （29） 实现；某32位计算机的CACHE容量为16KB（B：字节），CACHE块的大小为16B（B：字节），若主存与CACHE地址映像采用直接映像方式，则主存地址为0x1234E8F8的单元装入CACHE的地址 （30） ；在下列CACHE替换算法中,平均命中率最高的是 （31） 。

（29）A. 硬件                           B. 软件

C. 操作系统                               D. 应用程序

（30）A. 00010001001101               B. 01000100011010

C. 10100011111000                     D. 11010011101000

（31）A. 先入后出算法（FILO）         B. 随机替换算法（RAND）

C. 先入先出算法（FIFO）         D. 近期最少使用算法（LRU）

<答案>：A、C、D

29：Cache的主要功能由硬件实现，这个《教程》有介绍。

30：cache容量为16KB,即逻辑地址的低14位

    由于采用的是直接映象,所以cache的地址为:主存地址的低14位。

31：相比较说，D的命中率最低。

（6）2007年34题

在嵌入式系统的存储结构中，存取速度最快的是 （34） 。

（34）A. 内存           B. 寄存器组    C. Flash          D. Cache

<答案>：B

寄存器组>cache>内存>flash

（7）2007年41题

操作系统中的“抖动”是指 （41） 的现象。

（41）A. 根据一定的页面置换算法，将页面调出

B. 由于选择了长期未被访问的页进行置换，导致系统更换页面

C. 页面调入不久就被导出，导出不久又被调入，导致系统频繁更换页面

D. 根据系统运行情况决定将哪个页面调出，而不是由页面置换算法决定更换哪个页面

<答案>：C

《教程》中328页有对“抖动”的介绍。

（8）2006年1题

若内存按字节编址，用存储容量为32K×8比特的存储器芯片构成地址编号A0000H到DFFFFH的内存空间，则至少需要（1）片。

（1）A. 4     B. 6    C. 8      D. 10

<答案>：C

DFFFF=-A0000H=256KB。

256/32=8片

（9）2006年22题

从下表关于操作系统存储管理方案1、方案2和方案3的相关描述可以看出，他们分别对应（22）存储管理方案。

方案1：在系统进行初始化的时候就已经将主存储空间划分成大小相等或不等的块，并且这些块的大小在此后是不可以改变的。系统将程序分配在联系的区域中。

方案2：主储存空间和程序按固定大小大单位进行分割，程序可以分配在不连续的区域中。该方案当一个作业的程序地址空间大于主存可以使用的空间时也可以执行。

方案3：编程时必须划分程序模块和确定程序模块之间的调用关系，不存在调用关系的模块可以占用相同的主存区。

（22）A. 固定分区、请求分页和覆盖

B. 覆盖、请求分页和固定分区

C. 固定分区、覆盖和请求分页

D. 请求分页、覆盖和固定分区

<答案>：A

《教程》中有相关概念的介绍。

（10）2006年28题

在32位总线系统中，若时钟频率为500MHz，传送一个32位字需要5个时钟周期，则该总线系统的数据传输速率为 （28） MB/s。

（28）A. 200           B. 400    C. 600          D. 800

<答案>：B

与2007年的24和26题考查的是相同的内容。

在32位总线系统中，每次可以传送32位字，即4个BYTE。

时钟频率为500MHz，则传输32位的速率为100MHz。

也就是总线的数据传输速率为：4×100＝400MB/s。

在嵌入式系统的存储结构中，存取速度最快的是 （34） 。

（11）2006年29题

在CPU和物理内存之间进行地址转换时， （29） 将地址从虚拟（逻辑）地址空间映射到物理地址空间。

（29）A. TCB           B. MMU    C. CACHE          D. DMA

<答案>：B

TCB：任务控制块

MMU：存储管理单元

CACHE：高速缓存

DMA：直接存储

（12）2006年31题

下列存取速度最快的是（31）。

（31）A. flash存储器     B. DRAM存储器    C.高速缓存（CACHE）   D.磁盘

<答案>：C

    高速缓存（CACHE）> DRAM存储器> flash存储器、磁盘

（13）2006年51题

页式存储器当中的页面是由（51）所感知的。

（51）A. 用户     B. 操作系统    C. 编译系统      D. 连接程序

<答案>：B

概念理解，看过就应该会做，不看过也能推理出来。

   

总的来看，07年考查内存管理方面的内容比06年多，深度也相应的增加了。

这次到此为止，以后有时间再写，又问题可E我：[e-mail]。