第4章 存储器管理
1.概述–功能地址空间存储空间地址重定位
1.1 功能
-存储器分配：
-解决多进程共享主存的问题
-地址转换或重定位：
-研究各种地址变换方法及相应的地址变换机构。
-存储器保护：
-防止故障程序破坏OS和其它信息。
-存储器扩充：
-采用多级存储技术实现虚拟存储器，交换技术。
-存储器共享：
-研究并发进程如何共享主存中的程序和数据。
1.2 地址空间
符号名字空间：源程序中的各种符号名的集合所限定的空间。源程序用符号名访问变量和子程序。
编译：由于目标程序在主存中的位置是不可预知的，目标程序中的各个地址总是以“0”为参考地址顺序编码的；逻辑地址，相对地址，虚地址
逻辑地址空间：经编译链接后的程序大小所限定的空间。程序地址域，程序地址空间
1.3 存储空间
物理存储器中全部物理存储单元的集合所限定的空间；
每个物理存储单元（每个字节）都有自己的地址；
物理地址，绝对地址，实地址；
一个程序只有从地址空间装入到存储空间才能运行。
1.4 地址重定位
程序地址空间的逻辑地址->存储空间的物理地址
-又称为：地址映射，或地址变换
地址重定位的原因：
-地址空间的逻辑地址与分配到的存储空间的物理地址不一致。
-处理机执行用户程序时，所要访问的地址必须是实际的物理地址。
1.4.1 静态重定位
在进程执⾏前，由装⼊程序把⽤户程序中的的逻辑地址全部转换成物理地址；
特点：不需要硬件⽀持、要求占⽤连续的存储区、在程序执⾏期间不能移动，主存利⽤率低、难以做到程序和数据的共享、⽤于单道批处理系统
1.4.2 动态重定位
装入程序把用户程序和数据原样装入主存区。程序运行时，把该主存区的起始地址送入重定位寄存器。需硬件地址转换机构
用于多道批处理系统、分时系统
优点：主存利用充分；可移动用户程序，移动后，只需修改重定位寄存器；程序不必占有连续的主存空间；便于多用户共享主存中的程序和数据
1.4.3 程序的链接方式
静态链接：
-在构造可执行文件时，就将各目标模块与库例程链接在一起
-其映像形成的是个一维的地址域
动态链接：
-装入时动态链接：边装入边链接
-运行时动态链接：程序运行时才进行链接
-便于程序模块的共享，减少系统空间的开销
1.4 存储器保护
防止地址越界：
-进程运行时产生的所有存储器访问地址都要进行检查，确保只访问为该进程分配的存储区域。
存取方式的保护：
-对所访问的存储空间的存取方式（读、写、执行）进行检查，以防止由于误操作，使其数据的完整性受到破坏。
1.5 存储器共享
允许多个进程共享同一个主存区，以提高存储器利用率；
既可以是数据区，也可以是程序区；
被共享的程序叫可重入程序，无论执行多少遍，都保持不变；
具有这种性质的程序又叫纯代码。
通常存储器划分为两部分：
-操作系统占用区
-用户进程占用区（或用户区）
-存储器管理是指对用户区的管理
2.单用户单道程序的存储器分配
是一种最简单的存储管理方式。
用于单道批处理、单用户单任务系统。
单一连续区分配，主存只有一个用户作业。
作业一旦进入内存，就要等到它执行结束后才能释放内存。
存储保护容易实现，易判断地址是否越界
3.多用户多道程序的存储器分配——分区分配
把主存划分成若干个连续的区域，每个进程占用一个
系统中必须配置相应的数据结构，用来记录主存的使用情况，
为分配提供信息
-固定式分区
-可变式分区
3.1 固定式分区
适合多道程序的最简单的存储器管理方式
把主存预先划分成几个大小不等的分区
进程到达时，选择一个适合进程要求的最小空闲区分给进程；无适合的空闲分区时，让其等待
曾经在IBM OS/360大型机中运行了许多年
分区说明表：用以描述各分区的分配情况
内存管理程序
分配内存：
-检索分区说明表，找出一个空闲分区分配给进程，并置占用标志。若找不到空闲分区，就不分配内存。
回收内存：
-当进程执行完时，回收内存，将相应分区的状态置为未分配
缺点；主存利用不充分。因为作业的大小不可能刚好等于某个分区的大小，绝大多数已分配的分区中，都有一部分存储空间被浪费掉了。
优点：简单
3.2 可变式分区
按作业的⼤⼩动态地划分分区，使分区正好等于作业⼤⼩
-各分区的⼤⼩是不定的
-内存中分区的数⽬也是不定的
*管理分区的数据结构
3.2.1 分区说明表
分配主存：
-从未分配区表中找一个空闲区。将其一分为二，一部分分给作业，另一部分留在表中。
-在已分配区表中进行记录
回收主存：
-将回收的分区登记在未分配区表中。
-将该作业占用的已分配区表项置为空。
优点：⽐较直观、简单
缺点：由于主存分区个数不定，所以表格的⻓度不好确定。要么表格溢出，要么表格浪费
3.2.2 空闲区链
-是记录内存空闲区的一种较好方法
-已分配区，在进程的PCB中有记录
-在每个分区的首字和尾字中，有该区信息的记录
可变式分区–分配算法
首次适应法：
要求空闲区表或空闲区链中的空闲区按地址从小到大排列。
分配内存时，从起始地址最小的空闲区开始扫描，直到找到一个能满足其大小要求的空闲区为止。分一块给请求者，余下部分仍留在其中。
最佳适应法：
存储分配程序要扫描所有空闲区，直到找到能满⾜进程需求且为最⼩的空闲区为⽌。
-缺点：因为要查找所有的分区，所以⽐⾸次适应算法效率低；可能把主存划分得更⼩，出现很多⽆⽤的碎⽚。
-改进：从小到大对空闲区排序。
最坏适应法：
要扫描所有的空闲区，直到找到满⾜进程要求且为最⼤的空闲区为⽌。⼀分为⼆，⼀部分分给进程，另⼀部分仍留在链表中。
-⽬的：使剩下的空闲区可⽤。
-缺点：要扫描所有的空闲区；⼤空闲区的不断分割，可能满⾜不了⼤进程的要求。
-改进：从⼤到⼩对空闲区排序，以提⾼查找速度。
回收一个释放区
若释放区与空闲区相邻接，要进⾏合并。
3.3 地址重定位和存储器保护
固定分区：
-静态重定位，进程运⾏时使⽤主存物理地址。
-设置上、下界寄存器来实现存储器保护。
可变式分区：
-动态重定位，进程运⾏时CPU给出的是程序的逻辑地址。
-基址+限⻓寄存器。世界上第⼀台超级计算机CDC 6600使⽤该⽅案。
上、下界寄存器：
分别存放进程在主存区的最⾼地址和起始地址。进程运⾏时，下界寄存器≤CPU访存地址≤上界寄存器。否则产⽣地址越界错误，停⽌运⾏。
基址和限⻓寄存器：
进程运⾏时，将其分区的⾸地址装⼊基址（或重定位）寄存器，将其程序的⼤⼩装⼊限⻓寄存器。每个逻辑地址应⼩于限⻓寄存器内容。
3.4 分区管理的优缺点
主要优点：
-实现了多道程序共享主存。
-系统设计相对简单，不需要更多的软硬件开销。
-实现存储器保护的⼿段也⽐较简单。
缺点：
-主存利⽤不够充分。系统中总有⼀部分存储空间得不到利⽤，这部分被浪费的空间叫碎⽚。
-没有实现主存的扩充。进程的地址空间受实际存储空间的限制。
4.覆盖与交换技术
-覆盖与交换技术是解决⼤进程和⼩主存⽭盾的两种存储器管理技术，
-其实质是对主存进⾏逻辑扩充。
-覆盖技术主要⽤在早期的OS中，交换技术则在现代OS中仍具有较强的⽣命⼒。
覆盖：是指同⼀主存区可以被不同的程序段重复使⽤。
-通常⼀个进程由若⼲个功能上相互独⽴的程序段组成，进程在⼀次运⾏时，也只⽤到其中的⼏段。让那些不会同时执⾏的程序段共⽤同⼀个主存区。
覆盖段：可以相互覆盖的程序段。
覆盖区：可共享的主存区。
系统必须提供相应的复盖管理控制程序。⽤户提供复盖结构。通常难以分析和建⽴程序的复盖结构。
复盖技术主要⽤于系统内部程序的主存管理上。
*特点：打破了必须将⼀个进程的全部信息装⼊主存后才能运⾏的限制。在逻辑上扩充了主存。⼩主存可运⾏⼤进程。
交换：系统根据需要把主存中某个暂时不运⾏的进程的部分或全部信息移到外存，⽽把外存中的某个进程移到主存，并使其投⼊运⾏。
交换的目的：解决主存容量不够大的问题；保证分时用户的合理响应时间。
交换的时机：进程用完时间片或等待输入输出时；进程要求扩充其占用的存储区而得不到满足时。
交换技术的关键：设法减少每次交换的信息量；常将进程的副本保留在外存，每次换出时，仅换出那些修改过的信息即可。
文件区、交换区：具有交换功能的OS，通常把外存分为⽂件区和交换区
-⽂件区存放⽂件
-交换区存放从内存换出的进程
通常，交换区⼤⼩是内存的⼀到两倍
Windows的交换区是⼀个⼤⽂件：pagefile.sys
5.页式存储器管理
在分区存储管理中，每道程序要求占⽤主存的⼀个连续的存储区域，因⽽会产⽣许多碎⽚。
⻚式存储管理允许⼀个进程占⽤不连续的存储空间，从⽽克服了碎⽚。
5.1 页式管理的实现原理
主存块（⻚框）：
把主存分成⼤⼩相等的若⼲块。块的⼤⼩⼀般为1024或4096字节等2的整次幂。
逻辑⻚（⻚）：
-进程的地址空间被划分成与主存块⼤⼩相等的逻辑⻚。
-可以将进程中的任意⼀⻚放到主存的任意⼀块中，实现了离散分配。
页表：系统为每个进程建立一张页面映像表，记录逻辑⻚与主存块的映射关系。
-⻚表存放在主存。
-控制寄存器：在⻚式管理中，系统为每个处理机设⽴⼀个控制寄存器，⽤以记录现运⾏进程的⻚表始址和⻚表⻓度。
-硬件动态地址转换机构MMU负责将逻辑地址转换为物理地址。
5.2 页式动态地址变换
硬件动态地址转换机构负责将这个逻辑地址转换为物理地址。⼯作过程如下：
-(1) 把该进程的⻚表始址和⻚表⻓度放⼊ CPU 的控制寄存器中。
-(2) 将程序计数器内容的⻚号部分与控制寄存器中的⻚表⻓度相⽐较，若⻚号p⼩于⻚表⻓度时转(3)，否则产⽣地址越界，终⽌程序运⾏。
-(3) 将程序计数器中的⻚号与控制寄存器中的⻚表始址相加，得到该访问操作所在⻚号在⻚表中的⼊⼝地址。
*这⾥的加是根据⻚表项占⽤的字节数决定的。
⻚号在⻚表中的⼊⼝地址=⻚表始址＋⻚号×⻚表项占⽤的字节数
-(4) ⽤该地址去访⻚表，获得该⻚所对应的主存块号。
-(5) 把主存块号与程序计数器中的⻚内地址相拼接，从⽽得到该操作对应主存的物理地址。
5.3 快表和联想存储器
在上述地址转换过程中，执⾏⼀次访内操作⾄少要访问主存两次。降低了程序的执⾏速度。
-⼀次访问⻚表；
-⼀次实现指定操作。
5.3.1 联想存储器
联想存储器：(TLB, Translation Lookaside Buffer转换检测缓冲区)
-为了提⾼存取速度，在地址变换机构MMU中增设⼀个具有并⾏查找能⼒的⾼速缓存（寄存器组）
-并⾏的意思是不增加额外的访问时间
-⽤来存放最近访问过的⻚表项
-存取速度⽐主存快，造价⾼
-⽤8～16个寄存器，就可提⾼程序执⾏速度
5.3.2 快表
快表：存放在高速缓存中的页表
快表的格式
-状态位：指示该寄存器是否被占⽤。0表示空闲，1表示占⽤。
-访问位：指示该⻚最近是否被访问过。0表示没有访问过，1表示访问过。
5.3.3 引入快表的地址变换过程
同时开始两个变换：利⽤主存⻚表进⾏的正常变换；利⽤快表进⾏的快速变换。
-快表中有待查找的⻚号时，⽴即停⽌正常访问主存⻚表的过程。
-快表中没有要查询的⻚。则继续正常的转换过程。还要把从主存⻚表中取出的块号和CPU给出的⻚号⼀起写⼊快表中。（找空闲快表项；⽆时再找最近没被访问的快表项）
5.4 页式管理的主存分配与保护
⻚式主存分配
-⻚表：每个进程⼀个，在主存，⽤来实现将进程的虚⻚转换成主存的物理块。
-进程控制块 ：存有⻚表在主存的始址和⻚表⻓度。
-存储空间使⽤情况表：存储分块表、位示图。
存储分块表：
记录存储器中的块的占⽤情况。表的第⼀项指出当前空闲块总数，第⼆项为指向第⼀个空闲块的指针，各空闲块通过单向链链接在⼀起。
-分配主存时，查存储分块表先查空闲块总数是否够⽤，再分配。同时为进程建⽴⻚表。
-进程完成时，回收主存块。
位示图：
每个主存块对应位示图中的⼀位。0表示空闲，1表示被占⽤。
-主存块号<–>位示图中的字节、位
-块越⼩，位示图越⼤；块越⼤，位示图越⼩。
页式管理的存储器共享与保护
在系统中，很多程序代码是可共享的，⻚式管理共享受限。不好共享程序中的部分代码。
保护：可在⻚表中增加对该⻚的操作⽅式位，以表示是可读写/只读/只执⾏等。
6.段式存储器管理
前⾯介绍的各种存储管理技术中，⽤户的地址空间已被链接成⼀个⼀维的空间。
通常，⼀个进程由若⼲个程序段和数据段组成。共享⽤户编写的某些程序段和数据段是现代操作系统必须解决的问题。
6.1 段式管理的实现原理
-把程序划分成若干段，每个段都有自己的段名。
-每个段都有从”0”开始编址的一维地址空间。
-进程的地址空间是⼆维地址空间。
-逻辑地址：段号S和段内地址W。段名->段号。
分段地址空间：以段为单位分配内存，每段占用一个连续的主存空间，各段之间可以不连续。
6.2 段式动态地址变换
与页式管理基本相同
段表：
-实现从逻辑地址到物理地址的变换
-系统为每个进程建⽴⼀个段表
进程运⾏时，由系统将该进程的段表始址和段表⻓度送⼊控制寄存器中。
6.3 段的存储保护和共享
段的存储器保护
-第⼀级保护：控制寄存器的段表⻓度＞段号
-第⼆级保护：段表中的段⻓＞段内地址
-对段的信息进⾏保护：在段表中增加相应的操作⽅式字段，对相应的段规定读、写、执⾏是否许可的操作权限。
段的共享：
-易实现段的共享。使各进程的段表项指向共享段的物理地址
6.4 段的存储器分配
类似于“可变式分区”
-分区说明表或空闲区链表
-⾸次适应法、最佳适应法、最坏适应法
“可变式分区”是以进程为单位分配⼀个连续的分区；“段式管理”是以段为单位分配⼀个连续分区，各段之间可以不连续
同样不可避免碎⽚问题
6.5 段式与页式管理的比较
-段是由⽤户划分的；⻚是由硬件划分的，对⽤户是透明的。
-⻚的⼤⼩固定；段的⼤⼩不固定。
-段式⽤⼆维地址空间；⻚式⽤⼀维地址空间。
-段允许动态扩充，便于存储保护和信息共享。
-段可能产⽣主存碎⽚；⻚消除了碎⽚。
-段式管理便于实现动态链接，⻚式管理只能进⾏静态链接 。
-段与⻚⼀样，实现地址变换开销⼤，表格多。
7.虚拟存储器管理
实存管理技术：
进程运⾏时，其执⾏实体必须全部装⼊主存
虚拟存储技术：
进程运⾏时，其执⾏实体不必完全在主存中。程序可以⽐物理主存⼤
现在，功能较强的计算机均采⽤了虚拟存储器管理技术。
7.1 虚拟存储器管理
7.1.1 虚拟存储器
-是为满⾜应⽤对存储器容量的巨⼤需求⽽构造的⼀个⾮常⼤的地址空间。
-其容量由计算机的地址域确定，如32位地址空间虚存容量是4GB，64位地址是16EB
-虚存容量可以⼤于物理主存的容量
-虚存容量可以超过内存和辅助存储空间之和
-虚拟内存的最⼤容量是由计算机的地址结构（CPU寻址范围）确定
-虚拟内存的实际容量=min(内存和外存之和,CPU寻址范围)
7.1.2 程序访问的局部性原理
时间局部性：
-程序中往往含有许多循环，在⼀段时间内会重复执⾏该部分。被引⽤过的变量在不远的将来再次被引⽤
空间局部性：
程序中含有许多分⽀，在⼀次执⾏中，只有满⾜条件的代码运⾏，不满⾜条件的代码不运⾏。即使顺序执⾏程序，程序的地址域在短时间内变化不⼤。
7.1.3 支持虚拟存储器的物质基础
有⼀个⼤的CPU地址结构
采⽤多级存储结构（最流⾏的为⼆级）：要有⼤容量的外存，⾜以存放多⽤户的程序；要有⼀定容量的主存
地址转换机构(MMU)，以动态实现虚地址到实地址的地址变换
7.2 页式虚拟存储器管理
实现原理
-请求⻚式管理
-将进程信息的副本存放在磁盘辅助存储器中，并为其建⽴⼀张外⻚表，指出各⻚对应的辅存地址。
-当进程被调度运⾏时，先将进程中的较少⻚装⼊主存，在执⾏过程中，访问不在主存⻚时，再将其调⼊。
7.2.1 页面调度策略
取页
请求调⻚
预调⻚：需要调⼊某⻚时，⼀次调⼊该⻚以及相邻的⼏个⻚。能减少I/O次数
-置⻚：把调⼊的⻚放在主存何处。
-置换：固定分配局部置换。
进程地址空间的页有的在主存，有的在辅存，为此要修改页表。
保护码：对该页的读/写/执行操作的许可。
有效位（状态位）：⽤来指示某⻚是否在主存。
-为1表示该⻚在主存，完成正常的地址变换；
-为0表示该⻚不在主存，由硬件发出⼀个缺⻚中断，转操作系统进⾏缺⻚处理
修改位：指示该页调入主存后是否被修改过
-“1”表示修改过，“0”表示未修改过。
访问位（引用位）：指示该页最近是否被访问过
-“1”表示最近访问过，“0”表示最近未访问
缺页处理过程简述
-根据当前指令的逻辑地址查⻚表的有效位。
-有效位为0，该⻚不在主存，产⽣缺⻚中断。
-操作系统处理缺⻚中断，寻找⼀个空闲块（⻚框）
-若有空闲⻚框，则装⼊所需⻚。
-若⽆空闲⻚框，则按⻚⾯置换算法选择⼀个已在主存的⻚，进⾏淘汰。若修改过还要写磁盘。装⼊需要的⻚。之后要修改相应的⻚表和主存分块表。
-恢复现场，重新执⾏被中断的指令。
7.2.2 页面置换算法
-抖动现象：刚被置换的⻚⾯⻢上⼜要⽤，因⽽⼜要把它调⼊。调⼊不久再被置换，置换不久再次装⼊。如此频繁地调⼊调出，降低了系统的处理效率。
-算法假设：⼀个进程分配的主存块数固定不变，且采⽤局部置换(在本进程内部置换)。
最佳置换算法（OPT算法）
-选择以后不再访问的页或经很长时间之后才可能访问的页进行置换。
先进先出置换算法(FIFO)
-发⽣⻚⾯置换时，置换在主存驻留时间最⻓的那⼀⻚。
-⻚表⾥的⻚⾯，按访问先后顺序排成⼀个队列，设置队列头指针，指向最早进⼊的⻚。发⽣⻚⾯置换时，置换头指针所指的⻚，然后头指针加1，循环向下指。表⻓为获得的主存块数。
-有可能出现抖动：因为在主存驻留时间最⻓的⻚未必是最⻓时间以后才被访问的⻚。频繁地调⼊调出。
-Belady异常：Belady在1969年发现，采⽤FIFO算法，当为进程分配的主存块多时，有时产⽣的缺⻚中断次数反⽽增多。
最近最少使⽤的⻚⾯置换算法(LRU)
最近最少使⽤LRU, Least Recently Used。
-根据局部性原理，置换那些在最近⼀段时间⾥最少使⽤的⼀⻚。
-进程的⼯作集：在⼀段时间内，进程集中在⼀组⼦程序或循环中执⾏，导致所有的存储器访问局限于进程地址空间的⼀个固定的⼦集。
-利⽤栈记录⻚的使⽤。正在引⽤的⻚放在栈顶，最近最少使⽤的⻚放在栈底
-为了便于栈中元素移动，可采⽤双向链
-具有LRU算法特性的⼀类算法所具有的性质：$M(m, r) \subseteq M(m + 1, r)$
-m为分配的主存块数，r为⻚⾯引⽤序列。
-公式表明：在任何时刻，主存块为m+1时，存于主存中的⼀串⻚⾯必然包含主存块为m时存于主存中的各⻚。决不会出现Belady异常。
时钟⻚⾯置换算法
-第⼆次机会算法，近似LRU算法
-⻚表中的引⽤位：0表示最近未被引⽤；1表示最近被引⽤。
-将进程所访问的⻚放在⼀个像时钟⼀样的循环链中。链中的节点数就是为之分配的主存块数。
-系统设有⼀个指针指向最早进⼊主存的⻚。
-淘汰时，检查指针所指⻚。若引⽤位为0，则⽤新⻚置换之，指针向前⾛⼀个位置。若引⽤位为1，清0，指针前进，直到找到引⽤位为0的⻚。
7.3 页式管理设计中应考虑的问题
7.3.1 交换区的管理
-交换区是OS利⽤磁盘扩充主存的主要⽅法。
-交换空间的设置：可以从⽂件系统中分割⼀部分空间作为⼀个⼤⽂件使⽤；或者占⽤⼀个独⽴的磁盘或磁盘分区。
-Windows使⽤“⻚⽂件pagefile.sys”作为主存的补充。当系统启动时，打开⻚⽂件。
7.3.2 页尺寸
-操作系统设计者可以选择⻚的⼤⼩。4KB/4MB
-⻚尺⼨⼤：⻚的内部碎⽚⼤（进程的代码段、数据段、堆栈段的最后⼀⻚都有内部碎⽚）
-⻚尺⼨⼩：进程的⻚表⻓
7.3.3 页的共享
⻚的共享可以避免在主存中同时有多个相同⻚的副本。节约主存
需要⼀个专⻔的数据结构来记录共享⻚（原型⻚表P313）
把共享⻚锁在内存，且在⻚表中增加引⽤计数项，仅当其引⽤计数为0时，才允许调出或释放盘空间。
7.3.4 多级页表的结构
⼤⻚表：(地址空间4GB)/(⻚4KB)=1M个⻚表项。若每个⻚表项占4B，则最⼤的⻚表为4MB，需占⽤1K个⻚框
采⽤多级⻚表结构，⻚表在内存不必连续存放
不在装⼊主存时，⽽是推迟到要访问⻚时，才为包含该⻚的⻚表分配空间
Linux，WindowsP309
7.3.5 写时复制技术的利用
写时复制的⻚⾯保护：若没有进程向共享主存⻚写时，两个进程就共享之。若有进程要写某⻚，系统就把此⻚复制到主存的另⼀个⻚框中，并更新该进程的⻚表，使之指向此复制的⻚框，且设置该⻚为可读/写。
⽗⼦进程之间的写时复制：⽗⼦进程最初共享⽗进程的所有⻚，将这些⻚标记为写时复制。
Windows ，Linux
7.4 段式虚拟存储器管理
7.4.1 实现原理
-⼜叫请求段式管理
-把进程的所有段的副本存放在外存中
-进程运⾏时，再把需要的段装⼊主存
动态增⻓标志位：是为动态数组和动态表设计的。
-为1表示该段允许动态增⻓，这样在段⻓越界中断时，不做越界处理，⽽由操作系统扩充其段⻓；
-为0表示不允许动态增⻓。
进程执⾏：访问某段时，由硬件地址转换机构查段表。若该段不在主存，则硬件发⼀个缺段中断。由操作系统完成缺段中断处理。
缺段中断机构与缺⻚中断机构类似：
-在⼀条指令的执⾏期间产⽣和处理中断。
-在⼀条指令的执⾏期间可能产⽣多次缺段中断。
⽐缺⻚中断的处理复杂，因为段是不定⻓的。
7.4.2 段的动态链接和装入
动态链接：程序开始运⾏时，只需将主程序段装⼊主存即可。在主程序段运⾏过程中，⽤到⼦程序时，再将其与主程序段连接上。
-需增加两个硬件功能：间接编址字、连接中断位。
-间接编址字：硬件指令的间接地址中包含的字。
-连接中断位L：表示是否需要动态链接的标志位。
L=0：表示不要进⾏动态链接；
L=1：表示要进⾏动态链接，产⽣链接中断信号，转操作系统处理，完成段的动态链接。
7.4.3 段的共享
利⽤段的动态链接很容易实现段的共享。由于各进程对共享段的使⽤情况不同，每个进程为其分配的段号也不同。
为了便于多进程共享主存中的公⽤⼦程序，可在主存中设置⼀个共享段段表。其内容可包括：共享段名、在主存的始址、段⻓，调⽤该段的进程数及进程名。
7.4.4 段页式虚拟储存器管理
⻚式管理主存利⽤率⾼
段式管理便于信息共享和存取保护
段⻚式管理的基本思想：
-程序的逻辑结构按段划分
-每段再按⻚划分
习题
1.存储器管理的功能。名字空间、地址空间、存储空间、逻辑地址、物理地址。
-存储器管理的功能：
-存储器分配：解决多进程共享主存的问题。
-地址转换或重定位：研究各种地址变换方法及相应的地址变换机构。
-存储器保护：防止故障程序破坏OS和其它信息。
-存储器扩充：采用多级存储技术实现虚拟存储器，交换技术。
-存储器共享：研究并发进程如何共享主存中的程序和数据。
-名字空间：源程序中的各种符号名的集合所限定的空间。源程序用符号名访问变量和子程序。
-地址空间：经编译链接后的程序大小所限定的空间。程序地址域，程序地址空间。
-存储空间：物理存储器中全部物理存储单元的集合所限定的空间。
-逻辑地址：也称虚拟地址，是由CPU生成的地址，用于程序和进程之间访问内存，不直接对应物理内存上的特定位置。
-物理地址：是实际内存硬件上的地址，对应于计算机内存芯片的物理位置；是逻辑地址经过地址映射后得到的实际地址。
2.什么是地址重定位?分为哪两种?各是依据什么和什么时候实现的?试比较它们的优缺点。
-地址重定位：程序地址空间的逻辑地址映射到存储空间的物理地址。
-种类：静态重定位、动态重定位
-静态重定位：在进程执⾏前，由装⼊程序把⽤户程序中的的逻辑地址全部转换成物理地址。
-动态重定位：装入程序把用户程序和数据原样装入主存区。程序运行时，把该主存区的起始地址送入重定位寄存器。需硬件地址转换机构
-优缺点（特点）：
-静态重定位：不需要硬件⽀持；要求占⽤连续的存储区；在程序执⾏期间不能移动，主存利⽤率低；难以做到程序和数据的共享；⽤于单道批处理系统
-动态重定位：主存利用充分；可移动用户程序，移动后，只需修改重定位寄存器；程序不必占有连续的主存空间；便于多用户共享主存中的程序和数据
3.内存划分为两大部分：用户空间和操作系统空间。存储器管理是针对用户空间进行管理的。
存储器共享：
通常存储器划分为两部分：
-操作系统占用区
-用户进程占用区（或用户区）
-存储器管理是指对用户区的管理
4.存储保护的目的是什么?对各种存储管理方案实现存储保护时，硬件和软件各需做什么工作?
存储保护的目的：
-防止非法访问：避免进程访问未经授权的内存区域。
-数据完整性：保护系统和用户数据不被恶意或意外破坏。
-系统稳定性：防止错误的内存访问导致系统崩溃。
-进程隔离：确保各进程互相隔离，彼此独立运行，提高系统安全性。
-优化资源利用：通过控制内存访问，优化系统资源的使用效率。
硬件工作：
-内存管理单元（MMU）：
-负责地址转换，将逻辑地址（虚拟地址）转换为物理地址。
-通过页表实现逻辑地址到物理地址的映射。
-页面保护机制：
-设置每个页面的权限，如读取、写入、执行权限。
-防止进程访问不具备权限的内存区域。
-段寄存器和段描述符（在使用分段机制的系统中，如早期的x86架构）：
-存储段基地址、段界限和段权限。
-通过比较和权限检查，防止越界访问和非法操作。
-特权级别：
-硬件支持不同的运行级别（如用户态和内核态），防止低级别（用户态）访问高级别（内核态）的内存空间。
软件工作：
-操作系统的内存管理模块：
-负责分配和回收内存，对各进程分配相应的内存空间。
-维护页表和段表，确保正确的地址映射。
-页面调度与交换：
-处理页面的调度和换入换出，尽量保证活跃页面在物理内存中。
-实现页面置换算法，优化内存利用率。
-访问控制策略：
-实现和维护内存的访问控制列表（ACL），针对不同进程设置不同的访问权限。
-异常和中断处理：
-当发生非法内存访问时（如非法地址、越界访问），操作系统捕获相应的中断或异常，进行处理并通知进程或采取其他措施（如终止进程）
5.试述可变式分区管理空闲区的方法、算法及存储区的保护方式。覆盖与交换有什么特点？
可变式分区：按作业的⼤⼩动态地划分分区，使分区正好等于作业⼤⼩
-各分区的⼤⼩是不定的
-内存中分区的数⽬也是不定的
管理空闲区的方法（数据结构）：
-分区说明表
-分配主存：从未分配区表中找一个空闲区，将其一分为二，一部分分给作业，另一部分留在表中；在已分配区表中进行记录。
-回收主存：将回收的分区登记在未分区；将该作业占用的已分配区表项置为空。
-空闲区链
-是记录内存空闲区的一种较好方法；已分配区，在进程的PCB中有记录；在每个分区的首字和尾字中，有该区信息的记录。
可变式分区——分配算法：
首次适应法：
-要求空闲区表或空闲区链中的空闲区按地址从小到大排列。
-分配内存时，从起始地址最小的空闲区开始扫描，直到找到一个能满足其大小要求的空闲区为止。分一块给请求者，余下部分仍留在其中。
最佳适应法：
-存储分配程序要扫描所有空闲区，直到找到能满⾜进程需求且为最⼩的空闲区为⽌。
最坏适应法：
-要扫描所有的空闲区，直到找到满⾜进程要求且为最⼤的空闲区为⽌。⼀分为⼆，⼀部分分给进程，另⼀部分仍留在链表中。
覆盖：是指同⼀主存区可以被不同的程序段重复使⽤。通常⼀个进程由若⼲个功能上相互独⽴的程序段组成，进程在⼀次运⾏时，也只⽤到其中的⼏段。让那些不会同时执⾏的程序段共⽤同⼀个主存区。
交换：系统根据需要把主存中某个暂时不运⾏的进程的部分或全部信息移到外存，⽽把外存中的某个进程移到主存，并使其投⼊运⾏。
6.页表的作用是什么?简述页式管理的地址变换过程。能利用页表实现逻辑地址转换成物理地址。管理内存的数据结构有哪些？
页表的作用：
-虚拟地址到物理地址的映射：
-每个进程运行时都使用虚拟地址空间，操作系统通过页表将虚拟地址映射到物理内存中的实际地址。
-由于每个进程都有自己的虚拟地址空间，页表能够保证不同进程的虚拟地址不会互相干扰。
-支持分页管理：
-操作系统使用分页（Paging）机制来管理内存，将物理内存和虚拟地址空间划分为相同大小的页（页面），这些页在虚拟内存和物理内存中不是连续的。
-页表记录了每一页虚拟地址与物理地址之间的对应关系。每个虚拟页面对应一个物理页框。
-实现虚拟内存：
-虚拟内存技术让程序认为自己拥有完整的内存空间，尽管物理内存有限。页表帮助操作系统管理虚拟地址与物理内存的关系，允许操作系统根据需要将虚拟页换入或换出物理内存（即页面置换）。
-支持内存保护：
-页表不仅存储虚拟地址到物理地址的映射，还可以在每个页面上设置权限（如只读、读写、不可执行等）。这样，操作系统可以防止程序非法访问或修改不该访问的内存区域，从而提供内存保护。
-例如，页表可以标记某些页面是不可写的，这样即使程序想修改这些页面的内容，硬件也会阻止这种操作，防止程序越权访问。
-优化内存管理（通过多级页表）：
-在现代操作系统中，页表的大小可能非常庞大，因此常常采用多级页表（如二级页表、三级页表等）来减少内存开销和加速查找过程。
-多级页表减少了每个进程为页表分配的内存开销，同时仍能有效地进行地址映射。
-支持共享内存：
-不同进程可以通过页表映射共享物理内存区域。在这种情况下，多个进程会将相同的物理内存页映射到它们的虚拟地址空间，从而实现共享内存。
-实现惰性分配：
-页表支持惰性分配内存，操作系统可以按需分配物理内存。只有当程序真正访问某个虚拟页面时，操作系统才会为其分配物理内存，并进行页表更新。
-这有助于优化内存使用，避免不必要的内存分配和浪费。
页式管理的地址变换过程：
（1）虚拟地址的组成： 虚拟地址通常由两部分组成：
-虚拟页号：表示虚拟地址中对应的虚拟页面的编号。
-页内偏移：表示在虚拟页面内部的具体位置，用来指示该页内的字节偏移。
（2）查找页表：每个进程都有一个页表，页表将虚拟页号映射到物理页框号。操作系统通过查找进程的页表，找到虚拟页号对应的物理页框号。
（3）计算物理地址：一旦通过页表得到了物理页框号，就可以将物理页框号与页内偏移结合，形成物理地址。
-物理地址 = 物理页框号 + 页内偏移
管理内存的数据结构：页表、段表、页面目录、内存分配表、伙伴系统、交换区表、内存池、虚拟内存管理单元、访问控制表、栈、堆。
7.什么是页式存储器的内零头?它与页的大小有什么关系?可变式分区管理产生什么样的零头（碎片）？
页式存储器的内零头：由于内存块大小固定（通常是页面大小）而导致的内存空间浪费。
与页的大小的关系：页面较小，则内零头较小；如果页面较大，则内零头可能较大。
可变式分区管理产生的零头：外部碎片、内部碎片。
-外部碎片：由于分区的大小和分配顺序的不规律，内存中可能会出现许多小的空闲区域，这些区域的总大小可能足够容纳一个程序，但由于这些区域不连续，程序无法使用它们。外部碎片会随着内存分配和回收的频繁变化而累积。
-内部碎片：当一个程序被分配的内存空间大于它实际需要的内存时，剩余的未使用空间就会成为内碎片。虽然可变分区管理可以更精确地匹配程序的需求，但由于分区的分配仍然可能按固定大小进行，所以有时会出现类似的浪费。
8.段式存储器管理与页式管理的主要区别是什么?
段是由⽤户划分的；⻚是由硬件划分的，对⽤户是透明的
⻚的⼤⼩固定；段的⼤⼩不固定
段式⽤⼆维地址空间；⻚式⽤⼀维地址空间
段允许动态扩充，便于存储保护和信息共享
段可能产⽣主存碎⽚；⻚消除了碎⽚
段式管理便于实现动态链接，⻚式管理只能进⾏静态链接
段与⻚⼀样，实现地址变换开销⼤，表格多
9.什么是虚拟存储器。虚拟存储器的容量能大于主存容量加辅存容量之和吗?
虚拟存储器：是为满⾜应⽤对存储器容量的巨⼤需求⽽构造的⼀个⾮常⼤的地址空间。
虚拟存储器的容量可以大于主存容量加辅存容量之和。
10.实现请求页式管理，需要对页表进行修改，一般要增加。试说明它们的作用。
有效位（状态位）：⽤来指示某⻚是否在主存。
-为1表示该⻚在主存，完成正常的地址变换；
-为0表示该⻚不在主存，由硬件发出⼀个缺⻚中断，转操作系统进⾏缺⻚处理
修改位：指示该页调入主存后是否被修改过
-“1”表示修改过，“0”表示未修改过。
访问位（引用位）：指示该页最近是否被访问过。
-“1”表示最近访问过，“0”表示最近未访问。
11.产生缺页中断时，系统应做哪些工作?
-根据当前指令的逻辑地址查⻚表的有效位。
-有效位为0，该⻚不在主存，产⽣缺⻚中断。
-操作系统处理缺⻚中断，寻找⼀个空闲块（⻚框）
-若有空闲⻚框，则装⼊所需⻚。
-若⽆空闲⻚框，则按⻚⾯置换算法选择⼀个已在主存的⻚，进⾏淘汰。若修改过还要写磁盘。装⼊需要的⻚。之后要修改相应的⻚表和主存分块表。
-恢复现场，重新执⾏被中断的指令。
12。会利用FIFO、LRU、OPT以及时钟页面置换算法描述页面置换过程，计算产生的缺页率。Belady异常。
FIFO算法：
-发⽣⻚⾯置换时，置换在主存驻留时间最⻓的那⼀⻚。
-⻚表⾥的⻚⾯，按访问先后顺序排成⼀个队列，设置队列头指针，指向最早进⼊的⻚。发⽣⻚⾯置换时，置换头指针所指的⻚，然后头指针加1，循环向下指。表⻓为获得的主存块数。
LRU算法：
-每当一个页面被访问时，将其标记为“最近使用”。
-当需要替换页面时，选择最久未被使用的页面进行替换。
OPT算法：
-在内存已满的情况下，选择在未来访问序列中最远将来才被使用的页面进行替换。
时钟页面置换算法：
-每当访问一个页面时，设置该页面的访问位为1。
-当内存满时，时钟指针会扫描页面，若页面的访问位为0，则将其替换；若访问位为1，则将其置为0，并将时钟指针向前移动，继续扫描下一个页面。
缺页率计算公式：缺页率=缺页次数/总访问次数
Belady异常：指在某些页面置换算法中，增加内存的页面数反而会导致缺页率增加。FIFO算法最容易出现。
13.什么是程序的局部性原理？什么叫系统抖动?工作集模型如何防止系统抖动?
程序段局部性原理：
-时间局部性：程序中往往含有许多循环，在⼀段时间内会重复执⾏该部分。被引⽤过的变量在不远的将来再次被引⽤。
-空间局部性：程序中含有许多分⽀，在⼀次执⾏中，只有满⾜条件的代码运⾏，不满⾜条件的代码不运⾏。即使顺序执⾏程序，程序的地址域在短时间内变化不⼤。
系统抖动：操作系统频繁地发生页面置换，导致计算机性能严重下降的现象。
工作集模型防止系统抖动的方法：
-动态内存分配：工作集模型会根据进程的实际需要动态调整内存的分配大小。操作系统会监视进程的工作集大小，并确保为其分配足够的内存。这样可以避免由于内存不足而导致频繁的页面置换。
-限制页面置换：当系统知道某个进程的工作集已经被加载到内存中时，它会避免过多地将其他页面置换进出内存，减少页面置换的频率，从而减少系统抖动的发生。
-避免过多的页面交换：工作集模型通过减少页面的频繁置换来降低系统抖动，确保每个进程的工作集保持在内存中，从而减少了大量的I/O操作和页面交换。
14.多级页表的概念，多级页表中页表建立的时机。写时复制技术的概念。
多级页表是一种虚拟内存管理技术，用于解决大规模内存管理中单级页表存在的问题。
多级页表中页表建立的时机：
-一级页表在系统启动时会被分配，并且通常包含指向各二级页表的指针。
-二级页表及其他级别的页表则只有在需要访问对应的虚拟页面时才会建立。当CPU尝试访问某个虚拟地址时，操作系统会查找虚拟地址中对应的页表。如果某一页表尚未建立，操作系统会触发页表缺失中断，动态分配并建立所需的页表。
写时复制技术的概念：在多个进程共享相同的内存区域时，只有在某个进程尝试修改这些内存区域时，才会进行拷贝。
15.页的共享问题。需要一个专门数据结构来记录进程间共享页。
-⻚的共享可以避免在主存中同时有多个相同⻚的副本。节约主存
-需要⼀个专⻔的数据结构来记录共享⻚
-把共享⻚锁在内存，且在⻚表中增加引⽤计数项，仅当其引⽤计数为0时，才允许调出或释放盘空间。
