8. 메모리 관리 전략

1. 기본적 하드웨어

- 주 메모리와 프로세서 내장 레지스터는 CPU가 직접 접근할수 있는 저장장치이다. 모든 실행되는 명령어와 데이터는 CPU가 직접적으로 접근할 수 있는 주 메모리오 레지스터에 있어야 한다.

CPU의 내장 레지스터들은 일반적으로 CPU 클록의 1 사이클내에 접근이 가능한데 , 메모리 버스를 통해서 전송되는 주 메모리의 경우에는 많은 CPU 클록 틱 사이클이 소요되고, 지면(Stall) 현상이 발생하기도 한다. 따라서 CPU와 주 메모리 사이에 캐시(Cache)메모리를 추가하여 속도의 차이를 완화시킨다.

이러한 속도 차이에 대한 고려뿐만 아니라 보호기법등 여러가지 구현방법들이 있다.

---

2. 메모리 보호 기법

- 프로세스가 합법적인 영역만 접근하도록 설정하는것이 필요하다. "기준(base)" 와 "상한(limit)"이라고 불리는 두 개의 레지스터를 사용한다.

기준 레지스터는 합법적인 물리 메모리 주소의 값을 저장하고, 상한 레지스터는 주어진 영역의 크기를 저장한다.

유저모드에서 실행되는 프로그램에 의해서 운영체제의 메모리 공간이나 다른 사용자의 메모리 공간으로의 접근이 일어나면 운영체제는 에러로 간주하여 "트랩(trap)"을 발생시켜 보호한다.

---

3. 주소의 할당 (Adderss Binding)

- 프로그램이 실행이 되기 위해서는 주 메모리로 올라와 "프로세스"가 되어야 한다. 사용하는 메모리 관리기법이 어떤것이냐에 따라 프로세스는 실행하는 동안 디스크와 주 메모리 사이를 왔다갔다 할 수 있다.

큐(Queue)에서 하나의 프로세스를 선택하여 메모리로 올린 후 실행하고 프로세스는 실행하는 동안 메모리에서 명령어 및 데이터를 접근한다. 이 프로세스가 종료되면 기억공간이 가용공간이 되고 다른 프로세스를 위해 사용된다.

프로그램은 여러 단계를 거쳐 실행되기 때문에 여러 단계를 거치면서 주소들은 여러 가지 다른 표현방식을 가지게 된다. 그러한 과정을 주소를 "바인딩(Binding)" 한다고 한다. 프로그램은 기호 주소를 사용하여 작성되는데, 프로그램은 실행 되기전 이런 기호 주소를 실제 주소로 바인딩 해줘야한다.

* 컴파일 시간 바인딩 : 컴파일러가 프로세스가 어디에 적재될것인지 알고 있다면 컴파일할때 주소를 바인딩 할 수 있다.

* 적재시간 바인딩 : 컴파일러가 프로세스가 어디에 적재될지 모르면 컴파일러는 기준 위치 주소를 사용하는 재배치 가능 코드를 생성한다. 실제 바인딩을 적재할 때까지 지연된다.

* 실행시간 바인딩 : 실행 도중에 프로세스의 적재 위치가 바뀔 수 있으면 바인딩은 실행될 때 이루어진다.

* 컴파일 시간 바인딩, 적재시간 바인딩, 실행시간 바인딩 등 컴퓨터 시스템에서 여러 가지 바인딩들을 어떻게 효과적으로 구현할 수 있는가가 목표이다.

---

4. 논리주소 공간, 물리주소 공간

- CPU가 생성하는 주소를 "논리주소"라고 하고, 메모리가 취급하는 주소를 "물리주소"라 한다. 프로그램이 실행 중에는 이 같은 논리주소를 물리주소로 바꿔주어야 한다. 이 작업은 MMU ( Memory Management Unit ) 에 의해 실행된다.

기준 레지스터를 이용한 방법으로는 기준 레지스터를 "재배치 (relocation) 레지스터"라고 부른다. 기준 레지스터 속에 들어있는 값은 주소가 메모리로 보내질 때마다 사용자 프로세스에 의해 생성된 모든 주소에 더해진다.

가상주소 = 논리주소 를 왜 사용하냐면, 쉽게 말하면 메모리에 프로세스를 로드, 스와핑 하는 시간을 적게 하려고 ,,,

---

5. 동적 적재와 동적 연결

- 메모리 공간의 이용률을 높이기 위해 "동적 적재"를 사용한다. 각 루틴은 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기하고있다. 동적 적재의 장점은 사용되지 않는 루틴들의 경우 미리 적재되지 않는다는 것이다.

정적 연결과 동적 연결의 차이점은 정적 연결은 프로그래밍 언어에서 제공하는 라이브러리를 프로그램과 결합하는 방식으로 모든 프로그램은 라이브러리의 복사본을 가지고 있기 때문에, 디스크와 주기억장치의 공간이 낭비된다.

하지만, 동적 연결은 동적 적재와 비슷한 개념으로, 각 프로그램에 라이브러리를 부르는 곳마다 stub 이 생기고, 이것은 주기억장치에 공유되고 있는 라이브러리 루틴에서 프로그램이 필요하는 루틴을 찾아주는 적은 양의 코드이다.

스텁은 라이브러리 루틴의 주소를 알아내게 되고 자신을 그 루틴의 주소로 대체하여 루틴을 실행한다. 다음에 그 부분이 호출되면 동적 연결 없이 직접 그곳의 라이브러리 루틴을 실행하면 된다.

이렇듯 라이브러리 갱신이 용이하며, 디스크 공간과 주기억장치 공간을 절약할 수 있다는 장점이 있다. 하지만 다른 주소 공간을 접근해야 하므로 운영제체의 지원이 필요하다.

---

6. 스와핑

- 

---

7. 연속 메모리 할당

- 일반적인 메모리 할당 방법중 하나인 연속 메모리 할당 기법이다. 주 메모리는 운영체제 뿐만 아니라 사용자 프로세스도 수용해야 한다.

메모리는 2개의 부분으로 나눌 수 있다. 1) 운영체제 영역과 2) 사용자 프로세스 영역으로 나눌 수 있다. 인터럽트 벡터가 중요한 요인이므로 보통 0 번지에 위치하기 때문에 운영체제는 보통 하위 메모리에 위치하게 된다.

각 사용자 프로세스는 연속된 단일 영역을 할당받는다. 보통 메모리를 할당할때 운영체제를 사용자로부터 보호, 사용자 프로세스를 다른 사용자 프로세스로부터 보호해야 하므로 베이스 레지스터와 상한 레지스터를 사용한다.

공간을 할당하는 가장 간단한 방법은 메모리를 똑같은 고정된 크기로 "분할(partition)" 하는 것이다. 이러한 가변 분할 기법에서 운영체제는 메모리의 어느 부분이 사용되고 있으며, 어떤 부분이 사용되지 않는가를 파악할 수 있는 테이블을 가진다. 사용 가능한 영역을 "홀(hole)"이라고 표현한다.

프로세스가 시스템에 들어오면, 입력 큐에 넣고 운영체제는 각 프로세스가 메모리를 얼마나 요구하는지, 사용가능한 메모리 공간이 어디에 얼마나 있는지 고려하여 공간을 할당한다. 일반적으로 메모리에는 다양한 크기의 자유 공간이 여기저기 분산된다. 운영체제는 이런 자유 공간속에서 각 프로세스가 필요로 하는 적절한 공간을 찾아내야 한다. 

* 최초 적합 ( First - Fit ) : 충분히 큰 첫번째로 발견한 홀에 할당한다.

* 최적 적합 ( Best - Fit ) : 충분히 큰 공간들 중 프로세스를 수용할 수 있는 가장 작은 홀에 할당한다.

* 최악 적합 ( Worts - Fit ) : 가장 큰 홀에 할당한다.

이러한 알고리즘에서는 " 외부 단편화 ( External Fragmentation ) " 가 발생하게 된다. 쉬는 공간들을 모두 합치면 충분한 공간이 되지만 너무 작은 조각들로 여러 곳에 분산되어 있을 때 발생한다. 최초 적합 혹은 최적 적합 전략 중 어느것을 사용하느냐가 단편화의 양에 영향을 주게 된다. 따라서 이런 문제를 해결하는 방법으로 " 압축 ( Compaction ) "이 있다. 이 기법은 메모리의 모든 내용들을 한 쪽으로 몰고 모든 자유 공간을 다른 한군데로 몰아서 큰 블록을 만드는 방법이다.

또한, " 내부 단편화 ( Internal Fragmentation ) " 이라는 것은 할당된 공간,메모리가 요구된 메모리보다 커서 현재 사용되지 않아 낭비되는 경우에 발생하는 것이다.

---

8. 페이징

- "페이징 ( Paging) " 이란 현재 가장 널리 사용되는 기법으로 논리 주소공간이 연속적인 공간에 모여 있어야 한다는 제약을 없앤다. 즉, 프로세스에게 연속된 공간을 할당해주지 않아도 된다는 것이다. 외부 단편화가 없고 압축도 필요없게 되므로, 주 메모리에 올라와 있던 부분을 디스크로 내보낼 때 디스크 상에 이들을 연속으로 수용할 수 이는 자유 공간을 찾느라고 고생할 필요가 없게 된다.

일반적으로 페이징은 하드웨어에 의존적이기 때문에 운영체제와 하드웨어를 연관시켜 구현한다.

기본 방법으로는 물리적 메모리는 "프레임 ( Frame )" 이라고 불리는 고정된 크기의 블록으로 나누어져 있고, 논리 메모리는 " 페이지(Page) " 라고 불리는 프레임과 같은 크기의 블록으로 나누어진다.

CPU에서 나오는 모든 주소는 페이지 번호(P) 와 페이지 변위 (d)로 나누어진다. 페이지 번호는 주 메모리에 존재하는 페이지의 기준 주소를 갖는 "페이지 테이블"을 액세스할때 사용된다. 이 페이지 주소에 페이지 변위를 더하면 메모리 장치로 전송될 물리 주소가 된다.

페이징을 사용하면 외부 단편화가 발생되지 않지만, 프로세스의 마지막 페이지는 프레임 크기보다 작을 수 있어서 최악의 경우 한 프레임의 대부분이 낭비될 수 있기 때문에 내부 단편화가 발생한다. 따라서 페이지의 크기를 줄여 내부 단편화를 줄일 수 있지만, 반비례하게 페이지 테이블의 크기가 커지게 된다.

페이징의 가장 중요한 특징은 메모리에 대한 사용자의 인식과 실제 물리 메모리는 명확하게 분리한다는 것이다. 사용자 프로그램은 메모리가 하나의 연속적인 공간, 메모리에는 이 프로그램만 있다고 생각하지만 실제로 프로그램은 물리 메모리 여러 군데에 프레임 단위로 존재하고 있고, 다른 많은 프로그램들이 올라와 있다. 

운영체제는 주 기억장치를 관리하므로 물리 메모리의 자세한 할당에 대해 파악하고 있어야한다. 즉, 어느 프레임이 할당되어 있나, 어느 프레임이 사용가능 한가, 총 프레임 등등을 알아야하고, 이런 정보는 프레임 테이블이라는 자료구조에 있다.

그리고 프로세스가 CPU를 할당 받았을때 하드웨어 페이지 테이블을 설정하는데 CPU 디스패치가 사용되므로 문맥교환 시간을 증가시킨다.

8-1. 페이지 테이블 하드웨어 구현

- 각각 운영체제는 페이지 테이블을 저장하기 위한 고유의 방법들을 가지고 있다. 대부분 각 프로세스마다 하나의 페이지 테이블을 할당한다.

페이지 테이블을 하드웨어로 구현하는 여러 가지 방법이 있는데, 가장 간단한 페이지 테이블은 전용 레지스터 집합을 사용하는것이다.

1) 전용 레지스터 집합

- 페이지 테이블이 작은경우에 사용한다.

- 대부분 현재 컴퓨터는 페이지 테이블이 1백만 항목에 이를 만큼 매우 크므로 , 페이지 테이블을 주 메모리에 저장하고 " 페이지 테이블 기준 레지스터 (PTBR, Page - Table - Base Register) " 라는 페이지 테이블을 가르키는 레지스터를 사용한다. 이를 사용함으로 다른 페이지 테이블을 사용하려면 단지 이 레지스터만 교체하면 되며, 문맥 교환시간을 상당히 줄인다.

- 하지만, 메모리의 접근시간이 문제점이다.

- 만약 주소 i에 접근하기를 원한다고 하면 페이지 테이블을 액세스해야 한다. 따라서 프레임 번호를 알아내면 페이지 변위와 더하여 실제 주소를 계산해 내고 메모리 내의 원하는 장소로 접근할 수 있다.  따라서 페이지 테이블을 위해 한번, 메모리 자체를 위해서 한번 총 2번의 메모리 접근이 필요하게 된다. 따라서 메모리 접근은 2배로 느려진다.

2) TLB ( Translation - Look - aside Buffers ) 

- 특수한 소형 하드웨어 캐시를 사용하는 방법이다.

- TLB 내의 항목은 키(key) 와 값(Value) 의 두 부분으로 구성된다.

- 페이지를 찾아달라고 요청이 들어오면 찾고자 하는 페이지를 동시에 여러개의 내부 키와 비교하여 페이지 번호가 같은것이 발견되면 그에 대응되는 프레임 번호를 알려준다.

- 비싸고 크기가 제한적이므로 페이지 테이블에 일부만 가지고 있다.

- 캐시처럼 TLB를 먼저 검색한 다음 찾고자 하는 페이지 정보가 없다면 주기억장치의 페이지 테이블을 참조한다.

- 주 메모리에서 찾은 프레임 번호와 페이지 번호는 TLB에 추가되어 다음 참조시 매우 빨리 처리할 수 있게된다.

8-2. 페이지 테이블 보호

- 

8-3. 페이지 테이블 공유

---

9. 페이지 테이블의 구조

1) 계층적 페이징 ( Hierarchical Paging )

- ㅇ

2) 해시 페이지 테이블

3) 역 페이지 테이블

---

10. 세그먼테이션

- 페이징에서 피할 수 없는 중요한 사항은 사용자가 생각하는 메모리와 실제 물리 메모리를 분리한다는 것이다. " 세그먼테이션 " 이란 보통 사용자들은 주 기억장치를 연속적 선형 공간으로 생각하지 않고, 순서가 없는 다양한 크기의 세그먼트의 집합으로 생각하는데 세그먼테이션이 이런 사용자 관점을 지원해주는 주기억장치 관리 기법이다.

우리는 프로그램을 메서드, 프로시저, 함수의 집합을 갖는 메인프로그램으로 생각한다. 객체, 배열 , 스택 변수들 등의 다양한 자료구조들을 가질 수 있다. 보통 스택, 수학 라이브러리, 메인 프로그램등을 이야기 할때 메모리 원소들이 어느 위치에 저장되는지에 대해서는 신경쓰지 않는다.

이러한 세그먼트의 길이는 다양하며, 프로그램 내에서 세그먼트 목적에 의해 정해진다. 

논리 구조 공간을 세그먼트들의 집합으로 정의한다. 각 세그먼트는 이름과 길이를 가진다.

세그먼트 테이블을 사용하여 세그먼트 주소와 물리적 주소간에 매핑을 하고 세그먼트 이름과 오프셋을 이용하여 주소를 지정하고 컴파일러가 사용자 프로그램을 번역할 때 자동적으로 세그먼트를 구성한다.

1) 코드 ,, 2) 전역 변수 ,, 3) 메모리 할당을 위한 힙,, 4) 각각의 스레드를 위한 스택,, 5) 표준 C 라이브러리 가 있다.