운영체제(8) - Memory Management Strategies(1)

‘운영체제’를 공부하여 정리한 내용입니다.

1. Background

기본 하드웨어

• CPU는 자신의 레지스터, 그리고 메인메모리에만 접근이 가능하다.
  • 이는 디스크에는 접근이 불가능하다는 의미로, 디스크의 정보가 필요하면 무조건 메인메모리로 데이터를 옮겨야 한다.
• CPU가 레지스터에 접근할 때는 빠르게 접근할 수 있지만, 메인메모리에 접근할 때는 상당히 많은 시간이 필요하다.
  • 이 때, 메모리 접근에 시간이 소요되면서 Stall 현상이 발생한다.
    • 운영체제(5) - CPU Scheduling(2) - Multicore Processors에서 논의한 바 있다.
  • 그렇기 때문에 자주 사용하는 메인메모리의 정보는 CPU와 가까운 곳에 있으면 좋다(즐겨찾기 같은 느낌으로)
  • 이렇게 자주 사용하는 가까이 임시로 저장하는 빠른 속도로 접근할 수 있는 메모리를 Cache라고 한다.
• 각각의 프로세스는 독립된 메모리 공간을 가진다.
  • 이를 위해서 특정 프로세스만 접근할 수 있는 legal 메모리 주소 영역을 설정한다.
  • 이는 프로세스를 다른 불법적인 접근으로부터 막는 역할을 한다.
• 가장 단순하게 프로세스들의 영역을 나누는 방법을 Base와 Limit을 설정하여 연속적인 메모리 공간을 프로세스에게 배당하는 것이다.
  • 이 Base와 Limit은 각각 담당하는 레지스터가 있다.
  • CPU 하드웨어는 User모드에서 만들어진 모든 주소와 레지스터를 비교하여 각각의 공간을 보호한다.
  • 이 때, 겹치거나 하는 상황이 발생하면, OS는 이를 에러로 간주하고 Trap을 발생시킨다.

Address Binding

• 메모리 관리 기법에 따라, 프로세스는 실행하는 동안 디스크와 메인 메모리 사이를 왔다갔다 할 수 있다.
  • 이 때, 디스크에서 메인메모리로 들어로는 것을 기다리고 있는 프로세스들의 집합은 input queue를 형성한다.
• 대부분의 시스템은 User 프로세스가 메모리 내 어느 부분으로도 올라올 수 있도록 지원한다. (폰노이만 구조)
  • 다 그런 것은 아니다. 가끔은 코드와 데이터가 올라갈 수 있는 부분을 구분하기도 한다. (하버드 구조)
  • User 프로세스의 주소가 0x0000번지부터 시작한다고 해서, 메모리의 0x0000번지부터 올라와야 할 필요는 없다.
• 주소가 바인딩되는 과정을 중요한 부분만 빼서 정리해보자
  • 원시프로그램은 symbol로 주소를 표현한다: 변수 등.
  • 이를 컴파일러가 해석하면, 이 symbol을 재배치 가능 주소(상대적 주소)로 바인딩한다: 모듈의 첫번째 바이트로부터 네번째 바이트(상대적)
  • 이를 링커나 로더가 위의 재배치 가능 주소를 절대 주소로 바인딩한다.
• 메모리 주소 공간에 바인딩이 이루어지는 시점에 따라 다음과 같이 구분한다.
  • Compile time Binding
    • 컴파일 해서 나오는 파일 자체가 이미 메인메모리 주소까지 가지고 나오는 경우다.
    • 지금은 쓰지 않는다. 유연성이 없다.
  • Load time Binding
    • 메인 메모리로 적재되는 순간에 결정하는 것이다.
    • 이는 적재하는 순간마다 다른 메인메모리 주소 공간을 할당받게 된다.
  • Execution time Binding
    • 프로세스가 실행하는 중간에 메모리 내의 한 Section에서 다른 Section으로 옮겨진다면, 이는 실행시간 동안 메인메모리 안에서 주소가 바뀌는 것이다.
    • 나중에 정리하겠지만 이 Section은 Segment로 Segmentation fault의 그 Segment다.
    • 이게 가능하기 위해서는 특별한 HW의 지원이 필요하다.

Logical vs. Physical Address Space

• 주소의 종류
  • Logical Address: CPU가 생성하는 주소
  • Physical Address: 메인 메모리가 취급하는 주소

• 바인딩 기법에 따른 차이점

  • Compile time Binding, Load time Binding의 경우는 위의 두 주소가 같다.
    • Load time Binding의 경우도 프로세스가 메모리에 적재될 때 주소가 정해지는 것이기에, Logical과 physical을 나눌 필요가 없다.
  • Execution time Binding 만 위의 두 주소가 다르다.
    • 실행 시간동안 계속 변하기에 매핑하는 규칙을 가지고 있어야 한다.

• Logical Address를 Physical Address로 바꾸는 작업이 필요하다.

  • 이를 돕는 HW는 MMU(Memory Management Unit)로 앞서 얘기한 Base와 Limit을 이용해서 변환을 돕는다.
  • 여기서는 Base 레지스터를 relocation 레지스터라고 부른다.
• User Program은 Physical Address를 절대 알 수 없다!
  • 우리가 프로그래밍해서 출력하는 모든 포인터 값도 결과적으로는 CPU의 시점에서 보는 값이다.
  • 그렇기에 이 때 보이는 주소값은 Logical Address라는 것을 쉽게 알 수 있다.
  • 결과적으로 우리는 일반적인 방법으로 Physical Address를 직접 아는 것은 할 수 없다.

Dynamic Loading

• 필요성

  • 프로세스가 실행되기 위해서는 프로세스 전체의 크기가 가용 가능한 메모리 크기를 벗어나면 안된다.
  • 메모리를 효율적으로 쓰기 위해서는 쓰지 않는 루틴은 우선 메모리에 올리지 않는 방식을 생각해볼 수 있다.

• 위의 이유로 Dynamic Loading이라는 작업을 한다.

• 과정

  • 먼저 main 프로그램이 메모리에 올라와 실행된다.
  • 이 루틴이 다른 루틴을 호출하게 되면, 호출된 루틴이 메모리에 있는지를 검사한다.
  • 없다면, Relocatable linking loader 등을 이용해서 요구된 루틴을 메모리로 가져온다.
  • 그리고 작업을 이어나간다.

동적 링크 및 공유 라이브러리

• 필요성
  • 컴퓨터구조(2) - 명령어: 컴퓨터 언어(2) - 프로그램 번역과 실행 참고
  • 위의 글에서 필요성에 대해서 논의해두었다.
• 특징
  • 프로그램이 Load될 때는 라이브러리가 매핑되어 있지 않다가, 필요할 때 관련 Object 파일을 찾아가서 메모리에 적재하여 사용한다.
  • 한번 적재되면 그 후로는 메모리에서 사라지지 않는 이상 계속 사용이 가능하다.
  • 중요: 가장 중요한 것은, 이렇게 라이브러리 루틴이 메모리에 올라오면 동일한 루틴을 사용하는 다른 프로세스도 이 공간에 접근하여 루틴을 사용할 수 있게 된다.
    • 이는 보안 문제가 직결되기에, OS의 지원이 필요한 작업이다.

2. Swapping

필요성

• 많은 프로세스를 실행시키기 위해서는 메모리를 효율적으로 하용하는 것이 중요하다.
• 이 때, 우리는 프로세스들을 실행 도중에 임시로 보조 메모리에 빼두었다가 다시 사용할 때 불러오는 등의 작업을 할 수 있다.
• 이를 Swapping이라고 한다.

과정

• Dispatcher가 현재 가져와야 하는 프로세스가 메인 메모리에 올라와 있는지 확인한다.
• 이 때, 없다면, 이 프로세스를 가져오기 위해 메인 메모리의 공간을 확보한다.
• 그렇게 임시로 특정 프로세스는 sWap out하고 스케쥴링 된 프로세스는 swap in한다.

3. Contiguous Memory Allocation

Memory Protection

• 메모리 변환과 메모리 보호는 동시에 이루어진다.
  • Limit register: Logical Add가 Limit을 넘어가지 않았는지 확인 필요 (Logical Add < Limit)
  • Base(relocation) register: Logical Add에서 Physical Add메모리 변환에 사용 (Logical Add + Base = Physical Add)
  • 위의 레지스터들은 Dispatcher가 Context Switch를 진행할 때, 그 일환으로 가져온다.

Memory Allocation

• 간단하게 공간을 할당하는 방법은 메모리를 똑같은 고정된 크기로 Partition하는 것이다.

  • FPM: Fixed Partition Multiprogramming
  • 이 때 만들어지는 Partition에는 각각 한 프로세스를 적재할 수 있게 되고, 전제 Partition의 개수가 multiprogramming degree를 결정하게 된다.
  • 이 방법은 지금에 와서는 더이상 사용하지 않는다.

• 다음 방법은 메모리를 분할하지 않고 하나의 영역으로 고정한 뒤, 프로세스에 따라 분할의 크기를 정하는 것이다.

  • VPM: Variable Partition Multiprogramming
  • 이 방법은 전체의 메모리 영역을 여러 가능성의 Partition의 부분집합으로 이루어졌다고 보는 것이다.
  • 과정
    • 프로세스 확인
    • 현재 사용가능한 메모리 공간(Hole이라고 부른다)이 어디에 얼마나 있는지 확인
    • 공간 할당

  • 위의 과정을 위해서 OS는 항상 가용 공간의 크기들과 Input Queue를 유지

    • 이 때 Input Queue 내부 순서는 재배치 될 수 있는데, 예를 들어 가용공간 중에 현재의 프로세스를 올릴만큼 충분한 공간이 없을 경우이다.
  • 어떤 공간을 할당할 것인가에 대한 문제는: Dynamic Storage allocation problem의 한 예가 된다.
    • First-fit: 처음 찾은 충분히 큰 메모리 공간에 프로세스 배치
    • Best-fit: 남은 Partition들 중에서도 프로세스를 올리기에 충분한 것들 중, 가장 작은 것 선택
    • Worst-fit: 남은 Partition들 중에서도 프로세스를 올리기에 충분한 것들 중, 가장 큰 것 선택

Fragmentation

• External Fragmentation

  • 남은 Hole(자유공간)들을 모두 합쳤을 때, 충분히 현재 올리고 싶은 프로세스를 올릴 수 있지만, 이 모든 hole들이 여러군데로 찢어져서 존재하여 프로세스를 올리지 못하는 경우 External Fragmentation이 발생했다고 표현한다.

• Internal Fragmentation

  • 일반적으로 위의 방식을 사용할 때는 메모리를 먼저 아주 작은 공간으로 Partitioning하고 프로세스가 메모리 공간을 요청하면 이 작게 분할된 Partition의 정수 배로만 해주게 되는 것이 일반적이다.
  • 이 때, 이 정수배의 크기와 프로세스의 실제 크기에는 작게 분할된 Partition의 크기보다 작은 공간이 남게 되는데, 이 때 남는 공간의 크기(프로세스와 배치되는 메모리 공간과의 크기 차이)를 Internal Fragmentation이라고한다.

• External Fragmentation을 해결하는 방법

  • 조각 모음을 하듯이 메모리 공간을 정리해서 현재 올라와 있는 프로세스들을 압축한 공간으로 옮기는 방식
    • 비용이 너무 많이 들고, Execution time Binding이 가능할 때만 가능
  • 비연속적인 공간 할당
    • 위에서 논의하던 방식은 어쨌든 연속적인 공간을 배치하는 것이었는데, 일정 Partition으로 나눈 공간들을 비연속적으로 할당시켜주면 External Fragmentation 문제가 어느정도 완화될 수 있게 된다.
    • 이 해결책을 기반으로 고안된 방법이 이제부터 논의할 Paging과 Segmentation 기법이다.