크래프톤 정글 WEEK5 Day 43 - 퀴즈 리뷰 / implict list(best fit, realloc 개선 코드)

📆24.02.20

1. 5주차 퀴즈
2. find fit(best-fit)
3. realloc 코드 이해
4. 프로그래머스 / 백준

 

5주차 퀴즈

 

1. 페이징과 세그멘테이션 정의 및 각각의 장단점

 

페이징

• 메모리를 동일한 크기의 블록, 즉 '페이지'로 나누는 방법이다.
• 각 페이지는 가상 메모리 주소와 매핑되며, 페이지 테이블을 통해 물리적 메모리 주소로 변환된다.
• 페이징은 메모리 관리를 단순화하고, 메모리의 낭비를 줄이며, 프로그램 간의 메모리 충돌을 감지한다.

장점

• 외부 단편화 문제를 해결
• 메모리 관리가 상대적으로 단순하다

단점

• 내부 단편화 발생 가능성이 있음
• 페이지 테이블 관리에 추가적인 메모리가 필요함

 

세그멘테이션

• 세그멘테이션은 메모리를 의미 있는 단위인 '세그먼트'로 나누는 방법이다.
• 각 세그먼트는 시작 주소와 길이를 가지며, 다른 유형의 데이터(예 :  코드, 데이터, 스택)를 위해 사용된다.
• 세그멘테이션은 메모리를 더 유연하게 관리할 수 있게 해주며, 프로그램의 논리적 구조를 반영할 수 있다.

장점

• 메모리를 논리적 단위로 나누어 프로그램의 구조를 반영함
• 세그먼트별 보호와 공유가 용이함

단점

• 외부 단편화 발생 가능성이 있음
• 메모리 관리가 복잡해질 수 있음

 

2. First -fit, Next-fit, Best-fit일 때 요청에 대한 메모리 할당 순서

 

메모리 블록 : A(10), B(50), C(25), D(30), E(40)

요청 순서 : 1(30) , 2(25) , 3(25), 4(10)

 

• First- fit : 처음부터 탐색하고 크기가 맞는 첫 가용 블록을 선택한다.
  •  순서 :  B - C - D - A
• Next-fit : 이전 탐색이 종료된 시점부터 탐색한다.
  •  순서 : B - C - D - E
• Best-fit : 모든 가용 블록을 검사해서, 크기에 맞는 가용 블록 중 가장 작은 블록을 찾는다.
  • 순서 : D - C - E - A

 

3.  DMA의 기본 개념 , DMA가 시스템 성능에 미치는 이점 두 가지 이상 제시

• DMA는 Direct Memory Access의 약자로, CPU의 중재 없이 주변장치가 메모리에 직접 접근하여 데이터를 읽고 쓸 수 있게 해주는 시스템의 한 기능이다.
• DMA를 사용함으로써, 데이터 전송 과정에서 CPU가 필요하지 않으므로 , CPU는다른 작업을 수행하는 데 더 많은 시간을 할애할 수 있다. 이는 시스템 성능의 향상으로 이어지는데, 특히 I/O작업이 많은 시스템에서 그 이점이 두드러진다.
• 첫째, CPU의 부하가 감소하여 전체 시스템의 효율성이 증가한다
• 둘째, 데이터 전송 속도가 향상되므로, 전반적인 시스템 응답 시간이 단축된다.

 

4. 아래 코드 실행 결과

 

#include <stdio.h>

int main() {
	char* str[2];
	str[0] = "hello!";
	str[1] = "jungler";
	printf("1. %s\n", str[0] + 1);
	printf("2. %s\n", (str + 1)[0] + 2);
	return 0;
}

 

1 . ello!

2. ngler

 

내 답안

1 . e

2.  n

-> %s 를 보지 못하고 문자 하나만 출력하였다. %s는 문자열을 출력해야하므로 str[0] + 1번째, (str+1)[0] + 2 번째 부터의 문자열을 출력해야 한다.

str[0] + 1 -> str[0]의 1번째     ,  (str+1)[0] +2 ->  str[1] +2 , str[1]의 2번

 

5. 1 2 4 4 3 5 5 6의 입력이 Do it 알고리즘책 p.294의 알고리즘에 주어질 때의 상태를 그려라

 

 

malloc (best-fit)

 

best-fit은 가용 블록 리스트에서 가장 적합한 블록을 찾는다.

static void *find_fit(size_t asize)
{
    void *bp;
    void *best_fit = NULL;  //가장 적합한 블록 포인터

    for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {   
            // best_fit이 NULL이거나 현재 검사 중인 bp의 크기가 이전에 찾은 best_fit의 크기보다 작을 때
            if(!best_fit || GET_SIZE(HDRP(bp)) < GET_SIZE(HDRP(best_fit)))
                best_fit = bp;
        }
    }
    return best_fit;
}

 

 

기존 mm_realloc 

 void *mm_realloc(void *ptr, size_t size)
 {
     void *oldptr = ptr;     // 주어진 포인터를 oldptr에 복사.
     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;  //새로운 메모리 블록 포인터 반환
}

 

기존 mm_realloc은 무조건 새로운 메모리를 할당한 뒤, 데이터를 복사하는 방식이다. 그러다보니 반복적인 메모리 할당으로 코드의 효율성이 떨어진다.

 

mm_realloc을 개선하여 새로 크기를 조정하려는 블록의 다음 블록이 가용 블록이라면 새로 메모리 할당을 안해줘도 되게 하면 메모리적으로 효율적이게 된다! ( 단순히 헤더, 푸터의 사이즈 정보만 갱신해준다.)

개선된 mm_realloc

 

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr; //이전 포인터
    void *newptr;   //새로 메모리 할당 포인터

    size_t originsize = GET_SIZE(HDRP(oldptr)); // 원본 사이즈
    size_t newsize = size + DSIZE;      // 새 사이즈 + (헤더와 푸터 고려)
    
    // newsize가 더 작은 경우
    if (newsize <= originsize) {
        return oldptr;      //기존 메모리 블록 반환 (크기 줄일 필요 없음)
    }
    else {
        // 연속된 블록이 비어있고, 새로운 메모리 블록의 크기가 연속된 블록의 크기보다 작거나 같으면
        // 이전 메모리 블록의 사이즈를 새로운 크기로 설정해준다.
        size_t addSize = originsize + GET_SIZE(HDRP(NEXT_BLKP(oldptr)));    
        if (!GET_ALLOC(HDRP(NEXT_BLKP(oldptr))) && (newsize <= addSize)) 
        {
            PUT(HDRP(oldptr), PACK(addSize, 1));
            PUT(FTRP(oldptr), PACK(addSize, 1));
            return oldptr;
        }
        else
        {
            newptr = mm_malloc(newsize);    //새로운 메모리 블록 할당
            if (newptr == NULL)
                return NULL;
            memcpy(newptr, oldptr, newsize);    //이전 메모리 블록에서 새로운 메모리 블록으로 데이터를 복사
            mm_free(oldptr);
            return newptr;
        }
    }
}

 

프로그래머스

 

 

머쓱이 도장 깨기 5일차

문제들이 재밌어서 풀기 재밌다