[OS] Memory mangement I

범용 컴퓨터 시스템의 목적

• CPU의 활용률(Utilization)을 극대화
• 사용자에게 빠른 응답을 제공
  • 보다 많은 Progam을 Memory에 올려서 실행(Multi-Programming)
  • 여러 Program을 동시에 실행시키기 위한 Scheduling 기법 등장

Memory 관리의 필요성 등장

• 여러 Program이 동시에 Memory에 적재되어 실행되면서, Memory를 공유할 필요가 생김
• Computer의 Memory는 한정된 자원
  • 실행하는 Program이 많아지면 Memory 요구량이 증가

 

주소 공간(Address Space)

• 정의: 프로세스가 참조할 수 있는 주소들의 범위 또는 집합
• 특징
  • 프로세스와 1:1 관계를 가짐
  • 사용자 스레드(thread)는 이 주소 공간을 공유함
• 주소 공간의 크기: CPU의 주소 버스(Address Bus) 크기에 의존
  • ex) 32 bit 주소 버스 시스템의 주소 공간 크기는 $2^{32}$개의 주소를 가질수 있음 (4GB)
• 32 bit 주소 버스를 가진 System이 주소 1개당 1Byte의 Memory를 접근할 수 있다면, 이 System이 Address할 수 있는 주소 공간의 크기는 몇 Byte인가?
  • $2^{32}$=4GB의 주소에 1Byte의 메모리가 접근하니 4GB * 1B = 4Byte 
  • 지금은 64bit 주소 버스로 $2^{64}$을 다 쓰는 서비스는 없음
    • 보통 57 bit 정도 사용

 

물리 주소

• 컴퓨터의 메인 메모리(RAM)를 접근할 때 사용되는 실제 주소
• 기억 장치의 주소 레지스터에 적재되는 주소

 

가상 주소

• 프로세스의 관점에서 사용하는 주소
• CPU 관점의 주소는 사용하는 메모리 모델에 따라 PA일 수도, VA일 수도 있음
• 논리적(Logical)이기 때문에 주소 공간을 의미 있는 단위로 나누어 사용하지 않음
• 초창기엔 컴파일 시점에 물리 주소를 결정했지만, 다중 프로그래밍(Multiprogramming) 환경이 되면서 가상 주소 개념이 도입되고 주소 결정 시점이 다양해짐

다양한 가상 주소의 생성

 

 

Compile Time에서의 주소 결정

• Compiler가 Symbol Table을 만들고 주소는 Symbol Table Relative한 주소로 이루어짐
  • Symbol table: 선언한 function의 이름 같은 것들을 저장(ex. main 형식 이름, 전역 변수 정보)
• Compile된 Object 파일은 주소 0부터 시작함 (Relocatable: 상대 주소)

 

Link Time에서의 주소 결정

• Object 파일들과 System에서 제공하는 Library들을 묶어서 Symbol Table에 의존적이지 않은 주소를 만들어 냄
• Link의 결과로 하나의 Executable 파일이 만들어진 주소는 0부터 시작함
• Executable은 하나의 주소 공간으로 0부터 시작함
  • 실행 파일까지는 0으로 매핑 (아직 물리주소 X)
  • 상대 주소(논리/가상 주소)

 

Load 및 실행 시의 주소 결정

• Load Time
  • Program의 실행을 위해 Loader는 Executable을 Memory(실제 물리 메모리)로 load
  • Loader가 실행 파일을 메모리로 로드할 때 물리 주소 바인딩(물리 주소 결정) 발생
    • Program은 relocatable(재배치 가능한) 주소로 되어 있기 때문에, Base Register를 통해 물리 주소로 변환
    • Program의 시작 주소를 바꾸려면, 다시 Load 해야 함
• Execution Time(Runtime)
  • Process가 실행 될 때 물리 주소가 바뀌는 경우, 물리 주소에 대한 Binding은 Process가 실행될 때 일어남
    • Paging이나 Swapping을 통해서 Process가 올라가는 Memory의 물리 주소는 바뀔 수 있음
  • MMU와 같은 특별한 HW가 필요함
  • 대부분의 범용 OS가 이 방식 사용

 

CPU에서 사용하는 주소에 따른 변환 방법

• CPU에서 Physical Relative Address(상대 주소)를 사용하는 경우
  • Physical Relative Address: 프로그램 내의 명령어 주소들을 메모리의 시작 주소(Base Address)로부터 얼마나 떨어져 있는지(Offset)를 나타내는 상대적인 값
  • 절대 주소(물리 주소) = 시작 주소 + 상대 주소(가상 or 논리 주소)
  • 시작 주소가 결정되면 시작 주소 + 상대 주소의 합으로 물리 주소 생성

 

• CPU에서 Virtual Address(가상 주소)를 페이지 테이블을 사용하는 경우

• Translation의 속도가 중요한 요소가 됨
• ex) Chrome 탭 마다 가상주소가 달라서 메모리 주소가 연속적으로 배치되지 않아, translation을 거쳐야 함

가상 메모리 시스템에서, CPU가 내뱉는 주소를 '논리 주소'라고 부르는데, 이 주소는 항상 0번지부터 시작하는 '상대적인 값'이다.

 

Memory Management Unit (MMU)

• 역할: Virtual Address와 Physical Address 간의 변환을 수행하는 하드웨어 장치 (매핑 테이블)
• CPU로부터 받은 가상 주소를 물리 주소로 번역하여 메모리로 보냄

MMU 로직

 

가상 메모리(Virtual Memory)

• 정의: 실제로 존재하지 않지만, 사용자에게 메모리로서의 역할을 하는 메모리
  • 프로세서 시점에서 보는 메모리
• Basic Idea: 프로세스 실행을 위해 프로그램의 모든 부분이 실제 물리 메모리(Physical Memory)에 있을 필요는 없음
  
  • 현재 실행되고 있는 코드 부분만이 실제 메모리에 있으면 실행 가능
  • ex) 롤 한 판에 사용되는 맵과 챔피언만 메모리에 올리면 게임 플레이 가능

롤 게임 실행 시 가상 memory 배치 로직

가상 메모리 구현

가상 메모리 - Address Mapping Table

 

Paging

• 정의: 주소 공간을 동일한 크기인 Page로 나누어 관리하는 기법 (보통 4KB)
  • 페이지(Page): 가상 메모리(Process)를 고정된 크기로 나눈 하나의 블록
  • 프레임(Frame): 물리 메모리(RAM)를 고정된 크기로 나눈 하나의 블록
  • Block (블록/슬롯): Backing Storage(하드 디스크/SSD)를 페이지와 동일한 크기로 나눈 구역.
  • 페이지 크기 = 프레임 크기
• Page가 하나의 Frame을 할당 받으면, 물리 Memory에 위치하게 됨
  • Frame을 할당받지 못한 Page들은 외부 저장 장치(Backing Storage)에 저장됨
    
    • 외부 저장 장치(Backing Storage)도 Page, Frame과 같은 크기로 나누어져 있음
    • 프레임을 할당받지 못했다는 것은 현재 물리 메모리(RAM)가 꽉 찼거나, 해당 페이지가 당장 필요하지 않아 메모리에 적재되지 않았음을 의미
• Page 번호와 Offset
  • Page 번호(index): 각 Process가 가진 Page 각각에 부여된 번호
    • ex) 1번 Process는 0~63번까지의 Page를 갖고 있음
  • Page 주소(Offset): 각 Page의 내부 주소를 가리킴
    • ex) 1번 Process의 12번 Page의 35번째 byte

중간 점검

• 4KB의 Page를 접근하기 위해 필요한 bit는 12개.
  • 32bit CPU에선 남은 20bit로 Page Number를 표현
    • 4GB의 Logical Address를 Paging 할 수 있음
  • 64bit CPU에선 남은 52bit로 가능하지만 이 정도 개수의 Page를 만들 수 있는 기술력이 아직 안 됨

 

Page Table(페이지 테이블)

• 정의: 각 프로세스의 페이지 정보를 저장하는 테이블로 프로세스마다 하나씩 가짐
• Index: Page Numbe(페이지 번호)
• 내용: 해당 Page에 할당된 물리 메모리 (Frame의 시작 주소)
  • 물리 주소 생성:  Page 주소(Offset) + Frame 시작 주소 = 원하는 데이터의 물리 주소

Page Table을 이용한 Logical(Virtual) Address - Physical Address Mapping

• Page Table은 물리(Physical) 메모리에 위치함
• Page Table 기준 레지스터(PTBR: Page Table Base Register)가 물리 Memory 내의 Page Table의 시작 주소를 가리킴
• Page Table 길이 레지스터(PTLR: Page Table Length Register)가 Page Table의 Size를 나타냄
  • 둘 다 CPU 내부에 하드웨어 레지스터로 존재함

Page Table을 이용한 주소 변환

• p: 페이지 번호(Page Number)
  • 의미: CPU가 참조하려는 가상 메모리상의 "몇 번째 페이지인가"를 나타내는 인덱스
  • 역할: 이 번호(p)를 가지고 페이지 테이블을 찾아가서 프레임 번호를 알아냄
• d: 오프셋 / 변위(Displacement / Offset)
  • 의미: "페이지(또는 프레임) 내부에서 정확히 어디인가"를 나타내는 주소
  • 역할: 주소 변환 과정에서 변하지 않고 그대로 물리 주소의 뒷부분(d)으로 복사됨
    • 방 번호는 바뀌어도 방 안에서의 위치(d)는 똑같기 때문
• f: 프레임 번호(Frame Number)
  • 의미: 페이지 테이블을 통해 알아낸, 실제 물리 메모리(RAM)상의 "몇 번째 프레임인가"를 나타냄
  • 역할: 가상 주소의 페이지 번호(p)가 실제 메모리 위치인 프레임 번호(f)로 교체(Mapping)된 것
• 결과: 최종적으로 f와 아까 떼어둔 d가 합쳐져서 실제 물리 주소(f+d)가 완성됨

 

Page Table Entry(PTE)

• Page Table의 레코드(항목)에 프레임 주소 외에 다른 정보들이 꽉꽉 눌러 담겨 있음
• 주요 필드:
  • Page Base Address: 할당된 Frame의 시작 주소
    • 이를 통해 물리 Memory에 접근할 수 있음
  • Flag Bits
    • Accessed Bit: Page에 대한 접근이 있었는지
    • Dirty Bit: Page 내용의 변경이 있었는지
    • Present Bit: 현재 Page에 할당된 Frame이 있는지
    • Read/Write Bit: 읽기/쓰기에 대한 권한 표시
  • 그 외 구성에 따라 여러 가지 내용들이 포함될 수 있음

 

TLB(Translation Look-aside Buffer: 변화 색인 버퍼)

• Paging 방법에서는 Data로의 접근이 항상 두 번의 Memory 접근을 거쳐야 함
  • Page Table에서 한 번, 물리 Memory 내의 Data에서 한 번
  • Memory 접근 속도를 크게 떨어뜨림
• 해결 방법 - TLB in MMU(CPU)
  • Page Table을 이용해 변환된 주소를 TLB에 저장해 둠
  • 다음 접근 시에는 TLB에 저장된 값을 이용하여 빠르게 변환된 주소를 얻을 수 있음
    • TLB는 Register이기 때문에, Memory 보다 빠른 수행이 가능함
  • TLB Hit Ratio
    • TLB 내에서 원하는 주소를 찾을 수 있는 확률
    • 높을 수록 Memory 접근 속도를 향상시킬 수 있음
• TLB: 매번 사전(Page Table, 물리 메모리에 위치)을 찾으러 가기 귀찮으니, 자주 쓰는 단어(최근 변환된 Page 주소)를 CPU 옆에 있는 초고속 메모리(TLB, register)에 저장하여 사용하게 해주는 캐시 역할을 하는 레지스터

TLB 도식

 

다양한 Page Table 구현

다단계 페이지 테이블(Multi-level) Page Table의 필요성

• System의 발전에 따라 가상 주소 공간이 커지면서 Page Table의 크기가 너무 커져 메모리를 많이 차지하는 문제 발생
  • 위 TLB 도식 맨 아래 필기에 적힌 듯이 아까움
• ex) 32 Bit 가상 주소 공간을 가지는 System

100개의 프로그램 실행 시 400MB의 page table이 필요함

• 32bit 주소 체계는 4GB(4*$2^{30}$)를 표시할 수 있음
  • 페이지 크기가 4KB(4*$2^{10}$)이므로 총 1M($2^{20}$개의 페이지(Offset)를 가질  수 있음
  • 각 페이지 마다 int 형으로 number를 매겨준다면 4byte * 1M = 4MB
  • 한 프로세스마다 페이지 테이블로 4MB가 사용됨
• 문제점
  • 메모리 낭비 문제: 프로세스가 실제로는 10KB만 사용하더라도, 나머지 비어있는 공간(Hole)을 포함한 4MB 짜리 테이블 전체를 메모리에 유지해야 함
  • 연속 할당 문제: 테이블 전체가 하나의 거대한 배열이므로, 메모리 상에서 연속된 공간을 차지해야 함

 

2 Level Page Table 구현

• 단일 페이지가 가진 메모리 낭비 문제와 연속 할당 문제를 해결하기 위해 고안됨
• Outer Page Table을 하나 더 두어, Page Table들을 가리키도록 함
  • 프로세스의 주소 공간 중 실제 사용되지 않는 부분(Sparse Address Space)이 많다는 점을 이용하여, "안 쓰는 구간의 페이지 테이블은 만들지 않는다"는 것이 핵심 아이디어

• ex) 앞 예시에서, 20 bit를 차지하는 Page 번호를 다시 아래와 같이 나눔
  • 10 bit Page 번호
  • 10 bit Page 주소

32bit 주소의 Two level page table

• p1: 상위 10비트로 Level 1 테이블의 인덱스를 의미하며 그곳엔 "어떤 Level 2 테이블을 쓸까?"가 결정되어 있음
• p2: 중간 10비트로 Level 2 테이블의 인덱스를 의미하며 그곳엔 "그 테이블 안에서 몇번째 페이지인가?"가 결정되어 있음

 

2 Level Page Table 도식

2 Level Page Table의 Table 접근(Walk)

12KB 프로세스 매핑 예시(2 Level Page Table)

1. 1개의 L1 Page Table, 3개의 L2 Page Table을 이용하여 Mapping 한 예시
2. L1 접근: CPU는 논리 주소의 L1 index(앞에 10bit)를 사용하여 L1 페이지 테이블에 접근, L1 항목은 해당 영역의 L2 페이지 테이블의 시작 주소(Page Frame Number)를 포함
3. L2 접근: L1에서 얻은 L2 페이지 테이블 시작 주소와 논리 주소의 L2 인덱스(뒤에 10bit)를 합하여 L2 페이지 테이블 항목에 접근, 이 항목은 최종 물리 페이지 프레임 번호(PFN)를 포함
4. 물리 주소 생성: 최종 PFN에 논리 주소의 오프셋을 결합하여 실제 물리 주소를 생성

• 총 4GB의 가상 주소 공간 중 실제로 사용되는 것은 12KB(3 Page) 뿐(Process A)이지만, 2-level table 구조 덕분에 전체 4GB를 포괄하는 거대한 단일 페이지 대신, 실제 사용하는 3페이지에 대응되는 3개의 L2 테이블과 이를 연결하는 1개의 L1 테이블만 메모리에 할당됨

구분	단일 페이지 테이블 (Single)	2단계 페이지 테이블 (2-Level)
메모리 공간	전체 주소 공간에 대한 테이블을 다 만들어야 함 (낭비 심함)	실제 사용하는 영역의 테이블만 생성함 (효율적)
메모리 할당	반드시 연속된 큰 공간이 필요함	테이블이 쪼개져서 불연속적으로 저장 가능
속도	메모리 접근 1회 (빠름)	메모리 접근 2회 (느림) >> TLB 하드웨어로 보완

• Single Page Table: Process당 4MB
• 2-Level Page Table: 4KB(L1) + 4KB(L2)
  • $2^{10}$(1024개의 칸) * 4 byte(한 칸의 주소=32bit=4byte)
• PT의 Level이 많은 경우 장점
  • Level이 3인 경우 생각해보기(7, 7, 6으로 쪼갤 경우)
    • Level 1, 2 테이블 크기가 $2^7$으로 
    • Level 3 테이블의 크기가 $2^6$으로 엔트리가 64개 밖에 안 됨
      • 주소 하나가 4바이트(offset)이므로 테이블의 크기가 256바이트가 됨
      • 이 256 byte 짜리 테이블을 저장하기 위해 기본 단위인 4KB(4096 byte)를 사용함
        • 한 페이지 프레임 당 3840 byte 메모리 낭비
          • 공간 낭비 관점: "테이블을 저장할 때마다 프레임 내부에 3840바이트의 빈 공간(공기)이 생긴다."
          • 매핑 능력 관점: "테이블 엔트리 개수가 적어서(64개), 10-10 방식(1024개)보다 한 번에 매핑할 수 있는 메모리 양이 1/16로 줄어든다."
  • 어떨 때 PT가 차지하는 Memory가 줄어들까?
    • 4MB의 한 테이블(1024:page x 4096:offset) 하나가 모두 삭제됐을 때, Level 2 테이블(4KB) 하도 사라짐
• 단점
  • 성능 오버헤드가 증가하므로 Table Walk(접근)에 걸리는 시간이 증가함

 

Inverted Page Table

• Multilevel Page Table에서와 같은 Page Table의 용량 증가 문제를 해결하기 위한 다른 방법
• 동기
  • 64bit 시스템에서는 Multilevel Paging 정보의 크기가 너무 커짐
  • 아무리 가상 메모리 공간이 크더라도, 물리 메모리의 크기에는 한계가 있음
  • 모든 물리 메모리는 가상 메모리 페이지에 Mapping될 확률이 높음
• Think Different
  • 기존 방식은 Page #을 이용하여 Frame #을 검색
  • Inverted Page Table: 시스템 전체에 하나의 테이블만 둠
    
    • Page Table Index: Frame 번호
    • Page Table 내용: 해당 Frame을 사용하는 (Process Id, Page 번호) 쌍

• ex) 12번 Process의 23번 Page, 34번째 Data
  • Page Table을 처음부터 검색하여 12(pid), 23(page number)의 내용을 가지는 부분의 Index를 보고 Frame을 알 수 있음
    • 찾고자 하는 Data와 배열의 Content가 일치함을 확인했을 때, 그 배열의 Index가 검색 결과
  • 해당 Frame의 34번째 Data에 접근
• Page Table은 보다 적은 용량을 차지하지만, Table을 검색하는데 시간이 오래 걸림
  • 해쉬 테이블 등을 사용하여 단축 가능
  • Arm 기반의 메모리가 적은 모바일 기기 등에 사용

구분	일반 페이지 테이블 (100개 프로세스)	역 페이지 테이블 (시스템 전체)
기준	가상 주소 공간 (Virtual)	물리 메모리 공간 (Physical)
테이블 개수	100개 (프로세스마다 하나씩)	1개 (전역 테이블)
메모리 사용량	400 MB	4 MB
효율	프로세스 늘어나면 메모리 터짐	프로세스 늘어나도 일정함

 

Demand Paging

• 정의: Process 실행에 필요한 모든 Page를 Memory에 올리지 않고, 요청이 발생할 때(Demand)만 메모리에 올리는 Paging 기법
  • ex) 게임 로딩에서 메모리를 Load할 때 각 판에 필요한 memory만 로드
• Valid and Invalid Page
  • Page Table Entry의 Present Bit를 사용하여 페이지의 유효성(현재 물리 메모리에 있는지)을 판단
  • DRAM에 잘 올라와 있는지 확인
• 필요한 Page는 Paging Service를 통해서 한 Process에 필요한 Page를 Memory와 Secondary Storage(Backing Storage) 간에 이동시킴
• 장점
  • 실행을 위한 물리 메모리 구성 시간이 줄어듬
  • 프로세스 전체 이미지를 올리지 않기 때문에, 실제 필요한 전체 물리 메모리의 양을 줄일 수 있음
• 단점
  • 참조하려는 Page가 Valid한 경우
    • 해당 페이지가 물리 메모리에 존재하므로 정상적인 참조가 발생
  • 참조하려는 Page가 Invalid한 경우
    • 참조하고자 하는 page가 실제 물리 메모리에 없으므로 이에 대한 처리가 필요
    • Page Fault 발생 >> 오버헤드 발생
• Demand Paging을 하기 위해서 Page Table에 어떠한 정보가 더 필요할까?
  • Demand Paging을 구현하기 위해서는 페이지가 현재 물리 메모리에 존재하는지 여부를 나타내는 Present bit(혹은 Valid bit)와 같은 추가 정보가 Page Table에 필요함

 

Page Fault

• 프로세스가 페이지를 참조했을 때, 해당 페이지에 할당된 Frame이 없는 경우(present bit == invalid)에 발생
• 수행 내용: Page Fault가 발생하면 OS의 Page Fault Handler가 실행되며 다음과 같은 절차를 수행
  1. 새로운 Frame을 할당받음: 물리 메모리 내의 빈 Frame 확보
  2. Backing  Storage에서 Page의 내용을 Frame에 불러들임: 디스크(Backing Storage)에 저장되어 있던 필요한 페이지의 내용을 새로 할당받은 Frame으로 복사
  3. Page Table을 재구성: 새로 로드된 페이지 정보(Frame number, Present it=Valid)로 Page Table 엔트리를 업데이트 함
  4. Process의 작업 재시작: Page Fault를 유발했던 명령어부터 프로세스 작업을 다시 시작

• Page Fault 발생 빈도는 시스템의 Locality(지역성) 특성과 밀접하게 관련됨
  • 지역성이 잘 나타나는 경우(즉, 같은 페이지들을 반복해서 참조하는 경우), 처음에 몇 번의 Page Fault가 발생하여 Working Set이 형성된 후에는 Page Fault 발생률이 낮게 유지됨
• Locality(지역성): 프로세스가 일정 시간 동안 특정 페이지 집합을 집중적으로 참조하는 경향을 의미함

• Working Set
  • 어떤 Window 시간 동안에 접근한 Page들의 집합
  • 현재 이 프로세스가 집중적으로 쓰는 도구들의 목록
• 특징
  • 시간마다 Working Set은 변할 수 있음
  • 적당한 시간 Window를 설정하면, Working Set은 프로세스의 Locality를 잘 나타냄
  • OS는 Working Set 크기만큼의 Frame을 프로세스에게 할당하여 Page Fault 발생률을 낮추려고 시도함
• Trashing
  • 프로세스의 실행 시간 중, Page Fault를 처리하는 시간이 실제 Execution 시간보다 길어지는 상황을 의미
  • 시스템이 너무 바빠서 일은 안 하고 짐만 나르는 상황
• 원인
  • 시스템에 Frame이 충분히 할당되지 않아 프로세스의 Working Set 전체를 메모리에 올릴 수 없을 때 발생하기 쉬움
  • 프로세스가 페이지를 사용하자마자 곧바로 교체(Page Out)되어야 하고, 다시 필요해질 때 Page Fault가 발생하여 로드(Page In) 되는 현상이 반복됨