[운영체제] 메모리

 

 일반적으로 컴퓨터를 사용할 때 우리는 디스크에 저장된 이진코드와 메모리 상에서 실행중인 대상 둘 다 프로그램이라는 표현으로 퉁치지만, 컴퓨터 과학에서 프로그램과 프로세스는 명확히 구분된다. 프로세스는 메모리 상에서 실제로 동작하는 대상으로, 프로그램의 코드에 여러 자원을 할당하여 실제로 실행하는 것이다.

 과거의 컴퓨터는 한번에 하나의 프로세스만 실행할 수 있었다. 그러나 기술의 발전에 따라 CPU 와 메모리 사이의 동작 속도 사이에 큰 간격이 발생했다. 따라서 CPU가 메모리의 정보를 읽어오는데 많은 지연 시간이 발생하게 되었는데, 이를 stall이라고 한다. 이러한 낭비되는 시간을 줄이기 위해서 메모리에 여러개의 프로세스를 적재하고 경우에 따라 CPU을 돌려 쓰는 멀티 프로그래밍 기법이 고안된다.

 초기 프로세스는 멀티 프로그래밍 기반으로 메모리에 전체 코드를 순차적으로 할당되었는데(연속 적재), 전체 코드를 한번에 관리하려다 보니 외부 단편화 및 내부 단편화 현상이 발생했다. 이러한 메모리 상의 낭비를 막기 위해서 코드를 기능 혹은 특정 단위 별로 쪼개 관리하는 기법이 고안된다 ( 세그멘테이션, 페이징 ).

메모리 보호

 프로세스는 자신에게 허가된 영역의 메모리만 접근할 수 있다. 이러한 정보는 base 와 limit의 조합으로 나타난다. 프로세스가 접근 가능한 마지막 주소는 base+limit 이 된다.

• base : 프로세스의 기본 주소
• limit : 프로세스의 길이 ( 접근 가능한 마지막 위치 )

이러한 방식의 접근은 physical address 말고도 logical address space 에서도 사용된다.

하드웨어 수준에서 메모리 보호는 다음과 같이 수행될 수 있다.

 특정 프로세스가 base 및 limit 변수의 값을 가지고 있으므로, 해당 프로세스가 base 이상 base+limit 미만의 주소에 접근하는 경우에만 메모리 접근을 허가한다. 그렇지 않은 경우 segment fault가 발생하게 된다.

Address binding

 프로세스는 디스크 상에 저장된 프로그램 코드를 메모리에 적재하고, 이를 실행시켜 동작한다. 멀티 프로그래밍 이전의 환경에서는 메모리 0번 주소(물리적 주소)와 프로그램의 0번 주소를 단순히 대응하여 적재하면 그만이므로 데이터를 메모리 상에 바인딩하는 부분에 있어서 문제가 없었으나, 멀티 프로그래밍 기법을 도입하면서 메모리에 다양한 프로세스를 동시에 적재하게 되면서 메모리의 특정 주소에 프로세스를 적재하기 위한 기법이 필요해졌다.

프로그램의 생애동안 다음과 같은 주소들을 가질 수 있다.

1. 소스코드 상에 드러난 주소
2. 컴파일 과정에서 재배치된 주소
3. 링커 및 로더에 의해 물리적 메모리 상에 배치된 주소

 각각의 주소는 하나의 주소 공간을 다른 주소 공간으로 매핑시킨다. 데이터 및 instruction을 메모리 주소에 binding은 3개의 과정을 거치게 된다.

1. Compile Time
   : 컴파일 시점에 프로세스가 적재될 메모리 상의 주소를 알고 있는 경우, absolute code가 생성될 수 있다. 생성된 코드는 해당 프로세스의 메모리 주소를 시작으로 하게 되며, 프로세스의 주소가 달라지면 다시 컴파일러를 수행하여 해당 위치를 수정하게 된다.
2. Load Time
   : 컴파일 시점에 메모리 상에 프로세스가 위치할 주소를 특정할 수 없다면, 컴파일러는 relocatable code을 생성할 수 있다. 실제 바인딩은 프로그램이 메모리 상에 로드되는 시점에 링커 및 로더에 의해 수행된다.
3. Execution Time
   : 프로세스가 실행되는 동안 DLL과 같은 라이브러리 등을 추가적으로 호출하여 바인딩할 수도 있다. 보통 하나의 DLL을 메모리 상에 띄워두고 해당 정보를 다양한 프로세스가 공유할 수 있게 되므로 메모리 중복이 감소한다는 장점이 있다.

Logical & Physical Address Space

• Logical address 
  : CPU에 의해 생성된 주소로, CPU가 이해하는 가상 주소. 실제 메모리의 물리적 구조와 대응되지는 않는다. 
• Physical address
  : 메모리 상의 실제 물리적 주소. 

compile time & load time 에서 logical & physical address은 동일하나, execution time에는 주소가 달라진다.

• Logical address space : 프로그램상에서 만들어지는 논리적 주소의 집합.
• Physical address space : logical address에 대응되는 물리적 주소 집합.

Memory Management Unit

 런타임 시점에 virtual 메모리를 실제 메모리로 대응시키는 하드웨어 장치. base - limit 개념을 사용하지만, base 레지스터를 relocation register이라고 부른다. 

 프로세스의 logical memory에 relocation register 만큼 더하면 메모리 상의 physical address로 대응된다. 이런 동작은 유저가 사용하는 프로그램들이 logical address을 기반으로 동작하는데 비해 실제로는 각각의 프로세스들이 메모리 상의 실제 주소인 physical address에서 실행되어야 하기 때문에 필요하다.

 MMU는 CPU가 이해하는 논리적 주소를 실제 메모리의 물리적 주소로 변환해주는 기기를 의미한다. 논리 주소를 물리적 주소로 대응시키기 위해 상호 관계가 담긴 테이블 등을 이용하여 실제 물리적 메모리 주소를 반환한다.

Dynamic Loading

 프로그램이 실행되려면 메모리 상에 적재되어야 한다. 그렇지만 전체 프로세스를 기준으로 따졌을 때 초기에 모든 프로그램 코드가 메모리 상에 적재될 필요는 없다. 가령 특정 프로그램에서 거의 사용되지 않는 기능이 있다고 생각해보자. 해당 기능은 사용률이 낮으므로 메모리상에 상주시키기에는 자원 낭비이다. 이런 경우, 차라리 해당 기능이 필요한 시점에 프로그램 코드를 읽어와 실행하는 것이 나을 것이다.

 동적 로딩을 이용하면 특정 루틴이 필요한 시점에 관련된 코드를 메모리 상으로 읽어오게 된다. 코드가 자주 실행되지 않는 경우, 혹은 메모리 공간이 부족한 상황에서 최적화를 목적으로 사용될 수 있다. 운영체제 없이도 가능하거나, 관련된 라이브러리를 통해 기능을 지원한다.

Dynamic Linking ( Shared Libraries )

• Static Linking : 실행 이전에 시스템 라이브러리나 프로그램 코드를 이진 프로그램 형태로 연결해두는 것으로, 이진형태로 구성된 각 코드들을 하나의 파일로 묶는 역할을 한다.
• Dynamic Linking : 실행 시점까지 라이브러리의 링킹 과정을 미뤄두는 방식. 

 Static Linking 방식은 실행 시점에 관련된 모든 코드를 복사하여 하나의 파일 내에 저장한다. 해당 코드는 코드가 복사된 프로그램 내에서만 유효하며, 다른 프로그램에서는 해당 코드를 사용하지 못한다. 예를 들어 printf 함수를 프로그램 A에서 static linking 방식으로 연결하는 경우, A 프로그램 내에 printf 함수와 관련된 기능이 포함되지만, 다른 프로그램 B에서는 해당 기능에 접근할 수 없다.

 따라서 A와 B가 모두 printf 을 내부적으로 사용하면 각각의 프로세스에 대한 printf 가 존재하게 되므로 코드 중복에 의한 메모리 낭비가 발생한다고 볼 수 있다. Dynamic Linking은 코드의 중복 및 라이브러리 재사용을 목적으로 이용한다. 해당 환경에서 라이브러리는 메모리상에 하나만 존재하며, 다수의 프로세스들은 해당 라이브러리를 stub을 통해 참조하여 사용할 수 있다.

 stub은 메모리에 상주하는 적절한 라이브러리 루틴을 찾기 위해 사용되는 작은 코드 조각으로, 실행 시점에 stub이 가리키는 루틴과 자신의 주소를 바꿔치기하고, 해당 루틴을 실행한다. 따라서 라이브러리 자체는 메모리 상 어딘가에 하나만 저장되어 있어도 괜찮다.

 Dynamic Linking을 사용하는 경우, 라이브러리의 버전 관리가 중요하다. 가령 A 프로그램은 1.3 버전 코드를 사용하지만 B 프로그램의 경우 2.7 버전의 라이브러리를 사용한다고 가정하자. 두 프로그램은 동일한 라이브러리를 사용하지만 버전이 다르다. 따라서 버전 선택에 따라 프로그램들이 호환될 수도 있고, 안될 수도 있다. 따라서 라이브러리들에 대한 버전 관리를 철저하게 수행하여 버전 차이에 의한 문제 발생을 방지해야 한다.

---

Contiguous Allocation (연속 적재)

 프로세스와 관련된 자원들을 메모리 상에 연속적으로 적재하는 방식.

• 상주 운영체제는 메모리 상의 낮은 주소에 존재한다.
• 유저의 프로세스는 메모리 상의 높은 주소에 위치한다.
• 각각의 프로세스는 메모리 상의 연속된 단일 섹션 내에 속한다.

 relocation register은 유저의 프로세스가 접근하는 영역을 막거나, OS 코드 및 데이터를 변경하는데 사용된다. 후자의 경우, 운영체제가 잘 사용하지 않는 주변장치와 관련된 코드까지 유지할 필요는 없으므로 ( ex 자주 사용하지 않는 장치의 드라이버 ) 대응되는 코드를 제거하면서 운영체제 자체의 크기도 변할 수 있다. 

---

고정 파티션 ( Fixed Partition )

 메모리를 효율적으로 사용하기 위한 발상 중  메모리를 특정 크기의 파티션으로 나누는 방식이 등장했다. 해당 파티션의 개수를 얼마나 두는지에 의해 시스템의 멀티프로그래밍 정도(degree of multiprogramming)가 정해진다.

 hole 은 사용 가능한 ( 현재 할당되지 않은 ) 메모리의 블럭을 의미한다. 초기에는 하나의 홀만 존재하지만 시스템이 동작함에 따라 다양한 프로세스가 파티션을 차지하므로, 사용 가능한 파티션인 홀은 다양한 위치에 분산되어 존재한다.

• 균등 고정 파티션
  : 메모리 영역을 고정된 크기의 파티션들로 나누고, 각각의 프로세스를 해당 파티션에서 실행한다.
  
  • 미리 지정된 크기보다 큰 프로세스는 실행할 수 없다.
  • 지정된 크기보다 작은 프로세스는 메모리 공간을 낭비하는 셈이 된다.

 따라서 메모리 효율성을 위해 다양한 크기의 파티션을 두는 방식이 고안된다.

• 비균등 고정 파티션
  : 메모리 영역을 다양한 크기의 파티션으로 나눈다. 각각의 프로세스는 해당 파티션에서 실행된다.
  • 고정 크기의 단점은 동일하지만, 특정 프로세스에게 가장 적합한 메모리를 선택함으로써 균등 크기 파티션에서 발생했던 문제보다는 덜하다. 그렇지만 메모리 문제가 발생하지 않는 것은 아니다.

---

Fragmentation ( 단편화 )

 앞서 언급했듯이 파티션은 메모리 문제를 발생시킨다. 구체적으로는 프로세스에게 할당하기에 너무 작은 홀이 다수 생기는 현상이 발생하는데, 이것이 메모리 단편화 현상이다. 메모리 단편화에는 2가지 종류가 존재한다.

Internal Fragmentation ( 내부 단편화 )

 프로세스가 자신의 크기보다 큰 파티션에 할당되어, 해당 크기 차이만큼의 메모리 공간이 사용될 수 없는 상태. 미리 지정된 파티션이 존재해야만 발생하는 단편화이므로, 고정 파티션 방식에서만 발생한다.

 예를 들어 크기 8인 메모리 공간에 크기 5인 프로세스가 할당되었다고 생각해보자. 이 경우 크기 3의 메모리 공간이 남지만, 크기가 2인 새로운 프로세스가 해당 메모리에 할당될 수는 없다. 하나의 파티션에는 하나의 프로세스만이 포함될 수 있기 때문이다. 따라서 파티션 내부 공간이 비어있음에도 사용할 수 없는 내부 단편화 현상이 발생한다.

external Fragmentation ( 외부 단편화 )

 전체 메모리 공간에 대해서는 요청된 프로세스를 할당할 수 있어 보이지만, 해당 공간들이 연속적으로 존재하지는 않으므로 실제로는 메모리를 할당할 수 없는 현상. 고정 파티션 및 가변 파티션에 대해 발생하는 문제이다.

 메모리 전반적으로 홀의 크기 합이 13이고, 요청된 프로세스의 크기가 12를 차지한다고 생각해보자. 직관적으로는 총 남은 메모리 크기가 13이므로 프로세스를 충분히 할당할 수 있어 보이지만, 해당 공간들이 [3, 4, 6] 크기의 홀로 존재한다면 연속 적재(Contiguous Allocation) 가 불가능하다. 따라서 전체적으로는 사용할 수 있어 보이지만 실제로는 여러개의 홀로 분포되어 있어 사용할 수 없는 외부 단편화 현상이 나타난다.

 위 예시의 경우 가변 파티션 상황에서는 주기적인 메모리 공간 정리를 통해 해결할 수 있다. 그러나 근본적으로 가변 파티션 상황에서도 외부 단편화 현상이 발생할 수 있다.

일반적으로 단편화 현상으로 인해 전체 메모리의 30% ~ 50% 은 사용할 수 없다고도 한다.

---

가변 파티션 ( Variable Partition )

 고정 파티션 기법과는 달리 초기에 명확히 구분되는 파티션이 존재하지 않는다. 대신 프로세스가 메모리로 읽히는 시점에 요구된 정도와 정확히 일치하는 크기의 메모리를 할당하여 해당 공간에 프로세스를 저장한다. 즉, 초기에 파티션을 만들어 두는 대신 프로세스가 요청하는 시점에 프로세스 크기만큼의 파티션을 메모리 상에 할당하는 방식이 가변 파티션 방식이다.

 기존에 정해진 크기가 따로 존재하지 않기 때문에 파티션에 가용 메모리가 남는 현상인 내부 단편화가 발생하지 않는다. 그에 비해 외부 단편화 현상은 발생할 수 있는데, 주기적으로 메모리 공간을 검사하여 사용할 수 있는 메모리 자원을 한 곳으로 모음으로써(compaction) 가용 메모리 자원을 단편화 현상 없이 사용할 수 있다. 

 필요한 만큼만 메모리를 할당한다는 점에 있어서 메모리 자원을 효율적으로 사용할 수 있다는 장점이 있다. 하지만 파티션에 미리 정해진 크기가 존재하지 않아 각 프로세스 혹은 홀에 대한 base / limit 값을 따로 기억하고 있어야 하며, 외부 단편화 현상이 쉽게 발생할 수 있으므로 이를 제거하는 알고리즘을 주기적으로 수행해야 해서 전반적인 오버헤드가 커진다는 단점이 존재한다. 

---

메모리 할당 문제와 알고리즘 ( dynamic storage allocation problem )

 여러개의 홀이 존재할 때, 어떤 방식으로 남은 홀에 프로세스를 할당해야 전체 메모리를 효율적으로 사용할 수 있을까? 크게 3가지 방식이 존재한다.

• First-fit
  : 처음부터 순회하여 현재 프로세스를 넣을 수 있을만큼 큰 홀 중에서 처음으로 만나는 홀에 할당한다. 전체 홀을 순회할 필요가 없다는 장점이 있다.
• Best-fit
  : 전체 홀 중에서 현재 프로세스가 들어갈 수 있는 홀 중 가장 작은 크기의 홀에 할당한다. 홀이 크기순으로 정렬되어있지 않다면 전체 홀을 모두 순회해야 한다. leftover hole ( 할당하고 남는 메모리 공간 ) 을 최소화하는 방식이다.
• Worst-fit
  : 전체 홀 중에서 가장 큰 홀에 현재 프로세스를 삽입한다. leftover hole ( 할당하고 남는 메모리 공간 ) 을 최대로 하는 방식이다.

일반적으로 First-fit과 Best-fit 방식이 Worst-fit 방식에 비해 속도 및 저장소 사용 측면에서 더 좋다고 한다.

---

Segmentation

 기존 Contiguous Allocation 방식에서는 프로그램을 통째로 연속된 공간에 할당했다. 그런데 사실 하나의 프로그램이라도 서브루틴, 코드 영역, 스택, 심볼 테이블, 메인루틴 등 다양한 기준으로 구분될 수 있다. 각각은 어느정도 독립적으로 존재하므로 반드시 연속된 공간에 할당할 필요는 없으므로 여러개의 홀에 분산하여 넣어도 크게 상관이 없다.

 세그멘테이션 기법은 이러한 각각의 논리적 단위를 세그먼트(segment) 로 분류하고, 이들을 분산하여 메모리 상에 적재하는 기법을 의미한다. 실제로 해당 메모리를 사용하는 시점에는 물리적 메모리에 접근해야 하므로, MMU를 이용하여 가상 주소를 대응 관계가 적혀 있는 segment table을 이용하여 실제 물리적 주소로 대응시킨다.

 

• Segment Table : 논리적 주소를 물리적 메모리 주소로 변환하기 위한 대응 관계가 적혀 있는 테이블.
  
  • base : 세그먼트가 시작하는 물리적 주소
  • limit : 세그먼트의 길이
• logical address
  : 논리적 주소. <segment-number, offset> 의 튜플 형태를 띈다.
  세그먼트 테이블에서 찾은 base 주소에 오프셋을 더하면 실제 물리적 주소가 나온다.
  • segment-number(s) : 특정 세그먼트를 지정하는 번호. segment table의 인덱스로 사용된다.
  • offset(d) : 세그먼트 상의 논리적 주소부. limit 이상의 값을 가질 수 없다. (주소는 0부터)
• segment-table base register(STBR) : 세그먼트 테이블의 메모리 상 주소를 가리키는 레지스터.
• segment-table length register(STLR)
  : 프로그램에서 사용되는 세그먼트의 수. s < STLR 이어야만 실제 존재하는 세그먼트에 접근한다고 할 수 있다.

세그먼트 테이블에 각각의 세그먼트가 유효한지 보기 위해 validation bit를 둬서 0이면 illegal로 취급하며, 따로 read/write/execute에 대한 권한을 부여하기도 한다. Protection bit는 세그먼트 내에 존재한다.