[Chapter 9]
I. 메모리 관리와 페이징 기법
A. 목표
1. 프로그래밍할때 physical 메모리를 신경쓰지 않아도 되도록 abstraction을 제공한다. physical memory address와 분리된 logical memory address를 사용해서 프로세스마다 0번지부터 max번지까지의 메모 리를 사용할 수 있다고 가정하고 프로그래밍 한다.
2. 메모리 자원을 오버헤드를 줄이면서 최적의 성능을 내도록 할당.
3. 프로세스 간 메모리 isolation. 공유메모리를 설정하지 않으면 별개의 메모리를 가지고 동작함. B. 시스템 구분
1. Batch Programming: 메모리 관리가 필요없고 실행되어야하는 태스크를 실행시키고 실행끝나면 내려 주는 작업만 한다. IO가 발생하면 처리하는 동안 CPU Utilization이 떨어진다.
2. Multiprogramming: 여러개의 프로세스가 동시에 메모리를 점유한다.
각각의 프로세스는 자기만의 메모리 공간이 필요하다.
프로세스들마다 격리된 메모리 공간을 할당해주는 로직이 필요하다.
Partitioning, Paging, Segmentation 등이 있다.
메모리 관리에 있어서 필요한 사항들
Protection: 특정 프로세스가 다른 프로세스 메모리공간 침해하면서 의도치 않은 동작 방지. Fast translation: 필요한 메모리를 빨리 찾을 수 있어야 함.
Fast Context Switching: 컨텍스트 스위칭 빨라야함.
C. 메모리 관리 이슈
1. 다수의 프로세스에 격리된 메모리를 할당하고 Protection, 데이터 쉐어링 등의 기능을 제공해야한다. 2. Virtual Memory: 프로그램은 항상 모든 코드나 데이터가 메모리에 올라가 있을 필요는 없다. 읽히지 않는 메모리도 존재하고, 실행되지 않는 branch도 존재한다. 가상 메모리를 사용하면 이런 특성을 통해 Physical 메모리를 적게 사용하면서
프로그램을 실행시킬 수 있다.
또한 각 프로세스의 메모리 공간을 격리시키고 , 세컨더리 스토리지(디스크)의 일부를 메모리처럼 사용하면서 swap in, swap out을 통해 physical 메모리보다 큰 메모리 공간을 할당할 수 있는 기능을 제공한다. 보통 physical memory의 두 배 이상을 가상메모리로 설정한다.
가상 메모리에서는 메모리를 Physical Memory와 Logical Memory로 구분한다.
Physical Memory는 실제 하드웨어이고 Logical Memory는 Physical Memory를 직접 건드리지 않도록 추상화해놓은 것이다
D. 메모리 주소 바인딩
1. 프로그램이 실행되었을때 프로세스가 동작할 수 있는 코드, 데이터 섹션을 메모리에 로드시키는 시점 에 따라서 3가지로 구분된다
2. Compile time: 컴파일 되면 변수이름은 사라지고 주소값으로 대체된다.
컴파일 하고 어셈블리 코드 실행을 보면 변수이름이 없는 이유이다.
메모리 주소로 매핑되어서 직접 메모리 주소를 사용한다.
컴파일 타임에 메모리 주소를 바인딩한다는 것은 바이너리 이미지를 만드는 시점에 결정한다는 것이 다.
컴파일할때 어디서부터 어디까지의 주소를 사용한다고 지정한다. 실제로 메모리에 올라갈때 컴파일 타임에 지정된 주소로 할당된다. 실제로는 잘 사용되지 않는다. 펌웨어 레벨이나 임베디드 시스템에서는 사용된다.
다른프로그램이 실행될 때 똑같은 메모리 주소를 가진다면 프로그램을 올리지 못한다.
3. Load time: 컴파일타임의 문제를 해결하기 위해서 로드하는 시점에 피지컬 메모리에 만들어질 위치를 결정한다.
프로그램 크기를 지정하고 운영체제가 메모리를 보고 연속적으로 할당할 수 있는 공간을 찾아서 넣어준다. 그럼 시작위치를 base address로 하고 프로세스 내에서의 위치에 base address를 더하면 정상적으로 동작한다. 메모리 참조값을 base가 어딘지에 따라서 로드타임에 주소연산 해줘야 하고, 실행되지 않을 수도 있어도 모든 분기에 대해서 처리를 해줘야한다. 따라서 로드 시간이 굉장히 길어질 수 있다.
4. Execution time : 동일하게 로드타임에 적절한 위치에 할당 받고 코드에 있는 주소값을 그대로 가져와서 수행시에 base address와 계산해서 처리한다. 실행시간이 늘어날 위험이 있지만 최적의 방법이다. 주소연산 오버헤드를 줄이기 위해서 mmu라는 유닛을 만들었다. 특수한 목적으로 만들어진 하드웨어이다. 주소연산에 특화되어 있으며 로지컬 주소를 피지컬 주소로 변경하는 역할을 한다. 저사양 컴퓨터는 mmu가 없다. mpu라는 프로텍션 기능만 가진 유닛이 존재한다.
mmu는 cpu 대부에 존재하고 로지컬 메모리를 mmu에 cpu가 전달하면 피지컬 메모리로 전환해준다. 피지컬 메모리는 프로그램 실행시마다 달라질 수 있다. 하지만 변수의 주소값을 출력해보면 항상 같게 나오는 것을 확인할 수 있다. 따라서 로지컬 메모리를 통해 abstraction되어있고 프로그래밍시에 실제로 접근하는
주소는 로지컬 메모리인것을 확인할 수 있다.
E. 메모리 주소 할당
1. Contiguous Allocation: 연속적으로 메모리를 할당하는 방법.
다른 프로세스의 메모리 영역을 침범하지 않는지 계산하고 메모리를 할당한다.
단점은 프로세스가 종료되고 메모리를 반납했을때 빈공간이 생기는데, 다른 프로세스를 빈공간에 할 당하면 프로세스 크기 차이에 따라서 남는 공간이 발생한다. 이 공간이 하나의 프로세스를 돌리기에 부족하다면 해당 공간은 사용할 수 없다. 프로세스가 생겼다 없어지는 과정에서 hole이 다수 발생하 면 memory Utilization이 떨어진다.
이를 해결하기 위해서 hole들을 모아서 하나의 큰 블록으로 재배치하는 방법이 있다. 이를 compaction이라고 한다.
하지만 IO가 많이 발생하고 프로세스들을 복사해서 재배치하는 과정의 오버헤드가 크기 때문에 잘 쓰이지 않는다.
Hole의 사이즈를 최대한 줄이는것이 중요하므로 새로 올라오는 프로세스를 어느 hole에다 할당할것 이냐가 중요하고,
first fit, best fit, worst fit방식이 존재한다.
First fit은 메모리를 스캔하다가 첫번째 발생하는 빈공간에 메모리를 할당하는 방법이다. Best Fit은 가장 크기가 비슷한 hole에다가 프로세스를 할당하는 방식으로 홀의 개수, 위치, 사이즈를 운영체제가 관리해야하는 오버헤드가 존재한다.
Worst fit은 가장 큰 홀에 먼저 프로세스를 할당하는 방식이다.
실제로는 first와 best fit의 성능이 비슷하게 나온다.
어떤 방식을 사용해도 hole이 발생하고 프로세스 사이에서 생기는 홀으로 인해 메모리가 단편화되는 현상을 external fragmentation이라고 한다. Compaction으로 해결하는 방법이 있으나 IO로 인한 오버 헤드 문제가 발생한다.
2. Paging: 페이지란 논리 메모리를 일정한 크기로 나눈 블록이다. 프로세스를 logical address 단에서 지 정된 크기만큼으로 자른다. 페이지 크기와 똑같은 크기만큼 피지컬 메모리도 분할해서 슬롯을 만든다. 이것을 프레임이라고 한다.
운영체제가 정책에 따라서 페이지를 프레임에 할당하고 몇번 페이지가 몇번 프레임에 들어가있는지 페이지 테이블을 관리한다.
하지만 페이징 기법을 사용해도 fragmentation이 발생하는데, 페이지 단위로 분할한 프로세스 내부에서 페이지 단위보다 작은 메모리를 차지하는 부분은 단편화가 발생한다. 이것을 internal fragmentation이라고 한다.
하지만 internal fragmentation은 external fragmentation보다 메모리 낭비가 훨씬 줄어드므로
실제로 페이징 기법이 사용된다.
F. Address Translation
1. 논리 주소: page number와 offset으로 이루어져있다 (p,d)
페이지 번호는 페이지 테이블의 index와 동일하다.
offset은 페이지 내에서 어느 위치로 접근해야하는지의 값이다.
페이지 테이블이 몇 번 프레임에 페이지를 할당할지 결정한다.
2. 물리 주소: frame number와 offset으로 구성되어있다 (f,d)
3. Page table: 프로세스마다 개별적으로 가지고 있으며 운영체제가 관리하여 페이지 번호와 프레임 번호를 매핑한다.
하나의 페이지당 하나의 엔트리를 차지한다. 각 엔트리 크기는 int(4바이트)이다. 페이지 번호는 인덱스로,
프레임 정보를 데이터로 관리한다. 페이지 테이블은 각각의 프로세스를 독립적으로 관리하기 위한 가상 주소공간으로
페이지 테이블이 메모리 전체의 0번지부터 max 번지까지의 페이지를 다 사용 가능하다고 가정한다. 페이지 테이블은 메모리 상에 존재하며 위치를 알아내기 위해서
ptbr(page table base register)와 ptlr(page table length register)를 사용한다.
4. 과정: CPU가 자신 내부의 mmu에 logical address를 전달하면 p부분은 page table을 참조하여 프레임 번호로 변경하고 d부분은 그대로 프레임 번호와 합쳐서 physical address로 변환한다.
32비트 주소체계에서 20비트는 페이지 번호, 12비트는 오프셋으로 사용한다.
20비트를 사용하면 2의 20승 = 1메가개(약 105만개)의 페이지 번호를 가질 수 있다.
따라서 logical 메모리 공간을 1메가개만큼의 페이지로 나눌 수 있다.
이렇게 나눠진 페이지들을 페이지 테이블을 통해서 관리한다. 32비트 주소체계에서의 페이지 하나의 크기는 4kbyte이다. 20비트를 통해서 페이지 번호를 지정하고 12비트를 통해서 오프셋 정보를 표현한다. 1메가개의 페이지 * 4kbyte의 페이지 크기이므로 32비트 운영체제에서 메모리 크기는 최대 4GB가 된다.
5. 운영체제에서는 free frame list를 관리하여 새로운 프로세스가 실행될 때 free frame에서 선택해서 할당한다. 비어있는 프레임보다 새로 실행되는 프로세스의 페이지가 더 많으면 오버플로우가 발생하므로 이미 메모리에 있는
프로세스를 디스크로 swap out 후에 swap in 해야한다.
G. TLB
1. TLB 개념: 페이지 테이블은 크기가 크다.
1메가개의 페이지 엔트리 * 한칸당 4바이트 = 4MB가 된다. 여러개의 프로세스가 동시에 존재하므로 페이지 테이블을 캐시에서 관리할수는 없으므로 메모리에서 관리한다. 하지만 피지컬 메모리 주소를 알아내기 위해서 매번 메모리에 접근해야한다면 매번 두번씩 접근해야하므로 비효율적이다.따라서 TLB를 사용해서 해결한다.
TLB는 mmu내부에 존재하는 버퍼 메모리이다. TLB는 associative memory로 병렬 탐색이 가능해서 아 주 빠른속도로
페이지 테이블을 탐색할 수 있다. CAM(content addressable memory)라고도 부른다. TLB에 페이지 테이블을 캐싱해두고 메모리 엑세스가 필요할때 TLB부터 참조해서 Cache hit이 발생하 면
(값이 캐시에 있으면) 메모리에 엑세스하지 않고 한번에 피지컬 메모리에 접근할 수 있다. Cache hit이 발생하지 않으면 메모리로 엑세스 해야한다.
TLB는 하드웨어로 구현되어있고 Cache hit이 98퍼센트 이상으로 성능이 굉장히 좋다. 이렇게 높은 확률을 가지는 이유는 Locality때문이다.
2. Locality: Spatial Locality와 Temporal Locality가 있다.
프로그램은 반복을 많이 사용하고 일반적으로 코드의 20퍼센트가 80퍼센트 이상의 작업을 차지한다. temporal locality는 반복에 의해서 가장 최근에 사용된 데이터가 빠른 미래에 사용될 가능성이 높다는 개념이다. spatial locality는 인근에 있는 메모리 영역에 대한 접근 가능성이 높다는 개념이다. 따라서 메모리를 가져올때 주변의 데이터를 한번에 많이 가져오면 메모리 접근 횟수를 줄일 수 있다.
3. Context Switching발생시: 새로운 프로세스가 올라왔을 때 기존 프로세스의 페이지 테이블 정보는 쓸모가 없어지므로
전부 invalid상태로 변경한다. 처음 context switching이 발생했을때는 Cache miss가 발생하고 운영체제가 메모리에
접근해서 Temporal, Spatial Locality를 고려해서 페이지 테이블을 가져와서 캐시를 업데이트한다.
4. EAT(Effective Access Time): 메모리 엑세스 타임 성능을 수식으로 나타냄.
엡실론 = TLB접근시간, 메모리 엑세스 = 1, Cache hit확률 = 알파.
왼쪽은 TLB에서 hit이 났을 때의 시간, 오른쪽은 메모리 엑세스를 해야할 때의 시간.
H. 메모리 Protection
1. 페이징 기법 Protection: 프로세스가 5개의 페이지로 이루어져있는데 6번째 페이지에 접근하는 등 유 효하지 않은 페이지에 접근하는 문제가 발생할 수 있다. 따라서 페이지 테이블에서 하나의 비트를 활 용하여 유효한 페이지는 valid, 유효하지 않은 페이지는 invalid로 관리한다.
하지만 swap out으로 인해서 해당 페이지가 invalid인 상황일수도 있다. 따라서 페이지 테이블에서 invalid인 경우는 2가지 상황이 존재한다. 유효하지 않은 메모리에 접근하는 경우 protection으로 exception인터럽트를 발생시키는 경우, 디스크에서 swap in 시켜서 valid로 바꿔주는 경우이다.
2. PTE(Page Table Entry)구조: valid bit: 엔트리가 사용될 수 있는지 여부를 관리. Reference bit: 페이지가 엑세스 되었는지를 관리하는 비트.
Modify bit: 페이지가 write으로 인해 변경되었는지 관리.
Protection bit: 권한 관리 (read,write,execute,etc).
나머지 20비트는 Frame Number이다.
I. 페이지 테이블 구조
1. 한 프로세스마다 페이지 테이블을 하나씩 가지고 있고 20비트개 만큼의 엔트리에 페이지 크기가 4kbyte 이므로
메모리 전체를 사용한다고 가정한 것이다. 하지만 하나의 프로그램이 메모리 전체를 사용하는 경우는 거의 없다.
valid로 체크되어있는 엔트리에 대해서만 페이지를 할당하면 된다.
구현방법으로 hierarchical, hased, inverted page table이 있다. Hierarchical page table 방식만 실제로 사 용된다.
2. Hierarchical Page Table: 페이지 테이블의 depth를 나누고, 페이지 넘버를 표현하는 20비트를 10비트씩 쪼개서 앞부분을 첫번째 depth의 outer page table접근에 사용하고 뒷부분을 나눠진 page table에 접근 하는데 사용한다. 최악의 경우 메모리를 전부 다 쓰고 모든 페이지가 valid인 경우 outer page table의 사이즈는 2의10승이므로 4*2의10승은 4KB, page table은 4kbyte의 페이지가 2의10개만큼으로 분리되어 서 4MB의 크기를 가지므로 총 4.4MB의 크기를 가지게 된다. 싱글 레벨의 경우 4MB의 크기를 가지므 로 더 크다. 하지만 전부다 valid로 사용하는 경우는 거의 없고 outer page table에서 invalid라면 페이지 테이블에 할당하지 않으면 된다. 만약 한개의 페이지만 valid인 경우라면 outer page table은 그대로 4kb 를 유지하지만 page table은 한개의 페이지 테이블에서 한개의 페이지만 생성하면 되므로 4kb가 되어 총 크기가 8kb로 극단적으로 줄어든다.
3. Hashed Page Tables: 페이지 넘버를 해싱해서 저장하고 해싱된 결과가 똑같은 값을 가지는 것들을 linked list 로 관리하는 방식이다.
4. Inverted Page Table: 피지컬메모리의 입장에서 프레임마다 할당받은 페이지가 있고, 어떤 프레임에서 어떤 Pid 의 프로세스를 할당받았는지를 frame table 로 관리하는 방식이다. physical address 를 logical address 로 역으로 연산하는 과정이 복잡하고 하드웨어 아키텍쳐에 맞지 않아서 사용하지 않는다.
J. Shared Page
1. 동일한 프로그램에서 여러개의 프로세스를 생성하는 경우 코드섹션이 동일하다. 페이지를 사용하므로 운영체제에서 코드섹션 페이지를 공유하도록 해서 중복을 줄여 메모리를 아끼는 것이 가능하다.
dynamic linking되는 공유 라이브러리의 경우에도 여러 프로세스들이 같은 물리적 주소를 공유하게 할 수 있다.
공유 라이브러리는 여러 프로세스에서 공통적으로 사용되므로 프로세스마다 로드하는것이 아니라 한 번만 로드하고 각 프로세스의 페이지 테이블에서는 shared page를 가리키는 엔트리를 생성하여 물리 적으로 같은 메모리 주소를 공유한다.
K. 페이징의 장점
1. external fragmentation이 발생하지 않는다.
2. physical memory할당이 쉽다. free frame list를 통해서 빈 프레임을 할당하고 할당된 프레임은 list에서 제거하면 된다.
3. fork()하는 경우 코드섹션은 동일하므로 공유해서 사용함으로써 메모리를 아낄 수 있다.
4. 공유 라이브러리 또한 라이브러리를 메모리에 한번만 로드하고 프로세스들이 공유해서 사용할 수 있으므로 효율적이다.
L. 페이징의 단점
1. nternal fragmentation이 발생할 수 있다. 하지만 external fragmentation과 비교해 훨씬 작은 수준이므 로 무시할 수 있다.
2. 페이지 테이블의 사이즈가 커서 캐싱할 수 없다. TLB 를 MMU 내부에 하드웨어로 구현해 캐싱할 수 있게 했고, Hierarchical paging 을 통해서 사이즈를 줄임으로써 해결했다.
II. Segmentation
A. 정의
1. 프로그램을 여러개의 세그먼트로 나누어 메모리에 로드하는 기법. Contiguous Allocation과 비슷한 방 법으로 메모리 내의 빈공간에 프로세스를 세그먼트단위로 나누어 로드한다. segment table을 관리하여 세그먼트들을 관리한다. 세그먼트 테이블은 세그먼트 번호, 오프셋으로 논리적 주소를 나누어 관리한 다. 세그먼트 테이블을 참조하여 base 주소를 찾고, 오프셋이 범위를 넘어가지 않는지 체크하고 통과 하면 base주소를 더해서 physical 주소를 읽는다.
마찬가지로 external fragmentation이 발생한다.
프로그램은 코드 세그먼트, 데이터 세그먼트, 스택 세그먼트 등으로 나뉜다.
2. 만약 공유되는 페이지가 여러개 있고 fork 가 일어난 경우 몇번 페이지가 공유하는 페이지인지 관리하기 어렵다.
하지만 Segmentation 을 사용하면 sharing 이 편리하고 protection 도 쉽다(코드세그먼트는 쓰기 불가 등).
단점은 external fragmentation 이 발생한다.
B. Hybrid Approach
1. Page Segment: 프로세스를 세그먼트 단위로 나누고 나눠진 것을 페이징한다. 세그먼트 테이블, 페이 지 테이블이 각각 생성된다. hierarchy가 늘어나지만 세그먼트가 페이지로 나눠져 있으므로 세그먼트 테이블이 줄어든다. 세그먼트를 위해 페이지 크기는 하나로 고정되지 않고 여러개의 사이즈의 페이지 가 존재해서 필요한 크기를 사용하기도 한다. 이렇게 하면 세그먼트 단위로 용도에 따라 나누고 그 것을 페이징해서 external fragmentation이 발생하지 않고 internal fragmentation도 multiple page size 를 사용해서 많이 줄일 수 있다.
실제로 이 방법이 사용된다
2. Pentium System: Page Segment가 적용된 시스템이다. selector 는 세그먼트 주소를 저장하고 descriptor table 을 통해서 physical address 를 받고 offset 을 더해서 page 가 된다. 실제로 offset 은 page number 이다. 하단부는 hierarchical paging 으로 구현되어있다. Directory 는 outer page table 에 해당한다. page 는 inner page table 주소가 된다. Directory 를 참조하고 페이지테이블을 참조해서 base 주소를 가져다가 offset 값을 적용하면 physical address 가 나온다.
의미있는 단위인 세그먼트로 나누고, 페이지로 다시 나눠서 hierarchical paging 으로 구현. 그냥 paging 보다 locality 가 더 좋아진다.
C. 실제 아키텍쳐 사례
1. A-32: 인텔32비트 cpu 아키텍쳐. 서로다른 크기의 페이지를 사용하는 기법 적용. PAE(Page Address Extension)기법을 써서 4gb보다 큰 메모리 공간 사용.
2. x86-64: 48bit 주소체계를 씀. 64 비트를 다 쓸 필요가 없다. 현재 가장 큰 메모리가 1TB 이기 때문에 그만큼의 physical address 가 필요없다.
3. ARM: Two Level 로 페이징해서 사용한다. 임베디드에서 많이 사용된다. 페이지 사이즈를 자잘하게 쪼개서 사용한다. internal fragmentation 을 줄일 수 있고 큰 영역은 큰걸 할당하면 페이지 테이블 크기도 줄일 수 있다.