메모리 관리

<배경>
- 주기억장치(Main memory)
  - 저장 공간(words or bytes)들의 배열로 구성 -> RAM
 
- CPU 이용률(utilization)을 높이기 위해서는 multi-tasking 필요
  - 주기억장치에서 다수의 프로그램을 탑재하고 각각을 번갈아 가며 수행

- 주기억장치를 관리하는 여러 기법 소개
  - Paging, Segmentation, ... -> 대부분 하드웨어 지원이 필요

- CPU 메모리 접근 시간을 줄이기 위해
  - '가격대비 성능'을 위해 계층적으로 구성

 

<지역성의 원리(Principle of locality)>
- 정의
  - 프로그램이 실행되는 동안 CPU가 액세스 하는 기억장치는 몇몇 특정 영역에 '집중되는' 경향이 있다
  - =참조의 지역성(Locality of Reference)

- 근거
  - 반복루프와 서브루틴
  - 표나 데이터 배열에 대한 연산은 집단을 이루고 있는 데이터를 집중적으로 액세스





<OS의 메모리 관리 이유>
- 메모리는 여러 프로세스에 의해 사용되는 공유 자원이므로
  - 각 프로세스에게 적절히 할당/해제

- 메모리를 보호하기 위해
  - 각 프로세스의 독립된 공간 보장
  - 사용자 코드로부터 커널 공간에 보호

- 메모리의 용량 한계를 극복하기 위해
  - 가상 메모리

- 메모리 사용 효율성을 높이기 위해
  - 다중 프로그래밍 정도(degree of multiprogramming) 향상
 

<메모리 관리와 연관된 OS의 역할>
- 메모리 어디가/누구에 의해 사용되고 있는 지 추적해야 한다
- 메모리 공간이 사용가능하게 될 때 어떤 프로세스를 어디에 적재할 것인지 결정해야 한다
- 필요에 따라 메모리를 할당하거나, 할당된 메모리를 회수해야한다
- 접근이 허가되지 않은 영역에 침범하지 못하도록 보호




<메모리 주소의 종류(1/2)>
- 물리 주소(physical addrerss)
  - 하드웨어에 의해 고정된 메모리 주소
    - 물리 메모리에서 매겨진 주소
    - 0에서 시작하여 연속되는 주소 체계
      - ex) 100번지 -> 0x00000064(32비트 주소)

  - 프로그램 혹은 데이터가 점유하고 있는 메모리 공간의 실제 주소
  - 메모리가 취급하는 주소
    - 메모리는 시스템 주소 버스를 통해 물리 주소를 받음





<메모리 주소의 종류(2/2)>
- 논리 주소(logical address/virtual address)
  - 프로그램 수행을 위해 CPU가 취급하는 주소
    - 개발자나 프로세스가, 프로세스 내개에서 사용하는 주소
      - 0에서 시작하여 연속되는 주소 체계
      - 코드나 변수 등에 대한 주소

    - 컴파일러와 링커에 의해 매겨진 주고
 
    - CPU가 프로세스를 실행하는 동안 다루는 주소
      - 실행 파일/프로세스 내에 표현되는 주소들 
        - 프로그램에서 변수 n의 주소가 100번지라는 것은 논리 주소가 100이란 뜻

  - 사용자나 프로세스는 결코 물리 주소를 알 수 없다




<MMU(Memory Management Unit)>
- 논리주소를 물리 주소로 '매핑'하는 HW 장치
  - CPU가 발생시킨 논리 주소는 MMU에 의해 물리 주소로 바뀌에 메모리에 도달
  - 메모리 관리 방식에 따라 다르게 구현됨
    - 맵 테이블 이용

- 오늘날 MMU는 CPU 패키지 안에 내장
  - 인텔이나 AMD의 x86 CPU는 80286부터 MMU 내장
  - MMU 덕분으로 여러 프로스스가 하나의 메모리에서 실행되도록 됨

<메모리 할당(Memory allocation)>
- OS가 새 프로세스를 실행시키거나 실행 중인 프로세스가 메모리를 필요로 할 때
- 프로세스의 실행은 할당된 물리 메모리 상에서 이뤄짐

<메모리 할당 기법>
- 연속 할당(Contiguous allocation)
  - 프로세스 별로 연속된 한 덩어리의 메모리에 할당

- 비연속 할당(Non-contiguous allocation)
  - 각 프로세스마다 여러 덩어리로 나뉜 메모리를 할당

<연속 메모리 할당>
- 각 프로세스의 영역(코드와 데이터)을 연속된 메모리 공간에 배치
  - 메모리를 한 개 이상의 파티션으로 분할하고 프로세스당 하나의 파티션을 할당하는 방법
  - 할당 가능한 메모리 부족시 프로세스는 큐에서 대기
  - 연속 메모리 할당은 초기 운영체제에서 사용
    - MS-DOS와 같은 과거 운영체제 
      - 단일 사용자 단일 프로세스 시스템
      - 한 프로세스가 전체 메모리 독점
    - 가상 메모리 지원하지 않음





<연속 메모리 할당 기법>
- 고정 크기(fixed size partition) 할당
  - 전체 메모리를 고정된 크기의 n개의 파티션으로 분할, 각 프로세스마다 하나씩 할당
    - 수용가능 프로세스의 수 n 고정
  - 작은 프로세스의 경우 메모리 낭비 발생 가능, 큰 프로세스의 경우 실행 불가

- 가변 크기(variable size partition) 할당
  - 각 프로세스마다 가변 크기(그 프로세스와 같은 크기)의 연속된 메모리를 할당
    - 수용가능 프로세스 수 가변

<단편화(fragmentation) - 연속 메모리 할당 중 가장 큰 문제점>
- 요청을 만족하는 메모리 양이 존재하지만 프로세스에게 할당할 수 없는 '메모리 조각(hole)'이 생기는 현상
  - hole == 낭비되는 메모리

- 홀이 생기는 위치에 따른 종류
  - 내부 단편화
  - 외부 단편화






<내부 단편화(internal fragmentation)>
- 할당된 메모리가 요구된 메모보다 더 큰 경우 
  - 프로세스에 할당된 메모리 내부에 '사용할 수 없는 '홀이 생기는 현상
  - 파티션의 크기를 줄임으로 완화될 수 있으나 메모리 관리의 효율성은 떨어짐

<외부 단편화(external fragementation)>
- 요청을 만족하는 메모리 양이 존재하지만, '연속적'이지 않은 경우
  - 각 프로세스에 할당된 메모리들 사이에 사용할 수 없는 홀이 생기는 현상
    - 가변 크기의 파티션이 생기고 반환되면서 여러 개의 작은 홀 생성
    - 메모리 압축 기법 적용 가능

<압축(Compaction)>
- 불연속적인 hole들을 이동하여 외부 단편화 문제를 해결가능
- 한계 
  - 주소 relocation이 동적인 경우만 가능
  - 압축 시간으로 시스템 성능 저하될수도







<연속 메모리 할당의 구현>
- 하드웨어의 지원
  - CPU의 레지스터 필요
    - base 레지스터 : 할당된 물리 메모리의 시작 주소
    - limit 레지스터 : 현 프로세스에게 할당된 메모리 크기
    - 주소 레지스터 : 현재의 엑세스하는 메모리의 논리 주소
  - 주소 변환 하드웨어(MMU) 필요

- 운영체제의 지원
  - 각 프로세스별로 할당된 물리메모리의 시작 주소와 크기 정보 관리
    - 새 프로세스를 실행시킬 때마다 물리 메모리의 시작 주소와 크기 정보를 base 레지스터와 limit 레지스터에 적재
  - 비어있는 메모리 영역 관리

<연속 메모리 할당의 특징>
- 장점 
  - 논리 주소를 물리 주소로 바꾸는 과정이 단순
    - CPU의 메모리 액세스 속도 빠름
    - 운영체제게 관리할 정보량이 적어서 부담이 덜함

- 단점
  - 메모리 할당의 유연성이 떨어짐
  - 외부 단편화 발생





<홀 선택 알고리즘(동적 메모리 할당)>
- OS는 메모리가 요구될 때 적당한 홀을 선택해서 할당
  
  - 고정 크기 할당시 
    - 가용 파티션에 대한 리스트를 관리하고 이중에서 할당

  - 가변 크기 할당시
    - 가용 메모리 리스트(홀 리스트)를 통해 각 홀 마다 시작 주소와 크기 정보 유지
    - 이 홀 리스트에서 적절한 홀을 선택해 할당
      - 어떤 홀을 선택하느냐에 따라 성능이 달라짐

<홀 선택 알고리즘>
- Firs-fit(최초 적합)
  - 가능한 크기를 가진 첫 번째 hole에 할당
    - 가정 : 홀 리스트 주소에 대해 오름차순 정렬

- Best-fit(최적 적합)
  - 가능한 가장 작은 크기의 hole에 할당
    - 가정 : 홀 리스트는 홀 크기에 대해 오름차순 정렬
  - 할당 후 남은 공간을 최소화할 수 있음
    - 메모리 사용 효율이 높으나, 할당 때마다 홀 리스트 정렬 필요

- Worst-fit(최악 적합)
  - 가능한 가장 큰 크기의 hole에 할당
    - 가정 : 홀 리스트는 홀 크기에 대해 내림차순 정렬
  - 할당 후 남은 공간에 다른 프로세스의 할당 확률 높음







<일반적인 효율성 비교>
- Storage utilization
  - Best-fit >= First-fit > Worst-fit

- Speed
  - First-fit > Best-fit > Worst-fit