[PintOS Project 3 - VIRTUAL MEMORY] 가상 메모리 이론 공부1 물리적인 메모리 관리(Memory Management)

KEY-WORD

• Logical Address와 Physical Address
• 주소 바인딩 (compile, load, run(execution))
• MMU -> Dynamic Relocation(base 레지스터 + limit 레지스터)
• Dynamic Loading, Overlays, Swapping(swap in,out / backing store)
• Dynamic Linking(shared 라이브러리) 과 Static Linking(static 라이브러리)
• 연속할당(first fit, best fit, compaction)과 불연속 할당(paging)
• 페이징, 페이지 엔트리, 페이지 테이블, 다중 페이지 테이블

 

메모리 관리 

메모리 주소의 종류와 주소 바인딩, 변환방식, 관련 용어, 물리적인 메모리 관리에 있어서 두 방식 중 하나인 연속할당을 알아본다.

물리적인 메모리 관리 중 남은 한 방식인 불연속할당과 관련해 페이징 기법에 대해 알아본다.

 

---

Logical(Virtual) Address vs Physcal Address

• Logical address (=virtual address)
  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address 임
• Physical address
  • 메모리에 실제 올라가는 위치
• 주소 바인딩 : 주소를 결정하는 것
  
  • Symbolic 주소 ➡️ Logical 주소 ➡️ Physical 주소
  • Symbolic : 변수 같은 상징으로 코딩을 함

 

 

• Compile time binding
  • 물리적 메모리 주소(physical address)가 컴파일 시 알려짐
  • 시작 위치 변경시 재 컴파일
  • 컴파일러는 절대 코드(absolute code) 생성

-------  컴파일 때 메모리 주소가 정해지느냐에 따라 위에와 아래가 나뉜다 -------

• Load time binding
  • Loader의 책임하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능
• Execution time binding(=Run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음(Load와 차이점)
  • CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
  • 하드웨어적인 지원이 필요 (MMU)

1. cpu는 논리적인 주소를 본다.

      cpu가 메모리 접근을 하려면 논리적인 주소를 물리적인 주소로 변환해야 한다. 

2. 메모리 주소를 변환하는 일은 운영체제가 하는 일이 아니다!! 하드웨어(MMU)가 한다.

---

MMU

• MMU(Memory-Mangement Unit)
  • logical address를 physical address로 매핑해 주는 하드웨어 장치
• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register의 값을 더함
• user program
  • logical address만 다룬다.
  • 실제 physical address를 볼 수 없으며 알 필요도 없다. 

레지스터 2개만 있으면 되는 모델 (Dynamic Relocation)

 

Relocation register(base register) 

• 접근할 수 있는 물리적 메모리 주소의 최소값
• 346번지에 14000을 더해서 실제 물리 메모리 주소를 찾는다.

Limit register

• 논리적 주소의 범위
• cpu가 logical address를 주면 limit register보다 작은지 확인한다. (할당된 영역이 넘어서는지 확인)

 

용어 정리

 

• Dynamic Loading (동적 로딩)
  • 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 그때 그때마다 메모리에 load하는 것
  • memory utilization의 향상
    • 좋은 프로그램일수록 방어적 코드를 사용(오류 처리 루틴)
    • 실행되는 부분만을 사용하면 메모리를 효율적으로 사용
  • 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능)
  • Loading : 메모리를 올리는 것
• Overlays
  • 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올린다.
  • 프로세스의 크기가 메모리보다 클 때 유용하다
  • 운영체제의 지원없이 사용자에 의해 구현
  • 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
    • "Manual Overlay"
    • 프로그래밍이 매우 복잡
• Swapping
  • 프로세스를 일시적으로 메모리에서 backing store(디스크)로 쫓아내는 것

• Backing Store(=swap area)
  • 디스크: 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in / Swap out 
  • 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정 (suspended 상태 = 디스크에 저장되어 있는 상태 = cpu에서 실행될 수 없는 상태)
  • priority-based CPU scheduling algorithm
    • priority가 낮은 프로세스를 swapped out 시킨다.
    • priority가 높은 프로세스를 메모리에 올려 놓는다. 
  • Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야한다.
    • 원래 위치에 복원되어야 하기 때문에 비효율적
    • 고정된 메모리 영역이 이미 다른 프로세스가 사용하고 있으면 swap in이 불가능하거나 기다려야 한다.
  • Execution time binding(Run time binding)에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있으니까 편하다.
    • 실행 시점에 프로세스의 가상 주소가 동적으로 물리 주소로 매핑되기 때문에 효율적이며 유연하다.
  • swap time은 대부분 transfer time (swap되는 양에 비례하는 시간)이다. 

현재는 Swap in / Swap out 은 통째로 쫓겨나는 걸 설명하고 있다. 하지만 현대 메모리 관리는 일부만 쪼개서 메모리에 올라간다. 이 또한 swap in / swap out이라 표현하기도 한다. 

 

•  Dynamic Linking
  • Linking(라이브러리를 연결하는 것)을 실행 시간(execution time)까지 미루는 기법
  • Static linking (static library로 구현)
    • 애초에 컴파일 할 때부터 라이브러리를 포함하고 있는다. 
    • 라이브러리가 프로그램의 실행 파일 코드에 포함된다.
    • 실행 파일의 크기가 커짐
    • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비(eg.printf 함수의 라이브러리 코드)
  • Dynamic linking (shared library로 구현) 
    • 라이브러리가 실행시 연결(link)됨 (컴파일 때 미포함인데 필요할 때 파일을 열어 실행(라이브러리의 위치 정보만 저장)
    • 확장자 : `.so`  `.dll`  
    • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
    • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어온다.
    • 운영체제의 도움이 필요하다. 

---

Allocation of physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용한다.
  • OS 영역 : interrupt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역

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

 

Contiguous allocation (연속 할당) => 현대에서는 잘 안쓰임

• 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
• Fixed partition allocation (고정 분할 방식)
  • 고정된 크기 안에 넣을 수 있으면 넣는 방식
• Variable partition allocation (가변 분할 방식)
  • 차례대로 메모리를 채우면서 넣는 방식

• 연속 할당을 사용하면 외부 단편화, 내부 단편화가 생긴다. 
• compaction : 외부 단편화 문제를 해결하는 방법
  • 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
  • 비용이 매우 많이 드는 방법, 최소한의 메모리 이동으로 compaction하는 방법(매우 복잡)
  • compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행

Noncontiguous allocation (불연속 할당)

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

Paging (불연속 할당 기법)

Process의 virtual memory의 내용을 page 단위로 noncontiguous(불연속적)하게 저장하고 동일한 사이즈의 page 단위로 나눈다. 일부는 backing storage(디스크)에, 일부는 physical memory(렘)에 저장한다.

• physical memory를 동일한 크기의 frame(4KB)으로 나눈다.
• logical memory를 동일 크기의 page로 나눈다(frame과 같은 크기)
• 모든 가용 frame들을 관리
• page table(배열)을 사용하여 logical address를 physical address로 변환
• 외부단편화(External fragmentation) 발생 안함
  • 일정한 크기(4KB)만큼 고정 해놓고 사용하기 때문
• 내부단편화(Internal fragmentation) 발생 가능

 

 

위에 그림 설명

• P는 page 번호
  • p->f : page번호에서 frame 번호로 바뀐다.
• d는 page offset (page 내에서 얼만큼 떨어져 있는 거리)
  • 얼마만큼 떨어져 있는가를 나타내는 d는 변하지 않음

 

🤔CPU가 32bit 주소 체계를 사용한다면 한 번에 최대 얼마만큼의 메모리 주소를 나타낼 수 있을까?

• 렘에서 주소는 1개당 1byte(8bit) 사용한다. 
• cpu 주소체계가 1bit면 0번지, 1번지 주소를 나타낼 수 있다. 2bit면 0,1,2,3번지의 주소를 나타낼 수 있다...
• 32bit 주소 체계를 사용한다면 32bit로 나타낼 수 있는 주소의 개수는 2의 32승인 4GB이다.
  • 2의 10승이 K(킬로), 2의 20승이 M(메가), 2의 30승이 G(기가)
  • 32bit 주소 체계 사용 시 프로그램이 가질 수 있는 최대 메모리 크기는 4GB이다. 

🤔그럼 32bit 주소 체계 사용 시 페이지 개수는??

• 4GB 를 페이지 크기인 4KB로 나누면 된다. = 1M (백만개)
• 즉 백만개가 넘는 페이지 엔트리가 필요하다..

🤔32bit 체계 컴퓨터에서 페이지 번호(p)와 off_set은 몇 bit??

• 페이지 하나당 4KB(2^12)
• off_set은 12bit로 4KB를 왔다갔다 할 수 있고 나머지 20bit로 페이지 번호를 나타내면 된다.

 

Implementation of Page Table (페이지 테이블 구현)

• page table은 main memory에 상주
• Page-table base register(PTBR)는 page table의 시작 위치를 가리킨다. (위에 mmu에서 사용된 base 레지스터 생각)
• Page-table length register(PTLR)는 테이블 크기를 보관한다. (위에 mmu에서 사용된 limit 레지스터 생각)
• 모든 메모리 접근 연산에는 2번의 memory access가 필요하다.
  • 주소 변환을 위해 메모리에 있는 page table 접근 1번
  • 주소 변환 후 실제 data/instruction 접근 1번
  • 총 2번 필요!! 즉 메모리 속도가 2배 느려진 것
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup 하드웨어 캐시 사용
  • 캐시 메모리 : CPU와 메인 메모리 사이에 위치하여, 자주 접근하는 데이터를 임시 저장해 CPU가 더 빠르게 처리할 수 있도록 돕는 고속 메모리이다. 주소 변환을 위한 캐시 메모리와 데이터를 위한 캐시 메모리로 나뉘어진다.
  • TLB : 주소 변환을 빠르게 하기 위한 일종의 캐시 메모리

🤔 잠깐 정리) 어우 헷갈려!! 페이지(Page)랑 페이지 테이블(Page table)이랑 다른건가??! 다르다!!

• `페이지`라는 용어는 가상 메모리와 물리 메모리 모두에 사용되며, 일반적으로 동일한 크기의 메모리 블록을 의미한다.  (예: 4KB)
  • 가상 메모리 페이지에서는 프로그램이 사용하는 주소 공간을 여러 개의 페이지로 나누어 관리한다. 가상 페이지는 운영체제가 각 프로세스에 할당하는 메모리 블록이다. 
  • 물리 메모리의 페이지에서는 실제 데이터를 담고 있는 물리 메모리의 프레임을 의미한다. 실제로 프로그램 사용 시 필요한 데이터를 페이지 단위로 나누어 할당된 곳
• `페이지 테이블`은 가상 페이지 번호를 물리 메모리의 프레임 번호로 변환하는 매핑 정보만을 담고 있다.
• 즉 CPU가 요청한 논리 주소는 페이지 테이블을 통해 물리 주소로 변환되고, 해당 물리 frame의 off_set에서 데이터를 찾는다! 
• 둘 다 메모리에 있음~

🤔 그럼 페이지 번호(Page Number)랑 페이지 오프셋(Page offset)은 뭐하는 놈들인가?

• `페이지 번호(page number)` : 가상 주소를 여러 개의 고정된 크기(4KB)의 페이지로 나눈다. 각 페이지는 물리 메모리의 프레임(4KB)에 매핑된다. 
  • 페이지 번호는 어떤 가상 페이지가 어떤 물리메모리의 프레임에 매핑되는지 결정한다.
• `페이지 오프셋(page offset)` : 페이지 내에서 정확히 어느 위치에 데이터가 있는지 알려준다.

페이지 크기가 4KB인 경우, 페이지 번호는 페이지의 시작점(프레임)을 가리키고, 오프셋은 그 페이지 내에서 특정 데이터가 어디에 있는지를 가리킨다. 

 

예시) 가상 주소 : 0x12345 

• 가상 주소를 페이지 크기(4KB)로 나누면 
  • 페이지 번호: 0x12 (해당 페이지는 물리 메모리의 프레임에 매핑됨)
  • 오프셋: 0x345 (프레임 내에서 데이터가 있는 위치)
• CPU는 페이지 번호 0x12에 해당하는 프레임을 찾고, 그 프레임의 시작 주소에 오프셋 0x345만큼 더해서 정확한 물리 주소를 계산한다.

 

• page table의 정보의 일부를 TLB에 저장 후 빠른 주소 변환을 가능하게 한다. 
• TLB는 메모리보다 접근속도가 빠르다.
• CPU가 Logical address를 주면 page table에 가기 전 TLB를 먼저 확인한다. 있으면 메모리로 바로 접근해서 1번만 접근하면 된다. 없으면 페이지 테이블로! 
• 페이지 테이블은 p값이 주어지면 시작 지점에서 부터 +p만큼 해주면 해당 페이지 테이블의 주소로 접근가능해서 바로 주소변환이 가능했다.
  • 예를 들어 90만번째 페이지 엔트리의 주소로 접근하려 위에서 부터 90만번째 엔트리로 바로 가서 주소변환 하면된다.
• TLB는 일부만 담고 있다. 그래서 page번호와 frame 번호를 쌍으로 가지고 있다.
  • 주소 변환을 위해 p라는 주소 변환 정보가 있는지 없는지 TLB 안에 내용을 전부 서치해야한다. 오버헤드 발생!!
  • 이를 개선하기 위한 하드웨어가 associative register이다. 병렬로 한 번에 서칭이 가능하게 함. (아래그림 참고)(associative : 연관, 결합)

 

• 페이지 테이블은 프로세스마다 각각 있다.
  • 그래서 TLB는 context switch(문맥전환)마다 flush(remove old entries), 모든 엔트리가 다 지워져야 한다.
  • 즉 context switch 때마다 오버헤드가 크다.

 

• Hit의 반대는 miss
  • Hit ratio = α 이면 miss는 (1-α)
• hit는 메모리 한번만 참조하면 되고, miss는 두 번 참조해야 함

 

2단계 페이지 테이블 (Two-Level Page Table)

페이지 테이블의 장점 👍

• 메모리의 빈 위치가 있다면 page 단위로 아무곳이나 올려 사용해 메모리 이용도가 높다.
• 당장 필요한 페이지만 사용되기 때문에 메모리가 효율적으로 사용된다.

현재 페이지 테이블의 단점 👎  : 무조건 1M개 만큼 page table entry(4Byte)가 필요하고 페이지 테이블만을 위한 메모리 공간이 총 4MB가 사용된다.

• 32bit 주소 체계 기준으로는 page table entry가 백만개가 넘는다. entry 하나하나 당 frame을 담고 있는데 적어도 4byte 정도 된다. 프로세스당 페이지 테이블에 4MB(4byte * 1M개)이상의 메모리 공간이 필요하다. 이러한 테이블이 프로세스마다 각각 필요하다.
• 즉, 공간 낭비 발생!!

• • 32 bit address 사용시 : 2의32승 (4GB)의 주소 공간
    • page size가 4KB시 총 1M개의 page 개수 필요
      • 2의 32승(4GB) / 2의12승(4KB) = 2의 20승(1MB)
    • 각 page entry가 4byte 시 프로세스당 4MB의 page table이 필요하다
    • 그러나, 대부분의 프로그램은 4GB의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다.

 

🔨개선해보자!

• page table 자체를 page(4KB)로 구성
  • 페이지 테이블도 페이지 단위로 쪼개서 관리
• 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음)

 

• 기존 메모리 접근 2번에서 1번 더 추가됨. 최대 총 3번 메모리(렘)에 방문해야 한다.
• 시간상으로 손해지만 공간상으로 이득을 볼 수 있다. 
  • 그림을 봐보자!! 사용되지 않는 주소 공간을 outer-page table에서 NULL처리를 해주면 그림의 중간에 그려져 있는 page table이 생성되지 않는다. 공간 개이덕!
  • 다단계 페이지 테이블에서는 전체 페이지 테이블을 한 번에 로드하지 않고, 필요한 부분만 메모리에 로드하여 메모리 낭비를 줄인다.

 

 

 

공간이 낭비되는 이유 : 배열처럼 사용하기 위해 백만개의 엔트리가 나열되어 있어야 한다. 그래야 가상 주소에서 바로접근이 가능하기 때문, 하지만 상당부분 사용되지 않는 곳이 많다. 페이지 테이블에서 모두 만들어져야 한다.

 

안쪽 페이지의 크기는 4KB, 페이지 엔트리 크기는(4Byte) 총 개수는 1K개

 

2단계 페이징(Two-Level Paging) 예시

• logical address (32bit에서 4KB 페이지 사이즈) 구성
  • 20 bit는 페이지 번호(page number)
  • 12 bit는 페이지 오프셋(page offset) 
    • 페이지의 크기 4KB=2^12 ➡️ 12bit 필
• page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다 
  • 각 페이지(page) 크기 : 4KB, 각 page table entr : 4Byte
  • p1 : 10-bit 의 페이지 번호 (4MB / 4KB = 1K ➡️ 2^10 ➡️ 10 bit 필요)
    • 기존 페이지 테이블의 총 크기(4MB)를 페이지 크기(4KB)로 나눈다
    • 총 페이지 테이블의 페이지 개수 : 1K개 
  • p2 : 10-bit 의 페이지의 오프셋 (4KB / 4Byte = 1K ➡️ 2^10 ➡️ 10 bit 필요)
    • 페이지 크기(4KB)를 페이지 엔트리 크기만큼 나눈다. 
    • 페이지 안에 페이지 엔트리 개수 : 1K
• p1 페이지 넘버로 이동하기 전, outer-page table의 시작 위치는???
  • Page-table base register(PTBR)가 page table의 시작 위치를 가리킨다.

 

p1은 outer page table의 index 이고 p2는 outer page table의 page에서의 변위이다. 

 

 

• 위에서 2단계 페이지 테이블을 사용한 것처럼 다단계 페이지로 사용가능하다.
• 공간을 줄일 수 있다. 사용 안되는 곳은 null로 됨
• 하지만 시간이 오래걸린다. 
• 그런데 주소 공간의 상당부분이 사용되지 않는데 그래도 페이지 테이블의 엔트리가 백만개가 다 만들어져야 하는 문제가 있기때문에 다단계 페이지가 유효하다. TLB가 사용되는 페이지의 상당부분을 캐싱하고 있을 수도 있다. 4단계 페이지를 쓰더라도 TLB를 통해 주소변환을 되는 비율을 높일 수 있다. 
• TLB의 hit ratio가 98프로일 경우 128나노초만 소요된다.

 

 

vaild(`v`) : 메모리에 페이지가 할당 되어있을 때

invalid(`i`) : 메모리에 페이지가 할당 x ➡️ 디스크(swap area)에 있을 때 or 프로세스가 그 주소 부분을 사용하지 않는 경우

protection bit : read-only로 세팅시 write 금지

아래 내용은 그 외 page table... (pintos 구현할 때는 딱히 필요 없음)

 

Inverted page table (역방향 페이지 테이블)

장점 : 페이지 테이블 크기가 물리 메모리 크기에 비례 

단점 : 가상 주소를 물리 주소로 변환할 때, 가상 주소의 페이지 번호를 직접 인덱스로 사용하지 못한다. 그래서 매번 테이블을 전체 탐색해야 한다. 

단점 해결책으로 TLB에서 사용하는 associative memory를 사용한다. 하지만 연관 메모리는 비싸고 복잡하기에 한계가 있다.

• Inverted Page Table은 기존의 방식과 달리 각 프로세스마다 페이지 테이블을 두지 않고, 물리 메모리의 각 페이지 프레임마다 하나의 페이지 테이블 엔트리를 둔다. 
  • 메모리 공간을 줄이기 위해 고안된 테이블이다. 
  • physical address(물리 주소)를 보고 logical address(논리 주소)를 얻어내기 쉬움
• Inverted Page Table의 구조: 각 엔트리에는 해당 페이지가 어떤 프로세스의 가상 주소에 매핑되어 있는지에 대한 정보가 담긴다. 즉, 각 엔트리는 다음과 같은 정보를 포함
  • Process ID: 어떤 프로세스의 페이지인지 식별
  • 가상 페이지 번호: 해당 프로세스의 어느 가상 페이지가 이 물리 프레임에 매핑되었는지

 

1. CPU에서 가상 주소 생성: 가상 주소는 프로세스 ID(PID), 페이지 번호(p), 오프셋(d)로 구성됩니다.
2. Inverted Page Table 검색: PID와 페이지 번호(p)를 사용해 물리 메모리의 어느 프레임에 해당하는지 테이블에서 찾습니다.
3. 물리 주소 변환: 찾은 물리 프레임 번호(f)와 오프셋(d)를 더해 최종 물리 주소를 계산합니다.
4. 메모리 접근: 변환된 물리 주소로 가서 데이터를 가져옵니다.

Inverted Page Table은 시스템 전체에서 물리 메모리의 페이지별로 가상 주소 매핑을 관리

 

Shared page, segmentation table, segmentation with paging ... 등등은 pintos와 관련 없기에 나중에 다시보기로 하겠습니다..

 

 

출처 : http://www.kocw.net/home/search/kemView.do?kemId=1226304