8. Memory Management (1)

OS가 하는 Memory Management의 핵심 기능은 CPU가 프로그램을 수행할 수 있도록 만들어주는 것이다.

CPU가 메모리에서 data와 Instruction을 가져올 때 주소를 바탕으로 가져온다. PC, MAR에 들어있는 주소를 보고 가져옴.

그러기 위해서, OS가 메모리 측면에서 하는 일은 크게 2가지.
1. 주소를 어떻게 관리할 것인가. (본질적 기능)
2. virtual memory - 메모리 공간의 효율적 사용

프로세스가 메모리에 올라왔을때 그 프로세스의 코드를 수행하는 과정에 자신의 address space를 벗어난 영역에 접근하려 하면 막아주는 기능도 제공해야 한다.
대신 자신의 영역이 아닌 커널 영역에 접근하는 것은 System call을 통해서 간접적으로 접근할 수 있다.

 

Multistep Processing of a User Program

프로그램이 실행되기 위해서는 프로그램이 메모리에 올라와야 하는데, 어떠한 과정으로 올라오게 되는지 살펴보자.

하나의 프로그램을 구성하는 여러 개의 소스 코드에 들어있는 함수들이 서로가 서로를 호출하기 위해선 연결고리가 있어야 한다. 이 함수는 저 C 파일에 있는 함수를 호출하는 거야! 이런 거
이 연결하는 것이 링킹이다. 링커가 object 파일들을 다 모아서 하나로 묶어준다. 묶어진 게 load module이고,
링커가 만든 load module은 loader가 메모리에 탑재한다. 이때 소스 코드에서 호출한 c library 함수 등도 같이 메모리에 탑재한다. 여기서 끝이 아니라 dynamic library는 실제 호출 시에 런타임에 메모리에 올라오게 된다.

 

Address Space

이전에도 말했듯이, 프로세스는 Address space의 형태로 메모리에 올라오게 된다.

왜 Address space일까?
메모리에 탑재된 이 프로세스의 영역을 주소를 기준으로 접근하기 때문에 주소로 관리되는 영역이라고 해서 address space라고 한다.

CPU가 메모리에 접근해서 Instruction이나 data를 가져올 때 거기의 번지수를 알아야 가져올 수 있고, 그 번지수를 알기 위해서는 프로그램 코드에서 변수 명으로 선언한 이 변수 명이 이 변수가 저장된 address space 상의 주소와 매핑이 되어야 한다.

따라서 변수 명과 실제 데이터의 주소를 매핑시켜 주는 것이 메모리 관리의 중요한 역할이다.

 

변수 명과 변수가 저장된 주소를 매핑하는 것을 Binding이라고 한다.

Binding은 일어나는 시점에 따라 3가지로 나뉜다.

1. Compile time binding.

이름에서 알 수 있듯이 컴파일 타임에 바인딩이 일어나는 것이다.

초창기 컴퓨터에서는 프로세스가 하나 밖에 없을 때, 오로지 한 순간에는 하나의 프로세스만 수행될 수 있는 시스템의 OS는 컴파일 타임 바인딩을 썼다.
각 변수 명(심볼)의 주소를 매핑을 시키는 것을 컴파일할 때 했다. 컴파일 하고 나면 프로그램 코드 안에 각 변수의 주소 값이 하드 코딩이 된다.
=> 코드 안에 주소가 다 박혀있으니까 CPU는 그냥 거기에 접근하면 된다.

프로세스가 하나면 DRAM에서 커널 영역을 제외한 나머지 영역은 하나의 프로세스가 전부 사용하게 된다.
그럼 커널 영역 바로 위부터 프로세스가 올라온다 가정하고 주소를 할당하면 됨.
=> 이렇게 하면 문제가 있다. 이 프로그램을 다른 OS 환경에서 실행시키면 커널 영역의 크기가 다르기 때문에 유저 프로그램의 시작점이 달라진다. 그러면 그 프로그램은 그 기계에서 다시 컴파일을 해야 한다.

2. Load time binding.

컴파일할 때는 상대적인 주소만 코드에 박아넣는다. 이 프로세스의 address space가 0번지부터 시작한다고 가정하고 0번지에서 몇 바이트 떨어진 곳에 변수가 저장되어 있는지 상대적인 주소(offset)를 변수마다 binding.

상대적인 주소는 실제 메모리 상의 주소가 아니다. 이 프로세스가 실제 DRAM의 0번지에 올라가면 일치하겠지만 0번지에는 무조건 커널이 올라가기 때문에 그럴 수 없다. 실제 physical한 주소가 결정되는 시점은 프로세스가 실제 메모리에 올라가는 시점에 결정된다. 그때 이 프로그램이 탑재된 시작 주소를 알 수 있으니까 상대주소를 이용해서 모든 주소를 바인딩할 수 있다. 그래서 load time이라고 함.

만약 이 프로세스가 100번지부터 할당되었다고 하면, 100번지에 아까 바인딩한 상대 주소를 더해주면 그 변수의 주소를 알 수 있다.

=> 로드할 당시에 실제 주소가 결정되기 때문에 load time binding.

이렇게 되면 OS가 달라져서 커널 영역의 크기가 달라져도 상대 주소가 있으면 접근할 수 있다.
또한 여러 프로세스가 동시에 올라올 때도 적용이 가능한 방식임.

그런데 문제는 로드 타임 바인딩은 한 번 올라갔으면 주소가 결정되어 버린다. 실행되는 과정에 이 프로세스의 address space가 메모리 상에서 위치를 이동하는 것이 불가능. 이동하면 시작 주소가 바뀌기 때문에 바인딩한 주소가 다 바뀌어야 한다.

3. Execution time binding

이게 요즘에 쓰는 방식. 프로세스가 메모리 상에서 위치를 이동한다고 하더라도 아무 문제 없이 프로그램이 실행될 수 있도록 해준다.
실제로 코드 안에 물리적인 주소가 결정되지 않는다. 로드 되는 시점에도 상대적인 주소만 가지고 있다. CPU가 상대 주소를 가지고 메모리에 접근하려고 하면 실제 주소값으로 전환된다.

프로세스의 위치가 바뀌더라도 상대 주소는 바뀌지 않기 때문에 (시작을 0번지로 가정했기 때문에) 바뀐 위치에 대한 관리를 OS가 하게 되고, 시작 주소가 아까는 100번지였는데 이젠 200번지로 바뀌었어 이것만 알려주면 정상적으로 동작한다.
=> 상대 주소를 실제 물리적 주소로 바꿔주는 뭔가가 필요하다.
=> address mapping table 이라는 자료구조 필요
=> 이 테이블을 이용해서 빠르게 주소를 바꿔주는 누군가도 필요하다. 매 Instruction에 접근할 때마다 바꿔야 하기 때문에 매우 빨라야 한다. 하드웨어의 지원을 받을 수 밖에 없음.
=> 걔가 MMU( Memory Management Unit) 이다.

 

Address Mapping Table

logical한 0번지는 실제 500번지에 저장되어 있어. 또는 logical한 500번지는 실제 20000번지에 저장되어 있어.
이걸 mapping table을 보면 알 수 있다.

0번지부터 시작한다고 생각하고 바인딩한 상대 주소를 사용해서 데이터가 저장된 실제 주소를 알아내기 위해서는 필요한 정보들이 있다.

각각의 프로세스가 저장된 위치의 시작 주소와 Address space의 길이를 저장하는 변수가 필요. PCB안에는 이걸 저장하는 변수가 존재한다. 실제로 이 프로세스가 수행이 될 때 이 값들이 CPU의 레지스터에 저장이 된다. 이 레지스터들이 base와 limit.

이 프로세스가 메모리에서 내려갔다가 나중에 다시 올라오면 base 값은 바뀔 수 밖에 없다. limit은 안 바뀔 수 있지만.
=> base는 load time에 결정이 된다.

 

Logical vs Physical Address Space

• Logical address

: 논리 주소로 접근하는 주소 공간

CPU가 발생시키는 주소는 논리 주소이다. CPU가 어떤 주소로 접근해서 변수 값을 읽어오려고 할 때, CPU가 접근하려고 발생시키는 주소. 즉, CPU가 알고 있는 주소 체계를 Logical address, virtual address 라고 한다.
=> 0번지를 시작 주소로 가정해서 만들어낸 상대 주소

• Physical address

: 물리 주소로 접근하는 주소 공간

실제 DRAM의 주소 값을 가지는 주소 체계를 physical address라고 한다.

 

CPU가 어떤 변수에 접근할 때 물리적으로 메모리의 어디에 있는지는 신경쓰지말고 너가 알고 있는 Logical address를 이용해서 접근해라. 실제로 DRAM상의 주소는 OS가 관리하겠다.

CPU가 일일이 모든 물리 주소를 알 필요가 없게 된다.

이게 compile time binding과 load time binding을 사용할 때에는 이미 변수에 박혀있는 주소가 physical 주소이기 때문에 CPU가 알고 있는 Logical address와 실제 DRAM의 Physical address가 일치하게 된다.

그런데 execution time binding에서는 CPU가 알고 있는 주소인 logical address를 발생시키면 이걸 MMU가 테이블을 보고 실제 physical address로 변환해준다고 했다. 즉, CPU가 알고 있는 주소와 DRAM상의 주소가 다를 수 밖에 없음.
=> Execution time binding에서는 두 주소 체계가 분리된다.
=> 요즘 대부분의 OS는 Execution time binding을 쓰기 때문에 CPU의 주소 체계와 실제 DRAM의 주소 체계는 완전히 다르다고 생각하면 된다.

 

Memory-Management Unit(MMU)

Execution time binding을 지원하기 위해서는 실시간으로 logical address가 physical address로 바뀌어야 한다고 했다. CPU가 메모리에 접근할 때마다 주소 변환이 필요하기 때문에 매우 빨라야 해서 하드웨어의 지원을 받는다고 했다.
=> 그 하드웨어 장치가 MMU이다.

CPU가 발생시킨 Logical addres를 프로세스가 저장되어 있는 메모리의 시작 주소인 Base register 값에 더해서 실제 메모리 주소를 알아낼 수 있다.

=> 이 과정을 매우 빠르게 해주는 하드웨어가 MMU이다.

 

프로세스가 저장된 위치가 바뀌기 때문에 실제 주소는 계속해서 바뀔 것이다. 계속 바뀌는 실제 주소를 신경쓰면서  일을 하면 CPU가 일을 제대로 하지 못 할 것이다. 그렇기 때문에 CPU는 logical address만 알고 일을 하면 실제 주소로 바꿔주는 건 MMU가 해준다.

CPU는 논리 주소만 알고 실제 주소는 전혀 알지 못 한다.

 

음 그러면 결국 MMU가 하는 일은 Base register의 값에 CPU가 발생시킨 상대 주소를 더해서 리턴하는 건데, 하드웨어로 까지 구울 필요가 있었을까??

=> 이건 뒤에 나올 페이징 기법을 알게 되면 단순한 덧셈으로 이뤄지는 건 아니라는 것을 알게 될 것이다.

---

일단 한 번 address space가 메모리에 올라가면 그게 바뀔 일이 뭐가 있을까?

지금까지 알고 있는 지식으로만 대답을 준다면, 새로운 프로세스가 올라올 메모리 공간이 부족하면 Medium term scheduler가 swap을 하게 된다. 이때 주로 suspend된 프로세스가 swap out이 된다고 했다. 쫒겨난 프로세스가 나중에 suspend가 해제가 되어서 실행되어야 하는 시점에 메모리에 올라오게 되는데, 전에 이 프로세스가 있던 주소에 정확히 다시 올라온다는 것을 보장할 수가 없다.

결국 한 번 프로세스가 올라오면 끝까지 그 자리를 지킨다는 보장이 없다. 그렇기 때문에 Execution time binding을 해야 한다. CPU 너는 logical address를 이용해서만 접근해, 실제 주소로 바꾸는 건 MMU가 할 거니까.
즉, 스왑이 동작하는 OS에서는 Execution time binding을 써야 한다. 쓰지 않고는 변화하는 주소 체계를 따라다닐 수가 없음.

Swap된 프로세스의 address space가 저장될 공간을 Backing store라고 한다. 이걸 우린 그냥 디스크라고 알고 있다.

프로세스의 address space는 덩치가 크다. 이 놈이 swap out 될 때 디스크로 내리고 swap in 될 때 다시 메모리에 올리는 건 시간이 꽤 걸릴 것이다. 이 시간이 길면 너무 느리다는 느낌을 받기 때문에 최대한 빨리 I/O가 발생해야 하고, 그래서 Backing store에 대한 접근은 빠르게 프로세스를 내리고 올리는 최적화된 매커니즘을 사용해야 한다.

일반적인 I/O와 다르게 하드디스크에는 연속적으로 쭉 저장했다가 연속적으로 읽을 수 있도록 하는 매커니즘을 사용해야 한다. 

크지 않은 data는 연속적으로 쓰면 오히려 공간 활용도가 떨어진다. 하지만 프로세스와 같은 큰 데이터는 쭉 연속적으로 썼다가 쭉 연속적으로 읽는 게 제일 빠르다.

 

Contiguous Allocation

앞에서 말한 Base register에 CPU가 발생시킨 Logical address를 더해서 실제 주소를 알아낼 수 있는 전제 조건은 무엇일까?

이건 프로세스의 address space가 실제 메모리의 연속적인 공간에 올라와 있을 때만 가능한 것이다.

연속적으로 프로세스를 메모리 상에 탑재하는 기법을 Contiguous Allocation이라고 한다.

커널이 할당되는 영역을 제외하고, 나머지 영역에 프로세스를 연속적으로 저장하면 된다.
이 공간에 여러 프로세스가 저장되니까 OS는 각 프로세스의 위치 정보를 저장해야 한다.
=> 이게 base register와 limit register에 들어가는 정보다.

 

logical address를 가지고 실제 physical address로 변환하는 과정에서, 정상적인 접근이라면 logical address는 address space의 전체 크기인 limit register의 값보다 커질 수 없다.

logical address > limit register 라면 프로세스가 할당 받은 메모리 영역을 넘어서서 접근하는 경우이기 때문에 OS가 막아야 한다.

 

Hole

Contiguous Allocation 방법을 사용할 때 우리가 주목해야 할 사실이 하나 있다.
프로세스가 올라왔다가 실행이 끝나면 메모리에서 빠져나가게 되는데 그럼 중간 중간에 빈 공간이 생기게 된다.              이때  빈 공간의 크기는 제각각이다. 프로세스, 빈공간, 프로세스, 빈공간, ... 이런 형태로 현재 유저 영역이 할당되어 있을 것이다.

이러한 빈공간들을 우리는 Hole이라고 부른다. 이 Hole들을 OS가 관리를 해야 하는데, 왜냐하면 새로운 프로세스가 올라올 때 hole에 할당을 하게 될 것이기 때문이다.

 

Dynamic Storage-Allocation Problem

서로 다른 크기의 빈 공간(Hole)이 여러 개 있을 때 새로 올라올 프로세스를 어떤 빈 공간에 넣을지 결정하는 것이 쉬운 일이 아니다.

새로운 프로세스를 빈 공간들 중 어디세 할당할 것인지 결정하는 방법엔 대표적으로 3가지가 있다.

• First-fit

: 앞에서부터 쭉 돌면서 이 프로세스가 들어갈 수 있는 첫 번째 공간에 넣겠다

• Best-fit

: 이 프로세스와 가장 크기가 비슷한 빈 공간에 프로세스를 넣겠다.

• Worst-fit

: 무조건 제일 큰 hole에 새로운 프로세스를 넣겠다.

 

뭔가 이름만 보면 Worst-fit이 제일 좋지 않은 방법이고 Best-fit이 제일 좋은 방법인 것 같은데 과연 그럴까?

그렇지 않다. best fit을 사용하면 최대한 꽉 차도록 들어가기 때문에 비는 공간이 너무 협소해진다. 이러한 작은 공간이 많이 만들어질 것이다. 그런데 이러한 공간들은 너무 작아서 다른 프로세스들이 들어올 수 없게 되면 쓸모없는 공간이 된다.

반면에 worst fit은 큰 공간에 넣기 때문에 한 프로세스를 넣어도 남는 공간에 또 다른 프로세스가 들어올 수 있다.

=> 어떤 게 좋은지 단정적으로 결정할 수는 없음.

 

Fragmentation

Fragmentation은 자투리 공간이라고 생각하면 된다.

Fragmentation이 발생하면 메모리 공간이 낭비되는 것이기 때문에 최대한 줄여야 한다.

 

External fragmentation은 실제로 사용이 가능한 공간인데 크기가 너무 작아서 쓸모 없는 공간이다.

=> Best fit 방법을 사용하면 External fragmentation이 많이 발생할 것이다.

Internal fragmentation은 실제로 할당을 해줬는데, 이 프로세스가 사용을 하지 않는 경우이다.
예를 들어, 1000 byte가 필요한 프로세스에게 1024 byte를 할당해줬다면 24 byte는 사용을 하지 않는 공간임.
=> 남은 공간이 아니라 실제 할당을 해준 공간인데, 사용을 하지 않는 부분.

즉, External은 할당이 안 된 빈 공간인데 너무 작아서 활용도가 떨어지는 공간이고 Internal은 실제 할당을 해주었는데 사용하지 않는 공간.

 

Internal fragmentation은 이미 프로세스에게 할당이 된 공간이라 어쩔 수가 없지만 External fragmentation은 Compaction을 통해서 줄일 수 있다.

=> 메모리에 있는 프로세스의 address space들을 한 쪽으로 쭉 밀면 External fragmentation들이 모여서 꽤 큰 공간이 만들어질 것이다.
=> 이걸 Compaction이라고 한다.

Compaction을 사용하면 external fragmentation을 활용할 수 있는데, 문제는 Compaction이 매우 heavy한 operation이라는 것이다.
Compaction을 하고 나면 모든 프로세스의 base 주소가 바뀌게 된다. 그리고 밀어 붙이는 동안 메모리 copy가 계속 발생해야 하기 때문에 오버헤드가 크다.
=> 함부로 사용할 수가 없다. Compaction을 하면 되니까 external fragmentation을 마구 발생시켜도 되겠네? 라고 생각하면 안 된다.

 

결론은 Contiguos Allocation 방식을 사용하면 Fragmentation이 발생한다는 것인데, 이걸 해결하는 것이 까다롭다는 것이다.

 

그래서 탄생한 기법이 Paging(페이징) 기법이다.

페이징 기법은 External Fragmentation이 발생하지 않도록 하는 방법이다.

Paging

레고 블럭처럼 메모리 공간에 Address space를 끼워넣는 방식인데 똑같은 사이즈의 레고 블럭을 만든다. 같은 사이즈로 메모리 공간도 분할, 어드레스 스페이스도 분할.

메모리 공간 중간 중간에 블럭을 끼워넣다 보니 연속적인 공간에 어드레스 스페이스가 할당된다고 보장할 수 없다.
=> 이걸 허용해 줌으로써 External fragmentation이 발생하지 않도록 하는 방법.

 

DRAM을 똑같은 크기로 분할한다. 그리고 그 분할된 각각의 공간을 frame이라고 한다. 보통 frame 크기는 2의 지수승으로 정한다. (보통 4KB로 많이 함)

frame이 4KB라고 하면 Address도 4KB 단위로 자른다. 그 자른 4KB 하나를 "페이지"라고 한다.
=> 페이지와 frame의 크기는 같아야 한다. 그리고 frame에다가 페이지를 집어 넣겠다. 대신 연속된 frame 공간에 넣을 필요는 없다.

그럼 무슨 문제가 생길까??
연속적으로 집어 넣었을 때는 시작 주소와 상대 주소를 가지고 실제 물리 주소를 알 수 있었는데, 이제는 여기 저기에 페이지가 들어 있으니까 바로 찾을 수가 없다.
=> 각각의 페이지가 어디에 있는 frame에 저장되어 있는지 다 알아야 한다. 이걸 관리하는 자료 구조가 필요하고 그걸 우리는 "페이지 테이블" 이라고 부른다.

테이블에는 내 어드레스 스페이스의 1번 페이지는 DRAM의 5번 frame에 들어있다. 이런 정보가 들어 있음.

이렇게 하면 좋은 점은 빈 공간이 frame 단위로 비어 있다.
=> 쓸모 없는 자투리 공간이 생기지 않는다.
=> 즉, External fragmentation이 발생하지 않는다.

 

Contiguos Allocation을 사용하면 하나의 Address space가 연속된 메모리 공간에 탑재되기 때문에 해당 프로세스의 base 주소와 offset을 이용해서 원하는 데이터에 접근을 할 수가 있었다.

그런데 페이징 기법을 사용하면 페이지가 메모리의 frame 곳곳에 불연속하게 할당되기 때문에 base register와 limit register의 값이 의미가 없게 된다.

그렇다면 페이징 기법을 사용했을 때는 CPU가 발생시킨 논리 주소를 어떻게 실제 물리 주소로 변환할까?

 

Address Translation Scheme in Paging

페이지의 크기를 2의 지수승으로 결정하는 순간 뭐가 가능해지냐, logical address의 bit를 분할해서 페이지 번호와 페이지 내부의 offset으로 나눌 수 있게 된다.

logical address가 2^m으로 주소 체계가 만들어져 있다고 하고, page의 size는 2^n이라고 하자. 그러면 logical address를 표현하기 위한 bit는 m비트가 되고 페이지 내부의 offset을 나타내기 위한 bit는 n비트가 된다.

logical address를 나타내는 전체 m비트 중에서 앞쪽의 (m-n) bit는 몇 번째 페이지인지 나타내고, 제일 뒤의 n비트는 page 내부의 offset이 되더라.

왜 그렇게 될까?
2^m 짜리 Address space를 2^n 크기의 페이지로 자른다고 하자. 그럼 총 페이지의 수는 2^(m-n)이 된다. 2^(m-n)개의 페이지를 구분하기 위해서는 (m-n) 비트가 필요. 그리고 나머지 n 비트는 그 페이지 안에서의 offset이 된다.

결국 페이지 번호는 주소를 페이지의 사이즈로 나눈 몫이 되고, 페이지 내에서의 offset은 그 나머지가 된다.

그런데 나누기는 상대적으로 시간이 오래걸리는 연산이다.

그래서 나누는 수인 페이지의 사이즈를 잘 정하면 재밌는 현상이 나타난다

 

이해를 위해 10진수로  먼저 생각을 해보자.

논리 주소가 1234 이고 페이지의 사이즈가 10^1 이라면

페이지 번호는 1234 / 10 = 123 (page #)

그리고 123번 페이지 내에서의 offset은 1234 % 10 = 4 (offset)

굳이 나누기를 하지 않아도 숫자를 그냥 사이즈의 승수로 쪼갠 것으로 페이지 번호와 offset을 구할 수 있다는 것이다.

 

뒤의 예를 보면서 더 이해해 보자.

실제 Address space는 이것보다 훨씬 크지만 이해를 위해 Address space의 크기가 16(2^4)이라고 하자.

그리고 페이지와 frame의 크기는 4(2^2)라고 하자.

크기가 16인 Address space를 크기가 4인 페이지들로 분할했으므로 4개의 페이지가 생성된다.

=> 페이지를 구분하기 위해서 (4 - 2)bit = 2bit가 필요하게 된다.

그리고 각 페이지 내에서의 데이터를 구분하기 위한 offset으로는 2 bit가 필요하다.

 

그렇다면 CPU가 logical memory 상의 2번 데이터에 접근하려고 한다고 해보자.

2를 이진수로 나타내면 0010 인데, 앞 2bit는 페이지의 번호 뒤 2bit는 offset을 의미하기 때문에 0번 페이지의 2번 데이터라는 것을 의미한다.

그러면 페이지 테이블로 가서 0번 페이지가 어디 frame에 저장되어 있는지를 먼저 파악한다.

페이지 테이블을 통해 0번 페이지는 5번 frame에 저장되어 있다는 것을 알 수 있다. 그리고 페이지가 어디에 저장되든 페이지 내에서의 offset은 바뀌지 않기 때문에 그대로 offset을 2로 해서 원하는 데이터에 접근할 수 있다.

 

앞의 과정을 조금 더 추상적으로 보면 이런 느낌

 

Free Frames

앞에 나온 과정은 페이지 테이블 정보가 이미 만들어져 있다는 전제가 깔려있다.
그럼 Address space가 메모리에 올라오게 될 때 페이지 테이블 정보는 어떻게 만들어질까.

OS는 memory management를 담당하는 부분에서 현재 메모리 상에 비어 있는 frame의 정보를 유지한다.
정보를 관리하는 방법은 OS마다 다르지만 리스트를 만들어서 관리한다고 가정한다.

이 상황에서 새로운 프로세스가 만들어졌다. address space는 4개의 페이지로 나누어져 있다고 가정한다.
이 프로세스를 메모리에 탑재를 할 때 페이지 별로 탑재를 한다.

0번 페이지부터 넣는데, 리스트의 맨 앞을 보니 14번이 비어있다고 되어 있다. 0번 페이지는 14번 frame에 넣는다.
그리고 나서 페이지 테이블에 0번은 14번 frame에 들어있다라고 쓴다. 그 다음에 1번 페이지를 넣으려고 리스트를 봤더니 13번이 비어 있다. 1번 페이지는 3번 frame에 넣는다. 그리고 페이지 테이블에 1번 페이지는 13번 frame에 있다고 쓴다.
이렇게 쭉쭉 넣는다.

여기서 의문. 페이지를 넣으려는데 비어있는 frame이 없으면 어떡할까?? 이 문제는 나중에 virtual memory에서 다룬다.

 

Implementation of Page Table

이 페이지 테이블을 구현하기 위해서 OS는 어떤 정보를 갖고 있어야 할까?

페이지 테이블은 메인 메모리에 올라와 있어야 한다.

PTBR: 페이지 테이블이 저장된 위치를 저장하는 레지스터. 페이지 테이블의 위치를 이용해서 찾고자 하는 페이지의 번호만큼 내려가면 해당 페이지가 저장된 frame이 나와 있다.

PTLR: 페이지 테이블의 길이를 저장하는 레지스터

 

예전에는 CPU가 메모리 접근을 위해서 메모리 주소를 발생시키면 직접 그 메모리로 가서 데이터만 가져오면 됐었는데,

페이징 기법을 쓰면 페이지 테이블을 look up을 해서 실제 주소를 알아낸 다음에 메모리에 접근을 해야 하기 때문에 메모리에 2번 접근을 해야 한다. (페이지 테이블에 접근할 때 한 번, 실제 주소를 가지고 메모리에 접근할 때 한 번)

그래서 CPU를 메모리에서 데이터를 가져올 때마다 메모리에 2번 접근할 수 밖에 없음. 근데 CPU 입장에서 메모리 access는 매우 느리다.
frame의 시작 주소에 offset을 더하는 변환은 MMU 하드웨어를 사용해서 매우 빠르게 한다고 하더라도, 페이지 테이블에 접근을 해야 하기 때문에 느려지는 건 어쩔 수 없음.

그럼 페이징 기법을 쓰면 안 되나??
페이징 기법은 메모리 관리의 복잡성을 낮추기 위해 꼭 필요하다.

그래서 TLB(Translation Look-aside Buffer)라는 것을 사용한다.
캐시같은 개념. 메모리에 있는 페이지 테이블의 일부를 담고 있는 작고 빠른 메모리이다. 그러면 주소 변환을 페이지 테이블에 가서 하기 전에 TLB에 먼저 가서 이미 변환된 정보가 있는지 확인을 하게 된다.
TLB는 메모리보다 훨씬 빠르기 때문에 메모리에 2번 접근하는 것보다 훨씬 빨라진다.

 

CPU scheduling에 의해 CPU가 실행하는 프로세스가 바뀌게 되면, TLB는 비우게 된다.
페이지 테이블은 프로세스마다 갖고 있기 때문에 Context switch가 일어나면 TLB에 저장된 정보는 잘못된 정보이기 때문에 비워버려야 한다.

TLB에 없는 페이지는 어쩔 수 없이 페이지 테이블에 가서 찾아야 한다.

=> 그렇기 때문에 TLB에서 주소 변환이 대부분 일어나야 TLB를 사용하는 효과가 있다.

그런데 TLB는 빠르긴 하지만 저장 공간이 매우 작은 메모리이다.
따라서 페이지 테이블의 매우 작은 일부가 저장이 되는데 여기서 많은 히트가 날까?

가능하다. Locality(지역성) 때문이다. 
자주 접근되는 페이지의 정보를 TLB에 저장을 해두면 그 페이지에 접근할 때마다 TLB에서 변환이 될테니까 히트가 자주 발생할 수 밖에 없다.
=> 그만큼 locality가 강하다는 뜻.

 

Associative Memory

TLB에는 페이지 테이블의 일부가 띄엄띄엄 저장되어 있기 때문에 페이지 테이블의 일부 엔트리들이 연속되게 저장되지 않는다. 
때문에 위에서부터 3칸을 내려오면 4번 페이지의 정보가 저장되어 있다 이게 보장이 안 된다.
그러면 앞에서부터 페이지 번호를 다 찾아봐야 한다. 이러면 TLB가 아무리 빨라도 TLB를 사용하는 효과가 줄어든다.
그래서 "Associative Memory"를 사용해서 TLB를 만든다.
=> TLB의 모든 엔트리를 동시에 접근해서 찾고자 하는 페이지의 번호를 한 큐에 찾을 수 있다.

 

그럼 지금까지의 내용을 정리해보자.

CPU가 Logical address를 통해 데이터에 접근하려고 하면, 제일 먼저 Logical address로부터 페이지 번호를 알아내고, 그 페이지 번호를 가지고 TLB에서 찾는다. 있으면 바로 frame의 번호를 알 수 있기 때문에 주소 변환은 끝이 난다.

만약 TLB에 없으면 메모리의 페이지 테이블에 접근해서 frame의 번호를 알아내서 실제 주소를 알 수 있게 된다.

그런데 Locality에 의해 대부분의 경우 TLB에서 찾을 수 있게 된다.
=> TLB를 사용하면 페이징 기법의 성능이 좋아진다.

Contiguous allocation만큼 성능이 좋지는 않지만, 약간의 성능 희생으로 External fragmentation을 없애고, 관리상의 측면에서 많은 이점을 얻을 수 있다.

 

Effective Access Time(EAT)

TLB를 사용했을 때의 페이징 기법의 메모리 접근 시간 

=> CPU가 메모리에 접근해서 원하는 Instruction, Data를 가져오는데까지 걸리는 평균 시간.

TLB에서 Look up을 하는 시간을 α 라고 한다. (이 시간은 매우 매우 짧음)

그리고 Memory에 접근하는 시간을 β 라고 한다. (메모리 접근이므로 오래 걸린다)

그러면 Best case의 경우 모두 TLB 히트가 나면 EAT = α + β 가 된다.

하지만 최악의 경우 모두 TLB 미스가 나면 EAT = α + 2β 가 된다.

β는 메모리에 접근하는 시간이므로 최대한 줄여야 한다. 그래서 우리는 EAT가 α + β에 가깝게 되도록 해야 한다.

=> Localitiy에 의해 TLB 미스가 나는 일은 잘 없으므로 가능하다.

 

Memory Protection

페이징 기법을 쓰지 않았을 때는 현재 접근하는 주소가 잘못된 주소가 아닌지 offset이 limit register의 값보다 큰지 비교를 통해 MMU에서 검사를 했었다.

그런데 페이징 기법에서는 그런 과정이 없다.

페이징 기법은 Protection이 필요가 없을까? 잘못된 주소에 접근할 가능성이 없을까?
아니다. 페이징 기법에도 Protection이 필요하다.

페이지 테이블의 각 엔트리마다 Protection bit (=Valid-invalid bit) 1비트를 사용한다.
이 값이 valid로 표현되어 있으면 정상적인 접근이고, invalid로 되어 있으면 잘못된 접근임을 의미한다.

그런데 페이지 테이블의 길이를 저장하는 레지스터가 있었다 (PTLR).

Address space만큼 페이지 테이블이 만들어져 있으면 페이지 테이블의 길이만 가지고 접근하려는 페이지 번호가 그 길이를 넘어가면 잘못된 페이지 번호임을 판단할 수 있다.
=> 사실 valid-invalid bit이 없어도 잘못된 것을 알 수 있는데, 실제로 그걸 쓰진 않는다.
=> 이 얘기 역시 virtual memory 시간에 다룰 것이다.

이러한 valid-invalid bit은 어떻게 구현이 될까?

address space의 크기가 12,287이고 페이지의 사이즈가 2^11 이라면 총 6개의 페이지가 생성될 것이다.

0 ~ 5번 페이지의 엔트리는 페이지 테이블에 valid로 표시가 되어 있고 나머지 엔트리는 invalid로 표시가 되어 있다.

 

음 그러면 page table을 address space에 맞춰서 할당하면 되지 않나? 5번까지만 저장할 수 있도록 페이지 테이블을 만들면 되지 않나? 그럼 valid-invalid bit가 필요가 없을 것 같은데,,

Address space를 잘 생각해보자 제일 아래쪽인 0번부터는 text(code)가 저장되고 그 위엔 data, 그리고 그 위엔 heap과 stack이 마주보고 있다. 이때 stack은 max부터 아래로 자라는 방향으로 만들어져 있다.
즉, stack과 heap은 변하는 공간이기 때문에 프로세스가 처음 만들어졌을 때 사이즈를 알 수 없음
=> 그래서 페이지 테이블을 얼마나 크게 만들어야 할지 알 수가 없다.

또한 max번지는 몇 번지로 해야 하는지도 문제다. max를 너무 작게 잡으면, function call이 계속 일어나서 Stack이 커지고, 동적 할당이 계속 일어나서 Heap이 계속 커지면 둘이 충돌하게 될 것이다.

안전하게 하려면 max는 얼마나 크게?
이론적으로 가장 큰 max는 OS가 32bit 체계면 2^32 - 1번지, 64bit 체계면 2^64 - 1번지까지 가능하다. 이게 max가 된다.

그러면 페이지 테이블도 이에 맞춰서 만들어져야 한다.

heap과 stack 사이에 비어있는 공간은 할당된 공간이지만 사용되지 않는 공간이니까 invalid로 표현할 수 있다.

또한 페이지 테이블의 사이즈를 실제로 heap과 stack이 사용하는 영역만 가지고 할당을 한다면, 즉 heap과 stack 사이의 빈 공간에는 페이지를 할당하지 않으면 heap또는 stack이 늘어나게 돼서 페이지가 생겨나면 다른 페이지들의 번호가 다 바뀌게 된다. 이건 불가능하다.
=> 그래서 Stack은 제일 끝 max로 밀어버리는 것이고 페이지 테이블은 충분히 크게 만들어져야 한다.

=> 그럼 너무 커지게 되는데 이게 메모리에 탑재가 되느냐??
이것도 나중에 배우겠지만 페이지 테이블 역시 연속된 공간에 할당될 수 없기 때문에 쪼개서 들어가게 된다.
페이지 테이블을 위한 페이지 테이블이 또 별도로 필요하다.

 

Shared Pages

페이징 기법의 큰 장점 중 하나는 프로세스 간에 페이지 공유가 가능하다는 것이다.

기본적으로 각 프로세스의 address space는 다른 프로세스가 접근하지 못하도록 보호를 받는다.
=> 다른 프로세스가 내 영역에 들어와서 데이터를 막 써버리면 큰일나기 때문이다.

그런데 여러 학생들이 서버에 붙어서 숙제를 하면서 자기가 만든 코드를 gcc를 이용해서 컴파일한다고 해보자. A라는 학생과 B라는 학생이 각자의 코드를 gcc를 사용해서 컴파일하면 A도 gcc 프로세스를 하나 만들고, B도 gcc 프로세스를 하나 만든다. 같은 gcc를 실행하는 프로세스지만 각자 address space가 만들어져 메모리에 올라가게 된다.

두 프로세스는 완전히 다른 프로세스지만 둘 다 gcc를 실행하므로 code 부분은 일치한다. (둘 다 gcc 코드가 들어 있음).

그리고 코드에 대한 접근은 read-only이다.
따라서 read-only가 보장되어 있는 상태라면 하나의 공간을 공유해서 사용하면 메모리를 효율적으로 사용할 수 있다.
=> 코드 영역은 공유가 가능하겠다.

이게 왜 페이징 기법의 장점이냐

contiguous allocation을 하면 address space 공유가 불가능 하다. Instruction에 대한 접근 자체가 address space의 시작 지점에서 offset을 사용해서 접근을 한다. 즉, address space시작 주소가 똑같지 않은 이상은 공유가 불가능하다. 그런데 시작 주소가 같으면 다른 영역도 공유를 하게 되므로 이건 불가능하다.

페이징 기법을 사용하면, 페이지 테이블 엔트리를 통해 같은 물리 주소로 매핑이 되도록 하면 공유를 할 수 있게 된다

 

※ 본 내용은 한양대학교 강수용 교수님의 강의를 참고해서 작성되었습니다.