hrniin의 개발 노트

스래드 동기화 동일한 프로세스 내부에 생성된 스래드들은 병행적으로 실행되며 자원(프로세스의 코드 영역과 데이터 영역)을 공유한다. 따라서, 임계 영역의 문제(결정성)를 해결하기 위한 동기화 기법이 필요하다. 스래드 동기화 기법 1) 스래드 뮤텍스(mutex): 공유 자원의 개수가 오직 하나일 경우에만 사용. 2) 스래드 세마포어(semaphore): 공유 자원의 개수가 하나거나 그 이상일 경우에도 사용 가능. * 표준 라이브러리가 아님으로 컴파일링시 “–lpthread”를 반드시 첨가해야 한다. (ex: $gcc thread.c –o thread –lpthread) 1) 스래드 뮤텍스(mutex): 뮤텍스(mutexes)는 “MUTual Exclusion locks”의 약자이다. 공유 자원에 대한 상호 ..

B : 데이터 페이지들의 수 R : 페이지 당 레코드들의 수 D : 디스크 페이지를 read/write하기 위한 평균시간 파일 스캔 동등 검색 범위 검색 삽입 삭제 힙 파일 BD 0.5BD BD 2D 검색 연산 + D 정렬 파일 BD Dlog2B D (log2B + match page 수) 검색 연산 + BD 검색 연산 + BD 군집 트리 인덱스 1.5BD DlogF1.5B D(logF1.5B + match page 수) 검색 연산 + D 검색 연산 + D 비군집 트리 인덱스 BD(R + 0.15) D(1 + logF0.15B) D(logF0.15B + matched Records수) D(3 + logF0.15B) D(3 + logF0.15B) 비군집 해시 인덱스 BD(R + 0.125) 2D BD 4D..

한 노드의 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 큰 값으로 정렬되어 있음. 내부 노드: 인덱스 엔트리. 키값과 방향 지시자로 구성. 리프 노드: 데이터 엔트리(검색 키 값으로 정렬됨) 검색 과정: 루트 노드(메인 메모리에 상주)에서 검색 시작 -> 검색 값에 따라 해당 자식 노드로 분기 -> Leaf 노드에 도달하여 탐색 레코드를 찾음. B+ 트리 (Balanced tree in height) - 루트 노드에서 리프 노드로 가는 모든 경로의 길이가 동일한 인덱스 구조 - 탐색 키 값에 관계없이 검색 시간이 거의 일정 - 검색을 위한 디스크 IO 횟수는 root로부터 leaf에 도달하는 경로의 길이 - 모든 리프 노드들은 double linked list로 연결됨 - 범위 검색에 유용 - 범..

군집 인덱스(Clustered Index): 정렬된 속성으로 만든 인덱스. 최대 하나만 생성 가능. 비군집 인덱스(Unclustered Index): 정렬되지 않은 일반 속성으로 만든 인덱스. 여러 개 생성 가능 밀집 인덱스(dense index): 데이터 파일의 각 레코드마다 한 개의 데이터 엔트리를 가짐. 즉 모든 레코드를 인덱싱. 희소 인덱스(sparse index): 각 데이터 블록마다 한 개의 데이터 엔트리를 가짐. 데이터 블록 중 하나의 레코드만 인덱싱. 군집 인덱스에서는 대부분 희소 인덱스를 구축. 실제 데이터 파일이 인덱싱된 속성으로 정렬되어 있으므로, 인덱스를 통해 검색값이 어느 데이터 블록에 속하는지를 비교하여 검색. 희소 인덱스가 밀집 인덱스보다 크기가 적으므로 상대적으로 효율적. 비..

임계 영역(critical section) :프로세스 영역 중에서 공유 자원을 접근하는 코드 영역. (즉 공유 자원에 접근했을 때를 '임계 영역에 있다'고 말함) 모든 프로세스가 임계 영역을 가지고 있는 것은 아니지만 자원을 공유하면서 병행적으로 실행되는 프로세스는 반드시 임계 영역을 가지고 있다. 프로세스의 결정성이 보장되기 위해서는 임계 영역이 상호 배제적으로 실행되어야 한다. 프로세스의 코드 영역 1) 임계 영역(critical section) 2) 진입 영역(entry section) 3) 출구 영역(exit section) 4) 잔류 영역(remainder section) 임계 영역의 문제해결 만족조건 1) 상호 배제(mutual exclusion) 조건: 두 개 이상의 프로세스가 임계영역에 존..

병행성(concurrency): 여러 개의 프로세스 혹은 스래드들이 동시에 실행되는 것 결정성(determinacy): 동일한 입력에 대한 프로세스 혹은 스래드의 실행 결과는 항상 일정하다. 하지만 상호 영향을 주고 받으면서 자원을 공유하고 병행적으로 실행될 경우 실행 결과가 달라질 수 있다. (=결정성이 보장되지 않는다.) 즉, 결정성 보장을 위한 운영체제의 기능이 요구된다. 생산자 프로세스: 데이터를 생산하여 공유버퍼에 저장한다. 소비자 프로세스: 공유 버퍼에 저장된 데이터를 가져와 소비한다. - 두 프로세스는 상호 영향을 주고 받는다. - 두 프로세스에 대한 결정성 보장이 요구됨. (동기화 필요) 경쟁 조건(race condition): 다수의 프로세스들이 공유 메모리를 병행적으로 접근할 때, 그 ..

인덱스 목적: 찾고자 하는 레코드의 검색 속도 향상 - Digital Index: 모체 데이터(전체 데이터베이스)를 기반으로 search key(탐색 키) 값을 찾기 쉽도록 배열한 data entry들의 집합 - Data entry: 인덱스 파일에 저장된 레코드(탐색키 필드 + 주소 필드) - 탐색 키 값에 따라 정렬 - 범용적인 인덱스 구조: balanced 트리 - 모체 데이터가 추가/삭제/수정되면 각 인덱스에 반영되어야 함 복합 인덱스: 두개 이상의 속성으로 인덱스가 만들어지는 것 ex) 전공, 학년으로 인덱싱: 전공으로 1차 정렬, 학년으로 2차 정렬 Index의 data entry에 저장할 방식 ① k *: search key 값이 k인 실제 data record ② : rid는 k 값에 해당하..

페이지: 데이터를 읽고 쓰는 기본 단위 (대부분 4KB/8KB, 데이터베이스에서 주로 사용) 블락: 메인메모리와 디스크간의 데이터 입출력의 기본 단위. 몇 개의 페이지들로 구성. (운영체제에서 주로 사용) 데이터베이스 연산 처리시간 : 페이지들의 입출력 시간 + CPU 처리 시간 페이지의 입출력 시간이 CPU 처리 시간보다 훨씬 크므로 데이터베이스의 데이터를 빠르게 처리하기 위해서는 데이터의 입출력에 필요한 페이지 수를 최소화할 필요가 있음 데이터베이스는 여러 개의 파일로 구성 논리적으로는 테이블들로 구성, 물리적으로는 파일들로 저장 1) Heap 파일 (순서가 없는 파일) 동등검색(ex: 학번이 1234인 학생을 검색) 키(ex: 학번, 주민번호) : 평균적으로 전체 페이지의 절반을 검색 값을 찾은 후..