메인 메모리 관리

메모리란 무엇인가?

• 메모리란 주소(Address)를 통해 접근할 수 있는 저장 장치
• 주소는 메모리상의 서로 다른 위치를 구분하기 위한 숫자
• 32비트 시스템
  • 2^32 개만큼의 메모리 위치 구분 가능
  • 2^32 bytes의 메모리 공간 사용 가능
• 64비트 시스템
  • 2^63 개 만큼의 메모리 위치 구분 가능
  • 2^64 bytes의 메모리 공간 사용 가능

주소 바인딩(Address Binding)

• 메모리의 논리 주소와 물리 주소를 연계하는 작업

논리주소(Logical Address)

• 프로세스가 메모리에 적재될 때 할당되는 가상의 (독자적인) 위치

물리주소(Physical Address)

• 프로세스가 실제 배치되는 메모리상의 위치

주소 바인딩의 방식

• Compile Time Binding
  • 프로세스가 적재될 메모리 위치를 미리 알고 있다는 전제 하에서 컴파일러가 명령어와 데이터가 저장될 물리주소값을 강제로 결정
  • 컴파일을 하는 시점에서 프로그램이 물리 메모리 주소가 어디 위치할지 결정
  • 프로그램이 생성될 때 할당될 메모리 주소값이 고정되므로 만약 프로그램의 할당 주소값을 바꾸려면 컴파일을 다시 해야 함 ⇒ 비효율적
• Load Time Binding
  • 컴파일러가 컴파일을 수행할 때 재배치 코드를 생성
  • 메모리 주소값이 미리 결정되는 것이 아니고 프로세스가 실행되기 시작할 때 처음으로 메모리에 적재될 때 값이 결정됨
  • 메모리 바인딩이 loader가 프로그램을 메모리 위에 올릴 때 수행됨
  • 만약 프로그램이 할당된 주소값을 바꾸려면 메모리 위로 다시 적재가 수행되어야 함
• Execution Time Binding
  • 실행시간에 바인딩
  • 프로그램이 메모리 위에 적재되어 실행이 시작된 이후에도 프로그램이 위치한 물리 메모리 주소값을 바꿀 수 있음
  • CPU가 프로세스의 메모리 주소로 접근을 처리할 때마다 접근 주소값의 구체적인 주소값을 체크해야 함

Memory Management Unit(MMU)

• Execution Time Binding(실행 시간 바인딩)을 수행하기 위한 하드웨어 장치
• 논리 주소를 물리 주소로 매핑 수행

베이스 레지스터(Base register or Relocation register)

• 프로세스의 물리 메모리 시작 주소 정보를 가짐
• 접근 데이터 물리 주소 = 기준 레지스터 값 + 논리 주소(offset)

  

멀티 프로세스를 위한 메모리 관리

• 프로세스는 자신만의 고유 주소 공간을 가짐
• 프로세스 A가 말하는 주소 100번지(논리 주소)와 B가 말하는 100번지는 서로 다르다
• 문맥 교환이 발생할 때마다 베이스 레지스터의 값을 변경

  

• MMU기반의 주소 변환에 의해 임의의 프로세스가 다른 프로세스의 주소 공간을 침범할 수 있음

 

한계 레지스터(Limit register)

• 메모리 보호(Memory protection)를 위해 운용
• 프로세스가 허용 주소 공간을 넘어가는지 체크

  

Dynamic Loading

• 프로세스 실행 시 전체 주소 공간이 아닌 호출 루틴에 대해서만 메모리에 적재하는 방식 (프로세스의 주소 공간 전체를 메모리에 올리는 것은 비효율적)
• 프로세스 코드의 상당 부분은 특별한 경우에만 호출됨 (ex : error처리 루틴 등)

  

Dynamic Linking

Linking : object파일에 대해서 이미 작성한 라이브러리 파일들을 연결해서 실행파일을 만드는 것

Static linking(정적 연결)

• 작성 코드와 라이브러리가 합쳐져서 바이너리 파일 생성
• 바이너리의 크기 증가, 중복된 라이브러리 적재

Dynamic linking(동적 연결)

• 프로세스 실행 시점에 라이브러리를 연결
• 바이너리 파일에 라이브러리가 포함되지 않음

  

Swapping

• 메모리에 올라온 프로세스의 전체 주소 공간을 디스크 스토리지의 스왑 영역(swap area)에 내려놓는 것
• 프로세스가 실행되고 있는 동안에만 디스크에 일시적으로 저장
• 스왑 영역은 백킹 스토어(backing store)라고 불림

  

물리 메모리 할당

• 물리 메모리에는 커널을 위한 영역과 유저 프로세스를 위한 영역이 나뉘어 할당됨

Contiguous Memory Allocation(연속 메모리 할당 방식)

• 각 프로세스를 통째로 메모리에 할당
• Fixed Partition Memory Allocation
• Variable Partition Memory Allocation

Non-contiguous Memory Allocation(불연속 메모리 할당 방식)

• 각 프로세스를 분산하여 메모리에 할당
• Paging, Segmentation

Fixed Partition Memory Allocation

• 물리 메모리를 영구적으로 여러 개의 분할(partition)로 나눔
• 각 분할에 하나의 프로세스를 적재

External Fragmentation(외부 단편화)

• Partition의 크기 < 프로그램의 크기
• 대체 프로그램을 찾지 못하는 경우 메모리 낭비 발생

Internal Fragmentation(내부 단편화)

• Partition의 크기 > 프로그램의 크기
• 남는 공간만큼 메모리 낭비 발생

  

Variable Partition Memory Allocation

• 프로그램의 크기에 따라 분할(partition)의 크기와 개수가 변동
• 프로세스 크기에 딱 맞춰서 파티션 크기를 나누므로, Internal Fragmentation 문제 해결
• 기존 프로그램이 종료되어 메모리가 비게 될 경우 External Fragmentation 문제 발생 가능

  

Dynamic Storage-Allocation Problem

• 동적 메모리 할당 문제
• 프로세스를 메모리의 어떤 물리 주소 위치에 적재시킬지 결정

First-Fit Allocation(최초 적합 할당)

• 프로세스가 할당될 수 있는 가용 공간 중 가장 먼저 탐색되는 곳에 할당

Best-Fit Allocation(최적 적합 할당)

• 프로세스가 할당될 수 있는 가용 공간 중 크기가 가장 딱 들어맞는 곳에 할당

Worst-Fit Allocation(최악 적합 할당)

• 프로세스가 할당될 수 있는 가용 공간 중 가장 큰 곳에 할당

Compaction(컴팩션)

• 프로세스에 의해 점유된 메모리 공간을 한쪽 구석으로 몰아넣어서 가용 공간을 획득하는 방식
• External Fragmentation문제를 해결
• 프로세스 위치 변경 자체에 의한 오버헤드 발생 문제
• Execution Time Binding 지원 환경에서만 수행 가능

Paging(페이징)

• 프로세스를 동일한 크기의 페이지(page)라 불리는 조각으로 나누어 관리하는 불연속 할당(Noncontiguous Allocation) 방식
• 프로세스가 점유할 메모리 공간을 각 페이지로 분산

Frame(프레임)

• 물리 메모리 공간을 분할한 고정 크기 블록(Fixed-Sized Block)

Page(페이지)

• 논리 메모리 공간을 분할한 모두 동일한 크기의 블록
• 하나의 페이지는 하나의 프레임과 연계

Page Table(페이지 테이블)

• 물리 메모리의 각 프레임에 대한 base address 정보를 저장
• 논리 메모리의 페이지와 물리 메모리의 프레임을 매핑
• 프로세스를 N개의 페이지에 담으려면 N개의 가용 프레임이 필요
• CPU에 의해 생성되는 논리주소는 페이지 넘버와 페이지 오프셋으로 구성

Page Number(p) (페이지 넘버)

• 페이지 테이블의 인덱스로서 사용
• 물리 메모리에 있는 프레임 base address 정보와 연계

Page Offset(d) (페이지 오프셋)

• Base address를 시작점으로 하는 물리 메모리 주소 변위 표현

  

  

페이징 프로세스

 

페이지 테이블의 크기

• (CPU) 32비트 시스템에서는 일반적으로
• 페이지 테이블의 Entry 하나가 차지하는 크기가 약 4B가 될 수 있다. 이 경우 페이지 테이블을 통해 구분할 수 있는 프레임의 총개수는 2^4B = 2^32개
• 프레임 하나의 크기는 4KB(=2^12 bytes)가 될 수 있음
• 위와 같은 경우 페이지 테이블에서 저장할 수 있는 최대 물리 메모리 크기는 16TB(= 2^32 * 2^12 = 2^44B)가 된다. (주의 : 페이지 테이블에서 최대 메모리 크기와 CPU 레지스터의 관리 가능한 최대 메모리 크기는 다른 개념)

가용 프레임의 할당 전과 할당 후

페이징에서의 Fragementation문제

Internal Fragmentation

• 프로세스의 메모리 요구량이 페이지 크기의 배수가 되지 않는다면 발생(마지막 프레임의 공간 낭비 발생)
• 예시
  • 페이지 크기 : 2048 bytes
  • 프로세스 메모리 요구량 : 72,766 bytes
  • 할당 : 36 pages = 35 pages + 1068 bytes
  • 공간 낭비 : 2048 -1068 bytes = 962 bytes

페이징을 위한 레지스터

페이지 테이블 베이스 레지스터(Page-table base register, PTBR)

• 메인 메모리의 페이지 테이블에 대한 시작 물리 주소 저장

페이지 테이블 길이 레지스터(Page-table length regsiter, PTLR)

• 페이지 테이블에 대한 전체 길이 정보 저장

메인 메모리 이중 접근 문제

• CPU → 물리 메모리 위의 페이지 테이블 접근
• CPU → 프로세스가 저장된 물리 메모리 주소 접근

⇒ 이를 해결하기 위한 방법으로 캐시 사용

Translation Look-aside Buffer(TLB)

• TLB는 작고, 빠른 lookup이 가능한 고속 하드웨어 캐시
• key-value를 가지는 entry(64 -1024개)로 구성되어 있음 (메인 메모리보다 훨씬 작은 크기)
• 크기가 작으므로 페이지 테이블에서 자주 참조되는 페이지에 대한 value만을 저장
• TLB miss가 발생하는 경우 해당 value가 TLB에 새로 적재됨
  • 교체 정책(replacement policy)이 적용
• TLB entry의 address-space identifiers(ASIDs)를 통해 각 프로세스를 식별하여 address-space protection수행

  

Memory Protection

• 각 프레임과 연계된 별도의 protection bit를 정의하여 memory protection(메모리 보호) 수행
• bit값을 통해 페이지에 대한 read-write 혹은 read-only 허용 여부를 정의할 수 있음
• read-only페이지에 write 작업을 시도하는 경우 트랩(trap) 발생

Valid/Invalid bit

• bit값이 valid로 설정되어 있다면 해당 프로세스의 논리 주소 공간에 해당 페이지가 포함됨을 표시(legal page)
• bit값이 invalid로 설정되어 있다면 페이지가 포함되어 있지 않음

  

페이지 공유

Reentrant Code(재배치 코드)

• Non-self-modifying 코드
• 실행 중에는 수정되지 않는 코드
• Reentrant code의 경우 프로세스 간 페이지 공유가 가능
• ex) text editors, compilers, Windows systems

예시

• 40개의 유저 프로세스가 표준 C라이브러리 libc와 연결
• libc는 2MB의 메모리 할당 요구
• libc의 페이지를 공유하지 않는다면 모든 프로세스를 수행하기 위해 80MB의 메모리가 필요
• libc의 페이지를 공유한다면 2MB의 메모리만 필요

  

Hierarchical Page Table(계층 페이지 테이블)

• 페이지 테이블 자체도 불연속 할당 기반으로 관리될 수 있다.
• 페이지 테이블을 더 작은 조각(smaller pieces)으로 나누어 관리

  

Inverted Page Table

• Forwarded Page Table의 경우 모든 프로세스가 페이지 테이블을 가지므로 물리 메모리의 많은 공간을 차지한다는 단점을 가짐
• Inverted Page Table에서는 프로세스 ID(pid)와 해당 프로세스의 페이지 넘버를 연계 구성
• 프로세스는 자신이 사용하지 않는 페이지 정보까지 전부 포함된 페이지 테이블을 유지하지 않으므로 메모리 공간 절감 가능

  

Demand Paging

• 프로그램 실행 도중 요청(demand)되는 페이지에 대해서만 물리 메모리에 적재하는 방식
• 스와핑을 사용하는 페이징 시스템 구현 방식과 유사
• 메모리 효율성이 증대됨

Demand Paging : Page Fault

• "invalid"비트가 할당된 페이지에 접근 시도를 하게 될 때 page fault 발생
• MMU를 통해 "invalid"비트를 확인한 후 OS에게 통보, 이후 trap 발생

  

Demand Paging : Page Fault 처리

• 문맥교환 오버헤드가 생김

Demand Paging : Page Fault 및 EAT

페이지 교체(Page Replacement)

메모리 초과 할당(Memory Over-Allocation)

• 멀티프로그래밍 수준을 높이기 위해 수행
• 프로그램 페이지 외에 I/O를 위한 버퍼 역시 메모리에 할당
• page fault가 발생하는 경우 OS는 프로세스를 종료하거나 페이지 교체(page replacement)를 수행

  

First-In-First-Out(FIFO) Algorithm

• 가장 간단한 페이지 교체 알고리즘 중 하나
• 가장 오래된 페이지부터 우선적으로 교체
• 이해하기 쉽지만 성능은 보장되지 않음

  

Belady's anomaly

• Reference string : 1,2,3,4,1,2,5,1,2,3,4,5
• 더 많은 프레임을 추가하는 것이 더 많은 page fault를 발생시킬 수 있음

  

Optimal Page Replacement

• 가장 낮은 page-fault rate보장
• 가장 오랫동안 사용하지 않을 page를 우선 교체
• 적재할 page 번호를 미리 다 알고 있어야 함

  

Least Recently Used Algorithm

• 진정한 최적은 불가능하지만, 근사 최적은 가능
• 최근에 가장 적게 사용된 page를 우선적으로 교체(과거는 미래를 반영)