지밍이 블로그

# Heap management

- Heap Structure

- allocation : malloc, new, free, delete 

- Free List : Heap의 사용가능한 공간을 linked list로 구성

- Free함수의 역할 : Free List로 반환되는 공간이 기존 가용한 공간과 병합이 가능한 경우는 하나의 큰 공간으로 병합하고 아닌 경우에는 새로운 포인터로 연결

- Fragmentation : allocation과 reverse의 반복과정에서 생기는 작은 메모리 hole

- fragmentation이 많이 발생하면 메모리할당을 제대로 수행할 수 없음

- Buddy Allocator, Slap Allocator

: http://jiming.tistory.com/131

- Buddy Allocator의 Free 

: 인접한 buddy 들이 가용 상태인 경우 이를 병합함으로써 쉽게 큰 크기의 가용한 메모리 공간을 확보할 수 있음

# Free List

- Lisked List, Bitmap

 Free List가 주어지면 런타임에 어떤프로세스가 메모리 요청을 했을 때 메모리 할당에 대한 정책

- 메모리 fragments를 줄이기 위해 메모리 할당시에 적용되는 정책

: Best-fit, First-fit, Worst-fit

- Best-fit으로 allocation하는 것이 항상 좋은 결과를 가져오지 못하는 이유

: 시간이 지남에 따라 First-fit, Worst-fit에 비해 작은 크기의 hole들이 생성되기 때문에 Fragmentation 문제가 더 심각해 질 수 있음

- Memory Pool

; uni 사이즈로 메모리 요청을 수행하도록 함

: 여러 사이즈를 메모리 노드들을 동일한 사이즈끼리 묶어서 관리(다양한 사이즈를 지원할 수 있음)

: but, 사이즈 별로 불균현의 문제를 가지고 있음

# Static  vs  Dynamic

- Static : execution 전, pre-runtime, offline, static analisys, 

- Dynamic : execution 후, runtime, online

- Static Allocation : 프로그램이 수행되기 전에 미리 메모리를 할당하는 것 (Code(text) Segment, Data Segment)

변수의 lifecycle이 프로그램의 시작과 끝에 일치하는 것

- Dynamic Allocation : (Stack Segment, Heap Segment)

*Activation Records(Stack Frames/Acivation Frames) 

: 프로시저가 수행되기 위해 필요한 정보들을 저장하고 관리하기 위해 stack에 저장되는 데이터 구조

: 라이프사이클은 해당되는 함수가 시작되고 수행이 끝날 때까지임

: 함수 호출과 리턴은 Stack의 push, pop operation과 정확이 매칭됨

# Memory Manager

- Dynamic Storage Allocation, Heap

- Demanding Paging

# Linker and Loader

* .c (source file) -> Compile -> .o (object file)-> linking -> executable file -> memory loading -> executing

* object file 

: instructions, datas, address 정보, symbol table(프로그램에서 사용하는 symbol들에 대한 정보를 저장하는 자료구조), 링커가 프로그램 링킹을 위해 사용하는 정보(relocation table)

* Compiler : 소스파일을 오브젝트 파일로 변환

* Linker : 여러개의 오브젝트 파일을 하나의 실행가능한 파일로 변환

* Loader : OS의 한 부분으로 (fork, exec) 메모리에 프로그램을 로딩

# Section

: 오브젝트 파일을 구성하는 유닛. 어떤 데이터를 묶어둔 단위. text(code, instructions), datas, symbol table ...

- type이 각 section마다 다를 수 있음. 

- 각 section은 메모리에 저장이 될 때 독자적인 영역을 가짐짐 => segment 

<Object file의 Section 종류>

- Text Section : code, instructions 

- Data Section : 초기화된 전역변수

- BSS Section : 초기화 되지 않은 전역변수 (Block Started by Symbol)

=> 전역변수를 Data Section과 BSS Section을 구별하는 이유 ? 

초기화된 변수는 실제 메모리도 디스크상이지만 공간을 잡아야 하지만, 초기화 하지 않은 변수는 실제공간은 할당하지 않고 사이즈 정보등만 저장

- Other Section : symbol table, relocation table, ...

# Linking Process

<linking 과정의 문제점 - compiler가 주는 문제>

- 마이크로 프로세스는 프로그램을 수행할 때 symbol(함수명, 변수등)이 아닌 인스트럭션들의 op-code, operand 주소, branch의 target 주소를 보기때문에 symbol은 주소로 변환이 되어야 함. symbol을 주소로 변환하기 위해 실제 주소를 알아야 함.

* cross reference : 현재 파일에서 사용하고 있는 symbol이지만 다른 파일에서 주소의 위치가 정해진 symbol들의 주소

- cross reference를 알 수 없음 

=> 여러 파일에 흩어져있는 주소들을 모아야 하므로 한번의 Path로는 주소들을 모으기 힘들기 때문에 최소 2 path를 통해서 주소들을 모을 수 있음. 

=> symbol table : symbol들의 정보를 저장하는 테이블이며 엔트리는 각 symbol들이 됨(Symbol name, Section name, Section내의 Offset). linker가 수행

(같은 오브젝트파일에 들어있는 symbol의 주소는 당연히 알 수 있지)

-  PC Relative Addressing : 현재 PC값에서 Symbol의 주소로 점프하는 주소. Relocatable Address

* Internal Symbol들에 대한 PC Relative Addressing을 하는 이유 : 전체 Section의 위치에 관계없이 PC로부터의 상대적인 주소는 변하지 않기 때문 

# Race condition의 방지

- 하드웨어적 매커니즘 : 인터럽트 enable/disable, 버스의 트랜잭션 기법들

- 소프트웨어 매커니즘 : semaphores, monitors

# Deadlock

: 여러 프로세스들이 concurrent하게 수행할 때 발생. 

<해결방법>

- prevention. 예방하는 방법

- detection and recovery. 증상을 최소화하는 방법

* Resource Allocation Graph : 프로세스와 자원사이의 관계를 나타내는데 사용하는 자료구조

box : 프로세스

rounded box : 자원

자원-> 프로세스 : 자원이 프로세스에 할당

프로세스->자원 : 프로세스가 자원을 사용하기를원하는 상황

- Resource Allocation Graph를 이용한 Deadlock 탐지 : Cycle이 존재하는 경우 Deadlock이 발생한 상황임을 알 수 있음.
        단, 자원을 관리하는 세마포어가 바이너리 세마포어인 경우만 반드시 Deadlock 발생

# Deadlock의 사촌들

- Deadlock : 리소스를 공유하는 프로세스들이 서로가 원하는 리소스를 분점하고 있기 때문에 더 진행하지 못하는 것. 리소스를 기다리면서 wating상태에 빠지므로 CPU 관점에서의 리소스를 낭비하는 경우는 없음. 

- Livelock : CPU 리소스를 계속적으로 사용하지만 아무일도 하지 못하는 상황   

ex. router나 DB Server등에서의 Receive Live Lock. 

* interrupt coalescing : 인터럽트발생 빈도를 줄이기 위해 여러번의 입력을 모아하서 한번에 인터럽트를 발생시키거나 일정 시간마다 한번씩 인터럽트를 발생

* 패킷의 우선순위 매기기

- Indefinite postponement : 프로세스 하나 혼자서 주로 발생. 절대 일어날 수 없는 이벤트를 기다리는 상황

# Deadlock의 발생

<필요조건 4가지>

1. Mutual exclusion : 리소스를 공유할 수 없음

2. No preemption : preemption(자신의 리소스를 포기하고 리소스를 전달해 주기)을 할수없는 상황

=> 1,2번은 resource의 특징이므로 어쩔 수 없음

3. Hold and wait : 자신의 리소스는 점유하고 있으면서 다른 리소스를 또 원하는 상황

=> 프로세스가 수행을 시작할 때 해당 프로세스가 필요한 리소스를 한번에 다 받게 하기

=> 현실성이 없음. 어떤 프로세스가 어떤 리소스를 얼마나 필요로 할 지 프로그램 수행전 알기가 어렵고, 안다고 하더라도 비 경제적 임(한번에 많이 할당)

4. Circular wait : 원하는 리소스의 패턴이 Circular하는 상황

=> 역시나 비현실적임. 프로세스들이 사용할 수 있는 시스템의 리소스들을 넘버링하여 한방향으로 리소스를 할당시킴

# Prevention and Detection

1. Banker's Algorithm

: 어떤 프로세스들이 리소스를 점유하고 있을 때의 상태를 2가지로 분류

- safe state : 시스템이 Deadlock 상태에 빠지지 앟는 상태

- unsafe state : 시스템이 Deadlock 상태에 빠질 가능성이 있는 상태

ex. 1997년 12월 24일 우리나라의 IMF 상황

- 새로운 프로세스는 자신의 최대의 resource need를 선언해야 함 (단점이기도 함)

- 어떤 프로세스가 리소스를 요청하면 safe state와 unsafe state를 판단하여 리소스를 할당하거나 wait state로 진행

- Notations

* n : 시스템에 존재하는 프로세스의 갯수

* m : 시스템에 존재하는 리소스의 갯수

- Available[1:m] : 어떤 리소스 i가 몇개있는지 표현

- Max[1:n, 1:m] : 프로세스 i가 j타입의 리소스를 최대 몇개까지 원하는지 표현

- Allocation[1:n, 1:m] : 프로세스 i가 j타입의 리소스를 몇개 받아서 있는지를 표현

- Need[1:n, 1:m] : Max - Allocation. 향후 몇개를 더 할당 받을 수 있는지를 표현

- vectors X, Y

- work array : 어떤 자원의 중간 계산 결과를 저장하고 있는 array

- finish array : 어떤 프로세스가 종료되었는지를 나타내는 boolean array

- Safety Check

step 1. work에 현재 사용가능한 리소스를 asign. finish array의 모든 값을 false로 설정(아직 어떤 프로세스도 끝나지 않음을 의미)

step 2. 현재 수행을 끝내지 않았고, 최대로 필요로하는 리소스를 모두 만족해 줄 수 있는 어떤 프로세스 i를 찾음

step 3. 프로세스를 terminate시키고 finish로 리소스를 반납하는 과정을 모든 해당되는 프로세스만큼 반복하여 수행

step 4. 모든 finish[] 엔트리 값이 true가 되면 끝

- Safety Check를 사용해서 resource grant을 수행하는 방법

step 1. Request array에 각 프로세스의 새로 요청하는 request를 기록

step 2. 어떤 프로세스의 request가 Maximum보다 더 많은 요구를 하게되면 요청을 받아주지 않음

step 3. Maximum 값보다 적은 상태라면 일단 satety check 알고리즘을 수행한 후 safe하면 요청을 들어줌 

=> banker's algorithm은 satety하게 구현하며 deadlock avoidance를 수행. 

=> 프로세스가 maximum request를 각 타입별로 관리해야하고 그걸 수행하기 위해 비용이 비싼 의사결정이 필요하고 deadlock avoidance를 할 수 없는 상황도 있음.

=> Deadlock Detection!!

# Banker's Algorithm을 변형

step 1. 현재 리소스 상태가 주어지면 termination이 가능한 프로세스들을 termination시키기

step 2. 남은 리소스들을 보고, 데드락 때문에 종료되지 못한 리소스들을 발견할 수 있음  

* Deadlock Detection 기법이 큰 주목을 받지 못한 이유

Personal Computer에서는 사용자들이 임의로 종료시키기 때문에 큰 문제가 되지않음.

Server에서는 일종의 watch dog을 사용하여 termination 시킴

* 경우에 따라서는 termination이 비용이 굉장히 비싼 경우가 있음

이럴때, CPR(check point resume)이라는 응용이 동작 중에 일정 시간 간격으로 응용의 모든 상태를 디스크에 저장하고 문제가 발생했을 때 저장된 응용의 상태를 사용해 응용의 수행을 재개하는 기법