操作系统实验报告Lab2物理内存管理(含challenge)

Lab2实验报告练习0:填写已有实验利用Understand中的Compare完成此练习。练习1:实现firstfit连续物理内存分配算法大体思路：物理内存页管理器顺着双向链表进行搜索空闲内存区域，直到找到一个足够大的空闲区域，这是一种速度很快的算法，因为它尽可能少地搜索链表。如果空闲区域的大小和申请分配的大小正好一样，则把这个空闲区域分配出去，成功返回;否则将该空闲区分为两部分，一部分区域与申请分配的大小相等，把它分配出去，剩下的一部分区域形成新的空闲区。其释放内存的设计思路很简单，只需把这块区域重新放回双向链表中即可。实现目标： 重写default_init_memmap()，default_alloc_pages()，default_free_pages()函数。具体细节：default_init_memmap()函数这个函数是用来初始化空闲页链表的。主要有两个步骤：初始化每一个空闲页，计算空闲页的总数。注意：1.使用头插法是因为地址是从低地址向高地址增长。 2.p->flags=0语句已经将PG_reserved标志位置零。default_alloc_pages()函数这个函数是用来分配空闲页的。主要步骤如下：寻找足够大的空闲块如果找到了，重新设置标志位从空闲链表中删除此页判断空闲块大小是否合适如果不合适，分割页块如果合适则不进行操作计算剩余空闲页个数返回分配的页块地址备注：在参考答案中，我认为有些语句是冗余的，如图：验证：在第二次重置标志位前后，分别输出标志位的值，发现，flags并没有发生变化。然后将这两句话注释，编译后运行，依旧可以得到正确答案。所以我认为这两句话是没有必要的。default_free_pages()函数这个函数的作用是释放已经使用完的页，把他们合并到freelist中。具体步骤如下：在freelist中查找合适的位置以供插入改变被释放页的标志位，以及头部的计数器尝试在freelist中向高地址或低地址合并注意：在合并后，需要更新头部的页块大小的值即property。练习2:实现寻找虚拟地址对应的表项大体思路：尝试获取页表的地址，如果获取不到就新建一个页表。练习3:释放某虚地址所在的页并取消对应二级页表的映射大体思路：判断此页被引用的次数，如果仅仅被引用一次，则这个页也可以被释放。否则，只能释放页表入口。简析slub分配器slub分配器是通过slab分配器改进得来的，它减去了slab中一些复杂的数据结构。为了清楚的了解slub，首先应当了解slab分配器的相关原理。slab分配器简介slab分配器主要结构下图给出了slab结构的高层组织结构。在最高层是cache_chain，这是一个slab缓存的链接列表。这对于best-fit算法非常有用，可以用来查找最适合所需要的分配大小的缓存（遍历列表）。cache_chain的每个元素都是一个kmem_cache结构的引用（称为一个cache）。它定义了一个要管理的给定大小的对象池。超级麻烦的维护体系slab分配器直接工作在伙伴系统之上。每种缓冲区由多个slab组成，每个slab就是一组连续的物理内存页框，被划分成了固定数目的对象。根据对象大小的不同，缺省情况下一个slab最多可以由1024个物理内存页框构成。出于对齐等其它方面的要求，slab中分配给对象的内存可能大于用户要求的对象实际大小，这会造成一定的内存浪费。kmem_cache对象是以cache_chain为队列头的一个双向循环队列。每个slab都需要一个类型为structslab的描述符数据结构管理其状态，同时还需要一个kmem_bufctl_t（被定义为无符号整数）的结构数组来管理空闲对象。每个slab对象会根据状态的不同在三个队列中转换。SLAB分配器允许对象在一级硬件高速缓存中对齐同时使用着色（color）策略，使得同一缓冲区内不同slab中相同编号的对象的地址相互错开为了支持多处理器同时分配对象，缓冲区为每个处理器维护一个本地缓存。slub分配器SLUB分配器特点是简化设计理念，同时保留SLAB分配器的基本思想：每个缓冲区由多个小的slab组成，每个slab包含固定数目的对象。简化了kmem_cacheslab中有35个参数，而slub中有17个。slab等相关的管理数据结构个改变slab没有额外的空闲对象队列。slab也没有额外的描述结构，因为SLUB分配器在代表物理页框的page结构中加入freelist，inuse和slab的union字段，所以slab的第一个物理页框的page结构就可以描述自己。slub分配器的申请函数slab_alloc()查找正确的object——_slab_alloc()函数这个函数很长，因为它需要对很多情况进行处理：判断当前object是否和当前处理器匹配当前page中是否还有slab当前slab中是否还有pageempty_slab中是否还有slabPartial_slab中是否还有slab当出现异常的时候，解决的办法是找到可用的object，具体的方法是由下至上逐层查找是否存在空闲的结构。查找方向如图所示：具体代码判断有没有可用slab和处理器的匹配问题 load_freelist:返回可用的objectunlock_out:解锁（前面的代码对page加了锁）。 another_slab：在当前freelist中寻找另外一个slab new_slab：在Partialslab队列中选取一个slab。如果队列也没有可用slab了，则重新申请一个