매일 성장하는 블로그

오늘부터 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와 뇌버깅이 훨씬 더 편한것같다..

www.freitag.ch/en

  아이패드 11을 구매하였는데 15만원짜리 연필을 달랑달랑 붙이고 다니자니 불안해서 케이스를 구매했다. 늘 좋아하는 프라이탁의 노트북 12/13인치용 슬리브이다. 매장가서 살까 생각도 했지만 시간도 없고 코로나라 돌아다니기도 무서워서 온라인으로 구매하기로 마음을 먹었다.

  FREITAG의 장점이자 단점인 '유일한 Design'때문에, 마음에 드는 디자인의 제품이 공홈에 뜨기를 계속 기다렸지만 찾을 수 없었다. 그러던 와중 freshlabels.com이라는 사이트에서 마음에 드는 디자인을 찾아 구매하게 되었다. freshlabels는 유럽의 유명한 편집숍인것 같다.

  처음에는 유럽 배송대행지를 찾아보고자 검색하다가 유럽위크를 찾았다. 배송대행과 구매대행을 하는데, 구매대행을 해도 수수료가 붙지 않는다는 말에 덜컥 구매대행을 신청해버렸다. 1월 7일날 구매를 신청하였고, 1월 22일에 독일 유럽위크 배대지에 도착하여 한국으로 발송된 것을 확인하였다. 2주간의 시간이었지만 굉장히 길게 느껴졌다.(freshlabels에서 구매 신청을 하면 confirm letter를 받고 최종적으로 물품을 받는데 시간이 꽤 걸리는 것 같다.) 이제 한국으로 오는 중이니 기다리기만 하면 된다.

  가격은 공홈에서 구매 가격이 약 13만원인데 유럽위크에서 구매 및 배송 대행까지 하는데 약 12만원이 들었다. 프라이탁 공홈에서 주문하면 월요일날 주문해도 금요일 안에 거의 무조건 도착하니, 마음에 드는 디자인의 제품이 공홈에 있고 만원 정도의 차이는 괜찮다면 공홈에서 구매하는 게 좋을 것 같다.(프라이탁 공홈 주문 시 2일만에 도착해서 깜짝 놀란 적도 있었다.) 유럽위크 사용 시 전반적인 느낌은 좋았고, 수수료가 매우 싸다는 느낌을 받았다. 끝-!

europeweek.co.kr/

프로세스 : 운영체제로부터 자원을 할당받은 작업의 단위

쓰레드 : 프로세스가 할당받은 자원을 이용하는 실행 흐름의 단위.

쓰레드를 사용하는 이유 : 동시성을 보장하기 위해 사용한다. 예를 들어 서버를 생성한다고 하자. 하나의 프로세스로 구성된 서버는 한번에 한명의 클라이언트의 요청밖에 처리할 수 없다. 여러 개의 프로세스로 구동되는 서버를 사용할 수도 있지만, 프로세스는 개별 공간이 크고, Context Switching에도 시간이 오래 걸린다.(프로세스의 Context 스위칭 시, CPU 레지스터, RAM과 CPU 사이의 캐시 메모리까지 초기화된다. 쓰레드의 경우 개별 컨텍스트만 Switching 해주면 된다.)

기본적으로 하나의 프로세스는 하나의 쓰레드를 가지고 생성되며, 생성된 프로세스 안에서 쓰레드를 추가하면 멀티쓰레딩이라고 한다. 멀티쓰레드는 한개 프로세스의 컨텍스트 안에서 돌아간다. 각각 쓰레드는 자신만의 별도의 쓰레드 컨텍스트를 가지며, 쓰레드 ID, 스택, 스택 포인터, 프로그램 카운터, 조건 코드, 범용 레지스터 값들이 포함된다. 나머지 자원은 다른 쓰레드와 공유한다.(만일 A 쓰레드가 B 쓰레드의 스택을 가리키는 포인터를 획득한다면, 해당 포인터를 활용하여 다른 쓰레드의 스택데이터를 조작하는게 가능하다.)

1. Stack : 프로그램 실행 과정에서 생성되는 지역변수, 주소값 등을 저장하는 공간(순차적으로 주소가 낮아지는 방향으로 쌓임)

2. Heap : 동적으로 할당되는 메모리 공간 (By malloc ...)

3. Static : 1) Data : 초기화된 전역변수가 저장된다. 

            2) BSS : 초기화되지 않은 전역변수가 저장된다.

4. Code : 프로그램 실행 코드

쓰레드의 장점 : 다수의 쓰레드가 같은 프로그램의 변수들을 공유하기 쉽다.

쓰레드의 단점 :

1. 쓰레드 간의 동기화 문제가 발생한다. A 스레드가 어떤 자원을 사용하다가, B스레드로 제어권이 넘어간 후, B 스레드가 해당 자원을 수정했을 때, 다시 제어권을 받은 A스레드가 해당 자원에 접근하지 못하거나 바뀐 자원에 접근하게 되는 문제가 발생할 수 있다. 

2. 멀티프로세싱은 운영체제의 스케쥴러가 관장하는 반면, 멀티스레드는 운영체제가 처리하지 않기 때문에 프로그래머가 직접 동기화 문제에 대응할 수 있어야 한다. --> 일반적으로, 운영체제가 여러분의 쓰레드를 위해서 정확한 순서를 선택하게 될지 예측하는 방법은 없다.

3. 디버깅이 까다롭다.

4. 하나의 쓰레드에 문제가 발생하면 전체 프로세스가 영향을 받는다.

한 프로세스 내에서 쓰레드간 공유하는 공간은 반드시 관리되어야 한다. 하나의 쓰레드가 수정하는 경우 다른 쓰레드는 잠시 대기해야 한다. 이런 공간을 Critical Region이라고 하고, 해당 영역을 관리하기 위해 사용하는 키를 Mutex라고 한다.(Mutex는 1과 0의 값만을 가지는 Binary Mutex이다.)

아래의 예시를 보자. (공유된 메모리에 대한 잘못된 접근의 예시 : 출처 : CSAPP)

[ badcnt.c ]

0. niters라는 변수를 입력받는다.

1. cnt=0 라는 전역변수를 선언하고, thread()함수를 실행하는 쓰레드를 2개 생성한다.

 thread 함수 : niters만큼 cnt를 증가시킨다.

프로그램의 의도 : 프로세스를 두개 생성한 뒤 전역변수 cnt를 niters만큼씩 증가시킨다.

/* 
 * badcnt.c - An improperly synchronized counter program 
 */
/* $begin badcnt */
/* WARNING: This code is buggy! */
#include "csapp.h"

void *thread(void *vargp);  /* Thread routine prototype */

/* Global shared variable */
volatile long cnt = 0; /* Counter */

int main(int argc, char **argv) 
{
    long niters;
    pthread_t tid1, tid2;

    /* Check input argument */
    if (argc != 2) { 
	printf("usage: %s <niters>\n", argv[0]);
	exit(0);
    }
    niters = atoi(argv[1]);

    /* Create threads and wait for them to finish */
    pthread_create(&tid1, NULL, thread, &niters);
    pthread_create(&tid2, NULL, thread, &niters);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);

    /* Check result */
    if (cnt != (2 * niters))
	printf("BOOM! cnt=%ld\n", cnt);
    else
	printf("OK cnt=%ld\n", cnt);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp) 
{
    long i, niters = *((long *)vargp);

    for (i = 0; i < niters; i++) //line:conc:badcnt:beginloop
	cnt++;                   //line:conc:badcnt:endloop

    return NULL;
}
/* $end badcnt */

하지만 실제로 프로그램을 실행해보면, 아래와 같이 의도치 않은 결과가 나오는 것을 볼 수 있다.

무엇이 문제일까? 

우리가 사용하는 C언어 아래에는 또 어셈블리어가 있다. C언어에서는 최소 단위라고 생각되는 함수들이, 실제로 어셈블리어 단계에서는 여러 단계를 거쳐 수행된다. 해당 예제에서 문제가 되는 아래 부분이 실제로 CPU에서 어떻게 수행되는지 보자.

for (i = 0; i < niters; i++) //line:conc:badcnt:beginloop
	cnt++;                   //line:conc:badcnt:endloop

간단히 정리해보면, cnt++; 이라는 작업은 CPU 입장에서 아래와 같은 세 개의 작업으로 구분된다.

1) Load(L) : 메모리에 저장된 cnt를 불러와서 레지스터 r1에 저장한다.

2) Update(U) : r1에 있는 데이터에 1을 더한다.

3) Store(S) : r1에 있는 데이터를 메모리에 다시 저장한다.

1번 쓰레드가 수행해야 하는 작업을 L1, U1, S1이라고 하고 2번 쓰레드가 수행해야 하는 작업을 L2, U2, S2라고 하자.

원래는 L1, U1, S1 -> L2, U2, S2 순서대로 수행되는 것이 작성자의 의도이지만, 쓰레드 간의 실행 순서는 우리가 조작할 수 있는 범위를 벗어난다. 위와 같이 L1->U1->L2->S1->U2->S2순서대로 작업이 일어나면, cnt는 2가 아닌 1이 되면서 의도와 다른 결과가 나오게 된다.

따라서 이런 공유 영역들을 조절할 때는 아래와 같이 Mutex를 사용한다. Mutex는 공유된 자원(Critical Section)에 접근하는 키이다. 키를 가진 사람만 접근할 수 있도록 1이면 접근 가능, 0이면 사용중을 의미한다. 쓰레드가 공유 자원에 접근하려고 할 때 Mutex를 확인하고, 누군가가 사용중이면(Mutex == 0이면) 다음 쓰레드에게 실행 순서를 넘겨준다.(술집의 화장실 키를 생각하면 된다. 키가 없으면 기다리고, 키가 있으면 들고간다.)

P 함수는 Mutex가 1이면 0으로, V 함수는 Mutex가 0이면 1로 만들어주는 함수이다. 위의 코드를 작성자의 의도대로 수정하면 아래와 같다.

/* 
 * goodcnt.c - properly synchronized counter program 
 */
#include "csapp.h"

void *thread(void *vargp);  /* Thread routine prototype */

/* Global shared variable */
volatile long cnt = 0; /* Counter */
sem_t mutex;

int main(int argc, char **argv) 
{
    long niters;
    pthread_t tid1, tid2;
    Sem_init(&mutex, 0, 1);
    /* Check input argument */
    if (argc != 2) { 
	printf("usage: %s <niters>\n", argv[0]);
	exit(0);
    }
    niters = atoi(argv[1]);

    /* Create threads and wait for them to finish */
    pthread_create(&tid1, NULL, thread, &niters);
    pthread_create(&tid2, NULL, thread, &niters);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);

    /* Check result */
    if (cnt != (2 * niters))
	printf("BOOM! cnt=%ld\n", cnt);
    else
	printf("OK cnt=%ld\n", cnt);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp) 
{
    long i, niters = *((long *)vargp);

    for (i = 0; i < niters; i++){ 
        P(&mutex); // Mutex += 1 if Mutex == 0
        cnt++;                   
        V(&mutex); // Mutex -= 1 if Mutex == 1
    }
}
/* $end goodcnt */

  Dynamic Programming(동적 프로그래밍)은 구하고자 하는 최적해가 부분문제들로 이루어져있고 부분문제들이 또다른 작은 부분문제들로 이루어졌을 때 풀이시간 단축을 위해 사용된다. 반복되는 부분문제들을 한번씩만 계산하여 저장한 뒤, 저장한 값을 사용하여 중복되는 부분문제들의 계산을 줄이는 방법이다. 저장된 값을 재사용함에 따라 풀이시간은 감소하지만, 저장하는 값들의 공간만큼 메모리 공간이 더 소모된다는 단점이 있다.

DP 문제를 풀때의 일반적인 접근은 아래와 같다.

1. 최적해의 구조적 특징을 찾는다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 Bottom-Up으로 계산한다.

4. 계산된 정보들로부터 최적해를 구성한다.

정의만 읽어보면 두루뭉실하니, 예제를 보면서 이해해보자.

Problem : 피보나치 수열의 N번째 숫자를 구하라.

1. 피보나치 수열의 구조적 특징 : n번째 숫자는 n-1번째 숫자와 n-2번째 숫자를 더한 값이다.

2. 최적해의 값을 재귀적으로 정의한다.

def fib(n):
    if n==1 or n==2:
    	result = 1
    else:
    	result = fib(n-1) + fib(n-2)
    return result

  이 상태로도 풀이가 가능하지만, 시간초과 / Recursion Limit 초과로 불가능한 경우가 많다. 위의 코드대로 풀이를 진행하면, fib(5)를 구할 때 아래와 같이 반복된 계산을 수행하게 된다.

  따라서, 현재 구현된 재귀 방식의 시간복잡도는 O(2^n)이다. 계산 횟수를 줄이기 위해 계산값들을 memo라는 배열 안에 저장하고, 저장된 값들을 사용해보자.

def fib(n):

    memo = [0, 1, 1]
    memo.extend([0 for _ in range(n)])
    
    def find(n):
        if memo[n]:
            return memo[n]
        else:
            result = find(n-1) + find(n-2)
            memo[n] = result
        return result

    return find(n)

  우선 memo라는 배열을 만들어준 뒤, 계산한 값은 memo[n]에 저장한다. memo[n] 값이 존재하는 경우, 계산하지 않고 바로 이 값을 사용한다. 이렇게 중복되는 부분문제들의 결과값을 저장하여 사용하는 방법을 Memoization이라고 한다.

위와 같은 방식의 시간복잡도는 O(n)이 된다.

3. 최적해의 값을 Bottom-Up으로 계산한다.

  위와 같은 방법은 재귀적으로 호출하기 때문에 Max Recursive Limit에 걸리는 문제가 발생할 수 있다. 따라서 그냥 1부터 n까지 순차적으로 memo 배열을 채워가는 방식을 생각할 수 있는데, 이를 Bottom-up 방식이라고 한다. 재귀를 사용한 것보다 더 간단하고, 빠르다.

def fib(n):

    memo = [0, 1, 1]
    memo.extend([0 for _ in range(n)])
    
    for i in range(3, n+1):
        memo[i] = memo[i-1] + memo[i-2]

    return memo[n]

물론 피보나치보다 더 어려운 문제들을 접할 때는, 최적해의 구성을 통해 부분문제들을 정의하는 것이 매우 어려울 때가 많다. 추후 다른 문제들 Review를 통해 알아본다

가상 메모리, 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를 구현해본다.

위상 정렬이란, 비순환 방향 그래프를 순서대로 정렬하는 방법이다.

1. 위상 정렬 조건

* 비순환 : 그래프에 시작과 끝이 존재해야 한다.(순환 가능하면 안된다.)

* 방향성 : 노드들 사이에 방향이 존재해야 한다.

2. 위상 정렬 특성

* 위상 정렬을 사용하여 정렬된 결과는 여러가지가 있을 수 있다.

3. 방법

위와 같은 그래프의 모든 노드를 방향에 따라 순서대로 방문한다고 할 때, 위상 정렬은 아래와 같은 간단한 성질을 이용한다. 

특정 노드로 들어오는 간선(Edge)이 없다면, 방문 가능한 상태이다.

위의 성질을 이용하여, 아래와 같이 구현할 수 있다.

1. 방향 정보를 저장하는 배열을 생성한다.

주어진 방향 정보 : (1 → 2), (2 → 3), (2 → 4), (3 → 4), (4 → 5)

dir_list = [[1, 2],[2,3], [2,4], [3,4], [4,5]]

2. 각 노드들로 들어오는 간선의 개수(진입 차수)를 저장한다.

ex) 1번 노드로 들어오는 간선 : 0개

     2번 노드로 들어오는 간선 : 1개

     3번 노드로 들어오는 간선 : 1개

     4번 노드로 들어오는 간선 : 2개

     5번 노드로 들어오는 간선 : 1개

inDegree = [0, 1, 1, 2, 1]

3. 빈 큐를 생성하고, 들어오는 간선의 개수가 0인 노드들을 추가한다.

4. (Loop Start) 큐에서 순차적으로 deque한다.

5. deque된 노드에 연결된 간선들을 제거한다.(= inDegree 배열을 업데이트한다.)

6. 각 노드로 들어오는 간선의 개수(진입차수)가 0인 노드를 큐에 추가한다.(Loop End)

5. deque된 순서대로 출력한다.

위의 예시로 순차적으로 진행해보자.

[t = 0] : 초기 Set-up

1) inDegree 배열에서 들어오는 간선의 수(진입차수)가 0인 노드인 1번 노드를 찾아 큐에 추가한다.

[t = 1] : Loop Start

1) 큐에서 가장 왼쪽에 있는 노드를(1번 노드) deque한 뒤, 1번 노드에 연결된 간선들을 제거한다.

2) 들어오는 간선이 0이 된 2번 노드를 큐에 추가한다.

[t = 2]

1) 큐에서 가장 왼쪽에 있는 노드를(2번 노드) deque한 뒤, 2번 노드에 연결된 간선들을 제거한다.

2) 들어오는 간선이 0이 된 3번 노드를 큐에 추가한다.

[t = 3]

1) 큐에서 가장 왼쪽에 있는 노드를(3번 노드) deque한 뒤, 3번 노드에 연결된 간선들을 제거한다.

2) 들어오는 간선이 0이 된 4번 노드를 큐에 추가한다.

[t = 4]

1) 큐에서 가장 왼쪽에 있는 노드를(4번 노드) deque한 뒤, 4번 노드에 연결된 간선들을 제거한다.

2) 들어오는 간선이 0이 된 5번 노드를 큐에 추가한다.

[t = 5]

1) 큐에서 가장 왼쪽에 있는 노드를(5번 노드) deque한 뒤, 5번 노드에 연결된 간선들을 제거하려고 보니, 제거할 것이 없다. 그대로 deque한다.

아래 deque된 노드들을 그대로 출력하면 위상정렬이 완료되었다. 결과는 [1, 2, 3, 4, 5]이다. 

이 그래프의 경우는 답이 한가지밖에 나오지 않지만, 아래와 같은 그래프는 위상정렬하면 여러가지의 결과가 나올 수 있다. 처음 시작을 6에서 해도 되고 1에서 해도 되기 때문이다.

가능한 결과 : [1, 6, 2, 3, 4, 5], [6, 1, 2, 3, 4, 5]

위상정렬을 파이썬으로 구현하면 아래와 같다.

# n은 노드의 개수, m은 간선의 개수
# 생각의 편의를 위하여 0번 index는 비워놓고 진행

n,m = map(int, r().split())
inDegree = [0 for i in range(n+1)]
dir_list = [[] for i in range(n+1)]

for i in range(m):
    s, e = map(int, r().split())
    dir_list[s].append(e)
    inDegree[e] += 1

q = deque()

while True:
    for i in range(1, n+1):
        if inDegree[i] == 0:
            q.append(i)
    for i in range(1,n+1):
        x = q.popleft()
        answer.append(x)
        for j in dir_list[x]:
            inDegree[j] -= 1
            if inDegree[j] == 0:
                q.append(j)
    if not q:
        break
print(*answer)

그래프

그래프란 객체 간에 짝을 이루는 관계를 정점(Vertice)와 간선(Edge)으로 나타내는 수학구조이다.

예를 들면, 아래와 같이 대한민국의 도시들의 고속도로 연결관계를 그래프 구조로 나타낼 수 있다.

그래프는 아래와 같은 수식으로 나타낸다.

G = ( V , E )

V는 정점(Vertice), E는 간선(Edge)를 나타낸다. 위 그래프는 7개의 정점과 9개의 간선을 가진 그래프이다.

이제 그래프 구조를 자료구조로 나타내보자.

그래프를 표현하는 방법으로는 인접 행렬 표현법, 인접 리스트 표현법이 있다.

인접 행렬 표현법

  그래프의 연결 정보를 행렬로 저장하는 방법이다. 아래와 같이 세로축, 가로축에 각 도시 이름을 기록하고, 교차하는 곳에 도시를 연결하는 고속도로의 존재 여부를 표기한다. 고속도로가 있다면 1, 없다면 0을 기록하면 된다. 행렬의 크기는 정점(V)의 제곱이 된다. 따라서 간선이 많은(=높은 밀도의) 그래프의 표현 시 사용된다.

* 위와 같이 간선의 방향성이 없는 경우를 무방향 그래프라고 한다. 무방향 그래프는 인접 행렬로 표현했을 때 대칭이 되므로, 반만 저장하여 메모리 효율을 높일 수 있다.

인접 리스트 표현법

  그래프의 연결 정보를 리스트로 저장하는 방식이다. 도시 길이만큼의 배열을 만들고, 각 도시에 연결된 도시들을 리스트로 저장한다. 이때 저장되는 도시들의 수는 (간선의 총 개수 * 2) 이다. 즉, 2 * E만큼의 메모리를 사용한다. 따라서 정점의 개수에 비해 간선의 개수가 적은(=낮은 밀도의) 그래프의 표현 시 사용된다.

* 인접 리스트 표현은 무방향/방향 그래프 모두 메모리 사용이 동일하다.

이렇게 저장된 데이터를 사용하여 원하는 최댓값/최소값을 구하는 데 사용되는 알고리즘이 BFS, DFS이다. 해당 알고리즘에 대한 정보는 아래 글에 있다.

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