[OS] Memory Management (1) - MMU, Page, Page Table ...

Logical address (=Virtual address)

• 각 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작
• CPU가 보는 주소는 logical address임
  • 메모리에 올라갈 때 시작 위치는 바뀌지만 그 안에 있는 코드 상의 address는 그대로이다

 

Physical address

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

 

Symbolic Address

: 프로그래머 입장에서 보는 Symbol로 표현한 주소 (변수)

 

 

주소 바인딩(Address Binding)

Complie Time Binding

• 물리적 메모리 주소(Physical address)가 컴파일 시 알려짐
• 컴파일러는 절대 코드(absolute code) 생성
• 이미 결정된 Logical address가 Physical address가 된다
• 물리적 주소가 컴파일 시점에 미리 결정되어서 비효율적이다
• 메모리 주소를 변경하고 싶으면 컴파일을 다시 해야 함

Load Time Binding

• Loader의 책임하에(메모리에 올라갈 때) 물리적 메모리 주소 부여
• 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 가능
• 메모리가 비어있는 위치부터 논리적인 주소를 올린다

Execution Time Binding (= Run Time Binding) ⭐️

• 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
• CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
• 하드웨어적인 지원이 필요 (e.g... MMU)
• 현재의 컴퓨터 시스템

 

MMU(Memory-Management Unit)⭐️

• Logical address를 Physical address로 맵핑하는 하드웨어 디바이스
• 사용자 프로세스가 CPU에서 수행되며 생성하는 모든 주소 값에 대해 base register (=relocation register)의 값을 더한다
• 레지스터 2개를 이용해서 주소변환을 한다 (base, limit register)
• 유저 프로그램은 logical address만을 다루고 실제 physical address를 볼 수 없고, 알 필요가 없다

 

 

Hardware Support for Address Translation

limit register는 프로그램의 크기를 담는다

• 프로그램 크기보다 더 큰 논리적인 주소를 요청하면 다른 프로그램 영역을 요청하게 된다
• 이 것을 방지하기 위해서 limit register를 사용한다

 

Dynamic Loading (프로그래머가 명시적으로 하는 것)

• 프로세스 전체를 메모리에 미리 다 올리지 않고 해당 루틴이 호출되면 메모리에 load 한다
• memory utilization의 향상
• 가끔씩 사용되는 많은 양의 코드의 경우 유용 (ex: 오류 처리 루틴)
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능 (OS는 라이브러리를 통해 지원 가능)

 

Overlays

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

 

Swapping ⭐️

• 프로세스를 일시적으로 메모리에서 backing store로 쫓아낸다
• Backing store (= swap area)
  • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간 (디스크)

 

Swap in / Swap out

• 일반적으로 중기 스케줄러(swapper)에 의해 swap out 프로세스 선정
• priority-based CPU scheduling algorithm
  • 우선순위가 낮은 프로세스를 swapped out 시킴
  • 우선순위가 높은 프로세스를 메모리에 load
• Compile time 혹은 Load time binding에서는 원래 메모리 위치로 swap in 해야 함
• Excution time binding에서는 빈 메모리 영역 아무 곳에나 swap in 가능
• swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임

 

Dynamic Linking (Shared Library)

• Linking을 실행 시간(execution time)까지 미루는 기법
• 라이브러리가 실행 시 연결됨
• 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다
• 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 이동하고 없으면 디스크에서 읽어옴
• OS의 도움이 필요함

 

<=> Static Linking

• 라이브러리가 프로그램의 실행 파일 코드에 포함됨
• 실행 파일의 크기가 커짐
• 동일한 라이브러리를 각각의 프로세스가 메모리에 올리기 때문에 메모리 낭비가 있음

 

Allocation of Physical Memory

 

 

메모리는 일반적으로 두 영역으로 사용

- OS 상주 영역 : interrupt vector와 함께 낮은 주소 영역을 사용

- 사용자 프로세스 영역 : 높은 주소 영역 사용

 

 

 

 

Contiguous Allocation (연속 할당)

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

 

Noncontiguous Allocation(불연속 할당)

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

 

Contiguous Allocation

 

고정 분할 방식

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

 

가변 분할 방식

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

 

Hole

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

 

 Dynamic Storage-Allocation Problem

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

• First-fit
  • Size 가 N 이상인 것 중 최초로 찾아지는 hole에 할당
• Best-fit
  • Size 가 N 이상인 가장 작은 hole을 찾아서 할당
  • hole 리스트가 정렬되지 않은 경우 모든 hole의 리스트 탐색 필요
  • 많은 수의 아주 작은 hole들이 생성됨
• Worst-fit
  • 가장 큰 hole에 할당
  • 모든 리스트 탐색 필요
  • 상대적으로 아주 큰 hole들이 생성됨

 

Compaction

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

 

Paging ⭐️

• Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
• virtual memory의 내용이 page 단위로 noncontiguous 하게 저장됨
• 일부는 backing storage, 일부는 physical memory에 저장

• Physical memory를 동일한 크기의 frame으로 나눔
• Logical memory를 동일한 크기의 page로 나눈다 (frame과 같은 크기)
• 모든 가용 frame들을 관리
• Page table을 사용하여 logical address를 physical address로 변환
• External fragmentation 발생 X, Internal fragmentation 발생 가능

 

Address Translation Architecture - Paging

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

 

Paging Hardware with TLB ⭐️

logical address를 주면 memory 상에 있는 page table에 접근하기 전에 TLB(고속 하드웨어 캐시)에 저장된 정보를 이용해서 주소변환이 가능한지 찾는다. 만약 TLB에 존재하면 주소변환이 바로 이루어진다. 물리적 메모리에 바로 접근하기 때문에 메모리를 1번만 접근한다. 하지만 TLB에 없으면 (일반적인 주소변환 + 메모리 접근)이 이루어져 메모리를 2번 접근하게 된다.

• TLB는 page table 전체를 담지 않고 일부만을담고 있다 (자주 참조되는 일부분을 캐싱하고 있음)
• Page table은 p 만큼 떨어진 부분의 주소를 읽지만 TLB는  p의 위치에 어떤 값이 있는지 (p, f) 쌍으로 갖는다

 

Effective Access Time

 

Two-Level Page Table

2단계 페이지 테이블을 사용하는 이유???

: 속도는 줄어들지 않지만 공간의 효율성을 위해서 사용

 

현대의 컴퓨터는 address space가 매우 큰 프로그램 지원

• 32bit address 사용 시 : 2^32(4GB)의 주소 공간 -> 요즘은 64bit
  • Page size가 4KB일 때, 1,000,000개 page table entry가 필요하다
  • page entry 한 개가 4byte일 때, 프로세스 당 4MB 크기의 page table이 필요하다
  • 그러나 대부분의 프로그램은 4GB의 주소 공간 중 지극히 일부만 사용해서 page table 공간이 심하게 낭비됨

Page table 자체를 Page로 구성하면 사용되지 않는 주소 공간에 대한 outer page talbe의 엔트리 값은 NULL

 

 

Two-Level Paging Example

• logical address (32bit -> 4K page size)
  • 20bit의 page number : page offset(12bit)을 제외한 나머지
  • 12bit의 page offset : 4K를 표현하기 위한 비트의 수
• Page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나눈다
  • 10bit의 page number
  • 10bit의 page offset
  • 각 page table entry는 4byte

 

2단계 페이징에서의 Address-translation scheme (그림)

 

Multilevel Paging and Performance

• Address space가 더 커지면 다단계 페이지 테이블 필요
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
• TLB를 통해 메모리 접근 시간을 줄일 수 있음
• 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns, TLB hit ratio가 98%인 경우
  • EAT = 0.98 * 120 + 0.02 * 520 = 128ns (ns = nano seconds)
  • 결과적으로 주소변환을 위해 28ns 소요