[OS] Memory Management

CS/OS (2022-1)

[OS] Memory Management - 1

샤아이인 2022. 11. 29. 13:14

본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다.

1. Logical vs Physical Address

1 - 1) Logical Address

프로세스마다 독립적으로 가지는 주소 공간

각 프로세스마다 0번지부터 시작

CPU가 보는 주소는 논리적 주소이다.

1 - 2) Physical Address

메모리에 실제로 올라가는 위치이다.

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

1 - 3) Address Binding

프로세스의 논리적 주소를 물리적 메모리 주소로 연결하는 작업을 말한다.

Process마다 독자적인 논리적 주소가 있지만, 실제로 실행되기 위해서는 물리적 메모리에 올라가야 하기 때문에

이에 대한 변환이 필요하다.

이러한 주소 변환을 주소 바인딩 이라 부른다.

참고로, Symbolic Address는 프로그래머 입장에서 사용하는 것으로, 변수 이름과 같은 형태의 주소를 말한다.

주소 바인딩의 방식은 프로그램이 적재되는 물리적 메모리의 주소가 결정되는 시기에 따라 세 가지로 분류할 수 있다.

1 - 3 - 1) Compile time binding

물리적 메모리 주소가 프로그램을 컴파일할 때 결정되는 주소 바인딩 방식이다.

컴파일을 하는 시점에 해당 프로그램이 물리적 메모리의 몇 번지에 위치할 것인지를 결정하므로 프로그램이 절대 주소로 적재된다는 뜻에서 절대 코드(absolute code)를 생성하는 바인딩 방식이라고 부른다.

프로그램이 올라가 있는 물리적 메모리의 위치를 변경하고 싶다면 컴파일을 다시 수행해야 한다.

현대의 시분할 컴퓨팅 환경에서 거의 사용하지 않는 방식이다.

1 - 3 - 2) Load time binding

프로그램의 실행이 시작될 때에 물리적 메모리 주소가 결정되는 주소 바인딩 방식이다.

Loader의 책임 하에 물리적 메모리 주소가 부여되며 프로그램이 종료될 때까지 물리적 메모리 상의 위치가 고정된다.

(로더는 사용자 프로그램을 메모리에 적재하는 프로그램이다.)

컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우에만 가능하다.

재배치 가능 코드란, 항상 동일한 위치가 아닌, 실행시 비어있는 위치에는 어느곳이든 올라갈 수 있는 코드를 말한다.

1 - 3 - 3) Execution time binding(= Runtime binding)

프로그램이 실행을 시작한 후에도 그 프로그램이 위치한 물리적 메모리 상 위치를 변경할 수 있는 바인딩 방식이다.

CPU가 주소를 참조할 때마다 해당 데이터가 물리적 메모리의 어느 위치에 존재하는지 확인해야하는데, 이때 주소 매핑 테이블(MMU)을 사용한다. (MMU는 논리적 주소를 물리적 주소로 매핑하는 하드웨어 장치이다.)

base 레지스터, limit 레지스터 등과 같은 하드웨어적인 자원이 필요하다.

소스코드를 컴파일 하여 실행파일을 만들었을 때, "0: Add 20, 30" 인스트럭션을 생각해보면 CPU가 메모리 20번지의 값과 30번지의 값을 CPU로 불러 읽어 들인후에 합하게된다.

이때 이 20, 30번지의 값들은 Logical Address이다.

이 주소들이 실행이 되어 메모리에 올라 가더라도, 인스트럭션 코드 안에 있는 20, 30은 바뀌지가 않는다.

즉, 컴파일된 코드에 들어 있는 주소까지 바꿀수는 없다.

메모리에 올라갈때 시작 위치는 바뀌지만(0: Add -> 500: Add), 그 안에 있는 코드상의 주소는 Logical Address로 남아있을 수 밖에 없다.

즉, CPU가 바라보는 주소도 Logical Address 인 이유이다!

1 - 4) MMU (Memory-Management Unit) (주소 변환 하드웨어)

Logical Address를 Physical Address로 매핑해 주는 하드웨어 장치이다.

MMU를 사용한 기법을 MMU Scheme라고 하는데, 사용자 프로세스가 CPU에서 수행되며 생성해 내는 모든 주소 값에 대해 기준 레지스터의 값을 더하는 방식을 말한다.

MMU 기법에서 사용자 프로그램이나 CPU는 논리적 주소만을 다룰 뿐, 실제 메모리 주소는 알지 못하며 알아야 할 필요도 없다.

1 - 4 - 1) MMU 기법의 동작 과정

CPU가 Logical Address 346번지에 있는 내용을 달라고 하면, MMU는 2개의 레지스터(relocation, limit register)를 가지고 변환을 하게 된다.
MMU는 rerolcation register에다가 프로그램의 시작 위치를 저장해둡니다. (위 사진에서 14000 저장)
주소변환을 할때는, 실제 물리적 메모리의 시작 위치와 논리적 메모리 주소를 더한 값을(14346) CPU에게 전달한다.
- 논리적 메모리 주소는 offset 개념과 유사하다.
limit register는 프로그램의 크기(3000)를 나타내며 논리적 주소의 범위를 뜻한다. 이 범위를 넘어서는 주소를 요청하면 안 된다.

1 - 4 - 2) MMU scheme

사용자 Process가 CPU에서 수행되며 생성해주는 모든 주소값에 대해 base register(relocation register)의 값을 더한다.

이를 순서도를 통해 생각해보면 다음과 같다.

1) CPU가 메모리 몇번지를 달라고 요청해오면, limit register를 통해 논리 주소가 프로그램 크기보다 더큰 주소지인지?를 확인한다.

2) 이때 CPU가 요청한 논리적 주소 값을 limit register 범위를 넘어서면 trap을 발생시켜 프로세스를 강제 종료한다.

3) 그렇지 않으면 base register(rerolcation register)의 값을 더해서 물리적 주소로 변환한다.

4) 이렇듯, 사용자 프로그램은 논리적 주소만 다루므로 실제 물리적 주소를 알 필요는 없다.

사용자 프로그램은 Logical Address만 다루고 있다.

실제 물리적 주소는 볼수 없으며, 알 필요도 없다.

2. 메모리 관리와 관련된 용어

2 - 1) Dynamic Loading

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

2- 2) Dynamic Linking

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

2 - 3) Overlays

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

2- 4) Swapping

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

3. 물리적 메모리의 할당 방식

물리적 메모리는 운영체제 상주 영역과 사용자 프로세스 영역으로 나뉜다.

운영체제 상주 영역은 인터럽트 벡터와 함께 낮은 주소 영역을 사용한다. (1GB)
사용자 프로세스 영역은 높은 주소 영역을 사용한다.

출처 - https://gabrieletolomei.wordpress.com/miscellanea/operating-systems/in-memory-layout/

▶ 사용자 프로세스 영역의 할당 방법

연속 할당
- 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것이다.
- 고정 분할 방식과 가변 분할 방식이 존재한다.
불연속 할당
- 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가는 것이다.
- Paging, Segmentaing, Paged Segmentation 방식이 존재한다.

3 - 1) 연속 할당

3 - 1 - 1) Fixed partition allocation (고정 분할 방식)

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

3 - 1 - 2) Variable partition allocation 가변 분할 방식

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

▶ Hole

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

▶ 동적 메모리 할당 문제

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

First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 효과적이다. (실험적 결과)

▶ Compaction (압축)

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

3 - 2) 불연속 할당

Paging, Segmentation, Paged Segmentation 방식이 있다.

3 - 2- 1) 페이징

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