6.1 가상 메모리 (Virtual Storage) & Paging

김민우·2022년 6월 4일
0

운영체제

목록 보기
10/14
post-custom-banner

Virtual Storage (Memory)

  • Non-continuous allocation
  • 사용자 프로그램을 여러 개의 block으로 분할
  • 실행 시, 필요한 block들만 메모리에 적재
    - 나머지 block 들은 swap device에 존재
  • 기법들
    1. Paging System
    2. Segmentation system
    3. Hybird paging/segmentation system

allocation을 하게 될 경우 address mapping이라는 개념이 따라옴

Address Mapping

  • Continuous allocation
    - Relative address (상대 주소) : 프로그램의 시작 주소를 0으로 가정한 주소
    - Relocation (재배치) : 메모리 할당 후, 할당된 주소에 따라 상대 주소들을 조정하는 작업

❗ Non-continuous allocation

  • Virtual address (가상 주소)
    - Logical address
    - 연속된 메모리 할당을 가정한 주소
  • Real address (실제 주소)
    - 실제 메모리에 적재된 주소
  • Address mapping
    - Virtual address -> real address
    - 가상 주소를 물리 주소로 바꿔 주는 것을 말함

  • 사용자/프로세스는 실행 프로그램 전체가 메모리에 연속적으로 적재되었다고 가정하고 실행 할 수 있음

Block Mapping

  • 사용자 프로그램을 block 단위로 분할/관리
    - 각 block에 대한 address mapping 정보 유지
  • Virtual address : v = (b,d)
    - b = block number
    - d = displacement(offset) in a block
  • Block map table (BMT)
    - Address mapping 정보 관리
    • kernel 공간에 프로세스마다 하나의 bmt를 가짐
    • Residence bit : 해당 블록이 메모리에 적재되었는지 여부 (0/1)

Block Mapping 실행 순서

  1. 프로세스의 BMT에 접근
  2. BMT에서 block b에 대한 항목(entry)를 찾음
  3. Residence bit 검사
    • Residence bit = 0인 경우, (메모리에 안올라간 경우)
      swap device에서 해당 블록을 메모리로 가져 와서 BTM 업데이트 후 다음 단계 수행
    • Residence bit = 1인 경우,
      BMT에서 b에 대한 real address 값 a 확인
  4. 실제 주소 r 계산 (r = a + d)
  5. r을 이용하여 메모리에 접근

대부분의 운영체제는 공간 관리 문제를 해결할 때 두 가지 중 하나를 사용한다.
첫 번째 방법으로는 가변 크기의 조각들로 분할하는 Segmentation이다.
그러나, 이 방법은 공간을 다양한 크기의 Chunk로 분할할 때 공간 자체가 단편화 될 수 있고, 할당은 점점 더 어려워진다.

두 번째 방법인 공간을 동일 크기의 조각으로 분할하는 페이징을 고려해 볼 필요가 있다.
프로세스의 주소 공간을 몇 개의 가변 크기의 논리 세그먼트 (ex. code, heap, stack)로 나누는 것이 아닌 고정 크기의 단위로 나눈다.
이 각각의 고정 크기 단위를 페이지(page) 라고 부르며, 물리 메모리도 페이지 프레임(page frame) 이라고 불리는 고정 크기의 슬롯의 배열이라고 생각한다.
이 프레임 각각은 하나의 가상 메모리 페이지를 저장할 수 있다.
그렇다면, 페이지를 사용하여 어떻게 메모리를 가상화할 수 있을까?

Virtual Storage Methods

📖 Paging System

  • Paging System이란 프로그램을 같은 크기의 블록으로 분할 (Pages)한 것
  • Page : 프로그램의 분할된 block
    - Window의 page size는 4KB지만, Linux 같은 경우엔 자유롭게 바꿀 수도 있음
  • Page frame : 메모리의 분할 영역, Page와 같은 크기로 분할

Paging System의 특징

  • 논리적 분할이 아닌 크기에 따른 분할
    - Segmentation에 비해 Page 공유 및 보호 과정이 복잡함
    - Segmentation보다 Simple and Efficient
    - 외부 단편화는 없으나 내부 단편화 발생 가능이 있음

페이징은 이전 방식에 비해 많은 장점을 가지고 있다.
그 중 가장 큰 장점은 유연성 일 것이다.
페이징을 사용하면 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 예를 들어, 힙과 스택이 어느 방향으로 커지는가, 어떻게 사용되는가에 대한 가정을 하지 않아도 된다.

또 다른 장점은 페이징이 제공하는 빈 공간 관리의 단순함 이다.
예를 들어, 운영체제가 우리의 작은 64바이트 주소 공간을 8페이지 물리 메모리에 배치하기를 원한다고 할 때, 운영체제는 비어 있는 4개의 페이지만 찾으면 된다.
이를 위해 운영체제는 모든 비어 있는 페이지의 빈 공간 리스트를 유지하고 리스트의 첫 네 개 페이지를 선택할 것이다.

Address Mapping

  • Virtual address : v = (p, d)
    - p : page number
    - d : displacement (offset)

  • Address mapping
    - PMT(Page Map Table) 사용

Page Table?

📖 Page Table (page map table)에 대해 논하자면 다음과 같다.

  • 주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스 마다 페이지 테이블이라는 자료 구조룰 유지한다.

  • 페이지 테이블의 주요 역할은 주소 공간의 가상 페이지 주소 변환 (address translation) 정보를 저장하여 각 페이지가 저장된 물리 메모리의 위치가 어디인지 알려준다.
    페이지 테이블은 프로세스마다 존재한다.

✨ 그렇다면, 페이지 테이블은 어디에 저장될까?

페이지 테이블은 작은 세그멘트 테이블이나 베이스-바운드 쌍에 비해 매우 커질 수 있다. 예를 들어, 4KB 크기의 페이지를 가지는 전형적인 32비트 주소 공간을 상상해 보자. 이 가상 주소는 20비트 VPN(virtual page number) 과 12비트 오프셋으로 구성된다. (1KB 페이지 크기를 위해 10비트가 필요하며, 4KB 페이지를 위해서는 두 비트만 추가하면 된다.)
20비트 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 변환의 개수가 2^20(1,048,576)이라는 것을 의미한다.

물리 주소로의 변환 정보와 다른 필요한 정보를 저장하기 위하여 페이지 테이블 항목(page table entry, PTE) 마다 4바이트가 필요하다고 가정하면, 각 페이지 테이블을 저장하기 위하여 4MB의 꽤 커다란 메모리가 필요하게 된다. 프로세스 100개가 실행 중이라고 가정하면, 주소 변환을 위해서 운영체제가 400MB의 메모리를 필요로 하는 것을 의미한다.
컴퓨터가 Giga byte 단위의 메모리를 가지고 있는 요즘이라도 변환을 위해서 이런 큰 청크를 사용한다는 것은 매우 비정상적이다. (64비트 주소 공간을 위한 페이지 테이블의 크기는 얼마지?)

그래서 어디에 저장이 되나...?
페이지 테이블은 매우 크기 때문에 현재 실행 중인 프로셋스의 페이지 테이블을 저장할 수 있는 회로를 MMU 안에 유지하지는 않을 것이다.
페이지 테이블은 운영체제 가상 메모리에 저장할 수 있고 심지어 디스크에 스왑될 수 있다. 그러나 현재로선 매우 혼란스럽기 때문에 일단 무시하고,
대신 각 프로세스의 페이지 테이블을 메모리에 저장한다고 가정을 해두자!

Address mapping mechanism

  • 직접 사상 (Direct mapping)
    - Block maaping 방법과 유사
    - 가정
    • PMT를 커널 안에 저장
    • PMT entry size =entrySize
    • Page size = pageSize

📌직접 사상 순서

  1. 해당 프로세스의 PMT가 저장되어 있는 주소 b에 접근

  2. 해당 PMT에서 page p에 대한 entry 찾음
    ❗p의 entry 위치 = b + (p * entrySize)

  3. 찾아진 entry의 존재 비트 검사
    3.1 Residence bit = 0인 경우, (Page Fault)
    swap device에서 해당 page를 메모리로 적재
    PMT를 갱신한 후 3-2 단계 수행

    ✨ Page Fault?
    Page Fault는 소프트웨어 프로그램이 시스템의 RAM에 현재 저장되지 않은 메모리 블록에 액세스하려고 할 때 발생하는 interrupt입니다. 이 exception은 운영 체제가 가상 메모리에서 블록을 검색하여 장치의 스토리지(SSD 또는 HD)에서 RAM으로 보낼 수 있도록 합니다.

    3.2 Residence bit = 1인 경우,
    해당 entry에서 page frame 번호 p'를 확인

  4. p'와 가상 주소의 변위 d를 사용하여 실제 주소 r 형성
    ❗ r = p' * (pageSize + d)

  5. 실제 주소 r로 주기억장치에 접근


직접 사상의 문제점?

  • 메모리 접근 횟수가 2배 (성능 저하)
  • PMT를 위한 메모리 공간 필요

해결 방안

  • Associative mapping (TLB)
  • PMT를 위한 전용 기억장치(공간) 사용
    - Dedicated register or cache memory
  • Hierarchical paging
  • Hashed page table
  • Inverted page table

📌 연관 사상 (Association Mapping)

  • TLB(Translation Look-aside Buffer)에 PMT 적재
    - Associative high-speed memory
  • PMT를 병렬 탐색
  • Low overhead, high speed
  • Expensive HW
    - 큰 PMT를 다루기가 어려움

📌 hybrid direct/associative mapping

  • 두 기법을 혼합하여 사용
    - HW 비용은 줄이고, Associative mapping의 장점을 활용
  • 작은 크기의 TLB 사용
    - PMT : 메모리 (커널 공간)에 저장
    - TLB : PMT 중 일부 entry 들을 적재
    • 최근에 사용된 page 들에 대한 entry 저장
  • Locality (지역성 활용)
    - 프로그램의 수행과정에서 한 번 접근한 영역을 다시 접근 (temporal locality) 또는 인접 영역을 다시 접근 (spatial locality) 할 가능성이 높음

📖 Hybrid Direct/Associative Mapping의 순서

  1. TLB에 적재되어 있는 경우,
    • Residence bit를 검사하고 page frame 번호 확인
  2. TLB에 적재되어 있지 않은 경우,
    • Direct mapping으로 page frame 번호 확인
    • 해당 PMT entry를 TLB에 적재함

Memory Management

  • Page와 같은 크기로 미리 분할 하여 관리 / 사용
    - Page frame
    - FPM(Fixed Partition Multi-programming) 기법과 유사
  • Frame table
    • Page frame당 하나의 entry
    • 구성
      1. Allocated/Available filed
      2. PID filed
      3. Link filed : For free list (사용가능한 fp들을 연결)
      4. AV : Free list header (free list의 시작점)

Page Sharing

  • 여러 프로세스가 특정 page를 공유 가능
    - Non-continuous allocation

  • 공유 가능 page
    1. Procedure pages (pure code (reenter code))
    2. Data page : Read-only data, Read-write data(병행성(concurrency) 제어 기법 관리 하에서만 가능)

    Example

Page Protection

  • 여러 프로세스가 page를 공유 할 때,
    - protection bit 사용

Paging System - Summary

  • 프로그램을 고정된 크기의 block으로 분할 (page) / 메모리를 block size로 미리 분할 (page frame)
    - 외부 단편화 문제 없음
    - 메모리 통합/압축 불필요
    - 프로그램의 논리적 구조 고려하지 않음 then, Page sharing/protection이 복잡

  • 필요한 page만 page frame에 적재하여 사용
    - 메모리의 효율적 활용

  • Page mapping overhead
    - 메모리 공간 및 추가적인 메모리 접근이 필요
    - 전용 HW (TLB) 활용으로 해결 가능 -> HW 비용 증가

  • 페이지 테이블의 크기가 메모리 상에서 매우 크게 증가할 수 있어 처리 속도가 저하될 수 있다.

profile
김민우
Pay it forward.
이전 포스트

멀티 레벨 피드백 큐 (MLFQ)

다음 포스트

6.2. Segmentation system

post-custom-banner

0개의 댓글