이 글은 운영체제 공룡책을 읽고 정리한 내용입니다.

하드웨어에 대하여

CPU 스케줄링을 통해 성능향상을 이끌어내려면 많은 프로세스를 메모리에 유지하여 메모리를 공유하도록 해야합니다. 메인 메모리는 CPU가 직접 접근할 수 있는 유일한 범용 저장장치 이므로 모든 실행중인 프로세스는 메인메모리에 적재되어야 합니다.

위 사진처럼 메인 메모리에 여러 프로세스가 적재되는데 각 프로세스는 본인에게 해당하는 메모리에만 접근가능해야 하므로 기준 레지스터와 상한레지스터 주소를 정의하여 본인의 메모리가 아닌 외부의 주소를 접근할 경우 치명적인 오류로 간주하여 trap을 발생시킵니다.

Logical vs Physical 주소공간

일반적으로 프로그래밍을 할 때 로우레벨 하드웨어코딩이 아닌 이상 정확히 어떤 레지스터에 값을 저장할지 하드코딩하지 않습니다. 그저 변수에 값을 할당하는 식으로 코딩을 하면 컴파일 시에 배치 가능한 레지스터 주소 중 랜덤으로 저장되게 됩니다.
즉 CPU가 생성하는 주소를 논리주소 (Logical address), 메모리에 실제로 적재되는 주소를 물리주소 (Physical address) 라 부릅니다.

따라서 프로그램이 실행되면 가상주소를 실제 물리주소로 변환하는 작업이 필요한데, 이는 메모리 관리장치 (MMU) 에 의해 실행됩니다.

위 그림과 같이 논리주소가 346번일 때 MMU에서는 재배치 가능한 레지스터 주소를 참고하여 실제 물리주소로 매핑시키게 됩니다. 이 때 중요한 점은, 물리주소에는 상한레지스터가 있으므로 이를 벗어나지 않도록 적절히 물리주소로 변환하는 것이 핵심입니다.

동적 적재 (Dynamic loading)

프로세스를 실행할 때 모든 프로그래밍 데이터를 메인메모리에 적재해야 한다면 문제가 생깁니다. 예를들어 내 메인메모리가 8GB이라면 21GB 크기의 게임을 실행할 수 없을 것입니다.
메모리 공간을 좀 더 효율적으로 이용하기 위하여 각 루틴이 실제 호출되기 전까지는 재배치 (MMU에서 논리주소를 물리주소로 연결하여 적재하는 행위) 가능한 상태로 디스크에서 대기하고 있다가 해당 루틴이 호출된다면 메인메모리에 적재되어 테이블에 변화를 기록해두고 루틴이 종료되면 다시 CPU제어가 중단되었던 루틴으로 복귀합니다.
이러한 기법을 동적 적재라 부르는데 오류 처리 루틴과 같이 간혹 실행되면서 실행할 코드가 많은 경우에 유용합니다.

동적 연결 (Dynamic linking)

흔히 C언어로 파일을 작성하면 object 파일로 컴파일 하고나서, 해당 object 파일을 실행가능한 binary 파일로 빌드하게 됩니다.
이 때 object 파일을 binary파일로 빌드하는 과정을 linking이라 부릅니다.
프로그램이 실행될 때 사용자 프로그램에 연결되어 유용하게 사용가능한 프로그램의 일부를 시스템 라이브러리 라고 부릅니다. 이러한 시스템 라이브러리가 binary 실행파일에 결합되어 메모리에 한번에 적재되는 형식을 정적 연결 (static linking) 이라 부릅니다. 이러한 방식으로 실행을 하게되면 메인메모리가 낭비되고 실행 파일의 크기또한 커지게 됩니다.
따라서 프로세스 실행도중 라이브러리가 필요한 시점에서 연결 (linking) 되어 사용한 후 다시 원래코드의 흐름으로 돌아오는 방식을 동적연결 (Dynamic linking) 이라 부릅니다. 이렇게 하기 위해서는 해당 라이브러리 파일을 따로 정해진 위치에 저장해두고 해당 라이브러리의 루틴을 참조하려면 loader가 정해진 위치에서 필요한 프로그램을 메모리에 적재하면 됩니다. 이러한 라이브러리를 동적연결 라이브러리 (DLL) 라고 부릅니다.

흔히 규모가 큰 응용프로그램을 다운받아보면 .lib과 .dll파일 같은것이 보일텐데, .lib은 정적 연결 라이브러리, .dll은 동적 연결 라이브러리 파일입니다.

내용을 정리해보면 위 그림과 같은데, 프로그래밍된 파일을 컴파일러가 object file로 컴파일 하고, linker가 실행가능한 이진 파일로 변환한 다음 loader는 해당 파일을 실제 메인메모리에 적재하여 실행하게 됩니다.
그 과정에서 외부 라이브러리를 DLL (Dynamically linked libraries) 파일로 만들어 런타임 내에서 참조할 수 있도록 하는 기법을 동적 연결 (Dynamic linking), 모든 프로그램 데이터를 한번에 메모리에 올리지 않고 런타임 내에서 루틴이 필요해졌을 때 메모리에 적재하는 기법을 동적 적재 (Dynamic loading)이라 부릅니다.

메모리 할당

메인 메모리에 여러 프로세스를 적재하려면 가장 기본적으로 연속적인 메모리 할당 기법을 생각할 수 있습니다. 가장 위에 있는 그림처럼 기준레지스터와 상한레지스터를 기준으로 메모리에 차곡차곡 적재하는것을 말합니다.

이러한 논리 프로세스대로 기준레지스터와 상한레지스터 사이의 메모리 주소에 맞게 적재하며 외부의 메모리에 접근하지 못하도록 trap 오류를 일으켜 보안을 유지합니다.

이러한 연속적인 메모리 할당 기법을 사용했을 때 몇가지 문제점이 생기게 되는데 아래에서 살펴보겠습니다.

가변 파티션과 hole

가장 단순하게 프로세스를 메모리에 적재하기 위하여, 메모리의 각 부분들을 사용 중인 부분과 사용 가능한 부분으로 나누어 사용 가능한 부분에만 적재될 수 있도록 하는 가변 파티션 기법을 사용할 수 있습니다.

• 처음에는 low 메모리부터 프로세스를 차곡차곡 적재하게 되므로 1번째 상태와 같이 적재될 것입니다.
• 이후 프로세스 8이 종료되면서 해당 메모리가 빈 공간이 되고, 다른 프로세스가 적재될 수 있게 됩니다.
• 9번 프로세스가 빈 공간에 적재되었는데 비교적 작은 프로세스여서 메모리가 남게 되고
• 5번 프로세스도 종료되면서 메모리에 연속적이지 않은 빈 메모리 공간들이 생기게 됩니다.
• 이러한 빈 공간들을 hole이라 부르는데 이러한 과정으로 메모리에는 다양한 크기의 hole 들이 산재하게 됩니다.

연속적인 메모리 할당기법에 의해 프로세스를 적재하기 위해서는 프로세스 보다 더 큰 크기를 가지는 hole이 필요한데 분포되어 있는 hole중 어떤 곳에 프로세스를 적재할지 정하는 알고리즘이 3 가지가 있습니다.

• 최초 적합 (First-fit) : 가용 공간들을 linked-list로 구현하여 충분히 큰 hole을 찾았을 때 검색을 바로 종료하고 프로세스를 적재합니다. 일반적으로 가장 빠른 방법입니다.
• 최적 적합 (Best-fit) : 가용 공간들을 최소힙으로 구현하여 hole중 가장 작은것부터 탐색합니다. 해당 프로세스가 적재가능한 hole 중 가장 작은 사이즈이 hole에 적재되기 때문에 메모리공간을 효율적으로 사용하게 됩니다.
• 최악 적합 (Worst-fit) : 가용 공간들을 최대힙으로 구현하여 hole중 가장 큰 것부터 탐색합니다. 프로세스가 가장 큰 hole부터 적재되기 때문에 남는 가용 공간들을 더 크게 가져갈 수 있습니다.

단편화 (Fragmentation)

특히 최초적합과 최적 적합에서 잘 일어나는 현상인데, 프로세스들이 적재되고 제거되는 일이 반복되다보면 가용공간들이 점점 작아지고 파편화되어 흩어지게 됩니다.

프로세스들이 위와 같이 메모리를 차지하고 있다면, 분명 남은 메모리공간이 있음에도, 파편화 되어있기 때문에 추가적으로 프로세스를 적재할 수 없는 상황이 발생합니다.
이를 해결하기 위해 페이징 (Paging)이란 기법을 사용하게 되는데 그 이전에 개념적으로 segmentation에 대해 알아보도록 하겠습니다.

위 그림처럼 왼쪽의 거대한 응용프로그램이 있다면 응용프로그램을 통째로 메모리에 배치하는 것이 아니라 응용프로그램의 각 기능을 담당하는 부분부분별로 나누어서 따로따로 메모리에 적재하는 기법입니다. 이렇게 되면 메인메모리가 파편화가 되었더라도, 응용프로그램을 분리시켜 적재하여 어느정도 극복이 가능하게 됩니다.
흔히 C언어 개발하다가 보면 Segmentation fault라는 에러를 자주 마주치게 되는데, 위 그림에서 알 수 있듯이 각 segment들이 특정 메모리 공간을 차지하고 있기 때문에 허용되지 않은 메모리에 접근하는 경우 일어나는 오류라고 이해할 수 있겠습니다.

페이징 (Paging)

프로세스의 물리주소공간이 연속적이지 않아도 쪼개어 적재할 수 있는 기법을 paging기법이라 부릅니다. 페이징은 메인메모리의 단편화문제를 해결할 수 있으므로 대부분의 운영체제에서 사용하고 있습니다.

페이징을 사용한 메모리 접근방법

먼저 물리 메모리공간을 프레임이라 불리는 균일한 크기의 블록들로 나눕니다. 이후 논리적 메모리공간은 페이지라 불리는 같은 크기의 블록들로 나눕니다.
CPU에서 참조하는 주소는 모두 페이지 번호(p)와 페이지 오프셋(d) 두 부분으로 이루어집니다. 그리고 페이지 번호는 실제 프레임 위치로 매핑되며 오프셋을 더해 정확한 메모리 주소에 접근합니다.
즉 CPU에서 나오는 페이지 번호와 오프셋으로 이루어진 논리주소를 물리주소로 변환하기 위해 MMU에서 일어나는 과정은 아래와 같습니다.

• 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 이동한다.
• 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
• f 프레임으로 이동하여 d위치에 있는 물리 주소를 참조한다.

이런식으로 논리주소에서는 물리주소를 전~~혀 신경쓰지 않고 페이지 단위로 주소를 접근하고싶어 합니다. 그저 이 페이지 번호를 인덱스 삼아 page table을 참조할 뿐입니다.
그럼 운영체제에서는 프로세스가 메모리에 적재될 때 page table에 비어있는 frame을 할당해주기만 하면 되는것입니다. 애초에 메모리를 균등한 프레임으로 나누어 할당해주기 때문에 외부 파편화를 완전 방지할 수 있습니다.
하지만 한가지 문제점이 또 생기는데, 만약에 page3이 아주 조금의 메모리만 필요하다면, 프레임 내부적으로 남는 메모리 공간이 생길 것입니다. 이를 내부 파편화라고 합니다.

효율적인 페이징 접근

현대 CPU에서는 상당히 큰 사이즈의 페이지 테이블을 사용하므로 빠른 속도의 레지스터를 사용하기엔 부적절합니다. (레지스터는 작은 사이즈에 적합) 따라서 페이지 테이블을 메인메모리에 저장하고 페이지 테이블 기준 레지스터 (PTBR)로 하여금 페이지 테이블을 가리키도록 합니다.
이렇게 하면 context changing 속도가 빨라지지지만 메모리에 직접 엑세스하는 시간이 느려질 수 있습니다.
이를 보완하기 위해 TLB(translation look-aside buffers)라 부르는 특수 소형 하드웨어 캐시를 사용하여 빠르게 검색하여 메모리에 바로 접근할 수 있도로 합니다.