[OS] Address Translation

이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다.

 이 글에서는 OS가 실행하는 address translation을 설명한다. 예전에 작성했던 virtual memory 포스팅에서 작성했던 내용과 겹치는 부분이 상당히 많다.

 

Memory Abstraction

Process를 메모리에 올릴 때

 memory에 단 하나의 process만 올라간다면 앞서 봤던 복잡한 과정이 필요 없다. 그렇지만 다른 process가 실행되면 memory의 모든 정보를 디스크로 뺐다가 넣는 과정을 거쳐야 하기에 성능이 매우 나쁠 것이다.

 

physical memory

 반면 위 그림처럼 여러 process를 physical memory에 올린다고 생각해 봤을 때, 여러 process가 동시에 실행할 수 있지만 (multiprogramming), 각 process가 다른 process에 접근할 수 있는 protection issue가 발생한다. 또한 어떻게 이를 해결한다고 하더라도 process 간의 sharing은 어떻게 해결할 것인지 등 다양한 문제가 발생한다.

 

 

Address Space

address space

 address space는 OS가 제공하는 physical memory의 abstraction이다. 

 모든 process는 0부터 시작하는 address space 내의 주소에 접근하지만 이는 physical address가 아니다. 따라서 virtual address를 physical address로 변환하는 과정이 꼭 필요하다. 만약 변환하지 않고 바로 해당 주소에 접근한다면 다른 process, 또는 OS kernel이 위치해 있는 address에 접근할 수 있기 때문이다.

 

 

Free Space Management

 process가 physical memory에 올라가기 위해서는 single contiguous section이 필요하며, OS는 physical memory의 빈 공간의 어디에 process를 넣을 것인가를 결정한다. dynamic memory allocation 포스팅에서 살펴봤던 것처럼 free list를 유지하면서 first fit, best fit, worst fit 등 여러가지 기법을 사용해 process를 올릴 수 있는 적당한 free space를 찾는다.

segmentation과 paging 등에 의해 process가 single contiguous section 안에 올라간다는 명제는 깨진다.

 

• first fit : free block 중 할당할 수 있는 size를 가진 첫 번째 free block에 할당하는 방법
• best fit : 모든 free block을 살펴보고 할당할 수 있는 size 중 제일 작은 free block에 할당하는 방법
• worst fit : 제일 큰 free block에 할당하는 방법

 worst fit은 일반적으로 사용하지 않는 방법이다. best fit은 memory를 가장 효율적으로 사용할 수 있지만 속도가 느리고, first fit은 속도가 빠르지만 memory 효율성이 조금 떨어진다.

 

 

Fragmentation

 마찬가지로 dynamic memory allocation 포스팅에서 살펴봤던 내용이다.

• internal fragmentation : 할당된 block이 data보다 클 때
• external fragmentation : memory에 충분한 공간이 있지만 큰 하나의 free block이 없어 메모리를 할당할 수 없는 상황

 

 external fragmentation을 해결하기 위해 free block을 합쳐 하나의 큰 free block을 만드는 compaction을 사용할 수 있지만 모든 relocation이 가능해야 하며, 너무 큰 cost가 발생하며, 이로 인해 발생하는 direct memory access 등의 I/O 문제 또한 해결해야만 한다.

 external fragmentation이 발생하는 근본적인 문제는 너무 큰 크기를 가진 process를 single contiguous section에 할당하려 하기 때문이다. 이를 해결하기 위해 segmentation과 paging으로 process를 쪼개어서 external fragmentation을 막는다.

 

 

 

Address Translation

 address translation의 골자는 다음과 같다.

1. processor가 virtual address를 생성한다.
2. MMU가 virtual address를 physical address로 translate한다.
3. memory가 해당 address에 있는 data를 fetch해 processor로 보낸다.

 

 address translation의 방법에는 크게 3가지, base and bound, segmentation, paging이 있으며 이를 이용해 copy on write, zero on reference, fill on demand, demand paging, memory mapped file 등의 기능을 구현할 수 있다.

 이를 통해 다음과 같은 목표를 달성할 수 있다.

• memory protection : virtual address에서 physical address로 바꿀 때 memory access를 관리할 수 있다.
• memory sharing : process 간에 library를 공유하거나 communication을 할 수 있다.
• sparse address : sparse한 address도 효과적으로 사용할 수 있다.
• portability : 다른 process의 address를 신경쓸 필요 없이 자신의 address만 신경쓰면 된다.

 

 

방법 1 : Base and Bound

base and bound

 address translation을 구현하는 제일 간단한 방법은 base and bound이며, single contiguous section을 physical memory에 올리되, 단순히 위치만 변경하는 것이다. 

 

 base와 bound는 register이며, 다음과 같은 정보를 가지고 있다.

• base : virtual memory가 physical memory의 어디에서 시작하는지 주소값.
• bound : process size.

 virtual address + base로 physical address로 변환하며, 이 값이 bound보다 크다면 해당 processor의 범위를 벗어난 것이므로 exception을 발생시킨다.

 

장단점

• 간단하고 빠르다.
• compaction을 할 때 physical memory의 값만 옮기고, base register만 수정하면 되므로 relocation할 때도 성능이 좋다.

 

• translation 이후에 bound보다 값이 크다면 exception이 발생하기 때문에 다른 process의 code나 data에 접근할 수 없다.
• bound값이 고정되어 있기 때문에 heap이나 stack을 정해진 크기 이상으로 키울 수 없다.
• 메모리에 접근할 때 access permission를 사용하지 않으므로 code와 같은 read only 영역을 보호할 수 없다는 단점이 있다.

 

 

방법 2 : Segmentation

segmentation

 segmentation은 base and bound가 가진 단점을 조금 개선시킨 방법이다. 기존에 오직 하나의 base와 bound만 사용했다면, base와 bound array를 사용함으로써 virtual memory를 segment로 나누고, access permission를 사용해 memory protection도 사용할 수 있다.

segment는 logically contiguous memory의 영역이다. 보통 code, data, heap, stack으로 나눈다.
R, W, X는 각각 readable, writeable, executable이다.

 

 process는 virtual address를 segment와 offset 부분으로 나눈다. segment는 segment table의 index로 사용하고, 해당 base에 offset을 도해 physical address로 변환한다. 만약 bound보다 더 크다면 exception을 발생시킨다.

 segment table은 크기가 작기 때문에 CPU에 저장된다.

 

장단점

• 앞서 base and bound의 경우 bound값이 고정되어 있기 때문에 heap과 stack을 정해진 크기 이상으로 키울 수 없다는 단점이 있었다. 그러나 이 방법의 경우 heap이나 stack에 해당하는 bound값을 조절해 쉽게 크기를 조절할 수 있다.
• 다른 process의 segment table이 가리키는 값을 똑같이 만들어 process 간의 data sharing을 쉽게 구현할 수 있다.
• access permission도 있기 때문에 code 영역을 보호할 수도 있다.

 

• segment 크기가 다양하므로 관리하기 어렵고, external fragmentation이 발생한다.
• 다른 segment에 의해 relocation이 발생할 수 있다.

 

 

기능 : Copy On Write

 unix에서 process fork를 하면 parent process의 사본을 만든다. 이 때 모든 정보를 copy하는 것은 cost가 많이 들기에 fork 직후에는 같은 memory를 가리키다가 수정되면 그 때 복사하는 방법이 copy on write이다. (write 이전까지 copy를 미루는 방법.)

 segmentation을 사용하면 쉽게 copy on write를 구현할 수 있다.

1. segment table을 복사한다. 이 때 parent와 child의 segment table의 access permission은 read only로 바꾼다.
2. write가 발생하면 access permission error이므로 exception이 발생한다.
3. exception handler가 copy on write임을 감지한 후, 그 때 parent segment의 사본을 만들고 child segment로 바꾼다. access permission도 R/W로 바꾼다.

 

기존 상황. 처음에는 parent process P1만 존재한다.

fork가 일어난 상황.

 기존 상태에서 fork가 일어나면 1번과 같이 segment table을 복사하고 access permission을 모두 read only로 바꾼다. 이 때는 모든 base와 bound가 같으므로 P1과 P2가 같은 physical memory를 바라본다.

 이 상황에서 processor P2가 write를 시도했다고 하자.

 

P2에서 write가 발생한 상황.

 write가 발생하면 read only이기 때문에 access permission error로 인해 exception이 발생한다. exception handler는 copy on write임을 감지하고, 해당 segment를 복사한 후 access permission을 R/W로 설정한다.

 

 

기능 : Zero On Reference

 OS가 새로운 memory를 할당받으면 이전에 사용하던 값이 memory에 남아 있을 수 있기 때문에 제일 먼저 해당 영역을 모두 0으로 만들어야 한다.

 process가 생성될 때, 크게 4가지 segment - stack, heap, data, code - 영역으로 만들어지는데 data와 code 영역의 크기는 정해져 있으므로 0으로 초기화하는 것은 쉽다. 문제가 되는 것은 stack과 heap 영역인데, 얼만큼 크기가 필요한지 실행하기 전까지는 모르기 때문이다. 이를 해결하기 위해 reference가 발생했을 때만 0으로 만드는 zero on reference 기법을 사용한다.

 

 참고로 stack 주소값을 넘긴 주소값을 사용할 때는 다음과 같은 과정을 거친다.

1. segmentation fault가 발생한다.
2. kernel이 memory를 추가로 할당한다.
3. 할당받은 memory를 0으로 만든다.
4. segment table을 수정한다 : bound값을 수정한다.
5. process를 재개한다.

 

 

방법 3 : Paging

 segmentation의 문제 중 하나는 segment 크기가 다양해 관리하기 어렵다는 것이었다. 이를 해결하기 위해 memory를 특정 크기로 잘라 관리하는 방법인 paging을 사용한다. 이 때 virtual memory에서 단위를 page, physical memory에서 단위를 page frame이라고 한다.

base and bound나 segmentation의 경우 크기가 작기 때문에 register에 값을 보관할 수 있지만 page table은 크기가 커서 memory에 저장한다. page table의 위치와 크기는 register에 저장된다. (page table base register)

 

paging

 translation은 다음과 같이 이루어진다. 용어는 virtual memory 포스팅을 참고하자.

1. CPU가 virtual address를 보낸다.
2. MMU가 virtual address로부터 VPN, VPO로 파싱한다.
3. page table register를 이용해 page table에 접근하고, VPN을 이용해 page table에 있는 PPN을 얻어온다.
   • 이 때 page table length register와 page table size register를 사용해 사용해 page table의 element에 접근하거나 범위를 벗어나는지 검사한다.
4. PPN과 VPO를 이어붙여 physical address를 만든다.

 

장단점

• paging을 사용하면 memory를 page 단위로 나누기 때문에 external fragmentation이 발생하지 않는다.
• segmentation의 경우 메모리 관리가 복잡했지만 paging은 physical memory를 bitmap으로 표현할 수 있기 때문에 free page를 찾는 것이 매우 쉽다.
• data sharing이 쉽다. 같은 page frame을 가리키게 하면 되기 때문이다.

 

• page size가 너무 큰 경우 internal fragmentation이 발생한다.
• page size가 너무 작은 경우 page table이 비대해진다.

 

Paging을 사용할 때 Copy On Write와 Zero On Reference

 segmentation을 사용해서 구현하는 기능인 copy on write와 zero on reference의 경우, paging도 똑같은 방식으로 지원한다.

 단, copy on write의 경우 segment 단위가 아닌 page 단위로 copy on write를 사용하며, zero on reference의 경우 page table element에 invalid를 표기하고, 확장 할 때 page 단위로 0으로 만든다.

 

 

기능 : Fill on Demand

 프로그램을 실행할 때 모든 영역을 바로 memory에 올리는 것이 아니라 필요할 때 memory에 올리는 방식이다.

1. 프로그램이 시작한 직후에는 physical memory에 아무것도 올라가 있지 않은 상태이므로 page table을 모두 invalidate한다.
2. page 참조가 일어난 경우, page가 invalid하므로 page fault가 일어난다. (OS kernel trap)
3. page fault handler가 disk로부터 page를 가져오고 page table의 해당 page를 validate한다.
4. 실행을 재개한다.
5. 남은 page는 실행 중에 background로 가져온다.

 

 

 

다른 Translation들

 앞서 base and bound, segmentation, paging을 살펴봤다. 실제로 작동하고 있는 OS는 하나의 방법만 사용하는 것이 아니라 여러 개의 방법을 섞어 사용한다. 그렇지만 대부분의 경우 paging이 제일 low level에 위치해 있는데, memory allocation, disk transfer 등이 효율적이기 때문이다.

 

 

Paged Segmentation

 1단계로 segmentation, 2단계로 paging을 사용하는 방법이다.

 

 각각의 element는 다음 정보를 가지고 있다.

• segment table element
  • page table로의 pointer
  • page table 길이
  • access permission
• page table element
  • page frame
  • access permission

 

paged segmentation

 paged segmentation은 위 그림과 같이 이루어진다.

1. processor가 virtual address를 생성하면 MMU가 segment, page, offset 부분으로 나눈다.
2. segment table에서 segment 부분에 해당하는 element를 찾는다.
3. 해당 element와 page 부분을 이용해 bound를 검사한다.
   • base 부분에는 page table pointer가 있다. 이것을 이용해 page table에 접근한다.
4. page table pointer와 page 부분을 이용해 page table element에 접근해 frame을 얻는다.
5. frame과 offset을 합쳐 physical address를 만든다.

 

 

Multi Level Paging

 virtual memory 포스팅에도 설명한 내용이니 여기서는 간단하게만 짚고 넘어간다.

multi level paging

 page table을 여러 단계로 두는 방식이다. 이 방법을 사용할 경우 하나는 필요없는 page table을 만들지 않기 때문에 memory를 많이 절약할 수 있다. translation은 virtual memory를 여러 개로 쪼개어서 각각의 page table에 접근한다.

 

 

Inverted Page Table

 앞서 살펴본 page table은 크기가 너무 크다. multi level을 사용하더라도 마찬가지이다. 사용하지 않는 page들이 너무 많기 때문이다. 이를 해결하기 위해 inverted page table을 사용한다.

 

inverted page table

 inverted page table은 logical page에 대한 정보 대신 physical page에 대한 정보를 가지고 있다. inverted page table은 physical memory와 같은 크기를 가지며, 각각의 element는 physical page frame과 대응된다. 각각의 element는 다음과 같은 정보를 가진다.

• 해당 page를 가지는 process id
• physical page frame의 virtual address

 

 translation은 다음과 같은 과정으로 이루어진다.

1. processor가 virtual address를 생성하면 MMU가 process id, page number, offset으로 나눈다.
2. pid에 해당하는 page table에서 page number에 해당하는 element를 찾는다.
3. 이 때, 찾은 element의 index i가 곧 page frame index가 된다.
   • inverted page table에서 모든 page table element는 physical page frame과 대응되기 때문이다.

 

장단점

• page table의 크기가 줄기 때문에 메모리 소모량이 적어진다.

 

• translation을 위해 모든 page table을 탐색해야 하므로 탐색 시간이 길어진다.
  • 이를 해결하기 위해 hash 등의 방법을 사용할 수 있다. 그러나 이 경우 hash를 위해 memory에 2번 접근하기 때문에 그만한 overhead가 존재한다.
  • 다른 해결 방법으로 TLB를 사용한다.
• sharing을 구현하기 까다롭다.

 

 

 

Translation의 효율 증대 방안

TLB, Translation Lookaside Buffer

 page table은 memory에 있기 때문에, 하나의 memory access를 위해 memory에 2번 접근해야 한다. 이를 위해 TLB를 사용한다.

 TLB는 recent virtual address translation을 가지고 있는 cache이다. 최근의 translation 정보를 가지고 있기 때문에 TLB hit라면 해당 translation 결과를 바로 가져다 쓰면 되고, TLB miss라면 page table에 접근한다.

 TLB의 각 element는 다음과 같은 정보를 가지고 있다.

• virtual page number
• physical page frame number
• access permission

 

Translation Flow with TLB

 

TLB flow chart

 TLB를 사용했을 때 translation은 다음과 같이 이루어진다. virtual memory 포스팅에도 작성되어 있으며, 여기서는 page frame에 대한 내용만 조금 추가되어 있고 대부분 거의 유사한 내용이다. 

1. processor가 virtual address를 생성하면 virtual adddress를 TLBT, TLBI, offset으로 자른 후 TLB를 살펴본다. 
   • TLB hit이면 page frame number와 offset을 합쳐 physical address를 만든다.
   • TLB miss라면 page table을 살핀다.
     • Page hit라면 page table로부터 page frame을 받아온다.
     • Page miss라면 page fault exception이 발생하고, page fault handler가 disk로부터 memory로 page를 가져온다. (이 과정에서 victim page를 선정하고, dirty page면 disk에 쓰고, disk에서 page를 memory로 가져오는 과정을 거친다.)
     • 이렇게 추출한 page frame number와 offset을 합쳐 physical address를 만든다.
   • translation이 끝나면 TLB에 해당 translation 결과를 쓴다. 필요 시 eviction한다.
2. 만든 physical address를 cache나 memory에게 요청한다.
3. cache나 memory가 받은 physical address에 있는 데이터를 processor로 보낸다.

 

TLB의 성능

 TLB를 사용함으로써 address translation cost는 다음과 같이 줄게 된다.

 

TLB Translation Cost = [TLB lookup cost] + [TLB miss] * [Page Table Lookup Cost]

 

 TLB translation cost는 TLB lookup cost와 직결되기 때문에 TLB lookup cost가 작아야만 TLB의 존재 이유가 생긴다. 따라서 TLB는 CPU의 바로 옆인 L1 cache에 위치한다. 또한 lookup cost를 줄이기 위해 fully associative하게 만들어져 있다.

 

 

Virtually Addressed Cache

 virtually addressed cache는 physical address 대신 virtual address로 indexing을 하는 cache이며, cache를 이용해 성능을 향상시킬 수 있다. 이 방법을 사용하면 virtual address에서 physical address로의 translation을 생략할 수 있기 때문에 꽤 큰 성능 향상을 도모할 수 있다. 일반적으로는 translation과 virtually addressed cache를 synchronous하게 동시에 사용한다.

virtually addressed cache

 

Aliasing

 aliasing은 다른 virtual address가 같은 physical address를 가리키는 상황을 말한다. 다른 processor들의 cache가 서로의 존재를 모르기 때문에, aliasing이 발생하면 cache coherence가 유지되지 않는다. 

 이를 막기 위해서는 같은 physical address를 가리키는 cache들을 동시에 update하는 방식을 취하며, 아래 방식으로 이루어진다.

• virtually addressed cache와 TLB translation이 동시에 일어나게 한다.
• TLB에서 얻은 physical address를 모든 virtually addressed cache에 검색해 해당 physical address를 가리키는 cache가 있다면 이를 update한다.

 

 

Superpage

 TLB는 fully associative cache이기 때문에 크기를 키우기 어렵다. TLB의 하나의 element가 하나의 page만 가리킬 수 있기 때문에 [TLB size] * [page size]만큼의 memory만 기리킬 수 있다. 보통 page size가 4KB, TLB size가 128KB, memory는 16GB임을 감안하면 너무 적은 수치이다. 이러한 상황에서 TLB hit rate를 올리기 위해 사용하는 방법이 superpage이다. 

 superpage는 page size를 키우는 방법인데, page size가 커지면 TLB가 가리키는 page frame의 크기가 커져 더 많은 page frame을 가리키기 때문에 hit rate가 상승한다.

 

 

TLB Consistency

 multi processor 환경에서 cache를 사용할 때는 항상 cache coherence를 유지해야 한다. (multiprocessor synchronization 포스팅에서 cache coherence에 대해 다루었다.) TLB도 page table의 cache이기 때문에 coherence를 유지해야 한다.

 

TLB Shootdown

 TLB도 aliasing처럼 서로 다른 TLB가 같은 주소에 대한 element를 가질 수 있다. 이렇게 되면 page table element가 변경될 때마다 해당 page table element를 가리키는 TLB를 모두 버린다.

 이 때, OS는 TLB가 어떤 page를 가리키는지 모르고 TLB는 해당 TLB를 가진 processor만이 수정할 수 있기 때문에 OS는 모든 processor에게 모든 TLB를 지우라는 interrupt를 날려야 한다. 당연히 모든 TLB가 사라지기에 cold miss가 발생한다.

 

 TLB Coherence

 context switch가 일어날 경우, TLB는 이전 process에 해당하는 정보를 가지고 있기에 context switch 이후에는 기존 TLB의 값들이 필요없어진다. 이를 해결하기 위해 TLB를 삭제하는 방법, TLB를 재사용하는 방법 2가지가 있다.

 TLB를 삭제하는 방식은 간단하지만 overhead가 너무 크다.

 때문에 TLB를 재사용하는 방식을 취한다. TLB에 process id를 추가하고, TLB hit/miss 여부를 조사할 때 PID도 비교해서 TLB hit를 판단하는 것이다. 이렇게 하면 context switch가 일어나더라도 기존 TLB를 삭제하지 않고, 만약 또 다시 context switch가 일어나는 경우 cold miss를 줄일 수 있다는 장점이 있다.

 

 

 

 

 

잘못된 내용이나 오탈자에 대한 지적, 질문 등은 언제나 환영합니다.