운영체제 - 반효경 #8 Memory Management

unknownomad 2023. 5. 16. 00:43

# 8-1 Memory Management 1

Logical vs. Physical Address

메모리

주소 통해 접근하는 매체
주소가 매겨지는 것으로, 이 주소를 논리적 주소 / 물리적 주소 두 가지로 나눠볼 수 있음

논리적 주소

가상 주소
프로그램이 시작되면 0번째부터 주소 할당

물리적 주소

메모리의 어디에 프로그램이 올라가느냐
1개의 물리적 주소가 존재하고, 이 안에서 통으로 관리됨

주소 바인딩

프로그램 실행 시 독자적 주소 공간이 생성됨
프로그램마다 0번부터 시작되는 독자적 주소가 있는데,
이게 실행되려면 물리적 메모리의 어딘가로 올라가야 하고,
그러면 주소가 바뀌게 됨 = 주소 변환 = 주소 바인딩 = 주소 결정

Symbolic address

메모리 주소를 가지고 프로그래밍하지는 않음
메모리의 특정 위치에 변수값을 저장하지만, 메모리 몇 번째에 저장하는지와 같은 개념이 아닌, 그 이름의 '변수'에 얼마의 값을 저장하는 방식
함수 호출 시에는 함수 자체가 아닌, 함수 이름을 다루는 방식
즉, 숫자(값)를 직접 다루는 게 아니라 심볼을 다룸
➡️ 심볼릭 주소가 컴파일되면 ➡️ 숫자로 된 독자적인 논리적 주소가 되고 ➡️ 실행되기 위해 물리적 메모리로 올라가면서 물리적 주소가 됨

Logical address

Symbolic address 가 컴파일된 것

Physical address

Logical address 가 실제 실행된 것

주소 바인딩

Compile time binding

컴파일될 때

Load time binding

실행이 시작될 때

Execution time binding

Run time binding
프로그램 시작된 이후, 실행 도중에 바뀔 때

프로그램의 논리적 주소가 통째로 물리적 메모리에 올라갈 때를 가정한 그림

물리적 메모리로 주소가 올라가야 프로그램이 실행됨

그림 실행 순서

Symbolic address: A와 B를 더하고 C에서 점프
Compile
Logical address: 주소 20번지, 30번지의 내용을 더하고, 40번지에서 점프
실행 시작
Physical address

물리적 주소가 결정되는 시점

Compile time binding
Load time binding
Run time binding

Compile time binding

컴파일 타임에 주소가 미리 결정되기에 비효율적
컴파일 시점에 이미 물리적 주소가 결정되기에, 미리 정해진 주소에만 올려야 함
논리적 주소이지만 물리적 주소도 고정되며 바꿀 수 없기에, absolute code 라고도 부름
논리적 주소 위치를 바꾸거나, 메모리에 올라갈 위치를 바꾸려면, 이미 정해진 물리적 주소는 변경 불가이기에 새로 컴파일해줘야 함
e.g. 현재 0번지부터 올라가는데, 100번지부터 올리고 싶으면 다시 컴파일하기

Load time binding

프로그램이 시작돼서 메모리에 올라갈 때 물리적 메모리 주소가 결정됨
컴파일 시점에선 논리적 주소까지만 결정됨
컴파일해서 만들어지는 코드 = Relocatable code = 재배치 가능 코드
항상 특정 위치에 올라가는 게 아니라, 비어있는 위치라면 실행 시 어느 곳이든 올라갈 수 있음
e.g. 500번지 전까지 비어있으니, 그 이후부터 채워넣자

Run time binding

실행 시 주소가 결정되는 건 load time binding 과 똑같음
근데 이 주소가 실행 도중 바뀔 수 있음
얘만 주소가 바뀔 수 있기에, CPU 나 메모리를 사용할 때마다 binding 을 체크해봐야 함
e.g. 300번지부터의 주소가 700번지부터로 이동될 수 있음
메모리로 쫓겨날 수도 있음
지금 우리가 쓰는 시스템 방식
주소변환을 그때그때 해줘야 하기에 하드웨어적 지원 필요
주소 변환을 지원해주는 하드웨어 = MMU

CPU가 바라보는 주소는 뭘까?

CPU는 하드웨어라 physical address 바라볼 거 같지만, logical address 바라봄
컴파일된 실행 파일들 = instruction
CPU가 각 번지 주소에 있는 인스트럭션을 실행하려면, 실행 파일 안에 있는 값을 CPU로 읽어들여 연산해야 함
이 번지 주소 및 실행 파일 내의 값들은 전부 logical address 임
그리고 physical address 로 올라간 instruction, 즉 소스 내의 값들 또한 logical address 임
즉, 실행되어 physical address 로 올라간 실행 파일이라고는 하나, 실제 컴파일된 코드 자체에 들어간 주소값(인스트럭션 코드 안의 logical address)까지는 바꿀 수 없음(이게 바뀐다? 컴파일 다시 해야 함)
메모리에 올라가는 시작 위치는 바뀌지만 그 코드 상의 주소들은 그대로 남아있음
e.g. 메모리의 20번지, 30번지 안의 내용을 CPU 안으로 읽어들일 때의 주소 = logical address
CPU가 매번 메모리 몇 번째에 있는 내용을 달라 요청하면 ➡️ 그때 주소 변환해서 물리적 주소 찾은 후 ➡️ 그 내용을 읽어 CPU에 전달
그래서 CPU는 logical address 를 본다고 말함

Memory-Management Unit

Run time binding

주소가 계속 바뀌기에 주소 변환용 하드웨어가 필요함 = MMU
(프로그램의 논리 주소가 통째로 물리 주소로 올라가는 것을 가정한 설명)

MMU

2개의 레지스터를 통해 주소를 변환함

MMU scheme

사용자 프로그램과 CPU는 logical address 만 다룸
실제 physical address 는 볼 수도 없고, 알 필요도 없음

Dynamic Relocation

CPU 가 메모리 346 번째의 값을 달라고 하면
MMU 에서 가장 간단한 주소 변환은 2개의 레지스터로 이루어지는데,
Relocation register & limit register 통해 주소 변환이 이루어짐

현재 그림 상황

Virtual memory = logical memory
0 번지부터 3000 번지의 주소 공간에서 0 번지부터 346 번지까지의 메모리를 요청한 상황(346이라는 논리적 주소 찾기)
좌측 하단 점선 사각형 = CPU 에서 현재 실행 중인 프로그램
- 그리고 이 프로그램이 physical memory 상에서는 14000번지부터 올라와 있는 상황

주소 변환 방법

이 프로그램(프로세스)이 물리적 메모리에 올라간 시작 위치, 즉, 14000 번지 + 논리주소 346 번지 까지 읽은 후,
CPU에게 가져다주면 됨

베이스 레지스터에 시작위치 14000번지 저장
주소변환 시, 논리주소 + 시작위치

MMU 가 주소 변환 시 사용하는 레지스터 종류

Relocation register
Limit register

Relocation register

Base register
프로그램의 시작 위치 저장
주소 변환 시 논리주소 + 시작위치 = 346 + 14000 = 14346 이라는 물리적 주소를 얻게 됨

Limit register

프로그램의 최대 크기가 있는데, p1 의 최대 크기는 3000 번지, 이 레지스터는 그 값을 담고 있음
다른 프로그램의 메모리를 가져오는 걸 막기 위함
3000 + 14000 이 최대 메모리인데, 이보다 더 큰 메모리를 요청해 다른 프로그램의 범위를 차지하려는 악의적인 시도가 발생하는 것을 방지함

Hardware Support for Address Translation

CPU가 메모리 몇 번째를 달라는 논리적 주소를 주게 되면
이 논리적 주소가 프로그램 크기보다 더 큰 주소를 요청하는 게 아닌지 체크 = limit register
Limit register 의 값을 넘어가는 값을 요구하게 되면 trap 에 걸리게 됨
Trap 에 걸리면 이 프로그램이 CPU를 잡고 있다가도 하던 일을 멈추고, CPU는 운영체제에게 넘어가고, 운영체제는 trap 이 왜 걸렸는지 파악하게 됨

Trap

논리주소가 프로그램 크기보다 더 큰 걸 요구하는 경우 = 악의적인 경우
Limit register 와 logical address 를 비교
Limit register 를 벗어나는 범위이면 trap 에 걸림

정상 작동 순서

Logical address 가 프로그램 크기 이내에 있다면,
base register 의 값을 더해 주소 변환 후
물리적 메모리 어딘가에 있는 내용을 읽어 CPU에게 전달해주게 됨

Some Terminologies

Dynamic Loading

동적으로 올림 = 그때그때 필요할 때마다 메모리에 올림
메모리가 균일하게 사용되는 게 아님
프로그램 상당 부분은 거의 사용되지 않는 오류처리 등이 있고, 자주 사용되는 것도 굉장히 한정적인데,
아주 이상한 프로세스에서도 처리될 수 있도록 방어적으로 만드는 게 일반적임
이런 경우에는 사용되지 않는 것들도 메모리에 포함되는 문제가 발생함
그러니 필요할 때만 메모리에 올려놓자 = dynamic loading
OS는 프로그래머가 쉽게 dynamic loading 할 수 있도록 라이브러리 제공해줌
- OS는 페이징처리를 통해 직접 필요한 때만 메모리에 올려줌(나중에 추가 설명)

OS의 페이징 기법과 dynamic loading 은 원래 다르지만 섞어 쓰기도 함
프로그래머가 명시적으로 dynamic loading 하는 게 오리지널
프로그래머가 명시하지 않고 OS가 알아서 관리해주는 것도 dynamic loading 으로 쓰이긴 함

Overlays

Overlays

Dynamic loading 과 뭐가 다를까?
초창기 컴퓨터 시스템 메모리는 워낙 작기에 큰 프로그램을 쪼개 일부를 먼저 실행하고 ➡️ 그 다음을 메모리에 올려 실행시키는 수작업 코딩을 함 = manual overlay
OS의 지원 없고 코딩 통해 전부 수작업으로 진행

Dynamic loading

라이브러리 통해 진행되기에 훨씬 수월

Swapping

메모리에서 통째로 쫓겨나는 것
Run time binding이 swapping 효율 면에서 좋음

Schematic View of Swapping

Swap out

메모리에서 통째로 쫓겨나 하드디스크의 backing store 로 내려가는 것

Swap in

Backing store 로 쫓겨났던 게 다시 메모리로 올라오는 것

Dynamic Linking

Link

여러 군데 존재하던 컴파일된 파일을 묶어 하나의 실행파일로 만드는 과정
라이브러리도 링킹돼서 내 코드 안에 포함되는 개념 = static linking

Library

내가 작성하지 않은 함수임에도 매우 유용하기에 필요할 때 가져다 쓰는 것

Dynamic linking

내 코드 안에 라이브러리가 안 들어있기에 찾아야 함
실행파일에 라이브러리가 별도의 파일로 존재해서 이걸 찾는 걸 stub 이라 함
라이브러리 위치를 찾을 수 있는 포인터(stub)만 가지고 있고, 실제 코드는 포함하지 않는 것
라이브러리가 이미 메모리에 올라와 있다면 그걸 공유할 수 있는
Dynamic library = shared library

Allocation of Physical Memory

물리적 메모리 관리 방법

물리적 메모리의 낮은 주소 영역 : 항상 운영체제 커널이 상주함
높은 주소 영역 : 사용자 프로세스

사용자 프로세스 영역의 할당 방법

Contiguous allocation
Noncontiguous allocation

Contiguous allocation

연속 할당

Noncontiguous allocation

불연속 할당
Paging 기법 = 프로그램을 구성하는 주소 공간을 같은 크기의 페이지로 잘라, 페이지 단위로 물리적 메모리에 올려두거나 backing store 에 내려두거나 함
Page frame = 페이지가 들어갈 수 있는 공간 = 물리적 공간
불연속 할당 시 MMU 에 의한 주소 변환이 복잡해짐
- 메모리 어디에 올라가 있는지 확인 필요
- 주소 변환을 페이지 단위로 해야 하기에 binding 이 더 복잡해짐
Segmentation 기법 = 프로그램의 주소공간을 같은 크기로 자르는 게 아니라, 의미 있는 단위로 자르는 것

Contiguous Allocation

고정 분할 방식

사용자 프로그램이 들어갈 영역을 미리 나눠두는 것

가변 분할 방식

사용자 프로그램이 들어갈 영역을 미리 나눠두지 않는 것
프로그램이 실행될 때마다 차곡차곡 순서대로 올려두는 것
프로그램 D는 외부 조각들보다 크기가 커서, 외부 조각 위치에 들어갈 수 없음 = 사용 불가

낭비되는 메모리 조각

외부 조각
내부 조각

외부 조각

내가 이 프로그램을 메모리에 올리고 싶은데,
올리려는 프로그램보다 메모리 조각의 크기가 작아 사용이 안 됐을 때,
프로그램이 들어갈 수 있는 공간이 있음에도 사용되지 않는 것

내부 조각

프로그램의 크기가 분할한 크기보다 작아, 그 안에 남는 공간이 있을 때 사용되지 않는 것

Hole 이 n 보다 크기가 커야 함

Best fit

전체 hole 다 살펴본 후 적합한 hole 에 집어넣기에 hole 을 탐색하는 시간이 다소 소요됨

Run time binding 이 지원되는, 메모리 위치가 실행 중에서 변경될 수 있는 기능이 지원돼야 compaction 가능
최소한의 프로그램만을 이동시켜 큰 hole 을 만들 수 있으면 좋겠지

Dynamic Relocation

Segment

프로그램의 주소 공간을 구성하는 의미 있는 단위이자 주소 공간
Code, data, stack 으로 구성
Code 중에서도 함수를 나눠 segment 로 구성할 수도 있음
각각의 함수를 다른 segment 로 만들면 개수가 늘어남, 이 때의 함수 = 의미 단위
각 함수를 segment 로 잘라 물리적 메모리의 다른 위치에 올려놓을 수 있음
거기서 또 segment 단위로 주소 변환 해줘야
의미 단위로 잘랐기에 크기가 균일하지는 않음
(dynamic storage-allocation problem 에서도 segment 크기가 균일하지 않아 문제 발생)

Dynamic relocation

Segment 는 크게 Code segment / Data segment / Stack segment 로 나뉘는데, 각각의 세그먼트를 필요 시 물리적 메모리의 다른 위치에 올려둘 수 있는 방법

Paging

Paging

주소 변환이 페이지 단위로 이루어져야 함
레지스터 2개만을 이용한 주소 변환은 불가능
페이지 테이블 이용해 주소 변환

페이지 테이블

프로그램 구성하는 주소 공간의 페이지가 여러 개 구성되는데,
각 페이지마다 물리적 메모리의 어디에 올라가 있는지를 페이지 테이블에 표시해두는, 일종의 배열

Basic method

같은 크기로 잘랐기에 external fragmentation 발생 안 함
Internal fragmentation 발생 가능
- 프로그램의 크기가 반드시 페이지 크기의 배수가 되라는 보장은 없음
- 근데 이걸 페이지 단위로 썰다 보니, 페이지 하나보다 남는 자투리가 더 작을 수 있음
- 그럼 자투리 공간이 남는데, 페이지 하나에는 남는 자투리만 들어가고 아랫부분은 빈공간이 되기에, 외부 조각이 약간 생길 수 있음
근데 페이지 크기를 잘게 썰면 외부 조각에 영향력이 그다지 있지는 않음

# 8-2 Memory Management 2

Allocation of Physical Memory

컴퓨터 전원을 켜면 물리적 메모리에 운영체제 커널이 항상 상주
나머지 영역에 사용자 프로세스가 올라갈 수 있음

Contiguous allocation

사용자 프로세스를 연속으로 할당하는 방법
프로그램을 통째로 메모리에 올려놓는 방법
각각의 프로그램을 물리적 메모리에 올릴 때 주소 변환이 굉장히 간단함

Dynamic Relocation

한 프로그램(process p1)이 물리적 메모리에 통째로 올라가면,
프로그램의 주소 체계를 물리적 메모리의 주소 체계로 바꾸는 일
프로그램의 0번지가 물리적 메모리의 몇 번지에 올라가는지 그 시작 주소만 알면, 주소 변환이 쉽게 이루어졌음

e.g. CPU가 논리적 주소 346 번지를 요청하면

프로세스의 주소체계에서 346번지에 해당하는 게 물리적 메모리의 어디에 올라가 있는지를 주소 변환해야 아는 것
이는 레지스터를 통해 아주 간단히 주소 변환할 수 있는데,
베이스 레지스터에 프로세스의 물리적 메모리 상의 시작 위치를 담고 있고,
그럼 논리 주소 346번지 요청 시, 프로세스의 해당 주소(346번지) + 베이스 레지스터가 담고 있는 시작 주소 = 물리적 메모리의 어디에 있는지 쉽게 얻을 수 있음
근데 이는 프로그램이 통째로 메모리에 올라갈 때 그랬고, 실제로는 이렇게 진행되지 않음

Paging Example

페이징 기법

프로그램을 구성하는 주소 공간이 동일한 크기의 페이지로 잘려져, 각각의 페이지가 필요에 따라 물리적 메모리의 어느 위치든 올라갈 수 있는 방법
주소 변환이 단지 시작 위치만으로 이루어질 수 있는 게 아니기에, 각각 페이지들이 어느 위치에 올라가 있는지 알아내기 위해 페이지 별 주소 변환을 해주는 방법이 필요
이전 슬라이드처럼 단순히 레지스터 2개를 이용해 주소 변환하는 방법은 사실상 불가하다는 의미
프로그램을 구성하는 논리적 메모리를 동일한 크기의 페이지로 잘라, 페이지 별로 물리적 메모리의 적당한 어디든 비어있는 위치에 올라갈 수 있게 해주는 기법

페이지 테이블

각각의 논리적 페이지들이 물리적 메모리의 어디에 올라가 있는지 알 수 있게
각각의 논리적 페이지 별로 주소 변환하기 위한 페이지들
페이징 기법에서 주소 변환 위해 사용됨

페이지 프레임

논리적 페이지도 페이지 번호를 매기고,
물리적 메모리에서 이 논리적 페이지가 들어갈 수 있는 공간을 페이지 프레임이라 부름

페이지 프레임도 0번부터 동일한 크기의 페이지로 잘라 번호를 매김
논리적 페이지 0번이 물리적 페이지의 어디에 올라가 있는가
페이지 테이블은 논리적 메모리의 페이지 개수만큼 엔트리가 존재함
엔트리
- 테이블에서 흔히 쓰는 단어
- 배열의 practical한 의미
페이지 개수만큼 테이블의 엔트리가 존재하고,
각각의 테이블의 엔트리에는 그 페이지가 몇 번 물리적 프레임에 올라가 있는지를 나타내줌
e.g. 0번 페이지는 1번 페이지 프레임에 올라가 있음
주소 변환을 위한 페이지 테이블, 즉 페이지 배열은 순차적 검색 필요 없음
Why? 엔트리 크기가 미리 정해져 있기에
테이블이나 배열은 어떤 인덱스를 통해 곧바로 접근할 수 있는 자료구조

Address Translation Architecture

Paging Example의 다른 버전
CPU가 논리적 주소를 주면 이를 물리적 주소로 바꿔야 하는데, 페이징 기법은 주소 변환 시 페이지 테이블 사용
P = 주소에서 앞부분이 페이지 번호
d = 뒷부분이 그 페이지 내에서 얼마나 떨어져 있는지를 나타내는 offset
논리적 페이지 번호에 해당하는 엔트리를 ➡️ 페이지 테이블에서 p번째로 찾아가면 ➡️ f라는 페이지 프레임 번호가 나옴
➡️ 그럼 논리적 주소를 물리적 주소로 바꾸는데, 이는 단지 논리적 페이지 번호를 물리적 프레임 번호로 바꿔주면 주소 변환이 끝남

내부에서의 상대적 위치는 똑같음
페이지 내의 offset 부분은 주소 변환에 영향 없음
P와 f만 바뀌지, d는 바뀌지 않음

Implementation of Page Table

기본적인 MMU 기법에서는 2개의 레지스터(CPU안에 들어가는 아주 빠른 장치)로 주소 변환함
프로그램을 구성하는 주소 공간을 페이지 단위로 자르는데, 보통 페이지 단위는 4KB
- = 프로그램의 주소 공간이 굉장히 크다는 의미
주소 공간을 자르면 페이지 테이블의 엔트리가 현재 4개로 보이는데, 실제 100만개 정도 필요
- = 실제 100만개 정도의 페이지로 잘린다
- = 페이지 테이블이 엄청난 용량을 차지
프로그램마다 페이지 테이블을 별도로 둬야 하는 부담까지
페이지 테이블은 용량이 너무 커 레지스터에 넣을 수도 없고,
메모리 접근을 위한 주소 변환인데 이 페이지 테이블을 하드디스크에 저장할 수도 없고,
캐시 메모리에 들어가기에도 용량이 너무 큼
Q) 그럼 페이지 테이블은 어디에 넣어야 할까? A) 물리적 메모리에
실제로 메모리에 접근하려면 주소 변환 후 접근해야 하는데,
주소 변환을 하려면 페이지 테이블에 접근해야 하고,
또 페이지 테이블은 메모리에 존재하기에,
결국 메모리에 한 번 접근하려면 두 번의 메모리 접근이 필요
매번 두 번 접근해야 하는 부담이 커서 속도 향상이 중요함

첫 번째 memory access

페이지 테이블 통한 주소 변환 위해 메모리 접근 필요

두 번째 memory access

주소 변환 됐으면 메모리에서 실제 데이터에 접근하기 위해, 또다시 메모리 접근 필요

Base register

메모리 상에서 테이블이 어디에 있는지에 대한 시작 위치를 base register가 가지고 있음

Limit register

페이지 테이블의 길이는 PTLR이라는 레지스터가 가지고 있음

TLD

일종의 캐시
메인 메모리와 CPU 사이에 존재 및 주소 변환하는 계층

Paging Hardware with TLB

페이지 테이블

원래 물리적 메모리 안에 있음

오리지널 페이징 기법에서는

CPU가 주는 논리적 주소에 대해, 물리적 메모리 상에 존재하는 페이지 테이블을 통해 주소 변환
➡️ 이후 변환된 주소로 물리적 메모리에 접근
➡️ 그러면 물리적 메모리에 두 번 접근해야 하기에 속도 향상 필요
➡️ TLB라는 별도의 하드웨어를 둠

TLB

메인 메모리 윗단에 캐시 메모리가 있는데, 이 캐시 메모리는 운영체제에게는 감추어진(transparent) 계층
메인 메모리에서 빈번히 사용되는 데이터를 캐시 메모리에 저장해 CPU로부터 더 빨리 접근할 수 있게
이런 것처럼 메모리 주소 변환 위한 별도 캐시를 두고 있는데, 그게 바로 TLB 계층
데이터 보관용 캐시 메모리와 용도는 다름(TLB는 주소 변환이 목적)
페이지 테이블에서 빈번히 참조되는 일부 엔트리를 캐싱하는 역할
- 페이지 테이블의 전체가 아닌 일부만 담고 있음
- 빈번히 참조되는 엔트리 몇 개만 가지고 있음
페이지 테이블, 즉 메인 메모리보다 접근이 빠른 하드웨어로 구성됨
CPU가 논리적 주소를 주면 물리적 메모리 상의 페이지 테이블에 접근 전, TLB에서 먼저 검색
TLB에 저장된 정보를 이용해 주소 변환이 가능한지 확인
만약 존재하면 TLB 통해 바로 주소 변환이 이루어진 후 물리적 메모리에 접근 = 물리적 메모리에 1번만 접근
만약 TLB에 존재하지 않으면 물리적 메모리의 페이지 테이블에 접근해 주소 변환 후, 다시 물리적 메모리에 접근 = 물리적 메모리에 2번 접근

TLB는 페이지 테이블에 있는 모든 걸 가지고 있는게 아니니, 주소 변환된 프레임 번호 f만 보관한다고 주소 변환이 이루어지지 않음
- 페이지 테이블에서 몇 번째 엔트리에 해당하는 걸 주소 변환한 게 f인지
- 논리적 페이지 번호 p와 그 p에 대해 주소 변환된 프레임 번호 f, 이 둘을 쌍으로 가지고 있어야 함
전체를 가지고 있는 게 아니니 논리적 페이지 + 논리적 페이지 번호의 쌍을 가지고 있어야
주소 변환 위해 TLB의 특정 항목이 아닌 전체를 검색해야 함
p라는 페이지에 대한 주소 변환된 주소가 TLB에 있는지 확인하려면
- 위부터 전체 항목에서 p가 있는지 확인 후,
- 있으면 그에 대한 주소 변환된 정보인 f가 있다는 걸 알 수 있음
근데 TLB에 없으면 페이지 테이블로 가서 주소 변환해야
그러므로 TLB는 특정 항목이 아닌, 전체를 서칭함

Associative Register

TLB는 특정 항목이 아닌, 전체를 서칭함
그래서 병렬적 서칭이 가능한 associative registers를 통해 구현하고 있음
TLB에서 페이지 번호 p를 기준으로 p에 해당하는 주소 변환 정보가 있는지를 parallel하게 서칭해서
- 어느 한곳에 p가 있으면 주소 변환이 바로 이루어지고
- 어디에도 없으면 TLB miss가 나면서 페이지 테이블에서 주소 변환이 이루어짐

페이지 테이블

페이지 테이블에서는 엔트리 정보를 전부 서칭할 필요 없음
페이지 번호 p가 주어지면 배열의 인덱스를 이용해 바로 찾을 수 있음
직접 p번째 엔트리에 가기만 하면 주소 변환이 이루어짐
각 프로세스마다 논리적 주소 체계가 다름(각 프로세스마다 존재)
페이지 테이블의 일부를 담는 TLB도 프로세스마다 다른 정보를 담음
그래서 프로세스마다 CPU 넘겨받을 때 flush 처리

Effective Access Time

TLB에 접근하는 시간 = associative register lookup time = 입실론
TLB에 접근하는 시간이 메인 메모리에 접근하는 시간(memory cycle time)인 1보다 훨씬 작음
TLB로부터 주소 변환되는 비율 = hit ratio = a = 알파

<hit>

알파의 비율 만큼은, 즉, TLB에서 주소 변환 정보가 찾아지는 만큼은 = * a
TLB에 접근하는 입실론 시간 + 주소 변환이 끝났으니 실제 데이터에 접근하는 물리적 메모리 접근 시간 1 = (1 + 입실론)

<miss>

주소 변환 정보가 TLB에 없는 경우, 1 – a 의 비율만큼은 TLB접근을 해봤는데 TLB에 없었지 = 입실론에 한시간 걸리고
그럼 페이지 테이블에 접근하는 시간 필요, 물리적 메모리 접근 시간 1 들고
주소 변환 후 실제 데이터 접근하려고 물리적 메모리 접근해야 하니 물리적 메모리 접근 시간 + 1 = 2
알파는 거의 1에 가까운 큰 숫자, 입실론은 그에 반해 아주 작은 숫자
결과값 = 페이지 테이블만 있을 때 접근하는 시간 2보단 훨씬 작은 시간이 됨

페이지 테이블을 이용한 주소 변환

페이지 테이블이 물리적 메모리에 있고
속도를 향상시키기 위해 TLB라는 주소 변환용 캐시를 이용해 메모리 접근을 빠르게 해줌

Two-Level Page Table

논리적 주소가 32 bits로 구성되면

논리 주소는 프로그램마다 독자적으로 가지는 주소 공간, 즉, 프로그램의 크기(Virtual memory 크기)가 멕시멈 얼마까지 가능하겠느냐
현대 컴퓨터 시스템은 각 프로그램의 Virtual memory 크기와 실제 물리적 메모리 크기는 독립적
물론 물리적 메모리가 클수록 빠르긴 하나, 페이지 단위로 나뉘어 물리적 메모리로 올라오기에, 물리적 메모리보다 논리적 메모리 크기가 더 크더라도 실행 시 문제 없음
Q) 프로그램마다 가진 Virtual memory가 얼마까지 가능한가? A) 메모리를 표시하는 주소 체계를 몇 비트를 쓰느냐에 따라 달라짐

그럼 32 bits 주소 체계를 쓰면?

Q) Virtual memory에는 주소가 어떤 단위로 매겨지느냐? A) 바이트 단위로 매겨짐
- 그럼 전체 공간은 4G
- 페이지 사이즈는 4K
- 4GB를 4K로 나누면 1M 개의 페이지 개수가 얻어짐
결국 이 페이지 테이블도 물리적 메모리에 들어가야 함 = 공간 낭비가 심함
엔트리 개수가 1M (백만 여) 개인데, 엔트리 크기가 4 bytes = 공간 낭비 심함

1 bit면 표현 방법 1
2 bits면 표현 방법 4
3 bits면 표현 방법 8 = 2의 3승
…
32 bits면 2의 32승

2의 10승 = K 킬로
2의 20승 = M 메가
2의 30승 = G 기가

전체 논리적 메모리 공간에서 실제로 사용되는 공간은 굉장히 적음 = 대개 중간중간 빈 공간이 있음
근데 페이지 테이블은 위부터 아래로 인덱스 접근하기에, 빈 공간을 남겨두지 않음
주소 체계 중 실제 일부분만 사용되지만, 페이지 테이블은 다 만들어줘야 한다는 의미

2단계 페이지 테이블

페이지 테이블을 두 단계를 거쳐 주소 변환 진행
바깥쪽 페이지 테이블 + 안쪽 페이지 테이블 ➡️ 이후 실제 메모리 접근

컴퓨터에서는 보통 목적이 2가지

속도를 빠르게 하던지
공간을 줄이던지

기억해야 할 점

안쪽 페이지 테이블의 크기가 페이지 크기와 똑같음
안쪽 페이지 테이블은 테이블 자체가 페이지화되어, 물리적 메모리의 페이지 어딘가에 들어가 있게 됨, 여기서 물리적 메모리의 페이지 하나의 크기가 4KB = 안쪽 페이지 테이블의 크기
안쪽 페이지 테이블의 엔트리 하나의 크기 = 4 bytes
Q) 그럼 4KB의 안쪽 페이지 테이블에서 엔트리 하나가 4 bytes면, 4KB 안에 4 bytes를 몇 개를 넣을 수 있음?
- A) 4K 개
- 그럼 엔트리 개수는 1K 개

2단계 페이지 테이블 사용 이유

속도는 더 느리지만, 페이지 테이블을 위한 공간을 줄일 수 있음
근데 사실 바깥 테이블의 수가 줄어들 뿐, 안쪽 테이블은 백만 개 조회는 똑같음
게다가 바깥 개수 + 안쪽 개수이기에 시간은 더 걸리고, 공간도 더 차지함
주소 변환도 2번
공간도 1단계 페이지 테이블에서 쓰던 엔트리 다 필요 + 바깥용 페이지 테이블 위한 엔트리도 또 필요
그럼 시간도 손해, 공간도 손해라는 거임

그럼에도 쓰는 이유?

프로그램을 구성하는 공간 중 상당 부분은 사용되지 않음
실제 사용하는 페이지 수는 얼마 안 되는데, 페이지 테이블로 만들 땐 우리가 사용하지 않는 중간 공간들의 엔트리를 안 만들 수 없음(중간 엔트리를 없애면 배열의 인덱스 접근이 불가하기에)
➡️ 맥시멈 로지컬 메모리의 크기만큼 페이지 테이블에 엔트리가 만들어져야 함
근데 2단계 페이지 테이블을 쓰면 이를 해소할 수 있음
바깥 테이블은 논리적 크기만큼 만들어지나,
실제 사용 안 되는 주소에 대해 안쪽에서 안 만들어지고 포인터도 null로 되어 있고,
실제 사용되는 메모리 영역에 대해서만 안쪽 테이블에 만들어져서 물리적 메모리의 주소를 가리키고 있고,
중간에 사용 많이 안 하는 공간은 바깥 테이블에서도 null로 되어있고,
그럼 안쪽은 안 만들어지기에,
얼마나 사용 안 되는 공간이 많길래 2단계 페이지 테이블이 사용될지 짐작 가능
➡️ 이런 논리로 공간 절약이 가능하다는 의미

Two-Level Paging Example

page number
p1, p2 = 서울 서대문구처럼 p1 ➡️ p2로 갈수록 구체화되는

예제 순서

논리적 주소에서 바깥쪽 페이지 테이블의 인덱스를 찾은 페이지 번호로 p1 번째 엔트리로 가서 주소 변환 정보를 얻는데,
여기서 얻어지는 건 안쪽 페이지 테이블 중 어떤 페이지 테이블인지를 지정해줌
안쪽 페이지 테이블은 여러 개가 있음
그 다음 p2 번째 엔트리에 가면 물리적 페이지 프레임 번호를 얻게 됨
이 페이지 프레임 번호를 d에 덮어씌우면 페이지 프레임이 나오고,
페이지 내에서 d 번째 떨어진 위치에서 원하는 정보를 찾을 수 있음

32 bits의 주소 체계에서

페이지 안에서 떨어져 있는 offset이 몇 bits가 되어야 하고
안쪽 페이지 테이블 번호가 몇 bits로 표현되어야 하고
바깥쪽은 몇 bits로 표현되어야 하는지

페이지 하나의 크기 = 4KB = 2의 12승
그 안에서 byte 단위로 주소 구분을 하려면 몇 bits가 필요할까?

하나의 페이지 안에서 몇 번째 떨어져 있는 byte 인지를 구분하기 위해,
2의 12승 바이트를 구분하려면 12 비트가 필요함
페이지 안에서 바이트 단위로 얼마나 떨어져 있는지를 구분하는 offset에 의해 12비트가 필요

Q) 20비트의 page number는 어떻게 나눌 것이냐

안쪽 페이지 테이블에는 1K개의 엔트리가 있음
1K개의 엔트리의 위치를 구분하기 위해 p2는 몇 비트가 되어야 하느냐
1K = 2의 10승
서로 다른 2의 10승 개의 엔트리 위치를 구분하기 위해 몇 비트가 필요하느냐 = 10비트
그래서 page number인 p1, p2가 가리키는 숫자가 각각 10인 거임
64비트인 주소 체계인 경우에는 어떨까?

Access-Translation Scheme

p1 – p2 – d = p1의 비트

1K 군대 구별 ➡️ 10비트

서로 다른 4K 군대 구별 ➡️ 12비트

# 8-3 Memory Management 3

Multi-level Paging and Performance

Multi-level Paging and Performance

페이지 테이블을 위한 공간을 더 많이 줄일 수 있음
그러나 한 번 주소 변환하려면 페이지 테이블을 여러 번 거쳐야 함
또 페이지 테이블이 물리적 메모리에 있기에 주소 변환 위해 메모리에 4번 접근해야
또 주소 변환 후 실제 원하는 데이터에 접근하기 위해 또 물리적 메모리에 접근해야
그래서 총 5번의 접근이 필요해짐 = 오버헤드 엄청남

but TLB를 사용한다면 상황이 달라짐

주소 변환을 전담해주는 일종의 캐시 메모리
4단계 페이지 테이블 접근 시 시간이 오래 걸릴 수는 있으나,
대부분의 주소 변환은 TLB를 통해 직접 이루어지기에,
다단계 페이지를 사용하더라도 시간이 지나치게 오래 걸리지는 않음

Valid (v) / Invalid (i) Bit in a Page Table

왼쪽 그림

논리적 메모리
로지컬 메모리에 있는 페이지 개수 만큼 페이지 엔트리가 존재
사용되지 않는 주소 영역이 많이 존재

가운데 그림

페이지 테이블
각 엔트리에는 논리적 메모리에 있는 페이지가 물리적 메모리의 어떤 페이지 프레임에 올라가 있는지에 대한 페이지 프레임 정보, 즉, 주소 변환 정보가 들어있음
+ 주소 변환 정보 뿐만 아니라 추가적인 비트가 엔트리에 저장됨 = valid–invalid bit

프로그램의 주소 공간이 가질 수 있는 최대 사이즈만큼 페이지 엔트리가 생겨야 함
사용되지 않는 영역을 위해서도 엔트리가 만들어져야 함
Why? 테이블이라는 자료 구조 상 위에서부터 index로 접근해야 하기에, 빈 페이지가 있더라도 그대로 남겨둬야 함 = 이게 invalid bit

valid

페이지 테이블 엔트리에 가면 0번 페이지가 2번 프레임에 실제 올라와 있다는 의미

invalid

페이지가 프로그램에 의해 사용되지 않거나, 페이지가 항상 메모리에 올라가 있지 않은 경우
(사용할 때는 늘 물리적 메모리에 올라가 있으니)
그러면 하드디스크의 backing 스토어에 내려가 있을 것임
이때 그 페이지에 대한 주소 변환 시도 시, 물리적 메모리 프레임에는 안 올라와 있으니 invalid

오른쪽 그림

물리적 메모리

Memory Protection

backing store

swap area

protection bit

valid-invalid bit 말고, 또 다른 bit
자기 자신의 프로세스가 자기 자신에게만 접근하는 개념이기에, 이는 다른 프로세스의 접근과 무관함
페이지 접근 권한을 제어 = 어떤 연산에 대한 접근 권한이 있느냐를 나타냄
코드를 담는 페이지, 데이터나 스택 부분을 담는 페이지 등이 있는데,
코드의 경우, 내용이 바뀌면 안 되고, 원래의 그 내용을 cpu에서 읽어 인스트럭션을 실행하는 용도 ➡️ 그래서 코드는 read-only로 세팅
데이터나 스택은 read, write 권한 다 주고,
이런 연산에 대한 권한을 표시하는 게 protection bit

Inverted Page Table

페이지 테이블 자체가 차지하는 용량이 상당함
주소 변환을 위한 공간인데, 페이지 테이블 자체가 데이터를 많이 차지하면 안 되겠지?
주소 공간이 허용하는 한도만큼의 페이지 테이블 엔트리가 만들어져야 하고, 프로세스마다 각각 주소 변환을 해야하며, 각 프로세스마다 페이지 테이블이 있어야 하기에, 공간 오버헤드가 큼
이를 막아보자 = Inverted Page Table

Inverted Page Table Architecture

원래 페이지 테이블에 대한 주소 변환 개념을 역발상으로 전환한 것
기존에는 페이지 테이블이 프로세스마다 존재했는데, 얘는 시스템 안에 페이지 테이블이 1개만 존재
페이지 테이블의 엔트리가 프로세스의 페이지 개수만큼 존재하지 않고, 물리적 메모리의 페이지 프레임 개수만큼 존재한다는 의미
➡️ 페이지 프레임 개수만큼 엔트리가 존재

기존에는 페이지 번호를 보고 위에서부터 페이지 번호만큼 떨어지는 엔트리를 찾아 주소 변환을 진행했는데,
얘는 그게 아예 불가함. Why? 들어가는 방향이 반대임
첫 번째 엔트리에는 첫 번째 페이지 프레임에 들어가는 논리적 페이지 번호가 들어있음
…
즉, 페이지 프레임에서 먼저 f번째 엔트리를 찾으면 ➡️ 논리적 페이지 번호가 나오는 정반대의 개념
기존에는 논리적 주소를 보고 물리적 주소를 찾았는데,
얘는 물리적 주소를 보고 논리적 주소를 찾아 바꿀 수 있는 테이블
사실 우리 목적에 맞지는 않다고 봐야지

논리적 주소를 보고
➡️ 페이지 테이블에서 전체를 다 뒤져서
➡️ 해당하는 p가 나오면, 이게 f번째라면
➡️ 물리적 주소에서 f번째에 있는 정보를 찾을 수 있음
배열처럼 인덱싱해서 찾는 게 기존 페이지 테이블의 장점인데,
얘는 페이지 번호가 주어지면 엔트리를 전체 검색해야 주소 변환을 할 수 있음
그래서 이 페이지 테이블을 associative register라는 별도의 하드웨어에 넣어 병렬적으로 동시 검색 가능하게 하면 순차적 탐색 오버헤드를 줄일 수 있음

장점

시스템 안에서 하나만 존재하기에 공간을 많이 줄일 수 있음

단점

시간이 오래 걸림
엔트리를 전체 검색해야 물리적 주소의 정보를 알 수 있음
페이지 번호 p가 어떤 프로세스의 p번째 페이지 번호인지 그 프로세스 아이디(pid)를 함께 저장해야 함
왜냐하면 논리적 메모리는 프로그램마다 별도로 있는 개념이기에, 누구의 p번째 페이지인지에 대한 정보가 같이 필요

단점 보완

그래서 어떤 프로세스의 페이지 번호라는 정보를 같이 주고,
그 프로세스의 p번째 페이지가 어디인지 찾아서,
찾아진 위치가 위에서부터 몇 번째 엔트리인지 확인 후,
엔트리 위치에 해당하는 번호를 페이지 프레임 번호에 넣어주면 주소 변환 완료
근데 공간을 줄이기 위해 이렇게 일일이 다 검색하면 오버헤드가 너무 큼

Shared Page

shared code

프로그램을 구성하는 페이지 중, 다른 프로세스와 공유할 수 있는 페이지
re-entrant code
pure code
여러 프로그램들이 같은 코드를 가지고 프로그램을 돌린다면, 그들은 같은 코드를 써도 됨
이 경우, 중복 사용 가능한 코드를 메모리에 한 copy만 올려 씀
여러 프로세스가 공유할 수 있는 코드를 같은 물리적 메모리에 매핑해주는 기법

shared code의 제약조건이자 필수조건

이 코드들은 반드시 read-only
shared code는 동일한 논리적 주소(논리적 메모리에서 같은 페이지에 위치)를 가져야 함(동일한 물리적 주소를 가지는 건 당연)

private code and data

프로세스마다 별도로 가져야 하는 코드 및 데이터

Shared Pages Example

p1, p2, p3 모두

페이지 테이블에서 같은 페이지 프레임 번호로 매핑해 메모리에 한 카피만 올려 사용

논리적 주소

shared code를 가진 프로세스들은 동일한 논리적 메모리에서 페이지 번호를 가지고 있어야 함

shared memory vs shared page

shared memory	shared page
read, write 가능	read-only 코드를 공유

Segmentation

페이징 기법

프로그램을 구성하는 주소 공간을 페이지 단위로 쪼갠 것

segmentation 기법

프로세스를 구성하는 주소 공간을 의미 단위로 쪼갠 것
코드, 데이터, 스택 등으로 쪼갬
더 잘게 쪼개고 싶다? 그럼 코드 기준, main() 함수 아래 … 등 별도의 세그먼트로 구성 가능

Segmentation Architecture

페이징 기법과 비슷한 측면 있음

논리적 주소

segment-number, offset (세그먼트 안에서 얼마나 떨어져 있는지를 나타내는) 두 가지로 구성

각 세그먼트 별로 서로 다른 물리적 메모리 위치에 올라갈 수 있기에 세그먼트 별로 주소 변환을 해야 함, 그래서 세그먼트 테이블을 두고 있음
주소 변환 위한 두 가지 레지스터가 지원되는데,
테이블의 시작 위치를 나타내는 = STBR
테이블의 길이를 나타내는 = 그 프로그램이 사용하는 세그먼트 엔트리의 수 = STLR

Segmentation Hardware

CPU가 논리 주소를 주면 이를 두 부분으로 나눔
- segment-number
- offset
세그먼트 테이블의 시작 위치
- 레지스터가 가지고 있음
세그먼트 테이블은 그 시작 위치부터, 세그먼트 번호의 위치만큼 떨어진 엔트리 위치에 가면, 이 세그먼트가 물리적 메모리에 어떤 번지에 올라가 있는지에 대한 정보를 가짐

세그멘테이션 기법의 엔트리

세그멘테이션 기법은 페이지 기법과 다르게, 엔트리에 두 가지 정보를 가지고 있음
물리적 메모리 상의 시작 위치 외에,
limit이라는, 세그먼트 길이를 가지고 있음
페이지 기법에서는 페이지 크기가 모두 동일했으나, 세그멘테이션 기법에서는 의미 단위로 자르기에 세그먼트 길이가 균일하지 않을 수 있음

세그멘테이션 기법으로 주소 변환 시 고려해야 할 두 가지

CPU에 주어진 주소에서 논리 주소의 세그먼트 번호가 세그먼트 길이보다 작은 값인지 확인 필요
- Why? 세그먼트 길이보다 큰 값을 요청하면 잘못된 시도이기에 trap에 걸림
세그먼트를 통해 주소 변환 시, 세그먼트 길이보다 지금 세그먼트 안에서 떨어진 오프셋이 더 크지는 않는지 확인

정상적인 요청 = 주소 변환 = 세그먼트 시작 위치 + 오프셋
물리적 메모리에서 위에서부터 base 위치만큼 떨어진 곳에서부터 세그먼트가 시작
거기서부터 d만큼 떨어진 위치에 가면 원하는 주소의 내용이 들어있음

Segmentation Architecture (Cont.)

페이징 기법

페이지 크기가 모두 동일하기에, 오프셋이 미리 결정됨
시작 주소가 프레임 번호로 주어지면 됨

세그먼트 길이

오프셋으로 표현할 수 있는 비트수 이상은 불가함
세그먼트 크기가 다 달라서 세그먼트가 어디에서 시작하는지를 정확한 바이트 단위로 매겨줘야 함

연속할당기법에서 프로그램 크기가 균일하지 않아, 프로그램을 시작/종료할 때 여러가지 구멍이 생기는데, 세그먼트도 이와 마찬가지임
중간중간 사용하지 않는 메모리 공간(external fragmentation, 외부 조각)이 생기는 단점이 있음
➡️ 그래서 first fit / best fit을 가져다 써야 함

그럼에도 세그멘테이션 기법이 가지는 장점

의미 단위 작업 시 매우 효과적

protection

연산에 대한 권한 조건을 의미 단위로 나눠 부여
페이징 기법에서는 프로그램을 구성하는 페이지를 동일하게 자르면,
- 어떤 경우에는 코드와 데이터가 같이 들어가게 되는데,
- 그럼 read-only를 줘야 할지, read & write를 줘야 할지, 의미 단위로 나누는 게 어려워짐

sharing

의미 단위로 나눠야 효율적 작업 가능

allocation

그러나 크기가 균일하지 않기에 외부 조각 발생

# 8-4 Memory Management 4

Segmentation Hardware

논리주소

세그먼트 번호 + 세그먼트 안에서 얼마나 떨어져 있는지 그 위치를 나타내는 번호

세그먼트 번호

세그먼트가 몇 개 있느냐에 따라 세그먼트 엔트리 개수가 정해짐

세그먼트 주소 변환

세그먼트가 물리적 메모리 어디에 올라가 있느냐

세그먼트 테이블의 해당 엔트리에 가면 이 세그먼트의 물리적 메모리 상의 시작 위치, 즉, base라는 주소값이 있음
base + 얼마나 떨어져 있느냐를 상징하는 offset 더해주면 주소 변환 가능

세그먼트는 의미 단위로 자르기에 길이가 균일하지 않음
그래서 세그먼트의 시작 위치 + 길이를 세그먼트 테이블에 각각 담고 있음
세그먼트 길이보다 큰 값을 요구하면 적절하지 않은 메모리 참조인 것

주의사항

offset <= limit, 합당한 메모리 참조일 때만 주소 변환 해주기
offset = 세그먼트 내에서 얼마나 떨어져 있는지
limit = 세그먼트 길이
이 조건 벗어나면 trap 걸어서 방지해줘야

Segmentation Architecture

Example of Segmentation

페이징 기법에 비해, 메모리 공간 낭비 덜함

세그먼테이션

의미 단위 처리 / 공유, 보안 등에 활용

페이지는 개수가 되게 많은데, 세그먼트는 별로 없음
➡️ 페이징 기법은 테이블을 위한 메모리 낭비가 심함

Segmentation Architecture (Cont.)

Sharing of Segments

서로 다른 프로세스가 세그먼트 공유

segment 0

코드를 담고 있고, 서로 다른 프로세스에서 같은 역할을 함

shared segment

같은 물리적 메모리에 한 copy가 올라감(base : 43062)

segment1

data1, data2 : 서로 다른 주소 변환 정보가 들어있음

private segment

별도의 주소 변환 처리

Segmentation with Paging

segmentation & paging 혼합 기법
1개의 세그먼트가 여러 개의 페이지로 구성됨
세그먼트에 대한 주소 변환이 먼저 이루어짐

logical address

s = 세그먼트 번호
d = 세그먼트 안에서 얼마나 떨어져 있는지를 나타내는 offset

세그먼트 테이블이 메모리의 어디에 와 있는지를 찾아야 함
STBR 레지스터에 세그먼트의 시작 위치 정보가 들어있음
거기서부터 s번째 엔트리에 가면 s 세그먼트에 대한 주소 있음

오리지널 세그멘테이션 기법

세그먼트 테이블에 가면, 이 세그먼트가 물리적 메모리 어디에 올라가 있는지, 그 시작 위치가 담겨 있었음
근데 오리지널에서는 세그먼트가 물리적 메모리에 통째로 올라가기에, 세그먼트의 시작 위치를 알려줘도 되지만,

혼합 기법은

한 세그먼트가 여러 개의 페이지로 구성됨
그래서 물리적 메모리에 올라갈 때 페이지 단위로 쪼개져서 올라감
뭐가 장점일까? 중간중간 빈 곳 생겨 first나 best를 반영할 필요 없어짐 = allocation 문제가 발생하지 않음
Why? 물리적 메모리에는 페이지 단위로 올라가고, 세그먼트는 페이지 개수의 배수로 구성이 됨

의미 단위로 해야 하는 공유 / 보안 등은 세그먼테이션 레벨에서 진행
특정 세그먼트가 read-only인지, read & write 가능한지 등을 이 단계에서 표시
실제 물리적 메모리로 올라갈 땐 페이지 단위로 올라감
내부에서는 페이지 기법을 쓰는 게 수월함

두 단계의 주소 변환을 거치지만,

세그먼트가 각 페이지 별로 주소 변환
세그먼트 당 페이지 테이블이 존재하게 됨
세그먼트 테이블의 해당 엔트리에 가면 이 세그먼트를 구성하는 페이지 테이블의 시작 위치가 나옴
페이지 테이블의 엔트리 개수 = 세그먼트 길이

p = 페이지 번호
d = 페이지 내에서 얼마나 떨어져 있는지에 대한 offset
페이지 테이블의 시작 위치로부터 페이지 번호 만큼 떨어진 곳에 가면 해당 페이지에 대한 주소 변환 결과가 나오고,
물리적 메모리의 몇 번째 프레임에 있는지 그 번호가 나오게 됨

physical address

f = 물리적 메모리 내에서 몇 번째인지 프레임 번호
d = 페이지 안에서의 offset이 그대로 반영됨, 이게 물리적 메모리의 주소