연속 메모리 할당
프로세스에 연속적인 메모리 공간을 할당하는 방식을 연속 메모리 할당 방식이라고 한다.
스와핑
스와핑(swapping): 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식스왑 영역(swap space): 프로세스들이 쫓겨나는 보조기억장치의 일부 영역스왑 아웃(swap out): 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것스왑 인(swap in): 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것
스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 강간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있다.
메모리 할당
비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식에는 대표적으로 3가지 방식이 있다.
최초 적합
최초 적합(first fit)- 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
- 프로세스가 적재될 수 있는 공간을 발견하면 즉시 메모리를 할당하는 방식
- 검색을 최소화할 수 있고 결과적으로 빠른 할당이 가능함
최적 적합(best fit)- 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식
최악 적합(worst fit)- 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식
외부 단편화
외부 단편화(external fragmentation)- 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
- 프로세스들이 메모리에 연속적으로 할당되는 환경에서 프로세스들이 실행되고 종료되기를 반복함
- 메모리 사이 사이에 빈 공간들이 생김
- 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래 => 메모리 낭비
- 연속 메모리 할당은
외부 단편화문제를 내포하고 있어 메모리를 효율적으로 사용하는 방법은 아니다.
실제로는 메모리 용량이 크고 적재되는 프로세스도 많기 때문에 외부 단편화로 인해 낭비되는 공간은 더욱 크다. 이 때문에 외부 단편화 문제는 반드시 해결해야할 문제다.
압축(compaction)- 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
- 메모리 내에 저장된 프로세스들을 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 메모리 내에 저장된 프로세스를 적당히 재배치시켜 흩어져 있는 작은 빈 공간들을 하나의 큰 공간으로 만드는 방법
- 외부 단편화를 해결할 수 있는 대표적인 방안
- 메모리 조각 모음이라고도 함
- 단점
- 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 함
- 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기함
- 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어려움
- 또 다른 해결 방안 : 가상 메모리 기법(페이징 기법)
페이징을 통한 가상 메모리 관리
가상 메모리(virtual memory)- 실행하고자 하는 프로그램을 일부만 멤뢰에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
- 크게 페이징과 세그먼테이션이 있음
- 현대 대부분의 운영체제는 페이징 기법을 사용함
페이징이란
외부 단편화가 생긴 근본적인 이유 -> 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문
만약 메모리와 프로세스를 일정한 단위로 자르고, 이를 메모리에 불연속적으로도 할당할 수만 있다면 외부 단편화는 발생하지 않는다.
페이징(paging)- 메모리의 물리 주소 공간을
프레임단위로 자르고, 프로세스의 논리 주소 공간을페이지단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법 페이지(page): 프로세스의 논리 주소 공간을 일정한 단위로 자른 것프레임(frame): 메모리 물리 주소 공간을 페이지와 동일한 크기의 일정한 단위로 자른 것- 페이징 시스템에서의 스왑 인/스왑 아웃은 페이지 아웃(page out) / 페이지 인(page in) 이라고 부른다.
- 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다.
- 메모리의 물리 주소 공간을
페이지 테이블
프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 '다음에 실행할 명령어 위치'를 찾기가 어려워진다. 이를 해결하기 위해 페이지 테이블을 사용한다.
페이지 테이블(page table)
- 현재 어떤 페이지가 어떤 프레임에 할당되었는지 알려줌
- 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표
- 프로세스마다 각자의 프로세스 테이블이 있다.
- 물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적일 수 있다.
- 프로세스들이 메모리에 분서되어 저장되어 있더라도 CPU는 논리 주소를 그저 순차적으로 실행하면 된다.
내부 단편화(internal fragmentation)
- 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아니다. -> 모든 프로세스 크기가 페이지의 배수는 아니다.
- 내부 단편화는 하나의 페이지보다 작은 크기로 발생한다.
- 하나의 페이지 크기를 너무 작게 설정하면 그만큼 페이지 테이블의 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비된다.
- 내부 단편화를 적당히 방지하면서, 너무 크지 않은 페이지 테이블이 만들어지도록 페이지의 크기를 조정하는 것이 중요하다.
페이지 테이블 레지스터(PTBR; Page Table Base Register)
- 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있음
- 페이지 테이블 정보들은 각 프로세스의 PCB에 기록된다. 프로세스의 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경된다.
TLB(Translation Lookaside Buffer)
- 페이지 테이블의 캐시 메모리
- 페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배로 늘어나기 때문에 사용
- 페이지 테이블의 캐시이므로 페이지 테이블의 일부 내용을 저장
- 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장함
TLB hit: CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우TLB miss: 페이지 번호가 TLB에 없을 경우. 이 경우 메모리 내의 페이지 테이블에 접근해야 함
페이징에서의 주소 변환
페이지 또는 프레임의 특정 주소에 접근하려면 아래와 같은 두 가지 정보가 필요하다.
페이지 번호(page number)- 접근하고자 하는 페이지 번호
변위(offset)- 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보
페이지 테이블 엔트리
페이지 테이블 엔트리(PTE; Page Table Entry)- 페이지 테이블의 각각의 행들
- 페이지 번호와 프레임 번호 외에도 다른 중요한 정보들이 있음
유효 비트(valid bit)
- 현재 해당 페이지에 접근 가능한지 여부를 알려줌
- 프레임 번호 다음으로 중요한 정보
- 현재 페이지가 메모리에 적재되어 있는지 아니면 보조기억장치에 있는지를 알려주는 비트
페이지 폴트(page fault)- 유효 비트가 0인, 메모리에 적재되어 있지 않은 페이지로 접근하려고 할 때 발생하는 예외(Exception)
- 하드웨어 인터럽트를 처리하는 과정과 유사함
보호 비트(protection bit)
- 페이지 보호 기능을 위해 존재하는 비트
- 읽고 쓰기가 모두 가능한 페이지인지, 읽기만 가능한 페이지인지를 나타냄
- 프로세스에서 코드 영역 등은 읽기 전용 영역임
- 읽기, 쓰기, 실행하기 권한의 조합을 나타낼 수 있음
- 읽기(Read) r
- 쓰기(Write) w
- 실행(eXecute) x
참조 비트(reference bit)
- CPU가 이 페이지에 접근한 적이 있는지 여부
- 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1
- 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지는 0
수정 비트(modified bit)
- 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부
더티 비트(dirty bit)라고도 함- 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야하는지, 할 필요가 없는지를 판단하기 위해 존재
- 한 번도 수정된 적이 없는 페이지가 스왑 아웃될 경우, 추가 작업 없이 새로 적재된 페이지로 덮어쓰기만 하면 됨
- 그렇지 않은 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 함
페이지 테이블에 무엇이 저장되는지만 알아도 실제로 CPU가 메모리에 어떻게 접근하며 가상 메모리를 어떻게 다루는지 알 수 있다.
쓰기 시 복사(copy on write)
페이징은 외부 단편화 문제 해결 외에도 프로세스 간에 페이지를 공유할 수 있다는 장점이 있다.
유닉스/리눅스 계열이 OS에서 fork 시스템 호출을 하면 부모 프로세스의 복사본이 자식 프로세스로서 만들어진다. 새롭게 생성된 자식 프로세스의 코드 및 데이터 영역은 부모 프로세스가 적재된 메모리 공간과는 전혀 다른 메모리 공간에 생성된다.
=> 이러한 복사 작업은 프로세스 생성 시간을 늦출 뿐만 아니라 불필요한 메모리 낭비를 야기한다.
쓰기 시 복사에서는 자식 프로세스로 하여금 부모 프로세스와 동일한 프레임을 가리킨다. 이렇게 하면 굳이 부모 프로세스의 메모리 공간을 복사하지 않고도 동일한 코드 및 데이터 영역을 가리킬 수 있다. 만약 부모/자식 프로세스가 메모리에 어떠한 데이터도 쓰지 않고 읽기 작업만 이어 나간다면 이 상태가 지속된다.
부모/자식 프로세스 둘 중 하나가 페이지에 쓰기 작업을 하면 그 순간 해당 페이지가 별도의 공간으로 복제된다. 이것이 쓰기 시 복사이며, 이를 통해 프로세스 생성 시간을 줄이는 것은 물론이고 메모리 공간 절약도 가능하다.
계층적 페이징(hierarchical paging)
- 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 수 있는 방법
- 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
다단계 페이지 테이블(multilevel page table)이라고도 함- 페이지 테이블을 여러 개의 페이지로 쪼개고, 이 페이지들을 가리키는 페이지 테이블(Outer 페이지 테이블)을 두는 방식
페이지 테이블의 계층은 세 개, 네 개, 그 이상의 계층으로도 구성될 수 있다. 그러나 계층이 늘어날수록 페이지 폴트가 발생했을 경우 메모리 참조 횟수가 많아지므로 계층이 많다고 해서 반드시 좋다고 볼 수는 없다.
페이지 교체와 프레임 할당
요구 페이징
요구 페이징(demand paging)- 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
- 실행에 요구되는 페이지만 적재함
순수 요구 페이징(pure demand paging)- 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 하는 기법
- 프로세스의 첫 명령어를 실행하는 순간부터 페이지 볼트가 계속 발생함
- 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어짐
요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당 문제가 해결되어야 한다.
페이지 교체 알고리즘
페이지 교체 알고리즘(Page Replacement Algorithm)- 쫓아낼 페이지를 결정하는 방법
- 메모리에 적재된 많은 페이지 중 어떤 페이지를 내보낼지 결정하는 알고리즘
- 페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 알고리즘으로 평가함
페이지 참조열(page reference string)- CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
- 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않음
- 이 때문에 연속된 페이지를 생략함
- 즉, 페이지 폴트가 일어나지 않을 연속된 페이지에 대한 참조는 고려하지 않음
페이지 폴트 횟수를 알 수 있음
FIFO 페이지 교체 알고리즘
First-In First-Out Page Replacement Algorithm- 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
- 아이디어와 구현이 간단함
- 자주 참조되는 페이지가 먼저 적재되었다는 이유만으로 내쫓길 수 있음
2차 기회 페이지 교체 알고리즘
Second Chance Page Replacement Algorithm- FIFO 페이지 교체 알고리즘의 부작용을 어느 정도 개선한 변형 버전
- 방식
- 기본적으로 FIFO 페이지 교체 알고리즘처럼 메모리에서 가장 오래 머물렀던 페이지를 내쫓을 대상으로 선정함
- 이 때 페이지의 참조 비트가 1일 경우, 당장 내쫓지 않고 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정함
- 참조 비트가 1이라는 것은 CPU가 접근한 적이 있다는 의미임 -> CPU가 다시 접근할 가능성이 있으므로 한 번의 기회를 더 주는 것
최적 페이지 교체 알고리즘
Optimal Page Replacement Algorithm- CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
- 아이디어
- 메모리에 오랫동안 남아야 할 페이지는 자주 사용될 페이지이고, 반대로 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지임
- 즉, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이 가장 합리적임
- 이론상 가장 낮은 페이지 폴트율을 보장하는 알고리즘이지만 실제 구현이 어려움
- 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용됨
- 최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 페이지 폴트의 하한선으로 설정
- 이 알고리즘에 비해 얼만큼 페이지 폴트 횟수가 발생하느냐를 통해 페이지 교체 알고리즘을 평가하기 위해 사용함
LRU 페이지 교체 알고리즘
LRU; Least Recently Used Page Replacement Algorithm- '최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것'이라는 아이디어를 토대로 만들어짐
스레싱
- 페이지 폴트가 자주 발생하는 이유
- 나쁜 페이지 교체 알고리즘
- 프레임 수가 적음
- 이것이 페이지 교체 알고리즘보다 더 근본적인 이유임
- 프로세스가 사용할 수 있는 프레임 수가 많으면 일반적으로 페이지 폴트 빈도수는 감소함. 반대의 경우도 성립
스래싱(thrashing)- 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
- 페이지 교체에 너무 많은 시간을 쏟으면 성능에도 큰 악영향이 미침
- 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문에 발생
멀티프로그래밍의 정도(degree of multiprogramming)- 메모리에서 동시 실행되는 프로세스의 수
- 동시에 실행되는 프로세스 수를 필요 이상으로 늘리면
- 페이지 폴트가 지나치게 빈번히 발생
- CPU 이용률이 떨어져 전체적인 성능이 저하됨
- CPU 성능이 좋더라도 물리 메모리가 너무 작다면 전체 컴퓨터의 성능이 안 좋아지는 이유임
프레임 할당 방식
스레싱과 같은 문제를 방지하기 위해 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고, 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.
정적 할당 방식
- 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고려함
균등 할당(equal allocation)- 모든 프로세스에 균등하게 프레임을 제공하는 방식
- 권장되는 방법은 아님
비례 할당(proportional allocation)- 프로세스의 크기가 크면 프레임을 많이 할당하고, 프로세스 크기가 작으면 프레임을 적게 나눠주는 방식
- 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 아는 경우가 많음
동적 할당 방식
- 프로세스의 실행을 보고 할당할 프레임 수를 결정함
작업 집합 모델(working set model) 기반 프레임 할당- '프로세스가 일정 기간 동안 참조한 페이지 집합'을 기억하여 빈번한 페이지 교체를 방지함
- CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당
참조 지역성의 원리참고
작업 집합(working set): 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
페이지 폴트 빈도(PFF; Page-Fault Frequency)- 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식
- 아이디어
- 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
- 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
Q&A
실제 운영체제에서는 어떻게 교착 상태를 해결할까? (Ch13-2)
타조 알고리즘
대부분의 운영체제는 교착 상태 발생 시 시스템에 문제가 없는 척을 한다. 교착 상태는 매우 드물게 발생하는 경우이기 때문에, 이에 대한 투자는 교착 상태의 방지 또는 감지 등과 관련된 지속적인 오버헤드 및 시스템 성능 저하로 이어질 수 있다.
만약 문제가 발생했다면 참을성 없는 사용자가 직접 프로세스를 종료하거나 컴퓨터를 재시작한다.
Windows의 경우
Windows에는 런타임 시 교착 상태를 확인하도록 특별히 설계된 기본 제공 기능이 없다. (윈도우 드라이버에서 교착 상태가 일반적으로 발생하므로 드라이버 개발자가 교착 상태 버그를 진단하는데 도움이 되도록 설계된 도구가 있지만, 여전히 최종 사용자 단의 컴퓨터에서 실행되는 것은 아니다.)
Windows에서는 어떤 프로세스들이 교착 상태에 빠졌더라도, 그것이 일시적인 것인지 영구적인 것인지 알 수 있는 방법이 없다.
그리고 일반적인 Windows 소프트웨어에서는 교착 상태가 매우 드물기 때문에 Windows가 정교한 전략으로 교착 상태를 처리하는 것은 "프로그램 중 하나가 자원을 포기하거나 사용자가 와서 작업을 종료할 때까지 두 스레드를 모두 교착 상태로 두는 것"보다 비생산적이다. 이런 경우에는 그냥 컴퓨터를 다시 시작한다. (블루스크린)
즉, 프로그래머의 실수로 프로그램이 교착 상태에 빠지더라도, 운영체제는 이를 직접 해결하지 않고 최종 사용자에게 판단을 맡긴다.
참고
