벼락치기 - 운영체제 12

w12. 가상 메모리 관리 2

page replacement algorithm

thrashing. fram allocation

 

🚶‍♀️Page replacement algorithm

이론적 알고리즘

optimal(최적): 미래의 접근 패턴을 보고(예측) 대상 페이지를 선정하여 스왑으로 보냄. => 최고의 성능

 

간단한 알고리즘

Random(무작위): 랜덤으로 대상 페이지 선정해 스왑영역으로 보냄.

FIFO: 처음 메모리에 올라온 페이지를 스왑영역으로 보냄. 

 

최적 근접 알고리즘

LRU: 시간적으로 멀리 떨어진 페이지를 스왑영역으로 보냄

LFU: 사용빈도가 적은 페이지를 스왑영역으로 보냄

NUR: 최근에 사용한 적 없는 페이지를 스왑으로

FIFO변형: FIFO알고리즘 변형하여 성능 향상

 

*page fault rate : 일반적인 페이지 교체 알고리즘의 성능 평가기준

page fault rate=  page fault 횟수 / page 요구 횟수

(당연하지만 page fault는 낮을수록 좋음. 높으면 I/O 횟수 증가하여 비효율적)

---

👾 Random page replacement algorithm  - 간단한

swap으로 쫓아낼 대상 페이지를 무작위로 선정. 지역성은 전혀 고려하지 않음. 

=> 자주 사용하는 페이지가 선정될 수도 있기에 성능 좋지 않음.

 

👾 Optimal page replacement algorithm - 이론적

미래에 참조할 페이지를 미리 모두 안다고 가정함.

앞으로 가장 사용 가능성이 적은 페이지를 선정.

이상적인 방법이지만 실제로 구현 불가함. 

성공횟수가 5번보다 많을 수는 없음. (최고 성능의 기준을 알 수 있음.)

*optimal 알고리즘은 최소 page fault 수를 가짐.

 

👾  FIFO page replacement algorithm - 간단한

First In First Out

 

시간 상 가장 먼저 들어온 오래된 page를 선정

무조건 오래된 page를 대상 페이지로 선정하기 때문에 성능이 떨어짐.

 

👾  LRU page replacement algorithm - 최적근접

Least Resently Used

page에 접근한 "시간"을 기준으로 선정

 

최근에 언제 사용됐나? => 제일 오래된 것 Out

FIFO와의 차이점: 메모리에 처음 올라온 기준이 아니고, 가장 최근에 사용된 시간 기준임. 

 

👾  LFU page replacement algorithm - 최적근접

Least Ferquently Used

page가 사용된 "횟수"를 기준으로 선정

 

사용횟수 누가 적은가? => 사용횟수 적은 페이지 Out / 횟수 같을 시 임의 선정. 

단점: 가장 최근에 올라온 것이 미래에 자주 사용된다고 하더라도, 당장 횟수가 가장 적다면 out됨. 

---

 

🏃‍♂️ page table의 구성

page 번호 + flag bit + frame 번호(주소필드)

 

flag bit?

1. access bit (접근비트)

페이지가 메모리에 올라온 후의 사용 유무 알려줌 / 사용-1, 미사용-0

 

2. modified bit (변경비트, =reference bit 참조비트)

페이지가 메모리에 올라온 후의 데이터 변경 유무 알려줌. 

=> HDD에서 올라간 메모리가 변경됐다면 HDD와 비교했을 때 값이 다름. (변경사항 저장이 되기 전이라)

 

3. valid bit (유효비트)

페이지가 실제 메모리에 있는지 나타내줌

 

4. read bit (읽기비트), write bit (쓰기비트), execute bit (실행비트)

페이지에 대한 right(권한) bit. 

---

👾 NUR page replacement algorithm

Not Used Recently

 

LRU, LFU는 사실상 사용 불가.

=> 이미 메모리에 올라간 페이지의 사용횟수는 os가 알 수 없음

 

이를 보완한 NUR. access bit 사용해 이미 사용한 페이지 표시. / 사용-1, 미사용-0 (왼쪽 비트 변경해주면 됨)

 

"최근 미사용 페이지 교체 알고리즘" 이라고도 불림

1bit이기 때문에 어떤 페이지가 언제 사용됐는지, 몇 번 사용됐는지는 알 수 없음.

 

- page에 접근(read/ execute): access bit 1

- page가 변경(write/append): access bit 1, modified bit 1

 

modified bit이 1이라면, (변경사항이 있다면)

페이지가 메모리에서 삭제될 때 I/O통해서 HDD(SSD)에 변경사항을 저장하고,

modified bit이 0이라면 바로 삭제. 

 

특징

한번 access 하면 계속 access됨. 

 

👾 Clock algorithm - FIFO 변형

 

access bit = 1 이라면 포인터를 다음으로 내리고, 그 다음 사이클에서 1이었던 비트를 0으로 교체

 

👾  Frame allocation

페이지 교체 알고리즘은...

1. 메모리에 올라온 페이지들이 어떤 프로그램의 페이지인지 고려하지 않음. 

2. 자주 사용하는 페이지가 메모리를 독점하는 문제가 있음.

 

이를 해결하는 프레임 할당.

메모리를 특정 프로세스가 올라올 구역으로 미리 할당함

=> 메모리 독점 방지!

 

- process에 너무 적은 프레임 할당: page fault 빈번히 일어남

- process에 너무 많은 프레임 할당: memory 낭비 (page fault는 당연히 감소)

- process에 프레임을 할당하는 방식은 정적할당과 동적할당으로 구분. 

 

.

.

.

 

🤖 정적할당

1. Equal allocation(균등할당)

프로세스 크기와 상관 없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당

 

크기가 큰 프로세스는 필요한 만큼 프레임을 할당받지 못함 => page fault 빈번히 발생 

크기가 작은 프로세스는 메모리 공간 낭비

 

2. Proportional allocation(비례할당)

프로세스 크기에 비례하게 프레임 할당 - 균등할당의 문제 해결

 

프로세스의 크기를 고려하지 않는 균등할당보다 좀 더 현실적인 방식임.

 

*비례할당의 단점

비례할당은 프로세스가 실행 중 필요로 하는 프레임을 유동적으로 반영하지 못함. => 프로세스 실행 전 먼저 비례하게 할당하기 때문.

사용하지 않을 메모리를 처음부터 미리 확보해 공간을 낭비.

---

👾 Thrashing 

HDD의 I/O가 너무 많아져서, 잦은 page fault로 작업이 멈춘 것 같은 상태.

=> cpu사용률 급감.

 

발생시점

swap으로 페이지 쫓아내고 새로운 페이지를 메모리에 가져오는 작업이 빈번해져서 

CPU가 작업을 할 수 없는 상태에 이르게 되는 시점.

 

해결방법

- Physical 메모리의 크기를 늘리면 스레싱 발생시점 늦춰져서 원만한 프로세스 실행이 가능. 

- Frame allocation이 필요함. 

---

👾 Locality of reference

일반적으로 프로세스는 실행 시 특정 페이지만 집중해서 사용.

locality set: 집중 사용되는 페이지들의 집합.(자주 사용되는 page들)

 

In working set model!

-> locality set을 Working Set이라고 부름.

Working Set: 가장 최근에 페이지 참조를 한 page들의 집합

(자주 사용되는 것들이 가장 최근에 페이지 참조를 할 가능성 높음)

-> locality에 근거하여 프로세스가 원활히 수행되려면

  working set의 페이지들은 메모리에 미리 올라와 있어야 함

-> working set 전체가 메모리에 올라와 있어야 프로세스가 실행되고, 

  만약 한 페이지라도 올라와 있지 않다면 실행되지 않고 swap out을 해버림. 

 

특정 시간에 필요한 페이지 개수와 번호 알 수 있음

-> 다음 시간에 필요한 페이지 개수와 번호도 알 수 있나?

 예측 위해 과거 참조

-> 5,6,7,8,9,10,11이 자주 사용되었네?

미리 예상해서 5,6,7,8,9,10,11 메모리에 남기기

=> page fault 감소 (locality)

working set 페이지들은 다시 사용될 확률이 높아 Memory에 전부 올라와 있어야 함. 

---

👾 Frame allocation 

동적할당

- Working Set Model

- Page Fault Frequency

 

🤖 Working Set Model (작업 집합 모델)

최근 일정 시간 동안 참조된 page들을 집합으로 만들고,

집합에 속한 페이지들을 physical memory에 유지시킴

<working set window>
working set에 포함되는 페이지 범위. (참조한 페이지 수)

<working set size>
working set 모델에서 working set 갱신 전까지 메모리에 유지할 페이지 개수.(크기)

 

Working set size는 시간에 따라 갱신됨. 

 

OS의 Working set 관리방법

access bit(reference bit)이용해서 참조한 페이지들 관리

---

Thrashing과 Working set

ws_i는 워킹셋의 크기라고 보면 됨. 

ws1={1,2,3} 

wss1=3

 

Thrashing의 발생 조건

x: 워킹셋 크기의 합

y: 할당 가능한 프레임 수 

x>y가 되면

프로세스에 더이상 할당할 수 있는 최소 프레임이 존재하지 않기 때문에 스레싱 발생

---

Working set window의 크기와 프로세스 실행 성능

 

- 윈도우를 너무 크게 잡을 때

필요없는 페이지가 메모리에 남아서 정작 필요한 페이지도 올라가지 못함. 

 

- 윈도우를 너무 작게 잡을 때

필요한 페이지가 swap area로 쫓겨나서 프로세스의 성능 떨어짐.

 

=> 적정 크기의 워킹셋을 유지해 효율적인 메모리 관리가 필요.

---

🤖 page fault frequency (페이지 부재 빈도)

특정 프로세스의 page fault 횟수를 기록해서 page fault 비율 계산하는 방식

 

- p/f 비율이 상한선 초과하면 프레임 늘림

- p/f 비율이 하한선 밑으로 내려가면 할당한 프레임 회수(공간낭비라서)

 

프로세스를 실행하면서 추가적으로 페이지 할당/회수 반복하여 적정 할당량을 조절