Virtual Memory
가상메모리
가상메모리는 실제 메모리가 아닌 가상의 메모리를 관리하는 방법으로 멀티태스킹 운영체제에서 실제 메모리보다 큰 메모리를 제공 할 수 있다. 어느 시점에서 프로세스가 사용되는 부분은 일부분이며, 페이징이나 세그먼테이션 기법을 사용하여 실질적으로 필요한 부분만 메모리에 올려준다. 그러면 cpu는 연속적으로 메모리에 데이터를 가지고 있는것처럼 착각하게 된다.
Demanding Page
실제로 필요할때 page를 메모리에 적재하는것
현재 사용되는 부분은 물리 메모리에 올라와 있고 나머지 페이지는 backing store(swap area)에 존재한다.
페이지 테이블에 valid / invalid 비트를 두어 현재 물리 메모리에 올라와 있음을 체크한다. valid로 체크되어 있는 논리 주소는 바로 실제 주소로 변환된다. 하지만 invalid에 체크가 되어 있으면 MMU가 트랩을 발생 시키게 된다(“page fault”). 이때 운영체제는 backing store에서 해당 페이지를 momory로 읽어온다(disk io). 이 후에 페이지 테이블에서 해당 페이지를 valid로 체크하고 다시 프로세스에게 cpu를 이양하여 작업을 계속하게 된다.
Page replacement Algorithm
page fault가 발생하였는데 현재 메모리에 빈 공간이 없을 경우가 있다.
page replacement algorithm은 어떤 프레임을 내쫒을지 결정하는 알고리즘으로 page-fault rate를 줄이는 것이 관건이다.
Optiaml Algorithm (최적 알고리즘)
미래에 어떤 페이지가 올지 미리 알고 있는것을 가정한 것으로 가장 효율적인 알고리즘이다.
실제로는 불가능하기 때문에 성능 측정용으로 사용한다.
ex) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
| 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 4 | 4 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | ||
| 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
=> 6번 page fault 발생
FIFO Algorithm
먼저 들어온 것을 먼저 내쫒는다.
LRU (Least Recently Used) Algorithm
가장 오래전에 참조된 것을 내쫒는다.
과거에 그 페이지가 자주 참조되었는지는 고려하지 않는다.
가장 많이 사용되는 알고리즘 중 하나이다.
ex) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
| 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |
| 3 | 3 | 3 | 3 | 5 | 5 | 5 | 5 | 4 | 4 | ||
| 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 | 3 |
=> 8번 page fault 발생
LinkedList를 사용하여 구현하여 한줄로 세운다. 새로 참조되는 노드는 가장 줄의 가장 마지막으로 이동시키고 page fault가 발생할 경우 가장 첫 노드를 내쫒으면 된다. 시간복잡도 : O(1)
LFU (Least Frequently Used) Algorithm
가장 적게 참조된 것을 내쫒는다.
과거에 페이지의 빈도수를 계산하여 우선순위를 매긴다.
LinkedList를 사용하여 구현하게되면 새로 참조되는 노드부터 마지막 노드까지 비교하여 이동시키기 때문에 O(n)의 시간 복잡도가 된다. 하지만 Heap을 사용하여 구현하면 O(logN)가 된다.
Clock Algorithm
페이지들의 reference bit를 CirecularLinkedList로 구현하고 사용될때 1로 셋팅한다. bit를 1로 바꾸는 것은 하드웨어의 지원을 받고 0으로 바꾸는 것은 운영체제가 한다. 시계바늘이 한바퀴 돌면서 1인것은 0으로 셋팅하여 다음 방문까지 한번 더 기회를 주고 0인경우 페이지를 쫒아낸다. 내용이 수정된적이 있으면 modified bit(=dirty bit)을 1로 셋팅하여 1이면 디스크로 쫒아낼때 디스크 내용도 바꿔준다.
*reference bit (= access bit) : 1은 최근에 사용됨, 0은 사용되지 않음
클럭 알고리즘은 NUR(Not Used Recently), NRU(Not Recently Used)라고도 불린다.
Thrashing
메모리에 프로세스가 여러개가 올라와있는 경우 cpu utilization이 상승한다. 하지만 계속해서 프로세스가 메모리에 올라가게 되어 메모리의 한계치까지 도달하게 된다면 page-fault가 일어나기 시작한다. 결국에는 cpu가 일을 제대로 하지 못하고 페이지 교체만 처리하느라 cpu 이용률이 급격히 떨어지게 된다. 이와 같은 현상을 Thrashing 이라고 한다.
Locality of reference
프로세스는 특정 시점에서 일정 장소만을 집중적으로 참조한다.
집중적으로 참조되는 page들의 집합을 locality set이라고 한다.
다음은 스레싱을 방지하는 알고리즘이다.
Working-set Model
한꺼번에 메모리에 올라와 있어야 하는 page의 집합을 working-set이라고 한다.
Thrashing을 예방할 수 있다.
현재 시점에서 n개의 과거페이지를 워킹셋으로 두고 메모리에 유지한다. page-fault가 발생하여 쫒겨날 경우 통째로 쫒겨나고 메모리에 올라올경우 워킹셋을 보장할 수 있을때만 통째로 올라온다.
PFF (Page Fault Frequency)
프로세스가 처음 시작되면 페이지폴트가 계속해서 발생하여 페이지 부재율이 매우 높다. 이 후에 어느정도 메모리에 페이지를 할당받으면 페이지 부재율은 낮아지게 되며 곡선을 그리며 내려오게 된다. 즉, 초반에는 페이지 부재율이 급격히 낮아지다가 점점 감소율이 적어지게 된다. PFF는 가장 효과적인 구간을 유지하는 알고리즘이다.
페이지 부재율의 상한과 하한을 정하고 상한을 넘으면 frame을 더 할당하고 하한값 이하이면 할당 frame 수를 줄인다.
Page Size의 수
페이지 사이즈를 감소시킬때 장단점
- 페이지 수 증가
- 페이지 테이블 크기 증가
- 내부 단편화 감소
- page-fault시 더 많은 디스크io가 발생함
최근에는 큰 페이지 사이즈를 가지려고 하는 편이다.
댓글남기기