[운영체제] 가상 메모리 관리

💡 요구 페이징

1. 요구 페이징의 개요

- 요구 페이징

: 사용자가 요구할때 해당 페이지를 메모리로 가져오는 것

 

- 미리 가져오기

: 요구 페이징과 반대로 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식

ex) 캐시

 

2. 페이지 테이블 엔트리(PTE)의 구조

- 페이지 번호

:매핑 방식에 따라 포함되기도 하고 포함되지 않기도 함

 

- 프레임 번호 (주소 필드)

: 가상 주소의 패당 페이지가 어느 프레임에 있는지 알려주는 자료 구조로 페이지 테이블의 핵심

 

- 플래그 비트

• 접근 비트 : 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트
• 변경 비트: 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트
• 유효 비트: 페이지가 실제 메모리에 있는지를 나타내는 비트 (0일때가 있다는 의미)
• 읽기, 쓰기, 실행 비트: 페이지에 대한 읽기 권한, 쓰기 권한, 실행 권한을 나타내는 비트

 

3. 페이지 부재

: 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황

 

- 페이지 교체 알고리즘

: 메모리가 빈 프레임이 없을 때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘

 

📌 대상페이지

: 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지

 

4. 지역성

- 공간의 지역성

: 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다는 것

 

- 시간의 지역성

: 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다는 것

 

- 순차적 지역성

 : 여러 작업이 순서대로 진행되는 경향이 있다는 것

 

💡 페이지 교체 알고리즘

1. 무작위 페이지 교체 알고리즘

: 페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있는 방식. 스왑 여역으로 쫓아낼 대상 페이지를 특별한 로직없이 무작위로 선정한다.

 

2. FIFO 페이지 교체 알고리즘

: 선입선출 페이지 교체 알고리즘. 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정.

 

3. 최적 페이지 교체 알고리즘

: 앞으로 사용하지 않을 페이지를 선정. 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현 X.

 

4. LRU 페이지 교체 알고리즘 (Least Recently Used)

: 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 선정.

 

- 페이지 접근 시간에 기반한 구현

: 페이지에 접근한 시간을 기록하여 구현

 

- 카운터에 기반한 구현

: 접근 시간을 시간이 아니라 카운터 숫자로 기록

 

- 참조 비트 시프트 방식

: 각 페이지에 일정 크기의 참조 비트를 만들어 사용. 초기값은 0 이며 접근할때마다 1로 바뀜. 참조 비트는 주기적으로 오른쪽으로 한칸씩 이동하고 제일 작은 값을 대상 페이지로 선정

 

5. LFU 페이지 교체 알고리즘(Least Frequently Used)

: 최소 빈도 알고리즘. 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정

 

6. NUR 페이지 교체 알고리즘 (Not Used Recently)

: 최근 미사용 페이지 교체 알고리즘. 참조비트와 변경비트 2비트만 사용하여 미래를 추청함.

 

7. 2차 기회 페이지 교체 알고리즘

: FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용하지만, 차이점은 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨뒤로 옯김으로써 기회를 한 번 더 준다.

 

8. 시계 알고리즘

: 원형큐를 이용. 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 바닥으로 내려가면 다음번에는 다시 큐의 처음을 가리키게 된다. 이때 참조 비트가 1인 페이지는 건넘뜀으로써 기회를 한 번 더 준다.

 

💡 스레싱과 프레임 할당

1. 스레싱

: 하드 디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태

 

📌 스레싱 발생 시점

: CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리에 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 되는 시점

 

2. 정적 할당

: 프로세스 실행 초기에 프레임을 나누어준 후 그기를 고정하는 것.

 

- 균등 할당

: 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당하는 방식

-> 크기가 큰 프로세스의 경우 필요한 만큼 프레임을 할당받지 못하기 때문에 페이지 부재가 빈번하게 발생하고, 크기가 작은 프로세스의 경우 메모리가 낭비됨.

 

- 비례 할당

: 프로세스의 크기에 비례하여 프레임을 할당하는 방식

-> 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못하고, 사용하지 않을 메모리를 처음부터 미리 확보하여 공간이 낭비됨.

 

3. 동적 할당

: 시시각각 변하는 요청을 수용해서 프레임을 할당하는 방식

 

- 작업집합 모델

: 지역성 이론을 바탕으로 가장 최근에 접근한 프레임이 이후에도 또 참조될 가능성이 높나는 가정에서 출발.

 

📌 작업집합 윈도우

: 작업집합에 포함되는 페이지의 범위

 

- 페이지 부재 빈도

: 페이지 부재 횟수를 기록하여 페이지 부재 비율을 계산하는 방식. 페이지 부재 비율이 상한선을 초과하면 할당한 프레임이 적다는 것을 의미하므로 프레임을 추가하여 늘리고, 반대로 페이지 부재 비율이 하한선 밑으로 내려가면 메모리가 낭비된다는 의미이므로 할당한 프레임을 회수한다.