운영체제 - 가상메모리 정리 (방송통신대학교 운영체제)

가상 메모리의 개념

메모리 크기보다 더 큰 기억공간이 필요한 프로세스를 실행할 수 있게 하는 방법

→ 한번에 전체 프로세스의 일부분만을 실행함

가상메모리

• 프로세스에 의해 참조되는 주소를 메모리에서 사용하는 주소와 분리
• 가상주소와 실주소 공간으로 분리
• 가상주소공간(V): 실제 프로세스의 가상주소 공간
• 실주소공간(R): 실제 메모리의 주소 공간
• CPU에서는 실주소공간이 필요함. 메모리의 가상주소를 실주소로 변환하는 과정이 필요

사상

• 프로세스 실행을 위해 가상주소를 실주소로 변환
• 동적 주소 변환(DAT): 프로세스가 실행되는 동안 사상
• 인위적 연속성: 가상주소 공간에서는 연속이지만, 실주소 공간에서도 연속일 필요는 없음

블록 단위 주소 변환

블록 단위로 분류하여 각 블록이 메모리의 어디에 위치하는지를 관리

블록의 크기에 관한 문제점

• 작으면 사상표에 들어갈 사상정보가 많아짐
• 크면 블록 전송시간이 증가함
• 크면 적재할 수 있는 프로세스의 수가 낮아짐

가상주소 v=(b, d)

b: 블록 번호

d: 블록 내 변위

블록 단위 주소 변환

• 페이징 기법: 블록의 크기가 동일한 페이지로 구성
• 세그먼테이션 기법: 블록의 크기가 서로 다른 세그먼트로 구성

페이지와 페이지 프레임

• 가상 메모리를 고정된 크기의 블록인 페이지 단위로 나누어 관리
• 메모리 영역도 페이지와 동일한 크기의 블록인 페이지 프레임으로 나눔
• 각각의 페이지와 페이지 프레임은 각각의 번호가 부여되어 있음
• 예: 가상 메모리의 3번 페이지를 메모리의 5번 페이지 프레임에 적재한다

페이지 사상표

• 가상주소를 실주소로 동적 변환하기 위해 필요
• 가상주소의 페이지 번호에 대한 실주소의 페이지 프레임 번호를 저장

가상주소 v=(p, d)

p: 페이지 번호

d: 페이지 내 변위

실주소 r = (p’, d) = p’M+d

p’: 페이지 번호

d: 페이지 내 변위

M: 프레임의 크기

직접 사상: 페이지 사상표를 직접 이용

연관 사상: 연관기억장치에 저장한 연관 사상표를 이용

연관, 직접 사상

연관 사상표에는 가장 최근에 참조된 페이지들만 보관, 나머지는 페이지 사상표에 보관

• 먼저 연관사상표를 조회, 연관사상표에 있다면 실주소를 반환
• 연관사상표에 가상주소가 없다면 페이지 사상표를 조회
• 연관사상표에 페이지 존재 비트가 1이라면 해당하는 실주소를 반환
• 연관사상표에 페이지 존재 비트가 0이라면 해당 페이지를 메모리에 올리는 작업을 해야 함, 이때 페이지 사상표의 s를 이용함

페이징 기법의 특징

• 논리적 의미와 무관하게 동일 크기의 페이지로 가상 메모리를 나눔
• 프로세스 사이의 메모리 보호는 페이지 단위로 이루어짐
• 외부 단편화는 발생하지 않으나 내부 단편화는 발생할 수 있음

세그먼테이션 기법

세그먼트: 가상 메모리를 논리적 의미에 맞는 다양한 크기의 세그먼트 단위로 나누어 관리

한 세그먼트는 하나의 의미를 가질 수 있도록, 논리적인 단위로 나뉘어짐

가상주소 v = (s, d)

s: 세그먼트 번호

d: 세그먼트 내 변위

세그먼트 사상표

세그먼트 존재 비트, 보조 기억 장치 주소, 세그먼트 길이, 세그먼트 시작주소

세그먼트 시작주소: 메모리에서의 시작위치

세그먼트 길이: 오버플로 확인용

페이징/세그먼테이션 혼용기법

• 세그먼테이션 기법의 논리적 장점 + 페이징 기법의 메모리 관리 장점
• 가상 메모리를 세그먼트 단위로, 각 세그먼트를 다시 페이지 단위로 분할
• 메모리는 페이지 프레임으로 분할

가상주소 v = (s, p, d)

s: 세그먼트 번호

p: 페이지 번호

d: 페이지 내 변위

세그먼트 사상표 → 페이지 사상표 → 메모리 순서로 사상

페이지 호출 기법

• 페이지를 어느 시점에 메모리에 적재할 것인가를 결정
• 종류: 요구 페이지 호출기법, 예상 페이지 호출기법

요구 페이지 호출기법

• 한 프로세스의 페이지 요구가 있을 때 요구된 페이지를 메모리로 이동
• 즉, 명령어나 데이터가 실제로 참조되면 해당 페이지를 메모리에 적재
• 옮길 페이지를 결정하는데 오버헤드를 최소화
• 메모리에 옮겨진 페이지는 모두 프로세스에 의해 실제로 참조된 것인
• 프로세스 시작 시점에는 프로세스 진행에 따라 연속적으로 페이지 부재 발생(성능 저하)

예상 페이지 호출기법

• 현재 요구되지는 않지만 곧 사용될 것으로 예상되는 페이지를 미리 메모리로 이동
• 실제 필요한 시점이 되었을 때 프로세스 실행이 단절되지 않음
• 예상이 잘못된 경우 메모리 공간 낭비
• 프로세스 시작 시점에 적용하면 성능이 개선됨

다양한 페이지 교체기법

• 모든 페이지 프레임이 사용되고 있을 때 새로 적재되어야 할 페이지를 위하여 어느 페이지를 교체할 것인가를 결정
• 교채 대상 선택 → 보조기억장치에 보관 → 새로운 페이지를 적재

교체 대상 선택

최적화의 원칙

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택
• 이론적으로는 최적이나 미래를 예측할 수 없어 실현 불가능

선택을 위한 기본 정책

대체로 좋은 결론을 내리면서 시간 및 공간의 오버헤드가 적은 방법

교체 제외 페이지

• 페이징을 위한 슈퍼바이저 코드 영역
• 보조기억장치 드라이버 영역
• 입출력장치를 위한 데이터 버퍼 영역 등

페이지 교체 알고리즘

• FIFO(First-In First-Out)
• LRU(Least Recently Used)
• LFU(Least Frequently Used)
• NUR(Not Used Recently)
• 2차 기회
• 클럭 페이지
• 워킹 세트, PFF(Page Fault Frequency) → 프레임 갯수 고정 아님

FIFO

• 메모리 내에 가장 오래있었던 페이지를 교체
• 구현: FIFO 큐 이용

단점

• 오래 전에 적재되어 반복적으로 사용되는 페이지가 교체될 수 있음
• Belady의 이상현상 발생
• 프로세스에 더 많은 수의 페이지 프레임을 할당할 경우, 오히려 페이지 부재가 더 많이 발생할 수 있는 현상

LRU

• 가장 오랫동안 사용되지 않은 페이지를 교체
• 구현: 참조시간 이용 또는 리스트 이용

참조시간 이용

• 페이지가 참조될 때마다 그때의 시간을 기록
• 참조시간이 가장 오래된 페이지를 교체

특징

• Belady의 이상현상 발생하지 않음
• 많은 경우 최적화 원칙에 근사한 선택을 함
• 국부성(locality)에 기반 → 어느 한순간에 특정 부분을 집중적으로 참조

단점

• 경험적 판단이 맞지 않는 상황도 존재(국부성)
• 막대한 오버헤드

LFU

• 참조된 횟수가 가장 적은 페이지를 교체
• 구현: 참조횟수 이용

단점

• 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성이 높음
• 초기에 매우 많이 사용된 후 더 이상 사용되지 않는 페이지는 교체가능성 낮음
• 막대한 오버헤드

NUR

• 지금부터 나오는 페이지 기법들은 실제로 사용하기 괜찮은 방법들임
• 참조 여부와 수정 여부에 따른 우선순위에 따라 적합한 페이지를 교체
• 구현: 페이지마다 참조 비트 r과 수정 비트 m 이용

구현과정

• 페이지 프레임에 적재시 r = m = 0
• 페이지를 참조: r = 1
• 페이지를 수정: m = 1
• 교체 우선순위:

1. r=0, m=0
2. r=0, m=1
3. r=1, m=0
4. r=1, m=1

특징

• 적은 오버헤드로 적절한 성능을 낼 수 있음
• LRU와 유사하면서도 실제로 자주 쓰임
• 동일 그룹 내에서의 선택은 무작위
• 모든 참조 비트 r을 주기적으로 0으로 변경

2차 기회 페이지 교체기법

• FIFO페이지 교체기법과 참조 여부를 따른 우선순위를 고려하여 적합한 페이지를 교체
• 구현: FIFO 큐와 참조 비트 이용

교체 대상 선택 방법

1. 큐의 선두를 꺼내 참조 비트 조사
2. 참조 비트가 0이면 교체 대상으로 선택
3. 참조 비트가 1이면 0으로 바꿔 큐의 뒤에 넣음

클럭 페이지 교체기법

• 기본적인 틀은 2차 기회 페이지 교체기법과 동일
• 2차 기회 페이지 교체를 원형 큐를 이용하여 구현한 것
• 교체가 필요한 경우 큐에서의 삭제 및 삽입 대신 포인터 이동으로 간단히 구현

페이지 부재 시 포인터를 이동하며 참조 비트를 0으로 바꾸거나 페이지를 교체

페이지 교체 시 포인터를 다음으로 이동

프로세스별 페이지 집합 관리

프로세스별 페이지 집합

프로세스마다 페이지 프레임에 적재된 페이지들의 집합

프로세스별 페이지 집합의 크기가 적은 경우

• 메모리에 적재할 수 있는 프로세스의 수 많아짐 → 시스템이 처리가능한 프로세스 증가
• 각 프로세스별 페이지 부재 많아짐 → 성능 저하

페이지 집합 관리 알고리즘

• 워킹세트 알고리즘
• PFF 알고리즘

워킹세트 알고리즘

워킹세트

• 하나의 프로세스가 자주 참조하는 페이지의 집합
• 워킹세트 W(t,w): 시간 t-w로부터 시간 t까지의 프로세스 시간 간격동안 참조된 페이지의 집합

프로세스 시간

• 그 프로세스가 CPU를 점유하고 있는 시간
• t: 현재 시간
• w: 워킹세트 윈도 크기

워킹세트 알고리즘

• 데닝(Denning)이 제안
• 페이지 부재 비율을 감소시키기 위한 방법
• 원칙: 실행 중인 프로그램의 워킹세트를 메모리에 유지(국부성)
• 프로세스가 실행됨에 따라 워킹세트의 크기는 변함
• 운영체제는 충분한 여분의 프레임이 존재하면 새로운 프로세스를 실행시킴
• 반대로 프레임이 부족해지면 가장 우선순위가 낮은 프로세스를 일시적으로 중지시킴
• 워킹세트가 메모리에 유지되지 못하는 경우 쓰래싱 유발 가능

쓰래싱: 페이지 부재가 비정상적으로 많이 발생하여 프로세스 처리보다 페이지 교체에 너무 많은 시간을 소비하여 시스템 처리량이 급감하는 현상

문제점

• 과거를 통해 미래를 예측하는 것이 정확하지 않음
• 워킹세트를 정확히 알아내고 이를 계속적으로 업데이트 하는 것이 현실적으로 어려움
• 워킹세트 윈도의 크기 w의 최적 값을 알기 어려우며 이 역시 변화할 수 있음

PFF

• 프로세스의 상주 페이지 세트를 변경하며 관리
• 상주페이지 세트: 프로세스가 페이지 부재 떄문에 멈추게 되는 빈도에 기초한 페이지 세트
• 페이지 부재가 발생할 때 빈도를 계산하여 상한과 하한을 벗어나는 경우에만 변경
• 페이지 부재 빈도: 두 페이지 부재가 일어난 사이의 시간의 역수
• 운영체제는 프레임의 여분 상황에 따라 새로운 프로세스 추가 및 중지 결정