首次适应算法的分析.ppt

《首次适应算法的分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、alloc和free分配和释放块1234malloc(4*sizeof(int))123456789malloc(5*sizeof(int))1234free第二次分配的5个int123456malloc(2*sizeof(int))malloc算法分析首次适应算法：从头开始搜索空闲链表，选择第一个合适的空闲块。将大的空闲块保留在链表的后面。链表起始处留下小的空闲块的碎片，增加了对较大块的搜索时间。首次适应算法速度很快，因为它尽可能少地搜索链表结点。下一次适应算法和首次适应算法很相似，是不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。若上

3、一次在一个空闲块中发现足够的空间，那么这一次也能在这个剩余块中发现所需空间。比首次适应算法快，利用率却低。最佳适应算法检查数组的每一个空闲块，选择适合所需请求大小的最小空闲块。内存管理：使用coremap[]coremap[]按照map的起始地址排序。首次适应算法存储管理器对coremap[]进行搜索，直到找到一个足够大的空闲区。若空闲区大小和要分配的空间大小正好一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。教材p77的例题例题1.coremap[]:进程申请空间大小是15（1）搜索coremap[]，找到第一个长度>=15的空闲

4、区2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_size=30>15，首次找到一个足够大的空闲区5030coremap[1]m_size=10<15（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的例题例题

5、2.coremap[]:进程申请空间大小是30（1）搜索coremap[]，找到第一个长度>=15的空闲区2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_size=30>=30，首次找到一个足够大的空闲区5030coremap[1]m_size=10<15例题2（2）空闲区的分配若m_size==0,则应删除这个元素，coremap[]数组剩下的元素向前移动一个位置。5030coremap[1]分配30个块出去，则：m_size=30-30=0，m_a

6、ddr=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_

7、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);}所找到的空白区起始地址

8、的改变所分配空白区的起始地址变化的原因：return