[운영체제] 연속 메모리 할당과 가상 메모리 할당

연속 메모리 할당과 가상 메모리 할당

---

연속 메모리 할당

프로세스에 연속적인 메모리 공간을 할당

 

연속 메모리 할당

 

스와핑

- 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역(스왑 영역)으로 쫒아내고(스왑 아웃) 생긴 빈 공간에 새 프로세스 적재(스왑 인)
- 효율적인 메모리 관리
- 프로세스들이 요구하는 메모리 공간 크기가 실제 메모리 크기보다 크더라도, 스와핑을 이용하면 모두 실행시킬 수도 있음

- 프로세스는 메모리의 빈 공간에 할당되어야 한다. 빈 공간이 여러 개 있다면?
- 최초 적합, 최적 적합, 최악 적합

최초적합(first-fit)
- 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
- 검색 최소화, 빠른 할당

최적 적합(best-fit)
- 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 할당

최악 적합(worst-fit)
- 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당

외부 단편화

- 사실, 프로세스를 연속적으로 메모리에 할당하는 방식은 메모리를 효율적으로 사용하는 방법이 아니다.
- 외부 단편화 (external fragmentation)이라는 문제가 발생하기 때문
- 프로세스들이 실행되고 종료되길 반복하며 메모리 사이에 빈 공간 발생
- 외부 단편화
  - 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
- 그로 인해 물리 메모리보다 큰 프로세스 실행 불가

 

외부단편화

외부 단편화 해결

- 메모리 압축(compaction)
  - 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
  - 프로세스를 적당히 재배치시켜 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
  - 많은 오버헤드 야기

- 가상 메모리 기법

가상 메모리

- 실행하고자 하는 프로그램을 일부만 메모리에 적재(부분적재)하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
- 페이징, 세그멘테이션

페이징(paging)

- 외부 단편화가 발생했던 근본적인 문제는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문
- 프로세스를 일정 크기로 자르고 이를 메모리에 불연속적으로 할당할 수 있다면?
- 프로세스의 논리 주소 공간을 페이지라는 일정 단위로 자르고, 메모리의 물리 주소 공간을 프레임이라는 페이지와 동일한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법

페이징

페이징에서의 스와핑

- 프로세스 단위의 스왑 인, 스왑 아웃이 아닌 페이지 단위의 스왑 인(페이지 인), 스왑 아웃(페이지 아웃)
- 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃
- 실행에 필요한 페이지들은 메모리로 스왑 인
- 프로세스를 실행하기 위해 모든 페이지가 적재될 필요 없음
- 물리 메모리보다 더 큰 프로세스도 실행될 수 있다.

페이지 테이블

- 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 일일이 알기는 어렵다.
- 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행할 수가 없음
- CPU 입장에서 다음에 실행할 명령어 위치를 찾기가 어려워짐
- 페이지 테이블은 실제 메모리 내의 주소인 물리 주소에 불연속적으로 배치되더라도 CPU가 바라보는 주소인 논리 주소에는 연속적으로 배치되도록 하는 방법
- 페이지 번호와 프레임 번호를 짝지어주는 일종의 이정표
- 프로세스마다 페이지 테이블이 있다.
- 물리적으로는 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리주소는 연속적으로 보임
- CPU는 그저 논리 주소를 순차적으로 실행하면 될 뿐

페이지 테이블

내부 단편화

- 페이지 크기가 10KB, 프로세스 크기 108KB
- 2KB: 내부 단편화
- 하나의 페이지 크기보다 작은 크기로 발생

PTBR(Process Table Base Register)

 

- 페이지 테이블의 시작 주소를 가지는 레지스터
- 프로세스마다 페이지 테이블이 있고, 각 페이지 테이블은 CPU 내의 프로세스 테이블 베이스 레지스터가 가리킨다.
- 페이지 테이블이 메모리에 있으면 메모리 접근 시간 2배로 증가
- 페이지 테이블 참조하기 위해 한 번
- 페이지 참조를 위해 한 번

TLB(Translation Lookaside Buffer)

- TLB: CPU 곁에 페이지 테이블의 캐시 메모리
- 페이지 테이블의 일부를 가져와 저장
- CPU가 접근하려는 논리 주소가 TLB에 있다면 TLB 히트 (메모리 접근 1번)
- CPU가 접근하려는 논리 주소가 TLB에 없다면 TLB 미스 (메모리 접근 2번)

페이징에서의 주소 변환

- 특정 주소에 접근하고자 한다면 어떤 정보가 필요할까
  - 어떤 페이지/프레임에 접근하고 싶은지
  - 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
- 페이징 시스템에서의 논리 주소
  - 페이지 번호(page number)와 변위(offset)
- <페이지 번호, 변위>로 이루어진 논리 주소는 페이지 테이블을 통해 <프레임 번호, 변위>로 변환된다.

페이지 테이블 엔트리

- 페이지 테이블의 각각의 행: 페이지 테이블 엔트리(PTE)
  - 현재까지 설명한 PTEL 페이지 번호, 프레임 번호

- 유효 비트
  - 현재 해당 페이지에 접근 가능한지 여부

- 유효 비트가 0인 페이지에 접근하려고 하면 페이지 폴트(page fault) 라는 인터럽트 발생
1. CPU는 기존 작업 내역 백업
2. 페이지 폴트 처리 루틴 실행
3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
4. 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근 가능

- 보호 비트
  - 페이지 보호 기능을 위해 존재하는 비트

- 참조 비트
  - CPU가 이 페이지에 접근한 적이 있는지 여부

- 수정 비트 (= dirty bit)
  - CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부
  - 스와핑과 관련있음
  - 수정된 페이지는 스왑 아웃될 때 보조기억장치에도 쓰기 작업을 거쳐야 한다.

 

페이지 테이블 엔트리

쓰기 시 복사 (copy on write)

이론적인 fork()

- 프로세스는 기본적으로 자원을 공유하지 않는다. 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 적재(프로세스 생성 시간 지연, 메모리 낭비)

쓰기 시 복사

- 부모 프로세스와 동일한 자식 프로세스가 복제되어 생성되면 자식 프로세스는 부모 프로세스와 동일한 프레임을 가리킴 (쓰기 작업 없다면 이 상태 유지)
- 부모 프로세스/자식프로세스 둘 중 하나가 페이지에 쓰기 작업 수행 시 해당 페이지는 별도의 공간으로 복제 (프로세스 생성 시간 절약, 메모리 절약)

- 페이징의 이점 중 하나

계층적 페이징

- 프로세스 테이블의 크기는 생각보다 작지 않다.
- 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 낭비
- 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 방법
- 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
- 즉, 페이지 테이블을 여러 페이지로 쪼개고 이 페이지를 가리키는 페이지 테이블(outer page table)을 두는 방식
- 모든 페이지 테이블을 항상 메모리에 적재할 필요가 없어짐
  - CPU와 가장 가까이 위치한 페이지 테이블(outer page table)은 항상 메모리에 유지

계층적 페이징

계층적 페이징을 이용하는 환경에서의 논리 주소

1. 바깥 페이지 번호를 통해 페이지 테이블의 페이지를 찾기
2. 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로서 물리 주소 얻기
cf) 계층이 많다고 해서 무조건 빠르거나 좋지는 않다.

페이지 교체와 프레임 할당

- 물리 메모리보다 큰 프로세스를 실행할 수 있지만, 그럼에도 물리 메모리의 크기는 한정되어 있다.
- 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고 프로세스들에게 적절한 수의 프레임을 할당해야 한다.

요구 페이징

- 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
- 요구되는 페이지만 적재하는 기법

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2. 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
5. 다시 1번을 실행한다.

요구 페이징 시스템이 안정적으로 작동하려면 해결해야 할 문제

 

- 페이지 교체
- 프레임 할당

페이지 교체 알고리즘

- 요구 페이징 기법으로 페이지들을 적재하다보면 언젠간 메모리가 가득 차게 된다.
- 당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야 한다.
- 이때 어떤 페이지를 내보내야 하는지를 결정하는 방법이 페이지 교체 알고리즘

좋은 페이지 교체 알고리즘

- 페이지 폴트가 적은 알고리즘
- 페이지 폴트가 발생하면 보조 기억장치에 접근해야 해서 성능 저하
- 페이지 참조열을 통해 페이지 폴트 횟수를 알 수 있음
  - CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

FIFO(First-in First-out) 페이지 교체 알고리즘

- 가장 단순한 방식
- 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
- 구현이 간단한데 문제점이 있음
- 프로그램 실행 초기에 잠깐 실행될 페이지는 내쫓아도 될지 모르지만, 프로그램 실행 내내 사용될 페이지는 먼저 적재되었다고 내쫓아선 안됨

FIFO 페이지 교체 알고리즘 - 보완책

- 2차 기회(second-chance) 페이지 교체 알고리즘
- 참조 비트1: 한 번 더 기회를 주기 (참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정)
- 참조 비트 0: 내쫓기

최적 페이지 교체 알고리즘

- CPU에 의해 참조되는 횟수를 고려
- 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지
- 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
- 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
- 가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘
- 하지만 실제 구현이 어렵다
- 앞으로 오래동안 사용되지 않을 페이지를 예측하는 것은 쉽지 않음
- 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선(척도)으로 간주

LRU(Least-Recently-Used) 페이지 알고리즘

- 최적 페이지 교체 알고리즘: 가장 오래 사용되지 않을 페이지 교체
- LRU 페이지 교체 알고리즘: 가장 오래 사용되지 않은 페이지 교체
  - 최근에 사용되지 않은 페이지는 않으로도 사용되지 않을 것이라 예측

기타 페이지 교체 알고리즘

- 이외에도 많은 페이지 교체 알고리즘들이 있다.(e.g.  LRU 페이지 교체 알고리즘의 파생 알고리즘)
- 페이지 교체 알고리즘이란 무엇인지
- 페이지 교체는 왜 해야하는지
- 무엇이 좋은 페이지 교체 알고리즘인지 기억하는 것이 중요

스레싱과 프레임 할당

페이지 폴트가 자주 발생하는 이유

- 나쁜 페이지 교체 알고리즘을 사용해서
- 프로세스가 사용할 수 있는 프레임 자체가 적어서

스레싱

- 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제
- 동시 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 높아지는 것이 아니다.
- 멀티 프로그래밍의 정도 = 메모리에 동시에 실행되는 프로세스의 수
- 스레싱이 일어나는 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문
- 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다.

 

스레싱

프레임 할당

균등 할당(equal allocation)

- 가장 단순한 할당 방식
- 모든 프로세스들에게 균등하게 프레임을 할당하는 방식
- 실행되는 프로세스의 프레임 크기는 각기 다를텐데 동일한 프레임을 할당하는 것은 비합리적

비례 할당(proprotional allocation)

- 프로세스의 크기를 고려
- 프로세스 크기에 비례하여 프레임 할당
- 크기가 큰 프로세스인데 막상 실행해보니 많은 프레임을 필요로 하지 않거나
- 크기가 작은 프로세스인데 실행해보니 많은 프레임을 필요로 한다면 문제가 생긴다.
- 결국 프로세스가 필요로 하는 프레임 수는 실행해봐야 알 수 있음
- 그래서 실행과정에서 프레임 크기를 결정하는 방식이 고안(동적 할당 방식)

균등 할당, 비례 할당: 정적 할당 방식


작업 집합 모델

- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- 스레싱이 발생하는 이유는 빈번한 페이지 교체 때문
  - 그렇다면 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 된다.
- 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지
- 작업 집합이란 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합

- 작업 집합을 구하려면
1. 프로세스가 참조한 페이지
2. 시간 간격이 필요

 

페이지 폴트 빈도

- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- 두 개의 가정에서 생겨난 아이디어
1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
2. 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.

- 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식