1. 가상 메모리의 개념 프로그램에 의해 빈 프레임은 부재된 페이지를 수용하기 위해 사용. 페이지 대치 과정. ① 디스크에서 요구한 페이지의 위치 확인. ② 빈 프레임을 찾음. - 빈 프레임이 발견되면 빈 프레임을 사용. - 빈 프레임이 발견되지 않으면 희생 프레임 선정을 위해 페이지 대치 알고리즘 사용. - 희생 페이지는 디스크에 기록하고 페이지와 프레임 테이블을 수정함. ③ 요구된 페이지를 읽어 들이고 페이지와 프레임 테이블을 수정. ④ 사용자 프로세스를 시작함. 페이지 부재로 인한 페이지 대치 과정은 페이지 부재 처리 시간이 증가(페이지 두개가 이동 . 하나는 나오고 다른 하나는 들어감)하는 결과를 가져와 액세스 시간이 증가하므로 시스템 에 부담이 됨. - 수정된 비트를 활용하여 부담을 감소시킬 수 있음. 페이지 대치는 요구 페이징의 기본 요소로 논리적 공간과 실제 메모리 공간을 완벽히 분리 해주므로 프로그래머는 작은 실제 메모리에서 매우 큰 가상 메모리(디스크)를 제공할 수 있음.

3. 페이지 대치 알고리즘 페이지 부재와 프레임 개수 참조 문자열을 이용한 페이지 부재 횟수와 프레임 개수와의 관계. 참조문자열은 메모리를 참조하는 페이지를 의미함. 프레임 수가 증가하면 페이지 부재수가 감소함. - 위의 참조 문자열에 대해 세 개 또는 그 이상의 프레임을 가진 경우, 총 3번의 페이지 부재 발생. - 한 프레임만 이용할 수 있는 경우 각 참조마다 페이지 대치가 필요하며 결과적으로 11번의 부재 발생. [그림 8-17] 페이지 부재와 프레임 개수 그래프. - 프레임 수가 증가함에 따라 페이지 부재의 수가 최소한도의 수준으로 내려감. [그림 8-17] 페이지 부재와 프레임 개수

3. 페이지 대치 알고리즘 선입선출(FIFO, First-In-First-Out) 대치 알고리즘 ※ 페이지 대치 알고리즘을 확인하기 위해 아래 참조 문자열을 프레임이 3개인 메모리에 사용함. 선입선출(FIFO, First-In-First-Out) 대치 알고리즘 각 페이지가 메모리 안으로 들어간 시간을 이용. 가장 오래된 페이지부터 우선 대치시킴. 페이지 부재 발생 시, 즉 제거해야 할 페이지 선택 후 보조기억장치로 이동 교체시키고 페이지 테이블의 타당/비타당 비트를 변경함. 새로운 페이지에 대한 페이지 테이블 항목 변경 후 FIFO 큐의 마지막 위치에 삽입. [그림 8-18] 선입선출(FIFO) 대치 알고리즘

3. 페이지 대치 알고리즘 선입선출 큐(FIFO Queue)에 의해 메모리의 모든 페이지가 관리됨. 큐의 헤드부분에 있는 페이지를 먼저 대치함. 보조기억장치에 있는 페이지가 메모리로 들어갈 때 큐의 끝에 페이지가 삽입. 큐의 크기는 사용 가능한 메모리 프레임의 수에 해당됨. [그림 8-19] 선입선출(FIFO) 대치 알고리즘의 실행 - 세 개의 프레임을 사용할 수 있다 가정하고 앞의 참조 문자열을 실행, 페이지 부재는 15번 발생함. [그림 8-19] 선입선출(FIFO) 대치 알고리즘의 실행 ※ 알고리즘의 이해가 쉽고 프로그램의 작성이 쉬움.

3. 페이지 대치 알고리즘 문제점. 벨레디의 변이(Belady’s Anomaly) 발생. - 프레임이 많으면 페이지 부재 횟수가 줄어드는 현상에 반대되는 현상이 나타남. - 즉, 할당되는 프레임의 수가 증가해도 페이지 부재율이 증가하는 현상. - 이로 인해 최적 페이지 대치 알고리즘을 추구하는 경향 발생. 아래의 참조 문자열을 적용하여 문제점 확인. - 프레임이 3개일 때보다 프레임이 4개일 때 페이지 부재가 많이 발생. [그림 8-20] 프레임별 실행결과

3. 페이지 대치 알고리즘 최적(Optimal) 페이지 대치 알고리즘 모든 알고리즘 중 페이지 부재율이 가장 낮음. ‘앞으로 가장 오랜 기간 동안 사용하지 않을 페이지를 대치하라’는 사상을 표현. 고정된 프레임 수에 대해 가능한 가장 낮은 페이지 부재율이 보장됨. [그림 8-22] 최적 페이지 대치 알고리즘. - 앞의 참조 문자열을 적용한 경우, 총 9번의 페이지 부재가 발생함. - 페이지 부재 15번을 일으키는 선입선출 대치 알고리즘보다 좋음. [그림 8-22] 최적 페이지 대치 알고리즘 ※ 현실적인 구현이 어려우며, 비교 연구를 위해 주로 사용됨. - 참조 문자열이 언제 사용될 것인가에 대한 정확한 정보를 요구하는데, 알기 어렵기 때문.

3. 페이지 대치 알고리즘 최근 최소사용(LRU, Least Recently Used) 알고리즘 과거의 데이터를 이용하여 미래를 예측하기 위한 통계적 개념. 메모리의 지역성을 이용한 알고리즘으로 각 페이지에 마지막으로 사용된 시간을 연관시킴. 페이지 대치 시, 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법. - 가장 최근에 사용되지 않는 페이지를 교체. - 시간적으로 거꾸로 찾는 최적 페이지 대치 알고리즘이라 할 수 있음. [그림 8-23] 최근 최소사용(LRU) 알고리즘. - 앞의 참조 문자열 적용 시, 12번의 페이지 부재를 일으킴. - 처음 5번의 부재 처리 과정은 최적 대치 알고리즘과 같으나, 이후 페이지 4에 대한 참조가 일어날 때 메모리 속 페이지 중 가장 늦게 사용한 페이지 2를 선택하여 대치함. - 만약 페이지 2에 부재 발생 시, {0, 3, 4} 중 가장 늦게 사용한 페이지 3으로 대치함. [그림 8-23] 최근 최소사용(LRU) 알고리즘 ※ 프레임(페이지)이 마지막에 사용된 기간을 이용하여 정의되는 순서 결정을 위해 계수기 또는 스택을 사용하는 두 가지 방법으로 구현 가능함.

3. 페이지 대치 알고리즘 계수기를 이용한 순서 결정 방법. 스택을 이용한 순서 결정 방법. 각 페이지 테이블 항목과 사용시간 레지스터를 연관시키고 프로세서에 논리 클록이나 계수 기를 덧붙여 프레임의 순서를 결정. - 페이지에 대한 참조가 있을 때마다 클록은 증가함. 클록 레지스터의 내용은 페이지의 해당 페이지 테이블에 있는 사용시간 레지스터에 복사되어 각 페이지의 최소 참조에 대한 시간을 가짐. - 가장 작은 시간 값을 가진 페이지가 대치됨. 페이지 탐색과 페이지 테이블의 변화 과정을 유지해야 하는 부담을 고려해야 함. 스택을 이용한 순서 결정 방법. 순서 결정을 위해 페이지 번호를 스택(Stack)에 넣어 관리. 페이지가 참조될 때마다 페이지 번호를 스택의 꼭대기(Top)에 둠. - 꼭대기(Top)에 있는 페이지 번호는 가장 최근 사용한 페이지가 되며, 밑바닥(Bottom)에 있는 페이지 번호는 가장 늦게 사용한 페이지가 되어 페이지 부재 시 교체됨. 필드 비교, 업데이트, 계수기 등의 처리 과정은 생략되나, 스택의 중간에서 항목을 가져오므로 이중 링크의 조작이 필요해 오버헤드를 증가시킬 수 있음. - 헤드와 꼬리 포인터를 가진 이중 연결리스트를 사용하여 해결 가능하므로 탐색시간 감소.

3. 페이지 대치 알고리즘 [그림 8-24] 최근의 페이지를 참조한 스택. - a 이전의 스택 정보는 꼭대기에 가장 최근에 사용한 페이지 2가 있으며, 밑 바닥에는 가장 오래 전에 사용한 페이지 4를 유지하고 있음. - b 이전의 스택에서는 꼭대기에 있는 페이지가 최근 사용한 페이지 7로 교체됨. [그림 8-24] 최근의 페이지를 참조한 스택 가장 최근에 사용한 페이지 가장 오래전에 사용한 페이지

3. 페이지 대치 알고리즘 최근 최소사용 근접 알고리즘 상당수 시스템이 하드웨어의 지원 대신 참조 비트(Reference Bit)의 형태로 지원. 대부분의 시스템들이 최근 최소사용 알고리즘을 이용한 페이지 대치에 대한 하드웨어 지원 을 하지 않기 때문에 다른 알고리즘을 사용. 처음 모든 bit는 0으로 초기화한 후 사용자 프로세스가 수행될 때 참조된 각 페이지와 관련된 bit를 1로 변환하여 어느 페이지가 사용되었는지 조사하여 확인 가능. 부가된 참조비트 알고리즘. 각 페이지에 8bit(1byte) 정보에 일정한 간격으로 참조 비트를 기록. 8bit Shift Register를 이용하여 순서 정보를 얻음. - 각 페이지에 대한 참조비트(1)를 최상위 bit(8bit 위, 가장 왼쪽)로 삽입 이동하고 나머지 bit들은 한 비트씩 오른쪽으로 이동시켜 가장 낮은 자리 bit는 제거함. 8bit Shift Register는 최근 8번의 기간 동안 페이지 사용의 기록 정보를 유지함. - Shift Register의 값이 ‘00000000’인 경우 8번의 기간 동안 단 한 번도 사용되지 않음을 의미함. - ‘11111111’은 기간마다 한 번씩 사용되었음을 의미함. - ‘11000100(19610)’은 ‘01110111(11910)’보다 최근 사용되었음을 의미함.

3. 페이지 대치 알고리즘 [그림 8-25] 부가된 참조비트 예. - ‘00001011(11)’이 가장 사용빈도가 낮아 페이지 대치 대상임. [그림 8-25] 부가된 참조비트 예 8bit를 부호 없는 정수로 해석할 경우 가장 낮은 bit를 가진 페이지는 최근 최소사용(LRU) 페이지(오랫동안 미사용 페이지)이며, 대치 가능함. 참조 비트의 내용이 동일한 경우 발생할 수 있음. - 모든 페이지 프레임이 갖는 참조 비트의 값이 유일하지 않기 때문에 발생함. 작은 정수값을 갖는 프레임이 두 개 이상 있는 경우 희생자 선정 시점에서 문제 발생. - 가장 작은 정수값을 갖는 프레임 모두를 희생자로 선택하거나 FIFO의 원칙에 따라 하나를 희생자로 선택함.

3. 페이지 대치 알고리즘 시계(2차적 기회 대치) 알고리즘. 선입선출(FIFO) 대치 알고리즘을 기반으로 함. 최근 최소사용(LRU) 알고리즘과 성능은 비슷하나 과부하가 적음. - 각 프레임의 사용여부를 나타내는 참조(사용)비트를 추가. - 페이지가 메모리 내의 프레임에 처음 적재되었을 때 1로 설정한 후, 참조될 때마다 다시 1로 설정. - 프레임들은 원형 버퍼(큐)로 구성되고 각각 관련 포인터를 가짐. - 페이지 교체 시 포인터는 교체된 버퍼 다음 프레임을 가리키도록 설정. 운영체제가 페이지 교체 시기에 참조비트가 0인 프레임을 찾기 위해 원형 버퍼 검색. - 프레임의 참조비트가 ‘1’이면 ‘0’으로 조정하고 현재 시간으로 고침. - 수정한 페이지에 2차적 기회를 주고 다음 검사 시까지 대치시키지 않음 : 운영체제는 처음으로 만나는 참조비트가 0인 프레임을 교체. - 모든 사용비트가 1인 경우 각 페이지에 2차적 기회를 주며 포인터는 전체 큐를 한 바퀴 돌 수도 있음. 모든 bit가 1인 경우 2차적 알고리즘은 선입선출(FIFO) 대치와 같아짐. - 사용비트가 1인 프레임을 통과하는 과정을 제외하면 선입선출(FIFO) 대치 알고리즘과 비슷함. - 원형으로 배치된 것처럼 보여 시계 알고리즘이라고 함. [그림 8-26] 시계 페이지 대치 알고리즘

3. 페이지 대치 알고리즘 [그림 8-27] 간단한 시계 알고리즘의 예. - 메인 메모리 프레임 m개로 구성된 원형 버퍼가 버퍼 내의 페이지 1개를 새로운 페이지 420으로 교체하기 직전의 모습. - 현재 프레임 포인터는 페이지 768을 가지고 있는 프레임 4번을 가리키고 있음. - 프레임 4번의 사용비트가 1이므로 교체가 되지 않지만 사용비트는 0으로 재설정되고, 포인터는 다음 페이 지로 이동. - 프레임 5에 있는 페이지 9도 교체되지 않고 사용비트만 0으로 재설정되고 포인터는 다음 페이지로 이동. - 다음 차례인 프레임 6은 사용비트가 0이므로 페이지 11은 페이지 420으로 교체됨. - 이때, 사용비트는 1로 설정되고 포인터는 프레임 7번으로 이동. [그림 8-27] 페이지 대치 이전의 버퍼와 페이지 대치 이후의 버퍼 상태

3. 페이지 대치 알고리즘 최소사용 빈도수(LFU, Least Frequently Used) 알고리즘. 각 페이지마다 참조 횟수에 대한 계수기가 있으며, 가장 작은 수를 가진 페이지를 대치함. - 즉, 사용횟수(사용빈도)가 가장 낮은 페이지를 교체하는 기법. - 많이 사용되는 페이지는 큰 참조 횟수 값을 가짐. 어떤 프로세스의 초기 단계에서 한 페이지가 많이 사용되나 그 후로 다시 사용되지 않을 경우 사용하기 어려움. - 큰 계수를 가진 페이지가 더 이상 필요하지 않음에도 메모리 속에 계속 남기 때문. - 계수기를 어떤 일정한 시간 간격으로 하나씩 오른쪽으로 이동해서 지수적으로 감소하는 평균 사용수 를 형성하여 해결 가능함. 최대사용 빈도수(MFU, most Frequently Used) 알고리즘. 가장 작은 계수를 가진 페이지가 방금 들어온 것으로 아직 사용되지 않았기 때문에, 앞으로 사용할 확률이 높다고 가정하여 대치 페이지 후보에서 제외시킴. 가장 많이 사용된 페이지(계수가 높은 페이지)를 대치함. ※ LFU, MFU는 구현 시 비용이 많이 들고 최적 페이지 대치에 비해 성능이 떨어져 일반적으로 사용되지 않음.

3. 페이지 대치 알고리즘 페이지 버퍼링(Page Buffering). FIFO 같은 성능 저하를 막기 위해 교체 대상으로 선택된 페이지를 즉시 교체하지 않고 잠시 동안 메인 메모리에 유지함. 포인터 리스트 두 개를 이용하여 페이지를 관리하며, 페이지 대치 알고리즘은 FIFO임. VAX 컴퓨터의 VMS, XP, Mach에서 사용된 방식. [그림 8-28] 페이지 버퍼링 개념. - 수정 안 된 가용페이지 리스트. : 메모리에 적재된 후에 수정된 적이 없는 프레임 리스트로 교체 불필요. - 변경 페이지 리스트 : 메모리에 적재된 후 수정된 프레임의 리스트로 디스크에 재저장해야 하므로 디스크 기록을 대기함. [그림 8-28] 페이지 버퍼링 개념 변경되지 않은 페이지 교체 시, 교체된 페이지는 메모리에 남고 페이지 프레임은 가용 페이지 리스트의 끝에 추가됨. 변경된 페이지 교체 시, 페이지 프레임을 변경 페이지 리스트의 끝에 추가함.

3. 페이지 대치 알고리즘 알고리즘의 비교 분석 배르(BAER, 1980년) 발표. [그림 8-29] 페이지 대치 알고리즘의 비교. - 분석에 사용한 페이지 크기는 256word이며, 프레임 수를 6, 8, 10, 12, 14개로 변경시키면서 실행. - 적은 수의 프레임을 사용할 경우 차이가 크게 나타남. [그림 8-29] 페이지 대치 알고리즘의 비교

4. 프레임 할당 알고리즘 단독 사용자 시스템 가상 메모리 시스템의 가장 간단한 구조. 메모리 크기가 128K인 단일 사용자 마이크로컴퓨터 시스템에서(페이지 크기는 1K), 이 중 운영체제가 35K를 차지한다면 남은 93K는 사용자 프로세스를 위해 남음. - 순수 요구 페이징 방법 적용 시, 프레임 93개 모두 사용가능 프레임 리스트에 포함됨. - 사용자가 프로세스 수행을 시작하면 페이지 부재가 계속 발생함. - 93번까지의 페이지 부재는 사용가능 페이지 리스트에서 대기 중인 사용 가능 페이지를 모두 사용하게 됨. - 사용 가능한 페이지가 없어질 때, 즉 94번째 발생한 페이지 부재 해결을 위한 해결 방법 필요함. 사용가능 페이지가 없을 때, 페이지 부재 해결 방법. 페이지 대치 알고리즘을 사용. - 기억 장소 내에 있는 페이지 93개 중 하나를 선택하여 교체하며, 이때 페이지 대치 알고리즘을 호출. 사용되지 않는 경우 사용자 페이지로 변환시켜 사용. 사용가능 리스트(93개 중)에서 프레임 3개를 확보하여 페이지 부재 발생 시 항상 사용가능 프레임이 존재하도록 함. ※ 다중 프로그래밍 환경에서 기억 장소 내에 동시에 프로그램이 두 개 이상 존재하므로, 여러 개의 프로세스에 프레임 할당 방법에 대한 문제 발생.

4. 프레임 할당 알고리즘 최소 프레임 수 할당해야 할 최소 프레임 수 존재. 기억 장소 할당은 제한이 있어 총 유효 프레임 수보다 많이 할당할 수 없으나, 할당 가능한 최소 프레임 수는 존재함. - 각 프로세스에 할당되는 프레임 수가 줄어들면서 페이지 부재율은 올라가고 수행 속도는 저하됨. - 성능 저하를 막기 위해 할당해야 할 최소 프레임 수가 존재함. 최소 프레임 수는 명령어 구조에 의해 정의됨. - 수행 중인 명령이 끝나기 전에 페이지 부재 현상 발생 시 그 명령을 처음부터 다시 시작해야 함. - 하나의 명령어를 실행하려면 명령어가 참조하는 모든 페이지를 수용할 수 있는 충분한 프레임이 필요 함. ※ 한 프로세스당 최소 프레임 수는 컴퓨터 구조에 의해 정의되나, 최대 수는 유효 실제 기억 장소의 양으로 정의됨.

4. 프레임 할당 알고리즘 균일과 비례할당 알고리즘 균일할당. 비례할당. 프로세스 n개에 프레임 m개를 할당할 때 각 프로세스에 똑같이 프레임 m/n개씩 나눔. 각 프로세스가 갖는 메모리의 요구량이 서로 다르므로 페이지 프레임 낭비 및 페이지 부재가 발생할 수 있음. 비례할당. 균일할당 방법의 문제점을 해결하기 위해 사용됨. 사용 가능한 메모리를 각 프로세스가 필요로 하는 메모리 양 또는 프로세스의 크기에 비례하여 할당. 운영체제가 활동 중인 프로세스에 대한 정보를 알고 있어야 하며, 소프트웨어 오버헤드를 가져옴. 프로세스 Pi의 가상 메모리 크기를 si라고 하면 전체 프로세스가 갖는 가상 메모리 공간의 크기 S는 아래와 같이 정의됨. 사용가능 프레임의 총수를 m이라 하면 프로세스 Pi에 프레임 ai개를 할당하는데, 이때 ai는 대 략 아래와 같음. - 이때 ai는 명령어 집합이 필요로 하는 최소 프레임 수보다는 크고 총합이 m을 넘지 않는 정수이어야 함. - 프레임 62개를 일반 프로그램(페이지10개)과 대화식 데이터베이스(페이지127개)의 프로세스에 각각 프 레임 4개와 프레임 57개를 분배. m=62, S=137(10+127) 10/137 * 62 = 4 127/137 * 62 = 57

4. 프레임 할당 알고리즘 부하 제어(Load Control) 메인 메모리에서 실행할 프로세스의 개수 결정. 메인 메모리에 적재되어 실행되는 프로세스의 개수를 ‘다중 프로그래밍 수준’이라 함. 메모리 관리를 위해 매우 중요함. - 너무 적은 수의 프로세스가 메인 메모리에서 실행된다면 프로세스들의 보류 상태가 자주 발생하여 빈번한 교체가 발생됨. - 많은 프로세스가 메인 메모리에 적재되면 각 프로세스의 적재집합을 구성하는 평균 페이지 수가 적어 페이지 부재가 자주 발생하여 스레싱 현상을 일으킴.