OS: Memory Management

메모리에 저장되는 정보 분류

          1.  프로그램 내에 역할에 따라

                    >> Program Instructors

                    >> Constants

                    >> Variables

          2.  보호 상태에 따라

                    >> Readable and Writables: variable

                    >> Read-Only: Code, constants

                    >> Data 와 Code 공유에 중요

          3.  Binding Time ( 언제 공간이 할당 되는가?)

                    >> Static: 프로그램이 실행 되기 전

                              - 코드, 전역변수 등...

                    >> Dynamic: 프로그램 실행 도중

                              - 스텍, Dynamic storage 등...  

UNIX view of process's memory

        

Uniprogrammed System 에서의 Memory Management

 

               

          > OS 는 정해진 크기의 메모리를 가진다

          > 한번에 하나의 프로세스만 single memory segement 에서 돌아간다

                    >> 프로세스는 항상 address 0에 로드 된다

                    >> Compiler 와 linker는 물리적 주소를 generate 한다

                    >> Max address = mem size - OS size

 

 

Segments of a Process

          > 프로세스의 메모리는 logical segements로 나뉜다 -> text, data, bss, heap, stack

                    >> 몇몇은 read-only, 몇몇은 read-write

                    >> 몇몇은 컴파일링 전, 몇몇은 grow dynamically

          > 그렇다면 누가 segment에 memory를 할당하는가?

                    >> 컴파일러 & 어셈블러: 각 소스파일에서 객체 파일 생성(code & data segments) 

                    >> Linker: 모든 객체 파일을 합쳐 하나의 실행가능한 객체 파일로 만든다

                    >> Loader: 실행 가능한 객체 파일을 메모리에 load 한다(이때, 공간은 OS 가 할당해준다)

                    >> Program: 실행하면서 new 와 malloc을 사용해 동적으로 메모리를 할당, function call 도중 공간 할당 받음

 

Linking

          > Linker의 기능

                    >> 한 프로그램의 모든 파일과 라이브러리를 합친다

                    >> Regroup all segements from each file together

                    >> Regrouping에 알맞도록 주소를 조절

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

          > 객체파일(Object File)의 내용

                    >> File Header: 각 segment 마다 크기와 시작 주소

                    >> Segments for code and initialized data

                    >> Symbol table

                    >> External Symbols

                    >> Relocation Information

                    >> Debugging Information

 

          > 왜 linking이 어려운가?

                    >> Assembler가 파일을 assemble 할 때, external references를 찾을 수 있다. (symbols it doesn't know about)

                              >> 객체 코드를 생성할 때, 컴파일러는 0번지 주소를 넣는다

                              >> 컴파일러는 external symbols를 기록한다     

                              >> Linker는 external references를 해결해야 한다.

                    >> 컴파일러는 언제 프로그램이 메모리에 들어갈 지 모른다.

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

                              >> 컴파일러는 relocation information 기록, 객체 파일어 저장          

 

Loading

          > Loader는 실행가능한 완전한 프로그램을 메모리에 올린다.

                    >> Code 와 초기화된 data segments를 지정된 장소에 올린다

                    >> 아직 초기화 되지 않은 data를 위한 공간을 남겨둔다 (bss)

                    >> 시작 주소의 value를 OS 에 반환

          > Loading 에서의 대안책

                    >> Absolute Loader: 고정된 장소에 실행가능한 파일을 올린다

                    >> Relocatable Loader: 임의의 위치에 프로그램을 로드한다.

                              <어셈블러와 링커는 프로그램이 0에서 시작한다 가정>

                              <프로그램이 로드되면, loader는 모든 주소를 변경한다(by adding real start location)>

 

Running the Program (Static Mem Allocation)

          > 컴파일링, 링킹, 로딩은 static memory로 충분하다.

          > 하지만 static memory로 부족한 경우도 있다

                    >> Dynamic memory가 필요한 경우 : 프로그래머가 얼마나 많은 메모리가 필요할 지 모르는 경우

                    >> Malloc 또는 new 를 사용하여 필요한 메모리를 필요한 시점에 동적 할당할 때

                    >> 복잡한 데이터 구조: 노드에 대한 공간을 할당할 때 마다( Tree 의 경우)

                    >> 어떤 procedure이 호출될 지 OS는 모른다

                    >> OS 는 재귀적 procedure 을 다룰 수 있어야 한다

Running the Program (Dynamic Mem Allocation)

          > Dynamic Memory는 두개의 필수적 operation이 필요하다

                    >> 동적 storage 할당

                    >> 메모리가 더이상 필요 없을 경우 반납

          > Two basic methods of allocation

                    >> Stack

                              >> 할당과 반납이 어느정도 예측 가능할 때 good

                              >> 다음 상황에 사용:

                                        1. Procedure 에 parameter 전달

                                        2. Local 변수에 공간 할당할 때

                                        3. 트리 순회, 식 평가, 구문 분석

                              >> Stack Operation 사용 ( PUSH & POP )

                              >> 모든 free 한 공간을 구조화된 조직에서 함께 유지

                              >> 간단하고 효율적이나 제한적

                    >> Heap

                              >> 공간 할당과 반납이 예측 불가능할 때 사용

                              >> 다음 상황에 사용:

                                        >> 임의의 리스트 구조, 복잡한 데이터 구조를 위해

                              >> new 와 malloc 을 사용해 공간 할당, delete 와 free를 통해 공간을 반납

                              >> 시스템 메모리는 할당된 공간과 free 공간(hole)으로 나뉜다

                              >> 문제점: 많은 작은 holes 가 생기는데 이 hole 들은 너무 작아 실용적 x

                                        >> Fragmentation 이라 불린다

                                        >> Stack Allocation 에선 fragmentation 이 문제가 되지 않는다 -> top of stack 에서 add delete 하기 때문

                                        >> Solution Goal: hole들을 재사용하여 hole 의 총 수를 적고, 각 크기를 크게

                              >> 스텍이랑 비교했을때, more general, 덜 효율적, 더 어려움.

 

 

Topics in Memory Management

          > Uniprogrammed OS

                    >> Assembling, Linking, Loading

                    >> Static Memory Allocation

                    >> Dynamic Memory Allocation

                              <Stacks, Heaps>

          > Multiprogrammed OS

                    >> 위 사항들 다 포함

                    >> Static Relocation

                    >> Dynamic Relocation (Virtual vs Physical addr, Partitioning, Segmentation, Paging)

                    >> Swapping

                    >> Demand Swapping

 

Managing the Free List

          > Heap-based dynamic memory allocation techniques 는 보통 free list를 보유(모든 holes 를 기록)

          > Algorithms

                    >> Best fit

                              <1. Free block에 대한 링크드 리스트>

                              <2. 각 할당마다 모든 리스트를 검색한다>

                              <3. 필요한 크기랑 가장 비슷한 hole 선택>

                              <4. 메모리를 반납할 때, 옆에 있는 hole과 병합>

                    >> First Fit

                              <1. 전채 리스트를 스캔하다가 처음 검색된 충분한 크기의 hole 선택>

                              

Reclaming Dynamic Memory

          > 언제 메모리가 반환되는가?

                    > 프로그래머가 명령할 때

          > Reclaiming의 예상 문제점

                    > Dangling Pointers: 모든 프로세스가 사용 완료해야 한다

                    > Memory Leak: Must not "lose" memory

          > Automatic Reclamation

                    > Reference Counts

                              >> 파일 시스템이 사용

                              >> OS가 outstanding pointer의 수를 기록

                              >> 기록된 count 가 0이 되면, 메모리를 바노한

                    > Garbage Collection

                              >> 저장소는 명시적으로 해제되지 않고, 프로그래머는 포인터가 무엇을 가르키는가를 신경 x, 삭제

 

                              >> OS가 더 많은 공간이 필요한 경우, 모든 포인터 검색, 아무도 사용하지 않는 메모리 회수

 

Multiprogramming ; Goals

          > Transparency

                    >> 여러 프로세스가 메모리 내에 동시에 존재해야 한다

                    >> 프로세스는 메모리가 공유되는 것을 몰라야 한다

                    >> 각 프로세스는 어디에 있는지와 무관하게 실행되어야 한다

          > Safety

                    >> 프로세스는 서로를 corrupt 하면 안된다

                    >> Protection 메커니즘 사용

          > Efficiency

                    >> CPU 와 메모리의 능력이 저하되어서는 안된다

 

         

Static Relocation

 

          > OS 를 메모리의 최상위에 배치

          > 컴파일러와 링커는 각 프로세스가 0번지에서 시작된다 가정

          > Load 될 때, OS는 

                    >> 프로세스에 segement 를 할당

                    >> 프로세스들의 주소를 조절

MMU -> 프로세스 개수 만큼

 

Static vs Dynamic Relocation

          > Static Relocation의 문제점

                    >> Safety: 불만족

                    >> 프로세스 크기가 불변

                    >> 프로세스는 시작 후 이동 불가능

          > 대안책: Dynamic Relocaiton

                    >> 기본적인 개념은 프로세스가 실행됨과 동시에 메모리 주소 변경

                    >> MMU(memory management unit) 이 virtual 주소를 physical 주소로 변환

                    >> Physical Addr Space: OS만 봄

                    >> Virtual Addr Space: Process 가 봄

                    >> 즉 OS와 HW는 이제 두개의 다른 address를 관리해야 한다

 

Dynamic Relocation

          > 주소 공간의 두가지 개념

                    >> Physical: OS 만 보는 주소공간

                    >> Virtual(logical): 프로세스가 보는 주소공간

          > 여러 프로세스들은 physical memory를 공유하지만 각자는 각자의 가상 주소공간만 볼 수 있다