[쉽게 배우는 운영체제 2판] 9. 가상 메모리 관리

 

 

 

 

1. 요구 페이징

• 프로세스가 필요로 하는 데이터를 프로세스가 요청을 할 때 메모리로 가져올지를 결정

1. 요구 페이징의 개요

• 작업을 하지 않는 프로세스나 좀비 프로세스가 메모리를 차지아혀 메모리 관리가 복잡해지므로, 메모리에는 꼭 필요한 프로세스만 유지하는 것이 좋다.
• 큰 프로세스를 실핼할때는 필요한 메모리만 올리고 나머지는 필요하다고 판단될 때 메모리로 불러온다.
  • 메모리를 효율적으로 관리할 수 있다. 적은 양의 프로세스 유지
  • 응답 속도를 향상할 수 있다. 필요한 모듈만 올려 실행
• 요구 페이징: 프로그램 일부만 가져와 실행하고 사용자가 요구할 때 해당 모듈을 메모리에 올리면 메모리의 절약과 효율적 관리, 프로세스 응답 속도 향상 등의 효과를 볼 수 있다.
• like 포토샵: 메모리 포토샵의 본체 프로그램만 올리고 필터는 사용자가 필요로 할 떄마다 메모리로 가져오는 것이 효율적이다.

• 반대로, 미리 가져오기: 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식: 예상이 안 맞으면 말장 도루묵

 

 

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

• 가상 메모리의 크기는 물리 메모리와 스왑 영역을 합친 것이다.
  • 스왑 영역은 하드디스 크에 존재하나 메모리 관리자가 괸리하는 것  
  • 스왑인, 스왑아웃
  • 유효 비트
  • 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우
  • 메모리가 꽉 차서 스왑영역으로 옮겨 온 경우
• PTE: 페이지 테이블 엔트리: 페이지 번호, 플래그 비트, 프레임 번호
  • 프레임 번호(주소 필드): 가상 줏의 해당 페이지가 어느 프레임에 있는지 알려주는 자료구조
  • 플래그 비트: 접근 비트, 변경 비트, 유효 비트, 읽기 비트, 쓰기 비트, 실행 비트
    • 접근 비트: 페이지가 메모리에 올라온 후 사용한 것이 있는지 알려준다.
    • 변경 비트: 페이지가 메모리에 올라온 후 데이터 변경이 있었는지 알려준다.
    • 유효 비트: 페이지가 실제 메모리에 있는지를 나타낸다. (메모리, 스왑영역)
    • 읽기 비트, 쓰기 비트, 실행 비트: 접근 권한 비트

 

 

 

 

3. 페이지 부재

• 가상 메모리의 페이지 테이블에는 유효비트로 메모리에 있는지, 스왑영역에 있는지 알 수 있다. 
  
  • 유효비트가 0일 때는 페이지가 메모리에 있으므로 주소 필드에 물리 메모리의 프레임 번호가 저장된다.
  • 유효비트가 1일 때는 페이지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지의 주소가 저장된다.

 

 

 

 

• 페이지 부재: 프로세스가 페이지를 요청했을 떄 페이지가 메모리에 없는 상황
  • 페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다. 
    (스왑 -> 메모리)
  • 페이지 부재가 발생하면 스왑영역에 있는 페이지를 메모리의 빈 영역에 올리고 페이지 테이블을 갱신(업데이트) 한다. 
  • 빈페이지가 없으면 메모리에 있는 프레임 중 하나를 스왑 영역으로 보낸 후, 해당 페이지로 가져올 수 있다 -> 페이지 교체 알고리즘 ( 스왑 영역으로 보낼 페이지를 대상 페이지라고 한다.)

 

 

 

 

• 페이지 부재 프로세스
  1. 유효 비트가 1: 페이지 부재 발생
  2. 메모리가 꽉 차 있으므로 페이지 중 하나를 스왑 영역으로 보내야 한다. 페이지를 대상 페이지로 선정하여 스왑 영역으로 옮긴다. (스왑아웃)
  3. 대상 페이지 PTE 0의 유효 비트가 0에서 1로, 주소 필드 값이 프레임 3에서 스왑주 소 6으로 바뀐다. (업데이트)
  4. 스왑 영역 1 번에 있던 페이지 E가 프레임 3으로 올라간다. (스왑인)
  5. PTE 4의 유효 비트가 1에서 0으로, 주소 필드 값이 스왑 주소 1에서 프레임 3으로 바뀐다.

스왑 영역 1 번에 있던 페이지 E가 프레임 3으로 올라간다（스왑인）

 

 

 

• 세그먼테이션과의 차이
  • 세그먼테이션 오류는 사용자 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생한다.
  • 페이지 부재: 물리 메모리에 없을 때 발행하는 것으로 스왑 영역에 해당 페이지를 물리 메모리로 옮긴 후 작업을 진행한다.

 

 

 

 

 

 

 

 

 

 

2. 페이징 교체 알고리즘

• 메모리가 꽉 찾을 때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 재배치 정책에 대해 알아보자.

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

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

페이지 교체 알고리즘의 종류

• 간단한 알고리즘
  • 무작위: 무작위로 선정한 페이지
  • FIFO: 처음 메모리에 올라온 페이지
• 이론적 알고리즘
  • 최적: 미래의 메모리 접근 패턴을 보고 대상 페이지를 선정
• 최적 근접 알고리즘
  • LRU: 시각적으로 멀리 떨어진 페이지
  • LFU: 사용빈도가 적은 페이지
  • NUR: 최근에 사용할 적이 없는 페이지
  • FIFO 변형

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

• 페이지 부재 횟수, 평균 대기 시간, 전체 작업에 걸리는 시간, 페이지 부재 횟수와 페이지 성공 횟수를 비교
• 유지 비용

 

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

• 특별한 로직 없이 무작위로 선정한다. 

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

• 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫓아낸다. 
• F: 페이지 부재로 원하는 페이지가 메모리에 없는 경우 
• S: 원하는 페이지가 메모리에 있는 경우

• 큐
• 맨 위에 있는 페이지는 가장 오래된 페이지, 새로운 페이지는 맨 아래로 삽입된다. 
• 메모리가 꽉차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들이 위쪽으로 이동하며, 새로운 페이지는 아래로 들어옴.
• 페이지 부재는 일곱 번 발생
• 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어진다.

 

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

• 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시 가장 멀리 있는 대상 페이지를 선정한다. 
• 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정
• 미래의 접근 패턴을 알기는 불가능

 

 

5. LRU 페이지 교체 알고리즘

• 최근 최소 사용 페이지 교체 알고리즘

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

• 페이지에 접근한 시간을 기록하여 구현
• 페이지에 접근한 지 가장 오래된 페이지를 교체
• 페이지에 읽기, 쓰기, 실행과 같은 연산이 이루어진 시간을 기준으로 한다. 
• 메모리에 추가 공간이 필요한다. 

 

 

카운터에 기반한 구현

• 시간기록으로 구현할 수 있지만, 카운터로도 가능한다. 
• 메모리에 추가 공간이 필요한다. 

참조 비트 시프트 방식

• 각 페이지에 일정 크기의 참조비트를 만들어 사용한다. 
• 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀐다
• 참조 비트 중 가장 작은 값을 대상 페이지로 선정한다.

가장 작은 값은 가장 오랫동 안 접근하지 않은 페이지

 

 

 

6. LFU 페이지 교체 알고리즘

• 최소 빈도 사용 알고리즘
• 페이지가 몇 번 사용 되었는지
• 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다
• 낭비되는 메모리 공간이 많다는 것

 

 

 

 

 

7. NUR 페이지 교체 알고리즘

• 불필요한 공간 낭비 문제 해결
• 추가 비트 2개만 사용하여 미래를 추정한다.
• 참조 비트(페이지에 접근하면 1)와 변경 비트(페이지가 변경 되면 1)

 

 

 

 

8. FIFO 변형 알고리즘

• 2차 기회 페이지 교체 알고리즘과 시계 알고리즘

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

• 페이지 부재 없이 성공하면 큐의 맨뒤에 페이지를 옮겨서 기회를 한번 더 준다. 
• 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가된다는 단점

 

 

 

 

시계 알고리즘

• 원형큐
• 포인터로 대상 페이지를 가르킨다.

 

• 참조 비트의 초깃값은 0이고, 메모리에 있 는 페이지를 성공적으로 참조하면 0에서 1로 변경된다.
• 포인터는 스왑 영역으로 쫓겨날 페이지르 가르킨다. 
• 참조 비트가 1 인 페이지는 건너 뛰고, 메모리의 바닥에 도착하면 원형 큐처럼 다시 메모리의 상단으로 이동한다.
• 대상에서 제외되는 경우는 단 한 번뿐

 

 

 

 

 

 

 

 

 

 

 

 

 

3. 스레싱과 프레임 할당

• 프레임 할당과 관련한 다양 한 이론과 방법론

 

1. 스레싱

스레싱의 개념

• 물리 메모리를 늘리면 컴퓨터가 빨라진다. 
• CPU의 속도도 빨라야 하지만 물리 메모리의 크기도 커야 성능이 좋다.
• 스레싱: 하드디스크의 입출력이 너무 많아 져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태

물리 메모리의 크기와 스레싱

• 멀티 프로그래밍 정도: 동시에 실행하는 프로그램의 수
• 멀티 프로그래밍 정도가 너무 높으면 스레싱이 발생한다. 
• 멀티프로그래밍 정도와 CPU 사용률의 관계
  • CPU사용률이 계속 증가하다가 메모리가 꽉 차면 CPU 작업하는 시간보다 스왑 영역으로 페이지를 보내고 가져오는 시간이 빈번해져 CPU가 작업 할 수 없는 상태에 이른다. 이 시점이 스레싱 발생 지점이다. 
• 따라서 물리 메모리를 늘리면 컴터가 빨라진다. 
  • 물리 메모리가 작업하는 데 충분한 크기가 되면 그 이후에는 크기를 늘려도 작업 속도에 영향을 미치지 않는다.

 

 

스레싱과 프레임 할당

• 어떤 프로세스에는 너무 적은 프레임을 할당하여 페이지 부재가 빈번히 일어나고
• 어떤 프로세스에는 너무 많은 프레 임을 할당하여 페이지 부재는 줄었으나 대신 메모리를 낭비한다면 전반적으로 시스템 성능이 낮아진다.
• 프로세스에 프레임을 할당하는 방식은 크게 정적 할당과 동적 할당으로 구분

 

 

 

2. 정적 할당

• 정적할당은 프로세스 실행 초기에 프레임을 나누어 준 후 그 크기를 고정한다.
• 균등 할당 방식과 비례 할당 방식

 

균등 할당 방식

• 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당한다. 
• 크기가 큰 프로세스의 경우 필요한 만큼의 프레임을 할당받지 못하기에 페이지 부재가 빈번하게 일어난다.
• 크기가 작은 프로세스는 메모리 낭비가 발생한다.

 

 

 

비례 할당 방식

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

• 필요로 하는 프레임을 유동적으로 반영하지 못한다.
• 사용하지 않을 메모리를 처음부터 미리 확보하여 공간을 낭비한다.

 

 

 

 

3. 동적 할당

• 시시각각 변하는 요청을 수용하는 방식이 동적할당이다. 
• 작업 집합 모델 사용 방식, 페이지부재 빈도 사용 방식

작업 집합 모델

• 지역성 이론을 바탕: 가장 최근에 접근한 프레임이 이후에도 참조될 가능성이 높다는 가정에서 줄발
• 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고, 이 집합에 있는 페이지들을 물리 메모리에 유지하여 프로세스의 실행을 돕는다.
• 집합의 크기: 물리 메모리에 유지할 페이지의 크기, 작업 집합에 들어갈 최대 페이지 수를 의미한다.  +  얼마나 자주 작업집합을 갱신할 것인지를 의미  
• 작업 집합 윈도우:  현재 시점에서 최대 어느 범위까지의 페이지를 살펴볼 것인가를 결정하는 것

윈도우를 10 / 작업집합에는 WS(tl)={1, 7, 5, 2, 3} WS(t2)={2, 3, 4, 1, 7} WS(t3)={5, 3, 2, 4}

• 다음번 윈도우에 도달할 때까지 물리 메모리에 보존된다.
• 작업집합 윈도우에는 현재 시 점(tl)부터 시간적으로 가까운 페이지부터 삽입된다는 점에 주의
• 작업집합 윈도우의 크기에 따라 프로세스의 실행 성능이 달라진다
  • 작업 윈도우를 너무 크게 잡으면 필요없는 페이지가 메모리에 남아 다른 프로세스에 영향을 미치고
  • 너무 작게 잡으면 필요한 페이지가 스왑 영역으로 옮겨져서 프로세스 성능이 떨어진다. 
• 어떤 프레임을 물리 메모리에 유지해야 하는지는 알 수 있지만 프레임을 얼마나 할당해야 하는지는 알 수 없다.

 

 

페이지 부재 빈도

• 성능을 높이는 방법이지만 스레싱 문제를 해결하지는 못한다.
• 프로세스가 필요로 하는 양을 동적으로 결정하는 방법
  • 페이지의 부재 횟후를 기록하여 페이지 부재 비율을 계산하는 방식
  • 페이지 부재 비율의 상한선과 하한선을 설정한다. 
• 페이지 부재 빈도 방식에서는 프로세스를 실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절한다.

 

 

 

 

 

4. 전역 교체와 지역 교체

• 페이지 교체 알고리즘에 따라 전역 교체와 지역 교체가 있다. 
  • 전역 교체: 전체 프레임을 대상으로 교체 알고리즘을 적용한다.
  • 지역 교체: 현재 실행 중인 프로세스의 프레임을 대상으로 교체 알고리즘을 적용한다. 
• 가상 메모리에 프로세스 A, B, C가 올라와 있고 NUR 페이지 교체 알고리즘을 사용한다.
  • 전역 교체 방식: (a)와 같이 물리 메모리의 모든 프레임을 대상으로 스왑 영역에 보낼 페이지를 찾는다, 참조 비트와 변경 비트가(0, 0)인 프레임 6의 C2가 스 왑 영역으로 옮겨진다.
    • 자신에게 할당된 프레임의 전체 개수에 변화가 없다 = 페이지 교체가 다른 프로세스에 영향을 미치지 않는다
    • 할당된 프레임을 빼앗으면 프레임을 빼앗길 프로세스는 스레싱 발생 지점에 도달할 수 있다. 
  • 지역 교체 방식: (b)와 같이 물리 메모리의 프로세스 A와관련된 프레임을 대상으로 스왑 영역에 보낼 페이지를 찾는다. 그 결과 참조 비트와 변경 비트가 (1, 0 )인 프레임 1의 A2가 스왑 영역으로 옮겨진다.
    • 지역 교체 방식에서는 전체 프로세스에 할당된 프레임의 수가 변하지 않기 때문에 스레싱을 줄일수 있다.
    • 자주 사용하는 페이지가 스왑 영역으로 옮겨지면 시스템 효율이 떨어진다는 것
      • 지역 교체 방 식의 특성상 자주 사용되는 프레임 2가 스왑 영역으로 옮겨졌다.

 

 

 

 

 

 

---

출처 : 조성호 , 『IT CookBook, 쉽게 배우는 운영체제(2판)』한빛아카데미(2023).