자료구조

 

• 한정된 자원 내에서 프로그램을 효율적으로 작동시키기 위해선 Memory에 대한 이해가 필수적
• 자료구조를 Memory 내에 잘 형성할 수 있어야 함

 

Memory(RAM) 구조

Memory 구조 블록도

1. Text

• 사용자가 작성한 프로그램 자체가 저장되는 부분. CPU에게 명령을 내리는 구체적인 명령어들이 저장됨
  • CPU가 이 영역에 저장된 명령어를 하나씩 읽어서 처리함

 

2. Data

• 명령어 외의 Data에 해당하는 부분이 저장되는 부분
• Global / Static Variable이 저장됨
  • main 함수 호출 전, 즉 프로그램 실행 전에 선언되어 프로그램이 끝날 때 까지 메모리에 남아있는 변수들
  • 프로그램 종료 시 사라짐

 

3. Stack

• 프로그램 실행 시 필요한 공간을 미리 예상해서 여러가지 용도로 사용하기 위해 잡아놓는 segment
  • 내부적으로 Stack이라는 자료구조를 사용하여 Stack이라는 이름이 붙음 (아래 설명)
• main 함수 내의 변수들과 함수 호출 시 함수의 지역변수와 매개변수가 저장되는 영역
  1. 함수 호출 시 할당되며, 함수 종료 시 해당 변수들을 Memory에서 해제 (Pop)

• 정적(Static)으로 할당되는 Memory
• Heap과 반대로 높은 주소에서 낮은 주소로 할당
• Compile 시 크기가 결정됨
  • Compile : 사용자가 작성한 코드를 컴퓨터가 실행 가능한 기계어로 변환하는 과정

* Stackoverflow

• 함수를 반복적으로 재귀호출할 경우, Stack 영역에 해당 함수의 지역변수가 계속 할당됨
• 이 때, OS에서 할당한 Stack 영역을 초과할 경우 Stackoverflow Error가 발생 (사용 가능한 최대 용량이 정해져있음)

 

3.1. 자료구조 관점에서의 Stack

Stack

• Stack은 무언가를 쌓는 것을 뜻함 : 즉 Data를 아래서부터 하나씩 쌓아올린 형태의 선형 자료구조를 뜻함
• 가장 처음 들어간 Data가 가장 마지막에 나오는 LIFO (Last In First Out, 후입 선출) 구조
  • 새로운 Data 입력 시 TOP가 가리키는 가장 위쪽의 주소에 쌓임
• 한 쪽 끝에서만 Data의 입출력이 가능하며, TOP으로 정한 곳을 통해서만 접근 가능
• 삽입 연산은 Push, 삭제 연산은 Pop 이라고 함
• 함수의 지역변수가 저장되는 영역

활용 예시

• Interrupt 처리, 정렬, 산술연산, 재귀 알고리즘, undo 등에 사용
  • Data를 임시적으로 저장하고 추후 역순으로 처리할 때 유용

장점

• 타 자료구조에 비해 구조가 간단하고 단순하여 구현이 쉬우며 Data 추가 / 제거가 빠르게 진행될 수 있음
• 정해진 크기의 Memory를 사용하여 Memory 관리가 용이함
  • 필요한 만큼의 공간만 사용

단점

• Static하게 할당되는 Memory이므로, 제한된 크기를 가짐
  • 이를 초과할 시 overflow가 발생함
• LIFO 구조를 지녀 중간의 Data에 접근하려면 마지막에 들어온 Data들을 순차적으로 제거해야 함 : 비효율적 접근

 

 

4. Heap

• 미리 크기를 알 수 없는 Memory가 사용하는 부분
• 사용자에 의해 관리되는 영역 
• 동적(Dynamic)으로 할당되는 Memory
  • Heap은 컴퓨터 사양에 따라 거의 무제한, 즉 컴퓨터의 하드웨어를 최대한 활용할 수 있음
  • OS가 안에 가상의 커다란 메모리가 있는 것 처럼 관리를 해줌
  • Application이 종료될 때 까지 Memory가 유지되므로, 할당받은 Memory는 반드시 반환을 해줘야 함
• Object Reference가 저장되는 영역
  • Heap 영역 내의 Object를 가리키는 Reference variable은 Stack에 적재
• 낮은 주소에서 높은 주소로 할당
• Runtime시 크기가 결정됨
  • Runtime : Compile 후 프로그램이 동작하는 시점

• Memory 구조에서 Queue의 역할을 함
  • Heap은 Memory 관련 용어, Queue는 자료구조 관련 용어

 

4.1. Queue

Queue

• Stack과 달리 먼저 들어온 Data가 먼저 나가는 FIFO (First In First Out. 선입선출) 구조
• Enqueue(삽입) 연산이 진행되는 Rear / Dequeue(삭제) 연산이 진행되는 Front 로 나뉨

활용 예시

• 입출력 처리 타이밍 조절용 버퍼 / 일정하지 않은 시간 간격으로 들어오는 데이터 처리에 활용 가능

 

Stack vs Queue

• Stack과 Queue 모두 컴퓨터 혹은 I/O 장치의 Data를 임시로 저장할 때 사용
  • 모든 Data를 Memory address와 Index를 지정해가며 사용하기 복잡함
  • 따라서 stack과 queue를 통해 array의 요소에 접근 가능하게 함
• Stack과 Heap은 같은 공간을 공유
  • 서로의 영역을 침범하는 경우 Stackoverflow / Heapoverflow 발생

 

 

---

참고 자료 : 

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!

 

https://velog.io/@seungho1216/CS-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EA%B5%AC%EC%A1%B0

[CS] 메모리 구조

 

https://beenii.tistory.com/161

메모리 구조에서 Stack과 Queue의 역할

 

https://velog.io/@alkwen0996/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack

[자료구조] | 스택(Stack)

 

https://hoehen-flug.tistory.com/30

[자료구조] 스택(Stack) 자료구조 알아보기 & Java 예제 코드

 

https://velog.io/@shindoyeon/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EA%B5%AC%EC%A1%B0

[운영체제] 메모리 구조

 

https://st-lab.tistory.com/198

메모리 구조 [Memory Structure]