[운영체제] #10. Memory Management (1)

목차

• 주소 공간(Address Space)
• 물리 주소(PA)와 가상 주소(VA)
• 가상 메모리
• Paging
• Translation Look-aside Bufers (TLB)
• 다양한 Paging Table

 

서론

• 범용 컴퓨터 시스템의 목적
  • CPU 의 활용률 (Utilization) 을 극대화
  • 사용자에게 빠른 응답을 제공
    • 보다 많은 Program 을 Memory 에 올려서 실행 (Multi-Programming)
    • 여러 Program 을 동시에 실행시키기 위한 Scheduling 기법 등장
• Memory 관리의 필요성 등장
  • 여러 Program 이 동시에 Memory 에 적재되어 실행되면서, Memory 를 공유할 필요가 생김
  • Computer 의 Memory 는 한정된 자원
    • 실행하는 Program 이 많아지면 Memory 의 요구량이 증가

 

주소 공간

• 정의
  • 프로세스의 주소 공간:
    • 프로세스에서 참조할 수 있는 주소들의 범위 (집합) 
    • 프로세스는 고유한 주소 공간을 가지며, 물리 메모리와의 독립성을 유지 (1:1 관계)
    • 각 Thread 는 동일한 주소 공간을 공유
  • 주소 공간의 크기:
    • CPU의 주소 버스 (Address Bus)의 크기로 결정
      ex) 주소 버스가 32 bit 시스템에서는 최대 $2^{32}$ 개의 주소(4GB)가 가능
    • 실제 사용 가능한 주소는 시스템의 물리 메모리 크기에 따라 달라짐

 

물리 주소와 가상 주소

• 물리 주소 (Physical Address)
  • 컴퓨터의 메인 메모리를 접근할 때 사용되는 주소
  • 기억 장치의 주소 레지스터에 적재되는 주소
    ex) "서울특별시 강남구 ~"
• 가상 주소 (Logical Address or Virtual Address)
  • Process 관점에서 사용하는 주소
  • CPU 관점의 주소는 물리 주소도, 가상 주소도 될 수 있음
    • 어느 Memory Model 을 사용하느냐에 따라 달라짐
  • Logical 이기 때문에 주소 공간을 의미 있는 단위로 나누어 사용하지 않음
    ex) "우리집" 이라는 태그를 GPS 앱에 설정해 놓음
• 실제 예시
  • 두 개의 프로세스 $P_{1}$, $P_{1}$ 가 실행 중이고, 각각 다음과 같은 가상 주소를 사용한다고 가정.
    • 프로세스 P1P1P1과 P2P2P2는 모두 가상 주소 0x00000을 사용하지만,
    • 운영체제는 이를 물리 주소 0x1A3B50 와 0x2C5D7로 매핑하여 충돌 없이 독립적으로 동작하도록 한다.

프로세스	가상 주소	물리 주소
P1	0x0000	0x1A3B5
P2	0x0000	0x2C5D7

 

 

초창기 컴퓨터의 주소 관리

• 과거에는 물리 주소를 Compile Time에 고정하여 사용했음
• 하지만 멀티 프로그래밍(Multiprogramming) 환경에서는 하나의 프로그램 실행 시점에서 고정된 물리 주소를 사용하는 것이 어려웠음 (여러 프로그램이 동시에 실행될 때, 중복 주소 문제가 발생하기 때문)
• 이로 인해 가상 주소 공간(Logical Address) 개념이 도입

 

다양한 가상 주소의 생성

 

 

1. Compile Time
   
   • Symbol Table 생성:
     • 컴파일러가 심볼 테이블(Symbol Table)을 만들어 변수와 함수의 이름을 주소에 매핑합니다.
     • 이때 만들어지는 주소는 Symbol Table Relative 주소로, 실제 메모리 주소는 아직 결정되지 않음.
   • Relocatable Object File:
     • 컴파일된 프로그램은 Relocatable Object File로 만들어지며, 주소는 0부터 시작하는 상대적 주소를 가짐.
       ex) main() 함수가 0번 주소, foo() 함수가 20번 주소 등.
       
       
2. Link Time 
   • Library 및 Object File 결합:
     • 여러 Object 파일(.o)과 라이브러리를 결합하여 실행 파일(.out)을 생성.
     • Executable 파일의 주소는 0부터 시작한다. 
       
       
3. Load Time
   • Program 의 실행을 위해 Loader 는 Executable 을 Memory 로 Load 한다.
   • 주소 공간 전체가 Memory 에 올라간다면, Load 시에 물리 주소에 대한 Binding 이 일어난다.
     • Program 은 Relocatable 주소로 되어 있기 때문에 뒤에 배울 Base Register 를 통해서 물리 주소로 바꾸어 실행하게 된다.
   • 만일 Program 의 시작 주소를 바꾸려면, 다시 Load 해야 한다.
     
     
4. Execution Time
   • Program 이 실행 될 때 물리 주소가 바뀌는 경우, 물리 주소에 대한 Binding 은 Process 가 실행될 때 일어난다.
     • 나중에 배울 Paging 이나 Swapping 을 통해서 Process 가 올려지는 Memory 의 물리 주소는 바뀔 수 있다.
   • 이러한 형태의 주소 결정 방법을 사용하기 위해서 MMU (Memory Management Unit) 와 같은 특별한 하드웨어가 필요하다.
   • 대부분 General Purpose 운영체제는 이러한 방식을 사용한다.

 

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

1. CPU 에서 Physical Relative Address 를 사용하는 경우

• Base Address (시작 주소) + Offset 방식:
  • Base Register에 프로그램의 시작 주소가 저장되고, 명령어에서 주어진 Offset 값을 더해 물리 주소를 계산.
    ex) Base Address가 346, Offset이 14000이라면 최종 물리 주소는 14346.

 

2. CPU 에서 Virtual Address 를 사용하는 경우

• Translation 과정:
  • CPU가 가상 주소를 생성하면, Translation Logic이 이를 물리 주소로 변환.
  • 변환 속도는 MMU와 TLB(Translation Lookaside Buffer) 같은 하드웨어의 성능에 의해 좌우.
    ex) 가상 주소 0x0000 → 물리 주소 0x2C5D7.

 

 

Memory Management Unit (MMU)

• 역할:
  • 가상 주소(Virtual Address)를 물리 주소(Physical Address)로 변환하는 하드웨어 장치.
  • CPU가 명령어 실행 시 가상 주소를 생성하면, MMU가 이를 실제 물리 주소로 변환해 메모리에 접근.
• 구성 요소:
  • Page Table:
    • 가상 주소와 물리 주소 간의 매핑 정보를 저장.
    • 각 프로세스는 고유의 Page Table을 가짐.
  • Translation Logic:
    • MMU는 Page Table을 활용하여 변환 작업을 수행.
• 작동 과정:
  1. CPU가 가상 주소를 생성.
  2. MMU가 Page Table을 조회하여 가상 주소를 물리 주소로 변환.
  3. 변환된 물리 주소를 통해 메모리에 접근.

 

 

가상 메모리

• 정의:
  • 사용자 관점에서는 물리적으로 존재하지 않는 메모리 공간을 실제 메모리처럼 사용할 수 있도록 제공.
  • 운영체제와 MMU가 물리 메모리를 효율적으로 활용하기 위해 가상 메모리를 구현.
• 목적:
  • Process 가 수행 되기 위해서 Program 의 모든 부분이 실제 메모리 (Physical Memory) 에 있을 필요 없음
    • 현재 실행되고 있는 Code 부분만이 실제 Memory 에 있으면 Process 는 실행이 가능 
  • 각 프로세스에 독립적인 메모리 공간을 제공.
  • 실제 물리 메모리 크기보다 큰 메모리를 사용하는 것처럼 보이도록 지원.
• 구현
  • Page Table 기반 매핑:
    • 가상 메모리를 작은 단위(페이지)로 나누어 물리 메모리의 페이지와 매핑.
    • 예:
      • 프로세스 $P_{1}$의 가상 주소 0x0000 → 물리 주소 0x1000.
      • 프로세스 $P_{2}$의 가상 주소 0x0000 → 물리 주소 0x2000.
  • 메모리 부족 시 처리:
    • 스왑(Swap):
      • 물리 메모리가 부족하면, 사용하지 않는 페이지를 디스크(Secondary Storage)로 옮김.
      • 필요한 경우 다시 물리 메모리로 로드.

 

 

가상 Memory - Address Mapping Table

• Logical Address Space와 Physical Address Space를 매핑하는 표.
  • 각 Logical Address (논리 주소)는 Page 단위로 나뉨.
  • 각 Page는 Frame (물리 메모리의 단위)에 매핑됨.
• 예:
  • Logical Address의 Page 0 → Physical Address의 Frame 2
  • Logical Address의 Page 1 → Physical Address의 Frame 5
• 중요 개념: Page Table을 사용해 각 Page가 어떤 Frame에 매핑되는지 관리.

 

Paging

• 주소 공간을 일정한 크기의 Page로 나눠 관리.
  • Page:
    • 논리 메모리를 고정된 크기로 나눈 블록.
    • 각 Page는 Page Table을 통해 물리 메모리의 Frame과 연결.
  • Frame:
    • 물리 메모리를 고정된 크기로 나눈 블록.
• 기본 동작:
  • 프로세스의 논리 주소에서 해당 Page를 확인.
  • Page Table을 조회해 해당 Page가 매핑된 Frame의 시작 주소를 찾음.
  • Frame의 시작 주소 + Offset을 더해 물리 주소를 계산.
• Page와 Frame의 크기는 동일.
  • 보통 4KB 단위로 설정.
  • 예) 1개의 Page = 4KB = 1개의 Frame = 4KB
• Page Table의 역할:
  • Page가 할당된 Frame 정보를 저장.
  • Page가 Frame에 할당되지 않았다면, 해당 Page는 Backing Storage (디스크)에 저장.

 

중간 점검

1. 128MB의 물리 메모리를 4KB 단위로 Paging하면, 몇 개의 Frame이 필요한가?
   • 1 Frame = 4KB
   • 128MB / 4KB = 32,768 Frame 필요.
2. 4GB Logical Address를 Paging하려면, 총 몇 개의 Page가 필요한가?
   • 1 Page = 4KB
   • 4GB / 4KB = 1,048,576 Page 필요.
3. Page의 크기가 4KB일 때, 한 Page의 메모리를 Access하기 위한 주소는 몇 비트인가?
   • 1 Page = 4KB = $2^{12}$ 바이트.
   • 따라서 12비트 주소가 필요.

 

Page Table

• 정의
  • 각 프로세스의 Page 정보를 관리하는 데이터 구조. (Process 마다 하나의 Page Table 을 가짐)
  • Index (Page 번호)와 그에 매핑된 Frame 번호로 이루어짐.
  • 논리 주소에서 물리 주소로의 변환을 지원.
• 구현
  •  
  • Page Table 은 물리 Memory 에 위치
  • Page Table 기준 레지스터 (PTBR : Page Table Base Register) 가 물리 Memory 내의 Page Table 을 가리킴
  • Page Table 길이 레지스터 (PTLR : Page Table Length Register ) 가 Page Table 의 Size 를 나타냄

 

Page Table 을 이용한 LA-PA Mapping

• 예제
  • Page 크기 : 4KB ($2^{12}$ 바이트)
    • 하위 12 bit 가 offset
  • Logical Address : 32 bit (0x00001403) // 16진수 한자리는 4bit
    • Page Offset : 0x403 (하위 12bit)
    • Page Number : 0x0001 (상위 20bit)
  • Page Table
    • Page 1 -> Frame 9

Page	Frame
0	5
1	9
2	3

 

계산해보면, Frame 9 의 시작 주소 = 9 x 4KB = 0x9000 이고, Page Offset 은 0x403 이므로,

LA = 0x0001403 이 PA = 0x9403 로 Mapping 된다.

 

 

Page Table 을 이용한 주소 변환

 

• LA (Logical Address): CPU가 생성하는 주소.
• Page Table:
  • Page 번호를 Frame 번호로 매핑.
  • 각 Process는 자신의 Page Table을 가짐.
• 변환 과정:
  1. Page 번호로 Page Table을 조회.
  2. Frame 번호를 가져옴.
  3. Page Offset을 더해 최종 PA를 계산.

 

Page Table Entry (PTE)

• PTE란?:
  • Page Table의 Record.
  • Page에 할당된 Frame의 시작 주소와 상태 정보를 포함.
• PTE의 주요 필드:
  • Page Base Address: Page가 할당된 Frame의 시작 주소.
  • Flag Bits
    • Accessed Bit: 해당 Page에 접근이 있었는지 표시.
    • Dirty Bit: Page 내용이 변경되었는지 여부.
    • Present Bit: 해당 Page가 현재 물리 메모리에 존재하는지 여부.
    • Read/Write Bit: 읽기/쓰기 권한 여부.

 

Translation Look-aside Buffer (TLB)

• 도입 배경
  • 기존 Paging 방법에서는 Data 로의 접근이 항상 2번의 Memory 접근을 거쳐야 함
    • Page Table 에 한 번, 물리 Memory 내의 Data 에 한 번
    • Memory 접근 속도를 크게 떨어뜨림
•  정의
  • 메모리 관리 장치(MMU) 에서 사용하는 캐싱 메모리.
  • Page Table의 일부 정보를 저장하여 주소 변환 속도를 높임.
  • CPU가 논리 주소(Logical Address)를 물리 주소(Physical Address)로 변환할 때, 매번 Page Table을 참조하면 성능이 저하됨.
  • TLB는 이러한 과정을 캐시화하여 성능을 개선.
  • TLB 는 Register 이기 때문에, 빠른 수행이 가능함
• 동작 원리
  • TLB Hit:
    • 요청된 논리 주소의 변환 정보가 TLB에 존재.
    • CPU는 TLB에서 변환된 물리 주소를 즉시 가져옴.
    • Page Table 접근 없이 주소 변환이 완료됨.
    • 속도가 매우 빠름.
    • TLB Hit Ratio
      • TLB 내에서 원하는 주소를 찾을 수 있는 확률
      • 높을 수록 Memory 접근 속도를 향상시킬 수 있음
  • TLB Miss:
    • 요청된 논리 주소의 변환 정보가 TLB에 없음.
    • Page Table을 조회하여 변환 정보를 가져옴.
    • 변환 정보를 TLB에 저장하여 다음 요청에 대비.

 

Multilevel Page Table

• 필요성
  • System 의 발전에 따라 가상 주소 공간도 매우 큰 용량을 요구하게 됨
  • 그로 인해 Page Table 의 크기가 커지고, 그 차지하는 공간에 의해 Paging 이 잘 이루어질 수 없게 되고 있음
    ex) 32 Bit 가상 주소 공간을 가지는 System
    • Page 크기 : 4KB ($2^{12}$)일 경우,
    • 총 Page 개수 = $2^{32}$ / $2^{12}$ = $ 2^{20} $ (약 1M 개 페이지)
    • Page Table 의 크기 : 1M ($2^{20}$) * 4B = 4MB
      • Page Table Entry 의 값 하나는 보통 4B 를 차지함
  • 모든 프로그램이 4MB 의 페이지 테이블을 필요로 하면, 시스템 메로리를 낭비함
  • Page Table 자체도 Paging 된 공간에 저장됨
• 해결 (2 Level Page Table)
  • Outer Page Table (p1) 을 하나 더 두어, Page Table (p2) 을 가리키도록 한다.
    ex) 앞서의 예에서, 20 Bit 를 차지하는 Page 번호를 다시 아래와 같이 나눈다.
    • 10 Bit Page 번호
    • 10 Bit Page 주소
  • 결국 32 Bit 주소의 모양은 아래와 같게 된다.

 

아래는 12KB Process Mappig 이다. 한번 간단하게만 확인해보자.

 

Page Table Level 과 Memory 성능

• 하나의 주소 공간을 Mapping 하는 Page Table의 크기:
  • 단일 Page Table의 경우, 페이지 수에 비례하여 테이블 크기가 커짐.
  • 다단계 Page Table을 사용하면 메모리 낭비를 줄일 수 있음.
• PTE (Page Table Entry):
  • 각 레벨의 Page Table Entry가 추가적인 메모리를 사용함.
  • 여러 레벨의 Page Table을 사용하면 특정 레벨의 메모리 접근 속도가 느려질 수 있음.
• 단점: 다단계 구조로 인해 Table Walk에 소요되는 시간이 증가.

 

 

Inverted Page Table

• 동기 : 페이지 테이블의 용량 크기 문제를 해결
• 해결 방법
  • 아무리 가상 Memory 공간이 크더라도, 물리 Memory 크기에는 한계가 있음
  • 모든 물리 Memory 는 가상 Memory 의 Page 에 Mapping 될 확률이 높음

• 작동 방
  • 기존 방식은 Page # 를 이용하여 Frame # 를 검색
  • Inverted Page Table 은 CPU 에서 참조하는 Address 와 PID 조합으로 Page ID 를 만들어 Page Table 내에서 Page ID 를 검색함
    • Page ID 를 발견하면, 해당 Frame # 를 Logical Address 공간으로 Mapping
      ex) $P_{2}$ 프로세스가 5번 Page 에 접근하려고 할 때,
      • Frame # 4번에 Mapping 되어 있다고 가정하면, 이 Table 에서 찾아서 간다.
• 구현
  • 단일 Page Table:
    • 모든 Frame 정보를 저장하는 하나의 테이블만 유지.
    • 테이블 항목: PID, Page 번호, Frame 번호로 구성.
  • 검색 과정: PID와 Page 번호를 기반으로 테이블에서 일치하는 Frame 번호를 탐색.
  • 장점: 물리 메모리 크기에 비례하여 테이블 크기 절감.
  • 단점:
    • 테이블 검색 시간이 증가할 수 있음.
    • 해시 테이블과 같은 추가적인 자료구조 사용 가능.

 

Demand Paging

• 정의
  • 필요한 Page만 메모리에 로드:
    • 프로세스 실행을 위해 모든 Page를 메모리에 올리지 않고, 실행 중 필요한 Page만 가져오는 방식.
  • 나머지 Page는 Secondary Storage(디스크)에서 대기.
• 기능
  • Valid Page: 메모리에 로드된 Page.
  • Invalid Page: 메모리에 없는 Page로, 접근 시 Page Fault 발생. (Secondar Storage 에 있음)
• 장점
  • 실행을 위한 물리 Memory 구성의 시간이 줄어든다
  • Process 의 전체 이미지를 Memory 에 올리지 않기 때문에, 실제 필요한 전체 물리 Memory 양을 줄일 수 있다.
• 단점
  • 참조하려는 Page 가 InValid 한 경우
    • Page Fault:
      • Page가 메모리에 없는 상태에서 접근 시 발생하는 중단.
      • 프로세스 실행이 일시적으로 지연될 수 있음.
    • Page Fault를 처리하기 위한 추가적인 관리가 필요.

 

 

Page Fault

• 정의
  • Process 가 Page 를 참조하였을 때 해당 Page 가 할당 받은 Frame 이 없는 경우
    • 있는 경우 (present bit == valid) : Page base address 를 통해 해당 Frame 에 접근
    • 없는 경우 (present bit == invalid) 
      • Page Fault 발생 : Frame 을 새로 할당 받아야 함
      • Page Fault Handler 수행 (trap : 동기적 이벤트 // process 가 발생시켜서)
        
        • 새로운 Frame 를 할당 받음
        • Backing Storage 에서 Page 의 내용을 다시 Frame 에 불러들인다
        • Page Table 을 재구성한다
        • Process 작업을 재시작한다.

 

그래서, Page Size 가 4KB 로 정해짐

 

Page Fault - Locality

• 정의
  • 프로그램이 실행되면서 주소 공간에 접근하는 특정 패턴.
  • 시간적 지역성 (Temporal Locality):
    • 최근에 접근한 데이터는 다시 접근될 가능성이 높음.
      ex) 루프에서 동일 변수 반복 접근.
  • 공간적 지역성 (Spatial Locality):
    • 특정 메모리 주소에 접근하면 그 인근 주소도 접근될 가능성이 높음.
      ex) 배열 연속 접근.

• 그래프 설명
  • Locality가 높은 경우, 적은 수의 Page를 메모리에 유지해도 Page Fault가 줄어듦.
  • 일반적인 경우: 지역성이 유지되면 Page Fault 발생 빈도가 낮음.
  • VOD (Video On Demand) 시나리오: 데이터 접근 패턴이 불규칙한 경우 Page Fault 이 이어짐

 

Working Set

• 정의
  • 어떤 시간 Window 동안에 접근한 Page 들의 집합
  • 시간마다 Working Set 이 변함
    • ...25737456745680120123456
      • $W_{s} = {4,5,6,7,8,0}$
    • 적당한 Window 를 잡으면, Working Set 은 Locality 를 나타냄
      • 이를 기반으로 Context Switching 을 하거나 등등..
• Thrashing
  • Process 실행 시간 중, Page Fault 를 처리하는 시간이 Execution 시간보다  긴 상황
  • 줄이는 것이 좋음