[Operating System] Virtual Memory 1

virtual memory overview

사용 이유 : memory 사용의 효율성을 위함

motivation

기존 paging 기법은 단일로는 사용할 수 없는 기술

• address space를 max로 설정하기 때문에 하나의 process도 실제 memory에 적재할 수 없기 때문

method

virtual memory : address space의 일부만 upload

• 폰 노이만의 기본 원칙에 의해 모든 process는 실행되기 위해 반드시 memory에 적재되어야 하는데, 일부만 적재
• 따라서 logical address space/phisical address space로 분리해 cpu는 logical address space만 접근할 수 있도록 한다.
  ⇒ logical address space : 크기가 매우 큰 논리적인 address space

문제점

os는 logical address space의 일부만 memory에 적재

따라서 logical address space에서 memory에 적재하지 않은 page를 요청할 경우 disk access가 발생

또한 memory가 꽉 차 있는 경우에는 page replacement가 발생

 

다음 두 가지 기술로 위 문제점을 극복

• locality
• page replacement

logical address의 장점

logical address를 사용함으로써 다음과 같은 장점을 얻을 수 있게 되었다.

1. logical address space를 사용함으로써 address space를 쉽게 share할 수 있다.
   • logical address space에서는 각기 다른 주소를 mapping
   • physical address space에서 page를 공유
2. process creation를 매우 빠르고 효율적으로 할 수 있게 되었다.
   • physical address에서는 시작 page만 올리기만 하면 되기 때문에
3. page 단위로 memory swapping이 가능하게 되었다.

Demend paging

demend paging : virtual memory에서는 page를 필요한 경우에만 memory에 적재

 

demend paging으로 다음과 같은 장점을 얻을 수 있다.

1. I/O 요청이 덜 든다.
2. memory가 덜 든다.
3. response가 더 빨라진다.
4. 많은 user가 가능

⇒ 모든 page를 한번에 memory로 적재할 필요가 없으므로

따라서 logical address에서 page를 얻기 위해서 다음과 같은 것을 확인해야 한다.

• invalid reference ⇒ abort
• not-in-memory ⇒ memory로 적재

⇒ valid-invalid bit로 이를 확인

lazy swapper

demend paging은 lazy swapper

• page는 cpu가 요청하기 전까지 memory로 적재되지 않는 것

valid-invalid bit

각 page table entry는 valid-invalid bit를 갖고 있다.

• valid : 해당 page가 memory에 존재
• invalid
  1. illegal : 해당 page가 process의 address space의 범위 밖
  2. not-in-memory : 해당 page가 memory에 존재하지 않는 경우
  3. obsolete : 해당 page가 다른 process에 의해 disk에서 수정된 경우
  ⇒ not-in-memory/obsolete의 경우 모두 disk에서 다시 읽어와야 한다.

address translation 중 logical address가 invalid되는 경우 page fault라고 한다.

Page Fault

OS의 경우 page fault handler를 통해 page fault를 처리

1. OS page table을 확인한다.
   • illegal reference(bad address, pretection violation)이 발생한 경우 abort
   • not in memory나 obsolete인 경우 다음 단계를 진행
2. empty page frame을 search
   • empty page frame이 없는 경우 page replacement algorithm 수행
3. disk에서부터 해당 page를 읽어 frame에 적재
   • 결국 I/O 요청이므로 해당 process를 wait 상태로 만든 뒤 I/O 명령을 실행
   • I/O read가 끝난 뒤, 적재된 page table entries의 valid bit를 true로 setting
   • process를 다시 runnable 상태로 만들어 ready queue에 놓는다.
4. process가 다시 scheduler에 의해 실행되면 page fault trap을 종료
5. page fault trap이 종료된 후, page fault가 발생했던 지점부터 다시 instruction을 시작

문제점

page fault trap이 실행되고 다시 instruction이 실행되면서 데이터 무결성이 깨질 수 있다.

 

ex) block copy instruction

destination으로 copy 중 page를 load해 해당 code부터 다시 실행하게 될 경우 문제가 발생할 수 있다.

 

해결책

• Undo
• ⇒ 일시적으로 address와 values를 저장할 수 있는 HW를 둔다.

Performance of Demand paging

• page fault overhead : page fault trap을 실행하는 시간
• swap page in : page를 적재시키는 시간
• swap page out : page를 replacement 시키는 시간
• ⇒ 항상 swap이 발생하는 것은 아니고, swap 되더라도 해당 page의 값이 바뀐 경우에만 disk에 다시 써주기 때문에
• restart overhead : scheduling이 다시 발생되면서 생기는 overhead
• ⇒ context switching overhead, cache flushing overhead ...

example

• 정답

type of demand paging

1. pure demand paging
   • 실제 page가 요청받기 전까지는 memory에 적재되지 않는 방식
2. locality of reference
   • page를 locality를 반영해 연속된 page를 같이 memory에 적재
   • paging system이 실제로 동작될 수 있도록 한다.

Page Replacement

free frame이 없는 경우 어떤 page를 swap-out할 것인가를 선택

goal : page faults가 가장 적게 일어날 수 있도록 page를 replacement

• 또한 수정된 page의 경우 swap-out될 때 I/O 연산이 발생하므로 이를 고려해서 replacement해야 한다.
  ⇒ page table에 dirty bit를 추가로 둬 해당 page가 수정되었는지를 표시

basic page replacement

1. disk에서 memory에 올릴 page의 위치를 찾는다.
2. free frame을 찾는다.
   • 존재하는 경우 그 자리에 page를 바로 적재
   • free frame이 존재하지 않는 경우 page replacement로 victim page를 선택
3. page와 free frame tables을 update한다.
4. process를 재시작 한다.(ready queue로 전환)

basic assumption

전체 frames의 개수가 늘어나면 늘어날수록 여러 page를 동시에 적재할 수 있기 때문에 page faults의 수가 줄어들 것이라고 생각하게 된다.

 

하지만 FIFO algorithm의 경우 위 assumption이 들어맞지 않는 경우가 발생

⇒ Belady’s Anomaly

optimal algorithm

미래의 일어날 일을 모두 아는 경우에 발생하는 최소의 page faults

• 앞으로 접근할 page 중 가장 나중에 접근하게 될 page를 먼저 swap-out하는 경우, 6번의 page faults가 발생

LRU(Least-Recently Used) Algorithm

미래를 예측할 수 없으니, 과거를 바탕으로 선택을 하는 page replacement 방식

• 가장 예전에 선택된 page를 먼저 swap-out한다.

problem

1. 각 page가 언제 마지막으로 접근되었는지를 time-stamp로 기록해야 한다.
   • timer I/O를 요청해야 한다.
2. timestamp를 저장할 추가적인 공간이 필요하다.
3. timestamp값을 기준으로 최솟값을 searching해야 한다.

⇒ 이러한 문제 때문에 LRU를 효율적으로 구현할 수 있는 방법들이 필요

LRU Implementation algorithm

Counter implementation

timer 대신 integer를 입력하는 방식

• timer I/O를 요청하지 않아도 된다.
• 하지만 추가적인 공간 및 searching overhead가 여전히 존재

Stack implementation

stack과 doubly linked list를 이용해 page를 관리

• stack에서 특정 page가 접근될 때마다 stack의 최상단으로 올린다.
  ⇒ 최하단의 page가 자동적으로 victim이 되게 된다.

1. stack에서 7번 page의 위치를 찾는다.
2. doubly linked list이므로 0번과 4번 pointer를 변경시켜야 한다.
   ⇒ 2번의 포인터 연산
3. 7번 page를 stack의 맨 위로 올린다.
   ⇒ 2번과 7번을 연결시켜야 하므로 2번의 포인터 연산
4. stack top pointer과 7번을 연결한다.
   ⇒ 2번의 포인터 연산

총 6번의 포인터 연산이 발생하게 된다.

이러한 추가적인 포인터 연산은 page에 접근할 때마다 발생하게 되므로(stack 유지 overhead) overhead가 지나치게 많아져 사용할 수 없다.

LRU approximation algorithms

여러 LRU algorithm들의 overhead가 너무 커 실제 적용할 수 없었기 때문에 실제 적용할 수 있는 overhead를 갖고 LRU와 비슷하게 동작할 수 있는 algorithm을 고안

reference bit

1. 각 page마다 reference bit가 존재
2. page가 접근되는 경우 해당 page의 reference bit를 1로 설정
3. 특정 주기마다 모든 page의 reference bit를 다시 0으로 초기화
4. page replacement 발생 시 reference bit 0인 page 중 하나를 무작위로 swap-out

• 공간/search overhead가 거의 없지만, 성능도 지나치게 떨어진다.

additional-Reference bits

기존 reference bit가 초기화될 때마다 해당 값을 additional-reference bit에 기록하는 방식

1. refernce bit를 additinal-reference bit의 가장 왼쪽에 채워넣고 이전 값들은 right-shift하는 방식으로 구현
2. 이렇게 구현함으로써 최근에 reference bit가 1이었던 page의 AR값이 더 큰 값을 가지도록 할 수 있다.
3. AR값을 비교해 AR값이 가장 작은 page를 swap-out

하지만 결국 해당 알고리즘 역시 AR값의 최솟값을 searching해야 하기 때문에 overhead가 너무 크다는 단점이 존재

second-chance(clock) algorithm

1. next victim pointer가 가리키는 page의 reference bit가 0인 경우 해당 page를 swap-out
2. next victim pointer가 가리키는 page의 reference bit가 1인 경우 해당 page의 reference bit를 0으로 만든 뒤 다음 page로 이동
3. 위 방식을 특정 page가 swap-out될 때 까지 반복

이러한 방법은 결국 두 page가 동일하게 reference bit가 0이더라도 order가 부여되어 누가 더 오래 reference bit를 0으로 유지했는지를 알 수 있게 해준다.

위 예제에서 1번과 2번의 경우 둘다 refererence bit가 0이지만 1번의 경우 next victim이 방금 지나쳤기 때문에 2번 page가 더 오랫동안 reference bit를 0으로 유지하고 있음을 알 수 있게 된다.

other counting algorithm

1. LFU(least-frequently used) algorithm : 지금까지 가장 적게 참조된 page를 제거
2. MFU(most-frequently used) algorithm : 지금까지 가장 많이 참조된 page를 제거
   • 충분히 할당받았다는 차원에서

참고

- Operating System Concepts

- 운영체제, 한양대학교 강수용 교수님