12. Memory Management-2

멀티 프로그래밍 시스템에서 메모리 내에 위치한 유저 프로세스의 수가 증가함.

-> 모든 유저 프로세스가 사용하는 Page 수보다 PM의 Frame 수가 적은 상황이 발생

-> 메모리 과다 할당 상태(= 다 PM에 올려둘 순 없잖아~~)

 

이걸 해결하려면 Page Fault 처리에 Page Replacement를 추가해야함.

Page Replacement

: PM에 위치한 Page를 디스크에 저장하고 요구된 Page가 해당 Frame을 할당 받도록 하는 방법

 

Page Fault with Page Replacement

1. 디스크에서 요구된 Page의 위치를 찾음.

2. PM에서 Free Frame을 찾음

- Free Frame이 있으면 그거 바로 사용함.

- 없으면 Page Replacement Algorithm으로 교체할 Frame을 선택하고 그 Frame을 Disk에 저장하고 Page Table을 변경함.

3. 요구된 Page를 Free Frame으로 읽어 들이고, 해당 Page Table을 적절히 변경함.

4. 유저 프로세스를 재시작함.

Page Replacement 고려사항

1) 각 유저 프로세스에게 어떻게 Frame을 분배할 거임?

동등하게 1/N해서? ㄴㄴ

많이 필요로 하는 놈에게 많이, 적게 필요로 하는 놈에게 적게 분배해야 함.

-> Frame Allocation Algorithm

 

2) Page 교체가 필요 시 어떤 Page를 교체할 거임?

 -> Page Replacement Algorithm

 

위 알고리즘들은 모두 [Page 교체에 의한 I/O 작업 수행 횟수 줄이는게 목적](∵I/O 작업이 매우 큰 비용을 사용하기에...)

적합한 알고리즘의 사용이 시스템의 성능을 크게 좌우함.

 

Page Replacement Algorithms

- 어떤 Page Replacement Algorithm 쓸 거임?

-> 가장 낮은 Page Fault 발생 빈도를 가진 알고리즘(= 가장 낮은 I/O 작업 횟수를 요구하는 알고리즘)

 

여러 알고리즘들을 비교하기 위해선 아래 환경을 가정하고 비교해보자!!!

 

1) 3개의 Frame이 할당됨

2) Page를 참조하는 순서: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 

3) 한번 참조된 Page는 Page 교체가 일어나기 전까지는 PM에 위치함.(다시 참조 시엔 Page Fault 발생 X)

 

Optimal Algorithm

: 앞으로 가장 오랫동안 사용되지 않을 Page부터 먼저 교체함.

-> 이거 말만 들으면 가장 이론상 최적임(=가장 낮은 Page Fault 발생 빈도).

But, 앞으로 어떤 Page가 사용될지 미리 알 수 없기에 실제로는 구현 불가능함.

-> Page Fault 발생 횟수: 9번

 

FIFO Algorithm

: 먼저 Frame이 할당된 Page를 먼저 교체함.

-> 가장 단순함

- FIFO 큐를 이용해서 구현 가능

- 멀티미디어 Data로 인해 주목 받음(Why? 계속해서 새로운 데이터가 들어오니까!)

-> Page Fault 발생 횟수: 15번

SCR Algorithm(Second Chance Replacement Algorithm)

: FIFO 기법의 단점을 보완하는 기법으로, 자주 사용되는 Page의 교체를 방지함.

- FiFO 큐를 이용하되 참조 bit를 두어 Page를 관리함.

- 참조 bit은 최초로 Frame에 Load될 때, Page가 참조될 시에 1로 두고, 일정 주기마다 다시 0으로 바꾼다.

-> 만약 참조 bit가 1인데 제거 대상이 되면, 제거하지 않고 참조 bit만 0으로 변경함.(후...넌 한번 봐준다!! 대신 찬스 압수!)

 

Clock Algorithm

: SCR 기법의 발전형으로, 환형 큐가 추가됨.

여기서 화살표가 Hand임.

LFU Algorithm(Least Frequently Used Algorithm)

: 사용 빈도가 가장 적은 Page를 교체하는 기법으로, 지금까지 가장 적게 참조된 Page가 교체 대상으로 선택됨.

 

하지만!!!!!!!!

문제점: 프로그램 초기에만 많이 사용되고 이후 사용되지 않는 경우 Frame을 계속 차지한 채 바뀌지가 않는 문제가 있음.

 

NRU Algorithm(Not Recently Used Algorithm)

: 최근에 사용하지 않은 Page를 교체하는 기법으로, Page마다 참조 bit와 변형 bit를 두어 관리함.

'값이 변경된다면 오래 사용하지 않을까?' 하는 생각으로 만든 알고리즘임.

LRU Algorithm(Least Recently Used Algorithm)

: 가장 오랫동안 참조하지 않은 Page부터 먼저 교체하는 기법으로, 가장 Optimal 알고리즘과 유사하며 실제 구현 가능함.

-> Page Fault 발생 횟수: 12번

(오오!!! 거의 Optimal 알고리즘급인데???)

Swapping

: Page Out으로 메모리 부족을 해결치 못할 경우 필요한 기법.

- Swap Out 대상이 된 프로세스 전체를 Secondary Storage로 보냄.

- 이런 식으로 Page Out or Swapping에 사용되는 Secondary Storage를 Swap 영역이라고 함.

Contiguous Memory Allocation

1) Single Partition Allocation

-> 유저 프로그램 영역을 한번에 1개의 유저 프로그램만 사용하도록 함.

 

2) Multi Partition Allocation

-> 1) 방법에 멀티프로그래밍 개념을 추가해서 유저 프로그램 영역을 여러 개의 유저 프로그램이 사용하도록 함.

 

3) No Partition

-> 각 프로그램이 필요에 따라 전체 유저 프로그램 영역을 사용함.

이때, Page/Swap Out 시에 Garbage Collection이 필요함.(종료된 프로세스가 사용했던 메모리들을 제거해줌.)

Memory Allocation Problem

: 유저 프로그램이 Load될 때, PM의 OS영역을 제외한 User 영역에 배치됨.

이때, Protection(다른 프로세스가 사용 중인 메모리는 해치지 않긔!), Relocation, Swap 기법을 사용하는데...

프로그램을 메모리에 Load 시, 메모리의 빈 공간 중 어디에 프로그램을 Load할 지에 대한 고려가 필요함.

1) First-fit: 가장 처음 빈 공간에 배치

2) Best-fit: Load될 프로그램의 크기와 가장 비슷한(작아서 딱 들어맞는) 공간에 배치

3) Worst-fit: 빈 공간이 큰 곳에 배치

 

-> 이러한 고민들이 생긴 이유가 바로....!!!!

Fragmentation

1) External Fragmentation

: 프로그램에게 할당 후 남은 메모리의 총 공간이 새로운 할당 요청에 충분하긴 하지만, 그 공간이 연속적이지 않아서 사용할 수 없는 경우

 

2) Internal Fragmentation

: 할당된 메모리의 크기가 요청된 메모리의 크기보다 조금 더 커서 할당은 성공했으나 그 차이만큼의 영역을 사용할 수 없는 경우

ex. Paging에서 Page Frame이 4KB로 고정되었지만, 요청 PM 영역이 3998B이면, 2B만큼의 Internal Fragmentation이 발생함.

-> 뭔솔? 간단히 얘기하자면 Page 내부에 Fragmentation이 발생하는 것임.

 

External Fragmentation 예시

 

Protection과 Relocation

- Protection

: Contiguous Memory Allocatio 방법을 사용 시 OS의 메모리 영역과 유저 프로그램의 메모리 영역은 서로 구분되어야 함.

(OS 영역은 유저 프로그램이 절대절대절대절대절대절대절대 건들면 안됨.)

 

- Relocation

: 유저 프로그램은 재배치 가능한 주소로 표현됨. 재배치 가능한 주소를 이용해서 프로그램이 어느 위치에 Load되더라도 쉽게 Code의 주소를 결정할 수 있어야 함.

 

Protection과 Relocation을 위한 HW의 지원

-> Limit Register와 Relocation Register를 이용해서 구현함.

- Limit Register: 참조가 허용되는 주소의 최댓값

-> Limit Register의 값을 비교해서 참조하는 주소가 허용되는 영역인지 판별함.

 

- Relocation Register: 프로그램이 차지하는 주소 영역 중 첫번째 주소

-> 재배치 가능한 주소를 통해서 실제 물리 메모리의 주소로 참조 가능하게 함.

 

-> 이 부분들은 자세히 공부X. OS에서 할 거가 아님.