운영체제 - 10(가상메모리)

 

운영체제 온라인과제2.pptx

0.42MB

 

페이지 대치

 

 

1. 페이지 대치의 필요성 :

하드디스크에 저장되어 있는 페이지를 메모리로 로딩하고 싶은데, 적재할 곳이 없을 때 다른 페이지를 빼내고 로딩해야 한다. 이를 페이지 대치라고 하며 프레임의 개수가 상대적으로 부족하기 때문에 일어나는 일이다.

 

=> 페이지 대치를 통해 메인 메모리에 있으면서 사용되지 않는 페이지를 없애고 새로운 페이지로 바꿀 수 있다

 

희생 프레임 : 페이지 대치에 의해 교체되는 페이지

=> 효율적인 페이지 대치 알고리즘을 통해 희생프레임을 잘 찾는것이 중요하다

페이지 대치에 의해 희생된 프레임에 중요한 정보가 있을 수 있으므로 잘 선정해야함

 

2. 페이지 부재와 프레임 개수

프레임 수 증가 -> 페이지 부재수 감소

페이지 부재는 부정적인 요소이므로 프레임 개수를 늘려줘야한다

 

 

3. 페이지 대치 알고리즘

 

=> 어떤 것을 희생 프레임으로 선택할 것인가

 

 

1) 선입선출 대치 알고리즘

 

- 선입선출 큐에 의해 관리되어 메모리 도착시간을 따지고 가장 들어온지 오래된 페이지를 대치한다.

(먼저 들어온 놈을 먼저 대치한다)

 

* 벨레디의 변이

- 할당되는 프레임의 수가 증가함에 따라 페이지 부재율이 증가하는 이상현상이 일어남

=> Frame을 많이 할당했음에도 페이지 부재가 오히려 더 일어남

 

 

2) 최적 페이지 대치 알고리즘(Optimal)

 

- 앞으로 가장 오랜 기간 사용되지 않을 페이지로 대치

 

* 문제점

: 해당 페이지가 얼마나 오랜 기간 사용되지 않을지 미리 알기 어려움 => 현실적으로 불가능

 

 

3) 최근 최소사용 대치 알고리즘(LRU)

 

- 보다 더 현실적으로 OPT를 대체

- 미래의 예측을 과거의 자료로 해결하려는 통계적 개념

- 오랜 기간 동안 사용되지 않은 페이지로 대치

 

 

(1) Counter로 구현

- 특정 페이지가 참조될 때 클럭을 이용하여 특정 페이지가 참조될 때 클럭으로부터 현재 참조시간을 읽어 해당 페이지 테이블에 기록

- 이 클럭을 통하여 희생 프레임을 찾을 때 페이지 테이블의 클럭 정보를 스캔하여 가장 오래 전에 참조된 것을 선정.

 

(2) Stack으로 구현

- Stack 구조를 통하여 운영

 

(3) LRU 근접 대치 알고리즘

- LRU 변형 알고리즘

 

1. 부가된 참조비트 알고리즘

- 가장 낮은 참조 비트를 가진 페이지 프레임을 대치

 

2. 시계 알고리즘

- 원형버퍼로 구성된 fifo 스타일 알고리즘

 

 

4) 최소 사용 빈도수 대치 알고리즘(LFU)

- 참조횟수가 적은 프레임의 페이지 대치

- 참조될 때 마다 참조횟수(참조 Counter)를 증가시켜 이 수치가 낮은 것을 먼저 대치

- 참조횟수가 적은 것은 앞으로도 참조되지 않을 것이다

 

5) 최대 사용 빈도수 대치 알고리즘(MFU)

- 참조횟수가 많은 프레임의 페이지 대치

- 참조횟수가 많은 프레임은 앞으로도 사용될 가능성이 높을 것이다

 

6) 페이지 버퍼링

- Victim으로 선정된 페이지를 잠시 동안 메모리에 유지해 봄

- 혹시나 바로 또 쓰일지 모르니깐 메모리에 버퍼링

 

 

---

페이지 할당 알고리즘

 

- 페이지 부재율 감소를 위해 페이지대치와 프레임할당이 중요

- 최적의 프레임 할당 알고리즘 필요

 

1. 균일과 비례할당 알고리즘

- 균일할당 : 모든 프로세스에게 n분의 1개의 프레임 할당

- 비례할당 : 각 프로세스의 크기에 비례하여 프레임 할당

 

2. 스래싱

: 프로세스 수행 시간 < 페이지 교환에 보내는 시간인 현상

=> 페이지 부재가 연속적으로 발생하여 프로세스가 페이지 교환을 위하여 시간을 낭비할 때 발생

* 원인:

프로세스 이용률 감소(새 프로세스 도입) => 페이지 부재 일으킴(수행 중 프로세스에서 페이지 회수) => 필요한 프레임 미배당

 

프로세스가 추가되면서 다중 프로그래밍의 정도를 높임에 따라 프로세서 이용률도 증가하지만,

프로세스 개수가 과도하게 많아지자 오히려 페이지 교환에 보내는 시간이 더 많아지면서 이용률이 급감함

 

=> 지역 교환 알고리즘/우선순위 교환 알고리즘을 사용하여 스래싱 예방 가능

 

3. 지역성

- 프로세스 실행과정에서는 지역성의 특징을 가짐

1) 시간 지역성

: 참조된 기억장소가 가까운 미래에도 참조될 가능성 높음

2) 공간 지역성

: 참조된 기억장소의 근처 기억장소가 그 후에도 참조될 가능성 높음

 

* 작업설정 모델

: 지역성을 설명하기 위한 목적으로 개발

=> 참조가 많은 페이지들의 집합을 메모리에 지속적으로 상주시켜 페이지 부재를 줄이려는 목적

Working Set 찾기

△ = Working-set size

- 작게 설정된다면 지역성 커버 불가(사이즈가 너무 작으면 조금 먼 과거의 지역성은 해결불가)

- 크게 설정되야 지역성 커버 가능

- 무한대로 설정된다면 전체 프로세스를 커버