[혼자 공부하는 컴퓨터구조+운영체제] Chapter 14 가상 메모리

Chapter 14 가상 메모리

1. 연속 메모리 할당

스와핑/ 최소 적합/ 최적 적합/ 외부 단편화

 

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

스와핑(Swapping)

메모리에 적재된 프로세스 중 현재 실행되지 X 프로세스 존재

ex. 입출력 작업의 요구 -> 대기 상태 된 프로세스/ 오랫동안 사용 X 프로세스

-> 임시로 보조기억장치 일부 영역으로 쫓아내고, 메모리상의 빈 공간에 또 다른 프로세스 적재하여 실행하는 방식

메모리에서 사용 X 일부 프로세스 -> 보조기억장치로/ 실행할 프로세스 -> 메모리로 메모리 관리 기법

• 스왑 영역(swap space): 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
• 스왑 아웃(swap-out): 현재 실행되지 X 프로세스) 메모리 -> 스왑 영역
• 스왑 인(swap-in): 프로세스) 스왑 영역 -> 메모리

스왑 아웃된 프로세스 -> 스왑 인 => 스왑 아웃 전 물리 주소와 다른 주소에 적재될 수 있음

 

프로세스들이 요구하는 메모리 주소 공간의 크기 > 실제 메모리 크기 -> 프로세스 동시 실행 O

ex. 프로세스 A, B, C, D 크기 합 > 메모리의 크기 But, 스와핑 ~> 4개의 프로세스 동시 실행 O

---

메모리 할당

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

• 최초 적합(first fit)
  • 최초로 발견한 적재 가능한 빈 공간에 프로세스 배치
  • 검색 최소화, 빠른 할당 가능
• 최적 적합(best fit)
  • 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스 배치
• 최악 적합(worst fit)
  • 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스 배치

최초/ 최적/ 최악

---

외부 단편화(external fragmentation)

프로세스 -> 연속 메모리 할당(: 메모리에 연속적으로 배치) => 메모리 효율적 사용하는 방법 X

=> (-) 외부 단편화

• 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
• 프로세스 실행, 종료 반복 -> 메모리 사이 사이 빈 공간 생김 -> 큰 프로세스 적재 X => 메모리 낭비

=> (해결) 압축(compaction) = 메모리 조각 모음

• 흩어져 있는 빈 공간 하나로 모으는 방식
• 메모리 내 저장된 프로세스 적당히 배치 -> 흩어져 있는 작은 빈 공간 -> 하나의 큰 빈 공간으로 만듦
• (-) 시스템) 작은 빈 공간 하나로 모으는 동안 하던 일 중지
• (-) 메모리에 있는 내용 옮기는 작업 -> ↑ 오버헤드 야기
• (-) 어떤 프로세스 어떻게 움직여야 오버헤드 최소화하며 압축할 수 있는지 명확한 방법 결정 X

=> (해결) 페이징 기법 - 가상 메모리 기법

---

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

페이징/ 페이지 테이블/ PTBR/ TLB

 

가상 메모리(virtual memory)

• 실행하고자 하는 프로그램을 일부만 메모리에 적재
  -> 실제 물리 메모리 크기보다 더 ↑ 프로세스 실행할 수 있게 하는 기술
• 가상 메모리 관리 기법: 페이징/ 세그멘테이션

연속 메모리 방식에서 외부 단편화가 생긴 이유: 각기 다른 크기의 프로세스 -> 메모리에 연속적으로 할당

=> IF. 메모리와 프로세스 일정한 단위로 자르고, 메모리에 불연속적으로 할당 => 외부 단편화 발생 X

페이징(Paging)

• 프로세스_논리 주소 공간 -> 페이지(page)로 자름
  / 메모리_물리 주소 공간 -> 프레임(frame)으로 자름(= 페이지 크기)
  -> 페이지를 프레임에 할당하는 가상 메모리 관리 기법
• 스와핑 사용 O
  • 프로세스 전체가 스왑 아웃/ 스왑 인 X
  • 페이지 단위로 스왑 아웃/ 스왑 인 O
    
    • 스왑 아웃 = 페이지 아웃(page out): 메모리에 적재될 필요 X 페이지 -> 보조기억장치
    • 스왑 인 = 페이지 인(page in): 실행 필요 O 페이지 -> 메모리
  • = 한 프로세스 실행하기 위해 프로세스 전체가 메모리에 적재될 필요 X
  • 실행에 필요한 일부 페이지 -> 메모리에 적재/ 필요 X 페이지 -> 보조기억장치

---

프로세스가 메모리에 불연속적으로 배치 -> CPU) 순차적으로 실행 X

=> 프로세스를 이루는 페이지 어느 프레임에 적재돼 있는지 다 알지 X = 다음에 실행할 명령어 위치 찾기 어려움

=> (해결) 페이지 테이블

페이지 테이블(page table)

• 페이지 번호 이용 -> 페이지가 적재된 프레임 찾을 수 있음
• 현재 어떤 페이지가 어떤 프레임에 할당되었는지 알려줌
• 프로세스) 물리 주소(실제 메모리 내 주소)에 불연속적 배치 But, 논리 주소(CPU가 바라보는 주소)에 연속적으로 배치
  = 메모리에 분산되어 저장돼 있어도 CPU) 논리 주소 순차적으로 실행

페이징

• 프로세스의 논리 주소 공간 -> 페이지라는 일정한 크기로 자름
• But, 모든 프로세스가 페이지 크기에 맞게 잘리는 것 X = 프로세스 크기가 페이지의 배수 X
• 외부 단편화 문제 해결 But, 내부 단편화(internal fragmentation) 문제 야기할 수 O
  • 하나의 페이지 크기보다 작은 크기로 발생 => 하나의 페이지 크기 ↓ -> 발생하는 내부 단편화 크기 ↓
  • But, 하나의 페이지 너무 작게 설정 -> 페이지 테이블 크기 ↑ => 페이지 테이블이 차지하는 공간 낭비
    => 페이지 크기 조정 중요

페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register)

CPU 내에서 각 프로세스의 페이지 테이블이 적재된 주소 가리킴

프로세스 A 실행) PTBR은 프로세스 A 페이지 테이블 가리킴
=> CPU) 프로세스 A의 테이블 ~> 프로세스 A의 페이지가 적재된 프레임 알 수 있음

프로세스들의 페이지 테이블 정보 -> 각 프로세스의 PCB에 기록

/ 프로세스의 문맥 교환 일어날 때 다른 레지스터와 함께 변경

 

=> (-) 페이지 테이블을 메모리에 두면 메모리 접근 시간 2배로 ↑

(메모리에 있는 페이지 테이블 보기 위해 1번 + 프레임에 접근하기 위해 1번)

=> (해결) TLB(Translation Lookaside Buffer)

• 페이지 테이블의 캐시 메모리 역할 수행하기 위해 페이지 테이블 일부 내용 저장
• 참조 지역성에 근거해 최근에 사용된 페이지 위주로 가져와 저장

• TLB 히트(TLB hit)
  • CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우
  • 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요 X -> 메모리 접근 1번
• TLB 미스(TLB miss)
  • 페이지 번호가 TLB에 X -> 페이지가 적재된 프레임 알기 위해 메모리 내의 페이지 테이블로 접근

---

페이징에서의 주소 변환

특정 주소에 접근하기 위해 필요한 2가지 정보

• 어떤 페이지/ 프레임에 접근하고 싶은지
• 접근하려는 주소가 그 페이지/ 프레임으로부터 얼마나 떨어져 있는지

모든 논리 주소 = 페이지 번호(page number) + 변위(offset)

• ex. CPU) 32비트 주소 내보냄 -> N비트: 페이지 번호 + 32 - N비트: 변위
• 페이지 번호
  • 접근하고자 하는 페이지 번호
  • 페이지가 어떤 프레임에 할당 되었는지 알 수 있음
• 변위
  • 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지 알기 위한 정보
• CPU -논리 주소-> 페이지 테이블 -물리 주소-> 메모리
  • 논리 주소 <페이지 번호, 변위> ~페이지 테이블~> 물리 주소 <프레임 번호, 변위>

CPU가 5번 페이지, 변위 2라는 논리 주소 (<5, 2>)에 접근하고 싶어할 때 접근할 물리 주소?
5번 페이지 -> 1번 프레임 => 1번 프레임, 변위 2
1번 프레임 -> 8번지부터 시작 => 10번지에 접근

---

페이지 테이블 엔트리(PTE; Page Table Entry)

페이지 테이블의 각각의 행들

• 유효 비트(valid bit)
  • 현재 해당 페이지에 접근 가능한지 여부 알려줌
  • 페이지 테이블 엔트리에서 프레임 번호 다음으로 중요한 정보
  • 메모리에 적재 X: 0/ 적재: 1
  • 현재 페이지가 메모리에 적재돼 있는지 여부 알려주는 비트/ 페이지가 메모리 내에 적재 X
    -> 페이지 폴트(page fault): 예외 발생
    • 일부 페이지 보조기억장치(스왑 영역)에 있는 경우 O
    • 폴트 처리하는 과정 (~= 하드웨어 인터럽트 처리 과정)
      1. CPU) 기존의 작업 내역 백업
      2. 페이지 폴트 처리 루틴 실행
      3. 페이지 처리 루틴) 원하는 페이지 -> 메모리로 가져온 뒤 유효 비트를 1로 변경
      4. 페이지 폴트 처리 -> CPU) 해당 페이지에 접근할 수 있게 됨
• 보호 비트(protection bit)
  • 페이지 보호 기능을 위해 존재하는 비트
  • 페이지에 접근할 권한을 제한하여 페이지 보호
  • 해당 페이지가 읽기/쓰기 모두 가능한 페이지인지, 읽기만 가능한 페이지인지 나타냄
  • 읽기만: 0/ 읽기와 쓰기: 1
  • 읽기 r(Read)/ 쓰기 w(Write)/ 실행 x(eXecute) 
    • 보호 비트 100: r 1/ w 0/ x 0 => 읽기만 가능
    • 보호 비트 110 => 읽고 쓰기만 가능, 실행 불가능
    • 보호 비트 111 => 읽기, 쓰기, 실행 모두 가능
• 참조 비트(reference bit)
  • CPU가 이 페이지에 접근한 적 있는지 여부 알려줌
  • 적재 이후 한 번도 읽거나 쓴 적 X 페이지: 0/ CPU가 읽거나 쓴 페이지: 1
• 수정 비트(modified bit) = 더티 비트(dirty bit)
  • 해당 페이지에 데이터를 쓴 적 있는지 없는지 수정 여부 알려줌
  • 변경된 적 X 페이지(한 번도 접근한 적 없거나 읽기만 했던 페이지): 0/ 변경된 적 있는 페이지: 1
  • 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요 없는지 판단
  • CPU) 한 번도 접근 X or 읽기만 한 페이지
    
    • -> 보조기억장치에 저장된 해당 페이지의 내용 == 메모리에 저장된 페이지의 내용
      => 한 번도 수정된 적 X 페이지가 스왑 아웃 -> 새로 적재된 페이지로 덮어쓰면 됨
  • But, CPU) 쓰기 작업 수행한 페이지(수정 비트 1)
    • 보조기억장치에 저장된 해당 페이지의 내용 != 메모리에 저장된 페이지의 내용
      => 변경된 값을 보조기억장치에 기록하는 작업 추가

---

+페이징의 이점 - 쓰기 시 복사(copy on write)

페이징이 제공하는 이점

• 외부 단편화 문제 해결
• 프로세스 간 페이지 공유

(10장)

• 프로세스 fork -> 동일한 프로세스 2개 복제 -> 코드 및 데이터 영역 비롯한 모든 자원 복재 돼 메모리에 저장 
• 프로세스 통째로 메모리에 중복 저장 X 프로세스끼리 자원 공유하지 않는 방법 O

운영체제) fork 시스템 호출 -> 부모 프로세스의 복사본 -> 자식 프로세스로서 만들어짐

새롭게 생성된 자식 프로세스의 코드 및 데이터 영역의 메모리 공간 != 부모 프로세스가 적재된 메모리 공간

프로세스 간에는 기본적으로 자원 공유 X

부모 프로세스의 메모리 영역 -> 다른 영역에 자식 프로세스로서 복사,

각 프로세스의 페이지 테이블 -> 자신의 고유한 페이지가 할당된 프레임 가리킴

=> (-) 메모리 낭비

 

쓰기 시 복사: 부모 프로세스와 동일한 자식 프로세스 생성 -> 자식 프로세스가 부모 프로세스와 동일

한 프레임 가리킴

부모 프로세스의 메모리 공간 복사 X 동일한 코드 및 데이터 영역 가리킴

 

 

---

프로세스의 크기 ↑ -> 프로세스 테이블 크기 ↑

=> 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것 -> 메모리 낭비

+계층적 페이징(hierarchical paging) = 다단계 페이지 테이블(multilevel page table) 기법

• 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
• 프로세스의 페이지 테이블 -> 여러 개의 페이지로 자름
  -> 바깥쪽에 페이지 테이블 하나 더 두어 잘린 페이지 테이블의 페이지 가리키게 하는 방식
• 모든 페이지 테이블 항상 메모리에 유지 X, 보조기억장치 O 참조 필요 시 메모리에 적재

논리 주소 = 바깥 페이지 번호 + 안쪽 페이지 번호 + 변위 

• 바깥 페이지 번호
  • CPU와 근접한 곳에 위치한(바깥에 위치한) 페이지 테이블 엔트리 가리킴
   
• 안족 페이지 번호
  • 첫 번째 페이지 테이블 바깥에 위치한 두 번째 테이블 = 페이지 테이블의 페이지 번호 가리킴
• 주소 변환
  1. 바깥 페이지 번호 ~> 페이지 테이블의 페이지 찾기
  2. 페이지 테이블의 페이지 ~> 프레임 번호 찾고 변위 더함으로서 물리 주소 얻기

페이지 테이블의 계층 ↑ -> 페이지 폴트 발생 시 메모리 참조 횟수 ↑

---

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

요구 페이징/ 페이지 교체 알고리즘/ 스래싱/ 프레임 할당

요구 페이징(demand paging)

• 필요한 페이지만을 메모리에 적재하는 기법
  • 프로세스를 메모리에 적재할 때 처음부터 모든 페이지 적재 X 
• 실행에 요구되는 페이지만 적재하는 기법

1. CPU) 특정 페이지에 접근하는 명령어 실행
2. 해당 페이지가 현재 메모리에 O 경우(유효 비트 1) -> CPU) 페이지가 적재된 프레임에 접근
3. 해당 페이지가 현재 메모리에 X 경우(유효 비트 0) -> 페이지 폴트 발생
4. 페이지 폴트 처리 루틴: 해당 페이지 -> 메모리로 적재/ 유효 비트 1로 설정
5. 다시 1번 수행

순수 요구 페이징(pure demand paging)

• 아무런 페이지도 메모리에 적재 X 무작정 실행부터
• 프로세스의 첫 명령어 실행하는 순간부터 페이지 폴트 계속 발생
• 실행에 필요한 페이지가 어느 정도 적재된 이후 -> 페이지 폴트 발생 빈도 ↓

요구 페이징 안정적으로 작동하기 위한 조건 2개

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

요구 페이징 기법으로 페이지 적재 -> 메모리에 가득 참

-> 당장 실행에 필요한 페이지 적재 -> 메모리에 적재된 페이지 -> 보조기억장치로 내보내야 함

=> 어떤 페이지를 내보내는 것이 최선인지 결정하는 방법: 페이지 교체 알고리즘

---

페이지 교체 알고리즘

• FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm)
  • 메모리에 가장 먼저 들어온 페이지부터 내쫓는 방식
  • 오래 머물렀다면 나가라
  • (+) 아이디와 구현 간단
  • (-) 프로그램 실행 초기에 적재된 페이지 중 실행 내내 사용될 내용 포함하고 있을 수 있음
• 최적 페이지 교체 알고리즘(Optional Page Replacement Algorithm)
  • CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
  • 사용 빈도 가장 ↓ 페이지를 교체하는 알고리즘
    • 메모리에 오랫동안 남아야 할 페이지 = 자주 사용될 페이지
    • 메모리에 없어도 될 페이지 = 오랫동안 사용되지 않을 페이지
  • (-) 실제 구현 어려움 = 앞으로 오랫동안 사용되지 않을 페이지 예측 어려움
    => 이론상 성능 평가 목적으로 사용
    • 실행했을 때 발생하는 페이지 폴트 횟수 -> 페이지 폴트의 하한선
      얼만큼 폴트 발생하느냐 ~> 페이지 교체 알고리즘 평가
• LRU 페이지 교체 알고리즘(Least Recently Used Page Replacement Algorithm)
  • 가장 오랫동안 사용되지 않은 페이지 교체하는 알고리즘
    • 최근에 사용되지 않을 페이지는 앞으로도 사용되지 않을 것

 

---

나쁜 페이지 알고리즘/ (근본적인 이유) 프로세스가 사용할 수 있는 프레임 수 ↓ -> 페이지 폴트 발생

스래싱(thrashing)

• 프로세스가 실제 실행되는 시간 < 페이징에 시간 소요 -> 성능 저해되는 문제
• 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제

• CPU 이용률이 멀티 프로그래밍의 정도에 비례해서 증가하는 것 X
  멀티프로그래밍의 정도(degree of multiprogramming): 메모리에서 동시 실행되는 프로세스 수
  
  • ↑ -> 현재 메모리에 ↑ 프로세스 동시 실행 중
  • ↓ -> 현재 메모리에 ↓ 프로세스 동시 실행 중
• 각 프로세스가 필요로 하는 최소한의 프레임 수 보장 X -> 스래싱 발생
  => 각 프로세스 무리 없이 실행하기 위한 최소한의 프레임 수 파악
  / 프로세스에 적절한 수만큼 프레임 할당해 줄 수 있어야 함

프레임 할당 방식

• 정적 할당 방식: 프로세스 실행 과정 고려 X 단순히 프로세스 크기, 물리 메모리 크기만 고려
  • 균등 할당(equal allocation): 모든 프로세스에 동일한 프레임을 배분
  • 비례 할당(proportional allocation): 프로세스 크기에 따라 프레임을 배분
• 동적 할당 방식: 프로세스의 실행 -> 할당할 프레임 수 결정
  • 작업 집합 모델(working set model)
    • 작업 집합의 크기만큼만 프레임 할당
  • 페이지 폴트 빈도(PFF; Page-Fault Frequency)
    • 페이지 폴트율에 상한선과 하한선 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식

작업 집합(working set): 실행 중인 프로세스가 일정 시간 동안 참조한 페이지 집합

---

출처

[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제