728x90
728x90
[ 시스템 & 인프라/PintOS & CS ][CS:APP/C언어] Malloc Lab 사전 지식: 힙, 가용 리스트, 병합, 파편화2024-04-15 00:57:27TL;DR (세 줄 요약)Malloc Lab은 malloc, free, realloc을 직접 구현하는 과제입니다. 이 글은 구현을 시작하기 전에 알아야 하는 사전 지식을 정리합니다.힙은 sbrk로 늘립니다. 블록마다 크기와 사용 여부를 적은 헤더를 두고, 비어 있는 블록(가용 블록)은 리스트로 관리합니다. 할당 정책(First Fit, Best Fit 등)과 병합(Coalescing)이 파편화와 처리 속도에 영향을 줍니다.과제는 사용률(힙을 얼마나 낭비 없이 썼는가)과 처리량(1초에 요청을 몇 번 처리했는가)을 함께 봅니다. 두 값은 한쪽을 올리면 다른 쪽이 내려가기 쉬우므로 둘을 함께 확인해야 합니다.이 글은 크래프톤 정글 4기에서 Malloc Lab을 구현하기 전에 정리한 사전 지식입니다. Mallo..
[ 시스템 & 인프라/PintOS & CS ][PintOS/운영체제] Project 1 Threads 개념 정리: 스케줄링·동기화·MLFQS2024-03-17 23:56:26TL;DR (세 줄 요약)PintOS Project 1 Threads 과제를 하려면 프로세스와 스레드, CPU 스케줄링, 동기화, 경쟁 상태, 교착 상태, 문맥 교환, MLFQS를 설명할 수 있어야 합니다.CPU 코어 하나는 한 번에 작업 하나만 실행합니다. 그래서 운영체제는 스케줄러로 실행 순서를 정하고, 락과 세마포어로 공유 데이터에 접근하는 순서를 지키게 하고, 작업을 바꿀 때 문맥을 저장하고 복원합니다.각 개념을 정의, 원인, 대표 방법 순서로 정리하면 Alarm Clock, Priority Scheduling, MLFQS 구현이 무엇을 요구하는지 알 수 있습니다.이 글은 크래프톤 정글에서 KAIST PintOS를 팀 프로젝트로 구현하면서 정리한 기록입니다. 정글에서 제공한 가이드라인의 공부 키워..
[ 42경산 & 알고리즘/자료구조 & 코테 ][자료구조/C언어] 레드-블랙 트리(Red-Black Tree) 규칙·회전·삽입·삭제 정리2024-02-18 23:57:24TL;DR (세 줄 요약)레드-블랙 트리는 노드마다 빨강 또는 검정 색을 붙이고, 색에 대한 다섯 가지 규칙을 지키는 이진 탐색 트리입니다.이 규칙 덕분에 트리의 높이가 log n 수준으로 유지됩니다. 그래서 탐색, 삽입, 삭제가 최악의 경우에도 O(log n) 시간에 끝납니다.삽입이나 삭제로 규칙이 깨지면 색을 바꾸거나(재색칠) 회전으로 구조를 바꿔서 고칩니다. 삽입은 삼촌 노드의 색을, 삭제는 형제 노드의 색을 보고 처리 방법을 고릅니다.이 글은 크래프톤 정글 4기 Part 2 "탐험 준비" 4주차에 레드-블랙 트리를 공부하면서 정리한 기본 개념입니다. 먼저 알아야 하는 개념, 다섯 가지 규칙, 회전, 삽입, 삭제 순서로 설명합니다.1. 레드-블랙 트리는 무엇인가요?레드-블랙 트리(Red-Black ..
728x90
728x90