OS(0516) - Memory Management

* a.c와 b.c를 컴파일하면 -> a.o, b.o가 생성됨 -> linker가 이들을 묶어 hello.exe 로 만들어줌

> linker는 각각의 external 변수가 잘 선언되어 있는지 확인

> 각 파일에 있는 symbol table을 linker가 합쳐줌

 

 

#Classifying Information Stored in Memory

- 프로그램 내 역할에 따른 분류:

1. 프로그램 명령어(변경 불가) - text area, 공유됨

2. 상수: pi, maxnum, printf/scanf에서 사용되는 문자열 등(변경 불가)

3. 변수: 로컬 변수(stack), 전역 변수, 함수 매개변수(stack), 동적 할당된 저장소(malloc or new)(heap) -> 변경 가능, 초기화 돼있을수도 아닐수도 - data area

- 보호 상태에 따른 분류:

1. 읽기 및 쓰기 가능: 변수

2. 읽기 전용: 코드, 상수

    > 데이터 및 코드 공유에 중요

- 주소 vs  데이터:

    > 프로그램을 이동시키는 경우 주소를 수정해야 함(재배치, 가비지 콜렉션 - 더이상 쓰지 않는 자원 반납)

        > swap in, swap out 시에 주소 수정

 

#Memory management in a Uniprogrammed System

- OS는 고정된 메모리 세그먼트(일반적으로 가장 높은 메모리)를 할당받음

- 한 번에하나의 프로세스가 단일 메모리 세그먼트에서 실행됨

    > ★프로세스는 항상 주소 0 에서 로드됨 -> 모든 컴파일러는 이것을 가정하고 컴파일

    > 컴파일러와 링커는 물리적 주소를 생성함

    > 최대 주소 = 메모리 크기 - OS 크기 

 

#메모리에 저정된 정보 분류

- Binding time(공간이 언제 할당되나?)

    > Static: 프로그램이 실행되기 전에 할당(덩치가 큼) -> Compile시 linking

        > 프로그램 코드, 정적 전역 변수(초기화 및 초기화되지 않은 변수)

    > Dynamic: 프로그램 실행 중에 할당됨(덩치 작음) -> Runtime에 linking

        > Static보다 훨씬 덩치 작음(ex: if - else문에서 static은 둘다 할당하지만, dynamic은 하나만 할당)

        > 프로시저 스택, 동적 저장소(malloc or new에 의해 할당된 공간)

- 프로세스 메모리의 UNIX view(uniprogramming only for now):

#Segments of a Process

- 프로세스의 메모리는 논리적 세그먼트(text, data, bss, heap, stack)로 분할됨

    > 일부는 읽기 전용, 일부는 읽기 쓰기 가능

    > 일부는 컴파일 시간에 알려지고, 다른 일부는 프로그램 실행 중에 동적으로 성장

- 메모리 세그먼트에 대한 할당은 다음과 같이 이뤄짐:

    > 컴파일러와 어셈블러는 각 소스 파일로부터 코드와 데이터 세그먼트를 포함하는 객체 파일을 생성

    > 링커는 프로그램의 모든 객체 파일을 하나의 완전하고 독립적인 실행 가능한 객체 파일로 결합

    > 로더(OS의 일부)는 실행 가능한 객체 파일을 운영체제가 결정한 위치에 메모리로 로드

    > 프로그램은 실행 중에 new와 malloc을 사용하여 동적으로 메모리를 할당, 함수 호출 시 스택에서 공간을 얻음

 

#Linking

- Functions of a linker:

    > 프로그램의 모든 파일과 라이브러리 결합

    > 각 파일의 세그먼트를 함께 재그룹화(하나의 큰 데이터 세그먼트 등)

    > 재그룹화에 따라 주소를 조정합니다.

    > 결과물은 실행 가능한 프로그램임

- 객체 파일의 내용:

    > 파일 헤더 - 각 세그먼트의 크기와 시작 주소(메모리에서)

    > 코드와 초기화된 데이터를 위한 세그먼트

    > 심볼 테이블(심볼, 주소)
    > 외부 심볼(심볼, 위치)

    > 재배치 정보(심볼, 위치)

    > 디버깅 정보

    > 유닉스 디테일은 "man a.out"

 

#링킹은 왜 어려운가

- 어셈블러가 파일 어셈블시 외부참조(printf, scanf와 같은 심볼) 발견 가능

    > 컴파일러는 객체 코드 생성시 주소 0을 넣음

    > 컴파일러는 외부 심볼가 그 위치(객체 파일에서)를 교차 참조 목록에 기록, 그 목록을 객체 파일에 저장

    > 링커는 파일을 연결하는 과정에서 이러한 외부 참조를 해결해야 함

- 컴파일러는 프로그램이 메모리에서 어디에 위치할지 모름(Multi programming의 경우는 항상 0으로 가정)

    > 컴파일러는 프로그램이 0에서 시작한다고 가정

    > 컴파일러는 재배치 정보(나중에 조정될 주소의 위치)를 기록, 객체 파일에 저장

 

* 링킹이 끝나면 -> .o파일들이 모두 합쳐져 .exe파일이 만들어진 상태

 

#Loading

- 로더는 완성된 프로그램을 실행할 수 있는 메모리에 로드함

    > 코드와 초기화된 데이터 세그먼트를 지정된 위치의 메모리에 로드

    > 초기화되지 않은 데이터(bss)를 위한 공간을 남긴

    > 시작 주소의 값을 OS에 반환

- 로딩에 대한 대안(다음 2개의 강의에서 다룰 내용):
    > Absolute loader - 고정된 위치에 실행 가능한 파일 로드

    > Relocatable loader - OS에서 지정한 임의의 메모리 위치에 프로그램을 로드함(멀티 프로그래밍에 필요, 단일에는 필요 없음)

        > 어셈블러(컴파일러의 마지막 단계)와 링커는 프로그램이 위치 0에서 시작한다고 가정

        > 프로그램이 로드될 때, 로더는 모든 주소를 실제 시작 위치에 더하여 주소를 수정

 

* .c -> .o -> libc.a ->빈자리를 찾고 -> 첫 주소를 OS에 가르쳐주고 -> CPU에 가르쳐주면 그 빈자리부터 시

 

#Running the Program - Static Memory Allocation

- 컴파일, 링크, 로드는 정적 메모리에 대해서는 충분

    > 코드, 상수, 정적 변수 등

- 그러나 다른 경우에는 정적 할당만으로는 충분하지 않음

    > 동적 저장소가 필요한 경우 - 프로그램이 실행될 때 필요한 메모리의 양을 프로그래머가 알 수 없을 수 있음

    > 필요할 때 필요한 만큼의 메모리를 얻기 위해 malloc또는 new를 사용

    > 복잡한 데이터 구조(ex: 트리)의 경우, 노드에 대한 공간을 필요한 시점에 할당

    > OS는 미리 어떤 프로시저가 호출될 지 모름(미리 모든 프로시저의 모든 변수에 공간을 할당하는 것은 낭비)

    > OS는 재귀 프로시저를 처리할 수 있어야 함

 

#Running the Program - Dynamic Memory Allocation

- 동적 메모리는 두가지 기본 작음을 필요로:

1. 동적 저장소 할당

2. 더이상 필요하지 않을 때 메모리 해제 -> 스택과 힙에 대한 방법은 다양함

- 할당의 두 가지 기본적인 방법:

1. 스택(계층적)

    > 할당과 해제가 어느 정도예측 가능할 때 유용

    > 일반적으로 다음과 같이 사용됨:

        > 프로시저에 매개변수 전달

        > 프로시저 내에서 지역 변수에 공간 할당

        > 트리 순회, 식 평가, 파싱(parsing) 등에 사용됨

    > 스택 연산인 push, pop 사용

    > 모든 빈 공간을 구조화된 조직으로 함께 유지

    > 간단하고 효율적이지만 제한적

2. 힙

    > 할당과 해제가 예측할 수 없을 때 사용됨

    > 일반적으로 다음과 같이 사용:

        > 임의의 리스트 구조, 복잡한 데이터 구성 등에 사용됨

    > 공간을 할당하기 위해 new 또는 malloc을 사용하고, 공간을 해제흐기 위해 delete 또는 free 사용

    > 시스템 메모리는 할당된 영역과 빈 영역(구멍)으로 구성

    > 문제: 결국 많은 작은 구멍들이 생기는데, 각각이 유용한 정도보다는 작아서 사용하기 힘듦

        > 이를 fragmentation이라고 하며, 메모리 낭비를 초래

        > 스택 할당의 경우 fragmentation이 문제가 되지 않으므로 항상 스택의 위에서 추가/삭제 진행함

        > 해결법: 구멍의 공간을 재사용하여 구멍의 수를 작게 유지하고 크기를 크게 유지하는 방법을 목표로

    > 스택과 비교할 때 : 더 일반적이지만, 효율성이 낮고 구현이 어려움

 

#Topics in Memory Management

- Uniprogrammed operating systems

    > 어셈블링, 링킹, 로딩

    > static 메모리 할당

    > dynamic 메모리 할당

        > 스택, 힙

        > free list 관리, 메모리  reclamation

- Multiprogrammed operating system

    > 대부분의 topic을 포함

    > static relocation

    > dynamic relocation

        > Virtual vs physical 주소

        > Partitionoing(and compaction)

        > Segmentation

        > Paging

    > Swapping

    > Demand paging

 

#Managing the Free List

- 힙 기반의 동적 메모리 할당 기법은 일반적으로 free list를 유지, 모든 빈 공간을 추적, 관리

- free list manage algorithm:

1. Best fit

    > free block의 연결 리스트 유지

    > 할당마다 전체 목록을 검색하여 요청 크기와 가장 가까운 크기를 가진 빈 공간을 선택

    > 사용되지 않는 공간은 새로운 (더 작은) 빈공간이 됨

    > 메모리 해제 시, 인접한 빈 공간을 결합

2. First fit

    > 목록을 처음부터 검색하여 요청 크기에 충분한 첫 번째 빈 공간을 선택

    > 그렇지 않은 경우에는 Best fit과 동일한 방식으로 처리

 

#Reclaiming Dynamic Memory

- 메모리는 언제 해제되나?

    > 프로그래머가 명령시

    > 자동으로 하는 방법은?

        > 해당 아이템이 공유 아이템이라면 어려움

- reclamation의 잠재적 문제

    > Dangling pointers(무효 포인터) - 해당 항목을 사용하는 모든 부분이 완료되었는지 확인해야 함

    > 메모리 누수 - 해당 메모리를 적절한 시기에 해제하지 않아 메모리를 "lost"하지 않아야함

- 자동 회수 구현:

    > reference counts(참조 카운트)

        > 파일 시스템에서 사용

        > 운영체제는 각 메모리 항목에 대한 활성 포인터 수를 추적

        > 카운트가 0이되면 메모리를 해제

    > Garbage collection

        > LISP에서 사용됨

        > 저장 공간은 명시적으로 해제되지 않음. 프로그래머는 단순히 포인터를 삭제하고 해당 포인터가 가리키는 것 무시

        > 운영 체제가 더 많은 저장 공간이 필요할 떄, 모든 활성 포인터를 재귀적으로 검색, 아무도 사용하지 않는 메모리 회수

        > 응용 프로그램의 life를 쉽게 만들어줌, 그러나 구현 어려움

        > 종종 비용이 많이 들며, CPU time의 20% 사용 가능

        > 메모리 할당과 자동 메모리 해제에 50%시간 사용 가능

 

#Multiprogramming - Goals in Sharing the Memory Space

- 투명성:

    > 여러개의 프로세스가 메모리에서 공존해야 함

    > 어떤 프로세스라도 메모리가 공유된다는 것을 인식해서는 안됨

    > 각 프로세스는 메모리 내의 위치에 관계없이 실행되어야 함

- 안전성:

    > 프로세스는 서로 또는 운영체제를 손상시킬 수 없어야 함

    > 안전을 보장하기 위해 보호 메커니즘 사용

- 효율성:

    > CPU와 메모리의 성능이 공유로 인해 크게 저하되지 않아야 함

 

#Static Relocation

- 가장 높은 주소에 OS

- 컴파일러와 링커는 0에서 시작한다고 가정

- 로드 타임에서 OS는:

    > 프로세스를 완벽히 맞는 memory segment에 할당

    > 프로세스의 주소를 조절

 

#Static vs Dynamic Relocation

- 정적의 문제점:

1. 안전성 - 불만족: 하나의 프로세스가 다른 프로세스의 메모리에 접근하거나 손상 가능, 심지어 OS의 메모리까지 손상 가능

2. 프로세스 크기 변경 불가

3. 실행 시작 후에는 프로세스를 이동할 수 없음

4. MS-DOS, WINdows, Mac OS에서 사용됨

- 대안: 동적 재배치

    > 기본 아이디어는 프로세스가 실행되는 동안 각 메모리 주소를 동적으로 변경

    > 이러한 변환은 하드웨어에 의해 수향, CPU와 메모리 사이에는 메모리 관리 유닛(MMU) 또는 translation unit이 있어 가상 주소를 물리 주소로 변환

    > 이 변환은 프로세스가 수행하는 모든 메모리 참조에 대해 발생

*MMU: table(표)(2*n) -> 좌측도 주소(0~), 우측도 주소(실제 로딩되는 주소의 첫번째~)

*CPU는 0번지에만 접근하면 편하게 모든 주소에 접근 가능

*Loader가 Best fit에 load하고 MMU에 작성

*MMU = 프로세스 개수만큼 존재

 

#Dynamic Relocaiton

- 물리적 주소 공간: OS만 볼 수 있음, 기기의 물리적 메모리 만큼 존재

- 가상 주소 공간: 프로세스가 봄, 명령어 집합 아키텍처가 허용하는 한 존재

    > 현재는 물리적보다 훨씬 작다고 가정

- 여러 프로세스는 물리적 메모리를 공유하지만, 각각은 자신만의 가상 주소 공간만 볼 수 있음

- 이제 운영 체제와 하드웨어는 두 가지 다른 주소를 관리해야함

    > 가상 주소: 프로세스가 보는 주소

    > 물리 주소: 물리적 메모리의 주소(OS가 보는 주소)