tapito의 AVR 정복기 - 4부. RAM을 이용한 스택 구현

tapito의 AVR 정복기

4부. RAM을 이용한 스택 구현

(c) tapitolife

---

1. 스택?

    스택(Stack)은 컴퓨터에서 후입선출의 방식으로 데이터를 저장하는 자료 구조를 말합니다. 후입선출(Last-In First-Out, LIFO)은 말 그대로 가장 나중에 저장된 데이터가 출력될 때는 가장 먼저 출력된다는 의미로서 주로 함수를 실행할 때 적용되는 개념입니다. 문자열로 이루어진 수식을 첫 글자부터 하나씩 읽어 들이면서 함수가 보이면 일단 연산 버퍼에 기억해 두었다가 버퍼에서 함수를 하나씩 꺼내 쓸 때 스택의 구조를 이용하는데, 이를 그림으로 표현하면 아래와 같습니다.

   

   그림 1. Stack 자료 구조

2. 스택의 작동 과정

   • push

     push은 스택의 끝에 데이터를 추가하는 동작입니다.

   • pop

     pop은 스택을 이루는 데이터 중 가장 마지막 원소를 떼어 가져오는 동작입니다. pop 동작을 수행하면 스택에는 더이상 그 데이터는 존재하지 않게 됩니다.

   결국 pop과 push는 아래와 같은 그림으로 표현할 수 있습니다.

   

   그림 2. stack과 pop

3. Stack의 구현

   아래 회로는 3부에서 설명했던 RAM의 작동 방식을 토대로 간단하게 구현해 본 스택입니다. 실제 RAM이 작동되는 속도는 빠르지만, 여기서는 _delay_ms 함수를 사용해서 각 단계별로 지연시켜가면서 RAM의 작동을 확인해보도록 합니다.

   

   그림 3. stack의 구현 (클릭하면 크게 보입니다.)

   기호	품목	규격
   SW1~SW8	DIP 스위치	8비트 1개
   LED	LED	아무거나
   (저항)	저항	4.7k 1/8W로 통일
   POP, PUSH	Tact 스위치(누름 스위치)	아무거나
   (RAM)	RAM	SRAM (A625308A-70SF)
   (ATmega)	AVR	ATmega8535 DIP 타입

   펌웨어 소스

   /*************************************************************
    * (c) tapito http://tapito.tistory.com/                     *
    *                                                           *
    * main.c : stack test circuit                               *
    *************************************************************/
   #define F_CPU 16000000
   #define DELAY_TIME 20
   // 스택이 최대로 가질 수 있는 원소 수.
   // 회로상 RAM의 주소 중 A0~A7만을 사용하고 있으므로
   // 여기에서는 최대 256개
   #define MAX_STACK 0xFF 
   #include <avr/io.h>
   #include <avr/delay.h>
   
   int main()
   {
   	int memAddr = 0x00; // 가장 끝 원소가 있는 주소
   	int esp = -1;// 가장 끝 원소가 몇 번째 원소인지 기억할 변수
   
   	while(1)
   	{
   		switch(PINB & 0b11110000)
   		{
   			case 0b00100000 : // Push 버튼을 눌렀을 때 처리
   				// 스택이 이미 가득 찼다면, Push 명령 무시
   				if(esp >= 0xFF) { esp = 0xFF; break; }
   				DDRA = 0b11111111;
   				DDRB = 0b00001111;
   				DDRC = 0b11111111;
   				DDRD = 0b00000000;
   
   				PORTB = 0b00001111;
   				_delay_ms(DELAY_TIME * 5);
   				// 주소 버스로 주소를 출력한 다음... (이와 동시에 esp도 1 증가함)
   				PORTC = (memAddr + (++esp)) & 0xFF;
   				_delay_ms(DELAY_TIME * 5);
   				// 데이터 버스로 D에서 입력받은 값을 출력
   				PORTA = PIND; 
   				_delay_ms(DELAY_TIME * 5);
   				// 1. /CE를 LOW(=0V)로 만들어 칩 활성화
   				PORTB = 0b00000011; 
   				_delay_ms(DELAY_TIME * 5);
   				// 2. /WE를 LOW(=0V)로 만들어 데이터 버스에 있는 데이터를
   				// RAM이 받아들이도록 함.
   				PORTB = 0b00000010; 
   				_delay_ms(DELAY_TIME * 5);
   				// 3. 마무리
   				PORTB = 0b00000111; 
   				_delay_ms(DELAY_TIME * 5);
   				PORTC = 0b00000000;
   				_delay_ms(DELAY_TIME * 5);
   				PORTB = 0b00000000;
   
   				_delay_ms(DELAY_TIME);
   				break;
   			case 0b00010000 : // Pop 명령이 들어올 경우
   				// 스택이 비었다면 무시
   				if(esp <= -1) { esp = -1; PORTD = 0b00000000; break; }
   
   				DDRA = 0b00000000;
   				DDRB = 0b00001111;
   				DDRC = 0b11111111;
   				DDRD = 0b11111111;
   
   				PORTB = 0b00001111;
   				_delay_ms(DELAY_TIME * 5);
   				// memory 주소 설정
   				PORTC = (memAddr + esp) & 0xFF;
   				_delay_ms(DELAY_TIME * 5);
   				// /CE를 LOW로 만들어 칩 선택
   				PORTB = 0b00000011; 
   				_delay_ms(DELAY_TIME * 5);
   				// /OE를 LOW로 만들어 RAM이 해당 주소의 데이터를 보이도록 지시
   				PORTB = 0b00000001; 
   				_delay_ms(DELAY_TIME * 5);
   				// ATmega에서는 RAM으로부터 나오는 데이터를 받아들여서 PORTD로 전송
   				PORTD = PINA; 
   				_delay_ms(DELAY_TIME * 5);
   				// 마무리
   				PORTB = 0b00000111; 
   				_delay_ms(DELAY_TIME * 5);
   				PORTC = 0b00000000;
   				_delay_ms(DELAY_TIME * 5);
   				PORTB = 0b00000000;
   
   				// 끝 원소는 이제 삭제되었음
   				esp--;
   				
   				_delay_ms(DELAY_TIME);
   				break;
   		}
   	}
   
   	return 0;
   }
        

   	브레드보드로 만들어 본 스택 회로입니다. 협찬: 땅콩캬라멜(?)
   3부에서 손으로 직접 RAM을 제어하던 것을 이제 ATmega에 작성된 프로그램이 대신 제어합니다.

   
   
   데이터 모니터입니다. 어떤 데이터가 입력되고 있고 어떤 데이터를 출력하고 있는지 LED로 보여줍니다.
   
   
   RAM을 제어하는 3가지 신호:CE, OE, WE입니다.
   
   
   주소 버스입니다. LED를 통해 RAM에 접근하고 있는 주소를 보여줍니다.

   영상 1. stack과 pop 작동 영상