Lecture 22.~23. Memory Part 1.

Memory Management in a Uniprogrammed System

메모리에 저장되어 있는 프로그램의 위치를 이동시키면 반드시 주소값을 변경해야 합니다.

OS는 메모리의 고정된 segment를 가집니다. 한 프로세스는 하나의 메모리 세그먼트에서 한 번만 실행될 수 있습니다. 프로세스는 항상 주소 0번지에 load됩니다. 컴파일러와 링커가 물리적인 주소를 생성합니다. 최대 주소값은 전체 메모리 사이즈 - OS 사이즈 입니다.

Bindin time

1. Static : 프로그램이 실행되기 전에 바인딩 됩니다. 프로그램 코드와 static, global 변수들을 static 입니다. 프로그램의 size가 커지고 compile 시간이 길어지지만 runtime의 시간을 줄일 수 있습니다.
2. Dynamic : 프로그램이 실행될 때 바인딩 됩니다. Procedure stack과 동적 할당 공간 등은 Dynamic 입니다. 런타임에 동적으로 include 되는 라이브러리를 DLL(Dynamic Linking Library)라고 하며, 이는 여러 개 중 일부를 include해도 되지 않은 경우를 만들어줍니다. 코드의 흐름에 따라서 특정한 경우에 특정 라이브러리를 포함하지 않을 수 있습니다.

지금은 단 하나의 프로그램만 존재하는 것을 가정합니다. 그림에서 가장 위 부분이 MAX address이고 가장 아래 부분이 0번지 주소입니다. 이전 포스팅에서 언급한 적이 있는 Text, Data, BSS, Stack이 여기서 말하는 Segment입니다. 그림을 기억하면되는데, 위에서부터 S, Heap, B, D,T입니다.

//TODO

Segments of a Process

프로세스 메모리는 T,D,B,Heap,S의 5가지 논리적인 세그먼트로 나눠집니다. 몇몇 부분은 읽기만 가능하고, 나머지는 읽고 쓸 수 있습니다. 또한 일부분은 컴파일 타임에서 알 수 있고, 런타임에서 알 수 있는 부분도 있습니다.

Who assigns memory to segments?

1. Compiler와 aseembler가 각각의 소스파일로부터 object file을 생성합니다.
2. Linker는 모든 오브젝트 파일을 하나의 Executable object file 로 묶습니다. 이 실행파일은 완벽하게 독립적입니다.
3. Loader는(part of OS) Excutable object file을 Memory에 있는 OS가 지정해주는 주소에 Load합니다.
4. 이 Executable object file을 실행하면 프로그램을 불리는 것이고, 이는 동적 메모리 할당을 사용하고, function call을 하면서 stack 영역을 사용합니다.

Linking

링커가 수행하는 역할을 링킹이라고 합니다. 프로그램의 모든 파일과 라이브러리를 결합합니다. 그리고 각 파일에 있는 세그먼트들을 통합니다. 각각의 파일에 있는 data segment들을 모아서 큰 하나의 data segment를 만듭니다. 이렇게 regroup한 세그먼트에 주소를 할당합니다. 이런 과정을 거치면 Executable file이 되는 것입니다.

object 파일에는 다음과 같은 요소들이 들어있습니다.

ELF : Executable Linking Format

1. File header : 각 세그먼트의 시작 주소와 사이즈가 들어있습니다. 이를 통해서 어디부터 어디까지 어떤 세그먼트인지 알 수 있습니다.
2. 코드와 초기화된 데이터가 들어있는 segment가 있습니다.
3. Symbol table
4. Relocation information (프로그램을 실행할 때마다 저장되는 주소가 다르기 때문에 이를 MMU에 저장합니다.)
5. Debugging information

Linking이 어려운 이유

어셈블러가 파일들을 모을 때, 어셈블러는 printf와 scanf가 무엇인지 모르기 때문에 external references를 찾아야 합니다. 컴파일러는 오즈젝트 코드를 만들 때 그저 0번지 주소에 놓을 뿐입니다. 컴파일러는 external synbols와 그들의 위치를 cross-reference-list에 기록합니다. 그리고 이 list를 오브젝트 파일에 저장합니다. 링커는 반드시 이 파일들을 한 번에 link할 때에 이 list를 resolve해야합니다.

컴파일러는 프로그램이 메모리에서 어느 곳에 위치할지 모릅니다. 하나의 프로그램만 존재하는 uniprogramming의 경우 항상 0번지 주소에 프로그램이 load되겠지만, multiprogramming 환경에서는 어느 주소에 프로그램이 load될지 알 수 없습니다. 그래서 컴파일러는 그저 프로그램이 0번째 주소에서 실행된다고 가정합니다. 컴파일러는 relocation information을 ojbect file안에 아지고 있습니다. relocation informatino은 나중에 메모리에서 어느 곳에 위치할지를 알려주는 역할을 합니다.

MMU

Relocatino information은 MMU를 보면 알 수 있습니다. MMU는 Memory와 별개인 독립적인 H/W입니다. MMU는 process당 1개가 있으면 logical address와 physical address를 Mapping해주는 역할을 합니다. 이 Table은 엄청 길어서 context switching의 가장 비싼 연산 중 하나입니다.

Loading

loader는 완전한 프로그램을 메모리에 load합니다. 이 때 프로그램이 실행될 수 있는 위치에 로드합니다. 메모리에서 프로그램이 실행될 수 있는 특정한 위치에 코드와 데이터 segment를 load하고, BSS는 초기화가 이루어지지 않은 영역이므로 이를 위한 공간도 마련해 놓습니다. 로더의 return은 OS가 시작하는 주소값을 반환합니다. loader는 OS의 한 부분이기 때문입니다.

Absolute loader는 실행파일을 고정된 위치에 load합니다. Relocatable loader는 OS가 알려주는 실행이 가능한 위치에 프로그램을 Load 합니다. 어셈블러와 링커는 프로그램이 0번지에서 실행된다고 가정합니다. 프로그램이 로드되면 이러한 주소에 실제로 프로그램이 로드가 된 주소를 더합니다.

지역변수는 함수에 따라서 부를 수 있는 데이터에 대한 메모리만 갖고 있게 하는 것을 의미합니다.

동적 메모리 할당은 두 가지 기초적인 operation을 요구합니다. 먼저 동적으로 저장 공간을 할당하고, 이를 해제하는 Free 연산이 필요합니다.

Stack VS. Heap

Stack

동적할당과 해제가 예측 가능한 상황인 경우 사용하는 것이 좋습니다. procedures에 parameter를 전달하는 경우, procedure 안에서 동적으로 지역 변수를 할당하는 경우 등이 전형적으로 stack이 사용되는 경우입니다. Stack을 사용하기 위해서는 push와 pop을 사용합니다.

Heap

동적할당과 해제가 예측 불가능한 상황에서 사용하는 것이 좋습니다. 예를 들어서 임의의 list 자료구조와 복잡한 데이터 집합에 사용합니다. 이 경우 new와 malloc을 사용하고 delete와 free를 사용해서 공간을 release 합니다. Stack은 항상 top에서 push와 pop을 진행하기 때문에 조각조각 너무 작아서 유용하게 사용하기는 힘든 fragmentaion들이 생기지 않습니다. 하지만 heap은 이런 fragmentaion들이 생깁니다.

비교

Stack이 더쉽고 효과적이지만 top만 사용해야하므로 제한적입니다. Heap은 일반적으로 사용할 수 있고, 덜 효과적인 방법(fragmentation)이며, implementation하기가 더 어렵습니다.

Free lisg?

Heap 기반의 동적 메모리 할당 기술은 전형적으로 free list를 유지합니다. 이는 메모리에서 어디에 빈 공간이 있는지 기록하는 역할을 합니다.

• Best Fit

빈 block의 Linked list를 유지합니다. 매번 할당을 해야할 때마다 전체 리스트를 확인합니다. 그리고 요청과 가장 비슷한 크기의 사이즈를 할당해줍니다.

• First Fit

요청이 들어오면 free list를 읽어서 가장 먼저 만나는 할당 가능한 영역을 바로 줍니다. 요청된 크기가 3이고 처음 발견한 빈 공간의 크기가 10이어도 이를 줍니다.

결론적으로는 두 가지 방법 모두 Fragmentation이 발생합니다. 이는 조각 모음을 진행한 후 프로세스에게 돌려줘야 합니다.

Reclaimimg Dynamic Memory : 반납

동적할당된 메모리를 반납할 때에는 두 가지 문제점이 있습니다.

1. Dangling pointers : 할당된 이후에 이를 지칭할 포인터가 없는 경우를 말합니다. 특정 메모리를 사용할 다른 프로세스가 없음을 보장해야지 문제가 발생하지 않습니다.
2. Memory leak : 적절한 때에 Free를 해주어야지 프로세스 입장에서 메모리를 잃는 경우를 방지할 수 있습니다.

Implementin automaic reclaimation : Reference counts

파일시스템에서 사용되는 방법입니다. OS는 각 메모리 아이템에 대해서 포인터의 갯수를 기록합니다. 이 갯수가 0이 되었을 때 메모리를 Free합니다.

Implementin automaic reclaimation : Garbage collection

저장공간은 명시적으로 free 되지 않습니다. 프로그래머는 그저 특정 메모리 아이템을 가리키는 포인터를 삭제하고 걱정하지 않습니다. 나중에 OS가 더 많은 저장 공간을 필요로 할 때에, OS는 재귀적으로 모든 active pointer를 찾고 더이상 사용되지 않는 공간을 Free 합니다. Garbage collection 프로그램을 짜는 것이 어렵고 비싼 연산이라는 단점이 있습니다.

MMU 추가 설명 : Memory Management Unit

H/W를 보면 크게 세 가지가 있습니다.

CPU —- MMU —- Memory

1. CPU에서 MMU에 찾고 있는 process의 virtual address를 보냅니다.
2. MMU는 M에게 Physical address를 보냅니다.
3. 해당하는 process로 Context Switching을 진행합니다.
4. 이에 맞는 physical Address를 MMU에 저장합니다.
5. MMU가 CPU에게 다시 virtual 주소를 return 합니다.

프로세스가 실행될 때마다 load되는 주소가 다르기 때문에 이 프로그램이 어떤 Physical address를 갖게 되었는지와 MMU Table을 보고 CPU가 해당 프로세스를 볼 때 어떤 virtual address로 보는지 파악할 수 있습니다.

중요한 것은 Process Context SWitching이 일어날 때 MMU가 갱신되고, Thread Context Switing의 겨우 MMU가 갱신되지 않는다는 점입니다.

Static Relocation

멀티 프로그래밍의 예제입니다. 전체 메모리에 가장 주소값이 큰 부분은 OS가 저장되어 있습니다. 그리고 각각의 프로그램은 0번지부터 실행된다고 여겨집니다. 하지만 실제로 저장되어 있는 부분은 0번지가 아닐 수도 있습니다. Static Relocation의 경우 Swip 되어다가 다시 돌아올 때는, Swip 되기 전의 위치에 그대로 들어와야 합니다. 따라서 크기가 작은 Machine에 이 방법을 사용합니다.

Dynamic Relocation

프로세스가 실행되면서 Runtime에 주소값이 바뀔 수 있는 것을 의미합니다. Swip-in/out 되었을 때 저장되는 주소가 바뀔 수 있습니다. CPU는 runtime에 Virtual 메모리만 보고, MMU를 업데이트해서 MMU가 적절히 맵핑된 결과를 알려주기 때문에 CPU는 헷갈려하지 않습니다. CPU는 항상 고정된 자리에서 Process를 찾습니다.

주소 공간을 보는 두 가지 관점이 있습니다.

1. physical address space : OS가 보는 주소 체계입니다. machine에 부착된 저장공간만큼의 크기를 가집니다.
2. virtual address space : process가 보는 주소 체계입니다. 명령어 집합 아키텍쳐가 허용하는 공간만 볼 수 있습니다.

Implementing Dynamic Relocation

//TODO 그림

MMU로 virtual address가 들어오고 physical address로 mapping이 되서 나갑니다. Base register는 virtual address의 가장 작은 주소를 갖습니다. limit register는 virtual address의 가장 큰 주소를 갖습니다. virtual 주소에 base register를 더하면 physical address가 됩니다.

• physical address = virtual address + base register
• if(virtual address > limit register) { ASSERT ERROR }

각각의 Segment는 base registe와 limit register를 가지고 있습니다. 유저 프로그램(processes)는 각자 자신의 virtual memory의 주소를 바라봅니다.

유저 프로그램이 시스템 콜을 하는 경우, CPU는 atomic하게 커널모드로 들어가고 trap handler(S/W interrupt)를 trap합니다. OS trap handler는 physical 메모리에 접근을 하고 시스템 콜에 필요한 작업을 수행합니다. CPU는 Atomic하게 Relocation을 켜고, user mode로 돌아간 후 user program에 return 합니다.???