Main Memory - Paging & Segmentation

Paging

• Paging
  • 프로세스의 물리 주소 공간이 불연속적일 수 있음을 허용함
  • 물리 메모리는 프레임이라고 불리는 고정 된 사이즈의 블럭으로 나누어짐
  • 로지컬 메모리는 페이지라고 불리는 고정 된 사이즈의 블럭으로 나누어짐.
    • 페이지나 프레임의 사이즈는 2의 승수로 제공됨, 일반적으로 512B ~ 8KB
    • 프레임과 페이지가 용어상의 차이만 존재하지 같은 사이즈의 블락을 가짐
  • OS는 모든 프리 프레임의 정보를 유지하고 있음.
  • 페이지 매핑 테이블을 구성함.
• 
• 사용자의 관점
  • 사용자에게는 VAS(가상 주소 공간)를 통해서 0에서 N까지 연속적인 메모리 공간을 보여줌
  • 현실적으로 페이지는 물리 메모리상에 스케터 되어 있음
    • V2P의 페이지 매핑
    • 매핑은 프로그램에게 보여지지 않음.
  • Protection제공
    • VAS 바깥의 주소에 대해서는 접근 할 수 없기 때문에
• Translation address
  • Virtual address는 VPN과 Offset 두 개로 구분
  • VPN은 페이지 테이블의 인덱스
  • 페이지 테이블은 페이지 프레임 넘버를 결정(PFN)
• Pages table
  • OS에 의해서 관리됨
  • VPN to PFN
  • 하나의 페이지 테이블 엔트리(PTE)는 Virtual address 공간에서 페이지당 하나임.
  • 

• Paging Example
  • Virtual Address 32bit, Physical address 20 bit, Page size 4KB 라면 Offset은 12 bit이고 VPN은 20 bit이며 Page table entry는 2^20이 된다.
  • 
  • Protection
    • 메모리 Protection은 각각의 프레임 마다 protection 비트를 두어서 구현
    • Valid / Invalid
      • Valid라는 말은 VAS안에 있는 연관 페이지라는 말로 정상 접근이 가능하다는 것임
      • Invalid라는 말은 프로세스의 VAS안에 없는 페이지라는 말임.
    • Valid page에 대한 좀 더 풍부한(Finer) Protection이 가능 함.
      • 다시 말해 Read only, read-write, execute-only 등
• Page Table Entries(PTEs)
  • V, Valid bit는 PTE가 사용이 가능한지 아닌지를 나타내는 것임.
    • 매 시간 마다 Virtual address가 사용 중인지 아닌지를 나타내기 위해 사용.
  • R, Reference bit는 페이지가 액세스 되었는지 아닌지를 나타냄
    • 페이지를 읽거나 쓸 때 이 비트는 세팅됨
  • M, Modify bit는 페이지가 더티 인지 아닌지를 나타냄
    • 페이지 쓰기일 때 비트가 세팅 됨
  • P, Protection bit는 페이지 별로 어떠한 컨트롤 오퍼레이션이 가능 한지를 나타냄.
    • Read, Write, Execute등
  • 페이지 프레임 넘버(PFN) 는 Physical 페이지를 나타냄.
  • 
• 이점
  • 물리적 메모리 할당이 쉬움
    • 물리적 메모리는 프레임의 free리스트로 부터 할당 받으면 됨
    • 할당 받는 다는 것은 단지 free 리스트에서 제거 하는 것
  • External fragmentation이 없음
    • 페이지 단위로 할당 하기 때문에 External fragmentation이 생길 수 없음
  • 프로그램의 청크를 페이지 아웃 시키기 쉬움
    • 페이지가 고정된 사이즈를 가지고 있기 때문에 모든 청크는 같은 사이즈를 가짐.
    • 페이지 아웃된 페이지를 참조 하기 위해서는 Valid비트만 확인 하면 됨.
    • 페이지 사이즈는 디스크 블록 사이트의 멀티플로 선택함.
  • 불법적인 액세스로부터 페이지를 보호하기 쉬움
  • 페이지를 공유 하기 쉬움
• 단점
  • Internal fragmentation은 여전이 가능함.
    • 프로세스는 페이지의 배수 단위로 메모리를 사용 하지 않음.
    • Internal과 External의 차이는 사용 하지 않는 스토리지가 Allocated Region안에 있느냐 바깥에 있느냐의 차이임.
  • 메모리 레퍼런스 오버헤드
    • 어드레스 룩업당 2번의 메모리 레퍼런스가 생김. (페이지 테이블을 참조 하고 나서 메모리를 참조)
    • 하드웨어 TLB의 서포트를 받으면 이를 해결 할 수 있음
  • 페이지 테이블을 유지 하기 위한 메모리가 매우 클 수 있음.
    • PTE는 VAS만큼 필요 함
    • 4KB 사이즈의 페이지를 가지는 32비트 어드레스 공간이라면 2^20개의 PTE가 필요함
    • 하나의 PTE마다 4 바이트가 필요 하므로 페이지 테이블당 4MB가 필요함
    • OS가 일반적으로 프로세스 마다 페이지 테이블을 따로 가지고 있으므로 페이지 테이블을 유지 하기 위한 사이즈는 매우 큼
    • 이를 해결 하기 위해서는 멀티레벨 페이지 테이블, 인버티드(Inverted) 페이지 테이블등이 있을 수 있음.

Segmentation

• Segmentation은 로지컬리 관련된 데이터 유닛끼리 파티션 메모리를 구성하는 기술.
  • 예를 들면 코드 세그먼트, 스택, 힙과 같은 것들이 있다.
• 사용자의 메모리 뷰는 가변적 세그먼트의 컬렉션으로 제공된다. 그들 사이에 오더링에 대해서는 관심이 없다.
• 다른 세그먼트들은 서로 영향을 주지 않으면서 독립적으로 grow하거나 shrink한다.
• 가변 사이즈 파티션의 자연스러운 확장이다.
  • 가변 사이즈 파티션은 프로세스당 하나의 세그먼트를 할당 하는 것과 같음
  • 세그멘테이션은 프로세스당 많은 세그먼트를 할당하는 차이가 있음
• 하드웨어 서포트
  • 세그먼트 테이블이 존재
  • 세그먼트 테이블은 세그먼트 번호를 인덱스로 하여 세그먼트의 리밋과 베이스로 구성한 테이블
  • 
• 이점
  • Growing 또는 shrink하는 데이터 구조체를 핸들링 하는 것이 쉬움
  • 세그먼트를 Protect하는 것이 쉬움
    • 세그먼트 테이블의 각 엔트리 마다 valid 비트를 두고 있음
    • Protection bit들 역시 각 세그먼테 테이블 엔트리마다 존재 하기 때문에 관리가 쉬움
  • 세그먼트 공유가 쉬움
    • 같은 베이스와 리밋으로 번역하면 공유가 됨.
    • 코드와 데이터는 같은 세그먼트 레벨을 공유함.
    • 공유 라이브러러리가 좋은 예임.
• 단점
  • Cross-Segment address
    • 세그먼트는 프로세스간 공유를 위해 같은 세그먼트 넘버를 가리키는 포인터를 가질 필요가 있다.
    • 다른 경우는 간접 어드레싱만 사용한다.
  • Large segment tables
    • 메인 메모리에 유지하고 스피드를 위해서 하드웨어 캐시를 사용한다.
  • External fragmentation
    • 세그먼트가 다양한 길이를 가지기 때문에 메모리 할당은 다이나믹 스토리지 할당 문제를 가지게 된다.

Paging versus Segmentation

• 
  

Kind	Paging	Segmentation
Block size	Fixed(4KB ~ 64KB)	Variable
Linear address space	1	Many
Memory addressing	One-word (PN + offset)	Two-ward (SN + offset)
Replacement	Easy	Difficult
Fragmentation	Internal	External
Disk traffic	Efficient	Inefficient
Transparent to the programmers	Yes	No
Exceed the size of physical memory	Yes	Yes
Code, data 의 구분, 각각 보호 가능	No	Yes
Fluctuate size를 가진 테이블 수용	No	Yes(Shrink, Grow)
사용자 편의에 의한 코드 공유	No	Yes
발명된 이유	Physical memory 공간보다 더 큰 공간 제공	VAS에 관계 없이 코드 데이터 분리, 공유, 보호를 위해서 제작.

• 하이브리드 어프로치
  • 페이지된 세그먼트
    • 페이징이 가능한 세그먼트
    • 세그먼트는 다수의 페이지로 구성.
  • 페이지 사이즈의 배수
    • IA32에서는 4KB, 2MB그리고 4MB 페이지 사이즈가 지원됨
    • AXP 아키텍쳐에서는 8,16,32,64KB 지원
• 세그먼테이션과 페이징의 결합
  • 로지컬리 관련 있는 유닛들을 관리 할때는 세그먼트를 사용
    • 코드, 데이터, 힙, 스텍등.
    • 세그먼트는 다양한 사이즈 이지만 페이지 사이즈의 배수로 구성되는 큰 크기
  • 고정된 사이즈 청크로 세그먼트로 파티션하기 위해 페이지들을 사용
    • 세그먼트는 물리 메모리의 좀 더 쉽게 만듦
    • 세그먼트가 페이지어블 가능 하기 때문에 메모리에서 나갈 때 세그먼트가 아니라 페이지 단위로 이동 시킬 수 있음
    • External fragmentation이 없어짐
    • 세그먼트가 할당 된 경우에면 페이지 테이블 엔트리의 할당이 필요함.
      • MULTICS
      • 
      • IA32
      •