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

第三节首次适应算法的分析第1页，共31页，2023年，2月20日，星期三深刻理解计算机上机编程：分配器首次适应算法、最佳适应算法、下一次适应算法第2页，共31页，2023年，2月20日，星期三首次适应算法分析#include<stdlib.h>void*malloc(size_t,size);malloc函数返回一个指针，指向大小为至少size字节的存储器块。如果malloc遇到问题，那么返回NULL。注意：与教材中的malloc函数不同。第3页，共31页，2023年，2月20日，星期三free函数释放已经分配的malloc块#include<stdlib.h>voidfree(void*ptr)Ptr参数必须指向一个从malloc获得的已经分配块的起始位置。第4页，共31页，2023年，2月20日，星期三malloc和free分配和释放块1234malloc(4*sizeof(int))123456789malloc(5*sizeof(int))1234free第二次分配的5个int123456malloc(2*sizeof(int))第5页，共31页，2023年，2月20日，星期三malloc算法分析首次适应算法：从头开始搜索空闲链表，选择第一个合适的空闲块。将大的空闲块保留在链表的后面。链表起始处留下小的空闲块的碎片，增加了对较大块的搜索时间。首次适应算法速度很快，因为它尽可能少地搜索链表结点。下一次适应算法和首次适应算法很相似，是不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。若上一次在一个空闲块中发现足够的空间，那么这一次也能在这个剩余块中发现所需空间。比首次适应算法快，利用率却低。最佳适应算法检查数组的每一个空闲块，选择适合所需请求大小的最小空闲块。第6页，共31页，2023年，2月20日，星期三内存管理：使用coremap[]coremap[]按照map的起始地址排序。

第7页，共31页，2023年，2月20日，星期三首次适应算法存储管理器对coremap[]进行搜索，直到找到一个足够大的空闲区。若空闲区大小和要分配的空间大小正好一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。第8页，共31页，2023年，2月20日，星期三教材p77的例题例题1.coremap[]:进程申请空间大小是15（1）搜索coremap[]，找到第一个长度>=15的空闲区2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_size=30>15，首次找到一个足够大的空闲区5030coremap[1]m_size=10<15第9页，共31页，2023年，2月20日，星期三（2）空闲区的分配新的coremap[]数组5030coremap[1]分配15个块出去，则：m_size=30-15=15，m_addr=50+15=65。2010coremap[2]6515coremap[1]10020coremap[0]0coremap[CMAPSIZ-1]……第10页，共31页，2023年，2月20日，星期三教材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=10<15第11页，共31页，2023年，2月20日，星期三例题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]有变化第12页，共31页，2023年，2月20日，星期三malloc()函数malloc(mp,size)Structmap*mp;{registerinta;//a是malloc返回的分配区的起始块号registerstructmap*bp;//bp是工作块

第13页，共31页，2023年，2月20日，星期三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;第14页，共31页，2023年，2月20日，星期三malloc()}while((bp-1)->m_size=bp->m_size);//最后一个元素的长度为0，结束移动return(a);//malloc()成功，则返回分配区的起始地址a}}return(0);}第15页，共31页，2023年，2月20日，星期三所找到的空白区起始地址的改变所分配空白区的起始地址变化的原因：return(a)，而且a=m_addr若此空白区的起始地址不变化，则与a相同，引起混淆。所以，m_addr=m_addr+m_size第16页，共31页，2023年，2月20日，星期三2.mfree()回收算法《现代操作系统》P105回收时有四种情况：1.aa与前空白区(bp-1)相邻(bp-1).m_size=+size2.aa与前、后空白区相邻(bp-1).m_size=+bp.m_sizecoremap[]元素向前移动一个位置3.aa与后空白区相邻bp.m_addr=aabp.m_size=+size4.aa不与任何空白区相邻bp.m_addr=aa;bp.m_size=size;coremap[]的元素向后移动一个位置，bp++第17页，共31页，2023年，2月20日，星期三mfree()mfree(mp,size,aa)Structmap*mp;{registerstructmap*bp;registerintt;registerinta;第18页，共31页，2023年，2月20日，星期三mfree()a=aa;for(bp=mp;bp->m_addr<=a&&bp->m_size!=0;bp++);if(bp>mp&&(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)使上一个和下一个空白区连起

第19页，共31页，2023年，2月20日，星期三mfree()while(bp->m_size){//第二种情况coremap[]元素向前移动一个位置bp++;(bp-1)->m_addr=bp->m_addr;(bp-1)->m_size=bp->m_size;}}}第20页，共31页，2023年，2月20日，星期三mfree()else{//第三种情况map(aa,size)与下一个空白区相邻if(a+size==bp->m_addr&&bp->m_size){bp->m_addr=-size;bp->m_size=+size;}第21页，共31页，2023年，2月20日，星期三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);}}第22页，共31页，2023年，2月20日，星期三教材p79的例题例题3.coremap[]:回收区大小size=5，起始地址aa=40（1）搜索coremap[]，找到比回收区起始地址aa大的第一个空闲区。2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_addr=50>40，找到比回收区aa高的空闲区，bp=&coremap[1]5030coremap[1]m_addr=20<40第23页，共31页，2023年，2月20日，星期三（2）回收区的回收新的coremap[]数组405coremap[1]20+10<4040+5<50第四种情况2010coremap[2]405coremap[1]5030coremap[0]0coremap[CMAPSIZ-1]……coremap[2]10020coremap[]数组的元素从bp开始，向后移动一位。第24页，共31页，2023年，2月20日，星期三教材p79的例题例题3.coremap[]:回收区大小size=10，起始地址aa=40（1）搜索coremap[]，找到比回收区起始地址aa大的第一个空闲区。2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_addr=50>40，找到比回收区aa高的空闲区，bp=&coremap[1]5030coremap[1]m_addr=20<40第25页，共31页，2023年，2月20日，星期三例题4（2）回收区的回收新的coremap[]数组4010coremap[1]20+10<4040+10=50第三种情况2010coremap[2]4040coremap[1]10020coremap[0]0coremap[CMAPSIZ-1]……4040coremap[1]m_addr=40m_size=10+30=40coremap[]数组元素不必改变位置。第26页，共31页，2023年，2月20日，星期三下一次适应算法最佳适应算法最差适应算法《现代操作系统》P105第27页，共31页，2023年，2月20日