[Operating System Concepts 10th] 9. Main Memory 리뷰 (1)

본 글은 Operating System Concepts 10th (운영체제) 책을 보며 내용을 개인 공부에 목적으로 정리했습니다.
이전에 운영체제 관련 강의들을 들으면서 정리한 시리즈 글들이 있는데,
지식을 습득하는 데 있어 가장 느리지만 가장 빠른 방법이 원본책을 자세히 보는 것이라 생각됩니다.
책 내용들을 최대한 이해하기 위해 거의 모든 내용을 담고 있습니다.

책 pdf 링크 : Operating System Concepts 10th Edition by Abraham Silberschatz Peter B Galvin Greg Gagne pdf free download
연습 문제 정답지 : Solutions of Practice Exercises, Tenth Edition of Operating System Concepts, AVI SILBERSCHATZ

9. Main Memory

• CPU 스케줄링을 통해 CPU 이용률과 사용자에 제공하는 컴퓨터 응답속도를 모두 향상할 수 있다.
• 그러나 이러한 성능 향상을 실현하려면 많은 프로세스를 메모리에 유지해야 한다.
  • 즉, 메모리를 공유해야 한다.
• 이 장에서는 메모리를 관리하는 다양한 방법에 관해 설명한다.

• 목표
  • 논리 주소와 물리 주소의 차이점과 주소를 변환할 때 MMU(메모리 관리 장치)의 역할을 설명한다.
  • 메모리를 연속적으로 할당하기 위해 최초, 최적 및 최악 접합 전략을 적용한다.
  • 내부 및 외부 단편화의 차이점을 설명한다.
  • TLB (translation look-aside buffer)가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환한다.
  • 계층적 페이징, 해시 페이징 및 역 페이지 테이블을 설명한다.
  • IA-32, x86-64 및 ARMv8 아키텍처의 주소 변환에 관해 설명한다.

9.1 Background

• 메모리(memory)는 각각 주소(address)가 할당된 일련의 바이트들로 구성된다.
• CPU는 PC(program counter)가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져온다.
• 전형적인 명령어 실행은 먼저 메모리로부터 한 명령어를 가져오는 데서부터 시작한다.
• 그런 다음 명령어를 해독하고, 메모리에서 피연산자(operand)를 가져와 피연산자에 대해 명령어를 실행한 후에 계산 결과를 메모리에 다시 저장한다.
  • 메모리는 주소에 지시한 대로 읽기, 쓰기만 할 뿐 이 주소들이 어떻게 생성되었는지 혹은 그 주소가 가리키는 내용이 무엇인지를 모른다.

9.1.1 Basic Hardware

• 메인 메모리와 각 처리 코어에 내장된 레지스터들은 CPU가 직접 접근할 수 있는 유일한 범용 저장장치이다.
  • 기계 명령어들은 메모리 주소만을 인수로 취하고, 디스크의 주소를 인수로 취하지 않는다.
  • 따라서 모든 실행되는 명령어와 데이터들은 CPU가 직접적으로 접근할 수 있는 메인 메모리와 레지스터에 있어야 한다.
  • 만약 데이터가 메모리에 없다면 CPU가 그것들을 처리하기 전에 메모리로 이동시켜야 한다.

• 각 CPU 코어에 내장된 레지스터들은 일반적으로 CPU 클록(clock)의 1사이클 내에 접근이 가능하다.
  • 일부 처리 코어들은 레지스터에 있는 명령어의 해독과 간단한 연산을 클록 틱(clock tick)당 하나 또는 그 이상의 속도로 처리한다.
• 하지만 메인 메모리의 접근을 완료하기 위해서는 많은 CPU 클록 틱 사이클이 소요되며, 이 경우 CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고 지연되는(stall) 현상이 발생하게 된다.
  • 메인 메모리는 메모리 버스를 통해 전송된다.
• 이를 해결하기 위한 방법으로 캐시(cache)를 도입해 CPU와 메인 메모리 사이에 (통상 빠르게 접근할 수 있도록 CPU 안에) 빠른 속도의 메모리를 추가하는 것이다.
• CPU에 구축된 캐시를 관리하여 하드웨어는 어떠한 운영체제의 도움 없이 메모리 접근 속도를 향상한다.

• 운영체제가 CPU와 메모리 간의 접근 중에 개입하게 되면 성능이 떨어지기 때문에 “보호 기법”은 반드시 하드웨어가 지원해야 한다.
• 먼저 각각의 프로세스가 독립된 메모리 공간을 가지도록 보장해야 한다.
  • 개별적인 프로세스별 메모리 공간은 서로를 보호하고 동시 실행을 위해 여러 프로세스가 메모리에 적재되게 하는 것이 필수적이다.

• 개별적인 메모리 공간을 분리하기 위해서 특정 프로세스만 접근할 수 있는 합법적인(legal) 메모리 주소 영역을 설정하고, 프로세스가 합법적인 영역만을 접근하도록 하는 것이 필요하다.
• Figure 9.1에서 보여주듯이, 기준(base)과 상한(limit)이라고 불리는 2개의 레지스터들을 사용하여 이러한 보호 기법을 제공한다.
  • 기준 레지스터(base register)는 가장 작은 합법적인 물리(physical) 메모리 주소의 값을 저장한다.
  • 상한 레지스터(limit register)는 주어진 영역의 크기를 저장한다.
  • 기준과 상한 레지스터가 논리(logical) 주소 공간을 정의한다.
  • 기준과 상한 레지스터는 여러 가지 특권 명령을 사용하는 운영체제에 의해서만 적재된다.
  • 이러한 기법은 운영체제만 레지스터들의 값을 변경할 수 있도록 허가해 줌으로써 사용자 프로그램이 레지스터의 내용을 변경하는 것을 막는다.

• 메모리 공간의 보호는 CPU 하드웨어가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어진다.
• 사용자 모드에서 수행되는 프로그램이 운영체제의 메모리 공간이나 다른 사용자 프로그램의 메모리 공간에 접근하면 운영체제는 치명적인 오류로 간주하고 트랩(trap)을 발생시킨다.
  • 이러한 기법은 사용자 프로그램이 운영체제나 다른 사용자 프로그램의 코드나 데이터 구조를 수정하는 것을 만든다.

types of address

• 책에는 없지만, 주소의 정의를 정리할 필요가 있다고 느꼈다. ¹
• 논리 주소(logical address) : 프로세스마다 독립적으로 갖는 공간
  • 논리적인 주소 체계로, 0번지를 시작으로 상대적인 주소 값을 갖는다.
  • CPU에서 인식하는 주소 체계로, 가상(virtual), 상대(relative), 재배치 가능(relocatable) 주소라고도 부른다.
• 물리 주소(physical address) : 실제 물리적인 메모리 위치를 식별하는 주소
  • 절대(absolute) 주소라고도 한다.
• 심볼 주소(symbolic address) : 변수나 함수와 같이 코드에서 사용하는 상징적인 이름을 주소로 사용하는 방법이다.

9.1.2 Address Binding

• 프로그램은 원래 이진 실행 파일 형태로 디스크에 저장되어 있다.
• 실행하려면 프로그램을 메모리로 가져와서 프로세스 문맥 내에 배치해야 한다.
• 이 시점에 가용한 CPU에서 실행할 수 있게 된다.
• 프로세스가 실행되면 메모리에서 명령 및 데이터에 액세스 한다.
• 프로세스가 종료되면 다른 프로세스에서 사용하기 위해 메모리가 회수된다.

• 대부분의 경우 Figure 9.3과 같이 여러 단계를 거쳐 실행되기 때문에 이들 단계를 거치는 동안 주소들은 여러 가지 다른 표현 방식을 거치게 된다.

• 원시 프로그램에서 주소는 숫자가 아닌 심볼 형태(ex. 변수 count)로 표현된다.
• 컴파일러(compiler)는 이 심볼(symbolic) 주소를 재배치(relocatable) 가능 주소로 바인딩시키고(binding), 다음에 링커(linker)나 로더(loader)가 재배치 가능 주소를 절대 주소(absolute address)로 바인딩시킨다.
  • 바인딩(binding) 과정은 한 주소 공간에서 다른 주소 공간으로 맵핑하는 것이다.

• 메모리 주소 공간에서 명령어와 데이터의 바인딩은 그 바인딩이 이루어지는 시점에 따라 다음과 같이 구분된다.
  • 컴파일 시간(compile time) 바인딩 : 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다.
  • 적재 시간(load time) 바인딩 : 만일 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못하면 컴파일러는 일단 이진 코드를 재배치 가능코드로 만들어야 한다.
    • 이 경우에 심볼과 진짜 번지수와의 바인딩은 프로그램이 메인 메모리로 실제로 적재되는 시간에 이루어지게 된다.
  • 실행 시간(execution time) 바인딩 : 만약 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면 이것을 바인딩이 실행 시간까지 허용되었다고 이야기한다.

9.1.3 Logical-Versus Physical-Address Space

• CPU가 생성하는 주소를 논리 주소(logical address)라 하며, 메모리게 취급하게 되는 주소(즉, 메모리 주소 레지스터(MAR, memory address register))는 물리 주소(physical address)라 한다.
• 컴파일 또는 적재 시에 주소를 바인딩하면 논리 주소와 물리 주소가 같다.
  • 그러나 실행 시간 바인딩 기법에서는 논리, 물리 주소가 다르다.
  • 이러면 논리 주소를 가상 주소(virtual address)라 한다.
• 프로그램에 의해 생성된 모든 논리 주소 집합을 논리 주소 공간(logical address space)라 하며 이 논리 주소와 일치하는 모든 물리 주소 집합을 물리 주소 공간(physical address space)이라 한다.

• 프로그램의 실행 중에는 가상 주소를 물리 주소로 바꾸어줘야 하는데 이 변환(mapping) 작업은 하드웨어 장치인 메모리 장치 관리(MMU, memory management unit)에 의해 실행된다.

• 기준 레지스터를 재배치(relocation) 레지스터라고 부른다.
• 재배치 레지스터 속에 들어있는 값은 주소가 메모리로 보내질 때마다 그 모든 주소에 더해진다.

9.1.4 Dynamic Loading

• 메모리 공간을 더 효율적으로 이용하기 위해서는 동적 적재(dynamic loading)를 해야 한다.
• 동적 적재에서 각 루틴은 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기하고 있다.
• 먼저 main 프로그램이 메모리에 올라와 실행된다.
• 이 루틴이 다른 루틴을 호출하게 되면 호출된 루틴이 이미 메모리에 적재됐는지를 조사한다.
• 만약 적재되어 있지 않다면, 재배치 가능 연결 적재기(relocatable linking loader)가 불려 요구된 루틴을 메모리로 가져오고, 이러한 변화를 테이블에 기록해둔다.

9.1.5 Dynamic Linking & Shared Libraries

• 동적 연결 라이브러리(DLLs, dynamically linked libraries)는 사용자 프로그램이 실행될 때, 사용자 프로그램에 연결되는 시스템 라이브러리이다.
• 동적 연결 개념은 동적 적재의 개념과 유사하다.
  • 동적 적재에서는 로딩(loading)이 실행 시까지 미루어졌었지만 동적 연결에서는 연결(linking)이 실행 시기까지 미루어지는 것이다.
  • 하지만 동적 적재와는 달리 동적 연결과 공유 라이브러리는 일반적으로 운영체제의 도움이 필요하다.
  • 메모리에 있는 프로세스들이 각자의 공간은 자기만 액세스할 수 있도록 보호된다면, 운영체제만이 기억 공간에 루틴이 있는지를 검사해 줄 수 있고 운영체제만이 여러 프로세스가 같은 메모리 주소를 공용할 수 있도록 해줄 수 있다.
• 동적 연결은 주로 표준 C 언어 라이브러리와 같은 시스템 라이브러리에 사용된다.
• DLL은 또한 이러한 라이브러리를 여러 프로세스 간에 공유할 수 있어 메인 메모리에 DLL 인스턴스가 하나만 있을 수 있다는 것이다.
  • 이러한 이유로 DLL을 공유 라이브러리라고도 한다.

• 프로그램이 동적 라이브러리에 있는 루틴을 참조하면 로더는 DLL을 찾아 필요한 경우 메모리에 적재한다.
• 그런 다음 동적 라이브러리의 함수를 참조하는 주소를 DLL이 저장된 메모리의 위치로 조정한다.

9.2 Contiguous Memory Allocation

• 메인 메모리는 운영체제뿐만 아니라 여러 사용자 프로세스도 수용해야 한다. 그리고 각 영역은 각각 목적에 맞도록 효율적으로 관리되어야 한다.
• 메모리는 일반적으로 2개의 부분으로 나누어지는데, 하나는 운영체제를 위한 것이며 다른 하나는 사용자 프로세스를 위한 것이다.
  • 많은 운영체제는 운영체제를 높은 메모리에 배치한다.
  • 일반적으로 여러 사용자 프로세스가 동시에 메모리에 상주하기를 원한다.
  • 따라서 메모리에 적재되기를 기다리는 프로세스에 사용 가능한 메모리를 할당하는 방법을 고려해야 한다.
  • 연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재된다.

9.2.1 Memory Protection

• 만일 시스템이 상한 레지스터와 재배치 레지스터를 가지고 있다면 프로세스가 자신이 소유하지 않은 메모리를 접근할 수 없게 강제할 수 있다.
  • 재배치(relocation) 레지스터는 가장 작은 물리 주소의 값을 저장한다.
  • 상한(limit) 레지스터는 논리 주소의 범위 값을 저장한다.
    • 각각의 논리 주소는 상한 레지스터가 지정한 범위 안에 존재해야 한다.
• MMU는 동적으로 논리 주소에 재배치 레지스터의 값을 더함으로써 주소를 변환하는 역할을 한다.
  • 이렇게 변환된 주소는 메모리로 보내진다.

• CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처(dispatcher)는 문맥 교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재한다.
• CPU에 의해서 생성되는 모든 주소는 이 레지스터들의 값을 참조해서 확인 작업을 거치기 때문에, 운영체제와 다른 사용자 프로그램을 현재 수행 중인 사용자 프로그램의 접근으로부터 보호할 수 있다.

9.2.2 Memory Allocation

• 메모리를 할당하는 가장 간단한 방법 중 하나는 프로세스를 메모리의 가변 크기 파티션에 할당하는 것이다.
  • 각 파티션에는 정확히 하나의 프로세스만 적재될 수 있다.
  • 가변 파티션(variable partition) 기법에서 운영체제는 사용 가능한 메모리 부분과 사용 중인 부분을 나타내는 테이블을 유지한다.
  • 하나의 큰 사용 가능한 메모리 블록을 hole로 간주한다. (아래 하늘색 부분)

• 프로세스가 시스템에 들어오면, 운영체제는 각 프로세스가 메모리를 얼마나 요구하며, 또 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 공간을 할당한다.
• 프로세스가 공간을 할당받게 되면, 이후로는 CPU를 할당받기 위해 경쟁한다.
• 프로세스가 끝내면 메모리를 반납하고, 운영체제는 다른 프로세스에 이 공간을 할당할 수 있다.

• 일반적으로 메모리에는 다양한 크기의 hole이 여기저기 흩어져 있다.(scatter)
• 프로세스에 공간이 필요할 때 운영체제는 이 hole의 집합에서 적절한 것을 찾아내야 한다.
• 동적 메모리 할당 문제(dynamic storage allocation problem)은 일련의 가용 공간-리스트로부터 크기 n-바이트 블록을 요구하는 것을 어떻게 만족시켜 줄 것이냐를 결정하는 문제이다.
• 이러한 문제에 대한 해결책 중 3가지를 소개한다.
  • 최초 적합(first-fit) : 첫 번째 사용 가능한 가용 공간을 할당한다.
  • 최적 적합(best-fit) : 사용 가능한 공간 중에서 가장 작은 것을 택한다.
  • 최악 적합(worst-fit) : 가장 큰 가용 공간을 택한다.

9.2.3 Fragmentation

• 최초 적합 전략과 최초 적합 전략 모두 외부 단편화(external fragmentation)로 인해 어려움을 겪는다.
• 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 어떤 가용 공간은 너무 작은 조각이 되어 버린다.
• 외부 단편화는 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 너무 작은 조각드롤 여러 곳에 분산되어 있을 때 발생한다.
• 또한 메모리의 전체 크기와 프로세스 크기들은 모두 외부 단편화에 따라 큰 영향을 미칠 수 있다.

• 외부 단편화 문제를 해결하는 방법으로 압축(compaction)이 있는데, 이 방법은 메모리 모든 내용을 한군데로 몰고 모든 가용 공간을 다른 한군데로 몰아서 큰 블록을 만드는 것이다.
  • 압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능하다.
  • 주소가 동적으로 재배치할 수 있다면, 재배치 작업은 프로그램과 데이터를 새로운 위치로 옮기고 새 위치를 반영하기 위하여 기준 레지스터만 변경하면 완료된다.

• 외부 단편화 문제를 해결할 수 있는 다른 방법은 한 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법이다.
  • 이것은 페이징(paging)에 사용되는 전략이다.
• 내용을 이어서 보고싶다면 다음 링크를 클릭한다.
  • 링크 : [Operating System Concepts 10th] 9. Main Memory 리뷰 (2)

References

1. 메모리 관리 1 - 주소 바인딩 - Primitive ↩