논리적 주소와 물리적 주소

심볼 주소(Symbolic Address)

변수명, 함수명같이 코드에서 볼 수 있는 심볼로 된 주소

논리적 주소(Logical Address)

프로세스마다 가지고 있는 독립적인 주소이다. 해당 프로세스 내부에서만 사용되는 주소이다. 가상 주소(Virtual Address)라고도 한다.
각 프로세스마다 0번지 부터 시작하는 주소이다.
CPU는 명령어를 실행할 때, 논리적 주소를 보고 물리적 주소에 접근한다.

물리적 주소(Physical Address)

메인 메모리에 실제로 저장되는 주소이다.

주소 바인딩

• 심볼 주소 → 논리적 주소 → 물리적 주소

심볼 주소에서 논리적 주소로 바인딩 되는 시점은 컴파일이 될 때이다.
논리적 주소에서 물리적 주소로 바인딩 되는 시점은 방식에 따라 다른데 세 가지 방식이 있다.

컴파일 타임 바인딩

컴파일시에 물리적 주소가 정해지는 방식으로, 논리적 주소와 물리적 주소가 동일해진다.(이런 코드를 절대코드라고 부른다.) 물리적 주소의 위치가 변경되어야 할 때 재컴파일을 해야하는 단점이 있다.

로드 타임 바인딩

파일이 메모리에 적재될 때 물리적 주소가 정해지는 방식이다.

런타임 바인딩(= Execution time binding)

실행 중간에도 물리적 주소를 바꿀 수 있는 방식이다. 보통 현대 OS에서는 이 방식을 사용한다.
하드웨어(MMU)의 도움이 필요하다.

MMU(Memory Management Unit)
논리적 주소를 물리적 주소로 변환하는 하드웨어이다.
relocation register와 limit register를 가지고 있는데, reloacation register는 물리적 주소 시작 번지를, limit register는 접근하려는 물리적 주소의 길이를 저장한다.
입력받은 논리적 주소에 레지스터에 있는 물리적 주소 시작 번지를 더해 물리적 주소를 반환한다.
또, 두 레지스터를 사용해, 물리적 주소로 변환할 때 범위외에 주소에 접근하는 것을 방지한다.

스와핑(Swapping)

프로세스를 일시적으로 메모리에서 back store로 쫓아내는 것을 의미한다.
효율적으로 스와핑을 하려면 런타임 바인딩을 해야한다. 나머지 바인딩은 쫓겨나고 다시 돌아올 때, 다시 컴파일or로드를 하지않는 이상 똑같은 주소로 돌아와야 하기 때문. 런타임 바인딩은 실행도중에도 물리적 주소를 바꿀 수 있어서 괜찮다.

보통 데이터에 접근할 때 seek time(디스크 헤더가 움직이는 시간)이 크나 용량이 방대한 스와핑은 transfer time(데이터 전송 시간)이 시간의 대부분을 차지한다.

Page 단위로 쫒겨나는 것도 스와핑이라고 하기도 하지만, 원칙적으로는 프로세스의 모든 내용이 쫓겨나는 걸 스와핑이라고 부른다.

동적 적재(Dynamic Loading)

프로세스의 전체를 메인 메모리에 다 적재하지 않고, 루틴이 호출될 때 메모리에 적재하는 방식이다.
OS가 지원하지 않고, 사용자가 프로그램을 설계할 때 알아서 적용해야 한다. 그렇다고 프로그래머가 일일이 적용하는 건 아니고 OS가 라이브러리로 제공한다.

가끔 발생하지만 실행할 코드가 많은 오류 처리 루틴 적재에 효율적이라고 한다.

비슷한 개념으로 Overlays 라는 것도 있는데, 얘도 필요한 정보만 메모리에 올리는 것을 의미한다. 다만 동적 적재와 역사적으로 차이가 있는데, Overlays는 초기에 프로그래머가 수작업으로 직접 메모리에 올리는 것을 설정했던 것을 의미한다. 동적 적재는 라이브러리가 도와줌.

동적 연결(Dynamic Linking)

• Linking : 컴파일된 파일들을 묶어서 실행 파일로 만드는 과정
• 정적 연결 : 라이브러리가 프로그램 실행 파일 코드에 실제로 포함된 경우

반대로 동적 연결은 라이브러리 코드가 실제로 포함되지 않고, 라이브러리를 호출하는 부분에 stub 코드를 둔다. stub코드는 라이브러리를 저장한 별도의 파일을 가리키는 포인터를 지닌다.

동적 연결을 하는 라이브러리를 동적 연결 라이브러리(DLL)라고 부른다. 같은 라이브러리를 사용하는 프로세스들이 공유한다.(그래서 shared 라이브러리라고도 부른다.) 중복적으로 코드를 할당하지 않아도 되기에 공간적으로 이득이다.

동적 적재와는 다르게 동적 연결은 OS의 도움이 필요하다. 라이브러리를 직접 사용했던 동적 적재와는 다르게 자동으로 지원해주는 뭔가가 있나봄.

연속 할당과 불연속 할당

메인 메모리는 두 가지 영역으로 나누어져 있는데, 커널 코드를 저장하는 OS 상주 영역과 사용자 프로세스 영역이 있다.
사용자 프로세스가 프로세스의 code, stack data등이 올라가는 영역으로 물리적 주소로 접근할 수 있는 영역이다.
사용자 프로세스 영역에 프로세스를 연속적으로 할당하는 방식과 불연속적으로 할당하는 방식이 있다. 두 방식을 알아보자!

• 연속 할당 : 한 프로세스가 크게 한 덩어리로 연속적으로 할당됨.
• 불연속 할당 : 하나의 프로세스가 쪼개져서 산발적으로 할당될 수 있음.

연속 할당

고정 분할 방식과 가변 분할 방식으로 나뉜다.

고정 분할 방식

• 메인 메모리를 미리 쪼개둔다.
• 쪼개둔 곳에 프로세스를 할당한다.
  외부조각과 내부조각이 생길 수 있다.

  외부조각 : 할당된 영역들 사이에 비어있는 영역. 외부조각이 산발되어 있으면, 공간 낭비!
  내부조각 : 쪼개져있던 영역이 프로세스 코드보다 더 커서 할당된 영역 중 사용되지 않는 영역

가변 분할 방식

• 프로세스 실행될 때마다 그냥 차곡차곡 쌓아서 저장한다.
• 외부 단편화(외부조각)가 생길 수 있다. (프로세스가 종료되면 그 자리가 그대로 외부조각됨)

동적 메모리 할당 문제 해결 방법

메모리의 가용 구간이 여러개 있을 때, 프로세스를 어느 영역에 할당할 것인가?

• 최초 적합(First fit)
  • 사이즈가 P보다 큰 것중 제일 먼저 탐색된 가용 구간 선택
• 최적 적합(Best fit)
  • 사이즈가 P이상인 가용 구간 중 가장 작은 것 선택
• 최악 적합(Worst fit)
  • 사이즈가 P이상인 가용 구간 중 가장 큰 것 선택 (프로세스들의 크기가 거의 같을 때 유리할 수도 있다는데 잘 모르겠다. 외부 조각 최소화. 프로세스들이 빨리 끝날 때 효율적인건가?...)

Compection

외부 단편화들을 한 군데로 몰아서 활용성 높이는 방법.
단, 한 군데로 모는데 비용이 많이 듦. 또 런타임 바인딩 시에만 적용 가능하다.
전체를 다 밀지 않고, 최소한만 이동시키는 방식도 있다.

불연속 할당

Paging

모든 프로세스의 데이터를 Page단위로 나눈다. 메인메모리에 할당할 때도 Page단위로 할당한다.
외부 단편화와 Compection을 신경쓰지 않아도 된다.
내부 단편화는 생길 수 있다. 프로세스의 데이터가 항상 Page단위로 깔끔하게 나눠지지 않을테니 마지막 영역은 Page보다 작을 수 있기 때문.

논리적 주소는 페이지 번호 p와 페이지 오프셋 d로 이루어져있다.
논리적 주소의 단위를 페이지라고 하고, 물리적 주소의 단위를 프레임이라고 한다.
메모리에는 페이지와 대응하는 프레임을 저장하는 페이지 테이블이 존재한다.

페이징에서 논리적 주소를 물리적 주소로 변환하는 과정은 다음과 같다.

• CPU가 논리적 주소를 가지고 페이지 테이블에 접근
• 페이지 테이블에서 논리적 주소의 p를 통해 적절한 프레임을 찾아낸다.
• 프레임에 논리적 주소의 오프셋 d를 붙여 물리적 주소를 알아낸다.

페이지의 base주소를 저장하는 PTBR(Page Table Base Register)과 페이지 길이를 저장하는 PTLR(Page Table Length Register)가 존재한다.

페이징시, 메모리에 두 번 접근하게 된다.
1. 페이지 테이블에 접근
2. 실제 데이터를 얻어오기 위해 메모리 접근

속도를 향상하기 위해 TLB라는 레지스터를 사용한다.

TLB

메인메모리와 CPU사이에 존재하는 레지스터이며, 페이지 테이블이 가지고 있는 내용을 캐싱하고 있다.
페이지를 찾을 때 일일이 순회하지 않고 하드웨어적으로 병렬 탐색을 지원해서 빠르다.

TLB 접근 시간이 t, TLB hit 확률을 h라고 할 때, TLB를 사용했을 때 걸리는 시간은
(1+t)h + (2+t)(1-h) = 2 + t - h이다. (hit이면 페이지 테이블 접근 안해도 돼서 메모리에 1번 접근, hit이 아니면 메모리에 두 번 접근)
보통 t < h이므로 더 이득이라고 함.

페이지 테이블 크기 계산

32bit시스템을 사용한다고 해보자.
논리 주소와 페이지 테이블의 각 entry는 32bit이다.

논리 주소가 32bit이므로, 2^32개(4GB)의 주소를 표현할 수 있다.
페이지의 크기는 보통 4KB이다. 4GB의 주소를 4KB의 페이지로 표현하면 총 1MB개의 페이지를 저장할 수 있다. (4GB/4KB)

즉, 페이지 테이블의 entry또한 1MB개 필요해지고, 각 페이지 테이블의 entry는 4byte라고 하면, 페이지 테이블의 크기는 4MB가 된다.(1MB * 4B)

Valid & Invalid Bit

해당 페이지의 frame이 사용 가능한가를 표기

Protection Bit

해당 페이지의 접그 권한 표기

• 어떤 연산에 대해 접근 권한이 있는가?
  • code 영역일 경우 변경되면 안되므로 readOnly
  • data & stack 영역일 경우 read & write

Two Level Page Table

페이지 테이블이 차지하는 공간을 줄이기 위해 페이지 테이블을 두 단계로 분리

Inverted Page Table

Page 번호로 Frame을 찾는 방식이 아니라, 반대로 모든 Frame을 순회하며 나의 Page번호를 찾아내는 방식.

왜 이런 방식이 있을까?
위 페이지 테이블 계산에서 나왔듯이, 페이지 테이블의 크기는 매우 크다. 보통 각 프로세스마다 자신의 페이지 테이블을 들고있는데, 공간을 많이 차지한다. Inverted Page Table을 사용하면 프레임의 개수만큼만 정보를 저장하면 돼서 공간적으로는 이득이다.

Shared Page

다른 프로세스들과 공유하는 페이지이다.
각 프로세스 들이 동일한 논리 주소를 가져야 한다.(어케앎?)

Segmentation

페이지처럼 전부 고정된 크기로 자르지 않고, 의미 단위로 자른다. code, data, stack이냐에 따라 크기가 달라질 수 있다.

페이징보다 테이블 크기가 적다. 페이지 테이블은 페이지의 개수만큼 늘어나는데, 페이지가 보통 4KB라서 개수가 많다. 세그먼트는 4KB보다 더 큼직하게 가져갈 수 있기 때문에 테이블이 더 작을 확률이 크다.

대신 세그먼트들의 길이가 동일하지 않으므로 외부 단편화가 발생한다.

세그먼트 테이블이 세그먼트의 base와 limit을 가지고 있다.

Paged Segmentation

세그먼트가 페이지 형태로 나뉘어진다. 세그먼트가 여러 개의 페이지 형태로 이루어져 있다.

세그먼트 주소를 논리적 주소로 변환하고, 논리적 주소로 물리적 주소를 찾아가는 방식.

기존 Segmentation과의 차이점 : 세그먼트 테이블이 세그먼트의 base address를 가지고 있는게 아니라 세그먼트를 구성하는 page table의 base address를 가지고 있다.