OS - 8. Memory Management

1. 기본 하드웨어

  

 1. CPU가 직접 접근할 수 있는 유일한 범용 저장장치는 주 메모리와 프로세서 자체에 내장되어 있는 레지스터이다.

 2. CPU에 내장되어 있는 레지스터들은 일반적으로 CPU clock의 1cycle내에 접근이 가능하다. 

 3. CPU와 주 메모리 사이의 접근 속도를 높이기 위해 캐시를 이용했다.

 4. 시스템이 올바르게 동작하는것을 보호하기 위해 각각의 프로세스는 독립된 메모리 공간을 가지도록 한다.

 5. 프로세스의 독립된 공간은 base reg와 limit reg로 구별한다.

       

 5. 특정 프로세스가 다른 프로세스나 운영체제의 메모리 영역으로 접근할려고 할 시 트랩을 발생시켜 막는다.

 6. base reg와 limit reg는 운영체제(커널모드)에 의해서만 로드된다. 

 

2. 주소의 할당

  

 1. 컴파일 시간 바인딩 : 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다. 항상 프로그램이 실행되면 컴파일 시 입력된 해당 메모리 주소에 코드가 올라간다. 만약 메모리 위치가 변경된다면 컴파일을 다시 해야한다.

 2. 적재 시간 바인딩 : 프로세스가 메모리 내 어느 위치로 올라갈지 알 수 없기 때문에 컴파일러는 상대 주소로 하여 프로그램의 코드를 재배치 가능 코드(stub)로 만들어야 한다. 실제 메모리에 올라갈 때 해당 위치 주소와 바인딩된다. 

 3. 실행 시간 바인딩 : 해당 함수가 실행될 때 메모리에 올라와 바인딩된다. 따라서 실행 중 주소가 변경될수 있다. 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면 우리는 "바인딩이 실행 시간까지 허용되었다"라고 말한다.

exe 파일 크기는 컴파일 시간 바인딩이 가장 적으며, 실행에 대한 필요 메모리 크기는 실행 시간이 가장 작다. 단 실행 시간 바인딩은 속도가 느리다.

3. 논리 주소와 물리 주소 공간

  

  CPU가 사용하는 주소는 논리 주소라 하며 메모리에서 사용되는 주소를 물리주소라 한다. 컴파일 시간 바인딩과 로드 시간 바인딩은 논리 주소와 물리 주소가 같다. 그러나 실행 시간 바인딩은 로드가 된 주소가 실행하면 서 변경 될 수 있기 때문에 논리 주소와 물리주소가 다를 수도 있다. 이때 해당하는 논리 주소를 우리는 가상 주소라고 부른다.

  프로그램의 실행 중 가상 주소는 알맞은 물리 주소로 변경해 주어야 한다. 이러한 작업을 하는 하드웨어 장차가 메모리 관리기(MMU)이다. base reg를 우리는 재배치 레지스터라고 부르며 base reg가 10000을 가리키고 CPU 가상주소가 200을 가르키면 실제 물리주소 10200을 가르키는 것이다. 이러한 방식 때문에 사용자는 실제 프로세스가 올라가있는 메모리 주소를 알 수 없다.

4. Dynamic Loading

  

  동적 적재란 각 루틴이 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기하고 있다. 먼저 main 프로그램이 메모리에 올라와 실행되고 다른 루틴을 호출한다. 만약 호출한 루틴이 메모리에 없으면 재배치 가능 연결 적재기(relocatable linking loader)가 불려져 요구된 루틴을 메모리로 가져오고 테이블에 기록한다.

 

5. Dynamic Linking

  

  1. 동적 적재에서는 적재를 실행 시까지 미룬 것이고 동적 연결은 연결을 실행 시기까지 미루는 것이다.

  2. 동적 연결은 주로 시스템 라이브러리에 사용된다.

  3. 동적 연결에서는 라이브러리를 부르는 곳마다 스텁이 생긴다.

  4. 스텁은 해당 라이브러리를 어떻게 찾을 것인가르 알려주는 작은 코드 조각이다.

  5. 라이브러리는 메모리에 적재되어 있을 수도 있고 디스크에 있을 수도 있다. 스텁은 실행될 때 메모리내 라이브러리 존재 여부를 확인하고 디스크에서 가져온다. 이후 호출한 라이브러리 루틴의 주소를 찾고 자기 자신과 대체한다.  

6. Shared Libraries

  

  동적 연결은 라이브러리 루틴이 변경될 때 유용하다. 라이브러리는 새로운 버번으로 교체될 수 있고, 그렇게 되면 해당 라이브러리를 사용하는 모든 프로그램은 자동적으로 이 새 라이브러리를 사용하게 된다. 시스템 내에는 여러 버전의 라이브러리가 존재할 수 있으며 각 프로그램은 라이브러리의 버전 정보를 가지고 있어야한다. 

7. Swapping

  

  1. 스와핑은 실행 중에 있는 프로세스가 실행 중에 임시로 예비 저장장치로 보내어졌다가 실행을 계속하기위해 다시 메모리로 돌아오는 것을 말한다. 

  2. 스와핑을 사용함으로서 메모리보다 많은 프로세스를 실행할 수 있다.

  3. 비동기적으로 입출력을 수행중인 프로세스를 스왑 아웃을 하면 문제가 발생한다. 이를 해결하기 위한 방법으로는 입출력을 하고 있는 프로세스는 스와핑을 하지 못하게 하거나 입출력을 프로세스가 직접하는 것이 아니라 운영체제와 버퍼가 하게 한다. 후자는 오버헤드가 추가된다.

8. 모바일에서의 스와핑

  

  모바일 시스템은 어떠한 형태의 스와핑도 지원하지 않는 것이 일반적이다. 일반적으로 모바일 시스템의 저장장치는 일반 하드 디스크와 달리 쓰기 횟수가 정해져 있는 플레시 메모리를 사용한다. 스와핑을 대신하여 IOS에서는 자유 메모리가 어느정도 떨어지면 응용에게 자발적으로 메모리를 반환하도록 요청한다. 안드로이드는 응용을 종료하여 공간을 확보하지만 빠르게 재시작을 할 수 있도록 종료전 응용 상태를 메모리에 저장한다.

9. 연속 메모리 할당

  

  초기 메모리 할당 방법중의 하나이다. 메모리는 일반적으로 운영체제를 위한 부분과 사용자 프로세스를 위한 부분으로 나누어 진다. 연속 메모리 할당 시스템에서는 각 프로세스는 다음 프로세스를 포함하는 영역과 연속된 하나의 메모리 영역을 차지하게 된다.

1. 메모리 보호 : 앞서 말했듯이 시스템은 base reg와 limit reg로 프로세스 메모리를 보호할 수 있다. base reg는 재배치 레지스터라고도 불린다. 디스패처는 문맥 교환을 일환으로 재배치 레지스터와 상한 제리스터에 정확한 값을 적재하고 물리적 주소는 이 레지스터들의 값을 참조해서 확인하기 떄문에 다른 프로그램으로부터 프로그램을 보호할 수 있다.

2. 메모리 할당 : 가장 쉬운 방법은 메모리를 고정된 크기로 분할하는 것이다. 각 분할마다 하나의 프로세스를 가진다. 한 분할이 비게 되면 새로운 프로세스가 성정되어 들어오게 된다. 그러나 이 방법은 현재 사용하지 않는다.

 다음 분할 방법은 가변 분활 기법으로 운영체제가 메모리의 어떤 부분이 사용되고 사용안되는지 파악하는 테이블을 유지함으로 효율적으로 메모리를 사용한다. 이 때 사용되는 부분 사이의 사용되지 않는 부분을 hole이라고 부른다.

 복수의 hole 중 프로세스가 올라갈 hole을 정하는 방법에는 여러개가 있지만 다음 3개가 가장 일반적이다.

• 최초 적합 : 첫 번째 사용 가능한 가용 공간을 할당한다.

• 최적 적합 : 사용 가능한 공간들 중 가장 작은 것에 할당한다.

• 최악 적합 : 가장 큰 공간에 할당한다. 

3. Fragmentation(단편화) : 적재와 제거가 반복되다 보면 작은 hole들이 많이 발생하게 되고 이러한 홀들이 합치면 충분한 공간을 만들지만 분산되어 적재를 못할 때 외부 단편화가 발생한다. 외부 단편화는 압축을 하여 사용중인 것들을 한군데로 몰고 자유 공간을 한쪽으로 몰아 큰 가용공간을 만드는 방법이다. 그러나 비용이 많이 든다.

 또한, 기본적 분할 단위를 1bit가 아니라 특정 블록 단위로 분활되어 있는데 이때 이 단위보다 작은 크기를 할당할 경우 남는 공간이 생기게 된다. 이 역시 사용 못하는데 이를 내부 단편화라고 한다.

10. Segmentation

  

  1. 기본방법 : 전체 프로그램을 Main, sub, 라이브러리, 스텍, 힙 등과 같이 몇개의 세그먼트(그룹)으로 나눈다. 그리고 세그먼트에 번호를 붙여 "0번(Main)의 3번째 명령문"과 같이 접근한다. 이렇게 하면 나뉘어진 그룹은 연속적으로 있을 필요가 없어진다.

  2. 하드웨어 : 프로그램에 대해서 base와 limit가 필요하듯이 세그먼트에도 base와 limit가 필요하다. 이러한 정보를 세그먼트 테이블이 가지고 있다.

CPU가 가지는 가상 주소는 세그먼트 번호 + Offset이 된다.

11. Paging

  

  1. 기본방법 : 물리 메모리는 프레임이라 불리는 불록 단위로 나누어지고 논리 메모리는 페이지라 불리는 블록 단위로 나누어 진다. 이 단위를 같게하면 외부 단편화가 사라지게 된다. 프로세스는 특정 단위로 분할되어 메모리로 올라가는데 세그먼트 때와 마찬가지로 연속적으로 있을 필요가 없다. 대신 메모리상 어디에 있는지 위치를 알려주는 페이지 테이블이 필요하다. 

세그먼트 테이블과 다르게 페이지 테이블은 페이지 크기로 나뉘어진 메모리의 번호(프레임 번호)를 저장한다. 논리 주소는 "페이지 번호 + offset"이며 페이지 테이블로 인해 페이지 번호는 프레임 번호로 변경된다.

페이징 기법는 외부 단편화는 없앨 수 있어도 내부단편화는 존재한다. 페이지의 크기가 작아지면 내부 단편화가 줄어든다. 그러나 페이지 테이블 크기가 커쳐 테이블이 차지하는 공간이 낭비된다.

운영체제는 메모리를 관리하기 떄문에 물리 메모리의 자세한 할당에 대해 파악해야한다. 어느 프레임이 할당됬었고 사용가능한지 총 몇개인지 등을 알아야한다. 이러한 정보는 일반적으로 프레임 테이블이 가지고 있다. 만약 시스템에 여러 사용자가 있다면 사용자들은 모두 페이지 테이블의 복사본을 가지고 있어야 하며 항상 최신 상태로 유지해야 한다. 그래서 페이징은 context switch 시간을 증가 시킨다.

  2. 하드웨어 지원 : 페이지 테이블이 작을 경우에는 레지스터에 저장하여 속도를 올릴 수 있지만 대부분 컴퓨터는 페이지 테이블이 크다. 그래서 페이지 테이블을 메모리에 올려두고 페이지 테이블 기준 레지스터(PTBR)를 이용하여 페이지 테이블에 접근한다. 다른 페이지 사용할려면 이 레지스터만 변경하면 된다. 다만 이 방식은 특정 위치에 대한 정보를 얻기 위해서 메모리에 2번 접근을 해야한다. 이러한 시간을 줄이기 위해 TLB라는 하드웨어 캐시가 사용된다.

  추가 적으로 TLB에 저장된 페이지에 어느 프로세스의 페이지인지 알려주는 ASIDs를 저장하여 복수의 프로세스들의 페이지를 동시에 저장한다. 만약 ASIDs가 없다면 프로세스가 변경될 때마나 프로세스를 잘못된 접근에 대한 보호를 위해 TLB는 전부 flush가 되어야한다.

 TLB가 사용되었을때 메모리 접근 시간은 (TLB 적중률) * (메모리 접근시간) + (1-TLB 적중률) * (메모리 접근시간 X 2)이다.

  3. 보호 

1. 페이지 테이블에 보호 비트를 두어 해당 페이지가 읽기 전용인지 쓰기전용인지 제한할 수 있다. 만약 쓰기가 허용되지 않은 페이지에 쓰기를 시도할 시 운영체제가 트랩이 발생하도록 한다.

2. 페이지 테이블에 유효/무효 비트(1bit)를 둔다. 해당 비트는 페이지가 프로세스의 합법적인 페이지임을 알 수 잇다.

3. 대부분 프로그램은 특정 구간에서 일을 많이한다. 즉 페이지 테이블에 모든 페이지를 올릴 필요가 없다.  이러한 이유로 몇몇 시스템은 페이지 테이블의 크기를 나타내는 페이지 테이블 길이 레지스터(PTLR)을 제공한다.

  4. 공유 페이지 : 똑같은 프로세스를 다수의 사용자에게 제공할 때, 동시에 사용할 수 있는 즉, 재진입 가능코드 부분의 페이지는 공유해서 쓸 수 있다. 

12. Page Table Structure - Hierarchical Paging

  

 요즘 컴퓨터들은 2^32나 2^64개의 주소를 가진다. 그렇기 때문에 메모리의 크기도 커지며 페이지 테이블의 크기 역시 커진다. 이렇게 커진 페이지 테이블을 메모리에 모두 올리기에는 용양적 무리가 있다. 따라서 2단계 페이지 기법으로 페이지 테이블 자체를 다시 페이지화 시켜 부피를 줄인다.

 바깥 페이지에서 안쪽 페이지로 그리고 메모리로 들어간다고 해서 forward-mapped 페이지 테이블이라고 부른다.

13. Page Table Structure - Hashed Page Tables

  

 주소 공간이 32비트보다 커진면 해시 페이지 테이블을 많이 쓴다. 

해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있다. 각 원소들은 3개의 필드를 가지는 데 논리(가상) 주소, 물리 메모리 페이지 주소, 연결 리스트상의 다음 원소 포인터이다. 동작 원리는 다음과 같다.

논리 주소를 해시 함수안에 넣어 해당 알맞는 해시 테이블로 간다. 그리고 논리주소의 프레임 번호와 대응하는 연결리스트 상 원소를 찾는다. 해당 원소에서의 물리 페이지 주소와 논리 주소가 가지고 있던 offset을 합쳐 물리주소를 만든다.

14. Page Table Structure - Inverted Page Table

  

 물리 메모리 단위를 프레임, 가상 메모리 단위를 페이지이라고 한다. 프로세스마다 해당 프로세스의 페이지 테이블을 가지고 있는데 역 페이지 테이블은 프레임 전체에 대한 테이블이 있고 해당 테이블에는 각각의 물리메모리의 프레임과 특정 프로세스의 페이지와 매칭 시켜준다. 따라서 페이지 테이블의 페이지 개수는 물리 메모리의 프레임 개수와 같다.