메모리 관리

(참고 강의 : http://www.kocw.net/home/search/kemView.do?kemId=1046323)

Logical vs Physical Address

메모리(RAM)에 주소가 있는 것은 모두 알 것이다.
우리가 흔히 이야기 하는 주소는 Physical Address 일 것이다.
실제 메모리 어디에 있느냐
그런데 주소 종류가 1가지 더 있다.

Logical Address (=Virtual Address)

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작
• CPU가 보는 주소는 logical Address!

Physical Address

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

주소 바인딩 : 주소를 결정하는 것

Symbolic Address => Logical Address => Physical Address

Symbolic Address : 우리가 프로그래밍을 하면서 자연스럽게 사용하는 주소다.
인간의 입장으로서 실제 메모리 주소가 아닌 변수 명, 함수 명을 주소로 사용한다.

Logical Address : 소스코드를 컴파일한 실행파일 상에서 주소를 말한다.
Symbolic 주소가 Logical 주소로 바뀌었다.
컴퓨터는 이 주소를 따라 Jump하는 것이다.

Physical Address : 실제 메모리에 올라가는 주소다.

바인딩 방법은 크게 3가지가 있다.

Compile time binding

• physical address가 컴파일시 결정됨
• 시작 위치 변경 시 컴파일 다시 해야 됨
• 컴파일러가 절대 코드를 생성 (논리 주소 그대로 메모리에 올라가니까)

Load time binding

• Loader 책임하에 물리적 메모리 주소 부여
• 컴파일러가 재배치가능코드 생성한 경우 가능

실행 파일이 메모리에 올라갈 때 물리적 주소를 결정하는 것이다.

Execution time binding(= Runtime binding)

• 실행 중에 프로세스의 메모리 위치를 변경할 수 있음
• CPU가 주소를 참조할 때 마다 binding 점검 (address mapping table)
• 하드웨어 지원이 필요 (base, limit registers, MMU)

중요한 건 여기다.
메모리의 위치를 왜 계속 바꿔야 할까 생각해보자.
결국 메모리의 공간 때문이다.
메모리의 용량은 정해져 있다. 그리고 메모리 돈으로 사려면 ㅈㄴ 비싸다.
프로세스는 실행, 대기, 종료 등으로 상태가 계속 바뀐다.
메모리 공간이 중간 중간 구멍이 생길 수도 있고, ㅈㄴ 가끔 쓰는 프로세스 때문에 메모리 올려놓기는 공간이 너무 아깝다.
그래서 공간 재배치를 하기 위해 필요한 것이다.

아까 그림을 다시 보면

실행 중에 물리적 주소가 바뀐다. 또한 실행 파일에서 20,30으로 저장된 값이 진짜 20이 아닌 720,730을 참조해야 하기에, 0,100,200 단위를 시작으로 하는 것으로 보인다.

MMU(Memory-Management Unit)

CPU는 Logical Address를 참조한다고 했다.
그럼 이 주소를 진짜 Physical 위치로 변환해줘야 값을 불러와서 계산을 할 거 아닌가?
그것이 MMU(Memory Management Unit)다.

• logical address를 physical address로 매핑해주는 하드웨어 device

MMU Scheme

사용자 프로세스가 CPU에서 수행되며 생성하는 모든 주소값에 대해
base register(=relocation register) 값을 더한다.

User Program

• logical address만 다룬다.
• 실제 physical address를 볼 수도 없고, 알 필요도 없다.

사용자 프로그램은 logical 주소만 신경 쓰면 된다.
physical address는 우리 소관이 아니라 MMU 소관이다.

Dynamic Relocation

CPU가 346번지를 불러오고 싶다면,
MMU가 relocation Register(base register) 값과 더해서 Physical Address를 찾을 수 있다.

base register는 프로세스들의 메모리 시작 위치를 저장해논다.
limit register는 프로세스 전체 크기보다 큰 주소를 참고 하려고 할 때 거르려고 쓰는 것이다.
(ex. 프로세스 크기가 300인데 400번지 주소를 달라고? 응 꺼져~)

더 쉽게 도식화하면 이렇다.

참고 용어 정리

Dynamic loading

• 프로세스 전체를 메모리에 올리는 것이 아니라 해당 루틴이 불려질 때 load하는 것
• memory utilization 향상 (= 메모리 관리 굿)
• 가끔 사용하는 많은 양의 코드가 있을 경우 유용
• 운영체제 지원없이 프로그램 자체에서 구현 가능(os는 라이브러리로 지원 가능)

좋은 프로그램은 오류 처리, 보안 코드가 엄청 많다고 한다.
그런데 자주 쓰이지는 않으니, 메모리에 가~~끔 쓰는 걸 올리자니 공간 비효율.
그래서 다이나믹 로딩으로 관리하면 좋다! 이 소리다.

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만 올림
• 프로세스 크기가 메모리보다 클 때 유용
• 운영체제 지원없이 사용자에 의해 구현
• 작은 공간 메모리 사용하던 옛날 시스템에서 수작업으로 프로그래머가 구현해야됨
• Manual Overlay라고 부름

Dynamic loading이랑 똑같지 않은가?
똑같다.
다만 오버레이는 옛날에 프로그래머가 직접 이 부분을 구현해야 되는데,
Dynamic loading은 프로그래머가 신경쓸 필요없이 라이브러리 등이 해준다는 점이다.

Swapping

프로세스를 일시적으로 메모리에서 backing store로 보내는 것

backing store(=swap area)
하드 디스크의 부분이다.

• 많은 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간

Swap in / Swap out

• 중기 스케쥴러(swapper)에 의해 swap out 시킬 프로세스 선정
• priority-based CPU scheduling algorithm
  - priority 낮은 프로세스 swap out
  - priority 높은 프로세스 메모리에 올림
• compile time, load time binding에서는 원래 메모리 위치로 swap in 해야
• swap time은 대부분 transfer time(프로세스 용량만큼 시간 걸림)

Dynamic Linking

Linking을 실행 시간까지 미루는 기법

Static Linking

• 라이브러리가 실행 파일 코드에 포함
• 용량 커짐
• 동일한 라이브러리를 각각 프로세스가 메모리에 올리므로 낭비

Dynamic Linking

• 라이브러리가 실행시 연결(link)됨
• 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub 코드를 둠
• 라이브러리가 이미 메모리에 있으면 루틴의 주소로 가고, 없으면 디스크에서 읽어옴
• 운영체제 도움 필요

Allocation of Physical Memory

자 그럼 실제 메모리를 어떻게 할당하느냐

메모리는 일반적으로 두 영역으로 나뉜다.

• OS 상주 영역 (커널)
• 사용자 프로세스 영역

그 중에서

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

• Contiguous allocation : 각각 프로세스가 연속적인 공간에 적재
  - Fixed partition allocation
  - Variable partition allocation
  
• Noncontiguous allocation : 하나 프로세스가 메모리 여러 영역에 분산되어 올라갈 수 있음
  -Paging
  -Segmentation
  -Paged Segmentation

Contiguous allocation (올드 컴퓨터 방식)

각 프로세스가 통으로 메모리의 연속적인 공간에 적재

앞에서 본 Dynamic Relocation이

연속 할당에서 일어나는 것이다.
relocation register에 각 프로세스의 시작점을 알고 있다고 했지 않는가?
그 말은 즉슨 프로세스들이 통째로 메모리에 올라간다는 뜻이다.

고정 분할(Fixed Partition) 방식

• 물리적 메모리를 몇 개의 영구적 분할(parition)으로 나눔
• 분할 크기가 동일할 수도, 다를 수도
• 분할 당 하나의 프로그램 적재
• 융통성 없음(동시에 메모리 load 프로그램 수 고정, 최대 실행 프로그램 크기 제한)
• internal, external fragmentation 발생 (내부,외부 조각)

딱 봐도 단점이 보인다. 최대 실행 프로그램 수 제한, 프로그램 당 크기 제한, 메모리에 조각 조각 안 쓰는 공간 발생, 그래서 가변 분할 방식이 나온 것이다.

가변 분할(Variable partition) 방식

• 프로그램 크기 고려해서 할당
• 분할 크기, 개수가 동적으로 변함
• 기술적 관리 기법 필요
• External fragmentation 발생

빈 메모리에 차례대로 채워 넣는 것이다.
물론 여러 프로그램 실행, 종료 하다보면 빈 공간이 날 것이고,
아래와 같이 B가 끝나 공간이 생기고 크기가 큰 D가 실행한다면,
B자리가 아닌 다른 큰 공간에 들어갈 것이다. 얘도 외부 조각이 생길 것이다.
또한 프로그램을 어디 어디에 배치하는 기술적 관리도 필요할 것이다.

Hole

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

운영체제가 메모리의 어떤 부분이 사용 가능하고, 어떤 부분은 사용 중인걸 알아야
배치를 할 것 아닌가?

Dynamic Storage-Allocation Problem
가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

• First-fit : 최초로 찾아지는 hole에 할당
• Best-fit : n이상의 가장 작은 hole 찾아 할당, hole 리스트 다 탐색해야, 작은 hole 생성됨
• Worst-fit: 가장 큰 hole에 할당, 역시 모든 리스트 탐색, 큰 hole 생성됨

당연히 worst-fit이 속도, 공간 이용률 측면에서 효과적이겠지

Compaction = 압축

• external fragmentation 문제 해결하는 방법
• hole들을 몰아서 큰 block을 만드는 법
• 비용 많이 듬
• 최소한 메모리 이동으로 compaction (매우 복잡함)
• 프로세스 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행 가능

흩어진 hole들을 모으겠다는 말인데,
당연히 비용이 많이 들고, 실행 중인 프로세스들도 옮겨야 할 거 아닌가?
주소가 바뀌니 런타임 바인딩만 가능할 것이다.