[4과목 프로그래밍 언어 활용] 응용 SW 기초 기술 활용 - 154. ⭐ 가상기억장치 구현 기법 / 페이지 교체 알고리즘

1. 가상기억장치의 개요

• 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것
• 용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법
• 프로그램을 여러 개의 작은 블록 단위로 나누어서 가상기억장치에 보관해 놓고, 프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당
• 주기억장치의 용량보다 큰 프로그램을 실행하기 위해 사용
• 주기억장치의 이용률과 다중 프로그래밍 효율을 높일 수 있음
• 가상기억장치의 주소를 주기억장치의 주소로 바꾸는 주소 변환 작업 필요
  • 논리적인 가상주소를 물리적인 실기억주소로 변환하는 것
  • 주소 사상, 주소매핑
• 불록단위로 나누어 사용하므로 연속 할당 방식에서 발생할 수 있는 단편화를 해결

2. ⭐ 페이징(Paging) 기법

• 가장기억장치에 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 나눠진 프로그램(페이지)을 동일하게 나눠진 주기억장치의 영역(페이지 프레임)에 적재시켜 실행하는 기법
• 페이지(Page) : 프로그램을 일정한 크기로 나눈 단위
• 페이지 프레임(Page Frame) : 페이지 크기로 일정하게 나누어진 주기억장치의 단위
• 주소 변환을 위해 페이지의 위치 정보를 가지고 있는 페이지 맵 테이블(Page Map Table)이 필요
• 페이지 맵 테이블 사용으로 비용이 증가, 처리 속도 감소
• 외부 단편화 X, 내부 단편화 O

3. ⭐ 세크먼테이션(Segmentation) 기법

• 가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후, 주기억장치에 정재시켜 실행시키는 기법
• 세그먼트(Segment) : 프로그램을 배열이나 함수 들과 같은 논리적인 크기로 나눈 단위
• 각 세그먼트는 고유한 이름과 크기를 갖음
• 기억장치의 사용자 관점을 보존하는 기억장치 관리 기법
• 기억공간을 절약하기 위해서 사용
• 주소 변환을 위해 세그먼트가 존재하는 위치 정보를 가지고 있는세그먼트 맵 테이블(Segment Map Table)이 필요
• 주기억장치에 적재될 때 다른 세그먼트에게 할당된 영역을 침범할 수 없음 → 기억장치 보호키(Storage Protection Key) 필요
• 내부 단편화 X, 외부 단편화 O

💡 세그먼테이션 기법의 일반적인 주소 변환

① 가상주소의 세그먼트 번호를 세그먼트 맺 테이블에서 해당 세그먼트의 기준번지와 세그먼트 크기 구하기. 세그먼트 번호는 세그먼트 맵 테이블에 대한 색인으로 사용됨
② 가상 주소의 변위값과 세그먼트의 크기를 비교
③ 변위값이 작거나 같으면 기준번지와 변위값을 더하여 실기억주소를 만들어 주기억장치를 액세스
④ 변위값이 크면 다른 영역을 침범하게 되므로 실행 권한을 운영체제에게 넘기고 트랩을 발생시킴(현재 찾는 세그먼트의 위치가 해당 세그먼트의 크기(한계번지)를 초과하였다는 의미)

4. ⭐ 페이지 교체 알고리즘

• 페이지 부재(Page Fault)가 발생했을 때, 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 기법

1) OPT (OPTimal replacement, 최적 교체)

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

2) FIFO (First In First Out)

• 각 페이지에가 주기억장치에 정재될 때마다 그때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법
• 이해하기 쉽고, 프로그래밍 및 설계가 간단

① 참조 페이지를 각 페이지 프레임에 차례로 적재시키되 이미 적재된 페이지는 해당 위치의 페이지 프레임을 사용</br>
② 사용할 페이지 프레임이 없을 경우 가장 먼저 들어와서 오래 있었던 페이지 2를 제거한 후 5를 적재</br>
③ 적재된 페이지 3을 제거한 후 2를 적재하며, 같은 방법으로 나머지 참조 페이지 수행

3) LRU (Least Recently Used)

• 가장 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
• 각 페이지마다 계수기(Counter)나 스택(Stack)을 두어 현 시점에서 가장 오랫동안 사용하지 않은, 즉 가장 오래 전에 사용된 페이지 교체

① 참조 페이지를 각 페이지 프레임에 차례로 적재시키ㅚ 이미 적재된 페이지는 해당 위치의 페이지 프레임 사용</br>
② 사용할 페이지 프레임이 없을 경우 현재 시점에서 가장 오랫동안 사용되지 않은 페이지 3을 제거 후 5를 적재</br>
③ 같은 방법으로 나머지 참조 페이지 수행

4) LFU (Least Frequently Used)

• 사용 빈도가 가장 적은 페이지를 교체하는 기법
• 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용됨

5) NUR (Not Used Recently)

• LRU와 비슷한 알고리즘
• 최근에 사용하지 않은 페이지를 교체하는 기법
• 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전체로 LRU에서 나타나는 시간적인 오버헤트를 줄임
• 최근의 사용 여부를 확인하기 위해 각 페이지마다 참조비트(Reference Bit)와 변형비트(Modified Bit, Dirty Bit)가 사용됨

 

6) SCR (Second Change Replacement, 2차 기회 교체)

• 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것
• FIFO 기법의 단점 보완

 

 

 

📖 Reference

2023 시나공 정보처리기사 필기 : 네이버 도서