가상 메모리
프로세스가 연속적인 메모리 공간을 할당하는 방식을 연속 메모리 할당 방식이라 하는데 프로세스들을 메모리에 연속적으로 할당할 때 고려해야 할 것과 문제점들이 있다.
스와핑
메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법
프로세스들이 내보내지는 보조기억장치의 일부 영역을 스왑 영역이라고 하고, 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃, 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인이라고 한다.
메모리 할당
프로세스는 메모리 내의 빈 공간에 적재되어야 한다. 이때 메모리 공간에 프로세스를 연속적으로 할당하는 대표적인 세 가지 방식이 있다.
최초 적합(first fit) :
최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
최적 적합(best fit) :
프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식
최악 적합(worst fit) :
프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
외부 단편화(external fragmentation)
프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
프로세스 메모리에 연속적으로 할당하는 방식은 두 가지 문제를 내포하고 있다.
첫 번째로는 외부 단편화가 있고, 다른 하나는 물리 메모리보다 큰 프로세스를 실행할 수 없다는 점이다.
즉, 프로세스를 반드시 메모리에 연속적으로 할당해야 한다면 메모리보다 큰 프로그램은 적재할 수 없다.
가상 메모리(virtual memory)는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술이다.
페이징
연속 메모리 할당 방식에서 외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되어 있기 때문이다. 만일 메모리와 프로세스를 일정한 단위로 자르고 이를 메모리에 불연속적으로 할당할 수만 있으면 외부 단편화는 발생하지 않는다.
즉, 페이징은 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.
페이징에서도 스와핑을 사용할 수 있는데, 페이징을 사용하는 시스템에서는 프로세스 전체가 스왑 아웃/인되는 것이 아닌 페이지 단위로 페이지 아웃/인 이 된다.
즉, 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 같다. 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있게 된다. 이를 통해 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.
페이지 테이블
페이징을 했을 때, 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서는 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 모두 알고 있기가 힘들기 때문에 이를 순차적으로 실행할 수가 없다.
이를 해결하기 위해 페이징 시스템은 프로세스가 물리 주소에 불연속적으로 배치되더라도 논리 주소에서 연속적으로 배치되도록 페이지 테이블을 사용한다.
페이지 테이블의 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있다. 또한, 유효 비트, 보호 비트, 접근 비트, 수정 비트 등이 있다.
PTBR; Page Table Base Register :
프로세스마다 각자의 프로세스 테이블을 가지고 있고 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있다. PTBR은 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
TLB; Translation Lookaside Buffer :
페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배로 늘어나기 때문에 CPU 곁에 TLB라는 페이지 테이블의 캐시 메모리를 둔다. TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장하고 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장한다.
CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 이를 TLB 히트라고 하고 이경우에는 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없다. 그렇기에 메모리 접근을 한 번만 할 수 있게 된다.
하지만 페이지 번호가 TLB에 없을 경우 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근할 수밖에 없는데 이를 TLB 미스 라고 한다.
페이징에서의 주소 변환
하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있기에 특정 주소에 접근하려면 아래와 같은 두 가지 정보가 필요하다.
1. 어떤 페이지 혹은 프레임에 접근하고 싶은지
2. 접근하려는 주소가 그 페이지 또는 프레임으로부터 얼마나 떨어져 있는지
그렇기에 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호(page number)와 변위(offset)로 이루어져 있다.
ex) CPU가 32비트 주소를 내보내면 이 중 N비트는 페이지 번호, 32-N은 변위로 이루어지게 된다.
페이지 번호는 접근하고자 하는 페이지 번호로 페이지 테이블에서 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되었는지를 알 수 있다.
* 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼마큼 떨어져 있는지를 알기 위한 정보이다.
페이지 교체와 프레임 할당
가상 메모리를 통해 작은 물리 메모리보다 큰 프로세스도 실행할 수 있지만, 그럼에도 물리 메모리의 크기는 한정되어 있다. 운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록 기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보낼 수 있어야 하고, 프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 해야 한다.
요구 페이징
프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징이라고 한다.
즉, 페이지가 필요할 때에만 메모리에 적재하는 기법이다.
요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 페이지 할당을 해결해야 한다.
요구 페이징 기법으로 페이지들을 적재하다 보면 언젠간 메모리가 가득 차게 되는데 이때 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 한다.
이때 어떤 페이지를 내보내는지 결정하는 방법이 페이지 교체 알고리즘이다.
페이지 교체 알고리즘
좋은 페이지 교체 알고리즘이란 일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘을 일컫는다. 왜냐하면 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문이다.
페이지 폴트 횟수를 알아야 페이지 교체 알고리즘을 이해할 수 있는데 페이지 폴트 횟수는 페이지 참조열(page regerence string)을 통해 알 수 있다.
페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미한다.
예를 들어 CPU가 아래와 같은 순서로 페이지에 접근했다고 가정했을 때
2 2 2 3 5 5 5 3 3 7
연속된 페이지를 생략한 페이지열 즉, 페이지 참조열
-> 2 3 5 3 7
연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문이다.
대표적인 페이지 교체 알고리즘으로는
1. FIFO 페이지 교체 알고리즘
2. 최적 페이지 교체 알고리즘
3. LRU 페이지 교체 알고리즘
등 이 있다.
스래싱과 프레임 할당
페이지 폴트가 자주 발생하는 이유 중 프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트가 자주 발생할 수 있다. 반대로 프로세스가 사용할 수 있는 프레임 수가 많으면 일반적으로 페이지 폴트 빈도는 감소한다.
프레임이 부족하면 CPU 페이지 폴트가 자주 발생할 수 있고, 그 결과로 CPU의 이용률이 떨어지게 된다.
이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱(thrashing)이라 한다.
이 문제를 해결하기 위해서는 적절한 프레임 할당이 필요하다.
프레임 할당 방식에는 균등 할당과 비례 할당, 작업 적합 모델 기반과 페이지 폴트율 기반 프레임 할당 방식 등이 있다.