• 참고

Memory

<aside> 💡 NOTE

주소변환은 운영체제가 관여하지 않았는데, virtual memory 기법은 전적으로 운영체제가 관여한다.

실제로 필요할 때 page를 메모리에 올린다. = Demand Paging

• I/O 양의 감소

• memory 사용량 감소

• 더 빠른 응답 시간

• 더 많은 사용자 수용

  

• 필요한 A,C,F는 물리적 메모리에 올라가있고, 아닌 부분은 backing store에 내려간다.

• 처음에는 page entry가 모두 invalid로 초기화되어 구성되지만

• address translation(주소 변환)시에 invalid bit이 set되면 page fault가 발생합니다. trap이 생기면 Page Fault 단계에 따라 구성됩니다.

• 사용자 프로세스가 해당되지 못해 OS로 cpu 제어권이 넘어가게 됩니다.(trap 발생)

Page Fault 단계

invalid page를 접근하면 MMU가 트랩을 발생시킵니다. 이후 커널 모드로 들어가서 page fault handler에 의해 invoke됩니다.

1. 잘못된 요청인지 확인 → 잘못 되었으면 process abort
2. 빈 page frame을 가집니다. 없으면 replace 뺏어서 가져옵니다.
3. 해당 page를 disk에서 메모리로 가져옵니다.(가장 우선순위가 높은 ready queue로 부여)
4. disk를 읽으면 page table entry로 valid 기록
5. ready queue의 process를 insert에서 dispatch 로 변경
6. 중단된 process 다시 처리

Performance of Demand Paging

하지만 이런 page fault 처리로 disk에 접근하는 것은 시간을 많이 소모하는 작업이다. 또한 overhead가 매우 크다.

따라서 처리하는 시간과 접근 시간의 비율을 계산해서 효율적인 값으로 비율을 맞춘다.

Free frame이 없는 경우

page replacement

• 어떤 프레임을 빼앗아 올지 결정
• 동일한 page가 여러번 메모리에서 쫒겨났다가 read할 수도 있다.
• 0.1 이렇게 매우 작은 값으로 나오도록 만든다.

replace 알고리즘

• page-fault rate를 최소화하기 (목표)
• 알고리즘 평가
  • 주어진 page reference string에 대한 page fault를 조사

Page Replacement

valid, invalid를 통해서 관리하는 방법

메모리에서 swap in, out을 OS에서 처리해준다.

알고리즘

optimal : 미래의 순서를 알고있다고 가정, 가장 먼 미래에 참조되는 page로 대체하는 것 → 실제로 구현은 할 수 없지만 잘 만든 알고리즘의 page faults 최소 기준을 알려준다.

fifo : 선입 선출, 메모리 프레임을 늘려줘도 성능이 오히려 나빠지는 성질을 가진다.

lru(Least Recently Used) : 가장 오래전에 참조된것을 먼저 지운다.

lfu(Least Frequently Used) : 참조 횟수가 가장 적은 page를 먼저 지운다.

장점 : LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기에 page의 인기도 정확하게 반영 단점 : 참조 시점의 최근성을 반영하지 못한다. LRU보다 복잡하다.

어떤 메모리를 쫒아낼지에 대한 알고리즘

LRU : 한줄로 줄세우기→ 쫒아낼 것은 가장 위에서 보내고 가장 최근에 참조한 것은 가장 밑으로 보내는 것(모두 확인 안하고도 보낼 수 있다.)

LFU : 참조횟수가 1늘어나면 다른 값보다 참조횟수가 많아야 내려가므로 모두 확인할 필요가 있다. 따라서 힙을 통해 관리를 하는 방식(트리) - 부모가 자식보다 참조횟수가 많으면 자식으로 내려가는 것 O(log n)에 가능하다.

</aside>

Virtual Memory2

<aside> ✍️ NOTE

• Virtual Memory뿐만아니라 Cashing에서도 알고리즘을 사용한다.
• 캐싱기법

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

  • 캐시 메모리 - cpu에서 메모리 접근할 때 백엔드에서 주로 사용

    

    

    • redis 적용 했을 때

  • 버퍼 캐시 - 디스크의 파일 시스템 → 다음 챕터에서 설명

  • 웹 캐싱 - 웹 캐싱은 웹 페이지나 리소스를 임시로 저장하는 메커니즘입니다. 이는 사용자가 요청한 리소스를 빠르게 제공하기 위해 사용됩니다. 일반적으로 웹 캐싱은 클라이언트 측이나 중간 프록시 서버에 의해 수행됩니다. 캐싱은 주로 정적 콘텐츠(이미지, 스타일 시트, 자바스크립트 파일 등)에 대해 적용되지만, 동적 콘텐츠를 캐싱하는 경우도 있습니다.

• paging system에서 LRU, LFU 적용이 가능한가?

invalid인 경우 page fault 발생 → trap → OS → disk에 있는 메모리를 가상 메모리로 올려준다.

OS에서는 cpu 내부에서 처리하는 것을 관리할 때 OS에 넘어오지 않은 상태에서 처리를 해버리기 때문에 적용할 수 없다.

LRU, LFU 는 웹 캐싱, 버퍼 캐싱 같은 것에서는 사용할 수 있다.

Clock 알고리즘

하드웨어가 참조값이 최근에 사용되면 reference bit의 값을 1로 바꾼다.

그리고 page fault가 발생했을 때 OS에서 reference bit을 확인하고 bit 값을 0으로 바꾼다. 그리고 사용하지 않은 값들을 쫒아낸다.

modify bit은 수정을 했다면 modify bit을 1로 바꾸고 OS에서 확인할 때 같이 확인해서 값을 변경도 해준다.

page fault가 너무 자주 발생하면 스레싱이 발생한다.

프로그램을 여러개 올리게 되면 cpu 사용량이 증가한다.

하지만 어느정도 값을 넘으면 뚝 떨어지낟.

메모리 할당량이 너무 낮아지게되면 page fault가 너무 많이 발생해서 제대로 업무를 못하는 것 → swap in/out에 시간 대부분을 소모

degree의 값을 조절해서 사용하는 방법을 통해 방지할 수 있다.

working set model

한번에 여러 개의 최소 값을 받아서 처리하게된다.

하지만 그 페이지를 받을 수 없다면 모두 반환해서 받을 수 있을 때까지 suspend상태로 유지한다.

</aside>