Memory Management

Address

메모리에는 주소가 있다. 이러한 주소에는 두가지 종류, 가상메모리주소와 물리적 메모리 주소가 있다. 프로그램이 실행되면 프로세스가 되며 독자적인 주소공간이 형성된다. 이때 효율적인 메모리 사용을 위해 CPU는 가상메모리(logical address, virtual address)를 참조하고 가상메모리는 실제 메모리(physical memory)를 참조하게 된다. 이러한 엮여있음을 주소바인딩이라고 한다. 

 

가상 메모리에서 물리적 메모리로 주소변환이 되는 순간은 크게 3가지 시점으로 나누어 볼 수 있다. 

 

Compile time binding 

컴파일 시점에 물리적 메모리 주소가 결정된다. 가상메모리 주소가 사실상 물리적 메모리 주소. 컴파일 바인딩에 의해 만들어진 코드를 절대코드(absolute code)라고 부른다. -> 절대코드의 주소를 바꾸기 위해서는 컴파일을 다시해야함

 

Load time binding

프로그램이 시작되서 메모리에 올라갈 때 논리적 주소와 물리적 메모리 주소가 바인딩된다. 로드타임에 만들어진 코드는 재배치가능코드(relocatable code) 라고 부른다. -> 결국 컴파일타임, 로드타임 바인딩은 프로그램이 시작될 때 주소가 결정된다.

 

Execution time binding(=run time binding)

프로그램 실행때 논리적 주소와 물리적 메모리 주소가 바인딩 + 프로그램 실행 이후에도 주소가 바뀔 수 있음 -> CPU가 주소를 참조할 때마다 주소 바인딩을 점검하기 때문에 하드웨어적인 지원이 필요하다.

---

하드웨어에서 메모리 주소 바인딩

런타임 바인딩에서 주소의 동적 바인딩의 하드웨어 지원은 Memory-Management Unit(MMU) 이 맡게된다. OS의 모듈이 아닌 주소 변환을 위한 하드웨어이다.  MMU에서 주소변환을 할 때는 두개의 레지스터를 사용하게 된다.

 

MMU에서 간단한 주소변환은 두가지 레지스터에 의해 동작하는데 바로 Relocation register 와 Limit Register 이다.

 

Relocation Register (=base register)

접근할 수 있는 메모리 주소의 최소값

 

Limit Register

논리적 주소의 범위

 

만약 위와같이 CPU에서 P1이 실행중이고 P1은 가상메모리에서 0번부터 3000번 주소, 물리메모리에서는 14000번부터 17000번 주소까지  사용하고 있을 때 CPU에서 346번 메모리를 요청하면

1. 시작위치+요청주소 = 논리적 주소

2. 시작위치+논리적 주소 = 물리적 주소

이기 때문에 이를 이용해서 CPU가 알맞은 메모리를 참조할 수 있게한다. 이를위해 base register에 논리 주소 시작위치를 저장해둔다. 프로그램이 만약 본인크기를 초과해서 메모리를 참조하는 것을 방지하기위해 프로그램 크기를 limit register에 저장해두고 범위를 넘어설경우를 대비한다. 

---

Dynamic Loading / Overlay / Swapping / Dynamic Linking

메모리에 동적으로 올린다는 것은 프로세스 실행시 미리 메모리에 다올리는게 아니라 필요할 때마다, 호출될 때마다 올리는 것이다. 보통 다이나믹 로딩은 OS단에서  좀더 상위 프로세스에게 라이브러리를 제공함으로써 권한을 넘겨 주로 프로그래머가 작성하게된다. 

 

메모리에 필요할 때 그때그때 올려둔다는 점에서 다이나믹 로딩과 같으나 예전 메모리 크기가 워낙 작을 때 메모리를 효율적으로 이용하기 위해서 큰 프로그램을 쪼개서 특정 부분이 실행되면 특정부분이 메모리에 올려 실행시키는 과정을 개발자가 수작업으로 진행했다. 따라서 이를 Manual overlay라고도 불렸고 매우매우 복잡했다. 다이나믹 로딩과의 차이점은 라이브러리를 통해 손쉽게 동적 주소바인딩을 했다면 오버레이는 라이브러리 없이 손수 한땀한땀 동적 바인딩을 한 것이다.

 

Swapping 은 프로세스를 일시적으로 메모리에서 backing store(하드디스크, swap area)로 쫒아내는 것이다. 

Swap out: 메모리 -> 하드디스크 (backing store) 

Swap in: 하드디스크 (backing store) -> 메모리

 

프로세스 상태에서 중기스케쥴러가 어떻게 swap 할지를 결정한다. 이때 CPU가 자주 사용하지 않는, 우선순위가 낮은 프로세스부터 swap out 시킨다.  이러한 swap time은 사실상 메모리와 하드디스크를 왔다갔다 하는 transfer time이 대부분 차지하며 이는 프로세스 크기에 비례한다. 

 

링킹이란 여러군데 존재하던 컴파일 된 파일들을 하나의 실행파일로 묶는 작업이다. 링킹 과정에서 내가 작성했던 코드, 혹은 내가 작성하지 않았지만 유용해서 가져다 쓴 코드들이 합쳐져 하나의 실행할 수 있는 파일로 만들어진다. 만약 사용한 라이브러리가 실행파일 코드에 포함된다면 Static Linking, 라이브러리가 실행시 연결되는 방식이라면 Dynamic Linking 이라고 부른다. 만약 Static linking 에서 100명이 printf() 함수를 가져다 쓴다면 100개의 카피 메모리가 사용될 것이고 다이나믹 링킹환경이라면 한개의 메모리주소를 100명이 공유하는 방식이다.

---

물리 메모리 할당

앞서 배웠듯이 일단 프로그램이 실행되면 스택구조를 통해 OS가 메모리 가장 밑단에 깔리면서 계속해서 상주하고 그 위로 사용자 프로레스들이 쌓이게된다. 이때 사용자 프로세스 영역 할당 방법에는  두 가지 연속적 할당/비연속적 할당 방법이 있다.

 

Contiguous allocation

연속적 할당은 앞선 예와 같이 가장 단순하게 첫번호부터 순차적인 주소에 메모리를 할당하는 방법이다.

 

Noncontiguous allocation

반면 비연속적 할당은 하나의 프로세스가 첫주소부터 순차적으로 메모리가 할당되는 것이 아닌 분산된 주소에 메모리가 올라가게 된다.  이러한 불연속 할당을 하는 방법은 크게 3가지 방법이 있다. - Paging, Segmentation, Paged Segmentation

---

Contiguous Allocation (연속할당)

연속할당에서는 두 가지 방식이 존재한다. - Fixed partition(고정분할) 방식과 Variable partiiton(가변분할) 방식이다. 

 

Fixed Partition (고정 분할 방식)

Fixed partition 에서는 기본적으로 메모리 주소를 미리 나누어 놓는다.  위 이미지 예시를 기준으로 만약 프로그램 A가 실행되면 미리 나누어놓은 공간 분할1 에 메모리를 할당한다. 그 다음에 프로그램 B를 할당하려하니 분할2 는 너무 작아서 이부분은 "외부 조각(external fragmentation)"으로 남기고 분할 3영역에 프로그램 B를 할당한뒤 분할 3영역의 남은부분은 "내부 조각(internal fragmentation)"으로 남긴다. 

 

Variable Partition (가변 분할 방식)

고정 분할 방식은 앞서 살펴보았듯이 프로세스 메모리와 미리 나누어둔 메모리 공간이 맞지 않으면 낭비가 심해진다. 그래서 가변분할 방식에서는 메모리를 미리 나누어놓지 않고 실행되는 프로세스를 스택구조로 위부터 쌓는다. 하지만 이러한 방식에도 여전히 외부조각 낭비가 생기는데 만약 프로그램B가 끝나고 프로그램D가 실행될경우 스택구조상 프로그램B는 그대로 외부조각 공간으로 남게된다. 

 

연속할당에서는 위 두가지 모두 어쩔 수 없이조각 공간이 생길 수 밖에 없다. 이러한 가용 메모리 공간을 Hole이라는 용어로 부른다.  그렇다면 연속할당에서의 최적화는 어떻게 Hole을 최소화해서 메모리를 할당할 것인가로 귀결한다. 그리고 할당 알고리즘은 크게 3가지 종류가 있다. - FirstFit, BestFit, WorstFIt

 

결론부터 말하자면 First Fit, Best Fit 방법이 Worst Fit보다 속도/공간 측면에서 더 나은 방법이다.FirstFit 방법은 원하는 만큼의 빈 공간을 찾는 오버헤드가 적고 Best Fit은 필요한 가장 최적화된 크기의 hole을 찾아 넣기 때문에 향후 미래를 생각하다면 적합한 방법이다. 

 

Compaction은 이러한 Hole들을 한 군데로 모아서 재사용하는 방법이다. Hole을 한군데로 모아 한 번에 쓰게되면 치명적인 단점이 하나 있는데 각 Hole들을 찾아 바인딩을 하는 과정자체가 매우 많은 비용이 소모된다는 점이다. 

---

 Noncontiguous Allocation (불연속 할당)

페이징(Paging)은 메모리를 고정된 크기의 페이지로 나누어 사용하는 기법이다. 고정된 크기가 정해져있다는 점에서 연속할당의 fixed partition과 비슷하지만 페이징은 메모리를 고정된 크기의 페이지로 나누어 프로세스를 비연속적으로 할당한다. 메모리 사용 효율이 높고 외부 단편화 문제를 줄일 수 있지만, 주소 변환이 복잡하고 페이지 테이블의 오버헤드가 있다는 단점이 있다. 

 

페이징의 구체적인 과정은 다음과 같다. 한 줄요약하자면 논리적 주소 - 물리적 주소 쌍을 통해 메모리에 접근하는 방식이다. 

 

1. CPU가 논리주소(페이지 번호 p)와 오프셋(d)을 준다.

2. 페이지 번호를 통해 페이지 테이블 주소를 찾아간다. 

3. 테이블주소에 오프셋을 더하면 물리적 메모리 주소를 찾아갈 수 있다. 

 

결국 페이징 기법을 이용하면 테이블을 이용해서 물리메모리에 접근할 수 밖에 없다.  따라서 모든 메모리 접근 연산은 2번의 memory access 가 필요하다. (페이지 테이블도 메모리에 저장되어 있음)

 

페이징에서의 오버헤드를 최적화하기 위해 자주 접근하는 주소를 저장해두는, 마치 캐쉬메모리 같은 테이블 공간을 두는데 이를 TLB(Translation Lookaside Buffer) 라고 부른다. 페이지 테이블에서 빈번하게 참조되는 메모리를 저장하기 때문에 주소변환을 위한 캐쉬메모리라고 볼 수 있다. 따라서 먼저 TLB를 조회해서 캐쉬히트면 바로 짝 맞추어 메모리접근 캐쉬미스나면 페이지 테이블로 가게된다. (TLB는 병렬로 접근하기 때문에 TLB보다 빠를 수 밖에 없다)

 

결국 TLB든 페이지 테이블이든 페이징 기법을 통한 메모리 할당은 2단계를 거쳐야한다. 2단계를 거쳐야하는 이유는 메모리 공간을 절약할 수 있기 때문이다.

1. 가상메모리는 기본적으로 필요한 메모리만 실제로 올리기 때문에 절약된다.

2. 동적인 메모리 할당이기 때문에 내부/외부 단편화를 최소화할 수 있다. 

결국 페이지 translation은 물리 메모리 시작점과 offset을 통해 물리적 메모리에 할당하게 된다. 

---

Memory Protection

페이징 기법을 통해 프로세스를 작은 단위로 나누어 관리할 때 물리 메모리를 찾아가는데 있어 페이지 테이블을 조회하게 된다. 페이지 테이블에서는 먼저 페이지 번호와 프레임번호를 조회후 물리주소를 확인한 뒤에 valid-invalid bit에서 1(Valid)을 확인한 후에야 물리 메모리로 접근하게 된다. 이러한 valid bit 덕분에 운영체제는 커널영역 주소를 접근하지 못하게 할 수 있거나 잘못된 물리주소 접근을 못하게 보호할 수 있다. 

 

만약 논리메모리가 페이지테이블에 따라 물리메모리로 갔는데 데이터가 없으면 운영체제는 페이지에 필요한 메모리를 디스크 -> 물리메모리에 다시 채워넣는다. 이를 페이지 폴트(page fault)라고 한다.  이때 valid/invalid bit을 통해 필요한 데이터가 있는지 바로 확인가능해서(invalid bit, 0) 굳이 물리메모리를 훑어보지 않아도 바로 페이지 폴트를 감지한다.

 

물리메모리 공간을 정략하기위해 페이지 테이블(메모리 탑재)을 만들었는데 문제는 페이지 테이블의 크기가 너무 커져버린다. 이러한 오버헤드가 너무 커지는 문제를 방지하기 위해 Inverted page table이 등장했다. 

 

기존에 페이지 위치와 시작점등 논리 메모리 주소를 참고하여 물리메모리를 찾아갔다면 이번에는 물리메모리 주소를 페이지테이블에 적어놓고 이를 조회한다.  예를들어 p를 찾기 위해 페이지 테이블 다 뒤진뒤 f번째 엔트리라는 것을 찾으면 f번째 자체가 물리메모리 주소가 되는 것이다. 이렇게 되면 페이지 테이블의 크기제한은 프로세스 수가 아닌 물리적 메모리 크기로 된다. 결국 공간복잡도를 절약했지만 페이지 테이블을 전부 뒤져야하기 때문에 시간복잡도는 희생된다.

 

"Shared code"는  여러 프로세스가 동일한 코드 영역을 공유하여 메모리를 절약하는 방법이다. 이를 통해 여러 프로세스가 공통으로 사용하는 데이터를 메모리에 한 번만 로드하고, 이 메모리 영역을 여러 프로세스가 참조할 수 있게 한다. 이러한 공유 가능한 코드를 read only 로 셋팅해서 올리는데 이러한 코드들을 Re-entry code(=pure code)라고 부른다. 따라서 shared code는 모든 프로세스의 logical address space 를 공유하고 있어야한다. 

---

Segment 

앞서 불연속 할당 방법으로 페이징을 배웠다면 또한가지 불연속 할당 방법으로는 세그먼트가 있다. 페이지와의 가장 큰 차이는 논리적 단위로 끊어진다는 것이다. 

 

따라서 프로그램은 여러 세그먼트로 구성되고 각 세그먼트에는 코드, 데이터, 스택이 존재한다. 

 

세그먼트 주소변환도 테이블주소변환과 비슷하다. 세그먼트 시작점에서 끝번호(offset)를 통해 물리메모리에 올라간다.

 

CPU가 메모리를 얻기위해 세그먼트 넘버와 offset을 던지면 세그먼트 번호는 세그먼트 테이블에서 주소위치를 찾아 물리 메모리 주소로 찾아가고 offset으로 물리 메모리 영역을 인식한다. 이때 세그멘트는 limit이라는 정보가 있는데 페이지는 크기가 다 똑같으니 상관없었지만 세그먼트는 크기를 알기위해서 limit이라는 정보를 테이블에 따로 두어 만약 offset보다 limit이 클경우 당연히 잘못된 요청이므로 바로 에러처리한다.

---

https://core.ewha.ac.kr/publicview/C0101020140425151219100144?vmode=f

반효경 [운영체제] 18. Memory Management 1