지난 글에서 프로세스를 메모리에 올리는 다양한 방법을 고민하면서, 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 이고, 아니라면 ..

Memory & Process프로그래머가 원하는 이상적인 메모리는 용량도 크고, 입출력도 빠르고, 저장된 데이터도 망가지지 않는 메모리일 것이다.하지만 현실적으로 입출력이 빠른 메모리는 용량당 비용이 점점 높아지다보니, 용도에 맞춰 다양한 특징을 가진 메모리를 계층구조로 설계한다. 먼저 용량은 작지만 입출력이 빠르고 비싼 메모리는 cache 로 계층 상단에 두고중간 용량과 속도, 중간 가격대를 가진 메모리는 main memory 로 중간에 두고큰 용량과 낮은 속도, 싼 가격대를 가진 저장장치는 디스크 저장공간으로 제일 하단에 둔다. 메모리를 관리하는 memory manager 는 운영체제의 일부로서 메모리 계층 구조를 관리한다.또한 어떤 메모리의 어떤 부분이 사용되고 있고, 사용되지 않고 있는지 추적하며..

Ligntning Network비트코인을 통해서 어떤 상품을 결제한다고 하면, 기존의 비트코인 프로토콜 상에서는 최소한 10분은 기다려야 안심하고 상품이나 서비스를 제공받을 수 있다. 내가 비트코인을 전송하는 트랜잭션이 블록에 포함되어서 컨펌되려면 10분의 시간이 필요하기 때문이다.만약 그 금액이 크다면 판매자 입장에서는 1컨펌으로는 안심할 수 없으니 더 긴 시간을 기다려서 충분한 수의 컨펌이 이루어질 때까지 기다려야 안심하고 상품이나 서비스를 제공할 수 있을 것이다. 라이트닝 네트워크 (줄여서 LN이라고도 한다.) 는 이 문제를 해결하기 위해, 비트코인 프로토콜을 기반의 즉각적인 페이먼트를 할 수 있는 프로토콜이다. 그래서 비트코인을 첫 번째 레이어 프로토콜로 봐서 LN을 그 위에 세컨드 레이어로 프로..

컨센서스컨센서스는 말 그대로 '합의'를 말한다.비트코인에서 컨센서스라고 하면, 비트코인을 채굴하는 채굴자들 사이에 공통적으로 합의하고 있는 내용을 말한다.특히 비트코인에서 중요한 합의는 Canonical Block Chain에 대한 합의가 중요하다.각각의 노드마다 생각하는 Canonical Block Chain이 다르다면, 누구는 어떤 블록이 유효하다고 하고, 누구는 유효하지 않다고 말할 것이기 때문이다. 또한 블록체인은 일종의 은행장부와 같다.어떤 노드는 이 블록체인에 따르면 A가 100만원을 갖고 있다고 해서 A가 100만원을 송금하려고 하는데, 어떤 노드는 A가 50만원 밖에 갖고 있지 않다고 여겨서 거부하면 A입장에서는 난 100만원을 갖고 있는데 왜 50만원으로 인식이 되는지 이해할 수 없을 것..

데이터베이스에서는 다양한 이유로 레코드를 정렬해야 할 때가 있다. - order by 와 같은 SQL을 처리해야 할 수도 있고- 트리 인덱스에 데이터를 많이 넣고자 할 때도 정렬이 필요하고- projection 연산 결과로 중복을 제거할 때도 정렬이 유용하며- 조인을 구현할 때 정렬을 사용하여 조인할 수도 있다. 우리가 흔히 쓰는 정렬 알고리즘은 in place 방식이라고 하더라도 O(N)의 공간복잡도가 필요하다.하지만 요즘 메인 메모리의 크기가 점점 늘어나고는 있음에도 처리해야 할 데이터는 너무 많아서 메인 메모리만으로는 모든 데이터를 한번에 정렬할 수 없다.그렇다고 디스크를 메모리처럼 보고 정렬하기에는 너무 많은 입출력 비용이 발생하기 때문에 디스크 접근 비용을 최소화하면서 적은 메모리로 데이터를 정..

SQL 문장을 실제로 컴퓨터가 실행할 때는 어떤 과정으로 실행될까?먼저 SQL은 확장된 형태의 관계 대수로 변환된다.그리고 이 관계 대수식을 기반으로 '질의 처리 계획'을 만드는데, 이는 관계 대수 연산자를 노드로 하는 트리로 표현된다.트리의 각 노드에는 해당 연산자가 어떤 알고리즘을 사용할 것인지 표시하는 라벨이 있다.이렇게 관계 대수 연산자는 질의 수행의 기본 단위가 되며, 이 연산자들의 동작을 구현하는 것은 최대 성능을 위해 최적화 되어 있다. 시스템 카탈로그DBMS가 쿼리를 처리할 때, 어떻게 처리할 지 결정하는 과정에서 테이블의 구조와 인덱스 등의 데이터를 참고한다.이 정보는 '시스템 카탈로그'라는 특별한 '테이블' 에 저장된다. (데이터 딕셔너리, 카탈로그라고 부르기도 한다.)실제 테이블 데이..