지금까지 DFA에 대해서 정리하면서, DFA로 표현할 수 있는 언어를 regular language 라고 했었다.이때, 모든 NFA는 DFA로 변환이 가능하기 때문에 NFA로 표현할 수 있는 언어 역시 regluar language 였다.DFA로 표현가능한 언어가 regular language 라면, 거꾸로 regular language 는 DFA로 표현이 가능하다. 따라서 위 그림과 같은 관계가 성립한다.이번 글에서는 regular language를 나타내는 또 다른 방법인 regular expression 에 대해 정리해본다. regular expression 은 다음 3가지 내용으로 정의된다. 1. φ, λ, a ∈ Σ (알파벳에 포함되는 하나의 심볼) 3가지는 모두 regluar expressi..
다음 2개의 명제가 참인지 거짓인지 생각해보자. 1. DFA가 받아들이는 언어는 유일하다. (O)DFA가 받아들이는 (생성하는) 언어는 유일하다.(그리고 그 언어는 regluar 하므로, regular language 라고 할 수 있다.) 2. Regular Language 가 주어질 때, 이 언어를 만드는 DFA는 유일하다. (X)이 명제는 위 명제의 역인데, 이 명제는 틀렸다.하나의 언어를 받아들이는 (만드는) DFA는 여러개가 존재할 수 있다.같은 언어를 만들어내는데, 10개 state로 구성된 DFA를 만들 수도 있고, 20 state 로 구성된 DFA를 만들 수도 있다.따라서 이로부터 어떻게 하면 같은 언어를 만들더라도 최소한의 상태를 사용해서 만들 수 있을지 고민할 수 있다. 왼쪽의 DFA..
인덱스의 탐색 키는 여러 필드를 포함할 수 있다.이렇게 여러 필드로 구성된 탐색 키를 '복합 키' 라고 한다. 위 그림과 같은 테이블을 생각해보자.만약 age 라는 하나의 search key 를 둔 경우에는 11, 12, 12, 13 순으로 인덱스가 정렬되어 가리킬 것이고, 라는 복합키를 둔 경우에는 (10, 12) (20, 12) (75, 13) (80, 11) 순으로 가리킨다. 라는 복합키를 둔 경우에는 (11, 80) (12, 10) (12, 20) (13, 75) 순으로 가리킨다. 이제 이렇게 인덱스가 주어진 상태에서 다음의 쿼리를 실행해보자. 만약 위와 같은 쿼리를 실행한다면 라는 복합키와 라는 복합키가 주어졌을 때, 어떤 것이 더 효율적일까?정답은 이라는 복합키이다.왜냐하면 일단 ..
DBMS에서 디스크로부터 읽어온 데이터를 저장하는 방식은 다양하다.이번 글에서는 다양한 저장 방식의 종류와 특징에 대해 정리한다. 힙 파일DBMS에서 데이터를 저장하는 제일 간단한 파일 구조이다. (자료구조 힙과는 관련이 없다.)데이터베이스에서 읽어오는 페이지는 1KB ~ 8KB 까지 다양한 크기가 존재할 수 있다. 힙 파일에는 이런 페이지가 여러개 모여 저장된다.그리고 각 페이지를 저장할 때는 그냥 들어온 순서에 맞춰 차곡차곡 저장하므로,특정 기준에 의해 정렬되어있다거나 하지는 않는다. 이제 이렇게 데이터를 저장한 상태에서 DBMS의 기능인 데이터 조회, 수정, 삭제 연산을 생각해보자. 만약 힙 파일로 DBMS에 데이터를 저장해둔 상태에서 특정 레코드를 조회, 수정하는 경우,그 레코드가 위치한 페이지를..
하드 디스크의 구조 하드 디스크는 여러개의 원판이 겹겹이 쌓인 구조를 하고 있다.각 원판 중앙에는 spindle rod 라는 중심축이 있고, 각 원반은 중심축을 기준으로 회전한다.이 원반을 platter 라고 부르고, 플래터에 들어있는 0과 1로 이루어진 데이터를 r/w arm 이 읽어들인다.이때 데이터를 읽기 위해서는 각 arm이 물리적으로 이동을 해야 하는데, 디스크 플레이트는 여러개의 트랙으로 구분되고, 그림에서 보는 것처럼 원반을 부채꼴 모양으로 자른 섹터로 나눌 수도 있다. 데이터를 읽고 쓸 때는 하나의 플레이트에서 색터와 트랙이 만드는 영역에 저장되는 '블록' 단위로 데이터를 읽고 쓴다.따라서 데이터를 찾는 데 걸리는 시간은 트랙을 이동하는 시간과 회전하여 섹터를 찾는 시간의 합으로 나타낼 수..
그림과 같이 스레드가 구현되어 있다고 해보자.(이 구현은 user level 스레드를 보여주고 있다. 런타임 시스템과 그 내부에 스레드 테이블이 있기 때문이다.) 이때 각각의 프로세스에게는 50ms 의 퀀텀이 주어졌고, 각 스레드는 CPU burst 마다 5ms의 시간이 소모된다고 해보자. 그러면 커널이 먼저 실행할 프로세스를 고르고, 그 다음에 런타임 시스템이 실행할 스레드를 골라서 굴리므로 프로세스 A의 스레드들이 A1 A2 A3 A1 A2 A3 이런식으로 돌아간다.유저 레벨 스레드는 스레드 스위칭이 빠르므로, thread_yield 와 같은 프로시저를 사용하여 빠르게 스레드를 교체하며 돌리는 것이 가능하고, 성능도 좋다. (다만 라운드 로빈과 같이 정해진 퀀텀을 정해두고 돌리는 것은 힘들다.) 이때..
스레드를 구현하는 방법은 User space 에서 구현하거나, Kernel space 에서 구현하거나, 두 방법을 섞는 하이브리드 방법 크게 3가지가 있다. 각각의 구현 방법에 대해서 정리해본다. User Space 메모리 공간은 크게 User space 와 Kernel space 로 나뉜다.유저 스페이스는 일반적인 유저 프로세스가 실행되는 공간이고, kernel spaces는 운영체제의 핵심 요소인 커널이 존재하며 실행되는 공간이다. User space 에서 스레드를 구현하는 경우 위 그림과 같이 구현할 수 있다.이때 운영체제는 실제로 멀티스레드가 가능한 환경으로 동작하지만, 커널은 스레드의 존재를 모르고, 기존의 프로세스 모델에서 프로세스를 다루는 것과 비슷하게 돌아간다. 따라서 커널에는 proce..
Process Model지금까지는 프로세스와 프로세스 스케줄링, 프로세스 통신에 대해서 정리하였다.이렇게 프로세스를 사용하여 컴퓨터 프로그램의 동작을 기술하는 것을 Process Model 이라고 하며,이번 글부터는 Thread Model 을 통해서 프로그램의 동작을 기술해보고자 한다. Process Model 은 크게 2가지 개념을 갖는다.1. Resource Grouping2. Thread 리소스 그룹핑은 다음과 같은 데이터를 프로세스 단위로 갖는 것을 말한다.- Address Space (메모리에 프로세스가 차지하는 공간, 유닉스의 경우 Text(Code) 세그먼트, Data 세그먼트, Stack 세그먼트로 구분)- open file (현재 이 프로세스가 open 한 file에 대한 정보)- c..
예를 들어 어떤 DBMS 가 실행되고 있다고 해보자.DBMS는 여러 사용자가 접근 가능한 시스템이므로, 각 사용자를 응대하는 자식 프로세스가 여러 개 존재할 것이다.이때 DBMS가 유동적으로 자신이 원하는 특정 자식 프로세스에게 더 높은 CPU를 할당하고 싶은 상황이 있을 수 있다.하지만 일반적으로는 DBMS의 부모 프로세스도, 클라이언트를 응대하는 자식 프로세스도 모두 운영체제에 의해 관리되므로 DBMS가 이를 컨트롤 할 수 있는 방법은 존재하지 않는다. Policy vs. Mechanism 은 부모 프로세스에게 자식 프로세스에 대한 관리 기능을 제공해보자는 아이디어에서 등장했다.즉, 어떤 스케줄링 알고리즘 (Mechanism) 을 사용할 지는 운영체제가 결정하되, 그 알고리즘을 활용하는 정책(Poli..
Real-Time System 은 외부의 이벤트에 대해 정해진 시간 안에 적절하게 반응해야 하는 시스템이다.디스크 플레이어를 예로 들면, 디스크에 담긴 디지털 음원 데이터를 바로바로 디코딩해야 끊김없이 노래를 들을 수 있다.자동 조립 로봇, 자동 항법 시스템과 같은 경우도 모두 실시간 시스템의 한 예시이다. 실시간 시스템은 올바른 답을 '정해진 시간 안에' 내놓는 것이 매우 중요하다.정해진 시간 안에 답을 내놓지 못하는 실시간 시스템은 잘못된 답을 내보내는 시스템과 똑같이 나쁜 시스템이다. 실시간 시스템은 크게 2가지로 구분된다. 1. Hard Real Time : 절대적인 데드라인이 반드시 지켜져야 한다.2. Soft Real Time : 때때로 데드라인을 못 지켜도 (바람직하지는 않지만) 괜찮다. 미..
