11. Virtual Memory (2)

page fault를 많이 발생시키지 않기 위해서는 앞으로 사용되지 않을 가능성이 높은 페이지를 victim으로 선정하는 것이 중요하다.

앞에서는 이 프로세스에게 몇 개의 프레임이 할당되었다는 가정 하에 victim을 선정했었다.

그러기 위해서는 처음에 각 프로세스에게 몇 개의 frame을 할당할 것인가를 정해야 한다.

 

Allocation of Frames

각 프로세스마다 필요로 하는 최소 frame의 수가 있을 것이다.

 

하드웨어적인 측면에서 instruction 하나가 6byte라면, instruction 하나가 2페이지에 걸쳐서 있을 수 있다.

그리고 그 명령이 source의 주소에 있는 데이터를, destination에 있는 주소에 옮겨라. 이런 instruction이고 source가 2 페이지에 걸쳐서 있고, destination 역시 2 페이지에 걸쳐서 있다면 총 6개의 페이지에 접근할 것이다.

=> 이 instruction은 최소 6개의 페이지를 필요로 한다.

=> 5개의 frame만 할당하게 되면 instruction을 수행하지 못 하게 될 수도 있다.

 

소프트웨어적인 측면에서, 자주 접근되는 데이터는 메모리에 올라와 있는 것이 좋다.
그렇지 않으면 계속 페이지 폴트가 발생할 것이니까.
Loop같은 경우는 Loop를 포함하고 있는 페이지와 데이터는 메모리에 올라와 있어야 Loop를 도는 동안에 페이지 폴트가 나지 않는다.

=> 자주 수행되는 instruction과 Data는 메모리에 올라와 있는 것이 중요하다.

=> 소프트웨어 측면에서 locality에 포함되는 instruction과 data는 메모리에 올라와 있을 수 있을 만큼 충분히 frame이 할당 되어야 이 프로세스가 도는데 있어서 성능 저하가 발생하지 않을 것이다.

 

프로세스에게 frame을 할당하는 방법 2가지를 살펴보자.

Fixed Allocation과 Priority Allocation

 

Fixed Allocation

이름에서 알 수 있듯이 Fixed Allocation 방식은 각 프로세스에게 고정된 수의 frame을 할당해준다.

Equal allocation

: 프로세스의 크기와 관계없이 모든 프로세스에게 동일한 페이지를 할당한다.
E.g 100개의 사용가능한 frame이 있고, 프로세스가 5개라면 프로세스당 20개의 frame 할당

Proportional allocation

: 프로세스 크기의 비율에 따라 프레임을 할당하는 방법

 

Fixed allocation은 매우 간단한 방식으로 frame의 수를 결정한다.

 

Priority Allocation

Priority Allocation은 Proportional Allocation 기법인데 단지 사이즈를 기반으로 비례해서 주는 것이 아니라 프로세스의 중요도를 기반해서 비례하게 프레임을 할당하는 기법

프로세스에게 프레임을 많이 할당해주면 페이지 폴트가 자주 발생하지 않게 되고, I/O가 많이 발생하지 않으므로 빨리 수행될 수 있다.
=> 우선 순위가 높은 프로세스에게 많은 frame을 할당해서 빨리 끝날 수 있도록 해준다.

그런데 우선순위 또는 사이즈만을 가지고 frame을 할당해주면 정확하게 동작을 할까??
우선순위 또는 사이즈를 기준으로 할당하면 프로세스가 동작하는 과정에서 동적 할당을 받아서 사이즈가 커질 수가 있다.
그러면 frame이 부족하게 될 것이고 페이지 폴트가 자주 발생하게 된다.

도는 과정에서 할당된 frame의 수를 변경하는 매커니즘이 필요하지 않을까?

 

Global vs Local Replacement

자신에게 할당된 frame안에서 victim page를 선정하는 것을 local replacement라고 한다.
이와 다르게 다른 프로세스의 frame 중에서 victim을 선정할 수 있게 하는 것이 global replacement이다.

자신에게 할당된 frame 내에서 victim을 선정하게 되면 page fault가 자주 발생하더라도, 자신에게 할당된 frame의 수는 유지가 될 것이다.

반면 다른 프로세스의 frame 중에 victim을 설정하고 자신의 페이지를 올리면, 프로세스에게 할당된 frame의 수가 변하게 된다.

global replacement의 장점 중 하나가 victim을 선정하기 위해서는 모든 페이지를 관리를 해야 하는데, 예를 들어 clock algorithm을 사용한다고 하면 페이지들을 circular queue로 쭉 연결을 했었다.
local replacement 기법만을 사용한다면 프로세스마다 circular queue가 만들어지게 될 것이고, global replacement 기법을 사용하면 시스템 내에 하나의 큰 circular queue가 만들어지게 될 것이므로 관리가 더 쉽다.

 

필요한 메모리 사이즈가 고정되어 있는 특수목적 시스템이라고 하면, fixed allocation에 local replacement만 사용해도 충분할 것이다.
그런데 일반적인 시스템에서는 그렇게 할 수가 없기 때문에 Global replacement를 사용할 필요가 있을 것이다.

둘 중 어떤 방법을 쓰든 반드시 알아야 하는 개념이 있다.
=> Thrashing

 

Thrashing

지금까지 페이지 frame이 부족할 경우 어떤 놈을 victim으로 선정해서 쫓아낼 것인가. 어떻게 하면 페이지 폴트를 최소화 할 수 있을 것인가 하는 알고리즘들을 배웠다.

그런데 이런 것들이 모두 무의미해지는 경우가 있다.
하나의 프로세스에 할당된 frame의 수가 과도하게 작으면, 아무리 좋은 알고리즘으로 victim을 선정한다고 하더라도 페이지 폴트가 급격하게 발생하는 것을 막을 수가 없다.

각 프로세스가 충분한 페이지를 할당받지 못하면 페이지 폴트가 자주 발생하게 되고, 그렇다면 I/O가 자주 발생한다는 것이므로 CPU utilization이 떨어진다.
그러면 long term scheduler는 utilization을 높이기 위해 새로운 프로세스를 편입시킨다.
그렇게 되면 기존 프로세스들이 새로운 프로세스에게 자원을 나눠주어야 하고, frame이 더 부족하게 되므로 utilization이 더 떨어진다.
그럼 long term scheduler는 프로세스를 더 편입시키는 악순환이 반복된다.

 

메모리가 절대적으로 부족해서 페이지 폴트 발생 횟수가 급격히 증가해서 I/O만 발생하는 상황을 Thrashing이라고 한다.

main()

{ for (I = 1, 100000) {A = B + X}}

이러한 Loop가 있을 때, 운이 나쁘게도 main문, I, A, B, X가 모두 다른 페이지에 들어있다고 해보자.

그런데 할당된 페이지 frame이 4개라고 하면 메모리에 올라와 있지 않은 변수가 반드시 한 개 존재하게 된다.

=> Loop를 돌 때마다 페이지 폴트가 발생한다.

페이지 frame이 5개였다면, 변수가 들어 있는 모든 페이지가 메모리에 올라올 수 있게 되므로 메인 함수가 문제없이 돌아갈 수 있었을 것이다.
=> 페이지 frame 하나가 모자라서 페이지 폴트가 최소 10만 번 발생

충분한 페이지 frame이 없으면, 페이지 폴트가 발생하는 횟수가 급격하게 증가하고 페이지 폴트는 곧 I/O가 발생하는 것을 의미하므로 성능 저하를 시킨다.

실행되는 프로세스의 수가 점점 증가하게 되면 언젠가 결국 절대적으로 메모리의 크기가 부족한 상황이 오게 된다.
그러면 페이지 폴트가 발생하는 횟수가 급격하게 증가하게 되고 I/O만 발생해서 CPU utilization이 급격히 감소하는 상황이 된다.
=> Thrashing 발생

프로세스의 개수가 너무 과도하게 되면 프로세스당 할당되는 frame의 수가 너무 줄어들게 되고, 페이지 폴트가 급격하게 발생하게 되어 Thrashing이 발생되게 된다.

과도하게 많은 프로세스가 동시에 실행되면 안 된다.

 

페이지 폴트가 발생하면 엄청난 성능 저하를 일으키는데, 어떻게 페이징 기법을 사용할 수 있을까?

바로 locality가 있기 때문이다, locality에 의해 자주 접근되는 페이지들이 메모리에 올라와 있다면 페이지 폴트가 그렇게 자주 발생하지 않을 것이다.

locality는 시간에 따라 변하기 때문에, 현재 프로세스의 locality를 메모리로 다 올리기 위해서 필요한 frame의 수가 그때 그때 변할 수 밖에 없다.

=> 이론적으로 알아둬야 할 사실은 왜 Thrashing이 발생하는지이다.

=> 각 프로세스의 locality의 합이 할당된 메모리 사이즈의 합보다 크면 Thrashing이 발생한다.

 

그렇다면 과도하게 많은 프로세스가 수행되게 된다면 어떻게 해야 할까?
OS가 지금은 Thrashing의 발생 위험이 있으므로 프로그램을 실행할 수 없습니다.
이렇게 처리하는 것이 맞을까?
아니다. OS는 어떻게든 실행을 시켜주어야 한다.
그 뒷감당은 사용자가 하는 것이다.

=> 요즘 대부분의 OS는 Thrashing이 발생해도 막지 않는다.

 

Locality

이전에도 말했듯이, 어떠한 시점에 자주 접근되는 instruction과 data는 반드시 존재한다.

locality의 종류는 2가지가 있다.

시간 지역성은 가까운 시간 내에 정확히 "같은" 메모리가 다시 참조될 가능성이 높음을 의미한다.

공간 지역성은 가까운 시간 내에 현재 접근 중인 메모리의 "주변" 메모리가 참조될 가능성이 높음을 의미한다.

 

Working-Set Model

Working-set model은 Thrashing 문제를 해결하기 위한 이론적인 방법이다.

델타(△)는 working set을 도려내기 위한 window.
=> 현재 시점의 locality에 포함되는 페이지들을 도래내는 것이 목적이다.
=> 현재 시점을 define하기 위해서 사용되는 window

 

Working Set은  [ti ~ ti - △]에 접근된 페이지들의 집합이다.

델타가 너무 작으면 즉, 너무 작은 구간을 대상으로 working set을 찾아낸다면 큰 locality를 수행하고 있는 프로세스의 경우에 working set이 전체 locality를 포괄하지 못 하게 될 수 있다.
=> 정확도가 떨어짐

델타가 너무 커지면, locality가 이미 지나간 페이지들도 working set에 포함될 수 있다.
=> 정확도가 떨어짐

window의 사이즈에 따라 working set의 정확도가 달라진다.

WSSi는 현재 시점의 프로세스 i의 working set 사이즈이다.

D는 모든 프로세스들의 working set 사이즈의 합이다.

=> 총 요구되는 frame의 개수가 된다.

실제 메모리 상에 존재하는 frame의 수(사용 가능한 frame의 수)를 m이라고 했을 때, D > m이라면 요구되는 frame을 모두 충족시켜주지 못 한다는 뜻이므로 무조건 Thrashing이 발생한다.

 

만약 D > m이면 프로세스 하나를 suspend 시킨다. 하나를 suspend 시켰는데도 D > m이면 하나 더 suspend 시킨다.
언제까지? D <= m을 만족할 때까지


suspend를 시킨다는 것이 부정적인 것이 아니다.
몇 개의 프로세스를 suspend 시켜서 시스템이 정상적으로 동작할 수 있도록 만들고, 일을 끝 마치고 빠져나가는 프로세스가 생기면 suspend된 프로세스를 다시 실행시키고 이렇게 한다면, Thrashing이 발생했을 때보다 훨씬 더 빨리 일이 처리될 것이다.

=> 과감하게 Suspend를 하는 것이 유리하다.

Working set model은 Multiprograming degree(동시 수행 중인 프로세스의 수)가 변할 수 있는 방식이다.

물론 이것은 모두 이론일 뿐이다.
사용자의 지시 없이 OS가 마음대로 프로세스를 suspend를 시키는 경우는 잘 없을 것이다.
이건 OS의 디자인 철학마다 다를 것

 

시간이 지나면 locality도 변화하게 되는데, working set model은 이것을 잘 따라가고 있다.

Working set model은 프로세스에게 할당되는 frame의 수도 결정하고, 페이지 교체를 할 때 어떤 페이지를 victim으로 선정할지도 결정한다.

Victim을 선정해야 할 때, Working set에 포함되지 않은 페이지 중 하나를 Victim으로 선정한다.

Allocaton을 할 때, Working set의 사이즈에 따라 frame을 할당한다.

=> Working set이 모든 locality를 포함한다고 하면, 모든 locality가 메모리에 올라올 것이다.

 

Keeping Track of the Working Set

Victim을 선정할 때, 해당 페이지가 Working set에 포함되어 있는지 확인하기 위해서는 각 페이지마다 참조된 시점을 적는 space가 필요하다. 또한 working set에 포함되었는지 아닌지를 확인하기 위해서는 reference time을 델타 값과 비교를 해야 한다.
=> 구현이 어렵다

그렇다면 Working set에 포함되었는지를 Approximate하는 방법을 생각해보자.

특정 시간마다 인터럽트를 발생시키는 타이머와, 추가적인 Reference 비트가 필요하다.

델타가 10K라고 했을 때, 5K마다 타임 인터럽트를 보내서 Reference bit를 왼쪽 bit에 카피하면서 0으로 만든다.

확인한 시점에 방금 ①번 bit가 1로 set 되었다면 최근 5K 시간 내에 접근을 했다고 생각할 수 있다.

확인한 시점에 ②번 bit가 1로 set 되어 있으면 최근 5K ~ 10K 내에 참조가 되었음을 추측할 수 있다.

그런데 과연 진짜 5K ~ 10K 내에 참조가 된 걸까??
만약 확인한 시점 직전에 copy가 되었다고 하면 실제 5K ~ 10K 내에 참조된 것이 맞다.
그런데 또 다시 5K가 지나야 bit가 변경되기 때문에, 사실상 14,999 시간 전에 reference가 되었어도 여기가 1로 set되어 있을 것이다.
최악의 경우엔 0 ~ 14,999시간 내에 참조가 되었는지를 체크하는 셈이 되는 것이다.
4,999를 초과해서 윈도우를 갖게 되는 효과가 나타난다.
=> 정확도가 거의 50% 떨어짐.

 

이걸 개선하는 방법은 1,000번에 한 번 copy를 하되, 추가적인 bit를 10bit 사용한다.
=> 제일 마지막 bit는 9,000 ~ 10,999 사이에 참조되었는지를 나타내게 된다.
=> 오차가 10%로 낮아졌다.

타이머 인터럽트 간격을 짧게 하면, 정확성은 높아지지만 추가적인 bit가 많이 필요하게 된다.

=> 뭐 그렇다 하더라도 더 큰 문제는 델타를 어떻게 결정할지가 문제다.
과거 얼마까지 봐야 정확한 working set이 될까.
프로세스마다 locality 크기가 다 다르기 때문에 델타 값을 어느 정도로 해야될지 정하기가 어렵다.
프로세스마다 타이머 디바이스를 각각 준다고 하더라도 프로세스가 돌기 전에 locality의 크기를 알 수 없기 때문에 델타를 얼마로 정할지 정하기가 어렵다.

이론적으로는 괜찮지만, 실제 구현이 어렵기 때문에 OS는 working set model을 사용하고 있지 않다.

 

Page-Fault-Frequency Scheme

앞선 내용을 봤을 때, locality를 파악해서 정확히 working set을 찾는 것은 거의 불가능하지 않나.
더 간단하게 접근해서, 프로세스가 메모리가 부족한지 안 부족한지를 알 수 있는 시그널만 포착해보자.
=> 그 시그널은 프로세스가 페이지 폴트를 얼마나 자주 발생시키는지가 된다.
=> 페이지 폴트가 발생하는 빈도를 가지고 working set의 크기를 추정

상한선과 하한선을 둬서 페이지 폴트가 상한선보다 많이 발생하면, frame이 부족한 것으로 판단하고,
하한선보다 페이지 폴트가 적게 발생하면 frame이 너무 과도하게 할당된 것으로 판단한다.

하한선보다 페이지 폴트가 적게 발생하는 프로세스의 frame을 뺏어서 페이지 폴트가 많이 발생하는 프로세스에게 할당해준다.

꽤나 합리적이면서도 구현도 간단한 방법

working set model에서는 reference가 한 번 발생할 때마다 window를 움직여서 working set을 수정해야하므로 오버헤드가 엄청 크다.

반면 Page-fault Frequency scheme에서는 페이지 폴트가 발생할 때마다 페이지 폴트가 발생한 프로세스의 페이지폴트 rate만 바뀌게 된다.
=> 드물게 수정

메모리 reference의 횟수와 페이지 폴트의 발생 횟수는 차이가 매우 크다.
=> 오버헤드 차이가 크다.

 

PFF 방식은 오버헤드도 크지 않아 보이고, 구현도 간단해 보이는데 그렇다면 이 방법을 실제 사용할까?
아니다. 
하한선보다 페이지 폴트 발생횟수가 낮은 프로세스에서 frame을 하나 뺏어야 하는데, 어떤 frame을 뺏을까?
그걸 결정하려면 결국은 locality에 포함되지 않은 frame을 찾아야 한다.
=> Working set model과 동일한 문제가 발생

페이지 교체 기법이 이미 구현되어 있는 상황에서, victim frame을 선정할 프로세스를 선정하는 방법으로 사용될 수는 있다.

PFF 기법은 frame의 개수를 정하는 용도로만 사용될 수 있고, 별도의 victim selection 기법이 사용되어야 한다.

---

이제부터는 Virtual memory를 사용했을 때 생기는 부가적인 이점들을 살펴볼 것이다.

 

Copy on Write

부모 프로세스가 자식 프로세스를 fork할 때 기본적으로 부모 프로세스의 address space를 자식 프로세스에게 그대로 복사해준다고 했다.
=> memory copy는 오버헤드가 매우 크다.

virtual mermoy를 사용하면 논리적으로는 독립적인 address space를 만들어 주지만, 실제로는 부모 프로세스의 physical address를 공유하도록 할 수 있다.
=> 페이지 테이블만 카피해주면 된다. 그렇게 되면 logical address가 같은 물리 주소로 매핑되기 때문에 메모리를 공유하게 된다.
=> 프로세스는 logical address space만 보기 때문에 실제로는 어떤 일이 일어나는지 보지 못한다.

부모든 자식이든 공유하고 있는 space에 write를 하게 되면 그때는 실제로 별도의 공간을 만들어서 복사해 주어야 한다. 
=> write가 발생하면 실제로 copy를 하기 때문에 Copy on write라고 한다.

 

프로세스 1이 write를 하게 되면 실제 copy를 만들어서 매핑해준다.

write가 발생하면, write가 발생하는 일부만 분리해서 각자 갖도록 만들어 준다.

이렇게 하면 write가 일어나지 않는 부분은 계속 공유가 된다.

=> 최소한 Read only인 코드 영역은 공유가 될 것이다.

 

Memory Mapped Files

프로세스가 접근하는 파일인데, 그 파일을 파일 데이터로 접근하지 말고, 파일의 전체 데이터를 address space에 집어 넣는다 (mapping 시킨다).

파일의 첫 번째 데이터는 몇 번지, 두 번째 데이터는 그 다음 번지 이렇게 파일의 내용을 address space에 매핑을 시킨다.

그리고 나서 그 파일에 대한 접근을 file system을 통해서 즉, read, write로 접근하는 것이 아니라 메모리 access로 접근한다.

이게 virtual memory와 무슨 상관?
실제 파일을 logical address space 상에 매핑을 시킬 때, virtual memory가 없다면 파일의 전체 내용이 실제 메모리에 다 올라와야 한다.
=> 접근하지 않는 데이터도 메모리에 다 올라오게 된다.
=> 오히려 비효율적이게 된다.

virtual memory를 사용하면 logical address space에 파일을 매핑한다고 하더라도, 실제 접근하는 페이지만 메모리에 올라오게 되니까 모든 파일이 메모리에 올라오는 일이 없게 되므로, Memory-Mapped File 기법을 사용할 수 있게 된다.

 

여러 프로세스가 하나의 파일에 접근한다고 하면, 실제 메모리에는 한 번만 올리고 같은 주소로 매핑을 해서 데이터를 공유하도록 할 수 있다.

=> write가 발생하지 않으면 하나의 copy만으로 여러 프로세스가 파일을 공유하도록 할 수 있다.

---

여기부터는 virtual memory와 관련된 주변적인 issue들을 볼 것이다.

 

Prepaging

pure demand paging을 사용하면, 프로세스가 처음 시작되면 초기에는 매번 페이지 폴트가 발생한다.

프로세스의 시작 단계에서 페이지 폴트를 줄이기 위해서, 시작하고 페이지 폴트가 발생할 때마다 한 페이지씩 올리는 것이 아니라 프로세스가 시작하기 전에 미리 메모리에 페이지를 많이 올려둔다.
=> 초기 단계에 발생하는 페이지 폴트의 수가 많이 줄어들 것이다.
=> 하지만 미리 올려둔 페이지를 사용을 하지 않으면 오히려 불필요한 일을 해버린 것이다.
=> 그렇기 때문에 미리 몇 페이지를 올릴지를 결정을 해야 한다.

 

Page size

페이지의 사이즈를 얼마로 잡아야 할까?

페이지 사이즈가 크면, 전체 페이지의 수가 줄어든다.
=> 매핑할 페이지의 수가 줄어든다는 뜻이므로 페이지 테이블의 사이즈가 줄어든다.
또한 페이지 폴트가 발생했을 때, 디스크에서 가져오는 데이터의 양이 많아지므로 I/O 측면에서도 좋다.
locality 측면에서 하나의 페이지 frame이 많은 양의 locality를 포함할 수 있기 떄문에 locality 보존 측면에서도 장점을 갖는다.

그런데 internal fragmentation이 커진다는 단점이 있다.

요즘은 메모리의 사이즈가 커서 internal framgmentation이 조금 커지더라도 그렇게 큰 영향을 미치지 않는다.
그보다는 I/O로 인해 발생하는 시간적 측면에서의 낭비를 줄이는 것이 더 중요하기 때문에 페이지 사이즈의 크기를 키우는 방향으로 발전하고 있다.

 

TLB Reach

TLB Reach는 TLB hit를 통해 얼마나 많은 페이지 접근을 할 수 있는지를 나타낸다.
=> TLB Reach가 크면 클수록 좋은 것이다.

TLB Reach = (TLB Size) X (Page Size)로 몇 바이트가 TLB를 통해 주소 변환이 가능한가를 나타낸다.

 

이상적으로 locality에 포함된 페이지들은 모두 TLB를 통해 주소 변환을 할 수 있으면 좋다.

TLB Size는 하드웨어적으로 고정되어 있으므로 페이지 사이즈를 키워서 TLB Reach를 키울 수 있겠다.

하지만 Page size를 키우면 Internal fragmentation이 커진다고 했다.
물론 요즘은 페이지 사이즈의 크기를 키우는 방향으로 발전하고 있다고 했지만, TLB Reach를 키우기 위해서 Page size를 키우기는 좀 그렇다.

최신 OS 기술 중에 페이지 사이즈가 고정되어 있지 않고, 페이지 사이즈가 여러 개가 있는 경우도 있다.
=> 제일 마지막 페이지의 경우 작은 페이지로 할당하면 internal fragmentation을 줄이면서도 TLB Reach는 키울 수 있다.

 

Program Structure

프로그램 코드에 따라 페이지 폴트의 발생 횟수가 달라진다.

int data[128][128] 이러한 배열이 있고, 한 페이지에는 하나의 row가 통째로 들어갈 수 있다고 가정하자.

그리고 frame의 수는 128개보다 적다고 가정한다.

=> 따라서 모든 data가 메모리에 올라올 수 없으므로 페이지 폴트가 발생할 수 밖에 없다.

 

for(j = 0; j < 128; j++)
	for(i = 0; i < 128; i++)
    	data[i][j] = 0;

이러한 코드가 있다고 하면, row 순서대로 data에 접근하는 것이다.

처음에는 매 접근마다 페이지 폴트가 발생할 것이고, 한 바퀴를 돌고 다시 i = 0이 되었을 때는 해당 row는 밀려나서 메모리에 올라와 있지 않을 것이므로, 또 다시 페이지 폴트가 발생한다.

=> 모든 접근에서 페이지 폴트가 발생한다. 따라서 128 * 128 = 16,384번의 페이지 폴트가 발생한다.

 

for(i = 0; i < 128; i++)
	for(j = 0; j < 128; j++)
    	data[i][j] = 0;

반면에 이 코드는 column 순서대로 data에 접근을 한다.

모든 row의 첫 번째 column을 접근할 때에는 페이지 폴트가 발생하겠지만, 페이지에는 하나의 row가 통째로 올라오기 때문에 다음 접근부터는 메모리에 올라와 있는 데이터에 접근하는 것이므로 페이지 폴트가 발생하지 않는다.

=> 따라서 총 128번의 페이지 폴트가 발생한다.

이 코드는 free frame이 하나만 있더라도 128번의 페이지 폴트가 발생한다.

 

I/O interlock

하드 디스크에서 파일을 읽어서 USB로 카피하고 싶다면,  먼저 하드디스크에서 데이터를 읽어와서 버퍼에 올린다.

그런 다음 버퍼에 올린 데이터를 USB로 다시 내보내는 형식으로 카피가 이루어질 것이다.

그런데 이 버퍼에 올린 놈이 페이지 교체 알고리즘으로 인해 디스크로 쫓겨나게 된다면, 다시 디스크에서 올려야 한다.

이런 경우, 하드 디스크에서 읽어온 데이터는 Victim으로 선정되지 않도록 보호해줄 필요가 있다.
=> pin을 꼽는다고 해서 pinning이라고도 한다.

I/O를 위해서 사용되는 버퍼는 victim으로 선정되어 swap out되는 경우가 없도록 lock을 거는 것을 I/O Interlock이라고 한다.

 

총 정리

virtual memory는 메모리 공간 사용의 효율성을 높여주는 좋은 기법이다.
단지, virtual memory의 핵심인 demand paging을 위해서는, 메모리에 접근이 일어날 때 페이지 폴트로 인한 I/O가 발생해서 성능 저하가 발생할 수 있다.
=> 성능 저하를 최대한 막기 위해 victim을 잘 선정해야 한다.
=> locality를 최대한 보존할 수 있도록 victim을 선정하는 알고리즘들을 봤었다.

페이지 폴트를 줄이기 위해 locality를 잘 보존할 필요가 있고, locality들은 웬만하면 메모리에 올라와서 보존될 필요가 있더라. 그러기 위해서는 locality가 올라올 수 있는 충분한 frame을 프로세스에게 제공할 필요가 있다.
=> locality를 파악하기 위한 모델들이 필요하다.

그런데 working set model을 사용했을 때, locality를 일일이 파악하는 것은 매우 어렵기 때문에, locality를 추정하는 PFF라는 기법도 있었다.

 

※ 본 내용은 한양대학교 강수용 교수님의 강의를 바탕으로 작성되었습니다.