[5주차] 물리 메모리, 가상 메모리

물리 메모리

메모리 관리자가 하는 일

• 메모리 관리자는 메모리 관리 유닛(MMU)라는 하드웨어이다.
• 메모리 관리자의 작업은 가져오기, 배치, 재배치를 수행한다.

가져오기(fetch)

• 프로세스외 데이터를 메모리로 가져온다.
• 요청할때 메모리로 가져오거나, 미리 가져오는 방법이 있다.

배치 작업 (placement)

• 가져온 프로세스를 메모리의 어느 위치에 올려놓을지 결정한다.
• 페이징 : 메모리를 같은 크기로 자르기
• 세그먼테이션: 프로세스의 크기에 맞게 자르기

재배치 작업 (replacement)

• 메모리에 새로운 프로세스를 가져오기 위해 오래된 프로세스를 내보내는 작업
  • 앞으로 사용하지 않을 프로세스를 내보내면 시스템의 성능이 올라가지만, 자주 사용할 프로세스를 내보낸면 성능이 떨어진다.
• 교체 알고리즘 : 앞으로 사용하지 않을 프로세스를 찾아서 내보내는 알고리즘

 

메모리 주소

절대 주소 지정과 상대주소 지정의 차이점은 뭘까요?

절대 주소

• 메모리 하드웨어 상의 주소
  • 실제 물리 주소를 가리킨다.
  • 메모리 관리자 입장에서 바라본 주소
  • 메모리 주소 레지스터가 사용하는 주소
  • 램 메모리의 실제 주소
• 절대 주소를 사용자가 직접 사용하는 것은 위험하다.
  • 운영 체제가 업그레이드 되면 운영 체제 주소의 범위가 커지는 경우 사용자가 운영체제의 영역을 침범할 수 있다.

상대 주소

• CPU와 실행중인 프로그램이 사용하는 주소
  • 사용자 영역이 시작되는 주소를 시작으로 하여 사용한다.
  • 사용자 프로세스 입장에서 바라본 주소
  • 절대 주소와 관계없이 항상 0번지 부터 시작한다.
• 상대 주소 사용시 운영체제 주소 범위를 알 필요 없어 안전하고 편리하다.

절대 주소와 상대 주소 차이점

• 관점
  • 절대 주소 : 메모리 관리자 입장
  • 상대 주소 : 사용자 프로세스 입장
• 주소 시작 위치
  • 절대 주소 : 물리 주소 0번지부터 시작
  • 상대 주소: 물리 주소와 관계없이 항상 0번지부터 시작
• 주소 공간
  • 절대 주소: 물리 주소(실제 주소) 공간
  • 상대 주소: 논리 주소 공간

 

메모리 할당 - 단일 프로그래밍 환경

메모리 오버레이

• 프로세스 크기가 실제 메모리(물리 메모리)보다 클 때 전체 프로세스를 메모리에 가져오는 대신 적당한 크기로 잘라서 가져오는 기법

 

Swapping(스와핑)이란 무엇인가요?

• 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치(swap 영역)로 내보내고, 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법이다.
  • 대기 상태의 프로세스나 오랫동안 사용하지 않은 프로세스들이 스왑 아웃 대상이 된다.

swap 영역

• 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
  • 스왑 아웃(swap-out) : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
  • 스왑 인(swap-in) : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것

스왑 아웃 되었던 프로세스가 다시 스왑 인될때는 스왑 아웃 되기 전의 물리 주소와는 다른 주소에 적재될 수 있다.

 

• 사용자는 실제 메모리 크기와 스왑 영역의 크기를 합쳐서 전체 메모리로 인식한다.
  • ex) 실제 메모리 크기 1GB + 스왑의 크기 3GB = 메모리 크기 4GB

 

Swapping의 과정을 설명해 주세요.

• 운영체제가 스와핑 대상 프로세스를 선정한다.
• 스왑 아웃 : 선정된 프로세스의 메모리 내용을 보조기억장치의 스왑 영역으로 복사한다.
• 해당 프로세스가 사용하던 메모리 공간을 해제힌디.
• 스왑 인 : 필요한 경우, 스왑 영역에 있던 다른 프로세스를 메모리로 불러온다.

스와핑은 컨텍스트 스위칭 과정에서 일어나며, 프로세스의 상태 정보도 함께 저장/복원된다.

 

Swapping의 장단점을 설명해 주세요.

장점

• 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있다.
  • 메모리 부족 문제를 완화시킨다.
• 프로세스 A,B,C,D 동시 실행 가능
  • 프로세스 A, B, C, D가 모두 메모리에 동시에 올라갈 수 없더라도, swapping을 통해 번갈아가며 메모리에 적재된다.
  • 이로 인해 실제 물리적 메모리 크기보다 큰 총 메모리 요구사항을 가진 프로세스들도 동시에 실행되는 것처럼 보인다.
    ![[5. 가상 메모리-20240912163130257.webp|472]]

스와핑 과정에서 외부 단편화가 발생한다.

 

단점

• swap 영역은 고정된 크기로 설정되어 유동적으로 조절할 수 없어 하드디스크의 공간을 차지한다. (고정 크기)
• 스와핑 과정에서 데이터를 복사하는 데 시간이 소요되어 시스템 성능에 영향을 줄 수 있다. (오버헤드)
• 잦은 스와핑은 디스크 접근을 증가시켜 전체적인 시스템 성능을 저하시킬 수 있다. (디스크 I/O 증가)

 

메모리 할당 - 다중 프로그래밍 환경

메모리 분할에 대해 설명해주세요.

가변 분할 방식

• 프로세스의 크기에 따라 메모리를 나누는 것
  • 메모리의 영역이 각각 다르다.
  • 한 프로세스가 연속된 공간에 배치되므로 연속 메모리 할당이라고 한다.
• ex) 세그먼테이션

장점

• 하나의 프로세스를 연속된 공간에 배치한다.

단점

• 빈 공간을 다시 합쳐야 하는 등 메모리 관리가 복잡하다.
• 외부 단편화 : 빈 영역이 있어도 서로 떨어져 있으면 프로세스를 배정하지 못한다.

 

고정 분할 방식

• 프로세스의 크기와 상관없이 메모리를 같은 크기로 나누는 것
  • 한 프로세스가 분산되어 배치되므로 비연속 메모리 할당이라고 한다.
• ex) 페이징

장점

• 메모리를 일정한 크기로 나누어 관리하기 때문에 메모리 관리가 수월하다.
  • 메모리 통합같은 부가적인 작업을 할 필요가 없다.

단점

• 내부 단편화 : 나눠진 크기보다 작은 프로세스가 올라올 경우 메모리 낭비가 발생한다.

현대 운영체제에서 메모리 관리는 기본적으로 고정 분할 방식을 사용하면서 일부분은 가변 분할 방식을 혼합하고 있다.

 

가변 분할 vs 고정 분할

구분	가변 분할 방식	고정 분할 방식
메모리 단위	세그먼테이션	페이징
특징	연속 메모리 할당	비연속 메모리 할당
장점	프로세스를 한 덩어리로 관리 가능	메모리 관리가 편리
단점	빈 공간의 관리가 어려움	프로세스가 분할되어 처리됨
단편화	외부 단편화	내부 단편화

 

외부 단편화와 내부 단편화의 차이가 뭔가요?

외부 단편화

• 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상

외부 단편화를 해결하기 위해 메모리 배치 기법과 조각 모음(degragmentation)을 사용한다.

 

내부 단편화

• 프로세스 크기가 페이지의 배수는 아니므로 페이지 내에 낭비되는 공간이 생긴다.
• 페이지 크기를 작게 하면 내부 단편화 크기는 작아지지만 페이징 테이블의 크기가 커질 수 있다.
  • 내부 단편화를 적절히 방지하먼서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지 크기를 조절하는 것이 필요하다.

페이징은 외부 단편화 문제는 해결할 수 있지만, 내부 단편화 문제를 야기할 수 있다.

•  

 

메모리 배치 기법 (메모리 관리 전략)에 대해 설명해주세요.

• 메모리 배치 기법 : 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식

최초 적합 (first fit)

• 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
  • 검색을 최소화할 수 있고, 빠른 할당이 가능하다.

최적 적합 (best fit)

• 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

최악 적합 (worst fit)

• 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식

 

메모리 배치 기법중 하나인 버디 시스템에 대해 설명해주세요.

• 가변 분할 방식과 고정 분할 방식의 중간 구조를 가진다.

작동 방식

• 프로세스 크기에 맞게 메모리를 1/2로 자르고 프로세스를 메모리에 배치한다.
• 나뉜 메모리의 각 구역에는 프로세스가 1개만 들어간다.
• 프로세스가 종료되면 주변의 빈 조각과 합쳐서 하나의 큰 덩어리를 만든다.

특징

• 가변 분할 방식처럼 메모리가 프로세스 크기대로 나뉘며, 고정 분할 방식처럼 하나의 구역에 다른 프로세스가 들어갈 수 없고 내부 단편화가 발생한다.
• 버디 시스템은 가변 분할 방식보다 효과적으로 공간을 관리할 수 있다.
  • 비슷한 크기의 조각이 서로 모여 있기 때문에 작은 조각을 통합하여 큰 조각을 만들기가 쉽다.
• 공간 관리 효율성을 따지면 버디 시스템과 가변 분할 방식은 비슷한 수준이다.
  • 고정 분할 방식이 메모리 관리 측면에서 단순하기 때문에 버디 시스템보다 고정 분할 방식이 많이 사용되고 있다.

 

조각 모음(degragmentation)

• 서로 떨어져 있는 여러 개의 빈 공간을 합치는 작업
• 메모리 단편화를 해결하기 위해 사용될 뿐 아니라 하드디스크나 SSD와 같은 저장장치에서도 파일 시스템 성능을 개선하기 위해 사용된다.

 

메모리 배치 기법중 하나인 compaction(압축)에 대해 설명해주세요.

• 메모리 내에 저장된 프로세스를 적당히 재배치시켜 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
  • 메모리 내의 모든 빈 공간을 하나로 모은다.
  • 일반적으로 모든 프로세스를 메모리의 한쪽 끝으로 이동시킨다.
• 전체 메모리를 대상으로 한다.

단점

• 작은 빈 공간을 하나로 모으는 동안 시스템은 하던 일을 중지해야한다.
• 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기한다.
• 어떤 프로세스를 어떻게 움직여야 오버헤들르 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다.

 

메모리 배치 기법중 하나인 coalescing(통합)에 대해 설명해주세요.

• 주기억 장치 내에 인접해 있는 단편화된 공간을 하나의 공간으로 만드는 방법
• 압축과 달리 통합은 지역적이고 점진적인 작업이다.
  • 통합이 되어도 여전히 빈 공간이 분산되어 있을 수 있다.

압축은 주기억 장치 내에 분산되어있는 단편화된 공간을 결합하는 것이고, 통합은 인접해있는 단편화된 공간을 하나로 통합하는 것이다.

•  

 

가상 메모리

가상 메모리에 대해 설명해주세요.

• 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
  • 물리 메모리의 크기와 상관없이 프로세스에 커다한 메모리 공간을 제공하는 기술
• 가상 메모리의 최대 크기는 물리 메모리의 최대 크기로 한정된다.
  • 이론적으로 무한대의 크기를 가지는데, 이는 물리 메모리의 부족한 부분을 swap 영역으로 보충하기 때문이다.

가상 메모리의 크기 = 물리 메모리(실제 메모리) + 스왑 영역

•  

• 가상 메모리 관리 기법에는 페이징과 세그멘테이션이 있다.

가상 메모리 vs 물리 메모리

구분	가상 메모리	물리 메모리
최대 메모리 크기	CPU의 비트 값에 의존	CPU의 비트 값에 의존
메모리 분할 방식	세그먼테이션 페이징 세그먼테이션-페이징 혼용 기법	가변 분할 방식 고정 분할 방식
주소 지정 방식	가상 주소	절대 주소, 상대 주소

• 가상 메모리 시스템에서 가변 분할 방식을 이용한 메모리 관리 기법은 세그먼테이션, 고정 분할 방식을 이용한 메모리 관리 기법은 페이징이라고 한다.
  • 가상 메모리 시스템에서는 주로 두 기법의 단점을 보완한 세그먼테이션-페이징 혼용 기법을 주로 사용한다.

 

가상 주소(논리 주소)와 물리 주소(실주소)에 대해 설명해주세요.

물리 주소

• 실제 하드웨어의 메모리 위치
  • 메모리의 실제 크기에 의해 제한된다.
• 프로그램이 직접 접근할 수 없고, 운영체제에 의해 관리된다.

가상 주소

• 운영체제가 프로그램에 제공하는 논리적인 주소 공간
  • 실제 물리적 위치와 무관하게 연속적이고 큰 주소 공간을 제공한다. (주소 공간 0부터 시작)
• MMU가 가상 주소를 물리 주소로 변환한다.

 

가상 주소를 물리 주소(실주소)로 어떻게 변환할까요?

• 상대 주소를 절대 주소로 변환하는 작업은 메모리 관리자(MMU)가 빠르게 처리한다.
• MMU는 상대 주소에 재배치 레지스터(베이스 레지스터)를 더하여 절대 주소로 변환한다.
  • 재배치 레지스터 : 사용자 영역의 시작 주소 값이 저장된다.
• 한계 레지스터는 논리 주소의 최대 크기를 저장한다.
  • CPU는 메모리 접근 전에 논리 주소가 한계 레지스터보다 작은지 검사한다.

 

메모리 배치 기법중 하나인 페이징에 대해 설명해주세요.

• 고정 분할 방식으로 메모리를 분할해서 관리한다.
  • 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당한다.
• 외부 단편화를 해결한다.
  • 모든 페이지와 프레임은 동일한 크기이므로, 메모리 공간 사이에 사용할 수 없는 빈 공간이 생기지 않는다 (프레임 단위의 빈 공간이 존재한다).
  • 프로세스의 페이지가 메모리에 비연속적으로 할당될 수 있다.
  • 새 프로세스를 메모리에 로드할 때, 빈 프레임들을 찾아 페이지들을 분산 배치하면 된다. 큰 연속된 공간을 찾을 필요가 없다.

 

페이지 테이블

• 페이지 번호를 이용해 페이지가 물리적으로 적재된 프레임을 찾을 수 있다.
• 프로세스마다 페이지 테이블을 가지며 각 프로세스의 페이지 테이블은 메모리에 적재되어 있다.

 

페이지 테이블 레지스터 (PTBR)

• 각 프로세스의 페이지 테이블이 적재된 메모리 주소를 가리킨다.
• PTBR은 프로세스의 PCB에 기록된다.
  • 문맥 교환이 일어날때 PTBR 값도 변경된다.
• 페이지 테이블은 운영체제 영역에 있다.
  • 페이지 테이블의 크기가 커질 경우 일부를 swap 영역으로 옮길 수 있다.

페이지 테이블 매핑 방식에는 직접 매핑, 연관 매핑, 집합-연관 매핑, 역매핑이 있다.

•  

 

TLB (Translation Lookaside Buffer)

• 프레임에 접근하기 위해서 총 2번의 메모리 접근이 필요하다.
  • 메모리에 있는 페이지 테이블을 보기 위해 1번, 그렇게 알게된 프레임에 접근하기 위해 1번
• TLB는 페이지 테이블의 캐시 메모리이다.
  • 최근에 사용된 페이지 위주로 페이지 테이블의 일부를 저장한다.
• TLB 히트 : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB 히트
  • 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없다. (메모리 접근 1번)
• TLB 미스 : 페이지 번호가 TLB에 없을 경우 메모리 내의 페이지 테이블에 접근해야한다. (2번의 메모리 접근)

 

페이징에서의 주소 변환

• 논리주소는 기본적으로 페이지 번호와 변위(offset)으로 이루어져 있다.
• 논리주소<페이지 번호, 변위> 는 페이지 테이블을 통해 물리 주소<페이지 번호, 변위>로 변환된다.

논리 주소의 변위 값와 물리 주소의 변위 값은 같다.

 

페이지 테이블 엔트리

• 페이지 테이블의 각각의 행
• 페이지 번호 - 프레임 번호 뿐 아니라 유효 비트, 보호 비트, 참조 비트, 수정 비트가 있다.

 

유효 비트

• 현재 해당 페이지에 접근 가능 여부
  • 0 : 페이지가 메모리에 적재되어 있지 않은 상태 (swap 영역)
  • 1 : 페이지가 메모리에 적재되어 있는 상태
• 메모리에 적재되지 않은 페이지에 접근하면 페이지 폴트(page fault) 예외가 발생한다.
• 페이지 fault 처리 과정
  • 1. cpu는 기존 작업을 백업한다.
    2. 페이지 폴트 처리 루틴을 실행한다.
    3. 원하는 페이지를 메모리에 가져온 후 유효 비트를 1로 변경한다.
    4. 페이지 폴트를 처리했다면 cpu는 해당 페이지에 접근할 수 있게 된다.

보호 비트

• 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 읽기만 가능한 페이지인지 나타낸다.
• 0, 1로 표현하는 방법
  • 0: 읽기만 가능한 페이지
  • 1: 읽고 쓰기가 가능한 페이지
• r,w,x로 표현하는 방법도 있다.

참조 비트

• CPU가 해당 페이지에 접근한 적이 있는지 여부를 나타낸다.
• 0: 메모리 적재 이후 한번도 읽거나 쓴 적이 없는 페이지
• 1: 적재 이후 CPU가 읽거나 쓴 페이지

수정 비트 (dirty bit)

• 해당 페이지에 데이터를 수정한 적이 있는지 나타낸다.
  • 페이지가 메모리에 사라질 때 보조기억장치에 쓰기 작업을 해야하는지, 할 필요가 없는지를 판단
• 0 : 수정된 적이 없는 페이지
• 1 : 수정된 적이 있는 페이지

 

페이징에서의 Swapping(스와핑)

• 페이지 단위로 스왑 아웃/ 스왑 인이 수행된다.
  • 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃(페이지 아웃)되고, 실행에 필요한 페이지들은 메모리로 스왑 인(페이지 인) 된다.
• 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다.
  • 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있다.
  • 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.

 

쓰기 시 복사

• fork()로 부모 프로세스와 동일한 자식 프로세스가 생성되면, 자식 프로세스가 부모 프로세스와 동일한 프레임을 가리킨다.
  • 굳이 부모 프로세스의 메모리 공간을 복사하지 않고도 동일한 코드 및 데이터 영역을 가리킬 수 있다.
• 부모 프로세스 혹은 자식 프로세스가 페이지에 쓰기 작업을 하면, 그 순간 해당 페이지가 별도의 공간으로 복제된다.
  • 각 프로세스는 자신의 고유한 페이지가 할당된 프레임을 가리킨다.
• 프로세스 생성 시간을 줄이는 것은 물론 메모리 공간 절약도 가능하다.

 

계층적 페이징 (다단계 페이지 테이블)

• 페이지 테이블은 크기가 크기 때문에 모든 페이지 테이블 엔트리를 메모리에 두는 것은 메모리 낭비이다.
• 계층적 페이징 : 페이지 테이블을 여러 개의 페이지로 쪼개고, 페이지들을 가리키는 페이지 테이블(outer 페이지 테이블)을 두는 방식
  • outer 페이지 테이블은 항상 메모리에 존재해야한다.
  • 페이지 테이블 중 몇개는 보조기억장치에 있어도 된다.

• 계층적 페이징을 이용할 경우 논리 주소에 바깥 페이지 번호(outer 페이지)와 안쪽 페이지 번호를 저장해야한다.
  
  

• 바깥 페이지 번호를 통해 outer 페이지 테이블의 페이지 찾기 -> 해당 페이지로 프레임 번호를 찾고 변위를 더함으로써 물리 주소 얻기

페이지 테이블의 계층이 늘어날수록 페이지 폴트가 발생했을 경우 메모리 참조 횟수가 많아지므로 좋지 않다.

 

메모리 배치 기법중 하나인 세그멘테이션에 대해 설명해주세요.

• 가변 분할 방식을 이용하여 가상 메모리를 관리한다.
  • 물리 메모리를 프로세스 크기에 따라 가변적으로 나누어 사용한다.

장점

• 메모리를 프로세스 단위로 관리하기 때문에 페이지 테이블이 작고 단순하다.

단점

• 물리 메모리의 외부 단편화로 인해 물리 메모리 관리가 복잡하다.

 

세그먼테이션-페이징 혼용 기법

• 권한 비트 추가에 따라 페이지 테이블 크기가 커지는 문제를 세그먼테이션 테이블을 이용하여 해결한다.
  • 권한 비트와 같이 중복되는 데이터를 세그먼테이션 테이블로 옮겨 페이지 테이블의 크기를 줄인다.
• 사용자 입장에서는 세그먼테이션 기법을 사용하고, 메모리 관리자 입장에서는 페이징 기법을 사용한다.
  • 세그먼테이션으로 논리적 구조를 유지하면서도 페이징을 통해 물리 메모리를 효율적으로 사용한다.

 

가상 메모리 관리

가져오기 정책

• 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것
  • 가져오기 정책 중 요구 페이징이 일반적이다.
• 요구 페이징 : 프로세스가 요청할 때 메모리로 가져오는 방법
• 미리 가져오기 : 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식
  • ex) 캐시

미리 가져온 데이터가 쓸모 없을 경우 피해가 매우 크므로 현대의 운영체제는 요구 페이징을 기본으로 사용하고 있다.

•  

 

페이지 부재(page fault)를 최소화하려면 어떻게 해야 하나요?

페이지 부재(page fault)

• 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황
  • 페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 메모리 관리자가 스왑 영역에서 물리 메모리로 옮겨야 한다.

 

페이지 부재를 최소화하기 위해 대상 페이지 선정시 지역성을 고려하자.

• swap 영역으로 쫓아낼 대상 페이지를 고를 때는 앞으로 사용하지 않을 페이지를 고르는 것이 좋다.
  • 자주 사용되는 페이지를 쫓아내면 다시 물리 메모리로 불러와야 하기 때문에 성능이 떨어진다.
• 지역성: 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질
  • 공간의 지역성: 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다.
  • 시간의 지역성: 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다.
  • 순차적 지역성 : 여러 작업이 순서대로 진행되는 경향이 있다.

 

페이지 교체에 대해서 설명해주세요.

• 메모리에 빈 프레임이 없을 경우 페이지 부재가 발생하면 메모리에 있는 프레임 중 하나를 스왑 영역으로 내보내야한다.
• 페이지 교체 알고리즘 : 어떤 페이지를 swap 영역으로 내보낼지 결정하는 알고리즘
  • 대상 페이지 : swap 영역으로 보낼 페이지

 

페이지 교체 알고리즘

종류	알고리즘	특징
간단한 알고리즘	무작위	무작위로 대상 페이지를 선정하여 스왑 영역으로 보낸다.
	FIFO	처음 메모리에 올라온 페이지를 스왑 영역으로 보낸다.
이론적 알고리즘	최적	미래의 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보낸다.
최적 근접 알고리즘	LRU	시간적으로 멀리 떨어진 페이지를 스왑 영역으로 보낸다.
	LFU	사용 빈도가 적은 페이지를 스왑 영역으로 보낸다.
	NUR	최근에 사용한 적이 없는 페이지를 스왑 영역으로 보낸다.
	FIFO 변형	FIFO 알고리즘을 변형하여 성능을 높인다.

 

페이지 교체 알고리즘 FIFO에 대해 설명 해주세요.

• 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 swap 영역으로 쫓아낸다.
• 큐로 구현한다.
• 성능이 떨어진다.
  • 메모리에 먼저 올라왔어도 자주 사용되는 페이지가 있고, 나중에 올라왔어도 한번만 사용되는 페이지가 있을 수 있다.

 

FIFO 변형 알고리즘

• FIFO의 단점을 개선하여 FIFO 변형 알고리즘인 2차 기회 페이지 교체 알고리즘과 시계 알고리즘이 있다.

2차 기회 페이지 교체 알고리즘

• FIFO 방식 + 페이지 접근에 성공한 페이지를 큐의 맨 뒤로 옮겨 기회를 한번 더 준다.
• 성능 : LRU, LFU, NUR 페이지 교체 알고리즘보다 약간 낮고 FIFO보다 약간 높다.

 

페이지 교체 알고리즘 클럭 알고리즘에 대해 설명해주세요.

• FIFO, 2차 기회 페이지 교체 알고리즘과 달리 원형 큐를 사용한다.
• 참조 비트 : 메모리에 있는 페이지를 성공적으로 참조하면 1로 변경된다.
• 포인터 : 대상 페이지를 가리킴
  • 포인터가 시계처럼 한 방향으로 돈다.
  • 참조 비트가 1인 페이지는 0으로 설정 후 건너뛴다.
  • 메모리의 바닥에 도착하면 다시 메모리의 상단으로 이동한다.
• 알고리즘이 복잡하고 계산량이 많다.

 

최적 페이지 교체 알고리즘

• 앞으로 사용하지 않을 페이지를 swap 영역으로 옮긴다.
  • 메모리가 앞으로 사용할 페이지를 미리 살펴보고 사용 시점까지 가장 먼 페이지를 대상 페이지로 선정한다.
• 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋다.
  • 하지만 미래의 메모리 접근 패턴을 현실적으로 알 수 없으므로 구현할 수 없다.

 

최적 근접 알고리즘

• 성능이 최적 페이지 교체 알고리즘에 근접하는 최적 근접 알고리즘을 개발하였다.
  • 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정한다.
  • LRU, LFU, NUR 등이 있다.

 

페이지 교체 알고리즘 LRU에 대해 설명 해주세요.

• LRU(Least Recently Used) : 최근에 최소로 사용한 페이지
  • 가장 오랫동안 사용하지 않은 페이지를 대상 페이지로 선정한다.
• 카운터나 참조 비트를 사용해 구현한다.
  • 참조한 시간을 저장하기 위해 추가적인 메모리가 필요하다.
• 성능 : FIFO보다 우수하고 최적 페이지 교체 알고리즘보다 조금 떨어진다.

 

페이지 교체 알고리즘 LFU에 대해 설명 해주세요.

• LFU (Least Frequently Used) : 최소 빈도 사용
  • 최소로 사용된 페이지를 대상 페이지로 선정한다.
• 페이지 접근 횟수(빈도)를 표시하기 위해 추가적인 메모리가 필요하다.
• 성능 : LRU와 비슷하다.

페이지 교체 알고리즘 NUR

• NUR (Not Used Recently) : 최근 미사용
• LRU, LFU 페이지 교체 알고리즘과 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결한 알고리즘
  • 단 2 bit만 사용하면 된다.
• 참조 비트와 변경 비트를 사용하여 미래를 추정한다.
  • 참조 비트 : 페이지에 접근하면 1
  • 변경 비트 : 페이지가 변경되면 1

• 대상 페이지 선정 순서
  • 참조 비트가 0인 페이지를 우선적으로 고려한다.
  • 같은 비트의 페이지가 여러개라면 무작위로 대상 페이지를 선정한다.

NUR 페이지 교체 알고리즘은 메모리 낭비가 적고 쉽게 구현할 수 있기 때문에 가장 많이 사용된다.

•  

스레싱에 대해 설명해주세요.

• 컴퓨터의 성능 : CPU의 속도도 빨라야 하지만 물리 메모리의 크기도 커야 성능이 좋다.
  • 메모리가 꽉 차면 새로운 프로그램을 메모리에 올리기 위해 기존 프로그램을 swap 영역으로 옮기는 횟수가 잦아진다.
• 스레싱 : 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태

 

물리 메모리 크기와 스레싱

• 멀티프로그래밍 정도가 높으면 스레싱이 발생한다.
• 스레싱 발생 지점 : 메모리가 꽉 차면 CPU가 작업하는 시간보다 swap 영역으로 페이지를 보내고 새로운 페이지를 메모리로 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태
• 물리 메모리의 크기를 늘리면 스레싱 발생 지점이 늦춰져서 프로세스를 원만하게 실행할 수 있다.

 

스레싱과 프레임 할당

• 남아있는 프레임을 실행중인 프로세스에 적절히 나누어주어 페이지 부재가 덜 발생해야한다.
• 정적 할당 : 균등 할당과 비례 할당이 있다.
  • 균등 할당 : 프로세스 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당한다.
  • 비례 할당 : 프로세스의 크기에 비례하여 프레임을 할당한다.
    • 작은 프로세스라도 많은 프레임이 필요한 경우가 있다.
    • 당장 필요 없는 프레임을 할당하기 때문에 메모리가 낭비된다.
      
      

• 동적 할당 : 동적으로 프레임을 할당한다.
  • 작업 집합(Working Set) 모델 : 지역성에 기반하여 최근 일정 시간동안 참조된 페이지를 작업 집합으로 만들어 물리 메모리에 유지한다.
  • 페이지 부재 빈도(PFF) : 페이지 부재 비율이 상한선을 초과하면 프레임을 추가하고, 하한선 밑으로 내려가면 프레임을 회수한다.