입출력 장치입출력 장치는 크게 3가지로 분류할 수 있다. - Block Device : 고정된 크기의 블록에 데이터를 저장하는 장치. 각각의 블록은 주소를 가지며 주로 512KB ~ 323768KB 의 크기를 갖는다. 대표젹인 예시는 Disk - Character Device : 운영체제와 character stream을 주고 받는 장치. 블록 구조가 없기에 주소 체계도 없고, 무언가를 찾는 동작도 하지 않는다. 대표적인 예시는 프린터, 마우스, 네트워크 인터페이스 - Other device : 기타 장치들. 클락, Memory-mapped screens 등이 있다. 위 그림은 대표적인 입출력 장치들의 데이터 전송속도를 보여준다.아래로 내려갈수록 입출력 속도가 빨라지며, 사용자와 직접 상호작용하는 ..
전자 상거래샘이 아마존에서 상품을 주문하면 TLS (SSL의 새로운 버전) 프로토콜을 사용해서 요청을 암호화하여 보낸다.이때 암호화를 하는 기본적인 방법은 이전 글에서 정리한 RSA를 사용하여 아마존이 제공하는 공개키를 통해 요청을 암호화한다.아마존은 수신한 요청을 자신의 비밀키로 복호화하여 내용을 확인하고 처리한다.따라서 내 요청이 다른 사람에게 탈취당하더라도 다른 사람은 내 요청 내용을 알아낼 수 없다. 그런데 아마존이 알려준 공개키를 어떻게 신뢰할 수 있을까?해커가 자신의 공개키를 대신 보내주고 마치 이게 아마존의 공개키인 것처럼 속일 수도 있지 않을까? 그래서 이를 보증하기 위해 verysign 과 같은 인증기관이 등장했다.이 기관은 이 공개키가 아마존의 공개키가 맞다는 것을 보증해준다. 아마존은..
암호학 : 비밀 메세지를 보내는 기법사이퍼 (chiper) : 원문 메세지의 내용을 훼손하지 않고 메세지의 각 문자를 다른 문자나 기호로 바꾸는 방법 시저 암호알파벳을 특정 key 숫자만큼 자리 이동시켜 재배열한 글자로 대체 3글자씩 뒤로 밀어서 abby를 deeb로 변환하였다. 이를 문자대신 숫자로 매칭해볼 수도 있다. 그러면 이렇게 3을 더한 값을 사용할 수 있다.물론 27은 범위를 벗어났으니 26으로 나눈 나머지를 취해서 1로 사용할 것이다. 키 값이 3이라는 것을 서로 알고 있다면, 복호화할 때는 역으로 그 값을 빼서 알파벳을 매칭시킨다.만약 음수가 나오면 26을 더한 값을 취하면 된다. (-1 + 26 = 25) 시저 암호를 사용하여 비밀 메세지를 주고 받을 때는 2가지 정보를 알아야 한다...
라이트닝 네트워크는 Fairness Protocol 이다.따라서 다음과 같은 특성을 갖는다. - Trustless operationLN에 존재하는 노드는 서로 믿을 필요가 없다.프로토콜 자체가 수학을 이용하여 치팅을 막아주는 것을 신뢰할 수 있기 때문이다. - Atomicity여러 payment channel 을 이어서 돈을 주고 받는 경우, 내가 보낸 돈은 상대방에게 전송되거나 전송되지 않거나, 둘 중 하나의 결과만 발생하는 원자성이 보장된다.중간에 보낸 돈이 멈춰서 안간다거나 하는 일은 발생하지 않는다.(만약 중간에 사기를 치는 사람이 있다면 돈을 돌려받을 방법이 있다.) - MultihopLN은 기본적으로 P2P 네트워크에서 시작했지만, 그 보안성이 end-to-end 로 확장되어 나와 직접 연결되..
기존의 CFG는 화살표 왼쪽 부분만 single variable 이기만 하면 되므로 문법 표현이 자유로웠다.하지만 그런 문법으로 표현하는 언어는 너무 자유도가 높아서 파싱하는데 시간이 오래 걸리는 단점이 있었다.(지난 글에서 p^(2w+1) 으로 계산했었다.) 그래서 이번 글에서는 파싱을 좀 더 편하게 하기 위해 CFG가 표현할 수 있는 언어의 범위를 제한하지 않으면서 문법을 간단하게 바꿀 수 있는 방법들을 정리해본다. 우선 첫 번째 방법은 기존의 CFG 문법을 유지하면서 이 문법을 단순화 하는 방법을 알아본다.두 번째 방법으로는 normal form 으로 바꿔서 문법을 표현하는 방법을 알아본다. 이때 편의를 위해서 지금부터 변환하는 문법은 모두 문장으로 λ 를 갖지 않는, λ-free language ..
Directory Entry이제 파일 시스템의 예시로 UNIX V7 의 파일 시스템이 어떻게 구현되어 있는지 살펴보면서 파일 관련 내용 정리를 마무리한다. UNIX V7 에서는 위와 같은 형태의 Directory Entry를 가진다.2바이트(=16 bit)는 I-Node 번호를 표현하는데 쓰이므로 총 2^16 가지의 번호를 표현할 수 있다.따라서 이 시스템에서 저장할 수 있는 최대 파일의 개수는 2^16개이다. (★)뒤의 14바이트는 파일 이름을 나타내는데 사용되었다. I-node 이번에는 UNIX V7에서 사용한 하나의 i-node의 구조를 살펴보자. (★)i-node 에는 파일의 속성이 들어있고, 그 밑에는 실제 파일의 content가 저장된 디스크 블록을 가리키는 주소가 들어있다.이때 V7 에서..
정규화는 테이블에 여러 정보가 중복해서 저장될 때 발생하는 문제를 해결하기 위해 테이블을 바꾸는 것을 말한다.여러 정보가 하나의 테이블에 중복해서 (이때의 중복은 정말 동일한 데이터가 여러개 들어있는 중복만을 말하지는 않는다.) 들어있는 경우 다음과 같은 문제가 발생할 수 있다. 1. 중복 저장 (redundant store)동일한 데이터가 여러 번 저장되는 것 2. 갱신 이상데이터를 수정할 때 중복 저장된 데이터 중 일부만 수정하는 것 3. 삽입 이상데이터를 삽입할 때, 이 데이터의 삽입을 위해 상관없는 다른 데이터도 함께 삽입되는 것 4. 삭제 이상데이터를 삭제할 때, 이 데이터의 삭제를 위해 상관없는 다른 데이터도 함께 삭제되는 것 정리하면 1번은 데이터가 중복저장되는 문제2번은 1번으로 인해 수정..
이번 글에서는 CFL라는 새로운 종류의 언어에 대해 어떤 문장이 이 CFL에 속하는지 판별하는 방법을 알아보자.먼저 결론을 말하면, CFL에 대해 membership을 판단할 때는 parsing을 통해 판단할 수 있다. Parsing파싱은 L(G)에 속하는 문장 w를 유도하는 production 의 나열을 찾는 것을 말한다. 위와 같은 문법이 주어졌을 때, aabb 와 abb가 이 문법으로 만들어지는 언어에 포함되는지 확인해보자. (membership problem)CFL에서 멤버쉽을 따질 때는 파싱 알고리즘으로 주어진 문장이 L에 포함되는지 확인할 수 있다.파싱을 했더니 w를 유도하는 production 시퀀스가 존재했다면 멤버인 것이고, 아니라면 멤버가 아닌 것이다. 1. aabbaabb는 다음과..
개요 위 그림은 전체 디스크를 나타낸 그림이다.디스크의 앞부분에는 MBR 이라는 부분이 있고, 그 뒤에 partition table 이 있다.파티션 테이블 뒤에는 파티션들이 존재하며, 각각의 파티션에는 실제 파일과 디렉토리가 저장되어 있다.이때 각 파티션은 독립된 하나의 파일 시스템을 갖는다. MBR(Master Boot Record)은 컴퓨터를 부팅할 때 사용한다.파티션 테이블의 엔트리 하나는 하나의 파티션과 매핑되어 있으며, 각 파티션의 시작 / 끝 주소 정보를 갖고 있다.파티션 중에 하나는 반드시 active 라는 마킹이 되어있고, 이 파티션이 부팅하는 파티션이다.(윈도우에서 운영체제가 들어있는 부팅 디스크를 지정하는 것과 비슷하게 생각하면 아해가 된다.) 컴퓨터를 부팅하는 과정을 살펴보면1. 롬에..
지난 글에서는 트랜잭션의 ACID 특징과 여러 트랜잭션이 병행적으로 들어왔을 때 이를 실행하는 스케줄의 직렬 가능성에 대해 정리하였다.이번 글에서는 트랜잭션의 실행 스케줄이 직렬가능하지 않을 때, ACID 특징을 지키면서 모든 트랜잭션이 직렬 가능하게 동작하도록 하는 동시성 제어 방법들을 알아본다. (동시성 제어라고 했지만, 동시성과 병행성이 다르다는 말이 여기에서 등장한다. 병행적으로 오는 트랜잭션은 '동시에' 도착할 수도 있지만 살짝 얽혀서 얼기설기 들어올 수도 있다.) 동시성 제어에는 크게 엄격한 2PL, Tompson Read & Write, Timestamp 방법이 있다. Strict 2 Phase Locking먼저 직렬가능하지 않은 문제가 발생하는 원인은 같은 데이터에 여러 트랜잭션이 동시에 ..
