운영체제 리뷰 6 - 메모리

참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제
사진 출처 : Operating System Concepts 10E

1. 연속 메모리 할당

<스와핑>

1. 개요

• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고 생긴 공간에 새 프로세스 적재
• 스왑 인, 스왑 아웃
  

2. 스와핑의 이점

• 프로세스들이 요구하는 메모리 공간 크기 > 실제 메모리 크기

<메모리 할당>

1. 개요

• 프로세스는 메모리의 빈 공간에 할당되어야 한다.
• 빈 공간이 여러 개라면, 어느 곳에 할당하는 것이 이득일까?
  • 세가지 방식을 이용: 최초, 최적, 최악 적합

2. 최초 적합 (first-fit)

• os가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 배치하기
• 장점: 검색의 최소화 & 빠른 할당

3. 최적 적합 (best-fit)

• os가 빈 공간을 모두 검색해본 다음, 적재 가능한 가장 작은 공간에 할당하기

4. 최악 적합 (worst-fit)

• os가 빈 공간을 모두 검색해본 다음, 적재 가능한 가장 큰 공간에 할당

<외부 단편화 (external fragmentation)>

1. 개요

• 위에서 언급한 세가지 방식, 즉 프로세스를 연속적으로 할당하는 방식은 메모리를 효율적으로 사용하는 방법이 아니다.

2. 외부 단편화 예시

• 프로세스들이 실행되고 종료되길 반복하면서 메모리 사이사이 빈 공간이 발생하는데,
• 빈 공간의 합만큼의 메모리를 할당하지 못해서,
  • 빈 공간의 합은 50MB이지만, 30MB, 20MB 이런식으로 떨어져 있으므로 50MB짜리 프로세스를 할당하지 못함
  • 아래 그림 참고
• 메모리가 낭비되는 현상
  

<외부 단편화 해결 방법>

1. 메모리 압축 (Compaction)

• 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
• 프로세스를 재배치시켜 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
• 오버헤드가 크다는 단점
• 그렇다면 현재는 어떤 방식을 사용하는가?

-> 2. 가상 메모리 기법, 페이징!

2. 페이징을 통해 가상 메모리 관리

<연속 메모리 할당의 문제점>

1. 외부 단편화

2. 물리 메모리보다 큰 프로세스 실행 불가

<가상 메모리 (virtual memory)>

1. 개요

• 가상 메모리란, 실행하고자 하는 프로그램을 일부만 메모리에 적재해서 물리 메모리보다 큰 프로세스를 실행하도록 하는 기술
• 페이징과 세그멘테이션이 존재

<페이징 (paging)>

1. 개요

• 외부 단편화의 근본적인 문제는, 각기 다른 크기의 프로세스를 메모리에 연속적으로 할당했기 때문임
• 모든 프로세스가 같은 크기였다면, 외부 단편화 발생 x
• 이러한 아이디어를 사용한 것이 페이징

2. 페이징

• 간단하게 말하면 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당하도록 하는 기술
• 페이징 동작 방식
  • 프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고,
  • 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 일정한 단위로 자른 뒤
  • 페이지를 프레임에 할당하는 가상 메모리 관리 기법

3. 페이징에서의 스와핑

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

4. 페이징에서의 의문점

• 프로세스를 이루른 페이지가 어느 프레임에 적재되어 있는지 CPU가 일일이 알기는 어렵다.
• 프로세스가 메모리에 불연속적으로 배치되어있다면, CPU 입장에서 이를 순차적으로 실행할 수 없다.
• CPU 입장에서 다음에 실행할 명령어 위치를 찾기 어려움
• 그렇다면, 물리 메모리에 분리되어 저장된 것을 어떻게 다시 모아서 CPU가 실행할 것인가? -> 페이지 테이블 이용!!

<페이지 테이블>

1. 개요

• 실제 메모리 내의 주소인 물리 주소에 불연속적으로 배치되더라도
• CPU가 바라보는 주소인 논리 주소에는 연속적으로 배치되도록 하는 방법

2. 페이지 테이블

• 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표
• 물리적으로는 분산되어 저장되어 있더라도 CPU입장에서 바라본 논리 주소는 연속적이다
• 결과적으로 CPU는 논리 주소를 순차적으로 실행하면 된다.
• 그러나 내부 단편화라는 문제 발생..

<내부 단편화 (internal fragmentation)>

1. 개요

• 내부 단편화는 어떤 프로세스의 크기가 페이지 크기의 배수가 되지 않을 때 발생
• 결과적으로 하나의 페이지 크기보다 작은 크기가 낭비된다.
• 낭비되는 크기가 외부 단편화 보다는 작다. (대체로)

<프로세스 테이블 베이스 레지스터 (PTBR)>

1. 개요

• PTBR은 각 프로세스가 가지고 있는 페이지 테이블이 어디에 저장되어있는지를 나타내기 위한 레지스터
  • 각 페이지 테이블은 CPU 내의 PTBR이 가리킨다.
    

2. 문제점

• 페이지 테이블이 메모리에 있다면, 메모리 접근 시간이 2배로 든다.
  • 페이지 테이블을 참조할 때 + 페이지를 참조할 때
• 해결방안은 TLB를 사용하기!!

< TLB>

1. 개요

• TLB란 페이지 테이블의 일부를 가져와서 저장하는 캐시 메모리
• 자주 참고하는 페이지 테이블 내용을 저장한다.

2. 동작 방식

• TLB hit
  • CPU가 접근하려는 논리 주소가 TLB에 있는 경우
  • 메모리 접근을 한번만에 수행가능
• TLB miss
  • CPU가 접근하려는 논리 주소가 TLB에 없는 경우
  • 메모리 접근을 두번할 수 밖에 없다.

<페이징에서의 주소 변환>

1. 개요

• 특정 주소에 접근하기 위해 필요한 정보
  • 어떤 페이지, 프레임에 접근하고 싶은지
  • 접근하고자하는 주소가 그 페이지,프레임으로부터 얼마나 떨어져 있는지

2. 페이징 시스템에서의 논리 주소의 구조

• 페이지 번호와 변위를 가짐
• <페이지, 변위> 로 이루어진 논리 주소는, 페이지 테이블을 통해 <프레임 번호, 변위>인 물리 주소로 변환된다.
  • 이때 변위는 같아야 한다.
    

<페이지 테이블 엔트리>

1. 개요

• 페이지 테이블의 각각의 행을 페이지 테이블 엔트리(PTE)라고 한다.

2. PTE에 담기는 정보

• 페이지 번호
• 프레임 정보
• 유효 비트
  • 현재 해당 페이지에 접근 가능한지 여부를 알려줌
    • 유효 비트가 1이면 메모리에 적재된 페이지, 0이면 적재되지 않은 페이지
    • 유효 비트가 0인 페이지에 접근하려 하면, page fault라는 인터럽트 발생
      -> CPU가 기존 작업 내용 백업
      -> 페이지 폴트 처리 루틴 실행
      -> 페이지 처리 루틴은 원하는 페이지 메모리로 가져온 뒤 유효 비트를 1로 변경
      -> 페이지 폴트를 처리했다면, CPU는 해당 페이지에 접근 가능
• 보호 비트
  • 예를 들어 읽기 전용 페이지같은 경우, 보호 비트를 1로 설정해서 쓰기와 같은 다른 작업을 못하게 한다.
• 참조 비트
  • CPU가 해당 페이지에 접근한 적이 있다면 1, 없다면 0
• 수정 비트 (dirty bit)
  • CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부
  • swaping을 위해서 존재
  • 만약 페이지가 수정된다면, 보조기억장치에도 쓰기 작업을 해야함

<쓰기 시 복사 (Copy on Write)>

1. 개요

• 프로세스를 fork()하면 부모와 같은 내용을 가진 자식 프로세스가 생기므로,
• 프로세스 생성 시간이 지연되고, 메모리가 낭비되는 단점이 있다.

2. 쓰기 시 복사

• fork된 자식 프로세스는 부모 프로세스와 동일한 프레임을 가리키는 것
  • 만약 이때 아무 쓰기 작업도 이루어지지 않으면, 현재 상태를 유지한다.
• 그러나 쓰기 작업을 하게 된다면,
  • 쓰기 작업을 한 페이지는 별도의 공간으로 복제된다.

<계층적 페이징>

1. 개요

• 프로세스 테이블의 크기는 생각보다 작지 않기에, 프로세스를 이루는 모든 PTE에 메모리에 두는 것은 낭비이다.
• 프로세스를 이루는 모든 PTE를 항상 메모리에 유지하지 않는 기법

2. 계층적 페이징

• 페이지 테이블을 페이징하여, 여러 단계의 페이지를 두는 방식
• CPU와 가장 가까이 위치한 페이지 테이블 (outer page table)만 항상 메모리에 유지

3. 페이지 교체와 프레임 할당

• 물리 메모리보다 큰 프로세스를 실행할 수 있지만, 물리 메모리의 크기는 한정되어있다.
• 결과적으로
  • 기존에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보내고, (페이지 교체)
  • 프로세스들에게 적절한 수의 프레임을 할당해야 함! (프레임 할당)

<요구 페이징 (demand paging)>

1. 개요

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

2. 요구 페이징

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

cf) 순수 요구 페이징

• 아무런 페이지도 메모리에 적재하지 않고 실행하는 기법
• 첫번째 명령어를 실행하는 순간부터, 계속해서 페이지 폴트 발생
• 점차적으로 페이지 폴트가 적어진다

3. 요구 페이징이 해결해야 할 문제

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

<페이지 교체>

1. 개요

• 요구 페이징 기법으로 페이지를 적재하다보면 언젠가는 메모리가 가득 찬다.
• 당장 실행에 필요한 페이지를 적재하기 위해 적재된 페이지를 보조 기억장치로 내려야 하는데,
• 이때 어떤 페이지를 내보내야 하는가?

2. 페이지 교체 알고리즘

• 좋은 페이지 알고리즘은?
  • 페이지 폴트가 적은 알고리즘!
  • 페이지 폴트가 발생하는 순간 보조기억장치로 접근해야 하므로 성능이 저하되기 때문에
• 페이지 폴트의 횟수를 알기 위해 페이지 참조열 이용

3. 페이지 참조열 (page reference string)

• CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
• 연속된 페이지를 삭제해야 페이지 폴트를 줄일 수 있다.
  • ex)
    • 2 2 2 3 5 5 5 3 3 7 : 페이지 참조 순서
    • 2 3 5 3 7 : 페이지 참조열

<페이지 교체 알고리즘>

1. FIFO

• 가장 단순한 방식
• 메모리에 가장 먼저 올라온 페이지부터 내리는 방식
• 문제점
  • 프로그램 초기에 적재되었는데, 프로그램 실행 내내 사용될 페이지가 내쫓아진다면 성능면에서 이점이 없다.

2. 2차 기회(second-chance) 페이지 교체 알고리즘

• FIFO의 단점을 보완한 알고리즘
• 동작 방식
  • 참조 비트1
    • CPU가 한 번 참조한 적이 있는 페이지
      -> 오래되긴 했지만, 자주 쓴 것
    • 한번 더 기회를 주기
      -> 참조 비트를 0으로 초기화 하고
      -> 적재 시간을 현재로 바꿈
  • 참조 비트0
    • CPU가 참조한 적이 없는 페이지
    • 내쫓기

3. 최적(Optimal) 페이지 교체 알고리즘

• 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
  • CPU에 의해 참조되는 횟수를 고려
  • 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지!
• 동작 방식

• 문제점
  • 가장 낮은 페이지 폴트율을 보장하기는 하지만,
  • 구현이 어렵다. (예측을 어떻게 할건데?)

4. LRU (Least-Recently-Used) 페이지 교체 알고리즘

• 가장 오래 사용되지 않은 페이지 교체
• 동작 방식

<스래싱>

1. 개요

• 페이지 폴트가 자주 발생하는 이유
  • 좋지 않은 페이지 교체 알고리즘을 사용했기 때문
  • 프로세스가 사용할 수 있는 프레임 자체가 적어서

2. 스래싱 (Thrashing)

• 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
  • 지나치게 많은 페이징 때문
• 동시에 실행되는 프로세스의 수를 아무리 늘려도 CPU 이용률이 높아지지는 않는다.
• 원인
  • 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
• 해결 방안
  • 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고,
  • 프로세스들에게 적절한 프레임을 할당해야함

<프레임 할당>

1. 균등 할당 (equal allocation)

• 가장 단순한 방식
• 모든 프로세스들에게 균등하게 프레임을 할당하는 방식

2. 비례 할당 (proportional allocation)

• 프로세스의 크기에 비례하여 프레임 할당
• 프로세스의 실행 과정을 교려하지 않기 때문에 정적할당 방식이라고 한다.
• 문제점
  • 크기가 큰 프로세스이긴 하지만, 많은 프레임이 필요없을수도..
  • 필요한 프레임 수는 실행해봐야만 알 수 있다.
• 해결방안
  • 프로세스를 실행하는 과정에서 프레임을 결정하는 방식이 필요하다.
    -> 작업 집합 모델 & 페이지 폴드 빈도 기반 방식 (동적 할당 방식)

3. 작업 집합 모델

• 스레싱의 원인이 과도한 페이징 이므로
  • CPU가 특정 시간동안 주로 참조한 페이지 갯수만큼만 프레임을 할당하기
• 프로세스가 일정 기간동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체 방지
  • 작업 집합이란, 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 말한다.
• 작업 집합 구하기
  • 프로세스가 참조한 페이지
  • 시간 간격 필요

4. 페이지 폴트 빈도

• 아래 두가지 가정에서 생긴 아이디어
  • 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
  • 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
• 페이지 폴트율에 상한과 하한선을 정하고, 그 범위 안에서 프레임을 할당해주는 방식