Virtual Memory Management

김세영·2021년 6월 11일
OS
0

Virtual Memory

DRAM의 크기가 제한되어 있기 때문에, 동시에 실행할 수 있는 프로세스의 개수가 제한되어 있다.
동시에 실행 가능한 프로세스의 개수를 늘리기 위해 Virtual Memory를 도입하게 된다.

Memory Use Pattern

프로그램이 실행될 때, 많은 부분이 접근되지 않거나 실행되지 않는다.

1. 일부분의 코드만 실행

void main()
{
    ...
    if (i == 0)
        a();

    else if (i == 1)
        b();

    else 
        c();
   
    ...
    exception(e == 0)
        handle_error();
}

위의 코드에서 if문은 3개의 분기 중 오직 하나만 선택되게 된다.
또한 exception에서 e != 0일 때에는, handle_error()가 실행되지 않는다.

2. 제한된 메모리 접근

int a[1000][1000];에서, 만약 0 <= i, j <= 100에 해당하는
데이터만 사용하게 된다면, 나머지 공간들은 전혀 사용되지 않는다.

위의 경우에서 프로그램의 일부분만이 사용되기 때문에,
사용되지 않는 부분을 굳이 메모리에 올려 사용할 필요가 없다.
이를 해결하기 위해 Demand Paging기법이 도입되었다.

Demand Paging

위에서 설명한 바와 같이, 실행에 필요한 코드 / 데이터만을 메모리에 올려 실행하는 것을 Demand Paging이라 한다.
Demand Paging의 장점은 다음과 같다.

  • 메모리 용량이 500MB인 컴퓨터에서 전체 용량이 1GB인 프로그램을 실행시킬 때,
    실행에 필요한 데이터만을 메모리에 올려 실행을 가능하게 해 준다.
  • DRAM의 빈 공간이 늘어나, 동시에 실행 가능한 프로그램의 개수를 증가시킬 수 있게 해 준다.
  • Load, Swap 등 I/O 진행 시 용량이 적기 때문에 그만큼 실행 시간을 빠르게 해 준다.

Executable & Virtual Memory

Executable (실행 파일)

실행 파일은 여러 Page로 나누어 Disk에서 관리되고 있다.

Virtual Address Space

Virtual Address Space는 프로그램 실행 시 할당된다.

Executable - Virtual Memory

프로그램이 실행될 때, Disk의 Executable과 Virtual Address Space가 Mapping된다.
이 때 Mapping만 해주고 Memory(DRAM)에 적재하진 않는다.
Mapping 정보는 Virtual Address Space의 공간에 저장해놓는다.

Page Fault

Virtual Memory에 있는 Page를 접근하려고 해당 Page Table Entry를 참조할 때,
해당하는 Page가 Physical Memory에 없는(Valid-Invalid Bit = i) 현상을 Page Fault라 한다.

이 때 Page Fault Exception이 발생하게 된다.

Page Fault Exception

  • 1. CPU가 Page Fault Exception 이벤트를 발생시킨다.
  • 2. Kernel에 Exception을 전달한다.
  • 3. Kernel은 Page Fault Handler을 실행시킨다.
  • 4. Virtual Memory에 정의되어 있는 함수를 실행시킨다.
  • 5. 호출된 함수에서는 먼저 Page Fault의 원인을 분석하여,
    • (1) Disk에서 코드 또는 데이터를 불러온다.
    • (2) 프로세스를 종료한다.

5-(1)의 경우 다음 작업을 실행한다.

  • 1. 현재 실행되고 있는 프로세스를 일시정지한다.
  • 2. Exception을 발생시킨다.
  • 3. OS는 이를 받아 Disk에서 해당 페이지를 검색한다.
  • 4. 찾은 페이지를 DRAM의 빈 프레임에 적재한다.
  • 5. 적재된 프레임과 Page를 비교하여 Page Table에 등록하고, valid 상태로 변경한다.
  • 6. 일시정지된 프로세스를 시작시킨다.

5-(2)는 다음과 같은 경우에 발생한다. (예시)

  • 1. 코드상에서 OS가 할당된 주소를 참조한다.
  • 2. 값을 변경하려고 시도할 때, Page Table의 상태가 invalid이다.
  • 3. Page Fault Exception을 발생시켜 Kernel에 넘긴다.
  • 4. Kernel은 Page Fault Handler를 실행하여 원인을 분석한다.
  • 5. 이 때 발생한 Exception은 DRAM상에 할당할 수 없는 주소에 접근한 것이기 때문에
    SIGSEGV 시그널을 프로세스에게 보낸다.
  • 6. 프로세스는 이 시그널을 받으면
    화면에 Segmentation Fault 메시지를 띄운 후 프로세스를 강제 종료한다.

Performance of Demand Paging

p: Page Fault Rate, ma: Memory Access Time이라 할 때,

Effective Memory Access Time = (1−p)×ma+p ×(1 - p) \times ma + p\ \times Page Fault Time

이 때 Page Fault Time은 다음과 같다.

  • Interrupt 발생시켜 Handler을 실행시키는 시간
  • 해당 데이터를 디스크에서 불러오는 시간
  • 프로세스를 다시 실행시키는 시간

위 3개의 시간이 Page Fault Time을 구성한다.
역시 디스크에서 불러올 때가 시간이 제일 오래 걸린다.

Page Replacement

메모리가 모두 사용되고 있는 경우, Page Fault가 발생하여 디스크에서 새로운 데이터를
DRAM에 적재해야 하는 경우, 다음과 같은 방법을 사용할 수 있다.

  1. Process Termination
    Page Fault가 발생하면 프로세스를 종료시킨다.
    이는 새로운 데이터를 적재하지 못하므로 사용되지 않는다.

  2. Process Swaping
    다른 프로세스가 사용중인 Page를 모두 Disk에 내보내고 (Swap out)
    나중에 해당 프로세스가 실행될 때 다시 Page를 불러오는 방식 (Swap in)
    프로세스가 페이지를 많이 사용중인 경우 I/O 시간이 오래 걸리므로 거의 사용되지 않는다.
    메모리가 극도로 부족할 때 최후의 방법으로 사용

  3. Page Replacement <<<
    Page Fault가 발생하면, Physical Memory에서 교체할 페이지를 찾는다. (Victim Page)
    Victim을 Disk에 백업하고, Victim에 해당하는 Page Table Entry의 상태를 invalid로 전환한다. (Page out)
    그 후 불러올 데이터를 Disk에서 Physical Memory에 적재하고, 상태를 valid로 전환한다. (Page in)

Swap Space

Page out시에 Disk에 해당 페이지를 저장하는 공간이 존재한다.
이 공간을 Swap space라 하고,
리눅스에서는 보통 DRAM size * 2로 설정한다.

Modify Bit (in Page Table)

Disk에서 불러와 DRAM에 적재한 데이터가 한 번도 값이 쓰여지지 않았을 때,
이를 Clean bit로 표현한다.

반대로 Disk에서 불러온 데이터의 값이 DRAM상에서 변경되었을 때,
이를 Dirty bit로 표현한다.

Clean일 때는 Page Replacement 시에 Disk에 백업을 하지 않아도 되지만,
Dirty일 때는 DRAM에 있는 데이터가 최신 데이터이므로 Disk에 백업해야 한다.

Page Replacement Algorithm

Page Fault가 발생했을 때, 어떤 프레임을 선택하여 교체할 지(victim)
결정하는 방법을 Page Replacement Algorithm이라 한다.

이 때 Page Fault가 가장 적게 발생하도록 프레임을 결정하는 것이
좋은 알고리즘의 조건이다.

reference string: 일련의 메모리 접근 순서

FIFO Page Replacement

메모리에서 가장 오랫동안 머물렀던 프레임을 victim으로 설정하는 방법

Optimal Page Replacement

reference string에서 가장 먼 미래에 사용될 프레임을 victim으로 설정하는 방법
현실적으로 reference string은 아무도 알 수 없으므로 사용할 수 없다.

LRU Page Replacement

Lease Recently Used의 줄임말로, Optimal 알고리즘을 흉내낸 것이다.

가까운 과거에 접근된 페이지는 가까운 미래에 접근될 가능성이 높고,
먼 과거에 접근된 페이지는 먼 미래에 접근될 가능성이 높다는 이론에 기초
완벽하게 Optimal 알고리즘을 대체할 순 없지만,
가장 효율적인 방법으로 현재 많이 사용되는 방법이다.

LRU-Approximation Page Algorithm

Page Table에 reference bit를 추가시켜,
MMU에서 해당 페이지를 참조하면 bit를 1로 전환시킨다.
하드웨어적으로 비트만 바꿔주기 때문에, 커널은 어떠한 순서대로
페이지가 접근되었는지 알 수 없다.

Second-Chance Algorithm

Page-out Daemon

Page out Daemon은 커널에서 주기적으로 실행된다.

메모리 부족이 매우 심하면 페이지를 자주 교체해야 하기 때문에,
더 자주 실행된다.

이 Daemon이 실행되는 주기 사이에 페이지가 접근되면,
가까운 과거에 사용되었다고 판단하여 가까운 미래에 접근될 가능성이 있다고 판단한다.

커널에서는 Page들을 circular linked list로 관리하는데,
Daemon이 실행되면 이 리스트를 head부터 nn개 탐색하여
해당 페이지의 reference bit를 검사한다.

이 검사 과정에서 reference bit가 0일 경우
가까운 과거에 접근되지 않았다고 판단하여,
이 페이지를 victim으로 설정해 교체해버린다.

reference bit가 1일 경우
가까운 미래에 접근되었다고 판단하여, 한 번의 기회를 더 주게 된다.
이 기회라는 것은 해당 페이지의 reference bit를 0으로 만들고,
메모리 상에서 놔두는 것을 의미한다.

nn개만큼 탐색 후 Daemon이 종료되고 다음에 다시 Daemon이 실행되면
이 실행 시에는 n+1n+1번 부터 다시 리스트를 탐색하여 동일한 작업을 수행한다.

이 방법이 실제 상용 OS에 탑재되어 있다.

Counting-Based Page Algorithm

Page table에 counter가 4바이트 정도 들어가게 된다.
페이지가 접근될 때 마다 counter가 1씩 증가한다.
페이지 교체를 할 시점에,

counter가 가장 적은 페이지를 교체하는 방법을 LFU(Least Frequently Used)라고 한다.
반대로, counter가 가장 많은 페이지를 교체하는 방법을 MFU(Most Frequently Used)라고 한다.

이 방법은 Table에 4바이트가 추가되었기 때문에, 실제로 사용되지는 않는다.

Thrashing

짧은 시간에 Page Fault가 급격히 많이 일어나는 현상을 Thrasing이라 한다.

위 그림처럼 메모리 용량이 적을 경우, 페이지 교체 시 Page Fault가 급격히 일어나게 된다.
프로세스 2의 페이지로 메모리가 꽉 찼을 때 프로세스 1이 실행되면,
Page Fault가 엄청나게 일어나게 되고, 이 과정이 반복되게 된다.
유일한 해결 방법은 메모리를 큰 걸로 교체하는 것이다.

profile
김세영
초보 iOS 개발자입니다ㅏ
이전 포스트

Memory Management - 2

다음 포스트

Synchronization

0개의 댓글