3-1공부/운영체제

기말2. 메모리관리

KGW2027 2022. 5. 21. 12:41
728x90
반응형

1. 메모리 계층화

  • Register > L1 Cache > L2 Cache > L3 Cache > RAM > Storage
  • 코드, 데이터, 자원 등이 아주 짧은 시간내에 다시 사용되는 프로그램의 특성 (참조의 지역성)으로 인해 가능하다.
  • Loop의 경우 시간지역성을 가지고, Array의 경우 공간지역성을 가진다.

2. 메모리 관리 정책

 - 폰노이만 구조에서 메모리는 컴퓨터의 유일한 작업 공간이므로 모든 프로그램은 메모리에 올라오게 된다.

 - 일괄 처리 시스템에서는 한 번에 하나의 프로그램만 실행하기 때문에 문제가 없었으나, 다중프로그래밍 시스템에서는 OS를 포함한 모든 프로그램이 메모리에 올라오므로 프로세스를 잘 배치해야하고 정리를 잘 해야한다.

 - 프로세스는 가능한 많은 메모리를 독점하려 하며, OS는 메모리를 최대한 효율적으로 사용하려고 한다.

  • 적재 정책(Fetch Policy) : 프로세스가 필요로 하는 데이터를 언제 메모리에 가져올 것인가?
  • 배치 정책(Placement Policy) : 가져온 프로세스를 메모리의 어떤 위치에 올려놓을 것인가?
  • 재배치, 교체 정책 (Replacement Policy) : 메모리가 꽉찼을 때, 어떤 프로세스를 내보낼 것인가?

3. 메모리 주소

  • 물리 주소(Physical Address) : HW관점에서의 주소로, 물리 메모리에 매겨진 주소이다.
  • 논리/가상 주소(Logical/Virtual Address) : 프로세스 내에서 사용되는 주소, 코드나 변수 등에 대한 주소이다.
  • CPU가 프로세스를 실행하는 동안 다루는 모든 주소는 논리주소이다.
  • 프로세스 내에서 매겨진 상대주소는 실제 메모리에 접근하기 위해 절대주소로 변환돼야 하며, 이는 MMU에 의해 수행된다.
  • MMU(Memory Management Unit) : 논리주소를 물리주소로 바꾸는 하드웨어 장치로 CPU에 내장된다.
    - Base Register : 주소 변환의 기본이 되는 주소값. ( 프로세스 할당 시작 위치 )
    - Limit Register : 메모리 경계를 정하는 주소값. ( 프로세스 할당 끝 위치, 벗어날시 프로세스 종료 )
    - 주소가 변환될 때는, 물리주소와 논리주소가 매핑된 매핑테이블을 통해 변환된다.
  • ASLR ( Address Space Layout Randomization ) : 메모리 주소가 누출되면, 그 주소를 이용해 임의의 코드를 실행할 수 있다. 만약 System call의 주소가 누출되거나 할 경우 보안에 심각한 위험이 된다.
    - 1. 프로세스 주소 공간 내에서 스택/힙 등의 영역을 랜덤배치  -> 직접 메모리 참조가 어려워진다.
    - 2. 실행할 때마다 지역변수와 동적할당 메모리의 논리주소를 변경

4. 주소 바인딩 ( Address BInding )

  • 프로그램이 메모리의 어떤 물리적 위치에 저장될 지 결정하는 과정.
  • Compile-time binding : 물리주소와 논리주소가 동일시 되는 바인딩 방법.
    - Batch process와 같이 한 시스템에서 한 개의 프로그램만 실행된다면 사용 가능하나, 그렇지않다면 불가능하다.
    - Program에서의 address 0xFF가 Physical Memory의 0xFF하고 동일함.
  • Load-time binding : 상대주소를 지정하고, 프로그램이 로드되는 시점에 반영해서 등록한다.
    - 그러나 계산해야할 메모리 주소가 많다면 로드시간이 너무 길어지게 된다.
  • Runtime binding : 상대주소에 대한 계산을 실행시간에 반영한다.
    - Load-time binding과 비슷하지만, 로드때에 모두 반영하는게 아니라, 실행할때 MMU를 통해 계산해서 반영된다.
    ex) 프로세스 시작주소 0x100, 참조 데이터 상대주소 0x0AC에서
    Load-time binding은 로드과정에서 0x100+0x0AC가 계산되서 등록된다. -> 실행에선 부가적 계산없이 0x1AC로 됨.
    Runtime binding은 실행과정에서 MMU가 계산한다. -> 실제 참조과정에서 MMU가 +0x100을 한다.

5. 메모리 할당 기법 ( Memory Allocation )

  • OS가 새로운 프로세스를 실행하거나, 실행중인 프로세스가 메모리를 필요로 하면 물리 메모리가 할당된다.
  • 이 때, 프로세스가 메모리 내에 인접하냐 or 분할되냐에 따라 연속/불연속 할당으로 구분되고,
    분할될때 프로세스 크기에 맞는가 or 상관없는가에 따라 가변/고정 할당으로 구분된다.

 1) 연속 메모리 할당

  • 현재에는 주로 사용되지 않는 할당 방식으로, 초기 운영체제에서 사용되었다.
  • 가변크기 할당 : 프로세스의 크기에 맞춰 메모리를 할당한다. ( 최대 프로세스 수 가변 )
  • 고정크기 할당 : 메모리 전체를 고정크기 n개로 분할하여 프로세스마다 하나씩 할당한다. ( 최대 프로세스 수 고정 )
  • 구현 방법 : 하드웨어 ( Base Register, Limit Register, MMU 등 ), 소프트웨어 ( OS 지원 )
    장점 : 논리주소를 물리주소로 바꾸기 쉬움, CPU의 액세스 속도가 빠름, 관리 정보량이 적어 부담이 적음.
    단점 : 메모리 할당의 유연성이 떨어져서 외부 단편화 문제가 발생하기 쉬움.
  • 메모리 배치 기법 : 홀 선택 알고리즘
    - 최초 적합 (First-fit) : 할당 가능한 가장 앞의 파티션을 선택한다.
    - 최적 적합 (Best-fit) : 할당 가능한 가장 작은 파티션을 선택한다.
    - 최악 적합 (Worst-fit) : 할당 가능한 파티션 중 가장 큰 파티션을 선택한다.
    시뮬레이션 결과 First, Best가 Worst보다 나은 결과를 보이며, 알고리즘적으로는 First가 유리하다. 그러나 Case-by-Case는 존재함.

 2) 불연속(분할) 메모리 할당

  • 메모리를 정해진 크기로 분할 후, 프로세스도 그 크기에 맞춰 분할하여 할당한다.
  • 고정크기 할당 : 페이징(Paging)
  • 가변크기 할당 : 세그먼테이션(Segmentation), 버디시스템(Buddy System)
  • Segmentation
         - Segment : 프로그램의 논리적 구성 단위, 코드/데이터/스택/힙 세그먼트 등... 세그먼트마다 크기가 다르다.
     - 프로세스를 논리 세그먼트 크기로 나누고, 각 논리 세그먼트를 물리 메모리에 할당하고 관리한다.
     - 세그먼트 매칭 테이블을 두고 논리주소를 물리주소로 변환한다.
     구현방법 : 소프트웨어 ( Compiler, Loader, OS 등 ) 
     단점 : 외부 단편화 문제가 발생할 수 있다.
  • Buddy System
     - 메인 메모리를 계속 절반으로 분할하면서 프로세스를 넣을 수 있는 가장 작은 공간에 할당한다.
     장점 : 비슷한 크기의 조각들이 모여 큰 조각을 완성할 수 있다.
     단점 : 내부 단편화 문제가 발생할 수 있다.

6. 페이징 (Paging)
어째서 가상 메모리를 사용하는가?
 -> 다중 시스템에서 주소간 충돌이 일어날 수 있고, 이를 방지하기 위해 모든 시스템은 0번지부터 사용하는것으로 정의한다. 만약 메모리 공간이 부족하다면 Swap*을 이용해 해결한다.
Swap : 메모리가 모자라 쫓겨난 프로세스들을 모아두는 영역 ( 저장장치에 존재하지만 관리는 메모리에서 한다 )

  • 페이지(Page) : 프로세스의 주소 공간을 0번지부터 동일한 크기로 분할한 것 ( 주로 4KB )
  • 프레임(Frame) : 물리 메모리의 주소 공간을 0번지부터 페이지와 동일한 크기로 분할한 것
  • 페이지 테이블 : 각 페이지와 프레임을 1대1로 매칭한 정보를 저장하는 테이블, 각 프로세스 별로 페이지 테이블이 존재하며 PCB에 저장되고, OS에서 한 곳에 모아서 관리된다.
  • 장점
    구현이 쉽다.
    페이징 메모리 관리를 CPU에 의존하지 않기 때문에 다양한 시스템에 쉽게 이식 가능하다.
    페이지 크기를 자유롭게 설정할 수 있어 높은 융통성을 가진다.
    단편화 가능성이 적어 메모리 활용 및 오버헤드 관리에서 우수하다.

 1) 구현 방법

  • 하드웨어 ( CPU의 PTBR(Page Table Base Register), MMU장치 )
    - 각 페이지 번호에 매칭되는 프레임 번호를 PTBR에 저장하며, Offset을 이용해 접근한다.
    ex) 입력 데이터 : VA=<37, 42>일때, PA=<PTBR[37], 42>이다. 변환된 PA는 MMU에 의해 계산된다.
     - 주로 페이지 번호 20비트 + Offset 12비트의 32비트 구성으로 이뤄진다.
  • 소프트웨어 ( OS의 프레임 동적 할당 및 반환, 페이지 테이블 관리 기능 )

 2) 페이지 테이블 매핑 방식

  • 직접매핑(Direct Mapping) : 메모리 주소와 페이지 순서를 일치시킨다. ( Cache-hit가 떨어짐, 용량낭비 큼 )
  • 연관매핑(Associative Mapping) : 순서일치 X, Tag를 이용해 검색, Tag를 찾기위해 모두 검색해야할 수 있음.
  • 직접-연관 매핑(Set-Associative Mapping) : 그룹단위로 묶어서 순서를 일치시킨다.
  • TLB ( Translation Look-aside Buffer ) : 페이지와 프레임을 연관 매핑으로 저장하는 캐시메모리를 이용
    - 한 번의 메모리 액세스를 위해 PTBR 접근 > 물리 메모리 접근으로 나뉘는 2번의 작업이 필요하다.
    - 또한, 대다수의 프로세스가 모든 메모리 공간을 한 번에 사용하지는 않으므로 페이지 테이블이 낭비된다.
    -> 한번 접근한 테이블 데이터를 CAM(Content-addressable Memory)에 저장하여, 그 다음 접근을 빠르게 한다.
    -> TLB에서의 항목 비교는 병렬적으로 작동하므로 매우 빠른 검색속도를 가진다.
    - 참조의 지역성으로 인해 루프나 순차 메모리 액세스가 있다면 실행속도가 빠르나, TLB Miss가 자주 발생하면 실행속도의 향상이 없다.

7. 페이지 테이블의 공간 낭비

  • 32bit-CPU 환경에서 물리메모리 용량 4GB(2^32), 페이지 크기 4KB(2^12)일 때, 약 100만개(2^20)의 페이지가 있다.
    -> 한 항목당 4Byte(32bit, 페이지 위치 20bit + Offset 12bit) 이므로, 테이블크기 : 4*(2^20)Byte = 4MB
    페이지 테이블은 프로세스마다 한 개씩 존재하므로, 공간낭비가 심하다.
  • 해결법1. 역-페이지 테이블 ( Inverted Page Table, IPT )
    - 페이지 번호가 아니라, 프레임 번호를 기준으로 테이블을 작성한다. [ VA = <PID, PageNum, Offset> ]
    - 한 개만 존재해도 되므로 용량은 아낄 수 있으나, 테이블 전체를 검색해야하므로 속도가 느려진다.
    - PID = 4Byte, Page번호 = 4Byte 일 때, IPT의 크기 : 8*(2^20) = 8MB 고정. ( 기존은 (4*N) MB )
  • 해결법2. 멀티레벨 페이지 테이블, 계층 페이징 ( Multi-level Page Table, Hierarchinal Paging )
    - 페이지 테이블을 작게 나누고, 그 작게 나눈 페이지 테이블에 대한 테이블을 하나 더 만든다. (디렉토리)
    - 필요한 페이지가 생길 때 마다, 페이지 테이블을 추가해 디렉토리에 넣는다.
    - VA = <PageDirIndex, PageTableIndex, Offset>에서, DirIndex 10bit, TableIndex 10bit, Offset 12bit
    - 용량은 아낄 수 있으나, CPU->Directory Search->Table Search->Frame으로 3번의 과정을 거치므로 레이턴시가 생긴다.
    - 최소 용량 : 4KB (Directory), 최대 용량 : 4MB 4KB ( Directory + 2^10 Tables )
    - 그러나 일반적인 상황에서 1024개의 테이블이 모두 사용될 일은 없다.
  • 위의 두 해결법은 근본적으로 64bit 환경에서는 사용하기 어렵다.
    - 64bit에서는 최대 물리메모리 용량 2^64, 페이지 크기 2^12 일 때, 2^52개의 페이지가 있다.
     -> 한 항목당 8Byte(페이지 52bit + Offset 12bit), 테이블 크기 : 8*(2^52)Byte = 32PB = 32,000TB이다.
    - 만약 계층 페이징으로 하려면 할 수는 있겠지만, 중간과정이 길어지므로 지연시간은 더 길어질것이다.
  • 해결법3. 해시 페이지 테이블 ( Hash Page Table )
    - Page Index에 대한 Hash function을 만들어서 Hash table을 구성한다.
    - Hash table은 O(1)이므로, 검색속도도 매우 빠름.
    - 각 항목은, <가상 페이지 번호, 프레임 주소, 다음 번호>의 구성을 가지며, 검색 시 요청된 위치와 가상페이지 번호가 일치하면 프레임주소를 이용, 불일치하면 주어진 다음 번호의 위치로 이동해 비교하는 과정을 반복한다.
    => 해시 충돌에 대한 대응

8. 단편화 문제

  • 외부 단편화 ( External Fragmentation ) : 할당된 메모리들 사이에 사용할 수 없는 홀이 생김. 가변크기 할당의 문제
  • 내부 단편화 ( Internal Fragmentation ) : 할당된 메모리 내부에 사용할 수 없는 홀이 생김. 고정크기 할당의 문제
  • 단편화 해결 방법 : 조각모음(De-Fragmentation), 압축(Compaction)
    - 배치된 프로세스들의 위치를 옮겨 빈 공간들을 하나의 큰 덩어리로 만드는 작업.
    - 이 과정을 수행하기 위해서는 프로세스가 일시적으로 중단되어야 하므로 굉장히 비싼 작업이다.

 

 

 

 

728x90
반응형