- swap out 을 위한 Page 를 선정하기 위한 알고리즘
- Memory 에서 앞으로 사용할 가능성이 적은 페이지를 대상 Page 로 선정하여 Page Fault 를 줄이고, 시스템의 성능을 향상한다.
- 알고리즘 종류
- algorithms/First In First Out 교체 알고리즘
- LRU 교체 알고리즘
- LFU 교체 알고리즘
- NUR 교체 알고리즘리즘
...층이 방문하려면 “먼저 발견한 정점을 먼저 처리” 해야 한다. 큐에 넣고 앞에서 꺼내는 것이 곧 FIFO 다. 반면 DFS 는 마지막에 발견한 쪽으로 더 파고들어야 하므로 스택을 쓴다. 페이지 교체 알고리즘 — 메모리가 꽉 찼을 때 가장 오래전에 적재된 Page 를 내보낸다. 구현이 단순하고 적재 시각만 기록하면 되지만, 오래 있었다는 것과 앞으로 안 쓰인다는 것은 다른 이야기다. 자주 쓰...
LFU(Least Frequently Used)는 사용 빈도가 가장 낮은 항목을 먼저 제거하는 replacement policy다. cache나 페이지 교체 알고리즘에서 LRU와 함께 비교된다. LRU와의 차이 LRU는 “얼마나 최근에 썼는가”를 보고, LFU는 “얼마나 자주 썼는가”를 본다. 자주 쓰이는 hot item을 오래 보존하는 데는 LFU...
LRU(Least Recently Used)는 가장 오래 사용되지 않은 항목을 먼저 제거하는 replacement policy다. cache와 페이지 교체 알고리즘에서 자주 등장한다. 핵심 아이디어 최근에 접근한 데이터는 가까운 미래에도 다시 접근될 가능성이 높다는 locality 가정에 기대고 있다. 그래서 접근 시점을 계속 갱신하고, 공간이 부...
Not Used Recently. 페이지 교체 알고리즘 의 하나로, 최근에 쓰이지 않은 Page 를 골라 내보낸다. LRU 와 목적은 같지만, 마지막 사용 시각을 정확히 기록하는 대신 비트 두 개로 대충 근사한다. LRU 를 정확히 구현하려...
만약 Memory 가 꽉 찼다면 메모리에 있는 Page 를 swap 영역 으로 내보내야 한다 (swap out). 이때, 어떤 Page 를 보낼지 선정하는 알고리즘이 페이지 교체 알고리즘 이다.
LFU(Least Frequently Used)는 사용 빈도가 가장 낮은 항목을 먼저 제거하는 replacement policy다. cache나 페이지 교체 알고리즘에서 LRU와 함께 비교된다.
LRU(Least Recently Used)는 가장 오래 사용되지 않은 항목을 먼저 제거하는 replacement policy다. cache와 페이지 교체 알고리즘에서 자주 등장한다.
먼저 들어온 것을 먼저 내보내는 처리 순서다. 줄을 선 순서대로 처리한다고 보면 되고, 이 규칙을 구현한 자료구조가 큐(queue) 다. 반대는 나중에 들어온 것을 먼저 꺼내는 LIFO 이고, stack 이 그쪽이다.
Process 가 Page 를 요청했을 때, 그 Page 가 Memory 에 없는 상황 Process 의 부재에서 오류가 발생했을 뿐, Process 가 만든 오류는 아니다. Page Fault 가 발생하면, Process 가 해당 Page 를 사용할 수 있도록 swap 영역 에서 물리 Memory 로 옮겨야 한다...
Not Used Recently. 페이지 교체 알고리즘 의 하나로, 최근에 쓰이지 않은 Page 를 골라 내보낸다. LRU 와 목적은 같지만, 마지막 사용 시각을 정확히 기록하는 대신 비트 두 개로 대충 근사한다.
Linux 는 I/O 성능을 높이기 위해서 Page Cache 를 사용한다.
물리 Memory 에서 swap 영역 으로 데이터를 내보내는 것
실행할 프로그램의 코드가 저장되는 영역 (컴파일 시 크기가 결정됨)
선택 정렬은 다음과 같은 순서로 이루어진다.
Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort