메모리 관리 전략

메모리 관리 전략

배경

• CPU는 PC가 지시하는 메모리로부터 다음 수행할 명령어를 가져온다.
  • 필요에 따라 메모리와 데이터를 주고 받는다.
• 명령어를 가져오면 해독하고 메모리에서 피연산자(operand)를 가져온다.
• 피연산자에 대해 명령어를 실행한 후, 계산 결과를 메모리에 저장한다.

기본 하드웨어

운영체제를 보호하기 위해, 각 프로세스가 독립된 메모리 공간을 갖도록 보장해야 한다.

1. 프로세스가 점유할 메모리의 주소 영역을 구한다.

   • 이를 base register라고 한다.

2. 프로세스가 차지할 수 있는 메모리의 영역엔 한계점이 있다.

   • 이 끝 점을 limit register로 관리한다.

• base <= CPU의 주소 < base + limit
  • 이 조건을 만족해야 운영체제가 메모리 영역을 안전하게 보호할 수 있다.
  • 만약 base 30000, limit 10000이면 CPU는 30000~39999까지 접근할 수 있다.
    • 이 영역을 벗어나면 운영체제는 치명적인 오류로 간주하고 trap을 발생시킨다.
• base, limit register는 커널 모드의 특권 명령을 통해서만 로드된다.
  • 운영체제만 커널 모드에서 수행되기 때문에, 오로지 운영체제만이 register의 값을 변경할 수 있도록 하는 것이다.

주소 할당

• 프로그램은 디스크에 존재한다.
• 프로그램이 실행되기 위해서는 디스크 -> 주 메모리에 적재되어야 한다.
• 디스크에서 주 메모리로 적재되기를 기다리는 프로세스들을 Input Queue라고 한다.

대부분의 시스템은 메모리의 모든 부분을 활용할 수 있도록 지원한다.

• 메모리가 0부터 시작한다 해도 프로그램이 0번지부터 올라올 필요는 없다.
• 프로그램의 주소 번역 과정은 아래와 같다.
  1. 원시 프로그램은 심볼 주소의 형태로 나타낸다.
     • 예를 들면 int count와 같은 형식이다.
  2. 컴파일러는 심볼 주소를 재배치 가능 주소로 바인딩한다.
     • 예를 들어 int count는 프로그램의 첫 번째 주소부터 14 byte 떨어져 있다는 식이다.
  3. 연결 편집기(Linkage Editor)나 적재기(Loader)는 이 재배치 가능 주소를 절대 주소로 바인딩한다.
     • 메모리 상 정확한 번지 수를 나타낸다.

명령어와 데이터 바인딩은 바인딩 시점에 따라 3가지로 분류한다.

1. 컴파일 시간 바인딩

   • 프로세스가 적재될 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성한다.
     • R번지부터 시작한다고 친다면, 그 위치부터 번역을 시작한다.
   • 만약 이 위치가 변경된다면 코드는 다시 컴파일 해야한다.

2. 적재 시간(load time) 바인딩

   • 프로세스가 적재될 메모리 위치를 컴파일 시점에 알 수 없다면, 컴파일러는 이진 코드를 재배치 가능 코드로 만든다.
   • 심볼 주소와 절대 주소 바인딩은 프로그램이 주 메모리로 적재되는 시간에 이루어진다.
   • 시작 주소가 변경되면 아무 때나 사용자 코드를 다시 적재하기만 하면 된다.

3. 실행 시간(Run time) 바인딩

   • 프로세스가 실행 중 메모리 내 세그먼트로부터 다른 세그먼트로 옮겨진 경우이다. 특별한 하드웨어를 이용해야 한다.

논리 주소, 물리 주소

• 논리 주소는 CPU가 생성하는 주소를 말한다.
• 물리 주소는 메모리가 취급하는 주소를 말한다(MAR에 주어지는 주소).
  • 컴파일, 적재 시간 바인딩 기법엔 논리, 물리 주소가 같다.
  • 런타임 바인딩엔 논리, 물리 주소가 다르다. 이런 경우 논리 주소를 가상 주소라고 한다.
• 동적 재배치 과정
  • 메모리 관리기(Memory Management Unit)에 의해 실행된다.
  • CPU -> 재배치(relocation) 레지스터 -> 메모리의 과정을 거친다.
  • CPU는 논리 주소를 가지고 있다.
  • 재배치 레지스터는 값을 가진다. CPU가 보내는 주소를 메모리에 보낼 때마다 재배치 레지스터의 값을 더한다.
    • 논리 주소가 340이고 재배치 레지스터의 값이 10000이면 실제 주소는 10340이다.

동적 적재(Dynamic Loading)

프로세스가 실행되기 위해선 프로세스 전체가 메모리에 올라가야 한다. 메모리 공간의 효율적인 이용을 위해서 동적 적재 기법을 활용한다.

1. 동적 적재는 실제 호출 전까진 메모리에 올리지 않고 디스크에서 대기한다.
   • 이 과정에서 각 루틴은 재배치 가능한 형태로 대기한다.
2. 먼저 main(프로그램의 진입점)이 메모리에 올라와 실행된다.
3. main이 다른 루틴을 실행하면 그 루틴이 메모리에 적재되었는지 조사한다.
4. 적재되어 있지 않다면 재배치 가능 연결 적재기(Relocatable linking loader)를 호출하고 요구된 루틴을 테이블에 기록한다.

동적 적재는 루틴이 필요한 경우에만 적재하기 때문에 효율적이다.

특히 오류 처리 루틴처럼 발생 빈도는 적어도 많은 양의 코드를 필요로 하는 경우 유용하다.

동적 연결 및 공유 라이브러리(Dynamic Linking & Shared Libraries)

• 동적 연결 라이브러리는 사용자 프로그램이 실행될 때 연결되는 시스템 라이브러리이다.
• 동적 적재의 개념과 비슷하다.
  • 동적 적재는 로딩이 실행까지 미뤄진다.
  • 동적 연결은 연결(linking)이 실행까지 미뤄진다.
• 동적 연결에서는 라이브러리를 부르는 곳마다 스텁(Stub)이라는 코드 조각이 생성된다.
  • 스텁은 라이브러리를 어떻게 찾을지를 알려준다.
  • 스텁이 실행되면 라이브러리 루틴이 메모리에 적재되었는지 검사한다.
    • 없으면 디스크에서 가져온다.
    • printf()를 10개의 프로세스에서 쓴다고 하면 printf() 라이브러리 코드는 하나만 있어도 된다.

이러한 동적 연결은 라이브러리 루틴을 바꿀때 유용하다. 라이브러리는 어느 순간 갑자기 변경될 때가 있다. 그렇게 되면 이 라이브러리를 사용하는 모든 프로그램은 새로운 버전으로 업데이트된다.

• 다른 버전의 라이브러리 로딩을 막기 위해 버전 정보가 프로그램, 라이브러리에 포함된다.
• 각 프로그램은 라이브러리의 어느 버전을 사용할지를 결정한다. 전략적으로 옛 버전을 활용할 수도 있다.
• 라이브러리가 많이 수정되었다면 버전 번호를 증가시켜서 사용한다.
• 이러한 시스템을 공유 라이브러리라고 한다.

스와핑(Swapping)

프로세스는 실행 중 임시로 예비 저장장치(backup store)에 보냈다가 다시 메모리로 돌아올 수 있다. 이 과정을 스와핑이라고 한다. 스와핑을 이용하면 동시 실행이 가능해지기 때문에 다중 프로그래밍 정도가 증가한다.

기본 스와핑

메인 메모리와 예비 저장장치 사이에서 프로세스를 이동시킨다.

• 실행 준비가 된 모든 프로세스를 레디 큐에 갖고 있어야 한다.
• CPU 스케줄러는 다음 프로세스를 고를 때 디스패처를 호출한다.
• 디스패처는 레디 큐의 다음 프로세스가 메모리에 올라왔는지 확인한다.
  • 없다면 디스크에서 불러들인다.
• 프로세스를 위한 공간이 메모리에 없다면 메모리를 정리한다.
  • 현재 메모리에 올라와 있는 프로세스를 내보낸다. 이를 swap out이라고 한다.
  • 그 후 원하는 프로세스를 불러들인다.

사용자 프로세스의 크기는 100 MB, 예비 저장장치는 초당 50 MB의 전송 속도를 가졌다고 할 때 걸리는 시간은 100 / 50 = 2초이다.

• Swap 소모 시간은 2초이고, swap in, swap out을 해야 하므로 총 swap 시간은 4초이다. (기타 요소는 무시)
• 동적 메모리를 요구하는 시스템에선 request memory, release memory와 같은 시스템 호출이 필요하다
  • 메모리 요구사항의 변화가 있을 때마다 시스템에게 알려야 효율적으로 스왑 시간을 줄일 수 있다.
  • 스왑 시간을 줄이기 위해서는 실제로 사용하는 부분만을 스왑한다.

모바일 시스템에서의 스와핑

모바일은 스와핑을 지원하지 않는 것이 일반적이다.

• 모바일 장치는 하드디스크보다 플래시 메모리를 사용한다.
  • 저장 공간이 줄어들기 때문이다.
• iOS는 App에게 할당한 메모리를 자발적으로 반환하도록 요청한다.
• Android는 iOS와 유사하다. Free memory가 부족하면 프로세스를 종료시킬 수 있다. 프로세스 종료 전 Android는 app의 상태를 플래시 메모리에 저장하여 나중에 빠르게 시작할 수 있게 한다.

연속 메모리 할당

연속 메모리 할당 시스템에서 각 프로세스는 연속된 영역을 차지한다.

• 인터럽트 벡터는 0번지에 위치한다.

메모리 보호(Memory Protection)

• 프로세스가 소유하지 않은 메모리 영역에 대해 접근하지 못하게 해야 한다.
• 상한(limit) 레지스터, 재배치(Relocation) 레지스터가 있으면 가능하다.
  • 재배치 레지스터는 가장 작은 물리 주소값, 상한 레지스터는 논리 주소 범위 값을 저장한다.
• CPU -> 상한 레지스터 -> 재배치 레지스터 -> 메모리
  • CPU는 논리 주소를 갖고 있다.
    • 논리 주소 < 상한 레지스터가 참이면 다음으로 넘어간다.
    • 거짓이면 Trap(주소 오류)이 발생한다.
  • 논리 주소에 재배치 레지스터의 값을 더하면 실제 물리 주소를 구할 수 있다.

메모리 할당(Memory Allocation)

1. 최초 적합
   • 첫번째 가용 공간 할당
   • 충분히 큰 공간을 찾으면 검색 종료 및 할당
2. 최적 적합
   • 사용 가능한 공간 중 가장 작은 공간 탐색
   • 리스트가 크기 순으로 정렬되어야 효율적
   • 그렇지 않으면 전체 리스트 탐색
3. 최악 적합
   • 가장 큰 가용 공간 탐색
   • 남은 공간이 크기 때문에 다른 프로세스를 위해 사용 가능
   • 최적 적합과 마찬가지로 크기 순으로 정렬되어야 효율적

• 일반적으로 최초 적합, 최적 적합이 최악 적합보다 효율적이다.
• 속도는 최초 적합이 빠르다.

단편화(Fragmentation)

프로세스가 적재되었을 때 남는 작은 조각들을 단편화라고 한다.

• 외부 단편화는 프로세스가 적재되며 사용하기 어려운 작은 공간을 말한다.
  • 100 MB 공간에 70 MB 프로세스를 할당하며 30 MB가 남은 경우
• 외부 단편화는 적재된 프로세스에 비해 작업의 양이 너무 작아 내부에 남는 공간을 말한다.
  • 최소 100 MB를 적재해야 하는 시스템에서 70 MB 프로세스를 할당하면 100 MB 전체에 적재가 되지만 30 MB가 남는다.
• 최초/최적 적합 중 어느 것을 사용하느냐에 따라 단편화의 크기에 영향을 줄 수 있다.

단편화 해결 기법

• 압축
  • 남는 공간을 전체적으로 재배치하여 한 곳으로 모으고 가용 가능한 큰 공간으로 변환한다.
• 통합
  • 분산된 메모리 공간을 인접한 공간인 것처럼 합쳐 큰 메모리 공간으로 변환한다.
• 세그멘테이션, 페이징 기법
  • 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나눈다.
  • 나뉜 공간을 필요한 크기만큼만 할당하여 사용한다.