OS 메모리 관리

Paging 기법

 

논리적 주소 (Logical address)

 

물리적 주소 (Physical address)

 

주소 바인딩 (Address binding)

 

page table

frame

 

문제점

메모리 단편화 (Memory fragmentation)

 

- 내부 단편화 (발생)

 

- 외부 단편화 (미발생)

 

 

Segmentation 기법

 

code, data, heap, stack 단위 segment 정의

 

segment table

 

문제점

 

메모리 단편화 (Memory fragmentation)

 

- 내부 단편화 (미발생)

 

- 외부 단편화 (발생)

 

Paging <> Segmentation

 

page 일정한 크기의 단위로 나누어 할당

segmentation code, data, heap, stack 등 기능(의미) 단위로 물리 메모리 할당

	Paging	Segmentation
내부 단편화	O	X
외부 단편화	X	O

 

Paged Segmentation

Segmentation 기본으로 하되 이를 다시 동일 크기의 page로 나누어 물리 메모리 할당

 

- Segmentation 기법의 외부 단편화 방지

- Page 기법의 단점 보완

  - 기능(의미) 단위의 Segment로 나누어 process 간 공유, process 내의 접근 권한 보호

 

Virtual Memory

Process 전체를 메모리에 올리지 않더라도 실행 가능하게 하는 기법

process에서 논리적 주소 영역에서 필요한 부분만 물리적 메모리에 적재, 불필요한 메모리 디스크(Swap 영역)에 저장

 

page fault

page

 

Demand paging

https://bubble-dev.tistory.com/entry/Demand-paging

프로세스에서 사용할 메모리 페이지를 프로세스 생성 시에 모두 할당하지 않고, 필요할 때마다 동적으로 할당하는 기법

 

Valid bit: 어떤 페이지가 Physical memory 에 실재한다면 1, 없다면 0을 갖는 bit

 

Page fault

- 사용자가 요청한 페이지가 swap out 되었거나 아직 로딩되지 않아서 없는 경우

- 무효 비트 페이지에 엑세스

- MMU(Memory Management Unit)가 page fault trap(Trap = Software interrupt) 발생

- 해당 프로세스의 명령어 수행을 중지(Trap을 발생)시키고, 디스크에서 해당 페이지를 로딩한 뒤 명령어를 재시작해야함

 

 

Page 교체 알고리즘 (Replacement algorithm)

https://doh-an.tistory.com/28

https://code-lab1.tistory.com/60

 

FIFO (First In First Out)

- 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘

-  Belady`s Anomaly (벨레이디의 모순)

  - https://melonicedlatte.com/2020/10/13/003700.html

  - FIFO(First In First Out)에서, 원래 페이지 프레임의 개수를 늘리면 page fault발생이 감소 해야 하나, 오히려 늘어나는 경우가 발생하는데 그것을 Belady's Anomaly라 한다

 

LRU (Least Recently Used)

- 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘

 

LFU (Least Frequently Used)

- 참조횟수가 가장 적은 페이지를 교체하는 알고리즘

 

MFU (Most Frequently User)

-  LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘

 

OPT (Optimal)

- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.

- 실제로 사용하기 보다는 연구 목적을 위해 사용된다.

 

Thrashing

https://velog.io/@anjaekk/OS-Thrashing

스레싱(Thrashing)이란 페이지 부재율(Page fault)이 증가하여 CPU 이용율이 급격하게 떨어지는 현상을 얘기한다. 스레싱이 발생하는 이유는 프로세스를 처리하는 시간보다 메모리에 적재되지 못한 페이지로 인하여 페이지 교체에 드는 시간이 증가하게되고 그로 인해 CPU이용률이 떨어지게 된다.

운영체제는 CPU 이용율이 낮으면 메모리에 동시에 올라가 있는 프로세스의 수인 MPD(다중 프로그래밍의 정도, Multi-Programming Degree)를 높이게 되는데 동시에 실행하는 프로세스가 많아질 수록 각 프로세스에 할당된 메모리 페이지 프레임들은 더욱 작아지게 된다. 너무 적은 페이지 프레임을 할당받은 프로세스들은 페이지 부재가 증가하게되어 Swapping이 증가하게 되고 결국 CPU의 이용율이 더욱 떨어지는 악순환이 생기게 된다.

 

Solve

1. Working set

워킹셋이라는 이름과 같이 프로세스의 작업을 구성하는 자주 참조되는 페이지들을 묶는다고 생각하면 이해하기 좀 더 편하다. 해당 워킹셋의 합인 전체 프레임이 할당된 페이지 프레임보다 크게되면 Thrashing이 발생하게 된다.

2. Page Fault Frequency

프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거하여 각 프로세스에 할당할 메모리 양을 동적으로 예측하고 조절하는 알고리즘이다