10강 - 1. Virtual Memory

• Virtual Memory 기법은 운영체제가 관리를 함.
• Demand Paging 
  • 요청이 있으면 그 페이지를 메모리에 올림.
  • paging 기법은 대부분의 시스템이 사용하고 있다.
• 좋은 소프트웨어일수록 방어적으로 소프트웨어를 만듦.
  • 방어적인 코드가 프로그램에서 대부분을 차지한다. 
  • 근데 방어적 코드는 거의 대부분 사용이 안되는데 한꺼번에 메모리에 올리면 메모리가 낭비가 된다.
  • 그래서 필요한 page만 demand paging을 사용한다면 한정된 메모리를 더 잘 처리할 수 있다.

원기둥은 swap area(backing store)

• 가장 필요한 부분은 demand paging에 의해 메모리에 올라간다.
• 그렇지 않은 부분은 swap  area에 내려가 있는다.
• 사용하지 않는 영역 - logical memory에서 6, 7
  • page table의 entry는 주소공간의 크기만큼 만들어진다.
  • 사용되지 않은 페이지는 invalid로 표시가 된다.
• 사용되는 영역 - 0 ~ 5 (이 프로그램에서 구성하는 page)
  • invalid로 표시되어 있으면 물리적인 메모리영역에 올라가 있지 않고,  swap area에 내려가 있다.
  • 주소 변환을 통해서 물리적인 프레임 번호를 얻을 수 있는 경우에만 valid라고 표시가 된다.
• 프로그램을 최초로 실행시키면 page table에서 entry들의 valid/invalid bit는 전부 invalid로 설정된다.
  • 페이지가 메모리에 올라가면 valid로 바뀐다.
• cpu가 주소변환을 할 때, invalid라면? - page fault
  • 해당 페이지는 물리 메모리에 없다는 의미!
  • page를 디스크에서 메모리로 올려야 함.(i/o)
  • page fault가 발생한다. 이 경우에 cpu는 자동으로 운영체제에게 넘어가게 된다.- 일종의 소프트웨어 인터럽트에 해당한다.
  • 운영체제는 fault 된 page를 운영체제에 올린다.

• MMU : 주소 변환을 해주는 하드웨어
• abort : 중단하다.
• replace : 빈 페이지 프레임이 없다면 하나를 뺏어온다.

Page Fault가 발생시 이루어지는 동작이미지

• Page Fault가 났을 때, Disk 접근은 굉장히 오래 걸리는 작업이다. 
• Page Fault가 얼마나 발생했느냐에 따라서 메모리접근하는 시간이 크게 좌우가 된다.
• 대부분의 경우는 page fault가 안 난다.
• page fault가 발생 시 굉장히 오버헤드가 크다.

• Page replacement : 빈 공간이 없을 경우 다른 page를 쫓아내야 한다.
  • OS 가 하는 일이다.
• Replacement Algorithm
  • page fault rate을 최소화해야 한다.
  • 어떤 거를 쫓아낼지 결정해야 한다.

• swap out victim page 할 때, 내용이 변경되었다면 backing store에 써줘야 한다.
  • 변경된 게 없다면 지워버리기만 하면 된다.

page fault를 가장적게하는 알고리즘이다.

• 미래에 참조되는 page들을 미리 다 안다고 가정한다.
  • Offline Optimal Algorithm
  • 미리 알고 있다는 가정하에 알고리즘을 사용한다.
    • 가장 먼 미래에 참조되는 page를 replace 
    • 미래를 다 안다고 가정하기 때문에 실제 시스템에서 사용하는 건 불가능
• 빨간색은 page fault 의미
• 연보라 색은 page fault가 발생하지 않음
  • 메모리에서 직접 참조되는 경우를 나타냄.
• Optimal Algorithm은 어떤 알고리즘보다도 최선의 성능을 낸다.(미래를 알고 있다고 가정하고 만든 알고리즘이기 때문)
  • 다른 알고리즘의 성능에 대한 upper bound 제공

---

미래를 모르는 상태에서 만드는 알고리즘

• 미래를 모를 때 어떻게 할까?
  • 과거를 본다!
  • 과거에 일어난 일을 바탕으로 고려한다. = LRU
• FIFO(First In First Out)
  • memory frame이 늘어날수록 page fault가 많이 일어난다. = FIFO Anomaly

메모리 관리 알고리즘에서 제일 많이 사용됨

• 가장 덜 최근에 사용된 page를 쫓아냄. (제일 오래전에 사용된 page를 쫓아냄)

• LFU : 참조 횟수가 가장 적은 page를 쫓아냄.
• 만약 참조 횟수가 동일하다면?
  • page 중에 제일 오래전에 참조된 page를 지우게 구현한다.

LRU vs LFU

---

LRU 구현

• 메모리 안에 있는 페이지들을 참조시간 순서에 따라서 한 줄로 줄 세운다.
• Linked list 형태로 운영체제가 페이지들의 참조 시간 순서를 관리함. 
  • MRU page = Most Recently Used
    • 가장 최근에 참조된 페이지
  • LRU page= Least Recently Used 
    • 가장 오래전에 참조된 페이지
• 어떤 페이지가 메모리에 들어오거나, 메모리 안에서 다시 참조가 될 때
  • 제일 아래쪽으로 보낸다.
• Replacement : 쫓아낼 때는 제일 위쪽에 있는 놈을 쫓아낸다.
  • LRU 알고리즘은 O(1) 시간복잡도를 가진다.

---

LFU 구현

사진 1

• 참조 횟수를 비교해야 한다.
  • 하나하나 비교해서 자리 바꿈을 해야 한다.
    • 이러면  O(N) 시간복잡도가 된다.(사진 2)
  • 그래서 Heap datastructure를 이용해서 구현한다.
    • 자식이 2개씩 있는 이진트리를 이용한다. 
    • 직계 자식 2개를 비교하면서 내려간다.
    • O(log N) - (사진 1)

사진 2