Logical vs. Physical address

물리적 주소 상 낮은 주소에 운영체제 커널이 존재하고, 사용자가 실행한 프로그램이 높은 주소값에 들어간다.

프로그램이 메모리에 올라가기 전에, 독자적인 가상 메모리 공간에서 프로세스의 메모리 정보가 작성됨 -> 가상메모리의 정보가 물리적인 메모리 상에 올라가야 실행이 되는 것.

가상주소와 물리적 주소 간의 주소 변환이 필요하다!

프로그래밍을 할 때 사용자가 직접 메모리 주소를 적어가며 프로그래밍하지 않음.
변수이름 함수이름 등을 이용하여 프로그래밍. -> 이렇게 변수와 같이 주소 대신 상징성을 부여한 Symbolic address를 이용함.

symbolic address -> logical -> physical 순으로 주소 변환을 하게된다.

Logical address (=virtual address)

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작
• CPU가 보는 주소는 logical address 이다.
  : CPU는 기계어를 실행하고 기계어 하나 하나에 보이는 메모리 주소는 논리적 주소이기 때문.
  CPU가 바라보는 주소가 논리적 주소이므로 CPU는 메모리 접근할 때 마다 그때 그때 기계어 자체를 실행할 때 보이는 주소들은 주소 변환을 하여 접근하게 됨.

CPU가 메모리 접근할 때 마다 runtime binding 하에서는 런타임을 점검해야함. (메모리위치가 수시로 변할 수 있기 때문)

Physical address

• 메모리에 실제 올라가는 위치

주소 바인딩(address binding)

주소의 변환은 하드웨어(MMU)가 지원한다.
이러한 논리적 -> 물리적 주소 변환을 주소 바인딩이라고 한다.

주소 바인딩이 이루어지는 시점이 언제냐에 따라 다양한 주소 바인딩이 존재한다.

Compile time binding

• 물리적 메모리 주소(physical address) 가 컴파일 시 알려짐
• 시작 위치 변경시 재컴파일
• 컴파일러는 절대 코드(absolute code)를 생성함. -> 이렇게 만들어진 코드는 주소변환 과정이 필요없다.
• 논리적인 주소가 물리적 주소로 바뀌는 시점이 컴파일 하는 시점!
• 논리적 주소가 물리적 주소와 동일. (0번지 -> 0번지) : 현대적 범용 OS에는 맞지않음.

Load time binding

• 프로그램의 실행 시점에 주소 바인딩이 발생한다.
• loader의 책임 하에 물리적 메모리 주소 부여
• 컴파일러가 재배치가능코드(relocatable code, 물리적 주소위치가 바뀔수 있는 코드)를 생성한 경우 가능
• 프로그램 실행 시점에 물리적 주소가 정해지고 정해진 메모리주소는 바뀌지 않음.

Execution time binding(= Run time binding)

• 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음.
• CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table), 매번 메모리 접근할 때마다 주소변환이 필요함.
• 하드웨어적인 지원이 필요하다.(ex. base and limit registers, MMU)
• 프로그램 실행 시점에 물리적 주소가 정해지고, 프로그램 실행 도중에 바인딩이 변경될 수 있다.

Memory Management Unit, MMU

• MMU : logical address 를 physical address로 매핑해주는 하드웨어 기기
• MMU Scheme: 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (=relocation register)의 값을 더한다.
• user program
  : logical address 만을 다룬다.
  실제 physical address 를 볼 수 없으며 알 필요가 없다.

MMU 내에 레지스터 두 개(relocation register, limit register)를 통해 논리 주소를 물리 주소로 변환해준다.
두 레지스터는 운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터이다.

• relocation register(= base register): 접근할 수 있는 물리적 메모리 주소의 최소값.
• limit register: 논리적 주소의 범위. 프로그램의 크기를 담는다. -> 악의적인 메모리 주소 접근을 방지하기 위해 해당 프로그램 메모리 주소 범위를 벗어나는 요청을 처리하지 않으려고 존재.

Dynamic Loading

loading : 메모리로 데이터를 올리는 것.

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 로드하는 것.
• memory utilization(이용률)의 향상
• 가끔씩 사용되는 많은 양의 코드의 경우 유용. (ex. 오류 처리 루틴같은 경우 잘 안사용되므로, 동적 로딩을 통해 메모리를 효율적으로 사용할 수 있다.)
• 운영체제의 특별한 지원 없이 프로그램 자체에서 라이브러리를 통해 구현 가능 ( OS는 라이브러리를 통해 지원 가능 )
• 현대적 범용 OS는 사용하고 있지는 않음.(동적이긴 하지만, 프로그램 자체에서 구현하지는 않음)

필요할 때 마다 필요한 프로세스 가상 메모리 내용을 물리 메모리에 올려서 사용하는 방식.

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올린다.
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현.
  -> "Manual Overlay", 프로그래밍이 매우 복잡하다.

동적 로딩과 오버레이는 의미가 유사하다. 역사적인 부분에서 용어의 차이가 있다.
초창기에는 메모리가 작다보니 프로그래머가 코딩하면서 물리적인 메모리 관리까지도 수작업(manual)으로 진행하였음.

Swapping

• 프로세스를 일시적으로 메모리에서 backing store(=swap area) 로 쫓아내는 것.
• Backing store: 디스크, 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in / Swap out
  : 일반적으로 중기 스케줄러(swapper) 에 의해 swap out 시킬 프로세스 선정
  메모리가 부족할 때 프로세스를 통째로 내쫓는게 중기 스케줄러의 역할.

priority-based CPU scheduling algorithm

• priority가 낮은 프로세스를 swapped out 시킴.
• priority가 높은 프로세스를 메모리에 올림.

Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야함 -> swapping 비효율적.
Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음. -> 효율적.
Swapping 해주면 메모리에 있던 걸 디스크로 쓰기. 또는 읽기 해야하는데, 그 I/O 과정에서 발생하는 swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임.

Swapping 하게 되면, 주소값이 유동적인 runtime binding을 활용하는 것이 좋음.
스왑아웃되고 나서, 해당 메모리 자리는 다른 프로세스가 존재한다면 다른 메모리주소를 할당해주면 되기 때문.

여기서의 Swapping은 프로세스 통째로 왓다갓다하는 것을 의미함.

Dynamic Linking

• Linking을 실행 시간(execution time)까지 미루는 기법

• Static linking (static library)
  라이브러리가 프로그램의 실행 파일 코드에 포함됨
  실행 파일의 크기가 커짐
  동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비.

• Dynamic linking (shared library) .so .dll 등
  라이브러리가 실행 시, 라이브러리 파일을 찾아서 메모리에 올려서 실행됨.
  라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub라는 작은 코드를 둠
  라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고, 없으면 stub를 참고하여 디스크에서 읽어옴.
  운영체제의 도움이 필요.

프로그램 실행 파일 안에 printf가 없고 printf의 위치정보만 담겨있다. -> 쉐어드 라이브러리를 올려서 함수 실행. -> 다른 프로그램이 printf를 실행하면, 이미 올라가있는 메모리의 함수 정보를 가져와서 사용. (메모리 활용이 효율적임)

Allocation of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘어 사용됨.
1. OS 상주 영역: interrupt vector와 함께 낮은 주소 영역 사용
2. 사용자 프로세스 영역: 높은 주소 영역 사용.

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

1. Contiguous allocation (연속 할당)
   각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것. 프로그램이 쪼개지지 않고 메모리에 프로세스 통째로 올라가는 방식. 주소변환이 비교적 간단하다.

External fragmentation

• 프로그램 크기보다 분할의 크기가 작은 경우
• 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할

Internal fragmentation

• 프로그램 크기보다 분할의 크기가 큰 경우
• 하나의 분할 내부에서 발생하는 사용되지 않는 메모리조각
• 특정 프로그램에 배정되었지만 사용되지 않는 공간.

Fixed partition allocation

"고정 분할 방식"
물리적 메모리를 몇 개의 영구적 분할(partition)로 나누어 둠.
분할의 크기가 모두 동일한 방식 또는, 크기가 서로 다른 방식이 존재
분할 당 하나의 프로그램을 적재함
융통성이 없음: 동시에 메모리에 load되는 프로그램의 수가 고정됨. 최대 수행 가능 프로그램 크기 제한
internal fragmentation, 내부조각 발생 (external fragmentation 도 발생)
: 분할에 할당되는 프로그램의 크기가 분할의 크기보다 작을 경우, 메모리를 사용하고 남은 빈 공간이 존재. 이를 internal fragmentation이라 한다.

외부조각의 경우, 프로그램의 크기가 분할 크기보다 커서, 해당 분할 영역에 할당되지 못하고 낭비되는 경우 그 분할 영역을 외부조각(external fragmentation)이라고 한다.

Variable partition allocation

"가변분할 방식"
프로그램의 크기를 고려하여 할당.
분할의 크기, 개수가 동적으로 변함
기술적 관리 기법 필요
External fragmentation 발생, 아래 그림에서 프로그램B가 끝나고 D가 들어가지 못하고 낭비되는 영역이 외부조각.

Hole

• 가용 메모리 공간
• 다양한 크기의 홀들이 메모리 여러 곳에 흩어져있음.
• 프로세스가 도착하면 수용가능한 홀을 할당
• 운영체제는 다음의 정보를 유지.
  : a) 할당공간, b) 가용공간(hole)

Dynamic storage-Allocation Problem

: 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 홀을 찾는 문제

• First-fit: size 가 n 이상인 것 중 최초로 찾아지는 hole에 할당
• Best-fit: size 가 n 이상인 가장 작은 홀을 찾아 할당.
  Hole의 리스트가 크기순으로 정렬되지 않은 경우 모든 홀의 리스트를 탐색해야함.
  많은 수의 아주 작은 홀들이 생성됨.
• Worst-fit
  가장 큰 홀에 할당
  역시 모든 리스트를 탐색해야함
  상대적으로 아주 큰 홀들이 생성됨

first, best-fit이 속도와 공간 이용률 측면에서 효과적임.

compaction

• external fragmentation 문제를 해결하는 한 가지 방법
• 사용중인 메모리 영역을 한군데로 몰고 홀들을 다른 한 곳으로 몰아 큰 블록을 만드는 것
• 매우 비용이 많이 드는 방법이다
• 최소한의 메모리 이동으로 compaction하는 방법 ( 매우 복잡한 문제 )
• Compaction 은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있음

현대 운영체제에서 위 두가지 방식을 사용하고 있지는 않다.

---

다음 시간엔 불연속 할당에 대한 과정을 배워보자.

2. Noncontiguous allocation (불연속 할당)
   하나의 프로세스가 메모리의 여러 영역에 분산되어 산발적으로, 혹은 스토리지로 올라갈 수 있음

• Paging
• Segmentation
• Paged Segmentation