기억장치 관리

기억장치는 주기억장치, 보조기억장치, 캐시 기억장치, 가상기억장치 등을 일컫는 말.

기억장치는 계층 구조를 가진다.

기억장치 계층 구조의 특징

계층 구조에서 상위의 기억장치 일수록 접근 속도와 접근 시간이 빠르다. 기억 용량이 적고 고가.

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

레지스터, 캐시, 주기억장치의 프로그램과 데이터는 CPU가 직접 액세스 할 수 있으나

보조기억장치에 있는 프로그램이나 데이터는 직접 액세스 할수  없다.

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

기억장치의 관리 전략

반입(Fetch) 전략

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

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

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

배치(Placement) 전략

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

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

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

*단편화 - 주기억장치의 분할된 영역에 프로그램이나 데이터를 할당할 경우 분할된 영역이 프로그램이나 데이터보다 작거나 커서 생기는 빈 기억공간을 의미한다.

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

교체(Replacement) 전략

주기억장치의 모든 영역이 이미 사용중인 상태에서 새로운 프로그램이나 데이터를 주기억장치에 배치하려고 할 때,

이미 사용되고 있는 영역 중에서 어느 영역을 교체하여 사용할 것인지를 결정하는 전략.

FIFO, OPT, LRU, LFU, NUR, SCR 등이 있다.

주기억장치 할당 기법

단일 분할 할당 기법

주기억장치를 운영체제 영역과 사용자 영역으로 나누어 한 순간에 오직 한 명의 사용자만이

주기억장치의 사용자 영역을 사용하는 기법이다.

- 두 영역을 구분해주는 경계 레지스터가 사용된다.

- 프로그램의 크기가 작으면 사용자 영역이 낭비된다.

- 주기억장치보다 큰 프로그램은 실행할 수 없었다. (오버레이 기법으로 해결)

오버레이(Overlay) 기법

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

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

적재하여 프로그램을 실행한다.

- 프로그램이 실행되면서 주기억장치의 공간이 부족하면 주기억장치에 적재된 

프로그램의 조각 중 불피룡한 조각이 위치한 장소에 새로운 프로그램의 조각을 중첩하여 적재한다.

- 프로그램을 여러 개의 조각으로 분할하는 작업은 프로그래머가 수행해야 하므로 프로그래머는 

시스템 구조나 프로그램 구조를 알아야 한다.

스와핑(Swapping) 기법

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

- 주기억장치에 잇는 프로그램이 보조기억장치로 이동되는 것을 Swap out, 보조기억장치에 있는 프로그램이 주기억장치로 이동하는 것을 Swap in이라고 한다.

- 하나의 사용자 프로그램이 완료될 때까지 교체 과정을 여러 번 수행할 수 있다.

- 가상기억장치의 페이징 기법으로 발전되었다.

다중 분할 할당 기법

고정 분할 할당 기법 = 정적 할당 기법

사용자 영역을 여러 개의 고정된 크기로 분할하고 준비상태 큐에서 준비중인 프로그램을 각 영역에 할당하는 기법

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

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

- 단편화가 심하다.

- 실행할 프로그램의 크기를 미리 알아야 한다.

- 현재는 사용되지 않음.

가변 분할 할당 = 동적 할당 기법

미리 주기억장치를 분할해 놓는 것이 아니라 프로그램을 주기억장치에 적재하면서 필요한 만큼의 크기로 영역을 분할하는 기법.

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

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

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

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

단편화

Fragmentation은 분할된 주기억장치에 프로그램을 할당하고 반납하는 과정을 반복하면서 사용되지 않고

남는 기억장치의 빈 공간 조각을 의미한다.

내부 단편화(Internal Fragmentaion) - 분할된 영역이 할당된 프로그램의 크기보다 크기 때문에 프로그램이 할당 된 후 사용되지

않고 남아 있는 빈 공간.

외부 단편화(External Fragmentation) - 분할된 영역이 할당될 프로그램의 크기보다 작기 때문에 프로그램이 할당될 수 없어

사용되지 않고 빈 공간으로 남아 있는 분할된 전체 영역

단편화 해결 방법

주기억장치를 재사용할 수 있도록 단펴화된 공간을 모아 하나의 사용할 수 있는 공간으로 만드는 기법. 통합과 압축.

통합(Coalescing) 기법

- 주기억장치 내에 인접해 있는 단편화된 공간을 하나의 공간으로 통합하는 작업을 의미한다.

압축(Coompaction) 기법

- 주기억장치 내에 분산되어 있는 단펴화된 빈 공간을 결합하여 하나의 큰 가용 공간을 만드는 작업을 의미한다.

- 집약, 가비지 컬렉션이라고도 한다.

- 압축이 실행되는 동안 시스템은 모든 일을 일시 중단한다.

가상기억장치 구현 기법

가상기억장치는 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것으로,

용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법.

프로그램을 여러개의 작은 블록단위로 나누어 가상 기억장치에 보관해놓고,

프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리한다.

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

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

가상 기억장치에 저장되 프로그램을 실행하려면 가상기억장치의 주소를 주기억장치의 주소로 바꾸는 주소 변환 작업이 필요하다.

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

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

페이징 기법 - 프로그램을 동일한 크기로 나눈 단위를 페이지라 하며 이 페이지를 블록으로 사용하는 기법

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

페이징 기법

- 프로그램을 일정한 크기로 나눈 단위를 페이지(Page)라고 하고 페이지 크기로 일정하게 나누어진

주기억장치의 단위를 페이지 프레임(Page Frame)이라고 한다.

- 외부 단편화는 발생하지 않으나 내부 단편화는 발생할 수 있다.

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

- 페이지 맵 테이블 사용으로 비용이 증가되고, 처리 속도가 감소한다.

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

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

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

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

페이지 맵 테이블 : 디스크 | 페이지 프레임 번호 | 상태 비트

주소 변환 순서

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

만들어진 실기억 주소를 이용하여 주기억장치를 액세스 한다.

  

*페이지폴트(Page Fault)

프로그램 실행 시 참조할 페이지가 주기억장치에 없는 현상을 의미한다.

페이지 폴트 처리 순서

운영체제에서 트랩 요청 - 사용자 레지스트리와 프로그램의 상태 저장 - 현재 사용 가능한 페이지를 페이지 맵 테이블에서 검색

- 가상기억장치에 있는 페이지를 주기억장치로 가져옴 - 페이지 맵 테이블 갱신 - 프로그램 상태를 불어와 계속 작업을 진행

세그먼테이션(Segmentation) 기법

- 가상기억 장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후 

주기억 장치에 적재시켜 실행시키는 기법

프로그램을 배열이나 

- 프로그램을 배열이나 함수 등과 같은 논리적인 크기로 나눈 단위를 세그먼트라고 한다. 

각 세그먼트는 고유한 이름과 크기를 갖는다.

- 기억장치의 사용자 관점을 보존하는 기억장치 관리 기법이다.

- 궁극적인 이유 : 기억공간을 절약하기 위해

- 주소 변환을 위해 세그먼트가 존재하는 위치 정보를 가지고 있는 세그먼트 맵 테이블(Segment Map Table)이 필요하다.

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

- 내부 단편화는 발생하지 않으나 외부 단편화는 발생할 수 있다.

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

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

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

세그먼트 맵 테이블 : 세그먼트 번호(s) | 세그먼트 크기(L) | 기준번지(d)

주소 변환 순서

- 가상주소의 세그먼트 번호로 세그먼트 맵 테이블에 해당 세그먼트의 기준번지와 세그먼트 크기를 구한다.

- 가상주소의 변위값과 세그먼트의 크기를 비교한다.

- 변위값이 작거나 같으면 기준번지의 변위값을 더하여 실기억 주소를 ㅁ나들어 주기억장치를 액세스한다.

- 변위값이 크면 다른 영역을 침범하게 되므로 실행 권한을 운영체제에게 넘기고 트랩을 발생시킨다.(한계 범위 초과)

페이지 교체 알고리즘

OPT(Optimal replacement, 최적 교체)

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

- 페이지 부재 횟수가 가장 적게 발생하는 효율적인 알고리즘

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

FIFO

가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법.

LRU(Least Recently Used)

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

- 각 페이지마다 계수기나 스택을 두어 현 시점에서 가장 오랫동안 사용하지 않은 페이지를 교체한다.

- 계수기나 스택과 같은 별도의 하드웨어가 필요하고 시간적인 오버헤드가 발생한다. 실제로 구현하기도 매우 어렵다.

LFU(Least Frequntly Used)

가장 빈도가 적은 페이지를 교체하는 기법.

- 활방하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않는다.

NUR(Not Used Recently)

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

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

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

참조 비트    변형 비트    교체순서

0             0             1

0             1             2

1             0             3

1             1             4

SCR(2차 기회 교체)

가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기  위한 것으로,

FIFO 기법의 단점을 보완하는 기법.

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

페이지 크기

작을 경우

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

- 불필요한 내용이 주기억장치에 적재될 확률이 적다.

- 기억장치 효율이 높다.

- 페이지 맵 테이블이 커지고 매핑 속도가 늦어진다.

- 디스크 접근 횟수가 많아져서 전체적인 입출력 시간이 늘어난다.

클 경우

- 페이지 맵 테이블 크기가 작아지고, 매핑 속도가 빨라진다.

- 디스크 접근 횟수가 줄어 입출력 효율성이 증가한다.

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

- 프로세스 수행에 불필요한 내용까지도 주기억장치에 적재

Locality

국부성, 지역성, 구역성, 국소성은 프로세스가 실행되는 동안 주기억장치를 참조할 때

일부 페이지만 집중적으로 참조하는 성질이 있다는 이론!

- 스래싱을 방지하기 위한 워킹 셋 이론의 기반이 되었다.

- 집중적으로 사용하는 페이지를 알아내느 방법 중 하나로 가상기억장치 관리의 이론적 근거가 됨.

- 캐시 메모리 시스템의 이론적 근거

종류

시간 구역성(Temporal Locality)

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

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

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

공간 구역성(Spatial Locality)

- 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상이다.

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

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

워킹 셋(Working Set)

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

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

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

페이지 부재 빈도 방식

페이지 부재 빈도(PFF; Page Fault Frequency)는 페이지 부재가 일어나는 횟수를 의미.

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

프리페이징(Prepaging)

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

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

스래싱(thrashing)

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

- 다중 프로그래밍 시스템이나 가상기억장치를 사용하는 시스템에서 

하나의 프로세스 수행 과정 중 자주 페이지 부재가 발생함으로써 나타나는 현상이다.

- 다중 프로그래밍의 정도가 높아짐에 따라 CPU의 이용률은 어느 특정 지점까지 높아지지만,

다중 프로그래밍의 정도가 더욱 커지면 스래싱이 나타나고 CPU의 이용률이 급격히 감소한다.

스래싱 현상 방지 방법

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

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

- Working Set을 유지한다.

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

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

디스크 스케줄링

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

사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 경우 데이터를 액세스하기 위해 

디스크 헤드가 움직이는 경로를 결정하는 기법.

FCFS

SSTF(Shortest Seek Time First)

- 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법.

- 바깥쪽에 있는 경우 무한정 기다려야 하는 문제가 발생(응답 시간 편차가 너무 커짐)

SCAN

- SSTF가 갖는 탐색 시간 편차 문제를 해소

- 진행방향을 정하고 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청을 서비스하고, 

끝까지 이동 후 역방향으로 서비스하는 기법.

C-SCAN(Circular SCAN)

- SCAN의 원형 형태(시작과 끝이 인접)

N-step SCAN

- SCAN 기법의 무한 대기 발생 가능성을 제거. 어떤 방향의 진행이 시작될 당시에 대기 중이던 요청들만 서비스하고,

진행 도중 도착한 요청들은 한데 모아서 다음 반대 방향 진행 때 서비스하는 기법.

에션바흐(Eschenbach)기법

- 부하가 큰 항공 예약 시스템을 위해 개발되었다.

- C-SCAN처럼 움직이며 예외적으로 모든 실린더는 그 실런더에 요청이 있던 없던 간에 전체 트랙이

한 바퀴 회전할 동안에 서비스를 받는다.

SLTF(Shortest Latency Time Fisrt)

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

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

- 헤드의 이동이 거의 없는 고정 헤드 장치인 드럼과 같은 장치에서 사용된다.