- 연속 할당 : 프로그램이 메모리에 올라갈 때 통째로 메모리에 올라가는 방식
- 불연속 할당 : 프로그램을 구성하는 주소 공간을 같은 크기의 페이지 단위로 잘게 쪼개서 페이지 단위로 메모리에 올리는 방식
[ 불연속 할당 (Noncontiguous Allocation) ]
● Paging 기법
프로그램을 구성하는 주소 공간을 같은 크기의 페이지로 자르는 방법으로 페이지 단위로 물리적인 단위에 올려놓거나 Backing Store에 내려놓거나 한다.
물리적인 메모리에 사용자 프로그램이 들어갈 수 있는 공간들을 똑같은 크기로 잘라 놓는다.
물리적 메모리 공간 하나하나를 Page Frame이라고 하는데 Page Frame에는 Page가 올라갈 수 있다.
Paging 기법을 쓰면 Hole의 크기가 일정하지 않아서 어떤 Hole에 집어넣을 것인가 고민하거나 Hole들을 한 곳으로 모을 필요가 없다.
물리적 메모리에서 비어있는 위치가 있으면 그건 Page Frame이 비어있는 것이기 때문에 프로그램에 어떤 페이지든 간에 어디든 들어갈 수 있다.
대신, 불연속 할당을 하게 되면 잘린 각각의 페이지가 물리적 메모리 어디로 올라갔는지 확인을 해야 하기 때문에 주소 변환이 복잡해진다.
● Segmantation 기법
프로그램의 주소 공간을 같은 크기로 자르는 게 아니라 의미 있는 단위로 자르는 것이다.
프로그램의 주소 공간은 Code, Data, Stack으로 구성되어 있으며, 의미 단위인 Code Segment, Data Segment, Stack Segment로 구분하거나 더 잘게 자를 수도 있다.
의미 있는 단위로 나눈 거라 크기가 동일하지는 않아서 Dynamic Storage Allocation Problem 발생 가능성이 있다.
[ Paging ]
주소 공간을 동일한 페이지로 나누고, 그 페이지 일부는 Backing Store에 있고 일부는 물리적 메모리에 페이지 단위로 불연속적으로 올라갈 수 있다.
물리적 메모리도 페이지 크기로 나누고 페이지가 들어갈 수 있는 위치를 Frame이라고 하며, 프로그램의 주소 공간을 동일한 크기로 자른 것은 Page라고 한다.
주소 변환은 Page 단위로 이루어지기 때문에 두 개의 레지스터로 변환하지 못하기 때문에 Page Table로 주소 변환을 한다.
Page Table은 각각의 페이지마다 물리적 메모리 어디에 올라가 있는지 알려주는 일종의 배열이다.
✓ Paging
프로세스의 Virtual Memory를 동일한 Size의 Page로 나눔
Virtual Memory의 내용이 Page 단위로 Noncontiguous 하게 저장됨
일부는 Backing Store에, 일부는 Physical Memory에 저장됨
✓ Basic Method
Physical Memory를 동일한 크기의 Frame으로 나눔.
Logical Memory를 동일한 크기의 Page로 나눔. (Frame과 같은 크기)
모든 가용 Frame들을 관리
Page Table을 사용하여 Logical Address를 Physical Address로 변환
같은 크기로 잘랐기 때문에 External Fragmentation이 발생하지 않는다.
반면, 프로그램의 크기가 반드시 페이지 크기의 배수가 되는 것은 아니기 때문에 Internal Fragmentation은 발생 가능성이 있다.
● Paging Example
Paging은 논리적인 메모리를 동일한 크기의 페이지로 잘라서 각각의 페이지별로 물리적 메모리의 위치에 올라갈 수 있게 하는 방법이다.
주소 변환을 위해서 Page Table을 사용하고 Page Table은 각각의 논리적 페이지들이 물리적인 메모리 어디에 올라가 있는지 나타낸다.
페이지 테이블에는 논리적인 메모리 페이지 개수만큼 Entry가 존재하고 Entry는 그 페이지가 몇 번째 물리적 프레임에 올라가 있는지를 나타낸다.
아래의 그림을 보면 0번 Page는 1번 Frame에 올라가 있다는 것을 알려주는 Page Table이다.
Entry의 크기가 정해져 있기 때문에 주소 변환을 위해서 테이블을 순차적으로 탐색할 필요가 없다.
만약, n번째 페이지를 주소 변환하고 싶다고 하면, 페이지 테이블에서 n번째 Entry를 찾으면 그 페이지가 몇 번 Frame에 올라가 있는지 알 수 있다.
Table이나 배열이라는 것은 Index를 이용해 곧바로 접근 가능한 자료구조이다.
● Address Translation Architecture
주소 앞부분은 페이지 번호이고 뒷부분은 그 페이지 내에서 얼마나 떨어져 있는지를 나타내는 Offset이다.
논리적인 페이지 번호에 해당하는 Entry인 p를 가지고 Page Table에서 p번째에 찾아가면 f라는 Frame이 나온다.
이렇게 논리적인 페이지 번호를 물리적 프레임 번호로 변경하면 주소 변환이 끝난다.
● Implementation of Page Table
Page Table은 어디에 위치할까?
프로그램을 구성하는 주소 공간을 Page 단위로 자르는 데, 보통 페이지의 크기는 4KB이다.
프로그램의 논리적 메모리 크기는 4GB이므로 대략 Page Table의 Entry가 100만 개 정도 필요하다.
이 100만 개의 Entry가 CPU의 레지스터에 들어가기 힘들다.
게다가 Page Table은 각 프로그램마다 존재하므로 레지스터에 넣을 수 없고, 메모리 접근을 위한 주소 변환이기 때문에 하드 디스크 같은 곳에다가 저장할 수도 없다.
또한, 캐시 메모리에 들어가기에도 용량이 너무 크기 때문에 Page Table은 물리적 메모리에 넣는다.
한 번은 Page Table을 위한 메모리 접근이 필요하고 주소 변환이 되었으면 실제 데이터를 접근하기 위해서 메모리에 접근해야 한다.
따라서 데이터에 한 번 접근하기 위해 메모리에 두 번 접근해야 하는 상황이 발생한다.
Paging 기법에서 두 개의 Register가 Page Table Base Register와 Page Table Length Register로 사용된다.
즉, 메모리상에 Page Table이 어디에 있는지 그 시작 위치를 PTBR이 갖고 있으며, 그 Page Table의 길이는 PTLR이 갖고 있다.
Base Register와 Limit Register가 여기서는 주소 변환을 위한 Page Table의 Base 값하고 Limit값을 갖고 있는 용도로 사용한다.
매번 데이터에 한 번 접근하기 위해 메모리에 두 번 접근하는 건 시간이 두 배로 걸리기 때문에 비용이 크다.
그래서 속도 향상을 위해 별도의 하드웨어인 Associative Register(TLB) 일종의 캐시를 사용한다.
이 캐시는 메인 메모리와 CPU 사이에 존재하는 주소변환을 해주는 계층이다.
- Page Table은 Main Memory에 상주
- Page-Table Base Register (PTBR)가 Page Table을 가리킴
- Page-Table Length Register (PTLR)가 테이블 크기를 보관
- 모든 메모리 접근 연산에는 두 번의 Memory Access 필요
- 속도 향상을 위해 Associative Register 혹은 Translation Look-Aside Buffer (TLB)라 불리는 고속의 Lookup Hardware Cache 사용
● Paging Hardware with TLB
CPU가 주는 논리주소에 대해서 메모리상에 존재하는 Page Table을 통해 주소 변환 후, 변환된 주소로 물리적인 메모리에 접근한다.
이렇게 되면 두 번의 메모리 접근이 필요고 이러한 문제를 개선하기 위해서 TLB라는 별도의 하드웨어를 둔다.
메인 메모리에서 빈번하게 사용되는 데이터를 캐시 메모리에 저장해 CPU로부터 더 빨리 접근할 수 있는 캐시 메모리가 있는 것처럼
메모리 주소 변환을 위한 별도의 캐시를 두고 있는 게 TLB 계층이다.
주소 변환을 위한 캐시 메모리이며 데이터를 보관하는 캐시 메모리와는 다른 용도이다.
TLB는 Page Table에서 빈번하게 참조되는 일부 Entry를 캐싱하고 있으며 메인 메모리보다 접근 속도가 빠른 하드웨어로 구성되어 있다.
CPU가 논리적 주소를 주면 메모리 상에 있는 페이지 테이블에 접근하기 전에 TLB를 먼저 검색한다.
TLB에 저장되어 있는 정보를 이용해서 주소 변환이 가능한지 체크하는 과정이다.
만약 p에 해당하는 Entry가 Page Table로 가기 전에 TLB에 이미 저장되어 있다고 하면 TLB에 의해 주소 변환이 이루어진다.
그렇게 되면 주소 변환을 해서 바로 물리적인 메모리에 접근하게 되므로 메모리에 한 번만 접근하면 된다.
TLB가 없는 경우에는 Page Table을 통해서 일반적인 주소 변환을 하고 메모리에 접근을 한다. (메모리에 두 번 접근)
TLB는 Page Table 정보 전체를 담고 있는 게 아니라 일부만 갖고 있다. Entry가 100만 개 정도 되니까 빈번히 참조되는 Entry 몇 개만 TLB에 갖고 있다.
주소 변환을 할 때, Page Table에서 페이지 번호가 p면 위에서부터 p번째 Entry를 가면 f라는 Page Frame이 나온다.
즉, TLB는 논리적 페이지 번호 p와 p에 대한 주소 변환된 프레임 번호 f를 쌍으로 갖고 있어야 한다.
이게 일반적인 Page Table과의 차이점이다. 주소 변환을 위해서 TLB에서 특정 항목을 검색하는 것이 아니라 Table 전체를 검색해야 한다.
그러다 보니 시간이 오래 걸리고, 이걸 막기 위해 TLB는 보통 Parallel Search가 가능한 Associative Register를 이용해서 구현해야 한다.
CPU가 페이지 번호 p를 주면 p에 해당하는 주소 변환 정보가 있는지를 Parallel 하게 검색한다.
만약 p가 있으면 주소 변환이 바로 하고 없으면 Page Table을 이용해 주소 변환을 한다.
프로세스마다 각각의 논리적 주소 체계가 다르고 이것에 대한 주소 변환을 해야 하기 때문에 Page Table은 각각의 프로세스마다 존재한다.
따라서 TLB도 프로스세마다 다른 정보가 저장되어야 한다.
CPU가 다른 프로세스로 넘어가면, 페이지의 주소 정보가 달라지기 때문에 Context Switching이 일어나면 TLB Flush 하여 모든 Entry를 비워야 한다.
● Effective Access Time
실제로 메모리에 접근하는 시간은 어떻게 될까?
TLB에 접근하는 시간을 입실론(ε)은 메인 메모리에 접근하는 시간인 1보다 작다고 하고, TLB로부터 주소 변환 정보가 찾아지는 비율은 알파(α)라고 하자.
알파의 비율만큼은 (TLB에서 주소 변환 정보를 얻는 만큼) TLB에 접근하는 시간인 입실론과 메인 메모리에 접근하는 시간인 1을 곱한 시간만큼 걸릴 것이다.
그리고 주소 변환 정보기 없는 비율인 1-α와 메모리에 두 번 접근하는 시간 2 + TLB에 접근하는 시간(ε)을 곱해주면 Miss Time이 나올 것이다.
실제로 알파(α)의 값이 굉장히 높고 입실론(ε) 값은 굉장히 작은 값이다. Page Table만 있을 때 접근하는 시간 2보다 값이 훨씬 작다.
✓ Associative Register Lookup Time = ε
✓ Memory Cycle Time = 1
✓ Hit Rate = α (Associative Register에서 찾아지는 비율)
✓ Effective Access Time (EAT)
EAT = ( 1 + ε ) α + ( 2 + ε ) ( 1 - α ) = 2 + ε - α
<hit> <miss>
페이지 테이블은 물리적 메모리에 있고, 속도 향상을 위해 TLB라는 주소 변환용 캐시를 이용해서 메모리 접근을 더 빠르게 한다.
다음 포스팅에서 2단계 Page Table을 알아보자.
이전 발행글
[운영체제] Memory Management 1 (Logical vs Physical Address, 주소 바인딩, MMU)
● Logical Address vs Physical Address (논리적 주소 vs 물리적 주소) 프로그램이 시작되면 독자적인 주소 공간이 형성된다. 물리적인 메모리 내에서 3GB~4GB 주소 공간에는 운영체제 커널이 올라가 있고, 1G
rannnneey.tistory.com
2023.01.27 - [Operating System] - [운영체제] Memory Management 2 (동적 로딩, 동적 링킹, 오버레이, 스와핑)
[운영체제] Memory Management 2 (동적 로딩, 동적 링킹, 오버레이, 스와핑)
Some Terminologies Dynamic Loading Dynamic Linking Overlays Swapping ● 동적 로딩 (Dynamic Loading) 프로그램 전체를 메모리에 올리는 것이 아니라 필요할 때(해당 루틴이 불려질 때마다) 해당 루틴을 메모리에 올리
rannnneey.tistory.com
2023.01.31 - [Operating System] - [운영체제] Memory Management 3 (연속 할당, 고정 분할 방식/가변 분할 방식, 외부 조각/내부 조각
[운영체제] Memory Management 3 (연속 할당, 고정 분할 방식/가변 분할 방식, 외부 조각/내부 조각
물리적 메모리는 낮은 주소 부분에 운영체제 커널이 항상 상주하고 있고, 높은 주소 영역에는 사용자 프로그램들이 올라가 있다. 사용자 프로그램이 올라간 영역을 관리하는 방법은 크게 두 가
rannnneey.tistory.com
