- swap out 을 위한 Page 를 선정하기 위한 알고리즘
- Memory 에서 앞으로 사용할 가능성이 적은 페이지를 대상 Page 로 선정하여 Page Fault 를 줄이고, 시스템의 성능을 향상한다.
- 알고리즘 종류
- algorithms/First In First Out 교체 알고리즘
- LRU 교체 알고리즘
- LFU 교체 알고리즘
- NUR 교체 알고리즘리즘
1 min read
...층이 방문하려면 “먼저 발견한 정점을 먼저 처리” 해야 한다. 큐에 넣고 앞에서 꺼내는 것이 곧 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 이 그쪽이다.
Not Used Recently. 페이지 교체 알고리즘 의 하나로, 최근에 쓰이지 않은 Page 를 골라 내보낸다. LRU 와 목적은 같지만, 마지막 사용 시각을 정확히 기록하는 대신 비트 두 개로 대충 근사한다.
Process 가 Page 를 요청했을 때, 그 Page 가 Memory 에 없는 상황 Process 의 부재에서 오류가 발생했을 뿐, Process 가 만든 오류는 아니다.
Linux 는 I/O 성능을 높이기 위해서 Page Cache 를 사용한다.
물리 Memory 에서 swap 영역 으로 데이터를 내보내는 것 .
메모리의 구성 요소 4 개 Code 실행할 프로그램의 코드가 저장되는 영역 (컴파일 시 크기가 결정됨) Data 전역 변수, static variable 등 컴파일 시 결정되는 것들에 대한 영역 stack 지역 변수, parameters, return value 등 임시로 사용하는 값들에 대한 영역 (컴파일 시...
Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort .
선택 정렬은 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다.