07. Memory Management

Memory Address

Logical Address (= virtual address)

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

Physical Address

• 메모리에 실제로 올라가는 위치
• DRAM에서의 변하지 않는 실제 주소

Symbolic Address

• 프로그래머가 사용하는 변수나 레이블과 같은 기호적인 이름으로 표시된 주소

 

Address Binding

Address Binding

• Symbolic Address -> Logical Address -> Physical Address

(1) Compile Time Binding

• 컴파일 시 정적으로 물리적 주소가 결정됨
• 프로그램의 시작 위치를 변경하려면 전체 프로그램을 재컴파일해야 함
• 컴파일러는 절대 코드 (absolute code) 생성: 프로그램이 메모리에 로드되면 주소가 변경되지 않음

프로그램의 시작 위치 == 프로그램이 메모리에 로드될 때, 해당 프로그램이 상주하는 메모리 영역의 시작 주소

 

(2) Load Time Binding

• Loader가 물리적 주소 부여: 프로그램이 메모리에 로드될 때, loader가 물리적 주소를 부여
• 컴파일러가 재배치가능한 코드 (relocatable code)를 생성한 경우 가능: 프로그램의 시작 위치를 변경하더라도, 컴파일된 코드를 수정하지 않고도 로더가 물리적 주소를 조정할 수 있음

(3) Execution Time Binding (= Run Time Binding)

• 프로그램이 실행된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
• CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table): CPU가 주소를 참조할 때마다 주소 매핑 테이블을 검사하여 실제 메모리 주소로 변환
• 하드웨어적인 지원이 필요 (e.g. MMU)

 

MMU: Memory-Management Unit

• logical address를 physical address로 매핑해주는 Hardware device
• 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (= relocation register)의 값을 더한다.
  • context switch가 발생하면 MMU의 base register 값도 바뀐다.
• 사용자 프로그램은 logcal address만을 다루며 physical address를 알 수 없고 알 필요도 없다.

• Base register(= Relocatioin register): 접근할 수 있는 물리적 메모리 주소의 최솟값
• Limit register: 논리적 주소의 범위
  • if logical address > limit register: trap (addressing error) 발생

 

Terminologies

Dynamic Loading

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

Loading: 프로그램을 메모리로 올리는 것

 

Dynamic Linking

• 라이브러리가 실행 시 연결 (link) 됨
• 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다.
• 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어 온다.
• 운영체제의 도움이 필요함

Static Linking

• 라이브러리가 프로그램의 실행 파일 코드에 포함되므로 실행 파일의 크기가 커진다.
• 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 발생

1. 컴파일(Compilation): 소스 코드를 컴파일하여 오브젝트 파일 생성.
2. 링킹(Linking): 여러 오브젝트 파일을 하나의 실행 파일로 결합.
3. 로딩(Loading): 실행 파일을 메모리에 로드하여 초기화 및 실행.

 

Overlays

• 프로그램이 실행되는 동안에 필요한 부분만 메모리에 로드하는 방법
• 메모리 제약으로 인해 프로세스의 전체 크기를 한 번에 메모리에 올릴 수 없을 때 사용되는 메모리 관리 기술 중 하나
• 운영체제의 지원 없이 사용자에 의해 구현

• Dynamic Loading(동적 로딩): 실행 중에 필요한 모듈이나 라이브러리를 동적으로 로드하는 것. 필요한 부분을 메모리에 로드하고 사용하는 것이지만, Overlays처럼 수작업으로 구현하는 것이 아니라 운영체제가 지원합니다.
• Overlays: 프로세스의 크기가 메모리보다 클 때, 프로그래머가 직접 부분적으로 메모리를 관리하는 방법.

 

Swapping

• 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
• Backing store (= swap area): 디스크, 충분히 빠르고 큰 저장 공간
• Swap in / Swap out
  • 일반적으로 중기 스케줄러 (swapper)에 의해 swap out 시킬 프로세스 선정
  • priority-based CPU scheduling algorithm: priority가 낮은 프로세스를 swap out 시키고 높은 프로세스를 메모리에 올림
  • Compile time 혹은 Load time binding에서는 원래 메모리 위치로 swap in 해야 함
  • Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
  • swap time은 대부분 trasfer 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 allocation

• 물리적 메모리를 몇 개의 영구적 분할 (partition)으로 나누고 partition당 하나의 프로그램 적재
• partition의 크기가 모두 동일한 방식 vs 서로 다른 방식
• 융통성이 없다: 동시에 메모리에 load되는 프로그램 수 고정, 최대 수행 가능 프로그램 크기 제한
• Internal fragmentation, External fragmentation 발생

Variable partition allocation

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

External fragmentation: 프로그램 크기보다 partition 크기가 작은 경우 발생하는 외부 조각

• 아무 프로그램에도 배정되지 않은 빈 곳인데 프로그램이 올라갈 수 없는 작은 partition

Internal fragmentation: 프로그램 크기보다 parition 크기가 큰 경우 발생하는 내부 조각

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

 

Hole: 가용 메모리 공간

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

Dynamic Storage-Allocation Problem

• Variable partition allocation 방식에서 size n 인 요청을 만족하는 가장 적절한 hole을 찾는 문제
• (1) First-fit: 최초로 찾아지는 hole에 할당
• (2) Best-fit: Size n 이상인 가장 작은 hole을 찾아서 할당, 정렬되지 않은 경우 모든 hole 탐색해야 함, 많은 수의 아주 작은 hole들이 생성
• (3) Worst-fit: 가장 큰 hole에 할당, 정렬되지 않은 경우 모든 리스트 탐색해야 함, 상대적으로 아주 큰 hole들이 생성됨
  • (1), (2)번이 (3)번보다 속도와 공간 이용률 측면에서 효과적

Compaction

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

 

Paging

Paging

• 프로세스의 logical memory (virtual memory)를 동일한 사이즈의 page 단위로 나누고 noncontiguous하게 저장
• 일부는 backing storage에, 일부는 physical memory에 저장한다.
• physical memory를 동일한 크기의 frame으로 나눔
• logical memory를 frame과 동일한 크기의 page로 나눔
• page table을 사용하여 Logical address를 physical address로 변환
• External fragmentation & Internal fragmentation 발생 X

CPU는 다음 두 가지로 구성된 virtual address를 사용한다.

• Page number (p): page table의 index로 사용, 해당 index에는 그 페이지의 물리적 메모리 상의 base address가 저장됨
• Page offset (d): base address와 더해져서 physical address가 구해짐

 

Implementation of Page Table

• page table은 main memory에 상주
• PTBR(Page-table base register)가 page table을 가리킴
• PTLR(Page-table length register)가 테이블 크기를 저장
• 모든 메모리 접근 연산에는 2번의 memory access 필요: page table 접근 -> 실제 data/instruction 접근
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer (TLB)라 불리는 고속의 lookup hardware cache 사용

Asssociative Register (TLB)

• parallel search 가능
• Addres translatioin
  • page table 중 일부가 TLB에 저장되어 있음
  • 해당 page #가 TLB에 있는 경우 바로 frame #를 얻을 수 있고, 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
  • TLB는 context switch 발생하면 flush

Effective Access Time

• Associative register lookup time = t
• memory cycle time = 1
• Hit ratio: associative register에서 찾아지는 비율: a
• Effective Access Time (EAT) = (1 + t)a + (2 + t)(1 - a) = 2 + t - a

 

Two-Level Page Table

Two-Level Page Table

• 프로그램이 사용하는 주소 공간이 매우 큰 경우, 해당 프로그램의 페이지 테이블도 매우 커짐 -> But, 대부분의 프로그램은 주소 공간 중 일부분만 사용하므로 메모리 낭비 발생

👉 Page table 자체를 page로 구성

👉 사용되지 않는 주소 공간에 대한 Outer page table의 엔트리 값은 NULL (대응하는 inner page table 없음)

 

Multilevel Paging and Performance

• Address space가 커지면 multilevel table 필요 -> 더 많은 메모리 접근 필요
• 캐쉬 메모리를 통해 메모리 접근 시간을 줄일 수 있다.

Memory Protection

• Page table의 각 entry마다
  • Protection bit: page에 대한 접근 권한 (read / write / read-only)
  • Valid-invalid bit: valid(1)=해당 주소의 frame에 해당 페이지가 있음 (접근 허용), invalid(0)

Inverted Page Table

• 일반적인 페이지 테이블은 가상 주소를 물리 주소로 변환하는데 사용되는 매핑 정보를 저장하는데 비해, Inverted page table은 물리 주소를 가상 주소로 변환하는데 사용
• 역페이지 테이블은 물리 메모리 프레임을 인덱스로 사용하여 구성, 각 엔트리는 물리 메모리 프레임에 대한 정보를 저장
• 공간 효율성: 일반적인 페이지 테이블은 가상 주소 공간의 크기에 따라 크기가 결정되지만, 역페이지 테이블은 물리 메모리 프레임의 개수에 따라 크기가 결정되므로 더 효율적입니다.
• 빠른 검색: 역페이지 테이블에서는 물리 주소가 인덱스로 사용되므로 특정 물리 메모리 프레임에 대한 가상 주소 매핑 정보를 빠르게 찾을 수 있습니다.
• 단점: 테이블 전체를 탐색해야 함

 

Shared Page

• Shared Code: Re-entrant Code (= Pure code)
  • read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림 (물리적 메모리에 하나의 코드만 존재)
  • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
• Private code and data
  • 각 프로세스들은 독자적으로 메모리에 올림
  • Private data는 logical address space의 아무 곳에 와도 무방

 

Segmentation

Segment

• 프로그램은 의미 단위인 여러 개의 segment로 구성 (= logical unit)
• 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의, 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
• 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨

Segmentation Architecture

• Logical address: <segment-number, offset>
• Segment table: each table entry has
  • base: starting physical address of the segment
  • limit: length of the segment
• Segment-table base register(STBR): 물리적 메모리에서 segment table의 위치
• Segment-table length register(STLR): 프로그램이 사용하는 segment 수
  • segment number s is legal if s < STLR & offset d is legal if d < limit
• Protection: 각 세그먼트 별로 protection bit 존재
  • Valid bit: 1 == valid (legal) <-> 0 == invalid (illegal)
  • read / write / execution 권한 bit
• Sharing: shared segments have same segment number
  • segment는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 더욱 효과적이다.
• Allocation
  • first-bit, best-bit
  • external fragmentation 발생
  • segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점 발생

 

Segmentation with Paging

• segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음 == segment를 page로 나눈다.
• fragmentation이 줄어든다는 장점, 로직이 복잡해진다는 단점