운영체제) #9 가상 메모리 관리

요구 페이징

요구 페이징의 개요

프로세스의 일부만 메모리로 가져오는 이유

 - 메모리를 효율적으로 관리하기 위해서(메모리가 꽉차면 관리하기 어려우므로 가급적 적은 양의 프로세스만 유지)

 - 응답 속도를 향상하기 위해서(용량이 큰 프로세스를 전무 메모리로 가져와 실행하면 응답이 늦어질 수 있으므로 필요한 모듈만 올려 실행)

 

요구 페이징

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

 - 페이지를 미리 가져 오는 방식은 가져온 페이지를 쓰지 않을 경우 메모리를 낭비하게 됨

 - 따라서 요구 페이징이 메모리의 절약, 메모리의 효율적 관리, 프로세스의 응답속도 향상 등의 효과를 볼 수 있음

 

페이지 테이블 엔트리의 구조

요구페이징과 스왑 영역

 - 페이지가 스왑 영역에 있는 경우는 크게 두가지

   - 요구 페이징으로 인해 처음으로 물리 메모리에 올라가지 못한 경우

   - 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우

 

 

페이지 테이블 엔트리(PTE)의 구성

 - 페이지 번호

 - 프레임 번호

 - 플래그 비트

   - 접근비트 : 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주느 비트

   - 변경비트 : 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트

   - 유효비트 : 페이지가 실제 메모리에 있는지를 나타내는 비트

   - 읽기, 쓰기, 실행비트 : 페이지에 대한 읽기권한, 쓰기권한, 실행권한을 나타내는 비트

 

페이지 부재

유효비트

 - 가상 매모리의 페이지 테이블에는 페이지가 물리 메모리에 있는지, 스왑 영역에 있는지 표시하기 위해 유효 비트를 사용

   - 유효 비트가 0일때 : 페이지가 메모리에 있으므로 주소 필드에 물리 메모리의 프레임 번호가 저장

   - 유효 비트가 1일때 : 페이지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지의 주소가 저장

 

페이지 부재

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

 - 페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야함

페이지 부재 처리 과정

 1. 프로세스가 페이지 3을 요청하면 페이지 테이블의 유효 비트가 1이기 때문에 페이지 부재가 발생

 2. 메모리 관리자는 스왑 영역의 0번에 있는 페이지를 메모리의 비어있는 프레임인 5로 가져옴(스왑인)

 3. 프레임 5로 접근하여 해당 데이터를 프로세스에 넘김

 

페이지 교체

 - 페이지 부재가 발생하면 스왑 영역에 있는 페이지를 메모리의 빈 영역에 올리고 페이지 테이블을 갱신(업데이트)

 - 빈 프레임이 없을 때는 메모리에 있는 프레임 중 하나를 스왑 영역으로 내보낸 후에야 해당 페이지를 가져올 수 있음

 

페이지 교체 알고리즘

 - 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘

 

대상 페이지

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

 

메모리가 꽉 찬 상태에서 페이지 부재가 발생했을 때 조치

 1. 해당 페이지의 유효 비트가 1이라 페이지 부재가 발생

 2. 메모리가 꽉 차있는 상태이기 때문에 스왑 영역에 있는 페이지 E를 가져오기 위해 메모리의 페이지 중 하나를 스왑 영역으로 내보내야 함(물리 메모리의 프레임 3에 저장된 페이지를 대상 페이지로 선정했는데 이 페이지를 스왑 영역으로 옮김(스왑아웃))

 3. 대상 페이지 PTE 1의 유효 비트가 0에서 1로, 주소 필드 값이 프레임 3에서 스왑주소 6으로 바뀜

 4. 스왑 영역 1번에 있던 페이지 E가 프레임 3으로 올라감(스왑인)

 5. PTE 4의 유효 비트가 1에서 0으로, 주소 필드 값이 스왑 주소 1에서 프레임 3으로 바뀜

 

세그먼테이션 오류와 페이지 부재

 - 세그먼테이션 오류 : 사용자의 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생하며 해당 프로세스를 강제 종료하여 해결

 - 페이지 부재 : 해당 페이지가 물리 메모리에 없을때 발생하는 오류로 사용자 프로세스와 무관하기 때문에 페이지 부재가 발생하면 메모리 관리자는 스왑 영역에서 해당 페이지를 물리 메모리로 옮긴 후 작업을 진행

 

지역성

지역성

 - 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질

 - 페이지 교체 알고리즘이 쫒아낼 페이지를 찾을 때 지역성을 바탕으로 함

 

지역성의 종류

 - 공간의 지역성 : 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높음

 - 시간의 지역성 : 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터 보다 사용될 확률이 높음

 - 순차적 지역성 : 여러 작업이 순서대로 진행되는 경향이 있음

 

페이지 교체 알고리즘

페이지 교체 알고리즘의 개요

페이지 교체 알고리즘

 - 스왑 영역으로 보낼 페이지를 결정하는 알고리즘

 - 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지의 부재를 줄이고 시스템의 성능을 향상

 

페이지 교체 알고리즘의 성능평가 기준

 - 어떤 알고리즘이 다른 알고리즘보다 성능이 좋은지 평가하는 데에는 다양한 비교방법이 있음

 - 여기에서는 같은 메모리 접근 패턴을 사용하여 페이지 부재 횟수와 페이지 성공 횟수를 비교

 

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

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

 - 스왑 영역으로 쫒아낼 대상 페이지를 특별한 로직 없이 무작위로 선정

 - 지역성을 전혀 고려하지 않기 떄문에 자주 사용하는 페이지가 대상페이지로 선정되기도 하여 성능이 좋지 않음

 

FIFO 페이지 교체 알고리즘

 - 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑영역으로 쫒아냄

 - 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들이 위쪽으로 이동하며, 새로운 페이지가 아래쪽의 남은 공간에 들어옴

 - 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어짐

 - 페이지 성공 횟수 : 3

최적 페이지 교체 알고리즘

최적 페이지 교체 알고리즘

 - 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮김

 - 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리있는 페이지를 대상 페이지로 선정

 - 페이지 성공횟수 : 5

 - 이상적인 방법이지만 실제로 구현할 수 없음

최적 근접 알고리즘의 접근방식

 - 실제 구현이 가능하면서도 성능이 최적 근접 알고리즘에 근접한 알고리즘

 - LRU 페이지 교체 알고리즘 : 페이지에 접근한 시간을 기준으로 대상 페이지를 선정

 - LFU 페이지 교체 알고리즘 : 페이지가 사용된 횟수를 기준으로 대상페이지를 선정

 

LRU 페이지 교체 알고리즘

LRU 페이지 교체 알고리즘

 - '최근 사용 페이지 교체 알고리즘' 이라도고 함

 - 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮김

 - 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정

 - 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용하는 방법도 있음

 

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

 - 페이지에 접근한 지 가장 오래된 페이지를 교체

 - 페이지 성공 횟수 : 4

카운터에 기반한 구현

 - LRU 페이지 교체 알고리즘을 카운터를 사용하여 구현

 

참조 비트 시프트 방식

 - 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것

 - 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀜

 - 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동

 - 참조 비트를 갱신 하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정

 

참조 비트 시프트 방식이 LFU가 아니라 LRU 페이지 교체 알고리즘인 이유

 - 참조비트 방식은 시각을 기준으로 하기때문

 

LFU 페이지 교체 알고리즘

LFU 페이지 교체 알고리즘

 - 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정

 - 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역을 옮김

 

NUR 페이지 교체 알고리즘

NUR 페이지 교체 알고리즘

 - LRU, LFU 페이지 교체 알고리즘은 성능은 좋으나 추가적인 오버헤드가 큼

 - 이를 개선한 NRU는 두 개의 비트만으로 구현 가능

 - '최근 미사용 페이지 교체 알고리즘'이라고도 불림

 - 페이지마다 참조 비트와 변경 비트를 가짐

    - 참조비트 : 페이지에 접근 하면 1이 됨

    - 변경비트 : 페이지가 변경 되면 1이 됨

 - 모든 페이지의 초기 상태는 (0,0), 모든 값이 (1,1)이면 초기화 함

 - 대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를찾음

 - 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정

 - 페이지 성공 횟수 : 5

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

 - FIFO 페이지 교체 알고림과 마찬가지로 큐를 사용

 - 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지의 큐를 맨 뒤로 이동하여 대상 페이지에서 제외

 - 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 줌

 - 페이지 성공횟수 : 4

 

FIFO 변형 알고리즘

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

 - FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용

 - 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외

 - 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더줌

 - 페이지 성공횟수 : 4

시계 알고리즘

 - 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용

 - 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용

 - 포인터가 큐의 맨 바닥으로 내려가면 다음번에는 다시 큐의 처음을 가리키게 됨

 

시계 알고리즘의 동작

 - 2차 기회 페이지 교체 알고리즘에 비해 각 페이지에 참조 비트가 하나씩 추가

 - 참조 비트의 초깃값음 0, 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경

 - 대상 포인터는 메모리가 꽉 찰경우 스왑 영역으로 쫒겨날 페이지를 가리킴

 - 가리키는 페이지가 스왑 영역으로 쫒겨 나면 대상 포인터를 밑으로 이동하는데 이때 참조 비트가 1인 페이지는 0으로 만든 후 건너 뜀(2차 기회를 줌)

 - 페이지 성공 횟수 : 4

 

스레싱과 프레임 할당

스레싱

스레싱

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

 

스레싱 발생 시점

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

 - 물리 메모리의 크기를 늘리면 스레싱 발생 지점이 늦춰져서 프로세스를 원만하게 실행할 수 있음

 

스레싱과 프레임 할당

 - 프로세스에 너무 적은 프레임을 할당하면 페이지 부재가 빈번히 일어남

 - 프로세스에 너무 많은 프레임을 할당하면 페이지 부재는 줄지만 메모리가 낭비됨

 - 프로세스에 프레임을 할당하는 방식은 크게 정적할당과 동적할당으로 구분

 

정적할당

균등할당

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

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

 

비례 할당

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

 - 프로세스의 크기를 고려하지 않는 고정 할당보다 좀 더 현실적인 방식

   - 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못함

   - 사용하지 않을 메모리를 처음부터 미리 확보하여 공간을 낭비

 

동적할당

작업집합 모델

 - 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고, 이 집합에 있는 페이지들을 물리 메모리에 유지

   - 작업집합 크기 : 작업집합 모델에소 물리 메모리에 유지할 페이지 크기

   - 작업집합 윈도우 : 작업집합에 포함되는 페이지 범위

 - 델타 동안 참조된 10개의 페이지 중 작업집합에는 WS(t1)={1,7,5,2,3}이 삽임되며, 이 페이지들은 다음번 윈도우에 도달할 때까지 물리메모리에 보존

 

 

작업집합의 갱신

 - 작업 집합의 크기가 5라는 것은 페이지에 다섯 번 접근할 때마다 작업 집합을 갱신한다는 의미

 

작업집합 윈도우의 크기와 프로세스 실행 성능

 - 작업집합 윈도우를 너무 크게 잡으면 필요 없는 페이지가 메모리에 남아서 다른 프로세스에 영향을 미침

 - 윈도우를 너무 작게 잡으면 필요한 페이지가 스왑 영역으로 옮겨져서 프로세스의 성능이 떨어짐

 - 적정크기의 작업집합을 유지함으로써 메모리를 효율적으로 관리 할 수 있음

 

페이지 부재 빈도

 - 페이지 부재 횟수를 기록하여 페이지 부재 비율을 계산하는 방식

 - 페이지 부재 비율이 상한선을 초과하면 프레임을 추가하여 늘림

 - 페이지 부재 비율이 하한선 밑으로 내려가면 할당한 프레임을 회수

 - 페이지 부재 빈도 방식은 프로세스를 실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절

 

프레임 관련 이슈

전역 교체와 지역 교체

전역 교체와 지역 교체

 - 전역교체 : 전체 프레임을 대상으로 교체 알고리즘을 적용

 - 지역교체 : 현재 실행중인 프로세스의 프레임을 대상으로 교체 알고리즘을 적용

 

지역 교체 방식의 장단점

 - 장점 : 자신에게 할당된 프레임의 전체 개수에 변화가 없기 때문에 페이지 교체가 다른 프로세스에 영향을 미치지 않음

 - 단점 : 자주 사용하는 페이지가 스왑 영역으로 옮겨져 시스템의 효율이 떨어짐

 

페이지 테이블 크기

윈도우 NT의 페이지 테이블 크기

 - 페이지 테이블이 차지하는 공간은 1,048,576개 x 20bit = 약 2.62MB

 

VAX 운영체제의 테이블 크기

 - VAX의 페이지 테이블 크기는 8,388,608개 x 23bit = 약 24.11MB

 

쓰기 시점 복사

프로세스의 프레임 공유 예

 

fork() 시스템 호출로 프로세스를 복사하면 프레임 공유도 유지됨

 

프레임을 공유할 수 없는 경우 메모리 공간 확보 시기

 - 사용할지 안 할지 모르는 데이터를 위해 새로운 공간을 미리 만드는 것은 낭비

   -> 쓰기 시점 복사

    -> 데이터의 변화가 있을 때까지 복사를 미루는 방식