[OS] Ep.10 Memory Management (1)

서론

범용 컴퓨터 시스템의 목적

• **CPU의 활용률(Utilization)을 극대화

• 사용자에게 빠른 응답을 제공
  보다 많은 Program을 Memory에 올려서 실행 (Multi-Programming)
  여러 Program을 동시에 실행시키기 위한 Scheduling 기법 등장

Memory 관리의 필요성 등장

• 여러 Program이 동시에 Memory에 적재되어 실행되면서, Memory를 공유할 필요가 생김

• Computer의 Memory는 한정된 자원
  실행하는 Program이 많아지면 Memory 요구량이 증가

주소 공간 (Address Space)

정의 (Address Sapce)

• Process에서 참조할 수 있는 주소들의 범위(집합)

• Processdhk 1:1 관계

• 사용자 Thread는 주소 공간을 공유함

주소 공간의 크기

• **CPU의 주소 버스(Address Bus)의 크기에 의존

• 주소 버스가 32bit인 System에서 주소 공간의 크기
  $2^{32}$개의 서로 다른 주소에 대한 식별자를 만들 수 있으므로, 0부터 ($2^{32} - 1$)까지의 주소 범위를 Addressing 할 수 있음

• 32bit 주소 버스를 가진 System이 주소 1개당 1Byte의 Memory를 접근할 수 있다면, 이 System이 Address할 수 있는 주소공간의 크기는?
  $2^{32} * 1Byte = 4GB$

물리 주소와 가상 주고 (PA and VA)

물리 주소 (Physical Address)

• 컴퓨터의 메인 메모리를 접근할 때 사용되는 주소

• 기억 장치의 주소 레지스터에 적재되는 주소

가상 주소 (Logical Address or Virtual Address)

• Process의 관점에서 사용하는 주소

• CPU 관점의 주소는 물리 주소도, 가상 주소도 될 수 있음
  어느 Memory Model을 사용하느냐에 따라 잘라짐

• Logical이기 때문에 주소 공간을 의미 있는 단위로 나누어 사용하지 않음

초창기 컴퓨터의 주소 관리

물리 주소를 Compile Time에 생성

• Compiler는 Process가 물리 Memory에서 실행되는 주소를 Compile Time에 알아서 절대 코드를 생성한다.

• 시작 주소의 위치가 바뀔 경우에는 다시 Compile을 해야 한다.

다양한 Program이 실행됨에 따라 Compile Time에 물리 주소를 정하기가 어려워짐

• 1개의 Program이 실행될 경우 문제가 없음
• Multiprogramming의 경우, Compile Time 시에 결정된 주소는 다른 Program과 동시에 Memory에 Load하기 어려움
  => 가상 주소를 생성하기 시작함

Compile 및 Link Time에서의 주소 결정

Compile Time

• Compiler가 Symbol Table을 만들고 주소는 Symbol Table Relative한 주소로 이루어짐

• **Compile된 Object파일은 주소 0부터 시작함 (Relocatable)

Link Time

• Object 파일들과 System에서 제공하는 Library들을 묶어서 Symbol Table에 의존적이지 않은 주소를 만들어 냄

• Link의 결과로 하나의 Executable파일이 만들어진 주소는 0부터 시작함 (아직도 논리주소로...)

• Executable은 하나의 주소 공간으로 0부터 시작함
  

Load Time

• Program의 실행을 위해 Loader는 Executable을 Memory로 Load한다.

• 주소 공간 전체가 Memory에 올라간다면, Load 시에 물리 주소에 대한 Binding이 일어난다.
  Program은 Relocatable 주소로 되어 있기 때문에 Base Register를 통해서 물리 주소로 바꾸어 실행하게 된다.

• 만일 Program의 시작 주소를 바꾸려면, 다시 Load를 해야한다.

Execution Time

• Process가 실행 될 때 물리 주소가 바뀌는 경우, 물리 주소에 대한 Binding은 Process가 실행될 때 일어난다.

• 이러한 형태의 주소 결정 방법을 사용하기 위해서 MMU와 같은 특별한 H/W가 필요하게 된다.

• 대부분 General Purpose 운영체제에서는 이 방식을 사용한다

CPU에서 사용하는 주소에 따른 변환 방법

CPU에서 Physical Relative Address를 사용하는 경우

• Program 내 Instruction들의 주소를 시작 주소(Base Address)로 부터의 상대적인 Offset으로 표현하는 방법

• 시작 주소가 결정되면 시작 주소(Base Address) + 상대 주소의 합으로 절대 주소를 생성할 수 있다.
  

CPU에서 Virtual Address를 사용하는 경우

Translation의 속도가 중요한 요소가 된다.

Memory Management Unit (MMU)

Virtual Address와 Physical Address 간의 변환을 수행하는 Hardware 장치

가상 메모리

정의

• Memory로서 실제 존재하지는 않지만, 사용자에게 Memory로서의 역할을 하는 Memory(Virtual)

Basic Idea

• Process가 수행 되기 위해서 Program의 모든 부분이 실제 메모리 (Physical Memory)에 있을 필요는 없다
  현재 실행되고 있는 Code 부분만이 실제 Memory에 있으면 Process는 실행이 가능

가상 메모리 구현

가상 메모리 - Address Mapping Table

Paging

Paging

주소 공간을 동일한 크기인 Page로 나누어 관리

• 보통 1 Page의 크기는 4KB로 나누어 사용

• 프레임(Frame)
  물리 Memory를 고정된 크기로 나누었을 때, 하나의 Block

• 페이지(Page)
  가상 Memory를 고정된 크기로 나누었을 때, 하나의 Block

각각의 프레임 크기와 페이지 크기는 같다.
(프레임과 페이지는 물리 메모리, 가상 메모리에서 부르는 용어의 차이)

Page가 하나의 Frame을 할당 받으면, 물리 Memory에 위치하게 된다

• Frame을 할당 받지 못한 Page들은 외부 저장장치(Backing Storage)에 저장된다
  Backing Storage도 Page, Frame과 같은 크기로 나누어져 있다.

Paging - Page번호와 Offset

CPU가 관리하는 모든 주소는 두 부분으로 나뉜다

• Page 번호
  각 Process가 가진 Page 각각에 부여된 번호
  ex) 1번 Process는 0부터 63까지의 Page를 가지고 있음

• Page 주소
  각 Page의 내부 주소를 가리킴
  ex) 1번 Process 12번 Page의 34번째 Data

Page Table

페이지 테이블(Page Table)

• 각 Process의 Page 정보를 저장함
  Process마다 하나의 Page Table을 가짐

• index: Page 번호

• 내용: 해당 Page에 할당된 물리 Memory(Frame)의 시작 주소
  이 시작 주소와 Page 주소를 결합하여 원하는 Data가 있는 물리 Memory 주소를 알 수 있음

Page Table의 구현

• Page Table은 물리 Memory에 위치함
  (PTBR로 접근)

• Page Table 기준 레지스터(PTBR: Page Table Base Register)가 물리 Memory 내의 Page Table을 가리킴

• Page Table 길이 레지스터(PTLR: Page Table Length Register)가 Page Table의 Size를 나타냄

page table의 인덱스는 page 번호
page table의 내용은 물리 Memory(Frame)의 시작 주소

Page Table - Page Table을 이용한 주소 변환

Page Table Entry (PTE)

PTE란?

• Page Table의 Record

PTE의 각 필드 내용

• Page Base Address
  해당 Page에 할당된 Frame의 시작 주소

• Flag Bits

  • Accessed Bit
    page에 대한 접근이 있었는지
  • Dirty Bit
    Page 내용의 변경이 있었는지
  • Present Bit
    현재 Page에 할당된 Frame이 있는지
  • Read/Write Bit
    읽기/쓰기에 대한 권한 표시

Translation Look-aside Buffers (TLB)

Paging방법에서는 Data로의 접근이 항상 두 번의 Memory 접근을 거쳐야 함

• Page Table에 한 번, 물리 Memory 내의 Data에 한 번
• Memory 접근 속도를 크게 떨어뜨림

해결 방법 - TLB in MMU

• Page Table을 이용해 변환된 주소를 TLB에 저장해 둠

• 다음 접근 시에는 TLB에 저장된 값을 이용하여 빠르게 변환된 주소를 얻을 수 있음
  TLB는 Register(CPU내에 존재)이기 때문에, 빠른 수행이 가능함

• TLB Hit Ratio
  TLB 내에서 원하는 주소를 찾을 수 있는 확률 (높을수록 Memory 접근 속도를 향상시킬 수 있음)
  
  위의 사진과 달리 Page Table에 접근하기 전, TLB에 먼저 접근하는 것을 볼 수 있다

다양한 Paging Table

Multilevel Page Table

다단계(Multi-level) Page Table의 필요성

• System의 발전에 따라 가상 주소 공간도 매우 큰 용량을 요구하게 됨
• 그로 인해 Page Table의 크기가 커지고, 그 차지하는 공간에 의해 Paging이 잘 이루어질 수 없게 되고 있다

32bit 가상 주소 공간을 가지는 System에서 Page의 크기가 4KB이면, 페이지에 접근하기 위한 Bit의 수는 20bit(= 1MB)이고, (12bit는 page offset) PTE는 보통 4B의 크기를 가짐.
=> page table은 4MB의 크기를 가지게 됨.

프로세스마다 페이지를 소유하고 있기 때문에 (+ 페이지는 물리 메모리에 존재하기 때문에) 100개의 프로세스가 떠있다면, 물리 메모리에 페이지 테이블을 위해서 400MB가 할당되어야 함

2 Level Page Table 구현

구현 방법

• Outer Page Table을 하나 더 두어, Page Table들을 가리키도록 한다.
  ex) 앞 선 예시에서, 20Bit를 차지하는 Page번호를 다시 아래와 같이 나눈다
• 10Bit Page 번호
• 10Bit Page 주소
  

도식

2 Level Page Table의 Table walk

---

Page Table Level과 Memory 성능

하나의 주소공간을 Mapping하는 Page Table이 차지하는 Memory

• 2 Level인 경우와 1 Level인 경우 Page Table 전체가 차지하는 Memory
  

Page Table의 Level이 많은 경우 장점

• Level이 3인 경우 생각해보기
• 어떨 때 Page Table이 차지하는 Memory가 줄어들까?
  

단점

• Table Walk에 걸리는 시간이 증가함

Inverted Page Table - 동기

Multilevel Page Table에서와 같은 Page Table의 용량 증가 문제를 해결하기 위한 다른 방법

• 64bit 주소 공간의 System에서 Multilevel Paging을 위한 정보의 크기는 32bit에 비해 현격하게 증가됨

해결 방법

• 아무리 가상 Memory의 공간이 크더라도, 물리 Memory의 크기에는 한계가 있음
• 모든 물리 Memory는 가상 Memory의 Page에 Mapping될 확률이 높음

Inverted Page Table - Think Different

기존 방식은 Page#을 이용하여 Frame#을 검색

Inverted 방식은 CPU에서 참조하는 Address와 PID조합으로 Page ID를 만들어 Page Table 내에서 Page ID를 검색함

• Page ID를 발견하면, 해당 Frame#을 Logical Address 공간으로 Mapping

Inverted Page Table - 구현

System 전체에 하나의 Page Table만 둔다

• Page Table Index : Frame의 번호

• Page Table 내용 : Process 번호(PID)와 Page 번호, Page 주소를 함께 넣음

Page Table은 보다 적은 용량을 차지하지만, Table을 검색하는데 시간이 오래 걸린다

-> Multilevel로도 페이지 테이블의 용량을 줄일 수 있기에... 그렇게 많이 사용하는 방식은 아닌듯

도식

Demand Paging

Demand Paging이란?

• Process의 실행을 위한 모든 Page를 Memory에 올리지 않고, 필요한 Page의 요청이 발생할 때 메모리에 올리는 Paging 기법

Paging service를 통해서 한 Process에 필요한 Page를 Memory와 Secodary Storage 간에 이동시킴

Valid and Invalid PAge

Valid하다는 것은 page가 Secondary Storage가 아닌, 메모리에 올라와 있다는 것을 의미함

장점

• **실행을 위한 물리 Memory 구성의 시간이 줄어든다

• Process의 전체 이미지를 Memory에 올리지 않기 때문에, 실제 필요한 전체 물리 Memory의 양을 줄일 수 있다

단점

• 참조하려는 Page가 Invalid한 경우
  Secondary Storage에 갔다와야하기에 Page Fault 발생

Page Fault

Process가 Page를 참조하였을 때 해당 Page가 할당 받은 Frame이 없는 경우

• Page Fault가 발생하여 Page Fault Handler 수행

Page Fault Handler가 수행하는 내용

• 새로운 Frame을 할당 받음

• Backing Storage에서 Page의 내용을 다시 Frame에 불러들인다

• Page Table을 재구성한다

• Process의 작업을 재시작한다
  

Working Set