[컴퓨터구조] ch.8 중앙처리장치 (1) 스택 구조

Mano의 컴퓨터시스템구조 제3판, 프로텍 미디어, 김종상 옮김 도서를 정리, 요약하는 글입니다.

 

1. 스택 구조

- 대다수의 컴퓨터가 사용하는 기법은 스택 혹은 FIFO이다. 가장 나중에 저장되는 내용이 가장 먼저 꺼내지는 구조이다. 스택은 실질적으로는 수를 세는 역할만 하는 주소 레지스터를 가진 메모리이다. 실제 값이 삽입, 삭제 되는 것은 메모리 워드의 내용이다. 스택은 주소 레지스터(스택 포인터 = SP)를 가지고 있기만 하다. push는 스택의 꼭대기(top)에 집어 넣는 것이고 pop은 빼내는 것이다.

 

(1) PUSH 

SP ← SP + 1

M[SP] ← DR

if (SP = 0) then (FULL ← 1)

EMPTY ← 0

 

- 항상 push할 때는 먼저 SP를 1 증가시키고 그 위치에 저장한다. 

- 먄약 64개 워드를 가진 메모리 스택의 SP는 6비트일 것이다. SP는 000000에서부터 1씩 증가하다가 111111까지 증가할 것이고 그 후 +1을 하면 다시 000000이 될 것이다. SP = 0의 의미는 스택이 가득 찼다는 것을 의미한다.

- 어떤 것이든 주소에 저장되고 나면 empty 상태가 아니므로 EMPTY는 0으로 둔다.

 

(2) POP

DR ← M[SP]

SP ← SP - 1

if (SP = 0) then (EMPTY ← 1)

FULL ← 0

 

- 스택 top에 있는 것을 먼저 DR로 전달한다. 그 다음 SP를 1 감소한다.

- 어떤 것이라도 스택에서 나가고 나면 full이 아니므로 FULL은 0이 된다. 

- 만약 SP가 0일 때 (000000) pop이 수행되면 SP는 111111이 될 것이고, 가장 마지막에 들어간 값은 0에 들어갈 것이다. EMPTY = 1 일 때, pop하거나 FULL = 1 일 때, push하는 것은 잘못된 동작이 될 것이다.

 

2. 메모리 스택

- 스택을 CPU에 있는 RAM 메모리를 이용하여 구현할 수 있다. 즉 메모리의 일부를 스택으로 할당하고 르소세서 레지스터 중 하나를 SP로 쓴다. 다음 그림과 같이 구현할 수 있다.

 

- SP의 초기값이 4001일 때 스택의 주소가 감소되면서 커가는 모양을 가지고 있다. 따라서 스택의 push 동작은 다음과 같이 바뀌어야 할 것이다.

 

SP ← SP - 1

M[SP] ← DR

 

pop 동작도 다음과 같이 바뀌어야 한다.

 

DR ← M[SP]

SP ← SP + 1

 

- 이 마이크로 연산은 SP를 이용한 메모리 접근을 먼저 할 것인지 아니면 SP의 값을 먼저 갱신할 것인지에 따라서 순서가 바뀔 수 있다. 

 

3. 역 polish 표기

- 스택은 수식의 값을 구하는 데 효율적이다. 우리가 흔히 쓰는 수식인 infix 표현 방법은 컴퓨터가 이해하기 어렵다.

예를 들어서 A * B + C * D 이런 수식을 infix라 하는데, 이런 경우 A * B의 값을 계산해서 기억하고 C * D 값을 계산하여 기억하고 다시 둘을 더해야 해서 복잡하다.

- prefix 혹은 polish라고 하는 표현 방법은 피연산자 앞에 연산자를 놓는 방식이다. +AB라고 표현하는 것이다. 이를 반대로 하는 postfix 혹은 reverse polish라는 방식은 연산자를 앞에 두고 피연산자를 뒤에 놓는 방식으로 스택으로 표현하기 쉽다. 

 

-  AB*CD*+ 라는 수식이 있을 때, 왼쪽에서 오른쪽으로 읽어가면서 연산자이면 왼쪽에 있는 두 개의 피연산자에 대해서 연산하면 된다. 이 과정을 더이상 연산자가 없을 때까지 반복한다. 쉽게 괄호를 치면 편한다. (AB*)(CD*)+라고 두면 이를 다시 infix 수식으로 표현하면 (A*B)+(C*D)가 된다. 연산의 우선순위가 있을 때도 이를 고려하면 괄호 없이도 바꿀 수 있다.

 

4. 산술식 연산

- 이러한 역 polish 개념을 써서 레지스터와 스택으로 가장 효율적인 계산을 할 수 있다. 이는 컴퓨터와 전자식 계산기에서 쓰이고 있다. 특히 스택은 연속 계산을 포함한 길고 복잡한 문제를 취급할 때 효과적이다.

그림 출처 : https://www.youtube.com/watch?app=desktop&v=GKDtCqsM5uY

 

- 수식을 왼쪽에서 오른쪽으로 진행해나가면서 피연산자를 만나면 push하고 연산자를 만나면 두 개의 값을 pop하여 이를 연산자로 계산하여 스택에 push한다.