[week09] KOCW 운영체제(반효경교수님) - Memory Management 1

Memory Management 1

Logical vs Physical address

Logical address (=virtual address)

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

Physical address(DRAM)

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

Logical address와 Physical address는 어떻게 연결될까?

• A. 주소 바인딩을 통해서

어떤 프로그램이 물리적인 메모리 어디에 올라갈지 결정하는 것

Symbolic Address(변수 이름, 함수 이름) → Logical Address(숫자 주소) → Physical address(실제 주소)

주소 바인딩(address binding)

logical address가 실행이 되려면 physical address에 올라가야 하는데 이 주소변환(address binding)은 언제 진행해야 할까? 크게 compile 될 때, load 될 때, execution 될 때 binding되는 경우를 나눠서 생각해볼 수 있다.

Compile time binding

물리적 메모리 주소(physical address)가 컴파일 시 알려짐
시작 위치 변경시 재컴파일해야함
컴파일러는 절대 코드(absolute code) 생성
비효율적이라 현재에는 쓰이지 않음

Load time binding

Loader의 책임하에 물리적 메모리 주소 부여
컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능
컴파일을 하고 나면 논리적인 주소까지만 결정이 되고, 프로그램이 실행되어서 메모리에 올라갈 때 물리적 주소가 결정됨

Execution time binding(=Run time binding)

수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있다.
CPU가 주소를 참조할 때마다 binding을 점검(address mapping table)
하드웨어적인 지원이 필요(ex: base and limit registers, MMU)
현대의 컴퓨터는 run time binding을 지원한다.

Memory-Management Unit(MMU)

MMU

• logical address를 physical address로 매핑해주는(주소변환을 위한) hardware device

MMU scheme

• 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register)의 값을 더한다.
• limit register는 프로세스가 허용되지 않은 메모리 주소를 요청하는 것을 막는다.

user program

• logical address만을 다룬다.
• 실제 physical address를 볼 수 없으며 알 필요도 없다(protection 차원).

Hardware support for address translation

운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터

• limit register: 논리적 주소의 범위를 설정해줌
• relocation register(=base register): 접근할 수 있는 물리적 메모리 주소의 최솟값

4가지 용어에 대해 알아보자(Dynamic Loading, Overlays, Swapping, Dynamic Linking).

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것.

좋은 프로그램은 방어적으로 설계되기 때문에 오류 처리 루틴이 굉장히 많다. 그런데 실제로 프로그램에서 자주 사용되는 코드는 한정적이다. 이럴 경우, Dynamic Loading을 사용하면 효율적이다.

memory utilization(메모리 이용도)의 향상

운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원가능)

• paging 기법과 dynamic loading은 원래는 다른 것이다.
• 프로그래머가 명시적으로 dynamic loading을 구현하는 것이 dynamic loading이지만 운영체제가 알아서 올려놓고, 쫓아내고 하는 것도 dynamic loading이라는 말을 쓰기도 함

Loading: 메모리로 올리는 것을 의미

Overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올려놓는 것

운영체제의 지원 없이 사용자에 의해 구현

작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현

• Manual Overlay
• 운영체제의 라이브러리를 사용할 수 있는 dynamic loading보다 구현이 더 어려움

Swapping

swapping

프로세스를 일시적으로 메모리에서 backing store(하드디스크)로 쫓아내는 것

backing store(=swap area)

디스크: 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장공간

swap in / swap out

일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정

priority-based CPU scheduling algorithm

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

swapping이 효율적이려면 run time binding이 지원되는 것이 좋음

• compile time 혹은 load time binding에서는 쫓겨난 후에 다시 돌아올 때 원래 메모리 위치로 swap in 해야해서 비효율적임

swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임

• 용량이 방대하기 때문

지금 우리가 다루는 swapping은 하나의 프로그램이 통째로 쫓겨나는 것을 말한다(원칙적으로는 이게 맞음). 최근에는 page를 활용해서 프로그램 주소공간이 잘게 짤려서 일부 page가 메모리에서 쫓겨나는 형태를 띄는데, 이를 swap out이라고 표현하기도 한다.

Dynamic Linking

linking?

• 여러 군데에 존재하던 컴파일된 파일을 묶어서 하나의 실행파일을 만드는 과정

dynamic linking: linking을 실행시간(execution time)까지 미루는 기법

Static linking

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

Dynamic linking

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

물리적인 메모리를 어떻게 관리할 것인가?

Allocation of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘어 사용

OS 상주 영역(kernel 영역)

• interrupt vector와 함께 낮은 주소 영역 사용

사용자 프로세스 영역(user 영역)

• 높은 주소 영역 사용

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

Contiguous allocation(연속 할당)

• 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
• Fixed partitioin allocation
• Variable partition allocation

Noncontiguous allocation(불연속 할당)

• 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
• Paging
• Segmentation
• Paged Segmentation
• 현대 시스템에서는 이 방식 사용

Contiguous Allocation(연속 할당)

고정분할(Fixed partition) 방식

사용자 프로그램이 들어갈 메모리 영역을 미리 나눠놓는 것(융통성 없음)
internal fragmentation, external fragmentation 발생가능

가변분할(Variable partition) 방식

사용자 프로그램이 들어갈 메모리 영역을 미리 나눠놓지 않는 것
프로그램의 크기를 고려해서 할당
분할의 크기, 개수가 동적으로 변함
external fragment 발생

Hole

hole : 가용 메모리 공간
다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음
프로세스가 도착하면 수용가능한 hole을 할당
운영체제는 할당공간, 가용공간(hole)을 check하고 있음

Dynamic Storage-Allocation Problem

가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제 (n: 프로그램 크기)

Frist-fit

Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당

Best-fit

Size가 n 이상인 가장 작은 hole을 찾아서 할당
hole들의 리스트가 크기순 정렬되어있지 않으면 모든 hole의 리스트를 탐색해야 함
많은 수의 아주 작은 hole들이 생성됨

Worst-fit

가장 큰 hole에 할당
모든 리스트 탐색해야 함
상대적으로 아주 큰 hole들이 생성됨

실험적으로 First-fit, Best-fit이 속도와 공간 이용률(memory utilization) 측면에서 효과적

Compaction

external fragmentation 문제를 해결하는 방법 중 하나
사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아서 큰 block을 만드는 것
매우 비용이 많이 든다.
run time binding이 지원이 되어야 쓸 수 있음

Noncontiguous allocation(불연속 할당)

paging

프로그램의 주소공간을 동일한 크기의 page 크기로 자른다.

paging 기법을 사용하면 hole들의 크기가 일정하지 않아서 어디에 넣을지 결정하는 문제가 발생하지 않기 때문에 compaction 방법이 필요가 없다.

segmentation

프로그램의 주소공간을 같은 크기로 짜르는게 아니라 의미있는 단위로 자르는 것