[반효경 운영체제] Memory Management 1

operating-system-study에서 스터디를 진행하고 있습니다.

논리적 주소 vs 물리적 주소

논리적 주소 (가상 주소)

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작
• CPU가 보는 주소는 논리적 주소이다.

 

물리적 주소

• 메모리에 실제로 올라가는 위치이다.
• 보통 메모리의 낮은 주소 영역에는 운영체제가 올라가고, 높은 주소 영역에는 사용자 프로세스가 올라간다.

 

주소 바인딩

• 프로세스의 논리적 주소를 물리적 메모리 주소로 연결하는 작업을 말한다.
  • Symbolic Address → Logical Address (바로 이 시점)→ Physical Address
  • Symbolic Address는 프로그래머 입장에서 사용하는 것으로, 변수 이름과 같은 형태의 주소를 말한다.
• 주소 바인딩의 방식은 프로그램이 적재되는 물리적 메모리의 주소가 결정되는 시기에 따라 세 가지로 분류할 수 있다.

 

Compile time binding (컴파일 타임 바인딩)

• 물리적 메모리 주소가 프로그램을 컴파일할 때 결정되는 주소 바인딩 방식이다.
• 컴파일을 하는 시점에 해당 프로그램이 물리적 메모리의 몇 번지에 위치할 것인지를 결정하므로 프로그램이 절대 주소로 적재된다는 뜻에서 절대 코드를 생성하는 바인딩 방식이라고 부른다.
• 프로그램이 올라가 있는 물리적 메모리의 위치를 변경하고 싶다면 재컴파일해야 한다.
• 현대의 시분할 컴퓨팅 환경에서 거의 사용하지 않는다.

 

Load time binding (로드 타임 바인딩)

• 프로그램의 실행이 시작될 때에 물리적 메모리 주소가 결정되는 주소 바인딩 방식이다.
• Loader의 책임 하에 물리적 메모리 주소가 부여되며 프로그램이 종료될 때까지 물리적 메모리 상의 위치가 고정된다.
  • 로더는 사용자 프로그램을 메모리에 적재하는 프로그램이다.
• 컴파일러가 재배치 가능 코드를 생성한 경우에만 가능하다.

 

Execution time binding 또는 Runtime binding (실행 시간 바인딩)

• 프로그램이 실행을 시작한 후에도 그 프로그램이 위치한 물리적 메모리 상 위치를 변경할 수 있는 바인딩 방식이다.
• CPU가 주소를 참조할 때마다 해당 데이터가 물리적 메모리의 어느 위치에 존재하는지 확인해야하는데, 이때 주소 매핑 테이블(MMU)을 사용한다.
  • MMU는 논리적 주소를 물리적 주소로 매핑하는 하드웨어 장치이다.
• 기준 레지스터, 한계 레지스터 등과 같은 하드웨어적인 자원이 필요하다.

 

주소 바인딩 기법 예시

 

컴파일 타임 바인딩

• 프로그래머는 A, B와 같은 심볼릭 주소를 사용하며, 소스 코드를 컴파일해서 실행 파일이 만들어지면, 심볼릭 주소는 논리적 주소로 변환된다.
• 이제 이 파일이 실행되려면 물리적 메모리에 올라가야 하고, 컴파일 시점에 물리적 메모리 주소가 결정된다. 또한 컴파일러는 절대 코드를 생성한다.
• 과거에는 프로세스 하나 올리기도 벅차서, 여러 프로세스가 올라갈 일이 없으므로 컴파일 타임 바인딩 기법을 주로 사용하였다.

 

로드 타임 바인딩

• 프로그램이 실행되어 물리적 메모리에 올라갈 때 물리적 메모리 주소가 결정된다.
• 물리적 메모리를 보았더니, 마침 500번지부터 비어있으면 해당 위치로 주소를 정한다.
• 컴파일러가 절대 코드가 아닌 재배치 가능한 코드를 생성한다. 이 의미는 항상 특정 위치에 고정된 것이 아닌, 실행 시에 비워져 있다면 어디든 메모리에 올릴 수 있다는 뜻이다.
• 실행 중에는 물리적 메모리 주소가 변하지 않는다.

 

런타임 바인딩

• 로드 타임 바인딩처럼 프로그램이 실행되어 물리적 메모리에 올라갈 때 물리적 메모리 주소가 결정되는 것은 동일하다.
• 다만 이 기법은 실행 중에도 물리적 메모리를 바꿀 수 있다.
• CPU가 어떤 메모리 주소를 요청할 때마다 물리적 메모리 주소가 비워져 있는지 확인해야 하므로 논리적 메모리 주소를 물리적 메모리 주소로 변환하는 MMU 하드웨어를 사용한다.

 

MMU (Memory-Management Unit)

• 논리적 주소를 물리적 주소로 매핑해 주는 하드웨어 장치이다.
• MMU를 사용한 기법을 MMU Scheme라고 하는데, 사용자 프로세스가 CPU에서 수행되며 생성해 내는 모든 주소 값에 대해 기준 레지스터의 값을 더하는 방식을 말한다.
  • MMU 기법에서 사용자 프로그램이나 CPU는 논리적 주소만을 다룰 뿐, 실제 메모리 주소는 알지 못하며 알아야 할 필요도 없다.

 

MMU 기법의 동작 과정

• CPU가 논리적 메모리 346번지에 있는 내용을 달라고 하면, MMU는 2개의 레지스터를 가지고 변환을 하게 된다.
• 이때, 실제 물리적 메모리의 시작 위치와 논리적 메모리 주소를 더한 값을 CPU에게 전달한다.
  • 논리적 메모리 주소는 offset 개념으로 생각할 수 있다.
• 기준 레지스터(재배치 레지스터)가 물리적 메모리의 시작 위치를 갖고 있으며, 접근할 수 있는 물리적 메모리 주소의 최솟값에 해당한다.
• 한계 레지스터는 프로그램의 크기를 나타내며 논리적 주소의 범위를 뜻한다. 이 범위를 넘어서는 주소를 요청하면 안 된다.

 

• 위 순서도와 같이 CPU가 요청한 논리적 주소 값을 한계 레지스터와 비교하여 범위를 넘어서면 trap을 발생시켜 프로세스를 강제 종료한다.
• 그렇지 않으면 기준 레지스터(재배치 레지스터)의 값을 더해서 물리적 주소로 변환한다.
• 이렇듯, 사용자 프로그램은 논리적 주소만 다루므로 실제 물리적 주소를 알 필요는 없다.

 

메모리 관리와 관련된 용어

동적 로딩

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것이다.
  • load는 메모리에 올린다는 뜻이다.
• Memory Utilization이 향상된다.
• 가끔씩 사용되는 많은 양의 코드의 경우 유용하다.
  • ex) 오류 처리 루틴
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현이 가능하며, 운영체제가 라이브러리를 통해 지원할 수도 있다.

 

오버랩

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올리는 기법이다.
• 초창기 컴퓨터 시스템에서 물리적 메모리의 크기 제약으로 인해 하나의 프로세스조차도 메모리에 한꺼번에 올릴 수 없을 때, 프로세스의 주소 공간을 분할해서 당장 필요한 일부분을 메모리에 올려 실행하고 해당 부분에 대한 실행이 끝난 후에 나머지 부분을 올려 실행하는 기법을 뜻한다.
• 프로세스의 크기가 메모리보다 클 때 유용하다.
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 운영체제의 지원 없이 수작업으로 프로그래머가 구현하였다.
  • 수작업 오버랩
  • 프로그래밍이 상당히 복잡하다.
• 동적 로딩과의 차이점
  • 동적 로딩: 다중 프로세스 환경에서 메모리에 더 많은 프로세스를 동시에 올려놓고 실행하기 위한 용도이다.
  • 오버랩: 단일 프로세스만을 메모리에 올려놓는 환경에서 메모리 용량보다 큰 프로세스를 올리기 위한 어쩔 수 없는 선택이다.

 

Swapping (스와핑)

• 메모리에 올라온 프로세스의 주소 공간 전체를 디스크의 backing store로 쫓아내는 것이다.
  • backing store는 swap area라고 부르며, 디스크 내에 파일 시스템과는 별도로 존재하는 많은 사용자의 프로세스를 담을 만큼 충분히 빠르고 큰 저장 공간이다.
• 디스크에서 메모리로 올리는 작업을 swap in, 메모리에서 디스크로 내리는 작업을 swap out라고 부른다.
• swap이 일어나는 과정
  • 일반적으로 중기 스케줄러가 swap out할 프로세스를 선정한다.
    • 주로, 우선 순위 기반 CPU 스케줄링을 사용한다.
    • 우선 순위가 낮은 프로세스를 swap out함.
    • 우선 순위가 높은 프로세스를 swap in함.
  • 만약 컴파일 타임 바인딩 혹은 로드 타임 바인딩이 사용되고 있다면, swap out되었다가 swap in이 되면 원래 존재하던 메모리 위치로 다시 올라가야 한다.
  • 반면 런타임 바인딩이 사용되고 있다면, 추후 빈 메모리 영역 아무 곳에나 프로세스를 올릴 수 있으므로 Swapping에 적합하다.
• swap time은 디스크의 탐색 시간이나 회전 지연 시간 보다는 디스크 섹터에서 실제 데이터를 읽고 쓰는 전송 시간(transfer time)이 대부분을 차지한다.

 

동적 연결

• 연결(linking)이란 프로그래머가 작성한 소스 코드를 컴파일하여 생성된 목적 파일(object file)과 이미 컴파일된 라이브러리 파일들을 묶어 하나의 실행 파일을 생성하는 과정이다.
• 동적 연결은 컴파일을 통해 생성된 목적 파일과 라이브러리 파일 사이의 연결을 프로그램의 실행 시점까지 지연하는 기법이다.
• 정적 연결
  • 라이브러리가 프로그램의 실행 파일 코드에 포함된다.
  • 실행 파일의 크기가 커진다.
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비가 심하다. (ex. printf 함수의 라이브러리 코드)
• 동적 연결
  • 실행 파일에 라이브러리 코드가 포함되지 않으며, 프로그램이 실행되면서 라이브러리 함수를 호출할 때가 되어서야 라이브러리에 대한 연결이 이루어진다.
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다.
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고, 없으면 디스크에서 읽어 온다.
  • 운영 체제의 도움이 필요하다.

 

물리적 메모리의 할당 방식

• 물리적 메모리는 운영체제 상주 영역과 사용자 프로세스 영역으로 나뉜다.
  • 운영체제 상주 영역은 인터럽트 벡터와 함께 낮은 주소 영역을 사용한다.
  • 사용자 프로세스 영역은 높은 주소 영역을 사용한다.
• 사용자 프로세스 영역의 할당 방법
  • 연속 할당
    • 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것이다.
    • 고정 분할 방식과 가변 분할 방식이 존재한다.
  • 불연속 할당
    • 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가는 것이다.
    • Paging, Segmentaing, Paged Segmentation 방식이 존재한다.

 

연속 할당

 

고정 분할 방식

• 메모리를 주어진 개수만큼의 영구적인 파티션으로 미리 나누어두고 각 파티션에 하나의 프로세스를 적재해 실행한다.
• 동시에 메모리에 올릴 수 있는 프로그램의 수가 고정되어 있으며 수행 가능한 프로그램의 최대 크기 또한 제한된다는 점에서 융통성이 떨어진다.
• 외부 조각과 내부 조각이 발생할 수 있다.
  • 외부 조각: 프로그램의 크기보다 파티션의 크기가 작은 경우 해당 파티션이 비어있는 데도 불구하고 프로그램을 적재하지 못하기 때문에 생기는 메모리 공간을 의미한다.
    • 내가 올리려는 프로그램보다 메모리 크기가 작다.
  • 내부 조각: 프로그램의 크기보다 파티션의 크기가 큰 경우 해당 파티션에 프로그램을 적재하고 남는 메모리 공간을 의미한다.
    • 내가 올리려는 프로그램보다 메모리 크기가 크다.

 

가변 분할 방식

• 메모리에 적재되는 프로그램의 크기에 따라 파티션의 크기, 개수가 동적으로 변하는 방식이다.
• 고정 분할 방식과 달리 미리 메모리 영역을 나누어 놓지 않는다.
• 프로그램이 실행될 때마다 차곡차곡 메모리에 올리므로 내부 조각이 발생하지 않는다.
  • 다만 중간에 프로그램이 종료되어 메모리에서 빠져 나가고, 그 공간에 새로운 프로그램이 메모리에 할당될 경우 외부 조각이 발생할 수 있다.

 

Hole

• 가용 공간을 의미한다.
  • 가용 공간이란 사용되지 않은 메모리 공간으로서 메모리 내의 여러 곳에 산발적으로 존재할 수 있다.
• 프로세스가 도착하면 수용 가능한 hole을 할당해야 한다.
• 운영 체제는 이미 사용 중인 메모리 공간인 할당 공간과 사용하고 있지 않은 가용 공간에 대한 정보를 유지하고 있다.
• 아래 그림에서 어두운 색 영역이 Hole이다.

 

 

동적 메모리 할당 문제

• 가변 분할 방식에서 주소 공간의 크기가 n인 프로세스를 메모리에 올릴 때 물리적 메모리 내의 가용 공간 중 어떤 위치에 올릴 것인지 결정하는 문제이다.
• First-fit
  • size가 n 이상인 것 중 최초로 찾아지는 hole에 할당한다.
• Best-fit
  • size가 n 이상인 가장 작은 hole을 찾아서 할당한다.
  • Hole들의 리스트가 크기 순으로 정렬되지 않은 경우 모든 hole을 탐색해야 한다.
  • 많은 수의 아주 작은 hole이 생성된다.
• Worst-fit
  • 가장 큰 hole에 할당한다.
  • 역시 hole을 탐색해야 한다.
  • 상대적으로 아주 큰 hole이 생성된다.
• First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 효과적이다.

 

Compaction (압축)

• 외부 조각 문제를 해결하는 방법 중 하나이다.
• 물리적 메모리 중에서 프로세스에 의해 사용 중인 메모리 영역을 한 쪽으로 몰고, 가용 공간들을 다른 한쪽으로 몰아서 하나의 큰 가용 공간을 만드는 방법이다.
• 매우 비용이 많이 드는 방법이다.
• 최소한의 메모리 이동으로 압축하는 방법은 매우 복잡한 문제이다.
• 압축은 프로세스의 주소가 실행 시간에 동적으로 재배치가 가능한 런타임 바인딩 방식을 지원하는 환경에만 가능하다.

 

불연속 할당

• 페이징, 세그멘테이션, 페이지드 세그멘테이션이 있음.
• 이번 시간에는 페이징 기초만 다루고 넘어가고, 다음 시간부터 불연속 할당을 다룰 예정.

 

페이징

• 프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지를 저장하는 방식이다.
• 각 프로세스의 주소 공간 전체를 물리적 메모리에 한꺼번에 올릴 필요가 없고, 일부는 backing storage, 일부는 물리적 메모리에 혼재하는 것이 가능하다.
• 물리적 메모리를 페이지와 같은 동일한 크기의 프레임으로 미리 나누어 둔다.
• 메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로 외부 조각이 발생하지 않고, 동적 메모리 할당 문제도 고려할 필요가 없다.
• 페이지 테이블을 사용하여 논리적 주소를 물리적 주소로 변환하는 작업이 필요하다.
• 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없으므로 프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 내부 조각이 발생할 수 있다.

출처

• https://velog.io/@yuhyerin/kocw-운영체제-반효경-8.-Memory-Management1#10-paging-페이징
• https://core.ewha.ac.kr/publicview/C0101020140425151219100144?vmode=f
• 운영체제와 정보 기술의 원리 - 반효경