[OS] 가상메모리(Virtual Memory)

가상 메모리(Virtual Memory)

메모리가 실제 메모리보다 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에 착안하여 고안된 메모리 기법이다.

프로그램에서 코드와 데이터는 실행되기 위해서 메모리에 존재하지만, 모든 프로그램이 항상 사용되는 것은 아니다. 

ex) Error Code, unusual routines, large data structures

프로그램을 부분적으로 실행할 수 있다면 다음과 같은 장점이 있다.

• 프로그램은 더 이상 물리적 메모리의 한계에 제약받지 않는다.
• 각각의 프로그램들은 실행 중에 적은 크기의 메모리를 가진다.
• 프로그램을 메모리에 올리고 스왑 하는 데 필요한 I/O가 적어진다.

가상 메모리는 한정된 크기의 메모리를 여러 프로세스가 동시에 사용할 수 있게 하여 마치 무한한 메모리가 있다고 느끼게 한다.

운영체제는 가상 메모리 기법을 통해 프로그램의 논리적 주소 영역에서 필요한 부분만 물리적 메모리에 적재하고, 직접적으로 필요하지 않은 메모리 공간은 디스크에 저장하게 된다.

 

요구 페이징(Demand Paging)

요구 페이징은 프로세스가 실행되는 동안 실제로 필요한 페이지만 메모리에 가져오고, 나머지는 디스크에 저장하는 기법이다.

요구 페이징 시스템에서 Lazy swapper와 Pager가 페이지 스왑을 하는 데 사용되는데, Lazy swapper는 페이지 단위로 스왑하고 Pager는 개별 페이지를 처리한다.

프로그램이 실행 중에 어떤 페이지가 필요하다고 판단되면, 해당 페이지를 디스크에서 메모리로 가져오는 작업을 Swap-in이라 한다.

반대로 메모리가 부족한 상황에서 메모리에 저장된 프로세스나 프로그램의 일부를 디스크로 내보내는 작업을 Swap-out이라 한다.

요구 페이징 기법을 사용할 때는 페이징 교체 알고리즘을 통해 어떤 페이지를 Swap-in, Swap-out 할지 결정한다.

Valid-Invalid bit

페이지가 메모리에 올라와 있는 알기 위해서 비트를 저장하는데 이를 Valid-Invalid bit이라 한다.

페이지 테이블 엔트리의 invalid bit가 0 또는 false로 설정되어 있으면 해당 페이지는 메모리에 올라와있고 유효한 상태라는 것을 의미한다.

페이지 테이블 엔트리의 invalid bit가 1 또는 true로 설정되어 있으면 해당 페이지는 메모리에 없거나 현재 무효한 상태라는 것을 의미한다. 프로세스가 이 페이지에 접근하려고 할 때, Page Fault가 발생하고, 이때 운영체제는 해당 페이지를 디스크에서 메모리로 가져와서 페이지 테이블 엔트리를 유효한 상태로 변경한다.

 

Page Fault

Page Fault는 프로세스가 특정 페이지에 접근하려고 할 때, 해당 페이지가 메모리에 존재하지 않을 때 발생한다.

Page Fault를 처리하는 방법은 다음과 같다.

1. 운영체제가 페이지 테이블을 참조하여 프로세스가 접근하려는 페이지가 메모리에 있는지 확인한다. 없을 경우 Page Fault를 발생시키고 해당 프로세스를 일시 중단한다.
2. 디스크에서 해당 페이지를 찾아 물리 메모리의 free frame에 저장한다.
3. 페이지 테이블에 변경 사항을 반영한다.
4. Page Fault 처리가 완료되면 프로세스는 중단된 지점부터 다시 시작한다.

요구 페이징의 단계

1. os가 프로세스에 trap을 건다.
2. user register랑 process state를 저장한다.
3. trap이 page fault인지 확인한다.
4. page reference가 invalid 한 지 확인하고, 페이지가 디스크에 어느 위치에 존재하는지 결정한다.
5. 디스크에서 물리메모리의 free frame에 해당 페이지를 읽어온다
6. 페이지를 디스크에서 읽어오는 동안 cpu는 다른 프로세스가 다른 작업을 할 수 있도록 할당한다.
7. 디스크 I/O가 끝나면 interrupt 받는다.
8. 현재 사용하던 다른 프로세스의 register, process state를 저장한다.
9. 디스크에서 온 interrupt 인지 확인한다.
10. 해당 페이지가 메모리에 올라왔기 때문에 Page table을 수정하고 bit를 valid로 바꾼다.
11. 중지되었던 원래 프로세스를 wait 상태로 바꿔 cpu에 다시 할당받기를 기다린다.
12. 사용자 레지스터, 프로세스 상태 및 새 페이지 테이블을 복원한 다음 중단된 명령을 다시 시작한다.

 

페이지 선택 전략

Pure demand paging : 필요한 페이지만 메모리로 가져오는 전략

• 초기 메모리 요구량이 적어 메모리 절약이 가능하고 메모리 효율성을 높인다.
• 처음 접근하는 모든 페이지는 Page Fault가 발생하기 때문에 이로 인한 disk I/O가 필요하다.

Prepaging : 일부 페이지를 미리 메모리에 가져오는 전략

• 일부 페이지를 사전에 메모리에 적재해 Page Fault의 발생 가능성을 줄여 초기 실행 시간을 단축하고 성능을 향상한다.
• Page Fault가 발생하여 페이지를 디스크에서 가져올 때 그다음 페이지도 미리 가져온다.
• 미리 메모리에 적재한 페이지가 사용되지 않을 수 있으며, 메모리 낭비가 발생할 수 있고. 어떤 페이지를 사전에 로드할지 결정하기 어려운 경우가 있다.

Request paging : 사용자가 필요한 페이지를 알려주는 전략

Copy-on-Write : 부모와 자식 프로세스가 메모리 내의 동일한 페이지를 사용하게 하는 전략

• 부모 프로세스가 fork()를 하여 자식 프로세스를 생성하면 자식 프로세스는 부모 프로세스의 페이지를 참조한다.
• 한 프로세스가 공유된 페이지를 수정하려고 할 때 해당 페이지의 복사본이 메모리에 새로 저장된다.

프로세스가 서로 페이지를 공유하는 상황

페이지 수정으로 인한 복사 페이지 생성

 

페이지 교체

물리 메모리의 프레임이 꽉 찰 경우 새로운 페이지를 저장하기 위해서는 페이지 교체가 필요하다.

빈 프레임이 없다면 페이지 교체 알고리즘을 통해 교체할 페이지를 선택하고 새로운 페이지와 교체한다.

이때 페이지의 dirty bit가 1일 경우 disk에 저장할 때 write 해준다.

페이지 교체 알고리즘

FIFO 알고리즘

FIFO 알고리즘은 가장 먼저 메모리에 들어온 페이지를 교체하는 알고리즘이다.

다음은 3개의 frame이 있을 때 FIFO 알고리즘이 적용되는 방식을 나타낸다.

FIFO 알고리즘에서 frame을 3개에서 4개로 늘렸을 때 Page Fault가 감소할 것이라 예상되지만 다르게 동작할 수 있다.

frame의 수가 늘어났는데도 Page Fault가 더 발생할 수 있는데 이 현상을 Belady’sAnomaly 라 한다.

 

Optimal 알고리즘

Optimal 알고리즘은 가장 먼 미래에 사용될 페이지를 예측하여 교체하는 알고리즘이다.

가장 효율적으로 페이지 교체를 할 수 있는 방식이지만 미래의 페이지 참조를 예측하는 것은 매우 어렵기 때문에 실제로 사용되지는 않는다.

 

LRU 알고리즘

LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 내보낸다.

페이지가 참조된 시간 순서를 구현하기 위해서 2가지 방법이 있다.

Counter implement

• 페이지가 언제 참조되었는지 시간을 저장하는 counter를 사용한다.
• 페이지 교체가 필요할 때 counter가 가장 작은 페이지를 찾아 교체한다.

Stack implement

• 페이지 번호를 double link로 이어 stack에 저장한다.
• 새로 페이지가 참조되면 stack의 top으로 이동하고,  페이지 교체가 필요할 때는 스택의 bottom에 있는 페이지를 내보낸다.

 

페이지 프레임 할당

각각의 프로세스에 물리 메모리의 프레임을 몇 개 할당할 것인지에 대한 문제이다.

Fixed Allocation

• Equal allocation : 각각의 프로세스마다 동일한 수의 프레임을 할당한다.
• Proportional allocation : 각각의 프로세스의 크기의 비율에 따라서 프레임을 할당한다.

Priority Allocation : 프로세스의 크기 대신 다른 우선순위를 비교하여 프레임을 할당한다.

 

프로세스가 페이지를 교체할 때  할당받은 프레임 범위에서 선택하는 방식과 프레임 전체에서 선택하는 방식이 있다.

Global Allocation : 프로세스는 교체할 프레임을 모든 프레임 집합 안에서 선택한다. 한 프로세스가 다른 프로세스의 프레임을 할당받을 수 있다.

Local Allocation : 각각의 프로세스는 할당받은 프레임 집합 안에서 프레임을 선택해야 한다.