Logical vs. Physical Address

프로그래머 입장에서는 숫자로 된 주소가 아닌 symbolic address를 사용한다.

언제 주소 변환을 하는지에 따라 3 가지 방법으로 구분할 수 있다.

주소 바인딩 (Address Binding)

컴파일 타임 바인딩은 컴파일 때 이미 결정된 것이다. 요즘 컴퓨터에서는 여러 프로세스를 사용하기 때문에 잘 사용하지 않는다. 만약 주소를 바꾸고 싶으면 컴파일을 다시해야 한다.

로드 타임 바인딩은 로드될 때 결정되는 것이다. 비어있는 곳에 갈 수 있다.

런타임 바인딩은 로드 타임 떄 주소가 결정되지만, 실행될 때 주소가 바뀔 수 있다. 요즘 컴퓨터는 런타임 바인딩을 지원한다.

Runtime binding은 하드웨어의 도움이 필요하다 (MMU).

cpu는 logical addres를 바라본다. 이렇게 될 수 밖에 없다. 위위 그림을 보자. CPU가 instruction을 실행하려면 (20번지, 30번지를 읽어서 더해라). 이 20, 30은 logical address다. 이 컴파일에 들어간 코드상의 주소까지 바꿀 수는 없다. 그럴려면 컴파일 다시해야 한다. 따라서 CPU가 보는 것은 logical address일 수 밖에 없다.

Memory-Management Unit (MMU)

Dynamic Relocation

가장 간단한 방식은 mmu의 relocation register (base register)를 더해주는 것이다.

limit register는 프로그램의 최대 크기를 넘는지 안넘는지 체크해주는 것이다. 넘으면 트랩을 건다.

사실 이 방식은 여러 프로그램이 페이지로 나뉘어서 올라가는 요즘 시스템에는 안맞다.

Hardware Support for Address Translation

그래서 어떤 주소 값을 달라고하면 우선 메모리 범위를 벗어나지는 않는지 우선 체크한다.

Some Terminologies

Dynamic Loading

좋은 프로그램은 오류 처리 루틴이 많다. 이런 것은 필요할 때만 올리면된다.

페이징 기법과 차이점은 원래는 페이징 기법은 운영체제가 알아서 해주는 것이고 다이나믹 로딩은 프로그래머가 조작하는 것이다. 하지만 지금은 섞어서 쓰기도 한다.

Overlays

다이나믹 로딩과 비슷해보이지만, 역사적 시점에서 프로그래머가 수작업으로 하던 것을 일컫던 말이다.

Swapping

메모리에서 쫓겨나는 것이 swap out이고 메모리에 올리는 것을 swap in이라고 한다. 중기스케줄러가 하는 작업인데, 주로 cpu 우선순위가 낮은 것을 쫓아낸다. 런타임 바인딩에서 효과를 발휘한다. 300번지에서 쫓겨나고 700번지에 다시 들어갈 수 있어야 한다.

Dynamic Linking

다이나믹 링킹은 내 실행파일에 라이브러리 코드를 넣는 것이 아니라 연결만 해놓고 나중에 필요할 때 찾아가는 것이다.

Allocation of Physical Memory

현대 시스템에서는 당연히 불연속 기법 Noncontiguous allocation을 사용하고 있고, 페이지라는 동일한 크기로 나눠서 올렷다 내렸다 한다. 이를 페이징이라 한다.

Contiguous Allocation

hole들이 여러개인데 어느 홀에 넣어야하는지 결정하는 알고리즘이 필요하다.

외부조각들을 없애는 방식이다. 디스크 조각모음인데, 비용이 매우 많이 든다. 또 런타임 바인딩이 지원되어야만 가능하다.

Noncontiguous Allocation

Paging

같은 크기로 잘라놨기 때문에 external fragmentation은 발생하지 않는다.

Paging Example

paging기법에서 주소 변환을 위해 page table이라는 것이 이용된다. 논리적인 주소가 어떻게 물리적 주소로 바뀌는지 알려준다.

페이지 테이블은 메모리에 존재한다. 프로그램마다 페이지 테이블이 별도로 존재해야해서 캐시나 레지스터에 들어가기는 너무 크다. 그래서 메모리에 보관한다.

Address Translation Architecture

Implementation of Page Table

메모리에 접근하기 위해 주소 변환을 한 후 접근해야 하는데, 주소 변환을 하기 위해 페이지 테이블에 접근해야하는데 이게 메모리에 있다. 그래서 두 번 해야 한다.
이제는 레지스터가 페이지 테이블의 위치를 알려주기 위해서 사용된다. (PTBR, PTLR).
이전에 간단했던 두 개의 레지스터를 이용한 값이 페이지 테이블 위치를 알려주기 위해 사용하는 것이다.

메모리를 두 번 접근하니 성능이 느리다. 따라서 메인메모리보다 빠른 일종의 캐시인 TLB(Translation Look-aside Buffer)를 사용한다.

Paging Hardware with TLB

메모리에 접근 하기 위해 페이지 테이블에 접근하고, 실제 데이터를 가져오기 위해 2번 가져오는 것은 비용이 크다. 메모리 주소 변환을 위한 별도의 캐시 메모리인 TLB를 따로 둔다.

page table에서는 몇번째 p칸 떨어져있는지 알면 바로 주소가 나왔는데, TLB에서는 page number와 frame number 쌍으로 가지고 있다. 특정 page number가 있는지 TLB 전체를 찾아봐야하는데, 시간이 오래 걸리니 병렬적으로 탐색이 가능한 hardware를 쓴다.

TLB에서 못찾는다면 그때는 메모리에 접근해서 page table을 통해서 주소를 알아낸다.

Associative Register

context switch가 일어날때 오버헤드가 생기는 이유 중 하나이다. 프로세스마다 TLB에 들어가야하는 내용이 다르기 때문에 프로세스가 바뀌면 비워야 한다.

Effective Access Time

Two-Level page Table

두번 접근해야하니 속도에서 손해를 보고, 공간에서 이익을 본다. 이게 2단계 페이지 테이블을 쓰는 목적이다.

가운데 페이지 테이블에서 페이지 테이블 하나하나가 페이지 크기, 즉 4kb와 크기가 같다. 그 안에 엔트리는 4b이므토 1k개가 존재한다.

이 페이지 중요하다!

주소가 32비트면 2^32개 주소가 있다. 즉 4 2^20 byte = 4G의 주소공간이다. 한 페이지가 4K면 1M 개의 page table entry가 필요하다. 각 프로그램마다 페이지 테이블이 따로 있다. 하지만 실제로 사용되는 공간은 매우 적다. 그래서 2단계 테이블을 쓰겠다는 것이다.

Outerpage table에서 사용되지 않는 주소 공간에 대해 null로 만들면 대응하는 테이블을 null로 만들면 안쪽 테이블들을 만들지 않아 공간을 아낄 수 있다.

Two-Level Paging Example

4kb, 즉 2^12 비트를 구분하기 위해서 page offset에 12가 필요하다

p2는 페이지 테이블 내에 엔트리를 구분해야하는데, 엔트리는 1k가 있으므로, p2는10비트가 필요하다.

안쪽 테이블의 크기는 하나가 4kb로 페이지 크기와 같다.

Address-Translation Scheme

Multilevel paging and Performance

Valid (v) / Invalid (i) Bit in a Page Table

사실 페이지 테이블에 엔트리마다 부가적인 정보가 담겨져있는데, valid/invalid bit이다. 페이지 테이블 엔트리에는 사용되지 않는 부분에도 만들어져야하는데, 인덱스로 접근이 가능해야 하기 때문이다. 사용되지 않으면 invalid로 표시해주면 된다.

Memory Protection

또 다른 bit하나가 더 저장되는데, 페이지에 대한 접근 권한을 알려주는 bit이다.

Inverted Page Table

페이지 테이블의 용량이 너무 큰게 문제다.

Inverted Page Table Architecture

프로세스마다 존재하는 것이 아니라, 하나만 존재한다. 물리적인 메모리 프레임만큼 페이지 테이블의 엔트리가 존재한다. 페이지 테이블 설계가 물리적인 메모리에 논리적인 메모리가 매칭되어있기 때문에 페이지 테이블 전체를 찾아봐야 물리적인 메모리를 알 수 있다. 시간적인 제약이 많이 걸린다. 따라서 TLB 같은 register를 사용해서 문제를 해결할 수 있다.

주소 변환은 logical -> physical이 되어야 한다. 따라서 inverted page table은 우리 목적에 맞지 않다. 그래서 inverted page table은 다 찾아봐야 한다. 그래서 TLB 같은 register를 사용하는 것이다.

Shared Page

프로세스들 간에 같은 프로그램이면 같은 코드를 쓸 것이다. 이런건 공유를 해도 된다.

여기서는 read only이므로 shared memory와 조금 다르다.

Shared Pages Example

프로그램의 코드 부분은 공유할 수 있다. share 가능한 부분은 각각을 올리지 않고 하나만 올려도 된다.

Segmentation

Segmentation Architecture

Segmentation Hardware

segmentation에서는 의미 단위로 잘랐기 때문에 길이가 다 다르다. 그래서 limit을 가지고 있다.

Example of Segmentation

세그멘테이션은 페이징 기법보다 페이지 테이블 크기가 작기 때문에 메모리 낭비가 덜하다.

Sharing of Segments

Segmentation with paging

세그멘테이션과 페이징 기법을 혼합하는 방법이다. 세그먼트를 페이지로 구성하는 기법이다. 의미단위로는 segment 테이블에서 나누고, 세그먼트당 주소변환은 나중에 물리적인 주소로 바꾼다. 세그먼트당 페이지 테이블이 존재한다.

이 챕터에서 운영체제가 하는 일은 없었다. 다 하드웨어가 하는 역할이었다. cpu가 메모리에 접근하는데는 운영체제의 도움이 필요없다.