본문 바로가기
2023-1/운영체제

Virtual Memory - Page Replacement

by 철없는민물장어 2023. 6. 3.
728x90
반응형

Virtual Memory

: 물리메모리와 논리메모리를 분리. 이들 주소가 1:1로 매치되지 않는다. 

가상 메모리는 현재 필요한 메모리 페이지만을 물리 메모리에 유지하고, 나머지는 디스크에 저장함으로써 메모리의 효율적인 사용을 가능하게 한다.

 

각 프로세스는 자신만의 가상 메모리 공간을 갖게 되어 다른 프로세스의 메모리 영역에 접근하지 못하게 된다.

 

가상 메모리는 요구 페이징(Demand Paging), 요구 세그멘테이션(Demand segmentation)이라는 두 가지 방식으로 구현될 수 있다.

 

가상 메모리의 3가지 주요 특징

  • 프로그램 사이즈와 메모리 사이즈는 연관 없다. (프로그램 사이즈가 메모리보다 커도 됨). (디스크를 메모리의 일부처럼 사용하게하는 스왑핑 기능을 적용했기 때문)
  • 한 프로세스는 전체 메모리를 자기 혼자 사용한다고 생각
  • 프로그램의 일부분만 메모리에 로드될 수 있다(요구 페이징).

요구 페이징(Demand Paging)

프로그램의 모든 부분을 처음부터 메모리에 로드하지 않고, 실제로 필요한 페이지만 메모리에 로드하는 방식이다.

이를 통해 메모리의 효율적인 사용을 도모하고, 프로그램 실행에 필요한 초기 로딩 시간을 줄일 수 있다.

이 방식은 페이지 폴트가 발생할 수 있고, 페이지 폴트 발생시 필요한 페이지를 메모리에서 찾아 로드해야한다.

 

장점: 

적은 I/O 

적은 메모리 사용

빠른 응답

많은 유저

많은 동시 프로그램 실행

 

 

Valid-Invalid Bit

페이지 테이블 엔트리에, valid-invalid 비트가 추가됨. 1일 때 메모리에 있고, 0일 때 메모리에 없다는 의미.

초기에는 모든 엔트리에서 valid-invalid 비트는 0으로 초기화된다.

해당 비트가 0인 엔트리에 접근하면 페이지 폴트가 발생한다.

 

Page fault

프로그램 처음 실행될 때, 해당 페이지는 메모리에 로드되지 않았으므로 첫 번째 참조는 페이지 폴트가 발생한다.

valid bit=0인 경우 페이지 폴트가 발생한다.

폴트 발생시 빈 프레임을 가져와야 하고, 빈 프레임이 없으면 스왑해야한다.

 

요구 페이징의 성능

Page fault Rate가 0<p<1.0일 때

EAT = (1-p)*메모리 접근 시간 + p * 페이지 폴트 서비스 타임

 

Page Replacement

1. 페이지 폴트시 디스크에서 페이지를 찾음

2. free frame을 찾음

- 있으면 그것을 사용

- 없으면 교체를 진행. 알고리즘에 따라 희생프레임을 선택

3. 할당하고 읽음.page table과 frame table을 업데이트함.

4. 프로세스가 중단된 지점부터 재시작

 

(참고) dirty bit를 페이지 교체 오버헤드를 줄이기 위해 사용하기도 함.

수정된 페이지는 디스크에 written back해야하는데, 수정되지 않은 페이지는 이것이 필요없기 때문에

수정되지 않은 페이지를 교체하는것이 좋기 때문이다.

 

페이지 교체 정책은 페이지폴트 비율이 낮은 정책이 좋다.

또한 프레임 수가 많으면 page fault가 적게 일어나 컴퓨팅이 빠르다.

 

페이지 교체 정책들

  • FIFO
  • Optimal
  • LRU(Least Recently Used)
  • LRU Approximation Algorithms
  • Far Page Replacement
  • LFU/MFU

FIFO

 

Optimal - 가장 최적의 성능을 낼 수 있다. 교체할 페이지를 선택할 때, 가장 나중에 참조가 일어날 페이지를 교체하면 된다. 이 방법은 미래를 예측해야 하기 때문에, 실제로는 사용할 수 없고, 시뮬레이션으로 구현하여, 다른 교체정책과의 성능 비교책으로 사용된다.

 

LRU - Least Recently Used. 가장 오래전에 사용된 것을 교체

.

..


Allocation of Frames

 

초기 프레임 할당: 각 프로세스는 프로그램을 시작하기 위한 최소한의 페이지들이 필요하다.

우리는 초기 폴트를 줄이기 위해, 처음 프로세스 할당될 때 초기프레임을 할당할 수 있다.

 

두가지 방법:

-fixed allocation: 각 프로세스에 고정된 수의 프레임 할당

-priority allocation: 우선순위별로 프레임 수 할당

 

fixed allocation:

-Equal allocation: 모든 프로세스에 고정된 수의 프레임 할당

-Proportional allocation: 프로세스의 크기에 비례하여 크기에 고정적인 할당

 

priority allocation:

우선순위가 낮으면 적은 프레임을 할당받음

 


Global vs Local Page Replacement

 

페이지 폴트 발생시 페이지 교체 대상을 어디서 찾을건지?

-자신에 할당된 페이지들에서만 찾기: Local

-전체 중에서 찾기: Global

 

로컬 교체는 다른 프로세스에 영향을 주지 않지만, 전체 메모리 사용에 대한 유연성이 떨어진다.

반면, 글로벌 교체는 전체 메모리 사용에 대한 유연성이 높지만, 한 프로세스가 많은 페이지를 사용하면 다른 프로세스에게 영향을 줄 수 있다.

 


Thrasing

 

프로세스가 충분한 페이지를 가지고 있지 않으면, 페이지 폴트 비율이 굉장히 높아진다.

그럼, CPU utilization이 낮아지고, 운영체제는 멀티프로그래밍 디그리를 올리려고 한다. 그럼 다른 프로세스가 추가되어 더 상황이 악화된다.

 

가상메모리를 사용하여 모든 페이지를 메모리에 올리지 않다 보니 스레싱이 생김..

가상메모리는 요구페이징때문에 쓰는데.

요구 페이징은 왜 동작하나?

locality가 있기 때문에.(지역성을 띠므로 일부분만 올려놔도 실행이 됨)

 

각 프로세스의 지역성의 크기의 합이 > 필요한 메모리 사이즈보다 크면 스레싱이 발생

 

Working-Set Model

워킹셋: 프로세스가 필요로 하는 페이지프레임 수

워킹셋 윈도우: 델타값으로 표현... 이 윈도우만큼의 참조 내에 어떤 페이지가 사용됐는지.. set으로 표현한게 워킹셋

워킹셋의 요소가 적을수록 로컬리티가 높은것.

 

델타가 너무 작으면: 로컬리티를 커버하기 힘듦

델타가 너무 크면: 여러 로컬리티를 커버해버림

델타가 무한대가 되면: 전체 프로그램을 커버해버림

 

워킹셋들의 합 D = 모든 프로세스에서 요구하는 페이지들의 셋의 합

m = 이용가능한 프레임의 수

이 때, D>m이면 스레싱.

 

Page Fault Frequency Scheme

스레싱 솔루션 다른방법.

page fault rate가 일정 범위 내에 있도록 정해놓자.

 

폴트비율이 너무 높으면, 프로세스에 프레임을 더 할당해주고

폴트비율이 너무 낮으면 프레임을 빼서 다른 프로세스에 준다.

 


Benefits of Virtual memory

 

-Page Sharing

-Copy on Write: 페이지 쉐어링시 쓰기연산이 일어나는 경우에 카피하여 다른 페이지로 구분해 사용

-Memory-mapped files(MMF): 파일을 메모리에 매핑하여 사용. I/O read하는 (fread같은것)것을 파일을 메모리접근하듯이 사용가능. 프로그램 실행시 프로그램파일을 읽어오는 경우에 사용. mmap()시스템을 이용해 파일을 메모리에 매핑가능

페이지 접근처럼 파일접근가능

 


커널 메모리 할당

 

buddy system

slab allocation

 

메모리의 OS영역.. 커널주소공간은 경우에따라 페이지보다 큰 연속된 영역이 필요할수도, 페이지보다 작은 사이즈 영역만 필요할수도 있다.

 

buddy system:

2의 제곱인 블록들로 메모리를 관리하여 연속적인 페이지를 할당

 

slab allocation:

작은 사이즈의 메모리 공간이 필요할 때 한 페이지를 할당하면 내부 단편화가 발생한다.

연속된 페이지 몇 개를 slab으로 모으고, slab에서 페이지를 더 잘게 나누어 필요한 부분만큼만 cache에 모아 사용함.

캐시 내에서는 할당 사이즈가 다를 수 있다.


Other Issues

 

Pre-paging

Page size

TLB reach

Program structure

I/O interlock

 

Pre-paging: 프로세스 시작시 폴트를 줄이기 위해서, 사용이 예측되는 페이지 몇 개를 미리 가지고 옴.

(참고: pure demand paging system: 실제 요구하기 전에는 프리페이징하지 않음)

예측한 페이지가 사용되지 않으면 I/O자원이 낭비된다. 

s개를 프리페이징 했는데 a%만큼 사용한 경우, s*a만큼은 폴트 세이브, s*(1-a)만큼은 필요없는 페이지.

 

Page size: 페이지 크기가 크면 내부단편화가 큼. 페이지 크기가 작으면 페이지테이블 크기가 커짐.(이 페이지크기를 줄이려고 계층적, 해시, 역테이블 등 기법 사용)

I/O overhead - 페이지가 너무 크면.. 한번에 I/O가 불가능해서 두번 I/O하면 오버헤드가 커짐

locality-페이지가 커서 한 페이지 내에 로컬리티가 두개이상 있으면.. 좋진 않을듯

 

TLB reach: TLB가 커버하는 범위. = TLB 엔트리 수 * 페이지 사이즈 

페이지 사이즈를 늘리면 더 많은 범위를 TLB가 커버할 수 있음. (하지만 페이지 사이즈가 늘어나면 위에서 언급한 단점들이..)

 

Program Structure:

메모리에 2차원배열..등 올라갈 때, row-major-order인 경우 row별로 묶어 저장된다. 따라서.. 이 배열을 순회하는 반복문 코드에 따라 메모리에 접근하는 방식이 달라 페이지 폴트가 더 많이 발생하거나 적게 발생할 수 있다.

 

I/O interlock:

버퍼링이 일어날 때 이 버퍼는 메모리에 있음. 참조하려고 메모리에 열심히 올려놨는데, 이 페이지가 교체대상이 될 수 있음. 따라서 이 버퍼링 페이지는 교체대상이 되지 않도록 락을 걸어야함;. 이것이 I/O interlock

또는 파일copy시 등.. 

paged memory: 페이지할 수 있는 메모리?/ 페이지 스왑 가능

non paged memory: I/O 인터락이 되어있는 부분은 non paged memory로 교체정책 대상 제외(페이지 스왑 불가)

728x90
반응형

'2023-1 > 운영체제' 카테고리의 다른 글

File System  (2) 2023.06.14
File system and storage management  (0) 2023.06.10
Paging  (0) 2023.05.15
Memory Management and Virtual Memory  (0) 2023.05.06
Thread  (0) 2023.04.18

댓글