Memory Management

Logical vs Physical

• Logical Address == virtual address
  • 프로세스마다 독립적으로 가지는 주소 공간
  • CPU가 보는 주소
• Physical Address : 메모리에 실제 올라가는 위치

Symbolic (사용자가 보는) ---컴파일---> Logical (숫자 주소) ---?---> Physical (물리적 공간에 올라가기 위함)

주소 바인딩 Address Binding

1. Compile time binding
   • 컴파일 시
   • 시작 위치 변경시 재 컴파일
   • 절대 코드 생성, 논리 이자 물리적 주소 Absolute Code
   • 꼭 0번지부터
2. Load time binding
   • 실행 시작시 비어있는 곳으로 할당
   • 재배치 가능 코드를 생성한 경우 재배치 가능
   • CPU 요청시 주소변환하여 물리적 주소 찾아 반환
3. Execution time binding (Run time binding)
   • 실행 중
   • 수행 시작 후에도 위치 옮길 수 있음
   • CPU가 주소 참조시 매번 점검
   • 하드웨어적인 지원 필요 : MMU, base and limit registers

MMU Memory-Management Unit

logical address를 physical address로 매핑해주는 H/W 장치
프로세스가 생성해내는 모든 주소값에 대해 base register의 값을 더한다.
사용자 프로세스, 즉 CPU는 logical만 다루면 된다. mmu에게 요청만 하여 메모리 접근하면 된다.

• Dynamic Relocation
  Relocation regsiter(base)(: 접근할 수 있는 물리적 메모리 주소의 최소값)과
  limit register(: 논리적 주소의 범위)을 사용하여 physical 변환
  논리 + relocation register -> 물리 주소 시작 위치
  limit register : 악의적인 요청인지 확인 -> Trap -> OS에 Abort함

용어

Dynamic Loading

프로세스를 static하게 미리 다 올리는 것이 아니라 루틴이 불려질 때 메모리에 load
memory utilization 향상
가끔씩 사용되는 많은 양의 코드에 유용. (방어적인 루틴, 오류 처리 루틴)
OS의 라이브러리를 이용하여 개발자가 직접 만듦. OS가 직접적으로 참여하진 않음.

Overlays

프로세스 중 실제 필요한 정보만을 올림
프로세스 크기가 메모리보다 클 때 유용
OS 지원없이 사용자가 구현. 초창기 수작업으로 프로그래머가 구현 (Manual Overlay) -> 어려움

Swapping

프로세스를 일시적으로 통째로 메모리에서 backing store로 쫓아냄

• Backing store == Swap area -> 디스크(큰 저장 공간)
• Swap in : Compile time 혹은 load time binding에서 원래 메모리 위치로 돌아감 -> 그래서 run-time binding이 돼야 한다.
• Swap out: swapper 중기 스케줄러에 의해 쫓겨날 프로세스 선정 (priority순으로)
• Swap time: 대부분 transfer time. swap되는 양에 달려있음

Dynamic Linking

linking을 실행 시간까지 미루는 기법

• Static
  • 라이브러리가 이미 파일 코드에 포함됨
  • 실행 파일 크기 커짐
  • 동일한 라이브러리를 각 프로세스가 메모리에 올리므로 메모리 낭비
• Dynamic -> Shared Library(dll, shared object)
  • 라이브러리가 코드 실행시 link됨
  • 라이브러리 파일을 찾을 수 있는 stub 포인터. 현 프로그램의 주소 공산을 사용하지 않기에
  • OS의 도움 필요

Allocation of Physical Memory

메모리는 OS 상주 영역과 사용자 프로세스 영역, 두 영역으로 이루어져 있음
종류

• Contiguous Allocation : 연속 할당
  각각의 프로세스가 메모리 연속 공간에 적재되도록 함
  종류
  • fixed partition allocation : 고정 분할. 융통성 X, 내부 & 외부 조각 발생
  • variable partition allocation : 가변 분할, 외부 조각 발생
• Noncontiguous Allocation : 불연속 할당
  종류
  • Paging : 메모리를 같은 크기의 페이지로 자름. 페이지 단위로 움직임
  • Segmentation: 주소 공간을 의미 있는 단위로 자름.
  • Paged Segmentation: 혼합

Contiguous Allocation

• 고정 분할 방식
  • 미리 파티션으로 나눠둠
  • 분할 크기가 같을 수도, 다를 수도 있다.
  • 분할 당 하나의 프로그램 적재
  • 융통성 X
    • load 되는 프로그램 수가 고정됨
    • 최대 수행 가능 프로그램 크기 제한
  • 내부 조각 (올리는 프로그램이 공간보다 작아 남는 공간 발생)과 외부 조각(파티션이 너무 작아 사용이 안된 부분이 있음) 발생
• 가변 분할 방식
  • 프로그램의 크기 고려 할당
  • 분할의 크기, 개수가 동적으로 변함
  • 외부 조각 (파티션이 너무 작아 올라갈 프로그램이 없어 낭비) 발생

Hole

• 가용 메모리 공간
• 여러 hole들이 메모리 여러 곳에 흩어져있음
• 프로세스 도착시 수용가능한 hole 할당

<How to hole 할당?>
Dynamic Storage-Allocation Problem
: 가변 분할 방식에서 size n인 요청을 만족하는 hole 찾기 문제

• Fist-fit : 최초로 찾아지는
• Best-fit : 다 살펴본 뒤 크기가 가장 잘 맞는 것 찾기 (모두 탐색 필요)
• Worst-fit : 가장 큰 hole 할당 (모두 탐색 필요), 시간,공간 이용률 측면에서 가장 비효율적

Compaction

외부 조각 문제를 해결하는 방법

• 사용중인 메모리를 한 곳으로 몰고, hole도 다른 쪽으로 몰아 큰 block 만들기
• 비용이 많이 듦
• 실행 시간에 동적으로 재배치 가능한 경우에만 가능한 방법

Noncontiguous Allocation

Paging

• virtual memory를 동일한 사이즈의 Page단위로 나눔
• 불연속적으로 메모리 저장됨
• 일부는 backing storage에, 일부는 physical memory에 저장된다.

Basic method

• physical을 동일한 크기의 frame으로 나눔
• logical를 동일한 크기의 page로 나눔 (frame과 크기 동일)
• page table을 이용하여 logical to physical
• 외부 조각은 발생 X, 내부 조각은 발생 가능성이 있다.

Page table

page는 주로 4Kb로 logical memory는 100만개로 나뉜다.
그 만큼 page table의 entry가 필요하게 되는 데 용량이 커 메모리에 저장하게 된다.

CPU는 [ p | d ]를 통해 page table에 접근하여 p번째 entry를 찾아 frame 번호를 얻어 [ f | d ]로 physical 주소로 변환한다.

구현

• Page table 은 main memory에 상주
• Registers 2개
  • PTBR (Page-table base register) : page table 시작 위치를 가리킴
  • PTLR (Page-table length register) : table 크기를 보관한다.
• 메모리 접근 연산에 2번의 메모리 접근 필요 -> 비용 낭비
  page table 접근 1번, data/instruction 접근 1번
• 속도 향상을 위해 associative register 혹은 cache인 TLB(translation look-aside buffer)을 이용

TLB (paging h/w)

TLB에 빈번히 참조되는 것을 미리 올려둔다.

• 별도의 H/W cache이다.
• process 마다 존재
• Page 번호와 frame번호가 저장돼있어야 함 (쌍으로)
• 전체 검색이 필요

1. 먼저 TLB를 전체 탐색 후
2. hit(찾는 것이 있다면) : 바로 physical 접근 (메모리 접근 1번)
3. miss(찾는 것이 없다면) : page table에 가서 변환 (메모리 접근 2번)

Two-Level Page Table

32비트 주소 체계 -> 2^32 4GB의 주소 공간
page size : 4K -> page table entry 1M개 필요 (entry가 4B라면 4M page table 필요)
이 공간을 일부분만 사용하여 page table이 심하게 낭비 됨

-> page table을 또 하나의 page로 구성 : 사용하지 않는 주소 공간에 대해서 outer에서 null로 두고, inner은 대응하는 것이 없음.(낭비 줄임)

logical address
p1 | p2 | d
10 | 10 | 12
* p1은 outer의 index이고(page number), p2는 outer의 page에서 displacement(page offset)

• d
  page 하나당 4KB : 2^12B -> 12 bit 필요
• p2
  entry 하나당 4B : 1K = 2^10 -> 10 bit 필요

*64비트 체계라면?

Multilevel Paging and Performance

메모리 접근을 n번해야해서 오버헤드일지도 모르지만 TLB를 사용하여 시간 단축

Memory Protection

entry마다 bit를 둔다.

1. Protection bit
   page에 대한 접근 권한 표시. 연산에 대한 권한 (read/write/read-only)

2. Valid / Invalid Bit in a Page Table
   page table은 프로그램이 가지는 메모리 공간 만큼 필요하고, 사용되지 않더라도 생성되야 함
   그래서 Valid (공간 사용) / Invalid (공간 사용 X)로 bit에 표시

   • invalid : 프로세스가 그 주소 부분을 사용하지 않을 경우/ 메모리에 있지 않고 swap area에 있을 경우

Inverted Page Table

공간 오버헤드가 큰 것을 해결

• Page frame 당 page table에 하나의 entry를 둔 것. 하나만 있음 (system-wide)
• page table entry는 물리 메모리의 page frame을 담고 있음. p-id | logical address
• 테이블 전체 탐색 필요 -> associative register 사용 (병렬적으로 동시 검색)

CPU -> [ pid | p | d ] 로 페이지 테이블에서 찾기 -> f번째에 해당 process logical address를 찾음 -> [ f | d ]로 변환된 physical address 나옴
=> 몇번째 entry인지가 중요함

Shared Page

data를 제외하고 공유 가능한 코드. 즉, 재사용 가능한 코드. Re-entrant Code (Pure Code)
[조건]
1. read-only (다른 코드에 의한 영향이 X)
2. 동일한 logical address에 위치해야함.

Segmentation

• 의미 단위로 나뉜 segment로 구성

구조

• logical address :[ segment-number | offset ]
• Segmentation table [ base | limit ]
  • base : 물리적 위치 시작 주소
  • limit : segment 길이
• Registers 2개
  • STBR (Segment-table base register) : table 시작 위치
  • STLR (Segment-table length register) : table 길이. segment entry 개수
    -> s is legal if s<STLR : 아니라면 Trap!

1. CPU -> [ S | d ] ->
2. segment table의 s번째 확인 [limit | base] ->
3. 와중에 1. s true if s<STLR 2. d<limit (세그먼트는 의미단위라 길이가 다 달라 확인 필요) check!
4. base +d 가 physical address

장점
1. Protection : 세그먼트 별로 bit 있음
2. Sharing
=> 의미 단위이기에 효과적이다. (반면, paging은 의미단위가 아니라서 권한 부여시 맞지 않는 부분 발생)

• paging보다 개수가 적다. (Table로 인한 낭비가 적음)

단점
Allocation

• first-fit/best-fit 등을 이용하게 되고
• 외부 조각 발생 (반면, paging은 발생하지 않음)

Sharing of Segments
공유가능한 코드에 대해 같은 세그먼트를 이용.
data 같은 private segment는 다 따로 둠.

Segmentation with Paging (Paged Segmentation)

segment table entry는 segment의 base 가 아니라 segment를 구성하는 page table의 base를 갖고 있음
1. CPU-> [ s | d ] 세그먼트 번호 | offset
2. segment table에서 page table 시작 주소 찾기 [ segment length | page table base ] 페이지 단위로 올라가게 됨
3. page table base + d 하여 [ p | d' ] 페이지 번호 | 페이지 offset을 찾는다.
4. 해당 세그먼트를 위한 페이지 테이블에서 p entry를 찾아 physical로 변환 [ f | d' ]
5. 메모리에 페이지 별로 올라감 (물리 메모리는 페이지 단위로 이용하는 것)
=> 각 기법의 장점을 이용할 수 있다.

이 주제에서 주소 변환시 OS역할은? 없다
다 H/W가 한다. OS가 하면 CPU가 정신 없을 것이다.