惰性好友算法

Question

如何在linux上实现懒人好友系统算法？ Di 的初始值为 0。操作后，Di 的值更新如下：- (I) 如果下一个操作是对大小为 2i 的块的块分配请求：如果有任何空闲块，select 分配一个如果 selected 块在本地是免费的那么 Di = Di + 2; 否则 Di = Di + 1; 别的首先通过将一个较大的块分成两个来获得两个块。分配一个并标记其他本地空闲 Di不变。

(II)如果下一个操作是块大小为2i的无块请求案例 Di >= 2：将其标记为本地免费并在本地将其释放。迪 = 2 案例 Di = 1： mark it globally free 全局释放；尽可能合并迪 = 0 案例 Di = 0 mark it globally free 全局释放；尽可能合并 Select 一个大小为 2i 的本地空闲块并全局释放它；尽可能合并迪 = 0;

Answer 1

#include<stdio.h>

int tree[2050],i,j,k;
void segmentalloc(int,int),makedivided(int),makefree(int),printing(int,int);
int place(int),power(int,int);

main()
{
    int totsize,cho,req;
    for(i=0;i<80;i++) printf("%c",5);
        printf(" B U D D Y S Y S T E M R E Q U I R E M E N T S\n");
    for(i=0;i<80;i++) printf("%c",5);
        printf("Enter the Size of the memory : ");
    scanf("%d",&totsize);
    while(1)
    {
        for(i=0;i<80;i++) printf("%c",5);
            printf(" B U D D Y S Y S T E M\n");
        for(i=0;i<80;i++) printf("%c",5);
            printf("    * 1) Locate the process into the Memory\n");
        printf("    * 2) Remove the process from Memory\n");
        printf("    * 3) Tree structure for Memory allocation Map\n");
        printf("    * 4) Exit\n");
        for(i=0;i<80;i++) printf("%c",5);
            printf("* Enter your choice :\n ");
        scanf("%d",&cho);
        switch(cho)
        {
            case 1:
            printf(" ");
            for(i=0;i<80;i++) printf("%c",5);
                printf(" ");
            printf("M E M O R Y A L L O C A T I O N \n");
            for(i=0;i<80;i++) printf("%c",5);
                printf("* Enter the Process size : ");
            scanf("%d",&req);
            segmentalloc(totsize,req);
            break;
            case 2:
            printf(" ");
            for(i=0;i<80;i++) printf("%c",5);
                printf(" ");
            printf("M E M O R Y D E A L L O C A T I O N \n\n");
            for(i=0;i<80;i++) printf("%c",5);
                printf("* Enter the process size : ");
            scanf("%d",&req);
            makefree(req);
            break;
            case 3:
            printf(" ");
            for(i=0;i<80;i++) printf("%c",5);
                printf("M E M O R Y A L L O C A T I O N M A P\n\n");
            for(i=0;i<80;i++) printf("%c",5);
                printf(" ");
            printing(totsize,0);
            printf(" ");
            for(i=0;i<80;i++) printf("%c",5);
                break;
            default:
            return;
        }
    }
}

void segmentalloc(int totsize,int request)
{
    int flevel=0,size;
    size=totsize;
    if(request>totsize)
    {
        printf("%c R E S U L T : ",2);
        printf("* The system don't have enough free memory\n");
        printf("* Suggession : Go for VIRTUAL MEMORY\n");
        return;
    }
    while(1)
    {
        if(request<size && request>(size/2))
            break;
        else
        {
            size/=2;
            flevel++;
        }
    }
    for(i=power(2,flevel)-1;i<=(power(2,flevel+1)-2);i++)
        if(tree[i]==0 && place(i))
        {
            tree[i]=request;
            makedivided(i);
            printf("Result : Successful Allocation\n");
            break; 
        }
        if(i==power(2,flevel+1)-1)
        {
            printf(" Result : ");
            printf("* The system don't have enough free memory\n");
            printf("* Suggession : Go for VIRTUAL Memory Mode\n");
        }
    }

    void makedivided(int node)
    {
        while(node!=0)
        {
            node=node%2==0?(node-1)/2:node/2;
            tree[node]=1;
        }
    }

    int place(int node)
    {
        while(node!=0)
        {
            node=node%2==0?(node-1)/2:node/2;
            if(tree[node]>1)
                return 0;
        }
        return 1;
    } 

    void makefree(int request)
    {
        int node=0;
        while(1)
        {
            if(tree[node]==request)
                break;
            else
                node++;
        }
        tree[node]=0;
        while(node!=0)
        {
            if(tree[node%2==0?node-1:node+1]==0 && tree[node]==0)
            {
                tree[node%2==0?(node-1)/2:node/2]=0;
                node=node%2==0?(node-1)/2:node/2;
            }
            else break;
        }
    }

    int power(int x,int y)
    {
        int z,ans;
        if(y==0) return 1;
        ans=x;
        for(z=1;z<y;z++)
            ans*=x;
        return ans;
    } 

    void printing(int totsize,int node)
    {
        int permission=0,llimit,ulimit,tab;
        if(node==0)
            permission=1;
        else if(node%2==0)
            permission=tree[(node-1)/2]==1?1:0;
        else
            permission=tree[node/2]==1?1:0;
        if(permission)
        {
            llimit=ulimit=tab=0;
            while(1)
            {
                if(node>=llimit && node<=ulimit)
                    break;
                else
                {
                    tab++;
                    printf(" ");
                    llimit=ulimit+1;
                    ulimit=2*ulimit+2;
                }
            }
            printf(" %d ",totsize/power(2,tab));
            if(tree[node]>1)
                printf("---> Allocated %d",tree[node]);
            else if(tree[node]==1)
                printf("---> Divided");
            else printf("---> Free");
            printing(totsize,2*node+1);
            printing(totsize,2*node+2);
        }
    }

惰性好友算法

Lazy Buddy Algorthm

c++

linux