第三章:内存管理

一、内存管理概念

1. 基本原理和要求

(1)程序执行过程

①编译

  • 编译形成若干目标模块,形成汇编文本

②链接

  • 把一组目标模块和需要的库函数链接在一起形成一个装入模块
  • 形成整个程序完整逻辑地址空间(2011)
  • 分类:
链接方式描述
静态链接方式在程序运行之前把目标模块和库函数链接成一个完整的装配模块
装入时动态链接边装入边链接
运行时动态链接程序执行时需要该模块时才链接

③装入

  • 把程序装入内存,且逻辑地址变为物理地址
  • 分类:
装入方式描述特点
绝对装入方式编译时便产生绝对地址,只适合单道程序环境编译时确定内存位置,运行时无需改变地址
静态重定位装入时对地址“重定位”,将逻辑地址一次性变为物理地址作业装入内存时,必须分配其要求的全部内存空间;作业装入内存后不能再移动,只适合固定分区
动态重定位装入内存后仍为逻辑地址,到程序真正执行时才地址转换,需要重定位寄存器的支持程序只需装入部分代码就可运行;需要硬件支持(动态重定位寄存器)

(2)进程的内存映像

(3)内存保护

  • 基本概念
    • 分区分配内存管理方式的主要保护措施是界地址保护(2009)
    • 内存保护需要由操作系统和硬件机构合作完成
  • 保护方法
    • 设置上下限寄存器,每当CPU访问地址时进行比较判断是否越界
    • 重定位寄存器和界地址寄存器配合
      • 首先逻辑地址和界地址寄存器(含逻辑地址最大值)进行比较,判断是否越界
      • 然后逻辑地址+重定位寄存器(含物理地址最小值)=物理地址

(4)内存共享

  • 可重入代码(纯代码):允许多个进程同时访问但不允许任何进程修改

2. 连续分配

分配策略描述特点
首次适应空闲分区按地址递增顺序链接。会留下很多碎片,但通常最快最好
循环首次适应空闲分区按地址递增顺序链接从上次找到的空闲分区的下一个空闲分区查找
最佳适应空闲分区按容量递增顺序链接最容易产生内存碎片(2019)
最坏适应空闲分区按容量递减顺序链接产生碎片的可能最小、会很快导致没有可用的大内存块
动态可重定位分区分配紧凑:移动内存中作业位置,把分散的小分区拼接成大分区

3. 离散分配

(1) 分页

①地址结构:页号+页内偏移量

②分页存储基本概念

  • 用户程序分为“页”或“页面”,内存空间分为“物理块”、“页框”或“页帧”;它们都大小相同
  • 地址结构:页号+页内地址
  • 页面过大会使页内碎片增多;页面过小会使页表过大占用内存
  • 页表
    • 系统为每个进程建立一张页表,记录页号和物理块号的对应关系
    • 页表由页表项组成,大多驻留在内存中

③基本地址变换机构

  • 在系统中有一个页表寄存器(PTR),存放页表在内存的起始物理地址和页表长度(2021)
  • 进程未执行时页表信息存放在进程PCB中,调度到进程时才把信息装入页表寄存器

④快表

  • 也叫相联存储器(TLB),在地址变换机构中增设的,为了减少对内存的访问次数(经常考)

⑤两级页表

  • 目的:解决页表大而连续问题
页表级别特点
单级页表会产生很多页表,这些页表需要连续存储且进程执行时必须全部调入内存
二级页表二级页表在进程执行时只需调入一级页表并调入所需页表
  • 特点
    • 顶级页表最多只能占一个页面
    • 多级页表不能减少页表所占用的内存空间,但是能减少占用的连续内存空间(2014)
    • 多级页表会减慢地址变换速度,可能增加缺页中断次数

(2)分段

①地址结构:段号+段内偏移量(2009、2016)

②特点

  • 呈现二维特性:既包含地址空间,又标识逻辑关系
  • 各段可以不等长、可以不相邻
  • 优点:方便编程;信息共享;信息保护;动态链接、动态增长等

③分页和分段的区别

概念区别
信息的物理单位,大小固定,一维的。为了系统,对用户不可见。
信息的逻辑单位,大小不定,二维的。为了满足用户的需求。

(3) 段页式

  • 地址结构:段号+段内页号+页内地址
  • 一个进程中只有一个段表,每个段对应一个页表
  • 段表寄存器和页表寄存器都有两个作用:在段表或页表中寻址、判断是否越界

二、虚拟内存管理

1. 虚拟内存基本概念

(1)传统存储方式特征

  • 一次性:作业必须一次性全部装入内存后才能开始运行
  • 驻留性:作业从开始运行到结束一直在内存中不会被换出

(2)局部性原理

局部性概念描述
时间局部性某条指令执行后不久可能再次执行,某个数据访问后不久可能被再次访问(程序的循环执行)
空间局部性某个存储单元访问后不久其附近的存储单元会被访问(指令的顺序执行、数据以向量、数组、表等形式簇聚存储)

(3)虚拟内存的特征

特征描述
多次性作业无需一次性全部装入内存,可以在需要时分多次调入内存。
对换性程序和数据无需常驻内存,可以在内存和外存之间进行交换。
虚拟性用户看到的逻辑内存容量远远大于实际的物理内存容量。

(4)虚拟内存技术的实现

  • 必须建立在离散分配(分页分段)的内存管理方式基础之上(2012)
  • 三种实现方式:请求分页、请求分段、请求段页式
  • 虚拟内存的实际容量=min{内存+外存,地址位数表示能力}(2012)
  • 虚拟内存的最大容量=地址位数的表示能力

2. 请求分页管理

(1)页表机制

  • 页表项:
页表项字段描述
状态位该页是否在内存(程序访问时参考)
访问字段访问字段:页面访问次数(页面置换算法使用)
修改位页面调入内存后是否被修改(页面置换时是否写回外存)
外存地址页面对应的物理块号(地址转换使用)

(2)缺页中断机构

  • 缺页中断属于内部异常,一条指令在执行期间可能产生多次缺页中断

3. 页框分配

(1)内存分配策略

①固定分配局部置换

  • 固定分配:每个进程固定数目的物理块;
  • 局部置换:只能在该进程所分配的内存页面进行调换

②可变分配全局置换

  • 可变分配:每个进程的物理块可适当增加或减少;
  • 全局置换:发现缺页将OS保留的空闲物理块取出一块分配

③可变分配局部置换

  • 正常情况下是固定分配局部置换
  • 若频繁缺页或缺页率一直很低,就采用可变分配全局置换

④固定分配全局置换

  • 不存在(2015)

(2)调入策略

①何时调入

调页策略描述
预调页策略一次调入若干个相邻的页,但页面可能不会被访问(主要用于进程的首次调入,由程序员指定)
请求调页策略当发现页面不在内存时再调入,页面一定会被访问(所学的虚拟存储器就是采用这种方法)

②从何处调入

外存划分描述I/O速度特点
文件区用于存放文件,通常采用连续分配方式。I/O速度较慢,因为涉及大量数据的读写。
对换区用于存放对换页面,通常采用离散分配方式。I/O速度较快,因为每次只访问少量数据。
情况调入方法
若对换区足够大都从对换区调入
若对换区不够大不会修改的从文件区调入;可能被修改的换出时调到对换区,以后从对换区调入
UNIX方式未运行过的页面从文件区调入;运行过但又被调出页面从对换区调入

③如何调入

  • 当进程所访问的页面不在内存中时(存在位为0),便向CPU发出缺页中断,中断响应后便转入缺页中断处理程序。该程序通过查找页表得到该页的物理块,此时如果内存未满,则启动磁盘IO,将所缺页调入内存,并修改页表。如果内存已满,则先按某种置换算法从内存中选出一页准备换出;如果该页未被修改过(修改位为0),则无须将该页写回磁盘;但是,如果该页已被修改(修改位为1),则必须将该页写回磁盘,然后将所缺页调入内存,并修改页表中的相应表项,置其存在位为1。调入完成后,进程就可利用修改后的页表形成所要访问数据的内存地址。(2011)

4. 页面置换算法

(1)最佳(OPT)置换算法

  • 置换出未来最长时间不被访问的页面(不可实现)

(2)先进先出(FIFO)置换算法

  • 设第一个队列,总是淘汰最先进入内存的页面
  • 可能出现Belady异常,即分配的物理块增多,缺页次数不减反增(2014)

(3)最近最久未使用(LRU)置换算法

  • 置换出最近最久未使用的页面
  • 需要一组寄存器或一个栈的支持

(4) Clock置换算法

①简单型

  • 某页被访问,置1;没有被访问,为0
  • 算法步骤:置换算法检查到0,换出,检查到1,置0,这样循环进行

②改进型

  • 再考虑一个因素:置换代价(修改过的页面置换代价大),将所有页面分为四类(访问位,修改位)
  • 算法步骤
    • 第一轮:寻找00的页面置换,不更改访问位和修改位
    • 第二轮:寻找01的页面置换,同时将扫描过得页面的访问位置0
    • 重复第一轮、第二轮……

5. 抖动和工作集

(1)抖动(颠簸)

  • 概念:刚刚换出的页面马上又要换入主存,刚刚换入的页面马上又要换出主存
  • 产生原因:系统中运行的进程太多,内存分配给每个进程的物理块太少
  • 抖动的预防策略
    • 采用局部置换策略
    • 使用工作集算法
    • 利用“L=S”调节缺页率
      • L:缺页之间平均时间;S:置换一个页面所需时间
    • 暂停一部分进程(增大对换区容量没有用)(2011)

(2)工作集

概念解释
工作集某段时间内进程访问的页面集合
工作窗口这段时间的长度
驻留集进程分配的物理页框的集合
工作窗口一般要远大于工作集;驻留集一般大于工作集

6. 内存映射文件

  • 概念
    • 将磁盘块映射到内存块,从而把进程对磁盘块的访问转换为对内存页的访问
  • 作用
    • 多个进程允许并发地内存映射同一个文件,以便实现数据共
    • 很多时候共享内存是通过内存映射实现的,进程可以通过共享内存来通信
 1\documentclass{article}
 2\usepackage{resume} % Assuming a custom resume.cls file is used
 3\usepackage{hyperref}
 4\usepackage[margin=1in]{geometry}
 5\usepackage{fancyhdr}
 6\usepackage{tabularx}
 7\pagestyle{fancy}
 8\fancyhf{}
 9\rhead{\today}
10\lhead{[Your Name]}
11\rfoot{\thepage}
12\begin{document}
13\begin{center}
14    {\Large [Your Name]} \\
15    \textit{[Address]} \\
16    \textit{[Phone]} \\
17    \textit{[Email]} \\
18    \textit{[LinkedIn Profile]} (if applicable) \\
19\end{center}
20\section*{EDUCATION}
21\begin{tabularx}{\linewidth}{@{}l X@{}}
22    \textbf{South Central University, Changsha, Hunan, China} & Bachelor of Law, October 2020 - July 2024 \\
23    & \textit{GPA: 89.79/100, ranked 2nd out of 28 students} \\
24    & \textit{Language Proficiency: IELTS 7.5, CET-6 559, CET-4 586} \\
25    & \textit{Awards: 3rd Prize in National English Competition for College Students (2023), 2nd Prize in 21st Century Cup National English Speaking Competition (2023)} \\
26    & \textit{Bar Exam: Passed the Objective Exam (2023), pending the Subjective Exam} \\
27    & \textit{Future Education: Admitted to Master of Law program in International Financial Law at Shanghai University of Finance and Economics} \\
28\end{tabularx}
29\section*{WORK EXPERIENCE}
30\begin{tabularx}{\linewidth}{@{}l X@{}}
31    \textbf{Guohao Lawyers (Changsha Office), Changsha, Hunan, China} & Legal Assistant, June - August 2022 \\
32    & \textit{Assisted in the issuance of USD bonds for Chinese companies, utilizing knowledge of international economic law and business law} \\
33    & \textit{Participated in all-English projects, providing legal opinions to bond issuers} \\
34\end{tabularx}
35\section*{SOCIAL RESPONSIBILITY}
36\begin{tabularx}{\linewidth}{@{}l X@{}}
37    \textbf{Legal Publicity and Education Practice in Miluo City, Hunan, China} & Project Leader, June - August 2022 \\
38    & \textit{Led a team to Miluo City to conduct legal publicity, drug prevention work research, and dissemination of legal knowledge} \\
39    & \textit{Achievements: University-level approval for the project, 1st Prize in the 17th Shenghua Cup extracurricular academic competition, selected for SKSUNNY Happy Action by China Youth Development Foundation, published reports in local media} \\
40\end{tabularx}
41\section*{RESEARCH EXPERIENCE}
42\begin{tabularx}{\linewidth}{@{}l X@{}}
43    \textbf{Entrepreneurship Training Project for College Students, South Central University, Changsha, Hunan, China} & Deputy Project Leader, May 2023 - Present \\
44    & \textit{Conducted research in over 10 mines and visited over 20 companies, leading to the establishment of an ecological restoration service system for mines} \\
45    & \textit{Achieved national-level approval for the project, integrating technical support and legal policy support} \\
46\end{tabularx}
47\section*{EXTRACURRICULAR ACTIVITIES}
48\begin{tabularx}{\linewidth}{@{}l X@{}}
49    \textbf{Challenge Cup Competition, South Central University, Changsha, Hunan, China} & Deputy Project Leader, June 2022 - May 2023 \\
50    & \textit{Conducted field surveys and questionnaires on elderly couples with chronic diseases in 6 communities in Changsha} \\
51    & \textit{Achieved 3rd Prize in university-level competition} \\
52\end{tabularx}
53\section*{HONORS \& AWARDS}
54\begin{tabularx}{\linewidth}{@{}l X@{}}
55    \textbf{Outstanding Individual in Social Practice, South Central University} & (2022) \\
56    \textbf{Outstanding Student, South Central University} & (2022) \\
57    \textbf{3rd Prize, National English Competition for College Students} & (2023) \\
58    \textbf{2nd Prize, 21st Century Cup National English Speaking Competition} & (2023) \\
59