리눅스마스터 1급 : 리눅스 기억장치 관리

리눅스마스터 1급 : 리눅스 기억장치 관리

기억 장치 관리

기억 장치는 프로그램이나 데이터를 저장하는 부분이다.

프로그램이 실행되기 위해서는 반드시 주기억 장치에 적재되어야 하는데, 주기억 장치에 프로그램을 적재하기 위해서 메모리를 할당하는 방법을 살펴보고 각 방법의 특징, 장단점을 통해 여러 가지 알고리즘을 서로 비교․분석하도록 한다.

1) 기억 장치

기억 장치는 주기억 장치와 보조 기억 장치로 구분된다.

CPU가 프로그램과 데이터를 즉각적으로 실행하고 참조하기 위해서는 주기억 장치에 있어야 한다.

그러나 주기억 장치는 휘발성 메모리로 대량의 데이터를 장기적으로 보존할 수 없다.

따라서 많은 양의 프로그램과 데이터를 대량으로 저렴하게 저장하려면 보조 기억 장치(디스크, 테이프, 광디스크 등)를 사용해야 한다.

① 캐시 기억 장치의 개념캐시는 CPU와 주기억 장치의 사이에 위치해서 주기억 장치의 정보들을 고속으로 CPU에 제공하는 최상위 계층의 메모리이다.

최고속이지만 가격이 비싸고, 용량이 작다는 한계가 있다.

캐시의 특성들을 정리하면 다음과 같다.

∙접근 속도가 가장 빠르고 비싸다.

∙보통 주기억 장치보다 용량이 작다(최신 CPU의 경우 8MB 캐시도 장착된다)

∙주기억 장치의 일부 내용을 복사해 놓는다.

∙CPU가 실제적으로 참조하는 메모리이다.

∙기억 장치 중에서 최상위 단계의 메모리이다.

② 기억 장치 관리를 위한 요구 사항기억 장치를 관리하기 위해서는 프로그램의 적재 위치를 동적으로 변환하거나 특정 영역에 대한 엑세스를 제한하거나 공유하고, 정보 블록의 크기를 정하며, 미디어의 특성에 적합한 관리 기법이 필요하다.

이를 위해서 아래와 같은 기능이 요구된다.

∙재배치(Relocation) : 프로그램의 주소를 동적으로 재배치한다.

∙보호(Protection) : 다른 사용자의 영역을 허락없이 참조하는 것을 방지한다.

∙공유(Sharing) : 여러 프로세스들이 기억 장치의 특정 부분을 같이 참조한다.

∙논리 구조(Logical Organization) : 정보 블록의 크기가 일정한 모듈과 크기가 일정하지 않은 세그먼테이션으로 구성한다.

∙물리 구조(Physical Organization) :주기억 장치와 보조 기억 장치, 휘발성 메모리와 비휘발성 메모리로 특성이 구분된다.

③ 기억 장치 관리 기법기억 장치의 관리는 크게 보조 기억 장치에서 프로그램이나 데이터를 가져오는 기법에 관한 것과 엑세스한 내용을 주기억 장치에 적재하는 것, 새로운 프로그램이나 데이터를 적재하기 위해서 기존 페이지나 세그먼트를 제거하는 방법이 있다.

다음은 각 기법을 나열하고 간략하게 설명한 것이다.

∙호출 기법(Fetch) - 보조 기억 장치로부터 페이지나 세그먼트를 인출한다.- 종류 : 요구호출과 예상 호출

∙배치 기법(Placement)- 페이지나 세그먼트가 적재될 위치를 결정한다.- 종류 : 최초 적합, 최적 적합, 최악 적합

∙교체 기법(Replacement)- 페이지나 세그먼트 중의 하나를 제거한다.

- 페이지나 세그먼트를 교체하는 알고리즘의 종류 : Random, FIFO, LRU, LFU, NUR, Second chance, Locality

2) 분할 기억 장치 관리(Partitioned Memory Management)

프로그램이나 데이터를 적재할 때 기억 장치의 연속된 공간을 할당하는 것이 아니라 한 부분에 적재함으로써 하나의 시스템에 여러 개의 프로그램이 적재되어 실행될 수 있다.

여러 개의 프로그램을 시스템에 적재할 때 기억 장소의 분할과 관리에 대하여 살펴보도록 하자.

① 다중 연속 고정 분할 방법(Multiple Contiguous Fixed Partition)다중 프로그래밍 환경에서 절대 번역과 적재를 사용할 때 고정된 분할을 이용한다.

각 분할의 경계는 경계 레지스터가 하한과 상한의 주소를 가리키며 분할 영역의 크기를 나타낸다.

초기의 다중 프로그래밍에서는 다중 연속 분할 방법을 사용하였다.

② 다중 연속 가변 분할 방법(Multiple Contiguous Variable Partition)각 작업의 크기에 따라 분할 영역을 할당한다.

초기 분할 이후에는 주기억 장치에 작은 분할이 발생하므로 큰 기억 장소를 필요로 할 때 기억 장소 집약(Storage Compaction)이 필요하다.

③ 기억 장소 배치 기법(Storage Placement Strategy)시스템에 새로 적재되는 프로그램과 데이터를 주기억 장치의 어디에 배치할 것인지를 결정하는 것이 매우 중요한데 이것을 기억 장소 배치 기법이라고 한다.

ⓐ 최초 적합(First-Fit) 방법

가용 공간 중 수용할 수 있는 첫 번째 있는 기억 공간을 할당하는 방법이다.

∙평균적으로 비할당 영역을 찾는 데 약간만 찾아도 원하는 기억 공간을 찾을 수가 있다.

∙수행이 다 끝이 나서 다시 사용되지 않는 영역으로 되는 경우에 있어서 다른 사용되지 않는 영역과 인접해 있는지를 검토하는 데 편리하다.

∙기억 장소가 큰 것이 필요할 때의 요구를 만족시킬 수 있는 확률이 높게 된다.

∙가용 공간을 쪼개어 쓰는 일이 발생할 수 있다.

ⓑ 최적 적합(Best-Fit) 방법

가용 공간을 정렬하고 필요로 하는 공간과 같거나 수용 가능한 공간 중 가장 작은 것을 할당하는 방법이다.

∙장점

- 평균적으로 가용 공간을 반 정도만 찾으면 원하는 기억 장소가 나타난다.

- 가용 공간 중에서 크기가 가장 작은 기억 장소가 할당된다.

- First-Fit 방법과는 달리 큰 부분을 쪼개어 쓰는 일이 드물다.

∙단점

- 아주 적은 비할당 영역이 많이 생기게 된다.

- 가용 공간이 크기순으로 반드시 정렬되어 있어야 한다.

ⓒ 최악 적합(Worst-Fit) 방법

가용 공간을 내림차순으로 정렬하고 수용 가능한 공간 중 가장 큰 것을 할당하는 방법이다.

∙장점

- 가장 큰 기억 공간을 할당하므로 나중에 큰 기억 장소가 필요할 때 유용하다.

- 정렬된 가용 공간 중 가장 큰 첫 번째를 할당하므로 검색이 빠르다.

∙단점

- 가용 공간이 내림차순으로 정렬되어 있어야 한다.

- 기억 장소의 낭비가 발생한다.

3) 재배치 분할 기억 장치 관리

기억 장소를 할당하고 재할당하는 과정을 반복하면 수많은 파티션들로 인하여 작업을 할당하거나 처리하기 곤란할 정도로 아주 작은 기억 공간들이 많이 발생하게 된다.

이러한 작은 기억 장소를 조각(Fragment)라고 하는데 이것을 한 곳에 모아서 커다란 기억 공간으로 만들 필요가 있다.

이러한 작업을 압축(Compaction) 혹은 쓰레기 수집(Garbage Collection)이라고 한다.

① 압축(Compaction 또는 Recompaction)

분할된 기억 장소는 크기가 공간보다 작거나 같은 프로그램만 수용할 수 있으므로 필연적으로 할당되고 남은 부분인 작은 조각이 발생한다.

작은 조각들은 기억 장소로서 사용하기 어려울 정도로 작으므로 이것들을 한쪽으로 몰아주는 압축 작업을 거쳐야 사용 가능한 크기의 기억 공간이 만들어진다.

이러한 작업에 사용하지 않는 작은 찌꺼기를 기억 장소에 모은다는 의미에서 Garbage Collection이라고 한다.

② 재배치 레지스터 이용

재배치 레지스터는 다중 분할된 메모리를 관리하고 각 프로세스의 시작 주소와 경계에 대한 정보를 갖는다.

재배치 레지스터는 필요에 따라 분할 기억 장소의 경계를 나타내는 베이스-경계 재배치(Base-Bound Relocation) 레지스터의 값을 조정해서 프로세스의 적재 위치를 동적으로 재배치할 수 있다.

③ 집약의 장점과 단점

집약이란 압축 기법을 이용해서 산재된 조그만 기억 공간을 한데 모아서 사용 가능한 큰 기억 장소로 만드는 작업이다.

∙장점

- 작은 기억 공간을 모아서 큰 기억 장소를 만들 수 있다.

- 가변 분할에서 발생되는 조각(Fragment)을 없앨 수 있다.

∙단점

- 생산적으로 사용 가능한 시스템 자원을 소비한다.

- 집약하는 동안 시스템은 모든 작업을 중지해야 한다.

- 프로그램의 재배치 관련 정보의 유지 관리가 매우 복잡하다.

- 빠르게 교체되는 작업들의 기억 공간을 집약해서 얻는 이익보다 집약을 위해 소모되는 자원의 낭비가 더 크다.

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

프로세스에 의해 참조되는 주소를 주기억 장치에서 사용할 수 있는 주소와는 별개로 프로그램을 실행해야 할 부분만 컴퓨터에 적재하고 가상의 주소를 지정해서 마치 전체 프로그램이 모두 있는 것처럼 컴퓨터를 인식시킨다.

∙인위적 연속성(Artificial Contiguity) : 프로세스의 가상 주소 공간에서 연속인 주소가 실주소에서 연속일 필요가 없다.

∙가상 주소(Virtual Address) : 실행 프로세스가 참조하는 주소이다.

∙실주소(Real Address) : 주기억 장소에서 사용할 수 있는 주소이다.

∙가상 주소 공간(Virtual Address Space) : 실행 프로세스가 참조하는 가상 주소의 범위이다.

∙실주소 공간(Real Address Space) : 특정 컴퓨터에서 사용 가능한 실주소의 범위이다.

∙동적 주소 변환(DAT : Dynamic Address Translation) : 프로세스가 실행되는 동안 가상 기억 장소의 위치가 실기억 장치의 어디에 위치하는지 변환하는 과정이다.

∙가상 기억 공간을 구현하기 위한 알고리즘 : 가상 기억 공간을 구현하기 위해 특정한 소프트웨어 알고리즘이 필요하며, 운영체제 소프트웨어에서는 기본적으로 다음의 3가지가 처리되어야 한다.

- 작업표(JT : Jop Table)- 메모리 블록(MBT : Memory Block Table)- PMT(Page Map Table)

① 페이지 기억 장치 관리(Paged Memory Management)

가상 기억 공간을 구현하기 위하여 메모리를 일정한 크기의 페이지 프레임(Page Frame)으로 분할하고 페이지 맵(Page Map)을 이용해서 실제 주소 공간을 가상 주소 공간과 사상(Mapping)시키는 관리 기법이다.

페이지 기억 장치 관리 기법은 메모리의 조각화의 염려가 없고, 연산에 의해서 기억 장소를 구할 수 있지만 페이지 적재와 교체가 빈번한 페이지 스레딩과 내부 단편화(Fragmentation)의 문제가 있으며 관련된 용어 몇 개념은 아래와 같다.

∙블록(Block) : 사상의 수를 줄이기 위하여 인위적으로 구성한 정보의 분할 단위이다.

∙페이지(Page) : 블록의 크기가 일정한 블록이다.

∙페이징(Paging) : 페이지를 이용한 가상 기억 장소 구성 방법이다.

∙페이지 사상(Page Mapping) : 페이지를 이용한 가상 기억 장소와 실기억 장소의 주소 변환 방법이다.

∙변위(Displacement) : 블록의 시작 부분부터 항목까지의 상대적인 주소이다.

∙PMT(Page Map Table) : 페이지 블록들의 목록이 작성된 리스트이다.

② 세그먼트 기억 장치 관리(Segmented Memory Management)

페이지 기억 장치 관리가 고정된 크기의 페이지 프레임을 사용하는 방법에 비해 세그먼트 기억 장치 관리는 크기가 다른 세그먼트 프레임을 사용하는 방법이다.

페이지 프레임에 비하여 크기가 융통성이 있어 내부 단편화 현상을 줄일 수 있고 세그먼트 맵을 이용해서 고속으로 주소를 계산할 수 있다.

다만, 세그먼트의 크기가 모두 다를 수 있으므로 세그먼트 크기에 대한 정보를 별도로 관리해야 하고, 빈번한 세그먼트 적재와 교체가 발생할 수 있다.

∙세그먼트(Segment) : 정보 블록의 크기가 다른 블록이다.

∙세그먼트 기법(Segmentation) : 세그먼트를 이용한 가상 기억 장소 구성 방법이다.

∙기억 장치 보호키(Storage Protection Key) : 블록의 크기가 달라서 다른 사용자 영역을 참조하는 것을 막기 위하여 경계 레지스터 대신 사용자별로 고유한 CPU 기억 장치 보호키를 이용하여 다른 영역에 대한 액세스를 방지한다.

∙액세스 제어의 형태는 판독(Read), 기록(Write), 수행(Execute), 첨가(Append)가 있다.

③ 세그먼트의 소프트웨어 알고리즘

페이지 기법이 일정한 크기의 페이지만 취급하여 내부 단편이 발생하고 빈번한 페이지 부재로 인한 적재와 교체로 스레싱이 발생해서 속도가 저하되는 문제를 발생시키는 것에 대해, 세그먼트 기법은 이러한 문제를 해결할 수 있다.

세그먼트 기법의 특징은 다음과 같다.

∙단편화 제거

∙가상 기억 장치 제공

∙동적 증가 세그먼트 허용

∙동적 연결과 코드

∙공유 세그먼트(Shared Segment)

∙통제 접근

④ 요구 세그먼트 방법

해당 세그먼트에 대한 액세스 요청이 있는 경우에만 세그먼트를 교체하는 방법이다.

사용자 프로그램이 매우 큰 경우에 유리하고, 세그먼트 부재가 발생해야 교체하므로 속도가 느리다.

∙장점사용자 프로그램이 실제 기억 장소보다 큰 경우에도 처리 가능하다.

∙단점- 가상 기억 장치가 구현하기 쉽지 않다.- 만약 부주의하게 이용되면 부수적으로 활용도가 감소된다.

⑤ 교환(Swapping)

페이지나 세그먼트를 서로 맞바꾸기 위한 알고리즘이 필요하다.

∙Roll-Out : 교체되는 페이지를 제거하는 것

∙Roll-In : 신규 페이지를 적재하는 것

∙문맥 교환(Context Switch) : 페이지를 서로 교체하기 위해 문맥을 저장하고 재적재하는 것

5) 요구 페이지 기억 장치 관리(Demand-Paged Memory Management)

기억 장소가 필요할 때 적절한 기억 장소를 제공하는 기법은 매우 중요하다.

기억 장치 관리 기법에 따라서 실행 속도가 매우 느리거나 비효율적인 것이 있다.

여기서는 필요할 것같은 페이지를 미리 예측해서 적재하는 것이 현실적으로 어렵고 예측이 곤란한 문제가 있으므로 필요가 발생하면 그때그때 필요로 하는 페이지만 적재하는 방법에 대한 소개를 하기로 한다.

① 요구 페이지 방법

특정 페이지에 대한 액세스 요구가 발생하면 그때 해당 페이지를 기억 장소에서 읽어들이는 방식이다.

다음은 요구 페이지 방법의 특성을 나열한 것이다.

∙페이지를 필요로 하는 시점에 해당 페이지를 주기억 장소에 적재한다.

∙프로그램의 수행에 최소한의 페이지로 실행 가능하다.

∙동일 기억 장소에 많은 프로그램을 실행시킬 수 있다.

∙해당 페이지의 적재 시점이 늦으므로 프로그램의 실행이 빠르지 못하다.

∙스레싱(Thrashing) : 빈번하게 페이지 폴트가 발생해서 해당 페이지의 Swaping으로 페이징이 매우 느려지는 현상이 발생한다.

② 요구 페이징의 활용도

요구 페이징은 페이지 기법에서 참조가 예측되는 페이지를 미리 가져오는 것이 기억 공간의 낭비가 심하고 예측이 불가능한 경우가 많으므로, 페이지에 대한 요구가 발생한 후 해당 페이지 프레임을 액세스하는 방법을 소개한다.

이 방법은 페이지 저장 공간을 최소화하므로 기억 장소의 낭비가 없고 최소의 공간에 최대의 프로그램을 실행할 수 있지만, 빈번하게 페이지 부재가 발생하고 실행 속도가 매우 느리다는 단점이 있다.

다음은 페이지 부재가 발생하는 순서를 기술한 것이다.

∙페이지 부재 인터럽트 신호 발생

∙인터럽트가 페이지 부재인지를 결정

∙페이지 참조가 합법적이고 디스크상에 페이지의 위치를 결정

∙디스크의 해당 페이지 블록을 Read 액세스

∙읽은 페이지 블록의 전송 시작

∙디스크에서 Read 전송 완료 인터럽트

∙인터럽트가 디스크에서 발생되는지를 결정

∙요구된 페이지가 지금 기억 장소에 있는지를 보기 위해서 PMT와 다른 테이블을 결정

∙사용자 레지스터들, 프로그램 상태와 새로운 PMT를 다시 저장하고 그때 인터럽트된 명령을 재개

6) 페이지 대체(Page Replacement) 알고리즘

페이지 대체 알고리즘은 페이지 부재가 발생할 때 새로운 페이지를 적재하기 위해서 기존의 페이지를 제거하는 알고리즘이다.

각 알고리즘에 따라서 페이지 부재 발생률과 Throughput이 다르고 장단점이 있으므로 신중하게 검토해야 한다.

① 최적화 원칙(Principle of Optimality)

∙가장 오랫동안 사용되지 않을 페이지를 교체한다.

∙최적성의 증명은 가능하지만 일어나지 않은 미래를 예측하는 것이 불가능하므로 최적화 알고리즘을 구현할 수 없다.

∙페이지 교체 기법이 얼마나 최적성을 갖고 있는지를 비교하여 사용한다.

② 무작위 페이지 교체(Random Page Replacement)

임의로 아무 페이지를 선택해서 교체하는 방법으로 알고리즘은 매우 간단하지만 바로 참조될 페이지 프레임을 제거할 가능성이 있다.

다음은 무작위 페이지 교체의 특성을 설명한 것이다.

∙임의의 페이지를 교체한다.

∙페이지 교체 알고리즘이 가장 간단하다.

∙모든 페이지가 교체될 가능성이 동등하다.

∙최악의 경우 바로 뒤에 참조될 페이지가 교체될 수 있다.

따라서 거의 사용하지 않는다.

③ FIFO(First-In First-Out)

먼저 적재된 페이지를 제거하는 알고리즘이다.

적재된 순차적으로 제거되므로 공평하고 일반적인 방법처럼 보이지만 가장 오래된 페이지가 가장 많이 참조될 가능성이 있으며, 페이지 프레임을 늘려도 페이지 부재(Page Fault)가 늘어날 가능성이 있다.

∙적재된 지 가장 오래된 페이지를 교체한다.

∙페이지 교체 알고리즘이 상당히 간단하고 쉽다.

∙가장 오랫동안 적재된 페이지가 사용될 가능성이 높으므로 바람직하지 못하다.

∙페이지 프레임의 수를 늘려도 페이지 부재가 오히려 늘어나는 문제가 발생한다.

④ LRU(Least Recently Used)

최근에 가장 적게 사용된 페이지를 제거하는 방법이다.

참조 페이지들의 사용 시간과 같은 정보를 관리하는 오버헤드가 있다.

다음은 일반적인 페이지 교체 알고리즘을 설명한 것이다.

∙최근에 가장 적게 사용된 페이지를 교체한다.

∙페이지들의 참조 시간을 관리하는 데 큰 오버헤드가 있다.

∙순환문의 경우 참조한 지 오래된 부분이 바로 뒤에서 참조할 페이지일 가능성이 높다.

∙페이지 엔트리와 시간 관리의 오버헤드로 인해서 잘 사용하지 않는다.

⑤ LFU(Least Frequently Used)

가장 적게 사용된 것을 삭제한다.

시간 관리가 필요 없이 단순히 사용 여부를 체크하면 되므로 훨씬 간단하고 단순하다.

∙가장 적게 사용된 페이지를 교체한다.

∙페이지의 참조 횟수만 관리하므로 알고리즘이 간단하고 쉽다.

∙최악의 경우는 가장 나중에 적재된 페이지가 계속 참조되어야 하는 데도 참조 횟수가 적다는 이유만으로 교체되는 문제가 발생한다.

⑥ NUR(Not Used Resently)

최근에 사용하지 않은 페이지를 제거하는 것이다.

최근에 사용하지 않은 페이지는 순환의 경우 곧 사용할 순서인 경우가 많다.

∙최근에 사용되지 않은 페이지를 교체한다.

∙최근에 사용되지 않은 페이지는 금방 사용될 가능성이 없으므로 LRU의 변형이다.

∙각 페이지마다 참조 비트와 변형 비트를 사용한다.

∙시간 관리를 위한 오버헤드가 적고 알고리즘이 비교적 간단하며 효율적이다.

∙모든 페이지가 변형된 경우는 임의의 페이지를 교체하게 된다.

⑦ 2차 기회(Second Chance)

첫 번째 페이지 부재가 발생하면 점과 같은 것으로 표시를 하고, 두 번째는 교체하는 방법이다.

첫 번째는 RR(round robin) 방식으로 순환, 그 후로는 일반 태그를 사용한다.

∙페이지를 단번에 교체하지 않고 태그를 한 번 셋팅하고 두 번째에 교체한다.

∙리스트를 이동하면서 RR 방식으로 순환하다가 두 번째 태그가 바뀌면 교체된다.

∙알고리즘이 비교적 단순하고 오버헤드가 적은 편이다.

⑧ 국부성(Locality)

프로그램이나 데이터는 인접한 부분이 집중적으로 참조될 가능성이 매우 높다.

따라서 공간적으로 인접하지 않은 곳의 프레임을 교체하는 방법이다.

다음은 국부성에 대한 특성이다.

∙정보의 액세스가 특정 부분을 집중적으로 액세스하는 것을 활용한 것이다.

∙실제로 나타나는 성질이며 인접한 페이지들은 교체 대상에서 제외하는 것이다.

∙국부성은 시간 국부성과 공간 국부성이 있다.

- 시간 국부성 : 순환, 서브루틴, 스택 등

- 공간 국부성 : 배열, 순차 실행 등