댕글링 포인터(Dangling Pointer)란? 댕글링 포인터는 적절한 타입의 유효한 객체를 가리키고 있지 않은 포인터를 말한다. 예를 들어 이미 할당 해제된 메모리를 포인터가 계속 가리키고 있다면 해당 포인터는 댕글링 포인터이다. 예를 들어 메모리에 할당된 하나의 객체를 가리키는 두 개의 포인터 ptr1, ptr2가 있다고 하자. 이때 ptr1만을 free 하여 메모리를 해제해주면 ptr2는 Dangling Pointer가 돼버린다. 댕글링 포인터 해결법 1. Tombstone Approach 첫번째 방법은 tombstone(비석)이라고 불리는 특별한 cell을 설정해 포인터가 할당된 객체를 직접 가리키지 않고 비석을 통해 가리키도록 하는 방법이다. 예를 들어 [그림 3]처럼 ptr1을 free 한다..
바인딩(Binding) Binding은 연관 짓는 것이다(association). 예를 들어 엔티티(Entity)와 속성(Attribute), 심벌(symbol)과 연산자(operation)를 연관 짓는 것 등을 binding이라고 한다. 바인딩 타임(Binding Time) 바인딩 타임은 결정되는 시점에 따른 분류로 구분지을 수 있다. 언어 디자인 시점(at language design time) - 대부분의 언어에서 제어 흐름 구조, 기본 유형 집합, 복잡한 유형을 만드는 데 사용할 수 있는 생성자 및 언어론의 많은 측면들이 언어를 디자인할 때 선택된다. 언어 구현 시점(at language implementation time) - 대부분의 언어 매뉴얼이 언어 구현자의 재량에 다양한 이슈를 남긴다. ..
레드-블랙 트리(Red-Black Tree) 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다. 1. 모든 노드는 빨간색 혹은 검은색이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 4. 빨간색 노드의 자식은 검은색이다. == No Double Red(빨간색 노드가 연속으로 나올 수 없다) 5. 모든 리프 노드에서 Black Depth는 같다. == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 트리 관련 용어를 잘 모르겠다면 다음 포스팅을 참고하자. [자료구조] 트리(Tree)의 개념 | 이진 트리, 전 이진 트리..
AVL 트리란? 예전에 이진탐색트리에 대해 알아본적이 있다. [자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현 이진탐색트리(Binary Search Tree)이란? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다 code-lab1.tistory.com 이진탐색트리는 큰 문제점이 있으니, 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이다. 위와 같은 형태의 트리에서 특정 값을 찾으려면 O(N)의 시간이 필요할 것이다. 예를 들..
페이지 교체 알고리즘 (Page Replacement Algorithm) 이전 포스팅으로 요구 페이징(Demand Paging)에 대해 알아보았다. 필요한 페이지가 메모리에 없을 때 page-falut가 발생하고 Backing Store에서 해당 페이지를 찾아 빈 프레임에 로딩해야 하는데, 이때 빈 프레임이 없을 경우 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다. 페이지 교체 알고리즘은 page-fault 발생 비율을 줄이는 것을 목표로 한다. +요구 페이징에 대한 내용은 다음을 참고하자. [운영체제] 가상메모리(Virtual Memory)와 요구 페이징(Demand Paging), Valid-Invalid Bit, 페이지 부재(Page Faul 가상 메모리(V..
가상 메모리(Virtual Memory) 메인 메모리의 크기는 한정되어 있다. 따라서 물리적인 메모리 크기보다 크기가 큰 프로세스는 실행시킬 수 없게 된다. 예를 들어 메인 메모리의 크기가 100MB 일 때 300MB 크기의 프로세스는 실행시킬 수 없다. 크기가 큰 프로세스를 실행시키기 위해서는 메인 메모리를 크게 키우는 방법이 있겠지만, 이것은 매우 비효율적이다. 따라서 나온 방법이 바로 가상 메모리(Virtual Memory)이다. 가상 메모리는 메모리 관리 기법의 하나로, 기계에 실제로 이용 가능한 자원을 추상화하여 사용자들에게 매우 큰 메모리인 것처럼 보이게 만드는 것을 말한다. 즉, 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식이다. 가상적으로 주어진 주소를 가상 주소(vi..
Copy On Write (COW) 란? 1 2 3 4 5 6 std::string x("Hello"); std::string y = x; // x and y use the same buffer y += " World!"; // now y uses a different buffer // x still uses the same old buffer cs 위와 같은 코드가 있다고 하자. ( C++ 98에서의 동작이다. C++ 11 이상에서는 동작하지 않음 ) x라는 buffer에 "Hello" 라는 string을 넣고, y라는 복사본을 만든다고 하자. 이때 x와 y는 같은 buffer를 가리키게 된다. 하지만 이때 복사본인 y를 변경하면 아래와 같이 된다. 더이상 y는 같은 buffer를 가리키지 않고, 새로..
세그멘테이션(Segmentation)이란? 페이징은 프로세스를 물리적으로 일정한 크기로 나눠서 메모리에 할당하는 것을 의미한다. 반면, 세그멘테이션은 프로세스를 논리적 내용을 기반으로 나눠서 메모리에 배치하는 것을 의미한다. 세그멘테이션은 프로세스를 세그먼트(segment)의 집합으로 표현한다. 이때 세그먼트는 논리 단위로 아래와 같은 것들이 해당된다. main program procedure function method object stack local variable global variable etc... 프로세스를 code영역, data영역, stack영역 등으로 나누는 것 또한 세그멘테이션이라고 할 수 있다. 세그멘테이션도 페이징과 비슷하게 세그먼트 테이블을 가지고 있다. 페이징과 비슷하게 논리..
Hierarchical Page Table 하나의 페이지 테이블 안에 여러개의 페이지 테이블을 넣은 페이지 테이블을 의미한다. 이 중 대표적으로 2-level page table에 대해 알아보자. 32-bit machine, 4K page size를 가정했을 때, 논리 주소는 아래와 같이 구성된다. page number : 20bit p1-page number : 10bit p2-page offset : 10bit page offset : 12bit 즉 p1은 outer page table(바깥 테이블)의 index이고, p2는 해당 바깥 테이블에서의 위치를 나타낸다. 이해가 쉽지 않다면 다음 그림을 살펴보자. p1을 통해 outer-page table의 인덱스를 찾고, 해당 인덱스가 가리키는 page ..
페이징(Paging)이란? 페이징이란 논리주소의 메모리를 고정된 크기의 페이지(Page)로 나누어 관리하는 기법이다. 페이징은 아래와 같은 특징들을 갖고 있다. 물리주소 공간(Physical address)은 연속적이지 않을 수 있다(noncontiguous) 페이지는 모두 같은 크기를 가진다. 물리주소 공간을 페이지와 같은 사이즈로 나눈 것들을 프레임(Frame)이라고 한다. 페이지 사이즈(=프레임 사이즈)는 하드웨어에 의해 정해진다. 페이지의 크기는 일반적으로 2의 제곱수를 사용한다. 일반적으로 4KB(2^12) ~ 1GB(2^20) 페이지 테이블(page table)을 이용해 논리주소에서 프레임을 가리키는 물리주소로 매핑한다. 외부 단편화는 발생하지 않으나, 내부 단편화는 발생한다. 단편화에 대해서..