지난 글에서는 트랜잭션의 ACID 특징과 여러 트랜잭션이 병행적으로 들어왔을 때 이를 실행하는 스케줄의 직렬 가능성에 대해 정리하였다.이번 글에서는 트랜잭션의 실행 스케줄이 직렬가능하지 않을 때, ACID 특징을 지키면서 모든 트랜잭션이 직렬 가능하게 동작하도록 하는 동시성 제어 방법들을 알아본다. (동시성 제어라고 했지만, 동시성과 병행성이 다르다는 말이 여기에서 등장한다. 병행적으로 오는 트랜잭션은 '동시에' 도착할 수도 있지만 살짝 얽혀서 얼기설기 들어올 수도 있다.) 동시성 제어에는 크게 엄격한 2PL, Tompson Read & Write, Timestamp 방법이 있다. Strict 2 Phase Locking먼저 직렬가능하지 않은 문제가 발생하는 원인은 같은 데이터에 여러 트랜잭션이 동시에 ..

File파일은 데이터를 장기 저장하는 저장 공간으로, 다음과 같은 특징을 갖는다. 1. 많은 양의 데이터를 저장할 수 있다.2. 저장된 데이터는 그 데이터를 사용한 프로세스가 종료되어도 남아있는다.3. 여러 프로세스가 동시에 데이터에 접근할 수 있다.  다음은 다양한 파일 확장자들의 예시를 보여준다.이중에서 gif는 무손실 압축을 지향하는 이미지 확장자이고, JPG는 압축률을 높이는 대신 어느 정도 손실을 감수하는 확장자이다.  파일의 내부 구조는 크게 위와 같이 3가지 종류가 있을 수 있다. (a)는 byte sequence 형태로 데이터를 저장한 것을 말한다.윈도우, UNIX와 같은 운영체제에서 이 방식을 지원한다. (b)는 Record Sequence 형태로 데이터를 저장한 형태이다.이때 레코드의 ..

트랜잭션은 일련의 읽기와 쓰기 동작으로 이루어진 하나의 실행 동작을 말한다.트랜잭션은 여러 사용자가 같은 데이터에 동시에 접근할 때, 데이터의 일관성을 유지할 수 있도록 도와주며, 장애 복구에도 유용하게 사용된다. 이를 위해서 트랜잭션은 다음의 4가지 성질을 만족해야 한다. ACID1. atomicity (atomic)트랜잭션을 구성하는 일련의 동작들은 모두 수행되거나 모두 수행되지 않아야 한다.따라서 트랜잭션을 수행하는 일반 사용자는 트랜잭션 내 동작들이 일부만 수행되다가 장애가 발생했을 때도 그 영향에 대해 걱정할 필요가 없다. 2. Consistency각각의 트랜잭션은 데이터베이스의 일관성을 유지해야 한다.즉, 동시에 수행되지 않는 각각의 트랜잭션은 언제나 일관된 데이터를 보고 있어야 한다.(수업 ..

https://www.postgresql.org/docs/current/using-explain.html 대부분의 DBMS는 Explain 이라는 명령어를 통해서 SQL의 질의 수행 계획과 비용을 계산해볼 수 있다.이를 통해 어떤 관계 대수 연산이 먼저 실행되는지도 알 수 있다.이러한 질의 수행 계획은 DBMS가 알아서 계산하며, 인덱스를 추가하는 등의 방법으로 더 좋은 질의 계획을 만들도록 유도할 수 있다.(인덱스를 추가한다고 항상 좋아지는 건 아니다)  EXPLAIN 키워드는 이렇게 수행할 SQL 앞에 EXPLAIN 키워드만 붙이면 끝이다.  data grip 에서 다른 테이블에 대해 수행했을 때는 이렇게 나타난다. 위 예시에서는 where 절 없이 단순히 모든 데이터를 조회하였으므로, 관계 대수 연..

하나의 프로세스 크기가 너무 커서 메모리에 다 올리지 못할 때 가상 메모리를 이용하여 프로세스의 일부만 메모리에 올리는 방법을 사용한다. 그리고 이를 구체적으로 구현하는 방법으로 지금까지 페이징 기법을 살펴보았다.그런데 이를 구현하는 추가적인 방법으로 Segmentation 기법도 존재한다.  먼저 virtual address space 가 지금까지 배웠던 것처럼 위와 같이 존재한다고 해보자.그러면 가상 주소 공간은 0부터 점점 주소가 증가하는 1차원 주소 공간으로 존재할 것이다. 이때 이 공간에서 '컴파일러 프로그램'을 실행한다고 해보자.컴파일러는 소스코드를 파싱하고 심볼 테이블을 만들고, 파스 트리를 만드는 과정을 수행할 것이다.이때 이 과정에서 나온 결과물들을 저장해야 하는데, 각각을 segment..

지난 글에서 프로세스를 메모리에 올리는 다양한 방법을 고민하면서, Virtual Memory 방식에 대해 정리하였다.하나의 프로그램 전체를 메모리에 올린 뒤 그때그때 실행할 프로그램을 교체하는 방식이 스와핑이었다면, 하나의 프로그램을 모두 메모리에 올리기에는 프로그램 용량이 너무 커서 다 못 올리는 경우 가상 메모리를 사용하여 프로그램이 사용하는 전체 메모리를 가상 공간에 표현하고, 가상 공간과 실제 메모리를 '페이지' 라는 단위로 매핑하여 그때 그때 필요한 가상 공간 영역을 실제 메모리에 올리는 방법을 사용했다. 이때 가상 공간 상 페이지 번호(virtual page number, VPN)와 실제 메모리 공간 속 페이지 (page frame number) 를 매핑하기 위해 페이지 테이블을 두었는데, 이..

이제 LN의 큰 흐름을 이해했으니, 디테일한 부분과 확장된 기능들을 살펴보자. 앨리스와 밥 사이에 P2P 네트워크를 통해 실제 거래가 발생하면 페이먼트 채널이 업데이트된다.이때 commitment transaction 을 추가하는 것은 둘 사이의 P2P 네트워크로 데이터만 전송하면 되므로 1~2초면 끝난다.이런 점에서 비트코인과 비교하면 매우 빠른 속도로 결제가 이루어진다. 또한 엘리스와 밥 사이의 페이먼트는 암호화 시켜서 보낼 수 있으므로 확실한 프라이버시가 보장된다.지난 글에서 처럼 카페 사장과 손님의 예시로 들자면, 앨리스가 밥의 카페에서 얼마나 자주 커피를 마시는 지는 앨리스와 밥만 알 수 있고, 제 3자는 알 수 없다. 모든 거래 내역은 숨겨지고, 그 최종 거래금액만 네트워크에 뿌려지기 때문이다..

Leftmost / Rightmost Derivation다시 복습해보면 Derivation(유도)는 문법으로부터 문장을 만드는 과정에 등장하는 Sentential Form 또는 Sentence를 말한다.이때 어떤 프로덕션이 S → ABC 이고, A, B, C 는 변수라고 해보자.A, B, C가 produce하는 결과물을 각각 a, b, c 라고 할 때, S에서 시작해서 문장을 만드는 과정의 선택지는 여러가지가 있을 수 있다. S => aBC => abC => abc 가 될 수도 있고,S => AbC => Abc => abc 가 될 수도 있다. 따라서 같은 문장을 유도하는 과정이 여러가지 인 경우에는 각 단계에서 어떤 것을 선택해야 할 지 고려해야 할 점이 많다보니 상대적으로 비효율적이라, 일관된 기준을..

Context-Free LanguageL = { aⁿbⁿ : n ≥ 0 } 위 언어는 펌핑 레마를 통해 RL이 아님을 증명한 적이 있다.그런데 이 언어는 프로그래밍 언어에서 등장하는 언어로 표현할 수 있다.homomorphism을 이용하여 h(a) = '(', h(b) = ')' 로 표현하면 위 언어는 언제나 올바른 괄호 문자열이 된다.(강의록에서는 nested programming language 라고 표현하였다.) 그런데 우리는 분명 이런 언어도 표현하기를 원할 때가 있다.따라서 RL 보다 더 넓은 범위를 커버할 수 있는 언어를 새로 정의해보려고 한다. 그리고 그 시작으로 Context-Free Language를 먼저 정의해보자. Def. 만약 G = (V, T, S, P) 를 구성하는 모든 prod..

위와 같은 언어 L을 DFA로 표현해보자.주어진 언어는 aa를 포함하는 임의의 a, b로 구성된 문자열을 문장으로 갖는다.  정규표현식과 DFA 로는 위와 같이 표현할 수 있다.충분히 어렵지 않다. 위 언어는 regular expression 으로 표현할 수 있고, 또는 DFA로 나타낼 수 있었으므로 Regual Language 이다. 이제 이 DFA를 파이썬 코드로 작성해보자.  DFA의 트랜지션 함수는 위와 같다.  DFA 함수를 위와 같이 정의한다.s 라는 전체 문장에서 심볼을 하나씩 읽으면서 현재 상태에서 이 심볼을 읽었을 때 그 다음 state를 transition map을 통해 결정한다.전체 심볼을 다 읽었을 때 최종 state가 final state에 속하면 Accepted 이고, 아니라면 ..