[CS] 운영체제 - 메모리 관리

메모리는 주소를 통해서 접근하는 매체이다.
크게 논리적인 주소, 물리적인 주소로 나뉜다.

 

Logical address 와 Physical Address

Logical address(논리 주소)
프로세스마다 독립적으로 가지는 주소 공간이며, 각 프로세스마다 0번지부터 시작한다.
CPU가 보는 주소는 논리적인 주소이다.

Physical address(물리 주소)
메모리에 실제 올라가는 위치를 말한다.

 

주소 바인딩

주소 바인딩이란 주소를 결정하는 것을 의미한다.

Compile time binding

• 물리적 메모리 주소가 컴파일 시 알려진다.
• 시작 위치 변경시 재컴파일한다.
• 컴파일러는 절대 코드를 생성한다.

Local time bining

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

Execution time bining

• 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있다.
• CPU가 주소를 참조할 때마다 binding을 점검한다.
•  하드웨어적인 지원이 필요하다.

 

Memory-Management Unit (MMU)

MMU란 논리적인 주소를 물리적인 주소로 매핑해주는 하드웨어이다. (주소변환을 지원해주는 하드웨어이다.)
MMU scheme: 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register의 값을 더한다.

user program: 논리적인 주소만을 다루며, 실제 physical address를 볼 수 없으며 알 필요도 없다.

 

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 작업이 불려질 때 메모리에 로드하는 것을 말한다.

메모리의 이용률이 향상된다.
가끔씩 사용되는 많은 양의 코드의 경우 유용하다.

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

 

Dynamic Linking

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

Static linking

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

Dynamic Linking

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

 

Overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올린다.

프로세스의 크기가 메모리보다 클 때 유용하다.

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

작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현한다.
프로그래밍이 매우 복잡하고 어렵다.

 

Swapping

프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것을 말한다.

backing store(=swap area)는 디스크를 말한다. (하드디스크)
swap in / swap out

• 일반적으로 중기 스케줄러에 의해 swap out 시킬 프로세스를 선정한다.
• CPU우선순위가 낮은 프로세스를 swapped out 시킨다.
• Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야한다.
• Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있다.

 

Allocation of physical memory

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

• OS 상주 영역: interrupt vector와 함께 낮은 주소의 영역을 사용한다.
• 사용자 프로세스 영역: 높은 주소의 영역을 사용한다.

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

• 연속 할당: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것이다. fixed partition allocation, variable partition allocation 방식이 있다.
• 비연속 할당: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있다. paging, segmentation, paged segmentation 방식이 있다.

 

Contiguous Allocation (연속 할당)

고정분할(fixed partition) 방식

물리적 메모리를 몇 개의 영구적 분할로 나눈다.

분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재한다.
분할당 하나의 프로그램을 적재한다.
동시에 메모리에 로드되는 프로그램의 수가 고정되고, 최대 수행 가능 프로그램 크기의 제한이 있다.
internal, external fragmentation이 발생한다.

가변분할(variable partition) 방식

프로그램의 크기를 고려해서 할당한다.

분할의 크기, 개수가 동적으로 변한다.
기술적인 관리 기법이 필요하다.
external fragmentation이 발생한다.

 

internal fragmentation(내부 조각)

프로그램 크기보다 분할의 크기가 큰 경우 생긴다.

하나의 분할내부에서 발생하는 사용되지 않는 메모리 조각이다.

특정 프로그램에 배정되었지만 사용되지 않는 공간이다.

external fragmentation(외부 조각)

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

Hole

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

Dynamic Storage-allocation problem

가변 분할 방식에서 size가 n인 요청을 만족하는 가장 적절한 hole을 찾는 문제이다. 방법은 아래 3가지가 있다.

First-fit

•  size가 n 이상인 것 중 최초로 찾아지는 hole에 할당한다.

Best-fit

• size가 n 이상인 가장 작은 hole을 찾아서 할당한다.
• hole들의 리스트가 크기순으로 정렬되지 않은 경우는 모든 hole의 리스트를 탐색해야한다.
• 많은수의 작은 hole들이 생성된다.

Worst-fit

• 가장 큰 hole에 할당한다.
• 모든 리스트를 탐색해야 한다.
• 상대적으로 큰 hole 들이 생성된다.

compaction

외부 조각으로 생기는 문제를 해결하는 한 가지 방법이다.

사용중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아서 큰 블록을 만드는 방법이다.

매우 비용이 많이 드는 방법이다.

 

Noncontiguous allocation(비연속 할당)

현대에서 쓰이는 방식이다.

paging

process의 가상 메모리를 동일한 사이즈의 page 단위로 나눈다.

가상 메모리의 내용이 page 단위로 불연속적으로 저장된다.

일부는 backing storage에, 일부는 물리 메모리에 저장된다.

Basic Method

• 물리 메모리를 동일한 크기의 frame으로 나눈다.
• logical memory를 동일 크기의 page로 나눈다.
• 모든 가용 frame들을 관리한다.
• page table을 사용해서 논리 주소를 물리 주소로 변환한다.
• external fragmentation은 발생하지 않으며, internal fragmentation은 발생할 수도 있다.

Page table

• Page table은 메인 메모리에 상주한다.
• page-table base register (PTBR)가 page table을 가리킨다.
• page-table length register (PTLR)가 테이블 크기를 보관한다.
• 모든 메모리 접근 연산에는 2번의 memory access가 필요하다. (page table에 접근 1번, 실제 data에 접근 1번)
• 속도향상을 위해서 associative register 또는 translation look-aside buffer (TLB) 라고 불리는 고속의 lookup hardware cache를 사용한다.

 

Associative register(TLB)

parallel search가 가능하다. TLB에는 page table 중 일부만 존재한다.
Address translation

• page table 중 일부가 associative register에 보관되어 있다.
• CPU가 페이지 번호를 주면 TLB에서 parallel search를 한 후 어딘가에 페이지 번호가 있으면 주소 변환이 바로 이루어지며, 없으면 TLB miss가 일어나고 page table을 통해서 주소 변환을 한다.

2단계 Page table

기존 페이지 테이블은 1단계로 존재했지만 2단계 페이지 테이블은 외부 페이지 테이블과 내부 테이블을 두고 사용한다.
현대의 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원한다.
32 bit 주소를 사용시: 2^32 (4G)의 주소공간을 사용한다.

• page size가 4KB일때 100만개이상의 page table entry가 필요하다.
• 각 page entry가 4B일때 프로세스당 4M의 page table이 필요하다.
• 대부분의 프로그램은 4G의 주소 공간 중 일부분만 사용하기 때문에 page table의 공간이 낭비된다.
• 이러한 이유 떄문에 2단계 page table을 사용한다.

page table 자체를 page로 구성한다.

사용되지 않는 주소에 대한 외부 페이지 테이블의 엔트리 값은 null이다. (해당 값에 대한 내부 테이블이 없기 때문이다.)

Multilevel paging, performance

주소 공간이 더 커지면 다단계 페이지 테이블이 필요하다.

각 단계의 페이지 테이블이 메모리에 존재하기 때문에 논리적 주소의 물리적 주소 변환에 더 많은 메모리 접근이 필요하다.

TLB를 통해서 메모리 접근 시간을 줄일 수 있다.

Memory protection

page table의 각 entry 마다 아래의 bit를 준다.

Protection bit: page에 대한 접근 권한 (read/write/read-only)
Valid-invalid bit

• valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻한다. (접근 허용)
• invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻한다. (접근 거부)

Inverted Page table

모든 프로세스 별로 논리 주소에 대응하는 모든 page에 대해서 page table entry가 존재하고, 대응하는 page가 메모리에 있던지 아니던지 page table에는 entry로 존재하기 때문에 page table이 매우 크다.

Inverted page table

• page frame 하나당 page table에 하나의 entry를 둔 것이다. (system-wide)
• 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용을 표시한다.(프로세스의 id, 프로세스의 논리적 주소)
• 테이블 전체를 탐색해야 한다는 단점이 있다.
• Associative register를 사용해서 오버헤드를 줄일 수 있다.

Shared page

같은 프로그램을 여러개 킬 때 코드는 같은 코드를 사용한다. 메모리에 하나만 올려서 가리킨다.
Shared code

• re-entrant code(pure code 라고도 불린다.)
• read-only로 해서 프로세스 간의 하나의 code만 메모리에 올린다.
• shared code는 모든 프로세스의 논리 주소 공간에서 동일한 위치에 있어야 한다.

Private code and data

• 각 프로세스들은 독자적으로 메모리에 올린다.
• private data는 논리 주소 공간의 아무 곳에 와도 무방하다.

Segmentation

프로그램은 의미 단위인 여러개의 segment로 구성된다. (크기가 균일하지 않다.)

• 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의한다.
• 크게는 프로그램 전체를 하나의 세그먼트로 정의가 가능하다.
• 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의된다.

논리적 주소는 segment-number와 offset으로 구성된다.

세그먼트에서 주소 변환은 segment table로 이루어진다.

segment table

각 테이블은 base와 limit을 가지고 있다.

Segment-table base register (STBR): 물리적 메모리에서의 세그먼트 테이블의 시작위치를 나타낸다.
Segment-table length register (STBR): 프로그램이 사용하는 세그먼트의 수를 나타낸다.
각 세그먼트 별로 protection bit가 있다.
세그먼트는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 효과적이다.
세그먼트의 길이가 동일하지 않기 때문에 가변분할 방식에서와 동일한 문제점들이 발생한다. (external fragmentation)

Paged segmentation (paging과 segment를 혼합한 기법)

세그먼트 하나가 여러 페이지로 구성된다.

segment-table entry가 세그먼트의 base의 주소를 가지고 있는것이 아니라 segment를 구성하는 page table의 base 주소를 가지고 있다.

 

이 글에서 사용되는 기법들 중 OS가 하는 역할은 하나도 없다. 전부 하드웨어(MMU)가 처리한다.
그 이유는 주소변환을 할 때마다 OS가 개입을 한다면 CPU가 프로세스로부터 OS로 넘어가고 다시 프로세스로 넘어와야 하는데,
그렇게 되면 오버헤드가 커지기 때문이다. 그렇기 때문에 주소변환은 하드웨어 단에서 처리해야한다.