🌱 Virtual Memory Mangement의 목표
Virtual Memory의 성능을 개선하는 것!
👇 Cost Model
Virtual Memory의 성능을 높이기 위한 모델
Page Fault의 횟수(Frequency, Rate)를 최소화하기 위한 모델이다.
프로세스 Pa가 실행을 시작해서 종료할 때까지, 메모리를 접근한 내역 (r1, d1) (r2, d2) .. (rt, dt)를 보자.
(페이지 번호가 Page Fault에 영향을 미치는 것은 페이지 번호이지, displacemenet가 아니다)
📌 Page Reference String = r1, r2, .. rt
📌 Page Number (페이지 번호) = ri
📌 Number of Pages of Process = N
📌 Total Number of Memory Accesses of the Process : T
Page Fault 발생률 = Page Fault 발생횟수/총 메모리 참조횟수(T)
1. Hardware Component
Virtual Memory를 지원하는 하드웨어 컴포넌트(MMU)는 무엇인가?
1) Address Translation Device
Address Mapping을 효과적으로 하기 위한 디바이스
ex. Dedicated page-table Register, Cache memories, TLB
2) Bit Vectors
가상메모리 관리를 위한 비트 벡터 Reference Bit Vector, Update Bit Vector는 모두 0부터 m-1까지 1bit vector이다. 페이지 프레임의 개수만큼 존재한다.
페이지 프레임마다 Reference Bit Vector, Update Bit Vector이 하나씩 배당되어 있다.
CPU 안에 CPU 레지스터와 같은 형태로 존재한다.
📌 Reference Bit Vector
메모리의 각 페이지 프레임의 컨텐츠가 '최근에' 참조되었는지 아닌지를 나타내는 벡터
Reference Bit 은 프로세스에 의해 참조되면 1이 된다.그러나 주기적으로 모든 Reference Bit은 0으로 리셋된다.
프로세스가 실행하다가 페이지프레임 2에 있는 컨텐츠에 접근하면, r2가 1이 된다. 어떤 프로세스가 페이지 프레임 m-1에 접근하면 r(m-1)이 1이 된다. 즉, 해당 페이지 프레임을 참조되고 있는지를 말하는 비트이다.
만약 r1의 값이 0이라면 페이지프레임 1은 최근 한번도 참조되지 않은 것이다.
📌 Update Bit
페이지 프레임의 컨텐츠가 어떤 프로세스에 의해서 변경되면 1이 된다.
이러한 일은 CPU에 의해서 '하드웨어적으로' 세팅된다. (운영체제에 의한 것이 아님 !)
Update Bit = 1은 디스크의 페이지 원본 내용과 메모리의 페이지의 내용이 같지 않다는 것을 의미한다. 즉 디스크로 다시 write하는 (write-back)이 필요하다는 것을 의미한다.
주기적으로 reset되지 않는다.
디스크로 다시 Write하면, 그 때 Update Bit은 1에서 0이 된다.
2. Software Component
1) Allocation Strategies
How / How Much를 결정하는 기법
각각의 프로세스에게 공간(페이지 프레임)을 얼마나 할당할 것인가?
페이지 프레임 할당 개수를 어떻게 할당할 것인가?
(1) 고정 할당 (Fixed Allocation)
(2) 가변 할당 (Variable Allocation)
한 프로세스에게 할당량을 너무 적게주면 메모리에 페이지를 10개는 넣어놔야 하는데 3개만 넣어두면 page fault가 많이 발생한다.
그러나 너무 많이 할당하면 메모리 낭비가 발생한다.
2) Fetch Strategies
When을 결정하는 기법
Storage에 페이지들이 있는데, 메모리에 언제 가지고 들어올까?
한 프로세스에 N개의 페이지가 있다면 언제 각 페이지를 로딩할지 결정한다.
(1) demand fetch
페이지가 프로세스를 접근하겠다고 page fault가 발생하면 그 때 fetch한다. 즉 요청이 있을때 가져오겠다는 것이다.
(2) antipatory fetch (pre-fetch)
어떤 페이지를 참조하려고 할지 예측해서 가져온다. 예측을 잘 한다면, page fault를 대폭 줄일 수 있다. 그러나 그 예측은 누가 할건데? 결국 커널이 cpu를 잡아야 하기 때문에, 예측하는 자체의 오버헤드가 발생하고 예측의 정확도도 확실하지 않다는 문제가 존재한다.
따라서 대부분은 demand fetch 기법을 사용한다. 그래서 demand paging이라 한것!
3) Placement Strategies
Where을 결정하는 기법
메모리로 들어오는 페이지를 메모리 중 어디에 위치시킬 지 결정하는 것이다.
Segmentation System에서는 first fit, best fit, worst fit, next fit이 placement 기법이다.
paging system에서는 placement 기법이 필요하지 않다. 모든 공간이 동일한 크기이기 때문이다!
4) Replacement Strategies(교체)
Who를 결정하는 기법
고정할당 기반의 교체기법
한 프로세스가 10개의 페이지를 고정할당 받았다고 가정하자. 그런데 프로세스가 실행하면서 page fault가 발생해서 새로운 페이지를 가져와야 한다. 이 경우 들어오는 페이지를 위해 현재 있는 페이지 중 어떤 것을 내보낼지 결정하는 것이다!
즉, '고정할당' 기반의 교체 기법이다!
가변할당 기반의 교체기법
page fault가 발생했을 때 현재 있는 페이지를 내보낼 필요 없이 페이지 프레임을 더 할당 받으면 된다. 반면 다른 프로세스가 할당받던 공간을 뺏을수도 있고, 내 공간을 빼앗길 수도 있기에 이경우 어떻게 교체할지에 대한 기법이다
5) Cleaning Strategies
When을 결정하는 기법
Update된 페이지(update bit=1인 페이지)를 언제 write back할지에 대한 기법이다.
(1) demand cleaning
해당 페이지가 메모리에서 교체될 때, 즉 쫓겨날 때 write back을 한다.
(2) anticipatory cleaning (pre-cleaning)
교체될 때 write back 하면 시간이 오래걸리니 그때 하지 말고, 더 이상 update 되지 않을것 같은 때를 미리 예측해서 write back 한다. 그런데 write back 하자마자 또 update되면 또 write back 해야 하므로 시기를 잘 잡아야 한다.
따라서 이 경우도 demand cleaning이 주로 사용된다.
6) Load Control Strategies
How Many를 결정하는 기법
시스템의 Multiprogramming degree(메모리를 할당받는 프로세스의 개수)를 결정하는 기법이다.
이것은 Allocation Strategy와 밀접하게 연결된다.
할당량이 줄면 degree가 높아질수 있고 할당량이 커지면 degree가 적어진다.
degree가 아주 낮으면 throughput(처리량)이 낮은데, 점점 높아지면 어느 시점 a에서 throughput이 크게 증가하지 않는다.
degree가 매우 커지면 어느 시점 b에서 throughput 성능이 더 낮아진다.
따라서 a와 b 시점을 시험해보고, b 이상 올라가지 않도록 조절해야 한다. 이것을 하는 것이 load control 기법이다!
overloaded면 프로세스가 너무 많이 들어온 상태이기 때문에 각 프로세스가 할당받는 메모리 공간이 줄어들고, 그 프로세스는 계속해서 page fault를 발생시키기 때문에 (=excessive page fault = thrashing) 이로 인해 throughput 이 낮아지는 것이다 !
✔ 실제 시스템 성능에 가장 영향을 많이 미치는 것?
Allocation과 Replacement 전략이 큰 영향을 미친다.
👇 Locality
프로세스가 프로그램, 데이터의 일부 영역에 집중적으로 접근한다. (loop 때문이다)
이렇게 일부 영역이 집중 접근되는 현상을 locality라고 한다.
1) temporal locality
한 데이터가 접근되고 나서 시간적으로 금방 접근되는 것
2) spatial locality
한 데이터가 접근되고 나서 인접한 영역의 데이터가 접근되는 것
✅ example
sum = 0;
for (i=0; i<n; i++)
sum += a[i]
return sum;Data 참조
배열을 연속적으로 접근하기 때문에 spatial locality이다.
loop을 하면서 계속해서 sum변수에 접근하기 때문에 temporal locality이다.
Instruction 참조
명령어에 대해서 대부분의 경우 순서대로 실행되기 때문에 이를 spatial locality이다.
loop을 하면서 계속해서 주기적으로 접근되는 것이 temporal locality이다.
page fault를 잘 해결하기 위해서는 locality의 특성을 잘 파악하고 있어야 한다!
