08 Virtual Memory (2)

4. Paging

Support Nedded for Virtual Memory

- Hardwere(MMU) 장치 필요

- Operation system는 pages가 main memory와 disk 사이를 이동해야한다.

- OS는 page table도 관리해야한다. 

 

Paging

1) Modify bit in page Table

페이지가 메인 메모리로 마지막으로 로드된 이후 변경되었는지 여부를 나타내려면 수정 비트가 필요
변경이 없는 경우, 페이지를 스왑 아웃해야 할 때 디스크에 쓸 필요가 없음

2) two-level scheme for 32-bit Address

- 전체 page table이 주 메모리를 너무 많이 차지할 수 있음
- page table 은 가상 메모리에도 저장
- 프로세스가 실행 중일 때 페이지 테이블의 일부는 기본 메모리에 있음

 

 

 

 

3) Inverted page table

-  PowerPC, UltraSPARC 및 IA-64 아키텍처에 사용 (64bit)

- 메인메모리 전체 당 하나의 page table ( 메인메모리에 있는 프레임 크기만한 page table 설정 )
- 가상 주소의 페이지 번호 부분이 해시 값으로 매핑됨

만약 ID 값이 일치하지 않을 경우 chain에 연결해서 ID 비교 후 내 프로그램와 같은 ID일 때 페이지 값 가져옴
- 해시 값 반전된 페이지 테이블을 가리킴
- 과정 수에 관계 없이 이야기에는 고정 비율의 실제 기억이 필요

 

Translation Lookaside Buffer (TLB 실행 과정)

1) 각 가상 메모리 참조로 인해 두 번의 물리적 메모리 액세스가 발생할 수 있음
- 페이지 테이블을 가져온다 -> 데이터를 가져온다

- 비효율적
2) 이 문제를 해결하기 위해 페이지 테이블 항목에 대해 고속 캐시(TLB)가 설정
- TLB에는 가장 최근에 사용된 페이지 테이블 항목이 포함되어 있습니다.

3) 전체 실행 순서

① 가상 주소가 지정되면 프로세서가 TLB를 검사 -> 있으면 즉시 실제 주소 생성

② TLB miss (가장 주소에 해당 TLB 없음)

 : page table 참조 -> 페이지 테이블 참조 -> TLB 갱신 (새 페이지 항목을 포함하도록 TLB가 업데이트)

 : 페이지 번호를 사용하여 프로세스 페이지 테이블을 인덱싱
③ page fault (페이지가 메인 메모리에 없음)

하드디스크에 다음 페이지 값 -> main memory 빈 프레임에 page 값 옮기기

 

Page Size

1) 장단점

- 페이지 크기가 작을 수록 내부 조각율(사용하지않는 메모리공간)이 작음

- 페이지 테이블 크기 증가하면 메모리 소비가 커짐 (유일한 단점)

- 페이지 크기가 작을 수록 프로세스의 전체 페이수는 증가

- 프로세스당 페이지 수가 증가하면 페이지 테이블 크기 증가

2) 크기 변화에 따른 효과

- 한 프로세스에게 주어진 메모리 양은 고정되었다고 가정

 : 페이지 크기가 작아지면 프레임 크기 작아지고 프레임 수 증가

- 페이지 크기가 작을수록 프로세스당 많은 페이지가 메모리에 상주 가능 (명령어, 변수들이 소속된 페이지들이 상주)

- 시간이 흐를수록 프로세스가 최근에 참고한 페이지들이 거의 메모리에 상주 가능함 -> page fault율 낮음

- 페이지 크기가 커질수록 메모리에 상주할 수 있는 프로세스의 페이지 수가 줄어 듦. 최근에 참조한 페이지들이 모두 메모리에 못 들어갈 수 있음 -> page fault율 증가

시험에 잘 나오는 그래프 

Working set size

: 어떤 프로그램을 작성할 때 가장 합리적인 메모리의 양 (프레임의 수)

 

 

 

 

 

 

 

 

 

 

 

 

 

Thrashing

- 실행중인 프로세스가 많아질수록 CPU는 할 일이 많아서 이용률 높아짐

- 프로세스의 수가 증가할 수록 한 프로세스에게 주어지는 메모리의 frame의 수는 줄어듦 -> 점점 줄어들수록 page fatult 수는 증가함

- CPU는 page fault를 처리하느라 프로세스를 실행시키는 시간보다 page fault를 처리하는데 더 많은 시간을 소비함 (CPU : 일은 하지만 비 생산적임)

 

5. Policy

Fetch Policy

: 페이지를 언제 메모리에 가져오는가?

1) Demand paging : 필요(page fault)로 할 때 가져옴

2) Prepaging : 미리 예측하여서 가져옴 

- page fault가 발생하지 않음

- 현실적으로 구현하기 어려움

 

Placement Policy

: 디스크에서 읽어 온 페이지를 메모리 어디에 둘 것인가?

(paging system에서는 빈 프레임 아무 곳에나 두면 되므로 중요하지 않음)

1) important in a segmentation system

- 동적 메모리 할당이 이루어져야함

- Dynamic partitioning, Buddy system 참조

 

Replacement Policy

: 디스크에서 읽어 온 페이지를 메모리에 로드하기 전에 이미 메모리가 가득 찼으면, 일부를 디스크로 빼내 빈 공간을 만들어야하는데 어떤 페이지를 빼낼 것인가?

1) Frame Locking (디스크로 swap out이 되지 않도록 중요한 페이지들은 프레임에 고정시켜준다.)

- 만약 프레임을 고정시킬 경우 이것은 디스크로 빠져나가지 않고 항상 메인 메모리에 상주하게 된다. 즉, 교체되지 않는다.

- 운영체제의 커널 코드, 커널들이 관리하는 파일, 프로세스, 인터넷 소켓 구조체 등은 frame locking을 걸어둔다.

- I/O buffers (중간에 임시로 데이터를 받아놓는 장소) 또한 locking

- locking 되어 있다던 정보들은  page table에 저장되어 있다. 

2) Basic Replacement Algorithms (교체 되어질 페이지를 찾는 알고리즘)

① Optimal policy : 향후 가장 오랫동안 참조되지 않을 페이지를 선택

- 성능이 가장 좋은 알고리즘

- 미리 예측하는 것이 불가능하기 때문에 실현 불가능한 알고리즘

② Least Recently Used (LRU) : 과거 가장 오랫동안 참조되지 않은 페이지를 선택 (미래에도 참조될 가능성이 낮기 때문)

- 매 페이지 정보에 시간 정보를 저장하고 사용할 때마다 정보를 빼와야함

- 성능도 좋고 구현도 가능하다 (여기서 성능이 좋다는 것은 page fualt가 덜 발생하는 것을 의미)

-  overhead가 심하다. (메모리 많이 사용, 시간 오래걸림)

③ First-in, first-out (FIFO) : 메모리에 가장 오랫동안 있는 페이지 선택

- 구현은 쉽지만 성능은 가장 좋지 않음

④ clock policy (시험에서 use bit와 next frame pointer 정확히 표시)

- 구현하기 괜찮고 성능도 괜찮다. 많이 사용하는 알고리즘

- 별도의 use bit를 사용 (page table의 엔트리에 있음)

- 처음 메모리에 로드될 때 use bit를 1로 설정

- 페이지가 reference(참조) 될 때마다 use bit를 1로 설정

- 페이지가 교체 때 next frame pointer부터 시작하여 처음으로 use bit가 0인 페이지를 찾아 교체

- 메모리 끝까지 0인 페이지가 없으면 처음부터 계속 찾음

- next frame pointer를 교체된 페이지의 그 다음 프레임으로 설정 

- use bit가 0인 페이지를 찾아 갈 때 중간의 user bit가 1인 페이지는 0으로 변경

⑤ Enhanced Clock Poliy

- clock poliy에서 성능을 향상시킨 알고리즘

- 별도의 use bit (u)와 modify bit (m)를 사용

- 페이지가 읽혀질 때 페이지에 u=1, 수정이 발생했을 때 u=m=1

- 4가지 케이스

(u=0,m=0) : 가장 우선적으로 교체

(u=0,m=1) : 2번째로 교체 (탐색할 때 u=1인것은 0으로 바꾸어주면서 탐색)

(u=1,m=0)  

(u=1,m=1) 

 

Cleaning Policy

: 수정된 페이지가 있을 경우 언제 하드디스크에 백업을 받을 것인가?

1) Demand cleaning (필요할 때)

- 일반적으로 사용

- 페이지 교체 작업을 할 수정되어 있는 페이지일 경우

- 한 번의 page fault가 일어날 때 두번의 페이지 변경이 필요 : 디스크 백업, 그다음 페이지 가져오기

2) Precleaning (주기적으로 백업받아 놓기)

- 계속 백업을 하여야 함

- 언제까지 백업을 해야하는지 미지수

3) Best approach uses page buffering (생략)

 

Load Control

: 메인 메모리에 프로그램을 몇 개 넣는 것이 가장 적합한가? -> 이러한 문제를 제어하는 알고리즘이 없음

- 프로그램을 많이 돌리면 : thrashing

- 프로그램을 적게 돌리면 : swapping 하느라 시간 낭비