운영체제 9편 - 메모리

이 글은 학부 운영체제 수업을 듣고 정리한 글입니다.
맥락없이 운영체제에 대한 내용들이 불쑥 등장하니 양해부탁드립니다.

이번 편은 메모리에 대한 내용입니다.

서론

우리 핸드폰에서 가장 비싼 부품이 무엇일까? 첫번째는 CPU, 두번째로는 LCD 패널, 그 다음이 메모리다. CPU는 가장 비싸다. 이를 놀게만들수는 없다. 결국 범용 컴퓨터의 목적은 CPU 활용률(utilization)을 극대화 하는게 중요하다.

이전의 작성한 운영체제편들에서 사용자에게 빠른 응답을 제공하기위한 멀티프로그래밍도 알아보았고 이를 위해 스케줄링하는 것도 알게되었다. 여러 프로그램이 concurrent하게 돌아가다 보니 동기화 라는 것도 알게되었다.

하지만 여러 프로그램이 동시에 메모리에 적재되어 실행되면서 메모리를 공유해야할 필요성이 생겼다. 메모리가 아무리 커진다고 하더라도 메모리관리는 필요하다. 여러개의 프로세스가 동시에 뜰 수 있기 때문이다. 어떻게 이를 관리할 수 있을까?

주소공간(Address space)

주소공간은 프로세스에서 참조할 수 있는 주소들의 범위이다. 주소공간은 프로세스와 1대1로 매핑되며 스레드들은 이를 공유한다.

주소공간의 크기는 CPU의 address bus에 의존한다. Address Bus에 대해 다룬 글이 있으니 참고하면 좋겠다.

예를들어 address bus가 32bit width이면 주소자체의 개수는 2³²개 있고 byte-addressable 이면 주소공간의 크기는 4GB가 되겠다. 만약 word-addressable이고 word가 16bit이면 주소공간의 크기는 8GB가 된다.
byte-addressable 이라는 것은 최소로 읽어낼 수 있는 단위가 byte인 것이다. 즉 모든 byte 단위들로 주소를 가지고 있는 것이다.
word-addressable이고 word가 16bit이라면 char 타입을 저장할때 나머지 8bit는 비어있게된다. 이런면에서 memory 효율화 차이가 있지만 이런 내용들은 컴파일러가 적절하게 최적화할 수 있다.
요즘은 프로세서들은 byte-addressable 하지않다. 대부분 work-addressable 하므로 한번 읽으면 4byte를 한번에 읽는다.

또 메모리는 Memory alignment 라고하여, 메모리 주소로 접근할 때 word size에 대해서 align하는 것으로 제한한다. 즉 word size가 4byte이고 byte-addressable이라면 메모리 주소로 접근할때 반드시 4의 배수로 접근해야 한다는 것이다. 그렇지 않으면 trap이 발생한다.

물리주소와 가상주소

물리주소라는 것은 메모리를 접근할 때 사용되는 주소다. Address Bus로 메모리에 주소가 들어갈때는 다 물리주소로 들어간다. 메모리 자체는 수동적인 device이다. 주소가 들어오면 그냥 주소를 읽어들이는 것 뿐이다.
가상주소는 프로세스 관점에서 사용하는 주소이다. 우리가 이미 사용하고 있는 변수접근도 이미 가상주소를 사용하여 접근하고 있다. Logical한 주소공간이기 때문에 주소공간을 의미있는 단위로 나누어 사용할 수 있다.
이전에 다루었던 내용에서 프로세스의 메모리구조를 보았을때 text segment, data segment, stack 등으로 공간을 나누었었다. 이들은 가상주소를 의미있는 단위로 나누어 사용한 것 뿐이다.

Compile & Link time에서의 주소

Compile과 linking에서 다양한 논리주소들이 생성된다. Compiler는 symbol table을 만드는 것이 핵심이다. 예를 들면, 프로그래머들은 변수로 전부 이해할 수 있는 이름을 사용한다. int a, b에서 a, b 모두 symbol이다. 각 symbol이 가리키고 있는 메모리 주소를 map으로 가지고있는게 symbol table이다.
다만 이 symbol table에서의 주소는 relative한 주소이다. 오직 Object file 안에서만 유효한 주소이다. 주소는 0부터 시작하고 이후 relocate할 수 있다. 상대적인 위치만 정해놓은 것이다.
Linking을 하게되면 하나의 바이너리가 만들어진다. Linker가 하는것은 address resolution이다. 앞에서 만들어낸 relative한 주소를 relative하지 않게 만든다. 모든 Object 파일들과 라이브러리들을 묶어서 symbol table에 의존적이지 않은 주소를 만들어 낸다. 주소를 0부터 쫙 매긴다. 각각 들어가는 모듈들을 시작하는 주소에 상대적으로 다 더해줘서 주소를 모두 만들어낸다. 여기서 만들어지는게 가상주소이다. 이것이 프로그램이 사용하는 주소가 된다.
프로그램의 수행을 위해 Loader는 executable을 메모리로 load 한다. 메모리에 올라가면 그때 또 프로그램이 가지고있는 주소와 물리주소간에 연결을 시켜주어야 한다. 이를 위해 binding을 한다. 프로그램이 가지고 있는 주소와 물리주소를 연결시킨다.
Load가 다시 진행되면 똑같은 executable이 다른 물리주소로 가게될 수 있다. 그리고 런타임시에도 밑에서 자세히 보겠지만 swapping과 paging을 통해 물리메모리에서 내려갔다가 올라갈때 주소가 바뀔 수 있다.

이야기가 길어졌는데 결국 하고자 하는 이야기는 Compile time, Link time, load 과정에서의 주소와, runtime 할때의 주소가 따로 있다는 것이다. General purpose 한 운영체제에서는 보통 이런방법을 사용한다.

초창기 컴퓨터에서의 주소관리

초기의 시스템에서는 아주 간단한 주소변환만 했다.
주소에 base register에 있는 값을 더한다. 그리고 이 값을 바로 물리주소로 사용했다. base register를 프로그램마다 바꾸어 주는 방식이다. 즉, 각 시작번지를 바꾸는 방법이다.

이렇게 하는방법은 오버헤드가 적었다. 그냥 base register에 더하기만 하면 되었다. 다만 약점도 명확했는데, 프로세스가 반드시 continuous 해야 동작했다. 즉 한덩어리로 연결이 되어있어야 한다. linear 해야한다는 의미이다.
이를 극복하기 위해 virtual memory개념을 만들고 이를 translation을 하는 방법을 생각해냈다. 지금은 전부 이런 memory translation 을 전제로 하고있다. 가상주소를 변환하고 그것을 가지고 물리메모리에 접근한다.
리눅스 Kernel이 virtual translation과 physical memory 주소로의 변환을 모두 다룬다.

여기에 DMA가 붙으면 어디에 붙어야할까?
DMA는 I/O를 대신해준다. I/O 데이터를 읽어온 것을 메모리에 써주고, 또는 I/O에 쓸 것을 메모리에서 가져와서 대신 write 해준다.
DMA를 위 그림에 넣으려한다. DMA가 받아들이는 주소는 Virtual Address일까 Physical Address일까?
보통은 DMA는 Physical Address를 받는다. DMA중에 Virtual 주소를 받는것도 있긴하다. 이를 DVMA라고 부른다. 다만 일반적인 General purpose PC에서의 DMA에서는 물리주소를 받는다.

MMU(Memory Management Unit)

위에서 virtual address를 physical address로 변환하기 위해서는 translation을 해야한다고 했다. 다만 이 translation 속도가 굉장히 중요하다. 잘못하면 memory 접근속도가 반으로 떨어질 수 있다. 이 성능을 높이기 위해서는 software로는 더이상은 한계가 있다는 것을 알고 하드웨어를 도입했다. 이것이 MMU(Memory Management Unit)이다.
CPU는 그냥 주소를 MMU에 보낸다. MMU는 이를 physical address로 변환한다.
MMU는 CPU 칩안에 붙어있으며, address bus에는 physical address가 실린다.

위의 구조에서 CPU 캐시는 어디에 위치할까? 캐시는 translation 하기 전에 작동한다. 그 이유는 캐시는 빨리 접근하는 것이 중요하다. 캐시 hit이 되면 이를 translate 할 필요가 없으므로 더 빠르게 값을 얻을 수 있다. 즉 캐시는 virtual address를 보고있다. 다만 virtual address는 그 유효범위가 프로세스에서만 유효하다. Context Switching이 일어나면 캐시를 전부 flush 시켜야 한다. virtual address 이기 때문에 서로 다른 프로세스가 virtual address가 같지만 physical address는 다를 수 있기 때문이다. 다만 또 어떤 디자인에서는 캐시를 physical address에 붙이는 것도 존재하여 항상 그런것은 아니다.
이 CPU 캐시는 Kernel이 flush 해주어야 한다. 이를 flush할 수 있는 instruction이 존재한다. 다만 이 또한 연구가 계속 되고있으므로 언제든 변할 수 있다.

가상메모리(Virtual Memory)

가상메모리는 실제로 존재하지 않지만 사용자에게 메모리로서 역할을 한다. 가상 메모리를 생각한 아이디어는 다음과 같다.
물리메모리를 가지고 어떻게 이를 관리할 것인가에 대해 초점이 맞추는게 아닌, virtual memory가 있다고 가정을 하고 사용자들에게 그냥 virtual memory를 가지고 마음껏 사용할 수 있도록 하자는 것이 핵심이다.
프로세스가 수행되기 위해서 프로그램의 모든 부분이 물리메모리에 있을 필요가 없다는 것이다. 결국 프로세스는 현재 실행하고있는 code/data/stack 부분만 물리메모리에 있으면 실행가능하다.

Paging

메모리 주소공간을 동일한 크기인 page 라는 단위로 나누어 관리한다. 이를 Paging 이라고 한다.
보통 1 page의 크기를 4KB로 한다. 보통 Page Frame이라고 하면 물리메모리를 고정된 크기로 나누었을때 하나의 블록을 의미한다. Page 라고 하면 보통 가상메모리의 블록을 의미한다. Frame과 Page의 크기는 동일하다. 이 둘을 잘 구분해서 이해할 수 있도록 하자.

Page가 하나의 Frame을 할당받으면 물리메모리에 위치하게 된다. Frame을 할당받지 못한 Page들은 외부 저장장치(Backing Store)에 저장된다. Backing Store도 Page, Frame과 같은 크기로 나누어져 있다.

CPU가 관리하는 모든 주소는 두 부분으로 나뉜다. page 번호와 page offset이다.
page 번호는 각 프로세스가 가진 페이지 각각에 앞에서 부터 부여된 번호이다. 예를들어 1번 프로세스는 0부터 63번까지의 페이지를 가지고 있다.
Page offset은 각 페이지 안에서의 내부주소를 가리킨다. offset은 page가 4KB이니 0부터 4095까지 존재한다.
Page 번호와 offset으로 모든 주소를 표현할 수 있다. 예를들어 1번 프로세스의 12번 페이지(page 번호)의 34번째(offset) 데이터로 표현할 수 있다.

잘 이해했는지 확인하기 위해 퀴즈를 풀어보자.

1. 128MB의 물리메모리를 4KB 단위로 페이징하려면 몇개의 frame이 필요할까?
2. 4GB의 logical address를 페이징하려고 하면 총 몇개의 page가 필요한가? (페이지 크기는 4KB)
3. page 크기가 4KB일때, 한 페이지의 메모리를 access 하기 위한 주소 bit는 몇 bit인가?

해답은 다음과 같다.

1. 2²⁷ / 2¹² = 2¹⁵개 (약 32,000개)
2. 2³² / 2¹² = 2²⁰개 (약 1,000,000개)
3. 4KB 크기이므로 12bit이다.

가상메모리 mapping

실제 물리 메모리에는 이렇게 그림처럼 올라간다. 어떤 조합으로 올라갈것인가는 운영체제의 몫이다.
예를들면 위 그림에서 P3에 있는 page를 하나 더 물리메모리에 올리고싶다고 하자. 근데 현재는 물리메모리가 모두 사용중이다. 새로운 page를 올리기 위해 이미 올라가있던 Frame을 빼서 외부 저장장치에 임시로 저장해놓는다. 나중에 이 Page가 다시 필요하면 다시 가져와서 다시 메모리에 넣는다. 그리고 이를 반복한다.

서로 다른시간 t1, t2가 있다고 했을때 동일한 page frame에 대하여 t1과 t2에 특정 page frame에는 서로 다른 virtual page가 올라갈 수 있다.

Page Table

Page Table은 virtual memory와 physical memory 사이의 매핑이다. 각 프로세스의 페이지 정보를 저장한다. 그러므로 프로세스마다 하나의 page table을 가진다.
테이블의 인덱스는 페이지 번호이다. table 내용으로는 물리 frame의 시작주소가 있다. 이 시작주소와 페이지 offset을 결합하여 원하는 데이터가 있는 물리 메모리 주소를 알 수 있다.
page 크기가 4KB이면 offset이 12bit이므로 page(20 bit) + offset(12 bit)가 된다.
그러므로 물리 frame 번호만 변환하고 뒤에 offset을 붙이면 물리메모리 주소를 알 수 있다.

Page table은 Kernel이 관리하고 있는 data structure이다. Page table은 물리메모리 상에 저장이 되어있다. Page-table base register가 현재 수행중인 프로세스의 물리메모리 내 page table의 위치를 가리키고 있다. Context Switching이 일어나면 이 register의 값을 PCB에 저장한다. page table의 위치를 저장하는 것이다. 새로운 프로세스가 스케줄링되면 Kernel이 register의 값을 변경해주어야 한다.

결국 이를 위해서는 Kernel이 프로세스의 page table 위치를 알고있어야하는데, Page Table은 프로세스가 맨 처음 만들어질때 생성된다.

그림의 p는 페이지의 인덱스이며 page 번호이다. 이 page가 매핑된 값을 앞에 20bit에 넣고 offset은 그대로 뒤에 붙여준다. 그러면 정확한 물리메모리의 address가 나온다.
이 작업을 MMU가 한다. MMU는 하드웨어이다. 왜 이걸 MMU가 할까?
page table은 Kernel data structure로 memory에 있다. memory에 있다는 것은 page table에 접근할때 memory 접근 후, 이를 읽어낸 후 다시 이를 보고 physical 주소로 변환해야한다. 그러면 메모리 접근을 10번하려면 20번을 메모리 접근해야한다. 당연 성능이 좋지않다. 그래서 이를 하드웨어로 하자는 이야기로 MMU를 사용한다. MMU는 밑에서 다시 볼 것이다.

Page Table Entry

page table 내부를 살펴보자. page table을 통해서 메모리 접근이 다 일어나므로 매우 중요하다. page 별로 메모리에 올리고 내리고 하는게 가능하다. 이를 위해 page table이 어떻게 구현되어있는지가 핵심적이다.
Page Table Entry란 Page table에 있는 하나의 record-page를 의미한다. 간단하게 PTE라고 한다. PTE는 page에 대한 접근이 있었는지, 사용이 되는지의 여부, page가 바뀌었는지의 여부를 저장할 수 있다.
PTE의 대략적인 필드내용은 다음과 같다.

• Page base Address
  해당 페이지에 할당된 프레임의 시작주소이다. 이를 통해 물리메모리에 접근할 수 있다.
• Flag bits
  Accessed bit: 페이지에 대한 접근이 있었는지에 대한 bit
  Dirty bit: 페이지 내용의 변경이 있었는지에 대한 bit
  Present bit: 현재 페이지에 할당된 Frame이 있는지에 대한 bit
  Read/Write bit: 읽기/쓰기에 대한 권한표시 bit

실제로 프로세스가 작업하는 페이지는 물리메모리에 없을 수 있다. 이를 해결하기 위해 Present bit이 필요하다.
Dirty bit은 밑에서 볼 내용이지만 page가 page-out 되고, 다시 frame을 할당받았을때 dirty bit가 마킹이 안되어있으면 이전과 같은내용으로 다시 page-out이 될 때 I/O로 다시 써줄 필요가 없으므로 성능상 이득을 볼 수 있다.

Segmentaion fault의 발생은 언제 일어날까? 예를들어 *p = 1의 코드가 있는데 p가 NULL, 즉 0인 경우에 발생한다. 프로세스가 만들어 질때 첫번째 page는 읽어서도 안되고 써서도 안된다고 표시를 한다. 정확히는 fork 할때 page table도 copy를 하므로 똑같이 page 0번의 PTE에 Read/Write bit을 마킹을 해준다. 그래서 NULL pointer에 접근할때 0번의 PTE에 접근시 trap이 발생하여 segmentation fault가 발생한다.

이 Page table과 PTE를 보면 예전 프로세스에서 말했던 프로세스는 protection domain이라는 것을 이해할 수 있다. 프로세스 A는 프로세스 B의 page table에 접근할 수 없기 때문이다. 이는 MMU가 접근을 시켜주지 않는다. 다른 프로세스의 메모리에 접근할 수 없다는 것에 대해 이런 배경이 숨겨져 있다.

TLB

Computer Science의 magic 2가지가 있다. 하나는 caching이고 또 하나는 indirection이다.
성능이 안나오면 caching을 하는 경우가 많다. 그리고 뭐든지 복잡하면 layering을 한다. 그러므로 항상 computer science를 공부할때에는 여기서는 어떤 indirection을 사용하고 있는지 보면 도움이 될때가 많다.
캐싱을 사용하지 않으면 페이징 방법에서는 데이터로의 접근이 항상 두번의 메모리 접근을 거쳐야 한다. Page table에 한번 그리고 물리메모리에 한번이다. 이것이 메모리 접근 속도를 떨어뜨린다.
이를 극복하기 위해 MMU도 caching을 사용한다. 이것이 TLB(Translation Look-aside Buffers)이다.

Page table을 이용해 변환된 주소를 TLB에 저장해둔다. 그리고 다음 접근시에 TLB에 hit이 된다면 TLB에 저장되어있는 값을 이용하여 빠르게 변환된 주소를 얻는다. TLB는 register이기 때문에 빠른 수행이 가능하다. TLB hit ratio를 높여야 전체적인 메모리 접근속도를 높일 수 있다. miss가 나면 원래처럼 page table을 물리메모리에서 다시 조회해야한다.

TLB entry는 보통 16개에서 512개 정도이다. 이미 우리가 사용하는 PC들은 모두 MMU가 붙어있다.
TLB를 이용한 paging을 그림으로 나타내면 다음과 같다.

MultiLevel Page Table

Page Table의 크기는 얼마일까? PTE 하나는 보통 4 byte의 크기를 가진다. 그러므로 page table의 크기는 4MB이다. 크기가 작다고 생각할 수 있겠지만 프로세스가 100개라면 400MB가 된다.
우리가 만든 프로그램이 있다고 해보자. 이 프로그램에서 사용하는 page의 개수는 몇개일까?
segment별로 생각해보자. stack은 보통 프로그램에서 32KB를 넘어가지를 않는다. text segment는 코드가 1만 라인이라면 Page 10개를 넘지 못한다. text segment도 40KB를 넘기기 힘들다는 것이다. data segment도 보통은 작은 크기를 가진다. 결국 우리가 만든 프로그램은 PTE(page table entry)가 100개를 넘는 프로그램을 만들기 힘들다는 것이다.

Page table의 PTE는 총 2²⁰개이다. 약 100만개이다. 그러면 보통 프로그램에서는 이 100만개의 PTE중에 100개를 사용한다는 것은 비율상 0.01%개의 PTE만 사용된다는 것이다. Kernel 메모리 낭비가 굉장히 심하다.

이를 어떻게 메모리 사용량을 줄일수 있을까 하여 Multi-Level Page Table이 나오게 되었다. Intel은 거의다 2-level page table을 사용한다. page table 자체도 paging된 공간에 저장된다.

2-Level Page Table

Outer page table을 한개 더 두어서 이들이 page table들을 가르키도록 한다. 여기서 말한 outer page table은 level-1 page table이 된다.
예를들어, 20-bit를 차지하고 있는 page number를 다시 아래와 같이 나눈다.
10-bit page 번호 + 10-bit page 주소
결국 32bit 주소의 모양은 다음과 같아진다.

그러면 level-1 page table에는 1024개의 entry가 들어간다. 이 각각의 entry가 level-2 page table을 가리키는 구조이다. 이 level-2 page table에도 1024개의 entry가 존재하게 된다.

결국 level-1 page table entry 중 1개가 mapping 하고 있는 virtual memory의 크기는 4MB이다.
만약 page table entry의 4개만 사용하고있는 프로세스는 page table에 얼마의 메모리가 필요할까?
level-1 page table은 4KB가 필요하고, level-2 page table은 3개를 사용하고 있다고 가정하자. 최대 4개가 사용될 수 있지만, 2개의 page는 동일한 level-2 page table 에 있다고 하자.
그러면 총 4개의 page table이 사용되므로 16KB가 필요하다.

Page Walk

MMU가 page table에 접근하는 것을 Page Walk라는 표현을 사용한다(Table Walk라고도 부른다). 처음에 outer page table을 보고 그리고 level-2 page table을 보고 그 다음 물리메모리 주소를 찾는다. 다음은 2-Level page table 에서의 page walk 예시다.

page walk는 모든 메모리에 접근할때마다 발생한다.
만약 3-Level page table을 도입하면 어떻게될까? 이는 page size들을 더 줄일 수 있겠지만 그만큼 성능에 대한 tradeoff가 존재한다. page walk가 더 길어지기 때문이다.
보통 시스템은 2-level 까지만 하는 경우가 많은데 이는 3-level 부터는 성능이 개선되는게 별로 크지 않기때문이라고 한다.

Inverted Page

64bit 주소공간을 가진 시스템에서는 multi-level paging을 위한 정보의 크기는 32bit에 비해 현격하게 증가되어 문제가 있었다. 그래서 새로 연구된 paging 방법이 있는데 이것이 이번에 소개할 Inverted Page이다. 다만 이 방법은 현재는 거의 사용되고 있지는 않으므로 참고하는 정도로만 보면 좋겠다.

64bit 주소공간에 모든 물리메모리가 매핑되어 있지는 않지만, 이의 반대로 모든 물리메모리는 가상메모리에 전부 매핑이 되어있을 확률이 높다는 것에서 출발한다.
원래는 page table이 virtual page 번호가 들어오면 이에 매핑되는 physical page 번호를 반환하는 거였다면 이를 반대로 physical page 번호가 들어오면 virtual page 번호를 반환하자는 것이 아이디어다.
결국 physical page 번호를 가지고 page table을 만드는 것이다.
page table entry로는 process id와 virtual page 번호를 넣는다. 즉 pid와 virtual address의 조합으로 page id를 만든다.

이렇게하면 얻을 수 있는 장점이 시스템 전체에서 하나의 page table만 사용하면 된다.
문제는 page table을 검사하는데 너무 오랜 시간이 걸렸다. 테이블 검색을 전체를 검색하지말고 Hash table을 사용하여 개선하기도 하지만 이또한 한계가 존재한다.
그러하여 이런 방식보다는 virtual page를 찾고 TLB와 함께 사용하여 성능을 개선한 기존 방식을 많이 사용한다.

Demand Paging

Demand Paging은 프로세스의 실행을 위한 모든 page를 메모리에 올리지 않고, 필요한 page의 요청이 발생할 때 메모리에 올리는 paging 기법이다.
PTE의 valid bit을 활용하여 한 프로세스에 필요한 page를 memory와 secondary storage 간에 이동을 시킨다. 이런 방법을 통해 물리메모리 구성의 시간이 줄어든다. 그리고 프로세스 전체 이미지를 메모리에 올리지 않기때문에 실제 필요한 물리메모리의 양을 줄일 수 있다.

page table에서 참조하려는 page가 valid한 경우에는 이 page가 실제 물리메모리에 frame이 할당되어 있기 때문에 정상적인 참조가 가능하다. 다만 참조하려는 page가 invalid하다면 이 page가 실제 물리메모리에 존재하지 않으므로 이에 대한 처리가 필요한데 이것을 Page Fault라고 한다.

Page Fault

프로세스가 page를 참조하였을때 해당 page가 할당받은 frame이 없을경우 page fault가 발생한다. 그러면 page fault handler를 수행한다.
page fault handler는 새로운 page frame을 할당받는다. 그리고 backing store에서 해당 page의 내용을 frame에 불러들인다. 그리고 page table을 재구성한 후 프로세스의 작업을 재개한다.
다음 그림을 보자.

위 그림의 1번에서 페이지 참조를 하면 page fault가 일어난다. page fault는 trap이다.
그러면 disk로 부터 해당 page를 읽고 이를 물리메모리에 할당한다. page table을 적절하게 마킹을 표시해주고 재개한다.

프로세스가 맨 처음 실행될때는 어떤 일이 일어날까?
프로세스가 처음 실행을 시작하면 page fault가 일어난다. 처음에는 page가 물리메모리에 frame이 할당되어 있지 않기때문이다. 그래서 맨처음에 제일먼저 page fault가 일어난다.
그러면 page fault handler가 disk에서 해당 page의 내용을 다시 frame에 불러오고 이를 재개한다.

만약에 우리가 local variable을 접근하고 있다고하자. local variable은 stack에 존재한다. 하지만 맨 처음에는 이 접근에 page fault가 발생한다. 그럼 이 또한 disk 에서 읽어와야할까?
text segment와 data segment는 disk에서 읽어오는데 stack은 읽어올 내용이 없다. stack은 프로세스가 수행을 시작하고 프로세스가 끝나면 사라져야한다. 그러므로 stack 같은 경우에는 disk에 접근하는 것을 생략하고 frame만 할당한 후 page table을 업데이트하고 수행을 재개한다.

그러면 맨처음 page fault가 일어날때 어떻게 disk에서 이 위치를 알고 가져올 수 있을까?
Loader가 프로그램을 시작할때 executable file을 읽고 disk에 address space를 적절하게 build 해준다. executable file 자체가 text segment와 data segment의 page file이 되도록 하는 시스템도 존재한다.

page fault는 비싼작업이다. 일단 프로세스는 page fault가 발생하면 멈추어야한다. page fault는 trap으로 동작하고 할당가능한 frame을 찾고 필요하다면 disk에 접근하여 page file을 가져오고 다시 page table을 mapping 해주어야한다. frame을 찾는 것은 micro second 단위이지만 disk 접근은 milli second 단위이다. page fault가 최대한 발생하지 않도록 Kernel에서도 많은 노력을 하고있다.

프로세스의 실행시간중 page fault를 처리하는 시간이 execution보다 긴 상황을 Thrashing이 일어났다고 표현한다. 이런 Thrashing 현상을 줄이기 위해 여러 노력을 하고있는데 그중 하나가 working set model이 있다.

Working Set

메모리의 Locality 속성을 기반으로 프로세스가 일정시간동안 원활하게 수행되기 위해서 한꺼번에 메모리에 올라와 있어야 하는 page set을 working set이라고 한다. 특정 time window 동안에 접근된 page 들의 집합이 working set에 적용될 수 있다.
Kernel은 프로세스의 working set을 계산하여 이를 프로세스에게 제공하여 page fault를 최소화한다. working set에 포함된 page 수는 시스템 전반에 걸쳐 사용가능한 총 page 수에 따라 증가되기도 감소하기도 한다. 또 working set을 프로그램이 시작하면 바로 할당하면서 맨처음 수행시 page fault가 나지않도록 text, data segment에 해당하는 frame을 미리 할당하는 전략도 존재한다.

Page Replacement

멀티 프로그래밍 시스템에서 user process가 증가하면 모든 user process가 사용하는 page 수보다 물리메모리의 frame이 부족한 상황이 발생할 수 있다. 이럴때에는 page 교체(replacement)를 진행해야 한다. page fault를 할 때 page replacement가 추가된다.
물리메모리에 위치한 page를 disk에 저장한다. 그 frame에는 virtual page의 내용이 저장되어 있는데 이 값을 disk에 쓰고, 이 frame에 다른 virtual page를 불러와 교체한다. 이를 Page Replacement라고 한다.
다음은 page replacement 과정을 간략하게 설명한 내용이다.

1. Disk에서 요구된 page의 위치를 찾는다.
2. 물리메모리에서 free frame을 찾는다. 만약 free frame이 있다면 이를 사용하고, 없다면 page replacement 알고리즘을 사용하여 교체할 frame(victim frame)을 선택한다. 교체할 frame을 disk에 저장하고 page table, frame table을 변경한다.
3. 요구된 page를 free frame으로 읽어들이고 해당 page table, frame table을 적절하게 변경한다.
4. user process를 재개한다.

비어있는 frame이 존재하지 않는다면 어떤 frame을 교체할지 적절하게 알고리즘으로 판단하여 victim을 정한다. 그리고 이 victim을 disk에 write하고 page table을 변경한다. 이때 invalid bit(present bit)를 설정한다. 이를 page out 되었다고 표현한다.

user process가 page out된 page에 다시 접근하면 page fault가 발생한다. 이 말은 physical address binding이 runtime에 일어난다는 증거이다.
Kernel은 page fault가 날때마다 page table 업데이트를 2번 해주어야한다. victim은 page out하고 이 victim process의 page table의 invalid bit 세팅하고, 그리고 page-in 된 프로세스의 page table도 수정해야한다.

Page Replacement Algorithms

Page Replacement가 필요할 때 어떻게 교체할 페이지를 고를까?
이는 여러 알고리즘이 존재하는데 결국 핵심적인 내용은 이 알고리즘들은 모두 Page Replacement에 의한 I/O 작업 수행 횟수를 최대한 줄이려는 목적을 가지고 있으며, 적합한 알고리즘의 사용은 시스템의 성능을 크게 좌우하는 요소이다. I/O 작업은 매우 큰 비용을 지불해야 하기 때문이다.

여러 알고리즘이 존재하고 이들은 매우 간단하게 몇가지만 알아볼 것이다.
먼저 가장 목표로 해야되는 것은 앞으로 가장 오랫동안 사용되지 않을 page를 교체해야한다. 그렇게 해야 가장 낮은 page fault 발생빈도를 가질 수 있다. 다만 미래에 어떤 page가 사용되지 않을지는 알수가 없다.

FIFO 알고리즘

그냥 먼저 frame이 할당된 page를 교체한다.
가장 단순한 알고리즘이며 FIFO 큐를 이용해 구현가능하다.

NRU 알고리즘

NRU(Not Recently Used) 알고리즘은 이름 그대로 최근에 사용하지 않은 페이지를 교체하는 방식이다.
각 page마다 reference bit와 modified bit를 둔다. 이 bit들의 설정은 MMU가 한다.
reference bit는 최초로 frame에 로드되었을때 그리고 참조되었을때 bit를 1로 설정한다. 그리고 주기적으로 0으로 리셋한다.
modified bit은 최초로 frame에 로드될때는 0으로 설정하고 이후에 page의 내용이 변경되었을때 1로 설정한다.
그래서 page replacement가 필요한 시점에 다음 순서대로 rough 하게 교체대상을 찾는다.

1. reference bit = 0, modified bit = 0
2. reference bit = 1, modified bit = 0
3. reference bit = 0, modified bit = 1
4. reference bit = 1, modified bit = 1

LRU 알고리즘

LRU(Least Recently Used) 알고리즘은 가장 오랜시간 참조되지 않은 페이지를 교체하는 방식이다.
이는 Page의 locality를 고려하고 가장 이상적인 알고리즘에 근접해있어 가장 많이 사용하는 방법이다.
Counter를 사용하여 참조된 시간을 기록하는 방식으로 구현하거나, bit와 Queue를 사용하여 구현한다.

Swapping

Page Replacement, Page out은 4KB 짜리 page를 disk로 내보내는 것이다. 하지만 물리메모리가 부족한 상황에서는 page를 하나씩 내보내는 것으로는 부족하다. 이때에는 특정 프로세스 전체를 통째로 내려야한다. 이를 Swapping이라고 한다.
Swap 대상이 된 프로세스 전체를 secondary storage로 보낸다.
이렇게 page out이나 swapping에 사용되는 secondary storage의 영역을 swap 영역이라고 부른다.
OS를 설치할때 맨처음 disk에 대해 swap 영역의 크기를 물어보는 부분이 나올때가 있다. 이 부분은 처음에 OS설치시 file system이 이 영역을 사용하지 않고 swap 영역으로 사용하도록 한다.

서버에서 swap이 발생했다면 이미 상황이 좋지 않은 것이다. 왜냐하면 swap이 발생하면 Thrashing이 발생할 수 밖에 없는데 CPU가 굉장히 바쁘다. 한 프로세스가 사용하는 모든 page들을 disk로 내리고, 다른 프로세스를 swap in 시켜주어야 하기 때문이다.

그러면 이를 방지하기 위해서는 어떻게 해야할까?
현실적으로는 물리 메모리의 크기를 늘리거나 프로세스 숫자를 줄여야한다.

다음은 swapping의 swap-out과 swap-in 과정을 그림으로 표현한 것이다.

Kernel Memory

Kernel Memory 영역은 어떻게 잡히는 것일까? 이또한 위에서 살펴보았던 Virtual Memory와 연관이 있는것일까?
시스템이 virtual memory를 사용한다면, Kernel 또한 virtual memory를 사용한다. Windows 같은 경우는 2GB이상을 사용한다. 이는 kernel code, kernel data, process 별 page table 등을 포함하고 이들또한 disk로 page-out 될 수 있다.
즉 virtual memory의 특정영역이 Kernel에 사용되도록 되어있다.
예를들어 32bit 주소공간을 가진 시스템에서 주소가 2GB 이상부터는 Kernel 영역이라고 정할 수 있다. 그 영역을 매핑하는 page table들은 각 PTE가 kernel page들을 가리키게 된다. 이 PTE들은 user page를 매핑할 수 없다.

page table은 프로세스마다 존재한다. context switching이 일어나면 바라보는 page table 전체가 변경된다. 하지만 전통적으로 모든 프로세스들이 공유를 하고있는 영역도 존재를 한다.
이런 영역같은 경우는 page table에 특별한 marking을 해놓아서 TLB에 캐시가 invalidate 되지 않도록 한다. 그리고 매우 critical 한 부분은 swap이 되지 않도록 설정하기도 한다. 다음의 virtual memory segment 그림을 보자.

Kernel virtual memory 영역은 kernel code와 kernel data를 포함한다.
그리고 kernel memory의 특정영역은 physical memory에 매핑이되어 모든 프로세스들이 이를 공유하기도 한다. 예를들어 모든 kernel code와 kernel data는 모든 프로세스들이 공유한다.
리눅스 또한 특정영역의 인접한 virtual page들을 인접한 physical page로 매핑하기도 한다. 이는 커널이 physical memory에서 특정 영역을 접근하는데 편하게 해준다.
예를들어 page table에 접근을 할때나 memory mapped I/O operation을 수행해야 할때 도움을 준다.

Kernel virtual memory 영역에서 또다른 영역은 프로세스 별로 데이터를 가지고있는 영역도 있는데, 이 영역에는 그 프로세스의 page table이나 그 프로세스의 context에서 실행되는 kernel stack, 다양한 데이터 자료구조들이 존재한다.

기타사항

그렇다면 Virtual Memory를 사용하지 않는 운영체제도 있을까?
일부 임베디드 시스템들은 virtual meomory를 사용하지 않는 시스템이 있다. 예를들어 자동차 하드웨어의 일부는 virtual memory를 사용하지 않는데 MMU를 사용해야하므로 비용문제등으로 사용하지 않는 경우가 있다.