[운영체제] 페이징 테이블 계산 기초

페이징 계산은 운영체제 공부 중 중요하게 다뤄지는 내용 중 하나이다.

따로 포스팅하여서 정리하도록한다.

 

1. 페이징이 무엇인가

 

페이징은 보통 메모리 스페이스를 잘게 나눠서 메모리에 저장하는 가상화 방식중 하나이다.

 

2. 페이징을 왜쓰는가

 

내가 저장하고싶은 메모리는 10KB인데, 남은자투리메모리공간은 4KB, 7KB라고해보자.

 

[   점거 | 4KB FREE공간 | 어떤프로세스가 점거 | 7KB FREE 공간 ]

 

그럼 10KB가 들어갈 자리가 없다.

그걸 방지하기위해서 나온 기술이 페이징기술.

 

프로세스 메모리 공간을 모두 일정한 페이징단위로 나눠서,

분배해주는방식이다.

 

그럼 사용자입장, 가상화부분에서는

페이지가 메모리에 순서대로 잘 정리되어있다고생각하고

예를들어 이렇게..

 

int a[] = {1,2,3,4,5};

 

사용자의 View 

Memory

0x1000

0x1004

0x1008

....

 

실제 메모리에서는

메모리 리소스가 나눠서 들어가있다 라고 본다

0x3000

0x4003

...

....

 

 

 

3. 페이징 관련 용어정리

 

 

1) 페이지 사이즈 : 메모리를 작게나눌때의 그 사이즈, 각 페이지 블럭별 사이즈를 의미한다. 2^n 씩 커진다. ex) 4KB.

 

1-1) 페이지 : 그 한 블럭을 의미한다.

 

1-2) 페이지 테이블 : 

 

페이지테이블은 이곳에서 단순히 배열이라고 설명한다 (linear page table 혹은 array)

페이지테이블에따라 우리는 가상주소에서 -> 실제주소로 해석하는 과정을 거친다.

a index	value
0	1
1	3

배열도 인덱스와 벨류로 나누게되면 이렇게 멋진 테이블이 완성된다.

예제에서는 int형 배열을 생각한다.

int a[] = {1 ,3 };

 

1-3) Page Table Entry

페이지 테이블 엔트리는 페이지 테이블 내 하나의 칸을 뜻한다.

a[1], a[2]...

 

int a[] = {1 ,3 }

는 각 칸마다 총 4byte를 사용한다 (int형은 한칸당 4바이트다)

즉 PTE의 각 크기는 4BYTE (이 예제에서)

 

 

2) 오프셋 : 한페이지블럭이 주소를 얼마만큼 점거할수있는지 범위를 나타낸다.

 

만약 4KB를 점거했으면 

0부터 4KB만큼 내가 활용할 수 있다는 의미이다. (0부터 시작이라고 가정)

 

페이지 사이즈가 16byte라면 오프셋비트가 얼마나 필요할까? 

가장 작은사이즈 단위가 1바이트라고 가정한다면,

최대로 다 점거한다면 총 16개의 바이트를 먹는다는뜻이다.

 

즉, 0이 시작점이라면,

0 페이지범위

1  

2

..

..

15 페이지범위

16

...

 

총 16개의 페이지범위를 

이를 비트로 표현하기위해서는 총 몇개의 비트가필요할까?

2^x = 16이므로

x = 4

 

비트로 표현하는이유는, 가상메모리주소에 페이지 정보를 담아줄거다.

 

4KB면 얼마나필요할까?

4KB = 4 * 2^10 이므로,

총 2^12 = 4KB,  따라서 총 12비트가 필요하다.

 

이렇게 따로 표시해줌으로써, 어느곳에 점거하더라도, 다른 프로세스와 겹치지않게 정확하게 자기 블럭의 범위를 알 수 있다.

 

 

3) Virtual Page Number

 

 

간단하게 다시설명하자면

[가상 주소] -> 임의의 규칙적용 -> [원래주소] 로 번역

가상주소에  가상페이지정보, 오프셋등을 담는다.

OS는 그주소를 페이지테이블과 함께 해석한다.

 

OS는 페이지테이블 정보를 가지고있다라고 생각하면, (혹은 페이지테이블의 주소를 가지고있다)

가상주소 + 페이지테이블 참고 => 물리주소로 해석.

 

그럼 OS는 가상주소에서

그 페이지테이블에서 어떤걸 봐야되는지를 알고싶을거고

그 페이지가 얼마만큼의 범위를 차지하는지 알기위해서 오프셋도 알고싶을것이다.

 

어떤걸 봐야되는지 알려주는게 가상페이지넘버 (VPN) 이다.

가상주소가 16비트시스템이라고하고

오프셋이 12비트라고하면

남은 4비트가 이 가상페이지넘버를 표현할 수 있는 부분이 되겠다.

그럼 배열에서 16개 크기의 배열을 보유할 수 있다는의미이기도한다.

 

int a [16] = { 0, 1,2, 3,... };

 

 

총 16비트 가상주소 (0x 0001) 

[  0000 ] [ 나머지는오프셋 12비트]

가상페이지넘버 = 0 혹은 a[0]

가상페이지넘버의 범위는 1번재부터 4번째까지.

총 올수있는 가상페이지개수 = 2^4 = 16개

 

 

=========================

연습문제

 

1. 32비트 주소체계

2. 4KB 페이지를 사용.

3. 4 byte 엔트리

페이지테이블 실제크기는 얼마나 클까요?

 

4KB 페이지 사용 = 12비트를 오프셋으로

나머지 비트는 페이지에 사용할 수 있다.

총 20비트는 페이지 크기가 될것이다.

 

그렇다면 저 페이지테이블을 인덱스라고 생각한다면

총 인덱스는 2^20개가 생길것이다.

그곳에 각 인덱스별 크기가 4byte로 했으니 총 2^20 * 4 = 4MB.

==========================

 

==========================

실전문제

 

그럼 실제로 OS가 되어서 해석해보도록한다

 

0x0010 : load 0x1100, %edi.

라는 어셈블리를 해석한다.

 

이때, 페이지 테이블 엔트리는 4byte

각 페이지는 4kb짜리 = 오프셋 12비트.

페이지테이블의 주소는 0x5000으로 시작한다.

페이지는 int a[] = {2,0,80,99}; 라고 가정한다.

 

1. 처음에는 Instruction 자체에 접근을 먼저 시도하기때문에

0x0010이 들어온다.

 

오프셋 12비트이고, top 4비트 (VPN영역)을 보니 0이다.

그럼 VPN = 0이므로

a[0] = 2 

 

즉 PPN은 2가됨을 알 수 있다.

 

2. 메모리에 접근시도한다.

 

PPN이 2가되면,

PPN + OFFSET으로 메모리주소를 알아낼수있다.

2 + offset (0010) 

0x2010으로 물리주소임을 알 수 있다.

 

 

상세한 과정으로 다시소개한다.

1. 페이지 테이블에 접근

2. 페이지 테이블 주소인 0x5000에 접근해서 PPN값 받아오기 (메모리접근 1회)

3. 페이지 테이블을 통해 PPN얻은걸로 실제주소리계산 (PPN + offset)

4. 메모리 주소 계산 후 접근 (메모리접근 1회)

 

총 메모리 접근 2회를 통해, instruction에 접근했다.

 

두번째는 실질적으로 LOAD를 해야한다.

1. 페이지 테이블에 다시 접근 시도.

2. 가상주소가 0x1100이기때문에, 페이지넘버는 1, 오프셋은 100임을 알수있다.

3. 페이지테이블내 인덱스 1번으로 가려면 x5004로 접근해야한다.

 

[5000, 5001 5002 5003] [5004 5005 5006 5007] ....

 

앞써 가성에서 봤듯이 페이지엔트리가 4byte 혹은 int형이기때문에

각 배열별로 총 4칸씩 점거한다. 

그렇다면, 첫번째 페이지 넘버로 접근하기위해서는 5004번으로 접근해야한다.

(배열첫번째 + VPN * page number)

 

배열 3번째값은 배열 1번째주소에서 배열 2개만큼 더한것

a[2] = a[0]에서 2칸전진 (4byte + 4byte)

주소로 계산할때는 배열의칸도 직접계산하고, 배열의 첫번째 주소만알려주고, 배열의 칸의 크기는 얼마인지를 주로준다.

인덱스에 접근하려면 배열의 첫번째주소와 배열의 칸의 크기로 정확한 크기에 맞게 접근해야함 ^^;

 

4. int a[] = {2,0,80,99};  a[1] 은 0이므로

VPN = 1

PPN = 0

 

5. 따라서 주소계산으로 나온결과는 0x0100

6. 0x0100에 접근.

 

======================