Virtual Memory

Demanding Paging

• 정의
  • 페이지 레벨의 스와핑
  • 필요 할 때만 메모리에서 가져옴
    • 스와핑은 프로세스 단위로 움직이지만 디멘드 페이징은 페이지 레벨이라는 것의 차이가 있음
  • OS는 시스템내에 프로세스에 의해서 할당된 모든 데이터의 페이지 캐시로서 메인 메모리를 사용함
    • 페이지를 할당 받을 때는 물리적 메모리 프레임에서 할당을 받음
    • 물리 메모리가 모두 찾는데도 불구하고 새로운 페이지를 할당 해야 하면 이빅트(Evict)를 하여 메모리를 확보함.
  • 이빅트된 페이지는 디스크로 감
    • 물론 더티인 상태에서만 쓰일 필요가 있음
    • 스왑 파일로 감
    • 메모리와 디스크 사이의 페이지 이동은 OS에 의해서 이루어짐
    • 어플리케이션에게는 Transparent 함.
• Page faults
  • 이빅트 된 페이지의 Virtual Address를 참조하는 프로세스에게 일어나는 현상
    • 페이지가 이빅트 되었을 때는 OS는 PTE를 Invalid로 처리하고 해당 페이지의 스왑 파일의 위치를 저장함.
    • 프로세스가 이 해당 이빅트 된 페이지를 참조하면 PTE에서는 Invalid이므로 익셉션을 던진다.
  • OS는 익셉션에 응답으로서 페이지 폴트 핸들러를 실행 시킨다.
    • 핸들러는 Invalid PTE의 스왑 파일의 페이지 위치를 사용
    • 핸들러는 Physical frame으로 페이지를 읽어서 PTE를 그것을 가리키게 하고 Valid로 변경하여 업데이트 한다.
    • 핸들러는 fault된 프로세스를 다시 시작 시킨다.
  • 어디다 읽어 올 것인가?
    • 페이지가 꽉 찬 상태라면 다른 것을 page replacement algorithm으로 이빅트 시킨 뒤 읽어옴
    • OS는 전형적으로 이빅트를 야기시키지 않고 바로 할당을 하기 위해서 Free 페이지 들에 대한 풀을 유지하고 있음
    • 
• 왜 디멘드 페이징을 쓰는가?
  • 로컬리티
    • Temporal locality : 최근에 레퍼런스 한 위치를 다시 레퍼런스 할 가능성이 높음
    • Spatial locality : 레퍼런스 된 장소의 근처 위치들은 빠른 시일 내에 레퍼런스 될 가능성이 높음
  • 로컬리티가 있다는 이야기는 페이징이 자주 일어 나지 않는 다는 것을 의미함
    • 한번 페이지를 로드 하고 나면 그것은 여러 번 사용 될 수 있음
    • 디멘드 페이징은 많은 것을 고려 해야 하는 단점이 있음
      • 어플리케이션의 로컬리티 degree를 고려해야 함
      • Page replacement policy를 정해야 함
      • Physical memory의 양을 고려 해야 함
      • 어플리케이션의 패턴이나 메모리의 풋 프린터를 잘 고려해야 함
• 왜 "demand" 인가?
  • 프로세스가 처음 시작 되면 모든 PTE가 invalid인 페이지 테이블을 할당함
    • 물리 메모리로 어떠한 매핑도 없음.
  • 프로세스가 시작 하면 이때 할당됨
    • 인스트럭션은 코드와 데이터 페이지에서 즉각적으로 폴트 유발
    • 폴트는 필요한 코드와 데이터를 페이지를 페이지 인 할 때 까지 정지됨
    • 오직 프로세스의 필요에 의해 코드와 데이터가 demanded일 때 메모리로 로드 됨

Page Tables

• Managing page table
  • 페이지 테이블 공간에 대한 오버헤드
    • 페이지 4KB를 가지는 32비트 어드레스 공간의 페이지 테이블 사이즈는 4MB
    • 프로세스당 이므로 용량이 큼
  • 오버헤드를 줄이는 방법
    • 실제 사용되는 주소 공간에 대해서만 맵을 할당함.
    • 전체 공간의 일부로 (Fraction) 유지.
  • 어떻게 사용되는 영역에 대한 맵만 유지 할 수 있는가
    • 페이지 테이블을 다이나믹하게 확장 가능하도록 만듦
    • Indirection 레벨을 통해서
      • 2레벨, 하이라키컬, 해시등..
      • 
• Two-level page table
  • Virtual address는 3파트로 구성
  • 
  • 마스터 페이지 테이블은 마스터 페이지 넘버를 세컨더리 페이지 테이블로 매핑
  • 세컨더리 페이지 테이블은 세컨더리 페이지 넘버를 페이지 프레임 넘버로 매핑
  • 
• Multi level Page Tables
  • AXP 아키텍쳐의 예
    • 3레벨의 페이지 테이블을 가지고 있음
    • 64비트 어드레스가 3개의 세그먼트로 분리
      • Seg0 - 유저 코드
      • Seg1 - 유저 스텍
      • Kseg - 커널
    • 
• Hashed Page Tables
  • 정의
    • 어드레스 공간이 32비트 보다 클 때
      • 32비트 보다 클 때 왜 필요한가?
        • 한 페이지 안에 페이지 테이블을 넣을 수 있으면 메모리 접근 면에서 속도 gain이 있음
        • 4byte를 한 엔트리로 할때 1024의 엔트리를 구성 할 수 있고 이는 주소 공간에서 10비트를 차지 하게 됨.
        • 64비트 주소 공간 중 52비트를 주소를 가리키는데 사용 한다고 가정하면 10으로 나누어 총 6레벨의 페이지 테이블이 필요하게 됨
        • 이는 6번의 메모리 액세스를 참고로 하므로 이를 피하기 위해 해시 테이블을 사용.
    • VPN 은 해시테이블에 해시 되어 넣어짐
    • 각각의 해시 테이블 엔트리는 엘리먼트 리스트를 가지고 있음
    • 각 엘리먼트는 다음과 같은 항목을 가짐
      • VPN
      • 매핑 된 페이지 프레임 값
      • 다음 엘리먼트의 포인터.
    • 
  • 클러스터된 페이지 테이블들
    • 다양한 해시 페이지 테이블은 각각의 연속적인 페이지 테이블의 매핑 정보를 저장하고 있음.
    • VPBN로 해시를 하여 클러스터된 페이지 테이블을 가지고 오면 그 내에 블락 오프셋을 이용하여 실제 페이지 번호를 구할 수 있음.
    • 
• Inverted Page Tables
  • 실제 메모리의 페이지가 하나의 엔트리가 됨.
  • 실제 메모리 페이지인 하나의 엔트리는 VPN과 프로세스 정보가 저장 되어 있음
  • 일반적으로 VPN이 인덱스가 되고 그 내에 매핑된 PPN이 기술 되는데 이는 VPN이 제공하는 공간 만큼의 엔트리가 필요 하게 되므로 페이지 테이블이 커짐 이에 반해 IPT는 VPN을 저장하고 인덱스가 PPN이 되므로 실제 물리 메모리 사이즈 만큼의 엔트리만 존재 하면 되므로 페이지 테이블 사이즈가 매우 작음
  • 대신에 페이지를 찾기 위해 검색 시간이 들어가고 메모리 접근이 많아짐.
  • 이것을 해결 하기 위해서 Hashed Inverted Page Tables을 쓰거나 TLB와 같은 하드웨어 도움을 받음.
  • 
• Paging Page Tables
  • 페이지 테이블 자체에 대한 어드레스 고민
    • 페이지 테이블을 어디다 저장 할 것인가?
    • Physical Memory
      • 물리 메모리에 바로 저장하는 경우 주소 변환이 필요 없기 때문에 빠르고 쉬움
      • 하지만 물리 메모리를 바로 쓴다는 것은 그 만큼 VAS의 엔트리들이 물리 메모리 공간을 확보 못하기 때문에 빨리 이빅트 되고 이는 VAS의 라이프 타임을 줄이게 됨
    • Virtual Memory
      • 콜드 페이지 테이블의 페이지는 디스크로 페이지 아웃 시킴
      • 페이지 테이블을 참조 하기 위한 주소 번역 오버헤드가 존재.
      • 와어링을 위한 Outer 페이지 테이블이 필요 없음(다시 말해서 MSB 몇 비트를 통한 상위 레벨의 페이지 테이블이 필요 없는 것인데 이는 선형 메모리 주소를 보장 하기 때문에 한번에 엑세스가 가능해서라고 생각 됨, 만약 물리 메모리 공간에서도 마찬가지로 선형 메모리 주소를 보장한다면 충분히 가능)
  • 결국 페이지 테이블이 OS가 관리하는 VAS안에 저장되는 것임.
• TLB
  • 주소 변환의 효율성을 제공
    • 원래 페이지 테이블 스킴은 메모리 룩업의 코스트가 더블로 들어감
      • 한번은 페이지 테이블을 룩업 하는 것이고 다른 하나는 데이터를 패치 하는 것이다.
    • 2 레벨 페이지는 3배 코스트가 든다.
      • 페이지 테이블이 메모리 있다고 가정 했을 때 두 번은 페이지 테이블 룩업이고 세 번째는 데이터 패치이다.
    • 어떻게 하면 효율적으로 만들 수 있나?
      • Goal - Virtual address에서 패칭 하는 것도 Physical address를 패칭 하는 것 만큼이나 빠르게 해야 한다.
      • Solutions
        • V2P 번역을 하드웨어 캐시를 통해서 한다.
        • Translation Lookaside Buffer
        • TLB는 MMU에 의해서 관리 됨.
  • Translation Lookaside Buffers
    • VPN을 PTE에서 번역함.
    • 싱글 머신 사이클에 끝날 수 있음
    • 
  • TLB는 하드웨어에 구현됨
    • 모든 엔트리는 병렬 룩업이 가능한 Fully associative cache.
    • Cache tag는 VPN임.
    • 캐시의 값은 PTEs
    • PTE + offset를 통하여 MMU는 바로 물리 메모리의 주소로 변환 할 수 있다.
  • TLB는 로컬리티를 이용함(Exploit)
    • 프로세스는 정해진 시간에 몇 개의 페이지들만 사용함
      • TLB의 16-48엔트리가 일반적임(64-192KB)
      • 프로세스의 핫 셋이나 워킹 셋을 유지 할 수 있음
    • 히트 Rate는 매우 중요함.
  • 
  • TLB 미스에 대한 핸들링
    • 주소 번역은 TLB에 의해서 핸들링 됨.
      • 번역의 99% 번역이 가능 하지만 때때로 TLB도 미스 나는 경우가 있음
      • 미스가 나는 경우에 누가 TLB로 Translation을 대체 해줄 것인가?
    • 하드웨어
      • MMU
      • 메모리에 페이지 테이블이 어디에 있는 지 알고 있음
      • OS가 테이블을 관리하고 하드웨어는 직접 접근 함.
      • 페이지 테이블은 하드웨어로 정의되어 있어야 함.
    • 소프트웨어가 TLB 로드 함.
      • TLB가 미스 fault가 나는 경우에 OS가 적절한 PTE를 찾아서 TLB로 로드함.
      • 반드시 빨라야 한다(그러나 일반적으로 20 ~ 200 사이클을 먹음)
      • CPU, ISA는 TLB 조작을 위한 인스트럭션 셋을 따로 가진다.
      • 페이지 테이블은 OS의 편의를 위하여 어떤 포맷으로도 가능해야 한다.
  • TLB들 관리
    • OS는 페이지 테이블과 TLB의 의 컨시스턴시를 유지 해야 한다.
      • OS가 PTE의 Protection bit를 변화 시키면 그 PTE가 TLB에 있을 경우 반드시 Invalidation 시킬 필요가 있다.
    • 프로세스의 컨텍스트 스위칭이 발생할 때 TLB는 리로드 되어야 함
      • 프로세스는 일반적으로 하나 마다 자신의 페이지 테이블을 가지고 있으므로 컨텍스트 스위칭 시 TLB를 모두 플러시 해야 할 필요가 있다.
      • IA32에서는 CR3(페이지 디렉터리 베이스 레지스터)의 컨텐츠가 변화할 경우 TLB가 자동으로 플러시 됨.
      • 플러시 대신에 TLB 엔트리에 PID를 저장 해놓고 플러시 하지 않을 수 있음.
    • TLB가 미스 되면 새로운 PTE는 로드 되고 캐시된 PTE가 이빅트 될 수 있다.
      • PTE 빅팀을 선택 하는 것을 TLB Replacement policy라고 부름
      정책은 하드웨어로 구현 되어 있으며 일반적으로 LRU와 같이 간단하게 구현 되어 있음.
    
    

    Memory Reference

  • Situation
    • CPU에서 프로세스가 실행 중이고 프로세스가 virtual address를 읽으려고 시도 했을 때
    • 
  • Common case
    • MMU 안에 TLB를 읽음
    • TLB는 VPN을 사용하여 룩업을 시도함.
    • VPN이 매칭 되는 경우 해당 PTE를 찾음
    • TLB는 PTE의 Protection이 read를 허용하는지 검증함.
    • PTE에 명세 되어 있는 Physical frame과 offset을 이용하여 Physical address를 계산
    • MMU는 Physical address를 읽어서 값을 CPU에게 리턴 해준다.
  • TLB가 미스 났을 때
    • MMU는 메모리의 페이지 테이블로 부터 TLB를 로드하는 경우
      • 이 경우는 하드웨어가 TLB를 관리하고 OS는 이 단계에 간섭하지 않음.
      • OS는 이미 페이지 테이블을 셋업 해놓았기 때문에 하드웨어가 직접적으로 액세스 할 수 있음
    • Trap이 OS로 가능 경우
      • 소프트웨어 TLB를 관리함. 이 경우에는 OS가 이 시점에 관여함.
      • OS는 페이지 테이블을 룩업하고 PTE를 로드하여 TLB에 놓음
      • OS는 익셉션 상황에서 리턴하고 TLB는 계속 동작함.
  • TLB가 미스 났을 때 복잡해 보이는 경우.
    • 리커시브 페이지 폴트가 존재 하는 경우
      • 페이지 테이블 룩업은 페이지 테이블 자체가 페이지 아웃 되어 있을 때 리커시브하게 폴트가 생길 수 있음
      • 페이지 테이블이 OS에서는 VAS안에 존재 하기 때문에
      • 만약 Physical 메모리에 테이블을 두는 스킴의 경우는 문제가 없음
    • TLB가 PTE를 로드하고 번역을 재시작 하면 되는데 이때도 두 가지의 케이스가 존재.
      • 일반적인 케이스에 PTE는 메모리의 유효한 페이지를 참조함.
      • 특이한 케이스에서는 TLB가 PTE의 Protection 비트 때문에 PTE에서 폴트를 다시 냄.
  • 페이지 폴트
    • PTE가 프로텍션 폴트를 가리킬 수 있음.
      • 정책이 아니라 Invalid였다면 Virtual page 자체가 할당이 되지 않았거나 페이지가 물리 메모리에 없는 경우임
    • TLB가 OS에게 트랩하는 경우
      • Read / Write / Execute의 정책이 다른 경우 일반적으로 프로세스에게 다시 폴트를 보내거나 또는 트릭을 써서 진행 하기도 한다. (트릭이라고 함은 copy on write, mapped file등을 말함)
      • 할당 되지 않은 경우의 invalid일때는 OS는 프로세스에게 폴트를 보냄 (세그멘테이션 폴트)
        (할당이라는 단어를 사용 하고 있지만 주소 자체가 invalid인 경우로 abort인 상황이라고 판단)
      • 물리 메모리에 없는 경우의 Invalid일 때에는 OS는 프레임을 할당하고 디스크에서 리드를 하여 PTE를 Physical frame으로 맵핑 시킨다.
  • Physically addressed caches
    • 다수의 프로세스가 캐시에서 같은 시간에 블록 되는 것을 허용함
    • 다수의 프로세스가 페이지를 공유할 수 있음.
    • 캐시는 프로텍션 이슈를 고려 할 필요가 없음. (TLB 아래에 있으므로)
    • Address translation이 크리티컬 패스임.
    • 
  • Virtually addressed, Virtually tagged caches
    • 주소의 시너님(Synonyms)이나 엘리어스 문제가 있음
      (Virtual address가 각 프로세스마다 있으므로)
      • 소프트웨어 솔루션으로는 프로세스가 스위칭 될 때 마다 캐시를 플러시 한다.
      • 하드웨어 솔루션은 키핑 할 수 있는 위치를 모두 찾는 것.
    • 
  • Hybrid (Virtually addressed, physically tagged caches)
    • Virtual address를 가지고 TLB와 캐시를 병렬적으로 접근함.
    • Offset은 VA,PA모두 같다는 것을 사용함.
    • 

  Page Replacement

• 정의
  • 페이지 폴트가 나면 OS는 폴트 된 페이지를 디스크로 부터 읽어서 메모리의 페이지 프레임에 로드 해야 함
  • 이 시간에 프로세스의 모든 페이지 프레임이 사용되고 있다면 OS는 페이지 인 된 페이지를 리플레이스 해 야함
  • 다시 말해 Free 페이지 프레임을 확보 하기 위해 페이지를 이빅트 해야 하고 이때 페이지 리플레이스먼트 알고리즘이 이를 결정함.
• Evicting 베스트 페이지.
  • Replacement algorithms의 목표는 베스트 빅팀 페이지를 선택하여 폴트 Rate를 떨어 드리는 것임
  • 이빅트 할 베스트 페이지라는 것은 다시는(Never) 터치 되지 않을 페이지를 의미함.
    • 그렇다면 프로세서는 다시는 폴트가 나지 않을 것임
  • Never는 매우 긴 시간을 의미함. 그렇기 때문에 Page replacement는 이것에 가장 근접하도록 페이지를 선택 함.
    • Belady의 proof - 프로세스가 오랜 기간 동안 사용하지 않을 페이지를 이빅트 하는 것이 페이지 폴트 숫자를 최소화 하는 것임.
• Belady's 알고리즘
  • 미래에 오랜 시간 동안 사용되지 않을 페이지를 리플레이스 하는 것임
  • 가장 낮은 폴트 rate를 가짐
  • 미래를 예측 할 수 없으므로 쓸모가 없으나 기준(Yardstick)이 될 수 있음
    • 다른 알고리즘과 비교할 때 척도가 됨
• FIFO
  • 명백하고 구현이 쉬움
    • 들어온 순서대로 리스트만 유지하면 됨
    • 리플레이스 시에 가장 오래된 페이지를 이빅트 하면 됨
  • 가장 오래된 페이지에 대한 정책
    • 가장 오래된 것이 가장 안 쓰일 가능성이 높음
    • 정확한 케이스가 아님,
  • FIFO는 Belady's Anomaly를 가지고 있음
    • 메모리가 많이 주어지면 폴트 비율이 높아진다.
    • 

       

    • 
• LRU
  • Least Recently Used
    • 페이지 교환을 위해 LRU는 레퍼런스 정보를 이용하여 결정함
    • 기본 아이디어는 과거의 경험을 통해서 미래의 비헤비어를 추측 할 수 있음
    • 과거에 가장 적게 사용된 페이지를 이빅트 함
    • Belady는 미래를 살피길 원했지만 LRU는 과거를 살핌
  • Implementation
    • 완벽을 기하기 위해서는 매 레퍼런스에 대한 타임 스탬프가 필요하고 스택에 그 정보를 저장하기나 PTE에 넣어주어야 함
    • 이러한 기법은 비용이 비싸기 때문에 대략적인 방법을 사용하기도 함(Approximate)
  • Stack 알고리즘
    • 스택에 최 상위에는 가장 최근에 레퍼런스 된 페이지 정보를 유지 시킴
  • ALRU
    • Approximating LRU
    • PTE의 Reference bit을 이용하여 LRU를 대략적으로 구현함
    • 카운터 베이스드 어프로치
      • 각 페이지 마다 카운터를 유지
      • 매 정기적인 인터벌 마다 R비트를 참조함
      • 만약 R비트가 0이라면 카운터를 증가 시키고 1이라면 감소 시킴.
      • 결국은 가장 큰 값을 가지는 페이지가 가장 적게 사용된 페이지가 됨
    • 특정 아키텍쳐는 reference 비트가 없음
      • 폴트를 야기 하기 위한 valid 비트를 사용하여 레퍼런스 비트를 시뮬레이션 함.
• Second Chance
  • 최근에 레퍼런스 된 페이지에 대하여 세컨드 찬스를 부여하는 FIFO임.
  • 클럭이라고 부르는 큰 원에 물리 페이지 프레임을 배열 시킴
  • 클럭 핸드는 LRU 후보를 가리키고 있음
    • 클럭 핸드는 클럭의 오더와 같게 페이지들을 쓸고 지나감
    • 레퍼런스 비트가 꺼져 있으면 최근에 사용 되지 않은 것으로 빅팀 선정
    • 레퍼런스 비트가 켜져 있으면 꺼버리고 다음 페이지로 이동
  • 메모리가 풍부하면 오버헤드는 줄어듦, 메모리가 크면 정보의 정확성이 떨어짐.
  • 
• NRU Not Recently Used
  • NRU 는 메모리에 최근에 사용된 페이지를 키핑하는 것을 목적으로 한다
  • 알고리즘의 정책
    • 페이지가 레퍼런스 되면 페이지에 대한 레퍼런스 비트를 세팅
    • 마찬가지로 페이지가 수정되면 Modified 비트가 세팅
      (이 두 가지는 하드웨어에 의해 이루어짐)
    • 고정된 인터벌 시간에 트리거 된 인터럽트 때 모든 레퍼런스 비트를 클리어 시킴
    • 결국은 현재 클락 인터벌 내에 참조된 페이지들만 레퍼런스 비트를 유지함.
    • 리플레이스는 아래 순서로 빅팀으로 선정
      • 클래스 0, 레퍼런스가 안되고 수정도 안됨
      • 클래스 1, 레퍼런스가 안되고 수정이 됨
      • 클래스 2, 레퍼런스 되고 수정이 안됨
      • 클래스 3, 레퍼런스 되고 수정됨.
    • 
  • 이점
    • 이해하기 쉬움
    • 구현이 효율적임
    • 옵티멀은 아니지만 적절한 퍼포먼스를 유지함.
• LFU
  • Least Frequently Used
  • 카운팅 기반의 리플레이스먼트
    • 각 페이지 마다 소프트웨어 카운터가 있음
    • 각 클락 인터럽트마다 각 페이지의 R비트가 카운터에 첨가된다. (시프트)
    • 카운터는 얼마나 자주 참조 되었는지를 가르쳐 준다.
    • 리플레이스는 카운터가 가장 작은 페이지가 인빅트 되는 방식
      • 만약 MFU였다면 가장 큰 카운터를 가진 페이지가 인빅트 되었을 것임
      • MFU를 쓰는 이유는 가장 작은 카운터를 가진 페이지는 페이지 인 된 다음에 아직 사용되지 않은 것으로 참조 가능성이 높다고 생각함
  • Aging
    • 카운터는 각 페이지 별로 참조된 레퍼런스 비트를 leftmost에다가 삽입하고 왼쪽으로 한 비트 이동 시킴 (물론 매번 인터벌 클럭마다)
    • 

      
      

• • Allocation of frames

  • Problem
    • 멀티프로그래밍 시스템에서 경쟁관계의 프로세스 별로 물리 메모리를 할당할 방법이 필요함
      • 만약 빅팀된 페이지가 다른 프로세스에 의해 소유되고 있으면?
      • 각 프로세스에게 얼마나 많은 메모리를 할당 할 것인가?
    • Fixed space algorithms
      • 각 프로세스는 프로세스들이 쓸 수 있는 페이지들이 제한 되어 있음
      • 만약 한계에 도달 했을 때 그 프로세스들이 가진 페이지를 교환함.
      • Local replacement 정책으로 어떤 프로세스는 효율적으로 잘 동작하는 반면 아닌 프로세스도 있음.
    • Variable space algorithms
      • 프로세스의 페이지 할당이 다이나믹하게 grow하거나 shrink함
      • Global replacement, 하나의 프로세스가 휴식 중인 다른 프로세스를 손상(ruin) 입힐 수 있음.

  Thrashing

• 페이지 replacement 알고리즘이 실패하면 OS에서 일어나는 현상
• OS에 의해서 대부분의 시간을 페이징 데이터를 가져오거나 다시 되돌려 보내는데 보냄(페이징 인, 아웃)
  • 유용한 작업을 하는데 보내는 시간이 없어짐
  • 시스템이 overcommitted됨. (과도하게 개입함)
  • 메모리에 어떤 페이지가 폴트를 줄이게 되는가에 대한 대안이 없음
  • 모든 프로세스에게 충분한 메모리를 제공하지 못하게 됨.
• Solution
  • 스와핑, 프로세스의 모든 페이지를 write out
  • 물리 메모리를 늘림.
• 

Working Set Backgrounds

• Working set
  • 프로세스의 워킹 셋은 메모리 사용의 다이나믹 로컬리티를 가진 모델에 쓰이곤 함.
    • 워킹 셋, 프로세스가 필요로 하는 페이지의 집합( set)
    • Peter Denning 196800
  • Definition
    • WS(t,w) = { pages P such that P was referenced in the time interval (t,t-w) }
      정해진 페이지 레퍼런스 수를 채우는 동안의 인터벌 동안에 참조된 페이지의 집합
      • t:time, w:working set window size (measured in page references)
      • 워킹 셋 윈도우(working-set window) 사이즈, w라는 것은 고정된 페이지 레퍼런스 수를 이야기 함.
    • 만약에 윈도우 사이즈(레퍼런스 수)를 너무 작게 잡으면 로컬리티를 모두 내포(Encompass) 할 수 없음
    • 윈도우 사이즈를 크게 잡으면 몇몇 로컬리티들을 커버 할 수 있고 만약 무한대로 잡는다면 프로그램 전체를 커버 할 수 있음.
  • 워킹 셋 안에 페이지는 최근에 w번 레퍼런스 된 것 안에 페이지들이다.
• Working Set Size (WSS)
  • 워킹 셋 안에 페이지 수, 다시 말해 interval(t, t-w)안에 레퍼런스 된 페이지 수
  • 프로그램의 로컬리티에 따라 WSS는 변화 함
    • 로컬리티가 떨어지는 경우에는 더 많은 페이지들이 레퍼런스 될 것임
  • 직관적으로 봤을 때, 워킹 셋은 반드시 메모리의 heavy fault(Threshing)를 보호 할 수 있어야 한다.
  • 워킹 셋 기반의 멀티 프로그램의 degree 제어
    • 각각의 프로세스는 WSS 파라 미터를 가지고 있음
    • 만약에 WSS의 합계가 가용 가능한 프레임의 총 페이지 수를 넘어 갈 때 프로세스는 서스펜드 됨.
      • D = S WSS_i , WSS는 total demand frames과 유사.
      • D > m Þ Thrashing (m is total number of available frames)
        이때 suspend를 thrashing을 막기 위해 서스펜드 해줌.
    • 다른 프로세스들이 추가 되었을 때 WSS가 여전히 메모리에 맞아야지만 프로세스를 시작 할 수 있음.
    • 각 프로세스 내에서 Local replacement를 사용함.

 

Working Set Model

• 특정 페이지가 WS(t, w) 안에 속하였으면 메모리에 keep in, 아니면 out of memory.
  • 워킹 셋 모델은 이 원칙에 따라 replace, allocate를 결정함.
  • 시간의 흐름에 따라 allocation size가 달라 질 수 있음.
• Working Set 페이지 replacement
  • Last k 번 레퍼런스 안에 터치된 페이지들의 집합을 유지하는 것은 매우 비용이 비쌈.
    • 매 레퍼런스 마다 각 페이지들의 최근 레퍼런스 수를 워킹 셋 윈도우 사이즈와 비교 해야 하므로
  • 과거 인터벌 내에 사용된 페이지의 집합으로서 대략적인 워킹 셋을 사용
    • 측정 하는데 있어서 현재 virtual time을 사용함.
      Current virtual time이라는 것은 프로세스가 실제로 사용한 CPU 시간의 총량.
  • 워킹 셋 안에 없는 페이지를 찾아서 그것을 이빅트 함.
    • 인터벌 시간은 각 PTE의 필드 중 Tlast라고 불리는 마지막 사용 시간(time of last use)값을 이용
    • 주기적 클럭 인터럽트에 의해 R 비트는 클리어함.
    • 모든 페이지 폴트 때 이빅트 하기 에 알맞은 페이지를 찾기 위해서 테이블을 스캔 함.
    • R비트가 1일때 현재 Virtual time를 타임스탬프 해둠, (Tlast := Tcurrent)
    • R비트가 0이고 Tcurrent - Tlast가 람다 보다 클 때(정해진 시간 동안 레퍼런스가 없음), 이때 페이지를 이빅트 함.
    • 이빅트가 대상이 아닐 때는 페이지의 greatest age를 기록 해두었다가 이빅트.
  • 

 

PFF (Page Fault Frequency) Scheme

• 다양한 more ad-hoc 어프로치를 쓰는 스페이스 알고리즘 이 있음.
  • 각 프로세스의 fault rate를 모니터링 함.
  • Fault rate 가 threshold를 넘어가면 폴트를 줄이기 위해서 메모리를 더 할당해준다.
    물론 메모리를 늘리는 것이 매번 올바른 것은 아니다. Belady anomaly
  • 만약에 fault rate가 threshold값 아래로 내려가면 메모리를 뺏아감.
• PFF가 계속 증가하는데 가용 가능한 free 프레임이 없으면 특정 프로세스를 선택해서 서스팬드 해야 함.
• 

Advanced VM Functionality

• Virtual memory tricks.
  • 공유 메모리
  • Copy on write
  • Memory-mapped files
• Shared memory
  • Private virtual 어드레스 공간으로 각 어플리케이션 서로 서로를 Protect하는데 이것이 데이터 공유를 어렵게 하는 문제를 가지고 있음.
    • 웹서버 또는 프록시를 fork한 부모와 자식은 카피 없는 메모리 캐시의 공유를 원함.
    • Share data를 액세스 하는 read, write
    • 공유 라이브러리를 실행하는 경우
  • 디렉트 메모리 레퍼런스를 사용하는 공유 데이터를 사용하는 프로세스들을 허용하기 위해서 shared memory를 쓸 수 있음
    • Shared memory를 사용하는 프로세스는 모두 shared memory segment의 업데이트를 볼 수 있음.
    • 공유 된 데이터를 액세스 하기 위해서 우리는 어떻게 서로 협동 할 수 있는가?
  • Implement
    • 페이지 테이블을 사용한 shared memory 구현
      • 공유 타겟에 페이지 테이블의 PTE가 같은 물리적 메모리 프레임을 가리키도록 맵핑 함.
      • 각각의 PTE는 Protection 값을 따로 가지고 있음
      • 페이지가 Invalid가 되었을 때는 반드시 공유 타겟에 PTE를 모두 업데이트 해주어야 함.
    • 각 프로세스의 주소 공간에 같은 위치의 VA 또는 다른 VA에 Shared memory 맵을 위치 시킬 수 있음.
      • Different, Flexible함, 다른 VAS에 맵이 존재 하므로 주소 Conflict가 없음, 그러나 shared memory에 대한 포인터는 다른 프로세스에서 invalid함
      • Same, less flexible, 그러나 shared 포인터는 valid함.
• Copy on write
  • 프로세스 생성
    • 프로세스 생성시 부모 프로세스로부터 자식 프로세스로 모든 주소 공간의 복사가 필요함
    • 이러한 동작은 매우 느리고 비효율적임
  • Solution
    • 스레드를 사용
      • 메모리 공간을 공유
    • Vfork() 시스템 콜을 사용
      • Vfork는 부모와 같이 메모리 공간을 공유하는 프로세스를 생성함
      • 자식 프로세스가 부모 프로세스의 메모리 공간을 overwrite하는 것을 방지하기 위해서 자식이 exit되거나 새로운 프로그램이 실행 될 때 까지 부모 프로세스는 block됨.
      • 자식 프로세스에 의해서 어떤 변화가 있던지 간에 resume되는 동시에 부모 프로세스에 그 변화 내용이 보임.
      • Child가 즉시 exec()를 호출 하는 경우 매우 유용함.
    • Copy On Write (COW)
      • 모든 페이지를 복사하는 대신에 부모 페이지의 Shared 맵핑을 자식 프로세스의 주소공간에 생성함.
      • 공유 페이지들은 자식에게 read only로서 보호 됨
        • Read는 일반적으로 생김
        • Write가 있으면 protection fault가 발생, OS가 이때 발생한 트랩을 받아서 페이지를 복사하고 자식 프로세스에 존재하는 클라이언트 페이지 테이블을 변경한 다음 인스트럭션을 다시 수행함.
        • 
• Memory-Mapped Files.
  • 메모리 맵드 파일
    • 맵드 파일은 프로세스가 메모리 레퍼런스를 사용하여 file I/O를 할 수 있도록 한다.
      • 다시 말해 open(), read, write, close대신에 메모리 레퍼런스를 한다는 것임
    • mmap(), 파일을 virtual memory 영역에 bind시킴
      • PTE는 VA를 파일 데이터를 가지고 있는 physical frame으로 매핑
      • Virtual address base + N 이 파일 안에서 N offset을 참조한다.
    • 초기화 시 맵드 영역 안에 모든 페이지는 invalid로 마크 해놓음
      • OS 가 어떤 Invalid page를 액세스 하면 파일로부터 페이지를 읽어 옴.
      • OS 가 Physical memory로 부터 이빅트를 할 때 페이지를 파일로 씀
      • 물론, 페이지가 더티가 아니면 쓸 필요는 없음.
  • Note
    • 파일은 VAS의 영역을 위한 필수적인 backing 스토어임. (Swap file을 대신함)
  • 이점
    • 파일과 메모리를 단지 포인터만 사용하여 접근 할 수 있기 때문에 uniform 액세스가 가능해짐
    • 복사가 적어짐
      • 이는 일반적인 IO 퍼포먼스보다 메모리 맵드 파일이 빠른 속도를 가지게 되는 이유임.
        다른 하나는 local memory를 변경 하는 것 보다 system call의 오버헤드가 크기 때문임.
      • 복사가 적어지는 이유는 대부분의 OS에서 메모리 맵 영역은 커널 파일 캐시에 존재 하기 때문에 유저 공간에서 커널 공간으로의 복사가 줄어 듦.
  • Drawbacks
    • Standard IO 어프로치가 시스템콜 오버헤드와 메모리 카피 오버헤드를 가진다면 메모리 맵드 파일의 어프로치는 페이지 폴트에 있다.
    • 이러한 페이지 폴트로 생기는 코스는 상황에 따라 다르나 메모리 맵드 파일은 standard IO보다 갑자기 성능이 악화 될 수 있다. 큰 파일을 읽을 경우 대부분의 데이터는 커널에 의해 캐시 되지 않기 때문에 많은 페이지가 폴트를 유발 할 수 있다.

         

• •