网站开发公司团队优势,自己可以自己做公司的网站吗,徐州招聘网站哪个好,南阳网(网站).2017-2018-1 20155227 《信息安全系统设计基础》第十三周学习总结 找出全书你认为最重要的一章#xff0c;深入重新学习一下#xff0c;要求#xff08;期末占10分#xff09;#xff1a;
完成这一章所有习题详细总结本章要点给你的结对学习搭档讲解你的总结并获取反馈我选… 2017-2018-1 20155227 《信息安全系统设计基础》第十三周学习总结 找出全书你认为最重要的一章深入重新学习一下要求期末占10分
完成这一章所有习题详细总结本章要点给你的结对学习搭档讲解你的总结并获取反馈我选择教材第九章的内容来深入学习一方面虚拟内存这一部分内容本身就十分重要另一方面我在操作系统课上对这一部分的知识理解的很浅在十一周自学教材这一部分内容时也因为知识点太多而没有学得很深入正好借此机会来重新学习这一章的内容加深理解。 教材学习内容总结 第九章 虚拟存储器 为了更加有效地管理存储器且少出错现代系统提供了对主存的抽象概念叫做虚拟存储器(VM。 虚拟存储器是硬件异常硬件地址翻译主存磁盘文件和内核软件的完美交互。为每个进程提供一个大的一致的和 私有的地址空间。提供了3个重要能力。 将主存看成磁盘地址空间的高速缓存。 只保留了活动区域并根据需要在磁盘和主存间来回传送数据高效使用主存。为每个进程提供一致的地址空间 简化存储器管理保护了每个进程的地址空间不被其他进程破坏。虚拟内存在幕后工作程序员为什么要理解它呢 虚拟存储器是中心的。遍布在计算机系统所有层次硬件异常汇编器连接器加载器共享对象文件和进程中扮演重要角色。 虚拟存储器是强大的。 可以创建和销毁存储器片(chunk)将存储器片映射到磁盘文件的某个部分。其他进程共享存储器。例子 能读写存储器位置来修改磁盘文件内容。
加载文件到存储器不需要显式的拷贝。虚拟存储器是危险的 引用变量间接引用指正调用malloc动态分配程序就会和虚拟存储器交互。如果使用不当将遇到复杂危险的与存储器有关的错误。例子 一个带有错误指针的程序可以立即崩溃于段错误或者保护错误。运行完成却不产生正确结果。9.1 物理与虚拟寻址 物理地址(Physical Address,PA):计算机系统的主存被组织为M个连续的字节大小的单元组成的数组。每个字节的地址叫物理地址.CPU访问存储器的最自然的方式使用物理地址这种方式称为物理寻址。 早期的PC数字信号处理器嵌入式微控制器以及Cray超级计算机使用物理寻址。现代处理器使用的是虚拟寻址(virtual addressing)的寻址形式。 CPU通过生成一个虚拟地址(Virtual address,VA)来访问主存。 将虚拟地址转换为物理地址叫做地址翻译(address translation)。地址翻译也需要CPU硬件和操作系统之间的紧密结合。 CPU芯片上有叫做存储器管理单元(Memory Management Unit,MMU)的专用硬件。 利用存储在主存中的查询表来动态翻译虚拟地址。查询表由操作系统管理。9.2 地址空间 地址空间(address space)是一个非负整数地址的有序集合。 如果地址空间中整数是连续的我们说它是线性地址空间(linear address space)。 我们总是假设使用线性地址空间。在一个带虚拟存储器的系统中CPU从一个有N2^n个地址的地址空间中生成虚拟地址这个地址空间称为虚拟地址空间(virtual address space)。一个地址空间大小是由表示最大地址所需要的位数来描述的。 如N2^n个地址的虚拟地址空间叫做n位地址空间。现在操作系统支持32位或64位。一个系统还有物理地址空间,它与系统中物理存储器的M2^m(假设为2的幂)个字节相对应。地址空间的概念很重要因为它区分了数据对象(字节)和 它们的属性(地址)。 每个字节(数据对象)一般有多个 独立的地址(属性)。每个地址都选自不同的地址空间。 字节有一个在虚拟地址空间的虚拟地址。还有一个在物理地址空间的物理地址。两个地址都能访问到这个字节。9.3 虚拟存储器作为缓存的工具 虚拟存储器(VM) 被组织为一个存放在磁盘上的N个连续字节大小的单元组成的数组。 每个字节都有一个唯一的虚拟地址这个虚拟地址作为到数组的索引。磁盘上数组的内容被缓存到主存中。 同存储器层次结构其他缓存一样磁盘上的数据被分割成块。 这些块作为磁盘和主存之间的传输单元。虚拟页(Virtual Page,VP)就是这个块 物理存储器被分割为物理页,大小也为P字节 也被称为页帧(page frame)。任何时候虚拟页的集合都被分为3个不相交的子集。 未分配的: VM系统还未分配(或者创建)的页。未分配的块没有任何数据与之相关联。 不占用磁盘空间通过malloc来分配缓存的: 当前缓存在物理存储器的已分配页。未缓存的: 没有缓存在物理页面存储器中的已分配页。9.3.1 DRAM缓存的组织结构 DRAM表示虚拟存储器系统的缓存在主存中缓存虚拟页,有两个特点。 DRAM缓存不命中处罚十分严重。 因为磁盘比DRAM慢100000多倍。访问一字节开销 从一个磁盘的一个扇区读取第一个字节的时间开销要比从该扇区中读连续的字节慢大约100000倍DRAM缓存的组织结构由这种巨大的不命中开销驱动。因此有以下特点。 虚拟页往往很大。 4KB~2MBDRAM缓存是全相联 任何虚拟页都能放在任何物理页中。原因在于大的不命中惩罚更精密的替换算法 替换错了虚拟页的惩罚很高。DRAM缓存总是写回 因为对磁盘的访问时间很长而不用直写9.3.2 页表 判断命中和替换由多种软硬件联合提供。 操作系统软件MMU中的地址翻译硬件和页表(page table)。 页表是存放在物理存储器的数据结构。 页表将虚拟页映射到物理页。地址翻译硬件将虚拟地址转换为物理地址都会读取页表。操作系统负责维护页表的内容以及磁盘及DRAM之间来回传送页。 页表就是一个页表条目(Page Table Entry,PTE)的数组. 虚拟地址空间中每个页在页表的固定偏移量处都有一个PTE.每个PTE有一个有效位和n位地址字段。 有效位表明虚拟页是否被缓存。
如果有效位存在那么地址字段指向对应的物理存储器。
如果有效位不存在。 地址字段要么为NULL,要么指向虚拟页在磁盘所在的位置。9.3.3 页命中 一个页命中的过程。一个虚拟地址转换为物理地址的过程。9.3.4 缺页 DRAM缓存不命中称为缺页。 处理过程如下 读取虚拟地址所指向的PT。读取PTE有效位发现未被缓存触发缺页异常。调用缺页异常处理程序 选择牺牲页。如果牺牲页发生了改变将其拷贝回磁盘(因为是写回)需要读取的页代替了牺牲页的位置。结果牺牲也不被缓存需要读取的页被缓存。中断结束重新执行最开始的指令。在DRAM中读取成功。 块被称为页。
磁盘和DRAM之间传送页的活动叫做交换(swapping)或者页面调度(paging)。
有不命中发生时才换入页面这种策略叫做按需页面调度(demand paging)。 9.3.5 分配页面 比如某个页面所指向地址为NULL将这个地址指向磁盘某处那么这就叫分配页面。 此时虚拟页从未分配状态 变为 未缓存。 9.4 虚拟存储器作为存储器的管理工具 操作系统为每个进程提供一个独立的页表。 因此VM简化了链接和加载,代码和数据共享,以及应用程序的存储器分配。 简化链接 独立的空间地址意味着每个进程的存储器映像使用相同的格式。 文本节总是从0x08048000(32位)处或0x400000(64位)处开始。然后是数据bss节,栈。一致性极大简化了链接器的设计和实现。简化加载 加载器可以从不实际拷贝任何数据从磁盘到存储器。基本都是虚拟存储系统完成。简化共享 独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间的一致共享机制 操作相同的操作系统内核代码C标准库的printf.因此操作系统需要将不同进程的适当的虚拟页映射到相同的物理页面。 多个进程共享这部分代码的一个拷贝。而不是每个进程都要加载单独的内核和C标准库的拷贝。简化存储器分配 即虚拟页连续(虚拟页还是单独的)物理页可以不连续。使得分配更加容易。 9.5 虚拟存储器作为存储器保护的工具 任何现代操作系统必须为操作系统提供手段来控制对存储器系统的访问。 不应该允许用户进程修改它的只读文本段。不允许它读或修改任何内核的代码和数据结构不允许读写其他进程的私有存储器。不允许修改共享的虚拟页除非所有共享者显示允许这么做(通过调用明确的进程间通信 SUP: 是否只有在内核模式下才能访问?READ: 读权限。WRITE 写权限。如果指令违反了许可条件触发一般保护性异常然后交给异常处理程序Shell一般会报告为段错误(segmentaion fault)。 9.6 地址翻译 形式上来说地址翻译是一个N元素的虚拟地址空间(VAS)中的元素和一个M元素的物理地址空间PAS)元素之间的映射, 以下展示了MMU(Memory Management Unit,存储器管理单元)如何利用页表实现这样的功能 页表基址寄存器(Page Table Base Register,PTBR)指向当前页表。n位的虚拟地址包含两个部分 一个p位的虚拟页面偏移(Virtual Page Offset,VPO)一个n-p位的虚拟页号(Virtual Page Number,VPN)页面条目 (PTE)中物理页号(PPN)和虚拟地址中的VPO串联起啦即是物理地址 PPO和VPO是相同的记VPN,PPN都是块都是首地址而已所以需要偏移地址PPO,VPO 图(a)展示页面命中,CPU硬件执行过程: 第一步处理器生成虚拟地址把它传送给MMU。第二步: MMU生成PTE地址(PTEA)并从高速缓存/主存请求中得到它。第三步: 高速缓存/主存向MMU返回PTE。第四步: MMU构造物理地址(PA)并把它传送给高速缓存/主存。第五步: 高速缓存/主存返回所请求的数据字给处理器。页面命中完全由硬件处理与之不同的是处理缺页需要 硬件和操作系统内核协作完成。 第一到三步: 与命中时的一样第四步:PTE有效位是零所以MMU触发异常传递CPU中的控制到操作系统内核中的 缺页异常处理程序。第五步:缺页异常处理程序确定出物理存储页中的牺牲页如果这个页面已经被修改则把它换出到磁盘。第六步:缺页异常处理程序调入新的页面并更新存储器中的PTE。第七部:缺页异常处理程序返回到原来的进程再次执行导致缺页的指令之后就是页面命中一样的步骤。9.6.1 结合高速缓存和虚拟存储器 在任何使用虚拟存储器又使用SRAM高速缓存的系统中都存在应该使用虚拟地址 还是 使用 物理地址 来访问SRAM高速缓存的问题。 大多数系统是选择物理寻址。 使用物理寻址,多个进程同时在高速缓存中有存储块和共享来自相同虚拟页面的块成为简单的事。 而且还无需处理保护问题因为 访问权限的检查在地址翻译中(PTE)的一部分。以下是一个例子(将PTE进行高速缓存)。 9.6.2 利用TLB加速地址翻译 每次CPU产生一个虚拟地址MMU就必须查阅一个PTE以便将虚拟地址翻译为 物理地址。 在最糟糕的情况下会从内存中取数据代价是几十 到几百个周期如果PTE碰巧缓存在L1中那么开销就下降到一到两个周期许多系统都试图消除这样的开销他们在MMU中包含了一个关于PTE的小缓存称为翻译后备缓冲器(Translation Lookaside Buffer,TLB)。 TLB是一个小的虚拟寻址的缓存。 每一行都保存着一个由单个PTE组成的块。TLB通常用于高度的相连性 - 如图所示 用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果TLB有T2^t个组 那么TLB索引(TLBI)是由VPN的t个最低位组成。(对应于VPO)TLB标记(TLBT)是由VPN中剩余位组成(对应于VPN)下图展示了TLB命中步骤 关键点:所有的地址翻译步骤都是在芯片上的MMU中执行的因此非常快 TLB命中 第一步:CPU产生虚拟地址。第二步和第三部:MMU从TLB取出对应的PTE。第四步:MMU将这个虚拟地址翻译成一个物理地址发送到高速缓存/主存第五步:高速缓存/主存所请求的数据字返回给CPU当TLB不命中的时候MMU必须从L1缓存或内存中取出相应的PTE,并进行类似缺页处理过程。9.6.3 多级页表 如果我们有一个32位地址空间4KB大小的页面(p2^12)和一个4B的PTE即使应用所引用的只是虚拟地址空间中很小的一部分也总是需要一个4MB的页表驻留在存储器中。 所以多级页表的诞生用于解决在很少使用时有一个很大的页表常驻于内存。 用来压缩页表的常用方式是使用层次结构的页表。 以下用上图的两层作为例子。 总共有9KB个页面PTE为4个字节。 前2KB个页面分配给代码和数据。接下来6KB个页面未分配再接下来1023个页面也未分配接下一个页面分配给用户栈一级页表中的每个PTE负责映射虚拟地址空间中一个4MB大小的片(chunk). 每一个片都是由1024个连续的页面组成。4MB1024个页面*PTE大小4字节。如果片i中每个页面都没有分配那么一级PTE i就为空。 例如图中的PTE 2~PTE 7但是如果片i中有一个被分配了那么PTE i就不能为空。这种方法从两个方面减少了存储器要求。 如果一级页表PTE为空那么相应的二级页表就根本不会存在。 一种巨大的潜在节约大部分时候内存都是未分配的。只有一级页表才需要总是在主存中。 虚拟存储器系统可以在需要时创建页面调入调出二级页面减少主存压力。 k级页表层次结构的地址翻译。 虚拟地址被分为k个VPN和一个VPO。每个VPN i都是i-1级页表到i级页表的索引。PPN存于k级页表。PPO依旧与VPO相同。此时TLB能发挥作用因为层次更细更利于缓存。使得多级页表的地址翻译不比单级页表慢很多。 9.6.4 综合:端到端的地址翻译 一个在有一个TLB和L1 d-cache的小系统上。作出如下假设: 存储器都是按字节寻址的。存储器访问是针对一字节的字的。虚拟地址是14位长(n14)物理地址是12位长(m12)页面大小是64字节(P2^6)TLB是四路组相连的总共有16个条目L1 d-cache是物理寻址高速缓存直接映射(E1)的行大小为4字节而总共有16个组。存储结构快照 TLB: TLB利用VPN的位进行缓存。页表: 这个页表是一个单级设计。一个有256个但是这里只列出16个。高速缓存:直接映射的缓存通过物理地址的字段来寻址。 因为是直接映射通过索引就能直接找到。且E1。直接能判定是否命中。9.7 案例研究: Intel Core i7/Linux 存储器系统 处理器包(processor package) 四个核 层次结构的TLB 虚拟寻址四路组相连Linux 一页4kb层次结构的数据和指令高速缓存。 物理寻址L1L2 八路组相连L3 十六路组相连块大小64字节快速的点到点链接。 基于Intel QuickPath技术为了让核与其他核和外部I/O桥直接通信L3高速缓存DDR3存储器控制器9.7.1 Core i7地址翻译 上图完整总结了Core i7地址翻译过程从虚拟地址到找到数据传入CPU。 Core i7采用四级页表层次结构。 CR3 控制寄存器指向第一级页表(L1)的起始位置 CR3也是每个进程上下文的一部分。上下文切换的时候CR3也要被重置。一级二级三级页表PTE的格式: P1时 地址字段包含了一个40位物理页号(PPN)指向适当的页表开始处。强加了一个要求要求物理页4kb对齐。 因为PPO为12位 4kbPPO的大小就跟物理页的大小有关。四级页表的PTE格式: PTE有三个权限位控制对页的访问 R/W位确定页的内容是可以 读写还是 只读。U/S位确定用户模式是否能够访问从而保护操作系统内核代码不被用户程序访问。XD (禁止执行) 位是在64位系统引入禁止某些存储器页取指令。 这是一个重要的新特性限制只能执行只读文本段降低缓冲区溢出的风险。当MMU翻译虚拟地址时还会更新两个内核缺页处理程序会用到的位。 A位 每次访问一个页MMU都会设置A位称为引用位(reference bit).可以利用这个引用位来实现它的页替换算法。D位 每次对一个页进行了写 就会设置D位又称脏位(dirty bit).脏位告诉内核在拷贝替换页前是否要写回。内核通过调用一条特殊的内核模式指令来清除引用位或脏位。四级页表如何将VPN翻译成物理地址 每个VPN被用作页表的偏移量。CR3寄存器包含L1页的物理地址9.7.2 Linux 虚拟存储系统 内核虚拟存储器 内核虚拟存储器包含内核中的代码和数据。 内核虚拟存储器的某些区域被映射到所有进程共享的物理页面 如:内核代码全局数据结构。Linux也将一组连续的虚拟页面(大小等同于系统DRAM总量)映射到相应的一组物理页面。内核虚拟存储器包含每个进程不相同的数据。 页表内核在进程上下文中时使用的栈等等。Linux 虚拟存储器区域 Linux将虚拟存储器组织成一些区域(也叫做段)的集合。 一个区域就是已经存在着的(已分配的) 虚拟存储器的连续片这些片/页已某种形式相关联。 代码段数据段堆共享库段用户栈。所有存在的虚拟页都保存在某个区域。 区域的概念很重要允许虚拟地址空间有间隙。一个进程中虚拟存储器的内核数据结构。 内核为系统中每个进程维护了一个单独的任务结构。任务结构中的元素包含或指向内核运行该进程所需要的全部信息。 task_struct mm_struct 描述了虚拟存储器的当前状态。pgd 指向第一级页表的基址。当进程运行时内核将pgd存放在CR3控制寄存器mmap vm_area_structs(区域结构)每个vm_area_structs都描述了当前虚拟地址空间的一个区域(area).vm_start:指向这个区域的起始处。vm_end:指向这个区域的结束处。vm_port:描述这个区域内包含的所有页的读写许可权限。vm_flags:描述这个区域页面是否与其他进程共享还是私有。vm_next: 指向链表的下一个区域。Linux 缺页异常处理 MMU在试图翻译虚拟地址A时触发缺页 。这个异常导致控制转移到缺页处理程序执行一下步骤。 虚拟地址A是合法的吗? A在某个区域结构定义的区域内吗?解决方法: 缺页处理程序 搜索区域结构链表。把A和每个区域的vm_start 和vm_end 做比较。 通过某种树 的数据结构算法查找如果不合法 触发段错误 。试图访问的存储器是否合法? 即是否有读写执行这个页面的权限?如果不合法触发保护异常终止进程。 •一切正常的话 选择牺牲页替换重新执行指令9.8 存储器映射 存储器映射: Linux通过将一个虚拟存储器区域与一个磁盘上的对象关联起来以初始化这个虚拟存储器区域的内容这个过程叫做存储器映射。 虚拟存储器区域可以映射到以下两种类型文件。 Unix文件系统中的普通文件:一个区域可以映射到一个普通磁盘文件的连续部分。 例如一个可执行文件。文件区(section)被分成页大小的片每一片包含一个虚拟页面的初始化内容。仅仅是初始化虚拟页面此时还并未进入物理存储器。 直到CPU第一次引用这个页面。匿名文件 : 一个区域可以映射到一个匿名文件。 匿名文件由内核创建包含的全是二进制零。CPU第一次引用这样区域(匿名文件)的虚拟页面时。 将存储器中牺牲页面全部用二进制零覆盖。并将虚拟页面标记为驻留在存储器中。注意: 实际上虚拟页面并没有跟存储器进行数据传送。又叫请求二进制零的页(demand-zero page)。 交换文件交换空间。(win下叫做paging file) 一旦一个虚拟页面被初始化了它就在一个由内核维护的专门的交换文件(swap file)之间换来换去。交换文件也叫交换空间或者交换区域。需要意识到在任何时刻交换空间都限制着当前运行着的进程分配的虚拟页面总数。9.8.1 再看共享对象 共享对象的由来 许多进程有同样的只读文本区域。 printf运行Uinx shell的tcsh如果每个进程都加载进内存一次极其浪费。存储器映射提供一种机制来共享对象。一个对象被映射到虚拟存储器的一个区域一定属于以下两种。 共有对象 一个进程将一个共有对象映射到它的虚拟地址空间的一个区域。 进程对这个区域的写操作对于那些也把这个共享对象映射它的虚拟存储器的进程是可见的。这些变化也会反映到磁盘上的原始对象。映射到的虚拟存储器那个区域叫做共享区域。私有对象 对一个映射到私有对象的区域做出的改变对于其他进程不可见.并且进行的写操作不会反映到磁盘上。映射到的虚拟存储器那个区域叫做私有区域。9.8.1.1 共享对象 进程1将共享对象映射到虚拟存储器中然后虚拟存储器将这一段找一块物理存储器存储。当进程2也要引用同样的共享对象时。 内核迅速判定进程1已经映射了这个对象。使进程2的虚拟存储器直接指向了那一块进程1指向的物理存储器。即使对象被映射到多个共享区域物理存储器依旧只有一个共享对象的拷贝。 大大解决了物理存储器内存。9.8.1.2 私有对象 私有对象使用一种叫做写时拷贝(conpy-on-write)的巧妙技术。 私有对象开始生命周期的方式基本与共享对象一样。 即使对象被多个引用在物理内存都只保留一个拷贝。对于每个映射私有对象的进程相应私有区域的页表条目都被标记为只读。 并且区域结构(vm_area_structs)被标记为私有的写时拷贝。过程:只要有进程试图写私有区域内的某个页面那么这个写操作触发保护异常。 故障处理程序会在物理存储器中创建被修改页面的一个新拷贝。更新页表条目(PTE)指向这个新的拷贝恢复被修改页面的可写权限。故障处理程序返回CPU重新执行这个写操作。通过延迟私有对象中的拷贝直到最后可能的时刻写时拷贝充分使用了稀缺的物理存储器9.8.2 再看fork函数 了解fork函数如何创建一个带有自己独立虚拟地址空间的新进程。 当fork函数被当前进程调用时。 内核为新进程创建内核数据结构并分配给它唯一一个PID。为了给新进程创建虚拟存储器。 创建了当前进程的mm_struct,区域结构和页表的原样拷贝。将两个进程的每个页面都标记为只读。并给两个区域进程的每个区域结构都标记为私有的写时拷贝。注意:并没有对物理存储器进行拷贝哦利用的是私有对象的写时拷贝技术。当fork函数在新进程返回时。 新进程现在的虚拟存储器刚好和调用fork时存在的虚拟存储器相同。当两个进程中任一个需要被写时触发写时拷贝机制。9.8.3 再看execve函数 理解execve函数实际上如何加载和运行程序。 假设运行在当前的进程中的程序执行了如下的调用: Execve(a.out,NULL,NULL);execve函数在当前进程加载并执行目标文件a.out中的程序用a.out代替当前程序。 加载并运行需要以下几个步骤。 删除已存在的用户区域。 删除当前进程虚拟地址的用户部分中已存在的区域结构。映射私有区域。 为新程序的文本数据bss和栈区域创建新的区域结构。 所有新的区域结构都是私有的写时拷贝的。文本和数据区域被映射到a.out文件中的文件和数据区。bss区域是请求二进制零映射到匿名文件。 大小包含在a.out中堆栈区域也是请求二进制零。映射共享区域 a.out程序与共享对象链接。 这些对象都是动态链接到这个程序。然后映射到用户虚拟地址的共享区域。设置程序计数器(PC) execve最后一件事设置PC指向文本区域的入口点。 9.8.4 使用mmap函数的用户级存储器映射 Unix进程可以使用mmap函数来创建新的虚拟存储器区域并将对象映射到这些区域中。 #include unistd.h
#include sys/mman.hvoid *mmap(void *start,size_t length,int prot,int flags,int fd,off_t offset);返回:若成功时则为指向映射区域的指正若出错则为MAP_FAILED(-1).参数解释: fd,start,length,offset: mmap函数要求内核创建一个新的虚拟存储器区域最好是从地址start开始的一个区域并将文件描述符fd指定的对象的一个连续的片chunk映射到这个新的区域。 连续对象片大小为length字节从据文件开始处偏移量为offset字节的地方开始。statr地址仅仅是个暗示 一般被定义为NULL让内核自己安排。prot 参数prot包含描述新映射的虚拟存储器区域的访问权限位。(对应区域结构中的vm_prot位) PROT_EXEC:这个区域内的页面由可以被CPU执行的指令组成。PROT_READ:这个区域内的页面可读。 -PROT_WRITE:这个区域内的页面可写。PROT_NONE: 这个区域内的页面不能被访问。flag 参数flag由描述被映射对象类型的位组成。 MAP_ANON标记位:映射对象是一个匿名对象。MAP_PRIVATE标记位:被映射对象是一个私有的写时拷贝的对象。MAP_SHARED标记位:被映射对象是一个共享对象。9.9 动态存储器分配 虽然可以使用更低级的mmap和munmap函数来创建和删除虚拟存储器的区域。 但是C程序员还是觉得用动态存储器分配器(dynamic memory allocator)更方便。 动态存储器分配器维护着一个进程的虚拟存储区域称为堆(heap)。 系统之间细节不同但是不失通用型。假设 堆是一个请求二进制零的区域。紧接着未初始化的bss区域并向上生长(向更高的地址)。对于每个进程内核维护一个变量brk(break)指向堆顶。分配器将堆视为一组不同大小的块block的集合来维护。 每个块就是一个连续的虚拟存储器片即页面大小。要么是已分配要么是空闲。 已分配 已分配的块显式地保留供应用程序使用。已分配的块保持已分配状态直到它被释放。 这种释放要么是应用程序显示执行。要么是存储器分配器自身隐式执行(JAVA)。空闲 空闲块可用于分配。空闲块保持空闲直到显式地被应用分配。分配器有两种基本分格。 都要求应用显式分配不同之处在于那个实体负责释放已分配的块显式分配器(explict allocator) 要求应用程序显式地释放C语言中提供一种叫malloc程序显示分配器 malloc和freeC new和delete隐式分配器(implicit allocator)要求分配器检测一个已分配块何时不再被程序所使用那么就释放这个块。隐式分配器又叫做垃圾收集器(garbage collector).自动释放未使用的已分配的块的过程叫做垃圾收集(garbage collection). -Lisp,ML以及Java等依赖这种分配器。9.9.1 malloc和free 函数 malloc C标准库提供了一个称为malloc程序包的显示分配器。 #includestdlib.h
void* malloc(size_t size);返回:成功则为指针失败为NULLmalloc 返回一个指针指向大小为至少size字节的存储器块。 不一定是size字节很有可能是4或8的倍数 这个块会为可能包含在这个块内的任何数据对象类型做对齐。Unix系统用8字节对齐。malloc不初始化它返回的存储器。 如果想要初始化可以用calloc函数。 calloc是malloc一个包装函数。想要改变已分配块大小。 用realloch函数如果malloc遇到问题。 返回NULL 并设置errno。动态存储分配器可以通过使用mmap和munmap函数显示分配和释放堆存储器。 或者可以使用sbrk函数。#includeunistd.hvoid *sbrk(intptr_t incr);返回:若成功则为旧的brk指针若出错则为-1并设置errno为ENOMEML.free 程序通过调用free函数来释放已分配的堆块。 #includestdlib.hvoid free(void *ptr);返回:无 ptr参数必须指向一个从malloc,calloc,realloc获得的已分配块的起始位置。 如果不是那么free行为未定义。更糟糕的是free没有返回值不知道是否错了。 9.9.2 为什么要使用动态存储器分配 程序使用动态存储器分配的最重要原因是: 经常直到程序实际运行时它们才知道某些数据结构的大小。9.9.3 分配器的要求和目标 显式分配器有如下约束条件 处理任意请求序列。立即响应请求。 不允许为提高性能重新排列或缓冲请求。只使用堆。对齐块。 上文的8字节。不修改已分配的块。目标 吞吐率最大化和存储器使用率最大化。这两个性能要求通常是相互冲突的。 目标1:最大化吞吐率 假定n个分配和释放请求的某种序列R1,R2,R3.....Rn 吞吐率 :每个单位时间完成的请求数。通过使分配和释放请求的平均时间最小化 来最大化吞吐率目标2:最大化存储器利用率 设计优秀的分配算法。需要增加分配和释放请求的时间。评估使用堆的效率最有效的标准是峰值利用率(peak utilization)吞吐率和存储器利用率是相互牵制的分配器设计的一个有趣的挑战就是在两者之间找到一个平衡。9.9.4 碎片 造成堆利用率很低的主要原因是一种称为碎片(fragmentation)的现象。 碎片:虽然有未使用的存储器但不能满足分配要求时的现象。 内部碎片:已分配块比有效载荷(实际所需要的)大时发生。 比如:上文中只要5个字(有效载荷)却给了6个字(已分配块)那一个多的就是碎片.任何时刻内部碎片的数量取决于以前请求的模式和分配器的实现方式。 可计算的可量化的。外部碎片:当空闲存储器合计起来足够满足一个分配请求但是没有一个单独的空闲块足够大可以处理这个请求发生的。 外部碎片的量化十分困难。 不仅取决于以前请求的模式和分配器的实现方式还要知道将来请求的模式。9.9.5 实现问题 一个实际的分配器要在吞吐率和利用率把握平衡必须考虑一下几个问题。 空闲块组织: 如何记录空闲块? ( 9.9.6)放置: 如何选择一个合适的空闲快来放置一个新分配的块? (9.9.7)分割: 将一个新分配的块放入某个空闲块后如何处理这个空闲快中的剩余部分?(9.9.8)9.9.6 隐式空闲链表 将堆组织为一个连续的已分配块和空闲块的序列。 这种结构就叫做隐式空闲链表 隐式 : 为什么叫隐式链表。 因为不是通过指针(next)来链接起来。而是通过头部的长度隐含地链接起来。终止头部(类似与普通链表的NULL) 已分配大小为零的块优缺点: 优点:简单缺点1:任何操作的开销都与已分配块和空闲块的总数呈线性关系O(N). 放置分配的块。对空闲链表的搜索。缺点2: 即使申请一个字节也会分配2个字的块。空间浪费。9.9.7 放置已分配的块 有以下几种搜索放置策略 首次适配 从头开始搜索空闲链表选择第一个合适的空闲块。下一次适配 和首次适配很类似但不是从头开始而是从上一次查询的地方开始。最佳适配 检查每个空闲块找一个满足条件的最小的空闲块(贪心)。优缺点 首次适配 优点 往往将大的空闲块保留在链表后面。缺点 小的空闲块往往在前面增大了对较大快的搜索时间。下一次适配 优点 速度块。缺点 存储器利用率低最佳适配 优点 利用率高缺点 要完整搜索链表速度慢。9.9.8 分割空闲块 两种策略 占用所有空闲块 缺点:产生更多的内部碎片(但是如果内部碎片很少可以接受)优点:能使得 空闲块已分配块的数量减少 能加快搜索速度。有的外部碎片(几个字节很有可能是外部碎片)可能根本放置不了东西但是却占用了搜索时间还不如当内部碎片算了放置策略趋向于产生好的匹配中使用。 即占用所有空闲块内部碎片也很少。分割空闲块 缺点:更多的空闲块和已分配块搜索速度降低。优点:空间利用率更高。9.9.9 获取额外的堆存储器 如果分配器不能为请求块找到合适的空闲块将发生什么? 合并相邻的空闲块。sbrk函数 在最大化合并还不行的情况。向内核请求额外的堆存储器。 并将其转为大的空闲块将块插入链表。9.9.10 合并空闲块 假碎片: 因为释放使得某些时候会出现相邻的空闲块。 单独的放不下请求(碎片)合并却可以(假性)所以叫假碎片。何时合并? 立即合并 定义:块被释放时合并所有相邻的块。缺点:对于某些请求模式会产生抖动。推迟合并 定义: 一个稍晚的时候再合并。 比如:上文中的找不到合适空闲块的时候。9.10 GC_垃圾收集 垃圾收集器(garbage collector)是一种动态存储分配器。 垃圾: 它自动释放不再需要的已分配块这些块称为垃圾(garbage).垃圾收集(garbage collection) :自动回收堆存储的过程叫做垃圾收集。 应用显式分配堆块但从不显式释放堆块。垃圾收集器定期识别垃圾快并调用相应地free将这些快放回空闲链表。垃圾收集可以追溯到John McCarthy在20世纪60年代早期在MIT开发的Lisp系统。 它是Java,ML,Perl和Mathematic等现代语言系统的一个重要部分。有关文献描述了大量的垃圾收集方法数量令人吃惊。我们讨论局限于McCarthy自创的MarkSweep(标记清除)算法。 它可以建立已存在的malloc包的基础上为C和C提供垃圾收集。9.11 C程序中常见的与存储器有关的错误 9.11.1 间接引用坏指正 scanf(%d,val)
scanf(%d,val);最好的情况 : 以异常中止。有可能覆盖某个合法的读/写区域造成奇怪的困惑的结果。9.11.2 读未初始化的存储器 堆存储器并不会初始化。 正确做法 使用calloc.显示y[i]0;9.11.3 允许栈缓冲区溢出 程序不检查输入串的大小就写入栈中的目标缓冲区 那么就有缓冲区溢出错误(buffer overflow bug)。gets()容易引起这样的错误 - 用fgets()限制大小。9.11.4 假设指针和它们所指向对象是相同大小 有的系统里int和 int *都是四字节有的则不同。 9.11.5 越界 9.11.6 引用指针而不是它所指向的对象 对指针的优先级用错。 9.11.7 误解指针的运算 忘记了指针的算术操作是以它们指向的对象的大小为单位来进行的这种大小不一定是字节。 9.11.8 引用不存在的变量 返回一个指针指向栈里面一个变量的地址。但是这个变量在返回的时候已经从栈里被弹出。 地址是正确的指向了栈。但是却没有指向想指向的变量。9.11.9 引用空闲堆块的数据 引用了某个已经free掉的块。在C多态中经常容易犯这个错误。 9.11.10 引起存储器泄露 即是没有回收垃圾。导致内存中垃圾越来越多。 只有重启程序才能释放。对于守护进程和服务器这样的程序存储器泄露是十分严重的事。 因为一般情况不能随便重启。9.12 小结 虚拟存储器是对主存的一个抽象。 使用一种叫虚拟寻址的间接形式来引用主存。 处理器产生虚拟地址通过一种地址翻译硬件来转换为物理地址。 通过使用页表来完成翻译。 又涉及到各级缓存的应用。页表的内容由操作系统提供虚拟存储器提供三个功能 它在主存中自动缓存最近使用的存放在磁盘上的虚拟地址空间内容。 虚拟存储器缓存中的块叫做页简化了存储器管理 进而简化了链接进程间共享数据。进程的存储器分配以及程序加载。每条页表条目里添加保护位从而简化了存储器保护。地址翻译的过程必须和系统中所有的硬件缓存的操作集合。 大多数条目位于L1高速缓存中。 但是又通过一个TLB的页表条目的片上高速缓存L1。现代系统通过将虚拟存储器片和磁盘上的文件片关联起来以初始化虚拟存储器片这个过程叫做存储器映射。 存储器映射为共享数据创建新的进程 以及加载数据提供一种高效的机制。可以用mmap 手工维护虚拟地址空间区域。 大多数程序依赖于动态存储器分配例:malloc 管理虚拟地址空间一个称为堆的区域分配器两种类型。 显示分配器 CC隐式分配器 JAVAGC是通过不断递归访问指针来标记已分配块在需要的时刻进行Sweep。 CC无法辨认指针导致无法实现完全的GC。 只有保守的GC。需要配合平衡树进行查找p所指向的块第九章课后家庭作业 书上课后练习题都有答案就不在博客里详细写了。 9.11 A.虚拟地址0x027c 13121110987654321000001001111100B.地址翻译 参数值VPN0x09TLB索引0x01TLB标记0x02TLB命中No缺页NoPPN0x17C.物理地址格式 11109876543210010111111100D.物理地址引用 参数值字节偏移0x0缓存索引0xF缓存标记0x17缓存命中No返回缓存字节-9.12 A.虚拟地址0x03a9 13121110987654321000001110101001B.地址翻译 参数值VPN0x0ETLB索引0x02TLB标记0x03TLB命中No缺页NoPPN0x11C.物理地址格式 11109876543210010001101001D.物理地址引用 参数值字节偏移0x1缓存索引0xA缓存标记0x11缓存命中No返回缓存字节-9.13 A.虚拟地址0x0040 13121110987654321000000001000000B.地址翻译 参数值VPN0x01TLB索引0x01TLB标记0x00TLB命中No缺页YESPPN- 9.14 #include sys/types.h
#include sys/stat.h
#include fcntl.h
#include unistd.h
#include sys/mman.h
int main()
{int fd;char *start;fd open(hello.txt, O_RDWR, 0); //打开文件start mmap(NULL, 1, PROT_WRITE, MAP_SHARED, fd, 0);close(fd); if(start MAP_FAILED) return -1;//判断是否映射成功(*start) J;munmap(start, 1);return 0;
} 9.15 请求块大小块头部malloc(3)80x9malloc(11)160x11malloc(20)240x19malloc(21)320x219.16 对齐要求 | 已分配块|空闲块|最小块大小| ---|---|---|---| 单字 | 头部和脚部|头部和脚部|16字节| 单字 | 头部但是没有脚部|头部和脚部|16字节| 双字 | 头部和脚部|头部和脚部|16字节| 双字 | 头部但是没有脚部|头部和脚部|16字节| 空闲块至少是16字节。已分配块不需要pred和succ所以这八个字节可以装数据加上头和脚就是16字节而且满足单字双字对齐。 9.17 我们需要修改find_fit函数之前的版本在practise习题中写过书后有答案。 代码可以参考9.18。 为此需要先定义一个全局的cur_point指针表示上次搜索之后指向哪个块有效载荷首地址。 static void *find_fit(size_t asize)
{void *bp cur_point;do{if( !GET_ALLOC(HDRP(bp)) (asize GET_SIZE(HDRP(bp))) ) return cur_point bp;bp (GET_SIZE(HDRP(bp)) 0) ? heap_listp : NEXT_BLKP(bp); }while(bp ! cur_point);return NULL;
} 另外需要释放cur_point指向的指针时它可能和前面的空闲块合并我们应该将cur_point指向前一个空闲块首地址。在coalesce()函数中需要做如下修改 else if (!prev_alloc next_alloc) { /* Case 3 */size GET_SIZE(HDRP(PREV_BLKP(bp)));PUT(FTRP(bp), PACK(size, 0));PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));if(cur_point bp) cur_point PREV_BLKP(bp);bp PREV_BLKP(bp);
}
else { /* Case 4 */size GET_SIZE(HDRP(PREV_BLKP(bp))) GET_SIZE(FTRP(NEXT_BLKP(bp)));PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));if(cur_point bp) cur_point PREV_BLKP(bp);bp PREV_BLKP(bp);
} 9.18 需要考虑四个问题 初始化的时候序言块和结尾块是怎么样的。序言块八字节8|0x11。 结尾块四字节0|0x11.为堆申请更多空间的时候sbrk如何更改结尾块记录最后一个块的alloc。 结尾块向后延伸申请的空间并将刚多出的空间作为一个空闲块。设置为size|(alloc1)。再合并该空闲块。这里如何合并呢需要判断最后一块是否已分配可通过epilogue来判断。某个空闲块匹配的时候如何设置头和下一块的头。我们基于以下假设某个空闲块匹配上一个和下一个一定不是空闲块否则可以合并。 所以头部就设置为asize|0x011)。 如果要分割则下一块的头部设置为size-asize|0x010不用合并因为再下一块肯定是已经分配。释放某个块时如何合并。检查头部alloc_prev 上一块是否分配 检查下一个块的头部alloc_next 下一个块是否分配。 再根据那四种情况分别设置。 最后如果下一块已分配则需要将下一块头部设置为(原头部(~0x010))。另外在mm_malloc中分配多大的块也要发生相应的变化因为现在最小块大小可以是DSIZE而不是2*DSIZE。 代码已上传至码云9.19 1) a; 对于伙伴系统如果要申请大小为33的空间那么需要分配64个空间。如果申请大小为65的空间那么块大小就需要128所以最多可能有约50%的空间被浪费。b中最佳适配要搜索所有空间所以肯定比首次适配要慢一些。c边界标记主要功能是释放一个块时能立即和前后空闲块合并。如果空闲块不按顺序排列的话其实也能够和前一个或者后一个空闲块进行合并但如果要和前后一起合并可能会有些困难那需要搜索前后块在空闲链表中的位置并且删除一个再进行合并。可以参考P576LIFO方法。d其实任何分配器都可能有外部碎片只要剩余的空闲块大小和足够但是单个都不够就会产生外部碎片。2) d; 块大小递增那么最佳适配法找到的块和首次适配找到的块是同一个因为最佳适配总是想找一个刚好大于请求块大小的空闲块。a块大小递减首次适配很容易找到所以分配性能会很高。b最佳适配方法无论怎样都要搜索所有的链表除非维护成块大小递增的链表。c是匹配的最小的。3) c; 保守的意思就是所有可能被引用的堆都会被标记int像指针所以可能认为它表示的地址是正在被引用的实际上它只是个int。9.20 不会…… 教材学习中的问题及解决 在深入学习之前我和同伴是带着这些疑问的学习之后通过讨论对这些问题有了一点理解。 问题1Linux虚拟地址空间如何分布问题1解决 Linux 使用虚拟地址空间大大增加了进程的寻址空间由低地址到高地址分别为 1、只读段该部分空间只能读不可写(包括代码段、rodata 段(C常量字符串和#define定义的常量) )2、数据段保存全局变量、静态变量的空间3、堆 就是平时所说的动态内存 malloc/new 大部分都来源于此。其中堆顶的位置可通过函数 brk 和 sbrk 进行动态调整。4、文件映射区域 如动态库、共享内存等映射物理空间的内存一般是 mmap 函数所分配的虚拟地址空间。5、栈用于维护函数调用的上下文空间一般为 8M可通过 ulimit –s 查看。6、内核虚拟空间用户代码不可见的内存区域由内核管理(页表就存放在内核虚拟空间)。问题264位系统拥有2^64的地址空间吗问题2解决 事实上 64 位系统的虚拟地址空间划分发生了改变 1、地址空间大小不是2^32也不是2^64而一般是2^48。因为并不需要 2^64 这么大的寻址空间过大空间只会导致资源的浪费。64位Linux一般使用48位来表示虚拟地址空间40位表示物理地址这可通过 /proc/cpuinfo来查看2、其中0x0000000000000000~0x00007fffffffffff表示用户空间 0xFFFF800000000000~ 0xFFFFFFFFFFFFFFFF表示内核空间共提供 256TB(2^48) 的寻址空间。这两个区间的特点是第 47 位与 48~63 位相同若这些位为 0 表示用户空间否则表示内核空间。3、用户空间由低地址到高地址仍然是只读段、数据段、堆、文件映射区域和栈问题3如何查看进程发生缺页中断的次数问题3解决 用ps -o majflt,minflt -C program命令查看。 majflt代表major fault中文名叫大错误minflt代表minor fault中文名叫小错误。 这两个数值表示一个进程自启动以来所发生的缺页中断的次数。问题4发成缺页中断后执行了那些操作问题4解决 当一个进程发生缺页中断的时候进程会陷入内核态执行以下操作 1、检查要访问的虚拟地址是否合法2、查找/分配一个物理页3、填充物理页内容读取磁盘或者直接置0或者啥也不干4、建立映射关系虚拟地址到物理地址重新执行发生缺页中断的那条指令问题5堆内碎片不能直接释放导致疑似“内存泄露”问题为什么 malloc不全部使用 mmap 来实现呢(mmap分配的内存可以会通过 munmap 进行 free 实现真正释放)而是仅仅对于大于 128k的大块内存才使用 mmap 问题5解决 进程向 OS 申请和释放地址空间的接口 sbrk/mmap/munmap 都是系统调用频繁调用系统调用都比较消耗系统资源的。并且 mmap 申请的内存被 munmap 后重新申请会产生更多的缺页中断。例如使用 mmap 分配 1M 空间第一次调用产生了大量缺页中断 (1M/4K 次) 当munmap 后再次分配 1M 空间会再次产生大量缺页中断。缺页中断是内核行为会导致内核态CPU消耗较大。另外如果使用 mmap 分配小内存会导致地址空间的分片更多内核的管理负担更大。 同时堆是一个连续空间并且堆内碎片由于没有归还 OS 如果可重用碎片再次访问该内存很可能不需产生任何系统调用和缺页中断这将大大降低 CPU 的消耗。 因此 glibc 的 malloc 实现中充分考虑了 sbrk和 mmap 行为上的差异及优缺点默认分配大块内存 (128k) 才使用 mmap 获得地址空间也可通过 mallopt(M_MMAP_THRESHOLD, SIZE)来修改这个临界值。 上周考试错题总结 无 结对及互评点评模板 博客中值得学习的或问题 xxxxxx...代码中值得学习的或问题 xxxxxx...其他本周结对学习情况 -[20155318](http://www.cnblogs.com/lxy1997/)
- 结对照片
- 结对学习内容- 教材第九章内容- 跟着同伴回顾了第十二章的内容- ... 其他感悟、思考等可选 通过这一章的学习进一步加深了对虚拟存储器的了解。 代码托管 statistics.sh脚本的运行结果截图 学习进度条 代码行数新增/累积博客量新增/累积学习时间新增/累积重要成长目标5000行30篇400小时第一周133/1331/18/8第三周159/2921/310/18第五周121/4131/510/28第七周835/30052/710/38第八周1702/47771/810/48第九周1664/64413/1110/58第十一周300/67413/1410/68第十三周743/74842/1610/78尝试一下记录「计划学习时间」和「实际学习时间」到期末看看能不能改进自己的计划能力。这个工作学习中很重要也很有用。 耗时估计的公式 YXX/N YX-X/N训练次数多了X、Y就接近了。 参考软件工程软件的估计为什么这么难软件工程 估计方法 计划学习时间:15小时实际学习时间:10小时改进情况(有空多看看现代软件工程 课件 软件工程师能力自我评价表) 参考资料 《深入理解计算机系统V3》学习指导...转载于:https://www.cnblogs.com/guyanlin/p/8033903.html
