가상 메모리

프로세스 전체가 메모리 내에 올라오지 않더라고 실행이 가능하도록 하는 기법
프로그램이 physical memory보다 크더라도 실행 가능하도록

가상 메모리는 물리 메모리로부터 논리 메모리를 분리해서 메인 메모리를 엄청나게 큰 배열로 추상화시켜주면서 프로그래머는 메모리의 크기의 제약으로부터 자유로워진다.

• 파일, 라이브러리를 공유하거나, 프로세스를 생성할 때 굉장히 유용하다.

→ 파일과 메모리의 공유가 굉장히 쉬워진다. (through page sharing)

가상 주소 공간

virtual address space -> 한 프로세스가 저장되는 논리적인 모습(view)
0부터 시작하게 된다.

프로그램의 동작을 다시 한 번 살펴보자.

프로그램을 secondary storage(하드 디스크, SSD 등의 보조저장장치)에서 메인 메모리로 로딩
전체 프로그램을 physical memory에 올리는 대신 페이징을 통해 잘라서 일부분만 올리는 방법이 있다 - 까지가 저번시간의 이야기. 그럼 각각의 페이지를 언제 올릴까? 그것이 바로 demanding page 요청할 때 올리자! 라는 이야기.

Demand Paging

기본개념

어떤 프로세스가 실행중일 때는 일부는 memory에, 일부는 secondary memory에 존재할 것이다.
어디에 존재하는 지를 구분하려면? valid-invalid bit 을 활용, valid 이면 page가 legal하며 메모리에 존재하다는 것일거고, invalid는 not valid이거나 secondary storage에 있음을 의미하도록 하는 것이다.

그러니 valid-invalid bit이 포함된 페이지 테이블을 통해 메인 메모리에 존재하는 지의 여부를 알아낼 수 있을 것이다. 만약 페이지 테이블이 invalid로 설정되어 있다면, Page-fault trap을 발생시킨다.

• page-fault trap을 처리하는 방법
  invalid의 의미는 실제 참조가 무효하거나 / 보조 저장장치에 존재함을 의미한다. 프로세스에 대한 내부 테이블을 검사해서 두 경우를 구분해준다.
  만약 실제 참조가 무효라면 프로세스를 중단시키고, 유효한 참조인데 페이지가 아직 메인 메모리에 존재하지 않는 것이라면, free frame을 찾아서, 보조저장장치에서 해당 페이지를 읽어온다.
  페이지 테이블을 valid로 갱신하고, 내부 테이블도 수정한 후 트랩에 의해 중단됐던 명령어를 다시 수행한다. → page in

pure demand paging

만약 요청을 하지 않으면 절대페이지를 가져오지 않는 것. 처음에는 아예 아무것도 메인 메모리에 load되지 않은 상태에서 시작한다. 순수한 방식의 demand paging

• 프로그램은 한 명령어에서도 여러개의 페이지 폴드를 일으킬 것이고, 성능 하락으로 이어진다.

Locality of Reference

프로그램은 어느 한 특정 부분만 집중적으로 참조하는 경향이 있다는 말. 그래서 실제로는 pure demand paging보다 낮은 page-fault를 발생시키면서 시스템 성능을 향상시킬 수 있다.

Hardware Support to Demand Paging

• page table
  valid-invalid bit를 통해 특정 항목을 invalid로 설정가능해야한다.
• 보조저장장치
  메인 메모리에 없는 모든 페이지를 가지고 있다. 이를 스왑 장치라고 한다.
• page-fault trap 처리 후 명령어 restart
  중단된 프로세스 사태를 보관해두고, 정확히 같은 위치, 같은 상태에서 프로세스를 재시작할 수 있도록.

Free-Frame List

O/S는 linked-list를 통해 free-frame을 관리해줘야한다.

Demand Paging의 성능

effective access time을 계산하는 방법?

실질접근시간(effective access time) = (1-p) ma + p (page fault time)

• p: 페이지 폴드의 확률(0 <= p <= 1).
• ma : memory access time
• page fault time : 인터럽트의 처리 + 페이지 읽기 + 프로세스 재시작

copy-on-write

process가 shared page에 write를 할 때에만 shared page를 copy하는 것

부모 페이지를 fork()할 때 유용하게 이용할 수 있다. 부모로부터 페이지들을 다 복사해오는 대신 일단은 부모의 페이지를 공유하는 것

페이지 교체

• free-frame이 없을 때의 동작
• 그럼 특정 페이지를 physical memory에서 제거한 후 page table에서 제거시켜 준 후, 새로운 페이지를 page in 하는 과정을 시행해야겠지

자세한 과정
필요한 페이지가 보조저장장치의 어디에 위치하는 지를 찾는다.
→ 빈 페이지 프레임을 찾는다.

• 만약 free frame이 있다면 그걸 이용
• 없다면, 페이지 교체 알고리즘을 통해 victim 페이지를 찾아 제거한다. victim 페이지를 필요할 경우 보조저장장치에 기록하고, 관련 테이블을 수정한다.

→ 빼앗은 or 빈 페이지 프레임에 새 페이지를 읽어오고 페이지를 수정한다.
→ 페이지 폴트가 발생한 시점에서부터 프로세스를 계속한다.

두 가지 고려할 점

• 각 프로세스에 몇 개의 프레임을 할당할 지 → frame-allocation algorithm
• 어떤 페이지가 victim이 될 지 → page-replacement algorithm

왜냐하면 보조저장장치에 I/O를 하는 것은 비용이 많이 소모되기 때문에 시스템 성능에 큰 영향을 끼친다.

Page Replacement Algorithm

목표는? page-fault의 비율을 낮추는 것

• reference string: string of memory reference - 메모리 주소의 나열
• reference string을 이용하여 page-fault 비율을 낮추는 방법을 찾아야 한다.
• number of page frames? frame이 많을수록, page fault는 적어진다.

FIFO 페이지 교체

• 가장 간단하다.

• 가장 오래된 페이지를 교체하게 된다.

• Belady의 모순이 일어난다
  (프로세스에 프레임을 더 할당하였음에도 page-fault가 감소하는 현상)

최적(optimal) 페이지 교체

• OPT
• 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것
• 프로세스의 참조를 예측해야하므로 실제 구현은 어렵다
• 연구에서 다른 알고리즘의 성능과 비교할 때 이용

LRU 페이지 교체

• least-recently-used
• 가장 오랜 기간 동안 사용되지 않은 페이지를 교체한다.
• 페이지마다 마지막 사용 시간을 유지
• Belady 모순을 겪을 일이 없다.
• implementation
  counter: 각 항목마다 사용 시간 필드를 추가
  stack : 페이지가 참조될 때마다 스택 중간에서 스택 top으로 이동
  

Second-chance Algorithm

• FIFO 기반
• reference bit 을 이용(하드웨어 지원)
  : 0 or 1로, 페이지 참조가 있을 때마다 참조 비트가 세팅된다. 어떤 페이지가 그동안 사용되었는 지 확인이 가능, LRU 근사 알고리즘의 기본이 된다.
• reference bit == 0이면 페이지를 교체하고, 1이면 한 번 더 기회를 주고 다음 FIFO 페이지를 교체한다.
• 처음 모든 참조비트는 0, 참조될때마다 1, 한번 더 기회가 주어지면 1에서 0으로 바뀐다.
• circular queue를 이용

프레임의 할당

프로세스들에게 free-frame을 어떻게 할당할 것인가?

• Equal vs Proportional?
  프로세스마다 같은 비율을 주거나 vs 프로세스의 사이즈를 고려하여 할당하거나

• Local vs Global?
  페이지 교체를 할 때 해당 프로세스에게 할당된 프레임 내에서만 교체 vs 전체 프레임들 중에서 교체

스레싱, Thrashing

• 프로세스에게 충분한 페이지가 없는 경우, page-fault rate가 높아질 수 있다.
• degree of multiprogramming이 높아지는 경우가 하나의 예
• 페이지 폴트과 과하게 발생하면서 swapping이 많아지는데, 이러한 과도한 페이징 작업을 스레싱이라고 부른다.

• 어떤 프로세스가 실제 실행보다 페이징에 더 많은 시간을 소요하고 있으면 스레싱이 발생한다고 얘기한다.

Working-set Model

• locality를 기반으로 한다.
• 최근 delta만큼의 페이지를 참조하였을 때, 그 안에 들어있는 서로 다른 페이지들의 집합
• 페이지가 활발하게 사용되었으면 working-set에 포함되게 되고, 마지막 참조 이후로 delta만큼의 시간이 지나면 working set에서 제외된다.
• 스레싱 완화