[정보처리기사/계산식] 페이지교체 알고리즘

관련 강의

[정보처리 필기 특강] 교체 알고리즘 | LRU

[정보처리 필기 특강] 교체 알고리즘 | LFU

[정보처리 필기 특강] 교체 알고리즘 | FIFO

[Q&A] 페이지 교체 알고리즘 | FIFO

 

 

가상기억장치 구현기법: 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 기법

• 페이징 기법: 고정 크기로 나눔(페이지). 10k 공간에 3k를 넣으면 내부 단편화가 발생.
• 세그먼테이션 기법: 가변 크기로 나눔(세그먼트). 10k 공간에 12k 넣으려고 하면 외부 단편화 발생

 

페이지 교체 알고리즘

페이지 부재가 발생했을 때 가상기억장치의 필요한 페이지를 주기억장치에 적재해야함

→주기억장치의 모든 페이지 프레임이 사용 중이라면 어떤 페이지를 교체할 것인가?

• FIFO(First In First Out): 들어온 순서대로 교체(꽉 차면 제일 처음 넣었던 걸 빼기)
• LRU(Least Recently Used): 오랫동안 안 쓴 거 교체
• LFU(Least frequently used): 최근에 사용 안 한 거 교체
• OPT(Optimal): 미래에 가장 오랫동안 사용되지 않을 페이지를 교체. 미래의 페이지 참조를 알 수 없기 때문에 실제 시스템에서는 사용할 수 없음
• NUR(Not Used Recently): 최근에 사용되지 않은 페이지를 교체. 페이지에 사용 여부를 기록하는 비트 플래그를 두고, 주기적으로 플래그를 초기화하면서 페이지를 관리
• SCR(Second Chance Replacement): 기회를 2번 줌. 참조비트가 1이면 0으로 리셋하고 페이지를 큐의 뒤로 보내 교체를 미룸. 참조 비트가 0이면 교체.

 

스레싱 현상: 프로세스를 처리하는 시간보다 페이지 교체에 더 많은 시간을 사용하는 것. 워크셋 등을 이용하여 해결.

 

프로세스 상태 전이도

준비→실행, 실행→준비 로 변하는 게 context switching

준비, 실행, 대기 상태와 dispatch, timer runout, wake up 정도는 알아두기.

https://velog.io/@dd9s2/운영체제-프로세스-프로세스-상태-전이-PCB프로세스-제어-블록

 

 

계산식

• FIFO(First In First Out): 들어온 순서대로 교체(꽉 차면 제일 처음 넣었던 걸 빼기)

 

• LRU(Least Recently Used): 오랫동안 안 쓴 거 교체

 

• LFU(Least frequently used): 최근에 사용 안 한 거 교체