第三节：首次适应算法的分析2015.4.14.ppt

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

2、loc(4*sizeof(int),malloc(5*sizeof(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

4、,coremap0,m_size=3015，首次找到一个足够大的空闲区,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,corem

5、ap1,100,20,coremap0,0,coremapCMAPSIZ,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()函数,

6、malloc(mp,size) Struct map *mp; 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

7、数组中的元素 do bp+; /从bp+开始元素向前移动一个位置 (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,回收时有四种情况

8、： 1.aa与前空白区(bp-1)相邻 (bp-1).m_size=+ size 2.aa与前、后空白区相邻 (bp-1).m_size=+ bp.m_size coremap元素向前移动一个位置,修改coremap 3.aa与后空白区相邻 bp.m_addr=aa bp.m_size=+ size 4.aa不与任何空白区相邻 bp.m_addr=aa; bp.m_size=size; coremap的元素向后移动一个位置,修改coremap。,H,I,T,H,I,T,H,I,T,H,I,T,(1),(2),(3),(4),mfree(),mfree(mp,size,aa) Struct ma

9、p *mp; register struct map *bp; register int t; register int a;,mfree(),a=aa; for(bp=mp;bp-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)与下一

10、个空白区相邻 if(a+size=bp-m_addr /长度增加 ,mfree(),else if(size) do /回收区不能与上一个和下一个空白区合并 t=bp-m_addr; /coremap构成新表目， bp-m_addr=a; /起始地址 / coremap数组的元素向后移动一个位置 a=t; t=bp-m_size; bp-m_size=size;/长度 bp+; while(size=t); ,(1)a保留下一个表目的起始地址， (2)size保留下一个表目的长度。 (3)t作为交换变量,教材p79的例题,例题3. coremap: 回收区大小size=5，起始地址aa=40

11、（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_addr=2040,（2）回收区的回收 新的coremap数组,40,5,coremap1,20+1040 40+550 第四种情况,20,10,coremap2,40,5,coremap1,50,30,coremap0,0,coremapCMAPSIZ-1,c

12、oremap2,100,20,coremap数组的元素从bp开始，向后移动一位。,教材p79的例题,例题3. coremap: 回收区大小size=10，起始地址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_addr=2040,例题4,（2）回收区的回收 新的coremap数组,40,10,co

13、remap1,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数组元素不必改变位置。,下一次适应算法,下次适应算法 每次从上一次结束时，开始搜索coremap数组。 最佳适应算法 每次选最大的空白区分配 最差适应算法 每次选与申请长度size最近似的空白区 现代操作系统P105,Linux系统的内存管理方法,1.进程的管理方法 现代操作系统p430 每个进程分配3GB的虚拟

14、地址空间 2.内存的管理方法 设置一个页描述符数组mem_map，表示内存中所有的页框。 区域描述符，描述每个区域的所有组成页框的利用情况。进程地址空间按照区域分配。,1.Linux虚拟存储器系统,Linux进程地址空间的管理方法：虚拟存储器。 Linux系统为每一个进程维护一个单独的任务结构task_struct PID 指向用户栈的地址 可执行目标文件名字 程序计数器 因此，task_struct与UNIX的PCB块类似,Linux系统进程的地址空间,mm_struct,描述进程的地址空间 成员 pgd:第一级页表的基地址 mmap：VM_area_structs(区域结构)的链表 vm_

15、area_structs描述进程地址空间中的一个区域 mm_struct相当于APR页表。然而mm_struct的页面并不是连续的块组成，而是链表构成。,vm_area_structs：区域描述符,一个具体的vm_area_structs包含的成员 vm_start:区域的起始地址 vm_end:区域的脚地址 vm_prot:区域的读写权限 vm_flags:区域是否共享 UNIX V6用text.x_caddr和proc.p_addr代替vm_area_structs。,Linux组织存储器的方法,task_struct,mm,pgd,mmap,vm_area_struct,vm_end,vm_start,mm_struct,vm_prot,vm_flags,vm_next,vm_area_