KraftonJungle2기/Today I Learned
[TIL] CSAPP 9장 공부3 - next-fit
SooooooooS
2023. 5. 14. 18:26
728x90
1. 알고리즘 문제 풀이
1. 1107번 - 리모컨
import sys
N = int(sys.stdin.readline()) #목표 채널
M = int(sys.stdin.readline()) # 망가진 번호 수
brocken = {}
if M :
for i in list(sys.stdin.readline().split()) :
brocken[i] = 1
count = abs(100 - N) # + 또는 - 로만 움직였을 때 횟수
if count != 0 : # 이미 목표 채널이 아닐 경우만 반복
for i in range(1000001) :
num = str(i) #현재 채널 번호
length = len(num)
for j in range(length) :
if num[j] in brocken : #채널번호에 망가진 번호가 존재하면 갈수 없음
break
elif j == length-1 :
# 목표 번호 - 현재 번호 = + or -로 이동한 횟수
# length = 현재 번호로 이동하기 위헤 누른 횟수
count = min(count, abs(N-i) + length)
print(count)단순하게 생각하면 풀 수 있는 문제였다.
그러나 어떻게 해야 할지 감이 잘 안잡혀서 결국 참고하여 코드를 짰다.
< 참고 > https://velog.io/@jajubal/파이썬백준-1107-리모컨
count를 최소로 계속 업데이트하면서 구한다.
이때, 가장 생각을 하지 못했던 것은 횟수를 어떤 식으로 구해야 하는지 막막했다.
하지만 단순히 생각하면 이동한 채널번호(입력 횟수 존재)에서 목표 채널까지 + 또는 - 로만 이동할 수 있다.
이를 식으로 만들어 보면 len(이동한 채널 번호) + abs(목표 채널 - 이동한 채널) 로 간단하게 구현할 수 있다.
2. next-fit
이전 검색이 종료된 지점부터 가용리스트 검색하는 방법
- 이전 검색에서 가용블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어
next-fit을 사용하기 위해서는 계속해서 마지막 탐색 지점을 업데이트 해주어야 한다.
★ 주의할 점 ★
1. find-fit 함수를 사용할 때
가용 블록을 찾으면 그 다음 위치부터 탐색할 수 있도록 한다.
+ 마지막 탐색지점 이후 끝까지 못찾으면 그 앞부분도 확인해야한다.
★ 업데이트할 지점 ★
1. coalesce 함수를 사용할 때
가용 블록을 연결하면 원래 저장되어있던 위치가 사라질 수 있으므로 업데이트 필요
2. place 함수를 사용할 때
남은 가용영역이 존재할 시 그 영역이 현재 마지막으로 탐색을 마친 곳이다.
현재 malloc-lab 과제 진행상황
1. implicit (first-fit) 구현 완료 - 54점
2. implicit (next-fit) 구현 완료 - 83점
🛠️ 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 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의 할당 비트 반환
#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 반환
/* -------------- 함수 정의 -------------------------------------------- */
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 *heap_listp;
static char *nextfit;
/*
* mm_init - initialize the malloc package.
* 할당기를 초기화한다.
* 성공이면 0 / 아니면 -1 반환
*/
int mm_init(void){
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으로 할당
heap_listp += (2 * WSIZE);
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) {
return -1;
}
nextfit = heap_listp; //마지막 탐색지점을 저장할 변수 초기화
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;
//size가 0이면 필요 없다.
if (size == 0) {
return NULL;
}
//size가 2 word 보다 작을 경우
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;
}
/*
* next-fit 검색 수행
* 83점
*/
static void *find_fit(size_t asize) {
char *bp = nextfit;
// epilogue 의 크기는 0이다.
while (GET_SIZE(HDRP(bp)) > 0) {
if (!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) >= asize)) {
nextfit = bp;
return bp;
}
bp = NEXT_BLKP(bp);
}
//epilogue에서 while문이 끝나면 처음부터 검색
//단, nextfit보다 전까지만 검색
bp = heap_listp; //처음으로 초기화
while (bp < nextfit){
if (!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) >= asize)) {
nextfit = bp;
return bp;
}
bp = NEXT_BLKP(bp);
}
return NULL;
}
static void place(void *bp, size_t asize) {
size_t size = GET_SIZE(HDRP(bp));
//최소 블록 크기 = 16byte
if ((size - asize) >= (2 * (ALIGNMENT))) {
//앞에서부터 할당하기
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
//나머지는 다음 블록에 가용 영역 할당
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(size - asize, 0));
PUT(FTRP(bp), PACK(size - asize, 0));
nextfit = 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);
}
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) { //둘다 할당되어 있는 상태일 때
return bp;
}
else if (prev_alloc && !next_alloc) { //이전 블록만 할당되어 있을 때
size += GET_SIZE(HDRP(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))); //이전 블록 서이즈만큼 증가
//현재 가용 블록과 이전 가용 블록 더하기
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
//블록의 앞을 가리켜야 하므로 이전의 블록 포인터가 현재 블록 포인터
bp = PREV_BLKP(bp);
}
else { //둘다 할당 안되어 있을 때
size += (GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
//블록의 앞을 가리켜야 하므로 이전의 블록 포인터가 현재 블록 포인터
bp = PREV_BLKP(bp);
}
nextfit = 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;
}728x90