운영체제) 메모리 관리3 (Memory Management)

§ 페이지 교체 알고리즘

▣ 페이지 폴트 발생시

--> 새로운 페이지를 위한 공간 확보

--> 제거해야 할 페이지 결정

- 최적의 페이지 교체 기법 (Optimal page replacement algorithm)

; 참조되지 않는 페이지를 교체하는 방법. <-- 현실적으로 구현 불가능

▣ NRU (Not Recently Used)

- R (Reference bit) : 페이지 참조될 때마다 표시

--> 최근에 참조된 페이지를 구별하기 위해, 주기적으로 R비트 클리어 해준다.

- M (Modified bit) : 페이지가 수정될 때마다 표시

- 초기값 : 0, 0

- 페이지 폴트 발생시 

--> R, M비트를 4개의 클래스로 (11, 10, 01, 00) ~ 우선순위 순 (11이 가장 높고 00이 낮음)

--> 가장 하위 순위의 페이지 클래스부터 임의의 한 페이지 제거 ( 00이 먼저 제거 )

- 이해 및 구현 용이, 최적은 아니지만 합당한 성능을 제공

- R, M 비트만 고려하면 됨 --> 속도가 빠름

▣ FIFO (First-In First-Out)

- 순서화된 페이지의 연결 리스트

--> 순서대로 제거 --> 빠름

- 가장 오래된 페이지가 제거

--> 자주 참조되는 페이지를 제거할 가능성 있음

==> 재기회 알고리즘

▣ 재기회 (Second Chance)

- FIFO + NRU

- R비트를 참조하여 제거 여부 결정

--> R비트 = 1 이라면, 맨 뒤로 돌리고 R비트 0으로 바꿈.

--> R비트 = 0 이라면, 제거

- 페이지를 리스트에서 이동시키기 때문에 효율성 저하 가능성 존재

==> 클록 알고리즘

▣ 클록 (Clock)

- 순환 리스트

- 바늘은 가장 오래된 페이지를 가리킴

- 페이지 폴트 발생시

a. R비트 = 1 이라면, 0으로 변경 후 다음 페이지 가리킴

b. R비트 = 0 이라면, 제거 후 다음 가리킴

▣ LRU (Least Recently Used)

- 시간적 지역성 이용 <-- "최근에 참조된 페이지는 곧 다시 참조될 것"

- 로딩된 순서가 아닌 참조된 순서로 리스트 갱신

--> 페이지 폴트 발생시 : 가장 오랫동안 사용되지 않은 페이지 교체

- 구현 비용의 문제

; 모든 페이지들이 리스트로 연결되어 있기 때문에, 리스트 순회의 비용이 듬

==> 특별한 하드웨어 지원으로 구현

- C라는 64비트 카운터를 이용 ; 가장 적은 값의 페이지를 교체

- n개의 페이지 프레임이라면 --> n*n 비트로 구성된 행렬 이용

; k가 참조된다면 --> k번째 행의 모든 비트는 1, k번재 열의 모든 비트는 0으로 설정

▣ NFU (Not Frequently Used)

- LRU ; 하드웨어적 방법 --> 비싸다.

==> 소프트웨어적 방법 : NFU

- 각 페이지마다 소프트웨어 카운터를 유지

--> 초기값은 0

--> R비트를 카운터 값에 더함

--> 페이지들이 얼마나 참조 되었는지 알려줌

--> 페이지 폴트 발생시, 카운터가 가장 적은 값을 교체

- 단점 : 잊어버리는 기능이 없음 ( = 시간축의 개념이 없음 )

--> 예전에 참조된것과 최근에 참조된 것의 구분이 없다.

(예 / 과거에 100번, 최근에 10번 참조된 페이지가 있는 경우, 어느 페이지를 교체할 것인가?)

- NFU + Aging 기법 = Aging Algorithm

--> 카운터는 R 비트를 더하기 전 오른쪽으로 1비트 시프트

--> R비트는 오른쪽 비트가 아닌 왼쪽 최상위 비트에 추가

--> 페이지 폴트 발생하면, 카운터 값이 가장 적은 페이지가 교체

- Aging Algorithm 과 LRU의 차이

a.  시간 순서를 구별할 수 있는 정보

b.  카운트 값이 제한된 비트로 구성 --> 과거에 대한 정보 기억을 제한

§ 작업 집합 (Working Set)

; 사람의 행동이 패턴화 되어있는 것처럼, 프로그램 명령들도 그러하다.

▣ 용어 설명

- 요구 페이징 (demand paging) : 미리 적재하지 않고 필요할 때 요구해서 적재시키는 전략

- 참조 지역성 (locality of reference) : 주소 공간의 일부 페이지를 집중적으로 참조하는 경향

- 작업 세트 (working set) : 프로세스가 현재 자주참조하고 있는 페이지들의 집합

- 스래싱 (thrashing) : 가용 메모리 공간이 적어 작업 집합 전체를 유지할 수 없는 경우

--> 프로그램이 몇개의 명령을 수행할 때마다, 페이지폴트가 발생하는 현상

- 작업세트 모델 (working set model) : 각 프로세스의 작업 세트를 추적하여 프로세스가 실행되기 전에 이것들이 메모리에 적재되도록 하는 접근 방식 <-- 히스토리 이용

- 선 페이징(prepaging) : 프로세스가 실행되기 전에 페이지를 적재하는 것

- 현재 가상시간 (current virtual time) : 프로세스가 시작하고 실제 사용한 CPU 시간 == 프로그램 쪽의 상대적인 시간

▣ 작업 집합 ; w(t, k)

- 현재 시간 t에서 지금까지 참조된 페이지 중에서 가장 최근에 참조된 k개의 페이지 집합

i) k = 1 : 가장 최근에 참조된 페이지만을 갖는 작업 집합

ii) k>1 : 가장 최근에 참조된 페이지를 포함한 페이지 집합

- 작업 집합 모델 ; 운영체제는 어떤 페이지들이 작업 집합에 속하는 지 파악 -> k 값의 결정이 필요

==> 구현 방안1 : k 크기를 갖는 시프트 레지스터를 이용

--> 메모리가 참조될 때마다 왼쪽을 한 위치씩 이동

--> 가장 오른쪽 위치에 참조된 메모리의 페이지 번호가 추가

--> k개의 페이지 번호들이 저장됨 --> 작업집합

--> 시프트 레지스터 관리와 페이지 폴트시의 연산 실행으로 인한 부하가 큼

==> 구현 방안2 : 실행시간을 사용

--> 최근 몇개의 참조에서 사용된 페이지가 아니라, 최근 단위 시간동안 사용된 페이지들로 정의

▣ 작업 집합 페이지 교체 알고리즘 ( 2번째 방법 )

- 프로세스의 작업 집합은 가상시간 동안 참조된 페이지들의 집합

- 페이지 테이블의 각 엔트리는 두개의 키 정보를 유지

a. 페이지가 마지막으로 사용된 시간

b. R((referenced) 비트

- 동작

* 가정

; M과 R 비트는 하드웨어가 관리

; R 비트는 주기적으로 클리어

각 페이지 테이블 엔트리에서 R비트를 검사

--> R = 1이면, 현재 가상시간을 엔트리의 "Time of last use" 필드에 기록

--> R = 0이면, 교체 후보

--> 교체 여부는 나이에 의해 결정

--> 나이 = 현재 시간 - "Time of last use 필드에 기록된 시간"

--> 나이가 t보다 작거나 같으면 유지 (작업 집합 내 페이지)

--> 나이가 t보다 크면 교체의 대상

--> 만일 모든 페이지의 R이 1이면 임의적 교체 (M비트 참조)

==> 속도개선을 위해 Circular List로 관리 (환형 구조)

 

▣ WSClock

- 클록 알고리즘을 기반으로 작업 집합 정보를 관리

--> 페이지 프레임을 환형 리스트로 관리

- 알고리즘

초기에는 빈 리스트

--> 첫 번째 페이지가 적재되면서 리스트에 추가

--> 계속 페이지가 추가되면서 링 구조의 리스트를 형성

--> 각 엔트리는 작업 집합 알고리즘에도 사용하는 Time of last use 필드와 R 비트, M 비트를 갖음

페이지 폴트 발생시

--> 화살표가 가리키는 페이지부터 검사

--> 만약 R = 1 이면, 이 페이지는 교체 대상에서 제외, R을 0으로 설정

--> 화살표는 다음 페이지로 전진하여 다시 검사 계속

--> R = 0이면, 나이가 t보다 크고 페이지가 수정되지 않았으면, 이 페이지가 교체되어 새로운 페이지가 적재

--> 페이지가 수정되었으면 이 페이지의 내용을 우선 디스크에 기록 후 전진

--> 이 과정을 반복하면 언젠가 오래되고 수정이 안된 페이지를 발견

--> 그 페이지를 교체

▣ Belady의 모순

- 페이지 폴트에 대한 문제 : 페이지 프레임이 많을 수록 페이지 폴트가 적게 일어난다?

--> 꼭 그렇지 않다. --> 그렇기 때문에 페이지 교체 알고리즘이 중요하다.

▣ 스택 알고리즘 (stack algorithms)

- 프로세스 메모리 접근은 순서가 정해진 페이지 번호 리스트에 결정

--> 이 리스트를 참조 문자열이라 한다.

- 스택 알고리즘 : 표에 하나씩 써 넣으면서 하는것 (도표 생각)