Virtual Memory
✔️ Virtual Memory
- 프로그램의 일부분만 메모리에 올려놓고 실행하는 기술
- 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한다
✔️ 장점
-
프로그램은 물리 메모리 크기에 제약받지 않게 된다
-
사용자 프로그램이 더 작은 메모리를 차지하므로 더 많은 프로그램을 동시에 수행할 수 있다
-
메모리를 스왑하는 횟수가 줄어든다
- 페이지 공유를 통해 파일이나 메모리가 둘 또는 그 이상의 프로세스들에 의해 공유될 수 있다
- ex) 시스템 라이브러리는 읽기만 허용되는 상태로 프로세스 주소 공간에 매핑될 수 있다.
- ex) 프로세스들이 메모리를 공유할 수 있다
Demand Paging
✔️ Demand Paging
- 페이지가 필요할 때 메모리에 적재하는 방법
- 한 번도 접근되지 않는 페이지는 물리 메모리에 적재되지 않음
✅ Locality of reference(참조 국부성)
대부분의 프로그램은 실행될 때 어느 한 특정 작은 부분만 한동안 집중적으로 참조하기 때문에 요구 페이징은 만족할 만한 성능을 보인다.
✅ Pager
- 프로세스 내의 개별 페이지들을 관리한다
- 프로세스 전체를 스왑하는 대신에 실제로 필요한 페이지들만 메모리에 읽어 온다
✅ 장점
사용되지 않을 페이지는 메모리로 가져오지 않음으로써 시간 낭비와 메모리 공간 낭비를 줄인다
✔️ Hardware
어느 페이지가 디스크에 있고 어느 페이지가 메모리에 올라와 있는지 구별할 필요가 있다. 이 때 하드웨어의 도움이 필요하다
✅ Page-table
valid-invalid 비트가 적용하여 해당 페이지가 메모리에 올라와 있는지 설정할 수 있다.
✅ Swap space
- 메인 메모리에 없는 모든 페이지들을 가지고 있는 공간
- 스왕 영역에서의 디스크 입출력은 파일 시스템에서의 입출력 보다 빠르다
- 파일 시스템보다 더 큰 블록을 사용하기 때문에
✔️ Page Fault Trap
프로세스가 메모리에 올라와 있지 않은 페이지에 접근하려고 하면 어떤 일이 발생할까?
- 메모리 참조가 valid 인지 invalid 인지 확인한다.
- invalid 페이지에 대한 참조라면(메모리에 적재되지 않은 페이지) 그 프로세스는 중단된다
- 자유 프레임을 찾는다
- 자유 프레임을 해당 페이지에 할당한다
- 디스크 읽기가 완료되면, 페이지 테이블을 갱신한다
- 트랩에 의해 중단되었던 명령어를 다시 수행한다
✅ Page fault 처리
페이지 폴트 처리는 크게 아래 3가지로 볼 수 있다.
- 페이지 폴트 인터럽트(트랩) 처리
- 디스크에서 페이지 읽기
- 프로세스 재시작
다른 작업보다 페이지를 읽는 시간이 압도적으로 시간이 많이 드는 작업이다
✅ Effective access time for demand page
- EAT = (1-p) ma + p (page fault time)
- ma = memory access time
- p = probability of page fault
- 페이지 폴트율을 낮게 유지하는 것이 상당히 중요하다
✔️ Pure demang Paging
어떤 페이지가 필요하지 않는한 절대로 페이지를 메모리에 가져오지 않는 방법
-
메모리에 페이지가 하나도 올라와 있지 않은 상태에서 프로세스를 시작할 수 있다
-
OS에서 명령어 포인터의 값을 프로세스의 첫 명령으로 설정하는 순간 이 명령이 메모리에 존재하지 않는 페이지에 있으므로 페이지 폴트가 발생한다
-
페이지가 적재되고 나면 프로세스는 수행을 계속하는데 프로세스가 사용하는 모든 페이지가 메모리에 올라 올 때까지 필요할 때마다 페이지 폴트가 발생한다
✔️ Issue
✅ [1] Instruction Restart
-
페이지 폴트가 발생하여 중단된 프로세스 상태(레지스터 상태)를 저장해두면 다시 이 프로세스를 시작할 때 정확히 같은 위치, 같은 상태에서 프로세스를 다시 수행할 수 있다.
-
만약 Page fault가 Instruction Fetch시에 발생했다면 Instruction를 메모리로 읽어 온 후 다시 수행을 진행하면 된다
-
만약 operand를 fetch하는 동안에 Page fault가 발생했다면 나중에 그 명령어를 다시 읽어오고 decode하여 operand를 fetch하면 된다
-
ex)
ADD A,B,C;- Fetch and decode the instruction(ADD)
- Fetch A
- Fetch B
- ADD A and B
- Store the sum in C
1번 or 2,3번 or 5번 step 에서 page fault가 발생했을 때, 1번 step부터 다시 재시작하면 된다
✅ [2] Free Frame List 관리
Page-in을 하기 위해서 OS는 free-frame list(a pool of free frames)를 관리해야 한다
✅ [3] Swap space 관리
스왑 영역의 입출력이 파일 시스템의 입출력보다 빠른점을 활용하여 스왑 영역을 활용할 수 있다. 스왑 영역을 활용한 여러가지 방법이 있다.
-
프로세스를 시작시킬 때 프로세스 파일 이미지를 스왑 공간으로 복사한 후 스왑 공간으로부터 demang paging을 함으로써 페이징 처리율을 얻는 방법
-
프로그램을 처음 시작시킬 때에는 파일 시스템으로부터 요구 페이징을 처리하지만 그 페이지들이 교체될 때는 스왑 공간에 페이지를 기록하는 방법
-
실행 파일(binary file)을 스왑 영역에 넣지 않고 스왑 영역의 크기를 줄이는 방법
✔️ Prepaging
Copy on write
-
과거에는 부모 프로세스의 페이지들을 실제 자식 프로세스에게 복사해줌으로 써 자식 프로세스의 주소 공간을 구성해주었다. 하지만 자식들이 만들어지자마자 곧
exec()시스템콜을 호출하면 부모 프로세스로부터 복사해온 페이지들이 쓸모 없게 된다. -
프로세스 생성 시간을 더 줄이기 위해
fork()시스템콜을 통해 프로세스를 생성할 때에는 페이지 공유와 비슷한 기법으로demand paging조차 생략 가능하다. -
수정될 수 있는 페이지만이 Copy on write 페이지로 표시할 수 있다.
Page Replacement Algorithm
멀티 프로그래밍 degree를 올리면 메모리 과할당이 발생한다. 더욱이 시스템 메모리는 페이지를 저장하는 용도로만 사용되는 것이 아니다. 입출력을 위한 버퍼도 상당한 양의 메모리를 사용한다.
✔️ Page Replacement
-
빈 프레임이 존재하지 않으면 OS는 victim frame을 선정하여 페이지 교체 알고리즘을 적용해야 한다
-
free frame이 없는 경우에는 디스크를 두 번 접근해야 한다(페이지 아웃 1번+ 페이지 인 1번)
-
이에 따라 page fault 처리 시간이 2배 소요되고 effective access time도 증가한다.
-
이러한 오버헤드는 변경 비트(modify bit or dirty bit)를 사용해서 감소시킬 수 있다.
- victim page가 변경되지 않았다면 디스크 상의 복사본이 변경되지 않았기 때문에 메모리 페이지를 디스크에 기록할 필요가 없어진다.
- 따라서 page out을 하는 것을 생략할 수 있다.
- 이 기법은 읽기 전용 페이지들에 적용할 수 있다.
✅ Page Fault Service Routine
-
디스크에서 필요한 페이지의 위치를 찾는다.
-
빈 프레임을 찾는다
a. 빈 프레임이 있으면 그것을 사용한다
b. 없다면 victim 프레임을 선정하기 위해 page replace algorithm을 적용
c. victim page를 디스크에 기록하고, 페이지 테이블을 수정한다
-
빼앗은 프레임에 새 페이지를 읽어오고 페이지 테이블을 수정한
다 -
page fault가 발생한 지점에서부터 프로세스를 계속한다
✔️ FIFO
메모리에 올라온지 가장 오래된 페이지를 교체한다
✅ 장점
간단하다
✅ 단점
자주 사용되는 페이지를 교체할 경우 page fault율이 증가한다
✅ Belady's anomaly
프로세스에게 할당되는 프레임 수를 증가했는데, 페이지 폴트율이 증가하는 현상
