[OS] Memory Management (MMU, 메모리 연속 할당 기법)

메모리란 주소를 통해 접근하는 객체로 Main Memory는 주기억장치를 의미한다.

Logical vs Physical

Logical address (= virtual address)

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

Physical address

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

주소 바인딩

주소를 결정하는 것

Symbolic Address 👉 Logical Address 👉 Physical address

• Compile time binding
  • logical memory가 physical memory 그대로 올라간다.
  • 물리적 메모리 주소(physical address)가 컴파일 시 알려진다.
  • 시작 위치 변경 시 재컴파일
  • 컴파일러는 절대 코드(absolute code) 생성
  • 항상 프로그램이 실행되면 컴파일 시 입력된 해당 메모리 주소에 코드가 올라간다. 만약 메모리 위치가 변경된다면 컴파일을 다시 해야한다.
• Load time binding
  • logical memory는 physical memory의 비어있는 부분으로 올라간다.
  • Loader의 책임 하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치가능코드(relocateable code)를 생성한 경우 가능하다. (상대적 주소만 설정)
• Execution time binding(= Run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리상 위치를 옮길 수 있다.
  • CPU가 주소를 참조할 때마다 binding을 점검 (address ampping table)
  • 하드웨어적인 지원이 필요 (base and limit registers, MMU)

MMU (Memory-Management Unit)

Logical address를 Physical address로 매핑해주는 Hardware device

Scheme : 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (=relocation register)의 값을 더한다.
User program : logical address만을 다루고, 실제 physical address를 볼 수 없고 알 필요도 없다.

1. CPU가 Logical Address 346을 요청
2. MMU 안에 있는 14000을 더하여 Physical 메모리 14346번지에 있는 내용을 참조한다.

Hardware Support for Address Translation

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

• Relocation Register : 접근할 수 있는 물리적 메모리 주소의 최소값
• Limit Register : 논리적 주소의 범위 - 할당된 메모리 공간을 벗어나는지 체크한다.
  • trap 발생 : Software Interrupt -> 커널에게 알린다. Segmentation Fault

알아두어야 할 용어들 : Dynamic Loading, Dynamic Linking, Overlays, Swapping

Dynamic Loading

Loading : 메모리로 올리는 것

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load
• memory utilization의 향상 : 가끔씩 사용되는 많은 양의 코드의 경우 유용하다.
• 운영체제의 특별한 지원없이 프로그램 자체에서 구현 가능하다. (OS는 라이브러리를 통해 지원 가능)

Dynamic Linking

• Linking을 실행 시간(execution time)까지 미루는 기법
• Static Linking
  • 라이브러리가 프로그램의 실행 파일 코드에 포함된다 👉 실행 파일의 크기가 커진다.
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리가 낭비된다. (ex) printf 함수 라이브러리 코드)
• Dynamic Linking
  • 라이브러리가 실행 시 연결(link)된다.
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다.
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움 필요 (해당 프로그램을 모르기 때문이다.)
  • 연결이 실행 시간까지 연기된다.

    stub

    나중에 적재되거나 원격지에 위치해있는 큰 프로그램을 대리하기 위한 작은 프로그램 루틴
    Dynamic Linking에서 적절한 라이브러리 루틴을 찾는 코드이다.
    라이브러리 루틴이 없으면 Loading, 있으면 Linking
    자신을 그 루틴의 주소로 대체한다.

Overlays (참고)

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

Swapping (vs Paging)

프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것

• Backing store(=swap area)
  디스크 : 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in / Swap out
  • 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선점
  • priority-based CPU scheduling algorithm
    • priority가 낮은 프로세스를 swapped out 시킨다.
    • priority가 높은 프로세스를 메모리에 올려 놓는다.
  • Complie time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 한다.
    Execution time binding에서는 추후 빈 메모리 영역 아무 곳에서나 올릴 수 있다.
• swap time은 대부분 transfer time(swap 되는양에 비례하는 시간)이다.

Allocation of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘어 사용한다.

• OS 상주 영역 : interrupt vector와 함께 낮은 주소 영역을 사용한다.
• 사용자 프로세스 영역 : 높은 주소 영역을 사용한다.
  • 사용자 프로세스 영역의 할당 방법
    • Contiguous allocation
      각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것이다.
      Fixed partition allocation, Variable partition allocation
    • Noncontiguous allocation
      하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있다.
      Paging, Segmentation, Paged Segmentation

Contiguous Allocation

고정 분할(Fixed partition) 방식

• 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔
• 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재한다.
• 분할당 하나의 프로그램을 적재한다.
• 융통성이 없다.
  • 동시에 메모리에 load되는 프로그램의 수가 고정된다. (분할이 4개면 4개)
  • 최대 수행 가능 프로그램 크기가 제한된다.
• Internal fragmentation 발생 (external fragmentation도 발생한다.)

가변 분할(Variable partition) 방식

• 프로그램의 크기를 고려해서 할당한다.
• 분할의 크기, 개수가 동적으로 변한다.
• 기술적 관리 기법이 필요한다.
• External fragmentation 발생

External fragmentation (외부 조각)

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

Internal fragmentation (내부 조각)

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

Hole

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

Dynamic Storage-Allocation Problem

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

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

First-fit과 best-fit이 worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려진다.

• compaction
  • external fragmentation 문제를 해결하는 한 가지 방법이다.
  • 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것이다.
  • 매우 비용이 많이 드는 방법
  • 최소한의 메모리 이동으로 compaction 하는 방법 (매우 복잡)
  • compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.