首页 > 代码库 > MINI3内存分配算法

MINI3内存分配算法

 1 最差适应算法
 2 #ifdef USING_WORST_FIT 
 3 {
 4         //先找到第一个满足要求的空洞,  
 5         //再以第一个为标准寻找最适合的空洞。  
 6         //当最适合的空洞完全吻合  
 7         //就直接划给它,当空洞较大时就切割。  
 8       
 9         //首先注册目标指针、目标前一个指针、头指针  
10         //记录目标大小和目前最适合大小  
11         register struct hole *hp;  
12         register struct hole *prevAim_ptr;  
13         register struct hole *Aim_ptr;  
14         phys_clicks old_base;  
15       
16         //如果循环一次都没找到  
17         //就把可以退出内存的进程赶出去  
18         //再循环  ;
19         do{  
20             hp = hole_head;  
21             prevAim_ptr = NIL_HOLE;  
22             Aim_ptr = NIL_HOLE;  
23               
24             for(;hp != NIL_HOLE && hp->h_base < swap_base;  
25                 prevAim_ptr=hp,hp=hp->h_next)  
26             {  
27                     
28                 //当从没记录过合适内存时  
29                 //把遇到的第一个合适节点保存在aim中  
30                 if(hp->h_len >= clicks && Aim_ptr == NIL_HOLE)  
31                 {  
32                     Aim_ptr=hp;  
33                 }  
34                   
35       
36                 //当找到一个比原来aim更合适的空间  
37                 //记录新的空间  
38                 if(hp->h_len >= clicks && hp->h_len > Aim_ptr->h_len)  
39                 {  
40                     //mark it down  
41                     Aim_ptr=hp;  
42                 }  
43       
44             }  
45             
46             //we found bigest
47             if(Aim_ptr!=NIL_HOLE)
48             {
49                 old_base =Aim_ptr->h_base;
50                 Aim_ptr->h_base+=clicks;
51                 Aim_ptr->h_len-=clicks;
52 
53                 /* Remember new high watermark of used memory. */  
54                 if(Aim_ptr->h_base > high_watermark)  
55                     high_watermark = Aim_ptr->h_base;  
56                   
57                 return(old_base);  
58             }
59 
60       }while(swap_out());  
61       return(NO_MEM);  
62 }
63 #endif 
View Code

 

 1 最佳适应:
 2 #ifdef  USING_BEST_FIT  
 3     {  
 4         //先找到第一个满足要求的空洞,  
 5         //再以第一个为标准寻找最适合的空洞。  
 6         //当最适合的空洞完全吻合  
 7         //就直接划给它,当空洞较大时就切割。  
 8       
 9         //首先注册目标指针、目标前一个指针、头指针  
10         //记录目标大小和目前最适合大小  
11         register struct hole *hp;  
12         register struct hole *prevAim_ptr;  
13         register struct hole *Aim_ptr;  
14         phys_clicks old_base;  
15       
16         //如果循环一次都没找到  
17         //就把可以退出内存的进程赶出去  
18         //再循环  
19         do{  
20             hp = hole_head;  
21             prevAim_ptr = NIL_HOLE;  
22             Aim_ptr = NIL_HOLE;  
23               
24             for(;hp != NIL_HOLE && hp->h_base < swap_base;  
25                 prevAim_ptr=hp,hp=hp->h_next)  
26             {  
27                 
28                 //当从没记录过合适内存时  
29                 //把遇到的第一个合适节点保存在aim中  
30                 if(hp->h_len > clicks && Aim_ptr == NIL_HOLE)  
31                 {  
32                     Aim_ptr=hp;  
33                 }  
34                   
35       
36                 //当找到一个比原来aim更合适的空间  
37                 //记录新的空间  
38                 if(hp->h_len > clicks && hp->h_len < Aim_ptr->h_len)  
39                 {  
40                     //mark it down  
41                     Aim_ptr=hp;  
42                 }  
43             }  
44             //we found it  
45             if(Aim_ptr != NIL_HOLE)  
46             {  
47                 old_base = Aim_ptr->h_base;  /* remember where it started */  
48                 Aim_ptr->h_base += clicks;   /* bite off */  
49                 Aim_ptr->h_len -= clicks;    /* ditto */  
50                   
51                 /* Remember new high watermark of used memory. */  
52                 if(Aim_ptr->h_base > high_watermark)  
53                     high_watermark = Aim_ptr->h_base;  
54                   
55                 return(old_base);  
56             }  
57               
58         }while(swap_out());  
59         return(NO_MEM);  
60     }  
61 #endif 
View Code

 

 1 下一个最适合 :
 2 #ifdef USING_NEXT_FIT //161 error
 3 {
 4     register struct hole *hp, *prev_ptr;
 5     static register struct hole *start_ptr;
 6     
 7     phys_clicks old_base;
 8    start_ptr = hole_head;
 9    Prev_ptr=NIL_HOLE; 
10     hp=start_ptr;
11     
12  do{
13         
14         if(hp->h_next==start_ptr)
15          {
16            return(NO_MEM);
17          }
18 
19       while (hp->h_next != start_ptr && hp->h_base < swap_base){
20 
21           if (hp->h_len >= clicks) {
22             /* We found a hole that is big enough.  Use it. */
23               old_base = hp->h_base;    /* remember where it started */
24               hp->h_base += clicks;    /* bite a piece off */
25               hp->h_len -= clicks;    /* ditto */
26              
27               
28               /* Delete the hole if used up completely. */
29               if (hp->h_len == 0) del_slot(prev_ptr, hp);
30              
31              If((start_ptr=hp->h_next)==NIL_HOLE)
32                Start_ptr=hole_head;
33 
34              /* Return the start address of the acquired block. */
35              return(old_base);
36              }
37              
38           prev_ptr = hp;
39           hp = hp->h_next;
40               
41           If(hp==NIL_HOLE) 
42           hp=hole_head;
43     }
44        
45    }while(swap_out());
46 }
47 #endif  
View Code
FIRST_FIT
*===========================================================================*
 *                alloc_mem分配内存                     *
 *===========================================================================*/
PUBLIC phys_clicks alloc_mem(clicks)
phys_clicks clicks;        /* amount of memory requested */
{
/* Allocate a block of memory from the free list using first fit. The block
 * consists of a sequence of contiguous bytes, whose length in clicks is
 * given by ‘clicks‘.  A pointer to the block is returned.  The block is
 * always on a click boundary.  This procedure is called when memory is
 * needed for FORK or EXEC.  Swap other processes out if needed.
 */
  register struct hole *hp, *prev_ptr;
  phys_clicks old_base;

  do {
        prev_ptr = NIL_HOLE;
    hp = hole_head;
    while (hp != NIL_HOLE && hp->h_base < swap_base) {
        if (hp->h_len >= clicks) {
            /* We found a hole that is big enough.  Use it. */
            old_base = hp->h_base;    /* remember where it started */
            hp->h_base += clicks;    /* bite a piece off */
            hp->h_len -= clicks;    /* ditto */

            /* Remember new high watermark of used memory. */
            if(hp->h_base > high_watermark)
                high_watermark = hp->h_base;

            /* Delete the hole if used up completely. */
            if (hp->h_len == 0) del_slot(prev_ptr, hp);

            /* Return the start address of the acquired block. */
            return(old_base);
        }

        prev_ptr = hp;
        hp = hp->h_next;
    }
  } while (swap_out());        /* try to swap some other process out */
  return(NO_MEM);
}