中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall 第七讲 存储器管理 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall.

Presentation on theme: "中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall 第七讲 存储器管理 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall."— Presentation transcript:

1 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall
第七讲 存储器管理 中国科学技术大学计算机系 陈香兰 2013Fall

2 内容提要 存储器的层次结构 程序执行的基础知识、程序的装入和链接 连续分配存储管理方式 分页存储管理方式 分段存储管理 段页式存储管理

3 连续内存分配方式（contiguous memory allocation）
Reading： Operating System Concepts，p284- 连续分配存储管理方式 单一连续 固定分区 动态分区 对换

4 内存通常被划分为两个分区（partitions）:
系统区：常驻操作系统，通常位于内存低端 用户区：提供给用户（进程）使用，常位于内存高端 连续内存分配是指： 从用户区中为每个进程分配一个单独的、连续的内存空间。 主要有以下两种方式 单一连续分配方式 多分区式分配方式 固定分区式 动态分区式（可变分区式）

5 单一连续分配方式 最简单 只能用于单用户、单任务系统

6 存储保护机制 存储管理单元，MMU 或者不采用任何存储保护机制 出于信任，或采用再启动方式，

7 多分区式分配方式 支持多道程序， 根据分区大小是固定的还是可变的 用户区被进一步划分为若干个分区 每一个分区装载一个进程
多道程序度与分区的个数有关 根据分区大小是固定的还是可变的 固定分区方式 大小固定；等大小 or 不等大小 动态分区方式（可变分区方式） 动态&可变：内存的划分是动态的，分区的大小随进程的大小确定，分区的数目随系统的运行而不断变化

8 固定分区分配方式 支持多道程序，用于60年代IBM－360的MFT中 分区的划分方法，两种 但分区的大小一旦确定就不再发生变化 分配算法：
等大小 不等大小 但分区的大小一旦确定就不再发生变化 分配算法： 按大小顺序建立分区使用表

9 分配算法 操作系统 作业A 作业B 作业C 分区号 大小（KB） 起始地址(K) 状态 1 15 30 已分配 2 45 3 50 75 4
操作系统 作业A 作业B 作业C 30K 分区号 大小（KB） 起始地址(K) 状态 1 15 30 已分配 2 45 3 50 75 4 100 125 分配算法 45K 75K 固定分区使用表 125K 225K

10 缺点 内存利用率低 定义：内部碎片和外部碎片 内部碎片：已经分配出去但得不到利用的存储区域 外部碎片：不能被利用的小分区 解决方案：动态分区

11 动态分区分配方式 能根据进程实际需要的内存大小，动态分配 关键 能减少内部碎片 数据结构：记录内存的使用情况，特别是空闲内存 分配算法
分配和回收操作

12 数据结构 空闲分区表，占用额外的空间 空闲分区链，利用空闲分区 序号 分区大小 起始地址 状态 前向指针 N个字节可用 后向指针 N＋2

13 分区分配算法 在将一个新作业装入内存时，要从空闲分区表或空闲分区链中，选出一个分区分配给该作业，有三种常见的分配算法
首次适应算法FF：First Fit 循环首次适应算法 最佳适应算法：Best Fit=smallest 最差适应算法：Worst Fist ＝largest

14 分区分配操作 分配 可以看出，动态分区分配方式中内部碎片最大不超过min_size 设请求的分区大小为u.size；
利用某种分配算法，找到待分配的分区，大小为m.size 根据上述分区分配算法，有m.size>u.size 判断m.size-u.size与min_size的大小 min_size为事先约定的最小分区大小 >，分割，分割出来的分配出去，余下的加入空闲数据结构 否则，直接分配 将分配到的分区的首地址返回 可以看出，动态分区分配方式中内部碎片最大不超过min_size

15 回收，要考虑合并 向前合并 向后合并（图） 与前后同时合并 无相邻空闲分区，无需合并
只需修改前一个空闲分区表项中的大小 向后合并（图） 只需修改后一个空闲分区表项中的起始地址和大小 与前后同时合并 修改前一个空闲分区表项中的大小，并取消后一个分区表项 无相邻空闲分区，无需合并 建立一个新的表项，填写相关信息，插入 上述过程中，根据链表的维护规则，可能需要调整相应表项在空闲链表中的位置

16

17 动态分区分配分析 随着分配的进行，空闲分区可能分散在内存的各处 尽管有回收，但内存仍然被划分的越来越碎，形成大量的外部碎片 OS
process 5 process 8 process 2 process 9 process 10

18 解决方案之一：紧凑Compaction 针对外部碎片：采用紧凑的方法 紧凑：通过移动进程在内存中的位置，把多个分散的小分区拼成大分区
需要动态重定位技术支持

19 动态重定位分区分配算法： 引入紧凑和动态重定位技术的动态分区分配算法
基本与动态分区分配算法相同

20 Swapping 对换 最早用于MIT的CTSS中
单用户＋时间片＋对换 对换是指 把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存 能提高内存利用率 对换的单位： 进程：整体对换；进程对换 页、段：部分对换

21 对换技术需要实现三个方面的功能 对换空间的管理 进程的换出 进程的换入

22 Backing store，对换空间 Fast disk, large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images. 为提高速度，考虑连续分配方式，忽略碎片问题 需提供数据结构对空闲盘块进行管理 方法类似动态分区分配方法

23 进程的换出 第一步：选择被换出的进程 第二步：换出 Some approaches 确定要换出的内容 申请对换空间，换出，并修改相关数据结构
RR scheduling: swapped out when a quantum expires Priority-based scheduling: Roll out, roll in Lower-priority process is swapped out so higher-priority process can be loaded and executed. 第二步：换出 确定要换出的内容 非共享的程序和数据段的换出 共享的程序和数据段的换出：计数器 申请对换空间，换出，并修改相关数据结构

24 进程的换入 第一步：选择被换入的进程 第二部：申请内存并换入 考虑“静止就绪状态”的进程 ＋其他原则 申请成功
申请失败：利用对换技术腾出内存

25 Schematic View of Swapping

26 Swapping (cont.) Context switch
Swapped in & out cost too much Assume: process size 1MB, disk transfer rate 5MB/sec, average latency 8ms Transfer time =1MB / (5MB/sec) = 1/5 sec = 200 ms Swap time = 208 ms Swap out & in = 416 Major part of swap time is transfer time For RR scheduling, time quantum should >> 416ms Problems exist for pending I/O processes swapping

27 内容提要 存储器的层次结构 程序执行的基础知识、程序的装入和链接 连续分配存储管理方式
离散分配方式（Discrete Memory Allocation） 分页存储管理方式 碎片<页 分段存储管理 从逻辑上进行分段 段页式存储管理

28 内容提要 存储器的层次结构 程序执行的基础知识、程序的装入和链接 连续分配存储管理方式
离散分配方式（Discrete Memory Allocation） 分页存储管理方式 碎片<页 分段存储管理 从逻辑上进行分段 段页式存储管理

29 分页存储管理方式 1）将一个进程的地址空间分成若干个大小相等的片，称为页面或页（pages） 2）内存空间也分成与页大小相同的若干个存储块，称为物理页或页框（page frames） 序号： 0，1，……，n 大小：取2的幂， 512~8192B

30 地址结构 对于32位地址长度 页内偏移：相对于页（页框）的起始地址的相对地址 页（页框）号
若页（页框）的大小为4KB，则需要使用低端12位表示页内偏移 剩余的高端20位可以表示220个页（页框），1M个 31 12 11 页（页框）号p 页（页框）内偏移d

31 计算页（页框）号和页（页框）内偏移的方法：
地址：A 页（页框）大小：L 页（页框）号p＝ A 整除 L 页（页框）内偏移d＝ A mod L 考虑L是2的幂，不妨设为2N，则 p ＝ A 右移N位，即取A的高（32－N)位 d＝A的低端N位

32 必须在进程的逻辑地址空间和内存的物理地址空间之间建立一个映射关系 使用页表 每个进程都拥有各自的页面映射表，即页表
按序号，进程地址空间中的每个页在页表中都有一个页表项表示 页表项中记录的对应的物理页框的序号 可以实现从页号到页框号的映射

33 页表示意图

34 页表的例子 Page size = 4B Physical memory = 32B Logical memory = 16B
8 frames Logical memory = 16B 4 pages Logical address 9 = 2*4+1 p=2, d=1 Page 2 is stored in frame 1 Physical address = 1*4+1 = 5

35 地址变换机构 使用专门的（软）硬件 将用户地址空间中的逻辑地址转换为内存空间中的物理地址 基本的地址变换机构 具有块表的地址变换机构

36 基本的地址变换机构 Page table is kept in main memory, &
Page-Table Base Register (PTBR) Points to the page table currently used Page-table length register (PRLR) Indicates size of the page table Context switch

37 + > 3 b

38 Effective memory-access time, time needed for every data/instruction access
需要2次访存 Access the page table & Access the data/instruction Solution: A special fast-lookup hardware cache called associative registers or translation look-aside buffers (TLBs) 页表存放在内存中 访问一个逻辑地址中的内容需要两次访问内存 第一次：页表项，进而转换成物理地址 第二次：对应物理地址中的内容 速度：CPU vs. 2倍访存 解决方案：高速缓存（块表，TLB） Translation Lookaside Buffer

39 联想存储器，快表 Associative registers Address translation (A´, A´´)
Each register : a key & a value Parallel search (high speed) Expensive, typically 8~2048 entries Address translation (A´, A´´) If A´ is in associative register, get frame # out. Otherwise get frame # from page table in memory

40 联想存储器，快表 TLB miss（TLB缺失） Hit ratio（命中率） Context switch  TLB flushed
If the page number is not in the associative registers Get & store Hit ratio（命中率） The percentage of times that a page number is found in the associative registers Context switch  TLB flushed TLB replacement algorithm

41 具有块表的地址变换机构 + >

42 Effective Access Time 有效存取时间
设： Associative Lookup =  time unit; memory cycle time = t time unit; Hit ratio =  Effective Access Time (EAT) EAT = (t + )  + (2t + )(1 – ) = 2t +  – t If (20 ns), t(100 ns), 1(80%), 2(98%): TLB hit: =120 ns TLB miss: =220 ns EAT1 = 120* * 0.2 = 140 ns EAT2 = 120* * 0.02 = 122 ns

43 Memory Protection 内存保护
If page size 2n, page & frame is aligned at 2n, so … Memory protection implemented by associating protection bit with each frame Provide read only, read-write, execute-only protection or… Valid-invalid “valid”: the associated page is in the process’ logical address space, and is thus a legal page. “invalid”: the page is not in the process’ logical address space.

44 Valid/invalid bit example
Address space 214 Page size 2KB Process size (0~10468) Page 5 has internal fragmentation PTLR=6 Page 6 & 7 are invalid 10240 10486 12287

45 两级和多级页表 考虑： 地址空间：32位；页大小4KB；有220即1M个页 需要页表项：1M个 设，每个页表项使用32位表示，需要4MB的空间 解决方案： 进一步离散

46 两级页表 对页表分页，建立外层页表（页目录）
则上述4MB的页表，进一步分为1K个页 需要1K个页目录项 假设每个页目录项使用32位表示，需要4KB 因此，逻辑地址 where p1 is an index into the outer page table, and p2 is the displacement within the page of the outer page table. page number page offset p1 p2 d 10 12

47 两级页表举例

48 具有两级页表的地址变换机构 +

49 多级页表及其性能 Level number = L, effect memory accesses time = (L+1)t 考虑高速缓存技术： Cache hit rate of 98 percent yields: effective access time = 0.98 × × 520 = 128 nanoseconds. which is only a 28 percent slowdown in memory access time.

50 内容提要 存储器的层次结构 程序执行的基础知识、程序的装入和链接 连续分配存储管理方式
离散分配方式（Discrete Memory Allocation） 分页存储管理方式 碎片<页 分段存储管理 从逻辑上进行分段 段页式存储管理

51 分段存储管理方式 引入分段的目的，是为了满足用户在编程和使用上的需求（逻辑上） 在用户看来：
A program is a collection of segments. A segment is a logical unit such as: main program, procedure, function, method, Object local variables, global variables, common block, stack, symbol table

52 逻辑地址空间 A collection of segments A logical address
each segment <name, length> Two dimensional address space A logical address <seg-name, offset> <seg-num, offset> Compiler automatically constructs segments reflecting the input program. Pascal compiler FORTRAN compiler C compiler, such as gcc, … 段号 段内地址 31 16 15

53 Logical view of segmentation

54 Segment-table base register (STBR)
分段的硬件支持 段表 2-D logical address  1-D physical addresses; 每个段表项包括 段在内存中的基地址 段的长度 Segment-table base register (STBR) Points to the segment table’s location in memory. Segment-table length register (STLR) Indicates number of segments used by a program; Segment number s is legal if s < STLR.

55 段表举例

56 分段的地址变换机构 段表始址 段表长度 + ＞ 段号S 位移量W

57 分页和分段的主要区别 角度和目的不同 大小不同 地址空间的维数不同 分页：面向系统，物理上离散，减少外部和内部碎片，提高内存利用率
页是信息的物理单位 分段：面向用户，逻辑上离散，满足用户的需求 段是信息的逻辑单位，意义相对完整 大小不同 分页：大小固定，由硬件决定 分段：不固定，划分由程序决定，在编译时确定 地址空间的维数不同 分页：1维 分段：2维，段名＋段内偏移

58 分段举例 <segment2, 53> 4300 + 53 = 4353
How about <segment1,536>?

59 分段的好处 Relocation，可重定位，方便编程 Sharing Protection 动态增长 动态链接
Dynamic, by segment table Sharing shared segments same segment number Protection Use segment table entry Protection bit Read-only, execute-only, read/write Validation bit, 0illegal segment Protection & sharing at segment level 动态增长 动态链接

60 段的共享

61 关于代码的重入 可重入代码，又称为“纯代码”，是一种允许多个进程同时访问的代码。 绝对不允许可重入代码在执行中有任何改变

62 针对段的内存管理 由于段长不固定，采用动态分区管理方式 分配： 由于大小不固定，存在外部碎片 由于采用动态分区管理方式
首次适应、最佳适应等等 由于大小不固定，存在外部碎片 可能要考虑“紧凑” 由于采用动态分区管理方式 内部碎片很少

63 内容提要 存储器的层次结构 程序执行的基础知识、程序的装入和链接 连续分配存储管理方式
离散分配方式（Discrete Memory Allocation） 分页存储管理方式 碎片<页 分段存储管理 从逻辑上进行分段 段页式存储管理

64 段页式存储管理方式 考虑在分段的基础上分页 与单纯的分段相比 在段表项中存放的不是段的起始地址，而是段所对应的页表的起始地址

65 段页式举例：IA32体系结构中的段页机制 IA32是基于分段的，分页可选 常见的段寄存器如：CS, DS, ES, FS, GS, SS
IA32使用全局描述符表GDT或者局部描述符表LDT 每个描述符描述一个段，包括段大小、访问权限、基地址等 使用段选择子索引一个段 IA32的地址表示为，段：段内偏移 Linear address = segment base + segment offset 在不使用分页机制的情况下，线性地址就是物理地址 否则，线性地址通过页表机制转换成物理地址

66 IA32 address translation
2-level page table

67 作业 什么是内部碎片；什么是外部碎片 画出最基本的分页地址变换机构。 分页和分段的主要区别是什么？