[운영체제] Day09. Memory Management II

Paging 기법

Process의 Virtual Memory를 동일한 사이즈의 Page로 분할

• Virtual Memory 내용이 page 단위로 불연속(Non-contiguous)하게 저장
• 일부는 Backing Storage, 일부는 Physical Memory
• 주소 변환을 위해서 Page Table 이용.
  

Page Table

• 분할된 Logical memory의 Page와 Physical Memory의 Page Frame을 Page Table로 매핑.
• Paging 시 table에 의해 locical address는 변환되나 (p->f) 내부 상대적 위치를 나타내는 offset(d)은 변하지 않음.
• Page Table은 용량이 거대함 (각 프로세스마다 존재. 프로세스 하나 당 많은 Page)
• 때문에 Page Table은 메모리에 저장.
• 따라서 모든 메모리 접근 연산에는 메모리를 두 번 접근해야 한다.
• Page Table 접근 한 번(데이터 어딨는지 확인) + 실제 Physical 데이터 확인
• 기존의 MMU(Memory Management Unit)은 Table의 위치를 나타내는 PTBR(Page-Table base register)와 Table 크기를 나타내는 PTLR(Page-Table length register)로 구성.
• 메모리 두 번 접근으로 인한 속도 저하 -> 속도 향상을 위해서 TLB (Translation Look-aside Buffer) 사용, 일종의 주소 변환을 위한 Cache Memory.

TLB (Translation Look-aside Buffer)

메인 메모리와 CPU 사이에 존재하는 Cache Memory.

• 메인 메모리에 존재하는 Physical Address 접근하기 전에 먼저 TLB에서 frame # 체크.
• frame #가 TLB에 없으면 그때 Physical Memory로 접근해서 frame # 체크.
• 따라서 TLB를 전수 조사해야 하고, 시간이 오래걸릴 수 있다.
• TLB 시간 단축을 위해 병렬 탐색이 가능한 Associative Register 이용한다.
• page table은 프로세스마다 각각 존재한다. 프로세스마다 주소 변환 정보가 다르므로.
• 따라서 context switch 마다 flush 해서 TLB 내 주소 변환 정보를 초기화
  

EAT (Effective Access Time)

원하는 frame #를 얻기 위해 소요되는 시간의 기댓값.
Associative register lookup time = ε (TLB 뒤지는 시간)
memory cycle time = 1 (메모리 접근 소요 시간)
Hit ratio = α (TLB에서 찾아지는 비율)
EAT = (1 + ε)α + (2 + ε)(1 - α) = 2 + ε - α
즉, 찾으면 (1 + ε) 만큼의 시간 (메모리 한 번 접근)
못 찾으면 (2 + ε)의 시간이 걸린다. (메모리 두 번 접근)
EAT는 각 시간에 확률을 곱한 기댓값이다.

Two-Level Page Table

• 현대의 컴퓨터는 Address space 공간이 매우 큰 프로그램 지원(32bit, 64bit ...)

• 32bit memory address 사용 시 2^32 byte (4GB)

• page size가 4K 면, page Table 은 1M 개 만큼이 필요하다.

• 각 page entry가 4B시, 프로세스 당 4M 의 page Table 필요하다.

• 프로그램은 대개 4GB 주소 공간 중 일부만 사용. page table 공간 낭비.

• Two-Level Page Table

  Page table을 Page로 구성.

• Logical Address (32bit machine, 4K page size) 구성
  page number(20 bit), page offset(12 bit)

• page number의 구성
  page number(10 bit), page offset(10 bit)

  32 bit 할당 방법

  inner Page size는 4KB : 12 bit 필요
  inner Page Table은 4KB개. 각 entrys는 4 byte. 1K (10 bit 필요)
  outer Page Table = 32 - 12 - 10 = 10 bit

  시간도, 공간도 손해. 근데 왜 씀 ?

  • 주소 변환 2회 필요, 메모리 공간도 더 차지함.
  • 기존 1단계 Paging 에서는 Logical Memory 만큼 Page Table이 생성되어야 했음. (중간에 빈 부분이 있더라도)
  • 이는 table이므로 index 통해서 접근해야 하기 때문에.
  • 하지만 2단계 Paging 에서는 사용하지 않는 주소 공간에 대한 outer page Table 엔트리 값 Null
  • 대응하는 inner page Table 없음.
  • 실제 할당하는 영역에 대해서만 Memory 할당 가능.

MultiLevel Paging & Performance

• Address Space 더 커지면 다단계 페이지 테이블 필요
• 각 단계 페이지 테이블이 메모리에 존재하므로 주소 변환에 더 많은 메모리 접근 필요
• TLB 통해서 메모리 접근 시간을 줄일 수 있음.
• 4단계 페이지 테이블 사용 시에도 TLB를 이용하면 주소 변환에 큰 시간이 들지 않음.

memory protection

page table의 각 entry 마다 아래의 bit을 둔다.

• Protection bit : page에 대한 접근 권한 (read, write, read-only)
• valid/invalid bit : 해당 frame에 유효한 내용이 있는지 여부

Inverted Page Table

Page Table 순서를 역방향으로 뒤집어 놓은 것.

• Page Table은 공간에 대한 Overhead가 몹시 크다.
• 각 프로세스마다 Table이 존재하는 것이 아니라, 시스템 안에 하나로 존재함 (system-wide).
• Page Table 칸 수 : 물리적 메모리의 page frame 수 만큼. (logical memory의 page entry 수 말고.)
• logical memory side부터 주소 변환 하는 것이 아니라, valid한 page frame (physical memory side) 에서부터 주소 변환
• 우리 목적에는 사실 맞지 않음 (목적 : l => p, 현실 : p => l)
• 원하는 p 가 나올 때까지 Page Table 뒤져봐야 함
• 공간은 절약, 시간 면에서 Overhead 발생
• page table 탐색 방식 :
  • p 일치 확인
  • pid 일치 확인 (어떤 process의 p인지. system wide하게 저장되어 있으므로)
• 전수조사 : associative registers 사용 (expensive).

Shared Table

• Share 가능한 코드(Re-entrant Code, Pure Code)는 하나만 올림
  • read-only로 하여 프로세스 간에 하나의 Code만 메모리 올림
  • Shared Code는 모든 프로세스의 logical address space에서 동일한 위치에 존재 (동일한 physical address는 당연)
• Private code, data는 Logical memory 어디에 얹어도 OK
• 다른 process에서 동일한 logical address로 접근할 수 있도록

Segmentation 기법

Process 구성 주소 공간을 의미 단위로 분해. (작게는 함수마다)
Logical address는 <segment-number, offset> 구성
Segment Table : base(physical 주소 시작 위치) + limit(segment length)

• STBR (Segment-table base register)

  • 물리적 메모리에서의 시작 위치 저장

• STLR (Segment-table length register)

  • 프로그램 사용하는 segment의 수 (의미 단위로 잘라서 segment 길이가 일정하지 않을 수 있다)

• segment 번호로 (STLR 값 비교) 유효성 검증

• 단점 : 크기가 불균일 > first fit, best fit 등을 이용해야. (Allocation Problem)

• 장점 :

  • Protection : 각 세그먼트 별로 Protection bit 존재
  • Sharing : 의미 단위이므로 공유와 보안에 있어 paging 보다 효과적

  Paging vs. Segmentation

  Paging
  page table의 존재. 공간의 낭비가 심함.
  기능별 분할이 아니라 동일한 크기로 분할.
  Segmentation
  기능별 분할 : 보안, 공유에 대해서는 Paging보다 유리
  동일한 segment 크기로 분할되지 않음. 가변 분할 방식과 동일한 문제 발생.
  메모리 중간마다 hole 발생. allocation 문제 발생. (best fit? first fit?)
  

Segmentation with Paging

Segment 하나를 Page로 구분해서 메모리에 작성 (Allocation 문제 해결 가능)
논리 주소 : Segment #, offset

• 공유나 보안의 경우는 Segment Level에서 처리 (두 가지 장점을 모두 취득 가능)
• 2 level Paging과 같이 Segmentation 후 Paging.