가상 메모리

★ 스와핑

• 현재 실행되지 않는 프로세스를 임시로 보조기억장치 일부 영역으로 쫓아내고, 생긴 메모리 공간에 또 다른 프로세스를 적재하여 실행하는 방식
• 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있음
  ⭐︎ 스왑 영역 : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
  ⭐︎ 스왑 아웃 : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
  ⭐︎ 스왑 인 : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것

 

★ 메모리 할당

⭐︎ 최초 적합(first fit) : 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 즉시 프로세스를 배치하는 방식

-> 검색을 최소화할 수 있고 빠른 할당이 가능

⭐︎ 최적 적합(best fit) : 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식

⭐︎ 최악 적합(worst fit) : 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식

 

 

★ 외부 단편화(external fragmentation)

• 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
• 이를 해결할 수 있는 대표적인 방안은 메모리를 압축하는 방법

  ⭐︎ 메모리 압축

• 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식으로 메모리 내에 저장된 프로세스를 적당히 재배치시켜 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
• 작은 빈 공간들을 하나로 모으는 동안 시스템을 중지해야 하며, 메모리에 있는 내용을 옮기는 작업에서 많은 오버헤드를 야기할 수 있음
  -> 다른 해결 방안으로 가상 메모리 기법, 그 중에서도 페이징 기법이 등장

 

 

★ 페이징

• 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법
• 메모리에 불연속적으로도 할당할 수 있음!
• 페이징에서도 스와핑을 사용할 수 있음. 스왑 아웃/스왑인을 페이지 아웃/페이지 인이라고 부르기도 함
• 한 프로세스를 실행하기 위해 프로세스 전체를 메모리에 적재할 필요없이, 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있음
• 물리 메모리보다 더 큰 프로세스를 실행할 수 있음

 

 

★ 페이지 테이블

• 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 순차적으로 실행할 수가 없음
• 이를 해결하기 위해 물리 주소에 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 이용
• 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있도록 도와주는 일종의 이정표
• 프로세스마다 각자의 프로세스 테이블을 가지고 있고 각 프로세스 페이지 테이블들은 메모리에 적재되어 있음
• 페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리킴

 * 각 프로세스들의 페이지 테이블 정보들은 각 프로세스의 PCB에 기록되고, 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경됨

• 페이지 테이블을 메모리에 두면 페이지 테이블을 보기 위해 한 번, 알게된 프레임에 접근하기 위해 한 번 이렇게 총 두 번 메모리에 접근해서 접근 시간이 늘어남
• TLB(Translation Lookaside Buffer) : 테이블의 캐시 메모리
• 위 문제를 해결하기 위해 CPU 곁에 TLB를 두어 페이지 테이블의 일부 내용을 TLB에 저장(최근에 사용된 페이지 위주)

⭐︎ TLB 히트 : 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 -> 메모리에 접근할 필요 없음

⭐︎ TLB 미스 : 페이지 번호가 TLB에 없을 경우 -> 메모리에 접근해야 함

 

 

★ 페이징에서의 주소 변환

• 하나의 페이지 혹은 프레임은 여러 주소를 포관하므로 특정 주소에 접근하려면 두 가지 정보가 필요함
  1. 어떤 페이지 혹은 프레임에 접근하고 싶은지
  2. 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
• 모든 논리 주소는 기본적으로 페이지 번호, 변위로 이루어져 있음

• 페이지 번호는 말 그대로 접근하고자 하는 페이지 번호
• 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보
• 논리 주소 <페이지 번호, 변위> → 물리 주소 <프레임 번호, 변위>

 * 논리 주소의 변위와 물리 주소의 변위 값은 같음

 

 

★ 페이지 테이블 엔트리

• 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리(PTE; Page Table Entry)라고 함
• 페이지 테이블 엔트리에 페이지 정보, 프레임 번호 외에 다양한 비트 정보가 들어가있음

⭐︎ 유효 비트 

• 현재 해당 페이지에 접근 가능하지 여부 알려줌
• 페이지가 메모리에 적재되어 있다면 1, 아니면 0
• CPU가 유효 비트가 0인 페이지로 접근하려고 하면 페이지 폴트라는 예외 발생
• 페이지 폴트가 일어나면 CPU는 기존 작업 내역을 백업하고 페이지 폴트 처리 루틴을 실행하여 메모리에 페이지를 적재한 후 유효 비트를 1로 변경해줌

⭐︎ 보호 비트

• 페이지 보호 기능을 위해 존재하는 비트
• 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인 경우 1, 읽기만 가능한 페이지는 0으로 표현
• 좀 더 복잡하게 r(Read), w(Write), x(eXecute)로 나눌 수 있음

⭐︎ 참조 비트

• CPU가 이 페이지에 접근한 적이 있는지 여부를 나타냄
• 읽거나 쓴 페이지는 1로 세팅, 한 번도 읽거나 쓴 적이 없는 페이지는 0으로 유지

⭐︎ 수정 비트(더티 비트)

• 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줌
• 변경된 적이 있으면 1, 없으면 0을 나타냄
• 페이지가 스왑 아웃될 경우 수정 비트가 0이면 추가 작업 없이 덮어쓰기만 하면 되고, 1인 경우는 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 함

 

 

★ 요구 페이징(demand paging)

• 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법

1. CPU가 특정 페이지에 접근하는 명령어를 실행
2. 해당 페이지가 메모리에 있을 경우(유효 비트가 1인 경우) CPU는 페이지가 적재된 프레임에 접근
3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0인 경우) 페이지 폴트가 발생
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정
5. 다시 1번을 수행

 

 * 순수 요구 페이징 : 아무런 페이지도 메모리에 적재하지 않은 채 실행 -> 페이지 폴트가 계속 발생하고 어느 정도 적재가 된 이후부터는 페이지 폴드 발생 빈도가 떨어짐

 

• 요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당을 해결해야 함
• 요구 페이징 기법으로 페이지들을 적재하다 보면 메모리가 가득 차고, 쫓아낼 페이지가 생김
• 이를 결정하는 방법을 페이지 교체 알고리즘이라고 함!!

 

 

★ 페이징 기법과 세그멘테이션 기법

 

⭐︎ 페이징 기법

• 외부 단편화가 발생하지 않음
• 페이지의 크기를 작게 설계함으로써 내부 단편화를 줄일 수 있음
• 페이지 사상으로 비용이 증가하고 수행속도가 감소
• 페이지는 프로그램에 상응하는 논리적 의미를 갖지 못함

⭐︎ 세그멘테이션 기법

• 기억장치 할당은 최초, 최적, 최악 적합 기법을 사용하여 해결하는 동적 기억장치 할당 방법을 사용 (외부적 단편화가 발생)
• 세그먼트 공유와 보호 측면에서 세그먼트는 페이지 시스템보다 수행방법이 쉽고 명확

 

Q. 페이징 기법에서 페이지 크기에 대한 설명으로 옳지 않은 것은?

1. 페이지 크기가 작아지면 페이지 테이블의 크기도 줄어든다.

2. 주기억장치는 페이지와 같은 크기의 블록으로 나누어 사용된다.

3. 페이지 크기가 커지면 내부 단편화 되는 공간이 커진다.

4. 페이지 크기가 커지면 참조되지 않는 불필요한 데이터들이 주기억장치에 적재될 확률이 높아진다.

 

-> 페이지 크기가 작아지면 관리해야할 페이지의 갯수가 많아지고 따라서 페이지 테이블의 크기도 커진다. 또한 페이지 fault, 페이지 교체가 자주 발생하며 CPU 유휴시간이 길어진다. 하지만 1개의 블록이동시간은 짧아지며 필요한 부분만 가져올 수 있다.

 

 

★ 페이지 교체 알고리즘

• 특정 페이지를 스왑 아웃 시켰을 때 페이지 폴트가 가장 적게 일어나는 알고리즘을 좋은 알고리즘이라고 평가함
• 페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수를 알아야함
• 페이지 폴트 횟수는 페이지 참조열(page reference string)을 통해 알 수 있음
• 페이지 참조열 : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

 

⭐︎ FIFO 페이지 교체 알고리즘

• 메모리에 가장 먼저 적재가 된 페이지부터 내쫓는 방식
• 아이디어와 구현이 간단하지만, 페이지가 얼마나 자주 사용이 되는지는 고려하지 않는다는 문제가 있음
• Belady's 모순 : 어떤 프로세스에게 할당된 페이지 프레임의 수가 증가하면 페이지 부재의 수가 감소하여야 하나, 페이지 프레임의 수가 증가될 때 현실적으로 페이지 부재가 더 증가하는 경우가 있다는 모순

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

• FIFO의 부작용을 개선한 알고리즘으로 FIFO 알고리즘과 기본 동작 원리는 같으나 참조 비트를 확인한다는 차이가 있음
• 가장 오래 머물렀으나 참조 비트가 1이라면 기회를 한번 더 주고, 적재 시간을 현재 시간으로 설정함
  • 페이지를 교체할 시기에 참조가비트가 '0'인 프레임을 찾기 위해 이동할 때 참조비트가 1인 프레임을 0으로 변환시키면서 2차적 기회를 주고 다음에 검사될 때 여전히 0일 경우 그 프레임을 교체시킴
• 가장 오래 머물렀으며 참조 비트가 0이라면 내쫓음

 

⭐︎ 최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려하는 알고리즘
• 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 방법
• 페이지 폴트 발생 빈도가 제일 낮지만, 사용되지 ‘않을’ 페이지를 예측하기란 매우 어려우므로 실제 운영체제에서 사용되기 보다는, 다른 페이지 교체 알고리즘의 '이론상' 성능을 평가하기 위한 목적으로 사용됨

 

⭐︎ LRU 페이지 교체 알고리즘 (Least Recently Used)

• 최적 페이지 교체 알고리즘과 비슷한 알고리즘으로 '오랫동안' 사용되지 않은 페이지를 교체하는 방법
• 각 페이지들이 참조될 때마다 그때의 시간을 테이블에 기억시키는 막대한 오버헤드를 초래하게 됨

 

* 스택을 이용한 LRU 알고리즘

- 스택을 이용하여 가장 최근에 사용한 페이지가 top, 교체될 페이지를 bottom에 위치시키는 방법

 

⭐︎ LFU 페이지 교체 알고리즘 (Least Frequently Used)

• 각 페이지마다 참조 횟수에 대한 계수기를 가지며 그 값이 가장 작은 페이지가 교체
• 어떤 프로세스의 초기 단계에서 한 페이지가 많이 사용되고 이후에 사용되지 않을 경우 큰 계수를 가지고 있기 때문에 더 이상 사용되지 않아도 메모리에 남아있는 경우가 있을 수 있음

 

⭐︎ NUR 페이지 교체 알고리즘 (Not Used Recently)

• 최근에 쓰이지 않는 페이지는 가까운 미래에도 쓰이지 않을 가능성이 많기 때문에 교체대상으로 선택
• 각 페이지 당 필요한 두 개의 하드웨어 비트(참조비트, 변형비트)를 가지고 이 값으로 교체할 페이지를 선택

 

 

★ 적재 정책

 

⭐︎ 지역성 (Locality)

• 실행 중인 프로세스에 의해 나타나는 특성으로 프로세스들은 기억장치 내의 정보를 균일하게 액세스하는 것이 아니라 어느 한 순간에 특정부분을 집중적으로 참조
• 시간 지역성 : 처음에 참조된 기억장소가 짧은 시간 안에 재사용되는 것을 의미하며 가까운 미래에도 계속 참조될 가능성이 높다는 것을 의미 (순환, 서브 프로그램, 스택, 계산이나 합계에 사용하는 변수)
• 공간 지역성 : 일단 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조되는 경향을 의미 (배열, 순차적 코드 실행, 프로그래머들이 관련된 변수들을 근처에 선언하는 경향)

 

⭐︎ 스래싱과 프레임 할당

• 나쁜 페이지 교체 알고리즘도 있지만, 프레임 수가 너무 적어도 페이지 폴트가 자주 발생할 수 있음
• 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 CPU 이용률이 낮아지고 성능이 저해되는 문제를 스래싱이라고 함
• 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 수만큼 프레임을 할당해 줄 수 있어야 함
• 다중 프로그래밍의 정도가 점점 더 커지면 스래싱 현상이 자주 일어나게 되므로 스레싱을 중단하려면 다중 프로그래밍의 정도를 낮춰야 함
• 지역성을 이용하여 현재 지역 크기보다 적은 페이지 프레임을 할당하면 페이지 부재가 발생하는 원인이 될 수 있으며 프로세서가 요구하는 최소한의 수보다 페이지 프레임 수가 적으면 적을수록 페이지 부재율이 증가하며 프로세서의 효율 떨어짐

 

⭐︎ 페이지 부재 비율 (PFF; Page Fault Frequency)

• 스래싱을 예방하는 직접적인 액세스 방법으로, 페이지 환경에서 프로세스의 실행을 측정하는 기준이 됨
• 페이지 부재 비율이 높다는 것은 프로세스에 더 많은 프레임이 필요하다는 의미이고, 페이지 부재 비율이 낮다는 것은 프로세스에 프레임이 너무 많다는 의미
• 페이지 부재 비율이 상한 값을 초과하고 빈 프레임이 있을 때 해당 프로세스에 프레임을 할당하고 페이지 부재 비율이 하한 값 이하로 떨어지면 현재 프로세스의 프레임을 제거
• 페이지 부재 비율이 상한 값을 초과하고 빈 프레임이 없을 때 희생시킬 프로세스를 선택하고, 그 프로세스의 실행을 일시 중지시킨 후, 현재 프로세스의 페이지 부재 비율이 하한 값 이하로 떨어지면 현재 프로세스의 프레임을 제거
• 스래싱은 페이지 부재에서 발생하므로 페이지 부재 비율을 조절하는 것이 필요

 

• 프레임 할당 방식

   ⭐︎ 정적 할당 방식

균등 할당 : 모든 프로세스에 동일한 프레임을 배분하는 방식

비례 할당 : 프로세스 크기에 따라 프레임을 배분하는 방식

   ⭐︎ 동적 할당 방식

작업 집합 모델 : 작업 집합의 크기만큼만 프레임을 할당하는 방식

* 작업 집합 : 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합

페이지 폴트 빈도 : 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식

 

 

 

 

 

 

 

※ 참고

2024.01.24 - [CS/컴퓨터구조] - 기억장치 - 가상메모리, RAID

기억장치 - 가상메모리, RAID