Memory Management

Logical VS Physical Address

Logical Address (=virtual address)

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

Physical Address

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

주소 바인딩 : 주소를 결정하는 것

Symbolic Address -> Logical Address -> Physical address

주소 바인딩(Address Binding)

• Compile time binding
  물리적 메모리 주소(physical address)가 컴파일 시 알려짐
  시작위치 변경시 재컴파일
  컴파일러는 절대 코드(absolute code) 생성
• Load time binding
  Loader의 책임하에 물리적 메모리 주소 부여
  컴파일러가 재배치가능코드를 생성한 경우 가능
• Execution time binding(=Run time binding)
  수행이 시작된 이후에도 프로세스의 메모리 상 위치 옮길 수 O
  CPU가 주소를 참조할 때마다 binding 점검
  하드웨어적인 지원 필요, MMU

Memory-Management Unit (MMU)

Logical address를 physical address로 매핑해주는 하드웨어 장치

MMU Scheme

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

User program

logical address만을 다룸.
실제 physical address를 볼 수 없으며 알 필요가 없음.

Dynamic Relocation

Dynamic Loading

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

Overlays

작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현.

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원없이 사용자에 의해 구현

Swapping

Dynamic Linking

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

Allocation of Physical Memory

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

• OS 상주 영역
• 사용자 프로세스 영역
  

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

Contiguous allocation

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
Fixed partition allocation, Variable partition allocation

Noncontiguous allocation

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
Paging, Segmentation, Paged Segmentation

Contiguous allocation

실제 운영체제에서는 전혀 사용하지 않음.

• External fragmentation(외부조각)
  프로그램 크기 > 분할의 크기
  아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할.
• Internal fragmentation(내부조각)
  프로그램 크기 < 분할의 크기
  하나의 분할 내부에서 발생하는 사용되지 않은 메모리 조각.
  특정 프로그램에 배정되었지만 사용되지 않는 공간.
  

Paging

Address Translation Scheme

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

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

Associative Register

• Associative Registers(TLB): parallel search 가능
  TLB에는 page table 중 일부만 존재
• Address translation
  page table 중 일부가 Associative Register에 보관.
  만약 해당 page#가 Associative Register에 있는 경우 곧바로 frame#를 얻음.
  그렇지 않은 경우 main memory에 있는 page table롭터 frame#을 얻음.
  TLB는 context switch 때 flush(remove old entries)

Effective Access Time

Two-Level Page Table

현대의 컴퓨터는 address space가 매우 큰 프로그램 지원
32bit address 사용시 : 4G의 주소공간

• page size가 4k시 1M개의 page table entry 필요
• 각 page entry가 4B시 프로세스 당 4M의 page table 필요
• 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비

-> page table 자체를 page로 구성
-> 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음)

Multilevel Paging and Performance

• 보통 일반적으로, 공간은 커지나 시간이 오래 걸림
• Address space가 더 커지면 다단계 페이지 테이블 필요
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
• 캐쉬 메모리를 통해 메모리 접근 시간을 줄일 수 있음
• 4단계 페이지 테이블을 사용하는 경우
  메모리 접근 시간이 100ns, 캐시 메모리 접근 시간이 20ns, 캐쉬 적중률이 98%인 경우
  effective memory access time = 0.98x120+0.02x520 = 128 nanoseconds
  결과적으로 메모리 접근 시간을 28%만 감소시킴.

Memory Protection