기록공간

트리란? 트리(Tree)는 계층 구조(Hierarchical Structure)로 자료를 저장하는 자료구조이다. 여기서 말하는 계층 구조란 트리를 구성하는 노드가 부모-자식(Parent-Child) 관계라는 의미이다. 즉 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조를 말한다. 이러한 구조로 노드들이 연결된 모습이 마치 마치 나무와 같아 트리라는 이름이 붙여졌다. 그래서 앞으로 살펴 볼 용어 중 나무의 부분에 대한 명칭을 가져온 것이 있다. 예를 들어, 컴퓨터의 폴더 구조나 가족의 가계도, 직장의 조직도 등과 같이 계층적인 관계를 가진 자료를 표현하고 싶은 경우 선형 자료구조만으로 충분하지 않다. 트리는 이러한 계층적인 자료를 표현하는데 이용되는 자료구조이다. 트리의 용어들 트리와 관련된..

Direct3D 12는 다중 스레드를 효율적으로 활용할 수 있도록 설계되었다. 명령 목록의 설계는 Direct3D가 다중 스레드 적용의 장점을 취하는 한 방법이다. 물체가 많은 큰 장면을 다룰 때, 장면 전체를 하나의 명령 목록으로 그리려 한다면 명령 목록을 구축하는 데 시간(CPU 시간)이 오래 걸린다. 이에 대한 해결책은 여러 개의 명령 목록을 병렬로 구축하는 것이다. 예를 들어 스레드 네 개를 띄워서 각자 하나의 명령 목록을 구축하게 하면, 전체적인 시간이 기존의 25%로 줄어든다. 다음은 명령 목록 구축에 다중 스레드를 적용할 때 주의해야 할 점 몇 가지이다. 명령 목록은 자유 스레드(Free-thread) 모형을 따르지 않는다. 즉, 보통의 경우 여러 스레드가 같은 명령 목록을 공유하지 않으며,..

멀티 레벨 피드백큐(Multi Level Feedback Queue) 스케줄러가 해결하려고 하는 기본적인 문제는 두 가지이다. 첫째, 짧은 작업을 먼저 실행시켜 반환시간을 최적화하고자 한다. 전 장의 SJF나 STCF 같은 알고리즘은 작업의 실행 시간 정보를 필요로 하지만, 불행히도 운영체제는 이 실행 시간을 미리 알 수 없다. 둘째, MLFQ는 대화형 사용자(즉, 컴퓨터 사용자)에게 응답이 빠른 시스템이라는 느낌을 주고 싶기 때문에 응답 시간을 최적화 한다. 불행히도 RR과 같은 알고리즘은 응답시간을 단축시키지만 반환 시간은 거의 최악이다. 그러면 프로세스에 대한 정보가 없다면 이러한 스케줄러를 어떻게 만들 수 있을까? 실행 중인 작업의 특성을 알아내고 이를 이용하여 더 나은 스케줄링 결정을 하기 위한..

이진 트리의 문제점 이진 트리의 문제점은 한쪽으로 치우친 형태로 트리 구조가 만들어질 수 있다는 것이다. 이렇게 되면 트리 구조가 아니라 일반적인 연결 리스트와 별 차이가 없는 구조가 되어 이진 트리의 장점을 전혀 발휘할 수 없게 된다. 위와 같이 이진 트리가 구성되면 실제 이진 트리의 장점인 노드 검색 시 성능이 O(logN)이 된다는 것을 보장할 수 없다. 만약 위 그림처럼 트리가 구성되어 있다면 14를 찾기 위해서는 트리의 맨 밑까지 내려가야 한다. 즉, 9번의 노드 검사가 필요하게 된다. 이처럼 위 트리 구조는 최악의 경우에 성능이 O(N)이다. 이러한 문제를 해결하기 위한 방법 중 하나인 AVL 트리에 대해서 본격적으로 알아보도록 하자. AVL 트리 AVL 트리는 전체 트리의 구조가 균형이 맞도..

흔히 쓰이는 렌더링 효과 중에는 한 단계에서 GPU가 자원 R에 자료를 기록하고, 이후의 한 단계에서 그 자원 R의 자료를 읽어서 사용하는 식으로 구현하는 것들이 많다. 그런데 GPU가 자원에 자료를 다 기록하지 않았거나 기록을 아예 시작하지도 않은 상태에서 자원의 자료를 읽으려 하면 문제가 생긴다. 이를 자원 위험 상황(Resource hazard)이라고 부른다. 이 문제를 해결하기 위해, Direct3D는 자원들에게 상태를 부여한다. 새로 생성된 자원은 기본 상태(default state)로 시작한다. 임의의 상태 전이를 Direct3D에게 '보고'하는 것은 전적으로 응용 프로그램의 몫이다. 이 덕분에, GPU는 상태를 전이하고 자원 위험 상황을 방지하는 데 필요한 일들을 자유로이 진행할 수 있다. ..

이제부터 다양한 스케줄링 정책(Scheduling policy)을 소개할 것이다. 이러한 정책은 원칙이라고도 불리며 많은 똑똑하고 부지런한 사람들이 오랫동안 개발한 정책이다. 스케줄링의 기원은 컴퓨터 시스템 개발 이전으로 거슬러 올라간다. 초기의 방법들은 생산 관리 분야에서 개발되었으며 컴퓨터에 적용되었다. 이 사실은 그렇게 놀라운 일은 아니다. 생산 공정과 기타 많은 인간의 행동 역시 스케줄링이 필요하고, 효율성에 대한 요구 등, 공통된 해결 사항이 존재하기 때문이다. 스케줄링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들어야 할까? 핵심 과정은 무엇일까? 워크로드에 대한 가정 가장 먼저 프로세스에 대해서 몇 가지 가정을 할 것이다. 일련의 프로세스들이 실행하는 상황을 워크로드(Workload..

역시 동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 살펴보자. 피보나치 규칙인 F(N) = F(N - 1) + F(N - 2)를 염두해두고 보자. * N이 0일때 0 호출 횟수 = 1 1 호출 횟수 = 0 * N이 1일때 0 호출 횟수 = 0 1 호출 횟수 = 1 * N이 2일때 0 호출 횟수 = (1일때 0 호출 횟수) + (0일때 0 호출 횟수) = 0 + 1 = 1 1 호출 횟수 = (1일때 1 호출 횟수) + (0일때 1 호출 횟수) = 1 + 0 = 1 * N이 3일때 0 호출 횟수 = (2일때 0 호출 횟수) + (1일때 0 호출 횟수) = 1 + 0 = 1 1 호출 횟수 = (2일때 1 호출 횟수) + (1일때 1 호출 횟수) = 1 + 1 = 2 0과 1의 호출 횟수가 필요하기 때문에 ..

동적계획법을 사용하는 문제이다. 규칙을 먼저 살펴보자. * 1일 경우 1 -> 1개 * 2일 경우 1 + 1 2 -> 2개 * 3일 경우 1 + 1 + 1 2 + 1 1 + 2 3 -> 4개 * 4일 경우 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 2 + 1 + 1 2 + 1 1 + 3 3 + 1 -> 7개 (혹은 F(3) + F(2) + F(1) = 4 + 2 + 1 = 7) * 5일 경우 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 1 + 2 + 1 + 1 1 + 1 + 2 + 1 1 + 1 + 1 + 2 2 + 2 + 1 2 + 1 + 2 1 + 2 + 2 3 + 1 + 1 1 + 3 + 1 1 + 1 + 3 2 + 3 3 + 2 -> 13개 (혹은 F(4) + F(3..