non-continuous memory allocation 에는 3가지 시스템이 존재한다.
paging system , segment system , hybrid system
그 중 pagin system 부터 가보자고
Paging system
Paging system 은 프로세스를 같은 크기의 block 단위로 분할하여 메모리에 올리는 것으로
프로세스에서 block 단위로 나눠진 것을 page 라고 하며
실제 메모리는 page 크기 만큼 공간을 준비해두는데 실제 메모리에 준비된 영역을 page frame 이라고 한다.
특징
가장 두드러지는 특징은 block 단위로 나눌 때 프로세스를
논리적 단위로 나누는 것이 아니라 정해진 크기에 따라 나눈다는 것이다.
만약 1000줄의 코드로 이뤄진 프로세스를 10줄 단위로 나눈다고 했을 때
A 함수가 20줄로 이뤄진 코드라면 A 함수의 절반은 다른 block , 또 하나는 다른 block 에 존재하게 되는 것이다.
왜 그따구로 하지 ? 라는 생각이 들었다 처음엔
그런데 이런 특징을 통해 구현이 쉽고 실제 메모리를 관리하기가 쉽다는 장점이 있다.
다만 프로세스를 공유하거나 보호하는데 있어서는 단점이 있는데 이는 추후 설명하도록 한다.
Address mapping
Table : Page Mapping table (PMT)
paging system 에선 address mapping 을 하기 위해선 BMT 처럼 PMT 를 이용한다.
PMT 또한 커널에 프로세스 별로 하나 씩 정의된다.
paging system 에서 가상 메모리 주소는 v = (p,d) 로 정의되는데 p 는 page number 를 의미한다.
PMT 테이블을 살펴보며 v = (p , d) 를 이용해 어떻게 실제 메모리 주소에 접근 할 거 같은지 상상해보자
page number: 프로세스를 나눈page들을 가리키는 식별자 (가상 메모리)residence bit: 해당 페이지가 현재 메모리에 적재 되어 있는가를 나타내는 비트 (0, 1 만 존재)secondary storage address: 해당 페이지가 디스크에 적재되어 있는 주소 , 만약residence bit가0이라면 해당 주소에 접근해 메모리에 적재한다.page frame number: 실제 메모리에 존재하는page frame의 시작 주소
mechanism : Direct mapping
PMT 를 이용해 v = (p , d) 로 정의된 가상 주소를 실제 메모리 주소로 변경하는 방법은 3가지 존재한다.
우선 Direct mapping 방식은 말 그대로 PMT 를 이용해 직접 맵핑하는 것이다.
v = (p,d) 로 정의된 가상 주소를 실제 주소로 맵핑 할 때의 과정은 다음과 같다.
-
우선
p를 확인하고p가 실제 메모리에 올라가있는 주소 , 즉page frame number를 알아내기 위해PMT를 조회해야 한다. -
PMT를 조회하기 위해 커널에 존재하는PMT테이블을 조회한다.
2.1 조회하는 방법은PMT의 시작 주소인b+p * entry size를 이용하면 즉시p에 대한PMT테이블에 접근하는게 가능하다.entry는PMT테이블에서 하나의 페이지에 대한 행의 개수를 의미한다. 여기서는 한 페이지가 한 테이블 당 한줄로 설명 가능하게entrySize는 1이다. -
P'(page frame number) 를 조회하고 (실제 메모리 내 페이지의 시작 주소)d만큼 더해v가상주소를 실제 주소로 변경하는 것이 가능했다.이 때 만약
residence bit가0일 경우엔page frame number가 존재하지 않는다. 메모리에 적재되어있지 않기 때문이다. 이런 경우엔swap device에서 페이지를 메모리에 적재해야 한다.
이러한 경우를page fault라고 한다.
Direct mapping 의 문제점
문제점이 뭐가 있을까 ?
우선 메모리 접근 횟수가 2배라는 문제가 존재한다.
커널에서 PMT 한 번 , main memory 에서 한 번 말이다.
특히나 커널에 저장된 메모리에 접근한다는 것은 system call , context swiching 이 일어나야 하는 오버헤드가 큰 작업이다.
이것은
non continuous allocation방법의 공통된 한계점이다.
이 문제는 하드웨어의 발전을 통해 해결 할 수 있었다.
mechanism : Associative mapping
Translation Look - aside Buffer (TLB) 는 이름에서 알 수 있듯
특별한 자료구조를 담은 버퍼로서 메모리 내에 존재하는 것이 아니라 CPU 내부에 존재한다.
이로인해 Associative mapping 이라는 방식이 등장했는데 이는 PMT 를 메모리 내부에 저장해두는 것이 아닌 TLB 에 저장해두는 것이다.
TLB 는 CPU 내부에 존재하는 특별한 하드웨어로 시스템 콜 없이 조회가 가능하며 테이블을 한 번에 병렬적으로 조회 하기 때문에 매우 빠르게 조회하는 것이 가능했다.
mechanism : Hybrid direct/associative mapping
ㅋㅋ 저장장치가 속도가 빠르면 뭐다 ?
TLB 의 엄청난 단점은 가격이 매우 비싸다는 것이다.
이에 프로세스의 크기가 늘어 날 수록 필요한 TLB 의 크기가 커졌기에 개발자들은 direct / associative mapping 방법을 동시에 같이 쓰도록 하였다.
-
TLB에서는 모든PMT를 정의하는 것이 아니라 가장 최근에 사용된Page에 대한 정보를 담도록 한다. (용량이 모두 차면 가장 오래된Page는 삭제한다.)왜 최근에 사용된 것을 담을까 ?
그 이유는
locallity때문이다. 프로그램의 수행 과정에서 한 번 접근한 영역을 다시 접근 또는 인접한 영역을 다시 접근 할 가능성이 높기 때문이다. -
TLB에 들어가지 못한Page에 대한 정보는 이전과 같이kernel의PMT에 저장된다. -
v = (p,d)주소를 실제 주소로 변환 할 때 우선적으로TLB를 확인한다.
3.1 이 때 만약TLB에page에 대한 정보가 있다면 실제 주소로 변경한다. 이런 경우를TLB hit라고 한다.
3.2 만약TLB에 정보가 존재하지 않는다면kernel memory에 접근하도록 한다. 이를TLB miss라고 한다.
3.3kernel memory에서 사용된page에 대한 정보는TLB에 적재된다.
Memory Management
자 여태까지의 이야기들은 운영체제에서 프로세스 내 가상 메모리 주소를 실제 메모리 주소로 어떻게 변환하는지에 대한 이야기였다.
그럼 이번엔 어떻게 프로세스를 실제 메모리에 적재하는지 ? 에 대해 알아보자
Frame table
address mapping 을 위해 기법 별 table 이 존재했듯 메모리 관리를 위한 테이블이 필요하며
이를 Frame table 이라고 한다.
Frame table 은 매우 매력적인 구조로 되어 있는다.
-
page frame number: 분할 해둔page frame을 식별하는 식별자 -
allocated:page frame에 자료가 있는지 없는지를 나타내는 비트로 0과 1만 존재 -
PID (Process ID):page frame에 자료가 있을 경우 어떤 프로세스가 맡고있는지에 대한 식별자 ,PID를 통해 해당page frame을 보호하거나 공유하는 것이 가능하다. -
Link Filed:Link filed는 현재 비어있는page frame을 기준으로 본인 다음으로 비어있는page frame을 가리키는 포인터다. -
AV(Avaliable):Link Filed의header를 가리키는 포인터로 할당이 필요한page Frame의 경우엔AV가 가리키는 영역에 할당되고AV는 한 칸 앞으로 이동한다.
Page sharing
프로세스 별 공통되는 page 를 공유하고 싶은 경우가 존재한다.
예를 들어 공통된 프로세스를 N 개 띄워뒀을 때 프로세스의 로직을 모두 메모리에 올려두는 것보다 하나만 올려두고 공유한다거나
혹은 서로 다른 프로세스더라도 페이지를 공유하고 싶은 경우가 존재한다.
페이지 공유는 다음과 같은 내용이 가능하다.
Procedure pages: 함수와 같은 순수한 코드Data page:read only , read - write data, 하지만 상호배제의 원칙이 적용된
page sharing 은 각기 다른 PMT 에서 서로 같은 page frame number 를 가리킴으로 작동한다.
다만 paging system 의 단점으로 인해 sharing 을 힘들게 하는 부분이 존재한다.
그것은 paging system 은 논리적이지 않고 물리적인 단위로 프로세스를 나누기 때문에
서로 같은 page frame number 를 공유하면서 서로 다른 page number 를 사용하는 경우 문제가 발생한다.
공유하는 페이지 p' 에서 함수의 시작지점부터 d 만큼 떨어진 변수에 접근하라 했을 때
첫 번째 프로세스는 k1 이 함수의 시작 지점을 나타내는 가상 주소 , 두 번째 프로세스는 k2 가 가리키는 가상주소이다.
그럼 서로 공유하는 페이지 p' 에서는 이동하고자 하는 주소를 k1 , k2 중 어디로 하라고 해야할까 ?
어디로 이동하라고 하든 두 프로세스 중 하나는 무조건적으로 다른 페이지를 침범하게 된다.
이에 공유하는 페이지에 대해서는 모두 동일한 page number 를 사용하게 하여 문제를 해결 가능하다.
Page Protection
공유하는 페이지에서 만약 읽기 전용인 데이터를, 다른 프로세스가 수정해버린다면 문제가 발생 할 것이다.
이에 공유하는 페이지에 대해서 각 Page 별 사용가능한 기능을 명시해두기 위해 Protection bit 를 이용한다.
