[ OS ] 16. 메모리 관리 전략 - 가상 메모리 Paging (Demand Paging)

가상 메모리 Paging

다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야 한다. 가상메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법 이며, 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다.

실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 메모리 용량보다 큰 프로그램은 실행시킬 수 없었다. 또한, 여러 프로그램을 동시에 메모리에 올리기에는 용량의 한계와, 페이지 교체등의 성능 이슈가 발생하게 된다. 또한, 가끔만 사용되는 코드가 차지하는 메모리들을 확인할 수 있다는 점에서, 불필요하게 전체의 프로그램이 메모리에 올라와 있어야 하는게 아니라는 것을 알 수 있다.

• 프로그램의 일부분만 메모리에 올릴 수 있다면...
  • 물리 메모리 크기에 제약받지 않게 된다.
  • 더 많은 프로그램을 동시에 실행할 수 있게 된다. 이에 따라 응답시간은 유지되고, CPU 이용률과 처리율은 높아진다.
  • swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행된다.

위 그림과 같이 프로세스간의 페이지 공유가 가능하다.

• 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 한다. 각 프로세스들은 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가있는 물리 메모리 페이지들은 모든 프로세스에 공유되고 있다.
• 프로세스들이 메모리를 공유하는 것을 가능하게 하고, 프로세스들은 공유 메모리를 통해 통신할 수 있다. 이 또한, 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있다.
• logical address는 physical address로부터 분리된다.
• fork()를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 한다.

Demand Paging

요구 페이징

요청 할 때 Paging을 한다.

프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라 하며, 가상 메모리 시스템에서 많이 사용된다. 그리고 가상 메모리는 대개 Page(페이지)로 관리된다. 요구 페이징을 사용하는 가상 메모리에서는 실행과정에서 필요해질 때 페이지들이 적재된다. 한 번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.

프로세스 내의 개별 페이지들은 페이저(pager)에 의해 관리된다. 페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어 옮으로서, 사용되지 않을 페이지를 가져오는 시간낭비와 메모리 낭비를 줄일 수 있다.

위 그림은 메인 메모리에 페이지가 존재 하지 않을 때의 Page Table의 상황이다. page table의 valid-invalid bit를 통해서 physical memory에 어떤 페이지가 올라가 있는지 확인한다.

• valid : page가 legal 하면서 메인 메모리에 있다.
• invalid : page가 not valid 하거나 Secondary Stroage(HDD, SDD)에 있다.

위 그림은 Page Fault가 일어 났을 때 처리하는 과정을 나타낸다.

1. M이라는 페이지를 메모리에 로드하려고 할 때, page table에서 해당하는 페이지의 vaild-invalid bit를 체크한다.

2. 만약에 Page Fault라면(invalid) MMU(Memory Management Unit)가 O/S에 trap을 발생시킨다.

   2 - 1. 물리 메모리에 적재하기 위해서는 많은 시간이 소요되므로 해당 프로세스는 CPU 제어권을 뺐긴다.

   2 - 2. cpu register와 process state 및 program counter를 PCB에 저장한다.

3. Free-Frame List에서 비어있는 페이지를 찾는다.

4. Secondary Stroage에서 페이지를 읽어서 새로운 프레임을 physical memory 할당한다.

5. 기다리는 동안 CPU Core를 다른 process에게 할당한다(Context Swtich)

   5 - 1. disk i/o device controller에서 interrupt를 건다.

   5 - 2. 다른 process의 register와 process state를 저장한다.

6. 페이지를 메모리에 정상적으로 로드 했다고 page table의 valid-invalid bit를 valid로 바꿔준다.

   6 - 1. 프로세스를 ready queue로 이동시킨다.

7. 다시 CPU를 할당 받았을 때 PCB에 있던 값을 복원시켜 중단되었던 명령을 수행한다. (Instruction Restart)

Pure Demad Paging이라는 것은 요청을 하지 않으면 절대로 페이지를 가져오지 않고, 오로지 요청할 때만 페이지를 가져오는 것이다.
(-> 처음에 단 하나의 페이지도 로딩 하지 않고, Page Fault가 일어날 때 그 때 그 때 로딩한다.)

또한, Demand Page는 하드웨어 지원이 반드시 필요하다.

1. Page Table

   : Valid or Invaliid bit

2. Secondary Memory (Swap Space)

   : 메인 메모리에 존재 하지 않는 페이지를 저장하는 공간.
   : SSD가 빠른이유? (Swap이 엄청 빠르기 때문!!)

- Locality of Reference

참조 지역성

동일한 값 또는 해당 값에 관계된 스토리지 위치가 자주 액세스되는 특성으로, 지역성의 원리(principle of locality)라고도 한다.

참조 지역성에는 3 가지 기본형이 있다.

• 공간(spatial) 지역성
  • 특정 클러스터의 기억 장소들에 대해 참조가 집중적으로 이루어 지는 경향으로, 참조된 근처의 메모리를 참조한다.
• 시간(temporal) 지역성
  • 최근 사용되었던 기억 장소들이 집중적으로 액세스되는 경향으로, 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높다.
• 순차(sequential) 지역성
  • 데이터가 순차적으로 액세스되는 경향으로, 프로그램 내의 명령어가 순차적으로 구성되어 있다는 것이 대표적인 경우이다. 공간 지역성에 편입되어 설명되기도 한다.

- Free Frame List

Linked List로 Frame을 관리하는 Pool이다.

page fault가 발생했을때 second stroage에서 memory로 스왑핑할때, 이 free frame list에서 가져온다.

반드시 stack or heap segment로 관리가 되어야 한다.

- Instruction Restart

page fault가 일어났을 때 가장 먼저 O/S에 trap을 걸어서 wait queue에 보내버린다, 그리고 마지막 단계에서 page in이 끝나면 다시 깨운다.

그러면 그 과정에서 Context Switch가 일어나는데 restart를 할 때 같은 상태 같은 위치에서 restart 해줘야 하는데, 그 때까지 페이지 테이블은 괜찮을까?
(중간 중간에 다른놈들도 Context Switch로 인한 페이지 인/아웃을 하면 어떻게 될까?)

그래서 page table을 잘 관리해야 한다. Fetch 할때 조심!!

- EAT

Effective Access Time with page faults

그러면 demand page의 퍼포먼스를 계산해보자.

• p (0 <= p <= 1)
  : page fault가 발생할 확률

• ma

  : memory access time

• EAT = (1 - p) * ma + p * page fault time

- page fault service time의 세 가지 주요 작업 요소

1. service the page-fault interrupt

2. read in the page

   : page를 disk로부터 읽어와 frame에 적재 (I/O)

   : 가장 많은 시간이 소요된다.

3. restart the process

- Demand Paging 장점

1. 당장 필요한 페이지만 메모리에 적재하기 때문에 메모리 사용량이 감소한다.
2. 프로세스 전체를 메모리에 올리는데 들었던 입출력 오버헤드도 감소한다.
3. 시스템이 더 많은 프로세스를 수용할 수 있게 해준다.
4. 프로그램이 물리적 메모리 용량의 제약에서 벗어날 수 있게 해준다.