3장 기억장치 관리

정보처리기사 필기 - 3과목 운영체제

3장 기억장치 관리

090 기억장치 관리의 개요

① 기억장치 계층 구조의 특징

· 기억장치는 레지스터, 캐시 기억장치, 주기억장치, 보조기억장치를 다음과 같이 계층 구조로 분류

[그림 1] 기억장치 계층 구조

· 계층 구조가 상위의 기억장치일수록 접근 속도와 접근 시간이 빠르지만, 기억 용량이 적고 고가

· 주기억장치는 각기 자신의 주소를 갖는 워드 또는 바이트들로 구성되어 있으며, 주소를 이용하여 액세스 가능

· 레지스터, 캐시 기억장치, 주기억장치의 프로그램과 데이터는 CPU가 직접 액세스 가능, 보조기억장치에 있는 프로그램이나 데이터는 직접 액세스 불가능

· 보조기억장치에 있는 데이터는 주기억장치에 적재된 후 CPU에 의해 액세스될 수 있음

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

· 기억장치의 관리 전략은 보조기억장치의 프로그램이나 데이터를 주기억장치에 적재시키는 시기, 적재 위치 등을 지정하여 한정된 주기억장치의 공간을 효율적으로 사용하기 위한 것으로 반입(Fetch) 전략, 배치(Placement) 전략, 교체(Replacement) 전략

③ 반입(Fetch) 전략

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

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

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

④ 배치(Placement) 전략

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

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

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

(단편화 : 주기억장치의 분할된 영역에 프로그램이나 데이터를 할당할 경우, 분할된 영역이 프로그램이나 데이터보다 작거나 커서 생기는 빈 기억공간)

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

⑤ 교체(Replacement) 전략

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

· 교체 전략 : FIFO, OPT, LRU, LFU, NUR, SCR

091 주기억장치 할당 기법

① 주기억장치 할당의 개념

주기억장치 할당 기법은 프로그램이나 데이터를 실행시키기 위해 주기억장치에 어떻게 할당할 것인지에 대한 내용

연속 할당 기법	프로그램을 주기억장치에 연속으로 할당하는 기법으로, 단일 분할 할당 기법과 다중 분할 할당 기법 있음  · 단일 분할 할당 기법 : 오버레이, 스와핑  · 다중 분할 할당 기법 : 고정 분할 할당 기법, 동적 분할 할당 기법
분산 할당 기법	프로그램을 특정 단위의 조각으로 나누어 주기억장치 내에 분산하여 할당하는 기법으로, 페이징 기법과 세그먼테이션 기법으로 나눌 수 있음

② 단일 분할 할당 기법

단일 분할 할당 기법은 주기억장치를 운영체제 영역과 사용자 영역으로 나누어 한 순간에는 오직 한 명의 사용자만의 주기억장치의 사용자 영역을 사용하는 기법

· 가장 단순한 기법으로 초기의 운영체제에서 많이 사용하던 기법

· 운영체제를 보호하고, 프로그램이 사용자 영역만을 사용하기 위해 운영체제 영역과 사용자 영역을 구분하는 경계 레지스터가 사용됨

(경계 레지스터 : 사용자 영역에 있는 사용자 프로그램이 운영체제 영역에 접근하지 못하도록 보호하는 레지스터로, 사용자 영역이 시작되는 주소를 기억하고 있음)

· 프로그램의 크기가 작을 경우 사용자 영역이 낭비될 수 있음

· 초기에는 주기억장치보다 큰 사용자 프로그램은 실행할 수 없었으나 오버레이 기법을 사용하면서 이 문제 해겨로딤

오버레이(Overlay) 기법

오버레이 기법은 주기억장치보다 큰 사용자 프로그램을 실행하기 위한 기법

· 보조기억장치에 저장된 하나의 프로그램을 여러 개의 조각으로 분할한 후 필요한 조각을 차례로 주기억장치에 적재하여 프로그램 실행

· 프로그램이 실행되면서 주기억장치의 공간이 부족하면 주기억장치에 적재된 프로그램의 조각 중 불필요한 조각이 위치한 장소에 새로운 프로그램의 조각을 중첩(Overlay)하여 적재함

· 프로그램을 여러 개의 조각으로 분할하는 작업은 프로그래머가 수행해야 하므로 프로그래머는 시스템 구조나 프로그램 구조를 알아야 함

※ 오버레이 기법이 가능한 이유 : 하나의 프로그램을 여러 개의 조각으로 분할하여 처리할 수 있는 것은 프로그램의 모든 부분이 동시에 실행되는 것이 아니기 때문

스와핑(Swapping) 기법

스와핑 기법은 하나의 프로그램 전체를 주기억장치에 할당하여 사용하다 필요에 따라 다른 프로그램과 교체하는 기법

· 주기억장치에 있는 프로그램이 보조기억장치로 이동되는 것을 Swap Out, 보조기억장치에 있는 프로그램이 주기억장치로 이동하는 것을 Swap In이라고 함

· 하나의 사용자 프로그램이 완료될 때가지 교체 과정을 여러 번 수행 가능

· 가상기억장치의 페이징 기법으로 발점

③ 다중 분할 할당 기법

고정 분할 할당(Multiple contiguous Fixed parTition allocation, MFT) 기법 = 정적 할당(Static Allocation) 기법

고정 분할 할당은 프로그램을 할당하기 전에 운영체제가 주기억장치의 사용자 영역을 여러 개의 고정된 크기로 분할하고 준비상태 큐에서 준비중인 프로그램을 각 영역에 할당하여 수행하는 기법

· 프로그램을 실행하려면 프로그램 전체가 주기억장치에 위치해야 함

· 프로그램이 분할된 영역보다 커서 영역 안에 들어갈 수 없는 경우 발생 가능

· 일정한 크기의 분할 영역에 다양한 크기의 프로그램이 할당되므로 내부 단편화 및 외부 단편화가 발생하여 주기억장치의 낭비가 많음

· 실행할 프로그램의 크기를 미리 알고 있어야 함

· 다중 프로그래밍을 위해 사용되었으나 현재는 사용되지 않음

※ 내부 단편화 및 외부 단편화

· 내부 단편화 : 분할된 영역이 할당될 프로그램의 크기보다 크기 때문에 프로그램이 할당된 후 사용되지 않고 남아있는 빈 공간

· 외부 단편화 : 분할되 영역이 할당될 프로그램의 크기보다 작기 때문에 프로그램이 할당될 수 없어 사용되지 않고 빈 공간으로 남아 있는 분할된 전체 영역

가변 분할 할당(Multiple contiguous Variable parTition allocation, MVT) 기법 = 동적 할당(Dynamic Allocation) 기법

고정 분할 할당 기법의 단편화를 줄이기 위한 것으로, 미리 주기억장치를 분할해 놓는 것이 아니라 프로그램을 주기억장치에 적재하면서 필요한 만큼의 크기로 영역을 분할하는 기법

· 주기억장치를 효율적으로 사용할 수 있으며, 다중 프로그래밍의 정도를 높일 수 있음

· 고정 분할 할당 기법에 비해 실행될 프로세스 크기에 대한 제약이 적음

· 단편화를 상당 부분 해결할 수 있으나 영역과 영역 사이에 단편화가 발생할 수 있음

092 주기억장치 관리 기법의 문제점과 해결 방법

① 단편화

단편화(Fragmentation)는 분할된 주기억장치에 프로그램을 할당하고 반납하는 과정을 반복하면서 사용되지 않고 남는 기억장치의 빈 공간 조각을 의미하며, 내부 단편화와 외부 단편화가 있음

· 내부 단편화(Internal Fragmentation) : 분할된 영역이 할당될 프로그램의 크기보다 크기 때문에 프로그램이 할당된후 사용되지 않고 남아있는 빈 공간

· 외부 단편화(External Fragmentation) : 분할된 영역이 할당될 프로그래므이 크기보다 작기 떄문에 프로그램이 할당될 수 없어 사용되지 않고 빈 공간으로 남아 있는 분할된 전체 영역

② 단편화 해결 방법

· 주기억장치를 재사용할 수 있도록 단편화된 공간을 모아서 하나의 사용할 수 있는 공간으로 만드는 기법

통합(Coalescing) 기법

· 통합 기법은 주기억장치 내에 인접해 있는 단편화된 공간을 하나의 공간으로 통합하는 작업

· 주기억장치에 빈 공간이 발생할 경우 이 빈 공간이 다른 빈 공간과 인접되어 있는지 점검한 후 결합하여 사용

압축(Compaction) 기법

· 압축 기법은 주기억장치 내에 분산되어 있는 단편화된 빈 공간을 결합하여 하나의 큰 가용 공간을 만드는 작업, 집약 쓰레기 수집이라고도 함

· 여러 위치에 분산된 단편화된 공간을 주기억장치의 한 쪽 끝을 옮겨서 큰 가용 공간 만듦

· 압축이 실행되는 동안 시스템은 모든 일을 일시 중단함

093 가상기억장치 구현 기법

① 가상기억장치의 개요

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

· 프로그램을 여러 개의 작은 블록 단위로 나누어서 가상기억장치에 보관해 놓고, 프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리

· 주기억장치의 용량보다 큰 프로그램을 실행하기 위해 사용

· 주기억장치의 이용률과 다중 프로그래밍의 효율을 높일 수 있음

· 가상기억장치에 저장된 프로그램을 실행하려면 가상기억장치의 주소를 주기억장치의 주소로 바꾸는 주고 변환 작업 필요함

· 블록 단위로 나누어 사용하므로 연속 할당 방식에서 발생할 수 있는 단편화를 해결 가능

· 가상기억장치의 일반적인 구현 방법에는 블록의 종류에 따라 페이징 기법과 세그먼테이션 기법으로 나눌수 있음

페이징 기법	프로그램을 동일한 크기로 나눈 단위를 페이지라 하며 이 페이지를 블록으로 사용하는 기법
세그먼테이션 기법	프로그램을 가변적인 크기로 나눈 단위를 세그먼트라 하며, 이 세그먼트를 블록으로 사용하는 기법

※ 주소 변환

· 주소 변환은 가상기억장치에 있는 프로그램이 주기억장치에 적재되어 실행될 때 논리적인 가상주소를 물리적인 실기억주소로 변환하는 것으로, 주소 사상 또는 주소 매핑이라고 함. 이때 연속적인 가상주소가 반드시 연속적인 실기억주소로 변환되지 않아도 되는데, 이를 인위적 연속성이라고 함

· 가상주소는 보조기억장치에 있는 프로그램 상의 주소로 논리 주소라고 하며, 실기억주소는 주기억장치에 있는 기억공간의 주소로 실주소라고 함

② 페이징(Paging) 기법

페이징 기법의 개요

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

· 프로그램을 일정한 크기로 나눈 단위를 페이지라고 하며, 페이지크기로 일정하게나누어진 주기억장치의 단위를 페이지 프레임이라고 함

· 외부 단편화는 발생하지 않으나 내부 단편화는 발생할 수 있음

· 주소 변환을 위해서 페이지의 위치 정보를 가지고 있는 페이지 맵 테이블 필요함

· 페이지 맵 테이블 사용으로 비용 증가되고, 처리 속도 감소됨

페이징 기법의 일반적인 주소 변환

· 주소 형식에 따른 페이지 맵 테이블의 구성

- 가상주소는 페이지 번호를 나타내는 p와 페이지 내에서 실제 내용이 위치하고 있는 곳까지의 거리를 나타내는 변위값 d로 구성됨

가상주소 형식    [페이지번호(p) | 변위값(d)]

- 실기억주소는 페이지 프레임 번호를 나타내는 p'와 페이지 프레임 내에서 실제 참조하는 위치까지의 거리를 나타내는 변위값 d로 구성됨

실기억주소 형식    [페이지 프레임(p') | 변위값(d)]

- 페이지 맵 테이블은 사용할 페이지가 주기억장치에 존재하는지의 여부를 나타내는 상태 비트와 페이지가 주기억장치에 없을 때의 보조기억장치 주소를 나타내는 디스크 주소, 페이지가 주기억장치에 있을 때의 페이지 프레임 번호로 구성됨

페이지 맵 테이블    [디스크 주소 | 페이지 프레임 번호 | 상태 비트]

· 주소 변환 순서

① 가상주소의 페이지 번호에 해당하는 페이지 프레임 번호와 가상주소의 변위값을 이용하여 실기억주소 만듦

② 만들어진 실기억주소를 이용하여 주기억장치를 액세스함

③ 세그먼테이션(Segmentation) 기법

세그먼테이션의 개요

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

· 프로그램을 배열이나 함수 등과 같은 논리적인 크기로 나눈 단위를 세그먼트라고 하며, 각 세그먼트는 고유한 이름과 크기 가짐

· 기억장치의 사용자 관점을 보존하는 기억장치 관리 기법

· 세그먼테이션 기법을 이용하는 궁극적인 이유는 기억공간을 절약하기 위해서

· 주소 변환을 위해서 세그먼트가 존재하는 위치 정보를 가지고 있는 세그먼트 맵 테이블이 필요함

· 세그먼트가 주기억장치에 적재될 때 다른 세그먼트에게 할당된 영역을 침범할 수 없으며, 이를 위해 기억장치 보호키 필요

· 내부 단편화는 발생하지 않으나 외부 단편화는 발생할 수 있음

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

· 주소 형식에 따른 주소와 세그먼트 맵 테이블의 구성

- 가상주소는 세그먼트 번호를 나타내는 s와 세그먼트 내에서 실제 내용이 위치하고 있는 곳까지의 거리를 나타내는 변위값 d로 구성됨

가상주소 형식    [세그먼트 번호(s) | 변위값(d)]

- 실기억주소는 완전주소 형태를 사용하며 이는 세그먼트의 기준번지와 변위값을 더함으로써 얻을 수 있음

실기억주소 형식    [실기억주소(세그먼트 기준번지+변위값)]

- 세그먼트 맵 테이블은 세그먼트 번호 s와 세그먼트의 크기 L(한계 번지), 주기억장치 상의 기준번지(시작주소) b로 구성됨

세그먼트 맵 테이블    [세그먼트 번호(s) | 세그먼트 크기(L) | 기준 번지(b)]

· 주소 변환 순서

① 가상주소의 세그먼트 번호로 세그먼트 맵 테이블에서 해당 세그먼트의 기준번지와 세그먼트 크기를 구함. 세그먼트 번호는 세그먼트 맵 테이블에 대한 색인으로 사용됨

② 가상주소의 변위값과 세그먼트의 크기 비교

③ 변위값이 작거나 같으면 기준번지와 변위값을 더하여 실기억주소를 만들어 주기억장치 액세스함

④ 변위값이 크면 다른 영역을 침범하게 되므로 실행 권한을 운영체제에게 넘기고 트랩을 발생시킴(변위값이 크다는 것은 현재 찾는 세그먼트의 위치가 해당 세그먼트의 크기(한계번지)를 초과하였다는 의미)

094 페이지 교체 알고리즘

① 페이지 교체 알고리즘의 개요

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

· 페이지 교체 알고리즘 : OPT, FIFO, LRU, LFU, NUR, SCR

② OPT(OPTimal replacement, 최적 교체)

OPT는 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법

· 벨레이디(Belady)가 제안한 것으로, 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘

· 각 페이지의 호출 순서와 참조 상황을 미리 예측해야 하므로 실현 가능성 희박함

③ FIFO(First In First Out)

FIFO는 각 페이지가 주기억장치에 적재될 때마다 그때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

· 이해학 쉽고, 프로그래밍 및 설계 간단함

· 벨레이디의 모순현상 발생(페이지 프레임 수가 많으면 페이지 부재의 수가 줄어드는 것이 일반적이지만, 페이지 프레임 수를 증가시켰느데도 불구하고 페이지 부재가 더 많이 일어나는 현상을 의미

④ LRU(Least Recently Used)

LRU는 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

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

· 계수기나 스택과 같은 별도의 하드웨어 필요, 시간적인 오버헤드 발생

· 실제로 구현하기 매우 어려움

※ LRU에서 교체 페이지 선정 방법

· 최근에 가장 오랫동안 사용하지 않은 페이지를 쉽게 선정하려면, 현 시점가지 참조된 페이지 번호 순서를 거꾸로검사하여 중복되지 않고 가장 나중에 나타나는 페이지를 선택

※ LRU 근사 알고리즘

· LRU 알고리즘은 실제 구현하기 어렵기 때문에 시스템에서는 LRU와 비슷한 알고리즘을 사용하게 되는데, 이를 LRU 근사 알고리즘이라고 함

· LRU 근사 알고리즘은 참조 비트를 사용하는 것으로 다음에서 배울 NUR 등이 있음

⑤ LFU(Least Frequently Used)

LFU는 사용 빈도가 가장 적은 페이지를 교체하는 방법

· 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용됨

· 프로그램 실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않을 경우에도 프레임을 계속 차지할 수 있음

⑥ NUR(Not Used Recently)

NUR은 LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법

· 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로, LRU에서 나타나는 시간적인 오버헤드 줄일 수 있음

· 최근의 사용 여부를 확인하기 위해 각 페이지마다 두 개의 비트, 즉 참조 비트와 변형 비트가 사용됨

- 참조 비트 : 페이지가 호출되지 않았을 때는 0, 호출되었을 때는 1로 지정됨

- 변형 비트 : 페이지의 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1로 지정됨

⑦ SCR(2차 기회 교체)

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

· 각 페이지마다 참조 비트를 두고, FIFO 기법을 이용하여 페이지 교체 수행중 참조 비트가 0일 경우에는 교체하고, 참조비트가 1일 경우에는 참조 비트를 0으로 지정한 후 FIFO 리스트의 맨 마지막으로 피드백시켜 다음 순서를 기다리게 함

· 교체 대상이 되기 전에 참조 비트를 검사하여 1일 경우 한 번의 기회를 더 부여하기 때문에 'Second Chance'라고도 함

095 가상기억장치 기타 관리 사항

가상기억장치를 구현할 때 시스템의 성능에 영향을 미치는 페이지 크기나 Locality, 워킹 셋, 페이지 부재 빈도, 프리페이징에 대해 

① 페이지 크기

페이징 기법을 사용하면 프로그램을 페이지 단위로 나누게 되는데, 페이지의 크기에 따라 시스템에 미치는 영향이 다름

페이지 크기가 작을 경우

· 페이지 단편화가 감소되고, 한 개의 페이지를 주기억장치로 이동하는 시간이 줄어듦

· 불필요한 내용이 주기억장치에 적재될 확률이 적으므로 효율적인 워킹 셋을 유지할 수 있음

· Locality(국부성)에 더 일치할 수 있기 때문에 기억장치 효율이 높아짐

· 페이지 정보를 갖는 페이지 맵 테이블의 크기가 커지고, 매핑 속도가 늦어짐

· 디스크 접근 횟수가 많아져서 전체적인 입·출력 시간은 늘어남

페이지 크기가 클 경우

· 페이지 정보를 갖는 페이지 맵 테이블의 크기가 작아지고, 매핑 속도가 빨라짐

· 디스크 접근 횟수가 줄어들어 전체적인 입·출력의 효율성이 증가됨

· 페이지 단편화가 증가되고, 한 개의 페이지를 주기억장치로 이동하는 시간이 늘어남

· 프로세스(프로그램) 수행에 불필요한 내용까지도 주기억장치에 적재될 수 있음

② Locality

Locality(국부성, 지역성, 구역성, 국소성)는 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론

· 스래싱을 방지하기 위한 워킹 셋 이론의 기반이 됨

· 프로세스가 집중적으로 사용하는 페이지를 알아내는 방법 중 하나로, 가상기억장치 관리의 이론적인 근거가 됨

· Denning 교수에 의해 구역성의 개념이 증명되었으며 캐시 메모리 시스템의 이론적 근거

Locality의 종류

· 시간 구역성(Temporal Locality)

- 시간 구역성은 프로세스가 실행되면서 하나의 페이지를 일정 시간 동안 집중적으로 액세스하는 현상

- 한 번 참조한 페이지는 가까운 시간 내에 계속 참조할 가능성이 높음을 의미함

- 시간 구역성이 이루어지는 기억 장소 : Loop(반복, 순환), 스택(Stack), 부 프로그램(Sub Routine), Counting(1씩 증감), 집계(Totaling)에 사용되는 변수(기억장소)

· 공간 구역성(Spatial Locality)

- 공간 구역성은 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상

- 어느 하나의 페이지를 참조하면 그 근처의 페이지를 계속 참조할 가능성이 높음을 의미

- 공간 구역성이 이루어지는 장소 : 배열 순회, 순차적 코드의 실행, 프로그래머들이 관련된 변수(데이터를 저장할 기억장소)들을 서로 근처에 선언하여 할당되는 기억장소, 같은 영역에 있는 변수를 참조할 때 사용

③ 워킹 셋(Working Set)

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

· 데닝이 제안한 프로그램의 움직임에 대한 모델로, 프로그램의 Locality 특징을 이용함

· 자주 참조되는 워킹 셋을 주기억장치에 상주시킴으로써 페이지 부재 및 페이지 교체 현상이 줄어들어 프로세스의 기억장치 사용이 안정됨

· 시간이 지남에 따라 자주 참조하는 페이지들의 집합이 변화하기 때문에 워킹셋은 시간에 따라 변경됨

④ 페이지 부재 빈도 방식

페이지 부재(Page Fault)는 프로세스 실행 시 참조할 페이지가 주기억장치에 없는 현상이며, 페이지 부재 빈도는 페이지 부재가 일어나는 횟수

· 페이지 부재 빈도 방식은 페이지 부재율에 따라 주기억장치에 있는 페이지 프레임의 수를 늘리거나 줄여 페이지 부재율을 적정 수준으로 유지하는 방식

· 운영체제는 프로세스 실행 초기에 임의의 페이지 프레임을 할당하고, 페이지 부재율을 지속적으로 감시하고 있다가 부재율이 상한선을 넘어가면 좀 더 많은 페이지 프레임을 할당하고, 부재율이 하한선을 넘어가면 페이지 프레임을 회수하는 방식 사용

⑤ 프리페이징(Prepaging)

· 프리페이징은 처음의 과도한 페이지 부재를 방지하기 위해 필요할 것 같은 모든 페이지를 한꺼번에 프레임에 적재하는 기법

· 기억장치에 들어온 페이지들 중에서 사용되지 않는 페이지가 많을 수도 있음 

⑥ 스래싱(Thrashing)

스래싱은 프로세스의 처리 시간보다 페잊 교체에 소요되는 시간이 더 많아지는 현상

· 다중 프로그래밍 시스템이나 가상기억장치를 사용하는 시스템에서 하나의 프로세스 수행 과정 중 자주 페이지 부재가 발생함으로써 나타나는 현상으로, 전체 시스템의 성능이 저하됨

· 다중 프로그래밍의 정도가 높아짐에 따라 CPU의 이용률은 어느 특정 시점까지는 높아지지만 다중 프로그래밍의 정도가 더욱 커지면 스래킹이 나타나고, CPU의 이용률은 급격히 감소함

· 스래싱 현상 방지 방법

- 다중 프로그래밍의 정도를 적정 수준으로 유지

- 페이지 부재 빈도를 조절하여 사용

- Working Set 유지

- 부족한 자원을 증설하고, 일부 프로세스를 중단시킴

- CPU 성능에 대한 자료의 지속적 관리 및 분석으로 임계치를 예상하여 운영함

096 디스크 스케줄링

보조기억장치에는 자기 디스크, 광 디스크, 자기 테이프 등이 있으나 일반적으로 자기 디스크를 가장 많이 사용함

운영체제가 수행하는 디스크 스케줄링 기법의 개념과 종류에 대해

① 디스크 스케줄링의 개요

· 디스크 스케줄링은 사용할 데이터가 디스크 상의 여러곳에 저장되어 있을 경우 데이터를 액세스하기 위해 디스크 헤드가 움직이는 경로를 결정하는 기법

· 디스크 스케줄링은 일반적으로 탐색 기간을 최적화하기 위해 수행되며, 다음과 같은 목저글 갖고 있음

처리량 최대화	일정 시간에 디스크 입·출력 요구를 서비스해 주는 수를 최대화
응답 시간의 최소화	어떤 요청이 있은 후 결과가 나올 때가지 걸리는 시간을 최소화
응답 시간 편차의 최소화	각 요청의 응답 시간과 평균 응답 시간의 편차를 최소화

· 디스크 스케줄링의 종류에는 FCFS, SSTF, SCAN, C-SCAN, N-step SCAN, 에센바흐, STLF 스케줄링 기법이 있음

② FCFS(First Come First Service) = FIFO(First In First Out)

FCFS는 가장 간단한 스케줄링으로, 디스크 대기 큐에 가장 먼저 들어온 트랙에 대한 요청을 가장 먼저 서비스하는 기법

· 디스크 대기 큐에 있는 트랙 순서대로 디스크 헤드를 이동시킴

· 디스크 대기 큐에 들어온 순서대로 서비스하기 때문에 더 높은 우선순위의 요청이 입력되어도 순서가 바뀌지 않아 공평성이 보장됨

· 디스크 오버헤드가 적을 때 효율적이며, 프로그래밍이 쉬움

· 헤드 이동 거리가 상당히 길어질 수 있음

· 디스크 오버헤드가 커지면 응답 시간이 길어짐

· 탐색 시간을 최적화하려는 시도가 없는 기법

③ SSTF(Shortest Seek Time First)

SSTF는 탐색 거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법

· 현재 해드 위치에서 가장 가까운 거리에 있는 트랙으로 헤드를 이동시킴

· FCFS보다 처리량이 많고, 평균 탐색 시간이 짧음

· 처리량이 많은 일괄 처리 시스템에 유용

· 현재 서비스한 트랙에서 가장 가까운 트랙에 대한 서비스 요청이 계속 발생하는 경우, 먼 거리의 트랙(안쪽이나 바깥쪽)에 대한 서비스는 무한정 기다려야 하는 기아 상태가 발생할 수도 있음

· 응답 시간의 편차가 크기 때문에 대화형 시스템에는 부적합

④ SCAN

SCAN은 SSTF가 갖는 탐색 시간의 편차를 해소하기 위한 기법

· Denning이 개발한 것으로, 대부분의 디스크 스케줄링에서 기본 전략으로 이용됨

· 현재 헤드의 위치에서 진행 방향이 결저되면 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청을 서비스하고, 끝까지 이동한 후 역방향의 요청 사항을 서비스함

· 헤드가 안쪽과 바깥쪽을 왔다갔다 하면서 지나는 길에 있는 대기 요청뿐만 아니라 새로운 요청도 서비스하며, 현재의 진행 방향에 더 이상의 요청이 없을 때에만 이동방향 바꿈

· SSTF에서 발생하는 응답 시간의 편차를 줄일 수 있음

· 오버헤드가 적을 경우 가장 효율적인 기법

⑤ C-SCAN(Circular SCAN)

C-SCAN은 항상 바깥쪽에서 안쪽으로 움직이면서 가장 짧은 탐색 거리를 갖는 요청을 서비스하는 기법

· 헤드는 트랙의 바깥쪽에서 안쪽으로 한 방향으로만 움직이며 서비스하여 끝까지 이동한 후, 안쪽에 더 이상의 요청이 없으면 헤드는 가장 바깥쪽의 끝으로 이동한 후 다시 안쪽으로 이동하면서 요청 서비스함

· 마치 처음과 마지막 트랙을 인접시킨 것과 같은 원형 형태로 Disk를 처리함

· 요청을 서비스하는 도중 새로운 요청 사항이 도착하면 다음 헤드가 진행될 때 서비스 함

· 트랙의 안쪽과 바깥쪽의 요처엥 대한 서비스가 공평함

⑥ N-SCAN(N-step SCAN)

N-step SCAN은 SCAN 기법의 무한 대기 발생 가능성을 제거한 것으로, 어떤 방향의 진행이 시작될 당시에 대기 중이던 요청들만 서비스하고, 진행 도중 도착한 요청들은 한데 모아서 다음 반대 방향 진행 때 서비스하는 기법

· SSTF나 SCAN 기법보다 응답 시간의 편차가 적음

· 특정 방향에 많은 수의 요청이 도착할 경우 반대방향에서의 무한 지연 발생을 방지할 수 있음

· 진행 도중 도착한 요청은 반대 방향 진행시 서비스하기 위해 디스크 대기 큐에 저장

⑦ 에션바흐(Eschenbach) 기법

· 에센바흐는 부하가 매우 큰 항공 예약 시스템을 위해 개발됨

· 탐색 시간과 회전 지연 시간을 최적화하기 위한 최초의 기법

· 헤드는 C-SCAN처럼 움직이며 예외적으로 모든 실린더는 그 실린더에 요청이 있던 없던 간에 전체 트랙이 한 바퀴 회전할 동안에 서비스 받음

⑧ SLTF(Shortest Latency Time First)

SLTF는 섹터 큐잉이라고 하며, 회전 지연 시간의 최적화를 위해 구현된 기법

· 디스크 대기 큐에 있는 여러 요청을 섹터 위치에 따라 재정렬하고, 가장 가까운 섹터를 먼저 서비스

· 헤드의 이동이 거의 없는 고정 헤드 장치인 드럼과 같은 장치에서 사용됨

출처 : 2017 시나공 정보처리기사 필기