9. Memory Management (2)

페이지 테이블의 형태에 따라서 참조하는 방식이 달라진다.

페이지 테이블의 형태는 크게 3가지가 있다.

• Hierarchical Paging : Break up the logical address space into multiple page tables
• Hashing Page Tables : Using Hash to look up page table
• Inverted Page Tables

Two-Level Page-Table Scheme(Hierarchical Paging)

앞 내용에서 말했듯이 각 프로세스의 address space는 운영체제의 최대 bit에 맞춰서 max 주소가 설정되게 되고 32bit OS라면 max 주소가 2^32 - 1이 된다. => 각 프로세스는 32bit를 모두 사용한다

32bit address를 가지는 프로세스의 address space를 4KB의 페이지로 자르면 2^20개의 페이지가 만들어 진다.

그리고 2^20 개의 페이지를 구분하는 페이지 테이블을 만들기 위해서는 2^20개의 엔트리가 필요하고 각각의 엔트리는 페이지가 저장된 frame의 시작주소가 될테니 각 엔트리의 크기는 4 bytes 이다.

따라서 페이지 테이블의 크기는 4MB(2^22 bytes)가 된다.

=> 페이지 테이블을 또 다시 4KB 페이지로 잘라서 프레임에 분할해서 보관해야 한다.

4MB짜리 페이지 테이블을 4KB로 자르면 22 - 12 = 10 이므로 2^10개의 페이지가 만들어 진다.

따라서 2^10개의 페이지를 구분하기 위해 10bit를 페이지 번호로 사용해야 하고, 각 4KB (2^12) 페이지 내에는 2^10개의 페이지 테이블 엔트리가 들어간다.

페이지 내에서 각 엔트리를 구분하기 위해 10bit가 필요할 것이다.

페이지 테이블을 위한 페이지 테이블은 2^10개 페이지를 구분하면 되고 따라서 2^10개의 엔트리가 필요하며 각 엔트리는 4bytes 이므로 2^12 (4KB)가 된다.

4KB는 하나의 frame안에 딱 맞게 들어가므로 더 이상은 분할하지 않아도 된다.

=> Two level Page table

 

페이지 테이블의 크기가 4MB면 프로세스가 10개만 생성되어도 페이지 테이블의 크기만 40MB이다.

그렇다면 페이지 테이블 전체는 디스크에 저장을 하고 현재 접근 중인 페이지의 정보가 들어있는 페이지 테이블의 일부분만 실제 메모리에 올리는 방식을 사용할 수 있겠다.
=> on-demand 방식

이렇게 하려면 내가 찾으려는(CPU가 접근하려는) logical page가 저장된 frame의 주소가 적힌 페이지 테이블이 메모리의 어떤 frame에 저장되어 있는지를 알아야 한다.
=> 페이지 테이블을 위한 페이지 테이블이 필요하다.

원래 기본적인 페이지 테이블은 데이터가 저장된 페이지의 위치를 담고 있는데, 페이지 테이블을 위한 페이지 테이블은 페이지 테이블의 일부가 저장된 위치를 가리키게 된다.
원하는 페이지를 찾을 때, 먼저 내가 찾고자 하는 페이지 테이블 엔트리를 담고 있는 페이지 frame의 위치를 찾고, 그 안에서 페이지 테이블 엔트리를 찾아 내가 찾는 데이터가 들어있는 페이지 frame을 찾아서 데이터에 접근한다.
=> two level page table scheme

 

먼저, 내가 찾고자 하는 데이터가 들어 있는 페이지를 찾기 위한 페이지 테이블 역시 쪼개져서 프레임 내에 들어있으므로 그 페이지 테이블이 들어 있는 frame을 찾기 위해 outer-page table을 탐색한다.

그렇게 페이지 테이블이 들어 있는 frame에서 페이지 테이블 엔트리를 찾아 원하는 데이터가 들어 있는 페이지 frame에 접근하여 데이터를 얻는다.

=> 즉, outer-page table을 통해 페이지 테이블이 들어 있는 페이지 frame을 찾는다. 그런 다음 해당 frame으로 가서 페이지 테이블 엔트리를 찾아 원하는 데이터가 들어 있는 페이지가 들어 있는 페이지 frame을 찾아 접근한다.

말이 헷갈릴 수 있으나 천천히 생각해보면 된다.

 

그런데 logical address 하나만을 가지고 어떻게 이 두 테이블을 Look up 할 수 있을까??

페이지의 크기가 2의 지수승으로 결정되어 있기 때문에 가능하다.

앞에서 말했듯이, 2^20개의 페이지 테이블 엔트리는 또 다시 2^10개의 페이지 frame에 나눠서 저장되게 된다.

잘라진 페이지 테이블이 저장된 페이지 frame을 매핑하는 outer-page table의 엔트리는 2^10개가 된다.

그리고 그렇게 찾은 페이지 frame 내에는 2^10개의 페이지 테이블 엔트리가 들어있을 것이고, 따라서 원하는 페이지 테이블 엔트리를 찾기 위해 offset으로 10bit가 필요할 것이다.

page number를 의미했던 m-n bit가 또 다시 p1, p2로 나뉘어서 각각은 잘린 페이지 테이블이 저장된 페이지의 번호와 페이지 내에서의 offset을 의미하게 된다.

이 두 정보를 이용해서 outer-page table에서 페이지 테이블이 저장된 페이지를 찾아 해당 페이지 내에서 원하는 페이지 테이블 엔트리를 찾아, 엔트리를 통해 원하는 데이터가 들어 있는 페이지 frame을 찾아서 d(12bit)를 이용해서 원하는 데이터를 찾을 수 있다.

이 과정을 그림으로 나타내면 다음과 같다.

p1을 이용해서 outer-page table에서 페이지 테이블이 저장된 페이지 frame을 찾는다.

그렇게 찾은 페이지 frame에서 p2를 offset으로 하여 페이지 테이블 엔트리를 찾아서 원하는 데이터가 들어 있는 페이지 frame을 찾는다.

그 frame에서 d를 offset으로 이용해서 원하는 데이터를 찾게 된다.

 

Multilevel Paging and Performance

이렇게 여러 단계의 페이지 테이블을 이용했을 때의 성능은 어떻게 될까?

32bit 주소 체계를 사용하면 바깥쪽 page table이 2^10 * 4 (4KB)의 크기를 가지므로 하나의 frame에 쏙 들어가게 된다.
=> 32bit의 겅우 two level로 끝나게 된다.

그런데 바깥쪽 page table의 크기가 4KB를 넘어가게 되면 또 다시 하나의 frame에 들어가지 못 하게 되고 여러 frame에 나눠서 들어가게 되기 때문에 바깥쪽 page table을 위한 페이지 테이블이 또 다시 필요할 것이다.

2^64bit 주소 체계라면 2^32bit 와는 비교가 안 될 정도로 많은 주소가 있기 때문에 페이지 테이블이 two level로 끝나지 않을 것이다.
그러면 어떻게 하냐, 물론 계속 다단계로 페이지 테이블을 만들면 해결은 되겠지만 그 오버헤드가 꽤 커지게 된다.

two level만 해도 메모리에 총 3번을 접근하게 된다. outer page table에 한 번, inner page table에 한 번, 데이터에 한 번.
그런데 level이 더 커지게 되면 메모리 접근 오버헤드가 점점 커지게 될 것이다.

CPU가 데이터를 얻기 위해 메모리에 한 번 접근하기 위해서 실질적으로 4번, 5번 메모리에 접근하게 된다.

=> 이건 심각한 문제.

다행스럽게 TLB가 있기 때문에 어느 정도 오버헤드 완화가 가능하다.

 

TLB hit ratios가 98%인 4 level paging에서는 128 nanoseconds가 걸린다.

페이지 테이블이 없을 때는 바로 메모리에 가니까 100ns가 걸리는데 4단계로 접근해도 128ns니까 크게 차이가 나지 않음. (28%의 성능 저하)
=> TLB hit ratio가 높으면 레벨이 조금 높아져도 문제가 없겠다.

그런데 우리가 사용하고 있는 64bit의 경우 6레벨이 필요하다.
=> 이건 TLB를 사용하더라도 오버헤드가 꽤 클 것이다.

굳이 2^64 주소 공간을 모두 사용할 필요가 있을까? 사용하는 공간보다 사용하지 않는 공간이 더 클텐데??

그래서 사용하지 않는 bit는 버리자는 생각이 나옴
=> 48bit만 주소로 사용하자.
=> 이건 4 level로 가능하다.

 

이건 상식적으로 알아두자.

32bit OS를 사용하는데, DRAM을 2GB 짜리를 꽂았다고 생각해보자.
32bit는 2^32개의 주소를 커버할 수 있다. 2^32는 4GB
=> 모든 DRAM의 주소 커버 가능

DRAM을 늘려서 4GB 짜리를 꽂았다면, 딱맞게 DRAM의 모든 영역을 커버할 수 있다.

그런데 32bit OS를 사용하는데 8GB짜리 DRAM을 꽂았다고 하면, 4GB의 주소 영역만 커버가 가능하니까 나머지 4GB는 사용하지 못 하게 된다.
심지어 4GB도 다 사용할 수 있는 것이 아니라 특수 목적을 위해 reserved 되는 주소를 제외하면 사실상 대략 3.2GB 정도만 사용이 가능하다.

4GB 이상의 DRAM을 사용하려면 64bit CPU, OS를 사용해야 한다.

 

Hashed Page Tables

주소 변환 역시 Search라면 Search structure인 해시를 쓰지 못 할 이유가 없다.

=> 해시 테이블을 통해 실제 주소를 찾아내도록 할 수 있을 것이다.

32bit는 two level page table로 커버가 되므로 depth가 2인 tree라고 생각할 수 있다.
=> 이 경우엔 굳이 해시를 사용 안 해도 괜찮다.

해시를 사용했을 때 기대할 수 있는 시간 복잡도는 O(1)이지만 충돌이 발생했을 경우는 이를 해결하는 과정이 필요하므로 chaning을 통해 끝까지 간다고 하면 최악의 경우 O(N)까지 늘어날 수도 있다.

=> 해시 테이블은 설계를 잘 해야 한다.

충돌이 난 페이지 번호들이 모두 chain으로 연결이 되어 있다.
q라는 페이지는 s라는 frame에 저장이 되어 있고, p라는 페이지는 r이라는 frame에 저장이 되어 있다.
=> 이렇게 체인을 통해 대롱대롱 매달려 있다.
=> 최악의 경우엔 시간 복잡도가 O(N)으로 트리를 사용했을 때보다 오히려 느리게 될 수도 있다.

=> 해시 함수는 함부로 사용할 수 없지만 해시 함수를 잘 디자인해서 체인이 최대한 짧아지도록 한다면 해시를 사용한 기법이 효과를 발휘할 것이다.

=> 무조건적으로 어떤 기법이 좋다고 말할 수는 없지만 32bit 주소체계 이하인 경우엔 트리의 깊이가 2 이하이기 때문에 그러한 경우엔 Hashing보단 2단계 페이지 테이블이 나을 것이다.

 

Inverted Page Table

페이지 테이블은 프로세스마다 각각 갖는다고 했다.
=> 자신의 address space를 매핑하는 테이블을 갖게 된다.

32bit 머신의 경우 페이지 사이즈가 4KB라고 했을 때, 페이지 테이블의 크기가 4MB고 프로세스가 10개면 40MB의 메모리가 필요할 것이고, 100개라면 400MB가 페이지 테이블로만 채워질 것이다.

그런데 우리가 과연 모든 프로세스들이 자기만의 페이지 테이블을 유지하는 방법을 쓸 수 밖에 없을까??
logical address space는 주소 체계 전체를 다 쓴다고 가정한다. 그런데 하나의 프로세스가 4GB 전체를 다 사용하는 경우는 드물 것이다.

프로세스가 10개라고 하면 물리적으로 40GB의 메모리를 사용한다고 가정을 하는 것이다. 그런데 실제로 메모리의 크기가 4GB라면 말이 안 되는 상황이다.
=> 이러한 상황은 virtual memory에서 배울 것이다.

 

logical page 번호를 physical page로 변환하지 말고, physical page를 logical page로 매핑을 하자는 것이 Inverted Paging 기법의 기본적인 철학.

physical page는 DRAM의 사이즈에 의해 개수가 정해져 있다.
4GB라면 2^20개의 physical page가 존재한다. (페이지 사이즈가 4KB일 때)

DRAM의 첫 번째 페이지에는 프로세스 5번의 15번째 페이지가 들어가 있다. 두 번째 physical 페이지에는 프로세스 3번의 13번째 페이지가 들어가 있다.
이렇게 physical page를 logical page로 매핑시키게 되면 DRAM의 사이즈로 페이지 테이블의 크기가 정해지게 된다.
그리고 실제로 메모리에 탑재된 페이지에 대한 정보만 테이블에 들어가게 된다.
=> 실제 사용 중인 페이지에 대해서만 매핑 정보를 유지하자.
=> 페이지 테이블이 프로세스마다 생성되는 것이 아니라 컴퓨터 내에 딱 하나만 생성되게 된다.

 

이 방식이 가능하게 하려면 위에서부터 쭉 찾으면서 pid와 p가 매칭되는 엔트리를 찾아야 한다.
즉, 원래 페이징 기법에서는 페이지 번호 p를 사용해서 바로 거기로 점프할 수 있었는데, 이건 순차적으로 search를 해야 한다.
=> Associative search: 어떤 필드의 값이 일치하는지 비교하면서 Search를 하는 것.
=> 오래걸린다.

TLB 역시 Associative search를 하는데, 이걸 한 큐에 해주는 하드웨어의 도움을 받는다고 했지만 여기엔 사용을 하지 않는다.

어쩔 수 없이 위에서부터 하나 하나 읽으면서 비교를 해야 한다.
=> Inverted Paging 기법의 단점

이 단점을 해결하기 위한 방법이 해싱을 사용하는 것이다.
pid와 p를 해시 함수의 input으로 넣어서 DRAM에서의 인덱스를 output으로 내는 해싱을 사용하면 된다.

또는 TLB를 사용하면 miss가 난 경우에만 페이지 테이블을 Search하면 되기 때문에 hit가 많이 나면 Search를 하는 비중이 적을 것이다.

그런데 Inverted paging 기법을 사용하면 페이징 기법의 큰 장점인 page sharing이 불가능하다는 문제가 있다.
=> 이게 왜 불가능할까?
Inverted paging에서는 해당 DRAM의 frame과 매핑된 logical 페이지가 엔트리로 저장되게 되는데, 만약 페이지를 공유하게 되면 하나의 엔트리에 해당 frame을 공유하는 모든 프로세스의 정보가 적혀야 한다.
=> 이걸 다 적으려면 페이지 테이블의 크기가 커진다. 그리고 5개의 프로세스가 페이지를 공유한다고 하면 Search할 때 이 5개 엔트리를 모두 Search해야 한다.
=> 여러 문제가 있기 때문에 Page sharing을 사용하지 못 한다.

 

Segmentation

페이징 기법은 가장 큰 특징이 DRAM도 frame이라는 똑같은 크기로 자르고, 프로세스의 address space도 페이지라는 같은 크기로 모두 자른다고 했다.

프로세스의 address space를 단순히 크기만 가지고 잘라냈다.
프로그램 코드를 보면 어떤 함수가 호출되고 있는데, 함수의 일부는 첫 번째 페이지에 들어가고 함수의 뒷부분은 두 번째 페이지에 들어가는 상황이 발생한다.
또는 array를 선언했는데 array의 앞 부분은 다섯 번째 페이지에 들어가고 뒷 부분은 여섯 번째 페이지에 들어가는 경우가 생길 수 있다.
이게 그냥 크기를 기준으로 잘라서 발생하는 현상이다.
=> 이렇게 하면 잃어버리는 정보가 생긴다. "의미적인 덩어리"라는 개념을 잃어버린다.
=> 이걸 잃어버리면 뭐가 안 좋을까?
공유할 때 안 좋겠다는 생각을 할 수 있다. 예를 들어 이 object는 공유를 해도 되는 부분이야, 저 object는 공유를 하면 안 돼. 이런 것들이 object의 특성에 의해 결정되는데 사이즈 단위로 자르다 보니 어떤 페이지 안에는 공유할 수 있는 놈 반, 공유할 수 없는 놈 반. 이렇게 섞여서 들어갈 수가 있다.

또 프로그램의 코드 부분은 전체를 공유할 수 있다고 하면, 이 코드는 공유를 할래 이렇게 선언을 하면 되는데 크기 별로 5개로 나눠져 있다고 하면 5개에 대해서 각각 공유를 선언해야 한다.

의미는 무시하고 크기 단위로 잘랐기 때문에 생긴 문제.
=> 의미 단위를 유지하면서 자를 수 있는 방법은 없을까??

address space를 segmentation단위로 자르겠다.
그리고 잘린 각각은 길이가 다 다를 수 있다는 것을 허용한다.
메인 프로그램 한 덩어리, 메인 함수에서 호출하는 함수 한 덩어리, 현재 사용하는 스택 한 덩어리... 이렇게 의미 단위별로 자를 수 있다.

=> logical address space는 의미 단위들의 집합이 된다.

이건 페이징 기법이랑은 별개의 기법이다.
기본적으로 Contiguous Allocation이라고 생각하면 된다. 원래는 전체 address space를 통째로 연속적으로 올리는 것이었는데 그건 좀 심하고, 의미 단위들을 연속적으로 올리자.
main program을 연속적으로 올리고, Sqrt도 연속적으로 올리는데 main program과 Sqrt가 연속적일 필요는 없다.
=> 각각만 연속적으로 올라가면 된다.

 

그런데 이렇게 segmentation 단위로 메모리에 올리게 되면 주소 변환은 어떻게 할 수 있을까??

logical address를 page number와 offset으로 자르는 것과 비슷하게 segment number와 offset으로 자르자.

그리고 segment table을 유지하자.

Segment table에는 각각의 segment의 시작 주소를 담는 field가 하나 있다 (Base).
그리고 그 segment의 길이를 담는 정보가 하나 있다 (limit)

Base와 Limit의 페어가 segment table의 엔트리가 된다.

segment 번호를 보고 segment table 내에서 엔트리를 찾아내서 Base와 limit 정보를 얻는다.
Base에 offset을 더하면 원하는 데이터가 들어있는 주소를 알아낼 수 있다.

이렇게 각 segment에 번호를 매기고 segment table에는 segment 번호 별로 segment가 저장된 메모리의 시작 주소와 segment의 길이를 엔트리로 저장한다.

만약 4번 segment인 symbol table의 데이터에 접근하고 싶다고 하면 segment table에서 4칸을 내려가면 base가 4700임을 알 수 있다.

4700에 offset을 더해서 원하는 데이터를 얻을 수 있다. 이때 offset이 segment의 길이인 limit보다 크면 세그먼트의 범위를 넘어가는 접근이므로 보호를 해야 한다.

 

---

실행시킬 프로세스의 segment가 몇 개일지 모르기 때문에 OS는 segment table의 길이를 미리 알 수 없다.

그냥 미리 테이블을 할당해두고 사용하지 않는 부분은 invalid로 표시를 하자.

segment table 내에 세그먼트에 대한 접근 방식도 명시할 수 있다.
이게 왜 가능햐냐?
의미 단위로 분할이 되었기 때문에 이러한 디테일한 접근 컨트롤이 가능하다

=> Read only인 segment에 Write를 하려고 하면 막을 수 있다.

Sharing이 매우 effective하게 일어날 수 있다.
=> Segment 단위로 sharing을 할 수 있다.
페이지 단위로 하나 하나 sharing을 하는 것이 아니라 세그먼트를 통째로 sharing이 가능하다.
=> Segmentation 기법의 막강한 장점

그런데 Segmentation 기법을 사용하면 Contiguous Allocation과 동일하게 dynamic allocation problem이 생긴다.
이 Segment를 비어있는 공간 중에 어디에 올려야 할지를 결정해야 한다.
=> Segment 별로 크기가 다 다르기 때문에 발생하는 문제.
=> External fragmentation 문제가 발생할 수 밖에 없다.
=> Segment 크기에 맞게 할당하기 때문에 internal fragmentation은 발생하지 않는다.

발생하는 fragmentation의 종류가 Contiguous allocation과 동일하고 페이징 기법과는 반대다.

페이징 기법은 마지막 페이지에서 internal fragmentation이 발생하지만 frame과 페이지의 크기를 동일하게 자르기 때문에 external fragmentation은 발생하지 않았다.

 

Segment를 통째로 Sharing을 할 수 있게 된다.

 

Segmentation with paging

Segmentation 기법에서 발생하는 external fragmentation 문제를 해결하기 위해 페이징 기법을 도입한다.

페이징 기법과 동일하게 DRAM을 frame 사이즈로 동일하게 자른다.
그런데 logical space는 segmentation 단위로 자른다.
그리고 그 각각의 segmentation을 페이지 단위로 자른다.
=> 페이징 기법과 엄연히 다르다.

어느 데이터는 몇 번 세그먼트에 포함된 몇 번 페이지의 몇 번 offset에 있다.
이런 개념이 생긴다.

그냥 segmentation 방식은 하나의 segment가 연속된 공간에 올라오기 때문에 시작 주소로부터 offset을 더해서 원하는 데이터를 찾을 수 있었는데, 이제는 하나의 segment가 곳곳에 흩어져 있다.
=> 시작 주소에 offset을 더하는 방식이 통하지 않게 된다.

원래는 segment table에서 segment 번호만큼 내려가보면 limit과 base address가 저장되어 있다고 했다.
그런데 segmentation with paging 기법에서는 base가 아무런 의미도 없다. 하나의 segment가 여러 페이지로 나눠져서 들어가기 때문에.
대신 이 segment를 구성하는 각각의 페이지가 몇 번 frame에 들어가는지를 나타내는 페이지 테이블이 필요하다.
=> 즉, segment마다 페이지 테이블이 필요하다.
=> base 대신에 segment의 페이지 테이블의 시작 주소가 저장된다.

이걸 이용해서 segment의 페이지 테이블로 가서 페이지 번호를 이용해서 해당 페이지가 저장된 시작 주소를 찾아서 offset(displacement)을 더해서 원하는 데이터를 찾는다.

 

최종적으로는 페이지 단위로 저장되기 때문에 external fragmentation이 발생하지 않는다.
대신 internal fragmentation이 발생하게 된다. (마지막 페이지에만)

메모리 사용 효율 측면에서는 페이징 기법과 동일하지만 segment라는 개념은 유지된다.
=> 의미 단위는 유지되지만 공간 효율 측면에서는 페이징 기법과 동일

 

메모리 주소 변환에는 TLB가 사용된다고 했다. TLB까지 적용된 Segmentation with paging의 과정은 어떨까

세그먼트 번호와 페이지 번호를 사용해서 TLB look up을 하게 되고, TLB hit가 발생하면 찾는 데이터가 저장된 세그먼트의 페이지의 시작 주소가 변환 결과로 나오게 된다.

=> 굳이 segment table에서 페이지 테이블 시작 주소를 찾아서 페이지의 시작 주소를 찾을 필요가 없게 된다.

 

요즘 대부분은 Segmentation with paging 기법을 사용하는데, OS마다 구현의 방식은 다를 수 있다.
=> 기본적인 틀은 위와 같다.

 

※ 본 내용은 한양대학교 강수용 교수님의 강의를 바탕으로 작성되었습니다.