outline
Background
Binding of Data to Memory
MMU
contiguous allocation
paging
TLB
Background
메모리는 기본적으로 주소와 데이터로 구성되어 있다. CPU와 메모리는 양방향으로 주소와 데이터를 주고받는다. CPU는 주소를 가지고 메인 메모리에 데이터를 요청을 하고 해당 주소에 계산 결과를 통해서 메모리에 요구하는 실제 주소에 저장되어 있는 데이터를 CPU에 전달한다.
- 소스 파일(Source file) : 고수 준언어 또는 어셈블리어 (ex. c)
- 목적 파일(Object file) : 컴파일 또는 어셈블 결과 (ex. o)
- 실행파일(Executable file) : 링크 결과 (ex. exe)
- 소스파일은 컴파일러에 의해 수행 결과로 목적 파일을 생성한다. 프로그래밍을 하면서 외부의 라이브러리를 사용하지만 컴파일 단계에서는 목적 파일에 이를 추가하지 않는다. 링크 단계에서 하드디스크에서 프로그래머가 추가한 라이브러리를 찾아 정보를 추가하여 실행 파일을 만든다.
Binding of Data to Memory
주소를 변수(Symbolic address)의 개념으로 표시한다. 이러한 주소를 논리적 주소(Logical Address)라고 하며 이 주소를 물리적 주소(Physical address)로 변환하는 과정을 Binding이라 한다. CPU는 논리적 주소를 발생시키면 논리적 주소를 통해서 맵핑된 메인 메모리의 실제 주소를 CPU에게 반환해준다.
1. Compile time binding
하나의 프로세스만 수행될 수 있었던 운영체제에서는 각 변수(symbol)의 주소를 메모리 상의 맵핑을 시키는 것을 컴파일(compile) 때 이루어졌다. 모든 사용자의 프로세스는 커널이 끝날 때 메모리에 올라가서 실행이 된다. 만약에 다른 운영체제에서 이 프로그램을 돌릴 때 절대적인 주소가 다르기 때문에 재컴파일(recompile)을 해야 한다.
2. Load time binding
컴파일할 때 상대적인 주소를 변수마다 binding 시켜준다. 프로그램을 메모리에 탑재될 때 그 시작 주소에서 상대 주소 값을 더해서 실제 주소 값이 나오기 때문에 상대 주소만 알면 실제 주소를 구할 수 있기 때문에 compile time binding의 문제점이었던 달라진 시작 주소에 따른 재컴파일(recompile)을 할 필요가 없어진다.
한번 주소가 정해지면 실행하고 있는 과정에서 위치 변경이 불가능해진다. 위치 변경이 일어나면 다시 상대 주소 값을 다시 계산을 해야 한다. 이동에 대한 지원이 존재하지 않는다.
3. Execution time binding
load time binding의 문제였던 위치에 따른 지원을 허락해준다. 실행될 때 메모리의 주소가 결정되는 것으로 논리적 주소와 물리적 주소가 다르게 된다. 이에 따라 주소 번역 기능이 필요하고 이 번역 기능을 MMU에서 해주게 된다. 실행되면서 binding이 일어나므로 동적 재배치라 한다. 주소 번역 기능을 수행해야 하기 때문에 메모리 접근 시간이 2배로 늘어나지만 관리 측면에서 좋다.
Memory Management Unit(MMU)
논리적 주소(가상 주소)를 물리 주소로 바꾸어 주는 하드웨어 장치로, Base register는 Reolocation register라고 불리며, CPU는 논리적 주소만 다루고 물리적 주소에는 관여하지 않는다. 프로세스의 시작 주소를 Base register에 저장하고 프로세스의 길이를 Limit register에 저장한다.
CPU가 논리 주소 346 값을 요청하면 MMU에서는 해당 논리 주소에 mapping 되어 있는 베이스 레지스터 값 14000을 더해서 물리 주소 14346을 통해서 메모리에서 실제 주소를 CPU에게 전달해 준다.
연속 메모리 할당(Contiguous Allocation)
커널이 저장되는 영역을 제외한 남은 공간을 사용자의 프로세스를 연속적으로 저장을 한다. 프로세스가 연속적으로 메모리에 저장되어 저장될 때마다 베이스 레지스터에는 프로세스의 시작 주소가 저장되며, 리미트 레지스터에는 프로세스의 길이가 저장된다.
베이스 레지스터는 CPU가 발생시키는 논리 주소와 베이스 레지스터 값과 더해서 실제 주소 값을 구할 수 있기 때문에 별도의 베이스 레지스터가 필요로 했다. 그렇다면 리미트 레지스터는 어디에서 활용되는가??
예를 들면 CPU가 논리적 주소를 발생시킨다면, 논리적 주소와 베이스 레지스터 값과 더해서 실제 주소를 찾게 된다. 하지만 논리 주소 값이 리미트 레지스터 값보다 클 경우 error을 발생시킨다. 에러를 보내는 이유는 논리 주소 값이 리미트 레지스터 값보다 크다는 것은 연속적으로 저장되어 있는 공간에 다른 프로세스 영역에 접근될 수 있기 때문이다.
contiguous allocation으로 메모리에 프로세스를 연속적으로 할당을 했다. 그렇다면 프로세스가 종료되면 연속적으로 저장되어 있던 메모리 공간에 종료된 프로세스의 길이만큼 빈 공간이 발생된다. 이러한 빈 공간을 메모리 공간(memory hole)이라고 한다.
그렇다면 프로세스를 연속적으로 할당된 메모리 공간 안에서 빈 공간 처리를 어떻게 할 것인가??
1. first-fit : 첫 번째 빈 공간에 할당한다.
2. best-fist : 가장 적합한 빈 공간에 할당한다.
3. worst-fit : 가장 큰 빈 공간에 할당한다.
**빈 공간에 프로세스를 할당하는 방법은 세 가지 방법으로 나누어지는데 best-fit이 worst-fit보다 좋은 것은 아니다.
외부 단편화(external Fragmentation)
메모리 공간에서 프로세스가 종료되어 빈 공간이 발생되어 해당 빈 공간에 적합한 또한 작은 프로세스를 할당하다 보면 작은 공간이 무수하게 많아지는 경우가 발생한다. 이 처럼 메모리의 총 남아있는 공간을 계산했을 때 다음 들어올 프로세스가 들어올 수 있는 만족할만한 메모리 공간에 있음에도 불구하고, 가능한 공간들이 연속적이지 않고 너무 많은 작은 빈 공간들이 조각으로 남아있는 경우를 외부 단편화(external framentaion)이라 한다. 대게 best-fit을 사용할 경우 많이 발생하는 문제이다. 이러한 빈 공간을 연속적인 공간으로 만들고 움직이는 작업인 compaction이 고안되었지만 하드 디스크가 병목 되어 copy를 하는 작업이기 때문에 좋은 방법은 아니다.
페이징 기법(Paging)
프로세스를 연속적으로 메모리에 할당하면 외부 단편화가 발생하였다. 이러한 문제를 해결하기 위해 페이징(paging) 기법이 구현되었다. 페이징 기법은 주소 공간을 비연속적으로(noncontiguous) 할당하게 허락을 해준다. 페이징 기법을 사용하는 시스템에서는 페이지 번호(page number) - p와 페이지 참조 번호(page offset) - d 이 순서쌍 (p, d)으로 갖고 있다.
- 프레임(frame)과 페이지(page)는 메모리를 일정한 크기의 공간으로 나누어 관리하는 단위이며, 프레임과 페이지의 크기는 같다.
- 프레임(frame) : 물리 메모리를 일정한 크기로 나눈 블록.
- 페이지(page) : 논리 메모리(가상 메모리)를 일정한 크기로 나눈 블록.
- 페이지 테이블(page table)은 프로세스의 페이지 정보를 저장하고 있으며, 하나의 프로세스는 하나의 페이지 테이블을 가진다.
- 페이징 기법을 사용하면 비어있는 프레임 공간이 없고 그 말은 외부 단편화를 발생하지 않는다. 하지만 내부 단편화는 발생한다. 모든 프로세스가 똑같은 크기의 페이지와 프레임으로 할당받기 때문에 프레임 크기에 비하여 프로세스 크기가 작아서 할당은 되었지만 사용하지 않는 공간이 발생된다.
주소 변환(Address Translation)
페이지 기법을 사용하기 위해서는 여러 개로 흩어진 페이지에 CPU가 접근하기 위해 페이지 테이블을 통해 주소를 변환해야 한다.
논리 주소 : CPU가 내는 주소는 2진수로 표현되고 이를 m비트가 있다고 가정하면, 여기서 하위 n비트는 오프셋(offset)라고 한다. 그리고 상위 m-n비트는 페이지의 번호에 해당한다.(m-n = p, n = d)
논리 주소를 물리 주소로 변환하기 위해서 페이지 번호(p)는 페이지 테이블의 인덱스 값이고, p에 해당되는 테이블 내용은 메모리의 프레임 번호이다. 오프셋(d)은 변하지 않는 값이다.
***즉 우리가 알아야 하는 정보는!?
1. 논리 주소를 2^m으로 표현할 수 있는 m을 찾는다. -> 논리 주소(m)를 찾는 과정
2. m을 2^n으로 표현할 수 있는 n을 찾는다. -> offset(n)을 찾는 과정(페이지 테이블의 개수)
3. 페이지 번호(page numaber)를 찾는다. -> m-n
m-n개의 bit을 가지고 해당 bit에 해당하는 page table로 가서 page를 lookup을 해서 몇 번 frame에 들어있는지 정보를 확인하고 그 frame에서 offset만큼 건너뛰어서 해당 물리 주소을 알 수 있다.
내부 단편화(Internal Fragment)
내부 단편화는 프로세스 크기가 페이지 크기의 배수가 아닐 경우 마지막 페이지는 한 프레임을 다 채울 수 없다. 이로 인해 발생하는 공간은 결국 메모리 낭비로 이어진다. 내부 단편화는 해결할 방법이 없다. 하지만 내부 단편화는 외부 단편화에 비해 낭비되는 메모리 공간은 매우 적다. 내부 단편화의 최대 낭비되는 크기는 페이지 사이즈에서 마이너스 1이 된다. 이는 무시할 정도로 작은 크기이다.
Paging hardware with TLB
페이징 기법을 사용하면 메모리에 2번 접근해야 한다. page table에 접근하기 위해 메모리 접근 1번, 실제 주소을 구하고 메모리에 접근 1번)
TLB를 통해 이를 어느 정도 해소하면서 구현이 가능하다. TLB는 일종의 캐시로 Translation Look aside Buffer의 약어이다. 실제 전체 페이지 테이블은 메모리에 위치해 있고 테이블의 일부를 tlb에 가져와서 사용한다. 그러므로 tlb에 유효한 페이지가 있을 때와 없을 때의 속도 차이가 발생한다.
effective access time(EAT)
메모리를 읽는 시간(b)을 100ns라고 하고, TLB를 읽는 시간(a)을 20ns라고 하고, hit 확률을 0.8이라 하면 총 EAT 값은 140ns 값을 갖게 된다. TLB를 사용하게 되면 220ns 걸려야 하는 시간과 속도 차이가 발생한다.
보호와 공유(protection and shared)
모든 주소는 페이지 테이블을 경유하므로, 테이블을 이용해서 보호 기능을 수행할 필요가 있다. 잘못된 페이지 넘버에 접근할 때 vaild와 invaild bit로 구분하여 잘못된 접근을 방지한다.
공유는 메모리 낭비를 방지하기 위함이다. 같은 프로그램을 쓰는 복수 개의 프로세스가 있다면, 프로세스의 메모리는 code + data + stack 영역으로 나뉘는데 프로그램이 같다면 code 영역은 같을 것이다. 그러므로 하나의 code 영역을 복수 개의 프로세스가 공유하여 메모리 낭비를 줄이는 것이다.
