일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- GraphQL
- RxJS
- 프론트엔드
- pytorch
- 이진탐색
- 릿코드
- RT scheduling
- 자료구조
- 타입스크립트
- 포인터
- 웹팩
- alexnet
- 프로그래머스
- vue3
- 프로세스
- APOLLO
- 자바스크립트
- C
- 알고리즘
- Machine Learning
- 해시테이블
- cors
- 스택
- 컨테이너
- 연결리스트
- 코딩테스트
- 브라우저
- 배열
- 연결 리스트
- 큐
- Today
- Total
프린세스 다이어리
[OS] 페이지 교체 알고리즘(Page Replacement Algorithm) 5가지와 스레싱(Thrashing) 현상 본문
[OS] 페이지 교체 알고리즘(Page Replacement Algorithm) 5가지와 스레싱(Thrashing) 현상
개발공주 2022. 2. 2. 12:091. 페이지 교체 알고리즘 종류
메모리가 다 찬 상태에서, 메모리에 올라간 상태의 페이지들 중 어떤 것을 내리고 새 페이지로 교체할지 최선책을 내려야 한다. 최소한의 횟수로 페이지 폴트 인터럽트가 발생해야 CPU가 여러 프로그램을 동시에 실행할 때 처리 지연이 적다. 이를 판단하는 대표적인 알고리즘에는 5가지 정도가 있다.
1-1. FIFO
- 단순하게 가장 먼저 들어온 페이지를 내리고 새 페이지로 교체하는 알고리즘이다.
- 만약 page 1 -> page 3-> page 4 -> page 5 순으로 페이지가 올라가서 꽉 찬 상태라면, 새로 참조해야 하는 페이지인 page 2는 page 1과 교체가 된다.
1-2. OPT(OPTimal Replacement Algorithm)
- 가장 이상적으로 페이지 교체를 최소화하는 방법은 바로 애초에 인터럽트가 발생하지 않도록 준비하는 것이다.
- 앞으로 가장 오랫동안 사용하지 않을 것 같은 페이지를 내리고, 해당 공간에 새 페이지를 올리는 방식이다.
- 이건 앞으로 어떤 페이지가 필요할지 100% 알기 어렵기 때문에 일반적인 OS에서는 불가하다.
1-3. LRU(Least Recently Used)
- 가장 오래 전에 참조된 페이지를 교체하는 방법이다.
- 가장 많이 사용되는 페이지 교체 알고리즘이다.
1-4. LFU(Least Frequently Used)
- 가장 적게 사용된 페이지를 교체하는 방법이다.
1-5. NUR(Not Used Recently)
- LRU와 마찬가지로, 최근에 사용하지 않은 페이지부터 교체하는 방법이다.
- 각 페이지마다 참조비트(R), 수정비트(M)를 둔다.
- (0,0), (0,1), (1,0), (1,1) 순으로 페이지가 교체된다.
2. 메모리 지역성
메모리 지역성이란 지금 참조하는 메모리 주변을 다음에도 참조할 확률이 높다는 원리다. CPU가 프로그램을 실행하기 위해서는 메모리에서 데이터를 가져와야 하는데, 그 데이터가 메모리에 없다면 하드디스크로부터 데이터를 가져와 메모리에 올려야 한다. 이 과정을 최소화하기 위한 예측이 필요한데 바로 메모리 지역성이라는 원리가 여기에 활용된다.
3. 스레싱(Thrashing)
프로그램을 과도하게 많이 띄워 놓으면 어느 순간까지는 페이지 교체를 진행하면서 CPU가 실행을 잘 하다가 성능이 급격하게 떨어지는 순간이 온다. 원인은 프로세스가 실제 실행 시간 보다도 더 많은 시간을 페이징에 사용하고 있기 때문이다. 필요한 프로그램만 띄워서 사용해야 쾌적하게 컴퓨터를 사용할 수 있는 이유다.
참고
'운영체제, 컴퓨터 구조' 카테고리의 다른 글
[OS] 작은 C언어 코드가 실행될 때 어떻게 메모리를 사용하는지 설명 (0) | 2022.02.04 |
---|---|
[OS] 가상메모리 메커니즘 중 하나인 세그멘테이션 기법 정리 (0) | 2022.02.03 |
[OS] 요구 페이징(Demand Paging)과 관련해 페이지 폴트 인터럽트(Page Fault Interrupt) 발생하는 과정 설명 (0) | 2022.02.01 |
[OS] 페이징 시스템의 "공유 메모리(Shared Memory)" 개념 (0) | 2022.01.31 |
[OS] 다중단계 페이징 시스템의 개념, TLB 뜻 (0) | 2022.01.30 |