Virtual Memory Management

• 가상 메모리는 non-continuous allocation 시스템임.
• 이 시스템은 사용자 프로그램을 blocxk으로 분할하여 적재/실행함.

• page, segmentation system

• 관리의 목적은 성능 최적화겠지만 이 성능이라는 건 모호하기 때문에 cost model을 만듦.
• 비용 이라는 모델을 만들어 이 비용을 최소화 시킬 수 있는 다양한 기법을 통해 최소화시킴.

• cost model에는 page fault frequency (발생 빈도), page fault rate (발생률) 등이 있음.
• page fault는 메인 메모리에 실행해야 할 프로세스가 없을 때 발생함.
• 프로세스가 없을 때 해당 프로세스를 일시적으로 cpu를 반납시켜 block 상태로 보내 필요한 데이터를 가지고 다시 running 상태가 됨. 이런 과정은 프로세스를 뺏기고 가져오는 과정에서 context switch, high overhead임.

• 시스템을 향상시키기 위해 page fault rate를 낮춰야 할 것임.

• 결국 cost modal은 page fault임.

page reference string

• 페이지 참조 문자열 → 프로세스의 수행 중 참조한 페이지 번호 순서 (내가 어떤 페이지를 어떤 순서로 참조했는지 적어놓음).

• 왜 기록할까? → 어떤 페이지를 읽었는지에 대한 정보를 알아야 효율적인 알고리즘을 제작하고 기준을 세우고 평가하기 위해 기록함. 효율적으로 사용하는 데 쓰려고!

page fault rate

• 전체 참조했던 프로세스 중 몇 번 page fault가 났는지.

Hardware components

• address translation device (주소 사상 장치)
• 주소 사상을 효율적으로 수행하기 위해 사용.
• ex) TLB, Dedicated page-table register, Cache memories

• Bit vectors
• bit : 0, 1 값을 가짐, vectors : array 라고 생각하면 편함. ex) {0, 1, 1, 1, 0, 0}
• 메모리에 모든 프로세스가 다 차있다 할 때 새로 프로세스를 추가해야 한다면 어디에 넣어줘야 할지에 대해 선택을 해야 됨. 이 선택을 위해 정보, 기준이 필요한 데 bit vectors가 그 역할을 수행함.
• Reference bits (used bit)
• 참조 비트, 메모리에 적재된 각각의 page가 최근에 참조 되었는지를 표시 (지역성).
• 운영 방식
• reference bit를 확인함으로써 최근에 참조된 page들을 확인할 수 있음.
• Update bits (modified bits, write bits, dirty bits)
• 갱신 비트, page가 메모리에 적재된 후, 프로세스에 의해 수정되었는지를 표시.
• swap device에 있는 프로세스를 메모리에 올려놓았을 때 memory 상의 값이 바뀌게 되면 이 둘의 변한 값을 반영해야 함. 프로세스가 종료되고 다시 swap device로 돌아갈 때 반영 (write-back).
• 데이터의 무결성(정확성과 일관성을 유지하고 보증하는 것) 유지.
💡
메모리에서 나올 때 초기화 한다! 나오면서 write-back, swap-device에 변경된 정보를 저장한다! 이를 위해 사용하는 게 update bit다!

Software components

• Allocation Strategies(할당 기법)
• 각 프로세스에게 메모리를 얼마만큼 줄 것인가?
• Fixed allocation (고정 할당)
• 프로세스가 작업을 하는 동안 주어지는 프로세스 크기가 실행하는 동안 고정된 크기로 메모리를 할당함.
• Variable allocation (가변 할당)
• 프로세스의 실행동안 할당하는 메모리의 크기가 유동적임.
• 얼마만큼 주는 게 좋을까? → 적당히!
• 너무 큰 메모리가 할당되면 메모리가 낭비되고, 너무 적다면 page fault rate가 증가하고 시스템 성능이 저하됨.
• 프로세스 실행에 필요한 메모리 양을 적당히 예측해야 함.

• Fetch Strategies
• 특정 page를 메모리에 언제 적재할 것인가?
• Demand fetch (demand paging)
• 필요할 때 가져옴.
• 프로세스가 참조하는 페이지들만 적재.
• Anticipatory fetch (pre-paging)
💡
만화방에서 만화책을 가져올 때 한 권이 아닌 2~3권을 가져오는 것처럼
• 참조될 가능이 높은 page 예측.
• 가까운 미래에 참조될 가능성이 높은 page를 미리 적재함.
• 실제 대부분의 시스템은 demand fetch 기법 사용.
• 일반적으로 준수한 성능을 보여줌.
• 예측에 성공 시 page fault overhead가 없지만 잘못된 예측 시 자원 낭비(high overhead, 예측하는 데 필요한 kernel의 개입, hit ratio가 민감함)가 큼.
💡
그럼 Anticipatory fetch는 왜 배울까? 직접 통제 가능한 프로그램의 경우 예측 성공 가능성이 높고, 이런 환경일 때 성능 최적화가 가능함.

• Placement Strategies(배치 기법)
• page/segment를 어디에 적재할 것인가?
• 크기, 공간이 일정하기 때문에 paging sysyem에는 불필요.
• segmentation system에서의 배치 기법 ex) first-fit, best-fit, worst-fit, next-fit

• Replacement Strategies(교체 기법)
• 새로운 page를 어떤 page와 교체할 것인가?
• Fixed allocation을 위한 교체 기법.
• MIN(OPT, B0) algorithm
• Random algorithm
• FIFO(First In First Out) algorithm
• LRU(Least Recently Used) algorithm
• LFU(Least Frequently Used) algorithm
• NUR(Not Used Recently) algorithm
• Clock algorithm
• Second chance algorithm
• Variable allocation을 위한 교체 기법.
• VMIN(Variable MIN) algorithm
• WS(Working Set) algorithm
• PFF(Page Fault Frequency) algorithm

• Cleaning Strategies(정리 기법)
• 변경된 page를 언제 write-back 할 것인가?
• 변경된 내용을 swap device에 반영.
• Demand cleaning.
• 해당 page에 메모리에 내려올 때 write-back.
• Anticipatory cleaning
• 더 이상 변경될 가능성이 없다고 판단할 때 미리 write-back.
• 실제 대부분의 시스템은 demand cleaning 기법을 사용함.

• Load Control Strategies(부하 조절 기법)
• 얼마나 일을 많이 떠맡게 하는가!
• 시스템의 multi-programming degree 조절하는 전략.
• 어느 정도 유지하는 게 좋을까? → 적당히! (plateau, 고원)
• multi-programming degree를 저부하 상태로 만들 경우 시스템 자원 낭비, 성능이 저하되고, 고부하 상태로 만들면 자원에 대한 경쟁 심화(Thrasing 현상, 과도한 page fault 발생), 성능이 저하됨.