기억장치 관리

기억장치의 관리 전략

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

반입 (Fetch) 전략

반입 전략은 보조기억장치에 보관중인 프로그램이나 데이터를 언제 주기억장치로 적재할 것인지를 결정하는 전략이다.

- 요구 반입 (Demand Fetch)
실행중인 프로그램이 특정 프로그램이나 데이터 등의 참조를 요구할 때 적재하는 방법이다.

- 예상 반입 (Anticipatory Fetch)
실행중인 프로그램에 의해 참조될 프로그램이나 데이터를 미리 예상하여 적재하는 방법이다.

배치 (Placement) 전략

배치 전략은 새로 반입되는 프로그램이나 데이터를 주기억장치의 어디에 위치 시킬 것인지를 결정하는 전략이다.

- 최초 적합 (First Fit)
프로그램이나 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 첫 번째 분할 영역에 배치시키는 방법.

- 최적 적합 (Best Fit)
프로그램이나 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 단편화를 가장 작게 남기는 분할 영역에서 배치시키는 방법.

- 최악 적합 (Worst Fit)
프로그램이나 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 단편화를 가장 많이 남기는 분할 영역에 배치시키는 방법

문제 1. 기억장치 상태가 다음 표와 같을 때 기억장치 관리 전략으로 First FIt, Best Fit, Worst Fit 방법을 사용하려 할 때, 각 방법에 대하여 10K의 프로그램이 할당받게 되는 영역의 번호는?

영역 번호	영역 크기	상태
1	5K	공백
2	14K	공백
3	10K	사용중
4	12K	공백
5	16K	공백

10K의 프로그램이 할당받게 되는 영역의 번호
- First Fit : 2번 (14K에 들어갈 수 있고, 가장 첫 번째)
- Best Fit : 4번 (12K에 들어갈 수 있고, 가장 효율적 크기)
- Worst Fit : 5번 (16K에 들어갈 수 있고, 가장 최악의 가성비)

교체 (Replacement) 전략

교체 전략은 주기억장치의 모든 영역이 이미 사용중인 상태에서 새로운 프로그램이나 데이터를 주기억장치에 배치하려고 할 때, 이미 사용되고 있는 영역 중에서 어느 영역을 교체하여 사용할 것인지를 결정하는 전략

종류 : FIFO, OPT, LRU, LFU, NUR, SCR 등..

가상 기억장치

가상기억장치는 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것이다.
용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법이다.

- 프로그램을 여러 개의 작은 블록 단위로 나누어서 가상기억장치에 보관해 놓고, 프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리한다.
- 주기억장치의 용량보다 더 큰 프로그램을 실행하기 위해 사용한다.
- 주기억장치의 이용률과 다중 프로그래밍의 효율을 높일 수 있다.
- 가상기억장치에 저장된 프로그램을 실행하려면 가상기억장치의 주소를 주기억장치의 주소로 바꾸는 주소 변환 작업이 필요하다.
- 블록 단위로 나누어 사용하므로 연속 할당 방식에서 발생할 수 있는 단편화를 해결할 수 있다.
- 가상기억장치의 일반적인 구현 방법에는 블록의 종류에 따라 페이징 기법과 세그먼테이션 기법으로 나눌 수 있다.

페이징(Paging) 기법

가상 기억장치에 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 나눠진 프로그램(페이지)을 동일하게 나눠진 주기억장치의 영역(페이지 프레임)에 적재시켜 실행하는 기법이다.

- 프로그램을 일정한 크기로 나눈 단위를 페이지(Page)라고 하고, 페이지 크기로 일정하게 나누어진 주기억장치의 단위를 페이지 프레임(Page Frame)이라고 한다.
- 외부 단편화는 발생하지 않으나 내부 단편화는 발생할 수 있다.
- 주소 변환을 위해서 페이지의 위치 정보를 가지고 있는 페이지 맵 테이블(Page Map Table)이 필요하다.
- 페이지 맵 테이블 사용으로 비용이 증가되고, 처리 속도가 감소된다.

세그먼테이션(Segmentation) 기법

가상 기억장치에 보관되어 있는 프로그램을 다양한 크기와 논리적인 단위로 나눈 후 주기억장치에 적재시켜 실행시키는 기법이다.

- 프로그램을 배열이나 함수 등과 같은 논리적인 크기로 나눈 단위를 세그먼트라고 하며, 각 세그먼트는 고유한 이름과 크기를 갖는다.
- 기억장치의 사용자 관점을 보존하는 기억장치 관리 기법이다.
- 외부 단편화가 발생할 수 있다.
- 세그먼테이션 기법을 이용하는 궁극적인 이유는 기억공간을 절약하기 위해서이다.
- 주소 변환을 위해서 세그먼트가 존재하는 위치 정보를 가지고 있는 세그먼트 맵 테이블(Segment Map Table)이 필요하다.
- 세그먼트가 주기억장치에 적재될 때 다른 세그먼트에게 할당된 영역을 침범할 수 없으며, 이를 위해 기억장치 보호키(Storage Protection Key)가 필요하다.

워킹 셋 (Working Set)

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

---

구역성 (Locality)

- 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론이다.
- 시간 구역성 : 한 번 참조한 페이지는 가까운 시간 내에 계속 참조할 가능성이 높음을 의미한다.
- 공간 구역성 : 어느 하나의 페이지를 참조하면 그 근처의 페이지를 계속 참조할 가능성이 높음을 의미한다.

페이지 교체 알고리즘

페이지 부재(Page Fault)가 발생하면 가상기억장치에서 필요한 페이지를 찾아 주기억장치에 적재해야 하는데, 이때 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법이 페이지 교체 알고리즘이다.

종류 : OPT, FIFO, LRU, LFU, NUR, SCR 등..

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

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

문제 1. 다음의 참조 페이지를 세 개의 페이지 프레임을 가진 기억장치에 FIFO 알고리즘을 사용하여 교체했을 때 페이지 부재의 수는? (단, 초기 페이지 프레임은 모두 비어 있는 상태이다.)

페이지 부재의 수 : 6번

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

문제 1. 참조 페이지를 세 개의 페이지 프레임을 가진 기억장치에서 LRU 알고리즘을 사용하여 교체했을 때 페이지 부재의 수는? (단, 초기 페이지 프레임은 모두 비어있는 상태이다.

페이지 부재의 수 : 5번

LFU (Least Frequently Used)
- 사용 빈도가 가장 적은 페이지를 교체하는 기법이다.
- 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용된다.

NUR (Not Used Recently)
- LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법이다.
- 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로 LRU에서 나타나는 시간적인 오버헤드를 줄일 수 있다.
- 최근의 사용 여부를 확인하기 위해서 각 페이지마다 두 개의 비트, 즉 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)가 사용된다.
- 다음과 같이 참조 비트와 변형 비트의 값에 따라 교체될 페이지의 순서가 결정된다.

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