본문 바로가기
Computer Science/operating system

3. Virtualizing Memory

by yongmin.Lee 2020. 7. 19.

1. Address Space
2.  Base-and-Bound
3. Segmentation
4. Paging
5. 물리메모리 크기 극복

 

1. Address Space

- 정의

  • 실행중인 프로세스가 가정하는 선형적인 메모리의 모습. 실제로는 임의의 물리주소에 산재되어 탑재되어 있다
  • address space는 실행 프로그램의 모든 메모리 상태를 갖는다 : code, stack, heap

 

- virtualizing memory, VM, 메모리 가상화

  • 프로세스로 하여금 자신이 특정주소의 메모리에 탑재되고 자신만의 address space를 가지고 있다는 환상을 만드는 것
  • VM의 목표 1 : transparency -> 프로그램은 메모리가 가상화되었다는 사실을 인지해서는 안된다
  • VM의 목표 2 : efficiency -> OS는 가상화가 시간과 공간 측면에서 효율적이도록 해야 한다
  • VM의 목표 3 : protection -> OS는 다른 프로세스로부터 프로세스 및 자신을 보호해야한다. 이를 위해 프로세스들을 서로 고립, isolation 시켜야 한다

 

- address translation, 주소 변환

  • "효율적"이고 "유연성"있는 메모리가상화를 구현하기 위한 기법
  • 하드웨어는 명령어 반입, 탑재, 저장등의 가상주소정보를 정보가 실제로 존재하는 물리 주소로 변환
  • OS는 메모리의 빈 공간과 사용중인 공간을 항상 알고, 메모리 사용을 제어 및 관리
  • 주소변환을 통해 프로그램이 자신의 전용 메모리를 소유하고 그 안에 자신의 코드와 데이터가 있다는 환상을 만든다

 

2. Base-and-Bound ( = dynamic relocation )

- 정의

  • address translation 기법을 구현하기 위해 사용되는 기술
  • 각 cpu마다 "base register"와 "bound register"라고 불리는 2개의 하드웨어 레지스터를 이용
  • OS가 프로그램이 탑재될 물리 메모리 위치를 결정하고 base register를 그 주소로 지정한다. 그러면 프로세스 실행시 프로세스에 의해 생성되는 모든 주소가 프로세서에 의해 다음과 같이 변환 : physical address = virtual address + base
  • 프로세스가 생성하는 메모리 참조는 모두 가상주소 이며 하드웨어는 베이스 레지스터의 값을 이 주소에 더하여 물리 주소를 생성한다
  • 가상주소에서 물리주소의 변환을 address translation이라고 하며 이 주소의 재배치는 실행 시에 일어나고, 프로세스가 실행을 시작한 이후에도 address space를 이동할 수 있기 때문에 dynamic relocatoin이라고 한다
  • 베이스와 바운드 레지스터는 cpu칩 상에 존재하는 하드웨어 구조처럼 주소변환에 도움을 주는 프로세서의 일부를 MMU (메모리 관리 장치)라고 부른다

 

- H/W support

  1. 하드웨어는 processor status word 레지스터의 한 비트로 cpu의 현재 실행 모드 ( kernel mode or user mode)를 나타낸다
  2. 하드웨어는 base register와 bound register를 자체적으로 제공하며 프로세스가 생성한 가상주소에 base register값을 더하여 주소를 변환, bound register와 cpu 내부 일부 회로를 사용하여 주소가 유효한지 검사한다
  3. 하드웨어는 base register와 bound register 값을 변경하는 명령어를 제공한다
  4. cpu는 user program이 bound를 벗어난 주소로 불법적인 메모리 접근을 시도하는 상황에서 예외를 발생시킨다. 

 

- OS issue

  1. 프로세스가 생성될 때, OS는 새로운 주소 공간 할당에 필요한 영역을 찾기위해 free list 자료구조를 검색
  2. 프로세스가 종료할 때, OS는 프로세스가 사용하던 메모리를 회수하여 다른 프로세스나 운영체제가 사용할 수 있도록 한다
  3. 운영체제는 프로세스 전환시 base와 bound쌍을 저장/복원해야 하므로 OS가 process를 중단하기로 결정하면 메모리에 존재하는 프로세스 별 자료구조 안에 base register와 bound register 값을 저장한다
  4. OS는 예외핸들러 또는 호출될 함수를 제공해야 한다

 

- base-and-bound 문제점

  • address space 전체를 physical memory에 올리는 base-and-bound 방식은 스택과 힙 사이의 빈공간도 physical memory를 차지하므로 메모리 낭비가 심하다.
  • address space가 physical memory 보다 큰 경우 프로세스 실행이 불가능하므로 유연성이 없다

 

3. Segmentation

- 정의

  • base-and-bound 문제를 해결하기 위해 고안된 기법
  • 주소 공간의 논리적인 segment (코드, 스택, 힙) 마다 base와 bound 쌍이 각각 존재함으로써, OS는 각 segment를 physical memory의 각기 다른 위치에 배치할 수 있다. 

 

- address translation

  • offset : 주소가 참조하는 바이트가 세그먼트 안에서 세그먼트 시작으로부터 몇번째 바이트인지 나타내는 값
  • 하드웨어는 가상주소에서 offset을 구하고 여기에 base register값을 더함으로써 실제 physical address를 구한다.
     

- code sharing 

  • protection bit : 세그먼트마다 protection bit를 추가하여 세그먼트를 읽기 전용으로 설정할 수 있도록 한다
  • 코드세그먼트를 읽기 전용으로 설정하면 주소 공간의 독립성을 유지하면서 여러 프로세스가 주소 공간의 일부를 공유함으로써 메모리를 절약할 수 있다
  • 각 프로세스는 자신의 전용 코드세그먼트를 사용하고 있다고 생각하지만 OS는 변경 불가능한 메모리 영역을 비밀리에 공유시킴으로써 환상 구현

 

- external fragmentation, 외부 단편화 문제

  • 정의 : 물리메모리에 임의의 위치에 세그먼트들이 할당됨으로써 중간중간에 작은 크기의 free space들이 남게 되고 이는 새로 생성된 세그먼트를 할당하기에 너무 작아 메모리 낭비 발생
  • 해결책 1 compact : OS는 현재 실행중인 프로세스를 모두 중단하고 세그먼트들을 물리메모리상에 연속적으로 재배치 하여 하나의 큰 빈공간을 확보 -> 압축비용이 많이 든다
  • 해결책 2 free list : free space들을 리스트 형태로 관리하여 메모리할당시 외부단편화를 최소화 하도록 한다

 

- free list management

  • 분할 : 메모리할당 요청이 free space보다 작은 경우 free space를 분할하여 할당한다
  • 병합 : 메모리해제된 free space가 다른 free space와 인접하면 하나의 큰 free space로 병합
  • free space 마다 그 크기와 다음 free space의 주소값을 가지고 있는 헤더블럭을 유지함으로써 free list 자료구조를 구현

 

- free space allocation strategies

  1. best fit : 요청 크기와 가장 비슷한 메모리를 가지는 free space를 free list에서 검색하여 할당
  2. worst fit : free list에서 가장 큰 크기의 free space를 찾아 요청된 크기만큼 할당하여 최대한 큰 free space를 유지
  3. first fit : 요청 크기보다 큰 첫번째 free space를 free list에서 찾아 할당하여 빠르게 할당
  4. next fit : 마지막으로 할당된 free space 다음부터 요청크기보다 큰 free space를 검색하여 free list의 앞부분에서만 external fragmenation이 발생하는 것을 방지

 

4. Paging

- 정의

  • 메모리를 동일크기의 조각으로 분할하여 공간관리하는 방법
  • 프로세스의 주소공간을 논리 세그먼트로 나누는 것이 아니라, 고정크기의 단위로 나눈다. 고정크기단위로 나눈 가상메모리 블럭을 "Page"라고 하고, 같은 단위로 나눈 물리메모리 블럭을 "Page frame"이라고 한다
  • address space의 각 가상 page에 대한 물리메모리 위치를 기록하기 위해 OS는 프로세스마다 "Page Table"이라는 자료구조를 유지하고 여기에 address translation 정보를 저장한다. 다른 프로세스를 실행해야 한다면 OS는 해당 프로세스를 위해 또 다른 Page Table이 필요하다.
  • 프로세스가 생성한 virtual address의 변환을 위해서는 먼저 가상주소를 VPN (가상페이지번호)과 offset 2개의 구성요소로 분할한다.

 

- 장점

  • 유연성 : paging은 프로세스의 address space가 어떻게 사용되는 지에 상관없이 효율적으로 주소 공간 개념지원 가능
  • free space 관리의 단순함 : OS는 물리메모리의 비어있는 page의 free list를 유지하고 프로세스 실행시 리스트의 첫부분에서 부터 해당 크기의 page frame만 선택하면 된다.

 

- page table

  • 정의 : VPN (가상페이지번호)를 PFN (물리페이지번호)으로 mapping 하는데 사용되는 자료구조이다
  • 가장 간단한 page table은 linear page table로 vpn을 index로 하는 배열이다
  • OS는 vpn으로 배열항목에 접근하여 PTE ( page table entry) 를 검색. PTE에는 PFN 뿐만 아니라 다른 정보를 담고 있는 비트들(valid bit, protection bit, present bit, dirty bit, reference bit)도 존재

 

- 문제점

  1. 성능 저하 : 페이지에 접근하기 위해 페이지 테이블에 먼저 접근 // TLB로 해결
  2. 메모리 낭비 : 페이지테이블의 크기가 크면 물리메모리상의 공간 낭비  // multi-level page table로 해결

 

- TLB, translation-lookaside buffer

  • paging의 속도저하 문제 해결을 위해 MMU의 일부인 TLB를 도입
  • TLB는 자주 참조되는 가상주소-실주소 변환 정보를 저장하는 "하드웨어 캐시"이다.
  • 가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지를 확인한다. 만약 TLB에 있다면 페이지테이블을 참조하지 않고 변환을 빠르게 실행
  • TLB는 VPN, PFN, 다른 비트들(valid bit, protection bit, dirty bit, address-space identifier등)로 구성되어 있다
  • TLB 히트율은 spatial locality와 temporal locality에 영향을 받는다

 

- TLB algorithm

  1. 가상주소에서 VPN을 추출
  2. 해당 VPN이 TLB에 존재하는지 검사
  3. 존재하는 경우 : TLB 히트
    1. 해당 페이지에 대한 접근 권한 검사
    2. 접근권한이 있는 경우, 그 정보를 오프셋과 합쳐서 물리주소 구성
    3. 메모리접근
  4. 존재하지 않는 경우 : TLB 미스
    1. 하드웨어는 변환정보를 찾기위해 페이지테이블에 접근
    2. 가상메모리가 유효하고 접근 가능한지 검사
    3. 해당 변환정보를 TLB로 읽어들임
    4. TLB가 갱신되면 다시 TLB 검색
    5. TLB 히트

 

 - Multi-level Page Table

  • paging의 메모리낭비 문제 해결을 위해 사용되는 기법
  • 페이지테이블을 페이지 크기의 단위로 나눈 다음, 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면 해당 페이지를 할당하지 않는다.
  • PDE (page directory entry)로 구성된 page directory는 valid bit(페이지테이블의 각 페이지 할당 여부 정보)와 PFN 정보를 갖고 있다.
  • PDI ( page directory index)를 이용하여 PDE address를 알수 있다 : PDE address = PageDIrBase + (PDI * sizeof(PDE))
  • PTI (page table index)를 이용하여 PTE address를 알 수 있다 : PTE address = PDE.PFN + (PTI * sizeof(PTE))
  • 페이지 디렉토리가 너무 크면, 트리의 단계를 증가하여 메모리공간을 효율적으로 사용할 수 있지만 메모리주소를 구하는 작업비용이 증가한다

 

- Multi-level Page Table 장단점

  • 장점1 : 멀티레벨 테이블은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당되므로 메모리를 효율적으로 사용
  • 장점2 : 페이지테이블을 페이지 크기로 분할함으로써, 메모리 관리가 용이하고 페이지 테이블을 위한 공간 할당이 유연하다
  • 단점1 : 주소변환을 위해 두 번이상의 메모리 로드가 발생( 페이지 디렉터리 접근 + PTE접근)하므로 작업비용 증가
  • 단점2 : 페이지 테이블 검색이 복잡해진다

 

5. 물리메모리 크기 극복

- 물리메모리 한계

  • 주소공간이 물리메모리에 탑재되지 못하는 경우 큰 주소공간을 지원하기 위해 OS는 주소 공간중에 현재 필요하지 않는 일부를 보관해 둘 "공간"이 필요.
  • 보조기억장치 ( HDD, SSD 등)에서 "공간"을 확보하고 이 공간을 "swap space"라고 한다

 

- swap space

  • 정의 : 디스크에 페이지를 저장할 수 있는 공간
  • swap space 의 입출력 단위는 페이지 크기
  • OS는 swap psace에 있는 모든 페이지들의 디스크 주소를 기억
  • swap spce를 이용하면 시스템에 실제 물리메모리 공간보다 더 많은 공간이 존재하는 것처럼 가정
  • swap은 swap space에서 뿐만 아니라 물리페이지에서도 가능

 

-present bit

  • 하드웨어 기반 TLB를 사용하는 시스템은 page swap을 위해 하드웨어는 present bit를 사용하여 각 페이지 테이블 항목에 어떤 페이지가 존재하는 표현한다
  • 메모리 참조 알고리즘
    1. 프로세스가 가상 메모리 참조
    2. 하드웨어가 가상주소를 물리주소로 변환하기위해 가상주소에서 VPN 추출, TLB에 변환정보가 있는지 검색
    3. TLB 히트
      1.  물리주소를 얻은 후 메모리로 가져옴
    4. TLB 미스
      1. 페이지 테이블의 메모리 주소 파악
      2. PTE항목 추출
      3. PTE가 유효하고(valid bit = 1) 물리메모리에 존재 (present bit = 1)
        1. PFN 정보를 추출하고 TLB에 저장
        2. TLB 갱신되면 TLB 재검색
        3. TLB 히트
      4. PTE가 유효하지만(valid bit =1) 물리메모리에 존재 하지 않음 ( present bit = 0)
        1. page fault (물리메모리에 존재하지 않는 페이지 접근) 발생
        2. OS에게 제어권이 넘어가고 OS는 page-fault handler 실행
        3. OS는 디스크에 있는 페이지를 물리메모리로 swap-in 한다
        4. 물리메모리에 공간이 없는 경우, 물리메모리에 있는 페이지중 swap-out될 페이지는 replacement policy에 의해 결정된다
        5. 디스크 I/O가 완료되면 OS는 해당 PTE의 PFN값을 탑재된 페이지의 메모리 위치로 갱신하고 page fault를 발생시킨 명령어를 재실행
        6. TLB 히트

 

- swap-out이 일어나는 시기

  • 물리메모리의 여유공간이 고갈된 후에 교체 알고리즘이 작동하는 것은 비효율적이므로 OS는 항상 일정한 수준의 여유공간을 유지한다
  • OS는 HW (high watermark)와 LW ( low watermark)를 설정
  • swap demon 이라고 불리는 백그라운드 쓰레드가 여유공간의 크기가 LW보다 작으면 HW에 이를 때까지 페이지 제거 수행하고 완료후 슬립모드로 전환

 

- replacement policy

  • evict될 page는 OS의 replacement policy에 의해 결정됨
  • replacement policy 목표1 : 디스크로부터 swap-in 횟수 최소화
  • replacement policy 목표2 : 접근할 페이지가 이미 메모리에 존재하는 횟수 최대화
  • Optimal replacement policy : 가장 나중에 접근될 페이지를 evcit -> 가장 최적이며 가장적은 미스 발생하지만 미래의 정보는 알수 없으므로 구현 불가능
  • Least Recently Used : 가장 오래전에 접근된 페이지를 evict -> 과거의 정보를 활용하므로 구현 가능

 

- Approximating LRU

  • LRU 알고리즘은 구현은 가능하지만 과거의 메모리 참조 정보를 모두 기록하고 시간정보배여을 순차탐색해야 하므로 매우 큰 작업비용을 가진다
  • 몇몇 비트(use bit, dirty bit)를 추가하는 하드웨어 지원으로 LRU에 근사하는 저비용 알고리즘 구현 가능
  • Clock Algorithm
    • use bit를 추가, 페이지가 참조될 때마다 H/W는 use bit를 1로 설정
    • 페이지들을 노드로 하는 circular list를 구성
    • 페이지 교체시 OS는 현재 clock hand가 가리키는 페이지의 use bit를 검사
    • use bit가 1이면 해당 페이지는 최근에 참조된 페이지 이므로 물리메모리에 그대로 두고( temporal locality) OS가 use bit를 0으로 재설정
    • 다음 페이지를 검사하여 use bit가 0인 페이지를 찾으면 해당 페이지를 evict
  • Corbato Algorithm
    • 주기적으로 use bit를 지우고, 교체 페이지를 선택하기 위해 use bit가 1인지 0인지 검사
    • use bit가 0인 페이지를 찾으면 evict
  • Enhanced Clock Algorithm
    • dirty bit를 추가하여 페이지의 변경 여부 정보를 저장
    • 교체할 페이지 선택시 use bit와 dirty bit 둘다 고려
    • 페이지가 최근에 수정되어 dirty bit = 1 이면 그 페이지를 swap-out할 때 디스크에 있는 원본 페이지에 수정된 내용을 기록해야 하므로 추가비용 발생, dirty bit = 0 인 페이지는 추가적인 I/O 비용 없음
    • use bit = 0, dirty bit = 0 인 페이지를 먼저 찾고 evict 하고 이를 만족하는 페이지가 없으면 use bit = 0, dirty bit = 1인 페이지를 evict

 

- Thrashing

  • 발생과정
    1. 물리메모리가 요구를 감당할 수 없을만큼 많은 프로세스 실행중이면 많은 페이지폴트 발생
    2. CPU 사용률 감소 
    3. OS는 CPU 사용율 증가를 위해 더 많은 페이지를 물리메모리에 탑재
    4. 페이지폴트가 계속 발생하면서 page-in, page-out 반복
    5. cpu 사용률이 급감하는 thrashing 문제 발생
  • 해결방법
    1. admission control : 다수의 프로세스가 존재할 때, 일부 프로세스의 실행을 중지
    2. out-of-memory killer : 과다한 메모리 요청시, 메모리를 요구하는 프로세스를 kill




'Computer Science > operating system' 카테고리의 다른 글

4. Concurrency  (0) 2020.07.19
2. Virtualizing CPU  (0) 2020.07.19
1. Introduction to OS  (0) 2020.07.19

관련글

티스토리툴바