Paging
연속적으로 물리 주소를 할당하니 여러 문제가 생겨서 이 문제를 해결하기 위해 나온 개념이다.
paging이란 간단히 말해 논리 주소 (= 가상 주소)는 연속적으로 할당하나 물리 주소를 비연속적으로 할당하는 것이다. 할당할 때 하나의 단위로 메모리를 나누는데 논리 주소와 물리 주소에서 부르는 명칭이 다르다.
논리 주소에서 고정적 단위를 Page라고 한다. 조금 더 자세히 말하면, DRAM에서 Row 하나에서 Active되는 Column의 갯수를 말한다.
물리 주소에서 고정적 단위를 Frames라고 한다.
보통 하나의 page 크기는 512B ~ 16MB로 지정하는데 보통 4MB로 지정한다. 그런데 고정적인 크기로 지정하여 할당하면 예전에 말했던 static allocation과 뭐가 다르냐는 궁금증이 생길 수도 있다.
차이점은 크기의 차이다. 예전은 단위가 컸다면 Frames와 page는 작은 단위다. (+운영체제는 빈 frames를 계속 추적하고 있다가 할당해준다.)
아래 그림을 보면 논리 주소와 물리 주소는 page tabel라는 자식에 의해서 mapping 된다.
그림을 보면 논리 주소와 물리 주소가 서로 다르게 존재하는데 이렇게 되면 어떤 문제가 생기냐, 실행이 뒤죽박죽 된다.
물리 메모리에 올라가 실행되는데 순차적으로 실행된다고 하면 서로 다른 프로그램이 돌아갈 수도 있다.
무슨 말이냐 하면, 논리 메모리 상에서
page0, page1에는 카카오톡 프로그램이 할당되고
page2, page3에는 네이버 프로그램이 할당됐다고 한다면,
물리 메모리의 실행 순서는 0-2-1-3으로 실행되니까 이상하게 실행된다. 그러니 cpu에게 어떤 프로그램을 연속적으로 실행시키기 위해서 나온 게 page table을 만들어서 프로그램이 연속적 동작을 할 수 있게 한다.
간단히 말해 어떻게 mapping 됐는지 기록하는 table이 존재하는데 그게 page table이다.
paging을 하면 좋은 점은 shared pages로 코드를 공유할 수 있다는 점이다( reentrant ).
예를 들어 여러 프로세스를 돌린다고 할 때 동일한 라이브러리를 호출한다고 하면 한 번만 메모리에 올리고 나머지는 각각의 page table에 가지고 있으면 된다. 즉, 메인 메모리의 용량 사용을 줄일 수 있다. 이때 전제 조건은 코드가 변하지 않는 코드여야 한다. 가령 printf() 같은 함수가 있다.
Page Table
간단히 말해 논리 메모리와 물리 메모리가 어떻게 짝을 지어 mapping 됐는지 기록하는 table이다.
그렇다면 논리 주소에서 물리 주소로 어떻게 변환되는지 보자. 다른 말로는 page table 중에서 어느 index를 선택하는지 보자.
cpu에서 생성된 bit에서 page를 선택하는 bit는 아래와 같은 format을 따르는데,
page number는 page table의 몇 번째 index를 지정한다.
page offset은 물리 주소의 위치를 지정한다. frame에서 어디에 위치하는지 정한다.
논리 주소 공간은 2^m이고 page size는 2^n이라 주어졌을 때, 아래처럼 page number는 m-n bit , page offset은 n bit만큼 차지한다.
page table 하나하나를 page table entry라고 부른다.
흐름을 아래 그림을 보며 따라가 보자.
cpu는 page number와 page offset을 decoding 해서 메모리에 접근하는데 이때 page number를 이용해서 page table에 있는 frame index를 가리킨다. 좀 더 자세히 말하면 frame의 시작 주소를 뽑아낸다.
그리고 page offset을 그대로 가져와서 frame index 중에서 어디에 위치하는지 알아낸다.
이런 page table은 모든 core마다 자신만의 page table을 가지고 있다.
아래 그림을 보며 예를 들어보자
논리 주소는 2^4 = 16byte (m=4)이고, page size는 2^2 = 4byte (n =2)로 가정하고 물리 주소는 32byte로 가정하자.
만약 논리 주소 0번째인 "a"를 물리 주소로 매핑한다면, 0은 4bit로 0000이다.
만약 논리 주소가 32bit라면 0을 32bit로 나타내야 한다. 이때 상위 2bit는 page number로 사용되고, 하위 2bit는 page offset으로 사용된다.
그러니, p = 0, d = 0으로 세팅된다. page table 0번 index를 선택하는데 이때 5번과 mapping 돼 있으니 frame의 5번에서 시작한다는 의미다. 그러니 page size만큼 곱해줘야 시작 주소를 가리킨다. 또한 해당 frame에서 어디에 위치하는지는 d로 알 수 있는데 마찬가지로 0이다.
즉, 5 * 4 (page size) + 0 = 20이다.
또 다른 예로 논리 주소 11번째에 있는 "l"을 mapping 시켜보자.
11은 4bit로 1011이다. 이때 상위 2bit는 10으로 page table에서 2번 index를 가리킨다. 2번 index는 frame의 1번 index라고 한다. 또한 하위 2bit는 11로 3을 의미한다.
정리하면 1번 frame에서 3번째 주소에 l를 매핑시킨다는 의미다. (1 * 4 + 3 = 7)
이렇게 paging을 하면 전체 메모리 용량이 남는데 프로그램을 할당 못하는 External fragmentation은 해결됐지만, Internal fragmentation은 여전히 남아 있다.
어떤 거냐면, page size가 2KB( 2,048B )이고 프로세스가 72,766B라면 36page를 할당하고 1,086B만큼 남는다. 평균 page size의 절반 정도가 fragmentation 된다.
아니 그러면 page size를 줄이면 되는 거 아닌가 하는 생각이 든다. 하지만 말했듯이 운영체제는 frame을 계속 추적하고 있다. 그렇기 때문에 size가 작아지면 추적해야 하는 양도 엄청 늘어난다. cost가 많이 들어간다.
또 다른 예를 들어보면, 32bit 논리 주소 환경에서 page size가 4KB ( 2^12 )라면, (2^32 / 2^12)를 계산하면 100만 개의 entry가 필요하다는 의미다.
즉, 물리 메모리에 page 하나가 4MB를 차지하는데 이게 하나의 프로세스에 대한 용량이니 100개가 돌아간다고 하면 400MB의 용량을 차지한다는 의미다. ( page number가 20bit, page offset이 12bit )
이렇듯 용량을 많이 차지하고 overhead도 많이 들어가니까 효율이 떨어진다. 이에 cache 메모리를 이용할 수밖에 없다. 그래서 나온 것이 TLB다.
TLB에 대해선 다음에 포스팅하겠다.
'반도체 그 다음 학문 > 운영체제 (OS)' 카테고리의 다른 글
| 운영체제 Swapping ( page in, page out ) (0) | 2022.06.08 |
|---|---|
| 운영체제 TLB ( Translation Look-aside Buffer ) (0) | 2022.06.08 |
| 운영체제 Memory Allocation (논리메모리, 물리메모리, Dynamic Loading, paging이 나온 이유 ) (0) | 2022.06.08 |
| 운영체제 LRU ( Least Recently Used, FIFO, Belady's Anomaly, Page and Frame Replacement Alogorithms ) (0) | 2022.06.07 |
| 운영체제 Deadlock Detection (Deadlock 해결방법, 하드웨어 Deadlock) (0) | 2022.05.19 |
댓글