운영체체(9), Main Memory

Memory Management

메모리 관리의 목표

개발자가 메모리가 어떻게 되어있는지를 몰라도 쉽게 사용할 수 있도록 돕는다.

비싼 자원인 메모리를 효율적으로 사용할 수 있도록 하고, 메모리 프로텍션(두 개 이상의 프로세스를 독립적으로 만들어서)을 제공하는 목표를 가지고 운영체제가 메모리를 관리한다. 개발자가 몰라도 잘 사용할 수 있도록 추상화를 잘 해준다.

 

 

Batch programming

- monitor가 프로그램을 메모리에 올리고 이를 모니터링하다가 job을 처리하는 식으로 진행했다. 이때는 프로그램 하나가 메모리를 모두 썼다. 실제 ram의 주소를 사용해서 처리했다. 어차피 프로그램을 하나만 올려서 사용했기 때문이다.

 

Multiprogramming

- 여러 프로세스가 메모리에 올라가서 동작해야하기에 메모리 관리의 필요성이 생겼다. 메모리 관리에 대한 큰 틀은 이때 정의되었다.

 

Issues

- 메모리 관리는 여러개의 프로세스를 지원해야한다. 이를 위해 어떤 점을 고려해야하는지 생각해야한다.

- 실제 메모리는 1기가바이트인데 2기가 바이트 프로그램을 돌리기 위해서는 어떻게 하는지 생각해야한다.

- 프로세스간 독립(isolation)을 고려해 메모리 보호를 해야한다. 

- 메모리 공유가 가능해야한다. (shared memory)

- 성능적인 이슈도 있어야한다.

 

VM

virtual memory를 활용해 위의 이슈를 해결한다.

프로세스 내부에서 사용하는 메모리 주소를 virtual address 혹은 logical address라고 이야기한다. 실제 ram에 존재하는 address를 physical address라고 이야기한다. 이를 분리해서 관리하는 것이 virtual memory 관리의 첫번째 단계가 된다. 이를 어떻게 분리해서 관리하고 매칭할 지가 첫번째 이슈가 된다. -> 9장

 

ram은 1기가바이트인데, 2기가바이트 프로그램을 어떻게 실행시킬지 관리하는 것이 두번째 이슈가 된다. 이는 세컨더리 스토리지를 일부를 활용해 구현한다. 따라서 메모리는 무한하다고 가정해 이를 처리할 수 있게 된다.  -> 10장

 

위의 두 가지 key point를 가지고 memory 관리를 하는 것이 운영체제에서 메모리 관리를 하는 것이 된다.

 

 

Binding of Instructions and Data to Memory

메모리에 변수에 값을 일시적으로 저장하면 메모리에 어떤 번지에 저장할지 매핑하는 과정이 필요하다. 컴파일 할 때, 로드할 때, 실행할 때 연결하는 세가지 연결 방법이 있다. 

 

로드는 메모리에 있는 내용을 레지스터에 저장할 때 사용한다. store는 레지스터에 있는 내용을 메모리에 저장할 때 사용한다. 이때 메모리 주소가 등장하는데 그 주소가 실제 ram의 주소와 언제 연결되는지(컴파일, 로드, 실행)를 보고 판단한다.

 

Compile time

컴파일을 하면 data를 저장할 메모리 주소값이 필요해진다. 이 주소를 언제 결정할 것인지가 중요하다. 컴파일 타임에 이를 결정하면 data라는 변수는 꼭 실제 메모리 주소에 해당 주소로 이동해야한다. 따라서 해당 프로그램은 다른 곳에는 올라가지 못하게 된다. 나머지 부분에 맞춰 다른 프로그램을 올려야한다는 단점이 있다.

 

주로 하나의 프로그램만 올라가는 batch 프로그램이 이 방법을 사용한다. 혹은 아두이노에서 프로그램하는 경우에는 이 방법을 사용한다.

 

하지만 여러개의 프로그램을 돌리기에는 단점이 크기에 이는 사용하기 어렵다.

 

Load time

프로그램을 컴파일할 때에는 낮은 번지는 0번지라고 가정하고 data의 위치를 계산한다. 이후 메모리에 올릴 때에는 base address를 기준으로 모든 address를 더해줄 수 있다. 이렇게 되면 어떤 번지에 올라가도 동작할 수 있다는 장점이 있다. 하지만 로딩할 때 주소를 모두 바꿔야하기에 시간이 오래걸린다는 단점이 있다. 이 또한 오버헤드가 크기에 잘 사용되지 않는다.

 

 

Execution time

현재 사용하는 방법이다.

제일 밑에가 0번지부터 시작한다는 가정하에 data의 주소를 결정한다. 이후 어디에 올라가든지 명령어를 실행할 때 주소와 base address를 더해서 매핑된 주소를 가지고 실제 메모리를 엑세스하는 방식이다. 실제로는 단순히 더하는 것보다 더 복잡하게 이뤄져있다.

 

버추어 메모리를 사용하기에 왼쪽에 있는 것은 프로그램에서 사용하는 버추어 어드레스가 되고, 오른쪽은 피지컬 어드레스가 된다. 

 

Virtual Memory Management

Address mapping

프로그램 내에서 사용하는 virtual(logical) address, ram의 주소인 physical address로 나눠서 이를 관리한다. 사용하는 공간은 space라고 이름을 붙인다. 이를 physical address space로 변환을 할 때에는 cpu가 명령어를 실행할 때 이를 같이 계산한다. 이에 따라 CPU 내부에서 버추어 어드레스를 피지컬 어드레스로 변환시켜주는 것이 MMU이다. Memory Management Unit의 약자이다. 

 

ram은 1기가바이트인데 실제 프로그램은 2기가바이트인 경우에는 ram에 존재하는 일부분을 세컨더리 스토리지에 일시적으로 저장한다. 이러한 과정을 swap이라 한다. 

 

 

MMU(Memory-Management Unit)

CPU가 명령어를 실행할 때 logical address를 physical address로 바꿀 때 사용하는 CPU 내부의 디바이스이다.

 

Logical Address Space

n은 전역변수이기에 data segment에 존재한다. 해당 파일을 컴파일하면 실행파일로 a.out이 나온다. 이를 실행하면 n의 변수 주소가 0x08048508이 나온다.이를 반복적으로 실행해도 계속 같은 메모리 주소로 남는다. 만약 동시에 두 개의 프로그램을 실행시키는 경우에는 physical address space에서 할당이 되더라도 메모리 주소는 똑같이 나온다. 프로그램 내에서 사용하는 메모리 주소는 logical address이기 때문이다. 프로그램이 어디에 올라가서 실행이 되든지 간에 똑같이 메모리 주소가 나오게 된다.

 

실제로 사용하는 포인터의 값이 logical address이다.

 

cf) data segment는 전역변수와 static 변수들이 들어가서 프로그램이 실행되면서 항상 메모리 공간이 필요한 데이터가 들어가게 된다.

---

메모리 공간 할당 방법

Contiguous allocation

virtual address를 physical address로 어떻게 실행시킬 것인가에 대한 방법으로 logically contiguous 한 address를 physically contiguous한 address로 바꾸는 방법이다. 

 

0번지가 어디에 매핑이 되는지 보고 이를 그대로 더하는 방법이다. 가장 쉽고 간단한 방법이다. 위의 예시에서 본 방법이다. 하지만 단점이 많아서 지금은 사용되지 않는다. 

 

physical address의 base 값을 relocation register에 저장한다. 

 

Memory Protection

실제로 사용할 수 없는 메모리를 엑세스하면 허용하지 않는다. 이는 limit register를 사용한다. logical address가 limit register보다 작으면 허용하고, 크다면 참조할 수 없는 메모리를 참조한 것이 된다. 그렇게 되면 해당 명령어를 실행할 수 없으니 cpu가 할 수 없으니 exception(fault)을 걸어 운영체제가 수행된다. 교재에서는 trap이라고 표현된다.

 

참조할 수 있는 영역인 경우에는 base register와 더해서 이를 계산한다.

 

MMU라는 CPU 내 하드웨어가 이를 병렬적으로 처리하기에 엑세스 타임이라는 성능 면에서는 가장 좋다. 

 

Multiple-partition allocation

8번이 실행되다가 종료되면 해당 공간은 사용되지 않기에 hole이 된다. hole의 크기가 커졌다가 줄어드는 것을 볼 수 있다. hole이 여러개가 생기게 되면 각 hole에 배치시키는 알고리즘도 있다.

 

Dynamic storage allocation Problem

hole이 여러개 있을 때 새로운 프로세스를 어떤 hole에 배치할 것인지를 정해야한다. 이를 위해 다음 세가지 알고리즘이 있다.

First-fit

차례로 매칭하다가 프로세스를 넣을 수 있을 정도로 홀이 크다면 첫번째로 매칭되는 것에 넣는 방법이다.

 

Best-fit

홀을 모두 비교해본 뒤 짜투리 hole이 가장 작은 곳에 배치하는 방법

 

Worst-fit

홀을 모두 비교해본 뒤 짜투리 hole이 가장 많은 곳에 배치하는 방법, 이 방법을 사용하면 짜투 공간이 많이 남기에 이를 처리한다. 

 

위의 세가지 방법은 일반적인 알고리즘의 방법으로도 사용할 수 있다. 성능 상 first fit과 best fit이 worst fit보다 더 낫다. first fit은 매칭되면 바로 넣기에 성능이 빠르다. 한번의 결과가 나쁠 수도 있긴하지만 평균적으로는 이 방법이 더 낫다. 홀을 다 찾을 거면 best fit이 더 좋다.

 

Fragmentation

Contiguous allocation은 MMU에서 메모리 프로텍션을 위한 방법과 트렌스레이션의 방법이 간단하지만 Fragmentation 문제가 발생한다. 따라서 이를 사용하지 않는다. 

 

홀이 매우 작게 돼서 자투리 조각이 매우 많이 발생해서 해당 메모리 공간을 사용하지 않는다. 이에 따라 메모리 사용률이 매우 낮게 된다. 메모리 사용률이 100%가 될 수 없고, 이는 문제가 된다. 

 

 

 External fragmentation

홀이 점점 작아져서 더이상 사용되지 않는 자투리 조각으로 남는 것이다. 

 

compaction

잘게 쪼개진 홀을 사용하기 위해 사용 중인 프로세스를 카피한 뒤 모두 한 측면으로 몰아넣으면 홀이 넓어져 이를 사용할 수 있게하는 방법이다. 이를 위해서는 하드디스크로 메모리를 옮겼다가 여기서 다시 읽어야한다. 따라서 I/O 오버헤드가 매우 커서 실제로는 사용되지 않는다. 

 

----

 

명령어를 실행시킬 때의 data의 주소는 virtual address이다. 이는 ram에 저장할 때에는 실질적으로 physical address를 가지고 저장된다. 실제 physical address로 바꿀 때에는 MMU가 excution time에 이를 바꾼다.

 

Contiguous allocation

- base address를 더하면 되기에 쉽다는 장점이 있지만 Fragmentation이 발생하는 단점이 있다.

- external fragmentation 때문에 메모리 이용률을 100% 사용할 수 없다. compaction으로 이를 해결할 수 있지만 오버헤드가 매우 크다.

 

Paging

로지컬 메모리를 일정한 크기로 자르고(page), 이를 physical memory에서도 동일한 크기로 잘라서(frame) 이를 매핑해서 관리한다. 이에 따라 이론적으로 100% 메모리 효율을 관리할 수 있다.

가변적인 크기지만 일반적으로 4키로 바이트를 사용한다. 

 

logical contiguous -> physical non contiguous로 바꾼다.

 

위와 같이 배치를 하면 contiguous하게 배치하지 않아도 되기에 이론적으로 꽉차게 사용할 수 있다. 만약 한 프로세스의 크기가 15KB인 경우에는 4, 4, 4, 3KB로 나누게 된다. 이에 따라 남게 되는 fragmentation은 internal fragmentation이라 한다. 이때 internal fragmentation의 크기는 external에 비해 작게 된다. 반대로 frame의 경우에도 이는 발생할 수 있다.

 

internal fragmentation이 없다면 위의 방법은 이론적으로 100%의 메모리 효율을 보일 수 있다.

 

하지만 mapping을 관리해야한다는 단점이 있다. 이를 최적화하려는 노력이 있어야한다. 이는 table로 관리해야한다.

 

address 변환

- 페이지 번호와 offset을 가지고 이를 매핑하여 frame 번호와 동일한 offset으로 이를 처리한다.

- 페이지 테이블은 프로세스마다 필요하게 된다.

페이지 번호를 프레임 번호와 매핑하여 관리한다. page table은 프로세스마다 필요하게 된다.

offset은 동일하게 가게 된다.

 

Paging 예시

피지컬 어드레스: 20비트 -> 메모리 공간은 2의 20승이기에 메인 메모리가 1MB정도 있는 것을 가정한다.

page size: 4KB -> 2의 12승이기에 12 비트가 필요하게 된다. 따라서 12 비트가 offset이 된다.

Page Number = logical address - Offset = 32 - 12 = 20비트

Page table entires = 2의 page number 승

인티저 4바이트를 사용하게 되면 페이지 테이블은 4메가 바이트가 필요하게 되는데 이는 CPU MMU에 넣을 수 없기에 메인 메모리에 둬야한다.

 

 

피지컬 어드레스의 파란색은 안쓰이거나 다른 프로세스가 할당될 수 있다.

 

Free Frames

할당되지 않은 프레임

운영체제는 free frame을 관리해서 프로세스별로 page table에 맞춰 할당하게 된다.

 

page table의 문제점

2번의 메모리 엑세스가 필요하다. 이를 해결하기 위해 TLB라는 캐시 메모리를 사용한다.

 

메인 메모리인 page table을 참조한 뒤 계산해서 physical memory를 계산하기에 메인 메모리를 두 번 참조하게 된다.

(MMU에 둘 수 없을 정도로 양이 많은 데이터는 메인 메모리에 두기에 page table을 참조할 때 메인 메모리를 참조하게 된다.) 이를 해결하기 위해 캐시 메모리를 두어 해결한다. 자주 사용되는 메모리의 정보를 캐시에 저장한다. 이때 캐시를 TLB(Translation Look-aside buffer)라 한다. 이는 MMU 안에 있어야한다. 이에 따라 MMU에서 더하는 것만큼의 계산 속도를 가지게 된다.

 

캐시 메모리에 없는 경우에는 메인 메모리를 참조해야한다. TLB hit율이 99%라면 평균적으로 1.01번만큼 메모리에 엑세스 하게 된다.(0.99*1 + 0.01*2 = 1.01) 대부분 99% hit 한다.

 

Contiguous allocation에서의 MMU는 더하는 역할이지만 Paging에서는 TLB를 관리하는 것이 주요한 역할이 된다.

 

TLB라는 캐시 메모리는 우리가 알고있는 메모리와는 다른 부분이 있다. 메모리 주소를 주면 해당 주소의 값을 읽는 일반적인 메모리와는 다르게 병렬적으로 메모리 주소를 입력받고, 이에 매칭이 되는 피지컬 어드레스 값이 아웃풋으로 나오는 메모리이다. 이를 Associative memory(Content Addressable Memory)라 한다.

 

 

병렬적으로 서치해서 이와 매핑되는 주소가 나온다.

 

 

TLB는 로컬리티를 이용한다. 로컬리티는 하나의 프로세스가 실행되면 프로세스의 메모리 공간 중 20%가 전체에서 80%만큼 사용된다. (like 루프)

 

Temporal locality

시간적인 지역성 -> 메모리가 참조되었으면 다시 참조될 가능성이 높다.

코드 영역이 이에 해당한다. (while 등)

 

Spatial locality

메모리를 참조했으면 그 주변 영역의 메모리가 참조될 가능성이 높다.

어레이가 이에 해당한다.

 

지금 인텔, x86, arm 등에서 주로 사용하는 방법이다. 

 

간혹 TLB miss가 발생하지만 성능 상에서 큰 문제가 발생하지는 않는다.

 

TLB가 미스난다면 page table(메인 메모리)로 가서 운영체제에 exception을 걸어서 하거나 cpu가 알아서 이를 찾아서 사용한다. 대부분은 cpu 내의 mmu에서 tlb miss를 처리한다. 운영체제는 오버헤드가 무척 크기 때문이다.

 

입실론은 약간의 작은 오버헤드를 의미한다. -> 무시해도 된다.

 

메모리 프로텍션(두번째 이슈)

Contiguous에선 limit register(참조할 수 있는 가장 큰 어드레스)로 이를 관리한다.

paging에서는 valid, invalid bit로 이를 처리한다.

 

logical address가 32비트라고 가정하고 offset이 12비트라고 가정하면 page는 20비트가 있게 된다. 또한 페이지 엔트리는 2의 20승개가 있게 된다. 하지만 실제로 모든 프로세스가 2의 20승개만큼 page가 필요하지 않게 된다. 따라서 사용하지 않는 공간은 invalid로 표시하게 된다.

 

(3, 128) -> (7, 128)로 변환 가능

(6, 128) -> 변환 불가(invalid 때문) -> 이후 참조할 수 없는 영역을 참조했기에 fault를 발생시키고 해당 프로세스를 종료시킨다.

 

프로세스별로 page table이 존재하기에 invalid된 부분은 다른 프로세스가 사용중일 수 있다.  

 

 

Page Table Entries

페이지 넘버, 프레임 넘버, valid bit 등등을 포함해서 하나의 page table 엔트리에는 많은 비트가 들어가게 된다.

위의 네 개의 비트는 10장에서 설명이 나온다.

 

Prot bit는 Read, Write, Excute가 가능한지 등에 대한 정보가 들어간다.

 

 

Page Table Structure

페이지 테이블의 사이즈가 크지만 실제 프로세스의 사이즈가 작은 경우에는 페이지 테이블의 낭비가 발생한다. 따라서 페이지 테이블을 줄이고자 하는 노력이 들어간다.

 

페이지 테이블의 사이즈를 static하게 두지 않고, dynamically extensible하도록 한다. 이때 제안된 여러 방법 중 Hierarchical paging만 사용한다. 이 방법은 꼭 알아야한다.

 

Hierarchical Page Table

페이지를 두 단계로 나눈다. 페이지를 두번 액세스해야한다. TLB 미스가 나면 3번 액세스하게 된다.

 

모든 페이지를 사용하는 경우(Worst case)

싱글 레벨은 4메가 바이트가 항상 필요하게 된다. 위의 예시에서는 모든 페이지가 사용되기에 투레벨인 경우에는 4MB + 4KB가 필요하게 된다. 이는 최악의 경우가 된다.

 

페이지를 하나만 사용하는 경우(Best case)

Outer page table은 모두 있어야한다. 하지만 inner page table은 하나만 필요하게 된다. 따라서 4KB + 4KB = 8KB가 필요하게 된다. 또한 페이지가 2의 10승까지 있는 경우에는 이는 8KB만 필요하게 된다. 따라서 평균적으로 page table의 용량이 적게 된다.

 

outer page table에서 invalid인 경우에는 page table이 없게 된다.

 

 

Hashed Page Table

해시 함수를 통해 이를 처리하는 식으로 동작한다. 하지만 오버헤드가 커서 잘 사용되지 않는다.

 

Inverted Page Table

frame으로 페이지를 만든다. 즉, 어떤 프로세스가 어떤 페이지를 사용하는지 거꾸로 처리한다. 이에 따라 프로세스마다 존재하지 않더라도, physical memory 하나에만 있어도 된다. 따라서 페이지 테이블의 크기는 줄어든다. 하지만 내 프로세스에 대한 정보를 모두 확인해야하기에 비용이 많이 들어 이는 사용되지 않는다. 

 

Shared Pages Example

Paging은 Shared memory를 만들기 쉽다. P1~P3에서는 ed는 모두 동일하게 사용하고, 데이터만 달라지기에 페이지 번호를 동일하게 참조한다.

 

실제 shared library는 paging이라는 방법을 통해 shared memory를 쉽게 구현한다.

 

shared library는 유닉스/리눅스에서 사용한다. 윈도우에서는 dll(dynamic linking library)이라 한다. 메모리 효율을 좋게 하기 위해 이를 사용한다. 

 

 

페이징의 장점

 

페이징의 단점

아직 internal fragmentation은 있지만 이는 매우 적다. TLB를 통해 액세스 횟수도 줄이게 된다.

 

 

logical -> physical address translation의 세번째 방법

Segmentation

페이징에서 세그멘테이션으로 넘어가고 있다.

페이징은 고정 크기로 이를 나눈다. 이에 따라 영역이 함께 페이징으로 들어가게 될 수 있다. 예를 들어 code segment와 data segment가 한 페이지에 들어가게 될 수 있다. 이는 write을 하게 할지, 하게 하면 안될지 처리하기 곤란해진다. 이에 따라 의미있는 단위로 이를 자르게 된다.

 

intel은 코드로 자르고 데이터로 자르고 stack 자르고 나머지인 extra로 자른다.

 

 

페이징은 데이터의 의미를 고려하지 않고, 동일 크기로 잘랐기 때문에 이를 의미있는 단위로 자르고자 한다.

 

Segmentation Hardware

프로세스 전체를 segment로 나눠서 segment 단위로 contiguous allocation을 하게 된다. 이에 따라 가장 큰 문제는 external fragmentation 문제가 발생한다.

 

Sharing of segments

동일한 부분은 share한다.

 

장점

 

단점

이 문제 떄문에 paging과 segmentation의 장점을 취한 하이브리드 방법을 사용한다.

 

 

 

 

하이브리드 접근법

Segmentation with Paging 혹은 Paged segments라고 부른다.

일단 세그먼트로 나누고 이를 페이징한다. 

 

세그먼트로 나누고, 이를 페이징한다.

 

펜티엄

펜티엄 프로세스에서도 이를 사용한다. 

인텔에서는 segment number를 selector라고 한다.

segmentation을 하면 linear address가 나온다. 이후 투 레벨 hierarchical page table을 한다. 이후 frame number를 찾게 된다.

 

 

Address Translation in IA-32

인텔 아키텍쳐에서의 32비트

위의 방법과 거의 유사하다. 하지만 PAE라는 방법을 하나 더 사용한다.

 

예전에는 4기가 바이트까지만 피지컬 메모리를 사용할 수 있었다. 하지만 더 큰 메모리도 사용가능하도록 지원했다.

 

IA-32 segmentation

IA-32 Paging

상황에 따라 페이지 사이즈를 다르게 처리했다.

CR3는 cpu 내의 레지스터인데, page directory의 시작주소를 가지고 있는 mmu가 사용하는 레지스터이다.

 

IA-32 PAE(Page Address Extension)

더 큰 사이즈를 지원하기 위해 위의 두 비트를 사용해 페이지 테이블을 더 만들었다. 이에 따라 36비트까지 피지컬 메모리를 지원할 수 있게 됐다.

 

x86-64

페이지가 무척 크게 된다. 이에 따라 4레벨 hierarchical page table로 처리한다. 이에 따라 52비트까지 처리 가능하게 된다.

 

ARM

arm은 세그멘테이션은 안하지만 페이징을 한다. 대신 멀티플 페이지 사이즈로 세그멘테이션의 효과를 누린다.

투레벨을 사용한다.

 

ARMv8(AArch64)

세그멘테이션은 없지만 4레벨을 사용하며 멀티플 페이지 사이즈를 사용한다.