[Operating System] 메모리구조

📍 메모리구조

프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 Load되어야 함
또한, 프로그램에서 사용되는 변수들을 저장할 메모리도 필요
따라서, 컴퓨터 운영체제는 프로그램의 실행을 위해 다양한 메모리 공간을 제공
프로그램이 운영체제로부터 할당받는 대표적인 메모리공간에는 코드(code)영역 데이터(data)영역 스택(stack)영역 힙(heap)영역 이 있음

코드(Code) 영역

• 메모리의 코드(Code) 영역은 실행할 프로그램의 코드가 저장되는 영역으로, 텍스트(Text) 영역이라고도 함
• CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리

데이터(Data) 영역

• 메모리의 데이터(data) 영역은 프로그램의 전역 변수와 정적(static) 변수가 저장되는 영역
• 데이터 영역은 프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸

힙(Heap) 영역

• 메모리의 힙(heap) 영역은 사용자가 직접 관리할 수 있는, '관리 해야하는' 메모리 영역
• 힙 영역은 사용자에 의해 메모리 공간이 동적으로 할당&해제
• 힙 영역은 메모리의 낮은 주소 → 높은 주소 방향으로 할당

스택(Stack) 영역

• 메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역
• 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸
• 스택 영역에 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 함
• 스택 영역은 푸시(push) 동작으로 데이터를 저장, 팝(pop) 동작으로 데이터 인출
• 후입선출(LIFO, Last-In Fist-Out) 방식에 따라 동작하므로, 가장 늦게 저장된 데이터가 가장 먼저 인출
• 스택 영역은 메모리의 높은 주소 → 낮은 주소 방향으로 할당

📖 메모리 구조를 나눈 이유

메모리 영역을 4가지로 나누는 이유는 우리가 어떠한 프로그램을 구현할 때 각각의 변수, 함수, 클래스 등이 호출되고 해제되는 시기가 다르기 때문!
만약에 어떠한 함수 내에서 한 번 사용되는 변수가 프로그램 처음부터 끝까지 메모리에 남아있게 된다면? == 메모리 낭비
어떠한 함수 내에서 값을 변경하고 함수가 끝나더라도 그 값을 유지했으면 좋겠는데 함수 종료와 동시에 그 값이 메모리에서 사라진다면?
이것을 방지하기 위해 메모리 구조를 나눔

---

📍 Queue와 Stack

📖 스택(Stack)

스택(stack)이란 쌓아 올린다는 것을 의미
후입선출(LIFO, Last In First Out) 방식의 자료구조

Stack의 특징

• 같은 구조와 크기의 자료를 정해진 방향으로만 넣을 수 있고 top으로 정한 곳만 통해서 접근 가능
• 가장 위에 있는 자료(top)는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료 위에 쌓임
• 자료를 삭제할때도 top을 통해서만 가능
• 스택에서 top을 통해 삽입하는 연산을 push, 삭제하는 연산을 pop이라고 함
• 비어있는 스택에서 원소를 추출하려고 할때 stack underflow라고하며 스택이 넘치는 경우 stack overflow라고 함

스택이 넘친다는게 무슨 말일까?
스택은 크기를 고정해서 사용하기 때문에 고정된 크기의 스택에 데이터를 계속 넣어서 넘치면 다른 메모리 영역을 침범하게 된다. 이것이 StackOverFlow

📖 스택(Stack)으로 큐(Queue) 구현

스택으로 큐를 구현하기 위해서는 2개의 스택 필요

A 스택이 input, B 스택이 output이라고 생각하면 됨
A 스택에 push하고 B 스택에 pop 하게 되면 선입선출 구조로 사용 가능

📖 큐(Queue)

Queue의 사전적인 의미는 (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것
선입선출(FIFO, First In First Out) 방식의 자료구조

Queue의 특징

• 지정된 곳을 통해서 삽입, 삭제하는 스택과는 다르게 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어짐
  이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 수행되는 곳을 리어(rear)라고 정하여 각각의 연산작업만 수행
  이때, 큐의 리어(rear)에서 이루어지는 삽입연산을 인큐(enQueue), 프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부름

• 큐의 가장 첫 원소를 front, 가장 끝 원소를 rear라고 함

• 큐는 들어올때 rear로 들어오지만 나올때는 front부터 빠지는 특성을 가짐

• 접근 방법은 첫 원소와 끝 원소로만 가능

• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제(FIFO방식)

즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫번째 원소가 되고 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 된다.

📖 큐(Queue)로 스택(Stack) 구현

제일 마지막으로 PUSH한 3이 제일 아래에 가도록 1,2를 POP하고 다시 순서대로 PUSH 해줌
이렇게 되면 가장 나중에 들어온 값이 큐의 첫번 째 자리에 위치
top()이나 pop() 메소드를 호출할 때 큐의 첫번째 값을 참조하면 된다