Virtual Memory
지난 시간
- 물리메모리의 주소변환은 OS가 관여하지 않음
- Virtual Memory 기법은 전적으로 OS가 관여하고 있음
Demand Paging
요청이 있을 때 page를 메모리에 올림
Memory에 없는 Page의 Page Table
- page fault = 1번 page 메모리에 없음
- Disk , Packing store , Swap area = 원기둥
Page Fault
- invalid 에 접근하면 MMU (주소 변환 처리해주는 하드웨어)가 trap 발생 시킴
물리적인 메모리의 주소 변환은 운영체제가 관여하지 않는다. 그에 반에 virtual memory 기법은 전적으로 운영체제가 관리하고 있다.
가상 메모리라는 것은 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이다. 가상 메모리는 물리 메모리로부터 논리 메모리를 분리해, 메인 메모리를 균일한 크기의 저장 공간으로 구성된 엄청나게 큰 배열로 추상화 시켜준다. 이 기법을 통해 프로그래머는 메모리의 크기 제약으로부터 자유로워지고, 공유 메모리 구현도 가능하게 해주며, 프로세스 생성을 효율적으로 처리할 수 있는 기법도 제공한다.
그러나 이러한 가상 메모리는 구현하기 어렵고, 만약 잘못 사용하게 되면 성능이 현저히 저하될 수 있다.
Demand Paging
말 그대로 요청(demand)이 있으면 그 페이징을 메모리에 올리겠다는 것(페이징 기법을 사용한다고 가정. 실제에서도 페이징 기법이 많이 사용됨).
즉, 실제로 필요할 때 page를 메모리에 올리는 것 (접근되지 않은 페이지는 무리 메모리로 적재되지 않음)
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid/Invalid bit의 사용
- Invalid의 의미 - 사용되지 않는 주소 영역인 경우 / 페이지가 물리적 메모리에 없는 경우
- 유효 비트 - 해당 페이지가 메모리에 있다는 의미
- 무효 비트 - 해당 페이지가 유효하지 않거나(즉, 가상 주소 공간상에 정의되지 않았거나) 유효하지만 보조저장장치에 존재한다는 것
- 처음에는 모든 page entry가 invalid로 초기화
- address traslation 시에 invalid bit이 set 되어 있으면 "page fault"(요청한 페이지가 메모리에 없는 경우) → CPU는 자동으로 운영체제에게 넘어감(page fault trap이 걸린다라고 표현)
메모리에 없는 page의 page table
- 하나의 프로그램을 구성하는 논리적인 메모리는 여러개의 페이지들로 구성
- 페이지 테이블을 통해 주소 변환 정보가 저장됨
- 디스크에서는 swap area를 볼 수 있음
- 처음 프로그램이 구동이 되면, page table에는 모두 invalid bit만 올라가 있을 것임
- 당장 필요한 페이지는 demand paging에 의해 물리 메모리에 올라가 있고, 그렇지 않은 것들은 backing store에 올라가 있음
- A, C, F는 현재 쓰이고 있기 때문에 valid bit으로 올라가 있지만, 나머지 페이지들은 backing store에 내려가 있기 때문에 invalid bit으로 되어있음
- 위 그림은 어떤 페이지를 무효로 설정하는 것은 그 페이지를 접근하기 전까지는 어떠한 영향도 끼치지 않는 다는 점을 보여줌
Page Fault
Invalid page를 접근하면, MMU(주소 변환 처리해주는 하드웨어)가 trap을 발생시킴(= page fault trap)
Kernel mode로 들어가서 page fault handler가 invoke됨
- 다음과 같은 순서로 page fault를 처리한다.
- Invalid reference? (eg. bad address, protection violation) → abort process
- Get an empty page frame. (빈 페이지가 없으면? 뺏어온다 : Replace)
- 해당 페이지를 disk에서 memory로 읽어온다.
- disk I/O가 끝나기까지 이 프로세스는 CPU를 선점당함(block)
- disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
- ready queue에 process를 insert → dispatch later
- 이 프로세스가 CPU를 잡고 다시 running
- 아까 중단되었던 instruction 재개
Steps in handling a page fault
- 메모리 reference가 있었는데, 주소 변환을 하고자 하니 invalid 표시가 되어 있었음.(이 페이지가 메모리에 올라와 있지 않음)
- trap이 걸려, CPU가 자동으로 운영체제에게 반환
- 운영체제는 backing store에 있는 페이지를 물리적인 메모리에 올려 놓음
- 만약 빈 프레임이 없으면, 쫓아내서라도 물리적인 메모리에 올려놓음
- 올려놓는 작업이 다 끝나면, 해당하는 프레임 번호를 엔트리에다 적어놓고, invalid였던 것을 valid로 바꿈
- CPU를 다시 얻어서 주소 변환을 하면, valid로 되어있고, 주소변환을 정상적으로 해서 원하는 물리적인 메모리의 프레임에 접근
Performance of Demand Paging
- page fault가 발생했을 때, disk로 접근하는 것은 굉장히 오래 걸리는 작업
- page fault가 얼마나 크게 났는냐에 따라 메모리 접근 시간이 달라짐
- 대부분의 경우는 page fault가 일어나지 않고, 메모리로 부터 직접 주소변환을 할 수 있음 : (1−p)
- 그 외의 경우에 page fault가 발생하여 disk 접근을 해야하는 것(overhead가 큼) : p
Free Frame이 없는 경우
Page Replacement
- OS가 하는 업무
- 요구 페이징의 기본
- 어떤 frame을 빼앗아올지 결정해야 함
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
Replacement Algorithm
- page-fault rate을 최소화하는 것이 목표(가급적 0에 가깝도록)
- 알고리즘의 평가 - 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사(페이지 폴트 발생 횟수를 계산하여 평가)
- reference string(메모리 주소의 나열)의 예 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Page Replacement
- 희생자(victim)가 선정되면, 디스크로 쫓아버림. (만약, 희생자가 내용이 변경됐다면, backing store에 변경된 내용을 써줘야함.)
- 쫓겨난 페이지에 대해서는 invalid로 바꿔줌
- 새로운 메모리를 물리적 주소에 올려줌
- 해당 메모리를 valid로 바꿔줌
Optimal Algorithm
- 알고리즘 중에서 제일 좋은 알고리즘으로, page fault를 가장 적게 함
- 하지만, 시스템에서는 미래를 알 수 없음. optimal algorithm은 미래를 다 알고 있다고 가정한 상태에서 실행하기 때문에, 실제 시스템에서는 사용될 수 없음.
- Offline optimal algorithm이라고도 함
- 가장 먼 미래에 참조되는 page를 replace 하는 방법으로, 5번 요청이 되었을 때, 메모리에 없기 때문에 page fault가 나고 4가 가장 먼 미래에 참조될 것이라는 걸 알기에 쫓겨나는 것(replace)을 볼 수 있음
- 빨간색 - page fault 가 된 경우, 연보라색 - 메모리에서 직접 참조가 된 경우
- 아무리 좋은 알고리즘을 만들어도 optimal algorithm보다 성능이 좋을 수는 없음
- 알고리즘은 실제 구현이 어려움
FIFO(First In First Out) Algorithm
- 가장 간단한 페이지 교체 알고리즘
- 어떤 페이지를 교체해야 할 때, 메모리에 올라온 지 가장 오래된 페이지를 내쫓음
- FIFO Anomaly - 메모리 frame 수를 늘렸는데, 오히려 page fault수가 늘어나는 (기이한) 현상
LRU(Least Recently Used) Algorithm
- 가장 오랜 기간 동안 사용되지 않은 페이지를 교체하는 것
- 페이지마다 마지막 사용 시간을 유지
- 가장 오래전에 참조된 것이 3번 이므로, 3번을 지우는 것을 확인
- 가장 먼저 들어온 1번을 지우는 FIFO 알고리즘과의 다른 점 확인
LFU(Least Frequently Used) Algorithm
- 참조 횟수가 가장 적은 페이지를 교체하는 것
LRU와 LFU 알고리즘 예제
- LRU 알고리즘은 현재 시점부터 마지막 시점까지를 보았을 때, 4번 페이지가 가장 최근에 쓰였으므로 우선순위가 제일 높고, 1번 페이지가 제일 오래 전에 참조되었기 때문에 1번 페이지를 삭제하려고 할 것
- LFU 알고리즘은 참조횟수가 가장 높은 1번 페이지를 최우선시하고, 4번 페이지가 참조횟수가 제일 적으므로 4번 페이지를 삭제함
LRU와 LFU 알고리즘의 구현
- LRU 알고리즘은 참조 시간의 순서에 따라 줄세우기를 하며, 링크드 리스트 형태로 운영체제가 시간 순서를 관리하게 됨. 만약 어떤 페이지가 들어오거나 재참조를 하게 되면, 무조건 참조시점이 제일 최근 시점에 쓰인 것으로 제일 아래쪽으로 보내면 됨
- LRU 알고리즘은 시간 복잡도가 O(1)로 쫓아내기 위해 비교 연산이 필요하지 않다는 것을 의미함
- LFU 알고리즘은 한 줄로 줄세우기가 애매함. 또, 한 줄로 줄세우기 하면, O(n)의 시간이 소요됨
LFU 알고리즘
- 때문에 LFU 알고리즘은 Heap으로 구현을 하고, 이로 O(log n)의 시간으로 줄일 수 있음. 이로써 참조횟수가 적은 것이 들어와도 자리바꿈이 수월하게 이루어질 수 있음
