[운영체제] 가상 메모리

‘혼자 공부하는 컴퓨터구조+운영체제 - 강민철’ 책을 참고하여 작성한 포스트입니다.

---

연속 메모리 할당

• 프로세스에 연속적인 메모리 공간을 할당하는 것

스와핑

• 메모리에 적재된 프로세스들 중 현재 실행되지 않는 프로세스를 임시로 보조기억장치 일부 영역으로 쫓아내고, 그렇게 해서 생긴 메모리 상의 빈 공간에 다른 프로세스를 적재하는 방식을 스와핑(swapping) 이라고 한.
• 스와핑으로 보조기억장치로 보내지는 프로세스가 임시로 저장되는 영역을 스왑 영역(swap space) 이라고 한다.
• 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃(swap-out),
• 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨 오는 것을 스왑 인(swap-in) 이라고 한다.
• 물론 기존의 주소와 다른 주소에 적재될 수도 있다.

메모리 할당

• 프로세스를 메모리 내에 연속적으로 할당하는 방식에는 세 가지가 있다.

최초 적합(first fit)

• 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식이다.
• 빠른 할당이 가능하다

최적 적합(best fit)

• 운영체제가 메모리 내의 빈 공간을 모두 검색해 본 후, 프로세스 적재 가능한 공간 중 가장 작은 공간에 배치하는 방식이다.

최악 적합(worst fit)

• 운영체제가 메모리 내의 빈 공간을 모두 검색해 본 후, 프로세스 적재 가능한 공간 중 가장 큰 공간에 배치하는 방식이다.

외부 단편화(external fragmentation)

• 프로세스들이 메모리에 연속적으로 할당되는 환경에서는 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생긴다.
• 이 공간보다 큰 프로세스는 적재할 수 없으므로 결국 메모리 낭비로 이어지고, 이러한 현상을 외부 단편화 라고 한다.
• 즉, 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상이다.
• 외부 단편화를 해결하는 대표적 방법으로 메모리를 압축(compaction) 하는 방법이 있다. 메모리 조각 모음!
• 하지만 이 방법은 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고,
• 메모리에 있는 내용을 옮기면서 많은 오버헤드가 발생하며,
• 어떤 프로세스를 어떻게 움직여 효과적으로 압축할 지에 대한 명확한 방법을 결정하기 어렵다.
• 이에 또 다른 방안인 가상 메모리 기법 중에서도 페이징 기법을 오늘날 많이 이용한다.

페이징이란?

• 가상 메모리(virtual meemory)는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술.
• 가상 메모리 관리 기법에는 크게 페이징 과 세그멘테이션이 있다.
• 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임(frame) 이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법을 페이징(paging) 이라고 한다.
• 페이지 단위로 프로세스를 자르고, 조각들을 잘린 메모리 조각들에 불연속적으로 적재한다.
• 페이징에서도 스와핑을 사용할 수 있는데, 페이지 단위로 스왑 아웃/인 이 된다. 각각 페이지 아웃(page out), 페이지 인(page in) 이라 부르기도 한다.
• 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨 둠으로써 물리 메모리보다 더 큰 프로세스 실행이 가능하다

페이지 테이블

• 물리 주소(실제 메모리 내의 주소)에 불연속적으로 배치된 페이지들을 논리 주소에(CPU가 바라보는 주소) 연속적으로 배치되도록 할 수 있게 해주는 것이 페이지 테이블(page table) 이다.
• 페이지 테이블은 페이지 번호와 프레임 번호가 짝지어져 있으며, CPU는 페이지 테이블을 통해 해당 페이지가 적재된 프레임을 찾을 수 있다.
• 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있으며, CPU 내의 페이지 테이블 베이스 레지스터(PTBR, page table base register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다.
• 페이지 테이블은 각 프로세스의 PCB에 기록된다. 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경된다.
• CPU가 페이지 테이블에 접근하는 속도를 줄이기 위해 CPU 곁에 (일반적으로 MMU 내에) TLB(translation lookaside buffer) 라는 페이지 테이블의 캐시 메모리를 둔다.
• 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장한다.
• 캐시와 비슷하게 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB hit라고 하며, 그러지 않을 경우 TLB miss라고 하며 메모리 내의 페이지 테이블에 접근해 찾는다.

페이징은 외부 단편화 문제를 해결하지만, 내부 단편화(internal fragmentation)라는 문제가 생길 수 있다.
모든 프로세스가 페이지의 배수는 아니므로 잘리고 남은 나머지를 포함하는 프레임은 일부가 비어 있을 수 있다.
페이지 크기를 너무 작게하면 페이지 테이블이 너무 커지므로 적절히 조절하는 것이 중요하다.

페이징에서의 주소 변환

• 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호(page number)와 변위(offset)로 이루어져 있다.
• 페이지 번호를 통해 접근하고자 하는 페이지 번호를 찾을 수 있고, 변위는 접근하려는 주소가 페이지 번호로 부터 얼만큼 떨어져 있는지를 알려준다.
• 예를 들어 페이지 번호가 5이고, 변위가 2인 논리 주소에 접근할 때, CPU가 접근하게 될 물리 주소는..
• 페이지 테이블에서 페이지 번호에 따른 프레임 번호를 찾고, 메모리 상에 해당 프레임이 적재되어 있는 시작 주소에서 변위 값만큼 더한 주소이다.

페이지 테이블 엔트리(PTE, page tabel entry)

• 페이지 테이블 엔트리에는 페이지 번호, 프레임 번호 외에도 유효 비트, 보호 비트, 참조 비트, 수정 비트 등이 있다.

유효 비트(valid bit)

• 현재 해당 페이지에 접근 가능한지 여부를 알려 준다.
• 현재 페이지가 메모리에 적재되어 있다면 유효 비트가 1, 보조기억장치에 적재되어 있다면 유효 비트가 0이다.
• 유효 비트가 0인 페이지에 접근하려고 하면 페이지 폴트(page fault)라는 예외(exception)가 발생한다.

CPU가 페이지 폴트를 처리하는 과정은 하드웨어 인터럽트를 처리하는 과정과 유사하다.

1. CPU는 기존 작업 내역을 백업하고,
2. 페이지 폴트 처리 루틴을 실행한 뒤,
3. 원하는 페이지를 메모리로 가져오고 유효 비트를 1로 변경해 준다.

보호 비트(protection bit)

• 페이지 보호 기능을 한다.
• 1개의 비트인 경우 1이면 읽고 쓰기가 모두 가능, 0이면 읽기 전용 페이지이다.
• 3개의 비트인 경우 r(read), w(write), x(execute) 의 조합으로 읽기, 쓰기, 실행 권한을 나타낸다.
• 각 비트가 1이면 가능, 0이면 불가능이다.

참조 비트(reference bit)

• CPU가 이 페이지에 접근한 적이 있는지 여부를 나타낸다.
• 적재 이후 CPU가 읽거나 쓴 적이 있으면 1, 없으면 0이다.

수정 비트(modified bit)

• 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부.
• 더티 비트(dirty bit) 라고도 부른다.
• 1이면 변경된 적이 있는 페이지, 0이면 한번도 접근한 적 없거나 읽기만 한 페이지다.
• 0이면 페이지 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 하지 않겠지.
• 1인 페이지가 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가 되어야 한다.

쓰기 시 복사 (coppy on write)

• 페이징의 장점 중에 프로세스 간에 페이지를 공유할 수 있다는 점이 있다. 그 중 대표적인 것이 쓰기 시 복사(copy on write)다.
• copy on write 에서 부모 프로세스와 동일한 자식 프로세스가 생성되면 자식 프로세스는
• 새로 프레임을 할당받지 않고 부모 프로세스와 동일한 프레임을 가리킨다.
• 쓰기 작업을 않고 읽기 작업만 이어간다면 이 상태로 지속된다.
• 둘 중 하나가 페이지에 쓰기 작업을 하는 순간 해당 페이지가 메모리상의 별도의 공간(프레임)으로 복제되어 각각의 고유한 페이지가 할당된 프레임을 가리킨다.

계층적 페이징(hierarchical paging)

• 프로세스의 크기가 커지면 프로세스 테이블의 크기도 커지므로 모든 페이지 테이블 엔트리를 메모리에 두는 것은 메모리 낭비다.
• 테이블을 페이징 하여 여러 단계의 페이징을 두는 방식으로, 다단계 페이지 테이블(multilevel page table) 이라고도 불린다.
• CPU와 가장 가까이 위치한(가장 바깥) 페이지 테이블만 항상 메모리에 유지하면 된다.
• 계층적 페이징 상황에서 논리 주소는 기존의 ‘페이지 번호 + 변위’ 에서 ‘바깥 페이지 번호 + 안쪽 페이지 번호 + 변위’ 가 된다.
• 계층이 2개 이상이 될 수도 있지만 늘어날수록 페이지 폴트 발생 시 메모리 참조 횟수가 많아질 것이므로 늘리는 것이 반드시 좋지는 않을 수 있다.

요구 페이징(demanding paging)

• 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하는 것이 아닌 필요한 페이지만을 메모리에 적재하는 기법
• 아무런 페이지도 적재하지 않은 채 실행하는 것을 순수 요구 페이징(pure demand paging) 기법이라고 하며,
• 당연히 적재 되지 않은 페이지에 CPU가 접근할 때 페이지 폴트가 발생하고 페이지 폴트 처리 루틴에 따라 해당 페이지를 메모리에 적재하겠죠

---

페이징 시스템이 안정적으로 작동하려면.. 1. 페이지 교체, 2. 프레임 할당 이 두가지가 해결되어야 한다.

페이지 교체 알고리즘

• 메모리가 가득 찰 때 페이지를 적재할 공간을 비우기 위해 보조기억장치로 보낼 페이지를 고르는 알고리즘
• 페이지를 교체하고 난 뒤 발생하는 페이지 폴트가 다른 경우보다 적어야 좋은 알고리즘!
• 그러기 위해서 페이지 폴트 횟수를 알아야 하는데 이는 페이지 참조열(page reference string)을 통해 알 수 있다.
• 페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열이다.
• 연속된 페이지에 접근하는 경우 페이지 교체가 일어나지 않으니 고려하지 않는 것!

FIFO 페이지 교체 알고리즘

• First-In First-Out Page Replacement Algorithm
• 메모리에 가장 먼저 적재된 페이지먼저 교체하는 알고리즘이다.
• 간단하지만, 프로그램 실행 내내 사용될 페이지를 교체해 버려 페이지 폴트가 많이 발생할 우려가 있다.

2차 기회 페이지 교체 알고리즘(second change page replacement algorithm)

• FIFO 페이지 교체 알고리즘을 개선한 기법이다.
• 가장 먼저 적재된 페이지를 교체하되, 만약 해당 페이지의 참조 비트가 1인 경우 참조 비트를 0으로 만들고 적재 시간을 현재시간으로 재설정한다.
• 즉, 오래되었지만 사용된 적이 있는 페이지는 기회를 한번 더 주는 것이다.

최적 페이지 교체 알고리즘

• 최적 페이지 교체 알고리즘(optimal page replacement algorithm)은 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다.
• 하지만 당연하게도 앞으로의 사용빈도가 가장 낮을 페이지를 예측하는 것은 불가능에 가깝다.
• 그래서 주로 다른 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다.
• 최적 페이지 교체 알고리즘으로 교체했을 때의 페이지 폴트 횟수를 최적으로 보고 비교한다.

LRU 페이지 교체 알고리즘

• LRU 페이지 교체 알고리즘(LRU, Least Recently Used Page Replacement Algorithm)은 지금까지의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다.
• 오래 사용되지 않은 페이지는 앞으로도 오래 사용되지 않을 것이라는 가정이 기반이 된 기법이다.

스래싱(thrashing)과 프레임 할당

• 페이지 폴트가 자주 발생하는 이유에는 비효율적인 페이지 교체 알고리즘 뿐 아니라 비효율적인 프레임 할당도 있다.
• 프레임이 부족하면 페이지가 적재될 공간이 부족하여 페이지 폴트가 자주 발생하게 되며,
• 페이징 교체에 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱 이라고 한다.
• 보통 메모리에 올라와 있는 프로세스의 수에 비례하여 CPU 이용률은 증가하고, 동시 실행되는 프로세스의 수를 멀티프로그래밍의 정도(degree of multiprogramming)라고 한다.
• 하지만 멀티프로그래밍의 정도가 어느 수치를 넘어서면 오히려 CPU 이용률이 감소하는데,
• 이는 각 프로세스들이 사용 가능한 프레임 수가 적어지며 페이지 폴트가 빈번히 발생함으로써 생기는 성능 저하다.
• 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않으면 스래싱이 발생한다.

정적 할당 방식

• 프로세스의 크기와 물리 메모리의 크기를 고려한 방식
  • 균등 할당(equal allocation)
    • 모든 프로세스에 균등하게 프레임을 제공하는 방식
    • 프로세스의 크기에 관계없이 동일한 프레임 개수 할당은 비효율적이다.
  • 비례 할당(proportional allocation)
    • 프로세스의 크기에 비례하여 프레임을 제공하는 방식
    • 프로세스의 크기가 커도 막상 많은 프레임을 필요로 하지 않는 경우가 있다.

동적 할당 방식

• 프로세스의 실행을 보고 할당할 프레임 수를 결정하는 방식
  • 작업 집합 모델(working set model)
    • 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합(working set) 이라고 한다.
    • 이 크기만큼의 프레임 수를 할당한다.
  • 페이지 폴트 빈도(PFF, Page-Fault Frequency)
    • 페이지 폴트율과 할당된 프레임 수는 반비례하는 관계를 보인다.
    • 적당한 페이지 폴트율의 범위를 설정(상한선, 하한선이 있겠죠)하고, 그 범위 내의 프레임 수를 할당하는 방식이다.

정리

• 스와핑은 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법
• 최초 적합 방식은 최초로 발견한 적재 간능한 빈 공간에 프로세스를 배치하는 방식
• 최적 적합 방식은 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식
• 최악 적합 방식은 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식
• 외부 단편화는 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
• 페이징은 물리 주소공간을 프레임 단위로 자르고 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.
• 페이지 테이블을 통해 페이지가 적재된 프레임을 찾을 수 있다.
• PTBR은 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
• TLB는 페이지 테이블의 캐시 메모리 역할을 수행하기 위해 페이지 테이블의 일부를 저장한다.
• 요구 페이징은 페이지가 필요할 때에만 메모리에 적재하는 기법
• 페이지 교체 알고리즘에는 FIFO, 최적, LRU 페이지 교체 알고리즘 등이 있다.
• 스래싱이란 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제
• 프레임 할당 방식에는 균등 할당과 비례 할당, 작업 집합 모델 기반과 페이지 폴트율 기반 프레임 할당 방식이 있다.