[운영체제] Ch9. 메인 메모리

공룡책(운영체제)을 읽고 정리한 글입니다.

 

 

 

컴퓨터의 CPU는 프로그램 카운터(PC)가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져오는데 그 명령어는 필요한 경우 추가적인 데이터를 더 가져올 수 있으며 반대로 데이터를 메모리로 내보낼 수도 있다.

 

전형적인 명령어 실행은 먼저 메모리로부터 한 명령어를 가져오는 데서부터 시작된다.

그런 다음 명령어를 해독하고, 메모리에서 피연산자를 가져와 피연산자에 대해 명령어를 실행한 후에 계산 결과를 메모리에 다시 저장한다.

 

 

배경 지식

기본 하드웨어

메인 메모리와 각 처리 코어에 내장된 레지스터들은 CPU가 직접 접근할 수 있는 유일한 범용 저장장치이다.

기계 명령어들은 메모리 주소만을 인수로 취하고, 디스크의 주소를 인수로 취하지 않는다.

따라서 모든 실행되는 명령어와 데이터들은 CPU가 직접적으로 접근할 수 있는 메인 메모리와 레지스터에 있어야 한다.

 

각 CPU 코어에 내장된 레지스터들은 일반적으로 CPU 클록의 1사이클 내에 접근이 가능하다.

그러나 메모리 버스를 통해 전송되는 메인 메모리의 경우는 많은 CPU 클록 틱 사이클이 소요되며, 이 경우 CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고 지연되는 현상(Stall)이 발생하게 된다.

메인 메모리의 접근이 빈번한데 이러한 상황이 발생되는건 용납하기 힘들다.

해결 방안은 CPU와 메인 메모리 사이에 캐시라고 불리는 빠른 속도의 메모리를 추가하는 것이다.

 

물리 메모리의 상대적인 접근 속도의 차이를 캐시 메모리를 도입함으로서 해결할 수 있었다.

추가로 시스템이 올바르게 동작하기 위해서는 사용자 프로그램으로부터 운영체제 영역을 보호해야 할 뿐만 아니라 사용자 프로그램 사이도 서로 보호해야 한다.

 

먼저 각각의 프로세스는 독립된 메모리 공간을 가짐을 보장해야 한다.

개별적인 프로세스별 메모리 공간은 서로를 보호하고, 병행 실행을 위해 여러 프로세스가 메모리에 적재되게 하는 것은 필수적이다.

개별적인 메모리 공간을 분리하기 위해서 특정 프로세스만 접근할 수 있는 합법적인 메모리 주소 영역을 설정하고, 프로세스가 합법적인 영역만을 접근하도록 하는 것이 필요하다.

 

 

위 그림처럼 프로세스가 생성되면 base와 limit이라고 불리는 값이 들어있는 두 개의 레지스터를 사용하여 프로세스간 메모리 영역을 규정하고 보호한다.

EX. base가 300040이고 limit이 120900이면 프로그램은 300040에서 420940까지의 모든 주소를 접근할 수 있다.

 

메모리 공간의 보호는 CPU 하드웨어가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어진다.

사용자 모드에서 수행되는 프로그램이 운영체제의 메모리 공간이나 다른 사용자 프로그램의 메모리 공간에 접근하면 운영체제는 치명적인 오류로 간주하고 트랩을 발생시킨다.

 

base와 limit 레지스터는 여러 가지 특권 명령을 사용하는 운영체제에 의해서만 적재된다.

왜냐하면, 특권 명령은 오직 커널 모드에서만 수행되고, 운영체제만 커널 모드에서 수행되기 때문이다. 이러한 기법은 운영체제만 레지스터들의 값을 변경할 수 있도록 허가해 줌으로써 사용자 프로그램이 레지스터의 내용을 변경하는 것을 막는다.

 

다중 처리기 시스템 운영체제는 현 프로세스의 상태를 레지스터로부터 메모리로 저장하고, 다음 프로세스의 문맥(Context)를 메인 메모리로부터 레지스터로 불러오는 문맥 교환(Context Switching)을 실행해야 한다.

 

 

 

주소의 할당

대부분의 시스템은 사용자 프로세스가 메모리 내 어느 부분으로도 올라올 수 있도록 지원한다.

사용자 프로세스의 주소가 00000번지부터 시작된다고 해서 이 프로그램이 메모리의 00000번지부터 올라와야 할 필요는 없다.

 

대부분의 경우 아래와 같은 단계를 거쳐 실행된다.

• 컴파일 시간 바인딩
  만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다. 
  예를 들면 사용자 프로세스가 R번지로부터 시작한다는 것을 미리 알 수 있으면 컴파일러는 번역할 코드를 그 위치에서 시작해 나간다. 그러나 만일 이 위치가 변경되어야 한다면 이 코드는 다시 컴파일되어야 한다.
  
  
• 적재 시간(load time) 바인딩
  만일 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못하면 컴파일러는 일단 이진 코드를 재배치 가능 코드로 만들어야 한다. 이 경우에 심볼과 진짜 번지수와의 바인딩은 프로그램이 메인 메모리로 실제로 적재되는 시간에 이루어지게 된다. 이렇게 만들어진 재배치 가능 코드는 시작 주소가 변경되면 아무 때나 사용자 코드를 다시 적재하기만 하면 된다.
  
  
• 실행 시간 바인딩
  만약 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면 우리는 바인딩이 실행 시간까지 허용되었다고 이야기한다.
  이것이 가능해지려면 특별한 하드웨어를 이용해야 한다.

 

 

논리 대 물리 주소 공간

CPU가 생성하는 주소를 일반적으로 논리 주소(logical address)라 하며, 반면에 메모리가 취급하게 되는 주소[메모리 주소 레지스터(MAR)에 주어지는 주소]는 일반적으로 물리 주소(physical address)라 한다.

 

컴파일 또는 적재 시에 주소를 바인딩하면 논리 주소와 물리 주소가 같다.

그러나 실행 시간 바인딩 기법에서는 논리, 물리 주소가 다르다. 

이러면 논리 주소를 가상 주소라 할 수 있다. 이 책에서는 논리 주소나 가상 주소나 같은 뜻으로 사용한다.

프로그램에 의해 생성된 모든 논리 주소 집합을 논리 주소 공간이라하며 이 논리 주소와 일치하는 모든 물리 주소 집합을 물리 주소 공간이라 한다.

 

MMU 모형

프로그램의 실행 중에는 이와 같은 가상 주소를 물리 주소로 바꾸어줘야 하는데 이 변환(mapping) 작업은 하드웨어 장치인 메모리 관리 장치(memory management unit, MMU)에 의해 실행된다. 이러한 변환 방법은 여러 가지가 있다.(이후 설명)

 

MMU 메모리 검사

위에서 보았던 base 레지스터를 재배치(relocation) 레지스터라고 부른다.

재배치 레지스터 속에 들어있는 값은 주소가 메모리로 보내질 때마다 그 모든 주소에 각각 더해진다.

예를 들어, 재배치 레지스터의 값이 14000이라면 프로세스가 346번지에 액세스할 때, 실제로는 메인 메모리의 14346번지에 액세스하게 된다.

 

사용자 프로그램은 결코 실제적인 물리 주소에 접근하지 않는다는 것을 주의해야 한다. 

사용자 프로그램은 346번지에 대한 포인터를 생성해서 그것에 대해 저장, 연산, 다른 주소들과 비교하는 등 온갖 일을 할 수가 있다.

그러나 일단 346번지가 주소로 사용될 때는 기준 레지스터에 대해 다시 바인딩된다.

사용자 프로그램은 논리 주소를 사용한 것이고, 메모리 하드웨어는 논리 주소를 실제 주소로 바꾼 것이다.

 

가상 주소를 사용하게 되었으므로 사용자 프로세스는 단지 논리 주소만을 생성할 뿐이므로 주소가 메모리 위치 0에서 limit(max) 위치까지만 있다고 생각할 것이다.

 

핵심 개념은 별도의 물리 주소 공간에 연결되어야 하나는 가상 주소 공간의 개념은 올바른 메모리 관리에 핵심이라는 것이다.

 

 

동적 적재

지금까지의 설명에서는 프로세스가 실행되기 위해 그 프로세스 전체가 미리 메모리에 올라와 있어야 했다.

이 경우 프로세스의 크기는 메모리의 크기보다 커서는 안된다.

 

메모리 공간의 더 효율적인 이용을 위해서는 동적 적재(dynamic loading)를 해야 한다.

동적 적재에서 각 루틴은 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기하고 있다.

먼저 main 프로그램이 메모리에 올라와 실행된다.

이 루틴이 다른 루틴을 호출하게 되면 호출된 루틴이 이미 메모리에 적재됐는지를 조사한다.

만약 적재되어 있지 않다면, 재배치 가능 연결 적재기가 불려서 요구된 루틴을 메모리로 가져오고, 이러한 변화(추가적인 메모리 사용)를 테이블에 기록해 둔다.

 

동적 적재의 장점은 루틴이 필요한 경우에만 적재된다는 것이다. 이러한 구조는 오류 처리 루틴과 같이 아주 간혹 발생하면서도 실행할 코드가 많은 경우에 특히 유용하다.

이러한 상황에서는 전체 프로그램 크기가 클 수 있지만 사용되는 부분이 훨씬 작을 수 있다.

 

 

동적 연결 및 공유 라이브러리

동적 연결 라이브러리(DLL)는 사용자 프로그램이 실행될 때, 사용자 프로그램에 연결되는 시스템 라이브러리이다.

 

어떤 운영체제는 정적 연결(static-linking)만을 지원한다. 이러한 시스템에서는 라이브러리가 이 프로그램의 이진 프로그램 이미지에 끼어 들어가게 된다.

 

반대로 동적 연결 개념은 동적 적재의 개념과 유사하다.

동적 적재에서는 로딩이 실행시까지 미루어졌었지만 동적 연결에서는 연결이 실행 시기까지 미루어지는 것이다.

동적 연결은 주로 표준 C언어 라이브러리와 같은 시스템 라이브러리에 사용된다.

이 기능이 없으면 프로그램은 실행가는 이미지에 해당 언어 라이브러리(또는 최소한 프로그램이 참조하는 루틴)의 사본을 포함하기 때문에(필요없는 라이브러리 또는 당장 필요하지 않는 라이브러리) 메모리를 낭비할 수 있다.

 

DLL은 추가적으로 이러한 라이브러리를 여러 프로세스 간에 공유할 수 있어 메인 메모리에 DLL 인스턴스가 하나만 있을 수 있다는 것이다. 이러한 이유로 DLL을 공유 라이브러리라고도 하며 Windows 및 Linux 시스템에 광범위 하게 사용된다.

 

DLL은 라이브러리 갱신을 통해 확장할 수 있다. 어느 때나 새로운 버전으로 교체될 수 있고, 그렇게 되면 그 라이브러리를 사용하는 모든 프로그램은 자동으로 새로운 라이브러리 버전을 사용하게 될 것이다.(엄청 위험하지 않을까?)

 

동적 적재와는 달리 DLL은 일반적으로 운영체제의 도움이 필요하다. 메모리에 있는 프로세스들이 각자의 공간은 자기만 액세스할 수 있도록 보호된다면, 운영체제만이 기억 공간에 루틴이 있는지를 검사해 줄 수 있고 운영체제만이 여러 프로세스가 같은 메모리 주소를 공용할 수 있도록 해줄 수 있다.

이후 페이징을 알아볼 때 페이징을 통해 프로세스들이 DLL을 공유할 수 있는 방법에 대해 자세히 볼 수 있다.

 

 

연속 메모리 할당

일반적으로 여러 사용자 프로세스가 동시에 메모리에 상주하기를 원한다.

따라서 메모리에 적재되기를 기다리는 프로세스에 사용 가능한 메모리를 할당하는 방법을 고려해야 한다.

연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재된다.

그 전에 메모리를 어떻게 보호할 지 알아보자.

 

메모리 보호

레지스터에 base, limit 주소값을 넣는 아이디어와, 가상 주소 아이디어를 결합하면, 프로세스가 자신이 소유하지 않은 메모리를 접근할 수 없게 강제할 수 있다.

 

재배치 레지스터(base)에는 가장 작은 물리 주소의 값을 저장하고, 상한 레지스터(limit)는 가상 주소의 범위 값을 저장한다. 각각의 가상 주소는 상한 레지스터가 지정한 범위 안에 존재해야 한다.

MMU는 동적으로 가상 주소에 재배치 레지스터의 값을 더함으로써 주소를 변환하는 역할을 한다. 이렇게 변환된 주소는 메모리로 보내진다.

 

CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처는 문맥 교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재한다.

CPU에 의해서 생성되는 모든 주소는 이 레지스터들의 값을 참조해서 확인 작업을 거치기 때문에, 우리는 운영체제와 다른 사용자 프로그램을 현재 수행 중인 사용자 프로그램의 접근으로부터 보호할 수 잇다.

 

여기서 재배치 레지스터를 사용하기 때문에 운영체제의 크기는 실행 중이라도 얼마든지 변경될 수 있다.

이 덕분에 예를 들어, 운영체제에는 장치 드라이버를 위한 코드 및 버퍼 공간이 있다. 장치 드라이버가 현재 사용 중이 아닌 경우 메모리에 유지하는 것은 의미가 없다. 대신 필요할 때만 메모리에 적재할 수 있다. 마찬가지로 장치 드라이버가 더 필요하지 않은 경우 장치 드라이버를 제거하고 메모리를 다른 요청에 할당할 수 있다.

 

 

메모리 할당

메모리를 할당하는 가장 간단한 방법 중 하나는 프로세스를 메모리의 가변 크기 파티션에 할당하는 것이다.

각 파티션에는 정확히 하나의 프로세스만 적재될 수 있다. 이 가변 파티션 기법에서 운영체제는 사용 가능한 메모리 부분과 사용 중인 부분을 나타내는 테이블을 유지한다.

처음에는 모든 메모리가 사용자 프로세스에 사용 가능하며, 하나의 큰 사용 가능한 메모리 블록인 hole로 간주한다.

 

위 그림은 가변 파티션 기법을 보여준다.

처음에는 프로세스 5, 8 및 2가 적재되어 있고, 모두 사용중이다.

프로세스 8이 종료된 후 하나의 연속된 hole이 생긴다.

나중에 프로세스 9가 도착하고 메모리가 할당된다.

프로세스 5가 종료된 후 두 개의 불연속 hole이 생긴다.

 

프로세스가 시스템에 들어오면, 운영체제는 각 프로세스가 메모리를 얼마나 요구하며, 또 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 공간을 할당한다.

프로세스가 공간을 할당받게 되면, 이후로는 CPU를 할당받기 위해 경쟁한다.

프로세스가 끝나면 메모리를 반환하고, 운영체제는 다른 프로세스에게 이 공간을 할당할 수 있다.

 

만약 새로운 프로세스를 실행하기에 메모리가 충분하지 않다면?

1. 단순히 프로세스를 거부하고 적절한 오류 메시지를 제공할 수 있다.

2. 프로세스를 대기 큐에 다시 넣을 수 있다. 메모리가 나중에 해제되면 운영체제는 대기 큐를 검사하여 대기 프로세스의 메모리 요구를 충족시킬지 여부를 결정한다.

 

그림에서 보았듯이 일반적으로 메모리에는 다양한 크기의 hole이 여기저기 산재하게 된다.

프로세스에 공간이 필요할 때 운영체제는 이 hole의 집합에서 적절한 것을 찾아내야 한다.

만약 hole을 찾았는데 그것이 요청한 것보다 약간 크면 두 개로 나누어 한 조각은 프로세스에 할당하고, 나머지 하나는 hole 집합으로 돌아간다. 이 hole이 다른 hole과 인접해 있다면, 뭉쳐서 한 개의 큰 hole이 된다.

 

이러한 기법은 동적 메모리 할당 문제의 특별한 한 예이다.

이것은 일련의 '가용 공간-리스트'로부터 '크기 n-바이트 블록'을 요구하는 것을 어떻게 만족시켜 줄 것이냐를 결정하는 문제이다.

 

이러한 문제에 대한 해결책에는 최초 적합, 최적 적합, 최악 적합 이라는 일반적인 3가지 기법이 있다.

 

• 최초 적합
  첫 번째 사용 가능한 가용 공간을 할당한다. 검색은 집합의 시작에서부터 하거나 지난번 검색이 끝났던 곳에서 시작될 수 있다. 충분히 큰 가용 공간을 찾았을 때 검색을 끝낼 수 있다.
• 최적 적합
  사용 가능한 공간 중에서 가장 작은것을 택한다. 리스트가 크기 순으로 되어 있지 않다면 전 리스트를 검색해야만 한다. 이 방법은 아주 작은 가용 공간을 만들어 낸다.
  
  
• 최악 적합
  가장 큰 가용 공간을 택한다. 이 방식에서 할당해 주고 남게 되는 가용 공간은 충분히 커서 다른 프로세스들을 위하여 유용하게 사용될 수 있다. 이때 가용 공간들이 크기 순으로 정렬되어 있지 않으면 전 리스트를 검색해야만 한다.
  
  

 

단편화

최초 적합 전략과 최적 적합 전략 모두 외부 단편화로 인해 어려움을 겪는다.

프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 어떤 가용 공간은 너무 작은 조각이 되어 버린다.

외부 단편화는 이처럼 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 너무 작은 조각들로 여러 곳에 분산되어 있을 때 발생한다.

 

메모리의 전체 크기와 프로세스 크기들은 모두 외부 단편화에 따라 큰 영향을 미칠 수 있다.

예를 들어, 최초 적합의 경우 통계적인 분석을 해보면 N개의 블록이 할당되었을 때 0.5N개의 블록이 단편화 때문에 손실될 수 있다는 것을 알 수 있다.(사용 메모리 N, 단편화 메모리 0.5N 총 1.5N) 즉, 메모리의 1/3이 쓸 수 없게 될 수 있다는 것이다. 이 현상은 50% 규칙으로 알려져 있다.

 

메모리 공간을 낭비하는 현상인 단편화는 내부적으로도 발생할 수 있다. 

18464B 크기의 가용 공간이 있다.

어느 한 프로세스가 18462B를 요구한다.

요구된 블록을 할당하면 2B가 남는다.

이렇게 되면 2B짜리 가용 공간을 놓치지 않기 위해(가용임을 확인하기 위해) 2B보다 더 큰 부담을 시스템이 가지게 될 것이다.

 

일반적으로는 메모리를 아주 작은 공간들로 분할하고 프로세스가 요청하면 할당을 항상 이 분할된 크기의 정수배로만 해주는 것이 보통이다. 이 경우 할당된 공간은 요구된 공간보다 약간 더 클 수 있다.

이들 두 크기 사이의 남는 부분이 바로 내부 단편화이고, 이 내부 단편화 역시 사용이 못 되는 부분이다.

 

외부 단편화 문제를 해결하는 방법으로는 압축이 있다.

이 방법은 메모리의 모든 내용을 한군데로 몰고 모든 가용 공간을 다른 한군데로 몰아서 큰 블록을 만드는 것이다.

그러나 프로그램의 재배치가 어셈블 또는 적재시에 정적으로 행해진다면, 압축은 실행될 수 없다.(시작 주소가 고정되어 있기 때문)

압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능하다.

 

외부 단편화 문제를 해결할 수 있는 다른 방법은 한 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법이다.

이것은 컴퓨터 시스템에 가장 일반적인 메모리 관리 기법인 페이징에서 사용되는 전략이다.

 

 

페이징

지금까지 본 메모리 관리는 프로세스의 실행을 위해서는 프로세스의 물리 주소 공간이 연속적이어야 했다.

이제 프로세스의 물리 주소 공간이 연속되지 않아도 되는 메모리 관리 기법인 페이징을 알아보자.

페이징은 운영체제와 컴퓨터 하드웨어 간의 협력을 통해 구현된다.

 

기본 방법

물리 메모리는 프레임(frame)이라 불리는 같은 크기 블록으로 나누어진다.

가상 메모리는 페이지(page)라 불리는 같은 크기의 블록으로 나누어진다.

 

프로세스가 실행될 때 그 프로세스의 페이지는 파일 시스템 또는 예비 저장장치로부터 가용한 메인 메모리 프레임으로 적재된다.

예비 저장장치는 메모리 프레임 혹은 프레임의 묶음인 클러스터와 동일한 크기의 고정 크기 블록으로 나누어진다.

예를 들어 가상 주소 공간은 물리 주소 공간으로부터 완전히 분리되었기 때문에 물리 메모리의 크기가 2^64 바이트보다 적게 장착된 시스템에서도 프로세스는 64비트로 이루어진 가상 주소 공간을 사용할 수 있다.

 

CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 오프셋(d: offset) 두 개의 부분으로 나누어 진다.

페이지 번호는 프로세스 페이지 테이블(page table)을 액세스할 때 사용된다.

 

CPU에 의해서 가상 주소가 생성되었을 때, 이를 물리 주소로 변환하기 위해 MMU가 취하는 단계는 다음과 같다.

1. 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용한다.
2. 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
3. 가상 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.

오프셋 d는 변하기 않기 때문에 대체되지 않으며, 프레임 번호와 오프셋은 이제 물리 주소를 구성한다.

 

프레임 크기와 마찬가지로 페이지 크기는 하드웨어에 의해 정해진다.

페이지 크기는 2의 거듭제곱으로, 일반적으로 컴퓨터 아키텍처에 따라 페이지당 4 KB와 1 GB 사이이다.

 

페이지 크기가 2의 거듭제곱이면 가상 주소를 페이지 번호 및 페이지 오프셋으로 쉽게 변환할 수 있다.

가상 주소 공간의 크기가 2^m이고 페이지 크기가 2^n 바이트인 경우 가상 주소의 상위 m-n 비트는 페이지 번호를 지정하고 n개의 하위 비트는 페이지 오프셋을 지정한다. 따라서 가상 주소는 다음과 같다.