정보처리기사 4과목 프로그래밍 언어 활용 (기억장치 관리 전략 정리(페이지교체 알고리즘 포함))

기억장치의 관리 전략의 개요

• 보조기억장치의 프로그램이나 데이터를 주기억장치에 적재시키는 시기 (when), 적재 위치(where) 등을 지정하여
  한정된 주기억장치의 공간을 효율적으로 사용하기 위함

 

 

 

반입(Fetch) 전략

• 보조기억장치에 보관 중인 프로그램이나 데이터를 언제(when) 주기억장치로 적재할 것인지 결정하는 전략
  • 요구 반입(Demand Fetch)
    : 실행 중인 프로그램이 특정 프로그램이나 데이터 등의 참조를 요구할 때 적재하는 방법
  • 예상 반입(Anticipatory)
    : 실행 중인 프로그램에 의해 참조될 프로그램이나 데이터를 미리 예상해 적재하는 방법

 

 

배치(Placement) 전략

• 새로 반입되는 프로그램이나 데이터를 주기억장치의 어디에(where) 위치시킬지를 결정하는 전략
  • 최초 적합(First Fit) : 빈 영역 중에서 첫 번째 분할 영역에 배치
  • 최적 적합(Best Fit) : 빈 영역 중에서 단편화를 가장 작게 남기는 분할 영역에 배치
  • 최악 적합(Worst Fit) : 빈 영역 중에서 단편화를 가장 많이 남기는 분할 영역에 배치

 

 

교체(Replacement) 전략

• 이미 사용되고 있는 영역 중에서 어느(who) 영역을 교체할지 결정하는 전략
  • FIFO, LRU, LFU, NUR, OPT, SCR

 

[페이지교체 알고리즘]

FIFO(First In First Out) = FCFS(First Come First Serve)
- 선입선출
     - 가장 간단한 알고리즘으로 메모리에 올라온지 가장 오래된 페이지를 교체
     - 이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나
       페이지가 올라온 순서를 큐(Queue)에 저장하는 방식 등을 사용할 수 있다.
                                 (리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 스택과 달리,
                                  리스트의 한쪽 끝에서는 원소들이 삭제되고 반대쪽 끝에서는 원소들의 삽입만 가능)
- 각 페이지가 주기억장치에 적재될 떄마다 그때의 시간을 기억시켜
  가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

LRU(Least Recently Used)   (Recently : 최근)
- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
- 가장 오래 전에 사용된 페이지 교체

LFU(Least Frequently Used)   (Frequently : 자주)
- 사용 빈도가 가장 적은 페이지를 교체하는 기법

OPT(OPTimal replacement, 최적 교체)
- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
- 벨레이디(Belady)가 제안한 것으로, 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘

NUR(Not Used Recently)
- LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법
- 각 페이지마다 두 개의 비트, 즉 참조 비트와 변형 비트 사용

SCR(Second Chance Replacement, 2차 기회 교체)
- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 기법의 단점을 보완하는 기법

 

 

할당(Allocation) 전략

• 프로그램이나 데이터를 실행시키기 위해 주기억장치에 어떻게(How) 할당할지 정함
  • 연속 할당 기법 : 프로그램을 주기억장치에서 연속으로 할당하는 기법
    • 단일 분할 할당 기법 : 오버레이, 스와핑
    • 다중 분할 할당 기법 : 고정(정적) 분할 할당 기법, 가변(동적) 분할 할당 기법
  • 분산 할당 기법 : 프로그램을 특정 단위의 조각으로 나누어 할당하는 기법
    
    • 페이징(Paging) 기법, 세그먼테이션(Segmentation) 기법