with with

Minimum Spanning Tree Greedy 알고리즘의 예시인 Prim's Algorithm을 살펴보기 전에 그 알고리즘이 다루는 Minimum Spanning Tree의 정의부터 알아보자. - Tree Graph 구조에서 cycle 구조가 존재하지 않고, 연결되지 않은 vertex가 없고, edge에 방향성이 없는 그래프. - Spanning Tree 오리지널 Tree의 부분 트리. 즉, 오리지널 Tree에서 일부 edge가 없는 트리를 의미한다. - Minimum Spanning Tree Spanning Tree 중, edge의 weight의 합이 최소가 되는 트리. G1이 오리지널 트리라 했을 때, G4, G5만이 G1의 Minimum Spanning Tree이다. G2의 경우에는 G1에 S..

물리 메모리의 크기와 상관없이 프로세스에 거대한 메모리 공간을 제공하는 기술로, 가상 메모리를 이용하면 프로세스는 운영체제가 어디에 있는지, 물리 메모리의 크기가 어느 정도인지 신경 쓰지 않고 메모리를 마음대로 사용할 수 있게 된다. 가상 메모리의 크기는 실제 메모리의 크기와 스왑 영역의 크기를 합친 만큼이 되는데, 가상 메모리 공간에 접근하기 위해서는 동적 주소 변환이 필요하다. 즉, 가상 주소를 실제 주소로 변환해야 데이터를 물리 메모리에 저장할 수 있는 것이다. 가상 메모리의 메모리 분할 방식은 물리 메모리에서 가변 분할 방식을 채택한 것 처럼 세그먼테이션 방식을 채택하는 경우와, 고정 분할 방식을 채택한 것 처럼 페이징을 채택하는 경우가 있다. 버디 시스템처럼 두 단점을 보완한 세그먼테이션-페이징..

메모리는 폰노이만 구조의 컴퓨터에서의 유일한 작업공간이다. 따라서 모든 프로그램은 메모리에 올라와야 작업을 수행할 수 있다. 오늘날의 시분할 시스템에서 모든 응용 프로그램이 메모리에 올라와 실행되어야 하는데, 물리적인 메모리공간의 한계가 있기 때문에 이를 관리하는 것이 매우 어려워졌다. MMU - Memory Manage Unit 메모리 관리를 담당하는 하드웨어 유닛으로 아래와 같은 작업을 한다. 가져오기 프로세스와 데이터를 메모리로 가져옴. 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올 지 결정하는 정책이 있다. 배치 가져온 프로세스와 데이터를 메모리의 어떤 부분에 올릴지 정책에 따라 결정. 재배치 꽉 차 있는 메모리에 새로운 프로세스를 가져오기 위해 정책에 따라 프로세스를 내보냄 메모리 주소 ..

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 진행하지 못하는 상황을 의미한다. Deadlock 필요조건 아래의 4가지 조건이 모두 충족되는 경우 교착 상태가 발생한다. 상호 배제 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함. 비선점 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다. 점유와 대기 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함. 원형 대기 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함. 즉, 위 4조건 중 하나라도 충족되지 않으면 교착 상태는 발생하지 않는다. 교착 상태 예방 - 상호 배제 예방 시스템 내에 독점적으로 사용할 수 있는 자원..

통신 프로세스 간 통신의 종류는 다음과 같다 프로세스 내부 데이터 통신 2개 이상의 스레드가 존재하는 경우 스레드 간의 통신을 의미한다. 전역 변수나 파일을 이용하여 데이터를 주고 받는다. 프로세스 간 데이터 통신 공용 파일 또는 운영체제가 제공하는 파이프를 사용하여 데이터를 주고 받는다. 네트워크를 이용한 데이터 통신 컴퓨터 간의 통신을 의미한다. 소켓을 이용하여 데이터를 주고 받는다. 통신 방향에 따른 분류는 다음과 같다 양방향 통신 데이터를 동시에 양쪽 방향으로 전송할 수 있는 구조. 소켓 통신이 이에 해당. 단양방향 통신 데이터를 양쪽 방향으로 전송할 수 있지만, 동시에 양쪽 방향으로 전송은 불가능한 구조. 무전기가 이에 해당. 단방향 통신 데이터를 한 쪽 방향으로만 전송할 수 있는 구조. 프로세..

Overview parser and translator에서 문법 검사과 유효한 테이블에 접근하는지 검사한다. evaluation engine에서 최적화된 실행 계획에 맞게 쿼리문을 실행한다. optimizer는 같은 결과를 내는 여러 관계 대수식(실행문) 중 Cost가 가장 낮은 실행문을 고른다. Cost Disk access, CPU, network communication 등의 시간 비용을 의미한다. 여기서는 CPU비용은 너무 작으니 무시하도록 하고, 분산 시스템에서는 network communication이 중요하지만, 여기선 단일 시스템으로 가정하기에 역시 무시한다. Disk access는 실제 시간이 아닌, 몇 블럭을 읽어오는지, 공간 단위로 측정하도록 한다. Disk cost는 아래와 같은 비..

Index 인덱스는 table의 attribute의 부분집합을 복제하여 구조화, 정렬한 것으로 빠른 접근을 가능케 한다. 따라서 attribute로 만들 수 있는 모든 조합의 집합으로 인덱싱 해놓으면 어떻게 검색을 하든 매우 빠르게 데이터를 찾을 수 있을 것이다. 하지만, 이런 경우에는 저장공간이나, 업데이트시에 오버헤드가 매우 커지기 때문에 현실적으론 불가능하다. 따라서 공간 효율적으로 인덱싱 하기 위해 자료구조를 잘 사용해야 하는데, 이번 포스팅의 주제인 B+Tree는 DBMS에서 사용하기에 매우 적합한 자료구조이다. B+Tree B-Tree는 BST의 밸런싱 문제를 해결하고자 나온 자료구조인데, B+Tree는 이런 B-Tree의 특성을 살리면서 데이터베이스 시스템에서 사용하기 좋게 기능이 추가된 버..

hash table은 해시 함수를 이용해서 어떠한 입력이라도 특정 정수로 치환된 주소에 데이터를 저장할 수 있는 자료구조로 일반적으로 O(1)의 시간복잡도를 갖는다. 사실 해시함수를 구현하기에 따라 해시 테이블의 탐색 시간 복잡도가 크게 차이날 수 있는데, 이 포스트는 자료구조의 해시 테이블를 다루는 것 보다, 데이터베이스에서 데이터를 다룰 때 해시 테이블을 사용하는 방식을 다루기 때문에 깊은 내용은 생략합니다. 해시 테이블을 설계함에 있어 몇가지 부분에서 Trade-off가 요구됩니다. - Hash function 해시 함수는 큰 범위의 입력 값을 작은 도메인으로 줄여야 합니다. 그 과정에서 필연적으로 다른 입력에 대해 같은 값(collision)이 나올 수도 있습니다. 이 과정에서 collision ..