KOCW_Virtual Memory

• 물리적 메모리의 주소변환은 OS가 관여하지 않는다, 하드웨어가 담당
• Virtual Memory기법은 OS가 전적으로 관여한다

✅ Virtual Memory

• 각 프로세스마다 virtual address를 할당하는 메모리 관리 방법
• 프로세스의 Virtual Memory중 일부는 메모리에 적재, 나머지는 디스크의 스왑 영역에 존재
• Virtual Memory는 메모리의 연장 공간으로, 디스크의 스왑 영역이 사용될 수 있기 떄문에 프로그램 입장에서는 물리적 메모리에 대한 제약이 사라진다
• Virtual Memory 에서는 paging기법을 실질적으로 사용한다
• 실제로 현대적인 프로그램은 paging기법을 주로 사용

✅ Demand Paging(요구 페이징)

demand가 있으면 그 페이지를 paging, 즉 page에 올리겠다

• 실제로 필요할 때 page를 메모리에 올리는 것
• 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 ❌
• 요청이 되었을 때 address translation을 하고 page에 올린다
• 당장 필요한 프로세스만 메모리에 올린다 ⭕️

• 특정 page에 대한 CPU요청이 들어오면, 해당 page를 메모리에 적재한다.

  • 👍🏻 I/O양의 감소
  • 👍🏻 physical memory 사용량 감소
  • 👍🏻 빠른 응답 시간
  • 👍🏻 더 많은 사용자 수용 가능
  • 👍🏻 더 많은 프로그램을 메모리에 올릴 수 있음
  • 👍🏻 physical memory의 물리적 용량 제약을 벗어날 수 있다

• 시스템에서는 특정 프로세스를 구성하는 page 중에서 어떤 page가 메모리에 존재하고, 어떤 page가 디스크의 스왑 영역에 존재하는지 valid bit, invalid bit로 표시
  • valid bit: page가 메모리에 존재한다
  • invalid:
    • 1️⃣ 사용되지 않는 주소공간이다
    • 2️⃣ 페이지가 물리적 메모리에 없다
• 처음에는 모든 page entry가 invalid로 초기화, default

logical memory에 A~H까지 있음
logical memory       page table       physical memory      swap area
   0, A               0, 4, valid         4, A
   1, B               1, X, invalid     안 올라와 있음            B
   2, C               2, 6 valid          6, C
   6, G               6, X, invalid    사용되지 않는 주소공간       X

• 사용되지 않는 주소공간이라도 page table은 만들어진다
• 그래서 G, H가 만들어졌지만, 사용되지 않기 때문에 invalid이다

☑️ Memory에 없는 page의 page table

• address translation시에 invalid bit이 set되어 있으면
• ➡️ page fault

CPU에서 프로그램1을 실행하기 위해
address translation이 필요했고
그래서 프로그램1 logical memory를 page table에서 page1을 찾았다
그러나 page1은 invalid로 설정되어 있고, physical memory에 메모리가 안 올라와 있음
그러면 page fault
page1의 값을 메모리에 올리기 위해 I/O작업이 필요하다

page fault가 발생하면
CPU는 OS에게 넘어가게 된다 ➡️ 일종의 interrupt

✅ Page Fault

page fault가 발생했다는 의미는
🟰 CPU가 참조하려는 page가 물리적 메모리에 없다
🟰 그래서 비트 값이 invalid로 표시되어 있다 page fault
invalid page를 접근하면 MMU가 page fault trap을 발생시킨다

• CPU가 자동으로 운영체제에게 넘어감
• I/O를 해야 하기 때문이다
• kernel mode로 들어가서 page fault handler이 invoke됨
• page fault가 낮을수록 좋음

☑️ Page Fault Process

• 다음과 같은 순서로 page fault처리
• 운영체제가 CPU넘겨받아서 하는 일

1. 프로세스가 메모리에서 M이라는 값을 불러오려고 함, 그런데 메모리에 값 없음
2. page fault trap발생
    CPU가 자동으로 운영체제에게 넘어감
3. 해당 페이지에 대한 접근이 올바른지 확인
    - 잘못된 메모리 요청이 아닌지 확인
    - invalid reference(bad address, protection violation)
    - 사용되지 않은 주소 영역 접근이거나/ 접근 권한 위반
    ➡️ abort process
4. 해당 페이지에 대한 접근 문제가 없다면 물리적인 메모리에서 비어 있는 프레임을 할당받는다
    - get an empty frame
    - (비어있는 프레임 없으면 뺏어온다 replace)
5. 해당 페이지를 하드 디스크에서 찾아 물리적 메모리의 빈 프레임에 적재
    - 해당 페이지를 disk에서 memory로 읽어온다
    - 요청된 페이지를 디스크에서 메모리로 적재하는데는 오랜 시간 소요(I/O작업)
6. 요청된 페이지를 메모리로 적재하는 것은 오랜 시간이 걸리는 I/O작업이기 때문에 page fault를 발생시킨 프로세스는 CPU를 preempt, block
    - disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당한다(block)
7. Finish bring in missing page to physical memory
    - 디스크 입출력이 완료(페이지가 물리적 메모리에 적재)
6. 아까 중단되었던 instrucion을 재개
    - interrupt 발생, page tables entry = "Valid"
    - 이 프로세스가 CPU를 잡고 다기 running
    - Disk read가 끝나면 page tables entry기록 valid/invalid bit = "Valid"
    - ready queue에 process를 insert ➡️ dispatch later

☑️ Performance of demand paging

Demand Paging의 성능에 가장 큰 영향을 끼치는 요소는 page fault

• disk에서 프로세스를 읽어오는 건 매우 오래 걸리고 overhead가 큰 작업이기 때문이다
• 대부분은 page fault까지 가지 않지만,
• 👎🏻 page fault가 나서 메모리에서 값을 읽어올 때는 overhead가 비싸다

• 따라서 page fault가 낮을수록 좋음 ⬇️

• Page Fault Rte 0<= p <= 1.0
  • if p = 0 no page faults
  • if p = 1, every reference is a fault

Effective Access Time
 =  (1 - p) * memory access
    + (OS & HW page fault overhead)
    + [swap page out if needed] //메모리에 자리 없으면 프로세스 쫒아내기
    + swap page in
    + OS & HW restart overhead

✅ Page Replacement

physical memory에 더 이상 자리가 없어
기존 프로세스를 쫒아내고 empty frame을 만들어야 하는 상황
어떤 프로세스 page를 쫒아낼지 결정

• page fault가 발생하면 요청된 page를 디스크에서 메모리로 불러와야 하는데,

• 물리적 메모리에 빈 프레임이 존재하지 않을 경우 page replacement가 필요하다

• 메모리에 올라와 있는 page를 디스크로 쫒아내야하는데, 어떤 page를 쫒아낼까?
• 곧바로 사용되지 않을 page를 쫒아내는 것이 좋음
• 동일한 page가 여러 번 메모리에서 쫒겨났다가 다시 들어올 수도 있음

victim(쫒겨날 page)을 정하고
1. swap out victim page
2. victim page의 bit를 invalid로 바꾸기
3. 가져오고 싶은 프로세스 페이지 불러오기 swap in designed page
4. reset page table for new page, frame번호를 table에 적고 valid로 바꾼다

☑️ Page Replacement Algorithm

• physical memory가 꽉 찼을 때 어떤 page를 replace할 것인지 결정하는 알고리즘
• page fault rate를 최소화하는게 목표

• 알고리즘 평가: 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사

• Optimal Algorithm
• FIFO
• LRU
• LFU

📌 Optimal Algorithm

• page fault rate를 가장 적게 하는 알고리즘
• MIN(OPT): 가장 먼 미래에 참조되는 page를 replace, 쫒아내기
• 그러나 솔직히 미래의 참조를 알 수는 없기 때문에 이상적인 알고리즘
• 미래의 참조를 안다고 가정하고 알고리즘 구현(현실적으로 구현은 불가)

• Belady's optimal algorithm, MIN, OPT등으로도 불림

• ❓ 미래의 참조를 어떻게 아는가?
• offline algorithm

• 현실적으로는 미래를 알 수 없기 때문에 안다고 가정 ➡️ offline

• 👍🏻 다른 알고리즘의 성능에 대한 upper bound 제공
• 👍🏻 제일 이상적인 알고리즘으로, 다른 알고리즘과 성능 비교에 사용
• 👎🏻 현실적으로는 구현 불가

처음에는 메모리가 다 비어있음
1, 2, 3, 4까지는 메모리가 비어 있었기 때문에 page fault
page fault: 빨간색
메모리에 있는 경우: 연보라색
1, 2번은 메모리에 있음 ➡️ page fault
5번: page fault, 메모리 다 차서 page replacement 필요
4번이 제일 먼 미래에 참조되기 때문에 4번을 쫒아냄

총 6번의 page fault 발생

📌 FIFO(First In First Out) Algorithm

• FIFO: 먼저 들어온 것을 먼저 내쫒음

• page replacement시 물리적 메모리에 먼저 들어온 page를 가장 먼저 내쫒는다

• 메모리에 frame이 3개 있는 경우/ 4개 있는 경우 실험

• 가장 처음에 들어온 1번을 쫒아냄

• 3개 있는 경우: 9 page fault

• 4개 있는 경우: 10 page fault

• 보통은 메모리 성능이 좋아져 frame이 많아지면
• page fault도 줄어들어야 할 것 같은데, 오히려 늘어남!
• 이를 FIFO Anomaly, Belady's Anomaly라고 부름

• 👎🏻 more frames⬆️, more apge faults⬆️, less efficient

• 👎🏻 먼저 들어왔더라도 계속해서 많은 참조가 이루어질 수도 있기 때문에, 비효율적인 상황 발생 가능

📌 LRU Algorithm

Least Recently Used Algorithm
가장 오래 전에 참조된 것을 쫒아낸다, replace

• ✔️ temporal locality(참조지역성): 한번 참조된 메모리 영역은 짧은 시간 내에 재참조될 가능성이 높다

• 가장 오래전에 사용된 것을 쫒아내고
• 최근에 사용된 것은 메모리에 보관
• 마지막 참조 시점이 가장 오래전에 사용된 page를 쫒아내기

• 가장 오래전에 사용된 3번을 쫒아낸다

☑️ LRU 구현

• LRU: page참조를 연결리스트로 하여 한 줄로 줄세우기를 한다
• 메모리 내의 page들을 참조 시간 순서대로 연결리스트로 나열해서 관리
  • 연결리스트 앞: 오래전에 참조된 페이지
  • 연결리스트 뒤: 최근에 참조된 페이지
  • 또 참조되면 줄의 앞에 있다가 줄의 뒤로 옮김
• 그래서 쫒아낼 때는 맨 위에 있는 page만 쫒아내면 됨
• complexity: O(1) 비교가 필요가 없음

📌 LFU Algorithm

Least Frequently Used Algorithm
참조 횟수reference count가 가장 적은 페이지를 지움

• 참조 횟수를 기준으로 page를 교체한다

• 가장 덜 빈번하게 사용된 page를 쫒아낸다
  

• ❓ reference count가 동일한 page가 여럿 있는 경우?

  • LFU 자체에서는 여러 page중 임의로 한 개 선정
  • 또는 성능향상을 위해 가장 오래 전에 참조된 page를 지우도록 구현할 수 있다

• 👍🏻 LRU처럼 직전 참조 시점만 보는게 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확하게 반영할 수 있음
• 👎🏻 참조 시점의 최근성을 반영하지 못함
• 👎🏻 LRU보다 구현이 복잡하다

☑️ LFU 종류

• ✔️ Incache-LFU

• 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수 카운트

• ✔️ Perfect-LFU
• 페이지의 과거 총 참조 횟수 카운트
• 👍🏻 페이지의 참조 횟수 정확히 반영 가능
• 👎🏻 메모리에서 쫒겨난 페이지의 참조 기록까지 모두 보관해야 하므로 오버헤드가 크다

☑️ LFU 구현

• 만약 LFU를 연결리스트로 구현하면(한 줄로 세웠으면)
• complexity가 O(N)이 된다
• replace할 page를 뒤에 있는 page들과 참조횟수를 다 비교해야 하니까
• (하나씩 다 내려오면서 n개를 다 비교해야 하기 때문)

• 또 만약 새로운 page가 참조되어 메모리에 적재되거나, 기존 page가 다시 한 번 참조되면 연결리스트 내 순서를 바꾸기 위해서 참조횟수를 다 비교해야하니까 complexity가 O(N)

• LFU: heap으로 구현한다
• heap으로 구현하면 n개를 다 비교할 필요 없이 부모 노드랑만 비교하면 됨

• 그나마 complexity가 O(log n)이 된다

• 또 참조되면 아래에 있는 2개의 자식 page와 참조횟수를 비교
• 참조횟수가 많은 순서대로 자리바꿈을 한다
• 참조횟수가 많을수록 아래에 선다
• 쫒아낼 때는 맨 위 root에 있는 page를 쫒아내고 heap을 재구성한다

LRU 🆚 LFU

• LRU: 1번 페이지 삭제
• 🆚 LFU: 4번 페이지 삭제

• LRU: page참조를 연결리스트로 구현
• page replacement때는 맨 위에 있는 page만 쫒아냄

• complexity: O(1) 비교가 필요가 없음

• 🆚 LFU: heap으로 구현
• 자리바꿈을 할 때 아래에 있는 page와 참조횟수를 비교해야 하므로

• complexity: O(log n) 비교가 많이 일어남

• 👎🏻 공통된 단점: 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교해야 하므로 알고리즘의 운영에 시간적인 오버헤드 발생

✅ 다양한 caching 환경

• caching 환경에서도 Replacement Algorithm이 사용된다.
• 어떤 cache를 유지하고, 어떤 cache는 삭제할지

• 이러한 cache는 두 장치 간의 속도 차이 완화를 위해 사용되는 것이다

• paging system에서도 마찬가지로 cache가 사용된다
• 두 장치 간 속도차 완화 ➡️ 이 때 두 장치란, memory(빠름) 그리고 I/O장치, swap영역(느림)

☑️ Caching

한정된 빠른 공간cache에 요청된 데이터를 저장해 두었다가 후속 요청시 cache로부터 직접 서비스하는 방식

• paging system에서도 cache memory, buffer caching, web caching등 다양한 분야에서 사용된다.

☑️ cache운영의 시간 제약

cache환경에서는 꼭 시간 제약을 지켜야 한다

• Replacement Algorithm에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리면
• 실제 시스템에서 사용할 수 없음

• 모든 cache를 다~ 살펴보면서 어떤 것을 쫒아낼지 결정할 수는 없음! 너무 비효율적

• ✔️ buffer caching, web caching의 경우

  • buffer caching: 파일 시스템에서 같은 파일 여러번 읽어오는 경우
  • web caching: 같은 url을 여러번 요청하는 경우
  • O(1) ~ O(log n) 까지만 허용
• ✔️ paging system인 경우
  • page fault일 때만 OS가 관여함
  • 페이지가 이미 메모리에 존재하는 경우 참조시각 등 정보를 OS가 알 수 없음
  • O(1)인 LRU의 list조작조차 불가능
  • 그래서 실제로 paging system에서는 LRU, LFU가 불가능하다

❓ 왜 paging system에서는 LRU, LFU가 불가능한가?

• LRU, LFU를 하기 위해서는 참조 시간/참조 횟수를 알아야 하는데,
• OS는 page fault가 나면 관여를 하기 때문에 참조 시간/참조 횟수를 알지만
• page fault가 나지 않는 경우(이미 메모리에 적재되어 있는 경우) 관여하지 않기 떄문에 참조 시간/참조 횟수를 모른다.
• 따라서 OS는 참조 시간/참조 횟수를 정확히 알 수가 없음

프로세스A가 CPU를 가지고 running
메모리 참조를 위해 address translation
만약 address translation했더니 이미 물리적인 메모리에 올라와 있다면
바로 그 페이지를 CPU로 가져가면 된다.
➡️ 중간에 운영체제가 개입하지 않음
➡️ address translation에는 운영체제가 개입하지 않기 떄문이다
➡️ 따라서 운영체제는 그 페이지를 언제/몇번 사용했는지 모른다. ❌
➡️ 따라서  paging system에서는 LRU, LFU가 불가능

반면 물리적인 메모리에 없고 디스크에 있다면
page fault
CPU운영권이 OS에게 넘어간다
OS가 디스크에서 page를 page table에 올려놓고
언제 올려놨는지 그 시간을 안다 ⭕️

➡️ 결국, 운영체제는 page fault가 났을 때 page상태만 알고
이미 메모리에 올라간 page에 대해서는 모르기 때문에
결론적으로, paging system에서는 LRU, LFU가 불가능하다

📌 Clock Algorithm

LRU를 구현 가능하게 실현한 알고리즘
LRU의 근사 (approximation) 알고리즘
시계 바늘이 한 바퀴 도는 동안 참조되지 않는 페이지 교체

• 🟰 Second Chance algorithm(시계 바늘이 다시 올동안 참조되어야 함)
• 🟰 NUR(Not Used Recently)

• 🟰 NRU(Not Recently Used)

• 🆚 LRU: page들을 한줄로 줄세우고, 제일 오래된 page 쫒아냄
• Clock: page들을 원으로 세우고 bit가 0인, 최근 참조되지 않은 page 쫒아내기

0/1: reference bit, access bit

bit가 1이다: 최근에 사용되었다
- 페이지가 참조되면, address translation하는 하드웨어가 1로 만들어놓는다
- OS 바늘이 돌면서 bit가 1이면 0으로 바꾸고 지나감
- 0이면 쫒아낸다
bit가 1이다 🟰 OS 바늘이 한 바퀴 도는 동안 적어도 한 번 이상은 사용되었다

bit가 0이다: 최근에 사용되지 않았다
- 제일 오래된 페이지란 의미는 아니다 ❌
- 하지만 최근에 사용되지 않은 페이지는 맞다
- reference bit가 0인 페이지는 replace
bit가 0이다 🟰 OS 바늘이 한 바퀴 도는 동안 한번도 사용되지 않았다

• 각 frame마다 reference bit이 존재
• 교체할 page를 선정하기 위해 각 page frame들의 reference bit를 순차적으로 조사
• reference bit을 사용해서 replace될 page 선정

• circular list

• 특정 page가 참조되면, reference bit은 1로 바꿈
• clock algorithm은 reference bit가 0인 것을 찾을 떄까지 포인터를 하나씩 앞으로 이동
• 포인터를 이동하며 reference bit가 1인 것은 모두 0으로 바꾸고 지나감
• reference bit이 0인 것을 찾으면 그 page를 replace
• 한 바퀴 돌아왔는데(second chance) 0이면 그 때는 replace 당함

• 자주 사용되는 페이지라면 second chance가 와도 1일 것이다

• 👍🏻 하드웨어 지원을 통해 LRU, LFU에 비교해 오버헤드를 줄임

☑️ Clock Algorithm의 개선

• reference bit(access bit)과 modified bit(dirty bit)을 함께 사용하기
• ✔️ reference bit(access bit) = 1:
  • 최근에 참조된 페이지
  • CPU read 또는 CPU write
• ✔️ modified bit(dirty bit) = 1:
  • 최근에 변경된 페이지(I/O가 이루어진 페이지)
  • CPU write가 이루어진 페이지
  • 새로 바뀐 값을 저장하고 메모리에서 쫒아내야 하니까

✅ Page Frame Allocation

• LRU, LFU 모두 프로세스 별 메모리에 대해서는 관심이 없고
• 단순히 참조시간이 가장 오래된 페이지/가장 참조횟수가 적은 페이지를 삭제하는 것에만 집중
• ❓ 그런데 만약 메모리에 프로세스 별로, 프로세스A 페이지는 비우고, 프로세스B 페이지는 유지하고 싶으면 어떡하지?

☑️ Allocation Problem

• 각 process에 얼만큼의 page frame을 할당할 것인가?
• 각 process 별로 메모리를 다르게 할당하겠다.
• process A는 메모리 5개, process B는 메모리 10개 이런식으로

☑️ Allocation의 필요성

• Page Frame Allocation이 왜 필요한가?

• 메모리 참조 명령어 수행시 code, data 등 여러 페이지 동시 참조
• 명령어 수행을 위해 최소 할당되어야 하는 frame의 수가 있음

• 각 프로그램마다 메모리를 어느정도는 최소한으로는 가지고 있어야 실행이 원할함

• 반복문 LOOP을 구성하는 page들은 한꺼번에 allocate되는 것이 유리하다
• 최소한의 allocation이 없으면 loop마다 page fault발생

☑️ Allocation scheme

• ✔️ Equal allocation: 모든 프로세스에 똑같은 page 갯수 할당
• ✔️ Proportional allocation: 프로세스 크기에 비례하여 page 할당
• ✔️ Priority allocation: 프로세스 CPU priority애 따라 page 다르게 할당

Global 🆚 Local Replacement

• ✔️ Global Replacement
• 전체 메모리를 각 프로세스가 공유, 프로세스마다 할당되는 메모리 양은 가변적으로 변한다
• 각 프로세스에게 별도의 page할당 없음
• replace시 다른 process에 할당된 frame을 빼앗아 올 수 있다
• 모든 frame이 교체 대상이 된다
• FIFO, LRU, LFU등의 알고리즘을 Global Replacement로 사용시에 해당
• working set, PFF알고리즘 사용
• 👍🏻 프로세스 간 메모리를 가지고 무한경쟁
• 👍🏻 내가 메모리가 많이 필요한 프로세스라면 경쟁 통해 더 많이 얻을 수도 있음
• 👎🏻 특정 프로세스가 메모리를 독식할 수도 있음

• ✔️ Local Replacement
• 각 프로세스에게 각자의 page할당해주고, 그 내에서 replace
• 자신에게 할당된 frame 내에서만 replace
• 프로세스 너에게 할당된 양 내에서 알아서 replace해라
• FIFO, LRU, LFU등의 알고리즘을 process별로 독자적으로 운영한 경우

✅ Thrashing

프로세스의 원할한 수행에 필요한 최소한의 page frame수를 할당받지 못한 경우 발생
when degree of multiprogramming is too high, CPU utilization drops

• 프로세스가 수행되기 위해서는 일정 수준 이상의 page frame을 할당 받아야 하는데,

• 최소한의 page frame도 할당받지 못한 상태를 Thrashing이라고 한다

• page fault rate 매우 높아짐 ⬆️
• CPU utilization 낮아짐 ⬇️

• 👎🏻 low throughput ⬇️

• 💡 MPD(Multiprogramming degree): 메모리에 올라가 있는 프로세스의 수

OS는 CPU utilization이 낮아지면 메모리에 올라와 있는 프로세스가 적어서 그렇다고 판단
ready queue에 프로세스가 단 하나라도 있으면 CPU가 그 프로세스를 실행할텐데,
CPU utilization이 낮다는 것은 ready queue에 프로세스가 하나도 없다는 뜻
이는 메모리에 올라와 있는 프로세스의 수가 너무 적어
이 프로세스들이 I/O를 하러 가서 ready queue가 비었다는 의미
CPU utilization이 낮으면  MPD를 높여야 한다
OS는 MPD를 높이기 위해 메모리에 올라가는 프로세스를 더 추가

Thrashing때문에 CPU utilization이 낮은건데,
OS는 프로세스가 없어서 CPU utilization이 낮다고 생각해 프로세스를 더 추가

하지만  MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양 지나치게 감소
프로세스 당 할당된 page frame는 더욱 감소
프로세스는 원할하게 수행되기 위해 필요한 최소한의 page frame도 받지 못해 page fault발생
프로세스는 page의 swap in/swap out으로 I/O하느라 매우 바쁨
page fault가 발생하면 디스크 I/O해야 하므로 context swithcing이 일어나 다른 프로세스에게 CPU이양
다른 프로세스도 할당된 메모리 양이 적으니 page fault 발생

모든 프로세스가 page fault 발생
시스템은 page fault를 처리하느라 분주하고, CPU utilization은 낮아진다
OS는 CPU utilization이 낮은걸 보고 MPD를 높이기 위해 또 다른 프로세스를 메모리에 추가

• multiprogramming: number of program on memory
• CPU utilization: how much CPU is used

메모리에 프로그램이 1개 올라가 있을 때 ➡️ 그 프로그램이 I/O하러 가면 CPU는 할 일이 없음 ➡️ CPU utilization 👎🏻
메모리에 프로그램이 2개 올라가 있을 때 ➡️ 프로그램 하나가 I/O하러 가도 다른 프로그램 실행 ➡️ CPU utilization 👍🏻
메모리에 프로그램이 적당량 여러개 올라가 있을 때 ➡️ CPU utilization 👍🏻

메모리에 프로그램이 너무 많이 올라가 있을 때 ➡️ 각 프로그램이 실행하기 위한 최소한의 메모리도 얻지 못하는 상황 ➡️ CPU utilization 👎🏻
각각의 프로그램이 메모리가 없어 다 page fault나는 상황 ➡️ CPU utilization 👎🏻
➡️ Thrashing

• 따라서 Thrashing이 발생하지 않도록 하면서 CPU utilization을 높일 수 있도록 MPD를 조절하는게 중요
• Thrashing 방지 방법
  • ✔️ Working Set Model
  • ✔️ Page Fault Frequency scheme

✅ Working Set Model

💊 Thrashing 방지
locality set(working set)이 메모리에 올라갈 수 있도록 보장

☑️ Locality of reference

• 프로세스는 특정 시간 동안 특정 메모리(일정 장소)만을 집중적으로 참조하는 경향이 있음
• (Locality of reference)
• locality set(working set): 집중적으로 참조되는 해당 page이 집합

☑️ Working Set model

• locality에 기반하여
• 프로세스가 일정 시간동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 working set이라고 정의
• locality set(working set) 모델에서는 process의 working set 전체가 메모리에 올라갈 수 있는 경우에만 프로세스에게 메모리 할당

• 그렇지 않을 경우 모든 프로세스에게 할당된 모든 frame을 반납하고 그 프로세스의 주소 공간 전체를 디스크로 swap out, suspend됨

• 프로세스가 실행될 수 있는 최소 메모리는 보장해주자
• locality set은 적어도 메모리에 보장을 해 주자

예를 들어 프로그램A가 메모리에 올라가고자 하는데 locality set(working set)이 10임
그런데 메모리에 frame 5밖에 없음
그러면 메모리에 못 올라가게 한다
오히려 지금 가지고 있는 메모리 공간 빼았고, swap out, suspend
그리고 메모리에 공간이 생겨 10을 보장받을 수 있으면 메모리를 다시 할당받는다

• 💊 MPD조절
• 💊 Thrashing 방지
• 👍🏻 Multiprogramming degree를 결정함

✅ Working Set Algorithm

☑️ Working Set의 보장

• Working Set window를 통해 알아냄
• 과거에 △만큼 사용한 전적을 고려해서 window size를 설정
• window size가 △인 경우
  • 시각 ti에서의 working set WS(ti)을
    • time interval[ti-△, ti]사이에 참조된 서로 다른 페이지들의 집합으로 정의
    • ti시점에 working set에 포함된 페이지는 메모리에 유지
    • 그렇지 않은 페이지들은 메모리에서 쫒겨님
    • working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림
  • 즉, page가 참조된 후 △ 시간동안은 해당 page를 메모리에 유지
  • 그 시점이 지난 후 메모리에서 지워버림

☑️ 그림으로 살펴보기

• 현재 시점에 과거를 살펴보니 window size를 5개를 사용했으니
• window size를 5로 설정하고
• 메모리에는 {1, 2, 5, 6, 7}을 올려준다

☑️ Working Set window의 크기

• 메모리에 올라와 있는 프로세스들의 working set 크기의 합이
• frame의 수보다 큰 경우
• 일부 프로세스를 swap out
• 남은 프로세스의 working set이 메모리에 모두 올라가는 것을 보장

• 👍🏻 MPD 감소

• 반면 working set이 남는 경우
• swap in해서 프로세스를 다시 메모리에 올림
• working set 할당

• 👍🏻 MPD 증가

• 만약 window size인 △가 너무 작으면
• locality set(working set)을 모두 수용하지 못할 수 있음
• 만약 window size인 △가 너무 크면
• MPD가 감소해 CPU utilization감소

• 따라서 window size를 잘 결정하는 것이 중요

• working set의 크기는 시간에 따라 변한다
• 따라서 프로세스가 메모리를 많이 필요로 하면 working set 많이 할당,
• 적게 필요로 할 때는 적게 할당해 동적인 프레임 할당이 가능하다

✅ PFF Scheme

💊 Thrashing 방지
Page Fault Frequency Scheme
비율 page fault rate을 주기적으로 조사해 각 프로세스에 할당할 메모리 양 동적으로 조절

• 특정 프로그램 page fault rate의 상한값과 하한값을 둔다.

  • page fault rate이 상한값을 넘으면 그 프로그램에게 frame을 더 할당한다
    • 이 프로세스에게 할당된 frame의 수가 부족하다고 판단
  • page fault rate이 하한값 이하이면 그 프로그램의 할당 frame을 줄인다
    • 필요 이상으로 많은 frame이 할당되었다고 간주
  • page fault rate이 두 선 사이에 들어올 수 있도록 노력
• 빈 frame이 없으면 일부 프로세스를 swap out해서 메모리에 올라와 있는 프로세스의 수 조절

• 이런 방식으로 메모리 내 프로세스에게 필요한 frame을 다 할당한 후에도 frame이 남으면 swap out되었던 프로세스에게 frame 할당하여 MPD높이기

• 💊 thrashing 방지
• 💊 CPU utilization ⬆️

✅ Page size의 결정

• 32bit환경에서 Page size는 4KB

• Page size를 감소시키면 ⬇️
• 페이지 수 증가 ⬆️
• 👎🏻 페이지 테이블 크기 증가 ⬆️
• 👍🏻 internal fragmentation 감소 ⬇️ 메모리에서 낭비되는 공간 감소 ⬇️
• 👎🏻 Disk transfer의 효율성 감소 ⬇️
  • Disk에서 작은 Page size 조금조금씩만 읽어오기 때문에
  • page fault가 자주 일어남
  • seek/rotation 🆚 transfer
• 👍🏻 필요한 정보만 메모리에 올라와 메모리 이용이 효율적

• 👎🏻 locality이 활용 측면에서는 좋지 않음

• 요즘 추세: larger Page size