WOONY's 인사이트

malloc 주차가 끝나고, 이제 OS 전 마지막 준비 단계인 주차에 들어섰다. 간만에 밀린 운동도 해서 기분은 좋으나 매우 피곤한 관계로, 빠르게 정리하고 집에 갈 예정. 인터넷 네트워크 인터넷 통신 클라이언트와 서버는 어떻게 통신할까? 중간에 인터넷이라는 놈이 둘 사이를 연결해준다. 그러면 이 인터넷은 어떻게 구성되어 있는 걸까? 인터넷은 수많은 서버 노드의 집합이라고 생각하면 된다. IP(인터넷 프로토콜) 클라이언트와 서버는 무작정 소통하는 게 아니다. 둘 사이에는 일종의 전송 규칙을 설정해 통신하는데, 이때 정하는 규칙을 IP(인터넷 프로토콜)이라고 한다. IP의 역할은 크게 두 가지이다. IP address를 통해 데이터를 전달 패킷 형태로 데이터를 전송 IP는 일종의 통신 규약이라고 했다. I..

어제 떡하니 코드만 달랑 올려놓고 말아서 많은 분들이 실망했을 것으로 아는 바, 오늘은 디테일하게 Explicit 방식에 대해 정리하고 코드까지 리뷰하는 것으로 TIL 정리를 해보겠다. 정리를 하기 전에, 동적 메모리 할당 이전에 나오는 개념인 시스템 콜에 대해 간단히 정리하고 넘어간다. 시스템 콜 시스템 콜: OS(특히 커널)이 제공하는 서비스에 접근하기 위한 상호작용을 말한다. 커널(kernel): 메모리에 상주하고 있는 운영체제 핵심 중 일부를 뜻한다. 응용프로그램이 컴퓨터 시스템에서 수행되기 위해서는 메모리에 프로그램이 올라가 있어야 한다. 운영체제 역시 하나의 프로그램으로, 메모리에 올라가야 하는데 OS는 무겁기 때문에 필요한 핵심만 메모리에 올라간다. 이때, 메모리에 상주해 있는 OS의 일부를..

디테일한 설명은 내일...(올릴 수 있기를..) /* * mm-naive.c - The fastest, least memory-efficient malloc package. * * In this naive approach, a block is allocated by simply incrementing * the brk pointer. A block is pure payload. There are no headers or * footers. Blocks are never coalesced or reused. Realloc is * implemented directly using mm_malloc and mm_free. * * NOTE TO STUDENTS: Replace this header comment..

지난 포스팅에 이어서 진행. 정글사관학교 40일차 TIL: 동적 메모리 할당(malloc), 힙 단편화(fragmentation) malloc: Dynamic memory allocation(동적 메모리 할당) Dynamic Memory Allocator 우리는 왜 동적 메모리 할당을 이용할까? C언어에서는 배열을 만들 때, 반드시 그 사이즈를 미리 선언해줘야 한다. 예컨대 2학년.. woonys.tistory.com 이번에는 가장 기본으로 구현하는 Implicit free list(묵시적 가용 리스트)부터 정리해본다. 번역한 단어가 영 입에 감기지 않아 여기서는 implicit이라고 부르겠다. Implicit free list(묵시적 가용 리스트) allocator는 블록 간 경계를 구분하고 할당된 블..

오늘은 밖에서 오래 있느라 제대로 정리를 못했..알고리즘 문제 푼 걸 정리하고 빠르게 마무리. 문제 링크는 여기. 연결 리스트 개념은 잘 안다고 생각했는데 파이썬 클래스로 구현하는 방식이 손에 잘 익지 않더라. 클래스에서 어떻게 구현했는지 빠르게 보자. 주어진 연결리스트 클래스를 구현하는 ListNode는 클래스를 구성하는 원소가 두 가지인데, val과 next이다. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next 연결 리스트에서 해당 노드의 값을 val, 다음 연결 리스트를 next에 저장한다. 이때, self.next에 들어가는 것은 다음 노드의 값이 아니라 현재 연결 리스트의 노드 헤드를 제외한..

malloc: Dynamic memory allocation(동적 메모리 할당) Dynamic Memory Allocator 우리는 왜 동적 메모리 할당을 이용할까? C언어에서는 배열을 만들 때, 반드시 그 사이즈를 미리 선언해줘야 한다. 예컨대 2학년 3반 학생 수가 32명인데 이를 배열로 담는다고 하자. 그러면 정확히 size = 32라고 선언해줘야 한다. 그런데 2학년 모든 반에 대해 각각 배열을 만들어준다고 하면, 우리는 각 반 학생 수에 맞게 일일이 배열을 선언해줘야 한다. 이는 굉장히 비효율적이다. 일일이 타자를 치고 있는 상황을 생각해보라. 이런 낭비를 막기 위해, 학년 별 학생 수를 담고 있는 배열에서 숫자를 받아와 그 학생 수만큼 배열을 자체적으로 그때그때 생성할 수 있다면 프로그래머가 ..

대망의 RB트리 주차가 끝나고 malloc 함수 구현 과제 주차에 들어섰다. (현재 6주차) 어제는 시원하게 블로그 TIL을 건너뛰었다. (그래도 github에 저번 주차에서 배운 것들을 정리했다! BST 먼저 정리하고 이번주 주말에 가능하면 RB트리 readme를 작성할 예정.) 시원하게 쉬었으니 오늘부터 다시 달립시다. malloc 개념은 CSAPP 책 9.9 장에 나온다. 그 전에 9장 전반적으로 정리를 할 필요가 있어 가장 큰 개념인 가상 메모리부터 정리. 가상 메모리(virtual memory) 가상 메모리를 쓰는 이유는 메모리를 더욱 효율적으로 & 더 적은 에러로 관리하기 위해서이다. 이와 관련해 아주 재밌게 설명한 영상이 있어 공유. 예를 들어, 어떤 식당이 있다고 하자. 이 식당은 예약제로..

지금 시간은 3시 3분..자그마치 6명의 집단 지성이 힘을 합쳐 겨우 디버깅을 완료하고 모든 테스트 케이스 통과!! 삭제 기능에 대해 빠르게 로직 정리하고 집 가야겠다.. 삭제(Deletion) 옮기거나 삭제하는 노드의 원래 색을 기억해뒀다가 옮기거나 지우려는 노드 색이 검정인 경우에만(=이중 흑색 노드) 트리를 고친다. 지우려는 노드 z 혹은 옮기려는 노드가 빨간색이면 rb트리 특성을 위반하지 않으니 고칠 필요가 없다. 지우려나 옮기려는 노드가 검정일 때는 경로 상의 검정 노드 개수가 변하므로 트리 특성을 위반한다. 이 경우에는 fixup 함수로 수정한다. 삭제 기능은 세 가지 케이스로 나눠서 구현한다. 1. 삭제하려는 노드(=z)의 왼쪽 자식만 있는 경우 (=오른쪽 자식이 NIL인 경우) 이때는 왼쪽..

요 며칠간 끊임없이 고통을 안겨줬던 레드블랙 트리(이하 RB트리)..그래도 계속 보다 보니까 얼추 감이 잡히기 시작한다. 아직 가장 큰 관문인 삭제가 남아있지만 그래도 삽입 구현 완료! RB트리 개념부터 시작해서 삽입까지 빠르게 정리하고 마무리할 예정. 오늘 풀었던 알고리즘 문제는 따로 포스팅해야겠다. Red-Black Tree(레드블랙 트리) 1. RB트리 정의 rb트리는 균형 이진 탐색 트리의 여러 버전 중 하나이다. 균형 이진 탐색 트리란, 이진 탐색 트리에 노드를 삽입/삭제하는 과정에서 어느 한 쪽으로 노드가 쏠리는 것을 방지하기 위해 규칙을 추가한 심화 버전 이진 탐색 트리라고 보면 되겠다. 왜 이런 짓을 하냐? 이진 탐색 트리를 만드는 이유는 특정 노드를 검색하는데 드는 시간 복잡도가 O(lo..

RB트리를 구현하기 전에 개념을 익힐 겸 연결 리스트로 이진 트리를 구현하는 연습(by C)을 진행한다. 공부자료는 이것을 참조함. 이진트리 with 연결리스트 1. 이진탐색트리(Binary Search Tree, BST)란? 원소를 특정한 조건에 따라 정렬해 놓은 이진 트리를 말한다. 2. 이진탐색트리 특징 모든 원소는 유일한 키값을 갖는다. (중복 내용을 갖는 항목은 없다.) 왼쪽 서브트리의 모든 원소들은 루트의 key보다 작은 값을 갖는다. 오른쪽 서브트리의 모든 원소들은 루트의 key보다 큰 값을 갖는다. 왼쪽/오른쪽 서브트리 역시 이진 탐색 트리이다.(재귀적으로 정의된다.) 3. 이진탐색트리에서 탐색 시 시간 복잡도 이진탐색트리에서 특정한 키값을 찾을 때, 그 값이 비교하려는 노드의 값보다 크면..