8. Memory Management

Memory Management

Logical vs. Physical Address

• Logical address(=Virtual address)
  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 Logical address
• Physical address
  • 메모리에 실제 올라가는 위치
• 주소 바인딩: 주소를 결정 하는 것
  • Symbolic addr -> Logical addr -> Physical addr
  • cf. Symbolic addr: 프로그래머 입장에서의 주소(변수, 함수 등)

Address Binding

• Compile time binding
  • 물리적 메모리 주소가 컴파일 시 알려짐
  • 시작 위치 변경 시 재컴파일
  • 컴파일러는 절대 코드(absolute code) 생성
  • 컴파일 시 항상 논리적이자 물리적 주소를 알아야 하므로 비효율적(현대에는 사용 x)
• Load time binding
  • Loader의 책임 하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 사용 가능
• Execution time binding(=Run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때 마다 binding을 점검
  • 하드웨어적 지원이 필요(MMU)
  • 대부분의 현대 컴퓨터에서 지원

Memory Management Unit (MMU)

• Logical Addr를 Physical Addr로 매핑해주는 하드웨어 장치

• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register)의 값을 더함
• User program
  • Logical addr만을 다룸
  • 실제 Physical addr를 볼 수 없으며 알 필요도 없음

• Relocation register는 접근할 수 있는 물리적 메모리의 최소값(프로그램의 시작점)
• Limit register는 악성 프로그램이 요청 프로그램의 크기를 벗어나는 주소 번지를 요청하는 경우를 방지하기 위해 사용

Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 Load하는 것
  • Memory utilization의 향상
• 가끔씩 사용되는 많은 양의 코드의 경우 유용
  • ex) 오류 처리 루틴
• 운영체제의 특별한 지원 없이 프로그램 자체에서(Library를 통해) 구현 가능
• Paging 기법과는 다른 기법

Overlays

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

Swapping

• 프로세스 전체를 일시적으로 메모리에서 backing store로 쫓아내는 것
• Backing Store(=Swap area)
  • 디스크: 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in / Swap out
  • 일반적으로 중기 스케줄러(Swapper)에의해 Swap out 시킬 프로세스 선정
  • Priority-based CPU scheduling algorithm
    • 우선순위 높은 프로세스를 메모리에 올려 놓음
    • 우선순위 낮은 프로세스를 Swap out
  • Compile time 혹은 Load time binding에서는 원래 동작하던 메모리 위치로 Swap in 해야 함 (비효율)
  • Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음 (효율)

Dynamic Linking

• Linking을 실행 시간까지 미루는 기법
• Static Linking
  • 라이브러리가 프로그램의 실행 파일 코드에 포함
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비
• Dynamic Linking
  • 라이브러리가 실행 시 Link됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움이 필요

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나누어 사용
  1. OS 상주 영역: interrupt vector와 함께 낮은 주소 영역 사용
  2. 사용자 프로세스 영역: 높은 주소 영역 사용
• 사용자 프로세스 영역의 할당 방법
  • Contiguous allocation
    • 각각의 프로세스가 메모리의 연속적 공간에 적재되도록 하는 것
    • Fixed partition allocation / Variable partition allocation
  • Non-contiguous allocation (현대에 사용)
    • 하나의 프롯스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
    • Paging / Segmentation / Paged Segmentation

Contiguous Allocation

Fixed Partition

• 물리적 메모리를 몇 개의 영구적 분할로 나눔
• 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
• 분할 당 하나의 프로그램 적재
• 융통성이 없음
  • 동시에 메모리에 Load되는 프로그램의 수가 고정
  • 최대 수행 가능 프로그램 크기 제한
• Internal / External Fragmentation 발생

Variable Partition

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

Internal Fragmentation

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

External Fragmentation

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

Hole

• 가용 메모리 공간
• 다양한 크기의 hole들이 메모리 여러 곳에 산재
• 프로세스가 도착하면 수용 가능한 hole 할당
• 운영체제는 할당 공간 / 가용 공간의 정보를 유지

Dynamic Allocation Problem

• First-fit
  • Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
• Best-fit
  • Size가 n 이상인 가장 작은 hole 찾아 할당
  • hole들의 리스트가 크기 순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 함
  • 많은 수의 아주 작은 hole들이 생성됨
• Worst-fit
  • 가장 큰 hole에 할당
  • 역시 모든 리스트를 탐색해야 함
  • 상대적으로 아주 큰 hole들이 생성
• First-fit과 Best-fit이 속도와 공간 이용률 측면에서 효과적으로 알려짐

Compaction

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

Non-contiguous Allocation

Paging

• Paging
  • 프로세스의 Virtual memory를 동일한 사이즈의 page 단위로 나눔
  • Virtual memory의 내용이 page 단위로 non-contiguous 하게 저장됨
  • 일부는 backing storage에, 일부는 physical memory에 저장
• Basic method
  • Physical memory를 동일한 크기의 Frame으로 나눔
  • Logical memory를 동일한 크기의 Page로 나눔(frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • Page table을 사용하여 Logical addr를 Physical addr로 변환
    • 프로그램마다 Page table 존재
  • External fragmentation 발생 X
  • Internal fragmentation 발생 O

Implementation of Page Table

• Page Table은 main memory에 상주
• 모든 메모리 접근 연산에는 2번의 메모리 접근이 필요
  • Page table 1번 + 실제 data/instruction 1번
• 속도 향상을 위해 associative register 혹은 Translation Look-aside Buffer(TLB)라 불리는 고속의 Lookup Hardware Cache 사용

• TLB Search에도 시간이 오래 걸리므로, Parallel search를 지원
• TLB는 context switch 때 Flush 됨 (TLB도 프로세스에 따라 다르기 때문)

Two-Level Page Table

• 현대 컴퓨터는 address space가 매우 큰 프로그램 지원
• 그러나 대부분의 프로그램은 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비
• Page table 자체를 page로 구성하자!
• 사용되지 않는 주소 공간에 대한 Outer page table의 entry 값은 NULL -> 메모리 save 가능
• Multi-level Paging and Performance
  • 주소 공간이 더 커지면 다단계 Page table 필요
  • 각 단계의 Page table이 메모리에 존재하므로 Logical addr의 Physical addr 변환에 더 많은 메모리 접근 필요
  • TLB 통해 메모리 접근 시간 줄일 수 있음 -> Overhead 크지 않음!

Memory Protection

• Page Table의 각 entry 마다 아래의 bit를 둠
  • Protection bit
    • page에 대한 접근 권한(read/write/readonly)
  • Valid-Invalid bit
    • valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 의미(접근 허용)
    • invalid는 해당 주소의 frame에 유효한 내용이 없음을 의미(접근 불허)
      • 프로세스가 그 주소 부분을 사용하지 않는 경우
      • 해당 페이지가 메모리에 올라와 있지 않고, swap area에 있는 경우

Inverted Page Table

• Page frame 하나 당 page table에 하나의 entry를 두는 것
• 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시
• 장점: Page table entry 사용공간을 줄일 수 있음
• 단점: 테이블 전체를 탐색해야 위치를 알 수 있음
• 조치: TLB 사용 통해 Parallel search

Shared Page

• Shared code
  • Re-entrant code(=Pure code)
  • readonly로 하여 프로세스 간에 하나의 code만 메모리에 올림
  • Shared code는 모든 프로세스의 Logical addr space에서 동일한 위치에 있어야 함
    • 주소 변환 통해 같은 Physical addr로 가야 하기 때문에
• Private code and data
  • 각 프로세스들은 독자적으로 메모리에 올림
  • Private data는 Logical addr space의 아무 곳에 와도 무방

Segmentation

• 프로그램을 의미 단위인 여러 개의 Segment로 분할
  • 작게는 프로그램을 구성하는 함수 하나 하나로,
  • 크게는 프로그램 전체를 하나의 segment로 정의 가능
• 일반적으로는 code, data, stack 부분이 하나씩의 Segment로 정의됨
• Segmentation은 Paging 기법보다 메모리 낭비가 적음
• Segment의 길이가 균일하지 않을 수 있기 때문에, 주소 변환 시 길이를 의미하는 limit 변수를 함께 전달

Segmentation Architecture

• Protection
  • 각 Segment 별로 Protection bit 존재
  • Each entry:
    • valid bit = 0 -> illegal segment
    • read/write/execution 권한 bit

• Sharing
  • Shared segment
  • Same segment number
  • cf. Segment는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 훨씬 효과적
• Allocation
  • First fit / best fit
  • External fragmentation 발생
    • Segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들 발생

Paged Segmentation

• Segment 하나가 여러 개의 page로 구성
• 물리적 메모리에는 Page 단위로 올라감
  • Allocation 문제 발생 안 됨