[ OS ] 15. 메모리 관리 전략 - 단순 Paging

단순 Paging

프로세스를 연속 메모리 할당(Contiguous Memory Allocation) 을 하게 되면, 외부 단편화(External Framentation)이 발생하게 되고, 값 비싼 메모리 자원의 1/3 까지 손실될 수 있는 현상을 타파하고자 나온것이 Paging(페이징)이다.

하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없앤다.

외부단편화와 압축(Compaction) 작업을 해소하기 위해 생긴 방법론으로, 물리 메모리(Physical Memory)는 Frame이라는 고정 크기로 분리되어 있고, 논리 메모리(프로세스가 점유하는)(Logical Memory)는 Page라 불리는 고정 크기의 블록으로 분리된다.

페이징 기법을 사용함으로써 논리 메모리는 물리 메모리에 저장될 때, 연속되어 저장할 필요가 없고 물리 메모리의 남은 프레임에 적절히 배치된다.

페이지의 크기와 논리적 주소 구성

# Logical Address (논리적 주소) : CPU에 의해 생성되는 주소체계
# Physical Address(물리적 주소) : RAM에 실질적으로 로드되는 주소

• page number(p)
  • Page Table의 Index로 사용되며, 각 page별 Physical Memory에서 시작 주소를 포함한다.
• page size
  • 페이지 크기는 대게 512bytes에서 8192bytes까지 될 수 있는데, 4096bytes가 보통 전형적인 값이다.
  • 4096bytes(4KB)면 4 * 1024로 2의 12승이므로 페이지 하나당 12bits를 차지한다
• page offsert(d)
  • Base Address와 합쳐져서 Physical Memory Address로 변환된다.
  • 하나의 페이지가 4KB일 때 page0도 4KB가 된다. 결국 page0은 주소로 따지면 0번지에서 2¹²까지의 값의 번지까지 있는것이다.
  • 그렇게 해서 page번호 말고 page 내의 번호를 offset이라고 한다.
  • page0의 0번 오프셋이라 하면 2¹² 위치의 논리주소가 되는 것이고,
  • page1의 0번 오프셋이라 하면 2¹³번지에 위치한 주소를 가리키게 된다.

- 하나의 프로세스가 가질 수 있는 최대 크기?

만약 내가 사용하고 있는 운영체제가 32비트 프로세서이고, 페이지 크기가 4KB라고 가정한다면

한 번에 CPU가 2의 20승 개수의 페이지 번호를 구분할 수 있게 된다.

2²⁰개 이상의 페이지일 경우 32bits를 넘어가기 때문에 표현할 수 없다.

즉, 32비트 프로세서일 때 하나의 프로세스가 가질 수 있는 logical address 전체 크기는 2³² , 페이지의 최대 개수는 2²⁰이 된다.

32bit 프로세서에서는 프로세스 하나의 크기가 4기가(2³²)를 넘으면 안된다는 것!
근데 4기가짜리 프로세스는 사실 없지만, 32bit processor는 논리적으로 4기가 까지가 가능하다는 것이다.

logical address -> physical address

• 위 그림은 논리적 주소를 물리적 주소로 변환하는 Flow를 나타낸다.
• p는 페이지 번호(page number), f는 프레임 번호(frame number), d는 페이지 오프셋(page offset)이다.
• 논리 메모리 앞 20bits에서 페이지 번호를 페이지테이블에서 검색하면 프레임번호가 나온다.
• page의 크기하고 frame의 크기는 똑같기 때문에 offset은 똑같이 가면 된다.
• 즉, 논리메모리에서 p페이지의 d오프셋 위치는 f프레임의 d에 적재되어 있다는 것이다
• Process의 PCB 내에 Page Table이 존재해야 한다.
• Virutal Address를 Page Size로 나누어 Page Number를 구하고, 나머지 값은 offset이 된다.
• Physical Memory의 주소를 구하기 위해서 Page Number를 통해서 Page Table을 뒤져본 후 Frame Number를 찾아낸다. 찾아낸 Frame Number를 Frame Size크기만큼 곱하게 되면 이는 Physical Memory의 시작주소가 되며, 여기에 Virtual Address를 Page Size로 나눈 나머지인 offset의 값을 더해주면 Physical Memory를 구할 수 있다.

1. Virtual Address / Page Size = Page Number
2. Virtual Address % Page Size = offset
3. Physical Address = Frame number * Frame Size + offset

예를들어 물리주소인 (0xf

~

)를 쓸 필요가 없고 2(p)번 페이지에 23(d)번 주소를 access하자는 것이다.

이게 바로 logical address가 되는 것이다.

위 그림은 페이지 테이블의 구조를 나타낸다.

page0은 frame1에 있고, page1은 frame4, page2는 frame3, page3은 frame7에 있다고 알려준다.

결국 페이지 테이블은 배열과 같다.

배열처럼, 인덱스가 페이지 번호를 가르키고, 그 배열에 담고 있는 숫자가 매핑할 프레임 번호인 것이다.

각 운영체제는 페이지 테이블을 저장하기 위한 고유의 방법을 가지고 있다. 디스패처가 어떤 프로세스를 시작 시킬 때 이 레지스터들을 다시 적재하면 페이지 테이블도 함께 사용 할 수 있게 된다.

페이지 테이블은 레지스터의 집합으로 구현되기도 한다. 메모리의 모든 액세스는 이 페이징 맵을 통해야 하므로 매핑의 효율은 매우 중요하다. 디스패처는 이들 레지스터를 채우며 운영체제가 이를 담당한다.

페이지 테이블에 레지스터를 사용하는 것은 페이지 테이블이 작은 경우 적합하다. 하지만 대부분의 컴퓨터들은 수백만 항목에 이를 만큼 매우 크다. 이러한 컴퓨터의 페이지 테이블을 구현하기 위해서 빠른 레지스터를 사용하는 것은 부적절하다.(레지스터 비용이 비싸기 때문이다.)

그래서 대부분의 컴퓨터는 페이지 테이블을 주 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR, Page-Table Base Register)로 하여금 페이지 테이블을 가리키도록 한다. 다른 페이지 테이블을 사용하려면 단지 이 레지스터만 변화시키면 되기 때문에 문맥 교환시간을 줄일 수 있다.

PTBR의 문제점은 메모리의 접근 시간이다. 원하는 주소에 접근하기 위해서는 페이지 테이블에 접근해야 하는데 요청한 번지에 접근하기 위해서는 [프레임 번호 + 페이지 변위를 통한 실제 주소 의 접근]으로 2번의 접근이 필요하기 때문이다. 이런 지연이 반복되면 너무 느리기 때문에 스와핑 방법이 유리 할 수도 있다.

PTBR의 메모리 속도 문제를 해결하기 위해 TLB(Translation Look-aside Buffer)이라 불리는 캐시가 사용된다. TLB는 매우 빠른 연관 메모리(associative memory)로 구성된다. TLB 내의 각 항목은 키(key)와 값(value)의 두 부분으로 구성 된다.

TLB는 비싸므로 페이지 테이블의 일부분 밖에 가지고 있을 수 없다. CPU에 의해 논리 주소가 생성되면 그 페이지 번호를 TLB에 제시한다.

사용하려는 페이지를 찾으면 그 프레임 번호를 알 수 있으며 메모리로 접근하는데 사용할 수 있다. 페이지 번호가 TLB에서 발견 되는 비율을 적중률(hit ratio)라 부른다. 90%의 적중률은 TLB에서 원하는 페이지 번호를 발견할 횟수가 90%라는 것을 의미한다.

Memory Protection

그럼 페이지화된 환경에서의 메모리 보호는 어떻게 이루어지는가?

각 페이지에 붙은 보호 비트(protectioni bit)에 의해 구현된다.

이 비트들은 보통 페이지 테이블에 속해 있고, 메모리에 대한 모든 접근은 페이지 테이블을 거치므로 이 때 주소의 매핑과 함께 쓰기가 허용되는지 검사도 할 수 있다.

또한, 페이지 테이블의 각 항목에는 valid한지 invalid한지 판별하는 비트가 더 존재한다. 이 비트가 유효로 설정되면, 관련된 페이지가 합법적인 페이지이며 무효로 판전된다면 그 프로세스는 논리 주소 공간에 속하지 않는다.

이 비트를 이용해 페이지의 접근을 제한할 수 있다.

대부분의 프로세스들은 일정한 시각에 일정 부분의 주소 범위만 사용한다. 이런 경우 모든 페이지에 페이지 테이블 항목을 배정하는 것은 낭비이다. 일부 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(PTLR, Page Table Length Register)라는 레지스터를 제공 한다.

페이지는 공유를 쉽게 할 수 있다. 여러 프로세스들이 동시에 같은 코드를 수행 할 수 있으며 코드 부분을 공유하더라도 프로세스들은 레지스터의 복사 값과 프로세스가 저장소는 따로 가지고 있다. 물론 서로 프로세스의 자료는 다르다. 공유가 가능한 프로그램으로는 컴파일러, 시스템, 실시간 라이브러리, 데이터베이스시스템 등이 있다.

공유를 위해서는 반드시 Reentrance Code(코드 재진입)이 가능해야 하며 공유 코드의 읽기 전용 특징만으로는 코드의 정확성을 보장할 수 없기 때문에 운영체제에서 이를 보호해 주어야 한다.

# Reentrant Code
non-self modifying code
실행 중에 자기코드 변경이 없는 코드

• 위 그림은 비어있는 Frame에 대한 List에 대해서 page를 할당하는 과정이다.
• 그말은 즉, OS는 비어있는 Frame에 대한 정보를 가지고 있다.
• Frame Table
  • OS마다 Struct Type으로 Frame에 대한 정보를 가지고 있는 테이블이 존재한다.
  • 어떤 Frame이 위치하고 있는지, 존재하는 Total Frame의 개수 등의 정보를 가지고 있다.
• A copy of Page Table
  • OS는 프로세스의 PCB 내에 Struct Type으로 Page Table을 복사하고 유지한다.
  • 모든 Logical Address는 Physical Address로 변환되기 위해서 Page Table과 Mapping되어야 한다.
  • Paging은 Context swtich Time을 증가시킬 수 있다.

Internal Fragmentation

내부 단편화

메모리를 할당할 때, 프로세스가 필요한 양보다 더 큰 메모리가 할당되어서 프로세스에서 사용하는 공간이 낭비되는 현상이다.

Page size가 2048 bytes라고 가정하고, 프로세스의 size가 72,76 bytes라면, 35개의 page + 1086의 bytes가 사용되는 것이다. 이 말은 즉, 36개의 프레임이 사용되고 있지만 962 bytes가 내부 단편화로 낭비되고 있다는 것이다.

따라서 내부 단편화를 줄이기 위해서 Page의 Size가 작을수록 좋지만, 너무 작아져 버리면 Page Table의 Entry가 커지는 등 Overhead가 많이 발생하기 때문에 적당한 Size의 Page를 설정하는 것이 필요하다.

때문에 요즘의 Page는 4KB 또는 8KB의 값을 갖는것이 일반적이다.

Swapping

Swapping이란 메모리의 관리를 위해 사용되는 기법으로, 표준 Swapping 방식으로는 round-robin과 같은 스케쥴링의 다중 프로그래밍 환경에서 CPU 할당 시간이 끝난 프로세스의 메모리를 보조 기억장치(하드 디스크)로 내보내고 다른 프로세스의 메모리를 불러들이는 것이다.

위에서 보았듯, 물리적 주소공간과 논리적 주소공간을 분리 시켜놓으니까 내가 만든 프로그램이 물리적 주소공간보다 훨씬 커져도 상관이 없다.

어차피 페이지를 쪼갰으니까!

CPU의 명령어와 그게 access하는 데이터는 메모리에 상주해야 하는데, 메인 메모리(RAM)에 불러올 때 swap-in이라 하고, 필요없으면 보조 기억장치로 보내는 것을 swap-out이라 한다. 이 과정이 Swapping이다.

전체 프로세스를 Swapping하는 것은 부담이 크지만, Paging 단위로 하면 부담이 적다.

이렇게 되면 Physical Memory와 Logical Memory의 분리는 발생할 수 있지만, 아주 작은 단위의 스와핑 까지 가능하기 때문에 오늘날 스와핑이라고 하면, Swapping with Paging이라고 한다. 따라서 swap-out/swap-in 보다 page-in/page-out이라고 할 수도 있다.

이러한 페이징 기법은 뒤에 배울 Virtual Memory에서 Demand Paging을 위한 기반 개념이 된다.