第4章-内存管理

第4章内存管理(MemoryManagement)4.1概述4.2程序的连接与装入4.3实存储器管理4.4虚拟存储管理4.5小结一、存储器的层次结构4.1概述存储系统的设计目标可归纳成3个问题：容量，速度，成本容量：需求无止境速度：能匹配处理器的速度成本：成本和其他部件相比应在合适范围之内存储器的层次结构容量、速度和成本之间的矛盾：三个目标不可能同时达到最优，要作权衡存取速度越快，每一个位（Bit）的价格越高追求大容量，就要降低存取速度追求高速度，就要降低容量存储器的层次结构解决方案：采用层次化的存储体系结构当沿着层次向下时每位的价格下降容量增大速度变慢Cache内存磁盘寄存器策略：较小、较贵的存储器由较大、较便宜的慢速存储器作为后援虚拟存储器降低较大、较便宜的慢速存储器的访问频率高速缓存存储器的层次结构Cache内存磁盘寄存器寄存器（Register）：在CPU内部,用来暂存数据、地址以及指令信息。在计算机的存储系统中它具有最快的访问速度。速度比主存快得多造价高，容量一般都很小内存：速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥高速缓存（cache）：处于CPU和物理内存之间，访问速度快于内存，但低于寄存器二、内存管理的目的4.1概述有效利用内存空间帕金森（parkinson）定律：内存有多大，程序就有多大考虑管理的开销：时间，空间应用程序不必考虑内存的大小三、内存管理的功能4.1概述记录内存的使用情况（是否空闲）进程所占内存空间的分配与回收当内存不足时，采取相应措施内存空间的共享与保护4.2程序的连接与装入一、程序连接的功能多个目标文件及库文件连接成1个完整的可执行文件。定位目标文件可能存在的一些外部符号浮动地址的重定位4.2程序的连接与装入二、程序连接的时机静态连接：静态的，只连接1次，多次运行装入时连接：装入后是静态的实际运行时连接：调用时动态连接4.1程序的连接与装入装入方式：（1）完全静态装入（2）静态重定位装入（3）动态重定位装入三、程序的装入方式程序能否直接在外存中执行？不行！每个程序在运行前，必须装入内存。不一定一次全部装入。程序的装入方式1.完全静态装入程序装入时不作任何修改。即装入内存的每个字节与其可执行文件完全相同。例如，DOS操作系统下的.com文件。程序的装入方式2.静态重定位装入程序装入时进行一次地址重定位，运行时不变。重定位：程序中的相对地址（从0开始）绝对地址程序的装入方式逻辑地址（相对地址）用户的程序经过汇编或编译连接后形成可执行代码，代码通常采用相对地址的形式，其首地址为0，指令中的地址都采用相对于首地址的偏移量机器是不能用逻辑地址在内存中读取信息的。物理地址（绝对地址）内存中存储单元的实际地址静态重定位装入MOVAX,[500H]．．．．．．00fffh模块AMOVBX,[600H]．．．．．．01fffh模块BMOVAX,[500H]．．．．．．02fffh．．．MOVBX,[1600H]MOVAX,[10500H]．．．．．．12fffh．．．MOVBX,[11600H]10000h连接装入程序的装入方式3.动态重定位装入真正执行到一条指令要访问某个内存地址时，才进行地址重定位。好处：程序可以在内存中移动。如何实现动态重定位？一般设置1个重定位寄存器，存放当前进程在内存的起始地址绝对地址=相对地址+重定位寄存器的值动态重定位装入1000123456MOVAX,[200]0100200300...MOVAX,[200]123456逻辑地址空间110012001300物理地址空间200地址+1000重定位寄存器...............4.3实存储器管理程序的大小不能超过可用内存空间的大小。一、连续分配为每个进程分配连续的内存空间。1.单一连续区分配内存中只存在1个用户程序。整个用户区为该程序独占。一般将内存划分为2个区：系统区：存放OS程序和数据用户区：存放用户程序和数据只能用于单用户、单任务OS。连续分配2.固定分区将内存的用户区预先划分为若干区域（分区）分区个数和每个分区的大小是固定的每个分区存放1个进程管理所需的数据结构：1个分区使用表（内存分配表），记录分区状态。固定分区存在的问题：(1)超过最大分区的程序无法装入；(2)存在内部碎片(Internalfragmentation)：由于程序长度小于分区，使得分区内部有空间浪费。区号分区大小起始地址状态18k32kUsed216k40kFree322k56kFree434k78kUsedOS进程A(6KB)进程B(28KB)032k40k56k78k分区使用表内部碎片连续分配3.可变分区（VariablePartition）或称动态分区。开始时只有1个空闲分区，随着进程的装入和退出，分区的个数和每个分区的大小、位置会动态变化。可变分区开始OSOSA进程A进入OSAB进程B进入OSABC进程C进入OSADC进程D进入OSAC进程B退出可变分区空闲分区表/空闲分区链记录空闲分区的起始地址和长度已分配分区表（1）分区管理所需的数据结构OSP1P2P30K15K38K48K68K80K110K120K空闲分区表已分配分区表始址长度状态15K23K未分配48K20K未分配80K30K未分配空空始址长度进程38K10KP168K12KP2110K10KP3空空OSP1P2P30K15K38K48K68K80K110K120K空闲分区表已分配分区表始址长度状态15K23K未分配48K20K未分配98K12K未分配空空始址长度进程38K10KP168K12KP2110K10KP380K5KP485K13KP5P485KP598K可变分区（2）分区分配算法①最先适配法（firstfit）空闲分区链（表）按地址递增的次序排列从头开始，选择第1个大小足够的分区②下次适配法（nextfit）从上次分配的分区的下一个开始，选择第1个大小足够的分区分区分配算法③最佳适配法（bestfit）空闲分区链（表）按大小递增的次序排列从头开始，选择第1个大小足够的分区④最差适配法（worstfit）空闲分区链（表）按大小递减的次序排列从头开始，选择第1个大小足够的分区可变分区（3）分区的回收将回收的分区插入到空闲分区链（表）的合适位置合并相邻的多个空闲分区考虑：上邻、下邻、上下相邻、上下不相邻存在一个问题：外部碎片（Externalfragmentation）经过一段时间的分配和回收后，内存中存在很多很小的空闲分区。它们每一个都很小，不足以满足分配要求，但其总和满足分配要求。这些空闲块被称为碎片，造成存储资源的浪费。可变分区（4）如何解决碎片问题？内存紧凑（compaction）：集中小碎片为大分区OSABC10KB30KB14KBOSABC54KB紧凑涉及到程序在内存中的移动，开销很大。可变分区为什么会产生大量碎片呢？根本原因是：连续分配。如果把程序分成几部分装入不同分区呢？引入离散分配：分页分段段页式（分段+分页）4.3实存储器管理二、分页（Paging，静态页式管理）1.基本原理（1）等分内存为物理块（或称页面，页框，pageframe）物理块编号为0，1，2，．．．。（2）进程的逻辑地址空间分页（page）页大小=物理块大小页编号为0，1，2，．．．。（3）内存分配原则：进程的1页可装入任一物理块分页进程的最后1页可能装不满，产生“页内碎片”。分页类似于固定分区，但不同之处在于：页比较小，一个进程可占据多页，且不要求连续。分页2.管理需要的数据结构OS为每个进程建立1个页表（PageTable）记录进程的页号和物理块号的对应关系...01234560123456进程的地址空间物理块号页号页表内存中的物理块分页3.地址变换逻辑地址→物理地址（1）页表寄存器（PageTableRegister,PTR）系统设置1个页表寄存器，存放当前进程的页表起始地址和长度每个进程的页表起始地址和长度平时放在其PCB中，调度时由OS放入PTR分页（2）页大小的选择页小：碎片小，但页表占用空间大页大：页表小，但页内碎片大通常，页的大小为2的整数次幂（3）进程的逻辑地址结构地址的高位部分为页号，低位部分为页内地址1201131页号p页内地址d（4）基本的地址变换p'页表地址越界页表长度Lp=LY页表起始地址b+页号p页内地址dp'd物理地址页表寄存器逻辑地址Nb[p]物理块号分页分页逻辑地址空间page0page1page2page3页表1437页号0123块号0123物理地址空间page0page2page1page345678【例】设逻辑地址是16位，页大小为1KB=1024B，即第0-9位是页内地址，第10-15位是页号。已知逻辑地址05DEH，即0000010111011110B，物理地址为：11DEH，即0001000111011110B因为页号=1，对应的物理块号=4物理地址=块号×页大小+页内地址基本的地址变换CPU要存取一个数据时，需要访问内存几次？2次。第1次：访问页表，找到该页对应的物理块号，将此块号与页内地址拼接形成物理地址；第2次：访问该物理地址，存取其中的指令或数据。分页（5）引入快表的地址变换快表，又称联想存储器(AssociativeMemory)：具有并行查找能力的特殊高速缓冲存储器（cache）。在80x86系统中叫做TLB（Translationlookasidebuffers）用途：保存当前进程的页表的子集（部分表项），比如最近访问过的页表项。当切换到新进程时，快表要刷新。目的：提高地址变换速度pp'快表p'页表地址越界页表长度Lp=LY页表起始地址b+页号p页内地址dp'd物理地址页表寄存器逻辑地址Nb[p]物理块号分页分页快表表项：页号：进程访问过的地址空间的页号块号：该页所对应的物理块号访问位：指示该页最近是否被访问过（0：没有被访问，1：访问过）状态位：该快表项是否被占用（0：空闲，1：占用）为了保证快表中的内容为现正运行程序的页表内容，在每个进程被选中时，由恢复现场程序把快表的所有状态位清0，或恢复已保存的快表内容。分页具有快表的地址变换过程：①当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可取得块号，生成物理地址。②当被访问的页不在快表中时，就要根据页号查内存中的页表，找到对应的物理块号，生成物理地址。同时将页号与块号填入快表中，若快表已满，则置换其中访问位为0的一项。说明：由于成本的关系，快表不能太大；引入快表的效果，取决于快表访问时的命中率(hitratio)。4.二级页表为什么要提出二级页表？页表可能占用相当大的内存空间，而且是连续的。分页1201131页号p页内地址d每个进程最多可达到220（1M）个页设每个页表项占4B，则页表占用的内存空间=4MB（1）基本原理将页表进行分页，页大小=物理块大小设置1个一级页表，多个二级页表一级页表：第i项记录第i号二级页表所在的物理块号二级页表：第i项记录第i页对应的物理块号系统设置１个页表寄存器，存放一级页表的起始地址和长度（2）进程的逻辑地址结构：二级页表2202131一级页号p1页内地址d11二级页号p212二级页表一级页表．．．二级页表．．．．．．．．．内存空间．．．（3）地址变换二级页表逻辑地址一级页号p1页内地址d二级页号p2一级页表起始地址页表寄存器p1'一级页表+p'二级页表+p'd物理地址说明：（1）二级页表并未减少页表所占的内存空间，但解决了页表的离散分配问题；（2）对于32位地址，采用二级页表是可以的。如果是64位地址呢？需要三级甚至更多级的页表。二级页表4.3实存储器管理三、分段（Segmentation，静态段式管理）1.基本原理（1）进程的逻辑地址空间分段（segment）：按程序自身的逻辑关系划分为若干个程序段每一个段是连续的各