<aside> ☝🏻 메모리 할당 방식엔 연속 메모리 할당, 페이징을 통한 메모리 할당(+이를 통한 가상 메모리 관리)가 있다.
이 두 가지 방식의 발전 과정은 외부 단편화라는 문제를 해소하기 위해 진행되어왔다.
메모리 할당을 알기 전 알아야 할 지식: 스와핑 → 스와핑: 일부 프로세스들을 보조기억장치로 쫓아내고, 그렇게 남은 빈 공간에 다른 프로세스를 적재하여 실행하는 방식
</aside>
연속 메모리 할당
최초 적합: 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간 발견 시 배치하는 방식
→ 검색 최소화, 빠른 할당
최적 적합: 빈 공간을 모두 검색한 후, 가장 작은 공간에 배치하는 방식
→ 메모리 공간 효율 증가
최악 적합: 빈 공간을 모두 검색한 후, 가장 큰 공간에 배치하는 방식
→ 외부 단편화 문제(빈 공간이 있음에도 그보다 큰 프로세스를 적재하지 못 하는 상태, 메모리 낭비)
외부 단편화 해결 방식
a. 압축: 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
→ 오버헤드 야기, 현실적으로 쉽지 않음
b. 페이징: 각기 다른 크기의 프로세스를 일정한 단위로 잘라 할당하는 방식
프로세스의 논리 주소 공간을 페이지 단위로, 메모리 물리 주소 공간을 프레임 단위로 자른 후, 페이지를 프레임에 할당하는 방식
페이징을 통한 메모리 할당
→ 페이지 단위로 스와핑(스왑 아웃=페이지 아웃/스왑 인=페이지 인)하여 메모리를 관리하는 방법
페이지 테이블
→ 메모리의 불연속적 배치로 인한 실행의 어려움을 해소하기 위해, 페이지 번호와 프레임 번호를 짝지어주는 이정표**, 프로세스마다 테이블 한 개씩 존재하며 테이블은 메모리에 적재됨**
페이지 테이블 베이스 레지스터(PTBR)
→ 각 프로세스의 페이지 테이블이 적재된 주소를 가리키는 이정표, CPU 레지스터에 적재됨
TLB
→ 메모리 접근 시간이 두 배로 늘어나는 것을 방지하기 위해 사용하는 페이지 테이블의 캐시 메모리, 캐시 메모리에 적재됨, 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장
페이징에서의 주소 변환
특정 주소에 접근하기 위해선 두 가지 정보가 필요
페이징 시스템에서는 모든 논리 주소가 <페이지 번호, 변위>로 이루어짐
즉 논리 주소 <페이지 번호, 변위>는 페이지 테이블을 통해 <프레임 번호, 변위>로 변환됨
이때 페이지 테이블의 각각의 가로 줄(행)을 페이지 테이블 엔트리(PTE)라고 부른다
페이지 테이블 엔트리
→ 페이지 테이블 엔트리에는 페이지 번호, 프레임 번호도 있지만 유효 비트, 보호 비트, 참조 비트, 수정 비트 등도 있다.
a. 유효 비트: 현재 해당 페이지에 접근 가능한지 여부(← 모든 페이지가 메모리에 있지 않기 때문)
→ CPU가 유효 비트가 0인 페이지로 접근할 시 페이지 폴트(예외) 발생
→ 하드웨어 인터럽트를 처리하는 과정과 유사하게 진행
b. 보호 비트: 페이지 보호 기능을 위해 존재하는 비트
→ 두 개의 비트일 경우, 0은 읽기만 가능, 1은 읽고 쓰기 가능
→ 세 개의 비트일 경우, r가 읽기, w가 쓰기, x가 실행 가능
c. 참조 비트: CPU가 이 페이지에 접근한 적이 있는지 여부
→ 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지는 0, 그렇지 않으면 1
d. 수정 비트: 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부
→ 변경된 적 없으면 0, 있으면 1
→ 이를 통해 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는 판단
요구 페이징
→ 실행에 요구되는 페이지만을 메모리에 적재하는 기법
→ 페이지 폴트 처리 루틴 실행(해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정)
이때, 아무런 페이지도 메모리에 적재되지 않은 채 무작정 실행해서 페이지 폴트가 계속 발생하다 빈도가 떨어지는 기법이 ‘순수 요구 페이징’ 기법
→ 요구 페이징 시스템의 안정적인 작동엔 ‘페이지 교체’와 ‘프레임 할당’이 중요하다.
페이지 교체 알고리즘(← 페이지 교체)
<aside> ✌🏻 요구 페이징에서 페이지 교체가 중요한 이유: 메모리와 보조기억장치끼리 페이지 교체가 적어 성능이 높아지기 때문이다.
페이지 참조열: CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열 → 페이지 폴트 횟수를 페이지 참조열을 통해 알 수 있다.
</aside>
FIFO 페이지 교체 알고리즘
→ 메모리에 가장 먼저 올라온 페이지부터 내쫓는 알고리즘
최적 페이지 교체 알고리즘
→ CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
→ ‘앞으로의’ 사용 빈도가 가장 낮은 페이지를 교체하는 방식
LRU 페이지 교체 알고리즘(Least Recently Used Page Replacement Algorithm)
→ 가장 오랫동안 사용되지 ‘않은’ 페이지를 교체하는 알고리즘
스래싱과 프레임 할당(← 프레임 할당)
<aside> ✌🏻 요구 페이징에서 프레임 할당이 중요한 이유: 페이지 교체 이외에 사용할 수 있는 프레임 수가 적어서 생기는 페이지 폴트도 자주 발생한다. 더 근본적인 이유이기도 하다. 새로운 페이지를 참조할 때마다 페이지 폴트가 발생하기 때문이다. 계속 페이징을 하지 않도록 넉넉한 사용 가능 프레임 수가 필요한 것이다.
스래싱: 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
멀티프로그래밍의 정도: 메모리에서 동시에 실행되는 프로세스의 수
→ 멀티프로그래밍의 정도와 CPU 이용률을 통해 스래싱을 확인할 수 있다.
→ 고로 운영체제는 각 프로세스들이 무리 없이 실행할 수 있도록 최소한의 프레임 수를 파악하고 적절한 수만큼 할당해주어야 한다.
</aside>
프레임 할당 방식-정적 할당 방식
→ 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지 실행해봐야 알 수 있으므로, 동적 할당 방식도 검토할 필요가 있음
프레임 할당 방식-동적 할당 방식
작업 집합 모델: 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하며 빈번한 페이지 교체를 방지하는 방식
작업 집합 모델: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 기억하며 빈번한 페이지 교체를 방지하는 방식
→ 프로세스가 참조한 페이지와 일정 시간 간격, 두 조건을 가지고 작업 집합을 구한다.
할당된 프레임 수와 페이지 폴트율의 상관 관계를 통한 프레임 할당
→ 두 상관 관계는 반비례이므로, 상한성과 하한선을 두어 개별 프로세스에 대한 페이지 폴트율을 조정하는 것이 좋다.
