[CS] PintOS Project 3 - Virtual Memory(0) - Memory Management 1 개념 (Feat. 반효경 교수님)

PintOS 3 주차는 가상 메모리에 관한 과제이다.

과제를 수행하기 전 반효경 교수님 강의를 듣고 개념을 잡고 가려고 한다. 빠르게 가보자!

 

Logical Address vs Physical Address

---

Logical Address(Virtual Address)

• 프로세스마다 독립적으로 가지는 주소 공간이다.
• 각 프로세스마다 0번지부터 시작한다.
• CPU가 보는 주소는 Logical Address이다.

 

Physical Address

• 메모리에 실제 올라가는 위치이다.

 

주소 바인딩(Address Binding): 주소를 결정하는 것

*참고: 여기서 설명하는 전제는 프로세스 전체를 메모리에 올리는 것으로 가정한다.

 

프로세스마다 독자적인 주소 공간이 있지만, 실제로 프로세스를 실행하기 위해서는 물리 메모리에 로드되어야 한다. 그리고 물리 메모리 상 어딘가에 위치하게 된다면 주소가 바뀌게 된다.(가상 메모리 주소 -> 실제 물리 메모리 주소) 이런걸 '주소 변환'이라고도 하며, 다른 말로는 '주소 바인딩' 이라고도 한다. 그럼 주소가 언제 결정되는가? 그 방법에는 3가지 방법이 있다. 

 

 

💡

Symbolic Address란?

프로그래머가 프로그램을 만들 땐 논리주소, 물리주소 같은 숫자로 이루어진 주소를 가지고 프로그래밍을 하진 않는다. 변수를 이용하여 메모리 주소를 저장하고, 함수 이름을 가지고 함수로 JUMP 하는 등 Symbolic 을 이용해 접근/사용한다. (아래 그림 참고)

 

Compile time binding

• 컴파일 시점에 물리적 메모리 주소가 결정된다.
• 메모리 시작 위치 변경 시 재컴파일을 해야한다. (물리적 메모리 주소가 컴파일 시 결정되므로)
• 컴파일러는 절대 코드(absolute code)을 생성한다.
  • Logical Address 자체가 Physical Address 자체가 되므로 '절대 코드' 라고 부른다.

Load time binding

• 프로세스가 시작될 때 물리 메모리 주소가 결정된다.
• Loader의 책임하에 물리적 메모리 주소를 부여한다.
• 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능하다.

Execution time binding(=Run time binding)

• 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있다.
• CPU가 주소를 참조할 때마다 binding을 점검해야 한다.(address mapping table)
• 하드웨어적인 지원이 필요하다.(e.g, base and limit registers, MMU)

 

 

위의 사진은 A(100), B(330)를 더해 변수 A에 저장하는 간단한 프로그램이다. 초기 Symbolic address로 이루어진 변수들을 컴파일 하게 되면 프로그램 마다 가지는 Logical address 가 생성된다. 이제 실행 파일을 실행하게 되면 물리 메모리 상에 프로그램이 올라가게 되고, 물리 메모리 주소가 결정되는 이 시점을 '주소 바인딩' 이라고 했다.

 

Compile time binding 은 컴파일 시점에서 물리 메모리 주소가 결정되기 때문에 물리 메모리 주소 상에서도 Logical Address 가 동일한 모습이다. 

Load time binding 프로그램이 실행되서 물리 메모리에 올라갈 때 물리 메모리 주소가 결정된다. 

Execution time binding(=Run time binding) 'Load time binding' 과 동일하게 프로그램이 실행될 때 메모리 주소가 결정되는 것은 동일하지만, 실행 중에서도 메모리 주소가 바뀔 수 있는 것을 의미한다.

 

위의 사진을 통해 CPU가 왜 'Logical Address' 를 바라보는 지 이해할 수 있다. 실행 파일에 적혀 있는 각 줄은 '인스트럭션' 을 의미한다. 물리 메모리 주소에 바인딩될 때 '시작 주소'는 Logical Address의 시작 주소와 달라지게 되지만, 그 안의 인스트럭션에 정의되어 있는 Logical Address는(A, B, C 의 주소 등) 컴파일 시 이루어지는 작업이므로 주소가 바뀌지 않게 된다. 따라서 CPU는 Logical Address를 바라볼 수 밖에 없고, 시작 주소만 달라진 물리 메모리 주소 상에서 각 인스트럭션을 수행하게 된다.

 

Memory-Management Unit(MMU)

---

*참고: 여기서 설명하는 전제는 프로세스 전체를 메모리에 올리는 것으로 가정한다.

 

MMU(Memory-Management Unit)

• Logical Address 를 Physical Address 로 매핑해 주는 Hardware Device

MMU scheme

• 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(relocation register)의 값을 더한다.

User program

• Logical Address 만을 다룬다.
• 실제 Physical Address 를 볼 수 없으며 알 필요도 없다.

 

 

운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터

*참고: 여기서 설명하는 전제는 프로세스 전체를 메모리에 올리는 것으로 가정한다.

따라서 추후 페이징 기법에서는 두 개의 레지스터를 사용하는 것만으로는 물리 메모리 주소를 찾아가지 못한다.

 

Relocation Register(base register)

• 물리적 메모리의 시작 위치를 저장하고 있는 레지스터, 접근할 수 있는 물리적 메모리 주소의 최소값
• CPU가 Logical Address 를 통해 실제 Physical Address 를 접근해야 하는데, 가상 메모리의 주소 + relocation register의 주소를 더하여 실제 Physical Address 를 알 수 있다.

Limit Register

• 프로그램의 논리 주소 사이즈를 가지고 있는 레지스터, 논리적 주소의 범위
• 악의적인 프로그램 또는 모종의 이유로 프로그램이 가지고 있는 Logical Address 의 범위를 벗어난 영역에 대해서 Logical Address 를 요청할 수도 있다. 이를 방지하기 위해서 limit register를 통해 유효한 주소인지 체크한다.

위에서 설명한대로 limit register 를 통해 해당 프로그램의 유효한 주소 값인지 체크한 후,
Logical Address + relocation register 계산을 통해 실제 물리 메모리 주소로 접근하는 모습이다.

만약 유효하지 않은 주소에 접근할 시 trap(소프트웨어 인터럽트) 을 발생시킨다. trap 에 걸리게 되면 해당 프로그램이 CPU를 점유하고 있었지만 하던 작업을 잠시 멈추고, CPU 제어권이 운영체제에게 넘어가게 된다. OS에서는 어떤 이유로 trap이 걸렸는지 판별한 후 해당 프로그램에 대해서 어떤 상태로 변화시킬지 응징(?)하게 된다.

 

 

Some Terminologies

---

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 마다 메모리에 로드하는 것

• 메모리를 동적으로 필요할 때마다 메모리에 올리는 것이라 '동적'이라는 표현이 붙는다.
• memory utilization 의 향상 - 메모리를 효율적으로 사용할 수 있음
• 가끔씩 사용되는 많은 양의 코드의 경우 유용
  • 예: 오류 처리 루틴
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능)
  • 여기서 말하는 Dynamic Loading 은 OS에서 메모리를 관리하는 '페이징 기법'을 얘기하는 것이 아니라, 프로그래머가 프로그램을 짤 때를 얘기하는 것이다.

*참고: Loading: 메모리로 올리는 것

 

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올린다.
• 프로세스의 크기가 메모리보다 클 때 유용하다.
• 운영체제의 지원없이 사용자에 의해 구현된다.
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현했다.
  • Manual Overlay
  • 프로그래밍이 매우 복잡

 

Swapping

프로세스를 일시적으로 메모리에서 backing store 로 쫓아내는 것
원래 본연의 'Swapping' 의미는 프로세스 전체를 'Backing store'로 쫓아내는 것이 맞다. 하지만 프로세스 전체를 디스크에 보내고, 메모리에 로드시키는 작업은 상당히 자원 소모적인 작업이므로 현대의 시스템에서는 메모리를 일정 크기로 나누는 페이징 기법에서 특정 페이지만을 swap in/out 하게 된다. 그리고 그러한 작업을 Swapping 이라고 동일하게 부르기도 한다.

Backing store(swap area)

• 디스크 공간 - 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간

Swap in / Swap out

• 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정한다.
• priority-based CPU scheduling algorithm
  • priority가 낮은 프로세스(CPU 수행 가능성이 낮은 프로세스)를 swapped out 시킴
  • priority가 높은 프로세스(CPU 수행 가능성이 높은 프로세스)를 메모리에 올려 놓음
• Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야한다.
  • 스와핑의 효과를 제대로 보기 위해서는 Run time binding 방식이 사용되어야 한다. 왜냐하면 메모리 주소 공간이 한정적이라 자원을 효율적으로 사용하기 위해서 스와핑 방식을 사용하게 되는데 위의 두 개의 방식은 동일한 메모리 주소에 다시 binding이 이루어져야 하므로, 효과를 제대로 보긴 어렵다.
  • (위의 주소 바인딩 - 이미지 참고)
• Execution(Run) time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있다.
• swap time은 대부분 transfer time (데이터를 전송하는 시간, swap 되는 양에 비례하는 시간)임

*참고: 중기 스케줄러는 스왑 아웃 시킬 프로세스를 결정하는 역할을 수행한다.

 

 

Dynamic Linking

Linking을 실행 시간(execution time)까지 미루는 기법

• Static linking
  • 라이브러리가 프로그램의 실행 파일 코드에 포함된다.
  • 실행 파일의 크기가 커진다.
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비이다.(eg. printf 함수의 라이브러리 코드)
• Dynamic linking
  • 컴파일로 실행파일이 만들어 질 때 라이브러리가 포함되지 않고, 라이브러리가 실행 시 연결(link)된다.
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다.
  • Dynamic linking을 해주는 라이브러리를 'Shared Library' 라고 부른다.
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어온다.
  • 운영체제의 도움이 필요하다.

*참고 - Linking: 여러 군데 존재하는 컴파일된 파일들을 묶어서 실행파일로 만드는 것

 

Allocation of Physical Memory (Feat. 물리적 메모리 관리)

---

메모리는 일반적으로 두 영역으로 나뉘어 사용된다. (아래 이미지 참고)

• OS 상주 영역
  • interrupt vector와 함께 낮은 주소 영역 사용
• 사용자 프로세스 영역
  • 높은 주소 영역 사용

 

 

사용자 프로세스 영역의 할당 기법

• Contiguous allocation
  • 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
  • 고정분할 방식(Fixed partition allocation)
  • 가변분할 방식(Variable partition allocation)
• Noncontiguous allocation
  • 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
  • 페이징 기법(Paging)
  • 세그먼테이션 기법(Segmentation)
  • Paged Segmentation(위의 방식을 혼합한 기법)

 

Contiguous allocation - 연속 할당 기법

*참고: 현대 시스템에서는 Noncontiguous allocation - 불연속 할당 기법을 사용한다.

 

고정분할 방식(Fixed partition allocation)

• 사용자 프로그램이 들어갈 물리 메모리 영역을 미리 파티션으로 나누는 것
  • 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눈다.
  • 분할의 크기는 고정될 수도 있고, 가변적일 수도 있다.
• 메모리 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재한다.
• 메모리 분할 당 하나의 프로그램을 적재한다.
• 융통성이 없다.
  • 동시에 메모리에 로드되는 프로그램의 수가 고정된다.
  • 최대 수행 가능 프로그램 크기가 제한된다.
• 'internal fragmentation' (내부단편화) 이 발생한다. (external fragmentation 도 발생될 수 있다.)

 

가변분할 방식(Variable partition allocation)

• 프로그램의 크기를 고려해서 할당한다.
• 분할의 크기, 개수가 동적으로 변한다.
• 'External fragmentation' (외부단편화) 이 발생한다.

 

 

fragmentation(단편화)

External fragmentation(외부 단편화)

• 프로그램 크기보다 분할의 크기가 작은 경우
• 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할

Internal fragmentation(내부 단편화)

• 프로그램 크기보다 분할의 크기가 큰 경우
• 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
• 특정 프로그램에 배정되었지만 사용되지 않는 공간

 

Hole

• 가용 메모리 공간을 의미한다.
• 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있다.
• 프로세스가 도착하면 수용가능한 hole을 할당한다.
• 운영체제는 다음의 정보를 유지한다.
  • 할당된 공간
  • 가용 공간(hole)

 

 

Dynamic Storage-Allocation Problem

가변분할 방식(Variable partition allocation)에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

• First-fit
  • Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당한다.
• Best-fit
  • Size가 n 이상인 가장 작은 hole을 찾아서 할당한다.
  • Hole 들의 리스트가 크기 순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야한다.
  • 많은 수의 아주 작은 hole 들이 생성된다.
• Worst-fit
  • 가장 큰 hole에 할당한다.
  • 역시 모든 리스트를 탐색해야 한다.
  • 상대적으로 아주 큰 hole들이 생성된다.

*참고: First-fit과 Best-fit이 worst-fit 보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려졌다.

 

 

---

Ref

 

메모리 관리1 - 이화여자대학교 - 반효경 교수님