Physical Memory
앞서, 우리는 프로그램을 메모리에 적재할 때 메모리 내에 프로세스들이 연속적으로 배치되는 연속 메모리 할당 상황을 가정하였다.
스와핑
메모리에 적재된 프로세스들 중 입추력 작업으로 대기가 된 프로세스라던지, 오래동안 사용되지 않는 프로세스들을 잠시 보조기억장치의 영역으로 쫒아내고, 생긴 공간에 다른 프로세스를 적재하여 실행하는 방식을 스와핑이라고 한다.
이때 프로세스가 쫓겨난 보조기억장치의 일부 영역을 스왑영역, 실행되지 않는 프로세스가 스왑영역으로 쫓겨자는 것을 스왑아웃,스왑영역에 있던 프로세스가 다시 메모리로 돌아오는 것을 스왑인이라고 한다.
위 그림처럼 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있다.
메모리 공간에 프로세스를 할당하는 방식
-
최초 적합
최초 적합은 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식이다.
최초 적합 방식은 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식이므로 검색을 최소화하고 결과적으로 빠른할당이 가능하다. -
최적 적합
최적 적합은 운영체제가 빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식이다. -
최악 적합
최적 적합은 운영체제가 빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식이다.
외부 단편화
앞까지는 메모리 내에 프로세스들이 연속적으로 배치되는 연속 메모리 할당 상황을 가정하였다. 사실 이는 메모리를 효율적으로 사용하는 방법이 아니다. 왜냐면 연속 메모리 할당은 외부단편화 문제를 내포하기 때문이다.
프로세스들이 메모리에 연속적으로 할당되는 환경에서 프로세스들이 실행되고 종료하기를 반복하며 메모리 사이사이에 빈 공간들이 생긴다. 이 빈 공간들은 연속적이지 않고 빈 공간보다 큰 프로세스들은 적재하지 못하게 되면서 메모리 낭비로 이어지는 현상을 외부 단편화라고 한다.
Virtual Memory
위와 같이 프로세스를 메모리에 연속적으로 할당해야 한다면 메모리 보다 큰 프로그램은 실행할 수 없게되고 위에서 말한 외부 단편화 문제가 발생한다. 때문에 가상메모리라는 것을 사용한다.
가상 메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물미 메모리 크기보다 더 큰 프로세스를 실행할 수 있게하는 기술이다. 가상 메모리는은 페이징 기법을 통해 관리된다.
페이징 기법
연속 메모리 할당 방식에서 외부 단편화가 발생한 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문이다. 만일 프로세스를 일정한 단위로 자르고, 이를 메모리에 불연속적으로 할당할 수 있다면 외부 단편화는 발생하지 않는다. 이렇게 프로세스를 페이지라는 일정한 단위로 자르고, 메모리를 똑같은 크기인 프레임이라는 단위로 자른뒤 페이지를 프레임에 할당하는 것이 페이징 기법이다.
페이징 기법에서도 위에서 언급한 스와핑을 사용할 수 있다. 페이징 기법에서는 프로세스 전체가 스왑 인/아웃되지않고 페이지 단위로 인/아웃된다. 이걸 페이지 아웃/ 페이지 인이라한다.
페이지 테이블
위의 페이지 기법에서 페이지 단위로 잘라서 메모리에 불연속적으로 배치하면 cpu 입장에서는 이를 순차적으로 실행할 수 없다. cpu가 하나의 프로세스를 이루는 페이지가 어떤 프레임에 적재되어있는지 모두 알수는 없기 때문이다.
이를 해결하기 위해 프로세스가 비록 물리 주소에 불연속적으로 배치되더라도, 논리 주소에는 연속적으로 배치되도록하는 페이지 테이블을 이용한다. 페이지 테이블은 페이지 번호와 프레임 번호를 짝지어 주어 cpu로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게한다.
이렇게 하면 메모리에서는 프로세스들이 분산되어 저장되어 있더라도 cpu 입장에서 바라보는 논리 주소는 연속적으로 보이게 할 수 있다. 프로세스 마다 각자의 페이지 테이블을 가지고 있고, 각 프로세스의 페이지 테이블은 메모리에 적재되어 있다. 그리고 cpu내의 페이지 테이블 베이스 레지스터에 각 프로세스들의 페이지 테이블이 적재된 주소를 가리킨다.
TLB
cpu는 페이지 테이블 베이스 레지스터에 적혀있는 페이지 테이블이 적재된 주소를 찾아가 페이지 테이블을 보고, 그렇게 알게된 프레임에 접근한다. 총 두번의 메모리 접근이 필요한 것이다. 이와 같은 시간 낭비를 해결하기 위해 cpu곁에 TLB라는 페이지 테이블의 캐시 메모리를 둔다. 자주 사용하는 프레임의 주소를 페이지 주소와 짝지어 저장하는 것이다.
cpu가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB 히트라고 하고 이때는 메모리에 한번만 접근하면 된다. 페이지 번호가 TLB에 없을 경우 TLB 미스라고 하고 프레임 주소를 알기 위해 메모리 내의 페이지 테이블에 접근해야 한다.
내부 단편화
페이징은 외부 단편화 문제를 해결할 수 있지만, 내부 단편화 문제가 생길 수 있다. 페이징 기법은 프로세스를 일정한 크기 단위로 자른다 하였는데 모든 프로세스가 페이지 크기의 배수가 아니므로 정확히 잘리는 것은 아니다.이 경우 자르고 남는 부분이 생길 수 있다 이러한 메모리 낭비를 내부 단편화라고 한다.
페이징에서의 주소 변환
페이징 기법에서 특정 주소에 접근하려면 어떤 페이지에 접근할 것인지와 접근하려는 주소가 그 페이지로부터 얼마나 떨어져 있는지 두가지 정보가 필요하다.
따라서 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 되어있다.
변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는기 알기 위한 정보이다. 즉, 논리주소 <페이지번호, 변위>는 페이지 테이블을 통해 <프레임번호, 변위>로 변환된다.
페이지 테이블 엔트리
페이지 테이블에는 사실 페이지 번호, 프레임 번호만 있는 것이 아니라 다른 중요한 정보들이 있다.
- 유효비트
유효비트는 현재 해당 페이지에 접근 가능한지 여부를 알려준다. 위에서 프로세스는 스와핑을 통해 보조기억장치와 메모리를 왔다갔다 한다고 하였다. 프로세스는 사실 대부분 보조기억장치(스왑 영역)에 있는 경우가 많다. 유효 비트는 현재 페이지가 메모리에 적재되어 있는지 스왑영역에 있는지 알려준다. 만일 cpu가 스왑영역에 있는 페이지로 접근하려 하면 페이지 폴트가 발생하고, 해당 페이지를 메모리로 가져온뒤 접근한다.
- 보호비트
보호비트를 통해 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 혹은 읽기만 가능한 페이지 인지 나타낼 수 있다.
- 참조비트
참조비트는 cpu가 페이지에 접근한 적이 있는지 여부를 나타낸다.
- 수정비트
수정비트는 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 나타낸다. 수정 비트는 페이지가 메모리에서 사라질때 보조기억장치에 쓰기 작업을 해야하는지, 할 필요가 없는지 판단하기 위해 존재하
쓰기 시 복사
프로세스를 fork하여 동일한 두 개가 복제되면 모든 자원이 복제되어 메모리에 적재된다 하였다. 부모 프로세스가 자식프로세스를 생성하면 새롭게 생성된 자식 프로세스의 코드 및 데이터 영역은 부모 프로세스의 메모리 영역과 다른 새로운 공간에 할당된다.
이것은 불필요한 메모리 낭비를 야기한다. 반면 페이징 기법을 사용하면 부모 프로세스와 자식프로세스가 동일한 프레임을 가리킨다. 따라서 부모 프로세스의 메모리 공간을 복사하지 않고도 동일한 코드 및 데이터 영역을 가리킬 수 있다.
하지만 프로세스 간에는 자원을 공유하지 않으므로 둘 중 하나의 프로세스에서 쓰기 작업을 하면 페이지가 별도의 공간으로 복제된다.
계층적 페이징
프로세스의 크기가 커지면 프로세스의 테이블 크기도 커지기 때문에 모든 페이지의 테이블 엔트리를 메모리에 두
는 것은 메모리 낭비이다. 따라서 페이지 테이블을 다시 페이징하여 여러단계의 페이지를 두는 방식을 계층적 페이징이라고 한다.
페이지 테이블 관리하기
가상 메모리를 통해 물리 메모리보다 큰 프로세스도 실행할 수 있다고 하지만, 그럼에도 물리 메모리의 크기는 한정되어있다. 운영체제는 이를 어떻게 관리하고 해결할까?
요구 페이징
프로세스를 메모리에 적재할때 처음부터 모든 페이지를 적재하지 않고, 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징이라고 한다. 그렇지만 요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득 차게 된다. 이때는 당장 실행에 필요하지 않는 메모리에 적재된 페이지를 보조기억장치로 내보내야 한다.
이렇게 쫓아낼 페이지를 결정하는 방법을 페이지 교체 알고리즘이라고 한다. 페이지 폴트가 일어나면 보조 기억장치로부터 필요한 페이지를 가져와야 하기 때문에 페이지 폴트를 가장 적에 일으키는 알고리즘이 좋은 알고리즘으로 평가된다.
페이지 교체 알고리즘의 종류
- FIFO 알고리즘
메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식이다. 오래 있었다고 쫓아 내기엔 프로그램 실행 내내 사용
될 내용을 포함할 수도 있기 때문에 좋은 알고리즘은 아니다.
- 최적 페이지 교체 알고리즘
cpu에 의해 참조 되는 횟수를 고려하는 페이지 교체 알고리즘이다. 사용 빈도가 가장 낮은 페이지를 보조기억
장치로 내쫓는 것이다. 최적 페이지 교체 알고리즘은 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다. 다만 앞으로도 오랫동안 사용되지 않을 페이지를 예측하기는 어렵기 떄문에 실제 구현이 어렵다. 따라서 최적 페이지 교체 알고리즘은 실제 운영체제에서 사용하기 보다는, 다른 페이지 교체 알고리즘의 성능을 평가하기 위한목적으로 사용된다.
- LRU 페이지 교체 알고리즘
LRU페이지 교체 알고리즘은 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 내쫓는다.
스래싱
페이지 폴트는 프로세스가 사용할 수 있는 프레임수가 적을때 더 자주 발생한다. 당연히 프레임이 부족하면 cpu는 페이지 폴트가 자주 발생할 수밖에 없다. 이렇게 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱이라고 한다.
동시에 실행되는 프로세스 수가 어느정도 하면 cpu이용률이 높아지지만, 필요 이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 빈번히 발생하고, 이는 cpu 이용률의 저하를 야기한다. 따라서 운영체제는 프로세스들이 무리없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 수만큼 프레임을 할당해야 한다.
프레임할당
- 균등할당
각 프로세스에 똑같은 개수만큼 프레임을 할당하는 방법이다. 이는 크기가 큰 프로세스와 작은 프로세스가 같은 개수의 프레임을 할당받야하 하므로 비효율적이다.
- 비례할당
크키가 큰 프로세스에겐 많은 프레임을, 크기가 작은 프로세스에겐 적은 프레임을 할당하는 방식이다. 하지만 프로세스의 크기가 작아도 실행해보니 프레임이 많이 필요한 경우가 있기 때문에 이도 비효율적이다.
- 페이지 폴트 빈도 기반 프레임 할당 방식
cpu가 특정시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당한다.프로세스가 일정 시간동안 참조한 페이지의 집합을 참조 집합이라고 한다. 운영체제는 프로세스의 참조 집합의 개수가 10초 당안 20개였다면 20개의 프레임을 할당한다. 그 다음 페이지 폴트율의 상한선과 하한선을 정하고만약 페이지 폴트 비율이 상한선보다 높아지면 너무 적은 프레임을 가지고 있으므로 더 많은 프레임을 할당하고, 페이지 폴트율이 하한선보다 낮아지면 다른 프로세스에게 할당하기 위해 프레임을 회수한다.
