📌 가상메모리

가상 메모리 (Virtual Memory)

Demanding Page: 요청이 있으면 그 페이지를 메모리에 올리는 것

• 실제로 필요할 때 Page를 메모리에 올려두는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / InValid bit의 사용
  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 Page Entry가 invalid에 초기화
  • address tranlation 시에 invalid bit이 set되어 있으면 → “page fault” (요청한 페이지가 메모리를 얻는 경우)
• 메모리에 올라가 있으면 valid 그렇지 않으면 invalid
• 프로그램의 logical memory(주소공간)에서 해당 주소들을 제공해줌 따라서 page table에서는 해당 주소 공간 만큼의 entry가 만들어짐. 여기서 사용되지 않으면, valid/invalid 등으로 구분

Page Fault

• invalid page를 접근하면 MMU(주소 변환을 하는 하드웨어)가 trap을 발생시킴. (Page fault trap)
• kernel mode로 들어가서 page fault handler가 invoke(실행)가 됨.
• 따라서 다음과 같은 순서로 page fault를 처리함.
  1. Invalid Reference? (eg. bad address, protection violation) → abort process (이상한건면 강제로 abort, 중단 시킴)
  2. Get on entry page frame (없으면 뺐어온다: replace / 페이지가 없는 경우도 있기 때문에 뺏어와야함)
  3. 해당 페이지를 disk에서 memory로 읽어온다.
     1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함.(block)
     2. Disk read가 끝나면, page tables entry 기록, valid/invalid bit = “valid”
     3. Ready queue에 process를 insert → dispatch later
  4. 이 프로세스가 CPU를 잡고 다시 running
  5. 아까 중단되었던 instruction을 재개
• 여기서 page Fault가 얼마나 자주 일어나는가? 에 따라서 속도 측면에서 달라짐

page fault performance (대부분의 경우 주소변환이 되지 않음 (거의 안남))

• Page Fault Rate 0 <= p <= 1, (최대한 낮아지게 해야함)
  • if p = 0, no page faults
  • if p = 1, every reference is a fault
• Effective access Time = (1-p) + p
  • 1-p is x memory access (메모리 접근 시간)
  • p (OS & HW page fault overhead + [Swap page out if needed] + Swap page in + OS & HW restart overhead)

Free Frame이 없는 경우

• Page replacement
  • 어떤 frame을 뺐어올지 결정해야함.
  • 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 돌아올 수 있음
• Replacement Algorithm
  • page fault rate는 최소화하는 것이 목표
  • 알고리즘의 평가
    • 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
    • Reference String의 예
      • 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Optimal Algorithm (Page Fault를 가장 적게 하는 알고리즘, Reference String을 미리 알고있다고 가정, 비현실적)

• MIN(OPT): 가장 먼 미래에 참조되는 page를 replace
• 4 frame example
• 미래의 참조를 어떻게 아는가?
  • Offline Algorithm
• 다른 알고리즘의 성능에 대한 upper bound(제일 좋기 때문에) 제공
  • Belady’s optimal Algorithm, MIN, OPT 등으로 불림

FIFO (First In First Out): 먼저 들어온 것을 먼저 내쫓음

• FIFO Anomaly (Belady’s Anomaly)
  • more frame → less page fault 가 되지 않는다임 (페이지를 늘려줬는데 page fault가 오히려 늘어나는 현상)

LRU (Least Recently Used): 가장 오래전에 참조된 것을 지움

LFU (Least Recently Used): 참조 횟수가 가장 적은 페이지를 지움

• 최저 참조 횟수인 page가 여럿 있는 경우
  • LFU 알고리즘 자체에는 여러 page 중 임의로 선정한다.
  • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 할 수도 있다.
• 장단점
  • LRU 처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에, page의 인기도를 좀 더 명확히 파악할 수 있음
  • 참조 시점의 최근성을 반영하지 못함
  • LRU보다 구현이 복잡함

LRU, LFU 알고리즘의 구현

• LRU: 사용을 한줄로 줄세우기 함. 업데이트는 맨 앞으로 옮기거나 추가해주면 되고, 삭제는 가장 맨 위에 있는 삭제하면 됨. 이 때 시간복잡도는 빅오O(1)이 됨. Linked Lisk로 구현
• LFU: 얘도 한줄로 줄세우기를 하면 안됨, LFU는 업데이트를 할 때 해당 페이지가 어디까지 내려갈 수 있는지 확인해 봐야함. 그래서 구현이 복잡. 시간복잡도는 O(n)임. 그래서 heap(Tree)로 구현함. O(log n)

---

프로그램을 구성하는 논리적인 메모리가 항상 물리적인 메모리에 올라가는 것이 아니라, 꼭 필요한 것만 올라감 (가상 메모리의 개념) 필요가 없거나 사용되지 않은 부분은 Backing Storage에 빼놓음. Page fault는 운영체제로 실행이 넘어감.

다양한 캐쉬기법

• 캐슁기법
  • 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속요청시 캐쉬로부터 직접 요청하는 방법
  • paging system 외에도 cache memory(메인메모리 보다 CPU에 가까움), buffer caching, web caching 등 다양한 분야에서 사용
• 캐쉬 운영의 시간 제약 (order of any)
  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 시간이 사용되는 경우 실제 시스템에서 사용될 수 없음
  • Buffer caching, Web caching은 O(1) ~ O(log n)까지 가능
  • Paging System인 경우
    • page fault인 경우에만 OS가 관여함.
    • 페이지가 이미 메모리에 존재하는경우 참조시각 등의 정보를 OS를 알 수가 없음
    • O(1)인 LRU의 list 조작 조차 불가능
    • 그래서 paging system에서는 LRU, LFU 알고리즘을 사용할 수가 없음
• clock Algorithm
  • LRU 근사 알고리즘
  • 여러 명칭으로 불림
    • Second chance Algorithm
    • NUR(not used recently) 또는 NRU(not recently used)
    • Reference bit을 사용해서 교체 대상 페이지 선정 (circular list)
  • reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
  • 포인터 이동 중에서 reference bit 1은 모두 0으로 바꿈
  • Reference bit 0인 것을 찾으면 페이지를 교체
  • 한 바퀴 돌고 와서도 (=second chance) 0이면 그때는 replace 당함
  • 자주 사용되는 페이지면 second chance가 올 때 1
• clock Algorithm의 개선
  • reference bit(access bit)와 modify bit(dirty bit)를 함께 사용
  • reference bit = 1: 최근에 참조된 페이지 (읽기만)
  • Modify bit = 1: 최근에 변경된 페이지(I/O를 동반한 페이지) (읽고 쓰기 모두)

page Frame의 Allocation

• Allocation problem: process에 얼마만큼의 page fault가 사용될 것인가?
• Allocation의 필요성
  • 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조
    • 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
  • Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함.
    • 최소한의 allocation이 없으면 매 loop마다 page fault
• Allcation Scheme
  • Equal allocation: 모든 프로세스에 똑같은 갯수 할당
  • Proportional allocation: 프로세스 크기에 비례하여 할당
  • Priority allocation: 프로세스의 priority에 따라 다르게 할당

global replacement vs local replacement

• global (자동적으로 조절됨) / 자유경제
  • Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다.
  • process별 할당량을 조절하는 또 다른 방법임
  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당 working set, PFF 알고리즘을 사용
• local (프로그램마다 할당됨 고정적으로) / 공산주의
  • 자신에게 할당된 frame 내에서만 replacement
  • FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시

Threshing Diagram

• 멀티 프로그래밍 대비 CPU 사용량을 나타낸건데. 여기서 threshing이 일어나면 CPU 사용량이 뚝 떨어짐.
• Threshing는 page fault 하느라 정신은 없는데, CPU는 이용하지 못하는 상황을 말함.

Threshing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못하는 상황
• Page fault rate이 매우 높아짐
• CPU utilization이 매우 낮아짐
• OS는 MPD(Multiprogramming Degree)를 높여야한다고 판단
• 또 따른 프로세스가 시스템에 추가됨 (higher MPD)
• 프로세스가 할당된 frame의 수가 더욱 감소
• 프로세스는 page의 swap in / swap out으로 매우 바쁨
• 대부분의 시간에 CPU는 한가함
• low throughput

working set

• locality of reference
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
  • 집중적으로 참조하는 해당 page를 locality set이라고 한다.
• Working Set model
  • locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합은 working set이라고 한다.
  • working set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않은 경우 모든 frame을 반납한 후 swap out(suspend)
  • Threshing을 방지함
  • Multiprogramming degree를 결정함.

working set algorithm (global replacement)

• working set의 결정
  • working set window를 통해 알아냄
  • working size가 델타인 경우
    • 시각 t에서의 working set (WSti)
      • Time interval에 사용된 서로 다른 페이지들의 집합
      • working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림
      • 즉, 참조된 후 델타 시간 동안 해당 페이지를 메모리에 유지한 후에 버림

page fault frequency (PFF)

• Page fault rate의 상한값과 하한값을 둔다.
  • Page fault rate의 상한값을 넘으면 frame을 더 할당한다.
  • Page fault rate이 하한값을 넘으면 frame수를 줄인다.
• 빈 frame이 없으면 일부 프로세스를 swap out 한다.

page size의 결정

• Page size를 감소시키면
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • internal fragmentation 감소
  • Disk transfer의 효율성 감소
    • Seek/rotation vs transfer
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • locality의 활용 측면에서는 좋지 않음
• trend
  • Larger page size