혼자 공부하는 컴퓨터 구조 + 운영체제 Chapter 14

안녕하세요! 제이덥입니다~ 저는 학부 때 공부했던 CS 기초 내용을 Wrap-Up 하기 위해 혼공학습단 11기 활동을 진행해왔는데 이제 6주차로 마지막이네요. 개발 도서를 개발이나 프로젝트를 할 때 참고하기 위해 봤었지, 개인적으로 이렇게 오랜 기간 동안 나눠서 공부해본건 처음이었는데요. 주마다 일정 부분 나눠서 공부하니 지식을 쌓아가는 느낌이 들어서 좋았고, 이외에도 여러 관점에서 많은 것을 배우고 성장할 수 있었던 것 같습니다.
이번 포스팅에서는 Chapter 14 가상메모리에 대해서 다룹니다. 지식과 논리를 잘 결합해야 되는 과목이라 어려운 만큼 면접 질문에서 자주 등장합니다. 스와핑, 페이징, 페이지 교체 알고리즘 등의 개념과 어떻게 구현이 되는지 잘 살펴보시면 좋을 것 같습니다.
해당 도서는 제가 직접 구매하여 글을 작성한 것이며, 혼공단 11기 활동의 일환으로 학습 내용에 대한 공유 글을 작성하게되었음을 알려드립니다. 도서에 대한 자세한 내용과 활동에 대한 내용을 알고 싶은 분들은 아래 Reference에서 확인해주세요~

Chapter 14. 가상메모리

1️⃣ 연속 메모리 할당

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

• 스와핑(swappping)
  스와핑 개념(혼자 공부하는 컴퓨터 구조 + 운영체제)
  • 스와핑(swapping)의 정의 : 메모리에 적재된 프로세스 들 중 현재 실행되지 않는 프로세스를 임시로 보조기억장치의 일부 영역을 쫓아내고 생긴 빈 메모리 공간을 다른 프로세스로 적재하는 관리 방식
    • ex : 입출력 작업의 요구로 대기 상태가 된 프로세스
  • 스왑영역(swap space) : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
  • 스왑 아웃(swap-out) : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
  • 스왑 인(swap-in) : 스왑 영역에 있던 프로세스가 메모리에 다시 적재되는 것
    • 참고 : 스왑 아웃 되었던 프로세스가 스왑인이 될 때 적재되는 물리주소는 이전 주소와 다를 수 있음
  • 스와핑의 장점
    • 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시에 실행가능
      

      

      내 MAC에서 스와핑이 일어나는 모습 상당히 빈번하게 일어나는 것을 알 수 있다

• 메모리 할당
  • 프로세스는 메모리 내 빈 공간에 적재
  • 비어 있는 메모리 공간에 연속적으로 할당하는 대표적인 방식 3가지: 최초 적합, 최적 적합, 최악 적합
  • 최초 적합, 최적 적합, 최악 적합의 예는 모두 다음과 같은 상황을 가정
    • 적재해야되는 프로세스의 크기 : 20MB
    • 메모리의 사용자 영역: 200MB
    • 프로세스를 적재할 수 있는 빈 공간은 3곳 : 빈공간 A, B, C (하단 그림 참고)
  • 최초 적합(first fit)
    • 정의 : 최초로 발견한 적재 가능한 빈공간에 프로세스를 배치
    • 예시 설명 : 운영체제가 A→B→C를 순서대로 순회하며 프로세스가 적재될 수 있는 공간을 찾았을 때, 즉 메모리 빈공간 A에 프로세스 적재
      

      

      최초 적합(first fit)

  • 최적 적합(best fit)
    • 정의 : 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스 배치
    • 예시 설명 : 빈 공간 중에서 2프로세스가 적재될 수 있는 공간은 20MB보다 큼으로 빈 공간 A에 적재가 불가능하며. 빈 공간 B, C중 가장 작은 빈 공간인 C(20MB)에 프로세스 적재
      

      

      최적 적합(best fit)

  • 최초 적합(worst fit)
    • 정의 : 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
    • 예시 설명 : 빈 공간 중에서 2프로세스가 적재될 수 있는 공간은 20MB보다 큼으로 빈 공간 A에 적재가 불가능하며. 빈 공간 B, C중 가장 큰 빈 공간인 B(60MB)에 프로세스 적재
      

      

      최악 적합(worst fit)

• 외부 단편화(external fragementation)
  
  • 연속 메모리 할당은 효율적인 메모리 할당 방식이 아님 → 외부 단편화 문제를 야기
  • 외부 단편화(external fragmentation)의 정의 : 프로세스들이 실행되고 종료되는 과정에서 메모리 사이에 빈 공간이 생기는데, 이 공간들이 프로세스들을 할당하기 어려울 만큼 작아 메모리가 낭비되는 현상
    • ex) 빈 공간 10MB, 빈공간 20MB가 나누어져 있으면 30MB 만큼 메모리가 비어있어도 30MB 크기의 프로세스를 할당하지 못함
  • 실제 컴퓨터는 메모리 용량도 크고 적재되는 프로세스가 많기 때문에 이는 꼭 해결해야하는 문제임
  • 외부 단편화 해결방안 :
    1. 암축(compression) : 프로세스를 재배치 시켜 흩어져 있는 빈 공간들을 하나의 큰 빈 공간으로 만드는 방식
       • 단점 :② : 메모리에 있는 프로세스들을 재배치하는 작업에서 큰 오버헤드 발생
       • ③ : 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는 지에 대한 방법론이 명확하지 않음
       • ① : 작은 빈 공간들을 하나로 모으는 동안(프로세스 재배치를 하는 동안) 하던 작업을 중지
    2. 페이징 기법 : 오늘 날까지 널리 사용되는 기법으로 논리 주소 공간을 페이지(page)라는 일정한 단위로 자르고, 메모리 물리 주소를 프레임이라는 동일한 크기의 일정한 단위로 자른뒤 페이지를 프레임에 할당하는 기법.

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

• 페이징(paging)
  
  • 도입 배경 :
    1. 외부 단편화
    2. 물리 메모리보다 큰 프로세스를 실행할 수 없음
    3. ex) 4GB 메모리는 4GB보다 큰 프로그램을 실행할 수 없음
  • 가상 메모리(virtual memory) : 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
    • 구현 방법 : 세그멘테이션과 페이징
  • 페이징 정의 : 프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임으로 자른뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법
    • 페이지(page) : 프로세스의 논리 주소 공간을 자르는 일정한 단위
    • 프레임(frame) : 메모리 물리 주소 공간을 자르는 일정한 단위
  • 페이징에서 스와핑
    • 페이징에서 스와핑을 프로세스 단위로 스왑 아웃/스왑 인이 되는 것이 아닌 페이지 단위로 스와핑이 일어남
    • 페이지 아웃(page out): 메모리에 적재될 필요가 없는 페이지들이 메모리에서 보조기억장치로 쫓겨 나는 것
    • 페이지 인(page in): 실행에 필요한 페이지들이 메모리로 적재되는 것
    • 반드시 프로세스의 모든 페이지가 메모리에 적재될 필요가 없으며, 실행에 필요한 페이지만 적재가 되면 됨 ⇒ 실행에 필요하지 않은 페이지를 보조기억장치에 저장함으로써 메모리보다 더 큰 프로세스를 실행할 수 있게 됨
• 페이지 테이블(page table)
  
  • 도입 배경 : 프로세스가 메모리에 불연속적으로 배치되어 있으면, CPU는 어떤 페이지가 어느 프레임에 적재되어있는지 모두 기억할 수 없으므로 순차적으로 실행할 수 없음
  • 해결방법 : 물리 주소가 불연속적으로 배치되더라도 논리주소에는 연속적으로 배치 될 수 있도록 페이지 테이블(page table)을 이용
  • 페이지 테이블(page table) : 페이지 번호와 프레임 번호를 맵핑시켜주는 일종의 자료구조
    • 프로세스마다 프로세스 테이블을 가지고 있음 ⇒ CPU 내의 페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register)가 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있음
  • TLB(Translation Lookside Buffer)
    • 도입 배경
      • 페이지 테이블을 메모리에 두개되면 메모리 접근 시간이 두배로 늘어나는 오버헤드 발생
    • TLB 구현 방법:
      • CPU 곁에(일반적으로 MMU)내에 페이지 테이블 캐시 메모리를 둠.
      • 페이지 테이블의 일부 내용을 저장
      • 참조 지역성(locality)에 근거해 최근에 사용된 페이지를 위주로 저장
    • TLB 히트(TLB hit)
      • 논리 주소에 대한 페이지 번호가 TLB에 있는 경우로, 메모리 접근을 할 필요 X
    • TLB 미스(TLB miss)
      • 논리 주소에 대한 페이지 번호가 TLB에 없는 경우로, 메모리에 추가접근이 필요
• 페이징에서의 주소변환
  • 페이지 주소가 가지고 있어야 하는 정보 :
    • 어떤 페이지 혹은 프레임에 접근하고 싶은지
    • 접근하려는 주소가 그 페이지 혹은 프레임에서 얼마나 떨어져있는지
  • 페이지 주소의 구성 :
    • 페이지 번호(page number) : 접근하고자 하는 페이지 번호. 어떤 프레임이 할당되어 있는지 알 수 있음
    • 변위(offset) : 프레임이 시작 번지로부터 얼마만큼 떨어져 있는지
• 페이지 테이블 엔트리(PTE: Page Table entry)
  • 페이지 테이블 엔트리란?
    • 페이지 테이블의 각각의 행을 말함
    • 페이지 번호, 변위 말고도 여러 정보를 함께 저장
  • 페이지 테이블 엔트리에 저장되는 정보 :
    • 유효비트(valid bit) : 현재 페이지에 접근 가능한지를 알려주며 메모리에 적재되어 있으면 1, 아니면 0의 값을 가짐
      • 0일경우 페이지 폴트(page fault) 발생
        • 하드웨어 인터럽트를 처리하는 것처럼 'CPU 작업 백업 →페이지 폴트 처리 루틴 실행 → 메모리 적재' → 유효 비트 변경 과정으로 진행함
    • 보호 비트(protection bit) :
      • 페이지 보호 기능을 하는 비트로, 읽고,쓰고, 실행가능한지 알려줌.
      • 가능하면 1로, 불가능하면 0으로 나타냄.
      • 복잡한 방식으로는 읽기(r), 쓰기(w), 실행(x) 순으로 세개의 비트로 파일 권한을 나타냄
        • ex) 111 → 읽고 쓰고 실행이 모두 가능함
    • 참조 비트(reference bit) : CPU가 이 페이지에 접근한 적이 있는지 여부를 나타냄. 읽거나 쓴 페이지는 1, 적재 이후 사용하지 않은 페이지는 0으로 유지
    • 수정/더티 비트(modified/dirty bit) : 해당 페이지의 데이터의 변경이 있느니 알려주는 비트로 변경된적이 있으면 1, 변경된 적이 없으면 0 ⇒ 주기억장치는 전원이 종료되면 데이터를 잃게 됨으로 보조기억장치에 저장하기 위해 존재
• 내부 단편화(internal fragmentation)
  • 페이징을 사용할 때 발생할 수 있는 문제를 말하고, 프로세스 크기가 페이지의 배수가 아닐 때 할당된 페이지의 전체를 사용하지 않아 메모리 낭비가 발생할 경우
    • ex) 프로세스의 크기가 108KB이고 페이지가 10KB라면, 마지막 페이지의 10KB에서 8KB만 사용하므로 2KB의 메모리 낭비 발생
    • 페이지보다 작은 크기로 발생
  • 페이지의 크기를 적절한 사이즈로 조정하는 것이 중요
    • 페이지의 크기가 작으면 ⇒ 내부 단편화의 크기가 작아짐 ⇒ 메모리 낭비 감소 ⇒ 페이지 테이블 크기 증가 ⇒ 페이지 테이블이 차지하는 공간 낭비
    • 페이지 크기가 크면 ⇒ 내부 단편화 크기가 커짐

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

한정된 메모리를 효율적으로 이용하기 위해 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 하고, 불필요한 페이지를 내보내야 함 ⇒ 요구 페이징 + 페이징 교체 알고리즘 + 프레임 할당으로 이를 구현

• 요구 페이징(demand paging)
  • 요구 페이징의 정의 : 프로세스를 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만 적재하는 기법 ⇒ 실행에 요구되는 페이지만 적재
  • 작동 방식 :
    1. CPU가 특정 페이지에 접근하는 명령어 실행
    2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트 1) CPU는 페이지가 적재된 프레임에 접근
    3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트 0) 페이지 폴트 발생
    4. 페이지 폴트 처리 루틴을 통해 메모리를 적재하고 유효 비트 1로 설정
    5. 1~4 반복
  • 순수 요구 페이징(pure demand paging) :
    • 메모리에 적재하지 않은 채 실행하는 방법으로, 초기에 무수히 많은 페이지 폴트가 발생하지만 어느정도 메모리에 적재된 이후로 페이지 폴트 발생 빈도가 감소됨
  • 위와 같은 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당이 원활하게 이루어져야 함
• 페이징 교체 알고리즘
  • 페이징 교체 알고리즘 정의 : 페이지를 적재하다보면 언젠가 메모리가 가득 차게 되는데, 이 때 어떤 페이지를 내보내야 할지 정하는 알고리즘
  • 좋은 페이지 교체 알고리즘이란? 페이지 폴트를 일으키면 보조 기억창지로로부터 필요한 페이지를 메모리로 가져와야 하는 오버헤드가 발생하기 때문에 페이지 폴트를 가장 적게 일으키는 알고리즘이 좋은 페이지 교체 알고리즘으로 볼 수 있음
  • 페이지 교체 알고리즘을 작성하기 위해 알아야할 필수 개념
    • 페이지 폴트 횟수
    • 페이지 참조열(page reference string) : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
      • ex) 2 2 2 3 5 5 3 7 → 2 3 5 3 7
      • 연속된 페이지를 생략하는 이유 : 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문에 연산에서 제외
  • 페이징 알고리즘의 종류
    • FIFO 페이지 알고리즘(First-In First-Out Page Replacement Algorithm)
      • 정의 : 가장 먼저 올라온 페이지를 내쫓는 방식
      • 장점 : 아이디어와 구현이 간단
      • 단점 : 실행 초기에 실행되었던 페이지 중에서 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있으므로 효율적인 방법이 아닐 수도 있음
    • 최적 페이지 알고리즘(Optimal Page Replacement Algorithm)
      • 정의 : 사용 빈도가 가장 낮은 페이지를 내보내는 방식
      • 장점 : 페이지 폴트 빈도가 다른 교체 알고리즘에 비해 가장 낮음
      • 단점 : 어떤 페이지를 자주 사용할지 자주 사용하지 않을지 알기 어려움으로 실제 구현 방법이 어려움
      • 이용 : 따라서 페이지 폴트의 하한선으로 간주하여 페이지 교체 알고리즘을 평가하기 위한 메트릭(지표)로 사용
    • LRU 페이지 알고리즘(LRU: Least Recently Used Page Replacement Algorithm)
      • 정의 : 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 아이디어를 토대로 가장 오랫동안 사용되지 않은 페이지를 내보내느 방식
      • 장점 : FIFO 알고리즘과 비교해서 페이지 폴트가 일어날 가능성이 적음
      • 단점 : 최적 페이지 알고리즘과 비교해서 구현이 쉬움
• 스래싱과 프레임 할당
  • 스래싱(thrashing)이란?
    • 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 말함
  • 프레임 할당 방식
    • 균등 할당(equal allocation)
      • 모든 프로세스를 균등하게 프레임을 제공함
      • 단점 : 실행되는 프로세스들의 크기가 다른데 동일한 프레임 수를 할당하는 것은 비합리적
    • 비례 할당(proportional allocation)
      • 프로세스 크기에 따라 프레임을 배분
      • 단점 : 프로세스의 크기가 클지라도 막상 실행해보니 많은 프레임을 필요로 하지 않는 경우도 있고, 반대의 경우도 존재하기 때문에 비합리적
    • 프레임 배분 방식
      • 작업 집합 모델(working set model)
        • 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 교체를 방지
      • 페이지 폴트 빈도(PFF: Page Fault Frequency)
        • 페이지 폴트율 기반 프레임 할당은 페이지 폴트율에 상한선과 하한선을 정하고 내부 범위안에서만 프레임을 할당하는 방식

Reference :

• 혼자 공부하는 컴퓨터구조 + 운영체제
• 혼공학습단 11기 활동
• 외부 단편화 블로그 글