기억장치

1. 기억장치의 관리 전략

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

1) 종류

• 반입(Fetch) 전략 : 적재 시기 결정

요구 반입	실행중인 프로그램이 특정 프로그램/데이터 등의 참조를 요구할 때 적재하는 방법
예상 반입	실행중인 프로그램에 의해 참조될 프로그램이나 데이터를 미리 예상하여 적재하는 방법

• 배치(Pacement) 전략 : 적재 위치 결정
  프로그램이나 데이터가 들어갈 수 있는 크기의 빈 영역에 해당

최초 적합(First fit)	빈 영역 중 첫 번째 분할 영역에 배치시키는 방법
최적 적합(Best fit)	빈 영역 중 단편화를 가장 작게 남기는 분할 영역에 배치시키는 방법
최악 적합(Worst fit)	빈 영역 중 단편화를 가장 많이 남기는 분할 영역에 배치시키는 방법

• 교체(Replacement) 전략 : 주기억장치가 Full 일 때(모두 사용 중) 교체하여
  새로운 프로그램을 적재시킬 위치(교체위치) 결정
  • 종류 : FIFO, OPT, LRU, LFU, NUR, SCR 등

---

2. 주기억장치 할당기법

1) 연속 할당 기법

• 프로그램을 주 기억 장치에 연속으로 할당하는 기법
• 단일 분할 할당 기법
  - 주기억장치를 운영체제 영역과 사용자 영역으로 나누어, 한순간에는 오직 한 명의 사용자만이 주기억장치의 사용자 영역을 사용하는 기법
  - 경계 레지스터가 사용됨(운영체제/사용자 영역 구분)
  - 프로그램의 크기가 작을 경우, 사용자 영역이 낭비될 수 있음
  - 오버레이 기법 : 주기억장치보다 큰 사용자 프로그램을 실행하기 위한 기법
  - 스와핑 기법 : 하나의 프로그램 전체를 주기억장치에 할당하여 사용하다 필요에 따라 다른 프로그램과 교체
• 다중 분할 할당 기법
  - 고정 분할 할당 기법(정적 할당 기법)
     프로그램 할당 전, 운영체제가 주기억장치의 사용자영역을 여러 개의 고정된 크기로 분할하고,
     준비상태 큐에서 준비중인 프로그램을 할당하여 수행
  - 가변 분할 할당 기법(동적 할당 기법)
     프로그램을 주기억장치에 적재하면서 필요한 만큼의 크기로 영역을 분할
     고정 분할 할당 기법의 단편화를 줄이기 위해 사용

2) 분산 할당 기법

• 프로그램을 특정 단위의 조각으로 나누어 주기억장치 내에 분산하여 할당하는 기법
• 페이징 기법
• 세그먼테이션 기법

---

3. 가상기억장치 구현 기법

1) 가상기억장치(Virtual Memory)

• 보조기억장치의 일부를 주기억장치처럼 사용하는 것
• 프로그램을 여러 개의 작은 블록 단위로 나누어서 가상기억장치에 보관해놓고, 
  프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리
• 주기억장치의 이용률과 다중 프로그래밍의 효율 상승
• 블록단위를 나누어 사용하므로 연속 할당 방식에서 발생할 수 있는 단편화 해결
• 구현 방법 : 페이징 기법, 세그먼테이션 기법 (분산 할당 기법)

2) 가상 기억장치 구현 기법

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

• 세그먼테이션 기법
  • 가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위(작업 단위)로 나눈 후
    주기억장치에 적재시켜 실행시키는 기법
  • Segment : 프로그램을 배열이나 함수 등과 같은 논리적인 크기로 나눈 단위
    각 세그먼트는 고유한 이름과 크기를 가짐
  • 기억공간 절약 가능
  • 주소 변환을 위해 세그먼트 맵 테이블(Segment Map Table)필요
  • 외부단편화 발생 가능

---

4. 페이지 교체 알고리즘

• 페이지 부재(Page Fault)가 발생하면 가상기억장치에서 필요한 페이지를 찾아 주기억장치에 적재 해야함
  이 때 주기억 장치의 모든 페이지 프레임이 사용중일 때, 교체할 페이지 프레임을 선택하는 알고리즘
• 페이지 부재: 참조하려는 페이지가 페이지프레임에 올라와있지 않은 상태
• OPT(OPTimal replacement, 최적 교체)
  
  • 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체
  • 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘
• FIFO(First In First Out)
  • 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체
  • 이해가 쉽고 설계및 프로그래밍이 간단
• LRU(Least Recently Used)
  • 최근에 가장 오랫동안 사용하지 않은 페이지를 교체
  • 각 페이지마다 Counter나 Stack을 두어 현 시점에서 가장 오랫동안 사용하지 않은 페이지 교체
• LFU(Least Frequently Used)
  • 사용빈도가 가장 적은 페이지를 교체
  • 사용빈도가 많은 페이지는 교체되지 않고 사용됨
• NUR(Not Used Recently)
  • 최근에 사용하지 않은 페이지를 교체
  • 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로함
  • 최근의 사용여부를 확인하기 위해 각 페이지마다 참조비트(Reference Bit)와 변형비트(Modifed Bit)가 사용됨
  • 참조비트와 변형비트의 값에 따라 교체될 페이지의 순서가 결정됨 
    • 참조비트 : 호출 (1 , 0)
    • 변형비트 : 사용 (1 , 0) 
• SCR(Second Chance Replacement, 2차 기회 교체)
  • 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 기법
  • FIFO 단점 보완을 위해 사용

---

5. 관리 사항

1) 페이지 크기

• 페이징 기법 사용시 페이지의 크기에 따라 시스템에 미치는 영향이 다름
• 페이지 크기가 작을 경우
  • 페이지 단편화 감소, 페이지의 주기억장치로의 이동시간 감소
  • 효율적인 워킹셋 유지(불필요한 내용 적재 확률 감소)
  • 페이지 맵 테이블 크기 증가, 매핑 소요 시간 증가
  • 디스크 접근 횟수가 증가하므로 전체 입/출력 시간은 증가함
• 페이지 크기가 클 경우
  • 페이지 맵 테이블의 크기 감소, 매핑 소요 시간 감소
  • 디스크 접근 횟수가 감소하므로 전체적인 입/출력 효율성 증대
  • 페이지 단편화 증가, 페이지의 주기억장치로의 이동시간 증가

2) Locality

• 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론
• 스레싱(잦은 페이지 부재로 인한 잦은 페이지 교체) 방지하기 위한 워킹셋 이론의 기반
• 로컬리티의 종류
  • 시간 구역성 : 하나의 페이지를 일정 시간동안 집중적으로 액세스 하는 현상
  • 공간 구역성 : 일정 위치의 페이지를 집중적으로 액세스 하는 현상

3) 워킹 셋(Working Set)

• 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합