각각 프로세스 는 독립된 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한있음.
운영체제 만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않음.
Swapping : 메모리의 관리를 위해 사용되는 기법. 표준 Swapping 방식으로는 round-robin 과 같은 스케줄링의 다중 프로그래밍 환경에서 CPU 할당 시간이 끝난 프로세스의 메모리를 보조 기억장치(e.g. 하드디스크)로 내보내고 다른 프로세스의 메모리를 불러 들일 수 있다.
이 과정을 swap이라함.
주 기억장치(RAM)로 불러오는 과정을 swap-in
보조 기억장치로 내보내는 과정을 swap-out
swap 에는 큰 디스크 전송시간이 필요하기 때문에 메모리 공간이 부족할때 Swapping 이 시작된다.
메모리 관리 기법
연속 메모리 관리
고정 분할 기법 : 주기억장치가 고정된 파티션으로 분할
구현이 간단함, 운영체제 오버헤드가 거의 없음.
내부 단편화 발생으로 인한 비효율. 최대 활성 프로세스 수가 고정된다.
내부 단편화는 페이지 프레임에 여유공간이 과다하게 남는 현상.
동적 분할 기법 : 파티션들이 동적 생성되며 자신의 크기와 같은 파티션에 적재
내부 단편화가 없고 주기억장치를 보다 효율적으로 사용 가능
외부 단편화 발생을 해결하기 위한 메모리 집약이 요구됨. 처리기 효율이 나빠짐.
외부 단편화란: 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 자유 공간들이 많은 수의 작은 조각들로 나누어져 못 쓰게 되는 현상.
프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되어야 함
불연속 메모리 관리
페이지 : 고정 사이즈의 작은 프로세스 조각
프레임 : 페이지 크기와 같은 주기억장치 메모리 조각
페이지 테이블: 프로세스의 각 페이지에 해당하는 프레임 위치 관리
단순 페이징: 고정 분할과 유사.
단편화 : (기억 장치의 빈 공간 or 자료)가 여러 조각으로 나뉘는 현상(내부, 외부 단편화로 나뉨)
세그먼트 : 서로 다른 크기를 가진 논리적 블록이 연속적 공간에 배치되는 것
고정 크기 : 페이징(Paging)
단순 페이징
각 프로세스는 프레임들과 같은 길이를 가진 균등 페이지로 나뉨외부 단편화 X
소량의 내부 단편화 존재
모든 페이지가 적재되어야하고 페이지를 저장하는 프레임들은 연속적일 필요 없다.
단순 세그먼테이션
각 프로세스는 여러 세그먼트들로 나뉨내부 단편화 X, 메모리 사용 효율 개선, 동적 분할을 통한 오버헤드 감소
외부 단편화 존재
모든 세그먼트가 적재되어야하고 세그먼트를 저장하는 파티션들은 연속적일 필요 없다.
가상 메모리 페이징
단순 페이징과 비교해 프로세스 페이지 전부를 로드시킬 필요X외부 단편화 X / 가상 주소 공간이 크다.
복잡한 메모리 관리로 오버헤드 발생
필요한 페이지가 있으면 나중에 자동으로 불러들어짐
가상 메모리 세그먼테이션
필요하지 않은 세그먼트들은 로드되지 않음내부 단편화X / 가상 주소 공간이 크다. 보호와 공유를 지원한다.
복잡한 메모리 관리로 오버헤드 발생
필요한 세그먼트 있을때 나중에 자동으로 불러들어짐
가변 크기 : 세그먼테이션(Segmentation)
프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법
페이지교체(paging) 알고리즘.
페이징 기법으로 메모리를 관리하는 운영체제에서
페이지 부재 발생시 새로운 페이지를 할당해야 할때
현재 할당된 페이지 중 어떤 것을 교체할지 선택하는 방법론.
보조기억 장치로 부터 데이터를 램에 저장해놓고 램에 있는 데이터를 가지고 연산하는데 램과 같은 크기의 블록으로 구성해서 운용하게 된다. 이때 이 블록을 페이지라 한다. 필요한 데이터가 페이지에 있다면 cache hit, 없으면 cache miss
가상메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다. 하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 다 사용된 후에도 자리만 차지하고 있음. 따라서 메모리가 가득차면 추가로 페이지를 가져오기 위해서는 안쓰는 페이지는 out시키고 해당 공간에 현재 필요한 페이지를 in 시켜야 하는데 여기서 어떤 페이지를 out 시킬지 정해야한다. (out되는 page = victim page)
기왕이면 수정이 오래 되지 않은 그리고 않을 페이지를 선택해야 좋다.
Page Reference String
CPU는 논리 주소를 통해 특정 주소를 요구함
메인 메모리에 올라와 있는 주소들은 페이지의 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 페이지 결함 발생 X
따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 바로 Page Reference String
아래 그림의 참조열은 PRS고 파란색은 결함.
FIFO 알고리즘
victim page : out 되는 페이지는, 가장 먼저 메모리에 올라온 페이지
가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법임
초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮음
하지만 처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능함
자주쓰는 페이지를 내보낼 경우 비효율
First-in First-out, 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
2. OPT 알고리즘(최적 페이지 교체)
Optimal Page Replacement 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄
FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있음
하지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘임
구현이 실질적으로 불가능한 연구목적의 알고리즘.
3. LRU 알고리즘
Least-Recently-Used, 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘
최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나옴(시간 국부성과 공간 국부성)
OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘
(실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다)
OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나임
하지만 경험적 판단과 맞지 않는 상황의 존재와 막대한 오버헤드가 단점.
계수-기반(Counting-Based) 페이지 교체
페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅하는 방법이다. 이 방법을 이용해 두 가지의 알고리즘을 만들 수 있다.
LFU(least-frequently-used)
참조 횟수가 가장 작은 페이지를 교체
교체 대상인 페이지가 여러 개 일 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지로 교체한다.
LFU 알고리즘은 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있다.
앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문이다. 아래의 그림의 그 예시다.
초기에만 쓰인 7이 메모리에 잔존해 낭비가 일어난다.
역시 막대한 오버헤드가 일어날 수 있다.
MFU(most-frequently-used)
LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다. 참조 횟수가 적은 페이지가 최 근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단이다.
LFU와 MFU는 실제 사용에 잘 쓰이지 않는다.
구현에 상당한 비용이 들고,
최적 페이지 교체 정책을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문이다.
교체하는 방식
Global 교체
메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
Local 교체
메모리 상의 자기 프로세스 페이지에서만 교체하는 방식
다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음
따라서, 다양한 프로세스의 페이지가 메모리에 존재함
페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이
실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이다.
자기 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적
