[운영체제] Virtual memory(1)

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

Virtual memory -> 전적으로 운영체제가 관리

Demand Paging: 해당 페이지가 요청이 됐을 때, 그때 메모리에 page를 올림

좋은 소프트웨어일수록 방어적인 소프트웨어

 

한정된 메모리 공간에서, 더 의미 있는(필요한) page를 올리기 위한 기법 -> 응답 시간이 좋아짐

 

Invalid bit:

1) 논리적 메모리에 존재하는 주소가 물리적 메모리에는 올라가 있지 않을 때 표시

2) 물리적 메모리에서는 할당하지 않는 영역이지만, 논리적 메모리에서만 할당하는 영역일 때에도 표시

 

address translation을 할 때 찾아간 주소가 invalid bit으로 set되어있으면 "page fault"를 날림.

이렇게 page fault trap이 걸리면 CPU가 자동적으로 운영체제에게 넘어감. 이때 운영체제가 CPU를 가지고 fault난 page를 운영체제에 올림

---

invalid bit이 기록된 프로세스를 메모리에 올릴 때

1) empty page frame을 찾는다

2) 메모리가 꽉차서 empty page frame이 없다면 가장 우선순위가 낮은 페이지 프레임으로부터 뺏어온다

3) 해당 페이지를 disk에서 memory로 읽어온다

 

page fault에서 디스크에 접근하는 건 굉장히 오래 걸리는 작업

 

Page replacement -> 가급적 page fault rate이 낮아지도록 설계

 

* reference string: page들이 참조된 순서를 기록. 만약 1번 page가 한 번 사용이 됐는데 replacement가 되었다면 그다음 호출에서 page fault가 발생할 것.

 

Page replacement: 메모리에 공간이 부족할 때 디스크로 쫓겨날 page를 정하는 작업. 그런데 만약 victim이 메모리에 올라온 이후에 write가 발생해 변경이 발생했다면, 디스크로 갈 때 그 내용을 저장. 변경된 내용이 없다면 그냥 제거만 하면 됨

 

이런 역할을 운영체제가 하게 됨

---

Offline algorithm: reference algorithm을 미리 알고있다는 가정 하에 운영. 

EX) 5번이 처음 참조되는 시점에서, 가장 먼 미래에 참조되는 4번을 replacement.

하지만 실제 적용은 불가능하고, 다른 알고리즘 성능에 대한 upper bound 제공. 즉 Optimal 알고리즘보다 더 좋은 성능을 낼 수는 없다는 의미. 최대치로 참고하는 용도.

---

FIFO: 메모리에 먼저 들어온 페이지가 먼저 나감

-> 3page frame에서 4page frame으로 오히려 page fault가 증가하는 FIFO Anomaly가 발생할 수 있음

 

LRU: 가장 오래 전에(least recently) 사용된(referenced) page를 쫓아냄. FIFO와 반대

 

LFU: 가장 덜(Least Frequently) 사용된 page를 먼저 쫓아냄

동률이 발생할 때에는 마지막 참조 시점이 더 오래된 page를 지움.

---

LFU -> 만약 4번 page가 막 참조가 시작되는 시점이었다면 이후로 많은 page fault가 발생할 수 있음

 

운영체제가 Linked list 형태로 LRU에서 MRU까지 page들의 작동 시간을 관리. 쫓아낼 때 비교가 필요 없기 때문에 시간 복잡도가 O(1).

 

LFU 역시 참조횟수에 따라 page들을 줄 세우기. 가 가능할 것 같은 게 이게 불가능. LFU 알고리즘은 참조 횟수가 기준이기 때문에 새롭게 참조되었더라도 LRU처럼 MRU page로 올 수 있는 게 아니라 비교를 통해 어디까지 내려갈 수 있는지 확인해야 함. 최악의 경우에는 모든 page들을 모두 비교한 뒤에 단지 한 칸만 내려갈 수도 있음. 때문에 heap을 사용. 이진트리의 root부터 자식 node들과 비교하면서 자신의 자리를 찾아감. 이진트리이기 때문에 시간 복잡도가 많아봤자 lgn.