[운영체제/OS] 기억 장치의 관리 전략

4 분 소요

<h1 id="기억-장치-관리-전략의-종류">기억 장치 관리 전략의 종류</h1>
<h2 id="반입-전략fetch-strategy">반입 전략(Fetch Strategy)</h2>
<p>프로그램/데이터를 주기억 장치로 가져오는 시기를 결정하는 전략(<code class="language-plaintext highlighter-rouge">When</code>)</p>

<h3 id="요구demand-반입">요구(Demand) 반입</h3>
<p>요구가 있을 때마다 주기억 장치로 옮기는 방식(응용 프로그램을 실행하는 것은 사용자의 요구에 의해 주기억 장치에 적재하는 것)</p>

<h3 id="예상anticipatory반입">예상(Anticipatory)반입</h3>
<p>앞으로 요구될 가능성이 큰 데이터 또는 프로그램을 예상하여 주기억 장치로 미리 옮기는 방법</p>

<p>가상 기억 장치를 사용하게 될 때 주로 사용되며 자주 사용하는 페이지는 미리 주기억 장치에 가져다 놓는다(<strong>워킹 셋, Working Set</strong>). 앞으로 사용할 가능성이 높은 페이지를 가져다 놓는다(<strong>지역성, Locality</strong>)</p>

<p>예상이 성공하면 프로그램의 <strong>실행 속도가 빨라</strong>지지만 <strong>실패하면 오버헤드가 발생</strong>한다</p>

<h2 id="배치-전략placement-strategy">배치 전략(Placement Strategy)</h2>
<p>주기억 장치에 프로그램/데이터의 위치를 정하는 전략(<code class="language-plaintext highlighter-rouge">Where</code>)</p>

<h3 id="최초-적합first-fit">최초 적합(First Fit)</h3>
<p>입력된 작업을 주기억 장치 내에서 <strong>작업을 수용할 수 있는 첫 번째 공백</strong>에 배치</p>

<h3 id="최악-적합worst-fit">최악 적합(Worst Fit)</h3>
<p>입력된 작업을 주기억 장치 내에서 가장 잘 맞지 않는 공백에 배치(주기억 장치 내의 여러 공백 각각에 대해서 <strong>프로세스 크기를 차감하여 그 결과값이 가장 큰 공백에 배치</strong>)</p>

<h2 id="교체재배치-전략replacement-strategy">교체(재배치) 전략(Replacement Strategy)</h2>
<p>주기억 장치 내의 빈 공간 확보를 위해 제거할 프로그램/데이터를 선택하는 전략(<code class="language-plaintext highlighter-rouge">What/How</code>)</p>

<h3 id="optoptimal-replacement-최적">OPT(OPTimal Replacement, 최적)</h3>
<p>페이지 사용 횟수를 정확히 예측하여 교체하는 방법</p>

<ul>
  <li>앞으로 가장 오랫동안 사용되지 않을 페이지와 교체한다(이론상 페이지 부재 횟수가 가장 적으므로 성공률이 크다)</li>
  <li>Belady의 알고리즘으로 <strong>가장 이상적이지만 실현 가능성이 희박</strong>하다</li>
</ul>

<h3 id="fifofirst-input-first-out">FIFO(First Input First Out)</h3>
<p>주기억 장치에 들어와 있는 페이지에 <strong>타임 스탬프</strong>를 찍어 그 시간을 기억하고 있다가 가장 <strong>먼저 들어와 있던 페이지를 교체</strong>하는 방법</p>

<ul>
  <li>주기억 장치 내에 <strong>가장 오래된 페이지와 교체</strong></li>
  <li>알고리즘이 가장 <strong>간단</strong>하지만 <strong>페이지 교체가 가장 많다</strong></li>
  <li><strong>Belady 모순</strong> : 프로세스에 할당된 페이지 프레임 수가 증가하면 페이지 부재의 수가 감소하는 것이 당연하지만 <strong>페이지 프레임 수가 증가</strong>할 때, 오히려 현실적으로 <strong>페이지 부재가 더 증가</strong>하는 모순 현상이 발생한다</li>
</ul>

<h3 id="lruleast-recently-used">LRU(Least Recently Used)</h3>
<p><strong>참조된 지 가장 오래된 페이지</strong>를 대체 대상으로 선정하여 현 시점에서 가장 오랫동안 사용하지 않은 페이지와 교체한다</p>

<ul>
  <li>각 페이지마다 <strong>계수기(시간 기억 영역)</strong>를 두어 사용하는 기법</li>
</ul>

<h3 id="lfuleast-frequently-used">LFU(Least Frequently Used)</h3>
<p>페이지별로 사용된 횟수를 기억할 참조 변수를 확보한 후에 페이지가 참조될 때마다 1씩 증가한다. 주기억 장치에 기억된 페이지 중 하나를 교체하려고 할 때 참조 변수에 기억된 값이 가장 적은 페이지를 교체 대상으로 선정하는 기법</p>

<h3 id="nurnot-used-recently">NUR(Not Used Recently)</h3>
<p>페이지 당 두 개의 <strong>정보비트(참조 비트, 변형 비트)</strong>를 이용하여 교체하는 방법</p>

<p><strong>참조 비트</strong>는 <strong>해당 페이지를 호출했는가를 파악</strong>하는 비트이고, <strong>변형 비트</strong>는 <strong>주기억 장치 내에 있던 페이지를 사용</strong>했는가의 의미로 사용하는 비트이다. 비트 값이 <code class="language-plaintext highlighter-rouge">1</code>이면 <strong>최근에</strong>, <code class="language-plaintext highlighter-rouge">0</code>이면 <strong>오래전</strong>으로 판단한다</p>

<h3 id="pffpage-fault-frequently">PFF(Page Fault Frequently)</h3>
<p>자주 사용하는 페이지들은 주기억 장치에 미리 적재하여 페이지 폴트가 최소가 되도록 해야 한다.</p>

<p>자주 사용하는 페이지의 집합을 <a href="/study/os-memory/#작업-집합working-set"><strong>워킹 셋</strong></a>이라고 하는데 PFF는 워킹 셋에 존재하는 페이지들을 관찰하여 최근에 자주 사용되고 있지 않은 페이지와 <strong>워킹 셋에 속하지 않은 페이지</strong> 중에 <strong>최근에 자주 사용하는 페이지와 교체</strong>하여 교체 효율을 향상시키는 기법</p>

<h3 id="second-chancefifo의-2차-기회-부여">Second Chance(FIFO의 2차 기회 부여)</h3>
<p>가장 먼저 입력되었던 페이지를 제거 대상으로 삼는 <strong>FIFO의 단점을 보완</strong>한 것으로 가장 오래된 페이지를 제거하기 전에 <strong>한 번의 기회를 더 주는</strong> 방식</p>

<p>각 페이지에 프레임을 <strong>FIFO 순</strong>으로 유지시키면서 LRU 근사 알고리즘처럼 <strong>참조 비트</strong>를 갖게 한다. 또한 가장 오래된 페이지를 다시 <strong>처음에 입력된 페이지로 되돌리기 위해서는 LRU의 계수기를 필요</strong>로 하게 된다.
(<strong>FIFO + LRU</strong>)</p>

<h2 id="주기억-장치의-할당과-회수">주기억 장치의 할당과 회수</h2>
<p>주기억 장치에 프로그램이 적재될 때 빈 공간이 있는지 또는 크기는 어느 정도인지 우선 파악해야 한다. 이러한 <strong>정보를 파악하여 표시</strong>해두면 프로그램이 <strong>신속하게 적재</strong>할 수 있게 된다</p>

<h3 id="연결된-리스트linked-list">연결된 리스트(Linked List)</h3>
<p>분할된 영역의 정보를 구조적인 변수로 확보하여 동적인 연결 구조인 링크드 리스트 구조로 관리</p>

<p>구조적 변수의 항목으로 P(프로그램이 존재, Process), H(비어 있음, Hole), 시작 위치, 크기, 연결 정보로 구성</p>

<p>배치 전략에서 사용하기 적합하며 <strong>추가 삭제가 용이하므로 통합, 압축에 효과</strong>적으로 이용될 수 있지만 <strong>검색 속도는 비트 맴보다 다소 느리다</strong></p>

<h3 id="버디-시스템buddy-system">버디 시스템(Buddy System)</h3>
<p>큰 버퍼들을 반복적으로 반으로 나누어 작은 버퍼들을 만들며(버디 : 버퍼가 나누어질 때 각 공간을 의미), 가능할 때마다 인접한 자유로운 버퍼들을 합치는 과정을 반복(<strong>2의 거듭제곱 값으로 메모리를 할당</strong>)</p>

<ul>
  <li>블록 사상(페이지, 세그먼트) 주소 양식
    <blockquote>
      <p>V = (B, D)<br />
B: Page, Segment 번호<br />
D: Displacement(Offset)</p>
    </blockquote>
  </li>
</ul>

<h3 id="블록페이지-세그먼트-주소-사상-기법-종류">블록(페이지, 세그먼트) 주소 사상 기법 종류</h3>
<ul>
  <li>
    <p><strong>직접 사상(Direct Mapping)</strong><br />
페이지 번호와 변위로 구성된 가상 주소 중 페이지 번호로 페이지 사상 표에서 구한 실기억 장치의 주소와 가상 주소 중의 변위를 실제 주소로 변환하는 방법을 갖는 페이지 사상 기법</p>

<ul>
      <li>모든 페이지 항목은 페이지 사상 테이블에 존재</li>
      <li>총 2번의 메모리 접근이 필요(주소 변환에 시간을 많이 소비하게 되는 방식)</li>
    </ul>
  </li>
  <li>
    <p><strong>연관 사상(Associative Mapping)</strong><br />
직접 사상은 페이지의 분할 개수가 많을수록 해당 페이지를 검색하는 시간이 많은 소요되며, 프로그램을 가상 기억 장치로 실행하게 될 때 페이지 교체 속도가 늦어져 전체 프로그램 실행 속도에 영향을 주게 된다</p>

<p>이러한 단점을 보완하기 위해 <strong>고속의 연관 메모리에 자주 사용하는 페이지만</strong> 혹은 현재 적재된 페이지 만을 기억시켜 속도를 향상시키는 방법</p>

<ul>
      <li>매핑된 값들을 캐쉬 메모리에 저장(프로세스 번호, 페이지 번호, 매칭된 메인 메모리의 주소가 함께 매칭되어 입력)</li>
      <li>연관 기억장치에 저장한 연관 사상표를 이용</li>
      <li>빠른 주소 변환 수행</li>
    </ul>
  </li>
  <li>
    <p><strong>연관/직접 사상(Set Associative Mapping)</strong><br />
연관 사상 기법으로 사용하게 될 때 모든 페이지의 정보를 기억하려면 값비싼 고속의 메모리를 많이 사용해야 하므로 비용의 낭비가 많다. 따라서 <strong>우선 연관 사상 기법</strong>으로 해당 페이지를 찾고, <strong>페이지가 존재하지 않으면 직접 사상 기법</strong>으로 검색하여 사용하는 방법</p>

기억 장치 관리 전략의 종류

반입 전략(Fetch Strategy)

프로그램/데이터를 주기억 장치로 가져오는 시기를 결정하는 전략(When)

요구(Demand) 반입

요구가 있을 때마다 주기억 장치로 옮기는 방식(응용 프로그램을 실행하는 것은 사용자의 요구에 의해 주기억 장치에 적재하는 것)

예상(Anticipatory)반입

앞으로 요구될 가능성이 큰 데이터 또는 프로그램을 예상하여 주기억 장치로 미리 옮기는 방법

가상 기억 장치를 사용하게 될 때 주로 사용되며 자주 사용하는 페이지는 미리 주기억 장치에 가져다 놓는다(워킹 셋, Working Set). 앞으로 사용할 가능성이 높은 페이지를 가져다 놓는다(지역성, Locality)

예상이 성공하면 프로그램의 실행 속도가 빨라지지만 실패하면 오버헤드가 발생한다

배치 전략(Placement Strategy)

주기억 장치에 프로그램/데이터의 위치를 정하는 전략(Where)

최초 적합(First Fit)

입력된 작업을 주기억 장치 내에서 작업을 수용할 수 있는 첫 번째 공백에 배치

초기 결정력이 가장 빠르나, 내부 단편화의 크기에 상관없이 단편화가 많이 발생

최적 적합(Best Fit)

입력된 작업을 주기억 장치 내의 공백 중에서 작업에 가장 잘 맞는 공백에 배치(주기억 장치 내의 여러 공백에 대해서 프로세스 크기를 차감하여 그 결과값이 가장 작은 공백에 배치)

내부 단편화가 가장 적게 발생하나, 검색 시간이 길어 결정력이 가장 느리다

최악 적합(Worst Fit)

입력된 작업을 주기억 장치 내에서 가장 잘 맞지 않는 공백에 배치(주기억 장치 내의 여러 공백 각각에 대해서 프로세스 크기를 차감하여 그 결과값이 가장 큰 공백에 배치)

교체(재배치) 전략(Replacement Strategy)

주기억 장치 내의 빈 공간 확보를 위해 제거할 프로그램/데이터를 선택하는 전략(What/How)

OPT(OPTimal Replacement, 최적)

페이지 사용 횟수를 정확히 예측하여 교체하는 방법

앞으로 가장 오랫동안 사용되지 않을 페이지와 교체한다(이론상 페이지 부재 횟수가 가장 적으므로 성공률이 크다)
Belady의 알고리즘으로 가장 이상적이지만 실현 가능성이 희박하다

FIFO(First Input First Out)

주기억 장치에 들어와 있는 페이지에 타임 스탬프를 찍어 그 시간을 기억하고 있다가 가장 먼저 들어와 있던 페이지를 교체하는 방법

주기억 장치 내에 가장 오래된 페이지와 교체
알고리즘이 가장 간단하지만 페이지 교체가 가장 많다
Belady 모순 : 프로세스에 할당된 페이지 프레임 수가 증가하면 페이지 부재의 수가 감소하는 것이 당연하지만 페이지 프레임 수가 증가할 때, 오히려 현실적으로 페이지 부재가 더 증가하는 모순 현상이 발생한다

LRU(Least Recently Used)

참조된 지 가장 오래된 페이지를 대체 대상으로 선정하여 현 시점에서 가장 오랫동안 사용하지 않은 페이지와 교체한다

각 페이지마다 계수기(시간 기억 영역)를 두어 사용하는 기법

LFU(Least Frequently Used)

페이지별로 사용된 횟수를 기억할 참조 변수를 확보한 후에 페이지가 참조될 때마다 1씩 증가한다. 주기억 장치에 기억된 페이지 중 하나를 교체하려고 할 때 참조 변수에 기억된 값이 가장 적은 페이지를 교체 대상으로 선정하는 기법

사용한 횟수가 가장 적은 페이지와 교체
사용한 횟수가 기억될 참조 변수를 각 페이지에 두어 사용

NUR(Not Used Recently)

페이지 당 두 개의 정보비트(참조 비트, 변형 비트)를 이용하여 교체하는 방법

참조 비트는 해당 페이지를 호출했는가를 파악하는 비트이고, 변형 비트는 주기억 장치 내에 있던 페이지를 사용했는가의 의미로 사용하는 비트이다. 비트 값이 1이면 최근에, 0이면 오래전으로 판단한다

PFF(Page Fault Frequently)

자주 사용하는 페이지들은 주기억 장치에 미리 적재하여 페이지 폴트가 최소가 되도록 해야 한다.

자주 사용하는 페이지의 집합을 워킹 셋이라고 하는데 PFF는 워킹 셋에 존재하는 페이지들을 관찰하여 최근에 자주 사용되고 있지 않은 페이지와 워킹 셋에 속하지 않은 페이지 중에 최근에 자주 사용하는 페이지와 교체하여 교체 효율을 향상시키는 기법

Second Chance(FIFO의 2차 기회 부여)

가장 먼저 입력되었던 페이지를 제거 대상으로 삼는 FIFO의 단점을 보완한 것으로 가장 오래된 페이지를 제거하기 전에 한 번의 기회를 더 주는 방식

각 페이지에 프레임을 FIFO 순으로 유지시키면서 LRU 근사 알고리즘처럼 참조 비트를 갖게 한다. 또한 가장 오래된 페이지를 다시 처음에 입력된 페이지로 되돌리기 위해서는 LRU의 계수기를 필요로 하게 된다. (FIFO + LRU)

주기억 장치의 할당과 회수

주기억 장치에 프로그램이 적재될 때 빈 공간이 있는지 또는 크기는 어느 정도인지 우선 파악해야 한다. 이러한 정보를 파악하여 표시해두면 프로그램이 신속하게 적재할 수 있게 된다

비트 맵(Bit Map)

분할된 기억 장치 영역의 정보를 0(사용하지 않음),1(영역 사용중)로 구분하며 분할된 블록의 크기가 크면 비트 맵 용량이 줄어든다

사용되지 않는 영역이 있거나 단편화가 발생해도 합병, 집약이 어려우며 사용 여부를 알아내기 위해 순차 검색만을 수행하므로 검색 속도가 느리다

연결된 리스트(Linked List)

분할된 영역의 정보를 구조적인 변수로 확보하여 동적인 연결 구조인 링크드 리스트 구조로 관리

구조적 변수의 항목으로 P(프로그램이 존재, Process), H(비어 있음, Hole), 시작 위치, 크기, 연결 정보로 구성

배치 전략에서 사용하기 적합하며 추가 삭제가 용이하므로 통합, 압축에 효과적으로 이용될 수 있지만 검색 속도는 비트 맴보다 다소 느리다

버디 시스템(Buddy System)

큰 버퍼들을 반복적으로 반으로 나누어 작은 버퍼들을 만들며(버디 : 버퍼가 나누어질 때 각 공간을 의미), 가능할 때마다 인접한 자유로운 버퍼들을 합치는 과정을 반복(2의 거듭제곱 값으로 메모리를 할당)

약간의 외부 단편화와 메모리 간결화를 하는 오버헤드를 가지고 있다
요청된 메모리가 작은 블록보다 조금 더 크면 메모리가 낭비된다

기억 장치의 주소 사상 방법

블록 사상(페이지, 세그먼트) 주소 양식

V = (B, D)
B: Page, Segment 번호
D: Displacement(Offset)

블록(페이지, 세그먼트) 주소 사상 기법 종류

직접 사상(Direct Mapping)
페이지 번호와 변위로 구성된 가상 주소 중 페이지 번호로 페이지 사상 표에서 구한 실기억 장치의 주소와 가상 주소 중의 변위를 실제 주소로 변환하는 방법을 갖는 페이지 사상 기법
- 모든 페이지 항목은 페이지 사상 테이블에 존재
- 총 2번의 메모리 접근이 필요(주소 변환에 시간을 많이 소비하게 되는 방식)
연관 사상(Associative Mapping)
직접 사상은 페이지의 분할 개수가 많을수록 해당 페이지를 검색하는 시간이 많은 소요되며, 프로그램을 가상 기억 장치로 실행하게 될 때 페이지 교체 속도가 늦어져 전체 프로그램 실행 속도에 영향을 주게 된다

이러한 단점을 보완하기 위해 고속의 연관 메모리에 자주 사용하는 페이지만 혹은 현재 적재된 페이지 만을 기억시켜 속도를 향상시키는 방법
- 매핑된 값들을 캐쉬 메모리에 저장(프로세스 번호, 페이지 번호, 매칭된 메인 메모리의 주소가 함께 매칭되어 입력)
- 연관 기억장치에 저장한 연관 사상표를 이용
- 빠른 주소 변환 수행
연관/직접 사상(Set Associative Mapping)
연관 사상 기법으로 사용하게 될 때 모든 페이지의 정보를 기억하려면 값비싼 고속의 메모리를 많이 사용해야 하므로 비용의 낭비가 많다. 따라서 우선 연관 사상 기법으로 해당 페이지를 찾고, 페이지가 존재하지 않으면 직접 사상 기법으로 검색하여 사용하는 방법
- 저렴한 비용으로 캐쉬나 연관 기억 장치의 장점을 이용하는 방식
- 국부성에 근거하여 최근에 가장 많이 참조된 페이지만 유지

Twitter Facebook LinkedIn

SG Yoo.