STUDY AND LESSON

조합논리회로

- 조합논리회로는 임의의 시간에서의 출력이 이전의 입력에는 상관없이 현재의 입력조합(0 또는 1)으로부터 직접 결정되는 논리회로이다. 이에 반해 순서논리회로는 외부로부터의 입력과 현재 상태에 따라 출력이 결정된다.

조합논리회로의 종류

반가산기, 전가산기, 병렬가산기, 반감산기, 전감산기, 디코더, 인코더, 멀티플렉서, 디멀티플렉서, 다수결회로, 비교기조합논리회로

1) 반가산기(Half Adder) : 반가산기는 1Bit짜리 2진수 두 개를 덧셈한 합과 자리올림수를 구하는 조합논리회로이다.

2) 전가산기(Full Adder) : 전가산기는 뒷자리에서 올라온 자리올림수조합논리회로

* 반가산기는 한 개의 AND 게이트와 한 개의 Exclusive-OR 게이트로 구성된다.

* 전가산기는 두 개의 반가산기 + 한 개의 OR 게이트로 구성된다.

3) 병렬가산기(Parallel Adder) : 병렬가산기는 n Bit로 된 2진수 A, B에 대한 덧셈을 n개의 전가산기(FA)를 이용하여 구현한 실질적인 가산기로, 전파 지연을 Carry Look Ahead를 사용한다.

4) 반감산기(Half Subtract) : 반감산기는 1Bit짜리 2진수 2자리에 대한 감산을 하는 회로이다.

5) 디코더(Decoder) : 디코더는 n Bit의 Code화된 정보를 그 Code의 각 Bit 조합에 따라 2의 n승 개의 출력으로 번역하는 회로로, 명령어의 명령부나 번지를 해독할 때 사용하는 회로이며 주로 AND 게이트로 구성되어 있다.

6) 인코더(Encoder) : 인코더는 디코더의 반대 기능을 하며 2의 n승 개의 입력선으로 입력된 값을 n개의 출력선으로 코드화해서 출력하는 회로이다.

7) 멀티플렉서(Multiplexer) : 멀티플렉서는 2의 n승 개의 입력선 중 한 개를 선택하여 그 선으로부터 입력된 값을 1개의 출력선으로 출력시키는 회로이다. 버스를 구성에 사용할 수 있고 한 개의 선을 선택하기 위해 n개의 선택선(Select Line)을 이용한다.

8) 디멀티플렉서(DeMultiplexer) : 디멀티플렉서는 한 개의 입력선으로 들어오는 정보를 2의 n승 개의 출력선 중 1개를 선택하여 출력하는 회로이다. 2의 n승 개의 출력선 중 한 개의 선을 선택하기 위해 n개의 선택선(Select Line)을 이용한다.

중앙처리장치

- 중앙처리장치(Central Processing Unit)는 사람의 두뇌와 같이 컴퓨터 시스템에 부착된 모든 장치의 동작을 제어하고 명령을 실행하는 장치이다.

- 중앙처리장치는 제어장치, 연산장치, 레지스터 그리고 이들을 연결하여 데이터를 전달하는 버스로 구성되어 있다.

제어장치

- 제어장치(Control Unit)는 컴퓨터에 있는 모든 장치들의 동작을 지시하고 제어하는 장치이다.

- 제어장치는 명령 레지스터에서 읽어 들인 명령어를 해독하여 해당하는 장치에게 제어 신호를 보내 정확하게 수행하도록 지시한다.

제어장치의 구성요소

1) 명령 레지스터 : 현재 실행중인 명령어의 내용을 기억하고 있다.

2) 명령 해독기(Decoder) : 명령 레지스터에 있는 명령어를 해독하는 회로이다.

3) 제어신호 발생기, 부호기(Encoder) : 해독된 명령에 따라 각 장치로 보낼 제어 신호를 생성하는 회로이다.

4) 제어 주소 레지스터(CAR) : 다음에 실행할 마이크로 명령어의 주소를 저장하는 레지스터로 Mapping의 결과값, 주소 필드, 서브루틴 레지스터의 내용들이 적재되어 있다.

5) 제어 버퍼 레지스터(CBR) : 제어 기억장치로부터 읽혀진 마이크로 명령어 비트들을 일시적으로 저장하는 레지스터이다.

6) 제어 기억장치 : 마이크로 명령어들로부터 이루어진 마이크로 프로그램을 저장하는 내부 기억장치이다.

7) 순서 제어 모듈 : 마이크로 명령어의 실행 순서를 결정하는 회로들의 집합이다.

8) 순차 카운터 :(Sequence Counter) : 디코더에 의해 선택된 번호에 해당하는 타이밍 신호를 생성한다.

연산장치

- 연산장치(ALU, Arithmetic & Logic Unit)는 제어장치의 명령에 따라 실제로 연산을 수행하는 장치이다.

- 연산장치가 수행하는 연산에는 산술 연산, 논리 연산, 관계 연산, 이동(Shift) 등이 있다.

- 연산장치는 가산기, 누산기(AC, Accumulator), 보수기, 데이터 레지스터, 오버플로 검출기, 시프트 레지스터 등으로 구성되어 있다.

레지스터

- 레지스터(Register)는 CPU 내부에서 처리할 명령어나 연산의 중간 결과값 등을 일시적으로 기억하는 임시 저장소이다.

- 레지스터는 플립플롭(Flip-Flop)이나 래치(Latch)들을 병렬로 연결하여 구성한다.

- 레지스터는 메모리 중에서 속도가 가장 빠르다.

- 레지스터의 크기는 워드를 구성하는 비트 개수만큼의 플립플롭으로 구성되며, 여러 개의 플립플롭은 공통 클록의 입력에 의해 동시에 여러 비트의 자료가 저장된다.

- 레지스터를 구성하는 플립플롭은 저장하는 값을 임의로 설정하기 위해 별도의 입력 단차를 추가할 수 있으며 저장값을 0으로 하는 것을 설정해체(CLR)라고 한다.

레지스터 간의 자료 전송

- 직렬 전송 : 직렬 시프트 마이크 오퍼레이션을 뜻하며 병렬 전송에 비해 속도가 느리다.

- 병렬 전송 : 하나의 클록 펄스 동안에 레지스터 내의 모든 비트, 즉 워드가 동시에 전송되는 전송 방식이다.

- 버스 전송 : 모든 레지스터들이 공통으로 이용하는 경로로 병렬 전송에 비해 결선의 수를 줄일 수 있다는 장점이 있다.

레지스터의 종류 및 기능

1) 프로그램 카운터(Program Counter) : 다음 번에 실행할 명령어의 번지를 기억하는 레지스터로 분기(Branch, Jump) 명령이 실행되는 경우 그 목적지 주소로 갱신된다.

2) 명령 레지스터(Instruction Register) : 현재 실행중인 명령의 내용을 기억하는 레지스터이다.

3) 누산기(Accumulator) : 연산된 결과를 일시적으로 저장하는 레지스터로 연산의 중심이다.

4) 상태 레지스터(Status Register) : 시스템 내부의 순간순간의 상태가 기록된 정보를 PSW라고 한다.

5) 메모리 주소 레지스터(Memory Address Register) : 기억장치를 출입하는 데이터의 번지를 기억하는 레지스터이다.

6) 메모리 버퍼 레지스터(Memory Buffer Register) : 기억장치를 출입하는 데이터가 잠시 기억되는 레지스터로 CPU가 데이터를 처리하기 위해서는 반드시 거쳐야 한다.

7) 베이스 레지스터(Base Register) : 명령이 시작되는 시작 번지를 기억하고 있는 레지스터이다.

8) 인덱스 레지스터(Index Register) : 주소의 변경, 서브 루틴 연결 및 프로그램에서의 반복 연산의 횟수를 세는 레지스터로 프로그래머가 내용을 변경할 수 있다.

9) 데이터 레지스터(Data Register) : 연산에 사용될 데이터를 기억하는 레지스터이다.

10) 시프트 레지스터(Shift Register) : 저장된 값을 왼쪽 혹은 오른쪽으로 1Bit씩 자리를 이동시키는 레지스터로 2배 길이의 레지스터라고도 한다.

11) 메이저 스테이터스 레지스터(Major Status Register) : CPU의 메이저 상태를 저장하고 있는 레지스터

* 메이저 상태 : CPU의 현재 상태를 말하는 것으로 인출, 간접, 실행, 인터럽트 상태가 있다.

버스

- 버스는 CPU, 메모리, I/O 장치 등과 상호 필요한 정보를 교환하기 위해 연결하는 공동의 전송선이다.

- 컴퓨터 내부 회로에서 버스 선(Bus Lines)을 사용하는 목적은 결선의 수를 줄이기 위함이다.

- 메모리나 입출력 장치가 제대로 동작하려면 버스를 통해 전달되는 제어 신호, 어드레스 신호 및 데이터 신호의 상호 시간적 관계가 잘 유지되어야 한다.

전송하는 정보에 따른 분류

1) 번지 버스(Address Bus) : CPU가 메모리나 입출력기기의 번지를 지정할 때 사용하는 단방향 전송선

2) 자료 버스(Data Bus) : CPU와 메모리 또는 입출력기기 사이에서 데이터를 전송하는 양방향 전송선

3) 제어 버스(Control Bus) : CPU의 현재 상태나 상태 변경을 메모리 또는 입출력장치에 알리는 제어신호를 전송하는 데 사용하는 양방향 전송선

버스 위치에 따른 분류

1) 내부 버스 : CPU 및 메모리 내에 구성된 BUS

2) 외부 버스 : 주변 입출력장치에 구성된 BUS

시스템 카탈로그

- 데이터베이스 관리자(DBA)의 도구로써 데이터베이스에 저장되어 있는 모든 데이터 개체들에 대한 정의나 명세에 대한 정보를 수록한 시스템 테이블 (즉, 하나의 작은 데이터베이스, 데이터 사전(Data Dictionary)이라고도 한다.

- DDL의 결과로 생성되는 기본 테이블, 뷰, 인덱스, 데이터베이스, 접근 권한 등의 데이터베이스 구조 및 성능 평가를 위한 통계 정보를 저장한다.

- 데이터베이스의 스키마 정보, 스키마들 간의 사상 정보, DBMS의 특정 모듈을 필요이 필요로 하는 정보를 저장한다.

- 시스템 카탈로그에 저장된 내용을 메타 데이터(Meta Data)라고 한다.

시스템 카날로그의 특징

- 시스템 카탈로그는 데이터베이스 관리 시스템이 스스로 생성하고 유지한다.

- 시스템 카탈로그 그 자체도 테이블로 구성되어 있어, 일반 사용자가 SQL SELECT문을 이용하여 내용을 검색할 수 있다.

- 사용자가 SQL의 DDL문을 실행시켜 기본 테이블, 뷰, 인덱스 등에 변경을 주면 데이터베이스 관리 시스템이 자동으로 시스템 카탈로그를 변경한다.

- 사용자가 SQL의 INSERT, DELETE, UPDATE문으로 시스템 카탈로그를 직접 갱신하는 것은 허용되지 않는다.

- 분산 시스템에서의 시스템 카탈로그는 보통의 릴레이션, 인덱스, 사용자 등의 정보를 포함할 뿐만 아니라 위치 투명성 및 중복 투명성을 제공하기 위해 필요한 모든 제어 정보도 포함하고 있다.

* 시스템 카탈로그(System Catalog) = 데이터 사전(Data Dictionary)

- DBA가 사용하는 도구

- 데이터베이스가 취급하는 모든 데이터 객체들에 대한 정의나 명세에 대한 정보를 가지고 있다.

- 사상들에 대한 정보도 가지고 있어 데이터 관리 뿐만 아니라 데이터베이스 이용에도 사용한다.

* 데이터 디렉토리(Data Directory)

- 데이터 사전에 수록된 데이터를 실제로 접근하는데 필요한 정보를 가지고 있다.

- DBMS에 의해서만 접근이 가능하다.

해싱

- 해싱은 Hash Table이라는 기억공간을 할당하고 해시 함수(Hash Function)을 이용하여 레코드 키에 대한 Hash Table 내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식이다.

- 해싱은 직접 접근(DAM) 파일을 구성할 때 사용되며 접근 속도는 빠르나 기억 공간이 많이 요구된다.

- 다른 방식에 비해 검색 속도가 가장 빠르다.

- 삽입, 삭제 작업의 빈도가 많을 때 유리한 방식이다.

- 키-주소 변환 방법이라고도 한다.

해시 테이블(Hash Table, 해시표)

- 해시 테이블은 레코드를 한 개 이상 보관할 수 있는 Bucket들로 구성된 기억공간으로 보조기억장치에 구성할 수도 있고 주기억장치에도 구성할 수 있다.

- 버킷(Bucket) : 하나의 주소를 갖는 파일의 한 구역을 의미하며 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.

- 슬롯(Slot) : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.

- Collision(충돌 현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상이다.

- Sysnonym : 충돌로 인해 같은 Home Address를 갖는 레코드의 집합이다.

- Overflow : 계산된 Home address의 Bucket 내에 저장할 기억공간이 없는 상태로 Bucket을 구성하는 Slot이 여러 개일 때 Collision은 발생해도 Overflow는 발생하지 않을 수도 있다.

해싱 함수(Hashing Function)

1) 제산(Division)법 : 제산법은 레코드 키를 해시표의 크기보다 큰 수 중에서 가장 작은 소수로 나눈 나머지를 홈 주소로 삼는 방식, 즉 h(K) = K mod Q이다.

2) 제곱(Mid-square)법 : 레코드 키 값을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식이다.

3) 폴딩(Folding)법 : 레코드 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식이다.

4) 기수(Radix) 변환법 : 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고 이를 다시 주소 범위에 맞게 조정하는 방법이다.

5) 대수적 코딩(Algebraic Coding)법 : 기 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식이다.

6) 계수 분석법(숫자 분석법) : 계수 분석법은 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식이다.

7) 무작위법 : 난수를 발생시켜 나온 값을 홈 주소로 삼는 방식이다.

Overflow 해결법

1) 개방 주소법(Open Addressing) : 선형 방법이라고도 하며 Collision이 발생했을 때 순차적으로 그 다음 빈 버킷을 찾아 저장하는 방법이다.

2) 폐쇄 주소법(Close Addressing) : Overflow된 레코드들을 별도의 Overflow 영역에 저장하고 Chain(Pointer)으로 홈 버킷에 연결한다.