第三节首次适应算法的分析

1、,深刻理解计算机 上机编程：分配器 首次适应算法、最佳适应算法、下一次适应算法,首次适应算法分析,#include void *malloc(size_t,size); malloc函数返回一个指针，指向大小为至少size字节的存储器块。 如果malloc遇到问题，那么返回NULL。 注意：与教材中的malloc函数不同。,free函数释放已经分配的malloc块,#include void free(void *ptr) Ptr参数必须指向一个从malloc获得的已经分配块的起始位置。,malloc和free分配和释放块,malloc(4*sizeof(int),malloc(5*sizeo

2、f(int),free 第二次分配的5个int,malloc(2*sizeof(int),malloc算法分析,首次适应算法：从头开始搜索空闲链表，选择第一个合适的空闲块。 将大的空闲块保留在链表的后面。链表起始处留下小的空闲块的碎片，增加了对较大块的搜索时间。 首次适应算法速度很快，因为它尽可能少地搜索链表结点。 下一次适应算法和首次适应算法很相似，是不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。 若上一次在一个空闲块中发现足够的空间，那么这一次也能在这个剩余块中发现所需空间。 比首次适应算法快，利用率却低。 最佳适应算法检查数组的每一个空闲块，选择适合所需请求大小的最

3、小空闲块。,内存管理：使用coremap,coremap按照map的起始地址排序。,首次适应算法,存储管理器对coremap进行搜索，直到找到一个足够大的空闲区。 若空闲区大小和要分配的空间大小正好一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。,教材p77的例题,例题1. coremap: 进程申请空间大小是15 （1）搜索coremap，找到第一个长度=15的空闲区,20,10,coremap2,50,30,coremap1,100,20,coremap0,0,coremapCMAPSIZ,20,10,coremap0,m_size=3015，首次找到一个足够大的

4、空闲区,50,30,coremap1,m_size=1015,（2）空闲区的分配 新的coremap数组,50,30,coremap1,分配15个块出去，则： m_size=30-15=15， m_addr=50+15=65。,20,10,coremap2,65,15,coremap1,100,20,coremap0,0,coremapCMAPSIZ-1,教材p78的例题,例题2. coremap: 进程申请空间大小是30 （1）搜索coremap，找到第一个长度=15的空闲区,20,10,coremap2,50,30,coremap1,100,20,coremap0,0,coremapCMA

5、PSIZ,20,10,coremap0,m_size=30=30，首次找到一个足够大的空闲区,50,30,coremap1,m_size=1015,例题2,（2）空闲区的分配 若m_size=0,则应删除这个元素，coremap数组剩下的元素向前移动一个位置。,50,30,coremap1,分配30个块出去，则： m_size=30-30=0， m_addr=50+30=80,20,10,100,20,coremap1,coremap0,0,coremapCMAPSIZ-2,80,0,coremap1有变化,malloc()函数,malloc(mp,size) Struct map *mp;

6、register int a; /a是malloc返回的分配区的起始块号 register struct map *bp; /bp是工作块,malloc(),for(bp=mp;bp-m_size;bp+) /搜索coremap if(bp-m_size=size) /找到第一个空白区m_size=size，则分配。 a=bp-m_addr; /返回值为分配区域的起始块号 bp-m_addr=+size; /空白区的起始地址变化 if(bp-m_size=-size)=0) /若此map区域全部分配， 则不能再认为是coremap数组中的元素 do bp+; /从bp+开始元素向前移动一个位置

7、 (bp-1)-m_addr=bp-m_addr;,malloc(),while(bp-1)-m_size=bp-m_size); /最后一个元素的长度为0，结束移动 return(a); /malloc()成功，则返回分配区的起始地址a return(0); ,所找到的空白区起始地址的改变,所分配空白区的起始地址变化的原因： return(a)，而且a=m_addr 若此空白区的起始地址不变化，则与a相同，引起混淆。 所以，m_addr=m_addr+m_size,2.mfree()回收算法现代操作系统P105,回收时有四种情况： 1.aa与前空白区(bp-1)相邻 (bp-1).m_siz

8、e=+ size 2.aa与前、后空白区相邻 (bp-1).m_size=+ bp.m_size coremap元素向前移动一个位置 3.aa与后空白区相邻 bp.m_addr=aa bp.m_size=+ size 4.aa不与任何空白区相邻 bp.m_addr=aa; bp.m_size=size; coremap的元素向后移动一个位置，bp+,mfree(),mfree(mp,size,aa) Struct map *mp; register struct map *bp; register int t; register int a;,mfree(),a=aa; for(bp=mp;b

9、p-m_addrm_size!=0;bp+); if(bpmp /map(aa,size)使上一个和下一个空白区连起,mfree(),while(bp-m_size) /第二种情况coremap元素向前移动一个位置 bp+; (bp-1)-m_addr=bp-m_addr; (bp-1)-m_size=bp-m_size; ,mfree(),else/第三种情况map(aa,size)与下一个空白区相邻 if(a+size=bp-m_addr ,mfree(),else if(size) do /不能与上一个下一个空白块合并 t=bp-m_addr; /coremap增加一个节点 bp-m_a

10、ddr=a; / coremap数组的元素向后移动一个位置 a=t; t=bp-m_size; bp-m_size=size; bp+; while(size=t); ,教材p79的例题,例题3. coremap: 回收区大小size=5，起始地址aa=40 （1）搜索coremap，找到比回收区起始地址aa大的第一个空闲区。,20,10,coremap2,50,30,coremap1,100,20,coremap0,0,coremapCMAPSIZ,20,10,coremap0,m_addr=5040，找到比回收区aa高的空闲区，bp=&coremap1,50,30,coremap1,m_a

11、ddr=2040,（2）回收区的回收 新的coremap数组,40,5,coremap1,20+1040 40+550 第四种情况,20,10,coremap2,40,5,coremap1,50,30,coremap0,0,coremapCMAPSIZ-1,coremap2,100,20,coremap数组的元素从bp开始，向后移动一位。,教材p79的例题,例题3. coremap: 回收区大小size=10，起始地址aa=40 （1）搜索coremap，找到比回收区起始地址aa大的第一个空闲区。,20,10,coremap2,50,30,coremap1,100,20,coremap0,0,

12、coremapCMAPSIZ,20,10,coremap0,m_addr=5040，找到比回收区aa高的空闲区，bp=&coremap1,50,30,coremap1,m_addr=2040,例题4,（2）回收区的回收 新的coremap数组,40,10,coremap1,20+1040 40+10=50 第三种情况,20,10,coremap2,40,40,coremap1,100,20,coremap0,0,coremapCMAPSIZ-1,40,40,coremap1,m_addr=40 m_size=10+30=40,coremap数组元素不必改变位置。,下一次适应算法,最佳适应算法

13、最差适应算法 现代操作系统P105,Linux虚拟存储器系统,Linux系统为每一个进程维护一个单独的任务结构task_struct PID 指向用户栈的地址 可执行目标文件名字 程序计数器 因此，task_struct与UNIX的PCB块类似,Linux系统进程的地址空间,mm_struct,描述进程的地址空间 成员 pgd:第一级页表的基地址 mmap：VM_area_structs(区域结构)的链表 vm_area_structs描述进程地址空间中的一个区域,vm_area_structs,一个具体的vm_area_structs包含的成员 vm_start:区域的起始地址 vm_end:区域的脚地址 vm_prot:区域的读写权限