메모리 할당

메모리는 값 저장용 배열이며, CPU는 주소 값으로 특정 위치에 접근합니다. 하나의 프로세스는 메모리를 모두 사용할 수 있지만, 두 개 이상의 프로세스에서는 메모리 자원 분배가 중요합니다.

주소 할당 (Address Binding)

프로그램은 원래 디스크에 저장되어 있습니다. 프로그램이 실행되기 위한 단계는 다음과 같습니다.

1. 메인 메모리로 올라와서 프로세스가 되어야 합니다.
2. 프로세스는 실행될 때 메모리에 적재해 놓은 명령어와 데이터에 접근하여 사용하게 됩니다.
3. 이 프로세스가 종료되면 해당 프로세스가 사용하던 메모리 공간은 가용(available) 공간이 되어 다른 프로세스가 사용할 수 있게 됩니다.

프로그램이 이렇게 메모리로 올라올 때 메모리의 어느 부분을 사용할 지를 결정을 해 주어야 하는데 이것이 바로 주소 할당에 관한 문제입니다.

즉 메모리 접근을 위한 물리적인 주소를 결정해주는 것입니다.

주소 공간이 바인딩(binding)되는 시점에 따른 3가지 할당 방법

1. Compile Time Binding (컴파일 시간 바인딩)

• 컴파일이 실행될 때 주소가 먼저 결정됩니다.
• 컴파일 과정에서 어셈블리 코드로 변경될 때, 절대 코드(absolute code)가 생성되어 정확한 주소의 값이 결정됩니다.
• 만일 주소를 바꿔주고 싶다면 다시 컴파일을 해야 합니다.

2. Load Time Binding (로드 시간 바인딩)

• 프로세스가 메모리 내에 어디로 올라오게 될지를 컴파일 중에 알지 못하면, 컴파일러는 우선 재배치 가능 코드(relocatable code)를 생성하게 됩니다.
• 실제 메모리의 위치는 프로그램이 메인 메모리에 실제로 로드(load)될 때 결정되게 됩니다.
• 만일 메모리의 위치를 바꾸어야 한다면, 사용자 코드를 다시 로드하기만 하면 됩니다.

3. Execution Time Binding (실행 시간 바인딩)

• 프로그램이 실제로 실행될 때 메모리 주소가 동적으로 결정됩니다.
• 이 방법을 사용하기 위해서는 MMU라고 하는 특별한 하드웨어 장치가 필요하며, 대부분의 운영 체제에서 이 실행 시간 바인딩을 사용합니다.

Logical vs. Physical Address Space

논리적 주소 : CPU가 생성하는 주소. 가상 주소(virtual address)라고도 불립니다.

물리적 주소 : 메모리가 취급하는 주소

두 주소는 컴파일 시간 바인딩과 적재 시간 바인딩에서는 서로 같은 값을 가집니다.

하지만 실행 시간 바인딩 기법에서는 서로 다른 값을 가지게 됩니다. 실행 시간에 이 논리적 주소를 물리적 주소로 바꿔주는 것이 바로 MMU입니다.

MMU(메모리 관리기, Memory Management Unit)

실행 시간에 논리적 주소를 물리적 주소로 바꿔주는 하드웨어 장치입니다.

가장 단순한 MMU 기법을 예로 들자면, 재배치 레지스터(Relocation Register)에 있는 값 만큼을 CPU에서 받은 논리적 주소에 더해줘서 최종적인 물리적인 주소를 만들게 됩니다.

이 방법은 실행 시간 바인딩 기법 중 하나이며, 대부분의 운영 체제에서 사용됩니다.

연속 메모리 할당 (Continuous Memory Allocation)

• 가장 쉬운 메모리 할당 방법입니다.
• 순서
  1. 메모리의 일부를 Kernel에게 할당
  2. 남은 메모리들을 프로세스들에게 할당
• 하나의 프로세스는 메모리에서 하나의 연속된 메모리 섹션만을 할당받습니다.

Continuous Memory Allocation

이 시스템에서는 두 개의 레지스터가 필요합니다.

• 리미트 레지스터(Limit Register) : 리미트 레지스터는 할당된 메모리의 크기에 대한 값을 저장 → 리미트 레지스터의 값보다 큰 논리적 주소는 메모리에 접근할 수 없습니다.
  
• 재배치 레지스터 : 재배치 레지스터는 프로세스에 할당된 물리적 주소의 가장 작은 값을 저장

따라서 할당된 메모리의 범위 내의 값을 가지는 논리적 주소 값들은 리미트 레지스터를 통과해 재배치 레지스터의 값과 합쳐져서 물리적 주소를 만들어냅니다.

다른 물리주소를 만들기 위해선 당연히 리미트 레지스터와 재배치 레지스터가 가지고 있는 값은 각각의 프로세스마다 달라져야 합니다.

• Dispatcher가 레지스터들의 값을 바꿔주게 됩니다.

연속 메모리 할당의 종류

Fixed-partition scheme (현재 사용 X)

• 각 프로세스들에게 할당해주는 각각의 파티션들의 사이즈를 고정해서 할당.
  • 즉 어떤 프로세스에게 할당을 해주든 1GB면 1GB, 512MB면 512MB와 같은 형식으로 모두 똑같은 사이즈로 할당을 해주게 됩니다.
• 하나의 프로세스는 하나의 파티션만 할당.
• 이러한 시스템에서는 멀티프로그래밍에서 한 번에 실행될 수 있는 프로세스의 개수가 이 메모리의 파티션의 총 개수로 인해서 정해지게 됩니다.

Variable-partition scheme

• 파티션들은 모두 다른 크기의 사이즈를 가지며 운영체제는 어떤 파티션이 사용되고 있고 비어있는지를 알려주는 테이블을 가지고 있어야 합니다.
  • Hole : variable-partition scheme에서 메모리 내에 아직 할당되지 않은 부분.

• 새로운 프로세스가 도착하면 운영체제는 남은 Hole 중에서 적절한 크기의 Hole을 골라 프로세스에게 할당을 해줍니다.
• 너무 큰 Hole을 할당해주면 Hole이 반으로 갈라질 수도 있고, 효율적인 메모리 사용이 힘들 수도 있습니다. 물론 프로세스가 종료되면, 메모리는 반납되어 다시 Hole이 되게 됩니다.
• 반납된 부분과 다른 Hole이 바로 붙어있다면 둘은 합쳐져 큰 하나의 Hole이 되어 다른 프로세스를 기다리게 됩니다.
• 그래서 어떤 Hole을 어떤 프로세스에게 할당해주는 지를 정해주는 것은 메모리 효율을 위해 굉장히 중요한 부분입니다. 여기에는 3가지 방법이 존재합니다.
  1. First fit: 프로세스에게 충분한 크기의 Hole을 찾으면 바로 그곳을 할당시켜준다.
  2. Best fit: 남아있는 Hole을 모두 살펴본 뒤 그중에 프로세스에게 맞는 Hole 중 가장 작은 Hole을 할당시켜준다.
  3. Worst fit: 남아있는 Hole을 모두 살펴본 뒤 그 중에 가장 큰 Hole을 할당해준다

Fragmentation

• 메모리에서 현재 사용되지 못한 부분
• Externel Fragmentation : Hole들이 다 합친다면 충분한 크기를 가지지만 너무 작게 여러 곳에 분포해서, 프로세스에게 할당될 만큼 충분히 크지 않아서 사용되지 못하는 부분. paging으로 예방할 수 있습니다.
• Internel Fragmentation : Fixed-partition scheme과 같은 상황에서 프로세스에게 필요 이상으로 큰 파티션이 할당되어, 할당되었지만 사용되지 않는 부분을 뜻합니다.

Paging

메모리는 비연속적인 물리적 주소 공간을 할당해 줄 수도 있습니다. 그리고 이런 비연속적인 할당을 통해 external fragmentation을 예방할 수 있습니다.

페이징(Paging)은 메모리를 일정한 크기의 블록으로 분할하여 논리적 주소와 물리적 주소를 매핑하는 기법입니다.

1. 페이징 (Paging)

페이징에서 사용되는 개념

1. 물리 메모리(physical memory)는 여러 프레임(frame)으로 나뉘어집니다.
   • 프레임(frame): 고정된 사이즈의 블록
2. 논리 메모리(logical memory)는 여러 페이지(page)로 나뉘어집니다.
   • 페이지(page) : 프레임과 같은 사이즈의 블록
3. 논리 주소(logical address)는 페이지 번호(page number)와 페이지 변위(page offset)로 이뤄져 있습니다.
   • 페이지 번호 : 페이지 테이블에서의 인덱스로 사용
   • 페이지 변위 : 페이지 내에서 데이터를 찾을 때 사용
4. 물리 주소는 프레임 번호(frame number)와 프레임 변위(frame offset)로 이루어지게 됩니다.

페이징 과정

1. 한 프로세스가 실행되기 위해 도착하면, 그 프로세스가 몇 개의 페이지를 사용해야 하는지를 조사합니다.
2. 하나의 페이지는 하나의 프레임을 필요로 하기 때문에 메모리에 가용한 프레임의 수를 고려해주어야 합니다.
3. 프레임의 개수에 여유가 있다면, 프로세스에게 필요한 수의 프레임들을 할당해 줍니다.
4. 프로세스가 프레임을 사용할 때마다 페이지 테이블에 프레임의 번호를 기록해줍니다.

이런 방식을 사용하면 각각의 프로세스들은 물리 메모리에서 굳이 연속된 파티션을 할당 받을 필요가 없습니다. 물리 메모리의 어떤 프레임이든 비어있다면 사용할 수 있기 때문에 external fragmentation은 사라지게 되고, 메모리 사용의 효율을 크게 늘릴 수 있습니다.

페이지의 사이즈

• 페이지 사이즈가 너무 작아지게 되면 페이지 테이블이 커지게 되어 공간이 낭비될 수 있습니다.
• 디스크의 입장에서 볼 때 페이지의 크기가 클수록 유리하기 때문에 일반적으로는 메인 메모리가 커짐에 따라 페이지의 크기도 덩달아 커져왔습니다.
• 현재는 Windows 10은 4KB와 2MB의 페이지를, Linux는 기본적으로 4KB의 페이지를 지원합니다.

2. 하드웨어 지원

운영체제는 이러한 페이지 테이블을 사용하기 위해 여러 방법들을 지원합니다

첫 번쨰 방법

• 페이지 테이블 정보를 저장하고 있는 레지스터 파일을 CPU 내에 저장해 두는 것.
• 가장 쉬운 방법
• 장점 : CPU 내에 페이지 테이블이 있기 때문에 굉장히 빠르게 처리
• 단점 : 큰 사이즈의 페이지 테이블은 사용 불가

두 번째 방법

• 페이지 테이블을 메모리로 빼고 CPU에는 페이지 테이블의 주소 값을 저장하는 레지스터만 남기는 것. (이 레지스터를 PTBR(Page-Table base register)이라고 합니다.)
• 장점 : Context Switch Time을 줄일 수 있습니다.
  • 페이지 테이블은 프로세스마다 존재하기 때문에 앞에서의 방법은 Context switch가 일어나면 CPU 내의 페이지 테이블을 완전히 다 새로운 테이블로 바꿔줘야 하지만, 이 방법에서는 PTBR만 바꿔주면 되기 때문입니다.
• 단점 : 메모리에 접근하는 횟수가 너무 많아진다는 것
  • 원래 메모리 접근 자체가 시간이 많이 걸리는 작업입니다. 그런데 이런 방법을 사용하면 하나의 데이터를 읽어오기 위해 2번이나 메모리에 접근해야 합니다.
  • 우선 메모리에 있는 페이지 테이블에 접근해서 프레임 번호를 알아오고, 이것을 다시 CPU로 가져와서 MMU에서 물리 주소를 만든 뒤, 그 주소를 따라 다시 메모리로 가서 원래 원하던 데이터를 가져와야 하는 번거로운 작업을 거쳐야 하는 것입니다.

세번째 방법

두 번째 방법의 단점을 해결하기 위해 TLB(Translation Look-aside Buffer)라는 것을 사용합니다.

TLB

• 특수한 작은 소형 하드웨어 캐시
• TLB 내의 각 항목은 key(페이지 번호)와 value(프레임 번호)로 구성. 페이지 테이블과 유사한 형태.
• TLB는 CPU 내에 있는 페이지 테이블의 일부를 저장하는 임시 저장소입니다.

데이터를 찾아야 할 때는 먼저 TLB를 확인합니다. TLB에 내가 원하는 페이지 번호가 있으면 해당 프레임 번호를 가져와서 메모리의 페이지 테이블을 조회합니다.

이 임시 저장소가 효율적으로 작동하려면 최대한 자주 사용하는 페이지들이 TLB에 저장되어 있는 것이 좋습니다.

• 만일 원하는 페이지가 TLB에 존재한다면 이것을 TLB Hit라고 부르고, 존재하지 않는다면 이것을 TLB Miss라고 부릅니다.
• TLB가 가득차면 TLB에 어떤 페이지를 남기고 어떤 페이지를 삭제시킬지를 고민해 보아야 하며, 최대한 TLB Hit를 높일 수 있는 알고리즘을 이용해 TLB를 관리하는 것이 중요합니다.

Context Switch가 일어나면 원칙적으로는 TLB의 모든 정보를 지워버려야 합니다.

모든 프로세스는 자기 자신의 페이지 테이블과 논리적 주소 공간을 가지고 있기 때문에, 프로세스 간에 페이지의 번호가 같은 경우도 충분히 있을 수 있습니다. 그래서 CPU 내에 다른 프로세스의 TLB가 남아있다면 다른 프로세스의 메모리 공간에 잘못 접근하는 사태가 벌어질 수 있기 때문입니다. 앞에서도 말했지만, 다른 프로세스의 메모리 공간에 접근하는 것은 금지되어 있습니다.

하지만 Context Switch가 일어날 때 마다 모든 TLB를 지우고 새로운 정보를 입력하는 것은 너무 비효율적이라고 생각할 수 있습니다.

그래서 여기서는 ASID(Address-Space IDentifiers)라는 것을 사용합니다. TLB에 key와 value 이 외에 ASID라는 정보를 추가로 제공하는 것인데 이 ASID는 해당 페이지가 어떤 프로세스의 페이지인지에 대한 정보를 담고 있습니다. 다시 말해, 페이지를 검색할 때 우선 ASID를 살펴보고 지금 CPU에서 실행 중인 프로세스의 페이지들만 고려하여 검색을 하는 것입니다.

페이지 보호 (Page Protection)

페이지 테이블을 만들 때, 메모리 보호를 위해서 각 페이지들에 추가적인 비트들을 부여하여 사용할 수 있습니다.

비트종류

Read-write/Read-only bit

Read-write/Read-only를 표현하는 비트입니다. 당연히 Read-write 모드일 때만 데이터를 수정할 수 있으며 Read-only 모드에서는 읽을 수만 있습니다.

Valid-invalid bit

이 비트가 valid로 설정되어 있으면, 해당 페이지가 프로세스의 논리 주소 공간 안에 있는 합법적인 페이지라는 것을 나타냅니다. 운영체제는 이 비트를 통해서 해당 페이지에 접근을 허용할 것인지 말지를 결정합니다.

예를 들면 14비트의 논리적 주소 공간을 갖는 시스템은 0~16383의 주소를 사용할 수 있습니다. 그리고 이 중에 프로그램이 0~10468까지의 주소만 사용할 수 있다고 가정하면, 2KB짜리 페이지를 0번부터 5번까지 6개 사용할 수 있습니다. 이렇게 되면 페이지 테이블에 0~5번의 페이지에는 valid, 그리고 이 외의 페이지들에는 invalid로 설정해 줄 수 있습니다.

테이블 길이 레지스터(PTLR, Page Table Length Register)

또한 몇몇 시스템에서 사용하는 방법으로, 페이지 테이블의 크기를 저장해 둡니다.

말 그대로 페이지 테이블의 사이즈를 저장하는 레지스터로써, 프로세스가 제시한 주소가 유효한 범위 내에 있는 지를 확인하는 용도로 사용됩니다.

공유 페이지 (shared Pages)

페이징의 큰 장점 중 하나가 바로 코드를 쉽게 공유할 수 있다는 것입니다. 프로세스들은 코드 페이지들이 만약 재진입 가능 코드(Reentrant code, or Pure code)라면 해당 코드 페이지들을 공유할 수 있습니다.

재진입 가능 코드

수행되는 동안 절대 변하지 않는 코드로써(프로그램 내의 어떤 명령어도 프로그램 내의 다른 명령어를 위한 변수들을 수정시키지 않는다는 뜻) 프로그램들이 언제든 변수가 수정되지 않았다는 확신을 가지고 코드 내에 진입할 수 있도록 만들어 줍니다.

이렇게 재진입 가능 코드의 경우에는 코드를 물리 메모리에 올려놓으면 여러 프로세스들이 이 코드를 공유하여 사용할 수 있습니다. (라이브러리와 비슷한 느낌)

페이지 테이블 구조 (Page Table Structure)

1. 계층적 페이징(Hierarchical Paging)

배경

현재 사용되는 많은 컴퓨터들은 굉장히 큰 주소 공간을 가집니다. 주소 공간이 커진다는 말은 페이지 테이블도 함께 커질 수 밖에 없다는 것을 뜻합니다. 32비트 논리 주소 공간을 사용할 때, 페이지 사이즈가 4KB라면, 페이지 테이블은 100만 개의 항목을 담을 수 있어야 합니다. 이러한 문제점을 극복하기 위해 나온 방법이 바로 계층적 페이징입니다.

페이지 테이블을 위한 페이지 테이블을 만든다고 생각할 수 있습니다.

논리주소 변환

이러한 경우에 논리주소도 변환이 되어야 합니다.

그래서 페이지 번호가 들어가야 할 자리에 Outer Page Table에서 원하는 페이지를 찾기 위한 주소와, 두 번째 페이지 테이블에서 찾아야 할 주소를 모두 넣어줍니다.

Outer Page Table 그 자체의 주소는 CPU 내의 한 레지스터에 저장해둡니다.

메모리의 용량에 따라서 더 많은 단계를 거칠 수 있는데, 너무 많은 계층을 거치게 되면 최종적인 페이지에 도착할 때 까지 참조해야 할 페이지 테이블이 너무 많아져서 시간이 오래 걸릴 수 있습니다.

2. 해시 페이지 테이블(Hashed Page Table)

주소 공간이 32비트 보다 커지게 되면 해시 페이지 테이블을 많이 사용합니다.

논리적 주소에서 페이지 번호를 해시 함수를 거쳐 만든 해시 값으로 해시 테이블에 접근을 하여 프레임 번호를 찾는 것입니다. 해시 테이블에서 각각의 항목들은 연결 리스트를 가지고 있어서, 자신에게 해시되는 원소들을 쭉 연결시키게 됩니다.

그래서 페이지 테이블을 찾고자하면 우선 페이지 번호를 해시 함수를 돌려서 해시 값을 얻어내고, 이 해시 값으로 해시 테이블에 접근을 하게 됩니다. 그럼 해당 해시 값에 연결 리스트로 구현된 여러 페이지 정보들이 존재하고, 그중에 자신의 페이지 번호와 맞는 정보를 찾아서 프레임 번호를 얻어낼 수 있습니다.(아래 그림 참고)

3. 역 페이지 테이블(Inverted Page Table)

너무 많은 프로세스가 존재하거나 프로세스가 계속 늘어나게 되면 굉장히 큰 공간이 페이지 테이블로 사용됩니다.

• 페이지 테이블은 모든 프로세스 마다 하나씩 존재하기 때문

이를 막기 위해 물리 메모리와 같은 사이즈의 큰 하나의 페이지 테이블을 사용하여 모든 프로세스의 페이지 테이블 정보를 한 번에 구현하는 것입니다.

물리 메모리와 페이지 테이블의 크기가 같기 때문에 하나의 프레임 당 하나의 페이지 테이블 항목이 매핑됩니다.

모든 프로세스의 페이지 테이블이 하나에 모여있기 때문에 각각의 항목에 프로세스의 아이디를 추가로 표시해 주어야 합니다.

물론 이렇게 페이지 테이블이 너무 커지게 되면 원하는 페이지를 검색할 때 너무 느려지고, 프로세스 아이디를 이용해 테이블을 만들기 때문에 공유 메모리를 사용하기는 어렵다는 단점이 있습니다.

이 문제를 해결하기 위해 해싱 방법을 접목하여 사용할 수도 있습니다.