매일 성장하는 블로그

오늘부터 PINTOS(KAIST ver.) 프로젝트를 시작했다. 핀토스를 처음 접했을 때 느끼는 점은 도대체 뭐하라는거지? 이다.

Project 1 - Threads 에서는

1. Thread들의 생성 및 관리

2. Timer Interrupt

3. Synchronization

4. Scheduling

에 대해 알아본다. 개념 - 프로젝트 진행 순서로 정리한다.

PINTOS = Pint OS

Pint OS, 즉 작은 OS라는 뜻이다. 작은 OS를 가지고 여러가지 프로젝트를 수행한다.

1. 사용법

1. /pintos 경로에서 source ./activate (로그인할때마다 해야하므로 .bashrc에 명령어를 추가하는 것이 좋다.)

2. threads 폴더 들어가서 make clean - make check를 수행하면 Test Case들에 대해서 채점을 수행한다.

3. Test Case 한가지만 돌리고 싶다면, pintos/(프로젝트명)/build에 들어가서 아래 명령어를 수행하면 된다.

pintos -T (Timout이 걸리는 시간) -- -q -run (Test case 이름)

ex) pintos -T 10 -- -q run alarm-multiple

→ alarm-multiple 이라는 test case를 수행하며, 10초 후에는 무조건 종료하라.(무한루프에 빠지는 경우를 방지할 수 있다.)

4. 수행한 결과는 threads/build/tests/threads 폴더에 들어가면 확인해볼 수 있으며, Test Case에 관한 정보/코드는 pintos/tests/threads에 있다.

threads/build/tests/threads/ 에 .output파일이 내가 짠 코드의 Test Case 결과이며, 틀렸을 경우 Expected Output과 Actual Output이 비교되어 출력된다.

2. 개념

1) Synchronization

  동기화란, 임의의 메모리 공간을 공유하는 쓰레드들이 의도한 순서대로 작업을 수행하도록 보장하는 작업이다. 한 Process 안에 있는 Thread들 간에는 Scheduler에 의해 임의적으로 Preemption(CPU를 차지하는 행위)이 발생하게 되는데, 이 과정에서 프로그램 작성자의 의도와 다르게 실행되는 경우를 방지한다. 이번 프로젝트에서는 동기화에 사용되는 5가지 방법들을 구현한다. (동기화가 필요한 이유는 아래 글을 참고)

one-step-a-day.tistory.com/122

2) Interrupts

  Interrupt란 원하는 Event가 발생했을 때 알림을 받기 위한 장치이다. Interrupt를 끄면 Preempt가 일어나지 않기 때문에 동기화가 보장된다. (non-maskable interrupt도 있다.) 하지만 Interrupt를 끄게 되면 필요한 신호들을 받지 못할 수 있기 때문에, 활용 시 주의해야 한다.

Ex ) 핸드폰의 벨소리나 진동 같은 기능이라고 생각하면 된다. 벨소리나 진동이 없다면, 우리는 전화나 메시지가 오는지 항상 핸드폰을 보고있어야 할 것이다. 벨소리나 진동이 있기 때문에 다른일을 하다가도 전화가 온 것을 인지하고 받을 수 있다.

3) Semaphore

여러 Process/Thread 사이의 Critical Region을 정상적으로 관리하기 위한 Nonnegative Integer이다. 

Semaphore의 값을 1이라고 가정하자. Critical Region에 접근할 때 Semaphore의 값을 1 감소시키고,  나올 때 1을 증가시킴으로써 Critical Region에 접근하는 쓰레드는 항상 1개 이하로 유지할 수 있다.(Semaphore의 값을 증가/감소시킬 때는 Atomic Operation을 보장하기 위하여, Interrupt를 Disable한다.)

  1. P(Down) : 양수이면, 1 줄여라.

  2. V(Up) : 1 늘려라.

* 정확히 한번 일어날 Event에 대해서는 0으로 초기화된 semaphore를 사용할 수 있다. 예를 들어 A라는 쓰레드가 있고 A 쓰레드가 B 쓰레드를 시작시키고 특정 작업이 완료되면 B가 A에게 signal을 보내길 기다린다고 하자. A는 0으로 초기화된 semaphore를 만들고 P(Down)을 수행한다. 이 때 이미 0이므로 수행하지 못하고 기다리게 되고, B에게 수행권을 넘긴다. B가 실행되었을 때, 업무를 완료한 뒤 V(up)를 실행한다. 그럼 semaphore는 1이 되고, A가 Down을 실행하여 다시 semaphore는 0이 된다. (Cond-val 수행 시 이 용도로 사용된다.)

* Semaphore를 Up하면, 마지막에 Priority에 따라 Preempt(thread_yield)를 수행할 것이다. 이 때 Interrupt handler가 sema_up 함수를 호출하는 경우를 고려해야 한다. (감이 오지 않는다면 Project3까지 꼭 기억해두기로 하자.)

관련 파일 : synch.c, synch.h

4. Locks(Mutex)

Binary Mutex를 Lock이라고 부른다. Thread 프로젝트에서는 Semaphore의 소유권을 정하기 위해 사용된다. (synch.h의 struct lock에서 정의되어 있다.)

관련 파일 : synch.c, synch.h.

5. Monitors

세마포어나 Lock보다 한층 고차원의 동기화 수단이다. 특정 조건을 충족했을 때 Thread에 signal을 보내 작업을 수행하게 할 수 있다. 이번 프로젝트에서는 Cond라는 test에서 사용된다.

* Monitor의 구성요소

1) data being syncronized

2) lock(monitor lock)

3) one or more condition variables

* Monitor 작동 순서(protected Data에 접근할 때)

1) monitor lock을 획득한다.(=모니터 안으로 들어간다.)

2) 모니터 안에 들어가게 되면, 쓰레드가 protected data에 대한 control을 갖게 된다.

3) 작업이 끝나면 monitor lock을 release한다.

Monitor의 condition variable은 access를 허용하는 조건을 control할 수 있다. '특정 데이터가 도착할 때까지' 혹은 '사용자가 최종적으로 키를 친 뒤 10초 후 ' 라던지의 조건이다. 이런 조건들이 true가 되는 조건들을 걸어놓으면, lock을 release(+1)하고 특정 조건을 만족할 때까지 기다린다. condition이 true가 되면, 특정 기다리는 쓰레드를 깨우거나 모든 쓰레드를 깨우는 등의 작업을 할 수 있다.

include/threads/synch.h.

5. Optimization Barriers

(동기화의 수단으로 어떻게 사용되는지 잘 모르겠다.)

: 사용자의 의도와 다르게 Compiler Optimization 되는 것을 막아준다. barrier()를 쓴 곳에서는 Compiler Optimization이 수행되지 않는다. 코드 곳곳에서 사용되는 것을 볼 수 있다.(pintos/devices/timer.c)

* Compiler Optimization이란?

 : 컴파일러가 코드의 내용을 파악하여 필요없는 부분을 수행하지 않거나 작업 순서를 변경하는 등의 방법으로 최적화하는 행위

6. Priority

  Thread들은 Priority(우선순위)라는 정보를 가지고 있고, 반드시 Priority가 높은 Thread가 먼저 실행되어야 한다. (만일 Priority가 높은 것이 실행되지 않는다면, 중요하지 않은 프로그램이 실행되느라 중요한 프로그램이 계속 실행되지 못하는 상황이 벌어질 수 있다.) 하지만 Semaphore나 Lock을 사용하다 보면, Priority가 낮은 프로세스가 실행되는 상황이 발생한다.

* Priority Donation

  Priority가 10인 Thread A가 Lock A를 가지고 실행되는 도중 Priority가 30인 Thread B가 생성되는 상황을 가정하자. Thread B는 생성이 완료된 후 Ready Queue에 추가되고, Priority가 Thread A보다 높으므로 실행된다. Thread B가 실행 도중 Lock A를 요청한다면 어떻게 될까?

  Thread A가 Lock을 가지고 있기 때문에, Thread A가 실행이 되고 Thread B는 Lock을 획득할 때까지 기다리게 된다. 이렇게 되면 Priority가 10인 Thread A가 Priority 30인 Thread B보다 먼저 실행이 되는 상황이 발생한다. 이런 상황을 Priority Inversion이라고 부르고, 이런 상황을 방지하기 위해 Thread B의 Priority 30을 Thread A에게 부여하게 된다. 그럼 Thread A는 Priority 30이 되므로, Priority Inversion이 일어나지 않는다. 이를 Priority Donation이라고 부른다.

프로젝트 진행

1. Alarm Clock : 

목표 : Thread를 생성한 뒤 특정 시간이 지나면 특정 작업을 수행하게 하고싶다. 기본적으로 구현되어있긴 하지만, Busy Waiting 방식을 사용하고 있어 매우 비효율적이다. timer_sleep() 등 함수를 수정하여 Busy Waiting 방식을 효율적으로 변경한다.

* Busy Waiting : Thread A가 5tick 뒤에 특정 작업을 실행하길 원한다고 하자. 매 Tick마다 Thread A가 실행되어 5tick이 되었는지를 확인하는 방법을 Busy Waiting이라고 한다.

[ 상세 설명 ] 

1) 현재 :

   1. thread_create() 함수를 사용하여 thread를 생성하며, 실행해야할 함수로 timer_sleep() 혹은 timer_sleep()의 wrapper를 전달한다.

   2. thread가 실행되며 목표한 시간이 지났는지 확인한다.

   3. 목표한 시간에 도달하지 않았으면 ready_list에 넣는다.

   4. ready_list의 맨 앞에 있는 thread를 실행한다.

thread를 여러개 생성한 뒤, 2-3-4를 반복하면서 계속 목표한 시간에 도달되었는지 확인하고, 도달하면 thread를 종료시킨다. Test Case 수행 결과를 보면 kernel ticks, idle ticks, user ticks가 있는데 의미하는 바는 아래와 같다.

kernel ticks : kernel thread들이 수행되는데 걸리는 시간

idle ticks : idle thread가 수행되는데 걸리는 시간

user ticks : 사용자 프로그램이 수행되는데 걸리는 시간

Busy Waiting으로 구현되어있기 때문에, 모든 thread들이 종료될 때까지 idle thread는 수행되지 않는다. (user ticks는 현재 보지 않아도 된다.) 따라서, Busy Waiting으로 수행하면 아래와 같은 결과를 얻을 수 있다.

idle ticks : 0, kernel ticks : 800, user ticks : 0 

2) 목표 : 

   1. Sleep List를 만든다.

   2. thread_create()함수를 사용하여 thread를 생성하며, 실행해야할 함수로 timer_sleep() 혹은 timer_sleep()의 wrapper를 전달한다.

   3. thread가 time_sleep 함수를 실행하며 목표한 시간이 지났는지 확인한다.

   4. 목표한 시간이 지나지 않았으면 sleep_list에 추가한다.

   5. Sleep List에 있는 Thread들의 최소 Wakeup Tick을 전역변수에 저장한다.

   5. timer interrupt(매 tick마다 발생)마다 최소 Wakeup Tick보다 작은지 확인한다.

   6. 목표한 시간에 도달하면, sleep list에서 해당 thread를 제거하고, ready_list에 추가한다.

   7. ready_list에 추가된 thread는, 자신의 차례가 되면 실행되고 종료된다.

위와 같이 실행하면, 목표한 시간에 도달하지 못한 thread들은 모두 sleep_list에서 실행되지 않고 자고 있다. 따라서 idle_thread가 실행되며 아래와 같은 결과를 얻을 수 있다.(결과는 조금씩 다를 수 있다.)

idle ticks : 500, kernel ticks : 300, user ticks : 0 

2. Priority Scheduling

목표 :

   1. 현재는 thread들이 생성되면 ready_list의 맨 뒤에 넣고 순차적으로 실행된다. 하지만 thread에는 priority라는 우선순위를 나타내는 변수가 있다. 우선순위가 높은 것들이 먼저 실행되도록 관련 함수들을 변경한다.

   2. Semaphore와 Lock을 사용하여, Critical Region에서 Atomic Operation이 일어남을 보장한다.

   + Critical Region에 여러개의 쓰레드가 동시에 접근할 때, 하나의 작업이 종료되기 전에 다른작업이 시작되면 데이터가 이상해질 수 있다. 따라서 Critical Region에서 작업하는 Thread에게는 Lock의 소유권을 부여하고, Lock을 소유하지 못한 Thread들은 Lock의 소유권이 풀릴 때까지 Waiters에서 기다린다.  

   3. 2번의 상황에서 Priority가 높은 Thread가 Priority보다 낮은 Thread가 먼저 수행되는 것을 막기 위해, Priority Donation 이라는 개념을 적용한다.

3. Cond Var(Monitors)

   1. Monitor 구조를 활용한다.

4. Multi Level Feedback Queue Scheduler

   1. Priority Donation만으로는 Starvation 등의 문제를 해결하지 못한다. recent_cpu, load_average 등의 변수를 활용하여 Priority를 유동적으로 변경해주는 Multi Level Feedback Queue Scheduler를 적용한다.

후기

OS의 맛을 볼 수 있는 재미있는 프로젝트였다. 앞으로 훨씬 더 어려워질 것 같아 걱정이지만 열심히 공부하고 정리해야겠다.

Debugging은 gdb보단 printf와 뇌버깅이 훨씬 더 편한것같다..

가상 메모리, Heap, 동적 할당기, Malloc Lab 과제에 대한 글입니다.

1. Virtual Memory

  메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상메모리라고 알려진 메인 메모리의 추상화를 제공한다. 가상 메모리는 각 프로세스에 하나의 크고 통합된, 사적 주소공간을 제공하며, 기능을 크게 세 가지로 요약할 수 있다.

1) 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급한다.

2) 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.

3) 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.

2. Heap

  프로세스는 Stack, Heap, bss, data, text로 메모리 공간을 나눠놓고 사용하는데, Heap이라는 영역은 사용자가 필요에 따라 원하는 메모리 Block을 요청하고, 반환할 수 있다. Heap 영역은 일반적으로 낮은 주소에서 높은 주소로 자란다.

3. 동적 할당기 (Memory Allocator)

: 프로그램을 실행시키기 전에 자료구조의 크기를 알 수 없는 경우가 있기 때문에 동적 할당을 사용하는데, Heap 영역을 관리하는 도구를 동적 메모리 할당기라고 부른다. 할당기에는 두 가지 종류가 있다.

1) 명시적 할당기 : 명시적으로 malloc을 통해 공간을 할당하고, free를 통해 공간을 반환해야 하는 방식의 할당기. 즉, 사용자가 직접 공간을 할당하고 반환하는 작업을 명시적으로 해줘야 한다.

2) 묵시적 할당기 : 사용자가 할당한 메모리 Blcok들에 대하여, 더 이상 프로그램에 의해 사용되지 않는 Block을 검출하여 반환시켜주는 작업을 수행하는 할당기. 가비지 컬렉터라고 부르며, Block을 반환하는 작업을 가비지 컬렉션이라고 부른다.

* 명시적 할당기 예시 - C의 표준 라이브러리 : Malloc

  사용자가 요청한 크기의 빈 Block을 찾고, 포인터를 return한다. 32bit 시스템은 8의 배수, 64비트 시스템은 16의 배수로 align된 주소값을 return한다. 사용 가능한 메모리보다 큰 Block을 요청하는 경우 null을 return하고, 성공적으로 메모리 Block을 return하는 경우에도 메모리 블럭의 내용을 초기화하지는 않는다. 이를 원한다면 할당된 메모리를 0으로 초기화하는 calloc을 사용할 수 있다. 이미 할당된 메모리 Block의 크기를 변경하고자 한다면 realloc을 사용한다.

명시적 할당기의 구현

  명시적 할당기를 구현하는 과정이 Malloc Lab의 과제였다. 메모리 할당 과정은 아래와 같은 함수들로 구성된다. (Block에 관한 자세한 설명은 맨 아래 참조)

mem_sbrk() : Heap 전체 사이즈를 늘린다. 요청된 메모리 Block을 만족하는 빈 공간이 없을 때 호출된다.

find_fit() : 허용된 Heap 영역 내에서, 요청된 메모리 Block Size를 만족하는 빈 공간이 있는지 찾는다.

coalesce() : 빈 공간이 연속적으로 있다면, 합친다.

malloc() : 메모리 공간을 할당하기 위해 호출된다.

free() : 메모리 공간을 반환한다.

동적 할당은 아래와 같은 과정으로 이루어진다.

1) Heap을 초기 사이즈인 CHUNK_SIZE(ex : 4KB)로 생성한다.

2) 사용자의 요청에 따라 Heap 내에 공간을 할당한다.

3) 할당된 Heap 내에 더이상 할당할 공간이 없다면, CHUNK_SIZE 단위로 Heap을 증가시킨다.

실제로 구현하는 방법은 아래와 같이 구조/기능에 따라 다양하다.

[ 구조 ]

1) 묵시적 가용 리스트(Implicit Free List) : Allocated Block, Free Block이 할당된 채로 아무것도 하지 않은 구조. Header/Footer를 확인하며 순차적으로 검색한다.

2) 명시적 가용 리스트(Explicit Free List) : Free Block들만 연결 List로 연결한 뒤, Free List에서 요청한 크기를 만족하는 Free Block을 찾는다. 이 때 Free Block에 연결 List를 구성하기 위한 추가 데이터를 넣는다. 어짜피 비어있는 공간이라 메모리 낭비는 발생하지 않는다.

3) 분리 가용 리스트(Segregated Free List) : Free List를 크기 별로 관리한다. 크기를 관리하는 방법은 다양하다. 특정 크기가 들어왔을 때 해당 크기가 포함된 범위의 Free List만 살펴보면 되므로 검색 시간이 단축될 수 있다.

[ 기능 ]

1) First Fit : 처음부터 끝까지 순차적으로 검색하며 조건을 만족하는 Block을 바로 return한다.

2) Next Fit : 가장 최근에 할당된 Block을 기록해놓은 뒤, 그 다음 것 부터 찾는다.

3) Best Fit : 모든 공간을 검색해본 뒤, 가장 가까운 크기를 갖는 Block을 return한다.

할당기의 성능

할당기의 성능은 아래와 같이 측정할 수 있다.

할당된 공간 / 전체 Heap Size

위의 값이 클수록, 단편화(Fragmentation)가 적게 일어나서 메모리가 효율적으로 사용된 것이다.

(단편화에 관한 자세한 설명은 맨 아래 참조)

* 묵시적 할당기 예시 : 가비지 컬렉터

아래와 같은 경우 가비지(사용자가 메모리 Block을 동적 할당해놓고 반환하지 않는 경우)가 발생한다.

  이런 가비지들을 Free하기 위해서, 다양한 방법들이 있지만 가장 기초적인 Mark & Sweep 방법을 소개한다. 아래 그림과 같이 루트 노드들과 힙 노드들로 이루어진 방향성 도달 그래프로 메모리 참조 관계를 나타낸다. 각 힙 노드는 하나의 할당된 Block을 나타내며, 어떤 루트 노드에서도 특정 힙 노드 p로 향하는 경로가 없다면, p는 가비지로 인식된다.

Mark : 루트 노드들의 도달 가능하며 할당된 하위노드들을 표시하는 행위

Sweep : 표시되지 않은 블록을 반환하는 행위

  어떤 가비지 컬렉터는 별도의 쓰레드로서 실행되어 그래프를 관리하며 가비지를 회수하기도 하고, 어떤 가비지 컬렉터는 가용 블럭이 더이상 없을 때 호출되어 찾기도 한다. 후자를 보수적인 가비지 컬렉터라고 한다. 

* Segmentation Fault : 페이지 테이블에는 허가 비트라는 것이 있어서 가상 페이지 내용으로의 접근을 제어하는데, 어떤 인스트럭션이 이 허가사항을 위반할 경우 Fault를 발생시키며, 이것이 Segmentation Fault이다.

* Stack Buffer Overflow : 버퍼의 사이즈를 할당해놓고 입력을 받을 때, 입력의 사이즈가 버퍼의 크기를 넘어가는 경우 발생한다. fgets를 사용하여 입력 사이즈를 제한하여 해결한다.

* Block과 Free Block, Allocated Block

  이 글에서 명시하는 Block은 Heap 영역 내에 쪼개진 하나의 저장 공간을 의미한다. Allocated Block은 사용자가 명시적으로 할당을 요청한 Block이고, Free Block은 Allocated되지 않은 Block이다. 우선 하나의 Block은 어떤 구조를 갖는지 살펴보자.

  Block은 아래와 같은 구조를 갖는다. 맨 앞, 맨 뒤에 있는 식별자인 Header, Footer는 Free 시에 활용된다. 예를 들어 Allocated Block을 Free시킨다고 하자. 해당 Block을 Free시키는 것은 문제가 없지만, 외부 단편화와 내부 단편화를 막기 위해 앞뒤로 Free Block이 있는 경우 합치는 작업(Coalesce)을 진행해야 한다. 이 때 앞뒤에 있는 Block의 할당 여부, 크기를 알기 위해서 사용되는 것이 Header와 Footer이다.

* Header : 크기와 할당 여부를 나타내는 1Word 크기의 식별자

* Payload :  사용자가 할당을 요청한 데이터 영역. Malloc의 경우 해당 영역을 초기화하지 않는다.

* Footer : 크기와 할당 여부를 나타내는 1Word 크기의 식별자

* 외부 단편화(External Fragmentation) : 사용자가 요청한 메모리 할당을 위한 Free Space는 충분하지만, 연속적이지 않아 메모리 할당이 불가능한 경우. 아래와 같이 Free Space(흰색)와 Allocated Space(회색)가 있고, 사용자가 50KB의 메모리 공간 할당을 요청했다고 하자. 전체 Free Space의 합은 55KB로 요청한 메모리 할당을 위한 공간이 충분하지만, 연속적이지 않아 할당이 불가능하여 Heap 영역을 늘려야 한다. (이 때, 임의로 Assigned Block을 이동시켜 Free Block들을 합치는건 불가능하다.)

* 내부 단편화(Internal Fragmentation) : 할당기의 규칙에 의해 할당한 메모리 공간에서 실제로 사용되는 공간이 작은 경우 발생한다. 아래와 같이 Assigned Space보다 Used Space가 작을 때 발생한다. Padding이나 메모리 할당 방식의 차이에 따라 발생한다.

1. B-Tree의 정의

  B-Tree란 디스크 등의 보조기억장치에서 데이터를 검색하는데 시간을 최소화하기 위하여 고안된 자료구조이다.

2. B-Tree를 사용하는 이유

  특정 Data를 CPU에서 사용하기 위해서는, 원하는 데이터를 디스크에서 찾은 뒤 메인 메모리에 올려야 한다. 원하는 데이터를 찾기 위해서는 특정 데이터를 메인 메모리에 올린 후 원하는 데이터인지 비교함으로써 알 수 있는데, B-Tree를 사용하면 이 비교하는 횟수를 작게할 수 있다.

  임의의 Tree에서, 하나의 노드가 가진 데이터의 크기가 메모리의 크기와 동일하다고 하자. 원하는 데이터를 찾기 위해서는, 하나의 노드에 접근할 때마다 노드가 가진 데이터를 메인 메모리에 올려서 찾는 데이터가 맞는지 확인하는 과정이 필요하다. 트리의 높이가 낮을수록 비교하는 연산이 줄어들게 되며, B-Tree의 높이 h는 다음과 같이 정의된다.(t : 최소 차수, 뒤에서 추가 설명)

3. B-Tree의 정의

  B-Tree를 구현하는 방법은 다양하다. 여기서는 Introductions to Algorithms에서 정의하는 방식을 사용한다. (최대차수는 짝수만 가능하다.) 모든 노드는 KEY와 CHILD이라는 구성요소를 가진다. KEY는 트리 안에서 찾아야 하는 값이며, CHILD은 자식 노드를 가리키는 포인터이다.

1. B-Tree의 모든 노드는 아래와 같은 정의를 가진다.

  1) 모든 노드는 포함할 수 있는 KEY의 개수의 범위가 정해져 있다. 범위를 정하는 숫자 t를 최소 차수라고 하며, 최소 차수는 2 이상의 정수이다. 특정 노드의 KEY의 개수가 x개라면, CHILD의 개수는 x+1개이다.

  2) 루트를 제외한 모든 노드는 t-1 개 이상의 KEY를 가진다.(최소 KEY의 개수)

  3) 루트를 제외한 모든 노드는 t개 이상의 CHILD를 가진다.(최소 CHILD의 개수)

  4) 리프는 CHILD을 가지지 않는다.

  5) 모든 노드의 최대 KEY의 개수는 2t-1개이며, 최대 CHILD의 개수는 2t이다.(이 때 가득 차 있다고 표현한다.)

  6) 노드 내의 KEY는 정렬되어 있다.

  7) 특정 키 X의 왼쪽 CHILD에는 X보다 작은 KEY 값들만 존재하며, 오른쪽 CHILD에는 큰 KEY 값들만 존재한다.

이를 만족하는 최소 트리(t=2)는 아래와 같다.

다음 포스팅에서 B-Tree를 구현해본다.

12월 7일.

4년간 몸담았던 회사의 마지막 출근일이자 SW사관학교 정글 입소일.

  인수인계, 이사, 인간관계 정리를 하다보니 눈깜짝할새에 3주가 지나가버렸고, 새로운 시작을 위한 첫 발걸음을 떼는 날이 다가왔다. 회사 생활을 하며 불만이 많았지만, 마지막 퇴근 때 눈물이 찔끔 났던걸 생각해보면 미운 정이 들었나보다. 막상 모든걸 새롭게 시작하려니 살짝 두렵기도 한 지금, 초심을 잃지 않고자 내 각오를 적어본다.

  지나온 삶을 돌아보면, 언제나 안정적인 길을 그럭저럭 잘 걸어왔던 것 같다. 정규 교육을 이수하고 대학교에 진학하여, 졸업 뒤 취직. 이대로 안정적인 길을 가다보면 회사에서 퇴직을 했을테고, 퇴직 후에도 삶에 대해 고뇌했겠지만 가족들과의 행복을 위안삼으며 여생을 살았을 것 같다. 하지만 나는 늘 안정적인 길을 걸어오면서 의문이 가득했다. '나는 뭘 좋아하지?', '이렇게 사는 것이 행복한 것인가?' 같은 것들이다. 물론 요즘은 잊고 사는게 더 나은 질문들도 있다고 생각하지만, 이런 질문들에 대한 고뇌가 나를 여기로 이끌었음을 부정할 수 없다.

  지금까지 파악한 나의 지향점은 '기술을 통해 세상의 좋은 변화에 기여하는 사람'이다. (이 간절함이 극에 달하면 창업의 길로 뛰어들겠지만, 내가 그 지경까지 도달할 수 있을지는 의문이 든다.) 어떻게 목표를 이룰 수 있을까 고민하다가, '더 많은 기여를 하려면 뛰어난 사람이 되어야 하고, 뛰어난 사람이 되려면 열심히 일을 통해 배워야 하며, 열심히 하려면 자기가 좋아하는 일이여야 한다.' 라는 생각이 들어 회사를 뛰쳐나왔다.

  시작으로부터 일주일이 지난 지금, 밤이라도 새서 했어야 할 과제들을 조금씩 미루고 있는 내 자신을 보며 의구심이 드는 것도 사실이다. 하지만 믿어야 한다. 나를 믿고 조금 더 채찍질하며 남은 기간동안 열심히 달려서, SW 엔지니어로서 훌륭한 소프트 랜딩을 할 것이다. 열심히 하고 난 이후의 일은 그때 가서 생각하고, 우선 내 인생을 바꿀 수 있는 17주가 내 앞에 주어졌다. 열심히 달려서 5개월 뒤에 축배를 들 수 있기를.