Memory Management

Memory Management

Multitasking을 위해서는 대상이 되는 프로그램들을 메모리에 올려놓고 실행해야 한다.

이를 위해서 memory management가 필요하다.

 

Memory management는 운영체제에서 가장 복잡한 것 중 하나이다.

 

목적

Memory management의 일반적인 목적는 다음과 같다.

• 프로세스 별로 하나의 contiguous, protected 메모리 공간을 배정한다.
• 물리적으로 주어지는 메모리보더 더 많고 분리된 메모리를 프로세스마다 배정한다.

 

Tricks

• address translation
  • paging, segmentation 
  • address translation을 통해서 noncontiguous한 physical emmory allocation을 효율적으로 관리할 수 있다.
• demand paging
  • physical memory보다 더 많은 공간을 사용할 수 있다.

 

Address Binding and Memory Allocation

프로세스 실행을 위한 모든 instruction과 data에 memroy address를 할당하는 것을 address binding이라 한다.

이를 효율적으로 관리하는 것이 memory management의 가장 중요한 목적이다.

 

Address binding은 3 단계에서 발생한다.

• compile time
  
  • memory location이 사전에 알려져 있을 경우에 사용한다.
  • absolute code가 생성될 수 있다.
  • starting location이 변경되면 반드시 다시 컴파일 해야 한다.
  • virtual memory를 사용하지 않는 embedded system에서 사용된다.
• load time
  
  • memory location이 compile time에 확정되지 않은 경우, 컴파일러가 relocatable code를 생성한다.
  • 컴파일 할 때는 주소값이 확정되지 않고, 실행하기 위해서 memory에 load 할 때 주소가 확정된다.
  • 일반적인 환경에서 사용된다.
• execution time
  • 프로세스가 실행하는 중에 다른 memory segment로 옮겨질 수 있는 경우, binding이 runtime 때까지 delay 된다.
  • 주소값이 실행을 할 때 확정된다.
  • windows의 DLL(Dynamic Linked Library)나, UNIX의 *.SO 파일이 있다.

 

---

Contiguous Memory Allocation

본 노이만 모델에서는 PC(program counter)가 연속적으로 증가하며 프로그램이 실행된다.

따라서 연속된 메모리 공간을 할당해야 한다.

 

프로세스가 메모리에 올라오면, hole(이용 가능한 메모리 공간)을 할당한다.

이를 위해 운영체제는 allocated parition과 free partition(hole)에 대한 정보를 유지해야 한다.

 

Contiguous memory allocation은 운영체제의 memory management에 많은 제약을 준다.

더 효율적으로 관리하지 못하고, fragmentation problem(주로 external fragmentation)을 야기한다.

 

실제 운영체제는 address translation을 통해서 noncontiguous memory allocation을 사용한다.

 

Fragmentation Problem

Fragmentation은 사용되지 못하고 낭비되는 공간을 말한다.

 

2가지 종류가 있다.

• external fragmentation
  • hole이 너무 작아서 배정되지 못하고 낭비되는 경우
  • 전체 메모리 공간은 request를 충족할 수 있지만, contiguous하지 않고 쪼개져있기 때문에 할당할 수 없는 경우이다.
• internal fragmentation
  • 배정된 공간 내부에서 사용되지 못하고 낭비되는 경우
  • 할당된 메모리 공간이 요청한 메모리 공간보다 더 커서 낭비되는 경우이다.

 

Contiguous Memory Allocation Algorithom

3가지 알고리즘이 존재한다.

 

best-fit과 worst-fit 중 어느 것이 더 효율적인지는 모른다.

다만, speed와 storage utilization 관점에서는 first-fit과 best-fit이 worst-fit 보다 우수하다.

 

• first-fit
  • 첫번째 나오는 메모리 공간을 할당할 수 있는 충분한 크기의 hole을 할당한다.
  • 속도가 가장 빠르다.
• best-fit
  • 들어갈 수 있는 충분한 크기의 hole들 중 가장 작은 hole을 할당한다.
  • 매번 끝까지 스캔해야 하기 때문에 속도가 느리다.
  • 직관적으로 봤을 때 메모리 공간의 효율이 가장 좋다. 
  • 전체적으로 봤을 때 메모리 공간의 효율이 좋은지는 모른다.
    • 프로세스 생성/종료가 반복되는 과정을 거쳤을 때 여러 작은 hole들이 여러군데 나눠져있을 수 있다.
    • 이는 효율이 나빠짐을 의미한다.
• worst-fit
  • 들어갈 수 있는 충분한 크기의 hole들 중 가장 큰 hole을 할당한다.
  • 매번 끝까지 스캔해야 하기 때문에 속도가 느리다.
  • 직관적으로 봤을 때는 메모리 공간의 효율이 좋지 않다.
  • 전체적으로 봤을 때 메모리 공간의 효율이 좋을 수도 있다.
    • 가장 큰 메모리를 배정하는 것은 나중에 돌려받는 공간이 큰 hole임을 의미한다.
    • 이는 오랜 시간이 지나도 큰 hole이 있을 가능성이 크기 때문에 externel fragmentation이 줄어들 수 있다.

 

Fragmentation 해결책

compactition을 통해 externel fragmentation를 해결할 수 있다.

• 모든 free memory가 하나의 큰 block이 되도록 memory contents의 순서를 변경한다.
• compaction은 relocation이 dynamic하고 execution time에 수행될 때만 가능하다.

 

실제 운영체제는 address translation을 통해서 noncontiguous memory allocation을 사용한다.

 

---

Non-Contiguous Allocation

프로그램은 virtual address (logical address)를 사용한다.

 

운영체제나 하드웨어는 virtual address를 physical address (real address)로 translation 한다.

이를 address translation이라 한다.

 

Logical address는 CPU가 발생시키는 address이다.

Physical address는 실제 memory hardware에서의 address이다.

 

MMU를 이용해서 address translation을 한다.

MPU를 이용해서 memory protection을 한다.

 

Address Translation의 장점

• noncontiguous memory allcation이 가능하다.
  • memory allocation이 매우 유연해진다.
• memory protection, sharing을 효율적으로 할 수 있다.

 

MMU (Memory Management Unit)

MMU는 virtual address를 physical address로 매핑하는 hardware device이다.

 

User program은 logical address를 다루고, physical address에 대해서는 모른다.

CPU는 logical address를 내고, 메모리는 physical address를 본다.

따라서 이를 변환해야 한다.

 

Dynamic Relocation Using Relocation Register

MMU의 간단한 구현은 다음과 같다.

 

relocation register는 변환할 값을 가지고 있다.

physical address = logical address + relocatino register로 변환된다.

 

Hardware Support for Relocation and Limit Register

limit register를 이용해서 상한값과 비교하는 부분을 MPU(Memory Protection Unit)이라고 한다.

이를 이용해서 memory protection을 보장한다.

limit register에서 상한값과 비교해서 이를 넘어가면 에러를 발생시킨다.

 

요즘의 CPU는 MMU에 MPU 기능을 합쳐서 제공한다.

 

Memory Allocation

Noncontiguous memory allocation은 두 가지 방법을 이용한다.

• segmentation
  • segment 단위로 메모리에 할당한다.
  • process memory = code segment + data segment + stack segment ...
  • segment는 서로 다른 크기를 가질 수 있다.
  • fragmentation이 감소하긴 하지만 여전히 존재한다.
  • 각 segment들의 시작 주소들은 각 relocation은 각 relocation register에 저장된다.
    • 때문에 여러 개의 segment가 존재하면 relocation register도 그 수만큼 필요하다.
    • 만약 프로세스가 3개의 segment(code, data, stack)으로 이루어진다면 3개의 relocation register가 필요하다.
• paging
  • page 단위로 메모리에 할당한다.
  • process memory = page + page + page ...
  • page는 동일한 크기의 메모리 영역이다.
  • fragmentation이 발생하지 않는다.
  • 각 프로세스마다 배정될 수 있는 page의 최대 개수 만큼 relocation register가 필요하다.
    • 너무 많은 공간을 요구하면 많은 register가 필요하기 때문에 CPU 가격이 올라가고 가성비가 떨어지게 된다.