📑 본 글은 <혼공컴운>을 읽고 정리한 글입니다.

1. 연속 메모리 할당

연속 메모리 할당 : 프로세스에 연속적인 메모리 공간을 할당하는 방식

메모리에 연속적으로 프로세스를 할당할 때 고려할 점, 잠재적인 문제를 알아보자

1-1. 스와핑

스와핑
프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 커도 프로세스들을 동시 실행 가능

• 스왑 아웃(swap-out)
  • 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치의 스왑 영역(swap space) 내보낸다.
    • 대기 상태인 프로세스, 오랫동안 사용되지 않은 프로세스 등
• 스왑 인(swap-in)
  • 실행할 프로세스를 메모리로 들여보낸다.
  • 적재되는 주소는 이전의 물리 주소와 다를 수 있다.

1-2. 메모리 할당

비어있는 메모리 공간에 프로세스들을 연속적으로 할당하는 방식

• 최초 적합(first fit)
  • 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 공간을 처음 발견한 곳에 프로세스 배치한다.
  • 검색 최소화, 빠른 할당이 가능하다.
• 최적 적합(best fit)
  • 운영체제가 빈 공간을 모두 검색한 후, 들어갈 수 있는 공간 중 가장 작은 공간에 프로세스 배치한다.
  • 메모리 효율적
• 최악 적합(worst fit)
  • 운영체제가 빈 공간을 모두 검색한 후, 들어갈 수 있는 공간 중 가장 공간에 프로세스 배치한다.

1-3. 외부 단편화

외부 단편화(external fragmentation)

• 연속 메모리 할당의 문제점.
• 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들이 생겨서 메모리가 낭비되는 현상 ⇒ 압축(compaction) : 프로세스를 재배치해서 작은 빈 공간들을 하나의 큰 공간으로 합치는 방식
  • 프로세스 재배치? 오버헤드 크다.

⇒ 가상 메모리 기법 중 페이징 기법으로 해결할 수 있다.

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

연속 메모리 할당의 단점

1. 외부 단편화
2. 물리 메모리보다 큰 프로세스를 실행할 수 없다.

가상 메모리(virtual memory)

• 실행하고자 하는 프로그램의 일부만 메모리에 적재하여 실제 물리 메모리보다 큰 프로세스를 실행할 수 있다.
• 방법1) 페이징 ← 운체 pick!
• 방법2) 세그멘테이션

2-1. 페이징이란

페이징(paging)

• 페이지를 프레임에 할당하는 가상 메모리 관리 기법
• 페이지(Page) : 프로세스의 논리 주소 공간을 자른 단위
• 프레임(Frame) : 프로세스의 물리 주소 공간을 자른 단위, 페이지와 동일한 크기로 자름
• 페이지 아웃(page-out) : swap out in paging system
• 페이지 인(page-in) : swap in in paging system

⇒ 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다.

⇒ 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.

2-2. 페이징 테이블

프로세스를 메모리에 불연속적으로 배치해놓으면, CPU가 다음에 실행할 명령어 위치를 어떻게 암?

페이지 테이블(page table)

• 페이지 번호와 프레임 번호를 짝지어 주는 이정표
• 어떤 페이지가 어떤 프레임에 할당되었는지 알려준다.
• 프로세스가 물리 주소에 불연속적 배치되었지만, 논리 주소에는 연속적으로 배치되도록 함
• CPU는 논리 주소를 그저 순차적으로 실행하면 된다.

내부 단편화(internal fragmentation)

• 페이징 기법의 문제점.
• 페이지 크기보다 작은 애가 저장되면 조금 남은 공간이 낭비됨

페이지 테이블 베이스 레지스터(PTBR : Page table base register)

• 각 프로세스의 페이지 테이블이 적재된 주소 저장
• 프로세스마다 각자의 페이지 테이블을 가지고 있다. 이 테이블들은 메모리에 적재되어 있다.
• PCB에 기록된다.

테이블보러 메모리 접근 & 프레임 보러 메모리 접근

→ 메모리를 2번씩이나 접근?

TLB(Translation Lookaside Buffer)

• CPU 옆 MMU 안에 두는 페이지 테이블의 캐시 메모리
• 참조 지역성에 근거해 페이지 테이블의 일부 내용 저장한다.
• TLB Hit : 페이지 번호가 TLB에 있는 경우
• TLB Miss : 페이지 번호가 TLB에 없는 경우, 메모리 내 페이지 테이블에 접근해야 함

2-3. 페이징에서의 주소 변환

특정 주소에 접근하려면 필요한 정보들

페이징 시스템 논리 주소의 구성

• 페이지 번호
• 변위
  • 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지
• 논리 주소<페이지 번호, 변위> — 페이지 테이블 → 물리 주소<프레임 번호, 변위>

2-4. 페이지 테이블 엔트리

페이지 테이블 엔트리

• 페이지 테이블의 각각의 행들
• 구성 요소
  • 유효 비트(valid bit)
    • 현재 해당 페이지에 접근 가능한지 여부
    • 페이지가 메모리에 있음 → 0 / 페이지가 스왑 영역에 있음 → 1
    • 페이지 폴트(page fault)
      • 유효 비트가 0인 페이지에 접근하려는 경우
      • CPU 기존 작업 백업 → 페이지 폴트 처리 루틴 실행 → 페이지 메모리로 가져옴, 유효 bit = 1→ CPU 해당 페이지에 접근
  • 보호 비트(protection bit)
    • 해당 페이지가 읽고/쓰기 가능한지 알려줌
    • 운체가 관리해줌
    • r(read), w(write), x(execute)
      • 보호 비트 = 110, 읽기 O / 쓰기 O / 실행 X
  • 참조 비트(reference bit)
    • CPU가 이 페이지에 접근한 적이 있는지
  • 수정 비트(modified bit)
    • 해당 페이지에 데이터를 쓴 적이 있는지
    • = Dirty bit
    • 페이지 아웃할 때 수정 사항 반영해야하는지, 그냥 덮어쓰기만 하면 되는지 알아야함

✅ 페이징의 이점 - Copy on write

• 원래 프로세스를 fork하여 동일한 프로세스가 2개로 복제될 때 코드, 데이터 영역도 복제되어 메모리에 적재된다.
• copy on write 방식을 사용하면 자식 프로세스가 부모 프로세스와 동일한 프레임을 가리키게 한다.
• 만약 부모나 자식 중 하나가 페이지에 쓰기 작업을 하면 그 순간 해당 페이지만 별도의 공간으로 복제된다.
• 프로세스 생성 시간을 줄이고, 메모리 공간도 절약할 수 있다.

계층적 페이징(hierarchical paging)

• = 다단계 페이지 테이블
• Outer page : 페이지들을 가리키는 페이지 테이블
• 논리 주소 구성 : 바깥 페이지 번호 | 안쪽 페이지 번호 | 변위
• outer page를 제외하고 메모리에 있을 필요가 없다.
• page fault가 발생했을 경우 메모리 참조 횟수가 많아질 수 있다.

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

내보낼 페이지 선별하는 방법! 프로세스마다 몇 개의 프레임을 주는 게 좋을까?

3-1. 요구 페이징

요구 페이징(demand paging)

• 프로세스를 메모리에 적재할 때 필요한 페이지만 메모리에 올리는 기법
• 순수 요구 페이징
  • 아무런 페이지도 메모리에 적재하지 않고 걍 실행하는 방법
  • 페이지 폴트 계속 냄 → 좀 지나면 괜찮아짐

→ 페이지 교체, 프레임 할당 | 이 2개가 해결되어야 안정적 작동 가능

3-2. 페이지 교체 알고리즘

페이지 교체 알고리즘

• 쫓아낼 페이지를 결정하는 방법
• 좋은 페이지 교체 알고리즘 → page fault를 적게 내는 알고리즘
  • 페이지 폴트 횟수 : 페이지 참조열로 알 수 있삼
    • 페이지 참조열 : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

FIFO 페이지 교체 알고리즘(First In First Out)

• 메모리에 먼저 올라온 페이지부터 내쫓음

  ⇒ 2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)

  • FIFO + 기회 한 번 더 드림
  • 가장 오래된 페이지의 참조 비트가
    • 1이면, 참조 비트를 0으로 만들고 젤 마지막에 add
    • 0이면, 가차없이 제명.

최적 페이지 교체 알고리즘(Optimal page replacement algorithm)

• CPU에 의해 참조되는 횟수를 고려함
• 앞으로의 사용 빈도가 가장 낮은 페이지를 교체한다.
• 가장 낮은 page fault rate을 보장한다. → 다른 알고리즘을 이론상 성능 평가할 때 사용
• 현실적으로 구현하기 어렵다. 미래 예측 가능하셈?

LRU 페이지 교체 알고리즘(Least Recently Used page replacement algorithm)

• 가장 오랫동안 사용되지 않은 페이지를 교체한다.

3-3. 스레싱과 프레임 할당

스레싱(Thrashing)

• 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제
  • 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요 → 성능 저해
• Page Fault가 너무 많이 발생
  • 원인 1) 프로세스가 사용할 수 있는 프레임 부족
  • 원인 2) 나쁜 페이지 교체 알고리즘

멀티프로그래밍의 정도(degree of multiprogramming)

• 메모리에서 동시에 실행되는 프로세스의 수

⇒ 운영체제는 각 프로세스가 필요로 하는 최소한의 프레임 수를 보장해줘야 한다.

프레임 할당 방식

정적 할당 방식 : 프로세스의 크기와 물리 메모리의 크기만을 고려한 방식

• 균등 할당(equal allocation)
  • 총 frame 개수 / 프로세스 개수
• 비례 할당(proportional allocation)
  • 프로세스의 크기에 비례하여 frame을 나눠준다.

동적 할당 방식 : 프로세스의 실행 과정을 고려

• 작업 집합 모델(Working Set model)
  • Working set 만큼만 프레임을 할당한다.
  • Working Set : 실행 중인 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억한다.
  • CPU가 과거에 주로 참조한 페이지를 워킹셋에 포함하면 운체는 그 만큼만 프레임을 할당한다.
• 페이지 폴트 빈도(Page Fault Frequency)
  • 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 안에서만 프레임을 할당한다.
  • 페이지 폴트율을 보면서 프레임 수를 조율한다.
    • 페이지 폴트율이 높다 → 프로세스가 너무 적은 프레임을 가지고 있다.
    • 페이지 폴트율이 낮다 → 프로세스가 너무 많은 프레임을 가지고 있다.