가상 메모리 2

디멘트 페이징(가져오기 정책)

• 바탕이 되는 지역성 이론

도널드 커누스의 90:10 - 프로그램 실행시, 90%의 시간이 10%의 코드에서 보내는 것
	- 지역성 이론 (여기서 지역성이란?)
		- 1) 공간의 지역성 : 현재 위치에서 가까운 데이터에 접근할 확률이 높다.
		- 2) 시간의 지역성: 최근 접근했던 데이터가 예전에 접근했던 데이터보다 접근할 확률이 높다.
		- 지역성이론에 따라 성능이 안좋기때문에 GOTO문을 자제해야한다.
	- 곧 쓸거같은 데이터는 메모리에 올리고, 사용하지 않을 데이터는 스왑영역(하드디스크)에 올린다.

디멘트 페이징은 곧 사용할 거 같은 데이터를 메모리로 가지고 오고, 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책이다.

메모리 계층구조

가상메모리 크기 = 물리 메모리 크기 + 스왑영역(하드디스크)

• 스왑인: 스왑메모리 ——(데이터)——> 메인 메모리
• 스왑아웃: 스왑메모리 <——(데이터)—— 메인 메모리

Page Fault

페이지 테이블의 한 행 = 페이지 테이블 엔트리(PTE)

- 가상주소로 요청이 들어온다.
-> 메모리 관리자는 페이지 테이블에서 물리 메모리주소를 찾는때 이때 Invalid(없으면) 이면 Page Fault 라는 인터럽트를 발생시킨다.
-> 스왑영역에 접근하고 해당 프로세스는 대기상태 
-> 스왑인 이후 대기상태의 프로세스는 재실행된다.

페이지 교체 정책

: 메모리가 가득 찼을때, 어떤 페이지를 스왑영역으로 보낼지 결정하는 정책

Page Fault 가 발생하면 스왑영역의 페이지를 메모리로 가지고 와야하는 데, 이때 메모리가 가득 차있다면 메모리의 페이지를 스왑영역으로 옮겨야한다.

페이지 교체 정책을 통해 메모리에 있는 페이지 중에 어떤 페이지를 스왑영역으로 보낼지 정한다.

• 무작위로 선택
  • 지역성 고려하지 않아서 자주 쓰는 페이지가 스왑영역으로 이동할 수도 있음 -> 사용하지 않는다.
• FIFO(First In First Out)
  • 들어온 지 가장 오래된 페이지를 내보낸다.
    • 자주 쓰이는 페이지인데 먼저 들어왔다고 내보내질 수 있다.
    • 구현이 간단하고 성능이 나쁘지 않아서 변형해서 자주 쓴다.
      • 빌레이디의 역설: Page Fault를 줄이려고 메모리를 늘려 프레임 수를 늘렸는데, 오히려 Page Falut가 더 발생한다.
• Optimum
  • 앞으로 쓰이지 않을 것 같은 페이지를 내보낸다.
  • 사실상 구현이 불가능한 방법 -> 앞일은 예측이 불가능하기 때문이다.
  • 성능 비교시 참조용으로 쓰인다.
• LRU(Least Recently Used)
  • 최근 사용이 제일 적은 페이지를 내보낸다.
  • 시간의 지역성 -> 최근에 사용한 데이터가 앞으로도 사용할 확률이 높다.
  • 지역성 기반으로 만들어졌기때문에 프로그램이 지역성을 띄지 않을 때는 성능이 떨어진다.
  • 최근 시간을 기록하는건 무겁기 때문에 접근비트를 이용해서 근접하게 구현한다.

LRU가 좋으니까 LRU를 구현해야 한다. -> 최근인지 확인하기 위해서는 시간을 기록해야 하는데, 시간을 기록하는 건 어렵다. 그래서 접근 비트를 이용하는 클락 알고리즘을 이용한다.

클락 알고리즘

: 접근 비트를 이용한 알고리즘
- 일정시간마다 페이지의 접근 비트를 0으로 초기화한다.
- 페이지가 참조되면 +1 된다.
- 스왑영역으로 옮길 페이지를 포인터를 가르키는 데 이걸 클락핸드라고 칭한다.

- 페이지를 원형으로 연결한 후 시계방향으로 돌면서 해당 페이지의 접근비트를 확인한다.
	- 1인 경우 -> 0으로 변경하고 다음 페이지로 넘어간다.
	- 0인 경우 -> 내보낸다.

향상된 클락 알고리즘

접근비트와 변경비트를 확인해서 내보낸다. 상단부터 내보내지는 순서이다.

접근 비트	변경 비트
0	0
0	1
1	0
1	1

• LRU가 성능이 좋아 LRU만 사용할 것같지만, FIFO도 사용하게 되는 경우가 있다.
  • 하드웨어적으로 접근비트를 사용할 수 없는 경우, FIFO를 사용한다.
  • 어쩔수없이 FIFO를 사용해야 하는데, 어떻게 성능을 높여서 사용할까?
  • 2차 기회 페이지
    • FIFO와 동일하지만 Page Fault 없이 메모리에서 사용되는 경우, 해당 페이지를 큐의 맨 뒤로 옮겨서 수명을 연장시켜 준다.
• 성능
  • LRU > 2차 기회 페이지 교체 알고리즘 > FIFO

스레싱과 위킹셋

스레싱

CPU 스케줄링의 목적은 CPU의 사용률을 높이는 것으로 동시에 실행하는 프로세스(멀티프로그래밍)의 수를 높여야한다.

• 스레싱이 발생하는 상황

- 고정된 메모리에 많은 프로세스를 올린다.
- 이 프로세스들의 실행되는 일부 프레임을 다 메모리에 다 올리고, 실행되지 않는 프레임들은 다 스왑영역에 올린다. 
- 프로세스 실행시 많은 Page Fault가 발생 
- CPU의 작업시간 < 스왑작업의 시간 
- CPU의 사용률이 떨어진다.
- 운영체제는 cpu 사용률이 떨어지면 더 많은 프로세스를 올리려고 한다
- 사용률이 더 떨어진다.

워킹셋

스레싱은 근본적으로 메모리 크기가 너무 작아서 생기는 문제이다.

• 하드웨어적으로 해결:
  • 물리 메모리의 크기를 올려준다.
• 소프트웨어적으로 해결:
  • 한 프로세스당 페이지를 많이 할당 -> 다른 프로세스들의 공간이 너무 없다.
  • 한 프로세스당 페이지를 적게 할당 -> 빈번한 Page Falut -> 스레싱 발생 확률 높다.
    • 일단 일정량의 페이지를 할당하고 Page Falut가 발생 시에는 더 많은 페이지를 할당한다.
    • Page Fault가 너무 적게 발생 -> 너무 큰 페이지 할당한 것으로 인지 -> 페이지 회수
      • 프로세스가 실행되면서 그 프로세스에 맞는 적절한 페이지수가 결정된다.
      • 페이지가 결정되면, 어떤 페이지를 유지할 것 인가를 파악 -> 현재 메모리에 올라와있는 페이지를 하나의 세트로 묶어서 메모리에 올린다. -> 워킹셋
      • 프로세스가 준비상태 -> 실행상태가 되는 컨텍스트 스위칭때 사용된다.