[9장] 가상 메모리 관리

쉽게 배우는 운영체제 (조성호 著, 한빛아카데미) 참고하여 작성했습니다 

가상 메모리의 개념

1. 논리적 주소를 물리적으로 분리 →
   메인 메모리 용량을 초과한 프로세스에 주소를 지정하여 메모리 제한 없이 사용 가능
2. 프로그램 전체를 동시에 실행하지 않으므로 메모리 일부만 적재해도 실행 가능
3. 활동 영역을 메인 메모리에 유지하면서 디스크와 메모리사이의 스왑인, 아웃 기능을 활용하여 메모리 효율적 사용 
4. 메인 메모리의 제한된 용량과 중첩 사용 문제 해결

가상 메모리를 이용한 메인 메모리 운영의 특징

1. 예외를 처리하는 오류 처리 코드는 자주 필요하지 않으며, 발생하지 않을 수도 있다
2. 배열, 리스트, 테이블 등은 실제로 사용한 크기보다 항상 더 크게 정의할 수 있다
3. 문서 편집기의 복사하기, 붙이기, 잘라내기, 삽입하기 메뉴는 선택 메뉴 한 개만 메인 메모리에 적재하고 나머지는
   메인 메모리에서 내보내도 된다

---

메모리에 프로그램 일부만 적재할 때의 문제점 및 해결 방법

장점 

1. 중첩을 고려할 필요가 없으므로 프로그래밍 용이
2. 프로세서의 이용률과 처리율 향상 (응답시간이나 반환시간은 향상되지 않음)

문제점

1. 메모리와 디스크 사이의 이동량 증가, 스와핑 공간 필요, 페이지 적재 및 복귀 시 페이징 알고리즘 필요

해결방법

실행중인 프로세스가 참조하는 주소(가상주소, 논리적주소) 와 메인 메모리가 사용하는 물리적 주소 분리 

 

매핑 : 가상 주소 → 물리적 주소로 변환 (변환 함수로 표현)

매핑은 가능한 빨리 수행하지 않으면 성능이 떨어지고 가상 메모리의 사용 효과가 낮아진다. 

---

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

1. 메모리를 효율적으로 관리하기 위해서 (메모리가 꽉 차면 관리하기 어려우므로 가급적 적은 양의 프로세스만 유지)
2. 응답 속도를 향상 시키기 위해서 (용량이 큰 프로세스를 가져오면 응답이 늦어질 수 있으므로 필요한 모듈만 실행)

---

요구 페이징

• 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것
  (=필요한 페이지만 사용자가 요구할 때올리므로 요구페이징) 
• 프로그램 실행 시 프로그램의 전체가 아닌 일부만 메인 메모리에 적재하되,
  순차적으로 작성된 프로그램의 모듈을 처리 시 다른 부분은 실행하지 않음
• 페이지를 쓰지 않을 경우, 미리 페이지를 가져오는 방식은 메모리 낭비의 원인 
• 실행 중인 프로세스들의 요구 페이지만 메모리에 반입하여 프로세스의
  모든 페이지를 메모리에 동시에 적재하지 않음 (↔ 순수스와핑)
• 메모리의 절약, 효율적 관리, 프로세스 응답 속도 향상등의 효과를 볼 수 있다. 

---

스왑 영역과 유효 비트

가상 메모리에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 있다. 

이 때 페이지가 스왑 영역에 있는 경우는 두 가지 이다. 

 

하나는 요구 페이징으로부터 물리 메모리에 올라가지 못 한 경우.

나머지는 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우. 

위 두 개의 경우 사용하는 것이 유효비트

유효비트란? 페이지 테이블에 페이지가 메모리에 있는지, 스왑 영역에 있는지 표시하는 역할  

 

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

 

PTE(페이지 테이블 엔트리) (=페이지 테이블의 한 행을 의미) = 페이지 번호 + 플래그 비트 + 프레임 번호로 구성 

 

페이지 번호 : 직접 매핑시 필요없지만 연관 매핑시에는 프레임 번호와 함께 필요함

프레임 번호(=주소 필드) : 가상 주소의 해당 페이지가 어느 프레임에 있는지 알려 주는 자료 구조 

플래그 비트의 종류

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

---

페이지 부재 (Page fault)

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

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

 

유효비트

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

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

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

 

페이지 교체

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

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

 

페이지 교체 알고리즘

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

 

대상 페이지 (victim page)

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

 

세그멘테이션 오류

사용자의 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생.

해당 프로세스를 강제 종료하여 해결함

---

지역성

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

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

 

지역성의 종류

 

1. 공간의 지역성 

(현재 위치 기준) 가까운 데이터에 접근할 확률 > 먼 거리에 있는 접근할 확률

2. 시간의 지역성

(현재 기준) 가까운 시간에 접근한 데이터의 사용 확률 > 먼 시간에 접근한 데이터의 사용 확률 

3. 순차적 지역성

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

---

페이지 교체 알고리즘

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

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

 

1. FIFO 페이지 교체 알고리즘 (First In First Out page algorithm)
   메모리에 가장 먼저 들어온 페이지(오래된 페이지)를 대상 페이지로 선정하여 스왑 영역에서 쫓아냄 
   메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고, 나머지 페이지가 위쪽으로 가고
   새 페이지가 아래쪽의 남은 공간에 들어온다.
   
   가장 간단한 알고리즘
   메모리 페이지는 선입선출큐가 관리 (오래된 페이지를 무조건 먼저 빼냄, 성능 저하)
   큐의 크기는 사용 가능한 메모리 프레임의 수 
   
   
2. 최적 페이지 교체 알고리즘
   앞으로 사용하지 않을 페이지를 스왑 영역으로 옮김
   (메모리가 사용할 페이지를 미리 보고 페이지 교체 시점~사용 시점까지 중 가장 먼 페이지를 대상 페이지로 선정)
   모든 알고리즘 중 페이지 부재 비율이 가장 낮음
   이상적인 방법이지만 실제로 구현할 수 없음 
   
   
3.  최적 근접 알고리즘
   실제 구현이 가능하면서도 성능이 최적 근접 알고리즘에 근접한 알고리즘
   
   LRU 페이지 교체 알고리즘 (Least Recently Used) (=최근 최소 사용 페이지 교체 알고리즘)
   메모리에 올라온 후 가장 오랫동안 사용안한 페이지를 스왑 영역으로 옮김 
   페이지에 접근한 지 가장 오래된 페이지를 교체
   알고리즘은 시간 기준으로 구현
   ①카운터에 기반한 구현 방법과 ②스택을 이용한 순서 결정 방법, ③참조 비트 시프트 방식이 있음
   
   LFU 페이지 교체 알고리즘 (Least Frequently Used)
   현재 프레임에 있는 페이지마다 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮김
   
   NUR 페이지 교체 알고리즘 (Not Used Recently) (=최근 미사용 페이지 교체 알고리즘)
   LRU, LFU 사용시 오버헤드가 큰 단점을 보완
   최근 사용하지 않는 페이지는 미래에도 사용하지 않을 가능성이 높다는 아이디어가 바탕
   두 개의 비트만으로 구현 가능
   페이지마다 참조 비트(페이지 접근, 1) 와 변경 비트(페이지 변경, 1)를 가짐
   대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾음
   같은 비트의 페이지가 여러 개면 무작위로 대상 페이지를 선정 
   
   FIFO 변형 알고리즘 (First In First Out page replacement algorithm)
   ① 2차 기회 페이지 교체 알고리즘
   
   FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용
   

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

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

   가장 오랫동안 메인 메모리에 있던 페이지 중 자주 사용하는 페이지의 대치  방지
   

   최근 최소 사용 알고리즘과 성능은 비슷하지만 오버헤드 적음

    

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

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

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

   
   

 

          4. 무작위 페이지 교체 알고리즘 (random page replacement algorithm)
          스왑 영역으로 쫓아낼 대상 페이지를 특별한 로직 없이 무작위로 선정
          지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 교체 대상 페이지로 선정되기도
          하여 성능이 좋지 않음

---

스래싱과 프레임 할당

스래싱(thrashing)

• 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태
• 스래싱은 컴퓨터의 가상 메모리 리소스가 과도하게 사용되어 페이징 및 페이지 오류가
  지속적으로 발생하여 대부분의 응용 프로그램 처리를 방해할 때 발생
• 너무 많은 다중 프로그래밍, 즉 새로운 프로세스가 늘어나면 프로세스에 고정된 프레임 수가
  현재 활동에 충분하지 않으므로 서로 프레임을 빼앗기고 뺏는 과정(지속적인 페이지 부재)가 발생.

스래싱 발생 시점

• CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리에 가져오는
  작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 되는 시점
• 물리 메모리의 크기를 늘리면 스레싱 발생 지점이 늦춰져서 프로세스를 원만하게 실행할 수 있음

스래싱과 프레임 할당

• 프로세스에 너무 적은 프레임을 할당하면 페이지 부재가 빈번히 일어남
• 프로세스에 너무 많은 프레임을 할당하면 페이지 부재는 줄지만 메모리가 낭비됨
• 프로세스에 프레임을 할당하는 방식은 크게 정적 할당과 동적 할당으로 구분

스래싱의 예방

• 작업 집합(워킹셋) 모델 : 프로세스가 실제로 얼마큼 프레임을 많이 사용하는지
  검사하여 지역 모델(작업 집합 모델)을 정의
• 지역 모델 : 프로세스를 실행할 때 프로그램은 보통 지역 몇 개로 중첩해서 구성하므로
  한 지역 에서 다른 지역으로 이동하는 과정을 의미함

---

정적 할당

프로세스 실행 초기에 프레임을 나누어 준 후 크기를 고정하는 방식 

균등 할당과 비례 할당 방식이 있음 

프로세스를 실행하는 초기에 프레임을 할당하므로 프로세스 실행 동안 메모리 요구를 반영하지 못하는 단점이 있음 

 

균등 할당 

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

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

크기가 작은 프로세스의 경우 메모리가 낭비됨 

 

비례 할당

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

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

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

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

---

동적 할당 

시시각각 변하는 프로세스의 요청을 수용하는 방식 

 

작업 집합 모델 (working set model)

지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘

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

작업집합 크기 = 작업집합 모델에서 물리 메모리에 유지할 페이지 크기

 

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

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

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

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

 

페이지 부재 빈도 (page fault frequency)

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

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

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