[TIL] CASPP 9장 공부5 - 간단한 할당기3(segregated)

1. 아침 문제 풀이

1. 1359번 - 복권

import sys
from itertools import combinations

N, M, K = map(int, sys.stdin.readline().split())

jimin = list(combinations(range(N), M)) # 지민이가 뽑을 수들의 조합
result = list(combinations(range(N), M)) # 당첨 결과들의 조합

luck = 0 # 당첨된 횟수 저장
for jm in jimin :
    for re in result :
        count = 0 # 현재 지민이와 결과가 같은 수의 개수
        for i in range(M) :
            for j in range(M) :
                if jm[i] == re[j] :
                    count += 1
        if count >= K : # 적어도 K개이므로 그 이상일 경우 당첨!
            luck += 1

print(luck/(len(jimin)**2))

처음에는 식으로 풀이를 하려고 접근했던 문제 - 도저히 식이 나오지 않는다.

같이 푸는 사람 중에서 조합을 이용하여 접근한 것을 참고하여 조합(combination)을 사용
지민이가 뽑는 조합과 당첨 결과 조합을 비교하여 K개 이상의 원소가 겹치면 당첨으로 생각한다.
단, 전체 조합 수는 [지민이가 뽑는 조합수 * 당첨 결과 조합수] 이다.

---

2. Segregated Free List

1. 기본 설계

1. 분리 가용 리스트

• 블럭의 최소 크기 = 16byte = 2^4인 블럭들은 seg_list[0] 에 저장되어 있다.
• 최대크기 = 2^32
• 4 ~ 32 = 29 = LIST_NUM

2.  구조

---

3. 함수 정의

1. get_list_num

    : 현재 크기가 seg_list에서 어떤 인덱스에 속하는지 구하는 함수

 

사이즈 클래스가 어디에 속하는지?

• 2의 제곱근으로 표현한다.
• 그러므로 사이즈를 2로 나눠가면서 2의 몇 제곱에 속하는지 알아가야 한다.

//2의 제곱
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1024
2^11 = 2048
2^12 = 4096
2^13 = 8192
2^14 = 16384
2^15 = 32768
2^16 = 65536
2^17 = 131072
2^18 = 262144
2^19 = 524288
2^20 = 1048576
2^21 = 2097152
2^22 = 4194304
2^23 = 8388608
2^24 = 16777216
2^25 = 33554432
2^26 = 67108864
2^27 = 134217728
2^28 = 268435456
2^29 = 536870912
2^30 = 1073741824
2^31 = 2147483648
2^32 = 4294967296

2. find_fit

    : best-fit으로 구현

• 입력 가능한 사이즈 클래스부터 확인한다.
• 가능한 가장 작은 사이즈를 선택한다.

 

3. put_free_block

    : explicit free list에서는 그냥 하나의 연결리스트에 연결했지만 이를 어떤 사이즈 클래스의 가용 리스트에 넣을지 정하고 블록을 삽입한다.

 

4. remove_free_block

    : explicit free list에서는 그냥 하나의 연결리스트에서 삭제하지만 이를 어떤 사이즈 클래스의 가용 리스트에서 삭제할지 찾고 그 리스트에서 삭제해주어야 한다.

---

4. 주의할 점

1. 블록에서 헤더에 있던 할당 비트를 사용하지 않는다.

• 가용리스트에서 삭제나 삽입을 수행할 때 연결 정보(PREV, NEXT)만 바꿔준다.

2.  place() 함수

• 함수의 인자로 받은 bp를 변경하면 안된다.
• 가장 찾기 어려웠던 오류
• 솔직히 왜 안되는지는 확실하게 알아내지는 못했다.

---

🛠️ C 구현 코드

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/* -------------- 상수 정의 -------------------------------------------- */
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8 // 2워드
#define WSIZE 4 // 1워드
#define CHUNKSIZE (1 << 12) //초기 가용 블록과 힙 확장을 위한 기본 크기
#define LIST_NUM 29 //최소크기 2^4 ~ 최대크기 2^32

/* -------------- 매크로 정의 ------------------------------------------ */
#define MAX(x, y) ((x) > (y) ? (x) : (y)) //큰 값 반환

#define PACK(size, alloc) ((size) | (alloc)) //Header or Footer 에 저장할 값 반환

#define GET(p) (*(unsigned int *)(p)) //p가 참조하는 word 반환
#define PUT(p, val) (*(unsigned int *)(p) = (val)) //p가 가리키는 word에 val 저장

#define GET_SIZE(p) (GET(p) & ~0x7) //p가 가리키는 block size 반환
#define GET_ALLOC(p) (GET(p) & 0x1) //p가 가리키는 block의 할당 비트 반환

// bp를 char형 포인터로 사용하는 이유
// 주소 위치에 대한 연산을 위해 +1은 1byte를 더해주는 연산이라는 것을 알리기 위해

#define HDRP(bp) ((char *)(bp) - WSIZE) //bp가 가리키는 block의 Header를 가리키는 포인터 반환
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - ALIGNMENT) //bp가 가리키는 block의 Footer를 가리키는 포인터 반환

#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //다음 block pointer 반환
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - ALIGNMENT))) //이전 block pointer 반환

#define PREV_FREE(bp) ((char *)(bp)) //현재 블록의 이전 가용 블록 주소 저장 위치 반환
#define NEXT_FREE(bp) ((char *)(bp) + WSIZE) //현재 블록의 다음 가용 블록 주소 저장 위치 반환

/* -------------- 함수 정의 -------------------------------------------- */
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void put_free_block(void *bp);
static void remove_free_block(void *bp);
static int get_list_num(size_t size);

/* -------------전역 변수 선언 --------------------------------------------*/
static void *heap_listp;
static void *seg_list[LIST_NUM]; //가용 리스트 크기별 헤더 저장할 배열

/* 
 * mm_init - initialize the malloc package.
 * 할당기를 초기화한다.
 * + 배열 초기화한다.
 * 성공이면 0 / 아니면 -1 반환
 */
int mm_init(void){
    //seg_list 초기화하기
    for (int i = 0; i < LIST_NUM; i++) {
        seg_list[i] = NULL;
    }

    if ((heap_listp = mem_sbrk(2 * ALIGNMENT)) == (void *)-1) {
        return -1;
    }
    PUT(heap_listp, 0); //Padding Word
    PUT(heap_listp + (1*WSIZE), PACK(ALIGNMENT, 1)); //Prolog Header
    PUT(heap_listp + (2*WSIZE), PACK(ALIGNMENT, 1)); //Prolog Footer
    PUT(heap_listp + (3*WSIZE), PACK(0, 1)); //Epilogue Header - 크기를 0으로 할당

    if (extend_heap(CHUNKSIZE/WSIZE) == NULL) {
        return -1;
    }
    return 0;
}

/*
 * 힙을 확장하기 위한 함수
 * 1. 힙을 초기화할 때
 * 2. mm_malloc()이 적당한 fit을 찾지 못했을 때
 * 요청한 크기를 정렬을 유지하기 위해 8(double words)의 배수로 반올림하여 요청
 */
static void *extend_heap(size_t words) {
    char *bp;
    // words가 홀수일 경우 1을 더한 후 4만큼 곱해준다.
    size_t size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

    //실패했을 경우
    if ((long)(bp = mem_sbrk(size)) == -1) {
        return NULL;
    }

    //새로운 가용 블록 생성
    PUT(HDRP(bp), PACK(size, 0)); //가용 블록의 HEADER
    PUT(FTRP(bp), PACK(size, 0)); //가용 블록의 FOOTER
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); //새로운 Epilogue

    //새로 할당 받은 가용 블록 앞에 또다른 가용 블록이 존재할 수 있다.
    return coalesce(bp);
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size){
    size_t asize;
    size_t extendsize;
    char *bp;
    
    if (size == 0)
        return NULL;
    
    if (size <= ALIGNMENT)
        asize = 2*ALIGNMENT; 
    else
        asize = ALIGNMENT * ((size + (ALIGNMENT) + (ALIGNMENT - 1)) / ALIGNMENT); 

    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

/*
 * segregated free list를 이용한 best-fit
 */
static void *find_fit(size_t asize) {
    int idx = get_list_num(asize); //현재 크기가 할당받을 수 있는 인덱스

    char *bp = NULL;
    void *min_size_block = NULL; //사용가능한 가장 작은 영역
    while (idx < LIST_NUM) {
        bp = seg_list[idx];
        while (bp != NULL) {
            if (GET_SIZE(HDRP(bp)) >= asize) {
                if (min_size_block == NULL) {
                    min_size_block = bp;
                }
                else if (GET_SIZE(min_size_block) > GET_SIZE(HDRP(bp))){
                    min_size_block = bp;
                }
            }
            bp = GET(NEXT_FREE(bp));
        }
        //현재 리스트에서 사용가능한 영역을 발견했으면
        if (min_size_block != NULL) {
            return min_size_block;
        }
        idx++;
    }
    return NULL;
}

/*
 * 할당받은 영역이 사용하고 남은 영역이 분할 가능한지 파악
 * 최소 블록 크기 = 16byte
 */
static void place(void *bp, size_t asize) {
    remove_free_block(bp); //할당받은 영역은 분리 가용 리스트에서 제거
    size_t size = GET_SIZE(HDRP(bp));
    if ((size - asize) >= (2 * (ALIGNMENT))) {
        //앞에서부터 할당하기
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));

        //나머지는 다음 블록에 가용 영역 할당
        //현재 bp는 인자로 받아온 것이므로 바뀌지 않도록 한다!!!!!!!!!! - 장장 6시간동안 찾으러 다닌 오류!!!!!!!!!!!!!!!!!!!!!!!
        PUT(HDRP(NEXT_BLKP(bp)), PACK(size - asize, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size - asize, 0));

        coalesce(NEXT_BLKP(bp));
    }
    else { //현재 영역 전부 사용
        PUT(HDRP(bp), PACK(size, 1));
        PUT(FTRP(bp), PACK(size, 1));
    }
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr) {
    size_t size = GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    //연결할 수 있는 가용 블록이 있으면 연결하기
    coalesce(ptr);
}

/*
 * bp : 가용 블럭 포인터
 * 현재 가용 블럭이 연결될 수 있는지 확인
 * 가능하면 연결시키기
 */
static void *coalesce(void *bp) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); //이전 블록의 할당 비트
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); //다음 블록의 할당 비트
    size_t size = GET_SIZE(HDRP(bp));

    if (prev_alloc && next_alloc) { //둘다 할당되어 있는 상태일 때
        put_free_block(bp); //현재 가용 블럭 리스트에 추가하기
        return bp;
    }
    else if (prev_alloc && !next_alloc) { //이전 블록만 할당되어 있을 때
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 다음 블록 사이즈만큼 증가
        remove_free_block(NEXT_BLKP(bp)); //다음 블록 리스트에서 제거 (현재와 연결하므로)
        // 현재 가용 블록과 다음 가용 블록 더하기
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    else if (!prev_alloc && next_alloc) { //다음 블록만 할당되어 있을 때
        size += GET_SIZE(HDRP(PREV_BLKP(bp))); //이전 블록 사이즈만큼 증가
        remove_free_block(PREV_BLKP(bp)); // 이전 블럭 리스트에서 제거
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    else { //둘다 할당 안되어 있을 때
        size += (GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp))));
        remove_free_block(PREV_BLKP(bp)); // 이전 블럭 리스트에서 제거
        remove_free_block(NEXT_BLKP(bp)); // 다음 블록 리스트에서 제거
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        //블록의 앞을 가리켜야 하므로 이전의 블록 포인터가 현재 블록 포인터
        bp = PREV_BLKP(bp);
    }
    put_free_block(bp); //현재 가용 블럭 리스트에 추가하기
    return bp;
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size) {
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = GET_SIZE(HDRP(oldptr));
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

/*
 * 분리 가용 리스트에 가용 블럭 추가하기
 */
static void put_free_block(void *bp) {
    int idx = get_list_num(GET_SIZE(HDRP(bp)));
    if (seg_list[idx] == NULL) {
        PUT(PREV_FREE(bp), NULL);
        PUT(NEXT_FREE(bp), NULL);
    }
    else {
        PUT(PREV_FREE(bp), NULL);
        PUT(NEXT_FREE(bp), seg_list[idx]);
        PUT(PREV_FREE(seg_list[idx]), bp);
    }
    seg_list[idx] = bp;
}

/*
 * 분리 가용 리스트에서 가용 블럭 삭제하기
 */
static void remove_free_block(void *bp) {
    int idx = get_list_num(GET_SIZE(HDRP(bp)));

    if(GET(PREV_FREE(bp)) == NULL) {
        if (GET(NEXT_FREE(bp)) == NULL) {
            seg_list[idx] = NULL;
        }
        else {
            PUT(PREV_FREE(GET(NEXT_FREE(bp))), NULL);
            seg_list[idx] = GET(NEXT_FREE(bp));
        }
    }
    else {
        if (GET(NEXT_FREE(bp)) == NULL) {
            PUT(NEXT_FREE(GET(PREV_FREE(bp))), NULL);
        }
        else {
            PUT(PREV_FREE(GET(NEXT_FREE(bp))), GET(PREV_FREE(bp)));
            PUT(NEXT_FREE(GET(PREV_FREE(bp))), GET(NEXT_FREE(bp)));
        }
    }
}

/*
 * seg_list 인덱스 반환하는 함수
 */
static int get_list_num(size_t size) {
    int i = -4; //2^4 가 인덱스 0이다.
    while (size != 1) {
        size = (size >> 1); // size를 2로 나눈다.
        i++;
    }
    return i;
}