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보다 갑자기 성능이 악화 될 수 있다. 큰 파일을 읽을 경우 대부분의 데이터는 커널에 의해 캐시 되지 않기 때문에 많은 페이지가 폴트를 유발 할 수 있다.