가상메모리, 페이징, 세그멘테이션, 페이지교체 알고리즘

가상메모리, 페이징, 세그멘테이션, 페이지교체 알고리즘

 

 

 

# 가상메모리

프로그램이 실행되기 위해서는 주기억장치로 들어가야 하는데,

실행될 프로그램이 주기억장치보다 크거나 여러개인 경우에는 주기억장치 공간의 부족으로 인해 (저번 포스팅의 외부단편화, 내부단편화) 프로그램이 제대로 실행되지 못할 수 있다.

그래서 당장 실행에 필요한 부분만 우선 주기억장치에 저장하고,

가상의 공간을 만들어서

(나머지는 보조기억 장치에 두고 동작하도록 해서)

하나뿐인 컴퓨터 시스탬 내의 자원들을 여러개의 자원을 가지고 있는 것처럼 착각하게 하고자 하는 방법!

​

즉 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식을 말한다. 이 방식은 멀티태스킹 운영 체제에서 흔히 사용되며, 실제 주기억장치보다 큰 메모리 영역을 제공한다.

​

이런 가상메모리와 실제 메모리 사이의 재빠른 중계 역할을 맡고있는 것으로는 3가지가 있다.

​

​

1. 페이징 Paging

아래는 크기가 10인 주기억 장치에서 크기 20의 프로그램 A, B를 실행하는 그림!

당장 실행에 필요한 프로그램 A의 일부인 A1을 주기억장치에 올려 실행하고,

나머지는 보조기억장치에 두고있다. 물론 A2가 실행에 필요하게 되면, 주기억장치로 올리면 된다.

여기 왼쪽 그림을 보면 프로그램을 일정한 크기로 나누어져 있는데,

이렇게 가상 메모리 공간을 일정한 단위로 나눈 것을 페이지라 하며

이 페이지 단위로 주기억장치에 올리며 동작하는 것을 페이징 이라 한다.

* 하나의 메모리를 분배하는 것이 아니라, 가상메모리를 같이 쓴다는 점에서 고정분할과는 차이가 있다.

​

​

이때 실제 주기억장치(Physical memory)의 페이지에 해당하는 부분을 프레임 이라고 하고,

보조기억 장치(Logical memory)의 페이지를 페이지라고 한다.

​

​

: 동작원리 :

이렇게 16개의 페이지로 이루어진 프로세스 A와 B가 실행중이고, 주기억장치는 24개의 페이지 프레임 크기다.

그리고 각 페이지의 크기는 1000이라 가정하자.

​

그리고 프로세스 A의 페이지 0과, 프로세스 B의 페이지 0, 1이 당장 실행되어야 하고,

프로세스 A의 페이지 0이 주기억장치 페이지 프레임 0에,

B의 페이지 0과 1이 주기억 장치 페이지 프레임 2와 3에 저장된다고 가정한다.

​

​

이때 각 프로세스 마다 페이지가 주기억장치의 어느 프레임에 저장되는지를 나타내는 테이블을 운영체제가 관리하는데,

이를 # 페이지 테이블 이라 하고,

하나의 프로세스는 하나의 페이지 테이블을 가진다.

페이지 테이블은 Index를 키로 해당 페이지에 할당된 메모리 (Frame)의 시작주소를 Value로 저장한다.

​

* 페이지 테이블 : 논리주소가 테이블의 인덱스 값을 가리키고, 테이블은 value로 물리주소값을 가짐.

​

* 프로세스의 페이지가 실행될 때 논리주소는 페이지 번호와 페이지 변위로 구성.

: 논리주소 = 페이지번호 p +페이지 변위 d

물리주소 = 프레임 번호 f + 변위 d //페이지 테이블에 있음.

 

* 가상메모리 안에서 쓰는 것 -> 페이지. (일이 안됨)

메인메모리 안에서 쓰는 것 -> 프레임. (여기서 진짜 일이 진행된다)

​

균등한 크기로 나누기 때문에 외부단편화가 없지만,

내부단편화가 생길 수 있다!

​

​그리고 프로세스를 실행할 때 프로세스를 페이지로 나누어 프레임에 할당하는 방법을 이용하기 때문에,

꼭 물리 메모리상에 프로세스 크기 이상의 연속된 공간이 필요하지 않게 된다.

유저의 측면에서는 보는 메모리와 실제 물리 메모리를 완전히 분리시켜두었다는 것이다.

유저가 보기에는 단 하나의 메모리를 사용하는 것처럼 보이지만 이를 page table을 통하여 물리 메모리에 분배해서 할당하므로 프로세스는 실제로 메모리 상에 흩어져 할당되어 있는 것이다.

​이런 page table을 통한 매핑은 유저에게는 안보이므로 프로세스는 해당 프로세스 외에 다른 프로세스의 메모리 공간에 어드레싱할 수 없게 된다.(교수님?..)

​

OS는 물리 메모리도 관리하므로, 물리 메모리의 총 프레임이 몇 개인지, 어떤 프레임이 할당 되었는지, 어떤 프레임이 할당 가능한지를 알고 있어야한다. 이러한 정보는 frame table이란 자료구조를 이용하여 관리한다. 이 frame table의 각 엔트리는 각 물리 메모리의 프레임이 할당 가능한지 혹은 할당되었는지를 담고 있고, 만약 프레임이 할당되었으면 어떤 프로세스의 어떤 페이지가 할당 되었는지에 관한 정보를 담고 있다.

이런 여러과정을 거쳐야 하므로 페이징 기법의 단점은 문맥 전환 시간을 증가시킨다는 것.

​

​​

# 세그멘테이션 Segmentation

페이징은 프로세스를 일정 크기인 페이지 단위로 잘라서 메모리에 적재하는 방법이었다.

하지만 프로세스를 물리적인 단위인 페이지 말고 논리적 내용 단위인 세그먼트로 자를 수 있는 세그먼테이션 방법이 있다.

​

예를 들면 우리가 돼지를 잡아서 보관을 한다고 생각해보자.

페이징의 방법을 사용하면 돼지를 모두 같은 단위로 잘라서 보관을 하는 것이다.

반면에 세그먼테이션은 부위별로 다른 크기로 잘라서 보관하는 것이다.

미안해서 하트로 구분함

​

세그멘테이션은 프로세스를 세그먼트의 집합으로 생각한다.

사실 하나의 프로세스가 동작하려면 기본적으로 코드, 데이터, 스택 세 가지의 세그먼트는 항상 가지고 있다.

그리고 더 들어가 보면 코드에서도 main 함수가 있을 수 있고, 다른 함수들이 있을 수도 있고, 다른 루틴이 있을 수도 있다.

데이터를 보아도 어떤 구조체가 있을 수도 있고 배열도 있을 수 있다.

그래서 세그먼테이션은 물리적인 크기의 단위가 아닌 논리적 내용의 단위(의미가 같은)로 자르기 때문에 세그먼트들의 크기는 일반적으로 같지 않다.

​

프로세스를 어떻게 자르는가에 대한 방법 빼고 메모리에 할당하는 방법에 대해서는, 우선 페이징과 방법이 같다.

MMU 내의 재배치 레지스터를 이용하여 논리 주소를 물리 주소로 바꾸어 주는 방식을 취한다.

MMU는 세그먼트 테이블로 CPU에서 할당한 논리 주소에 해당하는 물리 주소의 위치를 가지고 있다.

이 방법을 이용하면 CPU는 프로세스가 연속된 메모리 공간에 위치한다고 착각을 하게 된다.

​

​

 

주소를 변환하는 방법 역시 같다.

하지만, 논리주소에서 보내는 주소값에서 하위 변위 비트를 제외한 앞의 비트들은 페이징 번호가 아니라

세그먼트 번호가 되는 것이다.

= 페이징과 테이블이 다르게 생겼다.

​

세그먼테이션의 경우에도 보호와 공유의 기능을 수행하고 있다.

모든 논리 주소들은 세그먼테이션 테이블을 경우하게 되므로 세그먼트 테이블 엔트리마다 r, w, x 비트를 만들어 해당 세그먼트에 대한 접근 제어를 가능하게 해준다. 또한 같은 프로그램을 사용하는 복수 개의 프로세스가 있다면 메모리에 하나만 적재하여 프로세서의 세그먼트 테이블 코드 영역이 같은 곳을 가리키게 만든다. 그런데 위와 같은 기능이 페이징의 기법보다 더 좋다고 할 수 있다. 간단하게 생각을 해보아도 그렇다는 것을 알 수 있다.

페이징은 프로세스를 같은 단위로 자르게 되므로 중요한 부분과 중요하지 않은 부분이 같은 페이지 안으로 잘라질 수 있다. 또한 코드 영역 또한 같은 단위로 잘리므로 애매하게 잘려질 확률이 있다.

하지만 세그먼테이션의 방법으로 자르게 되면 코드 영역은 코드 영역으로 잘리게 되고 중요한 세그먼트, 중요하지 않은 세그먼트를 논리적인 내용 측면으로 자를 수 있다.(처리 단순화) 그렇게 되면 보호와 공유의 기능을 수행하기 쉬워지는 것이다. 내용적인 측면으로 다 나누어 졌기 때문이다.

​

단점도 가지고 있다. 세그먼트는 크기가 고정되어 있지 않고 가변적이다. 크기가 다른 각 세그먼트를 메모리에 두려면 동적 메모리 할당을 해야 한다. 앞에서 말한 외부 단편화가 발생할 수 있다. 외부 단편화는 메모리 낭비를 매우 크게 발생시킨다.

따라서 우리는 세그먼테이션과 페이징의 기법을 모두 사용하고자 한다. 두 방식 모두 장단점을 가지고 있으니 장점만을 가져오게 되면 좋은 방법이 될 수 있기 때문이다. 세그먼테이션은 보호와 공유 면에서 효과적이고 페이징은 외부 단편화 문제 해결에 효과적이므로 두 가지 모두를 사용할 수 있으면 좋을 것이다. 따라서 세그먼트를 페이징 하는 방법을 취한다.

​

페이징	세그먼테이션
주기억장치를 고정된 크기의 프레임으로 분할	주기억 장치는 분할되지 않음
프로그램은 다수의 페이지로 분할	프로그래머가 컴파일러에게 프로그램 세그먼트를 명시해줌
내부단편화	외부단편화
각 페이지가 어느 프레임에 적재되어 있는지 나타내기 위해, OS는 프로세스 각각을 위한 페이지 테이블을 관리해야함	각 세그먼트의 적재 위치와 길이를 나타내기 위해, OS는 프로세스 각각을 위한 세그먼트 테이블을 관리해야 함

​

# 세그멘테이션 페이징

메모리에 할당하는 방식은 페이징, 가상메모리 상태에서는 세그먼테이션 리스트 사용.

세그멘 자체를 아주 작은 페이지로 만들었다고 할 수 있다.

​

세그먼테이션과 페이징 두 장점을 수용한다.

 

여기서 또 중요한 키워드로는 테이블 매핑(역맵핑, 집합맵핑, 집합연관 맵핑)이 있는데

근데 이것은 내가 지금 기억이 잘 안나니 Pass 합니돵?

 

 

​

페이지 교체 알고리즘

페이지 부재가 발생했을 때 (페이지 테이블의 valid bit 이 0일 때)

만약 해당 페이지를 메모리로 올릴 공간이 남아 있다면, 디스크(물리)에서 메모리(가상)로 페이지를 올리고 페이지 테이블을 갱신해주면 된다.

그러나 해당 페이지를 올릴 메모리 공간이 없을 경우엔,(= 캐시 메모리가 가득 차 있는 상태에서 CPU가 캐시 메모리에 접근했다가 실패했을때,) 메모리에 있는 페이지의 일부를 디스크로 내보내고, 해당 페이지를 메모리에 올려야 한다!

이때, 어떤 페이지를 메모리 밖으로 내보낼 것인지를 결정하는 방법이~~

페이지 교체 알고리즘이다.

 

=페이지 부재율이 가장 낮도록 하는 것이 목표,

일반적으로 프레임 수가 증가하면 페이지 부재가 줄어든다.

​

1. Fifo

가장먼저 메모리에 적재된 페이지를 먼저 내보내는 것.

구현하기 가장 쉽지만 성능이 좋지는 않다

​

2 OPT: 앞으로 (미래) 가장 사용되지 않을 것 같은 페이지를 교체해 주겠다.

미래를 예측하는 것이라 구현이 어렵지만 (거의 불가능?) 이론상 성능이 가장 좋다

​

3 LRU (Least Recently Used) :

가장 오랫동안 사용되지 않은 채로 있던 블록을 교체.

셋 중 가장 좋다고 할 수 있다.

얘들이 할당을 받으면,

옆에 하나 표를 만들어 놓고, 거기 카운트를 함. 해당 메모리에 접근하는지 안하는지 카운팅.

임벨리드 떠 있는 애들이 있으면 -

거의 안쓸것 같은애가 있으면, 빼버리고, 일단 들어오고나서 몇번 안쓰였으면

여기서 가장 중요한 것은 페이지 접근 시점. 해당하는 메모리에 접근을 했었는지 카운팅.

​

4 LFU :

사용빈도가 가장 적은 페이지를 교체 (가장 적게 참조된 페이지 교체)

* 구현하기 쉬운 순서와 장단점 기억하기​

​

* 페이지 교체는 적을수록 좋다.

페이지 교체는 가상메모리-물리메모리사이의 교환. 그 둘을 왔다갔다 하는것이기 때문이다.

원래는 페이지가 물리메모리에 있어야 하는데, 거기 있지 못하고 가상메모리는- 보조기억 장치에 있는 상황인거다. 보조기억 장치는 엄청 느린데!

그렇게 비효울 적인 곳에 자꾸 온다는건, 뭔가 잘못 데이터 저장을 했다는 것이고-> 뭔가 비효율적으로 되고 있다는 것.

페이지 교체가 최대한 안일어나게 하려면,

OPT가 가장 좋기는 하다. 미래를 예측하는 거니깐. 근데 이게 사실상 불가능하니

그나마 지금까지 가장 안쓰였던 것이 앞으로도 안쓰이지 않을까~하는 가정을 하는 LRU를 사용하는 것이 가장 효율적이라 할 수 있겠다.

물론 이 LRU는 추가로 카운팅해야하고.. 그런 부분은 감안 해야한다.