Computer Structure & OS(14) - 가상 메모리

1) 연속 메모리 할당

    1-1) 스와핑

    1-2) 메모리 할당

    1-3) 외부 단편화

2) 페이징을 통한 가상 메모리 관리

    2-1) 페이징이란

    2-2) 페이지 테이블

    2-3) 페이징에서의 주소 변환

    2-4) 페이지 테이블 엔트리

3) 페이지 교체와 프레임 할당

    3-1) 요구 페이징

    3-2) 페이지 교체 알고리즘

    3-3) 스래싱과 프레임 할당

 

 

 

 

 

 

 

1) 연속 메모리 할당

1-1) 스와핑

• 연속 메모리 할당 방식 : 프로세스에 연속적인 메모리 공간을 할당하는 방식
• 스와핑(swapping) : 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법
  • 스왑 영역(swap space) : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
  • 스왑 아웃(swap-out) : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
  • 스왑 인(swap-in) : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것
• 스왑 아웃되었던 프로세스가 다시 스왑 인될 때는 스왑 아웃되기 전의 물리 주소와는 다른 주소에 적재될 수 있음
• 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있음
• 유닉스와 리눅스, macOS에서는 free, top 명령어 등을 통해 스왑 영역의 크기를 확인할 수 있으며, 스왑 영역의 크기와 사용 여부는 사용자가 임의로 설정할 수 있음

 

1-2) 메모리 할당

• 프로세스는 메모리 내의 빈 공간에 적재되어야 함
• 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식
  • 최초 적합(first fit) : 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식(최초 적합 방식은 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식이므로 검색을 최소화할 수 있고 결과적으로 빠른 할당이 가능함)
  • 최적 적합(best fit) : 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식
  • 최악 적합(worst fit) : 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식

 

1-3) 외부 단편화

• 외부 단편화(external fragmentation) : 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상을 의미함
• 외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축(compaction)하는 방법이 있음
  • 압축 : 메모리 조각 모음이라고도 부르며, 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식으로 메모리 내에 저장된 프로세스를 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법임
  • 압축 방식의 단점
    • 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 함
    • 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기함
    • 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어려움
• 외부 단편화를 해결하기 위해 또 다른 해결방법이 등장했는데 이것이 오늘날까지도 사용되는 가상 메모리 기법, 그 중에서도 페이징 기법임

 

 

2) 페이징을 통한 가상 메모리 관리

2-1) 페이징이란

• 가상 메모리 관리 기법에는 크게 페이징과 세그멘테이션이 있지만, 우리는 현대 대부분의 운영체제가 사용하는 페이징 기법에 초점을 맞출 예정
• 연속 메모리 할당 방식에서 외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문임
• 만일 메모리와 프로세스를 일정한 단위로 자르고, 이를 메모리에 불연속적으로도 할당할 수만 있다면 외부 단편화는 발생하지 않음
• 페이징(paging) : 메모리의 물리 주소 공간을 프레임(frame) 단위로 자르고, 프로세스의 논리 주소 공간을 페이지(page) 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법임
• 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃되고, 실행에 필요한 페이지들은 메모리로 스왑 인되는 것임(페이징 시스템에서의 스왑 아웃은 페이지 아웃(page out), 스왑 인은 페이지 인(page in)이라고 부르기도 함)
• 즉, 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 같음(프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있음)

 

2-2) 페이지 테이블

• 페이지 테이블(page table) : 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표로, 페이지 테이블의 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있음
• 내부 단편화(internal fragmentation) : 하나의 페이지 크기보다 작은 크기로 발생함
  • 그렇기에 하나의 페이지 크기가 작다면 발생하는 내부 단편화의 크기는 작아질 것으로 기대할 수 있음
  • 하지만 하나의 페이지 크기를 너무 작게 설정하면 그만큼 페이지 테이블의 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비됨
  • 따라서 내부 단편화를 적당히 방지하면서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지의 크기를 조정하는 것이 중요함
• 프로세스마다 각자의 프로세스 테이블을 가지고 있고, 각 프로세스의 페이지 테이블은 메모리에 적재되어 있음
• CPU 내의 페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있음
• 각 프로세스들의 페이지 테이블 정보들은 각 프로세스의 PCB에 기록되며, 프로세스의 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경됨
• 단, 페이지 테이블을 메모리에 두면 문제가 있는데 바로 메모리 접근 시간이 두 배로 늘어난다는 점임(메모리에 있는 페이지 테이블을 보기 위해 한 번, 그렇게 알게 된 프레임에 접근하기 위해 한 번, 이렇게 총 두 번의 메모리 접근이 필요하기 때문임)
• 위의 문제를 해결하기 위해 CPU 곁에(일반적으로 MMU 내에) TLB(Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둠
• TLB는 페이지 테이블의 캐시 메모리 역할을 수행하기 때문에 페이지 테이블의 일부 내용을 저장함(이때 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장함)
• TLB 히트(TLB hit) : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우를 의미함
• TLB 미스(TLB miss) : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 없을 경우를 의미함

 

2-3) 페이징에서의 주소 변환

• 하나의 페이지 혹은 프레임은 여려 주소를 포괄하고 있는데 특정 주소에 접근하려면 아래와 같은 두 가지 정보가 필요함
  • 어떤 페이지 혹은 프레임에 접근하고 싶은지
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
• 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호(page number)와 변위(offset)로 이루어져 있음
  • 페이지 번호 : 말 그대로 접근하고자 하는 페이지 번호(페이지 테이블에서 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되었는지를 알 수 있음)
  • 변위 : 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보

 

2-4) 페이지 테이블 엔트리

• 페이지 테이블 엔트리(PTE; Page Table Entry) : 페이지 테이블의 각 엔트리, 다시 말해 페이지 테이블의 각각의 행들을 의미함
• 유효 비트(valid bit) : 해당 페이지가 메모리에 적재되어 있는지 여부를 알려주는 비트로, 페이지가 메모리에 적재되어 있지 않으면 페이지 폴트가 발생함
• 보호 비트(protection bit) : 페이지에 접근할 권한(r: 읽기, w: 쓰기, x: 실행)을 제한하여 페이지를 보호하는 비트
• 참조 비트(reference bit) : CPU가 해당 페이지에 접근한 적이 있는지 여부를 나타내는 비트
• 수정 비트(modified bit) : 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려주는 비트로, 더티 비트(dirty bit)라고도 부름

 

 

3) 페이지 교체와 프레임 할당

3-1) 요구 페이징

• 요구 페이징(demand paging) : 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고, 필요한 페이지만을 메모리에 적재하는 기법(즉, 페이지가 필요할 때에만 메모리에 적재하는 기법을 뜻함)
• 요구 페이징의 기본적인 양상
  • CPU가 특정 페이지에 접근하는 명령어를 실행함
  • 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근함
  • 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생함
  • 페이지 폴트 처리 루틴은 해당 페이지를 메모리에 적재하고 유효 비트를 1로 설정함
  • 다시 첫 번째 과정을 수행함
• 요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 페이지 교체와 프레임 할당을 해결해야 함
• 요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득차게 되는데 이때는 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 함

 

3-2) 페이지 교체 알고리즘

• 페이지 교체 알고리즘 : 메모리에 적재된 많고 많은 페이지 중 어떤 페이지를 내보내는 것이 최선인가를 결정하는 방법
• 일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 페이지 교체 알고리즘으로 평가함(이는 페이지 폴트가 일어날 시 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문임)
• 페이지 참조열(page reference string) : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미함
• 연속된 페이지를 생략하는 이유 : 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문임
• 대표적인 페이지 교체 알고리즘
  • FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm) : 적재된 페이지 순서대로 교체하는 알고리즘
  • 최적 페이지 교체 알고리즘(optimal page replacement algorithm) : 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
  • LRU 페이지 교체 알고리즘(LRU; Least Recently Used Page Replacement Algorithm) : 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘

 

3-3) 스래싱과 프레임 할당

• 스래싱(thrashing) : 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제(즉, 스래싱이란 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제를 뜻함)
• 멀티프로그래밍의 정도(degree of multiprogramming) : 메모리에서 동시 실행되는 프로세스의 수
• 멀티프로그래밍의 정도가 높다면 현재 메모리에는 많은 프로세스가 동시에 실행 중이고, 낮다면 현재 메모리에는 적은 프로세스가 동시에 실행 중이라고 이해하면 됨
• 스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문임
• 그렇기에 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 함
• 프레임 할당 방식
  • 균등 할당(equal allocation) : 모든 프로세스에 동일한 프레임을 배분하는 방식
  • 비례 할당(proportional allocation) : 프로세스 크기에 따라 프레임을 배분하는 방식
  • 균등 할당과 비례 할당 방식은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고려한 방식이라는 점에서 정적 할당 방식이라고도 함
  • 작업 집합 모델(working set model) 기반 프레임 할당 : 작업 집합(실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합)의 크기만큼만 프레임을 할당하는 방식
  • 페이지 폴트 빈도(PFF; Page-Fault Frequency)를 기반으로 한 프레임 할당(페이지 폴트율 기반 프레임 할당) : 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식
  • 작업 집합 모델 기반 프레임 할당과 페이지 폴트 빈도를 기반으로 한 프레임 할당 방식은 프로세스의 실행을 보고 할당할 프레임 수를 결정한다는 점에서 동적 할당 방식이라고도 함