切分、分页简介什么是分片？分段模型的前身：基地址加限制寄存器（动态重定位）分段管理分段思想分段地址翻译segment另一个优点：好支持共享虚拟地址翻译太慢？段的缺点：外部碎片太多分页管理分页思维分页地址翻译分页的缺点：页表太大怎么办？多级页表分段分页存储摘要：文章已收录我的仓库：Java学习笔记和免费书籍分享分段和分页介绍什么是分片？碎片分为内部碎片和外部碎片，两者都是指被浪费和不能使用的空间。内部碎片是指分配但未使用的地址空间。比如在64位空间，你只用了7个字节，但是因为内存对齐，你要给你分配8个字节的空间，这就产生了1个字节的内部碎片。外部碎片是指未分配和未使用的地址空间。比如你申请一个4字节的Int类型，然后申请一个8字节的long类型。对于内存对齐，4字节不能加载到8字节的类型中，导致4字节的外部碎片，如下图所示。内部碎片是操作系统不能使用的分配空间；externalfragments是未分配的，可以分配，但是空间太小（fragments的意思）无法加载到资源中，导致无法使用，但是Externalshards是可解的，可以将多个externalshards压缩成一个大的空闲空间，但这需要付出巨大的代价。段模型的前身：基地址加限制寄存器（动态重定位）。要理解分段和分页，首先要说说早期的虚拟内存模型。在经历了纯物理地址之后，科学家们期望解决这种内存模型难以统一的问题，于是虚拟内存技术诞生了，但让科学家们困惑的是如何将虚拟地址转换为物理地址。早期的科学家很容易想到把整个程序作为一个整体，给每个进程分配一个基址寄存器和一个界限寄存器。基地址寄存器存储实际物理地址处虚拟地址的起始点，而限制寄存器用来判断程序是否访问了非法地址。这样实际地址就很容易计算出来了：$$实际地址=虚拟地址+基地址$$但是这种方法还是把进程的整个地址空间加载到内存中。地址转换问题虽然解决了，但是还是会产生大量的内部碎片，如下图，进程栈区很小，所以栈区之间会产生内部碎片。从图中可以看出，如果我们把整个地址空间都放到物理内存中，那么栈和堆之间的空间并没有被进程使用，但仍然占据着实际的物理内存。因此，通过基址寄存器和限制寄存器实现的简单虚拟内存是一种浪费。此外，还要保证内存足够容纳进程的虚拟地址空间，但通常主存的成本比较昂贵，不如磁盘便宜。这种方法通常不支持大虚拟地址。如果剩余的物理内存不能提供一个连续的区域来放置整个地址空间，进程就无法运行。比如现在的32位进程空间通常是4GB，主存根本放不下几个进程。关键问题是：如何在堆栈和堆之间（可能）有大量可用空间的同时支持大虚拟地址空间？在前面的例子中，地址空间很小，所以这种浪费并不明显。但想象一个32位(4GB)地址空间。一个典型的程序只会使用几兆字节的内存，但它需要一次性将整个地址空间放入内存。我们需要更复杂的机制来利用物理内存并避免内部碎片，早期的科学家们提出了分段的想法。SegmentedManagementSegmentation分段实际上是基地址加限制概念的概括。在上面的例子中，我们为代码段、堆段、栈段维护了一个段基地址加上段限制寄存器，这样我们就不需要每次都强制加载整个进程空间，每个基地址寄存器存储的是物理地址处段的实际空间，仍然使用限制寄存器来保护地址空间。现在我们不需要分配程序未使用的空间（注意：我们仍然需要为堆保留更多的空间，除了堆段，其余段空间由编译器决定），其中大大提高了内存的利用率。另外，我们发现空间可以离散分配，即物理内存中的地址不需要连续，这样也可以大大提高物理地址的利用率。分段地址翻译分段地址翻译类似于基地址加边界的思想。在段的思想中，一个程序可能有多个段，操作系统通过段表来维护每个段的信息：段表的地址由操作系统维护。是的，段表项主要维护段长度和段基地址。段基地址是指段在物理内存中的起始地址。那么段中的虚拟地址就是段基地址+到实际地址的段偏移量。.段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）组成。例如系统按字节寻址，逻辑地址用3个二进制位表示，段号占16位，段内地址占16位，则其逻辑地址结构图如下。然后我们读取前16位作为段号，后16位作为段内的偏移量。操作系统通过计算addr=段号*段表项大小+段表地址来计算对应段表项的地址，查询段表项得到段基地址，通过计算得到物理地址段基址+段内偏移量。你可能已经发现，在虚拟地址中，每个段的起始地址是固定的，每个段的总大小也是固定的，其大小为：$$size=2^p字节，p=段的位数在内部地址$$如下图所示。注意它显示的是虚拟地址空间：另外，栈地址是反向增长的，所以段表中必须维护一个位来描述是否是栈段。分段的另一个优势：对共享的良好支持随着分段机制的不断改进，系统设计人员很快意识到，可以通过多一点硬件支持来实现新的效率提升。具体来说，为了节省内存，有时在地址空间之间共享某些内存段很有用。特别是，代码共享很普遍，该系统至今仍在使用。为了支持共享，需要一些额外的硬件支持，这就是保护位。基本上，每个段都添加了几个位来标识程序是否可以读取和写入该段，或者执行其中的代码。通过将一段代码标记为只读，相同的代码可以被多个进程共享，而不用担心破坏隔离。为什么页面不工作？纯页面管理，一个页面比较大，页面中没有任何逻辑信息，所以放什么代码都有可能，所以还要确定用哪些代码来分享，增加了成本。所以我们常说分段管理符合用户逻辑，有利于保护和分享。虚拟地址转换太慢？我们每次翻译一个虚拟地址，都需要在段表中查找段表项，相当于多义地址访问，太慢了！解决方案是为计算机配备一个小型硬件设备，将虚拟地址直接映射到物理地址，而无需访问段表。该设备称为转换后备缓冲器(TLB)，有时也称为快速表。快速表是一个小型高速缓存。现代操作系统在分段和分页中都使用这种软件技术。我们会在地址转换专用的文中解释快速表的地址转换。段的缺点：外部碎片过多分段可以避免内部碎片（不是绝对的），但由于分段是离散的，在主存中寻找并插入空闲槽，问题是物理内存很快被许多空闲槽填满空间，使得分配新段或扩展现有段变得困难-大量外部碎片。比如4kb的空间被加载到3kb的segment中，得到的1kb的空间是不能被加载到任何segment中的。产生碎片的主要原因是段使用的大小是不确定的。当然，如前所述，可以通过紧凑的方式将外部碎片组合成更大的自由空间，但这需要很大的成本，操作系统也很难维护。在这种情况下，分页管理应运而生。分页管理分页的思想是对于分段管理，一段时间后主存会被大大小小的外部碎片覆盖，操作系统难以维护。分段的思想是将内存空间分成不同长度的片段。由于长度不固定，难免会产生外部分片。将整个程序一起加载的方法虽然不会产生外部碎片，但是会产生巨大的内部碎片。我们需要更细粒度的划分，以减少对于内部碎片的产生，解决这个问题的方法是将空间划分成更小的、固定长度的碎片，这就是分页管理。分页管理将程序资源划分为固定大小的页面，并将每个虚拟页面映射到一个物理页面。由于每个页面的大小都是固定的，因此操作系统可以巧妙地分配物理内存空间以避免外部碎片。比如一个pagesize是4kb，主存是40kb，操作系统稍加管理就可以保证10个page随时可以整齐的加载。需要注意的是，页面在物理内存中并不是连续存在的，不需要为进程未使用的页面分配内存。这样，我们就可以解决分割带来的大量外部碎片的问题。小，在使用的页面中只会产生少量的内存碎片，这也是可以接受的。目前，分页是一个很好的解决方案。分页地址转换和分页一样，分页地址转换也需要基地址+页偏移来完成。在分段时，段表用于存储段基地址，而在分页时，页表用于存储页基地址，页基地址表示页在实际内存中的起始地址，那么实际address:$$addr=pagebaseaddress+pageoffset$$页表由操作系统维护，操作系统知道页表的开始是未知的，页表项的大小是固定的。在32位地址空间中，通常为8个字节。这64位不仅存储了页基地址，还存储了其他一些重要的数据，如：有效位、可读位、脏位等。虚拟地址由页表号+页偏移组成，类似到段中的虚拟地址。我们来做个简单的计算，得到页表号在32位程序中占用的位数。其中一个页表的大小通常为4kb，那么：$$虚拟地址的总空间大小=2^{32}=4GB\\页表项数=\frac{4GB}{4kb}=2^{20}\\4kb=2^{{12}}byte$$为了能够表示220个页表项，我们必须分配20位地址，剩下的12位表示页内的偏移量，即下图中p=12，n=32，我们通常称虚拟页号为VPN，页偏移量为VPO，如下图所示：为什么取VPO直接代表页偏移？这也很好理解，因为：页偏移=虚拟地址-页起始地址，而页起始地址实际上是固定的，即当VPO位全为0时，就是对应页的起始地址。当虚拟地址-页起始地址是VPO表示的值。现在操作系统取出虚拟地址，我们设置为vAddr，我们可以通过以下步骤将其翻译成物理地址：获取VPN和VPO，即VPN=vAddr&0XFFFFF000；VPO=vAddr&0X00000FFF;获取页表项的地址，$页表项地址=页表起始地址+VPN×页表大小$；从页表项中取出页基地址，即实际物理起始地址PPN（注意这里只有20位，需要右移12位才是真正的地址）；PPN与VPO相连，即$realaddress=(PPN<<12)|VPO$看个例子，还是假设3位地址的操作系统，第一位表示一级页表，第二位表示二级页表，第三位表示页偏移量：$$\begin{cases}000&first-level页表的页码为0，二级页表的页码为0，偏移地址为0\\001&第一层的页码-级页表为0，二级页表的页号为0，偏移地址为1\\010&一级页表的页号为0，二级页表的页号-一级页表为1，offset的地址为0\\011&一级页表的页号为0，二级页表的页号为1，offset为1\的地址\100&一级页表的页号为1，二级页表的页号为0，偏移量为0的地址\\101&一级页表的页号为1，并且二级页表的页号为0，偏移量为1\\110的地址&一级页表的页号为1，二级页表的页号为1，偏移量为1的地址0\\111&一级页表的页码为1,二级页表的页码页码为1偏移量为1的地址\\\end{cases}$$有一级页table，里面有两项，第一级页表项中至少有一个有效位，如果确实有效那么下一级页表的起始地址也被保存。我们仍然假设进程未使用地址000;001;010;011。现在假设进程访问地址010，MMU（地址转换单元）取出一级页号0，访问一级页表偏移量为0的页表项，此时操作系统发现use设置为0（未使用），则不需要访问二级页表，立即返回，通知进程地址非法，抛出异常或终止进程。现在一级页表中页号0对应的二级页表就不需要加载了。我们只需要一级页表的两个表项和页码为1.的一级页表的两个二级表项，一共四个页表表项。在这个例子中，我们需要的页表条目没有改变。这是因为我们假设的页表太小了。在实践中，一旦一级页表使用率不设置为0，就可以不加载数千个二级页表条目，从而大大减小了页表大小。即使在我们的例子中，一级页表项实际上比真正的页表项要小，仍然可以减少页表占用的内存。实际上，多级页表中的每一级页表都可以设置为正好适合一页，这样就不会产生内部碎片或外部碎片。例如Corei7中使用了4级页表，每级页表有9位，每级占9位，每级页表项为8字节，则每级页表的大小为$2^{9}×8byte=4kb$，恰好是一个页面的大小。需要指出的是，多级页表是有代价的。当TLB未命中时，需要多次从内存中加载，才能从页表中获取正确的地址转换信息（一次是针对页目录，一次是针对PTE本身）。因此，多级表是时空权衡的一个小例子。我们想要更小的桌子（并得到了），但不是免费的。虽然在常见情况下性能明显相同（TLB命中），但由于表较小，TLB未命中会导致更高的成本。另一个明显的缺点是复杂性。无论是硬件还是操作系统处理页表查找（在TLB未命中时），这样做肯定比简单的线性页表查找更复杂。通常我们愿意增加复杂性以提高性能或减少开销。在多级表的情况下，我们使页表查找更加复杂，以节省宝贵的内存。应该想到段页存储。在添加一层抽象的时候，我们不仅可以添加页面，还可以添加段。多年前，Multics的创造者（尤其是JackDennis）在构建Multics虚拟内存系统时，偶然发现了这样的想法。具体来说，Dennis想到了结合分页和分段来减少页表的内存开销。现在，我们还是把应用程序分成段，但是我们对每个段进行分页管理。结合分段的思想，就很容易理解为什么这种思想可以减少内存开销了：因为分段只保存使用过的资源，然后在每个页用到的地方分页每个分段！例如，假设程序分为代码段、堆段、栈段和4GB的虚拟空间。程序只用了15kb，其中代码段7kb，栈段4kb，堆段4kb。实际物理空间占用如图Display:我们可以确保所有页面都被使用，只有每个段的最后一页可能会产生一点内部碎片！再想想段页地址转换，这就需要我们把段和分页结合起来。此时，段描述符（段表项）中不再存储段基地址和段长度，而是存储该段对应的页表地址。段长页存储页表的长度：下图中地址向上增长：那么此时的虚拟地址也应该表示为段号+页号+偏移量：我们执行如下算法：1）根据段号找到段描述符2）检查该段的页表是否在内存中，如果在，找到其location；如果不在，则产生段错误。如果访问违反了段的保护要求，则发送越界错误（陷阱）。3）检查请求的虚拟页的页表项，如果该页不在内存中，则产生缺页中断，如果在内存中，则从页表项中取该页在内存中的起始地址。4)将页起始地址加上偏移量，得到内存中要访问的字的地址段页管理也使得操作系统很容易管理一些受保护或共享的段。sharedinthepaging.另外可以发现这种管理也省去了分页管理。内部分片可能很少（一个段末尾只有一个内部分片，可以忽略不计），同时又像分页一样，不包含任何外部分片，易于管理。这是一个聪明的主意。总结：段管理：优点：消除内部碎片，提高物理内存的利用率；将应用程序划分为逻辑段，人们可以编写不同类型的代码，并且可以轻松地共享或保护。缺点：会产生大量的外部碎片，使得操作系统难以分配空闲空间。分页管理：优点：消除外部碎片，提高物理内存的利用率，方便操作系统对空闲空间的管理。缺点：内部碎片还是会出现，虽然每个页碎片不超过页大小；页表太大，占用空间大，可以用多级页表的思想解决。分段页面管理：优点：同时具有分段和页面的所有优点。缺点：需要更多的硬件支持；当TLB未命中时，访问内存需要更多时间。
