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

•深刻理解计算机•上机编程：分配器•首次适应算法、最佳适应算法、下一次适应算法首次适应算法分析•#includestdlib.h•void*malloc(size_t,size);•malloc函数返回一个指针，指向大小为至少size字节的存储器块。•如果malloc遇到问题，那么返回NULL。•注意：与教材中的malloc函数不同。free函数释放已经分配的malloc块•#includestdlib.h•voidfree(void*ptr)•Ptr参数必须指向一个从malloc获得的已经分配块的起始位置。malloc和free分配和释放块1234malloc(4*sizeof(int))123456789malloc(5*sizeof(int))1234free第二次分配的5个int123456malloc(2*sizeof(int))malloc算法分析•首次适应算法：从头开始搜索空闲链表，选择第一个合适的空闲块。•将大的空闲块保留在链表的后面。链表起始处留下小的空闲块的碎片，增加了对较大块的搜索时间。•首次适应算法速度很快，因为它尽可能少地搜索链表结点。•下一次适应算法和首次适应算法很相似，是不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。•若上一次在一个空闲块中发现足够的空间，那么这一次也能在这个剩余块中发现所需空间。•比首次适应算法快，利用率却低。•最佳适应算法检查数组的每一个空闲块，选择适合所需请求大小的最小空闲块。内存管理：使用coremap[]•coremap[]按照map的起始地址排序。•首次适应算法•存储管理器对coremap[]进行搜索，直到找到一个足够大的空闲区。•若空闲区大小和要分配的空间大小正好一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。教材p77的例题•例题1.•coremap[]:•进程申请空间大小是15•（1）搜索coremap[]，找到第一个长度=15的空闲区2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_size=3015，首次找到一个足够大的空闲区5030coremap[1]m_size=1015•（2）空闲区的分配•新的coremap[]数组5030coremap[1]分配15个块出去，则：m_size=30-15=15，m_addr=50+15=65。2010coremap[2]6515coremap[1]10020coremap[0]0coremap[CMAPSIZ-1]……教材p78的例题•例题2.•coremap[]:•进程申请空间大小是30•（1）搜索coremap[]，找到第一个长度=15的空闲区2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_size=30=30，首次找到一个足够大的空闲区5030coremap[1]m_size=1015例题2•（2）空闲区的分配•若m_size==0,则应删除这个元素，coremap[]数组剩下的元素向前移动一个位置。5030coremap[1]分配30个块出去，则：m_size=30-30=0，m_addr=50+30=80201010020coremap[1]coremap[0]0coremap[CMAPSIZ-2]……800coremap[1]有变化malloc()函数•malloc(mp,size)•Structmap*mp;•{•registerinta;//a是malloc返回的分配区的起始块号•registerstructmap*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++开始元素向前移动一个位置•(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_size2.mfree()回收算法《现代操作系统》P105•回收时有四种情况：•1.aa与前空白区(bp-1)相邻•(bp-1).m_size=+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)•Structmap*mp;•{•registerstructmap*bp;•registerintt;•registerinta;mfree()•a=aa;•for(bp=mp;bp-m_addr=a&&bp-m_size!=0;bp++);•if(bpmp&&(bp-1)-m_addr+(bp-1)-m_size==a){//第一种情况•(bp-1)-m_size=+size;//map(aa,size)回收到上一个空白区(bp-1)•if(a+size==bp-m_addr){//第二种情况•(bp-1)-m_size=+bp-m_size;•//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&&bp-m_size){•bp-m_addr=-size;•bp-m_size=+size;•}mfree()•elseif(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);•}}教材p79的例题•例题3.•coremap[]:•回收区大小size=5，起始地址aa=40•（1）搜索coremap[]，找到比回收区起始地址aa大的第一个空闲区。2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_addr=5040，找到比回收区aa高的空闲区，bp=&coremap[1]5030coremap[1]m_addr=2040•（2）回收区的回收•新的coremap[]数组405coremap[1]20+104040+550第四种情况2010coremap[2]405coremap[1]5030coremap[0]0coremap[CMAPSIZ-1]……coremap[2]10020coremap[]数组的元素从bp开始，向后移动一位。教材p79的例题•例题3.•coremap[]:•回收区大小size=10，起始地址aa=40•（1）搜索coremap[]，找到比回收区起始地址aa大的第一个空闲区。2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_addr=5040，找到比回收区aa高的空闲区，bp=&coremap[1]5030coremap[1]m_addr=2040例题4•（2）回收区的回收•新的coremap[]数组4010coremap[1]20+104040+10=50第三种情况2010coremap[2]4040coremap[1]10020coremap[0]0coremap[CMAPSIZ-1]……4040coremap[1]m_addr=40m_size=10+30=40coremap[]数组元素不必改变位置。下一次适应算法•最佳适应算法•最差适应算法•《现代操作系统》P105Linux虚拟存储器系统•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:区域的读写权限•vm_flags:区域是否共享Linux组织存储器的方法task_structmmpgdmmapvm_area_structvm_endvm_startmm_structvm_protvm_flagsvm_nextvm_area_structvm_endvm_startvm_protvm_flagsvm_next链表进程地址空间共享库数据文本APRProc[]