기존의 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먼저 직렬가능하지 않은 문제가 발생하는 원인은 같은 데이터에 여러 트랜잭션이 동시에 ..

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..