[OS] 7. 메모리 관리

[OS] 7. 메모리 관리

2022. 5. 21. 14:09ㆍMajor`/운영체제

Memory

컴퓨터 시스템에서 메모리는 굉장히 중요한 하드웨어이다.

디스크에 존재하는 프로그램은 OS에 의해서 메인 메모리로 올라가게 되고, 스케줄링에 의해서 CPU를 할당받고 실행이 된다

이 때 CPU는 "해당 프로세스의 주소"를 통해서 프로세스에 접근할 수 있다

CPU가 직접 Access 가능한 것은 메인 메모리 & CPU 내부 레지스터이다

Logical Address

Logical Address란 "CPU가 보는 프로세스의 주소"이다

프로세스마다 독립적으로 보유하는 주소 공간이고 당연히 프로세스 입장에서는 0번지부터 시작된다

Physical Address

Physical Address는 "프로세스가 실제 메인 메모리에 올라가는 위치"를 의미한다

따라서 CPU가 프로세스에 access하려면 CPU가 보는 프로세스의 주소인 Logical Address가 아니라 프로세스가 실제로 메인 메모리에 어디 위치한지에 대한 Physical Address로 access해야 한다

>> Logical Address → Physical Address로 Mapping하는 과정이 반드시 필요하다

※ Symbolic Address
개발자가 실제 개발을 할 때 배열을 사용한다면 "int [] array = new int[10]"처럼 작성을 할 것이다.
이 때 array라는 이름을 통해서 40byte의 주소공간에 access한다

따라서 실제 메모리의 주소로 주소 공간을 표현하지는 않는다. 실제 메모리 주소로 적는 것은 말이 안되는 일이다

따라서 프로그래밍할때는 직접 메모리 주소에 관여하지 않고, 변수로 흐름을 제어한다

>> array같은 주소 공간을 대변하는 변수들을 Symbolic Address라고 한다

이 Symbolic Address는 "컴파일"을 통해서 Logical Address로 변환이 된다

Address Binding

Address Binding이란 Logical Address → Physical Address로 변환하는 것을 말한다

Address Binding은 언제 변환되느냐에 따라 3가지로 나뉘게 된다

1. 작성한 프로그램(소스 코드)을 "컴파일"하게 되면 Object Module로 변환이 된다 >> Compile Time
2. 변환된 Object Module과 이미 존재하는 Object Modules(라이브러리)들을 "Linking"을 통해서 실제 실행 가능한 프로그램(Load Module)으로 변환 시켜준다
3. 실행 가능한 프로그램(Load Module)은 "Loader"에 의해서 실제 메인 메모리에 적재가 된다

1. Compile Time Binding

Compile Time Binding(CTB)는 Address Binding이 Compile Time에 일어난다

근데 아까 위에서 Symbolic Address를 컴파일하면 Logical Address가 된다고 하였다

∴ 사실상 Logical Address와 Physical Address는 동일하다고 볼 수 있다

컴파일러가 컴파일을 수행해서 Symbolic Address를 Logical Address로 변환했는데 변환된 Logical Address가 Physical Address이므로 컴파일러는 "Absolute Code"를 생성했다고 볼 수 있다

Logical Address에 대한 변경을 하지도 않았는데 이미 Physical Address로 결정되었기 때문에

이렇게 Compile Time에 컴파일러가 프로그램의 변수/함수들이 실제 메모리 어디에 저장될지 결정 가능한 이유는 "컴파일러는 이 소스코드가 컴파일되어서 최종적으로 만들어진 Binary Code가 실행될 때 메모리 어디에 저장된다는 사실을 이미 알고있기 때문이다"

대표적인 CTB 시스템은 과거 "MS-DOS"이다

MS-DOS의 경우 "Single User OS"이므로 프로그램이 실행되면 정확히 메모리 어디에 프로그램이 적재되어야 하는지 고정이 되어있다

Single User = Single Tasking = 메모리에 프로그램 하나만 적재

따라서 각각의 변수/함수가 메모리 어디에 위치할지 컴파일러가 알 수 밖에 없다

요즘 시스템은 MultiProgramming이므로 CTB를 사용하지 않는다

※ 프로그램을 다른 메인 메모리 영역에 적재하고 싶습니다

컴파일을 다시 하면 된다. 프로그램을 컴파일하면 컴파일러는 Absolute Code를 생성하고 그 즉시 주소가 결정되기 때문에 다른 주소에 올리고 싶으면 컴파일을 다시 해야한다

2. Load Time Binding

Load Time Binding(LTB)의 경우 컴파일이 되고 나서, Loader에 의해서 프로그램이 메인 메모리에 Load될 때 미리 Logical Address를 전부 Physical Address로 변환하고 올린다

∴ 사실상 Logical Address와 Physical Address는 동일하다고 볼 수 있다

단, CTB와 다른 점은 CTB는 컴파일러가 Absolute Code를 생성했기 때문에 그 즉시 Physical Address로 fix되지만, LTB의 경우 컴파일이 되면 일단 Logical Address이고 해당 프로그램이 Loader에 의해서 실제 메인 메모리에 load될 때 Physical Address로 변환되기 때문에 "컴파일러는 Relocatable Code를 생성했다"라고 볼 수 있다

Logical Address와 Physical Address가 동일하다고 볼 수 있는 근거는 실제 프로그램이 메인 메모리에 적재가 되어서 CPU가 해당 프로그램에 access할때는 이미 프로그램의 Logical Address가 Load될 때 전부 Physical Address로 변환이 된 채로 메인 메모리에 적재되었기 때문에 CPU가 access한 주소는 Physical Address이다.
따라서 Logical Address와 Physical Address가 동일하다고 볼 수 있다

※ CTB & LTB의 공통점

둘다 어쨋든 메인 메모리에 올라가게 되면 CPU가 보는 주소는 사실상 Physical Address라고 볼 수 있기 때문에 만약 프로그램이 Swap Out되었다가 다시 Swap In이 되는 경우 "반드시 원래 있었던 영역에 적재가 되어야 한다"

만약 다른곳에 적재가 된다면 CPU가 본인의 프로세스 영역이 아닌 다른 프로세스의 영역을 침범하기 때문에 trap이 발생하게 된다

3. Run Time Binding (Execution Time Binding)

Run Time Binding(RTB)의 경우 Binding을 Run Time까지 미루는 것이다

일단 컴파일 된 프로그램은 Loader에 의해서 메모리에 적재가 된다. 따라서 여전히 프로그램의 Address는 Lobical Address로 이루어졌을 것이다

그리고 기계어를 실행할 때마다 Logical Address를 Physical Address로 변환해준다

MMU라는 하드웨어의 지원을 통해서 Binding을 한다

∴ Logical Address와 Physical Address는 다르다고 볼 수 있다

메인 메모리에 적재된 시점에 프로그램은 여전히 Logical Address를 가지고 있으니까 CPU는 프로그램에 access할 때 Logical Address로 access를 한다. 그리고 MMU에 의해서 Binding이 되어서 실제 메인 메모리 위치에 접근한다

LTB와 마찬가지로 RTB에서 컴파일러가 생성한 코드는 "Relocatable Code"이다

MMU : Memory Management Unit

Logical Address를 Physical Address로 Mapping해주는 H/W Device이다

MMU는 "Base(Relocation) Register & Limit Register"를 통해서 Mapping을 수행한다

RTB에서 user process는 절대로 Physical Address를 알 수 없다. 왜냐하면 Logical Address만 알고있고 Binding은 MMU에 의해서 이루어지기 때문이다

현재 CPU는 Process P1의 Logical Address : 346에 access하려고 한다

시스템은 Run Time Binding을 지원하고 있기 때문에 MMU의 도움을 받아서 346이라는 Logical Address를 Physical Address로 Mapping해야 한다

1. access하려는 주소가 Limit Register의 값을 넘는지 확인

Limit Register의 값은 해당 프로세스의 크기라고 볼 수 있다

따라서 access하려는 주소가 Limit Register의 값보다 크게되면 다른 프로세스의 영역을 침범하는 것이 되기 때문에 trap(Addressing Error)가 발생하게 된다

2. Logical Address + "Base Register Value" = Physical Address

Base Register의 값은 실제 메인 메모리에서 해당 프로세스가 시작하는 위치를 저장하고 있다

Base Register 14000이라는 값은 P1이 메인 메모리 14000번지부터 적재가 되었다는 의미이고 Limit Register가 3000이니까 [14000, 17000]에 P1이 있다는 의미이다

따라서 Logical Address : 346에 Base Register 14000을 더한 "14346"이 현재 CPU가 access하려는 P1 기계어의 실제 메인 메모리 위치이다

Dynamic Loading

프로그램 전체를 한번에 메인 메모리에 올리는게 아니라 해당되는 루틴이 불려질 때 메모리에 로딩하는 방법이다.

이러한 방법을 통해서 "Memory Utilization"이 향상된다

이 방법은 특히 "가끔 사용되는 코드인데 양이 굉장히 많은 코드"의 경우 유용한 방법이다

"Error Handling Code"는 빈번히 call되지 않고 가끔 call이 되지만 코드의 양이 방대하다

따라서 이런 코드를 메인 메모리에 계속 올려둘 필요는 없다

Dynamic Loading은 라이브러리를 통해서 프로그램 자체에서 개발자가 직접 구현이 가능하다

OS의 서포트를 통해서 메모리에 올라가고 내려가고 하는 것은 "Paging"이라고 한다

Overlays

Overlays는 Dynamic Loading과 마찬가지로 프로그램의 실제 필요한 정보만 메모리에 올리는 방법이다

하지만 둘은 역사적으로 약간 다르다

초창치 시스템에서는 지금처럼 메인 메모리의 크기가 크지 않기 때문에 프로그램 하나조차 메모리에 올리는 것이 불가능한 경우가 많았다.

따라서 프로그래머가 수작업으로 프로그램을 쪼개서 메모리에 올려야 했기 때문에 코딩이 매우 불편하고 복잡했다

하지만 Dynamic Loading은 라이브러리를 통해서 구현하기 때문에 Overlays보다는 편리한 방식이다

Dynamic Linking

Dynamic Linking이란 "Linking을 Run Time까지 미루는 기법"이다

보통 프로그램을 작성하고 컴파일 하고 "Linking"을 통해서 실행 파일을 만들게 된다

Linking : 여러군데로 흩어진 "컴파일된 파일"들을 묶어서 하나의 실행 파일로 만드는 것

int main(){
    printf(~~~)
    scanf(~~~)
    ...
    ...
    printf(~~~)
}

이런 소스코드에서 printf, scanf같은 함수들은 라이브러리로 제공해주기 때문에 우리가 직접 printf, scanf를 구현하지 않아도 사용할 수 있다

표준 라이브러리 함수(printf, scanf, ...)들을 모아둔 거대한 라이브러리 파일이 존재한다

※ Static Linking

여기서 Static Linking을 잠시 보고가면 Static Linking은 최종적인 실행파일을 만들 때 모든 Object Code를 한곳에 집어넣는 방식이다

컴파일된 소스코드 + 사용한 라이브러리 파일들을 전부 모아서 하나의 Binary Code로 만드는 것

## Program 1
int main(){
    printf(~~~)
    scanf(~~~)
    ...
    ...
    printf(~~~)
}

## Program 2
int main(){
    printf(~~~)
    scanf(~~~)
    ...
    ...
    printf(~~~)
}

이런 2개의 프로그램이 있다고 하자

Static Linking을 통해서 Binary Code를 만들게 되면 저 중복되는 라이브러리 함수들을 중복해서 만들게 될 것이다

따라서 메인 메모리에는 중복되는 수많은 코드가 존재한다

메모리를 효율적으로 사용하지 않게 되고 따라서 메모리가 낭비된다

다시 Dynamic Linking으로 돌아와서 보게되면

## Program 1
int main(){
    printf(~~~)
    scanf(~~~)
    ...
    ...
    printf(~~~)
}

## Program 2
int main(){
    printf(~~~)
    scanf(~~~)
    ...
    ...
    printf(~~~)
}

Static Linking은 거대한 라이브러리 파일들을 각각의 프로그램 Object Code에 중복해서 놓었지만 Dynamic Linking은 거대한 라이브러리 파일들을 중복해서 놓지 않고, 라이브러리 함수를 호출하는 부분에 "stub"이라는 코드를 놓는다

stub은 해당 라이브러리 함수를 호출할 수 있는 코드이다

"어떤 라이브러리의 어떤 함수를 사용하겠다"라는 정보가 stub에 존재한다

따라서 거대한 라이브러리 파일을 프로그램의 실행 파일 코드에 포함하지 않고 대신에 stub을 넣음으로써 해당 라이브러리 함수가 필요한 순간에 Linking을 하는 것이다

당연히 거대한 라이브러리 파일 "1개"는 메인 메모리에 존재해야 한다

여기서 Dynamic Linking을 해주는 라이브러리를 Shared Library라고 한다

물론 Dynamic Linking은 OS의 도움이 필요한 기법이다

Contiguous Allocation

Contiguous Allocation은 프로세스 하나가 메모리의 연속적 공간에 적재되는 메모리 할당 방식이다

한마디로 프로세스 통째로 메인 메모리에 적재된다는 의미이다

Fixed Partition Allocation

Fixed Partition Allocation이란 일단 메인 메모리를 미리 Partition 해놓는 방법이다

동일한 크기로 Partition할 수도 있고, 서로 다른 크기로 Partition할 수도 있다

이렇게 메인 메모리를 Partition했다고 하자

Process A : 20
Process B : 10
Process C : 20
Process D : 41

※ 외부 조각 (External Fragmentation)

Process A는 [20]에 적재되었고 그 다음에 Process B는 [3]에 들어가려고 했는데 본인의 크기가 너무 커서 그 다음 block인 [12]에 적재가 되었다

Process D는 [40]에 적재가 되어야 하지만 본인의 크기보다 작기 때문에 적재가 되지 못했다

이처럼 메모리 영역에 어떠한 프로그램도 적재되지 않았지만 프로그램이 올라갈 수 없는 조각을 외부 조각이라고 한다

물론 [3]의 경우 나중에 크기가 3인 프로세스가 적재되려면 적재가 될 수 있다

그리고 전체적으로 봤을 때 총 가용 공간은 3 + "10" + 40 = 53이지만 Process D(41)은 적재가 되지 못하는 것을 볼 수 있다

Request에 대한 가용 공간은 충분하지만, Continuous 관점으로 봤을 때는 가용 공간이 전부 쪼개져 있어서 request를 허용하지 못한다

※ 내부 조각 (Internal Fragmentation)

[30] 영역에 현재 "내부 조각"이 발생했다

Process C는 크기가 20이고 [30] 영역에 할당된 것을 볼 수 있다

그러면 실질적으로 [30] 영역에서 Process C는 (20)의 영역만 사용하기 때문에 나머지 "10"은 사용되지 않고 낭비가 되고 있다

이렇게 어떠한 영역에 프로그램이 존재하기는 하지만 사용되지 않고 낭비되는 공간을 내부 조각이라고 한다

보통 메모리 공간을 할당할 때 byte단위가 아니라 block단위로 할당하고, 이 block단위는 프로세스별로 정확히 나누어지지 않는 경우가 반드시 존재하기 때문에 내부 조각이 발생한다

Variable Partition Allocation

Variable Partition Allocation은 FPA와 달리, 미리 메인 메모리를 Partition하지는 않는다

VPA는 프로그램이 적재될때 가용 메모리에 차례대로 올려준다

여기서 각 프로세스는 작업을 수행하다가 Process B가 작업이 끝나고 종료가 되었다고 하자

그러면 Process B가 있던 [8]이라는 영역은 어떠한 프로세스도 존재하지 않게 되고 만약 Process E(50)이 적재가 되려고 하는데 50 > 8이므로 External Fragmentation이 발생하게 된다

Hole

Hole이란 현재 메인 메모리의 가용 공간으로써 매우 다양한 크기의 Hole들이 메모리 여러곳에 흩어져 있을 수 있다

프로세스는 메인 메모리에 적재될 때 수용 가능한 Hole을 할당해준다

>> 따라서 OS는 현재 메모리의 {할당된 공간 & Hole}정보를 유지해야 한다

하지만 Hole이 여러개가 존재할 때 도착한 프로세스에 대해서 "어느 Hole에 할당해줄까"라는 할당 문제가 발생할 수 있다

※ Dynamic Storage Allocation Problem

(1) First-Fit

First-Fit은 Size가 N이상인 Hole 중에서 가장 첫번째로 찾아진 hole에 프로세스를 할당하는 방법이다

First-Fit 방법을 사용하면 해당 프로세스는 [15]에 적재될 것이다

(2) Best-Fit

First-Fit은 Size가 N이상인 Hole 중에서 최적의 hole에 프로세스를 할당하는 방법이다

Best-Fit 방법을 사용하면 해당 프로세스는 [8]에 적재될 것이다

(3) Worst-Fit

First-Fit은 Size가 N이상인 Hole 중에서 가장 크기가 큰 hole에 프로세스를 할당하는 방법이다

Worst-Fit 방법을 사용하면 해당 프로세스는 [50]에 적재될 것이다

실험적 결과로 (Best-Fit & First-Fit)간의 우열은 가르기 힘들고 확실한 것은 둘다 Worst-Fit보다는 속도/공간 이용률 측면에서 더 효과적인 방법이다

External Fragmentation 해결 방법

(1) Compaction

Compaction이란 사용중인 프로세스를 전부 몰아서 Hole을 한곳에 만드는 방법이다

결과적으로 모든 Hole들이 모여서 굉장히 큰 Block이 생성된다

하지만 Compaction은 비용이 굉장히 많이 드는 방법이고 "Run Time Binding"이 지원되는 경우에만 수행이 가능하다

(2) Paging & Segmentation

Paging & Segmentation의 기본 컨셉은 "프로세스를 쪼개서 메인 메모리에 적재하자"이다

Paging은 "고정 크기의 page"로 쪼개고, Segmentation은 "가변 크기의 Segment"로 쪼갠다

연속적으로 프로세스를 배치하는게 아니라 쪼개진 각각을 메인 메모리에 불연속적으로 배치하기 때문에 Externel Fragmentation 문제를 해결할 가능성이 있다

근데 Segmentation은 여전히 Externel Fragmentation이 발생할 수 있다..

Noncontiguous Allocation

Noncontiguous Allocation은 contiguous와 달리 하나의 프로세스를 쪼개서 메모리 여러 영역에 분산해서 적재하는 메모리 할당 방식이다

Paging & Segmentation & Paged Segmentation ... 등이 존재한다

Paging

Paging은 프로세스를 "고정 크기의 Page"로 나눠서 물리적 메모리에 적재하는 방식이다

여기서 물리적 메모리도 Page와 동일한 크기의 Frame으로 나누게 된다

프로세스 >> 여러개의 Page
물리적 메모리 >> 여러개의 Frame
Page Size == Frame Size

이렇게 나뉘어진 Page들은 가용 Frame에 적재된다

Paging은 각 Page마다 Binding을 해줘야 하기 때문에 "Page Table"을 활용한다

Page Table은 {Page Number - Frame Number}쌍을 보유하고 있고, 몇번째 Page가 몇번째 Frame에 적재되었는지를 캐싱하고 있다

그리고 당연히 Page Table은 프로세스마다 별도로 보유하고 있다

Paging을 사용할 때는 External Fragmentation은 발생하지 않지만, Internal Fragmentation은 발생할 수 있다

프로세스 크기 : 1000 & Page 크기 : 400
>> {400 / 400 / 200)}

물리적 메모리
>> {400 / 400 / 400 / ....}

크기 200짜리 Page는 Frame[400]에 들어가기는 하지만 내부적으로 200의 낭비 공간이 발생한다 : 내부조각

Paging Example

Process P >> Size : 20bytes & Page Size : 4bytes
Memory M >> Size : 32bytes & Frame Size : 4bytes

Logical Address <p, d>에서 p는 Page Number을 의미하고 d는 해당 Page안에서의 offset을 의미한다

각 Page별로 4개의 Page Entry(Page 원소 하나하나)를 보유하고 있다

따라서 Page Offset은 4가 되고 4개를 구분할 수 있어야 하기 때문에 "2 bits"가 필요하다

Physical Address <f, d>에서 f는 Frame Number을 의미하고 d는 Logical Address에서와 동일하게 해당 Frame안에서의 offset을 의미한다

Logical Address에서의 d와 Physical Address에서의 d는 동일한 값을 가진다

물리적 메모리 크기가 32bytes이므로 총 frame은 8개가 되고, 따라서 각 frame을 구분할 수 있어야 하기 때문에 "3 bits"가 필요하다

이제 각 Page를 Page Table에 의해서 Frame에 적재한 모습은 다음과 같다

Page Table은 메모리에 적재된다

따라서 모든 메모리 접근 연산은 총 2번의 메모리 acess가 필요하다

Page Table 접근 : Binding을 위한 접근
실제 Data/Instruction 접근

Page Table이 메모리 어디에 적재가 되었고 크기는 얼마인지를 check하기 위해서 2개의 레지스터를 사용한다

PTBR (Page Table Base Register) : Page Table의 메모리 상에서의 시작 위치
PTLR (Page Table Length Register) : Page Table의 크기

>> 이 두가지 레지스터 PTBR & PTLR은 해당 프로세스의 PCB에 저장되어 있어야 한다

근데 매번 메모리에 접근하려면 2번씩 접근해야 하고 그만큼 비용이 많이 발생하게 된다

따라서 비용 감소를 위해서 TLB라는 고속의 "Lookup Hardware Cache"를 사용한다

TLB : Translation Look-Aside Buffer

TLB는 {Page Number - Frame Number}쌍을 보유한 캐시이다

1. 일단 Logical Address <p>에 대한 <f>의 정보가 TLB에 있나 확인한다

있으면 TLB Hit이고 즉시 실제 Data/Instruction에 access

2. TLB Miss이면 결국 Page Table을 access해야한다

>> TLB에 <p>에 대한 <f>정보가 있나 확인하려면 결국 TLB 전체를 탐색해야 한다. 따라서 병렬적 탐색이 가능한 "Associative Register"를 이용해서 탐색을 진행하면 더 빨리 탐색을 할 수 있다

※ Effective Access Time

TLB Hit Ratio에 따른 실제 메모리 접근 시간은 어느정도 될까??

TLB 접근 시간 : t
메인 메모리 접근 시간 : m
TLB Hit Ratio : k

1. TLB Hit

>> (t + m) × k

2. TLB Miss

>> (t + 2m) × (1 - k)

∴ tk + mk + t - tk + 2m - 2mk = 2m + t - mk = m(2 - k) + t

Memory Protection

Page Table Entry마다 Valid/Invalid Bit를 붙여준다

▶ Protection Bit

해당 Page에 대한 접근 권한을 나타낸다 : (read/write/read-only)

애초에 본인 Page에 대한 접근 권한이기 때문에 Protection이라는 의미자체가 "다른 프로세스가 본인에게 접근"하는 것이 아니라 본인에 대한 접근 권한을 나타낸다

Code Area의 경우 실행 도중에 내용이 바뀌면 안되기 때문에 "read-only"

Data/Stack Area의 경우 읽고 변경해도 되기 때문에 "read + write"

▶ Valid/Invalid Bit

이 bit를 통해서 변환된 해당 프레임이 현재 접근 가능한지 불가능한지 표현할 수 있다

Valid Bit는 변환된 Frame에 프로세스의 Page가 적재되어있고 access 가능하다는 것을 나타낸다

Invalid Bit는 변환된 Frame에 어떠한 Page도 없기 때문에 access 불가능하다는 것을 나타낸다

해당 Frame은 아예 Page가 올라가지 않는 영역
해당 Frame에 Page가 올라가긴 하지만 해당 Page가 현재는 적재되어있지 않고 Backing Store에 존재하는 경우

현재 Valid Bit로 표현된 Page는 {0, 1, 2, 3, 5, 7, 8}이고 이 Page들은 Frame으로 Binding되고 access가 가능하다는 의미이다

Page 4의 경우 현재는 적재가 되어있지 않고 Backing Store에 있지만, 나중에 Swap In이 되면 Frame 7로 적재가 되는 Page이다

Page 6의 경우 아예 프로그램에서 사용하지 않는 Page이고 따라서 Binding해도 해당 Frame은 access가 불가능하다

프로세스의 모든 Page들에 대해서는 Page Table Entry가 존재해야 한다
따라서 사용하지 않는 Page들도 Page Table Entry는 존재한다
>> Table이라는 자료구조 특성상 위에서부터 index로 접근하기 때문에 중간에 빈공간이 존재하면 안되기 때문에

따라서 프로그램이 사용하지 않는 영역은 반드시 Invalid Bit를 붙여줘서 Binding된 Frame이 유효한 Frame인지 표시해줘야 한다

Shared Page

프로세스를 구성하는 Page중에는 "다른 프로세스와 공유 가능한 Page"도 존재한다

※ Shared Code (Re-entrant Code :: Pure Code)

서로 공유하는 코드는 메모리 낭비를 방지하기 위해서 메모리에 1번만 올리고 서로 공유해서 쓰자

그리고 서로 공유하기 때문에 누군가가 수정하면 안되므로 Protection Bit로 "read-only"를 설정해준다

Process 1, 2, 3은 Editor라는 프로그램을 공통으로 사용하고 있다

Paging기법을 사용할 때 서로 공유하는 부분은 다음 조건을 만족해서 Paging을 해야 한다

1. 반드시 동일한 Logical Address상에 존재
2. 반드시 동일한 Page Table Entry상에 존재

※ Private Code & Data

Private는 각자 본인만 사용하는 영역이기 때문에 Logical Address가 동일할 필요는 전혀 없고, 권환도 맘대로 주어도 된다

Hierarchical Page Tables

"Page Table도 Page 단위로 쪼개서 메모리에 적재하자"

## 현재 컴퓨터의 Logical Address Space : 32-bit ##
Page Size : 4KB = 2^(12) byte
Page Table Entry : 4 byte

32-bit면 전체 Logical Address Space는 2^(32) byte이고 Page Size는 4KB = 2^(12)byte 이므로 "프로세스의 전체 Page 개수"는 2^(32) / 2^(12) = 2^(20)개이다

offset : 하나의 Page Size가 2^(12) byte니까 offset은 12bit
Page Number : offset이 12bit니까 Page Number는 32 - 12 = 20bit

그리고 Page Table Entry가 4bytes이므로 프로세스별로 필요한 Page Table의 크기(프로세스 전체 Page 개수 × Page Table Entry Size)는 4byte × 2^(20) = 2^(22) byte이다

전체 주소공간이 2^(32)인데 Page Table을 위한 연속적인 공간만 2^(22)이 필요한 것은 굉장히 부담이 되는 일이다

Linear하게 PT를 적재할 때는 부담이 되는 일이다.

만약 이미 Paging 기법을 적용했는데 PT가 2^(22)라면 PT의 크기가 Page 크기보다 크기 때문에 이거는 애초에 부담이 아니라 불가능한 적재이다

따라서 Page Table을 여러개의 작은 조각으로 나누어서 메모리에 적재를 하자

Page Table을 여러개의 작은 조각들로 나눈 "Page of Page Table"을 사진에서 볼 수 있다

나눌때는 "Page 단위"로 나눠준다

나누어진 Page of Page Table 전체를 Inner Page Table이라고 부른다

각각의 Page Of Page Table 내부는 당연히 Page단위로 잘린 "여러개의 <Page of Page Table>'s Entry"가 존재할 것이다.

Outer Page Table Entry 각각은 나누어진 Page Of Page Table 각각을 가리킬 것이다

P1 : Outer Page Table Entries

P2 : Page of Page Table's Entries (Inner Page Table에 존재하는 각각의 Page의 Entry 개수)

d : Page Offset

## 현재 컴퓨터의 Logical Address Space : 32-bit & Two-Level Paging ##
Page Size : 4KB = 2^(12) byte
Page Table Entry : 4 byte

Page Size는 2^(12) byte이므로 페이지 내부를 구분하는 offset은 12bit가 필요하다

Page Offset "d" : 12bit

"프로세스의 Page 개수"는 2^(20)개이다 {2^(32) / 2^(12)}

PTE(Page Table Entry)는 4 byte이므로 "프로세스를 위한 Page Table Size"는 2^(20) × 4 = 2^(22) byte이다

근데 Page Table Size가 2^(22)인데 Page(=Frame) Size가 2^(12) byte이므로 Page Table은 메모리상에 적재될 수 없다

>> Page Table을 Page 단위로 분할해보자

One of the Inner Table's Size는 2^(12) byte(Page 단위로 잘랐기 때문)이고 PTE가 4니까 Inner Table's Offset은 10bit{2^(12) / 4}가 필요하다

Page Table을 Page단위로 분할하게 되면 2^(22) / 2^(12) = 2^(10)개의 Outer Page Table Entry가 도출된다

따라서 Outer Page Table's Size는 2^(10) × 4 = 2^(12) byte이다

이제 Frame Size(2^12)에 맞기 때문에 더이상 분할하지 않아도 된다

<32bit>

10bit : Outer Page Table Entry 개수

10bit : Inner Page Table에 존재하는 각각의 Page의 Entry 개수

12bit : Offset

## 현재 컴퓨터의 Logical Address Space : 32-bit & Two-Level Paging ##
Page Size : 1KB = 2^(10) byte
Page Entry Size : 4 byte

<이 경우에는 Two-Level Paging으로 충분할까??>

Page Size는 2^(10) byte이므로 페이지 내부를 구분하는 offset은 10bit가 필요하다

Page Offset "d" : 10bit

"프로세스의 Page 개수"는 2^(22)개이다 {2^(32) / 2^(10)}

PTE(Page Table Entry)는 4 byte이므로 "프로세스를 위한 Page Table Size"는 2^(22) × 4 = 2^(24) byte이다

근데 Page Table Size가 2^(24)인데 Page(=Frame) Size가 2^(10) byte이므로 Page Table은 메모리상에 적재될 수 없다

>> Page Table을 Page 단위로 분할해보자

One of the First Inner Table's Size는 2^(10) byte(Page 단위로 잘랐기 때문)이고 PTE가 4니까 Inner Table's Offset은 8bit{2^(10) / 4}가 필요하다

Page Table을 Page단위로 분할하게 되면 2^(24)/2^(10) = 2^(14)개의 Outer Page Table Entry가 도출된다

따라서 Outer Page Table's Size는 2^(14) × 4 = 2^(16) byte이므로 여전히 Page Size보다 더 크다

>> Outer Page Table을 또 다시 Page 단위로 분할해보자

One of the Second Inner Table's Size는 2^(10) byte(Page 단위로 잘랐기 때문)이고 PTE가 4니까 Inner Table's Offset은 8bit{2^(10) / 4}가 필요하다

2^(16) / 2^(10) = 2^(6)개의 Outer Page Table Entry가 도출된다

따라서 Outer Page Table's Size는 2^(6) × 4 = 2^(8) byte이므로 Page Size보다 작아서 충분히 들어간다

하지만 이렇게 들어가면 Internal Fragmentation문제는 발생할 수 밖에 없다

<32bit>

6bit : Outer Page Table Entry 개수

8bit : First Inner Table에 존재하는 각각의 Page의 Entry 개수

8bit : Second Inner Table에 존재하는 각각의 Page의 Entry 개수

10bit : Offset

## 현재 컴퓨터의 Logical Address Space : 64-bit & Two-Level Paging ##
Page Size : 4KB = 2^(12) byte
Page Entry Size : 4 byte

<이 경우에는 Two-Level Paging으로 충분할까??>

Page Size는 2^(12) byte이므로 페이지 내부를 구분하는 offset은 12bit가 필요하다

Page Offset "d" : 12bit

"프로세스의 Page 개수"는 2^(52)개이다 {2^(64) / 2^(12)}

PTE(Page Table Entry)는 4 byte이므로 "프로세스를 위한 Page Table Size"는 2^(52) × 4 = 2^(54) byte이다

근데 Page Table Size가 2^(54)인데 Page(=Frame) Size가 2^(12) byte이므로 Page Table은 메모리상에 적재될 수 없다

>> Page Table을 Page 단위로 분할해보자

One of the First Inner Table's Size는 2^(12) byte(Page 단위로 잘랐기 때문)이고 PTE가 4니까 Inner Table's Offset은 10bit{2^(12) / 4}가 필요하다

Page Table을 Page단위로 분할하게 되면 2^(54)/2^(12) = 2^(42)개의 Outer Page Table Entry가 도출된다

따라서 Outer Page Table's Size는 2^(42) × 4 = 2^(44) byte이므로 여전히 Page Size(2^12)보다 더 크다

>> Outer Page Table을 또 다시 Page 단위로 분할해보자

One of the Second Inner Table's Size는 2^(12) byte(Page 단위로 잘랐기 때문)이고 PTE가 4니까 Inner Table's Offset은 10bit{2^(12) / 4}가 필요하다

Outer Page Table(1)을 Page단위로 분할하게 되면 2^(44)/2^(12) = 2^(32)개의 Outer Page Table Entry가 도출된다

따라서 Outer Page Table's Size는 2^(32) × 4 = 2^(34) byte이므로 여전히 Page Size(2^12)보다 더 크다

>> Outer Page Table(1)을 또 다시 Page 단위로 분할해보자

One of the Third Inner Table's Size는 2^(12) byte(Page 단위로 잘랐기 때문)이고 PTE가 4니까 Inner Table's Offset은 10bit{2^(12) / 4}가 필요하다

Outer Page Table(2)을 Page단위로 분할하게 되면 2^(34)/2^(12) = 2^(22)개의 Outer Page Table Entry가 도출된다

따라서 Outer Page Table's Size는 2^(22) × 4 = 2^(24) byte이므로 여전히 Page Size(2^12)보다 더 크다

>> Outer Page Table(2)을 또 다시 Page 단위로 분할해보자

One of the Fourth Inner Table's Size는 2^(12) byte(Page 단위로 잘랐기 때문)이고 PTE가 4니까 Inner Table's Offset은 10bit{2^(12) / 4}가 필요하다

Outer Page Table(3)을 Page단위로 분할하게 되면 2^(24)/2^(12) = 2^(12)개의 Outer Page Table Entry가 도출된다

따라서 Outer Page Table's Size는 2^(12) × 4 = 2^(14) byte이므로 여전히 Page Size(2^12)보다 더 크다

>> Outer Page Table(3)을 또 다시 Page 단위로 분할해보자

One of the fifth Inner Table's Size는 2^(12) byte(Page 단위로 잘랐기 때문)이고 PTE가 4니까 Inner Table's Offset은 10bit{2^(12) / 4}가 필요하다

Outer Page Table(4)을 Page단위로 분할하게 되면 2^(14)/2^(12) = 2^(2)개의 Outer Page Table Entry가 도출된다

따라서 Outer Page Table's Size는 2^(2) × 4 = 2^(4) byte이므로 Page Size보다 작아서 충분히 들어간다

하지만 이렇게 들어가면 Internal Fragmentation문제는 발생할 수 밖에 없다

<64bit>

2bit : Outer Page Table Entry 개수

10bit : First Inner Table에 존재하는 각각의 Page의 Entry 개수

10bit : Second Inner Table에 존재하는 각각의 Page의 Entry 개수

10bit : Third Inner Table에 존재하는 각각의 Page의 Entry 개수

10bit : Fourth Inner Table에 존재하는 각각의 Page의 Entry 개수

10bit : Fifth Inner Table에 존재하는 각각의 Page의 Entry 개수

12bit : Offset

이러한 Multilevel Paging에서의 EAT를 공식화해보면 다음과 같다

<Example>
메모리 접근 : 100ns
TLB 접근 : 20ns
TLB Hit Ratio : 98%