728x90
1. 아침 문제 풀이
1. 10026번 - 적록색약
import sys
from collections import deque
N = int(sys.stdin.readline())
graph = [list(sys.stdin.readline().strip()) for _ in range(N)]
color_count = 0
color_weakness = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y) : #색약이 아닌 사람이 보는 구역
global color_count, color_weakness
queue = deque()
visited[x][y] = 1
queue.append((x,y))
while queue :
curx, cury = queue.popleft()
for i in range(4) :
nx, ny = curx + dx[i], cury + dy[i]
if 0 <= nx and nx < N and 0 <= ny and ny < N and visited[nx][ny] == 0 and graph[curx][cury] == graph[nx][ny]:
queue.append((nx, ny))
visited[nx][ny] = 1
def weak_bfs(x, y) : #적록색약인 사람이 보는 구역
global color_count, color_weakness
queue = deque()
weak_visited[x][y] = 1
queue.append((x,y))
flag = True # True일 경우 R,G 탐색
if graph[x][y] == 'B' :
flag = False
while queue :
curx, cury = queue.popleft()
for i in range(4) :
nx, ny = curx + dx[i], cury + dy[i]
if 0 <= nx and nx < N and 0 <= ny and ny < N and weak_visited[nx][ny] == 0 :
if flag and (graph[nx][ny] == 'R' or graph[nx][ny] == 'G'):
queue.append((nx, ny))
weak_visited[nx][ny] = 1
elif not flag and graph[nx][ny] == 'B' :
queue.append((nx, ny))
weak_visited[nx][ny] = 1
visited = [[0]*N for _ in range(N)]
weak_visited = [[0]*N for _ in range(N)]
for i in range(N) :
for j in range(N) :
if visited[i][j] == 0 :
bfs(i, j)
color_count += 1
if weak_visited[i][j] == 0 :
weak_bfs(i, j)
color_weakness += 1
print(color_count, color_weakness)오랜만에 간단하게 그래프 문제풀이를 했다.
BFS를 이용하여 조건만 조금 다르게해서 일반 사람이 보는 구역과 적록색약이 있는 사람이 보는 구역을 탐색하는 함수를 만들어서 구현했다.
2. Exceptional Control Flow
제어흐름 (control flow)
: 프로그램에서 실행되는 각 구문, 명령어나 함수가 호출되는 순서
1. Exception
- 제어 흐름의 갑작스런 변화
- 예상치 못한 다양한 상황 발생에 대응
- 역할
- 오류 : 오류 메세지와 함께 수행이 중단(강제종료)되도록 한다.
- 예외는 오류 메세지 상황마다 그에 맞는 처리를 할 수 있게 한다.
- 프로그래밍을 유연하게 할 수 있는 도구
2. 예외 처리(Exception Handling)
- 예외 번호 : 예외 상황의 종류마다 중복되지 않는 양의 정수로 부여 = 예외 테이블의 인덱스
- 예외 테이블 : jump table로 k번 예외상황 k에 대한 핸들러의 주소를 갖는다.
- 예외 테이블 베이스 레지스터 : 테이블의 시작주소를 저장
- Exception Handler
- 예외가 탐지되었을 때만 실행되는 일종의 서브 프로그램
- 커널(kenel) 모드에서 돌아가므로 모든 시스템 자원에 접근할 수 있다.
3. 예외 종류
- interrupt
- 외부에 있는 I/O 디바이스로부터의 시그널 결과로 비동기적으로 발생
- 하드웨어 인터럽트 : 주변 장치 등이 자신에게 발생한 사건을 운영체제 커널에게 알리는 수단
- Handler는 제어를 다음 명령이 실행될 instruction으로 넘겨준다.
- trap
- 의도적인 예외 상황으로 어떤 명령어를 실행한 결과로 발생
- 소프트웨어 인터럽트
- Handler는 제어를 다음 명령이 실행될 instruction으로 넘겨준다.
- system call
- 사용자 프로그램과 커널 사이의 인터페이스 제공
- 커널모드에서 돌아간다.
- http://www.ktword.co.kr/test/view/view.php?nav=2&no=859&sh=system+call
- fault(오류)
- 핸들러가 정정할 수 있을 가능성이 있는 에러 조건으로부터 발생
- Handler
- 에러 정정이 가능하면 오류를 발생시킨 인스트럭션으로 제어를 반환
- 불가능하면 abort 루틴으로 반환하여 응용프로그램을 종료
- abort(중단)
- 절대 응용 프로그램으로 제어를 반환하지 않는다.
4. 용어 정리
- 논리적 제어 흐름 = PC 값들의 배열
- 동시성 흐름 = 자신의 실행시간이 다른 흐름과 겹치는 논리흐름
- X가 시작해서 종료되기 전에 Y가 시작하면 동시에 돌아가는 것이다.
- multi tasking = 프로세스가 다른 프로세스들과 교대로 실행된다 = time slicing
- time slice = 프로세스가 자신의 흐름 일부를 실행하는 매 시간 주기
- 병렬 흐름 = 두 갱의 흐름이 서로 다른 프로세서 코어나 컴퓨터에서 동시에 돌아간다.
5. 문맥 전환(Context Switch)
- 커널(kernel) 모드
- ISA의 어떤 인스트럭션도 실행할 수 있으며, 시스템 내의 어떤 메모리 위치도 접근 가능
- supervisor mode
- 사용자 모드
- 특수 인스트럭션을 실행할 수 없다.
- system call을 통해서 커널 코드와 데이터에 간접적으로 접근
- 문맥 전환
- 커널이 실행할 새 프로세스를 스케줄한 후 현재 프로세스를 선점하는 것
- 새로운 프로세스로 제어 이동
3. 할당기 설계
🔗 기본 개념 정리 : https://soo-note.tistory.com/69
1. 기본 설계
- 첫번째 word = 더블 워드 경계로 정렬된 미사용 padding word
- prolog block
- Header + Footer = 8byte
- 초기화 과정에서 생성, 반환X
- 할당기가 가리키는 블록
- epilogue block
- Header로만 구성 크기 = 0 할당
- 힙이 끝나는 부분에 항상 존재
2. 매크로 정의
※ CSAPP 그림 9.43의 내용 중 정리가 필요한 것들만 적어둔다. ※
1. Block size 구하기
2. 할당 비트 확인하기
3. block pointer로 header pointer, footer pointer 구하기
4. block pointer로 next block pointer, prev block pointer 구하기
3. 함수 정의
1. mm_init
할당기는 한개의 정적 전역 변수로 사용한다.
그리고 항상 prolog block을 가리킨다.
2. coalesce
coalesce 함수는 가용 영역을 연결해주는 함수이다.
case 1 : 앞뒤 모두 할당 중일 때 → 연결 불가능
case 2 : 현재 블록의 뒤에만 가용 영역이 존재할 때 = 맨위의 그림
case 3 : 현재 블록의 앞에만 가용 영역이 존재할 때 = 가운데 그림
case 4 : 앞뒤 모두 가용 영역일 때 = 마지막 그림
※ 코드 주의 사항 ※
여기서 연결이란 Header 와 Footer를 변경해주는 것으로 표현한다.
FTRP 매크로는 HDRP 매크로를 이용하기 때문에 이를 변경해줄 때 순서가 중요하다.
🛠️ 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;
/*
* 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;
}
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;
}
/*
* first-fit 검색 수행
* 할당 받을 가용 블록이 없을 경우 NULL 반환
* 54점
*/
static void *find_fit(size_t asize) {
char *bp = (char *)heap_listp;
//epilogue 의 크기는 0이다.
while (GET_SIZE(HDRP(bp)) > 0) {
if (!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) >= asize)) {
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));
}
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);
}
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
'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글
| [TIL] CSAPP 9장 공부4 - 간단한 할당기2(Explicit, first-fit) (1) | 2023.05.15 |
|---|---|
| [TIL] CSAPP 9장 공부3 - next-fit (3) | 2023.05.14 |
| [TIL] CSAPP 9장 공부2 - 동적 메모리 할당 (1) | 2023.05.12 |
| [TIL] CSAPP 9장 공부 - 가상 메모리 개념 정리 (0) | 2023.05.11 |
| [TIL] RB Tree 구현 (with C) (0) | 2023.05.10 |
