[OS] Memory Management

✔️ 논리적 주소와 물리적 주소 

논리적 주소와 물리적 주소

◾️ 메모리는 주소를 통해서 접근하는 매체이다.

◾️ 메모리 주소는 논리적 주소와 물리적 주소가 있다.

◾️ 논리적 주소 : 프로그램마다 가지고 있는 독자적인 주소이다. 

◾️ 물리적 주소 : 실제 메모리의 주소이다. 

◾️ 물리적 메모리 아래부분은 OS 커널이 위치한다. 상위 부분은 여러 프로그램이 섞여서 올라간다. 

◾️ 프로그램이 실행이 되려면 물리적인 메모리에 올라 가야한다. 이때 프로세스의 논리적 주소가 물리적 주소로 바뀌어야한다. 이를 주소 바인딩이라고 한다. 

◾️ Symbolic Address : 변수 등의 심볼로된 주소를 말한다. Symbolic Address는 컴파일 되어 숫자로된 논리적 주소로 바뀐다. 

 

주소 바인딩의 종류

 

주소 바인딩 시각화

 

◾️ Complie time binding : 컴파일 시점에 물리적인 주소가 결정된다. 즉 실행파일의 논리적 주소를 그대로 물리적 주소로 사용한다. 컴퓨터에서 프로그램이 하나만 실행되던 시절에 사용되었다. (그림에서 논리적주소를 그대로 물리적 주소로 사용하는 것을 볼 수 있다.)

◾️ Load time binding : 프로그램이 시작되서 메모리에 올라갈때 물리적 주소가 결정된다. (논리적 주소들이 500번대 물리적 주소로 바뀐 것을 볼 수 있다.)

◾️ Execution time binding : 기본적으로 프로그램이 시작할때 물리적 주소가 결정된다. 하지만 그 이후에 물리적 주소가 바뀔 수 있다. 메모리에서 프로그램이 쫓겨났다가 다시 올라가는 경우에 사용된다. (300번대 물리적 주소가 700번대 주소로 바뀌는 것을 볼 수 있다.) 현대 컴퓨터 시스템에서 사용한다. 

◾️ CPU는 명령어나 데이터를 읽을 때 논리적 주소를 사용한다. CPU는 논리적 주소를 하드웨어의 도움을 받아 물리적 주소로 변환해서 사용한다. 

◾️ 그림에서 보면 실행 파일이 통째로 메모리에 올라간다. 하지만 현대 OS는 실행 파일이 조각으로(페이지, 세그먼트) 나누어져 메모리에 올라간다. 

 

MMU

◾️ MMU는 주소변환을 지원해주는 하드웨어이다. 두 개의 레지스터를 이용해서 주소를 변환한다. 

 

 

◾️ CPU가 프로세스 P1의 논리적 주소 346번지에 있는 코드 또는 데이터를 요청한다. 이때 접근을 위해 물리적 주소 변환이 필요하다. 현재 프로세스 1번은 물리적 메모리에 적재되어 있다. 

◾️ 346은 프로세스 P1의 논리적 주소이다. 즉 프로세스 P1 내에서 346번째 줄이다. (그림을 확인 해보자)

주소 변환은 MMU 하드웨어를 통해 이루어진다. MMU는 relocation(base) register와 limit register 두 개로 구성된다.

◾️ relocation(base) register : 물리적 메모리에 적재되어 있는 프로세스 P1의 시작 위치를 가지고 있다.

◾️ limit register : 프로세스 P1의 크기다. 현재 P1은 0~3000번지까지 있으므로 크기는 3000임 물리적 메모리에 적재되어 있는 P1 공간을 넘는 접근을 막기 위한 용도(3000번대 이상 접근이 이루어 지면 trap 발생)

◾️ 논리적 주소 -> 물리적 주소 변환 : 논리적 주소 + relocation(base) register 

◾️ 위 그림에서는 프로세스 전체가 물리적 메모리에 적재되는데 실제로는 프로세스(프로그램)은 여러 조각으로 잘려서 올라간다. 

◾️ 위 일련의 주소 변환 과정 그리고 이 장에서 다루는 모든 주소 변환은 MMU와 같은 하드웨어단에서 처리된다.

 

◾️ 논리적 주소를 먼저 limit와 비교한다. limit을 초과하면, trap이 걸린다. (소프트웨어 인터럽트. 프로그램을 강제 abort하거나 함) limit를 초과하지 않는다면, 논리적 주소에서 base를 더한후 메모리에 적재된다. 

 

 

◾️ 프로그램에서 자주 사용된느 부분은 한정적이다. 오류 처리 루틴은 항상 발동하는 것이 아니기에 매번 모◾️ 두 물리적 메모리에 적재하는 것은 비효율적이다.

◾️ Dynamic Loading은 어떤 루틴이 필요할때 그 때 동적으로 물리적 메모리에 적재하는 것이다. 

◾️ Dynamic Loading은 프로그래머가 직접 수행한다. OS가 라이브러리를 제공해준다. 

◾️ Paging 기법은 OS가 직접 해주는 것이다. Dynamic Loading와 Paging은 공통점과 차이점이 있다.

 

 

◾️ Overrlay는 물리적 메모리에 필요한 부분만 적재한다. 하나의 프로세스(프로그램)을 물리적 메모리에 모두 적재하지 못하던 초창기 컴퓨터 시절에 사용하던 방법

◾️ 프로그래서가 수작업으로 구현했었다. 대단히 불편하고 어려운 프로그래밍 방법(OS 라이브러리 지원 없음)

 

◾️ 중기 스케줄러(swapper)가 swap out 시킬 프로세스를 결정한다. 

◾️ CPU 우선순위가 낮은 프로세스를 swap out 시킨다. 

◾️ swap out은 프로세스(프로그램) 전체를 통째로 하드 디스크로 쫓아내는 개념이다. 하지만 현대 컴퓨터 시스템에서는 프로그램 전체를 swap out 하는게 아니라 프로세스의 일부인 Page 단위로 swap out 한다. 

 

 

◾️ Linking : 프로그램은 Compile 되고 Linking을 통해 실행 파일로 만들어진다. Linker는 컴파일된 파일들을 하나로 묶어 실행 파일을 만든다. 

◾️ Static Linking : 라이브러리 코드가 실행 파일 코드에 포함됨

◾️ Dynamic Linking : 실행 파일안에 라이브러리 코드가 포함 되지 않음. 대신 라이브러리의 위치를 찾을 수 있는 stub이라는 포인터를 포함하는데, 라이브러리를 실행할때 stub을 통해 라이브러리를 호출하여 물리적 메모리에 적재하여 사용한다. 

◾️ 예제 1) Static Linking에서의 printf 함수 : 실행 파일안에 printf 코드가 포함된다. 

◾️ 예제 2) Dynamic Linking에서의 printf 함수 : 실행 파일안에 printf를 가리키는  포인터를 통해 printf를 사용한다. 

 

◾️ 물리적 메모리의 낮은 주소에는 OS가 상주하고 높은 주소에는 사용자 프로세스(프로그램)들이 위치한다.

◾️ Contiguous allocation(연속 할당) : 프로세스를 통째로 물리적 메모리에 적재하는 방법

◾️ Noncontiguous allocation(불연속 할당) : 프로그램을 구성하는 주소 공간을 잘게 조각내서 물리적 메모리리 여러 위치에 분산해서 적재하는 방법. 현대 컴퓨터 시스템에서 사용한다.

◾️ 불연속 할당은 Paging, Segmentation, Paged Segmentation 등의 방법이 존재한다. 

 

 

◾️ 연속 할당은 고정분할 방식과 가변 분할 방식이 존재한다. 

 

◾️ 고정 분할 방식 : 물리적 메모리의 사용자 프로세스 공간을 미리 파티션으로 나눈다. (external, internal ◾️ fragmentation 발생 가능 : 미리 물리적 메모리가 일정 크기로 잘라져있다. 따라서 작은 크기의 프로세스가 적재되면 파티션 내부적으로 빈 공간이 남는다.)

◾️ 가변 분할 방식 : 사용자 프로세스 공간을 미리 나누어 놓지 않는다. 동적으로 분할의 크기, 개수가 변할 수 잇다. (external fragmentation  발생 가능)

 

 

 

◾️ External fragmentation : 올라가려는 프로세스 크기가 커서, 물리적 메모리의 조각에 적재 불가

◾️ Internal fragmentation : 올라가는 프로세스 크기가 작아서, 물리적 메모리의 조각에 빈공간이 생김

 

◾️ 물리적 메모리의 어떤 파티션에 프로세스를 올려야할지 결정하는 방법 3가지 First-fit, Best-fit, Worst-fit이 있다.

 

 

 

 

 

◾️ 하나의 프로세스 주소 공간을 같은 크기의 Page단위로 나눈다. 

◾️ 물리적 메모리도 Page 단위로 나눠져있는데, 각각을 Page Frame이라고 한다.

◾️ 장점 : 물리적 메모리 공간의 효율이 증대된다. (추후 설명 참고)

◾️ 단점 : 주소 변환 과정이 복잡해진다. (하지만 하드웨어로 처리한다.), Internal fregmentation이 발생할 수 있다. 프로세스의 마지막 부분이 Page 단위로 딱 안 떨어질 수 있다. 예를 들어 프로세스 크기는 35이고, ◾️ Page 크기는 10이라고 하자 총 4개의 Page가 나온다. 마지막 Page에 5만큼의 Internal fregmentation이 발생하는 것을 알 수 있다. 프로세스의 크기는 항상 Page 크기의 배수가 아니다. Page를 더 잘게 조각내서 내부 조각의 영향력을 줄일 수 있다.

◾️ 주소 변환은 Page Table을 통해서 이루어진다. MMU 두 개의 레지스터로 변환 불가함.

 

 

◾️ Page는 물리적 메모리의 비어있는 Page Frame 어디던 적재될 수 있다.

◾️ Page Table에는 각 논리적 Page들이 물리적 메모리내의 어떤 Page Frame에 위치 하는지 알려주는 엔트리들이 존재한다. 

◾️ Page Table은 각 프로세스(프로그램)마다 별도로 존재한다. Page Table도 마찬가지로 물리적 메모리에 적재된다. 

 

◾️ 위 그림은 CPU가 논리적 주소를 물리적 주소로 변환하는 일련의 과정이다.

◾️ 논리적 주소는 p와 d로 이루어짐을 볼 수 있다. p는 Page 번호, d는 Page내의 어떤 위치에 있는지를 나타내느 offset이다.

◾️ d는 Page 내에서 얼마나 떨어져 있는지를 나타낸다. 즉 d는 각 Page 내에서 상대적인 위치이다.

◾️ f는 물리적 메모리의 Page Frame 번호이다. 

◾️ 논리적 주소의 p를 Page Table의 인덱스로 사용하여 Page Frame 번호를 알아내고 Page Frame에 offset을 더해서 물리적 주소 변환을 한다. 

 

◾️ PTBR : 물리적 메모리에 적재되어 있는 Page Table의 시작 주소를 보관한다.

◾️ PTLR : Page Table의 크기를 보관한다. 

◾️ 메모리 접근을 위해서는 먼저 Page Table을 접근하여 주소변환을 한 뒤 data/instruction 접근을 한다. 즉, 메모리 접근 연산에 2번의 메모리 접근이 필요하다. 

◾️ 메모리에 2번 접근하는 것은 시간이 오래 걸린다. 그래서 TBL라는 일종의 주소 변환 캐쉬를 사용한다. TLB는 CPU와 메인 메모리 사이에 존재하여 주소 변환을 해주는 계층이다. 

 

 

 

◾️ TLB는 메모리 주소 변환을 위한 별도의 캐쉬 메모리이다.  TLB는 Page Table에서 빈번히 참조 되는 일부 엔트리를 캐슁하고 있다. 

◾️ CPU는 논리적 주소를 Page Table을 통해 물리적 주소로 바꾸는 작업을 하기 전에, 먼저 TBL에 해당 엔트리가 캐쉬 되어있는지 확인한다. Hit 한다면 주소 변환을 시행한다. Hit시에는 메인 메모리에 1번만 접근하게 된다. (Page Table 접근은 하지 않기 때문이다.)

◾️ TLB에 원하는 엔트리가 캐쉬되어있는지 확인하기 위해서는 TLB 전부를 탐색 해야한다. TBL는 병렬 탐색이 가능한 레지스터로 구현된다. 따라서 병렬적인 탐색이 가능해서 빠르다. 

 

◾️ Page Table은 각 프로세스(프로그램)마다 존재 해야한다. 프로세스별로 논리적인 주소 체계가 다르기 때문이다. 

◾️ Page Table의 일부 엔트리를 캐쉬하고 있는 TBL 역시 프로세스마다 존재해야한다. Context Switch가 일어나면 TBL 정보를 다음 프로세스를 위해 모두 지워진다.

 

 

◾️ TBL 접근 시간은 입실론이다.

◾️ 메인메모리 접근 시간은 1 이다.

◾️ TBL로부터 주소 변환이 되는 비율은 알파이다.

◾️ 실제 메모리 접근 시간 : hit 시간 + miss 시간

◾️ hit :  (data/instructino을 위한 접근 시간 + TBL 접근시간) * 알파 : Hit 비율

◾️ miss : (data/instructino을 위한 접근 시간 + 페이지테이블 접근시간 + TBL 접근시간) * (1 - 알파 : Non-Hit 비율)

 

 

◾️ 주소 체계가 32 bit라면, 표현할 수 있는 전체 주소는 2^32개이다.

◾️ 프로세스(프로그램)의 논리적 메모리 크기가 물리적 메모리보다 커도 상관없다. Page 단위로 물리적 메모리에 적재되기 때문이다. 

◾️ 프로세스(프로그램)의 최대 가상 메모리 크기는 몇 bit 주소 체계를 사용하냐에 따라 달라진다. 

◾️ Page 크기 4KB일때 32Bit 주소 체계에서는 1M개의 Page 개수가 가능하다. 따라서 Page Table의 엔트리는 1M개가 필요하다.

◾️ Page Table의 각 Page Entry가 4B라면, 프로세스당 4M의 Page table이 필요하다. 공간이 너무많이 소요 되는것에 비해 프로세스의 주소 공간은 극히 일부만 사용된다. 2단계 Page Table을 사용해 공간의 효율을 높일 수 있다. 

 

 

◾️ 2단계 Page Table은 2개의 Page Table을 사용하기 때문에 공간을 더 많이 쓴다.

◾️ 하지만 사용되지 않는 주소 공간에 대해 outer-Page-Table에서 null로 표시한다.

◾️ 안쪽 Page Table는 그 자체가 Page가 되어 메모리에 올라간다. 

 

◾️ 메모리 주소는 byte 단위로 구분된다. 

◾️ Page 크기가 4KB(=2^12byte)일 때, 하나의 Page에는 2^12개의 주소가 존재한다. (0~2^12-1) 2^12 byte를 구분하기 위해서는 12개의 bit가 필요하다. 따라서 Page내의 주소 구분을 위한 offset 값 d는 12로 정해진다.

◾️ 안쪽 Page Table은 Page화 되어서 물리적 메모리에 적재된다. 안쪽 Page Table의 크기는 하나의 Page 크기이므로 4KB가 된다. 각 Page Table의 각 Entry 크기는 4B이다.

◾️ 안쪽 Page Table의 Entry는 1K개가 있다. 2^10가지 Entry를 구분하기 위해 10 bit를 사용한다. 

나머지 10bit는 outer Page Table에 준다. 

◾️ 만약 64 bit 주소체계를 사용하고, Page 크기는 4KB일 때 p1, p2, d는 각각 몇 bit일까?

 

◾️ 2단계 이상으로 Page Table을 사용할 수 있다. 하지만 한 번의 주소 변환을 위해 여러 단계를 거쳐야하는 단점이 있다.

◾️ 만약 4단계 Page Table을 사용할 경우 메인 메모리에 총 5번 접근해야한다. ( 4번은 메인 메모리에 적재되어 있는 4단계 Page Table에 대한 접근, 1번은 data/instruction을 위한 메인 메모리 접근)

 

◾️ 다시 정리해보자. 프로세스를 구성하는 Page 개수 만큼 Page Table의 Entry가 존재한다. 각 Entry에는 Page가 어떤 Page Frame에 올라가있는지에 대한 정보가 있다. 

◾️ 사실 Page Table Entry는 프로세스 주소 공간이 가질 수 있는 MAX 사이즈 만큼 생긴다. 그림에서 보면 프로세스는 5개의 Page로 나눠져 있는데, Page Table의 Entry는 7개인 것을 볼 수 있다. 

 

◾️ Page Table에 추가로 존재하는 정보가 있다. 

◾️ Vaild-bit : 사용되는 Entry를 뜻한다.

◾️ Invaild-bit : 사용되지 않는 Entry를 뜻한다.

◾️ Protection bit : Page 접근 권한에 대한 bit이다. 

◾️ 프로세스는 자기 자신의 Page Table만 접근할 수 있다. 즉, Protection bit는 다른 프로세스의 Page 접근 권한을 막는 용도가 아니다. Protection bit은 연산에 대한 권한을 막는 것이다. (예를들어 code 영역이 들어있는 Page를 읽으면 read-only로 세팅하고, data Page를 읽으면 read/write를 허용하는 세팅을 한다. code 영역이 들어있는 Page에 대해 write를 허용하면 안되지 않겠는가?)

 

 

◾️ 이제까지 Page Table은 프로세스마다 가지고 있다고 했다. 하지만 Inverted Page table은 시스템 안에 Page Table을 단 하나만 둔다. 

◾️ Inverted Page table의 Entry는 물리적 메모리의 Page Frame개수만큼 존재한다. (원래는 프로세스의 논리적 메모리 Page 개수만큼 있었다.)

◾️ 원래는 프로세스의 논리적 Page 번호를 사용해 물리적 주소를 얻어냈다.

◾️ 하지만 Inverted Page table을 사용하면 역으로, Page Frame을 통해 물리적 메모리 주소를 알아낸다.

◾️ 논리적 주소는 pid, p, d로 이루어져있다.

◾️ 예를들어 CPU가 논리적 주소에 대해 물리적 주소 변환을 하는 과정을 알아보자 

◾️ 먼저 Inverted Page table Full Scan해서 현재 프로세스 (pid)의 page(p)가 몇 번 Page Frame(f)에 있는지를 알아낸다. 

◾️ 몇 번 Page Frame에 있는지 알아냈다면, 그것을 offet (d)과 더해서 실제 물리적 메모리 주소를 알아낸다. 

◾️ Inverted Page table Full Scan은 Associative라는 별도의 하드웨어를 사용하여 병렬적으로 빠르게 이루어지게 한다. 

 

◾️ Shared Page는 다른 프로세스와 공유할 수 있는 Page를 말한다. 

◾️ Shared code 페이지는 read-only여야하고, 동일한 논리적 주소를 가지고 있어야한다.

(아래 그림에서 각프로세스의 ed1,ed2,ed3 논리적 위치가 같다는 것을 볼 수 있음) 

 

◾️ P1, P2, P3은 공통적으로 ed1, ed2, ed3 Page를 사용한다. 프로세스당 ed1, ed2, ed3을 각각 올릴 필요없이 한 세트만 메모리에 적재하고 Page Shared를 하면 효율적이다.

 

세그멘테이션

 

◾️ Segmentation은 프로세스의 주소 공간을 의미 있는 단위로 자른다. 균일한 크기로 자르는 Paging 기법과의 차이점이다.

◾️ 프로그램의 주소 공간은 크게 Code, Data, Stack으로 구성된다. 이를 각각 Code Segment, Data Segment, Stack Segment로 자른다. 의미 단위로 자르는 것이다. (함수 단위로 자를 수도 있다.)

◾️ 의미 단위로 잘랐기에 크기가 Page처럼 균일하지 않다. 따라서 위에서 살펴봤던 dynamic storage allocation problem이 발생할 수 있다. 

 

 

◾️ 위 그림은 Segmentation 기법에서 CPU가 논리적 주소를 물리적 주소로 바꾸는 과정이다.

◾️ CPU가 논리적 주소를 주소면 Segment 번호 s를 segment table의 인덱스로 사용하여 물리적 주소를 알아낸다. 

◾️ limit는 Segment 하나의 크기이다. (Page와 다르게 균일하게 조각나지 않으므로 각 Segment마다 limit가 존재)

과정을 살펴보자. 먼저

◾️ 논리적 주소의 s를 프로세스(프로그램)이 사용한 총  Segment개수 즉, STLR와 비교한다. 만약 s가 STLR보다 크다면, trap이 걸린다. 

◾️ 논리적 주소의 d를 limit와 비교한다. 만약 d가 limit 보다 크다면, 해당 Segment 크기를 넘어서는 offset(하나의 세그먼트 내부에서 떨어진 정도)이다. 따라서 trap이 걸린다.  

◾️ 예를들어 어떤 프로세스가 5번 Segment(s=5)를 요청했다. 하지만 이 프로세스의 STLR은 2 이다. 따라서 trap에 걸린다. 

 

 

◾️ Segment는 의미 단위로 잘라진다고 했다. 따라서 우리는 vailid/invaild bit를 통해 의미 단위로 권한을 줄 수 있다. 

또한 의미 단위이길래 공유와 보안에 있어서 유리하다. (어떤 Segment를 공유한다면, 의미 단위로 고유를 하지 않겠는가?)

◾️ Segment는 균일하게 나누어지지 않기 때문에 External framentation이 발생할 수 있다. 따라서 first / best fit 등의 기법을 사용해야한다. (Page는 균일하게 잘라지기에 External fragementation이 발생하지 않는다. Page Frame도 균일하기 때문. 하지만 Internal fragementation은 발생할 수 있다. 

 

◾️ Paging 기법의 Page는 많이 만들어진다. 그에 따른 table도 필요하기에 메모리 낭비가 심하다. Page를 잘게 자르면 더 그럴 것이다.)

◾️ Segment는 실제적으로 많이 만들어지지 않는다. 

위 그림은 하나의 프로세스(프로그램)을 구성하는 5개의 Segment를 보여준다. 의미 단위로 쪼개진 것을 확인할 수 있다. 

 

◾️ Segment도 Page와 마찬가지로 Share할 수 있다. 

◾️ 그림에서 보면 프로세스 P1과 P2가 공통적으로 사용하는 editor라는 Code 영역 Segment를 공유해서 쓰고있다. (editor Segment는 물리적 메모리에 1개만 적재 되어있다.)

 

그림1

◾️ 위 그림은 Segmentation과 Paging 기법을 혼합해서 사용하는 기법이다.

◾️ Segment를 다시 Page로 자르는 기법이다. 일련의 주소 변환 과정을 통해 알아보자.

1. 먼저 STBR(물리적 메모리에서의 Segment Table 시작 위치를 저장하고 있는 레지스터)로 Segment Table을 찾는다.

2. 논리적주소의 s (Segment 번호)를 Segment Table의 인덱스로 사용하여 Entry를 찾는다. 그리고 해당 Segment를 구성하는 Page의 Page Table 시작 주소를 얻는다.(page-table base) (s + STBR) 이때 offset d가 Segment lenth(Iimit) 보다 크면 trap에 걸린다. 

3. Segment 논리적 주소의 offset d에서  p와 d'를 얻어낸다. p는 Page 번호이고, d' Page offset이다. 위에서 얻어낸 page-table base에 p를 더하면 Page Table에서 해당 Page의 Page Frame을 f를 얻을 수 있다.

4. Page Frame f와 Page offset d'를 사용하여 물리적 주소를 최종적으로 얻어낸다. 

◾️ 위와같이 Segment를 다시 Page로 자르면 External fragmentation 등의 memory allocation 문제가 발생하지 않는다. (실제로 오리지날 Segmentation 기법은 사용되지 않는다.)

 

 

정리

 

◾️ 논리적 주소를 물리적 주소로 바꾸는 주소 변환에 있어서 사실 OS의 역할은 없다.

◾️ 주소 변환 일련의 과정은 하드웨어적으로 이루어진다. 

◾️ 만약 주소 변환을 할때마다 OS가 개입한다고 생각해보자. CPU는 프로세스를 잡고 있다가, 주소 변환을 원하면 OS를 잡아야한다. 그리고 OS에서 주소 변환을 한후 다시 프로세스를 잡아야한다. 

◾️ 즉, CPU가 주소변환을 할 떄마다 프로세스와 OS 사이를 계속 왔다갔다 해야한다. 오버헤드가 너무커서 현실적으로 불가능하다. 

◾️ OS가 개입하는 타이밍은 프로세스가 I/O접근을 할때다. 프로세스는 I/O에 직접 접근하지 못하기 때문이다.