메모리의 주소 공간

• 물리 주소: 메모리 하드웨어가 사용하는 주소
• 가상 주소: CPU 및 실행 중인 프로그램이 사용하는 주소
  • 실행 중인 프로그램 각각에 부여됨
• CPU가 메모리와 상호작용하려면, 가상 주소와 물리 주소 간 변환이 이루어져야 함
  • MMU(메모리관리장치)의 역할

스와핑

• 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고, 실행할 프로세스를 메모리로 들여보내는 기법
  • 스왑 영역: 프로세스들이 쫓겨나는 보조기억장치의 영역
  • 스왑 아웃: 메모리 -> 스왑 영역
  • 스왑 인: 스왑 영역 -> 메모리

연속 메모리 할당

• 메모리 내 빈 공간이 여러 개 있을 때, 프로세스를 어떻게 배치할지?
• 연속 메모리 할당: 메모리 내 프로세스들을 연속된 메모리 공간에 배치
  • 쉽게 말하자면, 메모리를 일정한 단위로 자르지 않고 통째로 배치하는 것
  • 최초 적합(first fit): 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치
  • 최적 적합(best fit): 빈 공간을 모두 검색 -> 적재될 수 있는 가장 작은 공간에 배치

• 문제점 1: 외부 단편화(external fragmentation)
  • 프로세스를 할당하기 어려울 만큼 작은 메모리 공간으로 인해, 메모리가 낭비되는 현상
  • (해결책 1) 압축: 메모리 내 흩어져 있는 빈 공간을 하나로 모으기
    • 단점: 작은 빈 공간을 하나로 모으는 동안, 시스템은 하던 일을 중지해야 함
  • (해결책 2) 가상 메모리와 페이징
• 문제점 2: 물리 메모리 공간보다 큰 프로세스를 실행할 수 없음

페이징

• 실행 프로그램을 일부만 메모리에 적재
• 물리 메모리 크기보다 큰 프로세스를 실행할 수 있기 위함

물리 프레임 / 가상 페이지

• 메모리와 프로세스를 일정한 단위로 자르고, 메모리에 불연속적으로 할당하기 위한 방법
• 메모리의 물리 주소 공간을 프레임 단위, 가상 주소 공간을 페이지 단위로 자른 뒤, 각 페이지를 프레임에 할당하는 기법
  • cf. 프레임과 페이지의 크기는 동일
  • 편의상 물리 프레임을 물리 페이지라 부르는 책들도 있음

페이징에서의 스와핑

• 페이징 사용 시, 프로세스 전체가 스왑 아웃 / 인되지 않음
• 페이지 단위로 스와핑이 이루어짐 -> 페이지 아웃 / 페이지 인으로도 불림
• 프로세스 내 페이지 중, 실행에 필요한 일부 페이지만을 적재
  • 남은 페이지들은 보조기억장치에 남겨 둠

페이지 테이블

• 페이지 테이블: 페이지 번호와 프레임 번호를 짝지어 주는 테이블
• 프로세스가 물리 주소엔 불연속적으로 배치되더라도, CPU가 이용하는 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 사용

• 프로세스마다 각각의 페이지 테이블을 가짐
• 페이지 테이블 역시 메모리에 적재되어 있음
  • CPU 내 PTBR(페이지 테이블 베이스 레지스터)는, 각 프로세스의 페이지 테이블의 주소를 가리킴
  • cf. 프로세스 간 문맥 전환 시 PTBR의 값 역시 변경됨

TLB

• 페이지 테이블 사용 시, 2번의 메모리 접근이 필요해 접근 시간이 늘어남
  • (1)메모리의 페이지 테이블에 접근 -> (2)페이지 테이블에서 확인한 프레임의 접근
• 해결법: CPU에 페이지 테이블의 캐시 메모리, TLB(Translation Lookaside Buffer)를 둠
  • 페이지 테이블 중 최근에 사용된 페이지 위주로 일부 저장
• TLB 히트: 가상 주소에 해당하는 가상 페이지 번호가 TLB에 있는 경우
  • 메모리까지 접근 안 해도 됨
• TLB 미스: 가상 주소에 해당하는 가상 페이지 번호가 TLB에 없는 경우
  • 어쩔 수 없이 메모리 내 페이지 테이블에 접근해야 함

페이징에서의 주소 변환

• 한 페이지 / 프레임은 여러 주소를 포괄함
• 따라서, 특정 주소에 접근하려면 2가지 정보가 필요함
  • (1) 어떤 페이지 / 프레임에 접근하고 싶은지 (페이지/프레임 번호)
  • (2) 주소가 해당 페이지 / 프레임의 시작으로부터 얼마나 떨어져 있는지

가상 주소 -> 물리 주소로의 변환

• 가상 주소는 페이지 번호(page number)와 변위(offset)로 이루어짐
  • e.g., 32비트 주소 -> 첫 $N$비트는 페이지 번호, 나머지 $32-N$비트는 변위
  • (1) 페이지 테이블을 이용해, 페이지 번호가 어느 프레임에 할당되었는지 확인
  • (2) 프레임의 시작 번지에 변위를 더해, 물리 주소를 찾음
• cf. 가상 주소의 $N$비트가 페이지 번호, $32-N$비트가 변위라면, 물리 주소 역시 $N$비트가 프레임 번호, 나머지 $32-N$비트는 변위.
• cf. 가상 주소와 물리 주소의 변위 값은 동일

페이지 테이블 엔트리

• 페이지 테이블의 각 행을 페이지 테이블 엔트리(PTE)라 함
  • 앞서 본 페이지 번호, 프레임 번호가 PTE에 포함됨
  • 이외에도 중요한 정보들이 저장됨

유효 비트 (valid bit)와 페이지 폴트

• 현재 페이지가 메모리에 적재되어 있으면 1
• 페이지가 보조기억장치(스왑 영역)에 있으면 0
• CPU가 유효 비트가 0인 페이지에 접근하려고 하면 -> 페이지 폴트
  • (1) CPU는 기존의 작업 내역을 백업
  • (2) 페이지 폴트 처리 루틴 실행 (하드웨어 인터럽트와 비슷)
  • (3) 루틴은 원하는 페이지를 메모리에 적재한 뒤, 유효 비트를 1로 변경
  • (4) 이후 CPU는 해당 페이지에 접근할 수 있음

다른 비트들

• 보호 비트: 읽기 r, 쓰기 w, 실행 x의 조합
  • 권한이 있으면 1, 없으면 0
  • e.g., 보호 비트가 110이면 읽고 쓰기는 가능, 실행은 불가능
  • e.g., 프로세스 내 코드 영역은 101: 읽기 및 실행은 가능하나, 쓰기는 막아야 함
• 참조 비트: CPU가 페이지에 참조한 적 있는지 나타냄 (있으면 1 없으면 0)
• 수정 비트: 해당 페이지에 데이터를 쓴 적이 있는지 나타냄 (있으면 1 없으면 0)
  • 페이지가 메모리에서 제거될 때, 보조기억장치에 수정된 내용을 갱신해야 할지 결정에 사용
  • 1인 경우, 보조기억장치엔 원래 내용이, 메모리엔 변경된 내용이 저장되어 있음 -> 갱신해야 함
  • 0인 경우, 보조기억장치에서 적재한 이후 변경된 내용이 없음 -> 갱신할 필요 없음

copy on write (쓰기 시 복사)

• fork 시스템 콜 수행 시, 부모 프로세스의 복사본이 자식 프로세스로 만들어짐
• 원칙적으로는, 부모 프로세스의 메모리 영역을 물리 메모리 내 다른 영역에 복제해야 함
  • 하지만 이러면 프로세스 생성 시간이 느려지며, 불필요한 메모리 낭비 발생

• copy on write 방식에선 일단 자식 프로세스는 부모 프로세스와 동일한 프레임을 가리킴
  • 페이지 테이블의 내용을 그대로 복제하기 때문
• 부모, 자식 중 하나가 페이지에 쓰기 작업을 하는 순간, 해당 페이지가 별도의 공간으로 복제됨
• 장점: 프로세스 생성 시간을 줄일 수 있으며, 메모리 공간 절약 가능

계층적 페이징 / 다단계 페이지 테이블

• 프로세스의 크기가 커지면, 프로세스 테이블의 크기도 커짐
• 모든 페이지 테이블 엔트리를 메모리에 두는 것은 공간 낭비
  • 계층적 페이징으로, 모든 PTE를 메모리에 유지하지 않을 수 있음

• 다단계 페이지 테이블
  • 프로세스의 페이지 테이블을, 여러 개의 페이지로 나누어 자름
  • 바깥쪽에 페이지 테이블을 하나 더 두어, 개별 잘린 페이지를 가리키게 함
  • 가장 바깥쪽 페이지 테이블만 항상 메모리에 유지
    • 안쪽 페이지 테이블은, 참조할 때만 메모리에 적재하면 됨
• 논리 주소 역시 바깥 페이지 번호, 안쪽 페이지 번호, 변위의 구성으로 이루어짐
  • 계층은 꼭 2개일 필요는 없음

페이지 교체와 프레임 할당

요구 페이징(demand paging)

• 프로세스를 메모리에 적재할 때, 실행에 필요한 페이지만을 메모리에 적재하는 기법
  • 즉, 모든 페이지를 처음부터 적재하진 않음
• 요구 페이징 과정
  • (1) CPU가 특정 페이지에 접근하는 명령어 실행
  • (2A) 해당 페이지가 현재 메모리에 존재 (유효비트=1) -> CPU는 프레임에 접근
  • (2B) 해당 페이지가 현재 메모리에 없음 (유효비트=0) -> 페이지 폴트
    • 페이지 폴트 처리 루틴: 페이지를 메모리로 적재하고, 유효비트를 1로 설정
    • 이후 (1)로 돌아가 재시도
• 순수 요구 페이징: 실제로 맨 처음엔 아무 페이지도 적재하지 않은 채, 실행만 시도할 수 있음
  • 처음부터 페이지 폴트 발생 -> 어느정도 적재가 이루어진 후부터 페이지 폴트 발생 빈도가 떨어짐

페이지 교체

• 메모리가 가득 찬 상태에서 새로운 페이지를 적재하는 경우, 기존 페이지를 내보내야함
• 내보낼 페이지는 페이지 교체 알고리즘에 의해 결정됨
• 좋은 페이지 교체 알고리즘은, 페이지 폴트를 가장 적게 일으키는 알고리즘

페이지 교체 알고리즘

• FIFO: 메모리에 가장 먼저 올라온 페이지부터 내쫓기
  • 하지만 먼저 올라온 페이지의 사용 빈도가 높을 수 있음
• 최적: 앞으로의 사용 빈도가 가장 낮은 페이지
  • 가장 낮은 페이지 폴트율을 보장하지만, 실제로 앞으로의 사용 빈도를 예측하긴 어려움
• LRU: 가장 오랫동안 사용되지 않은 페이지를 교체
  • 제일 많이 사용되는 방식