Paging

Paging

운영체제에서 메모리 관리를 위해 사용하는 기술 "페이징"

물리 메모리를 동일한 크기의 '페이지'로 분할하고, 각각의 프로세스를 이러한 페이지로 분할하여 메모리를 관리하는 방식이다.

(프로그램 한 조각은 page, 메모리의 한 칸은 frame이다)

 

페이징 시스템은 각 페이지가 메모리의 특정 위치에 연속적으로 위치하지 않는다. 대신 페이지 테이블이라는 데이터 구조를 사용하여 각 페이지의 현재 위치를 추적한다.

 

페이징시스템은... 

-외부 단편화가 없다.

-내부 단편화는 발생할 수 있으나 단편화의 양이 적다. (마지막 페이지에 한해 생기므로)

 

• Temporal Locality
• Spatial Locality

Temporal Locality(시간적 지역성)

: 특정 데이터 항목이 한 번 접근된 후, 가까운 미래에 다시 접근될 가능성이 높다. 

예를 들어 루프에서 반복적으로 사용되는 변수나 배열 요소, 재귀함수 등이 있다. 이러한 특성을 이용하여 최근에 사용된 데이터는 캐시에 보관되어 빠르게 접근할 수 있도록 한다.

 

Spatial Locality(공간적 지역성)

: 메모리의 특정 위치에 접근하면, 그 주변의 위치에 대한 접근이 곧 이어질 가능성이 높다.

예를 들어, 연속된 메모리 위치에 저장된 배열 요소에 순차적으로 액세스 하는 경우 등이 있다.

 

지역성을 이해하고 이를 활용하는 페이징 시스템은 메모리를 효율적으로 관리할 수 있게 한다.

지역성때문에 page시스템이 동작할 수 있다.

 

Page Table

가상 메모리를 물리 메모리에 매핑하는 데 사용되는 데이터 구조이다.

(몇 번째 page가 몇 번째 frame에 있는지?)

 

주소는 (p,d)로 표현한다.

p: page number: 몇번 째 페이지인지

d: page offset: : 페이지에서 어느 위치에 있는 데이터인지

 

32비트 아키텍처에서 주소 표현하기...

32비트 아키텍처에서 하나의 페이지가 4KB라고 한다면 P는 20비트, d는 12비트로 나타낼 수 있다.

 

4KB의 페이지 크기는 2^12 Byte이므로, 페이지 내에서 주소를 지정하기 위해서는 12개의 비트가 필요하다.(메모리 주소는 각 바이트에 대해 부여한다)

따라서 d는 12비트로 표현,

 

나머지 공간 20비트는 p를 표현하는데 사용된다.

(메모리가4GB라면.. 4KB짜리 페이지가 2^20개 생기므로 20비트로 딱맞게 표현할 수 있다)

 

Page Table은 메인 메모리(OS영역)에 있다.

 

CPU내부에 존재하는 PTBR(Page Table Base Register)에는 현재 실행중인 프로세스의 페이지 테이블이 시작하는 물리 주소가 있다. 

 

따라서, 데이터에 접근하기 위해서는 메모리를 두 번 접근해야 하는 문제가 있다.

이러한 단점을 보완하기 위해 TLB(Translation Lookaside Buffer)가 사용된다.

이는 하드웨어 캐시로, P.T의 일부를 TLB에 넣어놓고 사용한다.

(페이지테이블과 달리 page#,Frame# 쌍으로 저장)

(이 때.. 내가 필요한 정보가 TLB에 있으면 TLB히트라고 한다.

TLB 미스의 경우는 페이지 테이블을 참조해야 한다.)

 

평균 메모리접근시간 = (메인메모리 접근시간 * 2 + TLB접근시간 ) * TLB fault비율 + (메인메모리 접근시간 + TLB접근시간 )*TLB hit 비율

 

---

Memory Protection

 

• Memory access Operation protection(메모리 접근 연산 보호)
• Memory access Address protection(메모리 접근 주소 보호)

연산 보호: 각 page에 read-only or read-write or other information을 알려주는 보호 비트를 사용한다.

주소 보호: page table에서 valid 비트를 사용하여 주소접근을 보호함.(ex: 프로그램은 6페이지인데 페이지테이블은 8프레임까지 나타나는 경우 7,8 프레임은 프로그램이 있지 않으므로 접근하지 말아야 함)

---

Page table length register(PTLR)

 

Page table의 길이를 알 수 있다.

페이지테이블을 그냥 사용하면 대부분이 invalid이므로 가변적으로 사용하는것이 필요하고, 이를 위해 PTLR을 사용함

---

Shared Pages

 

여러 프로세스가 하나의 페이지를 공유하는 것.

이를 통해 여러 개의 프로세스가 같은 메모리 영역을 공유하고, 데이터의 복사나 메모리 할당에 따른 오버헤드를 줄일 수 있다.

 

공유 페이지로 사용하기 위해서는 재진입코드(Reentrant code) 여야 한다.

재진입코드는 코드가 진행되는 도중에 변경되지 않아야 한다.

 

.

예를 들어..

문서 편집기 프로그램을 동시에 2개 실행해서 두개의 프로세스가 있는 경우..

문서 편집기 프로그램 페이지는 공유하면 효율적이겠다.

 

---

Page Table Structure

 

페이지테이블이 많은 공간을 차지하는데, 어떻게 하면 효율적으로 P.T를 쓸 수 있는지..

• Hierarchical Page Tables
• Hashed Page Tables
• Inverted Page Tables

Hierarchical Page Tables(계층적 P.T)

: 페이지 테이블을 2단계나 3단계로 구성한다. 

분할된 계층적 구조를 통해 가상 주소의 일부만 로드하고 필요한 페이지 테이블만 메모리에 보유함으로써 메모리 사용량을 줄일 수 있다.(그러나 메모리를 여러번 접근해야 하므로 속도가 더 느려질 수 있다.)

(이 때 상위 계층의 정보를 TLB에 넣어두면 TLB히트율이 높아서  빠르게 접근할 수 있다. )

 

Hashed Page Tables

해시테이블을 이용한다.

해시테이블 크기가 작으면 충돌이 많이 발생한다.

예로, 만약 chain방법을 사용하면.. 체인이 길어져 검색시간이 증가할 수 있다.

 

Inverted Page Tables

역 페이지 테이블.

기존에는 프로세스당 하나의 페이지 테이블을 가졌었다.

이 방식은 하나의 글로벌 페이지테이블을 이용한다.

 

역 페이지 테이블을 사용하면 P.T 개수를 줄여 공간복잡도를 줄였지만

page table search time이 필요하다.

(하나의 page table을 여러 프로세스가 사용하니, 검색시 pid도 필요하고.. 전체 페이지를 순회하며 검색해야하는 문제가 있다)

---

Segmentation

지금까지 설명한 page시스템은, 하나의 프로세스를 같은 크기의 page로 쪼개었다.

segment 시스템에서는, 프로그램의 논리적인 단위를 반영하여, 성질별로 요소를 나누어 사용한다.

각각의 segment는 크기가 다 다를 수 있다.

그런데, segment의 크기는 일반적으로 page보다 훨씬 크다.. 따라서 연속할당과 같은 문제가 발생할 수 있다.

 

segmetation Architecture

논리 주소 표현 <segment #, offset> : 페이지 시스템과 유사.

 

segmentation table

page table에서는 1column으로, frame번호만 나타냈는데, segmentation은 각각의 세그먼트가 크기가 다르기때문에

2column으로, <base, limit>을 나타내야 한다.(또한, 페이지테이블은 사용하지 않는 주소 공간에 대해서도 페이지 테이블 항목이 존재하므로 공간 낭비가 심하다. 반면, 세그먼트 테이블은 사용하는 메모리 공간에 대해서만 정보를 가지고 있으므로 공간 효율이 좋다)

 

STBR(Segment Table Base Register)

세그먼트 테이블의 시작 주소를 가지고 있다. 이를 이용하여 세그먼트 테이블의 위치를 빠르게 찾아 접근할 수 있다.

 

STLR(Segment Table Length Register)

세그먼트 테이블의 길이(즉, 세그먼트의 수)를 저장한다. 운영체제는 이를 사용하여 세그먼트의 범위를 확인하고, 프로세스가 세그먼트 외부의 메모리를 접근하는 것을 막을 수 있다. 프로세스가 메모리에 접근을 시도할 때, 세그먼트 번호가 STLR에 저장된 세그먼트 테이블의 길이보다 크거나 같다면, 유효하지 않은 메모리 접근으로 간주할 수 있다.

(즉, 메모리 보호, 메모리 접근 오류를 방지한다)

---

페이지 시스템과 세그먼트 시스템을 결합한 방식

 

세그먼트 시스템은 사용자 관점에서의 메모리 관리에 유리하고, 프로그램의 논리적 구조에 따라 메모리를 나누는 것이 가능하다는 장점이 있다. 하지만, 세그먼트의 크기가 크기때문에 메모리 단편화 문제가 발생할 수 있다.

(외부 단편화, 큰 세그먼트 문제)

 

페이지 시스템은 운영체제 관점에서의 메모리 관리에 유리하며, 메모리 단편화를 해결할 수 있지만, 사용자 관점에서 메모리를 프로그램의 논리적 구조에 맞게 나누기가 힘들다는 단점이 있다.

(또한 내부단편화, 페이지테이블의 크기가 크다는 점도 있음. 많은 엔트리가 invalid)

 

이 두 시스템을 결합하여 논리적 메모리 구조를 유지하면서도 단편화 문제를 해결할 수 있다.

 

• Paged Segmentation System
• Segmented Paging System

Paged Segmentation System

: 세그먼트를 더 작은 page로 나누어 사용하는 방식. 

세그먼트 시스템은 외부 단편화가 발생한다는 문제가 있었다.또, 세그먼트가 너무 커서 메모리에 로드하기 힘들다는 문제가 있었다. 그래서, 각각의 세그먼트를 작은 페이지로 쪼개어 사용하고, 각각의 세그먼트에 page table을 만들어 관리한다.

(Segment, (P,d)) 형식으로 주소를 나타낼 수 있다.

이러한 방식은 외부 단편화를 없앨 수 있고, 메모리 할당 오버헤드를 해소할 수 있다.

세그먼트 테이블에서 해당 세그먼트를 찾고, 그 세그먼트 내에서 페이지 번호를 이용해 페이지 테이블을 찾아 해당 페이지를 찾음.

Segmented Paging System

: (페이징시스템 기반)

페이지 테이블이 여러개의 세그먼트로 나뉘어있다.페이지 번호를 사용해 페이지 테이블에서 해당 페이지를 찾고, 그 페이지가속한 세그먼트를 테이블에서 찾는다.?