Chapter 9 (Main Memory)

Background

Program Execution

프로그램을 실행하려면 메모리를 가져와야 합니다.

user program은 실행되기 전에 몇 가지 단계를 진행됩니다.

1. Instruction fetch from memory (메모리로 부터 명령어 가져오기)

2. Instruction decode (명령어 해석)

3. Operand fetch (피연산자 가져오기)

4. Instruction execute (프로그램 실행)

5. Results may be stored back in memory (결과물 메모리에 저장)

 

Memory Access Speed

processor에 내장된 main memory와 register는 CPU가 직접 access할 수 있는 유일한 저장소 입니다.

따라서 실행되는 명령들과 data들은 CPU가 직접적으로 접근할 수 있는 main memory나 register에 있어야 합니다.

register는 CPU clock의 1 cycle (또는 그 이하) 내에 접근이 가능합니다.

대부분 CPU들은 register에 있는 명령의 decode와 간단한 operation을 이 시간 내에 처리합니다.

이와 대비되어 main memory의 접근은 많은 cycle이 소요될 수 있습니다.

이러한 경우 processor는 명령을 완료하는 데 필요한 데이터가 없기 때문에 일반적으로 지연(stall) 해야 합니다.

이를 해결하기 위해 Cache를 사용합니다.

Cache는 main memory와 CPU, register (일반적으로 cpu chip) 사이에 위치합니다.

 

Memory Protection Hardware

안전한 작동을 위해 메모리 보호는 필수적입니다. 

여러 프로그램들이 사용하는 메모리 공간이 겹치게 되면 큰 오류가 발생할 수 있습니다.

OS가 이를 방지하면 성능이 떨어지기 때문에 hardware가 이를 지원합니다.

CPU는 메모리 공간을 보호하며, register 정보는 PCB에 담겨있습니다.

이 때, register는 base와 limit으로 나뉩니다. 

base는 process가 메모리에서 사용할 수 있는 가장 작은 physicall address를 의미합니다.

limit는 사용할 수 있는 주소의 범위를 의미합니다.

 

Address Binding (주소 할당)

일반적으로 프로그램은 디스크에 binary 실행 파일로 저장되어 있습니다. 

프로그램을 실행하기 위해서는 메모리에 load해 process로 만들어야 합니다.

이 때, 디스크에서 main memory로 load 되기를 대기하는 곳이 input queue입니다.

OS는 input queue에서 process를 선택해 memory에 load합니다.

이 때 메모리 주소를 언제 결정하느냐가 크게 3단계가 있습니다.

 

1) Compile time 

만약 complie time에 process가 메모리의 어느 위치에 들어갈지 미리 알고 있다면

absolute code를 생성할 수 있습니다. 위치가 변경된다면 코드를 다시 compile 합니다.

absolute code는 어셈블리어가 정한 위치에 물리적으로 고정되어 위치되는 코드를 말합니다.

 

2) Load time

process가 메모리의 어느 위치에 들어갈지 미리 알 수 없다면 compiler는 relocatable code를 

만들어야 합니다. 이 경우, 최종 바인딩은 load의 소요 시간만큼 지연될 수 있습니다.

relocatable code는 absolute code의 반대입니다.

 

3) Execution time

process가 실행 중 메모리의 한 segment에서 다른 segment로 이동할 수 있다면 바인딩은 runtime까지

지연되어야 합니다.

 

Logical vs Physical Address Space

logical address는 CPU에서 생성된 논리적 주소를 의미합니다. virtual(가상) address라고도 합니다.

physical address는 메모리에서 생성된 물리적 주소를 의미합니다. 

compile time과 load time에서는 주소를 바인딩 할 때는 logical address 와 physical address가 같게

생성되는 반면 execution time에서는 다르게 생성됩니다. 

이 경우 logical address를 virtual address라고 합니다. 

virtual address를 physical address로 대응시키는 것은 hardware인 MMU(Memory-Management-Unit)

가 합니다.

Dynamic Relocation

base register는 relocation register라고도 불립니다.

만약 relocation register값이 14000이라면, 346번지를 access할 때, 실제로는 14346번지를 access하게 됩니다.

이에, user program은 실제적인 물리 주소(physical address)를 절대 알 수 없습니다.

단지 346번지에 대한 pointer를 생성해서 그것에 대한 저장, 연산, 비교 등의 작업을 수행할 수 있습니다.

 

Static Library vs Dynamic Link Library

static linking은 실행 파일을 만들 때 library를 같이 포함시켜 .exe 파일을 만드는 것입니다.

이를 사용해 compile 하면 linker가 프로그램이 필요로 하는 부분을 library에서 찾아 실행파일에다가

바로 복사합니다.

따라서 library가 필요없고, compile 시간이 단축되는 장점이 있습니다.

하지만 실행 파일 내에 library 코드가 저장되기 때문에 메모리가 상당히 많이 듭니다.

예를 들어 printf 함수를 사용하려면 <stdio.h> library 모두 저장해야 합니다.

이를 방지하기 위해 만든 방법인 Dynamic Linking 입니다.

 

dynamic linking은 많이 사용하는 library를 메모리에 하나만 올려 여러 프로그램들이

공유하면서 사용하는 방식입니다.

이를 DLL(Dynamic Link Library) 라고 합니다. 즉, dynamic linking 할 때 사용되는 library 파일입니다.

OS가 dll을 메모리에 한번 load해 printf같이 많이 사용하는 함수들은 shared library에 한번만 접근해 갔다오면

됩니다.

dynamic linking에서는 library를 부르는 곳마다 stub이 생기게 됩니다.

즉, library를 어떻게 찾을 것인가에 대해 알려주는 작은 code조각이라고 보면 됩니다.

 

Dynamic Linking Library를 윈도우 에서는 dll이라고 부르고 리눅스와 유닉스에너는 Shared Linbrary라고

부릅니다.

Dynamic Linking은 위에서 보듯이 메모리의 요구사항이 적은 대신 내 프로그램 영역에서 library가 저장 되어 있는

주소로 점프하기 때문에 overhead가 발생합니다.

또한 점프해야 하기 때문에 불필요한 코드도 추가됩니다. 

성능상에서는 static linking이 좋지만, 메모리 관리 차원에서는 dynamic linking이 더 좋습니다.

우리가 프로그램 업데이트 할 때 도 dynamic linking이 자주 사용됩니다.

현재 shared library만 바꿈으로써 내 프로그램 성능을 up 시킬 수 있습니다.

 

Dynamic Loading vs Dynamic Linking

dynamic loading이란 process가 시작될 때 주소공간 전체를 메모리에 load하는 것이 아니라

메모리를 좀 더 효율적으로 사용하기 위해 필요한 routine이 호출 될 때 해당 routine을 load하는 방식을

말합니다.

즉, 다 load하는 것이 아니라 필요할 때 마다 load하는 것입니다.

최근에는 virtual memory management(vmm)가 나오면서 많이 필요하지는 않습니다.

 

Swapping

메모리는 크기가 한정되어 있기 때문에 수많은 process가

메모리에 load될 수 없습니다.

예를 들어 메모리가 최대 10개의 process를 감당할 수있다면

11번째 process가 실행되려면 메모리에 load되어 있는 10개의 process중

한개를 디스크 또는 ssd로 내보내야 합니다. 이를 swap-out이라고 합니다.

하나의 process를 내보냈다면 11번째 process는 들어올 수 있습니다.

이를 swap-in이라고 합니다.

이러한 swapping 과정은 우선 순위에 따라 어떤 process를 swap-in/out 할지

결정합니다. 

swap 하는데 걸리는 시간의 대부분은 디스크 전송시간입니다.

 

swapping은 디스크에 있던 것을 다시 메모리에 다시 load해야 하니까

조금 느립니다. 

이러한 시스템에서 나타나는 context-switching 시간은 생각보다 꽤 높습니다.

하지만 부족한 메모리에 더 많은 process를 실행할 수 있다는 큰 장점이 있습니다.

 

Memory Allocation

메모리 할당에는 크게 2가지로 나뉩니다. Contiguous Allocation과 Non-contiguous Allocation입니다.

 

Contiguous Allocation (연속 메모리 할당)

1. Two-partition allocation

보통 메모리는 크게 두개의 영역으로 나뉩니다. 바로 low memory에는 OS가 차지하고, high memory에는

user process를 담습니다. 

이 때 contiguous allocation 에서는 각각의 process들이 연속적으로 메모리 공간을 차지하게 됩니다.

process가 자신의 범위를 넘지 못하도록 하는 것은 base 레지스터와 limit 레지스터의 역할 입니다.

 

2. Multiple-partition allocation (fixed size)

메모리를 몇몇 고정된 크기의 partition으로 나누는 기법입니다.

각 partition은 정확히 하나의 process만 포함할 수 있습니다.

이 때 partition들의 개수를 degree of multiprogramming이라고 합니다.

보통 잘 사용하지 않는 방식입니다.

 

3. Multiple-partition allocation (variable size)

OS는 memory의 어떤 부분이 사용되고 있고, 어떤 부분이 사용되지 않고 있는지 파악하기 위해 table을 유지합니다.

이 때 process를 메모리에 load할 때는 먼저 메모리 상에 process를 넣을 수 있는 공간을 찾는데

메모리를 분할 하는 각 단위는 block이고, 이중 사용 가능한 block을 hole 이라고 합니다.

이 때 할당하는 방법은 여러가지가 있습니다.

일반적으로 memory에는 다양한 크기의 free 공간이 여기저기 존재합니다.

이런 memory에서는 Dynamic Storage Allocation problem(동적 메모리 할당 문제)이 있을 수 있습니다.

이는 free hole의 list로 부터 크기가 n의 block을 요구하는 것을 어떻게 만족시킬 것인가에 대한 문제입니다.

이를 해결하는데에는 크게 3가지 방법이 있습니다.

1) First fit : 첫번째 hole을 할당

2) Best fit : hole 중에서 가장 작은 곳을 할당 (전체 list 탐색)

3) Worst fit : 가장 큰 곳을 할당 (전체 list 탐색)

first fit과 best fit이 worst fit 보다 속도와 공간 유용성에 유리하지만 이러한 방식들은 모두 효율이 좋지 못합니다.

50% rule : 이러한 할당방법은 N개의 block이 할당되었을 때 0.5개의 block이 fragmentation 때문에

손실 될 수 있습니다. 이건 메모리의 1/3 쓸 수 없게 된것이고, 이를 50 퍼센트 규칙이라고 부릅니다.

Fragmentation (단편화)

fragmentation은 메모리 공간을 사용하지 못하게 되는 것을 의미합니다.

external fragmentation은 예를 들어 현재 hole이 60kb, 60kb 총 두 군데가 있다고 가정해봅시다.

이 때, 새로운 70kb process가 메모리에 들어오게 되면 실제로는 120kb가 비었음에도 불구하고 

어디에도 70kb가 들어갈 수 없습니다. 이를 external fragmentation이라고 합니다.

internal fragmentation은 실제 process 공간보다 큰 메모리를 할당하게 되는 경우를 말합니다.

일반적으로 메모리가 시스템 효율을 위해  fixed size의 할당되기 때문에 생기는 현상입니다.

 

external fragmentation을 해결하기 위해 compactation(압축)을 사용합니다.

즉, 현재 사용하고 있는 메모리 공간을 한쪽으로 모두 몰아 넣는것입니다. 그렇게 되면 

분리되어진 60kb 2개의 hole이 하나의 120kb가 되어 70kb process가 들어올 수 있는 것입니다.

하지만 process 할당은 정말 자주 일어나는 일이기 때문에 compaction 처럼 overhead가 큰 작업을 

매번 할 수 없습니다. 

즉, 과거의 방법들입니다.

 

Paging

fragmentation 문제가 발생하는 contoguous allocation 방식 대신에 non-contiguous allocation

방식이 주목을 받게 됩니다.

logical address를 동일한 크기로 자르고, 

physical address도 logical address과 동일한 크기로

자릅니다.

이 때 logical memory는 page라는 fixed size의

block으로 변합니다.

page의 크기는 하드웨어에 따라 달라집니다.

크기는 2의 제곱수로 

2^12(4KB) ~ 2^30(1GB) 까지 입니다.

page table은 logical을 physical로 변환하기 위함입니다.

paging을 사용하면 하나의 process를 연속적으로 

배치할 필요가 없어 external fragmentation이 

발생하지않습니다. 

대신에 internal framentation이 발생할 수 있습니다.

 

즉, paging은 process를 일정 크기인 page로 잘라서 메모리에 적재하는 방식입니다.

 

Address Translation Scheme

위와 같이 유튜브와 메이플을 재생할 때 page 0 -> 1 -> 2 이런 순서로 실행해야 오류가 발생하지 않습니다.

하지만 physical memory에 적재된 순서로 실행하게 되면 뒤죽박죽하게 됩니다.

따라서, 해당 page를 순서대로 알 수 있게 physical memery의 위치를 찾아줄 수 있게 page table이 필요합니다.

결국, 유튜브 process도 page table이 필요하고, 메이플 process도 page table이 필요한 것입니다.

각 process마다 각각의 page table을 가지고 있다는 의미입니다.

CPU에서 나오는 모든 주소(= logical address)는 Page number(p)와 Page offset(d) 로 이루어 집니다.

Page number는 page table에 접근할 때 사용되며, page table은 main memory(physical memory)에서

각 page(frame) 의 base address를 가지고 있습니다.

Page offset은 physical address얻을 때 쓰이며 page table의 base address에 page offset을 더하면

physical address를 구할 수 있습니다.

예를 들어 logical address가 m bit를 구성할 때,  page offset이 n bit를 가진다고 가정해봅니다.

그러면 page의 크기는 2^n 이되고, page table은 2^m-n개의 entry를 가집니다.

page들은 전형적으로 4KB 또는 8KB 입니다. 그러나 몇몇은 좀더 많은 page를 제공할 수 있습니다.

위 그림에서 p는 page number이고, f는 frame number입니다. d는 page offset입니다.

logical address에서 p를 page table에서 검색하면 f가 나옵니다. (page의 크기 = frame의 크기)

따라서 offset은 똑같이 가면 됩니다.

즉, logical memory에서 p page의 d offset 위치는 f frame의 d에 적재 되어있는 것입니다.

 

Memory Loading and Free Frames

process가 실행될 시스템에 도착하면 page 단위로

표시된 process의 크기가 검사됩니다.

일반적으로 n개의 page로 되어있는 프로그램을

실행시키기 위해 우리는 m개의 free된 frame들이

필요합니다. 여기서 n = m입니다.

모든 free된 frame들을 찾아내야 합니다.

각 page들이 free된 frame에 load가 되면, 

frame number가 process page table에 

들어가게 됩니다.

만약 가상메모리를 사용한다면 n이 m보다 더 

커질 수도 있습니다. 

 

 

 

 

 

 

 

Page Table Implementation

보통 32 bit OS에서는 하나의 page의 크기가 4KB나 됩니다.

그럼 하나의 process가 가질 수 있는 page의 최대 개수는 전체 주소 크기에서 한개의 page 크기로 나누면 됩니다.

logical address는 2^32이고 한개의 page 크기는 2^12(=4KB) 라고 한다면

page의 최대 개수는 2^20 개 입니다.

따라서 page table은 최대 개수의 page 정보를 저장해줘야 하므로 한 process당 page table의 크기는

4MB(2^20( =1 MB) * int(4 byte))가 됩니다.

이를 메모리에 계속해서 보관하는 것은 매우 비효율적입니다. 

또한 게임과 같은 큰 process를 사용하지않고, 일반적인 process를 사용할 경우

page의 개수가 2^20개 있는 것에 비해 매우 조금 사용합니다.

컴퓨터의 locality특성을 살펴보면 결국, 자주 사용하는 것만 사용하고, 한번 쓰이고 안쓰이는 것은 평생 안쓰일

확률이 높습니다. 이를 바탕으로 Cache 메모리가 탄생했습니다.

마찬가지로 실제로 참조되는 page는 이중에 몇개 안된다는 원리를 활용해 page 몇개에 대한 정보를 MMU안에다가

Cache로 두고 사용을 하게 되면 MMU에서 바로 사용이 가능합니다. 속도와 메모리 효율을 높인 것입니다.

이러한 Cache를 Translation look-aside buffers(TLBs) 라고 부릅니다.

TLB는 key-value pair로 데이터를 관리하는 associative memory이며, CPU는 page table 보다 TLB를 우선적으로

참조합니다.

 

Associative Memory / TLB Structure

TLB hit는 page number가 TLB에서 발견되는 것이고, TLB miss는 발견되지 못해서 page table에서

찾아야 한다는 의미입니다.

 

Effective Access Time

page number 가 TLB에서 발견되는 비율을 hit ratio라고 하며 Effective Access Time(EAT)에 

사용됩니다.

EAT = hit ratio * Memory access time + (1 - hit ratio) * (2 * Memory access time)

 

ex) hit ratio = 80 %이고, Memory access time이 100 microsecond라면

EAT = 0.8 * 100 + 0.2 * 200 = 120

 

Memory Protection

메모리 할당이 contiguous한 경우, limit만 비교해도

메모리를 보호할 수 있었습니다.

하지만 paging은 non-contiguous하기 때문에

다른방식을 사용합니다.

page table의 각 항목에는 vaild-invalid bit가 붙어있어

그 값이 vaild이면 해당 page에 접근이 가능하고, 

invalid라면 해당 page가 logical address 공간에 

속하지 않아 접근할 수 없다는 의미입니다.

 

 

 

 

 

 

 

 

 

Shared Pages

paging의 장점중 하나는 code를 쉽게 공유할 수 있다는 것입니다. 

만약 code가 reentrant code 또는 pure code 라면 공유가 가능합니다. 

reentrant cod는 run time 동안 절대로 변하지 않는 code이며, 여러 process들이 동시에 같은 code를

수행할 수 있습니다.

이런식으로 공통 page를 공유하면 12개 load해야할 것을 6개만 load해도 됩니다.

 

Structure of Page Table

paging을 직접 적용하면 page table의 크기가 커집니다. 

page table을 효율적으로 구성하는 몇가지 방법을 알아봅니다.

 

(1) Hierarchical Page Table

logical address 공간을 여러 단계의 page table로 분할하는 기법입니다.

예시로는 2-level page table이 있습니다.

page table과 메모리 사이에 page table을 하나 더 사용함으로써 모든 page를 load해야하는

부담을 줄일 수 있습니다.

만약 32 bit 시스템에서 page의 크기가 4KB라면, page table은 

page number = 2^20, page offset = 2^12 로 나뉠 수 있습니다.

이에 커지는 page table을 메모리에 연속적으로 할당하기 보다, page table을 여ㅕ러개로 나누어

사용하는 방법이 가능합니다.

page table 자체를 다시 page화 하는 것입니다.

여기서 p1은 outer page table의 인덱스 이고, p2는 outer page table내에 page 입니다.

 

64-bit 시스템에서의 경우 2-level paging은 적절하지 않습니다.

outer page table은 2^42 또는 2^44 byte(16 TB) 구성합니다. (각 table마다 4 byte를 할당할 경우)

 

만약 3-level paging을 하는 경우 어떻게 될까?

outer page table은 2^32 또는 2^34 byte(16 GB) 구성합니다. (각 table마다 4 byte를 할당할 경우)

 

Hierarchical page table은 일반적으로 더 큰 수준의 메모리 access 수를 증가시키기 때문에 적절하지 않습니다.

 

(2) Hashed Page Table

hash table을 이용해 page table을 관리하는 기법입니다. 

address 공간이 32 bit보다 커지만 hierachical paging이 비효율 적이기 때문에 주로 이 방법을 씁니다.

virtual page number를 hashing해 page table을 참조하는데 사용합니다.

hashed page table에서는 linked list를 따라가며 page number를 비교하고, 일치하면 그에 대응하는

page frame number를 얻습니다. hash table은 검색에 O(1)이 걸려 매우 빠르지만 구현이 어렵습니다.

 

(3) Inverted Page Table

각 table의 항목은 실제 메모리 위치에 저장된 page의 가상 주소와 해당 page를 소유하는 process에대한

정보(pid)로 구성됩니다.

따라서 메모리의 frame마다 한 항목씩 할당하는데, 이렇게 되면 physical frame에 대응하는 항목만 

저장하면 되기 때문에 메모리를 훨씬 적게 사용하게 됩니다.

각 page table을 저장하는 데 필요한 메모리는 줄이지만 page 참조가 발생할 때 table을 검색하는데

필요한 시간을 늘어납니다.

hash table을 사용해 검색의 범위를 제한할 수 있습니다.

 

Segmentation

하나의 process를 여러개로 나누는 것을 말합니다.

segment는 main, function, method,지역변수, 전역변수, object 등의 논리적 단위로,

인간의 관점에서 process를 나눈것입니다.

각 segment의 base와 limit은 segment table에 저장됩니다.

logical address공간은 segment로 가변적인 크기로 분할됩니다.

segment table을 통해 주소변환이 이루어집니다.

 

logical address는 <segment number, offset> 이렇게 튜플형태로 되어있습니다.

 

Sharing

같은 segment 번호이면 서로 공유가 가능합니다.

 

Protection

같은 segment table에 있으면 valid/invalid bit를 통해 접근 범위가 정해집니다.

 

Allocation

가변적인 메모리 길이는 first/best fit 방식을 사용합니다.

동적 메모리 할당 문제가 발생합니다.

 

Segmentation with Paging