저장 관리의 동적 구역 분배 (실험 4)

저장 관리 중의 연속 메모리 분 배 는 절대 불 러 오 는 방식 과 위치 추적 불 러 오 는 방식 이 있 습 니 다.절대 불 러 오 는 방식 입 니 다. 같은 시간 에 메모리 에 하나의 프로 세 스 만 실 행 될 수 있 습 니 다. 프로그램 이 메모리 에 있 는 물리 적 주 소 는 프로그램 을 작성 할 때의 논리 적 주소 와 완전히 같 아야 합 니 다.포 지 셔 닝 불 러 오 는 방식 은 여러 프로그램 이 디자인 한 여러 프로그램 이 메모리 에 불 러 오 는 문 제 를 해결 하고 여러 프로그램 이 동시에 메모리 에 불 러 오 는 것 을 실현 합 니 다.동적 구역 분배 알고리즘 은 첫 번 째 적응 알고리즘, 순환 첫 적응 알고리즘, 최 적 적응 알고리즘, 최 악의 적응 알고리즘 이 있다.
첫 번 째 적응 알고리즘: 빈 파 티 션 링크 는 주소 가 증가 하 는 순서 로 연결 되 고 메모 리 를 할당 할 때 체인 의 첫 번 째 순서 로 찾 습 니 다. 크기 가 만족 할 수 있 는 빈 파 티 션 을 찾 을 때 까지 단점 이 있 습 니 다. 낮은 주소 가 계속 분할 되 어 작은 파 티 션 (조각) 이 많이 생 깁 니 다.
순환 첫 적응 알고리즘: 분배 구역 은 지난번 에 찾 은 빈 구역 의 다음 빈 구역 부터 찾 아 파편 화 및 찾기 비용 을 줄 입 니 다.
최 적 적응 알고리즘: 남 은 파 티 션 은 파 티 션 크기 에 따라 작은 것 부터 큰 것 까지 정렬 되 고 파 티 션 을 나 눌 때 수 요 를 만족 시 킬 수 있 으 며 가장 작은 남 은 파 티 션 을 작업 에 나 누 어 주 며 단점 은 파편 이 생기 기 쉽다.
최 악의 적응 알고리즘: 남 은 파 티 션 은 파 티 션 크기 에 따라 큰 것 에서 작은 것 으로 정렬 되 고 파 티 션 을 할당 할 때 가장 큰 분 배 를 선택 하 며 매번 큰 남 은 파 티 션 을 나 누 어야 하 는 단점 이 있 습 니 다. 그러면 메모리 에 큰 남 은 파 티 션 이 부족 합 니 다.
동적 구역 분배 의 첫 번 째 적응 알고리즘 의 C 언어 시 뮬 레이 션:

#include 
#include 
#include 

struct frist_fit { /*      */
    int c_begin;
    int c_size;
    int NO;
    struct frist_fit *next;
    frist_fit() /*      */
    {
        c_begin = 0;
        c_size = 0;
        NO = -1;
        next = NULL;
    }
    void set_date(int c_size,int c_begin = 0,int NO = -1) /*      */
    {
        this->c_size = c_size;
        this->c_begin = c_begin;
        this->NO = NO;
        return;
    }

};

int menu() /*  */
{
    printf("create pthread:1
");
    printf("free memory:2
");
    printf("if over input:0
");
    printf("plase input a num: ");
    int m;
    scanf("%d",&m);
    switch(m){
    case 0:
    case 1:
    case 2:
        return m; break;
    default:
        return -1;
    }

    return m;
}

void init(struct frist_fit *head,int C_size) /*       */
{
    struct frist_fit *temp = new frist_fit();
    temp->set_date(C_size);
    head->next = temp;

    return;
}

void Out_one(struct frist_fit *t){ /*        */
    printf("NO=%d,begin=%d,size=%d
",t->NO,t->c_begin,t->c_size);

    return;
}

void Out(struct frist_fit *head) /*        */
{
    for(struct frist_fit *t = head ->next; t; t = t->next){
        Out_one(t);
    }
    printf("
");
}

void c_malloc(struct frist_fit *create,struct frist_fit *free) /*       */
{
    int NO,c_size;
    printf("please input Pathread_NO and Memory
");
    scanf("%d%d",&NO,&c_size);

    struct frist_fit *t = NULL;
    for(t = create; t->next; t = t->next){ /*               */
        if(t->next->c_size >= c_size){ /*      */
                struct frist_fit *temp = new  frist_fit();
                temp->c_begin = t->next->c_begin;
                temp->c_size = c_size;
                temp->NO = NO;
                temp ->next = free->next;
                free->next = temp; /*                */
                if(!(t->next->c_size - c_size)){ /*    */
                       struct frist_fit *p = t->next;
                        t->next = t->next->next;
                        delete p;
                        return;
                }
                else{ /*    */
                    t ->next->set_date(t->next->c_size - c_size,t->next->c_begin + c_size);
                    return;
                }
        }

    }
      if(t ->next == NULL){ /*            */
        printf("malloc memory failed
");
        return;
      }
    return;
}

void  c_free(struct frist_fit *create,struct frist_fit *free) /*    */
{
    int NO;
    printf("please input will delete pthread NO: ");
    scanf("%d",&NO);

    struct frist_fit *p = NULL;
    struct frist_fit *pp = NULL;
    for(p = free; p ->next; p = p->next) /*        */
        if(p->next->NO == NO){
            pp = p->next;
            p->next = p->next->next;
            break;
        }
        if(!pp){ /*       */
            printf("the pthread not create
");
            return;
        }

    for(struct frist_fit *q = create ->next; q; q = q ->next){ /*      */
        if(pp->c_begin + pp->c_size == q ->c_begin){ /*                     */
                q->set_date(q->c_size + pp->c_size,pp->c_begin,q->NO);
                delete pp;
                return;
        }else if(q ->next && q ->next->c_begin + q->next->c_size == pp->c_begin){ /*                     */
                 q->next->set_date(q->next->c_size + pp->c_size,q->next->c_begin,q->next->NO);
                 delete pp;
                 return;
        }else if(q->next && q->c_begin + q->c_size == pp ->c_begin && pp ->c_begin + pp ->c_size == q ->next->c_begin){/*                     */
                q->set_date(q->c_size + q->next->c_size + pp->c_size,q->c_begin,q->NO);
                struct frist_fit *qq = q->next;
                q->next = q->next->next;
                delete qq;
                return;
        }
    }
    pp ->set_date(pp->c_size,pp->c_begin); /*            */

    struct frist_fit *q =NULL;
    for(q = create; q ->next; q = q ->next) /*                        */
        if(q->next->c_begin > pp->c_begin){
            pp ->next = q->next;
            q->next = pp;
            return;
        }

    pp->next = NULL;
    q->next = pp; /*               */

    return;
}

int main(int arc,char *agv[])
{
    struct frist_fit *create = new frist_fit(); /*      */
    struct frist_fit *free = new frist_fit(); /*       */
    int C_size;
    int change;
    printf("please input memory size:
");
    scanf("%d",&C_size);
    init(create,C_size); /*       */
    printf("memory all size:
");
    Out(create); /*        */

    while((change = menu())){
        switch(change){
            case 1: c_malloc(create,free); break; /*      */
            case 2: c_free(create,free); break; /*      */
            case -1: printf("input wrong
"); break;

        }

       /*    */

       printf("
      
");
       Out(free);

       printf("    
");
       Out(create);
    }

    return 0;
}