[운영체제] 페이징 Paging

 

1. 페이징

(1) 페이징

 페이징이란  프로세스를 일정 크기(=페이지)로 잘라서 메모리에 담는 기법을 말한다.

외부 단편화를 해결할 수 있으나 내부 단편화가 발생할 수 있다. 

• 페이지 Page : 프로세스를 나눈 조각
• 프레임 Frame : 메모리를 나눈 조각

페이지를 프레임에 할당하고, MMU의 재배치 레지스터 값을 바꿔 CPU가 프로세스가 연속된 메모리 공간에 위차한다고 착각하게한다. 

페이지가 어느 위치의 프레임에 저장될 지를 재배치 레지스터가 기억한다.

MMU는 페이지 테이블(page table)이 된다.

 

 

2. 주소 변환

1) 논리주소 (Logical address)

•  CPU가 내는 주소는 2진수로 표현된다. (전체 m 비트)
• 주소는 페이지 번호(p)와 변위(displacement, d)로 나누어진다.
• 페이지 크기에 따라 하위 n비트가 변위(d)가 결졍되고, 그 나머지 앞부분(m-n비트)은 페이지 번호(p)가된다.
• 페이지 크기는 하드웨어에 의해 정의되는데, 논리적 주소를 페이지 주소와 간격으로 바꾸는 것이 수월하도록 보통 2의 제곱 형태로 정해진다. 페이지 사이즈를 2의 제곱 형태로 나타냈을 때, 지수가 n이 된다. (예시. page size = 4 = 2^2 -> n=2 , page size = 1 kb = 2^10 -> n=10)

 

 

2) 주소변환 : 논리주소 → 물리주소 (Physical address)

• 페이지 번호(p)는 페이지 테이블의 인덱스로써 사용된다.
• 페이지 테이블의 인덱스 페이지 번호(p)의 값이 물리 주소의 프레임 번호 (f)가 된다.
• 페이지 테이블은 물리적 메모리의 각 페이지의 Base 주소(시작 주소)를 저장하고 있다
• Base 주소(시작 주소)와 변위(d)를 합해 메모리의 물리적 메모리 주소를 정의할 수 있다.

 

 

3) 주소 변환 예시

 

예시1) 아래 조건에서 논리주소 13 번지는 물리주소 몇 번지 인지? 

Page size = 4 bytes

Page Table: 5 6 1 2

 

page size = 4 bytes = 2^2 -> n=2

13 = 1101(1) -> p : 11(2) = 3, d = 01(2)

page table [3] = 2 = 10(2) = f

physical address = 'f' +  'd' -> '10' + '01' = 1001(2) = 9

물리주소 9 = 10(2) (=2)번째 프레임에서 01(2) (=1) 만큼 떨어진 곳 (Page size = 4bytes -> 2번째 프레임 위치 : 8~12)

 

 

예시 2)

프로세스 P1을 여러 페이지에 나누어 할당할 경우

P1의 0번째 페이지는 메모리의 5번 프레임에,

P1의 1번째 페이지는 메모리 3번 프레임에, 

P1의 2번째 페이지는 메모리 2번 프레임에 , ... 할당된다.

 

P1의 3번재 페이지를 CPU가 50번에 할당하라고 했을 때,  (페이지 크기 16byte -> n=4)

50 =. 110010(2)  -> 11(2) : page number(p) , 0010(2) : d -> page table 11(2) = 3째 거쳐서 변환된다. 

page table 3째 값 = 8 = 1000(2) = frame number(f) , d = 0010(2) = 2

8번쨰 프레임의 위치는 130

 

 

 

예시 3) 아래 조건에서 물리/논리주소는 몇 번지인지?

page Size = 1KB

Page Table: 1 2 5 4 8 3 0 6

 

3-1) 논리주소 3000번지는 물리주소 몇 번지?

 

page size = 1 KB = 2^10 -> n=10

3000 = 101110111000(2) -> p : 10(2) = 2,  d : 1110111000(2)

page table [2] = 5 = 101(2) = f

physical address = 'f' + 'd' = '101' + '1110111000' = 1011110111000(2) = 6072

 

3-2) 아래 조건에서 물리주소 0x1A53 번지는 논리주소 몇 번지?

page size = 1 KB = 2^10 -> n=10

0x1a53 = 1101001010011(2) -> f=110(2) = 6, d=1001010011(2)

f = 6 -> p = 7 = 111(2)

logical address = 'p' + 'd' = '111' + '1001010011' = 1111001010011(2) = 0x1e53

 

 

3. 페이지 테이블 만들기와 유효 메모리 접근 시간

1) 페이지 테이블 만들기

• CPU 레지스터 사용
  • 장점 : 주소 변환이 빠르다. 논리주소를 페이지 테이블 거쳐서 변환되는데 CPU에 있으면 변환이 빠르다 
  • 단점 :  페이지 테이블 엔트리를 많이 생성할 수 없다. 
• 메인 메모리 사용
  • 장점 : 페이지 테이블 엔트리를 많이 생성할 수 있다.
  • 단점 : 속도가 느리다. (2배. 페이지 테이블 1번 읽고, 변환한 주소 읽고) 
• TLB (Translation Look-aside Buffer) 사용 
  • 캐시메모리처럼 별도의 SRAM으로 사용하는 방법이다. 속도와 용량(테이블 엔트리 수) 면에서 CPU와 메인 메모리 중간이다.
  • 속도 : (빠름) CPU > TLB > 메인 메모리 (느림)
  • 용량 : CPU < TLB < 메인 메모리

 

2) 유효 메모리 접근 시간 Effective Memory Access Time

nano = 1/10억

Tm 메모리 읽기 시간 : 100ns

Tb 테이블(버퍼) 읽기 시간 : 20 ns

h : hit ratio = 80%

 유효 메모리 접근 시간 = Tm + Tb (버퍼에 페이지 테이블 전부 올라와있는 경우 (hit ratio=100%인 경우))

 유효 메모리 접근 시간 = h*(Tm + Tb) + (1-h)*(Tb + Tm + Tm) 

-> (miss 확률 = (1-h)) * 버퍼 읽기 Tb + 메모리에 페이지 테이블 읽어서 버퍼에 가져오기 Tm + 메모리 읽는 시간 Tm)

 

0.8*(100+20) + (1-0.8)*(20+100+100) = 140ns

메모리 읽기 시간은 100ns인데 40% 느려진 것이다.. 

그러나 실제 hit ration = 95% 정도이다.

다시 계산하면 

0.95*(100+20) + (1-0.95)*(20+100+100) = 125ns 이다.

 

 

4. 내부 단편화

페이징으로 외부 단편화는 해결할 수 있지만 내부 단편화(할당 후 남는 메모리 낭비)가 발생할 수 있다. 

(프로세스 크기가 페이지 크기의 배수가 아니라면 마지막 페이지는 프레임을 다 채울 수 없는데, 그 남는 공간이 낭비된다.)

외부 단편화와 내부 단편화
https://almighty-denver.tistory.com/315