💫Introduction
메모리가 꽉 차서 Frame이 필요하다!
-> 피지컬 메모리에 있는 프레임에 저장되어 있는 것 들 중에서 디스크로 내려보내고(swap out) 디스크에서 진짜 필요한 것을 그 빈 자리에 다시 집어 넣어서 정상적으로 작동할 수 있도록하는 메커니즘이 필요하다.

Virtual Memory That is Larger Than Physical Memory

Demand Paging

: 요청이 있을 때만 page를 올리기 때문에 demand page

• 처음의 프로그램이 프로세스될 때 전체를 올리지 않고 실행되어야 하는 코드를 액세스할 때 그 때 메모리에 올려준다 (swap in) 디스크에서 피지컬 메모리로

invalid → 아직 메모리로 올라오지 않은 상태일 수도 있고 유효하지 않은 상태일 수도 있음
⇒ 프로그램 전체를 다 안 쓸 수도 있는데 그걸 다 올려? 너무 낭비자나

Locality 특성 덕분에 잘 동작!
→ Temporal locality, Spatial locality 두 가지가 다 적용이 된다.

• 당장에 실행시켜야 되는 것이 포함된 페이지만 그때 그때 올려서 사용하자!
• 메모리도 아끼고 로켈리티도 잘되고 관리를 잘 하기 위해 사용을 한다

why demand?

• 프로세스가 시작할 때는 메모리에 아무것도 안 올리고 시작을 하는데(모두 invalid 상태) 동작하면서 필요한 것들을 cpu의 요청에 의해 올리기 때문에
• virtual memory에 모든 페이지가 invalid 상태이다. 이런 경우에 어떤 메모리를 참조를 하더라도 피지컬 메모리에서 찾을 수 없으니까 이런 경우를 page fault라고 한다.

Revisited: Memory Protection in Paging

• valid : 메모리에 있는 것

• invalid : 메모리에 없음. → 메모리에 없지만 디스크에 있을 수 있으니 확인을 해야한다. 프로텍션에 걸리는 케이스가 아니라 디스크에 있는 상황을 Page Fault 라고 한다.
  ⇒ 이 판단은 OS가 한다
  

• if valid-invalid bit == v
  → in-memory
  

• if valid-invalid bit == i → CPU가 exceoption을 발생시킴 (interrupt)
  → not-in-memory (protection fault) or Page fault (os가 판단)

  • 메모리에 없는 거면 프로세스 킬
  • page fault면 디스크에서 업로드하고 다시 접근

Page Fault

: invalid page에 참조하려고 하는 경우

1. 특정 메모리 부분을 탐조하려고 한다. cpu는 mmu안에 있는 TLB 본다. 하지만 처음 프로세스를 실행하였으니 TLB도 free여서 page table을 참조한다. page table도 아직 로드하지 않았으니 invalid 상태이다.
2. CPU는 스스로 exception을 발생시켜 interrupt를 건다. interuppt를 걸면 interrupt hadler가 동작해야하기 때문에 os가 동작을 한다.
3. os는 disk에 있는 backing store에 있는 내용을 읽는다.
4. free frame에 할당을 해준다
5. page table에 업데이트를 하고
6. 다시 명령을 수행한다. invalid → valid로 바뀌어 있음

• OS마다 구현이 다른데 그냥 한 비트 더해서 하나는~ 진짜 valid invalid 하고 하나는~ 메모리 위에 올라왔는지 아닌지 이렇게 할 수도 있다.
  -> 근데 그건 구현의 차이!

• 디맨드 형태로 메모리에 올려서 사용할 때
  전체를 올리지 않고 필요한 것만 그 때 그 때 올려서 사용하고 그것을 디맨드 페이징이라고 한다,

• 필요한거가 메모리에 없을 때 디스크에 있는 것을 올려야 하는데 valid/invalid bit에서 invalid이면 운체가 page fault인지 protextion fault인지 확인

---

Page Replacement

다 할당받아진 상태일 때
특정 프로세스에서 page fault가 나서 swap in 을 시켜야하는데 꽉차서 못한다.

• 무언가 하나를 빼야하는데 원래 프레임을 차지하고 있는 프로세스가 아직 수행을 다 마치지 않았으니 원래 있던 것을 디스크에 백업하고 당장 실행되어야 하는 것을 올림.
• 그러면 어떤 것을 뽑을것인가?!?!?!
• io는 느리다
  replacement는 읽고 써야하니 두 번 해야해서 이게 제일 병목현상을 일으킨다.

Memory Reference

1. CPU에서 특정 메모리 영역을 참조하는 명령어 수행
2. 제일 먼저 TLB를 살펴 본다.
   • TLB Hit
   • TLB Miss
     • Page Fault → 메모리에 있는 페이지 테이블을 한 번 더 참조 → 엔트리 정보를 TLB로 올려주고 → 다시 실행을 하면 → TLB hit
     • Protection Fault → page table이 invalid라 exception을 발생했을 때 os가 protection fault 라고 판단

✅ 처음(context switching)에는 TLB도 clean한 상태여서 hit miss, page fault가 발생한다

• cold cache : cache miss가 계속 발생
• hot cache : cache hit이 계속 발생

• TLB 미스 페이지 테이블을 보려고 했는데 페이지 테이블이 없는 경우가 발생할 수 있다. 극히 드물지만. 스왑 아웃을 하면 페이지를 내리게 되는데 내리다보니 페이지 테이블을 내릴 수 있다. 거의 없다고 보아도 무방한 경우
  

✔ Page faults

→ 페이지 테이블에 invalid - 피지컬 메모리에 올라와있지 않은데 접근을 시도
→ TLB traps to the OS (software takes over)

• Invalid (Not allocated) – OS sends fault to the process (e.g., segmentation fault)
• Invalid (Not in physical memory) – OS allocates a frame, reads from disk, and maps PTE to physical frame

---

Copy-on-Write

• fork 수행시 : 똑같이 공유
• exec 수행시 : 다 날리고 새로 올력야 하는데 디맨드 페이징으로 한번에 다 올리는 것이 아닌 사용하는것만 조금씩 올림
  → 성능 개선이 됨
  → 새로운 프로세스를 실행했을 때 다 할당을 해주어야 해서 시간이 오래 걸리지만 fork exec할 때 demand paging 정책도 다 되어 있어서 fork할 때도 …
  디맨드 페이징에 때라 필요한 것만 하나씩 올리니까 로드하는 타임도 메모리도 절약이 가능하다.
  

---

“ What happens if there is no free frame?”

피지컬 메모리가 가즉차서 free frame이 없어 어떤 것을 swap out을 시켜야 한다. 이 때 어떤 것을 골라 내릴지가 굉장히 중요하다. 잘못 내리면 page fault 횟수가 늘어나게 된다.

Page Replacement

: 어떤 걸 내리고 올릴건지, page fault ratio를 낮추는 것을 목표

→ vitim 을 정해서 디스크로 내리고 다른 것을 올림

• 다시 참조되지 않을 거 같은 것을 내려야 page fault가 발생하지 않는다

• 실제로 프레임을 더 많이 할당받은 것이 page fault의 수가 적지만 실제로 5개 정도 이상 frame을 할당받았으면 그 이상은 거의 비슷하다.
  → locality의 특성 때문에
  

Page Replacement Algorithms

Goal: lowest page-fault rate, 자주 사용되지 않는 것을 내림

1. FIFO

: 먼저 들어온 것이 먼저 나간다

• 할당 받은지 오래된 것을 victim으로 선정

• swap in된지 오래 된 것을 먼저 뺀다 → 안된당 구려!

• 도착시간만 고려하기 때문에 앞으로 많이 참조될 것 같은 것의 기준이 도착시간인데 이게 miss match

2. Optimal Algorithm

Least Recently Used (LRU) Algorithm

• Timestamp implementation :최근에 가장 사용되지 않은 것을 swap out
  Timestamp 특정 시점의 그 시간 정보
  → 참조될 떄 마다 도장을 찍는다
  → 시간 나타내려면 4비트는 써야 하니 메모리가 엄청 필요하다
  → 매번 참조할 때마다 시간 정보를 가져다 써야 하니 오버헤드가 크다
  ⇒ 배보다 배꼽이 커진다
  

• Stack implementation 참조된 시간의 역순으로 스택을 만든다. 가장 최근 참조된 것을 stack에 top에 위치
  매번 페이지 접근을 할 때 마다 스택을 관리해주어야 하는데 이것도 오버헤드
  → os가 계속 관리를 해줘야 한다.
  

LRU Approximation Algorithms

Reference bit

: 시간정보를 4-8비트로 사용하지 않고 1비트로 사용한다. 최근에 사용했으면 1로 중간중간 0으로 초기화, 4비트에서 1비트로 줄이고 오래 안 쓰이면 0으로 만든다.

• initially = 0
• 참조가 되었으면 1로 update
• 주기적으로 0으로 바꿈 → timer interrupt가 발생했을 때

→ 레퍼런스 비트 가 0으로 된 애들중에 누구를 빼야 하는지 알 수가 없다. 방금 전에 참조가 되었는데 0으로 초기화되었는데 선정이 되면 page fault가 발생할 수 있다.

Second chance (or LRU clock)

→ 해결법으로 가 제안이 되었다
1이면 최근에 한 번은 사용된 것이니 넘어가고 넘어가면서 0으로 초기화를 해준다. 0을 만나면 이것이 vitim이 된다.

Not Recently Used (NRU)

• Use R (reference) and M (modify) bits

  • write - modify bit

• modify bit는 1로 한 번 바뀌면 다시 0으로 돌아가지 않는다. (메모리에 올라가 참조되어 있는 기간동안은 변하지 않는다)

• 우선순위 : 숫자가 작을수록 높다.

  class 0 → class 1 → class2 → class 3

  ⇒ 이 알고리즘을 사용하기 위해서는 2비트가 필요하다
  

메모리에 참조한다는것은 read + write임. write하면 정보가 바뀔 수 있다. read만 있는지 write도 했는지를 따진다. 최초에 시작할 때는 class 0으로 시작을 한다. 이게 바뀌었는지 아닌지 확인할 modify bit를 페이지 테이블 엔트리에 추가를 한다. class 0에서 시작을 해서 인터럽트가 걸릴 때 마다 reference bit를 0으로 초기화를 해준다.

• 실제로 시스템에 사용이 된다.
• 가장 합리적이다.
• 주기적으로 timer interrupt가 발생하면 reference bit를 0으로 초기화하는 것은 동일
• 특정 page에 write가 되었다는 의미는 참조도 되고 바꾸기도 되었다는 의미

Least Frequently Used (LFU)

: 가장 사용이 덜 된걸 뽑자, count 횟수가 가장 적은걸 뽑자 (사용된 횟수 기준)

• counter가 필요
• counter 나타내기 위한 비트를 approximation하게 줄이다 보면 1비트가 되고 그게 레퍼런스 비트가 되고 LRU랑 똑같아진다.
• Aging : shift reference를 사용
  

---

Allocation of Frames

피지컬 메모리에 있는 frame을 어떻게 누구에게 할당해줄 것이냐

Allocation algorithms

• Equal allocation : 모든 프로세스에게 똑같이 나누어주는 것
• Proportional allocation : 큰 프로세스에게 더 많이 주는 것
  → 현재 이 방법을 사용 (우선순위 개념과 함께 하이브리드로 사용)
• Priority-based allocation : 프로세스가 가지는 우선순위를 가지고 할당

Page-Fault Frequency Scheme

• Page fault가 너무 적은 경우 : frame을 너무 많이 할당
  → OS가 frame을 하나씩 뺏어감
  
• Page fault가 너무 많은 경우 : framed을 너무 적게 할당
  → OS가 Frame을 하나씩 allocation 해준다
  

Page replacement
피지컬 메모리를 다 사용하고 있을 때 vitim을 선정할 때 전체 프레임(Global Frame)을 기준을 해서 선정할 것이냐 아니면 할당된 프레임(Local Frame) 안에서 선정을 할 것인가

• Global Repalcement : 전체 Frame을 Replacement 대상으로 둔다
• Local Repalcement : 특정 프로세스가 동작할 때 Page Fault가 일어났으니 그 프로세스한테 할당 받아져 있는 Frame 중에서 Replacement한다

→ 최근 운체들은 Local Repalcemen을 기준으로! 프로세스 내에서도 로켈리티가 존재하기 때문에 프로세스 내에서 replacement를 한다.

---

Thrashing

: a process is busy swapping pages in and out

• 멀티프로그래밍 환경이라 다수의 프로세스가 올라가 작동한다.

• 프로세스 개수가 많아질수록 cpu사용률이 점점 올라가야 정상인데 그런데 어느 순간이 되면 뚝 떨어진다.(이런 경우를 Trashing)
  → 페이지 Repalcement에 의해 이런 현상 발생

• 프로세스 수가 많아지다보면 physical memory의 utilizaiton이 증가한다. 계속 증가하다보면 physical memory보다 많은 양을 필요로 하게 되어 page swap이 계속 일어난다.

→ 프로세스 로켈리티 사이즈의 합이 전체 메모리보다 크다
= Page Fault 가 많이 발생
= Replacement가 빈번하게 발생 ( = I/O = 느리다 = io하는 동안 cpu는 논다)

✅ 해결 방안

→ 일시적으로 degree of multiprogramming을 줄임
병목현상이 피지컬 메모리에서 걸리는 현상, 피지컬 메모리를 무한히 둘 수 없기 때문에
현재 시스템에서 돌아가는 프로세스들이 가지는 로켈리티의 총합이 피지컬 메모리 총량보다 큰 경우와 같다

---

Working-Set Model

단위 시간동안 필요한 프레임의 개수 → 크냐 작냐 =⇒ 모델링

• 너무 짧으면 : 로켈리티 특성을 파악하기 어려우
• 무한대 : 전체 시스템의 생애주기의 로켈리티를 다 보는 것

Other Considerations

1. Prepaging

디맨드 페이징은 수행할 때 딱 필요한 페이지만 가져다 쓰는데

• 접근하려는 페이지 다음페이지 다음다음 까지 한 번에 다 가지고 와서 사용하는 것
  미리 paging 하는 것

• 하드디스크를 쓸 때 사용하면 좋다
  arm seek time 때문에 느린데 이왕간김에 주르륵 읽어오는 것이 더 좋다
  

2. Page size selection

• Fragmentation
  → page 사이즈가 작아야 internel fracmentation이 줄어듬
  
• Page table size
  → 페이지 사이즈와 역수
  
• I/O overhead
  → 페이지 사이즈와 역수
  
• Locality
  → 많아야 좋은
  

⇒ 이걸 다 따져서 나온 것이 4KB

3. TLB Reach

• TLB에 저장되어 있는 Page Table Entry로 커버할 수 있는 영역을 TLB Reach라고함.
• TLB 사이즈가 커지면 TLB Reach가 커짐
• Page 사이즈가 커지면 TLB Reach가 커짐

tlb 용량이 있는데 이 조만한 캐시 가지고 실제 접근가능한 메모리의 총량

4. Program structure

한 줄당 4kb → 하나의 페이지 차지

5. I/O Interlock

DMA로 동작하는 task가 있을 때 physical memory에 특정 영역을 실제로 swap이 되지 않도록 page 교환이 되지 않도록 묶어두는 것