가상 메모리
프로그램이 실행되기 위해서는 물리 메모리에 올라와 있어야 하지만 프로그램 전체가 한꺼번에 메모리에 늘 올라와 있어야 하는 것은 아니다.
- 다음과 같은 예시가 있다.
- 잘 발생하지 않는 오류 상황을 처리하는 코드들은 거의 실행되지 않는다.
- array, list, table 등의 사용하지 않는 공간
- 프로그램 내 거의 사용하지 않는 옵션들
이점
프로그램의 일부분만 메모리에 올려놓고 사용한다면 다음과 같은 이점을 얻을 수 있다.
- 물리 메모리 크기에 제약받지 않고 더 큰 가상 주소 공간을 가정하고 프로그램을 만들 수 있다.
- 프로그램의 메모리 할당 공간이 줄어들어 더 많은 프로그램을 동시에 실행할 수 있다. 이 때, 응답 시간은 늘어나지 않고 CPU 이용률과 처리율을 높일 수 있다.
- 프로그램을 메모리에 올리고 swap 하는 I/O 회수가 줄어들어서 프로그램을 더 빨리 실행시킬 수 있다.
요구 페이징 (Demand Paging)
디스크에서 메모리로 프로그램을 적재할 때, 프로그램 실행 중 필요할 때만 페이지를 메모리에 적재하는 방식이다. 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.
물리메모리에 적재되지 않은 페이지는 backing storage에 저장된다
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 수용자 수용 가능
Valid/Invalid bit
- 무효, 유효 비트를 두어 각 페이지가 메모리에 존재하는지 표시한다.
유효 비트: 페이지가 메모리에 적재된 상태무효 비트: 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 page entry가 invalid로 초기화
- 참조하려는 페이지가 무효로 세팅되어 있는 경우를
페이지 부재=page fault가 일어났다고 한다.
page fault 의 오버헤드
- 메모리에 공간이 없으면 페이지를 swap out 해야함
- 페이지를 메모리에 올려야 함
- OS & HW 의 작업(valid 표시, 페이지 프레임 번호 작성 등)이 끝나고 CPU를 얻었을 때 restart 해야 함
페이지 교체
- 페이지 부재가 발생하면 해당 페이지를 디스크에서 메모리로 가져와야 한다. 이 때, 메모리에 빈 프레임이 없을 경우가 있다.
- 이 경우 메모리에 올라와 있는 페이지를 디스크로 쫓아내고 메모리에 빈 공간을 확보하는 작업을 해야한다. 이 작업을
페이지 교체라고 한다
페이지 교체 방법
- invalid page 를 접근하면
MMU(주소 변환 HW)가 trap을 발생시킴 (page fault trap) -> CPU 가 자동적으로 process에서 OS로 넘어감 - Kernel mode로 들어가서 page fault handler가 invoke
- 다음과 같은 순서로 page fault 처리함
- Invalid reference 인지 확인하는 절차 (잘못된 주소, 접근권한에 대한 침범이면 강제로 종료)
- get an empty page frame (없으면 뺏어온다 : replace)
- 해당 페이지를 disk에서 memory로 읽어옴
- disk I/O가 끝나기까지 프로세스는 CPU를 preempt 당함 (block)
- disk read 가 끝나면 page tables entry 기록, vaild/invalid bit = "valid"처리하고 해당하는 페이지 프레임 번호를 적음
- ready queue에 process를 insert -> dispatch later
- 이 프로세스가 CPU를 잡고 다시 running
- 아까 중단되었던 명령 재개
페이지 교체 알고리즘
- Page fault rate 를 최소화 하는 것이 목표
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
- 동일한 페이지가 여러번 나갔다가 다시 들어오지 않도록
FIFO(First In First Out)
- 가장 먼저 들어온 페이지를 페이지 폴트가 발생하면 교체한다.
- 동일한 페이지가 계속 참조되는게 아니라면 페이지 폴트가 지속적으로 발생한다.
LFU(Least Frequently Used)
- 참조 횟수가 가장 적은 페이지를 지운다
- 최근에 교체된 페이지가 교체될 가능성이 높다.
- 페이지 참조에 대한 횟수를 기록하는 오버헤드가 발생한다.
- 최저 참조 횟수인 page가 여러개가 있는 경우 page 중 임의로 선정
LRU(Least Recently Used)
- 가장 오래전에 참조되었던 것을 지움
- 페이지 참조 시간을 기록하는 오버헤드가 발생한다.
OPT(Optimal Replacement)
- 앞으로 오랫동안 사용되지 않을 페이지를 교체한다.
- 미래를 볼 수 있다는 가정으로 동작, 가장 먼 미래에 참조될 페이지를 교체함
- 제일 이상적이지만 앞으로 사용할 페이지를 미리 알아야 한다 -> 불가능
NUR(Not Used Recently)
- LRU 와 비슷한 알고리즘으로 시간 기록 오버헤드를 줄일 수 있다.
- 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 가능성이 높다는 것을 전제로 한다.
- 각 페이지마다 두 개의 비트
참조 비트,변형 비트를 사용한다참조 비트: 페이지가 참조되지 않았을 때 0, 호출 됐을 때 1 (모든 참조 비트를 주기적으로 0으로 변경)변형 비트: 페이지 내용이 변경되었을 때 1, 변경되지 않았을 때 0- 우선 순위 : 참조 비트 > 변형 비트
참고
내 머릿속 지우개