[OS] 페이징 시스템(Paging System)

페이징(paging) 개념

• 크기가 동일한 페이지로 가상 주소 공간과 이에 매칭하는 물리 주소 공간을 관리
• 하드웨어 지원이 필요
  • Intel x86시스템(32bit) CPU에서는 사이즈 단위를 4KB, 2MB, 1GB 지원
• 리눅스에서는 4KB로 paging
• 페이지 번호를 기반으로 가상 주소/물리 주소 매핑 정보를 기록/사용

페이징 시스템(paging system)

실질적인 예를 기반으로 페이징 시스템에 대해 알아보자.

• 프로세스(4GB)의 PCB(Process Control Block)에 Page Table 구조체를 가리키는 주소가 들어있음
• Page Table에는 페이지 각각의 번호 별로 가상주소와 그에 해당하는 물리 메모리 주소를 매핑해놓은 정보가 있음

PCB 구조

페이지 테이블은 페이지가 엄청 많으니까 당연히 길다. 그 페이지 테이블 맨 위에 접근할 수 있는 주소를 저장해놓는다.

위 그림을 참고해서 CPU가 어떤 가상주소에 접근하려고 할 때를 생각해보자.

일단, 이 가상주소를 통해 어떤 페이지 번호인지 바로 알 수 있을 것이다. 그 페이지 번호를 통해 PCB에 있는 페이지 테이블 구조에 들어가서 맨 위에서부터 몇 번째인지 찾아가며 매칭되는 물리 주소를 알아낸다. 그 물리주소를 갖고 실제 코드나 데이터 정보를 갖고 CPU에서 처리를 하게 된다.

---

페이징 시스템 구조

이제 좀 더 실질적으로 어떻게 동작하는지 살펴보자.

• page(=page frame) : 고정된 크기의 block(4KB)
  • 총 9KB의 데이터가 있다고 할 때 데이터가 쭉 쓰여지다보면, page1이 4kb, page2가 4KB, page3이 1KB라고 하면, 남는 3KB까지도 함께 물리메모리에 넣는다. 이 물리메모리의 주소는 페이지 테이블에 넣는다.
• paging system
  • 가상 주소 v = (p,d)
    
    • p : 가상 메모리 페이지
    • d : p 안에서 참고하는 위치(변위(=offset))

페이지 번호에 물리주소만 저장해놓고 d를 더하면 실제 물리 메모리에 있는 해당 데이터의 위치를 알 수 있다.

→ 페이지 크기가 4KB일 때로 예시를 들어보겠다. 32bit라고 하면 12~31bit는 페이지 번호가 될 수 있다. 4KB로 구성하다보면 실제 접근할 주소(코드 한 줄)은 어느 정도(예를 들어 2KB) 떨어져있을 수 있고, 그러면 page 번호의 base주소에 2KB(변위)를 더해주면 가상 주소를 알 수 있다. 

→ 즉, 가상 주소의 0bit에서 11bit는 변위(d)를 나타내며, 12bit 이상이 페이지 번호가 될 수 있다.

 

페이지 테이블(page table)

• page table
  • 물리 주소에 있는 페이지 번호와 해당 페이지의 첫 물리 주소 정보를 매핑한 표
  • 가상주소 v = (p,d) 라면
    • p : 페이지 번호
    • d : 페이지 처음부터 얼마 떨어진 위치인지
  • paging system 동작
    • 해당 프로세스에서 특정 가상 주소 엑세스를 하려면
      • 해당 프로세스 PCB에 있는 page table의 base 주소에 해당 가상 주소가 포함된 page 번호가 있는지 확인
      • page 번호가 있으면 이 page가 매핑된 첫 물리 주소(p')를 알아내면, p' + d가 실제 물리 주소가 됨

실제 프로세스 중 안 쓰이는 건 물리메모리에 올라갈 필요없으므로 valid-invalid를 체크하는 bit 또한 필요하다.

 

---

페이징 시스템과 MMU(컴퓨터 구조)

이제 MMU까지 합해서 살펴보자.

CPU는 가상 주소에 접근할 때 MMU 하드웨어 장치를 통해 물리 메모리에 접근한다.

이 때, 가상주소를 물리주소로 변환시켜주는데, PCB는 페이지 테이블의 base 주소를 갖고 있으므로 PCB를 통해 해당 페이지 테이블에 접근이 가능하다. 이러한 페이지 테이블 관련 정보는 디폴트로 물리 메모리에 들어가 있다.

프로세스가 맨 처음에 실행될 때, 페이지 테이블에 적재가 되면서 동시에 해당 페이지 테이블 base 주소가 별도 레지스터(CR3)에 저장되는 것이다.

그 후에 CPU가 해당 프로세스의 가상주소를 실행하기 위해 접근하게 되면, MMU가 CR3 레지스터를 가져와서 페이지 테이블 base 주소를 참조해서 물리주소로 변환을 한 다음, 해당 물리주소에 있는 데이터를 CPU에 가져다주게 된다.

---

다중 단계 페이징 시스템

• 32bit 시스템에서 4KB 페이지를 위한 페이징 시스템은
  • 하위 12bit는 오프셋
  • 상위 20bit가 페이징 번호이므로, 2의 20승(1048576)개의 페이지 정보가 필요함
• 페이징 정보를 단계를 나누어 페이지 디렉토리 생성
  • 필요없는 페이지는 페이지 테이블을 생성하지 않으면 공간 절약 가능
  • → 페이지 디렉토리 중 정말 필요한 영역에 대해서만 페이지 테이블을 생성하는 것을 다중 단계 페이징 시스템이라고 한다.
• 페이지 번호를 나타내는 bit를 구분해서 단계를 나눔
• 리눅스 기준으로 3단계이며, 최근 4단계까지 더 복잡하게 나눠서 처리되는 경우도 존재

다중 단계 페이징 시스템

• 전체 페이지 테이블의 맨 앞이 결과적으로는 페이지 디렉토리의 맨 앞을 가리키게 됨
• CR3 레지스터가 전체 페이지 테이블의 맨 앞에 들어가게 되고, 해당 주소에 대응하는 디렉토리로 가면 해당 디렉토리에 대한 페이지 정보를 갖는 페이지 테이블의 맨 앞 정보를 얻게 됨
• 해당 페이지 번호를 찾아서 그 페이지 번호와 Offset 정보를 갖고 물리 주소에 정보(데이터)를 갖고 온다.

---

MMU와 TLB(컴퓨터 주소)

• MMU가 물리 주소를 확인하기 위해 메모리를 갔다와야 함

  

  TLB가 없다면 메모리 접근 시간이 배로 들 것이다.

→ 문제는 메모리에 왔다갔다 하는 시간이 많이 걸린다는 것이다.

이러한 문제를 해결하기 위해 별도의 캐쉬 보조 하드웨어를 갖다놓는다.

TLB는 물리주소 cache역할을 수행한다.

• TLB(Translation Lookaside Buffer) : 페이지 정보 캐쉬

A라는 가상주소를 요청했더니 A'라는 물리주소가 나왔다고 해보자.이 정보를 TLB에 저장하는 것이다. 그래서 그 다음부터는 A라는 가상주소를 다시 메모리 요청하면 페이지 테이블을 갔다오는 것이 아니라 MMU 단계에서 TLB를 찾아본다. 찾아봐서 여기에 A의 물리주소가 있으면 2,3번 작업을 안 하고 4번 작업으로 바로 가기 때문에 메모리 접근을 두 번에서 한 번으로 줄일 수 있다.

---

페이징 시스템과 공유 메모리

• 프로세스 간 동일한 물리 주소를 가리킬 수 있음 (공간 절약, 메모리 할당 시간 절약)

  

  Linux에서의 공유메모리 개념

물리 메모리에는 하나만 갖다놓고 페이지 테이블에서의 주소를 변환할 때 해당 물리 주소만 동일하게 물리메모리를 가리키게 해놓으면 메모리를 2배로 쓸 이유가 없게 된다. → 공유 메모리의 개념

 

이 기법을 이용해서 몇 가지 기술이 가능한데 우선 리눅스의 예를 보자.

리눅스 프로세스에서의 4~3GB는 커널 공간이므로 결국에는 프로세스마다 운영체제를 다 갖고 있다는 말이 된다. 이렇게 되면 각 프로세스마다 추가로 1GB씩 붙어있게 되므로 공간 낭비가 되는 것 같아 아까울 수 있다.

그러나 기술적으로 보면 이 공간은 아깝지 않다. 그 공간에 해당되는 페이지 테이블은 결과적으로 동일한 메모리 공간을 가리키면 되기 때문이다. 그렇기 때문에 프로세스에서 커널을 일일히 다 갖고 있는 것처럼 보여도 어차피 물리메모리에서 공유가 되는 것이지 더 추가로 메모리 공간이 요구되진 않는다.

 

두 번째로 리눅스, 전통적인 유닉스 시스템에서 프로세스가 생성되는 방법은 무조건 어떤 프로세스에서 해당 데이터를 fork(복사)해서 새로운 프로세스(Child Process)를 만드는 것이다. 따라서 반드시 복사될 기존의 프로세스(Parent Process)가 있어야 된다.

프로세스 A와 프로세스 B는 4GB이다. 아무리 가상공간이라고 해도 어쨌든 있는 데이터니까 복사를 한다는 건 4GB를 통째로 복사한다는 건데, USB에 4GB 복사만 하려고 해도 어마어마한 시간이 걸린다..

 

그래서 실제로는 프로세스를 만들 때 그 공간을 복사하지 않는다. 그냥 페이지 테이블에서 프로세스 A의 일부가 들어있는 물리메모리의 공간을 프로세스 B 페이지 테이블도 우선은 가리키게 해놓는다.

굳이 4GB 전체를 복사하지 않고, 해당 공간의 물리메모리를 동일한 가상주소에 한해서 물리메모리만 업데이트해놓는 것이다. 이렇게 하면 프로세스 생성 시간은 굉장히 단축시킬 수 있다.

write 요청 시에는 어쩔 수 없이 copy가 요구된다.

그러나, 만약 새로 생성된 프로세스 또는 원래 프로세스가 해당 물리 메모리의 공간에 write를 하려고 할 때는 프로세스 A가 그 물리메모리에서의 데이터를 변경시킨다고 해서 프로세스 B가 그 변경된 데이터를 갖고 있으면 안 될 것이다. (그 둘은 완전히 다른 프로세스임을 잊지 말자.) 따라서 이 때만 복사를 해서 다른 공간에 놓고, 프로세스 B의 페이지 테이블의 물리주소값을 바꿔놓는다.

 

이렇게 하면 프로세스 생성시간을 굉장히 단축시킬 수 있으며, 커널과 공유메모리 등 공유데이터는 물리메모리 공간을 공유 가능하여 단순하게 page table의 해당 page에서 물리주소만 업데이트시키면 되기 때문에 공간 또한 절약 가능하다.

이 기법을 사용해서 리눅스 같은 경우에는 프로세스의 생성 시간까지도 줄일 수 있는 장점이 있다.

---

요구 페이징(Demand Paging 또는 Demand Paging)

• 프로세스 모든 데이터를 메모리로 적재하지 않고, 실행 중 필요한 시점에서만 메모리로 적재함
  • 요구 페이징은 선행 페이징의 반대 개념
  • cf) 선행 페이징(anticipatory paging 또는 prepaging) : 미리 프로세스 관련 모든 데이터를 메모리에 올려놓고 실행하는 개념
  • 더 이상 필요하지 않은 페이지 프레임은 다시 저장매체에 저장 (페이지 교체 알고리즘 필요)

페이지 폴트(Page Fault)

• 어떤 페이지가 실제 물리 메모리에 없을 때 일어나는 인터럽트
• Process에 있는 page3이라는 데이터를 갖고 오려고 할 때, page table에서의 page3에 대한 valid-invalid bit가 i(invalid)이면 page fault interrupt를 운영체제에 날려준다.
• 운영체제는 page fault interrupt를 받아 해당 페이지를 물리 메모리에 올려주고, page table의 물리주소도 올라가며 valid-invalid bit 상태도 v(valid)로 바뀌게 된다.
• 이렇게 하면 요구 페이징을 지원하기 위한 메커니즘이 만들어지게 된다.

페이지 폴트와 인터럽트

MMU, TLB, memory, OS까지 총괄적으로 전체 흐름을 살펴보자.

1. 맨 처음에 CPU가 가상주소를 요청한다. 그러면 MMU는 우선 TLB에 가서 해당 가상메모리에 대한 물리주소가 있는지 확인한다. 
   1. 물리주소가 TLB에 있으면 그 데이터(물리 주소)를 바로 메모리에 갖고 온 후, 바로 CPU에서 처리를 하면 된다.
   2. 만약 물리주소를 모른다면, CR3 레지스터를 갖고 page table에 접근한다. 그리고 이 때, valid-invalid bit를 보고 해당 물리주소가 메모리에 저장이 되어있는지, 안 되어있는지 확인한다.
      1. 만약에 물리주소에 저장이 되어있다고 하면, MMU가 해당 물리주소(해당 페이지의 데이터)를 갖고 와서 다시 CPU에 보내면 끝난다.
      2. 그런데 만약 invalid 상태라면 이 때는 page fault interrupt가 운영체제에 던져지게 된다. 운영체제는 page fault interrupt를 처리하기 위해서 해당 페이지를 저장 공간(ex. 실행 파일)에서 갖고 와서 그 해당 데이터를 메모리에 올려준다. 그 다음에 page table을 업데이트하고, CPU에게 재실행을 요청한다. 그러면 CPU는 위 그림의 7번처럼 가상주소를 다시 요청하고 MMU를 타서 해당 메모리에 있는 데이터를 CPU가 가져갈 수 있게 된다.

그 외로, page fault interrupt가 나면 원래는 IDT(Interrupt Discrete Table)에 가서 인터럽트 번호에 대한 OS 안에 있는 함수를 호출하고 4번과 같은 작업을 한다.

 

그런데 TLB를 바로 사용하는 것보다 당연히 페이지 폴트는 오래 걸리게 된다. 따라서 아래의 문제점들을 한 번 생각해볼 필요가 있다.

• 페이지 폴트가 자주 일어나면?
  • 실행되기 전에 해당 페이지를 물리 메모리에 올려야 함 → 시간이 오래 걸림
• 페이지 폴트가 안 일어나게 하려면?
  • 향후 실행/참조될 코드/데이터를 미리 물리 메모리에 적정하게 올리면 됨 → 앞으로 있을 일(어떤 게 참조될 지)을 예측해야 하는 것이므로 거의 불가한 신의 영역

---

페이지 교체 정책(page replacement policy)

• 운영체제가 특정 페이지를 물리 메모리에 올리려 하는데, 물리 메모리가 다 차있다면?
  • 기존 페이지 중 하나를 물리 메모리에서 저장매체로 내리고(저장)
  • 새로운 페이지를 해당 물리 메모리 공간에 올린다.

→ 어떤 페이지를 물리 메모리에서, 저장 매체로 내릴 것인가?

→ Page Replacement(Swapping) Algorithm

페이지 교체 알고리즘

FIFO(First In First Out) Page Replacement Algorithm

• 가장 먼저 들어온 페이지를 내리자

OPT(OPTimal Replacement) Algorithm

• 최적 페이지 교체 알고리즘
• 앞으로 가장 오랫동안 사용하지 않을 페이지를 내리자 → 그걸 어떻게 알까?;; 신의 영역이다. 일반 OS에서는 구현 불가.

LRU(Least Recently Used) Page Replacement Algorithm

• 가장 오래 전에 사용된 페이지를 교체
• OPT 교체 알고리즘이 구현 불가하므로, 과거 기록을 기반으로 시도

LFU(Least Frequently Used) Page Replacement Algorithm

• 가장 적게 사용된 페이지를 내린다

NUR(Not Used Recently) Page Replacement Algorithm

• LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 교체하는 기법
• 각 페이지마다 참조 비트(R), 수정 비트(M)을 둠 (R,M)
  • (0,0), (0,1), (1,0), (1,1) 순으로 페이지 교체 (0:False, 1:True)

 

cf. 메모리 지역성(Locality)

#include <stdio.h>
int main()
{
	int i = 0;
	int j = 0;
	for (i=1; i <= 9; i++)
	{
		for (j=1; j <= 9; j++)  // 이 시점에서 보면 이 부분을 굉장히 많이 실행을 할 것
		{
			printf("%d x %d = %d₩n",i,j,(i*j));
		}
		printf("₩n");
	}
	return 0;
}

x: 실행시간, y: 실제 코드의 주소들

실행 시간에 따라서 그림에 표시한 지역에서 위의 코드처럼 막 for문을 돌면서 실행되고 있는 것이다. 그래서 이런 메모리는 그 코드의 주변을 실행할 가능성이 가장 높다.

1번주소를 실행했다면, 2번이나 3번 같은 그 주변을 실행할 가능성이 가장 높다는 것이다.

따라서 일반적으로 LRU 같은 알고리즘이 OPT 교체 알고리즘과 유사한 성능을 낼 수 있다고 보고 있다.

 

스레싱(Thrashing)

• 프로그램 여러 개 띄우면 프로그램 전환 시 컴퓨터가 버벅거리는 원인
• 반복적으로 페이지 폴트가 발생해서 과도하게 페이지 교체 작업이 일어나 실제로는 아무 일도 하지 못하는 상황 

  

  돈 벌어서 램 사야하는 이유

프로그램을 많이 띄워놓으면 어느 순간부터 급격히 떨어질 수 있는데, page fault가 일어나고 page swap 일어나면서 페이지 교체 작업이 수시로 빈출하면서 실제 CPU 동작은 못하고 오로지 page fault, page swap 처리만 하게 되는 것이다.

 

결론 : 프로그램 많이 띄워놓지 말고 정 필요하면 메모리를 사서 램 늘리자.

---

References

fastcampus 컴퓨터공학 올인원 패키지

쉽게 배우는 운영체제